4 ms·

This mathematical hand waving plagued the field of genetic algorithms and its variants in the 90's until the 'No free lunch theorem' was published from the Sant

This mathematical hand waving plagued the field of genetic algorithms and its variants in the 90's until the 'No free lunch theorem' was published from the Santa Fe institute. It essentially said (my take on it) that if you had no information about the landscape you were searching - then couldn't say much about the algorithm you were selling. https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...

cgmg 9y ago
The problem with the NFL theorem is that, in a sense, it doesn't apply to the real world: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization#NFL_and_Kolmogorov_randomness https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
- viewtransform 9y ago
  True. High-dimensional non-linear systems (like deep NNs) are a frontier we are just beginning to explore with empirical success. 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.
nabla9 9y ago
You are using too general argument. 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.
- viewtransform 9y ago
  Agreed. NFL is general and we need to discuss a specific landscape. 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.
  - aoeusnth1 9y ago
    https://arxiv.org/abs/1710.05468 https://arxiv.org/abs/1710.05468 was an interesting paper that came out recently. 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.
throwaway37874 9y ago
The funnny thing is that there's no proof that SGD converges to the local minima either.

cgmg 9y ago

The problem with the NFL theorem is that, in a sense, it doesn't apply to the real world: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization#NFL_and_Kolmogorov_randomness https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...

viewtransform 9y ago
True. High-dimensional non-linear systems (like deep NNs) are a frontier we are just beginning to explore with empirical success. 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.

nabla9 9y ago

You are using too general argument. 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.

viewtransform 9y ago
Agreed. NFL is general and we need to discuss a specific landscape. 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.
- aoeusnth1 9y ago
  https://arxiv.org/abs/1710.05468 https://arxiv.org/abs/1710.05468 was an interesting paper that came out recently. 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.

throwaway37874 9y ago

The funnny thing is that there's no proof that SGD converges to the local minima either.