Report
Researchers report near-quadratic sample compression for all VC classes
The authors say their construction settles the weaker sample compression conjecture, not the stronger linear-size version.
TLDR
In an arXiv preprint, Yang Cai and colleagues report a sample compression scheme of size O(d² log² d) for every binary concept class of VC dimension d. They say this replaces an exponential bound with a polynomial one, proving the weaker version of a longstanding learning-theory conjecture. The full prize is smaller still: the original conjecture asks for O(d), which their result does not establish.
Combined views
2 Sources, first seen ago

Comments