Metraipolis › archive › dc_85d0dfae1eef

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube — arXiv:2610.12358

Source

arXiv (en)

Original

https://arxiv.org/abs/2610.12358

License (as archived)

CC0-1.0

Archived

2026-10-09T06:26:22.339Z

SHA-256 of the archived text

1a70d5c3bd7d59ddc3aca9e8bdf8253e68464912a7118c3e7a9b08f92470d240

Stable URL of this page

https://metraipolis.com/documento/dc_85d0dfae1eef

How to cite

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube — arXiv:2610.12358 — arXiv (en), https://arxiv.org/abs/2610.12358 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_85d0dfae1eef (Metraipolis archive dc_85d0dfae1eef, sha256 1a70d5c3bd7d59ddc3aca9e8bdf8253e68464912a7118c3e7a9b08f92470d240)

@misc{dc85d0dfae1eef,
  title = {Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube — arXiv:2610.12358},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.12358},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_85d0dfae1eef; sha256 1a70d5c3bd7d59ddc3aca9e8bdf8253e68464912a7118c3e7a9b08f92470d240},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.12358. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\sigma^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\Psi(k/d), \] where $\Psi(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 $\rho\in(0,1)$, the smallest set carrying a fraction $1-\rho$ of a nonzero degree-at-most-$k$ polynomial's energy has probability $\exp\{-E_{d,k}+O_{\rho,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-\rho$ of its energy on the same set, whose probability is at most $\exp\{-E_{d,k}+C_{\rho,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)\}$.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Probability (math.PR) ; Information Theory (cs.IT); Machine Learning (cs.LG); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.12358 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:50:32.295Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).