Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper studies the information-theoretic lower bound for list-decodable linear regression via statistical queries (SQ). The main contribution is on the linear regression in the presence of a majority of adversarial outliers. The goal is to make a small number of queries where the labeled examples are drawn from a corrupted version (the majority is corrupted) of Gaussian linear regression and return a small list of regression vectors such that at least one vector is close to the target Gaussian linear regression vector.
 
The results are two-fold. The first result shows an information-theoretic bound. Namely, there exists a (computationally inefficient) list-decoding algorithm that uses a small number of samples and returns a small size of list consisting of hypothesis vectors where at least one vector has a small $\ell_2$-error. The second result is a SQ lower bound. Any SQ algorithm that list-decoding learns the corrupted version of Gaussian linear regression does one of the following: (1) uses at least one STAT query with small tolerance, (2) makes an exponential number of queries, or (3) returns an exponentially large list.
 

main_review: The focus is on the second result, which shows strong SQ lower bounds and can be viewed as evidence that current upper bounds might be qualitatively best possible. This result is based on the approaches in [DKS17], [FGR+17], and [DKS19]. Following [DKS17], an SQ-hard family of distributions can be constructed by matching distributions A to low-degree moments of the standard Gaussian. For each distribution A, we consider the distribution $P_{A,v}$ where in the v-direction is a copy of distribution A and standard Gaussian in the orthogonal complement. The collection of $P_{A,v}$’s where the v’s form a set of nearly orthogonal unit vectors, is SQ-hard to learn. Since there exists a large set of nearly orthogonal unit vectors, one can show that if the SQ algorithm does not satisfy conditions (1) and (2), the list must be exponentially large.
 
The technical obstacle is that, unlike in [DKS17], this setting does not possess the symmetry properties required for moment-matching. Therefore, to establish SQ-hardness, a more careful argument for conditional distribution mixing is required, and there are more technical challenges that necessitate a modification to the moment-matching problem.
 
Although the main idea follows [DKS17], the tweak used to adapt the obstacles is non-trivial, especially the moment-matching approach used for Theorem 2.5. The paper clearly states the differences from the previous contributions and the related work is adequately cited. The authors have put a lot of effort into transmitting the ideas and I found the paper to be very well-written. Overall, I would tend towards accepting this paper since it makes progress in list-decodable learning and the technical contributions especially the conditional distribution mixing and the moment-matching techniques might have applications in other related problems.
 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proves a strong SQ lower bound for the problem of Gaussian linear regression in the list-decodable setting. In this problem, one is given access to a corrupted distribution $E = \alpha D + (1 - \alpha) N$, where:
  - the inlier distribution $D$ is the joint distribution of $(X, y)$ where $X \sim N(0, I_d)$ is Gaussian and $y = \beta^T X + \eta$ for some unknown weight vector $\beta$ and Gaussian noise $\eta$;
  - $N$ is an _arbitrary_ outlier distribution;
  - and $\alpha$ is thought of as a small constant.

The goal is to output a list $L$ of "small" size (traditionally $\text{poly}(1/\alpha)$) containing a $\hat{\beta}$ such that $\\|\hat{\beta} - \beta \\| \leq 1/4$.

The lower bound that the authors obtain is that any SQ algorithm using queries of tolerance at least $d^{O(1/\sqrt{\alpha}})$ must use either $2^{d^{\Omega(1)}}$ queries or require list size $2^{d^{\Omega(1)}}$.

This is an important result in list-decodable regression, a model that has recently become popular in robust statistics. To my knowledge, this is the first lower bound for this problem, and qualitatively matches current upper bounds.
main_review: The list-decodable setting has grown increasingly popular in robust statistics recently, and this paper makes an important contribution by showing a good (and to my knowledge first) lower bound for list-decodable linear regression in the widely-studied SQ model. The framework used for the lower bound is that of FGRVX17 for distributional SQ search problems, and the construction builds on the approach of DKS17. This latter approach -- involving a hard family of "Gaussian-except-in-hidden-direction" distributions along with moment matching properties -- is proving increasingly useful as a foundation for constructing hard SQ families. The authors use considerable technical skill to adapt this construction approach to the type of challenging corruption model they deal with. The main technical core is a nonconstructive approach for constructing distributions of a certain constrained form that have Gaussian low-degree moments. 

