2018

Deep learning generalizes because the parameter-function map is biased towards simple functions

Valle-Pérez, Guillermo, Camargo, Chico Q., Louis, Ard A.

Understand

Deep neural networks (DNNs) generalize remarkably well without explicit regularization even in the strongly over-parametrized regime where classical learning theory would instead predict that they would severely overfit.

While many proposals for some kind of implicit regularization have been made to rationalise this success, there is no consensus for the fundamental reason why DNNs do not strongly overfit.
In this paper, we provide a new explanation.
By applying a very general probability-complexity bound recently derived from algorithmic information theory (AIT), we argue that the parameter-function map of many DNNs should be exponentially biased towards simple functions.

Built on

On the complexity of finite sequences
Abraham Lempel and Jacob Ziv · 1976
Earlier work this paper cites.
Modeling by shortest data description
Jorma Rissanen · 1978
Earlier work this paper cites.
Occam’s razor
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth · 1987
Earlier work this paper cites.
What size net gives valid generalization?
Eric B Baum and David Haussler · 1989
Earlier work this paper cites.
Generalization and parameter estimation in feedforward nets: Some experiments
Nelson Morgan and Hervé Bourlard · 1990
Earlier work this paper cites.
A simple weight decay can improve generalization
Anders Krogh and John A Hertz · 1992
Earlier work this paper cites.
Keeping the neural networks simple by minimizing the description length of the weights
Geoffrey E. Hinton and Drew van Camp · 1993
Earlier work this paper cites.
The relationship between pac, the statistical physics framework, the bayesian framework, and the vc framework
David H Wolpert and R Waters · 1994
Earlier work this paper cites.
Flat minima
Sepp Hochreiter and Jürgen Schmidhuber · 1997
Earlier work this paper cites.
Discovering neural nets with low kolmogorov complexity and high generalization capability
Jürgen Schmidhuber · 1997
Earlier work this paper cites.
Boolean functions with low average sensitivity depend on few coordinates
Ehud Friedgut · 1998
Earlier work this paper cites.
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner · 1998
Earlier work this paper cites.
Some pac-bayesian theorems
David A McAllester · 1998
Earlier work this paper cites.
Bounds for averaging classifiers
John Langford and Matthias Seeger · 2001
Earlier work this paper cites.
On a generalization complexity measure for boolean functions
Leonardo Franco and Martin Anthony · 2004
Earlier work this paper cites.
Gaussian processes in machine learning
Carl Edward Rasmussen · 2004
Earlier work this paper cites.
Generalization ability of boolean functions implemented in feedforward neural networks
Leonardo Franco · 2006
Earlier work this paper cites.
On early stopping in gradient descent learning
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto · 2007
Earlier work this paper cites.
Kernel methods for deep learning
Youngmin Cho and Lawrence K Saul · 2009
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Alex Krizhevsky and Geoffrey Hinton · 2009
Earlier work this paper cites.
Elements of information theory
Thomas M Cover and Joy A Thomas · 2012
Earlier work this paper cites.
GPy: A gaussian process framework in python
GPy · 2012
Earlier work this paper cites.
Robustness and generalization
Huan Xu and Shie Mannor · 2012
Earlier work this paper cites.
On the non-randomness of maximum lempel ziv complexity sequences of finite size
E Estevez-Rams, R Lora Serrano, B Aragón Fernández, and I Brito Reyes · 2013
Earlier work this paper cites.
No free lunch versus Occam’s razor in supervised learning
Tor Lattimore and Marcus Hutter · 2013
Earlier work this paper cites.

Similar

The nature of statistical learning theory
Vladimir Vapnik · 2013
Cited alongside, same era.
Explaining and harnessing adversarial examples
Original
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy · 2014
Cited alongside, same era.
Adam: Amethod for stochastic optimization
Diederik P Kingma and Jimmy Lei Ba · 2014
Cited alongside, same era.
Kolmogorov complexity and its applications
LI Ming and Paul MB Vitányi · 2014
Cited alongside, same era.
On the number of linear regions of deep neural networks
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio · 2014
Cited alongside, same era.
Understanding machine learning: From theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Cited alongside, same era.
Dropout: A simple way to prevent neural networks from overfitting
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov · 2014
Cited alongside, same era.
Deep learning
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton · 2015
Cited alongside, same era.
Human-level control through deep reinforcement learning
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al · 2015
Cited alongside, same era.
Norm-based capacity control in neural networks
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro · 2015
Cited alongside, same era.
Deep learning in neural networks: An overview
Jürgen Schmidhuber · 2015
Cited alongside, same era.
Pac-bayesian theory meets bayesian inference
Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien · 2016
Cited alongside, same era.

