# Finite-sum Composition Optimization via Variance Reduced Gradient Descent

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2016.

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

- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)
- [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)
- [FedDRO: Federated Compositional Optimization for Distributionally Robust Learning](https://mlsanity.com/paper/2311.12652/) (2023)
- [Federated Multi-Level Optimization over Decentralized Networks](https://mlsanity.com/paper/2310.06217/) (2023)
- [Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Study](https://mlsanity.com/paper/2505.11752/) (2025)

## Abstract (arXiv)

The stochastic composition optimization proposed recently by Wang et al. [2014] minimizes the objective with the compositional expectation form: minx~(mathbbEiFi circ mathbbEj Gj)(x). It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: [minx f (x) := frac1n sumi = 1n Fi left(frac1m sumj = 1m Gj (x) right). ] We propose two algorithms to solve this problem by combining the stochastic compositional gradient descent (SCGD) and the stochastic variance reduced gradient (SVRG) technique. A constant linear convergence rate is proved for strongly convex optimization, which substantially improves the sublinear rate O(K-0.8) of the best known algorithm.