Image de couverture de livre

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Jiang, Ruichen, Maladkar, Devyani, Mokhtari, Aryan
Format:	Preprint
Publié:	2024
Sujets:	Optimization and Control Machine Learning
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

AdaGrad under Anisotropic Smoothness
par: Liu, Yuxing, et autres
Publié: (2024)

Revisiting Convergence of AdaGrad with Relaxed Assumptions
par: Hong, Yusu, et autres
Publié: (2024)

Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence
par: Jiang, Ruichen, et autres
Publié: (2024)

AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates
par: Zhang, Minxin, et autres
Publié: (2025)

Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
par: Jiang, Ruichen, et autres
Publié: (2024)

Stochastic Newton Proximal Extragradient Method
par: Jiang, Ruichen, et autres
Publié: (2024)

An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization
par: Cao, Jincheng, et autres
Publié: (2024)

AdaGrad-Diff: A New Version of the Adaptive Gradient Algorithm
par: Bojovic, Matia, et autres
Publié: (2026)

Last Iterate Convergence of AdaGrad-Norm for Convex Non-Smooth Optimization
par: Preobrazhenskaia, Margarita, et autres
Publié: (2026)

Modeling AdaGrad, RMSProp, and Adam with Integro-Differential Equations
par: Heredia, Carlos
Publié: (2024)

Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism
par: Patitucci, Francisco, et autres
Publié: (2025)

On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
par: Cao, Jincheng, et autres
Publié: (2025)

Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed
par: Chezhegov, Savelii, et autres
Publié: (2024)

Generalized Optimistic Methods for Convex-Concave Saddle Point Problems
par: Jiang, Ruichen, et autres
Publié: (2022)

Online Learning-guided Learning Rate Adaptation via Gradient Alignment
par: Jiang, Ruichen, et autres
Publié: (2025)

Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization
par: Jiang, Ruichen, et autres
Publié: (2026)

Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction
par: Rodomanov, Anton, et autres
Publié: (2024)

Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad
par: Choudhury, Sayantan, et autres
Publié: (2024)

Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad
par: Liu, Zijian
Publié: (2026)

Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization
par: Jiang, Ruichen, et autres
Publié: (2024)

A Riemannian AdaGrad-Norm Method
par: Bento, Glaydston de C., et autres
Publié: (2025)

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance
par: Fazla, Arda, et autres
Publié: (2026)

On the Provable Suboptimality of Momentum SGD in Nonstationary Stochastic Optimization
par: Sahu, Sharan, et autres
Publié: (2026)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
par: Saad, El Mehdi, et autres
Publié: (2025)

SLowcal-SGD: Slow Query Points Improve Local-SGD for Stochastic Convex Optimization
par: Dahan, Tehila, et autres
Publié: (2023)

Adaptive Optimization via Momentum on Variance-Normalized Gradients
par: Patitucci, Francisco, et autres
Publié: (2026)

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
par: Kovalev, Dmitry, et autres
Publié: (2024)

Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate
par: Jiang, Ruichen, et autres
Publié: (2024)

Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
par: Crawshaw, Michael, et autres
Publié: (2025)

Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
par: Ji, Kaiyi
Publié: (2025)

Non-asymptotic Global Convergence Rates of BFGS with Exact Line Search
par: Jin, Qiujiang, et autres
Publié: (2024)

Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search
par: Jin, Qiujiang, et autres
Publié: (2024)

Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization
par: Armacki, Aleksandar, et autres
Publié: (2026)

The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
par: Livni, Roi
Publié: (2024)

The Sample Complexity of Parameter-Free Stochastic Convex Optimization
par: Lawrence, Jared, et autres
Publié: (2025)

Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
par: Chae, Jiseok, et autres
Publié: (2024)

Online Non-Stationary Stochastic Quasar-Convex Optimization
par: Pun, Yuen-Man, et autres
Publié: (2024)

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
par: Kovalev, Dmitry
Publié: (2026)

AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methods
par: Lau, Tim Tsz-Kit, et autres
Publié: (2024)

AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size
par: Ostroukhov, Petr, et autres
Publié: (2024)