Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators

Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan

For the problem of high-dimensional sparse linear regression, it is known that an ${\ell }_0$-based estimator can achieve a $1/n$ "fast" rate on the prediction error without any condi…