# Multi-Level Composite Stochastic Optimization via Nested Variance Reduction

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2019.

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

- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Only Train Once: A One-Shot Neural Network Training And Pruning Framework](https://mlsanity.com/paper/2107.07467/) (2021)
- [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [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)
- [Compositional federated learning: Applications in distributionally robust averaging and meta learning](https://mlsanity.com/paper/2106.11264/) (2021)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networks](https://mlsanity.com/paper/2101.07706/) (2021)
- [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023)
- [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)
- [On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction](https://mlsanity.com/paper/2103.02696/) (2021)
- [Stochastic Compositional Optimization with Compositional Constraints](https://mlsanity.com/paper/2209.04086/) (2022)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Finite-Sum Optimization: A New Perspective for Convergence to a Global Solution](https://mlsanity.com/paper/2202.03524/) (2022)
- [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)
- [Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning](https://mlsanity.com/paper/2307.05384/) (2023)
- [Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2506.02504/) (2025)
- [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)

## Abstract (arXiv)

We consider multi-level composite optimization problems where each mapping in the composition is the expectation over a family of random smooth mappings or the sum of some finite number of smooth mappings. We present a normalized proximal approximate gradient (NPAG) method where the approximate gradients are obtained via nested stochastic variance reduction. In order to find an approximate stationary point where the expected norm of its gradient mapping is less than ε, the total sample complexity of our method is O(ε-3) in the expectation case, and O(N+√Nε-2) in the finite-sum case where N is the total number of functions across all composition levels. In addition, the dependence of our total sample complexity on the number of composition levels is polynomial, rather than exponential as in previous work.