On the Power of Preconditioning in Sparse Linear Regression
On the Power of Preconditioning in Sparse Linear Regression
复制标题
DOI：
10.1109/focs52979.2021.00061
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Jonathan A. Kelner;Frederic Koehler;Raghu Meka;Dhruv Rohatgi
中科院分区：
文献类型：
--
作者：
Jonathan A. Kelner;Frederic Koehler;Raghu Meka;Dhruv Rohatgi
稀疏的线性回归是高维统计的一个基本问题，但是对于如何在设计矩阵上有效解决的情况下，知之甚少。多变量高斯$ n（0，\ \ sigma）$，对于某些$ n \ times n $ n $阳性半明确矩阵$ \ sigma $，并寻求估算器$ \ hat {w} $最小化$（\ hat {w hat {w} - w^{\ ast}）^{t} \ sigma（\ hat {w} -w^{\ ast}）$，其中$ w^{\ ast} $是k-sparse地面真相只能使用$ O（K \ log n）$ hex $ \ sigma $和$ w^{\ ast} $实现强错误范围，但是，即使使用$ O（N） ）$样本，在$ \ sigma $或$ w^{\ ast} $上没有进一步的假设日期，随机设计实例（即特定的协方差材料$ \ sigma $）仅证明了与Lasso计划和变体相对的，这些“硬”实例经常在简单的BASIS变更之后就可以解决。 （即预处理）。回归问题几乎是最佳的：每当协变量的依赖性结构在马尔可夫属性的意义上，即使$ \ sigma $是高度不良的条件，也可以从小波和信号构建，即处理文献。第一次）随机设计实例，即使对于最佳预处理的套索也可能很难预处理的拉索（Profiented Lasso）有任何选择的预处理，都需要$ \ omega（t^{1/20}）$样本才能恢复$ O（\ log n）$ -SPARSE信号，当时从此模型中汲取协变量时。
Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on the design matrix. We consider the (correlated) random design setting, where the covariates are independently drawn from a multivariate Gaussian $N(0,\ \Sigma)$, for some $n\times n$ positive semi-definite matrix $\Sigma$, and seek estimators $\hat{w}$ minimizing $(\hat{w}-w^{\ast})^{T}\Sigma(\hat{w}-w^{\ast})$, where $w^{\ast}$ is the k-sparse ground truth. Information theoretically, one can achieve strong error bounds with only $O(k\log n)$ samples for arbitrary $\Sigma$ and $w^{\ast}$; however, no efficient algorithms are known to match these guarantees even with $o(n)$ samples, without further assumptions on $\Sigma$ or $w^{\ast}$. Yet there is little evidence for this gap in the random design setting: computational lower bounds are only known for worst-case design matrices. To date, random-design instances (i.e. specific covariance matrices $\Sigma$) have only been proven hard against the Lasso program and variants. More precisely, these “hard” instances can often be solved by Lasso after a simple change-of-basis (i.e. preconditioning). In this work, we give both upper and lower bounds clarifying the power of preconditioning as a tool for solving sparse linear regression problems. On the one hand, we show that the preconditioned Lasso can solve a large class of sparse linear regression problems nearly optimally: it succeeds whenever the dependency structure of the covariates, in the sense of the Markov property, has low treewidth - even if $\Sigma$ is highly ill-conditioned. This upper bound builds on ideas from the wavelet and signal processing literature. As a special case of this result, we give an algorithm for sparse linear regression with covariates from an autoregressive time series model, where we also show that the (usual) Lasso provably fails. On the other hand, we construct (for the first time) random-design instances which are provably hard even for an optimally preconditioned Lasso. In fact, we complete our treewidth classification by proving that for any treewidth-t graph, there exists a Gaussian Markov Random Field on this graph such that the preconditioned Lasso, with any choice of preconditioner, requires $\Omega(t^{1/20})$ samples to recover $O(\log n)$ -sparse signals when covariates are drawn from this model.