Dávid Pál

Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP

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 algo…