Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

The gist The worst-subspace sample threshold for 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 is determined by an exponential cost of noise, requiring (m + t)4k exp(−O(k1/3)) samples, which is exponentially worse than the O((m + t)2k) required for noiseless identification

Minimax Sample Thresholds

The paper determines the number of random examples needed before the parametric prediction rate is guaranteed for a known model, focusing on low-degree functions on the Boolean cube The central statistical question addressed is how many random examples are needed before the usual parametric prediction rate is guaranteed for known subspaces with a prescribed ambient dimension, degree, and model dimension Theorem 1.5 provides the minimax sample threshold, stating that if m ≤ Md,k or t ≥ m, then log Npar(d, k, m, A, δ) / (m + t) - Ed k ≤ Cq0A k1/3 This upper bound holds for every feasible m and is attained by ordinary least squares The unrestricted ambient dimension corollary shows that the threshold is (m + t) exp(2k + o(k)) when k/d → 0, which is compared to the noiseless upper bound O((m + t)2k)

Uncertainty Principle and Concentration

The paper sharpens the Polyanskiy–Samorodnitsky uncertainty principle by providing a quantitative subspace uncertainty principle Theorem 1.8 establishes that for a fixed leakage ρ ∈ (0, 1), if some nonzero h ∈ Pd,k satisfies E[h squared Ec] ≤ ρE[h 2], then µd(E) ≥ exp(−Ed k − Cρq0 k1/3) This yields a quantitative version of the uncertainty principle, with a remainder of uniformly optimal order Proposition 1.9 proves that there are constants such that for all sufficiently large k and all 1 ≤ m ≤ Md,k, log 1/p(d, k, m) - Ed k ≤ Cρq0 k1/3 This result yields both a one-dimensional obstruction to concentration and a subspace construction at the same precision

Moment Bounds and Clipping

The paper uses Kirshner–Samorodnitsky moment bounds to establish stable sampling thresholds Theorem 3.1 states that for nonzero f ∈ Pd,k, E[f p] (E[f 2])(p/2) ≤ exp(dF(p, k/d)) Lemma 3.2 shows that the cubic remainder in this moment bound is responsible for the k1/3 correction in the subsequent clipping bound Proposition 3.3 proves that for every fixed η ∈ (0, 1), log Td,k(η) - Ed k ≤ Cηq0 k1/3 This shows that optimizing a moment bound will give the matching upper estimate

Geometric Construction and Lifting

The paper constructs a polynomial concentrated on a Hamming ball using Krawchouk polynomials Lemma 2.2 provides an approximate eigenvector of JD with approximate eigenvalue τ, showing that the energy is near τ = 2p(D − l) Lemma 2.3 shows there is a unit radial polynomial p of exact degree l for which the cutoff u = τ - Mρq0√Dl−1/6 satisfies E[p squared Ec] ≤ ρ The construction then uses harmonic lift to extend this one-dimensional witness to a whole space Wr of dimension dR, where R = floor(k/3) Proposition 4.2 provides the harmonic lift, showing that µd(E) ≤ exp(−Ed k(R)+Cρq0K1/3), which proves the common-event assertion for every linear combination

Regression Guarantees and Bounds

The geometric bounds are converted into regression guarantees using empirical eigenvalues Lemma 5.1 shows that many small empirical eigenvalues are at most 128ρ with high probability when n ≤ m/(128p) Theorem 5.2 states that the minimax risk R∗n,δ(V) = Q1−δ(Zn,V), and any measurable least-squares minimizer attains this minimax value Proposition D.3 provides an estimator-independent parametric obstruction showing that R∗n,e−t (V) > Aσ2 m + t n for certain conditions

Sharpness and Limits

The paper proves the sharpness of the uniform uncertainty remainder by constructing a polynomial with a fixed fraction β > 0 of its squared L2-norm concentrated on the chosen set This construction shows that for every fixed leakage level, a positive correction of order k1/3 is necessary at one fixed leakage level, for all subspace dimensions in the stated range The convergence analysis shows that from the cube to Gaussian polynomials, PD j(t) converges to Hj(t) uniformly on bounded intervals of t The transfer to the Airy kernel describes the limiting behavior of Hermite kernel near the edge of its concentration region

