Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

Weaknesses: The authors should write down the full version (instead of informal statement) of the main theorems in the main text.
questions: I am wondering whether a matching upper bound can be achieved by computationally efficient algorithms.
limitations: Not applicable.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
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:
1. 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.  
2. The paper is purely theoretical. The established computational and/or statistical results shall be compared against existing sparse recovery methods via substantial numerical simulations.

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. 
2. Please provide the reference for “Lasso” and its interpretation.
3. 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

strengths_and_weaknesses: The description in Section 2.1-2.2 is instructive.

It 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.

Although 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.

The acronym SLR should be defined.
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? 

What 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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

This 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.

Moreover, as a byproduct in the proof of the main result, this paper establishes a result about sparse linear regression with adversarial erasures.
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.

To conclude, I think this is a very strong paper which should published.

Typos:
l. 294: leas->leads
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.

2. 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.

3. 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?

4. 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
review_title: null

Meta-review: metareview: This paper studies the problem of sparse regression with ill-conditioned Gaussian covariates. Despite the simplicity of this problem formulation and the extensive studies of sparse linear regression, the potential existence of a statistical-computational gap for this problem has not been well understood. Taking a step towards understanding this problem, the authors provide theoretically rigorous evidence about the limitation of randomly preconditioned Lasso for this problem. The paper contains solid impossibility results, and hence I recommend acceptance.  Note that one reviewer has suggested ways to improve the structure and readability of the paper, which I hope the authors can address in the final paper; the paper would also benefit from having more substantial experiments. 
confidence: Certain
Decision: Accept