Fugu-MT 論文翻訳(概要): Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

論文の概要: Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

arxiv url: http://arxiv.org/abs/2610.12358v1
Date: Thu, 08 Oct 2026 17:23:25 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-10 02:36:54.220416
Title: Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Title（参考訳）: ブールキューブのサブスペース不確かさとシャープサンプリング閾値
Abstract要約: ランダム入力は予測に不可欠な領域をアンサンプし、モデルが知られている場合でもパラメトリックレートを遅らせる。ポリアンスキー--サモロディニツキーの不確実性原理を2つの点で研ぎ澄ます。
参考スコア（独自算出の注目度）: 1.4721615285883427
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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σ^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Ψ(k/d), \] 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 the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage $ρ\in(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{\lfloor k^{1/3}\rfloor}$ 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_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（参考訳）: 我々は、d$次元ブール立方体上の次数-最大-k$関数の既知の$m$次元部分空間において、平方集団$L_2$損失の下でガウス回帰を研究する。ランダム入力は予測に不可欠な領域をアンサンプし、モデルが知られている場合でもパラメトリックレートを遅らせる。固定$q_0<1/2$, $1\le k\le q_0d$, and enough 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 \[N=(m+t)\exp\{E_{d,k}+O(k^{1/3})\}, \quad E_{d,k}=d\(k/d), \] where $\(q)=\log2-\mathsf H(\tfrac12-\sqrt{q(1-q)}$および$\mathf H$は自然対数を持つ二進エントロピーである。上界はすべての可能な$m$に対して成り立つ; 一致する下界は$m\le\binom d{\lfloor k^{1/3}\rfloor}$または$t\ge m$のときに成り立つ。ポリアンスキー--サモロディニツキーの不確実性原理を2つの点で研ぎ澄ます。第一に、固定リーク$ρ\in(0,1)$ に対して、多項式のエネルギーが 0 でない次数-at-most-k$ の分数 1-ρ$ を持つ最小の集合は、確率 $\exp\{-E_{d,k}+O_{ρ,q_0}(k^{1/3})\}$ である。エアリーカーネルの構成は、残りは一般に$o(k^{1/3})$では成り立たないことを証明している。第二に、次元 $\binom d{\lfloor k^{1/3}\rfloor}$ の部分空間を構築し、その部分空間のすべての函数は、そのエネルギーの少なくとも1-ρ$を同じ集合上に有する分数 1-ρ$ を持ち、その確率は、少なくとも $\exp\{-E_{d,k}+C_{ρ,q_0}k^{1/3}\}$ である。十分大きな$kの場合、このセットはハミングボールである。パラメトリックレートは$(m+t)4^k\exp\{-O(k^{1/3})\} のサンプルを必要とするが、$O((m+t)2^k)$ sufficeはノイズのない識別のために必要である。 k/d\to0$ の $k\to\infty$ の場合、ノイズ閾値は $(m+t)\exp\{2k+o(k)\}$ となる。

論文の概要: Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

関連論文リスト