Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization

2025/05/27 by Tuo Liu, El Mehdi Saad, Liu, Tuo +5
Decision Sciences · Economics, Econometrics and Finance · #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic processes and financial applications

paper · pdf · doi:10.48550/arxiv.2505.21394

openalex publication_date 2025/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(1 / T + σlog T/ √(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.

Citations

• High Probability Convergence of Stochastic Gradient Methods
• Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization
• Online Learning: A Modern Introduction Using Convex Optimization
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise
• Online Non-Convex Learning: Following the Perturbed Leader is Optimal
• Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• Optimization Methods for Large-Scale Machine Learning
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• Less Regret via Online Conditioning
• Primal-dual subgradient methods for convex problems

Related

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• Extended Regularized Dual Averaging Methods for Stochastic Optimization
• Lp and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective
• Making Gradient Descent Optimal for Strongly Convex Stochastic\n Optimization
• High Probability Convergence of Stochastic Gradient Methods