Efficient Algorithms for Outlier-Robust Regression

Introduction

An influential recent line of work has focused on developing robust learning algorithms– algorithms that succeed on a data set that has been contaminated with adversarially corrupted outliers. It has led to important achievements such as efficient algorithms for robust clustering and estimation of moments [LRV16, DKK+16, CSV17, KS17c, KS17a] in unsupervised learning and efficient learning of halfspaces [KLS09, DKS17] with respect to malicious or “nasty noise” in classification. In this paper, we continue this line of work and give the first efficient algorithms for performing outlier-robust least-squares regression. That is, given a training set drawn from distribution ${\cal D}$ and arbitrarily corrupting an $\eta$ fraction of its points (by changing both labels and/or locations), our goal is to efficiently find a linear function (or polynomial in the case of polynomial regression) whose least squares loss is competitive with the best fitting linear function for ${\cal D}$.

We give simple examples showing that unlike classical regression, achieving any non-trivial guarantee for robust regression is information-theoretically impossible without making assumptions on the distribution $\mathcal{D}$. In this paper, we study the case where the marginal of $\mathcal{D}$ on examples in the well-studied class of hypercontractive distributions. Many natural distributions such as Gaussians, strongly log-concave distributions, and product distributions on the hypercube with bounded marginals fall into this category.

In outlier-robust regression, our goal is similar with the added twist that we only get access to a sample from the distribution $\mathcal{D}$ where up to an $\eta$ fraction of the samples have been arbitrarily corrupted.

Observe that the corruptions can be adaptive, that is, they can depend on the original uncorrupted sample $X$ in an arbitrary way as long as $|U\cap X|/|X|\geqslant 1-\eta$. In unsupervised learning, this has been called the strong adversary model of corruptions and is the strongest notion of robustness studied in the context.

2 Statement of Results

Our main results give outlier-robust least-squares regression algorithms for hypercontractive distributions.

In addition, we say that $D$ is certifiably $(C,4)$-hypercontractive if there is a degree $4$ sum-of-squares proof of the above inequality.

Observe that $4$-hypercontractivity is invariant under arbitrary affine transformation, and in particular, doesn’t depend on the condition number of the covariance of the distribution.

We will elaborate on the notion of certifiability later on (once we have the appropriate preliminaries). For the time being, we note that many well-studied distributions including (potentially non-spherical) Gaussians, affine transformations of isotropic strongly log-concave distributions, the uniform distribution on the Boolean hypercube, and more generally, product distributions on bounded domains are known to satisfy this condition with $C$ a fixed constant.

We also get analogous results for outlier-robust polynomial regression. See Theorem A.3.

We believe that the dependence of the error on $\eta$ is likely suboptimal A previous version of this paper had an erroneous claim about an information-theoretic lower bound on the error of any estimator as a function of $\eta$. This was due to an issue in the analysis of the distribution we had constructed for the purpose of the lower bound. This was pointed out to us by Ainesh Bakshi and Adarsh Prasad. . Finding an efficent algorithm for outlier-robust regression with an improved/right dependence on $\eta$ is an outstanding open problem.

Our work has immediate applications for learning Boolean functions in the nasty noise model, where the learner is presented with an $\eta$-corrupted training set that is derived from an uncorrupted training set of the form $(x,f(x))$ with $x$ drawn from ${\cal D}$ on $\{0,1\}^{n}$ and $f$ is an unknown Boolean function. The goal is to output a hypothesis $h$ with $\ProbOp_{x}[h(x)\neq f(x)]$ as small as possible. The nasty noise model is considered the most challenging noise model for classification problems in computational learning theory.

Applying a result due to [KKMS08] (c.f. Theorem 5) for learning with respect to adversarial label noise only (standard agnostic learning) and a generalization of Theorem 1.3 to higher degree polynomials (see Theorem A.3) we obtain the following:

Let ${\cal C}$ be a class of Boolean functions on $n$ variables such that for every $c\in{\cal C}$ there exists a (multivariate) polynomial $p$ of degree $d(\varepsilon)$ with $\E_{x\sim D}[(p(x)-c(x))^{2}]\leqslant\varepsilon$. Assume that $d(\varepsilon)$ is a constant for any $\varepsilon=O(1)$ and that ${\cal D}$ is $(C,4)$ hypercontractive for polynomials of degree $d(\varepsilon^{2})$. Then ${\cal C}$ can be learned in the nasty noise model in time $n^{O(d(\varepsilon^{2}))}$ via an output hypothesis $h$ such that $\ProbOp_{x\sim{\cal D}}[h(x)\neq c(x)]\leqslant O(\sqrt{\eta})\E_{x\sim D}[(p(x)-c(x))^{4}]+\varepsilon$.

One of the main conclusions of work due to [KKMS08] is that the existence of low-degree polynomial approximators for a concept class ${\cal C}$ implies learnability for ${\cal C}$ in the agnostic setting. Corollary 1.4 shows that existence of low-degree polynomial approximators and hypercontractivity of $D$ imply learnability in the harsher nasty noise model.

We note that Corollary 1.4 gives an incomparable set of results in comparison to recent work of [DKS17] for learning polynomial threshold functions in the nasty noise model.

Using a set of different techniques, Diakonikolas, Kamath, Kane, Li, Steinhardt and Stewart [DKK+18] and Prasad, Suggala, Balakrishnan and Ravikumar [PSBR18] also obtained robust algorithms for regression in the setting where data $(x,y)$ is generated via the process: $y=\langle w,x\rangle+e$ for an fixed unknown vector $w$ and zero mean noise $e$. For improved bounds for the case when $x$ is distributed according to a Gaussian, see recent (independent and concurrent) work due to Diakonikolas, Kong, and Stewart [DKS18].

3 Our Approach

In this section, we give an outline of Theorem 1.3. At a high level, our approach resembles several recent works [MSS16, BM16, PS17, KS17c, HL17] starting with the pioneering work of [BKS15] that use the Sum-of-Squares method for designing efficient algorithms for learning problems. An important conceptual difference, however, is that previous works have focused on parameter recovery problems. For such problems, the paradigm involves showing that there’s a simple (in the “SoS proof system”) proof that a small sample uniquely identifies the underlying hidden parameters (referred to as “identifiability”) up to a small error.

In contrast, in our setting, samples do not uniquely determine a good hypothesis as there can be multiple hypotheses (linear functions) that all have low-error on the true distribution. Our approach thus involves establishing that there’s a “simple” proof that any low-error hypotheses that is inferred from the observed (corrupted) sample has low-error on the true distribution (we call this certifiability of a good hypothesis). To output a good solution in our approach (unlike in cases where there are uniqueness results), we have to crucially rely on the convexity (captured in the SoS proof system) of the empirical loss function.

For concreteness in this high-level description, we suppose that for $(x,y)\sim\mathcal{D}$, the distribution on $x$ is $(C,4)$-hypercontractive for a fixed constant $C$ and $\E[y^{4}]=O(1)$. Further, it can also be shown that, with high probability, $\hat{\mathcal{D}}$ is also $(O(1),4)$-hypercontractive as long as the size of the original uncorrupted sample $X$ is large enough.

It is easy to show that the minimum of the optimization program $\opt(\widehat{\mathcal{D}})\lessapprox\opt(\mathcal{D})$ (up to standard generalization error) by setting $X^{\prime}=X$ and $w_{i}=1$ if and only if $i$’th sample is uncorrupted. By the above arguments, solutions to the above program satisfy the bound stated in Theorem 1.3. Unfortunately, this is a quadratic optimization problem and is NP-hard in general.

We are now ready to describe the key idea that allows us to essentially turn this hopelessly inefficient algorithm into an efficient one. This exploits a close relationship between the simplicity of the proof of robust certifiability and the success of a canonical semi-definite relaxation of (1.1).

