Abstract: Algorithmic machine teaching has been studied under the linear setting where exact teaching is possible. However, little is known for teaching nonlinear learners. Here, we establish the sample complexity of teaching, aka teaching dimension, for kernelized perceptrons for different families of feature maps. As a warm-up, we show that the teaching complexity is $\Theta(d)$ for the exact teaching of linear perceptrons in $\mathbb{R}^d$, and $\Theta(d^k)$ for kernel perceptron with a polynomial kernel of order $k$. Furthermore, under certain smooth assumptions on the data distribution, we establish a rigorous bound on the complexity for approximately teaching a Gaussian kernel perceptron. We provide numerical examples of the optimal (approximate) teaching set under several canonical settings for linear, polynomial and Gaussian kernel perceptrons.
Introduction
In algorithmic machine teaching, the goal is to identify the smallest set of training examples—the Teaching Dimension (TD)—that can guide a learner to a specific target hypothesis. While well-understood for linear models, teaching nonlinear learners presents significant challenges. Nonlinear models, particularly those using kernels, often operate in high-dimensional or even infinite-dimensional feature spaces, making the "version space" of possible hypotheses difficult to constrain with finite data. This paper provides the first rigorous theoretical bounds for teaching kernel perceptrons, both exactly and approximately.
Teaching Linear and Polynomial Kernels
The authors first address cases where exact teaching is possible. For a linear perceptron in $d$ dimensions, the teaching dimension is $\Theta(d)$. Moving to polynomial kernels of degree $k$, the complexity increases to $\Theta(d^k)$, which corresponds to the dimension of the expanded feature space. In these scenarios, a teacher can strategically place points to "nullify" incorrect hypothesis directions, effectively forcing the learner's Empirical Risk Minimization (ERM) process toward the target.
Approximate Teaching for Gaussian Kernels
Gaussian kernels present a unique challenge because their feature maps are infinite-dimensional. Perfectly teaching a Gaussian decision boundary would theoretically require an infinite number of points. To resolve this, the authors introduce the $\epsilon$-approximate teaching dimension ($\epsilon$-TD). This metric measures the number of examples needed to ensure the learner's expected risk is within a margin $\epsilon$ of the target's risk.
The key insight lies in the rapid decay of eigenvalues in Gaussian kernels. Most of the decision boundary's information is captured by low-order polynomial components. By teaching a high-degree polynomial approximation of the Gaussian boundary, the teacher can achieve high precision with a finite teaching set.
Key Results and Validation
The theoretical bounds established are:
- Linear Perceptron: $TD = \Theta(d)$.
- Polynomial Perceptron: $TD = \Theta(\binom{d+k-1}{k})$.
- Gaussian Perceptron: $\epsilon-TD = d^{O(\log^2 \frac{1}{\epsilon})}$.
The Gaussian result is particularly significant, showing that complexity scales polylogarithmically with precision. These bounds were validated using synthetic datasets like the "two-moon," "two-circles," and "banana" datasets, as well as the real-world Iris benchmark. Simulations confirmed that as the size of the teaching set grows (aligned with the polynomial approximation degree), the error between the taught and target models decreases sharply, matching theoretical predictions.
Conclusion
This work extends algorithmic machine teaching into the nonlinear domain, providing a framework for understanding the complexity of teaching complex kernel-based models. While the current analysis assumes certain smoothness in data distribution, it lays the groundwork for future studies on other ERM learners like Kernel SVM or Logistic Regression. Future work will also explore non-constructive settings where the teacher is limited to a fixed pool of existing data points.
Summary updated