PaperlayerView exact revision on arXiv

Source-linked AI summary

FedCluster: Boosting the Convergence of Federated Learning via Cluster-Cycling

Cheng Chen, Ziyi Chen, Yi Zhou, Bhavya Kailkhura

arXiv:2009.10748v1cs.LGmath.OCstat.ML

TL;DR

FedAvg convergence is affected by device-level data heterogeneity, and existing federated-learning rounds perform only one global update. FedCluster cycles learning across device clusters, and its local-SGD analysis reports faster convergence than FedAvg in nonconvex optimization.

  • Problem

    FedAvg convergence is heavily affected by device-level data heterogeneity, which has been shown to slow convergence.

    Source: §I · p. 1

  • Method

    FedCluster groups devices into clusters that perform federated learning cyclically, producing multiple global updates within each learning round.

    Source: §I · p. 1, A. Our Contributions · p. 2, §II · p. 3

  • Results

    In nonconvex optimization, FedCluster with local SGD converges faster than FedAvg and its rate depends on cluster-level rather than device-level data heterogeneity.

    Source: B. Convergence Result · p. 4

  • Takeaways & Limitations

    FedCluster’s clusters can implement conventional federated algorithms and permit multiple global updates per round with the same computation and communication resources.

    Source: A. Our Contributions · p. 2

Abstract

from arXiv · show

We develop FedCluster--a novel federated learning framework with improved optimization efficiency, and investigate its theoretical convergence properties. The FedCluster groups the devices into multiple clusters that perform federated learning cyclically in each learning round. Therefore, each learning round of FedCluster consists of multiple cycles of meta-update that boost the overall convergence. In nonconvex optimization, we show that FedCluster with the devices implementing the local {stochastic gradient descent (SGD)} algorithm achieves a faster convergence rate than the conventional {federated averaging (FedAvg)} algorithm in the presence of device-level data heterogeneity. We conduct experiments on deep learning applications and demonstrate that FedCluster converges significantly faster than the conventional federated learning under diverse levels of device-level data heterogeneity for a variety of local optimizers.

I. INTRODUCTION

FedAvg convergence is slowed by device-level data heterogeneity, while existing approaches still perform only one global model update per round. FedCluster cycles federated learning across device clusters; its local-SGD analysis and deep-learning experiments report faster convergence.

I. INTRODUCTION

  • FedAvg convergence is heavily affected by device-level data heterogeneity, which empirical and theoretical studies have shown slows convergence.Prior approaches include local-loss regularization, variance reduction, control variates, server statistics, and normalized local gradients.Source: §I · p. 1

A. Our Contributions

  • FedCluster groups devices into clusters that perform federated learning cyclically, allowing multiple global updates per round with the same computation and communication resources.Clusters can implement conventional federated algorithms, including FedAvg and FedProx.Source: §I · p. 1, A. Our Contributions · p. 2
  • In nonconvex optimization, FedCluster with local SGD has rate O(1/√(TME)), versus O(1/√(TE)) for FedAvg, and depends on smaller cluster-level rather than device-level heterogeneity.The paper states the FedCluster rate is faster by a factor of M.Source: A. Our Contributions · p. 2
  • FedCluster converges significantly faster than conventional federated learning across different levels of device-level data heterogeneity and local optimizers in deep-learning experiments.The experiments also explore the effects of cluster count and cluster-level data heterogeneity.Source: A. Our Contributions · p. 2

B. Related Work

  • Prior work also studies clustering-based and personalized federated learning, alongside privacy, adversarial attacks, and fairness.The cited clustering approaches include decentralized cluster communication and device-to-device communication.Source: B. Related Work · p. 2

II. FEDCLUSTER: FEDERATED LEARNING WITH CLUSTER-CYCLING

FedCluster groups devices into clusters that take turns performing federated learning within each round. This adds global model updates while preserving the stated per-device resource constraint.

