LodeHQ
AI news for people who shipFree, by email

AI · arxiv.org · Friday, 20 November 2026

A new bound makes sample compression polynomial for every VC class

A new result proves the weaker sample compression conjecture for every binary concept class with VC dimension d, replacing the previous exponential-in-d bound with a scheme of size O(d² log² d). In plain terms, a consistent predictor can be represented using a much smaller part of its training sample, supporting tighter generalization analysis. The stronger goal, a linear O(d) scheme, remains open.

Read the source: arxiv.org ↗In the 20 November issue →