Dimension-free Private Mean Estimation for Anisotropic Distributions

Authors: yuval  dagan
michael i jordan
xuelin  yang
lydia  zakynthinou
nikita  zhivotovskiy
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:20:43

Abstract: We present differentially private algorithms for high-dimensional mean estimation. Previous private estimators on distributions over $\mathbb{R}^d$ suffer from a curse of dimensionality, as they require $\Omega(d^{1/2})$ samples to achieve non-trivial error, even in cases where $O(1)$ samples suffice without privacy. This rate is  unavoidable when the distribution is isotropic, namely, when the covariance is a multiple of the identity matrix. Yet, real-world data is often highly anisotropic, with signals concentrated on a small number of principal components. We develop estimators that are appropriate for such signals---our estimators are $(\varepsilon,\delta)$-differentially private and have sample complexity that is dimension-independent for anisotropic subgaussian distributions.  Given $n$ samples from a distribution with known covariance-proxy $\Sigma$ and unknown mean $\mu$, we present an estimator $\hat{\mu}$ that achieves error, $\|\hat{\mu}-\mu\|_2\leq \alpha$, as long as $n\gtrsim \text{tr}(\Sigma)/\alpha^2+ \text{tr}(\Sigma^{1/2})/(\alpha\varepsilon)$. We show that this is the optimal sample complexity for this task up to logarithmic factors. Moreover, for the case of unknown covariance, we present an algorithm whose sample complexity has improved dependence on the dimension, from $d^{1/2}$ to $d^{1/4}$.

