Near-Quadratic Sample Compression for All VC Classes

Yang Cai, Vineet Gupta, Aranyak Mehta, Shay Moran, Manfred K. Warmuth and colleagues at Google prove the weaker form of the sample compression conjecture, a learning-theory problem open since 1995, and report that the proof was produced autonomously by the Cogentic multi-agent orchestration running on Gemini 4 Carbon.
Ask this paper
The result. Every binary concept class of VC dimension d admits a sample compression scheme of size O(d^2 log^2 d). The best previous bound that depends only on d, from Moran and Yehudayoff in 2016, is exponential in d.
What was open. Floyd and Warmuth conjectured in 1995 that a scheme of size O(d) always exists. A weaker version asks only for size polynomial in d, and this paper settles that weaker version.
How the proof was found. The agent was asked to resolve the conjecture with no hints about approach, under three target tiers. It improved its bound in several steps before arriving at the near-quadratic scheme, at a total API cost of about $344.
Human role. The authors simplified the proof, improved the exposition and connected the techniques to prior work, and they take responsibility for correctness. The main overhead in the scheme comes from the unlabeled points, which the authors name as the target for reaching O(d).
Abstract
The sample compression conjecture is a longstanding open problem in learning theory, originating in the work of Littlestone and Warmuth in the 1980s. At its heart is a connection between simplification and generalization: if a predictor consistent with a training sample is defined using only a small part of that sample, then it is likely to generalize. Sample compression schemes formalize this idea, and many natural learning algorithms can be analyzed this way. The sample compression conjecture of Floyd and Warmuth (1995) asserts that every binary concept class of VC dimension $d$ admits a sample compression scheme of size $O(d)$; a weaker conjecture asks only for size polynomial in $d$. Both have remained open: the first bound depending only on $d$, due to Moran and Yehudayoff (2016), is exponential in $d$. We prove the weaker conjecture by constructing a sample compression scheme of size $O(d^2 \log^2 d)$.