Optimal random quantisers for spherically symmetric distributions

The gist Optimal random quantisers for spherically symmetric distributions proves that for spherically symmetric target distributions, optimization over all such distributions is a convex problem and derives an equivalence theorem that both characterises global optimality and yields a constructive algorithm (Page 1).

Key Concepts and Definitions

(Definition of Distortion)

The (µ, s)-distortion on an n-point set Xn is defined as Dµ,s(Xn) = Eµ[mini=1,..., n U - xis], where U µ is the random variable (Page 1). The Ls-mean quantisation error of a general probability measure µ on Rd with finite s-th moment E[Xs] for a given n-point set Xn is Dµ,s(Xn) = Eµ[d s(U, Xn)] = s Z ∞ 0 t(s−1) [1 − F(t; Xn, µ)] dt (Page 3).

(Quantisation Error)

The expected (µ, s)-distortion for a random quantiser Rn with i.i.d. points having some distribution P is defined as Dµ,s(Pn) = EPn [Esµ,s(Rn)] = s Z t≥0 t(s−1) [1 − F(t; Pn, µ)] dt (Page 3).

(Distance c.d.f.)

The mean distance c.d.f. F(t; Xn, ν) is the c.d.f of the random variable d(U, Xn) when U is distributed with ν: F(t; Xn, ν) = nu (U ∈ [i=1 Bd(xi, t)]) = nu d(U, Xn ≤ t) (Page 3).

Optimality and Convexity

(Optimality Condition)

The expected (µ, s)-distortion Dµ,s(Pn) can be expressed as Jµ,s(Φ; n) = s Z t≥0 t(s−1) Z r≥0 [1 − A(Φ; r, t)]n dΨ(r) dt (Page 8). The functional Jµ,s(·; n) and the associated sensitivity function Sµ,s(·; Φ, n) satisfy the following properties (the denomination “Equivalence Theorem” is a tribute to the result of Kiefer and Wolfowitz [7] in optimal design of experiments) (Page 9).

(Equivalence Theorem)

Theorem 3.1 states that for every n ≥ 1 and s > 0, the functional Φ → Jµ,s(Φ; n) is convex (Page 9). If µ is supported in Bd(rmax), then the infimum distortion over all spherically symmetric distributions is attained by a probability measure such that Φ is supported on [0, rmax] (Page 9). A spherically symmetric distribution P such that Φ is supported on this interval is globally optimal among all spherically symmetric distributions if and only if Sµ,s(ρ; Φ∗, n) ≤ Sµ,s(Φ∗, n) for every ρ ∈ [0, rmax] (Page 9).

Constructive Algorithm and Results

(Optimisation Algorithm)

Theorem 3.1 yields a constructive procedure: starting from a finitely supported measure with c.d.f. Φk, calculate ρk ∈ Arg max 0≤ρ≤rmax Sµ,s(ρ; Φk, n) (Page 10). If gµ,s(Φk; n) is below a prescribed tolerance, (22) certifies near-optimality. Otherwise set Φk+1 = (1 − γk)Φk + γkδρk, γk ∈ Arg min 0≤γ≤1 Jµ,s[(1 − γ)Φk + γδρk; n] (Page 10).

(Exact Result for s=2)

When s = 2 and P is uniform on Sd−1(a), the expected distortion is exactly Dµ,2(P[n]a) = Eµ[U 2] + a squared − 2a Eµ[U] (1 − 2mn,d), where mn,d = Z 1 0 t(s−1) [1 − Iz(δ, δ)]n dz (Page 7). The unique minimiser of Dµ,2(P[n]a) with respect to a ≥ 0 is a∗(d, n, 2) = Eµ[U] (1 − 2mn,d) (Page 7).

(Asymptotic Regimes)

Extreme-value theory identifies three asymptotic regimes for n growing with d: (i) if n1/d → ∞, then limd→∞ κn,d = 0; (ii) if n1/d → λ with λ > 1, then lim d→∞ κn,d = 1/2 h[1 − p(1−1/λ 2)]i; (iii) if (log n)/d → 0, then limd→∞ κn,d = 1/2 (Page 20). Theorem 4.2 states that the optimal radius a∗(d, n(d), s) converges to a limit a∞ that depends on the growth regime of n(d) but not on s (Page 21).

Comparison and Applications

(Performance Comparison)

