Convergence Analysis of Stochastic Accelerated Gradient Methods for Generalized Smooth Optimizations

Abstract

We investigate the Randomized Stochastic Accelerated Gradient (RSAG) method, utilizing either constant or adaptive step sizes, for stochastic optimization problems with generalized smooth objective functions. Under relaxed affine variance assumptions for the stochastic gradient noise, we establish high-probability convergence rates of order $\tilde{O}\left(\sqrt{\log (1/\hat{I}´)/T}\right)$ for function value gaps in the convex setting, and for the squared gradient norms in the non-convex setting. Furthermore, when the noise parameters are sufficiently small, the convergence rate improves to $\tilde{O}\left(\log (1/\hat{I}´)/T\right)$, where $T$ denotes the total number of iterations and $\hat{I}´$ is the probability margin. Our analysis is also applicable to SGD with both constant and adaptive step sizes.

64 pages