Information-Computation Tradeoffs  for Noiseless Linear Regression with Oblivious Contamination
Authors: Ilias Diakonikolas
Chao Gao
Daniel Kane
John Lafferty
Ankit Pensia
Venue: NeurIPS 2025 poster ()
Keywords: learning theory
information computation tradeoff
robust statistics
statistical query algorithms
Primary area: theory

Abstract: We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples 
from a distribution $(x, y)$ on $\mathbb R^d \times \mathbb R$  
with $x \sim \mathcal N(0,I_d)$ and $y = x^\top \beta + z$, 
where $z$ is drawn from an unknown distribution 
that is independent of $x$. 
Moreover, $z$  satisfies $\mathbb P[z = 0] = \alpha>0$.
The goal is to accurately recover the regressor 
$\beta$ to small $\ell_2$-error. 
Ignoring computational considerations, this problem 
is known to be solvable using $O(d/\alpha)$ samples. 
On the other hand, the best known polynomial-time algorithms 
require $\Omega(d/\alpha^2)$ samples. Here we provide formal 
evidence that the quadratic dependence in $1/\alpha$ is 
inherent for efficient algorithms. Specifically, we show 
that any efficient Statistical Query algorithm
for this task requires VSTAT complexity 
at least $\tilde{\Omega}(d^{1/2}/\alpha^2)$.

Information-Computaiio Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Ilias Diakonikolas University of Wisconsin, Madison ilias@cs. eiu
Chao Gao
University of Chicago
chaogao@uchiiaago.oo edu
Daniel M. Kane
John Lafferty
University of California, San Diego dakane@ucsd.com edu
Yale University
john. laffertyyyalle.edi
Ankit Pensia"
Carnegie Mellon University
ankitp@cmu. edu
Abstract
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d. samples from distribution (ar, y) Rd R with (O, La) and y where is drawn independently of z from an unknown distribution E. Moreover, z satisfies PE [z 0] a > The goal to accurately recover the regressor small fz-error. Ignoring computational considerations, this problem is known to be solvable using (d/aa) samples. On the other hand, the best known polynomial- time algorithms require ((d/a²) samples. Here we provide formal evidence that the quadratic dependence in 1/a is inherent for efficient algorithms. Specifically, we show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least (2 2
B+2,, z,
1 Introduction
Linear regression is a prototypical supervised learning task with wide range of applications [RL87; Die01; McD09]. In the vanilla setting, we are given labeled samples (z:(i) y where the covariates 2t()) are drawn i.i.d. from distribution on IR and the labels ( are (potentially noisy) evaluations of linear function. The goal of the learner to approximately recover the hidden regression vector.
In this standard setting, linear regression is well- well-understood both statistically and computationally. Specifically, under Gaussian covariates with additive Gaussian noise, the least-squares estimator computationally efficient and statistically optimal.
In many real-world scenarios, the input data is subject to some form of contamination, e.g., er- rors due to skewed and corrupted measurements, making even simple statistical estimation tasks algorithmically challenging. In the context of linear regression, classical computationally efficient estimators inherently fail in the presence of data contamination. An important goal in this context is understand the possibilities and limitations computationally efficient estimation the presence of contaminated data.
"The majority of this work was done while author was the Simons Institute, UC Berkeley.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this work, we study the fundamental problem of linear regression with Gaussian covariates in the presence of oblivious additive contamination in the responses (see Definition 1.1). In the oblivious contamination model, an adversary is allowed to corrupt (1 a-)-frcttinn of the labels (by adding an adversarially selected value to the lahel), for some parameter a > 0, and limited in their capability by requiring the contamination be independent of the samples. Interestingly, the oblivious model ceammation-hhooreicalll
allows for consistent estimation even for a + O. This stands in contrast to the more challenging model of adversarial contamination [Hub64; DK23J, where non-trivial guarantees are impossible more than half of the labels are corrupted.
To facilitate the subsequent discussion, we define our learning task below.
Definition 1.1 (Noiseless Linear Regression with Oblivious Contamination in Responses). Let (0, 1) be the probability of inliers. Let be a univariate distribution with P2~E = 0) 2 a.
For B E TRd, we denote by Pæ. the distribution on labeled examples yx. E R x R defined as
follows:
~ (O, I2) and x 3 + Z, where Z ~ E is independent of a. T.
Given i.i.d. samples {( y:) from an unknown P3+,E, the goal is to construct an estimate such that ||3 3 22 is small.
The model of Definition 1.1 goes back to the work of Candes and Tao [CTO5]. who studied it (for more general design matrices) as classical example of error correction. It is also standard model in face recogmition [WM10], image inpainting [NT13],
data analysis [DMT07], and model repair [GI.20]. A basic result this area that the true 8 can recovered exactly, as long as the design matrix satisfies restricted isometry (therefore, for Gaussian design) and the number of nonzero entries of the noise is not too large (detailed below) [CT05; CRTV05; WM10; NT13; GI.20]. Interestingly, Candes and Tao [CT05] noted that the model can also be recast compressed sensing.
The statistical task of linear regression with Gaussian covariates under oblivious contamination has been extensively studied over the past decade [TJSO14; JTK 14; BJK 15; BJKK17; SBRJ19; PF20; DT19; dNS21]. The oblivious model has also been explored for other natural tasks, including PCA, sparse recovery [PF20: dLNNST21], and estimating a signal with additive oblivious contamina- tion [dNNS22]. While most prior work has focused on Gaussian or subgaussian design matrices, a more recent line of investigation has developed efficient estimators in the distribution setting under mild assumptions [ЗКРТ23a; DKPT23b).
Let us return to Definition 1.1 and discuss the precise quantitative aspects. Ignoring computational constraints, the sample complexity n required to obtain any non-trivial estimate of 3 for the problem of Definition 1.1 is n = d/a; in fact, n = O(d/au az) samples suffice to estimate 3 exactly. In contrast, the best known computationally efficient algorithms require sample complexity of M(d/a²) samples [GL20; dNS21]. Interestingly. known polynomial-tin samples succeed even for the (more challenging) noisy version of the estimation whske (in addition to oblivious contamination) the clean labels are perturbed by random observation noise (e.g.. Gaussian noise).
algorithms using n = Od/aa²
While noisy linear regression with oblivious contamination ((d/a²) samples, this is not the case for the noiseless version considered in this work-where. as mentioned above, (ddaa) samples suffice. This quadratic gap in 1/a between the information- theoretic optimum and the sample complexity of known polynomial-time algorithms can be significant in applications where the fraction of inliers a is small. Beyond practical considerations, given the fundamental nature of this estimation problem, it is natural to ask whether computationally efficient algorithm with (near- Joptimal sample complexity (i.e., within logarithmic factors of the optimal) exists. This leads to the central question motivating our work:
-oiinaatoo-theorrticcalll requires
Question 1.2. Does there exist constant e >> 0 so that for all d e N. e (0, 1), there exists an algorithm, using O (Polyla)) samples and running in poly(d, n) time, that computes an estimate such that | 3 2| is small?
"To be precise, in the noisy version of the problem, the labels are of the form y xT E + Z, where E (O, Definition 1.1 corresponds the important special case of 0. For the noisy case of
the information- error rate is [ 1* O(a

---

Our main result answers this question in the negative for efficient Statistical Query (SQ) algorithms broad and well-studied family of algorithms.
1.1
Main Result
To establish our negative result, we shall show that even the following (easier) testing task is computationally hard for SQ algorithms:
Testing Problem 1.3 (Testing Version of Linear Regression with Oblivious Contamination). Let > 0 be the signal strength and a E (0, 1) be the inlier probability. Let E be a (known) univariate distribution on R that assigns at least a probability to O. Let RE, be the univariate distribution of G 2, where G (0, p²) and 2 ~ E independently. The algorithm gets sample access to a distribution (z, y) ~ θ with the goal of distinguishing:
"Null": θ P. where under P: x (O,,L,) and y RE independently.
"Alternate": First a unit vector e is sampled uniformly, and then conditioned on e, θ Qu. where under Q.: ~ (O, La) and pe x + 2, where E is independent of at.
We say that an algorithm A succeeds if the failure probability of less than 1/10 under both the "null" and the "alternate".
Note that, under the null hypothesis, the features x and the responses y are independent of each other; while under the alternate hypothesis, they follow the distribution P3.E of Definition 1.1 with || estimation algorithm for the task of solve the testing problem above.
p. We show in Appendix C that a coompuatiionally-ffiiiii estimating with error p/4 suffices (computationaalyyeffiiiinn
Proposition 1.4 (Efficient Reduction of Testing to Estimation; Informal). If there exists computatioalll-efffieee algorithm to compute 3 with || 11 < p/4 with high probability, then it can be transformed into a computatioally--ffiieen algorithm for Testing Problem 1.3.
Basics on SQ Algorithms. Instead of getting sample access, SQ algorithms [Kea98; FGRVX17] interact with the underlying distribution D through the following oracle.
Definition 1.5 (VSTAT Oracle). Let D be a distribution on X. statistical query is a bounded func- tion f X' - [0, 1]. For a "simulation complexity" E N, VSTAT(m) oracle for the distribution D on the input f returns a value such that |0- ED[f] S max (1/m, / (BDls](1 Bplfi)/m//
That is, the (STAT(m)) oracle returns estimate of En with error comparable to the deviation in Bernstein's 's inequality for high-probability estimates of taking m i.i.d. samples from the Bernoulli distribution with bias [p[s]. We thus refer to m as the simulation complexity.
Statistical Query (SQ) algorithm is an algorithm whose objective is to learn some information about an unknown distribution D by making adaptive calls the corresponding VSTAT oracle. The complexity of an SQ algorithm is quantified by the total number of queries to the VSTAT oracle (viewed as measure of the algorithm's rumning time) and the maximum simulation complexity of any such query (viewed as a measure of the algorithm's 's sample complexity).
In the context of our learning problem (Definition 1.1), it is worth pointing out the following. First, there exists an inefficient SQ algorithm with small simulation complexity, which in particular can be simulated using ((da)) many i.idd samples (see Appendix D). Second, there exist efficient SQ algorithm whose simulation complexity matches the sample complexity O(d/a?) of known efficient algorithms (see Appendix E).
With this context, our main result is the following:
Theorem 1.6 (SQ Hardness of Testing Problem 1.3; informal). Consider the Testing Problem 1.3. Suppose that (i) a > Auotyloraay (i.e., the fraction of inliers is not too tiny) and (ūi) p= ((a). Then there exists a distribution E satisfying PZ-E [Z = 0) 2 a such that any SQ algorithm that solves Testing Problem 1.3 either
uses Alog' (dja)) many queries, or uses least one query VSTAT(m) = 5(Vd/o²).
3

---

Informally speaking, Theorem 1.6 shows that no SQ algorithm can solve the testing problem (and, via Proposition 1.4, the estimation problem of approximating 5*) with less than super-polynomial in many queries, unless using queries whose simulation complexity is at least ((vd/a²). That is, either the algorithm "uses" (d(v//a)) many "samples" (in the sense of simulation complexity mentioned above) or it takes super-polynomial "time" (in the sense of number of queries). We thus obtain evidence that the quadratic dependence in 1/a on the sample size is required for computationally efficient algorithms.
It is worth noting that the SQ-hard instances that we construct for the testing problem are efficiently solvable with Ō( /d) samples. We conjecture that the correct dependence on d is in fact linear (i.e.. an (2(d/o 2 lower bound on the computational sample complexity). This is left as an interesting question for future work (see Section 4).
Finally, while the focus of this work is the SQ model, SQ-hardness results typically translate to quantitatively similar hardness for low-degree polynomial tests [Hop18; ;; KWB19], via the work of [BBHLS21]. While we do not establish formal theorem in this regard, we believe that our SQ-hard instances are also hard for low-degree polynomials.
1.2 Overview of Techniques
We wish to show that it is hard to solve Testing Problem 1.3 with fewer than vdl p samples (we will ultimately set = @(a)). The first question we face is to make a judicious choice of the contamination distribution E that (I) satisfies our noise model, namely Pz~E(Z = 0) 2 a: and (II) it is SQ-hard to distinguish the null and alternate hypotheses.
Choice of Contamination Distribution: Intuition. A natural first step to consider is what happens if we select the contamination distribution E to be the standard Gaussian, i.e., E = NN 1). In this case, the testing task corresponding to Testing Problem 1.3 is information-theovveiaall! impossible with of /dddppp p²) samples. Unfortunately, this choice does not fit our criterion (I), requiring that the contamination distribution must be exactly 0 with probability at least a.
Inspired from the information-theorett sample complexity lower bound for the Gaussian contam- ination setting, we instead consider a scenario where the contamination is given by distribution E, which is a discrete Gaussian with spacing (see Definition 2.9). Heuristically, the discrete Gaussian approximately matches its low-degree moments with the continuous Gaussian case. and thus, prior work [DKS17] [7] hints that it is SQ-hard to distinguish between the cases of discrete Gaus- sian and continuous Gaussian contamination. Since the case of continuous Gaussian contamination information-thhorrtticll
requires Ω 2(vd/p" samples, intuitively we are moving in the right direction. Note that the aforementioned discrete Gaussian E assigns probability (2(s) to O. Taking s = O(a), we simultancously satisfy criterion (I) above and have reasonable chance of satisfying (II).
The above is the key intuitive idea underlying our proof. However, there are a number of important technical steps required to make the analysis work towards satisfying (II).
Discrete Noise and Non-Gaussian Component Analysis. For a unit vector v, let Qu be the distribution over (x., y) such that y = pv x + Z, where Z ~ E independently of x and E is the suitable discrete Gaussian distribution. Let P be the distribution over (æ, y) corresponding to the null hypothesis, namely x and y are independent with correct marginals (i.e., x ~ (0, La) and y p²G + Z, where G ~ N(0, 1) and Z ~ E are independent). We wish to show that it is hQ-hard to distinguish between Qu. for random v, and P. Note that conditioning on the value of y. Qu is a standard Gaussian in the directions orthogonal to v and is given by some known distribution, Ag. in the v-direction. This means that the testing problem we are considering is effectively a conditional Non-Gaussian Component Analysis (NGCA) problem (Testing Problem 2.8). Unfortunately, there are several technical obstacles preventing us from applying existing tools [DKS17; DKS19].
The first technical hurdle arises from the fact that Ay is a discrete distribution, and in particular has infinite chi-squared norm with respect to the standard Gaussian. In particular, this means that the standard SQ-dinension related techniques for proving lower bounds will not work here. Instead, we need leverage and adapt the recent work of [DKRS23] that directly uses Gaussian Fourier analysis to establish SQ lower bounds even when the chi-squared distance is infinite. Unfortunately, the latter

---

work [DKRS23] does not give SQ-lower bounds for conditional Non-Gaussian Component Analysis tasks (as the one we are dealing with here). Consequently, we will require careful adaptation of their techniques in our context.
Connection with Continuous Gaussian Contamination. A key requirement for the Gaussian Fourier analysis to go through in [DKRS23] is that Ay 's have well-behaved moments. Unfortunately, an additional technical challenge arising in our context is that directly bounding the relevant moments of Ay (which belongs the family of discrete Gaussians) is challenging.
Instead, for the purpose of the analysis, we again leverage the connection with continuous Gaussian contamination. Specifically, we choose By to be continuous Gaussian counterpart of the discrete Gaussian Ay. Let the resulting distribution on (zz y) be T. (which is continuous counterpart of Q+). Note that this is again an instance of conditional NGCA. Since the B, 's are now (continuous) Gaus- sians (and hence satisfy many desirable properties, e.g., continuity), it can be shown that if v and w are nearly orthogonal vectors, T, and T., will have small chi-squared inner product with respect P.
Hardness of Continuous Noise Contamination. The fact that two random unit vectors have small inner product with high probability can be used to show that the task of testing between P and {To) w4- has large SQ dimension. This implies SQ-hardness of this basic testing problem. In fact, it will imply the more powerful result that for any bounded function S. with high probability over v, the expectations Er, [/] and [f[ cannot be distinguished by (oTA)()( query for mo == vd/(p² log* d); see Proposition 3.6.
Quantitative Relationship between Diserete and Continuous Gaussian Noise. We now return to the challenge of computing moments of discrete Gaussians Ag (for performing Gaussian Fourier analysis). We resolve this issue by comparing these moments to the moments of By. As A, will be a discrete version of the Gaussian By, this relationship will be relatively manageable to prove. We then combine this ingredient with techniques involving Hermite analysis from [DKRS23] show the following: for any bounded test function f. with high probability over the choice of a random v, it holds that [f] Er. [f]] is tiny (inverse super-poly apper-polynomiall in mq) as long as < polylog(d) (Theorem 3.7).
Putting Everything Together. Combining the above, we obtain the following: for any f. with high probability over random v, it holds that (i) [Eq, [f] - Er. [f]] is inverse super-por syper-polynomially small in mg, and (ii) |E, [ʃ] - Er [f] is smaller than the threshold for ( Therefore, by a union bound and triangle inequality, it follows that with high probability EE,, [s] [r[s]] is also
smaller than the threshold for (oTA)))(m))). implying SQ-hardness (Proposition 2.6).
1.3 Related Work
Our work is broadly situated in the field of robust statistics, which has a long history dating back to Huber and Tukey [Hub64; Tuk60J. Robust statistics aims to design estimators that are tolerant to data contamination. Focusing on high-dimensional data, our work studies the statistical and computational aspects of robust estimation, which has seen flurry of work in the last decade since [DKKLMS16; LRV 16]; see [DK23] for a recent book on this topic. For designing robust estimators, the choice of contamination model naturally plays crucial role. This work is part of broader effort to understand computational and statistical aspects of natural, not fully adversarial, contamination models; see, e.g., [BJK15, 15; BJKK17; 7JS19; DGT19; DK22; DKMR22; DKRS22; DKKT722; DKPT23a; DDKWZ23b; DDKWZ23a; MVBWS24: NGS24; PP24; DZ24; KG25; DIKP25].
Historically, the prototypical contamination model in robust statistics has been Huber's 's contamination model [Hub64], which was strengthened total variation distance [Hub65] and strong contamination models [DKKLMS16]. The task of linear regression under these contamination models is now well understood both statistically [CGR16] and computationally IDKS19; PJL20; DKPP23]. As mentioned earlier, it is information-theoreee -heoretically impossible to achieve consistency in these models if the proportion of contamination bounded away from zero. Thus, an important direction to under- stand the possibilities and limitations in other, less adversarial, contamination models. The oblivious adversary studied here is one such model, and indeed it does lead to consistent estimation even when the oblivious outliers constitute the majority of the observed data; see the discussion below Defini-
5

---

tion 1.1. Our work shows that while this weaker contamination model is benign from the perspective of information-theone rates, it does present surprising information compuutaoooooi tradeoff's.
2 Preliminaries
For univariate distribution E, we define R2 to be the univariate distribution of G + 2, where G ~ (O00, p²) and E independently. For two vectors v and in R use (u, w) denote the standard inner product Lie(d V,t0g A degree-k tensor in d-dimensions v is an element in (Rd))k, with entries (Vi K ((e] For vector u, we use v@k denote the k-tensor with entries l Vir- For two k-tensors v and w, we use (v, w) to denote the inner product Emp..die Vin..ri Wi..... and use ||v|]2 V(v, v). A k-tensor function F X (Rd)s* maps each x E X' to k-tensor.
Hermite Polynomials For a k N, we use h R + R to denote the k-th normalized probabilist's polynomial (which is a degree-k polynomial with definition hxx()) == Vel (-1) e² 1/2 d² -x2/2/ 2²))..
der
We shall also the k-th Hermite tensor H₃ as defined in [DKRS23, Definition 2.2].
Fourier Analysis For a distribution on a domain X, we use (2 , P) to denote the space of all functions X + R with (x)) < co. For two functions f.g E 12, P). we use (f.g) to denote the inner product Be- ([(())((())) and [|]ll to denote (J. For function f _d + R and an l E N, we define f to be the degree- Hermite approximation H&) where A := E (x)) We extend this definition to f Rd IR as follows: First, for each E IR, we define fy Rd + IR as + fxx, y) and then define (z (z.v) == (z)s that is, for each y. we perform degree- approximation of fy. We use
function (x) == Ei=o
f = ف to denote the residual.
Fact 2.1. For every function : R + 1-1. II (() - a + cc. Furthermore, for all f: 2 x R 1-1, 1] and univariate measures R. || (L. + 0 as l + oc.
We use Ω2, θ notation to hide polylog 1/a) factors. For two non-negative functions, and b we use a S b (similarly a 2 b) to say that there exists a constant (independent other problem parameters) such that Cb (respectively, 2 Cb); if a S b and Z a, then we say b.
SQ Algorithms We state the preliminaries of SQ for the following generic testing problem.
Testing Problem 2.2 (Generic Testing Problem). Let and (Qoleest- be distributions over a domain Z, which correspond to "null" and "alternate" respectively.
First sample r ~ Ber(1/2) and Sd-1 independently (unknown the statistician).
Then set θ = P ("null") if r = 0 and θ = 2. ("alternate")) otherwise.
The statistician gets (either sample/oracle) access to the distribution @ and generates I {0 using algorithm A. We say A solves the testing problem if P( T) < 0.1.
We say an SQ algorithm A solves a problem with query complexity and accuracy complexity m iteratively (potentially also adaptively and randomly) makes queries fi..... fa (each fi bounded in [0. 1] and could depend on the previous queries and their responses) on the underlying distribution (O above) VSTAT(m) oracle. An SQ lower bound is an wnffommation-theoreee
lower bound of the following form: any successful SQ algorithm A must have either 2 or m 2 mg. In the remainder of this section, we detail the technical results for proving such lower bounds.
Definition 2.3 (Pairwise Correlation). For a reference distribution P. and candidate distributions Q and Q2, the pairwise correlation between Q1 and Q₂ with respect to P is defined as Xp( (1 Q2) == Ez-p (Z)g((2) (2) 1]. where qı q-()), (-). p() denote the densities of Q1, 22, and P with respect to common measure, respectively. When Q 22, the pairwise correlation becomes the same as the diverrgeee between Q1 and P, i..., x² (Q1. P) Jz (m) p(z)
dr 1.
Statistical dimension is then defined using these pairwise correlations:
Definition 2.4 (Statistical dimension from [BBHL-S11), The statistical dimension of Testing Prob- lem 2.2 at accuracy complexity m is defined as:

---

SDA(m) == max { q E N: supe.r, (8 [Ixp(Q.. 2 -
m
where (i) v, id g independently and (ii) the inner supremum is taken over events & C
Sd-1 Sd-1 on e and r' (i.i.d. from unit sphere) that have probability at least 1 1/4².
We now define the notion of success of query f that will be useful to us:
Definition 2.5 (Success of query on distribution). We say that query f 2 [0, 1] succeeds on distinguishing 2. and P with accuracy complexity m, denoted by the event f. if e. [f())] Ep[f(Z)]I max
t min
(Va [V(mmm)
(01--)) m )) for Ep [f] and == [f.
m
We now equipped state the SQ lower bounds that will use repeatedly. Proposition 2.6 (SQ Lower Bound). Consider Testing Problem 2.2. Then
(C.I) For any query f + [0, 11. Pu-5a-1 (ff, S SDA(Tm]
(C.II) Suppose for all queries f - [0,1]. 1}, it holds that IP Pergg-- (f 4. Then any SQ algorithm A that solves Testing Problem 2.2 must use either S(q) queries in expectation or least one query as powerful as VSTAT(m +
Non-Gaussian Component Analysis form called Non-Gaussian Component Analysis (NGCA). We begin by defining High- Digee-Dimessinall Hidden Direction Distribution:
We will primarily consider Testing Problem 2.2 particular
Definition 2.7 Diigh-DDmeniional Hidden Direction Distribution). For a unit vector E R and the real line, we define P to be the distribution over Rd where pM is the product distribution whose orthogonal projection onto the direction of is H. and onto the subspace perpendicular to v is the standard (d (d-1))dimensional normal distribution. In particular, if H is continuous distribution with probability density function (pdf) H(x). then P (x) has the pdf H(v" (((ux))111 (z), where (I)(x) exp (-1|z (v x) (2/2) (d-1//2
distribution
[DKS17] established SQ lower bounds for the NGCA problem, where the null and the alternate are (O, Ia) and (P*)) powgd-i, respectively and (i) (nearly) matches many moments with A 1) and (ii) has finite x (H, 1)). For linear regression, we would need the following generalization:
Testing Problem 2.8 (Conditional NGCA). Let } lveR
k be a family of univariate distributions and R be a univariate distribution. Consider Testing Problem 2.2 over (z,z) on the domain Rd x R with
("Null") Under P: ~ NO, I2) and R independently.
("Alternate") Under Q.: y ~ R and conditioned on y = yo. X Xly 22o0
Building on [DKS17], [DKS19] showed SQ-hardness for the problem above if (i) Hy matches moments with (0, 1) for (nearly) all R and (ii) (Q. P) < co. Unfortunately, neither of these conditions holds for us, and we need more flexible and powerful tools to bypass these limitations.
Discrete Gaussian We define Discrete Gaussian distributions that central in analysis.
Definition 2.9. For a center μ E R, deviation o > 0, base f, and spacing s > 0, define the distribution DG'[p, p, a, 0. to be the positive measure over 0 + sZ that assigns mass s (f + si) for all i E Z; here, ôr. denotes the pdf of the Gaussian distribution with mean μ and standard deviation a. We use DG pr a, 0, denote the normalized probability distribution.
Discrete Gaussians behave similarly to Gaussians with respect to low-degree polynomials:
Fact 2.10 (DDKRS23, Fact C.3] and [DK22, Lemma 3.12]). For any polynomial of degree at most i and 0 R and 0, have that [Ec-,)o.,)/p((C] E. [P()) z (EGNNOOL (G) (G) (k)) exp( ((1(2(()/))))
3 Proof of Theorem 1.6
In this section, we will prove our main result Theorem 1.6. The first step is to make a judicious choice of the noise distribution E. For reasons outlined in Section 1.2, choose E to be discrete Gaussian with 2² s 1 and spacing (cventually set to ((a)).
7

---

As the second step, we note that the resulting testing problem is an instance of conditional NGCA.
Testing Problem 3.1 (NGCA with Discrete Gaussian). For y E R. define the distribution Ay :- DG D [y. o, sy) s'] with parameter values in Definition 3.2. Consider Testing Problem 2.8 with
(Marginal of y) : RE with E = DG[0, o, 0, (Conditional NGCA) For each E R, Hy is equal to Ay
We denote the corresponding null by P and the alternate for direction by Qu.
We mention the parameter choices that we shall enforce from now on:
Definition 3.2. Let signal strength & (0, Po) for sufficiently small Po 0, standard deviation
a E (0.5, 1), spacing E (0, 1) satisfy the following values:
o = / p². s' s/p S 0.001.
My := P
8y y p.
That is, for each y, the conditional distribution of the covariates in the hidden direction is discrete Gaussian with mean My (scaling linearly with y) and standard deviation o (slightly smaller than 1). While these parameters might look a bit obscure, they perfeetly resemble the typical setting of E = (10 o²). The next result, proved in Appendix B.I, shows that Testing Problem 1.3 is equivalent to Testing Problem 3.1.
Proposition 3.3. Testing Problem 3.1 is equivalent Testing Problem 1.3 when E DG [0, o, 0,
Thus, to prove Theorem 1.6, it suffices to consider Testing Problem 3.1, which is conditional NGCA instance. Since the distributions {Ay YER are (necessarily) degenerate, the lower bound machinery of SDA and pairwise correlations developed in [DKS17; DKS19] for (conditional) NGCA lead only to vacuous bounds. To bypass this degeneracy, we will instead use Proposition 2.6 (C.II) and will show that for any bounded query f : [0, 1].
P Pow-ge-i (ff [z-r[f(Z)]] "large") S "tiny",
where the notion of being "large" is according to Definition 2.5 for m = o(p² /d). However, it is unwieldy to compute (or upper bound) this probability. Hence, we first take detour to related testing problem with the more usual continuous Gaussian noise in the next section.
3.1 Conditional NGCA with Continuous Gaussian
As mentioned in the introduction, we use the similarity of discrete Gaussian with continuous Gaussian (with respect to polynomials) as analysis tool. We define the analogous testing problem with continuous Gaussian noise below.
Testing Problem 3.4. For y E IR, let By denote the distribution A (Hg, with parameters in Definition 3.2. Consider Testing Problem 2.8 with
(Marginal of y) R R5 with F. DG [G a, 8, (Conditional NGCA) For each y I, H. is equal to By.
We denote the corresponding null by P (same as 3.1) and the alternate for direction by T..
Remark 3.5. Observe that the alternate above T, does not correspond the following (Gaussian) linear model: y = po x + for æ ~ (0, Ia) and z ~ (0, o²) independently of æ. This is because the marginal of Y under the aforementioned linear model would have been Gaussian (( 1), while it is R in Testing Problem 3.4 (which is not Gaussian).
Before establishing similarity with discrete Gaussian quantitatively, we first establish that Testing Problem 3.4 is SQ-hard. In fact, we show the stronger result that the associated SDA is large.
Proposition 3.6 (SQ Hardness of Continuous Noise). Consider Testing Problem 3.4. Then for any m N and q N satisfying p² (lgg(1/)) <
m we have that SDA(m) Z 4-
Vd
Recall that R5 is the distribution of x + a for ~ NN0, p²) and ~ independent each other. "The conditional distribution of æ/y in the hidden direction would be (( o²) [DKPPS21, Fact 3.3].

---

Proof Sketch. We prove bound on SDA by calculating an analytic upper bound on the pairwise correlation (T(T,, I. Since the marginal of is identical (R) under P.T.. and Tw', the pairwise correlation is equal to El (P pel"), ]]. Since p and p. are Gaussians, there is closed-form expression (in terms of y), which we integrate out using nice properties of
As consequence, Proposition 2.6 (C.I) implies that for any f fu [0, and o( log d)
vd
IP ge- [|rT, [S] - Er[ 2 "threshold of VSTAT(m))) S d= dj
3.2 Hardness of Distinguishing Discrete and Gaussian Noise
Towards establishing (1), a natural step after proving (2) is to argue that, with high probability. [R, [f(2]] - Eq. [f(2]] is small. This is exactly what we establish in the next result, which is our main technical result:
Theorem 3.7. Suppose that (i) a >> doolstogtay and p² 2 s² log C (d/a) a large constant C > O.
log (dja))
Then for any :u - [0, 1]. it holds that P gu-g [ [f] Er, 2
Alug2
In the remainder of this section, we detail the proofs and intuition for the above result.
As first step, we do a Hermite expansion of the function as in [DKRS23], but generalized to the setting of conditional NGCA. However, for technical reasons due to the degeneracy of Ag and hence Qu we would need to perform another truncation operation.
Definition 3.8. Define Ag to be the univariate distribution Ay conditioned on (= : ||| S d) and let @ to be analogous to Qu but with Ay instead of Ag-
We now use the Hermite expansion to obtain the following result:
Proposition 3.9. Let f Rdd x R - [0, 1]. For any L < [1, (. E E N, and J f. I we have
Er. [5] [/.1[]1 S (((1.) +e -((d)
Σ
max MULL
ARN
BR EyyuR 110 Tauull
+ + 1529- Ee, 1
where Tk.y = E (on. Ak.y = Benn, (hx and BRy == (f
Since R 5 has very light tails, we can replace f with f which leads to a difference of at most P((y) 2 L.) Se -Q(L))
Proof Sketch. Sketch.
Next, we decompose f as j and f>r where the f term appears as is in (3) and can be ignored
momentarily. Then, using law of total expectation, can write E(,,,)=TQ. [fS]] F.y [E, / (x)]]- The result in [DKRS23, Lemma 3.3] implies that E p (755 = Et= AR. Su Tkw)) for Ak.y == E E [h) similar argument holds for By. Taking the difference and integrating over y, we obtain Eq. [f [ ET, [f = Ey [Ein (Ah., - BR..)) (v Tk.y)]
Since is zero for |v| 2 L, Tx,y is also zero for large y and we can take the maximum only over lvl < L. yielding (3) roughly. However, later on, would still need to control E=]f>), which could potentially be large because of degeneracy and unboundedness of Ays. Therefore, we replace Ays with y to make it bounded; using concentration of Ayss this leads to an additional e ( term. O
Thus, we crucially need to control A - BR.yl and obtain bigh-brobability estimates (over ran- domness in v) on (o Te,y' l- We begin with the former, whose proof is deferred to Appendix B.5; note that the key ingredient in proving this result is Fact 2.10.
Lemma 3.10 (Closeness of Hermite Coefficients). For any E R and l E N. we have
(Tighter for small k)) (Âk.y BR.ll & max (1, (1yl*) k00)) (e 20 ( + e -0(d))
(Tighter for larger k)) A Bk ol1)).

---

Thus, Lemma 3.10 implies that (i) for small k, the difference is inverse super-polynomially small if 2² >> s² polyyog((d) x polyyloog(d) and (ii) it stays bounded by O(1)e² for lyl -. L for any k.
We now turn to computing high-probability estimates on ( T Here, we reparameterize the arguments in [DKRS23] and obtain the following result, whose proof is deferred Appendix B.6. Proposition 3.11. Let {T N be arbitrary. Then for any ô E (0, 1), it holds with probability - over random unit vector v that
T KEN. be tensors with || S 1 for all lo E N. y E R. and let e
flog (000 1/4
od
E (0 RM TE and
Σ
Σ kSt+1
Tx>l] S d0i)) By 1100
+ (00)
_e
lox
d
The result above is applicable to our setting because for each y E Il Ilfulliz I 1, where the equality uses the orthonormality of Hermite tensors under .N It)
Σ IT
and the inequality uses that f is bounded by 1.
3.2.1 Proof sketch of Theorem 3.7
We are now ready present a proof sketch of Theorem 3.7. Combining Proposition 3.9 with Lemma 3.10 and Proposition 3.1 and the fact that |uyl < L for L 2 1, we obtain that for any E N with probability at least -dd-lo'' log"d
[r. Eq. [f] $ --(())) e-a(d) L'40'(
(6-0000-1111 e-(()) t
+ cl? (dt) (log log
1/4
+ el2
e d/polylog(d) + ET. 1 3q [F
For lolog log d, f = L and p st? the sum of the first four terms is at most O(e-L²) S do (d/a), For the last term, we show that taking é large enough suffices- -tis argument uses Fact 2.1 and the truncation of Ay as per [DKRS23]; see Appendix B.8 for details.
3.3 Proof Sketch of Theorem 1.6
Since E DG 0, 0, s). we have that Pa(2 0) Ossoo) up to normalization 1 -1/a" see Fact 2.10. Taking
@(a), we get that Pp: = 0) 2 satisfying our model. To establish SQ lower bound, it suffices to show that the probability of success of J on distinguishing Qu and P with m < ma- == ((Va/a²) accuracy complexity is at most 1/9o = d 2log d) (cf. Proposition 2.6).
Let this event be f. We now define the following events:
f,am == {w: [Q. (zx vi] - Er, (x. v)]l 2 = Theorem 3.7 implies that PPEE f. Equ" 8" f. defined analogous to &mn.m but with (i) T' instead of Q and (ii) Cm accuracy complexity as opposed to m for large constant C. Proposition 3.6 implies P(E S 240
Since E C E,v,m U. (Claim B.7), the desired result follows by a union bound.
4 Conclusions and Open Problems
In this work, we studied the fundamental problem of noiseless linear regression under Gaussian marginals with additive oblivious contamination. Our main result is an information-computatie tradeoff for SQ algorithms, suggesting that efficient learners require sample complexity at least quadratic in 1/a. where is the fraction of inliers, while linear dependence in 1/a information- theoretically suffices. An immediate open problem concerns the dependence on in the lower bound. Specifically, it is plausible conjecture that there exists lower bound of ((d/a?) the computational sample complexity of the problem (thus, exactly matching the sample complexity of known algorithms). We note that such lower bound would require new hardness construction, as our hard testing instance is efficiently solvable with (d2 (a?) samples.
10

---

Acknowledgements
ID was supported by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. CG was supported by NSF Grants ECCS-22169 222226191222 and DMS-2310769 and an Alfred Sloan fellowship. DK supported by NSF Medium Award CCF-2107547. AP supported by Research Pod on Resilience in Brain, Natural, and Algorithmic Systems at the Simons Institute, UC Berkeley.
References
[BBHLS21]
M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm. "Statistical query algorithms and low-degree tests are almost equivalent", In: Proc. 34th Annual Conference on Learning Theory (COLT). 2021.
[BJK15]
K. Bhatia, Jain, and P. Kar. "Robust Regression via Hard Thresholding". In: Advances in Neural Information Processing Systems 28 (NeurIPS). 2015, pp. 721- 729.
[BJKK17]
K. Bhatia, P. Jain, Kamalaruban, and P. Kar. "Consistent Robust Regression".
In: Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017. 2017, pp. 2107-2116.
[BLM13]
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inqqualities: A Nonasymp- totic Theory of Independence. Oxford University Press, 2013.
[CGR16]
M. Chen, C. Gao, and Z. Ren. "A General Decision Theory for Huber's SlepsilonS- Contamination Model". In: Electronic Journal of Statistics 10.2 (2016), pp. 3752- 3774.
[CRTV05]
E. Candes, M. Rudelson, T. Tao, and Vershynin. "Error correction via linear programming". In: 46th Annual IEEE Symposium on Foundations of Computer Science (5)) IEEE. 2005, pp.
[CTOS]
E. J. Candes and T. Tao. "Decoding by linear programming". In: IEEE transactions on information theory 51.12 (2005), pp. 4203-4215.
[DDKWZ23a]
I. Diakonikolas, J. Diakonikolas, D. Kane, P. Wang, and N. Zarifis. "Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise". In:
Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurIPS 2023, 2023, 2023.
[DDKW723b]
Diakonikolas, J. Diakonikolas, D. M. Kane, P. Wang, and N. Zarifis. "Information- Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise". In: The Thirty Sixth Annual Conference on Learning Theory, COLT 2023. Vol. 195. Proceedings of Machine Learning Research. PMLR, 2023, pp. 2211-2239. I. Diakonikolas, T. Gouleakis, and C. Tzamos. IDiitribution-Indeeeen Learning of Halfspaces with Massart Noise". In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019. 2019, pp. 4751-4762
[DGT19]
PAC
[Die01]
T. E. Dielman. Applied Regression Analysis for Business and Economics. Duxbury/Thomson Learning, 2001.
[DIKP25]
Diakonikolas, G. Iakovidis, D. M. Kane, and T. Pittas. "Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination". In: Proc. 42nd Inter- national Conference on Machine Learning (ICML). 2025.
[DK22]
Diakonikolas and D. M. Kane. Optimalptimal Statistical Query Hardness of Learning Halfspaces with Massart Noise". In: Proc. 35th Annual Conference
Learning Theory (COLT). 2022.
[DK23]
I. Diakonikolas and D. M. Kane. Algorithmic High- Diigh--Dmessionll Robust Statistics. Cambridge University Press, 2023.
[DKKLMS16]
Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and Stewart. "Robust Estimators in High Dimensions without the Computational Intractability". In: Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 2016. Diakonikolas, D. M. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. "Learning general halfspaces with general Massart noise under the Gaussian distribution". In: STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022. ACM, 2022, pp. 874-885.
[DKKTZ22]

---

[DKMR22]
I. Diakonikolas, D. Kane, P. Manurangsi, and L. Ren. "Cryptographic Hardness of Learning Halfspaces with Massart Noise". In: Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, 2022. 2022.
[DKPP23]
Diakonikolas, D. M. Kane, A. Pensia, and T. Pittas. "pttr-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression". In: Advances in Neural Information Processing Systems 36 (NeurlPS). 2023. I. Diakonikolas, D. M. Kane, A. Pensia, T. Pittas, and A. Stewart. "Statistical query lower bounds for list-decodable linear regression", In: Advances in Neural Information Processing Systems 34 (NeurIPS). 2021.
[DKPPS21]
[DKPT23a]
Diakonikolas, S. Karmalkar, J. Park, and C. Tzamos. DistributionnIndeeendenn Independent Regression for Generalized Linear Models with Oblivious Corruptions". In: Proc. 36th Annual Conference Learning Theory (COLT), 2023.
[DKPT236]
Diakonikolas, S. Karmalkar, Park, and C. Tzamos. "First Order Stochastic Optimization with Oblivious Noise". In: Advances in Neural Information Processing Systems 36 (NeurIPS). 2023.
[DKRS22]
Diakonikolas, D. Kane, L. Ren, and Y. Sun. "SQ Lower Bounds for Learning Single Neurons with Massart Noise". . In: Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022. 2022.
[DKRS23)
Diakonikolas, D. Kane, L.. Ren, and Y. Sun. "SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions". In: Advances in Neural Informa- tion Processing Systems 36 (NeurIPS). 2023,
[DKS17]
Diakonikolas, M. Kane, and A. Stewart. "Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures". In: Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS). 2017.
[DKS19]
Diakonikolas, W. Kong, and A. Stewart. "Efficient Algorithms and Lower Bounds for Robust Linear Regression". In: Proc. 30th Annual Symposium on Discrete Algorithms (SODA). 2019.
[dLNNST21]
T. d d'Orsi, C. H. Liu, R. Nasser, G. Novikov, D. Steurer, and S. Tiegel. "Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers". In: Advances in Neural Information Processing Systems 34 (NeurIPS). 2021.
[DMT07]
C. Dwork, F. McSherry, and K. Talwar. "The price of privacy and the limits of LP decoding" In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007, pp. 85-94.
[dNNS22]
T. d d'Orsi, Nasser, G. Novikov. and D. Steurer. "Higher degree sum-of-see -f--uurss- relaxations robust against oblivious outliers". . In: CoRR abs/2211.07332 (2022).
[dNS21]
T. d' d'Orsi, G. Novikov, and D. Steurer. "Consistent regression when oblivious outliers overwhelm". In: Proc. 38th International Conference on Machine Learning (ICML). Ed. by Marina Meila and Tong Zhang. 2021.
[DT199
A. Dalalyan and P. Thompson. "Outlier-robust estimation of sparse linear model using li-penalized Huber's 's M M-estimator". In: Advances in neural information processing systems 32 (2019).
[DZ24]
Diakonikolas and N. Zarifis. "A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise". In: Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, 2024. 2024.
[FGRVX17]
V. Feldman, E. Grigorescu, L. Reyzin, S. S. Vempala, and Y. Xiao. "Statistical Algorithms and a Lower Bound for Detecting Planted Cliques". In: Journal of the ACM 64.2 (2017).
[FGV17]
V. Feldman, C. Guzman, and S. S. Vempala. "Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization". In: Proc. 28th Annual Symposium on Discrete Algorithms (SODA). 2017.
[GL20]
C. Gao and J. Lafferty. "Model repair: Robust recovery of over par-parameterizee statistical models". In: arXiv preprint arX1v:2005.099// (2020).
12

---

[Hop18]
S. B. Hopkins. "Statistical inference and the sum of squares method". PhD thesis.
Cornell University. 2018.
[Hub64]
P. Huber. "Robust Estimation of Location Parameter". In: The Annals of Mathe-
matical Statistics 35.1 (Mar. 1964), pp. 73-101.
[Hub65]
P. J. Huber. "A Robust Version of the Probability Ratio Test". In: The Annals of Mathematical Statistics 36.6 (1965), pp. 1753-1758.
[JTK14]
P. Jain, A. Tewari, and P. Kar. "On Iterative Hard Thresholding Methods for High- Dimensional M-Estimation". In: Advances in Neural Information Processing Sys- lems 27 (NeurIPS). 2014.
[Kea98]
M. J. Kearns. "Efficient noise-tolerant Learning from Statistical Queries". In: Jour- nal of the ACM 45.6 (1998), pp. 983-1006.
[KG25]
S. Kotekal and C. Gao. "Optimal Estimation of the Null Distribution in Large-Seale Inference". In: IEEE Transactions on Information Theory (2025).
[Kra04]
Krasikov. "New Bounds on the Hermite Polynomials". In: arXiv preprint
math/0401310 (2004).
[KWB19]
D. Kunisky, A. S. Wein, and A. S. Bandeira. "Notes Computational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Likelihood Ratio", In: Mathematical Analysis, its Applications and Computation. 2019.
[LRV16]
K. A. Lai, A. B. Rao, and S. Vempala. "Agnostie Estimation of Mean and Co- variance". In: Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 2016.
[McD09]
H. McDonald. Handbook of Biological Statistics, volume 2. Sparky House Pub- lishing. Baltimore, MD, 2009.
[MVBWS24]
T. Ma. K. A. Verehand, B. Berrett, T. Wang, and R. Samworth. "Estimation beyond Missing (Completely) at Random".. In: arXiv 24/0. 10704 (2024). S. Nietert, Z. Goldfeld, and S. Shafiee. "Robust Distribution Learning with Local and Global Adversarial Corruptions (extended abstract)". In: Proc. 37th Annual Conference Learning Theory (COLT). 2024.
[NGS24]
[NT13]
N. H. Nguyen and T. Tran. "Exact Recoverability From Dense Corrupted Ob- servations via l 3-Minimmization.. In: IEEE transactions on information theory 59.4
(2013), pp. 2017-2035.
[PF20]
S. Pesme and N. Flammarion. "Online robust regression via sgd on the 11 loss". In: Advances in Neural Information Processing Systems 33 (2020), pp. 2540-2552.
[PJL20]
A. Pensia, V. Jog, and P. Loh. "Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination". In: CoRR abs/2009. 1976 (Sept. 2020).
[PP24]
A. Pensia and T. Pittas. "Optimal Robust Estimation under Local and Global Cor- ruptions: Stronger Adversary and Smaller Error". In: Proc. 38th Annual Conference on Learning Theory (COLT). 2024.
[RL87]
P. J. Roussceuw and A. M. Leroy. Robust Regression and Outlier Detection. New York, NY, USA: John Wiley & Sons, Inc., 1987.
[SBRJ19]
A. S. Suggala, K. Bhatia, P. Ravikumar, and P. Jain. "Adaptive hard thresholding for near-optimal consistent robust regression". In: Proc. 32nd Annual Conference on Learning Theory (COLT). 2019.
[TJSO14]
E. Tsakonas, J. Jaldén, N. D. Sidiropoulos, and B. Ottersten. "Convergence of the Huber Regression M-Estimate the Presence of Dense Outliers". In: IEEE Signal Processing Letters 20.10 (2014), pp. 1211-1214.
[Tuk60]
J. W. Tukey. "A survey of sampling from contaminated distributions". In: Contribu- tions to probability and statistics 2 (1960), pp. 448-485.
[Ver18]
R. Vershynin. High--Dienssionl Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018
[WM10]
J. Wright and Y. Ma. "Dense error correction via 4--minimization". In: IEEE
T Transactions Information Theory 56.7 (2010), pp. 15400-560..
[ZJS19]
B. Zhu, Jiao, and Steinhardt. "Generalized Resilience and Robust Statistics".
In: The Annals of Statistics 50.4 (2019), pp. 2256-2283.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All of the assumptions and limitations are mentioned in the main theorem.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the limitations of the SQ framework is mentioned.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
Yes, all of our assumptions and the distributional assumptions are mentioned clearly.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. wttpccccpppccccceeececceccccccct /ttp:///ggiieeeeeeeuuuubiiiiiiii /CodeSubmic ssisnnonllll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp///eerr././///e cc htw.lliic/Ehiccsuuueeeeleee
Answer: [Yes]
Justification: Yes, the research follows the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical where computational lower bounds of statistical problem studied.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No such risks exist for this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No such assets are used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No such assets are released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No such experiments are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No such experiments were conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : h/tp://ies...//eeeeeeeeee http///rrs..c//ooeeeeeeeeeeeeeee / for what should or should be described.
20

---

Supplementary Material
The Appendix is organized as follows: Appendix A contains additional preliminaries and background on SQ algorithms. Appendix B contains proofs deferred from Section 3. Appendix C gives conputationally-efiine eefficientfi reduction from testing to estimation. Appendix D gives an inefficient SQ algorithm that uses VSTAT oracle with accuracy complexity linear in whereas Appendix E gives an efficient SQ algorithm that uses VSTAT oracle with accuracy complexity quadratic in 1.
A Additional Preliminaries
We say random variable X or distribution l' is o-subgaussian if P( 2 2exp(-ct") /02) for all >> 0; here e is an absolute constant.
Fact A.1. There exists finite constant > 0 such that if X is ossubaaussian then
E
e
S
la| for |a| S ag.
Proof. We use expansion of 6 and the fact that E|JXP] S (Covp) for a o-subgaussian distribu- tion [Ver18, Proposition 2.5.2] to get
20
X
(co 22)
(Veacy/2)) 22)
Ele o- - 1| =
/eac/22
2
2i
i=1
which is of order (a) for small enough a because it then converges geometric sequence.
For completeness, provide the proof of Fact 2.1.
Fact 2.1. For every function f Rd + [11, 1], [| (L.(N(()))) - a - co. Furthermore, for
all Rd x R + [-1, 1] and univariate measures R, [12(..... 0 as l
Proof. The first statement is simple consequence of the fact that Hermite polynomials are complete orthonormal system of (IR, Ia)).
For the second statement, we shall use dominated convergence theorem. Define the residue 17(xx) = [(,,)) - fy(x)> and Je(y) = 11 (l2 Observe that Ey>x[Jr(v)) =
|| ( R)- The first statement implies that for each y E R. Je(-) - 0 co.
Furthermore, Jg is uniformly bounded by 4 as follows:
Je(y) (z) (
S 22 + 2
1 LL( S
where we Parseval's identity say |1 (1: S [1fulli Jj + pointwise as + oo and 0 < Jt I uniformly, by the dominated convergence theorem. Ey [J(() + 0 as l - 00.
and that |Syl <1. Since
A.1 Statistical Query Algorithms
Instead of getting sample access, SQ algorithms interact with the underlying distribution through an oracle. Observe that there are many ways of implementing VSTAT(m) oracle, especially when the SQ algorithm A makes multiple requires-al all we require is that each response is a valid VSTAT(m) response to each query.
Recall the notion of success from Definition 2.5. The notion of success is intimately tied to the SDA shown by the following result:
Proposition A.2 (SQ lower bounds using SDA; Proposition 2.6 (C. For any query f 2 10, 1].
the following holds: P Pu-ga-1 (E) l 3DA(7mJ
We the arguments implicit in [FGRVXI7; BBHLS2I: DKRS23].
21

---

Proof. Here, we assume that 2. has valid density with respect to P. For S and E 2, we use (2) to denote the Radon -ikkon- derivative of 2, with respect to Observe that
Ee. [f] Ep (g. f)p
Fix query f and assume that 01 Ep[f] < 1/2 otherwise apply the following arguments to f. We shall show that ((,)))))) S 1/SDA by contradiction. Suppose (( > 1/SDA(7m).
Lemma 3.5 in [FGRVX17] implies that for any m 2 1, 0 S 01, 02 S
if |a| a2 max m
min(
an (1-0a
(1 (1-aa)
then |a] -22l
ai (1-a))
m
3m
Applying this with Ep[f] and Beelfl. then if succeeds on v, then
1 fy Ky, - 1,51pl 2
6m
Taking expectation and squaring gives
((E
a1
S (Ev [. 18 - 1, f11))
6m
18 (40 - 1,5 sgn (g 1)
1Egmm (9. - (f())) sgm (g- -1. 11)
(E.
Ep
Eg [1mmm (gc - (f())) sgn (n. - 115 11)
[Ev
[Ey.,,m (go - sgn sgm
(10-) sgm
ff)
( | 1Ere. (gv - 1) sgn -1-11, L2(P)
1 a1
1srem 1pp (gx(2) - 1) (yor (2) sgn (g,-1
(g. sgn (aw 1,8
a1 Er,,r
1 1, (gu qu' 1 (g. sgm l9. 1,1 1)
1)
Teg Tey, Kg 1,90 qu - 11.1--1))mm 1)ml) -1)--)))
S 01
Dividing both sides by a₁ ((E and noting independence gives, for E Efr,. n E
En,w (00 1, qur - 11/1 8)
<
6m
Since P(E) = f,
7DA the definition of SDA implies the RHS is <
7m a contra-
1.
diction. Hence, f.,
SDA(Tm]
Proposition A.3 (Query Complexity Lower Bound; Proposition (C.II. Fix a m E N and e N.
Suppose that for all bounded queries f + 10, the probability of success small as follows:
P Pun-sa-1 (.) S
Then any (potentially randomized and adaptive to the responses of the previous queries) SQ algorithm A for solving Testing Problem 2.2 (with failure probability less than 0.25) must use either Dlg) ((SDA(7m)) queries or at least one query as powerful as VSTAT( m + 1).
Again, ideas implicit in [FGRVX17; BBHLS21; DKRS23).
Proof. We will fix the VSTAT oracle to be a deterministic oracle V defined below (independent of the algorithm A). Since the oracle is fixed, it suffices show lower bounds against deterministic algorithms.
Consider the following oracle V
22

---

If θ P, then for any query f, it returns Ep]f].
If è 2. then it answers differently based on the "niceness" of f:
- ("a good query for V on v") If Ef is a valid VSTAT(m) response, then answer Ep[f]. [f].
- (otherwise) Return [f].
Observe that the oracle V above is valid (STAT(m) oracle for all both null and all alternate.
Now, let A' be any deterministic SQ algorithm (deterministic as function of the answers of the oracle) that solves the testing problem with queries fq for q' = aq for some a < 1 to be decided soon.
Consider the case when P. Recall that the adversary returns Ep for E [g']. which is valid response. Then, the accuracy guarantee of A implies that A must output "null" on these instances (because it is deterministic)); otherwise the failure probability P( + r) 0.5.
Now, consider the alternate case where θ 2y for 8 Observe that if f.0,m holds for query f. then it is a "a good query for V on v". By assumption, the probability (over v) that any fixed query f is not good is at most Pe (E S 1/g. Thus, by a union bound, the probability (over v) that all the queries {ft] the algorithm's 's input is the same as in the null case, and hence the algorithm must answer "null". Therefore, the overall failure probability is at least 0.5(1 a) 2 0.25, which is contradiction. C
good for V is at least
When all the queries are good,
A.2 Pairwise Correlation
We will use the following closed-fome expression for the pairwise correlations between Gaussians: Lemma A.4. Let unit vectors u, E Rd and sculars a E R and 7 E (0, 1). Lel cos = u Tu. Then
a² cos ens #
cxp
+ (N (N(av, -YU0") ),NVau,, 1 yuu' )) V1 72 cos 0
Proof. For any two Gaussians A NN Ei) and B Nu E2), the average correlation with respect to the standard Gaussian can be calculated as follows:
XN((O.L)) (A, B) exp((h' h)/2)
where
(5)
/8182/512 $1,2
. A = E + + 1- 81
det(En) . det(En) . 8122 = dct(A-1)
h p1 ET
/41 + + 122 Ty= in + Dn #22
hh== = T Ay.
We will now instantiate the formula above in our context below.
(Calculating $1 and $2) $1 = $2 = 1 7 Also define = 7.
(Calculating h1) Morcover, ET1 = - vu + 6 To and Vn = (1 uu uu b--uuu
Therefore, h = 14) ΣΙ #n + ii Σx /1 = 2-
(Calculating y) The same calculations above give y Σ + Ej ab + u).
(Calculating 81,2) We begin by calculating A-1:
A Σj Eg1 = (T-vi) -w b b- bllo=" -ouT + (T -muu b-l
+ ? (vv T uu. T)
Therefore, the determinant of A is 1-92 cos? 8 for 12.. by considering 2 2 matrices: det. I
This can be seen follows
(1-7)²
a au ' [0] )))= det (litt au 0
aau 1 1+a ) (1 a)² a²(n' TnT²
au v a =
which equals the expression above.
23

---

. (Calculating A and ht) Letting U = |u; E R
and C' = alz, then
A= AI -
+
U UUUUU
= I 1-U U
a
0
a-1
0
+
[
cost
1
c
0
Ur
I - U
1 1 a
1 1 1+a
cos
1)
UT
cos 0
7--1
cos 0
I U
COS
7-1
UT
1
1
72 cos
1
0
U
720000
7
-72 cos 0)
coot)) 7
UT
72 cos 0
7
(wnT + +voT)
72 cos 0 (ou + ww ww)))
722 cos2 0
=1 7
(wu ov ) +
72 cos 0
72 cos² 0 (ou T + uv
=2co22
First, observe that (u + T))TTuu JJuu T (u + v) = (1 cos 0)² for J E fuu uu , ue0T J.
Therefore, (u + v) M(u + v) equals for M == I- A
7 cost) = 7 + cos
2(1 + cos
1- 1- coos2 0 -7-
+ 7 cos 0
Let M be I A. Then
h h= a²b yy Ay a²b-2
(u u)) (1- M) (u+ v)
27(1 + cos 0)2
aa²b- 2
2 + 2 cos 0
1 + y cos 0
(1 + cos 0)7
-2a²b + cos 0)
1 + y cos
1 + y cos ) = 2babb-1
(1 - 7)
(1 + cos 0)
2a-2 + cos 0)
(1 + 7 cos 0)
Overall, we get that 818281,2 = - 72 cos" 0 and 1/ - 20²b (1-2) cos
2a cos
1+7 cos
T+7 cos 0
A.3 Discrete Gaussian
Fact A.5 (Translation of Discrete Gaussian). For any 0 R. s > 0, M E R. o E R4,, the random variables X ~ DG jr, a, 0, s] and X' == oY + for Y ~ DG 1, 0', sy] with 0' = (6 w)/a and s' = s/a have the same law.
Proof. First the support of both X and X' are equal to 0 + sZ (indeed the support of Y is 8' + s'Z, which when multiplied by o, yields (f - 14) + sZ, and further shifting by μ yields 0 sZ.
Starting with X, for any i E P(X = 0 + si) x s + si) x _ exp(-0.5(0- + si - /o²), where we use that and a can be absorbed into the normalizing constant.
+ si /1 /02) x
Turning to the random variable X'.
PPX' = 0 si) = P(oY + = 0 si) P(Y (0- -1//o + si/a) = P(Y = 0' +
exp(-0.5(0' + +s(1)2) x exp (-0.5 ( 1 si - 11 2)
7
24

---

using the definitions of 6' and s', Since the support is equal and the two distributions are equal up to constant, they must be equal.
Fact A.6 (IDKRS23, Fact C.3] and [DK22, Lemma 3.12]). We have the following:
For any polynomial p of degree at most h and E R and & > O. we have that BG p[G]] R [0.10... (P)) S VF
()p((-(1182))
(Monomials and for the unnormalized measure) For any e N and 0: BG-N(0.1) [G*] -B [o000000..00 [V]] X k!(O(s))* exp(-x((1))))) tal mass of DG 8 is exp( exp(-(((1333)
In particular, the to-
B Proofs Deferred from Section 3
B.1 Proof of Proposition 3.3
Proposition 3.3. Testing Problem 3./ is equivalent to Testing Problem 1.3 when E = DG [0, 0,
Proof. First, by definition the distributions P under Testing Problem 1.3 and Testing Problem 3.1 are the same. For Q, we shall do the calculations explicitly.
As starting point, it is easy to that the conditional distribution of X given y under Testing Problem 1.3 is an instance of NGCA, as in Testing Problem 3.1. To see this, define x' x to be the projection of x along v, and define æ_ that x' and x are distributed as standard (multivariate) Gaussian and are independent of each other (because X (N, Ia)). Hence, the conditional distribution of given X = (a' x can be written as y = pz' + Z. implying that y is independent of r Therefore, the conditional distribution X given y yo follows like standard (multivariate) Gaussian in subspace orthogonal to Along the direction v. the distribution of X is equivalent to the conditional distribution x' given y, which we denote by Jy. Our goal is to show that Jy is equal to DG [yy 0y: s'] as in Testing Problem 3.1.
(w 2) to be its orthogonal projection. Observe
Observe that marginal distribution of Y is Gaussian mixture with countable components, given by
Y Σ (si))(si,
with w(i) = cs (2m) exp(-sa23 <xp(=)"(/((00")) where e denotes the normalization constant. Since Z is discrete over the domain sZ, the conditional distribution of X given Y yo is discrete with support (No / 8y s'Z, which is the same support as DG DG a, yyo s'). For any my in this discrete set, the conditional probability of X zo given y Yo is given by the following (where we hide multiplicative terms that do not depend on zo under the normalization constant):
P(X- = 20 X + = yo) fx PZ) = pro)
(exp(-xx//2) (w(yo prr))
eexp(
--,/ =//2) exp (- par))² )² 1//(2222))
1
2yopIr
x exp
1/
2
o²
1
2
2yopro
X exp
2
o²
1
/
3oP 2
X exp
2
X exp
20 (r)
yop) 2
X exp
(xo
pgo )
202
25

---

which is the mass assigned by DG OG(2 yy: st]; Here we repeatedly use that p² + 1.
B.2 Concentration Properties of Distributions
this section, we state the concentration properties of various distributions that appear in our analysis.
Lemma B.I. Let the parameters be as in Definition 3.2. Then we have the following:
1. The distributions Ay. Ag, and By are Olvv + -sssuauuunn and if X follows either one of these distributions, then P[[X Myl S e2
2. The distribution DG (0,o,, o, 0,8] is an (((o))suuaussicnn distribution, and R,,EE is an O
p)- subgaussian distribution.
3. The distributions PA pa., and p are O(1v + 1)ssuggaussian distributions.
Proof. We do it case-by-case.
1. For s" = s's and that 2 1:
Px~A, (1x- Myl > t)
(WW > t/o)
(Fact A.5)
X~Da (.,.(0,pp))/ss""
0 + 5")) +
s00.1 8'1)
(Fact 2.10 as s" <<
ieN
" e -0.5a 22
(a S 1)
NEN
S 1/0
8" 8
iEN
S 1202
(6)
et? This tail also implies O(yy + a- subgausssiittt as follows: we claim that P([X) > 1) z
mmxt(pggle)) Observe that it suffices to consider 2 max(Ipyl.o)) otherwise, the bound is trivially true. For >> 1pyl. P[XX > 1) < PP[ Pyl 2 4/2) and we can then use (6). The same arguments hold for By. The claim for the tails of |X] under Ay follows from that of Ay because A, obtained from conditioning on an event of probability at least 0.5.
The claim for DG (0, a, 0, s) follows from (6). For Rp.E. we use the fact that 01 and 22 are two independent σj and o2-subgaussian random variables, then their sum is O(vor + 02)- subgaussian [Ver18, 8, Proposition 2.6.1].
3. After rotating appropriately, P-Av and pB are vectors of independent coordinates and thus follow a multivariate subgaussian distribution with variance proxy bounded by the subgaussian parameter of any individual coordinate [Ver18, 8, Lemma 3.4.2]. The subgaussian proxy for the v direction is established in the first item, while for the other coordinates it is ((1).
B.3 Proof of Proposition 3.6
Proposition 3.6 (SQ Hardness of Continuous Noise). Consider Testing Problem 3.4. Then for any m N and q N satisfying p² /log(1/g) < m we have that SDA(m) Z 4-
/d
'A multivariate random vector X is termed o-subgaussian if, for all unit vectors the real-valued random variable v X is susbbaassian..
26

---

Proof. To calculate the average SQ correlation between Tn and Te', we can first calculate the average correlation between the conditional distributions and then take the average marginal over y to obtain the following expression:
X (Te,) TT.) Eug [XNCOOL (p. p (P.),
Here, we crucially used that the marginal distribution of y under P, TD and Tp is identical.
Observe that the distribution p. is equal to (ug (Ia ve ) + Using Lemma A.4 with
My Pl 7 o² = =p², and cos = To to calculate Xa
(pe", ,.))) we obtain
cos
p" cos exp
+ XV(L) (
p..y)
exp
Ity cos
1+p² ooa
V 72 cos? 0
V1
72 cos? 0
(1 + f(0) exp (g(0)²²)
and g(0) = for appropriately defined f(0) VI-pt ene2
I+ cos Therefore, the average
p² cos
correlation over E equal to
Xx(O..)) (To,Ty) = (1+ f(0)) Ey~ lexp (g(0))²) 1.
(8)
Now, observe that 1g(0)) S p² 2 & p by assumption for a sufficiently small po- Therefore, we define r(0) = By (exp (g(0))²) - 1, then Fact A.I implies that
r(0) = E [exp (g(0))²) - 1| 1/ lo(0))
Combining this with (8), we obtain
| (To, Twr
(1 + ((0) + 12 |r())
(using |r(0)] S 1)
x p² cos? + p² cos 0 - cos
(9)
where we use that p²1 cos 0 < 0.1. In particular,
x2 (
(10)
We are now ready to show that SDA(m) 2 q. for which we need to show the following:
E [Ixp (Tu, (T),Te)) <
sup E.P ((v2)))))21//
Using (9), it suffices to show that
1
sup C (ON))) E [1 o'll [8 < m
(11)
If and v' are two independent random unit vectors, then W = TT is centered ((L/VdD-subgaussi)) random variable [Ver18, Theorem 3.4.6]. For subgaussian random vari- ables, we use the simple inequality (a simple consequence of Hölder's inequality) B[[W]|E] < [[ vlog(L/P(E)) I Jaa Vlg(()() We obtain that the left hand side in (11) is less than p² (o9) vlogg) and hence (11) holds if
log 1/g)
1 m
<
(12)
Vd
which is the desired conclusion.
27

---

B.4 Proof of Proposition 3.9
Observe that Proposition 3.9 follows from the result below because of Lemma B.1. Indeed,
Lemma B.I implics that (i) Pylll 2 L) X e -a(L²) as o x and p X and (ii) for any with lul d/2, PA, (|=1 > d) S P. a, (1= Hyl
Proposition B.2. Let f: :u > [0, 1]. For L 2 1, define the set C {y: lul S Lo} and the function
= yeee Then for any & N, have that for y R.p.:
Tr [/] Bq.1011 S 4P(y + max PA. (1= d) + Eyy Σ w:ly SL
(ARy
Bryy) (O TR.y
k=
+ -B [
(13)
where TK, RE (0 Ak.y = Ba [mx((a)) and BRy = B, (f())] Ay. By defined in Testing Problems 3.1 and 3.4.
Proof. We start by replacing EQ, [f] with [5 at the cost of additive TV(Q., ((QQuQQu Qo). This to- tal variation distance is O(Pq. (Iv x| > d)), which can be upper bounded by P([vl 2 L) maxyiulss P(Jv" x 2 d). Hence, in the rest of this proof, we shall use Q everywhere.
Next we decompose f F f for f == flyyc
Then we further decompose f as f
By triangle inequality, it suffices to show that the expectations of f fizt), and f' are close. Observe that the term for fist already present in the final conclusion. Next, for f", the boundedness of f and the same marginals of Qu and Tn imply that
[Q.11" Er, [5'] (TP(Y) & C).
In the remainder, focus on the terms corresponding to f By the law of total expectation (whose validity for j justified below), we have that
E 17 (x, u)1 = E, E 2.
(14)
To compute the inner expectation, which is an instance of the unsupervised NGCA, we will use [DKRS23, Lemma 3.3]:
Lemma B.3 (Fourier Decomposition Lemma of [DKRS23]). Let A' be any distribution supported on R. and u unit vector. Then for any E N and g R + [0.
E PA (z)(())))
(z)) = Σ A @v Tk)
k=
where A& = (hx)) and Ta = (e
Consider fixed yo R and apply the above result to A' = Ago and g(x) = Fy(x) =
f(z, 90) wwec. Define A == B [hx()] and BRy Ex, B.BBBllo [hx(2)] and Tk.y (F (x))) We obtain that
3 |CC = Ey
1 [+)( = Ey
Σ And Sv The))
k==
Observe that the term k = 0 corresponds to EN (f
yo)l for each you implying that the expec-
lation of the k = 0 term (over y) is exactly EP If (x, f)}. Thus, we get the following decomposition:
E |3-9
Erl7
Ey Rv
Abu (D TEN)
(15)
28

---

Similarly, the decomposition for the continuous Gaussian noise is as follows:
Er, 1/5 (x)) - EP[[]] = Ey
Σ k=1
Bu (o Tem)
(16)
The claim follows by combining Equations (15) and (16).
Justifying (14). It suffices to show that E [1 Fubini's theorem, we have that
co, which will establish below. By
E [1/ | = Ey
xm
E
((x'HH&(')))
Hz(z))
P
Av
[| p f H H.
Ey
k=0
This can be further upper bounded by finite sum of the terms (at most (())) involving
EyE p.y | ((=')(((')))))) [p(x)]
for some polynomials p(-). Since If] is upper bounded by 1, the term above is further upper bounded
by EyE p. [Ip(x)) [] using Jensen's inequality. Using Lemma B.1, p. [Ip(=)]²] is upper
bounded by poly(1pyl.d [plle,) and since My linear in y. ([[poly(Hy)) is also finite because is sub)-subga
similar reasoning justifies (14) for T..
B.5
Proof of Lemma 3.10
Lemma 3.10 (Closeness of Hermite Coefficients). For any E R and k E N, we have
(Tighter for small k) |Ak. BRall S max (1, (uyl*) kO(k), (e -2( ()) -l(())
(Tighter for larger k) AR.. BR.Ul $ ol1))
Proof. We first consider the case for large
Large k. For large k, we shall use the fact that [xx(2)] I exp(22 /4) for all x e [Kra04].
Lemma B.1 implies that for both By and Ay.
vt: P( Mnl 2 () (xx)exx(((p""
where we that 1. Therefore, under the both X A, and X By, have that
P( > t) < ((1)) exp(O(p))) exp(-0.4t"
(17)
Indeed for f < 10ptg- the upper bound is bigger than 1 and hence holds; for t 2 10 P([ > t)
<
P[|X My1 2 0.9r) S exp(-0.41").
Therefore, upper bound El (X)] for both distributions as follows:
5 11+ / P([X) > 2//ogg u)du S 1 - Lo e -0.4--log. u
[X]][(X]]] S Ele x²
1+ /.o u u-1odu) eexp(O(12)).
$ exp(O(p)))
29

---

Smaller k. We first define Ck.y == BrnA, [x)] Since Ay is Ay conditioned on & := {2 |2| - d} and satisfies P(E) for S e--(d (see Lemma B.1), we have that for any function g:
x [g] EB, [ol S E - EB, + TB [9] + V TEA,,99)
The above inequality follows by noting that the left hand side above is exactly equal to EA, Bm, [ay() and then applying Cauchy-Schwarz, inequality. In context, the above display
rEa,
1-T + -1- 1-7
equation yields:
BRy
Ak S 2 - Ck + T|Bkyy + VF
(18)
We will now upper bound this difference. We first claim that for 0g (0, py)/o and 3 = $ /0. we have that
BRy
Ck.y EI Ex.-Noo.) My) E w' (o.1 [hx(ox' + My)l
(19)
To this, recall that BEy EgwB, hhe [x)] Ez~Niy, a2) he (z), which implies that it is equal to Ez-NNoo ba( + My). For A . the claim follows analogously from Fact A.5.
Lemma B.4. Let h E N. R.E R and s" < 1. Let G ~ N(O,1) and Y DG 0. 1, s.).
(b + aG]] - B(ha(( + at)l S max(1, (1, (b]*) max(1, |a (000)) tt.
< E| b4 + aG)l O0() max(1, b2h max(1, 2h.). (b - (kk max (24) max a2k.
Applying this result (19) with b Hy.
and s" = = 8' // a s/pa and plugging it in
(18) in combination with S e (Q()), get Lemma 3.10.
We now provide the proof of Lemma B.4
Proof. Defining the polynomial ps (z) == lb + ar), we can apply Fact 2.10 to p+(-) to conclude that the deviation in the first item is at most
/B--N (/ + (G)] exp( exp(-9(1/s²))
Hence, to establish both the first and the second items, remains to show the upper bound / V (b aG)] & kO(M) max(1, (b/²) max(1, (a]*). To that effect, we use the explicit form of the Hermite polynomials:
[R/2]]
(-1)2
hy (z) VA!
Σ
x k-2
A(k 26)! 2
t=
which gives the following ex expression:
11/211
(-1)e
(-1)²"
(b + aG)]
MIE
Σ
(b + aG)
El(h 28'! 2 (b (b+ aG)* 26'
El(k: 26)! 28
(=
There are (I:2) terms in the expression above and by linearity of the expectation, it suffices to control the maximum term above:
Elh + aG)] s k2k!
max
(b + aG)*
k- 26 aG) k-
(20)
25k/2.e5sk22
30

---

S k! max tsh
/
I k2 kt max + aG)²1
Psk
k max Ezt + 2 G
BSk
2 max 12 + a0 G2C)
max + (0 (((())))* x*)
k max(1, b²t max (1, a )².
which proves the desired result.
We now focus on the third item. Here, we again apply Fact 2.10 but this time to the polynomial pf: which would then imply that
[b + at) s (b + aG) E1 (b+ aG) exp(-
s k((h) (max(1, (1, b2h) max(1, a² + hy (b aG)
To upper bound E[ + aG)*). we can use a similar series of arguments as in (21) to get the desired result, wherein replace the use of Cauchy-Schwarz inequality with the inequality E[X, X2X S (B(x))))
We now provide the proof of Lemma B.4
Proof. Defining the polynomial pı (x) == (b + az), we can apply Fact 2.10 to p+(-) conclude that the deviation in the first item is at most
(E + aG)) exp(=s(11/2))
Hence, establish both the first and the second items, it remains to show the upper bound V /Ba-N (b aG)] & xo(k) max(1, (b/²) max(1, (a]*). To that effect, we use the explicit form of the Hermite polynomials:
[R/2]]
(-1) 2-2
hy (z) Vk!
2!(k: 26)! 2
t=0
which gives the following expression:
|k/2|1
(-1)²
(-1)²
(b + aG)]
MI
Σ
Alk 20)! 2 (b + aG) el(k 28'!! 2 (b + aG)
(=
There are ((k2) terms in the expression above. Moreover, By linearity of the expectation, it suffices to control the maximum term above:
E[h + aG)] S K
max BSK/2.P55/2
E (bb aG) 24 (b {(bb+a)))-20 aG) 26
(21)
max < k2
B((b+aG))a a
k2 kt max [b + aG)2
ESk
< k2 k! max E
2222
22r "²
ESk
22 max E. 2 + 2 (2
K
< 22 422 max tSk
2 2 + (O(vk))) (
31

---

s k max(1, b2t) max 1, a a²k),
which proves the desired result.
We now focus the third item. Here, again apply Fact 2.10 but this time the polynomial pi. which would then imply that
(b + aY) P1 s (b + aG)²1 E| h+ (b (2) exp(-
s k((h) (max(1, b²k) max(1, 2² + E hy (b (b+ aG)4))
To upper bound (b + aG)*), we can use a similar series of arguments as in (21) with the inequality E[X, Xxx,,X < I [E( instead of desired result.
inequality to get the
B.6 Proof of Proposition 3.11
Proposition 3.11. Let &TR yERR be tensors with ||Tx,ll2 S 1 for all & N, E. and let
N be arbitrary. Then any ò E (0, 1), it holds with probability 1 - over random unit vector v that
1/4 Ey E Txll z d (tlog $ ) + d01) k>1+1
Ey Σ @v Tky and
E
ge
log
d
The result for h S t follows by the claim that TRy has norm at most 1 almost surely. Hence, we will focus the second claim, for which shall crucially use the concentration results from [DKRS23], which we state in a different formulation below.
Lemma B,5 (Lemma 3.7 and Corollary 3.9 in [DKRS23]). Let Ta,y be a random k-tensor supported with randomness y. For random unit vector independent of y, let Wa denote the random variable Ey (u Tk.y'. Let W' be the random variable v. w for a unit vector w E Sd-1, Then for any even p N,
[| S (TEy (R ( Lok/s""
(22)
In particular, if (Tr.:: Te.y) S almost surely, then there exists constant C 0 Ouch that the following conclusion holds for any even E N and l E N:
1. [Wallr, 5 ((5rt)
Cpk
k/4
(useful for moderate k: o(d)
2. [Wallz, minnd, k) exp (-c kd max(d,pp)
(useful for large k: k x d)
d/v
3. [Welle, SC (pk)
(useful for extremely large k: h: w(d)
While (22) is established in [DKRS23, Lemma 3.7] for fixed tensor T. the desired follows by Jensen's inequality: for any even p and error bound g(v, y). we have that E.,, (E, y)]) S Eg(v, P] (LE, I)), where one can now use [DKRS23, Lemma 3.7].
We now couple Lemma B.5 with the simple fact that for any random variable X, with probability 1- 8, | < (1/8)///||x( for any p 2 Therefore, for any k 2 t, with probability 8/k². [W&l is less than mmin[]]Wallaaan ( Walll.) We now calculate these bounds separately for different k.
* (Small k and large p) Define x log(k//)). For any such that &s 2 and kpk S C' C'dpk. we have
Ctlog (1/8) (Cllog(188)
1/4 + exp (-c log²()/0)
This follows by considering the following two regimes separately:
32

---

k/4
(d'puk d for tiny enough constant c') In this regime, the bound decreasing in l and thus the maximum is achieved at k =
Ckpu
is
dC" 2 d'akk 2 d for large constant c') In this regime, the second bound gives the desired result by noting max(d, pyk) S C"dzk and k 2 d/pp 2 d/pp-
(Large k and = 2) Moreover, if 2 C²d, then [Wall2 S (x) Therefore, with probability 6/k², |W&l S /dd2/)(//22)222 S /d/8(d/2kkd/4
Taking union bound, we obtain the following bound that holds with probability at least 1 6,
W&l
Σ
&-IWal+
Σ
k*[
kEjL.CLd
AE(
$ (C'd)
((Plos
(1//6)
1/4
dexp (-C1og(1/3) 1og(d/5) ))
d
Σ
Valō
d
d/2
d
2k
R2Crd
The summation Σxscra expression in the sum (this can be seen by integrating J2220 x- dr for > 2), and the first expression
(dd d/2 2k
can be upper bounded by constant factor multiple of the first
at most e((( because C" large enough.
B.7 Proof of Theorem 3.7
We are now ready present the proof of Theorem 3.7.
Proof of Theorem 3.7. Combining Proposition 3.9 with Lemma 3.10 and Proposition 3.11 and the fact that |nyl < L for L 2 1, we obtain that for any t E N and l e N with probability at least
1 d log"
Br.Ifl Eq. [f] $ -0(22)
+ - (c
-2(1)) t
+ e (dt) ( (tlogt d) 1/4
+ t e eddpoolyon(d)) + Er, 1- Eq,1 17-11]-
For L= log d, t = 1 and p = sta, the sum of all but the last term is at most O L2) S d= (d/o), For the last term, we show in Appendix B.8 that taking é large enough suffices this argument uses Fact 2.1 and the truncation of A,, as per [DKRS23].
B.8 Handling fix
We now show that for any f Rd - [0, and any e (0, 1), there exists & N, depending only on (f, d, 8, L,o,,, a:) such that with 1 - 6, [Ee, [7-9] Er, [F]]] is smaller than y for a ? appropriately small.
First by Fact 2.1, we know that there exists an ((>') so that 11 (e S Sy Since (P,,,T,) is finite (as established in (10)), this implies that || - (lZ2(T,) is also sufficiently small. By Cauchy- Schwarz, we get that for every y and E 1d-1 there exists an (' d, 7) so that [E,, [7=1] $
Thus, it remains to argue about [g. By a Markov inequality, it suffices to show that E, E, < E. Bq. 11 < 788. Let D be the distribution of (æ, y) obtained over (2, as follows: first y and then d and given y under D. Thus E, El. [ < 7/8 = ED[[F>[I]. We will now show that (D, < oc,
P.A. Let Dy be the conditional distribution of
which would suffice for our result. Observe that
R (2)) (R(x) dady
2D, P):
R(y) R(y)G(x)
y n R. x
.f y
R(y) /
Dz(x)
( I.).
G(x)da
33

---

Observe that Dy is obtained from Poyy where Às supported only on {ar : |z|| E d]. [DKRS23, Lemma 3.1] implies that WD, La)) uniformly upper bounded by Oa(1). Integrating this uniform upper bound by Oa(1), we get the desired conclusion of xD, P) co.
B.9 Formal version of Theorem 1.6
We are now ready state and prove the formal version of Theorem 1.6.
Theorem B.6 (SQ Hardness of Testing Problem 1.3). Consider the testing problem in Testing Problem 1.3 with = DG 0, for 8 = a and = 1. Furthermore, assume that
. a (oolyiog(a) (i.e., it is not too tiny)
p² polyyooggdd/o and p S for sufficiently small absolute constant Pu-
Then have the following guarantees:
1. P P2(z = 0) 2 a (i.e., it is a valid instance).
2. Any SQ algorithm that solves the testing problem with probability least 2/3 either uses 9 == ddo"" (d/a) many queries or uses a single query which is as powerful as VSTAT(m) Va
for m a popoyloogd..//a)
Proof. Since a 2 1/2, we get that (z = 0) 2 (recall that P
Z-aa [0.0.0..] (z = 0) (s/o)))
which satisfies the first claim of Theorem B.6.
To establish the second claim about the SQ complexity, using Proposition 2.6, it suffices to show that the probability of success of f on distinguishing Qu and P with simulation complexity is at most 1/qu- Recall that the success event f.m.m is defined the following event:
(-. min m
[Ep (Ep(f)) Er(fl)
(Eq. (f)(1 EQ. B2.1 (23)
Q. [f]- 2 max
m
m
and our goal is to show that for any fixed bounded query f + [0, 11. we have Ponge [8r,umm] S
for g (d/oa) and 2 mo p'polylogid/aj
o² d'
We now define the following events:
First, & f.m is defined as: (f(x,)))))))) Rr, (fx, w)1l 2 .m
Next, the event 8% f.um is defined as: for a large constant C (which can be deduced from the proof of Claim B.7),
E7. [P]-E 2 max ( min (V (Bplf)(--EP) Ep(f)
(Er, [f))(1 ET, [f])
Cm
Cm
Next, we show in Claim B.7 that E,,um C E f.f.m By the union bound and Claim B.7, suffices to establish that the probabilities of these events individually is at most 2q'
(E))),)) Theorem 3.7 implies the desired bound for any m I (d)))) and I (loga))/a)
(C),v.)) oiva Taking = (d/a) and a = O(1) leads to mg x pooolylgld/aa*
This inequality was established in Proposition 3.6 for any m S mo with mo x
/d
PVloo(1/a)
This completes the proof of Theorem B.6.
We now provide the statement and the proof of Claim B.7.
34

---

Claim B.7. We have that &.eem C p,rm U U
Proof of Claim B.7. Indeed, we have that
[f (a,,ff//,,ll_--33 -
I 1B. v)] - Eog [z,,,)]]] + [Qq [z, v) Ex,
(Ep[f))(1 Ep(fl)
(Er, [f]) Er, [f])
max
min min
4m
C'n'
Cm
Cm
Observe that on E f..mm [T - Er, [f]] & for r = O(1/m²). Since the expectations are close,
standard deviations are also close: (Er, (/)(1 ET, (/]) - (Ee. (/) RQq - O(VF). Therefore, the second term above is at most
( min Cm
1
(V Ep())
(BQ. [ EQ. 111) vo(T).
max
V
Cm
Cm
Since r 2 1/m², the overall term is at most
Cm + max (cmm min (V (BElIN - Brll) (Eq. (S)( Eq. [(]
C
Cm
Cm
We now claim that this is less than the threshold for Ef,um in (23). Towards that goal, define /Eplf]- Ep[l f] and b for the corresponding term with Qu Consider the case when min(a, b)/v S 1/Cmm. Then the left hand side above is C.. which is less than the quantity in Efem, which is at least 1/m. Suppose now that min b) 2 1/(Cm). Then the term above is at most
min(a.b)
min(a.8) which is less than the quantity in &,,o, which is least min(a.d) m
VCm s
Cm
Cm
Thus, we have shown that E,r,, C E U U. f.om
C Computationally-EFficcet Reduction from Testing to Estimation
Suppose there is an algorithm A with the following guarantees: given n i.id. samples (z1, v1),..., (In, yn) in Rd x R from Definition 1.1 with inlier probability and regressor B E Rd computes an estimate 3 such that ||3 1/3- 2
Consider the following (randomized) algorithm A' that takes 2n samples S ((11,1)),... (a.) and 5' ((1), ví)...., (I vh)) and perform the following oper- ation:
Sample a random rotation matrix U e Rdxd
Let 31 the output of A on S.
Define S" == [(U21, vi),... (Ux', k())}
Let be the output of A S".
Let 32 U w.
Let W = |1 1
W > 1/9, output "alternate", otherwise output "null".
Theorem C.1. If S p/4 and d 2 log(1/8), then A' solves the testing problem in Testing Problem 1.3 with probability at least - 28.
Proof. We will argue the success probabilities separately.
35

---

Alternate Distribution Consider the case when the underlying distribution is alternate and let the latent hidden direction be v. Conditioned on v and U, the samples S and S" satisfy the conditions of Definition 1.1 with the underlying regressor 3 and UB, where / == pm; here we use that Gaussian distribution is rotationally invariant and Uæ again distributed as isotropic Gaussian.
Thus, the guarantees of A imply that with probability - 26, we have that ||3 - B|12 S T and |1.32 Bll = I| U I Since T S p/4, we have that B1 S 1.5p and the same for || Since
(3. 3B..3))((,8)) (3,3))
(31
-)-(3)
-8,,33 - B) 10-(3,3, - 3):
the closeness guarantee implies that
K (B. - (8, S 2pr 53/2/4.
Hence, with probability 1 - 26, we have that W| 2 (p² (/2/4)/ (3p/2)33 2 1/9, and hence the algorithm would correctly output "alternate".
Null Distribution We will argue that is independent of U. Indeed, for any U, the distribution of the samples in S" is i.i.d. from (0, Ia) x R. where R is the marginal distribution of y (recall that y is independent of under the null). Hence, S" and w are independent of U. Therefore, 8, Ba
distributed uniformly over the unit sphere (independent of (1). Hence, W is distributed as the product of two unit vectors, implying that with probability - 6, |W| S algorithm correctly outputs "null" for d large enough.
log(1/8) and hence the
d
D Inefficient SQ Algorithm with Correct Sample Complexity
In this section, we mention an SQ algorithm that uses q = exp(O(d/Ta)) queries from VSTAT(M) with m (11aa) and outputs an estimate 3 such that Bl12 S Furthermore, this SQ algorithm can be simulated from O [loo[1/o]] i.i.d. samples from distribution P3-
Theorem D.1. Let [1 ||2 S and a 10,1) and let the underlying distribution be P3-. for an unknown E and known a. There exists an SQ algorithm that uses q S queries to VSTAT(m)) for m 1/a and outputs estimate B such that || 1
(1/Ta)) many
Furthermore, with high probability, the (mTAT(m) oracle for this SQ algorithm can be simulated using m = (g) many i.i.d. samples from Pg..E-
Proof. Let C be r' cover of {x: |al|2 S 1} with respect the Euclidean norm for r' 0.017a. We know such a cover exists with log [C] S d dloo(117'), Furthermore, let B E C be r' close to 8 For each C, define the query fa(ø, v) 1|- poTB--lls""
The SQ algorithm as follows:
For each / E C, let Ug + VSTAT(fe,
Output 3 argmaxgec UB.
Correctness. To show correctness, we shall show that for that is 7-far from 3*, must be the case that Vgg < Ugr, which would imply that any such 3 can not be the output.
Let us start by analyzing E[ Let the distribution E be adg + E for an arbitrary distribution E", where &y is the point mass at origin. Then observe that for ~ (O0,
Eifs] aFE,, [ in T (8- + (1 - a Br. aP[(|G] < <'/11 ()) + (1 a P. (lG ||8 - 3r112 + 2| < <T)..
36

---

In particular, for 3", E[fal 2 0.5a because 11 - 8011 I r' and P(G & 1) 2 0.5. It can then
be checked maxpec 2 upr 2 Bifor] 1 m
Elsar
which is bigger than B/f if m 2 3
which is satisfied since m 2 #/4 and E|ga| 2 0.5a.
Now consider any such that ||3 3*1| =
100- /a. Then
Elfal = aP([ + (1-1l) a)) (Gr + T')
S aP[(| < + (1 a) max Pa + +21
E'ER
at' + +11 a)
$ $ 0.01a.
F < 0.02a if m ž 1/a. Therefore, any such
Therefore, for any such 3, U3 _ E[ + + 33 can not be and hence ||3 3 11 T.
Simulation with samples We implement the (STAT(m) oracle by taking set S of i..d. samples
and returning the empirical mean of qa over S. Observe that all of the queries Sa are halfspaces and hence have VC Dimension O(d). For i E (Il....,oog(//an log(L/oo)), let A₂ = {3 Elgo] E [2'a,2 2 al U
[1 2 a, 1 - 2'. Let Ao = { : E[gs] E [o, al - a, 1]}. By uniform concentration [BLMI3, Theorem 13.7] and [BLMI3, Theorem 12.5), if n 2 d / then with probability 5/J for J log(1/a), for all 3 e A, for i E NU (0), we 2
have
[Ssss]] - Ep,, x [gol
$ V (log(1/2'a) + V2
(J/()/6)
+ log(J/6)
dJ + log(J/6) Va
dJ + log(J/o)
log(J/0)
$
Bp BBp B.pr,,euu [us) 11-11111 (1--Epp-, [qs))
where we use that a + E[ffs] B[fa)) 2 a'a for all (U
By a union bound over Ar's 's. this uniform concentration holds for all E Rd. That is, if n > dJ (1/() then with probability 5, for all B E Rd, we have
Es S&] Epgr, [
dJ + log(J/0) + Va
dJ + log(J/0)
log log()/8)
$ Ep Bp llas (1 P [q=])
n
n
1
< Brg. [gs] (1
E. Fara (13))
m
if n (dJ + log(J/8))- (m + am?) m log(J/8). On this event, we get that the empirical ap- proximation is a VSTAT(m//4) oracle. Since we need m @(1aa), the required sample complexity for failure probability 6 most <lox(t//))+o(((ex(t//))
E Efficient SQ Algorithm with Matching Accuracy
We now show that there exists efficient SQ algorithm that solves Definition 1.1 and the hard instance in Theorem 1.6 with polynomially number of VSTAT(d/a²) queries. Let ( be the unknown regressor with || 2 I 1. In this section, we use as shorthand for (x.
Theorem F.1. Let a (0, 1) and 3r B, where B = {B: || S 1). For any e E (0, 1), there is an SQ algorithm that takes these a, c as input, makes poly(d) number of queries to VSTAT ( (.d on
Po- E, and (iii) computes estimate 3 Rd such that || 3r 1|2 S ea.
37

---

Observe that we do not need e to be very small to solve the hard instance of Testing Problem 1.3, i.e. can set p/a (1) and still solve Testing Problem 1.3 with polynomial number of queries (SdAT(@(d/a2)).
Proof. Define the function g(x) : + {0, } to be function such that ( = if and only if ||0||2 Z Lvd for L = polylog(d/ae) Consider the loss function ((3, u) g(z) Huber (y x 3); here Huber (.) is the Huber loss with the gradient h(z) = 2 21,1(-1,1] + (gn(2) | Consider the averaged loss [(3) = PaP (,((,, u)].
We claim the following:
1. L is k-strongly convex B for O(a).
2. C is L1 smooth (Lipschitz continuous gradient) B for L1 0(1).
3. For every 2 E 2, the function E(:, 2) is convex, and it Lo-Lipschitz for Lo S Lvd.
4. 3 is the unique minimizer of L.
Therefore, we can apply [FGV17, Corollary 4.12] with parameters Lo, L1, and x. to find an ac-close
estimate 3 such that || argmin ((8)lle S ae with O dL, Log(L (B)/e)) = d
many queries to VSTAT (o LE
d-polylog(d/a)
VSTAT
We get the desired conclusion by a't
noting that 3 uniquely minimizes C(3). We now give the details omitted earlier:
1. For any unit vector VLLu is equal to [= -xx convexity follows by non con-negativity the Huber loss.
-x ())(2z² (2) u))]. The
1 L = 22 Huber (y - ()(x ([(xTT)a]- = Eu (
E. L
2 a- N.. - uu) 20
The last
inequality follows because for some unit vector Using triangle inequality, P((1 g(x))) 2
TT (I u)²
"iellsszaaa T TT obtain that its probability is lower bounded by P[[ wigi [|
d 100 2
2. The smoothness follows from the same arguments as above by upper bounding g(x) and 2 Huber by 1.
3. Observe that the gradient satisfies v((B,2) g(x)h(y x 8) and therefore [V[[8, 2)xl|2 < Lvd, where loss is bounded by 1.
that [|>g(=)] s LL and the gradient of Huber
4. By strong convexity on B, suffices to show that 8 has zero gradient.
|V(()))) (VE](=)) 0,
where that xg(x) is symmetric random variable and independent of
38


Reviews:
[{"review_id": "g9veawgJsG", "reviewer": "Reviewer_wMTA", "summary": "The paper studies linear regression for Gaussian i.i.d features with unknown noise distribution. The problem exhibits a gap between the number of samples that are needed in theory and the number of samples that are needed by typical algorithms to work. In the fully Gaussian setting (Gaussian covariates with Gaussian noise), the problem is well understood. The paper derives a lower bound on the number of samples required by statistical query algorithms", "questions": "Section 1:\n\n- line 29 “and is limited in their capability 29 by requiring the contamination be independent of the samples” —> perhaps “is limited by the fact that” or “with the limitation that”\n- Definition 1.5. comes a little out of the blue and lines 98 - 100 are not very illuminating regarding definition. It would be much more interesting to know why the value v is important. I.e how can this value be used with respect to Testing Problem 1.3. \n- lines 111-112, you use “or” twice\n- line 111, you must add a line of explanation on the fact that the number of queries is superpolynomial in d. E.g. If you take log(d/a) = log_d(d/a)/log_d(e) you get ((d/a)^2)^(1/log_d(e)) = ((d/a)^2)^(log_e(d))\n\nSection 1.2. \n\n- lines 128 - 129, the sentence does not make any sense to me. I would rephrase like this: “In order to prove Theorem 1.6., we need to exhibit a distribution E that simultaneously satisfies (i) P(Z=0)\\geq \\alpha  and (ii) such that the AQ algorithm either uses d^… many samples or uses at least one query …”\n- line 149 “x and y are independent with correct marginals” —> What do you mean?\n- lines 151-152, Why is the distribution of (x, y) conditioned on y orthogonal to v?\n- lines 150-151, What do you mean “Q_v is a standard Gaussian in the direction orthogonal to v and is given by some known distribution A_y in the v-direction”? This is not clear. If Q_v is a standard Gaussian, why do you then say it is given by a distribution A_y?\n- lines 155 - 162 should go. They do not add anything to the clarity of the paper. Adding too much information without providing associated clear explanations does not make the paper clearer\n- Same comment for lines 163 - 166.\n- line 174, what is a large “SQ dimension”?\n- From what I understand, the key difficulties are (i)\n- liens 126 - 127, you start by mentioning distributions A_y and B_y and motivate the section as the connection between the discrete and continuous Gaussian distributions but then jumps back to Q_v and T_v without any explanation\n- lines 184, 186 you use the expression “inverse super polynomially small” why not just give the order of the bound. This would really be more clear and you would spare space. \n- The connection between the statement of Theorem 1.6. and the conclusion of section 1.2. I.e. the bound on |E_{Q_v} [f] - E_{P}[f]| is not clear. Definition 2.5 should come way earlier\n- Generally speaking, I feel that in section 1.2. \n\nSection 2\n\n- lines 198- 199: can’t you make the line shorted “we use h_k to denote ….” —> “we let h_k = 1/ \\sqrt{k} (-1)^k” —> the best way to communicate is the mathematical definition. The rest is unnecessary/redundant\n- lines 267 - 271, the definition of the Discrete Gaussian should come earlier. It should appear when you start using the term (It is actually central to the paper as indicated by the proof of Theorem 1.6). Perhaps also the definition of the NGCA.", "limitations": "see above", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Although the paper is well written I also believe that it is not yet ready for publication. You spend a lot of the time on the research you did while all that matters is the final result (see line 155 - 162 for example. All of this should go. Focus on the main result of the paper and explain this result as clearly as possible.). I think you need some more time to write the paper more clearly\n\n\nHere the crux of the paper is the construction of the distribution used in the proof of Theorem 1.6. How you build this distribution is by (1) investigating the Gaussian distribution because for this distribution you can show hardness of the detection problem then turn to the discrete Gaussian because your assumptions require the probability of 0 to be larger than alpha. From what I understand you then start from the discrete GD and try to show hardness of the detection problem for the discrete GD by relying on the mathematical tools (in particular Gaussian Fourier Analysis) developed for Non Gaussian Component Analysis and show that it is hard to distinguish between continuous and discrete Gaussian noise. Now those tools have to be adapted to your setting. If I don’t make too many mistakes, I think it would be good to have a summary of that form appear somewhere in the paper. Get rid of most of section 1.2. and replace this with a general clear sketch of the proof of Theorem 1.6. (remove all the difficulties you faced)", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. \n\nWe are grateful to the reviewer for their suggestions and typos. \n\nPlease find the answers to questions below:\n\n- Line 149: We mean that under $P$, the marginal of $X$ (respectively $y$) matches that of $X$ under $Q_v$ (respectively $y$ under $Q_v$) . But unlike $Q_v$, where $X$ and $y$ are not independent, they are independent under $P$.\n\n- Lines 151-152: We meant that the distribution of $X|y$ has the following structure (please see the proof of Proposition 3.3 for more details):\n\n  - If $u$ is orthogonal to $v$, then $u^\\top X$ (conditioned on $y$) is distributed as standard Gaussian.\n\n  - If $u$ is equal to $v$, then $u^\\top X$ (conditioned on $y$) is distributed as $A_y$.\n\nThat is, $X|y$ is an instance of High-DImensional Hidden Direction Distribution (Definition 2.7). In the notation of that definition, $X|y \\~ P_v^{A_y}$.\n\n- Line 174: We meant Definition 2.4. We will update the terminology and link the definition there."}, {"review_id": "eD8LXsD9dP", "reviewer": "Reviewer_1Aum", "summary": "This paper studies robust linear regression in the oblivious noisy model. \nNamely, we observe $y, X$ where the rows of $X$ are iid standard normal (in $d$ dimensions), and $y=X\\beta+z$ is an $n$ vector. Further the entries of $z$ are i.i.d independent of $X$, with a fraction $\\alpha$ equal to $0$. We would like to reconstruct exactly the $d$-dimensional vector $\\beta$.   \nInformation theoretically, exact reconstruction can be achieved  as soon as $n\\ge C d/\\alpha$. On the other hand, all known polytime algorithms require at least $C'd/\\alpha^2$ entries. This paper provides rigorous evidence towards an information computation gap in this model. It proves that, wthin the statistical query model, exact recovery requires either a superpolynomial number of queries or sample size at least d^{1/2}/\\alpha^2.", "questions": "The proof goes through multiple equivalent rephrasings of the same testing problems. Can this be simplified?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The problem is interesting and the result is the first one providing evidence of a gap. The proof is non-trivial.\n\nWeaknesses: The result is not optimal and implies a gap only when $\\alpha \\ll 1/\\sqrt{d}$.\nThe statistical query model has some limitations and the connection to the original problem is not as direct as one would like it to be.\nThe presentation of technical arguments is somewhat clumsy (not the argument themselves). For instance lines 81-83: Why do you write\n\"$\\Theta$ is set to $P$ wher under $P$...\".  Why not just \"Under $\\Theta$:..\". Or $\\Theta=P$ where $P$ is the distribution of:...\"\nor $..P=N(0,I_d)\\otimes R^*_{\\rho, E}...$.  The next two lines are even worse.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. We respond to their questions in more detail below:\n\n- _“Connection to the original problem is not as direct as one would like to be”_\n\n  - We point out that our SQ-hardness result also applies directly to the search version of the problem (see \\[FGRVX17, Definition 2.1] for details) without going to the testing problem. As an example, see \\[DKPPS21] who studied both the search and testing versions. \n\n  - We presented the testing problem because (i) the testing problem already captures the underlying SQ hardness while being no harder than estimation, and (ii) the connection between SQ and low-degree polynomials has been established for testing problems \\[BBHLS21].\n\n  - Please let us know if we have misunderstood your question. \n\n- _“It proves that, within the statistical query model, exact recovery requires …”_\n\n  - We would like to mention that we establish hardness not only for exact recovery, but also for weak recovery (error less than $\\rho/4$). This follows from Proposition 1.4 and Theorem 1.6. \n\n- _“The proof goes through multiple equivalent rephrasings of the same testing problems. Can this be simplified?_\n\n  - We use only one rephrasing (Proposition 3.2), which follows from a simple computation of conditional distribution. Please let us know if we may have misunderstood your point.\n\n  - If the reviewer is asking whether we could directly prove SQ hardness for discrete Gaussians without the connection with standard Gaussian, then for the reasons mentioned in Section 1.2 (related to Gaussian Fourier Analysis), it is unclear to us.\n\n- _“The result is not optimal and implies a gap only when $\\alpha \\ll 1/\\sqrt{d}$”_\n\n  - We agree with the reviewer, and we have mentioned this as a concrete open problem in the Conclusion section."}, {"review_id": "1UYAh90Q0x", "reviewer": "Reviewer_jfnB", "summary": "This paper studies the linear regression problem, where the noise is i.i.d. but sparse since it has a mass at $0$ controlled by $\\alpha$. The paper shows that the for SQ algorithms, the number of samples required is proportional to $\\frac{1}{\\alpha^2}$, which matches the scaling in $\\alpha$ for IT bounds.", "questions": "1. Why did we choose to analyze SQ algorithms instead of another class of algorithms? Is it the most likely candidate apriori to veryfiy Question 1.2? \n\n2. How sensitive are the hardness results to the precise distribution of the contamination? For example, if the contamination was not discrete Gaussian how would the number of samples change?\n\n3. Is there intution of why a discrete Gaussian was chosen instead of another distribution? Is the choice of the discrete Gaussian optimal in the sense that it gives the largest sample complexity?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well written and provides a nice review of relevant notions for a general audience. The problem is clear and the steps in the outline of the proof are well explained, so the main result is belieavable. This is done by reducing the problem to a form that allows applications of results from a series of papers by Diakonikolas et al. \n\nThe question of the sharpness of the sample complexity is very natural, and the main result provides convincing evidence on that the sample complexity bounds are indeed sharp for a class of natural algorithms. There seems to be significant differences in this problem so that it does not follow as a simple corollary of known results, and new ideas in the gradual reduction of the problem is needed.", "was_revised": true, "final_justification": "I agree with the other reviewers. This is nice work and I maintain my original positive assessment of this paper.", "rebuttal": "We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. \n\n- We analyzed the class of SQ algorithms because it is a very versatile and powerful class of algorithms. Please see \\[FGRVX17] for details. We believe that the same construction should lead to similar hardness against other classes of algorithms, such as low-degree polynomial tests (see \\[BBHLS21] for a connection to SQ algorithms) and natural Sum-of-Square formulations.\n\n- Sensitivity to the precise distribution of the contamination:\n\n  - The sample complexity requirement is understandably dependent on the choice of the noise distribution. Intuitively, if the noise is very benign (for example, if the noise is always zero), then roughly $d$ samples suffice (both information-theoretically and computationally), whereas if the noise is chosen carefully (say discrete Gaussian, as we show), then the computational sample complexity can be large. Importantly, we prove an information-computation tradeoff over the worst-case oblivious contamination, which is the standard goal in the minimax setting.\n\n  - The SQ hardness would continue to hold not only for discrete Gaussians (DG), but any distribution $E$ that is sufficiently close to DG in terms of its moments. This follows from the arguments implicit in Theorem 3.7, where we transferred SQ hardness from usual Gaussian to DG using nearly matching moments.\n\n- The choice of discrete Gaussian\n  - At a high level, we chose discrete Gaussian because of the following insights (please see Section 1.2 for more details)\n    - The case of continuous Gaussian is information-theoretically and SQ hard (but, unfortunately, is not a valid instance of our problem as it does not assign $>= \\alpha$ mass to 0), and\n    - Distinguishing between continuous Gaussian and discrete Gaussian should be SQ-hard.  \nHence, by choosing discrete Gaussian as our instance, we simultaneously satisfy the model assumption and the desired SQ \n  - Furthermore, the discrete gaussian noise is also optimal (in the sense of the largest SQ complexity) for the \\*testing\\* problem: there exists an efficient SQ algorithm that solves the testing problem (with any valid noise satisfying Definition 1.1) with only polynomially many queries to the VSTAT$(m)$ oracle for $m$ roughly $\\sqrt{d}/\\alpha^2$.  As mentioned in the conclusions section (Section 4), establishing optimality for the estimation problem is left as an interesting open problem."}, {"review_id": "8KFVQlXacA", "reviewer": "Reviewer_xzbN", "summary": "This paper studies the noiseless linear regression with oblivious contamination in the response variable. Under isotropic gaussian design, if (1-alpha) fraction of the responses is obviously corrupted, it is well known that d/alpha sample is needed to recover the regression coefficient. However all the poly time algorithms require d/alpha^2 samples. This paper proves lowerbound showing that any SQ algorithm either requires polynomial sqrt(d)/alpha^2 sample or superpolynomial time. Previous work [DKS17;DKS19] on the SQ lower bound for linear regression does not apply to the setting because the “noise” distribution has to include an alpha point mass at 0. Therefore following the work of DKRS23, a discrete gaussian distribution is used as the noise. Then the testing hardness is decomposed into two parts: 1) testing hardness between conditional gaussian 2)testing hardness between gaussian and discrete gaussian. The first part is straightforward and has been similarly proven in the prior work. Leveraging the fact that the low order Hermite moment of discrete gaussian and gaussian distribution nearly matches, they proved the second part and completed the proof.", "questions": "No", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nThe paper addresses a well known open problem and suggests that the sample complexity difference between efficient and inefficient algorithm in the noiseless linear regression with oblivious contamination is fundamental. \n\nWeakness:\nThe paper is mostly well written and easy to follow. However, I find page 8 and page 9 hard to read and the proof sketches hard to follow especially when some external lemmas are cited. I would suggest rewriting the proof sketch and potentially removing some of them.\nMost of the proof techniques are borrowed from DKRS23.", "was_revised": true, "final_justification": "There was no discussion during rebuttal and I will maintain my score of Accept.", "rebuttal": "We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. \n\nRegarding the proof sketches on Pages 8 and 9: Unfortunately the page restriction did not give us sufficient room for proper explanations of everything in the main body; we will reorganize/rephrase them better using the additional page allowed in the revised version."}]

Author rebuttal:

Meta-review: This paper establishes a new sample complexity lower bound for the problem of linear regression with outliers. While the lower bound does not exactly match the known upper bound, it helps understand the separation between noise-free and noisy regression problems. Reviewers found the paper sound and well-written, yet also raised concerns that some of key techniques have already been established in prior works. Overall, the strengths outweigh the weaknesses.
Decision: Accept (poster)