Outlier-Robust Sparse Estimation via Non-Convex Optimization
Authors: Yu Cheng
Ilias Diakonikolas
Rong Ge
Shivam Gupta
Daniel Kane
Mahdi Soltanolkotabi
Venue: NeurIPS 2022 Accept (2022)
Keywords: learning theory
high-dimensional robust statistics
non-convex optimization
sparse estimation

Abstract: We explore the connection between outlier-robust high-dimensional statistics and non-convex optimization in the presence of sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges to stationarity yields an efficient algorithm for these tasks. The obtained algorithms are simple, practical, and succeed under broader distributional assumptions compared to prior work.

Outlier-Robust Sparse Estimation via Non-Convex Optimization
Yu Cheng Brown University Providence, RI 02912 yu_ ru_cchnn@bbown.c edu
Ilias Diakonikolas University of Disconsin-Madison Madison, WI 53706 ilias@cs wisc edu
Rong Ge Duke University Durham, NC 27708 ronggedcs. duke. edu
Shivam Gupta
University of Texas at Austin Austin, TX 78712
ddu
shivangupta@utexas edu
Daniel M. Kane University of California, San Diego
Mahdi Soltanolkotabi University of Southern California Los Angeles, CA 90089 Aattaoo@uuc.edt
La Jolla, CA 92093 dakane@cs. ucsd. edu
Abstract
We explore the connection between outlier-robust high- tit-ddimeniinnll statistics and non-convex optimization in the presence sparsity constraints, with a focus on the fundamental tasks of robust sparse mean estimation and robust sparse PCA. We develop novel and simple optimization formulations for these problems such that any approximate stationary point of the associated optimization problem yields a near-optimal solution for the underlying robust estimation task. As a corollary, we obtain that any first-order method that efficiently converges stationarity yields The obtained algorithms are simple, practical,
efficient algorithm for these tasks [ and succeed under broader distributional assumptions compared prior work.
Introduction
In several modern machine learning (ML) applications, such as ML security [NNITIO BNLI2 SKL17 DKK 19a1 and exploratory analysis of real datasets, e.g., in population genetics [RWW 02
PLJDIO LAT 08, DKK 17). typical datasets contain a non-trivial fraction of arbitrary (or even adversarial) outliers. Robust statistics [HRRS86] HR09) is the subfield of statistics aiming to design estimators that are tolerant to a constant fraction fraction of outliers, independent of the dimensionality of the data. Early work in this field, see, e.g., [Tuk60 Hub64 [uk75] developed cample-efficieee robust estimators for various basic tasks, alas with runtime exponential in the dimension.
During the past five years, line of work in computer science, starting with [DKK*16 16 has developed the first computationally efficient robust high-dimensional estimators for a range of tasks. This progress has led to revival of robust statistics from an algorithmic perspective (see, e.g., [K119 DKK for surveys on the topic). In this work, we focus on high-dimensional estimation tasks in the presence of sparsity constraints. To rigorously study these problems, we need to formally define the model of data corruption. Throughout this work, we work with the following standard contamination model.
LRV16).
An implementation of our algorithms is available at http:://jiiib.ooommgggaaaaassaga
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Definition 1.1 (Strong Contamination Model, see [DKK 161) Given a parameter 0 < C < 1/2 and a distribution family 'D on R4, the adversary operates as follows: The algorithm specifies a number of samples n, and n samples are drawn from some unknown D D. The adversary is allowed to inspect the samples, remove up to en of them and replace them with arbitrary points. This modified set of n points then given as input the algorithm. We say that set of samples is e-corrupted if is generated by the above process.
High-dimensional robust statistics is algorithmically challenging because the natural optimization formulations of such tasks are typically non-convex. The recent line of work on algorithmic robust statistics has led to range of sophisticated algorithms. In some cases, such algorithms require solving large convex relaxations, rendering them computationally prohibitive for large-scale problems. In other cases, they involve a number of hyper-parameters that may require careful tuning. Motivated by these shortcomings of known algorithms, recent work [CDGS20 ZSS2 established an intriguing connection between high-dimensional robust estimation and non-conver optimization. The high-level idea is quite simple: Even though typical robust statistics tasks lead to non-convex formulations, may still be possible to leverage the underlying structure to show that standard first-order methods provably and efficiently reach near-optimal solutions. Indeed, (CDGS20 [JS20 were able to prove such statements for robust mean estimation under natural distributional assumptions. Specifically, these works established that any (approximate) stationary point of a well-studied non-convex formulation for robust mean estimation yields a near-optimal solution for the underlying robust estimation task.
In this work, we continue this line of work with a focus on sparse estimation tasks. Leveraging sparsity in high-dimensional datasets is a fundamental problem of significant practical importance. Various formalizations of this problem have been investigated in statistics and machine learning for at least the past two decades (see, e.g., [HTW15] for a textbook on the topic). We focus on robust sparse mean estimation and robust sparse PCA. Sparse mean estimation is arguably one of the most fundamental sparse estimation tasks and is closely related to the Gaussian sequence model [Ty088 [oh17). The task of sparse PCA in the spiked covariance model, initiated in [JohOT], has been extensively investigated (see Chapter 8 of [HTWI5] and references therein).
In the context of robust sparse mean estimation, we are given an e-corrupted set of samples from a distribution with unknown mean E Rd where μ is k-sparse, and we want to compute a vector ti close to fs. In the context of robust sparse PCA (in the spiked covariance model), we are given an e-corrupted set of samples from distribution with covariance matrix I + pvn"" where v E Rd k-sparse and the goal is to approximate e. worth noting that for both problems, we have access to much fewer samples compared to the non-sparse case (roughly O(k" log d) instead of ((d)). Consequently, the design and analysis of optimization formulations for robust sparse estimation requires new ideas and techniques that significantly deviate from the standard (non-sparse) case.
1.1 Our Results and Contributions
We show that standard first-order methods lead to robust and efficient algorithms for sparse mean estimation and sparse PCA. Our main contribution is to propose novel (non-convex) formulations for these robust estimation tasks, and to show that approximate stationarity suffices for near-optimality. We establish landscape results showing that any approximate stationary point of our objective function yields a near-optimal solution for the underlying robust estimation task. Consequently, gradient descent (or any other methods converging stationarity) can solve these problems.
Our results provide new insights and techniques in designing and analyzing (non-convex) optimization formulations of robust estimation tasks. Our formulations and structural results immediately lead to simple and practical algorithms for robust sparse estimation. Importantly, the gradient of our objectives can be computed efficiently via small number of basic matrix operations. In addition to their simplicity and practicality, our methods provably succeed under more general distributional assumptions compared to prior work.
For robust sparse mean estimation and robust sparse PCA, our landscape results require deterministic conditions on the original set of good samples. We refer to these conditions as stability conditions (Definitions [ and 2.2 formally defined in Section D At a high level, they state that the first and second moments of set of samples are stable when any e-fraction of the samples are removed. These stability conditions hold with high probability for a set of clean samples drawn from natural families of distributions (e.g., subgaussian).
2

---

For robust sparse mean estimation, we establish the following result.
Theorem 1.2 (Robust Sparse Mean Estimation). Let 0 < < to for some universal constant en and let 5 > e. Let G be set of n samples that is (k, e, 0-stablee (per Definition 2.7 w.E.. a distribution with unknown k-sparse mean I E Rdd Let S (X,) be e-corrupted version G There is an algorithm that on inputs S. k. 6, and ö, runs in polynomial time and returns a k-sparse vector R& such that 1|77 2llz I (5))
We emphasize that a key novelty of Theorem 1.2 is that the underlying algorithm is first-rder method applied to a novel non-convex formulation of the problem. The major advantage of our algorithm over prior work [BDLSI7] DKK + 19b] is its simplicity, practicality, and the fact that it seamlessly applies to a wider class of distributions on the clean data.
As we will discuss in Section when the ground-truth distribution D is subgaussian with unknown k-sparse mean E IR and identity covariance, a set of n = s2(k² log d/=²) samples drawn from D is (k, e, -tabbe (Definition 2.1 with high probability for 5 = ( v [oe(]/ It follows as an immediate corollary of Theorem 1.2 that, given an e-corrupted set of samples, we can compute a vector f that is O6)) = (ollv//oo((1)) (1/e)) close to the true mean μt This sample complexity matches the known computationallstaiie the concentration assumption on the clean data and obtain qualitatively similar error guarantees.
lower bounds [DKS17 [B20]. More generally, one can relax
Next we state our main result for robust sparse PCA.
Theorem 1.3 (Robust Sparse PCA). Let < S 1 and O <E< 6o for some universal constant eo- Let G+ be set of samples that is (ki, e, 8)-sballe (as in Desinition 2.2 w.r.l. centered distribution with covariance Σ = I + pvv for unknown k-sparse unit vector v E Rd. Let S = (X;) be an 6-corrupted version of G There is an algorithm that on inputs S, k; and 6, runs in polynomial time and returns a unit vector u. E IRd such that ||um" - -vo 1| ((V5/p/)) p))
Interestingly, our algorithm for robust sparse PCA a first-order method applied to a simple convex formulation of the problem. We view the existence of a convex formulation as an intriguing fact that, surprisingly, was not observed in prior work.
As we will discuss in Section 4 when the ground distribution D is centered subgaussian with covariance > = 1 + pvv" T_ for an unknown k-sparse unit vector v E Ed a set of n = S2 log d/e²)
samples drawn from D is (ki, e, d)-stable (Definition 2.2p with high probability for d = O log (I/e)). Therefore, our algorithm outputs a vector that is O( M<ve e log(1/e)/p) close to the true direction v. The sample complexity in this case nearly matches the computational-statiiiiin (1k2 log d/e²) (BR13) which holds even without corruptions. While the error guarantee of our algorithm is slightly worse compared to prior work [BDLS17 DKK for Gaussian data (we get 0(/0/p) rather than (()p)),, we note that our algorithm works for broader family of distributions.
log
lower bound of
Prior Work on Robust Sparse Estimation. We provide a detailed summary of prior work for comparison. [BDLS17] obtained the first sample-efficient and polynomial-time algorithms for robust sparse mean estimation and robust sparse PCA. These algorithms succeed for Gaussian inliers and inherently use the ellipsoid method. The separation oracle required for the ellipsoid algorithm turns out to be another convex program - corresponding to an SDP to solve sparse PCA. As a consequence, the running time of these algorithms, while polynomially bounded, is impractically high. [LLC19] proposed an algorithm for robust sparse mean estimation via iterative trimmed hard thresholding, which can only tolerate sub-constant fraction of corruptions. [DKK 19b] gave itcrative spectral robust algorithms for sparse mean estimation and sparse PCA. These algorithms are still quite complex and are only shown to succeed under Gaussian inliers.
1.2 Overview of Our Approach
In this section, we give overview of our approach for robust sparse mean estimation. At a very high level, we assign a nonnegative weight to each data point and try to find good set of (1 - e)n samples. The constraint on the weight vector is that it represents at least a (fractional) set of (1 e) -)-portion of the input dataset. Formally, given n datapoints (X 2- the goal is to find a weight vector w E T
For two sets of samples S and I', we say S is an e-corrupted version of if (S] [1' and |S \ 71 & dSs.
3

---

such that Miw = Ei W is close to the true mean Jr. The constraint on w is that it belongs to all k-sparse unit vectors v, then fww must be close to μ.. Unfortunately, it is NP-Hard to find the sparse direction with the largest variance. To get around this issue, [BDLS17) considered the following convex relaxation, minimizing the variance for convex combinations of sparse directions:
1 Vi A n,e { E R ||w|| 1 and 0 I wa (1 (1-c)m
which is the convex hull of all uniform distributions over subsets S S [n]] of size |S| (1- (1--e)m e)n.
[mm)) denote the weighted empirical covariance matrix. It is well-known that if one can find w E An,e that minimizes the weighted empirical variance v " for
Let Enp = E, W;(x; Mm:)
min W
max
(A (A.In))
(1)
Given the optimal A can be found using semidefinite programming (SDP). ZSS0 observed that any stationary point w of ( gives a good solution for robust sparse mean estimation. However, solving ①T) requires convex programming to compute the gradient in each iteration. As explained in the proceeding discussion, our approach circumvents this shortcoming, leading to a formulation for which each gradient can be computed using only basic matrix operations.
In this work, propose and analyze the following optimization formulation:
min f(w)
[[ 1 subject to An.e.
where F the Frobenius norm of the k²2 entries A with largest magnitude, with the additional constraint that these k²2 entries are chosen from A rows with & entries in each row.
We prove that any stationary point of fww yields good solution for robust sparse Here we provide a brief overview of our proof (see Section 3 for more details). Given a weight vector w. we show that if
estimation.
good solution, then moving toward w* (the weight vector corresponding to the uniform distribution on the clean input samples) will decrease the objective value. Formally, we will show that, for any 17 1,
- = (1 - Ew, + M + +11 - (M - -lur (HHo Mw )T
We can then take || F norm on both sides (after subtracting L) and show that the third term can be essentially ignored. If the third term were not there, we would have
f((1 - m) + mwn) = || [1 + -
- I11
S (1 m> Fll + +n/ 1 (1- (w-)))(ww) + nf(w")
Therefore, if w is bad solution with f(w) much larger than f(w*), then w cannot be a stationary point because f decreases when we move from w (1 - 17) + +n"*.
Remark 1.4. The technical overview for robust sparse PCA follows similar high-level approach, but is somewhat more technical. It is deferred to Section
Roadmap. In Section we introduce basic notations and the deterministic stability conditions that we require on the good samples. We present our algorithms and analysis for robust sparse mean estimation in Section 3 and robust sparse PCA in Section In Section we evaluate our algorithm on synthetic datasets and show that it achieves good statistical accuracy under various noise models.
2 Preliminaries and Background
Notation. For a positive integer n, let [n]] = {I....,, n1..
For a vector v, we use ||v || || and ||e||oo for the number of non-zeros, the L, (,, and foo norm of respectively. Let / be the identity matrix. For a matrix A, we use |[Allg ||A|]] p. tr(A) for the spectral norm, Frobenius norm, and trace of A respectively. For two vectors x, y. let T denote their inner product. For two matrices A, B, use A + B (A(AAT) B) for their entrywise inner product. A matrix A is said to be positive semidefinite (PSD) if Ax 2 0 for all We write A - B iff (B- A) is PSD.

---

For vector w E R", let diag(w) E Rux= denote a diagonal matrix with on the diagonal. For matrix A R=x= let diag(A) (A) R" denote a column vector with the diagonal of A. For a vector E IR and a set S _ [d], we write vg Id for a vector that is equal on S and zero everywhere else. Similarly, for matrix A E Rd and set S _ ([d] x [d]), write Ag for matrix that is equal to A on S and zero everywhere else.
For vector v, we define ||=||,,c max|s|= || to be the maximum ε--norm of any k entries of v. For matrix A, we define || F,x² to be the maximum Frobenius norm of any k2 entries of A. Moreover, we define [|A| Ir to be the maximum Frobenius norm of any k² entries with the extra requirement that these entries must be chosen from & rows with & entries in each row. Formally,
||A|| pA
max Q k2
AQll
and ||
max Σ ||::l2, where A, is i-th row of A (2) = SS
Sample Reweighting Framework. We use for the number of samples, d for the dimension, and for the fraction of corrupted samples. For sparse estimation, we use for the sparsity of the ground-truth parameters. We use G for the original set of n good samples. We use S = G U B for the input samples after the adversary replaced e-fraction of G", where C G is the set of remaining good samples and B is the set of bad samples (outliers) added by the adversary. Note that [G] = (1 c)n and B = cn.
Given samples XI,...; X,, write X Rdxn the sample matrix where the i-th column is X, For a weight vector w E R.,, we use Por = Xw Σ; Xo;X; ; for the weighted empirical mean and Ln = X diag(w).X - Par D. w;(X, ) (ww) - for the weighted empirical covariance. Let An, be the convex hull of all uniform distributions over subsets S S [ni] of size |S] (1 e)m: An, (w E R" ||w|| = and 0 w; ----
(I-c)m Vi), In other words, every
w E An,e corresponds to fractional set of (1 - c)n samples. We use w" to denote the uniform distribution on G' (the remaining good samples in S).
Deterministic Stability Conditions. For robust sparse mean estimation and robust sparse PCA, we require the following conditions respectively.
Definition 2.1 (Stability Conditions for Sparse Mean). set of n samples G = =X.) is said to be (ks e, 8) -ttable (w.rt. distribution with meun (1) iff for any weight vector w E An,20 have I|w - 1112, S 8 and [|S - 11 S 66//e, /e, where pw and En are the weighted empirical mean and covariance matrix respectively, and the 11,,1 norm is defined in Equation 2
Definition 2.2 (Stability Conditions for Sparse PCA). A set of n. samples G* = (Xi) is (k, 6)- stable (w.Et. a centered distribution with covariance I + pvu' itf for any weight vector E An,20 M (I + pev" Ill p:pa I 58, where M E, W,X. and the |1:e norm is defined in Equation
First-Order Stationary Points. We give a formal definition of the notion of (approximate) first- order stationary point that we use in this paper.
Definition 2.3 (Approximate Stationary Points). Fix a convex set K. and a differentiable function f. For 2 O, we say that x E K. is a 7-stationary point of f iff the following condition holds: For any unit vector u where x + onu E for some a > O, we have u f 2 -
We note that the objective functions studied this paper are not everywhere differentiable. This is because, taking the ||- norm an example, there can be ties in choosing the largest X² entries. When the function f is not differentiable, we use V informally denote an element of the sub-differential. We will show in Appendix that, while f is not differentiable, does have a nonempty subdifferential, as it can be written as the pointwise maximum of differentiable functions.
3 Robust Sparse Mean Estimation
In this section, we present our non-conver approach for robust sparse mean estimation. We will optimize the following objective, where 11- is defined in Equation (2)
min fw) w
|| - -
subject to w An.
(3)
5

---

We will show that the objective function (3) has no bad stationary points (Theorem 3.1) In other words, every first-order stationary point of yields a good solution for robust sparse mean estimation.
Our algorithm is stated in Algorithm As a consequence of our landscape result (Theorem 3.1 we know that Algorithm T works no mater how find stationary point of f (hecause any stationary point works), so we intentionally did not specify how to find such point. As a simple illustration, we show that (projected) gradient descent can be used minimize f. The convergence analysis and iteration complexity are provided in Appendix
Algorithm 1: Robust sparse mean estimation.
Input: k > 0, 0 < c < co. and an e-corrupted set of samples (X1) drawn from a distribution with k-sparse mean μ..
Output: a vector that is close μs.
1: Find a first-order stationary point w E An, of the objective min f(w) = 1|_ I F
2:
Return jū = (Ww)Q where Q is a set of l entries of Hou with largest magnitude.
Formally, we first prove that Algorithm can output a vector jú E IRd that is close to is in 11-12,, norm, as long as the good samples satisfies the stability condition in Definition 2.1
Theorem 3.1. Fix > 0, 0 <<< < 6g, and 5 > 6. Let G be a set of n samples that is (k, 6, ---sbblle (as in Definition 2.1 w.r.. a distribution with unknown k-sparse mean PA E IRd. Let S = (x:) be
an e-corrupted version Gf. Let f(w) = =I[E - I Letr-
12 3/2). Then, for any W E An,e that is y-stationary point of fw), we have || - -1112, 2 = O()).
Once we have a vector Phe that is Cloose to μ in I1-112, norm, we can guarantee that a truncated version of Per (the output Ji of Algorithm D is (15)-llose to j in the 62-nor::
Lemma 3.2. Fix two vectors I, y with ||=||, S k and | vll2, 2,k S 8. Let be vector that keeps
the k entries of with largest absolute values and sets the rest to O. We have ||x - 2|12 S v55.
Theorem follows immediately from Theorem 3.1 and Lemma
We apply Theorem 1.2 to get end-to-end result for subgaussian distributions. We show that the required stability conditions are satisfied with a small number of samples.
Lemma 3.3. Fix k 0 and 0 < Eg- Let G* be a of samples that are drawn i.i.d. from subgaussian distribution with mean μ and covariance I. If n = 22kk2 log d/e²), then with probability at least exp(-S2(12 log d)), G is e,,,e,) (,,,tbl (as in Definition 2.1 for 5 O (og(l//())))
Combining Theorem 1.2 and Lemma 3.3. we know that given an e-corrupted set of O(k² log d d/e²) samples drawn from subgaussian distribution with k-sparse mean ju, the output of Algorithm is O(ey/og (ogg())))-cloo)) to y in f--om.m
In the rest of this section, we will prove Theorem 3.1 Omitted proofs in this section are in Appendix
We start with some intuition on why we choose our objective function 33) We would like to design f(w)= g( - I) to satisfy the following properties
1. g(w,. - 1) is an upper bound on v T (En, - I)o for all k-sparse unit vectors v E IRd, This way, a small objective value implies that ||w #ll2,2 is small.
2. ((Ew.- --] I) is small for w² (the uniform distribution on G). This guarantees that a good w exists.
3. Triangle inequality on g. This allows us to upper bound the objective value when we move w toward w* by the sum of g(-) of each term on the right-hand side:
E(1-n)u-t - I - - (Ew I) + m - I) + 17(1 - ( - Hww (p pw )T
4. g(uu]] is close to g(v where u keeps only the i: largest entries of u. We want to approximate / in ||. 12.k norm, intuitively g(E.. I) should depend only the largest i entries of (NW μt).
'Witoout loss of generality we can assume that e is given to the algorithm. This is because we can run a binary search to determine e: if our guess of e is too small, then the algorithm will output w whose objective value f (w) is much larger than it should be.

---

Our choice of f(w) -I)= ||
F1 is motivated by (and satisfies) all these properties.
Lemma 3.4. Fix RRadd We have 10 T Au) s
any k-sparse unit vector Rd.
Lemma 3.5. For any vector R. |oo0 T r,r, 1012,x
We now continue to present key technical lemmas for proving our main structural result (Theorem) 3.1 Lemma 3.6 gives the weighted empirical covariance for convex combination of two weight vectors. Lemma 3.6. Fix n samples XI,...: Xn E RRd, Lef W. 10 E Rn" be two non-negative weight vectors with to | 1. For any a, 3 2 0 with 8 letting w aow + fii,, have
Eng am 3E a pa) pm))
Proof. Because w = am + 30 and fwu is linear in w, we have Mww = afw + Bpg. The lemma follows from the following calculations:
En Σ w,X,XX
Σ O. X,X; apTp B00xiX - -Baal
Mwll
+ aptHo + Spart (apw + 8pp)(aps - Bpa)
aLw + BEg aB( (a) pa)
The last step uses a - =² 3 = 0 + 1.
Let w denote the uniform distribution on G, i.e., w (I-c)m i E G and wi otherwise. By Lemma 3.6 for any w. if we move toward w", we have
E(1- -(
- -) + m + tn(11 (p pwr (poo Mmn ) T
We will show that we can essentially ignore the last rank-one term using Lemma 3.7 Lemma 3.7. Let G be (k, (,,5,,))sss --ttbble of samples with respect the ground-truth distribution with 0 < 6 S 6. Let S be an e-corrupted version of G Then, we have
(e Mw (pw pw. I 4e (11 F + 0(82/))
We are now ready to prove our main result (Theorem 3.1
Proof of Theorem 3.7 Fix any weight vector E An.e- We will show that if w is a bad solution, then f(w) decreases moves toward w", so w cannot a stationary point.
Let e1 be the constant in O() in Lemma 3.7
By Lemma
3.7 if Ilwl - 11l12, 2 cz for a sufficiently
large constant C2, then ||
7 F.,
2))))
By Lemma 3.6 E(1 gg)o I (1- ()- -1(E---I++ +n I)+ m Hw HHr Hw TT.
Using the triangle inequality for 11,11 have
E ypu IllEAA S (1 7)1 Fl
nl|2 1ll + 711 7m) pho (iw pw J TEA.
We know that (E Fl.. by the stability condition in Definition 2.1 By Lemma 3.7 and D Ill = (2(62/e)) we can show that for all 0 < n < 1,
f((1 - w1 + mwu") || ()= - 7 F.A.R
$ (1 - 7) Ew - 111 + Ida + 4en (| I Allat + +
S 17 + +4er)ll T1l + (4c) + n)nd
S (1 - 1 - -1llERA = (1 f))
7

---

The last step uses (2 - 4e) _ 2 2 (4c) + +1 which holds if S 1 10 and c3 2 164 ci + 40.
w" - It follows immediately that cannot be stationary point. Let || - and h 1) || I w
We have w hu (1 + E An.e because An.e convex. Since Iu- w|l2 0 ((ve/n)
Vf(w) lim u
f(w+th))-
(n/21/(w) I タ
lim
| Iw--wl1 S -nn 3/2).
h-0 h
By Definition
2.3 know w cannot be y-stationary point of f for some 0(1112226
4 Robust Sparse PCA
We consider a spiked covariance model for sparse PCA. In this model, there is a direction o E R with at most & nonzero entries. The good samples are drawn from a ground-truth distribution with covariance Σ = + pou', where p >> O is a parameter that intuitively measures the strength of the signal. We consider the more interesting case when p S 1 (if p is larger the problem becomes easier).
To solve the sparse PCA problem, we consider the following optimization problem, where My. E; " and || p,2N* === 5
min ((w) M 71l / subject to w E An,e.
(5)
The objective function minimizes the Frobenius norm of the largest 2k entries of reweighted second-moment matrix Ma. Note that f(w) is actually convex in w, because the matrix My is linear in w and the ||-|| p.2.2 norm is convex.
Let R be the support of vo T. Intuitively, the A?2 entries in R could be large due to spiked covariance. By minimizing the norm of the largest 24 entries, hope to make the entries outside of R very small. Our algorithm is given in Algorithm
Algorithm 2: Robust sparse PCA.
Input: k > 0, 0 < c < Ep. and an e-corrupted set of samples (X,) drawn from a distribution with covariance + puv" T for a k-sparse unit vector v. Output: vector that is close to
1: Find a first-order stationary point w E An, of the objective min, f(w) = || - F
2: Let A = M.. T. Let Q be the 1.2 entries of A with largest magnitude.
3: Return и the top eigenvector of (Aq + AT)-
Theorem 4.1. Let 0 < < 2 1, 0 < co, and 8 > Let G be set of samples that is (k: 6)- stable (as in Definition 2.2 w.E.f a centered distribution with covariance I + +pv" for an unknown k-sparse unit vector
d Let S (X,) be an e-corrupted version of G Algorithm outputs "wu"" ve" || = ((/pp))
a vector u such that
Theorem 1.3 is an immediate corollary of Theorem
We can apply Theorem 4. to get end-to mod-to-end result for subgaussian distributions. Algorithm requires the stability conditions (Definition 2.2) of the original good samples G* We show that these conditions satisfied with a small number of samples.
Lemma 4.2. Let O < p S 1 and 0 < c < cy. Let be a centered subgaussian distribution with covariance I + pvo' T for k-sparse unit vector u E Rd. Let G* be set of Ω(k22 log d/ samples drawn from D. Then then with probability at least 1 - exp(- log d)), G is (ki 6, 6)- stable (as in Definition 2.2 w.r.l. D for = O(e log(1/e)).
Combining Theorem 4.1 and Lemma 4.2 given as input an e-corrupted set of n (k(k2 log d/ e²)
samples drawn from centered subgaussian distribution with covariance + pue Algorithm returns vector u with ||uu" -vo" O(ve log(1/e)/p)
We defer the proofs of Lemma 4.2 and Theorem 4. to Appendix B and give an overview of the proof
of Theorem 4.1
8

---

Proof Sketch of Theorem 4.1 We can use the stability conditions to upper bound the optimal objective value: note that for w* (uniform distribution on the remaining good samples). we must
have M - (T+ puv)
F,212 I å by the stability conditions, therefore || 7 2, I
M ppo (l + || F:2x S p Because the objective function f(w)) is convex,
any stationary point w must be globally optimal and satisfies fww S p + 6.
Fix a stationary point w and let A = M, I. Let R be the support of vv" and let Q be the set of k? largest entries of A. The stability conditions implies for any w, the projection in the direction must be large (formally v Au 2 8). Because the objective function measures the norm of the largest 21 entries of A and it not much larger than the norm of the largest 1.2 entries, we can argue that An and Aq are close, so v Aqu
(()).
Now Aq is a matrix with Frobenius norm at most p + while T Aqe 2 O()). Together these imply that the norm of Aq in direction orthogonal to ve' T is at most O( (pvp)), and then by standard matrix perturbation bounds we know the top eigenvector of (Aq + AQ) is O( ((///p) close to v.
5 Experiments
We perform an experimental evaluation of our robust sparse mean estimation algorithm on synthetic datasets with a focus on statistical accuracy (éy-distance between the output and the true sparse mean). We evaluate our algorithm (Sparse Gradient Descent, Sparse GD) on different noise models, and compare it to the following previous algorithms:
oracle, which told exactly which samples are inliers, and outputs their empirical mean, the robust sparse mean estimation algorithm RME_sp from [DKK+195 19b),
NP (Naive Pruning), which removes samples far from the median and output the mean of the rest, RANSAC, which randomly selects half of the points and computes their mean. One solution is preferred to another if it has more points in a ball of radius O(vd) around it.
For algorithms that output non-sparse vectors, we take the largest entries before measuring the lz distance to the true mean. We evaluate the algorithms on various noise models:
Linear-hiding noise. The inliers are drawn from I). Let S be size k set. Then, half the outliers are drawn from ((1s, s, I) and the other half are drawn from N/0, 2 Is).
Tail-flippig noise. This noise model picks a k-sparse direction and replaces the fraction of points farthest the -u u direction with points in the + direction.
Constant-bias noise. This model adds a constant to every coordinate of the outlier points. In Figure 3 we add 2 to every coordinate of every outlier point.
We ran our experiments
computer with 1.6 GHz Intel Core i5 processor and 8 GB RAM. We built on the codebase of [DKK* 19b] 4 and implemented our new algorithm for the experiments. For each pair of algorithm and noise model, repeat the same experiment 10 times and plot the median value of the measurements. We shade the interquartile region around the reported points in the figure confidence intervals.
1000. 40, eps 0.1, linear hiding
300,
5000, eps 0.1, is hiding
orwcle sp
oracle
RME sp
NP
NP
1.2 loss
RANSAC
1006
RANSAC
Sparse CD
Sparso CD
(a) Fix the sparsity & and change the number of samples n.
(b) Fix n and change the sparsity k.
Figure 1: The performance of various algorithms under hiding noise. Notably, when the number of samples n or the sparsity is small, our algorithm Sparse GD outperforms RME_sp.
Available at: http://gitthb..com//sssututttttu sparsesssssssss_seeeeereeeee_eee sacee_eea_eeeee | MIT license

---

10. 1.
O.1, Noise tail flipiing
d 10, k 1. 5000, Noise tail flipping
ocacle
RME
loss
RANSAC
oracie
Sparas CD
RME
64.
RANSAC
Spurse
cps
(a) Fix the sparsity & and change the number of samples (b) Fix ne, k and change the fraction of corruption
Figure 2: The performance of various algorithms in the tail-flipping noise model.
d= 300 k= 10. eps = 0.1, Noise constant +2 biased
d 300. p 50000 eps 0.1. Noise is constant +2 biased
oracie
RME sp
1.2 loss
oratle
1.2 loss
RANSAC
sp
Sparse CD
NP
01-
Sparn CI
(a) Fix the sparsity Is and change the number of samples n.
(b) Fix n and change the sparsity
Figure 3: The performance of various algorithms in the constant-bias noise model.
Our experimental results are summarized in Figures I and For the linear- hiding and constant-bii noise models, we run two experiments: 1) fix the sparsity k and change the number of samples n, and 2) fix n and change k. For the tail-flipping noise model, we run two experiments: 1) fix the sparsity and change the number of samples n,, and 2) fix k and and change the fraction of corruption e.
In terms of statistical accuracy, our algorithm (Sparse GD), outperforms the filter-based RME_sp algorithm [DKK 19b] in the linear- hiding noise model when the number of samples or the sparsity small, as shown in Figure I Our algorithm matches the performance of RME_sp under the tail flipping and constant- biis noise models, as shown in Figures 2 and 3.
Matching our theoretical results, our Sparse GD algorithm has accuracy (cc/log(1/66 and is within a constant factor of the (l(e//og(1/e) worst-case performance of oracle. In contrast, the naive algorithms NP and RANSAC both incur error that scales as evk. The tail-flipping noise (Figure 2 illustrates that /2ee/I(lg log(1//)) (1/e)) error can occur no matter which algorithm is used (including oracle). because e-fraction of the original good samples was removed.
Acknowledgments and Disclosure of Funding
Yu Cheng is supported in part by NSF Award CCF-2307106. Ilias Diakonikolas is supported by NSF Medium Award CCF-2107079, NSF Award CCF-1652862 (CAREER), NSF Award AiTF-2006206, a Sloan Research Fellowship. and a DARPA Learning with Less Labels (LwLL)) grant. Rong Ge supported by NSF Award CCF-1704656, NSF Award CCF-184511 (CAREER), NSF Award CCF-1934964, a Sloan Research Fellowship. and a Google Faculty Research Award. Shivam Gupta supported by NSF Award CCF-2008868, NSF Award AiTF-2006206, and the NSF AI Institute for Foundations of Machine Learning (IFML). Some of this work was done while Shivam Gupta was visiting the University of Wisconsin-Madinn
Daniel M. Kane supported by NSF Award CCF-1652862 (CAREER), NSF Award CCF-210755 from CasperLabs. Mahdi Soltanolkotabi supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship. NSF Award CCF-1846369 (CAREER), NSF Award CCF. 1813877, DARPA Learning with Less Labels (I (LwL.L. and Fast Network Interface Cards (FastNICs) grants, and Faculty Research Awards from Google and Amazon.
Sloan Research Fellowship. and a grant
10


Reviews:
[{"review_id": "u5x4jGYWQU", "reviewer": "Reviewer_jPtK", "summary": "Algorithmic robust statistics is concerned with building efficient algorithms for statistical estimation problems when the observed data contains adversarial or heavy-tailed noise. For the canonical problem of mean estimation, a single grossly corrupted data point can completely invalidate the performance of the sample average as a natural estimate of the population mean. In the problem of mean estimation under the strong contamination model, one observes $n$ data points generated in the following manner:\n\n1. First $n$ ``good'' data points are generated from the true underlying distribution $D$.\n2. An adversary then inspects the generated samples and corrupts an arbitrary set of $\\epsilon n$ points in a completely unconstrained manner.\n\nGiven a corrupted dataset  $X = \\left\\\\{x_i\\right\\\\}_{i = 1}^n \\subset \\mathbb{R}^d$, the goal is to optimally recover the mean of $D$ generating the good data points. With no further assumptions, computationally efficient algorithms have been designed achieving the information theoretically optimal rate.\n\nThe paper considers the sparse setting where the mean, $\\mu$, of $D$ is $k$-sparse. In typical sparse estimation problems, this usually allows an improvement of the sample complexity to depending polynomially only on $k$ and poly-logarithmically on $d$. The paper relies on the existence of a stability condition introduced in prior work on building robust estimators in the sparse regime. However, unlike previous algorithms exploiting this condition which often utilize intricate filtering techniques or solve large convex programs, the algorithm proposed in the paper is a simple gradient descent on a natural non-convex objective. Furthermore, they show that any approximate stationary point of this non-convex objective is can be used to obtain a good estimate of the mean. \n\nIn the dense setting, the stability stability condition required is the existence of a set of well-spread weights, $\\left\\\\{w_i\\right\\\\}_{i \\in [n]}$ such that the empirical covariance of the data points weighted by $w$, $\\Sigma_w$, is small in spectral norm. Furthermore, any set of weights guaranteeing this condition can be used to get a good estimate of the mean. Formally, one would like a $w$ such that $f(w) = \\lVert \\Sigma_w\\rVert$ is small. While prior algorithms constructed a good set of weights through complex filtering techniques or by solving large convex programs, it was then subsequently shown that all approximate stationary points of $f$ also produce such a set [ZJS 20]. Thus, one can perform robust mean estimation by simply running gradient descent on the function $f$ without resorting to elaborate approaches from prior work.\n\nThe main contribution of the paper is the identification of a novel stability condition for the sparse regime where an analogously defined optimization function $f$ has similar nice properties; that is, its approximate stationary points yield a valid solution to our mean estimation problem. For sparse mean estimation, the specific function chosen by the paper is that $f(w) = \\lVert \\Sigma_w - I \\rVert_{F, k, k}$ where $\\lVert A \\rVert_{F, k, k}$ denotes the maximum Frobenius norm of the matrix $A$ restricted to any $k^2$ entries with the constraint that these $k^2$ entries must be chosen from $k$ distinct rows with $k$ entries from each row. The paper also proposes a variant for Robust Sparse PCA. Finally, the paper shows that under nice distributional assumptions such as sub-Gaussianity, such a stability condition holds with high probability. \n\n**** POST REBUTTAL UPDATE ****\n\nI acknowledge the authors' response and have decided to retain my current evaluation. While the new sparsity encouraging objective functions are interesting, the technical contributions seem somewhat limited in comparison to landscape results already known in the dense setting preventing me from strongly recommending this paper for acceptance. ", "questions": "It would be great if the authors could have a discussion on when the stability conditions required by the are satisfied beyond the settings where efficient approaches to efficient sparse estimation are already known.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper introduces a natural objective for robust sparse estimation and show that it recovers previously known results in this domain. Furthermore, the analysis is simple and easy to follow. Having said this, one of the main drawbacks with the result is that it is not clear how such a stability condition would hold for distributions not satisfying strong tail bounds for which we already know good estimators. Ensuring such a condition is currently the main bottleneck in extending prior approaches for robust sparse estimation to other potentially heavy-tailed distributions. Secondly, the condition itself is not significantly insightful as it is well-known that exploiting sparsity essentially involves reducing the search space for violating behavior to a smaller set of sparse directions which has underlain all prior approaches for this problem. \n\nDespite this, the paper makes a nice contribution to the growing literature on robust sparse estimation. Furthermore, any subsequent work establishing such a stability condition for more general distributions will now immediately yield a simple gradient descent based algorithm achieving optimal performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "C6d6LRI_4mh", "reviewer": "Reviewer_y6mC", "summary": "This paper focuses on sparse mean and covariance estimation in corrupted datasets. In particular, the authors focus on the strong contamination model of Diakonikolas et al ‘16, where an adversary is allowed to arbitrarily corrupt an $\\epsilon$-fraction of points after observing the sample. In this regime, the authors develop new nonconvex optimization programs for sparse mean and covariance estimation. The stationary points of these programs recover good estimates of the underlying mean under generic stability conditions on the uncorrupted data.", "questions": "- Should the sparsity of $\\hat{\\mu}$ and u in Theorems 1.2 and 1.3 be mentioned in the Theorem statement?\n- Given a dataset, is it possible to check if the stability condition (for either mean or covariance estimation) holds?\n- Why is the result for Robust Sparse PCA worse for Gaussian data? Can this be rectified or is it a limitation of the analysis?\n", "limitations": "There appears to be no clear discussion of limitations, outside of the discussion in 104-111 which states the worse bound under Gaussian data.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors present novel optimization programs for the tasks of robust sparse mean estimation and robust sparse PCA.\n- The algorithms are generic in that one can use any algorithm to find a first-order stationary point, such as gradient descent. \n- The stability conditions hold for more than just Gaussian inliers, although the only model of data that the authors' show satisfies this condition is sub-Gaussian.\n- Overall, the paper is clear and well-written.\n\nWeaknesses:\n- The paper could do a better job of explaining the intuition behind the methods, which seems to be hidden in Lemmas 3.2 and 3.4. As it stands, the optimization programs seem to come out of nowhere.\n- In practice, one typically would only find an approximate stationary point. As far as I can tell, there is no discussion of how this affects the approximation results of the algorithm.\n- It is unclear how general the deterministic stability conditions are, and if they extend past sub-Gaussian data.\n- For the practical gradient descent method, there is no iteration complexity bound given.\n- The experiments are quite limited, and there only seems to be a marginal improvement over the RME_sp method. Furthermore, I am left wondering what the optimization landscape of the objective looks like, and what convergence properties it exhibits.\n\nUpdate: through the clarification of the authors on the intuition behind the method as well as the novelty of the energy landscape, I have decided to raise my score.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5kL_yUHqrOd", "reviewer": "Reviewer_XqmN", "summary": "The authors demonstrate that standard first-order methods lead to robust and efficient algorithms for sparse mean\nestimation and sparse PCA. Their main contribution consists of non-convex formulations for  these robust estimation tasks in the presence of outliers in high-dimensional data.", "questions": "Can you provide a list of computer vision applications in which the proposed methods can be applied?", "limitations": "The authors have well addressed the limitations of their non-convex formulations.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper is well written and organized.\n2) The non-convex formulations for  robust estimation are novel and well detailed making them reproducible.\n\nWeaknesses:\nThe authors indicated applications of the proposed non-convex formulations for  robust sparse PCA and robust PCA. But they should also indicate applications in computer vision of robust sparse PCA and robust PCA.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept