# Near-Exponential Savings for Mean Estimation with Active Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 7 Nov 2025.

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

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- ["What We Can't Measure, We Can't Understand": Challenges to Demographic Data Procurement in the Pursuit of Fairness](https://mlsanity.com/paper/2011.02282/) (2020)
- [Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits](https://mlsanity.com/paper/1507.04523/) (2015)
- [Are sample means in multi-armed bandits positively or negatively biased?](https://mlsanity.com/paper/1905.11397/) (2019)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Beyond Ads: Sequential Decision-Making Algorithms in Law and Public Policy](https://mlsanity.com/paper/2112.06833/) (2021)
- [Building Bridges: Viewing Active Learning from the Multi-Armed Bandit Lens](https://mlsanity.com/paper/1309.6830/) (2013)
- [Addressing Discretization-Induced Bias in Demographic Prediction](https://mlsanity.com/paper/2405.16762/) (2024)

## Abstract (arXiv)

We study the problem of efficiently estimating the mean of a k-class random variable, Y, using a limited number of labels, N, in settings where the analyst has access to auxiliary information (i.e.: covariates) X that may be informative about Y. We propose an active learning algorithm ("PartiBandits") to estimate mathbbE[Y]. The algorithm yields an estimate, widehatμPB, such that left( widehatμPB - mathbbE[Y]right)2 is tildeOleft( fracnu + exp(c · (-N/log(N))) N right), where c > 0 is a constant and nu is the risk of the Bayes-optimal classifier. PartiBandits is essentially a two-stage algorithm. In the first stage, it learns a partition of the unlabeled data that shrinks the average conditional variance of Y. In the second stage it uses a UCB-style subroutine ("WarmStart-UCB") to request labels from each stratum round-by-round. Both the main algorithm's and the subroutine's convergence rates are minimax optimal in classical settings. PartiBandits bridges the UCB and disagreement-based approaches to active learning despite these two approaches being designed to tackle very different tasks. We illustrate our methods through simulation using nationwide electronic health records. Our methods can be implemented using the PartiBandits package in R.