On exponential convergence of SGD in non-convex over-parametrized learning
This addresses the gap between theoretical convergence rates and empirical performance for SGD in over-parametrized learning, which is incremental as it builds on prior convex results.
The paper extends exponential convergence results for SGD with constant step size from convex loss functions to a broader class of non-convex functions satisfying the Polyak-Lojasiewicz condition, showing that this applies to important machine learning problems like some neural networks in over-parametrized settings.
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.