Accelerated stochastic first-order method for convex optimization under heavy-tailed noise

2025/10/13 by He, Chuan, Lu, Zhaosong · 1 citation
#49M05 #49M37 #90C25 #90C30 #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2510.11676

Abstract

We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. In this paper, we demonstrate that a vanilla stochastic algorithm -- without additional modifications such as clipping or normalization -- can achieve optimal complexity for these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Numerical experiments are further provided to validate our theoretical results.

Citations

• Universal Complexity Bounds for Universal Gradient Methods in Nonlinear Optimization
• Can SGD Handle Heavy-Tailed Noise?
• Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise
• Towards Weaker Variance Assumptions for Stochastic Optimization
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping
• Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration
• From Gradient Clipping to Normalization for Heavy Tailed SGD
• Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimization
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance
• On Optimal Universal First-Order Methods for Minimizing Heterogeneous Sums
• A single cut proximal bundle method for stochastic convex composite optimization
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• Optimization Methods for Large-Scale Machine Learning
• Optimization Methods for Large-Scale Machine Learning
• Generalized Uniformly Optimal Methods for Nonlinear Programming
• Acceleration of Stochastic Approximation by Averaging
• A Stochastic Approximation Method

Cited by

• Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Mean

Related

• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
• Stochastic smoothing accelerated gradient method for general constrained nonsmooth convex composite optimization
• Gradient-Free Methods for Non-Smooth Convex Stochastic Optimization with Heavy-Tailed Noise on Convex Compact