A priori, we appear to have made our job harder. While computing a distribution on solutions is no easier than computing a single solution, even describing a distribution on solutions appears to require exponential resources in general. However, by utilizing the convexity of the square loss, we can show that having access to just the first moments of $\mu$ is enough to recover a good solution.

Formally, by the convexity of the square loss, the above inequality yields:

All of the above still doesn’t help us in solving program 1.1 as even finding first moments of distributions supported on solutions to a polynomial optimization program is NP-Hard.

The key algorithmic insight is to observe that we can replace distributions $\mu$ by an efficiently computable (via the SoS algorithm) proxy called as pseudo-distributions without changing any of the conclusions above.

Thus, the important remaining steps are to show that 1) the inequality (1.2) (which is essentially the conclusion of our robust certifiability lemma) and 2) the convexity argument in (1.4) has a low-degree SoS proof. We establish both these claims by relying on standard tools such as the SoS versions of the Cauchy-Schwarz and Hölder’s inequalities.

We give a brief primer to the SoS method in Section 4 that includes rigorous definitions of concepts appearing in this high-level overview.

4 Related Work

It is common for “robust regression” to refer to a scenario where only the labels are allowed to be corrupted adversarially (for example, see [BJKK17] and the references therein), or where the noise obeys some special structure (e.g., [HS10]) (although there are some contexts where both the covariates (the $x$’s) and labels may be subject to a small adversarial corruption [CCM13]).

What distinguishes our setting is 1) we do not assume the labels come from a generative model; each $(x,y)$ element of the training set is drawn iid from ${\cal D}$ and 2) we make no assumptions on the structure or type of noise that can affect a training set (other than that at most an $\eta$ fraction of points may be affected). In contrast to the parameter recovery setting, our goal is similar to that of agnostic learning: we will output a linear function whose squared error with respect to ${\cal D}$ is close to optimal.

From a technical standpoint, as discussed before our work follows the recent paradigm of converting certifiability proofs to algorithms. Previous applications in machine learning have focused on various parameter-recovery problems in unsupervised learnings. Our work is most closely related to the recent works on robust unsupervised learning (moment estimation and clustering) [KS17c, HL17, KS17b].

Preliminaries and Notation

2 Distribution Families

Our algorithmic results for a wide class of distributions that include Gaussian distributions and others such as log-concave and other product distributions. We next define the properties we need for the marginal distribution on examples to satisfy.

Many natural distribution families satisfy certifiable hypercontractivity with reasonably growing functions $C$. For instance, Gaussian distributions, uniform distribution on Boolean hypercube satisfy the definitions with $C(r)=cr$ for a fixed constant $c$. More generally, all distributions that are affine transformations of isotropic distributions satisfying the Poincaré inequality [KS17a], are also certifiably hypercontractive. In particular, this includes all strongly log-concave distributions. Certifiable hypercontractivity also satisfies natural closure properties under simple operations such as affine transformations, taking bounded weight mixtures and taking products. We refer the reader to [KS17c] for a more detailed overview where certifiable hypercontractivity is referred to as certifiable subgaussianity.

Robust Certifiability

The conceptual core of our results is the following robust certifiability result: for nice distributions (e.g., as defined in Definition 2.1), a regression hypothesis inferred from a large enough $\varepsilon$-corrupted sample has low-error over the uncorrupted distribution.

We begin by giving a robust certifiability claim for arbitrary distributions for L1 regression.

The error that we incur depends on the L2 squared loss of the best fitting regression hypothesis, and in particular, we do not obtain consistency in the statistical sense: i.e, the error incurred by the regression hypothesis does not vanish even in the “realizable” case when, in the true uncorrupted distribution, there’s a linear function that correctly computes all the labels. In Section 6, we show that if we make no further assumption on the distribution, then this is indeed inherent and that achieving consistency under adversarial corruptions is provably impossible without making further assumptions. In the following subsection, we show that assuming that the moments of the underlying uncorrupted distribution are “bounded” (i.e., linear functions of the distribution are hypercontractive), one can guarantee consistency even under the presence of adversarial outliers.

