Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs
Authors: Jonathan Kelner
Frederic Koehler
Raghu Meka
Dhruv Rohatgi
Venue: NeurIPS 2022 Accept (2022)
Keywords: sparse linear regression
statistical/computational gaps
compressed sensing with adversarial erasure
preconditioning

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.

Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs
Jonathan A. Kelner" MIT
Frederic Koehler Stanford
Raghu Meka UCLA
Dhruv Rohatgi MIT
Abstract
Sparse linear regression with ill-conditioned Gaussian random covariates is widely believed to exhibit a statisticalccompuuaaiionn 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 suc- ceed on nolylogarithmicalyy sparse signals with 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, construct single signal distribution which any
Lasso program fails with high probability, unless it receives a linear number of samples. Surprisingly, the heart of our lower bound is a new robustness result in compressed sensing. particular, we study recov- ering sparse signal when few measurements can be erased adversarially. To our knowledge, this natural question has not been studied before for sparse mea- surements. We surprisingly show that standard sparse Bernoulli measurements are almost-optimally robust to adversarial erasures: if measurements are erased, then all but (b) of the coordinates of the signal are identifiable.
1 Introduction
Random-design sparse linear regression (SLR) is fundamental problem high-dimensional statis- ties and learning theory. The simplest formulation of this problem is the following: given indepen- dent covariates XI....,X0 drawn from an n- n-variable Gaussian distribution with zero mean and positive-definite covariance Σ, and responses y4 (X4, w*) for some unknown k-sparse signal w" (i.e. with at most & nonzero entries), the goal is to recover w". While there are more complex mod- els (e.g. with noise non- non-Gaussian distributions), we are proving lower bounds, the simplified model only makes our results stronger.
information-thenn theoretically, for any positive-definite covariance Σ, it's possible to recover w" exactly from only ( log v)) samples (x), (Again, this is special case of more general results for the noisy setting.) However, the algorithm which achieves this sample complexity is computation- ally inefficient - has time complexity O(n²). Significant effort has gone into polynomial-ice
'kelneremit. edu. This work was supported in part by NSF Large CCF-1565235, NSF Medium CCF- 1955217, and NSF TRIPODS 1740751.
T edu. This work supported in part by NSF CAREER Award CCF-1453266 NSF Large CCF-1565235, A. Moitra's ONR Young Investigator Award. and E. Mossel's Vannevar Bush Faculty Fellowship ONR-N00014-20. --226.
'raghumêcs. ucla. This work was supported in part by NSF CAREER Award ICF-1553605 and
NSF Small CCF-2007682.
drohattgi @mit. edu. This work was supported in part by an Akamai Presidential Fellowship and U.S.
DoD NDSEG Fellowship.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

