# The Cost of Replicability in Active Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 12 Dec 2024.

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

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Replicable Bandits](https://mlsanity.com/paper/2210.01898/) (2022)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Replicable Online Learning](https://mlsanity.com/paper/2411.13730/) (2024)

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

- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)
- [Replicable Bandits with UCB based Exploration](https://mlsanity.com/paper/2604.20024/) (2026)

## Abstract (arXiv)

Active learning aims to reduce the number of labeled data points required by machine learning algorithms by selectively querying labels from initially unlabeled data. Ensuring replicability, where an algorithm produces consistent outcomes across different runs, is essential for the reliability of machine learning models but often increases sample complexity. This paper investigates the cost of replicability in active learning using two classical disagreement-based methods: the CAL and A^2 algorithms. Leveraging randomized thresholding techniques, we propose two replicable active learning algorithms: one for realizable learning of finite hypothesis classes and another for the agnostic setting. Our theoretical analysis shows that while enforcing replicability increases label complexity, CAL and A^2 still achieve substantial label savings under this constraint. These findings provide insights into balancing efficiency and stability in active learning.