{"id":"arxiv/2610.29898","url":"https://arxiv.org/abs/2610.29898","tags":["cs.LG","cs.DS","math.CO"],"score":0,"title":"A Sharp Dynamic Haussler Lemma","domain":"cs.LG","source":"arxiv","authors":["Shihao Shao","Dacheng Tao"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-21","reactions":{}}