Online sparse linear regression is an online problem where an algorithm repeatedly chooses a subset of coordinates to observe in an adversarially chosen feature vector, makes a real-valued prediction, receives the true label, and incurs the squared loss. The goal is to design an online learning algorithm with sublinear regret to the best sparse linear predictor in hindsight. Without any assumptions, this problem is known to be computationally intractable. In this paper, we make the assumption that data matrix satisfies restricted isometry property, and show that this assumption leads to computationally efficient algorithms with sublinear regret for two variants of the problem. In the first variant, the true label is generated according to a sparse linear model with additive Gaussian noise. In the second, the true label is chosen adversarially.

本文旨在设计一个在线学习算法，使其具有次线性失望成本并且具有计算效率，以适应在线稀疏线性回归问题。通过利用数据矩阵满足受限等距性质的假设，针对两个问题变体，证明了这个假设可以导致计算效率高的在线学习算法。第一个变体中，真实标签根据带有加性高斯噪声的稀疏线性模型生成，而在第二个变体中，真实标签由对手选择。

自适应特征选择：基于 RIP 的在线稀疏线性回归的计算有效性