stat.MLFeb 13, 2026

AdaGrad-Diff: a Corrected Version of the Adaptive Gradient Algorithm for Composite Optimization

Authors: Matia Bojovic, Saverio Salzo, Massimiliano Pontil

Organizations: Computational Statistics and Machine Learning, Istituto Italiano di Tecnologia, Genoa, Italy · Department of Mathematics, University of Genoa, Genoa, Italy · DIAG, Sapienza University of Rome, Rome, Italy · Department of Computer Science, University College London, London, UK

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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)\mathcal O(n^{-1/2}) rate. Motivated by this limitation, we study AdaGrad-Diff, a block-wise extension of the UniSgd method considered by \cite{rodomanov2024universality}, 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−ν)/2n^{-(1-ν)/2}, thereby avoiding AdaGrad's failure mechanism and recovering the standard O(n−(1+ν)/2)\mathcal 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.

Figures & tables

Figure 1: AdaGrad and AdaGrad-Diff on the objective f(x)=∣x∣f(x)=\lvert{x}\rvert with 1515 iterations, x0=1x^{0}=1 and η=0.12\eta=0.12 .
Figure 2: Objective gap for ( 3 ) with p=8p=8 , c=0.1c=0.1 , x0=1x^{0}=1 , η=1\eta=1 .
Figure 3: Logistic regression with the news20.binary dataset: objective gap of AdaGrad-Diff and UniSgd along the optimization trajectory, with optimally tuned parameter η\eta .
Figure 4: Stepsize sensitivity and optimization performance across representative experiments. Columns correspond to LAD regression and logistic regression on splice , respectively. The first row shows sensitivity to η\eta in terms of final objective gap, while the second row reports the training objective gap along the optimization trajectory using optimally tuned η\eta .
Figure 5: Logistic regression with the splice dataset, for three choices of the stepsize parameter η\eta . The first row reports the objective gap, while the second row shows the corresponding effective stepsize dynamics.
Figure 6: Logistic regression on news20.binary . AdaGrad and AdaGrad-Diff are compared for batch sizes 512512 , 40964096 , and 1274812748 . The first row shows sensitivity to η\eta in terms of final objective gap, while the second row reports the training objective gap along the optimization trajectory using optimally tuned η\eta . The left column considers a fixed number of iterations, whereas the right column considers a fixed number of epochs.
More in this topic

Adaptive Gradient Methods

Adaptive Gradient Methods adjust updates using gradient history, curvature, or noise estimates to improve optimization across diverse problems.

See all 161 papers

Explore similar work

CardsList
Sep 26, 2026

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

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 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 high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight Ω(log⁡T/T)Ω(\log T/\sqrt T) lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that log⁡T\log T in existing average-iterate upper bounds is unavoidable. Finally, we show that this log⁡T\log T loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates O(1/T){O}(1/\sqrt{T}).

Weiming Ou, Xiao Wang

Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics

Convergence AnalysisAdaptive Gradient MethodsLast-Iterate Convergence
AskPDF
May 18, 2026

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad

Many tasks in modern machine learning are observed to involve heavy-tailed gradient noise during the optimization process. To manage this realistic and challenging setting, new mechanisms, such as gradient clipping and gradient normalization, have been introduced to ensure the convergence of first-order algorithms. However, adaptive gradient methods, a famous class of modern optimizers that includes popular Adam\mathtt{Adam} and AdamW\mathtt{AdamW}, often perform well even without any extra operations mentioned above. It is therefore natural to ask whether adaptive gradient methods can converge under heavy-tailed noise without any algorithmic changes. In this work, we take the first step toward answering this question by investigating a special case, AdaGrad\mathtt{AdaGrad}, the origin of adaptive gradient methods. We provide the first provable convergence rate for AdaGrad\mathtt{AdaGrad} in non-convex optimization when the tail index pp satisfies 4/3<p≤24/3<p\leq2. Notably, this result is achieved without requiring any prior knowledge of pp and is hence adaptive to the tail index. In addition, we develop an algorithm-dependent lower bound, suggesting that the existing minimax rate for heavy-tailed optimization is not attainable by AdaGrad\mathtt{AdaGrad}. Lastly, we consider AdaGrad-Norm\mathtt{AdaGrad}\text{-}\mathtt{Norm}, a popular variant of AdaGrad\mathtt{AdaGrad} in theoretical studies, and show an improved rate that holds for any 1<p≤21<p\leq2 under an extra mild assumption.

Zijian Liu

Stern School of Business, New York University

Stochastic OptimizationNonconvex Stochastic OptimizationHeavy-Tailed NoiseStochastic Optimization ConvergenceHeavy-Tailed DistributionsAdaptive Gradient Methods+1
AskPDF
Oct 29, 2026

Adaptive Federated Optimization Across Smooth and Nonsmooth Regimes

AdaGrad-style methods can simultaneously adapt to both the order and constants of smoothness in centralized optimization. However, existing extensions to federated optimization with heterogeneous client objectives and multiple local steps require the smoothness order to be specified in advance. We address this limitation with AdaFed, a federated method that adapts across several regimes under a single choice of parameters. In the deterministic setting, AdaFed achieves an O(1/T)O(1/T) convergence rate for both smooth nonconvex and smooth convex objectives, and an O(1/T)O(1/\sqrt{T}) rate for Lipschitz nonsmooth convex objectives up to logarithmic factors. Under a light-tailed stochastic-gradient noise assumption, these guarantees extend to the stochastic setting with additional logarithmic factors and noise-dependent terms. Experiments across the three problem classes further support our theoretical findings.

Zimeng Wang, Ali Dadras, Alp Yurtsever

Department of Mathematics and Mathematical Statistics, Ume˚a University, Sweden

Federated LearningAdaptive Gradient MethodsStochastic Optimization ConvergenceNonsmooth Convex OptimizationNonconvex Stochastic Optimization
AskPDF