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

Abstract

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.

Advances in Neural Information Processing Systems (NIPS), Dec 2018, Montréal, Canada

Cited by in corpus (32)

• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Mean Field Limit for Coulomb-Type Flows
• Supervised learning from noisy observations: Combining machine-learning techniques with data assimilation
• Propagation of chaos: a review of models, methods and applications. II. Applications
• Analyzing Upper Bounds on Mean Absolute Errors for Deep Neural Network Based Vector-to-Vector Regression
• Mathematical Models of Overparameterized Neural Networks
• Convergence analysis for gradient flows in the training of artificial neural networks with ReLU activation
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• Quantitative Propagation of Chaos for SGD in Wide Neural Networks
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• When does OMP achieve exact recovery with continuous dictionaries?
• Unbiased deep solvers for linear parametric PDEs
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion
• Soft Mode in the Dynamics of Over-realizable On-line Learning for Soft Committee Machines
• Regression as Classification: Influence of Task Formulation on Neural Network Features
• A Mathematical Framework for Learning Probability Distributions
• Proximal methods for point source localisation
• Optimal Protocols for Continual Learning via Statistical Physics and Control Theory
• Global Convergence of SGD On Two Layer Neural Nets
• Law of large numbers and central limit theorem for wide two-layer neural networks: the mini-batch and noisy case
• The RL Perceptron: Generalisation Dynamics of Policy Learning in High Dimensions
• The loss landscape of deep linear neural networks: a second-order analysis
• Rethinking Gauss-Newton for learning over-parameterized models
• Phase Diagram of Initial Condensation for Two-layer Neural Networks
• FastPart: Over-Parameterized Stochastic Gradient Descent for Sparse optimisation on Measures
• Law of Large Numbers for Bayesian two-layer Neural Network trained with Variational Inference
• Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• Decomposed resolution of finite-state aggregative optimal control problems