A stochastic subgradient method with optimal failure exponent
Abstract
Fix a target accuracy ε, a gradient-noise level s, and a horizon N. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., ℰN = −log supf,P ℙP(f(xA) − f⋆ ≥ ε), with the noise law P known only to be sub-Gaussian. We single out a uniformly averaged schedule which is harmonic (of the form hk = R2/(ε (N+m−k))) and prove, via an optimized exponential supermartingale argument, that it attains the optimal exponent ℰN⋆ = ε2 N (1+o(1))/(2R2 s2). Optimality is certified by a matching impossibility result: under Gaussian noise, a gradient-masking change of measure caps the exponent of every algorithm at the same leading order. In a small-noise limit, our setting degenerates into the adversarial-error model of Gösgens and van Parys (2025) for subgradient methods.
Related
- The Last Iterate of the Projected Stochastic Subgradient Method Pays a Logarithm, Even in Dimension One
- Douglas-Rachford splitting method for nonconvex stochastic optimal control
- Nonminimizing Attractors of Stochastic Subgradient Methods on Semialgebraic Functions
- Iterative Method for Stochastic Optimal Control Problem Constrained by Parabolic Partial Differential Equation
- Optimal strong convergence of a splitting mixed finite element method for a stochastic Keller--Segel system
BibTeX
@misc{parys2026stochastic,
title = {{A stochastic subgradient method with optimal failure exponent}},
author = {Bart P. G. van Parys},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37425},
eprint = {2609.37425},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37425},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - A stochastic subgradient method with optimal failure exponent
AU - Bart P. G. van Parys
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37425
UR - https://arxiv.org/abs/2609.37425
AB - Fix a target accuracy ε, a gradient-noise level s, and a horizon N. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., ℰ_N = −log sup_f,P ℙ_P(f(x_A) − f_⋆ ≥ ε), with the noise law P known only to be sub-Gaussian. We single out a uniformly averaged schedule which is harmonic (of the form h_k = R^2/(ε (N+m−k))) and prove, via an optimized exponential supermartingale argument, that it attains the optimal exponent ℰ_N^⋆ = ε^2 N (1+o(1))/(2R^2 s^2). Optimality is certified by a matching impossibility result: under Gaussian noise, a gradient-masking change of measure caps the exponent of every algorithm at the same leading order. In a small-noise limit, our setting degenerates into the adversarial-error model of Gösgens and van Parys (2025) for subgradient methods.
ER -