Research map / Optimization / Nonconvex and smooth optimization
Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology
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.
Theoretical stability-based generalization analysis of zeroth-order decentralized SGD with time-varying topology, giving bounds for consensus and local models in convex, strongly convex, and non-convex cases.
Problem
Generalization error of zeroth-order decentralized SGD over changing communication topologies is not well understood, and prior ZO-SGD bounds do not match SGD in convex and strongly convex cases.
Approach
Uses uniform stability with a new decomposition of the zeroth-order stability error that exploits convexity, yielding SGD-matching bounds for the consensus model (topology-independent) and topology-dependent bounds for local models via a new average stability framework.
Key results
- Consensus-model generalization bounds for ZO-DSGD match SGD in convex (O(T/(mn))) and strongly convex (O(1/(µmn))) cases, and match DSGD in the non-convex case.
- Consensus-model bounds are topology-independent, while local-model bounds depend on the communication matrix product WT-1:t via Tr(WT-1:t).
- Results hold with a zeroth-order gradient estimator using K random directions, with learning rate scaled by K/(d+K-1) style factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use zeroth-order decentralized SGD with changing topology for the consensus model | ZO-DSGD · Convex case | generalization error bound | Helped |
| Use zeroth-order decentralized SGD with changing topology for the consensus model | ZO-DSGD · Strongly convex case | generalization error bound | Helped |
| Use zeroth-order decentralized SGD with changing topology for the consensus model | ZO-DSGD · Non-convex case | generalization error bound | Helped |
| Use local models instead of the consensus model | ZO-DSGD · Local models, convex case | generalization error bound | Mixed |
Surprising findings
- Communication topology has no effect on the consensus-model generalization bound, though it affects the final excess risk through optimization error.
Limitations
- Relies on Lipschitz and smoothness assumptions that may not hold in practice.
- Analysis restricted to full-batch-free single-sample updates; minibatch setting left to future work.
- Non-convex bound requires loss in [0,1] and monotonically decreasing learning rate.
Experimental setup
Metrics: generalization error bound uniform stability
Baselines: SGD bounds (Hardt et al. 2016) DSGD bounds (Richards and Rebeschini 2020; Le Bars et al. 2024) ZO-SGD bounds (Nikolakakis et al. 2022; Liu et al. 2024)
Builds on: Hardt et al. 2016 stability of SGD Nikolakakis et al. 2022 ZO-SGD generalization Liu et al. 2024 ZO-SGD generalization Le Bars et al. 2024 DSGD generalization Lei and Ying 2020 stability
Closest papers by meaning
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.92)
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.90)
- Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence (AAAI 2025 · similarity 0.89)
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.88)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.87)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.87)
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.