A Sharp Dynamic Haussler Lemma
Abstract
Haussler's covering lemma (JCTA 1995) gives the sharp (C/δ)d metric-entropy bound for binary VC classes under normalized ℓ1 distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized ℓp, for every 1≤ p<∞. Writing d=sfatε/32(ℱ), we obtain a global dynamic cover of size at most (C/εp)d for every horizon and 0<ε<1/2. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For 0<ε<1/4, a matching worst-case lower bound (c/ε)pd holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of p. For p=2, this resolves the horizon-independent sequential ℓ2 covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For p=1, it gives the sharp (C/δ)Ldim(ℋ) global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.
Related
BibTeX
@misc{shao2026sharp,
title = {{A Sharp Dynamic Haussler Lemma}},
author = {Shihao Shao and Dacheng Tao},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2610.29898},
eprint = {2610.29898},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29898},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Sharp Dynamic Haussler Lemma
AU - Shihao Shao
AU - Dacheng Tao
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2610.29898
UR - https://arxiv.org/abs/2610.29898
AB - Haussler's covering lemma (JCTA 1995) gives the sharp (C/δ)^d metric-entropy bound for binary VC classes under normalized ℓ_1 distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized ℓ_p, for every 1≤ p<∞. Writing d=sfat_ε/32(ℱ), we obtain a global dynamic cover of size at most (C/ε^p)^d for every horizon and 0<ε<1/2. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For 0<ε<1/4, a matching worst-case lower bound (c/ε)^pd holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of p. For p=2, this resolves the horizon-independent sequential ℓ_2 covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For p=1, it gives the sharp (C/δ)^Ldim(ℋ) global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.
ER -