FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning

• URL: http://arxiv.org/abs/2401.02734v1
• Date: Fri, 5 Jan 2024 10:06:41 GMT
• Title: FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning
• Authors: Jian Li, Yong Liu, Wei Wang, Haoran Wu, Weiping Wang
• Abstract summary: We introduce a novel approach to tackle this issue while still achieving fast convergence rates. Our proposed method, named as Federated Newton Sketch methods (FedNS), approximates the centralized Newton's method by communicating the sketched square-root Hessian instead of the exact Hessian. We provide convergence analysis based on statistical learning for the federated Newton sketch approaches.
• Score: 27.957498393822338
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent Newton-type federated learning algorithms have demonstrated linear convergence with respect to the communication rounds. However, communicating Hessian matrices is often unfeasible due to their quadratic communication complexity. In this paper, we introduce a novel approach to tackle this issue while still achieving fast convergence rates. Our proposed method, named as Federated Newton Sketch methods (FedNS), approximates the centralized Newton's method by communicating the sketched square-root Hessian instead of the exact Hessian. To enhance communication efficiency, we reduce the sketch size to match the effective dimension of the Hessian matrix. We provide convergence analysis based on statistical learning for the federated Newton sketch approaches. Specifically, our approaches reach super-linear convergence rates w.r.t. the communication rounds for the first time. We validate the effectiveness of our algorithms through various experiments, which coincide with our theoretical findings.

Related papers

• FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch [3.4927288761640565]
  We introduce Federated Learning with Enhanced Nesterov-Newton Sketch (FLeNS) FLeNS approximates the centralized Newton's method without relying on the exact Hessian. We provide rigorous convergence guarantees and characterize tradeoffs between acceleration, sketch size, and convergence speed.
  arXiv  Detail & Related papers  (2024-09-23T17:00:35Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework.
  arXiv  Detail & Related papers  (2024-02-04T05:54:51Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  Decentralized minimax optimization has been actively studied in the past few years due to its application in a wide range machine learning. This paper develops two novel decentralized minimax optimization algorithms for the non-strongly-nonconcave problem.
  arXiv  Detail & Related papers  (2023-04-24T02:19:39Z)
• 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)
• FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning [75.46959684676371]
  We introduce a novel framework called FedNew in which there is no need to transmit Hessian information from clients to PS. FedNew hides the gradient information and results in a privacy-preserving approach compared to the existing state-of-the-art.
  arXiv  Detail & Related papers  (2022-06-17T15:21:39Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Distributed Second Order Methods with Fast Rates and Compressed Communication [6.069611493148631]
  We develop several new communication-efficient second-order methods for distributed optimization. We prove global sublinear and linear convergence rates, and a fast superlinear rate. Our results are supported with experimental results on real datasets.
  arXiv  Detail & Related papers  (2021-02-14T14:06:45Z)
• DONE: Distributed Approximate Newton-type Method for Federated Edge Learning [41.20946186966816]
  DONE is a distributed approximate Newton-type algorithm with fast convergence rate. We show DONE attains a comparable performance to the Newton's method.
  arXiv  Detail & Related papers  (2020-12-10T12:25:34Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  We propose a novel end-to-end learning-based framework to generate dense point clouds. We first formulate the problem explicitly, which boils down to determining the weights and high-order approximation errors. Then, we design a lightweight neural network to adaptively learn unified and sorted weights as well as the high-order refinements.
  arXiv  Detail & Related papers  (2020-11-25T14:00:18Z)
• On Newton Screening [14.040371216692645]
  We develop a new screening method called Newton screening (NS) which is a generalized Newton method with a built-in screening mechanism. We show that NS possesses an optimal convergence property in the sense that it achieves one-step local convergence.
  arXiv  Detail & Related papers  (2020-01-27T11:25:33Z)

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.