In decentralized networks, multiple nodes collaborate to solve a global optimization problem or reach a consensus. However, exchanging high-precision floating-point values across nodes creates a massive communication bottleneck. To alleviate this, practitioners compress messages using quantization—mapping continuous values to a finite set of discrete bits.
The traditional challenge with quantization is the error floor. As shown by Apostolos I. Rikos et al. in Asynchronous Distributed Optimization via ADMM with Efficient Communication, standard static uniform quantization limits the algorithm's accuracy, causing iterates to stabilize within a bounded neighborhood around the optimum rather than converging to the exact solution. The size of this neighborhood is directly governed by the coarseness of the quantization grid.
Why Does Uniform Quantization Fail?
To build intuition, consider a standard gradient descent step where nodes exchange their current states. As the nodes approach the global optimum, the actual updates (or differences between node states) become arbitrarily small. If the quantization grid is fixed and uniform, these tiny updates eventually fall below the minimum resolution of the quantizer. The updates are either rounded to zero—causing the algorithm to stall prematurely—or bounce perpetually between grid points. This creates a persistent noise floor.
To achieve exact convergence or match the linear convergence rates of infinite-precision communication, the quantization error must scale down dynamically or structurally alongside the optimization error.
Mechanism 1: Adaptive Quantization (Dynamic Zooming)
One elegant way to break the error floor is to dynamically adjust the quantization range over time. Instead of keeping the discrete grid fixed, nodes "zoom in" on the solution as the algorithm progresses.
Siva Theja Maguluri et al. demonstrated this in Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization, proving that by shrinking the quantization range dynamically, the error penalty becomes a negligible constant factor, matching the fundamental convergence rates of perfect communication.
How fast should this grid shrink? Qiongxiu Li et al. showed in Communication efficient privacy-preserving distributed optimization using adaptive differential quantization that reducing the cell-width geometrically ensures the quantization error is finitely summable, allowing exact convergence to the global optimum.
Taking this further, Apostolos I. Rikos et al. introduced the DOFiBAQ framework in Distributed Optimization with Finite Bit Adaptive Quantization for Efficient Communication and Precision Enhancement, showing that by adapting the meaning of bits over time, nodes can achieve exact linear convergence using a fixed budget as low as 3 bits per message.
Mechanism 2: Logarithmic Quantization (Structural Scaling)
Instead of changing the grid dynamically over time, what if we change the structure of the grid itself? Uniform quantization uses equally spaced intervals, meaning the relative error grows massive as values get closer to zero. Logarithmic quantization solves this by spacing intervals exponentially closer together near zero.
As a result, the quantization error is naturally proportional to the magnitude of the signal itself. As nodes approach consensus or the optimum, the values being communicated shrink, and the absolute quantization error automatically drops toward zero.
Alireza Aghasi et al. leveraged this property in Distributed CPU Scheduling Subject to Nonlinear Constraints and D-SVM over Networked Systems with Non-Ideal Linking Conditions, proving that logarithmic quantization enables exact convergence to the centralized optimal solution rather than merely reaching an error neighborhood.
Furthermore, Mohammadreza Doostmohammadian et al. showed in Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data that log-scale quantization combined with gradient tracking yields linear convergence that is remarkably insensitive to the coarseness of the quantization level, allowing massive bandwidth savings without sacrificing convergence speed.
Mechanism 3: Quantizing Innovations and Differences
Another powerful intuition is to avoid quantizing absolute states entirely. If nodes transmit their absolute positions, they waste bits re-communicating large, redundant values. Instead, algorithms can quantize the innovation—the difference between the current state and a predicted state, or the difference between neighboring nodes.
In Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks, Yongyang Xiong et al. showed that quantizing the innovation allows nodes to achieve exact linear convergence over directed networks using as few as three quantization levels. Because the innovation naturally decays to zero as the network converges, the quantization error vanishes along with it.
In extreme cases, nodes can communicate by exchanging just the sign of the difference. Jiaqi Zhang et al. proved in Distributed discrete-time optimization by exchanging one bit of information that 1-bit updates can be treated as subgradient iterations on a penalized objective, achieving a theoretical convergence rate of $O(1/\sqrt{k})$, matching high-precision full-state exchange methods.
Alternative Error-Mitigation Strategies
Beyond scaling the grid or quantizing differences, researchers have found other mathematical properties that prevent quantization noise from destroying convergence:
- Step-Size Decay: Amirhossein Reisizadeh et al. showed in Quantized Decentralized Consensus Optimization that by carefully tuning the decay rate of the optimization step-size, the noise introduced by compression can be made to average out to zero over time, allowing exact convergence.
- Error Budgets: Mostafa El Gamal et al. established in On Randomized Distributed Coordinate Descent with Quantized Updates that coordinate-based descent methods remain stable as long as the rounding error stays below a mathematically defined threshold derived from the objective's smoothness and convexity.
- Conditional Independence: In multi-armed bandit settings, Osama A. Hanna et al. showed in Solving Multi-Arm Bandit Using a Few Bits of Communication that keeping quantization error conditionally independent of past observations preserves the Markov property, ensuring standard regret bounds hold even under extreme bit-rate constraints.
Key Foundational Work
Distributed subgradient methods and quantization effects (2008) — contributed 1 concept elements to this direction.
Quantized incremental algorithms for distributed optimization (2005) — contributed 1 concept elements to this direction.