The Teaching Dimension of Kernel Perceptron

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.

arXiv commentAISTATS 2021

References in corpus (9)

• Why Deep Neural Networks for Function Approximation?
• An Overview of Machine Teaching
• Iterative Machine Teaching
• Near-Optimally Teaching the Crowd to Classify
• Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners
• Teaching Inverse Reinforcement Learners via Features and Demonstrations
• Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints
• Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
• Optimal Collusion-Free Teaching

Cited by in corpus (1)

• Iterative Teaching by Label Synthesis