# Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2018.

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

- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Compositional federated learning: Applications in distributionally robust averaging and meta learning](https://mlsanity.com/paper/2106.11264/) (2021)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Doubly Robust Instance-Reweighted Adversarial Training](https://mlsanity.com/paper/2308.00311/) (2023)
- [Riemannian Stochastic Gradient Method for Nested Composition Optimization](https://mlsanity.com/paper/2207.09350/) (2022)

## Abstract (arXiv)

Convex composition optimization is an emerging topic that covers a wide range of applications arising from stochastic optimal control, reinforcement learning and multi-stage stochastic programming. Existing algorithms suffer from unsatisfactory sample complexity and practical issues since they ignore the convexity structure in the algorithmic design. In this paper, we develop a new stochastic compositional variance-reduced gradient algorithm with the sample complexity of O((m+n)log(1/ε)+1/ε3) where m+n is the total number of samples. Our algorithm is near-optimal as the dependence on m+n is optimal up to a logarithmic factor. Experimental results on real-world datasets demonstrate the effectiveness and efficiency of the new algorithm.