Learning from Untrusted Data

arXiv:1611.02315v2 [cs.LG] 11 Jun 2017

Moses Charikar
Stanford University
moses@cs.stanford.edu

Jacob Steinhardt
Stanford University
jsteinha@stanford.edu

Gregory Valiant
Stanford University
valiant@stanford.edu

Abstract
The vast majority of theoretical results in machine learning and statistics assume that the available
training data is a reasonably reliable reflection of the phenomena to be learned or estimated. Similarly,
the majority of machine learning and statistical techniques used in practice are brittle to the presence of
large amounts of biased or malicious data. In this work we consider two frameworks in which to study
estimation, learning, and optimization in the presence of significant fractions of arbitrary data.
The first framework, list-decodable learning, asks whether it is possible to return a list of answers,
with the guarantee that at least one of them is accurate. For example, given a dataset of n points for
which an unknown subset of αn points are drawn from a distribution of interest, and no assumptions are
made about the remaining (1 − α)n points, is it possible to return a list of poly(1/α) answers, one of
which is correct? The second framework, which we term the semi-verified learning model, considers the
extent to which a small dataset of trusted data (drawn from the distribution in question) can be leveraged
to enable the accurate extraction of information from a much larger but untrusted dataset (of which only
an α-fraction is drawn from the distribution).
We show strong positive results in both settings, and provide an algorithm for robust learning in a very
general stochastic optimization setting. This general result has immediate implications for robust estimation in a number of settings, including for robustly estimating the mean of distributions with bounded
second moments, robustly learning mixtures of such distributions, and robustly finding planted partitions
in random graphs in which significant portions of the graph have been perturbed by an adversary.

1 Introduction
What can be learned from data that is only partially trusted? In this paper, we study this question by considering the following setting: we observe n data points, of which αn are drawn independently from a
distribution of interest, p∗ , and we make no assumptions about the remaining (1 − α)n points—they could
be very biased, arbitrary, or chosen by an adversary who is trying to obscure p∗ . Our goal is to accurately
recover a parameter of interest of p∗ (such as the mean), despite the presence of significant amounts of untrusted data. Perhaps surprisingly, we will show that in high dimensions, accurate estimation and learning is
often possible, even when the fraction of real data is small (i.e., α ≪ 1). To do this, we consider two notions
of successful learning–the list decodable model and the semi-verified model–and provide strong positive
results for both notions. Our results have implications in a variety of domains, including building secure
machine learning systems, performing robust statistics in the presence of outliers, and agnostically learning
mixture models.
The goal of accurate robust estimation appears at first glance to be impossible if the fraction α of real
data is less than one half. Indeed, in the α = 12 case, it is possible that the real and fake data are distributed
identically, except that the mean of the fake data is shifted by some large amount; in such a case, it is clearly
impossible to differentiate which of these two distributions is “right”. Perhaps, however, such symmetries
are the only real problem that can occur. It might then be possible to output a short list of possible parameter
sets–if α = 12 , perhaps a list of two parameter sets–such that at least one is accurate. To this end, we consider
a notion of successful learning called list decodable learning, first introduced by Balcan et al. (2008). In
analogy with list decodable coding theory, the goal is for the learning algorithm to output a short list of
possible hypotheses.
Definition (List Decodable Learning). We say that a learning, estimation, or optimization problem is (m, ǫ)
list decodably solvable if an efficient algorithm can output a set of at most m hypotheses/estimates/answers,
with the guarantee that at least one is accurate to within error ǫ.
A central question in this paper concerns which learning problems can be robustly solved in the above sense:
To what extent are learning problems robustly solvable in the list decodable sense? If the dataset
consists of only an α-fraction of real data, in what settings is it possible to efficiently output a
list of at most α1 or poly( α1 ) parameter sets or estimates with the guarantee that at least one
closely approximates the solution that could be obtained if one were given only honest data?
The intuition for why strong positive results are obtainable in the list decodable setting is the following.
Given a dataset with an α fraction of trusted data, the remaining data might do one of two things: either it
can be fairly similar to the good data, in which case it can bias the overall answers by only a small amount, or
the adversarial data may be very different from the trusted data. The key is that if a portion of the untrusted
data tries too hard to bias the final result, then it will end up looking quite different, and can be clustered
out. Given this viewpoint, the question of robust learning in the list decodable model becomes a question of
the extent to which an adversary can completely obscure the inherent structure possessed by a dataset drawn
from a well-behaved distribution.
Our investigation of robust learning has three motivations. First, from a theoretical perspective, it is
natural to ask what guarantees are possible in the setting in which a majority of data is untrusted (α < 21 ).
Is it the case that learning really becomes impossible (as is often stated), or can one at least narrow down
the possible answers to a small set? Second, in many practical settings, there is a trade-off between the
amount of data one can collect, and the quality of the data. For a fixed price, one might be able to collect
1

either a small and accurate/trusted dataset, or a large but less trusted dataset. It is worth understanding how
the quality of models derived from such datasets varies, across this entire range of dataset quality/quantity.
Finally, robust learning with α ≪ 1 provides a new perspective on learning mixtures of distributions—by
treating a single mixture component as the real data, and the remaining components as fake data, we can ask
to what extent a mixture component can be learned, independently of the structure of the other components.
While this perspective may seem to give up too much, we will show, somewhat surprisingly, that it is possible
to learn mixtures almost as well under these adversarial assumptions as under stochastic assumptions.
Semi-Verified Learning. When α ≤ 12 , the list decodable model handles symmetries by allowing the
learner to output multiple possible answers; an alternative is to break these symmetries with a small amount
of side information. In particular, in many practical settings it is possible to obtain a (sometimes extremely
small) verified set of data that has been carefully checked, which could be used to determine which of multiple alternative answers is correct. This motivates us to introduce the following new notion of learnability:
Definition (The Semi-Verified Model). In the semi-verified model, we observe n data points, of which an
unknown αn are “real” data reflecting an underlying distribution p∗ , and the remaining (1 − α)n points are
arbitrary. Furthermore, we observe k “verified” data points that are guaranteed to be drawn from p∗ .
The definition of the semi-verified model is inspired by the semi-supervised model of learning (see e.g.
Chapelle et al. (2006)). In semi-supervised learning, one is concerned with a prediction/labeling task, and
has access to a large amount of unlabeled data together with a small amount of labeled data; the central
question is whether the presence of the unlabeled data can reduce the amount of labeled data required to
learn. Analogously, in our robust learning setting, we are asking whether the presence of a large amount of
untrusted data can reduce the amount of trusted data required for learning. Clearly the answer is “no” if we
make no assumptions on the untrusted data. Nevertheless, the assumption that a significant fraction of that
data is drawn from p∗ seems plausible, and may be sufficient to achieve strong positive results. We therefore
ask:
To what extent can the availability of a modest amount of “verified” data facilitate (either
computationally or information theoretically) the extraction of the information contained in the
larger but untrusted dataset? What learning tasks can be performed in the above semi-verified
setting given k ≪ n verified data points? How does the amount k of verified data that is needed
vary with the setting, the fraction α of honest data, etc.?
The above definition and associated questions reflect challenges faced in a number of practical settings,
particularly those involving large crowdsourced datasets, or datasets obtained from unreliable sensors or
devices. In such settings, despite the unreliability of the data, it is often possible to obtain a small verified
dataset that has been carefully checked. Given its pervasiveness, it is somewhat surprising that neither
the theory nor the machine learning communities have formalized this model; we think it is important to
develop an understanding of the algorithmic possibilities in this domain. Obtaining theoretical guarantees
seems especially important for designing provably secure learning systems that are guaranteed to perform
well even if an adversary obtains control over some of the training data used by the algorithm.
Relationships between the models. The semi-verified and list decodable models can be reduced to each
other. Informally, given m candidate outputs from a list decodable algorithm, we expect to be able to
distinguish between them with O (log(m))verified data points. Conversely, if a model is learnable with k
verified points then we can output O ( α1 )k candidate parameters in the list decodable setting (since if we
2

sample that many k-tuples from the untrusted data, at least one is likely to contain only honest data). For
simplicity we state most results in the list decodable model.
Our contributions. We provide results on robust learnability in a general stochastic optimization setting,
where we observe convex functions f1 , . . . , fn of which αn are sampled from p∗ , and want to minimize the
population mean f¯ = Ep∗ [f ].1 Our results are given in terms of a spectral norm bound on the gradients ∇fi .
Therefore, we obtain robustness in any setting where we can establish a matrix concentration inequality
on the good data — for instance, if the ∇fi are sub-Gaussian and Lipschitz, or sometimes even with only
bounded second moments.
From our general results (discussed in detail in the next section), we immediately obtain corollaries in
specific settings, starting with mean estimation:
• Robust mean estimation: When α > 21 we can robustly estimate the mean of a distribution p∗ to ℓ2
error O (σ), where σ 2 is a bound on the second moments of p
p∗ . For α bounded away from 1, this improves upon existing work, which achieves error either O(σ log(d)) under a 4th moment bound on
p∗ (Lai et al., 2016) or matches our rate of O (σ) but assumes p∗ is sub-Gaussian (Diakonikolas et al.,
√
2016). For α ≤ 21 , which was previously unexplored, we can estimate the mean to error Õ (σ/ α).
Since our results hold for any stochastic optimization problem, we can also study density estimation, by
taking fi to be the negative log-likelihood:

• Robust density estimation: Given an exponential family model pθ (x) ∝ exp θ ⊤ φ(x) , we can find
a distribution pθ with KL (pθ∗ k pθ ) ≤ O( √σrα ), where Covpθ∗ [φ(x)]  σ 2 I and r = kθ ∗ k2 .
While density estimation could be reduced to mean estimation (via estimating the sufficient statistics), our
analysis applies directly, to an algorithm that can be interpreted as approximately maximizing the log likelihood while removing outliers.
In the list decodable setting, our results also yield bounds for learning mixtures:
• Learning mixture models: Given a mixture of k distributions each with covariance bounded by σ 2 ,
and with minimum mixture weight α, we can accurately cluster the points if the means are separated
√
by a distance Ω̃ (σ/ α), even in the presence of additional adversarial data. For comparison, even
√
with few/no bad data points, the best efficient clustering algorithms require mean separation Ω̃(σ k)
(Awasthi and Sheffet, 2012; Achlioptas and McSherry, 2005), which our rate matches if α = Ω( k1 ).
• Planted partition models: In the planted partition model, we can approximately recover the planted
partition if the average degree is Ω̃(1/α3 ), where αn is the size of the smallest piece of the partition.
The best computationally efficient result (which assumes all the data is real) requires the degree to be
Ω(1/α2 ) (Abbe and Sandon, 2015a;b).
It is fairly surprising that, despite making no assumptions on the structure of the data outside of a mixture
component, we nearly match the best computationally efficient results that fully leverage this structure. This
suggests that there may be a connection between robustness and computation: perhaps the computational
threshold for recovering a planted structure in random data (such as a geometric cluster or a high-density
subgraph) matches the robustness threshold for recovering that structure in the presence of an adversary.
1

Typically, we actually observe data points xi , and fi is the loss function corresponding to xi .

3

Technical highlights. Beyond our main results, we develop certain technical machinery that may be of
broader interest. Perhaps the most relevant is a novel matrix concentration inequality, based on ideas from
spectral graph sparsification (Batson et al., 2012), which holds assuming only bounded second moments:2
2
Proposition 1.1. Suppose that p is a distribution on Rd with Ep [X]
 = µ and Covp [X]  σ I for some σ.
n
Then, given n ≥ dsamples from p, with probability
 1 − exp − 64 there is a subset I ⊆ [n] of size at least
1 P
n
⊤
≤ 24σ 2 , where λmax denotes the maximum eigenvalue.
i∈I (xi − µ)(xi − µ)
2 such that λmax |I|

This result is strong in the following sense: if one instead uses all n samples xi , the classical result
of Rudelson (1999) only bounds the maximum eigenvalue by roughly σ 2 log(n), and even then only in
expectation. Even under stronger assumptions, one often needs either at least d log(d) samples, or incurs a log(d) factor in the bound on λmax . In the planted partition model, this log factor causes natural
spectral approaches to fail on sparse graphs, and avoiding the log factor has been a topic of recent interest (Guédon and Vershynin, 2014; Le et al., 2015; Rebrova and Tikhomirov, 2015; Rebrova and Vershynin,
2016).
Proposition 1.1 says that the undesirable log factor only arises due to a manageable fraction of bad
samples, which when removed give us sharper concentration. Our framework allows us to exploit this by
defining the good data to be the (unknown) set I for which the conclusion of Proposition 1.1 holds. One
consequence is that we are able to recover planted partitions in sparse graphs essentially “for free”.
Separately, we introduce a novel regularizer based on minimum trace ellipsoids. This regularizer allows
us to control the spectral properties of the model parameters at multiple scales simultaneously, and yields
tighter bounds than standard trace norm regularization. We define the regularizer in Section 3, and prove a
local Hölder’s inequality (Lemma 5.1), which exploits this regularization to achieve concentration bounds
solely from deterministic spectral information.
We also employ padded decompositions, a space partitioning technique from the metric embedding
literature (Fakcharoenphol et al., 2003). Their use is the following: when the loss functions are strongly
convex, we can improve our bounds by identifying clusters in the data, and re-running our main algorithm
on each cluster. Padded decompositions help us because they can identify clusters even if the remaining data
has arbitrary structure. Our clustering scheme is described in Section 6.

