FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted Dual Averaging

• URL: http://arxiv.org/abs/2302.06103v1
• Date: Mon, 13 Feb 2023 05:10:30 GMT
• Title: FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted Dual Averaging
• Authors: Junyi Li, Feihu Huang, Heng Huang
• Abstract summary: Federated learning (FL) is an emerging learning paradigm to tackle massively distributed data. We propose textbfFedDA, a novel framework for local adaptive gradient methods. We show that textbfFedDA-MVR is the first adaptive FL algorithm that achieves this rate.
• Score: 104.41634756395545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated learning (FL) is an emerging learning paradigm to tackle massively distributed data. In Federated Learning, a set of clients jointly perform a machine learning task under the coordination of a server. The FedAvg algorithm is one of the most widely used methods to solve Federated Learning problems. In FedAvg, the learning rate is a constant rather than changing adaptively. The adaptive gradient methods show superior performance over the constant learning rate schedule; however, there is still no general framework to incorporate adaptive gradient methods into the federated setting. In this paper, we propose \textbf{FedDA}, a novel framework for local adaptive gradient methods. The framework adopts a restarted dual averaging technique and is flexible with various gradient estimation methods and adaptive learning rate formulations. In particular, we analyze \textbf{FedDA-MVR}, an instantiation of our framework, and show that it achieves gradient complexity $\tilde{O}(\epsilon^{-1.5})$ and communication complexity $\tilde{O}(\epsilon^{-1})$ for finding a stationary point $\epsilon$. This matches the best known rate for first-order FL algorithms and \textbf{FedDA-MVR} is the first adaptive FL algorithm that achieves this rate. We also perform extensive numerical experiments to verify the efficacy of our method.

Related papers

• Towards Hyper-parameter-free Federated Learning [1.3682156035049038]
  We introduce algorithms for automated scaling of global model updates. In first algorithm, we establish that a descent-ensuring step-size regime at the clients ensures descent for the server objective. Second algorithm shows that the average of objective values of sampled clients is a practical and effective substitute for the value server required for computing the scaling factor.
  arXiv  Detail & Related papers  (2024-08-30T09:35:36Z)
• Fed-Sophia: A Communication-Efficient Second-Order Federated Learning Algorithm [28.505671833986067]
  Federated learning is a machine learning approach where multiple devices collaboratively learn with the help of a parameter server by sharing only their local updates. While gradient-based optimization techniques are widely adopted in this domain, the curvature information that second-order methods exhibit is crucial to guide and speed up the convergence. This paper introduces a scalable second-order method, allowing the adoption of curvature information in federated large models.
  arXiv  Detail & Related papers  (2024-06-10T09:57:30Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  We propose a federated version of adaptive gradient methods, particularly AdaGrad and Adam, within the framework of over-the-air model training. Our analysis shows that the AdaGrad-based training algorithm converges to a stationary point at the rate of $mathcalO( ln(T) / T 1 - frac1alpha ).
  arXiv  Detail & Related papers  (2024-03-11T09:10:37Z)
• Preconditioned Federated Learning [7.7269332266153326]
  Federated Learning (FL) is a distributed machine learning approach that enables model training in communication efficient and privacy-preserving manner. FedAvg has been considered to lack algorithm adaptivity compared to modern first-order adaptive optimizations. We propose new communication-efficient FL algortithms based on two adaptive frameworks: local adaptivity (PreFed) and server-side adaptivity (PreFedOp)
  arXiv  Detail & Related papers  (2023-09-20T14:58:47Z)
• 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)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  We propose an efficient adaptive minimax optimization algorithm (i.e., AdaFGDA) to solve these minimax problems. It builds our momentum-based reduced and localSGD techniques, and it flexibly incorporate various adaptive learning rates.
  arXiv  Detail & Related papers  (2022-11-14T12:32:18Z)
• Local Stochastic Bilevel Optimization with Momentum-Based Variance Reduction [104.41634756395545]
  We study Federated Bilevel Optimization problems. Specifically, we first propose the FedBiO, a deterministic gradient-based algorithm. We show FedBiO has complexity of $O(epsilon-1.5)$. Our algorithms show superior performances compared to other baselines in numerical experiments.
  arXiv  Detail & Related papers  (2022-05-03T16:40:22Z)
• SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients [99.13839450032408]
  It is desired to design a universal framework for adaptive algorithms to solve general problems. In particular, our novel framework provides adaptive methods under non convergence support for setting.
  arXiv  Detail & Related papers  (2021-06-15T15:16:28Z)
• Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach [11.986523531539165]
  Federated learning (FL) is an emerging technique for training machine learning models using geographically dispersed data. gradient sparsification (GS) can be applied, where instead of the full gradient, only a small subset of important elements of the gradient is communicated. We propose a novel online learning formulation and algorithm for automatically determining the near-optimal communication and trade-off.
  arXiv  Detail & Related papers  (2020-01-14T13:09: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.