Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging

Stanley Wei, Alex Damian, Jason D. Lee

Introduction

In high-dimensional statistics, recovering a "planted" or hidden direction $\theta^\star$ from noisy data is a classic challenge. This problem frequently appears in models like Tensor PCA and Single-Index Models (where a target depends on the input through a function like $y = \sigma(\theta^\star \cdot x)$).

This paper demonstrates that simple Langevin dynamics—gradient descent with added noise—can achieve optimal sample complexity for these high-dimensional estimation tasks if the iterates are averaged over time. By combining noise injection with Stochastic Weight Averaging (SWA), the authors show that the algorithm implicitly "smooths" the optimization landscape, allowing it to recover hidden signals with significantly fewer samples than standard Stochastic Gradient Descent (SGD).

The Challenge of the Information Exponent

The difficulty of these estimation problems is governed by the information exponent ($k^\star$). Conceptually, $k^\star$ measures how "flat" the optimization landscape is at initialization; the higher the $k^\star$, the harder it is for a gradient-based algorithm to find the signal.

Previously, researchers identified a fundamental trade-off in sample complexity ($n$) relative to dimensionality ($d$):

  1. Standard SGD/Langevin: Easy to run, but requires a massive number of samples ($n \gtrsim d^{k^\star-1}$).
  2. Explicit Landscape Smoothing: Achieves the optimal sample rate ($n \gtrsim d^{k^\star/2}$), but requires complex, explicit modifications to the loss function.

The central question of this paper is whether we can achieve the optimal "smoothed" rate using the simple, noisy dynamics of Langevin optimization without explicitly changing the loss function.

Methodology: Langevin Dynamics + Iterate Averaging

The authors propose a surprisingly simple two-step approach:

  1. Noise Injection: They run a Stochastic Differential Equation (SDE) on a sphere. This is essentially gradient descent where a specific amount of Gaussian noise is injected at every step (Langevin dynamics).
  2. Iterate Averaging (SWA): Instead of relying on the last position of the algorithm, they compute the average position over the entire training run.

The specific estimator depends on the symmetry of the problem:

  • If the information exponent $k^\star$ is odd, they use the time-averaged iterate directly.
  • If $k^\star$ is even, the first-order average vanishes due to symmetry. Instead, they compute the time-average of the outer product of the iterates ($\theta_t \theta_t^\top$) and extract its top eigenvector.

Key Insights: Implicit Smoothing and Ergodicity

The mathematical engine driving this approach is ergodicity. While any single step of the algorithm might wander aimlessly near the "equator" (remaining nearly orthogonal to the true signal), the average of those steps slowly accumulates a bias toward the hidden direction $\theta^\star$.

  • Implicit Smoothing: The most profound insight is that noise combined with averaging is mathematically equivalent to landscape smoothing. The randomness of Langevin dynamics naturally "blurs" the landscape, and the averaging process extracts the signal from that blur.
  • Surviving the Equator: Previous wisdom suggested that Langevin dynamics fails because it cannot "escape the equator." This paper proves that escaping the equator isn't strictly necessary. Even if the correlation with the signal is tiny at any given step (e.g., $1/\sqrt{d}$), averaging enough iterates will eventually point the estimator in the right direction.

Key Results and Experimental Proof

The authors theoretically prove that their algorithm succeeds with $n \gtrsim d^{\lceil k^\star/2 \rceil}$ samples, matching the best-known theoretical limits for these problems. Furthermore, the averaged iterate can serve as a highly effective "warm start" for standard SGD, enabling a two-stage process that reaches arbitrary accuracy efficiently.

These theoretical guarantees are validated using synthetic high-dimensional datasets, including Tensor PCA and Single-Index Models with various link functions (like Hermite polynomials).

Correlation of the SWA estimator with the true direction for Hermite polynomial link functions.

As seen in the experimental simulations, the "raw" iterates (faint lines) show near-zero correlation with the truth, wandering aimlessly. However, the "averaged" SWA iterates (solid lines) demonstrate clear, rapid convergence to the hidden direction $\theta^\star$.

Limitations and Future Work

While the results are strong, the paper outlines several areas for future exploration:

  • The Minibatch Conjecture: The authors conjecture that standard minibatch SGD (without explicit Langevin noise) might achieve the same optimal rate, as the noise inherent in minibatch sampling could act similarly to Langevin noise. This remains unproven.
  • Knowing $k^\star$: The current algorithm requires prior knowledge of whether $k^\star$ is odd or even to select the correct estimator. Developing a "universal" estimator that adapts automatically would be highly valuable.
  • Gaussian Assumptions: Much of the theoretical proof relies on the input data being Gaussian. Extending these "implicit smoothing" guarantees to more complex, real-world data distributions is an open challenge for the field.

Summary updated

Abstract

Significant recent work has studied the ability of gradient descent to recover a hidden planted direction $\theta^\star \in S^{d-1}$ in different high-dimensional settings, including tensor PCA and single-index models. The key quantity that governs the ability of gradient descent to traverse these landscapes is the information exponent $k^\star$ (Ben Arous et al., (2021)), which corresponds to the order of the saddle at initialization in the population landscape. Ben Arous et al., (2021) showed that $n \gtrsim d^{\max(1, k^\star-1)}$ samples were necessary and sufficient for online SGD to recover $\theta^\star$, and Ben Arous et al., (2020) proved a similar lower bound for Langevin dynamics. More recently, Damian et al., (2023) showed it was possible to circumvent these lower bounds by running gradient descent on a smoothed landscape, and that this algorithm succeeds with $n \gtrsim d^{\max(1, k^\star/2)}$ samples, which is optimal in the worst case. This raises the question of whether it is possible to achieve the same rate without explicit smoothing. In this paper, we show that Langevin dynamics can succeed with $n \gtrsim d^{ k^\star/2 }$ samples if one considers the average iterate, rather than the last iterate. The key idea is that the combination of noise-injection and iterate averaging is able to emulate the effect of landscape smoothing. We apply this result to both the tensor PCA and single-index model settings. Finally, we conjecture that minibatch SGD can also achieve the same rate without adding any additional noise.
BibTeX
@inproceedings{wei2026improved,
  author = {Stanley Wei and Alex Damian and Jason D. Lee},
  title = {{Improved high-dimensional estimation with Langevin dynamics and stochastic weight averaging}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=GYXUD3hGTh},
}
Figure