AdaGrad adaptive methods face limits in stochastic optimization rates
Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
Machine Learning
Summary
AdaGrad is a popular tool used to improve learning from noisy data. This work shows that two versions of AdaGrad do not always get closer to the best answer when looking only at the final step, even in nice conditions. The authors prove that just limiting noise isn't enough to guarantee good results most of the time. They also found that a logarithmic factor slowing down progress is unavoidable unless certain restrictions hold. When these restrictions are met, AdaGrad can achieve better speed in finding optimal solutions.
What this means in practice
- •For machine learning engineers: Design optimization algorithms with realistic expectations on convergence speed and conditions when using AdaGrad variants in noisy data settings.
- •For statistical data scientists: Understand the limits of adaptive methods like AdaGrad for reliable parameter estimation under varying noise and bounded conditions.
A theory result. No direct application yet.
Authors
Weiming Ou, Xiao Wang
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 \textbf{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 \textbf{high-probability average-iterate} rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight $Ω(\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})$.