Coordinated Quantization via Shared Randomness

47 concepts27 papers2 proposals

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:

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_shared_randomness_quantization_0d16b531,
  title = {shared randomness quantization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shared-randomness-quantization/rdr_0d16b5312d224c198164f0f64862e91d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_shared_randomness_quantization_0d16b531_v1,
  title = {shared randomness quantization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/shared-randomness-quantization/rdr_0d16b5312d224c198164f0f64862e91d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake