PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of FedAvg on Non-IID Data

Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, Zhihua Zhang

arXiv:1907.02189v4stat.MLcs.LGmath.OC

TL;DR

FedAvg lacks convergence guarantees when federated data are non-IID and device participation is incomplete. This paper analyzes such settings and shows that heterogeneity and partial participation slow convergence, while fixed learning rates can leave the solution Ω(η(E −1)) from optimal.

  • Problem

    FedAvg lacked convergence guarantees without IID data and full device participation, despite inactive devices making universal participation impractical.

  • Method

    The paper analyzes FedAvg under strongly convex and smooth objectives with non-IID data, partial participation, and different averaging schemes.

  • Results

    Fixed learning rate η leaves FedAvg with E > 1 at least Ω(η(E −1)) from the optimum, while heterogeneity and partial participation slow convergence.

  • Takeaways & Limitations

    The number of local updates E must be tuned because both overly small and overly large values can worsen the convergence rate.

  • Takeaways & Limitations

    The analysis is constrained to convex problems, and diminishing step sizes can hinder fast convergence despite enabling the required learning-rate decay.

Abstract

from arXiv · show

Federated learning enables a large amount of edge computing devices to jointly learn a model without data sharing. As a leading algorithm in this setting, Federated Averaging (\texttt{FedAvg}) runs Stochastic Gradient Descent (SGD) in parallel on a small subset of the total devices and averages the sequences only once in a while. Despite its simplicity, it lacks theoretical guarantees under realistic settings. In this paper, we analyze the convergence of \texttt{FedAvg} on non-iid data and establish a convergence rate of $\mathcal{O}(\frac{1}{T})$ for strongly convex and smooth problems, where $T$ is the number of SGDs. Importantly, our bound demonstrates a trade-off between communication-efficiency and convergence rate. As user devices may be disconnected from the server, we relax the assumption of full device participation to partial device participation and study different averaging schemes; low device participation rate can be achieved without severely slowing down the learning. Our results indicate that heterogeneity of data slows down the convergence, which matches empirical observations. Furthermore, we provide a necessary condition for \texttt{FedAvg} on non-iid data: the learning rate $η$ must decay, even if full-gradient is used; otherwise, the solution will be $Ω(η)$ away from the optimal.

1 INTRODUCTION

This paper establishes theoretical convergence guarantees for FedAvg on strongly convex and smooth problems without assuming iid data or full device participation. It shows that communication, sampling, averaging, data heterogeneity, and learning-rate decay govern convergence quality.

  • Contributions: E controls convergence: setting E = 1 reduces FedAvg to SGD, while either excessively small or large E is unfavorable.Thus, local computation creates a trade-off between communication efficiency and convergence rate.
  • Contributions: Data heterogeneity and partial device participation slow FedAvg convergence, as confirmed by numerical experiments.These settings reflect practical federated-learning conditions involving nonrepresentative local data and unavailable devices.
  • Contributions: FedAvg achieves an O(1/T) convergence rate for strongly convex and smooth problems without iid-data or full-participation assumptions.The paper presents this as the first convergence guarantee under both relaxed assumptions.
  • Contributions: Suitable sampling and averaging schemes are crucial, and certain schemes achieve O(1/T) convergence under non-iid data.The work summarizes existing schemes and proposes a new one, while allowing partial device participation.
  • Contributions: For E > 1, learning-rate decay is necessary: with fixed η, FedAvg converges at least Ω(η(E −1)) away from the optimum, even under full gradient descent.The necessity result is established using a specific ℓ2-regularized linear regression construction.

2 FEDERATED AVERAGING (FEDAVG)