Main paper: 
 introduction: 
 Machine learning is increasingly deployed in real-world settings to learn about properties of populations, both large and small. When the data comes from human populations, it is essential that algorithm design allows inferring properties of populations without revealing potentially sensitive information about specific individuals in the population. That sensitive information can be revealed, inadvertently or adversarially, has been demonstrated in numerous ways, including via reconstruction attacks [21, 24] , as well as membership-inference attacks [56] , often targeting sensitive genomic data [34, 55, 64] . To mitigate the risk of privacy violations in general database theory, Dwork, McSherry, Nissim, and Smith [25] proposed the rigorous guarantee of differential privacy (DP), which has been widely adopted in industry [29, 11, 33, 62, 53, 4] and government [30, 1, 2] . Algorithms that are differentially private are guaranteed to not leak too much information about the individuals in a database.In the machine learning setting, there is a tension between differential privacy and inferential and predictive accuracy. It is an ongoing challenge to capture that tension mathematically, in a way that is applicable to a wide variety of problems and is sufficiently quantitative so as to provide a guide for real users and real systems designers. A particularly salient theoretical challenge is to obtain results that capture dimension-dependence-given that machine learning data are often of high dimensionality and involve significant correlation among dimensions, and given that privacy is difficult to guarantee in high dimensions, particularly so when there are correlations. Indeed, differentially private inference suffers from a curse of dimensionality-the sample size n that is required to obtain a non-trivial DP learner is often polynomial in the dimension d of the data.Significant progress has been made in addressing this challenge in recent years by focusing on a relatively simple inferential task, that of high-dimensional mean estimation. Formally, given a data set of n points, X = (X (1) , . . . , X (n) ) ∈ R d×n drawn i.i.d. from a multivariate distribution P with unknown mean µ ∈ R d , the goal is to learn µ.Obtaining low-error private mean estimators in the high-dimensional regime is not always possible. For example, consider a Gaussian distribution P = N (µ, σ 2 I d ), where I d is the d × d identity matrix. Here, the sample complexity of any private estimator μ achieving error ∥μ -µ∥ 2 ≤ α is n = Ω(dσ 2 /α 2 + dσ/(αε)) [39] , where ε is the privacy parameter. 1 The first term corresponds to the non-private sample complexity and the second term to the additional samples required due to privacy. Although both depend on d, note that for non-trivial error α = 0.01σ √ d and ε = 0.1, the non-private term is O(1), whereas the dimension-dependence persists in the cost of privacy which is O( √ d).In spite of this lower bound, there is still hope for obtaining better dependence on the dimension in certain cases. This is due to the fact that the lower bound instance assumes that the covariance is isotropic: a multiple of the identity matrix. However, real-world data are far from being isotropic. Often, the signal is concentrated in a few directions, while it is significantly weaker in others, as can be revealed via Singular Value Decomposition (SVD). In these cases, there are several examples of non-private estimators for a variety of tasks which exploit the structure of the data to achieve lower sample complexity. Specifically for mean estimation of Gaussian distributions, as in our example above, only n = O(tr(Σ)/α 2 ) samples are required [48] (this number of samples is sufficient even for robust estimators under the strong contamination model [50] ). This bound is instance-adaptive, as the trace of the covariance matrix tr(Σ) equals its upper bound, d∥Σ∥ 2 , in the isotropic case, but can be much smaller for anisotropic data. Exploiting the non-isotropic structure of the covariance matrix is also central to the covariance estimation problem with respect to the operator norm (namely, when the error between the true covariance matrix Σ and its estimate Σ is measured in terms of ∥ Σ -Σ∥ 2 ) [43, 65] . A more recent focus is on overparametrized linear regression [9] , where again the highly non-isotropic structure of the covariance matrix allows for inference under certain assumptions on the decay of eigenvalues of the covariance matrix. In all the mentioned results, non-private estimation is possible when n ≪ d, including even infinite-dimensional Hilbert spaces.Returning to private estimation, prior work has obtained optimal bounds for learning the mean of high-dimensional (sub)Gaussian distributions in the affine-invariant Mahalanobis distance [18, 39, 3, 46, 13, 47] . These imply an upper bound for learning the mean in Euclidean distance in the order of n = O(d∥Σ∥ 2 /α 2 + d ∥Σ∥ 2 /(αε)), which is optimal for isotropic, but loose for anisotropic cases. A folklore estimator, based on [41] achieves n = Ω( d tr(Σ)/(αε)), while [8] are the first to focus on the anisotropic case and obtain improved bounds for diagonal covariance, achieving error n = Ω(tr(Σ 1/2 )/(αε) + √ d/ε). Thus, all previous work requires that the sample complexity is at least Ω( √ d), which excludes the high-dimensional scenario we are interested in. We are led to pose the following question.: Question 1. Is it possible to obtain good private mean estimators with a sample size that grows slower with the dimension, or is even dimension-independent, when the covariance of the data is far from isotropic? What is the optimal sample complexity in the case of known and unknown covariance?First, note that no improved bounds are possible for pure DP, as follows directly from the so-called packing technique [32, 18] and specifically applying [18, Lemma 5 .1]: any ε-DP algorithm which estimates the mean of a Gaussian distribution up to constant accuracy requires n = Ω (d/ε) samples. This negative result motivates us to focus on (ε, δ)-differential privacy.In order to make progress, one would like to utilize the fact that when the covariance is far from being isotropic, the data is closer to being low-dimensional. Concretely, let Σ be the covariance matrix of P and σ 2 1 ≥ . . . ≥ σ 2 d its singular values. If the covariance is far from isotropic, there are only few directions with non-trivial variance. For illustration, ifσ 1 = • • • = σ k = 1, whereas σ k+1 = • • • = σ d = 1/d,then the distribution is, in some sense, close to being k-dimensional. Here, we would like our sample complexity to be of order k rather than√ d.We start by presenting a result in the case where the covariance matrix is known. Here, the bound depends only ond i=1 σ i = tr(Σ 1/2), a quantity allowing less contribution from small singular values: Theorem 1.1 (Upper bound, known covariance, informal). Set ε, δ ∈ (0, 1), α > 0. Let X ∼ N (µ, Σ) n with known covariance. There exists an (ε, δ)-differentially private algorithm which, with probability 0.99, returns an estimate μ such that ∥μ -µ∥ 2 ≤ α, and has sample complexityEQUATIONThe first term corresponds to the non-private sample complexity, whereas the remaining two terms are due to privacy. The result extends to subgaussian distributions. In the example illustrated above, this bound indeed yields a dimension-independent complexity of n = Õδ (k/α 2 + k/(αε)).We show that the sample complexity of Theorem 1.1 is nearly optimal. Indeed, the first summand is optimal due to [19, Theorem 4], while the last summand is optimal by a lower bound in the univariate case [41] . We show the optimality of the intermediate summand in (1) up to polylogarithmic terms. Theorem 1.2 (Lower bound, informal). Any (ε, δ)-DP algorithm which estimates the mean µ ∈[-1, 1] d of a Gaussian up to α with probability 0.99 has sample complexity n = Ω tr(Σ 1/2 ) αε log 2 (d) .We now move to the case of unknown covariance. A first approach would be to learn the covariance approximately, namely, find a matrix A such that A ⪯ Σ ⪯ CA, for some C > 1, and then use A instead of Σ in our known-covariance estimator. However, learning such a matrix A privately requires sample size n = Θ(d 3/2 ) [39, 40] . Another approach would be to learn only the diagonal elements of the covariance [41] this would require n = O( √ d/ε) samples. Below, we obtain a sample complexity whose dependence in the dimension is d 1/4 , together with a dependendence on the diagonal elements of the covariance matrix: Theorem 1.3 (Upper bound, unknown covariance, informal). Let parameters ε, δ ∈ (0, 1). Let X ∼ N (µ, Σ) n with unknown covariance Σ. There exists an (ε, δ)-DP algorithm which, with probability 0.99, returns an estimate μ such that ∥μ -µ∥ 2 ≤ α, and has sample complexityEQUATIONIn general, tr(Σ1/2 ) ≤ d i=1 Σ 1/2ii , and if Σ is diagonal, the two quantities coincide. Our theorem is in fact more adaptable to easier cases of covariance structure. As a special case, when the covariance is diagonal and the singular values exhibit an exponential decay, that is,σ i = σ 1 e -(i-1) , then n = Õ tr(Σ) α 2 + tr(Σ 1/2 ) √ log(1/δ) αε + log 5/3 (d) log 3/2 (1/δ) εsamples suffice even under unknown covariance.Known covariance. A folklore (ε, δ)-DP algorithm, based on techniques for the univariate case developed by [41] , is to filter outliers by privately estimating each individual coordinate of the mean, µ i , up to an additive error of Õ(Σ1/2ii ) for all i, clipping any sample point to within that range, and outputting the mean of the modified data set with added spherical Gaussian noise N (0, tr(Σ)I d /(ε 2 n 2 )).A standard analysis of this procedure yields a sample complexity of n ≳ tr(Σ)α 2 + √ d ε + √ d tr(Σ) αε, where the dependence on δ is omitted for clarity. For constant ε, the folklore estimator achieves privacy for free, that is, the error due to privacy is lower than the error of statistical estimation, when n ≳ d.An improvement to this simple analysis, proposed recently by Aumüller et al. [8] for matrices of diagonal covariance, suggests adding noise N 0, tr(Σ 1/2 )Σ 1/2 /(ε 2 n 2 ) instead, which introduces more noise in the directions of larger variance. Slightly simplifying their result and additionally ignoring logarithmic factors in d, and the range of µ, their sample complexity is n ≳ tr(Σ)α 2 + √ d ε + tr(Σ 1/2 ) αε. This estimator achieves privacy for free as long as n ≳ max{∥σ∥ 2 1 /∥σ∥ 2 2 , √ d}, where σ 2 denotes the vector of singular values of Σ. While this removes the dimension dependence in the third term compared to the naïve sample complexity, the second term still requires Ω( √ d) samples. This is due to the first step of the algorithm (inherited from [37] ), which performs d independent estimation tasks. In both approaches, the pre-processing step is a form of coarse mean estimation which ensures that the data will not include outliers, and it is the source of sample-inefficiency. Thus, in our work, we remove outliers, namely vectors too far away from the true mean in one of the coordinates, using only n = Õ(1/ε) samples, thus completely removing the dependence on d in the final sample complexity bounds. (Indeed, our estimator achieves privacy for free for n ≳ max{∥σ∥ 2 1 /∥σ∥ 2 2 }.) Next, we generalize the approach of [8] to general covariance, rather than diagonal. Finally, we show that the sample complexity is nearly optimal. Specifically:Our pre-processing is realized by using a polynomial-time filtering algorithm of Tsfadia et al. [63] . Given a predicate computed for two data points, so-called FriendlyCore returns a subset X ′ of the input, such that all pairs of the remaining, unfiltered data points satisfy the predicate. Its sample complexity is Õ(1/ε) for any predicate, hence it has the potential to yield a dimension-independent bound. For our purposes, X ′ needs to satisfy some sensitivity properties. It follows from our analysis that the filtering should be such that for any two points X (j) , X (ℓ) ∈ X ′ , ∥Σ -1/4 (X (j) -X (ℓ) )∥ 2 2 ≤ Õ tr(Σ 1/2 ) .The lower bound for (ε, δ)-DP is an application of the standard fingerprinting [15, 28, 39, 40] technique for isotropic Gaussians. A straightforward modification of the technique to anisotropic covariance Σ gives a weaker bound than Theorem 1.2. Instead one needs to choose an appropriate set of almost-isotropic coordinates whose size scales with tr(Σ 1/2 ), and apply the technique to that set.Unknown covariance. Moving to the case of unknown covariance, for illustration, we focus on the simpler, yet fundamental, case where the covariance matrix is diagonal, so that Σ = diag(σ 2 1 , . . . , σ 2 d ). First, the folklore algorithm described in the known-covariance setting, which adds spherical Gaussian noise, does not require knowledge of the covariance but only of its trace. The trace can be privately learned with n = Õ(1/ε) samples. Second, we note that with n = Õ( √ d/ε) samples, it is possible to learn each σ i up to a multiplicative constant [41] . This allows us to apply the algorithm with known covariance from Theorem 1.1. However, the first step in this approach still requires Ω( √ d) samples.Our approach is to combine these two methods. We privately learn the largest k ≈ ε 2 n 2 variances, and their indices. This is done using the sparse vector technique [23] and can be achieved with n samples. We use the known-covariance algorithm to estimate the mean in these top k coordinates, with the same error bound as in the known-covariance setting. For the mean at the remaining coordinates, we use the algorithm that only requires knowledge of the trace of the covariance. The error of the latter estimate is α bot ≈ √ d∥σ bot ∥ 2 /(nε), where σ bot is the vector containing the lowest d -k variances. The first observation is that σ contains at least k entries as large as ∥σ bot ∥ ∞ , hence, ∥σ∥ 1 ≥ k∥σ bot ∥ ∞ . Then, by Hölder's inequality,∥σ bot ∥ 2 ≤ ∥σ bot ∥ 1 ∥σ bot ∥ ∞ . Substituting k yields α bot ≈ √ d∥σ∥ 1 /(ε 2 n 2 ), which implies the desired sample complexity bound in Theorem 1.3.Differentially private Gaussian mean estimation. Smith [58] proposed estimators for asymptotically normal statistics with optimal convergence rates under a certain range of parameters. The optimal sample complexity for learning the mean of a Gaussian with known covariance in Mahalanobis norm under (ε, δ)-DP is n ≳ d/α2 + d/(αε) + log(1/δ)/ε and has been established in a series of works [18, 39, 3, 46] , starting from [41] in the univariate setting. Given the covariance matrix Σ, the Mahalanobis distance between the estimate μ and the true mean µ is defined as: ∥μ -µ∥ Σ = ∥Σ -1/2 (μ -µ)∥ 2 . When Σ = I d , the Mahalanobis and Euclidean norms coincide. The Mahalanobis distance yields an affine-invariant accuracy guarantee, and ∥μ -µ∥ Σ ≤ α immediately implies ∥μ -µ∥ 2 ≤ α ∥Σ∥ 2 . However, the power of the Mahalanobis guarantee is overshadowed by the fact that even for α = √ d, a large sample size, namely n = Ω( √ d), is required, which excludes the high-dimensional scenario we are interested in. 2 Furthermore, confidence sets induced by guarantees in the Euclidean distance have the pleasant property of being more easily constructible.Beyond global sensitivity. There are several lines of work within differential privacy which aim to satisfy some form of instance-adaptive accuracy guarantee, as we do. General purpose frameworks which aim to privately estimate a statistic of the data, with error which adapts to "good" data sets, include propose-test-release [22] , smooth-sensitivity [52] , and Lipschitz extensions [12, 42] . Our method follows the same high-level structure as propose-test-release. The latter has been combined with robust estimators to yield optimal private learners for several tasks [13, 47] . Even more generally, [6, 35] give a black-box method which transforms robust estimators to private ones via the inverse-sensitivity mechanism [5] (see [59] for a discussion on inverse-sensitivity). As there exist optimal robust estimators for the mean of anisotropic Gaussians [50] , this would be a viable approach, but the volumetric analysis of the transformation involves terms which depend on the dimension. Tsfadia et al. [63] propose a filtering method which yields private aggregators whose error adapts to the diameter of the input data set. It is their method that we utilize for our upper bounds. A series of works formalize instance-optimality for private estimation of empirical [5, 37, 20] or population [49, 7] quantities. These are all generally well-suited to our setting but either do not adapt to high dimensions, or a direct application would require n ≳ d tr(Σ)/(αε).Nikolov and Tang [51] study instance-optimality specifically for Gaussian noise mechanisms, albeit for data that belong in a bounded convex set. Although this is not the case for Gaussian data, it is worth noting that our error rates match those of [51] , which hold for arbitrary distributions over K, when the bounded set is K = µ + Σ 1/2 B d (1). Privately learning K however would require more samples.Privately learning nuisance parameters. Karwa and Vadhan [41] learn (a constant multiple of) the variance of a univariate Gaussian using n = Õ (log(1/δ)/ε) samples. In high dimensions, privately learning the covariance matrix of a Gaussian in spectral norm requires n ≳ d 3/2 samples [39, 40] , which is more than one needs to learn the mean under known covariance. Brown et al. [13] avoid the bottleneck of private covariance estimation, showing that the sample complexity of Gaussian mean estimation under known covariance with respect to Mahalanobis distance can in fact be matched, even when the covariance is unknown. Their tools also follow the propose-test-release approach and could be modified to fit our setting, but the privacy analysis would still require n ≳ d. Singhal and Steinke [57] learn a subspace in which the majority of the data lie, which could be used as a pre-processing step, followed by projection. However, to recover the set of top k eigenvectors, they require that there exists a large gap between the two consecutive variances, that is, σ k ≥ poly(d)σ k+1 .Comparison with [8] . The paper by Aumüller et al. [8] is the closest work to ours, aiming to find sample-efficient mean estimators with respect to the Euclidean norm in the anisotropic case. Their work focuses on the less general case of diagonal, (almost) known covariance. The sample complexity of their estimator requires n ≳ √ d, whereas our estimator for the known covariance case is dimension-independent, and, as we prove, optimal. However, the focus in [8] is on estimators that satisfy the stricter privacy guarantee of ρ-zCDP, which forces the need for dimension-dependent sample size. This is the key contrast with our dimension-free philosophy. As an interesting distinction, Aumüller et al. [8] provide accuracy guarantees with respect to the ℓ p norm (the upper bounds) for slightly more general classes of so-called well-concentrated distributions, which include subgaussians. It would be interesting to establish optimal private mean estimation bounds with respect to general ℓ p norms. In fact, the optimal non-private sample complexity of Gaussian mean estimation, with matching upper and lower bounds, with respect to general norms has been established only recently, and it depends on the Gaussian mean width of the set induced by the unit dual ball of the norm [19] .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: The introduction includes informal theorem statements for each of our main claims.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 We write [n] = {1, . . . , n}, log denotes the natural logarithm, and B d (c, r) denotes the d-dimensional Euclidean ball with radius r and center c. We omit c if c = 0.We introduce differential privacy here. We say that X, X ′ are neighboring data sets if either ∃j ∈ 3 Differentially private algorithms have indistinguishable output distributions on neighboring data sets.[|X|] such that X ′ = X \ X (j) or ∃j ∈ [|X ′ |] such that X = X ′ \ X ′(j) .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 [25] ). A randomized algorithm A :X * → W is (ε, δ)- differentially private if for all neighboring data sets X, X ′ we have A(X) ≈ ε,δ A(X ′ ).We say that algorithm A satisfies pure differential privacy if it satisfies the definition for δ = 0.Differential privacy satisfies several useful properties, such as post-processing and composition [25, 27] . For further details and guarantees of standard DP mechanisms, see Section A.Our estimators will use the BasicFilter procedure of Tsfadia et al. [63] , whose detailed definition is presented in Section 3 . They provide a framework which allows us to extend an algorithm which is private only for "easy" pairs of data sets, to an algorithm that is private for any worst-case pair. "Easy" pairs of data sets are modelled with respect to a predicate f between two data points: Definition 2.3 (f -friendly, Def. 1.1 [63] ). Let X be a data set over X and let f : X 2 → {0, 1} be a predicate. We say X is f -friendly if for all x, y ∈ X there exists z ∈ X such that f (x, z) = f (z, y) = 1. Definition 2.4 (f -friendly DP, Def. 1.3 [63] ). An algorithm A is called f -friendly (ε, δ)-DP if for any neighboring data sets X, X ′ , such that X ∪ X ′ is f -friendly, A(X) ≈ ε,δ A(X ′ ). Theorem 2.5 (Theorem 4.11 [63] ). Let A be an f -friendly (ε, δ)-DP algorithm. Given data setX, let v = BasicFilter(X, f, α = 0) and C(X) = {X (j) } {j: vj =1} . Then B(X) := A(C(X)) is (2(e ε -1)ε, 2e ε+2(e ε -1) δ)-DP.We assume data are drawn from subgaussian distributions, which include Gaussians. Definition 2.6 (Subgaussian distributions). The random vector X with mean µ is subgaussian with a p.s.d. covariance matrix proxy Σ if for any λ and any v ∈ R d , E e λ⟨X-µ,v⟩ ≤ e λ 2 v ⊤ Σv/2 . Lemma 2.7 (Norm of the subgaussian vector [36, 65] ). Let X = (X (1) , . . . , X (n) ) be drawn i.i.d. from the subgaussian distribution with mean µ and covariance-proxy Σ. With probability at least1 -β, ∥ 1 n n j=1 X (j) -µ∥ 2 ≤ tr(Σ)/n + 2∥Σ∥ 2 log(1/β)/n.3 Nearly-matching upper and lower bounds under known covariance Algorithm 1 proceeds in two simple steps. The first step filters out outliers so that all remaining pairs of data points satisfy the re-scaled distance predicate dist M,λ and, assuming enough data points remain, the second step releases their empirical mean along with appropriate Gaussian noise.We retrieve the folklore result, by taking M = I d , λ ≈ tr(Σ), which is known (otherwise, can be easily privately estimated as in Section 4). The filtering then guarantees that all pairs of points are within distance tr(Σ), and adds spherical Gaussian noise with covariance tr(Σ)I d /(ε 2 n 2 ). To retrieve the optimal bound, take M = Σ, which splits the privacy budget unevenly among coordinates. Then, λ ≈ tr(Σ 1/2 ) and the Gaussian noise has covariance tr(Σ 1/2 )Σ 1/2 /(ε 2 n 2 ), as in [8] .Algorithm 1 Private Re-scaled Averaging: Avg M,λ,ε,δ (X)Require: Data set X = (X (1) , . . . , X (n) ) T ∈ R n×d . Privacy parameters: ε, δ > 0. Failure probability β > 0. Symmetric invertible matrix M . Parameter λ.1: Let dist M,λ (x, y) = 1{∥M -1/4 (x -y)∥ 2 ≤ λ}. 2: v = BasicFilter(X, dist M,λ , α = 0). 3: Let C = {X (j) } {j: vj =1} . 4: Compute nC = |C| -log(1/δ) ε + z where z ∼ Lap( 1 ε ). 5: if |C| = 0 or nC ≤ 0 then 6: return ⊥. 7: return μ = 1 |C| x∈C x + η where η ∼ N 0, 8 log(1.25/δ)λ 2 ε 2 n2 C M 1/2 . 8: procedure BasicFilter(X, f, α) ▷ Algorithm 4.3 from [63].9:for j = 1, . . . , n do 10:Letz j = n k=1 f (X (j) , X (k) ) -n/2.Sample v j = Bern(p j ), wherep j =      0, if z j ≤ 0, 1, if z j ≥ (1/2 -α)n, zj (1/2-α)n , otherwise.12:return v = (v 1 , . . . , v n ) Theorem 3.1. Let ε ∈ (0, 10), δ ∈ (0, 1), α > 0, β ∈ (0, 1). Algorithm 1 is (ε, δ)-differentially private.Let X be a data set of size n, drawn from a subgaussian distribution with covariance-proxy Σ and mean µ.Given M = Σ, λ ≥ 2 tr(M -1/4 ΣM -1/4 ) + 2 2∥M -1/4 ΣM -1/4 ∥ 2 log( n β ), with probability at least 1 -β, Algorithm 1 returns μ such that ∥μ -µ∥ 2 ≤ α, as long asEQUATIONwhere Ω hides constants and a log factor of the third term multiplied with itself.The theorem holds more generally for any symmetric invertible M , and λ satisfying the assumptions. We sketch the proof of Theorem 3.1 next. All remaining details are in Appendix B.Proof sketch. We start with the accuracy analysis. First we show that the original dataset X passes through BasicFilter (i.e., C = X) with high probability. It suffices to show that each pairj ̸ = k ∈ [n], satisfies dist M,λ (X (j) , X (k) ) = 1 with probability 1 -β/n 2 . Observe that for j ̸ = k, M -1/4 (X (j) -X (k)) is subgaussian with mean 0 and covariance proxy 2M -1/4 ΣM -1/4 . By Lemma 2.7 and our setting of λ, indeed ∥M -1/4 (X (j) -X (k) )∥ 2 ≤ λ for each pair with probability 1 -β/n 2 . We condition on C = X. With high probability by the CDF of the Laplace distribution and since |C| = n = Ω(log(1/δβ)/ε), nC = Ω(n). Thus, the algorithm does not abort, and returns estimate μ. It remains to upper bound the total error of μ. This is at most the error of the empirical mean plus the error due to noise ∥η∥ 2 . By Lemma 2.7, with high probability, the former is Õ( tr(Σ)/n) and the latter Õ(λ tr(M 1/2 )/(εn)). Substituting M = Σ, and the value for λ, the total error becomes Õ( tr(Σ)/n + tr(Σ 1/2 )/(εn)), which yields the stated sample complexity.The privacy analysis follows the steps of [63, Claim 3.4] . By Theorem 2.5, it suffices to show that lines 4-7 of Algorithm 1, namely, A, are dist Σ,β -friendly DP. Consider neighboring inputs X, X ′ , differing in the n-th data point w.l.o.g., that isX ′ = X \ X (n) . Since ||X| -|X ′ || = 1, by the guarantees of the Laplace mechanism, the r.v.s nX , nX ′ in Line 4 are (ε, 0)-indistinguishable. Moreover, they both satisfy nX , n′ X < |X| with probability 1-δ/2 > 1/2. Conditioning on this event for the remainder of the sketch, we can fix nX = n′ X = n < |X|, for some value n. If n ≤ 0, both runs abort. Otherwise, it suffices to show that Line 7 adds sufficient noise to maintain privacy. By post-processing, since M is not data-dependent, this is equivalent to ensuring thatN (M -1/4 1 |X| |X| i=1 X (i) , v 2 I d ) ≈ ε,δ N (M -1/4 1 |X|-1 |X|-1 i=1 X (i) , v 2 I d ) where v = (2λ/n)( 2 log(1.25/δ)/ε). This is true by the guarantees of the Gaussian mechanism applied to f (X) = M -1/4 |X| i=1 X (i) /|X|, whose ℓ 2sensitivity for dist Σ,λ -friendly X, X ′ can be upper bounded by 2λ/|X| ≤ 2λ/n (since 0 < n < |X|, by assumption). By composition, A indeed satisfies dist M,λ -friendly (O(ε), O(δ))-DP.We show that the sample complexity of Theorem 3.1 is optimal. We briefly explain our lower bound construction here. All remaining details are in Appendix C.Proof Sketch of Theorem 1.2. Let Σ = diag(σ 2 ). Assume w.l.o.g. that σ 2 1 ≥ . . . ≥ σ 2 d . Partition the set of coordinates into buckets S k = {i ∈ [d] : σ i ∈ σ 1 • (2 -k , 2 -k+1 ]}, ∀k ∈ [log(d)] and S log(d)+1 = [d] \ k∈[log(d)] S k . We have that k∈[log(d)+1] i∈S k σ i = ∥σ∥ 1 .Consider the bucket S which contributes the most to this sum and let σ S be the maximum variance in this bucket. It must be that |S| ≥ ∥σ∥1 (log(d)+1)σ S . The lower bound of [39, Theorem 6.5] for isotropic Gaussians, implies that any (ε, δ)-private mean estimator which returns, with constant probability, an estimate μS with error α for the coordinates in S (note that they are all within a factor of 2), requires n = Ω(|S|σ S /(αε log(d))) = Ω(∥σ∥ 1 /(αε log 2 (d))) samples. As an estimator for the d-dimensional Gaussian mean restricted to S, would give us such a μS , the statement follows.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss limitations of this work in the introduction, in Section 4, and when outlining directions for future work.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
