PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal random quantisers for spherically symmetric distributions

Luc Pronzato, Anatoly Zhigljavsky

arXiv:2610.11772v1math.STcs.LGstat.MLstat.TH

TL;DR

Zador’s asymptotic quantisation results require astronomically large sample sizes in high dimensions. For spherically symmetric targets, this paper optimizes random quantisers and finds that suitably chosen sphere-uniform designs can outperform quantisers following the asymptotic limit unless n is extremely large.

  • Problem

    Zador’s asymptotic results are informative only when n^(1/d) is sufficiently large, requiring astronomically large n in high dimensions.

    Source: §1 · p. 1

  • Method

    The paper minimizes expected distortion for random quantisers and uses a conditional-gradient algorithm with a stopping certificate.

    Source: §2.2 · p. 4, §3.2 · p. 10

  • Results

    Unless n is extremely large, sphere-uniform random quantisers of suitable radius can significantly outperform quantisers following Zador’s asymptotic limit.

    Source: §5 · p. 24

  • Takeaways & Limitations

    The approach offers a practical way to construct high-performance quantisers as distortion variability rapidly diminishes with increasing n.

    Source: §5 · p. 24

    The claimed asymptotic optimality among all random quantisers is empirical; Theorem 4.2 optimizes only single-sphere distributions.

    Source: §4.2 · p. 22

Abstract

from arXiv · show

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$.

1 Introduction

Zador’s asymptotic quantisation results require astronomically large sample sizes in high dimensions. This paper studies random quantisers for spherically symmetric targets and develops sphere-supported designs that perform well when n is moderate.

1 Introduction

  • In high dimensions, Zador’s asymptotics are informative only when n^(1/d) is sufficiently large, requiring astronomically large n.Zador’s theorem characterises the weak limit of optimal quantisers’ empirical distribution and the asymptotic minimum distortion.Source: §1 · p. 1
  • For moderate n, suitably chosen sphere-uniform random quantisers perform exceptionally well, and their distortion variability vanishes as n increases.For s = 2, the optimal radius is proportional to Eµ{∥U∥}, and the minimum expected distortion is Eµ{∥U∥2} − R2.Source: §1 · p. 2
  • Extreme-value theory approximates the optimal radius and distortion; as d grows, the radius tends to zero for sub-exponential n and to r for super-exponential n.For exponential growth n = λd(1 + o(1)), the radius tends to r^(1 − 1/λ2).Source: §1 · p. 2
  • Nested low-error designs can be generated efficiently as an alternative to classical greedy packing for space-filling design.The conclusion also identifies quantisation of the uniform measure on the d-dimensional hypercube as a promising extension.Source: §1 · p. 2
  • The paper derives an explicit expected-distortion integral and uses convexity to characterize global optimality and construct an optimization algorithm.It presents examples for targets uniform on the unit sphere, uniform in the unit ball, and spherically symmetric normal targets.Source: §1 · p. 2

2 Distance c.d.f., quantisation error and distortion

This section defines distance-based quantisation error and develops its expected distortion for random quantisers with spherically symmetric point distributions. It also gives exact expressions for the sphere design when s = 2.

2.1 Definitions and basic properties

  • The distance c.d.f. records distances from a point sampled under a measure to its nearest quantiser, while the Ls-mean quantisation error is the corresponding distance mean.For a compact domain, the covering radius bounds the distance support; under the uniform measure, the distance c.d.f. describes the design's space filling.Source: §2.1 · pp. 2–3

2.2 Quantisation error of random quantisers

  • A random quantiser uses n i.i.d. points with distribution P, and the objective is to choose P to minimise expected (µ, s)-distortion.The distortion can be estimated by Monte Carlo; on compact support, its estimator concentrates exponentially around its mean as the sample size increases.Source: §2.2 · p. 4, §2.1 · p. 4

2.3 P {∥X −u∥≤t} when P is spherically symmetric

  • For spherically symmetric P, the probability that a random point lies within distance t of a fixed u depends on u through its radius, enabling a radial representation.A spherically symmetric vector decomposes into an independent radius and a direction uniformly distributed on the unit sphere.Source: §2.3 · p. 5

