Optimally compressing VC classes
arXiv:2201.04131v2
AI Analysis
This resolves a foundational problem in computational learning theory, with implications for model compression and generalization in machine learning.
The authors resolved a long-standing conjecture by Littlestone and Warmuth, proving that any concept class with VC-dimension d has a sample compression scheme of size d.
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$.