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.

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).
