Optimal random quantisers for spherically symmetric distributions

Luc Pronzato; Anatoly Zhigljavsky

math.STOct 8, 2026

Optimal random quantisers for spherically symmetric distributions

Authors: Luc Pronzato, Anatoly Zhigljavsky

Organizations: Laboratoire I3S, CNRS-Université Côte d’Azur, Sophia Antipolis, France · School of Mathematics, Cardiff University, UK

Abstract

Zador's celebrated theorem is a cornerstone of optimal quantisation: it establishes both the weak limit of the empirical distribution of an optimal $n$ -point quantiser in $R^d$ and the decay rate of the associated $L_s$ -mean quantisation error. In large dimension, however, observing this asymptotic behaviour requires an astronomically large sample size. We prove that, for spherically symmetric target distributions, optimisation over all spherically symmetric distributions is a convex problem and derive an equivalence theorem that both characterises global optimality and yields a constructive algorithm. We show that, for moderate $n$ , random quantisers uniformly distributed on a sphere of suitably chosen radius $R$ perform exceptionally well and, over a broad range of values of $n$ , are numerically certified to be optimal among all random quantisers. Their expected distortion has an explicit integral representation that can be evaluated to arbitrary precision, and we prove concentration across random quantisers: the distortion variance tends to zero as $n\to\infty$ for fixed $d$ . For $s=2$ , both the optimal radius and the associated minimum expected distortion admit exact expressions. For general $s$ , the optimal radius can be determined efficiently, and extreme-value theory provides useful approximations when $n$ grows with $d$ . Depending on this growth rate, $R$ either converges to zero or approaches a positive limit that is independent of $s$ .

Figures & tables

Figure 1: Sphere. Smallest $n=n(d,s)$ such that $\mathbb{P}$ uniform on ${\mathcal{S}}_{d-1}(a^{*})$ is optimal, for $s=2$ ( $\blacklozenge$ ), $s=4$ ( $\bigstar$ ) and $s=10$ ( $\bullet$ ).

Panel of Figure 2 — Figure 2: Sphere. Value $a^{*}$ minimising $D_{\mu,s}(\mathbb{P}^{[n]}_{a})$ (left column) and ratio $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a^{*}})/D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{1})$ (right column) as functions of $d$ for $s=2$ (top row) and $s=10$ (bottom row) and different values of $n$ : $n=10$ ( $\bullet$ ), $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ), and $n=10^{5}$ ( $\blacksquare$ ). On the top-left panel, the dashed lines correspond to the extreme-value approximation ( 42 ) of Corollary 4.1 .

Panel of Figure 3 — Figure 3: Ball, $d=8$ . Sensitivity function $S_{\mu,2}(\rho;\Phi^{*},n)$ when $n=1\,000$ (left) and $n=100\,000$ (right).

Panel of Figure 4 — Figure 4: Ball, $s=2$ , $d=8$ . $\Phi^{*}$ ( — $\bullet$ ) and c.d.f. for $\mathbb{P}=\mu$ ( - - - $\blacklozenge$ ) when $n=1\,000$ (left) and $n=100\,000$ (right). The locations of the support points of $\Phi^{*}$ are indicated by $\bullet$ .

Panel of Figure 5 — Figure 5: $n_{1}(d,2)$ ( $\blacklozenge$ ), $n_{2}(d,2)$ ( $\bullet$ ) and $n_{3}(d,2)$ ( $\bigstar$ ) as functions of $d$ , for $\mu$ uniform on ${\mathscr{B}}_{d}(1)$ (left) and $\mu$ the normal distribution ${\mathcal{N}}(\mathbf{0}_{d},\mathbf{I}_{d}/d)$ (right).

Panel of Figure 6 — Figure 6: Normal distribution, $s=5$ , $d=10$ , $n=1\,000$ . Left: Sensitivity function $S_{\mu,5}(\rho;\Phi^{*},n)$ . Right: $\Phi^{*}$ ( — $\bullet$ ) and c.d.f. for $\mathbb{P}=\mu_{\sigma_{\infty}^{*}}$ ( - - - $\blacklozenge$ ); the locations of the support points of $\Phi^{*}$ are indicated by $\bullet$ .

Panel of Figure 7 — Figure 7: Optimal values $a^{*}(d,n,s)$ ( $\bullet$ ) and $\sigma^{*}(d,n,s)$ ( $\blacklozenge$ ) as functions of $s$ for $d=10$ and $n=1\,000$ (left panel, with $\sigma_{\infty}^{*}$ shown as a dashed line), and as functions of $d$ for $s=2$ and $n=10\,000$ (right panel).

Panel of Figure 8 — Figure 8: Values of $\kappa_{n,d}$ (left) and of $\widehat{a^{*}}(d,n,2)-a^{*}(d,n,2)$ (right) as functions of $d$ for different values of $n$ : $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ) and $n=10^{5}$ ( $\blacksquare$ ).