2.4 F(t; P[n], µ) and Dµ,s(P[n]) when P is spherically symmetric

  • When P is spherically symmetric, expected distortion can be computed by integration over the radii of the target and quantiser distributions, with arbitrary precision for given radial c.d.f.s.For a spherically symmetric target, a minimum-distortion distribution can also be taken spherically symmetric; the paper states that its optimisation is convex and gives an optimality condition and algorithm.Source: §2.4 · p. 7
  • For any random quantiser distribution P, at least one non-random n-point set has distortion no greater than the expected distortion of P's random design.This consequence follows from the probabilistic method.Source: §2.4 · p. 7

2.5 An exact result for s = 2 when P is uniform on Sd−1(a)

  • For s = 2 and points uniform on a sphere, the expected distortion and its unique optimal radius have exact expressions.The target measure affects the optimal radius through its mean radius Eµ{∥U∥}.Source: §2.5 · pp. 7–8

3 Optimisation over all spherically symmetric distributions

The paper characterises optimal spherically symmetric quantiser distributions through a convexity-based equivalence theorem and gives a constructive optimisation algorithm. Its examples show when single-sphere designs are optimal and how optimal radial mixtures behave for spherical, uniform-ball, and normal targets.

3.1 A necessary and sufficient condition for optimality

  • A radial distribution is globally optimal exactly when its sensitivity is nowhere above its average sensitivity; convexity also ensures an optimum exists on the target’s bounded radial support.For unbounded targets, the condition extends to all radii when the relevant differentiations are justified by moment bounds.Source: §3.1 · pp. 8–10

3.2 An optimisation algorithm

  • The conditional-gradient algorithm alternates one-dimensional maximisation and line search, preserves finite support, decreases distortion, and provides a rigorous near-optimality certificate.It can determine whether the best radial law is a single sphere or a mixture without imposing either structure in advance.Source: §3.2 · p. 10

3.3.1 µ is uniform on the unit sphere Sd−1(1)

  • For a spherical target, sufficiently small designs may need a mixture of the origin and a smaller sphere, whereas designs above n*(d, s) are optimal on one sphere.The optimal radius decreases with s and dimension, increases with n, and choosing radius 1 can be poor, especially in high dimension.Source: §3.3.1 · pp. 11–12

3.3.2 µ is uniform in the unit ball Bd(1)

  • For a uniform-ball target, optimal radial laws are mixtures of concentric spheres whose number grows slowly with n and whose weights increase with radius; single-sphere designs remain preferable until extremely large n as dimension grows.In dimension 8, the computed optimum uses two spheres at n = 1,000 and four at n = 100,000.Source: §3.3.2 · pp. 13–14

3.3.3 µ is a spherically symmetric normal distribution

  • For a normal target with d = 10, s = 5, and n = 1,000, the computed optimal law is a mixture on two concentric spheres, while the asymptotic normal design has efficiency about 0.7828.The optimal sphere radius and normal scale increase with s, and their difference tends to zero as dimension increases.Source: §3.3.3 · p. 15

3.3.2 µ is uniform in the unit ball Bd(1)

  • For uniform-ball and normal targets, the sphere-to-optimality and sphere-to-competitor transition thresholds grow with dimension, with slower growth for the normal target than for the uniform ball.For the uniform ball at s = 2, n1(d, 2) nearly coincides with 2d + 1, while the sphere remains preferable to the ball until astronomically large n at high dimension.Source: §3.3.2 · p. 14, §3.3.3 · p. 16

4 Extreme-value approximations

This section develops extreme-value approximations for distortion in uniform-on-sphere random quantisers, including how growth regimes for the number of points relative to dimension affect limiting distortion and optimal radius. It also addresses approximation accuracy and variability, with results on fixed-dimension concentration and the asymptotic link between expected-distortion and distance-quantile minimisation.

