List-Decodable Mean Estimation in Nearly-PCA Time
Year: 2021

Abstract:
Robust statistics has traditionally focused on designing estimators tolerant to a minority of contaminated data. List-decodable learning [CSV17] studies the more challenging regime where only a minority 1 k fraction of the dataset, k ≥ 2, is drawn from the distribution of interest, and no assumptions are made on the remaining data. We study the fundamental task of list-decodable mean estimation in high dimensions. Our main result is a new algorithm for bounded covariance distributions with optimal sample complexity and near-optimal error guarantee, running in nearly-PCA time. Assuming the ground truth distribution on R has identity-bounded covariance, our algorithm outputs O(k) candidate means, one of which is within distance O( √ k log k) from the truth. Our algorithm runs in time Õ(ndk)2, where n is the dataset size. This runtime nearly matches the cost of performing k-PCA on the data, a natural bottleneck of known algorithms for (very) special cases of our problem, such as clustering well-separated mixtures. Prior to our work, the fastest runtimes were Õ(ndk) [DKK20], and Õ(ndk) [CMY20] for an unspecified constant C ≥ 6. Our approach builds on a novel soft downweighting method we term SIFT, arguably the simplest known polynomial-time mean estimator in the list-decodable setting. To develop our fast algorithms, we boost the computational cost of SIFT via a careful “win-win-win” analysis of an approximate Ky Fan matrix multiplicative weights procedure we develop, which may be of independent interest. ∗Part of this work was done as an intern at Microsoft Research. Throughout this work, the Õ notation hides logarithmic factors in n and the failure probability. 35th Conference on Neural Information Processing Systems (NeurIPS 2021).

