mlsanityData to 7 Oct 2026

Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning

arXiv 2111.01847 ↗First posted 2 Nov 2021cs.LG math.OCcited by 14

Not on the map. Why?

Abstract (arXiv)

Recent advances in distributed optimization have shown that Newton-type methods with proper communication compression mechanisms can guarantee fast local rates and low communication cost compared to first order methods. We discover that the communication cost of these methods can be further reduced, sometimes dramatically so, with a surprisingly simple trick: em Basis Learn (BL). The idea is to transform the usual representation of the local Hessians via a change of basis in the space of matrices and apply compression tools to the new representation. To demonstrate the potential of using custom bases, we design a new Newton-type method (BL1), which reduces communication cost via both em BL technique and bidirectional compression mechanism. Furthermore, we present two alternative extensions (BL2 and BL3) to partial participation to accommodate federated learning applications. We prove local linear and superlinear rates independent of the condition number. Finally, we support our claims with numerical experiments by comparing several first and second~order~methods.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 26 of its 41 references that are in the map. First posted on arXiv 2 Nov 2021.

Builds on

26 of 41 references.

References · 26

  1. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  2. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  3. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  4. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  5. 2018The Convergence of Sparsified Gradient Methodscited by 228
  6. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 199
  7. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  8. 2020On Biased Compression for Distributed Learningcited by 140
  9. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  10. 2019Distributed Learning with Compressed Gradient Differencescited by 110
  11. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  12. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
14 more
  1. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  2. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 50
  3. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 45
  4. 2017GIANT: Globally Improved Approximate Newton Method for Distributed Optimizationcited by 43
  5. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 42
  6. 2019A Double Residual Compression Algorithm for Efficient Distributed Learningcited by 31
  7. 2020Quantized Adam with Error Feedbackcited by 27
  8. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  9. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
  10. 2019DINGO: Distributed Newton-Type Method for Gradient-Norm Optimizationcited by 20
  11. 2021Distributed Learning Systems with First-order Methodscited by 17
  12. 2021LocalNewton: Reducing Communication Bottleneck for Distributed Learningcited by 15
  13. 2021Communication-Efficient Distributed Optimization with Quantized Preconditionerscited by 8
  14. 2021Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimizationcited by 4

Built on by

Cited by year

Citing papers per year: 2022: 5; 2023: 3; 2024: 4; 2025: 2.

14 papers.

Sort:

  1. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 20
  2. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  3. 2022Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergencecited by 14
  4. 2022SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharingcited by 11
  5. 2022Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregationcited by 11
  6. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  7. 2024Towards Faster Decentralized Stochastic Optimization with Communication Compressioncited by 4
  8. 2025Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEscited by 4
  9. 2022FedSSO: A Federated Server-Side Second-Order Optimization Algorithmcited by 3
  10. 2024Review of Mathematical Optimization in Federated Learningcited by 3
  11. 2024FAGH: Accelerating Federated Learning with Approximated Global Hessiancited by 1
  12. 2023Adaptive pruning-based Newton's method for distributed learningcited by 0
2 more
  1. 2024A second-order-like optimizer with adaptive gradient scaling for deep learningcited by 0
  2. 2025Accelerated Training of Federated Learning via Second-Order Methodscited by 0