Introduction
Statistical inference and machine learning algorithms are designed to extract population-level insights from data, but in doing so, they routinely reveal information about the individuals whose data they process. The risks of privacy violations are well documented, ranging from reconstruction [17 , 16 , 19 , 27 ] , membership-inference [22 , 36 , 7 , 18 SSSS17, YGFJ18] and the unintended memorization of training data [10 , 8 , 20 , 3 ] . Differential privacy (DP) [15 ] provides a rigorous framework for mitigating these risks by limiting the effect of any individual’s data on the distribution of an algorithm’s output, and has become a standard approach to privacy protection in statistics and machine learning.
At the same time, ensuring privacy can come at a substantial cost in statistical accuracy, especially in high-dimensional settings. This has motivated an extensive literature characterizing the tradeoffs between privacy, sample size, and accuracy, across a range of high-dimensional statistical and machine learning tasks. A central question is whether private algorithms can exploit structure in the underlying distribution to reduce this cost.
Gaussian mean estimation. A natural setting in which to study these tradeoffs is Gaussian mean estimation. Given independent samples from a Gaussian distribution with unknown mean μ ∈ R d \mu\in\mathbb{R}^{d} μ ∈ R d and covariance matrix Σ \Sigma Σ , the goal is to estimate μ \mu μ accurately in Euclidean distance. Mean estimation is a fundamental statistical task in its own right and serves as a building block for more complex procedures, including regression and optimization. Its simplicity also makes it an ideal setting in which we can isolate the interplay between privacy, dimensionality, and covariance structure.
Summary of our contributions. In this work, we compare the optimal error achievable for private Gaussian mean estimation when the covariance is unknown to the optimal error when the covariance is known (i.e., given as input to the algorithm). In the known covariance setting, recent work [13 ] shows that the optimal Euclidean error scales as
O ~ ( tr ( Σ ) n + tr ( Σ 1 / 2 ) log ( 1 / δ ) ε n ) , (1) \widetilde{\mathcal{O}}\left(\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}+\frac{\operatorname{tr}(\Sigma^{1/2})\sqrt{\log(1/\delta)}}{\varepsilon n}\right), \tag*{(1)} O ( n tr ( Σ ) + ε n tr ( Σ 1/2 ) log ( 1/ δ ) ) , (1)
where the first term is the statistical rate of Gaussian mean estimation, and the second term is the additional error due to privacy. Remarkably, the bound achieved by [13 ] is “dimension-free”—the error depends only on the geometry of the data, and is independent of the ambient dimension d d d . Our main contributions show that this dimension-free behavior cannot be recovered in the unknown covariance setting. Our first contribution shows that for a sample of size n n n , the optimal error in the unknown covariance setting can be larger by a factor of d / n \sqrt{d}/n d / n than the optimal error in the known covariance setting. Our second contribution considers the setting when the covariance is promised to be diagonal: we show that even under this additional promise, the optimal error in the unknown covariance setting can be larger by a factor of d / n 1.5 \sqrt{d}/n^{1.5} d / n 1.5 than the optimal error in the known covariance setting. Table 1 summarizes our main contributions.
Table 1. error u n k n o w n \operatorname{error}_{\mathrm{unknown}} error unknown and error k n o w n \operatorname{error}_{\mathrm{known}} error known , respectively, denote the Euclidean error in the unknown and known covariance settings. The known covariance bound, and the upper bound for unknown diagonal covariance are due to [13 ] . The upper bound for unknown general covariance is a folklore algorithm based on the framework from [TCKMS22] and presented in Section B. The lower bounds for error u n k n o w n \operatorname{error}_{\mathrm{unknown}} error unknown in both settings are Theorems 2.1 and 3.2 of this work.
Our bounds highlight two fundamental challenges for mean estimation with unknown covariance. In the promised diagonal setting, we show that every private mean estimation algorithm must, in some sense, “identify” many of the coordinates with the largest variances. And, in the general covariance setting, we show that every private mean estimation algorithm must learn the subspace spanned by the covariance.
In addition to our lower bounds for mean estimation in Euclidean distance, we show that in the more challenging setting of estimation in Mahalanobis error—where the error of the estimator in each direction is required to be proportional to the variance in that direction—private mean estimation with unknown covariance is impossible whenever n ≤ d − 2 n \le d - 2 n ≤ d − 2 . This is in stark contrast to the known covariance setting where the optimal Mahalanobis error is finite at essentially all sample sizes.
Our results
All of our lower bounds apply to the approximate DP setting defined below.
Definition 1.1 (Differential Privacy [15 ] ). A randomized algorithm A : X ∗ → W \mathcal{A}:\mathcal{X}^* \to\mathcal{W} A : X ∗ → W is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private, if, for all neighboring datasets X , X ′ X,X' X , X ′ , i.e. datasets that differ on a single entry, and all measurable subsets W ⊂ W W \subset\mathcal{W} W ⊂ W we have
Pr [ A ( X ) ∈ W ] ≤ e ε Pr [ A ( X ′ ) ∈ W ] + δ . \Pr[\mathcal{A}(X) \in W] \le e^\varepsilon\Pr[\mathcal{A}(X') \in W] + \delta. Pr [ A ( X ) ∈ W ] ≤ e ε Pr [ A ( X ′ ) ∈ W ] + δ .
In order to facilitate comparison between the error in the known and unknown covariance settings, and to present a scale-free “cost” of not knowing the covariance, we define the known and unknown covariance Bayes risk.
Definition 1.2 (Bayes risk). Let A ε , δ \mathcal{A}_{\varepsilon,\delta} A ε , δ denote the set of ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithms, and let P \mathcal{P} P be a prior distribution over μ ∈ R d \mu\in\mathbb{R}^d μ ∈ R d and positive semi-definite Σ ∈ R d × d \Sigma\in\mathbb{R}^{d\times d} Σ ∈ R d × d . The unknown-covariance Bayes risk with respect to the prior P \mathcal{P} P is defined as:
R ε , δ ( P , n ) = inf { α ≥ 0 : ∃ A ∈ A ε , δ s.t. Pr ( μ , Σ ) ∼ P X ∼ N ( μ , Σ ) ⊗ n [ ∥ A ( X ) − μ ∥ 2 ≤ α ] ≥ 3 4 } . \mathfrak{R}_{\varepsilon,\delta}(\mathcal{P},n) = \inf\left\{\alpha\ge0 : \exists\mathcal{A} \in\mathcal{A}_{\varepsilon,\delta}\ \text{s.t.}\ \Pr_{\substack{(\mu,\Sigma)\sim\mathcal{P}\\ X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}}\left[\left\|\mathcal{A}(X)-\mu\right\|_2 \le\alpha\right] \ge\frac{3}{4}\right\}. R ε , δ ( P , n ) = inf ⎩ ⎨ ⎧ α ≥ 0 : ∃ A ∈ A ε , δ s.t. ( μ , Σ ) ∼ P X ∼ N ( μ , Σ ) ⊗ n Pr [ ∥ A ( X ) − μ ∥ 2 ≤ α ] ≥ 4 3 ⎭ ⎬ ⎫ . We also define the known-covariance Bayes risk (i.e., the risk when the algorithm is given the
nchumu
covariance as input) with respect to the prior P \mathcal{P} P by:
R ε , δ k n o w n ( P , n ) = inf { α ≥ 0 : ∃ A ∈ A ε , δ s.t. Pr ( μ , Σ ) ∼ P X ∼ N ( μ , Σ ) ⊗ n [ ∥ A ( X ; Σ ) − μ ∥ 2 ≤ α ] ≥ 3 4 } . \mathcal{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P},n)=\inf\left\{\alpha\ge0:\exists\,\mathcal{A}\in\mathcal{A}_{\varepsilon,\delta}\ \text{s.t.}\ \underset{\substack{(\mu,\Sigma)\sim\mathcal{P}\\X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}}{\Pr}\left[\lVert\mathcal{A}(X;\Sigma)-\mu\rVert_2\le\alpha\right]\ge\frac{3}{4}\right\}. R ε , δ known ( P , n ) = inf ⎩ ⎨ ⎧ α ≥ 0 : ∃ A ∈ A ε , δ s.t. ( μ , Σ ) ∼ P X ∼ N ( μ , Σ ) ⊗ n Pr [ ∥ A ( X ; Σ ) − μ ∥ 2 ≤ α ] ≥ 4 3 ⎭ ⎬ ⎫ .
Our results demonstrate the impossibility of private mean estimation with both dimension-free error and dimension-free sample complexity in two settings. Each setting highlights a distinct aspect of private mean estimation that requires many samples: In the first setting, the variance in each basis direction is fixed, and the difficulty stems from the fact that the basis directions are chosen uniformly at random, while in the second setting, the basis directions are fixed, and the difficulty stems from the fact that the variance in each direction is chosen from a suitably pathological distribution.
General covariance
In this setting, we consider mean estimation when the mean μ \mu μ and the covariance Σ \Sigma Σ are sampled from the prior P s u b \mathcal{P}_{\mathrm{sub}} P sub defined by
( μ , Σ ) ∼ P s u b ( d , k ) ⟺ { μ ∼ N ( 0 , d 2 I d ) Σ = D D T where D ∼ H d , k . (\mu,\Sigma)\sim\mathcal{P}_{\mathrm{sub}}(d,k)\Longleftrightarrow
\begin{cases}
\mu\sim\mathcal{N}(0,d^2I_d)\\
\Sigma=DD^{\mathsf{T}}\ \text{where }D\sim\mathcal{H}_{d,k}.
\end{cases} ( μ , Σ ) ∼ P sub ( d , k ) ⟺ { μ ∼ N ( 0 , d 2 I d ) Σ = D D T where D ∼ H d , k .
where H d , k \mathcal{H}_{d,k} H d , k is the uniform distribution over d × k d\times k d × k matrices with orthonormal columns. Note that the effective dimension of every matrix in the support of the prior is k k k , and that the resulting distributions N ( μ , Σ ) \mathcal{N}(\mu,\Sigma) N ( μ , Σ ) are highly structured—the data are isotropic in a k k k -dimensional subspace. Indeed, if Σ \Sigma Σ is known, then the problem reduces to Gaussian mean estimation with covariance I k I_k I k . Using the bound in (1) for the error in the known covariance setting yields
R ε , δ k n o w n ( P s u b , n ) = O ~ ε , δ ( k n + k n ) . (2) \mathcal{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{k}{n}}+\frac{k}{n}\right). \tag*{(2)} R ε , δ known ( P sub , n ) = O ε , δ ( n k + n k ) . (2)
On the other hand, when Σ \Sigma Σ is unknown, a folklore algorithm based on the FriendlyCore framework of [TCKMS22] (presented in Section B for completeness) bounds the unknown covariance risk by O ~ ε , δ ( tr ( Σ ) n + d tr ( Σ ) n ) \widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}+\frac{\sqrt{d\operatorname{tr}(\Sigma)}}{n}\right) O ε , δ ( n tr ( Σ ) + n d tr ( Σ ) ) , which yields
R ε , δ ( P s u b , n ) = O ~ ε , δ ( k n + d k n ) . (3) \mathcal{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{k}{n}}+\frac{\sqrt{dk}}{n}\right). \tag*{(3)} R ε , δ ( P sub , n ) = O ε , δ ( n k + n d k ) . (3)
Our main result shows that when n ≪ k n\ll k n ≪ k the folklore estimator is optimal—in particular, a private algorithm cannot take advantage of the low dimensional structure until it has seen almost every direction in the span of Σ \Sigma Σ .
Theorem 2.1. For all n , k , d ∈ N n,k,d\in\mathbb{N} n , k , d ∈ N with k ≲ d k\lesssim d k ≲ d and n log n ≲ k n\log n\lesssim k n log n ≲ k , if ε ≤ 1 \varepsilon\le1 ε ≤ 1 and δ ≲ 1 / n \delta\lesssim1/n δ ≲ 1/ n then every ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithm M \mathcal{M} M satisfies
Pr ( μ , Σ ) ∼ P s u b X ∼ N ( μ , Σ ) ⊗ n [ ∥ M ( X ) − μ ∥ 2 ≥ d k n ] ≥ 1 4 . \underset{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{sub}}\\X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}}{\Pr}\left[\lVert\mathcal{M}(X)-\mu\rVert_2\ge\frac{\sqrt{dk}}{n}\right]\ge\frac{1}{4}. ( μ , Σ ) ∼ P sub X ∼ N ( μ , Σ ) ⊗ n Pr [ ∥ M ( X ) − μ ∥ 2 ≥ n d k ] ≥ 4 1 . In particular, R ε , δ ( P s u b , n ) ≥ d k n \mathcal{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)\ge\frac{\sqrt{dk}}{n} R ε , δ ( P sub , n ) ≥ n d k .
Theorem 2.1 is tight in two respects: First, it matches the upper bound in (3) for the setting where n log n < k n \log n < k n log n < k , and second, once n ≳ k + ε − 1 n \gtrsim k + \varepsilon^{-1} n ≳ k + ε − 1 , one can use the results of [SS21] to learn Σ \Sigma Σ exactly and recover the bound in (2) . Additionally, for the setting of n log n < k n \log n < k n log n < k , comparing the bound in Theorem 2.1 and the bound in (2) yields the following scale-free bound on the cost of unknown covariance in private mean estimation,
R ε , δ ( P s u b , n ) = Ω ~ ε , δ ( 1 + d k ) ⋅ R ε , δ k n o w n ( P s u b , n ) . \mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{\Omega}_{\varepsilon,\delta}\left(1+\sqrt{\frac{d}{k}}\right)\cdot\mathfrak{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n). R ε , δ ( P sub , n ) = Ω ε , δ ( 1 + k d ) ⋅ R ε , δ known ( P sub , n ) .
Setting k ≈ n log n k\approx n\log n k ≈ n log n recovers the blowup for general covariance in Table 1 .
Diagonal covariance
While the previous setting leverages the randomness in the basis vectors, in the second setting, we instead fix the basis vectors (i.e., we consider diagonal covariance), and leverage the randomness in the variances themselves. To do so, we consider the prior P d i a g \mathcal{P}_{\mathrm{diag}} P diag defined by
( μ , Σ ) ∼ P d i a g ( d ) ⟺ { μ ∼ N ( 0 , d 2 I d ) Σ = Diag ( ( σ i 2 ) i ∈ [ d ] ) , where ( σ i 2 ) i ∈ [ d ] ∼ inv χ 2 ( 1 , 1 ) ⊗ d (\mu,\Sigma)\sim\mathcal{P}_{\mathrm{diag}}(d)\Longleftrightarrow
\begin{cases}
\mu\sim\mathcal{N}(0,d^{2}I_{d})\\
\Sigma=\operatorname{Diag}((\sigma_{i}^{2})_{i\in[d]}),\ \text{where }(\sigma_{i}^{2})_{i\in[d]}\sim\operatorname{inv}\chi^{2}(1,1)^{\otimes d}
\end{cases} ( μ , Σ ) ∼ P diag ( d ) ⟺ { μ ∼ N ( 0 , d 2 I d ) Σ = Diag (( σ i 2 ) i ∈ [ d ] ) , where ( σ i 2 ) i ∈ [ d ] ∼ inv χ 2 ( 1 , 1 ) ⊗ d
where inv χ 2 ( ν , τ 2 ) \operatorname{inv}\chi^{2}(\nu,\tau^{2}) inv χ 2 ( ν , τ 2 ) denotes the scaled-inverse chi-squared distribution with ν \nu ν degrees of freedom and scale τ \tau τ (see Theorem 3.1). One can show that under the prior P d i a g \mathcal{P}_{\mathrm{diag}} P diag the covariance Σ \Sigma Σ satisfies tr ( Σ ) ≈ d 2 \operatorname{tr}(\Sigma)\approx d^{2} tr ( Σ ) ≈ d 2 and tr ( Σ 1 / 2 ) ≈ d log d \operatorname{tr}(\Sigma^{1/2})\approx d\log d tr ( Σ 1/2 ) ≈ d log d with high constant probability (this can be formalized using standard bounds for sums of heavy tailed random variables, see Theorem A.3 ).
For the unknown diagonal covariance setting, an algorithm from [13 ] gives the general bound O ~ ε , δ ( tr ( Σ ) n + ( 1 + d n ) tr ( Σ 1 / 2 ) n ) \widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}+\left(1+\frac{\sqrt{d}}{n}\right)\frac{\operatorname{tr}(\Sigma^{1/2})}{n}\right) O ε , δ ( n tr ( Σ ) + ( 1 + n d ) n tr ( Σ 1/2 ) ) , which combined with the bound (1) for private estimation with known covariance, yields the known and unknown covariance risk bounds for P d i a g \mathcal{P}_{\mathrm{diag}} P diag :
R ε , δ k n o w n ( P d i a g , n ) = O ~ ε , δ ( d n ) and R ε , δ ( P d i a g , n ) = O ~ ε , δ ( d n + d 3 / 2 n 2 ) . (4) \mathfrak{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n)=\widetilde{O}_{\varepsilon,\delta}\left(\frac{d}{\sqrt{n}}\right)
\qquad\text{and}\qquad
\mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n)=\widetilde{O}_{\varepsilon,\delta}\left(\frac{d}{\sqrt{n}}+\frac{d^{3/2}}{n^{2}}\right). \tag*{(4)} R ε , δ known ( P diag , n ) = O ε , δ ( n d ) and R ε , δ ( P diag , n ) = O ε , δ ( n d + n 2 d 3/2 ) . (4)
Our main result shows a tight lower bound on the unknown-covariance risk for the prior P d i a g \mathcal{P}_{\mathrm{diag}} P diag .
Theorem 3.2. For all n , d ∈ N n,d\in\mathbb{N} n , d ∈ N with n log n ≲ d n\log n\lesssim\sqrt{d} n log n ≲ d , if ε ≤ 1 \varepsilon\leq1 ε ≤ 1 and δ ≲ 1 / n \delta\lesssim1/n δ ≲ 1/ n then every ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithm M \mathcal{M} M satisfies
\underset{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{diag}}\\X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}{\Pr}\left[\lVert\mathcal{M}(X)-\mu\rVert_{2}\geq\frac{d^{3/2}}{n^{2}\log d}\right]\geq\frac{1}{4}.}
In particular, R ε , δ ( P d i a g , n ) ≥ d 3 / 2 n 2 \mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n)\geq\frac{d^{3/2}}{n^{2}} R ε , δ ( P diag , n ) ≥ n 2 d 3/2 .
As a corollary of Theorem 3.2 and (4) , we obtain the scale-free lower bound on the cost of unknown diagonal covariance in private mean estimation
R ε , δ ( P d i a g , n ) = Ω ~ ε , δ ( 1 + d n 3 / 2 ) ⋅ R ε , δ k n o w n ( P d i a g , n ) . \mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n)=\widetilde{\Omega}_{\varepsilon,\delta}\left(1+\frac{\sqrt{d}}{n^{3/2}}\right)\cdot\mathfrak{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n). R ε , δ ( P diag , n ) = Ω ε , δ ( 1 + n 3/2 d ) ⋅ R ε , δ known ( P diag , n ) .
While the blowup is Θ ( 1 ) \Theta(1) Θ ( 1 ) once n ≥ d 1 / 3 n\geq d^{1/3} n ≥ d 1/3 , we note that the bound in Theorem 3.2 nevertheless establishes the necessity of the additive d 3 / 2 / n 2 d^{3/2}/n^{2} d 3/2 / n 2 term for the full regime where n log n ≲ d n\log n\lesssim\sqrt{d} n log n ≲ d .
Table 2 summarizes our lower bounds for estimation with Euclidean error and includes the matching upper bounds from prior work.
Table 2. Euclidean upper and lower bounds for the two hard covariance priors. We assume ε ≤ 1 \varepsilon\le1 ε ≤ 1 and δ ≤ 1 / n \delta\le1/n δ ≤ 1/ n . All bounds hold with constant probability for the corresponding covariance priors.
Estimation in Mahalanobis norm. In addition to studying private mean estimation with error in ℓ 2 \ell_2 ℓ 2 norm, we show strong impossibility results for private mean estimation with error measured in Mahalanobis norm using n ≪ d n \ll d n ≪ d samples. For a positive semi-definite matrix Σ \Sigma Σ and a vector y y y , we let d Σ ( y ) d_{\Sigma}(y) d Σ ( y ) denote the Mahalanobis norm of y y y (defined in § 4 ). Our main result says that for n ≤ d − 2 n \le d-2 n ≤ d − 2 , every ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithm achieves finite Mahalanobis error with probability at most n δ n\delta n δ .
Theorem 4.1. For all d ∈ N d \in\mathbb{N} d ∈ N there exists a prior P r e l P_{\mathrm{rel}} P rel over instances ( μ , Σ ) (\mu,\Sigma) ( μ , Σ ) such that if n ≤ d − 2 n \le d-2 n ≤ d − 2 , then for all ε , δ > 0 \varepsilon,\delta> 0 ε , δ > 0 every ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithm M \mathcal{M} M satisfies
\mathop{\Pr}_{(\mu,\Sigma)\sim P_{\mathrm{rel}}}\limits_{X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}\left[d_{\Sigma}(\mathcal{M}(X)-\mu)<\infty\right]\le n\delta.
For δ < 1 n \delta< \frac{1}{n} δ < n 1 , Theorem 4.1 shows that private mean estimation with finite Mahalanobis error is essentially impossible with fewer than d d d samples. This is in stark contrast to the known covariance setting where finite Mahalanobis error can be achieved for essentially any n n n . For δ ≥ 1 / n \delta\ge1/n δ ≥ 1/ n a “name-and-shame” algorithm that publishes ⌊ δ n ⌋ \lfloor\delta n\rfloor ⌊ δ n ⌋ records selected randomly from the dataset achieves finite Mahalanobis error, but fails most intuitive concepts of privacy.
Our techniques
In contrast to existing lower bounds for private Gaussian mean estimation, which proceed by sampling μ \mu μ from a suitable prior and sampling the data from N ( μ , I d ) \mathcal{N}(\mu,I_d) N ( μ , I d ) , to prove lower bounds in our unknown covariance setting we must design a prior over both μ \mu μ and Σ \Sigma Σ . Intuitively, in order to show a lower bound that exceeds the lower bound in the known covariance setting, it suffices to show that an estimate of μ \mu μ in the unknown covariance setting also contains some non-trivial information about Σ \Sigma Σ , and that learning this information privately requires many samples. Indeed, a key step in our proofs is a reduction from a task T ( Σ ) T(\Sigma) T ( Σ ) that only involves Σ \Sigma Σ —that is, we leverage the randomness in μ \mu μ to show that a mechanism which accurately estimates μ \mu μ can be used to construct an algorithm which solves the task T ( Σ ) T(\Sigma) T ( Σ ) . We then prove a lower bound for privately solving the task T ( Σ ) T(\Sigma) T ( Σ ) , which by the reduction, implies a lower bound for privately estimating μ \mu μ .
General covariance. To prove our lower bound for general covariance, we define the prior over Σ \Sigma Σ as follows: sample a uniformly random orthonormal d × k d \times k d × k matrix D D D and let Σ = D D T \Sigma= DD^{\mathsf{T}} Σ = D D T —that is, Σ \Sigma Σ is a projection matrix onto a uniformly random k k k -dimensional subspace. The key idea used to prove the bound is that for n ≤ k / 2 n \le k/2 n ≤ k /2 , conditioned on μ \mu μ and the sample X = x 1 , … , x n ∼ N ( μ , Σ ) X = x_1,\ldots,x_n \sim\mathcal{N}(\mu,\Sigma) X = x 1 , … , x n ∼ N ( μ , Σ ) , the remaining k − n k-n k − n unseen directions in Span ( Σ ) \operatorname{Span}(\Sigma) Span ( Σ ) are uniformly random in the remaining d − n d-n d − n dimensional space. Intuitively, a private mechanism must add enough noise to hide the contribution of a single sample, and thus it must add noise in every direction in Span ( Σ ) \operatorname{Span}(\Sigma) Span ( Σ ) ; however, since conditioned on the sample, the remaining directions in Span ( Σ ) \operatorname{Span}(\Sigma) Span ( Σ ) are uniformly random in the ambient space, a private algorithm must add noise in every direction, which results in dimension-dependent error.
We formalize this intuitive argument by showing that every private and accurate mean estimation algorithm can be used to privately generate a sample that simultaneously “correlates” with the covariance Σ \Sigma Σ and has small ℓ 2 \ell_2 ℓ 2 norm. We call this sampling problem ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampling, where λ \lambda λ controls the “correlation” between y y y and Σ \Sigma Σ , namely E [ y T Σ y ] ≥ λ 2 \mathbb{E}[y^{\mathsf{T}}\Sigma y] \ge\lambda^2 E [ y T Σ y ] ≥ λ 2 , and α \alpha α controls the norm, that is ∥ y ∥ 2 ≤ α \lVert y\rVert_2 \le\alpha ∥ y ∥ 2 ≤ α . Essentially, our reduction shows that every private mean estimation algorithm with error α \alpha α and sample complexity n n n can be used to construct a private ( k / n , α ) (k/n,\alpha) ( k / n , α ) -sampler with sample complexity n n n . To complete the proof, we show that every private ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler with sample complexity n ≤ k / 2 n \le k/2 n ≤ k /2 requires α ≥ λ d / k \alpha\ge\lambda\sqrt{d/k} α ≥ λ d / k . Plugging in the parameters from the reduction yields that every private mean estimation algorithm with sample complexity n ≤ k / 2 n \le k/2 n ≤ k /2 has error
α ≥ d k n . \alpha\ge\frac{\sqrt{dk}}{n}. α ≥ n d k .
Sampler lower bound. To prove a lower bound for private sampling, we design a membership inference attack which uses a test that directly measures the correlation between the target point and the sample output by the mechanism—that is, for test point z ∈ R d z \in\mathbb{R}^d z ∈ R d , sample y ∈ R d y \in\mathbb{R}^d y ∈ R d , and covariance Σ \Sigma Σ , we define the test
T y , Σ ( z ) = ⟨ z , y ⟩ 2 y T Σ y . \mathcal{T}_{y,\Sigma}(z) = \frac{\langle z,y\rangle^2}{y^{\mathsf{T}}\Sigma y}. T y , Σ ( z ) = y T Σ y ⟨ z , y ⟩ 2 .
Intuitively, if a sampler has seen less than k / 2 k/2 k /2 samples, then in order to make y T Σ y y^{\mathsf{T}}\Sigma y y T Σ y large, it must either sample from a distribution with large variance in all directions, or it must make y y y large in the directions it has seen, which are highly dependent on the sample X X X . Since the output of a sampler must satisfy ∥ y ∥ 2 ≤ α \lVert y\rVert_2 \le\alpha ∥ y ∥ 2 ≤ α , the former option is impossible, and thus, we expect the output y y y to be highly dependent on the sample X X X . Somewhat more formally, suppose that we sample Σ \Sigma Σ as follows: first sample the data x 1 , … , x n x_1,\ldots,x_n x 1 , … , x n and let P X P_X P X denote the projector on Span ( X ) \operatorname{Span}(X) Span ( X ) . Second, since P X P_X P X defines an n n n dimensional subspace, we can sample Σ \Sigma Σ by sampling the remaining k − n k-n k − n directions uniformly at random from its orthogonal complement. We can then decompose the correlation between y y y and Σ \Sigma Σ into the correlation between y y y and P X P_X P X , and the correlation between y y y and a uniformly random k − n k-n k − n dimensional projection matrix:
y T Σ y = y T P X y + y T ( Σ − P X ) y . y^{\mathsf{T}}\Sigma y = y^{\mathsf{T}}P_Xy + y^{\mathsf{T}}(\Sigma-P_X)y. y T Σ y = y T P X y + y T ( Σ − P X ) y .
where ( Σ − P X ) (\Sigma-P_X) ( Σ − P X ) is a uniformly random projection from a d − n d-n d − n dimensional space to a k − n k-n k − n dimensional space. Thus using the norm bound on y y y , we have that y T ( Σ − P X ) y y^{\mathsf{T}}(\Sigma-P_X)y y T ( Σ − P X ) y is typically at most α 2 k / d \alpha^2 k/d α 2 k / d . Since the left hand side ( y T Σ y ) (y^{\mathsf{T}}\Sigma y) ( y T Σ y ) is in expectation at least λ 2 \lambda^2 λ 2 , we see that y T P X y ≥ λ 2 / 2 y^{\mathsf{T}}P_Xy \ge\lambda^2/2 y T P X y ≥ λ 2 /2 whenever α ≤ λ d / 2 k \alpha\le\lambda\sqrt{d/2k} α ≤ λ d /2 k . Thus, any ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler with α ≤ λ d / 2 k \alpha\le\lambda\sqrt{d/2k} α ≤ λ d /2 k must exhibit significant correlation with the data X X X . Leveraging this correlation allows us to show that the attack T \mathcal{T} T can distinguish a member in X X X from a fresh sample from the population, and thus, such a ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler cannot be private.
Diagonal covariance. A first step in proving the lower bound in the diagonal covariance setting is constructing a prior over Σ \Sigma Σ (or family of covariance matrices) for which we expect private mean estimation with unknown covariance to be much harder than private estimation with known covariance. Our starting point is the algorithm of [13 ] which proceeds as follows: First learn the coordinates with k ≈ n 2 k \approx n^2 k ≈ n 2 largest variances, and estimate the mean in those coordinates using the known covariance algorithm; and second, estimate the mean in the remaining d − k d-k d − k coordinates by adding spherical noise proportional to the trace. At a high level, one can show that the relative error of this algorithm compared to the optimal known covariance algorithm is largest when the diagonal entries σ i 2 \sigma_i^2 σ i 2 decay proportional to i − 2 i^{-2} i − 2 . This leads us to sample each σ i 2 \sigma_i^2 σ i 2 independently from the scaled-inverse-chi-squared distribution inv χ 2 ( 1 , 1 ) \operatorname{inv}\chi^2(1,1) inv χ 2 ( 1 , 1 ) . This distribution has a tail of order t − 1 / 2 t^{-1/2} t − 1/2 , so its i i i -th largest draw is typically on the scale d 2 i − 2 d^2i^{-2} d 2 i − 2 .
Next, to prove our lower bound for diagonal covariance, we show that every private and accurate mean estimation algorithm can be used to privately select the coordinates with the k k k largest variances—that is, we reduce from a “top-k k k ” variance selection problem that we call ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection. In ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection we are given samples X = x 1 , … , x n ∼ N ( 0 , Σ ) ⊗ n X=x_1,\ldots,x_n\sim\mathcal{N}(0,\Sigma)^{\otimes n} X = x 1 , … , x n ∼ N ( 0 , Σ ) ⊗ n where Σ = Diag ( σ 1 2 , … , σ d 2 ) ∼ inv χ 2 ( 1 , 1 ) ⊗ d \Sigma=\operatorname{Diag}(\sigma_1^2,\ldots,\sigma_d^2)\sim\operatorname{inv}\chi^2(1,1)^{\otimes d} Σ = Diag ( σ 1 2 , … , σ d 2 ) ∼ inv χ 2 ( 1 , 1 ) ⊗ d , and the goal is to output a list of at most ℓ \ell ℓ coordinates that contains at least 1 / 4 1/4 1/4 of the coordinates with the k k k -largest variances. Formally, our reduction shows that every private mean estimation algorithm that achieves error α \alpha α can be used to privately select the coordinates with the k k k largest variances, while selecting at most ℓ ≈ α 2 k n 2 d 2 \ell\approx\frac{\alpha^2kn^2}{d^2} ℓ ≈ d 2 α 2 k n 2 coordinates overall. We complete the proof by showing a lower bound for private ( k , ℓ ) (k,\ell) ( k , ℓ ) selection which states that any private ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection algorithm with n ≤ k n\le\sqrt{k} n ≤ k samples requires ℓ ≥ d / log d \ell\ge d/\log d ℓ ≥ d / log d . Setting k ≈ n 2 k\approx n^2 k ≈ n 2 and combining the selection lower bound with the setting of ℓ \ell ℓ in the reduction, we obtain that every private mean estimation algorithm has error
α ≥ d 3 / 2 n k ≈ d 3 / 2 n 2 . \alpha\ge\frac{d^{3/2}}{n\sqrt{k}} \approx\frac{d^{3/2}}{n^2}. α ≥ n k d 3/2 ≈ n 2 d 3/2 .
Selection lower bound. To show a lower bound for private selection we construct a membership inference attack against any ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection algorithm that uses n ≤ k n\le\sqrt{k} n ≤ k samples and at the same time selects at most ℓ ≤ d / log d \ell\le d/\log d ℓ ≤ d / log d coordinates. One natural candidate for such an attack, inspired by [SU17] is the following test: For test point z ∈ R d z\in\mathbb{R}^d z ∈ R d , covariance Σ \Sigma Σ , and selection vector s ∈ { 0 , 1 } d s\in\{0,1\}^d s ∈ { 0 , 1 } d , define
T n a i v e ( z , s , Σ ) : = ∑ j ∈ [ d ] ( z j 2 σ j 2 − 1 ) s j . \mathcal{T}_{\mathrm{naive}}(z,s,\Sigma):=\sum_{j\in[d]}\left(\frac{z_j^2}{\sigma_j^2}-1\right)s_j. T naive ( z , s , Σ ) := j ∈ [ d ] ∑ ( σ j 2 z j 2 − 1 ) s j .
One might hope that when the test point x i x_i x i is in the dataset the expectation E [ T n a i v e ( x i ) ] \mathbb{E}[\mathcal{T}_{\mathrm{naive}}(x_i)] E [ T naive ( x i )] will be large. Unfortunately, this is not the case in general: Using properties of the inv χ 2 \operatorname{inv}\chi^2 inv χ 2 prior on Σ \Sigma Σ , one can show that conditional on X X X , the expectation of each term in T n a i v e \mathcal{T}_{\mathrm{naive}} T naive is q j − 1 1 + n q j \frac{q_j-1}{1+nq_j} 1 + n q j q j − 1 , where q j q_j q j denotes the empirical variance in coordinate j j j . Thus, when q j ≫ 1 q_j\gg1 q j ≫ 1 , the contribution of term j j j is about 1 / n 1/n 1/ n , but when q j ∈ ( 0 , 1 ) q_j\in(0,1) q j ∈ ( 0 , 1 ) the contribution is negative and is typically on the order of − 1 / n -1/n − 1/ n . It follows that while the top k k k -terms may contribute k / n k/n k / n to the test, a careful selection algorithm may select many of the coordinates with the smallest variances, and these may contribute up to − ℓ / n -\ell/n − ℓ / n to the test. Hence, this approach can only hope to show that ℓ \ell ℓ must be at least k k k , which is too weak for our purposes (we aim to show that ℓ \ell ℓ must be at least d / log d d/\log d d / log d even when k ≈ n 2 k\approx n^2 k ≈ n 2 ). The problematic behavior in the test T n a i v e \mathcal{T}_{\mathrm{naive}} T naive occurs because the coordinates with the top-k k k variances don’t contribute enough to the sum to overcome the many small negative contributions from the coordinates where σ j 2 ∈ ( 0 , 1 ) \sigma_j^2 \in(0,1) σ j 2 ∈ ( 0 , 1 ) . Thus, a natural way to circumvent this barrier is to scale each term by σ j \sigma_j σ j . Because the scaling is asymmetric, the result is that the large terms become much larger, while the impact on the small terms is negligible. This leads us to the following more effective test
T s , Σ ( z ) : = ∑ j ∈ [ d ] ( z j 2 σ j 2 − 1 ) min { σ j , d k } s j , \mathcal{T}_{s,\Sigma}(z) := \sum_{j \in[d]} \left(\frac{z_j^2}{\sigma_j^2} - 1\right) \min\left\{\sigma_j, \frac{d}{k}\right\} s_j, T s , Σ ( z ) := j ∈ [ d ] ∑ ( σ j 2 z j 2 − 1 ) min { σ j , k d } s j ,
where the min is required for technical reasons (the σ j 2 \sigma_j^2 σ j 2 ’s are heavy tailed, and thus clipping helps to bound the variance). Using properties of the inv χ 2 ( 1 , 1 ) \operatorname{inv}\chi^2(1,1) inv χ 2 ( 1 , 1 ) distribution, one can show that the top-k k k variances are at least ( d / k ) 2 (d/k)^2 ( d / k ) 2 , and thus, the contribution of the corresponding terms in T \mathcal{T} T increases by a factor of d / k d/k d / k when compared to T n a i v e \mathcal{T}_{\mathrm{naive}} T naive . Since the negative terms are essentially unaffected (they have small σ j \sigma_j σ j ), we only require ℓ ≤ d / log d \ell\le d/\log d ℓ ≤ d / log d to guarantee that E [ T ( x i ) ] \mathbb{E}[\mathcal{T}(x_i)] E [ T ( x i )] is large.
Related work
Differentially private Gaussian mean estimation. Differentially private mean estimation has been studied extensively, including asymptotically efficient estimators [35 ] and estimators for univariate Gaussians with unknown parameters [28 ] . A series of works established nearly optimal guarantees for Gaussian mean estimation with known covariance in Mahalanobis error metric [6 , 24 , 1 , 29 ] . Brown et al. [4 ] developed optimal Gaussian mean estimators in Mahalanobis error metric with unknown covariance, followed by polynomial time algorithms matching these guarantees [5 , 23 ] . As defined above, this loss is affine invariant and implies
∥ μ ~ − μ ∥ 2 ≤ d Σ ( μ ~ − μ ) ∥ Σ ∥ o p . \lVert\widetilde{\mu} - \mu\rVert_2 \le d_{\Sigma}(\widetilde{\mu} - \mu)\sqrt{\lVert\Sigma\rVert_{\mathrm{op}}}. ∥ μ − μ ∥ 2 ≤ d Σ ( μ − μ ) ∥ Σ ∥ op .
However, it normalizes errors by the variance in each direction, including directions with very small variance, and therefore does not capture the full benefits of anisotropy under Euclidean error. Moreover, the sample size required by the methods in [4 ] is at least n ≳ d / ε n \gtrsim d/\varepsilon n ≳ d / ε . Our complementary results show that a sample size of n ≳ d n \gtrsim d n ≳ d is required to achieve any finite error in Mahalanobis distance, showing that this requirement is almost tight.
For Euclidean error, the FriendlyCore framework [TCKMS22] provides a filtering-based approach to private aggregation and underlies the general-purpose Gaussian mean estimator used as a benchmark in this work. Aiming to exploit covariance structure, Aumüller et al. [2 ] developed variance-aware private mean estimators for approximately-known diagonal covariance matrices, which achieve optimal error as long as n ≳ d / ε n \gtrsim\sqrt{d}/\varepsilon n ≳ d / ε . Dagan et al. [13 ] established optimal dimension-free guarantees up to logarithmic factors when the covariance is known, and improved dimension dependence when it is diagonal and unknown. Under pure differential privacy, Chen et al. [9 ] also obtain covariance-dependent Euclidean guarantees for known-covariance Gaussian mean estimation, in a regime requiring at least d / ε d/\varepsilon d / ε samples. Outside of differential privacy, [31 ] and [14 ] established optimal, dimension-free robust estimators for the mean of anisotropic Gaussian distributions under general norms.
Privately learning covariance structure. Privately learning the covariance or a low-dimensional subspace can enable subsequent mean estimation with fewer samples or better accuracy, but these intermediate tasks can themselves require a lot of data. Lower bounds for private Gaussian covariance estimation were established by [25 ] and strengthened by [32 , 33 ] . These results show that learning the covariance of a Gaussian distribution with constant spectral accuracy, which would suffice for subsequently using mean estimation algorithms with known covariance, requires n ≳ d 3 / 2 n \gtrsim d^{3/2} n ≳ d 3/2 samples.
Singhal and Steinke [SS21] give dimension-independent sample bounds for exact recovery of a subspace under a general position assumption, as well as approximate recovery under a sufficiently large eigenvalue gap. Tsfadia [Tsf24] studies subspace estimation in a distribution-free setting and further quantifies the role of eigenvalue gaps.
Related barriers arise in private sparse covariance estimation and PCA, where row-column sparsity of the covariance matrix alone need not eliminate the polynomial dependence of the sample size on the ambient dimension [26 ] . Our lower bounds establish the cost of unknown covariance directly for mean estimation, without requiring the estimator to recover the covariance or its principal directions.
Fingerprinting lower bounds. Our lower bounds build on the intuitive connection between accurate estimation and membership inference. Bun, Ullman, and Vadhan [7 ] introduced fingerprinting codes as a tool for information-theoretic lower bounds in differential privacy, and Dwork et al. [18 ] developed robust tracing attacks for binary and Gaussian data. These techniques were further developed for Gaussian estimation by Kamath et al. [24 ] , for exponential families by Kamath, Mouzakis, and Singhal [25 ] , and for general parametric models through score attacks by Cai, Wang, and Zhang [12 ] . Peter, Tsfadia, and Ullman [34 ] develop padding-and-permuting fingerprinting codes that vary smoothly with the required accuracy.
Our tracing arguments exploit priors over the covariance whose conditional distributions given the sample can be analyzed explicitly. The additional challenge in our setting is to exploit uncertainty about the covariance: we design joint priors over the mean and covariance, reduce mean estimation to covariance-dependent sampling or selection tasks, and construct tracing attacks for these tasks instead.
Private selection. Our diagonal-covariance lower bound is particularly related to the top-k k k selection problem of Steinke and Ullman [SU17], who extended fingerprinting arguments to selecting coordinates with large means. Related questions arise in private sparse mean estimation [11 ] . Our auxiliary task, called ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection, instead asks for a list of length ℓ \ell ℓ containing a constant fraction of the coordinates with the largest variances, and allows the list to contain a lot more than k k k coordinates. A direct adaptation of the mean-selection tracing argument is not sufficient for our purposes: contributions from selected low-variance coordinates can cancel those from high-variance coordinates. We address this issue using a weighted, truncated test, adapted to our prior on the variances.
Lower bound for mean estimation with general covariance
This section provides the lower bound of the Bayes risk for random non-diagonal covariance matrices, uniformly distributed among the orthogonal projectors on k k k -dimensional linear subspaces of R d \mathbb{R}^d R d . We define the prior P s u b ( d , k ) \mathcal{P}_{\mathrm{sub}}(d,k) P sub ( d , k ) over ( μ , Σ ) (\mu,\Sigma) ( μ , Σ ) as follows: Let H d , k \mathcal{H}_{d,k} H d , k be the uniform distribution over d × d \times d × matrices with orthonormal columns. Then
( μ , Σ ) ∼ P s u b ( d , k ) ⟺ { μ ∼ N ( 0 , d 2 I d ) Σ = D D T where D ∼ H d , k . (5) (\mu,\Sigma) \sim\mathcal{P}_{\mathrm{sub}}(d,k) \Longleftrightarrow\left\{\begin{aligned}
\mu&\sim\mathcal{N}(0,d^{2}I_{d})\\
\Sigma&= DD^{\mathsf{T}} \text{ where } D \sim\mathcal{H}_{d,k}.
\end{aligned}\right. \tag*{(5)} ( μ , Σ ) ∼ P sub ( d , k ) ⟺ { μ Σ ∼ N ( 0 , d 2 I d ) = D D T where D ∼ H d , k . (5)
This is equivalent to taking Σ \Sigma Σ to be the projector onto a uniformly-random (according to the Haar measure) k k k -dimensional subspace. We will omit the parameters d d d and k k k from the notation when they are clear from context.
Theorem 2.1 (Lower bound for private mean estimation with unknown covariance). There exists c > 0 c > 0 c > 0 such that for all d , k , n ∈ N d,k,n \in\mathbb{N} d , k , n ∈ N with k ≤ c d k \le cd k ≤ c d and n log n ≤ c k n \log n \le ck n log n ≤ c k , every ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP algorithm A \mathcal{A} A satisfies:
Pr ( μ , Σ ) ∼ P s u b X ∼ N ( μ , Σ ) coins of A [ ∥ A ( X ) − μ ∥ 2 ≥ c d k n ] ≥ 1 4 . \underset{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{sub}}\\X\sim\mathcal{N}(\mu,\Sigma)\\\text{coins of }\mathcal{A}}}{\Pr}\left[\left\|\mathcal{A}(X)-\mu\right\|_{2}\geq\frac{c\sqrt{dk}}{n}\right]\geq\frac{1}{4}. ( μ , Σ ) ∼ P sub X ∼ N ( μ , Σ ) coins of A Pr [ ∥ A ( X ) − μ ∥ 2 ≥ n c d k ] ≥ 4 1 .
That is, for all ε ≤ 1 \varepsilon\leq1 ε ≤ 1 and δ ≤ c n \delta\leq\frac{c}{n} δ ≤ n c , we have R ε , δ ( P s u b , n ) = Ω ( d k n ) \mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\Omega\left(\frac{\sqrt{dk}}{n}\right) R ε , δ ( P sub , n ) = Ω ( n d k ) .
Recall that the algorithm of [13 ] for the known covariance case obtains error
O ~ ε , δ ( tr ( Σ ) n + tr ( Σ 1 / 2 ) n ) = O ~ ε , δ ( k n + k n ) . \widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}+\frac{\operatorname{tr}(\Sigma^{1/2})}{n}\right)=\widetilde{O}_{\varepsilon,\delta}\left(\sqrt{\frac{k}{n}}+\frac{k}{n}\right). O ε , δ ( n tr ( Σ ) + n tr ( Σ 1/2 ) ) = O ε , δ ( n k + n k ) .
Comparing the above to our lower bound for mean estimation with unknown covariance yields the following cost of not knowing the covariance in private mean estimation: In the setting of Theorem 2.1,
R ε , δ ( P s u b , n ) = Ω ~ ( d k ) ⋅ R ε , δ k n o w n ( P s u b , n ) . (6) \mathfrak{R}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n)=\widetilde{\Omega}\left(\sqrt{\frac{d}{k}}\right)\cdot\mathfrak{R}^{\mathrm{known}}_{\varepsilon,\delta}(\mathcal{P}_{\mathrm{sub}},n). \tag*{(6)} R ε , δ ( P sub , n ) = Ω ( k d ) ⋅ R ε , δ known ( P sub , n ) . (6)
We note that this blowup is tight, since it matches the error of the folklore algorithm (see Section B). To be precise, for the family P s u b \mathcal{P}_{\mathrm{sub}} P sub , and privacy parameters ε = 1 \varepsilon=1 ε = 1 , δ = c / n \delta=c/n δ = c / n , the folklore algorithm based on [TCKMS22] and presented in Section B achieves, with constant probability, error
O ( k n + d k ( log n ) 3 / 2 n ) . O\left(\sqrt{\frac{k}{n}}+\frac{\sqrt{dk}(\log n)^{3/2}}{n}\right). O ( n k + n d k ( log n ) 3/2 ) .
for n n n larger than a universal constant. If n ≥ C k n \geq Ck n ≥ C k for some constant C > 0 C > 0 C > 0 , then one can learn the k k k -dimensional subspace of Σ \Sigma Σ [SS21, Theorem 1.1, $\ell=k-1$] and learn the mean with dimension-free error after projecting the data on this subspace. Our lower bound applies to the almost-complementary regime where n log n ≤ c k n \log n \leq ck n log n ≤ c k and states that the dimension-dependent cost of privacy of the folklore algorithm is necessary up to polylogarithmic factors.
To prove Theorem 2.1, we first show how to transform any private and sufficiently accurate mean estimation algorithm into a private “sampling” algorithm that correlates with the population covariance matrix.
Definition 2.2 ((λ , α \lambda,\alpha λ , α )-sampler). Fix d , k , n ∈ N d,k,n \in\mathbb{N} d , k , n ∈ N and α , λ > 0 \alpha,\lambda> 0 α , λ > 0 . An algorithm M \mathcal{M} M is a ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler for P s u b \mathcal{P}_{\mathrm{sub}} P sub (defined in (5) ) with sample complexity n n n if
Pr Σ ∼ P s u b X ∼ N ( 0 , Σ ) coins of M [ M ( X ) ⊤ Σ M ( X ) ≥ λ 2 ] ≥ 1 12 \Pr_{\substack{\Sigma\sim\mathcal{P}_{\mathrm{sub}}\\ X \sim\mathcal{N}(0,\Sigma)\\ \text{coins of }\mathcal{M}}}\left[\mathcal{M}(X)^{\top}\Sigma\mathcal{M}(X) \ge\lambda^{2}\right] \ge\frac{1}{12} Σ ∼ P sub X ∼ N ( 0 , Σ ) coins of M Pr [ M ( X ) ⊤ Σ M ( X ) ≥ λ 2 ] ≥ 12 1 and ∥ M ( X ) ∥ 2 ≤ α \|\mathcal{M}(X)\|_{2} \le\alpha ∥ M ( X ) ∥ 2 ≤ α .
Remark 1. Not all values of λ \lambda λ and α \alpha α are compatible with the existence of a ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler. Trivially, it follows directly from the definition that necessarily α ≥ λ \alpha\ge\lambda α ≥ λ . In fact, we will show in § 2.2 that, for n ≤ O ~ ( k ) n \le\widetilde{O}(k) n ≤ O ( k ) , the norm α \alpha α must be significantly larger than λ \lambda λ .
Our main technical contribution is a lower bound on the norm of any private ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler that uses few samples.
Theorem 2.3 (Lower bound for private sampling). There exists a constant c > 0 c > 0 c > 0 such that for all d , k , n ∈ N d,k,n \in\mathbb{N} d , k , n ∈ N and λ > 0 \lambda> 0 λ > 0 , if k ≤ c d k \le cd k ≤ c d and n log n ≤ c k n \log n \le ck n log n ≤ c k then every ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler for P s u b \mathcal{P}_{\mathrm{sub}} P sub with sample complexity n n n that is ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP requires α ≥ c λ d / k \alpha\ge c\lambda\sqrt{d/k} α ≥ c λ d / k .
To prove our main result, we show how to construct a private sampler from a private mean estimation algorithm.
Lemma 2.4 (From mean estimation to sampling). There exists a constant c > 0 c > 0 c > 0 such that for all d , k , n ∈ N d,k,n \in\mathbb{N} d , k , n ∈ N with n ≤ c k n \le ck n ≤ c k and k ≤ d k \le d k ≤ d the following holds: If A \mathcal{A} A is a ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP algorithm satisfying
Pr ( μ , Σ ) ∼ P s u b X ∼ N ( μ , Σ ) ⊗ n coins of A [ ∥ A ( X ) − μ ∥ 2 ≤ α ] ≥ 3 4 , \Pr_{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{sub}}\\ X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}\\ \text{coins of }\mathcal{A}}}\left[\|\mathcal{A}(X)-\mu\|_{2}\le\alpha\right]\ge\frac{3}{4}, ( μ , Σ ) ∼ P sub X ∼ N ( μ , Σ ) ⊗ n coins of A Pr [ ∥ A ( X ) − μ ∥ 2 ≤ α ] ≥ 4 3 , then there exists a ( c k / n , α ) (ck/n,\alpha) ( c k / n , α ) -sampler for P s u b \mathcal{P}_{\mathrm{sub}} P sub with sample complexity n n n that is ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP.
We now combine Theorems 2.3 and 2.4 to complete the proof of the mean estimation lower bound.
Proof of Theorem 2.1. Let c > 0 c > 0 c > 0 be a sufficiently small constant, and let A \mathcal{A} A be a ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP algorithm achieving the accuracy guarantee in Theorem 2.4 with parameter α \alpha α . Then there exists a ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP mechanism M \mathcal{M} M that is a ( c k / n , α ) (ck/n,\alpha) ( c k / n , α ) -sampler for P s u b \mathcal{P}_{\mathrm{sub}} P sub with sample complexity n n n . It follows from Theorem 2.3 that for n log n < c k n\log n < ck n log n < c k , we must have α ≥ Ω ( d k / n ) \alpha\ge\Omega(\sqrt{dk}/n) α ≥ Ω ( d k / n ) , which yields the result. □ \square □
The remainder of the section is organized as follows: In § 2.1 we prove Theorem 2.4 (the reduction from private mean estimation to private sampling), and in § 2.2 we prove Theorem 2.3 (the lower bound on the norm of the sampler).
Reduction from sampling
In this section, we construct a sampler that uses a mean estimation algorithm as a subroutine. The sampler used in our lower bound consists essentially of the clipped error of the mean estimation mechanism.
Proof of Theorem 2.4. For a vector y ∈ R d y \in\mathbb{R}^{d} y ∈ R d we define proj α ( y ) \operatorname{proj}_{\alpha}(y) proj α ( y ) as the projection of y y y into the ℓ 2 \ell_{2} ℓ 2 ball of radius α \alpha α centered at 0 0 0 . For ρ = d \rho= d ρ = d , let M \mathcal{M} M denote the following algorithm:
M ( X ) : Sample μ ∼ N ( 0 , ρ 2 I d ) . Return proj α ( A ( X + μ ) − μ ) . (7) \mathcal{M}(X):\ \text{Sample }\mu\sim\mathcal{N}(0,\rho^{2}I_{d}).\ \text{Return }\operatorname{proj}_{\alpha}(\mathcal{A}(X+\mu)-\mu). \tag*{(7)} M ( X ) : Sample μ ∼ N ( 0 , ρ 2 I d ) . Return proj α ( A ( X + μ ) − μ ) . (7)
Since A \mathcal{A} A is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP, postprocessing immediately implies that M \mathcal{M} M is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP. It remains to show that M \mathcal{M} M is a ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler for appropriate λ \lambda λ . Recall that for every Σ \Sigma Σ we denote ∥ ⋅ ∥ Σ \|\cdot\|_{\Sigma} ∥ ⋅ ∥ Σ the pseudo-norm induced by Σ \Sigma Σ , e.g. ∥ M ( X ) ∥ Σ = M ( X ) T Σ M ( X ) \|\mathcal{M}(X)\|_{\Sigma}=\sqrt{\mathcal{M}(X)^{\mathsf{T}}\Sigma\mathcal{M}(X)} ∥ M ( X ) ∥ Σ = M ( X ) T Σ M ( X ) . Let G 1 : = { ∥ A ( X + μ ) − μ ∥ 2 ≤ α } G_{1}:=\{\|\mathcal{A}(X+\mu)-\mu\|_{2}\leq\alpha\} G 1 := { ∥ A ( X + μ ) − μ ∥ 2 ≤ α } be the event under which the clipping does not modify anything, and for sufficiently small c > 0 c>0 c > 0 , let G 2 : = { ∥ A ( X + μ ) − μ ∥ Σ ≥ c k / n } G_{2}:=\{\|\mathcal{A}(X+\mu)-\mu\|_{\Sigma}\geq ck/n\} G 2 := { ∥ A ( X + μ ) − μ ∥ Σ ≥ c k / n } be the event that the raw output is large. Then, conditioned on G 1 G_{1} G 1 and G 2 G_{2} G 2 we have that
∥ proj α ( A ( X + μ ) − μ ) ∥ Σ = ∥ A ( X + μ ) − μ ∥ Σ ≥ c k n . \|\operatorname{proj}_{\alpha}(\mathcal{A}(X+\mu)-\mu)\|_{\Sigma}=\|\mathcal{A}(X+\mu)-\mu\|_{\Sigma}\geq\frac{ck}{n}. ∥ proj α ( A ( X + μ ) − μ ) ∥ Σ = ∥ A ( X + μ ) − μ ∥ Σ ≥ n c k .
We show that both events hold with probability 1 / 12 1/12 1/12 . Recall that by the guarantee of A \mathcal{A} A we have Pr [ ∥ A ( X + μ ) − μ ∥ 2 ≤ α ] ≥ 3 / 4 \Pr[\|\mathcal{A}(X+\mu)-\mu\|_{2}\leq\alpha]\geq3/4 Pr [ ∥ A ( X + μ ) − μ ∥ 2 ≤ α ] ≥ 3/4 , and thus Pr [ G 1 ] ≥ 3 / 4 \Pr[G_{1}]\geq3/4 Pr [ G 1 ] ≥ 3/4 . Next we show that Pr [ G 2 ] ≥ 1 / 3 \Pr[G_{2}]\geq1/3 Pr [ G 2 ] ≥ 1/3 . Our proof uses the following folklore result, which is a Bayesian variation of well-known lower bounds on private mean estimation under a Gaussian distribution via fingerprinting arguments [24 ] , the specific statement we use is from [21 ] .
Proposition 2.5 (Folklore Result). Let k , n ∈ N k,n\in\mathbb{N} k , n ∈ N . There exist absolute constants c , C > 0 c,C>0 c , C > 0 , such that for any ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -mechanism A : R k × n → R k \mathcal{A}:\mathbb{R}^{k\times n}\to\mathbb{R}^{k} A : R k × n → R k with δ ≤ c / n \delta\leq c/n δ ≤ c / n , any ε ≤ 1 \varepsilon\leq1 ε ≤ 1 , and any ρ ≥ C max ( 1 , k / n ) \rho\geq C\max(1,\sqrt{k}/n) ρ ≥ C max ( 1 , k / n ) ,
Pr μ ∼ N ( 0 , ρ 2 I k ) X ∼ N ( μ , I k ) ⊗ n coins of A [ ∥ A ( X ) − μ ∥ 2 ≥ c k n ] ≥ 1 3 . \Pr_{\substack{\mu\sim\mathcal{N}(0,\rho^{2}I_{k})\\ X\sim\mathcal{N}(\mu,I_{k})^{\otimes n}\\ \text{coins of }\mathcal{A}}}\left[\|\mathcal{A}(X)-\mu\|_{2}\geq\frac{ck}{n}\right]\geq\frac{1}{3}. μ ∼ N ( 0 , ρ 2 I k ) X ∼ N ( μ , I k ) ⊗ n coins of A Pr [ ∥ A ( X ) − μ ∥ 2 ≥ n c k ] ≥ 3 1 .
Fix Σ = D D T \Sigma=DD^{\mathsf{T}} Σ = D D T . We show that there exists an algorithm A Σ \mathcal{A}_{\Sigma} A Σ such that if μ k ∼ N ( 0 , ρ 2 ⋅ I k ) \mu_{k}\sim\mathcal{N}(0,\rho^{2}\cdot I_{k}) μ k ∼ N ( 0 , ρ 2 ⋅ I k ) and Y ∼ N ( μ k , I k ) ⊗ n Y\sim\mathcal{N}(\mu_{k},I_{k})^{\otimes n} Y ∼ N ( μ k , I k ) ⊗ n then ∥ A Σ ( Y ) − μ k ∥ 2 = ∥ A ( X ) − μ ∥ Σ \|\mathcal{A}_{\Sigma}(Y)-\mu_{k}\|_{2}=\|\mathcal{A}(X)-\mu\|_{\Sigma} ∥ A Σ ( Y ) − μ k ∥ 2 = ∥ A ( X ) − μ ∥ Σ , where X ∼ N ( μ , Σ ) ⊗ n X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n} X ∼ N ( μ , Σ ) ⊗ n and μ ∼ N ( 0 , ρ 2 ⋅ I d ) \mu\sim\mathcal{N}(0,\rho^{2}\cdot I_{d}) μ ∼ N ( 0 , ρ 2 ⋅ I d ) . This will allow us to use Theorem 2.5 to bound the probability of event G 2 G_{2} G 2 . Let A Σ \mathcal{A}_{\Sigma} A Σ denote the following algorithm,
A Σ ( Y ) : Sample μ ⊥ ∼ N ( 0 , ρ 2 ⋅ ( I d − Σ ) ) . Set x i = D y i + μ ⊥ . Return D T A ( X ) . (8) \mathcal{A}_{\Sigma}(Y):\ \text{Sample }\mu_{\perp}\sim\mathcal{N}(0,\rho^{2}\cdot(I_{d}-\Sigma)).\ \text{Set }x_{i}=Dy_{i}+\mu_{\perp}.\ \text{Return }D^{\mathsf{T}}\mathcal{A}(X). \tag*{(8)} A Σ ( Y ) : Sample μ ⊥ ∼ N ( 0 , ρ 2 ⋅ ( I d − Σ )) . Set x i = D y i + μ ⊥ . Return D T A ( X ) . (8)
Using the fact that D T D = I k D^{\mathsf{T}}D=I_{k} D T D = I k and D T μ ⊥ = 0 D^{\mathsf{T}}\mu_{\perp}=0 D T μ ⊥ = 0 we see that
∥ D T A ( X ) − μ k ∥ 2 = ∥ D T A ( X ) − D T D μ k ∥ 2 = ∥ D T ( A ( X ) − D μ k − μ ⊥ ) ∥ 2 = ∥ A ( X ) − μ ∥ Σ . \begin{aligned}
\|D^{\mathsf{T}}\mathcal{A}(X)-\mu_{k}\|_{2}
&=\|D^{\mathsf{T}}\mathcal{A}(X)-D^{\mathsf{T}}D\mu_{k}\|_{2}\\
&=\|D^{\mathsf{T}}(\mathcal{A}(X)-D\mu_{k}-\mu_{\perp})\|_{2}\\
&=\|\mathcal{A}(X)-\mu\|_{\Sigma}.
\end{aligned} ∥ D T A ( X ) − μ k ∥ 2 = ∥ D T A ( X ) − D T D μ k ∥ 2 = ∥ D T ( A ( X ) − D μ k − μ ⊥ ) ∥ 2 = ∥ A ( X ) − μ ∥ Σ .
By the distribution of μ k \mu_{k} μ k and μ ⊥ \mu_{\perp} μ ⊥ , the distribution of μ = D μ k + μ ⊥ \mu=D\mu_{k}+\mu_{\perp} μ = D μ k + μ ⊥ is N ( 0 , ρ 2 ⋅ I d ) \mathcal{N}(0,\rho^{2}\cdot I_{d}) N ( 0 , ρ 2 ⋅ I d ) . Moreover, by the distribution of y i y_{i} y i , we have, conditioned on μ \mu μ , that x i ∼ N ( μ , Σ ) x_{i}\sim\mathcal{N}(\mu,\Sigma) x i ∼ N ( μ , Σ ) . Thus, the event G 2 G_{2} G 2 defined above is equivalent to the event that ∥ A Σ ( Y ) − μ k ∥ 2 ≥ c k / n \|\mathcal{A}_{\Sigma}(Y)-\mu_{k}\|_{2}\geq ck/n ∥ A Σ ( Y ) − μ k ∥ 2 ≥ c k / n , which, invoking Theorem 2.5 as ρ = d ≥ k ≥ c − 1 / 2 max ( 1 , k / n ) \rho=d\geq k\geq c^{-1/2}\max(1,\sqrt{k}/n) ρ = d ≥ k ≥ c − 1/2 max ( 1 , k / n ) , occurs with probability at least 1 / 3 1/3 1/3 .
A union bound over G 1 G_{1} G 1 and G 2 G_{2} G 2 now yields that Pr [ ∥ M ( X ) ∥ Σ ≥ c k / n ] ≥ 1 / 12 \Pr[\|\mathcal{M}(X)\|_{\Sigma}\geq ck/n]\geq1/12 Pr [ ∥ M ( X ) ∥ Σ ≥ c k / n ] ≥ 1/12 . Moreover, the definition of M \mathcal{M} M enforces that ∥ M ( X ) ∥ 2 ≤ α \|\mathcal{M}(X)\|_{2}\leq\alpha ∥ M ( X ) ∥ 2 ≤ α , and thus M \mathcal{M} M is a ( c k / n , α ) (ck/n,\alpha) ( c k / n , α ) -sampler. □ \square □
Private sampling lower bound
We consider covariance Σ ∼ P s u b \Sigma\sim\mathcal{P}_{\mathrm{sub}} Σ ∼ P sub , dataset X = x 1 , … , x n ∼ N ( 0 , Σ ) ⊗ n X = x_1, \ldots, x_n \sim\mathcal{N}(0,\Sigma)^{\otimes n} X = x 1 , … , x n ∼ N ( 0 , Σ ) ⊗ n , output y = M ( X ) y = \mathcal{M}(X) y = M ( X ) , test point z ∼ N ( 0 , Σ ) z \sim\mathcal{N}(0,\Sigma) z ∼ N ( 0 , Σ ) . To prove a lower bound on the norm of the sampler, we consider the following test statistic. For fixed Σ \Sigma Σ and y , z ∈ R d y,z \in\mathbb{R}^d y , z ∈ R d with y T Σ y > 0 y^{\mathsf{T}}\Sigma y > 0 y T Σ y > 0 let
T Σ , y ( z ) = ⟨ y , z ⟩ 2 y T Σ y . T_{\Sigma,y}(z) = \frac{\langle y,z\rangle^2}{y^{\mathsf{T}}\Sigma y}. T Σ , y ( z ) = y T Σ y ⟨ y , z ⟩ 2 .
If y T Σ y = 0 y^{\mathsf{T}}\Sigma y = 0 y T Σ y = 0 , then we set T Σ , y ( z ) = 0 T_{\Sigma,y}(z) = 0 T Σ , y ( z ) = 0 . We will omit the dependence on Σ \Sigma Σ and y y y when they are clear from context and instead write T ( z ) T(z) T ( z ) . Theorem 2.3 follows immediately from the following two Lemmata: Our first result provides a bound on the test in the OUT case that holds for all fixed y y y and Σ \Sigma Σ with high probability over the test point z z z .
Lemma 2.6 (OUT case upper bound). For every c ∈ ( 0 , 1 ) c \in(0,1) c ∈ ( 0 , 1 ) there exists C > 0 C > 0 C > 0 such that for all y ∈ R d y \in\mathbb{R}^d y ∈ R d and Σ ⪰ 0 \Sigma\succeq0 Σ ⪰ 0 , if k ≥ C n log n k \ge Cn \log n k ≥ C n log n then
Pr z ∼ N ( 0 , Σ ) [ T Σ , y ( z ) ≥ k 4 n ] ≤ c n . \Pr_{z \sim\mathcal{N}(0,\Sigma)}\left[T_{\Sigma,y}(z) \ge\frac{k}{4n}\right] \le\frac{c}{n}. z ∼ N ( 0 , Σ ) Pr [ T Σ , y ( z ) ≥ 4 n k ] ≤ n c .
Proof of Theorem 2.6. The proof follows from the distribution of T Σ , y ( z ) T_{\Sigma,y}(z) T Σ , y ( z ) for fixed y y y and Σ \Sigma Σ . Observe that ⟨ y , z ⟩ ∼ N ( 0 , y T Σ y ) \langle y,z\rangle\sim\mathcal{N}(0,y^{\mathsf{T}}\Sigma y) ⟨ y , z ⟩ ∼ N ( 0 , y T Σ y ) , and thus ⟨ y , z ⟩ / y T Σ y ∼ N ( 0 , 1 ) \langle y,z\rangle/\sqrt{y^{\mathsf{T}}\Sigma y} \sim\mathcal{N}(0,1) ⟨ y , z ⟩ / y T Σ y ∼ N ( 0 , 1 ) . Since T Σ , y ( z ) = ( ⟨ y , z ⟩ / y T Σ y ) 2 T_{\Sigma,y}(z) = (\langle y,z\rangle/\sqrt{y^{\mathsf{T}}\Sigma y})^2 T Σ , y ( z ) = (⟨ y , z ⟩ / y T Σ y ) 2 we see that T Σ , y ( z ) ∼ χ 1 2 T_{\Sigma,y}(z) \sim\chi_1^2 T Σ , y ( z ) ∼ χ 1 2 . Standard concentration bounds for chi-square random variables (Theorem A.5) yield the result. □
Next, we state an analogous result for the value of the test in the IN case. We show that over the randomness of the data X X X , the mechanism’s output y = M ( X ) y = \mathcal{M}(X) y = M ( X ) , the covariance Σ \Sigma Σ , and the choice of index i i i , T ( x i ) T(x_i) T ( x i ) is “large” with probability Ω ( 1 / n ) \Omega(1/n) Ω ( 1/ n ) .
Lemma 2.7 (IN case lower bound). Let c > 0 c > 0 c > 0 be a sufficiently small constant. Suppose n ≤ c k n \le ck n ≤ c k and α ≤ c λ d / k \alpha\le c\lambda\sqrt{d/k} α ≤ c λ d / k . Then, if i ∼ [ n ] i \sim[n] i ∼ [ n ] is chosen uniformly
Pr X , y , Σ , i [ T Σ , y ( x i ) ≥ k 4 n ] ≥ c n . \Pr_{X,y,\Sigma,i}\left[T_{\Sigma,y}(x_i) \ge\frac{k}{4n}\right] \ge\frac{c}{n}. X , y , Σ , i Pr [ T Σ , y ( x i ) ≥ 4 n k ] ≥ n c .
Proof of Theorem 2.7. Throughout the proof, we let C > 0 C > 0 C > 0 denote a sufficiently large constant and c > 0 c > 0 c > 0 a small constant. We show that there exists an event G G G over the sampling of X X X , y y y and Σ \Sigma Σ such that Pr [ G ] ≥ c \Pr[G] \ge c Pr [ G ] ≥ c , and for all ( X , y , Σ ) (X,y,\Sigma) ( X , y , Σ ) in G G G , the expectation of T ( x i ) T(x_i) T ( x i ) over i i i is at least 4 k / n 4k/n 4 k / n . Thus, there is some i i i such that T ( x i ) ≥ 4 k / n T(x_i) \ge4k/n T ( x i ) ≥ 4 k / n , which, since i i i is uniform in [ n ] [n] [ n ] will suffice to prove the lemma. We begin by defining the event G G G .
Let P X P_X P X be the orthogonal projection onto the span of X X X , and let Σ ^ X = 1 n X X T \widehat{\Sigma}_X = \frac{1}{n}XX^{\mathsf{T}} Σ X = n 1 X X T . Define G = G 1 ∩ G 2 ∩ G 3 G = G_1 \cap G_2 \cap G_3 G = G 1 ∩ G 2 ∩ G 3 as the event that the following three conditions hold:
G 1 : k 2 n ⋅ P X ⪯ Σ ^ X ⪯ 2 k n ⋅ P X . G_1:\quad\frac{k}{2n} \cdot P_X \preceq\widehat{\Sigma}_X \preceq\frac{2k}{n} \cdot P_X. G 1 : 2 n k ⋅ P X ⪯ Σ X ⪯ n 2 k ⋅ P X .
G 2 : y T ( Σ − P X ) y ≤ 2 C α 2 k d . G_2:\quad y^{\mathsf{T}}(\Sigma-P_X)y \le\frac{2C\alpha^2 k}{d}. G 2 : y T ( Σ − P X ) y ≤ d 2 C α 2 k .
G 3 : y T Σ y ≥ λ 2 . G_3:\quad y^{\mathsf{T}}\Sigma y \ge\lambda^2. G 3 : y T Σ y ≥ λ 2 .
Intuitively, the event G G G occurs if X X X is a typical sample, if the norm of y y y in Span ( Σ ) ∖ Span ( X ) \operatorname{Span}(\Sigma) \setminus\operatorname{Span}(X) Span ( Σ ) ∖ Span ( X ) is at most a k d \frac{k}{d} d k fraction of the total norm of y y y , and if the norm of y y y in Span ( Σ ) \operatorname{Span}(\Sigma) Span ( Σ ) is at least the required norm λ 2 \lambda^{2} λ 2 . We first show that the expectation over i i i is large for every X X X , y y y , and Σ \Sigma Σ in G G G .
Claim 2.8. Suppose that α ≤ λ d 4 C k \alpha\le\lambda\sqrt{\frac{d}{4Ck}} α ≤ λ 4 C k d and that X X X , y y y , and Σ \Sigma Σ are in G G G . Then E i [ T Σ , y ( x i ) ] ≥ k 4 n \mathbb{E}_{i}\left[T_{\Sigma,y}(x_i)\right] \ge\frac{k}{4n} E i [ T Σ , y ( x i ) ] ≥ 4 n k .
Proof. The essence of the proof is the observation that
E i [ T ( x i ) ] = y ⊤ E [ x i x i ⊤ ] y y ⊤ Σ y = y ⊤ Σ ^ X y y ⊤ Σ y . \mathbb{E}_{i}[T(x_i)] = \frac{y^{\top}\mathbb{E}[x_i x_i^{\top}]y}{y^{\top}\Sigma y} = \frac{y^{\top}\widehat{\Sigma}_{X}y}{y^{\top}\Sigma y}. E i [ T ( x i )] = y ⊤ Σ y y ⊤ E [ x i x i ⊤ ] y = y ⊤ Σ y y ⊤ Σ X y .
The remainder of the proof follows by algebraic manipulation, and by applying the inequalities that hold for all X X X , y y y , and Σ \Sigma Σ in G G G .
y ⊤ Σ ^ X y y ⊤ Σ y ≥ k 2 n ⋅ y ⊤ P X y y ⊤ Σ y (9) \frac{y^{\top}\widehat{\Sigma}_{X}y}{y^{\top}\Sigma y} \ge\frac{k}{2n}\cdot\frac{y^{\top}P_Xy}{y^{\top}\Sigma y} \tag*{(9)} y ⊤ Σ y y ⊤ Σ X y ≥ 2 n k ⋅ y ⊤ Σ y y ⊤ P X y (9)
≥ k 2 n ⋅ y ⊤ Σ y − 2 C α 2 k / d y ⊤ Σ y (10) \ge\frac{k}{2n}\cdot\frac{y^{\top}\Sigma y-2C\alpha^{2}k/d}{y^{\top}\Sigma y} \tag*{(10)} ≥ 2 n k ⋅ y ⊤ Σ y y ⊤ Σ y − 2 C α 2 k / d (10)
= k 2 n ( 1 − 2 C α 2 k d y ⊤ Σ y ) ≥ k 2 n ( 1 − 2 C α 2 k d λ 2 ) ≥ k 4 n . (11) \begin{aligned}
= \frac{k}{2n}\left(1-\frac{2C\alpha^{2}k}{d y^{\top}\Sigma y}\right) \ge\frac{k}{2n}\left(1-\frac{2C\alpha^{2}k}{d\lambda^{2}}\right) \\
&\ge\frac{k}{4n}. \tag*{(11)}
\end{aligned} = 2 n k ( 1 − d y ⊤ Σ y 2 C α 2 k ) ≥ 2 n k ( 1 − d λ 2 2 C α 2 k ) ≥ 4 n k . (11)
Our second claim states that G G G occurs with constant probability.
Claim 2.9. There exists a constant c > 0 c > 0 c > 0 such that for all sufficiently large k ≤ c d k \le cd k ≤ c d and n ≤ c k n \le ck n ≤ c k , we have Pr X , y , Σ [ G ] ≥ c \Pr_{X,y,\Sigma}[G] \ge c Pr X , y , Σ [ G ] ≥ c .
Proof. Let C > 0 C > 0 C > 0 be a sufficiently large constant. And recall that G 1 G_1 G 1 , G 2 G_2 G 2 and G 3 G_3 G 3 are the events composing G G G . We first bound G 1 G_1 G 1 and G 3 G_3 G 3 : By standard results in random matrix theory (see Theorem A.1), as long as k k k is at least some sufficiently large constant, Pr [ G 1 ] ≥ 1 − 1 / C \Pr[G_1] \ge1 - 1/C Pr [ G 1 ] ≥ 1 − 1/ C . Additionally, by the definition of an ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler (Theorem 2.2) we have Pr [ G 3 ] ≥ 1 12 \Pr[G_3] \ge\frac{1}{12} Pr [ G 3 ] ≥ 12 1 .
It remains to bound the probability of G 2 G_2 G 2 . The key idea is that since Σ \Sigma Σ is uniformly distributed on the space of rank k k k orthogonal projections in R d \mathbb{R}^{d} R d , conditioned on X X X , the matrix Σ − P X \Sigma-P_X Σ − P X is a rank k − n k-n k − n random orthogonal projection within the linear subspace Span ( P X ) ⊥ \operatorname{Span}(P_X)^{\perp} Span ( P X ) ⊥ , which is a d − n d-n d − n dimensional space. Thus,
E [ Σ − P X ∣ X ] = k − n d − n ( I d − P X ) ⪯ 2 k d I d . \mathbb{E}[\Sigma-P_X\mid X]=\frac{k-n}{d-n}(I_d-P_X)\preceq\frac{2k}{d}I_d. E [ Σ − P X ∣ X ] = d − n k − n ( I d − P X ) ⪯ d 2 k I d .
Since ∥ y ∥ 2 ≤ α \lVert y\rVert_2\le\alpha ∥ y ∥ 2 ≤ α we have that E [ y ⊤ ( Σ − P X ) y ] ≤ 2 α 2 k / d \mathbb{E}[y^{\top}(\Sigma-P_X)y]\le2\alpha^{2}k/d E [ y ⊤ ( Σ − P X ) y ] ≤ 2 α 2 k / d , and hence, by Markov’s inequality,
Pr [ G 2 ] ≥ 1 − Pr [ y ⊤ ( Σ − P X ) y ≥ C E [ y ⊤ ( Σ − P X ) y ] ] ≥ 1 − 1 C . \Pr[G_2]\ge1-\Pr\left[y^{\top}(\Sigma-P_X)y\ge C\mathbb{E}[y^{\top}(\Sigma-P_X)y]\right]\ge1-\frac{1}{C}. Pr [ G 2 ] ≥ 1 − Pr [ y ⊤ ( Σ − P X ) y ≥ C E [ y ⊤ ( Σ − P X ) y ] ] ≥ 1 − C 1 .
To complete the proof of the claim, observe that the union bound yields Pr [ G 1 ∩ G 2 ∩ G 3 ] ≥ 1 12 − 2 C ≥ c \Pr[G_1\cap G_2\cap G_3]\ge\frac{1}{12}-\frac{2}{C}\ge c Pr [ G 1 ∩ G 2 ∩ G 3 ] ≥ 12 1 − C 2 ≥ c for C ≥ 48 C\ge48 C ≥ 48 and c ≤ 1 / 24 c\le1/24 c ≤ 1/24 . □
We now complete the proof of Theorem 2.7. Since for every X , y , Σ X,y,\Sigma X , y , Σ in G G G , there exists i ∗ i^* i ∗ such that T ( x i ∗ ) ≥ E i [ T ( x i ) ] T(x_{i^*}) \ge\mathbb{E}_i[T(x_i)] T ( x i ∗ ) ≥ E i [ T ( x i )] , we can conclude that
Pr X , y , Σ , i [ T ( x i ) ≥ k 4 n ] ≥ Pr [ T ( x i ) ≥ k 4 n ∣ G ] Pr [ G ] ≥ Pr [ T ( x i ) ≥ E i [ T ( x i ) ∣ X , y , Σ ] ∣ G ] Pr [ G ] ≥ Pr [ i = i ∗ ] Pr [ G ] ≥ c n . \begin{aligned}
\Pr_{X,y,\Sigma,i}\left[T(x_i) \ge\frac{k}{4n}\right] \ge\Pr\left[T(x_i) \ge\frac{k}{4n} \mid G\right]\Pr[G] \\
&\ge\Pr\left[T(x_i) \ge\mathbb{E}_i[T(x_i)\mid X,y,\Sigma] \mid G\right]\Pr[G] \\
&\ge\Pr[i=i^*]\Pr[G] \\
&\ge\frac{c}{n}.
\end{aligned} X , y , Σ , i Pr [ T ( x i ) ≥ 4 n k ] ≥ Pr [ T ( x i ) ≥ 4 n k ∣ G ] Pr [ G ] ≥ Pr [ T ( x i ) ≥ E i [ T ( x i ) ∣ X , y , Σ ] ∣ G ] Pr [ G ] ≥ Pr [ i = i ∗ ] Pr [ G ] ≥ n c .
The second inequality follows from Theorem 2.8 and the last inequality follows from Theorem 2.9 and the fact that i i i is uniform in [ n ] [n] [ n ] and independent of X X X , y y y and Σ \Sigma Σ . □ \square □
We conclude this section by combining Theorems 2.6 and 2.7 to prove Theorem 2.3 , which states that every ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler that is ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP and uses n ≤ k / log n n \le k/\log n n ≤ k / log n samples has norm α ≥ c λ d / k \alpha\ge c\lambda\sqrt{d/k} α ≥ c λ d / k . It will be convenient to define the following notation for indistinguishability.
Definition 2.10 ((ε , δ \varepsilon,\delta ε , δ )-indistinguishability). Two distributions P , Q \mathcal{P},\mathcal{Q} P , Q over a domain W \mathcal{W} W are ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -indistinguishable, denoted P ≈ ε , δ Q \mathcal{P} \approx_{\varepsilon,\delta} \mathcal{Q} P ≈ ε , δ Q , if, for any measurable subset W ⊂ W W \subset\mathcal{W} W ⊂ W ,
P ( W ) ≤ e ε Q ( W ) + δ and Q ( W ) ≤ e ε P ( W ) + δ . \mathcal{P}(W) \le e^\varepsilon\mathcal{Q}(W)+\delta\quad\text{and} \quad\mathcal{Q}(W) \le e^\varepsilon\mathcal{P}(W)+\delta. P ( W ) ≤ e ε Q ( W ) + δ and Q ( W ) ≤ e ε P ( W ) + δ . If x x x and x ′ x' x ′ are random variables with distribution P \mathcal{P} P and Q \mathcal{Q} Q respectively, we write x ≈ ε , δ x ′ x \approx_{\varepsilon,\delta} x' x ≈ ε , δ x ′ to indicate that P ≈ ε , δ Q \mathcal{P} \approx_{\varepsilon,\delta} \mathcal{Q} P ≈ ε , δ Q .
Proof of Theorem 2.3 . The proof follows by contradiction. Suppose M \mathcal{M} M is an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP ( λ , α ) (\lambda,\alpha) ( λ , α ) -sampler with ε ≤ 1 \varepsilon\le1 ε ≤ 1 , δ ≤ c / 2 n \delta\le c/2n δ ≤ c /2 n and α ≤ c λ d / k \alpha\le c\lambda\sqrt{d/k} α ≤ c λ d / k . For every index i ∈ [ n ] i \in[n] i ∈ [ n ] let X ⊕ i X^{\oplus i} X ⊕ i denote X X X with x i x_i x i replaced by z z z . Then, since M \mathcal{M} M is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP we have
T M ( X ) ( z ) ≈ ε , δ T M ( X ⊕ i ) ( z ) ≡ T M ( X ) ( x i ) T_{\mathcal{M}(X)}(z) \approx_{\varepsilon,\delta} T_{\mathcal{M}(X^{\oplus i})}(z) \equiv T_{\mathcal{M}(X)}(x_i) T M ( X ) ( z ) ≈ ε , δ T M ( X ⊕ i ) ( z ) ≡ T M ( X ) ( x i )
where the equality in distribution follows from the fact that x i x_i x i and z z z are both sampled from N ( 0 , Σ ) \mathcal{N}(0,\Sigma) N ( 0 , Σ ) independently of the other datapoints. Hence, if y = M ( X ) y=\mathcal{M}(X) y = M ( X ) and i ∼ [ n ] i\sim[n] i ∼ [ n ] , then by Theorems 2.6 and 2.7 there exists a constant C > 0 C>0 C > 0 (depending only on c c c ) such that if k ≥ C n log n k \ge Cn\log n k ≥ C n log n
c n ≤ Pr [ T M ( X ) ( x i ) ≥ k 4 n ] ≤ e ε Pr [ T M ( X ) ( z ) ≥ k 4 n ] + δ < c 2 n + c 2 n , \frac{c}{n} \le\Pr\left[T_{\mathcal{M}(X)}(x_i) \ge\frac{k}{4n}\right] \le e^\varepsilon\Pr\left[T_{\mathcal{M}(X)}(z) \ge\frac{k}{4n}\right]+\delta< \frac{c}{2n}+\frac{c}{2n}, n c ≤ Pr [ T M ( X ) ( x i ) ≥ 4 n k ] ≤ e ε Pr [ T M ( X ) ( z ) ≥ 4 n k ] + δ < 2 n c + 2 n c ,
which is a contradiction. Therefore, every such sampler must have α ≥ c λ d / k \alpha\ge c\lambda\sqrt{d/k} α ≥ c λ d / k . □ \square □
Lower bound for mean estimation with diagonal covariance
In this section we show a lower bound for private mean estimation when the covariance matrix is promised to be diagonal. Our lower bound uses the scaled-inverse-chi-squared distribution as a prior over the variances in each coordinate.
Definition 3.1 (inv χ 2 ( τ , ν ) \operatorname{inv}\chi^2(\tau,\nu) inv χ 2 ( τ , ν ) ). The scaled-inverse-chi-squared distribution with ν \nu ν degrees of freedom and scale τ \tau τ is the law with density, for x ≥ 0 x \ge0 x ≥ 0 , given by
f τ , ν ( x ) ∝ exp [ − ν τ 2 2 x ] x 1 + ν / 2 . f_{\tau,\nu}(x) \propto\frac{\exp\left[-\frac{\nu\tau^2}{2x}\right]}{x^{1+\nu/2}}. f τ , ν ( x ) ∝ x 1 + ν /2 exp [ − 2 x ν τ 2 ] . Equivalently σ 2 ∼ inv χ 2 ( ν , τ 2 ) \sigma^2 \sim\operatorname{inv}\chi^2(\nu,\tau^2) σ 2 ∼ inv χ 2 ( ν , τ 2 ) , if ν τ 2 σ 2 ∼ χ ν 2 \frac{\nu\tau^2}{\sigma^2} \sim\chi^2_\nu σ 2 ν τ 2 ∼ χ ν 2 .
We then define the prior P d i a g \mathcal{P}_{\mathrm{diag}} P diag over instance ( μ , Σ ) (\mu,\Sigma) ( μ , Σ ) as follows:
( μ , Σ ) ∼ P d i a g ( d ) ⟺ { μ ∼ N ( 0 , d 2 I d ) Σ = Diag ( ( σ i 2 ) i ∈ [ d ] ) , where ( σ i 2 ) i ∈ [ d ] ∼ inv χ 2 ( 1 , 1 ) ⊗ d (12) (\mu,\Sigma) \sim\mathcal{P}_{\mathrm{diag}}(d) \Longleftrightarrow\left\{
\begin{aligned}
\mu&\sim\mathcal{N}(0,d^2 I_d)\\
\Sigma&= \operatorname{Diag}((\sigma_i^2)_{i\in[d]}),\text{ where }(\sigma_i^2)_{i\in[d]} \sim\operatorname{inv}\chi^2(1,1)^{\otimes d}
\end{aligned}
\right. \tag*{(12)} ( μ , Σ ) ∼ P diag ( d ) ⟺ { μ Σ ∼ N ( 0 , d 2 I d ) = Diag (( σ i 2 ) i ∈ [ d ] ) , where ( σ i 2 ) i ∈ [ d ] ∼ inv χ 2 ( 1 , 1 ) ⊗ d (12)
with μ \mu μ and Σ \Sigma Σ independent. We now state our lower bound for private mean estimation with unknown diagonal covariance.
Theorem 3.2. There exists c > 0 c > 0 c > 0 such that for all d , n ∈ N d,n \in\mathbb{N} d , n ∈ N with n log n ≤ c d n \log n \le c\sqrt{d} n log n ≤ c d , every ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP algorithm A \mathcal{A} A satisfies
Pr X ∼ N ( μ , Σ ) ( μ , Σ ) ∼ P d i a g coins of A [ ∥ A ( X ) − μ ∥ 2 ≥ c d 3 / 2 n 2 log d ] ≥ 1 4 . \underset{\substack{X\sim\mathcal{N}(\mu,\Sigma)\\(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{diag}}\\\text{coins of }\mathcal{A}}}{\Pr}\left[\lVert\mathcal{A}(X)-\mu\rVert_2 \ge\frac{c d^{3/2}}{n^2\log d}\right] \ge\frac{1}{4}. X ∼ N ( μ , Σ ) ( μ , Σ ) ∼ P diag coins of A Pr [ ∥ A ( X ) − μ ∥ 2 ≥ n 2 log d c d 3/2 ] ≥ 4 1 . That is, for all ϵ ≤ 1 \epsilon\le1 ϵ ≤ 1 and δ ≤ c n \delta\le\frac{c}{n} δ ≤ n c we have R ϵ , δ ( P d i a g , n ) = Ω ~ ( d 3 / 2 n 2 ) \mathfrak{R}_{\epsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n)=\widetilde{\Omega}\left(\frac{d^{3/2}}{n^2}\right) R ϵ , δ ( P diag , n ) = Ω ( n 2 d 3/2 ) .
Recall that on instances ( μ , Σ ) ∼ P d i a g (\mu,\Sigma) \sim\mathcal{P}_{\mathrm{diag}} ( μ , Σ ) ∼ P diag the known-covariance algorithm of [13 ] obtains error
O ~ ϵ , δ ( d n ) , \widetilde{O}_{\epsilon,\delta}\left(\frac{d}{\sqrt{n}}\right), O ϵ , δ ( n d ) ,
since tr ( Σ ) = Θ ( d 2 ) \operatorname{tr}(\Sigma)=\Theta(d^2) tr ( Σ ) = Θ ( d 2 ) and tr ( Σ 1 / 2 ) = Θ ( d log d ) \operatorname{tr}(\Sigma^{1/2})=\Theta(d\log d) tr ( Σ 1/2 ) = Θ ( d log d ) with high probability. Thus we obtain the following scale-free “cost” of not knowing the covariance in private mean estimation:
R ϵ , δ ( P d i a g , n ) = Ω ~ ( 1 + d n 3 / 2 ) ⋅ R ϵ , δ k n o w n ( P d i a g , n ) . (13) \mathfrak{R}_{\epsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n)=\widetilde{\Omega}\left(1+\frac{\sqrt{d}}{n^{3/2}}\right)\cdot\mathfrak{R}^{\mathrm{known}}_{\epsilon,\delta}(\mathcal{P}_{\mathrm{diag}},n). \tag*{(13)} R ϵ , δ ( P diag , n ) = Ω ( 1 + n 3/2 d ) ⋅ R ϵ , δ known ( P diag , n ) . (13)
We note that the blow-up in error expressed by (13) , matches the error of the unknown covariance algorithm from [13 ] . To be precise, for the family P d i a g \mathcal{P}_{\mathrm{diag}} P diag and parameters ϵ = 1 \epsilon=1 ϵ = 1 , δ = c / n \delta=c/n δ = c / n , the method in [13 Theorem 4.1] achieves, with constant probability, error
O ( d n + d log d ( log n ) 3 / 2 n + d 3 / 2 ( log d ) 2 ( log n ) 2 log ( d n ) n 2 ) O\left(\frac{d}{\sqrt{n}}+\frac{d\log d(\log n)^{3/2}}{n}+\frac{d^{3/2}(\log d)^2(\log n)^2\log(dn)}{n^2}\right) O ( n d + n d log d ( log n ) 3/2 + n 2 d 3/2 ( log d ) 2 ( log n ) 2 log ( d n ) )
for n ≥ C log n log d log ( d n ) n \ge C\sqrt{\log n}\log d\log(dn) n ≥ C log n log d log ( d n ) for universal constant C > 0 C>0 C > 0 .
When the sample-size is large enough so that n log n ≥ d n\log n \ge\sqrt{d} n log n ≥ d , the middle term dominates the cost of privacy, and it is tight up to polylogarithmic factors, by the known-covariance lower bound [13 ] . The remaining sample-size regime of n log n ≤ d n\log n \le\sqrt{d} n log n ≤ d , is exactly the regime where the third term dominates and matches the regime of our new lower bound, showing that this term is also indeed necessary, up to polylogarithmic factors.
The proof of Theorem 3.2 is similar to Theorem 2.1, but instead of reducing from a sampling problem, we reduce from the following selection problem:
Definition 3.3 ((k , ℓ k,\ell k , ℓ )-selection mechanism). Let d , n , k , ℓ ∈ N d,n,k,\ell\in\mathbb{N} d , n , k , ℓ ∈ N . An algorithm M \mathcal{M} M is a ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism for P d i a g \mathcal{P}_{\mathrm{diag}} P diag with sample complexity n n n if the output s = M ( X ) ∈ { 0 , 1 } d s=\mathcal{M}(\mathcal{X})\in\{0,1\}^{d} s = M ( X ) ∈ { 0 , 1 } d of the algorithm satisfies:
Boundedness: ∑ j = 1 d s j ≤ ℓ \sum_{j=1}^{d}s_j\le\ell ∑ j = 1 d s j ≤ ℓ .
Accuracy: Let π \pi π be the permutation such that σ π ( 1 ) 2 ≥ … ≥ σ π ( d ) 2 \sigma_{\pi(1)}^{2}\ge\ldots\ge\sigma_{\pi(d)}^{2} σ π ( 1 ) 2 ≥ … ≥ σ π ( d ) 2 . Then
Pr Σ ∼ P d i a g X ∼ N ( 0 , Σ ) ⊗ n coins of M [ ∑ j = 1 k s π ( j ) ≥ k 4 ] ≥ 1 3 . \underset{\substack{\Sigma\sim\mathcal{P}_{\mathrm{diag}}\\ X\sim\mathcal{N}(0,\Sigma)^{\otimes n}\\ \text{coins of }\mathcal{M}}}{\Pr}\left[\sum_{j=1}^{k}s_{\pi(j)}\ge\frac{k}{4}\right]\ge\frac{1}{3}. Σ ∼ P diag X ∼ N ( 0 , Σ ) ⊗ n coins of M Pr [ j = 1 ∑ k s π ( j ) ≥ 4 k ] ≥ 3 1 .
In other words, a selection mechanism outputs no more than ℓ \ell ℓ indices, and with probability 1 / 3 1/3 1/3 over the randomness of the data and the algorithm, it selects at least k / 4 k/4 k /4 indices from the indices with the k k k largest variances.
The next theorem shows a tradeoff between the accuracy and the boundedness of private ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanisms.
Theorem 3.4 (Lower bound for private selection). There exist constants C , c > 0 C,c>0 C , c > 0 such that for all d , k , n ∈ N d,k,n\in\mathbb{N} d , k , n ∈ N with C max { n 2 log n , log d } ≤ k ≤ c d C\max\{n^{2}\log n,\log d\}\le k\le cd C max { n 2 log n , log d } ≤ k ≤ c d , every ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism for P d i a g \mathcal{P}_{\mathrm{diag}} P diag with sample complexity n n n that is ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP must have ℓ ≥ d / C log ( d ) \ell\ge d/C\log(d) ℓ ≥ d / C log ( d ) .
Informally, Theorem 3.4 states that a private ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism which successfully selects a constant fraction of the n 2 log n n^{2}\log n n 2 log n largest variance coordinates, must at the same time select almost all the d d d coordinates overall. The proof is deferred to § 3.2 . Next, we state Theorem 3.5, the reduction from private selection, and complete the proof of our main result (Theorem 3.2).
Lemma 3.5 (From mean estimation to selection). There exist constants C , c > 0 C,c>0 C , c > 0 such that for all α > 0 \alpha>0 α > 0 , and n , d , k ∈ N n,d,k\in\mathbb{N} n , d , k ∈ N with C n ≤ k ≤ d Cn\le k\le d C n ≤ k ≤ d , the following holds: If A \mathcal{A} A is a ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP algorithm satisfying
Pr ( μ , Σ ) ∼ P d i a g X ∼ N ( μ , Σ ) ⊗ n coins of A [ ∥ A ( X ) − μ ∥ 2 ≤ α ] ≥ 3 4 , \underset{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{diag}}\\ X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}\\ \text{coins of }\mathcal{A}}}{\Pr}\left[\left\|\mathcal{A}(X)-\mu\right\|_{2}\le\alpha\right]\ge\frac{3}{4}, ( μ , Σ ) ∼ P diag X ∼ N ( μ , Σ ) ⊗ n coins of A Pr [ ∥ A ( X ) − μ ∥ 2 ≤ α ] ≥ 4 3 , then, for ℓ = ⌈ C α 2 k n 2 d 2 ⌉ \ell=\left\lceil\frac{C\alpha^{2}kn^{2}}{d^{2}}\right\rceil ℓ = ⌈ d 2 C α 2 k n 2 ⌉ , there exists a ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP mechanism M \mathcal{M} M that is a ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism for P d i a g \mathcal{P}_{\mathrm{diag}} P diag with sample complexity n n n .
We now combine Theorem 3.5 and Theorem 3.4 to prove the mean estimation lower bound.
Proof of Theorem 3.2. Let c , C > 0 c,C>0 c , C > 0 and ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) be as in Theorem 3.4 . Fix n ∈ N n\in\mathbb{N} n ∈ N and set k = C max { n 2 log n , log d } k=C\max\{n^{2}\log n,\log d\} k = C max { n 2 log n , log d } . Suppose A \mathcal{A} A is an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithm with sample complexity n n n , that achieves error α \alpha α with probability at least 2 / 3 2/3 2/3 on instances sampled from prior P d i a g \mathcal{P}_{\mathrm{diag}} P diag . Then, by Theorem 3.5, there exists an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism with ℓ ≤ C α 2 k n 2 / d 2 \ell\le C\alpha^{2}kn^{2}/d^{2} ℓ ≤ C α 2 k n 2 / d 2 . But by our setting of k k k , Theorem 3.4 implies that ℓ ≥ d / C log d \ell\ge d/C\log d ℓ ≥ d / C log d , and therefore α 2 ≥ c 2 d 3 / C k n 2 log d ≥ Ω ( d 3 / n 4 log ( d ) 2 ) \alpha^{2}\ge c^{2}d^{3}/Ckn^{2}\log d\ge\Omega(d^{3}/n^{4}\log(d)^{2}) α 2 ≥ c 2 d 3 / C k n 2 log d ≥ Ω ( d 3 / n 4 log ( d ) 2 ) . □ \square □
Reduction from selection
In this section, we complete the proof of Theorem 3.5 by using a private mean estimation algorithm to design a ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism. Intuitively, the selection mechanism selects the coordinates in which the mean estimator suffers error above a carefully chosen threshold, and among these, we expect to find a lot of the coordinates with large variance.
Proof of Theorem 3.5. Let A \mathcal{A} A be the algorithm with accuracy α \alpha α as in the statement of Theorem 3.5. Define the selection mechanism M \mathcal{M} M with fixed parameters τ = d C n k \tau= \frac{d}{C n \sqrt{k}} τ = C n k d and ρ = d \rho= d ρ = d as follows:
M ( X ) : Sample μ ∼ N ( 0 , ρ 2 I d ) and set Y = X + μ . For j ∈ [ d ] set s j = 1 [ ∣ A ( Y ) j − μ j ∣ ≥ τ ] . If ∑ j s j ≤ ℓ return s = ( s 1 , … , s d ) , and otherwise return 0. (14) \begin{aligned}
\mathcal{M}(\mathbf{X}) &: \text{Sample } \boldsymbol{\mu} \sim\mathcal{N}(0,\rho^2 I_d) \text{ and set } \mathbf{Y} = \mathbf{X} + \boldsymbol{\mu}.\\
&\text{For } j \in[d] \text{ set } s_j = \mathbb{1}\left[ \left|\mathcal{A}(\mathbf{Y})_j-\mu_j\right| \geq\tau\right].\\
&\text{If } \sum_j s_j \leq\ell\text{ return } \mathbf{s}=(s_1,\ldots,s_d), \text{ and otherwise return } 0. \tag*{(14)}
\end{aligned} M ( X ) : Sample μ ∼ N ( 0 , ρ 2 I d ) and set Y = X + μ . For j ∈ [ d ] set s j = 1 [ ∣ A ( Y ) j − μ j ∣ ≥ τ ] . If j ∑ s j ≤ ℓ return s = ( s 1 , … , s d ) , and otherwise return 0. (14) To show that M \mathcal{M} M is a ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism, we must show that it never selects more than ℓ \ell ℓ coordinates, and that with probability at least 1 / 4 1/4 1/4 it selects at least k / 4 k/4 k /4 of the coordinates with the k k k largest variances. By inspection of (14) , one can easily see that M \mathcal{M} M never outputs a selection of more than ℓ \ell ℓ coordinates.
Let J = { π ( 1 ) , … , π ( k ) } J=\{\pi(1),\ldots,\pi(k)\} J = { π ( 1 ) , … , π ( k )} be the coordinates of the largest k k k variances in Σ \Sigma Σ . In the remainder of the proof, we argue that M \mathcal{M} M outputs at least k / 4 k/4 k /4 of the coordinates in J J J with probability at least 1 / 4 1/4 1/4 . First we argue that M \mathcal{M} M typically does not return 0: By construction of M \mathcal{M} M , for any choice of τ \tau τ , we have τ 2 ∑ j = 1 d s j ≤ ∥ A ( Y ) − μ ∥ 2 2 \tau^2\sum_{j=1}^{d}s_j\leq\|\mathcal{A}(\mathbf{Y})-\boldsymbol{\mu}\|_2^2 τ 2 ∑ j = 1 d s j ≤ ∥ A ( Y ) − μ ∥ 2 2 , and therefore, setting ℓ = ⌈ α 2 / τ 2 ⌉ \ell=\lceil\alpha^2/\tau^2\rceil ℓ = ⌈ α 2 / τ 2 ⌉ and using the accuracy guarantee of A \mathcal{A} A ,
Pr ( μ , Σ ) ∼ P d i a g X ∼ N ( 0 , Σ ) ⊗ n [ ∑ j = 1 d s j ≤ ℓ ] ≥ Pr ( μ , Σ ) ∼ P d i a g Y ∼ N ( μ , Σ ) ⊗ n [ ∥ A ( Y ) − μ ∥ ≤ α ] ≥ 3 4 . (15) \Pr_{\substack{(\boldsymbol{\mu},\Sigma)\sim P_{\mathrm{diag}}\\ \mathbf{X}\sim\mathcal{N}(0,\Sigma)^{\otimes n}}}\left[\sum_{j=1}^{d}s_j\leq\ell\right]\geq
\Pr_{\substack{(\boldsymbol{\mu},\Sigma)\sim P_{\mathrm{diag}}\\ \mathbf{Y}\sim\mathcal{N}(\boldsymbol{\mu},\Sigma)^{\otimes n}}}\left[\|\mathcal{A}(\mathbf{Y})-\boldsymbol{\mu}\|\leq\alpha\right]\geq\frac{3}{4}. \tag*{(15)} ( μ , Σ ) ∼ P diag X ∼ N ( 0 , Σ ) ⊗ n Pr [ j = 1 ∑ d s j ≤ ℓ ] ≥ ( μ , Σ ) ∼ P diag Y ∼ N ( μ , Σ ) ⊗ n Pr [ ∥ A ( Y ) − μ ∥ ≤ α ] ≥ 4 3 . (15) Next, we argue that s j = 1 s_j=1 s j = 1 for at least k / 4 k/4 k /4 of the indices in J J J with probability at least 1 / 4 1/4 1/4 . Our proof leverages a version of the standard lower bound for private mean estimation that bounds the number of coordinates with error above some threshold.
Proposition 3.6 (Coordinate-wise error lower bound [21 ] ). There exist constants C , c > 0 C,c>0 C , c > 0 such that for all n , d ∈ N n,d\in\mathbb{N} n , d ∈ N and α , ρ > 0 \alpha,\rho>0 α , ρ > 0 satisfying
ρ ≥ C max { 1 , α } , d ≥ C ( n + α 2 n 2 ) , \rho\geq C\max\{1,\alpha\},\qquad d\geq C(n+\alpha^2n^2), ρ ≥ C max { 1 , α } , d ≥ C ( n + α 2 n 2 ) , if μ ∼ N ( 0 , ρ 2 I d ) \boldsymbol{\mu}\sim\mathcal{N}(0,\rho^2 I_d) μ ∼ N ( 0 , ρ 2 I d ) and X = x 1 , … , x n ∼ N ( μ , I d ) ⊗ n \mathbf{X}=\mathbf{x}_1,\ldots,\mathbf{x}_n\sim\mathcal{N}(\boldsymbol{\mu},I_d)^{\otimes n} X = x 1 , … , x n ∼ N ( μ , I d ) ⊗ n , then every ( 1 , c / n ) (1,c/n) ( 1 , c / n ) -DP mechanism A \mathcal{A} A satisfies
Pr μ ∼ N ( 0 , ρ 2 I d ) X ∼ N ( μ , I d ) [ ∣ { j ∈ [ d ] : ∣ A ( X ) j − μ j ∣ ≥ α } ∣ ≥ d / 2 ] ≥ 2 3 . \Pr_{\substack{\boldsymbol{\mu}\sim\mathcal{N}(0,\rho^2 I_d)\\ \mathbf{X}\sim\mathcal{N}(\boldsymbol{\mu},I_d)}}\left[\left|\left\{j\in[d]:\left|\mathcal{A}(\mathbf{X})_j-\mu_j\right|\geq\alpha\right\}\right|\geq d/2\right]\geq\frac{2}{3}. μ ∼ N ( 0 , ρ 2 I d ) X ∼ N ( μ , I d ) Pr [ ∣ { j ∈ [ d ] : ∣ A ( X ) j − μ j ∣ ≥ α } ∣ ≥ d /2 ] ≥ 3 2 . Since Theorem 3.6 is for identity covariance, a few extra steps will be needed before we can apply it to our setting. Informally, we will construct an algorithm A Σ \mathcal{A}_{\Sigma} A Σ that uses A \mathcal{A} A as a subroutine for a k k k -dimensional mean estimation problem with identity covariance. We then show that the per-coordinate error of A Σ \mathcal{A}_{\Sigma} A Σ can be bounded by the error of A \mathcal{A} A on the coordinates in J J J . Applying Theorem 3.6 to A Σ \mathcal{A}_{\Sigma} A Σ allows us to conclude that A \mathcal{A} A must have large error in many of the coordinates in J J J .
Consider the following k k k -dimensional mean estimation problem:
θ ∼ N ( 0 , 4 k 2 ρ 2 d 2 I k ) and Z = z 1 , … , z n ∼ N ( θ , I k ) ⊗ n . (16) \theta\sim\mathcal{N}\left(0,\frac{4k^2\rho^2}{d^2}I_k\right)\text{ and }Z=z_1,\ldots,z_n\sim\mathcal{N}(\theta,I_k)^{\otimes n}. \tag*{(16)} θ ∼ N ( 0 , d 2 4 k 2 ρ 2 I k ) and Z = z 1 , … , z n ∼ N ( θ , I k ) ⊗ n . (16)
For a vector y ∈ R d y\in\mathbb{R}^d y ∈ R d and J ⊆ [ d ] J\subseteq[d] J ⊆ [ d ] , let y J y_J y J denote the vector ( y j ) j ∈ J (y_j)_{j\in J} ( y j ) j ∈ J , and similarly, for a matrix Σ ∈ R d × d \Sigma\in\mathbb{R}^{d\times d} Σ ∈ R d × d , let Σ J \Sigma_J Σ J denote the ∣ J ∣ × ∣ J ∣ |J|\times|J| ∣ J ∣ × ∣ J ∣ matrix with entries Σ j , j ′ \Sigma_{j,j'} Σ j , j ′ for j , j ′ ∈ J j,j'\in J j , j ′ ∈ J . Define algorithm A Σ \mathcal{A}_{\Sigma} A Σ as follows:
A Σ ( Z ) : If σ π ( k ) 2 < d 2 4 k 2 return ⊥ . Otherwise continue. \mathcal{A}_{\Sigma}(Z):\text{ If }\sigma_{\pi(k)}^2<\frac{d^2}{4k^2}\text{ return }\bot.\text{ Otherwise continue.} A Σ ( Z ) : If σ π ( k ) 2 < 4 k 2 d 2 return ⊥. Otherwise continue.
Sample θ J ′ ∼ N ( 0 , ρ 2 I d − k ) and for each i ∈ [ n ] : \text{Sample }\theta'_J\sim\mathcal{N}(0,\rho^2I_{d-k})\text{ and for each }i\in[n]: Sample θ J ′ ∼ N ( 0 , ρ 2 I d − k ) and for each i ∈ [ n ] :
Sample y ~ i , J = d 2 k z i + w i where w i ∼ N ( 0 , Σ J − d 2 4 k 2 I k ) . (17) \text{Sample }\widetilde{y}_{i,J}=\frac{d}{2k}z_i+w_i\text{ where }w_i\sim\mathcal{N}\left(0,\Sigma_J-\frac{d^2}{4k^2}I_k\right). \tag*{(17)} Sample y i , J = 2 k d z i + w i where w i ∼ N ( 0 , Σ J − 4 k 2 d 2 I k ) . (17)
Sample y ~ i , J ‾ ∼ N ( θ J ′ , Σ J ‾ ) \text{Sample }\widetilde{y}_{i,\overline{J}}\sim\mathcal{N}(\theta'_J,\Sigma_{\overline{J}}) Sample y i , J ∼ N ( θ J ′ , Σ J )
Return 2 k d A ( Y ~ ) J \text{Return }\frac{2k}{d}\mathcal{A}(\widetilde{Y})_J Return d 2 k A ( Y ) J
To see that A Σ \mathcal{A}_{\Sigma} A Σ is private, observe that since A \mathcal{A} A is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP, and for fixed random coins, A Σ \mathcal{A}_{\Sigma} A Σ simply runs A \mathcal{A} A on an affine transformation of the data and outputs the result, we have that A Σ \mathcal{A}_{\Sigma} A Σ is also ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP.
Next, we relate the accuracy of A Σ \mathcal{A}_{\Sigma} A Σ on the task defined in (16) , to the accuracy of A \mathcal{A} A on the coordinates in J J J in the experiment in the statement of the lemma. Let G G G denote the event that σ π ( k ) 2 ≥ d 2 / 4 k 2 \sigma_{\pi(k)}^2\ge d^2/4k^2 σ π ( k ) 2 ≥ d 2 /4 k 2 , and let θ J ′ = d 2 k θ \theta'_J=\frac{d}{2k}\theta θ J ′ = 2 k d θ . Then, conditional on G G G we have that y ~ i , J ∼ N ( θ J ′ , Σ J ) \widetilde{y}_{i,J}\sim\mathcal{N}(\theta'_J,\Sigma_J) y i , J ∼ N ( θ J ′ , Σ J ) and thus, by the distribution of y ~ i , J ‾ \widetilde{y}_{i,\overline{J}} y i , J , that Y ~ ∼ N ( ( θ J ′ , θ J ‾ ′ ) , Σ ) \widetilde{Y}\sim\mathcal{N}((\theta'_J,\theta'_{\overline{J}}),\Sigma) Y ∼ N (( θ J ′ , θ J ′ ) , Σ ) . Additionally, by the distribution of θ \theta θ and θ J ′ \theta'_J θ J ′ , we have that θ ′ = ( θ J ′ , θ J ‾ ′ ) ∼ N ( 0 , ρ 2 I d ) \theta'=(\theta'_J,\theta'_{\overline{J}})\sim\mathcal{N}(0,\rho^2I_d) θ ′ = ( θ J ′ , θ J ′ ) ∼ N ( 0 , ρ 2 I d ) . Furthermore, conditional on G G G , for each j ∈ [ k ] j\in[k] j ∈ [ k ] we have
∣ A Σ ( Z ) j − θ j ∣ = 2 k d ∣ A ( Y ~ ) π ( j ) − θ π ( j ) ′ ∣ = d 2 k d ∣ A ( Y ) π ( j ) − μ π ( j ) ∣ , \left|\mathcal{A}_{\Sigma}(Z)_j-\theta_j\right|=\frac{2k}{d}\left|\mathcal{A}(\widetilde{Y})_{\pi(j)}-\theta'_{\pi(j)}\right|\overset{\mathrm{d}}{=}\frac{2k}{d}\left|\mathcal{A}(Y)_{\pi(j)}-\mu_{\pi(j)}\right|, ∣ A Σ ( Z ) j − θ j ∣ = d 2 k A ( Y ) π ( j ) − θ π ( j ) ′ = d d 2 k A ( Y ) π ( j ) − μ π ( j ) ,
where the equality in distribution holds since conditional on G G G we have Y ≡ Y ~ Y\equiv\widetilde{Y} Y ≡ Y and μ ≡ θ ′ \mu\equiv\theta' μ ≡ θ ′ . Thus, if B 0 B_0 B 0 denotes the event that ∣ { j ∈ [ k ] : ∣ A Σ ( Z ) j − θ j ∣ ≤ τ ⋅ 2 k d } ∣ ≥ k / 2 \left|\{j\in[k]:|\mathcal{A}_{\Sigma}(Z)_j-\theta_j|\le\tau\cdot\frac{2k}{d}\}\right|\ge k/2 { j ∈ [ k ] : ∣ A Σ ( Z ) j − θ j ∣ ≤ τ ⋅ d 2 k } ≥ k /2 and B 1 B_1 B 1 denotes the event that ∣ { j ∈ [ k ] : ∣ A ( Y ) π ( j ) − μ π ( j ) ∣ ≤ τ } ∣ ≥ k / 2 \left|\{j\in[k]:|\mathcal{A}(Y)_{\pi(j)}-\mu_{\pi(j)}|\le\tau\}\right|\ge k/2 { j ∈ [ k ] : ∣ A ( Y ) π ( j ) − μ π ( j ) ∣ ≤ τ } ≥ k /2 then
Pr [ B 1 ] ≤ Pr [ G ‾ ] + Pr [ B 0 ] . \Pr[B_1]\le\Pr[\overline{G}]+\Pr[B_0]. Pr [ B 1 ] ≤ Pr [ G ] + Pr [ B 0 ] .
By our setting of ρ \rho ρ and τ \tau τ we have 2 k τ / d = 2 k / C n ≤ 2 k ρ / C d 2k\tau/d=2\sqrt{k}/Cn\le2k\rho/Cd 2 k τ / d = 2 k / C n ≤ 2 k ρ / C d (the standard deviation in (16) is 2 k ρ / d 2k\rho/d 2 k ρ / d ), and by our setting of k k k and n n n , we have k ≥ C ( n + 4 k 2 τ 2 n 2 d 2 ) k\ge C\left(n+\frac{4k^2\tau^2n^2}{d^2}\right) k ≥ C ( n + d 2 4 k 2 τ 2 n 2 ) . Thus, we can apply Theorem 3.6 to A Σ \mathcal{A}_{\Sigma} A Σ with ambient dimension k k k and coordinate-wise error threshold α ← τ ⋅ 2 k d \alpha\leftarrow\tau\cdot\frac{2k}{d} α ← τ ⋅ d 2 k to see that
Pr [ B 0 ] ≤ 1 3 . \Pr[B_0]\le\frac{1}{3}. Pr [ B 0 ] ≤ 3 1 .
Additionally, since by Theorem A.4 we have that Pr [ G ‾ ] ≤ 1 6 \Pr[\overline{G}]\le\frac{1}{6} Pr [ G ] ≤ 6 1 , we can conclude that
Pr [ B 1 ] ≤ 1 3 + 1 12 \Pr[B_1]\le\frac{1}{3}+\frac{1}{12} Pr [ B 1 ] ≤ 3 1 + 12 1
for k ≥ 24 k\ge24 k ≥ 24 —that is, A ( Y ) \mathcal{A}(Y) A ( Y ) has error at most τ \tau τ in at least k / 2 k/2 k /2 of the coordinates in J J J with probability at most 1 3 + 1 12 \frac{1}{3}+\frac{1}{12} 3 1 + 12 1 .
We now return to the analysis of mechanism M \mathcal{M} M (defined in (14) ). Applying the union bound over B 1 B_1 B 1 and the event controlled in (15) , we see that with probability at least 1 4 \frac{1}{4} 4 1 over the sampling of the instance ( μ , Σ ) ∼ P d i a g (\mu,\Sigma)\sim\mathcal{P}_{\mathrm{diag}} ( μ , Σ ) ∼ P diag , the data X ∼ N ( 0 , Σ ) X\sim\mathcal{N}(0,\Sigma) X ∼ N ( 0 , Σ ) , and the coins of the mechanism, M \mathcal{M} M outputs a vector s s s such that ∑ s i ≤ ℓ \sum s_i\le\ell ∑ s i ≤ ℓ , and s j = 1 s_j=1 s j = 1 for at least k / 2 k/2 k /2 of the coordinates j ∈ J j\in J j ∈ J . Thus, M \mathcal{M} M is a ( k , ℓ ) (k,\ell) ( k , ℓ ) selection mechanism with ℓ = ⌈ α 2 / τ 2 ⌉ \ell=\lceil\alpha^2/\tau^2\rceil ℓ = ⌈ α 2 / τ 2 ⌉ , which, by our setting of τ \tau τ , completes the proof. □ \square □
Private selection lower bound
To prove Theorem 3.4 , similarly to the diagonal case, we consider a test statistic that measures the correlation between the selection mechanism M \mathcal{M} M and the empirical covariance of the dataset. Fix a covariance matrix Σ ∈ R d × d = Diag ( σ 1 2 , … , σ d 2 ) \Sigma\in\mathbb{R}^{d \times d} = \operatorname{Diag}(\sigma_1^2,\ldots,\sigma_d^2) Σ ∈ R d × d = Diag ( σ 1 2 , … , σ d 2 ) , a selection vector s ∈ { 0 , 1 } d s \in\{0,1\}^d s ∈ { 0 , 1 } d , and a test point z ∈ R d z \in\mathbb{R}^d z ∈ R d . Define the test
T Σ , s ( z ) : = ∑ j ∈ [ d ] T Σ , s , j ( z ) , where T Σ , s , j ( z ) : = ( z j 2 σ j 2 − 1 ) min { σ j , L } s j , (18) \mathcal{T}_{\Sigma,s}(z) := \sum_{j \in[d]} \mathcal{T}_{\Sigma,s,j}(z), \qquad\text{where} \qquad\mathcal{T}_{\Sigma,s,j}(z) := \left(\frac{z_j^2}{\sigma_j^2}-1\right)\min\{\sigma_j,L\}s_j, \tag*{(18)} T Σ , s ( z ) := j ∈ [ d ] ∑ T Σ , s , j ( z ) , where T Σ , s , j ( z ) := ( σ j 2 z j 2 − 1 ) min { σ j , L } s j , (18)
and where L = L ( d , k ) L = L(d,k) L = L ( d , k ) is a parameter which we will set later.
We typically omit Σ \Sigma Σ and s s s from the notation for readability, using just T \mathcal{T} T and T j \mathcal{T}_j T j . Additionally, for convenience, we will use the shorthand h ( σ ) h(\sigma) h ( σ ) for min { σ , L } \min\{\sigma,L\} min { σ , L } . Similarly to § 2 , we compare the distribution of the two statistics with covariance Σ ∼ P d i a g \Sigma\sim\mathcal{P}_{\mathrm{diag}} Σ ∼ P diag , dataset X ∼ N ( 0 , Σ ) ⊗ n \mathbf{X} \sim\mathcal{N}(0,\Sigma)^{\otimes n} X ∼ N ( 0 , Σ ) ⊗ n , fresh sample z ∼ N ( 0 , Σ ) z \sim\mathcal{N}(0,\Sigma) z ∼ N ( 0 , Σ ) , and selection vector s ∼ M ( X ) s \sim\mathcal{M}(\mathbf{X}) s ∼ M ( X ) :
The OUT sample case in which we consider T Σ , s ( z ) \mathcal{T}_{\Sigma,s}(z) T Σ , s ( z )
The IN sample case in which we consider T Σ , s ( x i ) \mathcal{T}_{\Sigma,s}(x_i) T Σ , s ( x i ) with i i i uniform in [ n ] [n] [ n ] .
The following statements show that there exists a threshold τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) such that with high probability T ( x i ) ≥ d τ / n \mathcal{T}(x_i) \ge d\tau/n T ( x i ) ≥ d τ / n and T ( z ) < d τ / n \mathcal{T}(z) < d\tau/n T ( z ) < d τ / n . We defer the proof of Theorem 3.7 to § 3.3 , and Theorem 3.8 to § 3.4 , and complete the proof of the selection lower bound (Theorem 3.4 ) below.
Lemma 3.7 (OUT sample test is small). Fix τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) . There exist C > 0 C > 0 C > 0 such that for all d , k , n , ℓ ∈ N d,k,n,\ell\in\mathbb{N} d , k , n , ℓ ∈ N with k ≥ C n 2 log n k \ge Cn^2\log n k ≥ C n 2 log n , if L = d 4 k L = \frac{d}{4k} L = 4 k d then every ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism M \mathcal{M} M satisfies
Pr Σ , X , z , M [ T ( z ) ≥ d τ n ] = O ( 1 n 2 ) . \Pr_{\Sigma,\mathbf{X},z,\mathcal{M}}\left[\mathcal{T}(z) \ge\frac{d\tau}{n}\right] = O\left(\frac{1}{n^2}\right). Σ , X , z , M Pr [ T ( z ) ≥ n d τ ] = O ( n 2 1 ) .
Lemma 3.8 (IN sample test is large). Let C > 0 C > 0 C > 0 be sufficiently large. There exists τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) such that for all d , k , n , ℓ ∈ N d,k,n,\ell\in\mathbb{N} d , k , n , ℓ ∈ N with C max { n , log d } ≤ k ≤ d / C C\max\{n,\log d\} \le k \le d/C C max { n , log d } ≤ k ≤ d / C and ℓ ≤ d / C log d \ell\le d/C\log d ℓ ≤ d / C log d , if L = d 4 k L = \frac{d}{4k} L = 4 k d then every ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism M \mathcal{M} M satisfies
Pr Σ , X , i , M [ T ( x i ) ≥ d τ n ] = Ω ( 1 n ) . \Pr_{\Sigma,\mathbf{X},i,\mathcal{M}}\left[\mathcal{T}(x_i) \ge\frac{d\tau}{n}\right] = \Omega\left(\frac{1}{n}\right). Σ , X , i , M Pr [ T ( x i ) ≥ n d τ ] = Ω ( n 1 ) .
Proof of Theorem 3.4 . The proof follows by contradiction. Suppose M \mathcal{M} M is an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP ( k , ℓ ) (k,\ell) ( k , ℓ ) -selection mechanism with ε ≤ 1 \varepsilon\le1 ε ≤ 1 , δ ≤ c / n \delta\le c/n δ ≤ c / n , k ≥ C max { n 2 log n , log d } k \ge C\max\{n^2\log n,\log d\} k ≥ C max { n 2 log n , log d } , and ℓ ≤ d / C log ( d ) \ell\le d/C\log(d) ℓ ≤ d / C log ( d ) .
For every index i ∈ [ n ] i \in[n] i ∈ [ n ] let X ⊕ i \mathbf{X}^{\oplus i} X ⊕ i denote X \mathbf{X} X with x i x_i x i replaced by z z z , and let T ⊕ i \mathcal{T}^{\oplus i} T ⊕ i denote T \mathcal{T} T executed on M ( X ⊕ i ) \mathcal{M}(\mathbf{X}^{\oplus i}) M ( X ⊕ i ) . Then, since M \mathcal{M} M is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP we have
T ( z ) ≈ ε , δ T ⊕ i ( z ) ≡ T ( x i ) \mathcal{T}(z) \approx_{\varepsilon,\delta} \mathcal{T}^{\oplus i}(z) \equiv\mathcal{T}(x_i) T ( z ) ≈ ε , δ T ⊕ i ( z ) ≡ T ( x i )
where ≈ ε , δ \approx_{\varepsilon,\delta} ≈ ε , δ is defined in Theorem 2.10, and the equality in distribution follows from the fact that x i x_i x i and z z z are both sampled from N ( 0 , Σ ) \mathcal{N}(0,\Sigma) N ( 0 , Σ ) independently of the other datapoints. Hence, if i ∼ [ n ] i \sim[n] i ∼ [ n ] , and τ \tau τ is the constant in Theorem 3.8, then
Ω ( 1 n ) ≤ Pr [ T ( x i ) ≥ d τ n ] ≤ e ε Pr [ T ( z ) ≥ d τ n ] + δ ≤ O ( 1 n 2 ) + c n \Omega\left(\frac{1}{n}\right) \le\Pr\left[\mathcal{T}(x_i) \ge\frac{d\tau}{n}\right] \le e^\varepsilon\Pr\left[\mathcal{T}(z) \ge\frac{d\tau}{n}\right] + \delta\le O\left(\frac{1}{n^2}\right) + \frac{c}{n} Ω ( n 1 ) ≤ Pr [ T ( x i ) ≥ n d τ ] ≤ e ε Pr [ T ( z ) ≥ n d τ ] + δ ≤ O ( n 2 1 ) + n c
which, for sufficiently small c c c yields a contradiction. □
Analysis of the test in the OUT case
In this section, we prove Theorem 3.7, which states that T ( z ) ≥ d τ / n \mathcal{T}(z) \ge d\tau/n T ( z ) ≥ d τ / n with probability at most O ( 1 / n 2 ) O(1/n^2) O ( 1/ n 2 ) .
Proof of Theorem 3.7. First we bound the expectation. Observe that for every fixed Σ \Sigma Σ , X X X , and s = M ( X ) s=\mathcal{M}(X) s = M ( X )
E z j [ T j ( z ) ] = E z j [ z j 2 σ j 2 − 1 ] h ( σ j ) s j = 0 \mathbb{E}_{z_j}[\mathcal{T}_j(z)] = \mathbb{E}_{z_j}\left[\frac{z_j^2}{\sigma_j^2}-1\right]h(\sigma_j)s_j=0 E z j [ T j ( z )] = E z j [ σ j 2 z j 2 − 1 ] h ( σ j ) s j = 0
and thus, by linearity of expectation E [ T ( z ) ] = 0 \mathbb{E}[\mathcal{T}(z)]=0 E [ T ( z )] = 0 .
Next, we prove a high probability bound on T ( z ) \mathcal{T}(z) T ( z ) . Since for fixed σ j \sigma_j σ j and z j ∼ N ( 0 , σ j 2 ) z_j\sim\mathcal{N}(0,\sigma_j^2) z j ∼ N ( 0 , σ j 2 ) , the random variable z j 2 / σ j 2 z_j^2/\sigma_j^2 z j 2 / σ j 2 is χ 1 2 \chi_1^2 χ 1 2 , we can apply a scalar Bernstein inequality (e.g., Corollary 2.9.2 [Ver26]) to see that
Pr [ ∣ ∑ j ∈ [ d ] T j ( z ) ∣ ≥ ∑ j ∈ [ d ] h ( σ j ) 2 log ( 1 / β ) s j + L log ( 1 / β ) ] ≤ β . \Pr\left[\left|\sum_{j\in[d]}\mathcal{T}_j(z)\right|\ge\sqrt{\sum_{j\in[d]}h(\sigma_j)^2\log(1/\beta)s_j}+L\log(1/\beta)\right]\le\beta. Pr j ∈ [ d ] ∑ T j ( z ) ≥ j ∈ [ d ] ∑ h ( σ j ) 2 log ( 1/ β ) s j + L log ( 1/ β ) ≤ β .
Next, we prove a high probability bound on ∑ h ( σ j ) 2 s j \sum h(\sigma_j)^2s_j ∑ h ( σ j ) 2 s j . The proof goes through a Chernoff bound for bounded nonnegative random variables (Theorem A.2 ) applied to h ( σ j ) 2 ∈ [ 0 , L 2 ] h(\sigma_j)^2\in[0,L^2] h ( σ j ) 2 ∈ [ 0 , L 2 ] . We first bound the expectation:
E [ h ( σ j ) 2 ] ≤ ∫ 0 L 2 Pr [ σ j 2 ≥ t ] d t ≤ 1 + ∫ 1 L 2 t − 1 / 2 d t ≤ 2 L . \mathbb{E}[h(\sigma_j)^2]\le\int_0^{L^2}\Pr[\sigma_j^2\ge t]\,dt\le1+\int_1^{L^2}t^{-1/2}\,dt\le2L. E [ h ( σ j ) 2 ] ≤ ∫ 0 L 2 Pr [ σ j 2 ≥ t ] d t ≤ 1 + ∫ 1 L 2 t − 1/2 d t ≤ 2 L .
Applying Theorem A.2 , there exists a constant C 1 C_1 C 1 such that
∑ j ∈ [ d ] h ( σ j ) 2 log ( 1 / β ) ≤ C 1 L d log ( 1 / β ) + L log ( 1 / β ) \sqrt{\sum_{j\in[d]}h(\sigma_j)^2\log(1/\beta)}\le\sqrt{C_1Ld\log(1/\beta)}+L\log(1/\beta) j ∈ [ d ] ∑ h ( σ j ) 2 log ( 1/ β ) ≤ C 1 L d log ( 1/ β ) + L log ( 1/ β )
with probability at least 1 − β 1-\beta 1 − β , which, since s j ∈ { 0 , 1 } s_j\in\{0,1\} s j ∈ { 0 , 1 } implies the same bound on the sum involving s j s_j s j . Setting β = O ( 1 / n 2 ) \beta=O(1/n^2) β = O ( 1/ n 2 ) and choosing C = C ( τ , C 1 ) C=C(\tau,C_1) C = C ( τ , C 1 ) , we see that if L = d / 4 k ≤ d / C n 2 log n L=d/4k\le d/Cn^2\log n L = d /4 k ≤ d / C n 2 log n we obtain the desired bound
Pr [ ∑ j ∈ [ d ] T j ( z ) ≥ d τ n ] ≤ O ( 1 n 2 ) . \Pr\left[\sum_{j\in[d]}\mathcal{T}_j(z)\ge\frac{d\tau}{n}\right]\le O\left(\frac{1}{n^2}\right). Pr j ∈ [ d ] ∑ T j ( z ) ≥ n d τ ≤ O ( n 2 1 ) .
Analysis of the test in the IN case
This section is devoted to the proof of Theorem 3.8, which states that T ( x i ) ≥ d τ / n \mathcal{T}(x_i)\ge d\tau/n T ( x i ) ≥ d τ / n with probability at least Ω ( 1 / n ) \Omega(1/n) Ω ( 1/ n ) . Throughout this section we let E [ T j ( x i ) ∣ X , s ] \mathbb{E}[\mathcal{T}_j(x_i)\mid X,s] E [ T j ( x i ) ∣ X , s ] denote the random variable given by sampling a realization X X X and s s s of X \boldsymbol{X} X and s s s , and returning E [ T j ( x i ) ∣ X = X , s = s ] \mathbb{E}[\mathcal{T}_j(x_i)\mid X=X,s=s] E [ T j ( x i ) ∣ X = X , s = s ] . Additionally, for random variables w w w and k k k , let w ∣ k w\mid_k w ∣ k denote the random variable given by sampling a realization k k k of k k k and then sampling a realization w w w from the distribution of w w w conditioned on the event that k = k k=k k = k . Before formally stating the claims and proofs, we provide some intuition for the behavior of E [ T j ( x i ) ∣ X , s ] \mathbb{E}[T_j(x_i)\mid X,s] E [ T j ( x i ) ∣ X , s ] for fixed j ∈ [ d ] j\in[d] j ∈ [ d ] . It will be convenient to use the following conjugate prior property of the scaled-inverse chi-squared distribution:
Fact 3.9 (Conjugate prior property). Let σ 2 ∼ inv χ 2 ( ν , τ 2 ) \sigma^2\sim\operatorname{inv}\chi^2(\nu,\tau^2) σ 2 ∼ inv χ 2 ( ν , τ 2 ) , and X = ( x 1 , … , x n ) ∼ N ( 0 , σ 2 ) ⊗ n X=(x_1,\ldots,x_n)\sim\mathcal{N}(0,\sigma^2)^{\otimes n} X = ( x 1 , … , x n ) ∼ N ( 0 , σ 2 ) ⊗ n , then it holds that:
σ 2 ∣ X ∼ inv χ 2 ( ν + n , ν τ 2 + ∑ i ∈ [ n ] x i 2 ν + n ) . \sigma^2\mid X\sim\operatorname{inv}\chi^2\left(\nu+n,\frac{\nu\tau^2+\sum_{i\in[n]}x_i^2}{\nu+n}\right). σ 2 ∣ X ∼ inv χ 2 ( ν + n , ν + n ν τ 2 + ∑ i ∈ [ n ] x i 2 ) .
Let q j = 1 n ∑ i ∈ [ n ] x i , j 2 q_j=\frac{1}{n}\sum_{i\in[n]}x_{i,j}^2 q j = n 1 ∑ i ∈ [ n ] x i , j 2 denote the empirical variance of X X X in coordinate j j j . Since σ j 2 ∼ inv χ 2 ( 1 , 1 ) \sigma_j^2\sim\operatorname{inv}\chi^2(1,1) σ j 2 ∼ inv χ 2 ( 1 , 1 ) , by Theorem 3.9, conditional on X X X we have σ j 2 ∼ inv χ 2 ( n + 1 , 1 + n q j n + 1 ) \sigma_j^2\sim\operatorname{inv}\chi^2\left(n+1,\frac{1+nq_j}{n+1}\right) σ j 2 ∼ inv χ 2 ( n + 1 , n + 1 1 + n q j ) . Assuming n n n is large, we have that σ j 2 ≈ 1 + n q j 1 + n \sigma_j^2\approx\frac{1+nq_j}{1+n} σ j 2 ≈ 1 + n 1 + n q j with high probability. Thus, we expect that
E [ T j ( x i ) ∣ X , s ] = E [ ( E i [ x i , j 2 ] σ j 2 − 1 ) h ( σ j ) s j ∣ X , s ] ≈ q j − 1 1 + n q j min ( 1 + n q j 1 + n , L ) s j . \begin{aligned}
\mathbb{E}[T_j(x_i)\mid X,s]=\mathbb{E}\left[\left(\frac{\mathbb{E}_i[x_{i,j}^2]}{\sigma_j^2}-1\right)h(\sigma_j)s_j\mid X,s\right] \\
&\approx\frac{q_j-1}{1+nq_j}\min\left(\sqrt{\frac{1+nq_j}{1+n}},L\right)s_j.
\end{aligned} E [ T j ( x i ) ∣ X , s ] = E [ ( σ j 2 E i [ x i , j 2 ] − 1 ) h ( σ j ) s j ∣ X , s ] ≈ 1 + n q j q j − 1 min ( 1 + n 1 + n q j , L ) s j .
where the first equality follows since i i i is independent of X X X and Σ \Sigma Σ , and the second equality follows since E [ x i , j 2 ∣ X ] = q j \mathbb{E}[x_{i,j}^2\mid X]=q_j E [ x i , j 2 ∣ X ] = q j , and by substituting the approximation 1 + n q j 1 + n \frac{1+nq_j}{1+n} 1 + n 1 + n q j for σ j 2 \sigma_j^2 σ j 2 . Inspecting the expression on the right hand side, we see that (ignoring constant factors) there are two salient regimes: First, when q j ≫ 1 q_j\gg1 q j ≫ 1 , the expectation is at least min ( q j , L ) / n \min(\sqrt{q_j},L)/n min ( q j , L ) / n , and second, when q j ≪ 1 q_j\ll1 q j ≪ 1 , algebraic manipulation shows that the expectation is always at least − q j / n -\sqrt{q_j}/n − q j / n . We therefore expect the expectation to have the following behavior:
E [ T j ( x i ) ∣ X , s ] ≈ s j n ⋅ { min ( q j , L ) q j > 1 − q j q j ≤ 1 \mathbb{E}[T_j(x_i)\mid X,s]\approx\frac{s_j}{n}\cdot
\begin{cases}
\min(\sqrt{q_j},L) & q_j>1\\
-\sqrt{q_j} & q_j\le1
\end{cases} E [ T j ( x i ) ∣ X , s ] ≈ n s j ⋅ { min ( q j , L ) − q j q j > 1 q j ≤ 1
Subject to the above heuristic, we see that for each coordinate j j j with q j ≤ 1 q_j\le1 q j ≤ 1 , the expectation is always at least − 1 / n -1/n − 1/ n . Since M \mathcal{M} M can select at most ℓ \ell ℓ coordinates, these coordinates can contribute a total of − ℓ n -\frac{\ell}{n} − n ℓ to the sum. On the other hand, if the coordinates with the k k k largest q j q_j q j are all at least L L L , then, because M \mathcal{M} M is required to select at least a constant fraction of them, they must contribute at least k L n \frac{kL}{n} n k L to the sum. It follows that the expectation is large whenever k L ≫ ℓ ≈ d / log d kL\gg\ell\approx d/\log d k L ≫ ℓ ≈ d / log d , or equivalently when L ≈ d / k L\approx d/k L ≈ d / k . Using the distribution of σ j \sigma_j σ j and X X X , one can show that the k k k largest q j q_j q j are indeed typically at least d / k d/k d / k , which completes proof.
The first step in our proof is Theorem 3.10, which provides a more tractable form for analyzing the expectation of the test conditional on X X X and s s s . While the heuristic analysis above provides intuition by reasoning about the empirical variance q j q_j q j , Theorem 3.10 provides an equivalent representation of the expectation over σ j \sigma_j σ j that exhibits the same qualitative behavior as the heuristic.
Claim 3.10 (Simplifying the expectation). For all j ∈ [ d ] j\in[d] j ∈ [ d ] , the conditional expectation of T j T_j T j satisfies
E [ T j ( x i ) ∣ X , s ] = 1 n ⋅ E [ ( L 1 [ σ j > L ] − h ( σ j ) σ j 2 ) s j ∣ X , s ] . \mathbb{E}[T_j(x_i)\mid X,s]=\frac{1}{n}\cdot\mathbb{E}\left[\left(L\mathbf{1}[\sigma_j>L]-\frac{h(\sigma_j)}{\sigma_j^2}\right)s_j\mid X,s\right]. E [ T j ( x i ) ∣ X , s ] = n 1 ⋅ E [ ( L 1 [ σ j > L ] − σ j 2 h ( σ j ) ) s j ∣ X , s ] . In particular,
E [ T ( x i ) ∣ X , s ] = 1 n ⋅ E [ ∑ j ∈ [ d ] ( L 1 [ σ j > L ] − h ( σ j ) σ j 2 ) s j ∣ X , s ] . \mathbb{E}[T(x_i)\mid X,s]=\frac{1}{n}\cdot\mathbb{E}\left[\sum_{j\in[d]}\left(L\mathbf{1}[\sigma_j>L]-\frac{h(\sigma_j)}{\sigma_j^2}\right)s_j\mid X,s\right]. E [ T ( x i ) ∣ X , s ] = n 1 ⋅ E j ∈ [ d ] ∑ ( L 1 [ σ j > L ] − σ j 2 h ( σ j ) ) s j ∣ X , s .
Proof. Since Σ \Sigma Σ is independent of s s s conditional on X X X , we first analyze the expectation over Σ \Sigma Σ conditional on X X X , and then include the conditioning on s s s at the end of the proof. Let q j = 1 n ∑ i ∈ [ n ] x i , j 2 q_j = \frac{1}{n}\sum_{i\in[n]}x_{i,j}^{2} q j = n 1 ∑ i ∈ [ n ] x i , j 2 be the empirical variance in coordinate j j j . The proof follows from integration by parts. In what follows, we consider a fixed coordinate j ∈ [ d ] j\in[d] j ∈ [ d ] , and omit the subscript j j j from the calculations to reduce notational clutter. We begin by showing the following equation:
E [ σ h ′ ( σ ) ∣ X ] = E [ h ( σ ) ( ( n + 1 ) − 1 + n q σ 2 ) | X ] . (19) \mathbb{E}[\sigma h'(\sigma)\mid X]=\mathbb{E}\left[h(\sigma)\left((n+1)-\frac{1+nq}{\sigma^{2}}\right)\middle|X\right]. \tag*{(19)} E [ σ h ′ ( σ ) ∣ X ] = E [ h ( σ ) ( ( n + 1 ) − σ 2 1 + n q ) X ] . (19)
Recall by Theorem 3.9, the distribution of σ 2 ∣ X \sigma^{2}\mid X σ 2 ∣ X has density p σ 2 ( t ) ∝ t − ( ν / 2 + 1 ) exp ( − ν τ 2 2 t ) p_{\sigma^{2}}(t)\propto t^{-(\nu/2+1)}\exp\left(-\frac{\nu\tau^{2}}{2t}\right) p σ 2 ( t ) ∝ t − ( ν /2 + 1 ) exp ( − 2 t ν τ 2 ) , where ν = n + 1 \nu=n+1 ν = n + 1 and τ 2 = 1 + n q 1 + n \tau^{2}=\frac{1+nq}{1+n} τ 2 = 1 + n 1 + n q . Since the quantity in the expectation in question is σ \sigma σ (as opposed to σ 2 \sigma^{2} σ 2 ), it will be convenient to work with the density of σ ∣ X \sigma\mid X σ ∣ X instead. Let f σ ( s ) f_{\sigma}(s) f σ ( s ) be the density of σ ∣ X \sigma\mid X σ ∣ X . Then, by a change of measure, we have that f σ ( s ) = 2 s p σ 2 ( s 2 ) ∝ s − ( ν + 1 ) exp ( − ν τ 2 2 s 2 ) f_{\sigma}(s)=2sp_{\sigma^{2}}(s^{2})\propto s^{-(\nu+1)}\exp\left(-\frac{\nu\tau^{2}}{2s^{2}}\right) f σ ( s ) = 2 s p σ 2 ( s 2 ) ∝ s − ( ν + 1 ) exp ( − 2 s 2 ν τ 2 ) . Now, we apply integration by parts to the expectation:
E [ σ h ′ ( σ ) ∣ X ] = ∫ s = 0 ∞ s h ′ ( s ) f σ ( s ) d s = [ s f σ ( s ) h ( s ) ] 0 ∞ − ∫ s = 0 ∞ h ( s ) ( s f σ ( s ) ) ′ d s . \mathbb{E}[\sigma h'(\sigma)\mid X]=\int_{s=0}^{\infty}sh'(s)f_{\sigma}(s)\,ds
=\left[ sf_{\sigma}(s)h(s)\right]_{0}^{\infty}-\int_{s=0}^{\infty}h(s)\left(sf_{\sigma}(s)\right)'\,ds. E [ σ h ′ ( σ ) ∣ X ] = ∫ s = 0 ∞ s h ′ ( s ) f σ ( s ) d s = [ s f σ ( s ) h ( s ) ] 0 ∞ − ∫ s = 0 ∞ h ( s ) ( s f σ ( s ) ) ′ d s .
Since h ( s ) ≤ L h(s)\leq L h ( s ) ≤ L and lim s → ∞ s f σ ( s ) = lim s → 0 s f σ ( s ) = 0 \lim_{s\to\infty}sf_{\sigma}(s)=\lim_{s\to0}sf_{\sigma}(s)=0 lim s → ∞ s f σ ( s ) = lim s → 0 s f σ ( s ) = 0 , the boundary term is 0. To handle the remaining term, we use the formula for f σ ( s ) f_{\sigma}(s) f σ ( s ) to explicitly compute the derivative:
( s f σ ( s ) ) ′ = f σ ( s ) ( 1 + n q s 2 − ( n + 1 ) ) . \left(sf_{\sigma}(s)\right)'=f_{\sigma}(s)\left(\frac{1+nq}{s^{2}}-(n+1)\right). ( s f σ ( s ) ) ′ = f σ ( s ) ( s 2 1 + n q − ( n + 1 ) ) .
Substituting in the integral ∫ h ( s ) ( s f σ ( s ) ) ′ d s \int h(s)\left(sf_{\sigma}(s)\right)'\,ds ∫ h ( s ) ( s f σ ( s ) ) ′ d s yields (19) . By algebra, we see that
( n + 1 ) − 1 + n q σ 2 = ( 1 − 1 σ 2 ) − n ( q σ 2 − 1 ) , (n+1)-\frac{1+nq}{\sigma^{2}}=\left(1-\frac{1}{\sigma^{2}}\right)-n\left(\frac{q}{\sigma^{2}}-1\right), ( n + 1 ) − σ 2 1 + n q = ( 1 − σ 2 1 ) − n ( σ 2 q − 1 ) ,
and thus, that
n E [ ( q σ 2 − 1 ) h ( σ ) | X ] = E [ h ( σ ) − σ h ′ ( σ ) − h ( σ ) σ 2 | X ] . n\mathbb{E}\left[\left(\frac{q}{\sigma^{2}}-1\right)h(\sigma)\middle|X\right]=\mathbb{E}\left[h(\sigma)-\sigma h'(\sigma)-\frac{h(\sigma)}{\sigma^{2}}\middle|X\right]. n E [ ( σ 2 q − 1 ) h ( σ ) X ] = E [ h ( σ ) − σ h ′ ( σ ) − σ 2 h ( σ ) X ] .
The statement follows since h ( σ ) − σ h ′ ( σ ) = L 1 [ σ > L ] h(\sigma)-\sigma h'(\sigma)=L\mathbf{1}[\sigma>L] h ( σ ) − σ h ′ ( σ ) = L 1 [ σ > L ] , and since
E [ ( q j σ j 2 − 1 ) h ( σ j ) | X ] s j = E [ E i ∼ [ n ] [ ( x i , j 2 σ j 2 − 1 ) h ( σ j ) | X ] | s ] s j = E [ T j ( x i ) ∣ X , s ] , \mathbb{E}\left[\left(\frac{q_j}{\sigma_j^{2}}-1\right)h(\sigma_j)\middle|X\right]s_j
=\mathbb{E}\left[\mathbb{E}_{i\sim[n]}\left[\left(\frac{x_{i,j}^{2}}{\sigma_j^{2}}-1\right)h(\sigma_j)\middle|X\right]\middle|s\right]s_j
=\mathbb{E}[T_j(x_i)\mid X,s], E [ ( σ j 2 q j − 1 ) h ( σ j ) X ] s j = E [ E i ∼ [ n ] [ ( σ j 2 x i , j 2 − 1 ) h ( σ j ) X ] s ] s j = E [ T j ( x i ) ∣ X , s ] ,
which holds because i ∼ [ n ] i\sim[n] i ∼ [ n ] uniformly and independently of X X X , s s s , and Σ \Sigma Σ . □
In order to show that the conditional expectation is large, we must show that the positive part of the expression in Theorem 3.10 is much larger than the negative part. In line with our heuristic derivation, Theorem 3.11 shows that when L = d / 4 k L=d/4k L = d /4 k , the positive part is Ω ( d ) \Omega(d) Ω ( d ) with constant probability.
Claim 3.11 (Lower bounding the positive part). There exists c > 0 c > 0 c > 0 such that if L = d / 4 k L = d/4k L = d /4 k and k ∈ [ max ( 6 log d , 24 ) , c d ] k \in[\max(6 \log d, 24), cd] k ∈ [ max ( 6 log d , 24 ) , c d ] then
E [ ∑ j ∈ [ d ] L 1 [ σ j > L ] s j ∣ X , s ] ≥ c d \mathbb{E}\left[\left.\sum_{j \in[d]} L \mathbf{1}[\sigma_j > L]s_j\right|X,s\right] \ge cd E j ∈ [ d ] ∑ L 1 [ σ j > L ] s j X , s ≥ c d with probability at least c c c .
Before diving in to the proof, we give a brief overview of the main ideas. Let g = ∑ L 1 [ σ j > L ] s j g = \sum L\mathbf{1}[\sigma_j > L]s_j g = ∑ L 1 [ σ j > L ] s j and μ X , s = E [ g ∣ X , s ] \mu_{X,s} = \mathbb{E}[g \mid X,s] μ X , s = E [ g ∣ X , s ] . Then Theorem 3.11 states that μ X , s ≥ c d \mu_{X,s} \ge cd μ X , s ≥ c d with constant probability. The essence of the proof is the following three observations: First, g g g is bounded above by L d Ld L d . Second, the expectation E [ μ X , s ] = E [ g ] \mathbb{E}[\mu_{X,s}] = \mathbb{E}[g] E [ μ X , s ] = E [ g ] is in the interval [ c d , 2 d ] [cd,2d] [ c d , 2 d ] . And third, since g g g is bounded above by a sum of i.i.d. Bernoulli random variables, Pr [ g ≥ 4 d ] ≤ e − d / 3 L \Pr[g \ge4d] \le e^{-d/3L} Pr [ g ≥ 4 d ] ≤ e − d /3 L . Taken together, these observations imply that μ X , s \mu_{X,s} μ X , s cannot place too much mass above 4 d 4d 4 d , and, since E [ μ X , s ] ∈ [ c d , 2 d ] \mathbb{E}[\mu_{X,s}] \in[cd,2d] E [ μ X , s ] ∈ [ c d , 2 d ] , it must place sufficient mass above c d / 2 cd/2 c d /2 .
Proof. As in the proof sketch above, let g = ∑ L 1 [ σ j > L ] s j g = \sum L\mathbf{1}[\sigma_j > L]s_j g = ∑ L 1 [ σ j > L ] s j and μ X , s = E [ g ∣ X , s ] \mu_{X,s} = \mathbb{E}[g \mid X,s] μ X , s = E [ g ∣ X , s ] . We first prove the bound on the expectation. The upper bound follows since s j = M ( X ) j ≤ 1 s_j = \mathcal{M}(X)_j \le1 s j = M ( X ) j ≤ 1 , and since Pr [ σ j ≥ L ] ≤ 2 / L \Pr[\sigma_j \ge L] \le2/L Pr [ σ j ≥ L ] ≤ 2/ L (because σ 2 ∼ inv χ 2 ( 1 , 1 ) \sigma^2 \sim\operatorname{inv}\chi^2(1,1) σ 2 ∼ inv χ 2 ( 1 , 1 ) ). To see why the lower bound holds, observe that by Theorem A.4 we have that σ ( k ) ≥ d / 4 k \sigma_{(k)} \ge d/4k σ ( k ) ≥ d /4 k with probability at least 1 − 2 / k 1-2/k 1 − 2/ k . Let π \pi π be the permutation ordering ( σ j ) j ∈ [ d ] (\sigma_j)_{j \in[d]} ( σ j ) j ∈ [ d ] . Since s π ( j ) = 1 s_{\pi(j)} = 1 s π ( j ) = 1 for at least k / 4 k/4 k /4 of the j ∈ [ k ] j \in[k] j ∈ [ k ] with probability at least 1 / 3 1/3 1/3 , the union bound yields
∑ j ∈ [ k ] L 1 [ σ π ( j ) > L ] s π ( j ) ≥ ∑ j ∈ [ k ] d 4 k s π ( j ) ≥ d 16 \sum_{j \in[k]} L\mathbf{1}[\sigma_{\pi(j)} > L]s_{\pi(j)}
\ge\sum_{j \in[k]} \frac{d}{4k}s_{\pi(j)}
\ge\frac{d}{16} j ∈ [ k ] ∑ L 1 [ σ π ( j ) > L ] s π ( j ) ≥ j ∈ [ k ] ∑ 4 k d s π ( j ) ≥ 16 d
with probability at least 1 / 4 1/4 1/4 for k ≥ 24 k \ge24 k ≥ 24 , and thus, E [ μ X , s ] = E [ g ] ∈ [ c d , 2 d ] \mathbb{E}[\mu_{X,s}] = \mathbb{E}[g] \in[cd,2d] E [ μ X , s ] = E [ g ] ∈ [ c d , 2 d ] for some constant c > 0 c > 0 c > 0 .
Next, we prove a high probability bound on g g g . Observe that g ≤ ∑ L 1 [ σ j > L ] g \le\sum L\mathbf{1}[\sigma_j > L] g ≤ ∑ L 1 [ σ j > L ] , which is a sum of i.i.d. Bernoulli random variables with mean at most 2 d 2d 2 d . Let B 1 B_1 B 1 denote the event that g ≥ 4 d g \ge4d g ≥ 4 d , and let B 2 B_2 B 2 denote the event that E [ 1 [ B 1 ] ∣ X , s ] ≥ e − d / 6 L \mathbb{E}[\mathbf{1}[B_1] \mid X,s] \ge e^{-d/6L} E [ 1 [ B 1 ] ∣ X , s ] ≥ e − d /6 L . By a Chernoff bound, Pr [ B 1 ] ≤ e − d / 3 L \Pr[B_1] \le e^{-d/3L} Pr [ B 1 ] ≤ e − d /3 L , and thus, by Markov’s inequality, E [ 1 [ B 2 ] ] ≤ e − d / 6 L \mathbb{E}[\mathbf{1}[B_2]] \le e^{-d/6L} E [ 1 [ B 2 ]] ≤ e − d /6 L . In other words, g g g is rarely bigger than 4 d 4d 4 d , and with high probability over X X X and s s s , random variable g ∣ X , s g\mid_{X,s} g ∣ X , s is rarely bigger than 4 d 4d 4 d .
We now argue that μ X , s \mu_{X,s} μ X , s must be at least Ω ( d ) \Omega(d) Ω ( d ) with constant probability over X X X and s s s .
c d ≤ E [ μ X , s ] ≤ E [ μ X , s 1 [ B 2 ‾ ] ] + L d e − d / 6 L ≤ E [ E [ g 1 [ B 1 ] ∣ X , s ] ] + L d E [ E [ 1 [ B 1 ] ∣ X , s ] 1 [ B 2 ‾ ] ] + L d e − d / 6 L ≤ L d e − d / 6 L ≤ E [ μ X , s 1 [ μ X , s < c ′ d ] ] + 4 d E [ 1 [ μ X , s > c ′ d ] ] + 2 L d e − k / 6 for any c ′ > 0 \begin{aligned}
cd \le\mathbb{E}[\mu_{X,s}]
\le\mathbb{E}[\mu_{X,s}\mathbf{1}[\overline{B_2}]] + Ld e^{-d/6L} \\
&\le\mathbb{E}\left[\mathbb{E}[g\mathbf{1}[B_1]\mid X,s]\right] + Ld\,\mathbb{E}\left[\mathbb{E}[\mathbf{1}[B_1]\mid X,s]\mathbf{1}[\overline{B_2}]\right] + Ld e^{-d/6L} \\
&\le Ld e^{-d/6L} \\
&\le\mathbb{E}[\mu_{X,s}\mathbf{1}[\mu_{X,s}<c'd]] + 4d\,\mathbb{E}[\mathbf{1}[\mu_{X,s}>c'd]] + 2Ld e^{-k/6}
\qquad\text{for any } c' > 0
\end{aligned} c d ≤ E [ μ X , s ] ≤ E [ μ X , s 1 [ B 2 ]] + L d e − d /6 L ≤ E [ E [ g 1 [ B 1 ] ∣ X , s ] ] + L d E [ E [ 1 [ B 1 ] ∣ X , s ] 1 [ B 2 ] ] + L d e − d /6 L ≤ L d e − d /6 L ≤ E [ μ X , s 1 [ μ X , s < c ′ d ]] + 4 d E [ 1 [ μ X , s > c ′ d ]] + 2 L d e − k /6 for any c ′ > 0
≤ 2 c ′ d + 4 d Pr [ μ X , s > c ′ d ] , \le2c'd + 4d\Pr[\mu_{X,s}>c'd], ≤ 2 c ′ d + 4 d Pr [ μ X , s > c ′ d ] ,
where the final inequality holds since L = d / 4 k L = d/4k L = d /4 k and k ≥ 6 log ( d ) k \ge6\log(d) k ≥ 6 log ( d ) . Setting c ′ = c / 4 c' = c/4 c ′ = c /4 and rearranging terms, we see that μ X , s ≥ c d / 4 \mu_{X,s} \ge cd/4 μ X , s ≥ c d /4 with probability at least c / 8 c/8 c /8 . □
To complete our analysis of the conditional expectation, we prove Theorem 3.12, which states that the negative terms of the conditional expectation cannot decrease the overall sum by much more than ℓ d \sqrt{\ell d} ℓ d . We note that this analysis diverges slightly from the heuristic bound of ℓ \ell ℓ derived at the start of the section; however, the deviation is minor—for ℓ ≈ d / log d \ell\approx d/\log d ℓ ≈ d / log d we have that ℓ d ≈ ℓ log d \sqrt{\ell d} \approx\ell\sqrt{\log d} ℓ d ≈ ℓ log d .
Claim 3.12 (Upper bounding the negative part). For all C > 0 C > 0 C > 0
E [ ∣ ∑ j ∈ [ d ] h ( σ j ) σ j 2 s j ∣ X , s ] ≤ C ℓ d \mathbb{E}\left[\left.\left|\sum_{j \in[d]} \frac{h(\sigma_j)}{\sigma_j^2}s_j\right| \, X,s\right.\right] \le C\sqrt{\ell d} E j ∈ [ d ] ∑ σ j 2 h ( σ j ) s j X , s ≤ C ℓ d with probability at least 1 − 1 / C 1 - 1/C 1 − 1/ C .
Proof. Since h ( σ j ) ≤ σ j h(\sigma_j) \le\sigma_j h ( σ j ) ≤ σ j , and E [ σ j − 2 ] < ∞ \mathbb{E}[\sigma_j^{-2}] < \infty E [ σ j − 2 ] < ∞ , we can bound the expectation of the negative terms over X X X and s s s using Cauchy–Schwarz and Jensen’s inequality
E [ ∑ j ∈ [ d ] h ( σ j ) σ j 2 s j ] ≤ E [ ℓ ∑ j ∈ [ d ] σ j − 2 ] ≤ ℓ ∑ j ∈ [ d ] E [ σ j − 2 ] = ℓ d , \mathbb{E}\left[\sum_{j \in[d]} \frac{h(\sigma_j)}{\sigma_j^2}s_j\right] \le\mathbb{E}\left[\sqrt{\ell}\sqrt{\sum_{j \in[d]} \sigma_j^{-2}}\right] \le\sqrt{\ell\sum_{j \in[d]} \mathbb{E}[\sigma_j^{-2}]} = \sqrt{\ell d}, E j ∈ [ d ] ∑ σ j 2 h ( σ j ) s j ≤ E ℓ j ∈ [ d ] ∑ σ j − 2 ≤ ℓ j ∈ [ d ] ∑ E [ σ j − 2 ] = ℓ d ,
where the final inequality follows because σ j − 2 \sigma_j^{-2} σ j − 2 follows a χ 1 2 \chi_1^2 χ 1 2 distribution. By Markov’s inequality over X X X and s s s , the negative terms are at most C ℓ d C\sqrt{\ell d} C ℓ d with probability at least 1 − 1 / C 1 - 1/C 1 − 1/ C .
Theorems Theorems 3.10 to 3.12 show that the conditional expectation is Ω ( d / n ) \Omega(d/n) Ω ( d / n ) with constant probability. However, in order to show that the test itself is large with constant probability over the randomness of both Σ \Sigma Σ and X X X , we require a bound on the conditional variance. Theorem 3.13 states that the variance of the test conditional on X X X is typically less than L d / n Ld/n L d / n .
Claim 3.13 (Bounding the variance). For all C > 0 C > 0 C > 0
Var [ E [ T ( x i ) ∣ Σ ] ∣ X , s ] ≤ 4 C L d n \operatorname{Var}[\mathbb{E}[\mathcal{T}(x_i) \mid\Sigma] \mid X,s] \le\frac{4CLd}{n} Var [ E [ T ( x i ) ∣ Σ ] ∣ X , s ] ≤ n 4 C L d with probability at least 1 − 1 / C 1 - 1/C 1 − 1/ C .
Proof. Since the σ j 2 \sigma_j^2 σ j 2 ’s are sampled independently for each j ∈ [ d ] j \in[d] j ∈ [ d ] , we have that conditioned on X X X and s s s , the terms T j ( x i ) \mathcal{T}_j(x_i) T j ( x i ) are independent. Thus,
Var Σ [ E i [ T ( x i ) ∣ Σ ] ∣ X , s ] = ∑ j ∈ [ d ] Var [ ( q j σ j 2 − 1 ) h ( σ j ) s j ∣ X , s ] ≤ ∑ j ∈ [ d ] E Σ [ ( q j σ j 2 − 1 ) 2 h ( σ j ) 2 ∣ X ] . \begin{aligned}
\operatorname{Var}_{\Sigma}\left[\mathbb{E}_{i}[\mathcal{T}(x_i) \mid\Sigma] \mid X,s\right] = \sum_{j \in[d]} \operatorname{Var}\left[\left.\left(\frac{q_j}{\sigma_j^2}-1\right)h(\sigma_j)s_j \right| X,s\right] \\
&\le\sum_{j \in[d]} \mathbb{E}_{\Sigma}\left[\left.\left(\frac{q_j}{\sigma_j^2}-1\right)^2 h(\sigma_j)^2 \right| X\right].
\end{aligned} Var Σ [ E i [ T ( x i ) ∣ Σ ] ∣ X , s ] = j ∈ [ d ] ∑ Var [ ( σ j 2 q j − 1 ) h ( σ j ) s j X , s ] ≤ j ∈ [ d ] ∑ E Σ ( σ j 2 q j − 1 ) 2 h ( σ j ) 2 X .
Taking the expectation over X X X and s s s and swapping the order of expectation we see that,
E X , s [ Var Σ [ E i [ T ( x i ) ∣ Σ ] ∣ X , s ] ] ≤ ∑ j ∈ [ d ] E Σ E X [ ( q j σ j 2 − 1 ) 2 h ( σ j ) 2 ∣ Σ ] ≤ ∑ j ∈ [ d ] E Σ [ 2 n ⋅ h ( σ j ) 2 ] ≤ 4 d L n . \begin{aligned}
\mathbb{E}_{X,s}\left[\operatorname{Var}_{\Sigma}\left[\mathbb{E}_{i}[\mathcal{T}(x_i) \mid\Sigma] \mid X,s\right]\right] \le\sum_{j \in[d]} \mathbb{E}_{\Sigma}\mathbb{E}_{X}\left[\left.\left(\frac{q_j}{\sigma_j^2}-1\right)^2 h(\sigma_j)^2 \right| \Sigma\right] \\
&\le\sum_{j \in[d]} \mathbb{E}_{\Sigma}\left[\frac{2}{n}\cdot h(\sigma_j)^2\right] \\
&\le\frac{4dL}{n}.
\end{aligned} E X , s [ Var Σ [ E i [ T ( x i ) ∣ Σ ] ∣ X , s ] ] ≤ j ∈ [ d ] ∑ E Σ E X ( σ j 2 q j − 1 ) 2 h ( σ j ) 2 Σ ≤ j ∈ [ d ] ∑ E Σ [ n 2 ⋅ h ( σ j ) 2 ] ≤ n 4 d L .
The last inequality follows from the fact that E [ h ( σ j ) 2 ] ≤ 2 L \mathbb{E}[h(\sigma_j)^2] \le2L E [ h ( σ j ) 2 ] ≤ 2 L (see the proof of Theorem 3.7). Applying Markov’s inequality completes the proof of the claim.
We now complete the proof of our main lemma, which says that Pr [ T ( x i ) ≥ d τ / n ] = Ω ( 1 / n ) \Pr[\mathcal{T}(x_i) \ge d\tau/n] = \Omega(1/n) Pr [ T ( x i ) ≥ d τ / n ] = Ω ( 1/ n ) .
Proof of Theorem 3.8. Let c > 0 c > 0 c > 0 be the constant from Theorem 3.11, and define G G G as the event that
E [ T ( x i ) ∣ X , s ] ≥ c d 2 n and Var [ E [ T ( x i ) ∣ Σ ] ∣ X , s ] ≤ 16 L d c n . \mathbb{E}[\mathcal{T}(x_i) \mid X,s] \ge\frac{cd}{2n}
\quad\text{and}\quad
\operatorname{Var}[\mathbb{E}[\mathcal{T}(x_i) \mid\Sigma] \mid X,s] \le\frac{16Ld}{cn}. E [ T ( x i ) ∣ X , s ] ≥ 2 n c d and Var [ E [ T ( x i ) ∣ Σ ] ∣ X , s ] ≤ c n 16 L d .
Let μ Σ = E [ T ( x i ) ∣ Σ , X , s ] \mu_\Sigma= \mathbb{E}[\mathcal{T}(x_i) \mid\Sigma,X,s] μ Σ = E [ T ( x i ) ∣ Σ , X , s ] , and let E E E be the event that
μ Σ ≥ 1 2 E [ μ Σ ∣ X , s ] = 1 2 E Σ , i [ T ( x i ) ∣ X , s ] . \mu_\Sigma\ge\frac{1}{2}\mathbb{E}[\mu_\Sigma\mid X,s] = \frac{1}{2}\mathbb{E}_{\Sigma,i}[\mathcal{T}(x_i) \mid X,s]. μ Σ ≥ 2 1 E [ μ Σ ∣ X , s ] = 2 1 E Σ , i [ T ( x i ) ∣ X , s ] .
Since conditional on G G G we have E [ T ( x i ) ∣ X , s ] > 0 \mathbb{E}[\mathcal{T}(x_i) \mid X,s] > 0 E [ T ( x i ) ∣ X , s ] > 0 , we can apply Paley-Zygmund conditional on G G G to obtain that,
E Σ [ 1 E ∣ X , s ] G ≥ 1 4 E Σ [ μ Σ ∣ X , s ] G 2 E Σ [ μ Σ 2 ∣ X , s ] G = 1 4 E Σ [ μ Σ ∣ X , s ] G 2 Var [ μ Σ ∣ X , s ] G + E Σ [ μ Σ ∣ X , s ] G 2 ≥ 1 6 . \mathbb{E}_{\Sigma}[\mathbf{1}_E \mid X,s]_G
\ge\frac{1}{4}\frac{\mathbb{E}_{\Sigma}[\mu_\Sigma\mid X,s]_G^2}{\mathbb{E}_{\Sigma}[\mu_\Sigma^2 \mid X,s]_G}
= \frac{1}{4}\frac{\mathbb{E}_{\Sigma}[\mu_\Sigma\mid X,s]_G^2}{\operatorname{Var}[\mu_\Sigma\mid X,s]_G+\mathbb{E}_{\Sigma}[\mu_\Sigma\mid X,s]_G^2}
\ge\frac{1}{6}. E Σ [ 1 E ∣ X , s ] G ≥ 4 1 E Σ [ μ Σ 2 ∣ X , s ] G E Σ [ μ Σ ∣ X , s ] G 2 = 4 1 Var [ μ Σ ∣ X , s ] G + E Σ [ μ Σ ∣ X , s ] G 2 E Σ [ μ Σ ∣ X , s ] G 2 ≥ 6 1 .
where the final inequality follows since by definition of G G G and μ Σ \mu_\Sigma μ Σ , and our setting of k k k ,
Var [ μ Σ ∣ X , s ] G E Σ [ μ Σ ∣ X , s ] G 2 = Var [ E [ T ( x i ) ∣ Σ ] ∣ X , s ] G E Σ , i [ T ( x i ) ∣ X , s ] G 2 ≤ 16 n c 3 k ≤ 1 2 . \frac{\operatorname{Var}[\mu_\Sigma\mid X,s]_G}{\mathbb{E}_{\Sigma}[\mu_\Sigma\mid X,s]_G^2}
=
\frac{\operatorname{Var}[\mathbb{E}[\mathcal{T}(x_i) \mid\Sigma] \mid X,s]_G}{\mathbb{E}_{\Sigma,i}[\mathcal{T}(x_i) \mid X,s]_G^2}
\le\frac{16n}{c^3 k} \le\frac{1}{2}. E Σ [ μ Σ ∣ X , s ] G 2 Var [ μ Σ ∣ X , s ] G = E Σ , i [ T ( x i ) ∣ X , s ] G 2 Var [ E [ T ( x i ) ∣ Σ ] ∣ X , s ] G ≤ c 3 k 16 n ≤ 2 1 .
Taking the expectation over s s s and X X X , we see that E X , s , Σ [ 1 E ∣ G ] ≥ 1 / 6 \mathbb{E}_{X,s,\Sigma}[\mathbf{1}_E \mid G] \ge1/6 E X , s , Σ [ 1 E ∣ G ] ≥ 1/6 .
Next we argue that Pr [ G ] ≥ c / 2 \Pr[G] \ge c/2 Pr [ G ] ≥ c /2 . By Theorem 3.10, the random variable E [ T ( x i ) ∣ X , s ] \mathbb{E}[\mathcal{T}(x_i) \mid X,s] E [ T ( x i ) ∣ X , s ] can be decomposed into a positive part and a negative part. By Theorem 3.11, the positive part is at least c d cd c d with probability at least c c c , and by Theorem 3.12, the negative part is at most 4 c − 1 ℓ d 4c^{-1}\sqrt{\ell}d 4 c − 1 ℓ d with probability at least 1 − c / 4 1-c/4 1 − c /4 , which, since ℓ ≤ d / C log d \ell\le d/C\log d ℓ ≤ d / C log d and C > 0 C > 0 C > 0 is large enough, is at most c d / 2 cd/2 c d /2 . If both of these events occur then the expectation is at least c d / 2 n cd/2n c d /2 n . Additionally, by Theorem 3.13, the variance is at most 16 c − 1 L d / n 16c^{-1}Ld/n 16 c − 1 L d / n with probability at least 1 − c / 4 1-c/4 1 − c /4 . By the union bound G G G occurs with probability at least c / 2 c/2 c /2 .
To complete the proof, fix τ ∈ ( 0 , c / 4 ) \tau\in(0,c/4) τ ∈ ( 0 , c /4 ) and let A 1 A_1 A 1 be the event that T ( x i ) ≥ d τ / n \mathcal{T}(x_i) \ge d\tau/n T ( x i ) ≥ d τ / n . There exists w = w ( X , s , Σ ) ∈ [ n ] w = w(X,s,\Sigma) \in[n] w = w ( X , s , Σ ) ∈ [ n ] such that T ( x w ) ≥ E i [ T ( x i ) ∣ X , s , Σ ] \mathcal{T}(x_w) \ge\mathbb{E}_i[\mathcal{T}(x_i) \mid X,s,\Sigma] T ( x w ) ≥ E i [ T ( x i ) ∣ X , s , Σ ] . Let A 2 A_2 A 2 be the event that i = w i=w i = w . Then conditional on G G G we have 1 A 1 1 A 2 ≥ 1 E 1 A 2 \mathbf{1}_{A_1}\mathbf{1}_{A_2} \ge\mathbf{1}_E\mathbf{1}_{A_2} 1 A 1 1 A 2 ≥ 1 E 1 A 2 . Hence,
Pr X , s , Σ , i [ T ( x i ) ≥ d τ n ] ≥ E X , s , Σ , i [ 1 A 1 1 A 2 ] ≥ c 2 E X , s , Σ [ 1 E E i [ 1 A 2 ∣ X , s , Σ ] ∣ G ] ≥ c 2 n E X , s , Σ [ 1 E ∣ G ] = c 12 n , \Pr_{X,s,\Sigma,i}\left[\mathcal{T}(x_i) \ge\frac{d\tau}{n}\right]
\ge\mathbb{E}_{X,s,\Sigma,i}[\mathbf{1}_{A_1}\mathbf{1}_{A_2}]
\ge\frac{c}{2}\mathbb{E}_{X,s,\Sigma}\left[\mathbf{1}_E\mathbb{E}_i[\mathbf{1}_{A_2}\mid X,s,\Sigma]\mid G\right]
\ge\frac{c}{2n}\mathbb{E}_{X,s,\Sigma}[\mathbf{1}_E\mid G]
= \frac{c}{12n}, X , s , Σ , i Pr [ T ( x i ) ≥ n d τ ] ≥ E X , s , Σ , i [ 1 A 1 1 A 2 ] ≥ 2 c E X , s , Σ [ 1 E E i [ 1 A 2 ∣ X , s , Σ ] ∣ G ] ≥ 2 n c E X , s , Σ [ 1 E ∣ G ] = 12 n c ,
where the second inequality follows since Pr [ G ] ≥ c / 2 \Pr[G] \ge c/2 Pr [ G ] ≥ c /2 , and since 1 E \mathbf{1}_E 1 E is independent of i i i , and the third inequality follows since Pr [ i = w ] = 1 / n \Pr[i=w] = 1/n Pr [ i = w ] = 1/ n . ∎
Lower bound for mean estimation with Mahalanobis error
In this section we argue that private mean estimation in d d d dimensions with error relative to the covariance Σ \Sigma Σ is impossible with less than d d d samples. Let Σ † \Sigma^\dagger Σ † denote the pseudo-inverse of a positive semidefinite matrix Σ \Sigma Σ . For a vector y ∈ R d y \in\mathbb{R}^d y ∈ R d , the Mahalanobis norm of y y y relative to Σ \Sigma Σ is defined by
d Σ ( y ) = { y T Σ † y y ∈ Span ( Σ ) ∞ otherwise d_{\Sigma}(y) =
\begin{cases}
\sqrt{y^{\mathsf{T}}\Sigma^\dagger y} & y \in\operatorname{Span}(\Sigma) \\
\infty& \text{otherwise}
\end{cases} d Σ ( y ) = { y T Σ † y ∞ y ∈ Span ( Σ ) otherwise
Our lower bound uses the following prior P r e l \mathcal{P}_{\mathrm{rel}} P rel over instances ( μ , Σ ) (\mu,\Sigma) ( μ , Σ ) :
( μ , Σ ) ∼ P r e l ( d ) ⟺ { μ ∼ N ( 0 , I d ) Σ = I d − v v T where v ∼ { v : ∥ v ∥ 2 = 1 } uniformly. (20) (\mu,\Sigma) \sim\mathcal{P}_{\mathrm{rel}}(d) \Longleftrightarrow
\begin{cases}
\mu\sim\mathcal{N}(0,I_d) \\
\Sigma= I_d - vv^{\mathsf{T}} \text{ where } v \sim\{v : \lVert v\rVert_2 = 1\}\text{ uniformly.}
\end{cases} \tag*{(20)} ( μ , Σ ) ∼ P rel ( d ) ⟺ { μ ∼ N ( 0 , I d ) Σ = I d − v v T where v ∼ { v : ∥ v ∥ 2 = 1 } uniformly. (20)
We note that for instances Σ \Sigma Σ in the support of P r e l \mathcal{P}_{\mathrm{rel}} P rel and any vector y ∈ R d y \in\mathbb{R}^d y ∈ R d we either have d Σ ( y ) = ∥ y ∥ 2 d_{\Sigma}(y) = \lVert y\rVert_2 d Σ ( y ) = ∥ y ∥ 2 if y ∈ Span ( Σ ) y \in\operatorname{Span}(\Sigma) y ∈ Span ( Σ ) , or d Σ ( y ) = ∞ d_{\Sigma}(y) = \infty d Σ ( y ) = ∞ otherwise.
Theorem 4.1. There exists a constant C > 0 C > 0 C > 0 such that for all d , n ∈ N d,n \in\mathbb{N} d , n ∈ N and ε , δ ≥ 0 \varepsilon,\delta\ge0 ε , δ ≥ 0 , if d ≥ n + 2 d \ge n + 2 d ≥ n + 2 then every ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP mechanism M \mathcal{M} M satisfies
\underset{\substack{(\mu,\Sigma)\sim\mathcal{P}_{\mathrm{rel}}\\ X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n}}{\Pr}\left[d_{\Sigma}(\mathcal{M}(X)-\mu)<\infty\right] \le n\delta.}
The intuition behind the proof, is that conditioned on X − μ X-\mu X − μ , the span of Σ \Sigma Σ is composed of Span ( X − μ ) \operatorname{Span}(X-\mu) Span ( X − μ ) and a uniformly random d − n − 1 d-n-1 d − n − 1 dimensional subspace of Span ( X − μ ) ⊥ \operatorname{Span}(X-\mu)^\perp Span ( X − μ ) ⊥ . If the algorithm’s output is not in Span ( X − μ ) \operatorname{Span}(X-\mu) Span ( X − μ ) , then with probability 1 over the posterior sampling of v v v , its Mahalanobis error is infinite. Thus, the algorithm’s output must be within Span ( X − μ ) \operatorname{Span}(X-\mu) Span ( X − μ ) , from which we derive a privacy violation.
Proof. We show a contradiction to ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP by constructing an attack that distinguishes between z ∼ N ( μ , Σ ) z \sim\mathcal{N}(\mu,\Sigma) z ∼ N ( μ , Σ ) and x i x_i x i , where i ∼ [ n ] i \sim[n] i ∼ [ n ] uniformly. The test uses the output of the mechanism y y y , as well as the other n − 1 n-1 n − 1 datapoints X − i X_{-i} X − i . For all z , μ ∈ R d z,\mu\in\mathbb{R}^d z , μ ∈ R d and datasets X ∈ ( R d ) n − 1 X \in(\mathbb{R}^d)^{n-1} X ∈ ( R d ) n − 1 define
S X , μ ( z ) = Span { x 1 − μ , … , x n − 1 − μ , z − μ } ∖ Span { x 1 − μ , … , x n − 1 − μ } . S_{X,\mu}(z) = \operatorname{Span}\{x_1-\mu,\ldots,x_{n-1}-\mu,z-\mu\}\setminus\operatorname{Span}\{x_1-\mu,\ldots,x_{n-1}-\mu\}. S X , μ ( z ) = Span { x 1 − μ , … , x n − 1 − μ , z − μ } ∖ Span { x 1 − μ , … , x n − 1 − μ } .
And define the test T X , μ , y ( z ) = 1 [ y − μ ∈ S X , μ ( z ) ] T_{X,\mu,y}(z)=\mathbb{1}[y-\mu\in S_{X,\mu}(z)] T X , μ , y ( z ) = 1 [ y − μ ∈ S X , μ ( z )] . In the remainder of the proof, we will omit the subscripts X X X , μ \mu μ and y y y , since they will be clear from context.
Let ( μ , Σ ) ∼ P r e l (\mu,\Sigma)\sim\mathcal{P}_{\mathrm{rel}} ( μ , Σ ) ∼ P rel , X ∼ N ( μ , Σ ) ⊗ n X\sim\mathcal{N}(\mu,\Sigma)^{\otimes n} X ∼ N ( μ , Σ ) ⊗ n , y ∼ M ( S ) y\sim\mathcal{M}(S) y ∼ M ( S ) , z ∼ N ( μ , Σ ) z\sim\mathcal{N}(\mu,\Sigma) z ∼ N ( μ , Σ ) , and i ∼ [ n ] i\sim[n] i ∼ [ n ] uniformly and independently. Let G G G be the event that d Σ ( y − μ ) < ∞ d_{\Sigma}(y-\mu)<\infty d Σ ( y − μ ) < ∞ and let E E E be the event that y − μ ∈ Span ( X − μ ) y-\mu\in\operatorname{Span}(X-\mu) y − μ ∈ Span ( X − μ ) . The key idea behind our proof is that Pr [ G ] = Pr [ E ] \Pr[G]=\Pr[E] Pr [ G ] = Pr [ E ] , that is, the probability that the Mahalanobis error is finite is exactly the probability that y − μ y-\mu y − μ is in the span of X − μ X-\mu X − μ . To see why this is, observe that
E [ 1 G ] = E [ 1 G 1 E ] + E [ 1 G 1 E ‾ ] = E [ 1 E ] + E X , y , μ [ E v [ 1 G ∣ X , y , μ ] 1 E ‾ ] = E [ 1 E ] \mathbb{E}[\mathbb{1}_G]=\mathbb{E}[\mathbb{1}_G\mathbb{1}_E]+\mathbb{E}[\mathbb{1}_G\mathbb{1}_{\overline{E}}]
=\mathbb{E}[\mathbb{1}_E]+\mathbb{E}_{X,y,\mu}\left[\mathbb{E}_{v}\left[\mathbb{1}_G\mid X,y,\mu\right]\mathbb{1}_{\overline{E}}\right]
=\mathbb{E}[\mathbb{1}_E] E [ 1 G ] = E [ 1 G 1 E ] + E [ 1 G 1 E ] = E [ 1 E ] + E X , y , μ [ E v [ 1 G ∣ X , y , μ ] 1 E ] = E [ 1 E ]
where the second equality follows since 1 E = 1 \mathbb{1}_E=1 1 E = 1 implies 1 G = 1 \mathbb{1}_G=1 1 G = 1 . The final equality follows since conditional on y y y , X X X , and μ \mu μ such that 1 E ‾ = 1 \mathbb{1}_{\overline{E}}=1 1 E = 1 , over the random sampling of the direction v v v (see (20) ), we have ⟨ v , y − μ ⟩ ≠ 0 \langle v,y-\mu\rangle\ne0 ⟨ v , y − μ ⟩ = 0 with probability 1, and thus d Σ ( y − μ ) = ∞ d_{\Sigma}(y-\mu)=\infty d Σ ( y − μ ) = ∞ , implying E v [ 1 G ∣ X , y , μ ] = 0 \mathbb{E}_v[\mathbb{1}_G\mid X,y,\mu]=0 E v [ 1 G ∣ X , y , μ ] = 0 . IN case. Since n < d n < d n < d the data { x i − μ } i ∈ [ n ] \{x_i-\mu\}_{i\in[n]} { x i − μ } i ∈ [ n ] are linearly independent with probability 1, and thus ⋂ i ∈ [ n ] Span ( X − i − μ ) = { 0 } \bigcap_{i\in[n]} \operatorname{Span}(X_{-i}-\mu)=\{0\} ⋂ i ∈ [ n ] Span ( X − i − μ ) = { 0 } . It follows that there exists some random variable w ∈ [ n ] w\in[n] w ∈ [ n ] , such that when y ≠ μ y\ne\mu y = μ and conditional on E E E , we have y − μ ∉ Span ( X − w − μ ) y-\mu\notin\operatorname{Span}(X_{-w}-\mu) y − μ ∈ / Span ( X − w − μ ) , or equivalently T X − w , μ ( x w ) = 1 T_{X_{-w},\mu}(x_w)=1 T X − w , μ ( x w ) = 1 , with probability 1. Since i = w i=w i = w with probability 1 / n 1/n 1/ n independently of y y y , X X X , u u u and Σ \Sigma Σ , we obtain,
Pr [ T X − i , μ ( x i ) = 1 ] ≥ 1 n Pr [ T X − w , μ ( x w ) = 1 ∣ E ∩ { y ≠ μ } ] Pr [ E ∩ { y ≠ μ } ] ≥ Pr [ E ] − Pr [ y = μ ] n = Pr [ G ] n , \begin{aligned}
\Pr[T_{X_{-i},\mu}(x_i)=1]\ge\frac{1}{n}\Pr[T_{X_{-w},\mu}(x_w)=1\mid E\cap\{y\ne\mu\}]\Pr[E\cap\{y\ne\mu\}] \\
&\ge\frac{\Pr[E]-\Pr[y=\mu]}{n}=\frac{\Pr[G]}{n},
\end{aligned} Pr [ T X − i , μ ( x i ) = 1 ] ≥ n 1 Pr [ T X − w , μ ( x w ) = 1 ∣ E ∩ { y = μ }] Pr [ E ∩ { y = μ }] ≥ n Pr [ E ] − Pr [ y = μ ] = n Pr [ G ] ,
where the final equality holds since Pr [ y = μ ] = 0 \Pr[y=\mu]=0 Pr [ y = μ ] = 0 and Pr [ E ] = Pr [ G ] \Pr[E]=\Pr[G] Pr [ E ] = Pr [ G ] .
OUT case. Since n ≤ d − 2 n\le d-2 n ≤ d − 2 , for fixed y y y , μ \mu μ , X X X we have z − μ ∉ Span { X − μ , y − μ } z-\mu\notin\operatorname{Span}\{X-\mu,y-\mu\} z − μ ∈ / Span { X − μ , y − μ } with probability 1 over the randomness of z z z . Thus, Pr [ T X − i , μ ( z ) = 1 ] = 0 \Pr[T_{X_{-i},\mu}(z)=1]=0 Pr [ T X − i , μ ( z ) = 1 ] = 0 .
Bounding the accuracy. We use the definition of ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP to bound the accuracy of M \mathcal{M} M .
Pr [ G ] n ≤ Pr [ T X − i , μ ( x i ) = 1 ] ≤ e ε Pr [ T X − i , μ ( x i ) = 1 ] + δ using T ( z ) ≈ ( ε , δ ) T ( x i ) = δ . \begin{aligned}
\frac{\Pr[G]}{n}\le\Pr[T_{X_{-i},\mu}(x_i)=1] \\
&\le e^\varepsilon\Pr[T_{X_{-i},\mu}(x_i)=1]+\delta\qquad\text{using }T(z)\approx_{(\varepsilon,\delta)}T(x_i) \\
&=\delta.
\end{aligned} n Pr [ G ] ≤ Pr [ T X − i , μ ( x i ) = 1 ] ≤ e ε Pr [ T X − i , μ ( x i ) = 1 ] + δ using T ( z ) ≈ ( ε , δ ) T ( x i ) = δ .
Rearranging terms, we see that Pr [ d Σ ( y − μ ) < ∞ ] ≤ n δ . \Pr[d_{\Sigma}(y-\mu)<\infty]\le n\delta. Pr [ d Σ ( y − μ ) < ∞ ] ≤ n δ .
References
Concentration Results
Lemma A.1 (Concentration of the empirical covariance). Let Σ \Sigma Σ be a rank-k k k orthogonal projection in R d \mathbb{R}^{d} R d , and X ∼ N ( 0 , Σ ) ⊗ n \mathbf{X} \sim\mathcal{N}(0,\Sigma)^{\otimes n} X ∼ N ( 0 , Σ ) ⊗ n . There is a numerical constant c > 0 c > 0 c > 0 , such that, if n ≤ c k n \le ck n ≤ c k , then
k 2 n P X ⪯ Σ ^ X ⪯ 2 k n P X \frac{k}{2n}P_{\mathbf{X}} \preceq\widehat{\Sigma}_{\mathbf{X}} \preceq\frac{2k}{n}P_{\mathbf{X}} 2 n k P X ⪯ Σ X ⪯ n 2 k P X with probability at least 1 − 2 exp ( − c k ) 1 - 2\exp(-ck) 1 − 2 exp ( − c k ) .
Proof of Theorem A.1. The result is a direct consequence of standard results on the concentration of eigenvalues of matrices with i.i.d. standard gaussian entries. Indeed, the empirical covariance matrix and the projector on Span ( X ) \operatorname{Span}(\mathbf{X}) Span ( X ) write (for n ≤ k ≤ d n \le k \le d n ≤ k ≤ d )
Σ ^ X = 1 n X X T = ∑ i ∈ [ n ] σ i 2 ( X ) n d i ( X ) d i ( X ) T and P X = ∑ i ∈ [ n ] d i ( X ) d i ( X ) T , \widehat{\Sigma}_{\mathbf{X}} = \frac{1}{n}\mathbf{X}\mathbf{X}^{\mathsf{T}} = \sum_{i\in[n]} \frac{\sigma_i^2(\mathbf{X})}{n}d_i(\mathbf{X})d_i(\mathbf{X})^{\mathsf{T}} \quad\text{and} \quad P_{\mathbf{X}} = \sum_{i\in[n]} d_i(\mathbf{X})d_i(\mathbf{X})^{\mathsf{T}}, Σ X = n 1 X X T = i ∈ [ n ] ∑ n σ i 2 ( X ) d i ( X ) d i ( X ) T and P X = i ∈ [ n ] ∑ d i ( X ) d i ( X ) T ,
with ( d i ( X ) ) i ∈ [ n ] ∈ R d (d_i(\mathbf{X}))_{i\in[n]} \in\mathbb{R}^{d} ( d i ( X ) ) i ∈ [ n ] ∈ R d an orthonormal family, and ( σ i 2 ( X ) ) i ∈ [ n ] (\sigma_i^2(\mathbf{X}))_{i\in[n]} ( σ i 2 ( X ) ) i ∈ [ n ] the singular values of X X T \mathbf{X}\mathbf{X}^{\mathsf{T}} X X T (and also of X T X \mathbf{X}^{\mathsf{T}}\mathbf{X} X T X ). Since, in the span of Σ \Sigma Σ , X \mathbf{X} X is a k × n k \times n k × n matrix with i.i.d. standard gaussian entries, Theorem 4.6.1 in [Ver26] states that, with probability at least 1 − β 1-\beta 1 − β ,
∥ 1 k X T X − I n ∥ 2 ≤ C max ( a , a 2 ) with a = n k + log ( 2 / β ) k , \left\lVert\frac{1}{k}\mathbf{X}^{\mathsf{T}}\mathbf{X}-I_n \right\rVert_2 \le C\max(a,a^2) \quad\text{with} \quad a=\sqrt{\frac{n}{k}}+\sqrt{\frac{\log(2/\beta)}{k}}, k 1 X T X − I n 2 ≤ C max ( a , a 2 ) with a = k n + k log ( 2/ β ) ,
with C > 0 C > 0 C > 0 a universal constant. It follows that
max ( 0 , 1 − C max ( a , a 2 ) ) P X ⪯ n k Σ ^ X ⪯ ( 1 + C max ( a , a 2 ) ) P X . \max(0,1-C\max(a,a^2))P_{\mathbf{X}} \preceq\frac{n}{k}\widehat{\Sigma}_{\mathbf{X}} \preceq(1+C\max(a,a^2))P_{\mathbf{X}}. max ( 0 , 1 − C max ( a , a 2 )) P X ⪯ k n Σ X ⪯ ( 1 + C max ( a , a 2 )) P X .
A few algebraic manipulations show that for β = 2 exp ( − k / ( 4 C ) 2 ) \beta= 2\exp(-k/(4C)^2) β = 2 exp ( − k / ( 4 C ) 2 ) and k > ( 4 C ) 2 n k > (4C)^2n k > ( 4 C ) 2 n it holds that C max ( a , a 2 ) ≤ 1 / 2 C\max(a,a^2) \le1/2 C max ( a , a 2 ) ≤ 1/2 , which concludes the proof. □
Lemma A.2 (Chernoff for bounded random variables). Let r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m be independent random variables taking values in [ 0 , R ] [0,R] [ 0 , R ] . Then for all β > 0 \beta> 0 β > 0
Pr [ ∑ r j ≥ e ∑ E [ r j ] + R ln ( 1 / β ) ] ≤ β . \Pr\left[\sum r_j \ge e\sum\mathbb{E}[r_j] + R\ln(1/\beta)\right] \le\beta. Pr [ ∑ r j ≥ e ∑ E [ r j ] + R ln ( 1/ β ) ] ≤ β . Proof. Observe that for any m m m independent random variables r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m taking values in [ 0 , R ] [0,R] [ 0 , R ] we have
E [ e r j / R ] = ∏ E [ e r j / R ] ≤ ∏ E [ 1 + e r j / R ] ≤ e ( e / R ) ∑ E [ r j ] , \mathbb{E}\left[e^{r_j/R}\right] = \prod\mathbb{E}\left[e^{r_j/R}\right] \le\prod\mathbb{E}\left[1+er_j/R\right] \le e^{(e/R)\sum\mathbb{E}[r_j]}, E [ e r j / R ] = ∏ E [ e r j / R ] ≤ ∏ E [ 1 + e r j / R ] ≤ e ( e / R ) ∑ E [ r j ] , where the first inequality follows from the fact that for all t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] we have e t = 1 + t ∑ k ≥ 1 t k − 1 / k ! ≤ 1 + e t e^t = 1 + t\sum_{k\geq1}t^{k-1}/k! \le1+et e t = 1 + t ∑ k ≥ 1 t k − 1 / k ! ≤ 1 + e t . By a Chernoff bound, for all $t > 0
Pr [ ∑ r j / R ≥ t ] ≤ e ( e / R ) ∑ E [ r j ] − t . \Pr\left[\sum r_j/R \ge t\right] \le e^{(e/R)\sum\mathbb{E}[r_j]-t}. Pr [ ∑ r j / R ≥ t ] ≤ e ( e / R ) ∑ E [ r j ] − t . Setting t = ( e / R ) ∑ E [ r j ] + ln ( 1 / β ) t = (e/R)\sum\mathbb{E}[r_j] + \ln(1/\beta) t = ( e / R ) ∑ E [ r j ] + ln ( 1/ β ) and multiplying through by R R R completes the proof. □
Lemma A.3 (Sum of heavy tailed random variables). Let α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , t 0 > 1 / 2 t_0 > 1/2 t 0 > 1/2 . Let y y y be a nonnegative random variable such that Pr [ y ≥ t ] ≤ C t − α \Pr[y \ge t] \le Ct^{-\alpha} Pr [ y ≥ t ] ≤ C t − α for all t ≥ t 0 t \ge t_0 t ≥ t 0 . Let y 1 , … , y d y_1,\ldots,y_d y 1 , … , y d be i.i.d. copies of y y y . Then there exists K = K ( C , α , t 0 ) K = K(C,\alpha,t_0) K = K ( C , α , t 0 ) , such that for all m ≥ 1 m \ge1 m ≥ 1 ,
Pr [ ∑ i = 1 d y i ≥ m d 1 / α ] ≤ K m − α . \Pr\left[\sum_{i=1}^{d}y_i \ge md^{1/\alpha}\right] \le Km^{-\alpha}. Pr [ i = 1 ∑ d y i ≥ m d 1/ α ] ≤ K m − α . Additionally for α = 1 \alpha= 1 α = 1 , it holds that
Pr [ ∑ i = 1 d y i ≥ m d ] ≤ K 1 log ( m d ) m , \Pr\left[\sum_{i=1}^{d}y_i \ge md\right] \le\frac{K_1\log(md)}{m}, Pr [ i = 1 ∑ d y i ≥ m d ] ≤ m K 1 log ( m d ) , where K 1 = ( 2 C + t 0 ) K_1 = (2C+t_0) K 1 = ( 2 C + t 0 ) .
Proof. Let A : = max { C , t 0 α } A := \max\{C,t_0^\alpha\} A := max { C , t 0 α } . Then for all t > 0 t > 0 t > 0 , Pr [ y ≥ t ] ≤ min ( 1 , A t − α ) \Pr[y \ge t] \le\min(1,At^{-\alpha}) Pr [ y ≥ t ] ≤ min ( 1 , A t − α ) . Let
S = ∑ i = 1 d y i , M = max 1 ≤ i ≤ d y i , x = m d 1 / α . S = \sum_{i=1}^{d}y_i,\qquad M = \max_{1\leq i\leq d}y_i,\qquad x = md^{1/\alpha}. S = i = 1 ∑ d y i , M = 1 ≤ i ≤ d max y i , x = m d 1/ α . By the union bound,
Pr [ M ≥ x 2 ] ≤ d Pr [ y ≥ x 2 ] ≤ d min ( 1 , C ( x 2 ) − α ) = min ( d , A 2 α m − α ) ≤ A 2 α m − α . \Pr\left[M \ge\frac{x}{2}\right] \le d\Pr\left[y \ge\frac{x}{2}\right] \le d\min\left(1,C\left(\frac{x}{2}\right)^{-\alpha}\right) = \min(d,A2^\alpha m^{-\alpha}) \le A2^\alpha m^{-\alpha}. Pr [ M ≥ 2 x ] ≤ d Pr [ y ≥ 2 x ] ≤ d min ( 1 , C ( 2 x ) − α ) = min ( d , A 2 α m − α ) ≤ A 2 α m − α . Now let T = ∑ i = 1 d y i 1 [ y i ≤ x / 2 ] T = \sum_{i=1}^{d}y_i\mathbf{1}[y_i \le x/2] T = ∑ i = 1 d y i 1 [ y i ≤ x /2 ] . If S ≥ x S \ge x S ≥ x and M < x / 2 M < x/2 M < x /2 , then T = S ≥ x T = S \ge x T = S ≥ x , so
Pr [ S ≥ x ] ≤ Pr ( S ≥ x , M < x 2 ) + Pr ( S ≥ x , M ≥ x 2 ) ≤ Pr [ T ≥ x ] + Pr [ M ≥ x 2 ] . \Pr[S \ge x] \le\Pr\left(S \ge x, M < \frac{x}{2}\right) + \Pr\left(S \ge x, M \ge\frac{x}{2}\right) \le\Pr[T \ge x] + \Pr\left[M \ge\frac{x}{2}\right]. Pr [ S ≥ x ] ≤ Pr ( S ≥ x , M < 2 x ) + Pr ( S ≥ x , M ≥ 2 x ) ≤ Pr [ T ≥ x ] + Pr [ M ≥ 2 x ] .
Moreover, for α < 1 \alpha< 1 α < 1 ,
E [ T ] = d E [ y 1 { y ≤ x / 2 } ] ≤ d ∫ 0 x / 2 Pr [ y ≥ t ] d t ≤ d t 0 + d A ∫ t 0 x / 2 t − α d t = d t 0 + d A 1 − α ( ( x 2 ) 1 − α − t 0 1 − α ) . \begin{aligned}
\mathbb{E}[T] = d\mathbb{E}\left[y\mathbf{1}_{\{y \le x/2\}}\right] \le d\int_{0}^{x/2}\Pr[y \ge t]\,dt \\
&\le dt_0+dA\int_{t_0}^{x/2}t^{-\alpha}\,dt=dt_0+\frac{dA}{1-\alpha}\left(\left(\frac{x}{2}\right)^{1-\alpha}-t_0^{1-\alpha}\right).
\end{aligned} E [ T ] = d E [ y 1 { y ≤ x /2 } ] ≤ d ∫ 0 x /2 Pr [ y ≥ t ] d t ≤ d t 0 + d A ∫ t 0 x /2 t − α d t = d t 0 + 1 − α d A ( ( 2 x ) 1 − α − t 0 1 − α ) .
thus E [ T ] ≤ d A 1 − α 2 α − 1 x 1 − α \mathbb{E}[T]\le\frac{dA}{1-\alpha}2^{\alpha-1}x^{1-\alpha} E [ T ] ≤ 1 − α d A 2 α − 1 x 1 − α . By Markov’s inequality,
Pr [ T ≥ x ] ≤ E [ T ] x ≤ A 2 α − 1 1 − α d x − α ≤ A 2 α − 1 1 − α m − α . \Pr[T\ge x]\le\frac{\mathbb{E}[T]}{x}\le\frac{A2^{\alpha-1}}{1-\alpha}dx^{-\alpha}\le\frac{A2^{\alpha-1}}{1-\alpha}m^{-\alpha}. Pr [ T ≥ x ] ≤ x E [ T ] ≤ 1 − α A 2 α − 1 d x − α ≤ 1 − α A 2 α − 1 m − α .
where the last inequality holds by the fact that x = m d 1 / α x=md^{1/\alpha} x = m d 1/ α , so d x − α = m − α dx^{-\alpha}=m^{-\alpha} d x − α = m − α . Combining the two:
Pr [ S ≥ m d 1 / α ] ≤ A 2 α m − α + A 2 α − 1 1 − α m − α ≤ K α , t 0 , C m − α \Pr[S\ge md^{1/\alpha}]\le A2^\alpha m^{-\alpha}+\frac{A2^{\alpha-1}}{1-\alpha}m^{-\alpha}\le K_{\alpha,t_0,C}m^{-\alpha} Pr [ S ≥ m d 1/ α ] ≤ A 2 α m − α + 1 − α A 2 α − 1 m − α ≤ K α , t 0 , C m − α
where K : = max { C , t 0 α } ( 2 α + 2 α − 1 1 − α ) K:=\max\{C,t_0^\alpha\}\left(2^\alpha+\frac{2^{\alpha-1}}{1-\alpha}\right) K := max { C , t 0 α } ( 2 α + 1 − α 2 α − 1 ) .
For α = 1 \alpha=1 α = 1 ,
E [ T ] ≤ d t 0 + d C ∫ t 0 x / 2 t − α d t = d t 0 + d C log ( x 2 t 0 ) . \mathbb{E}[T]\le dt_0+dC\int_{t_0}^{x/2}t^{-\alpha}\,dt=dt_0+dC\log\left(\frac{x}{2t_0}\right). E [ T ] ≤ d t 0 + d C ∫ t 0 x /2 t − α d t = d t 0 + d C log ( 2 t 0 x ) .
Thus Pr [ T ≥ x ] ≤ t 0 m + C log ( m d / 2 t 0 ) m \Pr[T\ge x]\le\frac{t_0}{m}+\frac{C\log(md/2t_0)}{m} Pr [ T ≥ x ] ≤ m t 0 + m C l o g ( m d /2 t 0 ) . And
Pr [ S ≥ m d 1 / α ] ≤ 2 C m + t 0 m + C log ( m d / 2 t 0 ) m ≤ K 1 log ( m d ) m \Pr[S\ge md^{1/\alpha}]\le\frac{2C}{m}+\frac{t_0}{m}+\frac{C\log(md/2t_0)}{m}\le K_1\frac{\log(md)}{m} Pr [ S ≥ m d 1/ α ] ≤ m 2 C + m t 0 + m C log ( m d /2 t 0 ) ≤ K 1 m log ( m d )
where K 1 = ( 3 C + t 0 ) K_1=(3C+t_0) K 1 = ( 3 C + t 0 ) .
Lemma A.4 (Top-k k k samples from inv χ 2 ( 1 , 1 ) \operatorname{inv}\chi^2(1,1) inv χ 2 ( 1 , 1 ) ). Let σ 1 2 , … , σ d 2 ∼ inv χ 2 ( 1 , 1 ) ⊗ d \sigma_1^2,\ldots,\sigma_d^2\sim\operatorname{inv}\chi^2(1,1)^{\otimes d} σ 1 2 , … , σ d 2 ∼ inv χ 2 ( 1 , 1 ) ⊗ d , then there exists an absolute constant c > 0 c>0 c > 0 such that for all 1 ≤ k ≤ c d 1\le k\le cd 1 ≤ k ≤ c d ,
Pr [ σ ( k ) 2 ≥ d 2 4 k 2 ] ≥ 1 − 2 k . \Pr\left[\sigma_{(k)}^2\ge\frac{d^2}{4k^2}\right]\ge1-\frac{2}{k}. Pr [ σ ( k ) 2 ≥ 4 k 2 d 2 ] ≥ 1 − k 2 .
Proof. Let C ′ > 0 C'>0 C ′ > 0 be a sufficiently large absolute constant. For all i ∈ [ d ] i\in[d] i ∈ [ d ] , since σ i 2 ∼ inv χ 2 ( 1 , 1 ) \sigma_i^2\sim\operatorname{inv}\chi^2(1,1) σ i 2 ∼ inv χ 2 ( 1 , 1 ) , we have for t ≥ C ′ t\ge C' t ≥ C ′ that Pr [ σ i 2 ≥ t ] = C ( t ) t − 1 / 2 \Pr[\sigma_i^2\ge t]=C(t)t^{-1/2} Pr [ σ i 2 ≥ t ] = C ( t ) t − 1/2 , with C ( t ) ∈ [ 1 , e ] C(t)\in[1,\sqrt{e}] C ( t ) ∈ [ 1 , e ] . Consider the events H i : = { σ i 2 ≥ d 2 / ( 2 k ) 2 } H_i:=\{\sigma_i^2\ge d^2/(2k)^2\} H i := { σ i 2 ≥ d 2 / ( 2 k ) 2 } and let S = ∑ i ∈ [ d ] 1 H i S=\sum_{i\in[d]}\mathbf{1}_{H_i} S = ∑ i ∈ [ d ] 1 H i . It holds that Pr [ H i ] = 2 C k / d \Pr[H_i]=2Ck/d Pr [ H i ] = 2 C k / d , and thus E [ S ] = 2 C k \mathbb{E}[S]=2Ck E [ S ] = 2 C k . Since S S S is the sum of independent Bernoulli random variables, Chebyshev’s inequality yields
Pr [ S ≤ 1 2 E [ S ] ] ≤ Pr [ ∣ S − E [ S ] ∣ ≥ 1 2 E [ S ] ] ≤ 4 Var [ S ] E [ S ] 2 ≤ 4 d Pr [ H 1 ] E [ S ] 2 = 4 E [ S ] = 2 k . \begin{aligned}
\Pr\left[S\le\frac{1}{2}\mathbb{E}[S]\right]\le\Pr\left[|S-\mathbb{E}[S]|\ge\frac{1}{2}\mathbb{E}[S]\right]\le\frac{4\operatorname{Var}[S]}{\mathbb{E}[S]^2} \\
&\le\frac{4d\Pr[H_1]}{\mathbb{E}[S]^2}=\frac{4}{\mathbb{E}[S]}=\frac{2}{k}.
\end{aligned} Pr [ S ≤ 2 1 E [ S ] ] ≤ Pr [ ∣ S − E [ S ] ∣ ≥ 2 1 E [ S ] ] ≤ E [ S ] 2 4 Var [ S ] ≤ E [ S ] 2 4 d Pr [ H 1 ] = E [ S ] 4 = k 2 .
Thus, at least k k k of the σ j 2 \sigma_j^2 σ j 2 ’s are at least d 2 4 k 2 \frac{d^2}{4k^2} 4 k 2 d 2 with probability at least 1 − 2 k 1-\frac{2}{k} 1 − k 2 .
Lemma A.5 (Concentration of the χ k 2 \chi_k^2 χ k 2 distribution [30 ] ). Let x ∼ χ k 2 x \sim\chi_k^2 x ∼ χ k 2 , then for any t ≥ 0 t \ge0 t ≥ 0
Pr [ x ≥ k + 2 k t + 2 t ] ≤ exp ( − t ) and Pr [ x ≤ k − 2 k t ] ≤ exp ( − t ) . \Pr[x \ge k + 2\sqrt{kt} + 2t] \le\exp(-t) \quad\text{and} \quad\Pr[x \le k - 2\sqrt{kt}] \le\exp(-t). Pr [ x ≥ k + 2 k t + 2 t ] ≤ exp ( − t ) and Pr [ x ≤ k − 2 k t ] ≤ exp ( − t ) .
Folklore Algorithm
In this section we explain the folklore algorithm for Gaussian mean estimation, which demonstrates the tightness of Theorem 2.1. The algorithm proceeds in two phases: first, it estimates tr ( Σ ) \operatorname{tr}(\Sigma) tr ( Σ ) using the average norm of half of the samples, and second, it runs friendly-core with clipping radius tr ( Σ ) \operatorname{tr}(\Sigma) tr ( Σ ) . By the guarantees of Friendly-core, the resulting output is the empirical mean on half of the data plus Gaussian noise with variance approximately tr ( Σ ) / n 2 \operatorname{tr}(\Sigma)/n^2 tr ( Σ ) / n 2 .
Theorem B.1 (Folklore algorithm). For all ε , δ , β > 0 \varepsilon, \delta, \beta> 0 ε , δ , β > 0 there exists an ( ε , δ ) (\varepsilon, \delta) ( ε , δ ) -DP mechanism M \mathcal{M} M such that for all μ ∈ R d \mu\in\mathbb{R}^d μ ∈ R d and positive semi-definite Σ ∈ R d × d \Sigma\in\mathbb{R}^{d \times d} Σ ∈ R d × d if
n = Ω ( log ( 1 / β δ ) ε ) n = \Omega\left(\frac{\log(1/\beta\delta)}{\varepsilon}\right) n = Ω ( ε log ( 1/ β δ ) ) and X = x 1 , … , x n ∼ N ( μ , Σ ) X = x_1, \ldots, x_n \sim\mathcal{N}(\mu, \Sigma) X = x 1 , … , x n ∼ N ( μ , Σ ) then
∥ M ( X ) − μ ∥ 2 ≤ O ( tr ( Σ ) + ∥ Σ ∥ op log ( 1 / β ) n + d ⋅ tr ( Σ ) log ( 1 / δ ) log ( n / β ) ε n ) \lVert\mathcal{M}(X) - \mu\rVert_2 \le O\left(\sqrt{\frac{\operatorname{tr}(\Sigma) + \lVert\Sigma\rVert_{\operatorname{op}}\log(1/\beta)}{n}} + \frac{\sqrt{d \cdot\operatorname{tr}(\Sigma)\log(1/\delta)\log(n/\beta)}}{\varepsilon n}\right) ∥ M ( X ) − μ ∥ 2 ≤ O ( n tr ( Σ ) + ∥ Σ ∥ op log ( 1/ β ) + ε n d ⋅ tr ( Σ ) log ( 1/ δ ) log ( n / β ) ) with probability at least 1 − β 1 - \beta 1 − β .
Proof. In order to define the mechanism M \mathcal{M} M we will require the following two results.
We use a slightly modified version of stable-histogram from [28 ] . The original version of the statement in Theorem B.2 is from [4 ] , we instantiate it here with bins { [ 2 b − 1 , 2 b ] } b ∈ Z \{[2^{b-1}, 2^b]\}_{b\in\mathbb{Z}} {[ 2 b − 1 , 2 b ] } b ∈ Z and output Y ~ = 2 b ~ ∈ { 2 b − 1 , 2 b , 2 b + 1 } \widetilde{Y}=2^{\widetilde{b}}\in\{2^{b-1},2^b,2^{b+1}\} Y = 2 b ∈ { 2 b − 1 , 2 b , 2 b + 1 } instead of b ~ ∈ { b − 1 , b , b + 1 } \widetilde{b}\in\{b-1,b,b+1\} b ∈ { b − 1 , b , b + 1 } .
Lemma B.2 (Stable-histogram [4 ] ). There exists an algorithm StableHistogram ε , δ \operatorname{StableHistogram}_{\varepsilon,\delta} StableHistogram ε , δ that is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private and satisfies the following guarantee: Let z 1 , … , z n z_1,\ldots,z_n z 1 , … , z n be drawn i.i.d. from distribution P P P . Suppose that there exists b ∈ Z b\in\mathbb{Z} b ∈ Z and a constant β ′ < 1 4 \beta' < \frac{1}{4} β ′ < 4 1 , such that Pr [ z i ∉ [ 2 b − 1 , 2 b + 1 ] ] ≤ β ′ \Pr[z_i \notin[2^{b-1},2^{b+1}]]\le\beta' Pr [ z i ∈ / [ 2 b − 1 , 2 b + 1 ]] ≤ β ′ for any fixed i ∈ [ n ] i\in[n] i ∈ [ n ] . There exists a constant C > 0 C>0 C > 0 such that, for all 0 < ε , β , δ < 1 0<\varepsilon,\beta,\delta<1 0 < ε , β , δ < 1 , if
n ≥ C ε log 1 β δ , n \ge\frac{C}{\varepsilon}\log\frac{1}{\beta\delta}, n ≥ ε C log β δ 1 , then StableHistogram ε , δ ( z 1 , … , z n ) ∈ [ 2 b − 1 , 2 b + 1 ] \operatorname{StableHistogram}_{\varepsilon,\delta}(z_1,\ldots,z_n)\in[2^{b-1},2^{b+1}] StableHistogram ε , δ ( z 1 , … , z n ) ∈ [ 2 b − 1 , 2 b + 1 ] with probability at least 1 − β 1-\beta 1 − β .
We will also use the friendly-core aggregation algorithm discovered by [TCKMS22] to estimate the mean. The exact statement of Theorem B.3 does not appear explicitly in [TCKMS22], but it follows immediately from their results.
Lemma B.3 (Friendly-core averaging). Fix ε , δ , R > 0 \varepsilon,\delta,R>0 ε , δ , R > 0 . There exists an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP algorithm A \mathcal{A} A that gets as input X = x 1 , … , x n X=x_1,\ldots,x_n X = x 1 , … , x n and satisfies the following: If n ≥ Ω ~ ( log ( 1 / β δ ) / ε ) n\ge\widetilde{\Omega}(\sqrt{\log(1/\beta\delta)}/\varepsilon) n ≥ Ω ( log ( 1/ β δ ) / ε ) and ∥ x i − x j ∥ 2 ≤ R \lVert x_i-x_j\rVert_2\le R ∥ x i − x j ∥ 2 ≤ R for all i , j ∈ [ n ] i,j\in[n] i , j ∈ [ n ] then
∥ A ( X ) − 1 n ∑ i x i ∥ 2 ≤ O ( R d log ( 1 / δ ) log ( 1 / β ) ε n ) \left\lVert\mathcal{A}(X)-\frac{1}{n}\sum_i x_i\right\rVert_2 \le O\left(\frac{R\sqrt{d\log(1/\delta)\log(1/\beta)}}{\varepsilon n}\right) A ( X ) − n 1 i ∑ x i 2 ≤ O ( ε n R d log ( 1/ δ ) log ( 1/ β ) )
with probability at least 1 − β 1-\beta 1 − β .
Proof of Theorem B.3. Let A \mathcal{A} A denote the algorithm FC_Avg from [TCKMS22] run with zCDP parameters ρ = ε 2 / 10 log ( 1 / δ ) \rho=\varepsilon^2/10\log(1/\delta) ρ = ε 2 /10 log ( 1/ δ ) and δ 0 = δ / 2 \delta_0=\delta/2 δ 0 = δ /2 and diameter R R R .
First we argue that A \mathcal{A} A is private. By Theorem 5.2 of [TCKMS22], algorithm A \mathcal{A} A is ( ρ , δ ) (\rho,\delta) ( ρ , δ ) -zCDP, which, by Fact 2.7 of [TCKMS22] with δ ′ ← δ 0 \delta' \leftarrow\delta_0 δ ′ ← δ 0 , implies that A \mathcal{A} A is ( ρ + 2 ρ ln ( 1 / δ 0 ) , 2 δ 0 ) (\rho+2\sqrt{\rho\ln(1/\delta_0)},2\delta_0) ( ρ + 2 ρ ln ( 1/ δ 0 ) , 2 δ 0 ) -DP. By our setting of ρ \rho ρ and δ 0 \delta_0 δ 0 algorithm A \mathcal{A} A is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP.
To see that A \mathcal{A} A is accurate, we can apply Claim C.4 of [TCKMS22], which states that if n = Ω ( log ( 1 / ρ β δ 0 ) / ρ ) n=\Omega(\sqrt{\log(1/\rho\beta\delta_0)/\rho}) n = Ω ( log ( 1/ ρβ δ 0 ) / ρ ) and ∥ x i − x j ∥ 2 ≤ R \lVert x_i-x_j\rVert_2\le R ∥ x i − x j ∥ 2 ≤ R for all i , j ∈ [ n ] i,j\in[n] i , j ∈ [ n ] then
∥ A ( X ) − 1 n ∑ x i ∥ 2 ≤ O ( R n d log ( 1 / β ) ρ ) \left\lVert\mathcal{A}(X)-\frac{1}{n}\sum x_i\right\rVert_2\le O\left(\frac{R}{n}\sqrt{\frac{d\log(1/\beta)}{\rho}}\right) A ( X ) − n 1 ∑ x i 2 ≤ O ( n R ρ d log ( 1/ β ) )
with probability at least 1 − β 1-\beta 1 − β . Using our setting of ρ \rho ρ and δ 0 \delta_0 δ 0 concludes the proof.
Note: The requirement on n n n in Claim C.4 of [TCKMS22] is missing a square root—it reads n ≥ log ( 1 / β δ ) / ρ n\ge\log(1/\beta\delta)/\rho n ≥ log ( 1/ β δ ) / ρ ; however, the proof of Claim C.4 only requires n ≥ log ( 1 / β δ ) / ρ n\ge\sqrt{\log(1/\beta\delta)/\rho} n ≥ log ( 1/ β δ ) / ρ in order to invoke the relevant claim (Claim C.3), and thus the requirement on n n n in our proof is sufficient. □
Next, we define the mechanism M \mathcal{M} M . Let C > 0 C>0 C > 0 be a sufficiently large absolute constant.
Algorithm 1 Folklore estimator M \mathcal{M} M
Input: Privacy parameter ε , δ ∈ ( 0 , 1 ) \varepsilon,\delta\in(0,1) ε , δ ∈ ( 0 , 1 ) , dataset X = x 1 , … , x n X=x_1,\ldots,x_n X = x 1 , … , x n , failure probability β > 0 \beta>0 β > 0 .
Output: Estimate μ ~ ∈ R d \tilde{\mu}\in\mathbb{R}^d μ ~ ∈ R d
Set ℓ ← C ε log ( 1 / β δ ) \ell\leftarrow\frac{C}{\varepsilon}\log(1/\beta\delta) ℓ ← ε C log ( 1/ β δ )
Partition X X X into X 0 X_0 X 0 and X 1 X_1 X 1 , and X 0 X_0 X 0 into B 1 , … , B ℓ B_1,\ldots,B_\ell B 1 , … , B ℓ
For each i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] and x 1 , … , x n / 2 ℓ ∈ B i x_1,\ldots,x_{n/2\ell}\in B_i x 1 , … , x n /2 ℓ ∈ B i let y j = 1 2 ( x 2 j − 1 − x 2 j ) y_j=\frac{1}{\sqrt{2}}(x_{2j-1}-x_{2j}) y j = 2 1 ( x 2 j − 1 − x 2 j ) for each j ∈ [ n / 4 ℓ ] j\in[n/4\ell] j ∈ [ n /4 ℓ ] .
For each i ∈ [ ℓ ] i\in[\ell] i ∈ [ ℓ ] let
y ˉ i ← 4 ℓ n ∑ y j ∈ B i ∥ y j ∥ 2 2 \bar{y}_i\leftarrow\frac{4\ell}{n}\sum_{y_j\in B_i}\lVert y_j\rVert_2^2 y ˉ i ← n 4 ℓ y j ∈ B i ∑ ∥ y j ∥ 2 2
Let y ~ \tilde{y} y ~ be the output of StableHistogram ε / 2 , δ / 2 \operatorname{StableHistogram}_{\varepsilon/2,\delta/2} StableHistogram ε /2 , δ /2 on input ( y ˉ i ) i ∈ [ ℓ ] (\bar{y}_i)_{i\in[\ell]} ( y ˉ i ) i ∈ [ ℓ ]
Let R ← C y ~ log ( n / β ) R\leftarrow C\sqrt{\tilde{y}\log(n/\beta)} R ← C y ~ log ( n / β )
Output μ ~ ← A ε / 2 , δ / 2 ( X 1 , R ) \tilde{\mu}\leftarrow\mathcal{A}_{\varepsilon/2,\delta/2}(X_1,R) μ ~ ← A ε /2 , δ /2 ( X 1 , R ) where A \mathcal{A} A is the algorithm from Theorem B.3
First, we argue that M \mathcal{M} M is private. Since stable-histogram and A \mathcal{A} A are ( ε / 2 , δ / 2 ) (\varepsilon/2,\delta/2) ( ε /2 , δ /2 ) -DP, basic composition and postprocessing yields that M \mathcal{M} M is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP.
Next, we show that the accuracy guarantee holds. The basic idea is to show that each y ˉ i \bar{y}_i y ˉ i gives a multiplicative approximation to tr ( Σ ) \operatorname{tr}(\Sigma) tr ( Σ ) with high probability, and thus, stable-histogram returns an estimate y ~ \tilde{y} y ~ that is a multiplicative approximation to tr ( Σ ) \operatorname{tr}(\Sigma) tr ( Σ ) . We then argue that with high probability ∥ x i − x j ∥ 2 ≤ R \lVert x_i-x_j\rVert_2\le R ∥ x i − x j ∥ 2 ≤ R for all x i x_i x i and x j x_j x j in X 1 X_1 X 1 . Applying the guarantee of Theorem B.3 and a union bound suffices to complete the argument. The remainder of the proof formalizes this intuitive argument.
Lemma B.4 (Concentration of the norm). Let Y = y 1 , … , y m ∼ N ( 0 , Σ ) Y = y_1, \ldots, y_m \sim\mathcal{N}(0, \Sigma) Y = y 1 , … , y m ∼ N ( 0 , Σ ) then for all β > 0 \beta> 0 β > 0
∣ 1 m ∑ i ∥ y i ∥ 2 2 − tr ( Σ ) ∣ ≤ tr ( Σ ) log ( 2 / β ) m + ∥ Σ ∥ op log ( 2 / β ) m \left| \frac{1}{m} \sum_i \lVert y_i \rVert_2^2 - \operatorname{tr}(\Sigma) \right| \le\operatorname{tr}(\Sigma) \sqrt{\frac{\log(2/\beta)}{m}} + \lVert\Sigma\rVert_{\operatorname{op}} \frac{\log(2/\beta)}{m} m 1 i ∑ ∥ y i ∥ 2 2 − tr ( Σ ) ≤ tr ( Σ ) m log ( 2/ β ) + ∥ Σ ∥ op m log ( 2/ β ) with probability at least 1 − β 1-\beta 1 − β .
Proof. This follows from rotation invariance of N ( 0 , Σ ) \mathcal{N}(0, \Sigma) N ( 0 , Σ ) and Chebyshev’s inequality. Observe that if y ∼ N ( 0 , Σ ) y \sim\mathcal{N}(0, \Sigma) y ∼ N ( 0 , Σ ) , then we can equivalently write y y y as Σ 1 / 2 z \Sigma^{1/2}z Σ 1/2 z where z ∼ N ( 0 , I ) z \sim\mathcal{N}(0, I) z ∼ N ( 0 , I ) . Now, if Σ = V D V ⊤ \Sigma= VDV^{\top} Σ = V D V ⊤ then ∥ y ∥ 2 2 = z ⊤ V D V ⊤ z \lVert y\rVert_2^2 = z^{\top}VDV^{\top}z ∥ y ∥ 2 2 = z ⊤ V D V ⊤ z . By rotation invariance of the Gaussian distribution, the random variable z ~ = V ⊤ z \widetilde{z} = V^{\top}z z = V ⊤ z is still distributed according to N ( 0 , I ) \mathcal{N}(0,I) N ( 0 , I ) . Thus, ∥ y ∥ 2 2 = z ~ ⊤ D z ~ = ∑ j ∈ [ d ] λ j z [ j ] 2 \lVert y\rVert_2^2 = \widetilde{z}^{\top}D\widetilde{z} = \sum_{j \in[d]} \lambda_j z_{[j]}^2 ∥ y ∥ 2 2 = z ⊤ D z = ∑ j ∈ [ d ] λ j z [ j ] 2 , where λ j \lambda_j λ j is the j j j th eigenvalue of Σ \Sigma Σ and z [ j ] ∼ χ 1 2 z_{[j]} \sim\chi_1^2 z [ j ] ∼ χ 1 2 .
Applying the above argument to each y i y_i y i , we have that
1 m ∑ i ∈ [ m ] ∥ y i ∥ 2 2 = 1 m ∑ i ∈ [ m ] j ∈ [ d ] λ j z i [ j ] 2 \frac{1}{m} \sum_{i \in[m]} \lVert y_i\rVert_2^2 = \frac{1}{m} \sum_{\substack{i \in[m]\\j\in[d]}} \lambda_j z_{i[j]}^2 m 1 i ∈ [ m ] ∑ ∥ y i ∥ 2 2 = m 1 i ∈ [ m ] j ∈ [ d ] ∑ λ j z i [ j ] 2
Since E [ ∥ y i ∥ 2 2 ] = tr ( Σ ) \mathbb{E}[\lVert y_i\rVert_2^2] = \operatorname{tr}(\Sigma) E [∥ y i ∥ 2 2 ] = tr ( Σ ) , and since the z i [ j ] 2 z_{i[j]}^2 z i [ j ] 2 ’s are independent for each i i i and j j j , we can apply Scalar Bernstein (e.g., Corollary 2.9.2 [Ver26]) to see that
Pr [ ∣ 1 m ∑ i ∈ [ m ] j ∈ [ d ] λ j z i [ j ] 2 − tr ( Σ ) ∣ ≥ tr ( Σ ) log ( 2 / β ) m + ∥ Σ ∥ op log ( 2 / β ) m ] ≤ β . \Pr\left[\left| \frac{1}{m} \sum_{\substack{i \in[m]\\j\in[d]}} \lambda_j z_{i[j]}^2 - \operatorname{tr}(\Sigma) \right| \ge\operatorname{tr}(\Sigma)\sqrt{\frac{\log(2/\beta)}{m}} + \lVert\Sigma\rVert_{\operatorname{op}}\frac{\log(2/\beta)}{m}\right] \le\beta. Pr m 1 i ∈ [ m ] j ∈ [ d ] ∑ λ j z i [ j ] 2 − tr ( Σ ) ≥ tr ( Σ ) m log ( 2/ β ) + ∥ Σ ∥ op m log ( 2/ β ) ≤ β .
By our setting of n n n and ℓ \ell ℓ , and by Theorem B.4 with m = n / 4 ℓ m=n/4\ell m = n /4 ℓ and β ← 1 / 5 \beta\leftarrow1/5 β ← 1/5 , we have that Pr [ y ˉ i ∉ tr ( Σ ) ⋅ [ 1 / 2 , 2 ] ] ≤ 1 / 5 \Pr[\bar{y}_i \notin\operatorname{tr}(\Sigma) \cdot[1/2, 2]] \le1/5 Pr [ y ˉ i ∈ / tr ( Σ ) ⋅ [ 1/2 , 2 ]] ≤ 1/5 . Thus, by Theorem B.2, and our setting of n n n , we have that y ~ ∈ tr ( Σ ) ⋅ [ 1 / 2 , 2 ] \widetilde{y} \in\operatorname{tr}(\Sigma) \cdot[1/2, 2] y ∈ tr ( Σ ) ⋅ [ 1/2 , 2 ] with probability at least 1 − β 1-\beta 1 − β .
Let B 0 B_0 B 0 be the event that y ~ \widetilde{y} y is not in this interval, and let B 1 B_1 B 1 be the event that some x i − μ x_i-\mu x i − μ has ∥ x i − μ ∥ 2 ≥ C tr ( Σ ) log ( n / β ) \lVert x_i-\mu\rVert_2 \ge C\sqrt{\operatorname{tr}(\Sigma)\log(n/\beta)} ∥ x i − μ ∥ 2 ≥ C tr ( Σ ) log ( n / β ) for some large constant C > 0 C > 0 C > 0 . By Theorem B.4 with m = 1 m=1 m = 1 and the union bound over the n n n datapoints, we have that Pr [ B 1 ] ≤ β \Pr[B_1] \le\beta Pr [ B 1 ] ≤ β . Now, conditioned on B 0 ‾ ∪ B 1 ‾ \overline{B_0} \cup\overline{B_1} B 0 ∪ B 1 , we have that ∥ x i − x j ∥ ≤ R \lVert x_i-x_j\rVert\le R ∥ x i − x j ∥ ≤ R for all i i i and j j j , and thus, by Theorem B.3,
∥ A ( X ) − 2 n ∑ x i ∈ X 1 x i ∥ 2 ≤ O ( R d log ( 1 / δ ) log ( 1 / β ) ε n ) \left\lVert\mathcal{A}(X) - \frac{2}{n}\sum_{x_i\in X_1}x_i \right\rVert_2 \le O\left(\frac{R\sqrt{d\log(1/\delta)\log(1/\beta)}}{\varepsilon n}\right) A ( X ) − n 2 x i ∈ X 1 ∑ x i 2 ≤ O ( ε n R d log ( 1/ δ ) log ( 1/ β ) )
with probability at least 1 − β 1-\beta 1 − β . Let B 2 B_2 B 2 be the event that μ ~ \widetilde{\mu} μ fails to satisfy the above inequality. Then
Pr [ B 2 ] = Pr [ B 2 ∣ B 1 ‾ ∪ B 0 ‾ ] Pr [ B 1 ‾ ∪ B 0 ‾ ] + Pr [ B 2 ∣ B 1 ∪ B 0 ‾ ] Pr [ B 1 ∪ B 0 ‾ ] ≤ 3 β . \Pr[B_2] = \Pr[B_2 \mid\overline{B_1} \cup\overline{B_0}]\Pr[\overline{B_1} \cup\overline{B_0}] + \Pr[B_2 \mid\overline{B_1 \cup B_0}]\Pr[\overline{B_1 \cup B_0}] \le3\beta. Pr [ B 2 ] = Pr [ B 2 ∣ B 1 ∪ B 0 ] Pr [ B 1 ∪ B 0 ] + Pr [ B 2 ∣ B 1 ∪ B 0 ] Pr [ B 1 ∪ B 0 ] ≤ 3 β .
To complete the argument, we need to show that the empirical mean on X 1 X_1 X 1 is close to μ \mu μ with high probability. Let B 3 B_3 B 3 be the event that
∥ 2 n ∑ x i ∈ X 1 x i − μ ∥ 2 ≥ C tr ( Σ ) + ∥ Σ ∥ op log ( 1 / β ) n . \left\lVert\frac{2}{n}\sum_{x_i\in X_1}x_i-\mu\right\rVert_2 \ge C\sqrt{\frac{\operatorname{tr}(\Sigma)+\lVert\Sigma\rVert_{\operatorname{op}}\log(1/\beta)}{n}}. n 2 x i ∈ X 1 ∑ x i − μ 2 ≥ C n tr ( Σ ) + ∥ Σ ∥ op log ( 1/ β ) .
Standard arguments for the min-max rate of Gaussian mean estimation imply that Pr [ B 3 ] ≤ β \operatorname{Pr}[B_{3}] \le\beta Pr [ B 3 ] ≤ β . Since μ ~ \widetilde{\mu} μ satisfies the accuracy guarantee of Theorem B.1 whenever neither of B 2 B_{2} B 2 or B 3 B_{3} B 3 occur, the union bound over B 2 B_{2} B 2 and B 3 B_{3} B 3 implies that the guarantee holds with probability at least 1 − β ~ 1-\widetilde{\beta} 1 − β with β ~ = 4 β \widetilde{\beta}=4\beta β = 4 β . □ \square □