Panel of Figure 9 — Figure 9: Relative error $1-\widehat{D}_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})/D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ of the approximation of $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ (left for $s=2$ and right for $s=4$ ) based on extreme-value theory, as a function of $d$ for different values of $n$ : $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ) and $n=10^{5}$ ( $\blacksquare$ ); $a$ is the optimal value $a^{*}(d,n,s)$ .

Panel of Figure 10 — Figure 10: $n^{1/d}\,\widehat{D}_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ ( $\blacklozenge$ ) and $n^{1/d}\,D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a})$ ( $\bullet$ ) as functions of $n$ for $s=4$ and $d=20$ . Left: $a=0.75$ for top curves and $a=a^{*}(d,n,s)$ for bottom curves. Right: $a=a^{*}(d,n,s)$ , the values of $n^{1/d}\,E_{\mu,s}(\mathbf{R}_{n})$ computed numerically for 100 random quantisers $\mathbf{R}_{n}\stackrel{{\scriptstyle d}}{{\sim}}\mathbb{P}^{[n]}_{a^{*}}$ are shown as magenta dots.

Panel of Figure 1 — Figure 1: Sphere. Value $a^{*}$ minimising $D_{\mu,s}(\mathbb{P}^{[n]}_{a})$ (left column), $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a^{*}})$ (central column) and ratio $D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{a^{*}})/D_{\mu,s}^{1/s}(\mathbb{P}^{[n]}_{1})$ (right column) as functions of $d$ for $s=1$ (top row) and $s=10$ (bottom row) and different values of $n$ : $n=10$ ( $\bullet$ ), $n=10^{2}$ ( $\blacklozenge$ ), $n=10^{3}$ ( $\blacktriangledown$ ), $n=10^{4}$ ( $\bigstar$ ), and $n=10^{5}$ ( $\blacksquare$ ).

Explore similar work

Jun 9, 2026cs.IT

Minimum Distortion Quantization with Specified Output Distribution

We derive the optimal quantizer of a real-valued random variable

W

with distribution

P_W

such that 1) the distribution of the quantization output

X

that can take

k

values follows any specified distribution

P_X

over

\{1,\ldots,k\}

, and 2) the minimum mean squared error (MMSE) of estimating

W

from

X

is minimized. It is shown that the optimal quantizer takes the form

X=σ\big(F_{σ^{-1}(X)}^{-1}(F_W(W))\big)

, where

σ

is the optimal permutation of

\{1,\ldots,k\}

among all permutations to minimize the MMSE, and

F

is the cumulative distribution function. When

P_W

is uniform over an interval or

P_X

is uniform over

\{1,\ldots,k\}

, the quantizer takes a simple form

X=F_{X}^{-1}(F_W(W))

. The concept of majorization plays a key role in the optimality proof. Specifying the output distribution is useful for designing quantizers with explicitly controlled output entropy, maximized mutual information between input and output, tailored output distribution to match channel input requirements for communication, and data anonymization.

Aolin Xu

Rate-Distortion Theory Rate-Distortion Optimization

Ask PDF

May 13, 2026cs.LG

Provable Quantization with Randomized Hadamard Transform

Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require

Θ(d^2)

time. The randomized Hadamard transform

HD

reduces this cost to

O(d \log d)

, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies

HD

to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant achieves mean squared error

\bigl(π\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}

b

bits per coordinate, where the

o(1)

term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.

Ying Feng, Piotr Indyk, Michael Kapralov +2

Vector Quantization Randomized Sketching Low-Bit Quantization Neural Network Quantization

Ask PDF

May 7, 2026cs.LG

Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model weight quantization, and approximate nearest-neighbor search in vector databases. In practice, URRs are often replaced by randomized Hadamard transforms (RHTs), which preserve orthogonality while admitting fast implementations. The remaining issue is the performance for worst-case inputs. With a URR, each coordinate is individually distributed as a shifted beta distribution, which converges to a Gaussian distribution in high dimensions. Generally, one RHT is not suitable in the worst case, as individual coordinates can be far from these distributions. We show that after composing two RHTs on any

d

-sized input vector, the marginal distribution of every fixed coordinate of the normalized rotated vector is within

O(d^{-1/2})

of a standard Gaussian both in Kolmogorov distance and in

1

-Wasserstein distance. We then plug these bounds into the analyses of modern compression schemes, namely DRIVE and QUIC-FL, and show that two RHTs achieve performance that asymptotically matches URRs. However, we show that two RHTs may not be sufficient for Vector Quantization (VQ), which often requires weak correlation across fixed-size blocks of coordinates (as opposed to only marginal distribution convergence for single coordinates). We prove that a composition of three RHTs leads to decaying coordinate covariance. This ensures that any fixed, bounded, multi-dimensional VQ codebook optimized for URRs has the same expected error when using three RHTs, up to an additive term that vanishes with the dimension. Finally, because practical inputs are rarely adversarial, we propose a linear-time

{O}(d)

check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.

Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher +2

UCL and Broadcom · Carnegie Mellon University · Harvard University +2

Rotation-Based Quantization Gradient Compression Vector Quantization Randomized Sketching

Ask PDF