Research map / Federated learning and privacy / Communication-efficient FL
Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD
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.
Asymptotic CLT analysis of Unified Distributed SGD under Markovian/i.i.d. agent sampling, showing that improving a few agents' sampling efficiency reduces the limiting covariance and can match or beat many agents with moderate improvements.
Problem
Existing finite-time analyses of distributed SGD with Markovian sampling are dominated by the worst-performing (slowest-mixing) agent and do not show how individual agents' sampling strategies affect overall convergence.
Approach
Derives a CLT for UD-SGD (covering DSGD, local SGD, increasing communication intervals) where the limiting covariance is an average of per-agent asymptotic covariance matrices, so each agent's sampling efficiency contributes additively; a Loewner-order argument shows any single agent's efficiency gain reduces the overall covariance.
Key results
- Simulations with 100 agents on binary classification show that 10 agents using SRRW among 50 SRW-based agents achieve smaller MSE than all 50 agents using NBRW.
- Theory gives V = (1/N^2) sum_i V_i, implying a 1/N scaling of the limiting covariance and MSE improvement with number of agents.
- Empirically, shuffling outperforms i.i.d. sampling in asymptotic MSE, and SRRW > NBRW > SRW in sampling efficiency.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace SRW with SRRW sampling for graph-data agents | UD-SGD · ijcnn1 binary classification | MSE | Helped |
| Replace SRW with NBRW sampling for graph-data agents | UD-SGD · ijcnn1 binary classification | MSE | Helped |
| Replace i.i.d. sampling with shuffling for full-data agents | UD-SGD · ijcnn1 binary classification | asymptotic MSE | Helped |
| Replace i.i.d. sampling with shuffling for full-data agents | UD-SGD · ijcnn1 binary classification, early iterations | convergence | Mixed |
| Upgrade more graph-data agents from SRW to SRRW (ablation) | UD-SGD · ijcnn1 binary classification | asymptotic MSE | Helped |
| Upgrade 10 of 50 graph-data agents from SRW to SRRW, rather than use NBRW for all 50 (ablation) | UD-SGD · ijcnn1 binary classification | MSE | Helped |
| Upgrade 20 graph-data agents from SRW to SRRW (ablation) | UD-SGD · ijcnn1 binary classification | MSE | Helped |
| Use SRRW instead of NBRW or SRW sampling | UD-SGD · CIFAR-10 image classification | MSE | Helped |
| Change communication pattern among centralized SGD, LSGD-FP, DSGD-VT, and DFL while holding sampling fixed (ablation) | UD-SGD · ijcnn1 binary classification | MSE | No clear effect |
| Improve agents' sampling strategies (shuffling over i.i.d.; SRRW over NBRW over SRW) (ablation) | DSGD-VT and DFL · ijcnn1 binary classification | MSE | Helped |
Surprising findings
- A small subset of agents adopting highly efficient sampling (SRRW) can outperform the majority using moderately improved sampling (NBRW).
- Shuffling may underperform i.i.d. sampling for small time n due to slow initial mixing, despite better asymptotic MSE.
Limitations
- Requires gamma_n = 1/n for increasing communication intervals and stability assumption on iterates, which is assumed rather than proven.
- Finite-time bounds per agent are not developed; results are asymptotic.
- SRRW analysis for multi-agent settings is not theoretically treated; only numerically evaluated.
Experimental setup
Datasets: ijcnn1 CIFAR-10
Benchmarks: ijcnn1 CIFAR-10
Metrics: mean-square error asymptotic covariance
Baselines: i.i.d. sampling simple random walk non-backtracking random walk DSGD-VT DFL
Builds on: Unified Distributed SGD Poisson equation noise decomposition asymptotic covariance matrix for Markov chains
Closest papers by meaning
- Optimality and Stability in Federated Learning: A Game-theoretic Approach (NeurIPS 2021 · similarity 0.88)
- Sharp Gaussian approximations for Decentralized Federated Learning (NeurIPS 2025 · similarity 0.87)
- Streaming Federated Learning with Markovian Data (NeurIPS 2025 · similarity 0.86)
- LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging (NeurIPS 2026 · similarity 0.86)
- Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.86)
- Adaptive Federated Learning with Auto-Tuned Clients (ICLR 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.