Statistical Query Lower Bounds for List-Decodable Linear Regression
Authors: Ilias Diakonikolas
Daniel Kane
Ankit Pensia
Thanasis Pittas
Alistair Stewart
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: learning theory
high-dimensional robust statistics
statistical query model
list-decodable learning
linear regression

Abstract: We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Specifically, we are given a set $T$ of labeled examples $(x, y) \in \mathbb{R}^d \times \mathbb{R}$ and a parameter $0< \alpha <1/2$ such that an $\alpha$-fraction of the points in $T$ are i.i.d. samples from a linear regression model with Gaussian covariates, and the remaining $(1-\alpha)$-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output a small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of $d^{\mathrm{poly}(1/\alpha)}$ for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.


Statistical Query Lower Bounds for List-Decodable Linear Regression
Ilias Diakonikolas University of Disconsin-Madiin ilias@cs. wisc. edu
Daniel M. Kane University of California, San Diego dakane@cs, uesd.
Ankit Pensia
Thanasis Pittas
University of Wisconsin-Madison ankitpêcs. wisc edu
University of Wisconsin-Madison
pittas@wisc. edu
Alistair Stewart
Web 3 Foundation
stewart.. al ml@@mail.ccom com com
Abstract
We study the problem list-decodable linear regression, where an adversary can corrupt majority of the examples. Specifically, are given set T of labeled examples (z, y) E IR x and parameter 0 < a < 1/2 such that an a-fraction of the points in T are i..d. samples from linear regression model with Gaussian covariates, and the remaining (1 ar)-fraction of the points are drawn from an arbitrary noise distribution. The goal is to output small list of hypothesis vectors such that at least one of them is close to the target regression vector. Our main result is a Statistical Query (SQ) lower bound of (poly(1aa) for this problem. Our SQ lower bound qualitatively matches the performance of previously developed algorithms, providing evidence that current upper bounds for this task are nearly best possible.
Introduction
1.1 Background and Motivation
Linear regression is one of the oldest and most fundamental statistical tasks with numerous applica- tions in the sciences (RL87 Die01 McD09]. In the standard setup, the data are labeled examples (z(1), (²). where the examples (covariates) ( are i.i.d. samples from distribution D3 Rd and the labels () are noisy evaluations of a linear function. More specifically, each label is of the form (+)) B (x) + (,) where (8) is the observation noise, for unknown target regression vector Rdd The objective is to approximately recover the hidden regression vector. this basic setting, linear regression is well-understood. For example, under Gaussian distribution, the least-squares estimator is known to statistically and computationally efficient.
Unfortunately, classical efficient estimators inherently fail in the presence of even very small fraction of adversarially corrupted data. several applications of modern data analysis, including machine learning security [BNITTO) BNL12 SKLI17 DKK+19 and exploratory data analysis, e.g.. in biology IRWW 02 PLJDIO LAT+08) typical datasets contain arbitrary or adversarial outliers. Hence, it is important to understand the algorithmic possibilities and fundamental limits of learning and inference in such settings. Robust statisties focuses on designing estimators tolerant to a small
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

amount of contamination, where the outliers are the minority of the dataset. Classical work in this field [ARRS86] HR09 developed robust estimators for various basic tasks, alas with exponential runtime. More recently, a line of work in computer science, starting with LDKK11 [RV16), developed the first computationally efficient robust learning algorithms for various high-dimensional tasks. Subsequently, there has been significant progress in algorithmic robust statistics by several communities, see [DK19] for a survey on the topic.
In this paper, we study high-dimensional robust linear regression in the presence of a majority of adversarial outliers. As we explain below, in several applications, asking for minority of outliers is too strong of an assumption. It is thus natural to ask what notion of learning can capture the regime when the clean data points (inliers) constitute the minority of the dataset. While outputting a single accurate hypothesis in this regime is cenmmationnthooettccin
impossible, one may be able to compute a small list of hypotheses with the guarantee that al least one of them is accurate. This relaxed notion is known as list-decodable learning [BB CSV17). formally defined below.
Definition 1.1. (List-Decodable Learning) Given a parameter 0 < a < 1/2 and distribution family D on Fdd the algorithm specifies n é 24 and observes i.i.d. samples from a distribution E' = aD + (1-x).N NN, where D is an unknown distribution in D and N is arbitrary. We say D is the distribution of inliers, N is the distribution of outliers, and
an (1-a)- corrupted version of D. Given sample access to an (1 (1-a)-corrupted version of D, the goal is to output a "small" list of hypotheses L at least one of which is (with high probability) close to the target parameter of D.
We note that a list of size (11/a)) typically suffices; an algorithm with a poly (1a) sized list, or even a worse function of 1/a (but independent of the dimension d) is also considered acceptable.
Natural applications of list-decodable learning include crowdsourcing, where a majority of partic- ipants could be unreliable [SVCI6, MV18), and semi- semi-random community detection in stochas- tic block models [CSVI7]. List-decoding is also useful in the context of semi-verified learn- ing [CSV17 MV18), where learner audit very small amount of trusted data. If the trusted dataset is too small to directly learn from, using a list-decodable learning procedure, one can pinpoint a candidate hypothesis consistent with the verified data. Importantly, list-decodable learning generalizes the task of learning mixture models, see, e.g., DD [J94| ZID16 LL18] KC20 CLS20 DK20 for the case of linear regression studied here. Roughly speaking. by running list-decodable estimation procedure with the parameter a equal to the smallest mixing weight, each true cluster of points is an equally valid ground-trutt distribution, so the output list must contain candidate parameters close to each of the true parameters.
In dist-decodable linear regression (the focus of this paper), D is distribution on pairs (X, v), where X is a standard Gaussian on IRd, is approximately linear function of x, and the algorithm is asked to approximate the hidden regressor. The following definition specifies the distribution family D of the inliers for the case of linear regression with Gaussian covariates.
Definition 1.2. (Gaussian Linear Regression) Fix a > O. For B E Rdd, let D3 be the distribution over (X, X E RRd, y E R. such that X ~ (0, Ia) and y = 8d X + .7. where 1j ~ (O),o")) independently of X. We define D to be the set {Dg 8 E S'} for some set S' RR..
Recent algorithmic progress [KKK19 RY20a| has been made on this problem using the sum-of- squares (SoS) hierarchy. The guarantees in [KKK19 RY20al are very far from the information- theoretic limit in terms of sample complexity. In particular, they require (Poly(1/a) samples and time to obtain non-trivial error guarantees (see Table []: [KKK19 obtains an error guarantee of O(a ((r/aa) with a list of size (11/a), whereas RY20al obtains an error guarantee of ((//a3/2) with a list of size (1/ (a))) (log(
On the other hand, as shown in this paper (see Theorem 1.4). poly(d/a) samples information- theoretically suffice to obtain near-optimal error guarantees. This raises the following natural question:
What is the complexity of list-decodable linear regression? Are there efficient algorithms with significantly better sample-time tradeoffs?
We study the above question in natural and well-studied restricted model of computation, known as the Statistical Query (SQ) model [Ka99]] As the main result of this paper, we prove strong SQ lower bounds for this problem. Via recently established equivalence [BBH+20 20), our SQ lower bound also
2

---

Table I: The table summarizes the sample complexity, running time, and list size of the known list-decodable linear regression algorithms in order to obtain a 1/4-additive approximation to the hidden regression vector /3 in the setting of Theorem 1.5 i.e., when || S 1 and a is sufficiently small as function of a: [KKI19] requires o = (()) and [RY20a] requires or = O(a3/3)
Algorithmic Result
Sample Size
Running Time
List size
(d/a))(1aa) (d/a))(2la)) (O(1aa)
Karmalka-Kllvans-KKnn Klivans-Kothari KKK19
0(1/a) (1(1)"))1/aalooo)) (1/a)0(ox(1a))
Raghavendra and Yau RY200a
implies low-degree testing lower bounds for this task. Our lower bounds can be viewed as evidence that current upper bounds for this problem may be qualitatively best possible.
Before we state our contributions in detail, we give some background on SQ algorithms. SQ algorithms are a broad class of algorithms that are only allowed to query expectations of bounded functions of the distribution rather than directly access samples. Formally, an SQ algorithm has access to the following oracle.
Definition 1.3 (STAT Oracle). Let be a distribution on Rd. A statistical query is a bounded function q : Rd + [-1, 1]. For 0, the (TAT(T) oracle responds to the query q with value such that 0 Ex-D S т. We call 7 the tolerance of the statistical query.
The SQ model was introduced by Kearns Kea98 in the context of supervised learning as a natural restriction of the PAC model [a1844 Subsequently, the SQ model has been extensively studied in plethora of contexts (see, e.g.. [Fe116] and references therein). The class of SQ algorithms is rather broad and captures range of known supervised learning algorithms. More broadly, several known algorithmic techniques in machine learning are known to be implementable using SQs. These include spectral techniques, moment and tensor methods, local search (e.g., Expectation Maximization), and many others (see, e.g., [FGR* 17 FGV17)).
1.2
Our Results
We start by showing that poly samples are sufficient to obtain a near-optimal error estimator, albeit with a computationally inefficient algorithm.
Bound). There is a (computationally inefficient) list-decoding algorithm for Gaussian linear regression that uses (dda²) samples, returns a list of O(1/a)) many hypothesis vectors, and has ey-error guarantee of O((a/aa ((oo//aa/ / /log(I/a)), Moreover, if the dimension is sufficiently large, any list-decoding algorithm that outputs a list size poly (1/a) must have f2-error at least (((//o)/ /lo(/////////a)))
Theorem 1.4 (Information-Theoome
Due to space limitations, the proof of Theorem 1.4 is deferred to the supplementary material (see Theorems D.I and D.4). We note that the (computationally inefficient) estimator achieving the upper bound Theorem 1.4 is implicit in [KK19 See Appendix D.I for more details.
Our main result is a strong SQ lower bound for the list-decodable Gaussian linear regression problem. We establish the following theorem (see Theorem 2.1 more detailed formal statement).
Theorem 1.5 (SQ Lower Bound). Assume that the dimension d E Σ+ is sufficiently large and consider the problem of list-decodable linear regression, where the fraction of inliers is a E (0, 1/2), the regression vector 3 E IRd has norm ||31|2 S 1, and the additive noise has standard deviation < a. Then any SQ algorithm that returns a list C of candidate vectors containing a 3 such that ||3 - B112 I 1/4 does one of the following: (i) it uses at least one query with tolerance at most d (a)//a /o, (ii) it makes 2 queries, or (iii) returns a list of size |C] 2
Informally speaking, Theorem 1.5 shows that no SQ algorithm approximate 3 to constant accuracy with a sub-exponential in (() size list and sub-exponential in d((1) many queries, unless using queries of very small tolerance that would require at least ( samples to simulate. For a not too small, e.g., a = poly (ax), view of Theorem 1.4 this result can be viewed as an information-computaane tradeoff for the problem, within the class of SQ algorithms.
3

---

A conceptual implication of Theorem 1.3 is that list- distddecdeable linear regression is harder (within the class of SQ algorithms) than the related problem of learning mixtures of linear regressions (MIR). Recent work [K20 gave an algorithm (easily implementable in SQ) for learning MLR with & equal weight separated components (under Gaussian covariates) with sample complexity and running time (Polylog(k), i.e., quasi-polynomial in k. Recalling that one can reduce k-MLR (with well-separated components) to list-decodable linear regression for a = 1/k: Theorem 1.5 implies that the aforementioned algorithmic result cannot be obtained via such a reduction.
Remark 1.6. We note that our lower bounds rule out efficient algorithms in the SQ model, which is broad class of algorithms. The two existing algorithms [RY20al KKK19] for the present problem are based on the sum-of -quuooes (SoS) hierarchy. In general, SQ lower bounds do not imply lower bounds against all SoS algorithms, and SoS lower bounds do not imply SQ lower bounds. At the same time, lower bounds against low-degree tests [HS17 HKP* 17 Hop18 KWB19 have become the standard heuristic for SoS lower bounds, and establish hardness against low-degree tests as well. In particular, recent work [BBH 20] established that (under certain assumptions) an SQ lower bound also implies qualitatively similar lower bound in the low-degree model. By leveraging this connection, we deduce a similar lower bound in the latter model as well (see Appendix F
1.3 Overview of Techniques
In this section, we provide detailed overview of our SQ lower bound construction. We recall that there exists general methodology for establishing SQ lower bounds via an appropriate complexity measure, known as SQ dimension. Several related notions of SQ dimension exist in the literature. see, e.g., [BFT 94 FGR Fel17). Here we focus on the framework introduced in [FGR + 17] for search problems over distributions, which more natural in our setting. A lower bound on the SQ dimension of search problem provides an unconditional lower bound on the SQ complexity of the problem. Roughly speaking, for a notion of correlation between distributions in our family D (Definition
L88). establishing an SQ lower bound amounts to constructing a large cardinality sub-family D' C D such that every pair of distributions in D' are nearly uncorrelated with respect to given reference distribution R (see Definition 1.10 and Lemma I.II).
general framework for constructing SQ-hard families of distributions was introduced in [DKS17]. which showed the following: Let the reference distribution R be NN I) and A be univariate distribution whose low-degree moments match those of the standard Gaussian (and which satisfies an additional mild technical condition). Let PA.e be the distribution that is copy of A in the v- direction and standard Gaussian in the orthogonal complement (Definition Then the distribution JrES, where S is set of nearly orthogonal unit vectors, satisfies the pairwise nearly uncorrelated property (Lemmal 1.13), and is therefore SQ-hard to learn.
family ]
Unfortunately, the [DKS17) framework does not suffice in the supervised setting of the current paper for the following reason: The joint distribution over labeled examples (X, y) in our setting does not possess the symmetry properties required for moment- moment-matching with the reference R = N(,0 I) to be possible. Specifically, the behavior of y will necessarily be somewhat different than the behavior of X. To circumvent this issue, we leverage an idea from [KST1]. The high-level idea is to construct distributions Fg on (X, y) such that for any fixed value yo of y. the conditional distribution of X y = you under E, is of the form PA,v described above, where A is replaced with some Ago
We further explain this modified construction. Note that E,, should be of the form aD, + (1-a)NN, where D, is the inlier distribution (corresponding to the clean samples from the linear regression model) and N,, is the outlier (noise) distribution. To understand what properties our distribution should satisfy, we start by looking at the inlier distribution D. By definition, for (X, y) ~ D, we have that y = 3T X + 17. where X (N( and r) (O, o²) is independent of X. A good place to start here is to understand the distribution of X conditioned on y yo. for some yo. under D. is not hard to show (Fact 2.3 that this conditional distribution is already of the desired form PA.a: it is a product of a (d dimimensional standard Gaussian in directions orthogonal to B, while in the 3-direction it is much narrower Gaussian with mean proportional to you To establish our SQ-hardness result, we would like to mix this conditional distribution with a carefully selected outlier distribution N y = you such that the resulting mixture E y = yo matches many of its low-degree moments with the standard Gaussian in the 3-direction, while being standard Gaussian in the orthogonal directions. In the setting of minority of outliers, [DKS19 was able to provide an explicit formula for N and match three moments to show an SQ lower bound of 2(d²). The main

---

technical difficulty in our paper is that, in order to prove the desired SQ lower bound of 12 (ddPoly() we need to match poly(1/a) many moments. We explain how to achieve this below.
Here we take a different approach and establish the existence of the desired outlier distribution Nly Yo in non-constructive manner. We note that our problem is instance of the moment- matching problem, where given sequence of real numbers, the goal is to decide whether distribution exists having that sequence as its low-degree moments. At high-level, we leverage classical results that tackle this general question by formulating a linear program (LP) and using LP-duality to derive necessary and sufficient feasibility conditions (see [S53]] and Theorem 3.1. p. This moment- via LP duality approach is fairly general, but stumbles upon two technical obstacles in our setting.
The first technical issue is that our final distributions E. on v) need to have bounded x². divergence with respect to the reference distribution, since the pairwise correlations scale with this quantity (see Lemma 1.13). To guarantee this, we can ensure that the outlier distribution in the 9-direction is in fact equal to the convolution of a distribution with bounded support with a narrow Gaussian: (i) The contraction property of this convolution operator means that it can only reduce the x" x'-divergence, and (ii) the bounded support can be used in combination with tail-bounds on Hermite polynomials (Lemma 3.6 to bound from above the contribution to the X >dvdivegee of each Hermite coefficient of our distribution (Lemma 2.6). These additional constraints necessitate a modification to the moment-mauee momment-atching problem, but it can still be readily analyzed (Theorem 2.5).
The second and more complicated issue involves the fraction of outliers, i.c., the parameter "1-a". Unfortunately, it is easy to see that the fraction of outliers necessary make the conditional distributions match the desired number of moments must necessarily go to 1 as [y] goes to infinity: As lyl gets bigger, the conditional distribution of inliers moves further away from (O, T) (Fact 2.3 and thus needs to be mixed more heavily with outliers to be corrected. This is significant problem, since by definition we can only afford to use (1-aa)-frcttion of outliers overall. To handle this issue, we consider a reference distribution R on (X, y) that has much heavier tails in than the distribution of inliers has. This essentially means that as yy| gets large, the conditional probability that a sample is an outlier gets larger and larger. This is balanced by having slightly lower fraction of outliers for smaller values of [y). in order to ensure that the total fraction of outliers is still at most 1-a. To address this issue, we leverage the fact that the probability that clean sample has large value of lul very small. Consequently, we can afford to make the error rates for such y quite large without increasing the overall probability of error by very much.
1.4 Preliminaries
Notation We use N to denote natural numbers and 24 denote positive integers. For Z,
denote [n] del (1..... n and use gd-1 for the d-dimensional unit sphere. We denote by ((E) the identity matrix. For random
indicator function of the event E. We use Ia to denote the variable X, we use E[X] for its expectation. For m E Z+, the m-th moment of X is defined as E|X"".. We use N(,, Σ) to denote the Gaussian distribution with mean μ and covariance matrix Σ. We let Φ denote the pdf of the one-dimensional standard Gaussian. When D is a distribution, we use X ~ D to denote that the random variable X is distributed according to D. For a vector J E IR4, we let ||=||| denote its fo-mrrm For y RR we denote by 6, the Dirac delta distribution at y, i.e., the distribution that assigns probability mass I to the single point y e R and zero elsewhere. When there is no confusion, will use the same letters for distributions and their probability density functions.
Ornstein-Uhlenbee Operator For a p > O, we define the Gaussian noise (or Oonstein-Uhlenbern operator UP the operator that maps distribution F' on R to the distribution of the random variable pX + v1 - p²Z, where X F and Z ~ NN, 1) independently of X.
Background on the SQ Model We provide the basic definitions and facts that we use.
Definition 1.7 (Search problems over distributions). Let D be set of distributions over Rd, F be a set called solutions, and Z 'D - 2 be a map that assigns sets of solutions to distributions of D. The distributional search problem Z over D and F is to find valid solution Z(D) given statistical query oracle access to an unknown D E D.
The hardness of these problems is conveniently captured by the SQ dimension. For this, we first need to define the notion of correlation between distributions.
5

---

Definition 1.8 (Pairwise Correlation). The pairwise correlation of two distributions with probability density functions D1, D2 : Ie + R2 with respect to reference distribution with density R. R
R.. where the support of R contains the supports of D1 and D2, is defined as XR D1, D2) def Jax Di (2))) dx- - 1. When Dj = D2, the pairwise correlation becomes the same as the --diieegee between Dj and R, i.e., R)) def fge (x(x)/ dx -.
Definition 1.9. For 7, B > 0, the set of distributions D = ( (Di...., ) is called (7, -o-rrrlle
relative to the distribution R if [xn( D2)1 S 7, if i # j. and (xn(D;, D2)1 S B otherwise.
The statistical dimension of a search problem is based on the largest set of (7: 9) correlltte distribu- tions assigned to each solution.
Definition 1.10 (Statistical Dimension). For 7, > O, search problem 2 over a set of solutions F and a class 'D of distributions over X, we define the statistical dimension of Z, denoted by SD 22, 7, 3). to be the largest integer m such that there exists a reference distribution R over X and a finite set of distributions DR S 'D) such that for any solution f E F, the set Dj = DR 2 (f) is
(7, cororllltt relative to R and [Dyl 2 m.
Lemma 1.11 (Corollary 3.12 in [FGR 171. Let Z be search problem over set of solutions F and
y, B > O, let s = SD(Z,7: 7: (3) be the statistical dimension of the problem. For any 7 > O, any SQ algorithm for Z requires either s /(3 - 7) queries at least one query to STAT Vv + 7²) oracle.
a class of distributions D over R4. F,
We continue by recalling the machinery from DKS17 that will be used for our construction.
Definition 1.12 (High- Hiigh-Dimensional Hidden Direction Distribution). For a unit vector v E Rd and distribution A on the real line with probability density function A(z), define PA. to be distribution over Rd, where PA., is the product distribution whose orthogonal projection onto the direction of is A, and onto the subspace perpendicular to is the standard (d- -iieennsiai normal distribution.
That is, PA (z) == A(u" r)01o(x), where Φ1 (z) = exp (-11 - (v² x)) 122 (2xx) (d-1
The distributions (PA.)) } defined above are shown to be nearly uncorrelated as long as the directions where A is embedded are pairwise nearly orthogonal.
Lemma 1.13 (Lemma 3.4 in (KSI7)) Let m E EtF Let A be a distribution over RR that agrees with the first m moments of NO, 1). For any u, let PA,o denote the distribution from Definition 1.12 For all U, u E Rd,, we have that XN (PA,e: PA.u) S lu x (O.,
The following result shows that there are exponentially many
unit vectors.
Lemma 1.14 (see, e.g., Lemma 3.7 of [DKS17). For any < c < 1/2, there is a set S, of at least 20(4)) unit vectors in Rd, such that for each pair of distinct v, o E S, it holds (wi wT'l'l S ((dd-1/2)
1.5 Prior and Related Work
Early work in robust statistics, starting with the pioneering works of Huber and Tukey [Hu664| Tuk75), pinned down the sample complexity of high-dimensional robust estimation with minority of outliers. In contrast, until relatively recently, even the most basic computational questions in this field were poorly understood. Two concurrent works [DKK* 16 [RVI6) gave the first provably robust and efficiently computable estimators for robust mean and covariance estimation. Since the dissemination of these works, there has been a flurry of activity on algorithmic robust estimation in a variety of high-dimensional settings; see [DK19 for recent survey on the topic. Notably, the robust estimators developed in [DKK + 16) are scalable in practice and yield a number of applications in exploratory
data analysis DKK 17 and adversarial machine learning [TLM18 DKK 19
The list-decodable learning setting studied in this paper was first considered in CCVI7 with focus on mean estimation. (CSV17) gave a polynomial-time algorithm with near-optimal statis- tical guarantees for list-decodable mean estimation under bounded covariance assumption on the clean. Subsequent work has led to significantly faster algorithms for the bounded covariance setting [DKK20a CMY20 20k DKK 21) and polynomial-tin algorithms with improved error guarantees under stronger distributional assumptions [DKS18 KSS18). More recently, line of work developed list-decodable learners for more challenging tasks, including linear regres- sion [KK19 RY20a] and subspace recovery [RY20b] BK21

---

2 Main Result: Proof of Theorem 1.5
In this section, we present the main result of this paper: SQ hardness of list-decodable linear regression
(Definitions 1.1 and 1.2p. We consider the setting when 3 has norm less than 1, i.e., 3 = pe for V E Sd and p E (0.1) Note that the marginal distribution of the labels is (0, oz), where of = =²= o We ensure that the labels y have unit variance by using o² = 1 -1-1p p². Specifically, the choice of parameters will be such that obtaining a p/ o/2-additive approximation of the regressor 3 is possible information-thcoreti theoretically with poly(d/o) a samples (cf. Appendix D.I)) but the complexity of any SQ algorithm for the task must necessarily be at least deoly(1/a)/oo We show the following more detailed statement of Theorem
Theorem 2.1 (SQ Lower Bound). Let c E (0, 1/2), d 24 with d 200/0122-0), a E (0,1/2) E (0, 1), o² = 1 p², and m & 24 with m I ci/va a for some sufficiently small constant C1 > O. Any list-decoding algorithm that, given statistical query access a (L-q)-cormppeed version of the distribution described by the model of Definition 1.2 with B3 pp for E Su-1, returns list L of hypotheses vectors that contains 3 such that | Bl12 S p/2, does one of the following: (i) it uses at least one query STAT (2(dd) (((d))-(mmm)) o/ ((m)) /v1 p²) (ii)
makes (2)d d- (2mmmmm))))2222))1
many queries, or (iii) it returns a list L of size 20(4))
In the rest of this section, we will explain the hard-to-learn construction for our SQ lower bound, i... a set of distributions with large statistical dimension. The proof would then follow from Lemma 1.11
We begin by describing additional notation that we will use.
Notation:
As = pu for fixed p. we will slightly abuse notation by using D (2r, y) denote
the joint distribution of the inliers and we use (x, 3) to denote the (1-a)-corruptdd version of De (z, y). To avoid using multiple subscripts, we use Da to denote the conditional distribution of X y according to the distribution D. and similarly for the other distributions. In addition, we use (g) to denote the marginal distribution of y under D, and similarly for other distributions.
Following the general construction of (KS177, we will specify a reference joint distribution R(x, y) where X and y are independent, and X (O, Ia). We will find marginal distribution R(y) and way to add the outliers so that the following hold for each E,, (where m = @(/Vaa)):
(1) E. is indeed valid distribution of (X, y) in our corruption model (i.e., can be written mixture a (1, y) + (1-aa) (x. y) for some noise distribution N,). Moreover, the marginal of E., the labels, (v). coincides with R(y).
(II) For every E R. the conditional distribution E, (arli) is of the form PAy." of Definition 1.12 with Ay being distribution that matches the first 2m moments with (0 1)
(III) For Ay defined above, Ey-niyy Ix2 (A,, NO 1))] is bounded.
We first briefly explain why construction satisfying the above properties suffices to prove our main theorem (postponing formal proof for the end of this section). We start by noting the following decomposition (proved in Appendix B).
Lemma 2.2. For u, V E Sd-1, if E, and Ey have the same marginals Rly) on the labels, they satisfy XR(a.n) (Eg v). (x, v)) Egg- [XAr(o.Ta) (xly),, Ex(ly))
Using the decomposition in Lemma 2.2 for E, and E, satisfying Property that (XR())))) (Eo y), Ea (1) I TuT 222222n 222m+1 Eyy-R(y) R(y) Ix (Ag, N (O, I)). Letting D {E.
Lemma
1.13 implies
v E S}, where S is the set of nearly uncorrelated unit vectors from Lemma 1.14 we get that D is (7, correllaat relative to R, for 6 E(yn Ix
1))] and y S d (2(mm).. As
|S| = 20(4") b is bounded, and the list size is much smaller than [S], we can show that the statistical dimension of the list-decodable linear regression is large.
Thus, in the rest of the section we focus on showing that such construction exists. We first note that according to our linear model of Definition 1.2 the conditional distribution of X given y for the inliers is Gaussian with unit variance in all but one direction (see Appendix B for proof).
I This a standard assumption and considered by existing works [KKK RY20a (cf. Remark B.4
2 We use number of moments for simplicity. The analysis would slightly differ for odd number.
7

---

Fact 2.3. Fix > O, U. E.E.S.. S and consider the regression model of Definition 1.2 with 3 = po. Then the conditional distribution Xly of the inliers is N Nyypo, p² p²vv") ), i.e. independent standard Gaussian in all directions perpendicular to and (py, 1 - p²) in the direction of v.
Since Fact 2.3 states that (xly) is already of the desired form (standard normal in all directions perpendicular to u and (yp,, 1 - p²) in the direction of v), the problem becomes one-dimensional. More specifically, for every E IR we need to find one-dimensional distribution Qy and appropriate values 0g E [o, 1] such that the mixture A, (up, 1 -²) + yQy matches the first 2m moments with (V 1). Then, multiplying by ΦLv (which denotes the contribution of the space orthogonal to v to the density of standard Gaussian, as defined in Definition [.12] yields the d-dimensional mixture distribution a D,, + (L-a,)Qy(e x س (
(z). We show that an appropriate selection of ay can ensure that this is valid distribution for our contamination model.
Lemma 2.4. Let R be a distribution on pairs (x, E Rd+1 such that ay == aDo RRy) E [o. for all y E R. Suppose that for every y E R there exists univariate distribution Qy such that Ay = ag Vo,NNuo - p²) (1 -kky 22 matches the first 2m moments with (0, 1). If the distribution
of the outliers is N₂ (1 y) = ((1 (1-0a)/OC (1-a))Qy(( (v² (x)) Properties (1) and (1I hold.
The proof of Lemma 2.4 is included in Appendix B
We will choose the reference distribution R(x, v) to have X (0, Ia] and y ~ (0, 1/a) independently, which makes the corresponding value of Oy to be at = (v) R(v) = Va expl -y- a/2)). This satisfies the condition in Lemma 2.4 that Ci E [0, 1]. Our choice of R(y) ~ NN 1/a) is informed by Properties
(II)) and will be used later on in the proofs of Theorem 2.5 and Lemma (also see the last paragraph of Section 1.3
for more intuition). Going back to our goal, i.e., making A, = (yy. 1-p²) (1 (1-ay)Q, match moments with (0, 1). we will argue that it suffices to only look for Qg of the specific form UpFy. where Up is the Ornstein- Uhlennbc-hlebbkkkkk operator. This suffices because U,S,- = (Npp, 1 p²) and the operator U, preserves the moments of distribution they match with (0., 1) (see Lemma 2.6 (i) below). Letting Ay = Up 0y + (1 - ayy) Fyy, the new goal is to show that the argument of U, matches moments with (0, 1). We show the following structural result:
For any m Z. such that S C1/ Va and B Z C2v/m, with Cn >> 0 being sufficiently small constant and C2 being a sufficiently large constant, there exists a distribution F. that satisfies the following:
Theorem 2.5. Let y E R, B E. a E (0, 1 1/2), and define 0g == fa ((exp((s²(1-a))
1. The mixture distribution 0g + (1 - 0ry) matches the first 2m moments with N(0,
2. Fy is a discrete distribution supported on at most 2m + points, all of which lie in [- B, B].
The proof of Theorem 2.5 is the bulk of the technical work of this paper and is deferred to Section 3 As mentioned before, applying Up preserves the required moment- moment-matching matching property. More crucially, allows us to bound the x² -divergence: the following result bounds x² (A,,,. 1)) using contraction properties of Ups tail bounds of Hermite polynomials, and the discreteness of Fy.
Lemma 2.6. In the setting of Theorem 2.5 let p 0 and Q2 U. Then the following holds for the mixture Ay S.NN(uP, 1 0²)
o2) Qy: (i) Ag matches the first 2m moments with (0, and (ii) x² (Ay, 1)) S (a-((11)))))) (/11/ p²) + 02 p²)-
We prove Lemma 2.6 in Appendix B
We are now ready to sketch the proof of Theorem 2.1
(see
Appendix B for the detailed proof).
Proof Sketch of Theorem 2.7 Consider the search problem 2, where D is the set of all distributions
Eg satisfying propertics (1 (II and ( (let ((v) = pv be the corresponding regressors). For each Ev, the corresponding solution set is defined to consist of all lists L of size & having one element that is (p/2)-close to 3(v). Let the subset DR = [E.eees for S being the set of nearly orthogonal vectors of Lemma 1.14. Since |uF S 0 for any distinct u, v E and d 20(1/(1/--)) for any vector w, most one element of S can be (p/2)-close to Thus, for any list L of size e = | 'DR Z (C) -1- 2 20(d"), Using Lemmas 2.2 and 1.13 along with the bbond of Lemma 2.6 we get that DR is (1, bocorellate with respect to R, for b = e06m) /(1 p²) and
? : (dd -T2m+1 12/ An application of Lemma completes the proof.
O
8

---

3 Duality for Moment Matching: Proof of Theorem 2.5
We now prove the existence of a bounded distribution Fy such that the mixture 0z0z + (1-ay) matches the first 2m moments with (V 1). The proof follows a non-constructive argument based on the duality between the space of moments and the space of non-negative polynomials.
Let B and m Z.p. Let P(m) denote the class of all polynomials p R R with degree at most m. Let (2m, B) be the class of polynomials that can be represented in either the form p(t) - a² or the form p(t) = (B² t²) <E b,t')² The intuition for (2m, B) is that every polynomial of degree at most 2m that is non-negative in [-B, B] can be written as a finite sum of polynomials from p20 B). By slightly abusing notation, for polynomial p(t) = Di=n Pit', we also use p to denote the vector in Ik consisting of the coefficients (Po...., (Pmm....PP)) The following classical result characterizes when a vector realizable as the moment sequence of distribution with support in |- B, B3] (for simplicity, we focus matching an even number of moments in the rest of this section).
Theorem 3.1 (Theorem 16.1 of (KS3)). Let B > 0, k E Z_,, and x = (Zo: 21 2..... T25) E 22++ with zo There exists a distribution with support in [-B, B] having as its first 2k moments the sequence .u.....,22. if and only if for all p E (2k, B) holds that Σ zip; 2 0.
As we require the distribution to be discrete, we prove the following result using Theorem 3.1
Proposition 3.2. Fix E R. Og E (0, 1), B > O, and m E Zz. There exists a discrete distribution Fy supported at most 2m + points in B, B) such that agoy + (1 a:y) matches the first 2m moments with /N 1) if and only if E (o.)) (o.)))()))() [p(X) 2 ayp(y) for all p P20 (2m. B).
The proof of Proposition 3.2 deferred to Appendix C.1 To prove Theorem 2.5 we need to establish
the condition of Proposition 3.2 To this end, we first need the following two technical lemmas, whose proofs are sketched towards the end of this section (for detailed proofs see Sections C.2 and
Lemma 3.3. Let m E Z4. If B Cym for some sufficiently large constant C. > then for every E Pmm), it holds that B Ex~NOaa) (X)] 2 =Ex=N(0a)XX2'000M
(X)]
Lemma 3.4. Let E R. a E (0.1/2), m E Z4, and ar ex-exp(-y2 -a)/2). Sup- pose m & C/Vo for some sufficiently small constant C > O. Then for all r E P(m),r # 0: (x))/(xx~No
& (/0,g)
Proof of Theorem
By Proposition 3.2 it remains to show that if B 2 C2ym, then the condition ayP(y) holds for all p E p2202mm B). Thus, it suffices to ensure that the following two inequalities hold for X ~ (O0 1):
2.5
Ex~N((,1)) (x)
(B2 - ,²)
sup rE
E (X))
aly
and
sup (m 1).000
E ( - X2)
<
ag
(1)
where we use Lemma 3.3 to show that B - ( > 0 for all non-zen polynomials
q P(m 1). The first expression can be bounded using Lemma 3.4 when < C1/Va.
We now focus on the second expression. By Lemma 3.3 E Ex~N B x2 (X)) 2
0.5 (B
Therefore, we have that
(B² - ---)))2())
B²
sup g g00
E Ex-1((.1) ( X2 (Xx]
sup 4mP(m-1).
E Ex~N( ( XX))
B²
(2())
sup
Ex~M (..B²
qEP 1),420 E Ex-NO.n)(((X)
where the first inequality uses that the denominator is positive and 2² 2 and the second
X²)g²(X) 2 0.5 Ex~A((01)) [ (X)] The expression inequality uses that Ex= above is of the same form as the first expression Equation (T), and thus is also bounded above by
1/a, when m S C1/ Ca/va using Lemma 3.4 This completes the proof of Theorem 2.5
L

---

Proof sketch of Lemma 3.3;
The proof of Lemma 3.3 is relatively straightforward application
of Hölder's 's inequality and the Gaussian Hypercontractvvity Theorem (stated below). For p (0, oc).
we define the Lo-norm of a random variable to be | LP = (E(I
Fact 3.5 (Gaussian Hypercontractivity [Bog98 Nel73 Let X NO0, ifp E P(d) and
then Ipx())l S (t - 1)//2 (Ip(X))l
The proof is based on Hermite Analysis (see Appendix A for more details). The normalized probabilist's Hermite polynomials, {hs i [m)] form basis of ((m) and satisfy the property Ex~AA((,,1 (I: (h) = 1(i = =j)- Since r a polynomial of degree at most m, we can represent r(z)) = >i=1 aghe(z) for some d; E R. Using orthonormality of h; under the Gaussian measure, we get that Ex Ex=~N((.1) (r)))r(())]])))))))))()) = Ei= af. By standard optimization argument, we get that the supremum of (y)) E[ (X)] is exactly > (1))). It remains to show that for every Y E R. Σi= (y) < 1/2. As m I C/Va for a small enough constant C, it suffices to show that for every E [m], (y) v O(va). As ag == (irexp(-y((1a))) the following tail bound on the Hermite polynomials can be used:
Proof sketch of Lemma 3.4;
Lemma 3.6. Let hi be the i-th normalized probabilist's Hermite polynomial. x² (2)e (((()))))
Then
maxreR (
We break our analysis in two cases:
Case 1: |y| S 1/va. Since y²y S 1, Lemma 3.6 implies that for every lul s 1/V6, ayhi(v) ex exp(- = O(va).
Case 2: |y| > 1/va. In this case, we use rather crude bounds. A direct calculation shows that
[hr(x)] S (1 |z|)". Since a (0, 1/2), we get that (v)) S exp((p=))) //// + 2i log (2)ly)))) remains show that exp(-y2/4 2i log(2ily)) have that exp(-y2/4 2i 2i
O(1) under given conditions on and y. We log i). Since |y] 2 1/ the former condition is satisfied whenever i = O(1/Va). This completes the proof sketch.
O(1) whenever lul = i(vi D(vilog
Acknowledgments
Ilas Diakonikolas is supported by NSF Award CCF-1652862 (CAREER), Sloan Research Fel- lowship, and DARPA Learning with Less Labels (LwLL) grant. Daniel M. Kane supported by NSF Award CCF-1553288 (CAREER) and Sloan Research Fellowship. Ankit Pensia is supported by NSF Award 1749857 Thanasis Pittas supported part by NSF Award DMS-2023232 (TRIPODS).
10

---

References
[AAR99] G. E. Andrews, R. Askey, and R. Roy. Special Functions, Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1999.
[BBH+20] M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm. Statistical query algorithms and low-degree tests are almost equivalent. arXiv preprint arXiv:2009.066 06000, 2020. To appear in 34th Annual Conference on Learning Theory (COLT 2021).
[BBV08] M. F. Balcan, A. Blum, and S. Vempala. A discriminative framework for clustering via similarity functions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 671-680, 2008
[BF]+ A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich. Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixve Sixth Anmual Symposium on Theory of Computing, pages 253-262, 1994.
[BK21] A. Bakshi and P. Kothari. List-decodable subspace recovery: Dimension independent eтror in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1279-1297. SIAM, 2021.
[BNJT10] M. Barreno, B. Nelson, A. D. Joseph, and J. D. Tygar. The security of machine learning. Machine Learning, (12))121-148, 2010.
[BNL12] B. Biggio, B. Nelson, and P. Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, 2012.
[Bog98] V. Bogachev. Gaussian measures. Mathematical surveys and monographs, vol. 62, 1998.
[CFJ13] T. Cai, J. Fan, and T. Jiang. Distributions of angles in random packing on spheres. Journal of Machine Learning Research, 14(():1837-1844, 2013.
[CLS20) S. Chen, J. Li, and Z. Song. Learning mixtures of linear regressions in subexponential time via fourier moments. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 587-600, 2020.
[CMY20) Y. Cherapanamjeri, S. Mohanty, and M. Yau. List decodable mean estimation in nearly linear time. 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 141-148, 2020.
[CSV17] M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. In Proceedings of STOC 2017, pages 47-60, 2017.
[DeV89] D. DeVeaux. Analysis, 8(3):227-22 November 1989.
Mixtures of linear regressions. Computational Statistics Data
[Die01] T. E. Dielman. Applied Regression Analysis for Business and Economics. Duxbury/Thomson Learning Pacific Grove, CA, 2001.
[DK19] I. Diakonikolas and M. Kane, Recent advances in algorithmic nigh-dimensional robust statistics. CoRR, abs//1911.0999 2019.
[DK20] I. Diakonikolas and D. M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In Proceedings of the 61 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), 2020.
[DKK+16] 16] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions without the computational intractability. Proceedings of FOCS 16, pages 655-664, 2016.
[DKK 17] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, pages 999-1008. 2017.
11

---

[DKK* 19] I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and A. Stewart. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, pages 1596-1606, 2019.
[DK220a] I. Diakonikolas, D. M. Kane, and D. Kongsgaard. List-decodable mean estimation via iterative multi--ilterrngg Advances in Neural Information Processing Systems, 33, 2020.
[DKK* 20b] I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. List-decodable mean estimation in nearly-pca time. CoRR, abs/201 I. 009973, 2020.
[DKK*21] I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. Clustering mixture mod- els in almost-linear time via list-decodable mean estimation. CoRR, abs/2106.08537, 2021.
[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of digh-niiensional gaussians and gaussian mixtures. In 58th IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2017, pages 73-84, 2017. Full version http://arxiv.org/bb//////e 1ttps///1111........ 1.03473.
[DKS18] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, STOC 2018, pages 1047-1060, 2018. Full version available at htpp://arxiv.org/bb//111 /ataab//711.02.1..
[DKS19] I. Diakonikolas, W. Kong, and A. Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA 2019, pages 2745-27555 2019.
[EY07] A. Eremenko and P. Yuditskii. Uniform approximation of sgn x by polynomials and entire functions. Journal d' A'Aayyys Mathématique, 101(1):313-324, 2007.
[Fel16] V. Feldman. Statistical query learning. In Encyclopedia of Algorithms, pages 2090- 2095. Springer New York, 2016.
[Fel17] V. Feldman. A general characterization of the statistical query complexity. In Proceed- ings of the 30th Conference on Learning Theory, COLT 2017, pages 785-830. PMLR, 2017.
[FGR + 17] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and lower bound for detecting planted cliques. J. ACM, 64(2):8:1-8:3) 2017.
[FGV17] V. Feldman, C. Guzman, and S. S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty- Eighth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1265-1277. SIAM, 2017.
[Gan02] M. Ganzburg. Limit theorems for polynomial approximation with hermite and freud weights. Approximation Theory X: Abstract and Classical Analysis (CK Chui, et al, eds.), pages 211-221, 2002.
[GRO8] M. I. Ganzburg and J. Rognes. Limit theorems of polynomial approximation with exponential weights. American Mathematical Soc., 2008.
[HKP+17] S. B. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer. The power of sum-of-squares for detecting hidden structures. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 720-731. IEEE Computer Society, 2017.
[Hop18] S. B. Hopkins. Statistical inference and the sum of squares method. PhD thesis, Coreell University, 2018.
[HR09] P.J. Huber and E. M. Ronchetti. Robust statistics. Wiley New York, 2009.
[HRRS86] F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust statistics. The approach based influence functions. Wiley New York, 1986.
12

---

[HS17] S. B. Hopkins and D. Steurer. Efficient bayesian estimation from few samples: Commu- nity detection and related problems. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 379-390. IEFE Computer Society, 2017.
[Hub64] P. J. Huber. Robust estimation of location parameter. Ann. Math. Statist., 35(1):73- 101, 03 1964.
[JJ94] M. Jordan and A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. Neural Computation, 6(2):181-214, 1994.
[KC20] J. Kwon and C. Caramanis. EM converges for mixture of many linear regressions. International Conference on Artificial Intelligence and Statistics, pages 1727-1736. PMLR, 2020.
[Kea98] M. J. Kearns. Efficient moise-tolerant learning from statistical queries. Journal of the CCM 4566);983-1006, 1998.
[KKK19] S. Karmalkar, A. Klivans, and P. Kothari. List-decodable linear regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, pages 7423-7432, 2019.
[Kra04] I. Krasikov. New bounds on the Hermite polynomials. arXiv preprint math/040/310, 2004.
[KS53] S. Karlin and L. S. Shapley. Geometry of moment spaces, volume 12. American Mathematical Soc., 1953.
[KSS18] P. K. Kothari, Steinhardt, and Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposiam on Theory of Computing, STOC 2018, pages 1035-1046, 2018.
[KWB19] Kunisky, A. Wein, and A. S. Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv: 1907. 11636, 2019.
[LAT+08] J. Li, D. M. Absher, H. Tang, M. Southwick, A. M. Casto, S. Ramachandran, H. M. Cann, G. S. Barsh, M. Feldman, L. L. Cavalli-Sforza, and R. M. Myers. World- wide human relationships inferred from gide patterns of variation. Science, 319: 119:1100 100-11004 2008
[LL18] Y. Li and Y. Liang. Learning mixtures of linear regressions with nearly optimal complexity. In Conference On Learning Theory, COLT 2018, pages 1125-1144. PMLR, 2018.
[LRV16] K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proceedings of FOCS'16, 16, 2016.
[McD09] J. H. McDonald. Handbook of Biological Statistics, volume 2. Sparky House Publishing. Baltimore, MD, 2009.
[MV18] M. Meister and G. Valiant. A data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 1530-1546. PMLR, 2018.
[Nel73] E. Nelson. The free markoff field. Journal of Functional Analysis, 12(2):211-227, 1973.
[O'D14] O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
[PLJD100 P. Paschou, Lewis, A. Javed, and P. Drineas. Ancestry informative markers for fine- scale individual assignment to worldwide populations. Journal of Medical Genetics, 47:835-847, 2010.
[RL87] Rousseeuw and A. M. Leroy. Robust Regression and Outlier Detection. John Wiley & Sons, Inc., New York, NY, USA, 1987.
13

---

[RPW 02) N. Rosenberg, J. Pritchard, J. Weber, H. Cann, K. Kidd, L.A. Zhivotovsky, and M. W. Feldman. Genetic structure of human populations. Science, 298:2381-23855 2002.
[RY20a] P. Raghavendra and M. Yau. List decodable learning via sum of squares. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 161- 180. SIAM, 2020.
[RY20b] P. Raghavendra and M. Yau. List decodable subspace recovery. In Conference on Learning Theory, COLT 2020, volume 125 of Proceedings of Machine Learning Research, pages 3206-3226. PMLR, 2020.
[SKL17] J. Steinhardt, P. W. Koh, and P. S. Liang. Certified defenses for data poisoning attacks. In Advances in Neural Information Processing Systems 30, pages 3520-3532, 2017.
[SVC16] J.
Steinhardt, G. Valiant, and M. Charikar. Avoiding imposters and delinquents: Adver- sarial crowdsourcing and peer prediction. In NIPS, pages
2016.
[Sze89] G. Szegö. Orthogonal Polynomials, volume XXIII of American Mathematical Society Colloquium Publications. A.M.S, Providence, 1989.
[TLM18] B. Tran, J. Li, and A. Madry. Spectral signatures in backdoor attacks. Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, pages 8011-8021, 2018.
[Tuk75] J.W. Tukey, Mathematics and picturing of data. In Proceedings of ICM, volume 6, pages 523-531, 1975.
[Va184] L. Valiant, theory of the learnable. Communications of the ACM, 27(11):113--142, 1984.
[ZJD16] K. Zhong, P. Jain, and I. S. Dhillon. Mixed linear regression with multiple components. Advances in Neural Information Processing Systems 29: Anmual Conference on Neural Information Processing Systems 2016, pages 2190-2198. 2016.
14


Reviews:
[{"review_id": "jnWitAlVmdT", "reviewer": "Reviewer_8XsW", "summary": "This paper proves a super-polynomial statistical query lower bound for the problem of of list-decodable linear regression where an adversary can corrupt a majority of the examples. Specifically, the authors show a $d^{\\text{poly}(1/\\alpha)}$ lower bound, which matches the state-of-the-art algorithmic upper bounds; this gives an evidence that the gap between the statistical and computational gap is inherent. \n\n ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is well-written, motivated, rigorous, and interesting. Despite the fact that it is quite a technical paper, the authors managed to present their ideas and results in a clear and neat way. I read most of the proofs and everything seems clean to me.\nI do not have any important comments/concerns, and therefore I am happy to recommend acceptance of this paper.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "72"}, "extra_text": {}}, {"review_id": "hAAHVevxTTq", "reviewer": "Reviewer_9Tob", "summary": "Consider the following 'robust' linear regression problem: We see samples of the form $(X,Y)$ where with probability $\\alpha$ the sample is drawn from a true linear-regression problem with Gaussian covariates (i.e., $Y = \\beta^T X + Noise$) and an arbitrary noise distribution with probability $1-\\alpha$. \n\nIn the above scenario, it is impossible to identify the unknown regressor vector $\\beta$ exactly. However, one can ask for 'list-decodable linear regression'. Several recent works studied the case where we want to identify a small set of candidate vectors (preferably of size $(1/\\alpha)^{O(1)}$) that will contain the true vector $\\beta$ (or something close to it). \n\nTwo recent works showed positive results in this direction obtaining $\\approx poly(1/\\alpha)$ list sizes but the run-time was $d^{(1/\\alpha)^{O(1)}}$. \n\nThe present paper shows that such a dependence on $\\alpha$ is in some sense necessary: For the widely studied class of SQ algorithms, one needs an oracle with tolerance at most $\\approx d^{-1/\\sqrt{\\alpha}}$. Thus suggesting that the above works are almost optimal. \n\nList-decodable linear regression is an important problem from a theoretical perspective as it is connected to many other fundamental learning problems (e.g., learning mixture models). The positive results on the problem used the powerful SoS hierarchy and while the run-time was polynomial, it wasn't really a nice polynomial. The present paper helps us partly understand why this is the case and gives some evidence that beating these would be unlikely. \n\nThe methods of the paper are quite nice and will likely find use elsewhere as well. I recommend acceptance. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Techniques: The paper builds on the main way of showing SQ lowerbounds by designing distributions that satisfy the divergence conditions as in [FGR+]. This in turn relies heavily on the conceptual idea of [DKS] who suggested coming up with distributions that look Gaussian in all but one direction and then moment match a Gaussian in one hidden direction. In most cases, if one matches $k$ moments, one gets a lower bound of roughly $d^{\\Omega(k)}$. Implementing this conceptual idea for the present scenario is not easy and the authors develop several clever ideas. For instance, one such idea is that they generate the noise distribution such that the moment matching (using noise) happens on conditional distributions $X | Y= y_0$ for various $y_0$. The authors have to cleverly trade-off the noisy fraction for larger $y_0$ so that the overall noise is small while still matching moments for large $y_0$. \n\nCouple of questions:\n1. To my understanding, the SQ lower bound (and the implied lower bound to low-degree algorithms) does not apply to the SoS algorithms of [KKK] and [RY]. While this is not a big deterrent against the present lower bound, it would be good to mention that this is the case (if it is so). \n2. For intuition, to help the readers understand the construction it might be good to say a sentence or two as to why one cannot threshold on the value of $y$ and hence work with 'better' noise rates on the small $y$ and hence identify the $\\beta$ better. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Pl-EPqXwWGH", "reviewer": "Reviewer_A5qv", "summary": "The paper the list-decodable linear regression problem, where the adversary can corrupt a fraction alpha>0.5 of the labels, and the goal is to return a list of vectors of size f(alpha) such that at least one of the vectors is close to the true regression vector. The paper proves computational-statistical tradeoffs for the problem in the statistical query (SQ) model. It shows that any SQ algorithm needs d^(poly(1/alpha)) samples to solve the problem, whereas d/alpha^3 samples are information theoretically sufficient. Therefore, the previous known algorithms for the problem are nearly optimal in the SQ model.\n\nTo prove this result, the paper leverages and builds on the machinery in DKS17. DKS17 show that it is possible to prove SQ lower bounds by showing that there exists a family of distributions whose projection onto a certain direction v matches a given number of moments of the standard Gaussian, and the distribution is a Gaussian orthogonal to v. The paper shows that it is possible to match poly(1/alpha) moments onto this direction v, which gives a d^poly(1/alpha) lower bounds using the framework of DKS17. To match these moments, the paper employs an innovative non-constructive method which uses a relation between moments of a distribution and non-negative polynomials. Several technical challenges are involved in this construction, these are briefly outlined in Section 1.3.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper is technically interesting, and employs an interesting suite of techniques to obtain the desired SQ lower bound. It is not immediately clear though if these techniques can be useful in other contexts, and at least some of the heavy lifting here is done in DKS17 and DKS19. That being said, it still appears to be a solid technical result which obtains matching lower bounds in the SQ model.\n\nI'm not convinced though that the conceptual message is so strong here. A d^2 lower bound---and probably a d^constant lower bound as well---follows from DKS17. Though the authors make some references to crowd sourcing, it is not clear if the asymptotic dependence on alpha is that important from a practical perspective at least. From the conceptual side, the authors point that the result implies that list-decodable linear regression is harder than the mixture of linear-regressions, but its not clear why the reader should find this surprising or take away from it. Maybe elaborating more on what the SQ lower bound construction achieves which moves the problem away from a mixture of linear regressions could help here. Due to all this, the conceptual message appears to be a bit limited here.\n\nThe paper is overall well-written. However, I suggest that it would be better to spend much more time on the outline in Section 1.3, and move some of the detailed proofs in the main body to the appendix. As it is, it is not easy to follow Section 1.3 without first understanding some of the later sections in at least some depth. \n\n---post author response---\n\nI thank the authors for the very detailed and concrete response to my questions and concerns. I am satisfied regarding the conceptual contribution here, and have therefore raised my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, limitations and potential negative societal impact are adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2FYb8mcOxGj", "reviewer": "Reviewer_9D9p", "summary": "This paper studies linear regression in the \"list-decodable learning\" setting.\nThe main result is a computational lower bound shows that existing algorithms are qualitatively optimal, at least among statistical query algorithms.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studies linear regression in the \"list-decodable learning\" setting.\nConcretely, the problem studied is as follows.\nOne receives samples $(X_1,y_1),\\ldots,(X_n,y_n)$ in $R^{d+1}$ with the following guarantee.\nFor some $\\alpha > 0$, some $\\alpha$-fraction of the samples was drawn according to the standard linear model: $y_i = \\beta^\\top X_i + \\eta_i$ where $\\eta_i$ is independent Gaussian noise and $\\beta$ is an unkonwn regression vector.\nThe remaining samples may be arbitrary.\n\nCrucially, $\\alpha$ may be very small -- a large majority of the samples can be corrupted.\nWhile it is information-theoretically impossible to identify $\\beta$ from such highly corrupted samples, one can actually find a list of $O(1/\\alpha)$ candidates $\\beta'$ such that there exists $\\beta'$ in the list such that $\\|\\beta - \\beta'\\|$ is small.\n\nList-decodable learning in general (for clustering, linear regression, community detection, and other problems) has been intensely studied in recent years, as it is an appealing common generalization of learning in mixture models and robust statistics. (And has additional applications, e.g. to learning with a few verified samples.)\nNotably, in many settings the complexity of list-decodable learning is no greater than the complexity of learning mixture models in the setting.\n\nThe main result in this paper is a computational lower bound for list-decodable linear regression.\nExisting efficient algorithms which find a list of size $\\poly(1/\\alpha)$ require $d^{\\poly(1/\\alpha)}$ samples and time.\n(Even though, as this paper shows, in exponential time $\\poly(d/\\alpha)$ samples suffice.)\nThis paper shows that this is in fact necessary for statistical query algorithms.\nThis is somewhat surprising, because the analogous mixtures of linear regression problem can be solved in quasipolynomial time and samples (roughly, $(d/\\alpha)^{\\poly \\log (d/\\alpha)}$, which is almost exponentially faster.\n\nThe statistical query lower bound also implies lower bounds for algorithms based on low-degree polynomials, via a known reduction.\n\nThe lower bound requires constructing a hard family of instances.\nThe construction in this paper builds on a framework established by Diakonikolas-Kane-Stewart '17, which has since been used to prove numerous SQ lower bounds for high-dimensional statistics.\nThe construction involves finding a family of distributions which fit the list-decodable linear regression model but whose moments match those of a Gaussian.\nThe main innovation here over prior applications of [DKS17] technique is that the distributions need to match a growing number of moments -- $\\poly(1/\\alpha)$.\nThe authors use LP duality to show the existence of such distributions, rather than giving an explicit construction.\n\nBy this point there are numerous SQ lower bounds for high-dimensional (robust) learning.\nThis paper stands out from the crowd in the following ways:\n-- it qualitatively settles the complexity of list-decodable regression; this was previously unstudied from a lower bounds perspective\n-- it combines LP duality with the DKS17 technique\n-- it separates the complexity of a natural list-decodable learning problem from the analogous mixture model problem.\n\nI recommend that the paper be accepted, possibly as a spotlight.\n\n(I did not carefully check mathematical details, but the construction seems reasonable.)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theory paper with limited or no direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves an SQ lower bound for the problem of list-decodable linear regression over gaussian covariates that suggests that the algorithm needs a running time of d^{poly(1/\alpha)} to solve the problem in d dimensions with \alpha fraction inliers. This matches the performance of the best-known algorithm for the problem and shows that list-decodable linear regression is likely harder than the related special case of mixed linear regression that admits a sub-exponential time algorithm (in 1/\alpha). 

In authors' ​response, it was clarified that while SQ lower bound don't apply to SoS based algorithms, the authors believe that it does apply to the specific algorithm employed in prior work on this problem. This is a somewhat non-trivial statement and was brought up in reviewer discussion -- we recommend adding formal proof of this claim to the camera-ready version. 

The authors' response also clarified that prior works on SQ lower bound only yield a fixed polynomial in d lower bound on the running time resolving the concern about the relationship to prior works on SQ lower bounds for related problems. 

The paper proves an interesting lower bound on an important problem in algorithmic robust statistics and shows an interesting "separation" between list-decodable learning and the problem of learning components of a mixture. The techniques build on and improve on the SQ lower bounds proven in prior works. We recommend acceptance. 
Decision: Accept (Spotlight)