A Theorem of the Alternative for Personalized Federated Learning
- URL: http://arxiv.org/abs/2103.01901v1
- Date: Tue, 2 Mar 2021 17:58:20 GMT
- Title: A Theorem of the Alternative for Personalized Federated Learning
- Authors: Shuxiao Chen, Qinqing Zheng, Qi Long, Weijie J. Su
- Abstract summary: We show how excess risks of personalized federated learning depend on data heterogeneity from a minimax point of view.
Our results show that the presumably difficult (infinite-dimensional) problem of adapting to client-wise heterogeneity can be reduced to a simple binary decision problem.
- Score: 19.499120576896228
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A widely recognized difficulty in federated learning arises from the
statistical heterogeneity among clients: local datasets often come from
different but not entirely unrelated distributions, and personalization is,
therefore, necessary to achieve optimal results from each individual's
perspective. In this paper, we show how the excess risks of personalized
federated learning with a smooth, strongly convex loss depend on data
heterogeneity from a minimax point of view. Our analysis reveals a surprising
theorem of the alternative for personalized federated learning: there exists a
threshold such that (a) if a certain measure of data heterogeneity is below
this threshold, the FedAvg algorithm [McMahan et al., 2017] is minimax optimal;
(b) when the measure of heterogeneity is above this threshold, then doing pure
local training (i.e., clients solve empirical risk minimization problems on
their local datasets without any communication) is minimax optimal. As an
implication, our results show that the presumably difficult
(infinite-dimensional) problem of adapting to client-wise heterogeneity can be
reduced to a simple binary decision problem of choosing between the two
baseline algorithms. Our analysis relies on a new notion of algorithmic
stability that takes into account the nature of federated learning.
Related papers
- Byzantine-resilient Federated Learning Employing Normalized Gradients on Non-IID Datasets [23.640506243685863]
In practical federated learning (FLNGA) the presence of malicious attacks and data heterogeneity often introduces biases into the learning process.
We propose a Normalized Gradient unit (Fed-M) model which normalizes uploaded local gradients to be before aggregation, achieving a time of $mathcalO(pM)$.
arXiv Detail & Related papers (2024-08-18T16:50:39Z) - Federated Minimax Optimization with Client Heterogeneity [11.558008138030845]
Minimax computation has seen a surge in interest with the advent modern applications such as GANs.
We propose a general federated minimax framework that subsumes settings and existing methods like Local SGDA.
arXiv Detail & Related papers (2023-02-08T18:33:55Z) - Straggler-Resilient Personalized Federated Learning [55.54344312542944]
Federated learning allows training models from samples distributed across a large network of clients while respecting privacy and communication restrictions.
We develop a novel algorithmic procedure with theoretical speedup guarantees that simultaneously handles two of these hurdles.
Our method relies on ideas from representation learning theory to find a global common representation using all clients' data and learn a user-specific set of parameters leading to a personalized solution for each client.
arXiv Detail & Related papers (2022-06-05T01:14:46Z) - DRFLM: Distributionally Robust Federated Learning with Inter-client
Noise via Local Mixup [58.894901088797376]
federated learning has emerged as a promising approach for training a global model using data from multiple organizations without leaking their raw data.
We propose a general framework to solve the above two challenges simultaneously.
We provide comprehensive theoretical analysis including robustness analysis, convergence analysis, and generalization ability.
arXiv Detail & Related papers (2022-04-16T08:08:29Z) - 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) - Resource-constrained Federated Edge Learning with Heterogeneous Data:
Formulation and Analysis [8.863089484787835]
We propose a distributed approximate Newton-type Newton-type training scheme, namely FedOVA, to solve the heterogeneous statistical challenge brought by heterogeneous data.
FedOVA decomposes a multi-class classification problem into more straightforward binary classification problems and then combines their respective outputs using ensemble learning.
arXiv Detail & Related papers (2021-10-14T17:35:24Z) - Risk Minimization from Adaptively Collected Data: Guarantees for
Supervised and Policy Learning [57.88785630755165]
Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data.
We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class.
For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
arXiv Detail & Related papers (2021-06-03T09:50:13Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
The distributionally robust optimization framework is considered for training a parametric model.
The objective is to endow the trained model with robustness against adversarially manipulated input data.
Proposed algorithms offer robustness with little overhead.
arXiv Detail & Related papers (2020-07-07T18:25:25Z) - 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.