The Teaching Dimension of Kernel Perceptron

Understand

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