← All AI/ML open problems

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.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

For every nonempty finite class C⊆{0,1}X\mathcal C\subseteq\{0,1\}^X on a finite domain, with VC dimension d≥1d\geq1, must some c∈Cc\in\mathcal C have a teaching set T⊆XT\subseteq X of size at most CdCd for a universal constant CC? A teaching set satisfies {h∈C:h∣T=c∣T}={c}\{h\in\mathcal C:h|_T=c|_T\}=\{c\}. Prove this linear bound or construct classes for which the smallest teaching set of every concept is superlinear in dd; the general upper bound currently used as baseline is O(d2)O(d^2).

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

  1. 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.

  2. 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.

  3. 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.