# Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 49 references that are in the map.
- First posted on arXiv 17 Mar 2021.

## Builds on (most cited first, 30 of 37)

- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [Personalized Federated Learning: A Meta-Learning Approach](https://mlsanity.com/paper/2002.07948/) (2020)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [ATOMO: Communication-efficient Learning via Atomic Sparsification](https://mlsanity.com/paper/1806.04090/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Communication-efficient distributed SGD with Sketching](https://mlsanity.com/paper/1903.04488/) (2019)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent](https://mlsanity.com/paper/1705.05491/) (2017)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning](https://mlsanity.com/paper/1806.05358/) (2018)
- [No bad local minima: Data independent training error guarantees for multilayer neural networks](https://mlsanity.com/paper/1605.08361/) (2016)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [Gradient Descent Converges to Minimizers](https://mlsanity.com/paper/1602.04915/) (2016)
- [Distributed Newton Can Communicate Less and Resist Byzantine Workers](https://mlsanity.com/paper/2006.08737/) (2020)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)

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

- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [Optimal Compression of Unit Norm Vectors in the High Distortion Regime](https://mlsanity.com/paper/2307.07941/) (2023)
- [Personalized Federated Learning Techniques: Empirical Analysis](https://mlsanity.com/paper/2409.06805/) (2024)

## Abstract (arXiv)

The problem of saddle-point avoidance for non-convex optimization is quite challenging in large scale distributed learning frameworks, such as Federated Learning, especially in the presence of Byzantine workers. The celebrated cubic-regularized Newton method of citenest is one of the most elegant ways to avoid saddle-points in the standard centralized (non-distributed) setup. In this paper, we extend the cubic-regularized Newton method to a distributed framework and simultaneously address several practical challenges like communication bottleneck and Byzantine attacks. Note that the issue of saddle-point avoidance becomes more crucial in the presence of Byzantine machines since rogue machines may create fake local minima near the saddle-points of the loss function, also known as the saddle-point attack. Being a second order algorithm, our iteration complexity is much lower than the first order counterparts. Furthermore we use compression (or sparsification) techniques like δ-approximate compression for communication efficiency. We obtain theoretical guarantees for our proposed scheme under several settings including approximate (sub-sampled) gradients and Hessians. Moreover, we validate our theoretical findings with experiments using standard datasets and several types of Byzantine attacks, and obtain an improvement of 25% with respect to first order methods in iteration complexity.