https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
We are talking about continuous multidimensional optimization. We have already selected our bias and subset of problems we want to solve. Now we are figured out that in this domain there are some theoretical reasons that explain why gradient descent works so well over large number of problems.
Deep learning is continuous <nonlinear> multidimensional optimization - yes.
What defines the subset of problems ? a general nonlinear mapping from R^n to R^m n>m ? or are you limiting to image classification ? speech recognition ? which would be a subset.
We have empirical evidence that deep-learning works but I'm not confident that we have the mathematical tools to understand why.
It showed that large CNN models which have far greater capacity than the data they are shown (and could have memorized it) still tend to learn very good generalizable minima.
See proposition 1:
(i) For any model class F whose model complexity is large enough to memorize any dataset and which includes f∗ possibly at an arbitrarily sharp minimum, there exists (A, Sm) such that the generalization gap is at most epsilon, and
(ii) For any dataset Sm, there exist arbitrarily unstable and arbitrarily non-robust algorithms A such that the generalization gap of f_A(Sm) is at most epsilon.
https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
However, if I was a VC - my knowledge of the NFL would make me look skeptically at any grandiose claims of miracle learning algorithms. In a sense, it provides me with an upper bound to BS.