A Sharp Dynamic Haussler Lemma

Haussler’s covering lemma (JCTA 1995) gives the sharp $(C\mathrm{/}\delta {)}^d$ metric-entropy bound for binary VC classes under normalized ${\mathrm{\ell }}_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized ${\mathrm{\ell }}_p$, for every $1\le p<\mathrm{\infty }$. Writing $d={\mathrm{sfat}}_{\epsilon \mathrm{/}32}(\mathcal{F})$, we obtain a global dynamic cover of size at most $(C\mathrm{/}{\epsilon }^p{)}^d$ for every horizon and $0<\epsilon <1\mathrm{/}2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0<\epsilon <1\mathrm{/}4$, a matching worst-case lower bound $(c\mathrm{/}\epsilon {)}^{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 ${\mathrm{\ell }}_2$ covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For $p=1$, it gives the sharp $(C\mathrm{/}\delta {)}^{\mathrm{Ldim}(\mathcal{H})}$ 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.