Related work. The work closest to ours is Lai et al. (2016) and Diakonikolas et al. (2016), who study
high-dimensional estimation in the presence of adversarial corruptions. They focus on the regime α ≈ 1,
while our work focuses on α ≪ 1. In the overlap of these regimes (e.g. for α = 34 ) our results improve
upon these existing results. (The existing bounds are better as α → 1, but do not hold at all if α ≤ 12 .)
The popular robust PCA algorithm (Candès et al., 2011; Chandrasekaran et al., 2011) allows for a constant
fraction of the entries to be arbitrarily corrupted, but assumes the locations of these entries are sufficiently
evenly distributed. However, Xu et al. (2010) give a version of PCA that is robust to arbitrary adversaries
if α > 12 . Bhatia et al. (2015) study linear regression in the presence of adversaries, and obtain bounds
64
) when the design matrix is subset strong convex. Klivans et al. (2009)
for sufficiently large α (say α ≥ 65
and Awasthi et al. (2014) provide strong bounds for robust classification in high dimensions for isotropic
log-concave distributions.
The only works we are aware of that achieve general adversarial guarantees when α ≤ 12 are Hardt and Moitra
(2013), who study robust subspace recovery in the presence of a large fraction of outliers, and Steinhardt et al.
(2016), which is an early version of this work that focuses on community detection.
2

Since the writing of this paper, we were able to prove a stronger version of Proposition 1.1 that requires only bounded first
moments.

4

Balcan et al. (2008) introduce the list-decodable learning model, which was later studied by others, e.g.
Balcan et al. (2009) and Kushagra et al. (2016). That work provides bounds for clustering in the presence
of some adversarial data, but has two limitations relative to our results (apart from being in a somewhat
different setting): the fraction of adversaries tolerated is small (O( k1 )), and the bounds are not meaningful
O(k/γ 2 ) hypotheses, where γ typically scales
in high
√ dimensions (e.g. Balcan et al. (2008) output a list of k
as 1/ d).
Kumar and Kannan (2010) and the follow-up work of Awasthi and Sheffet (2012) find deterministic
conditions under which efficient k-means clustering is possible, even in high dimensions. While the goal
is different from ours, their condition is similar to the quantities appearing in our error bounds, and there is
some overlap in techniques. They also obtain bounds in the presence of adversaries, but only if the fraction
of adversaries is smaller than k1 as in Balcan et al. (2008). Our corollaries for learning mixtures can be
thought of as extending this line of work, by providing deterministic conditions under which clustering is
possible even in the presence of a large fraction of adversarial data.
Separately, there has been considerable interest in semi-random graph models (Blum and Spencer, 1995;
Feige and Krauthgamer, 2000; Feige and Kilian, 2001; Coja-Oghlan, 2004; Krivelevich and Vilenchik, 2006;
Coja-Oghlan, 2007; Makarychev et al., 2012; Chen et al., 2014b; Guédon and Vershynin, 2014; Moitra et al.,
2015; Agarwal et al., 2015) and robust community detection (Kumar and Kannan, 2010; Moitra et al., 2015;
Makarychev et al., 2015; Cai and Li, 2015). In these models, a random graph is generated with a planted
structure (such as a planted clique or partition) and adversaries are then allowed to modify some parts of this
structure. Typically, the adversary is constrained to only modify o(n) nodes or to only modify the graph in
restricted ways, though some of the above work considers substantially stronger adversaries as well.
Robust learning is interesting from not just an information-theoretic but also a computational perspective.
Guruswami and Raghavendra (2009) and Feldman et al. (2009) show that learning half-spaces is NP-hard
for any α < 1, while Hardt and Moitra (2013) show that learning k-dimensional subspaces in Rd is hard if
α < kd . More generally, algorithms for list decodable learning imply algorithms for learning mixture models,
e.g. planted partitions or mixtures of sub-Gaussian distributions, which is thought to be computationally
hard in at least some regimes.
Finally, there is a large literature on learning in the presence of errors, spanning multiple communities including learning theory (Kearns and Li, 1993) and statistics (Tukey, 1960). We refer the reader to
Huber and Ronchetti (2009) and Hampel et al. (2011) for some recent surveys.
Comparison of techniques. We pause to explain how our techniques relate to those of other recent robust
learning papers by Diakonikolas et al. (2016) and Lai et al. (2016). At a high level, our algorithm works by
solving a convex optimization problem whose objective value will be low if all of the data come from p∗ ;
then, if the objective is high, by looking at the dual we can identify which points are responsible for the high
objective value and remove them as outliers.
In contrast, Diakonikolas et al. (2016) solve a convex feasibility problem, where the feasible set depends
on the true distribution p∗ and hence is not observable. Nevertheless, they show that given a point that
is far from feasible, it is possible to provide a separating hyperplane demonstrating infeasibility. Roughly
speaking, then, we solve a “tainted” optimization problem and clean up errors after the fact, while they
solve a “clean” (but unobserved) optimization problem and show that it is possible to make progress if one
is far from the optimum. The construction of the separation oracle in Diakonikolas et al. (2016) is similar to
the outlier removal step we present here, and it would be interesting to further understand the relationship
between these approaches.
Diakonikolas et al. (2016) also propose another algorithm based on filtering. In the case of mean es5

timation, the basic idea is to compute the maximum eigenvector of the empirical covariance of the data
— if this eigenvector is too large, then we can find a collection of points that are responsible for it being
large, and remove them as outliers. Though it is not phrased this way, it can be thought of–similarly to our
approach–as solving a tainted optimization problem (top eigenvalue on the noisy data) and then cleaning up
outliers afterwards. Their outlier removal step seems tighter than ours, and it would be interesting to find an
approach that obtains such tight bounds for a general class of optimization problems.
Finally, Lai et al. (2016) pursue an approach based on iteratively finding the top n/2 eigenvectors (rather
than just the top) and projecting out the remaining directions of variation, as well as removing outliers if the
eigenvalues are too large. This seems similar in spirit to the filtering approach described above.
Outline. Our paper is organized as follows. In Section 2 we present our main results and some of their
implications in specific settings. In Section 3 we explain our algorithm and provide some intuition for why
it should work. In Section 4 we provide a proof outline for our main results. In Sections 5 and 6, we sharpen
our results, first showing how to obtain concentration inequalities on the errors, and then showing how to
obtain tighter bounds and stronger guarantees for strongly convex losses. In Section 7 we present lower
bounds showing that our results are optimal in some settings. In Section 8 we present some intuition for our
bounds, and in Section 9 we prove our main corollaries. The remaining sections are dedicated to deferred
proofs.
Acknowledgments. We thank the anonymous reviewers who made many helpful comments that improved
this paper. MC was supported by NSF grants CCF-1565581, CCF-1617577, CCF-1302518 and a Simons
Investigator Award. JS was supported by a Fannie & John Hertz Foundation Fellowship, a NSF Graduate
Research Fellowship, and a Future of Life Institute grant. GV was supported by NSF CAREER award
CCF-1351108, a Sloan Foundation Research Fellowship, and a research grant from the Okawa Foundation.

2 Main Results and Implications
We consider a general setting of stochastic optimization with adversaries. We observe convex functions
f1 , . . . , fn : H → R, where H ⊆ Rd is a convex parameter space. For a subset Igood ⊆ [n] of size αn,
i.i.d.

fi ∼ p∗ for i ∈ Igood , and the remaining fi are chosen by an adversary whose strategy can depend on the
fi for i ∈ Igood .
def
Let f¯ denote the mean of f under p∗ , i.e. f¯(w) = Ef ∼p∗ [f (w)] for w ∈ H; our goal is to find a
parameter ŵ such that f¯(ŵ) − f¯(w∗ ) is small, where w∗ is the minimizer of f¯. We use r to denote the
def

ℓ2 -radius of H, i.e. r = maxw∈H kwk2 .
This stochastic optimization setting captures most concrete settings of interest — for instance, mean
estimation corresponds to fi (w) = kw − xi k22 , linear regression to fi (w) = (yi − hw, xi i)2 , and logistic
regression to fi (w) = log(1 + exp(−yi hw, xi i)).

A key player: spectral norm of gradients. To state our main results, we need to define the following key
quantity, where k · kop denotes the spectral or operator norm:
def

S = max p
w∈H

1
|Igood |




∇fi (w) − ∇f¯(w) i∈I
6

good

op

.

(1)

In words, if we form the matrix of gradients [∇fi1 (w) · · · ∇fiαn (w)], where {i1 , . . . , iαn } = Igood , then
S measures the difference between this matrix and its expectation in operator norm, maximized over all
w ∈ H. This will turn out to be a key quantity for understanding learnability in the adversarial setting. It
acts as an analog of uniform
learning theory, where one would instead study the
P convergence in classical
1
¯
quantity maxw∈H k |Igood | i∈Igood (∇fi (w) − ∇f (w))k2 . Note that this latter quantity is always bounded
above by S.
The fact that fi ∼ p∗ is irrelevant to our results—all that matters is the quantity S, which exists even for a
deterministic set of functions f1 , . . . , fn . Furthermore, S only depends on the good data and is independent
of the adversary.
Scaling of S: examples. The definition (1) is a bit complex, so we go over some examples for intuition.
We will see later that for the first two examples below (estimating means and product distributions), our
implied error bounds are “good”, while for the final example (linear classification), our bounds are “bad”.
Mean estimation: Suppose that fi (w) = 12 kw−xi k22 , where xi ∼ N (µ, σ 2 I). Then ∇fi (w)−∇f¯(w) =
xi − µ, and so S is simply the maximum singular value of √ 1 [xi − µ]i∈Igood . This is the square root of
|Igood |
P
1
⊤ , which converges to σ for large n.
(x
−
µ)(x
−
µ)
the maximum eigenvalue of |Igood
i
i∈Igood i
|
d
Product distributions: Suppose that xi is drawn
Pdfrom a product distribution on {0, 1} , where the jth
coordinate is 1 with probability pj . Let fi (w) = j=1 xij log(wj ) + (1 − xij ) log(1 − wj ). In this case
P
f¯(w) = dj=1 pj log(wj ) + (1 − pj ) log(1 − wj ), and wj∗ = pj , so that f¯(w) − f¯(w∗ ) is the KL divergence
between p and w.
The jth coordinate of ∇fi (w) − ∇f¯(w) is (xij − pj )(1/wp
j + 1/(1 − wj )). In particular, the matrix
in the definition of S can be written as D(w) · [xi − p]i∈Igood / |Igood |, where D(w) is a diagonal matrix
with entries 1/wj + 1/(1 − wj ). Suppose that p is balanced, meaning that pj ∈ p
[1/4, 3/4], and that we
restrict wj ∈ [1/4, 3/4] as well. Then kD(w)kop ≤ 16/3, while the matrix [xi − p]/ |Igood | has maximum
singular value converging to maxdj=1 pj (1 − pj ) ≤ 14 for large enough n. Thus S = O(1) in this setting.
Linear classification: Suppose that xi ∼ N (0, I) and that yi = sign(u⊤ xi ) for some unknown vector u. Our loss function is the logistic loss fi (w) = log(1 + exp(−yi hw, xi i)). In this case ∇fi (w) =
− 1+exp(yyii hw,xi i) xi . It is less obvious how to compute S, but Lemma 2.1 below implies that it is O(1).
Sub-gaussian gradients: A useful general bound on S can be obtained assuming that the fi have
sub-Gaussian gradients. Recall that a random variable X is σ-sub-Gaussian if E[exp(u⊤ (X − µ))] ≤
2
exp( σ2 kuk22 ), where µ = E[X]. If ∇fi is sub-Gaussian, then S = O(σ) if αn ≥ Ω̃(d):
Lemma 2.1. If ∇fi (w) − ∇f¯(w) is σ-sub-Gaussian and L-Lipschitz for fi ∼ p∗ , and αn is at least
d max(1, log( rL
σ )) + log(1/δ), then S = O (σ) with probability 1 − δ.
In most of our concrete settings (such as mean estimation), sub-Gaussianity of ∇fi corresponds to subGaussianity of the data points xi ∈ Rd . In some settings we will be able to obtain bounds on S under weaker
(second-moment) conditions, as in Proposition 1.1.

2.1 Main Results
We can now state our main results. Our first result is that, just using the untrusted data, we can output a
small ellipse which contains a parameter attaining small error under f¯. This meta-result leads directly to our
more specific results in the list decoding and semi-verified settings.

7

Theorem 2.2. Given n data points containing a set Igood of αn data points
 with spectral norm bound S, we
r2
⊤
can obtain an ellipse EY = {w | ww  Y } such that tr(Y ) ≤ O α and


Sr
∗
min f¯(w) − f¯(w ) ≤ O √
.
(2)
w∈EY
α
Recall here that r is the ℓ2 -radius of the parameter space H. Also note that when Y is invertible,
 Y is equivalent to w⊤ Y −1 w ≤ 1, so Y really does define an ellipse. Theorem 2.2 shows that the
unverified data is indeed helpful, by narrowing the space of possible parameters from all of H down to the
small ellipse EY .
To interpret the bound (2), consider the mean estimation example above, where fi (w) = 12 kxi − wk22
with xi ∼ N (µ, σ 2 I). Note that f¯(w) − f¯(w∗ ) = 21 kw − µk22 . Assuming that kµk2 is known to within a
constant factor, we can take H to be the ℓ2 -ball of radius r = kµk2 . This leads to the bound kw − µk22 =
√
kµk2
O (σkµk2 / α), for some w in an ellipse of trace α 2 . Note that the ℓ2 -ball itself has trace dkµk22 , so the
ellipse EY is much smaller than H if d is large. Moreover, a random xi ∼ p∗ will have kxi − µk22 ≈ dσ 2 , so
w is much closer to µ than a random draw from p∗ , assuming that kµk2 ≪ dσ.
√
By applying our algorithm
multiple times we can improve the bound kw − µk22 = O (σkµk2 / α) to

kw − µk22 = O σ 2 /α , so that our bounds are meaningful for large d independent of kµk2 . We discuss this
in more detail in Section 6.
For an example where Theorem 2.2 is less meaningful, consider the linear classification example from
√
above. In that case S = O(1), and r is likely also O(1), so we obtain the bound f¯(w) − f¯(w∗ ) = O(1/ α).
However, f¯(0) = log(2) while f¯(w∗ ) ≥ 0, so this bound is essentially vacuous.
ww⊤

List decodable learning. Using Theorem 2.2 as a starting point we can derive bounds for both models
defined in Section 1, starting with the list decodable model. Here, we must make the further assumption that
the fi are κ-strongly convex, meaning that fi (w′ ) − fi (w) ≥ (w′ − w)⊤ ∇fi (w) + κ2 kw′ − wk22 . The strong
convexity allows us to show that for the good fi , the parameters ŵi = arg minw∈EY fi (w) concentrate
around w∗ , with radius r ′ ≪ r. By clustering the ŵi and iteratively re-running our algorithm on each cluster,
we can obtain bounds that do not depend on r, and output a single candidate parameter ŵj for each cluster.
We can thereby show:
Theorem 2.3. Suppose the functions fi are κ-strongly convex, and suppose there is a set Igood of size αn
1
⌋ candidate
with spectral norm bound S. Then, for any ε ≤ 21 , it is possible to obtain a set of m ≤ ⌊ (1−ε)α
 q

2
log( α )
S
∗
parameters ŵ1 , . . . , ŵm , such that minm
.
j=1 kŵj − w k2 ≤ O κ
αε
In Section 6 we state and prove a stronger version of this result. A key tool in establishing Theorem 2.3 is
padded decompositions (Fakcharoenphol et al., 2003), which identify clusters in data while making minimal
assumptions on the geometry of points outside of a cluster, and are thus useful in our adversarial setting.
Semi-verified learning. If the fi are not strongly convex then we cannot employ the clustering ideas above.
However, because we have reduced H to the much smaller set EY , we can nevertheless often approximate
w∗ with only a small amount of verified data. In fact, in some settings we only need a single verified data
point:
Lemma 2.4. Suppose that f (w) = φ(w⊤ x), where φ is 1-Lipschitz, and suppose that x has bounded qth
moments in the sense that Ep∗ [|hx − E[x], ui|q ]1/q ≤ σq for all unit vectors u and some q ≥ 2. Then given Y
8

h
from Theorem 2.2 and a single verified x ∼ p∗ , we can obtain a ŵ such that Px∼p∗ f¯(ŵ) ≥ f¯(w∗ ) + C ·

t−q ,

(S+tσq )r
√
α

for a universal constant C.

The particular functional form for fi was needed to obtain a concrete bound, but analogs of Lemma 2.4
¯
should be possible in any setting where we can leverage the low complexity of EY into
√ a bound on f − f .
r
Note that if we replace EY with H in Lemma 2.4, then the √α dependence becomes r d, which is usually
vacuous.
Optimality? The dependence on S, r and κ in the results above seems essentially necessary, though the
optimal dependence on α is less clear. In Section 7 we show lower bounds for robust mean
p estimation
S
∗
even if p is known to be Gaussian. These bounds roughly translate to a lower bound of Ω κ log (1/α)
p

for strongly convex fi , and Ω Sr log(1/α) for linear fi , and hold in both the list decodable and semip
p
verified settings. It is unclear whether the optimal dependence
p on α is 1/α or log(1/α) or somewhere
between. We do note that any dependence better than 1/α would improve the best known results for
efficiently solving
p k-means for well-separated clusters, which may suggest at least a computational barrier
to achieving log(1/α).

2.2 Implications

We now go over some implications of our general results in some more specific settings. All of the results
below follow as corollaries of our main theorems, and are proved in Section 9.
Robust mean estimation. Suppose we observe points x1 , . . . , xn ∈ Rd , of which αn are drawn from
a distribution p∗ with bounded covariance, and our goal is to recover the mean µ = Ex∼p∗ [x]. If we take
fi (w) = kw−xi k22 , then Theorem 2.3, together with the matrix concentration bound Proposition 1.1, implies
the following result:
Corollary 2.5. Suppose that p∗ has bounded covariance: Covp∗[x]  σ 2 I. Then, for n ≥ αd , with probability 1 − exp (−Ω(αn)) it is possible to output m ≤ O α1 candidate means µ̂1 , . . . , µ̂m such that
 q

log(2/α)
minm
kµ
−
µ̂
k
≤
O
σ
. Moreover, if α ≥ 0.51 then we can take m = 1.
j 2
j=1
α

We can compare to the results of Lai et al. (2016) and Diakonikolas et al. (2016), who study mean estimation when α > 12 and one is required to output a single parameter (i.e., m = 1). For simplicity take
p
α = 34 . Roughly, Lai et al. (2016) obtain error O(σ log(d)) with sample complexity n = O (d), while
requiring a bound on the
of p∗ ; Diakonikolas et al. (2016) obtain error O (σ) with sample
 fourth moments
3
∗
complexity n = O d , and require p to be Gaussian. Corollary 2.5 improves both of these by yielding
error O (σ) with sample complexity n = O (d), and only requires p∗ to have bounded second moments.3
We note that in contrast to our results, these other results obtain error that vanishes as α → 1 (at a rate of
e − α) in the second case). We thus appear to incur some looseness when
(1 − α)1/2 in the first case and O(1
α ≈ 1, in exchange for obtaining results in the previously unexplored setting α ≤ 21 . It would be interesting
to obtain a single algorithm that both applies when α ≪ 1 and achieves vanishing error as α → 1.
3

Some fine print: Diakonikolas et al. also estimate the covariance matrix, and their recovery results are stronger if Σ = Cov[x]
is highly skewed; they roughly show kµ̂ − µkΣ−1 = O(1). The adversary model considered in both of these other papers is also
slightly more general than ours: first n points are drawn from p∗ and then an adversary is allowed to corrupt (1 − α)n of the points.
√
However, it is straightforward to show (by monotonicity of the operator norm) that our bounds will be worse by at most a 1/ α
3
factor in this stricter setting, which is a constant if α = 4 .

9

i

≤

Learning mixture of distributions. In addition to robust mean estimation, we can use our results to
efficiently learn mixtures of distributions, by thinking of a single mixture component as the good data and the
remaining mixture components as bad data. Again applying Theorem 2.2 to fi (w) = kw − xi k22 , we obtain
the following result, which says that we can successfully cluster samples from a mixture of distributions,
even in the presence of arbitrary corruptions, provided the cluster means are separated in ℓ2 distance by
√
Ω̃(σ/ α).
Corollary 2.6. Suppose we are given n samples, where each sample either comes from one of k distributions
p∗1 , . . . , p∗k (with Covp∗i [x]  σ 2 I for all i), or is arbitrary. Let µi be the mean of p∗i , let αi be the fraction
of points from p∗i , and let α = minki=1 αi . Then if n ≥ αd , with probability 1 − k exp(−Ω(αε2 n)) we can
obtain a partition T1 , . . . , Tm of [n] and corresponding candidate means µ̂1 , . . . , µ̂m such that: for all but
∗
εα
i n of
 drawn from pi , the point is assigned a set Tj and candidate mean µ̂j with kµi − µ̂j k2 ≤
qthe points
2

log( α )
1
O σε
.
Moreover,
m
≤
O
α
α .

p
p
The 1ε dependence can be replaced with log(n)/ε, or with log(2/ε) if the xi are sub-Gaussian. The
only difference is in which matrix
concentration bound we apply to the xi . Corollary 2.6 says that we can

partition the points into O α1 sets, such that two points from well-separated clusters are unlikely to end
up in the same set. Note however that one cluster might be partitioned into multiple sets. In the adversarial
setting, this seems unavoidable, since an adversary could create a fake cluster very close to a real cluster,
and one would be forced to either combine the clusters or risk splitting the real cluster in two.
For comparison, the best computationally efficient algorithm for clustering
a mixture of k distribu√
tions (with few/no corruptions) requires mean separation roughly Õ(σ k) (Awasthi and Sheffet, 2012;
Achlioptas and McSherry, 2005), which our result matches if α = Ω(1/k).
Planted partitions. We next consider implications of our results in a version of the planted partition
model (McSherry, 2001). In this model we observe a random directed graph, represented as a matrix A ∈
{0, 1}n×n . For disjoint subsets I1 , . . . , Ik of [n], we generate edges as follows: (i) If u, v ∈ Ii , then
p(Auv = 1) = na . (ii) If u ∈ Ii , v 6∈ Ii , then p(Auv = 1) = nb . (iii) If u 6∈ ∪ki=1 Ii , the edges emanating from
u can be arbitrary. In contrast to the typical planted partition model, we allow some number of corrupted
vertices not belonging to any of the Ii . In general a and b could depend on the partition indices i, j, but we
omit this for simplicity.
Note that the distribution over the row Au is the same for all u ∈ Ii . By taking this distribution to be the
distribution p∗ , Theorem 2.3 yields the following result:
Corollary 2.7. For the planted partition model above, let α = minki=1 |Ini | . Then, with probability 1 −
exp(−Ω(αn)), we can obtain sets T1 , . . . , Tm ⊆ [n], with m ≤ O α1 , such that for all i ∈ [k], there is a

2 
)
a log( α
n, where △ denotes symmetric difference.
j ∈ [m] with |Ii △Tj | ≤ O α2 (a−b)
2

This shows that we can approximately recover the planted partition, even in the presence of arbitrary
2
≫ log(2/α)
corruptions, provided (a−b)
(since the bound on |Ii △Tj | needs to be less than αn to be meana
α3
2

(a−b)
ingful). In contrast, the best efficient methods (assuming no corruptions) roughly require a+(k−1)b
≫ k
in the case of k equal-sized communities (Abbe and Sandon, 2015a;b). In the simplifying setting where
b = 12 a, our bounds require a ≫ k3 log(k) while existing bounds require a ≫ k2 . The case of unequal size
in contrast to a ≫ α12 .
communities is more complex, but roughly, our bounds require a ≫ log(2/α)
α3

10

Summary. For robust mean estimation, we match the best existing error bounds of O (σ) when α = 34 ,
√
under weaker assumptions. For learning mixtures distributions, we match the best bound of Õ(σ k) when
α = Ω(1/k). For recovering planted partitions, we require average degree k3 log(k), in contrast to the best
known bound of k2 . It is pleasing that a single meta-algorithm is capable of matching or nearly matching
the best rate in these settings, despite allowing for arbitrary corruptions. We can also achieve bounds for
robust density estimation, presented in Section 9.

3 Algorithm
In this section we present our algorithm, which consists of an SDP coupled with an outlier removal step. At
a high level,
Pour algorithm works as follows: first, we give each function fi its own parameter vector wi , and
minimize ni=1 fi (wi ) subject to regularization which ensures the wi remain close to each other; formally,
we bound the wi to lie within a small ellipse. The reason for doing this is that the different wi are now only
coupled via this regularization, and so the influence of adversarial data on the good parameters can only
come from its effect on the shape of the ellipse. We will show that whenever the adversaries affect the shape
of the ellipse more than a small amount, they are necessarily outliers that can be identified and removed.
In the remainder of this section, we elaborate on these two steps of regularization and outlier removal, and
provide pseudocode.
Per-function adaptivity. If the functions f1 , . . . , fn were all drawn
p∗ (i.e., there are no adversaries),
Pfrom
n
then a natural approach would be to let ŵ be the minimizer of i=1 fi (w), which will approximately
minimize f¯(w) by standard concentration results.
The problem with using this approach in the adversarial setting is that even a single adversarially chosen
function fi could substantiallyPaffect the value of ŵ. To minimize this influence, we give each fi its own
parameter wi , and minimize ni=1 fi (wi ), subject to a regularizer which encourages the wi to be close
together. The adversary now has no influence on the good wi except via the regularizer, so the key challenge
Algorithm 1 Algorithm for fitting p∗
Input: f1 , . . . , fn
Initialize √
c ← [1; · · · ; 1] ∈ Rn
3: Set λ ← 8αnS
r
4: while true do
5:
Let ŵ1:n , Ŷ be the solution to
1:

2:

minimize

w1 ,...,wn ,Y

6:
7:
8:
9:
10:
11:

6r 2

n
X

ci fi (wi ) + λ tr(Y )

i=1

subject to wi wi⊤  Y for all i = 1, . . . , n.

(3)
⊲ Check for outliers
⊲ Not many outliers, can return

if tr(Ŷ ) ≤ α then
return ŵ1:n , Ŷ
else
c ← U PDATE W EIGHTS (c, ŵ1:n , Ŷ )
end if
end while

⊲ Re-weight points to down-weight outliers

11

is to find a regularizer which sufficiently controls statistical error while also bounding the influence of the
adversary.
It turns out that the right choice of regularizer in this case is to constrain the wi to lie within an ellipse
with small trace. Formally, the centerpiece of our algorithm is the following convex optimization problem:
minimize

w1 ,...,wn ,Y

n
X

ci fi (wi ) + λ tr(Y )

i=1

subject to wi wi⊤  Y for all i = 1, . . . , n.

(4)

Here the coefficients ci are non-negative weights which will eventually be used to downweight outliers (for
⊤
now
it is fine

 to imagine that ci = 1). Note that wi wi  Y is equivalent to the semidefinite constraint
Y wi
 0. The problem (4) can be solved in polynomial time in n and d assuming oracle access to
wi⊤ 1
the gradients ∇fi .
Note that the semidefinite constraint wi wi⊤  Y is equivalent to wi⊤ Y −1 wi ≤ 1, which says that wi
lies within the ellipse centered at 0 defined by Y . The regularizer is thus the trace of the minimum ellipse
containing the wi ; penalizing this trace will tend to push the wi closer together, but is there any intuition
behind its geometry? The following lemma shows that tr(Y ) is related to the trace norm of [w1 · · · wn ]:
Lemma 3.1. For any points w1 , . . . , wn ∈ Rd , suppose that Y  wi wi⊤ for all i. Then, letting k · k∗
2
denote the trace norm (i.e., sum of singular values) and WT = [wi ]i∈T , we have tr(Y ) ≥ kW|TT|k∗ for all sets
T ⊆ [n].
The appearance of the trace norm makes sense in light of the intuition that we should be clustering the
functions fi ; indeed, trace norm regularization is a key ingredient in spectral algorithms for clustering (see
e.g. Zha et al. (2001); Chen et al. (2014a;b)). Lemma 3.1 says that tr(Y ) simultaneously bounds the trace
norm on every subset T of [n], which ends up yielding better results than are obtained by simply penalizing
the overall trace norm; we believe that this local trace norm regularization likely leads to better results even
in non-adversarial spectral learning settings. The most important property of tr(Y ) is that it admits a certain
type of local Hölder’s inequality which we will explain in Section 5.
Removing outliers. Solving (4) is not by itself sufficient to achieve robustness. The problem is that a
single function fi could strongly push wi to a given value wtarget (e.g. if fi (w) = 10100 kw − wtarget k22 )
which allows the adversaries to arbitrarily expand the ellipse defined by Y . To combat this, we need some
way of removing outlier functions fi from our dataset. We will do this in a soft way, by assigning a weight
ci to each function fi , and downweighting functions that seem likely to be outliers.
How can we tell that a function is an outlier? Intuitively, if a function fi is really drawn from p∗ , then
there should be many other functions fj , j 6= i, that are “similar” to fi . We can quantify this by considering
whether there are a large number of j 6= i for which the parameter wj for fj does a good job of minimizing
fi . Formally, given a solution (ŵ1 , . . . , ŵn ) to (4), we compare ŵi to w̃i , which is defined as the solution to
the following optimization:
minimize fi (w̃i )

w̃i ,ai1 ,...,ain

subject to w̃i =

n
X
j=1

aij ŵj ,

0 ≤ aij ≤

12

2
,
αn

n
X
j=1

aij = 1.

(6)

The optimization (6) roughly asks for a parameter w̃i that minimizes fi , subject to w̃i being the average
of at least αn
2 distinct parameters ŵj . Given the solution w̃i to (6), we then downweight the influence of
the ith data point based on the value of fi (w̃i ) − fi (ŵi ). In particular, we will multiply the weight ci by
1 − η (fi (w̃i ) − fi (ŵi )) for some appropriate η. Hopefully, this will downweight any outliers by a large
amount while only downweighting good points by a small amount (this hope is verified in Lemma 4.5
below).
Pseudocode for our algorithm is given in Algorithms 1 and 2.

4 Approach and Proof Outline
We now provide an outline of the proof of Theorem 2.2, by analyzing the output of Algorithm 1. The structure of our proof has analogies to classical uniform convergence arguments, so we will start by reviewing
that case.
Warm-up: Uniform Convergence
In uniform convergence arguments, we assume that all of f1 , . . . , fn are drawn from p∗ , which brings us into
the realm of classical learning theory. The analogue to the optimization (3) in Algorithm 1 is regularized
empirical risk minimization:
n
X
ŵ = arg min
fi (w) + λh(w),
(7)
w∈H

i=1

where h(w) is a non-negative regularizer. Uniform convergence arguments involve two parts:
P
P
1. Bound the optimization error: Use the definition of ŵ to conclude that ni=1 fi (ŵ) ≤ ni=1 fi (w∗ )+
λh(w∗ ) (since P
ŵ minimizes (7)). This step shows that ŵ does almost as well as w∗ at minimizing the
empirical risk ni=1 fi (w).
P
2. Bound the statistical error: Show, via an appropriate concentration inequality, that n1 ni=1 fi (w) is
close to f¯(w) for all w ∈ H. Therefore, ŵ is nearly as good as w∗ in terms of the true risk f¯.
Algorithm 2 Algorithm for updating weights c to downweight outliers.
procedure U PDATE W EIGHTS(c, ŵ1:n , Ŷ )
for i = 1, . . . , n do
3:
Let w̃i be the solution to

1:

2:

minimize fi (w̃i )

w̃i ,ai1 ,...,ain

subject to w̃i =

n
X

0 ≤ aij ≤

aij ŵj ,

j=1

4:
5:
6:
7:
8:
9:

Let zi ← fi (w̃i ) − fi (ŵi )
end for
zmax ← max{zi | ci 6= 0}
−zi
c′i ← ci · zmax
zmax for i = 1, . . . , n
return c′
end procedure

13

2
,
αn

n
X
j=1

aij = 1.

(5)

We will see next that the proof of Theorem 2.2 contains steps similar to these, though bounding the statistical
error in the presence of adversaries requires an additional step of removing outliers.
Proof Overview
We will establish a stronger version of Theorem 2.2, which exhibits an explicit w ∈ EŶ with small error:
 P

P
Theorem 4.1. Let ŵ1:n , Ŷ be the output of Algorithm 1, and let ŵavg =
i∈Igood ci ŵi /
i∈Igood ci .
2
Sr
. Furthermore, ŵavg ∈ EŶ and tr(Ŷ ) ≤ 6rα .
Then, f¯(ŵavg ) − f¯(w∗ ) ≤ 18 √
α
To prove Theorem 4.1, recall that Algorithm 1 has at its core the following optimization problem:
minimize

w1 ,...,wn ,Y

n
X

ci fi (wi ) + λ tr(Y )

i=1

subject to wi wi⊤  Y for all i = 1, . . . , n.
(8)
Pn
This optimization asks to minimize i=1 ci fi (wi ) while constraining the wi to lie within the ellipse defined
by Y . As in the uniform
Perror that we need to bound: 
Pconvergence argument above, there are two sources of
the optimization error i∈Igood ci (fi (ŵi ) − fi (w∗ )), and the statistical error i∈Igood ci f¯(ŵavg ) − fi (ŵi ) .
Note that the statistical error now measures two quantities: the distance from fi (ŵi ) to fi (ŵavg ), and from
fi (ŵavg ) to f¯(ŵavg ).
Bounding the optimization error requires showing that the ellipse defined by Ŷ is not too small (so that
it contains w∗ ), while bounding the statistical error requires showing that the ellipse is not too large (so that
we cannot overfit too much). The former turns out to be easy and is shown in Lemma 4.2. The latter is more
involved and requires several steps. First, we show in Lemma 4.3 that the statistical error can be bounded
in terms of tr(Y ) and S, which verifies the intuition that bounding the statistical error reduces to bounding
Y . Next, in Lemma 4.4, we show that the parameters w̃i found in Algorithm 2 are bounded by an ellipse Ỹ
with small trace, and that fi (w̃i ) ≈ fi (ŵi ) for i ∈ Igood . By the optimality of (ŵ1:n , Ŷ ) for (8), the only
way that tr(Ŷ ) can be much larger than tr(Ỹ ) is therefore if fi (ŵi ) ≪ fi (w̃i ) for i 6∈ Igood . In this case,
we can identify outliers i 6∈ Igood by considering the value of fi (w̃i ) − fi (ŵi ), and Lemma 4.5 verifies that
we can use this to perform outlier removal. We expand on both the optimization error and statistical error
bounds below.
Bounding optimization error on Igood .
(ŵ1:n , Ŷ ) for (8), which implies that
n
X
i=1

ci fi (ŵi ) + λ tr(Ŷ ) ≤

Throughout the argument, we will make use of the optimality of
n
X

ci fi (wi ) + λ tr(Y ) for any feasible (w1:n , Y ).

(9)

i=1

P
P
ci fi (ŵi ), not just the fi
We wish to bound i∈Igood ci fi (ŵi ), but the preceding bound involves all of ni=1P
for i ∈ Igood . However, because the ŵi are free to vary independently, we can bound i∈Igood ci (fi (ŵi ) − fi (w∗ ))
in terms of the amount that tr(Ŷ ) would need to increase before w∗ (w∗ )⊤  Ŷ . In particular, by taking
Y = Ŷ + (w∗ )(w∗ )⊤ in (9), we can obtain the following bound on the optimization error:
Lemma 4.2. The solution ŵ1:n to (8) satisfies
X
ci (fi (ŵi ) − fi (w∗ )) ≤ λkw∗ k22 .
i∈Igood

14

(10)

Bounding the statistical error. We next consider the statistical error. We cannot bound this error via
standard uniform convergence techniques, because each fi has a different argument ŵi . However, it turns
out that the operator norm bound S, together with a bound on tr(Ŷ ), yield concentration of the fi to f¯. In
particular, we have:
def

Lemma 4.3. Let ŵavg =
X

i∈Igood

P

i∈Igood

P

ci ŵi

i∈Igood

ci

. Then the solution ŵ1:n , Ŷ to (8) satisfies
q

ci (fi (ŵavg ) − fi (ŵi )) ≤ αnS

X

i∈Igood



tr(Ŷ ) + r , and

X

ci f¯(ŵavg ) − f¯(w∗ ) ≤
ci (fi (ŵavg ) − fi (w∗ )) + 2αnrS.

(11)
(12)

i∈Igood

Lemma 4.3 relates fi (ŵi ) to fi (ŵavg ) in (11), and then relates fi (ŵavg ) to f¯(ŵavg ) in (12). Together
these allow us to bound the statistical error in terms of tr(Ŷ ) and S. The proof is an application of the matrix
Hölder’s inequality | tr(A⊤ B)| ≤ kAk∗ kBkop , with Ai = ŵi − ŵavg and Bi = ∇fi (ŵavg ) − ∇f¯(ŵavg ).
Bounding the trace. We next need to bound
P tr(Ŷ ) itself. We again exploit the optimality constraint (9),
which implies that tr(Ŷ ) ≤ tr(Y ) + λ1 ( ni=1 ci (fi (wi ) − fi (ŵi ))) for any feasible (w1:n , Y ). We will
2
take w1:n to be w̃1:n as defined in equation (5) of Algorithm 2; we then take Y to be αn
Ŵ Ŵ ⊤ , where
W = [w1 · · · wn ]. Lemma 4.4 asserts that (w1:n , Y ) is feasible, and uses this to “almost” bound tr(Ŷ ):
def

Lemma 4.4. For w̃i as defined in (6), and Ỹ =
2
tr(Ỹ ) ≤ 2rα . In addition,
1
2r 2
+
tr(Ŷ ) ≤
α
λ
and if

P

i∈Igood ci

≥

αn
2

2
⊤
αn Ŵ Ŵ ,

n
X
i=1

we have w̃i w̃i⊤  Ỹ for all i, and also
!

ci (fi (w̃i ) − fi (ŵi )) ,

(13)

then
X

i∈Igood

ci (fi (w̃i ) − fi (ŵi )) ≤ αn

q



tr(Ŷ ) + r .

(14)

P
This “almost” bounds tr(Ŷ ) in the following sense: if instead of i∈Igood ci (fi (w̃i ) − fi (ŵi )), (14) gave
P
2
a bound on ni=1 ci (fi (w̃i ) − fi (ŵi )), then we could plug in to (13) to obtain (e.g.) tr(Ŷ ) ≤ 2rα +

q
n
tr(
Ŷ
)
+
r
, after which solving the quadratic for tr(Ŷ ) would yield a bound. The problem is that
λ
fi (w̃i ), for i 6∈ Igood , could be arbitrarily large, so additional work is needed.
Outlier removal. This brings us to our final idea of outlier removal. The intuition is the following: let
def
zi = fi (w̃i ) − fi (ŵi ). Then either: (i) the average of zi over all of [n] is not much larger than over
Igood (in which case the bound (14) extends from Igood to [n]), or (ii) the average of zi is much larger on
[n] than on Igood , in which case it should be possible to downweight the points in [n]\Igood a substantial
amount relative to the points in Igood . This is the role that the outlier removal step (Algorithm 2) plays, and
Lemma 4.5 formalizes its effect on the weights ci .
15

P
Lemma 4.5. Suppose that n1 ni=1 ci (fi (w̃i ) − fi (ŵi )) ≥
update step in Algorithm 2 satisfies

2
αn

P

i∈Igood ci

(fi (w̃i ) − fi (ŵi )). Then, the

n
1 X
1 X
ci − c′i ≤
ci − c′i .
αn
2n
i∈Igood

Moreover, the above supposition holds if λ =

(15)

i=1

√
8αnS
r

and tr(Ŷ ) >

6r 2
α .

Lemma 4.5 says that, if the average value of zi is at least twice as large over [n] as over Igood , then the
2
weights ci decrease at most half as quickly on Igood as on [n]. Moreover, this holds whenever tr(Ŷ ) > 6rα .
 2
Lemma 4.5 ensures that eventually we have tr(Ŷ ) ≤ O rα , which allows us to
√
√
bound the overall statistical error (using Lemma 4.3) by O ( αnrS). In addition, since λ = O ( αnS/r),
√
the optimization error is bounded (via Lemma 4.2) by O ( αnrS), as well. Combining the various bounds,
we end up obtaining
 X 


√
(16)
ci f¯ (ŵavg ) − f¯ (w∗ ) ≤ O αnrS .
Combining the results.

i∈Igood

P
Then, since (15) ensures that the ci decrease twice as quickly over [n]
, we decrease i∈Igood ci
P as over Igoodαn
by at
Pmost a factor of 2 over all iterations of the algorithm, so that i∈Igood ci ≥ 2 . Dividing (16) through
by i∈Igood ci then yields Theorem 4.1.
In the remainder of this section, we will prove Lemmas 4.2 through 4.5, then show more formally how
Theorem 4.1 follows from these lemmas.

Proof of Lemma 4.2
P
P
We want to bound i∈Igood ci fi (ŵi ). As noted above, the optimality of (ŵ1:n , Ŷ ) implies that ni=1 ci fi (ŵi )+
P
λ tr(Ŷ ) ≤ ni=1 ci fi (wi ) + λ tr(Y ) for any feasible point w1:n , Y . We will use the particular choice of
 ∗
w : i ∈ Igood
, Y = Ŷ + w∗ (w∗ )⊤ .
(17)
wi =
ŵi : i 6∈ Igood
It is easy to see that this is a feasible point for the optimization: if i ∈ Igood , then wi wi⊤ = w∗ (w∗ )⊤ 
Ŷ + w∗ (w∗ )⊤ , and if i 6∈ Igood then wi wi⊤ = ŵi ŵi⊤  Ŷ  Ŷ + w∗ (w∗ )⊤ . Therefore, we have
n
X
i=1

ci fi (ŵi ) + λ tr(Ŷ ) ≤

Re-arranging yields

P

ci fi (w∗ ) +

i∈Igood

i∈Igood ci fi (ŵi )

Proof of Lemma 4.3

X

≤

P

X



ci fi (ŵi ) + λ tr(Ŷ ) + kw∗ k22 .

∗) +