text: √ k log k) from the truth.
Our algorithm runs in time Õ(ndk)2, where n is the dataset size. This runtime nearly matches the cost of performing k-PCA on the data, a natural bottleneck of known algorithms for (very) special cases of our problem, such as clustering well-separated mixtures. Prior to our work, the fastest runtimes were Õ(n2dk2) [DKK20], and Õ(ndkC) [CMY20] for an unspecified constant C ≥ 6. Our approach builds on a novel soft downweighting method we term SIFT, arguably the simplest known polynomial-time mean estimator in the list-decodable setting. To develop our fast algorithms, we boost the computational cost of SIFT via a careful “win-win-win” analysis of an approximate Ky Fan matrix multiplicative weights procedure we develop, which may be of independent interest.
∗Part of this work was done as an intern at Microsoft Research. 2Throughout this work, the Õ notation hides logarithmic factors in n and the failure probability.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1 Introduction
text: Mean estimation has emerged as one of the cornerstone tasks in robust statistics, as the most basic in a hierarchy of increasingly complex estimation problems. The problem is straightforward to state: given samples from a “nice” ground-truth distribution D, where an adversary has (arbitrarily) corrupted a fraction of the data, recover the mean of D as accurately as possible. Due to its fundamental nature, robust mean estimation has received extensive study in the statistics, theoretical computer science, and machine learning communities, starting from the 1960s [Ans60, Tuk60, Hub64, Tuk75]. Despite the apparent simplicity of the problem, efficient algorithms achieving near-optimal error rates were not known in high-dimensional settings until recently [LRV16, DKK+19]. These works studied mean recovery in the traditional setting where a majority of the data is “trusted,” i.e. the fraction of corruptions is strictly less than 12 . For the standard formulation of robust mean estimation, this assumption is necessary. Indeed, if only an α ≤ 12 fraction of points can be trusted, the dataset could consist of O( 1α ) well-separated clusters of “good” points. The mean of each individual cluster is an equally valid solution to the estimation problem, so asking for a single solution is ill-posed. In many settings of theoretical and practical interest, having a majority of inlier points is too strong of an assumption. To circumvent the issue of well-posedness in the α ≤ 12 regime, [CSV17] proposed a relaxed learning notion termed list-decodable learning. Rather than restricting to a single hypothesis, the algorithm may output a list of O( 1α ) hypotheses, guaranteeing at least one of them is close to the truth. In the context of robust mean estimation, this amounts to outputting O( 1α ) candidate means. A natural problem in its own right, list-decodable mean estimation also generalizes a number of other problems. A prototypical example is learning well-separated mixture models, which has received extensive treatment in the literature [Das99, VW04, AM05, DS07, AK05, RV17, HL18, DKS18, KSS18]. In this problem, data is drawn from a uniform mixture3 of k “nice” distributionsD1, . . . ,Dk with far apart means, and the goal is to recover clusters coming from each component. By running a list-decodable estimation procedure with α = 1k , each cluster is an equally valid “ground truth,” so the output must contain candidate means close to each true mean. If the candidates are sufficiently close, standard techniques recover the true clustering. List-decodable mean estimation robustly extends this problem to tolerate adversarial noise or non-uniformity, up to constants in the output size. Moreover, list-decodable mean estimation can be used to model important data science applications such as crowdsourcing (where a majority of respondents could be unreliable or malicious) [SVC16, MV18], or semi-random community detection in stochastic block models [CSV17]. This primitive is particularly useful in the context of semi-verified learning [CSV17, MV18], where a learner can audit a small amount of trusted data. Even if the trusted dataset is too small to directly learn from, in conjunction with a list-decodable learning procedure it can pinpoint a candidate hypothesis consistent with the verified data (indeed, only roughly log 1α vetted points are required). The first tractable algorithm for high-dimensional list-decodable mean estimation was given by [CSV17]. Their work considered the setting where D has (unknown) covariance Σ σ2I for some known σ (i.e. a second moment bound). In this setting, [CSV17] gave a sample-optimal, polynomial-time algorithm outputtingO( 1α ) candidate means, so some candidate is within `2 distance O(σ √ α−1 logα−1) from the mean of D. As later demonstrated in [DKS18], this error is optimal up to logarithmic factors. However, the [CSV17] algorithm heavily relies on black-box semidefinite programming solvers, and thus the runtime is prohibitively large in high-dimensional instances. The goal of our work is to develop much faster, truly scalable algorithms for list-decodable mean estimation which achieve optimal statistical guarantees. This goal fits broadly into a larger line of work focused on understanding the computational cost of robustness for basic statistical tasks. In some settings, this line has demonstrated strong evidence that robustness comes at an inherent computational cost [DKS17, HL19]. In contrast, recent algorithms have been developed that achieve robustness essentially “for free” in many other settings [CDG19, DHL19, CDGW19, LY20, JLT20]. While list-decodable mean estimation has received a fair amount of attention, there have only been a few results achieving improved runtimes. One line of work proposed an algorithm framework termed multi-filtering [DKS18, DKK20], based on learning multiple candidate “weight functions.” In particular, [DKK20] uses this approach to design an algorithm achieving near-optimal error in time Õ(n2dα−2), where n is the overall dataset size. While this dramatically improves over the runtime
3Some algorithms extend beyond the uniform setting; we present it this way for simplicity of exposition.
in [CSV17], the quadratic dependence on n is not ideal in high-dimensional settings. Concurrently, the work [CMY20] proposes a different, descent-based algorithm based on (approximate) positive semidefinite programming, achieving optimal error (up to constant factors) in time Õ(ndα−C) for some constant C ≥ 6. When α = Θ(1), the [CMY20] runtime is nearly-linear in the problem input size. However, if α−1 scales polynomially with d, e.g. a mixture model with many components in moderate dimension, then this large dependence on α−1 may also be prohibitively slow. In contrast to this somewhat murky runtime landscape, the state of affairs for clustering separated mixture models is relatively clear. The fastest known algorithm for clustering a mixture of k wellseparated components is almost twenty years old [VW04], and runs in time Õ(ndk), as a relatively simple and elegant application of (approximate) k-principal components analysis (k-PCA). Since list-decodable mean estimation can be thought of as the natural robust analog to clustering mixture models, it is natural to ask:
Can we perform list-decodable mean estimation as efficiently as learning mixture models?
Concretely, since clustering mixture models is an instance of list-decodable learning with α = k−1, the question becomes: can we solve list-decodable mean estimation in time Õ(ndα )? This presents itself as a natural barrier, since further improvement would imply faster learning of mixture models.

heading: 2 Our results
text: Our main contribution is to answer this question affirmatively with near-optimal statistical guarantees. We start by formally defining the problem we study, which we call “list-decodable mean estimation.”
Definition 1. Given T ⊂ Rd and 0 < α ≤ 12 such that an α-fraction of T are independent draws from a distribution D with unknown target mean µ∗ and unknown covariance Σ σ2I, output a small list of vectors {µ̂j}j∈L such that minj∈L ‖µ̂j − µ∗‖2 is minimized.
We emphasize that no assumptions are made on the remaining 1− α fraction of T , i.e. they may be arbitrary and chosen by a computationally unbounded adversary allowed to inspect the inliers. In the setting of Definition 1, our main result states that we can solve list-decodable mean estimation nearlyoptimally in the time it takes to perform k-PCA poly-logarithmically many times, for k = Θ( 1α ).
Theorem 1 (See Corollary 3 of the supplementary material). Given |T | = n = Ω( dα ) samples, there is an algorithm with runtime Õ ( nd α ) that with high probability outputs a list of m vectors {µj}j∈[m], for m = O( 1α ), such that minj∈[m] ‖µ ∗ − µj‖2 = O(σα− 1 2 √ logα−1).
A few remarks are in order. First, a list size of Ω( 1α ), sample complexity of Ω( d α ), and error of Ω(σα− 1 2 ) are information-theoretically necessary for this problem [DKS18]. We also provide an algorithm in the supplementary material returning m = O( 1α ) hypotheses {µj}j∈[m] attaining optimal error minj∈[m] ‖µ∗ − µj‖2 = O(σα− 1 2 ), with an additive runtime overhead of Õ(α−6). Without loss of generality α−1 = o(d), as otherwise there is a trivial algorithm (cf. Appendix A of the supplementary material), so the α−6 additive term is only dominant in the range α−1 ∈ [ω( √ d), o(d)] assuming n = Θ( dα ). Even with this overhead, our runtime is the best-known in all parameter regimes. Our approach is inspired by the way in which fast algorithms for robust mean estimation in the α→ 1 regime were built. First, a “simple” polynomial (but not nearly-linear) time algorithm — namely, the filter — was developed [DKK+19, DKK+17, Ste18]. Then, building on the framework of this simple algorithm, near-linear time algorithms were developed [CDG19, DHL19] using tools from the continuous optimization community — specifically, matrix multiplicative weights regret analyses. In this paper, we accomplish both these steps for the α 12 regime. First, we design a simple “basic” algorithm for the list-decodable mean estimation problem, and then speed it up using matrix regret minimization tools. As explained below, both steps require substantially new ideas.
SIFT: a new, simple algorithm for list-decodable learning. Our first main contribution is a novel algorithm for list-decodable mean estimation, which we call SIFT (Subspace Isotropic FilTering),4
4After the initial dissemination of this work, we were made aware there is another (unrelated) algorithm named SIFT developed in the computer vision community [Low99].
achieving optimal statistical guarantees in time Õ(n 2d α ). While by itself, SIFT does not achieve a nearly-linear runtime, its framework is vital in designing our more sophisticated algorithms. Crucially, SIFT is conceptually different from all prior approaches for our problem, with a complete decoupling of a “filtering” step and a “clustering” step; it is these differences that allow for our later speedups. The main advantage of SIFT is its simplicity. All prior algorithms for list-decodable mean estimation were quite complicated, with involved and lengthy analyses, whereas an analysis of SIFT fits in just over two pages. We believe SIFT is of independent interest (both theoretically and practically), and its framework may find applications in other list-decodable learning settings.
FastSIFT: speeding up SIFT via Ky Fan regret minimization. While each SIFT iteration can be performed in time Õ(ndk), the algorithm requires Θ(n) iterations in the worst case, as there are instances where each iteration removes only one data point. The main challenge is to combine the SIFT analysis with a downweighting procedure guaranteeing termination in polylogarithmically many iterations. To achieve this, we use tools from semidefinite programming (SDP) to design iterative schemes with stronger termination guarantees. This mirrors, and is inspired by, the α→ 1 regime, where tools such as packing SDP solvers [CDG19] and matrix multiplicative weights [DHL19] were used to speed up the basic filter. We note that [CMY20] also uses SDP tools to obtain their runtime, but in a substantially different way: they design a black-box Ky Fan norm packing SDP subroutine, whereas we directly use a (stronger) regret guarantee to guide weight removal. Finally, while there have been substantial recent runtime advances for solving SDPs (see e.g. [JKL+20]), these guarantees are too weak for our purposes, requiring the development of new approximate SDP tools.

heading: 3 Preliminaries
text: General notation. We letN (µ,Σ) denote the multivariate Gaussian distribution with specified mean and covariance, and [d] denote the naturals 1 ≤ j ≤ d. When applied to a vector argument, ‖·‖p is the `p norm. We denote the (solid) probability simplex in n dimensions by ∆n = {w ∈ Rn≥0 | ‖w‖1 ≤ 1}. The all-ones vector in appropriate dimension is 1. The identity matrix in appropriate dimension is I. We use the standard Loewner order on the set of symmetric matrices Sd = Rd×d with positive semidefinite subset Sd≥0. For k ∈ [d], the operation λk(·) on Sd returns the kth largest eigenvalue. When applied to a matrix in Sd≥0, ‖·‖k for k ∈ [d] is the Ky Fan norm (sum of the top k eigenvalues), and ‖·‖op in particular is the Ky Fan 1 norm. The inner product on Sd × Sd is 〈A,B〉 = Tr (AB).
Distributions. Let T be a set of points in Rd with |T | = n, and let w ∈ ∆n. For any T ′ ⊆ T , wT ′ ∈ ∆n is the vector which equals w on coordinates in T ′, and is zero elsewhere. We refer to the empirical mean and covariance, parameterized by weights w and subset T ′ ⊆ T , by
µw(T ′) := ∑ i∈T ′ wi ‖wT ′‖1 Xi, Covw(T ′) := ∑ i∈T ′ wi ‖wT ′‖1 (Xi − µw(T ′)) (Xi − µw(T ′)) > .
We denote uniform samples i from a set S by the notation i ∼ S.
Deterministic assumption. In the list-decodable mean estimation problem, we are given a set T of n points {Xi}i∈T in Rd, under Definition 1.5 Without loss, we assume σ = 1, which generalizes appropriately by scaling the dataset by σ−1. Regarding the sample size n, we recall the following (note that the matrix in Assumption 1 is not the covariance, as it is centered at the true mean). Proposition 1 (Proposition B.1, [CSV17]). For any constant ∈ (0, 1), there are constants c, C > 0 such that with probability at least 1− exp(−Ω(n)), for n = Cdα , if an (1 + )α fraction of points in {Xi}i∈T ⊆ Rd is drawn from D with covariance bounded by cI, then Assumption 1 holds. Assumption 1. ∃S ⊆ {Xi}i∈T ⊆ Rd of size αn = Θ(d) with Ei∼S [(Xi − µ∗) (Xi − µ∗)>] I.
In the remainder of the paper, we operate under Assumption 1, i.e. that there is a subset S of the dataset whose centered covariance around µ∗ is identity-bounded. Proposition 1 implies that this assumption holds for any failure probability larger than exp(−Ω(d)) (up to constants in parameter definitions); for any smaller failure probability, Proposition 1 implies that the assumption still holds by adjusting the sample size by a logarithmic factor. We also assume 1α ≤ d for simplicity, and handle the regime 1α = Ω(d) with a much simpler algorithm in Appendix A of the supplemental material.
Finally, k will be reserved for values which are Θ( 1α ) for explicitly stated constants. In particular, our algorithms will use operations such as principal components analysis in Θ( 1α ) dimensions. This is because a substantial portion of the challenge is reducing to the problem of learning the mean in Θ( 1α ) dimensions, at which point naïve random sampling suffices (up to logarithmic factors).
Organization. In this shortened version of our paper, we give a full statement and analysis of our “slow algorithm” SIFT in Section 4, achieving optimal sample complexity and error, at a logarithmic overhead in list size and an O(n) overhead in runtime compared to our final method. We then provide a detailed outline of our techniques to improve this result in Section 5, focusing on the statement of key technical ingredients developed in this work. Due to space constraints, we defer a more rigorous treatment of proofs, as well as an extended exposition of our techniques and comparison to the prior work on this problem, to an unabridged version in the supplementary material.
4 Warmup: SIFT algorithm and analysis
We develop a conceptually new and simple algorithm for solving list-decodable mean estimation based on a “soft downweighting” approach, which forms the backbone of our faster methods. In brief, its design philosophy can be summarized as follows: first learn the mean in all but Θ( 1α ) directions, and then randomly sample in the remaining subspace. All omitted proofs are either straightforward or from prior work, and are given in Section 3 of the supplementary material. We define two useful concepts in analyzing our downweighting methods.
Definition 2 (Saturated weights). We call w ∈ ∆n “saturated” if w ≤ 1n1 and ‖wS‖1 ≥ α √ ‖w‖1. Definition 3 (Safe scores). We call scores {τi}i∈T ∈ Rn≥0 “safe with respect to w ∈ ∆n” if∑ i∈S
wi ‖wS‖1 τi ≤ 12 ∑ i∈T wi ‖w‖1 τi. When w is clear from context, we simply call τ “safe”.
In algorithms based on soft filtering in the presence of a small amount of adversarial noise (e.g. [DKK+17, Li18, Ste18]), a typical goal is to iteratively remove more “good weight” than “bad weight.” However, when the overwhelming majority of the initial weight is bad, this is too strong of a goal. The intuition for Definition 2 is that a weaker goal suffices for our guarantees; while the good weight decreases throughout, Definition 2 requires that the good weight becomes more saturated when more weight is removed. We now make the connection between these definitions formal. Lemma 1. Let weights w be saturated. Then w′ is also saturated, where w′ is the result of the following update: let {τi}i∈T be safe with respect to w, and update for all i ∈ T :
w′i ← (
1− τi τmax
) wi, where τmax := max
i∈T |wi 6=0 τi. (1)
We next give three helper lemmas which reason about how the quality of empirical estimates based on S deteriorate, as weight allocated to S is reduced. The first shows how the quality of the empirical mean relates to the empirical covariance and proportion of weight in S.
5Abusing notation, we let T denote both the point set and indices, interchangeably using Xi ∈ T and i ∈ T .
Lemma 2. If w ∈ ∆n has w ≤ 1n1 entrywise, ‖µw(T )− µ ∗‖2 ≤ √ 2 ‖Covw(T )‖op ‖w‖1 ‖wS‖1 + 2α‖w‖1 .
The second shows how the empirical covariance of S grows relative to how much of S is kept. Lemma 3. Let w ∈ ∆n have w ≤ 1n1 entrywise. Then Covw(S) α ‖wS‖1 I.
The third shows how a bound on the saturation of S in a weight vector can be used to bound the distance between empirical means in S and T via the weighted empirical covariance matrix.
Lemma 4. (µw(S)− µw(T ))(µw(S)− µw(T ))> ‖w‖1 ‖wS‖1 Covw(T ).
We now present SIFT as Algorithm 1. It requires calls to an approximate k-PCA subroutine Power, the classical simultaneous power iteration method, whose guarantees we state here. Proposition 2 (Theorem 1, [MM15]). For any δ ∈ (0, 1) and k ∈ [d], there is an algorithm, Power, which takes as input k, δ, A ∈ Sd≥0 and ∈ (0, 1), and returns with probability 1 − δ a set of orthonormal vectors V ∈ Rd×k such that if V:i is column i of V,
〈V:i,AV:i〉 ∈ [1± ]λi (A) for all i ∈ [k], ∥∥(I−VV>)A (I−VV>)∥∥op ≤ (1 + )λk+1 (A) .
When A is given in the form M>M for some M ∈ Rn×d, the runtime of Power is O ( ndk log ( d δ )) .
Algorithm 1 SIFT(T, δ)
1: Input: T ⊂ Rd with |T | = n satisfying Assumption 1, δ ∈ (0, 1) 2: w(0) ← 1n1T , t← 0, β ← 1, k ← d 4 αe 3: V← Power(Covw(t)(T ), k, 0.2, δ2n ) 4: while λk(V>Covw(t)(T )V) ≥ 4√β do
5: τ (t)i ← ∥∥∥Σ− 12 V> (Xi − µw(T ))∥∥∥2
2 for all i ∈ T 6: w(t+1)i ← ( 1− τ (t) i
τ (t) max
) w
(t) i for all i ∈ T , where τ (t) max := maxi∈T |w(t)i 6=0 τ (t) i 7: t← t+ 1, β ← ∥∥w(t)∥∥
1
8: V← Power(Covw(t)(T ), k, 0.2, δ2n ) 9: end while 10: return L := {VV>Xi + ( I−VV> ) µw(t)(T ) where i ∈ T is sampled uniformly at random},
with list size |L| = d 2α log 2 δ e
As Lines 4 through 9 of Algorithm 1 constitute a weight removal method of the form given in (1), we now demonstrate the scores used are safe, which implies that w(t) is always saturated.
Lemma 5. In each iteration t of Algorithm 1 until termination, τ (t) is safe with respect to w(t).
Proof. Throughout this proof, let w := w(t) and τ := τ (t). Furthermore, let V, β correspond to the weights w(t), and let Σ := V>Covw(t)(T )V. We first compute the average score in S:∑ i∈S wi ‖wS‖1 τi = ∑ i∈S wi ‖wS‖1 ∥∥∥Σ− 12 V> (Xi − µw(T ))∥∥∥2 2
= ∑ i∈S wi ‖wS‖1 (∥∥∥Σ− 12 V> (Xi − µw(S))∥∥∥2 2 + ∥∥∥Σ− 12 V> (µw(S)− µw(T ))∥∥∥2 2 ) = 〈 Σ−1,V>Covw(S)V 〉 + ∥∥∥Σ− 12 V> (µw(S)− µw(T ))∥∥∥2
2 ≤ 〈 Σ−1, α
‖wS‖1 I 〉 + ‖w‖1 ‖wS‖1 ≤ 1 4 〈√ βI, 1√ β I 〉 + √ β α ≤ k 2 .
The first three equalities expanded definitions; the first inequality is by Lemmas 3 and 4. The second inequality used Definition 2 twice, which implies that ‖wS‖1 ≥ α √ β, as well as the exit condition in
Line 4. The third inequality follows from the definition of k. Finally, we conclude that τ is safe, by∑ i∈T wi ‖w‖1 τi = ∑ i∈T wi ‖w‖1 ∥∥∥Σ− 12 V> (Xi − µw(T ))∥∥∥2 2
= 〈 Σ−1,V> (∑ i∈T wi ‖w‖1 (Xi − µw(T )) (Xi − µw(T ))> ) V 〉 = 〈 Σ−1,Σ 〉 = k.
Theorem 2. Under Assumption 1, with probability 1 − δ, the output of Algorithm 1 satisfies minµ∈L ‖µ− µ∗‖22 ≤ 22 α . The overall runtime of Algorithm 1 is O ( n2dk log ( n δ )) .
Proof. Runtime. There are at most n iterations in Algorithm 1, since at least one weight is zeroed out in each iteration. Further, the bottleneck operation in each iteration is Power, since an eigendecomposition of Σ takes time O(k3) = O(ndk). Since is a constant in Proposition 2, this yields the runtime. We note that the algorithm must terminate before removing all the weight: since w is saturated, ‖w‖1 ≥ α2 via Definition 2 and ‖w‖1 ≥ ‖wS‖1. By a union bound, with probability 1− δ2 , Proposition 2 applies every iteration; we condition on this event for the remainder of the proof. Correctness. As in Lemma 5, we let w denote the weights in the last iteration of the algorithm (after exiting on Line 10). Denote P := VV> and Yi := PXi for all i ∈ T . Since
∑ i∈S 1 αn (Yi −Pµ∗) (Yi −Pµ∗)> = P (∑ i∈S 1 αn (Xi − µ∗) (Xi − µ∗)> ) P P,
by Assumption 1, the expectation of ‖Yi −Pµ∗‖22 for a uniformly random sample i ∈ S is 4 α by linearity of trace. By Markov, with probability ≥ 12 a sample from S has ‖Yi −Pµ ∗‖22 ≤ 8 α , so with probability ≥ 1− δ2 , some element of L uses an Xi with ‖Yi −Pµ ∗‖22 ≤ 8 α . For this i, we expand
‖(PXi + (I−P)µw(T ))− µ∗‖22 = ‖Yi −Pµ ∗‖22 + ‖(I−P) (µw(T )− µ ∗)‖22
≤ 8 α + ‖(I−P) (µw(T )− µ∗)‖22 .
To bound this second term, we apply Lemma 2 on the set of points {(I−P)Xi}i∈T . This implies
‖(I−P) (µw(T )− µ∗)‖22 ≤ 2β
‖wS‖1 ‖(I−P)Covw(T )(I−P)‖op +
2α β ≤ 12
√ β
‖wS‖1 +
2α β ≤ 14 α .
Here, the last inequality used that saturation implies β ≥ α2. The second used that Power and the termination condition imply that, since eigenvalues of Σ are the same as VV>Covw(T )VV>,
‖(I−P) Covw(T ) (I−P)‖op ≤ 1.2λk(Covw(T )) ≤ 1.5λk(Σ) ≤ 6√ β .
While Theorem 2 achieves the desired error, it has a quadratic dependence on the sample size n, and a suboptimal list size by a factor of O(log 1δ ). We address both issues with our fast algorithm.
5 Nearly-PCA time algorithm: overview of FastSIFT
In this section, we highlight the main technical ideas behind our fast algorithms. In particular, we show how to leverage tools built in developing SIFT and combine them with a weight removal scheme based on a Ky Fan variant of the matrix multiplicative weights (MMW) regret minimization framework we develop, to give our final algorithm. Throughout this overview, we define integer k = Θ( 1α ) to represent some dimensionality of a linear subspace; constants will be specified in relevant algorithms in the supplementary material.
Scoring via Ky Fan matrix multiplicative weights. To obtain the main result of this paper, it remains to show how we can improve the number of iterations of SIFT to polylogarithmic. For this, we turn to a strategy originating in [DHL19] in the large-α regime, which is to use the matrix multiplicative weights regret minimization framework to define weights for stronger performance guarantees. The intuition is that by using scores defined by more than the top eigenvector of the current covariance matrix (or in this paper, the top k eigenvectors), we capture more than one bad point at a time and obtain better worst-case iteration bounds. The main MMW regret guarantee makes this formal. Roughly, it says that if in each iteration we can downweight the current covariance so that its inner product with a matrix given by the MMW framework is small, then in O(log d) iterations we can halve the operator norm (the maximal inner product against all trace-1 nonnegative matrices). A key technical contribution of this paper is to give a Ky Fan k-norm (sum of k largest eigenvalues) generalization of MMW, which typically gives operator norm guarantees. We analyze our algorithm and show that it is tolerant to the error guarantees of approximate k-PCA procedures such as simultaneous power iteration [MM15]. Crucial to our tightest runtime bounds are strengthenings of the analysis of a similar procedure found in [CMY20] in several places, which save multiple k factors in our guarantees and may be of independent interest; we now highlight a few here.6
The main idea of our Ky Fan MMW regret guarantee is to bound the cost of actions {Yt}t≥0 against a sequence of positive semidefinite “gain matrices” {Gt}t≥0 as measured by inner products. The actions {Yt}t≥0 are given by the algorithm (depending on the gain matrices), and live in
Y := {Y ∈ Rd×d | 0 Y I,Tr(Y) = k}.
The reason for this choice of action set, the “k-Fantope,” is because it satisfies supU∈Y 〈U,G〉 = ‖G‖k, so the best action over Y in hindsight captures this norm. Ultimately, our re-weighting scheme requires matrix-vector query access to each Yt, which are defined by Bregman projections onto the set Y . It was shown in [CMY20] that the natural choice of projection, induced by a regularizer r(Y) chosen to be matrix entropy, is a truncated exponential, where truncation occurs on the top-k eigenspace. The bottleneck cost is computing this space, which normally requires an eigendecomposition. To this end, we show new guarantees on the performance of approximate k-PCA, which allow for their use in this process. In particular, we prove the following new (informal) fact; a more formal statement is in the supplementary material. Proposition 3 (Informal, see Proposition 7 of the supplementary material). Let P = VV> where V ∈ Rd×k is the result of Õ( −1) iterations of simultaneous power iteration (approximate top-k eigenvectors) on S ∈ Sd≥0. Then with high probability,
(1− )S PSP + (I−P) S (I−P) (1 + )S.
This improves a similar analysis in [CMY20], which showed an approximation factor of 1± k . The other technical piece required by our MMW algorithm is the following refined divergence bound. Proposition 4 (Informal, see Lemma 13 of the supplementary material). Let r(Y) = 〈Y, log Y〉 be the matrix entropy function defined on Y , let r∗ be its convex conjugate over Sd, and let V r∗A (B) := f(B)−f(A)−〈∇f(A),B−A〉 be the induced Bregman divergence. Then for all S ∈ Sd, G ∈ Sd≥0 and η > 0 satisfying ‖ηG‖op ≤ 1 2 ,
V r ∗ S (S + ηG) ≤ 〈ηG,Y〉 , where Y := ∇r∗(S) ∈ Y.
This is a strengthening of a much more straightforward bound of k ‖ηG‖op, which follows easily from strong convexity of r in the trace norm (and hence smoothness of its dual).7 We require this strengthening so that we can use the action matrices {Yt}t≥0 to define scores, to decrease inner products: the weaker bound above has no dependence on Y, so without the stronger bound it is unclear how to use the MMW update structure to downweight. A similar refined regret bound as Proposition 3 is derived in [Nes07], in the special case when k = 1 (and Y ⊂ Sd≥0 is trace-1 matrices).
6We believe that similar wins following from our tighter analysis apply to [CMY20], and brings their overall runtime down to roughly Õ(ndk4). We give a discussion of their k dependence in the supplementary material.
7It is a strengthening since ∇r∗(S) ∈ Y , so we can apply a matrix Hölder’s inequality and use Tr(Y) = k, ∀Y ∈ Y .
We prove our refined divergence bound by adapting arguments from previous literature [CDST19, JLL+20] on using Hessian formulae of spectral functions to prove divergence bounds, whenever the conjugate r∗ is twice-differentiable, and applying the Alexandrov theorem. Finally, up to (nondominant) approximation error terms, our Ky Fan MMW procedure’s main guarantee can be stated as: given a sequence of positive semidefinite matrices {Gt}t≥0, let step size η > 0 satisfy ηGt I for all t. The procedure plays a sequence {Yt}t≥0 ∈ Y , so that for any T ∈ N,∥∥∥∥∥ 1T T−1∑ t=0 Gt ∥∥∥∥∥ k ≤ 2 T T−1∑ t=0 〈Gt,Yt〉+ k log d ηT . (2)
Win-win-win analysis of MMW: FastSIFT. We now describe how to use the regret guarantee (2) to obtain a faster algorithm. In particular, when the sequence {Gt}t≥0 is monotonically nonincreasing, we can choose η = ‖G0‖−1op to meet all the boundedness conditions ηGt I. If we can guarantee that every 〈Gt,Yt〉 is bounded by, say, 15 ‖G0‖k, and k ‖G0‖op ≤ 2 ‖G0‖k (i.e. the top k eigenvalues of G0 are roughly uniform), the above regret guarantee becomes
‖GT ‖k ≤ ∥∥∥∥∥ 1T T−1∑ t=0 Gt ∥∥∥∥∥ k ≤ 2 5 ‖G0‖k + 2 ‖G0‖k log d T .
Now, T = O(log d) iterations suffice to halve the Ky Fan-k norm. Our strategy, following [DHL19], is to let Gt be the empirical covariance matrix with respect to wt, for monotonically decreasing weight sequence {wt}t≥0 formed by safe weight removals (1). This suggests that if we can implement this strategy, we will reach the termination condition of SIFT in polylogarithmically many iterations of MMW (since an upper bound on the Ky Fan norm of the empirical covariance also implies a bound on the kth largest eigenvalue). At this point, a few questions remain.
1. How do we define the sequence {Gt}t≥0 so that it is monotonically decreasing? For instance, our safety condition (Definition 3) is defined with respect to normalized scores, but normalizing the covariance matrices makes them no longer (necessarily) monotone.
2. How do we whiten the scores so that any one of the top k eigenvalues does not dominate? This requirement arises in several places in the analysis (akin to in the analysis of SIFT), for example in our earlier assumption that k ‖G0‖op ≤ 2 ‖G0‖k. We note that using a trick similar to normalizing the top-k eigenspace to be the identity, as in SIFT, is not effective here as these spaces may be incompatible, and break monotonicity of gain matrices.
3. How do we safely downweight the covariances to make them satisfy 〈Gt,Yt〉 ≤ 15 ‖G0‖k?
We show that a careful analysis of each failure case leads to a different “win condition” in the algorithm, which lets us certify progress in a different way.
1. We restart the algorithm in phases where the `1 norm of the weights halves, so that in each phase the normalizing constant is stable. There can only be logarithmically many phases.
2. We restart the algorithm whenever the kth largest eigenvalue of the covariance matrix is smaller than half the largest, setting aside the k eigendirections. The remainder of the algorithm works in the space orthogonal to these directions. Since each time we set aside k directions we halve the operator norm on the remaining subspace, this only occurs logarithmically many times, and yields a “set-aside subspace” of dimension Õ(k).
3. Whenever Θ(log d) iterations pass without meeting either of the above “exit criteria,” we use binary searches to safely remove as much weight as possible so each covariance matrix Gt meets the inner product criteria through Yt to progress, i.e. we use weight removal to bound the right hand side of the regret guarantee (2). This argument follows the safety analysis of SIFT closely, crucially using that the top k eigenvalues are roughly uniform.
By carefully reasoning about when each of the above three cases occurs, we eventually conclude that we are able to return in polylogarithmically many iterations a pair (B, w) such that B is an orthonormal basis of a subspace of dimension roughly k log d, and w is some weight vector whose empirical covariance’s projection into B⊥ has bounded operator norm. At this point, we can use the empirical mean in B⊥ to learn the mean in all but k log d dimensions. To learn the mean in B, there are a number of much simpler strategies such as random sampling from the dataset, which we discuss when describing ListDecodableMeanEstimation in the sequel.
Preprocessing and postprocessing. The above argument assumed that we initially had a bounded dataset diameter. We show a simple equivalence class partitioning, PreProcess, based on onedimensional projections efficiently produces clusters with polynomially bounded diameter, so that the entire good dataset lies in the same partition (with high probability), yielding the following claim. Lemma 6 (Informal, see Lemma 12 of the supplementary material). There is an algorithm running in time O(nd+ n log n) that partitions T into disjoint clusters with radius poly(n, δ−1) so that all of S is in the same cluster with probability ≥ 1− δ.
Furthermore, we give a greedy clustering step PostProcess which works in a low-dimensional subspace, reducing the size of a candidate list to the optimal O(k) (removing extraneous logarithmic factors), while only affecting the error guarantee by a constant. The statement of PostProcess depends on the specific guarantees of SIFT and FastSIFT (i.e. the decomposition into a Θ( 1α )-dimensional subspace and its complement), so we defer it to the supplementary material for brevity.
Putting it all together: ListDecodableMeanEstimation. Applying PreProcess and FastSIFT sequentially yields a Õ(ndα )-time algorithm which learns a subspace of dimension Õ(k) spanned by B, where the empirical mean in B⊥ is an estimate attaining the information-theoretic limit. It remains to produce a list which learns the mean inside B. At this stage, we employ two strategies: we can either randomly sample, as in the last line of SIFT, or we can simply run SIFT itself with a smaller dataset size on the subspace. Applying PostProcess to the output lists of these two strategies yield our full algorithms, whose guarantees are respectively summarized in the last two rows of Table 1.

heading: Acknowledgments and Disclosure of Funding
text: We thank Morris Yau for clarifying conversations about the prior work [CMY20]. Ilias Diakonikolas is supported by NSF Award CCF-1652862 (CAREER), a Sloan Research Fellowship, and a DARPA Learning with Less Labels (LwLL) grant. Daniel Kane is supported by NSF CAREER Award ID 1553288 and a Sloan fellowship. Kevin Tian is supported by NSF CAREER Award CCF-1844855 and NSF Grant CCF-1955039.

heading: Checklist
text: 1. For all authors... (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s
contributions and scope? [Yes] (b) Did you describe the limitations of your work? [Yes] We describe limitations in the
sense that we clearly state all statistical assumptions required by our algorithms and the distributional models that our algorithms work under.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work does not present any direct foreseeable societal consequence, as it is a result primarily of theoretical interest to the community. Moreover, because our results concern robustness of models to arbitrarily corrupted data, we believe our methods may have practical implications for downstream tasks where protection against a malicious adversary is warranted.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [Yes] (b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either in the supplemental material or as a URL)? [N/A] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they
were chosen)? [N/A] (c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [N/A] (d) Did you include the total amount of compute and the type of resources used (e.g., type
of GPUs, internal cluster, or cloud provider)? [N/A] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] (b) Did you mention the license of the assets? [N/A] (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects... (a) Did you include the full text of instructions given to participants and screenshots, if
applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount
spent on participant compensation? [N/A]

Review summaries:
This article is abound list-decodable learning in which we consider the mean estimation problem when more than half of the data are corrupted data. In this framework, the mean cannot be recovered exactly but one can obtain a list of $k$ potential mean and say that the mean of the inliers is among these $k$ values. This article exhibit an algorithm that attain optimal statistical bounds (up to log factors) in a linear running time (linear in the sample size but also the dimension and in $k$).