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

DOI10.1214/17-EJS1233MaRDI QIDQ521327zbMATH OpenOpenAlexFDO

Authors Yuchen Zhang, Martin J. Wainwright, Michael Jordan

Publication date 7 April 2017

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.03188, https://projecteuclid.org/euclid.ejs/1489201320

zbMATH Keywords

computationally-constrained minimax theoryhigh-dimensional statisticsnonconvex optimizationsparse linear regression

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Linear regression; mixed models (62J05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: For the problem of high-dimensional sparse linear regression, it is known that an $el{l}_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/sqrtn$ "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/sqrtn$. For convex regularizers, this lower bound applies to all global optima. The theory is applicable to many popular estimators, including convex $el{l}_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.

Recommendations

• Slope meets Lasso: improved oracle bounds and optimality
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
• A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
• Fast global convergence of gradient methods for high-dimensional statistical recovery

Cited in

(9)

• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Optimal prediction in the linearly transformed spiked model
• Finite-sample analysis of \(M\)-estimators using self-concordance
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• Grouped variable selection with discrete optimization: computational and statistical perspectives
• Estimation of Linear Functionals in High-Dimensional Linear Models: From Sparsity to Nonsparsity
• Robust decoding from binary measurements with cardinality constraint least squares
• Fitting sparse linear models under the sufficient and necessary condition for model identification
• A reproducing kernel Hilbert space approach to high dimensional partially varying coefficient model

This page was built for publication: Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521327)