acceptodds
Under review as a conference paper at ICLR 2027

Fast Learning Beyond Finite Variance: Fractional Bernstein Geometry under Heavy-Tailed Losses

Abstract

Classical fast-rate theory typically relies on second-moment or related Bernstein-type control. We ask whether fast rates remain possible when variance does not exist. For finite classes, we introduce a fractional Bernstein condition for centered relative losses. An observable median-of-means pairwise selector achieves and a matching minimax lower bound shows that this interpolation law is sharp up to constants. We derive the fractional Bernstein geometry from primitive increment regularity and polynomial risk growth; in particular, Lipschitz increments and quadratic growth yield and the exponent . We then show that this regime arises in vector quantization genuinely below finite variance. Relative squared losses require only a first moment, and therefore remain well defined in regimes where every absolute population distortion is infinite. A weighted Voronoi margin condition yields local quadratic relative-risk growth without requiring a second moment. For a symmetric two-component Student-\(t\) family, we prove the explicit separation law Hence, sufficient separation yields local finite-dictionary relative quantization at rate despite .

Primary area:
learning theory
Keywords:
heavy-tailed learning, fast rates, learning theory, fractional Bernstein condition, robust learning, median-of-means, minimax rates, relative risk, vector quantization, infinite variance

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_NyNNOpenReview ↗
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 qq-th moment, with 1<q≤21 < q \leq 2, under a fractional Bernstein condition. It proposes an observable pairwise median-of-means tournament and proves a high-probability excess-risk rate with exponent (q−1)/(q−γ)(q-1)/(q-\gamma). A rare-event construction gives a matching minimax lower bound for the abstract finite-class model. For a separated two-component Student-tt mixture, it obtains a local finite-dictionary rate even when every bounded-codebook squared distortion is infinite.

Critical strengths
  1. The rate β(q,γ)=q−1q−γ\beta(q,\gamma) = \frac{q-1}{q-\gamma} gives a clear interpolation between weak-moment estimation and classical Bernstein rates.

  2. The cancellation bound in Eq. (5.1) explains why first-moment assumptions can suffice for squared quantization.

  3. 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
  1. The Student-tt guarantee is not numerically checkable as stated. The separation threshold D0(ν,d)D_0(\nu,d) and the constants in AV(a)≤Cν,d(s/a)νA_V(a) \leq C_{\nu,d}(s/a)^\nu are only asserted to be finite.

  2. 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-tt mixtures.

  3. There are no numerical checks of the predicted exponent, the decay of AVA_V, or the behavior of the pairwise tournament.

Questions for authors
  1. How can a practitioner construct a finite dictionary that is guaranteed to lie in the local basin without knowing the reference codebook, rar_a, λa\lambda_a, or the Student-tt parameters?

  2. Can the authors provide computable constants for D0(ν,d)D_0(\nu,d), AV(a)A_V(a), and λa\lambda_a for the symmetric mixture?

  3. Is a matching lower bound possible for bounded-codebook relative quantization itself?

4 comments

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−δ1-\delta 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.

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 1<q<21 < q < 2, d≥1d\ge1, and fixed radius R>0R > 0, a nonparametric distribution class Pq(R)\mathcal{P}_q(R) 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 ν=1.5\nu=1.5 and a/s=16a/s=16, the fixed-grid MOM-11 selector exhibits a fitted log–log slope of −0.604-0.604 for the 95th-percentile exact relative excess risk, with bootstrap 95% confidence interval [−0.624,−0.578][-0.624,-0.578]. This is close to the theoretical upper-rate reference −0.621-0.621 at q=1.45q=1.45.

Weighted Voronoi decay (E2). The one-dimensional boundary diagnostic exhibits a fitted separation slope of −1.507-1.507, consistent with the predicted exponent −ν=−1.5-\nu=-1.5. 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 n=8192n=8192, the 95th-percentile excess risks relative to the certified global bounded optimum are:

MethodP95 relative excess risk
ERM0.279734
Pairwise MOM0.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 [0.1039,0.3892][0.1039,0.3892].

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 2(q−1)/q2(q-1)/q 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.

Reviewer_f3sVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies finite-class learning under a fractional Bernstein condition on centered relative losses, E∣Zf∣q≤BΔfγ\mathbb E|Z_f|^q\le B\Delta_f^\gamma, for 1<q≤21<q\le2 and 0≤γ≤10\le\gamma\le1. A pairwise median-of-means selector achieves the rate B1/(q−γ)(log⁡(M/δ)/n)(q−1)/(q−γ)B^{1/(q-\gamma)}(\log(M/\delta)/n)^{(q-1)/(q-\gamma)}, with a matching minimax lower bound. The paper derives sufficient conditions from increment regularity and risk growth, and establishes local quadratic relative-risk growth for sufficiently separated symmetric Student-tt mixtures. This yields a local finite-dictionary quantization guarantee despite infinite absolute squared distortion. Validation is entirely theoretical, through proofs of the statistical bounds and geometric conditions.

Critical strengths
  1. The finite-class bounds are sharp under the stated assumptions. The upper and lower bounds match in sample size, class size, confidence, and the moment constant. The selector also works without knowing qq, BB, or γ\gamma. This makes the conditional statistical result precise and complete.

  2. The Student-tt example gives a concrete verification of the geometry. The paper proves that sufficient separation yields positive local curvature despite infinite variance. This shows that the assumptions hold in an explicit model.

Critical weaknesses
  1. The new rate offers limited statistical insight. Given the fractional Bernstein condition, the upper rate follows from weak-moment MOM concentration and a fixed-point argument. Combining increment regularity with risk growth also gives the primitive verification result directly. A matching lower bound shows that the rate is optimal under these assumptions, but does not explain why the result is important. I am not convinced that the paper provides enough insight beyond deriving this rate. What important learning problem does it help solve, or what new phenomenon does it reveal?

  2. The application relies on restrictive assumptions. Theorem 6.4 requires a finite dictionary that contains the exact population codebook Ca∘C_a^\circ and stays within its specified local neighborhood. It is unclear how to construct such a dictionary from data without knowing Ca∘C_a^\circ. If a fixed grid only approximates Ca∘C_a^\circ, the paper gives no guarantee that accounts for this approximation error. Thus, the Student-tt analysis verifies the local geometry, but leaves key steps needed to apply the learning result unresolved. This limits the application’s value and weakens the case for the paper’s broader significance.

Questions for authors
  1. What is the main statistical insight beyond combining weak-moment MOM concentration with the fractional Bernstein condition? Please identify a concrete learning problem where the result gives an important conclusion that existing theory does not provide.

  2. In Theorem 6.4, how can the required dictionary be obtained without knowing Ca∘C_a^\circ? Does the existing analysis cover a dictionary that approximates Ca∘C_a^\circ but does not contain it exactly? If so, please state the guarantee and its assumptions. If not, please clarify the intended use of this result.

9 comments

We thank the reviewer for recognizing the sharpness of our finite-class minimax theory, the adaptivity of the selector, and the explicit geometric verification in the Student-tt model. Your review identifies two important questions: what statistical phenomenon the fractional Bernstein framework reveals, and how its quantization guarantees can be realized without knowing the population optimum or its local basin.

The revised manuscript addresses both questions through substantial new results. In particular, we establish global continuous relative quantization, a data-driven construction of the search domain, and a matching quantization-specific minimax lower bound.

1. Statistical significance: what new learning phenomenon does the framework reveal?

