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

arXiv: https://arxiv.org/abs/2111.01847 · HTML: https://mlsanity.com/paper/2111.01847/

## Key facts

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

## Builds on (most cited first, 26 of 26)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees](https://mlsanity.com/paper/2006.14591/) (2020)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [A Double Residual Compression Algorithm for Efficient Distributed Learning](https://mlsanity.com/paper/1910.07561/) (2019)
- [Quantized Adam with Error Feedback](https://mlsanity.com/paper/2004.14180/) (2020)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates](https://mlsanity.com/paper/1912.01597/) (2019)
- [DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization](https://mlsanity.com/paper/1901.05134/) (2019)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [Error Compensated Loopless SVRG, Quartz, and SDCA for Distributed Optimization](https://mlsanity.com/paper/2109.10049/) (2021)

## Built on by (most cited first, 15 of 15)

- [Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updates](https://mlsanity.com/paper/2310.19807/) (2023)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing](https://mlsanity.com/paper/2202.05800/) (2022)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEs](https://mlsanity.com/paper/2502.17009/) (2025)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [FAGH: Accelerating Federated Learning with Approximated Global Hessian](https://mlsanity.com/paper/2403.11041/) (2024)
- [Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions](https://mlsanity.com/paper/2603.23472/) (2026)
- [Adaptive pruning-based Newton's method for distributed learning](https://mlsanity.com/paper/2308.10154/) (2023)
- [A second-order-like optimizer with adaptive gradient scaling for deep learning](https://mlsanity.com/paper/2410.05871/) (2024)
- [Accelerated Training of Federated Learning via Second-Order Methods](https://mlsanity.com/paper/2505.23588/) (2025)

## 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.