handling unknown covariance: 
 In this section we consider the case of unknown covariance. First, recall that Ω(d 3/2 ) samples are required to privately learn the covariance matrix in spectral norm [40] , which is prohibitive. The lower bound instance is an almost-isotropic Gaussian, which means that anisotropic distributions may circumvent it. Still, the superlinear dependence on d implies that this approach will yield suboptimal sample complexity for mean estimation. Avoiding private covariance estimation, Brown et al. [13] propose a "covariance-aware" private mean estimator which returns the mean with Gaussian noise which scales with the empirical covariance matrix of the data set Σ X , as N (0, λ 2 M Σ X /(ε 2 n 2 )) for appropriate factor λ 2 M . Since adding data-dependent noise can break privacy, a pre-processing step is required to ensure that no outliers exist in the data set with respect to the empirical covariance, roughly ensuring that ∥Σ-1/2 X (X (k) -X (j) )∥ 2 ≤ λ M , for all j ̸ = k ∈ [n].In our case, to maintain the accuracy guarantee of the known-covariance case, the Gaussian noise should be N (0,λ 2 Σ 1/2 X /(ε 2 n 2 ))and all data points should satisfy ∥Σ -1/4 X (X (k) -X (j) )∥ 2 ≤ λ. Note that n ≥ tr(Σ)/∥Σ∥ 2 samples suffice for the empirical covariance to be close to the true covariance Σ in spectral norm [43] , so applying the algorithm from [13] could maintain accuracy while still allowing a dimension-free sample complexity. Unfortunately, we still cannot use this approach because n ≥ d samples are required for the privacy analysis to go though, namely, for neighboring data sets X, X ′ it holds that N (0, Σ1/2 X ) ≈ ε,δ N (0, Σ 1/2 X ′ ) for ε ≈ d/n,which forces us to take n ≥ d/ε samples. The same is true for the follow-up works of [14, 44] which give polynomial-time versions of this algorithm with slightly better statistical guarantees.Luckily, our accuracy guarantee does not require the variance estimate in all directions to be accurate. For example, consider all directions with variance at most ∥Σ∥ 2 /d. Adding spherical Gaussian noise to these directions maintains a dimension-free error, without requiring tighter estimates for their variance. Thus, on a high level, our approach for mean estimation in the unknown covariance case is to identify and estimate as many of the top variances as our sample size allows, which turns out to be k ≈ ε 2 n 2 , while adding spherical Gaussian noise to the remaining ones.We sketch the proof of the following theorem. All remaining details are in Appendix D. Theorem 4.1. Let parameters ε, δ ∈ (0, 1). Let X ∼ N (µ, Σ) n with unknown covariance Σ. Algorithm 2 is (ε, δ)-differentially private and, with probability 1 -β, returns an estimate μ such Algorithm 2 Private Re-scaled Averaging with Unknown Covariance Require: Data set X = (X (1) , . . . , X (2n) ) T ∈ R 2n×d . Privacy parameters: ε, δ > 0. Failure probability β > 0. 2 (1/δβ) + log(εn) and ℓ ← Θ(log(d)). 3: Split the dataset into two equal halves: X var and X mean . 4: Split X var into m = ⌊ n 2ℓ ⌋ groups of size 2ℓ. Define X (j,r) as the r-th sample in the j-th group. 5: for each group j = 1 to m and each dimension i = 1 to d do1: Require n = Ω log 2 (d) + log( 1 δβ ) log( 1 δ ) log(d)/ε . 2: Let k ← ε 2 n 2 / log 2 (d) log(1/δ) logEQUATIONwhere the symbol Ω hides multiplicative logarithmic factors in 1/β.Next, we describe Algorithm 2 and introduce some of its subroutines along with their guarantees. All omitted proofs are in Appendix D. Our algorithm receives a data set X (1) , . . . , X (n) , where each X (i) is a d-dimensional vector distributed as N (µ, Σ). The algorithm starts by splitting the dataset into m = ⌊n/(2ℓ)⌋ groups each of size 2ℓ, where ℓ = Θ(log d). Denote the elements of each group j by X (j,1) , . . . , X (j,2ℓ) . Within each group j, for each coordinate i, we compute an estimateV (j) i for Σ ii : V (j) i = 1 2ℓ ℓ r=1 (X (j,2r-1) i -X (j,2r) i ) 2 .For convenience, we define what it means for the V (j) i variables to provide a good estimate of the set of{Σ ii } i∈[d] .Definition 4.2. Given variances Σ 11 , . . . , Σ dd and given a set of estimates, V = {V(j) i } j∈[m],i∈[d] , we say that V is valid if |{j : ∀i ∈ [d], Σ ii /2 ≤ V (j) i ≤ 2Σ ii }| ≥ 4m/5.Proof sketch of Theorem 4.1. For ease of notation, we assume that Σ = diag(σ 2 ). We start from the accuracy analysis. Assume n satisfies the sample complexity bound of Eq. ( 4). By Chernoff bound, since ℓ = Θ(log(d)) and m = Ω(log(1/β)), with probability 1 -β, V is valid. We use the estimates V (j) i as inputs to private procedures: FindKthLargestVariance(V, k) (compute the k-th largest variance up to a multiplicative constant), VarianceSum(V, I) (compute the sum i∈I σ 2 i up to a multiplicative constant), and TopVar(V, R, k) (identify the indices of the at-most-k largest variances σ 2 i ≥ R). The first two tasks can be implemented by the Stable Histogram algorithm [16] if m = Ω(log(1/δ)/ε). TopVar can be implemented via the Sparse Vector technique [26, 54, 31] , if m = Ω( k log(1/δ) log(d/β)/ √ εn). Both are satisfied for the given m = n/2ℓ. With these procedures, the algorithm privately learns the k-th largest variance R, identifies the top k coordinates, I top , and learns estimates {σ i } Itop that are accurate up to a multiplicative constant.Next, we estimate the mean µ in the coordinates I top separately from I bot := [d] \ I top , denoted by µ top and µ bot , respectively. Denote vector σ top = ({σ i } i∈Itop ) and σ bot = ({σ i } i∈I bot ). To estimate µ top , Algorithm 1, given input vectors X (1) , . . . , X (n) , restricted to coordinates I top , diagonal matrix M , with M ii = σ2 i (assume that the rows and columns of M are indexed by I top ), and λ ≈ ∥σ top ∥ 1 , returns an estimate μtop with error α (since the sample complexity of Eq. ( 4) is larger than the one required by Theorem 3.1).To estimate µ bot , we do not know the variances, so we use the naïve approach. We first call VarianceSum once again, to provide an estimate t of ∥σ bot ∥ 2 up to a multiplicative constant. Given t, we again call Algorithm 1, now for a (d -k)-dimensional estimation problem. Given input vectors X (1) , . . . , X (n) , restricted to coordinates I bot , matrix M = I d-k , and λ ≈ t, Algorithm 1 returns an estimate μbot with error α as long as n = Ω(√ d∥σ bot ∥ 2 /(αε)). By Hölder's inequality, ∥σ bot ∥ 2 ≤ ∥σ bot ∥ 1 ∥σ bot ∥ ∞ ≤ ∥σ∥ 1 ∥σ bot ∥ ∞ .By the guarantees of TopVar and FindKthLargestVariance, ∥σ bot ∥ ∞ is smaller than the k-th largest variance of Σ up to a multiplicative constant, which, in turn, must be smaller than ∥σ∥ 1 /k. Substituting this above, we obtain that it suffices for the stated sample complexity to additionally satisfy n = Ω(√ d∥σ∥ 1 /( √ kαε)), which can be confirmed by substituting the definition for k.The privacy guarantee follows directly by composition of O(1) (ε, δ)-DP mechanisms.Remark 1. We note that the sample complexity of Algorithm 2 in fact depends on the decay of the diagonal elements of Σ, and can yield improved bounds for easier instances. In particular, the error of the algorithm due to privacy is in the order of ∥σ Itop ∥ 1 /(εn) + |I bot |∥σ I bot ∥ 2 /(εn). Thus, if σ follows an exponential decay, i.e., the i-th largest variance is proportional to e -(i-1) , or all σ bot variances are smaller than ∥σ∥ 1 /d, then it suffices to learn only the top k = log(d) variances and the error almost matches that of the known-covariance case, up to additional logarithmic factors in d, 1/δ. Moreover, identifying easier instances is possible by computing a private histogram over log(d) buckets of the form (2 -j , 2 -j+1 ]∥σ∥ ∞ , given n = Õ(log(d)/ε) samples [16, 41] . Thus, we can determine special cases where the decay of Σ allows us to achieve the optimal rate of Theorem 1.1 even with unknown diagonal covariance. But without further assumptions, our algorithm has sample complexity that depends on d 1/4 . The question of the optimal sample complexity for mean estimation in the case of unknown covariance, which captures anisotropic distributions, remains open. 
