# The Teaching Dimension of Kernel Perceptron

arXiv: https://arxiv.org/abs/2010.14043 · HTML: https://mlsanity.com/paper/2010.14043/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

## Built on by (most cited first, 5 of 5)

- [Teaching Humans When To Defer to a Classifier via Exemplars](https://mlsanity.com/paper/2111.11297/) (2021)
- [Iterative Teaching by Label Synthesis](https://mlsanity.com/paper/2110.14432/) (2021)
- [Nonparametric Iterative Machine Teaching](https://mlsanity.com/paper/2306.03007/) (2023)
- [Iterative Teaching by Data Hallucination](https://mlsanity.com/paper/2210.17467/) (2022)
- [Nonparametric Teaching for Multiple Learners](https://mlsanity.com/paper/2311.10318/) (2023)

## Abstract (arXiv)

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 ℝd, and Theta(dk) 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.