Quantization of Distributed Data for Learning

Osama A. Hanna, Yahya H. Ezzeldin, Christina Fragouli, Suhas N. Diggavi

TL;DR

Instead of compressing massive model gradients during distributed training, this paper proposes DaQuSGD, a method that quantizes the input data itself. By leveraging the fact that data dimensions are often much smaller than model dimensions, the authors achieve up to a 300x reduction in communication costs while maintaining the convergence speeds of standard SGD.

What Problem Does This Paper Address?

In distributed machine learning, a central server (the agent) trains a model using data streamed from various nodes (sensors, mobile devices, etc.). The "communication bottleneck" is a classic hurdle: sending updates over weak wireless links is slow and expensive.

Most existing solutions focus on gradient compression—shrinking the updates the nodes send back to the server. However, we are in an era of "model explosion." While a single image (data dimension $d$) stays the same size, the neural networks we use to process them (model dimension $h$) are growing to millions or billions of parameters. If $h \gg d$, quantizing the gradient is inherently less efficient than quantizing the data. The authors ask: Why not just send a compressed version of the data and let the server compute the gradients?

Methods

The authors introduce DaQuSGD (Dataset-Quantized Stochastic Gradient Descent), which consists of three main pillars:

  1. DataQ (Datapoint Quantization): This algorithm maps high-dimensional data points into a discrete, low-precision space. It uses a clever "splitting" technique (separating positive and negative components) to represent signs implicitly, saving bits.
  2. GradCorrQ (Gradient Correction): Quantizing data introduces bias. To fix this, the authors propose an optional step where the node sends a single stochastic bit to the server. This bit allows the server to "correct" the gradient estimate, ensuring it remains unbiased and theoretically guaranteed to converge at the optimal $O(1/\sqrt{n})$ rate.
  3. Sample Selection (Thresholding): Not all data is equally useful. Borrowing intuition from Support Vector Machines (SVMs), the nodes perform a "forward pass" to calculate the loss of a sample. If the loss is below a certain threshold—meaning the model already "knows" this point—the node simply doesn't send it, saving even more bandwidth.

Datasets

The researchers evaluated their approach on two standard computer vision benchmarks:

  • CIFAR-10: Training ResNet-18.
  • ImageNet: Training ResNet-50 (a much larger scale with ~25 million parameters).

Key Insights and Ideas

  • The Dimension Gap: The "aha moment" is realizing that while models get deeper and wider, the data (pixels, audio samples) remains relatively constant in dimension. By shifting quantization from the $h$-dimensional gradient space to the $d$-dimensional data space, you decouple communication cost from model size.
  • Data-Dependent Gradients: Gradients aren't random vectors; they are functions of the data. By quantizing the data, you are essentially exploiting the underlying structure of the gradient space.
  • Online Importance Sampling: The paper demonstrates that you don't need to see the whole dataset to decide what's important. A simple loss-based thresholding at the node level acts as an effective filter for redundant information.

Key Results

The experimental results show that DaQuSGD significantly outperforms state-of-the-art gradient compression methods like QSGD and QTopK-SGD:

  • Communication Savings: On CIFAR-10, DaQuSGD achieved a 14x reduction in bits compared to QTopK-SGD and a staggering 300x reduction compared to QSGD for the same target accuracy.
  • ImageNet Performance: On the much larger ImageNet dataset, the method offered a 7x saving over QTopK-SGD.
  • Accuracy Preservation: Despite the heavy quantization, the final top-1 accuracies remained comparable to unquantized SGD (e.g., ~93% on CIFAR-10 and ~73.6% on ImageNet).
  • Convergence: The theoretical analysis holds up—the model converges at the same "order-optimal" rate as standard SGD, meaning it doesn't need significantly more iterations to reach the goal.

Limitations and Future Work

  • Server Computation: The primary trade-off is that the "learning agent" (the server) must compute the gradients itself. In traditional federated learning, nodes do this work. This makes DaQuSGD best suited for scenarios where the server is powerful but the network is weak.
  • Trusted Networks: The current framework assumes a trusted network with no privacy constraints. Since raw (though quantized) data is being sent, additional layers (like Differential Privacy) would be needed for sensitive applications.
  • Threshold Tuning: The sample selection relies on a threshold that needs to be decayed over time. Finding the "sweet spot" for this decay is currently an empirical process that could be further automated.

Summary updated

Abstract

We consider machine learning applications that train a model by leveraging data distributed over a trusted network, where communication constraints can create a performance bottleneck. A number of recent approaches propose to overcome this bottleneck through compression of gradient updates. However, as models become larger, so does the size of the gradient updates. In this paper, we propose an alternate approach to learn from distributed data that quantizes data instead of gradients, and can support learning over applications where the size of gradient updates is prohibitive. Our approach leverages the dependency of the computed gradient on data samples, which lie in a much smaller space in order to perform the quantization in the smaller dimension data space. At the cost of an extra gradient computation, the gradient estimate can be refined by conveying the difference between the gradient at the quantized data point and the original gradient using a small number of bits. Lastly, in order to save communication, our approach adds a layer that decides whether to transmit a quantized data sample or not based on its importance for learning. We analyze the convergence of the proposed approach for smooth convex and non-convex objective functions and show that we can achieve order optimal convergence rates with communication that mostly depends on the data rather than the model (gradient) dimension. We use our proposed algorithm to train ResNet models on the CIFAR-10 and ImageNet datasets, and show that we can achieve an order of magnitude savings over gradient compression methods. These communication savings come at the cost of increasing computation at the learning agent, and thus our approach is beneficial in scenarios where communication load is the main problem.
BibTeX
@article{hanna2021quantization,
  author = {Osama A. Hanna and Yahya H. Ezzeldin and Christina Fragouli and Suhas N. Diggavi},
  title = {{Quantization of Distributed Data for Learning}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=JW4aEpHlDL},
}

Loading related content...

Figure