Statistical learning theory · Data-efficient learning / Open question
Teaching with Linearly Many Examples
A small set of carefully chosen examples can identify a rule much faster than random sampling. The question asks whether VC complexity also controls this teaching cost linearly.
Seed catalog · Showing the bundled record.
Problem statement
For every nonempty finite class on a finite domain, with VC dimension , must some have a teaching set of size at most for a universal constant ? A teaching set satisfies . Prove this linear bound or construct classes for which the smallest teaching set of every concept is superlinear in ; the general upper bound currently used as baseline is .
Assumptions and scope
- VC dimension is the largest size of a subset of X on which the class realizes every binary labeling. Both the domain and class may grow, and C must be independent of their cardinalities.
- This is best-case teaching within each class, not a claim that every concept has a small teaching set. Applying a universal bound to every nonempty subclass gives the corresponding recursive teaching-dimension bound.
- No restriction to graph-induced, intersection-closed or greedy-constructed classes is allowed in the full conjecture. No polynomial-time algorithm is required for an existential upper bound.
What would settle it?
A universal O(d) bound, or a sequence of finite classes with TS_min/d tending to infinity. An o(d^2) universal upper bound is explicitly partial progress; lower bounds on one greedy algorithm do not refute the conjecture.
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
Hu et al. prove O(d^2). The full binary cube gives a matching-order Omega(d) benchmark for any proposed linear theorem. Compton et al. show obstacles for small-block greedy constructions while leaving the optimal teaching-set question open; Simon settles particular graph-induced classes. No-clash teaching and sample compression are distinct notions. 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
- Compton, Pabbaraju and Zhivotovskiy — Lower Bounds for Greedy Teaching Set Constructions ↗problem statement · source checked 2026-11-19
HTML introduction and main-results table checked: TS_min = O(d) remains the target; the known universal bound is O(d^2). Lower bounds for small-block greedy algorithms are not superlinear lower bounds on the optimum teaching set.
- Hu, Wu, Li and Wang — Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes ↗partial theory · source checked 2026-11-19
Primary abstract checked, corroborated by the 2025 paper: RTD is O(d^2) for finite VC-d classes. The linear conjecture concerns every finite class, not a graph-restricted teaching model.
- Simon — RTD-Conjecture and Concept Classes Induced by Graphs ↗partial theory · source checked 2026-11-19
Abstract checked: the linear conjecture holds for classes of graph stars and connected sets. This is a restricted positive result, not the general finite-class bound.