Summary
This work studies the problem of sparse linear regression under the statistical model where the examples are drawn as zero-mean Gaussians with covariance matrix $\Sigma$ and each response is a t-sparse linear combination of the examples plus i.i.d. Gaussian noise. While classical results establish that the LASSO can computationally efficiently recover a good solution v* with a nearly optimal number of samples when the covariance matrix $\Sigma$ is well-conditioned, guarantees beyond this simple setting are substantially lacking, with a few notable exceptions. In general, not much is known beyond a brute-force approach of trying all $\binom{n}{t}$ sparsity patterns, which requires $n^t$ time. This work shows that even if $\Sigma$ is ill-conditioned, if Sigma is well-conditioned after removing the top or bottom O(1) eigenvalues (i.e. a notion of “robust” well-condtionedness), then this running time can be improved to roughly $f(t) \cdot n^3$.
When there are a small number of tiny eigenvalues, the main problem is the existence of sparse linear dependencies among the variables. The algorithmic approach to address this problem is then to iteratively peel off a small number of these variables at a time (IterativePeeling()). This procedure gives a construction of a small dictionary of vectors such that any t-sparse vector can be written as a linear combination of this dictionary with coefficients bounded in L1 (Lemma 2.9), which in turn implies that the LASSO identifies a good solution v in the sense of bounded excess risk. The authors interpret the technique of applying LASSO to an augmented dictionary as “feature adaptation”.
Strengths
* Sparse linear regression is a widely studied yet notoriously difficult problem, and this work identifies a very natural class of inputs for which positive results can be obtained.
* I find the discussion in Section 2.1 on the proposal of (t, alpha) dictionaries as a canonical abstraction of all existing approaches to sparse linear regression to be very interesting and valuable. It helps concentrate research efforts on this problem to this more structured approach, and I believe it may prove to be influential in following works on sparse linear regression.
Weaknesses
* It seems like like there are no bounds on the sparsity of the approximate solution v that is outputted by this algorithm, probably due to the fact that the feature adaptation step augments the feature set with dense linear combinations of the existing variables (please let me know if I have misunderstood). Thus, the measure of the “sparsity” of this algorithm lies in the small sample complexity, rather than its ability to output a sparse solution. Thus, the guarantees of this algorithm are tightly linked to the statistical setting of sparse linear regression, and it may be difficult to adapt these techniques to the problem of outputting a good sparse solution to linear regression. However, I do find this limitation very interesting, and I wonder if there are gaps between the performance of these algorithms if one is required to output a sparse solution. Such separations are known in certain sparse recovery settings (see, e.g., https://arxiv.org/abs/1110.4414).
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.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The authors have provided adequate discussion of limitations