cs.LGNov 18, 2026

Near-Quadratic Sample Compression for All VC Classes

Authors: Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang, 

Organizations: Google · Yale University · the Technion

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 dd admits a sample compression scheme of size O(d)O(d); a weaker conjecture asks only for size polynomial in dd. Both have remained open: the first bound depending only on dd, due to Moran and Yehudayoff (2016), is exponential in dd. We prove the weaker conjecture by constructing a sample compression scheme of size O(d2log⁡2d)O(d^2 \log^2 d).

Figures & tables

Explore similar work

May 12, 2026

High-arity Sample Compression

Recently, a series of works have started studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. In this work, we consider a high-arity variant of sample compression schemes and we prove that the existence of a high-arity sample compression scheme of non-trivial quality implies high-arity PAC learnability.
May 13, 2026

What is Learnable in Valiant's Theory of the Learnable?

Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: Which classes are learnable in it? For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that dd-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a poly(d)O~(1/ε)\mathrm{poly}(d) \tilde{O}(1/ε) sample and poly(d)polylog(1/ε)\mathrm{poly}(d) \mathrm{polylog}(1/ε) query algorithm, and prove that at least Ω(d)Ω(d) samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.
Oct 17, 2026

Uniform convergence at optimal rate and scale

Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension dd, the sharp worst-case sample complexity for additive error ε\varepsilon is of order d/ε2d/\varepsilon^2. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale γγ. The challenge is to achieve error γ+εγ+\varepsilon with order d/ε2d/\varepsilon^2 samples, matching the sample bound for binary classes, where dd is now the fat-shattering dimension at scale γγ. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns ε\varepsilon-nets with margin. A classical ε\varepsilon-net intersects every set of mass at least ε\varepsilon in a prescribed family; we allow the net to intersect a slightly enlarged version of each such set. Remarkably, this relaxation permits bounds independent of the ambient dimension in natural geometric settings. Second, we derive improved covering bounds in both discrete and real-valued settings: we extend Haussler's covering lemma to partial concept classes and use this extension to obtain ℓ2\ell_2 covers at the optimal scale for real-valued function classes. Third, we obtain a chaining bound at the optimal scale by aligning the covers so that successive approximations become increasingly close to one another.