Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Abstract
We study Gaussian regression under squared population L2 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 q0<1/2, 1≤ k≤ q0d, and sufficiently large fixed A, the worst-subspace sample threshold for minimax error Aσ2(m+t)/n with confidence 1−e−t, t≥log4, is N=(m+t)exp{Ed,k+O(k1/3)}, Ed,k=dΨ(k/d), where Ψ(q)=log2−H(1/2−√(q(1−q))) and H is binary entropy with natural logarithms. The upper bound holds for every feasible m; the matching lower bound holds when m≤binom d⌊ k1/3⌋ or t≥ m. We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage ρ∈(0,1), the smallest set carrying a fraction 1−ρ of a nonzero degree-at-most-k polynomial's energy has probability exp{−Ed,k+Oρ,q0(k1/3)}. An Airy-kernel construction proves that the remainder cannot be o(k1/3) in general. Second, we construct a subspace of dimension binom d⌊ k1/3⌋ 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{−Ed,k+Cρ,q0k1/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)4kexp{−O(k1/3)} samples, whereas O((m+t)2k) suffice for noiseless identification. As k→∞ with k/d→0, the noisy threshold is (m+t)exp{2k+o(k)}.
Related
- Sharp approximation thresholds for power means of common-subspace volumes
- A Sharp Fisher-Information Inequality for Boolean Pairs: Proof of the Amari--Kobayashi Conjecture
- Almost sharp sharpness for Poisson Boolean percolation
- The Geometry of Multitask Learning: Sharp Rates for Shared Subspace Estimation
- Tiling without a subspace complement: a sharp counterexample in dimension nine over the field with two elements
BibTeX
@misc{weinberger2026subspace,
title = {{Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube}},
author = {Thomas Weinberger},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12358},
eprint = {2610.12358},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12358},
}
RIS
TY - UNPB
TI - Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
AU - Thomas Weinberger
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12358
UR - https://arxiv.org/abs/2610.12358
AB - 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≤ k≤ 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≥log4, is N=(m+t)exp{E_d,k+O(k^1/3)}, E_d,k=dΨ(k/d), where Ψ(q)=log2−H(1/2−√(q(1−q))) and H is binary entropy with natural logarithms. The upper bound holds for every feasible m; the matching lower bound holds when m≤binom d⌊ k^1/3⌋ or t≥ m. We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage ρ∈(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⌊ k^1/3⌋ 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_0k^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 k→∞ with k/d→0, the noisy threshold is (m+t)exp{2k+o(k)}.
ER -