AdaGrad-Diff: a Corrected Version of the Adaptive Gradient Algorithm for Composite Optimization
stat.ML, cs.LG, math.OC
Submitted: 2026-02-13
Updated: 2026-10-29
Comments: 35 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: Vanilla gradient methods are often highly sensitive to the choice of stepsize, which typically requires manual tuning.
Terminology
Abstract
Vanilla gradient methods are often highly sensitive to the choice of stepsize, which typically requires manual tuning. Adaptive methods alleviate this issue, with AdaGrad being a prominent example. In this work, we first show that, in composite convex optimization, AdaGrad may fail to exploit the Hölder-smoothness of the differentiable term, as its stepsizes may decrease too rapidly, leading to convergence rates arbitrarily close to the nonsmooth O(n-1/2) rate. Motivated by this limitation, we study AdaGrad-Diff, a block-wise extension of the UniSgd method considered by, which accumulates successive gradient differences rather than gradients themselves. In the deterministic Lipschitz-smooth setting, we prove summability of squared gradient differences without assuming bounded iterates, yielding weak convergence to a minimizer in Hilbert spaces. Moreover, we show that, under ν-Hölder-smoothness, stepsizes decay no faster than n-(1-ν)/2, thereby avoiding AdaGrad's failure mechanism and recovering the standard O(n-(1+ν)/2) rate. The same approach recovers known stochastic convergence rates under a unified condition covering bounded variance and interpolation. Numerical experiments demonstrate that the proposed method is more robust than AdaGrad in several practically relevant settings.
Sources
- A Simple Convergence Proof of Adam and Adagrad
- On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration
- Less Regret via Online Conditioning
- ADADELTA: An Adaptive Learning Rate Method
Related papers
- Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks
- Diffusion Models Observe Only Gradients: A Geometric Perspective on Score Matching Errors
- Quantifying Error Propagation and Model Collapse in Diffusion Models
- Behavior of prediction performance metrics with rare events
- Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
- Control Variate Design for Score-Function Gradient Estimators in Importance-Weighted Variational Inference