Distributed Quasi-Newton Method for Multi-Agent Optimization

Ola Shorinwa, Mac Schwager

Abstract

Distributed optimization is a cornerstone of modern multi-agent systems, yet existing methods often struggle with the trade-off between computational complexity and convergence speed, particularly in "ill-conditioned" scenarios. This paper presents DQN and EC-DQN, two novel distributed algorithms that utilize quasi-Newton updates to capture global curvature information without the prohibitive costs of standard second-order methods. By employing gradient tracking and direct inverse Hessian estimation, these algorithms achieve up to a ten-fold reduction in communication costs compared to state-of-the-art techniques while maintaining robust performance across diverse benchmarks.

Introduction

In decentralized networks—ranging from autonomous robot swarms to distributed sensor arrays—agents must frequently collaborate to minimize a global objective function. The primary constraint in these environments is that each agent possesses only local data and can communicate solely with immediate neighbors.

While first-order methods like Gradient Descent are popular due to their simplicity, they are notoriously inefficient when faced with "ill-conditioned" problems—landscapes characterized by narrow, steep valleys where gradients provide poor guidance toward the optimum. Conversely, second-order methods like Newton’s Method offer superior convergence by utilizing the Hessian (curvature) of the objective function. However, calculating and inverting the Hessian in a distributed manner is traditionally computationally expensive and communication-intensive. This research bridges the gap by introducing a Distributed Quasi-Newton (DQN) framework that approximates second-order benefits with first-order communication overhead.

The DQN and EC-DQN Framework

The researchers developed two distinct algorithms to address different optimization needs:

  1. DQN (Distributed Quasi-Newton): Designed for unconstrained optimization problems.
  2. EC-DQN (Equality-Constrained DQN): Tailored for problems involving linear constraints, such as $Ax = b$.

Technical Innovations

The efficiency of these algorithms stems from three core architectural choices:

  • Aggregate Hessian Estimation: Unlike previous quasi-Newton methods (e.g., D-BFGS) that rely on local curvature, DQN utilizes gradient tracking (dynamic average consensus). This allows every agent to maintain an estimate of the aggregate gradient and Hessian of the entire network, providing a global perspective of the optimization landscape.
  • Direct Inverse Estimation: A major bottleneck in Newton-like methods is the $O(n^3)$ cost of matrix inversion. DQN bypasses this by directly estimating the inverse Hessian. This significantly reduces the computational burden on individual agents.
  • KKT-like Updates: For constrained scenarios, EC-DQN employs a Lagrangian-based approach. By satisfying Karush-Kuhn-Tucker (KKT) conditions directly, the algorithm avoids the need for complex and iterative projection procedures, streamlining the path to feasibility and optimality.

Experimental Evaluation

The algorithms were benchmarked against several state-of-the-art methods (including DIGing, ABm, ESOM, and D-Newton) across three primary mathematical domains:

  • Quadratic Programming (QP): Used to establish baseline stability and convergence speed.
  • Logistic Regression: Tested with both well-conditioned and ill-conditioned datasets to simulate real-world machine learning challenges.
  • Basis Pursuit Denoising: A signal processing task used to evaluate performance on non-smooth objective functions.

These tests were conducted across various network topologies to observe how "connectivity ratios" (the density of agent links) influenced performance.

Key Results and Insights

The findings demonstrate that tracking aggregate curvature is fundamentally more effective than relying on local neighborhood data.

  • Communication Efficiency: DQN achieved a 7-to-10 times reduction in communication costs compared to existing second-order methods. Because it directly estimates the inverse Hessian, the data exchanged per iteration is minimized (scaling at approximately $3n$ per iteration), regardless of network density.
  • Superior Convergence: In ill-conditioned logistic regression tasks, DQN converged significantly faster than both first-order and existing second-order alternatives. While first-order methods often stalled or exhibited slow "zig-zag" behavior, DQN maintained a 100% success rate in convergence.
  • Robustness in Constraints: In Basis Pursuit problems, EC-DQN outperformed established methods like SONATA and C-ADMM, particularly in densely connected networks where it achieved the fastest overall computation times.

Limitations and Future Directions

While DQN represents a significant step forward, the authors identify several areas for further development:

  • Distributed Line-Search: The current implementation relies on constant step-sizes or centralized search methods. A fully decentralized line-search mechanism is required for autonomous deployment.
  • Non-Convex and Non-Smooth Proofs: Although the algorithm performed well on non-smooth problems in practice, formal convergence proofs for non-convex landscapes remain an open theoretical challenge.
  • Inequality Constraints: Future iterations of the framework aim to incorporate inequality constraints ($Ax \leq b$), which would expand the algorithm's utility to a wider range of engineering and economic modeling problems.

Conclusion

DQN and EC-DQN provide a powerful new toolkit for multi-agent optimization. By enabling agents to efficiently "sense" the global curvature of a problem, these methods overcome the traditional weaknesses of distributed first-order algorithms without succumbing to the overhead of classical second-order techniques.

Summary updated

BibTeX
@article{shorinwa2024distributed,
  author = {Ola Shorinwa and Mac Schwager},
  title = {{Distributed Quasi-Newton Method for Multi-Agent Optimization}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
  doi = {10.1109/tsp.2024.3424436},
}
Figure