conclusion and future work: 
 We present (ε, δ)-differentially private mean estimators for subgaussian distributions with error α as measured in Euclidean distance, with high probability, as long as the sample size is n = Θ tr(Σ)/α 2 + tr(Σ 1/2 )/(αε) . The sample complexity is thus dimension-independent when the covariance is highly anisotropic. We show that this is the optimal sample complexity for this task up to logarithmic factors. We also present an algorithm in the more challenging case of unknown covariance, whose sample complexity has improved dependence on the dimension, that is, d 1/4 .In the known covariance case, the dependence on log(1/δ) could possibly be decoupled from the tr(Σ 1/2 )/(αε) term. This is an artifact of the Gaussian noise added for privacy and can possibly be avoided using mean estimators based on the exponential mechanism, as in the spherical Gaussian case [13, 3, 35] , but the volumetric arguments involved in their analysis incur factors dependent on d, which seem hard to overcome.A more interesting direction for future work is the case of unknown covariance. We can determine special cases where the decay of Σ allows us to achieve the optimal rate of Theorem 1.1 with unknown diagonal covariance. What is the appropriate norm in which one needs to learn Σ for the current known-covariance approach to be accurate, and how many samples are needed for this task privately? More generally, the optimal sample complexity of mean estimation in the unknown (even diagonal) covariance case for anisotropic distributions (possibly achieved by an algorithm which doesn't follow the same structure) is an open question.of Computing, funded by FODSI. We also wish to acknowledge funding from the European Union (ERC-2022-SYG-OCEAN-101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [NA] Justification: The paper does not include experiments. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper does not contribute data or models with high risk of misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: Definition A.1 (Laplace distribution). For v ≥ 0, let Lap(v) denote the Laplace distribution over R, which has probability density function p(z) = 1 2σ e -|z|/v . From the CDF of the Laplace distribution, we get that Pr z∼Lap(v) [z ≥ v log(1/2β)] = β. Definition A.2 (Laplace Mechanism, [25] ). Let f : X * → R, data set X over X , and privacy parameter ε. The Laplace Mechanism returns 25] ). The Laplace Mechanism is ε-differentially private.f (X) = f (X) + Lap(v), where v = ∆ f /ε and ∆ f = max X∼X ′ |f (X) -f (X ′ )|. Lemma A.3 ([Definition A.4 (Gaussian Mechanism, [25] ). Let f : X * → R d , data set X over X , and privacy parameters ε, δ. The Gaussian Mechanism returnsf (X) = f (X) + N (0, v 2 I d ), where v = ∆ f 2 log(1.25/δ)/ε and ∆ f = max X∼X ′ ∥f (X) -f (X ′ )∥ 2 is the global ℓ 2 -sensitivity of f . Lemma A.5 ([25]). The Gaussian Mechanism is (ε, δ)-differentially private.Differential privacy is maintained under post-processing and degrades mildly under composition.Lemma A.6 (Composition, [25, 27, 38] ). Let M be an adaptive composition of M 1 , . . . , M T , that is, on input X, M (X) := M T (X, M T -1 (X, . . . , M 2 (X, M 1 (X)))). Then 1. (Basic composition) If M 1 , . . . , M T are (ε 1 , δ 1 ), . . . , (ε T , δ T )-differentially private respec- tively, then M is (ε, δ)-differentially private for ε = T t=1 ε t and δ = T t=1 δ t .2. (Advanced composition) Let ε t > 0, δ t ∈ [0, 1] for t ∈ {1, . . . , T }, and δ ∈ [0, 1]. If M 1 , . . . , M T are (ε 1 , δ 1 ), . . . , (ε T , δ T )-differentially private respectively, then M is (ε δ , δ + T t=1 δ t )-differentially private where εδ is given by:εδ = k ℓ=1 (e ε ℓ -1)ε ℓ e ε ℓ + 1 + k ℓ=1 ε 2 ℓ log 1 δ .Fact A.7 (Fact 2.17 [63] reduced to pure DP). Let Y ≈ ε Y ′ random variables over Y and let the eventE ⊆ Y be such that Pr[Y ∈ E], Pr[Y ′ ∈ E] ≥ q. Then Y |E ≈ ε/q Y ′ |E .We state here again the general theorem which holds for any M .Theorem B.1. Let ε ∈ (0, 10), δ ∈ (0, 1), α > 0, β ∈ (0, 1). 4 Algorithm 1 is (ε, δ)-differentially private. Let X be a data set of size n, drawn from a subgaussian distribution with covariance-proxy Σ and mean µ. Given M = Σ, λ ≥ 2 tr(M -1/4 ΣM -1/4 ) + 2 2∥M -1/4 ΣM -1/4 ∥ 2 log( n β ), with probability at least 1 -β, Algorithm 1 returns μ such that ∥μ -µ∥ 2 ≤ α, as long asEQUATIONfor some universal constant C. If Σ is known, choosing M = Σ and substituting λ, the sample complexity becomesEQUATIONAlthough the theorem holds for any M, λ, choosing M = Σ gives us the optimal bound. 5 Remark 2. If M is such that Σ ⪯ M , we may assume without loss of generality that M is invertible. Indeed, if this is not the case, then we know that the distribution of the data is supported on a lower-dimensional subspace along with its mean µ. Using M , we can project onto this subspace. In this context, we can refocus our analysis on the scenario where M is an invertible matrix.Computational complexity We note that Algorithm 1 has time complexity O(n 2 ), which can be further improved to O(n log n) as in [63] .The guarantees of Theorem B.1 follow by combining Theorem B.3 and Theorem B.5 below and re-scaling parameters ε, δ, β with appropriate constants.We start with the accuracy analysis. We first prove that for subgaussian data sets, all data points pass the filter with high probability.Lemma B.2. Let X = (X (1) , . . . , X (n) ) be a data set drawn from a subgaussian distribution with covariance proxy Σ. Let β ∈ (0, 1), M invertible matrix and some λ ≥ 2 tr(M -1/4 ΣM -1/4 ) + 2 2∥M -1/4 ΣM -1/4 ∥ 2 log(n/β) given as inputs to Algorithm 1. Then the BasicFilter procedure outputs C = X, with probability 1 -β.Proof. It suffices to show that in BasicFilter we have p j = 1 for j ∈ [n] (so that v j = 1 and thus C = X). For each j, k ∈ [n], we want to show dist M,λ (X (j) , X (k) ) = 1 with probability at least 1 -β/n 2 . For j = k, it is trivial. What is left is to show for j ̸ = k,EQUATIONwith probability at least 1 -β/n 2 . First observe that -X (k) is a subgaussian vector independent of X (j) with mean -µ and covariance proxy Σ. Hence, X (j) -X (k) is a subgaussian vector with mean 0 and covariance proxy 2Σ, and so M -1/4 (X (j) -X (k) ) is subgaussian with mean zero and covariance proxy 2M -1/4 ΣM -1/4 . By Lemma 2.7, with probability 1 -β/n 2 ,∥M -1/4 (X (j) -X (k) )∥ 2 ≤ 2 tr(M -1/4 ΣM -1/4 ) + 2 2∥M -1/4 ΣM -1/4 ∥ 2 log(n/β) .Then we union bound all n(n -1) pairs of j, k ∈ [n], j ̸ = k such that Eq. ( 7) holds with probability of at least 1 -β. 5 For intuition, consider adding noise N (0, c 2 i ) to each coordinate i. (It is clear that the privacy budget should be distributed unevenly among coordinates.) We would like to minimize the ℓ2 norm of this noise, which is approximately d i=1 c 2 i . The average sensitivity of each coordinate of a Gaussian is σi, so to achieve total privacy loss ε, by advanced composition, we require the ci's to satisfy d i=1 σ 2 i /c 2 i ≤ ε 2 . Solving this optimization problem, we find that ci ∝ ∥σ∥1σi, which corresponds to noise N (0, ∆ 2 Σ 1/2 ), for ∆ 2 ≈ ∥σ∥ 1 ε 2 n 2 . The same reasoning can be applied to the case of the Mahalanobis error metric [13] where adding noise N (0, ∆ 2 M Σ) for ∆ 2 M ≈ d ε 2 n 2 gives us the optimal bound. Here the minimization objective is roughly Σ d i=1 c 2 i /σ 2 i so the optimal solution requires ci ∝ σi.Theorem B.3. Let ε > 0, δ ∈ (0, 1), α > 0, β ∈ (0, 1). Suppose n ≥ 2 log(1/δβ)/ε. Let X = (X (1) , . . . , X (n) ) be a data set drawn from a subgaussian distribution with mean µ and covariance proxy Σ. Then, given invertible matrix M and λ ≥ 2 tr(M -1/4 ΣM -1/4 ) + 2 2∥M -1/4 ΣM -1/4 ∥ 2 log(n/β), Algorithm 1, with probability 1 -7 2 β, returns μ such that∥μ -µ∥ 2 ≤ tr(Σ) √ n + 2∥Σ∥ 2 log(1/β) √ n + 4 2 log(1.25/δ)λ εn tr(M 1/2 ) + 2∥M 1/2 ∥ 2 log(1/β) .Proof. Let µ C , µ X be the sample mean of C and X, respectively. By the triangle inequality, we decompose it intoEQUATIONBy Lemma B.2, C = X with probability 1 -β. Condition on this event for the rest of the proof.Then, nC = n -log(1/δ) ε + z satisfies nC ≥ 0.5n > 0 with probability 1 -β/2 because Pr z < log(1/δ) ε -0.5n ≤ Pr z < log(1/δ) ε - log(1/δβ) ε = Pr z < - log(1/β) ε = 1 2 βby Definition A.1 and our assumption that n ≥ 2 log(1/δβ)/ε. Conditioning on this assumption, we do not abort and with probability 1 -β, by Lemma 2.7,∥μ -µ C ∥ 2 = ∥η∥ 2 ≤ 4 2 log(1.25/δ)λ εn tr(M 1/2 ) + 2∥M 1/2 ∥ 2 log(1/β) .Again, by Lemma 2.7, with probability 1 -β,∥µ X -µ∥ 2 = 1 n n j=1 X (j) -µ 2 ≤ tr(Σ) √ n + 2∥Σ∥ 2 log(1/β) √ n .Moreover, since C = X, it holds that µ X = µ C . Combining these results into Eq. ( 8), the algorithm does not abort and we retrieve the stated error bound, with probability 1 -7 2 β.We now move to the privacy analysis. Lemma B.4. In Algorithm 1, nC < |C|, with probability 1 -δ/2.Proof. It follows that by Definition A.1,Pr [n C ≥ |C|] = Pr [|C| -log(1/δ)/ε + z ≥ |C|] = Pr [z ≥ log(1/δ)/ε] = 1 2 δ.Note that this holds regardless of whether C is dist Σ,β -friendly or whether X is subgaussian.The privacy analysis follows the steps of [63, Claim 3.4 ]. Theorem B.5. Let ε ∈ (0, 1/2), δ ∈ (0, 1/2). For any input parameters M, λ, Algorithm 1 satisfies (21ε, e 10 δ)-DP.Proof. It suffices show that lines 4-7 of Algorithm 1 are dist Σ,β -friendly (ε ′ , δ ′ )-DP, such that byTheorem 2.5, Algorithm 1 is (2(e ε ′ -1)ε ′ , 2e ε ′ +2(e ε ′ -1) δ ′ )-DP.Denote lines 4-7 of Algorithm 1 as algorithm A. Consider neighboring inputs X, X ′ such that X ∪X ′ is dist Σ,β -friendly. Assume without loss of generality X ′ = X \ X (j) so that |X ′ | = |X| -1. Let A(X), A(X ′ ) represent the outputs of two independent executions of A and let N X , N X ′ be the random variable in line 4 of the algorithm. We want to show A(X) ≈ ε ′ ,δ ′ A(X ′ ).Note that |X| > 0. If |X ′ | = 0, then |X| = 1 and Pr [A(X ′ ) = ⊥] = 1.We then show that Pr [A(X) = ⊥] ≥ 1 -e ε δ/2. This holds since by Definition A.1,Pr[ NX ≤ 0] = Pr [z ≤ log(1/δ)/ε -1] = Pr [z ≤ log(1/(e ε δ))/ε] = 1 - e ε δ 2 .Therefore, in this case, A(X) ≈ 0,e ε δ/2 A(X ′ ). That is, if ε ≤ 1/2, A is (0, δ)-DP.Now consider |X ′ | > 0. By Lemma B.4, We know Pr[ NX < |X|] = Pr[ NX ′ < |X ′ |] = 1 -δ/2. Hence, Pr[ NX ′ < |X|] = Pr[ NX ′ < |X ′ | + 1] ≥ 1 -δ/2. Then what is left is to compare A(X)| NX <|X| , A(X ′ )| NX ′ <|X| . By Lemma A.3, NX ≈ ε,0 NX ′ as |X| -|X ′ | = 1. By Fact A.7, NX | NX <|X| ≈ ε/(1-δ/2),0 NX ′ | NX ′ <|X| .In order to perform composition by Lemma A.6, we now show that for each fixedn < |X|, A(X)| NX =n ≈ ε,δ A(X ′ )| NX ′ =n as follows: Choose n < |X|. If n ≤ 0, then A(X)| N X =n = A(X ′ )| N X =n = ⊥ and we are done. If 0 < n < |X|, it suffices to show N ( 1 |X| |X| i=1 X (i) , v 2 M 1/2 ) ≈ ε,δ N ( 1 |X|-1 |X| i=1,i̸ =j X (i) , v 2 M 1/2 ), where v 2 = 8 log(1.25/δ)λ 2 ε 2 n2, which, by post-processing, is equivalent toEQUATION) Define vector D = 1 |X| |X| i=1 X (i) -1 |X|-1 |X| i=1,i̸ =j X (i) . As X ∪ X ′ is dist Σ,β -friendly, for every i ∈ [|X|] \ {j}, there exists some Y (i) ∈ R d such that dist Σ,β (X (i) , Y (i) ) = dist Σ,β (X (j) , Y (i) ) = 1. We have ∥M -1/4 D∥ 2 = 1 |X|(|X| -1) M -1/4     |X| i=1,i̸ =j X (i)   -X (j) (|X| -1)   2 ≤ 1 |X|(|X| -1) |X| i=1,i̸ =j M -1/4 X (i) -Y (i) 2 + M -1/4 Y (i) -X (j) 2 (by triangle inequality) ≤ 1 |X|(|X| -1) |X| i=1,i̸ =j 2λ = 2λ |X| ≤ 2λ n .(by dist Σ,β -friendly assumption and since 0 < n < |X|)We know Equation ( 9) holds by applying the guarantees of the Gaussian mechanism (Lemma A.5) where we setf (X) = M -1/4 1 |X| |X| i=1 X (i) and ∆ f = 2λ/n.Combining these results, we have A is(ε + ε 1-δ/2 , δe ε/(1-δ/2) + δ 2 )-DP in this case. For ε ≤ 1/2, δ ≤ 1/2, this becomes at most (3ε, 2δ)-DP.Therefore, overall, by Theorem 2.5, Algorithm 1 is (2(e ε ′ -1)ε ′ , 2e ε ′ +2(e ε ′ -1) δ ′ )-DP with ε ′ = 3ε, δ ′ = 2δ. So for ε ≤ 1/2, the algorithm is (21ε, e 10 δ)-DP overall.The so-called packing lower bound technique [32, 10] implies a lower bound on the order of d for the number of samples required by any pure DP algorithm learning the mean of a Gaussian distribution, even in the anisotropic case we consider in this paper.There exist several statements in prior works which establish the lower bound for learning a Gaussian distribution with known covariance in TV distance, which is equivalent to learning the mean in Mahalanobis distance, or to learning the mean in ℓ 2 norm in the isotropic case [18, Lemma 5.1] . It is trivial to observe that the dependence on the dimension d persists in the anisotropic case, yet we include the proof here for completeness. Theorem C.1. For any α < R/2, any ε-DP algorithm which estimates the mean µ ∈ B d (R) of a Gaussian distribution with known covariance Σ, up to accuracy α in ℓ 2 norm with probability 9/10, requires n ≥ d log(R/2α) ε samples.Proof. Consider a 2α-packing of the d-dimensional R-radius ball, denoted by P 2α ⊂ B d (R). That is, ∀u, v ∈ P, ∥u -v∥ 2 > 2α, so that the balls with centers u, v and radius α are disjoint:B d (u, α) ∩ B d (v, α) = ∅.We consider the family of Gaussian distributions {N (u, Σ)} u∈P2α . Suppose A is an ε-DP algorithm with the stated accuracy requirement. This implies that ∀u ∈ P 2α :EQUATION)At the same time, for any pair of samples X, X 0 of size n, and any measurable set B ⊂ range(A), by the privacy guarantee,Pr A [A(X) ∈ B] ≤ e εn Pr A [A(X 0 ) ∈ B]. This implies specifically that for u 0 , u ∈ P 2α ,EQUATIONWe have1 ≥ Pr A,X0∼N (u0,Σ) n [A(X 0 ) ∈ u∈P2α B d (u, α)] = u∈P2α Pr A,X0∼N (u0,Σ) n [A(X 0 ) ∈ B d (u, α)] ({B d (u, α)} u∈P2α disjoint) ≥ u∈P2α e -εn Pr A,X∼N (u,Σ) n [A(X) ∈ B d (u, α)](by Eq. ( 11))≥ |P 2α |e -εn • 9 10.(by Eq. ( 10))We conclude that n≥ log |P2α| ε . Since |P 2α | ≥ R α d , it follows that n ≥ d log(R/2α) ε .This lower bound makes ε-DP prohibitive for the regime we consider in our setting. To compare with our upper bounds for (ε, δ)-DP, suppose that we want to learn µ with accuracy cσ 1 < R, where c > 0 is a small constant. Then our main result implies that this is achievable with n ≤ C ∥σ∥1 εσ1 samples for some constant C > 0, whereas under ε-DP, we would need at least n ≥ d ε ≫ ∥σ∥1 εσ1 for the regime we consider in this paper.The so-called tracing or fingerprinting lower-bound technique [15, 60, 17, 61, 28] is the main technique used to yield lower bounds for mean estimation under (ε, δ)-DP. Kamath et al. [39, 40] apply it to give lower bounds for the problem of learning a Gaussian in TV distance (which is equivalent to learning the Gaussian in Mahalanobis distance for the known covariance case, or to the isotropic case).Theorem C.2 (Theorem 6.5 [39] ).If A : R d×n → [-Rσ, Rσ] d is (ε, δ)-DP for δ = Õ( √ dRn ), and for every Gaussian distribution with mean µ ∈ [-Rσ, Rσ] d and known covariance matrixσ 2 I d , with probability 2/3, ∥A(X) -µ∥ ≤ α ≤ √ dσR/3, then n ≥ dσ 24αε log(dR) .Following exactly the same steps as the proof of the theorem under the slightly more general case of known covariance Σ = diag(σ 2 ) gives us a weak lower bound for our setting, on the order of n ≥EQUATION1 log(dR) . However, a more careful application of the same theorem directly gives us the following stronger lower bound, which implies that our algorithm for the known covariance case is near-optimal.Theorem C.3. If A : R d×n → R d is (ε, δ)-DP for δ = O((n log(n)) -1), and for every Gaussian distribution with mean µ ∈ [-1, 1] d and known covariance proxy Σ = diag(σ 2 ), with probability2/3, ∥A(X) -µ∥ ≤ α = O(∥σ∥ 1 / log(d)), then n = Ω ∥σ∥1 αε log 2 (d) . Proof. Assume w.l.o.g. that σ 2 1 ≥ . . . ≥ σ 2 d . Consider a partition of the set of coordinates [d] into buckets S k = {i ∈ [d] : σ i ∈ ( σ1 2 k , σ1 2 k-1 ]}, ∀k ∈ [log(d)] and S log(d)+1 = [d] \ k∈[log(d)] S k . We have that log(d)+1 k=1 i∈S k σ i = ∥σ∥ 1 .Consider the bucket S m which contributes the most to this sum, that is m = arg max i∈Sm σ i . Let σ Sm = max{σ i : i ∈ S m }. It must be that which returns, with probability 2/3, an estimate μSm with error ∥μ Sm -|S m | ≥ ∥σ∥ 1 (log(d) + 1)σ Sm . Otherwise, ∥σ∥ 1 = log(d)+1 k=1 i∈S k σ i ≤ (log(d) + 1)|S m |σ Sm < ∥σ∥ 1 ,EQUATIONNow assume that there exists (ε, δ)-DP algorithm A :R d×n → R d for δ = O 1 n √ log(n), such that, for every Gaussian distribution with mean µ ∈ [-1, 1] d and known covariance proxy Σ = diag(σ 2 ), with probability 2/3, ∥A(X)-µ∥ ≤ α ≤ ∥σ∥1 3(log(d)+1) . Restricting the output A(X) to the coordinates in S m , would give us a mean estimate for S m with error at most α. Combined with Eq. ( 12), this completes the proof of the theorem.We state the main theorem in more detail. Theorem D.1. Let parameters ε, δ ∈ (0, 1). Let X ∼ N (µ, Σ) n with unknown covariance Σ. There exists an (ε, δ)-differentially private algorithm which, with probability 1 -β, returns an estimate μ such that ∥μ -µ∥ 2 ≤ α, as long asEQUATIONEQUATIONandEQUATIONwhere the symbol Ω hides multiplicative logarithmic factors in 1/β and the term in parentheses.Both for estimating µ top , and for estimating µ bot , we use Avg M,λ,ε,δ (Algorithm 1 from Section 3) with appropriate choices of parameters M, λ. Recall that Algorithm 1 satisfies the guarantees of Theorem B.1.For estimating µ top , we use Avg M,λ,ε,δ for estimating the mean of a k-dimensional Gaussian, with input vectors restricted to coordinates I top , XItop , . . . , XItop , the k × k-dimensional diagonal matrix M , with M ii = Σii (we assume that the rows and columns of M are indexed by I top ),and λ = O i∈Itop Σ1/2ii log n β . Denote the output by μtop . Theorem B.1 shows that with probabilityEQUATIONwhere Ω hides multiplicative logarithmic factors in 1/β and the second term.For estimating I bot , we do not know the variances. In order to perform the estimation, we first call the algorithm VarianceSum to provide an estimate Ŝbot such that 1C i∈I bot Σ ii ≤ Ŝbot ≤ C i∈I bot Σ ii for a constant C.Given that estimate, we again will call Avg M,λ,ε,δ , now for a (d-k)dimensional estimation problem. We input the samples X(1)EQUATIONI bot , replace the matrix M with the identity of dimension (d -k) × (d -k), and let λ = O Ŝbot log n β . 6 Denote the output by μbot . The guarantees of Theorem B.1 provide that with probability 1 -β, ∥μ bot -µ bot ∥ 2 ≤ α, if, additionally to Eq. ( 17), we haveEQUATIONwhere Ω hides multiplicative logarithmic factors of 1/β and of the term in parentheses. As we prove below, combining these guarantees would yield the desired result. Additionally, we note that in order for the proof to go through, we split the sample into two groups. One group is used for estimating the variances and the other group is given as an input to the two invocations of VarianceSum. We provide the formal pseudocode in Algorithm 2.Accuracy analysis. We put together the statements of the lemmas above, to establish the overall accuracy guarantee of Algorithm 2. By Lemma D.2, the estimates V (j) i are valid (i.e., at least 4m/5 of the groups have approximation up to 2 for every coordinate), with probability 1 -β as long as m = Ω(log 1 β ). Consequently, Lemma D.4 implies that as long as m = Ω( 1 ε log 1 δβ ), FindKthLargestVariance outputs an estimate of the k-th largest variance, which is accurate up to a constant factor C = 8, with probability 1 -β. By scaling, we can assume that, R/8, is upper bounded by the k-th largest variance. Under this assumption, and as long as m = Ω k log(1/δ) εn log d β , Lemma D.6 implies that w.p. 1 -β, the output of TopVar, I top , is a set of size k, containing indices of elements whose variances are at least R/32. By Lemma D.5, as long asm = Ω 1 ε ′ log 1 δ ′ β ′ = Ω √ k log(1/δ) εlog k δβ , the estimates Σii to the variances in the indices in I top are accurate up to a constant factor, with a failure probability of β/k for each invocation of this lemma, which sums up to a failure probability of β. Similarly, the estimate Ŝbot has the same guarantee. If n is large enough to satisfy the requirement of Line 1, then all previous constraints on m are satisfied.Lastly, the two estimates from Avg M,λ,ε,δ suffer an approximation of α, each with a failure probability of β, provided that the conditions on the sample complexity n, that are given in Eq. ( 17) and Eq. ( 18), 6 We could additionally privately learn the largest variance among I bot , denoted by ŝ and set λ =Ŝbot + ŝ log n β to decouple Ŝbot from the logarithmic factor, but we choose not to for simplicity, and since we did not optimize for logarithmic factors overall.hold. By assumption on the sample complexity (Eq. ( 13),( 14)), the guarantee of Eq. ( 17) indeed holds. It remains to prove that the guarantee of Eq. ( 18) holds as well. We analyze the term i∈I bot Σ ii . Denote vector σ bot = ({σ i } i∈I bot ) whereσ i = Σ 1/2 ii . Then i∈I bot Σ ii = ∥σ bot ∥ 2 . By Hölder's inequality, ∥σ bot ∥ 2 ≤ ∥σ bot ∥ 1 ∥σ bot ∥ ∞ ≤ ∥σ∥ 1 ∥σ bot ∥ ∞ .By the guarantees of TopVar and FindKthLargestVariance, except for a failure probability of O(β), there exists a universal constant C > 1 such thatmax i∈I bot Σ 1/2 ii ≤ C R1/2 .Further, by assumption, R is up to a constant the k-th largest diagonal element of Σ, hence,C R1/2 ≤ 1 k d i=1 Σ 1/2ii .Substituting this above, we obtain thati∈I bot Σ ii ≤ 1 √ k d i=1 Σ 1/2ii .Thus, it suffices for the stated sample complexity to additionally satisfy n = Ω√ d log(1/δ) d i=1 Σ 1/2 ii √ kαε. Substituting the definition for k, we obtain Eq. ( 15), which completes the proof.Privacy analysis. Notice that the output of the algorithm is obtained by composing multiple differentially private mechanisms. Some of these mechanisms access the estimates V (1) , . . . , V (m) instead of the original dataset. Yet, since each input datapoint X (i) influences only one vector V (j) , this implies that any DP guarantees for algorithms that use the V The random variable (X(j,2r-1) i -X (j,2r) i )/ √ 2Σ ii is standard normal. Thus, ℓ r=1 (X (j,2r-1) i -X (j,2r) i ) 2 2Σ iifollows a chi-squared distribution with ℓ degrees of freedom. We use the following concentration property of a Chi-squared random variable [45, Lemma 1] : if Z is Chi-squared with ℓ degrees of freedom, Pr[E[Z]/2 ≤ Z ≤ 2 E[Z]] ≥ 1 -2e -cℓ , for some constant c > 0. Consequently, Pr ℓ 2 ≤ ℓ r=1 (X (j,2r-1) i -X (j,2r) i ) 2 2Σ ii ≤ 2ℓ ≥ 1 -2e -cℓ ,for some constant c > 0.By a union bound over all dimensions i, the probability that all dimensions' variance estimates fall within the specified bounds in a single group j is at least 1 -2d exp(-cℓ). Assuming ℓ ≥ C log d ensures this probability is very high (e.g., at least 7/8 for suitable constant C).Using the Chernoff bound for the binomial distribution, if each group independently satisfies the variance bounds with probability at least 7/8, then the probability that at least 4/5 of the groups satisfy the variance bounds is at least 1 -β for m = Ω(log(1/β)). We propose an algorithm which, receives estimates V (j) ifor the variances and a threshold R, and outputs k indices i ∈ [d] whose variance is at least R/C for some universal constant C. To do so, we use the sparse vector algorithm, which receives a dataset D, queries Q 1 (D), . . . , Q d (D), a threshold T and a natural number k. It outputs k indices i such that Q i (D) ≥ T (approximately). In order to use the sparse vector to identify the largest variances, our dataset D will be V , the collection of estimates. The query Q i (V ) will capture whether the i'th variance is Ω(R). We define the queryQ i (V ) = 1 m j : V (j) i ≥ R/2 ,and the threshold T = 1/2. Intuitively, if Q i (V ) ≥ 1/2 this means that at least half of the values of j, V≥ R/2, which implies that Σ ii ≥ Ω(R), provided that the estimates V are valid. Otherwise, it implies Σ ii ≤ R.We now formally define the sparse vector algorithm [26, 54, 31] , and review its guarantees. See [23, Section 3.6] for a detailed analysis of the sparse vector technique.Algorithm 3 Sparse(D, {Q i }, T, d, ε, δ), from [23] Require: Input is a private database D, an adaptively chosen stream of sensitivity 1/n queries Q 1 , . . ., a threshold T , a cutoff point k, and privacy parameters ε, δ. 1: T ← T + Lap 2 εn 2: σ ← 32k ln(1/δ)v i ← Lap(σ) 7: if Q i (D) + v i ≥ TQ i (D) = 1 m j : V (j) i ≥ R/2 2: T ← 1/2 3: return Sparse(V, {Q i }, T, k, δ)The privacy guarantees of TopVar follow directly from the guarantees of the sparse vector. Next, we describe how to derive the accuracy guarantees. Notice that if the V (j) i are valid, then, for any i such that Σ ii ≥ R: for at least 4m/5 values of j, it holds that V (j) i ≥ R/2, hence, Q i (D) ≥ 4/5. Further, for any i such that Σ ii < R/4, for at least 4m/5 values of j it holds that V (j) i < R/2, hence Q i (D) ≤ 1/5. Hence, if we set the threshold at T = 1/2, and α = 1/4, then, for any i output by the algorithm, Σ ii ≥ R/4. Further, if there are at least k indices i such that Q ii ≥ R, the algorithm will output k indices. We propose an algorithm, Algorithm 5, that receives pre-computed variance estimates V (j) i for each group j and coordinate i. The algorithm uses them to compute an estimate for the k-th largest variance for each V (j) :M j := k-th largest of V (j) 1 , . . . , V (j) d i∈[d].Our algorithm combines all of these estimates in a differentially private manner, using a stable histogram: Algorithm 6. That algorithm splits the real line into buckets, {B b } b∈Z∪{-∞} . It receives the estimates M 1 , . . . , M m ∈ R and outputs the index b of the bucket that contains the largest number of estimates M j (approximately).In our application, we would like to estimate the k-th largest variance up to a multiplicative constant factor, hence, we define the buckets asB b = [4 b , 4 b+1 ) b ∈ Z {0} b = -∞.Denote by b * index of the bucket that contains the k-th largest diagonal entry of Σ. If the estimates V (1) , . . . , V (m) The algorithm for k-th largest variance, Algorithm 5, is presented here:Algorithm 5 FindKthLargestVariance ε,δ ({V (j) i } i∈[d],j∈[m] , k) Require: Pre-computed variance estimates V (j) i for each group j and each coordinate i. Privacy parameters ε, δ > 0. Integer k ≤ d. Number of groups m. 1: for j ∈ [m] do 2: M j ← k-th largest value among {V (j) 1 , V (j) 2 , . . . , V (j) d } 3: Define bins {B b } b∈Z∪{-∞} by: B b = [4 b , 4 b+1 ) b ∈ Z {0} b = -∞ 4: b ← StableHistogram ε,δ ({M j } j∈[m] , {B b }) 5: return M = 4 bWe proceed by defining StableHistogram as introduced in [16] and providing its guarantees, and then we conclude with the proof of Lemma D.4. The presentation of StableHistogram is from [13] . * ∈ Z such that |{M 1 , . . . , M m } ∩ (B b * -1 ∪ B b * ∪ B b * +1 )| ≥ 3m/4 . There exists a constant C > 0 such that, for all 0 < ε, β, δ < 1, if m ≥ C ε log 1 δβ ,then with probability at least 1 -β, the algorithm's output lies in {b -1, b, b + 1}.The privacy guarantees of Algorithm 5 follow directly from the privacy guarantees of Algorithm 6.For the accuracy guarantees, notice that if the estimates V We propose an algorithm that is similar to Algorithm 5, with a single difference: given each estimate V (j) , the algorithm computesM j = i∈I V (j) i .The algorithm is summarized below:Algorithm 7 VarianceSum ε,δ ({V (j) i } i∈[d],j∈[m] , I) Require: Pre-computed variance estimates V (j) ifor each group j and each coordinate i. Privacy parameters ε, δ > 0.Subset I ⊆ [d]. Number of groups m. 1: for j ∈ [m] do 2: M j ← i∈I V (j) i 3: Define bins {B b } b∈Z∪{-∞} by: B b = [4 b , 4 b+1 ) b ∈ Z {0} b = -∞ 4: b ← StableHistogram ε,δ ({M j } j∈[m] , {B b }) 5: return M = 4 bThe proof is identical to the proof of Lemma D.4. In order to carry that proof, one has to notice that if b * is the bucket that contains i∈I Σ ii and if the estimates V (j) are valid, then at least 4m/5 of the estimates M j fall withinB b * -1 ∪ B b * ∪ B b * +1 .NeurIPS Paper ChecklistWe focus on approximate (ε, δ)-DP, as opposed to pure (ε, 0)-DP. However, we omit any dependence on δ in the introduction.This limitation is due to the fact that the Mahalanobis distance equalizes the variance across all directions and forces us to make inferences even in directions where the distribution has particularly small variance.This is the so-called add/remove model of DP, which will be convenient for our use of prior work. The same privacy guarantees will also hold for the swap model, where dHam(X, X ′ ) ≤ 1, up to constant factors.We require ε to be smaller than some constant, due to approximations we take in the privacy analysis. The theorem may hold for ε > 10 but we did not optimize the choice of constant, as this range is already wide. 


