SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance

Amit Attia, Tomer Koren
2/17/2023
cs.LGmath.OCstat.ML

No confident code implementation found for this paper.

Abstract

We study Stochastic Gradient Descent with AdaGrad stepsizes: a popular adaptive (self-tuning) method for first-order stochastic optimization. Despite being well studied, existing analyses of this method suffer from various shortcomings: they either assume some knowledge of the problem parameters, impose strong global Lipschitz conditions, or fail to give bounds that hold with high probability. We provide a comprehensive analysis of this basic method without any of these limitations, in both the convex and non-convex (smooth) cases, that additionally supports a general ``affine variance'' noise model and provides sharp rates of convergence in both the low-noise and high-noise~regimes.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Adaptive Step Sizes for Preconditioned Stochastic Gradient Descent

86% match2023

Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

86% match2023

SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration

85% match2025

Stochastic Adaptive Gradient Descent Without Descent

85% match2025

AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size

84% match2024

Revisiting Convergence of AdaGrad with Relaxed Assumptions

83% match2024

Cite this paper

@article{attia2023with,
  title  = {SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance},
  author = {Amit Attia and Tomer Koren},
  year   = {2023},
  eprint = {2302.08783},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2302.08783v2},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2302.08783.svg)](https://codeofpaper.com/paper/2302.08783)

Discussion