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 = 3d 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)0(2la)) (O(1aa)
Karmalka-Kllvans-KKnn Klivans-Kothari KKK19
0(1/a) (1(1)a)(1/a)ooo))) (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 T. 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 17h. 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 211 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 5d 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 umit 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) (E, (xly),, Ex(ly))
Using the decomposition in Lemma 2.2 for E, and E, satisfying Property that (XR()))))) (Eo y), Eu (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))Q (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(z, 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:
Theorem 2.5. Let y E R, B E. a E (0, 1 1/2), and define 0g == fa ((exp((s²(1-a)) 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:
For any
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²)
-nm-l <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 |- 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.)))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 - (o--yン) r²)
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~ B x2 (X)) 2
0.5 (B
Therefore, we have that
(B² - ---)))2())
B²
sup E Ex-1((.1) ( g g00
X2 (Xx]
sup 4mP(m-1). E Ex~N( ( XX))
B²
(2())
(EP(m-1)).qE Ex~M 10.BB (0..
sup
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 E Ex~N((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)))((())]])))))))))()) = 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-iiiensional 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 1ttpb///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//111.0721..
[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
A 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: 1900.1977.110 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-1142, 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": "eB6iLLtXB0d", "reviewer": "Reviewer_iqKa", "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.\n\nThe 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.\n\nThis 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.", "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": "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.\n\nThe 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?\n\nOne 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. \n\nThat 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.\n\nMiscellaneous comments:\n- 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.\n- 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Gn8M6lJWc2i", "reviewer": "Reviewer_LQDD", "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.\n \nThe 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.\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 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.\n \nThe 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.\n \nAlthough 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.\n \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": "2"}, "extra_text": {}}, {"review_id": "7Gqe-U6gKbF", "reviewer": "Reviewer_twpW", "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:\n  - 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  - $N$ is an _arbitrary_ outlier distribution;\n  - and $\\alpha$ is thought of as a small constant.\n\nThe 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$.\n\nThe 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)}}$.\n\nThis 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.", "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 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. \n\nThe 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.\n\nOne 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?\n\nRegarding 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nOne 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.\n\nA 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}$\".\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0c8N95tJS1", "reviewer": "Reviewer_NeJG", "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.\n \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 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. \n\nEstablishing 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.\n\nIn 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.  \n\nOverall, 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. \n\nQuestion: For non-Gaussian linear regression problem, any approach to derive a similar type of SQ lower bound? Some comments would be great. \n\nUPDATE: response read. Thank you for the response!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not addressed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}]

Author rebuttal:

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)