On exponential convergence of SGD in non-convex over-parametrized learning

Raef Bassily, Mikhail Belkin, Siyuan MaarXiv 2018 · OpenReview

TL;DR

This paper shows that Stochastic Gradient Descent (SGD) can achieve exponential convergence even for non-convex machine learning problems, provided the loss function satisfies the Polyak-Lojasiewicz (PL) condition and the model is over-parameterized enough to achieve interpolation. This bridges a gap between theory and practice, explaining why SGD works so well in modern deep learning settings.

What Problem Does This Paper Address?

Modern machine learning, especially deep learning, heavily relies on over-parameterized models trained with Stochastic Gradient Descent (SGD). Empirically, these methods often converge remarkably fast, even to global minima. However, most theoretical analyses of SGD focus on convex or strongly convex loss functions, which don't fully capture the behavior of deep neural networks. For non-convex problems, theoretical convergence guarantees are typically much slower (e.g., sublinear) than what's observed in practice. This paper aims to reconcile this discrepancy by extending theoretical convergence guarantees to a broader class of non-convex functions that are relevant to machine learning.

Methods

The core of the paper's contribution lies in extending the analysis of SGD convergence to non-convex functions satisfying the Polyak-Lojasiewicz (PL) condition. This condition, stated as $|| \nabla L(w) ||^2 \ge \alpha L(w)$ for some $\alpha > 0$, is a weaker requirement than strong convexity but still strong enough to guarantee convergence.

The authors build upon their previous work [8] which showed exponential convergence for convex loss functions in an interpolation setting. The interpolation setting, common in over-parameterized models, means that at a minimizer $w^*$, the individual loss functions $l_i(w^*)$ are all zero.

The paper then proves a key theorem (Theorem 1) demonstrating that for smooth, $\alpha$-PL loss functions in the interpolation setting, mini-batch SGD with a constant step size achieves exponential convergence. The proof involves carefully analyzing the expected decrease in the loss function at each step, leveraging the PL condition and the properties of mini-batch sampling.

Additionally, the paper explores the transformation invariance of the PL condition, showing that if a function is PL, then its composition with certain transformations (like feature maps) also results in a PL function. This is crucial because many machine learning pipelines involve such transformations.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Bridging the Theory-Practice Gap: The most significant insight is providing a theoretical explanation for the rapid convergence of SGD in non-convex, over-parameterized settings, which has been a long-standing puzzle.
  • The Power of Interpolation: The paper reinforces the idea that interpolation, a hallmark of over-parameterized models, is key to achieving fast convergence, even in non-convex scenarios.
  • The PL Condition as a Sweet Spot: The Polyak-Lojasiewicz (PL) condition emerges as a practical and theoretically tractable condition that captures a broad range of non-convex problems relevant to machine learning, offering a good balance between generality and analytical tractability.
  • Transformation Invariance is Crucial: The demonstration that the PL property is preserved under common transformations (like feature maps) is vital. It means that the fast convergence guarantees extend to models that use these transformations, which is ubiquitous in deep learning.
  • Simpler Analysis for Non-Convexity: The proof for exponential convergence under the PL condition is shown to be surprisingly simple, reminiscent of the original gradient descent analysis, suggesting that the PL condition simplifies the non-convex optimization landscape considerably.

Key Results

  • Exponential Convergence for Non-Convex PL Functions: The paper formally proves that mini-batch SGD with a constant step size achieves exponential convergence for smooth, $\alpha$-PL loss functions in the interpolation setting (Theorem 1).
  • Transformation Invariance: A formal claim (Claim 1) establishes that the PL property is invariant under certain transformations, meaning that if $f$ is $\alpha$-PL, then $f(\Phi(\cdot))$ is also $\alpha'$-PL for some $\alpha'$. This implies that SGD convergence guarantees are preserved under such transformations.
  • Faster Convergence for a Specific Convex Class: For a special class of convex losses that are compositions of strongly convex functions and linear maps, a tighter convergence bound is derived, showing exponential convergence without a dependence on $\alpha$ in the step size (Theorem 2).

Limitations and Future Work

  • Step Size Dependence: The derived step size for exponential convergence in the general PL setting depends on the parameter $\alpha$. The authors pose it as an open question whether this dependence is necessary.
  • Smoothness Assumption: The analysis assumes that the loss functions are $\beta$-smooth. While common, this might not hold for all practical scenarios.
  • Interpolation Requirement: The exponential convergence guarantees are contingent on the interpolation setting. While prevalent in over-parameterized models, it's not universally guaranteed.
  • Future Work: The paper suggests exploring whether the step size dependence on $\alpha$ can be removed for the general PL case. Additionally, the transformation invariance property opens doors for analyzing a wider range of complex machine learning models. The authors also highlight that their results imply exponential convergence for certain classes of neural networks that satisfy the PL condition, suggesting further investigation into these specific architectures.

Summary updated

Abstract

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.
BibTeX
@misc{bassily2018exponential,
  author = {Raef Bassily and Mikhail Belkin and Siyuan Ma},
  title = {{On exponential convergence of SGD in non-convex over-parametrized learning}},
  year = {2018},
  eprint = {1811.02564},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.02564},
}
Figure