mlsanityData to 14 Oct 2026

Multi-Level Composite Stochastic Optimization via Nested Variance Reduction

arXiv 1908.11468 ↗First posted 29 Aug 2019math.OC stat.MLcited by 28

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 9; 2023: 6; 2024: 4; 2025: 1; 2026: 3.

28 papers.

Sort:

  1. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  2. 2021Only Train Once: A One-Shot Neural Network Training And Pruning Frameworkcited by 70
  3. 2022Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applicationscited by 27
  4. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  5. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  6. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  7. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  8. 2021Compositional federated learning: Applications in distributionally robust averaging and meta learningcited by 12
  9. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  10. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  11. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 8
  12. 2021Communication-Efficient Sampling for Distributed Training of Graph Convolutional Networkscited by 7
16 more
  1. 2023Debiasing Conditional Stochastic Optimizationcited by 6
  2. 2023Learning Unnormalized Statistical Models via Compositional Optimizationcited by 6
  3. 2024Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptionscited by 6
  4. 2021On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reductioncited by 4
  5. 2022Stochastic Compositional Optimization with Compositional Constraintscited by 4
  6. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  7. 2022Finite-Sum Optimization: A New Perspective for Convergence to a Global Solutioncited by 2
  8. 2022Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimizationcited by 2
  9. 2023Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Ratecited by 2
  10. 2023Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimizationcited by 2
  11. 2024Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimizationcited by 2
  12. 2023Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learningcited by 1
  13. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
  14. 2026On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passescited by 0
  15. 2026Federated Compositional Muon Optimizer for Matrix-Wise Modelscited by 0
  16. 2026Optimal Momentum Methods for Stochastic Multilevel Compositional Optimizationcited by 0