The central insight is that weak-moment integrability and risk geometry play distinct roles in determining statistical learnability. Favorable geometry can accelerate learning without requiring finite variance. Our revision establishes this phenomenon in actual squared vector quantization through three complementary results.

  • Population well-posedness (Appendix M). Although every fixed relative squared-loss comparison is integrable under a first moment, the unrestricted population optimization problem can be ill-posed. For the Student-tt model with 1<ν<21<\nu<2 and k≥2k\ge2, we prove that the unbounded relative objective has infimum −∞-\infty: an escaping center decreases the relative objective by Θ(R2−ν)\Theta(R^{2-\nu}). Thus relative-loss cancellation alone does not guarantee a well-posed learning problem. Radius control is mathematically substantive, not merely a discretization device.

  • Global learnability (Theorems 6.3–6.4). For sufficiently separated centered symmetric isotropic Student-tt mixtures, we establish global quadratic relative-risk growth and accelerated learning over the full bounded continuous two-center class, without requiring knowledge of the population optimum or its local basin.

  • Quantization-specific minimax sharpness (Theorem 6.5 and Appendix N). We construct a fixed nonparametric infinite-variance distribution class with balanced, well-separated clusters and uniform global quadratic growth. On this class, the minimax confidence radius satisfies

\asymp_q R^2\left(\frac{\log(1/\delta)}{n}\right)^{2(q-1)/q},$$ for $1<q<2$, $0<\delta\le1/4$, and $n\gtrsim\log(1/\delta)$. The lower bound applies to every bounded two-center estimator, not merely symmetric estimators or the proposed MOM selector. Every distribution in the hard family has $m_q\le R$, infinite second moment, and global curvature at least $1/256$. Importantly, this hardness persists even when the clusters have equal probability and are separated by an empty slab, so that local Voronoi boundary instability vanishes in a sufficiently small neighborhood of the optimum. The statistical barrier arises from heavy-tailed centroid estimation rather than unfavorable clustering geometry. Together, these results establish when infinite-variance relative quantization is well-posed and globally learnable, and why even favorable geometry cannot eliminate the information-theoretic cost of weak moments. This is a concrete statistical consequence of the fractional Bernstein framework, beyond the upper-rate derivation from MOM concentration. ## 2. Approximation-aware learning: the dictionary need not contain the population optimum New Theorem 3.2 (Appendix I) removes the exact-inclusion requirement of the submitted finite-class result. Under fractional Bernstein control on every candidate, the original observable pairwise MOM selector satisfies, with probability at least $1-\delta$ and sufficient sample size, $$\Delta(\widehat f) \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)}.$$ The ambient population optimum need not belong to $\mathcal F_M$. The proof anchors the empirical comparisons at the best dictionary candidate and retains the original statistical exponent, with an explicit approximation term. For centroidal quantization, an $h$-accurate candidate $C_h$ satisfies $$\Delta(C_h)\le h^2$$ by the fixed-cell comparison. Under quadratic growth with curvature $\lambda$ throughout the candidate dictionary, the resulting guarantee is $$\Delta(\widehat C) \lesssim_q h^2+ \frac{(m_q+R)^2}{\min(1,\lambda)} \left( \frac{\log(2M/\delta)}{n} \right)^{2(q-1)/q}.$$ This provides an explicit approximation–estimation tradeoff for a predetermined dictionary that approximates, but does not contain, the population optimum.

We would love to address two other points as follows.

3. Eliminating the unknown local basin: global continuous learning

The stronger result is that a local dictionary is no longer necessary for the concrete model of Eq. (6.1).

New Theorem 6.3 proves that, for the centered symmetric isotropic Student-tt mixture, sufficiently large separation and ca≤R≤Lac_a\le R\le La imply

