A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates

• URL: http://arxiv.org/abs/2206.10189v1
• Date: Tue, 21 Jun 2022 08:46:05 GMT
• Title: A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates
• Authors: Yann Fraboni, Richard Vidal, Laetitia Kameni, Marco Lorenzi
• Abstract summary: We extend the standard FedAvg aggregation scheme by introducing aggregation weights to represent the variability of the clients update time. Our formalism applies to the general federated setting where clients have heterogeneous datasets and perform at least one step of gradient descent. We develop in this work FedFix, a novel extension of FedAvg enabling efficient asynchronous federated training while preserving the convergence stability of synchronous aggregation.
• Score: 10.609815608017065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel framework to study asynchronous federated learning optimization with delays in gradient updates. Our theoretical framework extends the standard FedAvg aggregation scheme by introducing stochastic aggregation weights to represent the variability of the clients update time, due for example to heterogeneous hardware capabilities. Our formalism applies to the general federated setting where clients have heterogeneous datasets and perform at least one step of stochastic gradient descent (SGD). We demonstrate convergence for such a scheme and provide sufficient conditions for the related minimum to be the optimum of the federated problem. We show that our general framework applies to existing optimization schemes including centralized learning, FedAvg, asynchronous FedAvg, and FedBuff. The theory here provided allows drawing meaningful guidelines for designing a federated learning experiment in heterogeneous conditions. In particular, we develop in this work FedFix, a novel extension of FedAvg enabling efficient asynchronous federated training while preserving the convergence stability of synchronous aggregation. We empirically demonstrate our theory on a series of experiments showing that asynchronous FedAvg leads to fast convergence at the expense of stability, and we finally demonstrate the improvements of FedFix over synchronous and asynchronous FedAvg.

Related papers

• FADAS: Towards Federated Adaptive Asynchronous Optimization [56.09666452175333]
  Federated learning (FL) has emerged as a widely adopted training paradigm for privacy-preserving machine learning. This paper introduces federated adaptive asynchronous optimization, named FADAS, a novel method that incorporates asynchronous updates into adaptive federated optimization with provable guarantees. We rigorously establish the convergence rate of the proposed algorithms and empirical results demonstrate the superior performance of FADAS over other asynchronous FL baselines.
  arXiv  Detail & Related papers  (2024-07-25T20:02:57Z)
• FedStaleWeight: Buffered Asynchronous Federated Learning with Fair Aggregation via Staleness Reweighting [9.261784956541641]
  Asynchronous Federated Learning (AFL) methods have emerged as promising alternatives to their synchronous counterparts by the slowest agent. AFL model training heavily towards agents who can produce updates faster, leaving slower agents behind. We introduce FedStaleWeight, an algorithm addressing in aggregating asynchronous client updates by employing average staleness to compute fair re-weightings.
  arXiv  Detail & Related papers  (2024-06-05T02:52:22Z)
• FedFa: A Fully Asynchronous Training Paradigm for Federated Learning [14.4313600357833]
  Federated learning is an efficient decentralized training paradigm for scaling the machine learning model training on a large number of devices. Recent state-of-the-art solutions propose using semi-asynchronous approaches to mitigate the waiting time cost with guaranteed convergence. We propose a full asynchronous training paradigm, called FedFa, which can guarantee model convergence and eliminate the waiting time completely.
  arXiv  Detail & Related papers  (2024-04-17T02:46:59Z)
• Stragglers-Aware Low-Latency Synchronous Federated Learning via Layer-Wise Model Updates [71.81037644563217]
  Synchronous federated learning (FL) is a popular paradigm for collaborative edge learning. As some of the devices may have limited computational resources and varying availability, FL latency is highly sensitive to stragglers. We propose straggler-aware layer-wise federated learning (SALF) that leverages the optimization procedure of NNs via backpropagation to update the global model in a layer-wise fashion.
  arXiv  Detail & Related papers  (2024-03-27T09:14:36Z)
• Asynchronous Federated Learning with Incentive Mechanism Based on Contract Theory [5.502596101979607]
  We propose a novel asynchronous FL framework that integrates an incentive mechanism based on contract theory. Our framework exhibits a 1.35% accuracy improvement over the ideal Local SGD under attacks.
  arXiv  Detail & Related papers  (2023-10-10T09:17:17Z)
• Federated Conformal Predictors for Distributed Uncertainty Quantification [83.50609351513886]
  Conformal prediction is emerging as a popular paradigm for providing rigorous uncertainty quantification in machine learning. In this paper, we extend conformal prediction to the federated learning setting. We propose a weaker notion of partial exchangeability, better suited to the FL setting, and use it to develop the Federated Conformal Prediction framework.
  arXiv  Detail & Related papers  (2023-05-27T19:57:27Z)
• FedSkip: Combatting Statistical Heterogeneity with Federated Skip Aggregation [95.85026305874824]
  We introduce a data-driven approach called FedSkip to improve the client optima by periodically skipping federated averaging and scattering local models to the cross devices. We conduct extensive experiments on a range of datasets to demonstrate that FedSkip achieves much higher accuracy, better aggregation efficiency and competing communication efficiency.
  arXiv  Detail & Related papers  (2022-12-14T13:57:01Z)
• FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
  Many contemporary ML problems fall under nested bilevel programming that subsumes minimax and compositional optimization. We propose FedNest: A federated alternating gradient method to address general nested problems.
  arXiv  Detail & Related papers  (2022-05-04T17:48:55Z)
• Blockchain-enabled Server-less Federated Learning [5.065631761462706]
  We focus on an asynchronous server-less Federated Learning solution empowered by (BC) technology. In contrast to mostly adopted FL approaches, we advocate an asynchronous method whereby model aggregation is done as clients submit their local updates.
  arXiv  Detail & Related papers  (2021-12-15T07:41:23Z)
• A Unified Linear Speedup Analysis of Federated Averaging and Nesterov FedAvg [49.76940694847521]
  Federated learning (FL) learns a model jointly from a set of participating devices without sharing each other's privately held data. In this paper, we focus on Federated Averaging (FedAvg), one of the most popular and effective FL algorithms in use today. We show that FedAvg enjoys linear speedup in each case, although with different convergence rates and communication efficiencies.
  arXiv  Detail & Related papers  (2020-07-11T05:59:08Z)

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.