aiqbench analysis
This theoretical work refines the Polyanskiy-Samorodnitsky uncertainty principle by establishing sharp sampling thresholds for Gaussian regression on the Boolean cube, revealing an exponential cost of noise that delays parametric rates. By constructing specific subspaces where function energy concentrates in small Hamming balls, the authors demonstrate fundamental limits on prediction accuracy when random inputs undersample critical regions. These findings provide rigorous bounds essential for understanding the sample complexity and robustness of high-dimensional learning models under noisy conditions.
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$, $1\le k\le q_0d$, and sufficiently large fixed $A$, the worst-subspace sample threshold for minimax error $A\sigma^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\Psi(k/d), \] where $\Psi(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 $\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/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-\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^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)\}$.
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\sigma^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\Psi(k/d), \] where $\Psi(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 $\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/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-\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^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)\}$.
Probability (math.PR); Information Theory (cs.IT); Machine Learning (cs.LG); Combinatorics (math.CO)
arXiv:2610.12358 [math.PR]
(or arXiv:2610.12358v1 [math.PR] for this version)
https://doi.org/10.48550/arXiv.2610.12358 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 321 words
Related coverage
Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
arXiv · Sep 22, 2026
Privacy-Robust Incrementality Measurement for Advertising Systems under Signal Loss
arXiv · Jun 3, 2026
Thermal aliases in quantum noise: sampling clocks and pulse widths
arXiv · Oct 14, 2026
When Can We Trust the Matching Principle? Robust Deployment Geometry Under Finite-Sample and Model Uncertainty
arXiv · Oct 6, 2026