Fast Convergence Algorithm for Analog Federated Learning

• URL: http://arxiv.org/abs/2011.06658v1
• Date: Fri, 30 Oct 2020 10:59:49 GMT
• Title: Fast Convergence Algorithm for Analog Federated Learning
• Authors: Shuhao Xia, Jingyang Zhu, Yuhan Yang, Yong Zhou, Yuanming Shi and Wei Chen
• Abstract summary: We propose an AirComp-based FedSplit algorithm for efficient analog federated learning over wireless channels. We prove that the proposed algorithm linearly converges to the optimal solutions under the assumption that the objective function is strongly convex and smooth. Our algorithm is theoretically and experimentally verified to be much more robust to the ill-conditioned problems with faster convergence compared with other benchmark FL algorithms.
• Score: 30.399830943617772
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider federated learning (FL) over a noisy fading multiple access channel (MAC), where an edge server aggregates the local models transmitted by multiple end devices through over-the-air computation (AirComp). To realize efficient analog federated learning over wireless channels, we propose an AirComp-based FedSplit algorithm, where a threshold-based device selection scheme is adopted to achieve reliable local model uploading. In particular, we analyze the performance of the proposed algorithm and prove that the proposed algorithm linearly converges to the optimal solutions under the assumption that the objective function is strongly convex and smooth. We also characterize the robustness of proposed algorithm to the ill-conditioned problems, thereby achieving fast convergence rates and reducing communication rounds. A finite error bound is further provided to reveal the relationship between the convergence behavior and the channel fading and noise. Our algorithm is theoretically and experimentally verified to be much more robust to the ill-conditioned problems with faster convergence compared with other benchmark FL algorithms.

Related papers

• Over-the-Air Federated Learning and Optimization [52.5188988624998]
  We focus on Federated learning (FL) via edge-the-air computation (AirComp) We describe the convergence of AirComp-based FedAvg (AirFedAvg) algorithms under both convex and non- convex settings. For different types of local updates that can be transmitted by edge devices (i.e., model, gradient, model difference), we reveal that transmitting in AirFedAvg may cause an aggregation error. In addition, we consider more practical signal processing schemes to improve the communication efficiency and extend the convergence analysis to different forms of model aggregation error caused by these signal processing schemes.
  arXiv  Detail & Related papers  (2023-10-16T05:49:28Z)
• Faster Adaptive Federated Learning [84.38913517122619]
  Federated learning has attracted increasing attention with the emergence of distributed data. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on momentum-based variance reduced technique in cross-silo FL.
  arXiv  Detail & Related papers  (2022-12-02T05:07:50Z)
• Time-triggered Federated Learning over Wireless Networks [48.389824560183776]
  We present a time-triggered FL algorithm (TT-Fed) over wireless networks. Our proposed TT-Fed algorithm improves the converged test accuracy by up to 12.5% and 5%, respectively.
  arXiv  Detail & Related papers  (2022-04-26T16:37:29Z)
• Over-the-Air Federated Learning via Second-Order Optimization [37.594140209854906]
  Federated learning (FL) could result in task-oriented data traffic flows over wireless networks with limited radio resources. We propose a novel over-the-air second-order federated optimization algorithm to simultaneously reduce the communication rounds and enable low-latency global model aggregation.
  arXiv  Detail & Related papers  (2022-03-29T12:39:23Z)
• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning [28.65635956111857]
  Federated learning (FL) enables edge devices to collaboratively train a global model without sharing their private data. To enhance the training efficiency of FL, various algorithms have been proposed, ranging from first-order computation to first-order methods.
  arXiv  Detail & Related papers  (2022-01-24T08:56:06Z)
• 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)
• AsySQN: Faster Vertical Federated Learning Algorithms with Better Computation Resource Utilization [159.75564904944707]
  We propose an asynchronous quasi-Newton (AsySQN) framework for vertical federated learning (VFL) The proposed algorithms make descent steps scaled by approximate without calculating the inverse Hessian matrix explicitly. We show that the adopted asynchronous computation can make better use of the computation resource.
  arXiv  Detail & Related papers  (2021-09-26T07:56:10Z)
• Over-the-Air Decentralized Federated Learning [28.593149477080605]
  We consider decentralized federated learning (FL) over wireless networks, where over-the-air computation (AirComp) is adopted to facilitate the local model consensus in a device-to-device (D2D) communication manner. We propose an AirComp-based DSGD with gradient tracking and variance reduction (DSGT-VR) algorithm, where both precoding and decoding strategies are developed for D2D communication. We prove that the proposed algorithm converges linearly and establish the optimality gap for strongly convex and smooth loss functions, taking into account the channel fading and noise.
  arXiv  Detail & Related papers  (2021-06-15T09:42:33Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  This letter investigates a channel assignment problem in uplink wireless communication systems. Our goal is to maximize the sum rate of all users subject to integer channel assignment constraints. Due to high computational complexity, machine learning approaches are employed to obtain computational efficient solutions.
  arXiv  Detail & Related papers  (2020-01-12T15:54:20Z)

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.