Convergence Rates of Non-Convex Stochastic Gradient Descent Under a Generic Lojasiewicz Condition and Local Smoothness

Kevin Scaman, Cédric Malherbe, Ludovic Dos SantosICML 2022 · OpenReview

The Challenge of Non-Convex Optimization

Training over-parameterized neural networks involves the empirical minimization of highly non-convex objective functions. We know that these large networks are surprisingly adept at finding global minima (zero training loss), even though their "loss landscapes" are messy and complex. Historically, theorists explained this phenomenon using the Polyak-Łojasiewicz (PL) condition, which essentially posits that the gradient remains large enough to keep the optimizer moving until it hits a global minimum.

However, the standard PL condition has two major flaws:

  1. Loss Limitation: It primarily works for quadratic losses like Mean Squared Error (MSE). It fails to accurately describe Cross-Entropy (CE) or Logistic loss, where the "optimal" parameters might actually reside at infinity.
  2. Global Assumptions: It often assumes the function is "smooth" everywhere, which is rarely true for deep neural networks.

This paper aims to provide a unified theoretical framework that explains why Stochastic Gradient Descent (SGD) converges for almost any convex loss function used in deep learning, relying on more realistic "local" conditions.

Introducing Localized Conditions: $SL^*$ and $KL^*$

To bridge the gap between theory and practice, the authors introduce two novel, localized assumptions:

  • The $KL^*$ Condition: A generalization of the PL condition that allows for non-linear relationships between the gradient norm and the loss value. This flexibility is crucial for modeling the "flatter" gradients typically seen when using Cross-Entropy.
  • The $SL^*$ Condition: An even more flexible variant (Separable-Łojasiewicz) where the gradient lower bound depends on both the current loss and the distance from the starting point (initialization). This is essential for losses where the optimum doesn't exist at a finite point in parameter space.

Crucially, the authors combine these conditions with Local Smoothness. Instead of assuming the network is well-behaved everywhere, they only require it to be smooth within a specific radius of the starting weights—a much more defensible assumption for modern architectures.

Key Insights: How Loss Dictates Speed

One of the most striking insights from the paper is how significantly the choice of loss function alters the convergence rate.

Gradient Descent with Mean Squared Error (MSE)
Gradient Descent with Cross-Entropy (CE)

By plotting the gradient norm against the loss during training, the authors demonstrate that the empirical "slope" of the training trajectory perfectly matches the lower bounds predicted by their $SL^*$ and $KL^*$ conditions.

  • Convergence Rates: While MSE converges relatively quickly, reaching precision $\epsilon$ in $O(\epsilon^{-2})$ steps for SGD, Cross-Entropy is theoretically much slower, requiring $O(\epsilon^{-4})$ steps. For general convex losses, the authors prove that SGD will converge in the over-parameterized regime, though the rate depends on the specific "capacity" ($\kappa$) of the model.
  • The "High-Dimensional Blessing": The authors identify three regimes for SGD convergence. Interestingly, in very high-dimensional spaces, the "noise" in the gradient becomes less harmful. Because the noise is spread across so many dimensions, its projection along the actual direction of the gradient scales by $1/\sqrt{d}$, making the optimizer more robust as the model gets wider.

Experimental Validation

The authors validated their theoretical findings using standard benchmarks like MNIST and CIFAR10. They employed a ResNet-18 architecture with GELU activations (to ensure the "smoothness" required by the math) and compared Gradient Descent (GD) against Stochastic Gradient Descent (SGD). Their experiments confirm that the theoretical bounds derived aren't just mathematical curiosities—they accurately describe the behavior of real ResNets.

Limitations and Future Work

While a significant step forward, the framework has a few limitations:

  • Smoothness Constraints: The current analysis requires smooth activation functions (like GELU or Sigmoid). Extending this to non-smooth "sub-gradient" regimes (like the widely used ReLU) is a logical next step.
  • Tightness of Bounds: While the authors provide upper bounds on convergence time, it remains to be seen if these bounds are "tight" (i.e., the absolute best possible) or if faster rates can be proven with even more specific assumptions.
  • Beyond Classification: The work focuses on standard supervised learning. Applying these Łojasiewicz conditions to more complex tasks like Reinforcement Learning or Generative Modeling (GANs/Diffusion) remains an open frontier.

Summary updated

Abstract

Training over-parameterized neural networks involves the empirical minimization of highly non-convex objective functions. Recently, a large body of works provided theoretical evidence that, despite...
BibTeX
@inproceedings{scaman2022convergence,
  author = {Kevin Scaman and Cédric Malherbe and Ludovic Dos Santos},
  title = {{Convergence Rates of Non-Convex Stochastic Gradient Descent Under a Generic Lojasiewicz Condition and Local Smoothness}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=W_6RpJwg1N0},
}
Figure