NEARLY OPTIMAL MINIMAX ESTIMATOR FOR HIGH-DIMENSIONAL SPARSE LINEAR REGRESSION

• 成果类型: Article
• 署名作者: Zhang, Li
• 署名单位: Microsoft
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/13-AOS1141
• 发表日期: 2013
• 页码: 2149-2175
• 关键词: nonconcave penalized likelihood; Orthogonal Matching Pursuit; model selection; Adaptive estimation; variable selection; DANTZIG SELECTOR; Lasso; RISK; RECOVERY; bounds

摘要

We present estimators for a well studied statistical estimation problem: the estimation for the linear regression model with soft sparsity constraints (lq constraint with 0 <= 1) in the high-dimensional setting. We first present a family of estimators, called the projected nearest neighbor estimator and show, by using results from Convex Geometry, that such estimator is within a logarithmic factor of the optimal for any design matrix. Then by utilizing a semi-definite programming relaxation technique developed in [SIAM J. Comput. 36 (2007) 1764-1776], we obtain an approximation algorithm for computing the minimax risk for any such estimation task and also a polynomial time nearly optimal estimator for the important case of l(1) sparsity constraint. Such results were only known before for special cases, despite decades of studies on this problem. We also extend the method to the adaptive case when the parameter radius is unknown.