Optimal Sketching Bounds for Sparse Linear Regression

Tung Mai, Alexander Munteanu, Cameron Musco +3

We study oblivious sketching for $k$-sparse linear regression under various loss functions such as an ${\ell }_p$ norm, or from a broad class of hinge-like loss functions, which inclu…