# Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 51 references that are in the map.
- First posted on arXiv 18 Jul 2022.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [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)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [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)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022)
- [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)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms](https://mlsanity.com/paper/1810.10690/) (2018)
- [Benchmarking Deep AUROC Optimization: Loss Functions and Algorithmic Choices](https://mlsanity.com/paper/2203.14177/) (2022)
- [Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem](https://mlsanity.com/paper/1809.02505/) (2018)

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

- [LibAUC: A Deep Learning Library for X-Risk Optimization](https://mlsanity.com/paper/2306.03065/) (2023)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization](https://mlsanity.com/paper/2305.18730/) (2023)
- [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)
- [Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints](https://mlsanity.com/paper/2504.15243/) (2025)
- [Serverless Federated AUPRC Optimization for Multi-Party Collaborative Imbalanced Data Mining](https://mlsanity.com/paper/2308.03035/) (2023)
- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [Communication-Efficient Federated Group Distributionally Robust Optimization](https://mlsanity.com/paper/2410.06369/) (2024)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization](https://mlsanity.com/paper/2602.02877/) (2026)
- [Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2506.02504/) (2025)

## Abstract (arXiv)

Variance reduction techniques such as SPIDER/SARAH/STORM have been extensively studied to improve the convergence rates of stochastic non-convex optimization, which usually maintain and update a sequence of estimators for a single function across iterations. What if we need to track multiple functional mappings across iterations but only with access to stochastic samples of O(1) functional mappings at each iteration? There is an important application in solving an emerging family of coupled compositional optimization problems in the form of sumi=1m fi(gi(w)), where gi is accessible through a stochastic oracle. The key issue is to track and estimate a sequence of mathbf g(w)=(g1(w), ldots, gm(w)) across iterations, where mathbf g(w) has m blocks and it is only allowed to probe O(1) blocks to attain their stochastic values and Jacobians. To improve the complexity for solving these problems, we propose a novel stochastic method named Multi-block-Single-probe Variance Reduced (MSVR) estimator to track the sequence of mathbf g(w). It is inspired by STORM but introduces a customized error correction term to alleviate the noise not only in stochastic samples for the selected blocks but also in those blocks that are not sampled. With the help of the MSVR estimator, we develop several algorithms for solving the aforementioned compositional problems with improved complexities across a spectrum of settings with non-convex/convex/strongly convex/Polyak-Lojasiewicz (PL) objectives. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on the strong convexity parameter. Empirical studies on multi-task deep AUC maximization demonstrate the better performance of using the new estimator.