A Sharp Dynamic Haussler LemmaResearch Paper
Haussler's packing lemma bounds the number of functions needed to approximate a class of VC dimension on a fixed sample: a static cover of size , independent of the sample size (Haussler 1995). Online learning needs a dynamic version, where the instances arrive one at a time, a cover is a family of prediction rules that see only the…