A stochastic subgradient method with optimal failure exponent
van Parys et al.
Averaged subgradient descent attains the sharp large-deviation exponent under sub-Gaussian noise, and a matching lower bound shows the constant is optimal.
In the Daily Brief of 11 October 2026
The paper asks how fast the probability of failure can decay for stochastic subgradient methods when the gradient noise is sub-Gaussian.
It shows that averaged subgradient descent with a harmonic step schedule has a failure probability that decays like \(\exp\bigl(-(1+o(1))\,\varepsilon^2 N/(2R^2 s^2)\bigr)\), where \(s\) is the noise level. A matching lower bound for Gaussian noise shows that the leading constant cannot be improved.
It is a sharp large-deviation result for stochastic optimisation: not only the rate but the exact constant in the exponent is identified.