Robust and differentially private mean estimation
Authors: Xiyang Liu
Weihao Kong
Sham M. Kakade
Sewoong Oh
Venue: NeurIPS 2021 Poster (2021)
Keywords: differential privacy
robust mean estimation

Abstract: In statistical learning and analysis from shared data, which is increasingly widely adopted in platforms such as federated learning and meta-learning, there are two major concerns: privacy and robustness. Each participating individual should be able to contribute without the fear of leaking one's sensitive information.  At the same time, the system should be robust in the presence of malicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable to the other. We bridge this gap for the canonical problem of estimating the mean from i.i.d.~samples. We introduce PRIME, which is the first efficient algorithm that achieves both privacy and robustness for a wide range of distributions. We further complement this result with a novel exponential time algorithm that improves the sample complexity of PRIME, achieving a near-optimal guarantee and matching that of a known lower bound for (non-robust) private mean estimation. This proves that there is no extra statistical cost to simultaneously guaranteeing privacy and robustness.  

Robust and differentially private mean estimation
Xiyang Liu, Weihao Kong, Sham Kakade, Sewoong Oh Paul G. Allen School of Computer Science and Engineering,
University of Washington
{xiyangl, whkong, shwno washington, edu
Abstract
In statistical learning and analysis from shared data, which is increasingly widely adopted in platforms such as federated learning and meta-learning, there are two major concerns: privacy and robustness. Each participating individual should be able to contribute without the fear of leaking one's sensitive information. At the same time, the system should be robust in the presence of malicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable the other. We bridge this gap for the canonical problem of estimating the mean from i.i.d. samples. We introduce PRIME. which is the first efficient algorithm that achieves both privacy and robustness for wide range of distributions. We further complement this result with novel exponential time algorithm that improves the sample complexity of PRIME, achieving near-optimal guarantee and matching a known lower bound for (non-robust) private mean estimation. This proves that there is no extra statistical cost to simultaneously guaranteeing privacy and robustness.
Introduction
When releasing database statistics on a collection of entries from individuals, we would ideally like make impossible to reverse-engineer each individual's potentially sensitive information. Privacy-preserving techniques add just enough randomness tailored to the statistical task to guarantee protection. At the same time, becoming increasingly common to apply such techniques to databases collected from multiple sources, not all of which can be trusted. Emerging data access frameworks, such as federated analyses across users' devices or data silos [50], make easier to temper with such collected datasets, leaving private statistical analyses vulnerable to a malicious corruption of a fraction of the data.
Differential privacy has emerged as a widely accepted de facto measure of privacy, which is now a standard in releasing the statistics of the U.S. Census data 2 statistics and also deployed in real-worke commercial systems (74 40) 41). A statistical analysis is said to be differentially private (DP) if the likelihood of the (randomized) outcome does not change significantly when a single arbitrary entry is added/removed (formally defined in $1.2). p. This provides a strong privacy guarantee: even powerful adversary who knows all the other entries in the database cannot confidently identify whether a particular individual is participating in the database based on the outcome of the analysis. This ensures plausible deniability, central to protecting an individual's privacy.
In this paper, we focus on one of the most canonical problems in statistics: estimating the mean of a distribution from i.i.d. samples. For distributions with unbounded support, such sub-Gaussian and heavy-tailed distributions, fundamental trade-off's between accuracy, sample size, and privacy have only recently been identified (58 52 54 and efficient private estimators proposed. However, these approaches are brittle when a fraction of the data is corrupted, posing real threat, referred to as data poisoning attacks [99 79]. In defense of such attacks, robust (but not necessarily private) statistics has emerged as a popular setting of recent algorithmic and mathematical breakthroughs [73 30
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

