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

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 46 references that are in the map.
- First posted on arXiv 5 Jan 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [The Non-IID Data Quagmire of Decentralized Machine Learning](https://mlsanity.com/paper/1910.00189/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms](https://mlsanity.com/paper/1801.07226/) (2018)
- [Distributed Newton Can Communicate Less and Resist Byzantine Workers](https://mlsanity.com/paper/2006.08737/) (2020)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [A Non-parametric View of FedAvg and FedProx: Beyond Stationary Points](https://mlsanity.com/paper/2106.15216/) (2021)
- [SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing](https://mlsanity.com/paper/2202.05800/) (2022)
- [Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization](https://mlsanity.com/paper/2006.05874/) (2020)
- [Leveraging Low-Rank Relations Between Surrogate Tasks in Structured Prediction](https://mlsanity.com/paper/1903.00667/) (2019)

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

- [Distributed Quasi-Newton Method for Fair and Fast Federated Learning](https://mlsanity.com/paper/2501.10877/) (2025)
- [FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch](https://mlsanity.com/paper/2409.15216/) (2024)
- [Accelerated Training of Federated Learning via Second-Order Methods](https://mlsanity.com/paper/2505.23588/) (2025)

## Abstract (arXiv)

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.