OVERCOMING THE LIMITATIONS OF PHASE TRANSITION BY HIGHER ORDER ANALYSIS OF REGULARIZATION TECHNIQUES

• 成果类型: Article
• 署名作者: Weng, Haolei; Maleki, Arian; Zheng, Le
• 署名单位: Columbia University; Columbia University
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/17-AOS1651
• 发表日期: 2018
• 页码: 3014-3044
• 关键词: VARIABLE SELECTION; regression; Lasso; neighborliness; asymptotics; EQUATIONS; sparsity; bridge; cdma; RISK

摘要

We study the problem of estimating a sparse vector beta is an element of R-p from the response variables y = X beta + omega, where omega similar to N(0, sigma(2)(omega) I-nxn), under the following high-dimensional asymptotic regime: given a fixed number delta, p -> infinity, while n/p -> delta. We consider the popular class of l(q)-regularized least squares (LQLS), a.k.a. bridge estimators, given by the optimization problem (beta) over cap(lambda, q) is an element of arg min(beta) 1/2 parallel to y - X beta parallel to(2)(2) + lambda parallel to beta parallel to(q)(q), and characterize the almost sure limit of 1/p parallel to(beta) over cap(lambda, q) - beta parallel to(2)(2), and call it asymptotic mean square error (AMSE). The expression we derive for this limit does not have explicit forms, and hence is not useful in comparing LQLS for different values of delta, or providing information in evaluating the effect of d or sparsity level of beta. To simplify the expression, researchers have considered the ideal error-free regime, that is, omega = 0, and have characterized the values of d for which AMSE is zero. This is known as the phase transition analysis. In this paper, we first perform the phase transition analysis of LQLS. Our results reveal some of the limitations and misleading features of the phase transition analysis. To overcome these limitations, we propose the small error analysis of LQLS. Our new analysis framework not only sheds light on the results of the phase transition analysis, but also describes when phase transition analysis is reliable, and presents a more accurate comparison among different regularizers.