Research map / Optimization / Optimizers
Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations
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.
Gives algorithmic-stability generalization and excess-risk bounds for three STORM-based methods (STORM, COVER, SVMR) on one-, two- and K-level stochastic optimization in convex and strongly convex settings.
Problem
Generalization of STORM-based variance-reduced algorithms for one-level, two-level (compositional) and K-level stochastic optimization is poorly understood, especially as the number of levels grows.
Approach
Defines a uniform stability notion for K-level optimization, links it to generalization error via a variance-augmented bound, and derives stability and excess-risk bounds for STORM, COVER and SVMR by balancing stability against optimization error.
Key results
- Convex one-level STORM stability bound has an extra variance term sum eta*Var(v_j) on top of SGD's O(L_f eta T / n), so STORM may be less stable than SGD.
- Excess risk O(1/sqrt(n)) for STORM requires T ~ n^{5/2} in the convex setting versus T ~ n^{7/6} in the strongly convex setting.
- Simulated experiments show generalization error rising with the number of levels and improving with larger initial batch sizes; noise variance up to about 1.5 helps, beyond that it hurts.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use STORM instead of SGD | Univariate quintic polynomial fitting · Synthetic polynomial data, 60/40 train-test split | train-test loss gap | Hurt |
| Use STORM instead of SGD | Univariate quintic polynomial fitting · Synthetic polynomial data, 60/40 train-test split | overall loss | Helped |
| Increase the number of optimization levels | SVMR · Synthetic two-level optimization framework, levels 1 to 50 | generalization error | Hurt |
| Increase the initial batch size to 256 or 512 instead of 128 | SVMR · Synthetic optimization with 10 levels | generalization error | Helped |
| Use an initial batch size smaller than 128 instead of 128 | SVMR · Synthetic optimization with 10 levels | generalization error | Hurt |
| Increase Gaussian noise variance up to 1.5 | SVMR · Synthetic optimization with 10 levels and batch size 128 | generalization | Helped |
| Increase Gaussian noise variance beyond 1.5 | SVMR · Synthetic optimization with 10 levels and batch size 128 | generalization | Hurt |
Surprising findings
- STORM generalizes worse than SGD in the quintic polynomial experiment despite achieving lower overall loss.
- Adding variance-reduction estimators can reduce stability, so STORM may be less stable than SGD in theory.
Limitations
- Experiments are limited to simulated data and small-scale settings.
- Bounds assume smoothness, Lipschitz continuity and bounded domain assumptions; stability can degrade due to estimator variance.
Experimental setup
Datasets: synthetic univariate quintic polynomial data with Gaussian noise
Metrics: training and testing mean squared error generalization error
Baselines: SGD
Builds on: STORM COVER SVMR algorithmic stability (Bousquet and Elisseeff)
Closest papers by meaning
- STORM+: Fully Adaptive SGD with Recursive Momentum for Nonconvex Optimization (NeurIPS 2021 · similarity 0.91)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.89)
- Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization (NeurIPS 2021 · similarity 0.89)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.88)
- Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions (NeurIPS 2024 · similarity 0.88)
- Non-convex Stochastic Composite Optimization with Polyak Momentum (ICML 2024 · similarity 0.87)
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.