Robust Sparse Estimation Tasks in High Dimensions

arXiv:1702.05860v2 [cs.LG] 28 Feb 2017

Jerry Li∗
EECS, MIT
jerryzli@mit.edu
March 2, 2017

Abstract
In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high
dimensions, in the robust setting where an ε-fraction of samples are corrupted adversarially. We study the natural
robust version of two classical sparse estimation problems, namely, sparse mean estimation and sparse PCA in the
spiked covariance model. For both of these problems, we provide the first efficient algorithms that provide non-trivial
error guarantees in the presence of noise, using only a number of samples which is similar to the number required for
these problems without noise. In particular, our sample complexities are sublinear in the ambient dimension d. Our
work also suggests evidence for new computational-vs-statistical gaps for these problems (similar to those for sparse
PCA without noise) which only arise in the presence of noise.

1 Introduction
In the last couple of decades, there has been a large amount of work in machine learning and statistics on how to
exploit sparsity in high dimensional data analysis. Motivated by the ever-increasing quantity and dimensionality of
data, the goal at a high level is to utilize the underlying sparsity of natural data to extract meaningful guarantees using
a number of samples that is sublinear in the dimensionality of the data. In this paper, we will consider the unsupervised
setting, where we have sample access to some distribution with some underlying sparsity, and our goal is to recover
this distribution by exploiting this structure. Two natural and well-studied problems in this setting that attempt to
exploit sparsity are sparse mean estimation and sparse PCA. In both problems, the shared theme is that we assume that
one wishes to find a distinguished sparse direction of a Gaussian data set. However, the algorithms inspired by this
line of work tend to be quite brittle—it can be shown that they fail when the model is slightly perturbed.
This connects to a major concern in high dimensional data analysis: that of model misspecification. At a high
level, the worry is that our algorithms should be able to tolerate the case when our assumed model and the true model
do not perfectly coincide. In the distributional setting, this (more or less) corresponds to the regime when a small
fraction of our samples are adversarially corrupted. The study of these so-called robust estimators, i.e., estimators
which work in the presence of such noise, is a classical subfield of statistics. Unfortunately, the classical algorithms
for these problems fail to scale as the dimensionality of the problem grows—either the algorithms run in time which
is exponential in the dimension, or the error guarantees for these algorithms degrade substantially as the dimension
grows. In a flurry of recent work, we now know new algorithms which circumvent this “curse of dimensionality”: they
run efficiently, and provide dimension independent error guarantees. However, these algorithms are unable to exploit
any inherent sparsity in the problem.
This raises the natural “meta-question”:
Question 1.1. Do the statistical gains (achievable by computationally efficient algorithms) for sparse estimation problems persist in the presence of noise?
∗ Supported by NSF grant CCF-1217921, DOE grant de-sc0008923, NSF CAREER Award CCF-145326, and a NSF Graduate Research Fellowship

1

More formally: Suppose we are asked to solve some estimation task given samples from some distribution D with
some underlying sparsity constraint (e.g. sparse PCA). Suppose now an ε-fraction of the samples are corrupted. Can
we still solve the same sparse estimation problem? In this work, we initiate the study of such issues. Interestingly,
new gaps between computational and statistical rates seem to emerge in the presence of noise. In particular, while
the sparse mean estimation problem was previously quite simple to solve, the efficient algorithms which achieve the
minimax rate for this problem break down in the presence of this adversarial noise. More concretely, it seems that
the efficient algorithms which are robust to noise run into the same computational issues as those which plague sparse
PCA. A very interesting question is whether this phenomenon is inherent to any computationally efficient algorithm.