The writing and exposition is clear and of high quality. The authors generally take care to first qualitatively sketch the mathematical approach being taken, even when it is somewhat technical. That said, the proofs are occasionally a little terse.

One thing I would be interested to see is a brief expository discussion of where in the proof the real magic of dealing with the "list" part of "list-decodable" is taking place. The authors spend time on the strong corruption model, but the learner's ability to output a list is not dwelt on as much. If I understand correctly, a lot of the legwork is done by the careful definition of the distributional search problem and the appearance of the $\mathcal{Z}^{-1}(L)$ in the SQ dimension, where $\mathcal{Z}$ is the solution mapping. This seems interesting because $\mathcal{Z^{-1}}$ is inherently a set function: even if $L$ were a singleton (so the learner does not output a list), $\mathcal{Z}^{-1}(L)$ would still be a set and the proof would not look much different (IIUC). So is the "list" aspect not particularly relevant from an SQ standpoint, only the corruption model?

Regarding originality, while it is true that this work builds on frameworks that have by now been seen relatively often in the SQ literature, the technical work required is still very substantial. I think that by any measure this work qualifies as original as well as significant. I have not verified every proof in complete detail but I did spend some time on the main ones and they look correct to me. I also only skimmed the material in Appendix E and F.
limitations_and_societal_impact: The authors are generally clear about the scope of this result, and I am not aware of any potential negative societal impact of this work.

One small technical curiosity is that in the formal statement of the lower bound, there is no dependence of the list size on $\alpha$, even though usually one considers $\text{poly}(1/\alpha)$-sized lists for such problems. (This sort of thing does happen often with SQ lower bounds, granted.) I suppose that when $\alpha$ is constant, $2^{d^{\Omega(1)}}$ is stronger than $\text{poly}(1/\alpha)$. In any case I'd be interested to hear the author's thoughts on the matter. It possibly dovetails with my question above about the "list" aspect of the proof.

A possible typo: in the full proof of Thm 2.1 in Appendix B, in line 662, I believe it should just be "any $u \in \mathbb{R}^d$" as opposed to "any $u \in \mathcal{F}$".
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: They study the computational complexity of list-decodable linear regression where an alpha < 1/2 fraction of the points (x,y) are inliers such that the x's come from N(0,Id) and y = <v,x> + N(0,sigma^2), the remaining 1 - alpha fraction of the points are chosen arbitrarily, and the goal is to output some dimension-independent list of candidate solutions containing v. They show that any statistical query algorithm for this problem which outputs a list of 2^{d^{o(1)}} solutions containing a vector O(1)-close to v must either make 2^{d^c} queries or make at least one query with tolerance d^{-1/sqrt(alpha)}. This is reminiscent of existing upper bounds for this problem which run in time roughly d^{poly(1/alpha)}. Notably, the lower bound proved in this paper is in sharp contrast with the complexity of learning mixtures of linear regressions, a special case of this problem where quasipolynomial dependence on 1/alpha is possible.

The proof technique is based on a variant of the framework of [DKS17] introduced in [DKS19], namely they show the existence of a moment-matching family of instances of list-decodable regression which match up to degree-poly(1/alpha) moments with N(0,Id). Concretely, for any instance in the family, the marginal distribution on y looks Gaussian (with carefully tuned variance), and for any value of y = y_0, the conditional distribution on x projected to a particular direction (the direction of the ground truth regressor) is a 1D distribution that matches N(0,1) on poly(1/alpha) moments, and orthogonal to this direction is isotropic Gaussian.

This essentially boils down to a 1D problem: given a point mass at a fixed y and a particular mixing parameter alpha_y, produce a distribution F_y which, if mixed with the point mass according to alpha_y, matches poly(1/alpha) moments with N(0,1). For technical reasons, F_y needs to be discrete and of bounded support so that certain relative chi-squared divergence bounds hold. They formulate a necessary and sufficient condition (bounds on Gaussian integrals of certain polynomials) for such an F_y to exist using LP duality and Caratheodory's and directly verify this condition.
main_review: Regarding originality, I think the novelty of the technical contribution is quite solid. While the overall framework of the proof is based on [DKS17], the main challenge is how to actually exhibit moment-matching examples, which is always very problem-specific. And while LP duality has been used previously in the context of moment-matching, e.g. in works on getting minimax rates for symmetric functional estimation, there are a number of hurdles unique to the setting in this particular work, e.g. how to ensure chi-squared divergence bounds hold, how to tune the variance of the reference distribution on y, etc.

