I am stuck on a theoretical roadblock in learning about machine learning, because I have not seen this explicitly addressed anywhere. In my studies, it seems as if Cross-validation (or some variant thereof, like LOOCV, or potentially another, but similar, validation scheme like bootstrapping) is the be-all-end-all of model selection. Choosing models and their parameters via exhaustive CV to maximize fit but also balance overfitting seems the optimal way to create models, and computational power is only getting cheaper. So what is there left to do for the human analyst?

I apologize in advance for this amateurish question, but could anyone fill in this gap for me, and potentially suggest some sources on model selection?


1 Answer 1


There is something known as the VC dimension of a hypothesis class. This refers to the maximum number of datapoints with arbitrary binary labels that can be correctly classified by a model from the hypothesis class.


If your number of datapoints is larger than the VC dimension for the hypothesis class you have chosen (say set of 2d hyperplanes), then no matter how much you tune your model using cross validation you can never achieve complete accuracy. Hence, the analyst has the important job of choosing the correct hypothesis class while making sure it doesn't overfit. In the case of deep learning this would mean coming up with a specific architecture and is often one of the most difficult tasks.

  • $\begingroup$ This sounds like a fascinating concept. Is there anything else like this to keep in mind in statistics/machine learning? $\endgroup$
    – Coolio2654
    Nov 8, 2018 at 3:38
  • $\begingroup$ Other aspects of a model including hyperparameters, choice of optimizer etc. also need to be chosen by the analyst. PS - Do upvote/ accept the answer if you found it useful :) $\endgroup$
    – Anshul G.
    Nov 8, 2018 at 12:53
  • $\begingroup$ I have heard that hyperparameters are usually not chosen via Cross-validation: why though? They just expand the parameter space and make the search more costly, so is it a fact that cross-validating over hyperparameters is too costly even for today's computers? So it seems in the end it comes back to computational power again. $\endgroup$
    – Coolio2654
    Nov 8, 2018 at 17:46
  • $\begingroup$ If you have infinite computation power, theoretically you could bruteforce through every possible model and hypothesis class. $\endgroup$
    – Anshul G.
    Nov 8, 2018 at 18:37
  • $\begingroup$ To follow up with one last naive question, then is that all the people at google and banks do, simply wait around for the best model to be calculated for them? I think there is something missing to this answer, but I appreciate the insight so far $\endgroup$
    – Coolio2654
    Nov 8, 2018 at 22:18

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.