Research map / Optimization / Nonconvex and smooth optimization
Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization
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.
Proposes Ada-Minimax and Ada-BiO, parameter-free adaptive momentum-normalized SGD methods for stochastic nonconvex-strongly-concave minimax and nonconvex-strongly-convex bilevel problems, with high-probability rates that adapt to unknown gradient noise.
Problem
Stochastic hierarchical (minimax and bilevel) optimization lacks convergence guarantees that adapt to unknown stochastic gradient noise levels; existing methods are suboptimal across noise regimes unless the noise magnitude is known.
Approach
Combine normalized SGD with momentum for the upper-level variable, using a noise-aware adaptive momentum parameter estimated online from gradient differences, with AdaGrad-Norm stepsizes for the lower-level variable, so the rate O~(1/sqrt(T)+sqrt(sigma)/T^{1/4}) is achieved without knowing the noise level.
Key results
- Ada-Minimax and Ada-BiO achieve high-probability rate O~(1/sqrt(T)+sqrt(sigma_bar)/T^{1/4}) for gradient norm without knowing noise level.
- On Sentiment140 deep AUC maximization, Ada-Minimax reports about 20% higher training AUC and 2% higher test AUC than the best compared algorithm PDSM.
- On the synthetic 1-D minimax problem, TiAda fails to converge at noise sigma=100 while the proposed method converges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Ada-Minimax instead of TiAda | minimax optimization · stochastic minimax convergence | gradient norm rate | Helped |
| use Ada-Minimax instead of PDSM | two-layer Transformer on Sentiment140 · training | AUC: +20% AUC | Helped |
| use Ada-Minimax instead of PDSM | two-layer Transformer on Sentiment140 · test | AUC: +2% AUC | Helped |
| reduce stochastic gradient noise | Ada-Minimax · synthetic minimax function | convergence speed | Helped |
| use Ada-Minimax instead of TiAda under high noise | synthetic minimax function · noise magnitude σ=100 | convergence | Helped |
| vary α within [0.1, 2.0] (ablation) | Ada-Minimax · deep AUC maximization | convergence speed and final AUC | No clear effect |
| vary η_y between 0.001 and 0.05 (ablation) | Ada-Minimax · deep AUC maximization | AUC curve | No clear effect |
| vary η_x from 0.001 to 0.01 (ablation) | Ada-Minimax · deep AUC maximization | final performance | No clear effect |
| increase η_x to 0.05 (ablation) | Ada-Minimax · deep AUC maximization | final training AUC | Hurt |
| vary γ within [0.01, 2.0] (ablation) | Ada-Minimax · deep AUC maximization | performance | No clear effect |
Limitations
- Requires the stochastic gradient noise to be lower-bounded (with probability one), an assumption that may be unusual.
- Theory covers only nonconvex-strongly-concave minimax and nonconvex-strongly-convex bilevel settings.
- Practical deep learning variant departs from the theoretical algorithm (modified noise estimate and stepsize).
Experimental setup
Datasets: Sentiment140 synthetic 1-D function f(x,y)=cos x + xy - y^2/2
Benchmarks: synthetic 1-D minimax function Sentiment140 deep AUC maximization hyperparameter optimization
Metrics: gradient norm training AUC test AUC running time
Baselines: TiAda SGDA PDSM
Builds on: normalized SGD with momentum AdaGrad-Norm TiAda Neumann series hypergradient approximation
Closest papers by meaning
- Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent (ICML 2022 · similarity 0.90)
- Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization (NeurIPS 2025 · similarity 0.89)
- Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via a Double Momentum Mechanism (ICLR 2025 · similarity 0.89)
- Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent (ICML 2025 · similarity 0.88)
- Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.88)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.88)
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.