When transmitting continuous data over digital channels, values must be quantized into discrete bits. Standard stochastic rounding maps a value to its nearest discrete neighbors randomly to remain unbiased, but this introduces independent variance at each step. However, if the sender and receiver share a simple pseudo-random seed—a resource known as shared randomness—the fundamental limits of quantization change.
As Ben-Basat et al. demonstrated in How to send a real number using a single bit (and some shared randomness), even a tiny amount of shared randomness can coordinate stochastic mapping to slash worst-case variance by half, approaching theoretical limits with minimal overhead. This core mechanism of coordinating quantization via shared stochasticity operates across two major domains: distributed aggregation and perceptual data compression.
Distributed Aggregation and Coordinated Error Cancellation
In distributed machine learning and optimization, a central server aggregates updates (such as gradients) from many separate nodes. If each node quantizes its data independently, their rounding errors add up randomly, creating an aggregate server-side error that scales with the global range of the input space.
By introducing a shared random seed across all nodes, we can coordinate their quantization thresholds. Suresh et al. introduced this concept as Correlated Quantization (CQ) in Correlated Quantization for Distributed Mean Estimation and Optimization. Instead of independent rounding, nodes use shared permutations to make their rounding errors negatively correlated. If one node rounds a value up, another node is statistically incentivized to round down. Consequently, when the server averages the updates, the individual rounding errors counteract and cancel each other out. This allows the aggregate estimation error to scale with the actual variance of the data points rather than the maximum possible range of the values.
Independent Quantization (Errors accumulate):
Node 1: 0.4 -> Rounds Up (+0.6) ──┐
Node 2: 0.4 -> Rounds Up (+0.6) ──┼─> Server Aggregate Error: +0.4
Node 3: 0.4 -> Rounds Up (+0.6) ──┘
Coordinated Quantization (Errors cancel):
Node 1: 0.4 -> Rounds Up (+0.6) ──┐
Node 2: 0.4 -> Rounds Down (-0.4) ──┼─> Server Aggregate Error: 0.0
Node 3: 0.4 -> Rounds Down (-0.4) ──┘
This error-cancellation mechanism provides substantial benefits across distributed tasks:
- Distributed Optimization: Panferov et al. applied correlated quantization to nonconvex distributed optimization in Correlated Quantization for Faster Nonconvex Distributed Optimization, showing that coordinated error cancellation yields a mean square error inversely proportional to the number of clients.
- Nonparametric Regression: Zhu et al. leveraged shared random seeds for scalar quantization in Distributed Nonparametric Regression under Communication Constraints, ensuring accurate aggregation under strict per-node bit budgets.
- Gradient Sparsification and Bandits: In settings like distributed linear bandits (Distributed Linear Bandits under Communication Constraints by Salgia et al.) and deep neural network training (Dithered backprop: A sparse and quantized backpropagation algorithm for more efficient deep neural network training by Wiedemann et al.), stochastic quantization allows aggressive bit-width reduction because the zero-mean quantization noise naturally minimizes or cancels out upon aggregation.
Perceptual Compression and the Rate-Distortion-Perception Trade-off
Beyond distributed systems, shared randomness fundamentally alters the Rate-Distortion-Perception (RDP) trade-off in lossy data compression. Traditional compression focuses strictly on minimizing distortion (such as Mean Squared Error), which often results in blurry, unrealistic reconstructions at low bitrates. Generative compression aims instead for perfect realism—ensuring the reconstructed data is statistically indistinguishable from the original source distribution.
To achieve high perceptual quality without increasing the transmission rate, the encoder and decoder must be synchronized. As Theis et al. proved in A coding theorem for the rate-distortion-perception function, shared randomness allows the decoder to select reconstruction candidates from a pre-synchronized distribution without transmitting any extra bits. Lei et al. demonstrated in Optimal Neural Compressors for the Rate-Distortion-Perception Tradeoff that shared randomness is an absolute mathematical necessity for optimal RDP performance; without it, there remains a fundamental performance gap that cannot be bridged by making neural networks larger or more complex.
This shared stochastic resource allows the decoder to synthesize fine-grained, realistic details that are statistically consistent with the source, even when the encoder provides no explicit guidance for them. While Wagner et al. showed in The Rate-Distortion-Perception Trade-off: The Role of Private Randomness that giving the encoder private randomness does not improve the trade-off, shared common randomness acts as a vital asset. For instance, Gunduz et al. (The Rate-Distortion-Perception Trade-off with Side Information) and Chen et al. (Distribution-Preserving Integrated Sensing and Communication with Secure Reconstruction) highlighted how common randomness enables distribution preservation and high perceptual quality at ultra-low bitrates.
In practical generative architectures, this synchronization manifests through shared seeds in diffusion models or optimal transport plans:
- Diffusion-Based Coding: Theis et al. developed DiffC in Lossy Compression with Gaussian Diffusion, utilizing shared randomness to transmit noisy samples via reverse channel coding, bypassing deterministic bitrate limits.
- Optimal Transport Plans: In cross-domain tasks like super-resolution and denoising, Nguyen et al. (Cross-Domain Lossy Compression via Rate- and Classification-Constrained Optimal Transport) and Liu et al. (Lossy Compression with Distribution Shift as Entropy Constrained Optimal Transport) showed that shared randomness decouples information transport from quantization, reducing stochastic compression problems into clean, deterministic optimal transport plans.
- Eliminating Metadata Overhead: In adaptive coding schemes, transmitting custom transform matrices normally consumes too many bits. Elata et al. (Zero-Shot Image Compression with Diffusion-Based Posterior Sampling) and Elata (PSC: Posterior Sampling-Based Compression) demonstrated that by synchronizing the encoder and decoder with a shared random seed and a common generative prior, the decoder can replicate the exact transform construction process step-by-step, entirely removing the need to transmit transform metadata. This principle also extends to preserving semantic meaning in low-rate environments, as explored by Chai et al. in Rate-Distortion-Perception Theory for Semantic Communication.
The Efficiency of Finite Shared Randomness
While theoretical models often assume an infinite supply of shared random bits, real-world implementations must operate under a strict budget. Fortunately, the marginal utility of shared randomness is heavily front-loaded.
Zhou et al. investigated this in Staggered Quantizers for Perfect Perceptual Quality: A Connection between Quantizers with Common Randomness and Without. They discovered that the most dramatic reduction in distortion occurs when introducing the very first bit of shared information. By using just a few shared bits to select from a small set of offset, staggered quantization grids, a system bridges the gap between rigid deterministic grids and infinite-randomness dithering.
To exploit this practically, Lei et al. introduced quantized shared randomness using nested lattices to communicate a finite amount of dither information. This allows low-complexity neural compressors to interpolate smoothly between private noise and infinite shared randomness, unlocking near-theoretical perceptual performance with minimal shared data.
Key Foundational Work
How to send a real number using a single bit (and some shared randomness) (2020) — contributed 2 concept elements to this direction.
Distributed Nonparametric Regression under Communication Constraints (2018) — contributed 1 concept elements to this direction.
Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding (2020) — contributed 1 concept elements to this direction.