mlsanityData to 7 Oct 2026

Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms

arXiv 2307.03357 ↗First posted 7 Jul 2023cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

Many machine learning tasks can be formulated as a stochastic compositional optimization (SCO) problem such as reinforcement learning, AUC maximization, and meta-learning, where the objective function involves a nested composition associated with an expectation. While a significant amount of studies has been devoted to studying the convergence behavior of SCO algorithms, there is little work on understanding their generalization, i.e., how these learning algorithms built from training examples would behave on future test examples. In this paper, we provide the stability and generalization analysis of stochastic compositional gradient descent algorithms through the lens of algorithmic stability in the framework of statistical learning theory. Firstly, we introduce a stability concept called compositional uniform stability and establish its quantitative relation with generalization for SCO problems. Then, we establish the compositional uniform stability results for two popular stochastic compositional gradient descent algorithms, namely SCGD and SCSC. Finally, we derive dimension-independent excess risk bounds for SCGD and SCSC by trade-offing their stability results and optimization errors. To the best of our knowledge, these are the first-ever-known results on stability and generalization analysis of stochastic compositional gradient descent algorithms.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 34 of its 53 references that are in the map. First posted on arXiv 7 Jul 2023.

Builds on

34 of 53 references.

References · 34

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  4. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  5. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  6. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  7. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  8. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  9. 2019Sharper bounds for uniformly stable algorithmscited by 91
  10. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  11. 2018A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimizationcited by 53
  12. 2020Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimizationcited by 51
22 more
  1. 2016Accelerating Stochastic Composition Optimizationcited by 46
  2. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  3. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  4. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 34
  5. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 27
  6. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  7. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  8. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 21
  9. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  10. 2020Optimal Algorithms for Convex Nested Stochastic Composite Optimizationcited by 20
  11. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  12. 2019Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimizationcited by 19
  13. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  14. 2020A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimizationcited by 16
  15. 2016Finite-sum Composition Optimization via Variance Reduced Gradient Descentcited by 15
  16. 2019Stochastic Proximal AUC Maximizationcited by 14
  17. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  18. 2019Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learningcited by 8
  19. 2020Compositional ADAM: An Adaptive Compositional Solvercited by 8
  20. 2018Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradientcited by 6
  21. 2018Nonparametric Stochastic Compositional Gradient Descent for Q-Learning in Continuous Markov Decision Problemscited by 5
  22. 2019Stochastic Variance Reduced Primal Dual Algorithms for Empirical Composition Optimizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 1.

3 papers.

  1. 2024Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizationscited by 2
  2. 2025Beyond Real Data: Synthetic Data through the Lens of Regularizationcited by 2
  3. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0