One might be misled into thinking that privacy ensures robustness since DP guarantees that a single outlier cannot change the estimation too much. This intuition is true only in a low dimension; each sample has to be an obvious outlier to significantly change the mean. However, in high dimension, each corrupted data point ean look perfectly uncorrupted but still shift the mean significant when colluding together (e.g., see Fig. [). Focusing on the canonical problem of mean estimation, we introduce novel algorithms that achieve robustness and privacy simultaneously even when a fraction of data is corrupted arbitrarily. For such algorithms, there is fundamental question of interest: do we need more samples to make private mean estimation also robust against adversarial corruption?
distributions. If we can afford exponential run-time in the dimension, robustness can be achieved without extra cost in sample complexity. We introduce novel estimator that (i) satisfies (s, 6)-DP, (it) achieves near-optimal rebustness under a-fraction of corrupted data, achieving accuracy of ( [og(I/a)) nearly matching the fundamental lower bound of ((a)) that holds even for a (non-private) robust mean estimation with infinite samples, and (tix) achieves near-optimal sample complexity matching that of a fundamental lower bound for (non-robust) private mean estimation as shown in Table I
Theorem 1 (Informal Theorem 7 exponential time). Algorithm 2 is (E, 8)-DP. When a fraction of the data is arbitrarily corrupted from n samples from a d-dimensional sub-Gaussian distribution with mean μ and an identity sub-Gaussian parameter. if = O(d/a² + (d + d² log((16))/
then Algorithm 2
achieves Í pll2 = O(a / (lo((//)) w.h.p.
We introduce PRIME (PRIvate and robust Mean Estimation) in $2.3 with details in Algorithm 2
Appendix E. to achieve computational efficiency. It requires a run-time of only O(d + ndf)), ) but at the cost of requiring extra dz/² factor larger number of samples. This cannot be improved upon with current techniques since efficient robust estimators rely on the top PCA directions of the covariance matrix to detect outliers. (78) showed that ((d3/2) samples are necessary to compute PCA directions while preserving (c, 8)-D when ||a:||| O(vd). It remains an open question if this ((88/2/ bottleneck is fundamental; no matching lower bound is currently known.
Theorem 2 (Informal Theorem 6 polynomial time). PRIME is (E, 5) and under the assumption
Thm / nn Add/o² (d log(1/0))/(az)) achieves || Mll2 O /log(1/a))) w.h.p.
Upper bound (poly-time)
Upper bound (exp-time)
Lower bound
(E, [52]
0 + dloog (1/6))
0 d
U d +
a-corruption (36)
0
12 2(45)
a-corruption and
Ō 4 log(1/8)
0
d+ log
1 4 + 0.
(e, 5)DD (this paper)
[Theorem 6
[Theorem
52
Table 1: For estimating the mean Rd of a Gaub-Gassiin distribution with a known covariance, we list the sufficient necessary conditions the sample sizes to achieve error || μاl2 Ō(a) under (c, -)- corruption of an a-fraction of samples, and both. requires the distribution to be Gaussian 14 and requires 5 < vd/n.
Heavy-tailed distributions. When samples are drawn from a distribution with bounded covariance, parameters of Algorithm can be modified to nearly match the optimal sample complexity of (non- robust) private mean estimation in Table 2 This algorithm also matches the fundamental limit on the accuracy of (non-private) robust estimation, which in this case is 2(22
Theorem (Informal Theorem 8. exponential time). From a distribution with mean μ E RRd and covariance Σ N I, n samples are drawn and a-fraction is corrupted. Algorithm is (c, 8DDD and if ((d + dz/2 log(1 (1)) + d²-2 3/2 (1/8)/e) achieves || /l|2 = 0(a-/2) w.h.p.
The proposed PRIME-HT for covariance bounded distributions achieve computational efficiency at the cost of extra factor of dz/2 in sample size. This bottleneck is also due to DP PCA, and it remains open whether this gap can be closed by an efficient estimator.
Theorem 4 (Informal Theorem ((((///oo(1/))) achieves ف μlll2 (a22/2) whh.p. under the assumptions of Thm.
g polynomial time). PRIME-HT is (E, and if
2

---

Upper bound (poly-time)
Upper bound (exp-time)
Lower bound
(c [54
O d log (1,00)
O d log (1/61)
M2( d
aE d
Q az
a-corruption [36
a-corruption and
Ō 272 logg (6)
Ō d+ log (1/
U2 d (544)
()-D) (this paper)
[Theorem 9
ac
ar [Theorem 8
Table 2: For estimating the mean μ Rd of covariance bounded distribution, list the sufficient
necessary conditions the sample size achieve error /1 /4|l2 ((22))) under (c, 6)-P, corruption of an e-fraction of samples, and both.
1.1 Technical contributions
We introduce PRIME which simultancously achieves (s, DDD and robustness against a-fraction of corruption. A major challenge in making a standard filter-based robust estimation algorithm (c.g.. 30)
private is the high sensitivity of the filtered set that we pass from one iteration to the next. We propose a new framework which makes private only the statistics of the set, hence significantly reducing the sensitivity. Our major innovation is a tight analysis of the end-to-end sensitivity of this multiple interactive accesses to database. This critical in achieving robustness while preserving privacy and is also of independent interest in making general iterative filtering algorithms private.
The classical filter approach (see, c.g. 30 needs to access the database (dd) times, which brings an extra O(vi factor in the sample complexity due to DP composition. In order to reduce the iteration complexity, following the approach in [36], we propose filtering multiple directions simultaneously using a new score based on the matrix multiplicative weights (MMW). In order to privatize the MMW filter, our major innovation is novel adaptive filtering algorithm DPTHRESHOLD( that outputs a single private threshold which guarantees sufficient progress at every iteration. This brings the number of database accesses from (dd to O(log d)
One downside of PRIME is that it requires an extra d'/2 factor in the sample complexity, compared known lower bounds for (non-robust) DP mean estimation. To investigate whether this is also necessary, we propose sample optimal exponential time robust mean estimation algorithm in $ and prove that there no extra statistical cost to jointly requiring privacy and robustness. Our major technical innovations is in using resilience property of the dataser to not only find robust mean (which the typical use case of resilience) but also bound sensitivity of that robust mean.
1.2 Preliminary differential privacy (DP)
DP a formal metric for measuring privacy leakage when a dataset is accessed with a query 377. Definition 1.1. Given two datasets $ = (2x Di and S' = {at we say S and S' are neighboring (S, < 1 where da (5,S*) - max 511, \ S1}, which is denoted by S ~ S'. For an output of a stochastic query q on a database, we say 9 satisfies (e. dififerrrella privacy for some E > 0 and 8 E (0, (g()) E A) < PF((") E A) + for all S ~ S' and all subset A.
Let Lap(b) be random vector with entries i.i.d. sampled from Laplace distribution with pdf (1/26)e-1=1/), Let N(p, M) denote Gaussian random vector with mean μ and covariance Σ. Definition 1.2. The sensitivity of query f(S) E R is defined as Ap sups-s' ( S(S')lp for norm ||ær|p (Eieja) [xr),)//r, For p 1, the Laplace mechanism outputs f(S) Lap(A1/s) and achieves (e, D)-DP (37]. For p = 2, the Gaussian mechanism outputs S(S) - (0, (A2( (l1//////// and achieves (e, DDP (8).
We use these output perturbation mechanisms along with the exponential mechanism 669 as building
blocks. Appendix A provides detailed survey of privacy and robust estimation.
1.3 Problem formulation
We are given n samples from a sub-Gaussian distribution with a known covariance but unknown mean, and fraction of the samples are corrupted by an adversary. Our goal is to estimate the
3

---

unknown mean. We follow the standard definition of adversary in [30], which can adaptively choose which samples corrupt and arbitrarily replace them with any points.
Assumption 1. An uncorrupted dataset Sgood consists of n i.i.d. samples from d-dimensional
sub-Gaussian distribution with mean μ Rd and covariance E [xzz ] La. which is Ssub-Gaussian, L.e. Elexp(e] z)] I exp(Ilull2/2 for all E RR. For some a E (0, 1/2), we are given a corrupted dataset S = { E J where an adversary adaptively inspects all the samples in Sgood. removes an of them, and replaces them with Soad which are on arbitrary points in R-
Similarly, we consider the same problem for heavy-tailed distributions with bounded covariance. We present the assumption and main results for covariance bounded distributions in Appendix B
For x RR we use ||>|| (Eveda (z;))) denote the Euclidean norm. For X E gaxd, we use || max ||Xeelaa to denote the spectral norm. The d x identity matrix Laxd- Whenever it is clear from context, we use to denote both a set of data points and also the set of indices of those data points. O and f hide poly-logarithmic factors in d, n, 1/a, and the failure probability.
Notations. Let [n] 21, n).
Outline. We present PRIME for uub-Gaussian distribution in 2 and present theoretical analysis in 3 We then introduce exponential time algorithm with near optimal guarantee in $4 Due to space constraints, analogous results for heavy-tailed distributions are presented in Appendix
2 PRIME: efficient algorithm for robust and DP mean estimation
In order describe the proposed algorithm PRIME, we need first describe standard (non-private) iterative filtering algorithm for robust mean estimation.
2.1 Background on (non-private) iterative filtering for robust mean estimation
Non-private robust mean estimation approaches recursively apply the following.filee whose frame-
work first proposed in (28) Given a dataset S {.:) the current set So S [n] of data points
updated starting with S [n]. At each step, the following filter (Algorithm in (63) attempts to detect the corrupted data points and remove them.
1. Compute the top eigenvector vi < arg max v:|||la] T Cov(S:-1)6 of the covariance of the current data set {ri]ess, 1:
2. Compute scores for all data points j E S Tj + (v. (zz- Mcan(S;-1)))²
3. Draw random threshold: Z, + Unif [0, 1))
4. Remove outliers from S defined as {i E St-1 : T; is in the largest 2o-tail of (TylEes..
and T; 2 Z, Fmax) where Tmax = maxjes.-. Tj
This is repeated until the empirical covariance is sufficiently small and the empirical mean j is output. At a high level, the correctness of this algorithm relies on the key observation that the a-fraction of adversarial corruption can not significantly change the mean of the dataset without introducing large eigenvalues in the empirical covariance. Therefore, the algorithm finds top eigenvector of the empirical covariance in step 1, and tries to correct the empirical covariance by removing corrupted data points. Each data point is assigned score in step 2 which indicates the "badness" of the data points, and a threshold Z, in step 3 is carefully designed such that step 4 guarantees to remove more corrupted data points than good data points (in expectation). This guarantees the following bound achieving the near-optimal sample complexity shown in the second row of Table I A formal description of this algorithm is in Algorithm 4 in Appendix C
Proposition 2.1 (Corollary of [63 Theorem 2.I... Under assumption 7 the above filtering algorithm achieves accuracy [ μll2 S ((a//log(1/o))) w.p. 0.9 in 2 ((d/a2).
Challenges in making robust mean estimation private. To get a DP and robust mean, naive attempt to apply standard output perturbation mechanism to f.. However, this obviously challenging since the end-to-end sensitivity is intractable. The standard recipe to circumvent this is to make the current "state" S, private at every iteration. Once S. private (hence, public knowledge), making the next "statee S₁ private is simpler. We only need to analyze the sensitivity of single step

---

and apply some output perturbation mechanism with (Ex, 6;). End-to-end privacy is guaranteed by accounting for all these (Ex, 6,)'s using the advanced composition [5]]. This recipe has been quite successful, for example, in training neural networks with (stochastic) gradient descent [I] where the current state can be the optimization variable Xz. However, for the above (non-private) filtering algorithm, this standard recipe fails, since the state St is set and has large sensitivity. Changing a single data point in St can significantly alter which (and how many) samples are filtered out.
2.2 A new framework for private iterative filtering
Instead of making the (highly sensitive) St itself private, we propose new framework which makes private only the statistics of Sy: the mean br and the top principal direction U4. There are two versions of this algorithm, which output the exactly same ji with the exactly same privacy guarantees, but are written from two different perspectives. We present here the interactive version from the perspective of an analyst accessing the dataset via DP queries (grange: Øsize Gmean: Qnorm and (PCA), because this version makes clear the inner operations of each private mechanisms, hence making (i) the sensitivity analysis transparent, (ii) checking the correctness of privacy guarantees easy, and (iii) tracking privacy accountant simple. In practice one should implement the centralized version (Algorithm 7 in Appendix D) which is significantly more efficient.
Algorithm 1: Private iterative filtering (interactive version)
Input: S {x; he(m). a E (0, 1/2), probability Ç E (0, 1), # of iterations T (d)), (E,6)
(z, B) + Grange (S, 5,,0011, 0.018)
ει + min / (0/3/44//77// /2 log(2/0)), 81 < 0.996/(8T)
3 if n < (4/a1) (1) ()) then Output: 0
for ( = I...,, do
5
T4e - qsize (1(ug, U22
B), if n4 < 3n/4 then Output: 0
jt f- Qmean (1(1e, U2, (0),
d f Anorm (1(pe) Fz. Zz) Zz)] E1, 14, 2, B)
if de S (C' 10C--0000 0.01)a log 1/a then Output: 1
((Ca(((He, 02, Ze) 2 (Et-
11, M4, 61, B))
10
Ze + Unif([0,1) I])
Output: frr
We give a high-level explanation of each step of Algorithm T here and give the formal definitions of all the queries in Appendix D First, Grauge returns (the parameters of) a hypercube I B/2. B B/2 that is guaranteed to include all uncorrupted samples while preserving privacy. This is achieved by running d coordinate-we wise private histograms and selecting ž as the center of the largest bin for the j-th coordinate. Since covariance is I, Grange returns a fixed B = 80 / /log( log(dn/(). Such an adaptive estimate of the support is critical in tightly bounding the sensitivity of all subsequent queries, which operate on the clipped dataset; all data points are projected as Pa++- B/2.B/22 B/////// (z) = arg ( B/2 Ily - æ||2 in all the queries that follow. With clipping, a single data point can now change at most by B Bdd.
The subsequent steps perform the non-private filtering algorithm of 221 but with private statistics μtt and As the set St changes over time, we lower bound its size (which we choose to be |St| > n/2) to upper bound the sensitivity of other queries quean Quorm and qPCA.
At the t-th iterations, every time query is called the data curator (i) uses (z, B) to clip the data, (ti) computes S, by running 1 steps of the non-private filtering algorithm of $2. but with given fixed set of parameters {(r,, vz) hee[t-1] (and the given randomness /ee )), and (Mii computes the queried private statistics of S,. If the private spectral norm of the covariance of S, (i.e., Aς) is sufficiently small, we output the private and robust mean ft = fe (line B). Otherwise, we compute the private top PCA direction U; and draw an randommess Z, to be used the next step of filtering, as in the non-private filtering algorithm. We emphasize that { are not private, and hence never returned to the analyst. We also note that this interactive version is redundant as every query is re-computing S. In our setting, the analyst has the dataset and there is need to separate them. This leads to
5

---

centralized version we provide in Algorithm@ the appendix, which avoids redundant computations and hence is significantly more efficient.
The main challenge in this framework is the privacy analysis. Because ((t) is not private, each query runs - 1 steps of filtering whose end-to-end sensitivity could blow-up. Algorithmically. (i) start with specific choice of non-private iterative filtering algorithm (among several variations that are equivalent in non-pin non-private setting but widely differ in its sensitivity). and (iæ) make appropriate changes in the private queries (Algorithm]) I keep the sensitivity small. Analytically, the following key technical lemma allows a sharp analysis of the end-to-end sensitivity of iterative filtering.
Lemma 2.2. Let Se(S) denote the resulting subset of samples after iterations of the filtering in the queries (Asizer Imean, quorm, and PPCA) are applied to dataset S using fixed parameters Alpe, ve, Zr) Then, we have do S((5)) I ds (S, where d'( - max \ 1",,18' (
Recall that two datasets are neighboring, i.c., S ~ S' iff (s S') < 1. This lemma implies that if two datasets are neighboring, then they are still neighboring after filtering with the same parameters. no matter how many times we filter them. Hence, this lemma allows us to use the standard output- perturbation mechanisms with (51, 51 )DP. Advanced composition ensures that end-to-end guarantee of 4T such queries is (0.99e, 0.99% 0.995)-DP. Together with (0.01e, 0.015)- budget used in grange- this satisfied the target privacy. Analyzing the utility of this algorithm, we get the following guarantee.
Theorem 5. Algorithum 7 is (e, 8D. Under Assumption ! there exists a universal constant E (0, 0.1) such that a S e and n = ÿ ((d/a2) + d2 (log(1/6) //22 0/2 (Ea)) then Algorithm achieves
|| - All2 S (oo((//o)))))))) with probability 0.9.
The first term (d)aa)) in the sample complexity is optimal (cf. Table but there is a factor of d gap in the second term. This is due to the fact that we need run (d)) iterations in the worst-case. Such numerous accesses to the database result in large noise to be added at each iteration, requiring large sample size combat that extra noise. We introduce PRIME to reduce the number of iterations to O(log d)²) and significantly reduce the sample complexity.
2.3 PRIME: novel robust and private mean estimator
Algorithm (specifiallyy Filter(-) in Algorithm I accesses the database (dd) times. This is necessary for two reasons. First, the filter checks only one direction d/ at each iteration. In the worst case, the corrupted samples can be scattered in M2(d) orthogonal directions such that the filter needs to be repeated (dd) times. Secondly, even if the corrupted samples are clustered together in one direction, the filter still needs to be repeated (dd) times. This is because we had use large (random) threshold of d = (dd) to make the threshold data-independent so that we can keep the sensitivity of Filter(-) low, which results in slow progress. We propose filtering multiple directions simultaneously using a new score { based on the matrix multiplicative weights. Central to this approach is novel adaptive filtering algorithm DPTURESIOLD( that guarantees sufficient decrease in the total score at every iteration.
2.3.1 Matrix Multiplicative Weight (MMW) scoring
The MMW-based approach, pioneered in [6 for non-private robust mean estimation, filters out multiple directions simultaneously. It runs over Olog d) epochs and every epoch consists of O Olog d) iterations. At every epoch and iteration I, step 2 of the iterative filtering in 22 is replaced by new score т; = (z; - ( (z; - Mcan(S.)) )) where Uf(*) now accounts for all directions in Idd but appropriately weighted. Precisely, it defined via the matrix multiplicative update:
exp (a()) Erejy (Cov(S!)) I))
U, = Tr( exp(a(() Evety (Cov(S!") 1)))
for some choice of (+) > 0. If set the number of iterations one, choice of (*)) recovers the previous score that relied on the top singular vector from 1 and a choice of (s) = 0 gives a
simple norm based score t. = || An appropriate choice ad)) smoothly interpolates between these two extremes, which ensures that O(log d' iterations are sufficient for the spectral norm of the

---

covariance to decrease strictly by constant factor. This guarantees that after Ollog d) epochs, we sufficiently decrease the covariance to ensure that the empirical mean is accurate enough. Critical in achieving this gain is our carefully designed filtering algorithm DPTHRESHOLD D that uses the privately computed MMW-based scores using Gaussian mechanism on the covariance matrices as shown in Algorithm I in Appendix E
2.3.2 Adaptive filtering with DPTHRESHOLD
Novelty. The corresponding non-private filtering of 36 Algorithm 9] for robust mean estimation takes advantage of an adaptive threshold, but filters out each sample independently resulting in prohibitively large sensitivity; the coupling between each sample and the randomness used to filter can change widely between two neighboring datasets. On the other hand, Algorithm
[ (i.e., Filter(-) in Algorithm 6) takes advantage of jointly filtering all points above a single threshold BzdZ, with a single randomness Z Unif (0, 1). but the non non-adaptive (and hence large) choice of the range B²d results in a large number of iterations because each filtering only decrease the score by little. To sufficiently reduce the total score while maintaining small sensitivity, introduce a filter with single and adaptive threshold.
Algorithm. Our goal here is to privately find a single scalar such that when a randomized filter is applied on the scores {ri} with a (random) threshold pZ (with Z drawn uniform in [o, 1)), we filter out enough samples to make progress in each iteration while ensuring that we do not remove too many uncorrupted samples. This is a slight generalization the non-private algorithm in Section 2.1 which simply set p max Tj. While this guarantees the filter removes more corrupted samples than good samples, it does not make sufficient progress in reducing the total score of the samples.
Ideally, we want the thresholding to decrease the total score by a constant multiplicative factor, which will in the end allow the algorithm to terminate within logarithmic iterations. To this end, we propose a new scheme of using the largest such that the following inequality holds:
Σ (T. - 0.31 TPP
(T: (T=-1)
T.E.
We use a private histogram of the scores to approximate this threshold. Similar to 55 58
we use
geometrically increasing bin sizes such that we only Oloog B2d) bins while achieving preferred multiplicattive error in our quantization. At each epoch s and iteration t, we run DPTHRESHOLD sketched in the following to approximate p followed by a random filter. Step 3 replaces the non-private condition in Eq. ① A complete description is provided in Algorithm T1
1. Privately compute scores for all data points i E s(*) T, < (x,- - 1e) Tu, (z. pt):
2. Compute private histogram (h, ( 2++lg((B') d) of the scores over geometrically sized bins
I = [1/4, 1/2), I2 = (1, 12+ = [2) 13* d)- 200](
3. Privately find the largest l satisfying E2 2t) h, 0.31 Σ Eis (Ti 1):
4. Output = 2f
Analyses of PRIME
Building on the framework of Algorithm T PRIME (Algorithm 9 replaces the score with the MMW- based score presented in $2..1 and the filter with the adaptive DPTHRESHOLD. This reduces the number of iterations to T T(log d)²) achieving the following bound.
Theorem 6. PRIME is (e, diffferrrnnllllly private. Under Assumption 7 there exists universal constant E (0, 0.1) such that if S and n ()(d/a²) + log(1/)) then PRIME
achieves || - pll22 = (aa log (1/()) with probability 0.9.
A proof is provided in Appendix F The notation K(-) hides logarithmic terms in d, R, and 1/a. To achieve an error of (Tag/Tog1 [o/((/))), the first term Q(d/a² log(1 log(1 is necessary even if there is no corruption. The accuracy of O(a Olaa//oo(L//a [o/(]/))) matches the lower bound shown in [33] for any polynomial time statistical query algorithm, and it nearly matches the information theoretical lower bound on robust estimation of Q(a). On the other hand, the second term of (2(d// log(/a)))
7

---

has an extra factor of d' compared to the optimal one achieved by exponential time Algorithm 2 It an open question if this gap can be closed by polynomial time algorithm.
The bottleneck is the private matrix multiplicative weights. Such spectral analyses are crucial in filter-based robust estimators. Even for special case of privately computing the top principal component, the best polynomial time algorithm requires (dd//2) samples [39 18 78
and this
sample complexity is also necessary as shown in (39 Corollary 25].
To boost the success probability to - Ç for some small > O, we need an extra log(1/() factor in the sample complexity to make sure the dataset satisfies the regularity condition with probability c/2. Then we can run PRIME (og() times and choose the output of run that satisfies n²(*) > n - 100) and A (+) I
Ca log(1/a)) termination.
Muan
Mean
Mean
PRIME
PRIME
PRIVE
5.09
Dimersion
60
160
Dimens
85
Figure 1: Private mean estimators (e.g.. DP mean (52)) are vulnerable to adversarial corruption especially in high dimensions, while the proposed PRIME achieves robustness (and privacy) regardless of the dimension of the samples.
Numerical experiments support our theoretical claims. The left figure with E,, = (0.05, 20, 0.01, 10%) is in the large a regime where the DP Mean error dominates by avd and PRIME error by / lo)(1/a). Hence, PRIME error is constant whereas DP Mean error increases with the dimension d. The second figure with (a, E, 6, n) (0.001, 20, 0.01,10% is in the small regime when DP Mean error consists of avd + /d/n and PRIME is dominated by vd/n. Both increase with the dimension d, and the gap can be made large by increasing a. The right figure with (ar, 8, n) = (0.1, 0.01, 10, 10%) ) is when DP Mean error is dominated by a and PRIME by avloog1/a) when E > ed /(am). Below this threshold, which happens in this example around 0.05, the added noise in the private mechanism starts dominate with decreasing e. Both algorithms have respective thresholds below which the error increases with decreasing e. This threshold is larger for PRIME because it uses the privacy budget to perform multiple operations and hence the noise added to the final output is larger compared to DP Mean. Below this threshold, which can be easily determined based on the known parameters (e, 5, n, a)), we should either collect more data (which will decrease the threshold) or give up filtering and spend all privacy budget on grange and the empirical mean (which will reduce the error). Details of the experiments are in Appendix
Exponential time algorithm with near-optimal sample complexity
Novelty. An existing exponential time algorithm for robust and private mean estimation in 14 strictly requires the uncorrupted samples to drawn from a Gaussian distribution. We also provide similar algorithm based on private Tukey median in Appendix [ and its analysis in Appendix [ In this section, we introduce a novel estimator that achieves near-optimal guarantees for more general sub-Gaussian distributions (and also covariance bounded distributions) but takes exponential run-time. Its innovation is in leveraging on the resilience property well-behaved distributions not only to estimate the mean robustly (which is the standard use of the property) but also to adaptively bound the sensitivity of the estimator, thus achieving optimal
tradcoff.
Definition 4.1 (Resilience from Definition 1 in 77].. A set of points {a: hes s lying in Rd is (a, a)- resilient around a point μ if ([(//[T) Eirr(; p)1 S a for all subsets T of size (1 - a)]s).
Algorithm. As data is corrupted, we define R(S) surrogate for resilience of the uncorrupted part of the set. If S indeed consists of a 1 - a fraction of independent samples from the promised class of distributions, the goodness score R(S) will be close to the resilience property of the good data.
8

---

Definition 4.2 (Goodness of set). For μ(S) = (1/151) EiEs 2i, let us define
min R(S) (1 TCS")T=((-0))S1) |Ia(T) - (((T))((S'(1a)
max
Algorithm 2 first checks if the resilience matches that of the promised distribution. The data is pre-pn pre-processed with Orange to ensure we can check R(S) privately. Once resilience is cleared, we can safely use the exponential mechanism based the score function d(a,, in Definition 4.3 to select an approximate robust mean j privately. The choice of the sensitivity critically relies on the fact that resilient datasets have small sensitivity of (((1/n) (log(1/a)) Without the resilience check, the sensitivity is ((d//2/n) resulting in an extra factor of v in the sample complexity.
Algorithm 2: Exponential-time private and robust mean estimation
Input: S = (a)) a (0, 1/2), (s,
if n < ed (og(1/0) (ea log(1//) (1/a)) then Output: @ [ cd2_22 log(1 / (sax) for hevay-tail]
(ar, B) 4 Orange (S, (1/3)e, (1 ())
Orange be (-) for hevay-tail]
3 Project the data points onto the ball: x4 + PB (1)) (z.). for all i E [7]]
R(S) + R(S) + Lap(3Bd ((ne))
R(()) > 2a alo/log///// then Output:
(i(S) > 20g v for hevay-tail]
else Output: randomly drawn point j E B ( sampled from density
r(p) x e (1/22A//og(1))))))m// d(a.s)
[e (e=(snva/(Qbee))dd...) for heavy-tail]
7
We propose the score function d(a, S) in the following definition, which is a robust estimator of the distance between the mean and the candidate p.
Definition 4.3. For set of data fai lying in RR, for any v E gd-1 define T to be the 3 [| points with the largest v value, B" to be the 3a|S] points with the smallest v x, value, and M" 5 B"). Define S) A max lo (μ(M²))
Analysis. For any direction v, the truncated mean estimator ((M") provides robust estimation of the true mean along the direction v, thus the distance can be simply defined by taking the maximum over all directions v. We show the sensitivity of this simple estimator is bounded by the resilience property divided by which is O((1/n) / /lo((1/)) once the resilience check is passed. This leads to the following near-optimal sample complexity. We provide a proof in Appendix H.2
Theorem 7 (Exponential time algorithm for sub- sub-Gaussian distributions). Algorithm 2 is (e. 6)-DP.
Under Assumption this algorithm achieves /| nll2 O(a /log///////// (1/a)) with probability Ç if
d + log d log (dwlog(dn//))/ + dd//2 log 1/2 + log & v /dlog log Ç8
n
n=
a log
Run-time. Computing R(S) exactly take (1)) operations. The exponential mechanism implemented with a-covering for ğ and a constant covering for can take O(nd( (log(dn/()/or operations.
5 Conclusion
Differentially private mean estimation is brittle against small fraction of the samples being corrupted by an adversary. We show that robustness can be achieved without any increase in the sample complexity by introducing a novel DP mean estimator, which requires run-time exponential in the dimension of the samples. The technical contribution is in leveraging the resilience property of well-behaved distributions in an innovative way to not only find robust mean (which is the typical use case of resilience) but also bound sensitivity for optimal privacy guarantee. To cope with the computational challenge, we propose an efficient algorithm, which we call PRIME, that achieves the optimal target accuracy at the cost of an increased sample complexity. The technical contributions

---

(i) novel framework for private iterative filtering and its tight analysis of the end end-to-end sensitivity and (it) novel filtering algorithm of DPTHRESHOLD which is critical in privately running matrix multiplicative weights and hence significantly reducing the number of accesses to the database. With appropriately chosen parameters, we show that our exponential time approach achieves near-optimal guarantees for both sub- Gaussian and covariance bounded distributions and PRIME achieves the same accuracy efficiently but at the cost of an increased sample complexity by d factor.
There are several directions for improving other problems, PRIME provides a new design principle for private and robust estimation. This can be more broadly applied to fundamental statistical analyses such robust covariance estimation
results further and applying the framework solve
28 30 [4
robust PCA
660 48
and robust linear regression (59] 35
PRIME could be improved in few directions. First, the sample complexity of (d(d/((a (og(a/)))) (d</2/(e (og(1/a))) (1g() in Theorem 6 suboptimal in the second term. Improving the d3/2 factor requires bypassing differentially private singular value decomposition, which seems to be a challenging task. However, it might be possible to separate the log(1/6) factor from the rest
of the terms and get an additive error of the form ((d/((² log(1/a))) + (d%/22 [ea log(1 /a))) (1/s)log(1 1og(1/5)) This requires using Laplace mechanism in private MMW (line 16 Algortihm 10) Secondly, the time complexity of PRIME is dominated by computation time of the matrix exponential
in (line 16 Algortihm 10 Total number of operations scale as ( nd?)). One might hope
to achieve (nd) time complexity using approximate computations of T 's using techniques from
[36] This does not improve the sample complexity, as the number of times the dataset is accessed remains the same. Finally, for (non-robust) private mean estimation, COINPRESS provides a practical
improvement in the small sample regime by progressively refining the search space [12]. The same principle could be applied to PRIME to design a robust version of COINPRESS. One important question remains open; how are differential privacy and robust statistics fundamentally related? We believe our exponential time algorithm hints on fundamental connection between robust statistics of data projected onto one- rreedimensional subspace and sensitivity of resulting score function for the exponential mechanism. It is an interesting direction to pursue this connection further to design novel algorithms that bridge privacy and robustness.
Acknowledgement
Sham Kakade acknowledges funding from the National Science Foundation under award CCF- 1703574. Sewoong Oh acknowledges funding from Google faculty research award, NSF grants 192-1929955, CCF-1705007, CNS-2002664, CCF 2019844 as a part of Institute for Foundation of Machine Learning, and 124-2112471 as part of Institute for Future Edge Networks and Distributed Intelligence.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308-318, 2016.
[2] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2867-2867, 2018.
[3] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded nigh-dimensional gaussians. arXiv preprint arXiv:2010.09922 2020.
[4] Zeyuan Allen Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the serty-seventh annual ACM symposium on Theory of computing, pages 237-245, 2015.
[5] Edoardo Amaldi and Viggo Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical computer science, (47(1-2):181-2 1995.
[6] Frank J Anscombe. Rejection of outliers. Technometrics, 2(2):123-146, 1960.
10

---

[7] Ainesh Bakshi and Pravesh Kothari. List-decodable subspace recovery via sum-of-squares. arXiv preprint arXiv:2002.05// 05109,, 2020.
[8] Balakrishnan, S. Du, J. Li, and A. Singh. Computationally efficient robust sparse estimation in high dimensions. In Proceedings of the 30th Conference on Learning Theory, COLT 2017,
pages 169 212, 2017.
[9] Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. arXiv preprint arXiv: 10731, 2019.
[10] K. Bhatia, P. Jain, P. Kamalaruban, and P. Kar. Consistent robust regression. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pages 2107-2116, 2017.
[11] Kush Bhatia, Prateek Jain, and Purushottam Kar. Robust regression via hard thresholding. In Advances in Neural Information Processing Systems, pages 721-729, 2015.
[12] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. arXiv preprint arXiv:2006.06618 2020.
[13] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-IIGG symposium on Principles of database systems, pages 228-138, 2005.
[14] Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. In Advances in Neural Information Processing Systems, pages 156-167, 2019.
[15] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint arXiv: /02.::9902.04495,, 2019.
[16] Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Za- kynthinou. Private identity testing for high-dimensional distributions. arXiv preprint 1tt.://05./////1 2019.
[17] Moses Charikar, Jacob Steinhardr, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47-60, 2017.
[18) Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha. A near-optimal algorithm for differentially-priiee principal components. The Journal of Muchine Learning Research, 14(1):2905 2943, 2013.
[19] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprini 1rXiv:1712.05553 2017.
[20] Yu Cheng, Ilias Diakonikolas, and Rong Ge. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2755-2771. SIAM, 2019.
[21] Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P Woodruff. Faster algorithms for high- dimensional robust covariance estimation. In Conference on Learning Theory, pages 727-757.
PMLR, 2019.
[22] Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. List decodable mean estimation in nearly linear time. arXiv preprini arXiv:2005.09790 2020.
[23] Arnak Dalalyan and Philip Thompson. Outlier-robust estimation of sparse linear model using fi-penalized huber's ss mn-estimator. Advances in Neural Information Processing Systems,
pages 33188-13198 2019.
[24] Jules Depersin and Guillaume Lecué. Robust subgaussian estimation of mean vector in nearly linear time. arXiv preprint arXiv: 03058, 2019.
[25] Lue Devroye and Gábor Lugosi. Combinatorial methods density estimation. Springer Science & Business Media, 2012.

---

[26] Aditya Dhar and Jason Huang. Designing differentially private estimators in high dimensions. arXiv preprint arXiv:2006.00 01944, 2020.
[27] Ila Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar, Robustly learning any clusterable mixture of gaussians. arXiv preprint wwxiv:2005.06417 2020.
[28] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-din sish-dienssoos without the computational intractabillity. SIAM Journal on Computing, 48(2):742 -24446444666... 2019.
[29] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: A robust meta-algorithm for stochastic optimization. In International Conference Machine Learning, pages 1596-1606, 2019.
[30] Iias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alis- tair Stewart. Being Robust (in High Dimensions) Can Be Practical. arXiv e-prints, page trXiv:1703.000 March 2017.
[31] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robustly learning a gaussian: Getting optimal error, efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2683-2702. SIAM, 2018.
[32] Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statisties. arXiv preprint
2019.
[33] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation high-ddmensiooal gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84. IEEE, 2017.
[34] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1047-1060, 2018
[35] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2745-2754. SIAM, 2019.
[36] Yihe Dong, Samuel Hopkins, and Jenry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. In Advances in Neural Information Processing Systems, pages 6067-6077, 2019.
[37] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[38] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4):21144)) 2014.
[39] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang, Analyze gauss: optimal bounds for prevayypres principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 11-20, 2014.
[40] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable ordinal response. In Proceedings of the 2014 ACM SIGSAC conference computer and communications security, pages 1054-1067, 2014.
[41] Giulia Fanti, Vasyl Pihur, and Úlfar Erlingsson. Building rappor with the unknown: Privacy- preserving learning of associations and data dictionaries. Proceedings on Privacy Enhancing Technologies, 2016(3):41-611 2016.
[42] Chao Gao et al. Robust regression via mutivariate regression depth. Bernoulli, 26(2):1139-111) 2020.
12

---

Conference on [43] Sam Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed tailed mean estimation made simple, via regret minimization. Advances in Neural Information Processing Systems, 33, 2020.
[44] Samuel B Hopkins. Mean estimation with sub-gaussian rates in polynomial time, Annals of Statistics, (8(2):1133-1213 2020.
[45] Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1021-1034, 2018.
[46] Samuel Hopkins and Jerry Li. How hard is robust mean estimation? Learning Theory, pages 1649-1682. PMLR, 2019.
[47] Peter J. Huber. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1):73 - 101, 1964.
[48] Arun Jambulapati, Jerry Li, and Kevin Tian. Robust sub-gaussian principal component analysis and width- indeedinddeendentt schatten packing. Advances in Neural Information Processing Systems, 33, 2020.
[49] He Jia and Santosh Vempala. Robustly clustering mixture of gaussians. arXiv preprint arXiv:1911.11888 2019.
[50] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977 2019.
[51] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference machine learning, pages 1376-1385, 2015.
[52] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Conference on Learning Theory, pages 1853-1902, 2019.
[53] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated gaussians. In 2020 Information Theory and Applications Workshop (ITA), pages 1-62. IEEE, 2020.
[54] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. arXiv preprint arXiv:2002.09460 2020.
[55] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Conference on Learning Theory, pages 2263-2285. PMLR, 2020.
[56] Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari. List-decodable linear regression. In Advances Neurul Information Processing Systems, pages 7423-7432, 2019.
[57] Sushrut Karmalkar and Eric Price. Compressed sensing with adversarial sparse noise via 11 regression. In 2nd Symposium on Simplicity in Algorithms, 2019.
[58] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv: /71 1et.:11110000000 100900,, 2017.
[59] Adam Klivans, Pravesh K Kothari, and Raghu Mcka. Efficient algorithms for outlier-robust regression. In Conference On Learning Theory, pages 1420-1430, 2018.
[60] Weihao Kong, Raghav Somani, Sham Kakade, and Sewoong Oh. Robust meta-learning for mixed linear regression with small batches. Advances in Neural Information Processing Systems, 33, 2020.
[61] Pravesh K Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1035-1046, 2018
13

---

[62] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665-674. IEEE, 2016.
[63] Jerry Li. CSE 599-M, Lecture Notes: Robustness in Machine Learning, 2019. URL: https //jerryzli .it.ub...b......... ret/usuuutmmm ml-111119/eeec77 pdf
[64] Jerry Li and Guanghao Ye. Robust gaussian covariance estimation in nearly-matrin multiplica- tion time. Advances in Neural Information Processing Systems, 33, 2020.
[65] Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis. High dimensional robust sparse regression. arXiv preprint
2018.
[66] Xiaohui Liu. Fast implementation of the tukey depth. Computational Statistics, 32(4):1395- 1410, 2017.
[67] Xiaohui Liu, Karl Mosler, and Pavlo Mozharovskyi. Fast computation of tukey trimmed regions and median dimension p> 2. Journal of Computational and Graphical Statisties, 28(3):682 (16,77686667 2019.
[68] Gábor Lugosi, Shahar Mendelson, al. Sub-gaussian estimators of the mean of random vector. Annals of Statistics, 47(2):733779,, 2019.
[69] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Anmual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103. IEEE, 2007.
[70] Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain, and Purushottam Kar. Clobally-convergent iteratively reweighted least squares for robust regression problems. In The 22nd International Conference Artificial Intelligence and Statistics, pages 313-322, 2019.
[71] A. Prasad, A. Suggala, S. Balakrishnan, and Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXiv: 2018.
[72] Prasad Raghavendra and Morris Yau. List decodable learning via sum squares. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 161-180. SIAM, 2020.
[73] Jacob Steinhardt, Moses Charikar, and Gregory Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In 9th Innovations Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zennnii fuer Informatik, 2018.
[74] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Pri- vacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprins arXiv:1709.02753 2017.
[75] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
[76] John W Tukey. A survey of sampling from contaminated distributions. Contributions to probability and statistics, pages 448 485, 1960.
[77] Martin J Wainwright. digeesiimeii statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[78) Lu Wei, Anand D Sarwate, Jukka Corander, Alfred Hero, and Vahid Tarokh. Analysis of a privacy-preserving pea algorithm using random matrix theory. In 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 1335-1339, IEFF, 2016.
[79] Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? International Conference on Machine Learning, pages 1699-1698. PMLR, 2015.
[80] Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni, and Zhiwei Steven Wu. Privately learning markov random fields. arXiv preprint arXiv:2002.094463, 2020.
14

---

[81] Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. Generalized resilience and robust statistics. arXiv preprint arXiv: 19t.199999.755 2019.
[82] Banghua Zhu, Jiantao Jiao, and Jacob Steinhardt. When does the tukey median work? arXiv preprint arXiv:2001.07805, 2020. 2020.
15


Reviews:
[{"review_id": "YlLAh4gf1nt", "reviewer": "Reviewer_i7TG", "summary": "This paper shows results on robust and differentially private mean estimation of sub-Gaussian and covariance bounded distributions. So far, work has mostly been done in the direction of either robustness or of differentially private statistics, but this paper puts both of them together. Specifically, it provides near-optimal (but exponential time) algorithm and sub-optimal (but polynomial time) algorithms for mean estimation of the aforementioned types of distributions.\n\nFor their polynomial-time algorithm, PRIME, they use an MMW filter-based approach, which they privatise in a novel filtering algorithm (which they call, \"DP-Threshold\"). This reduces the iteration complexity of the filter and the number of database accesses in each iteration.\n\nTheir exponential-time algorithm exploits the resilience property of the distributions to bound the sensitivity of the robust mean.\n\nFinally, they provide experimental results to back their theoretical results.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update: Upon the authors' response, I have decided to update my final evaluation.\n\nStrengths:\n1. The paper is very technical, and clearly a lot of work went into it.\n2. The paper is also quite well-written. It's organised and explains the background well enough.\n3. It is the first paper to give results for robust and differentially private mean estimation of sub-Gaussians and covariance bounded distributions. So, there's novelty in it.\n4. Their exponential-time algorithms are nearly optimal.\n5. The experimental results indicate significant improvements over any kinds of prior work in differential privacy. However, it is important to note that the comparison with the prior work of [KLSU'19] is a bit apples-to-oranges, as their work does not focus on robustness at all.\n\nWeaknesses:\n1. Their polynomial-time algorithms have $O(d^{3/2})$ sample complexity. The authors do highlight this deficiency in their work. New techniques altogether may be required to solve this problem, it seems, since going via the route of private PCA would incur such big costs.\n2. It is a bit surprising to see $(\\varepsilon,\\delta)$-differentially private algorithms needing a range on the mean $[-R,R]^d$. I say this because of the existence of stability-based methods in privacy. Is there a way to remove that dependence completely?\n3. This is kind of a nitpick, and the authors discuss this, too. The third graph in Figure 1. The accuracy of their algorithm is worse than the differentially private prior methods for value of $\\varepsilon$ less than $0.05$. This raises the question: are these algorithms really practical?\n\nComments:\n1. Typo: Figure 1 - second graph - y axis should be labelled as $||\\hat{\\mu}-\\mu||_2$.\n2. Line 355 should read as: We show that robustness can be achieved...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations have been mentioned in the detailed review. There doesn't seem to be any negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Ua9pznze5h8", "reviewer": "Reviewer_nCbz", "summary": "The paper proposes an algorithm which is both DP and robust for \"poisoning attacks\" for mean estimation. Namely, it can deal with an adversary corrupting \\alpha*n many points and still produces a mean which is fairly close to the true mean (of the remainder of the points); and do which without directly looking at the point but rather statistical properties that are randomly perturbed in order to preserve DP. In addition to the theoretical work, there was also a few experiments conducted on the output of the mechanism.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is an interesting paper that tackles DP-mean estimation from a new angle -- dealing with robustness and removing outliers. It is likely that it has implications - in terms of outlier detection - beyond what is discussed in paper and I am very fond of the idea of DP outlier detection/removal, as it means that the approach is likely to work even without some outlier.\n\nOn the flip side, I think that (a) the paper is poorly written (some mistakes are just plain embarrassing) and (b) I am baffled about the experiments. Firstly, as a theory-focused paper, I see little contribution in adding figures showing \"the math works\"; and more importantly, the first two figures are based on a very large \\eps value (unless I misunderstood the experiment section) so they are of very little importance. So I am left with the rightmost figure (pun intended), in which the error doesn't decay to 0 as \\eps increases. Is this a result of the fact that the robust mean estimation tends to be somewhat \"off\" even without privacy? A comparison to the non-private baseline would have helped here.\n\nStill, all in all I think this is an interesting paper and I advocate acceptance. \n\nTypos:\n* Line 110: The Lap-noise is to the power k, as each coordinate is perturbed.\n* Line 121: \\forall v.\n* Line 139: The current set S_t (not S_0)\n* Line 212: What's S'? Is this a general lemma for any S' or just for neighboring datasets?\n* U_t^{(s)} has a completely unclear definition. You sum over r yet you do not use the index r at all! The summation -- should it be in the numerator? Is it in the right place in the denominator? (Maybe I am missing something here...)\n* Section 2.3.2 needs a lot of work (at the expense of the discussion post Thm 6 + Sec. 5 which is mostly repetitive to the intro). What's the intuition for this \\rho? Where did the 0.31 factor come from?\n* Def 4.2: Don't get why S' has size (1-2\\alpha) rather than (1-\\alpha) and T should have size >= |S'|-\\alpha*n, no? Some discussion as to the bounds in the resilience score would be much appreciated here.\n* Line 351: Theta *inside* big O definition???\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Irrelevant.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Refuse to time myself."}, "extra_text": {}}, {"review_id": "HFUkNaSVRq6", "reviewer": "Reviewer_n7D3", "summary": "The paper considers the problem of robust mean estimation under adversarial contamination in the differentially private setting. In the canonical setting of robust mean estimation, one is given access to $n$ i.i.d samples from a well-behaved distribution over $\\mathbb{R}^d$ and the goal is to estimate the mean of the distribution. The catch is that an adversary is allowed to inspect the samples and arbitrarily corrupt an $\\alpha$ fraction of them. Standard assumptions on the distribution include assuming a spectral bound on the covariance matrix of the distribution although the optimal recovery guarantees improve under additional assumptions such as gaussianity. The key difference in the setup considered in this paper is that the algorithm is also required to be differentially private with respect to the data points. The problems of building robust and differentially private algorithms have received much attention in the recent part in isolation and building ones which satisfy both of these properties is a natural one. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers the problem of robust mean estimation under adversarial contamination in the differentially private setting. In the canonical setting of robust mean estimation, one is given access to $n$ i.i.d samples from a well-behaved distribution over $\\mathbb{R}^d$ and the goal is to estimate the mean of the distribution. The catch is that an adversary is allowed to inspect the samples and arbitrarily corrupt an $\\alpha$ fraction of them. Standard assumptions on the distribution include assuming a spectral bound on the covariance matrix of the distribution although the optimal recovery guarantees improve under additional assumptions such as gaussianity. The key difference in the setup considered in this paper is that the algorithm is also required to be differentially private with respect to the data points. The problems of building robust and differentially private algorithms have received much attention in the recent part in isolation and building ones which satisfy both of these properties is a natural one. \n\nThe paper proposes two main algorithms for the problem. The first is an algorithm which runs in polynomial time but suffers a sub-optimal sample complexity of $O(d^{3/2} / \\alpha^2)$ (as opposed to the information theoretically optimal rate of $O(d / \\alpha^2)$). The second is an exponential time algorithm which nevertheless obtains the optimal sample complexity up to log factors ($O(d / \\alpha^2)$). The efficient algorithm itself seems to be largely an adaption of the filtering based approach to robust mean estimation where one first obtains a spectral certificate determining which data points are likely to be outliers and uses this certificate to either remove corrupted data points or downweighting them in the computation of the mean estimate. The looseness in the sample complexity is due to the differentially private singular vector computation step that is used to compute the spectral certificate. The in-efficient algorithm in the paper essentially computes a noisy estimate of the solution to a direction wise trimmed mean problem. Roughly speaking, one searches for a mean estimate whose projection onto any direction $v$ is close to the trimmed mean of the data points when projected onto $v$ where the trimming eliminates the top and bottom $O(\\alpha)$ percentiles of the data points respectively. While this geometric insight existed in prior work as well, the adaptation to the differentially private setting (as done in Algorithm 2 of this paper) seems quite clever and novel even if it isn't emphasized as much. \n\nOverall, the contributions of the paper are valuable and interesting as the first work at the intersection of robustness and differential privacy. While the efficient algorithm is sub-optimal in terms of sample complexity, there seem to be clever insights in the construction of the inefficient algorithm which may enable future work on the topic. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3trdMQkLbsD", "reviewer": "Reviewer_reXf", "summary": "New algorithms for estimating Gaussian means that are both robust and differentially private. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides two new results on estimating the mean of a distribution via algorithms that are both robust (to an $\\alpha$ fraction of corruptions) and differentially private. \n\nThere are two new algorithms: \n\n1. An exponential-time algorithm that samples from the \"exponential mechanism\" (Gibbs distribution) over a rough bounding box for the distribution. The score function for the exponential mechanism is the Tukey depth of a point in the data set. The authors observe that this empirical Tukey depth is close to the analogous population quantity on correctly distributed data. (A similar reasoning underlies the simplest nonprivate robust estimation algorithm, which returns a point of maximimum Tukey depth. However, analyzing the randomized version requires understanding how the volumes of the level sets of the Tukey depth change with the depth.)\n\n2. A polynomial-time algorithm based on the (nonprivate) matrix-multiplicative-weights-based robust of Dong, Hopkins and Li. It was a little hard for me to understand what the real technical insight here was, but it seems like an important contribution, and one that provides a good starting point for future investigations. \n\nThe paper is clearly written and lays out its contributions succinctly. I think the authors could have done more to spell out dependencies on hidden parameters like R (the side-length of the bounding box from which the mean is drawn), and also to discuss how sensitive the results are to unknown co-variance structures. (For example, suppose we know a PSD matrix A such that the true covariance lies between $A$ and $cA$. Do the algorithm discussed here have sample complexity that scales polynomially with $c$? Logarithmically?) For what it's worth, I don't think it's fair to swallow dependencies on $R$ into the $\\tilde O(\\cdot)$ notation, since we don't know _a priori_ how $R$ relates to other quantities like $d$.\n\nI view the contributions of the paper largely in formulating the problem and laying out initial solutions. I think it should be accepted based on those. That said, it would have been nice to understand what the technical roadblocks were to analyzing the noisy version of the MMW-based algorithm of Hopkins et al, and also to see some discussion of whether there are fundamental relationships between robust and private estimation in high dimensions—for example, is some automatic conversion between the two possible, along the lines of the work of Dwork and Lei (STOC 2009)? \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review for technical limitations. The work is theoretical and doesn't directly address (or imply) social impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agreed that this is a strong and interesting technical work. The authors are advised to address dependence on the range parameter R, since this is often important in DP estimation tasks, as well as some related work mentioned by reviewers. Some weaknesses identified by reviewers include experiments (which is not the main contribution of the paper) and the suboptimal sample complexity of the efficient algorithm (which seems like a significant open problem), which can both be overlooked.
Decision: Accept (Poster)