PaperlayerView exact revision on arXiv

Source-linked AI summary

FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning

Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, Gauri Joshi

arXiv:2207.14130v1cs.LG

TL;DR

Partial client participation is a comparatively under-addressed source of error in data-heterogeneous federated learning. FedVARP reuses clients’ latest updates at the server, while ClusterFedVARP uses clustered updates to reduce storage. The paper reports that FedVARP outperforms state-of-the-art methods and ClusterFedVARP performs comparably with much less storage.

  • Problem

    In data-heterogeneous federated learning, partial client participation contributes to convergence error but has received less attention than client drift.

    Source: §1 · pp. 1–2

  • Method

    FedVARP reuses each client’s most recent update at the server for clients absent from a round, while ClusterFedVARP stores unified updates for client clusters.

    Source: §1 · p. 2

  • Results

    FedVARP outperforms state-of-the-art methods, while ClusterFedVARP performs comparably with much less storage.

    Source: §1 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    The paper concludes that its algorithms consistently outperform existing baselines, with the clustering-based approach reducing variance while remaining storage-efficient.

    Source: §7 · p. 8

    The theoretical analysis assumes uniform client sampling; designing server aggregation for arbitrary client participation remains an open direction.

    Source: §1 · p. 2

Abstract

from arXiv · show

Data-heterogeneous federated learning (FL) systems suffer from two significant sources of convergence error: 1) client drift error caused by performing multiple local optimization steps at clients, and 2) partial client participation error caused by the fact that only a small subset of the edge clients participate in every training round. We find that among these, only the former has received significant attention in the literature. To remedy this, we propose FedVARP, a novel variance reduction algorithm applied at the server that eliminates error due to partial client participation. To do so, the server simply maintains in memory the most recent update for each client and uses these as surrogate updates for the non-participating clients in every round. Further, to alleviate the memory requirement at the server, we propose a novel clustering-based variance reduction algorithm ClusterFedVARP. Unlike previously proposed methods, both FedVARP and ClusterFedVARP do not require additional computation at clients or communication of additional optimization parameters. Through extensive experiments, we show that FedVARP outperforms state-of-the-art methods, and ClusterFedVARP achieves performance comparable to FedVARP with much less memory requirements.

1 INTRODUCTION

The paper identifies partial client participation as a dominant source of FedAvg error and proposes server-side variance reduction to address it. FedVARP outperforms existing state-of-the-art methods, while ClusterFedVARP offers comparable performance with less storage.

1 INTRODUCTION

  • Partial client participation can skew the global model toward participating clients’ data distributions, and its error has received less attention than client drift.The paper reports that partial participation, rather than client drift, dominates FedAvg’s convergence rate.Source: §1 · p. 2
  • FedVARP reduces partial-participation error by reusing each client’s most recent update at the server, including updates for clients absent from the current round.It leaves local SGD unchanged and requires no additional client computation or communication.Source: §1 · p. 2
  • ClusterFedVARP reduces storage by retaining one unified update per client cluster, and can reduce partial-participation error when within-cluster heterogeneity is sufficiently bounded.The approach relaxes FedVARP’s storage requirements.Source: §1 · p. 2
  • FedVARP outperforms state-of-the-art methods on vision and language modeling tasks, while ClusterFedVARP performs comparably with much less storage.The authors report these results from extensive experiments.Source: §1 · p. 2
  • The theoretical analysis assumes uniform client sampling, although the algorithms can also be combined with non-uniform and biased sampling strategies.The authors identify server aggregation for arbitrary client participation as an open direction.Source: §1 · p. 2

2 PROBLEM SETUP

The paper formulates federated learning as minimizing a global objective composed of clients’ local objectives and describes FedAvg’s sampled-client local-SGD updates. Its convergence analysis decomposes error into stochastic-gradient, partial-participation, and client-drift sources, finding partial participation dominant under the stated setting.

2 PROBLEM SETUP

  • The global objective is a finite sum of local client objectives, each defined as expected loss over samples from that client’s data distribution.The formulation can be extended to unequally weighted client objectives.Source: §2 · p. 2
  • FedAvg samples clients each round, sends them the global model, and aggregates their local-SGD updates to update that model.Selected clients perform τ local steps; the analysis models sampling as uniform and without replacement.Source: §2 · pp. 2–3, §2.1 · p. 3
  • Randomly sampling clients amid data heterogeneity introduces variance that the paper terms partial participation error.The convergence analysis assumes smooth local objectives, unbiased stochastic gradients with bounded local variance, and bounded global variance.Source: §2 · p. 3, §2.1 · p. 3

2.1 CONVERGENCE ANALYSIS OF FEDAVG

  • Full participation removes the partial-participation error term, whereas setting τ = 1 eliminates client drift.The error decomposition identifies stochastic-gradient error as a separate source.Source: §2.1 · p. 3
  • FedAvg’s convergence error comprises stochastic-gradient, partial-participation, and client-drift terms, with partial participation dominating under the paper’s stated practical learning-rate comparison.The authors attribute this dominance to the partial-participation term’s scaling and note that the client learning rate is usually much smaller than the server learning rate.Source: §2.1 · p. 3
  • The paper says methods targeting client drift do not directly extend to partial participation, and its proposed server-only update modification avoids extra client computation or communication.The authors state that eliminating partial-participation variance allows the same convergence rates as FedDyn and SCAFFOLD.Source: §2.1 · pp. 3–4

