Related papers: Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance

Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance

URL: http://arxiv.org/abs/2310.02698v3
Date: Sat, 31 Aug 2024 16:15:35 GMT
Title: Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance
Authors: Dun Zeng, Zenglin Xu, Yu Pan, Xu Luo, Qifan Wang, Xiaoying Tang,
Abstract summary: Federated Learning (FL) is a distributed learning paradigm to train a global model across multiple devices without collecting local data. We present the first adaptive client sampler, K-Vib, employing an independent sampling procedure. K-Vib achieves a linear speed-up on the regret bound $tildemathcalObig(Nfrac13Tfrac23/Kfrac43big)$ within a set communication budget.
Score: 37.646655530394604
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Federated Learning (FL) is a distributed learning paradigm to train a global model across multiple devices without collecting local data. In FL, a server typically selects a subset of clients for each training round to optimize resource usage. Central to this process is the technique of unbiased client sampling, which ensures a representative selection of clients. Current methods primarily utilize a random sampling procedure which, despite its effectiveness, achieves suboptimal efficiency owing to the loose upper bound caused by the sampling variance. In this work, by adopting an independent sampling procedure, we propose a federated optimization framework focused on adaptive unbiased client sampling, improving the convergence rate via an online variance reduction strategy. In particular, we present the first adaptive client sampler, K-Vib, employing an independent sampling procedure. K-Vib achieves a linear speed-up on the regret bound $\tilde{\mathcal{O}}\big(N^{\frac{1}{3}}T^{\frac{2}{3}}/K^{\frac{4}{3}}\big)$ within a set communication budget $K$. Empirical studies indicate that K-Vib doubles the speed compared to baseline algorithms, demonstrating significant potential in federated optimization.

Related papers

Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learning [51.560590617691005]
We investigate whether it is possible to squeeze more juice" out of each cohort than what is possible in a single communication round. Our approach leads to up to 74% reduction in the total communication cost needed to train a FL model in the cross-device setting.
arXiv Detail & Related papers (2024-06-03T08:48:49Z)
Emulating Full Client Participation: A Long-Term Client Selection Strategy for Federated Learning [48.94952630292219]
We propose a novel client selection strategy designed to emulate the performance achieved with full client participation. In a single round, we select clients by minimizing the gradient-space estimation error between the client subset and the full client set. In multi-round selection, we introduce a novel individual fairness constraint, which ensures that clients with similar data distributions have similar frequencies of being selected.
arXiv Detail & Related papers (2024-05-22T12:27:24Z)
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)
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)
LEFL: Low Entropy Client Sampling in Federated Learning [6.436397118145477]
Federated learning (FL) is a machine learning paradigm where multiple clients collaborate to optimize a single global model using their private data. We propose LEFL, an alternative sampling strategy by performing a one-time clustering of clients based on their model's learned high-level features. We show of sampled clients selected with this approach yield a low relative entropy with respect to the global data distribution.
arXiv Detail & Related papers (2023-12-29T01:44:20Z)
FedLALR: Client-Specific Adaptive Learning Rates Achieve Linear Speedup for Non-IID Data [54.81695390763957]
Federated learning is an emerging distributed machine learning method. We propose a heterogeneous local variant of AMSGrad, named FedLALR, in which each client adjusts its learning rate. We show that our client-specified auto-tuned learning rate scheduling can converge and achieve linear speedup with respect to the number of clients.
arXiv Detail & Related papers (2023-09-18T12:35:05Z)
Towards Instance-adaptive Inference for Federated Learning [80.38701896056828]
Federated learning (FL) is a distributed learning paradigm that enables multiple clients to learn a powerful global model by aggregating local training. In this paper, we present a novel FL algorithm, i.e., FedIns, to handle intra-client data heterogeneity by enabling instance-adaptive inference in the FL framework. Our experiments show that our FedIns outperforms state-of-the-art FL algorithms, e.g., a 6.64% improvement against the top-performing method with less than 15% communication cost on Tiny-ImageNet.
arXiv Detail & Related papers (2023-08-11T09:58:47Z)
Beyond ADMM: A Unified Client-variance-reduced Adaptive Federated Learning Framework [82.36466358313025]
We propose a primal-dual FL algorithm, termed FedVRA, that allows one to adaptively control the variance-reduction level and biasness of the global model. Experiments based on (semi-supervised) image classification tasks demonstrate superiority of FedVRA over the existing schemes.
arXiv Detail & Related papers (2022-12-03T03:27:51Z)
Fed-CBS: A Heterogeneity-Aware Client Sampling Mechanism for Federated Learning via Class-Imbalance Reduction [76.26710990597498]
We show that the class-imbalance of the grouped data from randomly selected clients can lead to significant performance degradation. Based on our key observation, we design an efficient client sampling mechanism, i.e., Federated Class-balanced Sampling (Fed-CBS) In particular, we propose a measure of class-imbalance and then employ homomorphic encryption to derive this measure in a privacy-preserving way.
arXiv Detail & Related papers (2022-09-30T05:42:56Z)
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)
Clustered Sampling: Low-Variance and Improved Representativity for Clients Selection in Federated Learning [4.530678016396477]
This work addresses the problem of optimizing communications between server and clients in federated learning (FL) Current sampling approaches in FL are either biased, or non optimal in terms of server-clients communications and training stability. We prove that clustered sampling leads to better clients representatitivity and to reduced variance of the clients aggregation weights in FL.
arXiv Detail & Related papers (2021-05-12T18:19:20Z)

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