Online A-Optimal Design and Active Linear Regression

Abstract

We consider in this paper the problem of optimal experiment design where a decision maker can choose which points to sample to obtain an estimate $\hat{\beta }$ of the hidden parameter ${\beta }^{\star }$ of an underlying linear model. The key challenge of this work lies in the heteroscedasticity assumption that we make, meaning that each covariate has a different and unknown variance. The goal of the decision maker is then to figure out on the fly the optimal way to allocate the total budget of $T$ samples between covariates, as sampling several times a specific one will reduce the variance of the estimated model around it (but at the cost of a possible higher variance elsewhere). By trying to minimize the ${\ell }^2$-loss $\mathbb{E}[\Vert \hat{\beta }-{\beta }^{\star }{\Vert }^2]$ the decision maker is actually minimizing the trace of the covariance matrix of the problem, which corresponds then to online A-optimal design. Combining techniques from bandit and convex optimization we propose a new active sampling algorithm and we compare it with existing ones. We provide theoretical guarantees of this algorithm in different settings, including a $\mathcal{O}(T^{-2})$ regret bound in the case where the covariates form a basis of the feature space, generalizing and improving existing results. Numerical experiments validate our theoretical findings.

arXiv comment29 pages, 5 figures

References in corpus (11)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Active Learning with Statistical Models
• Information Directed Sampling and Bandits with Heteroscedastic Noise
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
• Active Regression via Linear-Sample Sparsification
• Active Regression by Stratification
• Trading off rewards and errors in multi-armed bandits
• Unbiased estimators for random design regression
• Normal Bandits of Unknown Means and Variances: Asymptotic Optimality, Finite Horizon Regret Bounds, and a Solution to an Open Problem
• Regularized Contextual Bandits
• Online Active Linear Regression via Thresholding

Cited by in corpus (2)

• Stream-based active learning with linear models
• Chernoff Sampling for Active Testing and Extension to Active Regression