Preprint

On the Iterate Convergence of AdaGrad for Generalized Smooth Convex Optimization

Mathieu Besançon Tung Le

Aug 2026 · 0 citations

Mathematics

TL;DR

This work constructs a counterexample empirically showing that smoothness alone is not sufficient for the sequential convergence of AdaGrad-type algorithms, and suggesting that additional geometric hypotheses are indispensable for sequential convergence results.

Abstract

We prove sequential convergence results for the AdaGrad algorithm family optimizing convex differentiable objectives. Specifically, we provide necessary and sufficient conditions for the convergence of iterates for the three main AdaGrad variants (AdaNorm, AdaDiag, AdaFull) when the objective is convex and locally Lipschitz-smooth, closing the question left open from the literature. We harness this general result to study the three variants under the generalized $(L_0,L_1)$-smoothness condition and show sequential convergence for sufficiently small constant step size. Moreover, under the so-called $(L_0,L_1)$-polynomially modifiable smoothness assumption, which is a relaxation of the $(L_0,L_1)$ generalized smoothness property and is satisfied by many function classes such as $L$-smooth functions or univariate polynomials, sequential convergence for these AdaGrad variants is proved for arbitrary learning rates. This result provides conditions under which AdaGrad presents adaptivity, i.e., does not require tuning the parameters based on the instance. Finally, we provide numerical illustrations of the behavior of AdaGrad on convex and nonconvex functions. In particular, we construct a counterexample empirically showing that smoothness alone is not sufficient for the sequential convergence of AdaGrad-type algorithms, and suggesting that additional geometric hypotheses (e.g., convexity as in this paper, or the Kurdyka-\L ojasiewicz inequality) are indispensable for sequential convergence results.

arXiv Semantic Scholar

View source

Similar papers

Preprint Sep 2026

Optimal Gradient-Norm Minimization in Non-Euclidean H\"older-Smooth Convex Optimization

Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study grad...

Nico Pelleriti, Maryam Shiran, David Martínez-Rubio et al. · 0 citations

Preprint Jul 2026

Parameter-Free Cubic-Regularized Newton Method: Sharp Complexity and Generalized Smoothness

A variant of the cubic-regularized Newton method for nonconvex optimization that is parameter-free in that it requires no prior knowledge of problem-dependent parameters is analyzed, and an oracle complexity bound is derived for finding an $(varepsilon, \delta)-second-order stationary point.

Shaoying Fang, Naoki Marumo, Akiko Takeda · 1 citation

Jul 2026

Entropy-Smooth Convex Optimization Cannot Be Accelerated

We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a lo...

Jacob M. Aguirre, Dmitrii M. Ostrovskii · arXiv.org · 0 citations

Preprint Aug 2026

A lower bound for stepsize-based acceleration of gradient descent

This work presents a new lower bound of $\Omega(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules, and provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate.

Jian-Hao Ma, Yu-Xin Chen · 8 citations · ⚡2

Preprint Jul 2026

Sharp Dimension Dependence for the Last Iterate of the SubGradient Method

We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ f...

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni et al. · 1 citation · ⚡1

Preprint Aug 2026

On the Iterate Convergence of Bregman Projected Gradient Method

A novel convergence analysis framework for the BPGM with the Shannon entropy kernel is developed, yielding strong convergence results for a broad class of objective functions under linear constraints.

He Chen, Anthony Man-Cho So · 1 citation