- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies finite-class learning when centered relative losses have only a -th moment, with , under a fractional Bernstein condition. It proposes an observable pairwise median-of-means tournament and proves a high-probability excess-risk rate with exponent . A rare-event construction gives a matching minimax lower bound for the abstract finite-class model. For a separated two-component Student- mixture, it obtains a local finite-dictionary rate even when every bounded-codebook squared distortion is infinite.
Critical strengths
-
The rate gives a clear interpolation between weak-moment estimation and classical Bernstein rates.
-
The cancellation bound in Eq. (5.1) explains why first-moment assumptions can suffice for squared quantization.
-
Theorem 6.2 links separation to a decay of the weighted Voronoi boundary term. This paper distinguishes finite boundary mass from the stronger positive-curvature condition.
Critical weaknesses
-
The Student- guarantee is not numerically checkable as stated. The separation threshold and the constants in are only asserted to be finite.
-
The minimax lower bound is sharp for a constructed finite loss family with rare binary observations. It does not establish a lower bound for squared vector quantization and Student- mixtures.
-
There are no numerical checks of the predicted exponent, the decay of , or the behavior of the pairwise tournament.
Questions for authors
-
How can a practitioner construct a finite dictionary that is guaranteed to lie in the local basin without knowing the reference codebook, , , or the Student- parameters?
-
Can the authors provide computable constants for , , and for the symmetric mixture?
-
Is a matching lower bound possible for bounded-codebook relative quantization itself?
4 comments
Q2. Can the separation threshold and geometric constants be made computable?
Yes. Appendix K now provides explicit sufficient constants in every ambient dimension, strengthening the existential bounds of the submitted manuscript.
Define
\frac{\nu^{\nu/2}\Gamma((\nu+1)/2)}{\sqrt{\pi}\Gamma(\nu/2)} \left(32+\frac{2(d-1)}{\nu-1}\right).$$ For $\nu > 1$ and $a/s\ge\mathbb{E}|T_\nu|$, we prove $$A_V(a)\le H_{\nu,d}(s/a)^\nu$$ uniformly over tube widths $$0 < t\le\frac{c_a}{2\sqrt{17}}, \qquad \rho=2c_a.$$ Consequently, an explicit sufficient separation threshold is $$D_0(\nu,d)=\max\left\\{ 1,\\, \mathbb{E}|T_\nu|,\\, (64H_{\nu,d})^{1/\nu} \right\\}.$$ Whenever $a/s\ge D_0(\nu,d)$, $$A_V(a)\le\frac{1}{64}, \qquad \lambda_a=\frac{1}{2}-16A_V(a)\ge\frac{1}{4}.$$ These are conservative but fully computable sufficient constants for the weighted relative Pollard geometry. We additionally provide two sharper certificates for the experimental benchmark. **Local univariate certificate (Appendix K).** At $d=1$, $\nu=1.5$, $a=16$, and $s=1$, we obtain $$A_V\le0.018395, \qquad \lambda_a\ge0.20568,$$ on a certified local radius of $0.04094$. **Global all-dimensional certificate (Theorem 6.3 and Appendix M).** At $\nu=1.5$ and $a/s=16$, we establish $$\Delta(C)\ge \frac{1}{300} d_{\mathrm{perm}}(C,C_a^\circ)^2 \qquad(C\in\mathcal{C}_R),$$ for every ambient dimension $d\ge1$ and every radius satisfying $c_a\le R\le2.5a$. The global certificate follows from an exact midpoint/half-separation decomposition and analytic scalar bounds, rather than a numerical search over candidate codebooks. We emphasize that the general-dimensional local threshold and the benchmark global certificate arise from different arguments and serve different purposes. The former explicitly controls $A_V$; the latter directly certifies global quadratic growth. The sufficient condition for the adaptive radius pilot is also verified analytically at this benchmark for $d=1,2$. These results make the geometric assumptions quantitatively checkable, rather than relying only on the existence of sufficiently large separation.Q3. Is a matching lower bound possible for bounded-codebook relative quantization itself?
Yes. This question has led to a new result that establishes minimax sharpness for actual squared vector quantization, rather than an abstract constructed loss family.
Theorem 6.5 and Appendix N construct, for every , , and fixed radius , a nonparametric distribution class for the actual squared two-center loss
\qquad C\in\mathcal{C}_R=\overline{B}(0,R)^2/S_2.$$ Every distribution in this class has a Lebesgue density, satisfies $$\left(\mathbb{E}_P\\|X\\|^q\right)^{1/q}\le R, \qquad \mathbb{E}_P\\|X\\|^2=\infty,$$ and admits a unique global bounded population optimum modulo permutations, with uniform global quadratic growth $$\Delta_P(C)\ge \frac{1}{256} d_{\mathrm{perm}}(C,C_P^\star)^2 \qquad(C\in\mathcal{C}_R).$$ Nevertheless, for every measurable estimator $\widehat{C}_n$ valued in $\mathcal{C}_R$, every $0 < \delta\le1/4$, and $n\ge\log(1/\delta)$, we prove $$\sup_{P\in\mathcal{P}_q(R)} P^n\left\\{ \Delta_P(\widehat{C}_n) \ge c_qR^2 \left( \frac{\log(1/\delta)}{n} \right)^{2(q-1)/q} \right\\} > \delta,$$ where $c_q > 0$ depends only on $q$. **Construction and proof mechanism.** The hard family is generated by $$X=S(a+W)e_1+U,$$ where $S$ is a symmetric random sign, $W$ is a nonnegative heavy-tailed magnitude, and $U$ is small independent isotropic jitter. The two clusters have equal probability and are separated by an empty slab. In fact, the weighted Voronoi margin coefficient is zero for sufficiently small tube widths. A rare-event perturbation of $W$ shifts the population-optimal centroids by $$\Omega\left(Rp^{(q-1)/q}\right),$$ while the induced sampling distributions satisfy $$P_1^n\ge(1-p)^nP_0^n.$$ Uniform global curvature converts this indistinguishability into a relative excess-risk lower bound of order $$R^2p^{2(q-1)/q}.$$ Choosing $p\asymp\log(1/\delta)/n$ yields the stated high-probability result. Crucially, the global geometry is verified over all bounded two-center codebooks, not merely symmetric candidates. The lower bound therefore applies to arbitrary bounded-codebook estimators, even when the separation axis and radius are revealed. **Matching upper bound on the same family.** For symmetric codebooks $C_t=\\{-te_1,te_1\\}$ with $t\in[0,R]$, the construction gives the exact identity $$\Delta_P(C_t)=(t-\mathbb{E}_P|X_1|)^2.$$ Applying MOM estimation to $|X_1|$ and projecting the estimated centroid magnitude onto the admissible interval gives a matching upper bound on this same known-axis family. Hence, for $n\gtrsim\log(1/\delta)$, the minimax confidence radius satisfies $$\mathfrak{R}_{n,\delta}(\mathcal{P}_q(R)) \asymp_q R^2 \left( \frac{\log(1/\delta)}{n} \right)^{2(q-1)/q}.$$ This establishes sharpness in sample size and confidence for genuine infinite-variance relative quantization. The statistical significance is that this information-theoretic barrier persists even with balanced clusters, an empty separating slab, and favorable uniform global curvature. The hardness arises from weak-moment centroid estimation, not from unstable Voronoi boundaries. We distinguish this nonparametric minimax result from the exact known-shape parametric Student-$t$ subfamily, which can admit faster parametric rates. We also do not claim matching dimension dependence for the general continuous-class upper bound.Numerical validation
We have added the requested numerical checks of all three mechanisms: learning-rate behavior, weighted Voronoi decay, and pairwise tournament selection (Figure 2 and Appendices L–M).
Learning-rate behavior (E1). At and , the fixed-grid MOM-11 selector exhibits a fitted log–log slope of for the 95th-percentile exact relative excess risk, with bootstrap 95% confidence interval . This is close to the theoretical upper-rate reference at .
Weighted Voronoi decay (E2). The one-dimensional boundary diagnostic exhibits a fitted separation slope of , consistent with the predicted exponent . The analytic certificates in Appendix K are established independently of these numerical diagnostics.
Genuine two-dimensional tournament (E3). We evaluate 45 codebooks allowing nonsymmetric configurations, with 400 paired replications per sample size. All candidates belong to the globally certified bounded class.
At , the 95th-percentile excess risks relative to the certified global bounded optimum are:
| Method | P95 relative excess risk |
|---|---|
| ERM | 0.279734 |
| Pairwise MOM | 0.087437 |
This corresponds to an approximately 69% reduction in upper-tail excess risk. The paired-bootstrap 95% confidence interval for the difference (ERM minus MOM) is .
We also report median risks, where ERM can perform better. These results demonstrate improved upper-tail robustness in the reported setting without asserting uniform empirical dominance.
Appendix M further reports global geometry stress tests, multi-start population optimization, adaptive-radius diagnostics, and numerical checks of the escaping-center obstruction.
These experiments support the theoretical mechanisms. They remain finite-sample diagnostics and do not establish equality of asymptotic learning exponents or validate a continuous minimax solver.
Summary
The revised manuscript establishes a substantially stronger connection between the abstract fractional Bernstein law and actual bounded squared quantization:
- The approximation-aware oracle and global geometry remove the exact-optimum-inclusion and unknown-basin requirements for the stated model.
- Explicit geometric constants make the local separation threshold and curvature guarantees computable, with an additional all-dimensional global certificate at the experimental benchmark.
- The new quantization-specific lower bound establishes that the accelerated exponent is minimax-sharp on a concrete nonparametric infinite-variance class, even with balanced clusters and favorable global geometry.
- The numerical experiments support the predicted separation decay and illustrate the upper-tail robustness of the pairwise MOM selector.
Together, these results show not only that fast relative-risk learning is possible below finite variance, but also that the accelerated exponent reflects a genuine statistical limit in squared quantization.
We sincerely thank the reviewer again for these insightful and constructive questions. In particular, the request for a quantization-specific lower bound has substantially strengthened the theoretical contribution. We hope that the new theorems, explicit geometric certificates, and numerical evidence address your concerns. We would greatly appreciate your reconsideration of the revised manuscript and welcome any further feedback at your earliest convenience during the discussion period.
Thank you again for your time and careful consideration.
We thank the reviewer for recognizing the sharp interpolation law, the relative-loss cancellation mechanism, and the separation-induced geometric control. Your questions identify three important directions for strengthening the connection between the abstract theory and actual squared quantization.
The revised manuscript addresses all three through substantial new results: global continuous learning without an unknown local basin, explicit geometric certificates in every dimension, and a matching quantization-specific minimax lower bound under genuine infinite variance. We also provide the requested numerical validation.
Q1. How can the dictionary be constructed without knowing the population optimum or its local basin?
The revision removes both limitations of the submitted quantization theorem.
Approximation-aware learning. New Theorem 3.2 (Appendix I) establishes that the original observable pairwise MOM selector does not require exact inclusion of the population optimum. Under fractional Bernstein control on every candidate, with probability at least 1−δ and sufficient sample size,
\lesssim_{q,\gamma} \inf_{f\in\mathcal F_M}\Delta(f) + B^{1/(q-\gamma)} \left( \frac{\log(2M/\delta)}{n} \right)^{(q-1)/(q-\gamma)}.$$ For centroidal quantization, an $h$-accurate candidate satisfies $\Delta(C_h)\le h^2$ by the fixed-cell comparison. Thus approximation error is explicitly incorporated into the learning guarantee. **Global geometry instead of an unknown local basin.** More strongly, new Theorem 6.3 establishes global quadratic growth for sufficiently separated centered symmetric isotropic Student-$t$ mixtures: $$\Delta(C)\ge \lambda_{\mathrm g} d_{\mathrm{perm}}(C,C_a^\circ)^2 \qquad(C\in\mathcal C_R),$$ where $\mathcal C_R=\overline B(0,R)^2/S_2$ is the full bounded continuous two-center class. Candidates need not be symmetric, aligned with the mixture axis, or close to the population optimum. The theorem covers arbitrary midpoint displacements, orientations, and center separations within the bounded class. Consequently, Theorem 6.4 gives a continuous pairwise-MOM excess-risk bound of order $$\frac{(m_q+R)^2}{\min(1,\lambda_{\mathrm g})} \left( \frac{d\log n+\log(1/\delta)}{n} \right)^{2(q-1)/q},$$ for $1<q<\nu\le2$, the prescribed odd block count, and the corresponding sample-size condition. **Data-driven construction.** Appendix M introduces an independent pilot $$\widehat R= 2\operatorname{median}_{i\le n_0}\|X_i\|.$$ Under the stated separation and noise-ball conditions, $$c_a\le1.5a,\qquad \Pr(s\|T\|\le a/4)\ge3/4,$$ an odd pilot size $n_0\ge8\log(2/\delta)$ guarantees $$c_a\le\widehat R\le2.5a$$ with probability at least $1-\delta/2$. The independent training sample is then used for continuous MOM over $\mathcal C_{\widehat R}$, or for the original finite-dictionary selector on a deterministic $h$-net of that class. The resulting finite-sieve guarantee is $$\begin{aligned} \Delta(\widehat C) \lesssim_q {}& h^2+ \frac{(m_q+\widehat R)^2} {\min(1,\lambda_{\mathrm g})}\\ &\times \left[ \frac{ 2d\log(1+2\sqrt{2}\widehat R/h) +\log(4/\delta)} {n} \right]^{2(q-1)/q}, \end{aligned}$$ with overall probability at least $1-\delta$ under the stated global geometry, pilot, and sample-size conditions. Neither construction requires knowledge of the population centroids, separation axis, mixture parameters, curvature constant, or local basin. The common mixture midpoint is assumed known. The finite sieve is explicit, although its cardinality can grow exponentially with dimension. Thus, for the concrete model, the unknown-basin requirement is eliminated rather than merely relaxed.