mlsanityData to 14 Oct 2026

Accelerating Stochastic Composition Optimization

arXiv 1607.07329 ↗First posted 25 Jul 2016math.OC stat.MLcited by 46

Not on the map. Why?

Abstract (arXiv)

Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic first-order method, namely the accelerated stochastic compositional proximal gradient (ASC-PG) method, which updates based on queries to the sampling oracle using two different timescales. The ASC-PG is the first proximal gradient method for the stochastic composition problem that can deal with nonsmooth regularization penalty. We show that the ASC-PG exhibits faster convergence than the best known algorithms, and that it achieves the optimal sample-error complexity in several important special cases. We further demonstrate the application of ASC-PG to reinforcement learning and conduct numerical experiments.

Key facts. Cited by 46 papers in the map (data through 14 Oct 2026). First posted on arXiv 25 Jul 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 12; 2023: 14; 2024: 4; 2025: 2; 2026: 2.

46 papers.

Sort:

  1. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  2. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  3. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  4. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  5. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 43
  6. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 35
  7. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  8. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 22
  9. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  10. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  11. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  12. 2023LibAUC: A Deep Learning Library for X-Risk Optimizationcited by 15
34 more
  1. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  2. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  3. 2021Compositional federated learning: Applications in distributionally robust averaging and meta learningcited by 12
  4. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  5. 2021Efficient Semi-Implicit Variational Inferencecited by 9
  6. 2023Post-processing Private Synthetic Data for Improving Utility on Selected Measurescited by 9
  7. 2021Projection-Free Algorithm for Stochastic Bi-level Optimizationcited by 8
  8. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  9. 2022Algorithmic Foundations of Empirical X-risk Minimizationcited by 8
  10. 2021Rethinking Adam: A Twofold Exponential Moving Average Approachcited by 6
  11. 2023Debiasing Conditional Stochastic Optimizationcited by 6
  12. 2023Learning Unnormalized Statistical Models via Compositional Optimizationcited by 6
  13. 2024Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptionscited by 6
  14. 2022Learning Distributionally Robust Models at Scale via Composite Optimizationcited by 5
  15. 2022DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphscited by 5
  16. 2022Stochastic Compositional Optimization with Compositional Constraintscited by 4
  17. 2023Federated Conditional Stochastic Optimizationcited by 4
  18. 2024A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimizationcited by 4
  19. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  20. 2023A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimizationcited by 3
  21. 2022Faster Adaptive Momentum-Based Federated Methods for Distributed Composition Optimizationcited by 2
  22. 2023A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothnesscited by 2
  23. 2023Doubly Robust Instance-Reweighted Adversarial Trainingcited by 2
  24. 2024Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimizationcited by 2
  25. 2022Riemannian Stochastic Gradient Method for Nested Composition Optimizationcited by 1
  26. 2023Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learningcited by 1
  27. 2023FedDRO: Federated Compositional Optimization for Distributionally Robust Learningcited by 1
  28. 2025Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximizationcited by 1
  29. 2021PASTO: Strategic Parameter Optimization in Recommendation Systems -- Probabilistic is Better than Deterministiccited by 0
  30. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  31. 2023Federated Multi-Level Optimization over Decentralized Networkscited by 0
  32. 2025Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimizationcited by 0
  33. 2026On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passescited by 0
  34. 2026Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraintscited by 0