Differentially Private Covariance Revisited
Authors: Wei Dong
Yuting Liang
Ke Yi
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
covariance estimation

Abstract: In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP).  The first algorithm achieves a Frobenius error of $\tilde{O}(d^{1/4}\sqrt{\mathrm{tr}}/\sqrt{n} + \sqrt{d}/n)$, where $\mathrm{tr}$ is the trace of the covariance matrix.  By taking $\mathrm{tr}=1$, this also implies a worst-case error bound of $\tilde{O}(d^{1/4}/\sqrt{n})$, which improves the standard Gaussian mechanism's $\tilde{O}(d/n)$ for the regime $d>\widetilde{\Omega}(n^{2/3})$.  Our second algorithm offers a tail-sensitive bound that could be much better on skewed data.  The corresponding algorithms are also simple and efficient. Experimental results show that they offer significant improvements over prior work.

Differentially Private Covariance Revisited
Wei Dong, Yuting Liang, Ke Yi {udongac, yl yli.nnba,nnnnnn. baaggbs.ykk)ecsee ust Department of Computer Science Hong Kong University of Science and Technology
Abstract
In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP). The first algorithm achieves Frobenius error of O(d (/dd///tr//// /n + vd/n), where is the trace of the covariance matrix. By taking tr 1, this also implies a worst-case error bound of (dd// /vm), which improves the standard Gaussian mechanism's 's (d/nn) for the regime d > (2 Our second algorithm offers tail-sensitive bound that could be much better on skewed data. The corresponding algorithms are also simple and efficient. Experimental results show that they offer significant improvements over prior work.
Introduction
Consider a dataset represented by matrix X Rdxa, where each column X;, I,...,m corresponds to individual's information. As standard in the literature, assume that all the X;'s live in B3, the d-dimensional by-unit ball centered at the origin. In this paper, we revisit the problem of estimating the (empirical) covariance matrix Σ(X) 1 XXXX " Xxx" under differential privacy (DP), fundamental problem in high-dimensional data analytics and machine learning that requires little motivation. We often write XX as Σ when the context is clear. As with most prior work, we use the Frobenius norm ΣΣ Σ) to measure the error of the estimated covariance Σ. To better focus, in the introduction state all results under concentrated different privacy (zCDP) [10]; extensions of our results to pure-DP are given in Appendix I.
x
1.1 A Trace-sensitive Algorithm
For any symmetric matrix A, cigenvalues, respectively, such that A P[AJAL [[A]A[A|P[A)] we use AA[A] to denote its ith largest eigenvalue. When A = Σ Σ(X), we simply write P P A[EJ, A > >,EE, so that = diag(A1.... Aa) and Σ PAP Let [P, Pa ... Pa]. where P. is the orthonormal basis vector corresponding to A;- Rudimentary linear algebra yields d E X,) for
P[A] and A[A] denote its matrices of eigenvectors and
1 & k: & d and ||2, Σn (PF x,)² for & i n. Thus, it follows that
tr Σ
tr[A]
= Σ A = Σ I K
1 ΣΣ
PT -
1 Σ I
That is. tr[A] < 1 is the average le norm (squared) of the X,'s, and we simply write it as
Recall that is assumed that all the X, 's live in B, In practice, this is enforced by assuming an upper bound B the norms and scaling down all X; by B. As often uses conservatively large B, typical values of tr can be much smaller than 1, so a trace-sensitive algorithm would be
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

d'/4
V/2
va
F-error
Gaussion Mechanism
Our Upper Bound
Lower Bound
Zero Matrix
Vn
Figure 1: Currently known worst-case error bounds (both axes are in log scale).
more desirable. Indeed, Amin et al. [2] take this approach, describing an algorithm with error' O(d%/4 /tr/ yn + vd/n) under zCDP². Note that the vd/n term inherits from mean estimation and the first term is the "extra" difficulty for covariance estimation. In this paper, we improve this term to d V///t// yn (we have similar, albeit lesser, improvement under pure-DP; see Appendix I). Our algorithm is very simple: We first estimate A using the Gaussian mechanism (this is the same as in [2, 22]), then we estimate P by doing an eigendecomposition of E masked with Gaussian noise. Intuitively, we obtain a v factor improvement over the iterative methods of [2, 22], because we can obtain all eigenvectors from one noisy E, while the iterative methods must allocate the privacy budget to all d eigenvectors. Our algorithm is also more efficient, performing just two eigendecompositions and one matrix multiplication, whereas the algorithm in [2, 22] needs (d) such operations.
Implication to worst-case bounds. Covariance matrix has also been studied in the traditional worst-case setting, i.e., the bound should only depend on d and n. Dwork et al. [17] show that the fz-sensitivity of Σ, i.e., maxx-x' Σ(X) Σ(X') where X ~ X' denotes two neighboring datasets that differ by one column, is O(1/n). Thus, the standard Gaussian mechanism achieves an еггor of (dd/n) by adding an independent Gaussian noise of scale ((1/n) to each of the d² entries of Σ. By taking tr = 1, our trace-sensitive bound degenerates into (dd1/4 /n). Note that the vd/n term is dominated by /2/4/v/ ii for d < Ö(r²), which is the parameter regime that allows non-trivial utility (i.e., the error less than 1).
To better understand the situation, it is instructive to compare covariance estimation with mean estimation (where data are also drawn from the E2 unit ball and the error measured in la norm), as the hardness of covariance estimation lies between d-dimensional mean estimation (only estimating the diagonal entries of Σ) and d² di-dimensional mean estimation (treating as d² ---dimensional vector). This observation implies a lower bound M(vd/n following from the same lower bound for mean estimation [19]², and an upper bound Ö(d/n) attained by the Gaussian mechanism. For < O(yn), Kasiviswanathan et al. [23] prove a higher lower bound {((d/n), which means that the complexity of covariance estimation is same dd-dimensional mean estimation in the low- dimensional regime, so one cannot hope to beat the Gaussian mechanism for small d. However, in the high- nigh-diimnsiooall regime, our result indicates that the covariance problem is strictly easier, due to the correlations of the d? entries of Σ. Another interesting consequence is that our error bound has utility for d up to Ö(n²) (utility is lost when the error is Ó(1), as returning a zero matrix can already achieve this error). This is the highest that allows for any utility, since even mean estimation requires d < Ö(n²) to have utility under zCDP [19, 10]. We pictorially show the currently known
We use the Ô notation to suppress the dependency on the privacy parameters and all polylogarithmic factors. We use the base of log (unless stated otherwise) and define log(x) 1 for any e.
"hheir paper states the error bound under pure-DP and for estimating Xx" (i.e., without normalization by
1 l/n) we show how this bound is derived from their result in Appendix C.
'This paper proves the lower bound under the statistical setting: Appendix D. we show how it implies the
claimed lower bound under the empirical setting.
'Their lower bound is under approximate-DD DP, which also holds under zCDP,

---

(worst-case) upper and lower bounds in Figure 1. It remains an interesting open problem to close the gap for (Vv)) < d < Ōnn²).
Through private communication with Aleksandar Nikolov, it is observed that the projection mecha- nism [31, 15] can also be shown have error Odd)/4/vT) when applied to the covariance problem. In Appendix E, we make this connection more explicit, while also giving an efficient implementation. However, the projection mechanism not suce-sensitive.
1.2 A Tail-sensitive Algorithm
A trace-sensitive bound only makes use of the average E2 norm, which cannot capture the full distribution. Next, we design algorithm with an error bound that more closely depends on the distribution of the norms. We characterize this distribution using the T-tail (I(-) is the indicator function):
(X, r) - I -(1xx,ll > =),
(1)
71
Note that (X, decreases as T increases. particular, 7X,0) Lr, (x, =
A common technique to reduce noise, at the expense of some bias, is to clip all the X, so that they have norms most т, for some threshold 5. This yields an error of Noise (o) + (XX,)) where Noise X. r) denotes the error bound of the mechanism when all the X,'s have norm bounded by T, and ? (X,+) r) is the (additional) bias caused by clipping. Opting for the better of the Gaussian mechanism or our trace-sensitive mechanism, we have
Td Vtr
²²vd)
Noise x) = min
(2)
n
V2
The technical challenge is therefore choosing a good in differentially private manner. We design a DP mechanism to choose the optimal t up to a polylogarithmic multiplicative factor and an exponentially small additive term. It also adaptively selects the better of Gaussian mechanism the trace-sensitive mechanism depending on the relationship between d, n, and a privatized tr. More precisely, our adaptive mechanism achieves an eгror of
Ô min (Noise (inise(X7)] X, +XX,(X T)) +2 2-nd
Note that this tail-sensitive bound is always no worse (modulo the 2 term) than Noise( (x,eeXX,)))) (i.e., without clipping), and can be much better for certain norm distributions. particular, the tail-sensitive bound would work very well on many real datasets with skewed distributions, e.g., most data vectors have small norms with a few having large norms. For example, suppose d = 3//4 and a constant number of data vectors have fe norm 1 while the others have norm 1144 Then Vtr ((n0)(n////)))) 1/4), Noise( X, 1) takes the trace-sensitive bound, which is 0(n-9/16). On the other hand, (3) is at most Ö(n 13/16) by taking T 1/4
Related Work
Mean estimation and covariance estimation are perhaps the most fundamental problems in statistics and machine learning, and how to obtain the best estimates while respecting individual's privacy has attracted lot of attention in recent years. Mean estimation under differential privacy is now relatively well understood, with the optimal worst-case error being é(v d/ n) [19], achieved by the standard Gaussian mechanism [17]. In contrast, the covariance problem is more clusive, As indicated in Figure 1, its complexity is probably piccewise linear (in the log-log scale) function.
When most data have norms much smaller than the upper bound given priori, the worst-case bounds above are no longer optimal. In these cases, it is more desirable to have an error bound that is cestance-specific Clipping common technique for mean estimation [3, 18, 4, 34, 29] and known that running the Gaussian mechanism after clipping X with a certain quantile of the norms of the X, 's achieves instance-optimality show in Appendix F that quantile can be the optimal clipping threshold achieving the bound in
certain sense [3, 18). However, for covariance estimation,
3