λkw∗ k22 , as was to be shown.

i6∈Igood
i∈Igood ci fi (w

(18)

First, by using Hölder’s inequality tr(A⊤ B) ≤ kAkop kBk∗ , we can show the following:
Lemma 4.6. For any w0 and any w1:n satisfying wi wi⊤  Y for all i, we have
X
p
ci h∇fi (w0 ) − ∇f¯(w0 ), wi i ≤ αn tr(Y )S.
i∈Igood

16

(19)

To establish (11) from Lemma 4.6, note that
X

i∈Igood

(i)

ci (fi (ŵavg ) − fi (ŵi )) ≤

X

i∈Igood

(ii)

X

=

ci h∇fi (ŵavg ), ŵavg − ŵi i

(20)

ci h∇fi (ŵavg ) − ∇f¯(ŵavg ), ŵavg − ŵi i

(21)

i∈Igood
(iii)

≤ αn

q

tr(Ŷ ) + r

2



S,

(22)

where (i) is by convexity of fi , (ii) is because
X
X
ci h∇f¯(ŵavg ), ŵavg − ŵi i = h∇f¯(ŵavg ),
ci (ŵavg − ŵi )i
i∈Igood

i∈Igood

= 0,

⊤ ) and (w , Y ) = (ŵ , Ŷ ).
and (iii) is two applications of Lemma 4.6, with (wi , Y ) = (ŵavg , ŵavg ŵavg
i
i
∗
¯
¯
To establish (12), we expand f (ŵavg ) − f (w ) as an integral; letting w(t) = tŵavg + (1 − t)w∗ , we
have
Z 1 X
X

∗
¯
¯
ci h∇f¯(w(t)), ŵavg − w∗ idt
(23)
ci f (ŵavg ) − f (w ) =
i∈Igood

=

0 i∈I
good
1 X

Z

ci h∇fi (w(t)), ŵavg
0 i∈I
good
Z 1 X

+
Z
(iv)
≤

0 i∈I
good

1

X

0 i∈I
good

=

X

i∈Igood

− w∗ idt

(24)

ci h∇f¯(w(t)) − ∇fi (w(t)), ŵavg − w∗ idt

ci h∇fi (w(t)), ŵavg − w∗ idt +
!

ci (fi (ŵavg ) − fi (w∗ ))

Z

+ 2αnrS,

1

2αnrSdt

(25)

0

(26)

as claimed. Here (iv) invokes Lemma 4.6 at w0 = w(t), wi = ŵavg − w∗ , Y = (ŵavg − w∗ )(ŵavg − w∗ )⊤ .

17

Proof of Lemma 4.4
P
Let w̃i = nj=1 aij ŵj as in (5). We have



⊤
n
n
X
X
aij ŵj  
aij ŵj 
w̃i w̃i⊤ = 
j=1

(i)



n
X

aij ŵj ŵj⊤

j=1
n
(ii) X



=

j=1

(27)

j=1

(28)

2
ŵj ŵj⊤
αn

(29)

2
Ŵ Ŵ ⊤ = Ỹ .
αn

(30)

2
Here (ii) P
is because aij ≤ αn
, while (i) is an instantiation of the inequality E[x]E[x]⊤  E[xx⊤ ] (using the
fact that j aij = 1). This completes the first claim.
2

2
2
2
Next, tr(Ỹ ) = αn
tr(Ŵ Ŵ ⊤ ) = αn
kŴ k2F ≤ αn
· nr 2 = 2rα . This completes the second claim. The
inequality (13) then follows from (9), by optimality of (ŵ1:n , Ŷ ) and feasibility
 ).
 of (w̃1:n , Ỹ
P
c
c
j
j
P
ŵj is a feasible
, we see that ŵavg =
Finally, by taking aij = P ′
j∈Igood
j ∈Igood cj ′
j ′ ∈Igood cj ′
P
2
point for w̃i (note that aij ≤ αn
, since cj ≤ 1 and j ′ ∈Igood cj ′ ≥ αn
assumption). We therefore have
2 byP
fi (w̃i ) ≤ fi (ŵavg ) for all i, and in particular for i ∈ Igood .Therefore, i∈Igood ci (fi (w̃i ) − fi (ŵi )) ≤
q
P
tr(Ŷ ) + r by Lemma 4.3. This estabc
(f
(
ŵ
)
−
f
(
ŵ
)),
which
is
bounded
by
αnS
i
avg
i
i
i∈Igood i

lishes (14) and completes the lemma.
Proof of Lemma 4.5

First, note that w̃i w̃i  Ŷ , since it is a convex combination of the ŵj , and so replacing ŵi with w̃i yields a
feasible point for the optimization. Therefore, fi (w̃i ) ≥ fi (ŵi ), and so zi ≥ 0.
−zi
Now, remember that c′i = ci · zmax
zmax . Then for any S ⊆ [n], we have
X
i∈S

X

zi
zmax
i∈S
1 X
=
ci zi .
zmax

ci − c′i =

ci ·

(31)
(32)

i∈S

Taking S = Igood and S = [n], it follows that
P
P
′
i∈Igood ci zi
i∈Igood ci − ci
Pn
= P
n
′
i=1 ci − ci
i=1 ci zi
(i)

≤

where (i) is by the supposition

1
n

Pn

i=1 ci zi

≥

2
αn

P

α
,
2

i∈Igood ci zi .

18

This establishes (15).

(33)
(34)

√

2

Next, suppose P
that λ = 8αnS
and tr(Ŷ ) > 6rα . In this case we must show that the supposition
r
P
n
1
2
i=1 ci zi ≥ αn
i∈Igood ci zi necessarily holds. Note that
n
X
X
ci zi =
ci (fi (w̃i ) − fi (ŵi ))
(35)
i∈Igood

i∈Igood

≤

X

i∈Igood

≤ αnS

ci (fi (ŵavg ) − fi (ŵi ))

q

tr(Ŷ ) + r

(36)



(37)

P
by
and (11). Now let x =
i∈Igood ci zi , and assume for the sake of contradiction that
PnLemma 4.3
2
x.
Then
by
(13)
c
z
<
in
Lemma
4.4
we
have
i=1 i i
α
!
n
(13) 2r 2
1 X
(38)
ci zi
tr(Ŷ ) ≤
+
α
λ
i=1
 
1 2
2r 2
+
x
(39)
<
α
λ α

q
(37) 2r 2
2nS
≤
tr(Ŷ ) + r .
(40)
+
α
λ
Solving the quadratic for Ŷ , we obtain (see Lemma C.1) tr(Ŷ ) ≤
√
8αnS
,
r

λ=
establishes

4r 2
α

+

6r 2
we have tr(Ŷ
is a ruled out by assumption
P)n ≤ α , which
2 P
the claim that i=1 ci zi ≥ α i∈Igood ci zi and completes the

4rnS
λ

+

4n2 S 2
λ2 .

Using the value

and is thus a contradiction. This
lemma.

Proof of Theorem 4.1
P
P
αn
α Pn
First, we note that i∈Igood ci ≥ αn
i∈Igood ci ≥ 2 + 2
i=1 ci holds
2 ; this is because the invariant
throughout the algorithm by Lemma 4.5. In particular, Algorithm 1 does eventually return, since Algorithm
2
P
zeros out at least one additional ci each time, and this can happen at most n − αn
c
times
before
i∈Igood i
2
would drop below αn
(which
we
established
is
impossible).
2
P
Now, let (ŵ1:n , Ŷ ) be the return value of Algorithm 1. By Lemma 4.2, we have i∈Igood ci (fi (ŵi ) − fi (w∗ )) ≤
2
λr 2 . Also, by assumption we have tr(Ŷ ) ≤ 6rα . By Lemma 4.3 we then have
X

i∈Igood

 (12) X
ci (fi (ŵavg ) − fi (w∗ )) + 2αnrS
ci f¯(ŵavg ) − f¯(w∗ ) ≤
(11)

≤

X

i∈Igood

ci (fi (ŵi ) − fi (w∗ )) + 3αnrS +

√
≤ λr 2 + 3αnrS + 6αnrS
√ √
√
= 3αnrS + ( 6 + 8) αnrS
√
≤ 9 αnrS.
(10)

P
Since i∈Igood ci ≥
shown.

(41)

i∈Igood

αn
2 ,

dividing through by

P

i∈Igood ci

19

√

6αnrS

(42)
(43)
(44)
(45)

Sr
yields f¯(ŵavg ) − f¯(w∗ ) ≤ 18 √
, as was to be
α

5 Concentration of Errors: A Local Hölder’s Inequality
Most of the bounds in Section 4 are bounds on an average error: for instance, Lemma 4.2 bounds the average
difference between fi (ŵi ) and fi (w∗ ), and Lemma 4.3 bounds the average difference between fi (ŵavg ) and
fi (ŵi ). One might hope for a stronger bound, showing that the above quantities are close together for almost
all i, rather than only close in expectation. This is relevant, for instance, in a clustering setting, where we
would like to say that almost all points are assigned a parameter ŵi that is close to the true cluster center.
Even beyond this relevance, asking whether we obtain concentration of errors in this adversarial setting
seems like a conceptually natural question:
If the good data is sub-Gaussian, then can we obtain sub-Gaussian concentration of the errors,
or can the adversaries force the error to only be small in expectation? What properties of the
good data affect concentration of errors in the presence of an adversary?
In this section, we will show that we can indeed obtain sub-Gaussian concentration, at least for the
statistical error. In particular, we will characterize the concentration behavior of the errors fi (ŵavg ) − fi (ŵi )
using a local Hölder’s inequality, which depends upon a refined notion of S that we denote by Sε . Before
defining Sε , we will state the local Hölder’s inequality:
P
Lemma 5.1. Suppose that the weights bi ∈ [0, 1] satisfy i∈Igood bi ≥ εαn, and that the parameters wi
satisfy wi wi⊤  Y . Then, for any w0 ∈ H, we have
!
X
X
p
tr(Y )Sε .
(46)
bi hwi , ∇fi (w0 ) − ∇f¯(w0 )i ≤
bi
i∈Igood

i∈Igood

We call this a local Hölder’s inequality because it is a sharpening of Lemma 4.6, which established via
Hölder’s inequality that
X

i∈Igood

ci hwi , ∇fi (w0 ) − ∇f¯(w0 )i ≤ αn

p

tr(Y )S.

(47)

p
¯(w0 )i > tr(Y )Sε ], Lemma 5.1 implies in particular that hwi , ∇fi (w0 )−
By taking bi =
I[hw
,
∇f
(w
)−∇
f
i
i
0
p
∇f¯(w0 )i ≤ tr(Y )Sε for all but εαn values of i ∈ Igood .
A local spectral norm bound. We now define Sε . The quantity Sε is essentially the maximum value of S
over any subset of Igood of size at least ε|Igood |:
def



1
p
∇fi (w) − ∇f¯(w) i∈T
w∈H T ⊆Igood ,|T |≥⌊εαn⌋
|T |

Sε = max

max

op

.

(48)

(As a special case note that S1 = S.) The quantity Sε bounds not just the operator norm of all of the points
in Igood , but also the operator norm on any large subset of Igood . We will see later that it is often possible to
obtain good bounds on Sε .

20

Concentration of statistical error. Using Sε , we can obtain an improved version of the bounds (11) and
b ) for almost all i ∈ I
(12) from Lemma 4.3, showing that fi (ŵi ) is close to a nominal value fi (ŵavg
good :
Lemma 5.2. Let the weights bi ∈ [0, 1] satisfy

the solution ŵ1:n , Ŷ to (8) satisfies
X

i∈Igood

bi



P

i∈Igood bi

≥ εαn, and define


X
b
b
b
fi (ŵavg
) − fi (ŵi ) ≤
bi h∇fi (ŵavg
), ŵavg
− ŵi i ≤
i∈Igood

def
b
=
ŵavg

X

bi

i∈Igood

!

Sε

Moreover, for any w, w′ ∈ H, we have
X

i∈Igood

X


bi f¯(w) − f¯(w′ ) −
bi fi (w) − fi (w′ ) ≤ 2
i∈Igood

X

i∈Igood

bi

P

i∈Igood

P

bi ŵi

i∈Igood

q

!

bi

. Then


tr(Ŷ ) + r .

rSε .

(49)

(50)

Relative to Lemma 4.3, the main differences are: The bounds now hold for any weights bi (with ŵavg
b ), and both (49) and (50) have been strengthened in some minor ways relative to (11) and
replaced by ŵavg
b ), ŵ b
′
(12) — in (49) we are now bounding the linearization h∇fi (ŵavg
avg − ŵi i, and (50) holds at all w, w
instead of just ŵavg , w∗ . These latter strengthenings are trivial and also hold in Lemma 4.3, but were omitted
earlier for simplicity. The important difference is that the inequalities hold for any bi , rather than just for the
original weights ci .
b , rather than ŵ
It is perhaps unsatisfying that (49) holds relative to ŵavg
avg . Fortunately, by exploiting
b
the fact that ŵavg is nearly optimal for f¯, we can replace ŵavg
with ŵavg at the cost of a slightly weaker
bound:
P
P
Corollary 5.3. Let the weights bi ∈ [0, 1] satisfy i∈Igood bi ≥ εαn, and suppose that i∈Igood ci ≥ 21 αn.
Then the solution ŵ1:n , Ŷ to (8) satisfies
!  q


X
X
2λr 2
bi (fi (ŵavg ) − fi (ŵi )) ≤
bi
Sε 3 tr(Ŷ ) + 9r +
.
(51)
αn
i∈Igood

In particular, if tr(Ŷ ) = O
but εαn values of i ∈ Igood .

i∈Igood

 2
r
α

√
√
and λ = O ( αnSε /r), then fi (ŵavg ) − fi (ŵi ) ≤ O (Sε r/ α) for all

Corollary 5.3 shows that no matter what the adversary does, the function errors fi (ŵavg ) − fi (ŵi ) will
be relatively tightly concentrated (at least assuming Sε is small; we will address the typical size of Sε later).
Looking ahead, we will also be able to show that, in the case that the fi are strongly convex, kwi − w∗ k22 is
also small for almost all i ∈ Igood . We give this result as Lemma 6.3 in Section 6.
Preserving inliers. Our outlier removal step can be modified based on Sε so that almost none of the
good points are removed. This is not strictly necessary for any of our later results, but is an intuitively
appealing property for our algorithm to have. That we can preserve the good points is unsurprising in light
of Corollary 5.3, which says that the good points concentrate, and hence should be cleanly separable from
any outliers. The modified outlier removal step is given as Algorithm 3.
Algorithm 3 is almost identical to Algorithm 2. The only difference from Algorithm 2 is that, instead of
setting zi to fi (w̃i ) − fi (ŵi ), we set zi to max (fi (w̃i ) − fi (ŵi ) − τ, 0) for an appropriately chosen τ . This
21

creates a buffer such that we do not start to downweight points until their function error passes the threshold
τ , which helps to make sure that very little mass is removed from the good points (because we do not start
to take away mass until we are fairly sure that a point is bad). Formally, we have the following result for
Algorithm 3, which is analogous to Lemma 4.5 for Algorithm 2:
Lemma 5.4. Suppose that λ =

√
8αnS
r

and tr(Ŷ ) >
X

i∈Igood

35r 2
α .

Then, the update step in Algorithm 3 satisfies
n

ci −

c′i

εα X
≤
ci − c′i .
2

(52)

i=1

This shows that the rate at which mass is removed from Igood is at most
removed overall.

ε
2

the rate at which mass is

Interpreting Sε . We end this section by giving some intuition for the typical scale of Sε . Recall that
Lemma 2.1 shows that, when the gradients of fi are sub-Gaussian with parameter
σ, then S ≤ O(σ)
p
assuming n ≫ d/α. A similar bound holds for Sε , with an additional factor of log(2/ε):
Lemma 5.5. If ∇fi (w) − ∇f¯(w) is σ-sub-Gaussian and L-Lipschitz, then with probability 1 − δ we have
s
 


p
+
log(1/δ)
d max 1, log rL
σ
 .
Sε = O σ  log(2/ε) +
(53)
εαn

 p



1
log(2/ε)
d max 1, log( rL
)
+
log(1/δ)
,
then
S
=
O
σ
In particular, if n ≥ εα
with probability
ε
σ
1 − δ, where O(·) masks only absolute constants.

Lemma 5.5 together with Corollary 5.3 show that, if the gradients of fi are sub-Gaussian, then the
errors between fi (ŵavg ) and
p fi (ŵi ) are also sub-Gaussian, in the sense that the fraction of i for which
fi (ŵavg ) − fi (ŵi ) ≥ Ω(σ log(2/ε)/α) is at most ε. Inverting this, for sufficiently large t the fraction
√
of i for which fi (ŵavg ) − fi (ŵi ) ≥ tσ/ α is at most exp(−Ω(t2 )). In other words, no matter what the
adversary does, it cannot prevent the function errors from concentrating in a sub-Gaussian manner, provided
the good data itself is sub-Gaussian.
Algorithm 3 Algorithm for updating weights c to downweight outliers.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure U
(c, ŵ1:n , Ŷ )
PDATE
q W EIGHTS
τ ← Sε 3 tr(Ŷ ) + 9r

for i = 1, . . . , n do
Let w̃i be the solution to (5) as in Algorithm 2.
Let zi ← max (fi (w̃i ) − fi (ŵi ) − τ, 0)
end for
zmax ← max{zi | ci 6= 0}
−zi
c′i ← ci · zmax
zmax for i = 1, . . . , n
return c′
end procedure

22

A general Chebyshev bound. What happens if the function errors are not sub-Gaussian, but we still have
a bound on S = S1 ? We can then bound Sε in terms of S by exploiting the monotonicity of the operator
norm.
q
q
ε2
2 αn⌋
S
≤
2
Lemma 5.6. For any ε1 ≤ ε2 , Sε1 ≤ ⌊ε
ε
2
ε 1 Sε 2 .
⌊ε1 αn⌋

When coupled with Corollary 5.3, this shows that the function errors concentrate in a Chebyshev-like
√
manner: The fraction of i for which fi (ŵavg ) − fi (ŵi ) exceeds
Ω (σ/ αε) is at most ε, and so the fraction

√
of i for which fi (ŵavg ) − fi (ŵi ) ≥ tσ/ α is O t12 . Note that this is already a strengthening of the
naı̈ve bound from Markov’s inequality, which would only say that the fraction is O 1t . The local Hölder’s
inequality in Lemma 5.1 thus leads to a tighter analysis even without any further bounding of Sε .
Proof of Lemma 5.1

Throughout this section we will for convenience use ∆i to denote ∇fi (w0 ) − ∇f¯(w0 ). We start with a
helper lemma that translates information about Sε into a more useful form:
P
Lemma 5.7. For any bi ∈ [0, 1] with i∈Igood bi ≥ ⌊εαn⌋, and any matrix Y  0, we have
!
X
X
bi ∆ ⊤
(54)
bi tr(Y )Sε2 .
i Y ∆i ≤
i∈Igood

i∈Igood

Proof. Since the inequality
P is linear in bi , it is enough to check it at the extreme values of bi . These consist of
bi ∈ {0, 1} such that i∈Igood bi = ⌊εαn⌋, which exactly correspond to subsets S of Igood of size ⌊εαn⌋.4
It thus suffices to check (54) at these points, which amounts to showing that
X
2
∆⊤
(55)
i Y ∆i ≤ |T | tr(Y )Sε for all sets T of size ⌊εαn⌋.
i∈T

Letting DT = [∆i ]i∈T , we show this as follows:
X

∆⊤
i Y ∆i = tr Y

i∈T

X

∆i ∆⊤
i

i∈T



= tr Y DT DT⊤

!

(56)
(57)

≤ tr (Y ) kDT DT⊤ kop

≤ tr (Y

(i)

(58)

) kDT k2op

(59)

≤ tr(Y )|T |Sε2 ,

(60)

kD k
as was to be shown. Here (i) invokes the definition of Sε , which implies that Sε ≥ max|T |=⌊εαn⌋ √T op .
|T |

We are now ready to prove Lemma 5.1.
4

There is also an extreme point corresponding to S = Igood , which we ignore as its analysis is identical.

23

Proof of Lemma 5.1. We have
X

i∈Igood

X

bi hwi , ∇fi (w0 ) − ∇f¯(w0 )i =

i∈Igood

v
u
u
≤t

(i)

X

bi

X

bi

i∈Igood

v
u
u
=t

v
u
u
≤ t

i∈Igood

(ii)

!

X

bi

i∈Igood

v
u
u
≤ t

i∈Igood

X

bi

i∈Igood

!

i∈Igood

X

(62)

⊤
bi ∆ ⊤
i wi wi ∆i

(63)

X

bi ∆ ⊤
i Y ∆i

(64)

i∈Igood

!2

Sε

bi hwi , ∆i i2

i∈Igood

!

bi

(61)

X

!

X

(54)

=

bi hwi , ∆i i

tr(Y )Sε2

p

(65)

tr(Y ),

(66)

as was to be shown. Here (i) is Cauchy-Schwarz and (ii) uses the condition wi wi⊤  Y .
Proof of Lemma 5.2

b ) − f (ŵ ) ≤ h∇f (ŵ b ), ŵ
First, note that fi (ŵavg
avg − ŵi i by convexity of fi , so only the second
i
i
i
avg
inequality in (49) is interesting. Similarly to how we established (11) in Lemma 4.3, we have
X
X
b
b
b
b
b
bi h∇fi (ŵavg
), ŵavg
− ŵi i =
bi h∇fi (ŵavg
) − ∇f¯(ŵavg
), ŵavg
− ŵi i
(67)
i∈Igood

i∈Igood

(46)

≤

X

bi

i∈Igood

!

Sε

q



tr(Ŷ ) + r .

(68)

In the final step we invoke (46) twice, identically to Lemma 4.3.
For (50), we follow an identical argument to (12) from Lemma 4.3. Defining w(t) = tw + (1 − t)w′ ,
we have
Z 1 X
X

′
¯
¯
bi f (w) − f (w ) =
bi h∇f¯(wt ), w − w′ idt
(69)
i∈Igood

=

0 i∈I
good
1 X

Z

0 i∈I
good

Z
(46)
≤
=

1

X

bi h∇fi (wt ), w − w idt +

0 i∈I
good

X

i∈Igood

′

Z

bi h∇fi (wt ), w − w′ idt +


bi fi (w) − fi (w )
′

24

!

+2

X

1

0 i∈I
good

Z

X

1

2
0

X

i∈Igood

bi h∇f¯(wt ) − ∇fi (wt ), w − w′ idt

bi

i∈Igood

bi

!

rSε .

!

(70)
rSε dt

(71)

(72)

This yields (50) and completes the lemma.
Proof of Corollary 5.3

P
b ) . By (50) in Lemma 5.2, we have
We need to bound i∈Igood bi fi (ŵavg ) − fi (ŵavg
X

i∈Igood


 (50)
b
) ≤
bi fi (ŵavg ) − fi (ŵavg
≤

X

bi

i∈Igood

X

bi

i∈Igood

!

!



b
f¯(ŵavg ) − f¯(ŵavg
) + 2Sε r

f¯(ŵavg ) − f¯(w∗ ) + 2Sε r .

(74)

On the other hand, by Lemmas 4.3 and 4.2, we also have
!
X
 (12) X
ci f¯(ŵavg ) − f¯(w∗ ) ≤
ci (fi (ŵavg ) − fi (w∗ )) + 2αnSr
i∈Igood

i∈Igood

(11)

≤

(10)

X

i∈Igood

∗

ci (fi (ŵi ) − fi (w )) + αnS

≤ λr 2 + αnS

q

(73)


tr(Ŷ ) + 3r .

q

(75)
tr(Ŷ ) + 3r



(76)
(77)

P
P
1
¯
¯ ∗
c
and
using
the
condition
Dividing through
by
i
i∈Igood ci ≥ 2 αn, we obtain f (ŵavg ) − f(w ) ≤
i∈I
good

q
2λr 2
tr(Ŷ ) + 3r . Using S ≤ Sε and substituting into (74) yields
αn + 2S
X

i∈Igood



b
) ≤
bi fi (ŵavg ) − fi (ŵavg

X

i∈Igood

bi

!

 2λr 2 
 q
Sε 2 tr(Ŷ ) + 8r +
.
αn


P
b ) − f (ŵ ) from (49) then gives the desired inCombining this with the bound on i∈Igood bi fi (ŵavg
i
i
√
equality (51). The rest of Corollary 5.3 follows by setting bi = I[fi (ŵavg ) − fi (ŵi ) > C · Sε r/ α] for an
appropriate absolute constant C.
Proof of Lemma 5.4
P
Recall that zi = max (fi (w̃i ) − fi (ŵi ) − τ, 0). Our goal is to show that i∈Igood ci zi ≤
we can show this, then the result follows identically to the first part of Lemma 4.5.

25

εα
2

Pn

i=1 ci zi .

If

To start, we have
X

ci zi =

i∈Igood

X

i∈Igood

≤
(i)

X

i∈Igood

(ci I[zi > 0]) · (fi (w̃i ) − fi (ŵi ) − τ )

(78)

(ci I[zi > 0]) · (fi (ŵavg ) − fi (ŵi ) − τ )

(79)

≤ max εαn,

i∈Igood

= max εαn −
≤ εαnτ.

X

X

!

ci I[zi > 0] τ −
!

ci I[zi > 0]τ

(80)

i∈Igood

ci I[zi > 0], 0 τ

i∈Igood

X

(81)
(82)

P
P
Here
P (i) is because i∈Igood (ci I[zi > 0]) (fi (ŵavg ) − fi (ŵi )) ≤ ( i ci I[zi > 0]) τ by Lemma 5.2 if
i∈Igood ci I[zi > 0] ≥ εαn, and if the sum is less than εαn, we can always arbitrarily increase the weights
beyond ci I[zi > 0] until their sum is large enough (since fi (ŵavg ) − fi (ŵi ) ≥ 0, this will only make the
resulting inequalityP
stronger).
Pn
2
Now let x =
i=1 ci zi < εα x. By
i∈Igood ci zi , and assume for the sake of contradiction that
Lemma 4.4 we have
!
n
2r 2
1 X
tr(Ŷ ) ≤
ci (fi (w̃i ) − fi (ŵi ))
(83)
+
α
λ
i=1
!
n
2r 2
1 X
ci (τ + max (fi (w̃i ) − fi (ŵi ) − τ, 0))
(84)
≤
+
α
λ
i=1


1
2r 2
2
+
x
(85)
≤
nτ +
α
λ
εα

 q
2r 2
3r
2r 2 3nτ
+
=
+√
(86)
≤
3 tr(Ŷ ) + 9r
α
λ
α
8α
s
2
11r 2 tr(Ŷ )
12r
≤
+
.
(87)
α
α
2

applied to tr(Ŷ ),P
we have tr(Ŷ ) ≤ 35r
By Lemma C.1 P
α . This contradicts the assumption of the lemma, so
n
εα
c
z
,
from
which
the desired result follows.
we indeed have i=1 ci zi ≥ 2
i∈Igood i i
Proof of Lemma 5.6

Let M be any matrix, and T1 ⊆ T2 be subsets of the rows of M . Then itqis easy to see that kMT1 kop ≤
2 αn⌋
kMT2 kop . Using this, it is then clear from the definition (48) that Sε1 ≤ ⌊ε
⌊ε1 αn⌋ Sε2 , since any subset T
appearing in the definition of Sε1 can be extended to a set T ′ appearing in the definition of Sε2 , whose size
⌊ε2 αn⌋
times bigger.
is at most ⌊ε
1 αn⌋

26

6 Bounds for Strongly Convex Losses
We now turn our attention to the special case that the functions fi are strongly convex in w, in the sense that
for all w, w′ ∈ H,
κ
(88)
fi (w′ ) ≥ hw′ − w, ∇fi (w)i + kw′ − wk22 .
2
In this case, we will obtain stronger bounds by iteratively clustering the output ŵ1:n of Algorithm 1 and
re-running the algorithm on each cluster. The main theorem in this section is a recovery result in the list
decoding model, for an algorithm (Algorithm 4) that formalizes this clustering intuition:
1
2

andlet U , ŵ1:n be
 the output of Algorithm 4. Then
 U√has sizeat most
√
log(2/α)
Sε log(2/α)
S
ε
1
√
√
⌊ (1−ε)α
. Moreover, kŵi − w∗ k2 ≤ O
for all
⌋, and minu∈U ku − w∗ k2 ≤ O
κ α
κ α

Theorem 6.1. Suppose that ε ≤
but εαn values of i ∈ Igood .

Note, interestingly, that the bound does not depend on the radius r. Since the list decoding model can be
reduced to the semi-verified model, Theorem 6.1 also yields strengthened results in the semi-verified model
when the functions are strongly convex (we omit these for brevity).
Algorithm and proof overview. Algorithm 4 works at a high level as follows: first, run Algorithm 1 to
obtain ŵi that are (as we will show in Proposition 6.2) relatively close to w∗ for most i ∈ Igood . Supposing
that the good ŵi are within distance r ′ ≪ r of w∗ , we can cluster ŵ1:n into balls of radius Õ (r ′ ), and re-run
Algorithm 1 on each cluster; Theorem 4.1 will now yield bounds in terms of r ′ instead of r. By repeating
this enough times, we can shrink our hypothesis space to a small ball around w∗ , thus obtaining substantially
better bounds. A key piece of machinery which will allow us to obtain a satisfactory clustering is the notion
of a padded decomposition, originally due to Fakcharoenphol et al. (2003), which we explain in more detail
later in this section.
Pseudocode for Algorithm 4 is provided above: We keep track of an upper bound r (t) on the distance
from the ŵi to w∗ , which is initially r and decreases by a factor of 2 each time. If this radius drops below
a threshold, then we perform a final greedy clustering and exit. Otherwise we use padded decompositions
to cluster the points, and run Algorithm 4 on each cluster to obtain new assignments for each ŵi (since the
padded decomposition is randomized, we repeat this several times to ensure correctness with high probability). We can show (Lemma 6.5) that these new assignments ŵi will be within distance 21 r (t) to w∗ for almost
all i ∈ Igood , which is the key to proving correctness of the algorithm.
The rest of this section consists of three parts: First, we will show that if the fi are strongly convex,
and ŵ1:n is the output of Algorithm 1, then kŵi − w∗ k2 is small for most i ∈ Igood (this requires some
work, since applying Theorem 4.1 directly would only imply that kŵavg − w∗ k2 is small). Next, we will
introduce the notion of a padded decomposition, and show (following ideas in Fakcharoenphol et al. (2003))
that padded decompositions of small diameter exist in our setting. Finally, we will combine these two results
to analyze Algorithm 4 and establish Theorem 6.1.
Establishing concentration of kŵi − w∗ k2 .
Igood . This is captured in Proposition 6.2:

We will first show that ŵi is close to w∗ for almost all i ∈

Proposition 6.2. For some absolute constant C and for any ω ≥ 1, the output ŵ1:n of Algorithm 1 satisfies
√ε for all but εαn
kŵi − w∗ k22 ≤ Cω · κrS
values of i ∈ Igood .
ω2
α
27

The key to establishing Proposition 6.2 lies in leveraging the bound on the statistical error from Lemma 5.2,
together
with the strong convexity of fi . Recall that Lemma 5.2 says that for any bi ∈ [0, 1] satisfying
P
i∈Igood bi ≥ εαn, we have
! q

X
X
b
b
(89)
bi h∇fi (ŵavg ), ŵavg − ŵi i ≤
bi S ε
tr(Ŷ ) + r .
i∈Igood

i∈Igood

Algorithm 4 Iterative clustering algorithm for approximating w∗
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

B(u; s) denotes the ball of radius s centered at u
A(u; s) denotes the output of Algorithm 1 with hypothesis space H ∩ B(u; s), radius s, origin shifted
to u
procedure F IND C LUSTERS
(1)
ŵ1:n ← A(0; r)
⊲ initialize ŵ
(1)
r ←r
for t = 1, 2, . . . do
(t)
(t)
W ← {ŵi | ŵi is assigned}
√
then
⊲ if radius is small, compute a clustering and exit
if r (t) < C1 · Sε log(2/α)
κ α √
Sε log(2/α)
√
⊲ C1 , C2 are absolute constants
Let rfinal = C2 ·
κ α
Greedily find a maximal set of points u1 , . . . , um such that:
(i) |B(uj ; 2rfinal ) ∩ W| ≥ (1 − ε)αn for all j
(ii) kuj − uj ′ k2 > 4rfinal for all j 6= j ′ .
(t)
return U = {u1 , . . . , um } as well as ŵ1:n .
end if


do
⊲ compute candidate assignment w̄1:n (h)
for h = 1, . . . , 112 log t(t+1)
δ
w̄1:n (h) ← unassigned

Let Ph be a (ρ, 2r (t) , 78 )-padded decomposition of W with ρ = O r (t) log( α2 ) .
for each T ∈ Ph do
⊲ run Algorithm 1 on each piece of the decomposition
Let B(u, ρ) be a ball containing T
(t)
For i with ŵi ∈ T , assign w̄(h)i based on the output of A(u; ρ + r (t) )
end for
end for
for i = 1, . . . , n do
⊲ pick an assignment that most of the w̄i (h) agree on
Find a h0 such that kw̄i (h0 ) − w̄i (h)k2 ≤ 13 r (t) for at least 12 of the h’s.
(t+1)

Set ŵi
← w̄i (h0 ) (leave unassigned if h0 does not exist)
end for
r (t+1) ← 12 r (t)
end for
end procedure

28

By strong convexity of fi , we then have


X
b
0≤
) − fi (ŵi )
bi fi (ŵavg

(90)

i∈Igood



κ
b
b
b
k22
), ŵavg
− ŵi i − kŵi − ŵavg
bi h∇fi (ŵavg
2
i∈Igood
! q

X
κ X
b
bi kŵi − ŵavg
k22 .
≤
bi S ε
tr(Ŷ ) + r −
2

≤

X

(92)

i∈Igood

i∈Igood

Therefore:

(91)

P
Lemma 6.3. For any bi ∈ [0, 1] satisfying i∈Igood bi ≥ εαn, we have
P

q
2
b
2
i∈Igood bi kŵi − ŵavg k2
P
tr(Ŷ ) + r Sε .
(93)
≤
κ
i∈Igood bi
P


bj
1
′
By applying Lemma 6.3 to bi = 2 bi + Pj cj ci , we obtain the following corollary, which gives
j

b :
bounds in terms of ŵavg rather than ŵavg

P
P
Corollary 6.4. For any bi ∈ [0, 1] satisfying εαn ≤ i∈Igood bi ≤ i∈Igood ci , we have
P

q
2
16
i∈Igood bi kŵi − ŵavg k2
P
≤
tr(Ŷ ) + r Sε .
κ
i∈Igood bi

q
16
2
In particular, at most εαn points i ∈ Igood have kŵi − ŵavg k2 ≥ κ
tr(Ŷ ) + r Sε .

(94)

Corollary 6.4 is crucial because it shows that all but an ε fraction of the ŵi , for i ∈ Igood , concentrate
around ŵavg .

Note that we also have kŵavg − w∗ k22 ≤ κ2 f¯(ŵavg ) − f¯(w∗ ) , which is bounded by Theorem 4.1;
moreover, Theorem 4.1 also bounds tr(Ŷ ). Finally, we have Sε/ω2 ≤ 2ωSε by Lemma 5.6. Combining all
of these inequalities, we can obtain Proposition 6.2.

Padded decompositions. Proposition 6.2 says that the output ŵ1 , . . . , ŵn of Algorithm 1 satisfies kŵi −
w∗ k2 ≤ s for almost all i ∈ Igood , for some s ≪ r. We would then ideally like to partition the ŵi into sets
of small diameter (say 2s), such that all of Igood is in a single piece of the partition (so that we can then run
Algorithm 4 on each piece of the partition, and be guaranteed that at least one piece has most of Igood ).
In general, this may not be possible, but we can obtain a probabilistic version of the hoped for result:
We will end up finding a partition into sets of diameter O (s log(2/α)) such that, with probability 87 , all of
Igood is in a single piece of the partition. This leads us to the definition of a padded decomposition:
Definition. Let x1 , . . . , xn be points in a metric space. A (ρ, τ, δ)-padded decomposition is a (random)
partition P of {x1 , . . . , xn } such that: (i) each element of P has diameter at most ρ, and (ii) for each xi ,
with probability 1 − δ all points within distance τ of xi lie in a single element of P.
Fakcharoenphol

 et al. (2003) show that for any τ and δ, a (ρ, τ, δ)-padded decomposition exists with
τ log(n)
ρ = O
. Moreover, the same proof shows that, if every xi is within distance τ of at least
δ


. In particular, in our case we can obtain
Ω(αn) other xi , then we can actually take ρ = O τ log(2/α)
δ
a (O (s log(2/α)) , 2s, 7/8)-padded decomposition of the ŵi output by Algorithm 1; we show this formally
in Lemma A.1. This probabilistic notion of clustering turns out to be sufficient for our purposes.
29

Analyzing Algorithm 4. We are now prepared
to analyze Algorithm 4. In each iteration, Algorithm 4

t(t+1)
independently samples l = 112 log
padded decompositions of the ŵi . For each decomposition Ph ,
δ
it then runs Algorithm 1 on each component of the resulting partition, and thereby obtains candidate values
w̄1 (h), . . . , w̄n (h). Finally, it updates ŵi by finding a point close to at least 12 of the candidate values w̄i (h),
across h = 1, . . . , l.
The idea for why this works is the following: since 87 of the time, the padded decomposition Ph succeeds in preserving Igood , it is also the case that roughly 87 of the candidate assignments w̄i (h) are “good”
assignments close to w∗ . Therefore, any point that is close to at least 12 of the w̄i (h) is, by pigeonhole, close
to one of the good w̄i (h), and therefore also close to w∗ .
If we formalize this argument, then we obtain Lemma 6.5, which controls the behavior of the update
(t)
(t+1)
ŵ1:n → ŵ1:n on each iteration of the loop:
Lemma 6.5. Algorithm 4 satisfies the following property: at the beginning of iteration t of the outer loop,
(t)
(t)
(t)
let Igood denote the set of points i ∈ Igood for which kŵi − w∗ k2 ≤ r (t) . Also suppose that |Igood | ≥
δ
(1 − ε)αn and ε ≤ 21 . Then, with probability 1 − t(t+1)
over the randomness in the padded decompositions,

2
(t+1)
(t)
√
kŵi
− w∗ k2 ≤ 12 r (t) for all but C0 · Sεκrlog(2/α)
· εαn points in Igood , for some absolute constant C0 .
(t) α
Essentially, Lemma 6.5 shows that if almost all of the good points are within r (t) of w∗ at the beginning
of a loop iteration, then almost all of the good points are within 12 r (t) of w∗ at the end of that loop iteration,
provided r (t) is large enough. Using Lemma 6.5, we can establish Theorem 6.1.
Proof of Theorem 6.1
(t)

Using Lemma 6.5 we can prove Theorem 6.1. The key is to show that the precondition |Igood | ≥ (1 − ε)αn
of Lemma 6.5 holds throughout Algorithm 4, for appropriate choices of the absolute constants C1 and C2 .
(t)
We will actually prove the stronger claim that |Igood | ≥ (1 − 23 ε)αn for all t. Lemma 6.5 shows that
2

√
(t)
√
εαn at iteration t. Now take C1 = 2C0 . In the
Igood decreases in size by at most C0 Sεκrlog(2/α)
(t) α
√
√
final iteration before halting, since r (t) ≥ 2C0 Sε log(2/α)
, we can conclude by Lemma 6.5 that at most
κ α
1
2 εn

(t)

points leave Igood in this iteration of the algorithm. But if we look back to previous iterations of the
(t)

algorithm, the bound on the number of points leaving from Igood decreases by a factor of 4 each time t
(t)

decreases (because r (t) increases by a factor of 2). Therefore, the total number of points that leave Igood

1
over all iterations of the algorithm is at most 12 εn 1 + 14 + 16
+ · · · = 23 εn < εn. This establishes that
(t)

|Igood | ≥ (1 − 23 ε)αn for all iterations of the algorithm.
(T )

Now, consider the points ŵ1:n obtained in the final iteration T of Algorithm 4. By invoking
q (T −1)Proposi
√
(T )
r √ Sε
∗
tion 6.2 with ω = 3, we have for an appropriate choice of C2 that kŵi − w k2 ≤ O
=
κ α
√
S
log(2/α)
(T −1)
C2 · ε κ√α
= rfinal for all but 13 εαn values of i ∈ Igood , and hence for all but εαn values of i ∈ Igood .

final .
Call the set of points satisfying this condition Igood
To finish, observe that by construction, U is a maximal set of centers u such that: (i) |B(u; 2rfinal ) ∩
final , we have
W| ≥ (1 − ε)αn and (ii) B(u; 2rfinal ) ∩ B(u′ ; 2rfinal ) = ∅ for u 6= u′ . But for i ∈ Igood
(T )

(T )

B(ŵi ; 2rfinal ) ⊇ B(w∗ ; rfinal ) ⊇ {ŵi

(T )

final }, and hence |B(ŵ
| i ∈ Igood
i ; 2rfinal ) ∩ W| ≥ (1 − ε)αn.

30

(T )

(T )

Therefore, B(ŵi ; 2rfinal ) must intersect B(u; 2rfinal ) for some u ∈ U , as otherwise we could add ŵi to
(T )
(T )
U . This implies that kŵi − uk2 ≤ 4rfinal , so that kw∗ − uk2 ≤ 5rfinal , and hence kŵi′ − uk2 ≤ 6rfinal
final . Therefore, the center u satisfies the required property that ku − w ∗ k = O(r
for all i′ ∈ Igood
2
final ) and
(T )

kŵi

− uk2 = O(rfinal ) for all but εαn elements of Igood .
We finally note that, for u ∈ U , the sets B(u; 2rfinal ) are disjoint and each contain at least (1 − ε)αn
1
⌋ elements in U .
points, so there can be at most ⌊ (1−ε)α

Proof of Proposition 6.2
√

tr(Ŷ )+r 2 Sε/ω 2
κ



By Corollary 6.4, we have that
≤O
for all but ωεα2 n points i ∈ Igood . But
 2


√ε
tr(Ŷ ) ≤ O rα , and Sε/ω2 ≤ 2ωSε , so we have kŵi − ŵavg k22 ≤ O ω · κrS
for all but ωεα2 n points.
α
 
rS
In addition, by Theorem 2.2 we have f¯(ŵavg ) − f¯(w∗ ) ≤ O √
, which by the strong convexity of f¯
α



∗ k2 ≤ 2 kŵ − ŵ
2 + kŵ
∗ k2 ≤
√
.
Combining
these,
we
have
k
ŵ
−w
k
−
w
implies that kŵavg −w∗ k22 ≤ O κrS
i
i
avg
avg
2
2
2
α




rS
rS
rS
ε
ε
√
√
√
O ω · κ α + κ α = O ω · κ α , as was to be shown.
kŵi − ŵavg k22

Proof of Corollary 6.4
For notational convenience, let B =
X

i∈Igood

P

i∈Igood bi
(i)

2
bi kŵi − ŵavg
k22 ≤

=
(ii)

≤

and C =

X

i,j∈Igood

1
B

bi ·

X

i,j∈Igood

1
B

P

i∈Igood ci .

We have

cj
kŵi − ŵj k22
C

(95)

2
bi · ( B
C cj )kŵi − ŵj k2

X

(bi +

B
C ci )(bj

+

(96)

B
C cj )kŵi

i,j∈Igood

− ŵj k22 ,

(97)

where the first inequality is convexity of k · k22 , and the second is because we only added positive terms to
the sum.

P
′
apply Lemma
6.3 at the value b′i = 12 bi + B
j cj ≥
C ci . This satisfies bi ∈ [0, 1] (since
P Now, we willP
P
′ =
6.3
to
obtain
b
),
and
also
b
b
≥
εαn.
We
can
therefore
invoke
Lemma
j j
i i
i i
1
B

X

(bi +

B
C ci )(bj

+

B
C cj )

i,j∈Igood

=

4
B

=8

X

i,j∈Igood

X

i∈Igood

16
≤
κ
as was to be shown.

31

q

b′i b′j kŵi − ŵj k22
′

b
b′i kŵi − ŵavg
k22



tr(Ŷ ) + r Sε ,

(98)

(99)
(100)

Proof of Lemma 6.5
(t)

Call a partition Ph good if the set Igood lies within a single piece of Ph , and let H be the set of iterations


for which Ph is good, and l = 112 log t(t+1)
be the total number of iterations. Note that each h is
δ

good with probability

l
δ
exp − 112
= t(t+1)
.

7
8

independently, so by the Chernoff bound, the probability that |H| < 34 l is at most
(t)

Note that, for any good h, if T is the element of Ph containing Igood , then w∗ is within distance r (t) of
T , and hence if T ⊆ B(u, ρ) then w∗ ∈ B(u, ρ + r (t) ). Therefore, the hypothesis space for A(u, ρ + r (t) )
contains w∗ and so Proposition 6.2 implies that, for any good h,
s


s
2
(t)
(t)
r
S
log(
)
(ρ + r )Sε 
ε
√
√ α 
kw̄i (h) − w∗ k2 ≤ O  ω ·
= O ω ·
(101)
κ α
κ α

(t)
εαn
of i ∈ Igood . We will take ω such that the right-hand-side of (101) is 16 r (t) , which
ω 2 values

√
(t)
yields ω = Ω Sκrlog( 2α) .
ε
α
(t)
Next, call an i ∈ Igood bad if kw̄i (h) − w∗ k2 > 16 r (t) for more than 8l of the good h. Averaging over
the good h, there are therefore at most 8εαn
bad values of i (since each such bad value would constitute 8l
ω2
violations of (101), and we know that there are at most l · εαn
violations in total).
ω2
Now if i is not bad, then kw̄i (h) − w∗ k2 ≤ 61 r (t) for at least 5l8 values of h (because it is small for all but
l
3l
1 (t)
of at least 2l of the w̄i (h).
8 of the at least 4 good h). Now, consider any w̄i (h0 ) that is within distance 3 r

for all but

By the pigeonhole principle, w̄i (h0 ) is therefore close to at least one of these good w̄i (h), and so satisfies
kw̄i (h0 ) − w∗ k2 ≤ kw̄i (h0 ) − w̄i (h)k2 + kw̄i (h) − w∗ k2 ≤ 12 r (t) . Moreover, such a h0 exists since any of
the good w̄i (h) be within distance 13 r (t) of the other good w̄i (h′ ).
(t+1)

In sum, the assigned value ŵi
i∈

(t)
Igood ,

= w̄i (h0 ) has distance at most 12 r (t) to w∗ for all but

8εαn
ω2

values of

which yields the desired result.

7 Lower Bounds
In this section we prove lower bounds showing that the dependence of our bounds on S is necessary
even if
q
1
∗
p is a multivariate Gaussian. For α, we are only able to show a necessary dependence of log( α ), rather
p
than the 1/α appearing in our bounds. Determining the true worst-case dependence on α is an interesting
open problem.
One natural question is whether S, which typically depends on the maximum singular value of the
covariance matrix, is really the right dependence, or whether we could achieve bounds based on e.g. the
average singular value instead. Lemma 7.1 rules this out, showing that it would require Ω(2k ) candidates in
the list-decodable setting to achieve dependence on even the kth singular value of the covariance matrix.
Lemma 7.1. Suppose that p∗ is known to be a multivariate Gaussian N (µ, Σ) with covariance Σ  Σ0 ,
where µ and Σ are otherwise unknown. Also let σk2 denote the kth largest singular value of Σ0 . Then, given
any amount of data, an α-fraction of which is drawn from p∗ , any procedure for outputting at most m = 2k−1
candidate means µ̂1 , . . . , µ̂m must have, with probability at least 12 , minm
j=1 kµ̂j − µk2 ≥
32

σk
4

·

1
log( α
)

q

1
)
1+log( α

.

By the reduction from the semi-verified to the list-decodable model, we obtain a lower bound in the
semi-verified setting as well:
Corollary 7.2. Any algorithm that has kµ̂ − µk2 <
verified model requires at least

k−2
1
log2 ( α
)

σk
4

·

1
log( α
)

q

1
1+log( α
)

with probability at least

1
2

in the semi-

verified samples.

We remark that the same proofs show lower bounds for non-strongly convex losses as well. For instance,
while mean estimation corresponds to fi (w) = kw − xi k22 , we could also estimate the direction of a vector
µ
by taking fi (w) = −w⊤ xi , and constraining kwk2 ≤ r; in this case the minimizer of f¯(w) is w∗ = r · kµk
,
2
where µ = E[x]. An essentially identical argument to Lemma 7.1 and Corollary 7.2 shows that at least 2Ω(k)
1
log( α
)
candidates ŵj are necessary to obtain minj f¯(ŵj ) − f¯(w∗ ) ≤ r · σk · q
with probability greater
4

than 21 , and at least Ω
we omit these.



k
1
log2 ( α
)



1
1+log( α
)

verified samples are needed in the semi-verified model. To avoid repetition

Proof of Lemma 7.1
Let us suppose that the unverified data has distribution p̂ = N (0, Σ0 ), which is possible iff p̂ ≥ αp∗ . We
start with a lemma characterizing when it is possible that the true distribution p∗ has mean µ:
Lemma 7.3. Let p̂ = N (0, Σ0 ) and p∗ = N (µ, Σ0 − λµµ⊤ ). Then p̂ ≥ αp∗ provided that µ⊤ Σ−1
0 µ ≤
1
)
log2 ( α
1
)
1+log( α

and λ =

1
1 .
)
log( α

2
As a consequence, if µ⊤ Σ−1
0 µ ≤ t for t =

1
log( α
)
q
,
1
1+log( α
)

then p∗ could have mean µ. Now, consider

the space spanned by the k largest eigenvectors of Σ0 , and let Bk be the ball of radius tσk in this space.
Also let P be a maximal packing of Bk of radius 4t σk . A simple volume argument shows that |Bk | ≥ 2k .
On the other hand, every element µ of Bk is a potential mean because it satisfies µ⊤ Σ−1
0 µ ≤

kµk22
σk2

≤ t2 .

Therefore, if the true mean µ is drawn uniformly from Bk , any 2k−1 candidate means µ̂j must miss at least
half of the elements of Bk (in the sense of being distance at least 4t σk away) and so with probability at least
t
1
2 , kµ̂j − µk2 is at least 4 σk for all j, as was to be shown.
Proof of Corollary 7.2
Suppose that we can obtain µ̂ satisfying kµ̂ − µk2 <

σk
4

·

1
log( α
)

q

1
1+log( α
)

with m ≤

k−2
1
log2 ( α
)

samples, with

probability at least 12 . If we sample m elements uniformly from the unverified samples, with probability αm
we will obtain only samples from p∗ , and therefore with probability 21 αm we can obtain (by assumption)
a candidate mean µ̂ with kµ̂ − µk2 <

σk
4

·

1
log( α
)
q
.
1
)
1+log( α

If we repeat this

2
αm

times, then with probability

 2
1 − 1 − 12 αm αm ≥ 1 − 1e > 12 , at least one of the candidate means will be close to µ. But by Lemma 7.1,
this implies that α2m ≥ 2k−1 , and so m ≥ logk−2
, as claimed.
(1)
2 α

33

8 Intuition: Stability Under Subsets
In this section, we establish a sort of “duality for robustness” that provides intuition underlying our results.
Essentially, we will show the following:
If a statistic of a dataset is approximately preserved across every large subset of the data,
then it can be robustly recovered even in the presence of a large amount of additional arbitrary/adversarial data.
To be a bit more formal, suppose that for a set of points {x1 , . . . , xn } lying in Rd , there is a subset I ⊆ [n]
with the following property: for any subset T ⊆ I of size at least 12 α2 n, the mean over T is ε-close to the
mean over I. In symbols,
X
1
def 1
xi .
(102)
kµT − µI k2 ≤ ε for all T ⊆ I with |T | ≥ α2 n, where µT =
2
|T |
i∈T

In such a case, can we approximate the mean of I, even if I is not known and the points in [n]\I are
arbitrary?
If we do not care about computation, the answer is yes, via a simple exponential-time algorithm. Call a
set of points J α-stable if it satisfies the following properties: |J| ≥ αn, and (102) holds with I replaced by
J (i.e., the mean moves by at most ε when taking subsets of J of size at least 21 α2 n). Then, we can run the
following (exponential-time) algorithm:
1. Initialize U = [].
2. Find an α-stable set J which has overlap at most 21 α2 n with all elements of U .
3. Append J to U and continue until no more such sets exist.

A simple inclusion-exclusion argument5 shows that k ≤ α2 . Therefore, the above algorithm terminates with
|U | ≤ α2 . On the other hand, by construction, I must have overlap at least 12 α2 n with at least one element of
U (as otherwise we could have also added I to U ). Therefore, for some J ∈ U , |I ∩ J| ≥ 21 α2 n. But then,
letting T = I ∩ J, we have kµI − µJ k2 ≤ kµI − µT k2 + kµT − µJ k2 ≤ 2ε. Therefore, the mean over I is
within distance 2ε of at least one of the µJ , for J ∈ U .
We have therefore established our stated duality property for robustness: if a statistic is stable under
taking subsets of data, then it can also be recovered if the data is itself a subset of some larger set of data.
Can we make the above algorithm computationally efficient? First, can we even check if a set J is
α-stable? This involves checking the following constraint:
X
i∈J

ci (xi − µJ )

2

≤ εkck1 for all c such that ci ∈ {0, 1},

X
i∈J

1
ci ≥ α2 n.
2

(103)

It is already unclear how to check this constraint efficiently. However, defining the matrix Cij = ci cj ∈
[0, 1]J×J , we can take a semi-definite relaxation of C, resulting in the constraints Cij ∈ [0, 1] and tr(C) ≥
1 2
⊤
2 α n. Letting Aij = (xi − µJ ) (xj − µJ ), this results in the following sufficient condition for α-stability:
tr(A⊤ C) ≤ ε2 tr(C)2 for all C such that
1
C  0, Cij ∈ [0, 1], tr(C) ≥ α2 n.
2
Specifically, k sets of size αn with pairwise overlap 12 α2 n must have a union of size at least kαn −
k ≤ α2 .
5

34

(104)
1 k
2 2

 2
α n, which implies

This is still non-convex due to the presence of tr(C)2 . However, a sufficient condition for (104) to hold is
that tr(A⊤ C) ≤ 12 ε2 α2 n tr(C) for all C  0, which is equivalent to kAkop ≤ 12 ε2 α2 n, or, letting X be the
q


2
√1 kXkop , where √1 kXkop is essentially our definition of S.
·
matrix with rows xi − µJ , ε ≥
α
αn
√ αn
From this, we can directly see why S/ α appears in our bounds: it is a convex relaxation of the α-stability
condition. Our main optimization (4) can (somewhat less directly) also be thought of as a semidefinite
relaxation which attempts to represent the means of all α2 of the α-stable sets simultaneously (this is done
implicitly, via the major axes of the ellipse Y ).
As an aside, we note that the above discussion, together with the bound (Lemma B.3) on the operator norm of samples from a sub-Gaussian distribution, implies that a set of samples from a sub-Gaussian
distribution is α-stable with high probability, and in particular the mean of any large subset of samples is
close to the mean of the overall set. Moreover, even if a distribution has only bounded second moments,
Proposition B.1 shows that a suitable subset of samples from the distribution will be α-stable.

9 Applications
In this section we present several applications of our main results.

9.1 Gaussians and Mixtures of sub-Gaussians
For robustly learning the mean of a distribution with bounded variance, we have the following result:
Corollary 9.1. Let p∗ be a distribution on Rd with mean µ and bounded covariance: Covp∗ [x]  σ 2 I.
Suppose that we observe n ≥ αd points, of which αn are drawn from p∗ . Then, for any ε ≤ 12 , with
1
⌋, such
probability 1 − exp(−Ω(ε2 αn)), it is possible to output parameters ŵ1 , . . . , ŵm , where m ≤ ⌊ α−ε
 q

log(2/α)
σ
that minm
.
j=1 kŵj − µk2 ≤ O
ε
α
Proof. Define fi (w) = kw − xi k22 , which is 1-strongly convex and has w∗ = µ. In this case, ∇fi (w) −
∇f¯(w) = xi − µ, and so Proposition B.1 implies that with probability 1 − exp(−Ω(ε2 αn)) there is a subset
√
of (1 − ε/2)αn of the good points satisfying S = O (σ/ ε), and hence (by Lemma 5.6) Sε/2 = O (σ/ε).
1
1
Theorem 6.1 then says that we can output parameters ŵ1 , . . . , ŵm , where m ≤ ⌊ (1−ε/2)
2 α ⌋ ≤ ⌊ (1−ε)α ⌋,

 q
log(2/α)
σ
, as was to be shown.
such that minm
j=1 kŵj − µk2 ≤ O
ε
α
For robustly learning a mixture of distributions, we have the following result:
Corollary 9.2. Suppose we are given n samples, where each sample either comes from one of k subGaussian distributions p∗1 , . . . , p∗k (with Covp∗i [x]  σ 2 I), or is arbitrary. Let Ii , αi , and µi denote respectively the set of points drawn from p∗i , the fraction of points drawn from p∗i , and the mean of p∗i , and let
α = minki=1 αi . Suppose that n ≥ αd . Then for any ε ≤ 12 , with probability 1 − k exp(−Ω(ε2 αn)), we can
output a partition T1 , . . . , Tm of [n] and candidate means µ̂1 , . . . , µ̂m such that:
1
⌋.
1. m ≤ ⌊ (1−ε)α

2. For all
but εαi n of the elements of h of Ii , h is assigned a partition Tj such that kµi − µ̂j k2 ≤
 q

O σε log(2/α)
, where O(·) masks only absolute constants.
α
35

Proof. We apply Theorem 6.1 in the same way as in Corollary 9.1, letting the candidate means q
µ̂ , . . . , µ̂m
 1

be the cluster centers U output by Algorithm 4. For each i, we then know that kµ̂j −µi k2 ≤ O σε log(2/α)
α

for atq
least one of the means µ̂j .6 Moreover, we know that the ŵh output by Algorithm 4 satisfy kŵh −µi k2 ≤


for all but εαi n elements of h ∈ Ii . We can therefore define Tj to be the set of h for which
O σε log(2/α)
α
ŵh is closer to µ̂j than to any of the other µ̂j ′ . It is then easy to see that any h ∈ Ii which is close to wi will
be assigned a mean µ̂j that is also close to wi . This yields the desired result.
For the planted partition model, we have the following result:
Corollary 9.3. Let I1 , . . . , Ik be disjoint subsets of [n], and consider the following random directed graph
with vertex set [n]:
• If u, v ∈ Ii , the probability of an edge from u to v is na .
• If u ∈ Ii , v 6∈ Ii , the probability of an edge from u to v is nb .
• If u 6∈ ∪ki=1 Ii , the edges emanating from u can be arbitrary.
Let α = minki=1
4
α,

|Ii |
n .

Then with probability 1 − k exp(−Ω(αn)), we canoutput setsT1 , . . . , Tm ⊆ [n], with

m≤
such that for all i ∈ [k], there is a j ∈ [m] with |Ii △Tj | ≤ O
symmetric difference of two sets.

a log(2/α)
n
α2 (a−b)2

, where △ denotes the

Proof. It turns out that this problem reduces to mean estimation as well, though we will need to be more
careful in how we apply our matrix concentration bound.
P
Let A be the adjacency matrix of the graph. We will let fu (w) = kw − Au k22 = nv=1 (wv − Auv )2 .
matrix with
Note that for u ∈ Ii , we have µi = E[Auv ] = nb + a−b
n I[v ∈ Ii ], and Cov[Au ] is a diagonal
pa
a
b
a
entries that are all either n or n , so that in particular k Cov[Au ]kop ≤ n , and hence σ = n .
In this case we have d = n,
Proposition
 so
 B.1 implies that we can find a subset of Ii of size at least
q
pa
d
1
=O
|Ii |/2 ≥ α2 n such that S = O σ 1 + αn
αn . Invoking Theorem 6.1 with ε = 2 , we obtain

 2


a log(2/α)
candidate means µ̂1 , . . . , µ̂m , with m ≤ α4 , such that kµi − µ̂j k22 ≤ O S log(2/α)
.
=
O
2
α
α n

Now, we define the set Tj such that u ∈ Tj iff (µ̂j )u ≥ a+b
2n . Suppose for some u, u ∈ Ii but u 6∈ Tj .
a
a+b
Then we must have (µ̂j )u < 2n , but (µi )u = n . Therefore, any u ∈ Ii with u 6∈ Tj contributes at least
(a−b)2
4n2

2

to kµi − µ̂j k22 . Similarly, any u ∈ Tj with u 6∈ Ii similarly contributed at least (a−b)
. We can

 4n2
(a−b)2
a log(2/α)
2
2
conclude that kµi − µ̂j k2 ≥ 4n2 |Ii △Tj |. In particular, if kµi − µ̂j k2 = O
, then |Ii △Tj | =
α2 n


O aαlog(2/α)
2 (a−b)2 n , as was to be shown.

Finally, we have the following corollary for density modeling:

Corollary 9.4. Let pθ (x) = exp θ ⊤ φ(x) − A(θ) , where A(θ) is the log-normalization constant. Let
x1 , . . . , xn be points such that αn are drawn from p∗ , and Covp∗ [φ(x)]  σ 2 I. Also suppose that φ(x) ∈ Rd
and n ≥ αd . Then with probability 1 − exp(−Ω(αn)), the following hold:

6
One might worry that, because different hyper-parameters are needed for different values of α, a single instance of Algorithm 4
cannot find all of the µi for different i. However, Algorithm 4 will run correctly given any α ≤ |Igood |/n, so we can in fact recover
all the µi simultaneously.

36

 

• Given a single verified sample x ∼ p∗ , we can output θ̂ such that E[KL pθ∗ k pθ̂ ≤ O √σrα ], where
θ ∗ is the minimizer of E[− log pθ (x)].


• We can output m = O log(2/δ)
candidates θ̂j such that, with probability 1−δ, minm
j=1 E[KL (pθ ∗ k pθ̂j )]
α
 
is at most O √σrα .

Note that KL (pθ∗ k pθ ) = (θ ∗ − θ)⊤ µ + A(θ) − A(θ ∗ ), where µ = E[φ(x)], so Corollary 9.4 roughly
asks for θ to have large inner product with µ, but with the additional goal of keeping A(θ) small.

¯
Proof of Corollary 9.4. Define the loss fi (θ) = − log pθ (xi ) = A(θ) − θ ⊤ φ(xi ). We observe
 that f (θ) −
∗
∗
⊤
∗
∗
⊤
∗
¯
f (θ ) = Ep∗ [(θ − θ) φ(x) + A(θ) − A(θ )] = (θ − θ) µ + A(θ) − A(θ ) = KL pθ∗ k pθ̂ , so bounding
KL (pθ∗ k pθ ) is equivalent to bounding f¯(θ) − f¯(θ ∗ ).
Note that ∇fi (θ) − ∇f¯(θ) = xi − µ. Therefore, Proposition B.1 implies that with probability 1 −
exp(−Ω(αn)) there is a set of at least α2 n samples xi with spectral norm bound S = O (σ). Theorem 4.1
then
that we obtain an ellipse EŶ and samples θ̂1:n such that θ̂i θ̂i⊤  Ŷ and f¯(θ̂avg ) − f¯(θ ∗ ) ≤

 implies
O

σr
√
α

.

Now take a single verified sample x ∼ p∗ , and define θ̂ = arg minθ∈EY A(θ) − θ ⊤ φ(x). Similarly to
Lemma 2.4, we have
f¯(θ̂) − f¯(θ ∗ ) = (θ̂ ∗ − θ)⊤ µ + A(θ̂) − A(θ ∗ )
∗

⊤

∗

(105)
⊤

∗

= (θ − θ̂) (µ − φ(x)) + (θ − θ̂) φ(x) + A(θ̂) − A(θ )

(106)

≤ (θ ∗ − θ̂)⊤ (µ − φ(x)),

(107)

(i)

where (i) is because θ̂ minimizes the right-hand term in (106). On the other hand, we have
Ex [((θ ∗ − θ̂)⊤ (µ − φ(x)))2 ] = Ex [(µ − φ(x))⊤ (θ ∗ − θ̂)(θ ∗ − θ̂)⊤ (µ − φ(x))]
≤ 4Ex [(µ − φ(x))⊤ Ŷ (µ − φ(x))]
⊤

= 4 tr(Cov[φ(x)] Ŷ )
2

(108)
(109)
(110)

≤ 4σ tr(Ŷ )
(111)
 2 2
σ r
.
(112)
=O
α
 
In particular, E[(θ ∗ − θ̂)⊤ (µ − φ(x))] = O √σrα , which together with the preceding inequality yields the
desired bound in f¯(θ̂) − f¯(θ ∗ ).
The above gives us the desired result in the semi-verified model. But then, we can reduce the semiverified model to the list decodable model by sampling random points from the untrusted data, which gives
us the list decodable result as well.

A

Padded Decompositions

The following lemma is essentially from Fakcharoenphol et al. (2003).

37

Lemma A.1. Let x1 , . . . , xn be points in a metric space, and let I ⊆ [n] be such that d(xi , xj ) ≤ r for all
i, j ∈ I. Consider the following procedure:
• Initialize X = {1, . . . , n}, P = ∅, and sample k uniformly from 2 to kmax , where kmax ≥ 1 +
n
1
δ log( |I| ).
• While there are points remaining in S:
– Sample i uniformly from {1, . . . , n}

– Let T be the set of points in X within distance kr of xi .
– Update X ← X\T , P = P ∪ {T }.
• Output the partition P.
Then, with probability at least 1 − δ, all elements of I are in a single element of P.
Proof. It suffices to show the following: if T contains any element of I, then with probability at least 34 it
contains all elements of I.
To see this, let N (k) denote the set of points within distance kr of at least one point in I. Then, for a
fixed k, the probability that T intersects I is |Nn(k)| ; but since all points in I are within distance r of each
def

other, the probability that T contains all of I is at least |N (k−1)|
. Letting ak = |N (k)|, the conditional
n
a
probability that T contains I, given that it intersects I, is therefore at least k−1
ak . Marginalizing over k, the
probability is at least
1
kmax − 1

kX
max
k=2

(i)

ak−1
≥
ak
≥



kY
max
k=2

|I|
n

ak−1
ak



!k

1
max −1

(113)

δ
log(n/|I|)

= e−δ ≥ 1 − δ,

(114)
(115)

as was to be shown. Here (i) is the good old AM-GM inequality.

B Matrix Concentration Bounds
B.1

Concentration from Second Moments

The following is proved using techniques from Batson et al. (2012). However, the bound itself appears to be
novel.
Proposition B.1. Suppose that p is a distribution on Rd 
with Ep[X] = µ and Covp [X]  σ 2 I for some σ.
2

Then, given n samples from p, with probability 1 − exp − ε16n there is a subset J ⊆ [n] of size at least
 P



1
d
⊤ ≤ 4σ2 1 +
(1 − ε)n such that λmax |J|
(x
−
µ)(x
−
µ)
i
i
i∈J
ε
(1−ε)n .

Proof. Without loss of generality we will take µ = 0. Our proof relies on the following claim:

Lemma B.2. For a matrix M , suppose that M ≺ cI and tr (cI − M )−1 ≤ 4σ1 2 . Then, for x ∼ p, with
probability at least 1− 2ε we have M + εxx⊤ ≺ (c+ 4σ 2 )I and tr ((c + 4σ 2 )I − (M + εxx⊤ ))−1 ≤ 4σ1 2 .
38

We prove this claim below, first showing how Proposition B.1 follows from the claim. We will go
through the stream of n samples, and keep a running set J and matrix M . Initially J = ∅ and M = 0. For
each index i in the stream, we will add i to J (and update M to M + εxi x⊤
i ) if the conclusion of Lemma B.2
holds for c = 4σ 2 (d + |J|). Note that then, by induction, the precondition of Lemma B.2 always holds for
c = 4σ 2 (d + |J|), since it holds when J = ∅ and the condition for adding i to J ensures that it continues to
hold.
At the end of the stream, we therefore obtain J and M such that M  4σ 2 (d + |J|)I, which implies
d
1 P
4σ2
1
⊤
1 + |J|
that λmax ( |J|
. It remains to show that |J| ≥ (1 − ε)n with
i∈J xi xi ) = ε|J| λmax (M ) ≤ ε
high probability.
To see this, note that for each element i, |J| increases by 1 with probability at least 1− 2ε . The distribution
ε
of |J| is therefore lower-bounded by the sum of n independent Bernoulli variables
 with bias 1 − 2 , which
2

by the Chernoff bound is greater than (1 − ε)n with probability at least 1 − exp − ε16n .

Proof of Lemma B.2. This is essentially Lemma 3.3 of Batson et al. (2012). Instead of M + εxx⊤ , it will
be helpful later to consider consider M + txx⊤ for arbitrary t ∈ [0, ε]. By the Sherman-Morrison matrix
inversion formula, we have

((c + 4σ 2 )I − M )−1 xx⊤ ((c + 4σ 2 )I − M )−1
.
1 − tx⊤ ((c + 4σ 2 )I − M )−1 x
(116)
Therefore, letting Φc (M ) denote tr((cI − M )−1 ), we have
((c + 4σ 2 )I − M − txx⊤ )−1 = ((c + 4σ 2 )I − M )−1 + t

Φc+4σ2 (M + txx⊤ ) = Φc+4σ2 (M ) +

x⊤ ((c + 4σ 2 )I − M )−2 x
.
1/t − x⊤ ((c + 4σ 2 )I − M )−1 x

(117)

We want to have Φc+4σ2 I (M + txx⊤ ) ≤ Φc (M ), which in light of the above is equivalent to the condition
1 ? ⊤
x⊤ ((c + 4σ 2 )I − M )−2 x
≥ x ((c + 4σ 2 )I − M )−1 x +
.
t
Φc (M ) − Φc+4σ2 (M )

(118)

Let us compute the expectation of the right-hand-side. Since E[x⊤ Ax] = tr(A⊤ Cov[x]) and Cov[x]  σ 2 I,
the right-hand-side of (118) has expectation at most
!


 tr ((c + 4σ 2 )I − M )−2
1
2
−1
2
2
+
(119)
≤ σ Φc+4σ2 (M ) + 2 ,
σ tr ((c + 4σ )I − M )
Φc (M ) − Φc+4σ2 (M )
4σ

where the second step is in light of the inequality

Φc (M ) − Φc+4σ2 (M ) = tr (cI − M )−1 − ((c + 4σ 2 )I − M )−1

≥ 4σ 2 tr ((c + 4σ 2 )I − M )−2 .



Since Φc+4σ2 (M ) ≤ Φc (M ) ≤ 4σ1 2 , the right-hand-side of (118) is at most 21 in expectation. Therefore,
with probability at least 1 − 2ε , it is at most 1ε , in which case (118) holds for all t ∈ [0, ε]. 
This certainly implies that Φc+4σ2 (M + εxx⊤ ) = tr ((c + 4σ 2 )I − (M + εxx⊤ ))−1 ≤ 4σ1 2 . Moreover, we also have that Φc+4σ2 (M + txx⊤ ) ≤ 4σ1 2 < ∞ for all t ∈ [0, ε]. Since the eigenvalues of
M + txx⊤ are a continuous function of t, we therefore know that the maximum eigenvalue of M + txx⊤
never crosses c + 4σ 2 for t ∈ [0, ε], and so M + εxx⊤ ≺ (c + 4σ 2 )I as well (since M ≺ cI ≺ (c + 4σ 2 )I
by assumption).
39

B.2

Concentration for sub-Gaussians

In this section we provide a matrix concentration result for sub-Gaussian variables, which underlies Lemma 5.5.
The proofs closely mirrors Theorem 5.39 of Vershynin (2010).
d
Lemma
 2 B.3. Let p be a distribution over vectors X ∈ R such that (i) E[X] = 0, and (ii) E[exp (hλ, Xi)] ≤
exp σ2 kλk22 for some constant σ. Then, if M is an m × d matrix with each row drawn i.i.d. from p, with
probability 1 − δ the following holds simultaneous for all subsets T of the rows of M with |T | ≥ s:

kMT k2op ≤ 18σ 2 (d + s log(e/β) + log(1/δ)) ,

(120)

kMT k2op − Q
,
|T |
|T |≥s

(121)

where β = s/m.
Proof. We will bound
max

where Q = 18σ 2 (d + log(1/δ)).
Let N be a (1/4)-net of the sphere S d−1 , meaning that all points in S d−1 are within distance at most 41
of a point in N . As shown in Vershynin (2010), N can be taken to have size at most 9d , and moreover one
has maxu∈N 2kMT uk22 ≥ maxkuk2 ≤1 kMT uk22 = kMT k2op . Using these results, we can bound (121) as
kMT k2op − Q
2kMT uk22 − Q
≤ max max
u∈N |T |≥s
|T |
|T |
|T |≥s
!

X
2
hMi , ui2 − Q/2 .
= max max
s u∈N |T |=s
max

(122)
(123)

i∈T


We will focus on bounding the inner expression for a fixed T , then union bound over the 9d m
s possibilities
2
⊤
2
for |T
E[exp (λhMi , ui)] ≤
 | 2andu. Let Zi = hMi , ui . Note that E[Zi ] = u Cov[X]u ≤ σ . In addition, 

σ
2
2
exp 2 λ (since kuk2 = 1), and so (see Lemma C.3) we have E[exp λ Zi − σ ] ≤ exp 16σ 4 λ2



P
for 0 ≤ λ ≤ 4σ1 2 . By independence, it follows that E exp λ i∈T (Zi − σ 2 ) ≤ exp 16sσ 4 λ2 , again
for 0 ≤ λ ≤ 4σ1 2 . By a Chernoff argument, at λ = 4σ1 2 , we obtain
#
"


X
t
2
2
(hMi , ui) ≥ sσ + t ≤ exp s −
P
.
(124)
4σ
i∈T

We need the right-hand-side to be smaller than

δ
,
9d (m
s)

for which we can take

t = 4σ 2 (d log(9) + s + s log(me/s) + log(1/δ))
≤ 4σ 2 (2.2d + s + s log(e/β) + log(1/δ)) .
Overall, we have that with probability 1 − δ,
X
(hMi , ui)2 ≤ σ 2 (8.8d + 5s + 4s log(e/β) + 4 log(1/δ))

(125)
(126)

(127)

i∈T

≤ 9σ 2 (d + s log(e/β) + log(1/δ))

(128)

for all T of size s and all u ∈ N . In particular, (123) can be bounded by 18σ 2 log(e/β), which completes
the proof.
40

C

Deferred Proofs

C.1 Bounding Quadratics
Lemma C.1. Suppose that z ≤ a +

√

bz + c2 where a, b, c, ≥ 0. Then, z ≤ 2a + b + c.

Proof. Re-arranging to remove the square-root, we have z 2 − (2a + b)z + (a2 − c2 ) ≤ 0. Now suppose that
z > 2a + b + c. Then, z 2 − (2a + b)z + (a2 − c2 ) = z(z − 2a − b) + (a2 − c2 ) > (2a + b + c)c + (a2 − c2 ) =
a2 + (2a + b)c > 0, which is a contradiction.

C.2 Proof of Lemma 2.1
We omit this as it is a special case of Lemma 5.5, proved below.

C.3 Proof of Lemma 2.4
p
1/q

≤ 2 tr(Y )σq . Let µ = E[x] and Σ = Cov[x].
We start by showing that E supw∈EY |f (w) − f¯(w)|q
We have
#
"
#
"
(129)
Ef sup |f (w) − f¯(w)|q = Ex sup |φ(w⊤ x) − Ex′ [φ(w⊤ x′ )]|q
w∈EY

w∈EY

= Ex
(i)

≤ Ex

(ii)

"

≤ Ex

= Ex

⊤ ′

⊤

⊤ ′ 2 q/2

sup Ex′ [|φ(w x) − φ(w x )| ]

w∈EY

"

"

q

sup |Ex′ [φ(w x) − φ(w x )]|

w∈EY

"

#

⊤

⊤

′

2 q/2

sup Ex′ [(w (x − x )) ]

w∈EY

#

(130)
#

 q/2


sup w⊤ Σ + (x − µ)(x − µ)⊤ w

w∈EY

(131)
(132)
#

i


h
≤ Ex tr(Y ⊤ Σ + (x − µ)(x − µ)⊤ )q/2


(iv)
⊤
q/2
⊤
q/2
q/2−1
tr(Y Σ) + Ex [((x − µ) Y (x − µ)) ] ,
≤ 2

(iii)

(133)
(134)
(135)

where (i) and (iv) are applications of the power mean inequality, (ii) is because φ is 1-Lipschitz, and (iii) is
because ww⊤  Y .
On the other hand, we have Σ  σq2 I by the qth moment condition (since q > 2), so tr(Y ⊤ Σ)q/2 ≤
P
tr(Y )q/2 σqq . Also, letting Y = i λi vi vi⊤ be the eigendecomposition of Y , we have
q/2 i
h X
(136)
λi (vi⊤ (x − µ))2
Ex [((x − µ)⊤ Y (x − µ))q/2 ] = Ex
i

(v)

≤ tr(Y )q/2−1 Ex

(vi)

≤ tr(Y )q/2 σqq ,
41

"

X
i

λi (vi⊤ (x − µ))q

#

(137)
(138)

where (v) is again the power mean inequality
and (vi) uses the qth
moment bound E[(vi⊤ (x − µ))q ] ≤ σqq .


Combining these, we obtain Ef supw∈EY |f (w) − f¯(w)|q ≤ (2 tr(Y ))q/2 σqq . To finish, we simply
apply Markov’s inequality to this statistic to get a tail bound on supw∈EY |f (w) − f¯(w)|, after which the
result follows from a standard uniform convergence argument.

C.4 Proof of Lemma 3.1
By duality of operator and trace norm, we have (letting zi be the ith row of the matrix Z)
kWT k2∗ =

sup tr(WT⊤ Z)2

kZkop ≤1

=

X

sup
kZkop ≤1

(i)

≤

i∈T

sup |T |

kZkop ≤1

sup |T |

=

kZkop ≤1
(ii)

≤

=

wi⊤ zi

!2

X
(wi⊤ zi )2
i∈T

X
i∈T

sup |T |

kZkop ≤1

(139)



wi⊤ zi zi⊤ wi

X

tr(Y zi zi⊤ )

(140)
(141)
(142)
(143)

i∈T

sup |T | tr(Y Z ⊤ Z)

(144)

kZkop ≤1

= |T | tr(Y ),

(145)

as was to be shown. Here (i) is Cauchy-Schwarz and (ii) uses the fact that wi wi  Y .

C.5 Proof of Lemma 4.6
Let F be the matrix whose ith row is ∇fi (w0 ) − ∇f¯(w0 ), and let W be the matrix whose ith row is wi . We
consider only the rows i ∈ Igood , so each matrix is αn × d. We have
X

i∈Igood

ci h∇fi (w0 ) − ∇f¯(w0 ), wi i = tr(F ⊤ diag(c)W )
≤ k diag(c)F kop kW k∗

(146)
(147)

by Hölder’s inequality. Furthermore, k diag(c)F kop ≤ k p
diag(c)kop kF kop ≤
p kF kop , and furthermore
√
kF kop ≤ αnS by the definition of S. Finally, kW k∗p≤ |Igood | tr(Y ) = αn tr(Y ) by Lemma 3.1.
Combining these, we see that (147) is bounded by αnS tr(Y ), as was to be shown.

C.6 Proof of Lemma 5.5
Proof. Define Sε (w) as

def

Sε (w) =



1
p k ∇fi (w) − ∇f¯(w) i∈T kop .
|T |≥⌊εαn⌋
|T |
max

42

(148)

By Lemma B.3 below, at any fixed w it is the case that
r
Sε (w) ≤ 6σ

log(e/ε) +

d + log(1/δ)
.
εαn

(149)

On the other hand, because ∇fi (w) − ∇f¯(w) is L-Lipschitz in w, one can check that Sε (w) is also
L-Lipschitz
in w (see Lemma C.2
 below). In particular, around any fixed w, it holds that Sε (w) ≤

q
d
for all w′ with kw′ − wk2 ≤ Lσ . But we can cover H with 1 + 2rL
σ 1 + 6 log(e/ε) + d+log(1/δ)
εαn
σ
balls of radius
have

σ
L.

Therefore, a union bound argument yields that, with probability 1 − δ, for all w ∈ H we
s



2rL
σ

+ log(1/δ)
d 1 + log 1 +

εαn
s
 


rL
p
d max 1, log σ + log(1/δ)
 ,
= O σ  log(2/ε) +
εαn

Sε (w) ≤ σ 1 + 6 log(e/ε) +

as was to be shown.





(150)

(151)

Lemma C.2. If ∇fi (w) − ∇f¯(w) is L-Lipschitz in w, then Sε (w) is also L-Lipschitz in w.


∇fi (w) − ∇f¯(w) i∈T
is L-Lipschitz for each T , since the max
Proof. It suffices to show that √1
|T |

op

of Lipschitz functions is Lipschitz. To show this, let ∆i (w) denote ∇fi (w) − ∇f¯(w), and note that
1
p
|T |

[∆i (w)]i∈T

−
op




∆i (w′ ) i∈T



1
∆i (w) − ∆i (w′ ) i∈T
≤ p
|T |
(ii)


1
≤ p
∆i (w) − ∆i (w′ ) i∈T
|T |
s
1 X
k∆i (w) − ∆i (w′ )k22
=
|T |
i∈T
s
(iii)
1 X 2
L kw − w′ k22
≤
|T |
(i)

op

op

F

i∈T
′

= Lkw − w k2 ,

(152)
(153)
(154)

(155)
(156)

as was to be shown. Here (i) is the triangle inequality for the operator norm, (ii) is because Frobenius norm
is larger than operator norm, and (iii) invokes the assumed Lipschitz property for ∆i (w).

C.7 Proof of Lemma 7.3
Recall that p∗ = N (µ, Σ0 − λµµ⊤ ) and p̂ = N (0, Σ0 ). We want to show that αp∗ ≤ p̂, which is equivalent
to (by expanding the density formula for a Gaussian distribution)
?

⊤ −1
(x − µ)⊤ (Σ0 − λµµ⊤ )−1 (x − µ) − x⊤ Σ−1
0 x + log det(I − λµµ Σ0 ) ≥ 2 log(α) for all x.

43

(157)

⊤ −1
Let us simplify the above quadratic in x. Letting s = x⊤ Σ−1
0 µ and t = µ Σ0 µ, we have

(x − µ)⊤ (Σ0 − λµµ⊤ )−1 (x − µ) − x⊤ Σ−1
(158)
0 x


⊤ −1
Σ−1
(i)
0 µµ Σ0
= (x − µ)⊤ Σ−1
(x − µ) − x⊤ Σ−1
(159)
0 x
0 +λ
1 − λµ⊤ Σ−1
µ
0

 
⊤ −1
2 
2
(x⊤ Σ−1
(µ⊤ Σ−1
(x⊤ Σ−1
(ii)
⊤ −1
⊤ −1
0 µ)(µ Σ0 µ)
0 µ)
0 µ)
− 2 x Σ0 µ + λ
+ µ Σ0 µ + λ
= λ
1 − λµ⊤ Σ−1
1 − λµ⊤ Σ−1
1 − λµ⊤ Σ−1
0 µ
0 µ
0 µ
(160)




s2
λst
t2
=λ
−2 s+
+ t+λ
(161)
1 − λt
1 − λt
1 − λt

1
λs2 − 2s + t ,
(162)
=
1 − λt

where (i) is the Woodbury matrix inversion lemma, and (ii) is expanding the quadratic. The minimizing
value of s is λ1 , so that we obtain a lower bound (over all x) of


−1

1
1
1
⊤ −1
⊤
⊤
− +t =− .
(x − µ) − x Σ0 x ≥
(x − µ) Σ0 − λµµ
1 − λt
λ
λ
Plugging back into (157), we obtain the condition
−

?
1
+ log det(I − λµµ⊤ Σ−1
0 ) ≥ 2 log(α).
λ

(163)

Simplifying further and again letting t = µ⊤ Σ−1
0 µ, we have
−

so it suffices to have

1
1
⊤ −1
+ log det(I − λµµ⊤ Σ−1
0 ) = − + log(1 − λµ Σ0 µ)
λ
λ
1
= − + log(1 − λt)
λ
1
λt
≥− −
,
λ 1 − λt

1
λt
λ + 1−λt

log( α1 ), or equivalently t ≤

≤ 2 log( α1 ). Now, we will take λ =

1
log2 ( α
)
1
1+log( α
)

1
1 ,
log( α
)

(164)
(165)
(166)

in which case we need

t
1
log( α
)−t

≤

, as claimed.

C.8 Bounding the square of a sub-Gaussian
Lemma C.3. Suppose that Z is a random variable satisfying E[exp (λX)] ≤ exp
Z 2 − E[Z 2 ] satisfies
for |λ| ≤

1
4σ2 .

E[exp (λY )] ≤ exp 16σ 4 λ2

44





σ2 2
2 λ


. Then, Y =
(167)

Proof. We begin by bounding the moments of Z. We have, for any p ≥ 0 and u,

E [|Z|p ] = E [exp (p log |Z|)]

 

(i)
1
≤ E exp p log a + |Z| − 1
a

 




(ii)
1
1
+ exp p log a − Z − 1
≤ E exp p log a + Z − 1
a
a
 p i
h

p 
Z + exp − Z
= E exp (p (log a − 1)) exp
a
a
 2 2
(iii)
p σ
≤ 2 exp (p (log a − 1)) exp
.
2a2

(168)
(169)
(170)
(171)
(172)

Here (i) uses the inequality log(z) − log(a) ≤ a1 (z − a) (by concavity of log), while (iii) simply invokes
the sub-Gaussian assumption at λ = ap . The inequality (ii) is used to move from |Z| to Z.
√
We will take the particular value a = pσ, which yields
 

1
1
p
E [|Z| ] ≤ 2 exp p
log p + log(σ) −
(173)
2
2


1
= 2σ p exp
p (log(p) − 1) .
(174)
2
Now, letting u = E[Z 2 ], we have
E[|Z 2 − u|p ] ≤ 2p−1 E[|Z|2p ] + up
p−1

≤2

2σ

2p



exp (p(log(2p) − 1)) + σ

2p

≤ 2p+1 σ 2p exp (p(log(2p) − 1)) .



(175)
(176)
(177)

Hence,

E[exp (λY )] = E[exp λ(Z 2 − u) ]
∞
X
|λ|p
E[|Z 2 − u|p ]
≤1+
p!

(178)
(179)

p=2

(177)

≤ 1+2

≤1+2
=1+2
≤1+2
=1+
Clearly, when |λ| ≤

1
,
4σ2

∞
X
(2|λ|σ 2 )p

p=2
∞
X
p=2

∞
X

p=2
∞
X

p!

exp (p(log(2p) − 1))

(180)

(2|λ|σ 2 )p exp (p(log(2p) − 1) − p log(p))

(181)

(2|λ|σ 2 )p exp (p(log(2) − 1))

(182)

(2|λ|σ 2 )p

(183)

p=2

8λ2 σ 4
.
1 − 2|λ|σ 2

(184)


the above is bounded by 1 + 16λ2 σ 4 ≤ exp 16σ 4 λ2 , as claimed.
45

References
E. Abbe and C. Sandon. Community detection in general stochastic block models: fundamental limits and
efficient recovery algorithms. arXiv, 2015a.
E. Abbe and C. Sandon. Detection in the stochastic block model with multiple clusters: proof of the
achievability conjectures, acyclic BP, and the information-computation gap. arXiv, 2015b.
D. Achlioptas and F. McSherry. On spectral learning of mixtures of distributions. In Conference on Learning
Theory (COLT), 2005.
N. Agarwal, A. S. Bandeira, K. Koiliaris, and A. Kolla. Multisection in the stochastic block model using
semidefinite programming. arXiv, 2015.
P. Awasthi and O. Sheffet. Improved spectral-norm bounds for clustering. Approximation, Randomization,
and Combinatorial Optimization, pages 37–49, 2012.
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.
M. Balcan, A. Blum, and S. Vempala. A discriminative framework for clustering via similarity functions. In
Symposium on Theory of Computing (STOC), pages 671–680, 2008.
M. F. Balcan, H. Röglin, and S. Teng. Agnostic clustering. In International Conference on Algorithmic
Learning Theory, pages 384–398, 2009.
J. Batson, D. A. Spielman, and N. Srivastava. Twice-Ramanujan sparsifiers. SIAM Journal on Computing,
41(6):1704–1721, 2012.
K. Bhatia, P. Jain, and P. Kar. Robust regression via hard thresholding. In Advances in Neural Information
Processing Systems (NIPS), pages 721–729, 2015.
A. Blum and J. Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19
(2):204–234, 1995.
T. T. Cai and X. Li. Robust and computationally feasible community detection in the presence of arbitrary
outlier nodes. The Annals of Statistics, 43(3):1027–1059, 2015.
E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM, 58
(3), 2011.
V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence for matrix
decomposition. SIAM Journal on Optimization, 21(2):572–596, 2011.
O. Chapelle, A. Zien, and B. Scholkopf. Semi-Supervised Learning. MIT Press, 2006.
Y. Chen, A. Jalali, S. Sanghavi, and H. Xu. Clustering partially observed graphs via convex optimization.
Journal of Machine Learning Research (JMLR), 15:2213–2238, 2014a.
Y. Chen, S. Sanghavi, and H. Xu. Improved graph clustering. IEEE Transactions on Information Theory,
60(10):6440–6455, 2014b.
46

A. Coja-Oghlan. Coloring semirandom graphs optimally. Automata, Languages and Programming, pages
71–100, 2004.
A. Coja-Oghlan. Solving NP-hard semirandom graph problems in polynomial expected time. Journal of
Algorithms, 62(1):19–46, 2007.
I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high dimensions
without the computational intractability. In Foundations of Computer Science (FOCS), 2016.
J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics.
In Symposium on Theory of Computing (STOC), pages 448–455, 2003.
U. Feige and J. Kilian. Heuristics for semirandom graph problems. Journal of Computer and System
Sciences, 63(4):639–671, 2001.
U. Feige and R. Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph. Random
Structures and Algorithms, 16(2):195–208, 2000.
V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami. On agnostic learning of parities, monomials, and
halfspaces. SIAM Journal on Computing, 39(2):606–645, 2009.
O. Guédon and R. Vershynin. Community detection in sparse networks via Grothendieck’s inequality. arXiv,
2014.
V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. SIAM Journal on Computing, 39(2):742–765, 2009.
F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust Statistics: The Approach Based
on Influence Functions. Wiley, 2011.
M. Hardt and A. Moitra. Algorithms and hardness for robust subspace recovery. In Conference on Learning
Theory (COLT), 2013.
P. J. Huber and E. M. Ronchetti. Robust Statistics. Wiley, 2009.
M. Kearns and M. Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):
807–837, 1993.
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.
M. Krivelevich and D. Vilenchik. Semirandom models as benchmarks for coloring algorithms. In Meeting
on Analytic Algorithmics and Combinatorics, pages 211–221, 2006.
A. Kumar and R. Kannan. Clustering with spectral norm and the k-means algorithm. In Foundations of
Computer Science (FOCS), pages 299–308, 2010.
S. Kushagra, S. Samadi, and S. Ben-David. Finding meaningful cluster structure amidst background noise.
In International Conference on Algorithmic Learning Theory, pages 339–354, 2016.
K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In Foundations of
Computer Science (FOCS), 2016.
47