II. FEDCLUSTER: FEDERATED LEARNING WITH CLUSTER-CYCLING

  • Traditional federated learning activates a subset of devices for local training and averages their uploaded models, but its convergence is slowed by data heterogeneity and infrequent global updates.The figure contrasts this system with FedCluster’s cluster-cycling design.Source: §II · p. 2, Figure 1 · p. 3
  • FedCluster activates clusters in sequence, with participating devices locally training and uploading models for averaging before the next cluster cycle.Each device is activated at most once per round, satisfying the stated limit of one download and one upload.Source: §II · pp. 2–3
  • Unlike traditional federated learning’s single global update per round, FedCluster updates the global model once per cluster and is expected to make more optimization progress per round.The paper also describes cluster scheduling as flexible when devices are busy or unavailable.Source: §II · p. 3
  • Traditional federated learning is a special case of FedCluster with one cluster, and clusters can use algorithms compatible with the traditional framework, including FedAvg and FedProx.The framework’s clustering approach can be selected for the application scenario, including random, timezone-based, or availability-based grouping.Source: §II · p. 3

III. CONVERGENCE ANALYSIS OF FEDCLUSTER WITH LOCAL SGD

  • The paper analyzes FedCluster’s convergence with local SGD in smooth nonconvex optimization.The later analysis compares its cluster-level heterogeneity with the device-level heterogeneity affecting traditional federated learning.Source: §III · p. 3, §II · p. 3

A. Problem Formulation and Algorithm

The formulation assigns each device a local dataset and weights its contribution by its share of the total data. FedCluster then cycles clusters through local SGD and model averaging under stated loss-function assumptions.

A. Problem Formulation and Algorithm

  • The objective is empirical risk minimization over device-held datasets, with each device’s data proportion defined by its sample count relative to the total.The local dataset loss is its average loss over that device’s samples.Source: A. Problem Formulation and Algorithm · pp. 3–4
  • In each round, FedCluster samples devices from each cluster and sequentially performs local SGD and model averaging, passing the updated global model to the next cycle.Activated devices initialize from the current model, perform multiple local iterations, and upload their trained models for averaging.Source: A. Problem Formulation and Algorithm · p. 4
  • The analysis assumes smooth, lower-bounded losses, bounded stochastic-gradient variance, and bounded expected squared gradient norms for the generated models.The paper identifies these as standard assumptions on the loss function.Source: A. Problem Formulation and Algorithm · p. 4

B. Convergence Result

Under full participation and cyclic cluster scheduling, the analysis establishes a faster nonconvex convergence rate for FedCluster with local SGD than for FedAvg. The rate depends on cluster-level heterogeneity, with the number and composition of clusters affecting its constant.

B. Convergence Result

  • The analysis assumes full participation and cyclic cluster scheduling with reshuffling each round, and defines cluster-level heterogeneity through gradient variance across cluster data.The cluster loss is the weighted sum of the local losses within that cluster.Source: B. Convergence Result · p. 4
  • O(1/sqrt(TME)) for FedCluster versus O(1/sqrt(TE)) for FedAvg gives a convergence-rate advantage by a factor of M under the theorem's conditions.The theorem assumes full device participation and specifies choices for the learning rate, E, M, and T.Source: B. Convergence Result · p. 4
  • The FedCluster rate depends on Hcluster rather than FedAvg's larger Hdevice, so it is less sensitive to device-level data heterogeneity.The supplied analysis states Hcluster ≤ Hdevice.Source: B. Convergence Result · p. 4
  • More clusters increase both Hcluster and the local-variance terms in C, making the choice of M important for minimizing the convergence bound.At fixed M, clustering that minimizes Hcluster can also improve the convergence rate.Source: B. Convergence Result · p. 5

A. Experiment Setup

The experiments compare FedCluster with traditional federated learning on CIFAR-10 and MNIST. On CIFAR-10, FedCluster converges faster across four device-level heterogeneity ratios in both train loss and test accuracy.

A. Experiment Setup

  • The setup uses AlexNet and cross-entropy on 1,000 simulated devices, each with 500 samples; device heterogeneity is controlled by the share of samples from a major class.FedCluster uses 10 uniformly random clusters by default; a larger ρdevice denotes higher heterogeneity.Source: A. Experiment Setup · p. 5
  • Both systems use 20 local SGD steps per cycle or round; FedCluster's learning rates are one tenth of the traditional system's and are not fine-tuned.The baseline activates 10% of devices per round, while FedCluster activates 10% of the corresponding cluster per cycle.Source: A. Experiment Setup · p. 5

