On the Convergence of FedProx with Extrapolation and Inexact Prox

• URL: http://arxiv.org/abs/2410.01410v1
• Date: Wed, 2 Oct 2024 10:42:27 GMT
• Title: On the Convergence of FedProx with Extrapolation and Inexact Prox
• Abstract summary: We investigate the behavior of FedExProx without the assumption that each client computes a certain operator exactly. We show that inexactness leads to convergence to a neighborhood of the solution. Our theoretical insights are validated through comprehensive numerical experiments.
• Score: 55.2480439325792
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Enhancing the FedProx federated learning algorithm (Li et al., 2020) with server-side extrapolation, Li et al. (2024a) recently introduced the FedExProx method. Their theoretical analysis, however, relies on the assumption that each client computes a certain proximal operator exactly, which is impractical since this is virtually never possible to do in real settings. In this paper, we investigate the behavior of FedExProx without this exactness assumption in the smooth and globally strongly convex setting. We establish a general convergence result, showing that inexactness leads to convergence to a neighborhood of the solution. Additionally, we demonstrate that, with careful control, the adverse effects of this inexactness can be mitigated. By linking inexactness to biased compression (Beznosikov et al., 2023), we refine our analysis, highlighting robustness of extrapolation to inexact proximal updates. We also examine the local iteration complexity required by each client to achieved the required level of inexactness using various local optimizers. Our theoretical insights are validated through comprehensive numerical experiments.

Related papers

• When Do Fewer Visual Tokens Accelerate Multimodal Inference? A Break-Even Study Across Decision Locations and Hardware [1.2103414068933553]
  Fewer visual tokens do not guarantee lower end-to-end latency.<n>We evaluate break-even with a reproducible protocol that accounts for decision overhead, shared work, and the operators each policy can avoid.
  arXiv  Detail & Related papers  (2026-08-04T13:33:11Z)
• Nondeterminism-Aware Optimistic Verification for Floating-Point Neural Networks [11.159101812934503]
  Nondeterministic Aware Optimistic verification protocol for floating-point execution on heterogeneous accelerators.<n>We implement NAO as a PyTorch-compatible runtime and a contract layer currently deployed on Holesky testnet.
  arXiv  Detail & Related papers  (2025-10-15T21:10:39Z)
• FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data [17.80715992954134]
  Composite learning offers a general framework for solving machine learning problems with additional regularization terms. We propose FedCanon algorithm to solve possibly non-smooth regularization problems.
  arXiv  Detail & Related papers  (2025-04-16T09:28:26Z)
• The Power of Perturbation under Sampling in Solving Extensive-Form Games [56.013335390600524]
  This paper investigates how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in imperfect-information extensive-form games. Perturbing the expected payoffs guarantees that the FTRL dynamics reach an approximate equilibrium. We show that in the last-iterate sense, the FTRL consistently outperforms the non-samplinged FTRL.
  arXiv  Detail & Related papers  (2025-01-28T00:29:38Z)
• The Effect of Personalization in FedProx: A Fine-grained Analysis on Statistical Accuracy and Communication Efficiency [21.202284638968496]
  FedProx is a simple yet effective federated learning method that enables model personalization regularization. We show how FedProx can outperform pure local training and achieve a nearly minimax-optimal statistical rate.
  arXiv  Detail & Related papers  (2024-10-11T16:00:21Z)
• 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)
• On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyond [41.082982732100696]
  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.
  arXiv  Detail & Related papers  (2022-06-10T15:35:10Z)
• 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)
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times [51.61278695776151]
  Federated Learning (FL) is well known for its privacy protection when training machine learning models among distributed clients collaboratively. Recent studies have pointed out that the naive FL is susceptible to gradient leakage attacks. Differential Privacy (DP) emerges as a promising countermeasure to defend against gradient leakage attacks.
  arXiv  Detail & Related papers  (2021-01-11T19:43:12Z)
• Faster Non-Convex Federated Learning via Global and Local Momentum [57.52663209739171]
  textttFedGLOMO is the first (first-order) FLtexttFedGLOMO algorithm. Our algorithm is provably optimal even with communication between the clients and the server.
  arXiv  Detail & Related papers  (2020-12-07T21:05:31Z)
• Beyond the Mean-Field: Structured Deep Gaussian Processes Improve the Predictive Uncertainties [12.068153197381575]
  We propose a novel variational family that allows for retaining covariances between latent processes while achieving fast convergence. We provide an efficient implementation of our new approach and apply it to several benchmark datasets. It yields excellent results and strikes a better balance between accuracy and calibrated uncertainty estimates than its state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2020-05-22T11:10:59Z)
• Towards Streaming Perception [70.68520310095155]
  We present an approach that coherently integrates latency and accuracy into a single metric for real-time online perception. The key insight behind this metric is to jointly evaluate the output of the entire perception stack at every time instant. We focus on the illustrative tasks of object detection and instance segmentation in urban video streams, and contribute a novel dataset with high-quality and temporally-dense annotations.
  arXiv  Detail & Related papers  (2020-05-21T01:51:35Z)
• A Closer Look at Accuracy vs. Robustness [94.2226357646813]
  Current methods for training robust networks lead to a drop in test accuracy. We show that real image datasets are actually separated. We conclude that achieving robustness and accuracy in practice may require using methods that impose local Lipschitzness.
  arXiv  Detail & Related papers  (2020-03-05T07:09:32Z)
• Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networks [65.24701908364383]
  We show that a sufficient condition for a uncertainty on a ReLU network is "to be a bit Bayesian calibrated" We further validate these findings empirically via various standard experiments using common deep ReLU networks and Laplace approximations.
  arXiv  Detail & Related papers  (2020-02-24T08:52:06Z)

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.