Decision: The authors consider the problem of differentially private mean estimation for anisotropic distributions (i.e., assuming the data has high variance only in a few directions or similarly, assuming data has small effective rank). For non-private setting, simple mean gives dimension-independent bound but doing this privately is non trivial. This is an important problem since mean estimation is a subroutine in many private algorithms. The authors consider the known and unknown covariance settings (results for unknown covariance is not tight). Although the paper may not be technically very novel, the results are interesting, non-trivial, and of broad interest in the privacy community. I recommend acceptance.

Reviews: review: paper_summary: paper_summary: The paper studies mean estimation for multivariate Gaussian distributions. It's well known that this problem under differential privacy suffers from a curse of dimensionality- the sample complexity of estimating the mean (in expected $\ell_2^2$ error) scales with $\sqrt{d}$ where $d$ is the dimension. However, the lower bounds are for isotropic covariance matrices, whereas in the real world, covariance matrices are often far from isotropic. The main intuition is that when covariance matrices are far from isotropic, there is a gap between large and small singular values, and hence the number of 'important dimensions' is relatively small- the object behaves 'more lower-dimensional' than the dimension $d$ indicates.

They consider two settings, the known and unknown covariance cases.

1) In the known covariance case, they show a dimension-independent bound (for approximate DP) that depends instead on the sum of (square roots of) singular values. They argue that this is optimal up to logarithmic factors (and also that no pure DP algorithm can achieve such a dimension-independent bound). 

2) For the unknown covariance case, one approach is estimating the covariance and then applying the known-covariance algorithm, but this might be prohibitive since estimating the covariance is known to require at least $d^{3/2}$ samples asymptotically. The authors instead show that it's possible to achieve a bound with a $d^{1/4}$ dependence instead.

For the known covariance case, the authors use the known FriendlyCore algorithm with a carefully specified predicate to remove outliers (points far from the mean in any coordinate), which allows them to bound the sensitivity and then add dimension-independent noise. The lower bounds are adaptations of the packing and fingerprinting approaches used for pure and approximate DP. In the unknown covariance case, they treat large and small singular values differently. Firstly, they learn the identities and values of the top $k$ singular values up to multiplicative factors and use the known covariance algorithm to estimate the mean restricted to these coordinates. For the other coordinates, they use Holder's inequality to bound the $\ell_2$ norm of the singular values. For small singular values, the variance does not need to be as accurately estimated since these directions are less important. Balancing $k$ to optimize the cumulative error gives the sample complexity bound.
strength_weakness: strength_weakness: 1) While the results are interesting, they mostly follow from applying known techniques from the privacy literature- the additional technical insight of this paper is rather limited.

2) The unknown covariance case as presented was confusing to me- is there an assumption that the covariance matrix is diagonal; this seems to be used in the author's proofs and approaches? This wasn't clearly described in the paper and could use clarification. I don't see how to extend the techniques of the authors to deal with general covariance matrices.
questions: questions: 1) Line 829, I believe the authors mean $\|\| \sigma_{bot} \|\|_2$. 

