PaperlayerView exact revision on arXiv

Source-linked AI summary

Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning

Haibo Yang, Minghong Fang, Jia Liu

arXiv:2101.11203v3cs.LGcs.DC

TL;DR

Whether federated learning can achieve linear convergence speedup with non-i.i.d. data and partial worker participation remains an open question. This paper analyzes generalized FedAvg with two-sided learning rates and shows linear speedup under both full and partial participation.

  • Problem

    Whether linear convergence speedup is achievable with non-i.i.d. worker data and partial participation remains an open question.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes generalized FedAvg with two-sided learning rates, in which workers perform local SGD steps and a server aggregates their updates.

    Source: §3 · p. 4

  • Results

    Generalized FedAvg achieves linear convergence speedup on non-i.i.d. data under both full and partial worker participation.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    With suitable hyperparameters, local steps could help convergence, and the maximum number of local steps is improved to K ≤ T/m.

    Source: §4 · p. 7, §6 · p. 9

    The analysis assumes every enlisted worker is available to participate, while practical worker availability and sampling schemes need further investigation.

    Source: §4 · p. 7

Abstract

from arXiv · show

Federated learning (FL) is a distributed machine learning architecture that leverages a large number of workers to jointly learn a model with decentralized data. FL has received increasing attention in recent years thanks to its data privacy protection, communication efficiency and a linear speedup for convergence in training (i.e., convergence performance increases linearly with respect to the number of workers). However, existing studies on linear speedup for convergence are only limited to the assumptions of i.i.d. datasets across workers and/or full worker participation, both of which rarely hold in practice. So far, it remains an open question whether or not the linear speedup for convergence is achievable under non-i.i.d. datasets with partial worker participation in FL. In this paper, we show that the answer is affirmative. Specifically, we show that the federated averaging (FedAvg) algorithm (with two-sided learning rates) on non-i.i.d. datasets in non-convex settings achieves a convergence rate $\mathcal{O}(\frac{1}{\sqrt{mKT}} + \frac{1}{T})$ for full worker participation and a convergence rate $\mathcal{O}(\frac{\sqrt{K}}{\sqrt{nT}} + \frac{1}{T})$ for partial worker participation, where $K$ is the number of local steps, $T$ is the number of total communication rounds, $m$ is the total worker number and $n$ is the worker number in one communication round if for partial worker participation. Our results also reveal that the local steps in FL could help the convergence and show that the maximum number of local steps can be improved to $T/m$ in full worker participation. We conduct extensive experiments on MNIST and CIFAR-10 to verify our theoretical results.

1 INTRODUCTION

The introduction asks whether linear convergence speedup is possible in federated learning with non-i.i.d. data and partial worker participation, and answers yes for FedAvg with two-sided learning rates. It also highlights larger local-step budgets and the potential for local steps to aid convergence.

1 INTRODUCTION

  • FL faces data heterogeneity because workers’ locally generated data distributions can differ, unlike the i.i.d. data often assumed in conventional distributed learning.The introduction identifies this non-i.i.d. setting as a challenge for FL algorithm design and performance analysis.Source: §1 · p. 1
  • Workers may join or leave across rounds, so the active set varies and servers may select only a subset rather than wait for stragglers.The introduction describes this as time-varying partial worker participation.Source: §1 · p. 2
  • FedAvg with two-sided learning rates achieves O(1/sqrt(mKT) + 1/T) with full participation and O(sqrt(K)/sqrt(nT) + 1/T) with partial participation on non-i.i.d. data.For sufficiently large T, the paper says these rates yield linear convergence speedup; its proof does not require bounded gradients.Source: §1 · pp. 2–3
  • Unlike SCAFFOLD, the proposed approach does not require extra variance-reduction operations, which the introduction says increase communication costs and implementation complexity.The proof also does not require the bounded-gradient assumption.Source: §1 · p. 2
  • With full worker participation and a proper learning-rate choice, local steps help rather than hurt convergence, and K can be as large as T/m for linear speedup.The paper says this improves on the T^(1/3)/m bound previously shown by Yu et al. (2019a) and Karimireddy et al. (2019), while more local steps can reduce communication overhead.Source: §1 · p. 2

2 RELATED WORK

Prior convergence analyses largely assume i.i.d. data or full worker participation; this paper addresses the remaining gap by showing linear speedup is achievable with non-i.i.d. data and partial participation, without extra requirements.