This section formulates federated optimization over weighted device-local objectives and describes FedAvg’s broadcast, local-update, and aggregation procedure. It contrasts IID assumptions with realistic non-IID and partial-participation settings, and specifies the resulting communication pattern.

  • Problem formulation: FedAvg models N devices with nonnegative weights p_k summing to one and device-specific local objectives defined from local training data.The k-th device holds n_k examples, and its objective uses a user-specified loss function.
  • Algorithm description: Each round broadcasts the latest global model, performs local stochastic updates on devices, and aggregates their resulting local models into a new global model.The aggregation can vary because of non-IID data and partial device participation.
  • IID versus non-iid: FedAvg avoids the IID assumption D_k = D for all k, instead allowing device data distributions whose overall distribution is the mixture D = ∑_k p_kD_k.The section identifies this as one of the paper’s theoretical contributions because real-world applications typically do not satisfy IID data assumptions.
  • Partial device participation: Partial participation sets a threshold K, aggregates the first K responded devices, and treats devices K + 1 through N as stragglers in that iteration.The selected-device weights sum to one in expectation, making the strategy more realistic when devices are offline or slow.
  • Communication cost: ⌊2T/E⌋ communications are required for T iterations, with one broadcast and one aggregation round per E iterations.The broadcast sends the global model to devices, while aggregation returns device outputs to the server.

3 CONVERGENCE ANALYSIS OF FEDAVG IN NON-IID SETTING

FedAvg achieves O(1/T) convergence for strongly convex, smooth objectives on non-IID data when local updates, sampling, and averaging are appropriately controlled. Partial participation remains convergent under alternative schemes, while heterogeneity constrains local-update counts and weakens dependence on participation.

  • Convergence guarantees: O(1/T) convergence holds for FedAvg on strongly convex, smooth functions with non-IID data when sufficiently small learning rates make local updates resemble an SGD step.The analysis assumes smoothness, strong convexity, bounded stochastic-gradient variance, and bounded expected squared gradient norms.
  • Partial participation: Partial device participation preserves the convergence bound under probability-based sampling with replacement and uniform sampling without replacement, but the latter requires balanced data.The two schemes use different aggregation conditions and constants in their respective theorems.
  • Choice of E: The communication cost as a function of E first decreases and then increases, so both overly small and overly large local-update counts can be inefficient.An optimal E therefore exists for communication efficiency.
  • Choice of E: E must not exceed Ω(…) in the non-IID setting; otherwise convergence is not guaranteed because excessive local updates can reduce FedAvg to one-shot averaging of local minimizers.The passages contrast this with the IID setting, where E can be set to O(…).
  • Choice of K: Under non-IID data, convergence depends only weakly on K, so FedAvg lacks linear speedup and the participation ratio K/N can be kept small without affecting the convergence rate.This can alleviate straggler effects.
  • Choice of sampling schemes: Non-uniform probability sampling converges faster than uniform sampling, especially when device probabilities are highly non-uniform, whereas large ν and small ς make convergence slow.Scheme I is preferred when the system can choose active devices; otherwise uniform sampling with Theorem 3 provides convergence guarantees.

4 NECESSITY OF LEARNING RATE DECAY

For non-IID FedAvg with more than one local step, diminishing learning rates are necessary for convergence: any fixed step size can leave the method at sub-optimal points. This necessity is specific to FedAvg’s biased local updates and motivates more communication-efficient alternatives.

  • Theorem 4: With full batch size, E > 1, and any fixed step size, FedAvg converges to sub-optimal points on a strongly convex and smooth constructed problem.The result is established using a ridge regression model.
  • Implications: Learning-rate decay is necessary: with E > 1, decaying rates can reach the optimum, whereas any fixed rate cannot.The contrast follows from Theorems 1 and 4.
  • Implications: FedAvg differs from gradient descent because E = 1 with full batches is exact full gradient descent, while E > 1 cannot converge under fixed learning rates.Proper fixed-rate full gradient descent is globally convergent, unlike multi-step FedAvg in this setting.
  • Implications: Constant learning rates preserve bias from possibly biased local updates, whereas diminishing rates can gradually eliminate that bias.Thus, the need for decay is inherent to FedAvg rather than an artifact of the analysis.
  • Implications: Diminishing step sizes may hinder fast convergence and offset FedAvg’s communication savings from performing multiple local updates before synchronization.Theorem 4 therefore motivates more efficient alternatives to FedAvg.

5 RELATED WORK

