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

• URL: http://arxiv.org/abs/2605.18694v1
• Date: Mon, 18 May 2026 17:30:15 GMT
• Title: Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad
• Abstract summary: We show that adaptive gradient methods can converge undertailed noise without any algorithmic changes.<n>We also show that the existing minimax rate for heavy-tailed optimization is not attainable by $mathttAdaGrad$, suggesting that the existing minimax rate is not attainable by $mathttAdaGrad$.
• Score: 3.8357180714081327
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\mathtt{Adam}$ and $\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, $\mathtt{AdaGrad}$, the origin of adaptive gradient methods. We provide the first provable convergence rate for $\mathtt{AdaGrad}$ in non-convex optimization when the tail index $p$ satisfies $4/3<p\leq2$. Notably, this result is achieved without requiring any prior knowledge of $p$ 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 $\mathtt{AdaGrad}$. Lastly, we consider $\mathtt{AdaGrad}\text{-}\mathtt{Norm}$, a popular variant of $\mathtt{AdaGrad}$ in theoretical studies, and show an improved rate that holds for any $1<p\leq2$ under an extra mild assumption.

Related papers

• Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications [7.195047020440563]
  In Online Convex Optimization (OCO), when the gradient has a finite variance, many algorithms provably guarantee a sublinear regret.<n>This work examines different old algorithms for OCO in the more challenging heavy-tailed setting.<n>Remarkably, these regret bounds are fully optimal in all parameters.
  arXiv  Detail & Related papers  (2025-08-10T20:17:38Z)
• $k$-SVD with Gradient Descent [18.260910876411973]
  We provide a gradient-descent method with a simple, universal rule for step-size selection that provably finds $k$-SVD for a matrix of any rank $d geq 1$.<n>Our convergence analysis reveals that the gradient method has an attractive region, and within this attractive region, the method behaves like Heron's method (a.k.a. the Babylonian method)<n>Our analytic results imply that the gradient method can be enhanced by means of Nesterov's momentum-based acceleration technique.
  arXiv  Detail & Related papers  (2025-02-01T05:00:28Z)
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
  We provide the first convergence under heavy-tailed noises but without clipping.<n>We also establish first $mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$ convergence rate in the case where the tail index $mathfrakp$ is unknown in advance.
  arXiv  Detail & Related papers  (2024-12-27T08:46:46Z)
• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  We focus on the class of (strongly) convex $(L0)$-smooth functions and derive new convergence guarantees for several existing methods.<n>In particular, we derive improved convergence rates for Gradient Descent with smoothnessed Gradient Clipping and for Gradient Descent with Polyak Stepsizes.
  arXiv  Detail & Related papers  (2024-09-23T13:11:37Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  Adaptive gradient methods are among the most successful neural network training algorithms.<n>These methods are known to achieve better dimensional dependence than over convex SGD-normarity.<n>In this paper we introduce new assumptions on the smoothness of the structure and the gradient noise variance.
  arXiv  Detail & Related papers  (2024-06-07T02:55:57Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth. We consider two kinds of zero-order projected gradient descent algorithms.
  arXiv  Detail & Related papers  (2023-06-03T17:05:13Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity. We proposed a method to solve problems master to agents' communication and local calls. The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
  arXiv  Detail & Related papers  (2022-05-30T14:28:02Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  We consider the problem of finding a saddle point for the convex-concave objective $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vu algorithm, which alternates between primal gradient steps and dual steps.
  arXiv  Detail & Related papers  (2021-10-28T14:19:30Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.