# Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

arXiv: https://arxiv.org/abs/2610.12358 · HTML: https://mlsanity.com/paper/2610.12358/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 8 Oct 2026.

## Builds on (most cited first, 5 of 5)

- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Learning low-degree functions from a logarithmic number of random queries](https://mlsanity.com/paper/2109.10162/) (2021)
- [Low-degree learning and the metric entropy of polynomials](https://mlsanity.com/paper/2203.09659/) (2022)
- [Extending the scope of the small-ball method](https://mlsanity.com/paper/1709.00843/) (2017)
- [Sum-of-squares hierarchies for binary polynomial optimization](https://mlsanity.com/paper/2011.04027/) (2020)

## Abstract (arXiv)

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)expEd,k+O(k1/3), quad Ed,k=dPsi(k/d), ] where Psi(q)=log2-mathsf H(tfrac12-√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≤binom dlfloor k1/3rfloor 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 dlfloor k1/3rfloor 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)exp2k+o(k).