FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data

• URL: http://arxiv.org/abs/2005.11418v3
• Date: Tue, 7 Jul 2020 22:04:13 GMT
• Title: FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data
• Authors: Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin and Yang Liu
• Abstract summary: Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model.
• Score: 59.50904660420082
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model, in which multiple local updates are performed using local data, before sending the local models to the cloud for aggregation. However, these schemes typically require strong assumptions, such as the local data are identically independent distributed (i.i.d), or the size of the local gradients are bounded. In this paper, we first explicitly characterize the behavior of the FedAvg algorithm, and show that without strong and unrealistic assumptions on the problem structure, the algorithm can behave erratically for non-convex problems (e.g., diverge to infinity). Aiming at designing FL algorithms that are provably fast and require as few assumptions as possible, we propose a new algorithm design strategy from the primal-dual optimization perspective. Our strategy yields a family of algorithms that take the same CTA model as existing algorithms, but they can deal with the non-convex objective, achieve the best possible optimization and communication complexity while being able to deal with both the full batch and mini-batch local computation models. Most importantly, the proposed algorithms are {\it communication efficient}, in the sense that the communication pattern can be adaptive to the level of heterogeneity among the local data. To the best of our knowledge, this is the first algorithmic framework for FL that achieves all the above properties.

Related papers

• Faster Adaptive Federated Learning [84.38913517122619]
  Federated learning has attracted increasing attention with the emergence of distributed data. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on momentum-based variance reduced technique in cross-silo FL.
  arXiv  Detail & Related papers  (2022-12-02T05:07:50Z)
• sqSGD: Locally Private and Communication Efficient Federated Learning [14.60645909629309]
  Federated learning (FL) is a technique that trains machine learning models from decentralized data sources. We develop a gradient-based learning algorithm called sqSGD that addresses communication efficiency and high-dimensional compatibility. Experiment results show sqSGD successfully learns large models like LeNet and ResNet with local privacy constraints.
  arXiv  Detail & Related papers  (2022-06-21T17:45:35Z)
• A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing [5.404315085380945]
  We present an original communication-constrained Newton-type (NT) algorithm designed to accelerate Federated Learning (FL) The proposed solution is thoroughly validated on real datasets.
  arXiv  Detail & Related papers  (2022-02-11T17:52:56Z)
• Local Learning Matters: Rethinking Data Heterogeneity in Federated Learning [61.488646649045215]
  Federated learning (FL) is a promising strategy for performing privacy-preserving, distributed learning with a network of clients (i.e., edge devices)
  arXiv  Detail & Related papers  (2021-11-28T19:03:39Z)
• Clustered Federated Learning via Generalized Total Variation Minimization [83.26141667853057]
  We study optimization methods to train local (or personalized) models for local datasets with a decentralized network structure. Our main conceptual contribution is to formulate federated learning as total variation minimization (GTV) Our main algorithmic contribution is a fully decentralized federated learning algorithm.
  arXiv  Detail & Related papers  (2021-05-26T18:07:19Z)
• Hybrid Federated Learning: Algorithms and Implementation [61.0640216394349]
  Federated learning (FL) is a recently proposed distributed machine learning paradigm dealing with distributed and private data sets. We propose a new model-matching-based problem formulation for hybrid FL. We then propose an efficient algorithm that can collaboratively train the global and local models to deal with full and partial featured data.
  arXiv  Detail & Related papers  (2020-12-22T23:56:03Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  We propose a new low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from Leiden-k-cut. This proposed algorithm is scalable, outperforms state-of-the-art algorithms, and outperforms in real-world time with little additional cost.
  arXiv  Detail & Related papers  (2020-12-04T15:46:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.