# The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 17 references that are in the map.
- First posted on arXiv 7 Jul 2026.

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

- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [Prediction-Oriented Bayesian Active Learning](https://mlsanity.com/paper/2304.08151/) (2023)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach](https://mlsanity.com/paper/1711.05174/) (2017)
- [Active Learning with Expected Error Reduction](https://mlsanity.com/paper/2211.09283/) (2022)
- [Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design](https://mlsanity.com/paper/1802.08318/) (2018)
- [Approximate Supermodularity Bounds for Experimental Design](https://mlsanity.com/paper/1711.01501/) (2017)
- [Strong Formulations and Algorithms for Regularized A-optimal Design](https://mlsanity.com/paper/2505.14957/) (2025)

## Abstract (arXiv)

Active learning studies the fundamental question: what data should we choose to observe? The greedy algorithm in optimal experiment design is a common heuristic and also equivalent to myopic Bayesian active learning for linear regression, the common framework where long-term planning is replaced with the one-step optimal choice. In this work, we prove a first-of-its-kind approximation ratio for the greedy algorithm's risk that is tight up to an absolute constant. The approximation ratio is linear in the maximum initial leverage score (MILS), a newly identified quantity fundamental to the greedy algorithm's performance. Finally, we illustrate the results with simple numerical simulations.