---

(3). Nevertheless, the bound in (3) is only achieving the optimal clipping threshold; we cannot say that is instance-optimal. since Noise(-) not even known be worst-case optimal.
Closely related to covariance estimation are the PCA problem and low-rank approximation. Instead of finding all eigenvalues and eigenvectors, they only aim at finding the largest one few. For these problems, iterative methods [2, 22, 38, 17, 11, 36] should perform better than the Gaussian mechanism or our algorithm, both of which try to recover the full covariance matrix.
Many covariance estimation algorithms have been proposed under the statistical setting, where the X2 are i.i.d. samples drawn from certain distribution, e.g., multivariate Gaussian [19, 9, 8, 1, 21, 28, 5, 25]. Instead of the Frobenius error, many of them adopt the Mahalanobis error | Σ| == |ー E F/.. which can be considered as normalized version of the former. Σ| & |A E & A1IAA Σ Σ. when Ep is well-conditioned, i.e. \ = O(1), any Frobenius error directly translates to a Mahalanobis error. However, for the Mahalanobis error, the more challenging question is how to deal with an ill-conditioned Σ, for which [19, 8] have provided elegant solutions for the case where D is multivariate Gaussian. It would be interesting to see if their methods can be combined with the tail-sensitive techniques in this paper to solve this problem for other distribution families, in particular, heavy-tailed distributions. For the lower bound, very recently, Kamath et al. [20] proved a similar lower bound for the owwdiimensional regime as in [23] but under the statistical setting.
It known that AaI
3 Preliminaries
3.1 Differential Privacy
We say that X, X'e Rdx= neighbors if they differ by one column, denoted X X'.
Definition 1 (Differential Privacy (DP) [16]). For O and 8 > 0, randomized mechanism
M Rdxn + y satisfics (s, ()PP) if for any X X' and any S = y. Pr[M(X) E s] <
e Pr[MM(X') E 5
In particular, we call it pure-DP if O; otherwise approximate-DP.
Definition (Concentrated Differential Privacy (zCDP) [10D. For p >> randomized mechanism M : dR - y satisfies p-zCDP if for any X ~ X', Da (M(X)JIM(X') < p.a for all a > 1, where Da (M(X)]IM((X') is the a-Rényi divergence between M(X) and M(X).
The relationship between these DP definitions is as follows. Pure-DP, also written as c-DP, implies
2 -CDP, which further implies (= + +ev22oog 1 -DP for any 5 > 0.
To preserve e-DP for query Q, a standard mechanism to add independent Laplace noises with scale proportional to the (global) & fi-sensitivity of Q to each dimension.
Lemma 1 (Laplace Mechanism [13]). Given Q RR - R², let GSq := maxx-x IQ(X) - Q(X')l1 The mechanism M(X) Q(X)= + GSQ Y where Y Lap(1)*, preserves e-DP.
The following composition property of e-DP allows us to design algorithms in a modular fashion. Lemma (Basic Composition). If M is an adaptive composition of mechanisms M1, Mr. where each M, satisfies D,D then M satisfies (E,e,)-DP
For p-zCDP, the standard method is the Gaussian mechanism:
Lemma 3 (Gaussian Mechanism [10].. Given Q Raxn - IR* let GSq ;= maxx-x IQ(X)
Q('') 2- The mechanism M(X) = Q(X) + GSq Y where Y ~ N (0. Taxk), preserves P-2CDP. /Ep
has been shown that the covariance matrix has an fz-sensitivity of v2 [8]. Thus, the Gaussian mechanism for covariance, denoted GaussCov, simply adds an independent Gaussian noise with scale I to each entry of Σ. Considering that Σ symmetric, symmetric noises also suffice, which ypn
preserve the symmetry of the privatized Σ. More precisely, we draw a random noise matrix W where W ~ -N(00,) i.i.d. for & & & and Wk, Wj,k. denoted as W SGW(d). Then GaussCov outputs EGnu = E + Vpn
W.

---

A similar composition property exists for p-zCDP.
Lemma 4 (Composition Theorem [10). If M is an adaptive composition of algorithms My..Mg.....Mp where each M, satisfies Pt-cDDP, then M satisfies (Σ, Pc)=-DDD
3.2 The Sparse Vector Technique
The Sparse Vector Technique (SVT) [14] has as input a sequence of scalar queries, fi(X), f..)
where each has sensitivity 1, and a threshold T. aims find the first query (if there is) whose answer is approximately above T. See Appendix A for the detailed algorithm. The SVT has been shown to satisfy e-DP with following utility guarantee.
Lemma 5 (Extension of Theorem 3.24 in [16]). With probability at least 1- B. SVT returns k such for any i < k. fi(X)= < T + log (2t/))) and if l # + 1, then fx > T log (2g(2t/p) 2)/
3.3 Concentration Inequalities
Lemma ([26)). Given Y (O, Iaxa), with probability least 1 8,
| n(d, == V d 2/ 1og(113))
Lemma 7 26)). Given W ~ SGW(d), with probability at least 1 B.
w & v(d, B) = 2vd 2d log 1/3 d+ 6(1+ (Log //d) Vlogd 2 2 log(113)
Vlog(1 + (log d 1))3)
Also, with probability at least 1 - B.
[ < w) = v 2 d (og((23)) 2 - 1)) + 6 (og((2/3).
Ignoring polylogarithmic factors, 71d, 3) and v(d, B) are both in Ö(vd), while w(d, 3) is in Ö(d). These concentration inequalities are very useful for error analysis. For example, the bound |[]]
immediately implies that GaussCov has error 1 w(d, B) Öddnn).
vpn
4 Trace-sensitive Algorithm
The state-of-the-art trace-sensitive algorithm [2] first obtains an estimate the eigenvalues, and then iteratively finds the eigenvectors by the exponential mechanism (EM), denote this algorithm as EMCov. Under zCDP, it has an error of /tr//////// + vd/n). Below, we present algorithm that is simpler, faster, and more accurate, improving the trace-dependent term by vd-factor.
The first step of our algorithm ScparateCov (shown in Algorithm is basically the same as EMCov, where we obtain an estimate of the eigenvalues with half of the privacy budget. [2] uses Laplace mechanism for pure-DP; for zCDP, we use the Gaussian mechanism, which relies on the fz- fz-sensitivity of A, which we provide in Lemma 10 in the Appendix B. For the eigenvectors, we
GaussCov obtain privatized Eçau with the other half of the privacy budget, and perform cigendecomposition. Finally, we assemble the eigenvalues of eigenvectors to obtain a privatized Σ. should be clear that, after computing Σ, SeparateCov just needs two eigendecompositions and one full matrix multiplication, plus some Odd?) ) operations. On the other hand, EMCov performs (dd) eigendecompositions and matrix multiplications, plus nontrivial sampling procedure for the EM.
That SeparateCov satisfies p-zCDP casily follows from the privacy of the Gaussian mechanism and the composition property. The utility is given by the following theorem:
Theorem Given any > O, for any E Bg and any B O, with probability at least B,
SeparateCov returns a Egep such that Esep ElLF &
22.25 vn
No (d. (d. +
V2 .7 d, 8
Spn
Ô
///44/tr Vn
Vdd
5

---

Algorithm SeparateCov
Input: data X B privacy parameter > 0.
1: A <- the eigenvalues of E X
2: Å Asep - A + v2 Y, where Y N(0,Iax4
vpn
3: EGau - GaussCov(X, 5)
4: Psep < P Gan
5: Ssep P Sop Sep P
Sep
6: return Esep
Remark While SeparateCov strictly improves over EMCov, does dominate GaussCov: When < ((d3/2/n)) SeparateCov is better; otherwise, GaussCov is better. EMCov is better than GaussCov for a smaller trace range: tr Ö(vd/n).
Theorem implies our worst-case bound by taking tr 1:
Theorem 2. Given any > O, for any E Bi and any > O, with probability at least - B,
ScparateCov returns Esep such that Esep E| = Ô
1/ vd vm
5
Tail-sensitive Algorithm
5.1 Clipped Covariance
Clipping is common technique reduce the sensitivity of functions the expense of some bias.
Given T > 0 and a vector X e Rd, let Clip(X, r) min (1, (1. T -X. Similarly, for any X e Rdxn
Clip(X., X, T) denotes the matrix whose columns have been clipped to have norm at most T. Clipping can be applied to both GaussCov and SeparateCov with given т: just run the mechanism on Clip(X,, and scale the result back by 72. We denote the clipped versions of the two mechanisms as ClipGaussCov and ClipSeparateCov, respectively.
The following lemma bounds the bias caused by clipping in terms of the 7-tail as defined in (I).
Lemma 8. [X E(Clip(X, r)) Σ X - 7²) x|xx|2 > 7) (X,, r).
Thus, rumning the better of ClipGaussCov and ClipSeparateCov yields total error of Noise(X X, T.P.3) + (XX, T). where
72 Vpn
2 1-/4 Vn
2 pp
Noise(X, X,,,, 9) min
(d,
VV
d
d
(4)
which is the exact version of (2). Note that the trace-sensitive term is only scaled by which follows from the proof of Theorem when all X; live 7. Ba.
Ideally, we would like to find the optimal noise-bias trade-off, i.e., achieving an error of mini(Noiseed X, + +(X, Two issues need to be addressed towards this goal: The first, minor, issue is that tr is sensitive, so we cannot use it directly to decide whether to use ClipGaussCor or ClipSeparateCov. This can be addressed by using privatized upper bound of tr. The more challenging problem is how to find the optimal T in DP fashion. This problem has been well studied for the clipped mean estimator [18, 3], where it can be shown that setting to be the Ō(v dh largest |x,]|2 results the optimal noise-bias trade-off [18]. Then the problem boils down finding a privatized quantile, for which multiple solutions exist [18, 12, 32, 6, 37J. For the clipped mean estimator, using such a quantile of the norms results in the optimal trade-off because Noise X, 7) takes the simple form largest X&ll2 would also yield an optimal trade-off, as ClipGaussCov is really just clipped mean in d² dimensions. However, due to the trace-sensitive noise term, no longer the case. In Appendix give examples showing that quantile, whose rank may arbitrarily depend on n, can achieve
In fact, we only had ClipGaussCov, setting r to be the Ödd)-th

---

an optimal trade-off even ignoring polylogarithmic factors, It thus calls for new threshold thrssholdfindding mechanism, which we describe next.
5.2 Adaptive Covariance: Finding the Optimal Clipping Threshold
Our basic idea is to try successively smaller values T = 1, 2 ...... As we reduce т, the noise decreases while the bias increases. We should stop when they are approximately balanced, which would yield a near-optimal т.
To do so in DP manner, we need to quantify the noise and bias. Consider the bias first. Given we divide the interval (r, 1] into sub-intervals (r, 27], (2T, .r] I]. For any X such that || (2*, 2* let X Clip(X, r) and then by Lemma 8,
|XX" XX*I & 2 72.
(5)
That is, clipping X can at most lead to 1 n have
(22222 -2) bias. Besides, since ||X E (2", (2*,2*-)) 29,,2=11, we
2 72 & 2 & 2 |X|2-
(6)
Then, given X, for any 8 E Z, we define Count, (X) see for any X ~ X', Count, differs by at most 1, so does the sum of any subset of Count,'s ss We can define upper bound on the bias: Bias(X, X, r) = 1 Di= Count, (22x42 r²). Let
|x,, IXill2 E (2 20t It easy to
X Clip(X, r). By (5) and (6), have
Xx"
XX"
< Bias X, r) & 2 2.277XX11 ((,
By the property of Count,'s s. given any т, the sensitivity of Bias(,, r) is bounded by n.
Now turn to the noise. Recall that Noise (iiise(X,T,,)) T,,, is the smaller of parts. The first part GaussNoise((T, p) := 7² 1 w(d, 3) is independent of X, so can be used directly. The second part depends on tr, is thus sensitive. Since its sensitivity is 4 we can easily privatize it by adding a Gaussian noise of scale + (1)) For technical reasons, we need to use an upper bound, so we add
Vpn
θ (0g(1/3) vpn
to it so as to obtain a privatized tr i tr. Then we set
21.25 SoparateNoiso(ff: T, p. == 5 Dl//nn V
V2.
d, 3 2
d 2
+ +72
Vpn
and use Noise( (Tr, T, P, min (Giuss P, 9), SeparateNoise T, P, B)) as DP upper
bound of Noisc T, P.. Note that given fr, Noisc (fr, T, p, B) is independent of X. Finally, we run SVT on the following sequence of sensitivity-1 queries with T 0:
Dif (, = n [Bias(X (X, 7) No
1, 2 2n
The SVT would return a that balances the bias and noise. After finding such т, we choose to run ei- ther GaussCov or SeparateCov by comparing GaussNoise(T, p, 3) and Separate Gr, T, p. 3). As the sequence consists of dn queries, SVT has an error of (log(dn)). which, we will show, affects the optimality by a logarithmic factor. Meanwhile, the smallest 7 we search over will induce an additive 2 error.
The algorithm above can almost give us the desired eиror bound in (3), except that one thing may go wrong: The SVT introduces error that is a logarithmic factor larger than the optimum, but at least (((1/)). This would be fine as long as there is one X; with || > π(1), so that the optimum error is (((1n)) However, when all the X;'s have very small norms, say 1/n², the ({1/m) error from SVT would not preserve optimality. To address this issue, we first find the radius (X)(X) = max; Xxilz., and use to clip X. The following lemma shows that, under DP, it is possible to find 2-approximation of rad(X) plus additive b that only O(log log(1/b)) vectors are clipped. This allows us to set b 2- while only incurring an Ollog dn) error. Nicely, they match the additive and multiplicative errors that already exist from the SVT, so there is no asymptotic degradation in the optimality.
7

---

Algorithm 2 AdaptiveCor
Input: data X E Bi privacy parameter > 0; high probablity parameter B.
I: f PrivRadius X, x 2-22dm)
2: X Clip X f)
3: tr 1 + 1
2F
N 1) + 2v22/2 vpn /Voo((8/3), 12)
4: min
pm
Diff 5: log, (7) +1 SVT ((Diff 6r :) Diff ((X, fr. F. 21 2: ....,Diffff Diff (xx fr. 2 dn
2 2) ,0 (/2)
6: - min 22+
8) GaussNoisc(f 2 2:2 7: if SeparateNoiso f, 2
8:
Adda - ClipGaussCvv [ 7.
9: else
10: Adda + ClipSeparateCor X, 2.
11:
return Ada
Lemma 9 ([12)). For any > 0, B 0 and > 0, given X E B with probability at least 1 1-8, 3. PrivRadius returns a PrivRadius (X, e, b) such that & 2 raa(()) and
X(]xx > F]1 O (t log log(rad(
The complete algorithm is given in Algorithm 2. Its privacy follows from the privacy of PrivRadius, SVT, GaussCov, SeparateCov, and the composition theorem of zCDP; its utility is analyzed the following theorem:
Theorem 3. Given any > 0 and 3 > O, for any X E By with probability at least 1 - B,
AdaptiveCov returns Ada such that
3) 1og(1/3)1/4
-log(n) + +X,, log(dn/33
Adda
F =0 min Noise
2' 2,,,2'22
X,
+ 2
2-nd dn
12/1
vP
= min (Noise (X, 7X,, T)) + 2 2-du)
6 Experiments
We conducted experiments to evaluate our algorithms on both synthetic and real-world datasets. We compare SeparateCov and AdaptiveCov against GaussCov [17], FMCov [2]. We implemented EMCov in Python following the pseudo-code provided [2] and the descriptions the sampling algorithm in [24]. We also tested CoinPress [8], but since it is designed to minimize the Mahalanobis error, it does not perform well when measured in Frobenius error. The two distance measures coincide when Σ well-conditioned but in this case, CoinPrees degenerates into GaussCov. Therefore, we omit it from the reported results. As baseline, we include returning zero matrix, which has error O(tr), hence a trivial trace-sensitive algorithm. When rad(X) X) is much smaller than 1, it is unfair for GaussCov and EMCov, so we scale all datasets such that 0.5 & rad(X) & 1. As a result, we do need the step to obtain a private radius in AdaptiveCor, either. Each experiment repeated 50 times, and we report the average eπтоr. Furthermore, we have also conducted experiments under pure-DP; the results can be found in Appendix J.
6.1 Synthetie Datasets
We generate synthetic datasets by first following the method in [2), to obtain a matrix X ZU, where U Rd'd is sampled from (0, 1), and Z Raxd sampled from (0 I). Then the vectors in X are adjusted to be centred at and their norms scaled. In [2], the vectors are scaled to have unit lz norm; in our experiments, to better control tr and data skewness, we scale the norms so that they
S 'The code can be found https: / /ttp//gttttttbt http:///w...aat///////tattttttt.

---

Probemuu Enoo
Frobamuus Error
Probanius
10-1
10-1
13-1
10
EMCov
AcaptleeCta
20-1
10
10-1
(a) n = 1000.
(b) 12
4000.
(c) T2 16000.
Figure 2: Results on synthetic datasets fixing tr 1.
Prteens
(a) various tr.
(b) various d.
(c) various
(d) various p.
Figure Results on synthetic datasets as d, n, N or p varies.
follow the Zipf's s law. More precisely, we divide the norms into bins. The number vectors the k-th bin proportional to 1/k" and their norm 2 The parameter characterizes the skewness, which we fix as 8 = 3. Note that N = corresponds to the unit-norm case with Lr =
The results on ir 1 case are shown in Figure 2, which correspond to the worst-case bounds. The here is fixed at 0.1 and we examine the eπror growth w.r.. d for n = 1000, 4000, 16000. The results generally agree with the theory: For low d, GaussCov is (slightly) better than SeparateCov, while the latter is much better for high d. AdaptiveCov is able to choose the better of the two adaptively, with small cost due allocating some privacy budget to estimate tr. Actually, if AdaptiveCov is given the precondition that all norms are 1, this extra cost can be saved.
Next, we vary one of the parameters while fixing the others at their default values d = 200, = 50000, N and p = 0.1, and the results are reported Figure 3. The most interesting case is Figure 3(a), where we increase N, hence reducing Ir, which demonstrates the trace-sensitive bounds. Clearly, GaussCov not trace-sensitive, while the other methods are. fact, returning the zero matrix the best trace-sensitive algorithm if tr is sufficiently small. However, this may not be very meaningful in practice, as N = 2 means that most data have norm 31 but few have norm 1. These few may be outliers and should be removed anyway. Figure 3(b)(d) shows that higher d, smaller and smaller p all have similar effects, i.e., SoparateCov becomes better while GaussCov becomes worse, while AdaptiveCov is able to pick the better one.
Habenius Emor
Frabentus Enror
1.0
10P
10-3
30-1
Prabenius
10-1
10-2
EMCON
Adsphett.
10-2
GaueeCovv
ZaraMartt
SeparassO
10-1
10tH
10tH
10th
107
10
10
10
10a
10th
12
10
10-1
10
10t
10
11
10
(a) 6000, tr < 1.
(b) 20000, tr < 1.
(c) 60000, tr 1.
Figure 4: Results on MNIST dataset.
6.2 Real-world Datasets
We also evaluate the algorithms on two real-world datasets. The first dataset is the MNIST [27] dataset, which contains images of handwritten digits. We use its training dataset which contains 60. 000 images represented as vectors in Zd where d = 784 = 28 28. These vectors are normalized by 2 in the experiments. We estimate E using samples containing all the digits, also estimate Σ corresponding to individual digits (reported in the Appendix J). In the first case, E can be used for further dimensionality reduction analysis; in the second case, individual E can be used for modelling the distributions of individual digits, which together can be used in collective

---

Freberius Eroor
Froberius
10--
Probamius
10-1
10
20m
10
12
10
10-2
13
18
(a) d 32, Lr
1.
(b) d 128, Ur
1.
(c) d 512, Ur
1.
rabenius Error
3.2
EMCCr
Gausakev
AcapiveÇos ZucMaix
Frabenius Error
1.2
12P
Separeecovv
30
Frabenlus
10-
10
10a
15a
10a
10'
10
10
100
10
10
12
10
10
10
10
15"
10
10
(d) d 32,
1.
(0) d 128, tr < 1.
(f) d 512,
1.
Figure Results on the news dataset.
model for classification (e.g. using a mixture model). The second dataset contains news commentary data [33] consisting of approximately 15, 000 articles, each containing 500 4300 words, which we convert into vectors of various dimensions using the hashing trick implemented in the scikit-learn package. In this case, the estimated Σ can be used to help with further feature selection for NLP models, for example. These vectors are normalized to have unit l norm or normalized by the max & norm.
The experimental results on these two real dataset are shown in Figure 4 and 5, where we vary n, and p. respectively. On these results, we see that GaussCov never outperforms SeparateCov. except a very small advantage in a few cases where we have Lr 1, a low d, and high p. Another interesting observation is that AdaptiveCov outperforms both GaussCov and SeparateCov in many cases, something that is not apparent on the synthetic datasets. We believe that this is because these real datasets have heavier tails than the Zipf distribution (we used 3 for Zipf), which makes the adaptive clipping threshold selection more effective. This really demonstrates the benefits of tail-sensitive bound.
Acknowledgements
This work has been supported by HKRGC under grants 16201819, 16205420, and 16205422. We would like thank Aleksandar Nikolov for helpful discussions on the projection mechanism and the anonymous reviewers who have made valuable suggestions on improving the presentation of the paper.
References
[1] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Algorithmic Learning Theory, pages 185 226. PMLR, 2021.
[2] Kareem Amin, Travis Dick, Alex Kulesza, Andrés Munoz Medina, and Sergei Vassilvitskii. Differentially private covariance estimation. In NeurIPS, pages 14190-14199, 2019.
[3] Karcem Amin, Alex Kulesza, Andres Munoz, and Sergei Vassilvtiskii. Bounding user contribu- tions: bias-variance trade-off in differential privacy. International Conference on Machine Learning, pages 263-271 133-271. PMLR, 2019.
[4] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34, 2021.
[5] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Conference on Learning Theory, pages 1075-1076. PMLR, 2022.
10

---

[6] Hilal Asi and John C Duchi. Instance-optimanne in differential privacy via approximate inverse sensitivity mechanisms. Advances neural information processing systems, 33, 2020.
[7] Afonso S Bandeira and Ramon Van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probubility, 44(4):2499-2066, 2016.
[8] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. Advances Neural Information Processing Systems, 33, 2020.
[9] Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. Advances in Neural Information Processing Systems, 32, 2019.
[10] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658 Springer, 2016.
[11] Kamalika Chaudhuri, Anand D Sarwate. and Kaushik Sinha. A near-optimal algorithm for differentially-priiea principal components. Journal of Machine Learning Research, 14, 2013.
[12] Wei Dong and Ke Yi. Universal private estimators. arXiv preprint urXiv:2111.02599: 2021.
[13] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[14] Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 381-390. 2009.
[15] Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete & Computational Geometry, 53(3):650- 673, 2015.
[16] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends@ in Theoretical Computer Science, 9(3-4):211-407 2014.
[17] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang, Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth annual ACM symposium Theory of computing, pages 11-20, 2014.
[18] Ziyue Huang, Yuting Liang, and Ke Yi. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems, 2021.
[19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Proceedings of the 32nd Annual Conference on Learning Theory, COLT 19, pages 1853-1902, 2019.
[20] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and a generalized fingerprinting lemma. arXiv preprint arXiv:2205.088 08532,, 2022.
[21] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationalll--ftiiii estimator for unbounded gaussians. In Conference on Learning Theory, pages 544-572 PMLR, 2022.
[22] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the twenty-fourhh annual ACM-SIAN symposium on Discrete algorithms, pages 1395 1414. SIAM, 2013.
[23] Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 775-784, 2010.
11

---

[24] John T Kent, Asaad M Ganeiber, and Kanti V Mardia. A new unified approach for the simulation of wide class of directional distributions. Journal of Computational and Graphical Statistics, 27(2):291-301, 2018
[25] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabiliz- ing convex relaxations. In Conference on Learning Theory, pages 723-777. 103-777.PMRR, 2022.
[26] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages
2000.
[27] Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. The mnist database of handwritten digits, 1998. Available online at: http://yann. http://aaannncc.n...mm cow/ wwtp/ood///ceeoctotttcttttccccce /edp//xdd/m//// May. 2022.
exdb/mnist/. mnist/. Last accessed:
[28] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statisties high dimensions. In Conference on Learning Theory, pages 167-1244. PMLR, 2022.
[29] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint wxXiv:110.006666 2017.
[30] Aleksandar Nikolov. Private query release via the
transform. arXiv
preprint arXiv:2208. 07410, 2022.
[31] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351-360, 2013.
[32] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007.
[33] Sixth Conference on Machine Translation WMT21. News commentary crawl v16, 2021. Available online at: https: www.wt.tttt....mmm org/ wwwttt/ttranslatiiiiito task. html. Last ac- cessed: May. 2022.
[34] Venkatadheerai Pichapati, Ananda Theertha Suresh, Felix Yu, Sashank J Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv: /908: 07643, 2019.
[35] Holger Sambale. Some notes on concentration for a-subexponential random variables. arXiv preprint arXiv:2002.10661, 2020.
[36] Vikrant Singhal and Thomas Steinke. Privately learning subspaces. Advances in Neural Information Processing Systems, 34:1312-1324, 2021.
[37] Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium Theory of computing, pages 813-822, 2011.
[38] Jalaj Upadhyay. The price privacy for low-rank factorization. In NeurlPS, 2018.
[39] Martin J Wainwright. Higl-ddiensional statistics: A non-asymptotic viewpoint, viewpooinn volume 48. Cambridge University Press, 2019.
12


Reviews:
[{"review_id": "mC6-yuQ0c7-", "reviewer": "Reviewer_vJW1", "summary": "The authors consider the problem of releasing the empirical covariance matrix under concentrated differential privacy. Assuming a boundedness assumption on the l2 norms of the data points, they propose a new algorithm for the problem and show theoretically that it has a better error bound compared to the previous work in the regime where d is very large. They also give a trace-sensitive guarantee to exploit the situations where an average point has a small norm, as well as a tail-sensitive guarantee. \n\nThe first algorithm is a combination of learning the eigenvalues and running PCA. I believe both of these individual steps are known in the literature. The tail sensitive result has more subtleties in order to pick the right threshold to clip the further points. ", "questions": "+ It is somewhat strange that in some experiments the Frobenius error increases with n. Can you elaborate on that?\n\n+ How does your method compare to the previous work in terms of dependence on the privacy parameters?\n\n+ How did you pick epsilon in the experiments?\n\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n+ contributions to a well-defined and well-motivated theoretical problem in the DP literature\n+ simple and intuitive algorithm which is implemented by the authors\n+ empirical results demonstrating the effectiveness of the method\n\nWeaknesses:\n\n+ The problem of mean estimation has been mentioned throughout the text many times but the exact definition is missing. Do you mean estimation w.r.t. l2 error? It will help to define the problem of mean estimation and even covariance estimation formally.\n+ The error bounds are only stated in terms of dimension and number of samples. The dependence on the privacy parameter is not explicit in these results\n+ As far as I can tell, the experiments results also don't mention the value of epsilon either\n+ It is assumed that all data points lie in a unit l2 ball. If we relax this to a ball of radius R, then I believe the authors error bound grows linearly with R. It is not clear if this linear dependence is optimal. Some discussion of the dependence on R will be useful. \n+ in some experiments the error increases with the number of samples, which seems odd.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fe0mhJOY9JZ", "reviewer": "Reviewer_pHxC", "summary": "This paper revisits the problem of differentially private (DP) covariance estimation. It provides bounds for three settings of the problem: (1) worst-case setting, (2) trace-sensitive setting, and (3) tail-sensitive setting. Several improvements are made for certain parameter regimes and types of DP notions over the prior work on this problem, and the algorithms provided are computationally efficient.\n\nIn the worst-case setting, in the high-dimensional case ($d>n^{2/3}$), a separation between the bounds is shown between pure DP and zCDP.\n\nIn the trace-sensitive setting, improvements in both pure DP and zCDP are shown via algorithms that are also more computationally efficient than those of the prior work.\n\nThe tail-sensitive setting also sees some improvements.\n\nBoth theoretical and experimental results are provided in this work, with the latter showing improvements on both synthetic and real-world datasets.\n\nEdit: Updated my score.", "questions": "I do have a few questions.\n\n1. Where are the results for the worst-case setting? I would expect a theorem or something in the main body or somewhere about it. I read a subsection about it in the introduction, but that's pretty much it.\n2. Section 1.2, Line 39. What is $\\Sigma$? Are you defining a notation here, or referencing something else?\n3. Line 41. Is $A = (X_1,\\dots,X_d)$? Or is $A$ the normalised, empirical covariance matrix? Please, be clear about your notations! It's not the responsibility of the reader to infer them.", "limitations": "1. Please, explain what you mean by things like \"worst-case\", \"trace-sensitive\", and \"tail-sensitive\". These terms don't mean anything by themselves, as far as I know. It may be obvious to the authors, but even a one-liner for each in the main body would make it so much easier to distinguish among these settings. It is a little unpleasant as a reviewer and a reader, to be getting into the manuscript without knowing what the context is.\n2. The first part of Lines 29-30 is a bit misleading. The lower bound from [KLSU19] is under a distributional assumption of a Gaussian with an almost identity covariance. The setting in this paper seems more empirical and under bounded norm assumption for the data.\n3. In the second half of Section 1.3 (mostly from Line 75 onward), things don't make a lot of sense here without any context about what these settings are. The results are just stated without any meaning.\n4. In the first paragraph of Section 2, there are really broad statements about the prior work without stating any specific error metrics and range bounds for the data. I would be more specific here.\n5. In the related work about low-rank approximations under DP, I would also state the recent work of Singhal-Steinke 2021 on private subspace estimation.\n6. Also, for the citation of DP with Definition 1, along with [DR14], please use [DMNS06]. The latter is the most important citation for the subject.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Improvements are made upon the prior work in all the three listed settings, which I would say is important. Polynomial improvements in the results over prior work in the listed parameter regimes look quite decent, I think.\n2. The separation in the worst-case setting for the high-dimensional setting between pure DP and zCDP regimes is somewhat significant. It means that for a decent range of parameters, there are newer and better tools at our disposal. I'm not fully convinced though that this regime is the most important one in terms of the significance of the contributions.\n3. The algorithms (SeparateCov and AdaptiveCov) look simple enough, and easy to understand. It is surprising that such simple algorithms are able to improve upon existing work.\n4. The experimental results are also in favour of their work for both synthetic and real-world datasets (MNIST and news commentary). In each, different variations are considered according to different parameters like $n$, $tr$, $d$, and $\\rho$. AdaptiveCov seems more consistent in the experiments on the latter maybe because it seems to be choosing the best of (truncated) SeparateCov and GaussCov.\n\nWeaknesses:\n1. My main complaint with this work is the writing quality. In many places, the notations are unclear, broad statements are made, and things are ill-defined. I will elaborate all of these in later sections of this review.\n2. I'm a little concerned that in the trace-sensitive setting, the SeparateCov algorithm is not able to improve upon the existing work for all settings. For lower trace, SeparateCov is better than GaussCov, but otherwise, it is not. So, it seems to be of limited utility to some extent.\n3. The above seems to be a general concern for me for the entire paper, to be honest. Yes, for a decent range, the worst-case bounds are nicer and give a separation between two forms of DP. I'm not sure how strong the results are owing to these constraints on the dimension.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NE3Ccu3NM_", "reviewer": "Reviewer_YXwa", "summary": "The paper considers the problem of privately estimating the covariance matrix that corresponds to a dataset. Two algorithms are given, with each of them attaining better performance depending on the regime. The first algorithm is *trace sensitive*, in the sense that the error rate depends on the trace of the sample covariance matrix, which is equal to $\\frac{1}{n} \\sum_{i = 1}^n ||X_i||^2$. This algorithm yields a new worst-case upper bound on the error rate of $\\frac{d^{\\frac{1}{4}}}{\\sqrt{n}}$ when $n^{\\frac{2}{3}} \\le d \\le n^2$. The second algorithm is a *tail-sensitive* algorithm, in the sense that the error rate becomes worse when we have more data-points whose $\\ell_2$-norm is close to $1$ (all points are assumed to exist in the unit ball).", "questions": "None for the time being.", "limitations": "The paper is a theoretical work and has no obvious societal impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The problem considered in this work is central to private statistics. Out of the $2$ algorithms proposed in the paper, the one that I found of greater interest was the tail-sensitive one. I found the way SVT was employed in the context of the algorithm to be quite interesting.\n\nWeaknesses: I did not identify any obvious flaws or weaknesses.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HR9NEXNKvIu", "reviewer": "Reviewer_1ufN", "summary": "The paper gives improved error bounds for releasing an approximation of a covariance matrix $\\Sigma$ under approximate differential privacy/zCDP, breaking lower bounds that hold under pure DP for dimension d between n^2/3 and n^2, where n is the number of data points. (Privacy is relative to changing one data point, a d-dimensional *unit vector*.) The new bounds improve both existing worst-case bounds and bounds expressed in terms of the trace of the covariance matrix (generalizing the worst-case bounds) measured in terms of *Frobenius norm* of the error.\n\nThe approach is surprisingly simple, and also more computationally efficient than previous work: Release the eigenvalues with DP by adding noise to the exact eigenvalues. Estimate the eigenvectors by doing an eigendecomposition of the covariance matrix made private using the Gaussian mechanism. Then put everything together. (The paper also has a more sophisticated approach that improves on the simple method in a data-dependent way by carefully clipping data.)\n\nPracticality of the methods is investigated through experimental comparison with the Gaussian mechanism and EMCov (NeurIPS '19). Good improvements are demonstrated on synthetic data as well as two real-world datasets. ", "questions": "* You assume vectors are unit length --- can you say something about to what extent this is a limitation of the approach, or whether (say) you can generalize to vectors with lengths in some fixed range?\n* In the case of vectors from {$-1/\\sqrt{d}, 1/\\sqrt{d}$}$^d$ one can apply results on release of 2-way marginals to estimate the covariance matrix. How do your results compare to that approach?\n* Do you have a use case/justification why one might be interested in the covariance matrix for the data sets you study? If not, are there other data sets with a more compelling use case you could try?\n\nComments\n* It would be good to describe GaussCov together with Algorithm 1, rather than hidden in the preliminaries\n* Line 263: Do you mean $10^{-10}$ rather than $1e^{-10}$?", "limitations": "I am satisfied with the paper discussion of limitations. Since this is a very general question it seems unlikely that there are negative societal impacts (and the authors do not discuss this).", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* A polynomial improvement in error (for sufficiently large dimension) compared to EMCov (NeurIPS '19) as well as the Gaussian mechanism\n* The mechanism is very neat --- it is surprising that it pays off to estimate eigenvalues and eigenvectors separately in different ways\n* Experimental evidence of practicality\n\nWeaknesses\n* It is not clear how the bounds achieved relate to what can be achieved using general query release methods, for example simhash combined with methods for release of 2-way marginals\n* There is no experimental comparison to CoinPress (NeurIPS '20), since CoinPress optimizes a Manahalobis distance and in general performs poorly in terms of Frobenius error; however there are covariance matrices for which these distance measures coincide, and where a comparison would make sense\n* Arguably, for the real-world data sets used in experiments it does not seem natural to be interested in computing the covariance matrix", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept