Abstract
This paper considers the decentralized consensus optimization problem defined over a network where each node holds a second-order differentiable local objective function. Our goal is to minimize the summation of local objective functions and find the exact optimal solution using only local computation and neighboring communication. We propose a novel Newton tracking algorithm, where each node updates its local variable along a local Newton direction modified with neighboring and historical information. We investigate the connections between the proposed Newton tracking algorithm and several existing methods, including gradient tracking and second-order algorithms. Under the strong convexity assumption, we prove that it converges to the exact optimal solution at a linear rate. Numerical experiments demonstrate the efficacy of Newton tracking and validate the theoretical findings.
Introduction
In decentralized consensus optimization, a network of nodes collaborates to minimize a global objective function that is the sum of local, private functions. This setup is common in large-scale machine learning where data is distributed across multiple devices. The primary challenge in this field is balancing accuracy, convergence speed, and communication costs.
Existing approaches often fall into two categories:
- First-order methods: Simple to implement but typically require diminishing step sizes to reach an exact solution, leading to slow convergence.
- Gradient Tracking methods: These achieve linear convergence with fixed step sizes but are limited by only using first-order information.
- Second-order methods: While potentially faster in terms of iterations, many existing decentralized second-order methods either converge only to a neighborhood of the solution or involve expensive inner communication loops.
This paper introduces Newton Tracking, a method designed to be both exact and fast by leveraging second-order information while maintaining efficient communication.
Methodology
The proposed Newton Tracking algorithm enables nodes to update their local variables along a modified Newton direction. Key features include:
- Tracking Mechanism: Each node maintains a local estimate of the global Newton direction, updated recursively using its previous direction, changes in local gradients, and a "consensus error" term from neighbors.
- Regularized Local Hessians: To ensure stability in early stages, the algorithm employs a regularized local Hessian ($\nabla^2 f_i + \epsilon I$).
- Primal-Dual Interpretation: The authors establish a mathematical equivalence between Newton Tracking and a linearized version of the Augmented Lagrangian method, facilitating a rigorous primal-dual convergence analysis.
- Fixed Step Size: The algorithm utilizes a unit step size for variable updates, avoiding the complexities of vanishing step sizes.
Results and Discussion
The algorithm was evaluated using decentralized logistic regression across various network topologies, including line, cycle, random, and complete graphs.
Convergence and Efficiency
Newton Tracking demonstrates a clear advantage in both convergence speed and communication efficiency. Under the assumption of strong convexity, the algorithm is theoretically guaranteed to converge to the exact optimal solution at a linear rate.
As shown in Figure 1, Newton Tracking significantly reduces the number of communication rounds required to reach high precision compared to other second-order methods like DQM and ESOM. This is particularly important in networked systems where communication is often the primary bottleneck.
Furthermore, Figure 3 illustrates that Newton Tracking outperforms popular first-order methods such as EXTRA, DLM, and standard Gradient Tracking in both the number of iterations and total runtime to achieve a relative error of $10^{-10}$.
Topology Sensitivity
The performance of the algorithm is sensitive to the network's spectral properties. Denser, better-connected graphs (e.g., complete graphs) facilitate faster information spread and thus quicker convergence, a relationship quantified by the authors' theoretical bounds on the convergence factor.
Conclusion
Newton Tracking represents a significant advancement in decentralized optimization, providing a second-order method that achieves exact linear convergence with high communication efficiency. While the method requires computing and inverting a Hessian matrix—which may be challenging for extremely high-dimensional problems—it offers a superior trade-off for many practical scenarios. Future work may explore extensions to non-convex problems and asynchronous communication environments.
Summary updated