In decentralized optimization, a network of agents must minimize a global cost function where each agent only knows its local objective. Traditionally, these networks rely on first-order methods like decentralized gradient descent. While simple to implement, these methods suffer from slow convergence, especially when the problem is ill-conditioned.
The "gold standard" for speed in optimization is Newton’s method, which uses second-order curvature (the Hessian) to take more direct steps toward the optimum. However, Newton’s method requires inverting the Hessian matrix. In a decentralized setting, even if the Hessian itself is sparse (reflecting the network's connectivity), its inverse is typically dense. This means that to calculate a single Newton step, every node would need to communicate with every other node in the network, destroying the decentralized nature of the system.
A growing body of research, led by Aryan Mokhtari, Alejandro Ribeiro, and Qing Ling, addresses this by using truncated Taylor series expansions to approximate the Hessian inverse using only local communication.
The Sparsity vs. Inversion Dilemma
In a consensus optimization problem, we want to minimize $\sum f_i(x)$. When we apply a penalty method to ensure all agents reach the same $x$, the resulting Hessian $H$ often takes the form $H = D + A$, where $D$ is a block-diagonal matrix of local Hessians and $A$ represents the network structure.
The matrix $H$ is "neighbor-sparse"—a node only needs information from its direct neighbors to know its part of $H$. However, the Newton direction requires $H^{-1}$. The inverse of a sparse matrix is almost always dense. To compute it exactly, a node in a sensor network in California would need data from a node in New York.
Approximating the Inverse Locally
The key insight shared across these papers is that we can approximate the inverse of a matrix using a Taylor series (also known as a Neumann series). If we can write the Hessian in the form $H = B(I - M)$, then:
$$H^{-1} \approx B^{-1} (I + M + M^2 + \dots + M^K)$$
In Network Newton-Part II, the authors show that if $M$ follows the sparsity of the network graph, then $M^K$ represents information from nodes exactly $K$ hops away. By truncating the series at a small $K$, an agent can compute a "Newton-like" step by communicating only with its $K$-hop neighborhood.
This mechanism transforms a global algebraic problem (matrix inversion) into a local communication problem (multi-hop gossip). As Andrea Simonetto and colleagues demonstrate in Decentralized Prediction-Correction Methods, this allows networks to track time-varying optimal solutions with much higher precision than first-order methods, as the Taylor approximation captures enough curvature to anticipate the objective's movement.
Tunable Communication and Convergence
This approach introduces a fundamental trade-off: communication cost vs. optimization accuracy.
- $K=0$: The approximation is purely local (like a gradient method).
- Small $K$: Nodes talk to near neighbors, gaining a "blurry" view of the global curvature.
- Large $K$: The approximation approaches the true Newton step, but communication costs rise.
In A Decentralized Second-Order Method with Exact Linear Convergence Rate (ESOM), Aryan Mokhtari and Wei Shi prove that even a small, fixed $K$ is sufficient to achieve an exact linear convergence rate. This means we don't need a perfect Hessian inverse to get the benefits of second-order optimization; a "good enough" local approximation is sufficient to outperform gradient descent.
Expanding to Quasi-Newton and ADMM
The Taylor series trick is versatile and has been integrated into various optimization frameworks:
- ADMM: Yichuan Li and Petros G. Voulgaris introduced DN-ADMM, which uses the Taylor expansion to speed up the subproblem steps in the Alternating Direction Method of Multipliers.
- Quasi-Newton: For problems where calculating the second derivative is too expensive, Decentralized Quasi-Newton Methods like D-BFGS maintain a local estimate of the Hessian that is constrained to match the network's sparsity. Huikang Liu and Qing Ling further extended this to stochastic environments, combining variance reduction with curvature estimation.
- Asynchrony: Ermin Wei and Fatemeh Mansoori showed in A Fast Distributed Asynchronous Newton-Based Optimization Algorithm that these matrix-splitting and Taylor techniques can even work without a global clock, allowing agents to update at their own pace while still achieving local quadratic convergence.
By approximating the global inverse through local power series, these methods bridge the gap between the theoretical speed of centralized second-order optimization and the practical constraints of decentralized hardware.