B. Comparison under Different Device-level Data Heterogeneities

  • Across ρdevice = 0.1, 0.4, 0.7, 0.9, FedCluster converges faster than FedAvg on CIFAR-10 in both train loss and test accuracy.Fig. 2 presents the comparison across these device-level data heterogeneity levels.Source: Figure 2 · p. 5, B. Comparison under Different… · p. 5
  • On MNIST, similar observations hold, and comparison with CIFAR-10 suggests FedCluster may be more advantageous on more complex data.The source phrases the complexity comparison as an apparent trend.Source: B. Comparison under Different… · p. 5

C. Comparison under Different Optimizers

Across tested local optimizers and data-heterogeneity settings, FedCluster outperforms conventional federated learning. Its performance also varies with cluster count and cluster-level heterogeneity, while the conclusion reports faster convergence than FedAvg for local SGD in nonconvex optimization.

C. Comparison under Different Optimizers

D. Effect of Number of Clusters

  • On CIFAR-10, FedCluster outperforms FedAvg for all tested cluster counts, and more clusters yield faster convergence; on MNIST, five clusters are comparable to FedAvg.The tested cluster counts are M = 5, 10, and 20; the number of clusters is limited in practice by the learning cycles allowed per round.Source: Figure 5 · p. 6, D. Effect of Number of Clusters · p. 6

E. Comparison under Different Cluster-level Data Heterogeneities

  • FedCluster converges faster than FedAvg at all tested cluster-level heterogeneity levels, with slightly faster convergence at lower cluster-level heterogeneity.The comparison fixes device-level heterogeneity at ρdevice = 0.5 and tests ρcluster = 0.1, 0.5, and 0.9.Source: E. Comparison under Different… · p. 6, Figure 6 · p. 7

V. CONCLUSION

  • The conclusion reports that FedCluster with local SGD converges faster than FedAvg in nonconvex optimization and is less dependent on device-level data heterogeneity.The experiments are described as corroborating the theoretical findings.Source: §V · p. 7

APPENDIX A SUPPORTING LEMMAS

The supporting lemmas set up a random cluster order and a weighted average of local models, then state properties of an expected quantity and a condition on the learning rate.

APPENDIX A SUPPORTING LEMMAS

  • Each learning round randomly permutes the clusters, which then perform federated learning sequentially; the passage also defines a weighted average of active-cluster local models.The average is defined for iteration t of cycle K in round j.Source: Appendix A · p. 8
  • Lemma 1 states that the defined quantity gj,K,t and its expectation over local sample randomness satisfy stated properties.The supplied passage does not specify those properties' expressions.Source: Appendix A · p. 8
  • Lemma 2 assumes a learning rate non-increasing over the combined round, cycle, and iteration index; its proof invokes Jensen’s inequality.The proof also uses the relation between consecutive cycles’ model states.Source: Appendix A · pp. 8–9

APPENDIX B PROOF OF THEOREM 1

The proof uses smoothness and stated assumptions to derive an iteration-wise bound, then telescopes that bound across rounds, clusters, and local iterations. It also gives a condition on the product of clusters and local iterations.

APPENDIX B PROOF OF THEOREM 1

  • The proof applies objective-function smoothness and uses the cited assumptions and inequalities to derive its bound.The derivation also invokes Jensen’s and Cauchy–Schwarz inequalities and the heterogeneity definition.Source: Appendix B · pp. 9–10
  • Telescoping the bound across learning rounds, clusters, and local iterations yields the aggregate bound.The proof identifies matching model states between consecutive cycles and rounds.Source: Appendix B · p. 10
  • The proof requires ME ≤ C/(8LG²) for the stated bound, with C defined in equation (4) and C2 = 8LG².The passage begins to state the requirement for an ϵ-stationary point but does not include the full expression.Source: Appendix B · p. 10

Related papers

Loading 2009.10748v1…