Introduction
Algorithmic machine teaching investigates a fundamental question: what is the absolute minimum number of training examples—the teaching dimension—required for a teacher to force a specific target model upon a learner? While traditional research focused on "version-space" learners with finite hypothesis sets, recent work has shifted toward Empirical Risk Minimizers (ERMs) like SVMs. However, the teaching complexity for non-linear ERM learners remained largely unexplored until this study, which rigorously characterizes the teaching dimension for kernelized perceptrons.
Methodology: Constructive Teaching
The authors employ a constructive teaching framework, where a teacher synthesizes specific training examples within the data distribution's support. The strategy varies significantly depending on the kernel's nature:
Exact Teaching for Linear and Polynomial Kernels
For linear and polynomial kernels, the goal is exact parameter matching. The teacher constructs examples that span the orthogonal subspace of the target weights $\theta^*$. By placing points precisely on this orthogonal plane, the teacher effectively "pins down" the decision boundary, forcing the learner's optimization process to nullify any weight components that do not align with the target.
$\epsilon$-Approximate Teaching for Gaussian Kernels
Exact teaching is mathematically impossible for Gaussian kernels because their Reproducing Kernel Hilbert Space (RKHS) is infinite-dimensional. To address this, the authors propose the $\epsilon$-approximate teaching dimension. Here, the teacher aims to ensure the learner's expected risk is within $\epsilon$ of the target model. This is achieved by projecting the infinite-dimensional Gaussian map into a finite-dimensional polynomial approximation using Taylor expansions.
Key Results and Complexity Bounds
The paper establishes rigorous mathematical bounds for different kernel types, showing that degrees of freedom in the feature space dictate teaching complexity:
- Linear Perceptron (in $\mathbb{R}^d$): The exact teaching dimension is $\Theta(d)$.
- Polynomial Perceptron (degree $k$): The dimension is $\Theta(\binom{d+k-1}{k})$, matching the dimensionality of the linear space of homogeneous polynomials.
- Gaussian Perceptron: The $\epsilon$-approximate teaching dimension is bounded by $d^{\mathcal{O}(\log^2 \frac{1}{\epsilon})}$. This represents the first known approximate teaching bound for a non-linear ERM learner.
Insights and Future Directions
A critical insight is that optimal teaching is often "adversarial" in nature; rather than providing typical i.i.d. samples, the teacher places examples precisely on or near the decision boundary to eliminate alternative hypotheses. Future work aims to extend this $\epsilon$-approximate framework to other non-linear ERMs, such as kernel SVMs and logistic regression, while relaxing current assumptions on data distribution and model smoothness.
Summary updated