I have the impression from some comments that the term "complexity" in a machine learning context is not well understood. It doesn't mean "complicated" from a h

I have the impression from some comments that the term "complexity" in a machine learning context is not well understood. It doesn't mean "complicated" from a human perspective at all, how difficult it is to grok the SVD algorithm vs NN. It actually refers to the complexity of the hypothesis set, which is, intuitively, the number of independent parameters to be learned. What matters in ML is the relative complexity of the hypothesis set (usually very high in deep learning) and the data complexity (sample size). If this relative complexity is too high, overfitting is likely (ie the noise is learned too), generalization bad, and regularization or a simpler model a must.