Research map / Federated learning and privacy / Communication-efficient FL
Sharp Gaussian approximations for Decentralized Federated Learning
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.
Proves Berry-Esseen bounds for Polyak-Ruppert averaged and final local SGD iterates in decentralized federated learning, plus two time-uniform Gaussian approximations of the full trajectory (Aggr-GA, Client-GA) for bootstrap-based attack detection.
Problem
Statistical (distributional) guarantees beyond convergence for local SGD in decentralized federated learning, including final-iterate inference and whole-trajectory approximation needed to detect adversarial model poisoning.
Approach
Derives a Berry-Esseen bound for local SGD iterates with explicit dependence on the number of clients K and step-size exponent beta, and constructs two time-uniform Gaussian process couplings (an aggregated one needing global covariance sharing and a client-level one mimicking local SGD) so that CUSUM-type maximal statistics can be bootstrapped.
Key results
- Berry-Esseen bound for Polyak-Ruppert averaged local SGD of order 1/sqrt(nK) + n^{1/2-beta} sqrt(K) + n^{-beta/2}/sqrt(K), implying CLT requires K = o(n^{2beta-1}).
- Shows a computation-communication phase transition: beta=3/4 optimal for K=o(sqrt(n)), while for K >~ sqrt(n) no beta in (1/2,1) makes the bound vanish.
- In simulations, Aggr-GA approximates the maximal partial-sum distribution best, with functional CLT (Brownian approximation) consistently worst.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Aggr-GA instead of a Brownian-motion functional-CLT approximation | Local SGD trajectory approximation · Simulation, K∈{10,25,50}, N=500, τ=20 | maximum-partial-sum quantile approximation | Helped |
| Use Client-GA instead of a Brownian-motion functional-CLT approximation | Local SGD trajectory approximation · Simulation, K∈{10,25,50}, N=500, τ=20 | maximum-partial-sum quantile approximation | Helped |
| Use Aggr-GA instead of Client-GA | Local SGD trajectory approximation · Local SGD trajectory | Gaussian approximation error: O_{\mathbb{P}}(n^{1-\beta}) + o_{\mathbb{P}}(n^{1/p}K^{-1/2}\log n); O_{\mathbb{P}}(n^{1-\beta}+(n/K)^{\frac{1}{4}+ \fra | Helped |
| Replace client-level approximation with Aggr-GA | Local SGD trajectory approximation · Inference-time computation and synchronization | synchronization and computational cost | Hurt |
| Increase the number of iterations N while holding K fixed | Local SGD · Berry-Esseen simulation | proxy Berry-Esseen error | Helped |
| Increase the number of clients K while holding n fixed | Local SGD · Berry-Esseen simulation | proxy Berry-Esseen error | Hurt |
| Set K=⌊n^0.2⌋ rather than K=⌊n^0.6⌋ | Local SGD with τ=5 and β∈{0.85,0.9,0.95} · Computation-communication trade-off simulation | proxy Berry-Esseen error as n increases | Mixed |
Surprising findings
- For K growing faster than sqrt(n), the Kolmogorov error does not vanish for any step-size exponent in (1/2,1).
Limitations
- Requires strong convexity and bounded moments; logistic-regression-type losses need an extra local concordance assumption and projection.
- Multiplier bootstrap is only sketched for the averaged iterate and not validated for the full trajectory; detailed derivations deferred to future work.
- Aggr-GA requires sharing covariance structure, which may affect privacy at inference time.
Experimental setup
Metrics: Kolmogorov distance proxy Q-Q plots of maximal partial sums
Baselines: functional CLT (Brownian motion approximation)
Builds on: local SGD Polyak-Ruppert averaging Komlos-Major-Tusnady approximation covariance-matching approximation
Closest papers by meaning
- Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD (NeurIPS 2024 · similarity 0.87)
- Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems (ICML 2024 · similarity 0.86)
- Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation (ICML 2025 · similarity 0.86)
- Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients (NeurIPS 2025 · similarity 0.86)
- Sketched Gaussian Mechanism for Private Federated Learning (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.