Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
Year: 2021

Abstract:
We present two sample-efficient differentially private mean estimators for ddimensional (sub)Gaussian distributions with unknown covariance. Informally, given n & d/α samples from such a distribution with mean μ and covariance Σ, our estimators output μ̃ such that ‖μ̃− μ‖Σ ≤ α, where ‖ · ‖Σ is the Mahalanobis distance. All previous estimators with the same guarantee either require strong a priori bounds on the covariance matrix or require Ω(d) 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, without releasing the covariance itself. 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.

heading: 1 Introduction
text: Although the goal of statistics and machine learning is to infer properties of a population, there is a growing awareness that many statistical estimators and trained models reveal a concerning amount of information about their data set, which leads to significant concerns about the privacy of the individuals who have contributed sensitive information to that data set. These privacy violations have been demonstrated repeatedly via reconstruction attacks [21, 30, 27, 46], membership-inference attacks [37, 52, 10, 32, 53, 59], and instances of unwanted memorization of training data [13, 14, 34, 7]. In order to realize the benefits of analyzing sensitive data sets, it is crucial to develop statistical
35th Conference on Neural Information Processing Systems (NeurIPS 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 [29], which has become the standard criterion for individual privacy in statistics and machine learning. Informally, a 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 [33, 6, 57], Apple [3], Facebook [55] and LinkedIn [51], as well as statistical agencies like the U.S. Census Bureau [1, 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 x1, . . . , xn ∈ Rd sampled i.i.d. from a distribution with mean µ ∈ Rd and covariance Σ ∈ Rd×d, 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 µx = 1n ∑ i xi. The natural way to state the sample-complexity guarantee of the empirical mean is
n & d
α2 =⇒ ‖µx − µ‖Σ ≤ α ,
where & hides a universal multiplicative constant, and the accuracy guarantee holds with large constant probability (say, 0.99). Importantly, ‖µx − µ‖Σ = ‖Σ−1/2(µx − µ)‖2 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 vTΣv in that direction. The Mahalanobis distance is the natural way to measure the error for mean estimation, since it tightly captures the uncertainty about the true mean and is preserved under affine transformations.
Unfortunately, in high dimensions, releasing the empirical mean leads to concrete privacy breaches [32, 41]. A natural question is thus: can we design a differentially private mean estimator that performs nearly as well as the empirical mean?
Without making additional assumptions, the answer turns out to be no—every differentially private 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 concentration properties, we can do much better [54, 44, 41, 42]. In this work, we focus on one class of well-concentrated distributions, those that are Gaussian (or, in some of our results, subgaussian). 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 & d [10, 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 a matrix A and bound κ ≥ 1 such that A Σ κA,1 then there is a folklore private estimator A(x), based on a 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
n & d α2 + d √ κ αε =⇒ ‖A(x)− µ‖Σ ≤ α, (1)
where ε is the privacy parameter controlling the level of privacy (see Definition 2.2), with stronger privacy as ε→ 0.2 Here & hides a universal multiplicative constant and polylogarithmic factors of d, 1δ , 1 ε 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
1Given two covariance matrices A,B ∈ Rd×d, the notation A B indicates that in every direction v ∈ Rd the variance vTBv is at least as large as vTAv. More generally, A B iff B −A is positive semidefinite.
2To simplify the discussion, we focus only on the ε parameter, although our results and many of those we discuss require relaxations of differential privacy such as approximate [28] or concentrated [26, 8] differential privacy, which have different parameterizations.
bound on the covariance so that κ is small (e.g. κ is a constant), and also that the privacy guarantee is not too strong (e.g. ε ≥ α). In particular, setting κ = 1 corresponds to the known-covariance setting, where the guarantee in (1) is known to be minimax optimal up to polylogarithmic factors [32, 41] among all differentially private estimators. However, the sample complexity in (1) grows asymptotically with √ κ, a large price to pay for the user’s uncertainty. Intuitively, this degradation arises because the algorithm perturbs the empirical mean µx 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 a weaker dependence on κ but a superlinear dependence on the dimension. In particular, there is an estimator [41, Theorem 4.3] with an error guarantee of the form
n & d
α2 +
d αε + d3/2 log1/2 κ ε =⇒ ‖A(x)− µ‖Σ ≤ α. (2)
Here & hides a universal multiplicative constant and logarithmic factors of d, 1ε , 1 α , log κ, and ρ, where ‖µ‖2 ≤ ρ; 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 covariance—which is the more difficult task considered in [2, Theorem 4.6]. Doing so incurs an even worse dependence on the dimension:
n & d2 α2 + d2 αε =⇒ ‖A(x)− µ‖Σ ≤ α. (3)
Here & hides a universal multiplicative constant and logarithmic factors of 1δ and 1 α ; the accuracy guarantee holds with large constant probability.
The Covariance-Estimation Bottleneck. The bottleneck in the algorithms above is privately obtaining 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-covariance approach in (1). Without privacy constraints, the empirical covariance will have this spectral-approximation property when the sample size is n & d. However, all known private covariance estimators require n = Ω(d3/2) samples, and there is evidence that this is an inherent limitation, as Ω(d3/2) samples are necessary for solving this task for a worst-case data distribution [31].
Our Work: Sample-Efficient Private Mean Estimation. We circumvent this apparent difficulty of covariance estimation by designing an algorithm that adapts the noise it adds to the distribution’s covariance without actually providing an explicit covariance estimate, nearly matching the optimal sample complexity (1) for the known-covariance setting. Theorem 1.1 (Informal). For α ≤ 1, there is an (ε, δ)-differentially private estimator A(·) such that if x = (x1, . . . , xn) are sampled from N (µ,Σ) for unknown µ and Σ of full rank,
n & d
α2 +
d
αε +
log(1/δ)
ε =⇒ ‖A(x)− µ‖Σ ≤ α.
The above guarantee holds with high probability over the sample x and the randomness of A. Here & 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; it is known to be a good robust estimator of the Gaussian mean. The natural way to sample such a point privately is to 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 is to sample from a data-dependent 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 1.1 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 an alternative
estimator, based on a completely different technique, that will give a similar guarantee for any distribution with subgaussian tails. For our purposes, we say that P with mean µ and covariance Σ is subgaussian if, for every direction u ∈ Rd, the tails of the distribution decay as fast as a univariate normal distribution with mean uTµ and variance CuTΣu for some constant C. That is, for every λ, E[eλuT (P−µ)] ≤ eCλ2(uTΣu)/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 α ≤ 1, there is an (ε, δ)-differentially private estimator A(·) such that if x = (x1, . . . , xn) are sampled from any subgaussian distribution with unknown mean µ and unknown covariance Σ of full rank,
n & d α2 + d log(1/δ) αε2 =⇒ ‖A(x)− µ‖Σ ≤ α.
The above guarantee holds with high probability over the sample x and the randomness of A. Here & hides a universal multiplicative constant and polylogarithmic factors of d, 1δ , 1 ε , and 1 α .
For the formal statement, see Theorem 4.4. This estimator is based on another simple approach—we perturb the empirical mean µx with noise scaled to Σx, where Σx 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.
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, it 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 a 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-sensitive 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.

heading: 1.1 Techniques
text: Tukey-depth Mechanism. Our first algorithm adapts a well-known approach to estimating the location of a 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 14 . To ensure differential privacy, we add a private check that the data set is “safe,” which we perform before running the main mechanism.
In more detail, our starting point is the exponential mechanism [50]. In this context, the exponential mechanism samples a point y ∈ Rd from the distribution with probability density roughly proportional to exp(−εq(x; y)), where q(x; y) is a 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 µ in the unknown Mahalanobis metric, and (ii) a set of candidate values y from which to sample. For (i), we choose q(x; y) = nTx(y) where Tx is the Tukey depth of a point, defined as
Tx(y) = 1
n · min v∈Rd
∣∣∣{xi ∈ x : 〈xi, v〉 ≥ 〈y, v〉}∣∣∣ . (4)
For normally distributed data, the Tukey depth ranges from 0 (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 in 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 a 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.3 However, on its own, it is not sufficient for our needs. The challenge is in specifying the set of potential outputs y from which we sample (step (ii) above). In order to reliably output a value y such that ‖y − µ‖Σ is small, we must sample from a set of outputs with Σ-norm that is not too large. For that, however, it would seem that one needs a 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 {y : ‖y − µ‖Σ ≤ c} for a modest constant c. Running the exponential mechanism on this set returns a good approximation to the mean (with Σ-norm o(1)) when n = ω(d/ε).
This gives us an accurate algorithm, dubbedM. The remaining challenge is thatM is not, on its own, differentially private. Specifically, there are data sets x for which the volume of the set of Tukey-depth-1/4 points changes drastically when a small number of records in x are changed. To address this, we identify a set of safe data sets x—these are data sets such thatM behaves similarly on all data sets x′ that are neighbors of x. We show that normally distributed data sets are typically safe and, furthermore, require many insertions or deletions of records to be made unsafe. This allows us to apply the propose-test-release (PTR) framework of [25] to obtain an algorithm that is accurate for nicely distributed data and differentially private in the worst case.
Our modification of the exponential mechanism is quite general. It is similar in flavor to the GAPMAX variant [11, 58, 15–17] as well as the top-k-of-k′ 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 in our setting.
Empirically Rescaled Gaussian Mechanism. The well-known Gaussian mechanism perturbs the empirical mean µx with noise drawn fromN (0, σ2I), for a scale parameter σ that is chosen based on a priori information about the data. In particular, σ2 must scale linearly with ‖Σ‖22, 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 is drawn i.i.d. from N (µ,Σ), and the number of samples is a bit larger than the dimension d, then the empirical covariance Σx is a good approximation to the true covariance in spectral norm. When this holds, perturbing µx with noise drawn from N (0, C2Σx) for C 1√d will be a good estimate of the mean in Mahalanobis distance. Thus, we want to understand when perturbing µx in this way can be made differentially private.
Adding noise from N (0, C2Σx) will not be private for worst-case data sets. To see this, consider a pair of adjacent data sets, one of which lies in a 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.
3We 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, a version of the Tukey depth algorithm where one samples from a 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-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).
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 µx and µx′ will be similar, as will Σx and Σx′ . 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, a data set x is good if Σx is invertible and, for every xi, ‖xi − µx‖Σx . √ d log n. Our main technical contribution is to show that if x and x′ differ on a small number of samples, and both data sets are good, then their empirical means and empirical covariances are close. Thus, µx +N (0, C2Σx) and µx′ +N (0, C2Σx′) will be indistinguishable in the sense required for (ε, δ)-differential privacy. However, we need to 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 input 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 x̃ and x̃′ that differ on a small number of examples.
This projection step is stated abstractly in Algorithm 2 as finding the minimizer over an infinite family of data sets. In the supplementary material, we present a concrete, exponential-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.

heading: 1.2 Additional Related Work
text: 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/α2 + 1/αε), without requiring a priori bounds on the parameters. Previously, Smith [54] gave estimators for asymptotically normal statistics (which include the mean of a Gaussian) with optimal convergence rates for a certain range of privacy parameters. In the multivariate setting, a series of works [41, 11, 2] gives algorithms for Gaussian mean estimation with known covariance that have a near-optimal sample complexity of Õ(d/α2 + d/αε). 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 as ours, has an error guarantee of ‖µ̂− µ‖2 ≤ α‖Σ1/2‖2. This result is strictly weaker than ours. However, their estimator, in contrast to ours, has the pleasant property of being computationally efficient.
Beyond (sub)Gaussian distributions, [4, 9, 42] study differentially private mean estimation under weaker moment assumptions.
In addition to the work we discuss in the introduction [41, 2], 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 Ω(d3/2) samples are necessary for private covariance estimation for Gaussian data as well.
Robust Statistical Estimation. Robust statistical estimation [40, 49], which dates to at least 1960 [56] and remains an active area of research [18–20, 22, 38], studies the problem of estimating distribution parameters when an α-fraction of the data may be adversarially corrupted. As noted by Dwork and Lei [25], robust statistics and differential privacy have similar goals, and private estimators are often inspired by robust estimators, but the models are formally incomparable.
More recent work aims to give algorithms which satisfy both constraints simultaneously [47, 35]. Specifically, independently from our work, Liu et al. [47] propose a simple mechanism for Gaussian mean estimation with known covariance, given α-corrupted data sets and an a priori bound on the range of the mean ‖µ‖∞ ≤ ρ. This estimator has sample complexity Õ(d/α2 + d log ρ/αε). The algorithm runs the exponential mechanism [50] in the given range, using the Tukey depth of a point as its score. We observe that the same mechanism gives a solution for the problem we study—mean
estimation in Mahalanobis distance with unknown covariance and no corruptions—but this solution requires a priori bounds on the mean and covariance, which are not required by our algorithms.

heading: 2 Preliminaries
text: We write x ∼ P to denote that x is drawn from distribution P and x ∼ P⊗n if x consists of n i.i.d. draws from P . We write [n] = {1, . . . , n}. We define the Hamming distance between two data sets x, y of size n by DH(x, y) = |{i ∈ [n] : xi 6= yi}|. For data set x and set S ⊆ Rn×d, we write DH(x, S) = minz∈S DH(x, z).
Let x, x′ ∈ Xn be two data sets of size n. We say that x, x′ are neighboring data sets if DH(x, x′) ≤ 1, and denote this by x ∼ x′. Differentially private algorithms have indistinguishable output distributions on neighboring data sets. Definition 2.1 ((ε, δ)-indistinguishability). Two distributions P,Q over domain W are (ε, δ)indistinguishable, denoted by P ≈ε,δ Q, if for any measurable subset W ⊆ W ,
Pr w∼P [w ∈W ] ≤ eε Pr w∼Q [w ∈W ] + δ and Pr w∼Q [w ∈W ] ≤ eε Pr w∼P [w ∈W ] + δ.
Definition 2.2 (Differential Privacy [29]). A randomized algorithm A : Xn → W is (ε, δ)differentially private if for all neighboring datasets x, x′ we have A(x) ≈ε,δ A(x′).
We next describe well-known mechanisms which serve as building blocks for our algorithms. Lemma 2.3 (Laplace Mechanism [29]). Let f : Xn → R, data set x ∈ Xn, and privacy parameter ε. The Laplace Mechanism returns f̃(x) = f(x) + Lap(∆f/ε), where ∆f = maxx∼x′ |f(x)− f(x′)| is the global sensitivity of f . The Laplace Mechanism is (ε, 0)-differentially private. Lemma 2.4 (Gaussian Mechanism [29]). Let f : Xn → Rd, data set x ∈ Xn, and privacy parameters ε, δ. The Gaussian Mechanism returns f̃(x) = f(x) + N (0, σ2I), where σ = ∆f √
2 log(5/4δ)/ε and ∆f = maxx∼x′ ‖f(x) − f(x′)‖2 is the global `2-sensitivity of f . The Gaussian Mechanism is (ε, δ)-differentially private.

heading: 3 Tukey Depth Mechanism
text: We start with a score function q(x; y) and wish to sample from the exponential mechanism, proportional to exp (ε · q(x; y)/2), but restricting the sampling to the set of points with score at least t. Denote this set Yt,x = {y ∈ Y : q(x; y) ≥ t} and call the resulting distributionMε,t(x). Unfortunately, sampling directly fromMε,t(x) may not be private. To address this, we try to sample only from data sets that are “safe” with respect to privacy, i.e., have distributions that are indistinguishable from those of their neighbors. Definition 3.1 (Safety). Data set x is (ε, δ, t)-safe if, for all x′ ∼ x, we haveMε,t(x) ≈ε,δMε,t(x′). Let SAFE(ε,δ,t) ⊆ Xn be the set of safe data sets, and let UNSAFE(ε,δ,t) = Xn \ SAFE(ε,δ,t) be its complement.
Following the propose-test-release framework of [25], we check if the input is far from UNSAFE(ε,δ,t). Since the distance check itself is private and indistinguishability is the definition of safety, the proof of privacy becomes straightforward. Such an abstract definition, however, does not 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 Yt±η,x (for certain values of η), which allows us to show that Gaussian data are far from UNSAFE(ε,δ,t) with high probability.
Algorithm 1 Restricted Exponential Mechanism AEε,δ,t(x) Require: Data space X . Output space Y ∪{FAIL}. Data set x ∈ Xn. Score function q : Xn×Y →
R, with global sensitivity 1 in the first argument. Privacy parameters ε, δ > 0. Minimum score t. 1: h← DH(x, UNSAFE(ε,δ,t)) 2: if h+ z < log(1/2δ)ε for z ∼ Lap(1/ε) then return FAIL.
3: return ŷ ∼Mε,t(x), whereMε,t(x) ∝
{ exp { εq(x;y)
2
} if y ∈ Yt,x
0 otherwise

heading: 3.1 Main Algorithm
text: We estimate the mean by instantiating Algorithm 1 with t = n/4 and score function q(x; y) = nTx(y), where Tx(y) is the (empirical) Tukey depth, defined in Equation (4). Observe that nTx(y) has sensitivity 1, since for any halfspace the fraction of points it contains can change by at most 1n when we change one data point. Theorem 3.2 (Privacy and Accuracy of the Tukey-Depth Mechanism). For any ε, δ > 0, Algorithm 1 is (2ε, eεδ)-differentially private. There exists an absolute constantC such that, for any 0 < α, β, ε < 1, 0 < δ ≤ 12 , mean µ, and positive definite Σ, if x ∼ N (µ,Σ) ⊗n and
n ≥ C ( d+ log(1/β)
α2 + d log(1/α) + log(1/β) αε + log(1/δ) ε
) , (5)
then with probability at least 1− 3β, Algorithm 1 with q(x; y) = nTx(y) returns AEε,δ,n/4(x) = µ̂ such that ‖µ̂− µ‖Σ ≤ α.
We focus here on the accuracy analysis. Privacy follows from standard propose-test-release calculations [25], which we include in the supplementary material.

heading: 3.2 Accuracy Analysis
text: The proof of accuracy proceeds in four stages. Using standard analysis, we first relate the empirical Tukey depth of a point y to its Mahalanobis distance ‖y − µ‖Σ via the expectation of Tukey depth under N (µ,Σ). Since Tukey depth is defined as a minimum over halfspaces, which have VapnikChervonekis 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 Ynp,x, where p ∈ (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 1 has a small probability of returning FAIL. Finally, conditioned on Algorithm 1 not returning FAIL, a similar analysis shows that with high probability the restricted samplerMε,t(x) returns a 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 Yt+η,x for moderate positive and negative values of η. Recall that Yt+η,x is the set of all points y with score q(x; y) = nTx(y) ≥ t+η, i.e., having empirical Tukey depth with respect to x at least (t + η)/n. Therefore, as η becomes smaller, the set Yt+η,x grows. We show that, if the volume of Yt+η,x does not increase too quickly as η decreases, then x is far from every data set in UNSAFE(ε,δ,t). In particular, this implies that x itself is in SAFE(ε,δ,t). 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 a lemma about the weight assigned to sets by the exponential mechanism. For any set S ⊆ Y , denote its weight by wx(S) = ∫ S exp { εq(x;y) 2 } dy.
Lemma 3.3. Assume δ < 12 . If wx(Yt+1,x) ≥ (1 − δ)wx(Yt−1,x), then x ∈ SAFE(ε,δ′,t) for δ′ = 4eεδ.
Proof Sketch. For an arbitrary adjacent x′, we must establish that the distributions Mε,t(x) and Mε,t(x′) are (ε, δ′)-indistinguishable. The proof is elementary but non-trivial: our hypothesis only concerns x, not its neighbors. To illustrate, we show that Pr[Mε,t(x) /∈ supp(Mε,t(x′))] ≤ δ′. By definition, supp(Mε,t(x′)) = Yt,x′ . Now we move from x′ to x: the score function has sensitivity 1, so every point with q(x; y) ≥ t+ 1 satisfies q(x′; y) ≥ t. Thus Yt+1,x ⊆ Yt,x′ , and we have
Pr[Mε,t(x) /∈ supp(Mε,t(x′))] ≤ Pr[Mε,t(x) /∈ Yt+1,x] = 1− wx (Yt+1,x) wx (Yt,x) .
Since Yt,x ⊆ Yt−1,x, wx(Yt,x) ≤ wx(Yt−1,x), and our hypothesis implies Pr[Mε,t(x) /∈ supp(Mε,t(x′))] ≤ δ, which is less than δ′ = 4eεδ.
The rest of the proof requires similar (but slightly longer) calculations.
We now use this lemma to establish when a data set is far from the set of unsafe data sets. Note that setting k = 0 below implies for all z ∈ UNSAFE that we have DH(x, z) > 0, i.e., x ∈ SAFE.
Lemma 3.4. For any k ≥ 0, if there exists a g > 0 such that Vol(Yt−k−1,x)Vol(Yt+k+g+1,x) · e −εg/2 ≤ δ, then for all z ∈ UNSAFE(ε,δ′,t), with δ′ = 4eεδ, we have DH(x, z) > k
Proof. Take some z at distance at most k from x (if k = 0, set z ← x). We show z ∈ SAFE(ε,δ′,t). We have, from Lemma 3.3, that if wz(Yt+1,z)wz(Yt−1,z) ≥ 1− δ, then z is safe. This assumption is equivalent to wz(Yt−1,z\Yt+1,z)wz(Yt−1,z) ≤ δ, which is the form we use.
First we lower bound the denominator:
wz(Yt−1,z) ≥ wz(Yt+g+1,z) ≥ Vol(Yt+g+1,z)eε(t+g+1)/2 ≥ Vol(Yt+g+k+1,x)eε(t+g+1)/2,
where (crucially) the last inequality switches to the volume under x, and we have used the sensitivity of q. We use the same idea on the numerator, switching to a volume under x in the first inequality:
wz(Yt−1,z\Yt+1,z) ≤ wz(Yt−k−1,x\Yt+1,z) ≤ Vol(Yt−k−1,x)eε(t+1)/2.
With an upper bound on the numerator, a lower bound on the denominator, and the fact that eε(t+1)/2
eε(t+g+1)/2 = e−εg/2, we have
wz(Yt−1,z\Yt+1,z) wz(Yt−1,z) ≤ Vol(Yt−k−1,x) Vol(Yt+k+g+1,x) · e−εg/2 ≤ δ,
so z ∈ SAFE(ε,δ′,t).
With these tools in hand, in the supplementary material we show that, if n = ω(d/ε), typical Gaussian data satisfy the hypothesis of Lemma 3.4 for g = n/8 and thus are far from unsafe (implying that we are unlikely to return FAIL) and that with high probability the restricted samplerMε,t(x) returns a point with high Tukey depth.

heading: 4 Empirically Rescaled Gaussian Mechanism
text: In this section, we describe our second estimator. At a high level, the estimator first privately checks whether the data set x is 1ε -close in Hamming distance to a good set of “roughly Gaussian” data sets G(λ). If so, it finds the closest data set to x that belongs in G(λ), which we call x̃. Then it returns a sample µ̂ drawn from N (µx̃, C2Σx̃), where µx̃ and Σx̃ are the empirical mean and covariance of x̃ and C is a scale parameter appropriately set to ensure privacy. Specifically, we use the definitions:
Definition 4.1 (Empirical Mean and Covariance). For data set x ∈ R3n×d, the empirical mean and covariance of x are respectively defined by µx = 1n ∑n i=1 xi+2n and Σx = 1 2n ∑n i=1(xi − xi+n)(xi − xi+n)T .
In comparison with the standard empirical estimators, ours enable a simpler privacy analysis, since replacing one datapoint in x only affects one term in one of the sums. For convenience, we choose the number of samples to be 3n so that we can pair the first two thirds to construct Σx and use the last third for µx. With these definitions at hand, the good set G(λ) is defined as follows: Definition 4.2 (λ-goodness). For any λ > 0, define G(λ) ⊆ R3n×d as
G(λ) def= { x ∈ R3n×d : Σx is invertible and ∀i ∈ [3n] ‖xi − µx‖2Σx ≤ λ } .
We set λ ≈ d log n, since for this value (sub)Gaussian data will belong in G(λ) with high probability. Finally, we note that the algorithm immediately aborts if the number of samples is less than kλ log(1/δ)
ε ≈ d log(1/δ) ε2 , a condition necessary to ensure privacy.
Algorithm 2 Empirically Rescaled Gaussian Mechanism AGε,δ,β(x)
Require: Data set x = (x1, . . . , x3n)T ∈ R3n×d. Privacy parameters ε, δ > 0. Failure probability β > 0.
1: Initialize: λ← O ( d log nβ ) , t← 1ε log 1 β , k ← 2 ε log 1 δβ + 1, C 2 ← 32k 2 ε2n2 · λ 1−2kλ/n · log 1.25 δ .
2: if n = o ( kλ ε log 1 δ ) then return FAIL. 3: x̄← σ(x) . random permutation σ : (Rd)3n → (Rd)3n 4: h← DH(x̄,G(λ)) . distance between x̄ and λ-goodness 5: if h+ r > t for r ∼ Lap (1/ε) then return FAIL. 6: x̃← arg minz∈G(λ)DH(x̄, z) . projection to λ-goodness 7: return µ̂ ∼ N (µx̃, C2Σx̃)
We remark that the sample size check in line 2 and the setting of λ are not well-defined, as they are stated with asymptotic notation. Although it is possible to compute the constants for these steps, we exclude them in favor of a cleaner analysis.
We prove accuracy for the following family of distributions: Definition 4.3 (Subgaussian distribution). Let Pµ,Σ be a distribution over Rd with mean µ and covariance Σ 0. For a constant c > 0, we say that Pµ,Σ is subgaussian with parameter cΣ, if for all u ∈ Rd such that ‖u‖2 = 1, Ev∼Pµ,Σ [eλu T (v−µ)] ≤ ecλ2(uTΣu)/2 for all λ ∈ R.
We write Pµ,Σ ∈ subG(cΣ). 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 ε > 0, 0 < δ < 1, Algorithm 2 is (3ε, eε(1 + eε)δ)-differentially private. There exists an absolute constant C such that, for any 0 < α, β, ε, δ < 1, mean µ, and positive definite Σ, if x ∼ P⊗nµ,Σ, where Pµ,Σ ∈ subG(cΣ) for some constant c > 0, and
n ≥ C ( d
α2 log
1 β + d αε2 log3 1 δβ · log d log(1/δβ) αε
) , (6)
then with probability at least 1− 3β, Algorithm 2 returns AGε,δ,β(x) = µ̂ such that ‖µ̂− µ‖Σ ≤ α.
Acknowledgments and Disclosure of Funding
We thank the anonymous NeurIPS reviewers for useful suggestions on the presentation of this manuscript. Gavin Brown and Adam Smith were supported in part by NSF award CCF-1763786 as well as a Sloan Foundation research award. Marco Gaboardi was supported in part by NSF award CCF-2040222, CCF-1718220, CNS-1565365, and CNS-2040215. Jonathan Ullman and Lydia Zakynthinou were supported by NSF grants CCF-1750640, CNS-1816028, and CNS-1916020. Lydia Zakynthinou was also supported by a Facebook Fellowship.

Review summaries:
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).   One 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.  The 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.   The 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.  

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.  

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.   The 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.  

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.