Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling

• URL: http://arxiv.org/abs/2112.11256v1
• Date: Tue, 21 Dec 2021 14:28:40 GMT
• Title: Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling
• Authors: Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, Leandros Tassiulas
• Abstract summary: Federated learning (FL) algorithms usually sample a fraction in each (partial participation) when the number of participants is large. Recent works have focused on the convergence analysis of FL. We obtain new convergence bound for FL algorithms with arbitrary client sampling probabilities.
• Score: 34.187387951367526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated learning (FL) algorithms usually sample a fraction of clients in each round (partial participation) when the number of participants is large and the server's communication bandwidth is limited. Recent works on the convergence analysis of FL have focused on unbiased client sampling, e.g., sampling uniformly at random, which suffers from slow wall-clock time for convergence due to high degrees of system heterogeneity and statistical heterogeneity. This paper aims to design an adaptive client sampling algorithm that tackles both system and statistical heterogeneity to minimize the wall-clock convergence time. We obtain a new tractable convergence bound for FL algorithms with arbitrary client sampling probabilities. Based on the bound, we analytically establish the relationship between the total learning time and sampling probabilities, which results in a non-convex optimization problem for training time minimization. We design an efficient algorithm for learning the unknown parameters in the convergence bound and develop a low-complexity algorithm to approximately solve the non-convex problem. Experimental results from both hardware prototype and simulation demonstrate that our proposed sampling scheme significantly reduces the convergence time compared to several baseline sampling schemes. Notably, our scheme in hardware prototype spends 73% less time than the uniform sampling baseline for reaching the same target loss.

Related papers

• Adaptive Heterogeneous Client Sampling for Federated Learning over Wireless Networks [27.545199007002577]
  Federated learning (FL) algorithms sample a fraction of clients in each round (partial participation) when the number of participants is large. Recent convergence analysis of FL have focused on slow-clock convergence due to client heterogeneity. We propose a new tractable convergence system for FL with arbitrary probability sampling.
  arXiv  Detail & Related papers  (2024-04-22T00:16:18Z)
• Random Aggregate Beamforming for Over-the-Air Federated Learning in Large-Scale Networks [66.18765335695414]
  We consider a joint device selection and aggregate beamforming design with the objectives of minimizing the aggregate error and maximizing the number of selected devices. To tackle the problems in a cost-effective manner, we propose a random aggregate beamforming-based scheme. We additionally use analysis to study the obtained aggregate error and the number of the selected devices when the number of devices becomes large.
  arXiv  Detail & Related papers  (2024-02-20T23:59:45Z)
• Adaptive Federated Learning in Heterogeneous Wireless Networks with Independent Sampling [15.027267764009052]
  Federated Learning (FL) algorithms sample a random subset of clients to address the straggler issue and improve communication efficiency. Recent have proposed various client sampling methods, but they have limitations in joint system and data heterogeneity. We propose a new independent client sampling strategy to minimize the wall-clock time of FL.
  arXiv  Detail & Related papers  (2024-02-15T16:51:38Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• 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)
• Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback [36.05851452151107]
  federated learning (FL) systems need to sample a subset of clients that are involved in each round of training. Despite its importance, there is limited work on how to sample clients effectively. We show how our sampling method can improve the convergence speed of optimization algorithms.
  arXiv  Detail & Related papers  (2021-12-28T23:50:52Z)
• Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity [57.275753974812666]
  Federated learning involves learning from data samples distributed across a network of clients while the data remains local. In this paper, we propose a novel straggler-resilient federated learning method that incorporates statistical characteristics of the clients' data to adaptively select the clients in order to speed up the learning procedure.
  arXiv  Detail & Related papers  (2020-12-28T19:21:14Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning [27.775096437736973]
  We show that the independent sampling scheme tends to improve performance of the commonly-used uniform sampling scheme. Our new analysis also derives a speed for the sampling than best one available so far.
  arXiv  Detail & Related papers  (2020-09-14T16:41:32Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.