On Convergence of FedProx: Local Dissimilarity Invariant Bounds,
Non-smoothness and Beyond
- URL: http://arxiv.org/abs/2206.05187v1
- Date: Fri, 10 Jun 2022 15:35:10 GMT
- Title: On Convergence of FedProx: Local Dissimilarity Invariant Bounds,
Non-smoothness and Beyond
- Authors: Xiao-Tong Yuan and Ping Li
- Abstract summary: We develop a novel local dissimilarity in convergence theory for FedProx and its minibatch extension through the lens of algorithmic stability.
Preliminary experimental results on a series of benchmark FL datasets are reported to demonstrate the benefit of minibatching for improving the sample efficiency of FedProx.
- Score: 41.082982732100696
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The FedProx algorithm is a simple yet powerful distributed proximal point
optimization method widely used for federated learning (FL) over heterogeneous
data. Despite its popularity and remarkable success witnessed in practice, the
theoretical understanding of FedProx is largely underinvestigated: the
appealing convergence behavior of FedProx is so far characterized under certain
non-standard and unrealistic dissimilarity assumptions of local functions, and
the results are limited to smooth optimization problems. In order to remedy
these deficiencies, we develop a novel local dissimilarity invariant
convergence theory for FedProx and its minibatch stochastic extension through
the lens of algorithmic stability. As a result, we contribute to derive several
new and deeper insights into FedProx for non-convex federated optimization
including: 1) convergence guarantees independent on local dissimilarity type
conditions; 2) convergence guarantees for non-smooth FL problems; and 3) linear
speedup with respect to size of minibatch and number of sampled devices. Our
theory for the first time reveals that local dissimilarity and smoothness are
not must-have for FedProx to get favorable complexity bounds. Preliminary
experimental results on a series of benchmark FL datasets are reported to
demonstrate the benefit of minibatching for improving the sample efficiency of
FedProx.
Related papers
- Privacy-preserving Federated Primal-dual Learning for Non-convex and Non-smooth Problems with Model Sparsification [51.04894019092156]
Federated learning (FL) has been recognized as a rapidly growing area, where the model is trained over clients under the FL orchestration (PS)
In this paper, we propose a novel primal sparification algorithm for and guarantee non-smooth FL problems.
Its unique insightful properties and its analyses are also presented.
arXiv Detail & Related papers (2023-10-30T14:15:47Z) - 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) - Achieving Statistical Optimality of Federated Learning: Beyond
Stationary Points [19.891597817559038]
Federated Learning (FL) is a promising framework that has great potentials in privacy preservation and in lowering the computation load at the cloud.
Recent work raised concerns on two methods: (1) their fixed points do not correspond to the stationary points of the original optimization problem, and (2) the common model found might not generalize well locally.
We show, in the general kernel regression setting, that both FedAvg and FedProx converge to the minimax-optimal error rates.
arXiv Detail & Related papers (2021-06-29T09:59:43Z) - Distributionally Robust Federated Averaging [19.875176871167966]
We present communication efficient distributed algorithms for robust learning periodic averaging with adaptive sampling.
We give corroborating experimental evidence for our theoretical results in federated learning settings.
arXiv Detail & Related papers (2021-02-25T03:32:09Z) - 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) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
arXiv Detail & Related papers (2020-06-12T00:32:21Z) - FedDANE: A Federated Newton-Type Method [49.9423212899788]
Federated learning aims to jointly learn low statistical models over massively distributed datasets.
We propose FedDANE, an optimization that we adapt from DANE, to handle federated learning.
arXiv Detail & Related papers (2020-01-07T07:44:41Z)
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.