Leverage Score Sampling for Faster Accelerated Regression and ERM

Naman Agarwal, Sham Kakade, Rahul Kidambi +3

Given a matrix $\mathbf{A}\in {\mathbb{R}}^{n\times d}$ and a vector $b\in {\mathbb{R}}^d$, we show how to compute an $\epsilon$-approximate solution to the regression problem $ \min_{x\in\m…