\lambda_{\mathrm g} d_{\mathrm{perm}}(C,C_a^\circ)^2 \qquad \text{for every }C\in\mathcal C_R,$$ where $$\mathcal C_R=\overline B(0,R)^2/S_2$$ is the full bounded continuous two-center class. Unlike the submitted local result, this theorem covers arbitrary midpoint displacements, center separations, and orientations. Candidate codebooks need not be symmetric or aligned with the unknown mixture axis. The proof exploits an exact midpoint/half-separation decomposition of relative squared distortion, establishing that $C_a^\circ$ is the unique global bounded population optimum modulo permutations. In particular, at $\nu=3/2$ and $a/s=16$, we obtain the explicit analytic certificate $$\lambda_{\mathrm g}\ge\frac1{300} \qquad \text{for }c_a\le R\le2.5a,$$ valid in every ambient dimension. Theorem 6.4 consequently establishes a continuous pairwise-MOM guarantee. For $1<q<\nu\le2$, $$\Delta(\widehat C) \lesssim_q \frac{(m_q+R)^2}{\min(1,\lambda_{\mathrm g})} \left( \frac{d\log n+\log(1/\delta)}{n} \right)^{2(q-1)/q},$$ with probability at least $1-\delta$, for the prescribed odd block count $K\asymp d\log n+\log(1/\delta)$ and $n\ge2K$. The estimator is defined directly over the continuous class. A finite covering net is used only in the proof, not as a restriction on the estimator. Thus, for the stated Student-$t$ model, the original unknown-basin requirement has been eliminated rather than merely relaxed. ## 4. How can the search domain be constructed from data? Appendix M gives an explicit independent-pilot construction. Using a pilot sample of size $n_0$, define $$\widehat R= 2\operatorname{median}_{i\le n_0}\|X_i\|.$$ Under the stated separation/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 pairwise MOM over $\mathcal C_{\widehat R}$, with conditional failure probability at most $\delta/2$. The procedure requires neither the population centroids, separation axis, nor mixture parameters $a,s,\nu$. It also does not require knowledge of the curvature constant or the local basin. The common mixture midpoint is assumed known. The sufficient pilot condition is verified at $\nu=1.5$ and $a/s=16$ for dimensions $d=1,2$. Alternatively, a practitioner can construct a deterministic $h$-net of the entire bounded class after observing the pilot radius and apply the original finite-dictionary selector. Its cardinality satisfies $$M_h\le \left(1+\frac{2\sqrt{2}\widehat R}{h}\right)^{2d}.$$ Combining the global geometry with Theorem 3.2 yields $$\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 probability at least $1-\delta$, under the corresponding global geometry, pilot, and sample-size conditions. This gives a fully specified statistical construction: select the radius from an independent pilot, cover the bounded class, and apply the original selector. Neither exact inclusion of the population optimum nor local-basin discovery is required. The finite sieve is explicit, although its cardinality can grow exponentially with dimension.

Regarding the experimental results, we would like to present our discussion as follows.

5. Numerical evidence and scope

The new experiments provide additional evidence for the statistical and geometric mechanisms (Figure 2 and Appendices L–M). In particular, a genuine two-dimensional pairwise tournament over 45 codebooks allowing nonsymmetric configurations achieves, at n=8192n=8192, a 95th-percentile excess risk of 0.087440.08744 for MOM versus 0.279730.27973 for ERM, measured relative to the certified global bounded optimum. This corresponds to a reduction of approximately 69% in upper-tail excess risk. The paired-bootstrap 95% confidence interval for the difference (ERM minus MOM) is [0.1039,0.3892][0.1039,0.3892].

The fixed-grid learning experiment also exhibits a fitted MOM-11 p95 slope of −0.604-0.604 at ν=1.5\nu=1.5, close to the theoretical upper-rate reference −0.621-0.621 at q=1.45q=1.45. The weighted Voronoi boundary diagnostic exhibits a separation slope of −1.507-1.507, consistent with the predicted exponent −ν=−1.5-\nu=-1.5.

These experiments support the predicted geometric decay and illustrate the upper-tail robustness of pairwise MOM. They evaluate finite-dictionary learning rather than continuous minimax optimization, and ERM can perform better in median risk. We do not interpret fitted finite-sample slopes as establishing equality of asymptotic learning exponents.

