We revisit the framework of online machine teaching, a special case of active learning in which a teacher with full knowledge of a model attempts to train a learner by adaptively presenting examples. While online machine teaching example selection strategies are typically designed assuming omniscience, i.e., the teacher has absolute knowledge of the learner state, we show that efficient machine teaching is possible even when the teacher is uncertain about the learner initialization. Specifically, we consider the case of learners that perform gradient descent of a quadratic loss to learn a linear classifier, and we propose an online machine teaching algorithm in which the teacher simultaneously learns the learner state while teaching the learner. We theoretically show that the learner’s mean square error decreases exponentially with the number of examples, thus achieving a performance similar to the omniscient case and outperforming two stage strategies that first attempt to make the teacher omniscient before teaching. We empirically illustrate our approach in the context of a cross-lingual sentiment analysis problem.
@article{Urcelay2023Online,
author = {{Martin Urcelay}, B\'elen and Bloch, Matthieu and Rozell, Chris},
journal = {SIAM Journal on Mathematics of Data Science},
title = {Online Machine Teaching under Learner Uncertainty: Gradient Descent Learners of a Quadratic Loss},
year = {2025},
number = {3},
pages = {884-905},
volume = {7},
doi = {10.1137/24M1657997},
file = {:2025-Urcelay-SIAMJMDS-Online Machine Teaching under Learner Uncertainty Gradient Descent Learners of a Quadratic Loss.pdf:PDF},
howpublished = {accepted to \emph{SIAM Journal on Mathematics of Data Science}}
}