I have on my uni lecture notes that one of the n-fold cross-validation disadvantages is that it is very expensive to train this because this could take a long time if the dataset is very large. But they say that this is not the case if we use k-nearest neighbors classifier. I know to some extend what a k-nearest neighbors classifier does, it tries to calculate a distance between the current example to all it k neighbors and assign this current example the label of the nearest example in terms of distance to current example. But I still don't get the connection to why n-fold CV is not expensive in this case.

Some clarification on this question is appreciated! Thanks


1 Answer 1


Your understanding is correct, but for the point of interest what matters is that k-NN is a "lazy learner" (see explanations for example here or here): training a k-NN model requires no computation, the training data is only stored as is. The computation happens at testing: any test instance needs to be compared to the instances in the training set to determine its label based on the closest ones. So the training is fast and the testing is slow, as opposed to most standard ML algorithms.

If one compares what happens in k-fold CV compared to what happens with a simple train-test split, assuming that the test set in the latter case has the same size as the full data used for CV:

  • the training is repeated k times, so it takes much more time if the training stage is long.
  • applying the model is proportional to the number of instances. If this number is the same in the two cases, there's no difference.

Thus there is little or difference in time for k-NN, as opposed to most other learning methods.

  • $\begingroup$ Could you share any documentation to understand this in more details $\endgroup$ Apr 6, 2022 at 13:00
  • $\begingroup$ @Ashwiniku918 good point. I added a few references I could find. I'm not sure if there are any refs for the specific points about CV and kNN though. $\endgroup$
    – Erwan
    Apr 6, 2022 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.