We distinguish the established statistical guarantees from broader computational and modeling questions. The global geometry theorem concerns the stated two-component mixture, the adaptive pilot assumes a known midpoint, and the quantization-specific lower bound concerns a nonparametric class rather than the exact known-shape Student-tt family. We do not claim polynomial-time continuous minimax optimization or sharp general-class dimension dependence.

In summary, the revision resolves the exact-optimum-inclusion and unknown-basin issues through an approximation-aware oracle, global continuous geometry, and a data-driven bounded search domain.

More fundamentally, it establishes a concrete statistical phenomenon in infinite-variance relative quantization: global accelerated learning is possible despite infinite absolute distortion, unrestricted population optimization can be ill-posed, and the accelerated exponent is minimax-sharp on a concrete class with favorable global geometry. These results substantially strengthen the statistical significance and applicability of the original fractional Bernstein framework.

We sincerely thank the reviewer again for these thoughtful and constructive questions, which have led to substantial improvements in the theoretical depth and statistical scope of the manuscript. We hope that the new theoretical results, constructive guarantees, 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.

Reviewer_GuLeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies selection among a finite set of M candidate predictors when the loss difference between a candidate and the best predictor has only a finite q-th moment, with q strictly between one and two, so that the variance may be infinite. It introduces a fractional Bernstein condition that bounds this q-th moment by a constant times the excess risk raised to a power gamma, and shows that a pairwise median-of-means selector attains excess risk of order (log(M/delta)/n) to the power (q-1)/(q-gamma), with a matching minimax lower bound (Theorems 3.1 and 3.2). Section 4 shows that Lipschitz loss differences with quadratic risk growth give gamma equal to q/2 and hence exponent 2(q-1)/q. Sections 5 and 6 apply this to squared-loss vector quantization written through relative losses, which remain finite under a first moment even when every absolute risk is infinite, and verify the required local geometry for a symmetric two-component Student-t mixture. The paper is purely theoretical.

Critical strengths
  1. The rate exponent (q-1)/(q-gamma) is a clean interpolation between the known weak-moment rate at gamma equal to zero and the classical Bernstein rate at q equal to two, with both an upper and a lower bound. I found no prior statement of this law.

  2. The selector in Equation 3.2 does not need q, the constant, or gamma, so the guarantee is adaptive. This matters because the condition itself cannot be checked from data.

  3. The paper is honest about scope. The contributions paragraph and Section 8 state that the quantization result is finite-class and local.

Critical weaknesses
  1. The upper bound is short once the pieces are in place. Given the standard median-of-means bound under a q-th moment, Theorem 3.1 follows from balancing the fluctuation scale against the excess risk, which the paper itself does in half a page in Section 2. The contribution is the formulation, not the proof.

  2. Closely related work is missing. Klochkov, Kroshnin and Zhivotovskiy (Annals of Statistics 49(4), 2021) prove matching upper and lower bounds for median-of-means k-means under two moments, depending on the same lightest-cluster mass that appears in Theorem 5.4. Hogsgaard and Paudice (arXiv:2506.14673, 2025) prove uniform median-of-means bounds for classes with p-th moments, p in (1, 2], and apply them to k-means over a continuous unbounded set of centers at the weak-moment rate. The second is exactly complementary to this submission and neither is cited. The sources of the gamma equal to zero rate (Bubeck, Cesa-Bianchi and Lugosi 2013; Devroye, Lerasle, Lugosi and Oliveira 2016) are also not cited.

  3. There is no simulation. A log-log plot of excess relative risk against n on the model of Equation 6.1 would be cheap and would make the exponent visible.

4 The manuscript is 68 pages for a result whose core fits in a few. Several statements are repeated across the appendices.

Questions for authors
  1. Is there any natural model where the fractional Bernstein condition holds with gamma strictly above q/2 for q below two?
  2. Would the authors add a simulation on the model of Equation 6.1?
4 comments

