[论文] Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

论文概要

研究领域: ML 作者: Thomas Weinberger 发布时间: 2026-10-08 arXiv: 2610.12358

中文摘要

我们研究 d 维布尔立方体上次数不超过 k 的函数所构成的已知 m 维子空间中、平方总体 L₂ 损失下的高斯回归。随机输入可能欠采样对预测至关重要的区域，即便模型已知也会拖慢参数速率的达成。对固定 q₀<1/2、1≤k≤q₀d 和充分大的固定 A，置信度 1-e^{-t}（t≥log4）下达到极小极大误差 Aσ²(m+t)/n 的最坏子空间样本阈值为 N=(m+t)exp{E_{d,k}+O(k^{1/3})}，其中 E_{d,k}=dΨ(k/d)，Ψ(q)=log2−H(1/2−√q(1−q))，H 为自然对数下的二元熵。上界对一切可行 m 成立；匹配的下界在 m≤C(d,⌊k^{1/3}⌋) 或 t≥m 时成立。我们在两个方向上加强了 Polyanskiy–Samorodnitsky 不确定性原理：其一，对固定泄漏 ρ∈(0,1)，承载非零次数≤k 多项式 1−ρ 比例能量的最小集合的概率为 exp{−E_{d,k}+O_{ρ,q₀}(k^{1/3})}，Airy 核构造证明余项一般不能是 o(k^{1/3})；其二，我们构造了一个维数为 C(d,⌊k^{1/3}⌋) 的子空间，使其中每个函数都至少有 1−ρ 比例的能量落在同一集合上，该集合概率至多为 exp{−E_{d,k}+C_{ρ,q₀}k^{1/3}}，且对充分大的 k 该集合是 Hamming 球。一个引人注目的推论是噪声的指数级代价：参数速率可能需要 (m+t)4^k exp{−O(k^{1/3})} 个样本，而无噪声识别只需 O((m+t)2^k)。当 k→∞ 且 k/d→0 时，有噪声阈值约为 (m+t)exp{2k+o(k)}。

原文摘要

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

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 t...

---

*自动采集于 2026-10-12*

#论文 #arXiv #ML #小凯