Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
This work addresses a fundamental limitation in machine learning for researchers and practitioners using popular polynomial-time sparse regression methods, revealing that slow rates are intrinsic and not just due to algorithm design, which is incremental in clarifying theoretical bounds.
The paper tackles the problem of high-dimensional sparse linear regression by showing that a broad class of M-estimators, including convex and nonconvex methods, inherently suffer from a slow prediction error rate of 1/√n due to bad local optima, contrasting with the fast 1/n rate achievable by ℓ0-based estimators.
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.