2 RELATED WORK

  • Earlier i.i.d., full-participation LocalSGD analyses achieve linear speedup, while LocalSGD is also reported as communication-efficient with better generalization.FedAvg was introduced by McMahan et al. (2016); the cited LocalSGD work includes Stich (2018), Yu et al. (2019b), and others.Source: §2 · p. 3
  • For non-i.i.d. data with full participation, prior works achieve linear speedup, though their convergence bounds could be improved.The cited works include Stich et al. (2018), Yu et al. (2019a), Wang & Joshi (2018), Karimireddy et al. (2019), and Reddi et al. (2020).Source: §2 · p. 4
  • With partial participation, Li et al. (2019b) obtain O(K/T) for strongly convex functions, while Karimireddy et al. (2019) analyze generalized FedAvg across convexity settings; neither establishes linear speedup for non-i.i.d. data.The passage says Li et al.'s result suggests local SGD steps slow convergence in original FedAvg.Source: §2 · p. 4
  • SCAFFOLD achieves linear speedup but requires extra variance-reduction operations, increasing communication costs and implementation complexity; this paper achieves linear speedup without those extra requirements.The passage also notes that multiple works heuristically demonstrate FedAvg variants on non-i.i.d. data.Source: §2 · p. 4

3 LINEAR SPEEDUP OF THE GENERALIZED FEDAVG WITH TWO-SIDED LEARNING RATES FOR NON-IID DATASETS

The section analyzes generalized FedAvg with separate worker and server learning rates, establishing convergence guarantees for non-i.i.d. data under full and partial worker participation.

3 LINEAR SPEEDUP OF THE GENERALIZED FEDAVG WITH TWO-SIDED LEARNING RATES FOR NON-IID DATASETS

  • Generalized FedAvg lets workers take K local SGD steps and sends their accumulated parameter differences for server aggregation with a separate global learning rate.Original FedAvg is a special case with server-side learning rate one.Source: §3 · p. 4
  • The analysis assumes Lipschitz-continuous gradients and bounded local and global variance, with global variance measuring non-i.i.d. heterogeneity; it does not require bounded gradients.A global variance of zero corresponds to i.i.d. data.Source: §3 · p. 5

3.1 CONVERGENCE ANALYSIS FOR FULL WORKER PARTICIPATION

  • O(1/sqrt(mKT) + 1/T) convergence is achieved with full participation when T ≥ mK, allowing K up to T/m local steps.The bound requires the local learning rate to decrease inversely with K; the improved local-step limit can reduce communication overhead.Source: §3.1 · pp. 5–6
  • Under full participation, the i.i.d. case has a bound with a 1/(TK) term in addition to 1/sqrt(mKT), improving the first term over prior work.This follows when the heterogeneity variance σG is zero.Source: §3.1 · p. 6

3.2 CONVERGENCE ANALYSIS FOR PARTIAL WORKER PARTICIPATION

  • Partial participation samples n workers uniformly with or without replacement, and the same convergence rate holds when at least n workers participate per round.The stated analysis presents rounds with exactly n participants for readability, while allowing |St| ≥ n.Source: §3.2 · pp. 6–7
  • O(sqrt(K)/sqrt(nT) + 1/T) convergence is achieved under partial participation with proper learning rates.Uniform worker sampling with or without replacement preserves the convergence order, though fewer participating workers and random sampling amplify the variance.Source: §3.2 · pp. 6–7

4 DISCUSSION

The discussion explains how two-sided learning rates enable linear speedup despite non-i.i.d. data, and highlights the effects of local steps, worker participation, and sampling. It also notes that practical participation may be constrained by worker availability.

Convergence Rate

  • With proper hyperparameters, generalized FedAvg with two-sided learning rates achieves O(1/sqrt(mKT)) convergence and linear speedup.The constant term is driven by local variance, global variability, and K, with the total global variability across K steps dominating; choosing ηL inversely with K makes it controllable.Source: §4 · p. 7

Number of Local Steps

  • With proper hyperparameters, local steps can aid convergence, and the maximum number can reach K ≤ T/m, though whether they help or hurt merits further investigation.The paper notes that other results report slower convergence with local steps.Source: §4 · p. 7

Number of Workers

  • Increasing workers per communication round improves convergence; under uniform sampling, their collective data distribution approximates the overall distribution in expectation.For non-i.i.d. data, more sampled workers provide a better approximation to the distribution across all workers.Source: §4 · p. 7

Worker Availability

  • The analysis assumes enlisted workers are available, but practical participation may require charging or idle states, making sampling and enlistment design important.The joint design of sampling schemes and generalized FedAvg is identified as a topic for further investigation.Source: §4 · p. 7

5 NUMERICAL RESULTS

Experiments use logistic regression, 2NN, and CNN on non-i.i.d. MNIST, plus ResNet on CIFAR-10; MNIST is partitioned across 100 workers by digit, with 10 workers per round for partial participation. The results examine data heterogeneity, worker participation, local steps, and comparison with SCAFFOLD.

Impact of non-i.i.d. datasets

  • With proper learning rates, generalized FedAvg converged across non-i.i.d. MNIST settings, but increasing heterogeneity slowed convergence and reduced test accuracy.For digits_5, convergence speed was comparable to digits_10; the degradation from digits_10 to digits_1 was more pronounced with partial participation.Source: §5 · p. 8, Figure 1 · p. 8

Impact of worker number

  • Partial participation caused zigzagging, slower convergence than full participation, and greater difficulty on highly non-i.i.d. data.Random sampling can leave active workers with only a subset of the ten MNIST digits, so their data may not represent the overall distribution.Source: §5 · p. 8, Figure 1 · p. 8

Impact of local steps

  • Local steps helped convergence under both full and partial participation, unlike the harm reported by Li et al. (2019b) on unbalanced non-i.i.d. MNIST.The authors suggest the earlier result may reflect the combined effect of data imbalance and local steps rather than local steps alone.Source: Figure 1 · p. 8, §5 · p. 9

Comparison with SCAFFOLD

  • On non-i.i.d. CIFAR-10, SCAFFOLD used more than 1.5 times FedAvg’s communication cost and wall-clock time, despite needing slightly fewer rounds to reach 75% accuracy.On MNIST, FedAvg was similar to or outperformed SCAFFOLD; the comparison used digits_2 and digits_10 datasets.Source: Table 2 · p. 9, §5 · p. 9

6 CONCLUSIONS AND FUTURE WORK

The generalized FedAvg algorithm with two-sided learning rates achieves linear speedup under full and partial worker participation on non-i.i.d. data. The analysis also improves the maximum local-step count and identifies open questions for future work.

6 CONCLUSIONS AND FUTURE WORK

  • The generalized FedAvg algorithm achieves linear speedup for convergence with full and partial worker participation on non-i.i.d. datasets.The analysis covers general non-convex optimization.Source: §6 · p. 9
  • The analysis shows that local steps can help convergence and improves the maximum number of local steps to T/m.Source: §6 · p. 9
  • Future work includes optimal sampling for partial participation and handling participant sets that vary in size and membership across communication rounds.Source: §6 · p. 9

A APPENDIX I: PROOFS

Appendix I provides detailed proofs for full and partial worker participation.

A APPENDIX I: PROOFS

A.1 PROOF OF THEOREM 1

The proof derives an expected descent bound for full-participation FedAvg by using smoothness to bound two terms, then rearranges and sums the bound over communication rounds. The argument assumes Assumptions 1–3 and imposes upper bounds on the local and global learning rates.

A.1 PROOF OF THEOREM 1

  • With full worker participation and learning rates satisfying ηL ≤ 1/(8LK) and ηηL ≤ 1/(KL), Theorem 1 applies under Assumptions 1–3.The theorem concerns the sequence of outputs generated by Algorithm 1.Source: §A.1 · p. 12
  • By smoothness in Assumption 1, the proof takes expectation of f(xt+1) over randomness at communication round t; it bounds A2 using bounded variance and independence of zero-mean terms.Source: §A.1 · pp. 12–13
  • After substituting the A1 and A2 bounds, the proof rearranges the inequality and sums it from t = 0 to T − 1.The displayed derivation notes that its coefficients satisfy the required conditions under the theorem’s learning-rate bounds.Source: §A.1 · p. 13

A.2 PROOF OF THEOREM 2 · A.2.1 KEY LEMMAS · A.3 AUXILIARY LEMMAS

The appendix proves Theorem 2’s convergence guarantees for partial worker participation under two sampling strategies, supported by lemmas on estimator unbiasedness and step-size behavior.

A.2 PROOF OF THEOREM 2

  • Theorem 2 establishes convergence guarantees under partial worker participation for Algorithm 1 with constant learning rates, under Assumptions 1–3.The supplied passages omit the displayed bounds, so no convergence-rate expression is reported here.Source: §A.2 · pp. 14, 16, 19
  • Theorem 2’s proof accounts for randomness from both worker sampling and stochastic gradients.The proof uses Et to denote expectation over both sources of randomness.Source: §A.2 · p. 14
  • The same convergence rate remains guaranteed when each round includes at least n workers, rather than exactly n.This relaxation is stated for both sampling strategies.Source: §A.2 · pp. 16, 18
  • Both independent sampling with replacement and equal-probability sampling without replacement yield convergence guarantees under their respective step-size conditions.The proof treats the two strategies separately and derives a convergence result for each.Source: §A.2 · pp. 16, 19

A.2.1 KEY LEMMAS

  • For both sampling strategies, Lemma 1 shows that the estimator ∆t is unbiased.The lemma’s proof notes that the sampling distributions are identical across the two strategies.Source: §A.2.1 · p. 19

