Research map / Federated learning and privacy / Communication-efficient FL
A New Theoretical Perspective on Data Heterogeneity in Federated 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.
Proposes a heterogeneity-driven pseudo-Lipschitz assumption (constant L_h) plus global Lipschitz constant L_g to replace the local Lipschitz constant in FedAvg convergence analysis, yielding tighter bounds that explain why more local updates can help under data heterogeneity.
Problem
Existing convergence bounds for FedAvg under data heterogeneity are pessimistic: they predict that more local updates hurt convergence when gradient divergence is large, contradicting empirical results.
Approach
Replaces the per-worker local Lipschitz gradient assumption with a weaker heterogeneity-driven pseudo-Lipschitz condition on averaged local gradients (constant L_h, which captures the gap between averaged and centralized models) plus a global Lipschitz constant L_g, so the local-update error scales with L_h rather than the local Lipschitz constant.
Key results
- On MLP/MNIST, the estimated L_h (0.82 at 25% non-IID) is far below the local Lipschitz constant (130.97), and on CNN/CIFAR-10 at 100% non-IID L_h=2.15 versus local L̃=1662.24.
- For quadratic objectives with L_h=0 (common Hessian), local SGD reaches the target loss in fewer rounds than mini-batch SGD at equal gradient budget when sigma^2 is small (e.g., 95 rounds for I=10 vs 927 for I=1, s=5 in the reported table).
- Theorem bounds for FedAvg replace the local Lipschitz constant with L_g and L_h, keeping the O(1/sqrt(RI)) order while allowing large I even when gradient divergence zeta is large.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the non-IID data percentage | MLP and CNN on MNIST and CIFAR-10 · MNIST and CIFAR-10, 25%–100% non-IID | local Lipschitz constant | Mixed |
| Increase the non-IID data percentage | MLP, CNN, VGG-11, and VGG-16 · MNIST, CIFAR-10, and CIFAR-100, 25%–100% non-IID | heterogeneity-driven pseudo-Lipschitz constant | Helped |
| Use different two-sided learning-rate pairs while keeping γη fixed | FedAvg · Quadratic objective, I=10 | rounds to target f(x)=0.8: 86\pm 1.6 across all four pairs | No clear effect |
| Increase local updates from I=1 to I=5 or I=10, with s=1 | FedAvg · Quadratic objective | rounds to target f(x)=0.8: 927\pm 3.4 -> 187 \pm 2.3; 927\pm 3.4 -> 95\pm 2.4 | Helped |
| Use local SGD with I=5 instead of mini-batch SGD with I=1, keeping sampled gradients per round equal | FedAvg · Quadratic objective, s=5 | rounds to target f(x)=0.8: 927\pm 3.4 -> 187 \pm 2.3 | Helped |
| Use local SGD with I=10 instead of mini-batch SGD with I=1, keeping sampled gradients per round equal | FedAvg · Quadratic objective, s=10 | rounds to target f(x)=0.8: 925 \pm 1.7 -> 95\pm 2.4 | Helped |
| Increase local updates to the largest tested I | FedAvg, CNN with partial participation and MLP with full participation · CIFAR-10 and MNIST, more than 50% heterogeneous data | training loss | Helped |
Surprising findings
- L_h can be zero while gradient divergence zeta is arbitrarily large, so zeta alone can overestimate the effect of heterogeneity.
- Local SGD can outperform mini-batch SGD for quadratic objectives without any constraint on gradient divergence when sigma is small.
Limitations
- The relation L_g^2/N + L_h^2 <= L̃^2 is only supported empirically, not proven.
- The quadratic-case bounds require a weak gradient divergence assumption on iterates, and the LHS involves virtual non-observable averaged models for k != 0.
- Partial participation bound retains a gradient-divergence term that L_h cannot reduce.
Experimental setup
Datasets: MNIST CIFAR-10 CIFAR-100
Benchmarks: MNIST CIFAR-10 CIFAR-100
Metrics: training loss estimated L_h, local Lipschitz constant, L_g communication rounds to target loss
Baselines: FedAvg convergence bound with local Lipschitz assumption mini-batch SGD FedAvg with momentum FedAdam
Builds on: FedAvg FedAvg with momentum FedAdam SCAFFOLD
Closest papers by meaning
- FedGPS: Statistical Rectification Against Data Heterogeneity in Federated Learning (NeurIPS 2025 · similarity 0.92)
- Widening the Network Mitigates the Impact of Data Heterogeneity on FedAvg (ICML 2025 · similarity 0.91)
- Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.90)
- Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up (ICML 2025 · similarity 0.89)
- Federated Learning with Sample-level Client Drift Mitigation (AAAI 2025 · similarity 0.89)
- Momentum Benefits Non-iid Federated Learning Simply and Provably (ICLR 2024 · 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.