Prior federated-learning research emphasized communication efficiency and privacy, while FedAvg studies on non-IID data lacked convergence-rate guarantees. Related LocalSGD and LocalGD analyses provide stronger results under additional assumptions, but fixed learning rates leave solutions away from optimality.

  • Federated learning: Federated-learning research has focused on communication efficiency and data privacy, while this work targets communication efficiency.FL was proposed for collaborative model learning without collecting users’ data.
  • FedAvg: FedAvg was proposed as an effective synchronous distributed-optimization heuristic, but prior non-IID analyses did not provide convergence rates.Asynchronous FedAvg analysis did not guarantee convergence to a saddle point or local minimum.
  • LocalSGD: Under iid data and full device activity, FedAvg becomes LocalSGD, whose simpler analysis establishes linear speedup with less communication for strongly-convex stochastic optimization.Other work studied LocalSGD in non-convex and heterogeneous settings, including O(1/NT) convergence.
  • LocalGD: For LocalGD on non-iid data, a fixed learning rate yields convergence only to a point O(η2E2) away from optimal, while this work lower-bounds the distance by Ω((E −1)η).The paper attributes the suboptimality to the fixed learning rate.

6 NUMERICAL EXPERIMENTS

Numerical experiments evaluate FedAvg on non-IID MNIST and synthetic data under controlled SGD and learning-rate-decay settings. They show a communication–convergence trade-off with local steps, limited sensitivity to active-device counts, and scheme-dependent performance under balanced versus unbalanced data.

  • Models and datasets: Experiments use logistic regression with weight decay λ = 1e−4 on MNIST distributed across N = 100 workers, each holding samples from only two digits.Both balanced and highly unbalanced MNIST variants are evaluated.
  • Experiment settings: Each round, selected devices perform E parallel SGD steps from w0 = 0, while the learning rate decays as ηt = η0/(1+t) with η0 ∈ {1, 0.1, 0.01}.Models are evaluated after each global synchronization under matched activated-device randomness.
  • Impact of E: Increasing E first reduces and then increases the communication rounds required for a target accuracy on unbalanced datasets.Small E increases communication burden, whereas large E lowers convergence speed, creating a trade-off between communication efficiency and convergence.
  • Impact of K: K has limited influence on FedAvg convergence in Synthetic(0,0), although sufficiently large K produces a slightly better curve.Similar behavior is reported on the other three datasets; small device counts are viable when sampling variance is not too large.
  • Effect of sampling and averaging schemes: On balanced data, Schemes I and II perform nearly identically and both outperform the original scheme, while on unbalanced data Scheme I performs best.The comparison covers four schemes across four federated datasets.

7 CONCLUSION

The paper studies FedAvg’s convergence in federated learning, examining sampling and averaging schemes. It provides theoretical guarantees for two schemes and empirical evidence that informs algorithm design.

  • 7 CONCLUSION: The paper studies the convergence of FedAvg, a heuristic algorithm suited to federated learning.This work aims to strengthen theoretical understanding of FedAvg.
  • 7 CONCLUSION: The analysis investigates the influence of sampling and averaging schemes.The paper provides theoretical guarantees for two schemes.
  • 7 CONCLUSION: The paper empirically demonstrates the performances of the investigated schemes and provides insights for realistic algorithm design.These results contribute to theoretical understanding of FedAvg.

A PROOF OF THEOREM 1 … B.1 ADDITIONAL NOTATION

