Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization

Tuo Liu, El Mehdi Saad, Wojciech Kotlowski, Francesco Orabona
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3682-3690, 2026.

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 the two classes are essentially equivalent in terms of theoretical guarantees. On the other hand, in the non-convex setting, the situation is drastically different: While it is provable that SGD can minimize the gradient norm 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 + \sigma \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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-liu26d, title = { Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization }, author = {Liu, Tuo and Saad, El Mehdi and Kotlowski, Wojciech and Orabona, Francesco}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3682--3690}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/liu26d/liu26d.pdf}, url = {https://proceedings.mlr.press/v300/liu26d.html}, 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 the two classes are essentially equivalent in terms of theoretical guarantees. On the other hand, in the non-convex setting, the situation is drastically different: While it is provable that SGD can minimize the gradient norm 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 + \sigma \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. } }
Endnote
%0 Conference Paper %T Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization %A Tuo Liu %A El Mehdi Saad %A Wojciech Kotlowski %A Francesco Orabona %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-liu26d %I PMLR %P 3682--3690 %U https://proceedings.mlr.press/v300/liu26d.html %V 300 %X 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 the two classes are essentially equivalent in terms of theoretical guarantees. On the other hand, in the non-convex setting, the situation is drastically different: While it is provable that SGD can minimize the gradient norm 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 + \sigma \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.
APA
Liu, T., Saad, E.M., Kotlowski, W. & Orabona, F.. (2026). Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3682-3690 Available from https://proceedings.mlr.press/v300/liu26d.html.

Related Material