Cover Image

Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Crawshaw, Michael, Liu, Mingrui
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
by: Gong, Xiaochuan, et al.
Published: (2024)

A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness
by: Gong, Xiaochuan, et al.
Published: (2024)

On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness
by: Gong, Xiaochuan, et al.
Published: (2025)

Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
by: Gong, Xiaochuan, et al.
Published: (2025)

Decentralized Stochastic Nonconvex Optimization under the Relaxed Smoothness
by: Luo, Luo, et al.
Published: (2025)

Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis
by: Hao, Jie, et al.
Published: (2024)

Non-Euclidean Gradient Descent Operates at the Edge of Stability
by: Islamov, Rustem, et al.
Published: (2026)

High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
by: Gorbunov, Eduard, et al.
Published: (2021)

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
by: Kovalev, Dmitry
Published: (2026)

A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems
by: Curtis, Frank E., et al.
Published: (2023)

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
by: Kovalev, Dmitry, et al.
Published: (2024)

A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness
by: Sun, Zhenyu, et al.
Published: (2024)

Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
by: Wu, Yuman, et al.
Published: (2026)

Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization
by: Yang, Yufeng, et al.
Published: (2024)

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
by: Jiang, Ruichen, et al.
Published: (2024)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
by: Saad, El Mehdi, et al.
Published: (2025)

Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
by: Cutkosky, Ashok, et al.
Published: (2023)

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
by: Kovalev, Dmitry, et al.
Published: (2024)

On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions
by: Hong, Yusu, et al.
Published: (2024)

Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization
by: Chen, Lesi, et al.
Published: (2025)

Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance
by: Chen, Hongxu, et al.
Published: (2026)

Non-convex Stochastic Composite Optimization with Polyak Momentum
by: Gao, Yuan, et al.
Published: (2024)

Explicit and Non-asymptotic Query Complexities of Rank-Based Zeroth-order Algorithm on Stochastic Smooth Functions
by: Ye, Haishan
Published: (2025)

Provable Adaptivity of Adam under Non-uniform Smoothness
by: Wang, Bohan, et al.
Published: (2022)

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
by: Bai, Cedar Site, et al.
Published: (2024)

Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness
by: Zhao, Yuheng, et al.
Published: (2025)

Adaptive Federated Minimax Optimization with Lower Complexities
by: Huang, Feihu, et al.
Published: (2022)

On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Łojasiewicz Condition
by: Bai, Yunyan, et al.
Published: (2024)

The Sample Complexity of Gradient Descent in Stochastic Convex Optimization
by: Livni, Roi
Published: (2024)

Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization
by: Sato, Naoki, et al.
Published: (2023)

Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent
by: Kou, Yiwen, et al.
Published: (2024)

Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints
by: Huang, Ruichuan, et al.
Published: (2025)

Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization
by: Chen, Lesi, et al.
Published: (2023)

Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms
by: Gu, Bin, et al.
Published: (2024)

Directional Smoothness and Gradient Methods: Convergence and Adaptivity
by: Mishkin, Aaron, et al.
Published: (2024)

Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression
by: He, Yutong, et al.
Published: (2023)

A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints
by: Wang, Lei, et al.
Published: (2022)

Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimization
by: Shen, Wei, et al.
Published: (2023)

An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes
by: Orvieto, Antonio, et al.
Published: (2024)

GeoAdaLer: Geometric Insights into Adaptive Stochastic Gradient Descent Algorithms
by: Eleh, Chinedu, et al.
Published: (2024)