The Teaching Dimension of Kernel Perceptron

Akash Kumar, Hanqi Zhang, Adish Singla, Yuxin Chen

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.

Comparison of teaching sets for linear and polynomial kernels in both input and feature spaces.

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.

The process of teaching a Gaussian kernel perceptron using polynomial approximation on the two-moon dataset.

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

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.
BibTeX
@inproceedings{kumar2021teaching,
  author = {Akash Kumar and Hanqi Zhang and Adish Singla and Yuxin Chen},
  title = {{The Teaching Dimension of Kernel Perceptron}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=zPD0hBebRMT},
}

Loading related content...

Figure