# Preference-based Teaching

arXiv: https://arxiv.org/abs/1702.02047 · HTML: https://mlsanity.com/paper/1702.02047/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2017.

## Built on by (most cited first, 11 of 11)

- [Machine Teaching for Inverse Reinforcement Learning: Algorithms and Applications](https://mlsanity.com/paper/1805.07687/) (2018)
- [Non-Clashing Teaching Maps for Balls in Graphs](https://mlsanity.com/paper/2309.02876/) (2023)
- [The Computational Complexity of Positive Non-Clashing Teaching in Graphs](https://mlsanity.com/paper/2503.07665/) (2025)
- [When Redundancy Matters: Machine Teaching of Representations](https://mlsanity.com/paper/2401.12711/) (2024)
- [Distribution Matching for Machine Teaching](https://mlsanity.com/paper/2105.13809/) (2021)
- [MAP- and MLE-Based Teaching](https://mlsanity.com/paper/2307.05252/) (2023)
- [Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds](https://mlsanity.com/paper/2602.00657/) (2026)
- [Conditional Teaching Size](https://mlsanity.com/paper/2107.07038/) (2021)
- [On a Combinatorial Problem Arising in Machine Teaching](https://mlsanity.com/paper/2402.04907/) (2024)
- [Teaching and Learning under Deductive Errors](https://mlsanity.com/paper/2605.13384/) (2026)
- [Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization](https://mlsanity.com/paper/2605.22964/) (2026)

## Abstract (arXiv)

We introduce a new model of teaching named "preference-based teaching" and a corresponding complexity parameter---the preference-based teaching dimension (PBTD)---representing the worst-case number of examples needed to teach any concept in a given concept class. Although the PBTD coincides with the well-known recursive teaching dimension (RTD) on finite classes, it is radically different on infinite ones: the RTD becomes infinite already for trivial infinite classes (such as half-intervals) whereas the PBTD evaluates to reasonably small values for a wide collection of infinite classes including classes consisting of so-called closed sets w.r.t. a given closure operator, including various classes related to linear sets over mathbbN0 (whose RTD had been studied quite recently) and including the class of Euclidean half-spaces. On top of presenting these concrete results, we provide the reader with a theoretical framework (of a combinatorial flavor) which helps to derive bounds on the PBTD.