mlsanityData to 7 Oct 2026

A Stochastic Composite Gradient Method with Incremental Variance Reduction

arXiv 1906.10186 ↗First posted 24 Jun 2019math.OC stat.MLcited by 26

Not on the map. Why?

Abstract (arXiv)

We consider the problem of minimizing the composition of a smooth (nonconvex) function and a smooth vector mapping, where the inner mapping is in the form of an expectation over some random variable or a finite sum. We propose a stochastic composite gradient method that employs an incremental variance-reduced estimator for both the inner vector mapping and its Jacobian. We show that this method achieves the same orders of complexity as the best known first-order methods for minimizing expected-value and finite-sum nonconvex functions, despite the additional outer composition which renders the composite gradient estimator biased. This finding enables a much broader range of applications in machine learning to benefit from the low complexity of incremental variance-reduction methods.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 8; 2022: 7; 2023: 7; 2024: 4.

26 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. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 32
  4. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  5. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  6. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  7. 2022Stochastic Constrained DRO with a Complexity Independent of Sample Sizecited by 16
  8. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  9. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  10. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  11. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  12. 2021Projection-Free Algorithm for Stochastic Bi-level Optimizationcited by 8
14 more
  1. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 7
  2. 2022Learning Distributionally Robust Models at Scale via Composite Optimizationcited by 5
  3. 2023Learning Unnormalized Statistical Models via Compositional Optimizationcited by 5
  4. 2024Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptionscited by 5
  5. 2021On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reductioncited by 4
  6. 2023Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimizationcited by 3
  7. 2022Finite-Sum Optimization: A New Perspective for Convergence to a Global Solutioncited by 2
  8. 2023Decentralized Multi-Level Compositional Optimization Algorithms with Level-Independent Convergence Ratecited by 2
  9. 2023Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimizationcited by 2
  10. 2024Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimizationcited by 2
  11. 2022Riemannian Stochastic Gradient Method for Nested Composition Optimizationcited by 1
  12. 2023FedDRO: Federated Compositional Optimization for Distributionally Robust Learningcited by 1
  13. 2023Achieving Linear Speedup in Decentralized Stochastic Compositional Minimax Optimizationcited by 0
  14. 2024Efficient Continual Finite-Sum Minimizationcited by 0