Training a classifier to resist small worst-case input changes is expensive in data. Adversarial training, which fits the model on inputs deliberately perturbed to fool it, needs far more labeled examples than ordinary training, and theory confirms that this cost is real. A different question has never been asked. Suppose a helpful teacher who already knows the right robust classifier picks the examples. How few examples does the learner then need? Machine teaching answers this for ordinary classifiers through the recursive teaching dimension, the number of examples needed when concepts are taught in order from easiest to hardest. For ordinary binary classes this number is known to be at most quadratic in the VC dimension. Nobody has defined or bounded it for robust classifiers. Nobody has asked whether a computer program can actually play the teacher or the learner.
We propose to define robust recursive teaching and to show that its answer depends sharply on what the teacher is allowed to say. Suppose the teacher may only show clean labeled points. Then teaching a robust classifier can cost unboundedly more than teaching the underlying one. Now suppose the teacher may attach a "robustness certificate" to a point, meaning "every input within distance $\epsilon$ of $x$ has label $y$." Then robust teaching turns into ordinary teaching of a multiclass class with one extra "not robust here" label. This reduction is the obvious move, and it holds for an idealized learner with unlimited computation. It breaks once the learner must be a computer program, because checking robustness over an infinite neighbourhood need not be decidable. The proposal is built around the questions of when the reduction survives and what the teaching-to-learning ratio becomes.
Core Claim
The relevant prior work splits into four groups. On Robust Multiclass Learnability handles robust learning as a statistical problem. It replaces each hypothesis $h$ by a "corrupted" hypothesis that outputs $h(x)$ when $h$ is constant on the perturbation set $\mathcal{U}(x)$ and a special symbol otherwise. It then bounds robust sample complexity between an adversarial Natarajan dimension $d^{\mathcal{U}}_N$ and an adversarial Graph dimension $d^{\mathcal{U}}_G$. That paper supplies our method; we reuse its corrupted class. However, it studies only passive learners and ignores computability.
On the Computability of Robust PAC Learning motivates the computability side. It shows that a class can be computably learnable and robustly learnable separately yet fail to be robustly learnable by a program, which the authors call the "Sum of Parts Fallacy." It also shows that robust learning can succeed when the robust loss is uncomputable. Both results are binary only, and teaching is absent.
On the Computability of Multiclass PAC Learning constrains us. It characterizes computable multiclass learning with finite label sets through the computable Natarajan dimension. It also proves that the DS dimension, which characterizes multiclass learnability (A Characterization of Multiclass Learnability), does not fit its characterization scheme. We therefore restrict ourselves to finite label sets, and the corrupted class adds only one label.
On the teaching side, Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes proves $RTD \le 39.3752 d^2 - 3.6330 d$ for binary classes. Its argument relies on Sauer's lemma. Lower Bounds for Greedy Teaching Set Constructions shows that greedy teaching can be no better than halving.
Our central claims are three. First, with clean-point teaching there exist classes in which both the underlying class and its corrupted class have small dimension, yet robust teaching needs unboundedly many examples. Second, with certificate teaching the robust teaching dimension equals the recursive teaching dimension of the corrupted multiclass class. That dimension can then be bounded polynomially in $d^{\mathcal{U}}_N$ and the label count $k$. The tool is a multiclass analogue of the Hu et al. recursion, with the Natarajan form of Sauer's lemma replacing the binary one. This gives the first teaching-to-learning ratio for robust learning, with $d^{\mathcal{U}}_N$ as the learning side. Third, there is a teaching analogue of the Sum of Parts Fallacy. We will construct a class over $\mathbb{N}$ that is computably teachable and has finite certificate-teaching dimension, but in which no program can act as the learner.
Research Program
The first stage fixes definitions. We model the teacher as a map from concepts to finite labeled sets, under either clean-point or certificate semantics. We use the recursive (easiest-first) protocol of Zilles et al., with no-clash teaching (Fallat et al.) as a second model that rules out collusion between teacher and learner. Success means the learner outputs a hypothesis with zero robust loss.
The second stage proves the separation. The plan is to embed a no-clash-hard structure into perturbation neighbourhoods. A clean point then cannot reveal how $h^*$ behaves on the rest of $\mathcal{U}(x)$, even though the corrupted class stays small.
The third stage proves the certificate reduction and the polynomial bound. We will rerun the $(x,y)$-class recursion of Hu et al. with Natarajan shattering. The main technical risk sits in the per-step $O(x)$ cost of that recursion: in the multiclass case it may grow with $k$. We will report whatever dependence on $k$ we can actually prove, and we will try to match it with lower-bound constructions that extend the known maximum ratio of $5/3$.
The fourth stage handles computability. We will define computable robust teaching, in which both teacher and learner are programs. We will then build a Halting-problem class in the style of Agarwal et al.. In that class each certificate is truthful, but finding a consistent robust hypothesis requires deciding membership in the perturbation set. We will also look for conditions that rescue the reduction. Our candidate is a computable version of $d^{\mathcal{U}}_N$, in the spirit of the computable robust shattering dimension $c\text{-dim}_U$, and we will test whether its finiteness suffices for computable certificate teaching. Unlike the passive case, where finiteness of $c\text{-dim}_U$ is necessary but not sufficient, a teacher who chooses the examples might close that gap. We will treat this as an open hypothesis, not a claim.
The fifth stage is a small empirical study. It asks whether teacher-chosen labels with certificates help adversarial training when labels are scarce.
Baselines
On the theory side, the reference point is passive robust learning. For the teaching-to-learning ratio, we compare robust teaching dimension against the lower bound $\Omega((d^{\mathcal{U}}_N+\ln(1/\delta))/\epsilon^2)$ for robust learning from On Robust Multiclass Learnability. A teaching result counts as meaningful only if it is independent of $\epsilon$ and polynomial in $d^{\mathcal{U}}_N$.
The naive teaching baseline treats the binary bound of Hu et al. as if it applied to the corrupted class through one-vs-rest decompositions. Following Daniely et al., we expect this to be loose, so beating it means a bound with better dependence on $k$.
Greedy teaching set construction is the algorithmic baseline. On the synthetic classes described below, the recursive procedure must produce strictly smaller teaching sets than greedy on Head-and-Tail-style constructions, consistent with Lower Bounds for Greedy Teaching Set Constructions.
Empirically, the strongest existing method is SSAT-MBI from Adversarial Training in Low-Label Regimes with Margin-Based Interpolation. It reports 52.00% AutoAttack accuracy on CIFAR-10 with 8% of labels, against 50.68% for RST and 49.33% for FixMatch. We will run SSAT-MBI unchanged with a random 8% labeled subset as the do-nothing reference. Our variant keeps the same total label budget and the same unlabeled pool. It changes only which points get labeled, and it adds certificate points: adversarial perturbations of labeled points that carry the teacher's label. Training compute and tuning budget are identical.
The teacher is an off-the-shelf robust model from the RobustBench zoo. Evaluation uses AutoAttack. Beating the baseline means exceeding 52.00% at 8% labels, or matching it with substantially fewer labels.
The key ablation is clean-point teaching with no certificates under the same selection rule. It isolates whether certificates, as the theory predicts, carry the gain.
Why not just…?
Why not just apply ordinary recursive teaching to the corrupted class and stop? That is the content of our second claim when the learner has unlimited computation. The point is that the reduction is not automatic in two ways. A clean-point teacher cannot express the corrupted labels, which is the first claim. A computable learner may be unable to use certificates, which is the third claim. If the computability construction fails, so that every class with finite certificate-teaching dimension turns out to be computably teachable, the proposal shrinks to the multiclass bound. We will report that outcome as such.
Why not just distil the robust teacher into the student on all unlabeled data? This is a real threat to the empirical part. A teacher that labels everything defeats any teacher that labels a subset. We therefore count every teacher query as a label and compare at equal query budget. Distillation at 8% of queries is the fair version, and it becomes a third empirical baseline. If distillation matches certificate teaching at equal budget, the empirical claim fails, and the contribution stays theoretical.
Why not just use greedy core-set or active selection? The theory already rules greedy out in the worst case (Lower Bounds for Greedy Teaching Set Constructions). On natural images it may still work fine, so we run a greedy disagreement-based selection as an additional arm under the identical SSAT-MBI pipeline. If it ties our recursive selection on CIFAR-10, we conclude that the worst-case gap does not show up on natural data.
Proposed Experiments
The decisive theoretical checks are four. The first is the separation construction for clean-point versus certificate teaching. The second is the polynomial bound on certificate-teaching dimension in $d^{\mathcal{U}}_N$ and $k$. The third is the Halting-problem class whose robust teaching dimension is finite but which no program can learn from a teacher. The fourth is a resolution, in either direction, of whether a computable robust Natarajan dimension suffices for computable certificate teaching.
For verification, we enumerate small finite classes over grids with Hamming-ball perturbations, including Head-and-Tail constructions with added perturbation structure. On each we compute exact robust teaching dimension by brute force, since exact RTD is hard to compute in general (A Note on Hardness of Computing Recursive Teaching Dimension), and plot it against $d^{\mathcal{U}}_N$ and $k$ to test the predicted growth. No reported result exists on Lacuna for robust teaching dimension on any class, so these numbers will be new.
On CIFAR-10, and on CIFAR-100 and SVHN where the file gives no reported number, we run the SSAT-MBI comparison described above at several label budgets. The prediction is that certificate teaching beats random selection, clean-point teaching and query-matched distillation, and that the gap is largest at the smallest budgets.
References
- On Robust Multiclass Learnability
- On the Computability of Robust PAC Learning
- On the Computability of Multiclass PAC Learning
- A Characterization of Multiclass Learnability
- Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes
- Lower Bounds for Greedy Teaching Set Constructions
- Teaching Dimensions based on Cooperative Learning
- On Batch Teaching Without Collusion
- On Learnability wih Computable Learners
- Multiclass Learnability and the ERM principle
- Adversarial Training in Low-Label Regimes with Margin-Based Interpolation
- RobustBench: a standardized adversarial robustness benchmark
- A note on hardness of computing recursive teaching dimension