C. M. Le, E. Levina, and R. Vershynin. Concentration and regularization of random graphs. arXiv, 2015.
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Approximation algorithms for semi-random partitioning problems. In Symposium on Theory of Computing (STOC), pages 367–384, 2012.
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Learning communities in the presence of errors.
arXiv, 2015.
F. McSherry. Spectral partitioning of random graphs. In Foundations of Computer Science (FOCS), pages
529–537, 2001.
A. Moitra, W. Perry, and A. S. Wein. How robust are reconstruction thresholds for community detection?
arXiv, 2015.
E. Rebrova and K. Tikhomirov. Coverings of random ellipsoids, and invertibility of matrices with iid heavytailed entries. arXiv, 2015.
E. Rebrova and R. Vershynin. Norms of random matrices: local and global problems. arXiv, 2016.
M. Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis, 164:60–72, 1999.
J. Steinhardt, G. Valiant, and M. Charikar. Avoiding imposters and delinquents: Adversarial crowdsourcing
and peer prediction. In Advances in Neural Information Processing Systems (NIPS), 2016.
J. W. Tukey. A survey of sampling from contaminated distributions. Contributions to probability and
statistics, 2:448–485, 1960.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv, 2010.
H. Xu, C. Caramanis, and S. Mannor. Principal component analysis with contaminated data: The high
dimensional case. arXiv, 2010.
H. Zha, X. He, C. Ding, H. Simon, and M. Gu. Spectral relaxation for k-means clustering. In Advances in
Neural Information Processing Systems (NIPS), pages 1057–1064, 2001.

48

