Implicit Regularization in Deep Learning
arXiv (Cornell University)Published 6 September 2017Open access
Behnam Neyshabur
Citations77
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that implicit regularization induced by the optimization method is playing a key role in generalization and success of deep learning models, and how different complexity measures can ensure generalization is studied to explain different observed phenomena in deep learning.
Abstract
In an attempt to better understand generalization in deep learning, we study several possible explanations. We show that implicit regularization induced by the optimization method is playing a key role in generalization and success of deep learning models. Motivated by this view, we study how different complexity measures can ensure generalization and explain how optimization algorithms can implicitly regularize complexity measures. We empirically investigate the ability of these measures to explain different observed phenomena in deep learning. We further study the invariances in neural networks, suggest complexity measures and optimization algorithms that have similar invariances to those in neural networks and evaluate them on a number of learning tasks.
Keywords
Computer ScienceEngineering
arXiv (Cornell University)Very Deep Convolutional Networks for Large-Scale Image Recognition
75,540 Citations2014Karen Simonyan, Andrew Zisserman
This work investigates the effect of the convolutional network depth on its accuracy in the large-scale image recognition setting using an architecture with very small convolution filters, which shows that a significant improvement on the prior-art configurations can be achieved by pushing the depth to 16-19 weight layers.
Proceedings of the IEEEGradient-based learning applied to document recognition
58,219 Citations1998Yann LeCun, Léon Bottou +2 more
This paper reviews various methods applied to handwritten character recognition and compares them on a standard handwritten digit recognition task, and Convolutional neural networks are shown to outperform all other techniques.
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)
50,318 Citations2021Mandi, Jayanta, Canoy, Rocsildes +2 more
A simple numeric simulation of DNA-co-polymerized hydrogel shape change and a genetic algorithm that generates and selects large batches of material designs that compete with one another to evolve and converge on optimal objective-matching designs are constructed.
Neural NetworksDeep learning in neural networks: An overview
18,033 Citations2014Jürgen Schmidhuber
This historical survey compactly summarizes relevant work, much of it from the previous millennium, review deep supervised learning, unsupervised learning, reinforcement learning & evolutionary computation, and indirect search for short programs encoding deep and large networks.
arXiv (Cornell University)Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
15,635 Citations2024Sergey Ioffe
Building a Large Annotated Corpus of English: The Penn Treebank
7,528 Citations1993Mitchell P. Marcus
Reading digits in natural images with unsupervised feature learning
4,546 Citations2024Yuval Netzer
A new benchmark dataset for research use is introduced containing over 600,000 labeled digits cropped from Street View images, and variants of two recently proposed unsupervised feature learning methods are employed, finding that they are convincingly superior on benchmarks.
On the importance of initialization and momentum in deep learning
3,526 Citations2013Ilya Sutskever, James Martens +2 more
It is shown that when stochastic gradient descent with momentum uses a well-designed random initialization and a particular type of slowly increasing schedule for the momentum parameter, it can train both DNNs and RNNs to levels of performance that were previously achievable only with Hessian-Free optimization.
Understanding Machine Learning: From Theory To Algorithms
3,083 Citations2015Shai Shalev‐Shwartz, Shai Ben-David
The aim of this textbook is to introduce machine learning, and the algorithmic paradigms it offers, in a principled way to students and non-expert readers in statistics, computer science, mathematics and engineering.
International Journal of Uncertainty Fuzziness and Knowledge-Based SystemsThe Vanishing Gradient Problem During Learning Recurrent Neural Nets and Problem Solutions
2,936 Citations1998Sepp Hochreiter
The de-caying error flow is theoretically analyzed, methods trying to overcome vanishing gradients are briefly discussed, and experiments comparing conventional algorithms and alternative methods are presented.
ACM SIGACT NewsIntroduction to the Theory of Computation
2,792 Citations1996Michael Sipser
Throughout the book, Sipser builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own.
Lecture notes in computer scienceNeural Networks: Tricks of the Trade
2,146 Citations2012Montavon, Grégoire, Müller, Klaus-Robert +1 more
The second edition of the book augments the first edition with more tricks, which have resulted from 14 years of theory and experimentation by some of the world's most prominent neural network researchers.
Lecture notes in computer scienceRademacher and Gaussian Complexities: Risk Bounds and Structural Results
2,111 Citations2001Peter L. Bartlett, Shahar Mendelson
This work investigates the use of certain data-dependent estimates of the complexity of a function class called Rademacher and Gaussian complexities and proves general risk bounds in terms of these complexities in a decision theoretic setting.
Neural network learning theoretical foundations
1,357 Citations2009Martin Anthony, Peter L. Bartlett
The authors explain the role of scale-sensitive versions of the Vapnik Chervonenkis dimension in large margin classification, and in real prediction, and discuss the computational complexity of neural network learning.
IEEE Transactions on Information TheoryThe sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network
1,187 Citations1998Peter L. Bartlett
Results in this paper show that if a large neural network is used for a pattern classification problem and the learning algorithm finds a network with small weights that has small squared error on the training patterns, then the generalization performance depends on the size of the weights rather than the number of weights.
Journal of Machine Learning ResearchExploring Strategies for Training Deep Neural Networks
1,114 Citations2009Hugo Larochelle, Yoshua Bengio +2 more
Information Processing LettersOccam's Razor
1,077 Citations1987Anselm Blumer, Andrzej Ehrenfeucht +2 more
It is shown that a polynomial learning algorithm, as defined by Valiant (1984), is obtained whenever there exists aPolynomial-time method of producing, for any sequence of observations, a nearly minimum hypothesis that is consistent with these observations.
A rank minimization heuristic with application to minimum order system approximation
994 Citations2001Maryam Fazel, H. Hindi +1 more
It is shown that the heuristic to replace the (nonconvex) rank objective with the sum of the singular values of the matrix, which is the dual of the spectral norm, can be reduced to a semidefinite program, hence efficiently solved.
Fast maximum margin matrix factorization for collaborative prediction
968 Citations2005Jasson D. M. Rennie, Nathan Srebro
This work investigates a direct gradient-based optimization method for MMMF and finds that MMMf substantially outperforms all nine methods he tested and demonstrates it on large collaborative prediction problems.
Deep learning via Hessian-free optimization
714 Citations2010James Martens
A 2nd-order optimization method based on the "Hessian-free" approach is developed, and applied to training deep auto-encoders, and results superior to those reported by Hinton & Salakhutdinov (2006) are obtained.
International Conference on Machine LearningWeighted low-rank approximations
702 Citations2003Nathan Srebro, Tommi Jaakkola
This work provides a simple and efficient algorithm for solving weighted low-rank approximation problems, which, unlike their unweighted version, do not admit a closed-form solution in general.
arXiv (Cornell University)On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
576 Citations2016Nitish Shirish Keskar, Dheevatsa Mudigere +3 more
arXiv (Cornell University)A Simple Way to Initialize Recurrent Networks of Rectified Linear Units
554 Citations2015Quoc V. Le, Navdeep Jaitly +1 more
This paper proposes a simpler solution that use recurrent neural networks composed of rectified linear units that is comparable to LSTM on four benchmarks: two toy problems involving long-range temporal structures, a large language modeling problem and a benchmark speech recognition problem.
Some PAC-Bayesian theorems
489 Citations1998David McAllester
International Conference on Learning RepresentationsExact solutions to the nonlinear dynamics of learning in deep linear neural networks
347 Citations2014Andrew Saxe, James L. McClelland +1 more
It is shown that deep linear networks exhibit nonlinear learning phenomena similar to those seen in simulations of nonlinear networks, including long plateaus followed by rapid transitions to lower error solutions, and faster convergence from greedy unsupervised pretraining initial conditions than from random initial conditions.
Lecture notes in computer scienceRank, Trace-Norm and Max-Norm
332 Citations2005Nathan Srebro, Adi Shraibman
This work studies the rank, trace-norm and max-norm as complexity measures of matrices, focusing on the problem of fitting a matrix with matrices having low complexity, and presents generalization error bounds for predicting unobserved entries that are based on these measures.
arXiv (Cornell University)Breaking the Curse of Dimensionality with Convex Neural Networks
321 Citations2014Francis Bach
arXiv (Cornell University)Optimizing Neural Networks with Kronecker-factored Approximate Curvature
292 Citations2015James Martens, Roger Grosse
arXiv (Cornell University)No More Pesky Learning Rates
291 Citations2012Tom Schaul, Sixin Zhang +1 more
Conference on Learning TheoryNorm-Based Capacity Control in Neural Networks
272 Citations2015Behnam Neyshabur, Ryota Tomioka +1 more
arXiv (Cornell University)Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
248 Citations2017Gintare Karolina Dziugaite, Daniel M. Roy
arXiv (Cornell University)Unitary Evolution Recurrent Neural Networks
222 Citations2015Martín Arjovsky, Amar Shah +1 more
arXiv (Cornell University)Spectrally-normalized margin bounds for neural networks
173 Citations2017Peter L. Bartlett, Dylan J. Foster +1 more
Neural Information Processing SystemsCollaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
166 Citations2010Nathan Srebro, Ruslan Salakhutdinov
arXiv (Cornell University)Path-SGD: Path-Normalized Optimization in Deep Neural Networks
164 Citations2015Behnam Neyshabur, Ruslan Salakhutdinov +1 more
This work revisits the choice of SGD for training deep neural networks by reconsidering the appropriate geometry in which to optimize the weights, and suggests Path-SGD, which is an approximate steepest descent method with respect to a path-wise regularizer related to max-norm regularization.
IEEE Transactions on Information TheoryEfficient agnostic learning of neural networks with bounded fan-in
156 Citations1996Wee Sun Lee, Peter L. Bartlett +1 more
Neural Information Processing SystemsPAC-Bayes & Margins
144 Citations2002John Langford, John Shawe‐Taylor
A new true error bound for classifiers with a margin which is simpler, functionally tighter, and more data-dependent than all previous bounds is shown.
Neural ComputationAlmost Linear VC-Dimension Bounds for Piecewise Polynomial Networks
127 Citations1998Peter L. Bartlett, Vitaly Maiorov +1 more
Upper and lower bounds on the VC dimension and pseudodimension of feedforward neural networks composed of piecewise polynomial activation functions are computed and it is shown that if the number of layers is fixed, then theVC dimension and pseudo-dimension grow as W log W, where W is thenumber of parameters in the network.
arXiv (Cornell University)Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
114 Citations2016Pratik Chaudhari, Anna Choromanska +7 more
Not) Bounding the True Error
80 Citations2001John Langford, Rich Caruana
A new approach to bounding the true error rate of a continuous valued classifier based upon PAC-Bayes bounds is presented, with results of a 2 - 3 order of magnitude improvement vs. the best deterministic neural net bounds.
arXiv (Cornell University)Natural Neural Networks
60 Citations2015Guillaume Desjardins, Karen Simonyan +2 more
Scaling up Natural Gradient by Sparsely Factorizing the Inverse Fisher Matrix
47 Citations2015Roger Grosse, Ruslan Salakhudinov
FActorized Natural Gradient (FANG), an approximation to natural gradient descent where the Fisher matrix is approximated with a Gaussian graphical model whose precision matrix can be computed efficiently is presented.
Implicit Regularization in Matrix Factorization
36 Citations2018Suriya Gunasekar, Blake Woodworth +3 more
It is conjecture and theoretical evidence that with small enough step sizes and initialization close enough to the origin, gradient descent on a full dimensional factorization converges to the minimum nuclear norm solution.
arXiv (Cornell University)Regularization and nonlinearities for neural language models: when are they needed?
32 Citations2013Marius Pachitariu, Maneesh Sahani
arXiv (Cornell University)Generalization Error of Invariant Classifiers
19 Citations2016Jure Sokolić, Raja Giryes +2 more
Information and Inference A Journal of the IMARiemannian metrics for neural networks II: recurrent networks and learning symbolic data sequences
12 Citations2015Yann Ollivier
A training procedure using a gradient ascent in a Riemannian metric is introduced, which produces an algorithm independent from design choices such as the encoding of parameters and unit activities for sparsely connected networks.
A New Perspective on Learning Linear Separators with Large L_qL_p Margins
5 Citations2014Maria-Florina Balcan, Christopher G. Berlind
A bound on the generalization error of learning linear separators with large LqLp margins is proved, which leads to a simple data-dependent sucient condition for fast learning in addition to extending and improving upon previous results.