← News

ResearchSources: arXiv · 20 Nov 2026

Learning theory conjecture resolved with near-quadratic compression bound

Researchers report a sample compression scheme of size O(d² log² d) for every binary concept class of VC dimension d, settling a weakened form of the Floyd–Warmuth conjecture.

In plain words

Learning theorists study whether a rule trained on data can be described using only a small subset of that data; if so, the rule tends to generalize well. A 1995 conjecture asked whether such a compact description always exists, with size scaling reasonably with a class's complexity measure. The authors show it does, with a near-quadratic bound.

What was announced

The sample compression conjecture, traced to Littlestone and Warmuth in the 1980s, links simplification to generalization: a predictor consistent with a training sample but defined from only a small part of it is likely to generalize. Floyd and Warmuth's 1995 version asserts that every binary concept class of VC dimension d admits a compression scheme of size O(d). That stronger claim remains open, as does the weaker polynomial-size variant, according to the paper.

The authors report settling the weaker variant. The first known bound depending only on d, due to Moran and Yehudayoff in 2016, was exponential in d. The new construction achieves size O(d² log² d), which is polynomial in d, though still above the linear bound the original conjecture targets. The result appears in an arXiv abstract; the summary does not cover proofs, constants, or peer review.

What it does not show

  • The source is an arXiv abstract only; it does not establish peer review, proof details, or the scheme's practicality.
  • The original O(d) conjecture of Floyd and Warmuth remains open; only the weaker polynomial-size version is claimed resolved.

Sources

Source-support review completed 21 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.

Coverage: arXiv: abstract.

Updates and corrections

No corrections so far.

First published 21 Nov 2026

New to the subject? AI from the Ground Up starts from the beginning.