Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization

Thinh T. Doan, Siva Theja Maguluri, Justin RombergarXiv 2018 · DOI · arXiv

Abstract: We study distributed optimization problems over a network when the communication between the nodes is constrained, and so information that is exchanged between the nodes must be quantized. This imperfect communication poses a fundamental challenge, and this imperfect communication, if not properly accounted for, prevents the convergence of these algorithms. Our first contribution in this paper is to propose a modified consensus-based gradient method for solving such problems using random (dithered) quantization. This algorithm can be interpreted as a distributed variant of a well-known two-time-scale stochastic algorithm. We then study the convergence and derive upper bounds on the rates of convergence of the proposed method as a function of the bandwidths available between the nodes and the underlying network topology, for both convex and strongly convex objective functions. Our results complement for existing literature where such convergence and explicit formulas of the convergence rates are missing. Finally, we provide numerical simulations to compare the convergence properties of the distributed gradient methods with and without quantization for solving the well-known regression problems over networks, for both quadratic and absolute loss functions.

Introduction

In the era of large-scale machine learning and decentralized sensor networks, data is rarely localized in a single repository. Instead, we increasingly rely on distributed optimization, where a network of nodes—such as mobile robots or environmental sensors—collaborates to solve a global objective without a central controller. However, a significant bottleneck in these systems is communication. Bandwidth is often limited, and nodes cannot exchange high-precision, 64-bit floating-point numbers without incurring prohibitive costs. Consequently, nodes must "quantize" or compress their messages, a process that introduces errors and can destabilize standard optimization algorithms.

Researchers at Georgia Tech have addressed this challenge in their paper, "Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization." They introduce a novel framework that ensures networks can reach an exact optimal solution even when forced to communicate in low resolution.

The Challenge of Quantization Error

In a typical distributed network, each node possesses only its local data and objective function. To minimize the global sum of these functions, nodes must iteratively swap their current estimates with neighbors to reach a consensus. The fundamental hurdle is the noise introduced by quantization. When a node rounds a value to save bandwidth, it creates a discrepancy between the intended message and the received one.

In standard distributed gradient descent, this quantization noise usually prevents the network from converging to the true optimum; instead, the estimates oscillate within a "neighborhood" of the solution. While previous researchers suggested increasing the communication bandwidth over time to mitigate this, such an approach is often impractical for hardware with fixed communication protocols.

Proposed Methodology: Random Dithering and Two-Time-Scale Updates

The authors propose a Distributed Subgradient Algorithm under Random Quantization built on two theoretical pillars:

  1. Random (Dithered) Quantization: Rather than simple deterministic rounding, the algorithm employs a probabilistic quantization method. This ensures that the quantized value is an unbiased estimate of the true value ($E[Q(x)] = x$). By transforming quantization error into zero-mean noise, the error becomes mathematically manageable.
  2. Two-Time-Scale Stochastic Approximation: The algorithm utilizes two distinct stepsizes (learning rates). A "fast" stepsize ($\beta$) governs the consensus part, where nodes attempt to align their estimates with neighbors. A "slow" stepsize ($\alpha$) governs the gradient descent part, where nodes move toward their local optima.

By ensuring that consensus occurs at a faster relative scale than optimization, the network effectively filters out the quantization noise before it can derail the global gradient descent process.

Numerical Results and Key Insights

The paper validates these theoretical contributions through simulations of linear regression problems using both quadratic and absolute loss functions on a simulated 50-node undirected graph.

Convergence comparison of different quantization methods for quadratic loss functions.

As shown in the convergence plots, the proposed random quantization method (red line) successfully tracks the optimal solution. While it is naturally slower than the ideal "No quantization" scenario (black line), it demonstrates stable asymptotic convergence, outperforming or matching more complex time-varying schemes in long-term stability.

The "Price" of Quantization and Topology

A major contribution of this work is the derivation of explicit convergence rates. For convex functions, the rate is established at $O(k^{-1/4})$, while for strongly convex functions, it reaches $O(k^{-1/3})$. These formulas explicitly incorporate the network's topology via $\sigma_2$ (the second largest singular value of the adjacency matrix), allowing engineers to predict how the "connectedness" of their hardware will impact software performance.

The Bit Threshold

Perhaps the most practical finding for system designers is the identification of a "bit threshold." The researchers observed that as the number of bits used for quantization increases, the number of iterations required to reach a specific error threshold drops sharply until it hits a plateau.

The relationship between communication bandwidth (bits) and the iterations required to reach a target error threshold.

In their tests, once the bandwidth reached approximately 11 to 12 bits, further increases yielded diminishing returns. At this point, the error is no longer dominated by communication constraints but by the inherent stochastic nature of the optimization itself. This suggests that high-precision communication is not a prerequisite for high-precision results.

Conclusion and Future Directions

This research provides a rigorous theoretical foundation for distributed optimization under strict communication budgets. By proving almost-sure convergence and providing explicit rate formulas, the authors bridge a significant gap in the existing literature.

Future work may extend this two-time-scale approach to non-convex landscapes, such as deep neural networks, or to distributed reinforcement learning, where multi-agent systems must learn complex policies under similar bandwidth constraints. For now, the study offers a clear roadmap for building resilient, communication-efficient distributed systems.

Summary updated

Abstract

We study distributed optimization problems over a network when the communication between the nodes is constrained, and so information that is exchanged between the nodes must be quantized. This imperfect communication poses a fundamental challenge, and this imperfect communication, if not properly accounted for, prevents the convergence of these algorithms. Our first contribution in this paper is to propose a modified consensus-based gradient method for solving such problems using random (dithered) quantization. This algorithm can be interpreted as a distributed variant of a well-known two-time-scale stochastic algorithm. We then study the convergence and derive upper bounds on the rates of convergence of the proposed method as a function of the bandwidths available between the nodes and the underlying network topology, for both convex and strongly convex objective functions. Our results complement for existing literature where such convergence and explicit formulas of the convergence rates are missing. Finally, we provide numerical simulations to compare the convergence properties of the distributed gradient methods with and without quantization for solving the well-known regression problems over networks, for both quadratic and absolute loss functions.
BibTeX
@misc{doan2018distributed,
  author = {Thinh T. Doan and Siva Theja Maguluri and Justin Romberg},
  title = {{Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization}},
  year = {2018},
  eprint = {1810.11568},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.11568},
}
Figure