How Fast can a Learner Learn under an Optimal Teacher?
For an ERM learner, if the environment feeds it iid training data then
the classic PAC bound holds. If a teacher feeds it optimal teaching
data then the classic Teaching Dimension takes over. We will explore
the latter case a bit deeper. What if the teacher knows the learner’s
specific algorithm? What if the teacher must choose teaching items
from a given iid data pool? What if the teacher must teach
sequentially? Our attempt to answer these questions opens up
connections to fields such as control theory and reinforcement
learning.