Sampling thresholds and energy concentration for polynomials on boolean cube
Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Information TheoryMachine Learning
Summary
This paper studies how many samples are needed to learn certain polynomial functions on a space of binary inputs (like yes/no questions). Even when the model is known, some input regions might be rarely sampled, making learning slower and harder when noise is present. The authors provide precise formulas for the number of samples needed to achieve good predictions with high confidence, revealing an unexpected exponential increase in samples when noise is involved compared to noise-free cases. They also identify special sets of inputs where most of a polynomial's energy is concentrated, improving previous uncertainty principles.
What this means in practice
- •For machine learning engineers: Determine minimum sample sizes when learning polynomial models on binary data with noise to avoid underestimating data requirements.
- •For signal processing teams: Design sampling strategies for signals represented by low-degree polynomials over binary domains, accounting for energy concentration and noise effects.
A theory result. No direct application yet.
Authors
Thomas Weinberger
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)\}$.