Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable

• URL: http://arxiv.org/abs/2503.20117v2
• Date: Tue, 03 Jun 2025 18:32:53 GMT
• Title: Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable
• Authors: Bicheng Ying, Zhe Li, Haibo Yang,
• Abstract summary: This work tackles the fundamental challenges in Federated Learning (FL)<n>It is well-established that popular FedAvg-style algorithms struggle with exact convergence.<n>We present FOCUS, Federated Optimization with Exact Convergence via Push-pull Strategy, a provably convergent algorithm.
• Score: 9.870718388000645
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work tackles the fundamental challenges in Federated Learning (FL) posed by arbitrary client participation and data heterogeneity, prevalent characteristics in practical FL settings. It is well-established that popular FedAvg-style algorithms struggle with exact convergence and can suffer from slow convergence rates since a decaying learning rate is required to mitigate these scenarios. To address these issues, we introduce the concept of stochastic matrix and the corresponding time-varying graphs as a novel modeling tool to accurately capture the dynamics of arbitrary client participation and the local update procedure. Leveraging this approach, we offer a fresh perspective on designing FL algorithms, provide a rigorous quantitative analysis of the limitations inherent in the FedAvg algorithm, and present FOCUS, Federated Optimization with Exact Convergence via Push-pull Strategy, a provably convergent algorithm designed to effectively overcome the previously mentioned two challenges. More specifically, we provide a rigorous proof demonstrating that FOCUS achieves exact convergence with a linear rate regardless of the arbitrary client participation, establishing it as the first work to demonstrate this significant result.

Related papers

• Sociodynamics-inspired Adaptive Coalition and Client Selection in Federated Learning [39.58317527488534]
  We introduce shortname (Federated Coalition Variance Reduction with Boltzmann Exploration), a variance-reducing algorithm inspired by opinion dynamics over temporal social networks.<n>Our experiments show that in heterogeneous scenarios our algorithm outperforms existing FL algorithms, yielding more accurate results and faster convergence.
  arXiv  Detail & Related papers  (2025-06-03T14:04:31Z)
• Personalized Federated Learning under Model Dissimilarity Constraints [8.095373104009868]
  KARULA is a regularized strategy for personalized federated learning that constrains the pairwise model dissimilarities between clients based on the difference in their distributions.<n>We show theoretically that KARULA converges with smooth, possibly nonrelations losses to a neighborhood rate stationary point with O (1/K)<n>We demonstrate KARULA on synthetic and real data sets sets the effectiveness of the strategy for highly complex interrelations.
  arXiv  Detail & Related papers  (2025-05-12T13:54:55Z)
• Federated Smoothing ADMM for Localization [9.25126455172971]
  Federated systems are characterized by distributed data, non-smoothity, and non-smoothness.<n>We propose a robust algorithm to tackle the scalability and outlier issues inherent in such environments.<n>To validate the reliability of the proposed algorithm, we show that it converges to a stationary point.<n> numerical simulations highlight its superior performance in convergence resilience compared to existing state-of-the-art localization methods.
  arXiv  Detail & Related papers  (2025-03-12T16:01:34Z)
• Client-Centric Federated Adaptive Optimization [78.30827455292827]
  Federated Learning (FL) is a distributed learning paradigm where clients collaboratively train a model while keeping their own data private.<n>We propose Federated-Centric Adaptive Optimization, which is a class of novel federated optimization approaches.
  arXiv  Detail & Related papers  (2025-01-17T04:00:50Z)
• Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration [66.43954501171292]
  We introduce Catalyst Acceleration and propose an acceleration Decentralized Federated Learning algorithm called DFedCata. DFedCata consists of two main components: the Moreau envelope function, which addresses parameter inconsistencies, and Nesterov's extrapolation step, which accelerates the aggregation phase. Empirically, we demonstrate the advantages of the proposed algorithm in both convergence speed and generalization performance on CIFAR10/100 with various non-iid data distributions.
  arXiv  Detail & Related papers  (2024-10-09T06:17:16Z)
• Federated Learning with Dynamic Client Arrival and Departure: Convergence and Rapid Adaptation via Initial Model Construction [24.71144869427636]
  Most federated learning approaches assume a fixed client set.<n>Realworld scenarios often involve clients joining or leaving the system based on their needs or interest in specific tasks.<n>We propose an algorithm that enables rapid adaptation to new client sets whenever clients join or leave the system.
  arXiv  Detail & Related papers  (2024-10-08T03:22:14Z)
• Aiding Global Convergence in Federated Learning via Local Perturbation and Mutual Similarity Information [6.767885381740953]
  Federated learning has emerged as a distributed optimization paradigm. We propose a novel modified framework wherein each client locally performs a perturbed gradient step. We show that our algorithm speeds convergence up to a margin of 30 global rounds compared with FedAvg.
  arXiv  Detail & Related papers  (2024-10-07T23:14:05Z)
• Decentralized Directed Collaboration for Personalized Federated Learning [39.29794569421094]
  We concentrate on the Decentralized Personalized Learning (DPFL) that performs distributed training model computation. We propose a directed collaboration framework by incorporating textbfDecentralized textbfFederated textbfPartial textbfGradient textbfPedGP.
  arXiv  Detail & Related papers  (2024-05-28T06:52:19Z)
• FedCAda: Adaptive Client-Side Optimization for Accelerated and Stable Federated Learning [57.38427653043984]
  Federated learning (FL) has emerged as a prominent approach for collaborative training of machine learning models across distributed clients. We introduce FedCAda, an innovative federated client adaptive algorithm designed to tackle this challenge. We demonstrate that FedCAda outperforms the state-of-the-art methods in terms of adaptability, convergence, stability, and overall performance.
  arXiv  Detail & Related papers  (2024-05-20T06:12:33Z)
• FedEGG: Federated Learning with Explicit Global Guidance [90.04705121816185]
  Federated Learning (FL) holds great potential for diverse applications owing to its privacy-preserving nature.<n>Existing methods help address these challenges via optimization-based client constraints, adaptive client selection, or the use of pre-trained models or synthetic data.<n>We present bftextFedEGG, a new FL algorithm that constructs a global guiding task using a well-defined, easy-to-converge learning task.
  arXiv  Detail & Related papers  (2024-04-18T04:25:21Z)
• 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)
• On the Power of Adaptive Weighted Aggregation in Heterogeneous Federated Learning and Beyond [37.894835756324454]
  Federated averaging (FedAvg) is the most fundamental algorithm in Federated learning (FL)<n>Recent empirical results show that FedAvg can perform well in many real-world heterogeneous tasks.<n>We present a simple and effective FedAvg variant termed FedAWARE.
  arXiv  Detail & Related papers  (2023-10-04T10:15:57Z)
• Momentum Benefits Non-IID Federated Learning Simply and Provably [22.800862422479913]
  Federated learning is a powerful paradigm for large-scale machine learning. FedAvg and SCAFFOLD are two prominent algorithms to address these challenges. This paper explores the utilization of momentum to enhance the performance of FedAvg and SCAFFOLD.
  arXiv  Detail & Related papers  (2023-06-28T18:52:27Z)
• Federated Conformal Predictors for Distributed Uncertainty Quantification [83.50609351513886]
  Conformal prediction is emerging as a popular paradigm for providing rigorous uncertainty quantification in machine learning. In this paper, we extend conformal prediction to the federated learning setting. We propose a weaker notion of partial exchangeability, better suited to the FL setting, and use it to develop the Federated Conformal Prediction framework.
  arXiv  Detail & Related papers  (2023-05-27T19:57:27Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Federated Learning as Variational Inference: A Scalable Expectation Propagation Approach [66.9033666087719]
  This paper extends the inference view and describes a variational inference formulation of federated learning. We apply FedEP on standard federated learning benchmarks and find that it outperforms strong baselines in terms of both convergence speed and accuracy.
  arXiv  Detail & Related papers  (2023-02-08T17:58:11Z)
• 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)
• On the Convergence of Heterogeneous Federated Learning with Arbitrary Adaptive Online Model Pruning [15.300983585090794]
  We present a unifying framework for heterogeneous FL algorithms with em arbitrary adaptive online model pruning. In particular, we prove that under certain sufficient conditions, these algorithms converge to a stationary point of standard FL for general smooth cost functions. We illuminate two key factors impacting convergence: pruning-induced noise and minimum coverage index.
  arXiv  Detail & Related papers  (2022-01-27T20:43:38Z)
• 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)
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization [93.78811018928583]
  This paper provides a framework to analyze the convergence of federated heterogeneous optimization algorithms. We propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.
  arXiv  Detail & Related papers  (2020-07-15T05:01:23Z)

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.