While the certifiability statements are independently interpretable, for the purpose of robust regression, it might be helpful to keep in mind that $D$ corresponds to uniform distribution on large enough sample from the unknown uncorrupted distribution while $D^{\prime}$ corresponds to the uniform distribution on the sample that serves as the “certificate”.

2 Robust Certifiability for Hypercontractive Distributions

The main result of this section is the following lemma.

Let $G$ be a coupling between $\mathcal{D},\mathcal{D}^{\prime}$. That is, $G$ is a joint distribution on $(x,y),(x^{\prime},y^{\prime})$ such that the marginal on $(x^{\prime},y^{\prime})$ is $\mathcal{D}^{\prime}$ and the marginal on $(x,y)$ is $\mathcal{D}$ satisfying $\ProbOp_{G}\bm{1}\Set{(x,y)=(x^{\prime},y^{\prime})}=1-\eta.$

Let $((x,y),(x^{\prime},y^{\prime}))\sim\mathcal{G}$. Writing $1=\bm{1}\Set{(x,y)=(x^{\prime},y^{\prime})}+\bm{1}\Set{(x,y)\neq(x^{\prime},y^{\prime})}$, we obtain:

Now, by using hypercontractivity of $\mathcal{D}_{X}$, we get

Combining the above three inequalities, we get

Therefore, as $(a+b)^{2}\leqslant 2a^{2}+2b^{2}$ and $2(1+\sqrt{C(k/2)})^{2}\leqslant 8C(k/2)$,

Substituting the above into Equation 3.1, we get

Rearranging the inequality and observing that $1/(1-2\eta^{1-2/k}C(k/2))\leqslant 1+O(C(k/2))\eta^{1-2/k}$ gives us

The argument for the above lemma also extends straightforwardly to polynomial regression (see Appendix A):

Sum of Squares proofs and Sum of Squares Optimization

In this section, we define pseudo-distributions and sum-of-squares proofs. See the lecture notes [BS16] for more details and the appendix in [MSS16] for proofs of the propositions appearing here.

This fact, together with the equivalence of weak separation and optimization [GLS81] allows us to efficiently optimize over pseudo-distributions (approximately)—this algorithm is referred to as the sum-of-squares algorithm.

We remark that if $D$ is an actual (discrete) probability distribution, then we have D\mathrel{\hbox{\raisebox{3.44444pt}{\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{8.00003pt}{0.47787pt}\hskip-8.00003pt\rule[0.75348pt]{8.00003pt}{0.47787pt}\hskip-8.00003pt\raisebox{-2.95354pt}{\makebox[8.00003pt]{\hbox{$\scriptstyle{}$}}}\hskip-8.00003pt\raisebox{2.95354pt}{\makebox[8.00003pt]{\hbox{$\scriptstyle{}$}}}}}}\mathcal{A} if and only if $D$ is supported on solutions to the constraints $\mathcal{A}$.

We say that a system $\mathcal{A}$ of polynomial constraints is explicitly bounded if it contains a constraint of the form $\{\|x\|^{2}\leqslant M\}$. The following fact is a consequence of Fact 4.1 and [GLS81],

A property of pseudo-distributions that we will use frequently is the following:

In particular, for all even integers $k\geqslant 2$, and polynomial $f$ with $deg(f)\cdot k\leqslant r$,

2 Sum-of-squares proofs

Let $f_{1},f_{2},\ldots,f_{r}$ and $g$ be multivariate polynomials in $x$. A sum-of-squares proof that the constraints $\{f_{1}\geqslant 0,\ldots,f_{m}\geqslant 0\}$ imply the constraint $\{g\geqslant 0\}$ consists of (sum-of-squares) polynomials $(p_{S})_{S\subseteq[m]}$ such that

Low-degree sum-of-squares proofs are sound and complete if we take low-level pseudo-distributions as models.

Concretely, sum-of-squares proofs allow us to deduce properties of pseudo-distributions that satisfy some constraints.

