2019

On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning

Li, Jian, Luo, Xuanyuan, Qiao, Mingda

Understand

Generalization error (also known as the out-of-sample error) measures how well the hypothesis learned from training data generalizes to previously unseen data.

Proving tight generalization error bounds is a central question in statistical learning theory.
In this paper, we obtain generalization error bounds for learning general non-convex objectives, which has attracted significant attention in recent years.
We develop a new framework, termed Bayes-Stability, for proving algorithm-dependent generalization error bounds.

Built on

Some methods of speeding up the convergence of iteration methods
Boris T Polyak · 1964
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate O ( 1 / k 2 ) (1/k^{2})
Yurii E Nesterov · 1983
Earlier work this paper cites.
Logarithmic sobolev inequalities and stochastic ising models
Richard Holley and Daniel Stroock · 1987
Earlier work this paper cites.
Fokker-planck equation
Hannes Risken · 1996
Earlier work this paper cites.
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al · 1998
Earlier work this paper cites.
Some inequalities for information divergence and related measures of discrimination
Flemming Topsoe · 2000
Earlier work this paper cites.
Stability and generalization
Olivier Bousquet and André Elisseeff · 2002
Earlier work this paper cites.
Leave-one-out error and stability of learning algorithms with applications
André Elisseeff, Massimiliano Pontil, et al · 2003
Earlier work this paper cites.
Metastability in reversible diffusion processes ii: Precise asymptotics for small eigenvalues
Anton Bovier, Véronique Gayrard, and Markus Klein · 2005
Earlier work this paper cites.
Stability of randomized learning algorithms
Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil · 2005
Earlier work this paper cites.
Metastability: a potential theoretic approach
Anton Bovier and Frank den Hollander · 2006
Earlier work this paper cites.
Derivations for linear algebra and optimization
John Duchi · 2007
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Alex Krizhevsky and Geoffrey Hinton · 2009
Earlier work this paper cites.
Bayesian learning via stochastic gradient langevin dynamics
Max Welling and Yee W Teh · 2011
Earlier work this paper cites.
Imagenet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton · 2012
Earlier work this paper cites.
Analysis and geometry of Markov diffusion operators , volume 348
Dominique Bakry, Ivan Gentil, and Michel Ledoux · 2013
Earlier work this paper cites.
Tighter pac-bayes bounds through distribution-dependent priors
Guy Lever, François Laviolette, and John Shawe-Taylor · 2013
Earlier work this paper cites.

Similar

On the importance of initialization and momentum in deep learning
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton · 2013
Cited alongside, same era.
Poincaré and logarithmic sobolev inequalities by decomposition of the energy landscape
Georg Menz, André Schlichting, et al · 2014
Cited alongside, same era.
Stochastic processes and applications: diffusion processes, the Fokker-Planck and Langevin equations , volume 60
Grigorios A Pavliotis · 2014
Cited alongside, same era.
Norm-based capacity control in neural networks
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro · 2015
Cited alongside, same era.
Train faster, generalize better: stability of stochastic gradient descent
Moritz Hardt, Benjamin Recht, and Yoram Singer · 2016
Cited alongside, same era.
Generalization bounds for randomized learning with application to stochastic gradient descent
Ben London · 2016
Cited alongside, same era.
Spectrally-normalized margin bounds for neural networks
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky · 2017
Cited alongside, same era.
Entropy-SGD: Biasing gradient descent into wide valleys
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina · 2017
Cited alongside, same era.
Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data
Gintare Karolina Dziugaite and Daniel M Roy · 2017
Cited alongside, same era.
A pac-bayesian analysis of randomized learning with application to stochastic gradient descent
Ben London · 2017
Cited alongside, same era.
Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky · 2017
Cited alongside, same era.
Information-theoretic analysis of generalization capability of learning algorithms
Aolin Xu and Maxim Raginsky · 2017
Cited alongside, same era.

Then

Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng · 2018
Later among the works it cites.
A PAC-Bayesian approach to spectrally-normalized margin bounds for neural networks
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro · 2018
Later among the works it cites.
Generalization error bounds for noisy, iterative algorithms
Ankit Pensia, Varun Jog, and Po-Ling Loh · 2018
Later among the works it cites.
Pac-bayes bounds for stable algorithms with instance-dependent priors
Omar Rivasplata, Csaba Szepesvári, John S Shawe-Taylor, Emilio Parrado-Hernandez, and Shiliang Sun · 2018
Later among the works it cites.
Local optimality and generalization guarantees for the langevin algorithm via empirical metastability
Belinda Tzen, Tengyuan Liang, and Maxim Raginsky · 2018
Later among the works it cites.
Global convergence of langevin dynamics based algorithms for nonconvex optimization
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu · 2018
Later among the works it cites.
Stochastic gradient descent optimizes over-parameterized deep relu networks
Original
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu · 2018
Later among the works it cites.
Learning and generalization in overparameterized neural networks, going beyond two layers
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang · 2019
Closest in time.
On exact computation with an infinitely wide neural net
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang · 2019
Closest in time.
On lazy training in differentiable programming
Lenaic Chizat, Edouard Oyallon, and Francis Bach · 2019
Closest in time.
Gradient descent finds global minima of deep neural networks
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai · 2019
Closest in time.
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Vitaly Feldman and Jan Vondrak · 2019
Closest in time.
Fisher-rao metric, geometry, and complexity of neural networks
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes · 2019
Closest in time.
Data-dependent sample complexity of deep neural networks via lipschitz augmentation
Colin Wei and Tengyu Ma · 2019
Closest in time.
Regularization matters: Generalization and optimization of neural nets vs their induced kernel
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma · 2019
Closest in time.
A hitting time analysis of stochastic gradient langevin dynamics
Yuchen Zhang, Percy Liang, and Moses Charikar · 2022
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…