Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

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$. We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage $ρ\in(0,1)$, the smallest set carrying a fraction $1-ρ$ of a nonzero degree-at-most-$k$ polynomial's energy has probability $\exp\{-E_{d,k}+O_{ρ,q_0}(k^{1/3})\}$. An Airy-kernel construction proves that the remainder cannot be $o(k^{1/3})$ in general. Second, we construct a subspace of dimension $\binom d{\lfloor k^{1/3}\rfloor}$ such that every function in the subspace has at least a fraction $1-ρ$ of its energy on the same set, whose probability is at most $\exp\{-E_{d,k}+C_{ρ,q_0}k^{1/3}\}$. For sufficiently large $k$, this set is a Hamming ball. A striking consequence is an exponential cost of noise: the parametric rate can require $(m+t)4^k\exp\{-O(k^{1/3})\}$ samples, whereas $O((m+t)2^k)$ suffice for noiseless identification. As $k\to\infty$ with $k/d\to0$, the noisy threshold is $(m+t)\exp\{2k+o(k)\}$.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Probability

• arXiv preprint · 8 October 2026

  The chromatic number of the associahedron: simple and logarithmic

  Benjamin Aram Berendsohn, Jean Cardinal, John Iacono and 1 other
• arXiv preprint · 9 October 2026

  Quantum-assisted rendezvous on hypercubes: a quantum Bernoulli noise approach

  Ce Wang
• arXiv preprint · 8 October 2026

  Mutually unbiased bases: common states, completion, and extension obstructions

  Hao-Yu Sun
• arXiv preprint · 9 October 2026

  Polynomial directed treewidth forces a large bramble with congestion two

  Victor A. Campos, Raul Lopes, Rodrigo Nogueira and 1 other
• arXiv preprint · 9 October 2026

  Bipartite Carrier Compression and Machine-Certified Bounds in Schönhage Trilinear Multiplication Tensors

  Volkan Dağlı, Zerrin Dağlı and Dağhan Dağlı

All new papers in Probability