On exponential convergence of SGD in non-convex over-parametrized learning
Large over-parametrized models learned via stochastic gradient descent (SGD) methods have become a key element in modern machine learning. Although SGD methods are very effective in practice, most theoretical analyses of SGD suggest slower convergence than what is empirically observed. In our recent work [8] we analyzed how interpolation, common in modern over-parametrized learning, results in exponential convergence of SGD with constant step size for convex loss functions. In this note, we extend those results to a much broader non-convex function class satisfying the Polyak-Lojasiewicz (PL) condition. A number of important non-convex problems in machine learning, including some classes of neural networks, have been recently shown to satisfy the PL condition. We argue that the PL condition provides a relevant and attractive setting for many machine learning problems, particularly in the over-parametrized regime.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Exponential convergence rates for momentum stochastic gradient descent in the overparametrized setting
We prove explicit bounds on the exponential rate of convergence for the momentum stochastic gradient descent scheme (MSGD) for arbitrary, fixed hyperparameters (learning rate, friction parameter) and its continuous-in-ti…
FrictionFirst Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions
Machine learning algorithms typically perform optimization over a class of non-convex functions. In this work, we provide bounds on the fundamental hardness of identifying the global minimizer of a non convex function. S…
BIG-bench Machine Learningparameter estimationParametrized Accelerated Methods Free of Condition Number
Analyses of accelerated (momentum-based) gradient descent usually assume bounded condition number to obtain exponential convergence rates. However, in many real problems, e.g., kernel methods or deep neural networks, the…
Ergodicity of the underdamped mean-field Langevin dynamics
We study the long time behavior of an underdamped mean-field Langevin (MFL) equation, and provide a general convergence as well as an exponential convergence rate result under different conditions. The results on the MFL…
The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
In this paper we aim to formally explain the phenomenon of fast convergence of SGD observed in modern machine learning. The key observation is that most modern learning architectures are over-parametrized and are trained…