On the Power of Preconditioning in Sparse Linear Regression

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.