Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness
Abstract
We study stochastic convex optimization under asymmetric (L0,L1)-generalized smoothness, a model motivated by machine-learning objectives whose local curvature may grow with the gradient norm. We assume an unbiased first-order oracle with additive norm-sub-Gaussian noise. Acceleration is difficult in this setting because momentum may enter regions of much larger curvature, while stochastic gradients cannot reliably certify an unrestricted trajectory. We propose \textsf{ARC-SG}, a two-phase accelerated method: Phase~I reduces excessively large gradients using a generalized-smoothness-aware stochastic step, then Phase~II solves strongly convex proximal subproblems by a restarted accelerated solver confined to certified smoothness balls. Exact proximal points do not increase the gradient norm, allowing these certificates to propagate through the outer loop. The contribution is a query-by-query certified-localization construction with explicit generalized-smoothness factors and a strongly convex restart extension. \textsf{ARC-SG} achieves, with high probability, an accelerated optimization contribution and smooth-subclass-optimal statistical dependence on accuracy, up to logarithmic and generalized-smoothness factors. Its convex accuracy exponents agree with a contemporaneous public stochastic-acceleration result under a broader smoothness and affine-variance model; our distinction is the certified geometry, explicit parameter accounting, and strongly convex guarantee. The results recover classical accelerated stochastic rates when L1=0. Experiments on objectives with unbounded gradients illustrate the two-phase mechanism and its finite-budget advantage.
Related
- The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization
- First-order Optimization Methods with Generalized Smoothness for Low-rank Matrix Factorization
- Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
- Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
- Acceleration Survives Heavy Tails and Generalized Smoothness
BibTeX
@misc{dvinskikh2026localize,
title = {{Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness}},
author = {Darina Dvinskikh and Alexander Gasnikov and Aleksandr Lobanov and Ilgam Latypov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06555},
eprint = {2609.06555},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06555},
}
RIS
TY - UNPB
TI - Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness
AU - Darina Dvinskikh
AU - Alexander Gasnikov
AU - Aleksandr Lobanov
AU - Ilgam Latypov
PY - 2026
DA - 2026/09/06
PB - arXiv
DO - 10.48550/arxiv.2609.06555
UR - https://arxiv.org/abs/2609.06555
AB - We study stochastic convex optimization under asymmetric (L_0,L_1)-generalized smoothness, a model motivated by machine-learning objectives whose local curvature may grow with the gradient norm. We assume an unbiased first-order oracle with additive norm-sub-Gaussian noise. Acceleration is difficult in this setting because momentum may enter regions of much larger curvature, while stochastic gradients cannot reliably certify an unrestricted trajectory. We propose \textsf{ARC-SG}, a two-phase accelerated method: Phase~I reduces excessively large gradients using a generalized-smoothness-aware stochastic step, then Phase~II solves strongly convex proximal subproblems by a restarted accelerated solver confined to certified smoothness balls. Exact proximal points do not increase the gradient norm, allowing these certificates to propagate through the outer loop. The contribution is a query-by-query certified-localization construction with explicit generalized-smoothness factors and a strongly convex restart extension. \textsf{ARC-SG} achieves, with high probability, an accelerated optimization contribution and smooth-subclass-optimal statistical dependence on accuracy, up to logarithmic and generalized-smoothness factors. Its convex accuracy exponents agree with a contemporaneous public stochastic-acceleration result under a broader smoothness and affine-variance model; our distinction is the certified geometry, explicit parameter accounting, and strongly convex guarantee. The results recover classical accelerated stochastic rates when L_1=0. Experiments on objectives with unbounded gradients illustrate the two-phase mechanism and its finite-budget advantage.
ER -