mlsanityData to 7 Oct 2026

Finite-sum Composition Optimization via Variance Reduced Gradient Descent

arXiv 1610.04674 ↗First posted 15 Oct 2016math.OCcited by 15

Not on the map. Why?

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.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Oct 2016.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 6; 2022: 4; 2023: 4; 2024: 0; 2025: 1.

15 papers.

Sort:

  1. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  2. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  3. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 34
  4. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  5. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  6. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  7. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  8. 2021Projection-Free Algorithm for Stochastic Bi-level Optimizationcited by 8
  9. 2022Learning Distributionally Robust Models at Scale via Composite Optimizationcited by 5
  10. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  11. 2023Doubly Robust Instance-Reweighted Adversarial Trainingcited by 2
  12. 2022Riemannian Stochastic Gradient Method for Nested Composition Optimizationcited by 1
3 more
  1. 2023FedDRO: Federated Compositional Optimization for Distributionally Robust Learningcited by 1
  2. 2023Federated Multi-Level Optimization over Decentralized Networkscited by 0
  3. 2025Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Studycited by 0