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

Abstract

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 conditions on the design matrix, whereas in absence of restrictive conditions on the design matrix, popular polynomial-time methods only guarantee the $1/\sqrt{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/\sqrt{n}$. For convex regularizers, this lower bound applies to all global optima. The theory is applicable to many popular estimators, including convex ${\ell }_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.

Add more coverage on related work; add a new lower bound for design matrices satisfying the restricted eigenvalue condition

References in corpus (3)

• Nearly unbiased variable selection under minimax concave penalty
• On the Prediction Performance of the Lasso
• Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions

Cited by in corpus (1)

• Optimistic lower bounds for convex regularized least-squares