A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
Authors: Ilias Diakonikolas
Daniel Kane
Jasper C.H. Lee
Ankit Pensia
Thanasis Pittas
Venue: NeurIPS 2023 spotlight (2023)
Keywords: robust statistics
covariance estimation
list-decodable learning
TL;DR: We give a sum-of-squares-free polynomial time algorithm for list-decodable Gaussian covariance estimation in relative Frobenius norm

Abstract: We study the problem of list-decodable Gaussian covariance estimation. Given a multiset $T$ of $n$ points in $\mathbb{R}^d$ such that an unknown $\alpha<1/2$ fraction of points in $T$ are i.i.d. samples from an unknown Gaussian $\mathcal{N}(\mu, \Sigma)$, the goal is to output a list of $O(1/\alpha)$ hypotheses at least one of which is close to $\Sigma$ in relative Frobenius norm. Our main result is a $\mathrm{poly}(d,1/\alpha)$ sample and time algorithm for this task that guarantees relative Frobenius norm error of $\mathrm{poly}(1/\alpha)$. Importantly, our algorithm relies purely on spectral techniques. As a corollary, we obtain an efficient spectral algorithm for robust partial clustering of Gaussian mixture models (GMMs) --- a key ingredient in the recent work of [BakDJKKV22] on robustly learning arbitrary GMMs. Combined with the other components of [BakDJKKV22], our new method yields the first Sum-of-Squares-free algorithm for robustly learning GMMs, resolving an open problem proposed by Vempala and Kothari. At the technical level, we develop a novel multi-filtering method for list-decodable covariance estimation that may be useful in other settings.

A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
Ilias Diakonikolas University of Aiaconsin-Madisse iliasOcs. wisc.
Daniel M. Kane University of California, San Diego dakane@cs. ucsd. edu
Jasper C.H. Lee University of -aadoonin-Madison jasper. leellieee.edeeee
Ankit Pensia IBM Research anki tp@i bm com
Thanasis Pittas
University of Wisconsin-Madison pittasQwisc.edi
Abstract
We study the problem of list-dccodable Gaussian covariance estimation. Given a multiset T of points in Rd such that unknown < 1/2 fraction of points in T are i.i.d. samples from an unknown Gaussian (j, Σ), the goal is to output a list (11/a) hypotheses least of which is close to Σ in relative Frobenius norm. Our main result is a poly(d, 1/a) sample and time algorithm for this task that guarantees relative Frobenius norm enror of poly(1/a). Importantly, our algorithm relies purely on spectral techniques. As a corollary. we obtain an efficient spectral algorithm for robust partial clustering of Gaussian mixture models (GMMs) key ingredient in the recent work of [BDJKKV22] on robustly learning arbitrary GMMs. Combined with the other components of [BDJKKV22], our new method yields the first Sum-of-Sqqares-ffeee algorithm for robustly learning GMMs, re- solving an open problem proposed by Vempala [Vem22] and Kothari [Kot21], J. At the technical level, we develop a novel multi multi--ilttring method for list-decodable covariance estimation that may be useful other settings.
Introduction
Robust statistics studies the efficient (parameter) learnability of underlying distribution given samples some fraction which might be corrupted, perhaps arbitrarily. While the statistical theory of these problems has been well-established for time [Hub64; HR09], only recently has the al- gorithmic theory of such estimation problems begun to be understood [DKKLMS16, LRV16; DK23J.
A classical problem in robust estimation is that of multivariate robust mean estimation - that is. estimating the mean of an unknown distribution outliers. One of the original results in the field is that given samples from Gaussian N(u, /) with an e-fraction of outliers (for some < 1/2), the unknown mean μ can be efficiently estimated to an error of O(e Vloy 1/c) in the norm BOKKLMSTIN 16). Note that the use of the fz-norm here quite natural, identity-cove edentity-covariance Gaussians is roughly proportional to
the presence of a small constant fraction of
the total variation distance between the fg-distance between their means; thus, this estimator learns the underlying distribution to total variation distance error ( /log 1/e). This bound cannot be substantially improved, as learning to impossible.
error o(e) in total variation distance is iiformation-thoortieeee
While the above algorithmic result works when is small (less than 1/2). if more than half of the samples are corrupted, it becomes impossible to learn with only single returned hypothesis-thh corruption might simply simulate other Gaussians, and no algorithm can identify which Gaussian is the original one. This issue be circumvented using the list-decodable mean estimation
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

paradigm [CSV where the algorithm is allowed to output small list of hypotheses with the guarantee that at least one of them is relatively close to the target. List-decodable learning is closely related to semi-verifted learning [CSV17; MV18), where a learner can choose to audit a small amount of data. The framework has been shown to capture a multitude of applications, including crowdsourcing (SVC16; MV18), semi-random community detection in stochastic block models [CSV17] and clustering (as we also show in this work). For Gaussian mean estimation in particular, if an a-fraction of the samples are clean (i.e., uncorrupted), for some < 1/2, there exist polynomial-time algorithms that return a list of O(1aa) hypotheses such that (with high probability) at least one of them is within Ō TTTTaa of the mean in fz-distance [CSV17]. Note that while this f--nrm distance bound does not imply a good bound on the total variation distance between the true distribution and the learned hypothesis, it does bound their distance away from one, ensuring some non-trivial overlap.
Another important, and arguably more complex, problem in robust statistics (the focus of this work) is that of robustly estimating the covariance of a multivariate Gaussian. It was shown in [DKKLMS16] that given e-corrupted samples from (0, Σ) (for < 1/2) there is a polynomial time algorithm for estimating Σ to error Oc 1/c) in the relative Frobenius norm, i.e., outputting hypothesis covariance Σ satisfying //511/25E1122
/||: S c. This is again the relevant metric, since, if //551//55511/2 |F S 2/3, then the total variation distance between W/0, Σ) and (( Σ) is proportional to the relative Frobenius norm |51122 1/2 I|1F [DMR18).
natural goal, with a number of applications, is to extend the above algorithmic result to the list- decodable setting. That is, one would like a polynomial-time algorithm that given corrupted samples from (O, Σ) (with an a-fraction of clean samples, for some < 1/2), returns a list of O(1/a) many hypotheses with the guarantee that at least one of them has some non non-trivin triviali overlap with the true distribution in total variation distance. We start by noting that the sample complexity of list-decodable covariance estimation is poly(d/a), albeit via an exponential time algorithm. The only known algorithm for dist-deco covariance estimation (with total variation error guarantees) is due to [IK22]. This algorithm essentially relies on the Lum-of-Squares method and has (sample and computational) complexity dPoly(1/a), Intriguingly, there is compelling evidence that this complexity bound cannot be improved. Specifically, [DKS17; DKPPS21] showed that any Statistical Query (SQ) algorithm for this task requires complexity d1oly(1/a), Combined with the reduction of [BBHLT20), this implies a similar lower bound for low-degree polynomial tests. These lower bounds suggest an intrinsic information-compuuatioo gap for the problem.
The aforementioned lower bound results [DKS17: DKPPS21] establish that it is SQ (and low-degree) hard to distinguish between a standard multivariate Gaussian, (0, I), and a distribution P that behaves like (0, I) (in terms of low-degres moments) but P contains an a-fraction of samples from Gaussian (0, Σ), where Σ is very thin in some hidden direction v. Since the distribution (0, Σ) is very thin along v. i... has very small variance, the obvious choice of N I) essentially has no overlap with (O, Σ)- making this kind of strong list-decoding guarantee (closeness in total variation distance) likely computationally intractable.
Interestingly, there are two possible ways that pair of mean zero Gaussians can be sepa- rated [DHKK20; BDHKKK20J: (I) one could be much thinner than the other in some direction, or (2) they could have many orthogonal directions in which their variances differ, adding up to something more substantial. While the lower bounds of [DKS17; DKPPS21] seem to rule out being able to detect deviations of the former type in fully polynomial time (i.e., poly(d/a)), it does not rule out efficiently detecting deviations of the latter. In particular, we could hope to find (in poly(d/a) time) a good hypothesis E such that 15-1/2 -1/2 [||: is not too big. While this does not exclude the possibility that Σ is much thinner than Σ in small number of independent directions, it does rule out the second kind of difference between the two. The main goal of this paper is to provide an elementary (relying only spectral techniques) list-decoding algorithm of this form. Given corrupted samples from a Gaussian (0, Σ), we give a poly(d/ a:) -ime algorithm that returns a small list of hypotheses Σ such that for at least one of them we have that 1/25 1/2 /|]F < (1ly(1/a).
In addition providing the best qualitative guarantee we could hope to achieve in fully polynomial time, the above kind of "weak" list-decoding algorithm has interesting implications for the well- studied problem of robustly learning Gaussian mixture models (GMMs). [BDJKKV22] gave a polynomial-timg time algorithm to robustly learn arbitrary mixtures of Gaussians (with a constant number
2

---

of components). One of the two main ingredients of their approach is subroutine that could perform partial clustering of points into components that satisfy exactly this kind of weak closeness guarantee. (SoS)
(BDJKKV22 developed such subroutine by making essential use of a Sum-of-Squne relaxation, for the setting that the samples come from a mildly corrupted mixture of Gaussians (with a small constant fraction of outliers). As corollary of our techniques, we obtain an elementary spectral algorithm for this partial clustering task (and, as already stated, our results work in the more general list-decoding setting). This yields the first SoS-free algorithm for robustly learning GMMs, answering an open problem in the literature [Vem22; Kot21].
1.1
Our Results
Our main result is a polynomial-time algorithm for list-decoding the covariance of a Gaussian in relative Frobenius norm, under adversarial corruption where more than half the samples could be outliers. Definition 1.1 makes precise the corruption model, and Theorem 1.2 states the guarantees of our main algorithm (Algorithm 1).
Definition 1.1 (Corruption model for list-decoding). Let the parameters e. a E (0, 1/2) and a distribution family D. The statistician specifies the number of samples m. Then set of n 2 am i.idd. points are sampled from an unknown D E DD We call these n samples the inliers. Upon inspecting the inliers, (malicious and computationally unbounded) adversary can replace an arbitrary i S en of the inliers with arbitrary points, and further add m - n arbitrary points to the dataset, before returning the entire set of m points the statistician. The parameter is also known a a-priori to the statistician, but the number n chosen by the adversary is unknown. We refer to this set of m points an (ax corrrupee set of samples from D.
In our context, the notion of list-decoding is as follows: our algorithm will return a polynomially-sized list of matrices HI, such that at least one H; is an "approximate square root" of the true covariance Σ having bounded cimmension--ndependdee
error | 1/2__ - |r. As discussed earlier, the bound we guarantee is poly(1/o)) which is in general larger than 1 and thus does not lead to non-trivial total variation bounds, thus circumventing related SQ lower bounds. Our main theorem is:
Theorem 1.2 (List-Decodable Covariance Estimation in Relative Frobenius Norm). Let C' > be sufficiently large constant und 6o > 0 be a sufficiently small constant. Let the parumeters a E (0, 1/2), e E (0, and failure probability 8 E (0, 1/2) be known to the algorithm. Let D be the Gaussian distribution N (H, Σ) with mean J E TRd and full-rank covariance E E Rddxd There is an ((m²d)) -time algorithm (Algorithm 1) such that, on input ox, 8 and an (ox, e)-coruupted set of m points from D (Definition 1.1) for any m > C² d log (d/a)) with probability least 1 8, the algorithm returns a list of at most ((1/a) many sets T, which are disjoint subsets of samples, each of size at least 0.5cm, and there exists a T, in the oulput list such that:
Recall the notation in the corruption model (Definition 1.1) where n is the size of the original inlier set S and & is the number of points in S that the adversary replaced-n n and are unknown the algorithm except that n. omn and S En. The set T, in the returned list satisfies that [T, n S) 2 (1 0.01a) E).
Denote H; : Ex Ex~r, [X The matrix H, satisfies |H, |H, 1/2 Ill S 2 log(2))
Algorithm 1 is an iterative spectral algorithm, as opposed to involving large convex programs based on the sum-of-squares hierarchy. We state Algorithm and give high-level proof sketch of why it satisfies Theorem 1.2 in Section 3. The formal proof of Theorem 1.2 appears in Appendix F (where we allow Σ to be rank-deficient as well).
We also briefly remark that, we wish to list-decode pairs of (mean, covariance), then we can run the following straightforward augmentation to Algorithm I: after running Algorithm 1, for each E in the output list, whiten the data using Σ and run standard list-decoding algorithm for the mean [CSV17; DKK20b]. These algorithms work if the data is distributed with a bounded covariance: by the guarantees of Theorem 1.2, after whitening, the data has covariance bounded by poly(1/a) I.
As corollary of our main result, the same algorithm (but with a slightly higher sample complexity) also achieves outlier-robust list- list-decoding of the covariances for the components of a Gaussian mixture model, in relative Frobenius norm. Definition 1.3 and Theorem 1.4 state the corresponding corruption model and theoretical guarantees Algorithm 1.
3

---

Definition 1.3 (Corruption model for samples from Gaussian Mixtures), Let c (0, Consider a Gaussian mixture model Ep a. pp), where the parameters Op. Hy and 2 are unknown and satisfy ap 2 a for some known parameter a. The statistician specifies the number of samples m, and m i.idd samples are drawn from the Gaussian mixture, which are called the inliers. The malicious and computationally unbounded adversary then inspects the m inliers and allowed to replace an arbitrary subset of cam many inlier points with arbitrary outlier points, before giving the modified dataset to the statistician. We call this the e-corrupted set of samples.
Theorem 1.4 (Outlier-Robure Clustering and Estimation of Covariances for GMM). Let C' > O be sufficiently large constant and Eo > be a sufficiently small constant. Let the parameters (0, 1/2), Eo). and failure probability 8 E (0, 1/2) be known. There is an Om (mmdd)) ) algorithm such that, on input a, 6, and m >
many e-corrupted samples from an unknown k-component Gaussian mixture _nm1 1pNNpppp pxp over IR.4 as in Definition 1.3, where all Eng 's are full-rank and all Op satisfies (tp 2 and k < is unknown to the algorithm, with probability at least algorithm returns a list of at most i many disjoint subsets of samples {Ti} such that:
aa
over the corrupted samples and the randomness of the algorithm, the
For the nd Gaussian component, denote the set Sp as the samples in the inlier set S that were drawn from component p. Let n.g be the size of Sp. and let lp be the number of points in Sp that the adversary replaced-1y ny and Ep are both unknown to the algorithm except that E[np] apm 2 om for each p and Ep S Eom. Then, for every Gaussian component p in the mixture, there exists a set Tú, in the returned list such that [Ti, SSpl 2 (1 (n, -alpp---p.. -p)-
For every component P. there is a set of samples T. in the returned list such that, defining Hip = =Exws,, [XX] we have Hi,, satisfying ||,,,"" ",,,,,,
I| S (1/a²) log(1/a).
Let E be the (population-level) covariance matrix of the Gaussian mixture. For any two components p + p' with |E-1//(EE, E C(1/a)² log(1/a) for sufficiently large constant C, the sets Tip and Tr from the previous bullet are guaranteed to be different.
The theorem states that, not only does Algorithm achieve list-decoding of the Gaussian component covariances, but it also clusters samples according to separation of covariances in relative Frobenius norm. The recent result of [BDJKKV22] on robustly learning GMMs also involves an algorithmic component for clustering. Their approach is based on the uf--or-quuares hierarchy (and thus requires solving large convex programs) while, Algorithm is a purely spectral algorithm.
We also emphasize that the list size returned by Algorithm 1, in the case of k-component Gaussian mixture model, is at most k- - instead of a weaker result such as O(1/a) or polynomial/exponeniaal large in 1/a. This is possible because Algorithm 1 keeps careful track of samples and makes sure that no more than a 0.01 a-fractio of samples is removed from each component or mis-clustered into another component. We prove Theorem 1.4 in Appendix G.
1.2 Overview of Techniques
At high level, our approach involves integrating robust covariance estimation techniques from [DKKLMM166 with the multifilter for list-decoding of [DKS18]. For a set S, we use SS to denote the set (xxx x E S). [DKKLLMS16] states that in order to estimate the true covariance Σ, it suffices to find a large subset S of points with large overlap with the original set of good points, so that if E' Cov(S) then Cov((E)) 1/2 (E') -1/2) has no large eigenvalues. This will imply E')(E')
that ((EE)-
|| 1/2|| is not too large (Lemma E.2).
As in [DKKLMS16], our basic approach for finding such a set is by the iteratively repeating the following procedure: We hegin by taking S to be the set of all samples and repeatedly check whether or not has a large eigenvalue corresponding to a matrix A (normalized to have unit Frobenius norm), we consider the values of fxx) = (A, (E')-1/22z7 xr (E'" for x in S, and attempt to use them to find outliers. Unfortunately, as the inliers might comprise minority of the sample, the values we get out of this formula might end-up in several reasonably large clusters, any one of which could plausibly contain the true samples; thus, not allowing us declare any particular points to be outliers
-1/2) has any large eigenvalues. If it does not, we are done. If it

---

with any degree of certainty. We resolve this issue by using the multifilter approach of [DKS18] we we either (i) iteratively remove outliers, or (ii) partition the data into clusters and recurse on each cluster. In particular, we note that if there is large variance in the A-direction, one of two things must happen, either: (i) The substantial majority of the values of [(x) lie in a single cluster, with some extreme outliers. In this case, we can be confident that the extreme outliers are actual errors and remove them (Section 3.2). (ii) There are at least two clusters of values of f(x) that are far apart from each other. In this case, instead of simply removing obvious outliers, we replace S by two subsets Sj and S2 with the guarantee that at least one of the St contains almost all of the inliers. Naively, this can be done by finding value y between the two clusters so that very few samples have ff f()) close y. and letting S1 be the set of points with f(x) < y and S2 the set of points with f(z) > (Section 3.3). will have cleaned up set of samples and can recurse each of the returned
In either case, subsets of S. Iterating this technique recursively on all of the smaller subsets returned ensures that there is always at least one subset containing the majority of the inliers, and that eventually once it stops having too large of a covariance, we will return an appropriate approximation to Σ.
We want to highlight the main point of difference where our techniques differ notably from [DKS18]. In order to implement the algorithm outlined above, one needs to have good a priori bounds for what the variance of (xx over the inliers ought to be. Since f() is quadratic polynomial, the variance of f over the inliers, itself depends on the covariance Σ, which is exactly what we are trying to estimate. This challenge of circular dependence does not appear in DKSS18: their goal was to estimate the unknown mean of an
Gaussian, and thus it sufficed to use a linear polynomial (instead of a quadratic polynomial). Importantly the covariance of a linear polynomial does not de- pend on the (unknown) mean (it depends only on the covariance, which was known in their setting). In order to overcome this challenge, we observe that if S contains most of the inliers, then the covariance of S cannot be too much smaller than the true covariance Σ. This allows us to find an upper bound on 2, which in turn lets us upper bound the variance of fax over the good samples (Lemma 3.2).
Related Work We refer the reader to [DK23] for overview of algorithmic robust statistics. We mention the most relevant related work here and discuss additional related work Appendix A. Algorithms for list-decodable covariance estimation were developed in the special cases of subspace estimation and linear regression in [KKK19; BK21; RY20b; RY20a; DJKS22J. On the other hand, [DKS17: DKPPS21J present SQ lower bounds for learning Gaussian mixture models and list-decodable linear regression (and thus list-decodable covariance estimation), respectively.
[IK22] gave the first algorithm for general list-decodable covariance estimation that achieves non- trivial bounds in total variation distance using the powerful sum-of sum-of-squares squares hierarchy. Their algorithm list of matrices containing an H, that is close to the true Σ in two metrics (i) relative Frobenius norm: || |H; E 1/2 T||: = poly (1/a) and (ii) multiplicative spectral approximation: (oly(a)E < H, 3 poly (1/ Their algorithm uses (1/a)(1/a) samples, which seems to be necessary for efficient (statistical query) algorithms achieving multiplicative spectral approximation [DKS17: DKPPS21]. In comparison, Theorem 1.2 uses only poly(d/a a/) samples, returns list of O(1/a) matrices, but approximates only in the relative Frobenius norm: |H, 1/ 1/2 Ale = (1))..
outputs an (sp(poly(//a))-siin
2
Preliminaries
For a vector v, we let ||l||| denote its fn-norm. We use Ia to denote the d d identity matrix; We will drop the subscript when it is clear from the context. For matrix A, we use ||A||] and |Allop to denote the Frobenius and spectral (or operator) norms, respectively. We denote by (v. u). the standard inner product between the vectors u, v. For matrices U, V gexd we use (U, V) to denote the trace
inner product Ees Vig. For a matrix A E Rddd we use A to denote the flattened vector in R
and for a v TRe we use of to denote the unique matrix such that A = v². For a matrix A, we let At denote its pseudo-inverse. We use @ to denote the Kronecker product. For a matrix A, we use ker(A) ) for the null space of A. We use X ~ D to denote that a random variable X distributed according to the distribution D. We use N(,, Σ) for the Gaussian distribution with mean μ and covariance matrix Σ. For a set S, we use X ~ S to denote that X is distributed uniformly at random from S. We use S b to denote that there exists an absolute universal constant C' > 0 (independent of the variables or parameters on which a and b depend) such that a S Cb..
5

---

2.1 Deterministic Conditions
Our algorithm will rely on the uncorrupted inliers satisfying a set of properties, similar to the "stability conditions" from [DKKLMS16 66. Intuitively, these concentration properties for sets of samples, but with the added requirement that every large subset of the samples also satisfies these properties.
Definition 2.1 ((7,, c)-Stable Set). Let D be distribution with mean j and covariance E. We say set of points A C IR is (T, e)-stable with respect to D, if for any subset A' C A with |A'] Z (1 e e)| the following hold: for every U E R symmetric E Rdxd, and every even degree-2 polynomial p:
(L.1) | E
0J (x- w) 20.1 (o Eo).
(1.2) 1
( ExEN - 1)(2 14) - E,U) S... /1/2////211
(1.3) Pr -E X XXDDD(X)]] [XX]||
X~A' [|(x)) E
YaD [ar In
( Sn.
(1.4) Varx~A [x(X) S Varx~nlp(X)).
(L.5) The null space of second moment matrix of A' is contained in the null space of E, i.e. ker (EDear xx" ) S ker(E).
Gaussian dataset is "stable" with high probability [DKKLMS16]; formally, we have Lemma 2.2. proved in Appendix D.1. Moreover, Lemma 2.2 can be extended to a variety of distributions (cf. Remark D.I).
Lemma 2.2 (Deterministic Conditions Hold with High Probability). For a sufficiently small positive constant eo and a sufficiently large absolute constant C, a set of m > Cd log" (d/ (11))/nn² samples from (u, E), with probability 1 - 5, is (T1, -)-sbbble set with respect p, E for all S e0-
3 Analysis of a Single Recursive Call of the Algorithm
Our algorithm, Algorithm 1, filters and splits samples into multiple sets recursively, until we can certify that the empirical second moment matrix of the "current data set" is suitable be included in the returned list of covariances. As a reference point, we define the notations and assumptions necessary to analyze each recursive call below. However, before moving to the formal analysis will first give an informal overview of the algorithm's 's steps and the high-level ideas behind them.
Assumption 3.1 (Assumptions and notations for a single recursive call of the algorithm).
S =xx,) y is set of n uncontaminated samples, which is assumed to be (1), 2cg -stabee with respect to the inlier distribution D having mean and covariance μ, Σ (c.f. Definition 2.1). We assume 77 S 0.001, cg 0.01, and Var Varx=D[X" [XT AX] s 1/ A + /2 / for all symmetric d x d matrices A and constant Ct.
T' is the input set to the current recursive call of the algorithm (after the adversarial corruptions). which satisfies |S T 2 (1 - | S| and [T] < S1/a))S).
We denote H = Exx- [
We denote by 5, T the versions of 5 and T normalized by H1/2; 3= (H1/2x: x E S} and T 111 x E T}. We use the notation ã for elements in 3 and T, and x for elements in S and T. Similarly, we use the notation X for random variables with support in S or T.
The mean and covariance of the inlier distribution D after transformation with Ht/2 are denoted by ğ = /2 p, Σ = H1/2y/1/2 We denote the empirical mean and covariance of the transformed inliers in T by ja = Ex- and E = Cov X~nnn
Much of the algorithm uses the fact that, for a Gaussian, even quadratic polynomials have small variance. We will leverage this for filtering and clustering samples. See Appendix E for the proof.

---

Lemma 3.2. Make Assumption 3.1 and recall that H = Ex-r [Xx], where T is the corrupted version of a stable inlier set S. For every symmetric matrix with ||]]| 1. we have that Varx~D((H1 X A(H x)) S 18C1/a².
Armed with Lemma 3.2, we can now give a high-level overview of a recursive call of Algorithm
1. In our notation, we call the current data set T. Denoting H = second moment matrix, we construct the normalized data set T = { normalization allows us to bound the covariance in terms of H.
for its the empirical
1/2 x E T). The
2. Since we are trying to estimate a covariance, consider the vectors ă = {( 2 E 7), which are the second moment matrices of each data point flattened into vectors.
3. The first step is standard in filtering-based outlier-robust estimation: we test whether the covariance of the & vectors is small. so, we are able to prove that the current H is a good approximate square root of 2 (c.f. Section 3.1) hence we just return H.
If the first test fails, that would imply that the empirical covariance of the 5 vectors is large in some direction. We want to leverage this direction to make progress, either by removing outliers through filtering or by bi bi-partitioning our samples into two clear clusters.
5. To decide between the 2 options, consider projecting the å vectors onto their largest variance direction. Specifically, let A be the matrix lifted from the largest eigenvector of the covariance of the 3 vectors. Define the vectors ÿ = -
Ai = (iz", A) for I E T, corresponding to the I 1-dimensional projection of onto the A direction. Since we have failed the first test, these ğ elements must have a large variance. We will decide to filter or divide our samples, based on whether the am-smallest and am ammlargest elements of the ÿs are close to each other.
If they are close, yet we have large variance, we will use this information to design a score function and perform filtering that removes random sample with probability proportional to its score. We will then go back to Step 1. This would work because by Lemma 3.2 and by stability (Definition 2)... the (unfiltered) inliers have a small empirical variance within themselves, meaning that the large total empirical variance is mostly due to the outlier.
Ideally, the score of a sample would be (proportional to) the squared distance between the sample and the mean of the inliers-the total inlier score would then be equal to the inlier variance. However, since we do not know which points are the inliers, we instead use the median of all the projected samples as a proxy for the unknown inlier mean. We show that the distance between the am--mmalees and largest js bounds the difference between the ideal and proxy scores.
7. Otherwise, amm-smallest and am ammlaagest elements of the j/s are far apart. By the stability condition Definition 2.1 (specifically, Condition (L.3)), most of the inliers must be close to each other under this I I-dimensional projection. Therefore, the large quantile range necessarily means there is a threshold under this projection to divide the samples into two sets, such that each set has at least am points and most of the inliers are kept within a single set.
The score function mentioned in Step 6 upper bounds the maximum variance we check in Step 3. For simplicity, in the actual algorithm (Algorithm I) we use the score directly for the termination check instead of checking the covariance, but it does not matter technically which quantity we use.
Remark 3.3 (Runtime of Algorithm 1). We claim that each "loop" in Algorithm takes ((md)) time to compute. The number of times run the "loop" is at most O(m), since each loop either ends in termination, removes element from the dataset, or splits the dataset, all of which can happen at most (m) times. From this, we can conclude a runtime of 2m? The sample complexity of our algorithm is also explicitly calculable to be Ó(d² (d22/a"), which follows from Lemma 2.2 and the choice of parameter 1) = O(a²) from Theorem F.1 (the formal version of Theorem 1.2).
To see the runtime of a single loop: the most expensive operations in each loop are to compute H,, its pscudo-inverse, and to compute the symmetric matrix A in Line 7 that is the top eigenvector of a de x d2 matrix. Computing H, trivially takes (md2)) time, resulting in a d x d matrix. Its pseudoinverse can be computed in ( time, which is dominated by ((md²) since m 2 d. Lastly, we observe that, instead of actually computing the top eigenvector in Line 7 to yield the matrix A, it suffices in our analysis to compute a matrix B whose Rayleigh quotient (B³)T T
(Cov x~ (X22] B³ 3²/((B²) B²)
at least 2 times (AP)T (Cov x-7, (X82) A² A?/((A') A?). We can do this via Ollog d) many
7

---

Algorithm List-Decodable Covariance Estimation in Relative Frobenius Norm
Constants:
m, a, 7) R. == C(1/a²) log(1/(Ega)) for C' 6000vCT, C² 720/co (where
C1, cn are defined in Assumption 3.1).
2:
function COYLISTDECODING(T))
3:
f O.
4:
1oop
5:
Compute H; [x-T((XX]]
Let T: (1, I ] the transformed set of samples.
6:
7:
Let A be the symmetric matrix corresponding to the top eigenvector of Cov x. (X32).
8:
Normalize A so that ||.A|F= 1.
9:
Compute the set Y, { AT 3 T.
10:
Compute the am/9-th smallest element Ωleft as well as the am/99-th largest element
Gright. well the median Umedian of Yr.
Define the function f(i) (H" AT Imedian)
12:
E Ex,7, [f(X) S C²R3/a" then
> c.f. Lemma 3.4
13:
If [ 2 0.5am then return (T:} else return the empty list. else gright - gleft R then
P c.f. Lemma 3.5
15:
Let the probability mass function p(ū) = f(3)/ Eiet, f(t).
Pick Fremoved E Te according to p( p(H,,
16:
T- + T, {Fremoved)
18:
else
19:
T +- FindDividerr(?; (Y,, om//9).
> c.f. Lemma 3.6
T - (H, E T,, H AT S T" + : AF > T). Li f COVLISTDECODING(T)), L2 COVLISTDCCOINNG((()))
20:
21:
22:
return Li U2.
23:
1+1+1.
power iterations. Since
82 [X X-T.
Cov
Σ
22
Σ
T
sET.
sET.
we can compute each matrix-vector product in (d) O(md)) time, thus yielding an (mmdd) runtime for the power iteration.
3.1 Certificate Lemma: Bounded Fourth Moment Implies Closeness
The first component of the analysis is our certificate lemma, which states that, if the empirical covariance of the (flattened) second moment matrices of current data set (after normalization) is bounded, then the empirical second moment matrix of the current data set is good approximation the covariance of the Gaussian component we want estimate.
Lemma 3.4 (Case when we stop and return). Make Assumption 3.1. Let w R be the leading eigenvector of the Cov [X with ||]|| = 1, and let E Rdxxd d be w², Note that [|w||2 =
implies || = 1. Then, we have Ht/ 1| < (1/a) Var Var AX + 1/a?.
See Appendix E.2 for the proof. Our termination check of Line 12 uses the score ((T) = ( AT
"median) )2 where Tmedian is the median of { Ai
T E T). Since Var x x [X TAX] s
E xx (X)) our check ensures that Var x AX
& poly(1/a) before returning.
3.2 Filtering: Removing Extreme Outliers
As discussed in the algorithm outline, if the termination check fails, namely the expected score over the entire set of T is large, then proceed to either filter or bi bi-partition our samples. This subsection

---

states the guarantees of the filtering procedure, which assumes that the am-smallest and largest elements in the set { A I E T'} have distance at most R for some R poly
ER-HAD AX Ex X ATAX1 is bounded by 0(1/a²). By stability, the same is true for Ex (XT AXTAAS AX- Ex-S-r(X1 AX])]] Notice that this looks almost like score function f(X), except that in f(X) we use Vmndiai for centering instead of Ex-5-7(X AX quantity is by definition unknown to the algorithm. In Lemma E.3, show that the two quantities have distance upper bounded by O(R), where H is the quantile distance in our assumption, which in turn implies that the inliers in S n T contribute very little to [x-rl/()), Given that E Ex_r([(X)) is large, by virtue of having failed the termination check, we can then conclude that most of the score contribution comes from the outliers. Thus, can safely use the score to randomly pick an element in the dataset for removal, with probability proportional to its score, and the element will be overwhelmingly more likely be outlier rather than an inlier. Lemma 3.5 below states the precise guarantees on the ratio of the total score of the inliers versus the total score over the entire dataset.
Recall from Lemma 3.2 that Var X-HI/aD [XT AX]
since the latter
Lemma 3.5 (Filtering). Make Assumption 3. I. Let be an arbitrary symmetric matrix with || = 1. Let R R= C(1/a) log(1/m) ( for C 2 /00/C1. Define Vmedian = Median( (f AT | T E TH). Define the function (()) == (7) AT Umedian) ) Let my be a number less than |S\/3. Denote by qu the i-th smallest point of (IT AI T E T). If //rr--mm 4m, S R and Ex-T [[x))] > C2R2/cc /o for C² 2 /20/E0. that is, in the case where the check in Line 12 fails, then, the function f()) satisfies Σ EEet [(T) 50 a Exešr+ [(3).
The score ratio determines (in expectation) the ratio between the number of outliers and inliers removed. In Lemma 3.5, the ratio is in the order of 1/a"~ this will allow to guarantee that at the end of the entire recursive execution of Algorithm 1, we would have removed at most a 0.01 fraction of the inliers. See Remark F.5 in Appendix F for more details.
3.3 Divider: Identifying Multiple Clusters and Recursing
The previous subsections covered the cases where (i) the expected score is small, or (ii) the expected score over T' is large and the and 1 quantiles of TXTAX What remains is the case when both the expected score is large yet the quantiles are far apart. In this instance, will not be able make progress via filtering using the above argument. This is actually an intuitively reasonable scenario, since the outliers may in fact have another R om samples that are distributed as a different Gaussian with a very different covariance-the algorithm would not be able to tell which Gaussian is supposed to be the inliers. We will argue that, when both the expected score is large and the quantiles are far apart, the samples are in fact easy to bipartition into 2 clusters, such that the most of the inliers fall within side of the bipartition. This allows us to make progress outside of filtering, and this clustering mechanism also allows us to handle Gaussian mixture models and make sure we (roughly) handle components separately.
AX ã E T) are close to each other.
The key intuition is that, by the stability Conditions (L.3) and (L.4), we know that the inliers under the I-dimensional projection {X* AX X E SnnT) must be well-concentrated, in fact lying in an interval of length ((/aa). The fact that the quantile range is wide implies that there must be some point within the range that is close to very few samples X AX,, by an averaging argument. We can then use the point as threshold to bipartition our samples. See below for the precise statement.
Algorithm 2 Divider for list decoding
1: function DINDDIVIDER at .m))
2: Let the my smallest point be gm, and my-th largest point be q/zi-mi'
3: Divide the interval [ym, -mi-mal into 2m'/ri equally-sized subintervals.
4: Find a subinterval I' with at most n' /2 points and return its midpoint.
Lemma 3.6 (Divider Algorithm). Let T = (y),..., ymm) be a set of mn points in R. Let Sproj C T be a set of n' points such that Sproj is supported on an interval 1 of length r. For every i E [m'], let

---

the i-th smallest point of the set T be qi- Suppose - qm. 2 R such that R 2 10(m' /n') I''r. Then, given T and n', my, Algorithm 2 returns a point such that if we define Ti = { E T st
and 22- T Ti then: (i) min([Ti], [Tl) 2 my and (ii) Sproj E Ti or Sproj C T2
Proof. The last step of the algorithm must succeed by an averaging argument. Consider the midpoint t of the returned subinterval I', which is at least gm, and at most g - Since Ti contains all points at
most 4m and 72 contains all points at most m-mp we must have min([Ti), I, (T2l) 2 mi- Lastly, we verify the second desideratum, which holds i & I. For the sake of contradiction, if t E 7, then since I has length r and l' has length at least Rt/22m/n') 2 5r, then / l'. However, since |/' n nTT S n' /2, we know that I cannot be strictly contained in I', reaching the desired contradiction.
4 High-Level Proof Sketch of Theorem 1.2
We discuss the proof strategy of Theorem 1.2 at a high level. See Appendix F for the complete proof.
Proof Sketch Recall that Algorithm 1 is a recursive algorithm: each call repeatedly filters out samples before either terminating or splitting the dataset into two and recursively calling itself. The execution of Algorithm 1 can thus be viewed as binary tree, with each node being recursive call.
The high-level idea for proving Theorem 1.2 is straightforward, though involving technical calcula- tions to implement. Consider the subtree grown from the root recursive call, up to and including a certain level j. We proceed by induction the height j of such subtree, and claim there must exists a leaf node in this subtree such that most of the inliers remain in the input dataset of the leaf node.
Concretely, let Tj be the subtree of height j grown from the root node. We claim that there must be leaf in this subtree, whose input set T satisfies
a (co/ / 40) + IS T S (j ()a + l,
(I)
recalling that is the proportion of inliers, éu is the maximum fraction of inliers removed by the adversary, is the actual (unknown) number of inliers removed and m is the size of the original dataset returned by the adversary. The left hand side keeps track of both a) how many inliers have accidentally removed, through the SS \ T] term, and b) the relative proportions of the outliers we have removed versus the inliers have removed, by comparing both terms on the left hand side.
For the induction step, we need to analyze the execution of a single recursive call. We show that (1) implies Assumption 3.1, and so the inductive step can follow the case analysis outlined in Section 3- either we terminate, or we decide to either filter or bipartition the sample set. To convert this into a high-probability statement, we use standard (sub-) martinaart argument in Appendix F.l.
Acknowledgements
We thank the anonymous reviewers for insightful comments and suggestions on this work. Ilias Diakonikolas is supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CA- REER), and a DARPA Learning with Less Labels (LwLL) grant. Daniel M. Kane is supported by NSF Medium Award CCF-2107547 and NSF Award CCF- 1553288 (CAREER). Jasper C.H. Lee is supported in part by the generous funding of a Croucher Fellowship for Postdoctoral Research, NSF award DMS-2023239, NSF Medium Award CCF-2107079 and NSF AiTF Award CCF-2006206. Ankit Pensia is supported by NSF Awards CCF- 1652862, and CCF-1841190, and CCF-201 1CF-2011255; The majority of this work was done while Ankit Pensia was at UW-Madison. Thanasis Pittas is supported by NSF Medium Award CCF-2107079 and NSF Award DMS- 20222993339 (TRIPODS).
References
[AK05]
S. Arora and R. Kannan. "Learning mixtures of separated nonspherical Gaussians". In: The Annals of Applied Probability 15.1A (2005), pp. 69-92.
[BBHLT20]
M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T.Schramm. "Statistical Query Al- gorithms and Low-Degree Tests Are Almost Equivalent". In: CoRR abs/2009.061007 (2020).
10

---

[BBV08]
M.-F. Balcan, A. Blum, and S. Vempala. "A discriminative framework for clustering via similarity functions". In: STOC. 2008, pp. 671-680.
[BDHKKK20]
A. Bakshi, Diakonikolas, S. B. Hopkins, D. M. Kane, S. Karmalkar, and P. K. Kothari. DoutlierRRobus Clustering of Gaussians and Other Non-Spherica Mix- tures". In: Proc. 6l IEEE Symposium on Foundations of Computer Science (FOCS). 2020.
[BDJKKV22]
A. Bakshi, Diakonikolas, H. Jia, D. M. Kane, P. K. Kothari, and S. Vempala. "Robustly Learning Mixtures of k Arbitrary Gaussians", In: Proc. 54th Annual ACM Symposium on Theory of Computing (STOC). 2022.
[Ber18]
D. S. Bernstein. Scalar, Vector, and Matrix Mathematics: Theory, Facts, and For- mulas. Revised and expanded edition. Princeton: Princeton University Press, 2018.
ISBN: 778-0-691-15120-3 978-0-691-17753-6
[BK21]
A. Bakshi and P. Kothari. "List-Decodable Subspace Recovery: Dimension Inde- pendent Error in Polynomial Time". In: Proc. 32nd Annual Symposium on Discrete Algorithms (SODA). 2021.
[BS10]
M. Belkin and K. Sinha. "Polynomial Learning of Distribution Families". In: FOCS.
2010, pp. 103-112.
[CMY20]
Y. Cherapanamjeri, S. Mohanty, and M. Yau. "List decodable mean estimation in nearly linear time". In: Proc. 61 IEFE Symposium Foundations of Computer Science (FOCS). 2020.
[CSV17]
M. Charikar, J. Steinhardt, and G. Valiant. "Learning from untrusted data". In: Proceedings of STOC 2017. 2017, pp. 47-60.
[Das99]
S. Dasgupta. 'Learning mixtures of Gaussians". In: Proceedings of the 40th Annual Symposium Foundations of Computer Science. 1999, pp. 634-644.
[DHKK20]
I. Diakonikolas, S. B. Hopkins, D. Kane, and S. Karmalkar. "Robustly Learning any Clusterable Mixture of Gaussians". In: CoRR abs/2005.06444 (2020). A. Das, A. Jain, W. Kong, and R. Sen. "Efficient List-Decodable Regression using Batches". In: CoRR abs/22 1. 1.14443 (2022).
[DJKS22]
[DK23]
I. Diakonikolas and D. M. Kane. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press, 2023.
[DKK20a]
Diakonikolas, D. M. Kane, and D. Kongsgaard. "List-decodable mean estimation via iterative muulti-filtering.. . In: Advances in Neural Information Processing Systems 33 (NeurIPS). 2020.
[DKK20b]
Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. "List-decodable mean esti- mation via iterative multi-filteringg. In: Advances in Neural Information Processing Systems 33 (2020), pp. 9312 9323.
[DKKLMS16]
I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. "Robust Estimators High Dimensions without the Computational Intractability". In: Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 2016, pp. 655- 664.
[DKKLT21]
Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. "List-decodable mean estimation in nearly-pea time". In: Advances in Neural Information Processing Systems 34 (NeurIPS). Vol. 34. 2021.
[DKKLT22]
I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, and K. Tian. "Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation". In: Proc. 54th Annual ACM Symposium on Theory of Computing (STOC). 2022.
[DKKPP22]
I. Diakonikolas, D. M. Kane, S. Karmalkar, A. Pensia, and T. Pittas. "List-Decodable Sparse Mean Estimation via Differencee-ofPaaie Filtering". In: Advances in Neural Information Processing Systems 35 (NeurIPS). 2022.
[DKPPS21]
I. Diakonikolas, D. M. Kane, A. Pensia, T. Pittas, and A. Stewart. "Statistical query lower bounds for list-decodable linear regression". In: Advances in Neural Information Processing Systems 34 (NeurIPS). 2021.
[DKS17]
Diakonikolas, M. Kane, and A. Stewart. "Statistical Query Lower Bounds for Gaussians and Gaussian Mixtures". In:
Robust Estimation of Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS). 2017, pp. 73 84.
11

---

[DKS18]
I. Diakonikolas, D. M. Kane, and A. Stewart. mation and Learning Mixtures of Spherical Gaussians". In: Proc. 50th Annual ACM Synposium on Theory of Computing (STOC). 2018.
Robust Mean Esti-
[DMR18]
Luc Devroye, Abbas Mehrabian, and Tommy Reddad. "The total variation distance between high-dimensional Gaussians with the same mean". In: arXiv preprint arXiv:/810.08693 (2018).
[DS07]
S. Dasgupta and L. J. Schulman. "A probabilistic analysis of EM for mixtures of separated. spherical Gaussians". In: Journal of Machine Learning Research 8
(2007), pp. 203-226.
[HR09]
P. J. Huber and E. M. Ronchetti. Robust Statistics. Wiley Series Probability and Statistics. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2009. ISBN: 978-0-470-
43469-7 978-0-470- 177-0-470-122990-6.
[Hub64]
P. J. Huber. "Robust Estimation of a Location Parameter". In: The Annals of Mathe- matical Statisties 35.1 (Mar. 1964), pp. 73-101. ISSN: 0003-4851.
[IK22]
Ivkov and P. K. Kothari. "List-decodable covariance estimation". In: Proc. 54th Annual ACM Symposium on Theory of Computing (STOC). 2022.
[KK10]
A. Kumar and R. Kannan. "Clustering with spectral norm and the k-means algo- rithm" In: 2010 JEFE 5 st Annual Symposium on Foundations of Computer Science. IEEE. 2010, pp. 299-308.
[KKK19]
S. Karmalkar, A. Klivans, and Kothari. "List-decodable linear regression". In: Advances in Neural Information Processing Systems. 2019, pp. 7423-7432
[Ko[21]
P. Kothari. Robustly Learning Mixtures of Gaussians. TCS+ Talk. Available online at: https: / //youuu bet.aaeeejjjjkkek be//jjookxviyy0xt=22533 2021.
[KS17]
P. K. Kothari and J. Steinhardt. "Better Agnostic Clustering Via Relaxed Tensor Norms". In: CoRR abs/1711.07465 (2017).
[Li18]
Li. "Principled approaches to robust machine learning and beyond". PhD thesis. Massachusetts Institute of Technology. 2018.
[LM21]
A. Liu and A. Moitra. "Settling the Robust Learability of Mixtures of Gaussians". In: Proc. 53rd Anmual ACM Symposium on Theory of Computing (STOC). 2021.
[LM22]
A. Liu and A. Moitra. "Learning GMMs with Nearly Optimal Robustness Guaran-
tees". In: Proc. 35th Annual Conference on Learning Theory (COLT). 2022.
[LRV16]
K. A. Lai, A. B. Rao, and S. Vempala. "Agnostic Estimation of Mean and Covari- ance". In: Proceedings of FOCS' 2016.
[MV10]
A. Moitra and G. Valiant. "Settling the polynomial learnability of mixtures of Gaussians". In: FOCS. 2010, pp. 93-102.
[MV18]
M. Meister and G. Valiant. "A data prism: Semi-verified learning in the small-alpha regime". In: Proc. 31st Annual Conference on Learning Theory (COLT). PMLR. 2018, pp. 1530-1546.
[RY20a]
P. Raghavendra and M. Yau. "List decodable learning via sum of squares", In: Pro- ceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2020, pp. 161-180.
[RY20b]
P. Raghavendra and M. Yau. "List Decodable Subspace Recovery"". In: Proc. 33rd Annual Conference on Learning Theory (COLT). 2020.
[SVC16]
J. Steinhardt, G. Valiant, and M. Charikar. " "Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction". In: Advances in Neural Information Processing Systems 29 (NeurIPS). 2016.
[Vem22]
S. Vempala. Robustly Learning Mixtures of Arbitrary Gaussians in Polynomial Time. Bangalore Theory Seminar Series. Available online at: https:/ /youuu. be/
F=9XTRRFFTgtt=3100 2022.
[VW04]
S. Vempala and G. Wang. "A spectral algorithm for learning mixture models". In:
Journal of Computer and System Sciences 68.4 (2004), pp. 841-860.
[ZS22]
S. Zeng and J. Shen. "List-Decodabbe Sparse Mean Estimation". In: Advances in Neural Information Processing Systems 35 (NeurIPS). 2022.
12

---

A Additional Related Work
Gaussian Mixture Models Gaussian mixture models (GMM) have a long history in statistics and theoretical computer science. In theoretical computer science, a system investigation of efficient algorithms for GMM was initiated by [Das99], and then improved upon in a series of works, see, for example, [VW04; AK05; DS07; KK10J. However, these algorithms imposed additional assumptions on the parameters of GMM, for example, separation between the components. Later, [MV10; BS10] gave algorithms without any assumptions on the components but these algorithms were sensitive to outliers. The field of algorithmic robust statisties has developed the last decade to develop outlier-robust algorithms. A recent line of work (BDHKKK20; LM21; LM22; BDJKK has developed efficient algorithms for learning GMM robustly.
List-decodable Learning The model of list-decodable learning was first introduced in [BB and was first used in the context of high-dimensional estimation in [CSVI7]. Regarding mean estimation in particular, body of work presented algorithms with increasingly better guarantees [DKS18; KS17; RY20a; CMY20; DKK20a; DKKLT21; DKKLT22; DKKPP22; ZS22J.
B
Omitted Preliminaries
B.1 Notation
We use Z.+ to denote positive integers. For Z+. we denote [n] def {I...., n and use Sd-1 for the d-dimensional unit sphere. For a vector v, we let ||ll| denote its fn-morm. We use La to denote the d d identity matrix. We will drop the subscript when it is clear from the context. For matrix A. we use ||Al| and ||Allop to denote the Frobenius and spectral (or operator) norms respectively. We say that symmetric d x d matrix A is PSD (positive semidefinite) and write A Z 0 if for all vectors x E Rd we have that x Ax 2 O. We denote Amax(A) == max x Az. We write A 3 B when B- A is PSD. For a matrix A E Raxdd Lr(A) denotes the trace of the matrix A. We denote by (u, u). the standard inner product between the vectors u, v. For matrices U, V E Rddxd, we generalize the inner product as follows: (U, V) Eig Viy For matrix A E Rdxd we use A² denote the flattened vector in IRd and for a Rdd we use od to denote the unique matrix A such that A' 2d_ For matrix A, we let At denote its mneudo-inverse. We use @ to denote the Kronecker product. For a matrix A, we use ker(A) (A) for the null space of A and use Pa to denote the projection onto the range of A, i.c., P = AA' [Ber18, Proposition 8.1.7 (xii).
We use the notation X ~ D to denote that a random variable X is distributed according to the distribution D. For a random variable X, we use E[X] for its expectation. We use N(,, Σ) to denote the Gaussian distribution with mean and covariance matrix Σ. For set S, we use (SS) to denote the uniform distribution on S and use X S as a shorteut for X ~ U(S).
We use a S to denote that there exists an absolute universal constant C > 0 (independent of the variables or parameters on which and depend) such that S Cb.
B.2 Miscellaneous Facts
In this section, we state standard facts that will be used in our analysis.
Fact B.1. For any matrix A E dxd Varx~W(,.>) [X_ AX] s 4/ + +8|EE/AAA1) Apl2.
Proof. We write X~ ~ ~N(H, Σ) as X = E1/2 + / for Z ~ No0, I). We have that
Var X)
X T AXI
Var (5'1/2 + 4) T A A 1/2 Z + +1]
20,1
Var [z y112 //////AA/// Z + 2/ AE + 4 Au]
(o)
2
Var (0.1)
1/ AV 2
Var [N T AΣ 21) (0.1
S 4 < 1/
+ 8 1 1
(2)
13

---

where the first inequality line uses that Var A + B = Var A + Var [B] + 2 Cov[A, || S Var[A] + Var[B] +2 Var[A] Var[B] (v Var A + Var [B] < 2 2(Var[A) Var Var( and the last inequality uses the following: The first term uses the fact that for symmetric matrix and vector v, Vorz=W(..)) [Z BZ] BI and Varz~No.. z = ||0l22 with B Σ1/ /2
and = /1/² Au.
L
Fact B.2 Axzuma-Hofffding Inequality). Let JnnN submartingale or supermatingale with respect to a sequence
for all n = 1,2,.. it holds X X Xn-1l S On almost surely,
thenfor for any > O and n E
2²
Pr[X, - X, S exp
Et=1 Cr
Fact B.3 (See, c.g., [Ber18, Proposition 11.10.34J). Let R and M be two square matrices, then [RM ||e S min ([] llop || AM
Fact B.4 (Frobenius norm and projection matrices). Let be a symmetric matrix. If L1 and L2 are two PSD projection matrices satisfying L1 I L2, then [|LA ||f S || l|f.
Fact B.5 (Pscudo-inversee of a matrix). Let G be square matrix and define R = G Let the SVD of be UAVT. Then R VATUT, Pg UAAUU and R RPG. Moreover, Let A be any arbitrary diagonal matrix such that if A1, 0, then D.s 0, and define L VAV Then = LRG.
Proof. The first follows from [Ber18, Chapter 8), the second follows from [Berl& 8, Proposition 8.1.7 (xii),, and the third follows from the first two and the fact that A AtAAt A. The final claim follows from the following series of equalities:
LRG = VAV AAATUUAV'
VAV VAVTVALU VAUU
VAAAVV
VAVT =
where use that A is diagonal and for each i such that D., + 0, O.A.,Ar, 1.
Fact B.6 ([Ber18, Fact 8.4.16)). Let A and B be two square matrices and suppose that A is full rank. Then PBA = Pg.
C Linear Algebraic Results
In this section, we prove the proofs of certain linear algebraic results that we need. In particular, provide the proofs of Lemmata C.I and C.3 that will be used later.
C.1 Relative Frobenius Norm to Frobenius Norm: Proof of Lemma C.1
In this section, we provide the proof of Lemma C.I.
Lemma C.1. Consider two arbitrary full rank, positive definite matrices En and Eg,, and suppose there exists a full rank, positive definite matrix H. such that (i) || H H S p and (ii)
||| H1/2 Ht/2 p. Then, for an arbitrary full rank, positive definite matrix E, we have
1E-1/2E,E-11 1/2 Σー 1/2 - 1//
olp || 1/2 1/pp)
Proof of Lemma C.I. Let G = 11 11112221/ Let ΣЛ = Σ 3-11221 and ΣS = Σ 1 both of which are positive definite matrices. Since Σ is full rank, obtain that
1/2,, - ,1/25
Σ - /,
14

---

This directly gives us that GE = - HE,H and GΣnG = - HEgH. Overall, we have obtained the following:
1I- || S and G- ||: S.
We first state a result, proved in the end of this section, that transfers closeness in relative Frobenius norm to Frobenius norm of the difference (along most of the directions).
Lemma C.2. Let G be d x d matrix and let B be an arbitrary symmetric matrix of the same dimension. Recall that P denotes the projection matrix onto range of G. Suppose that
| - GBGT ||F p
for some 2 1. Let the SVD of G be G = UAVT for some orthonormal matrices U and V and a diagonal matrix A.
Then there exists d x matrix such that
1. (L captures directions of G) L = V for some binary diagonal matrix DB 3 AAt. That is, the diagonal entries of AB are all in (0, 1}, and furthemooee, all the diagonal entries of AB are also non-zero diagonal entries in A.
2. (rank of L) The rank of L satisfies I| -ABll: S 2p and
3. fcloseness of G and B along L) L (RR - B) L
2pl
2pl Bllop where R = Gt.
We will now apply Lemma C.2 twice following the same notation as in its statement. In particular, the SVD decomposition of G UAV and R G1, Lemma C.2 implies that there exist two binary diagonal matrices A and A2, where A is for Σ₁ and A₂ is for En such that (i) both || A || and | - A1 || are at 2p, and (ii) V A V (RR Σ, VA V and V VÁgV (RR V2) V2) VT have Frobenius norms at most 2pI Σ lop and 2p|| 22||E2llop respectively. Let A A x A2 and define L = VAVT. By (i), we have that || L||F = ||I ALle I 4p. Since L 3 VA, and L is projection matrix, Fact B.4 along with (ii) above implies that
| EE) 1le S 2pl 2
Similarly for Σg. By triangle inequality, we obtain that
[ Σ2)L ||r S 4pmax [151 (E2(lap)
Since a projection matrix, triangle inequality implies that
[( - = E Eg L
+ (I - L)
Σ1 - -E2) (1 - L)T(
( - Σ2) L
+ +1 LilF
|S/ - Σz |1
$ p. max (1E2llop. 1Eill(o))
This completes the proof.
We now provide the proof of Lemma C.2.
Lemma C.2. Let G be d d matrix and let B be an arbitrary symmetric matrix of the same dimension. Recall that PG denotes the projection matrix onto range of G. Suppose that
IPP GBG ||F S
for some p 1. Let the SVD of G be G UAVT for some orthonormal matrices U and V and diagonal matrix A.
Then there exists d x d matrix L such that
15

---

1. (L captures directions of G) = VABVT for some binary diagonal matrix Ag = AAT. That is, the diagonal entries of AB are all in {0, 1}, and furthermore, all the I diagonal entries of AB are also non-zero diagonal entries in A.
2. (rank of L) The rank of L satisfies || ABlFF fal|= S 2p and
3. (closeness of G and B along L.) L. (RR B) I. ||
S 2pl Bllop, where R = Gt.
Proof. Let U1, U2...... . ud be the columns of U and 01, Ug..... Ud be the columns of V. Let the entries of A be A1, >2,.... Ad, which are non-negative by SVD property. Let I be the set of i's in [d] such that X; >
Define the matrices F U UBG U and B' := v BV. Then since G VAUT T we have B U = AU = AV BVA = AB'A.
F GBG
Thus the (i. entry of F is Didz.
Now define the matrix M == UTU. From Fact B.5, have that Pa UAATUT And thus, M = AAT, which the diagonal matrix with entries Ma- = for each i E J, and M = otherwise.
Using the invariance of Frobenius norm under orthogonal transform, we obtain the following series of equalities:
PPa GBG l
| (PG - GBG-G)B
I|M FIlE
Σ
(Mi,i Fi,i)²
EEJ
Σ (1 B' x?)) SEJ
(3)
Let I S. I be the of i's in J such that B2 (1/2). Then Σiez (1 - B X²)
[I/ Thus if [Z] is larger than 4p², then the Frobenius norm squared larger than r², which is contradiction.
I II, then X 1/(2 and not just > O.
Define the matrix be L := EmErA wny. which is equal to VAgV VT where AB is a diagonal matrix with the i-th diagonal entry equal to if E J \ I and 0 otherwise. By definition, L has rank |J| - [I] and furthermore, the diagonal entries of A B always non-zero diagonal entries in A.
Let R = G and by Fact B.5, we have that R = VALUT, Thus LR = VÁ V TVAUT = VABAUUT, and thus the singular values of LR satisfy that they are most
min A; S max /BB S S 21 = = /2 BV = 21
We first need two more observations: L = -RLRG and LRR LT = LRP LT, both of which hold by Fact B.5. Finally, we show that RR and B close along the directions in L.
|| -BYL ||F
|RR T LBLT
|RRP R. IT ..RBG R L I|r
|TRIPP GBG GBGT)R T.
[TR |Pg GBB ||r|| IT][R.
I I.
|RR 13 |PG GBG ||r
S 2|| Bllop
This completes the proof.
16

---

C.2
Proof of Lemma C.3
now restate and prove Lemma C.3. Lemma C.3. Let and be two PSD matrices with PB PA A or equivalently ker(A) C ker(B))
Then |ABAA PBllF s 2|JABA - PAlle
Proof. Applying triangle inequality, we have that
ABA PaI|F < ||BAA - PAIFF + |PA FnllF.
It thus suffices to show that the second term, ||P IP Pll is less than ||ABA- FAlle. Let d be the rank of and dg be the rank of B. We will show the following two results, which imply the desired bound:
|| B PAlli = ddg dal ||AA Pelli
(5)
In the rest of the proof, we will establish the above two inequalities.
We begin with the second inequality in (5). By the lemma assumptions, we have that the null space of A being subspace of the null space of B. This is equivalent to saying that the column space of B being a subspace of the column space of A. In particular, this also implies that dæ S. dA It is easy to that rank(ABA) < rank(B) I rank(A) rank(IP, )). and the eigenvalues of IP are either 0 or 1. We now state a simple result lower bounding the Frobenius norm by the difference of the ranks for such matrices:
Claim C.4 (Bound on rank difference). Let A' be a symmetric matrix such that the eigenvalues of A' belong to {0, 1, -1.. Let B' be an arbitrury matrix. Then B A 2 rank(A') rank (B)).
Proof. Let U1,-.. Ud be the orthonormal eigenvectors of A' with eigenvalues λ1 -.,-..; ... da such that [}g = for i & rank(A') and X; = otherwise. Without loss of generality, we assume rank( B') S vank(A"), otherwise the result is trivial. Let I be the set of i's such that rank(A')
and B' u; 0.
rauk(A)) (A')
IB' A 1 =
Σ
BBuu u
A'uill3 N
Σ
BBuu u; A'uil13
1=1
rank(A')
Σ
1B'u - A.ui -uu4-uu113 2
Σ Dauu = [Z].
EEI
Since the rank of B' is less than the rank of A', it follows that B'u uz nonzero for most rank B') many un's 's in {uy rank(A')). Thus [Z] is at least bank(A')- rank
By Claim C.4, we have that rank (P&) rank(ABA) S IPg - ABAIE. Thus, it implies the desired inequality, Idg - dal < P
We will now establish the first inequality (5). Observe that both PA and Pg are PSD matrices. whose eigenvalues are either 1 or O. The following result upper bounds the Frobenius norm of PA Pg terms of the difference of their ranks.
Claim C.5. A and B are two PSD matrices such that Pn 3 PA, then | .P = rank(A) BBn
Proof. Let dA be the rank of and dg be the rank of B. We have that dp rank(I' < rank(PA)) d.A Consider any orthonormal basis U Ud in Rd such that U....., Uda spans the column space of P. A. and vI,..., , Can spans the column space of B. Since the column space of i is subspace of that of Pz, such orthonormal basis always exists.
Moreover, since the eigenvalues of A are either 0 or 1, we have that IP AA = vs for S da and otherwise. Similarly, PBU, for i dg and 0 otherwise.
17

---

We will also use the following basic fact: for any square matrix J and any set of orthonormal basis vectors Wi,.... Uds have that || Σ JJull. Applying this fact to PA PB and the orthonormal basis U1,..... lid above, we get the following:
d
du
A
| - PBl
PP PA - P
Σ ==1
PAus - PB +
|| - P
dg+1
dg+1
dA
dB:
where the second equality uses that PA4; Pe, = 0 for i 2 da. and the third equality uses that PAU; puu; Uj for i I dg and PB; 0 and IP A = U, for E {dg 1,..., da}.
By Claim C.5, we have that PA Pg | |ran((A) rB)n
D Stability: Sample Complexity and Its Consequences
In this section, we prove results related to stability. Appendix D.1 proves the sample complexity for the stability condition hold for Gaussians and Appendix D.2 focuses on some consequences of stability.
Remark D.1. We note that the deterministic conditions of Definition 2.1 are not specific to the Gaussian distribution but hold with polynomial sample complexity poly(d/n) for broader classes of distributions, roughly speaking, distributions with light tails for degree-4 polynomials.
Condition (L.1) is satisfied with polynomial sample complexity by distributions that have bounded second moment.
Condition (L.3) at the population level is a direct implication of hypercontractivity of degree-2 polynomials. The log(1/n) factor in the condition as stated currently is tailored to the Gaussian distribution but it is not crucial for the algorithm and could be relaxed to some polynomial of 1/1;; this would translate incurring some poly(1 poly(1/n) to the final error guarantee of the main theorem. After establishing the condition at the population level, it can be transferred to sample level with polynomial sample complexity.
Regarding Condition (L.22, every entry of the Frobenius norm is degree 2 polynomial, thus the property holds for distributions with light tails for these polynomials, c.g., hyper- contractive d distributions.
Condition (L.4) can also be derived by hypercontractivity of degree 4 polynomials similarly.
Condition (L.5) holds almost surely for continuous distributions.
D.1 Sample Complexity of Stability Conditions
Lemma 2.2 (Deterministic Conditions Hold with High Probability). For a sufficiently small positive constant 6o and a sufficiently large absolute constant C, a set of m > Cd log" (d/ (nō))/n samples from (H, E), with probability - 5, is (17, c)-stable set with respect to p. for all S Cg-
Proof. Let A be a set of i.ddd. samples from A ((u E). We check the four conditions from Definition 2.1 separately. Since A is set of i.i.d. samples from Gaussian, it satisfies Condition (L.1) with high probability (sec, c.g., [Li18, Corollary 2.1.13]).
We start with Condition (L.2). Let X ~ (N, )), then X - g2/22 z with ~ (O I). Let A be set of m i..dd. samples from ((,, Σ) and like before, for every 1//2 2, where z are corresponding i.i.d. samples from 1), Let subset A' C. A with [A'| 2 [A - e). Then, we have the following
- μ (0, E). Equivalently, X
E A, write
1
Σ
x p)(x -T - U
1/2
1
Σ
zz -1)
)1/24
18

---

( 22 -1 21
S (1))
where the first line uses the rewriting that we introduced before, the second line uses the cyclic property of the trace operator, and the last line uses [Li18, Corollary 2.1.13]. As stated in that 5/4 as long as the sample complexity sufficiently large multiple of (d / log(4/8). Fixing = sufficiently small positive absolute constant can make the right hand side of the above inequality 0.1//4//UX////11
corollary, the inequality holds with probability
Condition Condition (L..1) be shown identically using [Li18, Corollary 2.1.9).
We now turn our attention to Condition (L.3). [DKKLMS 16, Lemma 5.17] implies that with the stated number of samples, with high probability, it holds that
Pr X-A
[m(x)| >
Var (Y)))10
2
1 2
V (n,
Since |A^ 2 |4| oo) 2 JA1/2, Condition (L.3) holds. Finally, Condition (L.4) follows by noting that Varx~A (x)) S 2 Varx=a(p(X)) and using [DKKLMS16, Lemma 5. 5.] again with = 60- In order for the conclusion of that lemma to hold with probability 1 1 6/4, the number of samples of the Gaussian component is a sufficiently large multiple of di log"(4d) (4d/(17)) the events corresponding to each of the four conditions concludes the proof.
A union bound over
Lastly, we show Condition (L.5). We will in fact show a stronger statement: suppose the rank of Σ is dg. Then, if we take m 2 dy + i.idd samples {u + 21, p 22,.... f 2m from ((,, Σ), must be the case that with probability 1, for all A' C A with |A| 2 dy + 1, we have Ezer (v x)² (or equivalently, being orthogonal all vectors x E A') implying v Ex 0 for all vectors Rd
We will need the following straightforward claim: A' = {n + ./...., . + 2'd=²) (of size dy + 1) is such that 1) {21 - 26..... Z'd= - =6) are linearly independent and 2) 2 all lie within the column space of Σ, then for any vector E Rd, being orthogonal to all of A' implies that v -E = 0. To see why this is true, observe that {zí z0:...: Zds =0}, which are linearly independent vectors that all lie in the column space of Σ, must span the entirety of the column space of Σ by dimension counting.
Thus, if e orthogonal to all the points A', then orthogonal to of {a} 26 2/4 3
which implies v T Ev = 0.
We can show the following inductive claim on the size of A, which combined with the above claim implies the strengthened version of Condition (L.5). Specifically, we show inductively that, with probability 1 over the sampling of A, for any subset A' C A of size most dy + 1, the claim conditions hold for A'. Namely, if A' {1r + 26. /1 + 2/) for some j S dy, for some arbitrary 2/1 is linearly independent and 2)
ordering of the elements in A', then 1) the set {2f 2/1 ...,,
xf all lie in the column space of Σ.
The base case of |A| 1 is trivial. Now suppose the above statement is true for |Ael - e, and consider sampling a new point μ + zt and adding it to A to form A Take any subset A' of A of size at most dy + 1. If A' C A& we are already done by the induction hypothesis. Otherwise, A' = {u+ 2
U.A. where A/- = {p+zl...., .4++ 2/ in the induction by the inductive hypothesis. The space of μ + such that 2 - 2f lies in the span of {&î - 26. ................................ 2/ 2/1 has measure 0 under N E). given there are strictly fewer than dy many linearly independent vectors in { 2 ... 2/1 26), all of which lie in the column space of Σ. Furthermore, there is only a finite number of such A/. Thus, with probability 1, the new point μu 22 will be sampled such that for all such A/e, {μ + 2T } U A remains linearly independent. Additionally, also with probability 2z will lie in the column space of Σ. This completes the proof of the inductive claim, which as we have shown implies Condition (I..5).
has size at most dy and satisfies the conditions
19

---

D.2 Facts Regarding Stability
The following corollaries will be useful later on. In particular, since our algorithm will perform transformations of the dataset, we will need Corollary D.2 to argue about the stability properties of these sets, Moreover, the next lemma (Lemma D.3) will be used extract the final Frobenius norm guarantee of our theorem given the first bullet of that theorem. The proofs are deferred to Appendix D.4.
Corollary D.2 (Stability of Transformed Sets). Let D be distribution over Rd with mean μ and covariance Σ. Let be a set of points in I' that satisfies Conditions (L.1) and (L.2) of Definition 2.1 of (n, e) -taability with respect to D. Then have that for any symmetric transformation P E g and every A' C A with
| 2 (1 - Al, the following holds:
1. P [ ExEN' --)11 s0.1 /
2. (IAT (x - 1² 2) P|] S0.1||
The following lemma (proved in Appendix D.4) will be needed to prove our certificate lemma to transfer the final guarantees of our algorithm from the empirical covariance of the sample set to the actual covariance of the Gaussians.
Lemma D.3. Let A be a set of points in Rd satisfying Conditions (L.1) and (L.2) of (1), e--stability
(Definition 2.1) with respect μ. E. Let A' C A such that AA' (1 c) Pf L E Raxd are
symmetric matrices with the property that || Covxxai [P]] - L||r S т, then
PEP - T.lp Or + [TT[[op))
D.3 Certificate Lemma
The following result shows that if the covariance matrix of X over the corrupted set of points is bounded in operator norm, then the empirical second moment matrix of T is a good estimate of covariance of inliers in Frobenius norm. We prove a more general version below that allows for arbitrary linear transformation matrix P and since we are interested in guarantees for relative Frobenius norm, our algorithm will chose P so that Ex~r[PXX P] is equal to identity.
Lemma D.4 (Bounded fourth-moment and second moment imply closeness of covariance). Let T be set of n points in Rd. Let P be arbitrary symmetric matrix. Let w Rdd be the leading eigenvector of the Cov xxxxx 82 with ||w/|2 ||2|2- = 1, and let E Rdxd be w². Note that |lllz = implies ||A||| 1. For every subset T T with [T'] 2 (a/2)(TT, we have that
2
2
E PXX X
E
[XXX
P
VarlX"] P
PAPX]
and
xaT
a X~1
4
Cov PX] X-TV
E a
[XXX
P1
PAPXI + at X-T
PXXXX
a X-T
lp
In particular, suppose that there exists set S that satisfies Conditions (L.1) and (L.2) of (1, E)- stability (Definition 2.1) with respect to a and E for some n and e, and suppose that |S T 2 min(a[T1/2, (1 -e). Then
PEP
E 1XXXXXPP X~1
P < VarlX XAPXX
+ 1 a² 1
E IPXX P
2
a X
Proof. Let T define the set (PX X T}. In this notation, w is the leading eigenvector of [X with ||w|2 1, and A = wa. Then, for any T" C T with [T'| 1/22/2 we have
Cov Gov,_>lX²
the following
(
2
Var X [TAXX= X-T
sup
E
1002
_
E
1.
|1
X-F
V~T
T
27
sup
E
x02
E
18
202
?
||
T
X
YnT
20

---

T
T
E
x02
E
S
IT'
XNTITT
F-T
2
sup
E
E
[
1
(since (T (a/2)[T)
VER .I =1 X~TP
Y~T
2
sup
E
E
y
(E 2 (E()))2 for any Y)
"E .|+||==1
Y-T
27
1,1)
sup
[XX
E YNT
E X-T
-XXXX
E X-T
2
where the penultimate step above holds by lifting the flattened matrix inner products the previous line to the matrix inner product, and the last line uses the variation characterization of the Frobenius
norm. This implies the first inequality since Ex_r(XXT]
Ex~r (XXX
We will now establish the second inequality. Using the relation between the second moment matrix and the covariance, we have the following:
Cov [X] X~5"
E [XX X-T
E X~7
XXI
E
X
E
X
E
[X
X
X-T7
X-T
<
2
E X-TT
XXX
E
[XX]
+2
E
[
E X~
X-T
1--
I Var a X-T
T AX
+
E X~TT"
[X]
E X~T
where the last step uses that Ex [X] Ex [X]] has rank one and thus its Frobenius and operator norm match. Thus to establish the desired inequality, it suffices to prove that
E Ex X
E
x [ (2/a)- = J. Indeed, we have that
E
|X
[XX
1
Σ
XX
T
Σ XET
X
8~T
X~T
X~T
IT'
T
Xet
2 1
XX
2 1
Σ
X
a
IT
XET
XET
where the last expression is in fact equal (2/a: E Ex second statement.
[X This completes the proof for the
We now consider the case when T contains a large stable subset. Let T' = T S, which satisfies
that |T' 2 (a/2)[T) and (TI 2 (1 - (S.). By applying Lemma D.3 with -= [xxr(PXXX to the second inequality in the statement with TV, we obtain the desired result.
D.4 Proofs of Corollary D.2 and lemma D.3
Corollary D.2 (Stability of Transformed Sets). Let D be a distribution over Rdd with mean μ and covariance E. Let A be set of points in Rdd that satisfies Conditions (L-1) and (L.2) of Desinition 2.1 of (1, e) stabbility with respect to D. Then we have that for any symmetric transformation P E dddd and every A' c. Awtth A' 2 (1 - A)] the following holds:
1.
P
ExEN x - S0.1 PPEPP
A
2.
P
Ex 1)(x T ->) P <0.1||PP||o op
[A'
21

---

Proof. We explain each condition separately. We begin with the first condition as follows: For any unit vector u in Rd we have that
Σ
S..IV PEPUS S VIIpSiPllap
A
ÆEA'
where the first inequality uses Condition 1I..1) of Definition 2.1 for v Pu.
now focus our attention to the second condition. Denote := [.4 EmeN 1)(x - u)² for
+
saving space. Let be any symmetric matrix Q E Rdxd with ||Q1| I 1. Using the cyclical property of trace, we obtain
P ( PP)=))Q0- - ( (r(((=)
PQP) s 0.1 // PQPE!1
where the last step applies Condition (I.22 of Definition 2.1 with V = PQP. Finally, using the cyclic properties of the trace operator,
/ 1VPP = tr 1/2 PUPPPOPPQPP =
=IQPEPIE < 1Q ||PEP|E
where the first inequality uses Fact B.3 and the second inequality uses ||||| 1. Thus we have the following:
||| ( p| sup tr Q:1R@ISS
Σ) PQ)
PQ)
sup symmetric Q:11011eS1
tr
S PEP| llop.
where the second equality is due to the fact that P ( P is itself symmetric.
Lemma D.3. Lel A be a set of points in Rdd satisfying Conditions (L.1) and (I.2) of (1,, e)-stability
(Definition 2.1) with respect to μ. E. Let A' C such that |A' 2 (1 - -A) If P, L E Rdxd are symmetric matrices with the property that Covx~Ar [PX] L|[e then
PEP - LllF = Or + [b(ppp
Proof. To simplify notation, let S = Covx [X] and Σ = Ex- - 14) - T. Observe that Σ E + (μ+ p)(u T. We apply triangle inequality and Corollary D.2 with obtain the following:
IP( - < P(E - E) [|[( p A)
T PIl
=P - E)P |P[M (PP((-11 f
< 0.1 +.1
< 0.2 PEPllop
(6)
where the first inequality follows from the triangle inequality and the second inequality uses Corol- lary D.2.
We now analyze the desired expression by using the triangle inequality and the lemma assumption as follows:
PEP T.I|r S | Pp TA|F + || E) S + 0.2|
where the first term was bounded by by assumption and the second term uses the bound (6). Thus it suffices show that ||EP = O(r + [|_])op). To this end, we again use triangle inequality as follows:
PEP|Ipp < IPEP - L| + |p + IP E)p S [l + 0.2] PEPllop
where the second inequality uses the bound (6). Rearranging the above display inequality, we obtain PEPPlop O(r + [L)p)))
D
22

---

E Analysis of a Single Recursive Call of the Algorithm: Proofs from Section
In this section, we present the details that were omitted from Section 3. We recall Assumption 3.1 from the main body.
Assumption 3.1 (Assumptions and notations for a single recursive call of the algorithm).
{ara) x is of uncontaminated samples, which assumed to be (17, (eto--ttable with respect to the inlier distribution D having mean and covariance p., E (c.f. Definition 2.1). We assume & 0.001, 6o = 0.01, and Varx~D [XTAX] & Ci / + |> for all symmetric x d matrices A and constant C1.
T is the input set to the current recursive call of the algorithm (after the adversarial corruptions), which satisfies NS 2 (1 [S and [T] s (1/a)]S).
We denote H = =Ex-T [Xx]]-
We denote by S. the versions of S and T normalized by Ht/2; 3 (Ht/2x: x E S) and T (Hi/²x x E T). We use the notation T for elements in S and T,, and for elements in and Similarly, we use the notation X for random variables with support in 3 or T.
The mean and covariance of the inlier distribution D after transformation with HT/2 are denoted by jı ;= HT/2,, n. = H We denote the empirical mean and covariance of the transformed inliers in T by = E Ex and Σ Cov X~
E.1 Normalization and Proof of Lemma 3.2
We start with simple result stating that after normalization with H H1/ the mean and covariance of the inliers, both empirical and population-level, are bounded. This is intuitive since the inliers constitute ((a--fraction of the overall samples and the second moment of the complete set after normalization is bounded by identity.
Lemma E.1 (Normalization). Make Assumption 3. I and recall the notations ÿr, E, f. E that were defined in Assumption 3.1. have that:
1. [Bln S 2//o.
2. |Al|2 s 12/aa
3. [Ello $3/0
4. 17 I v3/a
5. Exaa(XIll S 2/ and Cov (ollallA1l S 4/a.
6. For every matrix A with ||]]| $ 1, Ex 1x AX - Ex Ex= ( <
1 /a..
Proof.
We prove each part below:
Establishing Item 1 The transformation H is such that Ex [XX
Ex-r x Ht/2] Ht/2HH//2 Pи. which has operator norm most 1. By
assumption, we have that nnT 2 (1 -2 2 0.5a[T). Thus, we obtain the following inequality:
Σ
TI 1
TT
T
2 PH 1
PH Q
(8)
TnT
S
T
S
T
ZET
23

---

By applying (8), we obtain
2 I
Σ SnT
Σ
(x - A) - a) =
ΣF
H
S
T
FEShT
implying that Sap S 2/a, since PH is just projection matrix with 0/1 eigenvalues.
Establishing Item 2 Since, for any random vector X, we have that E[X] = E (which is equivalent Cov [X] 0), we obtain
ju
Σ
TT
P
2
SnT
TEšnī
where the last inequality uses (8). This implies that || < 2/a.
Establishing Item 3 The goal is to bound the population- covariance |E To this end, we will use the bounds from Items 1 and which bounds their empirical versions and relate the empirical versions to the population ones via the deterministic conditions.
Consider an arbitrary subset S1 of S satisfying
S1
[ (1 2c0). We first note that by Corol-
lary D.2, we have that
Σ E [[X -x) x) (
< 0.1 ||/
and
j
[X]
0.1
X-31
8-31
2
op
Now define Σ = E Ex~3ni - -x) - T2)T], the centered second moment matrix of Šnn,
which satisfies Σ₁ ΣΣ (īi -- - T.).. We have that
[ op S | - + ||E1|opp
(triangle inequality)
-S Eg + 1| ill2 + |||||ap (triangle inequality and E. E - ( -b)
< 0.2//E/lop + ||ا||.p
where in the last line we use (9) for 51 SnT and the fact that 5n 2 (1 (1)2))) Rearranging,
we have that |E_llop 1.25 Dlpp for which we can use Item to further upper bound it by 3/a.
Establishing Item
We use a similar argument in Item 3:
aill
|| + 7 μ112 |Al| 0.1 / E S v3/a.
(10)
where the first step uses the triangle inequality, the second inequality uses Equation (9) for 3 = 3nf, and the last incquality uses Items and 3.
Establishing
Item 5
For the covariance condition, we have the following:
CovlX X~S
S
E X~5
(X
x - -
(using Cov 3 E(XXT)
op
E F
(X - x 7
|| op
(triangle inequality)
< 1.1//E/lop.
where the last step upper bounds the first term using Equation (9) for S S, which trivially satisfies |S| [5 2c.). The overall expression is upper bounded by (1.1 x 3)/ /a by Item
The mean condition has a similar proof:
E E <
E X
X
11 & 0.1 [Ellop + /3/a 2/ Va. +
X~S
where we use Equations (9) and (10).
24

---

Establishing Item 6
Consider an arbitrary square matrix A with ||A]|e S 1. We have that
E
X
AX
E X
[
(H)
X~8
A, E
[XX
E
(1H112 (1
X
4, Cove2
X
+
E
E
[
(5 + xipi
X~S
X~
X
A, Cov|
Σ
+
A,
E
[
E
[X]
pup
(triangle inequality)
X~3
X~S
< Cov
[X]
- -5
+
E
pip T
(variational definition of Frobenius norm)
X~3
F
X~5
(
T
E I(X - x
- ]
Σ +
E [X] -
E [X] 1 Øi
X~S
XN0
Xx-3
E
E
X~S
X~2
E [ - m1) m)
<
E
[X-
xi
(X
イ Σ
+
E
X
16
X
X
X~3
E
E [X] pp
8~5
X~.
E [X- - (x - 1 1 5
+3
E
[X]
X~5
1x~8
< 0.1| op + 1300
(using (9))
< 1/a,
(using Item 3)
where the inequality (a) uses the fact that |luu" we T T12 I ||u - -w13 + ||u 2/13 for the last term.
The previous result implies that the mean and covariance of the inlier distribution after transforma- tion with HT/2 is bounded. Since the variance of degree-two polynomials under D is bounded by assumption, we obtain the following bound on the variance:
Lemma 3.2. Make Assumption 3.1 and recall that H = Exxr[XXT] where T is the corrupted version of a stable inlier set S. For every symmetric matrix with ||]|] 1, we have that Varx~D((H)/2X)) A(H S 18C1/a?
Proof. By Assumption 3.1, we have that Varx [ S (( 11 Byl1/
for all B Rddd Applying this to B = H1/2AH we have that
Varl(Ht/2xx] A(H A - C1 12 X~D
AH 1/2 1
= - 15 1 + ||51/2 A713))
(11)
where we use that //512 = 12/22t/2AAH//22
and ||
pul1 =
/5 A since Σ H 1/222/1/2 and ÿ H1/2p. By Lemma E.I, |/iloop < 3/a. Since || = 1, we have that the first term in (1)) is bounded as follows: ||51/ 2 S
2 A < 9/a², using the fact that ||AB|| S || B|| (Fact B.3). We also have that A < || li S 9/a², where we the bounds from Lemma E. The desired conclusion then follows by applying these upper bounds in (11).
L
25

---

E.2 Certificate Lemma: Proof of Lemma 3.4
Lemma E.2 (Case when we stop and returm; Formal version of Lemma 3.4). Make Assumption 3.1. Let w Rd be the leading eigenvector of the Cov X~7 (X 22 with ||wll 1, and let Rdxd be w Note that ||wl|2 implies that
||A|| 1. For every subser T S with TT' (a/2)(T), we have
1
Cov - PH R~TT"
Var
XT
AX]
a²
FF
a
XxT
In particular, we have that | - Psll < Var
H
PH l
S
+ AX +
o and
x
X
AX
+
+
Proof. We will apply the main certificate lemma, Lemma D.4, with P H1/2 The desired result then follows by noting that Ex~r(PXX) EXXTPP
PP H F and the operator norm of F is at most 1. We will use the following result, proved in Appendix C, to upper bound the frobenius norm of H 1/22 1/2 Py:
Lemma C.3. Let and be two PSD matrices with FB PA or equivalently ker(A) ker(B). Then ABAA FB F= < ABA - PAI|F
Before providing the proof sketch of Lemma C.3 below, we show that it suffices prove the desired result. Since И the second moment matrix T, we have that ker(H) (H) S ker(E ker(EwesnT xx which is further contained ker(E) by Condition (L..5) in Definition 2.1. We apply Lemma C.3 with B = Σ and A = H, which gives the desired result.
We now give brief proof sketch of Lemma C.3. By triangle inequality, it suffices show that PP < A- A//F. Since ker(A) C ker(B), PA-PP is again a projection matrix of rank equal rank (a)-rank(()))) and thus its frobenius On the other hand, the matrices ABA A and PA have rank difference of at least rank(A) rank B). Combining this observation with the fact that PA has binary eigenvalues, we can lower bound ||ABA PAIlF by square root of (An rank(B).
is equal to square root of rank(A) rank B).
E.3 Filtering: Proof of Lemma 3.5
We first show that if we take the median of a quadratic polynomial p over the corrupted set, then the sample mean of p over the inliers is not too far from the median if the left and right quantiles are close.
Lemma E.3 (Quantiles of quadratics after normalization). Make Assumption
3.1. Let A be an
arbitrary symmetric matrix with ||Al|e 1. Define Jwedian Median
Aa
2 T Let mi
be any number less than [S|/3. Denote by qs the i-th smallest point of A
T E T]
Suppose that qmp qm for R C(1/a) (1/n)))) with C 100 (recall that the absolute constant C₁ defined in Assumption 3.1). Then, E Ex AXXXX Tmediaa
2R.
Proof. Let μl = =Ex Ex (Not to be confused with j and jú in Assumption 3.1, which are expectations of X in the samples and at the population level, instead of the quadratic form in the definition of μ!.)
Given that Umedian (by definition) lies within the interval [Qmg gpr-mm] which has length most Rt it suffices to argue that μt also lies within distance R of that interval. Namely, μ 2 9m, R and μ' < - my + R.
Let o² == Varx (12 /x The (n, 2e0) 2ea)-stability of S in Assumption 3.1 (see Condition (L.3)) implics that all but fractin of { A T S T3 lies in the interval
26

---

Ex~D((Ht/2X)) A(HH/// 100 log 1/)) since the size of the set Šnî) is at least |S| 2co) (by Assumption 3.1).
Thus, for at least (1 1))5 7 2 | (1 - 260 r))|s| points in T, the value of TTT AT lies in the ( interval Ex=D|(H//2)) - + 10x log(1/n). Since v) - 0.01 and co < 1/4, the number
of such points least [5]/3.
Rephrasing, there is interval (Weeft: Mright] that contains at least /$// points in T, where
E 1 A(/T/((////))) 10x log
Vleft
X
Fright = E (2 A(H11/2)) + 10x (l/))))))
X
Therefore, there are at most [T] - 1 points in T that are less than ylet, implying that 7 2 Geeft Furthermore, since, by assumption we have mı $ |S|/3, this implies that 9 Vleft. By symmetric argument, we also have that Om; I Mright.
Next, recall that by Item 6 of Lemma E, have that Ex~D (X~D((H+/2)) A(Ht/2 n²|
( x)_ A(H X E Ex~g(X (X AX]] < 1/a. Thus, we have qprl-m; 2 yleft 2 n' 100 log(1/m) - 1/a. Rearranging, we get p² S qpri-m, + 10o log(l/n) + 1/a. Symmetrically, we get that μ² 2 gm1 10o log(1/n) 1/a.
Finally, we argue that 10o log(1/n) 1/ux s R. showing that μ² S q/21-m, + and μ 2 4m R. which we argued at the beginning of the proof is sufficient to show the lemma statement. To argue this, by Lemma 3.2, we have that o S 5vC1/a. Thus, suffices to choose, as in the lemma statement, that R (C/a) log(L/n) for some sufficiently large C' > O.
The above result implies that if we calculate the "squared deviation" of the projections of inliers centered around the empirical median of the corrupted set, then it will be the order of the empirical variance of inliers up to factor of R² (by triangle inequality). Moreover, the empirical variance of the inliers is the order O11a²²) by Lemma 3.2. Thus the variance of the corrupted set much larger than the upper bound, then we can assign score each point, the function f below, such that the contribution from outliers is much larger than the inliers.
Lemma E.4 (Filtering; Formal version of Lemma 3.5). Make Assumption 3.1. Let A an arbitrary symmetric matrix with ||A|||= = 1. Let R C(1/a) log(1/n) for C 2 100/C1. Define Vmedian Median (5 AT T)). Define the function ( = ( A Vmediau)2 Let my be a number
less than /3 Denote by qu the i-th smallest point of (5 At EE T}.
If q/T -m Gmz < R and Ex [f()) > C' R / for C' 2 720/co. that is, in the case where the check in Line 12 fails, then, the function f(.) satisfies
Σ GET
Σ s()) 10)
a
JESHT
Proof. The core argument for the proof is that Enešnt (() can be upper bounded under the assumption that q/T -m. -mm < R, as shown in the following claim.
Claim E.5. Assuming the conditions in Lemma E.4, we have EneInf ((3) S RR
Proof. Let p¹ = =E ATAX), We have the following series of inequalities:
Σ [(3) < Σ f(3)
(since f(x) 2 0)
FEšnT
Σ
Ai
Vmedian) )
3E3
27

---

x Tx - w²) -w)= + (n' Vroedian ))
2 Σ
(by (a + 6)2 - 2a² + +2b)
BEB
2|
Var X AX| + Σ (n'
Vmmediin)
X~S
ZE8
2|S] Var Xm.
X AX + 8R
(by Lemma E.3)
72C
2|S
+ +8R2|s
(by Lemma 3.2 and Condition (L.4))
a²
$ 9
(by definition of Rt)
where the last line uses that R 2 12/Ci/a, which is satisfied for C 2 12 This completes the proof of Claim E.5.
On the other hand, we have that
(by assumption)
ΣET
2 0,5C"
(since [7'] 2 SSTT 2 |S](1 2ca) 2 SS|/2
> (360/co)R211 S////a
(since C' 2 720/co)
2 40/
Σ (())
(using Claim E.5)
žešnI
This completes the proof of Lemma E.4.
F Proof of Theorem 1.2
In this section, we present the main algorithmic result of the paper. As previously stated, the theorem holds for distributions beyond Gaussians, as long as the input set points satisfies the deterministic conditions from Section 2.1 and the distribution meets mild requirement, We now restate and prove the theorem in this more general form.
Theorem F. (Weak List Decodable Covariance Estimation). Let the ambient dimension be d E Zez. let C be a sufficiently large absolute constant, and let the parameters a E (0, 1/2), e E (0, en) for a sufficiently small positive constant 6o, and failure probability 5 1/2) be known to the algorithm. Let D be distribution with mean E RR covariance Σ E Rdxd and assume that There is a polynomial-time algorithm
Var x=> AX] = O2 /21 + || such that, input a., 8 as well as (a, coorruption of set S (Definition 1.1) with [S| Ci (1/(a))) which is ((ca/40)a 2en))--sabl with respect to D (Definition 2.1), with probability least 1 - 8 over the randomness of the algorithm, the algorithm returns list of most O(1/a:) many sets T; which are disjoint subsets of samples in the input, each T₃ has size at least 0.5om, and there exists T; in the output list such that:
Recall the notation in the corruption model (Definition 1.1) where n. is the size of the original inlier set S and & is the number of points in S that the adversary replaced-nt and are unknown to the algorithm except that v. 2 om and f. S en. The set T3 satisfies that [T. n S| (1 -0.01))(n E).
Denote H; : Ex-T; [XXT]. The matrix H. satisfies
max (1( P (((")))/2((H))12 PElll) - (((1/a))))gl (1/)))
The Gaussian distribution N ( >)) satisfies the distributional assumption of Theorem F.1 (c.f. Fact B.1), and set of size m C² l (d/oo) from (1, Σ) ((sa/40)a² 2 with probability 1 d for a constant eg (c.f. Lemma 2.2). Thus, Theorem F.1 theorem covers the Gaussian
a
28

---

case D = (p, Σ) with polynomial sample complexity, and it directly implies Theorem 1.2, the main result of this work.
We achieve the guarantee of Theorem F.1 by combining the procedure the previous section in a recursive algorithm (Algorithm 1). We maintain the notation of Assumption 3.1 with the addition of subscripts that indicate the number of filtering steps performed.
We restate the algorithm below, before proving Theorem F.l:
Algorithm 3 List-Decodable Covariance Estimation in Relative Frobenius Norm
Constants:
m, a, 7): R := C(1/a²) log(1/(<oa)) for C' 6000/C1, C' > 720/co (where C1, are defined in Assumption 3.1). function (OYLISTDECODING((T))
2:
3: 6 O.
4: loop
5:
Compute H, Ex-T, [XX]]
Let (H! x T.} the transformed set of samples.
6:
Let A be the symmetric matrix corresponding to the top eigenvector of Cov Xn [X 8..
7:
8:
Normalize A so that |||||= 11
9:
Compute the set Y, T - TA
TTT,)
10:
Compute the am/99th smallest element Nees as well as the am/99tth largest element
Fright, well as the median Vmedian of Y,,
Define the function f() (= AF )mediaan)?. Ex,9, [f()) - C²R2/O² then
12:
D c.f. Lemma 3.4
13:
If [T. 2 0.5am then return (Ti) else return the empty list. else if fright Deft R then
14:
c.f. Lemma 3.5
15:
Let the probability mass function p()) f(0)/ Exeñ, f(Ø).
Pick Fremoved E Ti according to p p(H.//22)
16:
T--1 + T, (Fremoved))
18:
else
+- FindDivider amm/9).
b c.f. Lemma 3.6
T + (H, : E T,, H AJ < <), T - 1H i TET AF > T).
20:
[ + COVLISTDECODIN((T)) T2 COVLISTDECODING(("))
22:
return L1 UL2
23:
t 1+
Proof of Theorem F.I. Since the final error guarantees do not depend on without loss of generality we use the maximum level corruptions letter denote the expression (Eo/ 40) as in the stability assumption in the theorem statement on the inlier set. We will proceed to prove Theorem F.1 by induction, and crucially use the following fact that "union bounds also work under conditioning".
co 0.01 in the following proof. We will also use the
Fact F2. If event A happens with probability 1 Ti and event B happens with probability 1 - T2 conditioned on event A, then the probability of both A and B happening is at least T1 T2-
The technical bulk for proving Theorem F.1 is Lemma F.4, inductive claim over the levels of recursion, that (in addition to some other basie properties) with high probability over any level, either (i) there recursive call at prior level whose input contains most of the inliers. and by definition that call has terminated, or (ii) there exists some recursive call at this current level whose input contains most of the inliers. We will use the following notation (Definition F.) to denote various objects in the recursive execution our algorithm.
Definition F.3 (Notation for Recursion Tree). We define rooted binary tree T that corresponds to the execution of our recursive algorithm (Algorithm 1). The root node at level O corresponds to the top-leve call of COVLLSSDDECODING (Algorithm 1) and for every non-leaf node, left child corresponds to a call of CoYLISTDECODING from Line 21 and its right child corresponds to a call
29

---

from Line 21. Thus, every node is uniquely specified by the level in the tree and its position within that level. We denote by Tt the ith node of level j. where the node numbers are also O-indexed (e.g..
[(] the root node is To,o). For the node Tig, we denote by T(E.3) the input data set to the corresponding recursive call. In order to refer to the working data set at the thh iteration of the main loop in the execution of node Tag. we the notation ((t33) and T((.s)
(t)
(t) exactly in the same way as T(t) and T(t)
are used in Algorithm 1. Finally, T3 (i.e., using a single subscript) refers the subtree growing from the root and including all the nodes up and including the jth level.
Lemma F.4. In the context of Theorrm F.I, consider the recursion tree of COVLISTDECODING (Definition F.3). Then, for any j E 9//...,///)) we have that with probability at least 1 0.01ajō the following holds:
1. (Size decrease under recursion) The input of every node Tr.j of level j satisfies (T(6) S jam/9
2. (Disjoint imputs) Consider the subtree Tj growing from the root and truncated at (but including) level j. All the leaves in T have disjoint input sets. Note that the leaves may not all be at level j. and some might be at earlier levels.
3. (Bound on inliers removed) Consider the subtree Ty growing from the root and truncated at (but including) level j. There exists a leaf T in T, (but the level of the leaf j' is not
necessarily equal j) such that its imput T(f33) 3') satisfies
(0)
(co/ (c00/40) 40) (1)))))))))))))))))))))) 3') +
S (co (cm/20)m + l
(12)
where as in Definition 1.1, m is the size of the original input set of the root node To.0 and 8 S Egn is the number of samples that the adversary replaced in S. In particular, the number
of inliers removed by the algorithm until T ji) is at most (j + (c))))(//22))))))))))
(0)
Remark F.5, We remark on why (12) uses a cubic power of which is the same cubic power appearing in Lemma E.4 that states that the total score of all the outliers is a 1/a2 factor more than the total score of the inliers. The three powers of a are due to the following reasons: 1) the inliers can be as few as an a-fraction of all the samples, 2) the depth of the recursion tree can be as much as O(1/a), meaning that a set can be filtered O(1/a) times, and 3) Theorem F.1 guarantees that we remove most an O(a) fraction of inliers. We also remark that, by tweaking parameters in the algorithm and increasing the power of (1ly(1/a) in our covariance estimation guarantees, we can make the score function ratio (and hence the poly(a)) factor in (12)) as large power of a as we desire. This would guarantee that we remove at most a smaller poly(a:) fraction of inliers.
Proof. We prove Lemma F.4 by induction on the level number j. For the base case of j = O. Conditions 1 and 2 are trivial. As for Condition 3, at j 0 we have (T/00) = m and |S T0(0000 < é by the detinition of the contamination model (Definition 1.1), which directly implies (U)
a (0) + |S ( S a² 400m + L < a (c0/20mm + é as desired.
(o)
To show the inductive case, we assume the lemma statement is true for some j and we will show the statement for the case j 1.
Conditions 1 and These are trivially true, by virtue of the fact that the recursive algorithm, after it is done with removing points via filtering, it partitions the input set using FINDDIVIDER which guarantees that both output sets have size at least m2 = am/9 / (Lemma 3.6).
Condition 3
Recall the notation ((id)) from Definition F33 that is used to denote the set of points in the variable T, after the th iteration in the 4t recursive call in level j.
By Fact F.2, we will condition on Condition 3 being true for TT. the subtree truncated at (but including) level j and show that Condition 3 holds also for T,+1, the subtree truncated at level j + 1, except with probability 0.0lad. Concretely, the conditioning implies that there exists leaf Te. of the subtree
30

---

Tj whose input set (0) ('' satisfies the inequality in Condition 3 for S Jf < then done (since it continues to be leaf and the desired bound on the right hand size in Equation (12) is only larger). Otherwise, in the case of j' j. we have to analyze the execution of the recursive call associated with this leaf node in the recursion tree J..
To begin with the analysis, we verify that the input set T (
satisfies Assumption 3.1. We first check
that |S n T d)
2 n01 - 200):
(0)
|S I (0)
|S| |S \ T .01
(0)
2 (j + 1)aa (E0 20020)mm -
(by the inductive hypothesis)
2 (9/a 1)a² 200220mmm
S 9/0)
2 n a² Emm En7
(l < k)7)
2 n arg - Eg
(n 2 am)
n 1.5eg
(13)
where the last line uses that a S 1/2. Then it remains to check that (T S (1/a)]S], but this
trivially satisfied since it holds for the input set T (0000) that start with: |T (1 - [ S (1/a)n- [L.
(0)
In a recursive call, the algorithm iteratively removes points (through Line 16) before either terminating (Line 12) calling FINDDIVIDER and recursing (Line 21). Denote the iteration just before either terminating or running FINDDIVIDER by t... We need to argue that the iterative filtering of points prior to iteration & still roughly preserves Condition 3. Lemma F6, that is stated below and proved in Lemma F.,, captures the standard martingale argument for iltering-based robust algorithms, and it
informally states that if the input T satisfies Assumption 3.1, then Condition is roughly preserved.
(0)
Lemma F.6. Recall the notations and assumptions from Assumption 3.1. I. Consider an execution of DOVLISDDECODINGS with To = ' (with T satisfying the assumptions from Assumption 3. 1), and suppose that (Tol 2 C' log (1 (1/(ox))- Further assume that |S \ Tol S 1.5colS] (which is strengthening over Assumption 3.1). Moreover, denote by Te the dataset through the loop iterations of Algorithm 1. Then, with probability least 0.01ad, it holds that
(co/ TTl + + \ Til < aco + IS Tol + (co
simultaneously for all iterations t until the execution of COYLISDDECODING enters either Line 13 or Line 19.
Concretely, applying Lemma F.6 for input set T( s) and with failure probability 0.01 in place of 8.
(0)
The lemma is applicable since its first requirement J.S T (V' f)
< 1.5eo|S] has been already checked
(0)
in (13), and for its second requirement have that [T 5) (T S| > (1 1.5eg) S 2
(0)
C' (aaaaa)) log(//(o0)), where the last one uses (13) and the next step uses our assumption |S| >
Ca((aee)) log)).(a))). The lemma then yields that, with probability at least 0.01aš. T 1 is such that
(c(o/40) (c))
1 + T o 5)
s ()aa(cc/200)))) (cm/20)m + E (co/40)a
(14)
Now, either the recursive call terminates at iteration to or it goes into Line 19. In the former case, are done (since it now a leaf node). Otherwise, the recursive call uses FINDDIVIDER to partition (p(i into T" and 7" We need show that least one of T" and 7 satisfies Condition 3 (for case (e5)
j + 1), using Lemma 3.6. Let us now derive what parameters and set to invoke Lemma 3.6 with.
Using (i) Condition (L.3) of the stability property of the original inlier set S, and (ii) the fact that
(Ht/2x) X A(Ht/2 (x A(Ht/22)) is even quadratic in X for any H
31

---

and A, it must be the case that a 1) fraction (recall is a shorthand for (co/40ja²) of the points
S satisfies
(HT)22) 2)(+/222))
E X~N(pE
(H x) A(Ht/2XX)
(15)
s 100og(2/11)
Var X~D
(Ht/2X) [(HH2X A(H112X)
50llg(2/m)) a
(Lemma 3.2)
Denote the set of points x E S with the above property by SH,A C S, and let ((E T(('
(t5)
SH,A. We will therefore apply Lemma 3.6 with Sproj {(H1/2x)) A(H E Score J
T = ==) A(H1/2)) x E T((515)) and diameter r = 100 (2/1) VC/a. It remains to
check that for qm = Qleft and (1266" I-m: = Gright of T(E's) we have (2 1-m
Ium 2
(17)
(17)
(t7)
10 (1g) 1/1Spros
make sure that the application of Lemma 3.6 is valid.
To show this, recall that Line 14 fails whenever FINDDIVIDER is called, meaning that
9176552) m1
(e5)
qm > R. Thus, we need to verify that the definition of R in Algorithm satisfies R 2
The main step is to lower bound |Sproj] [s(oee) Since (f we can lower bound the above by
C S,
(c5)
(s( D
2 |S| |S SH. 1S T65S
(f')
-T(3)) SSH,A))
2 (1 -] |S )
(by the definition of SH,,
(17)
2 (1 S| (j + (co) 20) f (co/40)a 2m
(by (14))
2 (1 (1-1)) 1-))) (i+ 2)a² (Ea/ 20mm -
(S) = n and basic inequality)
2 (1 (1-1)) -n7) (i (co/ 20)n
(n am)
2 (1-1)m- acon - l
(j S 9/a and < 1/2)
(1 17)n aeσπ Enn
(L < 6n))
2 (1 26,)n 2 n/2
(n S 0.001 and cD 0.01)
Combining with the fact that || [r((':3 S m. we have that (' 10 //Spoo)))) S 20(m/n)r s
(2)) (20/a)r. Recalling that r = 100 (2 (2/n) v) CT a. nj = (co/ 40) and eo = 0.001, the definition of R in Algorithm 1 satisfies R 2 6000 CT /a²) log(1/(cnaa) (20/air 10(1T(5) ( S/oSppr
Knowing that the application of Lemma 3.6 is valid, the lemma then guarantees that either T" or T" contains all of s(i'd) Without loss of generality, we assume this happens for T". We now check Condition 3 for case j + 1 on T":
a² (<o + IS T & (co/ 40) (()) (S
(since T C CTTCT
(1 (17))
(1))
s sa (0000 (f.)) 15 core
(by Lemma 3.6)
<a²(co/4)1T
+
|S
((:)) (5)
++ SH.Al
(by the definition of s(E'j) and a union bound)
(()) 15 (1
+ ry
(by the definition of SH,4)
$ (1++100 20) + f (co/ 40)a 2m + mp
(by Equation 14)
1j+ 20 + l + (co/20) a0)
(since = (Eo/ 400 and n S m)
32

---

(j + 2)a (co/20)m +e.
(16)
Thus Condition 3 is satisfied by T for case j + 1, completing the inductive proof of this lemma.
We now use the lemma conclude the proof of Theorem F.1.
By Lemma F.4, we know that with probability at least 1 - 0.096, the recursion tree generated up to level 9/a, namely Tg/a, satisfies the lemma guarantees. In particular, since (i) by Line 19 in Algorithm 1, the input to any recursive call must have size at least m. am/99 and (ii) Condition I of Lemma F.4 applied to j = m/m, 9/a yields an input size upper bound of O, we can conclude that the execution of the algorithm must have completely terminated by level 9/ax We know by Lemma F.4 that there exists a leaf node in the recursion tree whose input satisfies Condition the third part of the lemma statement. That is, letting j denote the level of that leaf, we have that
a (co/ 20) T( |
+ IS
T (..5 s (j + 1)aa()(a))))) (co/20)n + E.
(17)
The recursion node Ti, starts with that input set T((J) and, before terminating, it may perform some filtering steps. As in the proof of Lemma F.4, will use Lemma F.6 to analyze the "working set" right before the recursive call terminates. we denote by t* the number of filtering steps before termination, Lemma F.6 yields that except with probability 0.01ad, we have
(<((o/40)) + IS (6-9) S (i +
+ & (cn/ 44)
(18)
Note that by Fact F.2, the total failure probability is upper bounded by 0.095 + 0.01ad which is less than d.
We are now ready to prove the first bullet of Theorem F.1. The above inequality implies that
T.
ns = |||| - |S [(--))
2 n L (co/ (j) + 1)a (5o/ (o0440)amm
(by (18))
2 n f (co/20)(j + 2)a²m
2 n f (co/20)(j + 2)a²n
(n 2 am)
2 é (50/2)am
(j S 9/a and 1/2)
2 n f <o 6 cm
(1/2 S 1 - 6p)
2 n f coa(1 f)
(L S fn))
(n () GOa)
(19)
(19) further implies that (T(0)) n S 2 (n o)(1 cua)= 2 n(1 co) 2 (a/2)m (since n 2 amm and eg and a are small), meaning that the set ((fs)) will indeed be returned. This completes the proof of the first bullet of Theorem F.1.
We now move the second bullet. Defining H E E
[XX 1, we need to show that (e*)
/// H S (og"())) We will apply Lemma E.2 to show the bounds in the second bullet, which requires checking that Assumption 3.1 is satisfied by T((=)) Earlier, right below (19), we have already checked that (T(-)) ns 2 (a/2)I((3)) The only remaining condition to check is (i.)) < [S]/a, but this is trivially true since T(62) c I (the original input set to the recursive algorithm) and [T,000) s [S]/a by Definition 1.1. Thus, Lemma E.2 yields that
(0)
/1/3//11/22 -PH
1
Var AX +
1
(
a²
1
1
E
[f(x]]
+
(Var(Y) < E[(Y c for any E R)
a d
33

---

Ri2
x
(c.f. Line 12 of Algorithm 1)
α
a (1)
2 o
log?
(R (0102))))) noting that cp = 0.01)
where the penultimate inequality uses the fact that, if the algorithm terminated, it must be the case that E Ex-r3- [[(X) < C²R2/0² by Line 12 in Algorithm 1. Taking square root on both sides
(e*)
implies that
1 H1/2HH// PH 2 at
1
log
a
The same guarantee holds for |1///HH/2 -P' p also following from Lemma E.2.
Lastly, we check that only return (11/a) sets in the output list. This is true by construction: (i) Line 13 only allows sets to be output if they have size at least ((xm), (ii) there were only m points begin with and (iii) all the leaves have disjoint input sets by Lemma F.4.
F1 Proof of Lemma F.6
We now prove that filtering does remove many inliers using standard martingale argument.
Lemma F.6. Recall the notations and assumptions from Assumption 3.1. Consider execution of COvLISTDECODINGGT with To = 'I' (with II' satisfying the assumptions from Assumption 3.1), and suppose that [Tol 2 C' Ca/(a E log (I/(a6)). Further assume that |S \, Tol S 1.5eo]S] (which is strengthening over Assumption 3.1). Moreover, denote by T. the dataset through the loop iterations of Algorithm 1. Then, with probability least 0.01ad, it holds that
a² (²(o//0)) + \ S a (co/40) + +5 Tol + (co440)T)
simultaneously for all iterations t until the execution of CONLIDDDECODING enters either Line 13 or Line 19.
Proof. We will use the notation of Assumption 3.1 for a single call of Algorithm 1. Denote by t the iteration count. Also define the stopping time fend to be the first iteration when a² (eo 40) IS Tremal > 2ca[S] ( or when the iteration goes into Line 12 or Line 19 instead of Line 16 (that is,
when Ex [1 /2 X)] I C²R2/a" or when fright
gleft > R for the iteration tena). Now,
define A, = a² (co/ (0/40))222 [Tii (tstewa) + IS \ Tmin (f.fcma))-
In order to prove the lemma, we will show that at the first t" (if one exists) such that a (co/ 40) T |S \. T,-| a (co/ 40) + IS Tol + a (c/ (40)[Tal. then A,- a (co (o) + IS Tol a=(so/ Tol as well. Afterwards, we will show that A, is a sub-martingale and use sub-martingale tail bounds to show that the sequence A, remains small over an entire trajectory of [Ta] steps with high probability.
The first step is easy show, since the threshold of a (en/40) + |S \ Tol + ( (eee///001 40) < a a=o (2) Tol + S] < a² /20] 1.5cg/ S| < 2S. where the first incquality by the lemma assumption. Therefore, t" I fend if it exists, meaning that A,. a. a<o/ (0) IS T
Now we need to show that A, I 12 lend- then A441 is by definition equal to A, and thus E[A++1 [Tinn(...mmm |] A Otherwise, have that E[A++1 Tr) is equal to A, plus the expected number of inliers removed minus times the expected number of all points removed by our filter. Since the stopping condition
nub-martingale with respect to the sequence miin If
is not satisfied, we have |S \ T, 26, SS, meaning that Assumption 3.1 continues to hold for Tú, as well as that the other conditions for Lemma E.4 hold. We can therefore apply Lemma E.4 to obtain
E E|4
T: = A. +
Σ #Ešnff
a
ED
f < A.
40
REA,
Summarizing, the above case analysis shows that (At)eN sub-martingale with respect to T Fuiin(t.anal t.ma).
34

---

We note also that for every i, |A, - A++1l I 1 with probability 1. Thus, using the standard Azzma-HHeffdiin inequality for sub-martingales (Fact B.2), we have that for every S [Tol.
Pr A Ao > (co/40)a se- (2/4440))
By a union bound over all E [[Tol], we have
Pr 3t e [m] A, do + a (Eo/ To/
1 |Tole [Tole-
(204/4/)/)))))))) < 0.01a8,
(20)
where the last inequality uses that [To o
log
(1)) for a sufficiently large absolute constant C².
G Applications to Learning Gaussian Mixture Models
In this section, we prove the applications of our result to robustly learning Gaussian mixture models. Theorem 1.4 (Outlier-Robll Robust Clustering and Estimation of Covariances for GMM). Let C' 0 be sufficiently large constant and en > be a sufficiently small constant. Let the parameters a E (0, 1/2), e E (0) and failure probability 8 E (0, 1/2) be known. There is an Ó(m² ) )-tme
log" (d/a5) many e-corrupted samples from an algorithm such that, on input a, 6, and m >> 1og unknown k-component Gaussian mixture Dp=1
a"
Ex) over IR& as in Desinition 1.3, where all Egg 's are full-rank and all Op satisfies Op 2 a and k probability at least 1 8 over the corrupted samples and the randomness of the algorithm, the algorithm returns a list of at most many disjoint subsets of samples {Ti} such that:
unknown to the algorithm, with
For the nd Gaussian component, denote the Sp as the samples in the inlier set S that were drawn from component p. Let ne be the size of Sp. and let lp be the number of points in Sp that the adversary replaced-ny and Ep are both unknown to the algorithm except that E|np] = aym 2 omn for each p and Ep fn S eomm Then, for every Gaussian component p in the mixture, there exists set Ti, in the returned list such that (Ti, S.Spp= 2 (1 -0.0la)( Lp).
For every component p. there is a set of samples Ti, in the returned list such that, defining Hip- =ExwI, [XX]] we have Hi, satisfying || [ 1//1//2,, "H,, - I|1 S (1/a²) log(1/a).
Let E be the (population-level) covariance matrix of the Gaussian mixture. For any components > C(1/a)² (g())))))/ for a sufficiently large constant C,
* p' with [| 1E-1/2(E, the sets Tr, and Tr from the previous bullet are guaranteed to be different.
We show the first two bullets direct corollary of Theorem 1.2 applied to each Gaussian component D = (Nppp Σp) as the inlier distribution. The proof of the final bullet involves some more involved linear algebraic lemmas. Here we give only the high-level proof of the final bullet, and defer the proof of these individual lemmas to Appendix C.
Proof. First observe that, with sufficiently large poly (d, a: log })) samples, with probability at least 1 8/4, the number of inliers np from component p least 0.99am for all components p. We will condition on this event.
Furthermore, noting that in the corruption model defined in Definition 1.3, at most cam points can be corrupted total, this implies that E, I cam < (c/0.99)mi np (since n2 2 0.99am).
Therefore, we apply Theorem 1.2 to all the & Gaussian components, using parameter 0.99a in place of a, e/0.99 in place of e, and failure probability 5/ (4k). This implies that, with union bound, using m (oly 1 /aa log k/8) poly (d, 1 o/ log 188 samples (since k S 1/ax, for otherwise the Gaussian mixture will have weight greater than 1), with probability least 8/4, the two bullet points in the theorem holds for all the Gaussian components, directly guaranteed by Theorem 1.2.
remains to show that the algorithm will return at most &: subsets in its output list. Noting that, across the subsets output by the algorithm for each of the components, there is already a total of (1 (1-0.01a) (n - Ep) points being output. Recall that E, np and E, lp I eam. Thus, in
35

---

the output subsets corresponding to the components, there are total of at least m - (e 0.01)am 2 m 0.4am points (where we used that is bounded by sufficiently small constant. Since (i) there were only m points in the input and (ii) all the output subsets are disjoint subsets of the input, this means that there are at most 0.4am points that can be output in any additional subsets not corresponding to any Gaussian component. However, by Theorem 1.2, any output subset must have size at least 0.5(0.99a)),, and so there cannot be any extra subset output in the list that does not correspond to any Gaussian component. This shows that there can be at most A subsets in the output list.
We turn to the final bullet of the theorem. We will show that any two components p and p' that belong to the same set T; in the output of the algorithm satisfy that | x--1// 5-1/2 a log(1/a). Taking the contrapositive yields the final theorem bullet.
Sp 5 1/2 1|: S
Let H be the second moment matrix of this set, that is, H = [xxx,IXX"] Then H satisfies that
||4 - 2 |F S r and || /2,, H 1/31 < r for S log(La))) by the second bullet point of the theorem. Furthermore, H's is full rank because H is the second moment matrix of a large subset of empirical points of component and thus Condition (L.5) implies that ker (H) is contained in ker (ep)) which is empty since E, is full rank by the theorem assumption.
We will now apply the following result (Lemma C.I) to infer that E, and En must be close, in the sense of the final theorem bullet point. We defer the proof of this lemma to Appendix C.
We will now apply Lemma C.I to Σ En and Σg En, and upper bound the right hand side of the lemma to give the final theorem bullet point.
We claim that the operator norm of Σ 10-1"",, 1-122 is bounded by 1/a, due to the fact that component p has mass at least Indeed, we have that
E (X- - xx( ] = 1 1.5.
E Ep 3 X N-
[X - -1)(=))(--- - -x)) ap X-E, N,
Σ.
0p
This in particular implies that 1, 1/2 3 1 1 I, and hence | | 1-22 1lup 1
oy The same conclusion holds for the component p'. Recalling that r $ (1/a²) log( 1/a), the right hand side of Lemma C.I can be upper bounded by (((1/a)) log (1/a)), thus yielding the final bullet in the theorem, as discussed above.
We end this section with a brief discussion on the proof of Lemma C.I. The lemma states that, if there exists single matrix H that is an approximate square root to both Σ, and Σg, in the sense that ||I H Ht/2||| || and || H Ht/2|| || are both upper bounded, then E, and Eg cannot be too far from each other, in that Σ Eg must also have bounded Frobenius norm. In fact, this can be generalized to the normalized version Σ 1
Σ²)Σ 1/2 for any positive definite matrix Σ.
For simplicity of the discussion, let us assume for now that Σ T. To show Lemma C. a natural first idea is to show that, if I|4 / 1/ 1/2 || bounded, say by some quantity p. then so must be | - 1 by some quantity related to (pp), times the operator norm of Σ, for appropriate scaling. Unfortunately, that is not true: Even for Σ = I, we can have H being infinity in the first diagonal element and Is in the other diagonal elements, and ||I - H || would only be 1 yet H Σ, is infinite in the first dimension. The crucial observation, then, that a slightly weaker statement is true: On an orthonormal basis that depends only on H and not on E, H approximates V in most dimensions, namely d d(0(p") many dimensions. This statement is formally captured by Lemma C.2. Thus, in these dimensions, Eg (in Frobenius norm). In the rest of the dimensions where H does not approximate either Σ, or Σg well, can bound these dimensions' contribution to the Frobenius norm of Σ, Eg simply by maxx||[E]]] lopp |Ee lllo)) times the number of such dimensions, which is small. Combining these bounds yields Lemma C.1 as desired.
can bound the difference between Σ1 and
36


Reviews:
[{"review_id": "6iI1DKQDcD", "reviewer": "Reviewer_ymEk", "summary": "The paper focuses on a fundamental problem in the field of robust statistics, the problem of estimating the covariance matrix of a high-dimensional Gaussian distribution, given access to corrupted samples. The amount of corruption allowed in the setting considered is such that there is not enough information for retrieving an estimate of the unknown covariance matrix. Moreover, prior work has provided strong evidence that even if the algorithm is allowed to output a list of candidate matrices, it is computationally intractable to form a list that contains a multiplicative spectral approximation of the ground truth covariance matrix. This work overcomes the existing lower bounds (by relaxing the measure of closeness between matrices) and proposes a simple and efficient algorithm that outputs a short list of matrices that contains (with high probability) a matrix that is close to the ground truth in relative Frobenius norm. En route, it is shown that the same algorithm, when the samples are drawn from a Gaussian Mixture Model (GMM) corrupted with a small fraction of outliers, clusters the samples according to the covariance matrix of the corresponding generating Gaussian, up to error in relative Frobenius norm. The latter result, combined with existing results from [BDJKKV22], provides a new algorithm for robustly learning GMMs that does not use semi-definite programming.\n\nThe main algorithm recursively computes the empirical covariances corresponding to each sample (in the current set of samples) and measures the variance of these quantities across the samples (variance of the point-wise empirical covariances). If the variance is small, then the point-wise empirical covariances agree and therefore the empirical covariance of the current set is provided to the output. If the variance is large, the current sample set is either filtered (removing outliers) or split in two sets (each of which will be recursively processed in the next steps) according to whether the empirical covariances seem to have multiple modes when projected on the direction of maximum variance.", "questions": "My main question concerns the choice of the relative Frobenius norm. I understand the existence of lower bounds for different metrics, the intuition provided in the paper regarding the relative Frobenius norm, as well as the fact that minimizing the relative Frobenius norm has applications in learning GMMs, but what are other metrics that one might hope to get results for (if any)?", "limitations": "Yes, limitations are adequately addressed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper proposes a simple and efficient algorithm for a fundamental problem in robust statistics. The proposed algorithm also has an application in learning Mixtures of Gaussian distributions, resolving an open problem in the literature. Although the main idea of the algorithm is simple, the analysis is quite delicate and requires a considerable amount of technical work, as well as careful choice of the overall objective (decoding only up to a list and guarantees in terms of the relative Frobenius norm). Moreover, the presentation of the setting, the results, the techniques and the related work are complete and organized and the proofs are split in several lemmas that might be of independent interest.", "weaknesses": "One minor presentation issue is that the paper becomes overly technical in some places. For example, in section 1.2 (and in particular in the beginning of the paragraph), it might be preferable to provide some abstract description of the main approach, instead of (or in addition to) defining the particular quantities that the algorithm uses (like the covariance matrix whose eigenvalues determine whether the algorithm stops). In other parts of the paper, however, providing exact (and therefore technical) claims is indeed important (for example in the theorem statements and the proofs).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work and for your question. There are some variants for the relative Frobenius norm one could consider: 1) currently the relative Frobenius norm is measured with respect to the basis of the output $H$, one could ask for measuring with respect to the true $\\Sigma$ instead, and 2) instead of Frobenius norm (which is already stronger than the spectral norm), one could perhaps ask for even stronger guarantees such as the nuclear norm. While we believe 1) should not be possible in general, it is an interesting direction to investigate other error norms for future work.\n\nFor 1), this should not be possible based on evidence in known SQ lower bounds. Suppose the true $\\Sigma$ is very thin in an unknown (and computationally difficult to detect) direction $v$ and unit variance in all other directions. To ensure $\\Sigma^{-1/2} H \\Sigma^{-1/2} - I$ has a small Frobenius norm, the output $H$ would also have to be (i) small in the direction $v$ and (ii) have roughly unit variance in all other directions. Such an $H$ would contradict known SQ lower bounds. See for example [DKS17,DKPPS21].\n\nFor 2), the naïve bound on the relative nuclear norm blows up our guarantees by a factor of $\\sqrt{d}$. We don’t know if it is possible to remove this $d$-dependence. The algorithm we propose is intrinsically $\\ell_2$ in nature: we consider flattening second moment matrices of samples, and consider the Euclidean geometry of these flattened matrices. The $\\ell_2$ geometry of flattened matrices naturally correspond to the Frobenius norm, and so it is unclear if the current algorithm would also offer any guarantees with respect to the relative nuclear norm (which is $\\ell_1$ in terms of the eigenvalues of the matrices, instead of $\\ell_2$).\n"}, {"review_id": "WOdWLgYV6L", "reviewer": "Reviewer_64Ly", "summary": "Summary: This paper studies the following problem: given a collection of datapoints in $R^d$, of which a small $\\alpha$ fraction (inliers) are guaranteed to be drawn from an unknown Gaussian distribution, and the rest are drawn adversarially (outliers), the goal is approximately identify the distribution. Note that for $\\alpha < 1/2,$ it is not possible to uniquely identify the distribution, but one could hope to output a list of $\\alpha^{-1}$ hypothesis distributions, one of which is correct (this is called list decoding).\n\nThis problem has received significant attention recently from a computational perspective. By now, several algorithms are known for list-decoding in these settings. However, most of them are based on solving large, expensive convex programs (sums-of-squares SDPs) and require $d^{poly(1/\\alpha)}$ running time and sample complexity. While the strongest of these algorithms can recover a list of hypotheses such that at least one of them has a bounded total variation distance from the unknown Gaussian, there are lower bounds showing that such a recovery requires  $d^{poly(1/\\alpha)}$ samples for a wide class of algorithms. \n\nThis paper presents a significantly simpler and faster algorithm ($poly(d/\\alpha)$ time and samples) that is able to generate a list of $O(1/\\alpha)$ hypotheses such that at least one of the covariance matrices is close to the original covariance matrix in relative Frobenius norm. This is necessarily a weaker guarantee than total variation distance, since it bypasses the known lower bounds.", "questions": "Your algorithm removes points one by one in line 16, what is the obstacle in removing a large fraction of the points at each step?\n\nMinor comments:\n1. In Def 1.1, since the adversary choses all the outliers after looking at the distribution, is it not equivalent to the setting of having exactly $\\alpha m$ inliers?\n2. Theorem 1.2, first bullet point -- it's awkward to recall within a theorem statement, I suggest removing the sentence \"Recall ... $\\ell \\le \\epsilon n$\"", "limitations": "Theoretical work. \nSee weakness pointed above.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "\nStrengths:\n+ A fairly simple to describe algorithm based on multi-filtering\n+ avoids solve large convex programs\n+ achieves a reasonable $poly(d/\\alpha)$ sample complexity and running time guarantee, much better than most previous algorithms", "weaknesses": "The main theorems in the paper only talk of recovering the covariance matrix, but not a pair $(\\tilde{\\mu}, \\tilde{\\Sigma})$ where both the mean and covariance are close. Are these guarantees also achievable? If yes, I strongly suggest the authors include such a complete result\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their time and effort. We address their questions below:\n\n  \n\n**(Guarantees on pairs of covariance-mean candidates)**\n\nYes, it is possible to output $(\\hat{\\mu},\\hat{\\Sigma})$ pairs such that, $|| \\hat{\\Sigma}^{-1/2}\\Sigma \\hat{\\Sigma}^{-1/2} - I ||_{F} \\leq \\mathrm{poly}(1/\\alpha)$ (as in the paper) and furthermore that $\\hat{\\mu}$ is a bounded estimate of the true $\\mu$ in Mahalanobis norm with respect to $\\hat{\\Sigma}$: $(\\hat{\\mu} - \\mu) \\hat{\\Sigma} (\\hat{\\mu} - \\mu) \\leq \\mathrm{poly}(1/\\alpha)$.\n\n  \n\nThe idea is simple: after running our list-decoding algorithm for $\\hat{\\Sigma}$, for each candidate $\\hat{\\Sigma}$, whiten the data by $\\hat{\\Sigma}$ and run a list-decoding algorithm for candidate means $\\hat{\\mu}$ (see for example [CSV17, DKK20]).\n\n  \n\nTo show this works, we need to check the main assumption for the list-decoding algorithm for the mean, that the data distribution has bounded covariance. After whitening, the data is distributed with covariance $\\hat{\\Sigma}^{-1/2}\\Sigma \\hat{\\Sigma}^{-1/2}$, which has operator norm $\\le \\mathrm{poly}(1/\\alpha)$ by our list-decoding guarantees.\n\n  \n  \n\n**(Removing single point vs multiple points per filtering iteration)** \n\nSome other filtering-based algorithms in robust statistics filters by flipping an independent coin for each sample (with bias proportional to the score), thus deleting multiple samples for each filter. In these works, this results in slightly better runtime analysis, replacing a factor of $m$ by $d$. However, most of these other works assume a known covariance (or at least, sphericality), which does not apply immediately in our setting. Given that our runtime is $\\tilde{O}(m^2d^2)$, and the sample complexity is $d^2$ resulting in a $d^6$ runtime, the improvement would only bring the runtime down to $d^5$ anyway, so we did not pursue this potential improvement. We emphasize that the focus of this work is getting the first SoS-free spectral algorithm, and not getting the fastest runtime. We hope that the tools and techniques in our paper can inspire future work on optimizing the runtime of the algorithm.\n\n  \n**(Contamination model)** \n\nThe contamination model that we define is slightly stronger in the sense that the adversary can also remove a small fraction of inliers too. Subtractive corruption can introduce biases into the data, and is non-trivial to handle.\n"}, {"review_id": "83r96e1VeN", "reviewer": "Reviewer_Wync", "summary": "This paper studies the problem of robustly estimating the covariance of a multivariate Gaussian distribution in the presence of outliers. Specifically, the authors focus on a list-decodable setting, where the algorithm is allowed to output a small list of hypotheses with the guarantee that at least one of them is close to the target. The authors propose a novel polynomial-time algorithm that efficiently list-decodes the covariance of a Gaussian distribution in relative Frobenius norm under adversarial corruption. ", "questions": " *\n", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very nice paper that tackles an important problem in robust statistics, and the result has direct applications in robustly learning GMMs. The contributions of the paper are novel algorithms that significantly improve the state-of-art algorithm in terms of sample complexity and answer size. The paper is very well written and it is a pleasure to read. In our opinion, this is an important contribution to the literature.", "weaknesses": "The organization of this paper can be improved. In particular, I think the stability section deserves some space in the main paper and \nthe paper could benefit from a discussion section at the end of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their effort and comments. If the paper is accepted, we will move content into the main body as suggested, using the extra page allowed in the camera ready version. "}, {"review_id": "qUwRc99de5", "reviewer": "Reviewer_WZLc", "summary": "This work studies the problem of list-decodable covariance estimation. In this problem, we are given a number of samples, an $\\alpha$-fraction of which were i.i.d. drawn from a Gaussian distribution $N(\\mu,\\Sigma)$. The authors design an algorithm that runs in time $\\mathrm{poly}(d/\\alpha)$ and produces a list of size $O(1/\\alpha)$ such that one element in the list is close to $\\Sigma$ in relative Frobenius norm (up to error $\\mathrm{poly(1/\\alpha)}$).\n\nPrevious work has given an $d^{\\mathrm{poly(1/\\alpha)}}$-time algorithm that achieves the stronger guarantee that one element in the list is close in total variation distance to $N(0,\\Sigma)$ (in this case the list contains tuples of estimates, one for the mean and one for the covariance). While the TVD is related to the error metric the authors consider, the recovery guarantees of the authors do not imply anything about TVD-closeness. This is unsurprising, there are known SQ lower bounds that suggest that for TVD guarantees $d^{\\mathrm{poly(1/\\alpha)}}$ samples are required. The authors show that if one settles for the weaker guarantee of \"only\" relative Frobenius norm error, efficient algorithms, i.e., that run in time polynomial in all problem parameters, are possible.\n\nTheir techniques are similar to the techniques for list-decodable mean estimation with additional technical tweaks to handle the more challenging covariance estimation setting. They also provide an application to robustly learning mixtures of non-spherical Gaussians.", "questions": "You say that your list-decoding algorithm can be used to obtain a \"sum-of-squares-free\" algorithm for robustly clustering non-spherical Gaussians. Does this come with any (theoretical) speed-ups? If yes, I think it would be good to mention what these are.", "limitations": "Maybe I missed this, but I didn't see any statements about limitations in their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "List-decodable covariance estimation is a very natural and important problem. The relative Frobenius norm metric the authors consider is the natural choice here since it captures the \"intrinsic\" scale of the problem induced by the true covariance matrix -- even in the regime where it is not related to the total variation distance.\n\nThe authors show how to extend the techniques for list-decodable mean estimation to this setting. This requires non-trivial modifications since covariance estimation in general is a more difficult and much less well-understood task than mean estimation.\n\nThe paper is fairly well-written and the authors give a nice proof overview in Section 1.2.", "weaknesses": "The relation to IK22 was not clear to me in the beginning, and I believe it would be important to clarify already in the beginning. My main confusion comes from the fact that in Line 49 you say that small relative Frobenius norm is equivalent to small TVD. Then you go on to say that IK22 achieve error in TVD and you in relative Frobenius norm. At this point it seems that the two error guarantees are the same, and it also seems like your algorithm is breaking the SQ lower bound.\n\nOnly later you clarify that for the equivalence to hold the relative frobenius norm needs to be smaller than 1. (You do say in Line 49 that it only holds if the relative Frobenius norm is smaller than a small enough constant but do not specify what this is and how it relates to $\\mathrm{poly(1/\\alpha)}$, your error guarantee.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their effort and feedback, and address their points below.\n\n  \n\n**(Relation to [IK22])** \n\nThank you for pointing out the issue with phrasing. We will emphasize earlier on in the paper that only relative Frobenius error <= 1 would imply TV distance bounds.\n\n  \n\n**(Speed-ups)**\n\nAs mentioned in the statement of Theorem 1.2 and Remark F.2 in the Appendix, the runtime of our algorithm is $\\tilde{O}(m^2d^2)$, where $m$ is the sample size and $d$ the ambient dimensionality. SDP optimization and SoS algorithms are generally much slower (note that in [BDJKKV22] the runtime is polynomial in these parameters with the power being some large constant). We thus expect a sizable speed-up in the SoS-free version that we provide. If the paper is accepted, we will move the runtime discussion into the main body given the extra page.\n"}]

Author rebuttal:
We thank the reviewers for the in-depth reviews, and for the positive assessment of our paper. We are particularly encouraged by reviewers recognizing our paper for 1) tackling a fundamental/important problem in robust statistics (Reviewers ymEk, Wync, WZLc), and 2) proposing a simple and efficient algorithm based on multi-filtering (Reviewers ymEk, 64Ly, Wync, WZLc). We are also pleased that the reviewers found our paper well-written (Reviewers ymEk, Wync, WZLc), and we will take into account the further suggestions to improve certain parts of the presentation, particularly using the extra page available in the camera-ready version, if the paper is accepted.

Meta-review: The paper addresses the problem of estimating the covariance matrix of a high-dimensional Gaussian distribution from corrupted samples in robust statistics. It introduces a simple and efficient algorithm that outputs a concise list of matrices, containing a matrix close to the true covariance in relative Frobenius norm. The algorithm computes empirical covariances for each sample, filters or splits the sample sets based on variance, and provides accurate estimates when projections on the direction of maximum variance show multiple modes in empirical covariances. The approach extends to Gaussian Mixture Models and provides a new algorithm for robustly learning GMMs without using semi-definite programming. While some sections are highly technical, the paper's presentation is organized and comprehensive, and it tackles an open problem in the field with significant contributions. One referee wondered about the choice of relative Frobenius norm over other metrics and potential metrics for obtaining results.
Decision: Accept (spotlight)