Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
Authors: Gavin R Brown
Marco Gaboardi
Adam Smith
Jonathan Ullman
Lydia Zakynthinou
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Differential Privacy
Mean Estimation
Gaussian Estimation
Tukey Depth
Statistical Learning Theory

Abstract: We present two sample-efficient differentially private mean estimators for $d$-dimensional (sub)Gaussian distributions with unknown covariance. Informally, given $n \gtrsim d/\alpha^2$ samples from such a distribution with mean $\mu$ and covariance $\Sigma$, our estimators output $\tilde\mu$ such that $\| \tilde\mu - \mu \|_{\Sigma} \leq \alpha$, where $\| \cdot \|_{\Sigma}$ is the \emph{Mahalanobis distance}. All previous estimators with the same guarantee either require strong a priori bounds on the covariance matrix or require $\Omega(d^{3/2})$ samples.  
   
Each of our estimators is based on a simple, general approach to designing differentially private mechanisms, but with novel technical steps to make the estimator private and sample-efficient. Our first estimator samples a point with approximately maximum Tukey depth using the exponential mechanism, but restricted to the set of points of large Tukey depth. Proving that this mechanism is private requires a novel analysis. Our second estimator perturbs the empirical mean of the data set with noise calibrated to the empirical covariance. Only the mean is released, however; the covariance is only used internally. Its sample complexity guarantees hold more generally for subgaussian distributions, albeit with a slightly worse dependence on the privacy parameter. For both estimators, careful preprocessing of the data is required to satisfy differential privacy.

edu Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
Gavin Brown
Marco Gaboardi
Department of Computer Science
Department of Computer Science
Boston University
Boston University
grbrownabu edu
gaboardi@bu edu
Adam Smith
Jonathan Ullman
Department of Computer Science Boston University ads220bu. edu
Khoury College of Computer Sciences Northeastern University
jullman8ccs neu, edu
Lydia Zakynthinou
Khoury College of Computer Sciences
Northeastern University
Abstract
We present two sample-efficient differentially private mean estimators for d- dimensional (sub)aaussian distributions with unknown covariance. Informally, given n Z d/a a² samples from such distribution with mean μ and covariance E, estimators output jı such that | μ||x I a, where || || is the Mahalanobis distance. All previous estimators with the same guarantee either require strong a priori bounds on the covariance matrix or require (2(d322) samples.
Each of our estimators is based on simple, general approach to designing differ- entially private mechanisms, but with novel technical steps to make the estimator private and sample-efficient. Our first estimator samples point with approximately maximum Tukey depth using the exponential mechanism, but restricted to the set of points of large Tukey depth. Proving that this mechanism is private requires novel analysis. Our second estimator perturbs the empirical mean of the data set with noise calibrated to the empirical covariance, without releasing the covariance itself. Its sample complexity guarantees hold more generally for subgaussian dis- tributions, albeit with slightly worse dependence on the privacy parameter. For both estimators, careful preprocessing of the data is required to satisfy differential privacy.
Introduction
Although the goal of statistics and machine learning is to infer properties of a population, there is growing awareness that many statistical estimators and trained models reveal concerning amount of information about their data set, which leads to significant concerns about the privacy of the individuals who have contributed sensitive information that data These privacy violations have been demonstrated repeatedly via reconstruction attacks [21 30 27 46). membershippinnfereess
attacks 377 52 10 32
53 59) and instances of unwanted memorization of training data [13] 14 334
77. In order to realize the benefits of analyzing sensitive data sets, it is crucial to develop statistical
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

estimators and machine learning algorithms that make accurate inferences about the population but also protect the privacy of the individuals who contribute data.
In this work we study statistical estimators that satisfy a condition called differential privacy 22 which has become the standard criterion for individual privacy in statistics and machine learning. In- formally, differentially private algorithm guarantees that no attacker, regardless of their background knowledge or resources, can infer much more about any individual than they could have learned had that individual never contributed to the data set 45 A long body of work shows that differential privacy is compatible with a wide range of tasks in statistics and machine learning, and it is now seeing deployment at companies like Google B3 6 57], Apple [3, Facebook (55] and LinkedIn [ST]
as well statistical agencies like the U.S. Census Bureau [ 36
Background: Differentially Private Mean Estimation. We revisit differentially private estimators for one of the most fundamental tasks in all of statistics and machine learning-given .1,.... In Rd sampled i.i.d. from a distribution with mean E R2 and covariance Σ E IRaxd estimate the mean μ.. Mean estimation is not only an essential summary statistic in its own right, but also a building block for more sophisticated tasks like regression and stochastic optimization.
Without privacy constraints, the natural solution is to output the empirical mean Ne 1. E, The natural way to state the sumple-coppleitty guarantee of the empirical mean is
d
llue Eاام a.
where 2 hides a universal multiplicative constant, and the accuracy guarantee holds with large constant probability (say, 0.99). Importantly, ||ا - =||== = -|--1/²( - 1l)l2 is the error in Mahalanobis distance scaled to the covariance Σ. Bounding the error in Mahalanobis distance implies that in every direction v, the squared error is proportional to the variance v' Ev in that direction. The Mahalanobis distance is the natural way to measure the enror for mean estimation, since it tightly captures the uncertainty about the true mcan and is preserved under affine transformations.
Unfortunately. in high dimensions, releasing the empirical mean leads to concrete privacy breaches 32 mator that performs nearly as well as the empirical mean?
natural question thus: can we design a differentially private mean esti-
Without making additional assumptions, the answer turns out to be no-every differentially pri- vate estimator incurs a large overhead in sample complexity compared to the empirical mean [42]. However, it is known that if we further assume that the distribution satisfies some additional con- centration properties, we can do much better [54] 44 42). In this work, we focus on one class of well-concentrated distributions, those that are Gaussian (or, in some of our results, sub subaaussian). Although assuming Gaussian data is restrictive, it is a natural starting point for understanding the complexity of estimation when the distribution is not pathological. Moreover, even in the Gaussian case, one cannot obtain error comparable to that of the empirical mean unless n 2 d [0 32 41 so we will also focus on the case where the sample size is at least as large as the dimension.
For Gaussian data, if the analyst has prior information about the covariance matrix in the form of matrix A and bound x 2 such that A < Σ < K.A then there is folklore private estimator A(x). based on line of work initiated by Karwa and Vadhan [44] 41 5 2). that finds an approximate range for the data, truncates the points to within that range, and runs the Gaussian mechanism on the resulting empirical mean. This estimator achieves
d dVK [1(()) m11s: S a,
(1)
where is the privacy parameter controlling the level of privacy (see Definition 2.2). with stronger privacy as E - 0 Here Z hides universal multiplicative constant and polylogarithmic factors of d, 3: 2 and 1; the accuracy guarantee holds with large constant probability. We can interpret this result as showing that the additional cost of privacy is small provided that the user has a strong a priori
Given two covariance matrices A, B E ied the notation A A B indicates that in every direction E igd the variance o Be is at least as large x" Ae. More generally, A A B iff B A is positive semidefinite. "To simplify the discussion, we focus only on the e parameter, although our results and many of those we discuss require relaxations of differential privacy such as approximate (28 or concentrated [26 g differential privacy, which have different parameterizations.
2

---

bound on the covariance so that K is small (e.g. K is a constant), and also that the privacy guarantee is not too strong (e.g. E 2 a). particular, setting
corresponds the known- nhow--covariance setting, where the guarantee in ①T is known to be minimax optimal up to polylogarithmic factors 32 41 among all differentially private estimators.
However, the sample complexity in ① grows asymptotically with vK. a large price to pay for the user's uncertainty. Intuitively, this degradation arises because the algorithm perturbs the empirical mean Me with noise from a spherical Gaussian distribution, whose magnitude must be proportional to the largest variance in any direction, so the noise is unnecessarily large in the directions with small variance. In contrast, when the user is very uncertain about the covariance, there are estimators with weaker dependence on but a superlinear dependence on the dimension. In particular, there an estimator [41 Theorem 4.3] with an enror guarantee of the form
d d d log
||A()) pllss a.
(2)
50
Here 2 hides a universal multiplicative constant and logarithmic factors of d, 1 log KG and p. where ||a||2 S po; the accuracy guarantee holds with large constant probability. Without any prior information about the covariance, the best known approach is to estimate the mean by learning the entire distribution- both mean and seariannce-hichee is the more difficult task considered in [2] Theorem 4.6]. Doing so incurs an even worse dependence on the dimension:
at
d2
d2
|l(())
p|ا S..
QE
Here 2 hides a universal multiplicative constant and logarithmic factors of and 1, the accuracy guarantee holds with large constant probability.
a
The Covariance-Estimattio Bottleneck. The bottleneck in the algorithms above is privately obtain- ing a good spectral approximation to the covariance, i.e. a matrix A such that A Σ = 2A. With such an estimate, one can apply the known- covorrcoveei approach in (T). Without privacy constraints, the empirical covariance will have this spectral-apprott approxxiappoooiiooonnn property when the sample size is Z d. However, all known private covariance estimators require n = ((d/22) samples, and there is evidence that this is an inherent limitation, as (2d5/22 samples are necessary for solving this task for a worst-case data distribution 31
Our Work: Sample-Efficiee Efficient Private Mean Estimation. We circumvent this apparent difficulty of covariance estimation by designing algorithm that adapts the noise it adds to the distribution's s covariance without actually providing an explicit covariance estimate, nearly matching the optimal sample complexity ① for the known-covariance setting.
Theorem 1.1 (Informal). For a S 1, there is an (e, 5)differrnttial private estimator A(-) such that if x = (I1...., zn) are from (p, Σ) for unknown p and E. full rank,
d
log (1/8) = ||A(z) 1ll= a.
a
aE
The above guarantee holds with high probability over the sample x and the randomness of A. Here z hides a universal multiplicative constant and a logarithmic factor of 1.
For the formal statement, see Theorem 3.2 Our estimator is based on privately sampling a point of large Tukey depth. Tukey depth generalizes the notion of quantiles to multiple dimensions; is known to be a good robust estimator of the Gaussian mean. The natural way to sample such a point privately use the exponential mechanism (as in the concurrent work of (47). ). but sampling from a distribution over the entire domain Rd will not have finite sample complexity. Our innovation to sample from a data data-depender domain consisting only of points of large Tukey depth, which necessitates careful preprocessing and privacy analysis.
We emphasize that the sample complexity of this estimator is optimal up to polylogarithmic factors. However, the estimator is not computationally efficient. An interesting open problem is to design an estimator matching the guarantee of Theorem I.I with running time polynomial in the dimension.
Beyond Gaussian Distributions. A natural question is how much the assumption of Gaussian data can be relaxed without blowing up the sample complexity. Our second result is alternative
3

---

estimator, based on completely different technique, that will give a similar guarantee for any distribution with subgaussian tails. For our purposes. we say that P with mean I and covariance Σ is subgaussian if, for every direction E TR, the tails of the distribution decay as fast as a univariate normal distribution with mean u² μ. and variance Cu Eu for some constant C. That is, for every X, B[eAu"(P-H)) (P-#)] < e (u)/222u)/2 Eu)/2, More generally, our estimator works for any distribution such that the empirical covariance matrix converges rapidly to the population covariance matrix and typical samples are close to the mean in Mahalanobis distance.
Theorem 1.2 (Informal). For a I 1, there is an diffferrrell private estimator A(-) such that if æ (01.. are sampled from any subgaussian distribution with unknown mean y and unknown covariance E of full rank,
dloo((1/)) - -
n 2 a²
+
ae
The above guarantee holds with high probability over the sample x and the randomness of A. Here 2 hides a universal multiplicative constant and polylogarithmic factors of d, 1. and 1 a'
This estimator is based on another simple approach- we perturb the empirical mean 14 with noise scaled to Σz, where Eg is the exact (not private) empirical covariance. We show that this approach satisfies differential privacy if the data set satisfies certain concentration properties, which we enforce using a careful preprocessing step.
For the formal statement, see Theorem 4.4
Both of our estimators generalize beyond Gaussian distributions in different directions, not fully captured by our theorems. Although the Tukey depth estimator will only return an approximation to the mean when the distribution is symmetric and will not generalize to arbitrary subgaussian distributions, returns an approximate median for distributions satisfying some natural regularity conditions. In contrast, the empirically rescaled estimator generalizes to distributions that are well-concentrated, in the sense that typical samples from the distribution are close to the mean in Mahalanobis distance with respect to the empirical covariance, which captures much more than just subgaussian distributions. Exploring the extent to which each estimator can be generalized is an interesting direction for future work.
Limitations. Our estimators are not computationally efficient. We provide finite implementations which construct and search over sufficiently fine grid, resulting in running time exponential in the dimension d and sample size n. We also stress that the error guarantees of our estimators only hold for families of distributions which satisfy certain regularity conditions, as described above. We leave these two interesting directions of improvement to future work.
Societal Impact. Since our algorithms are inefficient, they will not see practical use without further research. More broadly, our work serves the goal of increasing the array of differentially private algorithms, and thereby enables safer access to privacy- priviiy-sensttive data. Although such tools might support corporations and governments in harmful data-collection efforts, we believe that the existence of these tools is beneficial on balance.
1.1 Techniques
Tukey-depth Mechanism. Our first algorithm adapts a well-known approach to estimating the location of distribution with differential privacy. Briefly, we sample from the distribution defined by the exponential mechanism (50) based on the Tukey depth, but restricted to a data-dependent set of possible outputs-those points with Tukey depth at least z. To ensure differential privacy, we add private check that the data set is "safe," " which we perform before rumning the main mechanism.
In more detail, our starting point is the exponential mechanism [50]. In this context, the exponential mechanism samples a point y e IRd from the distribution with probability density roughly proportional to exp(- (=;( y)), where ((r;; y) is score function that indicates how good a match y is for the data set at hand. To instantiate the mechanism, one must choose (i) a score function that rewards values y that are close to mean jı in the unknown Mahalanobis metric, and (ii) set of candidate values from which to sample. For (i), we choose ( y) = nTT, (y) where T. is the Tukey depth of a point, defined as
Tx = min
{ [z E x (o u) 2 (2. 1/}
(4)
veRd

---

For normally distributed data, the Tukey depth ranges from O (outside the convex hull of the data points) to about 1/2 (near the mean μ)). The point of maximal Tukey depth, called the Tukey median, is well-known as a robust estimator of the mean of a Gaussian distribution. In general, the expectation of Tukey depth over the draw of the data can be cleanly described terms of the Gaussian cumulative distribution function. See the supplementary material for further technical details.
Using the exponential mechanism with Tukey depth as the score function is well-established idea. In one dimension, it is now the standard algorithm for approximating the median (e.g. (54), and its high-dimensional variant was studied in previous 43 and concurrent 47 work However, on its own, it is not sufficient for our needs. The challenge is in specifying the set of potential outputs from which we sample (step (ii) above). In order to reliably output value y such that |1y/ - م is small, we must sample from set of outputs with E-norm that is not too large. For that, however, it would seem that one needs rough approximation to Σ, which is exactly what we want to avoid.
We circumvent the barrier by sampling from a data-defined set without releasing a description of that set. Specifically, consider the algorithm which samples from the exponential mechanism restricted to points with Tukey depth at least 1/4. A standard concentration argument shows that this set is roughly the ellipsoid {v : lly ællI S. c} for modest constant c. Running the exponential mechanism on this set returns a good approximation to the mean (with Σ-norm o(1)) when n = w(d/e).
This gives an accurate algorithm, dubbed M. The remaining challenge is that M is not, on its own, differentially private. Specifically, there are data sets z for which the volume of the set of Tukey-depth-1/4 /4 points changes drastically when a small number of records in address this, we identify a set of safe data sets x rhehee are data sets such that M behaves similarly on all data sets x' that are neighbors of x. We show that normally distributed data sets typically safe and, furthermore, require many insertions or deletions of records to be made unsafe. This allows us apply the prapose-test-relaass (PTR) framework of (25) to obtain an algorithm that is accurate for nicely distributed data and differentially private in the worst case.
changed. To
Our modification of the exponential mechanism is quite general. It is similar in flavor to the GAP- MAX variant [TT 58 15 as well as the top-k-offk' approach of [24]. However, we do not know how to obtain our results using those variants since they are specific to the discrete setting and appear to require knowledge of the volume of the level sets of the score function. Such knowledge is not obviously available our setting.
Empirically Rescaled Gaussian Mechanism. The well-known Gaussian mechanism perturbs the empirical mean μı with noise drawn from (O., dfI)., for scale parameter a that is chosen based on a priori information about the data. In particular, d² must scale linearly with |Σ the maximum variance in any direction. Since the noise is spherical, the error will be too large in directions with small variance, and so this mechanism cannot in general achieve a good estimate in Mahalanobis distance.
Our approach relies on the following simple idea: If the data set x drawn i.i.d. from ([(,, 2)) and the number of samples is a bit larger than the dimension d, then the empirical covariance Σn is good approximation to the true covariance in spectral norm. When this holds, perturbing fzz with noise drawn from (00 I² for C < 1 will be a good estimate of the mean in Mahalanobis distance. va Thus, want to understand when perturbing Mr in this way can be made differentially private.
Adding noise from A C² will not be private for worst-case data sets. To see this, consider a pair of adjacent data sets, one of which lies in proper subspace of dimension d - 1 and the other of which has full rank. For one of these data sets, our mean estimate will always lie in the proper subspace, while for the other it will lie outside of this subspace with probability 1, making the two cases easy to distinguish.
'We became aware of Liu et al''s work (47 while we were working on this project. Our empirically rescaled Gaussian algorithm is entirely independent of their work, but the presentation and parts of the analysis of our Tukey-based algorithm were influenced by their approach. Liu et al. consider, among other algorithms, version of the Tukey depth algorithm where one samples from fixed box whose dimensions are determined by a priori bounds on the covariance matrix. We analyze a more complex procedure, where the set from which one samples is data data-dependent. Liu et al. aim to solve a different problem from the one we address here, but the two analyses overlap (notably in volume computations and concentration arguments that relate empirical Tukey depth to the underlying distribution).
5

---

Our main observation is that such pathological examples should not arise when the data sets are sampled from a distribution, such as a Gaussian, that satisfies strong concentration properties. For example, if x and x' are adjacent data sets of i.i.d. samples from the same Gaussian, then jrr and fax will be similar, as will Ex and Ez,. To take advantage of these nice distributions, we define a family of "good data sets" that captures certain properties of typical samples from a Gaussian. Roughly, data set æ is good if 2ig is invertible and, for every zs. || - Mu lI,, S v log n. Our main technical contribution is to show that if and x' differ on small number of samples, and both data sets are good, then their empirical means and empirical covariances are close. Thus, Mx + +O C²E,) and Me + N[O, C² will be indistinguishable in the sense required for (E, d)dffferrett privacy.
However, we need define our estimator on data sets that are not good in such a way that the estimator will be differentially private in the worst case. To do so, we privately test whether the imput data set lies close to the good set and, if needed, we project the data into the family of good data sets. This preprocessing step will have no effect when the data is Gaussian, and any pair (Gaussian or not) of adjacent data sets x and x' will be mapped to a pair of good data sets F and H' that differ on a small number of examples.
This projection step is stated abstractly in Algorithm 2 finding the minimizer over an infinite family of data sets. In the supplementary material, we present a concrete, exponential-tin time algorithm that searches over a discrete grid of candidate datasets. We leave the task of identifying more efficient algorithms as an interesting problem for future work.
1.2 Additional Related Work
Differentially Private Mean and Covariance Estimation. The line of work most relevant to ours was initiated by Karwa and Vadhan 44), who established optimal private mean and variance estimators of univariate Gaussians with sample complexity O(1/a² 1//E), without requiring priori bounds on the parameters. Previously, Smith [54] gave estimators for asymptotically normal statisties (which include the mean of a Gaussian) with optimal convergence rates for certain range of privacy parameters. In the multivariate setting, a series of works [1 2 gives algorithms for Gaussian mean estimation with known covariance that have near-optimal sample complexity of Od/oa² 2 + d/az). We note that [2] obtain the best bound among these works, but the guarantees of the estimator from [41] extend naturally to subgaussian distributions as well. [12] also studied mean and covariance estimation of subgaussian distributions, but their setting requires strong a priori bounds on the parameters. In concurrent work, [39] give a differentially private estimator for our unknown parameter setting which, for the same sample complexity ours, has error guarantee of l| /ll2 I x||E//2 22. This result is strictly weaker than ours. However, their estimator, in contrast to ours, has the pleasant property of being computationally efficient.
Beyond Saubsaan distributions, 4, study differentially private mean estimation under weaker moment assumptions.
In addition to the work we discuss in the introduction 41 recent work focuses on practical private mean and covariance estimation in univariate (23 and multivariate (5) settings, although these approaches still require explicit private covariance estimation. Dwork et al. [31] gave a lower bound of ((d3/2) for privately estimating the empirical covariance, albeit via a non- Gaussian distribution. Together, these results serve as evidence that (dd2/2 samples are necessary for private covariance estimation for Gaussian data well.
Robust Statistical Estimation. Robust statistical estimation 1960 (56) and remains an active area of research [18 mating distribution parameters when an a-fraction of the data may be adversarially corrupted. As noted by Dwork and Lei (55 robust statistics and differential privacy have similar goals, and private estimators are often inspired by robust estimators, but the models are formally incomparable.
40
which dates to at least studies the problem of esti-
20
22
38
More recent work aims to give algorithms which satisfy both constraints simultaneously 47 35 Specifically, independently from our work, Liu al. [47] propose a simple mechanism for Gaussian mean estimation with known covariance, given c-corrupted data sets and priori bound on the range of the mean || < p. This estimator has sample complexity Ó(d/a² + d d p/os). The algorithm runs the exponential mechanism (50) the given range, using the Tukey depth of a point as its score. We observe that the same mechanism gives solution for the problem study-men

---

estimation in Mahalanobis distance with unknown covariance and no corruptions bustoonss-uuttt but this solution requires priori bounds on the mean and covariance, which are not required by our algorithms.
2
Preliminaries
We write æ ~ P to denote that a drawn from distribution P and x ~ p x consists of n i.i.d. draws from P. We write [n] {1, .I,...,00 n). We define the Hamming distance between two data sets y of size n. by Du (x. Hi [n] xı + 3. For data set and set S C Raxd, we write Du (r. 5) minzes DH(5, 2).
Let x'' E X be two data sets of size n. We say that x' are neighboring data sets if DH (I,x') x') S x'. Differentially private algorithms have indistinguishate output
and denote this by distributions on neighboring data sets.
Definition 2.1 ((E, (ee,6)-indisee indistinguishability. Two distributions P.Q. over domain W are (E, indistinguishable denoted by #e,6 Q. for any measurable subset W C.W,
Pr w E W] e Pr (w E W] d and w~P
w>Q I S E Pr Pr. W] +
Pr
w~Q
w-P"
Definition 2.2 (Differential Privacy (291). randomized algorithm A: X - W is (c,
differentially private for all neighboring datasets x, x' we have A(x) Re, A(x').
We next describe well-known mechanisms which serve building blocks for our algorithms.
Lemma 2.3 (Laplace Mechanism (29). Let f N R. data set X and privacy parameter
The Laplace Mechanism returns f(x) f(z) + Lap(AA/E)) where D5 max If(x)) f(x')
is the global sensitivity of f. The Laplace Mechanism is (s, 0) d)-iifferentially private.
Lemma 2.4 (Gaussian Mechanism (29). Let
X + RRd. data set x X", and pri- The Gaussian Mechanism returns f(x) f(x) + NN ofI), where
vacy parameters
A 2 loog(5/8))/ and D = maXgww' [xf(x) f(x')l2 is the global & ég-sensitivity of
f. The
Gaussian Mechanism is (e,
( difffrrennll private.
3 Tukey Depth Mechanism
We start with score function q(æ; y) and wish sample from the exponential mechanism, pro- portional to exp (s q(:;; 2)) but restricting the sampling to the set of points with score at least i. Denote this set Vr.= (y E ) g(;; y) 2 1) and call the resulting distribution M..e(.).. Unfortu- nately, sampling directly from (x) may not be private. To address this, we try to sample only from data sets that "safe" with respect to privacy, i.c., have distributions that are indistinguishable from those of their neighbors.
Definition 3.1 (Safety). Data set is (e,5,t)-safe if. for all x' x. we have Me,((z) Re,8 Me,((z)). Let (A.E C X be the set of safe data sets, and let UNSAFE = Xn (AFE be its complement.
Following the propose-test test-release framework of (25). check if the input is far from INSAFE Since the distance check itself is private and indistinguishability is the definition of safety, the proof of privacy becomes straightforward. Such abstract definition, however, does yield much insight into what safe data sets look like. Below, we show that one can establish safety via a simple condition on the volumes of sets of the form Vety, (for certain values of 17), which allows us show that Gaussian data are far from (e, with high probability.
Algorithm 1 Restricted Exponential Mechanism A
Require:
Data space X. Output space Yu (PAIL). Data set X Score function q X x x R. with global sensitivity in the first argument. Privacy parameters e, 8 > O. Minimum score t. h DH UNSAFE
2: if h log(1/25) for Lap(1/s) then return FAIL.
3: return (z)( where Me,((z)
exp
sg(2:0)
if y V4, otherwise

---

3.1 Main Algorithm
We estimate the mean by instantiating Algorithm I with t n/ / and score function g(2; y) (y). where To (1) is the (empirical) Tukey depth, defined in Equation 4 Observe that nT=(y) has sensitivity since for any halfspace the fraction of points it contains can change by at most when we change one data point.
Theorem 3.2 (Privacy and Accuracy of the Tukey-Dephl Mechanism), For any E, 8 > 0, Algorithm 7 is (2z, e 8)-fifferentially private. There exists an absolute constant C such that, for any 0 < a, B, 1, < S 2, mean μu, and positive definite Σ,, if x N (1, x))² and
n nzo C ( + (og(11)) c. d.log(1/0)) 1/))///)/))))()) - 1og(1/B) 1og(1/6)
(5)
a²
then with probability at least 1 33, Algorithm 7 with q(x;)) y) nyT returns AR ( j
such that [/ ıllx S a.
We focus here on the accuracy analysis. Privacy follows from standard propose-test-relesse calcula- tions 225 which we include in the supplementary material.
3.2 Accuracy Analysis
The proof of accuracy proceeds in four stages. Using standard analysis, we first relate the empirical Tukey depth of point y its Mahalanobis distance | - sulls: via the expectation of Tukey depth under N ((,, E). Since Tukey depth is defined as minimum over halfspaces, which have Vapnik- Chervonekis dimension d + 1, one can show via uniform convergence that the empirical measure concentrates around its expectation. This portion ends with a standard lemma relating the sets Vnp... where p E (0, 1/2), to ellipsoids defined by Mahalanobis distance.
The remaining three steps, which are new to this work, begin with a characterization of the set SAFE defined above, which provides conditions under which a data set is far from UNSAFE. We discuss this in more detail below. The third stage uses that characterization and the tools we developed to show that Gaussian data is typically far from UNSAFE, establishing that Algorithm [ Thas small probability of returning FAIL. Finally, conditioned on Algorithm ① not returning F FAIL, a similar analysis shows that with high probability the restricted sampler Mc.(()) returns point with high empirical Tukey depth. Together, this yields a bound on the Mahalanobis distance to the true mean.
A Volume Condition for Safety We consider sets of the form Vitn, for moderate positive and negative values of n) Recall that Vetn.e is the set of all points y with score q(:; y) = nTT, 2 + 77. ie.. having empirical Tukey depth with respect to z at least (t + n)/nn. Therefore, as 1) becomes smaller, the set Vitn.a grows. We show that, if the volume of Vetn, does not increase too quickly as decreases, then x is far from every data set in UNSAFE In particular, this implies that x itself in (A.) These lemmas do not rely on specific features of Gaussian data or Tukey depth, which enter in only in the last two stages as described above, when we argue about typical data sets.
Before arguing about volumes directly, we sketch the proof of lemma about the weight as- signed to sets by the exponential mechanism. For any set S C y. denote its weight by w. (S) = exp
exp =q(xrv) 2
dy.
Lemma 3.3. Assume 8 < 1.2 If (w((1))1)) 2 (1 (1--8wwpp (0-1((1)11)) then x E SAFE 3)) for 8' 4c
Proof Sketch. For an arbitrary adjacent x', we must establish that the distributions Mca(x) and (a.( are (e, iiiiiinnittiggulhaallle.. The proof is elementary but non-trivial: our hypothesis only concerns x, not its neighbors. To illustrate, we show that Pr[Me,, definition, supp(MM,((z') = =Vr,a'. Now we move from x' to æ: the score function has sensitivity 1, so every point with q(x;)) 2 ++t satisfies q(x': y) 2 t. Thus Ve-1,z S V.,,,, and we have
& supp(Me..(z))) < 8'. By
We (14+1.2)
(x) & supp (x'))) S Pr[ (r) $ Vet1,))
War (Vi..))
Since Vr.rr C V-1,., wa (Vrzz) V ( and our hypothesis implies Pr Pr(Me,(()) & supp(Ma,, (x)))))))))))))))))))))))))))( < 6, which is less than d' 4e 6.
8

---

The rest of the proof requires similar (but slightly longer) calculations.
We now use this lemma to establish when data set is far from the set of unsafe data sets. Note that setting k = O below implies for all E UNSAFE that we have Du (v, =) > O, i.e., x E SAFE.
Lemma 3.4. For any k 2 O, if there exists a > such that -o all (N, (e,8',)) .y with 8' ô, have DH k
Vol)++*-0+1.a) - ===9/ S 6, thenfor
Proof. Take some distance most from (if 1: We have, from Lemma 3.3 that if m² (x(Vet - 6, then is safe. This assumption is equivalent we (1)
2 x). We show SAFE
( \ (x(Di-1,a)
< which is the form we use.
First we lower bound the denominator:
W/ (Di-1,a) 2 wa (Vt+o++1.)) 2 (olD)++ot..)eetttttt) 2 1
where (crucially) the last inequality switches to the volume under x, and we have used the sensitivity of q. We use the same idea the numerator, switching to volume under in the first inequality:
(.+----.eW We (1'--, W1411,s & wz (1 W141.) & 1e
With an upper bound on the numerator, a lower bound on the denominator, and the fact that 20411//2
-88/2 we have
w' (D--1,2 (1H1,2)
Vol()i-x-1,z) 66 -89/2 S6
w² ()(-11,)))
Vol((++++t11.)
so 2 E SAFE
With these tools in hand, in the supplementary material we show that, if w(d/s), typical Gaussian data satisfy the hypothesis of Lemma 3.4 for n/8 and thus are far from unsafe (implying that we are unlikely to return FAIL) and that with high probability the restricted sampler (a)) returns point with high Tukey depth.
4 Empirically Rescaled Gaussian Mechanism
In this section, we describe our second estimator. At high level, the estimator first privately checks whether the data set -clloee in Hamming distance to a good set "roughly Gaussian" data sets (()). If so, it finds the closest data set to æ that belongs in G()), which we call 5. Then returns sample f drawn from (Jug, C²Ez), where μa and Σg are the empirical mean and covariance and C' is a scale parameter appropriately set to ensure privacy. Specifically,
the definitions:
Definition 4.1 (Empirical Mean and Covariance). For data set x R3axd the empirical mean and covariance of x are respectively defined by (lg = Di=1 T442n and Eg = 2n Dz [x+ DT+n)T T.
In comparison with the standard empirical estimators, ours enable simpler privacy analysis, since replacing one datapoint in x only affects one term in one of the sums. For convenience, we choose the number samples be 3n so that we can pair the first two thirds to construct Σ, and use the last third for Mr. With these definitions at hand, the good set (()) is defined as follows:
Definition 4.2 (A-goodness). For any X 0, define (()) IR xp3xx
(())
d {ar I 333dd d Eng invertible and Vi [3n] ||= - Mr 12, S SA}
We set dloog n, since for this value (sussaansiian data will belong in ( with high probability. Finally, we note that the algorithm immediately aborts if the number of samples is less than AA 188) dlog(1/6) condition necessary to ensure privacy.

---

Algorithm 2 Empirically Rescaled Gaussian Mechanism A A,
Require: Data set = (II,...., x3n)² E 3xxd Privacy parameters e, >> 0. Failure probability
B > O.
1: Initialize: X 4-0 O (dlog 3). + log B k +- log 53 + 1, C2
326 E'n 1-2kX/n
log 1.25 6
LAA 2: if ( log :) then return FAIL.
3: I (xx
random permutation a (R + (R2)) P distance between and X-goodness
4: h h ((A))
5: h > t for ~ Lap (1/c) then return FAIL.
6: 5 arg mrgmin (5,2)
projection X-goodness
7: return (us, C²
We remark that the sample size check in line and the setting of À are not well-defined, as they are stated with asymptotic notation. Although it is possible compute the constants for these steps, we exclude them in favor of cleaner analysis.
We prove accuracy for the following family of distributions:
Definition 4.3 (Subgaussian distribution). Let P.. be distribution over IR with mean and covariance E > O. For a constant c O, we say that Pu.z: subgaussian with parameter cL, for all _ such that ||u||2 Pu..P. (v-M)) S ex"(""Ea))3 for all X E R.
We write Pu.x E (cbG The definition appears in relevant literature 48 22 and intuitively asks that the distribution concentrates "at least as well" as a Gaussian along every univariate projection.
We now state the guarantees of Algorithm 2
We defer their proof to the supplementary material.
Theorem 4.4 (Privacy and Accuracy of the Empirically Rescaled Gaussian Mechanism). For any private. There exists absolute constant C such that, for any 0 a, e,,, < 1, mean μ., and positive definite E, if E.E where Pa,z subG(cE) for some constant 0, and
> O, 0 8 < 1, Algorithm is (3s, e (1 + )
d
1 d 3
1
dlog(1/88)
n C
log
log
log
(6)
asa
83
then with probability at least 1 33, Algorithm
returns AC (z) = fa such that |1 - pllx S a
Acknowledgments and Disclosure of Funding
We thank the anonymous NeurIPS reviewers for useful suggestions the presentation of this manuscript. Gavin Brown and Adam Smith were supported in part by NSF award CCF-1763786 as well Sloan Foundation research award. Marco Gaboardi was supported in part by NSF award CCF-2040222. CCF-17 11F--71185 1718220, CNS-1565365, and CNS-2040215. Jonathan Ullman and Lydia Zakynthinou were supported by NSF grants CCF- 1CF-1750640, CNS-1816025 and CNS-1916020. Lydia Zakynthinon was also supported by Facebook Fellowship.
10

---

References
[1] John M Abowd. The US Census Bureau adopts differential privacy. In ACM International Conference Knowledge Discovery & Data Mining, KDD 18, pages 2867-2867, 2018.
[2] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Proceedings of the 32nd International Conference Algorithmic Learning Theory (ALT 2021), ALT 21. JMLR, Inc., March 2021.
holl.httss://ee //rpxvv./ .rgg abbs/010... 09929
[3] Apple Differential Privacy Team. Learning with privacy at scale. Apple Ma-
chine Learning Journal, 1(8), 2017. http:://maachinneeearnnnngg apppll.ennnappe....eeeeeemmeee wtt.ccooocaaaoeeeee
scale/
pdf
[4] Rina Barber and John Duchi, Privacy and statistical risk: Formalisms and minimax bounds. arxiv preprint arXxi:1442.444 12 2014.
[5] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. COINPRESS: Practical Private Mean and Covariance Estimation. In Advances in Neural Information Processing Systems, NeurIPS '20, 2020. hatts://arxiv/ org/
06618
[6] Andrea Bittau, Ülfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. PROCHLO: Strong privacy for analytics in the crowd. In ACM Symposium on Operating Systems Principles, SOSP 17, pages 441 459, Shanghai, China, 2017. attts:://axivy org/ abs/ 17100 00901
[7] Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is memo- rization of irrelevant training data necessary for high-accuracy learning? arXiv, 2012.06421, 2021.
[8] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, TCC '1, pages 635-658, Beijing, China, 2016. https: /ttp///axvvv///////////ee//aaavr httaaaaivvvoggg/e//// www./ogg////aeeeeee/oo wtwpaaass......//1
[9] Mark Bun and Thomas Steinke. Smooth sensitivity, revisited. Manuscript, 2019.
[10] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approxi- mate differential privacy. In ACM Symposium the Theory of Computing, STOC 14, pages 1-10, New York, NY, USA, 2014. https: /ttps://arxxii www/obs/////eoooooog/...o...eert aaaaaaa/1/ //1111111111 3158
[11] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. In Advances in Neural Information Processing Systems, NeurIPS '19, pages 156-167. Vancouver, Canada, 2019, htttps://axxi..oo owt.:ws..gbbbbbbbb 19///19955.. 13229
[12] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint
2019.
[13] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernjj Kos, and Dawn Song. The secret sharer:
Evaluating and testing unintended memorization in neural networks. In {USENIX) Security Symposium, ((USENIX) '19), pages 267-284, 2019. https://arte org/abs/
[14] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voor Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models, arXiv preprint arXiv:2012.07805. 2020.
[15] Lue Devroye and Gábor Lugosi. A universally acceptable smoothing factor for kernel density estimates. The Annals of Statistics, 24(6):2499 2512, 1996. doi: 10.1221//os/1002218 164.
[16] Luc Devroye and Gábor Lugosi. Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. The Annals of Statistics, (5(6):2626 2637, 1997. doi: 10. 121 2/4//os// 1030741088, URL htt.s:tps/// /tt.///oi..oo org/ 10. 1214/ 2014///001000771118888

---

[17] Luc Devroye and Gábor Lugosi. Combinatorial methods in density estimation. In Springer series in Statisties, 2001.
[18] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In IEEE Annual Symposium on Foundations of Computer Science, FOCS '16, pages 655-664. IEEE, 2016. https://arxiy: org/ abs/ 1604. 06443
[19] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, ICML 17, pages 990-1008, 2017. https://arxi:: http///rxii..orgga////////
00893
[20] 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 29th Annual ACM-SIAM Symposium Discrete Algorithms (SODA 2018). SODA '18, Philadelphia, PA, USA, January 2018 SIAM. URLhttps: //axxps://rrxiv.. org/ wtwgab////aaaa...o.og/o/gee ab////0// 1704. 03866
[21] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems, PODS '03, pages 202-210. ACM, 2003.
[22] Yihe Dong, Samuel Hopkins, and Jerry Li. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL / /ttpap///01///iA/A///22222111111 /atp////2...11177444000003333133 Paper. pdf
neurips
[23] Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differentially private confidence intervals. arxiv preprini urXiv:2001.022865 2020.
[24] David Durfee and Ryan M Rogers. Practical differentially private top-k selection with pay- what-you-get composition. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL ptatt::://proceeenng...n http:///g/.rrrppppc//////////// http://.....0111000a000000oeeoe. Paper pdf
[25] Cynthia Dwork and Jing Lei. Differential privacy and robust statisties. In Proceedings of the 41st ACM Symposium on Theory of Computing, STOC '09, pages 371-380. ACM, 2009.
[26] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint 1rXiv: 01800, 2016.
01887
[27] Cynthia Dwork and Sergey Yekhanin. New efficient attacks on statistical disclosure control mechanisms. In Annual International Cryptology Conference, pages 469-480. Springer, 2008.
[28] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT '06, pages 486-503, St. Petersburg, Russia, 2006.
[29] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Conference on Theory of Cryptography, TCC '06, pages 265-284, New York, NY, USA, 2006.
[30] Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of LP decoding. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 85-94. ACM, 2007.
[31] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Zhang. Analyze gauss: optimal bounds for
principal component analysis. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC '4, pages 11-20, New York, NY, 2014. ACM.
12

---

[32] Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan. Robust traceability from trace amounts. In IEEE Symposium on Foundations of Computer Science, FOCS 15, 2015.
[33] Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preservigg ordinal response. In ACM Conference on Computer and Communications Security, CCS '14 2014.
[34] Vitaly Feldman. Does learning require memorization? A short tale about a long tail. In ACM Symposium on Theory of Computing, STOC '20, pages 954-959, 2020. https: arxxiv org/ abs/1906. 05271
[35] Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Thao Nguyen. Robust and private learning of halfspaces. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1603-1611, PMLR, 13-15 Apr 2021.
[36] Samuel Haney, Ashwin Machanavajihala, John M Abowd, Matthew Graham, Mark Kutzbach, and Lars Vilhuber. Utility cost of formal privacy for releasing national employer-employee statisties. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17, pages 1339-1354, Chicago, IL, 2017. ACM.
[37] Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muchling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Re- solving individuals contributing trace amounts of DNA highly complex mixtures using high-density SNP genotyping microarrays. PLoS genetics, 4(8):e1000167 2008
[38] Samuel B Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. arxiv preprint arXiv:2007.15839, 2020.
[39] Ziyue Huang, Yuting Liang, and Ke Yi. Instance-optimal mean estimation under differential privacy, 2021.
[40] Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
[41] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high dimensional distributions. In Annual Conference Learning Theory, COLT 199 JMLR.org. 2019.
[42] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2204 2215.22235.221 PMLR, 09-10 Jul 2020. URRp mlr. press/v125/ kamath20a. html
[43] Haim Kaplan, Micha Sharir, and Uri Stemmer. How to find a point in the convex hull privately, In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, volume 164 of LIPlcs, pages 52:1-52:15. Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2020. doi: 10.4230/LIPIcs. SoCG.2020.52. URL https: //doi org/ 10. /ww./2222........ SoCG. 2020. 52.
[44] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Proceedings of the 9th Conference on Innovations Theoretical Computer Science, ITCS 11, fuer Informatik.
pages 44:1-44:9 Dagstuhl, Germany, 2018. Schloss Bhgsstul-Leibniz-Zznae
[45] Shiva Prasad Kasiviswanathan and Adam D. Smith. On the 'semantics' differential privacy:
A bayesian formulation. Journal of Privacy and Confidentiality, 2014.
[46] Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC '10, pages 775-784. ACM, 2010.
13

---

[47] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. arXiv preprint arXiv:2102.09/19, 2021.
Gábor Lugosi and Shahar Mendelson. Sub-Gaussian estimators of the mean of random vector. The Anmals of Statisticx, 47(2):783 794, 2019. doi: 10.121411-AOSS133) URL [48]
https://doli org/100..00... 1214/17 ADS1639
[49] Ricardo A Maronna, R Douglas Martin, Victor J Yohai, and Matías Galibián-Barres Robust statistics: theory and methods (with R). John Wiley & Sons, 2019.
[50] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy, In IEEE Symposium on Foundations of Computer Science, FOCS '07, pages 94-103, Las Vegas, NV, USA, 2007.
[51] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. Linkedin's 's audience engagements api: A privacy preserving data analytics system scale. arXiv preprint arXiv:2002.05580 2020.
[52] Sriram Sankararaman, Guillaume Obozinski, Michael I Jordan, and Eran Halperin. Genomic privacy and limits of individual detection in pool. Nature genetics, 41(9))965-966 2009.
[53] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy (S&P), Oukland, 2017.
[54] Adam Smith. Privacy-preserviv statistical estimation with optimal convergence rates. In Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing, STOC '11, pages 813 822, New York, NY, USA, 2011. ACM.
[55] David Tastuggine and Ilya Mironov. speed library for training PyTorch vacy. Facebook introducing-opaeee wwwpgg--ppuusssee high-speese with wwwddrdentiallpprieeee privacyy
Introducing Opacus: A high- models
with differential pri- https://ai facebook. com/blgg/
Blog, 2020.
pytorch-models: horp:-/pppe--bbbrrr-oooottaaaaaa oograa--oooo-aaaaig.oooooooooo..
[56] John D. Tukey. A survey of sampling from contaminated distributions. Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling, pages 448-485 1960.
[57] Royce Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons- Marengo, and Bryant Gipson. Differentially private sql with bounded user contribution. Pro- ceedings on Privacy Enhancing Technologies, 2020(2):230-255) 2020. https://arxiv..r orrg
(58) Yannis G. Yatracos. Rates of Convergence of Minimum Distance Estimators and Kolmogorov's Entropy. The Annals of Statistics,, 13(2):768 - 774, 1985. doi: 10. 00.121//ao//116334955 URL https: :/doi. wrg/10..... 1211 aos aae.a//////11000 1176349553
[59] Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In JEEE Computer Security Foundations Symposium, CSF '18 pages
2018. https::/arre: http///xxvv.rr//abbbe wwwp/aa/////////// 01604
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] addition to the discussion of
the assumptions in our theorems, see the "Limitations" paragraph in the introduction.
(c) Did you discuss any potential negative societal impacts your work? [Yes] Please see the "Societal Impact" paragraph in the introduction.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Our formal theorem statements, Theorems (32 and explicicy specify our assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are contained in either the submission or supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "PwC4lwvUDr", "reviewer": "Reviewer_8L9y", "summary": "This paper investigates mean estimation of high dimensional Gaussian (and sub-Gaussian) distributions under the constraint of differential privacy (DP). More specifically, the authors aim at privately estimating the mean of a high-dimensional Gaussian in the Mahalanobis distance (w.r.t. to the covariance matrix). \n\nOne simple approach for this task is to first privately estimating the covariance matrix (say up to a constant factor in spectral distance) after which the problem has known solutions. Unfortunately, this approach is suboptimal as estimating the covariance matrix is harder task. Thus, the authors provide a way to circumvent the issue and construct simple estimators whose sample complexity scales only linearly with the dimension.\n\nThe first algorithm is based on combination of the propose-test-release (PTR) framework, exponential mechanism, and the concept of Tukey depth. Roughly speaking, the authors show that by sampling from the distribution defined by the exponential mechanism with a score function based on the Tukey depth restricted to a data dependent set of possible outputs (some points with high Tukey depth), one can get an accurate and private algorithm for mean estimation. In order to maintain privacy while restricting the output to be a data-dependent output set, the authors make use of the PTR framework to test whether the specific dataset is ``safe’’ for use. They then show that when sampled from Gaussian data, a dataset will be safe with high probability, proving that the algorithm will often output an estimate of the mean. Finally, upon success the output will w.h.p. be a point of high Tukey depth, so the estimator is also accurate. \n\nThe second algorithm relaxes the requirement of strict Gaussian data to sub-Gaussian data. This algorithm is also based on PTR framework, with a clever application of \"skewed\" Gaussian noise addition. The standard Gaussian mechanism used in DP adds Gaussian noise scaled equally in all directions. The authors propose to use an additive Gaussian mechanism (to the empirical mean) that adds noise proportional to the empirical covariance of the data instead. Intuitively, this preserves the scale of the data (and thus preserves accuracy w.r.t. to the Mahalanobis distance). While this is not private for worst case datasets, the authors circumvent this by using the PTR to first test whether the dataset is ``good’’ (appropriately defined), and if need be, project the dataset to the set of good datasets before running the algorithm. Finally, they show that with high probability, sub-Gaussian data will be good and there will be no projection, thus the algorithm will output the empirical mean (perturbed with skewed Gaussian noise), that will be accurate w.r.t. the Mahalanobis distance. \n", "questions": "", "limitations": "", "rating": 8, "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 authors have applied techniques such as the exponential mechanism, propose test release framework, and additive Gaussian noise in very clever ways to prove new results for a fundamental problem in DP statistics. The arguments about the privacy and accuracy of the method are sound. The paper is well written and the high level discussions helps with understanding the big picture.\n \nBefore this paper, it was not known whether it is possible to estimate the mean of a Gaussian/sub-Gaussan distribution w.r.t. the Mahalanobis distance under the constraint of DP without first approximating the covariance. Non-privately, the empirical mean works well for this task. Thus, this paper is the first to prove that it is possible to achieve the same in the private case.\n\nWhile the methods proposed in this paper are not computationally efficient, the approach is of broad interest to theoreticians and can be a starting point for the design of more practical approaches.\n\n\n-----------\nupdate after rebuttal: the authors did not specifically respond to my review and I am happy to keep the score after checking out the other reviews/responses.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "PBRZRVmZ1L", "reviewer": "Reviewer_6nea", "summary": "This paper considered the DP mean estimation problem with unknown covariance under Mahalanobis norm. In the known covariance setting, previous work can estimate gaussian mean near optimally. But in the unknown covariance setting, previous algorithms either need to pay an additional conditional number factor, or require d^3/2 samples to estimate the covariance which are both unsatisfactory. The key difficulty of the problem is getting Mahalanobis norm guarantee without first estimating the covariance privately. \n\nThe authors present two different (exponential time) algorithms for Gaussian and sub-Gaussian settings. The gaussian algorithm is based on an exponential mechanism with Tukey depth score. Although this approach has been used in [45] before, they need to choose the sampling region adaptively based on the data in order to achieve a good Mahalanobis guarantee. This brings additional difficulty in making the algorithm private, and they use the classical propose-test-release framework to obtain privacy guarantees. The second estimator uses the empirically rescaled Gaussian mechanism, where the gaussian noise is scaled by the empirical covariance such that Mahalanobis guarantee is naturally achieved. This estimator can be applied more generally on sub-gaussian distribution, though the sample complexity has a d/\\alpha\\eps^2 instead of the optimal d/\\alpha\\eps. \n", "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": "In summary, this paper answered a fundamental question in DP and brings interesting new ideas along the way. I will be interested in the authors’ thoughts on the more efficient algorithms on this problem. \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": "MZ_LV_-Dv1f", "reviewer": "Reviewer_ubCi", "summary": "The paper studies the problem of private mean/median estimation for Guassian and subGaussian variables. In order to reduce the noise required to satisfy privacy, the algorithms tailor the noise to the (unknown) covariance of the distribution, without directly estimating the covariance matrix. This is an important distinction from some prior methods, as privately estimating the covariance matrix is expensive. The methods used combine techniques including the exponential mechanism with Tukey depth, the Gaussian mechanism, and propose-test-release(PTR). While the authors mention that the privacy analysis uses standard techniques, they give a rigorous proof of the utility of the mechanism which they mention uses novel techniques. \n", "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": "Originality:\nMean estimation is one of the oldest problems in DP, and there have been several works developing techniques to improve the utility of mean estimation in DP. One of the key distinctions of this paper is that the noise is scaled according to the (unknown) covariance matrix, without privately releasing the estimated covariance function. As the authors mention, this greatly improves the sample complexity. It also offers much more realistic assumptions on the data generating distribution, rather than requiring tight apriori bounds on the covariance matrix, such as in Karwa & Vadhan. \n\nThe proposed mechanism builds upon several existing DP techniques, including the exponential mechanism with Tukey depth, the Gaussian mechanism, and propose-test-release(PTR). Still, these techniques are combined in a novel manner. More importantly, the utility analysis is novel and this is where the main contributions of the paper are. \n\nQuality:\nThe theoretical results in the paper support both the privacy and utility of the proposed mechanisms. \n\nThe authors suggest that the proposed mechanism is primarily of theoretical interest, as it has exponential running time in both the dimension and sample size. The lack of a practical algorithm limits the work, making it seem somewhat incomplete. \n\nFurthermore, the paper does not have any empirical evaluations of the mechanism. The inclusion of simulations would help to demonstrate the utility of the proposed mechanism compared to prior approaches. \n\nSignificance:\nFrom a theoretical standpoint, the paper provides a novel and important result demonstrating that mean estimation can be achieved privately with much improved utility compared to previous results. Furthermore, the results and techniques could provide building blocks for future researchers to design efficient DP algorithms for other problems. Or, potentially future researchers could modify the techniques of this paper to produce a computationally efficient mechanism with similar utility.\n\nAs mentioned earlier, the lack of a computationally efficient algorithm limits the usefulness of this paper. As the authors mentioned, the proposed algorithm has running time exponential in both n and d, making it entirely impractical for the analysis of real datasets. As such, the results of the paper are currently only of interest to other privacy experts rather than to practitioners looking to implement DP methods. \n\nAnother limitation of the result is that it is framed in approximate-DP. Approximate-DP has been criticized since it allows for a catastrophic failure of privacy with a small probability (approx  delta). Due to this weakness, there has been increasing interest in Renyi-divergence based DP frameworks, which also allow for a relaxation of pure DP, but protect against the catastrophic failure that approx-DP allows. Since the authors are using the PTR technique for their results, I suspect that their results cannot be analyzed using Renyi-DP. \n\nClarity:\nThe authors do a good job of communicating the prior approaches to the problem, and the sample complexity & assumptions of the previous methods. They effectively communicate how their proposed method improves over the prior work in terms of both sample complexity and more realistic assumptions. \n\nThe Tukey depth is introduced in equation (4), but little intuition is given about why it is a useful score function. Some exposition discussing the intuition of Tukey depth, both why it is useful to estimate the location as well as why it is useful in the exponential mechanism would be helpful. \n\nIn Theorem 3.2, it is not clear what is meant by the superscript $\\otimes n$ means.\n\nIn line 303, it is not clear what is meant by Y_{t,x}. I gathered later that this may be the support of M_{epsilon,t}(x), but this should be clearly defined.\n\nConclusion:\nThe paper proposes new DP mean estimation algorithms that improve the sample complexity over previous techniques, and have less stringent assumptions. However, the algorithm proposed in the paper is not computationally practical, limiting the results to only theoretical interest. Nevertheless, the methods of the paper could be of interest to the DP community, and could be potentially used to develop new DP algorithms with high utility. Because I believe that this paper would be of interest to the DP community, I rate it 7 \"good paper, accept\".\n\nUpdate: After reading the other reviews and the author feedback, my opinion of the paper is unchanged. My score remains 7.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues.", "review_text": "", "extra_scores": {"ethical_concerns": "No issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "G7rxjnadv4M", "reviewer": "Reviewer_bd7q", "summary": "The authors considered the problem of estimating the mean of d-dimensional Gaussian and sub-Gaussian distribution under DP constraint. The error bounds for the mean estimate is given in terms of the Mahalanobis distance, however, interestingly enough, the proposed method does not estimate the covariance matrix. The tool proposed by the authors is a sampling mechanism which is based on Tukey depth: the probability of choosing a point is exponentially proportional to the negative Tukey depth. Then one can run a mean estimator on the sampled data. This alone is not enough to accomplish DP, therefore the authors make use of a propose-test-release framework which is basically checks whether the sampled data contains too many points for which the Tukey depth is too small. The proposed methods of order D^{2/3} and in addition, it does not assume anything about the covariance matrix, and does not need a prior estimate for the covariance matrix as previous methods required. The sub-gaussian case basically find the closest gaussian model and applies the same mechanism.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am on the positive side with this paper pretty much. It is really dense. Based on the main paper, one can have only a high level impression on how complex the technical details are. Nevertheless, the appendix is well-structured, and self-contained ( however I have not read all 42 pages of Appendix yet). The basic idea of the paper is very nice and novel as far as I know. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is a dedicated paragraph to address the societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper provides a non-trivial advancement for the important problem of differentially private mean estimation. Reviewers 6nea, 8L9y, and ubCi found the proof techniques and algorithmic strategies insightful and novel. Reviewer ubCi found the assumptions underlying this paper to be significantly more realistic than prior work.  The only complaint about the paper is that the proposed algorithms have exponential running time, but reviewers 8L9y and ubCi feel that these algorithms could be the starting point for more practical algorithms. I therefore recommend that this paper be accepted.
Decision: Accept (Spotlight)