Robust Sparse Regression with Non-Isotropic Designs
Authors: Chih-Hung Liu
Gleb Novikov
Venue: NeurIPS 2024 poster (2024)
Keywords: linear regression
sparse regression
robust regression
sum-of-squares
Primary area: learning_theory

Abstract: We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries: oblivious and adaptive.
Consider the model $y^*=X^*\beta^*+ \eta$ where $X^*$ is an $n\times d$ random design matrix, $\beta^*\in \mathbb{R}^d$ is a $k$-sparse vector, and the noise $\eta$ is independent of $X^*$ and chosen by the \emph{oblivious adversary}. 
Apart from the independence of $X^*$, we only require a small fraction entries of $\eta$ to have magnitude at most $1$. 
The \emph{adaptive adversary} is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples $(X_1^*, y_1^*),\ldots, (X_n^*, y_n^*)$.
Given the $\varepsilon$-corrupted samples $(X_1, y_1),\ldots, (X_n, y_n)$, the goal is to estimate $\beta^*$.  
We assume that the rows of $X^*$ are iid samples from some $d$-dimensional distribution $\mathcal{D}$  with zero mean and (unknown) covariance matrix $\Sigma$ with bounded condition number.

We design several robust algorithms that outperform the state of the art even in the special case of Gaussian noise $\eta \sim N(0,1)^n$. 
In particular, we provide a polynomial-time algorithm that with high probability recovers $\beta^*$ up to error $O(\sqrt{\varepsilon})$  as long as  $n \ge \tilde{O}(k^2/\varepsilon)$, only assuming some bounds on the third and the fourth moments of $\mathcal{D}$. 
In addition, prior to this work, even in the special case of Gaussian design $\mathcal{D} = N(0,\Sigma)$ and noise $\eta \sim N(0,1)$, no polynomial time algorithm was known to achieve error $o(\sqrt{\varepsilon})$ in the sparse setting $n < d^2$.  
We show that under some assumptions on the fourth and the eighth moments of $\mathcal{D}$, there is a polynomial-time algorithm that achieves error $o(\sqrt{\varepsilon})$ as long as $n \ge \tilde{O}(k^4 / \varepsilon^3)$. 
For Gaussian distribution $\mathcal{D} = N(0,\Sigma)$, this algorithm achieves error $O(\varepsilon^{3/4})$. 
Moreover, our algorithm achieves error $o(\sqrt{\varepsilon})$ for all log-concave distributions if $\varepsilon \le 1/\text{polylog(d)}$. 

Our algorithms are based on the filtering  of the covariates that uses sum-of-squares relaxations, and weighted Huber loss minimization with $\ell_1$ regularizer.  We provide a novel analysis of weighted penalized Huber loss that is suitable for heavy-tailed designs in the presence of two adversaries. Furthermore, we complement our algorithmic results with Statistical Query lower bounds, providing evidence that our estimators are likely to have nearly optimal sample complexity.

