# Near-optimal Bayesian Active Learning with Correlated and Noisy Tests

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2016.

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

- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [Active Cost-aware Labeling of Streaming Data](https://mlsanity.com/paper/2304.06808/) (2023)
- [Scalable Batch-Mode Deep Bayesian Active Learning via Equivalence Class Annealing](https://mlsanity.com/paper/2112.13737/) (2021)
- [Efficient Online Decision Tree Learning with Active Feature Acquisition](https://mlsanity.com/paper/2305.02093/) (2023)
- [Cost-Aware Recovery-Pathway Identification and Bayesian Optimization for Autonomous Materials Discovery](https://mlsanity.com/paper/2607.23896/) (2026)
- [Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes](https://mlsanity.com/paper/2312.15357/) (2023)
- [Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback](https://mlsanity.com/paper/2610.17760/) (2026)

## Abstract (arXiv)

We consider the Bayesian active learning and experimental design problem, where the goal is to learn the value of some unknown target variable through a sequence of informative, noisy tests. In contrast to prior work, we focus on the challenging, yet practically relevant setting where test outcomes can be conditionally dependent given the hidden target variable. Under such assumptions, common heuristics, such as greedily performing tests that maximize the reduction in uncertainty of the target, often perform poorly. In this paper, we propose ECED, a novel, computationally efficient active learning algorithm, and prove strong theoretical guarantees that hold with correlated, noisy tests. Rather than directly optimizing the prediction error, at each step, ECED picks the test that maximizes the gain in a surrogate objective, which takes into account the dependencies between tests. Our analysis relies on an information-theoretic auxiliary function to track the progress of ECED, and utilizes adaptive submodularity to attain the near-optimal bound. We demonstrate strong empirical performance of ECED on two problem instances, including a Bayesian experimental design task intended to distinguish among economic theories of how people make risky decisions, and an active preference learning task via pairwise comparisons.