Research map / Optimization / Distributed and compressed
Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent
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 on-average argument stability and generalization bounds for decentralized minibatch SGD (with and without replacement) across convex, strongly convex, nonconvex and zeroth-order settings.
Problem
Generalization (learning theory) guarantees for decentralized minibatch SGD (DM-SGD) were largely unexplored, while existing D-SGD stability analyses do not cover minibatch sampling.
Approach
Analyzes on-average argument stability of DM-SGD by decomposing the mixing matrix to reduce the update to a centralized minibatch SGD form, and models with-replacement minibatch sampling via binomial sample counts; results recover centralized SGD rates.
Key results
- Establishes ℓ1 and ℓ2 on-average stability bounds for DM-SGD (with replacement) in convex, strongly convex and nonconvex cases, recovering C-SGD-type results.
- For convex smooth case with T≍n and step size c/√T, excess generalization error is O((n+b)/(n²b) + R(w*)/√n).
- Extends stability analysis to zeroth-order DM-SGD using two-point Gaussian gradient estimates.
Limitations
- Purely theoretical; no experiments validate the bounds
- Analysis restricted to i.i.d. sampling; non-i.i.d. (Markov chain) sampling left for future work
- Some bounds (e.g., nonsmooth nonconvex) rely on assumptions like Lipschitz continuity or non-negative loss
Experimental setup
Metrics: on-average argument stability generalization error bound excess generalization error
Baselines: Sun, Li, and Wang 2021 (D-SGD AWC) Bars, Bellet, and Tommasi 2023 (D-SGD CAU) Lei and Ying 2020 (C-SGD) Hardt, Recht, and Singer 2016 (C-SGD) Zhu et al. 2022
Builds on: D-SGD (Lian et al. 2017) on-average argument stability (Lei and Ying 2020) Bars, Bellet, and Tommasi 2023 stability analysis Nikolakakis et al. 2022a ZO stability
Closest papers by meaning
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.94)
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.92)
- Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology (AAAI 2025 · similarity 0.92)
- Enhancing Parallelism in Decentralized Stochastic Convex Optimization (ICML 2025 · similarity 0.90)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.89)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.89)
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.