The Teaching Dimension of Kernel Perceptron

Akash Kumar, Hanqi Zhang, Adish Singla, Yuxin Chen
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2071-2079, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-kumar21a, title = { The Teaching Dimension of Kernel Perceptron }, author = {Kumar, Akash and Zhang, Hanqi and Singla, Adish and Chen, Yuxin}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2071--2079}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/kumar21a/kumar21a.pdf}, url = {https://proceedings.mlr.press/v130/kumar21a.html}, 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. } }
Endnote
%0 Conference Paper %T The Teaching Dimension of Kernel Perceptron %A Akash Kumar %A Hanqi Zhang %A Adish Singla %A Yuxin Chen %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-kumar21a %I PMLR %P 2071--2079 %U https://proceedings.mlr.press/v130/kumar21a.html %V 130 %X 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.
APA
Kumar, A., Zhang, H., Singla, A. & Chen, Y.. (2021). The Teaching Dimension of Kernel Perceptron . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2071-2079 Available from https://proceedings.mlr.press/v130/kumar21a.html.

Related Material