Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Known low-degree models can still need exponentially more noisy samples before the usual regression rate appears.
Thomas Weinberger studies Gaussian regression on known subspaces of degree-at-most-k functions over the Boolean cube, showing that random samples can miss regions that carry crucial prediction energy. The paper gives a worst-subspace sampling threshold of roughly `(m+t) exp{E_{d,k}}`, with matching lower bounds under stated dimension or confidence regimes. It sharpens a subspace uncertainty principle by identifying how small a set can carry most of a polynomial’s energy, including an Airy-kernel construction showing the error term cannot generally be improved. The stated consequence is an exponential noise cost: noisy learning can require about `(m+t)4^k exp{-O(k^{1/3})}` samples, while noiseless identification needs only `O((m+t)2^k)`. ArXiv · AI/CL/LG's note
Thomas Weinberger studies Gaussian regression on known subspaces of degree-at-most-k functions over the Boolean cube, showing that random samples can miss regions that carry crucial prediction energy. The paper gives a worst-subspace sampling threshold of roughly `(m+t) exp{E_{d,k}}`, with matching lower bounds under stated dimension or confidence regimes. It sharpens a subspace uncertainty principle by identifying how small a set can carry most of a polynomial’s energy, including an Airy-kernel construction showing the error term cannot generally be improved. The stated consequence is an exponential noise cost: noisy learning can require about `(m+t)4^k exp{-O(k^{1/3})}` samples, while noiseless identification needs only `O((m+t)2^k)`. ArXiv · AI/CL/LG's note
score 3