In classical learning theory, we often measure the complexity of a concept class—the set of possible "rules" a model might learn—using the Vapnik-Chervonenkis (VC) dimension. This metric tells us how many random examples a passive learner needs to see before they can reliably distinguish between different concepts.
However, learning is rarely just a passive process of observing random data. In many scenarios, a "teacher" can choose specific, highly informative examples to guide a learner. This shift from random sampling to intentional selection leads to a fundamental question: How much more efficient is teaching than passive learning?
The answer lies in the relationship between the VC dimension and the Recursive Teaching Dimension (RTD).
The Teacher's Advantage
Imagine trying to teach someone the concept of a "rectangle in a 2D plane." If you give them random points, they might need many samples to find the boundaries. But if you are a teacher, you can simply provide the four corners.
The Teaching Dimension (TD) measures the minimum number of examples needed to uniquely identify a concept within a class. While this sounds efficient, simple TD has a flaw: it can be easily "gamed" by collusion between the teacher and learner. To solve this, researchers like Xi Chen and Bo Tang focus on the Recursive Teaching Dimension (RTD).
RTD works by ordering concepts from "easiest" to "hardest." A teacher first teaches the easiest concepts using very few examples. Once those are eliminated, the remaining pool of concepts becomes smaller, making it easier to teach the next set. This hierarchical approach prevents collusion and provides a more robust measure of a concept class's inherent "teachability."
The RTD Conjecture
The central mystery in this field is the RTD-Conjecture: Is the number of examples required for recursive teaching linearly bounded by the VC dimension?
For decades, the gap between these two measures was vast. While the VC dimension ($d$) provides a linear lower bound for learning, the proven upper bounds for RTD were initially exponential. This suggested that, in the worst case, a teacher might be exponentially less efficient than random sampling—a counterintuitive result.
Significant progress was made by Lunjia Hu and Liwei Wang, who proved a quadratic upper bound, showing that $RTD(C) = O(d^2)$. While this moved the field closer to a linear relationship, a gap remains. As Xi Chen noted, the highest known empirical ratio of RTD to VC dimension is only 5/3, far below the quadratic limit.
Geometry as a Bridge
To understand why the linear bound is so elusive, researchers have turned to the geometry of the concepts themselves. Hans U. Simon has shown that for concept classes derived from graph structures—such as "stars" or "connected subgraphs"—the RTD-Conjecture actually holds. In these structured domains, the most informative examples provide a learning benefit that is almost perfectly proportional to the complexity of learning from random data ($VCD - 1 \le RTD \le VCD$).
However, when the underlying structure becomes more complex, the relationship can break down. Fionn Mc Inerney and Sébastien Ratel found that in certain graph topologies, like "trees of cycles," the teaching dimension can actually exceed the VC dimension. This suggests that the VC dimension is not a universal upper bound for all forms of interactive learning.
Why the Gap Matters
Resolving the relationship between RTD and VC dimension isn't just a theoretical exercise; it has deep implications for how we understand model capacity and data efficiency:
- Sample Compression: The RTD-Conjecture is closely linked to the Sample Compression Conjecture, which posits that any concept class with a small VC dimension can be "compressed" into a tiny subset of examples. If RTD is linearly bounded by VC dimension, it would provide a powerful tool for proving this conjecture.
- Verification vs. Training: As Jonathan Shafer and Saachi Mutreja have explored, it is often quadratically easier to verify a model's quality than to train it. Understanding the limits of teaching helps clarify this "P vs. NP" of machine learning.
- Information Complexity: Recent work by Mahdi Haghifam and Shay Moran has shown that the information a learner reveals about its training data (Conditional Mutual Information) cannot always be bounded by the VC dimension alone. This suggests that "complexity" is multi-faceted, and the VC dimension may only be capturing one slice of the puzzle.
By narrowing the gap between passive learning (VC) and interactive teaching (RTD), researchers are moving toward a unified theory of how information—whether random or curated—is converted into knowledge.