3 THE FEDVARP ALGORITHM AND ITS CONVERGENCE ANALYSIS

FedVARP reduces partial-participation variance by reusing clients’ latest observed updates in server aggregation, without changing client LocalSGD. Its convergence analysis removes the partial-participation error while retaining stochastic-gradient and client-drift errors.

3.1 PROPOSED FEDVARP ALGORITHM

  • FedVARP uses each participating client’s update and the server’s latest stored updates for nonparticipants to reduce partial-participation variance.The variance-reduction correction is applied globally at the server, without extra client computation or communication.Source: §3.1 · p. 4
  • Storing a latest update for every client requires O(Nd) server memory, which can be expensive in federated settings.The paper introduces ClusterFedVARP to reduce this storage requirement.Source: §3.1 · p. 4
  • FedVARP weights current updates more heavily than stored updates, and its expected update matches FedAvg.The higher weight on current updates gives the aggregation its unbiased property.Source: §3.1 · p. 4

3.2 CONVERGENCE ANALYSIS OF FEDVARP

  • Theorem analysis shows FedVARP eliminates partial-participation error but retains stochastic-gradient and client-drift errors.The local SGD procedure is unchanged.Source: §3.2 · p. 5
  • When σ = 0, τ = 1, and M = 1, FedVARP reduces exactly to SAGA.The section also compares FedVARP with MIFA and SCAFFOLD; FedVARP avoids MIFA’s first-round participation requirement and SCAFFOLD’s added client correction communication.Source: §3.2 · p. 5, §3.1 · p. 5

4 CLUSTER FEDVARP, AND ITS CONVERGENCE ANALYSIS

ClusterFedVARP reduces FedVARP’s server storage by sharing one update state among clients in each cluster. The number of clusters trades storage against variance-reduction error, including a cluster-heterogeneity term.

4 CLUSTER FEDVARP, AND ITS CONVERGENCE ANALYSIS

  • ClusterFedVARP stores one state per cluster rather than one per client, reducing the storage needed for server-side variance reduction.Each cluster state is the average update of its participating clients and remains unchanged when none participate.Source: §4 · pp. 5–6

ClusterFedVARP satisfy

  • ClusterFedVARP’s convergence bound includes stochastic-sampling, client-drift, and cluster-heterogeneity errors.Its analysis assumes bounded cluster variance; the within-cluster dissimilarity bound motivates clustering.Source: ClusterFedVARP satisfy · p. 6, §4 · p. 6
  • Varying K trades storage against variance reduction: K = N recovers FedVARP’s rate, while K = 1 recovers FedAvg.The server can choose K based on its storage constraints.Source: ClusterFedVARP satisfy · p. 6
  • Cluster states are updated whenever any client in the cluster participates, reducing state staleness but adding cluster-heterogeneity error and a trade-off between convergence speed and error floor.This state-update frequency differs from FedVARP, where a client’s state updates only when that client participates.Source: ClusterFedVARP satisfy · p. 6

5 EXPERIMENTS

Across vision and language-modeling experiments, FedVARP outperforms the baselines, while ClusterFedVARP performs comparably with lower storage requirements. The experiments use partial participation across CIFAR-10 and Shakespeare tasks.

5.1 EXPERIMENTAL SETUP

  • Experiments cover CIFAR-10 classification with LeNet-5 and ResNet-18 and Shakespeare next-character prediction with an RNN.They compare with FedAvg, MIFA, and SCAFFOLD; ClusterFedVARP uses 55 CIFAR-10 clusters and 36 Shakespeare clusters.Source: §5.1 · pp. 6–7, Figure 1 · p. 7
  • Each round samples five clients, corresponding to 2% participation for CIFAR-10 and less than 1% for Shakespeare; clients perform five local epochs.CIFAR-10 clients are partitioned across 250 clients, while the Shakespeare task uses 1,089 clients.Source: §5.1 · p. 7

5.2 COMPARISON WITH BASELINES

  • Under 536 rounds versus FedAvg’s 1158 rounds, the proposed algorithms reached 50% test accuracy on CIFAR-10 with LeNet-5, for up to 2.1x speedup.The reported experiments find FedVARP outperforming baselines in all cases and ClusterFedVARP in most cases.Source: Figure 1 · p. 7, §5.2 · p. 8
  • The algorithms outperform MIFA and SCAFFOLD in all experiments; the authors report MIFA’s initial-round bias and worse practical performance from SCAFFOLD’s client-drift correction.The authors attribute MIFA’s bias to not assuming that every client participates in the first round.Source: §5.2 · p. 8

6 RELATED WORK

Related work addresses FedAvg convergence, variance reduction, and clustered federated learning. The paper distinguishes its use of clusters for reducing participation variance from approaches that learn separate models per cluster.

6 RELATED WORK

  • Prior work analyzes FedAvg under non-iid data and partial participation, while broader reviews cover federated-learning convergence results.The cited analyses include nonconvex objectives.Source: §6 · p. 8
  • SVRG-style methods trade storage for periodic full or large-minibatch gradients, but federated use would require all clients to participate in some rounds.The authors consider that participation requirement unrealistic.Source: §6 · p. 8
  • Federated momentum-based variance-reduction methods can require communicating two global models and running local SGD for both, doubling communication and computation.The paper characterizes these approaches as unsuitable for practical federated settings.Source: §6 · p. 8
  • Unlike clustered federated learning that learns separate models per cluster, this work uses client clusters to reduce partial-participation variance while learning one global model.The section also notes N-SAGA’s centralized, strongly convex setting and suggests combining client and cluster states as future work.Source: §6 · p. 8

7 CONCLUSION

The paper addresses partial-participation variance in large-scale federated learning with FedVARP and a storage-efficient clustering-based variant, ClusterFedVARP.

7 CONCLUSION

  • FedVARP eliminates partial-participation variance at the server, while ClusterFedVARP reduces variance with lower storage requirements.The reported experiments show both methods consistently outperform existing baselines.Source: §7 · p. 8

A NOTATIONS AND BASIC RESULTS

This material introduces sampling notation and outlines intermediate results used in the FedAvg convergence proof.

A NOTATIONS AND BASIC RESULTS

B CONVERGENCE PROOF FOR FEDAVG (THEOREM 1)

B.1 INTERMEDIATE LEMMAS

  • Three intermediate lemmas state bounds on the iterates generated by FedAvg under specified assumptions on the objective and client stochastic oracles.Source: §B.1 · p. 13

B.2 PROOF OF THEOREM 1

Theorem 1’s proof presents a FedAvg error decomposition and then derives it using intermediate bounds.

B.2 PROOF OF THEOREM 1

  • Theorem 1 labels the FedAvg bound’s terms as initialization, client-drift, and partial-participation error.Source: §B.2 · pp. 13–14
  • The proof substitutes intermediate bounds, rearranges terms, and sums over training rounds to obtain the theorem.Source: §B.2 · p. 14

B.3 PROOFS OF THE INTERMEDIATE LEMMAS

  • The intermediate proofs separately bound terms T1 and T2; the Lemma 6 proof borrows techniques from.Source: §B.3 · p. 15

C CONVERGENCE RESULT FOR FEDVARP (THEOREM 2)

This section presents FedVARP’s convergence result and associated complexity and communication guarantees, supported by intermediate lemmas.

C CONVERGENCE RESULT FOR FEDVARP (THEOREM 2)

C.1 INTERMEDIATE LEMMAS

  • Three intermediate lemmas state bounds on FedVARP iterates under assumptions on the objective and client stochastic oracles.Source: §C.1 · p. 17

C.2 PROOF OF THEOREM 2

Theorem 2 gives a FedVARP convergence bound under stated assumptions and learning-rate conditions, with separate terms for client drift, initialization, and stochastic-gradient error. The surrounding material also introduces ClusterFedVARP's convergence analysis and an intermediate result that recovers an earlier bound when r = 1.

C.2 PROOF OF THEOREM 2

  • FedVARP's Theorem 2 states a convergence bound for iterates under assumptions on the objective and client stochastic oracles, subject to learning-rate conditions.The bound separates client-drift error, initialization, and stochastic-gradient error.Source: §C.2 · pp. 17–18

D CONVERGENCE RESULT FOR CLUSTERFEDVARP (THEOREM 3)

  • The ClusterFedVARP convergence section provides its theorem proof together with complexity and communication guarantees.The supplied section introduction identifies these as the section's contents.Source: D CONVERGENCE RESULT FOR… · p. 23

D.1 INTERMEDIATE LEMMAS

  • When r = 1, the intermediate result recovers the earlier Lemma 10 result up to multiplicative constants.Source: §D.1 · p. 24

D.2 PROOF OF THEOREM 3

Theorem 3 gives a ClusterFedVARP convergence bound under stated assumptions and learning-rate conditions. Its bound distinguishes stochastic-gradient, client-drift, initialization, and clustering errors; the intermediate proofs also use equal-sized clusters.

D.2 PROOF OF THEOREM 3

  • ClusterFedVARP's Theorem 3 states a convergence bound for iterates under objective and client-function assumptions and specified learning-rate conditions.The bound identifies stochastic-gradient error, client-drift error, initialization, and error due to clustering as separate terms.Source: §D.2 · p. 24

D.3 PROOFS OF THE INTERMEDIATE LEMMAS

  • The intermediate proof assumes equal numbers of devices in each cluster and uses the probability that a particular cluster has no sampled client.Source: §D.3 · pp. 27–28

Related papers

Loading 2207.14130v1…