2020

Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss

Chizat, Lenaic, Bach, Francis

Understand

Neural networks trained to minimize the logistic (a.k.a.

cross-entropy) loss with gradient-based methods are observed to perform well in many supervised classification tasks.
Towards understanding this phenomenon, we analyze the training and generalization behavior of infinitely wide two-layer neural networks with homogeneous activations.
We show that the limits of the gradient flow on exponentially tailed losses can be fully characterized as a max-margin classifier in a certain non-Hilbertian space of functions.

Built on

Lexicographic and depth-sensitive margins in homogeneous and non-homogeneous deep models
Original
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry · 1905
Earlier work this paper cites.
A refined primal-dual analysis of the implicit bias
Original
Ziwei Ji and Matus Telgarsky · 1906
Earlier work this paper cites.
On general minimax theorems
Maurice Sion · 1958
Earlier work this paper cites.
A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
Lee K. Jones · 1992
Earlier work this paper cites.
Universal approximation bounds for superpositions of a sigmoidal function
Andrew R. Barron · 1993
Earlier work this paper cites.
Numerical Analysis
Walter Gautschi · 1997
Earlier work this paper cites.
Bounds on rates of variable-basis and neural-network approximation
Vera Kurková and Marcello Sanguineti · 2001
Earlier work this paper cites.
Empirical margin distributions and bounding the generalization error of combined classifiers
Vladimir Koltchinskii and Dmitry Panchenko · 2002
Earlier work this paper cites.
Mirror descent and nonlinear projected subgradient methods for convex optimization
Amir Beck and Marc Teboulle · 2003
Earlier work this paper cites.
Stochastic Approximation and Recursive Algorithms and Applications , volume 35
Harold Kushner and G. George Yin · 2003
Earlier work this paper cites.
Smooth minimization of non-smooth functions
Yurii Nesterov · 2005
Earlier work this paper cites.
Convex neural networks
Yoshua Bengio, Nicolas Le Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte · 2006
Earlier work this paper cites.
A nonsmooth Morse–Sard theorem for subanalytic functions
Jérôme Bolte, Aris Daniilidis, and Adrian Lewis · 2006
Earlier work this paper cites.
Probabilistic representation and uniqueness results for measure-valued solutions of transport equations
Stefania Maniglia · 2007
Earlier work this paper cites.
Gradient Flows: in Metric Spaces and in the Space of Probability Measures
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré · 2008
Earlier work this paper cites.
Random features for large-scale kernel machines
Ali Rahimi and Benjamin Recht · 2008
Earlier work this paper cites.

Similar

Information, physics, and computation
Marc Mézard and Andrea Montanari · 2009
Cited alongside, same era.
Randomized smoothing for stochastic optimization
John C. Duchi, Peter L. Bartlett, and Martin J. Wainwright · 2012
Cited alongside, same era.
Margins, shrinkage, and boosting
Matus Telgarsky · 2013
Cited alongside, same era.
In search of the real inductive bias: On the role of implicit regularization in deep learning
Original
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro · 2014
Cited alongside, same era.
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Stochastic particle gradient descent for infinite ensembles
Original
Atsushi Nitanda and Taiji Suzuki · 2017
Cited alongside, same era.
Integration methods and optimization algorithms
Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d’Aspremont · 2017
Cited alongside, same era.
On the global convergence of gradient descent for over-parameterized models using optimal transport
Lénaïc Chizat and Francis Bach · 2018
Cited alongside, same era.
Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced
Simon S. Du, Wei Hu, and Jason D. Lee · 2018
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Cited alongside, same era.
Risk and parameter convergence of logistic regression
Original
Ziwei Ji and Matus Telgarsky · 2018
Cited alongside, same era.
Learning overparameterized neural networks via stochastic gradient descent on structured data
Yuanzhi Li and Yingyu Liang · 2018
Cited alongside, same era.

Then

The implicit bias of gradient descent on separable data
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro · 2018
Later among the works it cites.
When will gradient methods converge to max-margin classifier under ReLU models?
Original
Tengyu Xu, Yi Zhou, Kaiyi Ji, and Yingbin Liang · 2018
Later among the works it cites.
Sparse optimization on measures with over-parameterized gradient descent
Original
Lénaïc Chizat · 2019
Later among the works it cites.
On lazy training in differentiable programming
Lénaïc Chizat, Edouard Oyallon, and Francis Bach · 2019
Later among the works it cites.
Gradient descent provably optimizes over-parameterized neural networks
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh · 2019
Later among the works it cites.
Spherical Hellinger–Kantorovich gradient flows
Stanislav Kondratyev and Dmitry Vorotnikov · 2019
Later among the works it cites.
Gradient descent maximizes the margin of homogeneous neural networks
Original
Kaifeng Lyu and Jian Li · 2019
Later among the works it cites.
Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
Original
Song Mei, Theodor Misiakiewicz, and Andrea Montanari · 2019
Later among the works it cites.
The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime
Original
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan · 2019
Later among the works it cites.
A function space view of bounded norm infinite width ReLU nets: The multivariate case
Original
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro · 2019
Later among the works it cites.
Neuron birth-death dynamics accelerates gradient descent and converges asymptotically
Grant Rotskoff, Samy Jelassi, Joan Bruna, and Eric Vanden-Eijnden · 2019
Later among the works it cites.
How do infinite width bounded norm networks look in function space?
Original
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro · 2019
Later among the works it cites.
Mean field analysis of neural networks: A central limit theorem
Justin Sirignano and Konstantinos Spiliopoulos · 2019
Later among the works it cites.
Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma · 2019
Later among the works it cites.
On the convergence of gradient descent training for two-layer relu-networks in the mean field regime
Original
Stephan Wojtowytsch · 2020
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…