Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

arXiv:2610.12358v1 Announce Type: cross 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, 1le kle q_0d, and sufficiently large fixed A, the worst-subspace sample threshold for minimax error Asigma^2(m+t)/n with confidence 1-e^{-t}, tgelog4, is [ N=(m+t)exp{E_{d,k}+O(k^{1/3})}, quad E_{d,k}=dPsi(k/d), ] where Psi(q)=log2-mathsf H(frac12-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 mleinom d{lfloor k^{1/3}rfloor} or tge m. We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage rhoin(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/3})}. An Airy-kernel construction proves that the remainder cannot be o(k^{1/3}) in general. Second, we construct a subspace of dimension inom d{lfloor k^{1/3}rfloor} 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/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^kexp{-O(k^{1/3})} samples, whereas O((m+t)2^k) suffice for noiseless identification. As koinfty with k/do0, the noisy threshold is (m+t)exp{2k+o(k)}.

Source: arXiv cs.LG | 2026-10-09