Sever: A Robust Meta-Algorithm for Stochastic Optimization

arXiv:1803.02815v1 [cs.LG] 7 Mar 2018

Ilias Diakonikolas ∗
CS, USC
diakonik@usc.edu
Jerry Li §
EECS & CSAIL, MIT
jerryzli@mit.edu

Gautam Kamath †
EECS & CSAIL, MIT
g@csail.mit.edu
Jacob Steinhardt ¶
CS, Stanford University
jsteinha@stanford.edu

Daniel M. Kane ‡
CSE & Math, UCSD
dakane@cs.ucsd.edu
Alistair Stewart k
CS, USC
stewart.al@gmail.com

March 8, 2018

Abstract
In high dimensions, most machine learning methods are brittle to even a small fraction of structured
outliers. To address this, we introduce a new meta-algorithm that can take in a base learner such as
least squares or stochastic gradient descent, and harden the learner to be resistant to outliers. Our
method, Sever, possesses strong theoretical guarantees yet is also highly scalable—beyond running the
base learner itself, it only requires computing the top singular vector of a certain n × d matrix. We apply
Sever on a drug design dataset and a spam classification dataset, and find that in both cases it has
substantially greater robustness than several baselines. On the spam dataset, with 1% corruptions, we
achieved 7.4% test error, compared to 13.4% − 20.5% for the baselines, and 3% error on the uncorrupted
dataset. Similarly, on the drug design dataset, with 10% corruptions, we achieved 1.42 mean-squared
error test error, compared to 1.51-2.33 for the baselines, and 1.23 error on the uncorrupted dataset.

1

Introduction

Learning in the presence of outliers is a ubiquitous challenge in machine learning; nevertheless, most machine
learning methods are very sensitive to outliers in high dimensions. The focus of this work is on designing
algorithms that are outlier robust while remaining competitive in terms of accuracy and running time.
We highlight two motivating applications. The first is biological data (such as gene expression data),
where mislabeling or measurement errors can create systematic outliers [RPW+ 02, LAT+ 08] that require
painstaking manual effort to remove [PLJD10]. Detecting outliers in such settings is often important either
because the outlier observations are of interest themselves or because they might contaminate the downstream
statistical analysis. The second motivation is machine learning security, where outliers can be introduced
through data poisoning attacks [BNJT10] in which an adversary inserts fake data into the training set (e.g.,
by creating a fake user account). Recent work has shown that for high-dimensional datasets, even a small
fraction of outliers can substantially degrade the learned model [BNL12, NPXNR14, KL17, SKL17].
∗ Supported

by NSF Award CCF-1652862 (CAREER) and a Sloan Research Fellowship.
by NSF Award CCF-1617730, CCF-1650733, CCF-1741137, and ONR N00014-12-1-0999.
‡ Supported by NSF Award CCF-1553288 (CAREER) and a Sloan Research Fellowship.
§ Supported by NSF Award CCF-1453261 (CAREER), CCF-1565235, a Google Faculty Research Award, and an NSF
Graduate Research Fellowship.
¶ Supported by a Fannie & John Hertz Foundation Fellowship, a NSF Graduate Research Fellowship, and a Future of Life
Institute grant.
k Supported by a USC startup grant.
Authors are in alphabetical order.
† Supported

1

remove outliers
and re-run

Data
(X, Y )

Fit Model

extract
gradients

SVD

compute
scores

θ

Figure 1: Illustration of the Sever pipeline. We first use any machine learning algorithm to fit a model to the
data. Then, we extract gradients for each data point at the learned parameters, and take the singular value
decomposition of the gradients. We use this to compute an outlier score for each data point. If we detect
outliers, we remove them and re-run the learning algorithm; otherwise, we output the learned parameters.
Crucially, in both the biological and security settings above, the outliers are not “random” but are instead
highly correlated, and could have a complex internal structure that is difficult to model. This leads us to
the following conceptual question underlying the present work: Can we design training algorithms that are
robust to the presence of an ε-fraction of arbitrary (and potentially adversarial) outliers?
Estimation in the presence of outliers is a prototypical goal in robust statistics and has been systematically
studied since the pioneering work of Tukey [Tuk60]. Nevertheless, until recently, all known efficient estimators
suffered from large errors in the presence of a small fraction of outliers, even for the most basic highdimensional tasks that are common in machine learning. Recent work in theoretical computer science has
resulted in efficient robust estimators for classical problems such as linear classification [KLS09, ABL14],
mean and covariance estimation [DKK+ 16, LRV16], clustering [CSV17], and regression [BJK15, BJKK17,
BDLS17]. (See Section 1.1 for a detailed discussion of prior and related work.)
Despite this recent algorithmic progress, the promise of efficient high-dimensional robust estimation is yet
to be realized; indeed, the aforementioned results generally suffer from one of two shortcomings—either they
use sophisticated convex optimization algorithms that do not scale to large datasets, or they are tailored to
specific problems of interest or specific distributional assumptions on the data, and hence do not have good
accuracy on real data.
In this work, we address these shortcomings. We propose an algorithm, Sever, that is:
• Robust: it can handle arbitrary outliers with only a small increase in error, even in high dimensions.
• General: it can be applied to most common learning problems including regression and classification,
and handles non-convex models such as neural networks.
• Practical: the algorithm can be implemented with standard machine learning libraries.
At a high level, our algorithm (depicted in Figure 1 and described in detail in Section 2.2) is a simple “plugin” outlier detector—first, run whatever learning procedure would be run normally (e.g., least squares in the
case of linear regression). Then, consider the matrix of gradients at the optimal parameters, and compute
the top singular vector of this matrix. Finally, remove any points whose projection onto this singular vector
is too large (and re-train if necessary).
Despite its simplicity, our algorithm possesses strong theoretical guarantees: As long as the data is not
too heavy-tailed, Sever is provably robust to outliers—see Section 2 for detailed statements of the theory.
At the same time, we show that our algorithm works very well in practice and outperforms a number of
natural baseline outlier detectors. In line with our original motivating biological and security applications, we
implement our method on two tasks—a linear regression task for predicting protein activity levels [OSB+ 18],
and a spam classification task based on e-mails from the Enron corporation [MAP06]. Even with a small
fraction of outliers, baseline methods perform extremely poorly on these datasets; for instance, on the Enron
spam dataset with a 1% fraction of outliers, baseline errors range from 13.4% to 20.5%, while Sever incurs
only 7.3% error (in comparison, the error is 3% in the absence of outliers). Similarly, on the drug design

2

dataset, with 10% corruptions, we achieved 1.42 mean-squared error test error, compared to 1.51-2.33 for
the baselines, and 1.23 error on the uncorrupted dataset.

1.1

Comparison to Prior Work

In the context of supervised learning, [KLS09] gave the first efficient algorithms for robustly learning origincentered linear separators with respect to the 0-1 loss under the assumption that the distribution of the
good data is isotropic and log-concave. Subsequently, [ABL14] obtained an improved robust algorithm that
achieves nearly tight error bounds for this learning problem.
In the context of unsupervised learning, two concurrent works [DKK+ 16, LRV16] gave the first provably
robust and efficiently computable estimators for several basic high-dimensional unsupervised tasks, including
robust mean and covariance estimation. Since the dissemination of [DKK+ 16, LRV16], there has been
a flurry of research activity on algorithmic robust estimation in a variety of high-dimensional settings,
including learning graphical models [DKS16], understanding computation-robustness tradeoffs [DKS17c,
DKK+ 18], establishing connections to PAC learning [DKS17a], tolerating more noise by outputting a list of
hypotheses [CSV17, MV17, DKS17b], robust estimation of discrete structures [Ste17, QV17, SCV18], and
robust estimation via sum-of-squares [KS17b, HL17, KS17a].
Despite this recent theoretical progress, prior works focus on designing specialized algorithms for specific
settings (such as mean estimation or linear classification) rather than on designing general algorithms. The
only exception is [CSV17], which provides a robust meta-algorithm for stochastic convex optimization in a
similar setting to ours. However, that algorithm (i) requires solving a large semidefinite program and (ii)
incurs a significant loss in performance relative to standard training even in the absence of outliers. On the
other hand, [DKK+ 17] provide a practical implementation of the robust mean and covariance estimation
algorithms of [DKK+ 16], but it is not clear how to extend their approach to a broader class of learning tasks.
In the concrete settings of regression and classification considered in our experiments, there has been a
substantial number of related works. A number of papers [NTN11, NT13, BJK15, BJKK17] have proposed
efficient algorithms for a type of robust linear regression. However, these works consider a restrictive corruption model that only allows adversarial corruptions to the responses (but not the covariates). On the other
hand, [BDLS17] studies (sparse) linear regression and, more broadly, generalized linear models (GLMs) under a robustness model very similar to the one considered here. The main issues with this algorithm are that
(i) it requires running the ellipsoid method (hence does not scale) and (ii) it crucially assumes Gaussianity
of the covariates, which is unlikely to hold in practice.
In a related direction, [SKL17] study outlier detectors for linear classification, and provide a method for
either numerically certifying that a given outlier detector imparts robustness to the learning algorithm, or
for providing an attack if the learner is not robust. They show that the outlier detector they consider is very
brittle in high dimensions, motivating the need for the robust algorithms presented in the current work.
Concurrent Works. Contemporaneous work and independent work [PSBR18] has obtained a robust
algorithm for stochastic convex optimization by combining gradient descent with robust mean estimation. For
the case of linear regression, [DKS18] provide efficient robust algorithms with near-optimal error guarantees
under various distributional assumptions and establish matching computational-robustness tradeoffs.

2

Framework and Algorithm

In this section, we describe our formal framework as well as the Sever algorithm.

2.1

Formal Setting

We will consider stochastic optimization tasks, where there is some true distribution p∗ over functions
def
f : H → R, and our goal is to find a parameter vector w∗ ∈ H minimizing f (w) = Ef ∼p∗ [f (w)]. Here
we assume H ⊆ Rd is a space of possible parameters. As an example, we consider linear regression, where
3

f (w) = 21 (w · x − y)2 for (x, y) drawn from the data distribution; or support vector machines, where f (w) =
max{0, 1 − y(w · x)}.
def

To help us learn the parameter vector w∗ , we have access to a training set of n functions f1:n =
{f1 , . . . , fn }. (For linear regression, we would have fi (w) = 21 (w · xi − yi )2 , where (xi , yi ) is an observed data
point.) However, unlike the classical (uncorrupted) setting where we assume that f1 , . . . , fn ∼ p∗ , we allow
for an ε-fraction of the points to be arbitrary outliers:
Definition 2.1 (ε-contamination model). Given ε > 0 and a distribution p∗ over functions f : H → R, data
is generated as follows: first, n clean samples f1 , . . . , fn are drawn from p∗ . Then, an adversary is allowed to
inspect the samples and replace any εn of them with arbitrary samples. The resulting set of points is then
given to the algorithm. We will call such a set of samples ε-corrupted (with respect to p∗ ).
In the ε-contamination model, the adversary is allowed to both add and remove points. Our theoretical
results hold in this strong robustness model. Our experimental evaluation uses corrupted instances in which
the adversary is only allowed to add corrupted points. Additive corruptions essentially correspond to Huber’s
contamination model [Hub64] in robust statistics.
Finally, we will often assume access to a black-box learner, which we denote by L, which takes in functions
f1 P
, . . . , fn and outputs a parameter vector w ∈ H. We want to stipulate that L approximately minimizes
n
1
i=1 fi (w). For this purpose, we introduce the following definition:
n
Definition 2.2 (γ-approximate critical point). Given a function f : H → R, a γ-approximate critical point
of f , is a point w ∈ H so that for all unit vectors v where w + δv ∈ H for arbitrarily small positive δ, we
have that v · ∇f (w) ≥ −γ.
Essentially, the above definition means that the value of f cannot be decreased much by changing the
input w locally, while staying within the domain. The condition enforces that moving in any direction v
either causes us to leave H or causes f to decrease at a rate at most γ. It should be noted that when
H = Rd , our above notion of approximate critical point reduces to the standard notion of approximate
stationary point (i.e., a point where the magnitude of the gradient is small).
We are now ready to define the notion of a γ-approximate learner:
Definition 2.3 (γ-approximate learner). A learning algorithm L is called γ-approximate if, for any functions
f1 , . . . , fn : H → R each bounded below
Pn on a closed domain H, the output w = L(f1:n ) of L is a γapproximate critical point of f (x) := n1 i=1 fi (x).
In other words, L always finds an approximate critical point of the empirical learning objective. We
note that most common learning algorithms (such as stochastic gradient descent) satisfy the γ-approximate
learner property.

2.2

Algorithm and Theory

As outlined in Figure 1, our algorithm works by post-processing the gradients of a black-box learning
algorithm. The basic intuition is as follows: we want to ensure that the outliers do not have a large effect
on the learned parameters. Intuitively, for the outliers to have such an effect, their corresponding gradients
should be (i) large in magnitude and (ii) systematically pointing in a specific direction. We can detect this
via singular value decomposition–if both (i) and (ii) hold then the outliers should be responsible for a large
singular value in the matrix of gradients, which allows us to detect and remove them.
This is shown more formally via the pseudocode in Algorithm 1.
Theoretical Guarantees. Our first theoretical result says that as long as the data is not too heavy-tailed,
Sever will find an approximate critical point of the true function f , even in the presence of outliers.
Theorem 2.1. Suppose that functions f1 , . . . , fn , f : H → R are bounded below on a closed domain H, and
suppose that they satisfy the following deterministic regularity conditions: There exists a set Igood ⊆ [n] with
|Igood | ≥ (1 − ε)n and σ > 0 such that
4

Algorithm 1 Sever(f1:n , L, σ)
1: Input: Sample functions f1 , . . . , fn : H → R, bounded below on a closed domain H, γ-approximate
learner L, and parameter σ ∈ R+ .
2: Initialize S ← {1, . . . , n}.
3: repeat
4:
w ← L({fi }i∈S ). . Run approximate learner on points in S.
b = 1 P
5:
Let ∇
i∈S ∇fi (w).
|S|
b i∈S be the |S| × d matrix of centered gradients.
6:
Let G = [∇fi (w) − ∇]
7:
Let v be the top right singular vector of G.

2
b ·v .
8:
Compute the vector τ of outlier scores defined via τi = (∇fi (w) − ∇)
S0 ← S
S ← Filter(S 0 , τ, σ) . Remove some i’s with the largest scores τi from S; see Algorithm 2.
until S = S 0 .
12: Return w.

9:
10:
11:

Algorithm 2 Filter(S, τ, σ)
1: Input: Set S ⊆ [n], vector τ of outlier scores, and parameter σ ∈ R+ .
P
2: If
i τi ≤ c · σ, for some constant c > 1, return S . We only filter out points if the variance is larger
than an appropriately chosen threshold.
3: Draw T from the uniform distribution on [0, maxi τi ].
4: Return {i ∈ S : τi < T }.
(i) CovIgood [∇fi (w)]  σ 2 I, w ∈ H,
P
√
def
(ii) k∇fˆ(w) − ∇f (w)k2 ≤ σ ε, w ∈ H, where fˆ = (1/|Igood |) i∈Igood fi .
Then our algorithm
Sever applied to f1 , . . . , fn , σ returns a point w ∈ H that, with probability at least 9/10,
√
is a (γ + O(σ ε))-approximate critical point of f .
The key take-away from Theorem 2.1 is that the error guarantee has no dependence on the underlying
dimension d. In contrast, most natural algorithms incur an error that grows with d, and hence have poor
robustness in high dimensions.
We show that under some niceness assumptions on p∗ , the deterministic regularity conditions are satisfied
with high probability with polynomially many samples:
Proposition 2.2 (Informal). Let H ⊂ Rd be a closed bounded set with diameter at most r. Let p∗ be a
distribution over functions f : H → R and f = Ef ∼p∗ [f ]. Suppose that for each w ∈ H and unit vector
v we have Ef ∼p∗ [(v · (∇f (w) − f (w)))2 ] ≤ σ 2 . Under appropriate Lipschitz and smoothness assumptions,
for n = Ω(d log(r/(σε))/(σ 2 ε)), an ε-corrupted set of functions drawn i.i.d. from p∗ , f1 , . . . , fn with high
probability satisfy conditions (i) and (ii).
The reader is referred to Proposition B.5 in the appendix for a detailed formal statement.
While Theorem 2.1 is very general and holds even for non-convex loss functions, we might in general
hope for more than an approximate critical point. In particular, for convex problems, we can guarantee that
we find an approximate global minimum. This follows as a corollary of Theorem 2.1:
Corollary 2.3. Suppose that f1 , . . . , fn : H → R satisfy the regularity conditions (i) and (ii), and that H is
convex with `2 -radius r. Then, with probability at least 9/10, the output of Sever satisfies the following:
√
(i) If f is convex, the algorithm finds a w ∈ H such that f (w) − f (w∗ ) = O((σ ε + γ)r).

(ii) If f is ξ-strongly convex, the algorithm finds a w ∈ H such that f (w) − f (w∗ ) = O (εσ 2 + γ 2 )/ξ .
5

Practical Considerations. For our theory to hold, we need to use the randomized filtering algorithm
shown in Algorithm 2 (which is essentially the robust mean estimation algorithm of [DKK+ 17]), and filter
until the stopping condition in line 11 of Algorithm 1 is satisfied. However, in practice we found that
the following simpler algorithm worked well: in each iteration simply remove the top p fraction of outliers
according to the scores τi , and instead of using a specific stopping condition, simply repeat the filter for r
iterations in total. This is the version of Sever that we use in our experiments in Section 3.
Concrete Applications We also provide several concrete applications of our general theorem, particularly
involved with optimization problems related to learning generalized linear models. In this setting, we are
given a set of pairs (X, Y ) where X ∈ Rd and Y is in some (usually discrete) set. One then tries to find
some vector w that minimizes some appropriate loss function L(w, (X, Y )) = σY (w · X). For example, the
standard hinge-loss has Y ∈ {±1} and L = max(0, 1 − Y (w · X)). Similarly, the logistic loss function is
− log(1 + exp(−Y (w · X))). In both cases, we show that an approximate minimizer to the empirical loss
function can be found with a near-optimal number of samples, even under ε-corruptions (for exact theorem
statements see Theorems E.8 and E.11).
Theorem 2.4 (Informal Statement). Let DX,Y be a distribution over Rd ×{±1} so that E[XX T ]  I and
so that not too many X values lie near any hyperplane. Let (X1 , Y1 ), . . . , (Xn , Yn ) be n = Õ(d/ε) ε-corrupted
samples from DX,Y . Let L be either the hinge loss or logistic loss function. Then there exists a polynomial
time algorithm that with probability 9/10 returns a vector w that minimizes E(X,Y )∼DX,Y (L(w, (X, Y ))) up
to an additive Õ(ε1/4 ) error.
Another application allows us to use the least-squares loss function (L(w, (X, Y )) = (Y − w · X)2 )
to perform linear regression under somewhat more restrictive assumptions (see Theorem E.2 for the full
statement):
Theorem 2.5 (Informal Statement). Let DX,Y be a distribution over Rd × R where Y = w∗ · X + e for some
independent e with mean 0 and variance 1. Assume furthermore, that E[XX T ]  I and that X has bounded
5 2
fourth moments. Then there exists an algorithm that given O(d
√ /ε ) ε-corrupted samples from D, computes
d
∗
a value w ∈ R so that with high probability kw − w k2 = O( ε).

2.3

Overview of Sever and its Analysis

For simplicity of the exposition, we restrict ourselves to the important special case where the functions
involved are convex. We have a probability distribution p∗ over convex functions on some convex domain
H ⊆ Rd and we wish to minimize the function f = Ef ∼p∗ [f ]. This problem is well-understood in the absence
of corruptions: Under mild assumptions, if we take sufficiently many samples from p∗ , their average fˆ approximates f pointwise with high probability. Hence, we can use standard methods from convex optimization
to find an approximate minimizer for fˆ, which will in turn serve as an approximate minimizer for f .
In the robust setting, stochastic optimization becomes quite challenging: Even for the most basic special
cases of this problem (e.g., mean estimation, linear regression) a single adversarially corrupted sample can
substantially change the location of the minimum for fˆ. Moreover, naive outlier removal methods can only
tolerate a negligible fraction ε of corruptions (corresponding to ε = O(d−1/2 )).
A first idea to get around this obstacle is the following: We consider the standard (projected) gradient
descent method used to find the minimum of fˆ. This algorithm would proceed by repeatedly computing the
gradient of fˆ at appropriate points and using it to update the current location. The issue is that adversarial
corruptions can completely compromise this algorithm’s behavior, since they can substantially change the
gradient of fˆ at the chosen points. The key observation is that approximating the gradient of f at a given
point, given access to an ε-corrupted set of samples, can be viewed as a robust mean estimation problem.
We can thus use the robust mean estimation algorithm of [DKK+ 17], which succeeds under fairly mild
assumptions about the good samples. Assuming that the covariance matrix of ∇f (w), f ∼ p∗ , is bounded,
we can thus “simulate” gradient descent and compute an approximate minimum for f .
6

In summary, the first algorithmic idea is to use a robust mean estimation routine as a black-box in order
to robustly estimate the gradient at each iteration of (projected) gradient descent. This yields a simple
robust method for stochastic optimization with polynomial sample complexity and running time in a very
general setting (See Appendix D for details.)
We are now ready to describe Sever (Algorithm 1) and the main insight behind it. Roughly speaking,
Sever only calls our robust mean estimation routine (which is essentially the filtering method of [DKK+ 17]
for outlier removal) each time the algorithm reaches an approximate critical point of fˆ. There are two main
motivations for this approach: First, we empirically observed that if we iteratively filter samples, keeping
the subset with the samples removed, then few iterations of the filter remove points. Second, an iteration
of the filter subroutine (Algorithm 2) is more expensive than an iteration of gradient descent. Therefore,
it is advantageous to run many steps of gradient descent on the current set of corrupted samples between
consecutive filtering steps. This idea is further improved by using stochastic gradient descent, rather than
computing the average at each step.
An important feature of our analysis is that Sever does not use a robust mean estimation routine as
a black box. In contrast, we take advantage of the performance guarantees of our filtering algorithm. The
main idea for the analysis is as follows: Suppose that we have reached an approximate critical point w of fˆ
and at this step we apply our filtering algorithm. By the performance guarantees of the latter algorithm we
are in one of two cases: either the filtering algorithm removes a set of corrupted functions or it certifies that
the gradient of fˆ is “close” to the gradient of f at w. In the first case, we make progress as we produce a
“cleaner” set of functions. In the second case, our certification implies that the point w is also an approximate
critical point of f and we are done.

3

Experiments

In this section we apply Sever to regression and classification problems. As our base learners, we used
ridge regression and an SVM, respectively. We implemented the latter as a quadratic program, using
Gurobi [Gur16] as a backend solver and YALMIP [Löf04] as the modeling language.
In both cases, we ran the base learner and then extracted gradients for each data point at the learned
parameters. We then centered the gradients and ran MATLAB’s svds method to compute the top singular
vector v, and removed the top p fraction of points i with the largest outlier score τi , computed as the
squared magnitude of the projection onto v (see Algorithm 1). We repeated this for r iterations in total.
For classification, we centered the gradients separately (and removed points separately) for each class, which
improved performance.
We compared our method to five baseline methods. These all have the same high-level form as Sever
(run the base learner then filter top p fraction of points with the largest score), but use a different definition
of the score τi for deciding which points to filter:
• noDefense: no points are removed.
• l2: remove points where the covariate x has large `2 distance from the mean.
• loss: remove points with large loss (measured at the parameters output by the base learner).
• gradient: remove points with large gradient (in `2 -norm).
• gradientCentered: remove points whose gradients are far from the mean gradient in `2 -norm.
Note that gradientCentered is similar to our method, except that it removes large gradients in terms of
`2 -norm, rather than in terms of projection onto the top singular vector. As before, for classification we
compute these metrics separately for each class.
Both ridge regression and SVM have a single hyperparameter (the regularization coefficient). We optimized this based on the uncorrupted data and then kept it fixed throughout our experiments. In addition,
since the data do not already have outliers, we added varying amounts of outliers (ranging from 0.5% to 10%
of the clean data); this process is described in more detail below.
7

3.1

Ridge Regression

For ridge regression, we tested our method on a synthetic Gaussian dataset as well as a drug discovery
dataset. The synthetic dataset consists of observations (xi , yi ) where xi ∈ R500 has independent standard
Gaussian entries, and yi = hxi , w∗ i + 0.1zi , where zi is also Gaussian. We generated 5000 training points and
100 test points. The drug discovery dataset was obtained from the ChEMBL database and was originally
curated by [OSB+ 18]; it consists of 4084 data points in 410 dimensions; we split this into a training set of
3084 points and a test set of 1000 points.
Centering We found that centering the data points decreased error noticeably on the drug discovery
dataset, while scaling each coordinate to have variance 1 decreased error by a small amount on the synthetic
data. To center in the presence of outliers, we used the robust mean estimation algorithm from [DKK+ 17].
Adding outliers. We devised a method of generating outliers that fools all of the baselines while still
inducing high test error. At a high level, the outliers cause ridge regression to output w = 0 (so the model
always predicts y = 0).
If (X, y) are the true data points and responses, this can be achieved by setting each outlier point
(Xbad , ybad ) as
Xbad =

1
y > X and ybad = −β ,
α · nbad

where nbad is the number of outliers we add, and α and β are hyperparameters.
If α = β, one can check that w = 0 is the unique minimizer for ridge regression on the perturbed dataset.
By tuning α and β, we can then obtain attacks that fool all the baselines while damaging the model (we
tune α and β separately to give an additional degree of freedom to the attack). To increase the error, we
also found it useful to perturb each individual Xbad by a small amount of Gaussian noise.
In our experiments we found that this method generated successful attacks as long as the fraction of
outliers was at least roughly 2% for synthetic data, and roughly 5% for the drug discovery data.

1.00

0.50

0.00
0.00 0.02 0.04 0.06 0.08 0.10

Regression: Drug discovery data
2.00

Regression: Drug discovery data,
attack targeted against Sever
2.00

1.80

1.80

1.60
1.40

1.60
1.40

1.20

1.20

1.00
0.00 0.02 0.04 0.06 0.08 0.10

1.00
0.00 0.02 0.04 0.06 0.08 0.10

Outlier Fraction epsilon

Outlier Fraction epsilon

uncorrupted

Test Error

Test Error

Test Error

Regression: Synthetic data

l2

loss

gradientCentered

Outlier Fraction epsilon

Sever

Figure 2: ε vs test error for baselines and Sever on synthetic data and the drug discovery dataset. The left
and middle figures show that Sever continues to maintain statistical accuracy against our attacks which are
able to defeat previous baselines. The right figure shows an attack with parameters chosen to increase the
test error Sever on the drug discovery dataset as much as possible. Despite this, Sever still has relatively
small test error.

8

Figure 3: A representative set of histograms of scores for baselines and Sever on synthetic data and a drug
discovery dataset. From left to right: scores for the l2 defense on the drug discovery dataset, scores for loss
on synthetic data, and scores for Sever on the drug discovery dataset, all with the addition of 10% outliers.
The scores for the true dataset are in blue, and the scores for the outliers are in red. For the baselines, the
scores for the outliers are inside the bulk of the distribution and thus hard to detect, whereas the scores for
the outliers assigned by Sever are clearly within the tail of the distribution and easily detectable.
Results. In Figure 2 we compare the test error of our defense against the baselines as we increase the
fraction ε of added outliers. To avoid cluttering the figure, we only show the performance of l2, loss,
gradientCentered, and Sever; the performance of the remaining baselines is qualitatively similar to the
baselines in Figure 2.
For both the baselines and our algorithms, we iterate the defense r = 4 times, each time removing the
p = ε/2 fraction of points with largest score. For consistency of results, for each defense and each value of ε
we ran the defense 3 times on fresh attack points and display the median of the 3 test errors.
When the attack parameters α and β are tuned to defeat the baselines (Figure 2 left and center), our
defense substantially outperforms the baselines as soon as we cross ε ≈ 1.5% for synthetic data, and ε ≈ 5.5%
for the drug discovery data. In fact, most of the baselines do worse than not removing any outliers at all
(this is because they end up mostly removing good data points, which causes the outliers to have a larger
effect). Even when α and β are instead tuned to defeat Sever, its resulting error remains small (Figure 2
right).
To understand why the baselines fail to detect the outliers, in Figure 3 we show a representative sample of
the histograms of scores of the uncorrupted points overlaid with the scores of the outliers, for both synthetic
data and the drug discovery dataset with ε = 0.1, after one run of the base learner. The scores of the outliers
lie well within the distribution of scores of the uncorrupted points. Thus, it would be impossible for the
baselines to remove them without also removing a large fraction of uncorrupted points.
Interestingly, for small ε all of the methods improve upon the uncorrupted test error for the drug discovery
data; this appears to be due to the presence of a small number of natural outliers in the data that all of the
methods successfully remove.

3.2

Support Vector Machines

We next describe our experimental results for SVMs; we tested our method on a synthetic Gaussian dataset
as well as a spam classification task. Similarly to before, the synthetic data consists of observations (xi , yi ),
where xi ∈ R500 has independent standard Gaussian entries, and yi = sign(hxi , w∗ i + 0.1zi ), where zi is
also Gaussian and w∗ is the true parameters (drawn at random from the unit sphere). The spam dataset
comes from the Enron corpus [MAP06], and consists of 4137 training points and 1035 test points in 5116
dimensions.
To generate attacks, we used the data poisoning algorithm presented in [SKL17]; the authors provided
us with an improved version of their algorithm that can circumvent the l2 and loss baselines and partially
circumvents the gradient baselines as well.

9

In contrast to ridge regression, we did not perform centering and rescaling for these datasets as it did
not seem to have a large effect on results.
n− +n+
· rε of highest-scoring
In all experiments for this section, each method removed the top p = min{n
+ ,n− }
points for each of r = 2 iterations, where n+ and n− are the number of positive and negative training points
respectively. This expression for p is chosen in order to account for class imbalance, which is extreme in the
case of the Enron dataset – if the attacker plants all the outliers in the smaller class, then a smaller value of
p would remove too few points, even with a perfect detection method.
SVM: Strongest attacks against Sever on synthetic data

SVM: Strongest attacks against loss on synthetic data

0.25
0.30

Test Error

Test Error

0.20

0.20

0.15

0.10

0.10
0.05

0.00
0.00

0.01

0.02

0.00
0.00

0.03

Outlier Fraction epsilon

0.01

0.02

0.03

Outlier Fraction epsilon

uncorrupted

loss

Sever

Figure 4: ε versus test error for loss baseline and Sever on synthetic data. The left figure demonstrates
that Sever is accurate when outliers manage to defeat loss. The right figure shows the result of attacks
which increased the test error the most against Sever. Even in this case, Sever performs much better than
the baselines.

Synthetic results. We considered fractions of outliers ranging from ε = 0.005 to ε = 0.03. By performing
a sweep across hyperparameters of the attack, we generated 56 distinct sets of attacks for each value of ε. In
Figure 4, we show results for the attack where the loss baselines does the worst, as well as for the attack where
our method does the worst. When attacks are most effective against loss, Sever substantially outperforms
it, nearly matching the test accuracy of 5.8% on the uncorrupted data, while loss performs worse than 30%
error at just a 1.5% fraction of injected outliers. Even when attacks are most effective against Sever, it still
outperforms loss, achieving a test error of at most 9.05%. We note that other baselines behaved qualitatively
similarly to loss, and the results are displayed in Section F.
Spam results. For results on Enron, we used the same values of ε, and considered 96 distinct hyperparameters for the attack. There was not a single attack that simultaneously defeated all of the baselines, so
in Figure 5 we show two attacks that do well against different sets of baselines, as well as the attack that
performs best against our method.
At ε = 0.01, the worst performance of our method against all attacks was 7.34%, in contrast to 13.43% −
20.48% for the baselines (note that the accuracy is 3% in the absence of outliers). However, at ε = 0.03,
while we still outperform the baselines, our error is relatively large—13.53%.
To investigate this further, we looked at all 48 attacks and found that while on 42 out of 48 attacks our
error never exceeded 7%, on 6 of the attacks (including the attack in Figure 5) the error was substantially
higher. Figure 6 shows what is happening. The leftmost figure displays the scores assigned by Sever
10

SVM: Strongest attacks against
gradientCentered on Enron

SVM: Strongest attacks
against loss on Enron

SVM: Strongest attacks
against Sever on Enron
0.20

0.15

0.10

0.05

0.00
0.00

Test Error

Test Error

Test Error

0.20

0.10

0.15
0.10
0.05

0.01

0.02

Outlier Fraction epsilon

0.03

0.00
0.00

0.01

0.02

0.03

0.00
0.00

Outlier Fraction epsilon

uncorrupted
gradientCentered

loss
Sever

0.01

0.02

0.03

Outlier Fraction epsilon

gradient

Figure 5: ε versus test error for baselines and Sever on the Enron spam corpus. The left and middle
figures are the attacks which perform best against two baselines, while the right figure performs best against
Sever. Though other baselines may perform well in certain cases, only Sever is consistently accurate. The
exception is for certain attacks at ε = 0.03, which, as shown in Figure 6, require three rounds of outlier
removal for any method to obtain reasonable test error – in these plots, our defenses perform only two
rounds.

Figure 6: An illustration of why multiple rounds of filtering are necessary. Histograms of scores assigned by
Sever in three subsequent iterations of outlier removal. Inliers are blue, and outliers are red (scaled up by a
factor of 10). In early iterations, a significant fraction of outliers may be “hidden” (i.e. have 0 loss) by being
correctly classified in one iteration. However, once previous outliers are removed, these points may become
incorrectly classified, thus significantly degrading the quality of our solution but simultaneously becoming
evident to Sever.
after the first iteration, where red bars indicate outliers. While some outliers are assigned extremely large
scores and thus detected, several outliers are correctly classified and thus have 0 gradient. However, once we
remove the first set of outliers, some outliers which were previously correctly classified now have large score,
as displayed in the middle figure. Another iteration of this process produces the rightmost figure, where
almost all the remaining outliers have large score and will thus be removed by Sever. This demonstrates
that some outliers may be hidden until other outliers are removed, necessitating multiple iterations.
Motivated by this, we re-ran our method against the 6 attacks using r = 3 iterations instead of 2 (and
decreasing p as per the expression above). After this change, all 6 of the attacks had error at most 7.4%.

11

4

Discussion

In this paper we have presented an algorithm, Sever, that has both strong theoretical robustness properties
in the presence of outliers, and performs well on real datasets. Sever is based on the idea that learning
can often be cast as the problem of finding an approximate stationary point of the loss, which can in turn
be cast as a robust mean estimation problem, allowing us to leverage existing techniques for efficient robust
mean estimation.
There are a number of directions along which Sever could be improved: first, it could be extended to
handle more general assumptions on the data; second, it could be strengthened to achieve better error bounds
in terms of the fraction of outliers; finally, one could imagine automatically learning a feature representation
in which Sever performs well. We discuss each of these ideas in detail below.
More general assumptions. The main underlying assumption on which Sever rests is that the top
singular value of the gradients of the data is small. While this appeared to hold true on the datasets we
considered, a common occurence in practice is for there to be a few large singular values, together with many
small singular values. It would therefore be desirable to design a version of Sever that can take advantage
of such phenomena. In addition, it would be worthwhile to do a more detailed empirical analysis across a
wide variety of datasets investigating properties that can enable robust estimation (the notion of resilience
in [SCV18] could provide a template for finding such properties).
√
Stronger robustness to outliers. In theory, Sever has a O( ε) dependence in error on the fraction
ε of outliers (see Theorem 2.1). While without stronger assumptions this is likely not possible to improve,
in practice we would prefer to have a dependence closer to O(ε). Therefore, it would also be useful to
improve Sever to have such an O(ε)-dependence under stronger but realistic assumptions.
Unfortunately,
√
all existing algorithms for robust mean estimation that achieve error better than O( ε) either rely on strong
distributional assumptions such as Gaussianity [DKK+ 16, LRV16], or else require expensive computation
involving e.g. sum-of-squares optimization [HL17, KS17a, KS17b]. Improving the robustness of Sever thus
requires improvements on the robust mean estimation algorithm that Sever uses as a primitive.
Learning a favorable representation. Finally, we note that Sever performs best when the features
have small covariance and strong predictive power. One situation in particular where this holds is when
there are many approximately independent features that are predictive of the true signal.
It would be interesting to try to learn a representation with such a property. This could be done, for
instance, by training a neural network with some cost function that encourages independent features (some
ideas along these general lines are discussed in [Ben17]). An issue is how to learn such a representation
robustly; one idea is learn a representation on a dataset that is known to be free of outliers, and hope that
the representation is useful on other datasets in the same application domain.
Beyond these specific questions, we view the general investigation of robust methods (both empirically
and theoretically) as an important step as machine learning moves forwards. Indeed, as machine learning
is applied in increasingly many situations and in increasingly automated ways, it is important to attend to
robustness considerations so that machine learning systems behave reliably and avoid costly errors. While
the bulk of recent work has highlighted the vulnerabilities of machine learning (e.g. [SZS+ 14, LWSV16,
SKL17, EEF+ 17, CLL+ 17]), we are optimistic that practical algorithms backed by principled theory can
finally patch these vulnerabilities and lead to truly reliable systems.

References
[ABL14] P. Awasthi, M. F. Balcan, and P. M. Long. The power of localization for efficiently learning linear
separators with noise. In Symposium on Theory of Computing (STOC), pages 449–458, 2014.

12

[BDLS17] S. Balakrishnan, S. S. Du, J. Li, and A. Singh. Computationally efficient robust sparse estimation
in high dimensions. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, pages
169–212, 2017.
[Ben17] Y. Bengio. The consciousness prior. arXiv preprint arXiv:1709.08568, 2017.
[BJK15] K. Bhatia, P. Jain, and P. Kar. Robust regression via hard thresholding. In Advances in Neural
Information Processing Systems 28: Annual Conference on Neural Information Processing Systems
2015, pages 721–729, 2015.
[BJKK17] K. Bhatia, P. Jain, P. Kamalaruban, and P. Kar. Consistent robust regression. In Advances in
Neural Information Processing Systems 30: Annual Conference on Neural Information Processing
Systems 2017, pages 2107–2116, 2017.
[BNJT10] M. Barreno, B. Nelson, A. D. Joseph, and J. D. Tygar. The security of machine learning. Machine
Learning, 81(2):121–148, 2010.
[BNL12] B. Biggio, B. Nelson, and P. Laskov. Poisoning attacks against support vector machines. In
International Conference on Machine Learning (ICML), pages 1467–1474, 2012.
[CLL+ 17] X. Chen, C. Liu, B. Li, K. Lu, and D. Song. Targeted backdoor attacks on deep learning systems
using data poisoning. arXiv preprint arXiv:1712.05526, 2017.
[CSV17] M. Charikar, J. Steinhardt, and G. Valiant. Learning from untrusted data. In Proceedings of STOC
2017, pages 47–60, 2017.
[DKK+ 16] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators
in high dimensions without the computational intractability. In Proceedings of FOCS’16, pages
655–664, 2016.
[DKK+ 17] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Being robust (in high
dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, pages 999–1008, 2017. Full version available at https://arxiv.org/abs/1703.00893.
[DKK+ 18] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. Robustly learning a
gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM
Symposium on Discrete Algorithms, SODA 2018, pages 2683–2702, 2018. Full version available at
https://arxiv.org/abs/1704.03866.
[DKS16] I. Diakonikolas, D. M. Kane, and A. Stewart. Robust learning of fixed-structure bayesian networks.
CoRR, abs/1606.07384, 2016.
[DKS17a] I. Diakonikolas, D. M. Kane, and A. Stewart. Learning geometric concepts with nasty noise.
CoRR, abs/1707.01242, 2017.
[DKS17b] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning
mixtures of spherical gaussians. CoRR, abs/1711.07211, 2017.
[DKS17c] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 58th IEEE Annual Symposium
on Foundations of Computer Science, FOCS 2017, pages 73–84, 2017. Full version available at
http://arxiv.org/abs/1611.03473.
[DKS18] I. Diakonikolas, W. Kong, and A. Stewart. Efficient algorithms and lower bounds for robust linear
regression. Manuscript, 2018.
[EEF+ 17] I. Evtimov, K. Eykholt, E. Fernandes, T. Kohno, B. Li, A. Prakash, A. Rahmati, and D. Song.
Robust physical-world attacks on machine learning models. arXiv, 2017.
13

[Gur16] Gurobi Optimization, Inc. Gurobi optimizer reference manual, 2016.
[HL17] S. B. Hopkins and J. Li.
abs/1711.07454, 2017.

Mixture models, robustness, and sum of squares proofs.

CoRR,

[Hub64] P. J. Huber. Robust estimation of a location parameter. Ann. Math. Statist., 35(1):73–101, 03 1964.
[KL17] P. W. Koh and P. Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning (ICML), 2017.
[KLS09] A. R. Klivans, P. M. Long, and R. A. Servedio. Learning halfspaces with malicious noise. Journal
of Machine Learning Research (JMLR), 10:2715–2740, 2009.
[KS17a] P. K. Kothari and J. Steinhardt. Better agnostic clustering via relaxed tensor norms. CoRR,
abs/1711.07465, 2017.
[KS17b] P. K. Kothari and D. Steurer. Outlier-robust moment-estimation via sum-of-squares. CoRR,
abs/1711.11581, 2017.
[LAT+ 08] J.Z. Li, D.M. Absher, H. Tang, A.M. Southwick, A.M. Casto, S. Ramachandran, H.M. Cann, G.S.
Barsh, M. Feldman, L.L. Cavalli-Sforza, and R.M. Myers. Worldwide human relationships inferred
from genome-wide patterns of variation. Science, 319:1100–1104, 2008.
[Löf04] J. Löfberg. YALMIP: A toolbox for modeling and optimization in MATLAB. In CACSD, 2004.
[LRV16] K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Proceedings
of FOCS’16, 2016.
[LWSV16] B. Li, Y. Wang, A. Singh, and Y. Vorobeychik. Data poisoning attacks on factorization-based
collaborative filtering. In Advances in Neural Information Processing Systems (NIPS), 2016.
[MAP06] V. Metsis, I. Androutsopoulos, and G. Paliouras. Spam filtering with naive Bayes – which naive
Bayes? In CEAS, volume 17, pages 28–69, 2006.
[MV17] M. Meister and G. Valiant. A data prism: Semi-verified learning in the small-alpha regime. arXiv,
2017.
[NPXNR14] A. Newell, R. Potharaju, L. Xiang, and C. Nita-Rotaru. On the practicality of integrity attacks
on document-level sentiment analysis. In Workshop on Artificial Intelligence and Security (AISec),
pages 83–93, 2014.
[NT13] N. H. Nguyen and T. D. Tran. Exact recoverability from dense corrupted observations via `1 minimization. IEEE Transactions on Information Theory, 59(4):2017–2035, 2013.
[NTN11] N. M. Nasrabadi, T. D. Tran, and N. Nguyen. Robust lasso with missing and grossly corrupted
observations. In Advances in Neural Information Processing Systems (NIPS), 2011.
[OSB+ 18] I. Olier, N. Sadawi, G. R. Bickerton, J. Vanschoren, C. Grosan, L. Soldatova, and Ross D.
King. Meta-qsar: a large-scale application of meta-learning to drug design and discovery. Machine
Learning, 107(1):285–311, Jan 2018.
[PLJD10] P. Paschou, J. Lewis, A. Javed, and P. Drineas. Ancestry informative markers for fine-scale
individual assignment to worldwide populations. Journal of Medical Genetics, 47:835–847, 2010.
[PSBR18] A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. Robust estimation via robust
gradient estimation. CoRR, abs/1802.06485, 2018.
[QV17] Mingda Qiao and Gregory Valiant. Learning discrete distributions from untrusted batches. arXiv
preprint arXiv:1711.08113, 2017.
14

[RPW+ 02] N. Rosenberg, J. Pritchard, J. Weber, H. Cann, K. Kidd, L.A. Zhivotovsky, and M.W. Feldman.
Genetic structure of human populations. Science, 298:2381–2385, 2002.
[SCV18] J. Steinhardt, M. Charikar, and G. Valiant. Resilience: A criterion for learning in the presence of
arbitrary outliers. In Innovations in Theoretical Computer Science (ITCS), 2018.
[SKL17] J. Steinhardt, P. W. Koh, and P. Liang. Certified defenses for data poisoning attacks. In Advances
in Neural Information Processing Systems (NIPS), 2017.
[Ste17] J. Steinhardt. Does robustness imply tractability? A lower bound for planted clique in the semirandom model. arXiv, 2017.
[SZS+ 14] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing
properties of neural networks. In International Conference on Learning Representations (ICLR),
2014.
[Tuk60] J. W. Tukey. A survey of sampling from contaminated distributions. Contributions to probability
and statistics, 2:448–485, 1960.

Appendix
The appendix is organized as follows. In Section A, we describe additional preliminaries required for our
technical arguments. In Section B, we analyze our main algorithm, Sever. In Section C, we specialize our
analysis to the important case of Generalized Linear Models (GLMs). In Section D, we describe a variant
of our algorithm which performs robust filtering on each iteration of projected gradient descent, and works
under more general assumptions. In Section E, we describe concrete applications of Sever – in particular,
how it can be used to robustly optimize in the settings of linear regression, logistic regression, and support
vector machines. Finally, in Section F, we provide additional plots from our experimental evaluations.

A

Preliminaries

In this section, we formally introduce our setting for robust stochastic optimization.
def

Notation. For n ∈ Z+ , we will denote [n] = {1, . . . , n}. For a vector v, we will let kvk2 denote its
Euclidean norm. For any r ≥ 0 and any x ∈ Rd , let B(x, r) be the `2 ball of radius r around x. If M is
a matrix, we will let kM k2 denote its spectral norm and kM kF denote its Frobenius norm. We will write
X ∼u S to denote that X is drawn from the empirical distribution defined by S. We will sometimes use the
notation ES , instead of EX∼S , for the corresponding expectation. We will also use the same convention for
the covariance, i.e. we let CovS denote the covariance over the empirical distribution. [Anything else?]
Setting. We consider a stochastic optimization setting with outliers. Let H ⊆ Rd be a space of parameters.
We observe n functions f1 , . . . , fn : H → R and we are interested in (approximately) minimizing some target
function f : H → R, related to the fi ’s. We will assume for simplicity that the fi ’s are differentiable with
gradient ∇fi . (Our results can be easily extended for the case that only a sub-gradient is available.)
In most concrete applications we will consider, there is some true underlying distribution p∗ over functions
def
f : H → R, and our goal is to find a parameter vector w∗ ∈ H minimizing f (w) = Ef ∼p∗ [f (w)]. Unlike the
∗
classical realizable setting, where we assume that f1 , . . . , fn ∼ p , we allow for an ε-fraction of the points
to be arbitrary outliers. This is captured in the following definition (Definition 2.1) that we restate for
convenience:

15

Definition A.1 (ε-corruption model). Given ε > 0 and a distribution p∗ over functions f : H → R, data is
generated as follows: first, n clean samples f1 , . . . , fn are drawn from p∗ . Then, an adversary is allowed to
inspect the samples and replace any εn of them with arbitrary samples. The resulting set of points is then
given to the algorithm.
In addition, some of our bounds will make use of the following quantities:
• The `2 -radius r of the domain H: r = maxw∈H kwk2 .
• The strong convexity parameter ξ of f , if it exists. This is the maximal ξ such that f (w) ≥ f (w0 ) +
hw − w0 , ∇f (w0 )i + 2ξ kw − w0 k22 for all w, w0 ∈ H.
• The strong smoothness parameter β of f , if it exists. This is the minimal β such that f (w) ≤
f (w0 ) + hw − w0 , ∇f (w0 )i + β2 kw − w0 k22 for all w, w0 ∈ H.
• The Lipschitz constant L of f , if it exists. This is the minimal L such that f (w) − f (w0 ) ≤ Lkw − w0 k2
for all w, w0 ∈ H.

B

General Analysis of Sever

This section is dedicated to the analysis of Algorithm 1, where we do not make convexity assumptions about
the underlying functions f1 , . . . , fn . In this case, we can show that our algorithm finds an approximate critical
point of f . When we specialize to convex functions, this immediately implies that we find an approximate
minimal point of f .
Our proof proceeds in two parts. First, we define a set of deterministic conditions under which our
algorithm finds an approximate minimal point of f . We then show that, under mild assumptions on our
functions, this set of deterministic conditions holds with high probability after polynomially many samples.
For completeness, we recall the definitions of a γ-approximate critical point and a γ-approximate learner:
Definition 2.2 (γ-approximate critical point). Given a function f : H → R, a γ-approximate critical point
of f , is a point w ∈ H so that for all unit vectors v where w + δv ∈ H for arbitrarily small positive δ, we
have that v · ∇f (w) ≥ −γ.
Definition 2.3 (γ-approximate learner). A learning algorithm L is called γ-approximate if, for any functions
f1 , . . . , fn : H → R each bounded below
Pn on a closed domain H, the output w = L(f1:n ) of L is a γapproximate critical point of f (x) := n1 i=1 fi (x).
Deterministic Regularity Conditions We first explicitly demonstrate a set of deterministic conditions
on the (uncorrupted) data points. Our deterministic regularity conditions are as follows:
Assumption B.1. Fix 0 < ε < 1/2. There exists an unknown set Igood ⊆ [n] with |Igood | ≥ (1 − ε)n of
“good” functions {fi }i∈Igood and parameters σ0 , σ1 ∈ R+ such that:
EIgood
and




T 
∇fi (w) − ∇f (w) ∇fi (w) − ∇f (w)

2

≤ (σ0 + σ1 kw∗ − wk2 )2 , for all w ∈ H ,

√
def
k∇fˆ(w) − ∇f (w)k2 ≤ (σ0 + σ1 kw∗ − wk2 ) ε, for all w ∈ H, where fˆ =

1
|Igood |

X

fi .

(1)

(2)

i∈Igood

In Section B.1, we prove the following theorem, which shows that under Assumption B.1 our algorithm
succeeds:
Theorem B.2. Suppose that the functions f1 , . . . , fn , f : H → R are bounded below, and that Assumpdef
tion B.1 is satisfied, where σ = σ0 + σ1 kw∗ − wk2 . Then
√ Sever applied to f1 , . . . , fn , σ returns a point
w ∈ H that, with probability at least 9/10, is a (γ + O(σ ε))-approximate critical point of f .
16

Observe that the above theorem holds quite generally; in particular, it holds for non-convex functions.
As a corollary of this theorem, in Section B.2 we show that this immediately implies that Sever robustly
minimizes convex functions, if Assumption B.1 holds:
Corollary B.3. For functions f1 , . . . , fn : H → R, suppose that Assumption B.1 holds and that H is convex.
Then, with probability at least 9/10, for some universal constant ε0 , if ε < ε0 , the output of Sever satisfies
the following:
√
(i) If f is convex, the algorithm finds a w ∈ H such that f (w) − f (w∗ ) = O((σ0 r + σ1 r2 ) ε + γr).
(ii) If f is ξ-strongly convex, the algorithm finds a w ∈ H such that


ε
γ2
∗
2
f (w) − f (w ) = O
(σ0 + σ1 r) +
.
ξ
ξ
In the strongly convex case and when σ1 > 0, we can remove the dependence on σ1 and r in the above
by repeatedly applying Sever with decreasing r:
Corollary B.4. For functions f1 , . . . , fn :√H → R, suppose that Assumption B.1 holds, that H is convex
and that f is ξ-strongly convex for ξ ≥ Cσ1 ε for some absolute constant C. Then, with probability at least
9/10, for some universal constant ε0 , if ε < ε0 , we can find a w
b with
 2

εσ0 + γ 2
∗
f (w)
b − f (w ) = O
.
ξ
and
kw
b − w ∗ k2 = O

√

εσ0 + γ
ξ



√
using at most O(log(rξ/(γ + σ0 ε))) calls to Sever.
To concretely use Theorem B.2, Corollary B.3, and Corollary B.4, in Section B.4 we show that the
Assumption B.1 is satisfied with high probability under mild conditions on the distribution over the functions,
after drawing polynomially many samples:
Proposition B.5. Let H ⊂ Rd be a closed bounded set with diameter at most r. Let p∗ be a distribution over
functions f : H → R with f = Ef ∼p∗ [f ] so that f − f is L-Lipschitz and β-smooth almost surely. Assume
furthermore that for each w ∈ H and unit vector v that Ef ∼p∗ [(v · (∇f (w) − f (w)))2 ] ≤ σ 2 /2. Then for
 2 2

d L log(rβL/σ 2 ε)
n=Ω
,
σ2 ε
an ε-corrupted set of points f1 , . . . , fn with high probability satisfy Assumption B.1.
The remaining subsections are dedicated to the proofs of Theorem B.2, Corollary B.3, Corollary B.4, and
Proposition B.5.

B.1

Proof of Theorem B.2

Throughout this proof we let Igood be as in Assumption B.1. We require the following two lemmata. Roughly
speaking, the first states that on average, we remove more corrupted points than uncorrupted points, and
the second states that at termination, and if we have not removed too many points, then we have reached a
point at which the empirical gradient is close to the true gradient. Formally:

17

Lemma B.6. If the samples satisfy (1) of Assumption B.1, and if |S| ≥ 2n/3 then if S 0 is the output of
Filter(S, τ, σ), we have that
E[|Igood ∩ (S\S 0 )|] ≤ E[|([n]\Igood ) ∩ (S\S 0 )|].
Lemma B.7. If the samples satisfy Assumption B.1, Filter(S, τ, σ) = S, and n − |S| ≤ 11εn, then
∇f (w) −

1
|Igood |

X

√
≤ O(σ ε)

∇fi (w)

i∈S

2

Before we prove these lemmata, we show how together they imply Theorem B.2.
Proof of Theorem B.2 assuming Lemma B.6 and Lemma B.7. First, we note that the algorithm
must terminate in at most n iterations. This is easy to see as each iteration of the main loop except
for the last must decrease the size of S by at least 1.
It thus suffices to prove correctness. Note that Lemma B.6 says that each iteration will on average
throw out as many elements not in Igood from S as elements in Igood . In particular, this means that
|([n]\Igood ) ∩ S| + |Igood \S| is a supermartingale. Since its initial size is at most εn, with probability at
least 9/10, it never exceeds 10εn, and therefore at the end of the algorithm, we must have that n − |S| ≤
εn + |Igood \S| ≤ 11εn. This will allow us P
to apply Lemma B.7 to complete the proof, using the fact that w
1
is a γ-approximate critical point of |Igood
i∈S ∇fi (w).
|
Thus it suffices to prove these two lemmata. We first prove Lemma B.6:
Proof of Lemma B.6. Let Sgood = S ∩ Igood and Sbad = S\Igood . We wish to show that the expected
number of elements thrown out of Sbad is at least the expected number thrown out of Sgood . We note that
our result holds trivially if Filter(S, τ, σ) = S. Thus, we can assume that Ei∈S [τi ] ≥ 12σ.
P
It is easy to see that the expected number of elements
Pthrown out of Sbad is proportional to i∈Sbad τi ,
while the number removed from Sgood is proportional to i∈Sgood τi (with the same proportionality). Hence,
P
P
it suffices to show that i∈Sbad τi ≥ i∈Sgood τi .
We first note that since Covi∈Igood [∇fi (w)]  σ 2 I, we have that
(a)

3
Covi∈Igood [v · ∇fi (w)]
2
3
= · v > Covi∈Igood [∇fi (w)]v ≤ 2σ 2 ,
2

Covi∈Sgood [v · ∇fi (w)] ≤

where (a) follows since |Sgood | ≥ 23 Igood .
Let µgood = Ei∈Sgood [v · ∇fi (w)] and µ = Ei∈S [v · ∇fi (w)]. Note that
Ei∈Sgood [τi ] = Covi∈Sgood [v · ∇fi (w)] + (µ − µgood )2 ≤ 2σ + (µ − µgood )2 .
We now split into two cases.
Firstly, if (µ − µgood )2 ≥ 4σ 2 , we let µbad = Ei∈Sbad [v · ∇fi (w)], and note that |µ − µbad ||Sbad | =
|µ − µgood ||Sgood |. We then have that
Ei∈Sbad [τi ] ≥ (µ − µbad )2
2



|Sgood |
|Sbad |

2

≥ (µ − µgood )


|Sgood |
≥2
(µ − µgood )2
|Sbad |


|Sgood |
Ei∈Sgood [τi ].
≥
|Sbad |
18

P
P
Hence, i∈Sbad τi ≥ i∈Sgood τi .
P
2
2
2
P On the other hand, if (µ − µgood ) ≤ 4σ , then Ei∈Sgood [τi ] ≤ 6σ ≤ Ei∈S [τi ]/2. Therefore i∈Sbad τi ≥
i∈Sgood τi once again. This completes our proof.
We now prove Lemma B.7.
Proof of Lemma B.7. We need to show that
X
(∇fi (w) − ∇f (w))
δ :=
i∈S

√
= O(nσ ε).
2

We note that
X
(∇fi (w) − ∇f (w))
i∈S

≤

2

X

(∇fi (w) − ∇f (w))

i∈Igood

=

X

+

i∈(Igood \S)

2

X

(∇fi (w) − ∇f (w))

i∈(Igood \S)

(∇fi (w) − ∇f (w))

2

√

+ O(n σ 2 ε).

(∇fi (w) − ∇f (w))

i∈(S\Igood )

2

(∇fi (w) − ∇f (w))

i∈(S\Igood )

2

X

+

X

+

2

First we analyze
X

(∇fi (w) − ∇f (w))

i∈(Igood \S)

This is the supremum over unit vectors v of
X

.
2

v · (∇fi (w) − ∇f (w)).

i∈(Igood \S)

However, we note that
X

(v · (∇fi (w) − ∇f (w)))2 = O(nσ 2 ).

i∈Igood

Since |Igood \S| = O(nε), we have by Cauchy-Schwarz that
X
√
p
v · (∇fi (w) − ∇f (w)) = O( (nσ 2 )(nε)) = O(n σ 2 ε),
i∈(Igood \S)

as desired.
We note that since for any such v that
X
X
(v · (∇fi (w) − ∇f (w)))2 =
(v · (∇fi (w) − ∇fˆ(w)))2 + δ 2 = O(nσ 2 ) + δ 2
i∈S

i∈S

(or otherwise our filter would have removed elements) and since |S\Igood | = O(nε), and so we have similarly
that
X
√
√
∇fi (w) − ∇f (w) = O(nσ ε + δ nε).
i∈(S\Igood )

2

Combining with the above we have that
p
√
δ = O(σ ε + δ ε/n),
√
and therefore, δ = O(σ ε) as desired.
19

B.2

Proof of Corollary B.3

In this section, we show that the Sever algorithm finds an approximate global optimum for convex optimization in various settings, under Assumption B.1. We do so by simply applying the guarantees of Theorem B.2
in a fairly black box manner.
Before we proceed with the proof of Corollary B.3, we record a simple lemma that allows us to translate
an approximate critical point guarantee to an approximate global optimum guarantee:
Lemma B.8. Let f : H → R be a convex function and let x 6= y ∈ H. Let v = y − x/ky − xk2 be the unit
vector in the direction of y − x. Suppose that for some δ that v · (∇f (x)) ≥ −δ and −v · (∇f (y)) ≥ −δ .
Then we have that:
1. |f (x) − f (y)| ≤ kx − yk2 δ.
2. If f is ξ-strongly convex, then |f (x) − f (y)| ≤ 2δ 2 /ξ and kx − yk2 ≤ 2δ/ξ.
Proof. Let r = kx − yk2 > 0 and g(t) = f (x + tv). We have that g(0) = f (x), g(r) = f (y) and that g is
convex (or ξ-strongly convex) with g 0 (0) ≥ −δ and g 0 (r) ≤ δ. By convexity, the derivative of g is increasing
on [0, r] and therefore |g 0 (t)| ≤ δ for all t ∈ [0, r]. This implies that
Z r
|f (x) − f (y)| = |g(r) − g(0)| =
g 0 (t)dt ≤ rδ .
0

To show the second part of the lemma, we note that if g is ξ-strongly convex that g 00 (t) ≥ ξ for all t. This
implies that g 0 (r) > g 0 (0) + ξr. Since g 0 (r) − g 0 (0) ≤ 2δ, we obtain that r ≤ 2δ/ξ, from which the second
statement follows.
def

Proof of Corollary B.3. By applying the algorithm of Theorem B.2, we can find a point w that is a γ 0 =
√
def
(γ + O(σ ε))-approximate critical point of f , where σ = σ0 + σ1 kw∗ − wk2 . That is, for any unit vector v
pointing towards the interior of H, we have that v · ∇f (w) ≥ −γ 0 .
To prove (i), we apply Lemma B.8 to f at w which gives that
|f (w) − f (w∗ )| ≤ r · γ 0 .
To prove (ii), we apply Lemma B.8 to f at w which gives that
2

|f (w) − f (w∗ )| ≤ 2γ 0 /ξ.
Plugging in parameters appropriately then immediately gives the desired bound.

B.3

Proof of Corollary B.4

We apply Sever iteratively starting with a domain H1 = H and radius r1 = r. After each iteration, we
know the resulting point is close to w∗ will be able to reduce the search radius.
At step i, we have a domain of radius ri . As in the proof of Corollary B.3 above, we apply algorithm of
√
def
Theorem B.2, we can find a point wi that is a γi0 = (γ + O(σi0 ε))-approximate critical point of f , where
def

σi0 = σ0 + σ1 ri . Then using Lemma B.8, we obtain that kwi − w∗ k2 ≤ 2γi0 /ξ.
0
Now we can define Hi+1 as the intersection of H and the ball of√radius ri+1
√ = 2γi /ξ around wi and
0
repeat using this domain. We have that ri+1 = 2γi /ξ = 2γ/ξ + O(σ0 ε/ξ + σ1 εri /ξ). Now if we √
choose
the constant C such that the constant in this O() is C/4, then using our assumption that ξ ≥ 2σ1 ε, we
obtain that
√
√
√
ri+1 ≤ 2γ/ξ + Cσ0 ε/4ξ + Cσ1 εri /4ξ ≤ 2γ/ξ + Cσ0 ε/4 + ri /4
√
√
Now if ri ≥ 8γ/ξ + 2Cσ
√ 0 ε/ξ, then we have ri+1 ≤ ri /2 and if ri ≤ 8γ/ξ + 2Cσ0 ε/ξ then we also have
ri+1 ≤ 8γ/ξ + 2Cσ0 ε/ξ . When ri is smaller than this we stop and output wi . Thus we stop in at most
20

√
√
√
O(log(r) − log(8γ/ξ√+ 2Cσ0 ε/ξ)) = O(log(rξ/(γ
+ σ0 ε)) iterations
and have ri = O(γ/ξ + Cσ0 ε). But
√
√
then γi0 = γ + O(σi0 ε)) ≤ γ + C(σ0 + σ1 ri0 ) ε/8 = O(γ + σ0 ε). Using Lemma B.8 we obtain that
|f (wi ) − f (w∗ )| ≤ 2γi02 /ξ = O(γ 2 /ξ + σ02 ε/ξ).
as required. The bound on kw
b − w∗ k2 follows similarly.
Remark B.1. While we don’t give explicit bounds on the number of calls to the approximate learner needed
by Sever, such bounds can be straightforwardly obtained under appropriate assumptions on the fi (see,
e.g., the following subsection). Two remarks are in order. First, in this case we cannot take advantage of
assumptions that only hold at f but might not on the corrupted average f . Second, our algorithm can take
advantage of a closed form for the minimum. For example, for the case of linear regression considered in
Section E, fi is not Lipschitz with a small constant if xi is far from the mean, but there is a simple closed
form for the minimum of the least squares loss.

B.4

Proof of Proposition B.5

We let Igood be the set of uncorrupted functions fi . It is then the case that |Igood | ≥ (1 − ε)n. We need to
show that for each w ∈ H that
Covi∈Igood [∇fi (w)] ≤ 3σ 2 I/4
(3)
and
∇f (w) −

1
|Igood |

X
i∈Igood

√
≤ O(σ 2 ε).

∇fi (w)

(4)

2

We will proceed by a cover argument. First we claim that for each w ∈ H that (3) and (4) hold with high
probability. For Equation (3), it suffices to show that for each unit vector v in a cover N of size 2O(d) of the
sphere that
Ei∈Igood [(v · (∇fi (w) − f ))2 ] ≤ 2σ 2 /3.
(5)
However, we note that
Ep∗ [(v · (∇f (w) − f ))2 ] ≤ σ 2 /2.
Since |v · (∇f (w) − f )| is always bounded by L, Equation (5) holds for each v, w with probability at least
1−exp(−Ω(nσ 2 /L2 )) by a Chernoff bound (noting that the removal of an ε-fraction of points cannot increase
this by much). Similarly, to show Equation 4, it suffices to show that for each such v that
√
Ei∈Igood [(v · (∇fi (w) − f ))] ≤ O(σ ε).
(6)
Noting that
Ep∗ [(v · (∇f (w) − f ))] = 0
2
2
A Chernoff bound implies that with
√ probability 1 − exp(−Ω(nσ ε/L )) that the average over our original set
of f ’s of (v · (∇f (w) − f )) is O(σ ε). Assuming
√ that Equation (5) holds, removing an ε-fraction of these f ’s
cannot change this value by more than O(σ ε). By union bounding over N and standard net arguments,
this implies that Equations (3) and (4) hold with probability 1 − exp(−Ω(dnσ 2 ε/L2 )) for any given w.
To show that our conditions hold for all w ∈ H,√we note that by β-smoothness, if Equation (4) holds for
some w, it holds for all other w0 in a ball of radius σ 2 ε/β (up to a constant multiplicative loss). Similarly,
if Equation (3) holds at some w, it holds with bound
σ 2 I for all w0 in a ball of radius σ 2 /(2Lβ). Therefore,
√
if Equations (3) and (4) hold for all w in a min( σ 2 ε/β, σ/(2Lβ))-cover of H, the assumptions of Theorem
B.2 will hold everywhere. Since we have such covers of size exp(O(d log(rβL/(σ 2 ε)))), by a union bound,
this holds with high probability if
 2 2

d L log(rβL/σ 2 ε)
n=Ω
,
σ2 ε

as claimed.
21

C

Analysis of Sever for GLMs

A case of particular interest is that of Generalized Linear Models (GLMs):
Definition C.1. Let H ⊆ Rd and Y be an arbitrary set. Let Dxy be a distribution over H × Y. For
each Y ∈ Y, let σY : R → R be a convex function. The generalized linear model (GLM) over H × Y with
distribution Dxy and link functions σY is the function f : Rd → R defined by f (w) = EX,Y [fX,Y (w)], where
fX,Y (w) := σY (w · X) .
A sample from this GLM is given by fX,Y (w) where (X, Y ) ∼ Dxy .
Our goal, as usual, is to approximately minimize f given ε-corrupted samples from Dxy . Throughout this
section we assume that H is contained in the ball of radius r around 0, i.e. H ⊆ B(0, r). Moreover, we will
let w∗ = arg minw∈H f (w) be a minimizer of f in H.
This case covers a number of interesting applications, including SVMs and logistic regression. Unfortunately, the tools developed in Appendix B do not seem to be able to cover this case in a simple manner.
In particular, it is unclear how to demonstrate that Assumption B.1 holds after taking polynomially many
samples from a GLM. To rectify this, in this section, we demonstrate a different deterministic regularity
condition under which we show Sever succeeds, and we show that this condition holds after polynomially
many samples from a GLM. Specifically, we will show that Sever succeeds under the following deterministic
condition:
Assumption C.1. Fix 0 < ε < 1/2. There exists an unknown set Igood ⊆ [n] with |Igood | ≥ (1 − ε)n
of “good” functions {fi }i∈Igood and parameters σ0 , σ2 ∈ R+ such that such that the following conditions
simultanously hold:
• Equation (1) holds with σ1 = 0 and the same σ0 , and
• The following equations hold:
√
k∇fˆ(w∗ ) − ∇f (w∗ )k2 ≤ σ0 ε , and
√
|fˆ(w) − f (w)| ≤ σ2 ε, for all w ∈ H ,
def
where fˆ =

1
|Igood |

P

i∈Igood

(7)
(8)

fi .

In this section, we will show the following two statements. The first demonstrates that Assumption C.1
implies that Sever succeeds, and the second shows that Assumption C.1 holds after polynomially many
samples from a GLM. Formally:
Theorem C.2. For functions f1 , . . . , fn : H → R, suppose that Assumption C.1 holds and that H is convex.
Then, for some universal constant ε0 , if ε < ε0 , there is an algorithm which, with probability at least 9/10,
finds a w ∈ H such that
√
√
f (w) − f (w∗ ) = r(γ + O(σ0 ε)) + O(σ2 ε) .
If the link functions are ξ-strongly convex, the algorithm finds a w ∈ H such that
√
√
(γ + O(σ0 ε))2
∗
f (w) − f (w ) = 2
+ O(σ2 ε) .
ξ
Proposition C.3. Let H ⊆ Rd and let Y be an arbitrary set. Let f1 , . . . , fn be obtained by picking fi i.i.d.
at random from a GLM f over H × Y with distribution Dxy and link functions σY , where


d log(dr/ε)
n=Ω
.
ε
Suppose moreover that the following conditions all hold:
22

1. EX∼Dxy [XX T ]  I,
2. |σY0 (t)| ≤ 1 for all Y ∈ Y and t ∈ R, and
3. |σY (0)| ≤ 1 for all Y ∈ Y.
Then with probability at least 9/10 over the original set of samples, there is a set of (1 − ε)n of the fi that
satisfy Assumption C.1 on H with σ0 = 2, σ1 = 0 and σ2 = 1 + r.and σ2 = 1 + r.

C.1

Proof of Theorem C.2

As before, since Sever either terminates or throws away at least one sample, clearly it cannot run for more
than n iterations. Thus the runtime bound is simple, and it suffices to show correctness.
We first prove the following lemma:
Lemma C.4. Let f1 , . . . , fn satisfy Assumption C.1. Then with probability at least 9/10, Sever applied to
√
f1 , . . . , fn , σ0 returns a point w ∈ H which is a (γ + O(σ0 ε))-approximate critical point of fˆ.
Proof. We claim that the empirical distribution over f1 , . . . , fn satisfies Assumption B.1 for the function
fˆ with σ0 as stated and σ1 = 0, with the Igood in Assumption B.1 being the same as in the definition of
Assumption C.1. Clearly these functions satisfy (2) (since the LHS is zero), so it suffices to show that they
satisfy (1) Indeed, we have that for all w ∈ H,
EIgood [(∇fi (w) − ∇fˆ(w))(∇fi (w) − ∇fˆ(w))> ]  EIgood [(∇fi (w) − ∇f (w))(∇fi (w) − ∇f (w))> ] ,
so they satisfy (1), since the RHS is bounded by Assumption C.1. Thus this lemma follows from an application
of Theorem B.2.
With this critical lemma in place, we can now prove Theorem C.2:
Proof of Theorem C.2. Condition on the event that Lemma
of Sever.
√ C.4 holds, and let w ∈ H be the output
√
By Assumption C.1, we know that fˆ(w∗ ) ≥ f (w∗ ) − σ2 ε, and moreover, w∗ is a γ + σ0 ε-approximate
critical point of fˆ.
√
Since each link function is convex, so is fˆ. Hence, by Lemma B.8, since w is a (γ +O(σ0 ε))-approximate
√
critical point of fˆ, we have fˆ(w) √
− fˆ(w∗ ) ≤ r(γ
√ + O(σ0 ε)). By Assumption B.1, this immediately implies
∗
that f (w) − f (w ) ≤ r(γ + O(σ0 ε)) + O(σ2 ε), as claimed.
The bound for strongly convex functions follows from the exact argument, except using the statement in
Lemma B.8 pertaining to strongly convex functions.

C.2

Proof of Proposition C.3

Proof. We first note that ∇fX,Y (w) = XσY0 (w · X). Thus, under Assumption C.1, we have for any v that
Ei [(v · (∇fi (w) − ∇f (w)))2 ]  Ei [(v · ∇fi (w))2 ] + 1  Ei [(v · Xi )2 ] + 1 .
In particular, since this last expression is independent of w, p
we only need to check this single matrix bound.
We let our good set be the set of samples with |X| ≤ 80 d/ε that were not corrupted. We use Lemma
A.18 of [DKK+ 17]. This shows that with 90% probability that the non-good samples make up at most an
ε/2 + ε/160-fraction of the original samples, and that E[XX T ] over the good samples is at most 2I. This
∗
proves that the spectral bound holds everywhere. Applying it to the ∇fX,Y
also with 90%
√ (w ), we find
∗
probability that the expectation over all samples of ∇fX,Y (wp) is within ε/3 of ∇f (w∗ ). Additionally,
√
throwing away the samples with |∇fX,Y (w∗ ) − ∇f (w∗ )| > 80 d/ε changes this by at most ε/2. Finally,
it also implies that the variance of ∇fX,Y (w∗ ) is at most 3/2I,
p and therefore, throwing away any other
ε-fraction of the samples changes it by at most an additional 3ε/2.

23

√
We only need to show that |Ei good [fi (w)] − EX [fX (w)]| ≤ ε for all w ∈ H. For this we note that
√ since
the fX and fi are all 1-Lipschitz, it suffices to show that |Ei good [fi (w)] − EX [fX (w)]| ≤ (1 + |w|) ε/2 on
an ε/2-cover of H. For this it suffices to show that the bound will hold pointwise except with probability
exp(−Ω(d log(r/ε))). We will want to bound this using pointwise concentration and union bounds, but this
runs into technical problems since very large values of X · w can lead to large values of f , so we will need
to make use of the condition above that the average of Xi XiT over our good samples is bounded by 2I. In
particular, this implies √
that the contribution
to the average of fi (w) over the good i coming from samples
√
remaining
where |Xi · w| ≥ 10|w|/ ε is at most ε(1 + |w|)/10. We consider the average of fi (w) over the p
d/ε and
i. Note that these
values
are
uniform
random
samples
from
f
(w)
conditioned
on
|X|
≤
80
X
√
|Xi · w| <√10|w|/ ε. It will suffices to show that taking n samples from this distribution has average within
since |fX (w)| ≤ O(1 + |X · w|), we have that
(1 + |w|) ε/2 of the mean with high probability. However,
√
over this distribution |fX (w)| is always O(1 + |w|)/ ε, and has variance at most O(1 + |w|)2 . Therefore,
by Bernstein’s Inequality, the probability that n random
samples from fX (w) (with the above conditions on
√
X) differ from their mean by more than (1 + |w|) ε/2 is
exp(−Ω(n2 (1 + |w|)2 ε/((1 + |w|)2 + n(1 + |w|)2 ))) = exp(−Ω(nε)).
Thus, for n at least a sufficiently large multiple of d log(dr/ε)/ε, this holds for all w in our cover of H with
high probability. This completes the proof.

D

An Alternative Algorithm: Robust Filtering in Each Iteration

In this section, we describe another algorithm for robust stochastic optimization. This algorithm uses
standard robust mean estimation techniques to compute approximate gradients pointwise, which it then
feeds into a standard projective gradient descent algorithm. This algorithm in practice turns out to be
somewhat slower than the one employed in the rest of this paper, because it employs a filtering algorithm
at every step of the projective gradient descent, and does not remember which points were filtered between
iterations. On the other hand, we present this algorithm for two reasons. Firstly, because it is a conceptually
simpler interpretation of the main ideas of this paper, and secondly, because the algorithm works under
somewhat more general assumptions. In particular, this algorithm only requires that for each w ∈ H that
there is a corresponding good set of functions, rather than that there exists a single good set that works
simultaneously for all w.
In particular, we can make do with the following somewhat weaker assumption:
Assumption D.1. Fix 0 < ε < 1/2 and parameter σ ∈ R+ . For each w ∈ H, there exists an unknown set
Igood = Igood (w) ⊆ [n] with |Igood | ≥ (1 − ε)n of “good” functions {fi }i∈Igood such that:
EIgood
and




T 
∇fi (w) − ∇f (w) ∇fi (w) − ∇f (w)

√
def
k∇fˆ(w) − ∇f (w)k2 ≤ σ ε, where fˆ =

1
|Igood |

≤ (σ)2 ,

(9)

2

X

fi .

(10)

i∈Igood

We make essential use of the following result, which appears in both [DKK+ 17, SCV18]:
Theorem D.2. Let µ ∈ Rd and a collection of points xi ∈ Rd , i ∈ [n] and σ > 0. Suppose that there exists
Igood ⊆ [n] with |Igood | ≥ (1 − ε)n satisfying the following:
1
|Igood |

X

(xi − µ)(xi − µ)>  σ 2 I and

i∈Igood

1
|Igood |

X

(xi − µ)

2

√
≤ σ ε.

(11)

i∈Igood

Then, if ε < ε0 for some universal constant ε0√, there is an efficient algorithm, Algorithm A, which outputs
an estimate µ̂ ∈ Rd such that kµ̂ − µk2 = O(σ ε).
24

Our general robust algorithm for stochastic optimization will make calls to Algorithm A in a black-box
manner, as well as to the projection operator onto H. We will measure the cost of our algorithm by the total
number of such calls.
Remark D.1. While it is not needed for the theoretical results established in this subsection, we note that the
robust mean estimation algorithm of [DKK+ 17] relies on an iterative outlier removal method only requiring
basic eigenvalue computations (SVD), while the [SCV18] algorithm employs semidefinite programming. In
our experiments, we use the algorithm in [DKK+ 17] and variants thereof.
Using the above black-box, together with known results on convex optimization with errors, we obtain
the following meta-theorem:
Theorem D.3. For functions f1 , . . . , fn : H → R, bounded below on a closed domain H, suppose that either
Assumption D.1
√ is satisfied with some parameters ε, σ > 0. Then there exists an efficient algorithm that
finds an O(σ ε)-approximate critical point of f .
Proof. We√note that by applying Algorithm A on {∇fi (w)}, we can find an approximation to ∇f (w) with
error O(σ ε). We note that standard projective gradient descent algorithms can be made √
to run efficiently
even if the gradients given are only approximate, and this can be used to find our O(σ ε)-approximate
critical point.

E

Applications of the General Algorithm

In this section, we present three concrete applications of our general robust algorithm. In particular, we describe how to robustly optimize models for linear regression, support vector machines, and logistic regression,
in Sections E.1, E.2, E.3, respectively.

E.1

Linear Regression

In this section, we demonstrate how our results apply to linear regression. We are given pairs (Xi , Yi ) ∈
Rd × R for i ∈ [n]. The Xi ’s are drawn i.i.d. from a distribution Dx , and Yi = hw∗ , Xi i + ei , for some
unknown w∗ ∈ Rd and the noise random variables ei ’s are drawn i.i.d. from some distribution De . Given
(Xi , Yi ) ∼ Dxy , the joint distribution induced by this process, let fi (w) = (Yi − hw, Xi i)2 . The goal is then
to find a w
b approximately minimizing the objective function
f (w) = E(X,Y )∼Dxy [(Y − hw, Xi)2 ] .
We work with the following assumptions:
Assumption E.1. Given the model for linear regression described above, assume the following conditions
for De and Dx :
• Ee∼De [e] = 0;
• Vare∼De [e] ≤ ξ;
• EX∼Dx [XX T ]  σ 2 I for some σ > 0;


• There is a constant C > 0, such that for all unit vectors v, EX∼Dx hv, Xi4 ≤ Cσ 4 .
Our main result for linear regression is the following:
Theorem E.2. Let ε > 0, and let Dxy bea distribution
over pairs (X, Y ) which satisfies the conditions of

d5
Assumption E.1. Suppose we are given O ε2 ε-noisy samples from Dxy . Then in either of the following
two cases, there exists an algorithm that, with probability at least 9/10, produces a w
b with the following
guarantees:
25



√

√
ξε+ε
1. If EX∼Dx [XX T ]  γI for γ = Ω( ε), then f (w)
b ≤ f (w∗ ) + O (ξ+ε)ε
and kw
b − w ∗ k2 = O
.
γ
γ
√
√
√
√
2. If kw∗ k2 ≤ r, then f (w)
b ≤ f (w∗ ) + O((( ξ + ε)r + Cr2 ) ε).
The proof will follow from two lemmas (proved in Section E.1.1 and E.1.2, respectively). First, we will
bound the covariance of the gradient, in Lemma E.3:
Lemma E.3. Suppose Dxy satisfies the conditions of Assumption E.1. Then for all unit vectors v ∈ Rd , we
have
v > Cov(X,Y )∼Dxy [∇fi (w, (X, Y ))] v ≤ 4σ 2 ξ + 4Cσ 4 kw∗ − wk22 .
With this in hand, we can prove Lemma E.4, giving us a polynomial sample complexity which is sufficient
to satisfy the conditions of Assumption B.1.
Lemma E.4. Suppose Dxy satisfies the conditions of Assumption E.1. Given O(d5 /ε2 ) ε-noisy√samples
√
from Dxy , then
√ with probability at last 9/10, they satisfy Assumption B.1 with parameters σ0 = 30 ξ + ε
and σ1 = 18 C + 1.
The proof concludes by applying Corollary B.4 or case (i) of Corollary B.3 for the first and second cases
respectively.
E.1.1

Proof of Lemma E.3

Note that for this setting we have that f (w, z) = f (w, x, y) = (y − hw, xi)2 . We then have that ∇w f (w, z) =
−2(hw∗ − w, xi + e)x. Our main claim is the following:


Claim E.5. We have that Cov[∇w f (w, z)] = 4 EX∼D hw∗ − w, xi2 (xxT ) + 4 Var[E]Σ − 4Σ(w∗ − w)(w∗ −
w)T Σ.
Proof. Let us use the notation A = ∇w f (w, z) and µ = E[A]. By definition, we have that Cov[A] =
E[AAT ] − µµT .
Note that µ = Ez [∇w f (w, z)] = Ez [(−2hw∗ − w, xi + e)x] = −2Σ(w∗ − w), where we use the fact that
Ez [e] = 0 and e is independent of x. Therefore, µµT = 4Σ(w∗ − w)(w∗ − w)T Σ.
To calculate E[AAT ], note that A = ∇w f (w, z) = −2(hw∗ − w, xi + e)x, and AT = −2(hw∗ − w, xi + e)xT .
Therefore, AAT = 4(hw∗ − w, xi2 + e2 + 2hw∗ − w, xie)(xxT ) and
Ez [AAT ] = 4 Ex [hw∗ − w, xi2 (xxT )] + 4 Var[e]Σ + 0 ,
where we again used the fact that the noise e is independent of x and its expectation is zero.
By gathering terms, we get that
Cov[∇w f (w, z)] = 4 Ex [hw∗ − w, xi2 (xxT )] + 4 Var[e]Σ − 4Σ(w∗ − w)(w∗ − w)T Σ .
This completes the proof.
Given the above claim, we can bound from above the spectral norm of the covariance matrix of the
gradients as follows: Specifically, for a unit vector v, the quantity v T Cov[∇w f (w, z)]v is bounded from
above by a constant times the following quantities:
• The first term is v T Ex [hw∗ − w, xi2 (xxT )]v = Ex [hw∗ − w, xi2 · hv, xi2 )]. By Cauchy-Schwarz and our
4th moment bound, this is at most Cσ 4 kw∗ − wk22 , where Σ  σ 2 I.
• The second term is at most the upper bound of the variance of the noise ξ times σ 2 .
• The third term is at most v T Σ(w∗ − w)(w∗ − w)T Σv, which by our bounded covariance assumption is
at most σ 4 kw∗ − wk22 .
This gives the parameters in the meta-theorem.
26

