Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv RohatgiNeurIPS 2022 · OpenReview

Introduction

In high-dimensional statistics, Sparse Linear Regression (SLR) is a fundamental problem: recovering a $k$-sparse signal $w^*$ from $m$ samples of the form $y_i = \langle X_i, w^* \rangle$. While information theory dictates that $O(k \log n)$ samples are sufficient to recover the signal, standard polynomial-time algorithms like the Lasso only succeed when the data's covariance matrix ($\Sigma$) is "well-conditioned"—meaning its features are not overly correlated.

When $\Sigma$ is ill-conditioned, Lasso frequently fails. A popular strategy to mitigate this is the Preconditioned Lasso, which applies a change-of-basis (a "preconditioner" $S$) to the data before running the optimization. Previous research has shown that for any fixed preconditioner, there is always a "bad" signal that causes failure. However, in many areas of computer science, randomization acts as a powerful tool to bypass worst-case scenarios. This paper asks a critical question: Can randomized preconditioning bridge the statistical/computational gap and make SLR efficient for any ill-conditioned covariance matrix?

The authors provide a definitive, negative answer, establishing a fundamental limit on the power of preconditioning for sparse linear regression.

Methodology: Constructing the Hard Instance

To prove that randomized preconditioning cannot save the Lasso, the authors construct a specific, mathematically rigorous "hard instance." Their approach relies on two main components:

1. Hard Covariance Construction

They define a highly specific covariance matrix $\Sigma = (M^T M + \epsilon I)^{-1}$, where $M$ is a carefully chosen sparse measurement matrix. This structure guarantees that the data is extremely ill-conditioned in specific "sparse" directions, effectively hiding the signal from standard $\ell_1$-minimization techniques.

2. Erasure-Robust Sparse Designs

To finalize their lower bound, the authors develop a novel result in compressed sensing. They analyze the behavior of a sparse Bernoulli matrix when an adversary "erases" a small number of measurements. Surprisingly, they prove that these matrices are remarkably robust: if $b$ measurements are erased, all but $O(b)$ coordinates of the signal remain identifiable. This robustness is the trap that prevents any preconditioner from successfully correcting the ill-conditioning without destroying the sparsity of the signal.

Key Insights and Results

The paper yields several major theoretical breakthroughs regarding the geometry of sparse recovery:

  • Randomization is Not a Silver Bullet: In numerical linear algebra, random projections (like Johnson-Lindenstrauss transforms) often simplify problems. Here, the authors demonstrate that for SLR, the geometry of ill-conditioned sparse recovery is too "rigid." Randomization cannot hide the hard directions from the Lasso's objective function.
  • The Main Lower Bound (Theorem 2.1): For any invertible randomized preconditioner $S$, there exists a signal distribution where $S$-preconditioned Lasso fails with high probability ($1 - o(1)$) unless it receives a linear number of samples ($\Omega(n)$). This holds even though the target signal is only polylogarithmically sparse.
  • Extension to Rectangular Preconditioners (Theorem 2.2): The failure of preconditioning is not limited to invertible matrices. The result extends to rectangular (non-invertible) preconditioners, ruling out a much broader class of "sketching" or dimension-reduction approaches.
  • Density Amplification: The proof hinges on showing that if a vector is in the kernel of a "good" part of the measurement matrix, that vector must be very dense. This forces the preconditioner into a catch-22: it must either become very dense itself (destroying the signal's sparsity, which Lasso relies on) or fail to correct the covariance.

Limitations and Future Work

While this paper provides a near-complete negative answer for preconditioned Lasso, it leaves exciting avenues for future research:

  • Scope of Algorithms: The lower bound specifically targets the Preconditioned Lasso family. While this is the most common approach for SLR, it does not strictly rule out all possible polynomial-time algorithms (e.g., those utilizing sum-of-squares hierarchies or methods not based on $\ell_1$ minimization).
  • Computational Open Questions: The authors proved that partial recovery is information-theoretically possible under adversarial erasures in sparse Bernoulli systems. However, finding a computationally efficient algorithm to achieve this partial recovery remains an open problem.
  • A New Benchmark: The "hard instances" constructed in this paper serve as a rigorous new benchmark. Researchers developing next-generation SLR algorithms that aim to go beyond simple preconditioning must now test their methods against these specific covariance structures.

Summary updated

Abstract

Sparse linear regression with ill-conditioned Gaussian random covariates is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidence for this belief. Recent work has shown that, for certain covariance matrices, the broad class of Preconditioned Lasso programs provably cannot succeed on polylogarithmically sparse signals with a sublinear number of samples. However, this lower bound only holds against deterministic preconditioners, and in many contexts randomization is crucial to the success of preconditioners. We prove a stronger lower bound that rules out randomized preconditioners. For an appropriate covariance matrix, we construct a single signal distribution on which any invertibly-preconditioned Lasso program fails with high probability, unless it receives a linear number of samples. Surprisingly, at the heart of our lower bound is a new robustness result in compressed sensing. In particular, we study recovering a sparse signal when a few measurements can be erased adversarially. To our knowledge, this natural question has not been studied before for sparse measurements. We surprisingly show that standard sparse Bernoulli measurements are almost-optimally robust to adversarial erasures: if $b$ measurements are erased, then all but $O(b)$ of the coordinates of the signal are identifiable.
BibTeX
@inproceedings{kelner2022lower,
  author = {Jonathan A. Kelner and Frederic Koehler and Raghu Meka and Dhruv Rohatgi},
  title = {{Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=4UMKEweGRi},
}
Figure