4.1 Uniform quantisers on a sphere

  • For fixed u, the normalized nearest-neighbour distance ζ(n,d)/κn,d converges in distribution to a Weibull random variable, motivating an averaged distortion approximation.The averaged expression is an approximation, not an exact identity of means.Source: §4.1 · pp. 16–17
  • For every fixed d, the variability of the realized distortion tends to zero in L2 and in probability as n→∞.The theorem applies for d≥2, n≥2, s>0, a>0, and targets with finite Bµ,s(a).Source: §4.1 · pp. 17–18
  • For s=2, the extreme-value approximation gives an explicit expected distortion and minimizing radius in terms of the target’s radial moments.The approximation is bEµ,2(n;a)=MΨ,2−2aMΨ,1+a²+4aκn,dMΨ,1Γ(1+1/δ), with ba*=MΨ,1[1−2κn,dΓ(1+1/δ)] and minimum MΨ,2−(ba*)².Source: §4.1 · pp. 18–19

4.2 Three asymptotic regimes for n growing with d

  • Under Theorem 4.2’s assumptions, the limiting distortion is minimized at a=r(1−2κ∞), with minimum [4r²κ∞(1−κ∞)]^(s/2).Here κ∞ is 0 if n^(1/d)→∞, 1/2(1−1/λ²) if n^(1/d)→λ>1, and 1/2 if log n=o(d). The radius and distortion limits depend on the growth regime, but the minimizing radius limit does not depend on s.Source: §4.2 · pp. 20–21
  • For norm-concentrated targets, including uniform measures on the unit ball and normal targets, numerical evidence suggests single-sphere quantisers may be asymptotically optimal among all random quantisers for sufficiently small λ>1.This conclusion is empirical; Theorem 4.2 optimizes only over single-sphere distributions.Source: §4.2 · p. 22
  • The minimum of bqγ over a ≥ 0 is ba*(d,n,γ)=[1−2κn,d tγ]+; since tγ→1 as d→∞, for fixed γ it has the same limits as ba*(d,n(d),s), independently of γ, when n=n(d)→∞ according to one of the three regimes in (43).Source: §4.2 · p. 22
  • L2 quantisation is suggested to be roughly equivalent to minimising the median of the distance distribution.The passage notes that this phenomenon can also occur in other situations.Source: §4.2 · p. 22

4.3 Example: µ uniform on the unit sphere Sd−1(1)

  • For s = 2, the approximated optimal radius is 1 − 2κ_{n,d}Γ(1 + 1/δ), with corresponding expected distortion 1 − (approximated radius)^2.These expressions are given by Corollary 4.1.Source: §4.3 · p. 22
  • The approximation of the optimal radius is an overestimate, and its accuracy improves with d but worsens as n increases.The difference between the approximated and optimal radii is positive.Source: §4.3 · p. 22
  • The extreme-value approximations are quite accurate when n is large enough, but convergence to the extreme-value distribution is slow for large d and the distortion approximation slightly overestimates the true value.The passages describe the approximation for D^(1/s).Source: §4.3 · pp. 22–23
  • The simulations agree closely with the exact mean distortion and show very little variability across independent random quantisers.This is reported for s = 4 and d = 20.Source: §4.3 · p. 23

5 Conclusions

Suitable-radius spherical random quantisers can significantly outperform quantisers following Zador’s asymptotic distribution unless n is extremely large, and their distortion variability diminishes as n increases. The conclusion points toward extensions involving hypercube and product measures.

5 Conclusions

  • For s=4 and d=20, the figure compares distortion at a=0.75 with distortion at the optimal radius, using 100 random quantisers for the right-panel values.The optimal-radius values are marked by magenta dots.Source: §5 · p. 24
  • Unless n is extremely large, a suitable-radius sphere-uniform random quantiser can significantly outperform one following Zador’s asymptotic distribution.The distortion variability of these random quantisers rapidly diminishes as n increases.Source: §5 · p. 24
  • For hypercube quantisation, a spherically symmetric approximation is proposed, while preliminary findings suggest promising performance for quantisers on smaller-hypercube vertices; product measures are another proposed direction.The text notes that greedy quantisation becomes computationally infeasible for large d [9, 10], and cites a spherical approximation for the uniform measure.Source: §5 · p. 24

