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
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 \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−ν)/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.
Figures & tables
Figure 1: AdaGrad and AdaGrad-Diff on the objective f(x)=∣x∣ with 15 iterations, x0=1 and η=0.12 .
Figure 2: Objective gap for ( 3 ) with p=8 , c=0.1 , x0=1 , η=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 η .
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 η in terms of final objective gap, while the second row reports the training objective gap along the optimization trajectory using optimally tuned η .
Figure 5: Logistic regression with the splice dataset, for three choices of the stepsize parameter η . 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 512 , 4096 , and 12748 . The first row shows sensitivity to η in terms of final objective gap, while the second row reports the training objective gap along the optimization trajectory using optimally tuned η . The left column considers a fixed number of iterations, whereas the right column considers a fixed number of epochs.
Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics