Faster Non-Convex Federated Learning via Global and Local Momentum

• URL: http://arxiv.org/abs/2012.04061v3
• Date: Fri, 19 Feb 2021 22:57:58 GMT
• Title: Faster Non-Convex Federated Learning via Global and Local Momentum
• Authors: Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S. Dhillon, Ufuk Topcu
• Abstract summary: textttFedGLOMO is the first (first-order) FLtexttFedGLOMO algorithm. Our algorithm is provably optimal even with communication between the clients and the server.
• Score: 57.52663209739171
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose \texttt{FedGLOMO}, the first (first-order) FL algorithm that achieves the optimal iteration complexity (i.e matching the known lower bound) on smooth non-convex objectives -- without using clients' full gradient in each round. Our key algorithmic idea that enables attaining this optimal complexity is applying judicious momentum terms that promote variance reduction in both the local updates at the clients, and the global update at the server. Our algorithm is also provably optimal even with compressed communication between the clients and the server, which is an important consideration in the practical deployment of FL algorithms. Our experiments illustrate the intrinsic variance reduction effect of \texttt{FedGLOMO} which implicitly suppresses client-drift in heterogeneous data distribution settings and promotes communication-efficiency. As a prequel to \texttt{FedGLOMO}, we propose \texttt{FedLOMO} which applies momentum only in the local client updates. We establish that \texttt{FedLOMO} enjoys improved convergence rates under common non-convex settings compared to prior work, and with fewer assumptions.

Related papers

• Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clients [30.135431295658343]
  Federated learning (FL) aims to learn a common global model without exchanging or transferring the data that are stored locally at different clients. In this paper, we propose an efficient federated learning (AFL) framework called DeFedAvg. DeFedAvg is the first AFL algorithm that achieves the desirable linear speedup property, which indicates its high scalability.
  arXiv  Detail & Related papers  (2024-02-17T05:22:46Z)
• Towards Instance-adaptive Inference for Federated Learning [80.38701896056828]
  Federated learning (FL) is a distributed learning paradigm that enables multiple clients to learn a powerful global model by aggregating local training. In this paper, we present a novel FL algorithm, i.e., FedIns, to handle intra-client data heterogeneity by enabling instance-adaptive inference in the FL framework. Our experiments show that our FedIns outperforms state-of-the-art FL algorithms, e.g., a 6.64% improvement against the top-performing method with less than 15% communication cost on Tiny-ImageNet.
  arXiv  Detail & Related papers  (2023-08-11T09:58:47Z)
• Federated Learning for Semantic Parsing: Task Formulation, Evaluation Setup, New Algorithms [29.636944156801327]
  Multiple clients collaboratively train one global model without sharing their semantic parsing data. Lorar adjusts each client's contribution to the global model update based on its training loss reduction during each round. Clients with smaller datasets enjoy larger performance gains.
  arXiv  Detail & Related papers  (2023-05-26T19:25:49Z)
• Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape [59.841889495864386]
  In federated learning (FL), a cluster of local clients are chaired under the coordination of a global server. Clients are prone to overfit into their own optima, which extremely deviates from the global objective. ttfamily FedSMOO adopts a dynamic regularizer to guarantee the local optima towards the global objective. Our theoretical analysis indicates that ttfamily FedSMOO achieves fast $mathcalO (1/T)$ convergence rate with low bound generalization.
  arXiv  Detail & Related papers  (2023-05-19T10:47:44Z)
• FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy [84.45004766136663]
  Federated learning is an emerging distributed machine learning framework. It suffers from the non-vanishing biases introduced by the local inconsistent optimal and the rugged client-drifts by the local over-fitting. We propose a novel and practical method, FedSpeed, to alleviate the negative impacts posed by these problems.
  arXiv  Detail & Related papers  (2023-02-21T03:55:29Z)
• 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)
• DP-NormFedAvg: Normalizing Client Updates for Privacy-Preserving Federated Learning [48.064786028195506]
  We propose to have the clients send a textitfin quantized version of only the textitunit in terms of magnitude information. We also introduce QTDL, a new differentially private quantization mechanism for unitnorm.
  arXiv  Detail & Related papers  (2021-06-13T21:23:46Z)
• Efficient Algorithms for Federated Saddle Point Optimization [32.060759921090856]
  We consider strongly convex-concave minimax problems in the federated setting, where the communication constraint is the main bottleneck. Our goal is to design an algorithm that can harness the benefit of similarity in the clients while recovering the Minibatch Mirror-prox performance under arbitrary heterogeneity.
  arXiv  Detail & Related papers  (2021-02-12T02:55:36Z)
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning [102.26119328920547]
  Federated learning (FL) is a challenging setting for optimization due to the heterogeneity of the data across different clients. We propose a general algorithmic framework, Mime, which mitigates client drift and adapts arbitrary centralized optimization algorithms.
  arXiv  Detail & Related papers  (2020-08-08T21:55:07Z)

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.