Batch List-Decodable Linear Regression via Higher Moments
Authors: Ilias Diakonikolas
Daniel Kane
Sushrut Karmalkar
Sihan Liu
Thanasis Pittas
Venue: ICML 2025 poster (2025)
Keywords: Robust Statistics;Linear Regression;Sum of Square
Primary area: theory->learning_theory
TL;DR: This paper designs an efficient algorithm based on the sum-of-square algorithm for list-decodable linear regression with batched samples.

Abstract: We study the task of list-decodable linear regression using batches, recently introduced by Das et al. 2023.. 
In this setting, we are given $m$ batches with each batch containing 
$n$ points in $\mathbb R^d$. A batch is called clean if the points it contains are i.i.d. samples from an unknown linear regression distribution. 
For a parameter $\alpha \in (0, 1/2)$, an unknown $\alpha$-fraction 
of the batches are clean and no assumptions are made on the remaining batches. 
The goal is to output a small list of vectors at least one of which is close to the true regressor vector in $\ell_2$-norm. Das et al. 2023 gave an efficient algorithm for this task, under natural distributional assumptions, 
with the following guarantee. 
Under the assumption that the batch size satisfies 
$n \geq \tilde{\Omega}(\alpha^{-1})$ and the total number of batches 
is $m = \text{poly}(d, n, 1/\alpha)$, 
their algorithm runs in polynomial time and 
outputs a list of $O(1/\alpha^2)$ vectors at least one of which 
is $\tilde{O}(\alpha^{-1/2}/\sqrt{n})$ close to the target regressor. 
Here we design a new polynomial-time algorithm 
for this task with significantly stronger guarantees under the assumption that the low-degree moments of the covariates distribution are 
Sum-of-Squares (SoS) certifiably bounded.
Specifically, for any constant $\delta>0$, as long as the batch size is 
$n \geq \Omega_{\delta}(\alpha^{-\delta})$
and the degree-$\Theta(1/\delta)$ moments of the covariates are SoS certifiably bounded, 
our algorithm uses $m = \text{poly}((dn)^{1/\delta}, 1/\alpha)$ batches,
runs in polynomial-time, and outputs an $O(1/\alpha)$-sized list of vectors one of which is 
$O(\alpha^{-\delta/2}/\sqrt{n})$ close to the target. That is, our algorithm substantially 
improves both the minimum batch size and the final error guarantee, while achieving the optimal list size. 
Our approach leverages higher-order moment information by carefully combining the SoS paradigm interleaved with an iterative method and a novel list  pruning procedure for this setting. 
In the process, we give an SoS proof of the Marcinkiewicz-Zygmund inequality that may be of broader applicability.

