Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
Abstract
We develop an accelerated stochastic method for convex (H0,H1)-smooth optimization under heavy-tailed noise. The unbiased oracle has a finite p-th noise moment, 1<p≤2, with constant, gradient-dependent, and gap-dependent terms. Our method combines accelerated updates with clipping, projection, and phase restarts. Each iteration uses a single stochastic-gradient sample, without minibatching. We prove high-probability convergence to any desired accuracy despite clipping bias. The deterministic terms retain square-root dependence on both H0 and H1. In our three-component noise model, strong convexity leaves a polynomial accuracy cost only for the constant component; without it, the dependence is logarithmic even for p<2. More generally, for noise moments scaling as (f(x)−f⋆)α, the stochastic cost becomes logarithmic at α=p for convex objectives and α=p/2 under strong convexity.
Related
- Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
- TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise
- Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information
- The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
- Safety stock calculation with heteroscedastic, autocorrelated and heavy-tailed forecast errors, an adaptive parametric method.e
BibTeX
@misc{lobanov2026accelerated,
title = {{Accelerated Stochastic Method under $(H_0,H_1)$-Smoothness and Heavy-Tailed Noise}},
author = {Aleksandr Lobanov and Darina Dvinskikh and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33415},
eprint = {2609.33415},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33415},
}
RIS
TY - UNPB
TI - Accelerated Stochastic Method under (H_0,H_1)-Smoothness and Heavy-Tailed Noise
AU - Aleksandr Lobanov
AU - Darina Dvinskikh
AU - Alexander Gasnikov
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33415
UR - https://arxiv.org/abs/2609.33415
AB - We develop an accelerated stochastic method for convex (H_0,H_1)-smooth optimization under heavy-tailed noise. The unbiased oracle has a finite p-th noise moment, 1<p≤2, with constant, gradient-dependent, and gap-dependent terms. Our method combines accelerated updates with clipping, projection, and phase restarts. Each iteration uses a single stochastic-gradient sample, without minibatching. We prove high-probability convergence to any desired accuracy despite clipping bias. The deterministic terms retain square-root dependence on both H_0 and H_1. In our three-component noise model, strong convexity leaves a polynomial accuracy cost only for the constant component; without it, the dependence is logarithmic even for p<2. More generally, for noise moments scaling as (f(x)−f^⋆)^α, the stochastic cost becomes logarithmic at α=p for convex objectives and α=p/2 under strong convexity.
ER -