If the pseudo-distribution $D$ satisfies $\mathcal{A}$ only approximately, soundness continues to hold if we require an upper bound on the bit-complexity of the sum-of-squares \mathcal{A}\mathrel{\hbox{\raisebox{3.44444pt}{\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{10.63307pt}{0.47787pt}\hskip-10.63307pt\raisebox{-7.75671pt}{\makebox[10.63307pt]{\hbox{$\scriptstyle{r^{\prime}}$}}}\hskip-10.63307pt\raisebox{1.96112pt}{\makebox[10.63307pt]{\hbox{$\scriptstyle{}$}}}}}}B (number of bits required to write down the proof).

The following fact shows that every property of low-level pseudo-distributions can be derived by low-degree sum-of-squares proofs.

Suppose $d\geqslant r^{\prime}\geqslant r$ and $\mathcal{A}$ is a collection of polynomial constraints with degree at most $r$, and $\mathcal{A}\vdash\{\sum_{i=1}^{n}x_{i}^{2}\leqslant B\}$ for some finite $B$.

Let $\{g\geqslant 0\}$ be a polynomial constraint. If every degree-$d$ pseudo-distribution that satisfies D\mathrel{\hbox{\raisebox{3.44444pt}{\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{7.92819pt}{0.47787pt}\hskip-7.92819pt\rule[0.75348pt]{7.92819pt}{0.47787pt}\hskip-7.92819pt\raisebox{-5.96742pt}{\makebox[7.92819pt]{\hbox{$\scriptstyle{r}$}}}\hskip-7.92819pt\raisebox{2.95354pt}{\makebox[7.92819pt]{\hbox{$\scriptstyle{}$}}}}}}\mathcal{A} also satisfies D\mathrel{\hbox{\raisebox{3.44444pt}{\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{10.63307pt}{0.47787pt}\hskip-10.63307pt\rule[0.75348pt]{10.63307pt}{0.47787pt}\hskip-10.63307pt\raisebox{-8.74913pt}{\makebox[10.63307pt]{\hbox{$\scriptstyle{r^{\prime}}$}}}\hskip-10.63307pt\raisebox{2.95354pt}{\makebox[10.63307pt]{\hbox{$\scriptstyle{}$}}}}}}\{g\geqslant 0\}, then for every $\varepsilon>0$, there is a sum-of-squares proof \mathcal{A}\mathrel{\hbox{\raisebox{3.44444pt}{\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.16281pt}{0.47787pt}\hskip-8.16281pt\raisebox{-6.82222pt}{\makebox[8.16281pt]{\hbox{$\scriptstyle{d}$}}}\hskip-8.16281pt\raisebox{1.96112pt}{\makebox[8.16281pt]{\hbox{$\scriptstyle{}$}}}}}}\{g\geqslant-\varepsilon\}.

We will use the following standard sum-of-squares inequalities:

Algorithm

In this section, we present and analyze our robust regression algorithms. We begin by setting some notation that we will use throughout this section:

We will write $X=((x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{n},y_{n}))$ to denote the uncorrupted input sample of size $n$ drawn according to $\mathcal{D}$. For some bound $B$ on the bit-complexity of linear functions, we will write $\opt(\mathcal{D})$ for the optimum least squares error of any linear function of bit complexity $B$ on $\mathcal{D}$. Recall that the bit complexity of a linear function is the number of bits required to write down all of its coefficients.

We will write $\widehat{\mathcal{D}}$ for the uniform distribution on the sample $X$. $\widehat{D}=\widehat{\mathcal{D}}_{x}$ will denote the marginal distribution on $x$. Note that our algorithm does not get direct access to $\mathcal{D}$ or $\widehat{\mathcal{D}}$. We will write $\opt(\widehat{\mathcal{D}})$ for the optimum least squares error of any linear function of bit complexity $B$ on $\widehat{\mathcal{D}}$.

We will write $U=((u_{1},v_{1}),(u_{2},v_{2}),\ldots,(u_{n},v_{n}))$ to denote an $\eta$-corruption of $X$, i.e., $U$ is obtained by changing $\eta$ fraction of the example-label pairs. Our algorithm gets access to $U$.

