Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Authors: Tommaso d'Orsi
Chih-Hung Liu
Rajai Nasser
Gleb Novikov
David Steurer
Stefan Tiegel
Venue: NeurIPS 2021 Poster (2021)
Keywords: Consistent Estimation
Robust Optimization
Oblivious Outliers
Principal Component Analysis
Sparse Regression.

Abstract: We develop machinery to design efficiently computable and \emph{consistent} estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an $\alpha$ fraction of the samples.
As concrete examples, we investigate two problems: 
sparse regression and principal component analysis (PCA).
For sparse regression, we achieve consistency for optimal sample size $n\gtrsim (k\log d)/\alpha^2$ 
and optimal error rate $O(\sqrt{(k\log d)/(n\cdot \alpha^2)})$
where $n$ is the number of observations, $d$ is the number of dimensions and $k$ is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples.
Prior to this work, no estimator was known to be consistent when the fraction of inliers $\alpha$ is $o(1/\log \log n)$, even for (non-spherical) Gaussian design matrices.
Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d'Orsi et al.~\cite{ICML-linear-regression}.
In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). 
Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in $n$ (e.g., Gaussian with variance $1/n^2$).

To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the $\ell_1$ norm or the nuclear norm, and extend d'Orsi et al.'s approach~\cite{ICML-linear-regression} in a novel way to analyze the loss function.
Our machinery appears to be easily applicable to a wide range of estimation problems.
We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with is optimal up to a constant factor.

Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers
Tommaso d'Orsi ETH Zürich
Chih-Hung Liu ETH Zürich Zürich, Switzerland
Rajai Nasser ETH Zürich Zürich, Switzerland
Gleb Novikov ETH Zürich Zürich, Switzerland
Zürich, Switzerland
David Steurer
Stefan Tiegel ETH Zürich Zürich, Switzerland
ETH Zürich Zürich, Switzerland
Abstract
We develop machinery to design efficiently computable and consistent estima- tors, achieving estimation error approaching zero the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but a fraction of the samples. As concrete examples, investigate two problems: sparse regression and principal component analysis (PCA). For sparse regression, achieve consistency for optimal sample size
(k log a² and optimal error rate O( O(v log d)/(n a²)) where n is the number of observations, d is the number of dimensions and is the sparsity of the parameter vector, allowing the fraction of inliers to be anverse-polynome
in the number of samples. Prior to this work, no estimator was known to be consistent when the fraction of inliers is o(1 o1//log log n), even for (non-spherical) Gaussian design matrices. Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d' Orsi al. (dNS21). In the context of PCA, attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used matrix completion). Previous works could obtain non-trivial guarantees only under the sumptions that the measurement noise corresponding to the inliers is polynomially small in n (e.g.. Gaussian with variance 1/
To devise our estimators, we equip the Huber loss with non-smooth regular- izers such as the e norm or the nuclear norm, and extend d'Orsi al.'s ap- proach (dNS21) in a novel way to analyze the loss function. Our machinery appears be easily applicable
wide range of estimation problems. We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with optimal up to a constant factor.
Introduction
Estimating information from structured data central theme in statistics that by now has found
applications in wide array of disciplines. On a high level, a typical assumption in estimation problem is the existence of -nown priori- family of probability distributions p == [Pp l E Q} over some space Z that are each indexed by some parameter B Q. We then observe a collection
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

of n independent observations Z = (Z,,..., Zn) drawn from an unknown probability distribution Pp E P. The goal is (approximately) recover the hidden parameter f
Oftentimes, real-world data may contain skewed, imprecise or corrupted measurements. Hence, a desirable property for estimator is to be robust to significant, possibly malicious, noise perturbations on the given observations. Indeed, in the last two decades, large body of work has been developed on designing robust algorithms (e.g see (BGNO9; BBCI1; MMYSB19)). However, proving strong guarantees often either demands strong assumptions on the noise model or requires that the fraction of perturbed observations is small. More concretely, when we allow the noise to be chosen adaptively, i.e., chosen dependently on the observations and hidden parameters, common theme is that consistent estimators estimators whose error tends to zero as the number of observations grows can be attained only when the fraction of outliers is small.
In order make vanishing error possible in the presence of large fractions of outliers, it is necessary to consider weaker adversary models that are oblivious to the underlying structured data. In recent years, a flurry of works have investigated oblivious noise models (CLMW 11; ZLW* 10; TJSO14; BJKK 17; SZF18; SBRJ19; PJL21; dNS21). These results however are tailor-made to the specific models and problems. To overcome this limitation, in this paper we aim to provide a simple blueprint to design provably robust estimators under minimalistic noise assumptions for a large class of estimation problems. As a testbed for our blueprint, we investigate two well-studied problems:
Principal component analysis (PCA): Given matrix Y := L" N where L' R is an unknown parameter matrix and N is an n-by-n random noise matrix, the goal is to find an estimator L for L which is as close as possible to L in Frobenius norm.
Sparse regression: Given observations (X1, y1), ..... (X,, yn) following the linear model yi (Xi, + Ti where X; R B Rd is the k-sparse parameter vector of interest (by k-sparse we mean that it has at most k nonzero entries) and .7,.... .In is noise, the goal is to find an estimator / for 3e achieving small squared prediction error | f²)l where X is the matrix whose rows are XI,-..,X, X,,
Principal component analysis. natural way to describe principal component analysis under oblivious perturbations is that of assuming the noise matrix N to be n--y-- matrix with uniformly random set of a n1² entries bounded by some small ( > 0 absolute value. In these settings, we may think of the a fraction of entries with small noise as the set of uncorrupted observations. Moreover, for Ç > 0, the fact that even for uncorrupted observations the noise is non-zero allows us to capture both gross sparse errors and small entry-wise noise in the measurements the same time (for example [ = 1 then the model captures settings with additional standard Gaussian noise). Remarkably, for O, Candès et al.'s seminal work (CLMWII) 11) provided an algorithm that exactly recovers L' even for a vanishing fraction of inliers, under incoherence conditions on the signal L.. The result was slightly extended in (ZLW*1 10) where the authors provided an algorithm recovering L' up squared error O n*) thus allowing polynomially small measurement noise č, but still failing to capture settings where standard Gaussian measurement noise added the sparse noise. Even for simple signal matrices L", prior to this work, it remained an open question whether consistent estimators could be designed in presence of both oblivious noise and more reasonable measurement noise (e.g.. standard Gaussian).
L Linear regression. Similarly to the context of principal component analysis, a convenient model for oblivious adversarial corruptions is that of assuming the noise vector 17 to have a random set of n entries bounded by ( in absolute value (here all results of interest can be extended any ( > 0 just by scaling, so we consider only the case ( = 1). This model trivially captures the classical settings with Gaussian noise (a Gaussian vector with variance 0² will have an a = O (L) fraction of inliers) and, again, allows us to think of the a- of entries with small noise as the set of uncorrupted observations. Early works on consistent regression focused on the regime with Gaussian design X X, (O,, Σ) and deterministic noise 11.² (BJKKI7) presented estimator achieving error
In this paper, assume Q C Rd and Z S RD for some d, D. denote random variables in bold face, and hide absolute constant factors with the notation O(),, ())), 2. S and logarithmic factors with Ö(-), Q())
2Our analysis also works for the parameter error -
For Gaussian design X one may also consider deterministic noise model. This noise model is subsumed by the random noise model discussed here (if X is Gaussian). As shown in (dNS21), roughly speaking the

---

O(d/(a². n)) for any larger than fixed constant. (SBRJ19) extended this result by achieving comparable error rates even for a vanishing fraction of inliers a ž 1/log log n. Assuming n 2 d²/a" (TJSO14) proved that the Huber-loss estimator (Hub64) achieves optimal error rate O(d/a² (a2..) n) even for polynomially small fraction of inliers a 2 vd/n. n. This line of work culminated in (dNS21) which extended the result of (TJSO14) achieving the same guarantees with optimal sample complexity 2 d/a². For Gaussian design, similar result as (dNS21) can be extracted from independent work (PF20). Furthermore, the authors of (dNS21) extended these guarantees to deterministic design matrices satisfying only a spreadness condition (trivially satisfied by sub- uub-Gaussian design matrices).
Huber loss was also analyzed in context of linear regression in (SZF18; DT19; SF20; P1I.21.. These works studied models that are different from our model, and these results do not work in the case a = o(1) (SZF18) 8) used assumptions on the moments of the noise, (DT19) and (SF20) studied the model with non-oblivious adversary, and the model from (PJL21) allows corruptions in covariates.
In the context of sparse regression, less is known. When the fraction of observations is constant QQ)1, (NTN11) provided first consistent estimator. Later (DT19) and (SF20) improved that result (assuming a > (1),, but these results also work with non-oblivious adversary). In the case a = o(1) the algorithm of (SBRJ19) (for Gaussian designs) achieves nearly optimal error convergence Ó(k log" d))a²n). but requires 2 1/log log n. More recently, (dNS21) presented an algorithm for standard Gaussian design X N(0, 1y achieving the nearly optimal error convergence O(k/(a²-n) n)) for nearly optimal inliers fraction a z v(k log" d)/n. Both (SBRJ19) and (dNS21) use an iterative process, and require a bound || < d00) (for larger || these algorithms also work, but the fraction of inliers or the error convergence is worse). The algorithm from (dNS21), however, heavily relies on the assumption that X ~ N(0, 1)nxd and appears unlikely to be generalizable to more general families of matrices (including non-spherical Gaussian designs).
Our contribution. We propose new machinery design efficiently computable consistent esti- mators achieving optimal error rates and sample complexity against oblivious outliers. In particular, we extend the approach of (dNS21) to structured estimation problems, by finding a way to exploit adequately the structure therein. While consistent estimators have already been designed under more benign noise assumptions (e.g. the LASSO estimator for sparse linear regression under Gaussian noise), it was previously unclear how to exploit this structure in the setting of oblivious noise. One key consequence of our work is hence to demonstrate what minimal assumptions on the noise are sufficient to make effective recovery (in the sense above) possible. Concretely, we show
Oblivious PCA:
Under mild assumptions on the noise matrix N and common assumption on the parameter matrix L' -traditionally applied in the context of matrix completion (NW12)- we provide an algorithm that achieves optimal error guarantees.
Sparse regression: Under mild assumptions on the design matrix and the noise vector similar to the ones used in (dNS21) for dense parameter vectors 3 we provide an algorithm that achieves optimal error guarantees and sample complexity.
For both problems, our analysis improves over the state-of-the -ot and recovers the classical optimal guarantees, not only for Gaussian noise, but also under much less restrictive noise assumptions. At high-level, we achieve the above results by equipping the Huber loss estimator with appropriate regularizers. Our techniques closely follow standard analyses for M-estimators, but crucially depart from them when dealing with the observations with large perturbations. Furthermore, our analysis appears to be mechanical and thus easily applicable to many different estimation problems.
2 Results
Our estimators based regularized versions of the Huber loss. The regularizer we choose depends on the underlying structure of the estimation problem: We use E regularization to enforce sparsity in linear regression and nuclear norm regularization to enforce low-rank structure in the context of PCA. More formally, the Huber penally is defined as the function fn R - R such that
underlying reason is that the Gaussianity of X allows one to obtain several other desirable properties "for free".. For example, one could ensure that the noise vector is symmetric by randomly flipping the sign of each observation (y,, X:). the design matrix will still be Gaussian. See Section 2 for more in-depth discussion.
3

---

1/22 [h(1t- 5)
for |1| < h otherwise.
fu(t)
(2.1)
where > 0 is a penalty parameter. For X E RD, the Huber loss is defined as the function (x) LiE(D] (x))... We will define the regularized versions in the following sections. For matrix A, we use || [l. |lme ||A ||Almmax to denote its spectral, nuclear, Frobenius, maximum* use ||o||| and ||l|| to denote its l and & norms.
norms, respectively. For a vector
2.1
Oblivious principal component analysis
For oblivious PCA, we provide guarantees for the following estimator (G will be defined shortly):
i : argmin (F 100V7 p//////
(2.2)
LERUXK, m| sp/nn
Theorem 2.1. Let L' E Ruxa be an unknown deterministic matrix and let N be an n-by- n random matrix with independent, symmetrically distributed (about zero) entries and a == min N < <t) for some [, > 0. Suppose that rank(L")) = and || & ppin.
Then, with probability at least 1 1-2 2- over N. given Y = + N. { and p. the estimator Eq. (2.2)
with Huber parameter h = C ++( p/nt satisfies
Vrn a
|| - L-- 0
We first compare the guarantees of Theorem 2.1 with the previous results on robust PCA (CLMW1I) 11; ZLW* 10). The first difference that they require L" to satisfy certain incoherent conditions." 6 Con- cretely, they provide theoretical guarantees for < ([(=""((oog 2))-)), where μr is the incoherence parameter. In certain regimes, such constraint strongly binds with the eigenvectors of L', restricting the set of admissible signal matrices. Using the different assumption ||mx||max & p/n (commonly used 0 as 11 - oo) even when the ju-nccherence conditions are not satisfied for any μl < n n/log" n, and hence the results (CLMWI)) 11; ZLW* 10) cannot be applied. We remark that, without assuming incoherence, the dependence of the error on the maximal entry of L' is inherent (see Remark 3.2).
for matrix completion, see (NW12)), we can obtain nontrivial guarantees (i.e. || L- /
The second difference is that Theorem 2.1 provides significantly better dependence on the magnitude of the entry-wise mcasurement error. Specifically, in the settings of Theorem 2.1, (ZLW* 10) showed that if I." satisfies the incoherence conditions, the error of their estimator is O (n² If the entries of N are standard Gaussian with probability a (and hence [ & O()), and the entries of I," are bounded by O(1), then the error of our estimator is O(Vrn/ a), which is considerably better than O(r²)) as in (ZLW- 10). On the other hand, their еттоr does not depend on the magnitude p/n of the signal entries, so in the extreme regimes when the singular vectors of L' satisfy the incoherence conditions but L has very large singular values (so that the magnitude of the entries of L is significantly larger than 1), their analysis provides better guarantees than Theorem 2.1.
As another observation to understand Theorem 2.1, notice that our robust PCA model also captures the classical matrix completion settings. In fact, any instance of matrix completion be easily transformed into an instance of our PCA model: for the entries (i, f) that we do not observe, we can set Ni, to some arbitrarily large value =C(p, n) p/n, making the signal-to-noise ratio of the entry arbitrarily small. The observed (i.e. uncorrupted) O(a n²?) entries may additionally be perturbed by Gaussian noise with variance @ The error guarantees of the estimator in Theorem 2. is
*For matrix A, |mllmmx maxx
'We remark that in (CLMW11) 1) the authors showed that they consider non-symmetric noise when the
fraction inliers is large a > 1/2. However for smaller fraction of inliers their analysis requires the entries of the noise to be symmetric and independent, so for a < 1/2, their assumptions are captured by Theorem 2.1.
6 A rank-r x dimensional matrix M is u-incoherent if its singular vector decomposition M UIVT
satisties max;<[m] || eell= & Hr. mmxxcc]]]ll T eell? & ur
# and ||UV 1loo yur

---

Vrn/a)). (((//)+()/r//z) Thus, the dependency on the parameters p, S, and r is the same as in matrix completion and the error is within a factor of @ (())/a from the optimum for matrix completion. However, this worse dependency on is intrinsic to the more general model considered and it turns out to be optimal (see Theorem 2.4). On a high level, the additional factor of @( @(v1/a) comes from the fact that in our PCA model we do not know which entries are corrupted. The main consequence of this phenomenon that a condition of the form a 2 vr/n appears inherent to achieve consistency. To get some intuition on why this condition is necessary, consider the Wigner model where we are given matrix Y xx o W for flat vector E [=1)" and a standard Gaussian matrix W. Note, that the entries of W fit our noise model for Ç = 1, p/n 1 spectral norm of o concentrates around 20 v and thus it is to approximately recover the vector x for o = 1/a w(vn) (see (PWBM16).
r = 1 and a @(1oo) The impossible
2.2 Sparse regression
Our regression model considers a fixed design matrix X E RRnd and observations y = X +1 E R where 8 is an unknown s-sase parameter vector and 1) is random noise with P([n: 1) > a for all i E [n]. Earlier works (BJKKI7), (SBRJ19) focused on the setting that the design matrix consists of ii.d. rows with Gaussian distribution N(O, Σ) and the noise is 1) + w where Ç is deterministic (a spaase vector and w is subgaussian. As in (dNS21), our results for a fixed design and random noise can, in fact, extend to yield the same guarantees for this early setting (see Theorem 2.3). Hence, a key advantage of our results that the design X does not have to consist of Gaussian entries. Remarkably, some mild conditions. Concretely, we make the following three assumptions, the first two of which standard in the literature of sparse regression (e.g., see (Wai19), section 7.3):
handle arbitrary deterministic designs long they satisfy
1. For every column X' of X. ||*||| & vn.
2. Restricted eigenvalue property (RE-property): For every vector u E Rd such that?
[| > 0.1 ||| we have =1l |||| > A -||=|| for some parameter À > 0.
3. Well-spreadness property: For some (large enough) m [n]] and for every vector u Rd such that |uup(()))) > 0.1 -|Il[| and for every subset [n]] with [S] > n m, it holds that II(Xu)sll > X||Xu|].
Denote F2($) = Σ fz - (X;,B)) where X; are the rows of X, and fa is as in Eq. (2.1). We
devise our estimator for sparse regression and state its statistical guarantees below:
B = arg min [F(()) 100 logd -1181l))
(2.3)
&CR
Theorem 2.2. Let 8r Rd be an unknown k-sparse vector and let X Raxd be deterministic matrix such that for each column X of X, ||X'|| & vř, satisfying the RE-property with À > 0 and
well-spreadness property with m z --a""
klogd (recall that n > m)
Further, let n be n-dimensional random vector with independent. symmetrically distributed (about zero) entries and a = minjetu) P([n 1}.
Then with probability at least 1 d 10 over n, given X and y XB8 17, the estimator Eq. (2.3) satisfies
2 + }| of
klog d
and 11 & o klog d
an.n
There are important considerations when interpreting this theorem. The first is the special N(0,02) which satisfies our model for a @(1oo). For this case, it is well known (e.g..
7 For vector R and set [d]. we denote by us the restriction of v to the coordinates in S.
5

---

see (Wai19), section 7.3) that under the same RE assumption, the LASSO estimator achieves prediction error rate of O klugd O k Klogd a
X-a--n' matching our result. Moreover, this error rate essentially optimal. Under a standard assumption in complexity theory (NP & P/poly), the RE assumption is necessary when considering polynomial-time estimators (7.WJ14). Further, this also shows that the dependence on the RE constant seems unavoidable. Under mild conditions on the design matrix, trivially satisfied if the rows are i.i.d. Gaussian with covariance Σ whose condition number is constant, our guarantees are optimal up to constant factors for all estimators if k & d d (e.g, < )0,99), see (RWYII). This optimality also shows that our bound on the number of samples is best possible since otherwise we would not be able to achieve vanishing error. The (non-sparse version of) well-spreadness property was first used in the context of regression in (dNS21). In the same work the authors also showed that, under oblivious noise assumptions, some weak form of spreadness property is indeed necessary.
The second consideration is the optimal dependence on a: Theorem 2.2 achieves consistency as al (k log d/n). To get an intuition, observe that lower
long the fraction of inliers satisfies bounds for standard sparse regression show that, already for n ~ N(O, o Id,), it is possible to achieve consistency only for и = w(aRk log d) (if k & d'-0(1)). As for this 17. the number of entries of magnitude at most 1 Onn/o) with high probability, it follows that for a @(1/a) <
o ((k (k log d)/11 nt) no estimator is consistent.
To the best of our knowledge, Theorem 2.2 is the first result to achieve consistency under such minimalistic noise settings and deterministic designs. Previous results (BJKK17; SBRJ19; dNS21) focused on simpler settings of Gaussian design X and deterministic noise, and provide no guarantees for more general models. The techniques for Theorem 2.2 also extend to this case.
Theorem 2.3. Let B E Rd be an unknown k-sparse vector and let X be a n n-by-d random matrix with i.i.d. rows XI,... Xn N(0, Σ) for positive definite matrix Σ. Further, let 1l E R" be deterministic vector with a.n coordinates bounded by 1 in absolute value. Suppose that n 2 ([I) log where v(E) is the maximun diagonal entry of E and miin(E) (E) its smallest eigenvalue.
Then, with probability at least - d-10 over X, given X and = XB" + 17. the estimator Eq. (2.3) satisfies
n1 (
}|] 0 v(z) k logd Omin [I) a² n
- ||B-
v(Σ) k log d o (E) a
and
Even for standard Gaussian design X ~ N(O, 1yaxd the above theorem improves over previous results, which required sub-optimal sample complexity n v (k/a²) (22))-log log d- d-log]|s'|| For non-spherical Gaussian designs, the improvement over state of the art (SBRJ19) is more serious: their algorithm requires a > Q11/log log n),, while our Theorem 2.3 doesn't it have such restrictions and works for
all 2
klogd in many interesting regimes a is allowed to be smaller than n -Q(1) The (2)
v(E)
dependence on a is nearly optimal: the estimator is consistent as long as a w
v(E) klog
Tmial (2)
and from the discussion after Theorem 2.3, if & O(v(k log d)/n), no estimator is consistent.
Note that while we can deal with general covariance matrices, to compare Theorem 2.3 with Theo- rem 2.2 it is easier to consider Σ in a normalized form, when v(Σ) & 1. This can be easily achieved by scaling X. Also note that Theorem 2.2 can be generalized to the case || < vvn for arbitrary v > 0, and then the error bounds and the bound on m should be multiplied by v.
The REEproperty of Theorem 2.2 is a standard assumption in sparse regression and is satisfied by large family of matrices. For example, with high probability random matrix X with i.i.d. rows sampled from (00, Σ), with positive definite Σ d whose diagonal entries are bounded by 1, satisfies the RE-property with parameter Q miin (Σ)) for all subsets of [d] of size k (so for every possible support of (²) as long as long as n 2 ) k log dl (see (Wai19), section 7.3.3). The well- spread assumption is satisfied for such X with for all sets S C [n] of size m & en (for sufficiently small c) and for all subsets of [d] of size k as long as 2 (min(E) k log d.

---

2.3 Optimal fraction of inliers for principal component analysis under oblivious noise
We show here that the dependence on a we obtain in Theorem 2.1 is information theroetically optimal up to constant factors. Concretely, let L', N, a, p and Ç be as in Theorem 2.1, and let O < E < 1 and
successful (E, 6) -e-ek recovery algorithm for PCA is an algorithm that takes Y as input and returns a matrix L such that || LiIl== < E p with probability least 1 Ö.
can be easily seen that the Huber-loss estimator of Theorem 2.1 fails to be a successful weak- recovery algorithm if a of (r/nn) (for both cases [ < p/n n and p/n & G, we need a = (Vvrn)). A natural question to ask is whether the condition a = Q vr/n) is necessary in general. The following theorem shows that if = of ((Vr/)), then weak-recovery is ieformatiion-hhoortiice impossible. This means that the (polynomially small) fraction of inliers that the Huber-loss estimator of Theorem 2.1 can deal with is optimal up to a constant factor.
Theorem 2.4. There exists universal constant Co 0 such that for every 0
1 and 0 < ò < 1,
if == minn ,l & {] satisfies a Co (1- - 8) vr/n, and n is large enough, then it information- information-theorttiaally theoreticalll impossible to huve a successful (E, 8) - recovery algorithm.
The problem remains pnormatiio-thhoretice impossible (for the same regime of parameters) even if we assume that L' incoherent; more precisely, even if we know that L' has incoherence parameters that are as good as those of random flat matrix of rank r, the theorem still holds.
3 Techniques
To illustrate our techniques proving statistical guarantees for the Huber-loss estimator, we first use sparse linear regression as a running example. Then, we discuss how the same ideas apply to principal component analysis. Finally, we also remark our techniques for lower bounds.
3.1 Sparse linear regression under oblivious noise
We consider the model of Theorem 2.2. Our starting point to attain the guarantees for our estimator Eq. (2.3), i.e., β arg minperi F2(ß) + 100 n log al [[]i|],, is classical approach for M-estimators (see c.g. (Wail9), chapter 9). For simplicity, we will refer to F2(B) as the loss function and to ||ı|], as the regularizer. At high level, it consists of the following two ingredients:
an upper bound on some norm of the gradient of the loss function at the parameter (",
(II) lower bound on the curvature of the loss function (in form of local strong convexity bound) within a structured neighborhood of f². The structure of this neighborhood can roughly be controlled by choosing the appropriate regularizer.
The key aspect of this strategy is that the strength of the statistical guarantees of the estimator crucially depends on the directions and the rudius in which we can establish lower bounds on the curvature of the function. Since these features are inherently dependent on the landscape of the loss function and the regularizer, they may differ significantly from problem to problem. This strategy has been applied successfully for many related problems such as compressed sensing or matrix completion albeit with standard noise assumptions." 8 Under oblivious noise, (dNS21) used a particular instantiation this framework to prove optimal convergence of the Huber-loss. without any regularizer for standard linear regression. Such estimator, however, doesn't 't impose any structure on the neighborhood of 8** considered in (II) and thus, can only be used to obtain sub-optimal guarantees for sparse regression.
In the context of sparse regression, the above two conditions translate to: (I) an upper bound on the largest entry in absolute value of the gradient of the loss function at f", and (II) lower bound on the curvature of F2 within the set of approximately k-sparse vectors? close to f². We use this recipe to show that all approximate minimizers of are close to 8 While the idea of restricting to only approximately sparse directions has also been applied for the LASSO estimator in sparse
The term "standard noise assumptions" is deliherately vague; as a concrete example, we will refer Buub)-Gussiian noise distributions. See again chapter 9 of (Wail9) for a survey. We will clarify this notion in the subsequent paragraphs.
7