1.1 Our Contribution
We study the natural robust versions of two classical, well-studied statistical tasks involving sparsity, namely, sparse
mean estimation, and sparse PCA.
Robust sparse mean estimation Here, we get a set of d-dimensional samples from N (µ, I), where µ is k-sparse,
and an ε-fraction of the points are corrupted adversarially. Our goal then is to recover µ. Our main contribution is the
following:
Theorem 1.2 (informal, see Theorem 2.1). There is an efficient algorithm, which given a set of ε-corrupted samples of
p
2
d
e k log
size O(
) from N (µ, I) where µ is k-sparse, outputs a µ
b so that with high probability, kb
µ − µk2 ≤ ε log 1/ε.
ε2
p
The
recovery
guarantee
we
achieve,
namely
O(ε
log 1/ε), is off by the optimal guarantee by only a factor of
p
log 1/ε. Moreover, results of [DKS16] imply that our bound is tight for any efficient SQ algorithm. One can show
d
that information theoretically, it suffices to take O( k log
ε2 ) samples to learn the mean to ℓ2 error O(ε), even with
corrupted data. Without model misspecification, this problem is quite simple algorithmically: it turns out that the
truncated empirical mean achieves the information theoretically optimal rate. However, efficient algorithms for this
task break down badly given noise, and to our knowledge there is no simple way of fixing them. Very interestingly, the
rate we achieve is off from this information theoretic rate by a k 2 vs k factor—the same computational vs. statistical
gap that arises in sparse PCA. This phenomenon only seems to appear in the presence of noise, and we conjecture that
this is inherent:
d
e k2 log
) samples.
Conjecture 1.1. Any efficient algorithm for robust sparse mean estimation needs Ω(
ε2

In Appendix D we give some intuition for why it seems to be true. At a high level, it seems that any technique
to detect outliers for the mean must look for sparse directions in which the variance is much larger than it should be;
at which point the problem faces the same computational difficulties as sparse PCA. We leave closing this gap as an
interesting open problem.

Robust sparse PCA Here, we study the natural robust analogue of the spiked covariance model. Classically, two
problems are studied in this setting. The detection problem is given as follows: given sample access to the distributions,
we are asked to distinguish between N (0, I), and N (0, I + ρvv T ) where v is a k-sparse unit vector. That is, we wish
to understand if we can detect the presence of any sparse principal component. Our main result is the following:
p
Theorem 1.3 (informal, see Theorem 2.2). Fix ρ > 0, and let η = O(ε log 1/ε). If ρ > η, there is an efficient
2
d
algorithm, which given a set of ε-corrupted samples of size O( k ρlog
) which distinguishes between N (0, I), and
2
T
N (0, I + ρvv ) with high probability.
e
The condition that ε = O(ρ)
is necessary (up to log factors), as otherwise the problem is impossible information
theoretically. Observe that this (up to log factors) matches the optimal rate for computationally efficient detection for
sparse PCA without noise (under reasonable complexity theoretic assumptions, see [BR13, WBS16]), and so it seems
that noise does not introduce an additional gap here. The recovery problem is similar, except now we want to recover
the planted spike v, i.e. find a u minimizing L(u, v) = √12 kuuT − vv T k, which turns out to be the natural measure
for this problem. For this, we show:
2

p
Theorem 1.4 (informal, see Theorem 2.3). Fix ε > 0 and 0 < ρ = O(1), and let η = O(ε log 1/ε). There is an
2
d
) from N (0, I + ρvv T ), outputs a u so
efficient algorithm, which given a set of ε-corrupted samples of size O( k ηlog
2
 
that L(u, v) = O ηρ with high probability.

This rate is non-trivial—in particular, it provides guarantees for recovery of v when the number of samples we take
is at the detection threshold. Moreover, up to log factors, our rate is optimal for computationally efficient algorithms–
[WBS16] gives an algorithm with rate roughly O(ε/ρ), and show that this is necessary.

Techniques We first introduce a simple way to describe the optimization problems used for solving sparse mean
estimation and sparse PCA. This approach is very similar to the approach taken by [CRPW12] for solving underdetermined linear systems. We observe that any set S in a Hilbert space naturally induces a dual norm kxk∗S =
maxy∈S |hx, yi|, and that well-known efficient algorithms for sparse mean estimation and sparse PCA simply compute
this norm, and the corresponding dual witness y ∈ S which maximizes this norm, for appropriate choices of S.
These norms give us a language to only consider deviations in directions we care about, which allows us to prove
concentration bounds which are not true for more traditional norms.
We now describe our techniques for robust sparse mean estimation. Our starting point is the convex programming
approach of [DKK+ 16]. We assign each sample point a weight, which morally corresponds to our belief about
whether the point is corrupted, and we optimize these weights. In previous work of [DKK+ 16], the approach was to
find weights so that the empirical covariance with these weights looked like the identity in spectral norm.
Unfortunately, such an approach fundamentally fails for us because the spectrum of the covariance will never
concentrate for us with the number of samples we take. Instead, we utilize a novel connection to sparse PCA. We
show that if instead we find weights so that the empirical covariance with these weights looks like the identity in
the dual norm induced by a natural SDP for sparse PCA (in the noiseless setting), then this suffices to show that
the trucnated empirical mean with these weights is close to the truth. We do so by convex programming. While we
cannot explicitly write down the feasible set of weights, it is a convex set. Thus, by the classical theory of convex
optimization, it suffices to give a separation oracle for this convex set to optimize over this set. We show that in fact
the SDP for sparse PCA gives us such a separation oracle, if one is sufficiently careful to always work with sparsity
preserving objects. This in turns suffices to allow us to (approximately) find a point in the desired feasible set of points,
which we show suffices to recover the true mean.
We now turn to robust sparse PCA. We first consider the detection problem, which is somewhat easier technically.
Here, we again use the dual norm induced by the SDP for sparse PCA. We show that if we can find weights on the
samples (as before) so that the empirical covariance with these samples has minimal dual norm, then the value of the
dual norm gives us a distinguisher between the spiked and non-spiked case. To find such a set of weights, we observe
that norms are convex, and thus our objective is convex. Thus, as before, to optimize over this set it suffices to give a
separation oracle, which again the SDP for sparse PCA allows us to do.
We now turn our attention to the recovery problem. Here, the setup is very similar, except now we simultaneously
find a set of weights and an “explainer” matrix A so that the empirical covariance with these weights is “maximally
explained” by A, in a norm very similar to the one induced by the sparse PCA SDP. Utilizing that norms are convex,
we show that this can be done via a convex program using the types of techniques described above, and that the top
eigenvector of the optimal A gives us the desired solution. While the convex program would be quite difficult to write
down in one shot, it is quite easily expressible using the abstraction of dual norms.

1.2 Related Work
As mentioned previously, there has been a large amount of work on various ways to exploit sparsity for machine
learning and statistics. In the supervised setting, perhaps the most well-known of these is compressive sensing and its
variants (see [CW08, HTW15] for more details). We do not attempt to provide an exhaustive overview the field here.
Other well-known problems in the same vein include general classes of linear inverse problems, see [CRPW12] and
matrix completion ([CR12]).
The question of estimating a sparse mean is very related to a classical statistical model known as the Gaussian
sequence model, and the reader is referred to [Tsy09, Joh11, Rig15] for in-depth surveys on the area. This problem
3

has also garnered a lot of attention recently in various distributed and memory-limited settings, see [GMN14, SD15,
BGM+ 16]. The study of sparse PCA was initiated in [Joh01] and since yielded a very rich algorithmic and statistical
theory ([dEGJL07, dBG08, AW08, WTH09, JNRS10, ACCD11, LZ12, Ma13, BJNP13, CMW13, OMH14, GWL14,
CRZ16, BMVX16, PWBM16]). In particular, we highlight a very interesting line of work [BR13, KNV15, MW15,
WGL15, WBS16], which give evidence that any computationally efficient estimator for sparse PCA must suffer a
sub-optimal statistical rate rate. We conjecture that a similar phenomenon occurs when we inject noise into the sparse
mean estimation problem.
In this paper we consider the classical notion of corruption studied in robust statistics, introduced back in the 70’s
in seminal works of [HR09, Tuk75, HRRS86]. Unfortunately, essentially all robust estimators require exponential
time in the dimension to compute ([JP78, Ber06, HM13]). Subsequent work of [LT15, BD15] gave efficient SDPbased estimators for these problems which unfortunately had error guarantees which degraded polynomially with the
dimension. However, a recent flurry of work ([DKK+ 16, LRV16, CSV16, DKK+ 17, DKS17, DKS16]) have given
new, computationally efficient, robust estimators for these problems and other settings which avoid this loss, and are
often almost optimal. Independent work of [DSS17] also considers the robust sparse setting. They give a similar result
for robust mean estimation, and also consider robust sparse PCA, though in a somewhat different setting than we do,
as well as robust sparse linear regression.
The questions we consider are similar to learning in the presence of malicious error studied in [Val85, KL93],
which has received a lot of attention, particularly in the setting of learning halfspaces ([Ser03, KLS09, ABL14]). They
also are connected to work on related models of robust PCA ([Bru09, CLMW11, LMTZ12, ZL14]). We refer the
reader to [DKK+ 16] to a detailed discussion on the relationships between these questions and the ones we study.

2 Definitions
Throughout this paper, if v is a vector, we will let kvk2 denote its ℓ2 norm. If M
P is a matrix, we let kM k denote
its spectral norm, we let kM kF denote its Frobenius norm, and we let kM k1 = ij |Mij | be its ℓ1 -norm if it were
R
considered a vector. For any two distributions F, G over Rd , we let dTV (F, G) = 21 Rd |F − G|dx denote the total
variation distance between the two distributions.
We will study the following contamination model:
Definition 2.1 (ε-corruption). We say a a set of samples X1 , X2 , . . . , Xn is an ε-corrupted set of samples from
a distribution D if it is generated by the process following process. First, we draw n independent samples from D.
Then, an adversary inspects these samples, and changes an ε-fraction of them arbitrarily, then returns these new points
to us, in any order. Given an ε-corrupted set of samples, we let Sgood ⊆ [n] denote the indices of the uncorrupted
samples, and we let Sbad ⊆ [n] denote the indices of the corrupted samples.
As discussed in [DKK+ 16], this is a strong notion of sample corruption that is able to simulate previously defined
notions of error. In particular, this can simulate (up to constant factors) the scenario when our samples do not come
from D, but come from a distribution D′ with total variation distance at most O(ε) from D.
We may now formally define the algorithmic problems we consider.
Robust sparse mean estimation Here, we assume we get an ε-corrupted set of samples from N (µ, I), where µ
is k-sparse. Our goal is to recover µ in ℓ2 . It is not hard to show that there is an exponential time estimator which
e log d/ε2 ), and moreover, this rate is optimal (see Appendix A). However, this algorithm requires
achieves rate O(k
highly exponential time. We show:
p
Theorem 2.1 (Efficient robust sparse mean estimation). Fix ε, δ > 0, and let k be fixed. Let η = O(ε log 1/ε).
Given an ε-corrupted set of samples X1 , . . . , Xn ∈ Rd from N (µ, I), where µ is k-sparse, and
!
2
min(k 2 , d) + log kd2 + log 1/δ
,
n=Ω
η2
there is a poly-time algorithm which outputs µ
b so that w.p. 1 − δ, we have kµ − µ
bk2 ≤ O(η).
4

It is well-known that information theoretically, the best error
pone can achieve is Θ(ε), as achieved by Fact A.1. We
show that it is possible to efficiently match this bound, up to a log 1/ε factor. Interestingly, our rate differs from that
e 2 log d/ε2 ) versus O(k log d/ε2 ). We conjecture this is necessary
in Fact A.1: our sample complexity is (roughly) O(k
for any efficient algorithm.
Robust sparse PCA We will consider both the detection and recovery problems for sparse PCA. We first focus
detection problem for sparse PCA. Here, we are given ρ > 0, and an ε-corrupted set of samples from a d-dimensional
distribution D, where D can is either N (0, I) or N (0, I + ρvv T ) for some k-sparse unit vector v. Our goal is
to distinguish between the two cases, using as few samples as possible. It is not hard to show that information
theoretically, O(k log d/ρ2 ) samples suffice for this problem, with an inefficient algorithm (see Appendix A). Our first
result is that efficient robust sparse PCA detection is possible, at effectively the best computationally efficient rate:
p
Theorem 2.2 (Robust sparse PCA detection). Fix ρ, δ, ε > 0. Let η = O(ε log 1/ε). Then, if η = O(ρ), and we
are given a we are given a ε-corrupted set of samples from either N (0, I) or N (0, I + ρvv T ) for some k-sparse unit
vector v of size
!
2
min(d, k 2 ) + log kd2 + log 1/δ
n=Ω
ρ2
then there is a polynomial time algorithm which succeeds with probability 1 − δ for detection.
It was shown in [BR13] that even without noise, at least n = Ω(k 2 log d/ε2 ) samples are required for any polynomial time algorithm for detection, under reasonable complexity theoretic assumptions. Up to log factors, we recover
this rate, even in the presence of noise.
We next consider the recovery problem. Here, we are given an ε-corrupted set of samples from N (0, I + ρvv T ),
and our goal is to output a u minimizing L(u, v), where L(u, v) = √12 kuuT − vv T k. For the recovery problem, we
recover the following efficient rate:
Theorem 2.3 (Robust sparse PCA recovery). Fix ε, ρ > 0. Let η be as in Theorem 2.2. There is an efficient algorithm,
which given a set of ε-corrupted samples of size n from N (0, I + ρvv T ), where
!
2
min(d, k 2 ) + log kd2 + log 1/δ
n=Ω
,
η2
outputs a u so that
L(u, v) = O



(1 + ρ)η
ρ



.

e
In particular, observe that when η = O(ρ), so when ε = O(ρ),
this implies that we recover v to some small
constant error. Therefore, given the same number of samples as in Theorem 2.2, this algorithm begins to provide
non-trivial recovery guarantees. Thus, this algorithm has the right “phase transition” for when it begins to work, as
this number of samples is likely necessary for any computationally efficient algorithm. Moreover, our rate itself is
likely optimal (up to log factors), when ρ = O(1). In the non-robust setting, [WBS16] showed a rate of (roughly)
O(ε/ρ) with the same number of samples, and that any computationally efficient algorithm cannot beat this rate. We
leave it as an interesting open problem to show if this rate is achievable or not in the presence of error when ρ = ω(1).

3 Preliminaries
In this section we provide technical preliminaries that we will require throughout the paper.

5

3.1 Naive pruning
We will require the following (straightforward) preprocessing subroutine from [DKK+ 16] to remove all points which
e
are more than Ω(d)
away from the true mean.

Fact 3.1 (c.f. Fact 4.18 in [DKK+ 16]). Let X1 , . . . , Xn be an ε-corrupted set of samples from N (µ, I), and let δ > 0.
There is an algorithm NAIVE P RUNE (X1 , . . . , Xn , δ) which runs in O(εd2 n2 ) time so that with probability 1 − δ,
we have that (1) N
pAIVE P RUNE removes no uncorrupted points, and (2) if Xi is not removed by NAIVE P RUNE, then
kXi − µk2 ≤ O( d log(n/δ)). If these two conditions happen, we say that NAIVE P RUNE has succeeded.

3.2 Concentration inequalities

In this section we give a couple of concentration inequalities that we will require in the remainder of the paper. These
“per-vector” and “per-matrix” concentration guarantees are well-known and follow from (scalar) Chernoff bounds, see
e.g. [DKK+ 16].
Fact 3.2 (Per-vector Gaussian concentration). Fix ε, δ > 0. Let v ∈ Rd be a unit vector, and let X1 , . . . , Xn ∼
N (0, I), where


log 1/δ
n=Ω
.
ε2
Then, with probability 1 − δ, we have

*

n

1X
Xi , v
n
i=1

+

≤ε.

Fact 3.3 (Per-matrix Gaussian concentration). Fix ε, δ > 0, and suppose ε ≤ 1. Let M ∈ Rd×d be a symmetric
matrix, and let X1 , . . . , Xn ∼ N (0, I), where


log 1/δ
.
n=Ω
ε2
Then, with probability 1 − δ, we have:

*

n

1X
Xi XiT − I, M
n i=1

+

≤ε.

3.3 The set Sn,ε
For any n, ε, define the set
Sn,ε =

(

n
X

1
, ∀i
wi = 1, and 0 ≤ wi ≤
w∈R :
(1 − ε)n
i=1
n

)

.

(1)

We make the following observation. For any subset I ⊆ [n], if we let wI be the vector whose ith coordinate is 1/|I|
if i ∈ I and 0 otherwise, we have
Sn,ε = conv {wI : |I| = (1 − ε)n} .
The set Sn,ε will play a key role in our algorithms. We will think of elements in Sn,ε as weights we place upon our
sample points, where higher weight indicates a higher confidence that the sample is uncorrupted, and a lower weight
will indicate a higher confidence that the sample is corrupted.

6

4 Concentration for sparse estimation problems via dual norms
In this section we give a clean way of proving concentration bounds for various objects which arise in sparse PCA
and sparse mean estimation problems. We do so by observing they are instances of a very general “meta-algorithm”
we call dual norm maximization. This will prove crucial to proving the correctness of our algorithms for robust
sparse recovery. While this may sound similar to the “dual certificate” techniques often used in the sparse estimation
literature, these techniques are actually quite different.
Definition 4.1 (Dual norm maximization). Let H be a Hilbert space with inner product h·, ·i. Fix any set S ⊆ H.
Then the dual norm induced by S, denoted k · k∗S , is defined by kxk∗S = supy∈S |hx, yi|. The dual norm maximizer of
x, denoted dS (x), is the vector dS (x) = arg maxv∈S |hv, xi|.
In particular, we will use the following two sets. Equip the space of symmetric d × d matrices with the trace inner
product, i.e., hA, Bi = tr(AB), so that it is a Hilbert space, and let
Uk = {u ∈ Rd : kuk2 = 1, kuk0 = k}

Xk = {X ∈ R

d×d

(2)

: tr(X) = 1, kXk1 ≤ k, X  0} .

(3)

We show in Appendix B.1 that existing well-known algorithms for sparse mean recovery and sparse PCA without
noise can be naturally written in this fashion.
Another detail we will largely ignore in this paper is the fact that efficient algorithms for these problems can only
approximately solve the dual norm maximization problem. However, we explain in Appendix B.2 why this does not
affect us in any meaningful way. Thus, for the rest of the paper we will assume we have access to the exact maximizer,
and the exact value of the norm.

4.1 Concentration for dual norm maximization
We now show how the above concentration inequalities allow us to derive very strong concentration results for the
dual norm maximization problem for Uk and Xk . Conceptually, we view these concentration results as being the major
distinction between sparse estimation and non-sparse estimation tasks. Indeed, these results are crucial for adapting
the convex programming framework for robust estimation to sparse estimation tasks. Additionally, they allow us to
give an easy proof that the L1 relaxation works for sparse PCA.
Corollary 4.1. Fix ε, δ > 0. Let X1 , . . . , Xn ∼ N (0, I), where
k + log

n=Ω
Then k n1

Pn

i=1

d
k



+ log 1/δ

ε2

!

.

Xi k∗Uk ≤ ε.

Proof. Fix a set of k coordinates, and let S be the set of unitvectors supported
on these k coordinates. By Fact 3.2

k+log 1/δ
, we have that
and a net argument, one can show that for all δ, given n = Ω
ε2
*

n

1X
v,
Xi
n i=1

+

with probability 1−δ. The result then follows by setting δ ′ =

≤ε,

d −1
δ
k

and union bounding over all sets of k coordinates.

The second concentration bound, which bounds deviation in Xk norm, uses ideas which are similar at a high level, but
requires a bit more technical work.

7

Theorem 4.2. Fix ε, δ > 0. Let X1 , . . . Xn ∼ N (0, I), where
n=Ω

min(d, k 2 ) + log
ε2

d2
k2



+ log 1/δ

!

.

Then
n

1X
Xi XiT − I
n i=1

∗
Xk

≤ε.

Let us first introduce the following definition.
Definition 4.2. A symmetric sparsity pattern is a set S of indices (i, j) ∈ [d] × [d] so that if (i, j) ∈ S then (j, i) ∈ S.
We say that a symmetric matrix M ∈ Rd×d respects a symmetric sparsity pattern S if supp(M ) = S.
With this definition, we now show:


2
min(d,k2 )+log (d
k2 )+log 1/δ
Lemma 4.3. Let n = O
. Then, with probability 1 − δ, the following holds:
ε2
b − I)X)| ≤ O(ε), for all symmetric X with kXk0 = k 2 and kXkF ≤ 1.
|tr((Σ

(4)

Proof. Fix any symmetric sparsity pattern S so that |S| ≤ k 2 . By classical arguments one can show that there is
2
a (1/3)-net over all symmetric matrices X with kXkF = 1 respecting S of size at most 9O(min(d,k )) . By Fact
3.3and a basic net argument,
we know that for any δ ′ , we know that except with probability 1 − δ ′ , if we take n =

min(d,k2 )+log 1/δ ′
b
O
samples, then for all symmetric X respecting S so that kXkF ≤ 1, we have |tr((Σ−I)X)|
≤ ε.
ε2
 2 
d
2
The claim then follows by further union bounding over all O k2 symmetric sparsity patterns S with |S| ≤ k .
We will also require the following structural lemma.

Lemma 4.4. Any PSD matrix X so that tr(X) = 1 and kXk1 ≤ k can be written as
O(n2 /k2 )

X=

X

Yi ,

i=1

where each Yi is symmetric, have

PO(n2 /k2 )
i=1

kYi kF ≤ 4, and each Yi is k 2 -sparse.

Proof. Observe that since X is PSD, then kXkF ≤ tr(X) = 1. For simplicity of exposition, let us ignore that the
Yi must be symmetric for this proof. We will briefly mention how to in addition ensure that the Yi are symmetric
at the end of the proof. Sort the entries of X in order of decreasing |Xij |. Let Yi be the matrix whose nonzeroes
are the ik 2P+ 1 through (i + 1)k 2 largest entries of X, in the same positions as they appear
P in X. Then we clearly
have that
Yi = Xi , and each Yi is exactly k 2 -sparse.1 Thus it suffices to show that
kYi kF ≤ 4. We have
1T |Yi |1
kY1 kF ≤ kXkF ≤ 1. Additionally, we have kYi+1 kF ≤
, which follows simply because every nonzero entry
k
of Yi+1 is at most the smallest entry of Yi , and each has exactly k 2 nonzeros (except potentially the last one, but it is
not hard to see this cannot affect anything). Thus, in aggregate we have
O(n2 /k2 )

X
i=1

O(n2 /k2 )

kYi kF ≤ 1 +

X
i=2

O(n2 /k2 )

kYi kF ≤ 1 +

X
i=1

1T |Yi |1
1T |X|1
= 1+
≤2,
k
k

which is stronger than claimed.
1 Technically

the last Yi may not be k 2 sparse but this is easily dealt with, and we will ignore this case here

8

However, as written it is not clear that the Yi ’s must be symmetric, and indeed they do not have to be. The only real
condition we needed was that the Yi ’s (1) had disjoint support, (2) summed to X, (3) are each Θ(k 2 ) sparse (except
potentially the last one), and (4) the largest entry of Yi+1 is bounded by the smallest entry of Yi . It should be clear that
this can be done while respecting symmetry by doubling the number of Yi , which also at most doubles the bound in
the sum of the Frobenius norms. We omit the details for simplicity.
Proof of Theorem 4.2. Let us condition on the event that (4) holds. We claim then that for all X ∈ X , we must have
b − I)X)| ≤ O(ε), as claimed. Indeed, by Lemma 4.4, for all X ∈ X , we have that
|tr((Σ
O(d2 /k2 )

X

X=

Yi ,

i=1

where each Yi is symmetric, have

PO(d2 /k2 )
i=1

kYi kF ≤ 4, and each Yi is k 2 -sparse. Thus,
O(d2 /k2 )

X

b − I)X)| ≤
|tr((Σ

i=1

O(d2 /k2 )

X

=

i=1

(a)

≤

(b)

b − I)Yi )
tr((Σ



b − I) Yi
kYi kF tr (Σ
kYi kF

O(d2 /k2 )

X
i=1

kYi kF · O(ε)

≤ O(ε) ,

where (a) follows since each Yi /kYi kF satisfies the conditions in (4), and (b) follows from the bound on the sum of
the Frobenius norms of the Yi .

4.2 Concentration for Sn,ε
We will require the following concentration inequalities for weighted sums of Gaussians, where the weights come
from Sn,ε , as these objects will naturally arise in our algorithms. These bounds
follow by applying the above bounds,

n
then carefully union bounding over all choices of possible subsets of εn
subsets. We need to be careful here since
the number of things we are union bounding over increases as n increases. We include the proofs in Appendix C.
p
Theorem 4.5. Fix ε ≤ 1/2 and δ 
≤ 1, and fix k ≤ d. There
is a η1 = O(ε log 1/ε) so that for any η > η1 , if

2
min(d,k2 )+log (d
k2 )+log 1/δ
, then
X1 , . . . , Xn ∼ N (0, I) and n = Ω
η2


n

Pr ∃w ∈ Sn,ε

1X
:
wi Xi
n i=1

∗
Uk



≥ η ≤ δ .

Theorem 4.6.
δ ≤ 1,and fix k ≤ d. There is a η = O(ε
 Fix ε 2≤ 1/2 dand
2
min(d,k )+log (k2 )+log 1/δ
, then we have
and n = Ω
η2


Pr ∃w ∈ Sn,ε

n
1X
:
wi Xi XiT − I
n i=1

9

∗
Xk

p

log 1/ε) so that if X1 , . . . , Xn ∼ N (0, I)


≥ η ≤ δ .

5 A robust algorithm for robust sparse mean estimation
This section is dedicated to the description of an algorithm R ECOVER ROBUST SM EAN for robustly learning Gaussian
sequence models, and the proof of the following theorem:
p
Theorem 5.1. Fix ε, τ > 0. Let η = O(ε log 1/ε). Given an ε-corrupted set of samples of size n from N (µ, I),
where µ is k-sparse
!
2
min(k 2 , d) + log kd2 + log 1/τ
,
n=Ω
η2
then R ECOVER ROBUST SM EAN outputs a µ
b so that with probability 1 − τ, we have kb
µ − µk2 ≤ O(η).

Our algorithm builds upon the convex programming framework developed in [DKK+ 16]. Roughly speaking, the
algorithm proceeds
as follows. First, it does a simple naive pruning step to remove all points which are more than
√
roughly Ω( d) away from the mean. Then, for an appropriate choice of δ, it will attempt to (approximately) find a
point within the following convex set:


∗
n


X
≤τ .
(5)
wi (Xi − µ)(Xi − µ)T − I
RobustSM eanCτ = w ∈ Sn,ε :


i=1

Xk

The main difficulty with finding a point in Cτ is that µ is unknown. A key insight of [DKK+ 16] is that it suffices
to create an (approximate) separation oracle for the feasible set, as then we may use classical convex optimization
algorithms (i.e. ellipsoid or cutting plane methods) to find a feasible point. In their setting (for a different Cτ ), it turns
out that a simple spectral algorithm suffices to give such a separation oracle.
Our main contribution is the design of separation oracle for Cτ , which requires more sophisticated techniques. In
particular, we will ideas developed in analogy to hard thresholding and SDPs similar to those developed for sparse
PCA to design such an oracle.

5.1 Additional preliminaries
Throughout this section, we let X1 , . . . , Xn denote an ε-corrupted set of samples from N (µ, I), where µ is k-sparse.
We let Sgood denote the set of uncorrupted
samples, and we
P
Plet Sbad denote the set of corrupted samples. For any set
of weights w ∈ Sn,ε , we let wg = i∈Sgood wi and wb = i∈Sbad wi .
Throughout this section, we will condition on the following three deterministic events occurring:
NAIVE P RUNE (X1 , . . . , Xn , δ) succeeds,
X

i∈Sgood

X

i∈Sgood

where η = O(ε

p

wi (Xi − µ)

log 1/ε). When n = Ω

≤ η , ∀w ∈ Sn,2ε , and

(7)

≤ η , ∀w ∈ Sn,2ε ,

(8)

Uk
∗

wi (Xi − µ)(Xi − µ)T − wg I


(6)

∗

Xk
2

min(k2 ,d)+log (k
d2 )+log 1/δ
η2



these events simultaneously happen with

probability at least 1 − O(δ) by Fact 3.1, Theorem 4.5, Theorem 4.6 and a union bound, and the observation that if
w ∈ Sn,ε , then w/wg restricted to the indices in Sgood is in S(1−ε)n,2ε .

10

5.2 The separation oracle
Our main result in this section is the description of a polynomial time algorithm ROBUST SM EAN O RACLE and the
proof of the following theorem of its correctness:
Theorem 5.2. Fix ε > 0 sufficiently small. Suppose that (7) and (8) hold. Let w∗ denote the set of weights which are
uniform over the uncorrupted points. Then, there is a constant 1 ≤ c ≤ 21 so that ROBUST SM EAN O RACLE satisfies:
1. (Completeness) If w = w∗ , ROBUST SM EAN O RACLE outputs “YES”.
2. (Soundness) If w 6∈ Ccη the algorithm outputs a hyperplane ℓ : Rn → R so that ℓ(w) ≥ 0 but ℓ(w∗ ) < 0.
Moreover, if the algorithm ever outputs a hyperplane, we have ℓ(w∗ ) < 0.
Plugging these guarantees into an ellipsoid (or cutting-plane) method, we obtain the following:
Corollary 5.3. Fix ε > 0 sufficiently small. Suppose that (7) and (8) hold. There is an algorithm A PPROX R ECOVER ROBUST SM EAN which queries ROBUST SM EAN O RACLE at most
p poly(d, 1/ε, log 1/δ) times, and so runs in time
poly(d, 1/ε, 1/δ) which outputs a w′ so that kw − w′ k∞ ≤ ε/(n d log n/δ), for some w ∈ Ccτ .

Our separation oracle, formally described in Algorithm 1, proceeds as follows. Given w ∈ Sn,ε , it forms µ
b =
P
P
′
T
b
· dUk (b
µ ), where µ
b =
wi Xi . It then forms the matrix Σ =
wi (Xi − µ
b)(Xi − µ
b) , and computes
b
b
A = dXk (Σ). The algorithm then checks if hA, Σi > C for appropriately chosen threshold C. If it does not, the
algorithm outputs “YES”. Otherwise, the algorithm outputs a separating hyperplane given by this matrix A.
kb
µ′ k∗Uk

Algorithm 1 Separation oracle for robust sparse mean estimation.
1: function ROBUST SM EAN O RACLE (X1 , . . . , Xn , w)
P
2:
Let µ
b = wi Xi
b = P wi (Xi − µ
3:
Let Σ
b)(Xi − µ
b)T
b
4:
Let A = dXk (Σ)
b
5:
if |hA, Σ − Ii| ≥
 20η then 
b − Ii
6:
Let σ = sgn hA, Σ
7:
return the hyperplane ℓ given by
ℓ(w) = σ

n
X
i=1

8:
9:
10:
11:

else
return “YES”
end
end function

T

b)(Xi − µ
b)
wi A, (Xi − µ

−1

!

b − Ii| .
− |hA, Σ

We will require the following two lemmata:
Lemma 5.4. Let ω1 , . . . , ωm be a set of non-negative weights that sum to 1. Let a1 , . . . , am be any sequence of
scalars. Then
!2
m
m
X
X
2
.
ω i ai
ω i ai ≥
i=1

i=1

Proof. Let Z be a random variable which is ai with probability ωi . Then E[Z] =
the inequality follows from the fact that E[Z 2 ] − E[Z 2 ] = Var[Z] ≥ 0.
Lemma 5.5. Let u ∈ Rd . Then (kuk∗Uk )2 ≤ kuuT k∗Xk ≤ 4(kuk∗Uk )2 .
11

P

ωi ai and E[Z 2 ] =

P

ωi a2i . Then

Proof. Let v = dUk (u). Then since vv T ∈ Xk , we have that (kuuT k∗Xk ) ≥ hvv T , uuT i = hu, vi2 = (kuk∗Uk )2 . This
proves the first inequality.
To prove the other inequality, we first prove the intermediate claim that supM∈Yk2 uT M u ≤ (kuk∗Uk )2 , where Yk2
is the set of symmetric matrices M with at most k 2 -non-zeroes satisfying kM kF = 1. Indeed, fix any M ∈ Yk . Let
S ⊆ [n] be the set of non-zeroes of dUk (u). This is exactly the set of the k largest elements in u, sorted by absolute
value. Let P be the symmetric sparsity pattern respected by M . Fix an arbitrary bijection φ : P \(S×S) → (S×S)\P ,
and let M ′ be the following matrix:

T
if (i, j) ∈ P (S × S) ,
 Mij
′
sgn (ui uj ) Mφ−1 (i,j) if (i, j) ∈ (S × S) \ P ,
Mi,j
=

0
otherwise.
Then we claim that uT M u ≤ uT M ′ u. Indeed, we have
X
|Mij (uuT )φ(i,j) | − Mij (uuT )i,j
uT M ′ u − uT M u =
(i,j)∈P \(S×S)

≥

X

(i,j)∈P \(S×S)


|Mi,j | |(uuT )φ(i,j) | − |(uuT )i,j | ≥ 0 ,

from the definition of S. Moreover, for any M respecting S × S with kM kF = 1, it is not hard to see that uT M u ≤
(kuk∗Uk )2 . This is because now the problem is equivalent to restricting our attention to the coordinates in S, and
asking for the symmetric matrix M ∈ RS×S with kM kF = 1 maximizing uTS M uS , where uS is u restricted to
the coordinates in S. This is clearly maximized by M = kuS1 k2 uS uTS , which yields the desired expression, since
2
kuS k2 = kukUk .
PO(n2 /k2 )
We can now prove the original lemma. By Lemma 4.4 we may write A =
Yi where each Yi is
i=1
PO(n2 /k2 )
2
symmetric, k -sparse, and have i=1
kYi kF ≤ 4. We therefore have
O(n2 /k2 )

T

u Au =

X

uT Yi u

X

kYi kF (kuk∗Uk )2

i=1

O(n2 /k2 )

=

i=1

≤ 4(kuk∗Uk )2 ,
as claimed, where the second line follows from the arguments above.
Throughout the rest of this section, let Yi = Xi − µ, so that so that Yi ∼ N (0, I) if i ∈ Sgood . We first prove the
following crucial proposition:
Pn
∗
Proposition 5.6. Let w ∈ Sn,ε , and let τ ≥ η. Assuming (7) and (8) hold, if k i=1 wi Yi kUk ≥ 3τ , then
Pn
2
∗
τ
T
i=1 wi Yi Yi − I Xk ≥ ε .
P
∗
Proof. Observe that (7) and a triangle inequality together imply that
i∈Sbad wi Yi Uk ≥ 2τ . By definition, this
P
P
implies there is a k-sparse unit vector u so that hu, i∈Sbad wi Yi i ≥ 2τ . WLOG assume that hu, i∈Sbad wi Yi i ≥ η
(if the sign is negative a symmetric argument suffices). This is equivalent to the statement that
X wi
2τ
hu, Yi i ≥ b .
wb
w
i∈Sbad

b

Observe that the wi /w are a set of non-negative weights summing to 1. Hence, by Lemma 5.4, we have
 2
X wi
2τ
2
hu, Yi i ≥
.
wb
wb
i∈Sbad

12

Let A = uuT . Observe that A ∈ Xk . Then the above inequality is equivalent to the statement that
X

i∈Sbad

wi YiT AYi ≥

τ2
4τ 2
≥
.
wb
ε

Moreover, by (8), we have
X

i∈Sgood

wi YiT AYi − I ≤ η ,

and together these two inequalities imply that
n
X
i=1

wi Yi AYi ≥

4τ 2
τ2
−η ≥
,
ε
ε

as claimed. The final inequality follows from the definition of η, and since 4 > 2.
Proof of Theorem 5.2. Completeness follows from (8). We will now show soundness. Suppose w 6∈ C21η . We wish to
show that we will output a separating
Pn hyperplane. From the description of the algorithm, this is equivalent to showing
b − IkX ≥ 20η. Let µ
that kΣ
b = i=1 wi Xi , and let ∆ = µ − µ
b. By elementary manipulations, we may write
k
n
X
i=1

wi (Xi − µ
b)(Xi − µ
b)T − I

=

n
X
i=1

Xk
(a)

=

wi (Yi + ∆)(Yi + ∆)T − I

n
X
i=1

(b)

≥

(c)

≥

n
X
i=1

n
X
i=1

wi Yi YiT + ∆∆T − I
wi Yi YiT − I
wi Yi YiT − I

Xk

Xk

Xk

− ∆∆T

Xk

2

Xk

− 4 k∆kUk ,

Pn
where (a) follows since p
i=1 wi Yi = ∆ by definition, (b) follows from a triangle inequality, and (c) follows from
Lemma 5.5. If k∆kUk ≤ η/2, then the RHS is at least 21η since the second
p term is at most η, and the first term
isP
at least 21η since we assume that w 6∈ C21η . Conversely, if k∆kUk ≥ η/2, then by Proposition 5.6, we have
n
k i=1 wi Yi Yi − IkXk ≥ k∆k2Xk /(6ε) > 48k∆k2Xk as long as ε ≤ 1/288. This implies that the RHS is at least
40k∆kXk2 ≥ 20η, as claimed.
Hence, this implies that if w 6∈ C4η , then we output a hyperplane ℓ. It is clear by construction
that ℓ(w) ≥ 0;
P
1
thus, it suffices to show that if we output a hyperplane, that ℓ(w∗ ) < 0. Letting µ
e = (1−ε)n
i∈Sgood wi Yi , we have
Observe that we have
n
X
i=1

X
1
(Yi + ∆)(Yi + ∆)T − I
(1 − ε)n
i∈Sgood


X
1

=
Yi YiT − I  + ∆e
µT + µ
e∆T + ∆∆T
(1 − ε)n
i∈Sgood


X
1

Yi YiT − I  + (∆ + µ
e)(∆ + µ
e)T − µ
eµ
eT .
=
(1 − ε)n

wi∗ (Xi − µ
b)(Xi − µ
b)T − I =

i∈Sgood

13

Hence by the triangle inequality and Lemma 5.5, we have
n
X
i=1

wi∗ (Xi

T

−µ
b)(Xi − µ
b) − I

Xk

i∈Sgood

+ 4 k∆ +
≤

∗
ke
µk U k

by (7) and (8).
Observe that to show that ℓ(w∗ ) < 0 it suffices to show that

i=1

+4

Xk

2
ke
µk∗Uk

i∈Sgood

≤ 13η + 8

wi∗ (Xi

2
µ
ek∗Uk

X
1
Yi YiT − I
1(1 − ε)n
+8

n
X

∗

X
1
≤
Yi YiT − I
1(1 − ε)n

2

+4

∗ 2
k∆kUk

∗

−µ
b)(Xi − µ
b) − I

Xk

+ 8 k∆k∗Uk

Xk

∗ 2
ke
µkUk

,

b −I
< Σ

∗
Xk

2
(9)

.

(10)

p
η/2, then this follows since the quantity on the RHS is at least 20η by assumption, and the quantity on
p
2
the LHS is at most 17η by (9). If k∆k∗Uk ≥ η/2, then by Proposition 5.6, the RHS of (10) is at least k∆k∗Uk /(3ε),
which dominates the LHS as long as k∆k∗Uk ≥ η and ε ≤ 1/288, which completes the proof.
If k∆k∗Uk ≤

5.3 Putting it all together
We now have the ingredients to prove our main theorem. Given what we have, our full algorithm R ECOVER RO BUST SM EAN is straightforward: first run NAIVE P RUNE , then run A PPROX R ECOVER ROBUST SM EAN on the pruned
points to output some set of weights w. We then output kb
µkUk dUk (b
µ). The algorithm is formally defined in Algorithm
2.
Algorithm 2 An efficient algorithm for robust sparse mean estimation
1: function R ECOVER ROBUST SM EAN (X1 , . . . , Xn , ε, δ)
2:
Let S be the set output by NAIVE P RUNE (X1 , . . . , Xn , δ). WLOG assume S = [n].
3:
Let w′ =P
A PPROX R ECOVER ROBUST SM EAN (X1 , . . . , Xn , ε, δ).
n
4:
Let µ
b = i=1 wi′ Xi .
5:
return kb
µk∗Uk dUk (b
µ)
6: end function
Proof of Theorem 5.1. Letus condition on the eventthat (6), (7), and (8) all hold simultaneously. As previously
2
min(k2 ,d)+log (k
d2 )+log 1/δ
mentioned, when n = Ω
these events simultaneously happen with probability at least
η2

1 − O(δ). For simplicity of exposition, let us assume that NAIVE P RUNE does not remove any points. This is okay
since if it succeeds, it never removes any good
p points, so if it removes any points, it can only help us. Moreover, since
it succeeds, we know that kXi − µk2 ≤pO( d log(n/δ)) for all i ∈ [n]. By Corollary 5.3, we know that there is some
w ∈ C21η so that kw − w′ k∞ ≤ ε/(n d log n/δ). We have
kb
µ − µkUk =

n
X
i=1

wi′ Xi − µ
b

∗

Uk

≤

n
X
i=1

∗

wi Xi − µ
b

≤ O(η) + O(ε) ,
14

+
Uk

n
X
i=1

|wi − wi′ | kXi − µk2

by Proposition 5.6. We now show that this implies that if we let µ′ = kb
µk∗Uk dUk (b
µ), then kµ′ − µk2 ≤ O(η). Let S
′
be the support of µ , and let T be the support of µ. Then we have
X
X
X
µ2i .
(µ′i )2 +
kµ′ − µk22 =
(µ′i − µi )2 +
i∈S∩T

i∈T \S

i∈S\T

2
P
P
µ − µk∗Uk , since µ was originally nonzero on the entries in
Observe that i∈S∩T (µ′i − µi )2 + i∈S\T (µ′i )2 ≤ kb
S \ T . Moreover, for all i ∈ T \ S and j ∈ S \ T , we have (µ′i )2 ≤ (µ′j )2 . Thus we have
X

i∈T \S



µ2i ≤ 2 

X

i∈T \S

(µ − µ′i )2 +

Therefore we have kµ′ − µk22 ≤ 3 kb
µ − µk∗Uk

2

X

i∈S\T



(µ′j )2  ≤ 2 kb
µ − µk∗Uk

2

.

, which implies that kµ′ − µk2 ≤ O(η), as claimed.

6 An algorithm for robust sparse PCA detection
In this section, we give an efficient algorithm for detecting a spiked covariance matrix in the presence of adversarial
noise. Our algorithm is fairly straightforward: we ask for the set of weights w ∈ Sn,ε so that the empirical second
moment with these weights has minimal deviation from the identity in the dual Xk norm. We may write this as a
convex program. Then, we check the value of the optimal solution of this convex program. If this value is small, then
we say it is N (0, I). if this value is large, then we say it is N (0, I + ρvv T ). We refer to the former as Case 1 and the
latter as Case 2. The formal description of this algorithm is given in Algorithm.
Algorithm 3 Learning a spiked covariance model, robustly
1: function D ETECT ROBUST SPCA(X1 , . . . , Xn , ε, δ, ρ)
2:
Let γ be the value of the solution
min

w∈Sn,ε

3:
4:

n
X

wi (Xi XiT

i=1

∗

− I)

(11)
Xk

if γ < ρ/2 then return Case 1 else return Case 2
end function

6.1 Implementing D ETECT ROBUST SPCA
We first show that the algorithm presented above can be efficiently implemented. Indeed, one can show that by taking
the dual of the SDP defining the k · k∗Xk norm, this problem can be re-written as an SDP with (up to constant factor
blowups) the same number of constraints and variables, and therefore we may solve it using traditional SDP solver
techniques.
Alternatively, one may observe that to optimize Algorithm 4 via ellipsoid or cutting plane methods, it suffices to,
given w ∈ Sn,ε , produce a separating hyperplane for the constraint (11). This is precisely what dual norm maximization allows us to do efficiently. It is straightforward to show that the volume of Sn,ε × Xk is at most exponential in the
relevant parameters. Therefore, by the classical theory of convex optimization, (see e.g. [CITE]), for any ξ, we may
find a solution w′ and γ ′ so that kw′ − w∗ k∞ ≤ ξ and γ ′ so that |γ − γ ′ | < ξ for some exact minimizer w∗ , where γ
is the true value of the solution, in time poly(d, n, 1/ε, log 1/ξ),
As mentioned in Section B.2, neither approach will in general give exact solutions, however, both can achieve
inverse polynomial accuracy in the parameters in polynomial time. We will ignore these issues of numerical precision
throughout the remainder of this section, and assume we work with exact γ.

15

Observe that in general it may be problematic that we don’t have exact access to the minimizer w∗ , since some of
the Xi may be unboundedly large (in particular, if it’s corrupted) in norm. However, we only use information about γ.
Since γ lives within a bounded range, and our analysis is robust to small changes to γ, these numerical issues do not
change anything in the analysis.

6.2 Proof of Theorem 2.2
We now show that Algorithm 4 provides the guarantees required for Theorem 2.2. We first show that if we are in Case
1, then γ is small:
Lemma 6.1. Let ρ, δ > 0. Let ε, η be as in Theorem 2.2. Let X1 , . . . , Xn be an ε-corrupted set of samples from
N (0, I) of size n, where n is as in Theorem 2.2. Then, with probability 1 − δ, we have γ ≤ ρ/2.
P Pn
Proof. Let w be the uniform weights over the uncorrupted points. Then it from Theorem 4.2 that k w i=1 wi (Xi XiT −
I)k∗Xk ≤ O(η) with probability 1 − δ. Since w ∈ Sn,ε , this immediately implies that γ ≤ O(ρ). By setting constants
appropriately, we obtain the desired guarantee.
We now show that if we are in Case 2, then γ must be large:
Lemma 6.2. Let ρ, δ > 0. Let ε, η, n be as in Theorem 2.2. Let X1 , . . . , Xn be an ε-corrupted set of samples from
N (0, I) of size n. Then, with probability 1 − δ, we have γ ≥ (1 − ε)ρ − (2 + ρ)η. In particular, for ε sufficiently
small, and η = O(ρ), we have that γ > ρ/2.
Proof. Let Σ = I + ρvv T , and let Yi = Σ−1/2 Xi , so that if Yi is uncorrupted, then Yi ∼ N (0,
w∗ be
PnI). Let
∗
the optimal solution to (11). By Theorem 4.6, we
wi Yi YiT =
Pn write∗ i=1
Phave that∗ withTprobability 1 − δ, we can
T
g
∗
w (I + N ) + B, where kN kXk ≤ η, and B = i∈Sbad wi Yi Yi . Therefore, we have i=1 w Xi Xi = wg (Σ +
Σ1/2 N Σ1/2 ) + Σ1/2 BΣ1/2 . By definition, we have
n
X
i=1

wi (Xi XiT

∗

− I)

Xk

≥ hwg (Σ + Σ1/2 N Σ1/2 ) + Σ1/2 BΣ1/2 − I, vv T i
≥ wg h(Σ + Σ1/2 N Σ1/2 ), vv T i − 1

= wg (1 + ρ) + wg v T Σ1/2 N Σ1/2 v − 1

≥ (1 − ε)ρ + (1 − ε)v T Σ1/2 N Σ1/2 v − ε .

T 1/2
1/2
It thus suffices to show
√ that |v Σ N Σ v| < (1 + ρ)η. Since v is an eigenvector for Σ with eigenvalue 1 + ρ, we
1/2
have that Σ v = ρ + 1 · v and thus

v T Σ1/2 N Σ1/2 v = (1 + ρ)v T N v = (1 + ρ)hN, vv T i ≤ (1 + ρ)kN k∗Xk ≤ (1 + ρ)η .

Lemmas 6.1 and 6.2 together imply the correctness of D ETECT ROBUST SPCA and Theorem 2.2.

7 An algorithm for robust sparse PCA recovery
In this section, we prove Theorem 2.3. We give some intuition here. Perhaps the first naive try would be to simply
run the same SDP in (11), and hope that the dual norm maximizer gives you enough information to recover the
hidden spike. This would more or less correspond to the simplest modification SDP of the sparse PCA in the nonrobust setting that one could hope gives non-trivial information in this setting. However, this cannot work, for the
following straightforward reason: the value of the SDP is always at least O(ρ), as we argued in Section 6. Therefore,
the noise can pretend to be some other sparse vector u orthogonal to v, so that the covariance with noise looks like
wg (I + ρvv T ) + wg ρuuT , so that the value of the SDP can be minimized with the uniform set of weights. Then it is
16

easily verified that both vv T and uuT are dual norm maximizers, and so the dual norm maximizer does not uniquely
determine v.
To circumvent this, we simply add an additional slack variable to the SDP, which is an additional matrix in Xk ,
which we use to try to maximally explain away the rank-one part of I + ρvv T . This forces the value of the SDP to be
very small, which allows us to show that the slack variable actually captures v.

7.1 The algorithm
Our algorithms and analyses will make crucial use of the following convex set, which is a further relaxation of Xk :
n
o
(2)
Wk = X ∈ Rd×d : tr(X) ≤ 2, kXk2 ≤ 1, kXk1 ≤ 3k, X  0 .

Our algorithm, given formally in Algorithm 4, will be the following. We solve a convex program which simultaneously chooses a weights in Sn,ε and a matrix A ∈ Wk to minimize the Wk distance between the sample covariance
with these weights, and A. Our output is then just the top eigenvector of A.
Algorithm 4 Learning a spiked covariance model, robustly
1: function R ECOVER ROBUST SPCA(X1 , . . . , Xn , ε, δ, ρ)
2:
Let w∗ , A∗ be the solution to
arg min
w∈Sn,ε ,A∈Xk

3:
4:
5:

n
X

wi (Xi XiT

i=1

∗

− I) − ρA

(12)
W2k

Let u be the top eigenector of A∗
return The dUk (u)kuk∗Uk , i.e., the vector with all but the top k coordinates of v zeroed out.
end function

This algorithm can be run efficiently for the same reasons as explained for D ETECT ROBUST SPCA. For the rest of the
section we will assume that we have an exact solution for this problem. As before, we only use information about A,
and since A comes from a bounded space, and our analysis is robust to small perturbations in A, this does not change
anything.

7.2 More concentration bounds
Before we can prove correctness of our algorithm, we require a couple of concentration inequalities for the set Wk .
Lemma 7.1. Fix ε, δ > 0. Let X1 , . . . , Xn ∼ N (0, I), where n is as in Theorem 4.2. Then with probability 1 − δ
n

1X
Xi XiT − I
n i=1

∗
Wk

≤ O(ε) .

b denote the empirical covariance. Observe that Wk ⊆ S∞ 2−i X2i+1 k . Moreover, for any i, by Theorem
Proof. Let Σ
i=0
4.2, if we take



d2
min(d, (2i+1 k)2 ) + log (2i+1
+
log
1/δ
2
k)

n = Ω
(2−i ε)2
!
2
min(d, k 2 ) + log kd2 + 22i log 1/δ
=Ω
,
ε2

17

b ≤ ε for all M ∈ 2−i X2i+1 k with probability 1 − δ/2. In particular, if we take
then |hM, Σi|
!
2
min(d, k 2 ) + log kd2 + log 1/δ
n=Ω
ε2
2i

b ≤ ε for all M ∈ 2−1 X2i+1 k with probability at least 1 − δ 2 /2. By a union
samples, then for any i, we have |hM, Σi|
P∞ 22i
b ≤ ε for
bound over all these events, since i=0 δ ≤ 2δ, we conclude that if we take n to be as above, then |hM, Σi|
S∞ −i
∗
b
all M ∈ i=0 2 X2i+1 k with probability 1−δ. Since Wk is contained in this set, this implies that kΣ−ΣkWk ≤ O(ε)
with probability at least 1 − δ, as claimed.

By the same techniques as in the proofs of Theorems 4.5 and 4.6, we can show the following bound. Because of
this, we omit the proof for conciseness.
Corollary
7.2. Fix ε, δ > 0. Let X1 , . . . , Xn ∼ N (0, I) where n is as in Theorem 4.6. Then there is an η =
p
O(ε log 1/ε) so that


∗
n
X
≥ η ≤ δ .
wi Xi XiT − I
Pr ∃w ∈ Sn,ε :
i=1

Wk

7.3 Proof of Theorem 2.3
In the rest of this section we will condition on the following deterministic event happening:
∀w ∈ Sn,ε :

n
X

wi Xi XiT

i=1

∗

−I

W2k

≤η,

(13)

where η = O(ε log 1/ε). By Corollary 7.2, this holds if we take
n=Ω

min(d, k 2 ) + log
η22

d2
k2



+ log 1/δ

!

samples.
The rest of this section is dedicated to the proof of the following theorem, which immediately implies Theorem
2.3.
Theorem 7.3. Fix ε, δ, and let η be as in (13). Assume that (13) holds.
p
Let vb be the output of R ECOVERY ROBUST SPCA(X1 , . . . , Xn , ε, δ, ρ). Then L(b
v , v) ≤ O( (1 + ρ)η/ρ).

Our proof proceeds in a couple of steps. Let Σ = I + ρvv T denote the true covariance. We first need the following,
technical lemma:
Lemma 7.4. Let M ∈ Wk . Then Σ1/2 M Σ1/2 ∈ (1 + ρ)Wk .

√
Proof. Clearly, Σ1/2 M Σ1/2  0. Moreover,√since Σ1/2 = I + ( 1 + ρ − 1)vv T , we have that the maximum value
1/2
of any element of Σ
is upper bounded by 1 + ρ. Thus, we have kΣ1/2 M Σ1/2 k1 ≤ (1 + ρ)kM k1 . We also have
tr(Σ1/2 M Σ1/2 ) = tr(ΣM )
= tr(M ) + ρv T M v ≤ 1 + ρ ,
since kM k ≤ 1. Thus Σ1/2 M Σ1/2 ∈ (1 + ρ)Wk , as claimed.
Let w∗ , A∗ be the output of our algorithm. We first claim that the value of the optimal solution is quite small:
18

Lemma 7.5.
n
X

wi∗ (Xi XiT

i=1

∗

− I) − ρA

∗
W2k

≤ η(1 + ρ) .

Proof. Indeed, if we let w be the uniform set of weights over the good points, and we let A = vv T , then by (13), we
have
n
X

wi Xi XiT = Σ1/2 (I + N )Σ1/2 ,

i=1

where kN k∗Xk ≤ η, and Σ = I + ρvv T . Thus we have that
n
X

wi (Xi XiT

i=1

− I) − ρvv

T

∗
W2k

= kΣ1/2 N Σ1/2 k∗W2k
= max tr(Σ1/2 N Σ1/2 M )
M∈Wk

= max tr(N Σ1/2 M Σ1/2 )
M∈Wk

≤ (1 + ρ)kN k∗W2k ,
by Lemma 7.4.
We now show that this implies the following:
Lemma 7.6. v T A∗ v ≥ 1 − (2 + 3ρ)η/ρ.

P
Proof.PBy (13), we know that we may write ni=1 wi (Xi XiT − I) = wg ρvv T + B − (1 − wg )I + N , where
B = i∈Sbad wi Xi XiT , and kN k∗Wk ≤ (1 + ρ)η. Thus, by Lemma 7.5 and the triangle inequality, we have that
wg ρvv T + B − ρA

∗
Wk

≤ η + kN k∗Wk + (1 − wg )kIk∗Wk + (1 − wg )kρAk∗Wk
≤ (1 + ρ)η + ε + ρε
≤ (1 + 2ρ)η + ε .

Now, since vv T ∈ Wk , the above implies that
|wg ρ + v T Bv − ρv T A∗ v| ≤ (1 + 2ρ)η + ε ,
which by a further triangle inequality implies that
|ρ(1 − v T A∗ v) + v T Bv| ≤ (1 + 2ρ)η + ε + ερ ≤ (2 + 3ρ)η .
Since 0 ≤ v T A∗ v ≤ 1 (since A ∈ Xk ) and B is PSD, this implies that in fact, we have
0 ≤ ρ(1 − v T A∗ v) ≤ (2 + 3ρ)η .
Hence v T A∗ v ≥ 1 − (2 + 3ρ)η/ρ, as claimed.
Let γ = (2 + 3ρ)η/ρ. The lemma implies that the top eigenvalue of A∗ is at least 1 − γ. Moreover, since
A ∈ Xk , as long as γ ≤ 1/2, this implies that the top eigenvector of A∗ is unique up to sign. By the constraint that
η ≤ O(min(ρ, 1)), for an appropriate choice of constants, we that γ ≤ 1/10, and so this condition is satisfied. Recall
that u is the top eigenvector of A∗ . Since tr(A∗ ) = 1 and A∗ is PSD, we may write A∗ = λ1 uuT + A1 , where u is
the top eigenvector of A∗ , λ1 ≥ 1 − γ, and kA1 k ≤ γ. Thus, by the triangle inequality, this implies that
∗

kρ(vv T − λ1 uuT ) + Bk∗X2k ≤ O(ργ)
19

which by a further triangle inequality implies that
kρ(vv T − uuT ) + Bk∗X2k ≤ O(ργ) .

(14)

We now show this implies the following intermediate result:
Lemma 7.7. (v T u)2 ≥ 1 − O(γ).

Proof. By Lemma 7.6, we have that v T A∗ v = λ1 (v T u)2 + v T A1 v ≥ 1 − γ. In particular, this implies that (v T u)2 ≥
(1 − 2γ)/λ1 ≥ 1 − 3γ, since 1 − γ ≤ λ ≤ 1.
We now wish to control the spectrum of B. For any subsets S, T ⊆ [d], and for any vector x and any matrix M ,
let xS denote x restricted to S and MS,T denote the matrix restricted to the rows in S and the columns in T . Let I be
the support of u, and let J be the support of the largest k elements of v.
Lemma 7.8. kBI,I k ≤ O(ργ).
Proof. Observe that the condition (14) immediately implies that
kρ(vI vIT − uI uTI ) + BI,I k ≤ cργ ,

(15)

for some c, since any unit vector x supported on I satisfies xxT ∈ X2k . Suppose that kBI,I k ≥ Cγ for some
sufficiently large C. Then (15) immediately implies that kρ(vI vIT − uI uTI )k ≥ (C − c)ργ. Since (vI vIT − uI uTI ) is
clearly rank 2, and satisfies tr(vI vIT −uI uTI ) = 1−kuI k22 ≥ 0, this implies that the largest eigenvalue of vI vIT −uI uTI
is positive. Let x be the top eigenvector of vI vIT − uI uTI . Then, we have xT (vI vIT − uI uTI )x + xT Bx = (C − c)ργ +
xT Bx ≥ (C − c)ργ by the PSD-ness of B. If C > c, this contradicts (15), which proves the theorem.
This implies the following corollary:
Corollary 7.9. kuI k22 ≥ 1 − O(γ).

Proof. Lemma 7.8 and (15) together imply that kvI vIT − uI uTI k ≤ O(γ). The desired bound then follows from a
reverse triangle inequality.
We now show this implies a bound on BJ\I,J\I :

Lemma 7.10. kBJ\I,J\I k ≤ O(ργ).
Proof. Suppose kBJ\I,J\I k ≥ Cγ for some sufficiently large C. Since u is zero on J \ I, (14) implies that
T
+ BJ\I,J\I k ≤ cργ ,
kρvJ\I vJ\I
T
for some universal c. By a triangle inequality, this implies that kvJ\I k22 = kvJ\I vJ\I
k ≥ (C − c)γ. Since v is a unit
2
vector, this implies that kvI k2 ≤ 1 − (C − c)γ, which for a sufficiently large C, contradicts Corollary 7.9.

We now invoke the following general fact about PSD matrices:
Lemma 7.11. Suppose M is a PSD matrix, written in block form as


C D
M=
.
DT E
Suppose furthermore that kCk ≤ ξ and kEk ≤ ξ. Then kM k ≤ O(ξ).
Proof. It is easy to see that kM k ≤ O(max(kCk, kDk, kEk)). Thus it suffices to bound the largest singular value of
D. For any vectors φ, ψ with appropriate dimension, we have that


φ
T
T
(φ − ψ ) M
= φT Aφ − 2φT Dψ + ψ T Cψ ≥ 0 ,
−ψ
which immediately implies that the largest singular value of D is at most (kAk+kBk)/2, which implies the claim.
20

Therefore, Lemmas 7.8 and 7.10 together imply:
T
Corollary 7.12. kvI∪J vI∪J
− uI∪J uTI∪J k ≤ O(γ) .
T
Proof. Observe (14) immediately implies that kρ(vI∪J vI∪J
− uI∪J uTI∪J ) + BI∪J,I∪J k ≤ O(ργ), since |I ∪ J| ≤ 2k.
Moreover, Lemmas 7.8 and 7.10 with Lemma 7.11 imply that kBI∪J,I∪J k ≤ O(ργ), which immediately implies the
statement by a triangle inequality.

Finally, we show this implies kvv T − uJ uTJ k ≤ O(γ), which is equivalent to the theorem.
Proof of Theorem 7.3. We will in fact show the slightly stronger statement, that kuuT − vJ vJT kF ≤ O(γ). Observe
T
that since uuT − vv T is rank 2, Corollary 7.12 implies that kvI∪J vI∪J
− uI∪J uTI∪J kF ≤ O(γ), since for rank two
matrices, the spectral and Frobenius norm are off by a constant factor. We have
X
X
X
(ui uj )2 .
(vi vj )2 +
(ui uj − vi vj )2 +
kuuT − vv T k2F =
(i,j)∈J×J\I×I

(i,j)∈I×I\J×J

(i,j)∈I∩J×I∩J

We have
X

(i,j)∈I∩J×I∩J

(ui uj − vi vj )2 +

X

(i,j)∈J×J\I×I

T
− uI∪J uTI∪J k2 ≤ O(γ) ,
(ui uj )2 ≤ kvI∪J vI∪J

by Corollary 7.12. Moreover, we have that
X

(i,j)∈I×I\J×J



(vi vj )2 ≤ 2 

X

(i,j)∈I×I\J×J



(vi vj − ui uj )2 +

T
≤ 2 kvI∪J vI∪J
− uI∪J uTI∪J k2 +



T
≤ 2 kvI∪J vI∪J
− uI∪J uTI∪J k2 +

X

(i,j)∈I×I\J×J

X

(i,j)∈I×I\J×J

X

(i,j)∈J×J\I×I

≤ O(γ) .



(ui uj )2 


(ui uj )2 



(ui uj )2 

since J × J contains the k 2 largest entries of uuT . This completes the proof.

Acknowledgements
The author would like to thank Ankur Moitra for helpful advice throughout the project, and Michael Cohen for some
surprisingly2 useful conversations.

2 Is

it really surprising though?

21

References
[ABL14]

P. Awasthi, M. F. Balcan, and P. M. Long. The power of localization for efficiently learning linear
separators with noise. In STOC, pages 449–458, 2014.

[ACCD11] Ery Arias-Castro, Emmanuel J Candès, and Arnaud Durand. Detection of an anomalous cluster in a
network. The Annals of Statistics, pages 278–304, 2011.
[AW08]

Arash A Amini and Martin J Wainwright. High-dimensional analysis of semidefinite relaxations for
sparse principal components. In Information Theory, 2008. ISIT 2008. IEEE International Symposium
on, pages 2454–2458. IEEE, 2008.

[BD15]

S. Balmand and A. Dalalyan. Convex programming approach to robust estimation of a multivariate
gaussian model, 2015.

[Ber06]

T. Bernholt. Robust estimators are hard to compute. Technical report, University of Dortmund, Germany,
2006.

[BGM+ 16] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Communication lower
bounds for statistical estimation problems via a distributed data processing inequality. STOC, 2016.
[BJNP13]

Aharon Birnbaum, Iain M Johnstone, Boaz Nadler, and Debashis Paul. Minimax bounds for sparse pca
with noisy high-dimensional data. Annals of statistics, 41(3):1055, 2013.

[BMVX16] Jess Banks, Cristopher Moore, Roman Vershynin, and Jiaming Xu. Information-theoretic bounds and
phase transitions in clustering, sparse pca, and submatrix localization. arXiv preprint arXiv:1607.05222,
2016.
[BR13]

Quentin Berthet and Philippe Rigollet. Optimal detection of sparse principal components in high dimension. The Annals of Statistics, 41(4):1780–1815, 2013.

[Bru09]

S. C. Brubaker. Robust PCA and clustering in noisy mixtures. In SODA 2009, pages 1078–1087, 2009.

[CLMW11] E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? J. ACM, 58(3):11,
2011.
[CMW13]

T Tony Cai, Zongming Ma, and Yihong Wu. Sparse pca: Optimal rates and adaptive estimation. The
Annals of Statistics, 41(6):3074–3110, 2013.

[CR12]

Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111–119, 2012.

[CRPW12] Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of
linear inverse problems. Foundations of Computational mathematics, 12(6):805–849, 2012.
[CRZ16]

T Tony Cai, Zhao Ren, and Harrison H Zhou. Estimating structured high-dimensional covariance and
precision matrices: Optimal rates and adaptive estimation. Electronic Journal of Statistics, 10(1):1–59,
2016.

[CSV16]

Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. arXiv preprint
arXiv:1611.02315, 2016.

[CT12]

Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.

[CW08]

Emmanuel J Candès and Michael B Wakin. An introduction to compressive sampling. IEEE signal
processing magazine, 25(2):21–30, 2008.

22

[dBG08]

Alexandre d’Aspremont, Francis Bach, and Laurent El Ghaoui. Optimal solutions for sparse principal
component analysis. Journal of Machine Learning Research, 9(Jul):1269–1294, 2008.

[dEGJL07] Alexandre d’Aspremont, Laurent El Ghaoui, Michael I Jordan, and Gert RG Lanckriet. A direct formulation for sparse pca using semidefinite programming. SIAM review, 49(3):434–448, 2007.
[DKK+ 16] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust
estimators in high dimensions without the computational intractability. In FOCS, pages 655–664. IEEE,
2016.
[DKK+ 17] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Efficient and optimally robust learning of high-dimensional gaussians. 2017.
[DKS16]

Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. arXiv preprint arXiv:1611.03473, 2016.

[DKS17]

Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Robust learning of fixed-structure bayesian
networks. Available at arXiv:1606.07384, 2017.

[DSS17]

Simon Du, Balakrishnan Sivaraman, and Aarti Singh. Computationally efficient robust estimation of
sparse functionals. arXiv preprint arXiv:1702.07709, 2017.

[GMN14]

Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estimation
and dimensionality. In NIPS, pages 2726–2734, 2014.

[GWL14]

Quanquan Gu, Zhaoran Wang, and Han Liu. Sparse pca with oracle property. In NIPS, pages 1529–1537,
2014.

[HM13]

M. Hardt and A. Moitra. Algorithms and hardness for robust subspace recovery. In COLT 2013, pages
354–375, 2013.

[HR09]

P. J. Huber and E. M. Ronchetti. Robust statistics. Wiley New York, 2009.

[HRRS86] F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust statistics. The approach based
on influence functions. Wiley New York, 1986.
[HTW15]

Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical learning with sparsity. CRC press,
2015.

[JNRS10]

Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for
sparse principal component analysis. Journal of Machine Learning Research, 11(Feb):517–553, 2010.

[Joh01]

Iain M Johnstone. On the distribution of the largest eigenvalue in principal components analysis. Annals
of statistics, pages 295–327, 2001.

[Joh11]

Iain M. Johnstone. Gaussian estimation: Sequence and wavelet models. unpublished manuscript, 2011.

[JP78]

D. S. Johnson and F. P. Preparata. The densest hemisphere problem. Theoretical Computer Science,
6:93–107, 1978.

[KL93]

M. J. Kearns and M. Li. Learning in the presence of malicious errors. SIAM Journal on Computing,
22(4):807–837, 1993.

[KLS09]

A. Klivans, P. Long, and R. Servedio. Learning halfspaces with malicious noise. 2009.

[KNV15]

Robert Krauthgamer, Boaz Nadler, and Dan Vilenchik. Do semidefinite relaxations solve sparse pca up
to the information limit? The Annals of Statistics, 43(3):1300–1322, 2015.

23

[LMTZ12] G. Lerman, M. B. McCoy, J. A. Tropp, and T. Zhang. Robust computation of linear models, or how to
find a needle in a haystack. CoRR, abs/1202.4044, 2012.
[LRV16]

Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In FOCS,
pages 665–674. IEEE, 2016.

[LT15]

P. L. Loh and X. L. Tan. High-dimensional robust precision matrix estimation: Cellwise corruption under
-contamination. Available at arXiv:1509.07229, 2015.

[LZ12]

Zhaosong Lu and Yong Zhang. An augmented lagrangian approach for sparse principal component
analysis. Mathematical Programming, pages 1–45, 2012.

[Ma13]

Zongming Ma. Sparse principal component analysis and iterative thresholding. The Annals of Statistics,
41(2):772–801, 2013.

[MW15]

Tengyu Ma and Avi Wigderson. Sum-of-squares lower bounds for sparse pca. In Advances in Neural
Information Processing Systems, pages 1612–1620, 2015.

[OMH14]

Alexei Onatski, Marcelo J Moreira, and Marc Hallin. Signal detection in high dimension: The multispiked case. The Annals of Statistics, 42(1):225–254, 2014.

[PWBM16] Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub-optimality
of pca for spiked random matrices and synchronization. arXiv preprint arXiv:1609.05573, 2016.
[Rig15]

Philippe Rigollet.
High dimensional statistics.
2015.
http://www-math.mit.edu/ rigollet/PDFs/RigNotes15.pdf.

[SD15]

Jacob Steinhardt and John C Duchi. Minimax rates for memory-bounded sparse linear regression. In
COLT, 2015.

[Ser03]

R. Servedio. Smooth boosting and learning with malicious noise. JMLR, 4:633–648, 2003.

[Tsy09]

Alexandre B Tsybakov. Introduction to nonparametric estimation. Revised and extended from the 2004
French original. Translated by Vladimir Zaiats. Springer Series in Statistics. Springer, New York, 2009.

[Tuk75]

J.W. Tukey. Mathematics and picturing of data. In Proceedings of ICM, volume 6, pages 523–531, 1975.

[Val85]

L. Valiant. Learning disjunctions of conjunctions. In Proc. 9th IJCAI, pages 560–566, 1985.

[WBS16]

Tengyao Wang, Quentin Berthet, and Richard J Samworth. Statistical and computational trade-offs in
estimation of sparse principal components. The Annals of Statistics, 44(5):1896–1930, 2016.

[WGL15]

Zhaoran Wang, Quanquan Gu, and Han Liu. Statistical limits of convex relaxations. arXiv preprint
arXiv:1503.01442, 2015.

[WTH09]

Daniela M Witten, Robert Tibshirani, and Trevor Hastie. A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis. Biostatistics, page kxp008,
2009.

[ZL14]

T. Zhang and G. Lerman. A novel m-estimator for robust pca. J. Mach. Learn. Res., 15(1):749–808,
January 2014.

24

available

at

A

Information theoretic estimators for robust sparse estimation

This section is dedicated to the proofs of the following two facts:
Fact A.1. Fix ε, δ > 0, and let k be fixed. Given an ε-corrupted set of samples X1 , . . . , Xn ∈ Rd from N (µ, I),
where µ is k-sparse, and


k log(d/ε) + log 1/δ
n=O
,
ε2
there is an (inefficient) algorithm which outputs µ
b so that with probability 1 − δ, we have kµ − µ
bk2 ≤ O(ε). Moreover,
up to logarithmic factors, this rate is optimal.
Fact A.2. Fix ρ, δ > 0. Suppose that ρ = O(1). Then, there exist universal constants c, C so that: (a) if ε ≤ cρ, and
we are given a ε-corrupted set of samples from either N (0, I) or N (0, I + ρvv T ) for some k-sparse unit vector v of
size
!

k + log kd + log 1/δ
,
n=Ω
ρ2
then there is an (inefficient) algorithm which succeeds with probability 1 − δ for the detection problem. Moreover, if
ε ≥ Cρ, then no algorithm succeeds with probability greater than 1/2, and this statistical rate is optimal.
The rates in Facts A.1 and A.2 are already known to be optimal (up to log factors) without noise. Thus in this
section we focus on proving the upper bounds, and the lower bounds on error.
The lower bounds on what error is achievable follow from the following two facts, which follow from Pinsker’s
inequality (see e.g. [CT12]), and the fact that the corruption model can, given samples from D1 , simulate samples
from D2 by corrupting an O(ε) fraction of points, if dTV (D1 , D2 ) ≤ O(ε).
Fact A.3. Fix ε > 0 sufficiently small. Let µ1 , µ2 be arbitrary. There is some universal constant C so that if
dTV (N (µ1 , I), µ2 , I) ≤ ε, then kµ1 − µ2 k2 ≤ Cε, and if kµ1 − µ2 k2 ≤ ε, then dTV (N (µ1 , I), N (µ2 , I)) ≤ Cε.
Fact A.4. Fix ρ = O(1). Let u, v be arbitrary unit vectors. Then dTV (N (0, I), N (0, I + ρvv T )) = Θ(ρ), and
dTV (N (0, I + ρvv T ), N (0, I + ρuuT )) = O(L(u, v)).
Our techniques for proving the upper bounds go through the technique of agnostic hypothesis selection via tournaments. Specifically, we use the following lemma:
Lemma A.5 ([DKK+ 16], Lemma 2.9). Let C be a class of probability distributions. Suppose that for some n, ε, δ > 0
there exists an algorithm that given an ε-corrupted set of samples from some D ∈ C, returns a list of M distributions so
that with 1 − δ/3 probability there exists a D′ ∈ M with dTV (D′ , D) < γ. Suppose furthermore that with probability
1 − δ/3, the distributions returned by this algorithm are all in some fixed set M. Then there exists another algorithm,
which given O(N +(log(|M|)+log(1/δ))/ǫ2 ) samples from Π, an ε-fraction of which have been arbitrarily corrupted,
returns a single distribution Π′ so that with 1 − δ probability dTV (D′ , D) < O(γ + ε).

A.1 Proof of Upper Bound in Fact A.1
′
′
Let MA be the set of distributions {N
√ (µ , I)}, where µ ′ ranges over the set of k-sparse vectors so that each coordinate
′
of µ is an integer multiple of ε/(10 d), and so that kµ − µk2 ≤ A. We then have:
√

Claim A.6. There exists a N (µ′ , I) = D ∈ MA so that kµ − µ′ k2 ≤ O(ε). Moreover, |MA | ≤ kd · (10A d/ε)k .

Proof. The first claim
√ is straightforward. We now prove the second claim. For each possible set of k coordinates, there
are at √
most (10A d/ε)k vectors supported on those k coordinates with each coordinate
being an integer multiple of

ε/(10 d) with distance at most A from any fixed vector. Enumerating over all kd possible choices of k coordinates
yields the desired answer.
25

The estimator is given as follows: first,
p run NAIVE P RUNE (X1 , . . . , Xn , δ) to output some µ0 so that with probability 1 √
− δ, we have kµ0 − µk2 ≤ O( d log n/δ). Round each coordinate of µ0 so that it is an integer multiple
′′
of ε/(10 d). Then, output the set of distributions
M′ = {N (µ′′ , I)},
p where µ is any k-sparse vector with each
√
coordinate being an integer multiple of ε/(10 d), with kαk2 ≤ O( d log n/δ). With probability 1 − δ, we have
M′ ⊆ MO(√d log n/δ) . By Claim A.6, applying Lemma A.5 to this set of distributions yields that we will select, with
probability 1 − δ, a µ′ so that kµ − µ′ k2 ≤ O(ε). By Claim A.6, this requires
!
!

log |MO(√d log n/δ) |
log kd + k log(d/ε) + log 1/δ
=O
,
O
ε2
ε2
samples, which simplifies to the desired bound, as claimed.

A.2 Proof of Upper Bound in Fact A.2
Our detection algorithm is given as follows. We let N be an O(1)-net over all k-sparse unit vectors, and we apply
Lemma A.5 to the set {N (0, I + ρuuT )}u∈N ∪ {N (0, I)}. Clearly, we have:

Claim A.7. |M| = kd 2O(k) .
By Fact A.4 and the guarantees of Lemma A.5, by an appropriate setting of parameters, if we have
!



k + log kd + log 1/δ
log |M| + log 1/δ
=O
n=O
ε2
ε2

samples, then with probability 1 − δ we will output N (0, I) if and only if the true model is N (0, I). This proves the
upper bound.

B Omitted Details from Section 4
B.1

Writing non-robust algorithms as dual norm maximization

In this section we will briefly review well-known non-robust algorithms for sparse mean recovery and for sparse PCA,
and write them using our language.
Thresholding Recall that in the (non-robust) sparse mean estimation problem, one is given samples X1 , . . . , Xn ∼
N (µ, I) where µ is k-sparse. The goal is then to recover µ. It turns out the simple thresholding algorithm T HRESH OLD M EAN given in Algorithm 5 suffices for recovery:
Algorithm 5 Thresholding for sparse mean estimation
1: function T HRESHOLD M EAN (X1 , . . . , Xn )
Pn
2:
Let µ
b = n1 i=1 Xi
3:
Let S be the set of k coordinates of µ
b with largest magnitude
4:
Let µ
b′ be defined to be µ
b′i = µ
bi if i ∈ S, 0 otherwise
5:
return µ
b′
6: end function
The correctness of this algorithm follows from the following folklore result, whose proof we shall omit for conciseness:
Fact B.1 (c.f. [Rig15]). Fix ε, δ > 0, and let X1 , . . . , Xn be samples from N (µ, I), where µ is k-sparse and
!

log kd + log 1/δ
n=Ω
.
ε2
Then, with probability 1 − δ, if µ
b′ is the output of T HRESHOLD M EAN, we have kb
µ′ − µ
bk2 ≤ ε.
26

To write this in our language, observe that

where µ
b=

1
n

Pn

i=1

T HRESHOLD SM EAN(X1 , . . . , Xn ) = kb
µk∗Uk · dUk (b
µ) ,
Xi .

L1 relaxation In various scenarios, including recovery of a spiked covariance, one may envision the need to take
k-sparse eigenvalues a matrix A, that is, vectors which solve the following non-convex optimization problem:
max v T Av
s.t. kvk2 = 1, kvk0 ≤ k .

(16)

However, this problem is non-convex and cannot by solved efficiently. This motivates the following SDP relaxation of
(16): First, one rewrites the problem as
max tr(AX)
s.t. tr(X) = 1, kXk0 ≤ k 2 , X  0 , rank(X) = 1

(17)

where kXk0 is the number of non-zeros of X. Observe that since X is rank 1 if we let X = vv T these two problems
are indeed equivalent. Then to form the SDP, one removes the rank constraint, and relaxes the ℓ0 constraint to a ℓ1
constraint:
max tr(AX)
s.t. tr(X) = 1, kXk1 ≤ k , X  0 .

(18)

The work of [dEGJL07] shows that this indeed detects the presence of a spike (but at an information theoretically
suboptimal rate).
Finally, by definition, for any PSD matrix A, if X is the solution to (18) with input A, we have X = dXk (A).

B.2

Numerical precision

In general, we cannot find closed form solutions for dXk (A) in finite time. However, it is well-known that we can find
these to very high numerical precision in polynomial time. For instance, using the ellipsoid method, we can find an
M ′ so that kM ′ − dXk (A)k∞ ≤ ε in time poly(d, log 1/ε). It is readily verified that if we set ε′ = poly(ε, 1/d) then
the numerical precision of the answer will not effect any of the calculations we make further on. Thus for simplicity
of exposition we will assume throughout the paper that given any A, we can find dXk (A) exactly in polynomial time.

C

Omitted Proofs from Section 4


n −1
Proof of Theorem 4.5. Fix n as in Theorem 4.5, and let δ1 = εn
δ. By convexity of Sn,ε and the objective function,
it suffices to show that with probability 1 − δ, the following holds:
∀wI s.t. |I| = (1 − ε)n :
Condition on the event that

n
X

n

1X
Xi
n i=1
By Corollary 4.1, this occurs with probability 1 − O(δ).

27

∗

wi Xi

i=1

Uk

≤η.

∗
Uk

≤ε.

(19)

Fix any I ⊆ [n] so that |I| = (1 − ε)n. By Corollary 4.1 applied to I c , we have that there is some universal
constant C so that as long as
εn ≥ C ·
then with probability 1 − δ ′ ,

Since log

n
εn



min(d, k 2 ) + log

d2
k2



+ log

n
εn

α2
1 X
Xi
εn
i6∈I



+ log 1/δ

,

(20)

∗

≤α.

(21)

Uk

= Θ(nε log 1/ε), (20) is equivalent to the condition that


min(d, k 2 ) + log
ε log 1/ε
n ε−C
≥C·
2
α
α2

p
Let α = O( log 1/ε). By our choice of η, we have that 0 ≤ ε −
constants, since by our choice of n we have
min(d, k 2 ) + log
εn
≥C·
2
α2

d2
k2

d2
k2

ε log 1/ε
η2





+ log 1/δ

.

≤ ε/(2C), and by an appropriate setting of

+ log 1/δ

,


n
we have that (21) holds with probability 1−δ ′ . Thus by a union bound over all εn
choices of I so that |I| = (1−ε)n,
we have that except with probability 1 − δ, we have that (21) holds simultaneously for all I with |I| = (1 − ε)n. The
desire result then follows from this and (19), and a union bound.
Proof of Theorem 4.6. This follows from the exact same techniques as the proof of Theorem 4.5, by replacing all Uk
with Xk , and using Theorem 4.2 instead of Corollary 4.1.

D

Computational Barriers for sample optimal robust sparse mean estimation

We conjecture that the rate achieved by Theorem 5.1 is tight for computationally efficient algorithms (up to log factors).
Intuitively, the major difficulty is that distinguishing between N (µ1 , I) and N (µ2 , I) given corrupted samples seems
to inherently require second moment (or higher) information, for any µ1 , µ2 ∈ Rd . Certainly first moment information
by itself is insufficient. In this sparse setting, this is very problematic, as this inherently asks for us to detect a large
sparse eigenvector of the empirical covariance. This more or less reduces to the problem solved by (16). This in turn
requires us to relax to the problem solved by SDPs for sparse PCA, for which we know Ω(k 2 log d/ε2 ) samples are
necessary for non-trivial behavior to emerge. We leave resolving this gap as an interesting open problem.

28

