# Teaching an Active Learner with Contrastive Examples

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 28 Oct 2021.

## Builds on (most cited first, 19 of 19)

- [An Overview of Machine Teaching](https://mlsanity.com/paper/1801.05927/) (2018)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Iterative Machine Teaching](https://mlsanity.com/paper/1705.10470/) (2017)
- [ALICE: Active Learning with Contrastive Natural Language Explanations](https://mlsanity.com/paper/2009.10259/) (2020)
- [Near-Optimally Teaching the Crowd to Classify](https://mlsanity.com/paper/1402.2092/) (2014)
- [Teaching Categories to Human Learners with Visual Explanations](https://mlsanity.com/paper/1802.06924/) (2018)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Interactive Teaching Algorithms for Inverse Reinforcement Learning](https://mlsanity.com/paper/1905.11867/) (2019)
- [Towards Black-box Iterative Machine Teaching](https://mlsanity.com/paper/1710.07742/) (2017)
- [Teaching Inverse Reinforcement Learners via Features and Demonstrations](https://mlsanity.com/paper/1810.08926/) (2018)
- [Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints](https://mlsanity.com/paper/1906.00429/) (2019)
- [Teaching Multiple Concepts to a Forgetful Learner](https://mlsanity.com/paper/1805.08322/) (2018)
- [Understanding the Role of Adaptivity in Machine Teaching: The Case of Version Space Learners](https://mlsanity.com/paper/1802.05190/) (2018)
- [Machine Teaching of Active Sequential Learners](https://mlsanity.com/paper/1809.02869/) (2018)
- [An Optimal Control Approach to Sequential Machine Teaching](https://mlsanity.com/paper/1810.06175/) (2018)
- [Robust Learning from Discriminative Feature Feedback](https://mlsanity.com/paper/2003.03946/) (2020)
- [String Submodular Functions with Curvature Constraints](https://mlsanity.com/paper/1303.3018/) (2013)
- [Generalized Binary Search For Split-Neighborly Problems](https://mlsanity.com/paper/1802.09751/) (2018)
- [An Optimal Control View of Adversarial Machine Learning](https://mlsanity.com/paper/1811.04422/) (2018)

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

- [Optimal Design for Reward Modeling in RLHF](https://mlsanity.com/paper/2410.17055/) (2024)
- [Iterative Teaching by Data Hallucination](https://mlsanity.com/paper/2210.17467/) (2022)
- [Deep Active Learning in the Presence of Label Noise: A Survey](https://mlsanity.com/paper/2302.11075/) (2023)
- [When Redundancy Matters: Machine Teaching of Representations](https://mlsanity.com/paper/2401.12711/) (2024)
- [Formal Models of Active Learning from Contrastive Examples](https://mlsanity.com/paper/2506.15893/) (2025)
- [XAL: EXplainable Active Learning Makes Classifiers Better Low-resource Learners](https://mlsanity.com/paper/2310.05502/) (2023)
- [Multi-Modal, Multi-Environment Machine Teaching for Robust Reward Learning](https://mlsanity.com/paper/2607.08647/) (2026)
- [Optimally Teaching a Linear Behavior Cloning Agent](https://mlsanity.com/paper/2311.15399/) (2023)
- [On a Combinatorial Problem Arising in Machine Teaching](https://mlsanity.com/paper/2402.04907/) (2024)
- [Label-Efficient Skeleton-based Recognition with Stable-Invertible Graph Convolutional Networks](https://mlsanity.com/paper/2511.17345/) (2025)
- [Active Learning for GCN-based Action Recognition](https://mlsanity.com/paper/2511.21625/) (2025)
- [Learning Half-Spaces from Perturbed Contrastive Examples](https://mlsanity.com/paper/2602.02080/) (2026)

## Abstract (arXiv)

We study the problem of active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance xq, the teacher provides the requested label xq, yq along with explanatory information to guide the learning process. In this paper, we view this information in the form of an additional contrastive example (xc, yc) where xc is picked from a set constrained by xq (e.g., dissimilar instances with the same label). Our focus is to design a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads to a challenging sequence optimization problem where the algorithm's choices at a given round depend on the history of interactions. We investigate an efficient teaching algorithm that adaptively picks these contrastive examples. We derive strong performance guarantees for our algorithm based on two problem-dependent parameters and further show that for specific types of active learners (e.g., a generalized binary search learner), the proposed teaching algorithm exhibits strong approximation guarantees. Finally, we illustrate our bounds and demonstrate the effectiveness of our teaching framework via two numerical case studies.