  In this paper, we consider the problem of iterative machine teaching, where a
teacher provides examples sequentially based on the current iterative learner.
In contrast to previous methods that have to scan over the entire pool and
select teaching examples from it in each iteration, we propose a label
synthesis teaching framework where the teacher randomly selects input teaching
examples (e.g., images) and then synthesizes suitable outputs (e.g., labels)
for them. We show that this framework can avoid costly example selection while
still provably achieving exponential teachability. We propose multiple novel
teaching algorithms in this framework. Finally, we empirically demonstrate the
value of our framework.
