Paper ID: 2201.04131

Optimally compressing VC classes

Zachary Chase

Resolving a conjecture of Littlestone and Warmuth, we show that any concept class of VC-dimension $d$ has a sample compression scheme of size $d$.

Submitted: Jan 11, 2022