Online Linear Regression with Paid Stochastic Features

We study an online linear regression setting in which the observed feature vectors are corrupted by noise and the learner can pay to reduce the noise level. In practice, this may happen for several reasons: for example, because features can be measured more accurately using more expensive equipment, or because data providers can be incentivized to release less private features. Assuming feature vectors are drawn i.i.d. from a fixed but unknown distribution, we measure the learner's regret against the linear predictor minimizing a notion of loss that combines the prediction error and payment. We first study the case in which the mapping between payments and noise covariance is known and prove order-optimal regret bounds in the interaction length (up to log-factors). We then derive order-optimal bounds also when the noise covariance is unknown and prove that the regret rate is worse than the case of known covariances. Our analysis leverages matrix martingale concentration, showing that the empirical loss uniformly converges to the expected one for all payments and linear predictors.