Newest papers

A Sharp Dynamic Haussler Lemma

Shihao Shao, Dacheng Tao · 2026 · arXiv

DOI: 10.48550/arXiv.2610.29898 · open-access PDF

Chinese

哈斯勒的覆盖LEMMA(JCTA 1995)为二进制VC类在正常化的$\ell_1$距离下提供了尖锐的$(C/δ)^d$计量关。我们证明了在正常化的$\ell_p$中为边界的真实值类提供了一个尖锐的全球动态模拟,为每一个$1\le p<\infty$写了$d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$,我们获得了最多每一个地平线和每一个$0&lt\varepsilon<1/2$的最大规模的全球动态覆盖。

Machine translation (Meta M2M100); the English original follows.

Abstract

Haussler's covering lemma (JCTA 1995) gives the sharp $(C/δ)^d$ metric-entropy bound for binary VC classes under normalized $\ell_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized $\ell_p$, for every $1\le p<\infty$. Writing $d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$, we obtain a global dynamic cover of size at most $(C/\varepsilon^p)^d$ for every horizon and $0<\varepsilon<1/2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0&lt

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange