← All AI/ML open problems

Statistical learning theory / Open question

Can Every Learnable Rule Be Compressed?

If a rule can be learned from limited evidence, must every consistent dataset have a comparably small explanation? This is a precise form of the connection between simplicity and generalization.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Does every binary concept class of VC dimension dd admit a labeled sample-compression scheme retaining O(d)O(d) examples and O(d)O(d) side-information bits? A fixed compressor and reconstructor must encode every finite realizable sample so that the reconstructed classifier agrees with all its labels, including the discarded ones.

Assumptions and scope

  • Fix the binary concept class before receiving the sample; the decoder knows that class but has no access to discarded examples or their indices.
  • Retained examples must come from the input sample. State and charge side-information bits separately; unrestricted side information would trivialize the question.
  • Use labeled, potentially improper reconstruction in the base formulation. Unlabeled, proper, stable, computationally efficient and exact-size-d schemes are distinct stronger variants.

What would settle it?

A universal linear bound on retained examples plus side bits, or a superlinear lower-bound family under that convention. Bounds with larger side-information budgets or improvements below the known near-quadratic bound are partial progress with their scope stated.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Moran and Yehudayoff proved sample-independent exponential compression for binary classes. Cai et al.'s November 18, 2026 preprint claims O(d² log² d) examples with O(d log² d) side bits, resolving the polynomial-size version. The linear-size question remains; neither polynomial compression nor basic compression-based generalization is listed as open. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Cai et al. — Near-Quadratic Sample Compression for All VC Classes ↗problem statement · source checked 2026-11-19

    Full HTML introduction, definition and Theorem 1.1 checked: O(d² log² d) retained examples and O(d log² d) side bits; the linear-size conjecture remains the target. The November 18 preprint discloses AI-generated discovery; the proof is not independently audited here.

  2. Moran and Yehudayoff — Sample Compression Schemes for VC Classes ↗partial theory · source checked 2026-11-19

    Primary abstract and correction checked: exponential-in-VC compression for binary classes; an earlier multiclass statement was erroneous. The new near-quadratic binary bound is a subsequent improvement.