On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport

By Lénaïc Chizat, Francis R. Bach. 2018

854 citations recorded by the source corpus.

Many tasks in machine learning and signal processing can be solved by minimizing a convex function of a measure. This includes sparse spikes deconvolution or training a neural network with a single hidden layer. For these problems, we study a simple minimization method: the unknown measure is discretized into a mixture of particles and a continuous-time gradient descent is performed on their weights and positions. This is an idealization of the usual way to train neural networks with a large hidden layer. We show that, when initialized correctly and in the many-particle limit, this gradient flow, although non-convex, converges to global minimizers. The proof involves Wasserstein gradient flows, a by-product of optimal transport theory. Numerical experiments show that this asymptotic behavior is already at play for a reasonable number of particles, even in high dimension.

Subfields: Artificial Intelligence, Radiology, Nuclear Medicine and Imaging, Statistics and Probability, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Radiology, Nuclear Medicine and Imaging

In Statistics and Probability

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Feature Learning in Infinite-Width Neural Networks (2020, methodology): “Technical Assumptions Earlier works on neural tangent or mean field limits (e.g. (Chizat & Bach, 2018; Fang et al., 2020; Jacot et al., 2018; Mei et al., 2018; Nguyen & Pham, 2020; Rotskoff & Vanden-Eijnden, 2018; Sirignano & Spiliopoulos, 2018)) assume various forms of regularity conditions, such…”
When do neural networks outperform kernel methods? (2020, background): “Further even in the infinite width limit, it is known that two-layers neural networks can actually capture a richer class of functions than the associated RKHS, provided SGD training is scaled differently from the lazy regime [23, 7, 28, 30, 8].”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, methodology): “[18, 54, 42, 53, 49] relate the distribution of the network weights to Wasserstein gradient flows using mean field analysis.”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “, analysis of the dynamics of the algorithm [Li and Yuan, 2017], optimal transport theory [Chizat and Bach, 2018], to name a few.”
Continual Learning in the Teacher-Student Setup: Impact of Task Similarity (2021, methodology): “However, the student dynamics cannot be described by the simple set of ODEs from above; instead, the dynamics of the student are captured by the time-evolution of the density ρ ( θ ) of the full set of parameters θ of the network (Mei et al., 2018; Rotskoff & Vanden-Eijnden, 2018; Chizat & Bach, 201”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…ﬁeld analysis to establish that for inﬁnitely wide neural networks, the empirical distribution of the neural network parameters can be described as a Wasserstein gradient ﬂow (Mei et al., 2018; Chizat & Bach, 2018a; Sirignano & Spiliopoulos, 2018; Rotskoﬀ & Vanden-Eijnden, 2018; Wei et al., 2018).”
On Lazy Training in Differentiable Programming (2018, background): “Relationship to the global convergence result in [7].”
Mean Field Analysis of Neural Networks: A Law of Large Numbers (2018, background): “As it is also extensively discussed in [2], but also pointed out in the recent works by [11, 38, 26], this means that the trajectory’s t 7→ p(t, ·) goal is to minimize the limit objective function L̄(p) as defined by (1.”
Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit (2019, methodology): “As shown in Chizat and Bach (2018b) the existence of a kernel regime is not specific to neural networks but it is a generic feature of overparameterized models, under certain differentiability assumptions.”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, methodology): “There has been a recent surge of research on connecting neural networks trained via gradient descent with the neural tangent kernel (NTK) (Jacot et al., 2018; Du et al., 2018a,b; Chizat and Bach, 2018b; Allen-Zhu et al., 2018a; Arora et al., 2019a,b).”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, background): “, [30, 36, 37, 31, 10, 35]), or allows them to learn in various settings (e.”
How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks (2020, background): “More recent works study the implicit biases induced on MLPs by gradient descent, for both the “NTK” and “adaptive” regimes (Bietti & Mairal, 2019; Chizat & Bach, 2018; Li et al., 2019; Song et al., 2018).”
Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations (2019, methodology): “We mention that this careful analysis has already been proposed by some recent works, e.g. Chizat & Bach (2018) propose a proof for GD in asymptotic sense (m→∞).”