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.
Seed catalog · Showing the bundled record.
Problem statement
Does every binary concept class of VC dimension admit a labeled sample-compression scheme retaining examples and 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
- 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.
- 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.