The appendices prove FedAvg convergence by introducing notation for synchronized and local updates, establishing lemmas on SGD progress, variance, and device divergence, and completing an induction-based proof. They then extend the analysis to partial participation using sampled device sets, an updating-scheme construction, and separate randomness accounting.

  • A PROOF OF THEOREM 1: Full device participation is analyzed first as the setting for Theorem 1’s proof.
  • A.1 ADDITIONAL NOTATION: FedAvg notation distinguishes global synchronization steps, immediate one-step SGD results, and parameters obtained after communication.Synchronization steps are defined as IE = {nE | n = 1, 2, · · · }, with all devices activated at communication times in the full-participation setting.
  • A.2 KEY LEMMAS: Three key lemmas bound one-step SGD results, stochastic-gradient variance, and divergence among device parameters under stated stepsize assumptions.Lemma 1 assumes ηt ≤ 1 4L; Lemma 3 additionally assumes ηt is non-increasing and ηt ≤2ηt+E.
  • A.3 COMPLETING THE PROOF OF THEOREM 1: Theorem 1 is completed by combining the lemmas and proving an inductive bound for Δt under a diminishing stepsize.The proof uses ηt = β t+γ for some β > 1 and verifies the required stepsize relation.
  • A.4 DEFERRED PROOFS OF KEY LEMMAS: The deferred proofs derive the bounds using smoothness, strong convexity, variance control, and the E-step communication interval.They define γt = 2ηt(1 −2Lηt) and use ηt ≤ 1 4L, while bounding stochastic-gradient variance by σ2.
  • B PROOFS OF THEOREMS 2 AND 3: Partial device participation is analyzed separately, with FedAvg randomly activating a subset of devices at communication times.
  • B.1 ADDITIONAL NOTATION: Sampling notation represents with-replacement selections as multisets and defines St as the most recent selected device set.With-replacement schemes may activate a device several times in one communication round.
  • B.1 ADDITIONAL NOTATION: FedAvg’s partial-participation analysis uses an all-device thought construction, while distinguishing stochastic-gradient randomness from device-sampling randomness.The construction samples a random multiset St and updates only sampled devices; ESt(·) denotes expectation over sampling randomness.

B.2 KEY LEMMAS … C.3 SOME PROPERTIES OF THE EXAMPLE

The paper establishes unbiased partial-participation schemes and bounded-variance lemmas for FedAvg, then uses them to complete convergence proofs. A constructed sparse, balanced but non-identically distributed regression example shows that constant-step FedAvg can remain suboptimal, while learning-rate decay can restore optimality.

  • B.2 KEY LEMMAS: Two sampling and averaging schemes satisfy the required unbiasedness condition and provide convergence guarantees under partial device participation.Scheme I samples with replacement using probabilities p1, …, pN; Scheme II samples uniformly without replacement.
  • B.2 KEY LEMMAS: The original McMahan et al. (2017) scheme is not unbiased, so the analysis does not cover it.The original scheme is similar to Scheme II but uses a different averaging scheme.
  • B.3 COMPLETING THE PROOF OF THEOREM 2 AND 3: Unbiasedness makes term A3 vanish, while wt+1 = vt+1 eliminates A1 outside communication times; Lemma 5 controls the remaining terms.At communication times, Lemma 5 also bounds A1.
  • B.3 COMPLETING THE PROOF OF THEOREM 2 AND 3: The completed proofs use diminishing stepsizes ηt = β/(t+γ), with β > 1/µ, γ > 0, η1 ≤ 1/(4L), and ηt ≤ 2ηt+E.The argument follows the same structure as the earlier theorem proof, with an additional C term.
  • B.4 DEFERRED PROOFS OF KEY LEMMAS: The deferred proofs establish Lemma 4 through identical sampling distributions and Lemma 5 through separate variance arguments for the two schemes.The variance proof uses independence and unbiasedness where applicable, plus the non-increasing-step-size condition.
  • C.1 DETAIL OF THE EXAMPLE: With exact gradients, constant small η and E > 1 make FedAvg converge to a suboptimal solution, whereas E = 1 converges to the optimum.The example distributes sparse local quadratic objectives across devices and interprets the resulting problem as distributed linear regression.
  • C.2 NUMERICAL ILLUSTRATION ON THE EXAMPLE: The numerical illustration sets N = 5, p = 4, and µ = 2 × 10^-4, and shows that learning-rate annealing can recover optimality even when E > 1.The annealing parameter a is selected from {10^-2, 10^-4, 10^-6}.

C.4 PROOF OF THEOREM 5. · C.5 PROOF OF LEMMA 6 · D EXPERIMENTAL DETAILS