We thank the reviewer for recognizing the sharp interpolation law, the matching minimax bounds, and the adaptivity of the selector to unknown moment and geometry parameters. The review raises important questions about the statistical significance of the framework, its applicability beyond quadratic geometry, and its relationship to existing work. We address these questions through substantial new theoretical and numerical results in the revised manuscript.

1. Novelty and statistical significance

The central contribution is a sharp characterization of how weak moments and excess-risk geometry jointly determine learnability below finite variance. The simplicity of the upper-bound argument reflects the modularity of the framework: weak-moment concentration determines the stochastic scale, while fractional Bernstein geometry determines how that scale translates into excess risk.

The revision substantially strengthens the statistical consequences of this characterization:

  • Global learnability (Theorems 6.3–6.4): For sufficiently separated centered symmetric isotropic Student-tt mixtures, we establish global quadratic relative-risk growth and accelerated learning over the full bounded continuous two-center class, without requiring knowledge of the population optimum or its local basin. At ν=3/2\nu=3/2 and a/s=16a/s=16, we obtain an explicit global curvature certificate λg≥1/300\lambda_{\mathrm g}\ge1/300 in every ambient dimension, for ca≤R≤2.5ac_a\le R\le2.5a.

  • Unboundedness impossibility (Appendix M): For 1<ν<21<\nu<2 and k≥2k\ge2, the unbounded relative population objective has infimum −∞-\infty, despite the integrability of every fixed pairwise comparison. Thus relative-loss cancellation alone does not guarantee a well-posed population optimization problem.

  • Quantization-specific minimax sharpness (Theorem 6.5 and Appendix N): We establish a matching lower bound for actual squared two-center quantization on a fixed nonparametric infinite-variance class with balanced clusters and uniform global quadratic growth. On this class, the minimax confidence radius satisfies

\asymp_q R^2\left(\frac{\log(1/\delta)}{n}\right)^{2(q-1)/q},$$ for $n\gtrsim\log(1/\delta)$. These results identify a concrete statistical phenomenon: favorable geometry makes accelerated relative-risk learning possible under infinite variance, but even well-separated, balanced clusters cannot eliminate the information-theoretic cost of weak-moment centroid estimation. The contribution therefore extends beyond the derivation of an upper bound from MOM concentration. ## 2. Can $\gamma>q/2$ occur when $q<2$? Yes. Section 4 and Appendix J now provide an explicit weighted absolute-deviation regression model $$\ell_\theta(W,Y)=W|Y-\theta|,$$ with response-dependent heavy-tailed weights and a cusp-shaped weighted response density. For $1<q<m<2$, we prove, on the specified parameter interval, $$\Delta(\theta)=c|\theta-\theta^\star|^m, \qquad \mathbb E|Z_\theta|^q \le B\Delta(\theta)^{q/m},$$ while $\mathbb E|Z_\theta|^2=\infty$ for every $\theta\ne\theta^\star$. Consequently, $$\gamma=\frac qm>\frac q2, \qquad \beta=\frac{m(q-1)}{q(m-1)}.$$ For example, $q=3/2$ and $m=7/4$ give $\beta=7/9$, compared with $2/3$ under quadratic growth. Importantly, the ordinary and weighted population medians differ, so removing the heavy-tailed weights changes the learning target. This provides a genuine infinite-variance learning example in which nonquadratic risk geometry yields a faster guaranteed rate. The construction is nonregular, as expected from its subquadratic risk growth.

We would love to discuss the remaining points as follows.

3. Numerical validation of Eq. (6.1)

We have added the requested simulation and extended it to examine learning-rate behavior, weighted Voronoi geometry, and genuine pairwise tournament selection (Figure 2 and Appendices L–M).

For the symmetric Student-tt mixture, we use multiple tail indices and sample sizes from 128128 to 3276832768, with 400 replications per configuration.

At ν=1.5\nu=1.5 and a/s=16a/s=16, the fixed-grid MOM-11 selector exhibits a fitted log–log slope of −0.604-0.604 for the 95th-percentile exact relative excess risk (bootstrap 95% CI [−0.624,−0.578][-0.624,-0.578]), close to the theoretical upper-rate reference −0.621-0.621 at q=1.45q=1.45.

