The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression
Provides the first theoretical guarantee for a widely used heuristic in active learning, addressing a fundamental question for practitioners.
The paper proves a tight approximation ratio for the greedy algorithm in myopic Bayesian active learning for linear regression, showing it is linear in the maximum initial leverage score (MILS).
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.