Batch List-Decodable Linear Regression via Higher Moments
Ilias Diakonikolas" Daniel M. Kane 22 Sushrut Karmalkar" *3 Siban Liu" Thanasis Pittas 11
Abstract
setting. In the process, we give an SoS proof of the Marcinkiewiez-Zyggmndd inequality that may be of broader applicability.
We study the task of dist-deco linear regres- sion using batches. A batch is called clean if the points it contains are i.i.d. samples from an un- known linear regression distribution. For a param- eter a E (0, 1/2). an unknown a- fracction of the batches are clean and no assumptions are made on the remaining batches. The goal is to output a small list of vectors at least one of which is close to the true regressor vector in fn-norm. (Das et al., 2023) gave an efficient algorithm for this task, under natural distributional assumptions, with the following guarantee. Under the assumption that the batch size n satisfies n 2 11 and the number of batches is m = poly n, 1/a), their algorithm runs in polynomial time and outputs a list of (1//a²) vectors at least one of which is close to the target regressor. Here we design new polynomial-tin this task with significantly stronger guarantees under the assumption that the low-degree mo- ments of the covariates distribution are Sum-of- Squares (SoS) certifiably bounded. Specifically, for any constant 5 O, as long as the batch size is as(a=5) and the degree-O(1/6) moments of the covariates are SoS certifiably bounded, our algorithm uses m = poly((dn) 1/aa batches, runs in polynomial-tine time, and outputs an Osizeds list of vectors one of which O(a 0(a-6/2// /Vr) close to the target. That is, our al- gorithm achieves substantially smaller minimum batch size and final error, while achieving the optimal list size. Our approach leverages higher- order moment information by carefully combin- ing the SoS paradigm interleaved with an iterative method and a novel list pruning procedure for this
1. Introduction
In several modern applications of data analysis, includ- ing federated learning (Wang et al., 2021), sensor networks (Wax & Ziskind, 1989), and crowdsourcing (Steinhardt et al., 2016), it is typically infeasible to collect large datasets from single source. Instead, samples are collected in batches from multiple sources. Unfortunately, it is often hard to find sources that provide many samples, i.e., that have large-size batches. A standard example is a movie recommendation system using rates collected from users. Here, an individual user is often unlikely to provide rating scores for large number of movies, frequently resulting in data batches with relatively small sizes. Even less favorable, in such crowd- sourcing settings, it is also the case that a majority of the participants might be unreliable (Steinhardt et al., 2017; 2016; Charikar et al., 2017). Such practical settings serve as motivation for this work. Formally, we study the task of linear regression under the assumption that we are given access to the model through small batches of samples col- lected from different sources. Importantly, as motivated by our running example, we consider the setting where most batches might not be collected from reliable sources.
algorithm for
Definition 1.1 (List- Decodaaece Linear Regression using Batches). Let Dz- be the distribution on pairs (X,y) y) Rd+1 such that 8 T X + +g. for & ~~ NN(0aa)) and X ~ G that are drawn independently from each other. Suppose we are given m batches of size n each, where for each batch, with probability a the batch consists entirely of i.i.d. samples from D3- and with probability 1 from some arbitrary distribution. The goal is to output a list L of vectors in Id with |L| < O(1aa), and the guarantee that there is 3 E L such that || 8 1*112 is small.
is drawn
Equal contribution 'epaarment of Computer Science, Univer- sity of Wisconsin Madison, Madison, United States 'Department of Compuetr Science and Engineering, University of Californi San Diego San Diego United States "Microsoft Research, Cambridge, England. Correspondence to: Thanasis Pittas <pittas@ ceattas@wisc.edee wisc..duu>.
For the vanilla setting of linear regression, with batch size 1 and no outliers, the classical least-squares esti- mator is essentially optimal. Unfortunately, even a single outlier is enough to force the least-squares estimator to de- viate arbitrarily. To address this discrepancy, Huber (1964); Rousseeuw & Leroy (1987) proposed classical robust es- timators that could handle constant fraction of outliers.
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Batch List-Decodable Linear Regression via Higher Moments
However, these estimators are computationally intractable (i..,, have runtime exponential in the dimension). Start- ing with the works of Diakonikolas et al. (2016); Lai et al. (2016), there have been flurry of results for efficient es- timators which are robust to a small constant fraction of outliers in the data. See Diakonikolas & Kane (2023) for an overview of this field.
Is there computationally efficient algorithm for list-decodable linear regression in the batch setting with significantly improved batch size and/or error guarantees?
Here we answer this question in the affirmative. In particular, we provide an algorithm that for any constant ò > 0, it runs in polynomial time and succeeds with minimum batch size n Os(a- (a) achieving error Ox(Ea (o/aa-66//// / /v)) As note regarding notation, will switch from using the parameter 5 > O to using k = [1/5] throughout the paper.
The regime where a majority of the data might be out- liers, known as list-decodable setting, was initially examined for mean estimation, where Charikar et al. (2017) demon- strated the first polynomial-time algorithm. Their algorithm computes small list of hypotheses with the guarantee that one element in the list is close to the target. Generating a list of candidates, as opposed to a single solution, is information- theoretically necessary (intuitively because the outliers can mimic legitimate data points). The size of the list typically scales polynomially with the inverse of the inlier fraction, a. The problem of fist-decodable linear regression (with batches of size 1) was first studied in Karmalkar et al. (2019); Raghavendra & Yau (2020). Unfortunately, the al- gorithms obtained in both of these works had sample and
1.1. Our Results
Throughout our work, we assume that the clean covariate distribution satisfies the following conditions.
Assumption 1.2. Let X be the clean covariates distribution from Definition 1.1. We assume that
1. X is L hypercontractive, i.e., for any u E Rd, it holds E [[xTxx]
O(1) E [(u" x)?]²
2. X has identity second moment, i.c., ][XX]== II
3. There exists Q 2 1 and an integer A such that for all integer E [A] the degree-2t moments of X are SoS certifiably bounded by Q (see Definition 3.2 for the formal definition).
computational complexities scaling exponentially in 1/a, specifically of the form dpoly(1/o) for d dimensions. Inter-
estingly, it was subsequently shown (Diakonikolas et al., 2021) that such dependence may be inherent (for Statis- tical Query algorithms and low-degree polynomial tests two powerful, yet restricted, models of computation).
We note that assumptions 1 and 2 are common in the con- text of robust linear regression (see, e.g., Das et al. (2023); Cherapanamjeri et al. (2020)). Assumption 3 is made so that the algorithm can take advantage of higher-order mo- ment information from the distribution and is satisfied by wide range of structured distributions, e.g., all strongly logconcave distributions.
Motivated by this hardness result, Das et al. (2023) pro- posed the batch version of the problem (Definition 1.1). The hope was that by introducing (sufficiently large) batches, the exponential complexity dependence on 1/a can be clim- inated. Before we summarize their results, some comments in order regarding Definition 1.1. First, in the extreme case where the batch size is n 1, we recover the standard list-decodable setting. Second, in the other extreme where n = R(d), the problem becomes straightforward. since one batch contains sufficient information to recover the target regression vector. As discussed in our running example, the batch size, which corresponds to the number of samples collected from single source, is rarely large enough in real-world applications with high-dimensional data. This leaves the regime of 1 < & d as the most meaningful. Das et al. (2023) showed that using m = poly n, 1 fa) batches of size n 2 Q(1/a), it is possible to efficiently recover a list of size O(1/a²) containing an element & with ((a). Their algorithm runs in fully polynomial time, thus escaping the exponential dependence on 1/a.
Our main result is the following theorem.
Theorem 1.3 (Main Algorithmic Result). Let a E 10,1. 0>0, k E z and 8 E RRd Assume that OSR. 11,8 1R,s,, and l < A/2. There is an algorithm that takes as imput a, a, R, k. draws m = Ô ((0((((k)) ((kd) fa + a =3) log ( ($) batches of size = O Q2////// Q0/K) from the distri- bution of Desinition 1.I, and returns a list of estimates of size O(a-1), such that, with high probability, there exists at least one estimate 3 satisfying || - -8*112 O 1kQ -3/k/ /n).
Some remarks are in order. Theorem 1.3 provides substantial qualitative improvement over the bounds of Das et al. (2023) by succeeding for a dramatically smaller batch size while at the same time improving the estima- tion error. Concretely, our algorithm can use batch size of n 0 6/k) for any k E Z+ of our choice, while Das et al. (2023) was only able work with n = Q(1/a). We note that these improvements are possible due to our
|| 32
The linear dependence on 1/a in the minimum batch size n is inherent in the approach of Das et al. (2023). Moti- vated by the practical applications of the batch setting, here we ask whether efficient algorithms are possible that suc- ceed with significantly smaller batch size and/or with better error guarantees:
Since X has identity covariance, this implies that the bound Q has to he at least 1.
2

---

Batch List-Decodable Linear Regression via Higher Moments
stronger distributional assumptions that allow us leverage higher moments.
v om needs to be larger than 1.
In the remainder of this section, we outline the ideas of our approach.
Conceptually, we view the capability of our algorithm to work with ffexible batch size as valuable feature- especially in real-world applications where the batch size corresponds to quantities that are not controllable by algo- rithm designers, i.e., the number of datapoints contributed by each provider. Our result essentially shows that there is smooth tradeoff between the batch size provided and the computational resources required. More generally, our algorithm can cover the entire regime of C' C'log" l'log"(1/a) (1/a) S n I C/a, if we do not necessarily restrict & to be an ab- solute constant. A limitation is that reaching the lower end of the regime would require k to be super-constant, namely ~ log" (1/a), which would result in quasi-polynomial runtime. Interestingly, even for that lower regime of The- orem 1.3 gives the first non-trivial (i.e., sub-exponential time) algorithm for the task.
Iterative Estimation of the Regressor Our main idea is to incorporate higher moment information into the estimator to alleviate the requirement on batch sizes. There are two main challenges in exploiting higher moment information. First, existing multi-filte approaches in the literature do not exploit higher moments, thus they are not easily modified. Second, existing higher-moment filters are not designed for iterative use. They can generate a list of potential candidates but cannot progressively refine sample clusters for cleaner data segmentation, as the gradient descent method by Das et al. (2023) requires.
To address this, our approach adopts similar frame- work to Diakonikolas et al. (2019) for robust linear regres- sion with a small fraction of outliers, but in a non-batch setting. Here is an overview of their algorithm: They be- gin by estimating the mean of the product of the covariate X with the label y. In the outlier-free setting, this expec- tation equals to the true regressor 3", and the covariance matrix can be bounded above by 0 (11,5*13 I (assuming ||8 > o). They then use an algorithm for robust mean estimation for an initial estimate 3 with a bounded error relative to 3r. They then improve the error by bootstrapping this approach. To do this, they adjust the labels via the transformation y' = y 8 X. This reduces the problem of learning 3 to another robust linear regression instance whose solution has much smaller norm. Repeating this process iteratively al- lows them to refine their estimate to a final error of O (EEr).
Complementing our upper bounds, we point out that the super-polie polyrooolno dependence for extremely small values of n might be inherent. Via a simple reduction from the non-batch to the batch-setting (combined with the lower bound of Diakonikolas et al. (2021)). we give evidence that the computational resources used in the algorithm of Theorem 1.3 do not suffice for significantly smaller than log(1 /a). See Appendix F for the relevant discussion.
covarianve distributions to derive
1.2. Technical Overview
Prior Techniques We start by reviewing the algorithm of Das et al. (2023), which uses a batch size of n = (11/o).
For simplicity, consider the case where the covariates are standard normal. The high-level idea in Das et al. (2023) is to search for approximate stationary points 2 of the L2- loss, [(3) 1/ Exx,,) [[8TX- - u) Without outliers, the expected gradient precisely equals 9 Sr. If we recover a E-approximate stationary point for the inlier distribution, we can estimate 3 up to an error of O given enough samples. With outliers, the method exploits an upper bound on the covariance the gradient distribution of the inliers to detect outliers and to control their influence. They then use the multi-filter approach for list-decodable estimation (Di- akonikolas et al., 2020) to find a subset of the samples with the covariance matrix of the gradients being upper bounded by ((1) ||B 3 |13 /nI. with an a overlap with the inliers. This ensures that a É-approximate stationary point under the corrupted sample distribution will still be a (E+ + ||3 / / -aprxxxmie stationary point under the inlier distribution. This means that approximates 3 up to error of & + ||B 30112// Unfortunately, this results in ||3 - 1²112 < O(E) only when > 1/a, since
In our setting, a natural strategy is to replace the ro- bust mean estimation algorithm with one designed for list- decodable mean estimation, since the fraction of corruptions is larger than 1/2. Suppose that we have an algorithm A which produces list of candidate regressors )m such that at least one of them satisfies || - 12 < ||/3 By applying the transformation y = y - 3, X, we can create m distinct linear regression instances such that the regressor of one of these will have a significantly smaller norm. This allows us to compute more accurate estimates in the next iteration.
Beyond Second Moments As mentioned in the last para- graph above, the natural approach is to iteratively use a list-decodable mean estimation algorithm like the one from Diakonikolas et al. (2020) in order to estimate the mean of the random variable W = + E(x,)) n y (where B is an inlier batch) and reduce the error by a factor of in each iteration. List-decodable mean estimators that rely only on second moment information have error behav- ing like /l[[Cv(W))lo) Va, where v/l Co
'A vector 8 E RRd is called a-pproxiiaate stationary point of some function f: Rd + R if it holds [BV]( S g.
3

---

Batch List-Decodable Linear Regression via Higher Moments
O (1181 is the maximum standard deviation of W along any direction. This already reveals the problem with this approach: for the error to become less than || 1l2/2, we need batch size n >>>>> 1/a.
"explains" these samples. This results in certain "consis- tency" tests, on the basis of which can prune elements of the list. The tests are designed such that (i) 3 and the subset of inlier samples should pass the consistency tests, and that (ii) for any pair of sufficiently separated hypotheses, if they both pass the tests, their corresponding sets cannot have a large overlap. Given property (ii), the argument from Diakonikolas al. (2020) shows that we can find a small cover of the set of plausible hypotheses.
We overcome this (Proposition 3.1) by using a list- decodable mean estimator that uses higher moment infor- mation, like Theorem 5.5 from Kothari & Steinhardt (2017), or Theorem 6.17 from Diakonikolas & Kane (2023). These algorithms are based the Sum-of-Squares hierarchy and their guarantee is that whenever the higher moments of the inliers are "SoS "SoS-certifiably bounded" by M, then the estimation error is O -3/k).
In the list pruning step for list-decodable mean esti- mation, one usually leverages the fact that the inlier sam- ples cluster closely around the learned mean (see, e.g., Di- akonikolas et al. (2018; 2020)). This ensures survival of the optimal mean from the pruning procedure. One may want to generalize the test to the linear regression setting by asserting that Xy y should concentrate around the candidate regressor 3. However, such test turns out to be sub-optimal for linear regression 3. Instead, we design the following "cross-candidate" test: we keep 3 only if 3 demonstrates a smaller empirical &g error for an a-fraction of selected batches in comparison to any other regressor significantly distant from B. One may wonder whether the best regressor in the list can still survive the test, as there may be multiple equally good candidate regressors in the list with respect to the same cluster of batches. However, we note that the regressor is only compared to distant regressors. Conse- quently, they must all be far from the optimal regressor (by the triangle inequality), ensuring the survival of the best regressor. This is formally shown in Lemma 3.8.
However, to leverage the above SoS-based algorithm, we require sharp SoS bounds on moments of the batched re- gressor estimator W- TET Σ e vX, which a sum of i.i.d. random variables, while our distributional assump- tion only posits that the covariate X has certifiably bounded moments. The fact that W should also have bounded mo- ments (but not necessarily SoS certifiable) follows from the famous Marcinkiewicz Zygmund Inequality. Unfortunately, to the best of our knowledge, an SoS proof of this inequal- ity does not exist in the literature. We give the first SoS proof of the inequality using combinatorial arguments (ef. Lemma 3.3). We believe that this technical lemma may be of broader applicability.
Given the SoS moment bounds on W, the SoS- based list-decoding algorithm allows us to construct a list of size O(1/a)) such that one of the estimates is (x(((1)8* /222)1/(2))) -a/k-3//k))k -close to 3r. Hence, we will have some estimate B satisfying || whenevern > a -3/k, which is significant relaxation from the condition >> 1/a required by both the first approach and the approach of Das et al. (2023).
S [|
1.3. Related Work
In this section we discuss related works from list- decodable linear regression and robust learning from batches. The problem of mixed linear regression is related very closely to work well, but due to space restric- tions, we defer the relevant discussion to Appendix A.
List Size Pruning Having gotten the right estimate for one step, we bootstrap this to design an iterative algorithm such that the final list will contain an element that is sufficiently close. A significant challenge arises during the iterative phase of our list decoding algorithm. Initially, we gener- ate list of (1/ax) hypotheses, with the guarantee that at least one of them is near 8*, For each hypothesis, iterating further produces another ((1/a) hypotheses for each of the original hypotheses. Without careful management, this process can lead to an increase in the number of hypothe- ses that scales exponentially with the number of iterations, rendering the algorithm's 's complexity infeasible.
List-decodable Linear Regression The list-decoding framework was first introduced in the context of machine learning in Charikar et al. (2017). They derived the first poly- nomial time algorithm for list-decodable mean estimation when the covariance is bounded. Later work considered the problem of list-decodable linear regression in the non-batch setting (Karmalkar et al., 2019; Raghavendra & Yau, 2020). Unfortunately the runtime and sample complexity had an exponential dependence on 1/a, this was later shown to be necessary for SQ algorithms (Diakonikolas et al., 2021).
We overcome this (Proposition 3.6) with techniques inspired by Theorem A.1 in Diakonikolas et al. (2020) (see also Exercise 5.1 in Diakonikolas & Kane (2023)), which performs list-size reduction for list-decodable mean estima- tion. The general principle behind these methods is to check whether each hypothesis in the list has a (f)--factiion sub- set of the samples associated with such that the hypothesis
Robust Learning from Batches The problem of learning discrete distributions from untrusted batches was introduced
'Intuitively, this is because such a test fails to take into account the influence of the size of / on the concentration of the inlier samples.
4

---

Batch List-Decodable Linear Regression via Higher Moments
in Qiao & Valiant (2018), which gave exponential-time so- lutions. Progress was made by Chen et al. (2020b) and Jain & Orlitsky (2020), achieving quasi-polynomial and polyno- mial runtimes, respectively, with the latter also obtaining optimal sample complexity. Further developments by Jain & Orlitsky (2021) and Chen et al. (2020a) expanded this work to one-dimensional structured distributions. Das et al. (2023) was the first to study the problem of list-decodable linear regression in the batch setting. Compared to Das et al. (2023), our method demonstrates substantial improvements in the error and the required batch size, when the covariates are i.i.d. samples from (0, 1). This can be attributed to our algorithm's 's ability to efficiently utilize higher moment information, allowing for smaller batch sizes of (2 ) and achieving an error of Ok.a(aa -3/k/ / VT), marking significant improvement over a batch size of (((a-)) and error of /on), achieved in Das et al. (2023).
this proof is of degree K and write A K r(z) 2 0. When we want to emphasize that x is the indeterminate a partic- ular SoS proof, we write A A r(x) 2 0. When A is empty, we omit it from the notation.
3. SoS Based Algorithm for List-Decodable Linear Regression with Batches
Our algorithm iteratively updates a list of candidates, ensuring that, in every iteration, at least one candidate from the list is close to the target regressor. It does so by iter- atively applying two subroutines. In Subsection 3.1, we discuss a list-decoding subroutine that, given batch sam- ple queries, generates a list of candidates containing some near-optimal regressor. In Subsection 3.2, we discuss a prun- ing subroutine that ensures that the size of our list remains bounded. Finally, in Subsection 3.3 we combine these com- ponents into the main algorithm (Algorithm 2) and prove our main theorem.
Organization In Section 2, we define our notation and state some basic definitions about SoS programming. In Section 3, we describe the main parts of our algorithm in Sections 1, and 3.2; we then put things together to prove our main theorem in Section 3.3.
3.1. Single Iteration: Approximate Estimation of 1
In this section, we construct an efficient SoS-based list- decoding algorithm to estimate the regressor 8 assuming that || - R. Specifically, this can be used to perform crude list-decodable estimation of the optimal regressor. In the final algorithm, we will bootstrap this method to generate our final list with improved error guarantee.
2. Preliminaries
Notation We use X ~ D to denote that random variable X is distributed according to the distribution D. We use N (v, 2) for the Gaussian distribution with mean j and covariance matrix Σ. For a set S, we use X ~ S to denote that X is distributed uniformly random from S. We write & b to denote that a I b for sufficiently small absolute constant > O. We use a(n) = (x(b(n)) to denote that there is constant C' such that for all n > C, a(n) S C b(n) for a constant Ck that can arbitrarily depend on k.
Proposition 3.1. Let a E (0,1/2), E (0.1), m, k e Z a, R 0, B E Rd. Assume 11,8112 S R and k S A/2. Then, there exists an algorithm that takes a, k. 8, o, R in the inputs, it draws log(1))((1/5) many batches from the corrupted batch distribution of Definition 1.1, runs in time poly md) and outputs 0(log(1/8)a")) many estimations such that there exists at least one estimation 3 satisfying 1|,8 81 S O ((k//n) Q2/(2k) (R+ a) a=3/k) with proba- bility at least 1 - 5 over the randomness of the batches.
O ((4kd)***= +
Sum-of-Squares Preliminaries The following notation and preliminaries are specific to the SoS part of this paper. We refer to Barak & Steurer (2016) for more complete treat- ment of the SoS framework.
A standard way of estimating the regressor is to con- sider the random variable y.X When there are no out- liers, y. gives an unbiased estimator of 5*. In the batch setting, natural estimator is to use the batch average ZB := 1 E(x,)> y.X The main idea behind Propo- sition 3.1 is that we can leverage the property that the batch average estimator Zn has SoS-certifiably bounded central moments when B consists of i.i.d. samples from the un- corrupted linear regression distribution D3- (cf. Defini- tion 1.1).
Definition 2.1 (Symbolic Polynomial). A degree-k sym- bolic polynomial p with input dimension d is collection of indeterminates p(a), one for each multiset a S [d] of size at most k. We think of it as representing a degree-k polynomial R.d - R whose coefficients are themselves indeterminates via p(x) = Enced, al p(a)a=.
Definition 2.2 (SoS Proof). Let 2 In, be indetermi- nates and A be set of polynomial equalities {pi(x) 0,... (x) = 0}. An SoS proof of the inequal- ity r(x) N 0 consists of two sets of polynomials (ra()) ( such that -xx)= = ->" r+,)+ (())((
Definition 3.2 (SoS-Certifiably Bounded Central Moments).
Let M 0, & be an even integer, and D be a distribu- tion with mean μ. We say that D has ( (M, k, -)-cetiifialyy
If the polynomials {² U
E all have degree at most K, we say that
bounded moments if [|linlB = 1} K Ex-D (uT(X-
5

---

Batch List-Decodable Linear Regression via Higher Moments
] < M. We say set of points T has 2k-th central moments SoS-certifably bounded by M if the empirical distribution over these points does so.
for some positive inlegers k, K and M O. Then there exists an algorithm that, given S,k, K, M and o, runs in time poly(dk, (SS),, and with probability 0.9, returns a list of O(1/a) many vectors containing some fu with j Ms 2 = O (M/1/22) ox
Observe that Zn is the sum of n i...d. copies of yX, and X has SoS-certifably bounded moments by Assumption 1.2. Applying the Marcinkiewicz-Zygmmnn Inequality, which controls the moments of i..d. random variables by their individual moments, will almost immediately yield that Zn also has bounded central moments. To further show that the bound is SoS-certifiablee we thus require an SoS version of this moment inequality, which is provided below.
Proof of Proposition 3.1. Suppose we take m ((4k))& ( Q- + 1) a- many batches. m M(a) > (4kd)šk + 1 many of these batches are of inlier type with high constant probability, We denote the set of these batches by G. Define ZB A. - By. Xy. Let D be the distribu- tion of clean batch of size n whose samples are all i.d. from D3- (cf. Definition 1.1). As shown in the proof of Lemma 3.4, we have E BE [Zg] = gr o"
Then
Lemma 3.3 (SoS Marcinkiewicz--Zygme E Rd X1, ,., be i.i.d. random real vectors in Rd, and p IR x Idd + IR be a degree-t polynomial. Assume that
Inequality). Lei
and Cov Cov Di- [Zal 3 O R2)nn))))))))))n))) I. Since GG > (4kd)8k Q + 1, by Markov's inequality, it holds that
2RE E (p((.. X2) Eip(v, XDI* S M f
1}
for some number M > O. Then the degree-k central moment of the sum of p(u, Xi) is also SoS-certifabbl bounded:
Σ Zn/ G| 3r 50((o + (0((o+R)/VV (2) BEG
n
E [11e112 = 13 a Re
Σ
(ple, x.) [l((c;x)))
with high constant probability. Besides, since G >> (4kd)s*Q-1 + 1, Lemma 3.4 shows that 2 [6B B E G} has 2k-th central moments SoS-certifiably bounded by
I (kn))/// 1/2 M.
(1)
M = ((())) /n²) (o + 1
(3)
Combining the above SoS inequality with the fact that yX = =(3* E) X is a 2 polynomial in X, which has SoS certifiably bounded moments, and &, which follows the Gaussian distribution, then gives essentially population version of the moment bound. The SoS moment bound on the empirical distribution over samples then fol- lows by a careful analysis on the concentration properties of the empirical moments of ZB. See Appendix D for the detailed argument.
with high constant probability. Moreover, the covariance of 2 can be bounded from above by
Covz [2] = O (lo2+ R²)/n)
(4)
with high constant probability. By the union bound, Equation (2), Equation (3), and Equation (4) hold si- multaneously with high constant probability. Condi- tioned on that, Lemma 3.5 thus allows us to esti- mate the mean of {Zn O ((k/Vn) (2k) (a+ a 3k) Our estimate is then O ((k/V)) Q Q1/(2)) R) a -33)) close to 8r by Equa- tion (2), and the triangle inequality. This concludes the proof of Proposition 3.1. Finally we can boost the proba- bility of success to 1 - 8 by running the above procedure log(1/6) many times and combining the lists obtained.
Lemma 3.4 (SoS Moment Bound), Let a E (0, 1/2), a>0, k E Z= 8r E Rd. Let T be set of m batches drawn according the distribution Dg. defined in Definition 1.1, and batch size Assume that the clean covariates distribu- tion X satisfies Assumption 1.2 and ls & A/2. Define Z =
E G} up to accuracy
1 EXxxieB Xy. Suppose m >> ((Akd))*Q-) + +1) a-1
Then the following holds with probability at least 0.9: (a)
{ZB B E T} has (M, 2k. 4k) -ketcceiiy bounded mo-
ments for some M = ((k)) 22 /n²) Q (02k +2 [18 112).
3.2. Pruning Routine
and (b) CovB-r [p ((II) l2 + D/))L
In this subsection, we show that there is an algo- rithm, Pruning, which reads a list L containing a candidate close to 8", and returns sub-list T,' C L of size O(1/a) also containing a candidate close to /
Once we have that the central moments of Z are certi- fiably bounded, Proposition 3.1 follows from the following SoS-based list-decodable mean-estimation algorithm:
Lemma 3.5 (Theorem 5.5 from Kothari & Steinhardt (2017)). Let S be a set of points in Rd containing a subset Syood with |Syood 2 a}S}. Moreover, assume that Syout has (M, 2k, K) -e-eertilllbly bounded moments
Proposition 3.6 (Pruning Lemma). Let a E (0, 1/2), 8 E (0, 1). k E Z,, O, > O, and 3" E Rd. Let L C Rd be a list of candidate regressors, and $ E L be a regressor such that ||B - f0112 < R. Assume
6

---

Batch List-Decodable Linear Regression via Higher Moments
that the batch size n satisfies that > k Qafk a a-2/k and k S A/2. Then there exists an algorithm Pruning that takes the list L, and the numbers a, 6, R as input, draws m = O (min (log(IL))dd) d²) 1og(1/6) a a=3) many batches from the corrupted batch distribution of Defini- tion 1.1, runs in time poly(dm)Li)) and outputs at most ((1/a) candidate regressors L' S. L such that there is at least one regressor& B E L' satisfying ||3 - 3 1/
Lemma 3.7 (List Size Bound). Let R > O, and L be a list of candidate regressors. Let T be set of batches. Let T'' C L be sublist of candidate regressors satisfying the following conditions: (1) [E(3; L, T, R) has solutions for each B e I,, and (2) | - 82112 2 c R + tt- I /va)) for any two 8 32 E L'. Then it holds the size of L' is at most O(1/a).
O (R ka-1/koQU/k / /vn) with probability at least 1 over the randomness of the batches drawn.
The next lemma we need shows that the list after an application of Lemma 3.7 contains an element close to f To get some intuition, let us fix some that is close to 3* and some 3 that is far from B. By the triangle inequality, 8' therefore should be far from 3 as well. As the square loss of a candidate regressor can be viewed as a surrogate for the distance between the regressor and the optimal, it follows that Σ(X,)E (U -x must be significantly
The Pruning algorithm involves two phases. Initially, it filters regressors 3 E L by keeping those matching a certain set of solvable linear inequalities. Then it selects subset of the remaining regressors, ensuring each pair is adequately distant. Lemmas 3.7 and 3.8 respectively show that the refined list is not excessively large and that it contains a vector near the true regressor S if such a candidate exists in the original list L. The proof of Proposition 3.6 follows from the above two lemmas.
less than E(Xy)EB (y - xT over all inlier batches in expectation. Due Lz-ha hypercontractivity of X, can show that (y -x x 2 must be weakly onti-concentrated On the other hand, due to the bounds on the higher-order
For each regressor, we now describe the set of linear inequalities used in the pruning process involving weight- ing function W over the set of batches T. At a high level, weighting function can be interpreted as "soft cluster"' for each candidate regressor 3, and the inequalities aim to identify a soft cluster for each candidate regressor 3 by en- suring: (i) at least an a-fraction of batches are included in the cluster, and (ii) 33 has a smaller empirical l error in comparison to any other regressor 3' that is significantly dis- tant from B, based on the following conditions involving the constant c, radius R, standard deviation a, and batch size n. We denote this set of linear inequalities by IB(3; L, T, R), i.e. IB(3; L, T, Rt) is the following set of inequalities in the variable(s) W: T + [0, 1]:
x moments of X, we can show that (v-XT3) 3) must be sufficiently concentrated around its mean. Combining the two observations then show that Equation (6) must hold with high probability over the inlier distributions. Therefore, setting W to be the indicator variables for inlier batches must constitute a valid solution to the set of inequalities IE(3; L, T, R) constructed. The full proof can be found in Appendix E.
Lemma 3.8 (Error Bound). Let a 10.1/2), Ee (0. n, K E Z4, a, R > O, and f E Rdd Let L. be a list of candidate regressors of size K and 3 E L be a regres- sor such that || - B8112= < R. Let n >> k Q2/k a -2/k be the batch size parameter. Suppose T is a set of m > min (log (K), d²) log(1/5) x-3 many batches of size n drawn from the corrupted batch distribution of Defini- tion 1.1. With probability at least 1 1- 8 over the randomness of T. we have that the system IE (3; L, T, R) has solutions.
EBET (B) 2 0.
(5)
ko ko- fo-1/KoQU/
vB' E L satisfying ||3 - B112 2 c R
nn
for some sufficiently large constant c,
Proposition 3.6 now follows by an application of the above lemmas.
EeE 1XE (y - x 3)
E(x)E (u X 8) W(B) S EBET
Proof of Proposition 3.6. The pruning procedure proceeds in two steps. First, it filters out the / such that IB(3; L, T. R) has no solution. Second, among the remaining regres- sors, it adds them into the output list as long as it is not e (R + ka 11/K / /Vn) -close to some existing regres- sor in the output list for sufficiently large constant c. Then the size of the output list is most O(1/a) by Lemma 3.7.
(6)
We now provide some intuition about why there cannot be too many regressors whose associated linear inequalities are satisfiable subject to the constraint that they are all suffi- ciently separated. At a high level, this is because condition (ii) enforces the soft clusters associated with two sufficiently separated candidate regressors must have small intersection as two candidate regressors cannot simultaneously do bet- ter than the other in terms of their empirical errors on the same batch. We now precisely state the lemmas. For proofs, please see Appendix F.
It remains to show that there exists some 3' close to 3 in the output list if there exists some 3 satisfying ||B - 8* < R in the input list. By Lemma 3.8, B will not be filtered out with probability at least 1 - 8 in the first step. In the second step, either 3 is added
7

---

Batch List-Decodable Linear Regression via Higher Moments
to the output list or there must be some 3' satisfying ||8' I 0 (R + ka /u). Hence, we must have ||@ - 31112 2 O (R + kar - 1/k 101-1//k//// /t//////// /Vr) by the tri- angle inequality. This concludes the proof.
didate 3 such that || 11 I O(g) after all but the last iteration with respect to t. This is trivially true if R = O()). Otherwise, if R > a, we use induction to argue that for all t = 0, max(log(co R/oo) 0) 0) -1, with probability at least (1 - 27)". the list I. will contain some candidate regressor 3 such that || - ll2 S R 2- after the 1-th iteration. Note that this implies the above claim for max(log (c. 0) and for all t considered in the inductive hypothesis we have < R2-
3.3. Putting Things Together
Algorithm Batch-Listt Litth----s---Deedeee LeereseL (Informal)
Require: Batch sample access to the linear regression in- stance, o, I as specified in Theorem 1.3,
Conditioned on the existence of such 3 in the list after the (t - 1) round. By Proposition 3.1, when we exccute line 2 in the iteration where 3 = B(2), we obtain a list of regressors such that with probability at least 1 - t there exists some 3(2) E Lo and some small constant such that
1: Initialize a list
{0] to hold candidate regressors.
2: fort= = 0,
Jog Iog(R/or [Raa) do
3: Initialize an empty list L' to store refined candidate regressors.
4: for candidate regressor 33 E T. do
||,3(2) + g(2) -3112 (k: QU(2)) (R2- + oo) a a-3/k) Se ReR2
5: Take sufficiently many batched samples T.
6: For each (X. y) in T, compute the residue (X,y-8TXx) Denote the resulting new set of batches as T".
Vn
7: Lear a new list of regressors by running the al- gorithm from Proposition 3.1 on TV, and add the results to L'.
where the last inequality is true as long as n k² a-6/ Q1/k, and R 2- >> c.. The list Lo is now of size ((lo(L/r)//a) Thus, after Line 2, by Proposition 3.6, the list L gets pruned into one with size O(1/a) with probabil- ity at least 1 - r. Moreover, L still contains some candidate ((3) such that
8: end for
9: Replace I. with E/"
10:
Run algorithm from Proposition 3.6 to prune the list
L into one with size O(1/a).
11: end for Return L.
|| - Blla s 0 (cR2"' + ka ka- < R R2"
12:
as long as c is sufficiently small, n > 12a 2/ Q2// and R2- >> a. This concludes the induction.
In this section, we prove our main theorem, starting with high-level overview of the algorithm, which mirrors the structure of the robust linear regression algorithm from Diakonikolas et al. (2019) that can tolerate a small constant fraction of outliers. The process begins with estimating 3*, as outlined in Corollary 3.1, to obtain a list L. We then create new linear regression instances by transforming each sample (X, 3) into (X, y X) for every in L. This ensures that for at least one transformed instance, the norm of the optimal regressor decreases significantly. Applying Corollary 3.1 to these instances and merging the resulting lists yields a list containing a candidate regressor that is closer to 3*. We iterate this process until we get a list with an element that sufficiently close to 3*. One issue is that the list size will increase exponentially terms of the number of iterations. To counter this, Proposition 3.6 is employed to prune the list to an optimal size while main- taining the error of the best candidate regressor to within constant factor. The pseudocode of an informal version of the algorithm is provided in Algorithm 1. See Algorithm 2 in the appendix for the formal version.
In the last round, since we have R I ( with similar argument. arrive at a list of size 0(1/a) that contains some ,3 satisfying
|| - 8-11 10112 Q(12k) (1( a a o0/3/////V
+ (ka 1/k - -o (((/VT)) Q a a a=//)).
It is not hard to see that the total number of samples con- sumed by the algorithm is at most
(Akd)s*QQ log (log(1/T)/a) log(1/T) Log(R/o) a Ō (((4kd))) /a- - a=3) log (R/o))-
a²
Moreover, the runtime polynomial in the sample size times d² which is the space complexity required for repre- senting moment 2k tensor.
Impact Statement
Proof of Theorem 1.3. Suppose 1|a* S R. We claim that with high constant probability the list I. will include can-
This work is predominantly theoretical and does not present any immediate societal or ethical considerations
8

---

Batch List-Decodable Linear Regression via Higher Moments
requiring special attention. Its contribution lies in advancing foundational understanding rather than influencing direct real-world applications policy.
References
Barak, B. and Steurer, D. Proofs, beliefs, and algorithms through the lens of sum sum-of- 2016.
Charikar, M., Steinhardt, J., and Valiant, G. Learning from untrusted data. In Proc. 49th Annual ACM Symposium Theory of Computing (STOC), pp. 47-60, 2017.
Chen, S., Li, J., and Moitra, Learning structured dis- tributions from untrusted batches: Faster and simpler. In Advances in Neural Information Processing Systems, 2020a.
Chen, S., Li, J., and Song. Z. Learning mixtures of linear regressions in subexponential time via fourier moments. In Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC), 2020b. 2020b.
Cherapanamjeri, Y., Aras, E., Tripuraneni, N., Jordan, M. I., Flammarion, N., and Bartlett, P. L. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.08137 2020.
Das, A., Jain, A., Kong, W., and Sen, R. Efficient list- decodable regression using batches. In International Con- ference on Machine Learning, pp. 7025-7065, PMLR, 2023.
De Veaux, R. D. Mixtures of linear regressions. Computa- tional Statistics & Data Analysis, 8(3):227-245, Novem- ber 1989.
Diakonikolas, I. and Kane, D. M. Small covers for near zero sets of polynomials and learning latent variable models. In Proc. 61 IEEE Symposium on Foundations of Com- puter Science (FOCS), 2020.
Diakonikolas, 1. and Kane, D. M. Algorithmic high- dimensional robust statisties. Cambridge university press, 2023.
Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, Robust estimators in high dimensions without the computational intractability. In Proc. 57th IEEE Symposium Foundations of Computer Science (FOCS), pp. 655-6644 2016.
Diakonikolas, I., Kane, D. M., and Stewart, A. List- decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1047-1060, 2018
Diakonikolas, I., Kong, W., and Stewart, A. Efficient al- gorithmms and lower bounds for robust linear regression. Proceedings of the Thirtieth Annual ACM-SIAM Sym- posium on Discrete Algorithms, pp. 2745-2754, -754.. SIAM, 2019.

---

Batch List-Decodable Linear Regression via Higher Moments
Diakonikolas, I., Kane, D. M., and Kongsgaard, D. List- decodable estimation via iterative multi-filtering. In Advances in Neural Information P Processing Systems 33 (NeurlPS), 2020.
Kothari, P. K. and Steinhardt, Better agnostic clus- tering via relaxed tensor norms. ArXiv preprint arXiv:1711.07455 2017.
Lai, K. A., Rao, A. B., and Vempala, S. Agnostic estimation of mean and covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 665- 674, 2016.
Diakonikolas, I., Kane, D. M., Pensia, A., Pittas, T., and Stewart, A. Statistical query lower bounds for list- decodable linear regression. In Advances in Neural Infor- mation Processing Systems 34 (NeurIPS), 2021.
Qiao, M. and Valiant, Learning discrete distributions from untrusted batches. In Proceedings of the 9th Con- ference on Innovations in Theoretical Computer Science, ITCS 18, pp. 47:1-47:22 2018.
Diakonikolas, I,, Kane, D. M., Karmalkar, S., Pensia, A., and Pittas, T. Robust sparse mean estimation via sum of squares. Conference on Learning Theory, COLT, 2022a.
Diakonikolas, I., Kane, D. M., Karmalkar, S., Pensia, A., and Pittas, T. List-Decodable Sparse Mean Estimation via Difference-of-Paiee Filtering. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022b.
Raghavendra, P. and Yau, M. List decodable learning via sum of squares. In Proc. 31st Annual Symposium on Discrete Algorithms (SODA). SIAM, 2020.
Rousseeuw, J. and Leroy, A. M. Robust Regression and Oullier Detection. John Wiley Sons, Inc., 1987. ISBN 0-471 1--73--5233--.
Hardy, G. H., Littlewood, J. E., and Pólya, G. Inqqualities. Cambridge university press, 1952.
Hopkins, B. Clustering and sum of squares proofs: Six blog posts on unsupervised learning. 2018.
Steinhardt, J., Valiant, G., and Charikar, M. Avoiding im- posters and delinquents: Adversarial crowdsourcing and peer prediction. In Advances in Neural Information Pro- cessing Systems 29 (NeurIPS), 2016.
Huber, P.J. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1):73-101, March 1964.
Steinhardt, J., Koh, P. W., and Liang, P. S. Certified de- fenses for data poisoning attacks. In Advances in Neu- ral Information Processing Systems (NeurIPS) 2017, pp. 3520 3520-3532, 2017.
Jain, A. and Orlitsky, A. Optimal robust learning of discrete distributions from batches. In International Conference on Machine Learning, pp. 4651 16660. PMLR, 2020.
Wang. J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., Al-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., Data, D., et al. A field guide to federated optimization. arXiv preprint arXiv:2 107.06977777.. 2021.
Jain, A. and Orlitsky, A. Robust density estimation from batches: The best things in life are (nearly) free. In International Conference on Machine Learning, pp. 4698- 4708. PMLR, 2021.
Wax, M. and Ziskind, I. On unique localization of multiple sources by passive sensor arrays. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7):996- 1000, 1989.
Jain, A., Sen, R., Kong, W., Das, A., and Orlitsky, A. Lin- ear regression using heterogeneous data batches. ArXiv Preprint (rxhv:2309.0997. 2023.
Jordan, M. I. and Jacobs, R. A. Hierarchical mixtures of experts and the EM algorithm. Neural Computation, (2):181-214, 1994.
Karmalkar, S., Klivans, A., and Kothari, P. K. List- decodable Linear Regression. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
Kong, W., Somani, R., Kakade, S., and Oh, S. Robust meta- learning for mixed linear regression with small batches. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020a.
Kong, W., Somani, R., Song, Z., Kakade, S., and Oh, S. Meta-learning for mixed linear regression. In Interna- tional Conference on Machine Learning, pp. 5394-5404 PMLR, 2020b.
10

---

Batch List-Decodable Linear Regression via Higher Moments
Supplementary Material
Organization In Appendix A we discuss work on the problem of mixed linear regression, which is very related to the setting we consider here. In Appendix B we state some basic SoS facts. Then, in Appendix we adapt proofs from (Diakonikolas et al., 2022a) to show that if the original distribution has certifiably bounded moments, then the uniform distribution over sufficiently large sample also has certifiably bounded moments. We then use this to prove Lemma 3.4. In Appendix E we prove the lemmas required to get our pruning guarantee in Subsection 3.2. Finally, in Appendix F we present a simple reduction of our problem to the problem of list-decodable linear regression in the non-batch setting.
A. Related Work on Mixed Linear Regression
Mixed Linear Regression The mixed linear regression setting is when the data is generated by mixture of distributions
D1, Di,..., Dr, each on IRd x R such that (X,y) ~ D, is equivalent y - _ X + E for X NN 7) and (N o²) (DeVeaux, 1989; Jordan & Jacobs, 1994). We refer the reader to Section 1.2 of (Chen et al., 2020b) for detailed summary of prior work for this problem. In the non-bater setting, this problem suffers from an exponential dependence on t. This is inherent in moment-based approaches, as shown in (Chen et al., 2020b). The most efficient algorithm for the problem is due to (Diakonikolas & Kane, 2020) which runs in time and needs samples quasi-polynomial in l.
In the batch setting, this was first studied for covariates drawn from NO0 I) by (Kong et al., 2020a;b). Here, all the samples from each batch belong to a single component. (Kong et al., 2020b) design an algorithm that requires (d) batches of size O(vi) solve the problem efficiently (including in terms of the parameter t). Subsequently, (Kong et al., 2020a) uses the sum-of-squares hierarchy to design a class of algorithms that can trade between the batch size and sample complexity while being robust to a small fraction of outliers. 4 Finally, (Jain et al., 2023) greatly generalize the scope by designing an algorithm that can recover the regressors for all components such that at least an a fraction of the batches satisfy a linear-regression model with variance in the noise bounded by o². Their algorithm works even when the covariates for each component are different, varying, and heavy- They do this by allowing for batches nonuniform size. They require O(d/a²) batches of size 2 and min( Vt, 1/ va)/a batches of size Q min( (VE, 1/va). This is very close the list-decodable setting we study in this paper; however, do not allow for nonuniform batch sizes. Even so, our algorithm can improve the batch size required by a constant power of the algorithm designer's choice in the exponent.
B. Further background of SoS Proofs and Moment Bounds
It is a standard fact that several commonly used inequalities like the triangle inequality, Cauchy-Schward or AM-GM inequalities have an SoS version. Fact B.1 (SoS Cauchy-Schware and Hölder (see, e.g., (Hopkins, 2018))). Let fi, fi. .1......
,.....,,, fnr In be indeterminates. Then,
1
figi
2m1
Fact B.2 (SoS Triangle Inequality). If k is an even integer,
(Ein
01)*
S n (Eizaa)) d
Fact B.3 (SoS AM-GM Inequality, see, e.g.. Chapter 2 of (Hardy et al., 1952)). Let k be an even integer, and {w:) be integers such that Σ wi = k. Then it holds that
W.
k
x
k
Using these inequalities, we can construct SoS proofs for bounds of moments of sum of i.i.d. random variables with So$ certifiably bounded moments. The non-sos version of the inequality is commonly known the Marcinkiewicz--yyymnd inequality.
Proof of Lemma 3.3. For notational convenience, we define yi = p(v,X; - Elp(e: (,, X,)]. Note that each y, is a degree-t polynomial in u and X,. If we expand (Σi=1 v1)* we get n² many monomials of the form I Vo, for some o, E [r]]a.
*This similar in flavor to what we do this paper but for the much harder problem of list-decodable linear regression.

---

Batch List-Decodable Linear Regression via Higher Moments
If the degree of some y/ is the expected value of that monomial will be 0 since Elye] Elp(v, X₂) Elp(v, X,)]
Hence, E E j=1 Voy non-zero only if the number of variables appeared is at most k/2 since otherwise some y/s must have degree-1 by the pigeonhole principle, By a simple counting argument, we have that the number of monomials with non-zero expectations then most ((1/2)) kk/2 Let I y4 be one of such monomial with non-zero expectation.
where > W = k. We can bound its expectation from above by
flull = 1}
E
S M,
where the first inequality is by Fact B.3, and the second inequality is by our assumption that {1lu1 1} E (p(v, X,) E[p(v, X:))* follows that
E
such monomials with non-zero expectation, it then < M. Since there are at most n/2 h2/2
{1el11 = 1}
2k
Σ V1
S 4/2 M.
C. Algorithm Pseudocode
Algorithm 2
Require: Batch sample access to the linear regression instance, and a, a, R, k as specified Theorem 1.3.
Initialize (0).
2: Set failure probability 0.001/ log(R/o).
3: Let co be some sufficiently small constant and C' be some sufficiently large constant.
4: for (= 0,
Rt/o), 0) do 5: Initialize Lo = {0}
6: for candidate regressor 3 L do
7: for r = 0, ... log(1/77 (1/r) do
8: Take a batch of C (2dk) /a samples T.
9: For each (X, v). compute 1x,3-3T X). Denote the new set of batches as T' Learn list L1 of regressors by running the algorithm from Proposition 3.1 on T'. Add the candidate regressors (3' + 3 8 E L1} into Lo-
10:
11:
12:
end for end for
Set L= Lo.
15: Draw C min (og((log1/77//a)] d²) log(1/r)a batch of samples T'.
16: Run algorithm from Proposition 3.6 on T" prune the list L with failure probability
17:
end for
18:
Return L.
D. Certifiably Bounded Moments of the Regressor Estimator
In this subsection, we give the proof of Lemma D.4. We first give several preliminary lemmas regarding the concentration properties of empirical higher order moment tensors of distribution with bounded central moments. The proof is similar, for example, to Lemma A.4 from (Diakonikolas et al., 2022b).
Lemma D.1. Let be a distribution over TRd with mean μ. and t E Z4. Suppose that D has its covariance bounded from above by sI, and its degree-2t central moments bounded by F, iee. EX-D V (X [x)))= S F. Let X1,..., ... Xm be m i...d. samples from D. The following inequalities hold with high constant probability.
[X, [~/mm]
11)
[X - 1999) X
E
so (dVV/F/m)
12

---

Batch List-Decodable Linear Regression via Higher Moments
Define in Ei=1 X We also have that
|1 Tal22 O
( (Vdd/m).
Proof. Note that each entry within the tensor Ex-D [[X - (1) (0 is of the form EX-D [T - r)], where T': R + R some monomial of degree Fix some degree i monomial
IR + R, and consider the random variable Y T(X - p4), where X D. The corresponding entry within the tensor (i-(m) [(X; - p) [ has the same distribution as the average of i.i.d. copies of Y. We will bound from above the variance of Y. We will need the following claim regarding expectations of monomials.
Claim D.2. Lett t Z+ be an even integer. Suppose the distribution D has its t-th central moments bounded from above by M. Let T Rd - be a monomial of degree t. Then it holds
E X~D
(T -+)] S 1.M
Proof. Suppose T(X- - (1) -II (X: - m1) where Di=1s =t Then we have
87
E X-D
[T(X -w]l
E
max
[
[x - mul (Xi-Mul)
XmD
iEld];a,20
(IX; (IXI- -x11') [ml')]
E
max [iE|d],,>0
X~D
Σ
E
(X, -me² s tM.
X~D
=E|d]a;;00
where in the first inequality we bound (X; -44) from above by maxig(d)ss XX; M4 in the second inequality we bound the maximum of a set of non-negative numbers by their sum, and in the last inequality we use the fact that there are at most non-zero s "s and that D has its f-th central moments bounded from above by M. This concludes the proof of Claim D.2.
We can therefore bound from above the variance of Y by
Var(Y] > E( 10] (OFF)
where in the last inequality we note that 7 is degree 2/ monomial, and thus we can apply Claim D.2. Hence, by Chebyshev's inequality, we have that
E L (m]
[T(X, - w)]
E IT(X w)]l s (IF/m))
X
with probability at least (d '). then follows from the union bound that
[X, - [~[m
E
E XND I 2) S (tE/m/)
with high constant probability. Lastly, we bound from above ||ا 2.12. Since D has its covariance bouned from above by xI, it holds that the random vector f p has mean 0 and covariance bounded from above by K/ /mm. Hence, the expected squared le norm of the vector is at most kd/m. m. It then follows from Markov's inequality that || Pll2 S kd/m holds with high constant probability. This concludes the proof of Lemma D.I.
The next lemma provides sum of square proof that bounds from above the square of polynomial in terms of its coefficients.
Lemma D.3. Let p(v) a ot for some d' d' matrix A with || Then
p(v) S ad 10//
28
13

---

Batch List-Decodable Linear Regression via Higher Moments
Proof. Since the Frobenious norm of A is most ad', we have that A is bounded from above by ad in Lowner order. Thus, can write y (ad' Tyy@ / A as a sum of squares by diagonalizing 7 and A. The lemma then follows by noting that the expression is exactly ad || p(u).
We can now put these together to get the lemma need.
Lemma D.4. Let D be a distribution over IRd with mean j and t be a positive even integer. Assume that (i) the covariance of D is bounded from above by kl, (ūi) the degree-2t 2t central moments of D is bounded from above by F >> 0, and (iii) there exists M > O such that D has (M,t, K) ccertifabyy bounded moments. Let S = (X1....,Xm, be a set of m Li.d. samples from D. D' be the uniform distribution over S, and Jı == Ex=D' [X]. If m >o (td)" + drM 1aMM-2f 2/t, then DY will have (2++2 M, K) -eerttiiaay bounded moments with probability at least 0.9.
Proof. From Lemma D.1 and that m > (td)"(F/MM)) + dxM -2/t, we have that the fox norm of the difference between the expected and empirical t-th tensors (X (1) 0t of D and D' is small, i.e.
M
E i~/m
[X; 11) 01
E X~D
[X - 11) m)
(8)
vd
and that the empirical mean and the distribution mean are close, i.e.,
|/ - 11 S 1/t
(9)
with high constant probability.
Let g(v)= == Eg-imi im Ku, X1+ -1)01 -xx=D((,, X - -. Combining Lemma D.3 and Equation (8) gives that
E
[(e, -1) XxD 100, --1) -199
b~ [m]]
S Vddlbulbé
E [(X; - 10 (w(m)
E x~n
E - p)
S Mllll
(10)
Observe that
F E F
(1, X; - -
E i~[m)
(1 Xi - w/9
E X~D 1(u, X -139 + E XND
[m(m)
(11)
where in the second line we use Equation (10) and our assumption that D has certifiably bounded central moments.
I Lastly, to prove bounded central moments of D' (the uniform distribution over the samples in S), we note that
[m] [wu X,
S 2
E in [m]]
[1,,
X, 14)9] + 2t E [(v,X,
[Kv, / - m
s 2
E
uu)9] + 1 -Fillé
[m]
2 10
where in the first line we use the SoS triangle inequality (Fact B.2), in the second line we use SoS Cauchy's 's inequality (Fact B. 1),), and the last inequality follows from Equations (9) and (11).
Lemma D.5 (SoS Moment Bound). Let a E (0, 1/2), o>0, E Z 3 E RRd. Let T be a set of m batches drawn according to the distribution D3. defined in Definition 1.1, and batch size n. Assume that the clean covariates distribution X satisfies Assumption 1.2 and io < A/2. Define ZB n E(x Xy. Suppose > ((Akd)&*Q-) + +1) a Then
the following holds with probability at least 0.9: (a) [7. B T) has (M, 2k: 4k) certtifabyy bounded moments for some
M (((k))2 / Q 2o 2 1(2k,, and (b) CovB-T[Ze) = O([I /2)
Proof. We first prove that the population version of the above inequality has SoS proof. Specifically, we show that
[| 1} 44
E [ (ZB - E
lx:)
267
<
(2 2k
n Q (0 + 11))) 22)
(12)
B-D
B
14

---

Batch List-Decodable Lincar Regression via Higher Moments
We rewrite the left hand side
n
)
267
Xiy:
E
[ T X
(N..u))~PP. vie(m)
24
E (N. ViE(n]
X,yi v. (3)))
(13)
n 2k
(u' (Xy - /²))²² 26]
We first show that
is SoS-certifiably bounded. In particular, we claim that
[||111 1}
E
[10 [vT -))) 2k s (2k)* Q (o + +118*12))
(14)
Note that
[11e113 1}
lak
E
(x (Xy-3*))
E (X.))
[ 8r + + X v (²))
(X.y)~~'p
S 3th
[xTxxTT B+) + (xTXE) 2k + (u' (uT 8*) 8
2k
(X.g)~Pp-
where in the last line we apply the SoS triangle inequality (Fact B.2). We then tackle the three terms separately. For the first term, we note that
11l11 = 13
E (X.
Xx
2k
<
||3
2
[(Tx + (X (118"1111*122)
(X.))~Pa
1
12
where in the first inequality we use the SoS AM-GM inequality (Fact B.3), and in the second inequality the assumption that the degree-4k moments of X are SoS certifiably bounded by Q (Assumption 1.2). For the second term, note that
11 =
E
[xTx()) x=)
X 2k
E (X.))~P..
xx)xx)²
2k
E|g2k] S (2k)&
(X
where in the first equality use that X and are independent, and in the second inequality on the moments of X and that the degree 2k moments of & is bounded by (2k)* For the last term, we note that
again the assumption
(v 3*)22 < || gk ||,8* I12 by an application of the SoS Cauchy's 's inequality (Fact B. Combining the above analysis then
shows Equation (14).
By Lemma 3.3, we then have the SoS proof
(T8r) 2k
n Σ v T
flle| 2 1}
L 2 PP viejn]
X
S n² (2K)2* (02h +118-1))))*
(15)
Combining this with Equation (13) then yields SoS proof for Equation (12).
In order to establish an SoS proof for the empirical moments, we will additionally need to bound the covariance of the empirical distribution over (Z } BET. Since an SoS proof on the bound of the covariance is not needed, we can readily apply the L2 La hypercontractivity of X. In particular, this shows that El(u" x)*] < O(1) (E [(" x) < O(L) for any unit vector With argument almost identical the SoS bound on the degree-2N 22 moments, we show that
2
X o7 T
(0
0² + 181
E (X WiEM
50
n
15

---

Batch List-Decodable Linear Regression via Higher Moments
This shows property (b) in the lemma.
Let C' be sufficiently large constant. The SoS proof for the empirical moments then follows by an application of
Lemma D.4 with = 2k, x = C (o² + 118) M = (2k)ar a 2 MMQ-..Qaaa and
Q (o2h + 11 F := (4k) dn
mar Q (o + |19 ك
m > (2kd) Sk 2 Q-1 + d (o² + 113))12) M +
It is not hard to see that
(2kd) 8k 24h Q-++ 2 + (o2 1191)11 M 1/k + 5 (4kd))*Q- + dQ- 1/k + 11) S ((4kd)& Q
where the last inequality can be shown by examining the cases where dQQ 1/k 2 and dQ-1/b < separately. This concludes the proof of Lemma 3.4.
E. Pruning Procedure and its Analysis
The main theorem for this subsection is the following:
Proposition E.1 (Pruning Lemma). Let a E (0, & E (0, k, E Et, o, R > O, and 3 E RR. Let L C Rd be list of candidate regressors, and 3 E L be a regressor such that || 30112 < R. Assume that the batch size n satisfies that >> k Q a -2/k and v //2. Then there exists an algorithm Pruning that takes the list I,, and the numbers a, 6, R as input, draws m O (in (log([L)), d²) log(l/8) a 33) many batches from the corrupted batch distribution of Definitionn 1.I, runs in time (oly(dm) L)). and outputs at most (11/a) candidate regressors L' L such that there is at least one regressor B E L' satisfying || 3 12 S O R ka 1/kkQQ//P /k| /VT) with probability at least 1 ô over the randomness of the batches drawn.
The Pruning algorithm involves two phases: initially, it filters regressors 3 E L by retaining those matching a certain set of solvable linear inequalities. Then, it selects a subset of the remaining regressors, ensuring each pair is adequately distant. Lemmas 3.7 and 3.8 respectively prove that the refined list is not excessively large and contains regressor near the optimal 8 given one exists in the original list L. The proof of Proposition 3.6 follows from the above two lemmas.
For each regressor, restate the set of linear inequalities L, in the weighting function W over the set of batches T.
Σ BET W(B)= 0.9a|T],
(16)
v/ E L such that 11,3' -B1 c R R+ ka 1//00///////v)
/v) for some sufficiently large constant e,
Σ BET
Σ (X.))B
(y x
S Σ (M-XT (X.))B
W(B) < 20
Σ W(B).
(17)
We now show there cannot be too many regressors whose associated linear inequalities are satisfiable subject the constraint that they are all sufficiently separated. This mainly comes from the observation that Condition 17 enforces the soft clusters associated with two sufficiently separated candidate regressors must have small intersection.
Lemma E.2 (List Size Bound). Let R > O, and L be a list of candidate regressors. Let T be a set of batches. Let I,' C L be a sublist of candidate regressors satisfying the following conditions: (1) IE(3; L,T, R) has solutions for each 8 E L', and (2) 0 32ll2 2 c (R + ka 1/k o() 1b vn) for any two 31, B2 E L'. Then it holds the size of is at most O(1/a).
Proof. Let / be a set of weighting functions W : T for weighting functions as follows
+ [0, 1] over batches. We first define the union and disjoint operators
(n ())) (B) = min W(B).
(B) (B)= max W(B),
WET
WeT
WET
WE!
16

---

Batch List-Decodable Linear Regression via Higher Moments
Moreover, for weighting function W > [0, 1I. we define W(T) -BBET W(B). Let 31, B2 be vectors from the sublist 12, and W1, W2 be the solutions of IB(31; T., T, R) and [E(;;; I, R) respectively. We proceed argue that (W) (W))(T < 0.1a (Wi(T) + W2(T)). For the sake of contradiction, we assume that
(Wi (2)))) > 0.1a
(18)
Define the following two subsets of batches:
& B BET: T:
(u E(XOIE (U=XT3))² s ExxxwIB (V-XTBy) BE BEBT T: E (v - xx)) S <(IxwE (y (y-x
and &
x 31))
Since each batch B belongs to either Er or Eg, we have either (W1 n W2) (E1) 2 (W1 n W2) (T) or (W1 n (22 (E)) (W)) (2) Without loss of generality, assume that we are in the former case. This then implies that
Σ { (T=X S (1 BET
(v- - Ba)
M1
2 0.05a (Wi(T) + W2(T))
a Emi(T)
20 BET
which contradicts Equation (17) for 31. This shows the opposite of Equation (18).
Lastly, assume that there more than 4/a many candidate regressors in the sublist L' for the sake of contradiction. Arbitrarily pick = [4/a] many regressors from L,, and let WI...., We be the solutions to the linear inequalities associated with the candidate regressors picked. Then,
1 Uwa (T) 1=1
IT|
2
Wi(T)
Σ (W.nW))(T)
1=1
KSER
Σ
W((T) 0.1a Σ (WI(T) +W,
1=1
(<jE(l]
(1 0.1a(l 11)
1)) Σ WT(T)
2 (1- 0.100.1---00 - 1)a) ((.
> 2.
where in the first line we use the fact that the weights are bounded from above by 1, in the second line we use the approximate inclusion-exclusion principle, in the third line we use the opposite of Equation (18), in the fourth line we use the elementary fact that Eipset (I;; + x2) = (e-1) Ei in the fifth line we use W:(T) 2 0.9ox|7] as they need to satisfy Condition 5, and in the last line Lemma 3.7.
the definition of l [4/a]. This is clearly contradiction, and hence concludes the proof of
Next we show that the set of linear inequalities constructed for some 3 admit solutions with high probability as long 3 is close to 3*
Lemma E.3 (Error Bound), Let a (0, å E (0, n, K E Z,, R> 0, and 3 E Rd. Let L be a list of candidate regressors of size K. and 3 E L be regressor such that ||3 - 10112 < R. Let > k Q2fk a -2/k be the batch size parameter. Suppose T is a set of m > min (log(K), d²) log(1/5) a many batches of size n drawn from the corrupted over the randomness of T, we have that the system
batch distribution of Definition I.I. With probability at least IE(3 L,, T, R) has solutions.
17

---

Batch List-Decodable Linear Regression via Higher Moments
To prove Lemma 3.8, will make essential use of the following anti-concentration inequalities.
Fact E.4 (Paley-Zygmund Inequality). If 2 0 a positive rundom variable with finite variance, and E [0, 1]. then holds
E 2 E 2
Pr[z 2 0E| 2 (1 - 0)²
Combining the above with our distributional assumption that the clean covariates distribution satisfies T2-Ta hypercon- tractivity, we obtain the following weak anti-concentration property.
Corollary E.5 (Weak Anti-concentration). Let be a unit vector in R and X be random unit vector satisfying Assumption 1.2. Then it holds
Pr((uX)²21/3) 2(1))
We are now ready give the proof of Lemma 3.8.
Proof of Lemma 3.8. Let be a regressor within the list such that 1- < R. Our goal is show that the associated linear inequalities [3; L, T, R) admits solutions. In particular, we claim that setting W(B) for all inlier batch B and W(B) 0 for all outlier batch B gives solution. Condition 5 is satisfied since in expectation there should be a-fraction of inlier batches. Since we take C' log( 6 /a² many batches, the actual fraction of inlier batches should be at least 0.9a with probability at least 1 - ā when C' is sufficiently large by the Chernoff bound.
Next we show Condition 6 is satisfied with high probability over the randomness of T. Fix some S satisfying || - 22 > R ka 1/k MQ/////////0 //k /vn. We will analyze the random variable
(B) = Σ 1 x
E (V-XTB)² (X.)~~B
(Xia)~BB
where B ~ Dg-. Recall that we have XT + where & ~ (O), We will rewrite 7(8') slightly with the random
where each (+) is drawn independently from distribution satisfying Assumption 1.2, and each ((i) is independently distributed NN00 o²). We thus have that
variables (((1),
}( ((x()
Z Σ (6' (6'-8 (1B- +2e(1) (B BT)
Tx 10)
Denote the three terms in the summation by:
71 Σ (x- 2 11
n
72 :2 = Σ (B-38))xx0)) 73 = Σ 2c(0 (3- T x(). i=1
We proceed to argue that 2, is bounded from below, and Zz, Z3 are bounded from above with high probability. For Z1, applying the weak anti-concentrratoon property X (Corollary E.5) gives that
Pr -0) 2 1|8 - -- ///2//2 2 7.
for some universal constant 7. By the Chernoff bound, given that > log(1/at, the fraction of ( such that - xx)) 2 1|3 - 8 1B/2 will be at least 7/2 with probability at least a/120. then follows that
n 188 -3-133 > 1 - a/120. 4
Pr
Zi
(19)
For Zzz, since O (x()' 7 by Assumption 1.2, it follows that E E(Zg] n1|.3 13- In order to show that Zg sufficiently concentrated, we will bound from above the k-th central moments of Ze for some even integer k S A. Define
3 Note that there are correlations between Z1, 72, Zg. Nonetheless, these correlations will not affect our analysis.
18

---

Batch List-Decodable Linear Regression via Higher Moments
y/ = ((3 - T ) ?.
We note that the yos are i..d. random variables with their degree-k central moments bounded from
above by
E (x))))
-113 1311)
88) x 2# 2 E [10-
113 8" 1
2 ||3 5 2 Q
where in the first line we apply the triangle inequality (Fact B.2), and in the second line we use the assumption on the degree 2k moments of X. Hence, applying Lemma 3.3 gives that the degree k moment of Zg is bounded from above by
E
Σ
(u
Eieel)
< 2 (4kn) /4/2 |8 1- Q.
In other words, we have that
)1)
1/k
E
(y)
E
E(wl))
S 2/k // V4kn Q 3²12.
By Chebyshev's inequality, we thus have that
Pr 72 | 31 (n+ 1000/n kn Ql/+t] a/120.
(20)
For Z3, note that E[ since g(t) has mean O. To argue for its concentration, we again proceed to bound its degree-k moment for some even integer Similarly, we define 2; = ( 8¹) X The degree-k central moments of 2 can be bounded from above by
(B- =E (5 E (1--
E
We apply the upper bounds on the degree-k moments of g(6) and (0) respectively. This allows to conclude that
E (B)) 8) < 20 11,3 81
Applying Lemma 3.3 then gives that
E
Σ
2i
1/2 1*OO*11 311
In other words, we have that By Chebyshev's inequality, it holds that
1)
1/k
E
Σ
S sknn 1 111122
iml
Pr Zg > 10k/n ||3 - ['112] < a/120
(21)
By the union bound, the events in Equation (19), Equation (20), and Equation (21) are satisfied simultaneously with probability least 1 a:40. When that happens, Za. will be bounded from below by
7
11." 3-1 ||3
113 -1/k
1/k nn 100 kn Q2/k) 10k oQ -1/k 1/4 ||3 - B'112.
(22)
19

---

Batch List-Decodable Linear Regression via Higher Moments
First, we claim that
| 8*1 > || | |8 8*112 (1 o(1))]|B 8'12.
(23)
(24)
To prove Equation (24), we note that
|| - - 1
B112
8 (1 o(1))113 1811.. |13
where the first inequality is the triangle inequality, and the second inequality is true by our assumption that || 3 112
R < ||3' 2. Equation (23) then follows immediately as || B 2| > || - 12
With the above inequalities in mind, we proceed to argue that the positive term dominates all the negative terms in Equation (22). Since y is a universal constant, it follows that
y || 5 112
| - 1----111 11...
Next recall that n. >> k Q2/k a- -/2 by our assumption on n. It then follows that
n 11,3' - 13 > ||3 - 1 100 Q¹/k oz 1/k
Lastly, recall that we assume ||8- >> koQ a 1-11/ 1/k / /n. Combining this with Equation (24) and Equation (23) then gives that - 2 (1-)(1)) 118- > koQ a 1/k Vī, which implies that || - 11 >> then follows that
||3 - 3" I12koQ a ---1 1/k V..
' 11 31 10kvn oQ a -1/h 1/k ||3 8 l2
Combining the above gives that
Pr Zg (B) > 0 > >1 a/40,
(25)
B-Dgg
as long as n >> k Q2/k -2k and ||3 B'112
> R+ ka -0.--// 1/k /Q1////////0/ VVT.
Since the inlier batches are all drawn independently, it holds the faction of inlier batches violating the condition is at most a/20 with probability least 1 6/K² when the number of inlier batches drawn are at least N >> log(K/5) (//8a=-² Since the size of L is at most K, there are at most K - 1 many 3r we need to consider. Condition 6 is therefore satisfied with probability at least - 8 by the union bound.
When we have log K) > dZ, we will need an alternative argument. We note that Z₁ and Zz are both linear functions in the random variables Σ ( (+) of dimension d², and Z: a linear function in the random variables Σー_ g(0) X00
Thus, overall, for any 3" E Rd Z (B) is linear function in O (d²) many random variables. It then follows that, for any 3' Rd. oz (B) 0} is an dddmenddimas linear threshold function, which has VC-dimension Odd²). Let G be
N' >> la log( (1/8) many inlier batches drawn from Dz-. By the VC-inequality, we thus have
Pr sup B'ERd
Pr [ZB(B' > 0] B
(3)(3') 0 B-D
Pr
a/20 S 8.
Combining this with Equation (25) then shows that Condition 6 is satisfied with probability at least
F. Reduction from the Batch-Setting to the Non-Batch Setting
We point out simple reduction (in Claim F.1), which allows one to solve list-decodable linear regression in the non-batch setting using algorithm for the batch-setting in black-box manner. The idea is the trivial observation construct our own batches of size n just by collecting together n individual labeled examples. Denote by the probability that an individual example is inlier. Then the probability that a batch made in the aforementioned way consists only of inliers is a = a Then, running any algorithm designed for the batch setting should yield guarantees where the corruption rate is being replaced by a". In particular, if we denote by m(a d), E(ag) and error(ag) the sample complexity, list size and error guarantee of the black-box algorithm (which are functions of the corruption rate & and maybe other parameters
20

---

Batch List-Decodable Linear Regression via Higher Moments
like the dimension d which do not matter for this discussion), then the resulting algorithm for solving the problem in the non-batch setting will have its sample complexity, lits size and error rate being m(a", d), f(a") and error(a") respectively.
For convenience, throughout this section we will restrict our ourselves to the case than half of the data being corrupted. We are interested only in this since this is the truly "list- "list-decodable setting". For this reason, we will have 1/2 we need < log(1/aB))
1/2, which corresponds to more
1/n thus in order to < log(1/az)) in the claim below (because we have already mentioned that a
Claim F.I. Denote by d the ambient dimension and by E 1/2) the corruption level for the non-batch setting. Let c. O be a sufficiently small absolute constant. Suppose that A is algorithm with the guarantee that for any aB (0,1/2) it can draw m(aB, d) batches of size n. = c /log(1/ap) from the corrupted distribution of Definition 1.1 with corruption level B. and output a list of size (())) of vectors which contains vector 3 with || -3 S error(a Then, there exists another algorithm A' that draws mla" d) batches of size 1 from the corrupted distribution of Definition 1.1 with rate of corruption o, and outputs list of size E(a?") of vectors which contains vector 3 with || B112 s error(a")).
This reduction, in combination with the lower bound of (Diakonikolas et al., 2021), can serve as informal evidence that doing list-decodable linear regression with batch sizes & log(1/aB) likely requires exponential time. In particular, Theorem 1.5 in (Diakonikolas et al., 2021) provides evidence that any algorithm with polynomial sample complexity needs exponential list-size or exponential runtime. Let n = clog(1/ ((/)) for some constant C < 1. If Theorem 1.3 were to allow for that batch size of n = c clog(1/ /a (recall that it right now only works for n > log(1/aB) then, by the reduction above (Claim F.1) we would obtain an algorithm for the non-bate batch setting, with quasi muasi-polynomial runtime and list size which would contradict the hardness evidence.
"By "evidence" mean that the lower bound is only about the Statistical Query model. Although this does imply hardness results for the class all algorithms, SQ lower bounds have long served as strong indication hardness.
21


Reviews:
[{"review_id": "GhPpuR4N1s", "reviewer": "Reviewer_HmAU", "summary": "This paper studies the list-decodable linear regression, under the setting that the algorithm can collect batches of samples. This paper can be seen as a follow-up of Das et al. 2023, which studies the same problem under same batch setting, however uses a batch size $n \\geq \\tilde{\\Omega}(\\alpha^{-1})$, number of batches $m=\\text{poly}(d,n,\\alpha^{-1})$, and outputs a list of $O(\\alpha^{-2})$ vectors at least one of which is $\\tilde{O}(\\alpha^{-1/2}/\\sqrt{n})$ close to the target regressor. This paper, proposing a new algorithm that uses degree-$1/\\delta$ moment information, enjoys a batch size $n\\geq\\Omega_{\\delta}(\\alpha^{-\\delta})$ with $m = \\text{poly}((dn)^{1/\\delta},\\alpha^{-1})$ and outputs a list of $O(\\alpha^{-1})$ vectors at least one of which is $O(\\alpha^{-\\delta/2}/\\sqrt{n})$ close to the target. The algorithm implements a refining idea for regressor using mean estimation from Diakonikolas et al. (2019) and apply a SoS list-decodable mean estimation approach to handle the linear regression in list-decodable setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reading our paper. We respond to the points raised individually below:\n\n(**Tradeoff between batch size and algorithm complexity is not discussed**) There indeed is a tradeoff between batch size and algorithm complexity. However, this is not a hidden aspect of the result. Rather, it is explicitly stated, and it is part of the conceptual take-away point of the paper. We reiterate the main points below for completeness:\nThe tradeoff is clearly presented in Theorem 1.3, where all parameters (batch size, number of batches, and runtime) are formally stated. Specifically, the batch size $n = \\Omega_{\\delta}(\\alpha^{-\\delta})$ and the number of batches $m = \\text{poly}((nd)^{1/\\delta}, \\alpha^{-1})$, referenced by the reviewer, are explicitly given there.\nThe tradeoff is discussed in detail directly after the theorem (lines 93-131). Specifically the discussion paragraph states “Our result essentially shows that there is a smooth tradeoff between the batch size provided and the computational resources required”. The subsequent text points out that if the parameter $\\delta$ is superpolynomial then the algorithm is no longer efficient and that there is evidence in the form of known Statistical Query lower bounds, (discussed further in Appendix F) suggesting that this tradeoff is unavoidable.\nQuantifying this tradeoff is part of the main conceptual contribution of the work: On the one hand, SQ lower bounds from Diakonikolas et al., 2021 suggest that the problem is hard for batch-size equal to one; while Das et al. (2023) gives an efficient algorithm when the batch-size is $\\approx 1/\\alpha$ (see lines 69-81). It is natural to ask what happens in between (lines 91-97). Is there a sharp phase transition (in terms of the existence of a poly-time algorithm) when the batch-size goes from constant to linear in $1/\\alpha$ or does the tradeoff happen smoothly? Our result suggests the latter: when the batch-size is $1/\\alpha^c$, for $c>0$, there exists an algorithm using $O(1/c)$-degree SoS to achieve a small error for the task (lines 112-131). \nIf the reviewer’s concern stems from our use of the term “efficient”, such as in lines 104–108 (“Is there a computationally efficient algorithm […] with improved batch size and/or error guarantees?”), we clarify that “efficient” there refers to poly-time algorithms in general, which is the standard convention in the learning theory literature. This does not imply the absence of trade-offs within the space of poly-time algorithms. If this was the source of confusion, we will revise the phrasing to ensure this distinction is explicit.\n\n(**Clarifications on the algorithmic approach**) We respond to the specific questions below:\n* (*Which mean estimation framework is being used?*) As stated in line 166 of our paper, either Theorem 5.5 from Kothari & Steinhardt (2017), or Theorem 6.17 from Diakonikolas & Kane (2023) suffices for our purpose of list-decodable mean estimation. In general, any list-decodable mean estimation algorithm satisfying the guarantee in Lemma 3.5 suffices for our purpose, and the exact implementation is not important for our algorithm.\n* (*“It is not true that there exists no multi-filter framework using high-moment information. Actually, the very beginning of the multi-filter framework proposed by Diakonikolas et al. 2018 already considered higher moments”*). The proof strategy in Diakonikolas et al. 2018 requires exact Gaussianity of the data (also listed in the their theorem statement). The subsequent work of Diakonikolas et al. 2020 was able to adapt the proof strategy for the case of just bounded covariance data but it did not extend for higher moment boundedness. We refer to Chapter 6 of the book Diakonikolas & Kane (2023) where the difficulties of using higher information is described. To the best of our knowledge SoS based algorithms are the only ones that work with higher moments beyond Gaussian distributions. Thus, we apply an SoS list-decodable mean estimation to the regressor estimator $\\frac{1}{|B|}\\sum_{(X,y) \\sim B} Xy$. Even if $X$ were Gaussian, this estimator would not be, making Diakonikolas et al. (2018) inapplicable. To address this, we show SoS certifiability of the moment bounds by deriving a novel SoS proof of the Marcinkiewicz-Zygmund inequality that may be of independent interest. Finally, we  highlight that the biggest difficulty in our paper is not finding the right algorithm to apply as a black-box but the subsequent issue that applying this algorithm iteratively may result in a number of hypotheses that blows up (see the paragraphs after line 194). Making that iterative framework work is where our novel pruning procedure is used. This procedure is optimal, and uses techniques that differ significantly from prior work of Diakonikolas et al. 2020.\n\nI. Diakonikolas,  D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. STOC 2018.", "claims_and_evidence": "Given that the prior work on batch list-decodable linear regression didn't use high-moment information, the improvement makes senses in some way. \n\nHowever, the algorithm is somehow not clear, maybe due to the complexity of this problem and SoS based algorithms. As stated in the paper, the regressor is estimated using the mean of $yX$, and the list-decodable learning is made possible via implementation of SoS based algorithms for mean estimation. Then, it should be clearly specify which mean estimation framework the algorithm is based on, as the literature for list-decodable mean estimation is well developed. On the other hand, it is not true that there exists no multi-filter framework using high-moment information. Actually, the very beginning of the multi-filter framework proposed by Diakonikolas et al. 2018 already considered higher moments. Hence, I don't see what the challenging part is here.", "methods_and_evaluation_criteria": "The method makes sense, by applying robust linear regression technique together with a list-decodable mean estimator.", "theoretical_claims": "The theoretical claims make sense. It is hard for me to check all of the proofs.", "experimental_designs_or_analyses": "No experiments required.", "relation_to_broader_scientific_literature": "This paper aims to improve upon previous work on batch list-decodable linear regression. The findings on establishing a SoS proof for the Marcinkiewicz Zygmund Inequality, might be of broader interest.", "essential_references_not_discussed": "It seems all are cited.", "other_strengths_and_weaknesses": "There is a key weakness for this paper. As the key contribution is the improvement over the batch size, however, this is at the cost of increasing the number of batches, which is not stated in this paper. The paper nor discusses the total sample complexity and how it is affected by applying different parameter $k$ in its algorithm. To check this closely, although batch size is reduced to $n=\\Omega_{\\delta}(\\alpha^{-\\delta})$, the number of batches $m=\\text{poly}((nd)^{1/\\delta},\\alpha^{-1})$. Hence, to avoid higher number of batches, if $\\delta=1$, the result is essentially the same to Das et al. 2023. Since there are lots of hiding terms, it is hard to verify if this algorithm is truly efficient.", "other_comments_or_suggestions": "It must be specify the tradeoff between batch size and number of batches.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No concerns."}}, {"review_id": "bEiBPBIojT", "reviewer": "Reviewer_ez6k", "summary": "This paper proposes an efficient polynomial-time algorithm for batch list-decodable linear regression, using higher-order moment information within a Sum-of-Squares (SoS) framework. Compared to previous methods, this approach notably reduces both the required minimum batch size and the final regression error. These improvements rely on assuming that the covariates have higher-order moments that are certifiably bounded within the SoS framework. The authors' main innovation is an iterative list-pruning algorithm that leverages these higher moments, enabling stronger performance guarantees than existing techniques.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and positive assessment of our work. We respond to their points below:\n\n(**Distributional assumptions**) The condition of having SoS certifiably bounded moments is standard (in the algorithmic robust statistics literature) for leveraging higher-order moment information in the algorithm. This condition holds for all distributions satisfying the Poincare inequality (Kothari & Steinhardt (2017)), which results in a large family of distributions: it includes Gaussians, product distributions, strongly log-concave distributions, and any sum or uniformly continuous transformation of such distributions. There are also other non-Poincare distributions with SoS certifiably bounded moments, i.e., distributions over discrete points sampled from Gaussians. Moreover, via recent results (Diakonikolas et al. (2024) cited at the end of this rebuttal), it is known that the class of all sub-Gaussian distributions also satisfies the SoS certifiably bounded moments condition. Finally, regarding practicality, if having bounded $k$-th moments for very large $k$ is viewed as unrealistic in practice, we point out that even if we use only the first $k=4$-th order of moment information, our algorithm will have already improved upon the prior work with substantially smaller batch sizes and achieved better error. We thus view our work as an important step towards building practical algorithms for smaller batch sizes.\n\n(**Experimental evaluation**) While we acknowledge the reviewer's interest in experiments and the importance of developing practical algorithms, we would like to emphasize that our primary contribution is to characterize the computational-statistical landscape for this fundamental learning task—in terms of error guarantee, batch size complexity, and batch number, and the tradeoff between them. That being said, there are practical regimes (like $k=4$) where we already get improved error compared to Das et. al. 2023 in poly-time and any other previously known alternative for the same error would require exponential runtime.\n\nReferences:\n\nDiakonikolas, Ilias, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel. \"SoS certifiability of subgaussian distributions and its algorithmic applications.\" arXiv preprint arXiv:2410.21194 (2024).", "claims_and_evidence": "The claims are generally well-supported by rigorous theoretical arguments.", "methods_and_evaluation_criteria": "The proposed methods and/or evaluation criterias are sound and particularly suitable.", "theoretical_claims": "The key theoretical contributions—particularly Lemma 3.3 (SoS Marcinkiewicz–Zygmund inequality)—are clearly and rigorously presented. Additionally, I checked Theorem 1.3 and Proposition 3.1, whose proof techniques are based on reference [1]. The provided proofs appear correct, though very technical.\n\n[1]. Das, A., Jain, A., Kong, W., and Sen, R. Efficient list decodable regression using batches. In International Conference on Machine Learning, pp. 7025–7065. PMLR, 2023.", "experimental_designs_or_analyses": "This paper focuses exclusively on theoretical contributions without empirical validation.", "relation_to_broader_scientific_literature": "The paper places itself clearly within the literature, comparing explicitly and thoroughly with prior works (Das et al. 2023, Diakonikolas et al., 2019, Diakonikolas & Kane, 2023, Kothari & Steinhardt, 2017). It effectively leverages and builds upon known techniques from robust and list-decodable regression, robust mean estimation, and the SoS methodology. It makes a clear advancement in terms of algorithmic complexity relative to Das et al. (2023).", "essential_references_not_discussed": "This paper studies batch list-decodable linear regression via higher moments, where the list-decodable linear regression is provided by [2].\n\n[2] Sushrut Karmalkar, Adam R. Klivans, Pravesh Kothari: List-decodable Linear Regression. NeurIPS 2019: 7423-7432", "other_strengths_and_weaknesses": "Strengths:\n1. Strong theoretical contribution: notably improves upon previous algorithms by leveraging higher moments.\n2. Introduction of novel theoretical techniques (SoS Marcinkiewicz-Zygmund inequality) valuable to the broader theoretical ML community.\n\nWeaknesses:\n1. The assumptions required for significant improvements (e.g., hypercontractivity, bounded SoS-certifiable moments) might limit broader applicability.\n2. No experimental validation, even preliminary, to provide intuition about practical relevance.", "other_comments_or_suggestions": "It will be better if the authors add numerical experiments to validate your theories.", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qxNTrow1Ma", "reviewer": "Reviewer_GB1B", "summary": "First, in the interest of full disclosure, this review is very lightly modified from a review I wrote for this paper for NeurIPS 2024.\n\nThis paper studies a problem in algorithmic robust statistics: batch list-decodable linear regression. The setting is as follows. We get $m$ batches of $n$ samples $(X_i,Y_i)$ each, from a linear model $Y_i = X_i^\\top \\beta + \\epsilon_i$. An $\\alpha > 0$-fraction of the batches are \"good\", ie distributed like above. The remaining $(1-\\alpha)m$ batches are actually chosen by a malicious adversary. The goal is to output a list of possible $\\beta$s, actually $O(1/\\alpha) of them (which is the best you can hope for), one of which is close to the ground truth.\n\nThe motivation for this problem comes from:\n\n- list-decodable regression *without* the batch assumption -- ie just $1/\\alpha$ fraction of samples are \"good\" -- seems to require exponential in $1/\\alpha$ time, per SQ lower bounds\n- in the real world, datasets are often collected in batches, but the batches may be small.\n\nThe paper's main contribution is a new family of polynomial-time algorithms with stronger quantitative guarantees than prior work for this problem. The key improvement is to the size of batches needed. Prior works obtained provable guarantees in polynomial time only when the batch size $n \\gg 1/\\alpha$. By contrast, the present work tolerates really small batches, of arbitrarily small polynomial size -- $n \\gg \\alpha^{-\\delta}$ for any small constant $\\delta > 0$. The tradeoff is that the resulting algorithm requires:\n\n- strong assumptions on $X$: the random variable $X$ for the \"good\" samples must be \"SoS-certifiably bounded\" for moments up to $O(1/\\delta)$. This assumption is satisfied by strongly log-concave distributions and by subgaussian distributions; it is largely unknown what other distributions may satisfy it. (The paper should probably mention the fact that subgaussian distributions satisfy their assumption.)\n- a lot of samples and time: (nd)^{O(1/\\delta)}$ batches and time are needed.\n\nThe algorithm and its analysis borrow a lot of technical ingredients from the now-enormous algorithmic robust statistics literature. It is a little unclear to me to what extend there is a fundamental new algorithmic/analysis idea here, although certainly combining several existing techniques from algorithmic robust stats is on its own a nontrivial matter. The authors suggest that their combination of an iterative list-pruning technique with SoS is novel; I am not sufficiently expert in the specifics of list-decodable estimation to assess the novelty independently.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and the positive evaluation of our paper. We respond to the points raised individually below:\n\n(**Assumptions on $X$**) The SoS certifiability of moments is a well-established condition, known to hold for various important distribution families, including sub-Gaussian distributions and those satisfying the Poincaré inequality. Please see our response to Reviewer ez6k for more details.\n\n(**Sample and Time Complexity**) There is a tradeoff between the batch size and the complexity of the algorithm: Before this work, we only knew that for batch size $n=1$ the problem exhibits exponential complexity hardness results and for $n=1/\\alpha$ it becomes feasible in polynomial time, but we did not know anything in between: Is the complexity interpolating in a smooth way or there is some phase transition phenomenon? One of the main goals of this paper is to quantify this tradeoff and show that it is indeed smooth, which we view as an interesting theoretical insight. As explained in lines 114-131 (first column) although this tradeoff means that for extremely small delta the algorithm becomes efficient, this matches the prior known SQ lower bounds, thus in this sense, this behavior is unavoidable. Moreover, there is a wide range of regimes where the algorithm is efficient. For example setting $\\delta$ to be a constant like $¼$, already gives a polynomial time algorithm that works only under 4-th bounded moment distributions and has better error guarantee than prior work (any algorithm before our work would either have larger error or run in exponential time).\n\n(**Technical contributions**) One of our main technical contributions is a novel pruning procedure to reduce the candidate list size to $O(1/\\alpha)$. This procedure is optimal, and uses techniques that differ significantly from prior work. The procedure is critical for the success of the iterative algorithm as the number of candidate lists will grow exponentially with the number of iterations without pruning. Moreover, although robust mean estimation using SoS is by now a standard tool, our work requires a novel iterative framework where each iteration improves the accuracy of the estimators. Lastly, in order to apply the result from Kothari & Steinhardt (2017), we need to show that the fact that the covariate has certifiably bounded moments implies that the regressor estimator we use also has SoS certifiably bounded moments, which is technically non-trivial. Finally, in order to apply SoS robust mean estimators for the variable $yX$ we need to ensure certifiability of moments, for the purpose of which we prove an SoS version of the famous Marcinkiewicz Zygmund Inequality, that might be useful independently of the result of this paper.\n\n(**Motivation of Studying Batch-size in Robust Statistics Tasks**) Once again, we would like to emphasize the importance of studying the role of batch size in robust statistics. While the common assumption in robust statistics is that an arbitrary subset of data points (with a certain size bound) is corrupted, in the crowdsourcing setting, adversarial corruption naturally happens at a user-level, leading to corrupted batches of data instead of corrupted data points. As shown in Diakonikolas et al. (2021) and Das et al. (2023), such batch structure in corruption may lead to drastic change in the computation landscape of the statistical estimation task, and we believe it is a natural as well as important research direction to explore the quantitative relationship between batch size and other algorithmic resources needed in robust estimation tasks.  Our work is the first revealing a smooth quantitative tradeoff between batch sizes and the computation/statistical resources needed for the concrete application of list-decodable linear regression. \n\nOn the practical side, we believe that optimizing the batch-size is crucial to any crowd-sourcing setting. In particular, if only 1% of users were reliable, prior work would roughly require one of the following: Either each user provides one data point, but the learning algorithm has exponential complexity Karmalkar et al. (2019), or (ii) each user will have to contribute at least $100$ data points Das et al. (2023) (which may well be unrealistic). On the other hand, we give an efficient algorithm that succeeds with much fewer data points per user; prior to our work, it was not clear if this is even possible in polynomial time. In particular, even if we use only the first $k=4$-th order of moment information, our algorithm will have already improved upon the prior work with substantially smaller batch sizes and achieved better error. We thus view our work as an important first step towards building practical algorithms for smaller batch sizes.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "no", "experimental_designs_or_analyses": "n/a", "relation_to_broader_scientific_literature": "thoroughly discussed in the introduction to the paper; I will not repeat the discussion here.", "essential_references_not_discussed": "none", "other_strengths_and_weaknesses": "## Strengths\n\nPushes the frontier of polynomial-time guarantees for a well-motivated problem in robust statistics. Reasonably well written.\n\n## Weaknesses\n\nWhile batch list-decodable linear regression itself seems like a reasonably well-motivated problem, I see only moderate motivation for the goal of obtaining algorithms tolerating smaller batch size if the resulting algorithms have impractical (albeit still polynomial) running time. Given that algorithmic robust statistics has been under intense investigation for almost a decade now, I think a strong new paper should ideally either:\n\n1. introduce a fundamental new algorithmic or lower-bound technique, overcome a serious technical barrier, etc., and/or\n2. make headway in pushing the many new theoretical ideas from the last 10 years towards the realm of practical algorithms/impact beyond theory.\n\nI think this paper is making some contribution on both types of goals, but not groundbreaking contribution on either. For (1), the paper is indeed pushing the frontier of polynomial-time algorithms, but it is hard to tell if there's a really new technique here, versus clever combination of existing ideas. For (2), although pushing for smaller batch sizes is a well-motivated practical goal, the paper is hamstrung by its reliance on higher-moment techniques and SoS which give very large polynomial running time.\n\nStill, I think the problem is appealing enough and the results will be appreciated by the ICML audience.", "other_comments_or_suggestions": "none", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mzxbyoG4An", "reviewer": "Reviewer_gZA8", "summary": "In modern machine learning, collecting large datasets from a single source is often impractical. Instead, data is typically gathered in batches from multiple sources. This paper investigates the $\\textbf{batch list-decodable linear regression}$ problem: given pairs $(X, y) \\in \\mathbb{R}^{d+1}$ drawn from the distribution $D_{\\beta^*}$ such that $y = {\\beta^*}^\\top X + \\xi$, where $\\xi \\sim \\mathcal{N}(0, \\sigma^2)$, we are provided with $m$ batches, each containing $n$ samples. With probability $\\alpha$, a batch consists entirely of i.i.d. samples from $D_{\\beta^*}$, while with probability $1-\\alpha$, the batch is drawn from an arbitrary distribution. The goal is to compute a list $L$ of vectors $\\widehat{\\beta}$ such that at least one $\\widehat{\\beta}$ satisfies that $\\\\|\\widehat{\\beta} - \\beta^*\\\\|_2$ is small.   \nCompared to the prior work [DJKS'23], which reduced the batch size dependency from exponential in $1/\\alpha$ to linear, this paper further improves the batch size and achieves lower estimation error by leveraging the higher-order moment assumptions through the Sum-of-Squares (SoS) framework.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and positive assessment of our work. We reply to the points mentioned individually below:\n\n(**Applicability of the SoS-certifiability Assumption**) SoS certifiability of moments is by now a well-studied condition that is known to hold for broad families of interest such as sub-Gaussian distributions and all distributions satisfying the Poincare inequality. Please see our response to Reviewer ez6k on this.\n\n(**Comparison of runtime with Das et al. 2023**) As discussed in lines 91-107, the runtime of Das et al. 2023 is $\\mathrm{poly}(d,n,m,1/\\alpha)$. Their theorem statement does not specify what is the absolute constant in the exponent of that runtime. In comparison, our algorithm is also polynomial time but the parameter $k$ appears in the exponent (order of the higher moment information used) instead of just an absolute constant. \n\n(**Quasi-polynomial runtime for very small batch sizes**) It is indeed true that the algorithm is no longer polynomial-time when the batch size becomes very small (e.g., when $k$ is on the order of $\\log^2(1/\\alpha)$). As discussed after the main theorem statement (lines 115–131), there is evidence (based on previously known Statistical Query lower bounds from Diakonikolas et al. 2021) that this phenomenon is inherent. We view this as an interesting conceptual conclusion: The tradeoff between complexity and batch size appears to be smooth. Specifically, for $n = 1/\\alpha$, the complexity of our algorithm matches the previously known algorithm of Das et al., 2023, while for $n = \\log^2(1/\\alpha)$, it matches known SQ hardness results. In the intermediate regime, our results suggest a continuous interpolation rather than a sharp phase transition at a specific point.", "claims_and_evidence": "Yes, the claims in this paper are clearly stated and rigorously supported by detailed proofs.", "methods_and_evaluation_criteria": "The main result of this paper is purely theoretical and is thoroughly validated through rigorous theoretical analysis.", "theoretical_claims": "The proofs seem correct since I didn't read all the proofs carefully.", "experimental_designs_or_analyses": "No experiments in this paper.", "relation_to_broader_scientific_literature": "(1) The use of higher moments and SoS-based techniques could be applied to other robust regression settings, such as sparse linear regression or generalized linear models, where outliers or heavy-tailed noise are common.  \n(2) The batch setting considered in this paper shares similarities with mixed linear regression, where each batch could correspond to a different component of the mixture. Extending the SoS-based approach to estimate multiple regression components simultaneously would be an interesting direction.   \n(3) The SoS framework might be leveraged to design robust algorithms for list-decodable PCA under the batch setting, especially in the presence of corruptions or outliers.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "$\\textbf{Strengths:}$ (1) The proposed algorithm improves the performance of previous works by requiring smaller batch sizes and achieving better error guarantees, and provides a flexible tradeoff between batch size and computational complexity.  \n(2) This paper leverages higher-order moment information under the SoS framework to improve the robustness and accuracy of the estimation.   \n(3) This paper provides the first SoS proof of the Marcinkiewicz-Zygmund Inequality, which could be useful in other robust estimation tasks.   \n$\\textbf{Weaknesses:}$ (1) The proposed method relies on SoS-certifiably bounded moments, which might limit its applicability to more general distributions.  \n(2) The algorithm is polynomial in the dimension and batch size but can become quasi-polynomial for very small batch sizes.", "other_comments_or_suggestions": "It would clarify the generality of the proposed method if this paper could discuss the tightness of the SoS assumptions.", "questions_for_authors": "This paper is closely related to the work of Das et al. [DKS'23]. Could you compare the running time of the proposed algorithm with that of [DKS'23]?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Overall, the reviewers agree that the key theoretical contributions of the paper are insightful. They are clearly and rigorously stated, and might be of broader interest. Nevertheless, some of the reviewers raised concerns about the problem setting and significance, which should be carefully addressed.
Decision: Accept (poster)