Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance. Conventional wisdom attributes small generalization error either to properties of the model family, or to the regularization techniques used during training. Through extensive systematic experiments, we show how these traditional approaches fail to explain why large neural networks generalize well in practice. Specifically, our experiments establish that state-of-the-art convolutional networks for image classification trained with stochastic gradient methods easily fit a random labeling of the training data. This phenomenon is qualitatively unaffected by explicit regularization, and occurs even if we replace the true images by completely unstructured random noise. We corroborate these experimental findings with a theoretical construction showing that simple depth two neural networks already have perfect finite sample expressivity as soon as the number of parameters exceeds the number of data points as it usually does in practice. We interpret our experimental findings by comparison with traditional models.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Hey I love this but watch out with this kind of stuff. And by stuff I mean training RNNs to do classification on very small (100s) sets of images. (Also you didn't mention your train/test split?). Which just means, get more data and make a smaller network by likely re-using a trained network.
I highly recommend the paper "Understanding deep learning requires rethinking generalization" (https://arxiv.org/abs/1611.03530), which shows how amazing some RNNs are at memorizing pure noise.
Would love to see different applications of DL on historical visual art: GANNs making new paintings in different styles, mapping meaning-space between artists, style transfer, "is this painting done by this artist?" ...
Yes, and that's the problem. What Zhang et al [2] showed convincingly in the Rethinking paper is that just focusing on the hypothesis space cannot be enough since the same hypothesis space fits real and random data so it's already too large. Therefore, these methods that focus on the hypothesis space have to talk about a bias in practice towards a better subspace, and that already requires studying the specific optimization algorithm in order to understand why it picks certain hypothesis over others in the space.
But once you are ready to do that then algorithmic stability is enough. You don't then need to think about Bayesian ensembles, or other proxies/simplifications…
Read the full comment
etc. but can focus on just the specific learning setup you have. BTW algorithmic stability is not a new idea. An early version showed up within a few years of VC theory in the 80s in order to understand why nearest neighbors generalizes (it wasn't called algorithmic stability then though).
If you are interested in this, also recommend [3].
[2] https://arxiv.org/abs/1611.03530
[3] https://arxiv.org/abs/1902.04742
A decade ago the paper "Understanding deep learning requires rethinking generalization" [0] was published. The submission is a response to that paper and subsequent literature.
Deep neural nets are notable for their strong generalization performance: despite being highly overparametrized they do not seem to overfit the training data. They still perform well on hold-out data and very often on out of distribution data "in the wild". The paper [0] noted a particularly odd feature of neural net training: one can train neural nets on standard datasets to fit random labels. There does not seem to be an inductive bias strong enough to rule out bad overfitting. It is in principle…
Read the full comment
possible to train a model which performs perfectly on the training data but gives nonsense on the test data. But this doesn't seem to happen in practice.
The submission argues that this is unsurprising, and fits within standard theoretical frameworks for machine learning. In section 4 it is claimed that this kind of thing ("benign overfitting") is common to any learning algorithm with "a flexible hypothesis space, combined with a loss function that demands we fit the data, and a simplicity bias: amongst solutions that are consistent with the data (i.e., fit the data perfectly), the simpler ones are preferred".
The fact that the third of these conditions is satisfied, however, is non-trivial, and in my opinion is still not well understood. The results of [0] are reproducible with a wide variety of architectures, with or without any form of explicit regularization. If there is an inductive bias toward "simpler solutions" in fitting deep neural nets it has to come either from SGD itself or from some bias which is very generic in architecture. It's not something like "CNNs generalize well on image data because of an inductive bias toward translation invariant features." While there is some work on implicit smoothing by SGD, for example, in my opinion this is not sufficient to explain the phenomena observed in [0]. What I would find satisfying is a reproducible ablation study of neural net training that removed benign overfitting (+), so that it was clear what exactly are the necessary and sufficient conditions for this behavior in the context of neural nets. As far as I know this still has never been done, because it is not known what this would even entail.
(+) To be clear, I think this would not look like "the fit model still generalizes, but we can no longer fit random labels" but rather "the fit model now gives nonsense on holdout data".
[0] https://arxiv.org/abs/1611.03530
[1] Was an empirical paper that inspired much theoretical follow-up.
[2] Is one such follow-up, and the references therein should point to many of the other key works in the years between.
[3] Introduces the neural tangent kernel (NTK), a theoretical tool used in much of this work. (Not everyone agrees that reliance on NTK is the right way towards long-term theoretical progress.)
[4] Is a more recent paper I haven't read yet that goes into more detail on interpolation. Its authors were well known in more "clean" parts of ML theory (e.g. bandits) and recently began studying deep learning.
---
[1] Understanding deep learning requires rethinking generalization. Zhang et al.,…
Read the full comment
arXiv, 2016. https://arxiv.org/abs/1611.03530
[2] Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization. Azizan et al., arXiv, 2019. https://arxiv.org/abs/1906.03830.
[3] Neural Tangent Kernel: Convergence and Generalization in Neural Networks. Jacot et al., NeurIPS, 2018. https://proceedings.neurips.cc/paper/2018/hash/5a4be1fa34e62...
[4] A Universal Law of Robustness via Isoperimetry. Bubeck et al., NeurIPS, 2021. https://proceedings.neurips.cc/paper/2021/hash/f197002b9a085...
With over-parameterized neural networks, the problem essentially becomes convex and even linear [1], and in many contexts provably converges to a global minimum [2], [3].
The question then becomes: why does this generalize [4], given that the classical theory of Vapnik and others [5] becomes vacuous, no longer guaranteeing lack of over-fitting?
This is less well understood, although there is recent theoretical work here too.
[1] Lee et al (2019). Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. https://proceedings.neurips.cc/paper/2019/hash/0d1a9651497a3...
[2] Allen-Zhu et al (2019). A convergence theory for deep learning via…
Read the full comment
over-parameterization. https://proceedings.mlr.press/v97/allen-zhu19a.html
[3] Du et al (2019). Gradient Descent Finds Global Minima of Deep Neural Networks. http://proceedings.mlr.press/v97/du19c.html
[4] Zhang et al (2016). Understanding deep learning requires rethinking generalization.
[5] Vapnik (1999). The nature of statistical learning theory. https://arxiv.org/abs/1611.03530
I think you misunderstood the point of deep double descent. The x-axis is not number of training epochs, it is model capacity.
I think you'd be interested in https://arxiv.org/abs/1611.03530. It discusses how SGD is an implicit regularizer. We also actually want high variance weights for symmetry breaking.
No it's not scary in the slightest. Missing or scrambled labels are routine in ML and the algorithms are able to handle it.
This was a huge paper a couple years ago that demonstrates deep nets will still find the structure in the data even with totally randomized labels: https://arxiv.org/abs/1611.03530
There are also various well known techniques to verify whether you've over or underfit.
1. people overfit the baby datasets to zero training loss (MNIST) all the time. maybe you meant a "hard" dataset.
2. You clearly have no idea what you are talking about.
This paper is trying to argue a bit about why neural networks generalize well by showing with math that a nn with some of their conditions converges to the zero training loss. It isn't remotely meant to be practical. IT IS A THEORETICAL PAPER.
And comparing it to nearest neighbors of 1 is so so so so so silly it isn't even wrong.
edit. #1 is actually an entire research direction in the theory of machine learning fyi.
It is possible to get neural networks that massively overfit but still generalize (which Is weird).
https://arxiv.org/pdf/1611.03530.pdf
That paper was really famous. It showed you can get zero training loss on data when you replace the labels with random noise.
edit 2: I am sorry to be harsh. It is just hard to read such arrant nonsense.
Check out this classic paper on deep learning with randomized labels:
https://arxiv.org/abs/1611.03530
Spoiler: the neutral net thinks it's doing a really good job!
I would say training a CNN from scratch or even fine-tuning one takes a lot of domain knowledge and best practices which often are not standardised yet. Besides, we don't even know why they generalise in the first place! See: https://arxiv.org/abs/1611.03530, https://arxiv.org/abs/1711.11561
Really don't think that's the best paper to say "sheds quite a bit of light on this". That paper has been somewhat controversial since it came out.
I think https://arxiv.org/abs/1609.04836 is seminal in showing unsharp minima = generalization, the parent's paper is good for showing that gradient descent over non-convex surfaces works fine, https://arxiv.org/abs/1611.03530 is landmark for kicking off this whole generalization business (mainly shows that traditional models of generalization, namely VC dimension and ideas of "capacity" don't make sense for neural nets).
In fact recent research indicates that you can randomly relabel the training examples and the network still achieves zero training error (https://arxiv.org/abs/1611.03530). So it is not "understanding" anything intrinsic or fundamental about the letter "A". Rather, it's just storing training examples somewhere inside of its millions of parameters, which sounds a lot less impressive.
All machine learning models are capable of overfitting. Deep learning does not have a special relationship to overfitting, and in fact, there is some evidence that the structural priors in complex deep networks actually inhibit overfitting and improve generalization [1].
Citing certain examples of misuse of deep learning by folks who "tweaked it till it worked" doesn't say anything about deep learning at large. The same team would do the same with a much less powerful model.
Of course, being able to explain is a very valuable trait. But there's just no evidence that deep learning methods are any less amenable to interpretation than SVMs or decision trees. The latter…
Read the full comment
models' "interpretation" is mostly stuff like "feature 543 and 632 were on" , while deep learning methods can not only do that, but can also synthesize examples of characteristics that the model looked for [2].
[1]: https://arxiv.org/abs/1611.03530
[2]: https://arxiv.org/abs/1605.09304
Based on our current theoretical understanding the we should expect overfitting. In practice however, a very large number of parameters does not necessarily lead to overfitting. Clearly there is a gap between out theoretical understanding and practice. Check out a recent paper that explores exactly this questions:
https://arxiv.org/abs/1611.03530
Timeseries can 100% work like that. If you expect your timeseries data to be coming from a similar distribution that is what you do to train your LSTM. It's not just a magic box - you have to train it to encode useful features in the gate.
Sure, you can prefer to use subsets of a single time series instead of multiple time series. The issue remains that it doesn't matter what your performance on training data is. You still need to partition your dataset into training and test data - otherwise you could just be storing a lookup table for all you know. It looks like the author has trained on the entirety of the dataset, and then is just considering that performance...
Let…
Read the full comment
me put this another way. You do this with a random walk. Train on your entire timeseries - every length 50 window. Say that there's only 8 unique values at each timestep. That means that there's 8^50 possible input sequences into the neural network. A sufficiently complex neural network can fit an arbitrary function, so if you just have a couple thousand windows there's ~(8^50 / 1000) possible functions that can predict the correct output exactly - and this is on noise! And in all likelihood the neural net will learn that noise: https://arxiv.org/abs/1611.03530 Without comparing training and test results there's no way to know that neural network learned anything of value - it can get perfect accuracy on training data that's pure noise!
This stuff is really critical to get right if you're doing machine learning.
Even if it were practically useless (which it is not, although the practical applications are less impressive than the research achievements at this point), it would be magical. Deep learning has dominated imagenet for a decade now, for example. One reason this is magical is because the sota models are extremely over parametrized. There exist weights that perform perfectly on the training data but give random answers on the test data [0]. But in practice these degenerate weights are not found during sgd. What's going on there? As far as I know there is no satisfying explanation.
[0] https://arxiv.org/abs/1611.03530
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.