.png){kind=icon}
返回
SPARSE HIGH-DIMENSIONAL LINEAR REGRESSION. ESTIMATING SQUARED ERROR AND A PHASE TRANSITION
.png){kind=icon}
OA
AI
DOI：10.1214/21-AOS2130.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider a sparse high-dimensional regression model where the goal is to recover a k-sparse unknown binary vector beta* from n noisy linear observations of the form Y = X beta* + W is an element of R-n where X is an element of R-n has i.i.d. N(0, 1) entries and W is an element of R-n has i.i.d. N(0, sigma(2)) entries. In the high signal-to-noise ratio regime and sublinear sparsity regime, while the order of the sample size needed to recover the unknown vector information-theoretically is known to be n* := 2k log p/log (k/sigma(2) + 1), no polynomial-time algorithm is known to succeed unless n > n(alg) := (2k + sigma(2)) log p. In this work, we offer a series of results investigating multiple computational and statistical aspects of the recovery task in the regime n is an element of [n *, n(alg)]. First, we establish a novel information-theoretic property of the MLE of the problem happening around n = n* samples, which we coin as an all-ornothing behavior: when n > n* it recovers almost perfectly the support of beta*, while if n < n* it fails to recover any fraction of it correctly. Second, at an attempt to understand the computational hardness in the regime n is an element of r we prove that at order n(al)g samples there is an Overlap Gap is an element of [n*, n(alg)], Property (OGP) phase transition occurring at the landscape of the MLE: for constants c, C > 0 when n < cn(alg) OGP appears in the landscape of MLE while if n > Cn(alg) OGP disappears. OGP is a geometric disconnectivity property, which initially appeared in the theory of spin glasses and is known to suggest algorithmic hardness when it occurs. Finally, using certain technical results obtained to establish the OGP phase transition, we additionally establish various novel positive and negative algorithmic results for the recovery task of interest, including the failure of LASSO with access to n < cn(alg) samples and the success of a simple local search method with access to n > Cn(alg) samples.
Keyword:
High-dimensional linear regression
sparsity
overlap gap property
all-or-nothing phenomenon
second moment method
期刊
IF:
3.7
论文数:
2.8K
被引数:
2.9W
机构
暂无机构信息
引用论文
The role of endobronchial ultrasound elastography in the diagnosis of mediastinal and hilar lymph nodes.png)
Oncotarget
OAAI
OncotargetIF0
OAAI分享收藏分享收藏
查看更多内容