# Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 7 Jul 2024.

## Builds on (most cited first, 16 of 16)

- [On the Variance of the Adaptive Learning Rate and Beyond](https://mlsanity.com/paper/1908.03265/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Flipout: Efficient Pseudo-Independent Weight Perturbations on Mini-Batches](https://mlsanity.com/paper/1803.04386/) (2018)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2002.07836/) (2020)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization](https://mlsanity.com/paper/1912.13515/) (2019)
- [Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation](https://mlsanity.com/paper/2209.08281/) (2022)
- [STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization](https://mlsanity.com/paper/2111.01040/) (2021)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization](https://mlsanity.com/paper/2308.09604/) (2023)

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

- [On the Stability and Generalization of First-order Bilevel Minimax Optimization](https://mlsanity.com/paper/2604.20115/) (2026)
- [Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization](https://mlsanity.com/paper/2610.01572/) (2026)

## Abstract (arXiv)

STOchastic Recursive Momentum (STORM)-based algorithms have been widely developed to solve one to K-level (K ≥ 3) stochastic optimization problems. Specifically, they use estimators to mitigate the biased gradient issue and achieve near-optimal convergence results. However, there is relatively little work on understanding their generalization performance, particularly evident during the transition from one to K-level optimization contexts. This paper provides a comprehensive generalization analysis of three representative STORM-based algorithms: STORM, COVER, and SVMR, for one, two, and K-level stochastic optimizations under both convex and strongly convex settings based on algorithmic stability. Firstly, we define stability for K-level optimizations and link it to generalization. Then, we detail the stability results for three prominent STORM-based algorithms. Finally, we derive their excess risk bounds by balancing stability results with optimization errors. Our theoretical results provide strong evidence to complete STORM-based algorithms: (1) Each estimator may decrease their stability due to variance with its estimation target. (2) Every additional level might escalate the generalization error, influenced by the stability and the variance between its cumulative stochastic gradient and the true gradient. (3) Increasing the batch size for the initial computation of estimators presents a favorable trade-off, enhancing the generalization performance.