2) Do known lower bounds for estimating the covariance matrix depend on $d$ even with large singular value gaps? Could one hope to get bounds for this problem that depend similarly on the sum of singular values? I am curious if existing results truly rule out the approach of estimating the covariance matrix before using a known covariance algorithm.
limitations: limitations: Yes
paper_summary: paper_summary: This paper presents a new method for estimating the mean of a subgaussian distribution, such that differential privacy is guaranteed (i.e., the final result does not provide too much identifying information about any individual sample).  For the proposed method, in the case of known covariance,  the sample complexity depends only on the trace of the (1/2) power of the covariance matrix. This means that, if the distribution is highly anisotropic (with the variance mostly concentrated in only a few dimensions) then the sample complexity does not depend explicitly on the full dimensionality of the space *at all*, only on the dimensionality of the lower-dimensional space where "most" of the variance lies. This improves on the prior SOTA result, from (Aumüller et al 2023), where the sample complexity explicitly contains a factor of sqrt(d), where d is the full dimensionality of the space. The core algorithm proceeds by first filtering outliers, using a differentially-private filtering mechanism proposed by (Tsfadia et al 2022), and then simply taking the mean of the remaining samples and adding Gaussian noise.

A matching lower bound is also proven, showing that we can't in general do any better asymptotically than O(trace(Σ^(1/2))), up to logarithmic factors.


