List-Decodable Mean Estimation in Nearly-PCA Time
Authors: Ilias Diakonikolas
Daniel Kane
Daniel Kongsgaard
Jerry Li
Kevin Tian
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: robust statistics
learning theory
mixture models
semidefinite programming
list-decodable learning

Abstract: Robust statistics has traditionally focused on designing estimators tolerant to a minority of contaminated data. {\em List-decodable learning}~\cite{CharikarSV17} studies the more challenging regime where only a minority $\tfrac 1 k$ fraction of the dataset, $k \geq 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 {\em nearly-PCA time}. Assuming the ground truth distribution on $\mathbb{R}^d$ has identity-bounded covariance, our algorithm outputs $O(k)$ candidate means, one of which is within distance $O(\sqrt{k\log k})$ from the truth. 
  
 Our algorithm runs in time $\widetilde{O}(ndk)$, 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 $\widetilde{O}(n^2 d k^2)$~\cite{DiakonikolasKK20}, and $\widetilde{O}(nd k^C)$ \cite{CherapanamjeriMY20} for an unspecified constant $C \geq 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.

List-Decodable Mean Estimation in Nearly-PCA Time
Ilias Diakonikolas
Daniel M. Kane
Department of Computer Science University of Wisconsin, Madison
Department of Computer Science University of California, San Diego La Jolla, CA 92093 dakane@cs. ucsd. edu
Madison, WI 53706 iliasecs. wwwc.ediii..
Daniel Kongsgaard
Jerry Microsoft Research Redmond, WA 98052
Department of Mathematics
University of California, San Diego
La Jolla, CA 92093 dkongsga@ucsd.co edu
j jerr1@mi crosoft. com
Kevin Tian
Department of Computer Science
Stanford University Stanford, CA 94305
kjtian@stanford.. edu
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 fraction the dataset, k 2 2, drawn from the distribution of interest, and assumptions made the remaining data. We study the fundamental task of list-dccodable mean estimation in high dimensions. Our main result is 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 Rd has identity-bounded covariance, our algorithm outputs (A) candidate means, one which is within distance O OlVilog k) from the truth.
Our algorithm runs in time Ö(dkk) where is the dataset size. This run- time nearly matches the cost of performing k-PCA on the data, a natural bot- tleneck of known algorithms for (very) special cases of our problem, such as clustering well- well-separated mixtures. Prior to our work, the fastest runtimes were Ón dl:)) [DK220] and (ndkk") [CMY20) for an unspecified constant C 2 6. Our approach builds novel soft downweighting method we term SIFT, guably the simplest known polynomial-time mean estimator in the list-decodable setting. To develop fast algorithms, boost the computational cost of SIFT via a careful "win-win-winn analysis of an approximate Ky Fan matrix multiplicative weights procedure 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 n and the failure probability.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Introduction
Mcan estimation has emerged as one of the comeestone tasks in robust statistics, as the most basic in hicrarchy of increasingly complex estimation problems. The problem is straightforward to state: given samples from "nice" ground-truth distribution D, where an adversary has (arbitrarily) corrupted 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] [Tk660] 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] 1KK+ 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 3.. For the standard formulation of robust mean estimation, this assumption is necessary. Indeed, if only a S fraction of points can be trusted, the dataset could consist of O ( well-separated clusters of "good" points. The mean of each individual cluster an equally valid solution to the estimation problem, so asking for a single solution is ill- -oo-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 S 1 regime, [CSV17] proposed relaxed learning notion termed list-decodable learning. Rather than restricting to a single hypothesis, the algorithm may output list of ( hypotheses, guaranteeing least one of them is close the truth. In the context of robust mean estimation, this amounts to outputting O candidate means.
A natural problem in its own right, list-decodable mean estimation also generalizes 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 HLI8 DKS18 KSST8) In this problem, data is drawn from a uniform mixture of k "nice" distributions Di:-.., DR with far apart means, and the goal is to recover clusters coming from each component. By running a list-decodable estimation procedure with a E. 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-unife non-uniformity, up to constants in the output size.
Moreover, list-decodable mean estimation can be used model important data science applications such as crowdsourcing (where a majority of respondents could be unreliable or malicious) [SVCI6 MV18), or semi-random community detection stochastic block models [CSV17). This primitive is particularly useful in the context of semi-verified learning [CSV17 MV18, where learner can audit small amount of trusted data. Even if the trusted dataset is too small 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 a 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 Σ < I for some known (i.e. a second moment bound). In this setting, (CSV17) gave a sample-optimal, polynomial-time algorithm outputting ( candidate means, so some candidate is within &g distance O(aVa-1 log 11) from the mean of D. As later demonstrated in (DKST&) 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 decodaae mean estimation which achieve optimal statistical guarantees. This goal fits broadly into a larger line of work focused 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 CDGWI9 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--iiltering [DKS18 DKK20J, based on learning multiple candidate "weight functions." " In particular, (DKK20) uses this approach to design an algorithm achieving near-optimal error in time Ö(n2 da 2), where n is the overall dataset size. While this dramatically improves over the runtime
Some algorithms extend beyond the uniform setting: we present it this way for simplicity of exposition.

---

in [CSVI7], the quadratic dependence on n is not ideal in high- sigh--imnnsionll settings. Concurrently, the work [CMY20] proposes different, descent-based based algorithm based on (approximate) positive semidefinite programming, achieving optimal error (up to constant factors) in time O(nda -9) for some constant C 2 6. When
(1), the [CMY20] runtime is nearly- Marly-llinerr in the problem input size. However, if a 1 scales polynomially with d. e.g. a mixture model with many components in moderate dimension, then this large dependence on a 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 mixture well- separated components is almost twenty years old [VW04], and runs in time (ndkk), 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 efficiently as learning mixture models?
Concretely, since clustering mixture models is instance of list-decodable learning with k-1, the question becomes: can we solve list-decodable mean estimation in time Ö and )? This presents itself as a natural barrier, since further improvement would imply faster learning of mixture models.
a
2
Our results
Our main contribution is to answer this question affirmatively with near- cear-optimal statistical guarantees. We start by formally defining the problem we study, which we call "list- decodaece mean estimation."
Definition 1. Given T C Rdd and 0 < or such that an a-fraaction of T are independent draws from a distribution D with unknown target mean μ² and unknown covariance Σ I I²L, output small list of vectors {م hiet such that minjet. [| p=' 1= is minimized.
We emphasize that no assumptions are made on the remaining 1 - ar 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 [ our main result states that we can solve list-decodable mean estimation nearly- optimally in the time it takes to perform A-PCA noly-togarthhmically many times, for k = =
Theorem (See Corollary 3 of the supplementary material). Given [T| = n = 2( samples, there is an algorithm with runtime Ô pdd that with high probability outputs a list of m vectors {uy)
for m = ( such that minje[m] I| p = O(aa à Vloga=
A few remarks are in order. First, list size of ((2), sample complexity of ((g). and error of Q(aaa 1) are anformation-theoreiicnn an algorithm in the supplementary material returning m ((2) hypotheses {uy}semi attaining optimal error minje(m) ||,² M1il2 = ()ra=)), with an additive runtime overhead of ((a-)). Without loss of generality a = o(d), as otherwise there is trivial algorithm (cf. Appendix A of the supplementary material), so the additive term is only dominant in the range a- [w( dd) odd) assuming n Ø( Even with this overhead, our runtime is the best-known in all parameter regimes.
necessary for this problem DKS18). We also provide
Our approach is inspired by the way in which fast algorithms for robust mean estimation in the a 1 regime were built. First, a "simple" polynomial (but not nearly-linear) time algorithm - namely, the filter- was developed [DKK + 19 DKK* 17 Ite18]. 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 a < 1 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)
After the initial dissemination of this work, we were made aware there is another (unrelated) algorithm named SIFT developed in the computer vision community [Lw99]]
3

---

Reference
Runtime
Error guarantee
CSV17
ply(n,d,a")
d,
O(aa Vloga
DKK20
Ō(n2da-2)
O(Ea loga"')
CMY20
Ö(nd(ar 2220)
Our work
O(nda
O Vloga=t)
Our work Õ(nda + 6
O
Table I: List-decodable mean estimation algorithm runtimes. All algorithms listed return lists of size ) and use sample complexity n O which are nnormation-thcorttiic optimal [DKST8]
The O notation hides polylogarithmic factors in failure probability and dimension.
achieving optimal statistical guarantees in time ) 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 "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 ((ndk), the algorithm requires ((n) iterations in the worst case, 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 polylogarilhmically many iterations. To achieve this, we use tools from semidefinite programming (SDP) to design iterative schemes with stronger termination guarantees. This mirrors, and inspired by. the - regime. where tools such as packing SDP solvers [CDG19] and matrix multiplicative weights [DHLI9] were used speed up the basic filter. We note that [CMY20] also uses SDP tools obtain their runtime. but in substantially different way: they design 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.
3 Preliminaries
General notation. We let (H, Σ) denote the multivariate Gaussian distribution with specified mean and covariance, and [d] denote the naturals S j S d. When applied to a vector argument, IlIlpp is the Ep norm. We denote the (solid) probability simplex in dimensions by A {w R25 ||w|| S 1]. The all-ones vector in appropriate dimension is 1. The identity matrix in appropriate dimension I. We the standard Loewner order < the set of symmetric matrices gd = Rddx with positive semidefinite subset 22- For l E [d]. the operation (x(+) on Sd returns the 1t largest eigenvalue.
When applied to matrix in ag. I1-ll, for & [d] is the Ky Fan norm (sum of the top &s eigenvalues), and ||- II- in particular is the Ky Fan norm. The inner product on Sd x Sd is (A, Tr (AB).
Distributions. Let T' be set of points in Id with |T] n, and let w E A For any T' C T, WT, E A" is the vector which equals w on coordinates in 7", and is zero elsewhere. We refer to the empirical mean and covariance, parameterized by weights w and subset T C CT,by by
Pno (T)
Σ SET
Wc W 1
X,, Cov (T') =
Σ T
Wi
(X, - Mm - (T')) (X: - (T)
|WTr l|1
We denote uniform samples from set S by the notation i~ S.

---

Deterministic assumption. In the fist-decodable mean estimation problem. we are given set T of Without loss, we assume o which generalizes n points (eT in R under Definition Regarding the sample size n, we recall the following appropriately by scaling the dataset by o (note that the matrix in Assumption [ is not the covariance, as it is centered at the true mean).
Proposition 1 (Proposition B.I, [CSVI7). For any constant E (0, 1), there are constants c, C>> 0 such that with probability at least 1 exp(-9(n)), for Cdl if an (1 + +)) fraction of points in {Xiher S R is drawn from D with covariance bounded by cI, then Assumption 1 holds.
Assumption 1. 3S S {X.)ter C TRd of size om (cd) with E,-s((X, - -1" (X, 1² 1²) II
In the remainder of the paper, we operate under Assumption T i.e. that there is a subset S of the dataset whose centered covariance around je" is identity- -bounde. Proposition I immplis that this assumption holds for any failure probability larger than definitions); for any smaller failure probability, Proposition implies that the assumption still holds by adjusting the sample size by a logarithmic factor. We also assume 1/ S d for simplicity, and handle the regime_ a (d()) with a much simpler algorithm in Appendix A of the supplemental material.
(up to constants in parameter
Finally, k will be reserved for values which are 2 for explicitly stated constants. In particular, our algorithms will use operations such as principal components analysis in ( dimensions. This is because a substantial portion of the challenge is reducing to the problem of learning the mean in O dimensions, at which point naive random sampling suffices (up to logarithmic factors).
a
Organization. In this shortened version of our paper, give a full statement and analysis of our "slow algorithm" SIFT in Section | achieving optimal sample complexity and error, at a logarithmic overhead in list size and an (nn) 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 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 ( 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 (Saturated weights). We call w E A "saturated" if S 1 and I|wlll 2 a | Definition 3 (Safe scores). We call scores {Ti)iET E 12/0 "safe with respect to E An" if EiEs Twssl T4 S 1/2 Σier |w|, T.. When w is clear from context, we simply call 7 "safe".
In algorithms based on soft filtering in the presence of small amount of adversarial noise (e.g. [DKK117 Li18, 18)) 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 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.
Let weights be saturated. Then w' is also saturated, where w' is the result of the following update: let (Tiheer be safe with respect to w, and update for all E T:
Lemma 1.
-1--7
To Ws, where Tmax ==
w/ +
max Tí. 1
(I)
Tiax
We next give three helper lemmas which reason about how the quality of empirical estimates based on deteriorate, as weight allocated to S reduced. The first shows how the quality of the empirical mean relates to the empirical covariance and proportion of weight in S.
Abusing notation, let I' denote both the point set and indices, interchangeably using X E T and i E T.
5

---

Lemma 2. I E A has w S 1 a entrywise, (I - 10 S V2
+ 2ex
wwslli"
||ril
The second shows how the empirical covariance of S grows relative to how much S is kept. Lemma 3. Let w E A" have w S 1 entrywise. Then Cov =
a
The third shows how a bound on the saturation of a weight vector can be used to bound the distance between empirical means in S and 7 via the weighted empirical covariance matrix.
Lemma 4. (m (S) Mw (T)) (m (S)
(T)) T = Tesl Cov (T).
|||||
We now present SIFT as Algorithm | 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 ó E (0, 1) and [d], there is algorithm, Power, which takes input k, 8, A E 8 and E (0, 1), and returns with probability 1 ó set of orthonormal vectors V gaak such that if Va is column of V.
(V., E [1 +e)A, for all E [b), [|(I-VVT) A VVT)
(A).
When A is given in the form M for some M E Raad the runtime of Power is O pdl log 4
Algorithm SIFT(T,8)
1: Input: T C R with [T'] satistying Assumption |
ô (0,
2: () - 1T. + 0, 3 4 1, k
3: V Power(Cov wr)e) (T), 0.2,
2n
4: while (v Cov (9 (T) 2
do
v
5: T/
Σ
v (X: - Mu (T)
||
for all i ET
2
6:
wi
(++1)
1
[t)
(1)
w
(t)
for all i E T. where (1) max
(ef (0 #0 T
Timax
7:
t t+ 1.
||0(()]
8: V Power(Cor wiee: (T', 0.2., )
9:
end while
10: return L:= (VV T X; + [--VV] Me (T) where i E T is sampled uniformly at random).
with list size [L| = log 2
As Lines 4 through 9 of Algorithm I constitute a weight removal method of the form given in (T. we now demonstrate the scores used are safe, which implies that w(() is always saturated.
Lemma 5. In each iteration of Algorithm !
until termination, r(+) is safe with respect to w(!)
Proof. Throughout this proof, let ((()) and (1)) Furthermore, let V, f correspond the weights (tt, and let Σ = V Cov (T)V. We first compute the average score in S:
Wa
W/
Σ LT (X: Mwe (T))
wwsl
|ws ||
RES
ieS
[| (x, Mr (S))
- DVViVT (S) Mho (To
|wsll1
E VTCovi +
E V (Mw
Mw (T)) 2
||ll 1 (VBL, Iwsl
v3
B1,
< 2
v3
a
The first three equalities expanded definitions; the first inequality is by LemmasBaand The second inequality used Definition 2
twice, which implies that ||ws|| > a well as the exit condition in

---

Line 4. The third inequality follows from the definition of k. Finally, we conclude that 7 is safe, by
Wi
Σ
V
(X; - (mo
EET
Σー
V
Wi
(X; - Hhw (w) (X:- -xur)))))))))))))))
= =x Σ) k.
NET
Theorem 2. Under Assumption
1
with probability 8, the output of Algorithm 7 satisfies
minpez L ||
1 n011 22, The overall runtime of Algorithm 7 is O (ni- log (*)
Proof. Runtime. There are at most n iterations in Algorithm since at least one weight is zeroed out in each iteration. Further, the bottleneck operation in each iteration is Power, since eigende- composition of takes time (1:3) = (nddk). Since is a constant in Proposition 2 this yields the runtime. We note that the algorithm must terminate before removing all the weight: since is saturated, |w|], 2 a² via Definition and ||w|| 2 ||w/||i ll. By union bound, with probability 1- 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 the algorithm (after exiting Line 10). Denote = VV and : PX; for all T. Since
1 Σ - Py Pa-)= = P iES
Σ iES
1 (x, - -x) x2) P P
on
by Assumption the expectation of || - - for uniformly random sample S is 4 by linearity of trace. By Markov, with probability 2 a sample from S has ||; Pu S a. with
a
probability 5. some element of L uses an X; with I| PH s &. For this i, we expand
PP. + (I- pa pm n" = Y Pμ + I| P) -
[I P) (M 11") )1²)
To bound this second term, we apply Lemma 2 on the set of points {(I P)Xiher This implies
23 |ws||
2a
12vB [wslli
2a
14
(I P) (T) p0)
,ll-, (T)(I P)llop (P))l +
<
< a
3
Here, the last inequality used that saturation implies 326 a². The second used that Power and the termination condition imply that, since eigenvalues of Σ are the same as VV (TVV
6
(II ( (T) (I (I-P)) P) 1.22& (T)) S 1.5A, <
/B
While Theorem 2 Jaciievss the desired error, it has a quadratic dependence on the sample size and a suboptimal list size by a factor of (log }). We address both issues with our fast algorithm.
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 Ky Fan variant of matrix multiplicative weights (MMW) regret minimization framework we develop, to give our final algorithm. Throughout this overview, we define integer linear subspace; constants will be specified in relevant algorithms in the supplementary material.
= ) to represent some dimensionality
7

---

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 strategy originating in [HI.19] in the large-a 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 time and obtain better worst-case iteration bounds. The main MMW regret guarantee makes this formal. Roughly, it says that 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 (log d) iterations we can halve the operator norm (the maximal inner product against all trace-1 nonnegative matrices).
key technical contribution of this paper to give a Ky Fan k-norm (sum of 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 factors in guarantees and may be of independent interest; now highlight few here [
The main idea of our Ky Fan MMW regret guarantee is to bound the cost of actions (Y (Y)r20 against sequence of positive semidefinite "gain matrices" {G+ h20 as measured by inner products. The actions t220 are given by the algorithm (depending on the gain matrices), and live in
y = (Y E Rddd
03 Y Ir()) kj-
The reason for this choice of action set, the "k-Fantoppe," is because it satisfies supuey (U, = [|G|| so the best action over }' in hindsight captures this norm. Ultimately, our re-weighting scheme requires matrix-vector query access to each Y,. which are defined by Bregman projections onto the set V. It was shown in [CMY20) that the natural choice of projection, induced by 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 approximate k-PCA, which allow for their use in this process. In particular, we prove the following new (informal) fact; more formal statement is in the supplementary material.
Proposition 3 (Informal, see Proposition of the supplementary material). Let P VVT where V Raak is the result of ((-1)) iterations of simultaneous power iteration (approximate top-k eigenvectors) on S 200 Then with high probability,
(1- PSP + (I P)S-P) = (1+e)S.
This improves a similar analysis in [CM220) which showed an approximation factor of 1 + kc. The other technical piece required by our MMW algorithm 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 V, let r" be its conver conjugate over $4, and let VĀ (B) = f(B - (V B A) be the induced Bregman divergence. Then for all S Sd, G Sd and 1) > 0 satisfying || ll.pp < 2
ViS (S + G) & (nG, Y), where Y == Vr*(S) E V.
This is a strengthening of much more straightforward bound of l ||n which follows easily from strong convexity of in the trace norm (and hence smoothness of its dual) We require this strengthening so that we can use the action matrices {Y,) hizo 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 [Ns007] in the special case when k (and y C $ is trace-1 matrices).
'We believe that similar wins following from our tighter analysis apply to [CMY20), and brings their overall runtime down to roughly Ö(ndk*)). give discussion their dependence the supplementary material.
'I is strengthening since Vr (S") E V. so we can apply matrix Hölder's inequality and use Tr(Y) k.
VY y.
8

---

We prove our refined divergence bound by adapting arguments from previous literature [CDST19 [ on using Hessian formulae of spectral functions to prove divergence bounds. whenever the conjugate r' is twice-differentaable, and applying the Alexandrov theorem. Finally, up to (non- dominant) approximation error terms, our Ky Fan MMW procedure's main guarantee can be stated as: given sequence of positive semidefinite matrices (Gr let step size 1j > O satisfy r/G, = I for all t. The procedure plays a sequence (Yt)o20 E V so that for any T E N.
T-1 T
T-1
koog T/
T
G 1=0
G.. Y.)
(2)
1=0
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 {Gr h20 is monotonically non-
increasing, we can choose 17 |Gollap to meet all the boundedness conditions 1/G, 3 I. If we can
1 ||Golla. and |Gollop S 2 2|ooll, (i.e. the top guarantee that every (G,, Y,) bounded by, say, 5
eigenvalues of Gu are roughly uniform), the above regret guarantee becomes
2|GGoll logd
|GTll < T Σ G.
5 |Goll +
T
Now, T = (log d) iterations suffice to halve the Ky Fan-k norm. Our strategy, following [DHL19] to let G2 be the empirical covariance matrix with respect to Wt, for monotonically decreasing weight sequence {we he2 formed by safe weight removals (T). This suggests that if we can implement this strategy, we will reach the termination condition of SIFT in polylogarithmiaaly many iterations of MMW (since an upper bound on the Ky Fan norm of the empirical covariance also implies a bound on the ht largest eigenvalue). At this point, a few questions remain.
1. How do we define the sequence (G+ 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 & 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 & |Gollop S 2 2 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 (G,, Y.) S ||Golla?
We show that 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 &, norm of the weights halves, so that each phase the normalizing constant is stable. There can only be logarithmically many phases.
2. We restart the algorithm whenever the 4th largest eigenvalue of the covariance matrix is smaller than half the largest, setting aside the k cigendirections. The remainder of the algorithm works in the space orthogonal to these directions. Since each time we set aside & directions we halve the operator norm on the remaining subspace, this only occurs logarithmically many times, and yields "set-aside subspace" of dimension Ö(k).
3. Whenever O(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 G, meets the inner product criteria through Y, 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 & 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 polylogarithmicalyy many iterations a pair (B, w) such that B is an orthonormal basis of a subspace of dimension roughly & 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 le 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 ListDecodableMeenEESiii
in the sequel.

---

Preprocessing and postprocessing. The above argument assumed that we initially had a bounded dataset diameter. We show simple equivalence class partitioning, PreProcess, based on one- dimensional 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 algorithm running in time O + n log n) that partitions T into disjoint clusters with radius poly(n, 6²)) so that all of S in the same cluster with probability 2 8.
Furthermore, we give greedy clustering step PostProcess which works in 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 O () subspace and its complement), so we defer it to the supplementary material for brevity.
Applying PreProcess and FastSIFT se- quentially yields a Ō nd o >-time algorithm which learns subspace dimension ((k) spanned by B, where the empirical mean in B is an estimate attaining the information-thcortti limit. It remains to produce a list which learns the mean inside 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
Putting all together: listDecodallMeeeESiimaaiioo
Acknowledgments and Disclosure of Funding
We thank Morris Yau for clarifying conversations about the prior work (CMY20). Taaas Diakonikolas supported by NSF Award CCF-1652862 (CAREER), Sloan Research Fellowship, and DARPA Learning with Less Labels (LwLL) grant. Daniel Kane is supported by NSF CAREER Award ID 1553288 and Sloan fellowship. Kevin Tian is supported by NSF CAREER Award CCF- 184455 and NSF Grant CCF-1955039.
10

---

References
[AK05] Sanjeev Arora and Ravi Kannan. Learning mixtures of separated nonspherical gaussians. The Annals of Applied Probability, 15(1A):69 92, 2005.
[AM05] Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distribu- tions. In International Conference on Computational Learning Theory, pages 458 469. Springer, 2005.
[Ans60] Frank J Anscombe. Rejection of outliers. Technometrics, 2(2): 123114,, 1960.
[CDG19] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2755-2771. SIAM, 2019.
[CDGW19] Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P Woodruff. Faster algorithms for high-dimensiona robust covariance estimation. In Conference on Learning Theory, pages 727-757, 2019.
[CDST19] Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian. A rank-1 sketch for matrix multiplicative weights. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 589-623, 2019.
[CMY20] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation in nearly linear time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, 2020.
[CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 47-60, 2017
[Das99] Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 634-644. IEEE, 1999.
[DHL19] Yihe Dong, Samuel B. Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC. Canada, pages 2019.
[DKK*17] Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 999-1008, 2017.
[DKK+19] 19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-864, 2019.
[DKK20] Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. List-decodable mean estima- tion via iterative multi-filterigg In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 2020, virtual, 2020.
[DKS17] Ilias Diakonikolas, Daniel Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of nigh-dimmnsional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84. IEEE, 2017.
[DKS18] Ilias Diasonikolas, Daniel M. Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1047-1060, 2018.
11

---

[DS07] Sanjoy Dasgupta and Leonard Schulman. A probabilistic analysis of em for mixtures of separated, spherical gaussians. Journal of Machine Learning Research, 8(Feb):203-226, 2007.
[HL18] Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1021-1034, 2018.
[HL19] Samuel B Hopkins and Jerry Li. How hard is robust mean estimation? In Conference on Learning Theory, pages 1649-1682, 2019.
[Hub64] Peter Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73-101, 1964.
[JKL+20] Haotian Jiang. Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. faster interior point method for semidefinite programming. In 61 IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 910-918, 2020.
[J]L+20] Arun Jambulapati, Yin Tat Lee, Jerry Li, Swati Padmanabhan, and Kevin Tian. Positive semidefinite programming: mixed, parallel, and width- independent. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL. USA, June 22-26, 2020. pages 789-802 2020.
[JLT20] Arun Jambulapati, Jerry Li, and Kevin Tian. Robust sub-gaussian principal component analysis and width- indth-indeeendent schatten packing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual, 2020.
[KSS18] Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035-1046, 2018.
[Li18] Jerry Zheng Li. Principled approaches to robust machine learning and beyond. PhD thesis, Massachusetts Institute of Technology, 2018
[Low99] David G. Lowe. Object recognition from local scale-invariant features. In Proceedings of the International Conference on Computer Vision, Kerkyra, Corfu, Greece, September 20-25, 1999, pages 1150-1157, 1999.
[LRV16] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665-674. IEEE, 2016.
[LY20] Jerry Li and Guanghao Ye. Robust gaussian covariance estimation in nearly-matrix multiplication time. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[MM15] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1396-1404, 2015.
[MV18] Michela Meister and Gregory Valiant. data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory, pages 1530-1546. PMLR, 2018
[Nes07] Yurii Nesterov. Smoothing technique and its applications in semidefiiite optimization. Math. Program., 110(2):245225) 2599, 2007.
[RV17] Oded Regev and Aravindan Vijayaraghavan. On learning mixtures of well-separated gaussians. In 20/7 JEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 85-96. IEEE, 2017.
12

---

[Ste18] Jacob Steinhardt. Robust Learning: Information Theory and Algorithms. PhD thesis, Stanford University, 2018.
[SVC16] Jacob Steinhardt, Gregory Valiant, and Moses Charikar. Avoiding imposters and delin- quents: Adversarial crowdsoureing and peer prediction. In Advances in Neural Informa- tion Processing Systems, pages 4439 4447, 2016.
[Tuk60] John Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pages 448 485, 1960.
[Tuk75] John W. Tukey. Mathematics and the picturing of data. Proceedings of the Inter- national Congress of Mathematicians, Vancouver, 1975, volume 2, pages 523-531, I, 1975.
[VW04] Santosh Vempala and Grant Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-80) 2004.
13

---

Checklist
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 your work? [N/A] This work does not present any direct foreseeable societal consequence, as it is result primarily of theoretical interest to the community. Moreover, because our results concern robustness of models arbitrarily corrupted data, believe our methods may have practical implications for downstream tasks where protection against 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 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 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]
(c) 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, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "wxPrFJHBV8n", "reviewer": "Reviewer_F5h5", "summary": "This paper studies the list-decodable mean estimation problem and proposes an algorithm that runs in nearly $k$-PCA time, which can be seen as a natural barrier to this problem. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies the list-decodable mean estimation problem: that is, if only $\\frac{1}{\\alpha}$-fraction of the data is the good point, we want to output a list of $O(\\frac{1}{\\alpha})$ solutions, one of which is guaranteed to be close to the true mean of the distribution. This problem can be seen as an extended to the outlier robust mean estimation problem and has received significant attention in recent years. \nIn this work, the authors give a new algorithm for the bounded covariance distribution that runs in $\\tilde{O}(\\frac{nd}{\\alpha})$ time, which nearly matches the time to perform $k$-PCA on the data, which can be seen a natural bottleneck of this problem. This result is better than the previous one in [CMY20](FOCS 2020)(runs in time $\\tilde{O}(\\frac{nd}{\\alpha^C})$ where $C \\ge 6$) and only increase the error by logarithmic factor.\n\nThis paper first gives a simple version of the algorithm that runs in $\\tilde{O}(\\frac{n^2 d}{\\alpha})$ but is conceptually new. Then, following the result in [DHL19], the author uses the matrix multiplicative weights regret minimization framework to reduce the runtime to $\\tilde{O}(\\frac{nd}{\\alpha})$. One technical contribution here is to give a Ky Fan k-norm generalization of MMW.\n\nThis paper is technically very strong and the writing is well. The authors provide a lot of intuition for the proofs. This paper is a pure theory paper. However, a set of accompanying experiment results would be also nice.\n\nSome minor questions:\n\n- For the second \"=\" in the equation which starts in line 211, is it should be \"$\\le$\" instead of \"=\"?\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the \"Main Review\".", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8-10"}, "extra_text": {}}, {"review_id": "ctpDq4PUW7A", "reviewer": "Reviewer_1cxi", "summary": "This paper studies the fundamental task of list-decodable mean estimation in high dimensional space. This paper proposes a novel algorithm for bounded covariance distributions with optimal sample complexity and near-optimal error guarantee, running time in nearly-PCA time.\n", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: This paper improved all the previous results (e.g. [Charikar, Steinhardt, Valiant, STOC’17], [Diakonikolas, Kane, Kongsgaard NeurIPS’20], [Cheapanamjeri, Mohanty, Yau\nFOCS’20]) running time. This paper is a truly breakthrough result.\n\nMore impressively, this paper proposed a super fancy technique called Subspace Isotropic FilTering\n(SIFT) . To the best of my knowledge, I have never seen such a thing before, this is completely new. \n\nClearly, this paper should be at least an oral presentation at NeurIPS.\n\nMinor: \n\nIn Reference, [AK+05], should be [AK05], the et al should be removed. This might be a bug of google scholar citation. Clearly, this paper only has two authors.\n\nIn Reference, the [DKK20] conference information is missing. It is a NeurIPS 2020 paper.\n\nIn Reference, the [LY20] conference information is missing. It is a NeurIPS 2020 paper.\n\nIn Reference, the [JLT20] conference information is missing, it is a NeurIPS 2020 paper.\n\nThis paper mentioned SDP in a number of places. Several recent, state-of-art SDP solvers should be cited ``A Faster Interior Point Method for Semidefinite Programming’’ and “Solving Tall Dense SDPs in the Current Matrix Multiplication Time”.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are not mentioned. However, this paper is a super fancy theory paper, in order to make it more practical might take more efforts. Societal impact is not mentioned and since this paper is pure theory, it does not have a direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "QvNuO_OLQ9B", "reviewer": "Reviewer_Zu6e", "summary": "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$). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The article is quite significant because it exhibit a considerable faster algorithm than previous works for the same optimal error guarantees.  The article is clear and the quality of the redaction is ok.\n\nRemark : I would ask the authors to be more mindful of the abbreviations they use. Their are a lot of abbreviations that are not transparent, for instance the notation PCA is never made clear in  the article : what algorithm does it represent exactly ?  Also SIFT is not transparent and in fact there already exist a SIFT algorithm in image processing so this might not be the best choice of name for the algorithm. Similarly the reader also have to remember what is MMW...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The article would greatly benefit from some practical experiments. The theory is stated up to a constant and in practice if the constant in the big O are large, then even though the algorithm is nearly PCA time, it may not be computable. Please provide a proof of concept, even on a corrupted mixture of spherical Gaussian this would already be a good illustration to show that the algorithm work in practice.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a nearly "PCA" time algorithm for the problem of list-decodable mean estimation. There are two relevant parameters in the problem: the underlying dimension d, the number of samples n, and the fraction of inliers \alpha. There's a significant history of works on this problem -- starting with polynomial (but large exponent) running time in both d and 1/\alpha. A significant leap was made in a recent work that gave linear time algorithm in nd but a large polynomial (1/\alpha^5) dependence on \alpha. This paper resolves the issue completely and gives an algorithm with a quasi-linear dependence in nd/\alpha. 

List-decodable mean estimation is a fundamental question in algorithmic robust statistics (it generalizes mean estimation and spherical mixture clustering problems) and finding efficient algorithms for the problem is an important research direction. This paper makes a foundational contribution to this area by giving a nearly optimal algorithm for the problem. While there were concerns of whether the nearly optimal running time in this paper translates into practical gains, the authors' response convincingly clarified that a provably linear time algorithm paves the way for a practically fast one. 

We recommend acceptance. 


Decision: Accept (Spotlight)