---

regression under standard Gaussian noise. in the presence of oblivious noise, our analysis of the Huber-loss function requires more careful approach.
More precisely, under the assumptions of Theorem 2.2, the error bound can be computed as
s S|IGllie
(3.1)
K
where is gradient of Huber loss at f",, Il-llieg is a norm dual to the regularization norm (which is equal to II-IImax for l regularizer), is a structure parameter, which is equal to vk/ A, and k is restricted strong convexity parameter. Note that by error here we mean J || 8'1l--
Vii
Similarly, under under assumptions of Theorem 2.1, we get the error bound Eq. (3.1), where i gradient of Huber loss at L', ||- Il-llieg is a norm dual to the nuclear norm (i.e. the spectral norm), structure parameter is Vr, and x is restricted strong convexity parameter. For more details on the conditions of the error bound, see the supplementary material. Below, we explore the bounds on the norm of the gradient and on the restricted strong convexity parameter.
Bounding the gradient of the Huber loss. The gradient of the Huber-loss F2(.) at 6" has the form VF=(6") -= f [3[n) X; where X; is the i-th row of X. The random variables f/ n: J. e [n]. are independent, centered, symmetric and bounded by 2. Since we assume that each column of X has norm at most Vı1, the entries of the row X, are easily bounded by Vı.. Thus, VF2(8*) is a vector with independent, symmetric entries with bounded variance, so its behavior can be easily studied through standard concentration bounds. In partieular, by a simple application of Hoeffding's inequality, we obtain, with high probability,
(V
max ]=[4]
Σ flm) Xij & O(v logd VE[M]
(3.2)
Local strong convexity of the Huber loss. Proving local strong convexity presents additional challenges. Without the sparsity constraint, (dNS21) showed that under a slightly stronger spreadness assumptions than Theorem 2.2, the Huber loss is locally strongly convex within a constant radius R ball centered at 8o whenever linear parts.) Using their result as a black-box, one can obtain the error guarantees of Theorem 2.2. but with suboptimal sample complexity. The issue is that with the substantially smaller sample size of Ókk a²)) that resembles the usual considerations the context of sparse regression, the Huber loss is not locally strongly convex around 68 uniformly across all directions, so we cannot hope to prove convergence with optimal sample complexity using this argument. To overcome this obstacle, we make use of the framework of M-estimators: Since we consider a regularized version of the Huber loss, it will be enough to show local strong convexity in a radius uniformly across all directions which are approximalely k-sparse. For this substantially weaker condition, Ö(k/a²) will be enough.
d/a². (This function not globally strongly convex due to its
More in details, for observations y XB" + 17 and an arbitrary u E Rd of norm || < R, is possible to lower bound the Hessian 10 of the Huber loss at 8 + u by:!!
HF2(B" + + = Σ f [Xuu) m X,X,
Σ
1[0x0000133] X/XI
1
1=1
M(u)= = Σ [[(x, [[m//<1] X,X,T
As can be observed, we do not attempt to exploit cancellations between Xu and 17. Let Q := {i E [m]] In| & }} be the set of uncorrupted entries of 7. Given that with high probability Q has size Q(a-n). the best outcome we can hope for is to provide a lower bound of the form (u, M(u)u) > an in the direction / - 8 In (dNS21), it was shown that if the span of the measurement matrix X is well spread, then (u, M()uu) > Q(a nt).
1he Hessian does not exist everywhere. Nevertheless, the second derivative of the penalty function f2 exists an function in the sense that f(bb) f(aa) = l/" 11j This property is enough for our purposes. 11 A more extensive explanation of the first part of this analysis can be found in (dNS21).
8

---

If the direction B- was fixed, it would suffice to show the curvature in that single direction through the above reasoning. However, & depends on the unknown random noise vector 1 Without the regularizer in Eq. (2.3), this dependence indicates that the vector f may take any possible direction, so one needs to ensure local strong convexity to hold in a constant-radius ball centered at 8". That is, jill min((((() > a2 n). It can be shown through a covering argument (of the ball) that this bound holds true for n > d/a². This is the approach of (dNS21).
The minimizer of the Huber loss follows a sparse direction. The main issue with the above approach is that no information concerning the direction & - 8² is used. In the settings of sparse regression, however, our estimator contains the regularizer 11 The main consequence of the
regularizer is that the direction p-8 is approximately flat in the sense 11 < < B -
The reason 12 is that due to the structure of the objective function in Eq. (2.3) and concentration of the gradient Eq. (3.2), the penalty for dense vectors is larger than the absolute value of the inner product (VF(8"), B B*) (which, as previously argued, concentrates around its (zero) expectation).
This specific structure of the minimizer implies that it suffices to prove local strong convexity only in approximately sparse directions. For these of directions, we carefully construct sufficiently small covering set so that n > Okk/a²) samples suffice ensure local strong convexity over it. Remark 3.1 (Comparison with LASSO). is important to remark that while this approach of only considering approximately sparse directions has also been used in the context of sparse regression under Gaussian noise (e.g. the LASSO estimator), obtaining the desired lower bound is considerably easier in these settings as it directly follows from the restricted eigenvalue property of the design matrix. In our case, we require an additional careful probabilistic analysis which uses a covering argument for the set of approximately sparse vectors. As we see however, it turns out that we do not need any additional assumptions on the design matrix when compared with the LASSO estimator except for the well-spreadness property (recall that some weak version of well-spreadness is indeed necessary in robust settings, see (dNS21)).
3.2 Principal component analysis under oblivious noise
A convenient feature of the approach in Section 3.1 for sparse regression, is that it can be easily applied additional problems. We briefly explain here how to apply for principal component analysis. We consider the model defined in Theorem 2. We use an estimator based on the Huber loss equipped with the nuclear norm as a regularizer to enforce the low-rank structure in our estimator
i ==
argmin LER || Spin
(Ectp/n(Y L) + 100V7(C + (enn(CC+nnnnll p/n)IILIlmm)-
(3.3)
In this setting, the gradient VY LL) is matrix with independent, symmetric entries which are bounded (by + p/n) and hence its spectral norm is O ((C ( p/n) with high probability. Local strong convexity can be obtained in similar fashion as shown in Section 3:1: due to the choice of the Huber transition point all entries with small noise are in the quadratic part of F. Moreover, the nuclear norm regularizer ensures that the minimizer is an approximately low-rank matrix in the sense that ||Me & ([V So again, it suffices to provide curvature of the loss function only on these subset of structured directions.
Remark 3.2 (Incoherence spikiness). Recall the discussion on incoherence in Section 2. If for every μ & n n//log² matrix L." doesn't satisfy j--ncoherence conditions, the results in (CLMW11; ZLW* 10) cannot be applied. However, our estimator achieves error |Iا-L"Il=/ || - 0 и co. Indeed,let w(1) & (n) & o(log² n) and assume Ç 0. Let u E R" be f(r)-pparse unit vector whose nonzero entries are equal to 1/ f()). Let v E Rd be a vector with all entries equal to 1/Vī. Then, TOT does not satisfy incoherence with any f < n/ (n). We have || 1. and the error of our estimator is O(1((a (n))). so it tends to zero for constant (or even some subconstant) a.
Furthermore notice that the dependence of the error of Theorem 2.1 on the maximal entry of I.* is inherent if we do not require incoherence. Indeed, consider L₁ = b ejei for large enough b > 0
This phenomenon is consequence of the decomposabillit of the Lj norm, see the supplementary material.

---

and L2 ezez". For constant a, let Nii be with probability a/2, 0 with probability a/2 and with probability
a. Then given Y we cannot even distinguish between cases L' L1 or L' L2. and since ||_.; - 1211p e b, the error should also depend on b.
Remark 3.3 (a vs a²: what if one knows which entries are comuutte??). As was observed in Section the error bound of our estimator is worse than the error for matrix completion by a factor 1/ Va. We observe similar effect in linear regression: if, as in matrix completion, we are given randomly chosen a fraction of observations {(i, yi (X,, (²) + 7))) the remaining samples we may not assume any bound on the sgmal-to-noiss ratio, then this problem is essentialy the same as linear regression with an observations. Thus the optimal prediction error rate is O ((vd/(an)) Now, if we have X + d, where n ~ N(0, 1/a²), then with probability O(a), Inpl & 1, but the optimal prediction error rate in this case is O O(vd/(a²r)) So in both linear regression and robust PCA, prior knowledge of the set of corrupted entries makes the problem easier.
i=1 where 7 N(0, 1)", and since for
3.3 Optimal fraction of inliers for principal component analysis under oblivious noise
In order to prove Theorem 2.4, will adopt generative model for the hidden matrix L": We will generate L' randomly but assume that the distribution is known to the algorithm. This makes the problem easier. Therefore, any impossibility result for this generative model would imply impossibility for the more restrictive model for which L is deterministic but unknown.
We generate random flat matrix L' using nl independent and uniform random bits in such way that L of rank and incoherent with high probability. Then, for every constant 0 < & 1, we find a distribution for the random noise N in such way that the fraction of inliers satisfies
== Pl & CI = (
and such that the mutual information between L and Y = L' N can be upper bounded as I(L"; Y) & O(E independent L and Y will be. Now using an inequality that is similar to the standard Fano-inequality but adapted to weak-recovery, we show that if there is successful (e, 5)-weak recovery algorithm for L' and N, then I(L": > Q(11- - 22)2- together, deduce that if & is small enough, it is impossible to have successful (e, 5)-weak recovery algorithm for L' and N.
r). Roughly speaking the smaller & gets, the more
8) -)-P2 n r). By combining all these observations
Acknowledgments and Disclosure of oufFuu Funding
The authors thank the anonymous reviewers for useful comments. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No 815464).
References
[Ad190] Robert J. Adler, An introduction continuity, extrema, and related topics for general gaussian processes, Lecture Notes-Monograph Series 12 (1990), i-155.
[BBC1I]
Dimitris Bertsimas, David B. Brown, and Constantine Caramanis, Theory and appli- cations of robust optimization, SIAM Review 53 (2011), no. 3, 464-501. 2
[BGN09] Aharon Ban-Tal, Laurent El Ghaoui, and Arkadi Nemirovski, Robust optinization, Princeton Series in Applied Mathematics, vol. 28, Princeton University Press, 2009.
[BJKK17] Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar, Con- sistent robust regression, NIPS, 2017, pp. 2107-2116. 5.
[CLMW11] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright, Robust principal compo- nent analysis?, J. ACM 58 (2011) 1), 3, 11:1-11:37. 2, 9,
[dNS21] Tommaso d' Orsi, Gleb Novikov, and David Steurer, Consistent regression when obliy- ious outliers overwhelm, 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, PMLR, 2021. 1, 6, 8,
10

---

[DT19] Arnak Dalalyan and Philip Thompson, Outlier-robust estimation of sparse linear model using I penalize huber's m-estimator, Advances in Neural Information Pro- cessing Systems, 2019, pp. 13188-13198.
[Hub64] Peter J. Huber, Robust estimation of location parameter, Ann. Math. Statist. 35 (1964), no. 1, 73-101. 3
[MMYSB1]] Ricardo A. Maronna, R. Douglas Martin, Victor J. Yohai, and Matías Salibián-Barrera Robust statistics:
Theory and methods, 2 ed., Wiley Series in Probability and Statistics, John Wiley & Sons, 2019. 2
[NTN11] Nasser Nasrabadi, Trac Tran, and Nam Nguyen, Robust lasso with missing and grossly corrupted observations, Advances in Neural Information Processing Sys- tems (J. Shawe-Taylor R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, eds.), vol. 24, Curran Associates, Inc., 2011. 3
[NW12] Sahand Negahban and Martin Wainwright, Restricted strong convexity and weighted matrix completion: Optimal bounds with noise, Journal of Machine Learning Research 13 (2012), 1665-1697. 3,
[PF20] Scott Pesme and Nicolas Flammarion, Online robust regression via sgd on the 11 loss, Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, eds.), vol. 33, Curran Associates, Inc., 2020, pp. 2540 2552. 3
[PJL21] Ankit Pensia, Varun Jog, and Po-Ling Loh, Robust regression with covariate filtering:: Heavy tails and adversarial contamination, 2021. 2.3
[PWBM16] Amelia Perry, Alexander S. Wein, Afonso S. Bandeira, and Ankur Moitra, Optimality and sub-optimality of PCA for spiked random matrices and synchronization, CoRR abs/1609.052. 005560 (2016).
[RV10] Mark Rudelson and Roman Vershynin, Non-asymptotic theory of random matrices: Extreme singular values, Proceedings of the International Congress of Mathematicians 2010, ICM 2010 (2010).
[RWY10] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu, Restricted eigenvalue properties for correlated gaussian designs, Journal of Machine Learning Research 11 (2010), no. 78, 2241-2251
[RWY11] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu, Minimax rates of estimation for high-dimensional linear regression over Eg -balls, IEEE Transactions on Information Theory 57 (2011), no. 10, 1994.6994. 6
[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, 2019, pp. 2892-2897 2, 3, 5,
[SF20] Takeyuki Sasai and Hironori Fujisawa, Robust estimation with lasso when outputs are adversarially contaminated, 2020.
[SZF18] Qiang Sun, Wenxin Zhou, and Jianqing Fan, Adaptive huber regression. 2,
[TJSO14] Efthymios Tsakonas. Joakim Jaldén, Nicholas D Sidiropoulos, and Björn Ottersten, Convergence of the huber regression m-estimate in the presence of dense outliers, IEEE Signal Processing Letters 21 (2014), no. 10, 1211-1214. 2,
[Ver18] Roman Vershynin, High-dimensional probability: introduction with applications in data science, Cambridge Series in Statistical and Probabilistic Mathematics, Cam- bridge University Press, 2018
[Vis18] Nisheeth Vishnoi, Algorithmss for convex optimization, Cambridge University Press, 2018.

---

[Wai19] Martin J. Wainwright, High High-ddimensional statistics: A non-asymptoric viewpoint. Cam- bridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2019. 5, 7
10L Zihan Zhou, Xiaodong Li, John Wright, Emmanuel J. Candès, and Yi Ma, Stable principal component pursuit, ISIT, IEEE, 2010, pp. 1518- 1522. 2, 4,
[ZWJ14] Yuchen Zhang, M. Wainwright, and Michael I. Jordan, Lower bounds on the per- formance of polynomial time algorithms for sparse linear regression, COLT, 2014.
12


Reviews:
[{"review_id": "ej7pVfTgqD", "reviewer": "Reviewer_y31x", "summary": "This paper studies sparse regression and principal component analysis under \noblivious perturbations. \n\nMain contributions:\n1. The authors propose estimators that achieve the optimal error guarantees for PCA and sparse regression under oblivious perturbations separately, by minimizing the Huber loss function with some regularization. For sparse regression the estimator also achieves the optimal sample complexity. \n2. This machinery has the potential to be applied to other estimation problems.\n\nPost rebuttal: I acknowledge that I have read the authors responses and other reviewers' comments.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is reasonably well-written, with clear introduction of the problem and comparison with the related work. The result of the paper improves over the state-of-the-art. Some comments on improving the paper:\n\n1. Current version of the paper is very theoretical, it will be better if some experimental results could be added. \n2. The well-spreadness property at line 181 could is not clear: in the current statement it sounds to me like this property is satisfied as long as it holds for any arbitrary choice of $m$. But according to my understanding you do need the $m$ here to have some lower bound (otherwise setting $m = 0$ is trivial). What is the desired size of $m$? \n3. Typos in the paper: (1) At line 57, \"preturbations\" should be \"perturbations\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "dCqbhhf8i8H", "reviewer": "Reviewer_Aoiu", "summary": "The paper studies algorithms for sparse regression and principle component analysis using Huber loss in the presence of overwhelming oblivious noise.\nIn particular, the fraction of inliers, $\\alpha$, is going to $0$ but it is still possible to achieve consistency as the noise model is benign (oblivious, symmetric noise).\nThe paper obtains optimal error rates and dependence on $\\alpha$ for a wide range of distribution assumptions.\nThese rates are achieved by using regularized Huber loss (nuclear norm for the matrix case and $\\ell_1$-norm for regression case).\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper makes significant contributions for sparse (and rank-constrained) models in the presence of overwhelming noise. The proof strategy follows the standard analysis of regularized high-dimensional models [Wai19], in combination with a recent line of work on Huber regression for optimal error in robust regression ([SFZ19, PJL20, SF20, dNS21]). The paper is also well-written and usually clear. \n\nI thus recommend \"accept\". Some comments and suggestions are attached below:\n\n**Main Comment**\n\n\n+ Citations to several existing works on robust linear linear regression that use Huber loss are missing: [SFZ19, PJL20, SF20]. (Surprisingly [SFZ19] is listed in references but not mentioned in the paper. [SFZ19] is not even cited in the full paper attached as the supplementary material.)  These papers also follow the same proof strategy. In particular, regarding Line 201: The (non-sparse version of) well-spreadness condition looks very similar to the weak stability of [PJL20] (also see [PJL20, Theorem 3.1] ). Although the aforementioned works are looking at a different corruption model, there seems to be a strong relation in techniques, and thus should be discussed.\n\n**Other Comments**\n\n+ Please make it explicit early on that the regression setting only allows corruption in responses (and not the covariates). Assuming clean covariates simplifies the problem considerably.\n\n+ Lines 48-55: It says that the error will be mentioned in $\\|\\cdot\\|$ but the following text in Section $1$ mentions rates for error in $\\|\\cdot\\|^2$.\n\n+ Footnote 3: The second sentence should make it explicit that the reduction is for Gaussian design. I found it confusing at first.\n\n+ Line 123: Define maximum norm. It is less standard than the others.\n\n+ Lines 204-209: it is not clear from these lines that the condition on $\\alpha$ is optimal. Please add more details for clarity.\n\n+ When referencing to books, please mention the specific result being used (or a chapter for a broad topic).\n\n**References**\n\n+ [SF20] Sasai, T. & Fujisawa, H. Robust estimation with Lasso when outputs are adversarially contaminated. arXiv:2004.05990 (2020).\n+ [PJL20] Pensia, A., Jog, V. & Loh, P. Robust regression with covariate filtering: Heavy tails and adversarial contamination. arXiv:2009.12976 (2020).\n+ [SFZ19] Sun, Q., Zhou, W. & Fan, J. Adaptive Huber Regression. arXiv:1706.06991 (2019).\n\n---\nAfter the Author Feedback\n\nI thank the authors for their thoughtful response. I am maintaining my score and thus recommend acceptance of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Wsup8Tz9smt", "reviewer": "Reviewer_ALou", "summary": "The authors study PCA and sparse regression in the presence of an oblivious adversary. The observation model is as follows: the observations may have symmetric, independent, additive noise. Each noise term is bounded by $\\zeta$ with probability at least $\\alpha$ which can be much smaller than 1. The authors show that the estimators which minimize Huber loss with appropriate $\\ell_1$ penalty achieve optimal error rates.\n\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors explain the implications of their results in detail. They give intuition to setup sketch their proofs. Assumptions about the design matrix and the noise are weaker than those in related prior work.\n\nLine 205: \\alpha should be \\alpha^2\nLine 208: use appropriate placeholder constants in front of = and <= \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NxLdpcHAJO", "reviewer": "Reviewer_3eeA", "summary": "The authors have proved non-trivial estimation error bounds for one type of robust estimate for sparse linear regression and PCA. Specifically, the estimate is constructed by minimizing the Huber Loss function with L1 regularization.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think overall the paper is well written. For each problem analyzed in this paper, there are sufficient comparisons with the prior work in terms of the sharpness of the error bound and shows when the error bounds derived in this paper are tighter. The discussion of the techniques looks clear. My major concerns of the paper are:\n1) While the authors have claimed that their techniques provide a general framework that proves tight error bound for Huber loss-based robust estimate. However, besides the proof details specific to the two problems studied in the paper, I do not find anything new in the approach. To claim a general framework, I am expecting a statement that as long as the problem satisfies certain general properties, then there is a tight error bound for a type of robust estimate.\n2) Related to the above point, it is unclear to me why the authors only looked at the Huber loss function. It would be nice and more general to say that as long as the loss function satisfies some assumptions, the error bounds hold. Then point out that Huber loss is one example and hopefully the authors can show a second example of the robust loss function.   \n\nOverall, despite the concerns, I think it is a good paper to be accepted.    ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is a theoretical paper and the main limitation is that the paper mainly looks at two specific problems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the fundamental problems of Principal Component Analysis (PCA) and Sparse Linear Regression (SLR) in the presence of oblivious outliers. In the oblivious noise model, a fraction of the labels can be adversarially corrupted and the corruptions are assumed to be independent of the covariates. This corruption model is significantly weaker than other models studied in the recent literature. In particular, recovery is information-theoretically possible even when the fraction of inliers is close to zero. Prior work had developed efficient algorithms for linear regression in the oblivious noise model. The current work extends these previous ideas to PCA and SLR, obtaining efficient algorithms with near-optimal statistical guarantees under a range of distributional assumptions. The reviewers agreed that the contributions are significant and the paper should appear in NeurIPS.
Decision: Accept (Poster)