Revisiting Convergence of AdaGrad with Relaxed Assumptions
Yusu Hong Junhong Lin
In this study, we revisit the convergence of AdaGrad with momentum (covering
AdaGrad as a special case) on non-convex smooth optimization problems. We
consider a general noise model where the noise magnitude is controlled by the
function value gap together with the gradient magnitude. This model encompasses
a broad range of noises including bounded noise, sub-Gaussian noise, affine
variance noise and the expected smoothness, and it has been shown to be more
realistic in many practical applications. Our analysis yields a probabilistic
convergence rate which, under the general noise, could reach at
(\tilde{\mathcal{O}}(1/\sqrt{T})). This rate does not rely on prior knowledge
of problem-parameters and could accelerate to (\tilde{\mathcal{O}}(1/T)) where
(T) denotes the total number iterations, when the noise parameters related to
the function value gap and noise level are sufficiently small. The convergence
rate thus matches the lower rate for stochastic first-order methods over
non-convex smooth landscape up to logarithm terms [Arjevani et al., 2023]. We
further derive a convergence bound for AdaGrad with mometum, considering the
generalized smoothness where the local smoothness is controlled by a
first-order function of the gradient norm.