A.3 AUXILIARY LEMMAS

  • Under ηL ≤ 1/(8LK), the auxiliary lemma restated from Reddi et al. (2020) supplies a bound used in the proof.The appendix restates that lemma’s proof to make the paper self-contained.Source: §A.3 · p. 19

B APPENDIX II: EXPERIMENTS

Appendix II provides experimental details for experiments using non-i.i.d. versions of MNIST and CIFAR-10.

B APPENDIX II: EXPERIMENTS

  • The experiments use non-i.i.d. versions of MNIST and CIFAR-10.The appendix says it provides the full experimental details, but the supplied passage does not include those details.Source: B APPENDIX II: EXPERIMENTS · p. 20

B.1 MNIST · B.2 CIFAR-10

The experiments evaluate MNIST under controlled degrees of label heterogeneity and CIFAR-10 under i.i.d. and non-i.i.d. client partitions, using multiple model architectures and specified training settings.

B.1 MNIST

  • MNIST experiments classify handwritten digits 0–9 using a modified non-i.i.d. dataset.The passage describes the task and dataset modification but provides no outcome values.Source: §B.1 · p. 20
  • With 100 workers, MNIST heterogeneity is varied by giving each worker samples from p digit classes, from p = 1 to the essentially i.i.d. p = 10 case.Workers receive the same number of training and test samples; local datasets are split by digit class.Source: §B.1 · p. 20
  • Each MNIST round runs K local epochs in parallel before the server samples n workers for aggregation, with hyperparameters grid-searched as shown in Table 3.Table 3 is identified as the hyperparameter-tuning table; its values are not supplied.Source: §B.1 · p. 20, Table 3 · p. 20
  • MNIST is evaluated with multinomial logistic regression, a two-hidden-layer 2NN, and a CNN; results are reported in Figures 2–4.The 2NN has two 200-neuron ReLU hidden layers followed by an output layer; Table 4 is identified as the CNN architecture table.Source: §B.1 · p. 20, Table 4 · p. 20

B.2 CIFAR-10

  • For CIFAR-10, the default server and client learning rates are η = 1.0 and ηL = 0.1, with K = 10 local epochs, 100 clients, and n = 10 clients per round.These are stated as the default settings unless otherwise noted.Source: §B.2 · p. 20
  • CIFAR-10 i.i.d. data are evenly divided across clients, while non-i.i.d. data are label-sorted into 200 shards of 250 examples, with two randomly assigned per client.The cited passage attributes this distribution strategy to McMahan et al. (2016).Source: §B.2 · p. 20
  • CIFAR-10 classifiers use a ResNet model, with results shown in Figures 5 and 6.The supplied passage identifies the model and figures but gives no result values.Source: §B.2 · p. 20

B.3 DISCUSSION

The discussion finds that non-i.i.d. data and partial participation can hinder FedAvg convergence, while local steps help only slightly. It also describes a communication-versus-computation tradeoff between SCAFFOLD and generalized FedAvg.

Impact of non-i.i.d. datasets

  • FedAvg converges on non-i.i.d. data with a proper learning rate, but increasing data skew raises training loss, lowers test accuracy, and destabilizes convergence, especially for CNNs.With p = 5, convergence is comparable to the i.i.d. case p = 10.Source: §B.3 · p. 21, Figure 2 · p. 21

Impact of worker number

  • Partial participation adds sampling randomness, causing zigzagging and slower convergence because sampled workers may not represent system heterogeneity, especially with highly non-i.i.d. data.With p = 1 and 10 workers per round, active workers may cover only 4 or 5 digits; CIFAR-10 shows a dramatic test-accuracy drop.Source: §B.3 · pp. 21–23, Figure 5 · p. 22
  • In practice, worker states affect availability, so sampling and enlistment require care; joint design of sampling, worker count, and FedAvg remains future work.The experiments use random sampling with equal probability without replacement.Source: §B.3 · p. 23

Impact of local steps

  • Local steps help convergence under both full and partial participation, but their effect is slight compared with non-i.i.d. data and worker count.The discussion draws on MNIST results under both participation regimes and CIFAR-10 results.Source: Figure 3 · p. 21, Figure 4 · p. 22, Figure 6 · p. 22

Comparison with SCAFFOLD

  • At 75% test accuracy, SCAFFOLD uses fewer communication rounds and less computation time than generalized FedAvg, but communicates twice as much, prolonging communication time.The comparison uses the same NVIDIA V100 GPU and assumes 20 MB/s bandwidth for uploading and downloading.Source: Figure 7 · p. 23, §B.3 · p. 23

Related papers

Loading 2101.11203v3…