Research map / Optimization / Optimizers
How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization?
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.
Derives stability-based generalization and optimization bounds for SCGD and SCSC (convex and non-convex) and their black-box (zeroth-order) variants, and applies them to FOO-based VFL and VFL-CZOFO.
Problem
Learning guarantees (generalization and optimization) for stochastic compositional optimization are known only for first-order methods with restrictive parameter choices; the impact of derivative-free (black-box) gradient estimation on these guarantees is unknown.
Approach
A new uniform-stability analysis framework gives sharper SCGD/SCSC bounds under milder step-size and iteration choices, extended to non-convex losses via an almost co-coercivity lemma; three black-box variants are analyzed to show that better gradient estimation (smaller smoothing distance mu, more random directions b) tightens the bounds.
Key results
- Convex SCGD/SCSC stability bound O((n^-1+m^-1) log T) improves on prior O(T^{-1/7}+...) analysis and works with T=O(max(n,m)) instead of O(max(n^{7/2},m^{7/2})).
- Non-convex black-box SCGD/SCSC excess risk bound O((n^-1+m^-1)T^{1/2} log T + n^{-1/2} + mu^2 + b^{-1}d_2), so smaller smoothing distance mu and more directions b tighten the bound.
- Applied to VFL, FOO-based VFL and VFL-CZOFO obtain the first stability-based generalization bound O(n^-1 T^{1/2} log T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the new stability analysis rather than the prior [21] analysis | Convex SCGD/SCSC · Convex SCO | generalization bound: O\left(T^{-1/7} + \left(n^{-1} + m^{-1}\right)T^{1/7} + m^{-1/2}\right) -> O\left(\left(n^{-1} + m^{-1}\right)\log T + n | Helped |
| extend the stability analysis to non-convex objectives | SCGD/SCSC · Non-convex SCO | generalization bound: O\left(\left(n^{-1} + m^{-1}\right)T^{1/2}\log T + n^{-1/2}\right) | Mixed |
| estimate the outer gradient using a smaller finite-difference distance μ | Outer black-box SCGD/SCSC · Outer black-box SCO | excess risk bound: μ² | Helped |
| use more random directions b for gradient estimation | Outer black-box SCGD/SCSC · Outer black-box SCO | excess risk bound: b^{-1}d^2 | Helped |
| estimate both inner and outer gradients instead of only one gradient | Full black-box SCGD/SCSC · Full black-box SCO | optimization bound: O\left(\mu^4 + d_2^2/b^2 + d_2/b\right) | Mixed |
| apply the analysis to FOO-based VFL | FOO-based VFL · VFL | generalization bound: O\left(n^{-1}T^{1/2}\log T\right) | Helped |
| apply outer-gradient finite differences in VFL-CZOFO | VFL-CZOFO · VFL | excess risk bound: O\left(n^{-1}T^{1/2}\log T + \mu^2 + b^{-1}d_2\right) | Helped |
Surprising findings
- Full black-box setting exhibits a stronger dependence on gradient estimation quality when the fraction of unknown gradients is large.
Limitations
- Analysis restricted to uniform model stability with bounded-variance and Lipschitz/smooth assumptions; no experiments reported.
- Non-convex optimization results require an additional PL-type condition (Assumption 5) for the empirical risk.
- Non-convex generalization bound is T^{1/2} times larger than the convex one.
Experimental setup
Metrics: generalization error bound excess risk bound stability bound
Baselines: SCGD (Wang et al. 2017 stability / Chen et al. 2021 analysis) SCSC FedZO VFL-CZOFO FOO-based VFL
Builds on: SCGD SCSC algorithmic stability (Hardt et al. / Bousquet and Elisseeff framework) Wang et al. 2017 stability for compositional SGD
Closest papers by meaning
- Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms (ICML 2024 · similarity 0.91)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.88)
- A Doubly Recursive Stochastic Compositional Gradient Descent Method for Federated Multi-Level Compositional Optimization (ICML 2024 · similarity 0.87)
- Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization (NeurIPS 2025 · similarity 0.87)
- Sample Average Approximation for Conditional Stochastic Optimization with Dependent Data (ICML 2024 · similarity 0.86)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.86)
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.