Further Bounds and Model Examples

The paper derives additional bounds for larger model dimensions, showing that for any integer 0 ≤ R ≤ k with m ≤ dR, log Npar(m + t) ≥ Ed k − C(R + k1/3) The leading exponent for subexponential model dimensions is Ed k + o(d), and the upper bound of Theorem 1.5 also has error o(d) and holds for every feasible m For a known span of m Walsh characters, N ≤ Cd d k(log m + t) This establishes the stable-sampling or parametric threshold

Conclusion

The worst-subspace uncertainty principle determines the worst-subspace parametric threshold, throughout the matching range, to an O(k1/3) error in the exponent It explains the exponential cost of noise relative to identification

The paper is a detailed study of how random inputs can undersample regions essential for prediction, delaying the parametric rate even when the model is known

How it works

1. The worst-subspace sample threshold for 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 is determined by an exponential cost of noise, requiring (m + t)4k exp(−O(k1/3)) samples, which is exponentially worse than the O((m + t)2k) required for noiseless identification

2. The paper sharpens the Polyanskiy–Samorodnitsky uncertainty principle by providing a quantitative subspace uncertainty principle Theorem 1.8 establishes that for a fixed leakage ρ ∈ (0, 1), if some nonzero h ∈ Pd,k satisfies E[h squared Ec] ≤ ρE[h 2], then µd(E) ≥ exp(−Ed k − Cρq0 k1/3)

3. The paper constructs a polynomial concentrated on a Hamming ball using Krawchouk polynomials Lemma 2.2 provides an approximate eigenvector of JD with approximate eigenvalue τ, showing that the energy is near τ = 2p(D − l) Lemma 2.3 shows there is a unit radial polynomial p of exact degree l for which the cutoff u = τ - Mρq0√Dl−1/6 satisfies E[p squared Ec] ≤ ρ

4. The construction then uses harmonic lift to extend this one-dimensional witness to a whole space Wr of dimension dR, where R = floor(k/3) Proposition 4.2 provides the harmonic lift, showing that µd(E) ≤ exp(−Ed k(R)+Cρq0K1/3), which proves the common-event assertion for every linear combination

5. The geometric bounds are converted into regression guarantees using empirical eigenvalues Lemma 5.1 shows that many small empirical eigenvalues are at most 128ρ with high probability when n ≤ m/(128p) Theorem 5.

1. Bold model uncertainty quantification: AI systems can determine if a known low-degree model is estimable from random evaluations by calculating the worst-subspace sample threshold, which is bounded by terms like N = (m + t) exp(Ed,k + O(k1/3)) for the minimax error.

2. Sharp noise cost analysis: The system can quantify the exponential separation between noiseless identification and noisy prediction, noting that the parametric rate can require (m + t)4 k exp(-O(k1/3)) samples, whereas O((m + t)2k) suffice for noiseless identification.

3. Uncertainty principle application: The system can employ a quantitative subspace uncertainty principle to find the smallest set carrying a fraction of a polynomial's energy, which is crucial for designing robust sampling strategies in high-dimensional Boolean spaces.

4. Adaptive sampling thresholding: For learning low-degree functions, the system can calculate whether many directions on one Hamming ball are difficult to sample, using bounds derived from the harmonic lift to determine the required number of samples for stable sampling versus parametric regression rates.

5. Minimax risk optimization: The AI can use results like Theorem 5.2 (El Hanchi–Maddison–Erdogdu) to compute the minimax prediction risk, which is determined by the quantile of the empirical covariance matrix, providing a rigorous benchmark for estimator performance regardless of noise level.

6. Model complexity assessment: The system can distinguish between different model classes by analyzing how the ambient dimension and model dimension jointly determine the sample size needed, using corrections like log Npar(d, k, m, A, δ) = 2k − 2k2 / (3d) + O(k3/d2).