Then

A closer look at memorization in deep networks
Original
David Krueger, Nicolas Ballas, Stanislaw Jastrzebski, Devansh Arpit, Maxinder S. Kanwal, Tegan Maharaj, Emmanuel Bengio, Asja Fischer, Aaron Courville, Simon Lacoste-Julien, and Yoshua Bengio · 2017
Later among the works it cites.
Deep neural networks as gaussian processes
Original
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein · 2017
Later among the works it cites.
Theory of deep learning ii: Landscape of the empirical risk in deep learning
Original
Qianli Liao and Tomaso Poggio · 2017
Later among the works it cites.
Why does deep and cheap learning work so well?
Henry W Lin, Max Tegmark, and David Rolnick · 2017
Later among the works it cites.
Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao · 2017
Later among the works it cites.
Empirical analysis of the hessian of over-parametrized neural networks
Original
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou · 2017
Later among the works it cites.
A bayesian perspective on generalization and stochastic gradient descent
Original
Samuel L. Smith and Quoc V. Le · 2017
Later among the works it cites.
The implicit bias of gradient descent on separable data
Original
Daniel Soudry, Elad Hoffer, and Nathan Srebro · 2017
Later among the works it cites.
Towards understanding generalization of deep learning: Perspective of loss landscapes
Original
Lei Wu, Zhanxing Zhu, et al · 2017
Later among the works it cites.
Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms
Original
Han Xiao, Kashif Rasul, and Roland Vollgraf · 2017
Later among the works it cites.
Musings on deep learning: Properties of sgd
Chiyuan Zhang, Qianli Liao, Alexander Rakhlin, Karthik Sridharan, Brando Miranda, Noah Golowich, and Tomaso Poggio · 2017
Later among the works it cites.
Stronger generalization bounds for deep nets via a compression approach
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang · 2018
Closest in time.
To understand deep learning we need to understand kernel learning
Mikhail Belkin, Siyuan Ma, and Soumik Mandal · 2018
Closest in time.
Input–output maps are strongly biased towards simple outputs
Kamaludin Dingle, Chico Q Camargo, and Ard A Louis · 2018
Closest in time.
Essentially no barriers in neural network energy landscape
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht · 2018
Closest in time.
Data-dependent pac-bayes priors via differential privacy
Original
Gintare Karolina Dziugaite and Daniel M Roy · 2018
Closest in time.
Deep convolutional networks as shallow Gaussian processes
Original
Adrià Garriga-Alonso, Laurence Aitchison, and Carl Edward Rasmussen · 2018
Closest in time.
Size-independent sample complexity of neural networks
Noah Golowich, Alexander Rakhlin, and Ohad Shamir · 2018
Closest in time.
Gaussian process behaviour in wide deep neural networks
Original
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani · 2018
Closest in time.
On the importance of single directions for generalization
Original
Ari S Morcos, David GT Barrett, Neil C Rabinowitz, and Matthew Botvinick · 2018
Closest in time.
Towards understanding the role of over-parametrization in generalization of neural networks
Original
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro · 2018
Closest in time.
Bayesian convolutional neural networks with many channels are gaussian processes
Original
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein · 2018
Closest in time.
Theory of deep learning iii: the non-overfitting puzzle
Tomaso Poggio, Kenji Kawaguchi, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack Hidary, and Hrushikesh Mhaskar · 2018
Closest in time.
Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning
Original
Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O Stanley, and Jeff Clune · 2018
Closest in time.
Energy–entropy competition and the effectiveness of stochastic gradient descent in machine learning
Yao Zhang, Andrew M Saxe, Madhu S Advani, and Alpha A Lee · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…