Log-Scale Quantization in Distributed First-Order Methods: Gradient-Based Learning From Distributed Data

Mohammadreza Doostmohammadian, Muhammad I. Qureshi, Mohammad Hossein Khalesi, Hamid R. Rabiee, Usman A. Khan

Abstract

Decentralized strategies are of interest for learning from large-scale data over networks. This paper studies learning over a network of geographically distributed nodes/agents subject to quantization. Each node possesses a private local cost function, collectively contributing to a global cost function, which the proposed methodology aims to minimize. In contrast to many existing literature, the information exchange among nodes is quantized. We adopt a first-order computationally-efficient distributed optimization algorithm (with no extra inner consensus loop) that leverages node-level gradient correction based on local data and network-level gradient aggregation only over nearby nodes. This method only requires balanced networks with no need for stochastic weight design. It can handle log-scale quantized data exchange over possibly time-varying and switching network setups. We analyze convergence over both structured networks (for example, training over data-centers) and ad-hoc multi-agent networks (for example, training over dynamic robotic networks). Through analysis and experimental validation, we show that (i) structured networks generally result in a smaller optimality gap, and (ii) logarithmic quantization leads to smaller optimality gap compared to uniform quantization.

Introduction

In decentralized machine learning, data is often spread across geographically distant nodes, such as edge devices or distributed data centers. To train a global model, these nodes must exchange information—typically gradients or model weights. However, real-world communication channels are constrained by limited bandwidth, necessitating quantization to reduce the number of bits used for data representation.

Existing distributed algorithms face two primary hurdles. First, quantization error in standard uniform quantization (rounding to fixed intervals) often leads to a significant "optimality gap." As the algorithm approaches the minimum and values become smaller, uniform quantization loses the precision required to continue improving. Second, many methods demand network rigidity, requiring "weight-stochastic" matrices where incoming and outgoing link weights must sum to one—a condition difficult to maintain in dynamic networks with frequent link failures.

Proposed Methodology

This work introduces a first-order distributed optimization method characterized by two key innovations: log-scale quantization and weight-balanced design.

Log-Scale Quantization

Unlike uniform quantization, log-scale quantization assigns more bits to represent smaller values and fewer bits to larger ones. Mathematically, this acts as a "sector-bound" nonlinearity. This approach ensures high precision near the optimum where gradients are small, which is critical for achieving convergence to a true minimum rather than stalling due to rounding errors.

Comparison of uniform (left) and log-scale (right) quantization functions.

Weight-Balanced (WB) Design and Gradient Tracking

The algorithm relaxes network requirements by only requiring the network to be "weight-balanced" (the sum of weights on incoming links equals the sum on outgoing links). This makes the system significantly more robust to time-varying topologies. To ensure global convergence despite local, quantized data, the method employs a gradient tracking mechanism. Each node maintains an auxiliary variable to track the average of the global gradients, guiding the local updates toward the global minimum.

Experimental Validation

The researchers validated the proposed framework using two distinct setups:

  1. Synthetic Benchmark: A 16-agent network minimizing a non-convex cost function with trigonometric terms, testing the ability to handle complex local functions that aggregate into a strongly convex global function.
  2. MNIST Classification: A standard image classification task using 12,000 images distributed across 16 nodes, employing logistic regression with a convex regularizer.

Key Results

Experimental results demonstrate that log-scale quantization consistently achieves a significantly lower optimality gap compared to uniform quantization across various quantization levels ($\rho$). While uniform quantization causes the optimality gap to plateau relatively early, log-scale quantization allows the algorithm to maintain linear convergence for much longer, reaching significantly higher precision.

Optimality gap comparison between uniform (top) and log-scale (bottom) quantization across different iterations.

Furthermore, the study highlights that structured networks (e.g., exponential graphs) yield faster convergence and smaller optimality gaps than ad-hoc networks (e.g., random geometric graphs). The method also proved robust to "switching" networks, where the topology changes every few iterations.

Conclusion

By prioritizing precision where it matters most—near the optimum—log-scale quantization offers a superior alternative to uniform methods in bandwidth-constrained distributed learning. The proposed weight-balanced first-order method matches the performance of state-of-the-art non-quantized algorithms while significantly reducing communication overhead. Future work will explore "union-connectivity" assumptions and the application of this framework to distributed reinforcement learning and optimal control.

Summary updated

Abstract

Decentralized strategies are of interest for learning from large-scale data over networks. This paper studies learning over a network of geographically distributed nodes/agents subject to quantization. Each node possesses a private local cost function, collectively contributing to a global cost function, which the considered methodology aims to minimize. In contrast to many existing papers, the information exchange among nodes is log-quantized to address limited network-bandwidth in practical situations. We consider a first-order computationally efficient distributed optimization algorithm (with no extra inner consensus loop) that leverages node-level gradient correction based on local data and network-level gradient aggregation only over nearby nodes. This method only requires balanced networks with no need for stochastic weight design. It can handle log-scale quantized data exchange over possibly time-varying and switching network setups. We study convergence over both structured networks (for example, training over data-centers) and ad-hoc multi-agent networks (for example, training over dynamic robotic networks). Through experimental validation, we show that (i) structured networks generally result in a smaller optimality gap, and (ii) log-scale quantization leads to a smaller optimality gap compared to uniform quantization. Note to Practitioners—Motivated by recent developments in cloud computing, parallel processing, and the availability of low-cost CPUs and communication networks, this paper considers distributed and decentralized algorithms for machine learning and optimization. These algorithms are particularly relevant for decentralized data mining, where data sets are distributed across a network of computing nodes. A practical example of this is the classification of images over a networked data centre. In real-world scenarios, practical model nonlinearities such as data quantization must be addressed for information exchange among the computing nodes. This work emphasizes the importance of handling log-scale quantization and compares its performance over uniform quantization. By exploring these quantization methods, we aim to determine which is more accurate in terms of optimality gap and learning residual. Moreover, we study the impact of the structure of the information-sharing network on reducing the optimality gap and improving the convergence rate of distributed algorithms. As contemporary distributed and networked data mining systems demand highly accurate algorithms with fast convergence for real-time applications, our research emphasizes the benefit of structured networks under logarithmic quantization information-exchange. Our findings can be extended to different machine learning algorithms, offering pathways to more accurate and faster data mining solutions.
BibTeX
@inproceedings{doostmohammadian2024log,
  author = {Mohammadreza Doostmohammadian and Muhammad I. Qureshi and Mohammad Hossein Khalesi and Hamid R. Rabiee and Usman A. Khan},
  title = {{Log-Scale Quantization in Distributed First-Order Methods: Gradient-Based Learning From Distributed Data}},
  booktitle = {IEEE Trans Autom. Sci. Eng},
  year = {2024},
  url = {https://openreview.net/forum?id=USBIb9trgS},
}
Figure