{"id":"arxiv/2609.37425","url":"https://arxiv.org/abs/2609.37425","tags":["math.OC","stat.ML"],"score":0,"title":"A stochastic subgradient method with optimal failure exponent","domain":"math.OC","source":"arxiv","authors":["Bart P. G. van Parys"],"reviews":0,"subject":"math.OC","summary":"Fix a target accuracy $\\varepsilon$, 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., $\\mathcal{E}_N = -\\log \\sup_{f,P} \\mathbb{P}_P(f(x_A) - f_\\star \\ge \\varepsilon)$, 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/(\\varepsilon (N+m-k))$) and prove, via an optimized exponential supermartingale argument, that it attains the optimal exponent $\\mathcal{E}_N^\\star =…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}