Xiaojin (Jerry) Zhu

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