Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

arXiv:2609.32729v1 Announce Type: cross Abstract: AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal extbf{last-iterate} rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield extbf{high-probability average-iterate} rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Omega(log T/sqrt T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates {O}(1/sqrt{T}).

Source: arXiv cs.LG | 2026-09-29