Research map / Optimization / Nonconvex and smooth optimization
Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions
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-STORM, a fully adaptive STORM variance-reduction method with a cumulative-gradient-based learning rate that reaches O(T^{-1/3}) for non-convex stochastic optimization without bounded-gradient or bounded-function-value assumptions or log T factors, extended to compositional and finite-sum problems.
Problem
Adaptive variance reduction (STORM-style) for non-convex stochastic optimization, where existing adaptive methods need bounded gradients/function values or incur an extra O(log T) factor; also finite-sum and compositional settings.
Approach
Learning rate set to min{1/T^{1/3}, 1/(T^{(1-α)/3}(Σ||v_i||²)^α)} with fixed momentum β=T^{-2/3}, so the step size adapts to accumulated gradient estimates; the analysis avoids bounded-gradient assumptions. For finite-sum, a SAG-type or SVRG-type correction term is added to the STORM estimator to reach O(n^{1/4}T^{-1/2}).
Key results
- Ada-STORM achieves O(T^{-1/3}) convergence for non-convex stochastic optimization without bounded gradient/function value assumptions and without the extra O(log T) factor.
- Finite-sum variant attains O(n^{1/4}T^{-1/2}), improving on AdaSpider's O(n^{1/4}T^{-1/2} log(nT)) for alpha in (1/4,1/3).
- Experiments on CIFAR-10/100 and WikiText-2 report comparable training behavior and better test loss/accuracy and slightly better perplexity relative to STORM, STORM+, META-STORM, SGD, Adam, AdaBelief.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adaptive STORM learning rate (Ada-STORM) instead of STORM's fixed-form step size with known L, G | STORM for non-convex stochastic optimization · theory: non-convex stochastic | convergence rate | Helped |
| Compositional extension of adaptive STORM | stochastic compositional optimization · theory: NC compositional | convergence rate | Helped |
| SAG-style gradient-memory correction added to STORM estimator for finite-sum | STORM finite-sum (SAG-type) · theory: NC finite-sum | convergence rate | Helped |
| SVRG-style periodic full-gradient correction replacing SAG memory in STORM estimator | STORM finite-sum (SVRG-type) · theory: NC finite-sum | convergence rate | No clear effect |
| Ada-STORM vs. STORM, STORM+, META-STORM and SGD/Adam/AdaBelief on image classification | ResNet18/ResNet34 on CIFAR-10/100 · CIFAR-10, CIFAR-100 | training loss/accuracy and testing accuracy | Mixed |
| Ada-STORM vs. baselines on language modeling | 2-layer Transformer on WikiText-2 · WikiText-2 | perplexity and convergence speed | Helped |
Limitations
- Algorithm requires the total iteration count T in advance, circumvented only via a doubling trick.
- Parameter alpha must satisfy 0<alpha<1/3; the optimal exponent trade-off is stated only for alpha approaching 1/3.
- Experiments are limited to small-scale image classification and a 2-layer Transformer on WikiText-2.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 WikiText-2
Benchmarks: CIFAR-10 CIFAR-100 WikiText-2
Metrics: training loss training accuracy testing loss testing accuracy perplexity
Baselines: STORM STORM+ META-STORM SGD Adam AdaBelief
Builds on: STORM STORM+ META-STORM SPIDER SAG
Closest papers by meaning
- Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization (AAAI 2024 · similarity 0.88)
- Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations (ICML 2024 · similarity 0.88)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.87)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.86)
- Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.86)
- Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization (NeurIPS 2025 · similarity 0.86)
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.