The proof establishes convergence under deterministic, synchronized local updates and characterizes how the number of local SGD steps E affects the limit. It then proves that the nonzero error for E>1 is quantitatively unavoidable when η is sufficiently small.

  • C.4 PROOF OF THEOREM 5.: Theorem 5 assumes equal data sizes, parallel local updates, a shared learning rate η, and full-local-dataset gradients, making the analysis deterministic.The proof first treats the case μ = 0.
  • C.4 PROOF OF THEOREM 5.: For η < 1/4, the proof shows the global iterates form a Cauchy sequence and converge to a limit ew∗.This follows from bounding the update operators and showing their relevant quadratic forms decrease with E.
  • C.4 PROOF OF THEOREM 5.: When E = 1, FedAvg converges to the optimum, with ew∗ = A−1b = w∗.The proof identifies this exact recovery directly from equation (28).
  • C.4 PROOF OF THEOREM 5.: For E > 1, the limiting point ew∗ differs from w∗, so local updates can produce a nonzero optimization error.The proof states that the right-hand side of equation (29) cannot be zero.
  • C.5 PROOF OF LEMMA 6: Lemma 6 gives a nonvacuous lower bound on this error for sufficiently small η when A1A2 ≠ 0 and w∗ is dense.The nonvacuity condition is stated explicitly after the lemma’s bound.
  • C.4 PROOF OF THEOREM 5.: For μ > 0, the proof replaces Ai with Ai + μI and adjusts the step-size condition, while leaving the analysis across E unchanged.The argument assumes μ < 1/(4+μ) in the strongly convex case.
  • C.5 PROOF OF LEMMA 6: The Lemma 6 proof analyzes the η-sufficiently-small regime using Θ(f(η)) matrix bounds and inequalities derived from 0 < ∥A∥ ≤ 4.It combines expansions from equations (31) and (29), using ∥A−1x∥ ≥ 1/4∥x∥.

D.1 EXPERIMENTAL SETTING

The experiments test the theory on multinomial logistic regression using heterogeneous real and synthetic federated datasets, with controlled initialization, participation, and learning-rate decay.

  • Model and loss: The model is multinomial logistic regression with softmax predictions and a convex objective regularized by λ = 10^-4.The parameter is w = (W, b), with predictions f(w; x_i) = softmax(Wx_i + b).
  • Datasets: MNIST data are distributed across N = 100 devices, each containing samples from only two digits, with device sample counts varied to study imbalance.The experiments use real data and impose statistical heterogeneity through label-restricted device partitions.
  • Datasets: Synthetic data manipulate heterogeneity through α and β in Gaussian parameter and feature-generation distributions.The setup uses x ∈ R60, W_k ∈ R10×60, and b_k ∈ R10, with α and β controlling heterogeneity more precisely.
  • Experiments: All runs initialize with w_0 = 0, selected devices perform E parallel SGD steps per round, and the learning rate decays as η_t = η_0/(1+t).η_0 is selected from {1, 0.1, 0.01}, and models are evaluated after each global synchronization.
  • Experiments: Experiments control randomness so the activated-device set is identical across comparisons.This supports fair comparison of the evaluated averaged models on the corresponding global objective.

D.2 THEORETICAL VERIFICATION

The theoretical verification identifies an optimal local-step count and predicts that greater data heterogeneity requires more communication. Experiments show convergence across device-participation levels, while Scheme I is stable and Scheme II can diverge on highly unbalanced data.

  • The impact of E: The required communication rounds first decrease and then increase with local steps E, implying an optimal local step E∗.At E∗, the theory evaluates the communication-round expression Tϵ/E.
  • The impact of E: More severe data heterogeneity requires more communication rounds for FedAvg.This conclusion follows directly from the theoretical communication-round analysis.
  • The impact of K: FedAvg converges for every tested device count K, with curves largely overlapping and larger K only slightly improving late-round behavior.Experiments fix E = 5 and η0 = 0.1 and use Scheme I across four datasets.
  • Sampling and averaging schemes: Scheme I performs stably and well across most experiments, consistent with its theoretical convergence guarantee in the common federated setting.Scheme I samples iid indices with replacement and averages models using weights pk.
  • Sampling and averaging schemes: Scheme II lacks a convergence guarantee on unbalanced data and may diverge when device sample counts differ substantially.On the two most unbalanced synthetic datasets, Scheme II fluctuates without convergence, while Transformed Scheme II converges more slowly than Scheme I.
Loading 1907.02189v4…