Sparse linear regression is a fundamental task in high-dimensional statistics, where the goal is to recover a $k$-sparse signal $w^* \in \mathbb{R}^n$ from observations $y = Xw^* + \xi$. While information theory suggests that $O(k \log n)$ samples should suffice, standard algorithms like the Lasso typically require the design matrix $X$ to be well-conditioned, satisfying properties such as the Restricted Isometry Property (RIP).
In many real-world applications, such as time-series analysis or random walks, variables are highly correlated. This ill-conditioning causes standard Lasso to fail even when the sample size is significantly larger than the sparsity level. This paper investigates whether "preconditioning"—a change of basis—can bridge the gap between algorithmic performance and information-theoretic limits.
The Preconditioning Framework
The authors focus on Right Preconditioning, which transforms the variables to "whiten" the data before applying the Lasso. The objective becomes:
$$\text{argmin}_w \|y - Xw\|_2^2 + \lambda \|S^T w\|_1$$
where $S$ is the preconditioning matrix. The challenge lies in finding an $S$ that improves the conditioning of $X$ without destroying the sparsity of $w^*$.
Treewidth as a Fundamental Complexity Metric
The core contribution of this work is identifying treewidth as the dial that governs the success of preconditioned Lasso.
The Upper Bound: Graphical Cholesky
For covariates drawn from a Gaussian Markov Random Field (GMRF), the authors propose an algorithm called GraphicalCholesky. By leveraging a tree decomposition of the dependency graph, they construct a "sparsity-preserving" preconditioner inspired by generalized wavelets. For a graph with treewidth $t$, this method recovers the signal with $O(kt \log^3 n)$ samples.
The Lower Bound: High Treewidth Hardness
To prove that preconditioning is not a universal fix, the authors use the Grid Minor Theorem to construct "hard" instances. They show that if the dependency graph has high treewidth, any preconditioner that successfully whitens the data will necessarily "smear" the sparse signal, making it dense in the transformed basis and thus unrecoverable by $\ell_1$ methods.
Empirical Validation
The theoretical results are supported by experiments on synthetic designs, most notably random walks. In these settings, standard approaches fail to exploit the underlying structure efficiently.
Figure 1: Recovery error vs. sample size $m$ for different Basis Pursuit (BP) variants on a random walk design. Preconditioned BP achieves exact recovery with significantly fewer samples than standard or standardized BP.
As illustrated in the figure, "Standardized BP" (which scales variables to unit variance) requires nearly $n$ samples to succeed. In contrast, the proposed preconditioned approach achieves recovery at a much lower sample complexity, aligning with the near-optimal $O(\log^3 n)$ theoretical prediction for this structure.
Key Insights and Conclusion
Right vs. Left Preconditioning: The paper clarifies that while "Left" preconditioning (weighting samples) is common, only "Right" preconditioning (changing the basis of parameters) can fundamentally improve the sample complexity of sparse recovery in noiseless settings.
Algorithmic Limits: The work establishes a definitive link between the graph-theoretic property of treewidth and the statistical limits of convex sparse recovery methods.
By providing both a near-optimal algorithm for low-treewidth designs and a robust lower bound for high-treewidth cases, this research offers a comprehensive understanding of when and why preconditioning can save the Lasso.
Summary updated
Abstract
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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N(0,\ \Sigma)$</tex> , for some <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n\times n$</tex> positive semi-definite matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma$</tex> , and seek estimators <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\hat{w}$</tex> minimizing <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\hat{w}-w^{\ast})^{T}\Sigma(\hat{w}-w^{\ast})$</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$w^{\ast}$</tex> is the k-sparse ground truth. Information theoretically, one can achieve strong error bounds with only <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(k\log n)$</tex> samples for arbitrary <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$w^{\ast}$</tex> ; however, no efficient algorithms are known to match these guarantees even with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$o(n)$</tex> samples, without further assumptions on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma$</tex> or <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$w^{\ast}$</tex> . 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma$</tex> ) 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Sigma$</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(t^{1/20})$</tex> samples to recover <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log n)$</tex> -sparse signals when covariates are drawn from this model.
BibTeX
@inproceedings{kelner2021power,
author = {Jonathan A. Kelner and Frederic Koehler and Raghu Meka and Dhruv Rohatgi},
title = {{On the Power of Preconditioning in Sparse Linear Regression}},
booktitle = {FOCS},
year = {2021},
url = {https://openreview.net/forum?id=wQ8JdjQPp0D},
}