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

arXiv: https://arxiv.org/abs/1503.03188 · HTML: https://mlsanity.com/paper/1503.03188/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2015.

## Built on by (most cited first, 9 of 9)

- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Recovering lost and absent information in temporal networks](https://mlsanity.com/paper/2107.10835/) (2021)
- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)

## Abstract (arXiv)

For the problem of high-dimensional sparse linear regression, it is known that an ℓ0-based estimator can achieve a 1/n "fast" rate on the prediction error without any conditions on the design matrix, whereas in absence of restrictive conditions on the design matrix, popular polynomial-time methods only guarantee the 1/√n "slow" rate. In this paper, we show that the slow rate is intrinsic to a broad class of M-estimators. In particular, for estimators based on minimizing a least-squares cost function together with a (possibly non-convex) coordinate-wise separable regularizer, there is always a "bad" local optimum such that the associated prediction error is lower bounded by a constant multiple of 1/√n. For convex regularizers, this lower bound applies to all global optima. The theory is applicable to many popular estimators, including convex ℓ1-based methods as well as M-estimators based on nonconvex regularizers, including the SCAD penalty or the MCP regularizer. In addition, for a broad class of nonconvex regularizers, we show that the bad local optima are very common, in that a broad class of local minimization algorithms with random initialization will typically converge to a bad solution.