E.1.2

Proof of Lemma E.4

√
Let S be the set of uncorrupted samples and I be the subset of S with kXk2 ≤ 2 d/ε1/4 . We will take Igood
to be the subset of I that are not corrupted.
Firstly, we show that with probability at least 39/40, at most an ε/2-fraction of points inq
S have kXk2 >
√
Pd
Pd Pd
2 d/ε1/4 , and so |Igood | ≥ (1−ε)|S|. Note that ED [kXk42 ] = ED [( j=1 Xj2 )2 ] ≤ j=1 k=1 ED [Xj2 ] E[Xk2 ] ≤
√
Cd2 , since EDx [XX T ]  I. Thus, by Markov’s inequality, PrD [kXk2 > 2 d(C/ε)1/4 ] = PrD [kXk42 >
16d2 /ε] ≤ ε/16. By a Chernoff bound, since n ≥ 10ε2 this probability is at most ε/2 for the uncorrupted
samples with probability at least 39/40.
Next, we show that (1) holds with probability at least 39/40. To do this, we will apply Lemma E.3 to
Igood . Since S consists of independent samples, the variance over the randomness of S of |S| ES [e2 ] is at
most |S|ξ. By Chebyshev’s inequality, except with probability 1/99, we have that ES [e2 ] ≤ 99ξ and since
Igood ⊂ S, EIgood [e2 ] ≤ |S| ES [e2 ]/|I| ≤ 100ξ. This is condition (i) of Lemma E.3.
√
We note that I consists of Ω(d5 /ε2 ) independent samples from D conditioned on kXk2 < 2 d/ε1/4 , a
distribution that we will call D0 . Since the VC-dimension of all halfspaces in Rd is d+1, by the VC inequality,
we have that, except with probability 1/80, for any unit vector v and T ∈ R that
R ∞ | PrI [v·X > T ]−PrD0 [v·X >
T ]| ≤ ε/d2 . Note that for unit vector v and positive integer m, E[(v.X)m ] = 0 m(v ·X)m−1 Pr[v ·X > T ]dT .
Thus we have that
Z ∞
EI [(v.X)m ] =
m(v · X)m−1 Pr[v · X > T ]dT
I

0

Z

2d1/2 (C/ε)1/4

m(v · X)m−1 (Pr0 [v · X > T ] + ε/d2 )dT

≤

D

0
m

1/2

= ED0 [(v.X) ] + (2d

1/4 m

(C/ε)

) (ε/d2 )

≤ (1 + ε) ED [(v.X)m ] + 2m C m/4 (ε/d2 )1−m/4 .
√
Applying this for m = 2 gives EI [XX T ]  (1 + ε + 4 Cε/d2 )I  2I and with m = 4 gives EI [(v.X)4 ] ≤
(1 + ε)C + 16C. Similar bounds apply to Igood , with an additional 1 + ε factor.
2
Thus, with probability at least 39/40, Igood satisfies
the conditions
√ of Lemma E.3 with ξ := 100ξ, σ := 2
√
and C := 5C. Hence, it satisfies (1) with σ0 = 20 ξ and σ1 = 18 C + 1.
For (2), note that ∇w fi (w) = (w · xi − yi )xi = ((w − w∗ ) · xi )xi − ei xi . We will separately bound
k EIgood [((w − w∗ ) · X)X] − ED [((w − w∗ ) · X)X]k2 and k EIgood [eX] − ED [eX]k2 .
We will repeatedly make use of the following, which bounds how much removing points or probability
mass affects an expectation in terms of its variance:
Claim E.6. For a mixture of distributions P = (1 − δ)Q +
pδR for distributions P, Q, R and a real valued
function f , we have that | EX∼P [f (X)] − EX∼Q [f (X)]| ≤ 2 δ EX∼P [f (X)2 ]/(1 − δ)
p
p
Proof. By Cauchy-Schwarz | EX∼R [f (X)]| ≤ EX∼R [f (X)2 ] ≤ EX∼P [f (X)2 ]/δ. SincepEX∼P [f (X)] =
(1−δ) EX∼Q [f (X)]+δ EX∼R [f (X)], this implies that | EX∼P [f (X)]/(1−δ)−EX∼Q [fp
(X)]| ≤ δ EX∼P [f (X)2 ]/(1−
δ). However | EX∼P [f (X)]/(1 − δ) − EX∼P [f (X)]| = (δ/(1 − δ))| EX∼P [f (X)]| ≤ δ EX∼P [f (X)2 ]/(1 − δ)
and the triangle inequality gives the result.
We can apply
this to P = I and Q = Igood with δ = ε/2 and also to P = D and Q = D0 with δ = ε/16,
√
√
with error 2 δ/(1 − δ) ≤ 2 ε in either case.
For the first of term we wanted to bound,
we have k EIgood [((w − w∗ ) · X)X] − ED [((w − w∗ ) · X)X]k2 =

