Quantized consensus ADMM for multi-agent distributed optimization

Shengyu Zhu, Mingyi Hong, Biao ChenOpenReview 2016 · DOI · OpenReview

TL;DR

This paper introduces QC-ADMM, the first quantized distributed optimization algorithm based on the Alternating Direction Method of Multipliers (ADMM) that handles general, non-smooth objective functions (like LASSO). Unlike previous methods that struggle with slow convergence or errors that scale with network size, QC-ADMM achieves linear convergence to a consensus within finite iterations and provides a tight error bound independent of the number of agents.

What Problem Does This Paper Address?

In distributed optimization, a network of agents (like sensors or microprocessors) tries to minimize a global objective function that is the sum of their individual local functions. Ideally, agents would exchange high-precision real numbers to reach the optimal solution.

However, in the real world, communication is expensive. Bandwidth limits, battery constraints, and hardware realities mean agents must quantize their data—converting continuous values into a finite set of bits—before transmitting them.

Existing quantized algorithms (like subgradient descent or dual averaging) have two major flaws:

  1. Slow Convergence: They typically converge at sublinear rates ($O(1/\sqrt{k})$ or $O(1/k)$).
  2. Scaling Issues: Their "consensus error" (how far the final agreement is from the true optimum) often grows as the network gets larger.

While ADMM is known for being fast and efficient, prior quantized versions only worked for simple quadratic problems. This paper seeks to bring the power of ADMM to general, non-smooth convex optimization under strict quantization constraints.

Methods

The authors propose QC-ADMM (Quantized Consensus ADMM). The core idea is to modify the standard Consensus ADMM (C-ADMM) by applying a deterministic rounding quantizer to the variables before they are communicated between neighbors.

Key technical highlights include:

  • Deterministic Rounding: They use a rounding quantizer that maps real values to the nearest point on a grid (lattice) defined by a resolution $\Delta$.
  • Auxiliary Vector Analysis: Instead of trying to prove the convergence of the agent variables directly (which is difficult due to the "jumpy" nature of quantization), the authors track an auxiliary vector. They show that QC-ADMM can be viewed as a standard ADMM update plus a bounded error term caused by quantization.
  • Initialization: They prove that a simple initialization (setting variables to zero) is sufficient to guarantee convergence.

Datasets

As a theoretical optimization paper, the authors evaluate their algorithm using synthetic simulations rather than standard static datasets:

  • Distributed Constrained Optimization: A network of 40 nodes minimizing a sum of quadratic functions subject to local box constraints.
  • Distributed LASSO: A classic non-smooth optimization problem where agents perform sparse linear regression on locally generated measurement matrices and vectors.

Key Insights and Ideas

  • Consensus in Finite Time: One of the most striking findings is that because the quantization lattice is discrete, the algorithm actually reaches a perfect consensus (all agents agreeing on the exact same quantized value) in a finite number of iterations.
  • Network-Independent Error Bound: The authors derive a tight upper bound on the consensus error. Crucially, this bound depends on the quantization resolution ($\Delta$), the network's edge count ($E$), and the "strong convexity" of the functions, but it does not grow simply because you add more agents ($N$).
  • Linear Convergence for General Functions: By leveraging the underlying structure of ADMM, they show that the algorithm retains a linear convergence rate even when dealing with non-smooth components, provided the smooth parts of the objective are strongly convex.

Key Results

  • Speed: In simulations of a 40-node network, QC-ADMM reached a stable consensus significantly faster than Quantized Dual Averaging (Q-DA).
  • Accuracy: While Q-DA only reaches a "neighborhood" of the optimum and continues to oscillate, QC-ADMM settles on a fixed value.
  • Consensus Error: The practical error was found to be much smaller than the theoretical upper bound. For a LASSO problem, increasing the quantization resolution ($\Delta$) expectedly increased the final error but decreased the time required to reach consensus (as there are fewer lattice points to navigate).

Limitations and Future Work

  • Perfect Communication Assumption: The paper assumes that once data is quantized, it is transmitted perfectly. In reality, wireless channels introduce noise and packet loss, which could disrupt the consensus.
  • Fixed Topology: The proofs assume the network structure doesn't change over time. Extending this to dynamic or "sleepy" sensor networks where links appear and disappear is a logical next step.
  • Computational Complexity: While communication is reduced via quantization, the local "x-update" for each agent can still be computationally heavy for complex non-smooth functions. The authors suggest looking into "linearized" versions of the algorithm to reduce this local burden.

Summary updated

Abstract

This paper considers multi-agent distributed optimization with quantized communication which is needed when inter-agent communications are subject to finite capacity and other practical constraints. To minimize the global objective formed by a sum of local convex functions, we develop a quantized distributed algorithm based on the alternating direction method of multipliers (ADMM). Under certain convexity assumptions, it is shown that the proposed algorithm converges to a consensus within log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+η</sub> Ω iterations, where η > 0 depends on the network topology and the local objectives, and O is a polynomial fraction depending on the quantization resolution, the distance between initial and optimal variable values, the local objectives, and the network topology. We also obtain a tight upper bound on the consensus error which does not depend on the size of the network.
BibTeX
@misc{zhu2016quantized,
  author = {Shengyu Zhu and Mingyi Hong and Biao Chen},
  title = {{Quantized consensus ADMM for multi-agent distributed optimization}},
  year = {2016},
  doi = {10.1109/icassp.2016.7472455},
  howpublished = {OpenReview},
}
Figure