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. When the mapping between payments and noise covariance is known, we prove that the rate $\sqrt{T}$ is optimal for regret if logarithmic factors are ignored. When the noise covariance is unknown, we show that the optimal regret rate becomes of order $T^{2/3}$ (ignoring log factors). Our analysis leverages matrix martingale concentration, showing that the empirical loss uniformly converges to the expected one for all payments and linear predictors.

翻译：我们研究一种在线线性回归场景，其中观测到的特征向量被噪声污染，且学习者可以通过付费来降低噪声水平。在实践中，这种情况可能由多种原因导致：例如，使用更昂贵的设备可以更精确地测量特征，或者可以通过激励数据提供者发布隐私性较低的特征。假设特征向量从固定但未知的分布中独立同分布抽取，我们以最小化结合预测误差与支付成本的损失度量的线性预测器为基准，衡量学习者的遗憾。当支付与噪声协方差之间的映射关系已知时，我们证明忽略对数因子后，遗憾的最优速率为 $\sqrt{T}$。当噪声协方差未知时，我们表明忽略对数因子后，最优遗憾速率变为 $T^{2/3}$ 阶。我们的分析利用了矩阵鞅集中性，证明了对于所有支付和线性预测器，经验损失均一致收敛于期望损失。