5 ms·
When the network is deep or big enough, local minimums tend to have loss close to global optimum. There is theoretical and empirical evidence for this. Global
by nabla9 9y ago
When the network is deep or big enough, local minimums tend to have loss close to global optimum. There is theoretical and empirical evidence for this. Global minimum is usually overfitting so what is needed is getting close enough.
In practice algorithms like stochastic gradient descent have problems distinguishing between saddle points and local minima. There is hypothesis that in many/most cases local minima where algorithms get stuck are actually saddle points with long plateau.
- deleted 9y ago[deleted]
- viewtransform 9y agoThis 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 agoThe 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 agoTrue. 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 agoYou 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 agoAgreed. 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 agohttps://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 agoThe funnny thing is that there's no proof that SGD converges to the local minima either.
- YeGoblynQueenne 9y ago>> Global minimum is usually overfitting so what is needed is getting close enough. If the global minimum is overfitting, then what are local minima doing, exactly? Generalising well? I find that very hard to believe. Also- we're talking about overfitting in the context of a particular training dataset, right? Because we all know that it doesn't matter how well your model validates against your out-of-sample data, its performance is going to fall by 10% to 20% once it hits the real world and has to deal with truly unseen data.
- chillee 9y agoYes. Specifically, the common argument has become that flat minima generalize well. As for the last part, when people talk about overfitting we're typically ignoring distributional shift. Otherwise, models can achieve very good generalization.
- breatheoften 9y agoIs there a separate word from overfitting to refer to generalization performance in a way that explicitly includes distributional shift? Just curious as I never realized that overfitting was commonly constrained in the way you describe and would like to go back and relabel my knowledge to better distinguish between your definition of overfitting and a more general version.
- chillee 9y agoGeneralization performance is typically defined in roughly this manner. Assume your training data consists of a sample S of m elements from your full distribution D. Let L(S) be the average loss for your model (hypothesis is also a common term) on S, and L(D) be the average loss for your model on D. Now, we say that training generalizes if your model that minimizes L(S) also achieves similarly low L(D). In practice, we detect generalization by taking a separate sample (validation set) S_2 from D and using L(S_2) to approximate L(D). I'm not familiar with any literature of generalization to arbitrary distributional shift between training and test. If you allow arbitrary distributional shift (say we decide that all dogs are now called cats and all cats are now called dogs), it's pretty clear that you can get arbitrarily poor "generalization".