# Newton-like method with diagonal correction for distributed optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2015.

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

- [Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03263/) (2022)
- [Network-GIANT: Fully distributed Newton-type optimization via harmonic Hessian consensus](https://mlsanity.com/paper/2305.07898/) (2023)
- [A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints](https://mlsanity.com/paper/2409.04998/) (2024)

## Abstract (arXiv)

We consider distributed optimization problems where networked nodes cooperatively minimize the sum of their locally known convex costs. A popular class of methods to solve these problems are the distributed gradient methods, which are attractive due to their inexpensive iterations, but have a drawback of slow convergence rates. This motivates the incorporation of second-order information in the distributed methods, but this task is challenging: although the Hessians which arise in the algorithm design respect the sparsity of the network, their inverses are dense, hence rendering distributed implementations difficult. We overcome this challenge and propose a class of distributed Newton-like methods, which we refer to as Distributed Quasi Newton (DQN). The DQN family approximates the Hessian inverse by: 1) splitting the Hessian into its diagonal and off-diagonal part, 2) inverting the diagonal part, and 3) approximating the inverse of the off-diagonal part through a weighted linear function. The approximation is parameterized by the tuning variables which correspond to different splittings of the Hessian and by different weightings of the off-diagonal Hessian part. Specific choices of the tuning variables give rise to different variants of the proposed general DQN method -- dubbed DQN-0, DQN-1 and DQN-2 -- which mutually trade-off communication and computational costs for convergence. Simulations demonstrate the effectiveness of the proposed DQN methods.