Variance-Reduced Heterogeneous Federated Learning via Stratified Client Selection

• URL: http://arxiv.org/abs/2201.05762v1
• Date: Sat, 15 Jan 2022 05:41:36 GMT
• Title: Variance-Reduced Heterogeneous Federated Learning via Stratified Client Selection
• Authors: Guangyuan Shen, Dehong Gao, Libin Yang, Fang Zhou, Duanxiao Song, Wei Lou, Shirui Pan
• Abstract summary: We propose a novel stratified client selection scheme to reduce the variance for the pursuit of better convergence and higher accuracy. We present an optimized sample size allocation scheme by considering the diversity of stratum's variability. Experimental results confirm that our approach not only allows for better performance relative to state-of-the-art methods but also is compatible with prevalent FL algorithms.
• Score: 31.401919362978017
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Client selection strategies are widely adopted to handle the communication-efficient problem in recent studies of Federated Learning (FL). However, due to the large variance of the selected subset's update, prior selection approaches with a limited sampling ratio cannot perform well on convergence and accuracy in heterogeneous FL. To address this problem, in this paper, we propose a novel stratified client selection scheme to reduce the variance for the pursuit of better convergence and higher accuracy. Specifically, to mitigate the impact of heterogeneity, we develop stratification based on clients' local data distribution to derive approximate homogeneous strata for better selection in each stratum. Concentrating on a limited sampling ratio scenario, we next present an optimized sample size allocation scheme by considering the diversity of stratum's variability, with the promise of further variance reduction. Theoretically, we elaborate the explicit relation among different selection schemes with regard to variance, under heterogeneous settings, we demonstrate the effectiveness of our selection scheme. Experimental results confirm that our approach not only allows for better performance relative to state-of-the-art methods but also is compatible with prevalent FL algorithms.

Related papers

• A Trust-Region Method for Graphical Stein Variational Inference [3.5516599670943774]
  Stein variational (SVI) is a sample-based approximate inference technique that generates a sample set by jointly optimizing the samples locations to an information-theoretic measure. We propose a novel trust-conditioned approach for SVI that successfully addresses each these challenges.
  arXiv  Detail & Related papers  (2024-10-21T16:59:01Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Learning Fair Policies for Multi-stage Selection Problems from Observational Data [4.282745020665833]
  We consider the problem of learning fair policies for multi-stage selection problems from observational data. This problem arises in several high-stakes domains such as company hiring, loan approval, or bail decisions where outcomes are only observed for those selected. We propose a multi-stage framework that can be augmented with various fairness constraints, such as demographic parity or equal opportunity.
  arXiv  Detail & Related papers  (2023-12-20T16:33:15Z)
• Aggregation Weighting of Federated Learning via Generalization Bound Estimation [65.8630966842025]
  Federated Learning (FL) typically aggregates client model parameters using a weighting approach determined by sample proportions. We replace the aforementioned weighting method with a new strategy that considers the generalization bounds of each local model.
  arXiv  Detail & Related papers  (2023-11-10T08:50:28Z)
• Tackling Diverse Minorities in Imbalanced Classification [80.78227787608714]
  Imbalanced datasets are commonly observed in various real-world applications, presenting significant challenges in training classifiers. We propose generating synthetic samples iteratively by mixing data samples from both minority and majority classes. We demonstrate the effectiveness of our proposed framework through extensive experiments conducted on seven publicly available benchmark datasets.
  arXiv  Detail & Related papers  (2023-08-28T18:48:34Z)
• Client Selection for Federated Policy Optimization with Environment Heterogeneity [0.0]
  Policy Iteration (PI) has inspired many recent algorithms for Reinforcement Learning (RL) This paper investigates the federated version of Approximate PI (API) and derives its error bound. We propose a client selection algorithm to alleviate the additional approximation error.
  arXiv  Detail & Related papers  (2023-05-18T13:48:20Z)
• Fast Heterogeneous Federated Learning with Hybrid Client Selection [29.902439962022868]
  We present a novel clustering-based client selection scheme to accelerate the convergence by variance reduction. We also present the tighter convergence guarantee of the proposed scheme thanks to the variance reduction.
  arXiv  Detail & Related papers  (2022-08-10T04:10:24Z)
• Variational Refinement for Importance Sampling Using the Forward Kullback-Leibler Divergence [77.06203118175335]
  Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference. Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures. We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
  arXiv  Detail & Related papers  (2021-06-30T11:00:24Z)
• Adaptive transfer learning [6.574517227976925]
  We introduce a flexible framework for transfer learning in the context of binary classification. We show that the optimal rate can be achieved by an algorithm that adapts to key aspects of the unknown transfer relationship.
  arXiv  Detail & Related papers  (2021-06-08T15:39:43Z)
• Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
  We study off-policy evaluation from multiple logging policies, each generating a dataset of fixed size, i.e., stratified sampling. We find the OPE estimator for multiple loggers with minimum variance for any instance, i.e., the efficient one.
  arXiv  Detail & Related papers  (2020-10-21T13:43:48Z)
• Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
  Off-policy policy optimization is a challenging problem in reinforcement learning. Off-policy algorithms are memory-efficient and capable of learning from off-policy samples.
  arXiv  Detail & Related papers  (2020-09-14T16:22:46Z)

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.