High Probability Convergence of Stochastic Gradient Methods
This work provides stronger theoretical guarantees for stochastic optimization algorithms, which is important for machine learning practitioners seeking reliable convergence bounds, though it is incremental in extending existing methods.
The paper tackles the problem of proving high probability convergence for stochastic gradient methods in both convex and non-convex optimization with sub-Gaussian noise, achieving improved convergence rates such as O((1+σ²log(1/δ))/T+σ/√T) for known T and O((1+σ²log(T/δ))/√T) for unknown T, and extends these techniques to AdaGrad algorithms.
In this work, we describe a generic approach to show convergence with high probability for both stochastic convex and non-convex optimization with sub-Gaussian noise. In previous works for convex optimization, either the convergence is only in expectation or the bound depends on the diameter of the domain. Instead, we show high probability convergence with bounds depending on the initial distance to the optimal solution. The algorithms use step sizes analogous to the standard settings and are universal to Lipschitz functions, smooth functions, and their linear combinations. This method can be applied to the non-convex case. We demonstrate an $O((1+σ^{2}\log(1/δ))/T+σ/\sqrt{T})$ convergence rate when the number of iterations $T$ is known and an $O((1+σ^{2}\log(T/δ))/\sqrt{T})$ convergence rate when $T$ is unknown for SGD, where $1-δ$ is the desired success probability. These bounds improve over existing bounds in the literature. Additionally, we demonstrate that our techniques can be used to obtain high probability bound for AdaGrad-Norm (Ward et al., 2019) that removes the bounded gradients assumption from previous works. Furthermore, our technique for AdaGrad-Norm extends to the standard per-coordinate AdaGrad algorithm (Duchi et al., 2011), providing the first noise-adapted high probability convergence for AdaGrad.