Research map / Optimization / Nonconvex and smooth optimization
Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves complexity lower bounds under (L0,L1)-smoothness for Decorrelated AdaGrad-Norm, Decorrelated AdaGrad, AdaGrad, and single-step adaptive SGD, showing quadratic dependence on Δ, L0, L1 that exceeds the optimal smooth SGD rate.
Problem
Whether adaptive gradient methods (AdaGrad variants) can achieve the optimal smooth-case complexity for non-convex stochastic optimization under relaxed (L0,L1)-smoothness, given existing upper bounds with higher-order polynomial dependence on problem parameters.
Approach
Constructs difficult piecewise objectives (exponential-type pieces satisfying the (L0,L1) smoothness with equality) and high-dimensional stochastic oracles that inject noise into one coordinate per step, showing AdaGrad-type step-size rules cannot avoid quadratic dependence on Δ, L0, L1; for single-step adaptive SGD, a biased random walk / tricky-pair argument yields a lower bound under affine noi
Key results
- Decorrelated AdaGrad-Norm requires at least Ω(Δ²L1²σ²ε⁻⁴) stochastic gradient queries under (L0,L1)-smoothness with bounded noise.
- Decorrelated AdaGrad lower bound Ω(Δ²L0²σ²γ⁻²ε⁻⁴) and AdaGrad lower bound Ω(Δ²L0²ε⁻⁴) (for γ ≤ σ), both quadratic in Δ and L0.
- Single-step adaptive SGD lower bound includes a term nearly quadratic in Δ, L1 in the non-dominating term for large σ2 under affine noise.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Decorrelated AdaGrad-Norm under $(L_0, L_1)$-smoothness instead of the smooth-case optimal first-order complexity reference | Decorrelated AdaGrad-Norm · $(L_0, L_1)$-smooth, Bounded-Noise | gradient-query complexity: \tilde{\Omega} \left( \frac{\Delta^2 L_1^2 \sigma^2}{\epsilon^4} + \frac{\Delta L_0 \sigma^2}{\epsilon^4} + \frac{\Delta | Hurt |
| Use Decorrelated AdaGrad under $(L_0, L_1)$-smoothness instead of the smooth-case optimal complexity reference | Decorrelated AdaGrad · $(L_0, L_1)$-smooth, Bounded-Noise | gradient-query complexity: \tilde{\Omega} \left( \frac{\Delta^2 L_0^2 \sigma^2}{\gamma^2 \epsilon^4} + \frac{\Delta^2 L_1^2 \sigma^2}{\gamma^2 \eps | Hurt |
| Use AdaGrad under $(L_0, L_1)$-smoothness instead of the smooth-case optimal complexity reference | AdaGrad · $(L_0, L_1)$-smooth, Bounded-Noise | gradient-query complexity: \tilde{\Omega} \left( \frac{\Delta^2 L_0^2}{\epsilon^4} + \frac{\Delta^2 L_1^2}{\epsilon^2} \right) | Hurt |
| Use single-step adaptive SGD with any current-gradient-only step size under affine noise | Single-step Adaptive SGD · $(L_0, L_1)$-smooth, Affine-Noise | gradient-query complexity: \tilde{\Omega} \left( \frac{\Delta L_0 \sigma_1^2}{\epsilon^4} + \frac{(\Delta L_1)^{2- \gamma_2 - \gamma_3} \sigma_1^{\ | Hurt |
| Use gradient clipping under relaxed smoothness rather than the AdaGrad variants considered | Gradient Clipping · $(L_0, L_1)$-smooth, Bounded-Noise | gradient-query complexity: \mathcal{O} \left( \frac{\Delta L_0 \sigma^2}{\epsilon^4} \right) | Helped |
Surprising findings
- SGD with gradient clipping achieves the classical Δ L0 σ² ε⁻⁴ complexity in the same setting where AdaGrad variants are shown to be provably worse.
- The lower bound for single-step adaptive SGD degenerates to zero as σ2 approaches 1, leaving open whether such methods can converge without quadratic dependence in that regime.
Limitations
- Strongest lower bounds apply to decorrelated AdaGrad variants that are not commonly used in practice.
- The AdaGrad lower bound is weaker in its dependence on σ than the decorrelated variant's bound.
- Upper and lower bounds do not exactly match, so the exact complexity of AdaGrad variants remains uncharacterized.
Experimental setup
Metrics: iteration complexity (gradient queries) to find epsilon-stat
Baselines: SGD AdaGrad-Norm upper bound Gradient clipping
Builds on: AdaGrad AdaGrad-Norm SGD with gradient clipping
Closest papers by meaning
- Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent (ICML 2022 · similarity 0.92)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.90)
- Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.90)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.90)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.90)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.