Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
This work addresses the statistical/computational gap in sparse linear regression for researchers in theoretical machine learning and compressed sensing, providing formal evidence against Preconditioned Lasso and introducing a novel erasure-robustness property.
The paper tackles the problem of sparse linear regression with ill-conditioned Gaussian designs by proving a stronger lower bound against Preconditioned Lasso, showing that any invertibly-preconditioned Lasso fails with high probability on a specific signal distribution unless given a linear number of samples. The result is based on a new positive finding that standard sparse random designs are robust to adversarial measurement erasures, enabling identification of all but O(b) coordinates after b erasures.
Sparse linear regression with ill-conditioned Gaussian random designs is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidence for this belief, even in the form of examples that are hard for restricted classes of algorithms. 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 shows that for every preconditioner, there exists at least one signal that it fails to recover successfully. This leaves open the possibility that, for example, trying multiple different preconditioners solves every sparse linear regression problem. In this work, we prove a stronger lower bound that overcomes this issue. 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 positive result in compressed sensing. We show that standard sparse random designs are with high probability robust to adversarial measurement erasures, in the sense that if $b$ measurements are erased, then all but $O(b)$ of the coordinates of the signal are still information-theoretically identifiable. To our knowledge, this is the first time that partial recoverability of arbitrary sparse signals under erasures has been studied in compressed sensing.