In this section, we present our Robust Least Squares Regression algorithm. The main goal of this section is to establish the following result.

By an entirely analogous argument, we also get a similar guarantee for outlier-robust polynomial regression. We defer the details to Section A.

We need the boundedness assumption on the labels $y$ (that they lie in $[-M,M]$) and the bounded bit-complexity assumption on the linear functions ($B$) mainly to obtain generalization bounds for linear regression as are often used even for regression without corruptions. Further note that specializing the above to the case $k=4$ gives Theorem 1.3.

Observe that this system is feasible: use $w_{i}=1$ if $(x_{i},y_{i})=(u_{i},v_{i})$ and $0$ otherwise (i.e., $w_{i}=1$ if and only if the $i$’th example was corrupted) and taking $(x_{i}^{\prime},y_{i}^{\prime})=(x_{i},y_{i})$ for all $i\in[n]$.

We are now ready to describe our algorithm for robust L2 regression.

2 Analysis of the Algorithm

Under the assumptions of Theorem 5.1 (and following the above notations), with probability at least $1-\varepsilon$,

Under the assumptions of Theorem 5.1, with probability at least $1-\varepsilon$, the following hold:

$\widehat{\opt}_{SOS}\leqslant\opt(\mathcal{D})+\varepsilon$.

We defer the proofs of the above lemmas and proceed to finish analyzing our algorithm. With Lemma 5.3, 5.4 in hand, we are now ready to prove our main theorem. We just need the following lemma to get around bounding $\widehat{\opt}_{k}$.

Therefore, by Lemmas 5.3, 5.4, and the above observation, we get that with probability at least $1-O(\varepsilon)$,

We now prove Lemma 5.3. While the proof can appear technical, it’s essentially a line-by-line translation of the robust certifiability Lemma 3.2.

We next formalize the above approach starting with a SOS proof of Lemma 3.2. We defer the proof of the lemma to Section 5.2.2.

Moreover, the bit complexity of the proof is polynomial in $n$ and $d^{k}$.

We also need the following lemma (that follows from appropriate matrix concentration results) from [KS17c] stating that the uniform distribution on a sufficiently large set of i.i.d samples from a hypercontractive distribution also satisfy hypercontractivity. This allows us to argue that the uncorrupted empirical distribution $\widehat{\mathcal{D}}$ is also hypercontractive when $\mathcal{D}$ is.

Taking $2/k$th powers of both sides of the above equation and recalling the definition of $\widehat{\opt}_{SOS},\widehat{\opt}_{k}$, we get

2.2 Proof of Lemma 5.6

Here we prove Lemma 5.6. The proof is similar in spirit to that of Lemma 3.2 but we need to adapt the various steps to a form suitable for SOS proof system.

Let $w^{\prime}\in\zo^{n}$ be given by $w^{\prime}_{i}=w_{i}$ iff $i$th sample is uncorrupted in $U$ and $0$ otherwise. Then, observe that $\sum_{i}w_{i}^{\prime}=s$ for $s\geqslant(1-2\eta)n.$

Combining the above and using the sum-of-squares vesion of the Hölder’s inequality, we have:

Next, using the sum-of-squares inequality $(a+b)^{k}\leqslant 2^{k}a^{k}+2^{k}b^{k}$, we have:

By certifiable hypercontractivity of $\mathcal{D}_{x}=D$, we have:

Again, by using the sum-of-squares inequality $(a+b)^{k}\leqslant 2^{k}a^{k}+2^{k}b^{k}$, we have:

Finally, using the sum-of-squares version of Hölder’s inequality again, we have:

2.3 Bounding the Generalization Error

In this section we prove Lemma 5.4. The lemma follows from standard concentration inequalities combined with standard generalization bounds for linear regression.

3 Robust L1 Regression

In this section, we present our robust L1 regression algorithm. Our main goal is the following theorem.

The lower bound example in Lemma 6.1 also shows that the above bound is tight in the dependence on $\eta$ and $\kappa$.