T
T
∗ T
k(w − w ) EIgood [XX ] − ED [XX ] k2 ≤ kw − w∗ k2 k EIgood [XX T ] − ED [XX T ]k2 . For any unit vector v,
√
2
0 [(v · X) )]| ≤ 4
the VC dimension argument above gave that
| EI [(v · X)2 ] − ED√
Cε/d2 and Claim E.6 both
p
2
2
4
gives that | EI [(v·X) ]−EIgood [(v·X) )]| ≤ 2 ε EI [(v.X) ] ≤ 10 Cε and that | ED [(v·X)2 ]−ED0 [(v·X)2 )]| ≤
p
√
√
2 ε ED [(v.X)4 ] ≤ 2 Cε. By the triangle inequality, we have that | ED [(v ·X)2 ]−EIgood [(v ·X)2 )]| ≤ 16 Cε.
Since this holds for all unit v and the matrices involved are symmetric, we have that k EIgood [XX T ] −
27

√
ED [XX T ]k2 ≤ 16 Cε. The overall first term is bounded by k EIgood [((w − w∗ ) · X)X] − ED [((w − w∗ ) ·
√
X)X]k2 ≤ 16 Cεkw − w∗ k2 .
Now we want to bound the second term, k EIgood [eX] − ED [eX]k2 . Note that ED [eX] = ED [e] ED [X] = 0.
So we need to bound EIgood [eX]. First we bound the expectation and variance on D0 using Claim E.6. It
p
√
yields that, for any unit vector v, | ED0 [e(v · X)]| ≤ 2 ε ED [e2 (v · X)2 ] ≤ 2 εξ.
Next we bound the expectation on I. Since I consists of independent samples from D0 , the covariance
matrix over the randomness on I of |I| EI [eX − ED0 [eX]] is |I| ED0 [(eX − ED0 [eX])(eX − ED0 [eX])T ] ≤
|I| ED0 [XX T ] ≤ |I|(1 + ε)I and its expectation is 0. Thus the expectation over the randomness of I of
T
0 [eX]) ]) ≤ |I|(1 + ε + 4ξε|I|)d.
(|I|2 k EI [eX] − ED0 [eX]k2 )2 is Tr(|I| ED0 [(eX − ED0 [eX])(eX − ED√
By
Markov’s inequality, except with probability 1/40, Pr[k EI [eX]k2 ≥ 2 ξε + ε] ≤ d/|I|ε2 . Since |I| ≥ 40d/ε2 .
This happens with probability at least 1/40.
Next we bound the expectation on Igood which
follows by a slight p
variation of Claim E.6.pLet J =
p
EJ [e2 ] EJ [(v · X)2 ] ≤
ES [e2 ] EI [(v · X)2 ]|J|/ |S||I| ≤
Iq− Igood . Then, for any v, EJ [e(v · X)] ≤
p
p
√
100ξ(1 + ε + 4 Cε/d2 )|J|/ |S||I| ≤ 20|J| ξ/|S||I| by bounds we obtained earlier. Now k EIgood [eX]k2 =
p
√
√
k(|I|/|Igood |) EI [eX] − (|J|/|Igood |) EJ [eX]k2 ≤ 20 ξε + ε + (1 +√ε) ξε/16 ≤ 30 ξε + ε.
√
√
√
= 18 √C + 1 ≥ 16 C√to get (2).
We can thus take σ0 = 30 ξ + ε and σ1 √
To get both (2) and (1) hold with σ0 = 30 ξ + ε and σ1 = 18 C + 1). This happens with probability
at least 9/10 by a union bound on the probabilistic assumptions above.

E.2

Support Vector Machines

In this section, we demonstrate how our results apply to learning support vector machines (i.e., halfspaces
under hinge loss). In particular, we describe how SVMs fit into the GLM framework described in Section C.
We are given pairs (Xi , Yi ) ∈ Rd ×{±1} for i ∈ [n], which are drawn from some distribution Dxy . Let
L(w, (x, y)) = max{0, 1 − y(w · x)}, and fi (w) = L(w, (xi , yi )). The goal is to find a w
b approximately
minimizing the objective function
f (w) = E(X,Y )∼Dxy [L(w, (X, Y ))].
One technical point is that fi does not have a gradient everywhere – instead, we will be concerned with
the sub-gradients of the fi ’s. All our results which operate on the gradients also work for sub-gradients. To
be precise, we will take the sub-gradient to be 0 when the gradient is undefined:
Definition E.1. Let ∇fi be the sub-gradient of fi (w) with respect to w, where ∇fi = −yi xi if yi (w ·xi ) < 1,
and 0 otherwise.
To get a bound on the error of hinge loss, we will need to assume the marginal distribution Dx is
anti-concentrated.
Definition E.2. A distribution is δ-anticoncentrated if at most an O(δ)-fraction of its probability mass is
within Euclidean distance δ of any hyperplane.
We work with the following assumptions:
Assumption E.7. Given the model for SVMs as described above, assume the following conditions for the
marginal distribution Dx :
• EX∼Dx [XX T ]  I;
• Dx is ε1/4 -anticoncentrated.
Our main result on SVMs is the following:

28

Theorem E.8. Let ε > 0, and let Dxy be a distribution over pairs (X, Y ), where the marginal distribution
Dx satisfies the conditions of Assumption E.7. Then there exists an algorithm that with probability 9/10,
given O(d log(d/ε)/ε) ε-noisy samples from Dxy , returns a w
b such that for any w∗ ,
E(X,Y )∼Dxy [L(w,
b (X, Y ))] ≤ E(X,Y )∼Dxy [L(w∗ , (X, Y ))] + O(ε1/4 ).
Our approach will be to fit this problem into the GLM framework developed in Section C. First, we will
restrict our search over w to H, a ball of radius r = ε−1/4 . As we argue in Lemma E.9, this restriction
comes at a cost of at most O(ε1/4 ) in our algorithm’s loss. With this restriction, we will argue that the
problem satisfies the conditions of Proposition C.3. This allows us to argue that, with a polynomial number
of samples, we can obtain a set of fi ’s satisfying the conditions of Assumption C.1. This will allow us to
apply Theorem C.2, concluding the proof.
We start by showing that, due to anticoncentration of D, there is a w0 ∈ H with loss close to w∗ :
Lemma E.9. Let w0 be a rescaling of w∗ , such that kw0 k2 ≤ ε−1/4 (i.e. w0 = min{1, ε−1/4 /kw∗ k2 }w∗ ).
Then E(X,Y )∼Dxy [L(w0 , (X, Y ))] ≤ E(X,Y )∼Dxy [L(w∗ , (X, Y ))] + O(ε1/4 ).
Proof. If w0 = w∗ , then E(X,Y )∼Dxy [L(w0 , (X, Y ))] = E(X,Y )∼Dxy [L(w∗ , (X, Y ))].
Otherwise, we break into case analysis, based on the value of (x, y):
• |w0 ·x| > 1: If y(w0 ·x) > 1, then L(w0 , (x, y)) = L(w∗ , (x, y)) = 0. If y(w0 ·x) < −1, then L(w0 , (x, y)) =
1 − y(w0 · x) ≤ 1 − y(w∗ · x) = L(w∗ , (x, y)). Both cases use the fact that kw0 k2 < kw∗ k2 .
• |w0 · x| ≤ 1: In this case, we have that L(w0 , (x, y)) ≤ 2. Since L(w∗ , (x, y)) ≥ 0, we have that
L(w0 , (x, y)) ≤ L(w∗ , (x, y)) + 2.
Note that if |w0 · x| ≤ 1, then x is within 1/kw0 k2 = ε1/4 of the hyperplane defined by the normal vector
w0 . Since Dx is ε1/4 -anticoncentrated, we have that PrX∼Dx [|w0 · X| ≤ 1] ≤ ε1/4 . Thus, we have that
E(X,Y )∼Dxy [L(w0 , (X, Y ))] ≤ E(X,Y )∼Dxy [L(w∗ , (X, Y )) + 2 · 1(|w0 · X| ≤ 1)] ≤ E(X,Y )∼Dxy [L(w∗ , (X, Y ))] +
O(ε1/4 ).
Proof of Theorem E.8. We first show that this problem fits into the GLM framework, in particular, satisfying
the conditions of Proposition C.3. The link function is σy (t) = max{0, 1 − yt}, giving us the loss function
L(w, (x, y)) = σy (w · x). We let H be the set kwk2 ≤ ε−1/4 , giving us the parameter r = ε−1/4 . Condition
1 is satisfied by Assumption E.7. For y ∈ {−1, 1}, σy0 (t) = 0 for yt ≥ 1 and σy0 (t) = −y for yt < 1. Thus
we have that |σ10 (t)| ≤ 1 for all t and y, satisfying Condition 2. Finally, one can observe that σy (0) = 1 for
all y, satisfying Condition 3. Thus we can apply Proposition C.3: if we take O(d log(dr/ε)/ε) ε-corrupted
samples, then they satisfy Assumption C.1 on H with σ0 = 2, σ1 = 0 and σ2 = 1 + ε−1/4 , with probability
9/10.
Now we can apply the algorithm√of Theorem C.2. Since √
the loss is convex, we get a vector w
b with
f (w)
b − f (w∗ 0 ) = O((σ0 r + σ1 r2 + σ2 ) ε) = O((2ε−1/4 + ε−1/4 ) ε) = O(ε1/4 ) where w∗ 0 is the minimizer of
f on H.
We thus have that f (ŵ) ≤ f (w∗ 0 ) + O(ε1/4 ) ≤ f (w0 ) + O(ε1/4 ) ≤ f (w∗ ) + O(ε1/4 ). The second inequality
follows because w∗ 0 is the minimizer of f on H, and the third inequality follows from Lemma E.9.

E.3

Logistic Regression

In this section, we demonstrate how our results apply to logistic regression. In particular, we describe how
logistic regression fits into the GLM framework described in Section C.
We are given pairs (Xi , Yi ) ∈ Rd ×{±1} for i ∈ [n], which are drawn from some distribution Dxy . Let
1
φ(t) = 1+exp(−t)
. Logistic regression is the model where y = 1 with probability φ(w · x), and y = −1 with
probability φ(−w · x). We define the loss function to be the log-likelihood of y given x. More precisely, we
let fi (w, (xi , yi )) = L(w, (xi , yi )), which is defined as follows:




1+y
1
1−y
1
1
L(w, (x, y)) =
ln
+
ln
= (− ln (φ(w · x)φ(−w · x)) − y(w · x)) .
2
φ(w · x)
2
φ(−w · x)
2
29

The gradient of this function is ∇L(w, (x, y)) =
approximately minimizing the objective function

1
2 (φ(w

· x) − φ(−w · x) − y)x. The goal is to find a w
b

f (w) = E(X,Y )∼Dxy [L(w, (X, Y ))].
We work with the following assumptions:
Assumption E.10. Given the model for logistic regression as described above, assume the following conditions for the marginal distribution Dx :
• EX∼Dx [XX T ]  I;
p
• Dx is ε1/4 log(1/ε)-anticoncentrated.
We can get a similar result to that for hinge loss for logistic regression:
Theorem E.11. Let ε > 0, and let Dxy be a distribution over pairs (X, Y ), where the marginal distribution
Dx satisfies the conditions of Assumption E.10. Then there exists an algorithm that with probability 9/10,
given O(d log(d/ε)/ε) ε-noisy samples from Dxy , returns a w
b such that for any w∗ ,
p
b (X, Y ))] ≤ E(X,Y )∼Dxy [L(w∗ , (X, Y ))] + O(ε1/4 log(1/ε)).
E(X,Y )∼Dxy [L(w,
The approach is very similar to that of Theorem E.8, which
p we repeat here for clarity. First, we will
−1/4
restrict our search over w to H, a ball of radius
r
=
ε
log(1/ε). As we argue in Lemma E.12, this
p
1/4
restriction comes at a cost of at most O(ε
log(1/ε)) in our algorithm’s loss. With this restriction, we
will argue that the problem satisfies the conditions of Proposition C.3. This allows us to argue that, with a
polynomial number of samples, we can obtain a set of fi ’s satisfying the conditions of Assumption C.1. This
will allow us to apply Theorem C.2, concluding the proof.
We start by showing that, due to anticoncentration of D, there is a w0 ∈ H with loss close to w∗ :
p
p
0
−1/4
(i.e.
w
=
min{1,
ε
ln(1/ε)/kw∗ k2 }w∗ ).
Lemma E.12. Let w0 be a rescaling of w∗ , such that kw0 k2 ≤ ε−1/4 ln(1/ε)
p
∗
1/4
0
Then E(X,Y )∼Dxy [L(w , (X, Y ))] ≤ E(X,Y )∼Dxy [L(w , (X, Y ))] + O(ε
ln(1/ε)).
Proof. We need the following claim:
Claim E.13.
|t| ≤ − ln(φ(t)φ(−t)) ≤ |t| + 3 exp(−|t|)
Proof. Recalling that φ = 1/(1 + exp(−t)), we have that − ln(φ(t)φ(−t)) = ln(exp(t) + exp(−t) + 2). Since
exp(t) + exp(−t) + 2 ≥ exp(|t|), we have |t| ≤ − ln(φ(t)φ(−t)). On the other hand, ln(exp(t) + exp(−t) + 2) =
|t| + ln(1 + 2 exp(−|t|) + exp(−2|t|)) ≤ |t| + ln(1 + 3 exp(−|t|)) ≤ |t| + 3 exp(−|t|).
For any x ∈ Rd , we have that:
− ln(φ(w0 · x)φ(−w0 · x)) − y(w0 · x) − 3 exp(−3|w0 · x|) ≤ |w0 · x| − y(w0 · x)
≤ |w∗ · x| − y(w∗ · x)
≤ − ln(φ(w∗ · x)φ(−w∗ · x)) − y(w∗ · x)
The first and last inequality hold by Claim E.13. For the second inequality, we do a case analysis on y. When
y = sign(w0 ·x) = sign(w∗ ·x), then both sides of the inequality are 0. When y = −sign(w0 ·x) = −sign(w∗ ·x),
then the inequality becomes 2|w0 · x| ≤ 2|w∗ · x|, which holds since kw0 k2 ≤ kw∗ k2 . We thus have that for
any y ∈ {±1}, L(w0 , (x, y)) ≤ L(w∗ , (x, y)) + 23 exp(−3|w0 · x|). If |w0 · x| ≤ 31 ln(1/ε), then L(w0 , (x, y)) ≤
p
L(w∗ , (x, y)) + 32 . If |w0 · x| ≥ 13 ln(1/ε), then L(w0 , (x, y)) ≤ L(w∗ , (x, y)) + 32 ε. Since kw0 k2 ≤ ε−1/4 ln(1/ε)
p
p
and Dx is ε1/4 ln(1/ε)-anticoncentrated, we have that PrDx [|w0 · x| ≤ 31 ln(1/ε)] ≤ O(ε1/4 ln(1/ε)). Thus,
p
E(X,Y )∼Dxy [L(w0 , (X, Y ))] ≤ E(X,Y )∼Dxy [L(w∗ , (X, Y ))] + O(ε1/4 ln(1/ε)), as desired.
30

With this in hand, we can conclude with the proof of Theorem E.11.
Proof of Theorem E.11. We first show that this problem fits into the GLM framework, in particular, satisfying the conditions of Proposition C.3. The link function is σy (t) = 21 (− ln(φ(t)φ(−t)) − yt), giving us the
p
−1/4
loss function
L(w,
(x,
y))
=
σ
(w
·
x).
We
let
H
be
the
set
kwk
≤
ε
ln(1/ε), giving us the parameter
y
2
p
−1/4
r=ε
ln(1/ε). Condition 1 is satisfied by Assumption E.10. For y ∈ {−1, 1}, σy0 (t) = 21 (φ(t)−φ(−t)−y),
which gives that |σy0 (t)| ≤ 1 for all t and y, satisfying Condition 2. Finally, σy (0) = ln 2 < 1 for all y, satisfying Condition 3. Thus we can apply Proposition C.3: if we take O(d log(dr/ε)/ε)
ε-corrupted samples, then
p
they satisfy Assumption C.1 on H with σ0 = 2, σ1 = 0 and σ2 = 1 + ε−1/4 ln(1/ε), with probability 9/10.
Now we can apply the algorithm √
of Theorem C.2. pSince the loss ispconvex, we
b with
pw
√ get a vector
f (w)
b − f (w∗ 0 ) = O((σ0 r + σ1 r2 + σ2 ) ε) = O((2ε−1/4 ln(1/ε) + ε−1/4 ln(1/ε)) ε) = O(ε1/4 ln(1/ε))
where w∗ 0 is the minimizer of f on H.
p
p
p
We thus have that f (ŵ) ≤ f (w∗ 0 )+O(ε1/4 ln(1/ε)) ≤ f (w0 )+O(ε1/4 ln(1/ε)) ≤ f (w∗ )+O(ε1/4 ln(1/ε)).
The second inequality follows because w∗ 0 is the minimizer of f on H, and the third inequality follows from
Lemma E.12.

F

Additional Experimental Results

In this section, we provide additional plots of our experimental results, comparing with all baselines considered.

1.00

0.50

0.00
0.00 0.02 0.04 0.06 0.08 0.10

Regression: Drug discovery data
2.00

Regression: Drug discovery data,
attack targeted against Sever
2.00

1.80

1.80
Test Error

Test Error

Test Error

Regression: Synthetic data

1.60
1.40

1.60
1.40

1.20

1.20

1.00
0.00 0.02 0.04 0.06 0.08 0.10

1.00
0.00 0.02 0.04 0.06 0.08 0.10

Outlier Fraction epsilon

Outlier Fraction epsilon

uncorrupted
loss

noDefense
gradientCentered

Outlier Fraction epsilon

l2
Sever

Figure 7: ε vs test error for baselines and Sever on synthetic data and the drug discovery dataset. The left
and middle figures show that Sever continues to maintain statistical accuracy against our attacks which are
able to defeat previous baselines. The right figure shows an attack with parameters chosen to increase the
test error Sever on the drug discovery dataset as much as possible. Despite this, Sever still has relatively
small test error.

31

SVM: Strongest attacks against loss on synthetic data

SVM: Strongest attacks against Sever on synthetic data
0.25

0.30

Test Error

Test Error

0.20

0.20

0.15

0.10
0.10
0.05

0.00
0.00

0.01

0.02

0.00
0.00

0.03

0.01

0.02

0.03

Outlier Fraction epsilon

Outlier Fraction epsilon

uncorrupted
gradient

noDefense
gradientCentered

l2
Sever

loss

Figure 8: ε vs test error for baselines and Sever on synthetic data. The left figure demonstrates that Sever
is accurate when outliers manage to defeat previous baselines. The right figure shows the result of attacks
which increased the test error the most against Sever. Even in this case, Sever performs much better than
the baselines.

SVM: Strongest attacks against
gradientCentered on Enron

SVM: Strongest attacks
against Sever on Enron

SVM: Strongest attacks
against loss on Enron
0.20

0.10

0.00
0.00

0.01

0.02

0.03

0.20

Test Error

Test Error

Test Error

0.20

0.10

0.00
0.00

Outlier Fraction epsilon

uncorrupted
gradient

0.01

0.02

0.03

0.10

0.00
0.00

Outlier Fraction epsilon

noDefense
gradientCentered

0.01

0.02

0.03

Outlier Fraction epsilon

l2
Sever

loss

Figure 9: ε versus test error for baselines and Sever on the Enron spam corpus. The left and middle
figures are the attacks which perform best against two baselines, while the right figure performs best against
Sever. Though other baselines may perform well in certain cases, only Sever is consistently accurate. The
exception is for certain attacks at ε = 0.03, which, as shown in Figure 6, require three rounds of outlier
removal for any method to obtain reasonable test error – in these plots, our defenses perform only two
rounds.

32

