Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization

Tuo Liu, El Mehdi Saad, Wojciech Kotłowski, Francesco Orabona

This paper, recently published by researchers from KAUST and the Poznan University of Technology, solves a long-standing theoretical mystery in the world of optimization: Does Stochastic Dual Averaging (SDA) actually work for non-convex problems?

While practitioners have used Dual Averaging variants for years, and its theory for convex problems is rock-solid, the non-convex case remained a "theoretical black hole"—until now.

TL;DR

The authors provide the first finite-time convergence guarantees for Stochastic Dual Averaging (SDA) on smooth, non-convex functions. They prove that SDA matches the optimal $O(1/\sqrt{T})$ convergence rate of SGD and introduce an adaptive version (ADA-DA) that works without knowing the noise level of the data.

What Problem Does This Paper Address?

In the "recipe book" of first-order optimization, there are two main families: Gradient Descent (GD) and Dual Averaging (DA).

  • SGD (Stochastic Gradient Descent) updates the current position by taking a step in the direction of the latest noisy gradient.
  • SDA (Stochastic Dual Averaging) maintains a running average of all past gradients and maps that average back to a "primal" position.

In convex optimization, these two are essentially siblings with nearly identical performance guarantees. However, in the non-convex world (where most modern deep learning lives), SGD has a well-established theory, while SDA’s theory was surprisingly sparse. Previous attempts to prove SDA's convergence required restrictive assumptions, like assuming the algorithm's path stays within a pre-defined bounded area. This paper closes that gap, proving SDA works under standard, realistic conditions.

Methods

The researchers' "aha!" moment came from a clever mathematical reduction. They showed that SDA is actually equivalent to running SGD on a sequence of changing functions.

Specifically, they view SDA as SGD applied to a series of "implicitly regularized" objectives: $$f_t(x) = f(x) + \frac{\gamma_t}{2} \|x\|^2$$ where $\gamma_t$ is a regularization parameter that changes over time.

By analyzing how the objective function "shifts" at every step, the authors were able to derive a new "descent lemma." This allowed them to handle the fact that SDA weights all past gradients equally ($1/t$), whereas SGD gives much more weight to the most recent information.

They analyzed three main scenarios:

  1. Deterministic Step Sizes: Using a fixed schedule (roughly $1/\sqrt{t}$).
  2. High-Probability Bounds: Proving that the algorithm doesn't just work "on average," but will succeed in a single run with high confidence (assuming sub-Gaussian noise).
  3. Adaptive SDA (ADA-DA): A version that uses AdaGrad-style scaling to automatically adjust the step size based on the gradients it sees, removing the need for the user to know the exact noise variance ($\sigma$) or smoothness ($L$) of the function.

Datasets

The paper is purely theoretical and focuses on mathematical proofs of convergence. Consequently, no empirical datasets were used for training or evaluation.

Key Insights and Ideas

  • The Weighting Paradox: Nesterov (the father of DA) originally noted that standard subgradient descent makes newer information less important over time. SDA fixes this by giving "fresher" information equal weight, which is intuitively better for navigating the complex, "wiggly" landscapes of non-convex functions.
  • Iterate Independence: Unlike previous work, this proof does not assume the iterates stay within a bounded ball. It proves that the algorithm converges regardless of how far the iterates wander, as long as the function is smooth and bounded from below.
  • Strong Growth Condition (SGC): The authors use a more modern noise model (SGC) where the noise is allowed to grow as the iterates move further away, which is much more realistic for problems like least-squares or over-parameterized neural networks than the classic "bounded variance" assumption.

Key Results

  • Optimal Convergence: For a tuned step size, SDA achieves a convergence rate of $O(1/T + \sigma \log T / \sqrt{T})$. This matches the minimax-optimal rate of SGD.
  • Fast Rates in Low Noise: In the "noiseless" regime ($\sigma = 0$), the bound improves to $O(1/T)$, showing that SDA can take advantage of high-quality gradients.
  • ADA-DA Performance: The adaptive variant achieves the same $O(1/\sqrt{T})$ rate without requiring the user to tune hyperparameters based on unknown noise levels, provided the iterates remain bounded.

Limitations and Future Work

  • Heavy-Tailed Noise: The high-probability proofs rely on "sub-Gaussian" noise. However, recent research suggests that noise in large language models (like BERT) can be "heavy-tailed." The authors note that their current rates might not hold in those extreme cases.
  • The "Boundedness" Hurdle for Adaptivity: While the deterministic proof is "iterate-independent," the proof for the adaptive ADA-DA still requires an assumption that the iterates stay within some radius to guarantee the optimal rate. Removing this requirement for adaptive methods remains an open challenge.
  • Momentum: Most modern optimizers (like Adam) use momentum. A natural next step is extending this "implicitly regularized" analysis to DA variants that incorporate momentum-like moving averages.

Summary updated

Abstract

Dual averaging and gradient descent with their stochastic variants stand as the two canonical recipe books for first-order optimization: Every modern variant can be viewed as a descendant of one or the other. In the convex regime, these algorithms have been deeply studied, and we know that they are essentially equivalent in terms of theoretical guarantees. On the other hand, in the non-convex setting, the situation is drastically different: While we know that SGD can minimize the gradient of non-convex smooth functions, no finite-time complexity guarantee for Stochastic Dual Averaging (SDA) was known in the same setting. In this paper, we close this gap by a reduction that views SDA as SGD applied to a sequence of implicitly regularized objectives. We show that a tuned SDA exhibits a rate of convergence $\mathcal{O}(1 / T + σ\log T/ \sqrt{T})$, similar to that of SGD under the same assumptions. To our best knowledge, this is the first complete convergence theory for dual averaging on non-convex smooth stochastic problems without restrictive assumptions, closing a long-standing open problem in the field. Beyond the base algorithm, we also discuss ADA-DA, a variant that marries SDA with AdaGrad's auto-scaling, which achieves the same rate without requiring knowledge of the noise variance.
BibTeX
@inproceedings{liu2026dual,
  author = {Tuo Liu and El Mehdi Saad and Wojciech Kotłowski and Francesco Orabona},
  title = {{Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=mHyCz0KHOu},
}
Figure