Research map / Optimization / Nonconvex and smooth optimization
Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first algorithmic stability and generalization analysis of stochastic compositional gradient descent (SCGD and SCSC), yielding dimension-independent excess risk bounds O(1/√n + 1/√m).
Problem
Generalization of stochastic compositional optimization (SCO) algorithms, which had only been analyzed for convergence, not for how well learned models perform on unseen data.
Approach
Introduces compositional uniform stability, which perturbs either the outer-function sample set or the inner-function sample set, links it to generalization for SCO via a sample-splitting argument, and then bounds stability of SCGD and SCSC to derive excess risk bounds that trade stability against optimization error.
Key results
- SCGD and SCSC both achieve excess risk O(1/√n + 1/√m) in the convex smooth case, with SCGD needing T ≍ max(n^3.5, m^3.5) iterations versus T ≍ max(n^2.5, m^2.5) for SCSC.
- In the strongly convex case, SCGD needs T ≍ max(n^{5/3}, m^{5/3}) and SCSC needs T ≍ max(n^{7/6}, m^{7/6}) iterations for the same rate.
- The generalization gap bound for any ε-uniformly stable randomized algorithm is L_f L_g ε_ν + 4 L_f L_g ε_ω + L_f sqrt(m^{-1} E[Var_ω]), which reduces to the standard SGD stability bound when g_ω(x)=x.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the SCSC update instead of the SCGD update | Stochastic compositional gradient descent · Convex F_S | iterations to achieve excess risk \mathcal{O}(1/\sqrt{n}+1/\sqrt{m}): T \asymp \max(n^{3.5},m^{3.5}) -> T \asymp \max(n^{2.5},m^{2.5}) | Helped |
| Use the SCSC update instead of the SCGD update | Stochastic compositional gradient descent · Strongly convex F_S | iterations to achieve excess risk \mathcal{O}(1/\sqrt{n}+1/\sqrt{m}): T \asymp \max(n^{5/3},m^{5/3}) -> T \asymp \max(n^{7/6},m^{7/6}) | Helped |
Surprising findings
- SCGD requires substantially more iterations than SGD-style rates to reach the O(1/√n) generalization rate, which the authors attribute to the moving-average tracking and inner-function variance terms.
Limitations
- Analysis restricted to convex and smooth (or strongly convex and smooth) settings; non-smooth and non-convex cases such as ReLU networks are left open.
- Iteration requirements (T ≍ max(n^3.5, m^3.5) for SCGD) are super-linear in the sample sizes, not the linear T = O(max(n,m)) the authors hope for.
- No empirical experiments are reported to validate the bounds.
Experimental setup
Metrics: compositional uniform stability excess risk number of iterations required
Baselines: SGD (non-compositional stability bound) uniform convergence bound for SCO ERM minimizer
Builds on: SCGD SCSC uniform argument stability of SGD on-average model stability
Closest papers by meaning
- How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization? (NeurIPS 2024 · similarity 0.91)
- Fast Training Method for Stochastic Compositional Optimization Problems (NeurIPS 2021 · similarity 0.90)
- Efficient Smooth Non-Convex Stochastic Compositional Optimization via Stochastic Recursive Gradient Descent (NeurIPS 2019 · similarity 0.90)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.89)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.88)
- Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.