For large d, the values of a∗(d, n, s) and b∗(d, n, s) become very close; in particular for the uniform measure in Bd(1), both a∗ and b∗ converge to 1 as n → ∞ (Page 30). The optimal distribution P[n]a stops being preferable to P[n]0,b when d is sufficiently large (Page 32).

(Practical Implications)

The paper demonstrates that for a spherically symmetric measure µ in Rd, unless the sample size n is extremely large, a random quantiser uniformly distributed on a sphere of suitable radius can significantly outperform a random quantiser whose distribution follows the asymptotic limit predicted by Zador’s theorem (Page 24). The optimal radius can be determined numerically by minimising a triple integral, which can be evaluated with arbitrary precision (Page 24).

(Numerical Examples)

The paper provides numerical examples for three cases: (i) µ is uniform on the sphere Sd−1(1), (ii) µ is uniform in the ball Bd(1), and (iii) µ follows a multivariate spherically symmetric normal distribution, showing that the optimal distribution is a mixture of uniform distributions on concentric spheres with radii ρi (Page 26).

(Conclusion)

The paper concludes that for a spherically symmetric measure µ in Rd, unless the sample size n is extremely large, a random quantiser uniformly distributed on a sphere of suitable radius can significantly outperform a random quantiser whose distribution follows the asymptotic limit predicted by Zador’s theorem (Page 24). The optimal radius can be determined numerically by minimising a triple integral, which can be evaluated with arbitrary precision (Page 24). Additionally, an approximation of the optimal radius is available, derived from extreme-value theory (Page 21).

(Supplementary Material)

The supplementary material provides numerical examples for the three cases and compares random quantisers with full factorial designs (Page 26). The left column of Figure 1 presents a∗(d, n, s) as a function of d for different n and s = 1 (top) and s = 10 (bottom) (Page 27). The right column shows the efficiency of the naive quantiser with n points i.i.d. on Sd−1(1) relative to optimised random quantisers with n points on Sd−1(a∗).

(Convergence)

The empirical distribution of an optimal quantiser Xn minimising Eµ,s(Xn) converges weakly to N (0d,(σ∗∞)2 Id/d) as n → ∞, where σ∗∞ = p1 + s/d (Page 33). The convergence in probability is established by Theorem 4.2 (Page 21).

(L2 Equivalence)

Remark 4.2 shows that for large n, minimising the expected (µ, 2)-distortion is equivalent to minimising the median of the distance c.d.f., a phenomenon that can also be observed in other situations (Page 33).

References

[1] N. Alon and J.H. Spencer The Probabilistic Method Wiley, 2000 Second edition (Page 25).

[2] S. Boucheron G. Lugosi and O Bousquet Concentration inequalities In O Bousquet U von Luxburg and G Ratsch editors Advanced Lectures on Machine Learning pages 208–240 Springer, 2004 (Page 3).

[3] K.-T Fang S Kotz and K.W Ng Symmetric Multivariate and Related Distributions Chapman and Hall/CRC, 1990 (Page 1).

[4] V.V Fedorov Theory of Optimal Experiments Academic Press, New York, 1972 (Page 25).

[5] W.

1. Bold header: Extreme-value approximation for distortion estimation

This allows AI systems to estimate performance metrics like Dbµ,s(P[n]a) with high accuracy by using explicit formulas derived from extreme-value theory, specifically Equation (30): Ebs µ,s(n; a) = Z r≥0 Z ζ≥0 (r − a)2 + 4 a r κn,d ζ s/2 dFd(ζ).

2. Bold header: Optimal design parameter determination

AI can determine the optimal radius for random quantisers by minimizing the expected distortion functional, using the Equivalence Theorem and its optimality condition (Equation (20)), which states that a spherically symmetric distribution P such that Φ is supported on this interval is globally optimal among all spherically symmetric distributions if and only if Sµ,s(ρ; Φ∗, n) ≤ Sµ,s(Φ∗, n) for every ρ ∈ [0, rmax].

3. Bold header: Adaptive design choice based on growth regimes

The AI can dynamically select the optimal quantiser structure by analyzing the growth rate of sample size relative to dimension (e.g., for a sub-exponential growth, R → 0; for a super-exponential growth, R → r).

4. Bold header: Convergence analysis for high-dimensional quantization

The system can predict the asymptotic behavior of optimal parameters, such as the optimal radius limit a∗ d → r(1 − 2κ∞), based on the growth regime of n(d).

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