The Teaching Dimension of Kernel Perceptron

Akash Kumar, Hanqi Zhang, Adish Singla, Yuxin Chen

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.

Figure 3: Visualization of a polynomial kernel in its higher-dimensional feature space, where the decision boundary becomes a linear plane.

$\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.

Figure 6: The resulting decision boundary when a Gaussian kernel is taught using a polynomial approximation strategy.

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

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 perceptions.
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},
}
Figure