arXiv preprint ·
Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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})$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Convergent Plug-and-Play Image Restoration with Annealed Noise Levels
Plug-and-Play Methods Provably Converge Even with Improperly Trained Denoisers: Convergence by Architectural Design
LocalProp: Neuro-Localized Memory-Efficient Backpropagation
ILP-BO: Integer Linear Programming-Based Black-Box Optimization
Optimal Reinsurance-Dividend Strategy with Fixed Transaction Costs in a Regime-Switching Brownian Risk Model: A Viscosity Solution to the Impulse Control Problem
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.