KNN: Should we randomly pick "folds" in RandomizedSearchCV? TL;DR
In KNN, K is the hyperparameter so we randomly pick it while performing RandomizedSearchCV. Should we also randomly pick the split [Cross-validation + Train] after k-folding? I am considering both K and k-folds as hyperparameters.
In Detail:
This is my understanding:
Assumptions:

*

*D: Dataset

*K: Number of neighbors

*k: number folds.

*CV: Cross-validation

GridSearchCV
In GridSearchCV, say we pick K = {1, 2, ..., 15} then:

*

*Perform 3-folds on dataset D which splits the dataset like:




Split
CV
Train




1
[0, ... 33%]
[34, ..., 100%]


2
[34, ... 67%]
[0, ..., 33%, 68%, ..., 100%]


3
[67%, ..., 100%]
[0, ... 66%]





*For each K we compute accuracy on each split from the previous table.


*Take mean of accuracies of all the splits for next steps.
RandomizedSearchCV
In RandomizedSearchCV we randomly choose some 15 K values b/w range[3, 25] then:

*

*Sort K.

*Split the dataset D into 3 folds as shown in the above table.

*For each K randomly pick one split.

*Compute accuracy (no need of mean since we are taking only one mean) for next steps.

But my mentor said this approach of RandomizedSearchCV is wrong and we have to apply KNN for each K on all splits. So my questions are:

*

*In the case of KNN what is the benefit/difference of RandomizedSearchCV over GridSearchCV if we are only randomizing hyperparameter K?

*Why should we not randomly pick the split [Cross-validation + Train] after k-folding? I am considering both K and k-folds as hyperparameters.

Update:
Sorry for the confusion, I am not using sklearn. I had implemented RandomizedSearchCV in Kaggle kernel. Check the code here.
 A: As you say, the k-nearest neighbor algorithm has a number of hyperparameters such as the number of neighbors $K$ (but also e.g. distance function, how you summarize outcomes amongst neighbors etc.). If you want to predict with the model for new data, then you want to choose these hyperparameters based on something that mimics the task of interest (i.e. predicting for new unseen data).
Assuming there's no temporal order, clusters or other issues in the data that need to be accounted for, randomly splitting into training data (where the model is fit) and validation data (where we see how it performs to inform our hyperparameter choice) makes sense. Of course, one split gives you a bit of a noisy performance assessment. Thus, randomly splitting the data into $k$ different folds and training $k$ different models (for each leaving out a different validation part) gives you a less noisy assessment after averaging the performance of the different splits. In practice, we tend to use a $k$ between 3 and 10, and if the signal is too noisy still could also repeat this a few times (e.g. 2 to 10). Alternatively, there's also bootstrapping approaches, but we'll ignore those.
You have to fix your validation scheme (i.e. how your cross-validation is done), as you cannot assess/compare different ones. I.e. you cannot pick $k$ (or different random number seeds for splitting etc.) through cross-validation, because you'd compare performance with more or less, and different training data. Similarly, it makes no sense to only look at different validation folds for different hyperparameter values (what can make sense is method (3) below, but that seems very different from what you asked). If you can only afford (i.e. takes too long to train models) to try one training-validation split (or if the dataset is so huge that this would already give a reliable assessment), then you'd want to use the same split for all hyperparameter combinations to ensure comparability to inform your choice.
In some special situation you could use some other source of information to pick these (e.g. in a Kaggle competition one could use the alignment between CV performance and public leaderboard score to assess the CV scheme), but in practice that's not usually an option.
We may have a lot of hyperparameter values to consider and cannot possibly try all possible hyperparameter combinations (esp. if some are continuous). To deal with that a number of strategies have been proposed:

*

*Creating a grid of values (all combinations of all values of all hyperparameters we consider) and trying all the values on the grid (aka sklearn.model_selection.GridSearchCV to use the Python scikit-learn name for it that you used).

*Create a grid of values and randomly select some values on the grid to try (aka sklearn.model_selection.RandomizedSearchCV to use the Python scikit-learn name for it that you used).

*Racing methods (avoid training some models in (1) or (2) when some hyperparameters already do so badly on some splits that they can be clearly abandoned)

*More targeted search methods (such as Bayesian hyperparameter optimization) that attempt to try more informative or more promising hyperparameter values based on the CV results for those that were already tried.

As you can see, the main difference between the two approaches is what hyperparameter values are tried, the cross-validation would be done the same in either case.
A: I agree with your mentor that this is a bad idea.  By randomly selecting the split that you will evaluate, you put the different actual hyperparameter values on unequal footings: maybe K=5 is best, but it got selected with the hardest split and so its accuracy was poor in the search.
Indeed, since you mention the sklearn classes, note that you cannot easily do what you describe using RandomizedSearchCV.  For each hyperparameter point (randomly) selected, models are always fitted-and-scored on every split, and those metrics averaged over folds.
As for your question (1), it depends on how much computational expense you can handle.  If you can and desire to search over all the values of $K$, then do the grid search.  If that'll take too much time (or if you want to search over other hyperparameters), then do a randomized search (or something more clever like a line search or Bayesian search).
