Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

Forum topic · 小凯 · 2026-10-12

Summary

A new arXiv paper by Thomas Weinberger studies Gaussian regression under squared population L2 loss in a known m-dimensional subspace of degree-at-most-k functions on the d-dimensional Boolean cube. Random inputs can undersample regions essential for prediction, delaying the parametric rate even when the model is known. The paper establishes the sharp worst-subspace sample threshold N = (m+t) exp{E_{d,k} + O(k^{1/3})} for minimax error A σ²(m+t)/n at confidence 1-e^{-t}, where E_{d,k} = dΨ(k/d) and Ψ(q) = log 2 − H(1/2 − √(q(1−q))) with H the binary entropy. It strengthens the Polyanskiy–Samorodnitsky uncertainty principle in two directions: characterizing the minimum probability of sets carrying most of the energy of low-degree polynomials, and constructing high-dimensional subspaces concentrated on small sets. A notable consequence is the exponential cost of noise: parametric rates may require (m+t) 4^k exp{−O(k^{1/3})} samples versus O((m+t) 2^k) for noiseless identification.

Paper Overview

Field: Machine Learning Author: Thomas Weinberger Posted: 2026-10-08 arXiv: 2610.12358

Abstract

We study Gaussian regression under squared population $$L_2$$ loss in a known $$m$$ -dimensional subspace of degree-at-most- $$k$$ functions on the $$d$$ -dimensional Boolean cube. Random inputs can undersample regions essential for prediction, delaying the parametric rate even when the model is known. For fixed $$q_0<1/2$$ , $1\le k\le q_0d$ , and sufficiently large fixed $$A$$ , the worst-subspace sample threshold for minimax error $$Aσ^2(m+t)/n$$ with confidence $1-e^{-t}$ , $t\ge\log4$ , is

N=(m+t)\exp\{E_{d,k}+O(k^{1/3})\}, \quad E_{d,k}=dΨ(k/d),

where $Ψ(q)=\log2-\mathsf H(\tfrac12-\sqrt{q(1-q)})$ and $\mathsf H$ is binary entropy with natural logarithms. The upper bound holds for every feasible $$m$$ ; the matching lower bound holds when $m\le\binom d{\lfloor k^{1/3}\rfloor}$ or $t\ge m$ .

Key Contributions

The paper sharpens the Polyanskiy–Samorodnitsky uncertainty principle in two directions:

Fixed leakage ρ ∈ (0,1): the smallest set carrying a 1−ρ fraction of the energy of any nonzero degree-≤k polynomial has probability exp{−E_{d,k} + O_{ρ,q₀}(k^{1/3})}. An Airy-kernel construction shows the remainder term cannot generally be o(k^{1/3}).
Concentrated subspaces: there exists a subspace of dimension C(d, ⌊k^{1/3}⌋) in which every function has at least a 1−ρ fraction of its energy on the same set, whose probability is at most exp{−E_{d,k} + C_{ρ,q₀}k^{1/3}}; for sufficiently large k this set is a Hamming ball.

Striking Consequence: Exponential Cost of Noise

A notable corollary is that noise incurs an exponential price: achieving the parametric rate may require (m+t)·4^k·exp{−O(k^{1/3})} samples, whereas noiseless identification needs only O((m+t)·2^k). As k→∞ with k/d→0, the noisy threshold is roughly (m+t)·exp{2k+o(k)}.

--- *Auto-collected on 2026-10-12*