Bounding Machine Teaching Complexity by the VC Dimension

71 concepts37 papers8 proposals

In classical computational learning theory, we typically measure the complexity of a hypothesis class using the Vapnik-Chervonenkis (VC) dimension. The VC dimension tells us how many random samples an algorithm needs to observe to guarantee good generalization.

But what happens if the data isn't random? Imagine an omniscient, helpful teacher who knows the exact target concept and wants to guide a learner to it using the absolute minimum number of examples. This is the core premise of Machine Teaching.

Intuitively, learning from a targeted teacher should be significantly faster than learning from random data. Yet, for decades, proving a clean mathematical relationship between teaching efficiency and learning capacity remained one of the field's most stubborn challenges. This article explores why mapping teaching to learning is so difficult, how researchers bypassed early paradoxes using cooperative frameworks, and how close we are to proving that teaching complexity is fundamentally bounded by the VC dimension.

The Paradox of the Empty Set

To understand why measuring teaching complexity is tricky, consider a simple concept class over a massive universe of $N$ elements. Our concept class consists of all "singletons" (sets containing exactly one element) plus the empty set $\emptyset$.

If we want to learn a singleton concept from random data, the VC dimension of this class is exactly $1$. It is an incredibly simple class to learn.

Now, let's look at this through the lens of a naive teacher who must provide a "teaching set" of examples that uniquely identifies the target concept:

  • Teaching a singleton $\{x\}$: The teacher simply provides a single positive example: $(x, 1)$. Because no other concept in our class contains $x$, the learner instantly knows the target is $\{x\}$. The cost is $1$.
  • Teaching the empty set $\emptyset$: What example can the teacher provide? If they provide a negative example like $(x, 0)$, they have only ruled out the singleton $\{x\}$. The learner might still wonder if the target is $\{y\}$ or $\{z\}$. To uniquely isolate the empty set, the teacher is forced to provide a negative example for every single element in the universe. The cost is $N$.

This is the fundamental paradox of the standard Teaching Dimension (TD). Even though the concept class has a VC dimension of $1$, its teaching dimension scales with the size of the universe $N$, which could be arbitrarily large or even infinite.

Eliminating the Paradox via Cooperation

The failure of the naive teaching dimension stems from a lack of coordination. The learner doesn't know the teacher is trying to be efficient, so the teacher must brute-force the elimination of every alternative hypothesis.

To fix this, Zilles et al. introduced cooperative learning frameworks. The most prominent of these is the Recursive Teaching Dimension (RTD).

RTD introduces a simple rule: both the teacher and the learner agree on an elimination order of the concepts, from "easiest to teach" to "hardest to teach."

Let's apply RTD to our singleton paradox:

  1. The singletons are easy to teach (cost 1), so they are placed at the front of the queue.
  2. The empty set is hard, so it is placed at the very end.
  3. The learner receives the teaching set. If the teacher provides a positive example $(x, 1)$, the learner identifies $\{x\}$.
  4. What if the target is $\emptyset$? The teacher provides zero examples.

Why does this work? The learner reasons: "If the target were any of the singletons, the teacher would have given me a positive example. Since they gave me nothing, and all singletons are now recursively eliminated from my version space, the only concept left standing is the empty set."

[ Singleton {x} ] ---> Taught with (x, 1) ---> Cost: 1
[ Singleton {y} ] ---> Taught with (y, 1) ---> Cost: 1
       |
       v (Recursively removed from the version space)
       |
[   Empty Set   ] ---> Taught with nothing ---> Cost: 0

By leveraging this hierarchical elimination, the maximum cost to teach any concept in this class drops from $N$ to $1$.

A closely related model is the No-Clash Teaching Dimension (NCTD), analyzed by Fallat et al.. Instead of a strict recursive order, no-clash teaching maps each concept to a unique identifying set of examples such that no two valid concepts "clash" (i.e., produce the same labels on the same subset of points while being ambiguous).

The Linear Teaching Conjecture

With cooperative models like RTD and NCTD successfully neutralizing the empty-set paradox, researchers noticed a striking pattern: for almost every familiar concept class, the cooperative teaching dimension was less than or equal to its VC dimension ($d$).

This led to a major open question formalized by Simon et al.: Is the Recursive Teaching Dimension always linearly bounded by the VC dimension? That is, does there exist a constant $c$ such that for any concept class, $RTD \le c \cdot d$?

For a long time, the best proven upper bounds were discouragingly large. Even when Moran et al. made a breakthrough by shrinking the dependence on the total number of concepts to a double-logarithmic factor, the relationship with the VC dimension itself remained exponential.