sample-efficient algorithms for sparse linear regression, under as weak conditions on the covariates as possible [22, 16, 44. 15, 13, 21, 20, 14, 18, 12, 45, 53, 48, 38, 47, 11, 46]. Essentially all of these algorithms are variations on one of two fundamental methods: 61 regularization (most notably, the Lasso program [44]), and greedy variable selection (most notably, Orthogonal Matching Pursuit [45]. Moreover, both of these methods seem to hit the same fundamental barrier: they require that > is in some sense well-conditioned. The most basic assumption enabling efficient algorithms is a bound on the condition number Xmax (En//min Amin(2),,
and this assumption has been weakened (to e.g. the Restricted Isometry Property [15], the Compatibility Condition [48], or Weak Submodularity [18]) but not eliminated. This barrier, and the lack of algorithmic techniques which evade it, suggests that sparse linear regression with general positive-definite Σ may exhibit a computationaalstatiiiiicc gap: that is, sumple-effcienn signal recovery may be computationally hard.
Preconditioned Lasso. Recent work [32] provided the first computationally--ffiiiii and sample- efficient algorithm for a broad class of ill-conditioned covariance matrices Σ (specifically, covari- ance matrices of Gaussian Graphical Models with low treewidth such as Gaussian time-series data). The algorithm was a generalization of Lasso via an initial preconditioning step; while precondition- ing has been enormously impactful for efficiently solving linear systems [39], it has only recently been applied to sparse linear regression. The algorithmic results of [32] raise an obvious question: can preconditioning close the statistical/computtiion gap for ill-conditioned sparse linear regres- sion? Or is the gap inherent?
The answer is unclear. The basic obstacle is that no "candidate" hard instances of random-design sparse linear regression are known: nearly all examples which Lasso provably fails can be trivially fixed by preconditioning [53, 23, 17, 46, 31j. The exception is the lower bound in [32], which provides limited negative answer the first question: there is a covariance matrix Σ such that any deterministic preconditioner fails (see Section 1.1 for a concrete statement). They showed that for each preconditioner, there exists specific bad signal on which it fails, where the signal chosen depends heavily on the preconditioner.
This suggests the tantalizing possibility that any ill-conditioned SLR problem can be solved by applying randomized preconditioning. This way, the signal can no longer be chosen adversarially based on the preconditioner. Indeed, numerical linear algebra is full of situations where randomized maps are useful precisely for this reason, including the JL embedding and other dimension reduction methods, algorithms based on random metric embeddings, and the famous Nystrom method for low rank approximation and preconditioning (see e.g. [56, 51, 42]). Also, it was observed in [31, 32] that randomized preconditioners (or, roughly equivalently, trying a class of preconditioners) can be used to solve SLR problems in various cases where we do not currently know of a fixed deterministic preconditioner that works. Given this context, we need to ask the following question: can randomized preconditioning close the statisticalccomputatioaaal gap?
Our result. We give a near-complete negative answer to this revised question: for a carefully- Lasso program
chosen Σ and distribution over the unknown signal w", any with invertible preconditioners fails (see Section for a more concrete statement).
Broader context statisticalcompptaatinnall gaps. Random-design sparse linear regression is very interesting among high-dimensional statistics problems, in that there is essentially no evi- dence for its conjectured statistical/computttii not drawn from a distribution) has been proven computationally hard under standard worst-case sapplexitt--hhoreetii assumptions [37, 57, 30, 28], such hardness is known for random-design SLR.5 5 In contrast, problems as diverse as sparse PCA [7]. average-case RIP certification [55], planted dense subgraph [10], robust sparse mean estimation [8]. and negative-spike sparse PCA [8] have provably statistica//compuaationn gaps under (variants of) the Planted Clique conjecture.
gap; while SLR with worst-case covariates (i.e.
Why isn't sparse linear regression on this list? One possibility is that there is no statisti- cal/computational gap; in this case, our results imply that new algorithmic techniques beyond pre- conditioning are needed, and our hard instances provide natural testing ground for new techniques.
is not invertible the task would be learning the concept/regression function, iec outputting any w so that (w - "I w) = 0. If required to output a k-sparse predictor and Σ is not invertible, the problem is NP hard with infinitely many samples [29] as it's equivalent to finding a sparse solution of linear equations.
'This is when
invertible.

---

But another potential explanation is the current dearth of conjecturally- instances of random- design sparse linear regression. Reductions from Planted Clique (and other techniques for proving average-case lower bounds) either explicitly or implicitly involve constructing distributions over the unknown concept class which encapsulate (to some degree) the hardness of the original problem. For instance, sparse PCA is conjecturally hard even when the planted sparse direction is drawn uniformly at random from k-sparse vectors with nonzero entries +1/ // [36. 9]. Similarly, non-reduction based lower bounds like Statistical Query lower bounds are typically derived against the uniform distribution over a finite set of concepts [27]. Thus, it is problematic that for sparse linear regression, no such distribution has even been hypothesized: i.c., a family (En, Dn)neN where Σn describes an covariance matrix, and D,, describes distribution over (sn)-sparse n-dimensional sig- nals, specifying a model which seems to encapsulate some of the difficulty of handom-desige SLR. While it would certainly be necessary that the covariance matrices E,, are ill-conditioned, there also natural families of ill-conditioned covariate distributions which lead to tractable instances (e.g. [32, 31), so such property is by no means sufficient.
Our main result provides a family of covariance matrices and signal distributions which is hard at least for all preconditioned Lasso algorithms (this was not accomplished by [32], because they constructed a different signal for each preconditioner). Thus, our work can be viewed as necessary first step towards average-case computational hardness of ill-conditioned sparse lincar regression.
1.1 The Preconditioned Lasso
Perhaps the canonical method solve sparse linear regression problems is by solving convex program known as the Lasso [44]. In our noiseless setting, it reduces to the basis pursuit program
argmin
||w||
wER":X10=y
This program is well-studied, and it's known to succeed with high probability with O log n) sam- ples when Σ is well-conditioned [54], but it also is known to fail if Σ is ill-conditioned [23, 17, 31]. In the context of ill-conditioned SLR, the class of programs known as the Preconditioned Lasso [32] is significantly more powerful. Informally, these algorithms apply some change-of-basis to "condition" the covariates before solving the basis pursuit program. Formally:
Definition 1. For an invertible n x n matrix (which we think of as an arbitrary function of Σ that however cannot depend on the samples), the S-preconditioned Lasso on data (X;, y4) applies the transformation X; + S-1 solves the basis pursuit to get an estimate i and returns w := S This corresponds to solving the convex program
à E argmin ||STROl)
(1)
wER":Xu=y xumy
Preconditioned Lasso obviously generalizes the Lasso, and it works for SLR tasks where applying the Lasso directly will fail badly. For example, whenever the covariates come from autoregressive time series data (c.g. random walk or AR(1)) the sparse linear regression problem can be solved nearly optimally via Preconditioned Lasso, even though the covariates are likely to be heavily cor- related. More generally, any covariance matrix with low-treewidth dependency structure induces an SLR model that tractable via Preconditioned Lasso, even if the matrix is arbitrarily ill-conditioned [32]. Due this generality, examples that are provably hard against the Preconditioned Lasso are much more difficult to obtain, and much more interesting. Concretely, prior to the present work, the only known hardness result against the Preconditioned Lasso was the following statement:"
Theorem 1.1 (Informal theorem statement from [32]). For any > O, there is a positive-definite covariance matrix Σ : n X n such that any preconditioner S, there exists some polylog(n) (agllognn-spprsss -sparse signal w' which S S-preconditioned Lasso with probability 1 - o(1) fails to recover, when given o(n) independent samples X, ~ (0, Σ) and yi (X,, w.).
'Relatedly, for realizable regression problems there is general computationally inefficient algorithm which makes a smaller number of SQ queries [49].
"To he more precise, Theorem 1.1 and the definition of Preconditioned Lasso actually apply all rectan- gular n x preconditioners. not just invertible preconditioners (note that Program is still defined, though no longer corresponds to a change-of- -o-ange.f-basss).. However, most algorithms applying Preconditioned Lasso in the literature use invertible preconditioners [31, 32). Moreover, restricting to invertible preconditioners does not improve the failure probability achievable by the techniques in [32].
3

---

This provides a converse to the algorithmic results of [32], which show that for certain covariance matrices, there is a preconditioner that works for all signals. However, the limitation of Theorem 1.1 is that the hard signal depends on the preconditioner: unpacking the proof of Theorem 1.1 only gives a signal distribution on which any preconditioner fails with probability 92(1 (21//)). Thus, the lower bound is extremely weak if we allow for randomization in the choice of preconditioner, which is how preconditioners are often applied in other contexts.
2
Main Results
In this paper, we eliminate that limitation and provide single signal distribution which is provably impossible to precondition. That is, we construct a covariance matrix and a sparse signal distribution under which Preconditioned Lasso with any invertible, randomized change-of af-bbaiis must fail with high probability, unless a linear number of samples are given.
Theorem 2.1 (Theorem E.3 of the Appendix). Let ni > O. There is a positive-defiitte covariance matrix Σ n. x and a distribution D over polylog(n)-sparse signals with the following property: for any invertible randomized preconditioner S. if we draw w² DD then S-preconditioned Lasso fails to recover w" with probability least 1 (1), when given onn) independent samples X₃ N (0, Σ) and y; = (X,, w*).
In fact, the full version of Theorem E.3 is even stronger: it shows that even if we fix family of poly(n) different preconditioners, they will all fail on a problem instance sampled from our distri- bution with probability 1 o(1). This allows us rule out even larger class of algorithms: for example, the algorithm used in [31] for solving jointly walk-summable SLR instances adaptively se- lects one of possible (invertible) preconditioners before running the Preconditioned Lasso, and our lower bound shows that this strategy and variants are provably defeated by our new construction.
Additionally, we can extend our result to show hardness against rectangular n X s preconditioners. For technical reasons we only achieve a failure probability of 1/2 - o(1), and require bound on the preconditioner size. Nonetheless, at this failure probability and with poly-logarithmically sparse signals, we can rule out all polynomially sized preconditioners.
Theorem 2.2 (Theorem 1. of the Appendix). Let n > O. There is a positive-defiitte covariance matrix E n n and a distribution D over k-sparse signals. for any 2 log'²(n), (n). with the following property: for any randomized preconditioner with at most cxp(k/ / log log (n)) columns, if we draw w" ~ 'D. then S-preconditioned Lasso fails to recover w with probability at least 1/2 - o(1), when
given o(n) independent samples X, [ Σ) and y: = (X,, w*).
In both theorems, the probability is over the choice of preconditioner, the signal distribution, and the random samples. Surprisingly, the key technique used to prove Theorem 2.1 and 2.2 is a poxitive identifiability result in compressed sensing. We show that random sparse compressive design matri- ces are robust to adversarial erasures. To prove our lower bounds, we will fix one such matrix M, and we will define the covariance matrix Σ (M M + +e)- for small M will then imply important properties of Σ. Note that the final Gaussian SLR design matrix (with independent rows drawn from NO, Σ)) will be quite different from the erasure- rrobust design matrix M. But first, we describe the application of such matrices M to compressed sensing, as we believe it is of independent interest and main contribution of this work.
O; the robustness of
2.1 Key Technique: Erasure-Robus. Sparse Designs
In this section we describe the key technique that enables our main results, an crasure-robust sparse design, and provide an independent motivation for this design from compressed sensing. At the end, we provide intuition for how it connects back to hardness against Preconditioned Lasso.
There is a vast literature on sparse linear regression and compressed sensing. Many determinis- tic conditions and stochastic models for the measurement matrix (also known as design matrix or covariate matrix) have been demonstrated to imply that sparse signals can be recovered either thoomaaion-hheoretically or algorithnically [54]. In noisy settings, the goal is usually either ap- proximate recovery under an é, norm prediction error (e.g. [14, 53]); exact support recovery with some assumptions about the signal-to-noiss ratio (e.g. [53]): or approximate support recovery under distributional assumptions about the signal (e.g. [40]). However, in noiseless settings, the goal is

---

invariably exact recovery. This is obviously ideal. But in situations where the measurements are not entirely controlled by the algorithm designer, exact recovery could be impossible. A natural goal is then to try to recover part of the signal. To our knowledge, this notion of partial recovery of sparse signals (i.e. due shortcomings of the measurement matrix rather than due noise) has received essentially no attention; see Section 3 for a discussion of related notions.
Part of the reason may be that it's not obvious what models for compressive measurement matrix exhibit the behavior that some but not all of the coordinates of a sparse signal are identifiable, besides artificial examples where e.g. unconstrained variables are added the system. Such examples do not answer the question of whether partial recovery is possible under fundamentally weaker modelling assumptions than total recovery.
Grasure-robustness Our key technical contribution is a proof that partial recovery is possible in a natural semi-randon model. Specifically, we show that random sparse compressive measurement matrices M are "erasure-robust" by which we mean that if an adversary erases small fraction of the measurements (M,, x;),, replacing them with question-marks then most of the coordinates of the sparse signal vector x" are still infornation-theorriicall identifiable. Moreover, the identifiability result stable under additive measurement noise with polynomially small norm.
Adversarial crasures have been studied in compressing sensing before, and of course have also been long and extensively studied in coding theory (see e.g. [35. 33, 24]). For random dense compressive matrices, it's known that deleting small fraction of the mcasurements essentially does nothing; the sparse signal is still totally recoverable with high probability [19, 52, 34]. But for random sparse matrices (which in the absence of erasures do also enable total sparse recovery [5]), no such robustness has been proven, because it's not true: the adversary may simply delete all measurements interacting with a particular coordinate, rendering that coordinate unidentifiable. Given this, partial recovery is the best that can hoped for. Our result implies that is also attainable, at least cntrmaationnthoortiiillll
Moreover, we achieve nearly-tight bound on the number of unidentifiable coordinates. Here is the informal statement:
Theorem 2.3 (Theorem C.14 of the Appendix). Let n. m > satisfy > m > +(log n). and
let M be an m n matrix with independent Bernoulli-p entries for p O(log" n)/m. With
high probability, the following holds. For any set of "deleted" equations B C [ml of size |B] s
O(m/ polylog(n)), there is a set C (the "unidentifiable coordinates" ") of size |C| s 2 such that
| l12 S poly(n). ||
for any O(m/ (appllo(())ssparsee vector x E IR..
To make apparent the implication for compressed sensing, we state the following corollary:
Corollary 2.4. Let M E {0, 1]mxx be a fixed, known matrix for which the guarantee of Theo- rem 2.3 holds. Let x² E R be an unknown k-sparse vector with k S O(m/ polylog(n)). Define measurements y = Mxx + +n for some noise vector n with || S 8, but suppose that y undergoes adversarial erasures. That is, we only observe R where
? 94
iiiE B
U
for an addversarially-choseee set B S [m]. Then we can information- identify an estimate t IR" and a region of uncertainty C. C. [n] such that (.. æz| I 5 poly(n) for all C. Moreover, the region of uncertainty is a function of B (nol depending on x or y) and is bounded as |C| < 2/B).
In particular, the estimator is simply å = arggming:l M:le <6 ||=|| The region of uncertainty C' is any set C' satisfying the guarantee of Theorem 2.3 with respect to B; it can be (inefficiently) computed from via brute-force computation of singular values of submatrices of M. Then, since à - x² is 2k sparse, the guarantee of Theorem 2.3 gives that
I|( - x² )c o1.0 S poly(n) ||M - -x*) Il
poly(n) [[ ( -n-) ) + (Un= MB 1lox S poll((n) 8
as claimed in the corollary.
5

---

Sparsity of the measurement matrix (and not just the signal) is well-studied in compressed sensing and has various practical applications. For example, in scientific experiments it is often the case that linearity of the response with respect to the covariates is a modelling assumption that's only reasonable for a sparse covariate vector [26]. Our result implies that even with a sparse measurement matrix, adversarial erasures (due to e-g. experimental error) are not disastrous. (Note that in the above theorem, each row of the measurement matrix is roughly (n log" nt/mm sparse, which up to logarithmic factors cannot be improved, even without erasures, since the measurement matrix must have (n)) nonzero entries).
Open question. Our results show that partial sparse recovery in this semi-random model is possible. However, finding a computationally efficient algorithm is an interesting open problem.
Connection to lower bounds against Preconditioned Lasso. It may seem rather mysterious that construction of an erasure-robust, "good" design matrix is the key ingredient in a distributional hard example for family of sparse recovery algorithms. The technical reasons for this connection are deferred to the overview, but here we try to give some high-level intuition. First, for intuition, we restrict our focus to sparse preconditioners, because dense preconditioners (morally) do not preserve the sparsity of the unknown signal and therefore should not work. Now, if I is very ill-conditioned, the preconditioner essentially needs to "fix" Σ by reweighting the different eigenspaces.
If we are allowed to construct the signal based on the preconditioner, then the preconditioner is forced to be a good approximation for Σ everywhere, with no bad directions. But from any good measurement matrix, using the fact that it has dense kernel, we can construct a Σ so that no sparse preconditioner can approximate Σ everywhere. This is the approach taken in [32] for Theorem 1.1.
In our case, we need to construct the signal distribution without knowing the preconditioner, so the preconditioner is only forced to be good approximation for E in most directions. Ruling out sparse preconditioners then corresponds to a mcasurement matrix which has a density property even if some of the rows are ignored (specifically, erasure-robustness). Sparsity of the measurement matrix is needed so that the rows are valid sparse signals, and compressivity is needed so that Σ is ill-conditioned in many directions.
3 Related Work
Hard Examples for SLR. As we mentioned earlier, SLR with worst-case covariates is known to be computationally hard under worst-case complexity-theone
assumptions [37, 57, 30, 28]. However, for the candom-desige covariate model, there is no known Idtuctioo-basser hardness, even under average-case or cryptographic assumptions. We enumerate known restricted hardness results:
First, there is a large literature on when the Lasso and Basis Pursuit programs fail at sparse recovery, even for random designs [53, 23, 17, 46, 31]. While these results do (technically speaking) prove lower bounds against classes of algorithms, these classes are quite small: the constructed examples are only proven to be hard for the Lasso and/or Basis Pursuit (at best, these programs have one meta- parameter). In fact, as has been previously observed [58, 32], all of the "hard" examples provided in the above works can be fixed by simple change-of thange-of-basis.. basis.
Second, there a more general lower bound against the class of convex programs solving least- squares regression with coordinate-separabe regularizers [58]. While this is a fairly broad class of algorithms (incomparable with the Preconditioned Lasso), the result has two limitations. One is that the constructed hard signals depend the regularizer, so there no single signal distribution that is hard for the entire class. The other limitation is that, like in the previous works on hardness against the Lasso, the hard example in [58] can be made easy for the Lasso by simple change-of-basis.
Third, in [32], motivated by the latter limitation, covariance matrices are constructed such that for any thange-of-basic there is sparse signal (in the original basis) which causes the "preconditioned" basis pursuit program to fail. However, as we have previously noted, this result is still limited by the strong dependence of the signal on the preconditioner: it does not even rule out the possibility that there are always two preconditioners so that every signal can be recovered by one of them.
Fourth, for isotropic random-design SLR (i.e. when Σ = /), there has been work on identifying the precise sample complexity of sparse recovery. In particular, there appears to be a constant-facte gap between the sample complexities of algorithmic recovery and information-theoredt recovery.

---

Evidence has been given for this gap via the Overlap Gap Property [25], which implies the failure of a restricted class of "stable" algorithms. However, this problem seems fundamentally different from the problem we consider, where the hardness arises from the ill-conditioning of the covariates, and the sample complexity gap is conjecturally exponential rather than constant.
Partial sparse recovery. There are several other works in compressed sensing that use the ter- minology of "partial" recovery. To our knowledge, these works all consider different settings from ours; we explain the differences. First, in [3], partial sparse recovery refers to totally recovering signal that is only partially sparse (where the signal space is divided into two sets of coordinates, and it's known that the signal is sparse on the first set). Second, in [43], the goal is indeed recover only part of the support of the signal. However, their model is the Gaussian Sequence Model (i.e. where the measurement matrix is the identity), where it is obvious that partial recovery is possible, because there is no compression. Third, as discussed previously, one common goal in noisy models is partial support recovery (see e.g. [40]). There, the goal is estimate the support with few false positives and false negatives, and the reason for error is simply that some coordinates of the signal may be very small and therefore indistinguishable from noise. In contrast, partial identifiability occurs in our setting even without noise, due to weaker model for the measurement matrix. Moreover, proving partial support recovery in the setting of [40] requires make strong probabilistic assumptions about the signal, c.g. that the support is a uniform sparse set. In contrast, our results prove conditions under which a measurement matrix enables partial recovery of arbitrary sparse signals.
4 Technical Overview
We start with sketch of the proof of Theorem 1.1 from [32], which only achieves failure proba- bility of (1//n), and which formally motivates the need for erasure-robust sparse designs. We then sketch the proof of our main technical result that random sparse designs are erasure-robust. Finally, we discuss how this result leads to stronger lower bounds against Preconditioned Lasso.
4.1 Lower Bounds via Sparse Designs.
The hard covariance matrix constructed in [32] to prove Theorem 1.1
is defined as = - where = ② e and θ = .M' M, for a rectangular matrix M. Note that for small e >> 0, this covariance is very ill-conditioned, so long as M has non-trivial kernel. To prove that all Preconditioned Lasso al algorithms with m samples fail to recover k-sparse signals, these three properties are used:
1. The rows of M are k-sparse,
2. dim ker M 2 2m,
3. ker M is bounded away from all (n/k) log(n)-sparse vectors.
The first property is self-explanatory One way to achieve the second property is if M has at most n 2m rows. And the third property, in compressed sensing, is essentially what a design matrix needs to satisfy to informatioo-ttheorrtiaallll theoretically enable (n/K /) log( (s)-prsee recovery. Thus, to show that (n)) samples are needed to recover polylog(n)-spene --parse signals, M must be a sparse, compressive matrix which (as design matrix) enables the recovery of n/ polylog(n)--spamg
signals.
How do these properties imply that for every preconditioner S. there is a bad k-sparse signal? By the first property, the rows of M are valid signals. For each row M,, if it is not a bad signal for S-preconditioned Lasso, then it can be shown to induce a certain constraint on S: namely, that every column of 5 either has small magnitude or is nearly orthogonal to M, So if none of the rows of M; are bad signals, then every column of S either has small magnitude or lies near ker M, in which case by the third property it must be (n/k (n/k)log(n) -denss... Roughly speaking, this structure can be used together with the second property show that k-sparse signal with uniformly random support causes the Preconditioned Lasso to fail.
hard signal distribution? The above proof shows that for any preconditioner, either it fails (with high probability) on random k-sparse signal, or there exists some row of M on which it fails. we want a signal distribution that is uniformly hard, it's therefore natural to equiprobably pick either (a) random row of M, or (b) a random k-sparse signal. But then the above proof only
7

---

implies that for this signal distribution, for any preconditioner, the Preconditioned Lasso fails with probability ((1/n). Moreover, it's not clear whether the failure probability can be improved under just the above assumptions: consider the case that for some preconditioner, just few rows of M are bad signals. Then the likelihood that one of these rows is chosen as the signal is only ((1/m) Moreover, the columns of 5 are now only forced to be orthogonal to most rows of M, not all. As result, the columns may have large magnitude and yet fail to be dense, because for sparse matrices like M, it's possible to adversarially delete few rows so that the kernel of the remaining rows contains sparse vectors. This is an obstacle to proving that such a preconditioner must fail on a sparse signal with uniformly random support.
To circumvent this obstacle, we need to show that preconditioner S which has columns orthogonal to most rows of M, but not all, still has useful structure. As we suggested earlier, this can be done by reasoning about sparse compressive matrices under adversarial deletions.
4.2 Erasure-robustness
We will return to the lower bound problem in the next section of the overview, but for now focus on the core technical result about partial recovery with adversarial erasures. Based the discussion after Theorem 2.3, we need to solve the following problem.
(llgg))mm We want to show that with high probability, M supports erasure-robust partial sparse recovery: that is, for any set B [m] of "bad equations", there is a small set C' S [rx] such that if x E 12" is 7-sparse, then
Let M be an m x sparse random Bernoulli matrix with parameter
| l|2 I poly(n) ||
Erasure-robustnes:: the exact case. For simplicity, in this proof sketch we start by considering the exact case, where M = 0, and we want to show that either supp(>>)] 2 or supp(#) C C. Without erasures (i.e. B 0). this property follows for C = 0 by the fact that the adjacency graph of M is with high probability a unique-neighbor expander. 8 Concretely, because the graph is (1 e)d expander for small constant e > O, any set S S [n] of size at most r == O(m/ log(n)) has at least (1 (e)) )d]{) unique neighbors in [m]. Moreover, if j E [m] is a unique neighbor of supp(z) for some vector e R", then M, & O. Thus, if Mr 0 then supp(z) must have no unique neighbors, so either ssupp(x) 2 T or x = O.
However, this argument breaks down in the presence of adversarial crasures. All that can be said that if MB = then supp(x) must have no unique neighbors in B By the unique neighbor this can be
lower bound, it does follow that either supp(z)| 2 T or supp(rr) I O((Bl/d) thought of as a kind of density amplification result for ker MB,, since it eliminates the possibility of any vector in the kernel having intermediate density. Unfortunately, this does not directly because we need a single set C' that contains the supports of all sparse vectors in ker M, not a different C' for each x. (For example, if we allow C = supp(æ;) then the result is not very interesting.) Moreover, it's not clear that anything useful can be said about the vertex set supp(z): certainly many vertices in supp(z:) must be adjacent to "bad" equations, but it's conceivable that other vertices could be farther away. Pictorially, one possible case (of many) is that B could be chosen the set of "boundary" equations of ball subgraph; then ker MB certainly contains a vector supported on the ball, which is not actually contained in the neighborhood of B.
imply erasure-robustnest
Given the above obstacles, one approach is to show that although supp(z) may not be contained in the neighborhood of B, it must be contained in a distance-r ball around B, for some small but super-constant r. The argument is that if there is vertex of supp(æ) which is distance greater than from B, then by iteratively growing neighborhoods of the vertex until B is reached, the support must have size at least d", and contradiction is reached if d' > B /l,d, because then B cannot contain all unique neighbors of supp(z). Unfortunately, the constructed set C' (the distance-r ball around B) then has size |B]- (dP)" se B since the distance metric is that two coordinates are adjacent if they share an equation. This is much larger than the desired bound (O(B)) )) and in particular, too large to use in ultimate lower bound application.
In summary, to get the linear bound claimed in Theorem 2.3, we need a different argument. The key idea is to exploit linearity. We want to show that the union U of supports of all 7-sparse vectors in
'e note that this initial part of the argument (the case without erasures) is quite reminiscent of arguments used in the analysis of LDPC codes (see e.g. [41]).
8

---

ker MB has small size. We've seen that for any fixed z, there is density amplification result: if x
MB = 0 and x is /dddense,, then z must be r-dense. So take vectors x ,..",,,,,, E ker ge which are 7-sparse (and therefore [B/dd-ppasse and which cover U. Now observe that since x(1)) and xz(2) are /pparre,,,,, any linear combination cyz((t) + (2x!22) must be 2) B) /d-parse But c +c2x(2) E ker MB= by linearity. So if 2 B|/ < r. then by the (contrapositive of the) density amplification result, we in fact know that the sum |BI/d sparse! Inductively, it follows that any linear combination c),(() +... + C,ar(() is BB/ d-spare. But for generic : Cn. we have
supp(cræ()) + + Gral())
= U supp(z!!)) = U.
==1
This shows that in fact we can find a set C of size O(IB)dd) satisfying the desired property.
Erasure robustness: the general case. Note that the above argument was when Mg = 0. The proof for the general case, when Mg.2 is small but not nonzero, uses the same insight with several complications. First, we need a quantitative density amplification lemma which states that if Mg. is small and v has more than B coordinates with magnitude exceeding some threshold 6, then we can trade off density for magnitude, i.e. find coordinates with magnitude exceeding 6/ poly(n)- To prove this without losing a superpolynomial factor on the threshold, we actually need the graph to satisfy stronger property than just expansion: we also need that for any two disjoint sparse sets S,T C [ni], the intersection of their neighborhoods has size only O(v Vd max([S), (T)).. Note that expansion would only give a bound of (ed max( S), [T])). Nonetheless, it can be proven that the random sparse adjacency matrix of M satisfies the desired stronger property with high probability.
Second, the iterative addition procedure in the noiseless case requires a modification for the noisy case; each addition causes the quantitative threshold to decay, and after additions it would decay by factor superpolynomial in Instead, we add the vectors 2(11, ...., (x()) recursively according to a d-ary tree. This tree has depth only log, n, which allows the decay to be controlled to only a poly(n) factor, proving Theorem 2.3.
4.3 Stronger lower bound via erasure-robustness
We now return to the problem of proving hardness against Preconditioned Lasso. Theorem 2.3 can be used to show that for an appropriately chosen M, if the number of rows of M that are bad signals for S-preconditioned Lasso at most n/ polylog(n), then there set C C [n] of size n/ polylog(n) (n) such that each column of S is either n/ polylog(n)-deng
or has small magnitude on coordinates outside the set C. This precisely the structure lemma we need for preconditioners that succeed on most rows of M: it crucially allows for a nearly-linear number of rows of M that are bad signals, although exchange there is set C of sublinear size where we cannot control the columns of S (the corresponding structure lemma in [32] could not tolerate any bad rows). We also show that in this situation, the number of dense columns of must be ((()).
With these results, we can prove our lower bounds. First, to prove our lower bound against invertible preconditioners (Theorem 2.1), we define a distribution over polylog (n) -sparee signals by taking w* to be the sum of polylog(n) random rows of M. plus an infinitesimal uniformly random polylog(n) sparse vector. Under certain conditions, if at least one of the rows in the sum a bad signal, then the sum must also be a bad signal. With this amplification (at the cost of polylog(n) factor in sparsity), any invertible preconditioner must fail with probability bad rows of M, in which case the sum of the chosen rows is bad signal with high probability, and the infinitesimal perturbation does not affect the program failure. Or, S has many dense columns, in which case S "= is dense due to the perturbation. By dimension-counting argument (which crucially uses invertibility of S), this implics that there exists a feasible direction of improvement for the program objective.
(1)): :: either there are Q(n/ polylog(n))
Extending the lower bound to rectangular preconditioners is more involved and involves generaliza- tions of techniques from [32]. The factor of 1/2 in Theorem 2.2 arises because we are not able to construct a single signal distribution that causes failure of both "incompatible" preconditioners (i.e. for which more than 12/ polylog(n) rows of M are bad signals) and "compatible" preconditioners (for which at most n/ polylog(n) rows of M are had signals, so the structure lemma applies) with high probability. Instead, we take mixture of the two cases" hard distributions: either sum of rows

---

of M, or uniformly random sparse vector. Due to the lack of invertibility of the preconditioners, the second case is no longer a simple camension-countigg argument. In [32], the proof crucially relies on "projection lemma" which states that if dim ker M 2 2m, then any fixed direction is unlikely to align with the span of the covariates. Since our structure lemma has no control over the preconditioner columns in the subspace indexed by the set C, we prove generalized projection lemma which states that alignment is unlikely even on C This yields Theorem 2.2.
References
[1] Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2004.
[2] Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A Journal of the IMA, 3(3):224 294, 2014.
[3] Afonso S Bandeira, Katya Scheinberg, and Luis Nunes Vicente. On partial sparse recovery. arXiv preprint 104.2993 2013.
[4] Anirban Basak and Mark Rudelson, Sharp transition of the invertibility of the adjacency ma- trices of sparse random graphs. Probability Theory and Related Fields, pages 1-76, 2021.
[5] Radu Berinde, Anna Gilbert, Piotr Indyk, Howard Karloff, and Martin Strauss. Combining geometry and combinatories: A unified approach to sparse signal recovery. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 798-803 805. IEEE, 2008.
[6] Radu Berinde and Piotr Indyk. Sparse recovery using sparse random matrices, preprint, 2008
[7] Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component detection. Conference on learning theory, pages 1046-1066. PMLR, 2013.
[8] Matthew Brennan and Guy Bresler. Reducibility and statistical-computtationaal gaps from secret leakage. In Conference on Learning Theory, pages 648-847. PMLR, 2020.
[9] Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory, pages 48-166. PMLR, 2018.
[10] Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. In Conference on Learning Theory, pages 417-468. PMLR, 2019.
[11] T Tony Cai and Lie Wang. Orthogonal matching pursuit for sparse signal recovery with noise. IEEE Transactions on Information theory, 57(7):468044688, 2011.
[12] Emmanuel Candes, Terence Tao, et al. The dantzig selector: Statistical estimation when is much larger than n. Annals of statistics, 35(6):2313-235)) 2007.
[13] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2))489-509 2006.
[14] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incom- plete and inaccurate measurements. Communications on Pure and Applied Mathematics; A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8): 100- 2006.
[15] Emmanuel J Candes and Terence Tao. Decoding by linear programming. JEEE transactions on information theory, 51(12):220--2255 2005.
[16] Shaobing Chen and David Donoho. Basis pursuit. In Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers, volume 1, pages 41-44. IEEE, 1994.
[17] Arnak S Dalalyan, Mohamed Hebiri, Johannes Lederer, et al. On the prediction performance of the lasso. Bernoulli, 23(1):552-581, 2017.
10

---

[18] Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975, 2011.
[19] Mark A Davenport, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. A simple proof that random matrices are democratic. arXiv preprint arXiv:0911.0736. 2009.
[20] David L Donoho. Compressed sensing, IEEE Transactions on information theory, 52(4))1289- 1306, 2006.
[21] David I. Donoho, Michael Elad, and Vladimir Temlyakov. Stable recovery of sparse over- complete representations in the presence of noise. IEEE Transactions information theory, 52(())6-18, 2005.
[22] David I. Donoho and Philip Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics, 49(3):906-933 1989.
[23] Rina Foygel and Nathan Srebro. Fast rate and optimistic rate for 11 I1-regularized regression. Technical report, Toyota Technological Institute. arXiv: 1108.037 v1, 2011.
[24] Matthew Franklin, Ran Gelles, Rafail Ostrovsky, and Leonard J Schulman. Optimal coding for streaming authentication and interactive communication. IEEE Transactions on Information Theory, (1(1):133-145, 2014.
[25] David Gamarnik and Ilias Zadik. High dimensional regression with binary coefficients. esti- mating squared eπтоr and phase transtition. In Conference on Learning Theory, pages 948- 953. PMLR, 2017.
[26] Anna Gilbert and Piotr Indyk. Sparse recovery using sparse matrices. Proceedings of the IEEE, 986)99337-947, 2010.
[27] Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Super- polynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pages 3587-3596. PMLR, 2020.
[28] Aparna Gupte and Vinod Vaikuntanathan. The fine-grained hardness of sparse linear regres- sion. arXiv preprint
2021.
[29] Aparna Ajit Gupte and Kerri Lu. Fine- fine-grained complexity of sparse linear regression. 2020.
[30] Sariel Har-Peled, Piotr Indyk, and Sepideh Mahabadi. Approximate sparse linear regression. In 45th International Colloquium on Automata, Languages, and Progrumming (ICALP 2018). fuer Informatik, 2018
Schloss Meastuul-Leibnii-Zeeine
[31] Jonathan Kelner, Frederie Koehler, Raghu Meka, and Ankur Moitra. Learning some popu- lar gaussian graphical models without condition number bounds. In Proceedings of Neural Information Processing Systems (NeurIPS), 2020.
[32] Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. On the power of pre- conditioning in sparse linear regression. 62nd Annual IEEE Symposium on Foundations of Computer Science, 2021.
[33] Michael Langberg. Private codes or succinct random codes that are (almost) perfect. In FOCS, volume 4, pages 325-334--3333 -344, 2004.
[34] Ran Lu. On the strong restricted isometry property of bernoulli random matrices. Journal of Approximation Theory, 245:1-2) 2019.
[35] Michael G Luby. Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A Spiel- man. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 57(2):569- 584, 2001.
[36] Tengyu Ma and Avi Wigderson. Sum-of-squares lower bounds for sparse pea. Advances in Neural Information Processing Systems, 28, 2015.

---

[37] Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2):27-223, 1995.
[38] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Restricted eigenvalue properties for correlated gaussian designs. The Journal of Machine Learning Research, 1 11:2441-2259, 2010.
[39] Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
[40] Jonathan Scarlett and Volkan Cevher. Limits on support recovery with probabilistic models: An information-theorttic framework. IEEE Transactions on Information Theory, 63(1):593- 620, 2016.
[41] Michael Sipser and Daniel A Spielman. Expander codes. IEEE transactions Information Theory, (2(6))1710-1122 1722, 1996.
[42] Daniel A Spielman and Jaeoh Woo. A note on preconditioning by low-stretch spanning trees. arXiv preprint arXiv:0903.2816, 2009.
[43] Ali Tajer and H Vincent Poor. Hypothesis testing for partial sparse recovery. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 901-908. IEEE, 2012.
[44] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[45] Joel A Tropp and Anna C Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on information theory, 53(12):4655 2007.
[46] Sara Van De Geer. On tight bounds for the lasso. Journal of Machine Learning Research, 19:46, 2018.
[47] Sara van de Geer, Johannes Lederer, et al. The lasso, correlated design, and improved ora- cle inequalities. In From Probability to Statisties and Back: High-Dimensional Models and Processes-A Festschrift in Honor Jon A. Wellner, pages 303-316. Institute of Mathematical Statistics, 2013.
[48] Sara A Van De Geer, Peter Bühlmann, et al. On the conditions used to prove oracle results for the lasso. Electronic Journal of Statistics, 3:1360-1392, 1392, 2009.
[49] Santosh Vempala and John Wilmes. Gradient descent for ond-hiddenllayer neural networks: Polynomial convergence and sq lower bounds. In Conference on Learning Theory, pages PMLR, 2019.
[50] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv: 2010.
[51] Roman Vershynin. High-dimenniooal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[52] Vladislav Voroninski and Zhiqiang Xu. A strong restricted isometry property, with ap- plication to phaseless compressed sensing. Applied and computational harmonic analysis, 40(2):386-35,. 2016.
[53] Martin Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery us- ing l1-constrained quadratic programming (lasso). IEEE transactions on information theory, 55(5):2183-2202, 2009.
[54] Martin J Wainwright. digeediimeiional statisties: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[55] Tengyao Wang, Quentin Berthet, and Yaniv Plan. Average-case hardness of rip certification. Advances in Neural Information Processing Systems, 29, 2016.
[56] Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. Advances in neural information processing systems, 13, 2000.
12

---

[57] Yuchen Zhang, Martin Wainwright, and Michael I Jordan. Lower bounds on the performance of polynomial- time algorithms for sparse linear regression. In Conference on Learning Theory, pages 921-948, 2014.
[58] Yuchen Zhang, Martin J Wainwright, Michael Jordan, et al. Optimal prediction for sparse linear models? lower bounds for coordinate-separabl m-estimators. Electronic Journal of Statistics, 11(1):752-79, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 2
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See supplemental material
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did report eтror bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 'e using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yKguTVwWO8K", "reviewer": "Reviewer_dzk8", "summary": "This paper considers a sparse linear regression problem, where the covariate matrix is very-ill conditioned. This paper is motivated by the fact that there might be a computational-statistical tradeoff for this problem. That is, no polynomial-time algorithm exists which solves this problem in polynomial-time with an information theoretically (near-)optimal sampling rate. \n\nThis paper constructs a covariate matrix and a corresponding signal distribution such that any randomized $S$ preconditioned LASSO fails with high probability, if $S$ is a square matrix. In case that $S$ is a rectangular matrix contains a result of similar flavour. (However, in the latter scenario the paper only shows that any randomized $S$-preconditioned LASSO fails with probability $1/2$.) This gives first evidence that there might be a computational-statistical tradeoff in this problem.\n\nMoreover, as a byproduct in the proof of the main result, this paper establishes a result about sparse linear regression with adversarial erasures.", "questions": "1. Many (all?!) other problems, which exhibit a computational-statistical tradeoff, like RIP certification or sparse PCA, can be reduced to the planted clique conjecture (at least in a certain sense). This seems not to be the case for this problem. It would be great if the authors could elaborate further on this.\n\n2. LASSO is not the only algorithm one could apply to this problem. It would be great if the authors could comment on why they expect that properly modified variants of other algorithms like orthogonal matching pursuit also will not work in the low-sample regime.\n\n3. In the abstract the authors write: \"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.\" Are there any references where this possibility is discussed?\n\n4. The paper uses the term LASSO to describe the optimisation problem (1). Would it not be more accurate to use the terminology \"basis pursuit\" instead?", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In contrast to other problems where these tradeoffs are suspected (k-Clique, sparse PCA,...) and reductions to the k-clique problem are known, sparse linear regression with ill-conditioned covariates is surprisingly poorly understood. This paper makes an important step towards better understanding this problem and identifying a potential computational-statistical tradeoff. Moreover, this paper is extremely well-written and it is a pleasure to read.\n\nTo conclude, I think this is a very strong paper which should published.\n\nTypos:\nl. 294: leas->leads", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uoQ4Yyr6o_f", "reviewer": "Reviewer_ahcD", "summary": "In this work, lower bounds on randomly preconditioned Lasso are provided. The authors construct a covariance matrix and a sparse signal distribution under which any randomly-preconditioned Lasso program with invertible preconditioners fails. The key technique is a new robustness result in compressed sensing, and the authors study recovering a sparse signal when a few measurements can be erased adversarially.", "questions": "I am wondering whether a matching upper bound can be achieved by computationally efficient algorithms.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper is well-written. Both the main theoretical results (lower bounds on randomly preconditioned Lasso) and the key proof technique (erasure-robust sparse designs) are interesting to me. Although I have not checked the proofs in detail, the theoretical results seem to be reliable based on the technical overview.\n\nWeaknesses: The authors should write down the full version (instead of informal statement) of the main theorems in the main text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "r90XMvDqx26", "reviewer": "Reviewer_nP3f", "summary": "The paper shows that the use of randomized preconditioners does not improve the performance of preconditioned lasso, as it is always possible to find data distributions (over sufficiently sparse signals) where the number of samples required by randomly preconditioned Lasso is linear. The analysis is tied to a result in compressed sensing that shows tolerance to adversarial erasure of randomized measurements that still allows partial recovery of the signal support, by exploiting the fact that binary random matrices are likely to provide adjacency matrices for expander graphs.\n", "questions": "Corollary 1.5 should be more explicit about what it means to identify \"information theoretically\" - the estimator in line 214 looks for the sparsest signal that meets a mismatch up to delta per observed measurement: how is this information-theoretic? \n\nWhat does \"morally\" refer to in line 233? Is this discussion of preconditioners specific to random ones? Plenty of dense preconditioners can provide sparsity.", "limitations": "The compressed sensing result hinges on a non-practical recovery algorithm, hindering its applicability. It is also not fully clear how this aspect of the CS result impacts the preconditioner result - perhaps there could be a different recovery method that improves over the results here.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The description in Section 2.1-2.2 is instructive.\n\nIt would be illuminating to have a discussion of the traits of the data distributions that nullify the possible improvement of randomized preconditioners. Perhaps this can inform whether randomized preconditioners may provide an advantage for the distribution at hand.\n\nAlthough Theorems 1.2 and 1.3 easily track their counterparts in the supplement, it is less clear to see the relationship between Theorem 1.4 and its counterpart.\n\nThe acronym SLR should be defined.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WRcuY0wAoki", "reviewer": "Reviewer_S6CT", "summary": "This paper investigated the problem of random-design sparse linear regression. Recent work 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. For an appropriate covariance matrix, a single signal distribution is constructed on which an 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. ", "questions": "1. What dose “statistical/computational gap” mean in the Abstract? And what is the “lower bound\"? It is better to provide detailed explanations of these terms in this paper. \n2. Please provide the reference for “Lasso” and its interpretation.\n3. Is it possible to include numerical examples in this paper? This is helpful for readers to better understand the correctness and effectiveness of the results.", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This manuscript studied recovering a sparse signal when a few measurements can be erased adversarially. Generally speaking, the paper is well-written, and enriched the existing results. However, the paper contains also several weaknesses:\n1. The structure of the paper can be re-organized thus to improve the readability. So far, the paper contains only two sections. The flow of revealing the ideas and results is not very smooth and clear. The main contributions should be summarized in Section I. Moreover, (most of) the theoretical results established in the paper are presented in informal form. Then why not simply present them in the supplementary material and just cite them in the paper? These informal statements render it difficult to judge the results of the paper in a rigorous setup.  \n2. The paper is purely theoretical. The established computational and/or statistical results shall be compared against existing sparse recovery methods via substantial numerical simulations.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept