Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

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\mathrm{/}2$, $1\le k\le q_{0}d$, and sufficiently large fixed $A$, the worst-subspace sample threshold for minimax error $A{\sigma }^2(m+t)\mathrm{/}n$ with confidence $1-e^{-t}$, $t\ge \log 4$, is $$N=(m+t)\exp \{E_{d,k}+O(k^{1\mathrm{/}3})\},E_{d,k}=d\mathrm{\Psi }(k\mathrm{/}d),$$ where $\mathrm{\Psi }(q)=\log 2-\mathsf{H}(\frac{1}{2}-\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 \left(\genfrac{}{}{0px}{}{d}{\lfloor k^{1\mathrm{/}3}\rfloor }\right)$ or $t\ge m$. We sharpen the Polyanskiy–Samorodnitsky uncertainty principle in two respects. First, for fixed leakage $\rho \in (0,1)$, the smallest set carrying a fraction $1-\rho$ of a nonzero degree-at-most-$k$ polynomial’s energy has probability $\exp \{-E_{d,k}+O_{\rho ,q_0}(k^{1\mathrm{/}3})\}$. An Airy-kernel construction proves that the remainder cannot be $o(k^{1\mathrm{/}3})$ in general. Second, we construct a subspace of dimension $\left(\genfrac{}{}{0px}{}{d}{\lfloor k^{1\mathrm{/}3}\rfloor }\right)$ such that every function in the subspace has at least a fraction $1-\rho$ of its energy on the same set, whose probability is at most $\exp \{-E_{d,k}+C_{\rho ,q_0}{k}^{1\mathrm{/}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\mathrm{/}3})\}$ samples, whereas $O((m+t)2^k)$ suffice for noiseless identification. As $k\to \mathrm{\infty }$ with $k\mathrm{/}d\to 0$, the noisy threshold is $(m+t)\exp \{2k+o(k)\}$.