# Optimal Algorithms for Stochastic Multi-Level Compositional Optimization

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 43 references that are in the map.
- First posted on arXiv 15 Feb 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Tilted Empirical Risk Minimization](https://mlsanity.com/paper/2007.01162/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization](https://mlsanity.com/paper/1812.01094/) (2018)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [Linear Convergence of Adaptive Stochastic Gradient Descent](https://mlsanity.com/paper/1908.10525/) (2019)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2002.07836/) (2020)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019)
- [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020)
- [Multi-Level Stochastic Gradient Methods for Nested Composition Optimization](https://mlsanity.com/paper/1801.03600/) (2018)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Accelerated Method for Stochastic Composition Optimization with Nonsmooth Regularization](https://mlsanity.com/paper/1711.03937/) (2017)
- [SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms](https://mlsanity.com/paper/1810.10690/) (2018)
- [Stochastic Recursive Momentum Method for Non-Convex Compositional Optimization](https://mlsanity.com/paper/2006.01688/) (2020)
- [Variance Reduced methods for Non-convex Composition Optimization](https://mlsanity.com/paper/1711.04416/) (2017)

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

- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [Learning Unnormalized Statistical Models via Compositional Optimization](https://mlsanity.com/paper/2306.07485/) (2023)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)
- [AgenticRecTune: Multi-Agent with Self-Evolving Skillhub for Recommendation System Optimization](https://mlsanity.com/paper/2604.26969/) (2026)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimization](https://mlsanity.com/paper/2211.01883/) (2022)
- [Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Rate](https://mlsanity.com/paper/2306.03322/) (2023)
- [Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization](https://mlsanity.com/paper/2308.09604/) (2023)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizations](https://mlsanity.com/paper/2407.05286/) (2024)
- [On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passes](https://mlsanity.com/paper/2602.20646/) (2026)
- [Federated Compositional Muon Optimizer for Matrix-Wise Models](https://mlsanity.com/paper/2608.12710/) (2026)
- [Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization](https://mlsanity.com/paper/2610.01572/) (2026)
- [Convergence Analysis of STORM Under Different Geometries](https://mlsanity.com/paper/2610.01599/) (2026)

## Abstract (arXiv)

In this paper, we investigate the problem of stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth but possibly non-convex functions. Existing methods for solving this problem either suffer from sub-optimal sample complexities or need a huge batch size. To address these limitations, we propose a Stochastic Multi-level Variance Reduction method (SMVR), which achieves the optimal sample complexity of Oleft(1 / ε3right) to find an ε-stationary point for non-convex objectives. Furthermore, when the objective function satisfies the convexity or Polyak-Lojasiewicz (PL) condition, we propose a stage-wise variant of SMVR and improve the sample complexity to Oleft(1 / ε2right) for convex functions or Oleft(1 /left(μεright)right) for non-convex functions satisfying the μ-PL condition. The latter result implies the same complexity for μ-strongly convex functions. To make use of adaptive learning rates, we also develop Adaptive SMVR, which achieves the same complexities but converges faster in practice. All our complexities match the lower bounds not only in terms of ε but also in terms of μ (for PL or strongly convex functions), without using a large batch size in each iteration.