The weighted Voronoi boundary diagnostic independently exhibits a separation slope of −1.507-1.507, consistent with the theoretical exponent −ν=−1.5-\nu=-1.5.

Beyond the symmetric grid, we evaluate a genuine pairwise MOM tournament over 45 two-dimensional codebooks allowing nonsymmetric configurations. At n=8192n=8192, the 95th-percentile excess risk relative to the certified global bounded optimum is 0.087440.08744 for MOM versus 0.279730.27973 for ERM, a reduction of approximately 69%. The paired-bootstrap 95% confidence interval for the difference (ERM minus MOM) is [0.1039,0.3892][0.1039,0.3892].

These results support the predicted geometric decay and demonstrate improved upper-tail robustness in the reported setting. We also report median risks, where ERM can perform better. The experiments are finite-sample diagnostics rather than claims of exact asymptotic exponents or validation of a continuous minimax solver.

4. Relationship to prior work and presentation

We appreciate the suggested references and have incorporated all four into Section 7.

  • Klochkov, Kroshnin, and Zhivotovskiy (2021) establish matching robust quantization bounds under finite second moments. Our setting permits infinite input variance and infinite absolute squared distortion.

  • Høgsgaard and Paudice (2025) establish general uniform MOM bounds under weak moments. Their k-means application in Theorem 4.1 assumes a finite second input moment. Our results complement their concentration theory by identifying and verifying the geometry that converts weak-moment fluctuations into accelerated relative excess-risk rates.

  • Bubeck, Cesa-Bianchi, and Lugosi (2013) and Devroye, Lerasle, Lugosi, and Oliveira (2016) provide important foundations for robust estimation under weak moments, including the regime recovered at γ=0\gamma=0.

We also explicitly acknowledge the established minmax MOM framework of Lecué and Lerasle and the principal-point geometry of Yamamoto and Shinozaki. Our contribution is not a new robust mean-estimation primitive or classical principal-point characterization, but the sharp fractional Bernstein law and its quantitative realization in relative quantization below finite variance.

Finally, we have substantially refined the exposition, preserving the original fractional Bernstein narrative within the revised manuscript, while integrating the new theoretical and empirical contributions. The appendices provide a self-contained mathematical development, retaining the original proofs and establishing the new results in full detail. This organization keeps the central scientific message focused and accessible while ensuring that every theoretical claim is supported by a complete proof.

In summary, the revision establishes not only that fast learning remains possible below finite variance, but also that global relative quantization is statistically learnable, why removing radius control can make the population problem ill-posed, and why the accelerated exponent is minimax-sharp on a concrete quantization class. These results substantially strengthen both the theoretical significance and the practical interpretation of the original framework.

In summary, the revision establishes not only that fast learning remains possible below finite variance, but also that when global relative quantization is statistically learnable, removing radius control can make the population problem ill-posed, and that the accelerated exponent is minimax-sharp on a concrete quantization class. These results substantially strengthen the theoretical significance and statistical scope of the original framework.

We sincerely thank the reviewer again for the thoughtful and constructive feedback, which has helped us strengthen the manuscript. We hope that the new theoretical results, numerical evidence, and clarifications 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.

Dear Reviewer,

We sincerely appreciate your time and thoughtful evaluation of our submission. We have addressed your concerns in our detailed rebuttal and uploaded a substantially revised manuscript, incorporating new theoretical guarantees, expanded experimental evidence, stronger comparisons, and improved presentation.

As the discussion period approaches its conclusion, we would be grateful if you could review our responses and the revised manuscript when convenient. We would also sincerely appreciate any final feedback or reconsideration of your assessment in light of these updates.

We fully respect your independent judgment and understand the time required to evaluate the revisions.

Thank you again for your time, expertise, and consideration. We look forward to hearing your thoughts.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.