An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias

Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, Murat A Erdogdu

Introduction

In modern statistical machine learning, Stochastic Gradient Descent (SGD) is the workhorse of optimization. While its convergence properties in convex settings are well-documented, the behavior of SGD in non-convex landscapes—typical of deep learning—remains a subject of intense study. Specifically, while we know SGD can find critical points, we have historically lacked a rigorous framework for uncertainty quantification in these settings.

When training complex models, practitioners often ask: How much do the results fluctuate due to stochastic noise? Can we construct reliable confidence intervals for our estimates? This paper addresses these questions by establishing an asymptotic normality result for constant step size SGD iterates in non-convex and non-smooth regimes, bridging a significant gap in optimization theory.

The Markov Chain Perspective

The core innovation of this work lies in treating the sequence of SGD iterates not merely as an optimization path, but as a Markov Chain. In constant step size SGD, the iterates do not converge to a single point; instead, they explore the parameter space and eventually settle into a "steady state" known as a stationary distribution ($\pi_\eta$).

To analyze this behavior in non-convex environments, the authors rely on several key technical pillars:

  • Dissipativity: Rather than requiring global convexity, the authors assume the objective function is dissipative. This condition ensures that when iterates wander far from the origin, the gradient pushes them back toward a central region, preventing the algorithm from diverging.
  • V-uniform Ergodicity: The authors prove that the SGD Markov Chain converges to its unique stationary distribution at a geometric rate. Crucially, this holds even if the objective function is non-smooth.
  • Polyak-Ruppert Averaging: The study focuses on the average of the SGD iterates. By averaging the trajectory, the high-frequency noise of individual steps is smoothed out, revealing the underlying statistical structure of the algorithm's behavior.

Main Results: Asymptotic Normality and Bias

1. The Central Limit Theorem (CLT)

The primary contribution is the formal proof of a Central Limit Theorem for non-convex SGD. The authors show that as the number of iterations $n$ grows, the distribution of the averaged iterates becomes Gaussian:

$$\sqrt{n}(\bar{\theta}_n - \mu_\eta) \xrightarrow{d} \mathcal{N}(0, \Sigma)$$

Where $\bar{\theta}_n$ is the average of the iterates and $\mu_\eta$ is the mean of the stationary distribution. This result is striking because it demonstrates that even if the underlying loss landscape is "jagged" or multi-modal, the aggregate behavior of the algorithm is remarkably predictable and follows a bell curve.

2. Characterizing the Bias

While the CLT tells us about the fluctuations, it centers around $\mu_\eta$ (the mean of the stationary distribution), not necessarily the true local minimizer ($\theta^*$) of the objective function. This discrepancy is the bias. The authors characterize this bias under various regularity conditions:

  • For smooth non-convex functions, the bias is typically $O(\eta)$ or $O(\sqrt{\eta})$, where $\eta$ is the step size.
  • Under the Polyak-Lojasiewicz (PL) inequality, they recover a linear bias of $O(\eta)$.

This reveals a fundamental trade-off: a larger step size $\eta$ may allow for faster initial exploration, but it increases the distance between the algorithm's "steady state" and the actual optimal point.

Empirical Validation

The theoretical findings were validated using numerical simulations of robust statistical problems known for their non-convexity:

  • Heavy-tailed Linear Regression: Using a non-convex log-loss function with Student-t distributed noise.
  • Blake-Zisserman MLE: A model used in computer vision for corrupted linear regression, which presents a notoriously difficult non-convex landscape.

In these experiments, the empirical distribution of the averaged iterates consistently formed the predicted Gaussian density, regardless of the initialization point, confirming the existence of a unique invariant distribution.

Implications and Future Work

This work provides the theoretical foundation necessary to perform inference on non-convex models trained with SGD. By proving that asymptotic normality holds, it becomes possible to construct confidence intervals, provided the asymptotic variance can be estimated.

However, some challenges remain for practical implementation. The theory requires a "sufficiently small" step size, the bounds of which depend on dissipativity constants that are difficult to calculate for high-dimensional neural networks. Additionally, while the paper suggests methods for variance estimation (such as online bootstrapping or parallel trajectories), the full theoretical analysis of these estimators in the non-convex regime remains an open area for future research.

Summary updated

Abstract

Structured non-convex learning problems, for which critical points have favorable statistical properties, arise frequently in statistical machine learning. Algorithmic convergence and statistical estimation rates are well-understood for such problems. However, quantifying the uncertainty associated with the underlying training algorithm is not well-studied in the non-convex setting. In order to address this shortcoming, in this work, we establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD) algorithm--a widely used algorithm in practice. Specifically, based on the relationship between SGD and Markov Chains [DDB19], we show that the average of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution, as long as the non-convex and non-smooth objective function satisfies a dissipativity property. We also characterize the bias between this expected value and the critical points of the objective function under various local regularity conditions. Together, the above two results could be leveraged to construct confidence intervals for non-convex problems that are trained using the SGD algorithm.
BibTeX
@inproceedings{yu2021analysis,
  author = {Lu Yu and Krishnakumar Balasubramanian and Stanislav Volgushev and Murat A Erdogdu},
  title = {{An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=nZnYVf0k0yY},
}
Figure