The writing was fairly clear, though the specific choice of reference distribution was a bit mysterious to me. It makes sense to me as described in Lines 188-200 why you'd want the variance to be bigger, but perhaps around Lines 319-321 the authors could vaguely sketch how it actually gets used in the proofs of Theorem 2.5 and Lemma 2.6?

One conceptual complaint is that the existing algorithms for list-decodable regression are based on assigning sum-of-squares variables to indicate whether each point in the dataset is an outlier or not. It's not clear whether these can be turned into statistical query algorithms, so it's a bit strange to be proving SQ lower bounds for this problem. The low-degree hypothesis testing result in Section F is morally related to sum-of-squares, but lower bounds for the former need not translate to lower bounds for the latter. 

That said, as the authors point out in lines 119-125, the best known algorithm for learning mixtures of linear regressions can be implemented in SQ, so this paper does still give a genuine separation between that and list-decodable regression.

Miscellaneous comments:
- Perhaps the authors could mention some of the other relatively recent works that exploit LP duality for moment matching, e.g. Wu-Yang, Han-Jiao-Weissman, etc? Those settings don't seem very related, but it would be good to comment on them if there are any conceptual similarities.
- It was a bit tricky jumping between the main body and the appendix because while the lemma statements from the body are restated, the numbering is different. It would be helpful if the authors could add pointers to address this confusion.
limitations_and_societal_impact: The main theorem is an impossibility result, so I don't think there is any negative societal impact. As for the limitations, it might be good to remark somewhere in the introduction that the current upper bounds are not SQ.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, a statistical query lower bound is analyzed for the list-decodable linear regression problem, where an adversary can corrupt a majority of the examples (more than a half). The goal of list decoding is to output a small list of hypothesis vectors such that at least one of them is close to the true regression vector. The authors first analyze the information-theoretic limit for this problem, which shows that there exists a gap between the information-theoretic limit and the computational limit based on SoS hierarchy. Then, the authors derive a statistical query (SQ) lower bound, which restricts the available algorithms only to SQ algorithms, which have access to query expectations of bounded functions of the distribution rather than to samples. The derived SQ lower bound shows that the computational limit from the previous algorithm (based on SoS hierarchy) is nearly optimal for the set of SQ algorithms.
 

main_review: The main contribution of this work is at deriving a strong SQ lower bound for the list-decodable Gaussian linear regression problem. The strength of this converse result comes from the generality of SQ algorithms, which include a broad class of algorithms based on spectral methods, moment methods and local search. This result also has implications to a related restricted computational model as well, including low-degree (polynomial) algorithms, and allows a similar lower bound for the low-degree model. 

Establishing information-computational trade-off and analyzing the gap between the two limits for statistical inference problems is an important topic. This work makes some progress on the analysis of such trade-offs for the list-decodable linear regression problem with majority of outliers.

In the proof of SQ lower bound, the main technical contribution comes from analyzing SQ dimension (SQ-hardness result) for the model with majority of outliers. To circumvent some difficulties in designing outlier distribution with moment-matching up to poly(1/\alpha) moments, the authors establish the existence result of the desired outlier distribution in a non-constructive manner.  

Overall, this paper has importation implications for information-computational trade-off for list-decodable linear regression problem with majority of outliers, and the established SQ lower bound shows that the current upper bounds are nearly best possible. 

Question: For non-Gaussian linear regression problem, any approach to derive a similar type of SQ lower bound? Some comments would be great. 

UPDATE: response read. Thank you for the response!
limitations_and_societal_impact: Limitations are not addressed.
review_title: null

Meta-review: The paper shows an SQ lower bound for the list decodable version of linear regression which "matches" existing algorithms. This suggests a computational limitation that may be inherent in this problem. The proofs require significant technical innovation over prior work and the results are important and interesting.
Decision: Accept (Spotlight)