Robust Sparse Regression with Non-Isotropic Designs
Chih-Hung Liu Department Electrical Engineering
National Taiwan University chliugntu, eddw
Gleb Novikov
Lucerne School of Computer Science and Information Technology gleb. neribnovviovhhhl..cc
Abstract
We develop a technique design efficiently computable estimators for sparse linear regression in the simultancous presence of two adversaries: oblivious and adaptive. Consider the model y" x + 1l where X* is an и X d random design matrix, 8* Rd is s-spasse vector, and the noise 7 is independent of X" and chosen by the oblivious adversary. Apart from the independence of X we only require small fraction entries of 17 to have magnitude at most 1. The adaptive adversary is allowed to arbitrarily corrupt an e-fraction of the samples (X,, yj)...., (X,, n V,) Given the E-corrupted samples (X1, yı), (X., yn), the goal is to estimate B². We assume that the rows of X" are iid samples from some d-dimensional distribution D with zero mean and (unknown) covariance matrix Σ with bounded condition number. We design several robust algorithms that outperform the state of the art even in the special case of Gaussian noise 1 ~ N(0, 1)". In particular, we provide polynomial-time algorithm that with high probability recovers 8 up to error O(V)) long as > Ö(k2/e) /E), only assuming some bounds on the third and the fourth moments of D. In addition, prior to this work, even in the special case Gaussian design D NO, Σ) and noise 1J ~ N(0, 1), no polynomial time algorithm was known to achieve error o(VE) in the sparse setting that under some assumptions on the fourth and the eighth moments of D, there is polynomial-ting algorithm that achieves eтror O(VE) as long > Ö(k- e²)). For Gaussian distribution D N00, Σ), this algorithm achieves error 1443)) Moreover, our algorithm achieves error ((ve) for all log-concave distributions if & // /pooyllogdd..
d², We show
Our algorithms are based on the filtering the covariates that uses sum-of-squares relaxations, and weighted Huber loss minimization with & regularizer. We provide a novel analysis weighted penalized Huber loss that is suitable for heavy-tailed designs in the presence of two adversaries. Furthermore, we complement our algorithmic results with Statistical Query lower bounds, providing evidence that our estimators are likely to have nearly optimal sample complexity.
Introduction
Linear regression is the fundamental task in statistics, with many applications in data science and machine learning. In ordinary (non-sparse) linear regression, we are given observations .i...., V/, and X,, X E Rdd such that y; (X, 8¹) + for some B E Rd and some noise 1] E IR", and the goal
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is to estimate B². If is independent of X" and has iid Gaussian entries yT; ~ N(, 1), the classical least
squares estimator / with high probability achieves the prediction error Note that if d - O, the enror is vanishing.
- -B)Il O ((d/n))
VR
Despite the huge dimensions of modern data, many practical applications only depend on a small part of the dimensions of data, thus motivating sparse regression, where only k < d explanatory variables are actually important (i.e.. 8 is k-sparse). In this case we want the error to be small even if we only have < d samples. In this case, there exists an estimator that achieves prediction
error Of yk log(d)/n) (for N(0, 1)"). However, this estimator requires exponential computation time. Moreover, under a standard assumption from computational complexity theory (NP & P/poly), estimators that can be computed in polynomial time require an assumption on X' called restricted eigenvalue condition in order to achieve error Of y log(d)/n
(see [ZWJ14 for more details). One
efficiently computable estimator that achieves error O (vv Io under the restricted eigenvalue condition is Lasso, that is, a minimizer of the quadratic loss with regularizer. In particular, the restricted eigenvalue condition is satisfied for X with rows X; fid N(0,)) where Σ has condition number O(),, as long 2 k log d (with high probability).
Further we assume that the designs have iid random rows, and the condition number of the covariance matrix is bounded by some constant. In addition, for random designs, we use the standard error [ Bl) Note that when the number of samples is large enough, this error is very close to J ( (*)
V2
Recently, there was an extensive interest in the linear regression with the presence of adversarially chosen outliers. Under the assumption X iid N(O, Σ), the line of works TISO14 BIKK17 [BR]19]
dNS21 2L studied the case when the noise 1] is unbounded and chosen by oblivious adversary, i.e., when is an arbitrary vector independent of X". As was shown in [JLN*21]. in this case, it is possible to achieve the same error (up to a constant factor) as for 1 ~ N(0, 1)" if we only assume that Q(11) fraction of the entries of 17 have magnitude at most 1. They analyzed the Huber loss estimator with f regularizer.
Another line of works [BJK15] DT19, MNW22 Tho23) assumed that 17 has iid random entries that satisfy some assumptions on the moments, but adversarially chosen e-fraction of yir..., yi is replaced by arbitrary values by an adaptive adversary that can observe X", B" and 1j (so the corruptions can depend on them). [Tho23] showed that for X" with iid sub-Gaussian rows and rj with iid sub- Gaussian entries with unit variance, Huber loss estimator with & regularizer achieves an
error of O y log(d)/n e log(1/e)) with high probability. Note that the second term depends on E, but not on nı; hence, even if we take more samples, this term does not decrease (if remains the iid same). It is inherent: in the presence of the adaptive adversarial outliers, even for X; N(0, Id) and 17 ~ (O, 1)", the information thcoretically optimal error is 22 Vk log(d)/n + e). so independently of the number of samples, is Qee). In the algorithmic high-dimensional robust statistics, we are interested in estimators that are computable in time poly(d). There is evidence that it is unlikely that poly(d)-time computable estimators can achieve error O(e) [DK117]. Furthermore, for other design distributions the optimal error can be different.
Hence the natural questions to ask are : Given an error bound f(),, does there exist a poly(d)-time computable estimator that achieves error at most f()) with high probability? If possible, what is the smallest number of samples that is enough to achieve error f() time poly(d)? In the rest of this section, we write error bounds in terms of and mention the number of samples that is required to achieve this error. In addition, we focus on the results for the high dimensional regime, where f(e) does not depend polynomially on k or d.
considered the case when the adaptive adversary is allowed to corrupt g e-fraction of all observed data, i.e. not only .i...., Vn. but also X .,, X;, while the noise 17 is assumed to have iid random entries that satisfy some concentration assumptions. For simplicity, to fix the scale of the noise, we formulate their results
Another line of works [BDLS17 LSLC20 P1L20
Sas22
SF23
2

---

assuming that 17 ~ N(0, 1)". . In npa-sp settings, [PL20 showed that in the case of identity covariance sub-Gaussian designs, Huber loss minimization after proper filtering of X" achieves error Ó(e) with 2 e samples. Informally speaking, filtering removes the samples X; that look corrupted, and if the distribution of the design is nice enough, then after filtering we can work with (X", y²)" just like in the case when only y is corrupted. For unknown covariance they showed a bound (ve) for a large class of distributions of the design. x; n e (dP/E²) samples to robustly estimate the covariance, and achieve nearly optimal error Ö(e) in the case (see DKS19 for more details).
iid N(0, Σ) for unknown I, one can use
gap for the sample complexity of this In the sparse setting, there is likely an information-compuraa problem, even in the case of the isotropic Gaussian design X; iid N(0, Id). While it is information- theoretically possible to achieve optimal error O(E) with > Ō(k/=²) samples, achieving any error (11) is likely to be not possible for poly(d)-time computable estimators if < k2. Formal evidence for this conjecture include reductions from some version of the Planted Clique problem [BB20], as well as a Statistical Query lower bound (Proposition 1.10). For > Ö(k2/e) several algorithmic results are known to achieve error Ö()), in particular, [BDLSI7 LSLC20, and FF23 for more general isotropic sub-Gaussian designs. Similarly to the approach of P1L.20 (fi-penalized) Huber minimization after filtering X"
used
The non-isotropic case (when Σ * Id is unknown) is more challenging. [SF23 showed that for uub-Gaussian designs it is possible to achieve error (VE) with > Ö(k) samples. [Sas22] showed that (Vv) error with n > Ō(k² + || K2) samples can be achieved under some assumptions on the fourth and the eighth moments of the design distribution. While this result works for large class of designs, the clear disadvantage is that the sample complexity depends polynomially on the norm
of B". For example, if all nonzero entries of B have the same magnitude and || = Vd, then the sample complexity is n > d², which is not suitable in the sparse regime.
Prior this work, no poly(d)-time computable estimator that could achieve error o (VE) with unknown E was known, even in the case of Gaussian designs X; 7 NO0, 1)" (apart from the non-sparse setting, where such estimators require n > d²).
iid N(0, Σ) and the Gaussian noise
1.1 Results
We present two main results, both of them follow from a more general statement; see Theorem B.3 Before formally stating the results, we define the model as follows.
Definition 1.1 (Robust Sparse Regression with 2 Adversaries). Let n, n, N such that k & d, o > 0, and ε E (0, 1) is smaller than some sufficiently small absolute constant. Let 2 be a probability distribution in Rd with mean 0 and covariance Σ. Let y = X + 17. where X' is an n X d random D. 8 E Rd k-sparse, E I is independent of X" and has at least 0.01 n entries bounded by in absolute value]] We denote by x(E) the condition number of Σ.
matrix with rows x; iid
An instance of our model is a pair (X, where X E nxd is a matrix and y E RR is a vector such that there exists set Sgood [nz] of size at least (1 E)n such that for all E S Sgood, X; = X; and yi = V
Note that random noise models studied prior works are captured by our model in Definition I.I For example, if 17 has iid entries that satisfy B/ns < a/2, by Markov's 's inequality. Inml & with probability at least 1/2, and with overwhelming probability, at least 0.01 π entries of 1j are bounded by in absolute value. In addition, Cauchy noise (that does not have the first moment) with location parameter 0 and scale a also satisfies these assumptions, as well as other heavy-tailed distributions studied in literature (with appropriate scale parameter σ).
Our result also works for more general model, where we require an entries to be bounded by for some 2 E. The error bound in this case also depends
3

---

We formulate our results assuming that the condition number of the covariance is bounded by some constant: x(L) & O()). the most general formulation (hhorem B.3). we show the dependence of the number of samples and the error on x(I).
1.1.1 Robust regression with heavy-tailed designs
We use the following notion of boundness of the moments of D:
Definition 1.2. Let M 0, > 2 and d E N. We say that a probability distribution D in Rd with zero mean and covariance Σ has M-bounded t-th moment, for all R
B X-D (x, u)1"
1/1 & M VIEII |u|l
Note that an arbitrary linear transformation of an isotropic distribution with M-bounded t-th moment also has M-bounded 1-th moment. Also note that if 1' & and distribution D has M-bounded 1-th moment, then the 1 1'-th moment of D is also M-bounded. In particular, M cannot be smaller than 1, since the second moment cannot be M-bounded for M < 1. In addition, we will need the following (weaker) notion of the boundness of moments:
Definition 1.3. Let 0, 1 > 2 and d N. We say that probability distribution in Rd with zero mean and covariance Σ has entrywise v v-bounded 1-th moment, if
E |xyl' & v' // X-D
max jE[
If a distribution has M-bounded f-th moment, then it also has entrywise M-bounded 1-th moment, but the converse might be true for some distributions. Now we are ready to state our first result.
Theorem 1.4. Let d, k, X, E, D, o, be in Definition 1.1, Suppose that x(Σ) & O(1) and that for some 1 & M O(1) and 1 & & O(1), has M-bounded 3-rd moment and entrywise v-bounded 4-th moment. There exists an algorithm that, given X,y, y, k, E, in time (n d)o( outputs E Rd such that if z x2 log(d)/= E, then with probability at least 1 -10
| - f')ll < O(a Vt).
Let us compare Theorem 1.4 with the state of the art. For heavy-tailed designs, prior to this work, the best estimator was [Sas22]. That estimator also achieves error O(ovE), but its sample complexity depends polynomially on the norm of f", while our sample complexity does not depend on In addition, they require the distribution have bounded 4-th moment (as opposed to our 3-rd moment assumption). and bounded entrywise 8-th moment (as opposed to our entrywise 4-th moment assumption). Finally, noise assumption is weaker than theirs since they required the entries of rj to be iid random variables such that B|nj < o' for some o' > 0 known to the algorithm designer; as we mentioned after Definition I.] is special case of the oblivious noise with 20'.
Let us also discuss our assumptions and possibilities of an improvement of our result. The third moment assumption can be relaxed, more precisely, it is enough to require the f-th moment to be bounded, where t is an arbitrary constant greater than 2, and in this case the sample complexity is increased by constant factof see Theorem B.3 for more details. The entrywise fourth moment assumption is not improvable with our techniques, that is, we get worse dependence on k if we relax it to, say, the third moment assumption.
The dependence of on E is not improvable with our techniques The dependence of the error on o optimal. The dependence of n on and the error on Ve is likely be (nearly) optimal: Statistical Query lower bounds (Proposition and Proposition 1.11) provide evidence that for O(1), it is unlikely that polynomial-tima algorithms can achieve error o(1) if и & k2, or error of o(vē) if и & k4. Remark 1.5. Our results also imply bounds on other types of error studied in literature. In particular, observe that l 11 < 1B // Amin(E)) where Amin (I) is the minimal eigenvalue of Σ.
We did not aim to optimize this dependence. 3This factor depends M and x(E), as well on f. In particular, it goes infinity when 2. *Some dependence of on e is inherent, but potentially our dependence could be suboptimal. For sub- exponential distributions it is possible to get better dependence, see Remark 1.9 a.9 Appendix H

---

In addition, our estimator also satisfies /| f'11 & 1 -B'Il (k/Amin(E)) ( The same is also true for our estimator from [Theorem 1.7 below. These relations between different types of emror are standard for sparse regression, and they are not improvable.
1.1.2 Beyond VE error
Prior to this work, no polynomial-time algorithm for (non-isotropic) robust sparse regression was known to achieve error ((ovE) even for Gaussian designs X; iid N(0, Σ) and Gaussian N(0, a)". In this section we show that for a large class of designs, it is possible achieve error o( Vε) in polynomial time, even when 1j is chosen by an oblivious adversary. For our second result, we require not only some bounds on the moments of 2) but also their certifiability in the sum-of -quuarrssseesss proof system:
Definition 1.6. Let M > 0 and let f be an even number. We say that a probability distribution D Rd with zero mean and covariance Σ has f-certifiably M-bounded 4-th moment, if there exist polynomials ,I,..., Am E ....,..., of degree at most 8/2 such that
B (x, u)* x-D
> 1=1
h2(u) = M ||||| ||a||*
Definition 1.6 with arbitrary & implies[Detiniees Definition 1.2 (with the same M). Under standard complexity- theoretic assumptions, there exist distributions with bounded moments that are not f-certifiably bounded even for very large [HL19]. Note that similarly to Definition 1.2, an arbitrary linear transformation of isotropic distribution with Ê-certifiably M-bounded 4-th moment also has f-certifiably M-bounded 4-th moment.
Distributions with certifiably bounded moments are very important in algorithmic robust statistics. They were extensively studied literature, e.g. [KS17a KS17h HL.I8 HL.99
2K
Now we can state our second result.
Theorem 1.7. Let n, d, k, X, y, E, D,,,,,,, be as in Definition 1.1 Suppose that x(Σ) O(1) O(1), D has t-certifiably
and that for some M > I, some even number > 4, and I M M-bounded 4-th moment and entrywise v-bounded 8-th moment. There exists an algorithm that, given X, y, k, E, J, M,,, in time (n + djolt) outputs B e Rd such that if n & M 1 log(d)/ then with probubility least 1 1100
|2 --''ll & O(M M. 63/4)
In particular, in the regime M < O(1), as long n > O(K*/E2), the algorithm recovers 3* from (X, y) up to eиrог 3/4) (with high probability). If & O(1), the algorithm runs in polynomial time. Note that in this theorem we do not assume that M is constant as opposed to Theorem 1.4 since for some natural classes of distributions, only some bounds on M that depend on d are known.
The natural question is what distributions have certifiably bounded fourth moment with O(1). First, these are products of one dinenninnnio distributions with M-bounder fourth moment, and their linear transformations (with 4). Hence, linear transformations of products of one-dimensional distributions with ((1)-bounded 8-th moment satisfy the assumptions of the theorem with M & O(1) and Note that such distributions might not even have a 9-th moment. This class also includes Gaussian distributions (since they are linear transformations of the N(0, 1)d and N(0, 1) has O(1)- bounded 8-th moment).
Another important class is the distributions that satisfy Poincaré inequality. Concretely, these dis- tributions. for some Cp > 1, satisfy Var,- g(x) & C ||_|| Ex- for all continuously differentiable functions g : I - R. KS177a showed that such distributions have 4-certifiably D(Cr)-bounde) fourth moment. We will not further discuss Poincaré inequality, and focus on the known results on the classes of distributions satisfy this inequality.
The Sannan-Lovászz -iovnssz-imoooiiss (KLS) conjecture from convex geometry says that Cp is bounded by some universal constant for all log-concave distributions. Recall that a distribution D is called log-concave if for some convex function V Rd - K. the density of D is proportional to e V(x).
5

---

Apart from the Gaussian distribution, examples include uniform distributions over convex bodies, the Wishart distribution and the Dirichlet distribution ([Pré7]), see also [KBJ00] for further examples). In recent years there has been a big progrees towards the proof of the KI.S conjecture. [Che22] showed that Cp & dd(1), and since then, the upper bound has been further significantly improved. The best current bound is Cp & Olylog d) obtained by [Kla23]. This bound implies that for all log-concave distributions whose covariance has bounded condition number, the error of our estimator is O Vlog d c3/4), Hence for e & o (d)) and & O()), the error is o o(vE). Note that if the KLS conjecture is true, the error of our estimator is ((4g2/4) for all log-concave distributions with x(2) & O(1), without any restrictions on E (except the standard S 1).
Remark 1.8. Theorem 1.7 1.7can can be generalized as follows: If the (2t)-th moment of is M-bounded for constant f E 222 if this bound can be certified by a constant degree sum-of- squares proof and D has entrywise (4t)-th O(1)-bounded moment, then with high probability, there is poly(d)-time computable estimator that achieves error O(Moe)-1/21) as long as n & x log(d)/ 2111 See Theorem B.3 for more details.
Remark 1.9. The dependence of n on & can be improved under the assumption that D is sub- exponential distribution. In particular, all log- log-concave distributions are sub-exponential. Under this additional assumption, in order to achieve the error O it is enough to take n & k2 polylog(d) + k log(d)/ e, and to achieve error O(Mae3/4) it is enough to take и & k* polylog(d) ()) + k log(d)/ e/22 samples (assuming, as in Theorem 1.7 that the fourth moment is M-certifiably bounded).
1.1.3 Lower bounds
We provide Statistical Query (SQ) lower bounds by which our estimators likely have optimal sample complexities needed to achieve the errors O(ve) and of (ē)) even when the design and the noise are Gaussian. SQ lower bounds are usually interpreted as a tradeoff between the time complexity and sample complexity of estimators; see Appendix G and [KS17] for more details. Our proofs are very similar to prior works OKSITIDKSII DKK 22 since was observed in [DKS19], lower bounds for mean estimation can be used to prove lower bounds for linear regression, and we use the lower bounds for sparse mean estimation from [DKS17 DKK |22
Let us fix the scale of the noise o = The first proposition shows that already for E Id, k2 samples are likely to be necessary to achieve error o(1)
Proposition 1.10 (Informal, see Proposition G.9). Let n, nition 1.1 Suppose that D = NO, Id) and n NO0, 82 where 0.99 < ō < 1. Suppose that d 0000 < k < Vo,
o, be as in Defi
Viogd' and n < k1.99 Then for each SQ algorithm A that finds such that llş - B11 & 10 the simulation of A with n samples has to simulate super-polynomial (ex)(d number of queries.
Note that under assumptions of PProposition 1.10. Theorem 1.4 implies that we take n > k2 polylog(d) samples, the estimator achieves error O ((E) that is o(1) if as - co.
The second proposition shows that for Σ = Id, K4 samples are likely to be necessary to achieve error o(vē):
Proposition 1.11 (Informal, see Proposition G.10 Lei n, d, X, V,E,D,E,,, be in Defini tion 1.1 Suppose that D = NO, Σ) for some Σ such that 1 < Σ = Id. and n N(0, 82 where 0.99 < l & 1. Suppose that d 0000 < k & Vd, E 2 logd and n & k3.99. Then for each SQ algorithm A that finds B such that IIBr - - < Ve, the simulation of A with n samples has to simulate super-polynomial (exp(d)())) number of queries.
Note that under assumptions of Proposition 1.11 Theorem 1.7 implies that if we take n > ka polylog(d) samples, the estimator achieves error ( that o(ve) if 0 as d co.
SSee Definition B.2 for formal definition.

---

2 Techniques
Since the problem has multiple aspects, we first illustrate our approach on the simplest example
X lid NO, Σ) under the assumption that 0.1 ld 3 3 10 Id. Note that already in this case, even for 1 N(O, 1)", our estimator from Theorem 1.7 outperforms the state of the art. In addition, assume that o = 1.
Our estimators are based on preprocessing X. and then minimizing & -ipeaaaleedd Huber loss. In the Gaussian case, the preprocessing step consists only of fittrrng, while for heavy-tailed designs, an additional truncation step is required. The idea of using filtering before minimizing the Huber loss first appeared in [PIL220] for the dense settings, and was applied to sparse settings in [Sas22 SF23
We will not discuss the filtering method in detail, and rather focus on its outcome: It is a set & S [m]] of size at least (1 - O(=))n n that satisfies some nice propertie Further, we will see what properties we need from S, and now let us define the Huber loss estimator.
Definition 2.1. For [n], the Huber loss function restricted S defined as
Hs((p) = # Σ h(((.. - yi) where h(x,) LES
if [x < 2: 2/x;| 2 otherwise.
1 x 2
For a penalty parameter A, the fi-penalized Huber loss restricted to is defined as Ls(8) == Hs(B)+ + A- [| We use the notation (xx) for the derivative of lt(x). Note that for all x, |6(x)] < 2.
Our estimator is the minimizer ßg of LB((), where Š is the set returned by the filtering algorithm. To investigate the properties of this estimator, it is convenient to work with elastic balls. The k-elastic ball of radius is the following set: (r) := (u Rd ||^|| & sr, IIulli & vk. Note that this ball contains all k-sparse vectors with Euclidean norm at most r (as well as some other vectors). Elastic balls are very useful for sparse regression since if the following two properties hold,
1. Gradient bound: For all E Eg(r), IVHg, u>l s oi || + r||u|l,
2. Strong convexity on the boundary: For all и E Ex(r) such that [|u|] =
Hg(p" + u) - Hg(l") - (VHg, u) > Q(12),
then for an appropriate choice of the penalty parameter A, then || 8sll
Hence it is enough to show these two properties. In the Gaussian case, the strong convexity property can be proved in exactly the same way as it is done in [dLN*21] for the case of the oblivious adversary. while for heavy- designs it is significantly more challenging. Since we now discuss the Gaussian case, let us focus on the gradient bound. Denote HG(B) Σies h ((X; B) - v/) By triangle inequality,
KVHg, u)l KVH.
Spwaans 11) (VHs s n u) KVH u)l IVH.
IVV [n]
u)1 I(VH
S u)l
Since the first term can be bounded by I/V im |l [|u|| it is enough to show that IIV In S v/v where r is the error we aim to achieve. Note that VHūm + Σm= (X;;) u) does not depend on the outliers created by the adaptive adversary. The sharp bound on I1VHi,yllas can be derived in exactly the same way as in 21] (or other prior works): Since 17 and X" are independent and (6(n) < 2, VHr [n] is a Gaussian vector whose entries have variance (1/ By standard properties of Gaussian vectors, [[VHi, & O(vlog(d)/n) with high probability.
'Technically, the tiltering we returns weights of the samples. For simplicity assume here that the weights are 0 or 1.
For simplicity, we omit some details, e.g. we need to work with Er-(r) instead of (r) where k' 2 k. See Theorem A.3 the formal statement. Similar statements appeared in many prior works on sparse regression.
7

---

To bound the second and the third term, we can use dependence on the error (like it is done in prior works on robust sparse regression. for example.
inequality and get ((v))
[Sas22] or [SF23), or use Hölder's inequality and get better dependence, but also more challenges since we have to work with higher (empirical) moments of X and X. Let us use Hölder' sineuulliy and illustrate how we work with higher moments. Note that both sets [n] \ (Soood O S) and S S have size at most OEE).. Hence the second term can be bounded by
0(E2/4)
Σ
(x;; O(E214)
< ie[m]
(X; 11) ,)))
while the third term is bounded by
EE uxx,, O(E21)) iESwaNS
E icS
u
A careful probabilistic analysis shows that with high probability, for all > 0 and all Eg(r), Eid[n] / H((;, u>* & O(Iull+), Hence, our requirement $ is that Σics 1/4 u)+ & 0(1) for all u E (1) (by scaling argument, it is enough to consider r = 1). If we find such set S, we get the desired bound. Indeed, if n & k log(d)/ e 3/2, |V [|ll < 0(E3/4/VB) and the other terms bounded by O(e3/*,, implying that ||@ Aull < r = O(e3/4)
Note that such sets of size (1 - On)) exist since good satisfies this property. It is clear how to find such a set inefficiently: we just need to check all candidate sets S and maximize the quartic function Eies(X; u over checking all the sets: If we can maximize Eies u)* over ı E (1) efficiently, we can also find the desired set efficiently.
Ex(1), Furthermore, the by-now standard filtering method allows to avoid
Before explaining how we maximize this function, let us see how prior works [DLS17 SF23) optimized simpler quadratic function Eies u)² over u E E((.). They use the basic SDP relaxation for sparse PCA, that is, they optimize the linear function Eies (X, U) over B, :=
{U E R U Z O, Tr(U)) & ||Ll||, & k). This set has been used in literature for numerous sparse problems since it is nice (perhaps the best) convex relaxation of the set S; = (uu u E R., R < 1, ||uu|lo < k)- Moreover, crucially for sparse regression, it is easy to see that Bg also contains all matrices Hu such that и (1). Hence, one may try to optimize quartic functions by using relaxations of Sx fu u Rd ||||| < 1, ||ullo & k). A natural relaxation is the sum- of-squares with sparsity constraints. [DK 22) used these relaxations for sparse mean estimation Ri They showed that these relaxations provide nice guarantees for distributions with certifiably bounded 4-th moment, assuming that the distribution has sub-exponential tails. Since we now discuss the Gaussian case, the assumption on the tails is satisfied. However, there is no guarantee that these relaxations capture 11 04 for all u E (1). So, for sparse regression, we need another relaxation.
We use the sum-of-squares relaxations with elastic constraints. These constraints ensure that the set of relaxations Px IRdd is guaranteed to contain 3 for all и &x(l). We show that if Ö(k-), there is degree-O(1) sum-of-squares proof from the elastic constraints of the fact that Eiejm (Xi, u & O(1). It implies that the relaxation is nice: If _ (Xes u)* & O(1) for all u E (1), then n (x u) < O()) for all U E Px. Since we can efficiently optimize over Pk. we get an efficiently computable estimator with error ((43/) for Gaussian distributions. Furthermore, if we first use a proper thresholding (that we discuss below), our sum-of-squares proof also works for heavy-tailed distributions, that, apart from the certifiably bounded 4-th moment (that we cannot avoid with the num-of-squares approach), are only required to have entrywise bounded 8-th moment.
Robust sparse regression with heavy-tailed designs is much more challenging. Again, for simplicity assume that 0. Id 2 Σ 3 10 Id and a = 1. First, there is an issue even without the adversarial noise: IVH oo can be very large. Even under bounded fourth moment assumption, it can have magnitude /4 /nt), which is too large in the sparse setting. Hence we have perform additional thresholding step and remove large entries of X. Usually thresholding of the design matrix should be
&These relaxations were also used in 4KNS20 in the context of sparse PCA, but they used them in different way.
8

---

done very carefully since it breaks the relation between X and y. [Sas22 required the thresholding parameter to be large enough and depend polynomially on [1 so that this dependence does not break significantly. Since ir can be as large as Ó(T/n), the sample complexity of their estimator also depends polynomially on II
Our idea of thresholding very different, and it plays a significant role in our analysis, especially in the proof of strong convexity. Since we already have to work with outliers chosen by the adaptive adversary, we know that for an e-fraction of samples, the dependence of y on X can already be broken. So, if we choose the thresholding parameter to be large enough so that with high probability only affects an e-fraction of samples, we can simply treat the samples affected by such thresholding as additional adversarial outliers, and assume that the adaptive adversary corrupted 2 samples. Note that since D is heavy-tailed, each sample X might have entries of magnitude dd(1), However, y depends only on the inner products (X;,,")) (B"), that correspond to the support of g". Even though we don't 't know the support, we can guarantee that for > 20/k/E, E, all entries of X, from the support of 8r are bounded by t with probability 1 1 e/2. Indeed, since the variance of each entry is bounded by 10, Chebyshev's 's inequality implies that this entry is smaller than with probability at least 1 - =/(2k), and by union bound, (Xi,8" is not affected by the thresholding with probability - E/2. Hence by Chernoff bound, with overwhelming probability, the number of samples affected by our thresholding is at most en.
and this inner product depends only on the entries of X*
Let us denote the distribution of the rows of X" after thresholding with parameter T by D(t). After the thresholding step. we can assume that X; iid ~ D(r). Note that thresholding can shift the mean, i.c. E XX; can be nonzero. It is easy to see that [[Ex= xllco & O(17)). Hence by Bernstein's 's inequality, IIV & 6 (V/n + 7/n + 1/T) with high probability In particular, in order get the error bounded by O(e)1t, need to take 2 vk/e3/6 and it affects sample complexity. Furthermore, our sum-of-squares proof requires that ||: (x:) 04 -(()) 8d is smaller that 1/k². It can
be shown that this quantity is bounded by δ V 1/n + / + 1/7*) with high probability 10 In
particular, we need n > Ö(r*k2), so for 2 vk/e2/4, we have to take n > O(K/ As was discussed in Remark 1.9 if D has -ubeexxpnential tails, we do not have to do the thresholding, and the bounds from DKK allow to avoid this dependence of on E. Note that due to the SQ lower bound (Proposition 1.11). sample complexity k is likely to be necessary, even for Gaussian designs.
Finally, let us discuss the strong convexity property. Here, we do not assume any properties related to sum-of-squares, and focus on the weak assumptions Theorem 1.4] First, assume that we need to show strong convexity only for sparse vectors, and not for all u E (r). As was observed in prior works on regression with oblivious outliers, e.g. [JLN+211, p(u) == Hg + +u) - Hg( (VHg, u) can be lower bounded by (Xi, 2 (Ixx,,)) 1:1ss |Ix.,,)<]]] Let C(u) goodd n ASSSAABB B(u), where A is the set of samples where Ind < and B(u) (i [m] 1(X;, u)l < 1). Then, p(u) > Q ((iccc()) (X;, u)²). It can be shown that for some suitable and for each k-sparse of norm r, C(u) is a large subset of the set A (of size at least Al) Note that since A is independent of X", the rows of X" that correspond to indices from A are just iid samples from D. If X; were Gaussian, we could have applied concentration bounds and prove strong convexity via union bound argument over subsets of size 0.99|A]. A|. In the ceavy-tailed case, we need a different argument. For a fixed set C of size |.99| Al, we can use Bernstein's 's inequality" m We cannot use union bound argument over all subsets of size |.99|A| (there are too many), but fortunately we do not need it since for each k-sparse u of norm r, it enough to show that (X; u)² > Q(r²), where T(u) C A is the set of the smallest (in absolute value) A| entries of the vector XA E RIAI, Hence, we can use an epsilon-net argument for the set of k-sparse vectors u (of norm r). This set has very dense nets of
9 'Here we used the fact that ((n)) & 2.
10 [2L2222 used thresholding for robust sparse mean estimation, and showed a similar bound for second- order tensors. We generalize it higher order tensors.
ll Using a standard truncation argument. See also Proposition C.I. of PJL20 for a similar argument in the dense setting.
9

---

(relatively) small size, and this is enough to show the lower bound Ziec(u) (X; u)? > Q(72) for all k-sparse u of norm with high probability, as long as n Ō(k2).
In order to show the same bound for all и & Ex(r) of norm r, we observe that 12 if a quadratic form is ((22) K-sparse vectors of norm for some K k, then it is also ( all E (x(r), and applying the argument from the previous paragraph to K-sparse vectors, we get the desired bound. We remark that directly proving it for u e Ex(r) is challenging, since we extensively used the properties of the set of sparse vectors that are not satisfied by Ex(r), c.g. the existence of very dense epsilon-nets of small size.
3 Future Work
There is an interesting open problem in robust sparse regression that is not captured by our techniques. For sparse mean estimation, in the Gaussian case, there exists a polynomial time algorithm with nearly optimal guarantees: It achieves error O(E) with k polylog(d)/= samples (IDKK*22l) This algorithm uses a sophisticated sum-of-squares program It is reasonable to apply the techniques of [DKK= 22 to robust sparse regression in order to achieve nearly optimal error O(ž) with poly(k) samples. However, simple approaches (e.g. our approach with replacing the sparse constraints by the elastic constraints) fail in this case. Here we provide high-level explanation of the issue. In order to combine the filtering algorithm with their techniques, we need to check whether the values of a certain quartic form are small on all sparse vectors. The analysis in [DKK 22 shows that this form is indeed small for the uncorrupted sample with high probability (see their Lemma F.2.). Since we want have
the filtering algorithm to be efficient, find a sum-of-squares (or some other nice relaxation) version of the proof from [DKK*22) However, in their proof they use covering argument, and it reasonable relaxations that we have thought about. Both potential outcomes (either an algorithm or a computational lower bound) are interesting: An algorithm would likely require new sophisticated ideas, and a lower bound would show significant difference between robust sparse regression and robust mean estimation, while, so far, the complexity pictures of these problems have seemed be quite similar.
a relaxation of sparse vectors. Hence need to
clear how avoid it. This argument fails for
Another interesting direction is to get error (E) for distributions that do not necessarily have certifiably bounded moments, As was shown in [HL19), only moment assumptions (without certi- fiability) are not enough for efficient robust mean estimation, and the same should be true also for distribution D can make the problem solvable
linear regression. However, other assumptions in polynomial time. For robust mean estimation, some symmetry assumptions are enough even for heavy-tailed distributions without the second momen [14] (see [NST23)). It is interesting to investigate what assumptions on the design distribution are sufficient for existence of efficiently computable estimators for robust sparse regression.
Acknowledgments and Disclosure of Funding
Chih-Hung Liu is supported by Ministry of Education, Taiwan under Yushan Fellow Program with the grant number Taiwan with the grant number 11
and by National Science and Technology Council,
12mimilar arguments are sometimes used to prove the restricted eigenvalue property of random matrices.
A similar program for the dense setting was studied in KKZ22 14 Andd in some sense, even without the first moment, if instead of the mean we estimate the center of symmetry.
10

---

References
[BB20]
Matthew S. Brennan and Guy Bresler, Reducibility and cuatstical-computaie gaps from secret leakage, Proceedings of the 33rd Annual Conference on Learning Theory (COLT), vol. 125, 2020, pp. 648-847.
[BDLS17] Sivaraman Balakrishnan, Simon S. Du, Jerry Li, and Aarti Singh, Computationally efficient robust sparse estimation high dimensions, Proceedings of the 30th Conference on Learning Theory COLT 2017, pp. 169-212.
[BJK15] Kush Bhatia, Prateek Jain, and Purushottam Kar, Robust regression via hard thresholding, NIPS, 2015, pp. 721-729.
[BJKKI7] Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar, Consistent robust regression, Advances in Neural Information Processing Systems (I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds.),
vol. 30, Curran Associates, Inc., 2017.
[Che21] Yuansi Chen, An almost constant lower bound of the isoperimetric coefficient in the kls conjecture, 2021.
[DKK*22] Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas, Robust sparse mean estimation via sum of squares, Proceedings of the 35th Annual Conference on Learning Theory (COLT22), Proceedings of Machine Learning Research, 2022, pp. 4703-4763.
[DKLP22] Ilias Diakonikolas, Daniel Kane, Jasper C. H. Lee, and Ankit Pensia, Outlier-robust sparse mean estimation for heavy-tailed distributions, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022 (Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, eds.), 2022.
[dKNS20] Tommaso d' J'Orsi, Pravesh Kothari, Gleb Novikov, and David Steurer, Sparse pea: algo- rithms, adversarial perturbations and certificates, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2020, pp. 553-564
[DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, Statistical query lower bounds for robust estimation of high- dimensiimnn gaussians and gaussian mixtures, Proceedings the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS17), 2017, pp. 73-84.
[DKS19] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart, Efficient algorithms and lower bounds for robust linear regression, Proceedings of the 30th Annual Symposium on Discrete Algorithms 1S0DA19), 2019, pp. 2745-2755
[d]N*21] Tommaso d' O'Ori,, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, and Stefan Tiegel, Consistent estimation for pea and sparse regression with oblivious outliers, Advances in Neural Information Processing Systems 34 (2021), 25427-25438.
[dNS21] Tommaso d' O'Osi,, Gleb Novikov, and David Steurer, Consistent regression when oblivi- ous outliers overwhelm, Proceedings of the 38th International Conference on Machine Learning, (ICMI. 2021) (Marina Meila and Tong Zhang, eds.), 2021, pp. 2297-2306.
[DT19] Arnak S. Dalalyan and Philip Thompson, Outlier-robust estimation of sparse linear model using & fi-eenalized huber's 's M M-estimator, Proceedings of the 32nd Annual Confer- ence Neural Information Processing Systems (NeurIPS19), 2019, pp. 13188-13198
[HL18] Samuel B. Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, 2018, pp. 1021-1034.
[HL19]
How hard robust mean estimation?? ?, Proceedings of the 32nd Annual Confer-
ence Learning Theory (COLT19), 2019, pp. 1682.
[KBJ00]
Samuel Kotz, N. Balakrishnan, and Norman L. Johnson, Continuous multivariate distri-
butions: Models and applications, Wiley, 2000.
[Kla23]
Bo's az Klartag, Logarithmic bounds for isoperimetry and slices of convex sets, 2023.
11

---

[KMZ22] Pravesh K. Kothari. Peter Manohar, and Brian Hu Zhang. Polynomial-time sum-of- squares can robustly estimate mean and covariance of gaussians optimally, Proceedings of The 33rd International Conference on Algorithmic Learning Theory (Sanjoy Dasgupta and Nika Haghtalab, eds.), Proceedings of Machine Learning Research, vol. 167, PMI.R, 29 Mar-01 Apr 2022, pp. 638-667
[KS17a] Pravesh K. Kothari and Jacob Steinhardt, Better agnostic clustering via relaxed tensor norms, CoRR abs/1711.00 77..7.66666 (2017).
[KS17b] Pravesh K. Kothari and David Steurer, Outlier-robust moment-estimation via sum-of- squares, CoRR abs/1711.11581 (2017).
[Las01] Jean B. Lasserre, New positive semidefinite relaxations for nonconvex quadratic programs, Advances in convex analysis and global optimization (Pythagorion, 2000), Nonconvex Optim. Appl., vol. 54, Kluwer Acad. Publ., Dordrecht, 2001, pp. 319-331. MR 1846 160
[LSLC20] Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis, High dimensional robust sparse regression, Proceedings of the 23rd International Conference on Artificial Intelligence and stics AISTATS 2020, 2020, pp. 41
[MNW22] Stanislav Minsker, Mohamed Ndaoud, and Lang Wang, Robust and tuning-free sparse linear regression via square-rool slope, arXiv preprint arXiv:22100 20.0. 16808 (2022). Yurii Nesterov, Squared functional functtion systems and optimization problems. High performance optimization, Appl. Optim., vol. 33, Kluwer Acad. Publ., Dordrecht, 2000, pp. 405-440.
[Nes00]
MR 1748764
[NST23]
Gleb Novikov, David Steurer, and Stefan Tiegel, Robust mean estimation without mo- ments for symmetric distributions, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023 (Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz, Hardt, and Sergey Levine, eds.), 2023.
[Par00]
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustmess and optimization, Ph.D. thesis, California Institute of Technology, 2000.
[PJL20]
Ankit Pensia, Varun S. Jog, and Po-Ling Loh, Robust regression with covariate filtering: Heavy tails and adversarial contamination, CoRR abs/2009. 12976 (2020).
[Pr871]
András Prékopa, Logarithmic concave meusures with application to stochastic program- ming, Acta Scientiarum Mathematicarum (1971), 301-316.
[RH23]
Philippe Rigollet and aan-Christian Hütter, High-dimensional statistics, 2023.
[Sas22]
Takeyuki Sasai, Robust and sparse estimation of linear regression coefficients with heavy-tailed noises and covariates, CoRR abs/2206.07594 (2022).
[SBRJ19] Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain, Adaptive hard thresholding for near-optimal consistent robust regression, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA (Alina Beygelzimer and Daniel Hsu, eds.), Proceedings of Machine Learning Research, vol. 99, PMLR, 2019, pp. 2892-2897
[SF23]
Takeyuki Sasai and Hironori Fujisawa, Outlier robust and sparse estimation of linear regression coefficients, CoRR abs/2208. 115922 (2023).
[Sho87]
N. Z. Shor, Quadratic optimization problems, Izv. Akad. Nauk SSSR Tekhn. Kibernet. (1987), no. 1, 128-139, 222. MR 939596
[Thoo3]]
Philip Thompson, Outlier-rouust sparse/low-rank least-squares regression and robust matrix completion, 2023.
[TJSO14] Efthmmoss Tsakonas, Joakim Jaldén, Nicholas D. Sidiropoulos, and Bjöm Ottersten, Convergence of the huber regression m-estimate in the presence of dense outliers, IEEE Signal Processing Letters 21 (2014), no. 10, 1211-1214.
[Tro15] Joel A. Tropp, An introduction to matrix concentration inequalities, Foundations and Trends in Machine Learning 8 (2015), no. 1-2, 1-230.
[ZWJ14] Yuchen Zhang, Martin J. Wainwright, and Michael I. Jordan, Lower bounds on the performance of polynomiall-ime algorithms for sparse linear regression, Proceedings of the 27th Annual Conference on Learning Theory (COLT14), 2014, pp. 921-948.
12

---

A Properties of the Huber loss minimizer
Definition A.I. For oo the weighted Huber loss function is defined
Σ w; - yi) where hxxx)) = 2|x;| otherwise. ic|n)
x
if [x, < 2;
(B)
For a penalty parameter A, the fi-penalized Huber loss restricted to S is defined as (B) =
(B) A ||
Lemma A.2. Suppose that w E R, u E R4, yı, v2, A > 0 satisfy the following properties:
1. |> wrd(n; + (x)),,)) & yallull1 y2||=1//u]
2. À > 2
3. (B + 11) + A |1B u|l; H=(B") + A. 118'11
Then
||l|| & /4vk/omin + 2/2/2) -2 ||
where Omin the minimal eigenvalue L.
Proof. K = supp(("). Note that
I1 + ull; ||B. "x ux|l |11"11, + ||| |1
By the convexity of Hw.
Hp u) (B') >
w, + (x)(),))
-Allull//2 1alll1/2-22/111 -22
Hence
0 > A (IIB* + uI1, 111*11)) + Hap + ++ Xu) - Haw (1 + ()
> A (||اع|| [| -lll||l - 1 ||,5 - 7/2
> A |||ح||| ] 1/2.
Therefore,
A|lul| & 41 2y2 2/22|= ///////
+ + E1/2u|
41
I
1/2 u
2y2
11/
min
Theorem A.3. Let p, 7/2 > and
Ayk/ommn 1/2
= 100
P
p
where Jmin is the minimal eigenvalue of Let k' > 100k/ Omin Consider the k' -lastic ellipsoid of
radius r:
Ex((r) = Rdd || & 1ull & Vk. r].
Suppose that the weights w IR" are such that the following two properties hold:
1. Gradient bound: For all Ex((r),
wip(n + (T), &illulh 12/12122111.
13

---

2. Strong convexity on the boundary: For all E (x((r such that |= =
Hw (B" + 1)) H.w 7
wid(n (x))) + t..02.
Let
Omin
A > 2y1 + 122
Then the minimizer 8 of the weighted penalized Huber loss with penalty and weights w satisfies
1 BT) <r.
Proof. Let Å - | < r, we get the desired bound. Otherwise, u be the (unique) point in the intersection of (r) and the segment [0, à] C Rd. By convexity of the penalized loss, (1 + C+ Xx) + à I1B + u/l; < (1 + () à |1
Since E (r),(r), either | u or ||u||1 Vk r. Let show that the latter is not possible.
Since > 2y1, we can apply Lemma A.2
Vk (4vk/ 2/2/1)
Cancelling and using the bound A y2 the strong convexity and the gradient bound,
we get a contradiction. Hence || By
HB + +u) (H)
Σ +G) u)
+ +p-
///2
>> p 82 1/11 |||u|l1 y/2 1/2
= pp.r2 2 f11 ||u||] - -727.
Note that
HB + u) (B') < A (1181),, - 11B* + =Il,) < A/lu/|h
By putting the above two inequality together and by Lemma A.2, we have that
p p. < A|llW/] y2r 61 6k/okmmmnn r 5y2r
Dividing both sides by p. get
Avk/omii
1/2
< 100
+
P
p
contradiction. Therefore, |||//||||
B Heavy-tailed Designs
First, define bit more general model than Definition 1.1
Definition B.1 (Robust Sparse Regression with 2 Adversaries). Let d, N such that k & d,
O, (0, 1] and a. Let D be probability distribution in Bd with mean 0 and covariance
14

---

E. Let y' +J. where X is an d random matrix with rows x; uid D. 8 Rd is k-sparse, E R" is independent of X and has at least a n entries bounded by o in absolute value
An instance of our model is a pair (X, y), where X E BRa is a matrix and y E IR" is a vector such that there exists set ggoud [n] of size at least (1 E) such that for all 5 ggood X, = X and yi = Vi. Definition B.2. Let M > O, N. and let > 2f be an even number. We say that probability distribution in Rd with zero mean and covariance Σ has f-certifiably M-bounded (2t) ythh moment, if there exist polynomials li,..., hm R[ui...... Hal of degree at most 8 f/2 such that
B 1) X-D
n2(w)= M -1E=11 ||u||
In this section prove the following theorem
Theorem B.3 -eeavy-tailedd designs, general formulation). Let n, d, E, be in Definitionn B.1 and let E (0, 1).
Suppose that for some > 2, t E N. Ms, M2i > 1, and even number { > 2t, D has My-bounded s-th moment, and e-certifiably Ma bas-ouudd (2f) -th moment. addition, D has entrywise y-bounded (4f)-th moment.
There exists an algorithm that, given X, y, e,, E, M2,, t, and mmx such that ||Σ]|| max such that if
O(] in time (n + d)ott) outputs X' E Badd and weights wo =
10100
M (MB)
v Al (10*M.) S
(x(E) + x(E)2)
11 Z
k2 log( ()/5)
2
then with probability at least 1 6. the weighted fi-penalized Huber loss estimator Bun B (X', (X', ,)
with weights w (as in Definition 2. 1 and parameter ht satisfies
Ma xx()
1/2 12 81]]| <0
a O 6
a.4and Let us explain how this result implies Theorem and Theorem 1.7
Theorem 1.4is a special case of Theorem with 1, 3, f 2, My = 1, M, M, 0.01. Indeed, we only need to estimate |[]] up to a constant factor. We can do it by estimating the variance of the first coordinate of D. Applying [[)]
algorithn (T to the first coordinate, we to the variance of the first coordinate of. Note that
get an estimator 5² that ||X]/x((2) & of ||_|| Since in Theorem 1.4 k<E) and v are constants, and & is sufficiently small, we get that 2x(2] |||| < 22 max < 2 [| Hence for constant C > k x{E,, δmax = 2C is the desired
estimator of ||_||.
Similarly, Theorem 1.7 is special case of Theorem B.3 with = 2, s = 4, Ma. = M = M, 0.01.
[=]| can be estimated using the procedure described above.
Before proving the theorem, note that we can without loss of generality assume that o = 1. Indeed, since is known, can simply divide X and y by it before applying the algorithm.
B.1
Truncation
We cannot work with X directly since it might have very large values, and Bernstein inequality that we use for random vectors concentration would give very bad bounds if work with X', Fortunately,
Our result also works for more general model, where we require entries to be bounded by for some 2 e. The error bound in this case also depends a. 16See, for example, Fact 2.1. from [DKLP22), where they state the guarantees of the median-of means algorithm.
15

---

we can perform truncation. This technique was used in [DKLP22 for sparse mean estimation and in
Sas22 for sparse regression.
For 0 let (1) xi
[Ig]ET]] Note that since P [ π <
| if VIEIIk/e.
then the number of entries where (x;, * (x((t),)))))))) is at most en with probability at least
1 1 2- > 1 6/10. Hence in the algorithm we assume that the input is X'(t) instead of X', and we treat the entries where (Xi, # (X((T),B* BO) corrupted by an adversary.
Concretely, further we assume that we are given (x((()) yi, ) such that y = (z) + where (T) E Rnx differs from (z) E R only in rows from the set Sbad C [n] of size at most En (where e < & & O())). Ç R" is an En-sparse vector such that supp(C) S Soad. 8² E R k- k-sparse vector, and r R" oblivious noise such that least an entries do not exceed I in absolute value.
In addition, we define
B
We=
W R" Vie [n] 0 <
< 1/n,
Σ
wi > (1 E)m
The weights for the Huber loss will be from We. Appendix E will discuss more properties of the truncation.
B.2 Gradient Bound
Lemma B.4, Let b, V1 > O. Suppose that w E We and Rd sarisfy
Σ sE[H]
1i (X) < b | !
u))
<b²L $bt.11172
Je(u]
and
(
y
Then
Σ wio(n (x) u)
< y ||ll| + +6 6-bl/5/21) (0 21
u). It is linear function of w, so [F(w)] is maximized in one of the vertices of the polytope W/ This vertex corresponds set S. of size at least (I z). That is, the weights of the entries from S. are 1/n, and outside of Sn the weights are zero. follows that
Proof. Denote F(w) =
wip(n + (x)
wx((n) u)
Σ w))(() u)
Σ
woΦ(n (x)()()))
(Triangle Inequality)
iESh
y1 ||u]] +2 Σ
xx(x +2
Σ
(I(x((T), + +2 Σ
(,),
#ES
16

---

27
21
y ---lllll
4. 1- 27
Σ #
(x((t))
28 21
Σ ic[m]
wi (x))
(Hölder's inequality)
1 1//221 11
y |all 6.
b
The following lemma provides bound //:
Lemma B.5. With probability at least - 5/100
((t)) i
< | log(d/0) 107 log(d/8) 2n ||_11/T.
Proof. It follows from Bernstein's 's inequality Fact 1.1 and the fact that
Σ
(4())) [Bx]()] < (T) & 2n ||El//,
i=[n]
where we used Corollary E.4
B.2.1 Strong Convexity
Lemma B.6. Suppose that 10002, 7 2 1000 ,2. || Vk" (r (Omin) and
2 ((k")2 log + k" log( // (8)) 10t (ss (s- x ((I))==/(6-2))
where k" 104. k' |لl|| Then with probability 1 for all u E Ex((r) such that || = r.
H(8- + +u) H(B))
wiΦ(n (X) u) + 1
Proof. Denote Agoot Sood n A, where A is set of entries i such that Imj & 1. Note that A is independent of X*. follows that
H(f" + u) -H(") Σ w; + (,),;;
Σ wi (Xi, u) 11n mox
1=1
wi wi((X(t)) u) 1mml ((x)))))))))))))
iES
W
w
(X((T), ()
[[(x(())a)11 )
iEAged
w (8,, 2 (((8,)))11]
iEAged
where 8, 1 /110//1 V /I X,(T).
Denote F(w)= EicApmn wi( w (x, u) 11(xa))< It linear function of w, maximized in
one of the vertices of the polytope W. This vertex corresponds to set Sn of size at least (1 n) That is, the weights of the entries from S., are 1/n, and outside of S.,, the weights are zero.
Σ
wi (X:, u)² [[((8.0)111] >
Σ iCAguanns
(Xi, { [((x))))1]]
iCAgoed
17

---

Hence we need lower bound for EicAoo (X;, u). where
A(u) = Agood n Sw n E [u]] uX) & 1].
In order to bound ΣicAgo (x x)² for vectors from the elastic ball (r) we first show that is bounded for -spaees vectors u' for some large enough k First we need to show that Eier ( (xi, u²) well-concentrated for fixed set I. Concretely, we need the following lemma:
Lemma B.7. Suppose that T > 1000 M2 v2. || Vk" (r for some k" N. Then for fixed (independent of X) set I size
| 2 ((K") log d + k" log(1/0)) 10 (0/2211-222200)1 222 x(2))+ -
for all K" k"-sparse vectors u' Rd such that r & || < 2r.
0.99. 1112 & + (x), 1.01 1|
iCI
with probability at least 5.
Proof. First let us show that
0.995 B(X;, u²)² < u'), < 1.005 (OxS-B( u²)²
Since for each set K of size k", B (x((())) Ejex B/ E(x;(T))
< 2||E||K" by Markov's
inequality,
P p]l(( 10105/16-2), 1 k"
1010s/(s-2). M M22/(6-21, k<I))/(s-2)
Denote B 105s/(s-2). M x(E) E| k". By Hölder's inequality, for all vectors u' Rd with support K,
B(x((T), = B(Xi(T), u 2 |11(((()) (X((T),) u²) "
< <B(X,, u²) 2 2B((X; |11(( ||=8| + +2B((x(t) X7, u², u²)
(B(x)
2
2v 1|211 11
=B(X,, 2 [[(()))))
||||| ||u||
1(X u²) + 1010 x(E)
2r /10
< B Xi u² ) + 2r 102/1010 2
where we used Lemma E. and the fact that || un 111 & k"Il''n'T|| < k"]/u/2 By Corollary E.5 B(X;, u²) - 2r 110 < 0.995.B(X, u²² 0.999 B (X((T))) u²)² B(X,, u' )²)² 1.001 < 1.005-B(X;, u²)²
(x) < <(X;; n²) )² 2 Hence
For a fixed set K of size k" and for all unit vectors u' E Rd with support K, by Bernstein inequality for covariance Fact 1,2] with probability 5,
|E|| log(d/5)
B² log(d/5)
Xi, u²)² - -B(X,, n²)²
< 1000
||u0112
|7|
[]]
iCI
|| Ba log(d/0)
B² log(d/8)
4000
.,2
0- [
Omin
18

---

In order to make this quantity smaller than r2/1000, it is sufficient to take [Z] M
/ ft-l x(E)2+5/(6-2) k" log(d/0).
By union bound over all subsets K of [d] of size k", we get the desired bound.
Let us bound the size of A(u)- Agood n Sww has size at least (a 3Z)n > 0.997an. By Lemma B.7 and Lemma F.2
|Xu]|² & 1.1 anr? hence at most 3anr2/h & 0.00lan entries of Xu can be greater than h/2. Therefore, |A(x)] > 0.99
Let k" = min { [/[0= independent of X' By union bound, the result of B.7 also holds for all I that correspond the bottom 0.99-fraction of entries of vectors (Xu") .) where u" are from an (1/n ) N in the set of all -paare vectors u' such that ||=1/2n'|| = 1.01r. Let u' be an arbitrary k" -sppare vector such that || 1.01r, and let u1" u Au be the closest vector in the net N to u', It follows that
dd. Recall that A set of entries such that Inil < 1, and A is
Σ (X,,''>
E(x,,
(&i, n" Au))
tEA(U)
iEA(u)
Σ icAla)
{x 2-
-2n² 2222/1x
0.99an
2n -7
0.9an r2
If k" = d, we get the desired bound, since we can take u = Otherwise, by Lemma B.7
(x, u²)
(K,, )²) < 1.1 an an.r2. +²,
icA(s)
and we get the desired bound by Lemma H2
B.3 Putting everything together
First, truncate the entries of X and X' and obtain X"(T) and X'(T) using some 7 such that
& Ma VIEII v2
where k" 106 k x(E). We discuss the choice of a further in this subsection. Let us denote
T/ V/VI
Then we find the weights Wi,... W. using Algorithm C.I
We will show all the conditions of Theorem A. are satisfied if
10 10
M2; 4 + (10*M,)** A/
(x(E))4s/(=-2++ + x(I)2t
> C
2 (og(d/))
21-1
for some large enough absolute constant and
Mzr Mervk(E) 1-11/(20)
A 1000 M2r V el 1-111(2)) 1011//2////3> 1000
Vk/ōmin
First let us show that the assumptions of Lemma B.4 are satisfied with y1 & 100 M2r ||]]| 1111/22/ V and /2 10Mz (Z).
First we bound 2/2 Note that u (r((r) for 100k/0min O then ||い|| < k"]lu[] Hence if
1000 4t (k")' (T722) (K") log(d/8),
19

---

then Lemma D.2
implies that for all E Er,(r), with probability 1- 8/110,
2r || & (2M2rVK(2) 2t
-|= 1
π Σ
u)
(2Mrv/
i=[m]
Lemma D.2 and Lemma C.2
imply that for all (r) with probability 1 6/10,
Σ 1
w (x)()) < (2M2 ||= 2r
Let us bound yı. By Lemma B.5 if
n > 1000 k log(d/0)/e 2-1it +Tlogd/00WK//
then by with probability 1 8/10, y1 & 100 1-1
Vk/anin
The strong convexity holds by Lemma B.6 with probability 6/10 as long as
2 (k2 log(d/6)) 10 (s000/)0/2220))))0000000)))) M2 ((2))==)))))) /E,
where we used the fact that $ a and that that lemma.
||| v2. Vie" E satisfies the assumption of
Therefore, all the conditions of Theorem A.3 satisfied and attain the desired bound of
Mar xx)
1-2 stated in Theorem B.3
Now let us discuss the choice of v. First we can find an estimator & of x(<) by plugging it into the formula
10
(R44S/(6-2) + x21
C
2 log(d/5).
211
1/(2))
Then we can take 7' = 0.01
Note that if express in terms of & and plug into the formula for z', get that r' is an increasing function of k. Also note that & > x(E). Hence both conditions are satisfied: I Vomax z' is larger than the required lower bound for it, and is larger than 10000(7')21 (k"*)' (og(d/ō) 8) and 10000r log(d/8)v ( 1111/(21) as required.
F logid/8)
C Filtering
We use the following system of elastic constraints with sparsity parameter K > 1 and variables D
Ddt S1 ..,-
Vi E [d]
$t
Vi E [d]
;;0;
i2
Vi e [d]
8,0;
-0;
d
Ax:
Σ 0f <
(C.I)
s,U; & VK
1=1
Note that the vectors from the elastic ball / Rd with s; sign(v;). We will later discuss the corresponding cum-of-squares, certificates in Appendix D
||a|| <
||l||
VK
satisfy these constraints
Let a > O be such that Ed (x;) 021
02
< 2!
20

---

Algorithm C.1 (Filtering algorithm).
1. Assign weights wi =... W. = 1/n.
2. Find degree 21 pseudo-expectation B that satisfies Ag and maximizes (E wix? BBoo).
3. If ( - X B2x2)) 10' stop.
4. Compute Tj (x Br02r) and reweight: wo = (1 - ||T wi.
5. goto 2.
Lemma C.2. If at each step ( Σ (x;) 821 BB021 & a²2,, then the algorithm terminates at
most [2en] steps, and the resulting weights satisfy Σi=1 wi > 1 2E.
To prove it, we will use the following lemma:
Lemma C.3. Assume that
1 π
Ei=1
(x;)
021
B2
& a²
( Ei= X,02, BB,211 > 10 at and
Σ
wi
155g
E5
Then
Σ
Σ
w
<
S5S
ieSp
Proof of Lemma C.3
Note, that is enough show that
Σ
wi
w/
Wi w/-
iESp
Further, recall that w. =(1 show that
Ti Tmax
20, so for all i E [nr]. w
w/
1
T,W, Hence is enough to
Tmxx
Σ
Tiw;
1;W0;
iES,
ieSp
Since Sy and Sp partition [n] and
Σ
Σ
x 821 E2
WiT;
wi
1=1
1=1
we can prove Eies, TWW; Eies, w;W; by showing that
EE wiXee Br
Σ les,
Tww; & a²
Note that
11
TiW;
Σ /E5
821
021
(7))
021
BB
a
11
E5
Proof of Lemma C.2 We will show that the algorithm terminates after at most [2en]] iterations. Assume that does not terminate after T = [2en] iterations. Note that the number of entries of z that are equal to 0 increases by at least in every iteration. Hence, after T iterations we have set
21

---

at least en entries of w to zero whose index lies in Sg. By assumption that the algorithm did not terminate and Lemma C.3 holds that
Σ iES,
5pl
w
&
E
iES
a contradiction.
Let be the index of the last iteration of the algorithm before termination. Then
w
(7)
(T)
w (T)
28.
iESg
LE5.
D Sum-of-Squares Certificates
We use the standard sum-of-squares machinery, used in numerous prior works, e.g. KS17a KS17b
HL18 [HL19) dKNS20 DKK 22
Let fi, fi. fr and g be multivariate polynomials in x. A sum-of-sqqaree proof that the constraints (ff ,, fm > 0} imply the constraint (g 0) consists of sum-of-squares polynomials (ps)sg(u) such that
Σ ps Iieffi ScIm]
g
We say that this proof has degree if for every set [m]. the polynomial iss has degree
most there is degree & SoS proof that (fi > 0 i < r) implies {g > 0}, we write:
{fi > 0 r la {g > 0}.
We provide degree 28 sum-of-squares proofs from the system Ax (see below) of (n + d) constraints. The ofu-of-squares algorithm (that appeared it [Sho87 Par00 Nes00 Las01] See, e.g.. Theorem 2.6. [DKK+22] for the precise formulation) returns linear functional B R[x]<2r that is called a degree 2 eseudo-expectatiinn In particular, it means that once we prove in sum-of-squares of degree 2 that constraints Ax imply that some polynomial g(u) is non-negative, the value of the returned by the algorithm on g(u) is also non-negative
R.
that satisfies the constraints of Ag in time (n d)0(),
Recall the system Ag of elastic constraints in Equation (C.1) as follows:
Vi [d]
Vi [d]
s,0; i
Vi E [d]
8;0;
-0;
Ax:
Σ of <
1=1
d
& VK
1=1
Also recall that the vectors from the elastic ball constraints with s; sign(z;).
Rd
||^||| <
||a||
vK satisfy these
The following lemma similar to Lemma 3.4 from [DKK 22 but we prove in using the elastic
constraints. The derivation from the elastic constraints requires a bit more work.
Lemma D.1. For arbitrary polynomial p(v) Σ Eish Pin.i Ui U0, of degree at most we have
15 Ax
(((T)) 11.113. Kt
22

---

Proof. Observe that Ak
8.0
2 5;0; hence Ak 4
8.0 (Eg | 8,01) 8:01) 2F
& K' In addition, by note that,
0i 0i, Di ... .5. D.. It follows that
Ag Σ
Σ
Pi... Vij Ph.
Vi
Pi Ps (i ... 04
Jel sd
Σ
Phid Dij 14
P ... -1.5
1ahnnin ed
Pi Vig ... Vie
Pi ... Dt
1si1 Ed
1ell
2
21
1,
4f
Σ
Pin..h Ui -.. Vi
< |1p11
Σ
siúi
i=1
2
Σ 1eftooii
< Il Kt
Pi...
Vi
The following lemma shows that certify upper bound on the value of the empirical moments (as polylinear functions) of truncated distribution Zi(t) on the vectors from the elastic ball. Lemma D.2 (Certifiable bound on empirical moments). Suppose that for some I, l N and M2: 1,
Ak |6
{B(Xi x) < My -1=11
and for some v >
max B| < v || je(d]
2 22. VK- VIIII and
21
n > 1000
vsl
Kt
I
K' log(d/5),
VIEII
then with probability least 1 for each degree 28 pseudo-expectati B that satisfies Ag.
E
o)
< (2M2)) ||=||".
Proof. Consider the polynomial
1 a
n Σ
p(v)
By Lemma and the assumptions on and t, its coefficients are bounded by
v || llg(d/8)
+0 2 flo(dd/))
2t
|
2 2 21 ||E||
A 20
n
2t
It follows that
12
a Σ
5,0 Ag
Σ (x((t))
(X( -B(;, 10*+B/4 +B(X,,0)
28
n
23

---

2
s,p
< Σ
(x((T),)) 0) - B(xi 1)91) + +2(B((;, 2))
2
1=1
1=1
5,0
Σ (x;(t), z)/21
& 2212 2M
2f
Hence
2
Xi, 2) < (222z)) ||
By Cauchy-Schwand inequality for pseudo-expeccations (see, for example, Fact A.2. from DKKK22
we get the desired bound.
E Properties of the truncation
As before, let xj...., X; be iid samples from D.
For > O, let (t) = X 1 [xx|tr]] In this section we prove some properties of (T((t) that we use in the paper. We start with the following lemma.
Lemma E.1. Suppose that for some v > I,
max B|X vt ||=||
]=
Then
|3(x(() (x;()) x;) 7/-
vt. |||
72
Proof.
B ((x}(t)-x))(
(x;(t))
xix)
Xij 1
|
(x:)
1x |r| (xip)
|
1/4
13 (x:x) )1) 1/4
E
|
18 xx
(B (15,110))
[P|1X31 >
T²] Ff|xxi1** > x4) 12111111111
1/4
/1///11//72
The following lemma shows that the moments of the truncated distribution are close to the moments of X in -orm. Lemma E.2. Lest e N and suppose that for some B 0 and q 0,
B| 1+g < B²+9
max
je[d]
Then
t B'+g
-B(;)) or
<
79
24

---

Proof. Denote = X((T), b = x, Note that by Hölder's inequality, for all s [f],
Blb,, ... --b--ll-- 1ay. - -b,,1 1ajm a. = Blb,, ... -b-- ba ... az11 1 [ax==]
(F [a = =0]) पoं (BIb), ... bio- bj, / ::- aj, /1git) i
(BIb, ... b111 by1110/19 t
P (Xiz yru q x(1n
+ max B|b,|*
B9
[c([]]
B!+g
It follows that
[ ap -. -a B b,b,b; ... byl
Blaji A; -- aj. b, bjl
E [| 12 ... bj 2/2 a; + // .. a, bj b/2 ... b/1
Blay, bj |a ... 2 B|b |0/2 a....aa.. a, b/2 ... b,,
t B
74
The following statement a straightforward corollary of Lemma E.2 with = Corollary E.3. Let t N and suppose that for some B > 0.
max B ij
1
< B
jeld]
Then
f 2 <
B(x)
7
The following two statements special cases of Corollary E.3 for forf = 1 and f 2. Corollary E.4.
E
(
Corollary E.5. Suppose that for some 1,
max B B| < ||
j=[d]
Then
2 2 |||!
72
The following lemma shows that the empirical mean of (X((z)) oo is close to B(x;) 81 for an appropriate choice of and large enough и. Lemma E.6. Let i E N be and suppose that for some > 1
max [dd
B|X;
2 ||_||'
Then with probability 1 8,
(((tt) (X(x)))-Bxxx)) 61
12 ||'||* log(d/5)
+ 10 r' flogd//))
t- v- ||'||
< 10
7
Proof. It follows from Corollary E.3 Bernstein inequality Fact I.1 and a union bound over all d' entries of (3x;) 81
25

---

F Properties of sparse vectors
Lemma E1. Ler E E Raxd be a positive definite matrix, k', E r, > 0, and
Ex((r) = {u Rdd
|| < I1ull < vk. -
Sy-(T) = u Rd || = (1 + 8) r, u is k" sparse
Ifk" 4k|]E1//8,, then
(x)(r) S (onv(See(r))
Proof. Let us take some u E (r) Without loss of generality assume that ui > u2 > ... udd Let's split indices (1, d into blocks .i..., Brapon of size k" (the last block might be of smaller size). Let for each block B;, let
| ug
Pi [a/k" j=1
||
Since Σ, _.41k"" (1 + ö)r.
p: and u Σx T./ee
piu pt. is sufficient show that for all (u l1/p;
Note that for all j > 2, since ||uB,
< Vk [k lloo and ||us; Il < E |lBB,
|E|l
12 un,ll & V|E ||uB,|1 < k* ||uB &
||uB,- Il1
By the triangle inequality,
[dik"1 >
1/ uB, ll < ||E\/2u||
| 1/2 ug ll.
j=2
Hence
|
|| pi
[dikm Σ
|| 12 uB:
j=1
[a/K"1
< /2 + 2
|
1/2 ug
[d.
|
<r+2
||
lh
K"'
1=2
Er 2
||
K"
K1|
1 2
r
k"
< (1 + .r.
Lemma F.2. Ler E E Raxd be positive definite matrix, and let X E R.ndd be matrix such that for
some > 0 and E (0, 1). all "s-sarre vectors u' such that r < ||/1/22||| < 2r.
(1 6) /| u'll
I|Xx (1 5) || /2
Vm
kfK" 4 then for all u such that ||Σ|/2|| || and ||4|| < rvk.
(1 - 46) r <
-
||u|| || < (1 + 48)
vmn
26

---

Proof. The inequlity
1 Vin
|xu|| & (1+ 8) r & (1 46) follows from Jensen's 's inequality and
Lemma F.1
Let us show that (1 - 48) &
1
Xu|l. Let Bi...., Biaian be blocks of indices as in the proof of
Vm
Lemma F follows that
[a/k"1 Σ
Xu
||
Xue ||
Vm
Vin
Vid
[d/k"1
> - 8) 1| uB, -1 8)
>
|/2 ug,
ug,
f=2
k'||I|
> (1 8) || 2- r
k"
> (1 8)2 7 dr
> 40) 7
G Lower bounds
In this section we prove Statistical Query lower bounds. SQ lower bounds standard tool of showing computational lower bounds for statistical estimation and decision problems. SQ algorithms do not use samples, but have access an oracle that can return the expectation of any bounded function (up desired additive error, called folerance). The SQ lower bounds formally show the trateoff between the number of queries to the oracle and the tolerance. The standard interpretation of SQ lower bounds relies on the fact that simulating a query with small tolerance using iid samples requires large number of samples. Henee these lower bounds are interpreted as a tradeoff between the time complexity (number of queries) and sample complexity (tolerance) of estimators. See (DKS17) for more details.
First we give necessary definitions. These definitions are standard and can be found in [KS17]
Definition G.1 (STAT Oracle). Let D be a distribution over Rd A statistical query is function f + [-1, 1]. For 7 the STAT(T) oracle responds to the query f with value v such that Bx-D f(X) & Parameter is called the tolerance the statistical query.
Simulating query STAT(T) normally requires Q(1/r²) iid samples from D, hence SQ lower bounds provide trade-off' between the running time (number of queries) and the sample complexity ((2(1/²²)).
Definition G.2 (Pairwise Correlation). Let D2, D be absolutely continuous distributions over Rd, and suppose that supp(D) = Rdd The pairwise correlation of D, and D2 with respect to D is defined as
PD. (x)
xD(D,,
dx -
PD(x)
where PD, (x), (x), are densities of D1, D2, D respectively.
Definition G.3 Schi-Squared Divergence). Let D', D be absolutely continuous distributions over Rd, and suppose that supp(2)) Rdd The chi-squared divergence from D' D is
((D')2) xi>('',))
Definition G.4 (yy, p)coorcclt.ion) Let p.y 0, and let D be distribution over Rd. We say that family of distributions F over Rd is (y, -orrrelatee relative D, if for all distinct D', D" e F Ixo(D', DD)) & and Ixn(D', DD) &
Fact G.5. Let D be a distribution over Rd and F be family of distributions over Rdd that does not contain D, and consider hypothesis testing problem of determining whether given distribution D' = D or D' EF
27

---

y, 0,8 E.,, N, and suppose that there exists a subfamity of of size that is (y, correlllaee relative D. Then for all y' O, every SQ algorithm for the hypothesis testing problem requires queries of tolerance Ny + y or makes least sy (pp -- y) queries.
We will also need the following facts:
Fact G.6 (DKSS17 Lemma 6.7]). Let c E (0, 1) and k, d N be such that k & Vd. There exists set V C Id of k-sparse unit vectors of size dck such that for all distinct u, v E V, (0, & 2k
Fact G.7 (IDKS17 Lemma 3.4]). Let m N, and suppose that a distribution M over R matches first m moments of N(O, 1). For a unit vector v E R let a be a distribution such that its projections onto the direction of has distribution M, the projection onto the orthogonal complement is N(O, Idg-1),
and these projections are independens. Then for all u, V E R
[XNoOJas) Pa) < Ku, 1) x (M,
The following fact is a slight reformulation of Lemma E.4 from [KS19
Fact G.8 (DKSS19, Lemma E.4]). Let N(0, 1), Po > O, m E N, and g R B R. Let My be family of distributions over R satisfies the following properties:
such 1. M = (1 (H, ((1)) + f.r some Ey and By such that My has the same first m moments as N(O, 1).
2. If > 10 then E./((1 Ep) < (2²)) and x²M,,N(O, 1)) & (max(11))
3. Iflul 10ti. then Ey and (2,,, 1)) g()).
For unit Rd let Po. be the same as Pv in Fact G.7 whose projection onto My. Let Q' be a distribution over Bd+1 such that (X, y) ~ Q¹ satisfy the following properties: ~ N(0, 1), and Xly ~ P y. Then for all unit u, E Rd,
XDD(2,, Q,) < -()())+()))))_,))))
where D NO0 Idg+1).
Proposition G.9 (Formal version of Prrppsiiiin 1.10p. Let k, d E Vd, E (0, c ( 1).
For vector 8 Rd, and number a consider the distribution G ,) over Ro+1 such that (X, y) G( o) satisfy X NO, Id) and y (* + X.
where rl ~ N(0, o²) independent of
There exist set B C RC of k-sparse vectors, 0.99 < < and distribution Q over Rd+11 such that if an SQ algorithm A given access mixture (1 =f L, + =Q for B B, outputs Br such that |1 B1l 10-5, then A either
makes d k-2+2c queries.
makes al least one query with tolerance smaller than k-1tc (01+6
Proof. Note that (X G(B", a) satisfy y N(0,, az), where of |1B'112 + 0² and Xly
N 8" Id- -
We will use vectors B* of norm 10 Denote v = = and let 0² - 11 Consider a distribution Mμ = (1 (H, 1 11+) + =N μ 1). Note that x² x² N(O, 1)) < 00 (max(111f2a1)) and e/(1 E) < O (n²2 for μ > 10-4 Hence by Fact G.8
XolQ,, 2n) & (0,
for all unit v, u E Rdd_
Using Fact G.6 we can apply Fact G.5 with y = 220-2 p co((e, (p k 2+22 get that A requires least d 212c queries with tolerance greater than k lic (01fe)
28

---

Proposition G.10 (Formal version of Proposition 1.11). Let k, E K & Vd, E E (0,
с 1), For vector 8* R. positive definite matrix I and number a > 0, consider the distribution G [[ a) over Rd+1 such that (X, y) G( o) satisfy X ~ N(O, E) and 8") + TT. where
N(0, o²) is independent of X.
There exist set B C Rd of k-sparse vectors, 1td 1 Σ = ld, 0.99 < d & and a distribution Q over Rd+1, such that if an SQ algorithm A given access to mixture (1 - =) 0) eQ for g B, outputs such that lll ßll Vo then A either
makes dek 18 k-4+4c queries.
makes al least one query with tolerance at least k- 2
Proof. Note that (X G("",I, satisfy N(O, of)), where oz =B + o² and Xly
N (I$))
We will use vectors 8 of norm 10 Denote 11111|1|||| 11 Σ Id -d-c'do c'U0 where c' a constant such that
(IS" = ld c'uo
= Id va /3.
By DKSI9 Lemmas E.2], there exists distribution M that satisfies the assumption of Fact G.8 with m and g(E) = (O1fe) Hence by Fact G.8
Xo Q1) se oold (v, n)*
for all unit v, u E Rd.
Using Fact G.6 we can apply Fact G.5 with 2 p 001e), y' (p y)) k-Atdc, get that A requires least d 78k +4c queries with tolerance smaller than k-2+2c 011/s),
H Sub-exponential designs
Recall that distribution D in Rd is called L-sub-exponential, if has (Lr)-bounded f-th moment for each f E N. In particular, all log- oog-concave distributions are L-sub-exponential for some L < O(1).
In this section we discuss how can improve the dependence of the sample complexity on if (in addition to the assumptions Theorem B.3) we assume that D is L-sub-exponential For these designs we do need a truncation.
First, let us show how the gradient bound| B.5 modifies in this case. can be obtained directly from Bernstein's 's inequality for sub- uub-exponential distributions ([RH23 Theorem 1.13))
Lemma H.1. With probability at least 5/10 10,
E log(d/0)
| L log(d/8)
((n)) X
< 10
10
n
Te[a]
The proof of strong convexity bound (Lemma B.6) is exactly the same, with X'(z) X*.
since we need to prove Lemma D.2 for sub-exponential distributions. By Lemma C.I. from DKK 22), for all L-sub-exppapp eesub-exponentiall distribu- tions, with probability Ö.
Finally, we need to bound
( 021
-(x;) 021
log(d/8)
1
x7)
021
B(X;) 021
<
(10LV/|E]| log(d/6))*
11
n1
29

---

Hence with n 2 K2 log(d/))) 4+ we get (X:) 02 - -B(X)) 821
& < /K'
so we get the conclusion Lemma D.2
Putting everything together, the sample complexity is
k log(d/0) (k2 log(d/))) 2) k(I) <(I)41s/(622)
+k2 x 1ogg(d/0)) 411
22-1/1
Note that we can use and M3 4L.
Consider the case when D log-concave, so < O(1). x(2) < 0(1, > Q111, = 1, with
high probability we get error Vz) as long as
k klogd d k2 (log d)
Similarly, for x(E) O(1), a > 10), with high probability get error O(Mae3/4) (where
M < Ooylog d) is the same as Theorem 1.7
as long as
k logg d 3/2
n
kt (logd)".
Note that for sub-Gaussian distributions one can use better tail bounds and the polylog(d) factors should be better in this case.
I Concentration Bounds
Throughout the paper the following versions of versions of Bernstein's 's inequality. The proofs can be found in [Tro15).
Fact I.1 (Bernstein inequality). Let I. and let x E TRd be a zero-mean random variable. Let X1, Nn
Xn be i..dd. copies of x. Suppose that |x| L. Then the estimator all f >
- X; satisfies for
f'n
P(J5) > f) < exp
+
Fact 1.2 (Bernstein inequality for covariance). Let L O and let E Rdd be d-dimensional random vector. Let X1.... be i..d. copies of x. Suppose that ||x|1 & L. Then the estimator
1 E x satisfies for all t > 0
fn |2||_|| + Lt
P(| Exx T|| >
2d exp
30

---

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

---

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

---

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

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: This is theory paper, and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:::////eip..eeeeeeeeee httpr//......pp.....ttccccccaeea
Answer: [Yes]
Justification:
The research conforms, every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
34

---

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

---

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


Reviews:
[{"review_id": "GEkse5GEEe", "reviewer": "Reviewer_JPFs", "summary": "This paper studies sparse linear regression with oblivious and adaptive adversaries. The design matrix is random, the noise is chosen by an adversary, and the goal is to find the optimal k-sparse weight vector. The results are as follows: to achieve $O(\\sqrt{\\varepsilon})$ error, a sample complexity of $\\widetilde{O}(k^2/\\varepsilon)}$ is needed, and to achieve $O(\\varepsilon^{3/4})$ error, a sample complexity of $\\widetilde{O}(k^4/\\varepsilon^3)$ is needed. Previous work did not achieve error better than $\\sqrt{\\varepsilon}$ with any sample complexity better than $d^2$, unless the rows of a design matrix are drawn from an isotropic Gaussian distribution.\n\nTo obtain their results, the authors make the following assumptions: (1) the noise vector has at least $0.01n$ entries that are bounded by $\\sigma$, where $n$ is the number of examples, (2) at most an $\\varepsilon$ fraction of rows of $X$/entries of $y$ are corrupted, and (3) the rows of $X$ have bounded 3rd moments and entrywise-bounded 4th moments, i.e. the rows of X can be heavy-tailed random vectors. \n\nIn this setting, they obtain two results:\n1. With $O(k^2/\\varepsilon)$ samples, they obtain $O(\\sqrt{\\varepsilon})$ error. Compared to the best prior work for heavy-tailed design matrices, the advantage of this result is that there is no dependence on the norm of the optimal k-sparse regression vector.\n2. With $k^4/\\varepsilon^3$ samples, they obtain $O(\\varepsilon^{3/4})$ error. This result additionally assumes that the distribution of the rows of the design matrix has a bounded 4th moment, with a constant-degree sum-of-squares proof of the bound. It also additionally assumes that the rows of the design matrix have entrywise-bounded 8th moment.\nAdditionally, they give matching statistical query lower bounds.\n\nThe algorithm consists of obtaining a filtered set of examples, then minimizing Huber loss with l1 regularization, on the remaining examples. In the analysis, the authors show that if the following two conditions:\n(1) A bound on the gradient of the loss function\n(2) A condition similar to strong convexity\nhold on the boundary of certain regions they call \"elastic balls\" (the elastic ball of radius $r$ has points with $\\ell_2$ norm at most $r$ and $\\ell_1$ norm at most $\\sqrt{k} \\cdot r$) then the weight vector they obtain will be similar to the true optimal weight vector. \n\nOne of the key steps in this analysis, compared to prior works is as follows: instead of using Cauchy-Schwarz to bound certain terms in the gradient bound, they use Holder's inequality. This leads to them having to bound the sum of $\\langle X_i, u \\rangle^4$, as $X_i$ ranges over the examples in the filtered set, and $u$ can be any vector in the elastic ball of radius 1. Thus, during the algorithm, they must select $\\widehat{S}$ so that it satisfies this property, and thus need an efficient algorithm to find such a set of size $(1 - O(\\varepsilon))n$. They do this using a sum-of-squares relaxation with elastic constraints, which makes it so the relaxation set is a superset of $u^{\\otimes 4}$ for $u$ in the elastic ball.\n\nFor the heavy-tailed case, it is also necessary to do some thresholding of X, which may have large entries even without adversarial noise. In previous works, the thresholding parameter needs to depend polynomially on the norm of the weight vector (to preserve the relationship between the un-corrupted X and y). This paper observes that in order to preserve the relationship between X and y, it is only necessary to analyze the effect of thresholding for the entries that are in the support of the optimal k-sparse regression vector $\\beta^*$. This allows the thresholding parameter to only depend on $k$ and $\\varepsilon$ and not the norm of $\\beta^*$.\n\nThe proof strategy for showing the strong convexity property for heavy-tailed design matrices is also interesting. They first show it for vectors $u$ in the elastic balls which are $k$-sparse, then extend to dense vectors $u$. They show the bound for all k-sparse vectors using Bernstein's inequality, and a small $\\epsilon$-net for the k-sparse vectors. To extend to dense vectors, they use the fact that if a quadratic form is $\\Theta(r^2)$ on $k$-sparse vectors of norm $r$, then the quadratic form is $\\Theta(r^2)$ on the elastic ball of radius $r$.", "questions": "- On line 278, what is $\\hat{\\beta}$? I thought the final estimator you return is $\\hat{\\beta}_{\\hat{S}}$. Do you mean to refer to the ground-truth $k$-sparse regression vector?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The results are very strong compared to previous works.\n- The technical tools used are very interesting.", "weaknesses": "- While the writing is mostly good, it would be nice to organize the techniques section better. It would be useful for readers if you explicitly write the algorithm in a separate box, and divide the techniques section into some subsections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JPFs,\n\nThank you very much for your review! We appreciate your evaluation of our work and will improve the techniques section in the final version according to your suggestions.\n\nRegarding your question: Indeed, it is a typo, there should be $\\beta^*$ instead of $\\hat{\\beta}$ in line 278.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TN67OJDNUr", "reviewer": "Reviewer_sWxz", "summary": "The paper focuses on robust estimation of sparse linear regression in the presence of both oblivious and adaptive adversaries. It claims to offer polynomial-time algorithms capable of recovering a sparse coefficient vector with high probability. The paper includes theoretical analyses using the standard techniques such as pre-filtering, truncation to ensure robustness.", "questions": "- Is the oblivious adversary allowed to change all the $n$ samples, unlike the adaptive adversary, which only changes $\\varepsilon*n$ samples? \n\n- If the oblivious adversary is also restricted to $\\varepsilon * n$ samples, it should be stated in line 6. Also, are the oblivious and adaptive adversaries changing the same $\\varepsilon * n$ samples? \n\n- The authors claim that their algorithm achieves $o(\\sqrt{\\varepsilon})$ error for all log-concave distributions if $\\varepsilon \\leq 1/\\text{polylog}(d)$. Hence, $\\varepsilon$ can be very small for large $d$. Can this upper bound on $\\varepsilon$ be improved? \n\n- The condition number of the covariance matrix is assumed to be bounded. Is that assumed in the existing literature or a new assumption in this submission? \n\n- Line 110 typo: 'ehrtr' and from 's' more \n\n- Line 234 typo: 'ghdsample' complexity", "limitations": "- In Definition 2.1, why was $|x_i| \\leq 2$ chosen as the threshold to define the quadratic and linear part of Huber loss? In general, it could be dependent on the data? For example, there could be some dataset where $|x_i| \\leq 3$ may be more appropriate. \n\n- The above could affect the upper bound on the gradient $|\\phi(\\eta)|$ taken as 2 in line 288. \n\n- A conclusion section and pointers to future work seem to be missing. \n\n- Towards the end of the main manuscript, the focus seems too much on the proof sketch. The writing or presentation can be improved. \n\n-  Some sort of empirical justification for the proposed results on synthetic or real datasets would have been really nice. This would have also helped to draw attention to the significance of the contributions of polynomial time algorithms. In Proposition 1.10 and 1.11, the number of queries is claimed as $\\exp(d^{\\Omega(1)})$, which does not seem to be very useful for practitioners.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The authors claim to deal with two adversaries, which can be seen as a generalization of dealing with one adversary. \n\n- The theoretical analysis seems to be rigorous. \n\n- The analysis also covers heavy tails under the standard assumptions on the moments made in the existing literature. \n\n- The literature review is good.", "weaknesses": "As per my understanding, the oblivious and adaptive adversary are dealt in literature separately. \n\n- For the oblivious adversary, the existing literature can handle constant outlier proportions and deliver consistent estimates. \n\n- For adaptive adversary, existing literature [PFL20] already has the results which are proposed in the submission. They use a trimmed MLE algorithm whose convergence rates are analyzed. Further, [Sas22] and [SF23] already extended these results for sparse settings (line 264). \n\nSo, as per my understanding, the authors claim bounds similar to those in the existing literature for a slightly more complex setting of two adversaries. \n\n- Why are few entries of $\\eta$ required to be close to $1$ in magnitude? Doesn't that make the oblivious adversary weak? \n\n- The authors use pre-filtering ideas, assuming a known covariance matrix and truncation to deal with heavy tails. They use standard techniques like sum-of-squares and weighted Huber loss minimization with $\\ell_1$ regularization. \n\nThese ideas are well explored in the literature. So, strictly speaking, there is a lack of major novelty in new ideas to deal with outliers and encourage robustness.  \n\n- More importantly, $O(\\sqrt{\\varepsilon})$ error is already proved to be minimax optimal in the existing literature even when $n \\to \\infty$ while using techniques like trimming, pre-filtering, or truncation. A more interesting question could be under what conditions on $\\varepsilon \\neq 0$ or adversary can we achieve zero error for at least $n \\to \\infty$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer sWxz,\n\nThank you very much for your review! We appreciate your feedback and would like to address the points raised, as well as answer the questions and discuss limitations.\n\n**Regarding the weaknesses:**\n\n*Existing literature on the adaptive adversary:* While [PJL20] inspired the idea of filtering before Huber loss minimization, our work diverges significantly. [PFL20] did not explore the sparse case and (in the case of $o(\\sqrt{\\varepsilon})$ error) studied only isotropic designs. Our approach employs a sum-of-squares program for sparse regression, which was not addressed in prior works. Consequently, our Theorem 1.7 presents a smaller error than prior works on sparse regression ([Sas22, SF23]). Even in Theorem 1.4's context, dealing with very heavy-tailed designs without sum-of-squares, our results surpass [Sas22] with weaker moment assumptions. We remark that our results outperform the results of prior works even in the simplest special case of Gaussian noise (i.e. when Gaussian noise is added to $X^*\\beta^*$ by an oblivious adversary).\n\n*Oblivious adversary's strength:* The assumption that a few entries of $\\eta$ are close to 1 appeared in prior works on linear regression with oblivious adversary ([dNS21, dLN+21]). This is one of the weakest assumptions used in literature (so the adversary is strong). Without this assumption, the oblivious adversary can simply add Gaussian noise with very large variance (say, $2^d$) to each entry of $X^*\\beta^*$, and the error has to scale with the variance of the noise. Hence some restriction of this kind is necessary for achieving optimal (or at least bounded) error.\n\n*Covariance matrix assumption:* We do not assume that the covariance matrix is known. Furthermore, the problem with unknown covariance that we study is likely to be significantly more complicated than the case when the covariance is known.\n\n*Minimax optimality of $O(\\sqrt{\\varepsilon})$ error:* While generally optimal, specific designs can yield better errors. Our Theorem 1.7 is novel in demonstrating errors smaller than $O(\\sqrt{\\varepsilon})$ in sparse settings, outperforming prior results, even for Gaussian designs and Gaussian noise (i.e. when the oblivious adversary simply adds iid Gaussian variables to the entries of $X^* \\beta^*$).\n\n*Zero error conditions:* Achieving zero error is impossible even with $\\varepsilon = 0$ when Gaussian noise is added to $X^*\\beta^*$. If the query concerns settings without $n$-independent error terms, our focus on the classical version of the adaptive adversary necessitates some error term that depends on $\\varepsilon$ but not (directly) on $n$. Weaker adaptive adversary versions are beyond our scope.\n\n**Regarding the questions:**\n\n*Oblivious adversary's power:* Yes, the oblivious adversary can alter all samples, provided it remains independent of $X^*$. A constant fraction (0.01 in Definition 1.1) of true labels can be changed by at most $\\sigma$, while other samples can be changed by arbitrarily large values. This model includes adding Gaussian or Cauchy noise, aligning with previous noise models (see also the discussion in lines 120--125, where we explain how the general random noise model studied in prior works is captured by the oblivious adversary).\n\n*$\\varepsilon < 1/polylog(d)$ requirement:* This stems from the KLS conjecture. If the conjecture is true, this assumption is needed. For some specific log-concave distributions (e.g. Gaussian distribution, or uniform distributions over $\\ell_p$ balls) for which Poincare parameter is know to be independent of $d$, this assumption on $\\varepsilon$ is not needed. We discuss it in lines 203--219, and we will clarify this further in the final version of the paper.\n\n*Error dependence on covariance condition number:* The error's dependence on the covariance condition number is detailed in Theorem B.3, and it is similar to prior works ([Sas22], [SF23]). We did not optimize this dependence, but Proposition 1.11 highlights that even a condition number of 2 presents significant challenges compared to the case of identity covariance.\n\n**Regarding the limitations:**\n\n1) *On the Huber parameter*: In Definition 2.1, we focus on $\\sigma = 1$, using Huber parameter 2. For general cases, dividing by $\\sigma$ suffices, as this parameter is assumed to be known. Note that in prior works on regression with oblivious adversary ([SBRJ19, dNS21, dLN+21]) this parameter is also assumed to be known, see discussion in [SBRJ19] on \"Estimating the noise variance\". We will add a discussion on this topic to the final version of the paper.\n\n2) *On the lower bounds*: Our focus was on proving the strongest possible theoretical guarantees in polynomial time, and we added the lower bounds in order to illustrate that our assumptions on the number of samples are inherent for polynomial time algorithms. Our results are consistent with the usage of SQ lower bounds in prior works on learning theory, e.g. [DKS17]. We believe that practical applications of theoretical results on algorithmic robust statistics are a significant challenge in machine learning and theoretical computer science. Addressing this challenge is beyond the scope of our work.\n\nThank you again for your valuable feedback. We hope this addresses your concerns and clarifies our contributions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J3PFna4NoL", "reviewer": "Reviewer_mVbA", "summary": "It developed efficient estimators for sparse linear regression in the presence of oblivious and adaptive adversaries. It presents a robust algorithm that outperforms sota under desired conditions on the moment of the distribution.", "questions": "NA.", "limitations": "The results depend on specific assumptions about the distribution and moments of the data, which may not always hold in real-world scenarios.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces several robust algorithms that outperform the sota in sparse linear regression.\n\n- It also gives analysis of weighted penalized Huber loss suitable for heavy-tailed designs.\n\n- The paper includes theoretical results with proofs and assumptions, which are clearly stated.", "weaknesses": "- algorithms may require significant computational resources, which could limit practical applications.\n\n- There is a lack of empirical evidence comparison with the sota even on a toy setup.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer mVbA,\n\nThank you very much for your review! Our focus was on proving the strongest possible theoretical guarantees in polynomial time. There is extensive literature in learning theory, particularly in robust estimation and linear regression, that lacks empirical validation, and we believe making these theoretical results practical is a significant challenge in machine learning and theoretical computer science. Addressing this challenge is beyond the scope of our work.\n\nWe identify two issues for practical applications: First, the algorithms for the $o(\\sqrt{\\varepsilon})$ error require $k^4$ samples, which might be too large for some instances. Second, our approach uses the sum-of-squares algorithm, which is very slow in practice. While the first issue is likely to be inherent, the second can be potentially addressed in future works. Specifically, it may be possible to design a fast spectral algorithm inspired by the sum-of-squares approach (although this is beyond our current scope).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "izmmjqTmo6", "reviewer": "Reviewer_e1Aa", "summary": "This paper studies sparse linear regression $y^* = X^* \\beta^* + \\eta$ (where $\\beta^*$ is $k$-sparse) in the presence of two types of adversaries. \n\n- First, the noise vector $\\eta$ is sampled before $X^*$ in an (obliviously) adversarial way. Then $X^*$ is sampled independently of $\\eta$ with i.i.d. rows and $y^*$ is generated according to the model. \n\n- Second, an adaptive adversary takes $(X^*, y^*)$ and (adaptively) corrupts at most $\\epsilon$ fraction of $(X_i^*, y_i^*)$. \nThe resulting samples given to the statistician are denoted by $(X, y)$. \n\nThe results are two-fold. \n\n- First, a poly-time algorithm for estimating $\\beta^*$ up to $\\epsilon$ expected prediction error using $n \\approx k^2/\\epsilon^2$ samples. \n\n- Second, a poly-time algorithm for estimating $\\beta^*$ up to $o(\\epsilon)$ expected prediction error using $n \\approx k^4/\\epsilon^6$ samples. \nFor correlated Gaussian design, this can be improved to $n\\approx k^4/\\epsilon^4$.", "questions": "I'm not familiar with the SoS machinery, so the authors may find my comments shallow and unconstructive. \nThat said, I am familiar with ordinary (sparse) linear regression and I do think that the presentation of the paper should be improved. \n\nMajor comments: \n\n1. The sample complexity bounds are written in a wacky way. \nWhy don't we fix the goal to be achieving $\\epsilon$ error and write the sample complexity bounds accordingly?\n\n1. The two results in the paper (for achieving $O(\\sqrt{\\epsilon})$ and $o(\\sqrt{\\epsilon})$ errors) seem to have very discontinuous transitions as $\\epsilon$ varies. \nCan the authors comment on whether it's expected to be so or it's a proof artifact?\nIn fact, should I think of $\\epsilon$ as potentially depending on $n,k,d$ in an arbitrary way? \nThis is not clear since sometimes the authors view $\\epsilon$ as a constant in which case $O(\\epsilon), o(\\epsilon)$ don't make sense to me. \n\n1. I suggest the authors add a short section discussing related work at the level of techniques (e.g., filtering, SoS, etc.). \nCurrently, these techniques and the difference between the present paper and prior work are buried in Section 2 which itself is written in an obscure way. \n\nMinor comments:\n\n1. Line 48-51 seems out of place.\n\n1. Please unify the notation $N(0,\\mathrm{Id}), N(0,1)^n$. \n\n1. Multiple typos in line 110. \n\n1. Line 114, should $X$ be $X^*$?\n\n1. Typo in line 234. \n\n1. I don't understand line 243-244. \nPlease define \"simulation\". \nMy shallow understanding is that SQ lower bounds only apply to detection version of the problem. \nI'm not sure if this has the same spirit as \"simulation\". \n\n1. Section 2 (Techniques) is written in a very informal and dense way. \nAs someone who's not familiar with these techniques, I couldn't get much out of it. \n\n1. Typo in line 259, $\\eta\\sim N(0,\\mathrm{Id})$. \n\n1. Typo in line 264, it --> in. \n\n1. Line 291, please provide a reference for the sentence in the parentheses. \n\n1. Is line 298 the only property one needs from the output of filtering?\nIf so, why not say it upfront in line 266?\n\n1. Line 364, 365, there're two \"only\"'s in the sentence. \n\n1. I don't understand line 371, even grammatically. \n\n1. A very minor comment on the writing. I feel that the language used in this paper is quite informal and the writing was perhaps done in a hasty. \nFor instance, there're ~20 \"only\", ~20 \"even\", ~10 \"likely\"...", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "NA", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer e1Aa\n\nThank you very much for your review! We will address all the typos and enhance the writing and notation as per your suggestions.\n\n1) *“The sample complexity bounds are written in a wacky way. Why don't we fix the goal to be achieving $\\varepsilon$ error and write the sample complexity bounds accordingly?”* — For some design distributions it might be not possible achieve error $\\varepsilon$, even information-theoretically. Furthermore, even for Gaussian designs error $O(\\varepsilon)$ is believed to be not achievable by polynomial time computable estimators. Hence it makes sense to ask the question what error can we get in polynomial time, and what are the weakest assumptions needed to achieve this error.\n\n2) *“The two results in the paper (for achieving $O(\\sqrt{\\varepsilon})$  and $o(\\sqrt{\\varepsilon})$ errors) seem to have very discontinuous transitions as $\\varepsilon$ varies. Can the authors comment on whether it's expected to be so or it's a proof artifact? In fact, should I think of  as potentially depending on $n,k,d$ in an arbitrary way? This is not clear since sometimes the authors view $\\varepsilon$ as a constant in which case $O(\\varepsilon)$, $o(\\varepsilon)$ don't make sense to me.”* — indeed, the transition is discontinuous (we need $k^2$ samples for $O(\\varepsilon)$ and $k^4$ samples for $o(\\varepsilon)$), and the lower bound (Proposition  11) shows that it is likely to be necessary for polynomial time algorithms. While $\\varepsilon$ can depend arbitrarily on $n,k,d$ (as long as the conditions of the theorems are satisfied), it is instructive to think of $\\varepsilon$ as something tending to zero as $k\\to\\infty$, but not very rapidly, e.g. $1/polylog(k)$ or so. The reason is that for Gaussian designs there is a simple algorithm that achieves error $O(\\varepsilon \\sqrt{k})$, which is better than our bounds for very small $\\varepsilon$, but is much worse for larger $\\varepsilon$. It is a usual phenomenon in robust statistics, and the standard goal is to obtain a bound that would not (directly) depend on the dimension, but would only depend on $\\varepsilon$ (note that a term that depends on $\\varepsilon$ and does not vanish for fixed $\\varepsilon$ as $n\\to \\infty$ is inevitable). And while the results are correct for small constant $\\varepsilon$, they are interesting only under assumption $\\varepsilon \\to 0$. We will add a more detailed discussion on this topic to the final version of the paper.\n\n3) We will improve Section 2 by simplifying technical details and emphasizing the difference from the techniques of the prior works. The main reason why our Theorem 1.4 is better than the result of the prior work ([Sas22]) is that we use a different proof of the strong convexity (we use eps-net over sparse vectors, and then extend the argument to the elastic vectors, while they used a different argument).\n\n4) Regarding SQ lower bounds: in general, SQ algorithms can be used for estimation problems, not only for hypothesis testing problems. However, for lower bounds we indeed use standard arguments that SQ algorithms need either very small tolerance, or very large number of queries in order to solve some hypothesis testing problem (and that implies that SQ algorithms with small number of queries and large tolerance cannot estimate $\\beta^*$ up to certain error). By \"simulation\" we simply mean the standard simulation of the oracle using iid samples, i.e. estimating $\\mathbb{E} f(X)$ using the empirical mean. We will clarify it in the final version of the paper. We discuss SQ lower bounds (and some definitions related to SQ algorithms) in Appendix G. See also [DKS17] for more details regarding SQ algorithms and lower bounds.\n\n5) Regarding line 114: Indeed, there is a typo, there should be $X^*$, not $X$.\n\n\n6) Regarding line 371: We simply meant that the set of indices $A$ is independent of $X^*$, and hence we may assume that the rows of $X^*$ that correspond to $A$ are just iid samples from $D$. We will clarify it in the camera version of the paper.\n\n\nThank you again for your valuable feedback, which we will address to improve the final version of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NAxjM2KsH2", "reviewer": "Reviewer_3A8o", "summary": "The authors provide a computationally efficient estimator for robust and sparse linear regression under non-isotropic covariance matrices. Their first result achieves $O(\\sqrt{\\epsilon})$ error with state-of-the-art sample complexity under a weaker noise assumption than prior work. Their second result is the first to achieve $o(\\sqrt{\\epsilon})$ error for robust and sparse linear regression under non-isotropic covariance matrices, under a sum-of-squares certificate for the $4^{th}$ moment. They further provide Statistica Query Lower bounds supporting their results.", "questions": "Small typo on Line 110 - ehtr\n\nSee weakness section.", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- They improve the state-of-the-art result for $O(\\sqrt{\\epsilon})$ error in terms of the sample complexity being independent of the $l-2$ norm of the true weight vector, $\\beta_{*}$\n- They provide the first result achieving $o(\\sqrt{\\epsilon})$ error, under a suitable sum-of-squares certificate for the $4^{th}$ moment.\n- They provide SQ lower bounds which suggest that their results might be tight for polynomial time estimators", "weaknesses": "I don't see any weaknesses per se, was just curious to understand if the authors believe that the sum-of-squares assumption is necessary to achieve $o(\\sqrt{\\epsilon})$ error or a weaker assumption such as Definition 1.6 suffices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 3A8o,\n\nThank you very much for your review! We appreciate your evaluation of our work.\n\nRegarding your question: We believe that moment assumptions without sum-of-squares are not enough.  For robust mean estimation, similar lower bound was shown in [HL19]. However, we believe that it might be possible that some additional assumptions, in particular, related to symmetry of the distribution, might be potentially used without any assumptions related to sum-of-squares, as was shown for robust mean estimation in [NST23].\n\nReferences:\n\n[HL19] *How Hard is Robust Mean Estimation?* Samuel B. Hopkins, Jerry Li. **COLT 2019**\n\n[NST23] *Robust Mean Estimation Without Moments for Symmetric Distributions*. Gleb Novikov, David Steurer, Stefan Tiegel. **NeurIPS 2023**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies sparse linear regression robust against both oblivious and adaptive adversaries. The majority of reviewers agree that both the theoretical results and the technical contributions seem qualitatively strong. Although concerns about the practical nature of the proposed algorithms were raised, the general consensus is that the paper is primarily of theoretical interest. Author responses during the rebuttal phase adequately addressed additional initial reviewer concerns.

I recommend the authors incorporate reviewer feedback and improve the clarity/presentation to ensure the work has a stronger impact. Further, it has been brought to my attention two additional works that examine similar error models in related contexts: https://ieeexplore.ieee.org/document/4544953 and https://dl.acm.org/doi/10.1145/1250790.1250804. While these studies focus on problems where the signal is not required to be sparse, considering these connections may provide useful insights or strengthen the theoretical foundations of the current work. I encourage the authors to review these references and evaluate whether citing them could benefit their contribution.
Decision: Accept (poster)