Supplementary Material for the paper Optimal random quantisers for spherically symmetric distributions Luc Pronzato2 and Anatoly Zhigljavsky3

The supplement presents numerical examples for sphere, unit-ball, and spherically normal targets, comparing radial choices, mixtures, and deterministic designs. It reports regimes where sphere-supported quantisers outperform the optimal normal distribution and notes that some high-dimensional scale limits remain unproved, while norm concentration alone does not establish an extreme-value limit.

1.1 P = Pa uniform on Sd−1(a)

  • For fixed d, the optimal sphere radius a* rises with n toward 1 and falls with s; choosing a=1 can be inefficient at large d or small n.For sufficiently small n, a*(d,n,∞)=0.Source: §1.1 · p. 26

1.2 Mixture of P = Pa uniform on Sd−1(a) and δ0d

  • Adding a point mass at the origin can reduce distortion for small n, but choosing a suitable sphere radius has a stronger effect than optimising the mixture weight.The optimal mixture weight approaches 1 as n grows, while 1−α* remains greater than 1/n for all n.Source: §1.2 · p. 27

1.3 Comparison between random quantisers uniform on a sphere and optimised full factorial 2d designs

  • Optimised full-factorial radii tend to 0.797885 from above, while optimised random-sphere radii tend to 0.8660 from below as d increases.The random-quantiser distortion is relatively insensitive to radius near its optimum.Source: §1.3 · p. 29
  • For d≥7 with n=2d, mean random-quantiser distortion is below optimised full-factorial error for s=2,4, implying some non-random design also beats it.Numerical certificates further indicate that P_a* is optimal among i.i.d. random-quantiser distributions in the cases considered; concentration explains typical performance but is not needed for the existence argument.Source: §1.3 · p. 29
  • At fixed n, both optimal radii a* and b* approach zero as d increases, with b*>a* and their gap narrowing.This large-d behaviour remains qualitatively similar for other s values.Source: §2 · p. 30
  • For unit-ball targets, optimising the ball radius improves on the unit-radius choice at sufficiently large d, and b* exceeds the sphere-optimal a* in the reported comparisons.The displayed distortion values for ball and sphere targets are for different target measures and should not be interpreted as a direct performance comparison; in fixed d, both optimal radii approach 1 as n grows [6, Table 7.1].Source: §2 · pp. 30–31
  • For unit-ball targets, the sample-size transition n2(d,s) at which the optimal sphere quantiser ceases to be preferable grows extremely rapidly and appears super-exponential in d.For s=2, the extreme-value radius approximation is practically indistinguishable from the optimal radius in the reported comparisons.Source: §2 · p. 31
  • For n = 10 000, the asymptotic regime is still unreached across the considered dimensions, though at d = 10 the sphere quantiser is dominated by a suitably chosen normal distribution.At n = 1 000, the plotted distortion curves are close, especially near their minima for d ≥ 10, and the behaviour is similar for other s.Source: §3 · pp. 32–33, Figure 9 · p. 33
  • In the examined exponentially growing-n regime, P[n(d)]a∗ is not optimal among all spherically symmetric distributions but still outperforms the optimised normal distribution.Source: §3 · p. 33
  • Five sphere-supported quantiser choices outperform the optimal normal distribution for d ≥ 4 when a = Mψ,1 ea∗(d, n, s).The figure compares their efficiencies with the optimal normal distribution for n = 2d and s = 4.Source: §3 · pp. 33–34, Figure 10 · p. 34
  • As d → ∞, four candidate radius quantities tend to ca∗3/2; σ∗ is numerically suggested to share this limit, but rigorous analysis is still needed.The asymptotic behaviour of b∗(d, n, s) in the optimised quantiser also remains to be analysed.Source: §3 · p. 33
  • Norm concentration as d → ∞ does not by itself imply an extreme-value limit for d(u, Rn), and even uniform-ball and multivariate-normal cases pose significant challenges.Source: §3 · p. 34
Loading 2610.11772v1…