{"ID":2856502,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.11676","arxiv_id":"2510.11676","title":"Accelerated stochastic first-order method for convex optimization under heavy-tailed noise","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.","short_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 ad...","url_abs":"https://arxiv.org/abs/2510.11676","url_pdf":"https://arxiv.org/pdf/2510.11676v1","authors":"[\"Chuan He\",\"Zhaosong Lu\"]","published":"2025-10-13T17:45:05Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.AI\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}