As in the previous section, our algorithm will find pseudo-distributions satisfying a set of polynomial inequalities that encode the hypotheses of the robust certifiability lemma and the “error” polynomial.

Let $\mathcal{A}_{U,\eta,Q}$ be the following system of polynomial equations:

This system of equations takes as parameters the input sample $U$ and a bound on the fraction of outliers $\eta$.

We can now describe our algorithm for robust L1 regression.

Under the assumptions of Theorem 5.9 (and following the above notations),

Under the assumptions of Theorem 5.9, with probability at least $1-\varepsilon$,

$\widehat{\opt}_{SOS}\leqslant\opt(\mathcal{D})+\varepsilon$.

$\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}\leqslant\E_{\mathcal{D}}y^{2}$.

The proofs of the above two lemmas are entirely analogous to the ones presented in the previous section. The main technical ingredient as before is a SoS version of the robust certifiability result. Since this is the only technical novelty in this subsection, we present the statement and proof of this result below and omit the other proofs.

For every $i\in[n]$, define $w^{\prime}_{i}=w_{i}$ iff $(x_{i},y_{i})$ is uncorrupted in $U$. Then, observe that $\sum_{i}w_{i}^{\prime}=s$ for $s\geqslant(1-2\varepsilon)n$ and that \mathrel{\hbox{\raisebox{3.44444pt}{\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{9.97334pt}{0.47787pt}\hskip-9.97334pt\raisebox{-4.975pt}{\makebox[9.97334pt]{\hbox{$\scriptstyle{w}$}}}\hskip-9.97334pt\raisebox{1.96112pt}{\makebox[9.97334pt]{\hbox{$\scriptstyle{2}$}}}}}}\Set{w_{i}^{2}-w_{i}=0}.

Further, it’s easy to verify by direct expansion that:

Using the sum-of-squares vesion of the Cauchy-Shwarz inequality, we have:

Using that for any PSD matrix $A$, we have the SoS inequality $\|x\|_{2}^{2}\|A\|_{min}\leqslant x^{\top}Ax\leqslant\|x\|_{2}^{2}\|A\|_{max}$ where $\|A\|_{max}$ and $\|A\|_{min}$ are the largest and smallest singular values of $A$, respectively, we have:

Combining the above inequalities with (5.11) yields the lemma.

Statistical Limits of Outlier-Robust Regression

Here we exhibit statistical lower bounds for what can be achieved for outlier-robust regression. In particular, these simple examples illustrate strong separations between regression and regression in the presence of contamination and also demonstrate the necessity of our disributional assumptions.

It follows that for some universal constant $c>0$, and $\kappa=1/\sqrt{\eta}$, $\min(\mathsf{err}_{\mathcal{D}}(w),\mathsf{err}_{\mathcal{D}^{\prime}}(w))\geqslant c.$

Finally, let $\mathcal{D}^{\prime\prime}$ be the distribution of the random variable sampled as follows: 1) Sample $\alpha$ uniformly at random from $$; 2) With probability$1-\delta$output$((\alpha,\alpha),\alpha)$; 3) With probability$\delta/2$output$((\kappa\cdot\alpha,\alpha),\alpha)$; 4) With probability$\delta/2$output$((\alpha,\kappa\cdot\alpha),\alpha)$.

Acknowledgment

We thank Ainesh Bakshi and Adarsh Prasad for pointing out an error in the proof of one of our information-theoretic lower-bounds in Section 6 in a previous version of the paper.

References

Appendix A Outlier-Robust Polynomial Regression

Our arguments also extend straightforwardly to get similar guarantees for polynomial regression. We elaborate on these next.

The following extends the definition of hypercontractivity to polynomials.

Many natural distributions satisfy certifiably hypercontractivity [KOTZ14] for polynomials such as gaussian distributions and the product distributions on the hypercube $\zo^{n}$ with all coordinate marginals in $(0,1)$. Our results will apply to all such distributions.

Next, we state an extension of our robust certification lemma for polynomial regression. The proof is essentially the same as that of Lemma 3.2.