The first major structural breakthrough came when Chen et al. proved that the RTD of a concept class is bounded by a function of its VC dimension alone, completely independent of the size of the hypothesis space or the instance universe. They also established that the ratio between RTD and VC dimension can reach at least $5/3$, proving that teaching complexity is not always strictly less than learning complexity.

Breaking the Exponential Barrier

The definitive leap toward resolving the conjecture occurred when Hu et al. shattered the exponential barrier, proving a quadratic upper bound:

$$RTD(C) = O(d^2)$$

To understand why this works, we have to look at how recursive teaching plans are constructed. To find a concept that is easy to teach, you need to find a concept that has a small "uniqueness set" relative to the remaining concepts.

Previous proof techniques failed because when you restrict a concept class to a smaller subset of instances, the structural properties can degrade, adding an additive penalty proportional to the instance space size at each recursive step.

The authors bypassed this by analyzing the combinatorial density of the concept class. They proved that any finite VC class contains at least one concept that can be distinguished from all others using at most a quadratic number of samples relative to $d$. By recursively peeling away this "easy" concept, the entire class can be taught without the complexity ever exploding exponentially.

Why Simple Greedy Strategies Fail

Given that a quadratic bound exists, why has a purely linear bound ($O(d)$) remained so elusive?

The most natural way to build a teaching set is a greedy strategy: pick an instance that splits the remaining version space as evenly as possible, eliminating the maximum number of alternative hypotheses. If greedy strategies worked perfectly, proving the linear conjecture would be straightforward.

However, Pabbaraju et al. proved that greedy teaching set constructions are fundamentally limited. They demonstrated that for certain adversarial concept classes, local greedy choices get trapped in structural bottlenecks, failing to achieve the $O(d)$ bound.

This tells us that the linear teaching conjecture cannot be solved by simple, local heuristics. Achieving a linear bound requires global coordination that respects the deep, underlying geometric structure of the version spaces.

The Power of Sequence and Overlap

While a universal linear bound for batch teaching remains an open problem, researchers have found that changing the rules of interaction can unlock the desired linear efficiency.

1. Sequential Teaching

In a batch setting, the teacher hands over a single set of examples, and the learner must figure it out. In a sequential setting, the teacher provides an example, watches how the learner's hypothesis changes, and then provides the next example.

Mansouri et al. demonstrated that by integrating both the learner's current hypothesis and the remaining version space into the teaching process, sequential teaching achieves a purely linear bound relative to the VC dimension. The interactive feedback loop allows the teacher to dynamically steer the learner past the combinatorial bottlenecks that ruin batch teaching.

2. Representational Overlap

If we must stick to batch teaching, how do we get a linear bound? Mansouri et al. showed that batch teaching complexity can be linearly upper-bounded by the VC dimension if we accept some level of representational overlap between different concepts, such as in preference-based or non-clashing teaching maps.

By relaxing the requirement that a teaching set must be an absolute, unyielding barrier, and instead allowing the learner to utilize soft preferences or non-clashing conditions, the sample complexity of teaching aligns perfectly with the complexity of passive learning.

Summary

The journey to bound machine teaching complexity by the VC dimension reveals a profound truth about communication: efficiency requires shared context.

  • Naive teaching fails because it lacks coordination, leading to teaching costs that scale with the size of the universe.
  • Cooperative frameworks like RTD and NCTD introduce shared elimination protocols, proving that teaching complexity depends solely on the intrinsic structural complexity of the concepts ($O(d^2)$).
  • While local greedy heuristics fail to achieve perfect linearity, dynamic interaction (sequential teaching) or soft structural constraints (non-clashing maps) fully bridge the gap, proving that an optimized teacher can guide a learner using a number of examples directly proportional to the class's fundamental learning capacity.

Key Foundational Work

Neural Networks with Quadratic VC Dimension (1995) — contributed 1 concept elements to this direction.
Threshold Network Learning in the Presence of Equivalences (1991) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 39 papers
  2. Version 1 · 2026-10-04 · 53 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_teaching_to_learning_complexity_ratio_8d6e2c7a,
  title = {teaching-to-learning complexity ratio},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/teaching-to-learning-complexity-ratio/rdr_8d6e2c7a63e2467da20f5d64aeff36ae},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_teaching_to_learning_complexity_ratio_8d6e2c7a_v2,
  title = {teaching-to-learning complexity ratio},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/teaching-to-learning-complexity-ratio/rdr_8d6e2c7a63e2467da20f5d64aeff36ae/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake