2016/02/09 by Carlos Riquelme, Riquelme, Carlos, Ramesh Johari +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1602.02845
openalex publication_date 2016/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of online active learning to collect data for regression modeling. Specifically, we consider a decision maker with a limited experimentation budget who must efficiently learn an underlying linear population model. Our main contribution is a novel threshold-based algorithm for selection of most informative observations; we characterize its performance and fundamental lower bounds. We extend the algorithm and its guarantees to sparse linear regression in high-dimensional settings. Simulations suggest the algorithm is remarkably robust: it provides significant benefits over passive random sampling in real-world datasets that exhibit high nonlinearity and high dimensionality --- significantly reducing both the mean and variance of the squared error.