Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
En palabras de los autores
We study Gaussian regression under squared population loss in a known -dimensional subspace of degree-at-most- functions on the -dimensional Boolean cube. Random inputs can undersample regions essential for prediction, delaying the parametric rate even when the model is known. For fixed , , and sufficiently large fixed , the worst-subspace sample threshold for minimax error with confidence , , is \[ N=(m+t)\exp\{E_{d,k}+O(k^{1/3})\}, \quad E_{d,k}=d\Psi(k/d), \] where and is binary entropy with natural logarithms. The upper bound holds for every feasible ; the matching lower bound holds when or . We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage , the smallest set carrying a fraction of a nonzero degree-at-most- polynomial's energy has probability . An Airy-kernel construction proves that the remainder cannot be in general. Second, we construct a subspace of dimension such that every function in the subspace has at least a fraction of its energy on the same set, whose probability is at most . For sufficiently large , this set is a Hamming ball. A striking consequence is an exponential cost of noise: the parametric rate can require samples, whereas suffice for noiseless identification. As with , the noisy threshold is .
Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.