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

arXiv: https://arxiv.org/abs/2505.04599 · HTML: https://mlsanity.com/paper/2505.04599/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2025.

## Built on by (most cited first, 4 of 4)

- [Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad](https://mlsanity.com/paper/2605.18694/) (2026)
- [When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds](https://mlsanity.com/paper/2605.06615/) (2026)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (2025)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)

## Abstract (arXiv)

Recent results in non-convex stochastic optimization demonstrate the convergence of popular adaptive algorithms (e.g., AdaGrad) under the (L0, L1)-smoothness condition, but the rate of convergence is a higher-order polynomial in terms of problem parameters like the smoothness constants. The complexity guaranteed by such algorithms to find an ε-stationary point may be significantly larger than the optimal complexity of Theta left( Delta L σ2 ε-4 right) achieved by SGD in the L-smooth setting, where Delta is the initial optimality gap, σ2 is the variance of stochastic gradient. However, it is currently not known whether these higher-order dependencies can be tightened. To answer this question, we investigate complexity lower bounds for several adaptive optimization algorithms in the (L0, L1)-smooth setting, with a focus on the dependence in terms of problem parameters Delta, L0, L1. We provide complexity bounds for three variations of AdaGrad, which show at least a quadratic dependence on problem parameters Delta, L0, L1. Notably, we show that the decorrelated variant of AdaGrad-Norm requires at least Omega left( Delta2 L12 σ2 ε-4 right) stochastic gradient queries to find an ε-stationary point. We also provide a lower bound for SGD with a broad class of adaptive stepsizes. Our results show that, for certain adaptive algorithms, the (L0, L1)-smooth setting is fundamentally more difficult than the standard smooth setting, in terms of the initial optimality gap and the smoothness constants.