A variant of the algorithm is proposed for the case of unknown covariance as well, which has sample complexity with an explicit dependence on d^(1/4), which is still an impovement overt the prior SOTA d^(1/2).
strength_weakness: strength_weakness: - The order of the presentation could be improved. The preliminaries section could be presented earlier in the paper, before the definitions given are referred to.
- No empirical tests are performed. Including a numerical simulation of the algorithm would increase the reader's confidence in the correctness of the theoretical  results, as well as give an idea of the tightness of the bound in practice.
questions: questions: - Is it possible to derive a separate, tighter lower bound for the the case of unknown covariance? Or is it possible that we may in the future improve from the d^(1/4) result in this paper?
limitations: limitations: Limitations are addressed adequately in the Future Work section.
paper_summary: paper_summary: This paper considers the problem of DP mean estimation and the focus is on the high dimensional settings where the distribution is nearly low rank (or tr(Sigma)<<d), and the error metric is l_2. Prior work in this setting still requires sqrt(d) samples to achieve any non-trivial error which is sub-optimal. In the known covariances setting this paper achieves sample complexity n = tr(Sigma)/alpha^2 + tr(Sigma^1/2)/(alpha*eps) which can be significantly smaller than sqrt(d) in the high dimension setting. The algorithm filters out the outlier using the FriendlyCore algorithm [62] and leverages the propose-test-release framework. For the unknown covariance, one will need to first have a rough estimate of the covariance such that appropriate noise can be added to guarantee privacy. However dimension free estimation of the covariance is impossible, so the idea is to estimate the top-K coordinate with the largest variances, and simply adding small and isotropic gaussian noise to the remaining directions. Combining the error incurred in the top and bottom coordinate gives a d^(1/4) dependency in the dimensionality. On the lower bound side, they prove their known covariance result is optimal up to logarithmic factors. It is unclear what the optimal sample complexity for the unknown covariance should be.
strength_weakness: strength_weakness: The techniques for the known covariance setting have been developed previously.
questions: questions: I don't have question for the authors.
limitations: limitations: NA
paper_summary: paper_summary: The paper presents new differentially private algorithms for estimating the mean of high-dimensional data, addressing the inefficiencies of traditional methods that suffer from the "curse of dimensionality." The proposed estimators are tailored for anisotropic subgaussian distributions, where data signals are concentrated in fewer dimensions. These estimators achieve optimal sample complexity that is independent of dimensionality when the covariance is known and improve the sample complexity for unknown covariance cases from $d^{1/2}$ to $d^{1/4}$.
strength_weakness: strength_weakness: 1. I understand the space of the main text is limited but there is no conclusion.
2. There is no experimental design to verify their theoretical findings.
questions: questions: 1. The lower bound does not totally match the upper bound. Is it possible to improve the gap?
2. In Theorem 3.1., the range of $\epsilon$ is from 0 to 10. Actually, 10 is a weak privacy guarantee in DP in practice. Why do you take this value?
limitations: limitations: There is no experiment.
paper_summary: paper_summary: This paper tackles the problem of DP mean estimation for high-dimensional distributions exhibiting anisotropy, meaning the variances along different directions are highly non-equal. Prior works on this problem were plagued by a "curse of dimensionality", requiring sample complexities at least on the order of the square root of the ambient dimension d, even in cases where the non-private setting permits much lower sample sizes. The authors make two main contributions to address this limitation.

Firstly, for the case when the covariance matrix $\Sigma$ is known, they provide a DP algorithm achieving sample complexity independent of the dimension d. Instead, the sample complexity depends solely on $tr(\Sigma^{1/2})$, which can be substantially smaller than d when the distribution is highly anisotropic. The bound matches the optimal non-private sample complexity up to logarithmic factors. Secondly, the authors develop a DP algorithm for the unknown covariance setting that improves upon prior work by reducing the dimension dependence from $1/2$ to $1/4$, while also depending on properties of the diagonal entries of $\Sigma$.
strength_weakness: strength_weakness: - The results involving known covariance are straightforward. The benefits comes from (1) application of Tsfadia et al. and (2) rescaled noise adding, which is similar to Aumüller et al.
- There is still a $d^{1/4}$ left.
questions: questions: Major questions with potential score raising:
- Is it possible to establish a lower bound strictly higher than Theorem 1.2 for the unknown covariance case? This could help identify an intrinsic gap between the known and unknown covariance settings beyond logarithmic factors.
- The authors mention that for special cases of eigenvalue/variance decay, the unknown covariance bound can be improved to nearly match the known case up to log factors. What are the key bottlenecks or assumptions preventing a fully dimension-independent bound for unknown covariance? The remaining $d^{1/4}$ dependence seems to stem from coordinates with smaller variances - is this avoidable under some assumptions on the decay behavior?

Minor questions:
- In line 113, is the last term in the sample complexity bound for unknown covariance correct?
limitations: limitations: Limitations are well addressed.

Comments: title: Response to Rebuttal
comment: Thank you for responding to my comments.

To be more specific about the ordering of the paper, the FriendlyCore procedure; and the distinction between "pure" DP and (\epsilon,\delta)-DP, could be introduced earlier, before being referenced.

I am keeping my original "Accept" score.
Thanks for the clarification and I have updated my score. I still think a lower bound for unknown covariance (even if not tight) would be convincing.
Thanks to the authors for their clarifications!