Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
Authors: Oren Mangoubi
Nisheeth K Vishnoi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
Dyson Brownian Motion
Random Matrices
Rank-k Covariance Approximation
Subspace Recovery

Abstract: Given a symmetric matrix $M$ and a vector $\lambda$, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for  approximating $M$ by a matrix whose spectrum is $\lambda$, under $(\varepsilon,\delta)$-differential privacy. Our bounds depend on both $\lambda$ and the gaps in the eigenvalues of $M$, and hold whenever the top $k+1$ eigenvalues of $M$ have sufficiently large gaps. When applied to the problems of private rank-$k$ covariance matrix approximation and subspace recovery, our bounds yield improvements over previous bounds. Our bounds are obtained by viewing the addition of Gaussian noise as a continuous-time matrix Brownian motion. This viewpoint allows us to track the evolution of eigenvalues and eigenvectors of the matrix, which are governed by  stochastic differential equations discovered by Dyson. These equations allow us to bound the utility as the square-root of a sum-of-squares of perturbations to the eigenvectors, as opposed to a sum of perturbation bounds obtained via Davis-Kahan-type theorems.


Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
Oren Mangoubi Worcester Polytechnic Institute
Nisheeth K. Vishnoi Yale University
Abstract
Given a symmetric matrix and a vector X, we present new bounds on the Frobenius-distamte
utility of the Gaussian mechanism for approximat- ing M by a matrix whose spectrum is A, under (e, d)-differential privacy. Our bounds depend on both À and the gaps in the eigenvalues of M, and hold whenever the top + eigenvalues of M have sufficiently large gaps. When applied to the problems of private rank-k covariance matrix approx- imation and subspace recovery, our bounds yield improvements over pre- vious bounds. Our bounds obtained by viewing the addition of Gaus- sian noise as a contimuous-time matrix Brownian motion. This viewpoint allows us to track the evolution of cigenvalucs and cigenvectors of the ma- trix, which are governed by stochastic differential equations discovered by Dyson. These equations allow a sun-of-squares of perturbations to the eigenvectors, as opposed to a sum of perturbation bounds obtained via Davis- Davis-Kahan type theorems.
bound the utility as the square-rool of
Introduction
Given a dataset A E Rexd which consists of m individuals with d-dimensional features, methods for preprocessing or prediction from A often use the covariance matrix M := A of A. In many such applications one computes a rank-k approximation to M or finds matrix close to M with specified sot of cigenvalucs À = (AI,..., Aa) include the rank-k covariance matrix approximation problem where one seeks to compute rank-k matrix which minimizes given distance to M, and the subspace recovery problem where the goal is to compute a rank k-projection matrix H V.VV. where Vi. is the x & matrix whose columns are the top-k eigenvectors of M. These matrix approximation problems are ubiquitous in ML. and have rich algorithmic history; see 24
37 23
36
Examples
10
In some cases, the rows of correspond sensitive features of individuals and the release of solutions to aforementioned matrix approximation problems may reveal their private information, e.g., as in the case of the Netflix prize problem 5 Differential privacy (DP) has become a popular notion to quantify the extent to which an algorithm preserves privacy of individuals [6 Algorithms for solving low-rank matrix approximation problems have been widely studied under DP constraints
BC 7 19 Ii. Notions of DP studied in the
19 which is the notion we study in this paper, To define nolion of DP in problems involving two matrices M = A A and M' -A A' are said to be neighbors if they arise from A, A' which differ by most one row and as, oftentimes done, require that each row of the datasets A' has norm at most 1. For any E, 8 2 0, randomized mechanism A (e, diffforrryyy private for all neighbors M' E Rddd and any measurable subset S of outputs of A, we have P(A(M) e S) (PA(M) 5)+6.
literature include (c, 6DD
17
25
26
as well as pure (e, O) 1n covariance matrices, following 7 17
3D
2
32
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

The problem. We consider a class of problems where one wishes to compute an approxi- mation a symmetric d x matrix under (e, d--dfferret privacy constraints. Specifically, given M A A for A mmxd together with vector À of target eigenvalues A 2 ..... 2 Ad, the goal is output dxd matrix Hl with eigenvalues À which minimizes the Probenius-norm distance || H|| under (e, dddifferrnnt privacy constrainis Here H is the matrix with eigenvalues À and the same eigenvectors as M. This class of problems includes as a special A 0.
case the subspace recovery problem if we set \ It also includes the rank-k covariance approximation problems if we set X = o; for S k, where 01 2 2 oa are the eigenvalues of M. Since revealing 0,8 may violate privacy constraints, the eigenvalues of the output matrix A should not be the same those of H.
A = 1 and Ab+1
Various distance functions have been used in the literature to evaluate the utility of (E, DP mechanisms for matrix approximation problems, including the Frobenius norm distance HH- (e.g. I9 2
Jand the Frobenius inner product utility (M, H H) (e.g.
[1 I 2
Note that while a bound | f| S b implies an upper bound on the inner product utility of (M, H fr I | (by the Cauchy-Schwarz inequality), an upper bound on the inner product utility does not (in general) imply any upper bound on the Frobenius-norm distance. Moreover, the Frobenius-norm distance can be a good utility metric to use the goal is to recover a low rank matrix H from a dataset of noisy observations (see e.g. 12]. Hence, we use the Frobenius-norm distance to measure the utility of an (e.6)-DP mechanism.
Related work. The problem of approximating a matrix under differential privacy con- straints has been widely studied. In particular, prior works have provided algorithms for problems where the goal is to approximate a covariance matrix under differential privacy constraints, including rank-k PCA and subspace recovery 77. 30 19
as well as rank-k covariance matrix approximation 7 L Another set of works have studiod the problem of approximating rectangular data matrix A under DP 7 II 25 26 We note that upper bounds on the utility of differentialll-priiate mechanisms for rectaugular matrix approx- imation problems can grow with the number of datapoints m, while those for covariance matrix approximation problems oftentimes depend only on the dimension d of the covariance matrix and do not grow with imation problems such as rank-k covariance matrix approximation and subspace recovery are the most relevant to our paper. The notion of DP varies among the different works on differentially--rivate matrix approximation, with many of these works considering the
3%
Prior works which deal with covariance matrix approx-
notion (c, 8)-D 25 28 10
while other works focus (pure) (c, DP 30
2
33
19 analyze a version of the Gaussian mech- anism of [6 : where one perturbs the entries of M by adding a symmetric matrix E with ii.d. Gaussian entries N(0, /le),))/e), to obtain an (efff-dlifrrenntiall private mechanism which outputs a perturbed matrix M M + E. One can then post-process this matrix M to obtain a rank-k k projection matrix which projects onto the subspace spanned by the top-k eigenvectors of M (for the rank-k PCA or subspace recovery problem), or a rank-k matrix fl with the same top-k eigenvectors and eigenvalues as M (for the rank-k covariance matrix approximation problem). 16 consider different notions of utility in their results, including the inner product utility (for PCA), and the Frobenius-now norm and speetral-norm distance distances (for low-rank approximation and subspace recovery).
Analysis of the Gaussian mechaviss in 1
In one set of results, I9 give lower utility bounds of (²(kvd) w.h.p. for the rank-k PCA problem with respect to the inner product utility (M, H), together with matching upper bounds provided by post-processing of the Gaussian mechanism, where Ω hides polynomial factors of 1 and log(z) (their Theorems 3 and 18). As noted by the authors, their lower bounds are tight for matrices M with the "worst-case" spectral profile a, but they can obtain improved upper bounds for matrices M where d%. F > ((VV) (Theorem 3 of 19]
For the subspace recovery problem, M0 obtain Frobenins-distance bound of | H < Ô (Vid/(o -0+1)) w.h.p. for a post-processing of the Gaussian mechanism whenever Tk 0 > Ω(vā) (implied by their Theorem 6, which is stated for the spectral norm). And for the rank-k covariance matrix approximation problem, [9 show a utility bound of
2

---

1 I ((kvd) w.h.p. for a post- post-processing of the Gaussian mechanism (Theorem 7 in [ ) and also give related bounds for the spectral norm. While their Frobe- nius bound for the covariance matrix approximation problem is independent of the number of datapoints m, it may not be tight. For instance, when = d, one can easily obtain a better bound since, by the triangle incquality, || M - || M I || H F = || S ((d) w.h.p., since || is just the norm of a vector of d2 Gaus- || - = sians with variance (1). Moreover, the bound for the the rank-k covariance approximation problem, | - H| F < (kvv)) d), is also a worst-case upper bound for any spectral profile as the right hand side of the bound not depend on the eigenvalues a.
Thus, a question arises of whether the Frobenius-norm utility bounds for the rank-k coveri- ance matria approzimation and subspace recovery problems are tight for all spectral profiles a, and whether the analysis of the Gaussian mechanism can be improved to achieve bet- ter utility bounds. A more general question is to obtaán utility bounds for the Gaussian mechanism for the matrir approzimation problems for arbitrary X.
utility Our contribution. Our main result is new upper bound on the Frobenius- of the Gaussian mechanism for the general matrix approximation problem for a given M and X (Theorem 2.2 Our bound depends on the eigenvalues of M and the entries of X.
The novel insight is to view the perturbed matrix M + E as a continuous-tim symmetric matrix diffusion, where each entry of the matrix M + E' is the value reached by a (one- dimensional) Brownian motion after some time T = Vlog( motion, which we denote by ((), induces a stochastic process on the eigenvalues 7h (I) 2 ... 2 (a((t) and corresponding eigenvectors u1 (t)t...... ua(t) of ((t) originally discovered by Dyson and now referred to as Dyson Brownian motion, with initial values (0))) = o, and
This malrix-valued Brownian
(,) which are the eigenvalues and eigenvectors of the initial matrix M 20
We then use the stochastic differential equations the cigenvalues and cigenvectors of the Dyson Brownian motion, to track the perturbations to each eigenvector. Roughly speaking, these equations say that, as the Dyson Brownian motion evolves over time, every pair of eigenvalues 7a(() and (y((), and corresponding eigen- with the magnitude of the interaction term proportional to 7x( at any given time t. This allows us to bound the perturbation of the eigenvectors at every time 4, provided that the initial gaps in the top 1+1 eigenvalues of the input matrix are 2 ((vd) (Assumption 2.1 Empirically, we observe that Assumption 2.1 is satisfied for covariance matrices of many real-world datasets (see Appendix Jh. as well as on Wishart random matrices W = A A, where A is an m x d matrix of i.i.d. Gaussian entries, for sufficiently large m (see Appendix D]. We then derive a stochastic differential equation which tracks how the utility changes as the Dyson Brownian motion evolves over time (Lemma 4.1. and integrate this differential equation over time to obtain a bound on the (expectation of) the utility B|||A - H||r (Temma 4.5) as a function of the gaps (tt) (t).).
and which govern the evolution of
vectors (t) and (I))), interacts with the other eigenvaluu//iigeneecal
Plugging in basic estimates (Lemma 4.4 for the eigenvalue gaps xt()) (t) to Lemma
4.5 we obtain a bound on the expected utility E[]] - H||e] (Theorem 2.2 for the different matrix approximation problems
function of the eigenvalue gaps o, σ, of the input
matrix M. Roughly speaking, our bound is the square-root of sum-of-squaree of the ratios, \,-,, of eigenvalue gaps of the input and output matrices.
When applied to the rank-k covariance matrix approximation problem (Corollary 2.3 The- orem 2.2 implies bound of E[JAA H [[] S Ó(Vkd) whenever the eigenvalues of the input matrix M satisfy a - x++ 2 l(ax)) and the gaps in top k + eigenvalues sat- isfy a, - 0:41 2 ((vd). Thus, when M satisfies the above condition on our bound improves by a factor of vix the (expectation of) the previous bound of [1] which says that | M][F || M|lF < Ō(kvd) w.h.p., since by the triangle incquality | M|[F - || - M|]F < fl H||.. This condition on is satisfied, e.g., for ma- trices M whose eigenvalue gaps are at least as large as those of the Wishart random co- variance matrices with sufficienlly many datapoints m (see Section 2 for details). And,
3

---

if a is such that o; 0411 2 N(0x - Tk+1) for S k, Theorem 2. implies a bound of
B =]] - ((v((ox=-<)))) for the subspace recovery problem (Corollary 2.4 improv-
ing by factor of Vk (in expectation) the previous bound of 19 which implies that | M | F S O (Vod/(o)))111)) w.h.p.
Results
Our main result (Theorem 2.2 gives and unified upper bound on the Frobenius norm utility of a post-processing of the Gaussian mechanism, for the general matrix approximation problem where one is given a symmetric matrix M Raxdd and a vector À with A1 2 ... 2 Ad, and the goal is to compute matrix H with eigenvalues À which minimizes the distance || Hlr. Here H is the matrix with eigenvalues À and the same eigenvectors as M. Plugging in different choices of to Thcorem 2.2, we obtain as corollarics new Frobenius- distance utility bounds for the rank-k covariance matrix approximation problem (Corollary 2.3 and the subspace recovery problem (Corollary 2.4.. Our results rely on the following assumption about the eigenvalues of the input matrix M:
Assumption 2.1 ((M, k E1) Eigenvalue gaps). The gaps in the top h + eigenvalues
eigenvalues 01 2 ... 2 oa of the matriz M E Raxd satisfy o; 0+11 2 8 8oog 22
Vd +
3 log (Azk) for every i [k].
We observe empirically that Assumption 2.1 is satisfied on number of real-world datasets which were previously used as benchmarks the differentially private matrix approximation literature I 2 (see Appendix D.. Assumption 2.1 is also satisfied, for instance, by random Wishart matrices W = A A, where A is an m x d matrix of i.i.d. Gaussian entries, which are popular model for sample covariance matricos ir This bocause the minimum gap o; - of a Wishart matrix grows proportional to /m with high probability; thus for large enough m, Assumption 2.1 holds (see Appendix for details). Hence, the assumption requires that the gaps in the top k- eigenvalues of M are at least large as the gaps in a random Wishart matrix.
Theorem 2.2 (Main result). Let E, > O, and given a symemelric matrix M E Rdddd 2 ... 2 aa and corvesponding orthonornal eigenveclors ......y va-
with eigenwalues Let G be a matria with i..dd. NO,, entries, and consider the mechanism that oulputs
M M + V2log( L2b (G + GT). Then such mechanism is (c, -diffferrret private. Moreover, let \1 5 ... 2 As and k E [d] be any numbers such that X; = for > k, and define and V [ul,..., val, and define ōi 2 .... 2 δa to be the eigenvalues of M with corresponding orthonormal eigenvectors 01,..., δa and V 1......, _0)-- Then if M satisfies Assumption 2.1 for (M, k. X1, E, 8), we have
A ;=
d
(4--21²
log(
EE [IRADT- 1P 0O
Σ
(a: (
g2
The fact that the mechanism in this theorem is (e, diffeereeell private follows from stan- dard results about the Gaussian mechanism [ Given any list of eigenvalues X, and letting = diag(A), one can post-process the matrix M by computing its spectral decomposition M = VΣLT and replacing its cigenvalues to obtain a matrix VAFT with eigenvalues and eigenvectors V. Since VAÍT is a post-processing of the Gaussian mechanism, the mecha- nism which outputs TA TT is differentially private as well. Theorem 2.2 bounds the excess utility E[[ÍAÄT VAVT [12.1 (whenever the gaps in the eigenvalues d1 2 2.. 2 aa the input matrix satisfy Assumption 2.1 as sum-of-squares of the ratio of the gaps X; Xÿ in the given cigenvalues to the corresponding gaps d; - max(o TR+1) ) in the eigenvalues of the input matrix (note that X; Aÿ A max AR+1) since A = 0 for
k 1).
While we do not know if Theorem 2.2 is tight for all choices of and k, it does give tight bound for some problems. Namely, when applied to the covariance matrix estimation

---

problem, in the special case where A = d Theorem 2.2 implies a bound of B[I - M] -
(G GGG the matrix M - M has independent Gaussian entries with mean zero and variance ((1) and we have from concentration results for Gaussian random matrices (see e,g, Theorem 2.3.6 of [ that B|||M- M || = (dd), implying that the bound in Theorem 2.2 is tight in this case.
Ö(Vkd) O(d) (see Corollary 2.3 Since M M 2 logi Li
The proof of Theorem 2.2 differs from prior works, including that of I which use Davis- Kahan-type theorems
and trace inequalities, and instead relies on an interpretation of the Gaussian mechanism as diffusion process which may be of independent interest (See K for additional comparison
previous approaches). This connection allows us to use sophisticated tools from stochastic differential equations and random matrix theory. We present an outline of the proof in Section
Appendix
Application to covariance matrix approximation: Plugging A; = o, for i is k and X; = 0 for i > k into Theorem 2.2 and plugging in concentration bounds for the perturbation to the eigenvalues di, we obtain utility bounds for covariance matrix approximation:
Corollary 2.3 (Rank-k covariance matrix approximation). Let e, > O, and given a symmetric matrix M Raxd with eigenvalues d1 2 2.... oa and corresponding orthonormal eigenvectors vi...., Va- Let G be a matrix with i.i.d. (0, entries, and consider the mechonism that outputs M- M + 22loo( - (G+ GT). Then such mechanism is (E, differentially private. Moreover, for any
e k E [d], define Σn == diag(o1....., ....,)).)))) and
V = [ui....,,d.] and define 81 2 ... ....... 2ā to be the eigenvolues of M with corresponding orthonormal eigenvectors 01...., Gd, and define Exx diag(ā ,,, .....)) 0) and V == Then if M satisfies Assumption 2.1 for (M, (4,,0,,,,, and defining aut1 == 0,
have
E BIIVESOT -VEV |1
so @0(vdd [kdxx
log²
Ok 0k+1
The proof appears in Appendix
G Tf oz ak+1 M(xx), then Corollary 2.3 implies that
E -
[|x]
kd
log (+)
Thus, for matrices M with eigenvalues sat-
isfying Assumption 2.1 and where ox 0bt1 M((x)), Corollary 2.3 improves by factor of Vk on the bound in Theorem of I Ō(kvZ) w.h.p.. This is because an upper bound on || PT VV,V bound on |JVÉ& VT M] - [[E hand, while their result does not require a bound the gaps in the eigenvalue of M and bounds their utility w.h.p., our Corollary 2.4 requires a bound on the gaps of the top k + eigenvalues of M and bounds the expected utility E VT - VV&V [|]]
which says ||V
M ||VE VT M
- ||r implies an upper -M]rr by the triangle incquality. On the other
Application to subspace recovery: Plugging in a ... = A = 1 and A = A==0, O, the post-processigg step Theorem 2.2 outputs a projection matrix, and we obtain utility bounds for the subspace recovery problem.
Corollary 2.4 (Subspace recovery). Let e, > 0, and given a symmetric matria M Raxd with eigenvalues 01 2 ... 2 aa and corresponding orthonormal eigenvectors 2I...., Va. Let G be a matrir with i.i.d. N(0, entries, and consider the mechanism that
outputs M. M + /2log(
(G + GT). Then such mechanism is (E, -)fffffrrent private. Moreover, for any k E [d], define the d x k matrices V = [vi...., vb) and
VE [f,,...,ūk,, where ōr ... 2 ôs denote the eigenvalues of M with corvesponding
orthonormal eigenvectors 01...., dg. Then if M satisfies Assumption 2.1 for (M, k. 2, 6),
we have E |IVEE - VAVI |1 s 0h-0k11
vkd x log2(t)
Moreover, if we also have that
o, 0++1 D(0r I2+1) 1) for all i k, then
Va
log (t)
E [ VT V.VV lle] 50
x
Th -
5

---

The proof appears in Appendix
H
For matrices M satistying Assumption 2.1 the first
inequality of Corollary 2.4 recovers (in expectation) the Frobenius-norm utility bound im-
plied by Theorem 6 of 19
which states that V|V&V V 11. S
ok- x log log²(1) (1)
vkd
w.h.p. Moreover, for many input matrices M with spectral profiles 2 .... 2 satisfying
Assumption 2.1 Theorem 2.2 implies stronger bounds than those in [0] for the subspace
recovery problem. For instance, if we also have that 0++1 2 Q2(0 x++1) for all i < k
the bound given in the second inequality of Corollary 2.4 improves on the bound of 19 by
a factor of VE. On the other hand, while their result only requires that σß 0k+1 Vd and bounds the Frobenius distance [1V V bound on the gaps of the top & + eigenvalues of M and bounds the expected Frobenius distance V V.V, [|]].
k || w.h.p. our Corollary 2.4 requires a
3 Preliminaries
Brownian motion and stochastic calculus. A Brownian motion W(t) in is a con- timuous process that has stationary independent increments (sce c-g., 3 In multi- dimensional Brownian motion, each coordinate is an independent and identical Brownian motion. The filtration F, generated by ((1) is defined as (Usgio(W(s))) where o(2) is the o-algebra generated by Ω. (()) is a martingale with respect to F..
Definition 3.1 (Itō Integral). Let W(t) be a Brownian motion for 2 0, let F, be the filtration generated by (t), and let z(t) Fi R be stochastic process adapted to Fi. The Itō integral is defined as 1o¹ z(t)dW((t) == lim Ee 2(tw) x [W(i+ 1)w) (iw)).
Lemma 3.1 (Itô's Lemma, integral form with no drift; Theorem 3.7.1 of 31) Let R T + R be any twice- citee-ddffreeniibblee function. Let (t) E Ra be a Brownian motion, and let (1) E TR" be an Itô diffusion process with mean zero defined by the following stochastic differential equation:
dx,(t) = Σ (t)(t)d
(1)
for some Itō diffusion R(t) guxn adapted to the filtration generated by the Brownian motion (t). Then for any T 2 0,
f(X(T)) - f(x(0))
0x, f((()) Ree(t)dW.(t)
n1
ox,ox, ox,ox, ((X(6)) R. (e)(())
E-
Dyson Brownian motion. Let ((t) Raxd be matrix where each entry is
independent standard Brownian motion with distribution N(O,tTa) at time t, and let B(I) W(I) + WT().. Define the symmetric-matrix valued stochastic process &(1) as
follows:
(1) = + B())
(2)
The process (t) is referred to as (matrix) Dyson Brownian motion. At every time > the eigenvalues ?1 (a....,,a()) of +(t) are distinct with probability 1, and 2 induces stochastic process on the eigenvalues and eigenvectors. The process on the eigenvalues and eigenvectors be expressed via the following diffusion equations. The eigenvaluc diffusion process, which is also referred to as (eigenvalue) "Dyson Brownian motion", is defined by the stochastic differential equation
3 The (eigenvalue) Dyson Brownian motion an Itō diffusion and can be expressed can be expressed by the following stochastic differential equation 20
drx(t) dBB((t + Σ
1
dt
Vi E [d].t 0.
(3)
3æ1 7:(1)
(1)))

---

The corresponding cigenvector process 21 (t)....... va(t), referred to as the Dyson vector flow, also an Itō diffusion and, conditional on the eigenvalue process can be expressed by the following stochastic differential equation (see e.g., ):
(1)(() = Σ (t) J#L 71(() (1) 41(()
E (x(()) 75 (1)) (1)
dt
Vi [c]. 0.
(4)
2
Eigenvalue bounds. The following two Lemmas will help us bound the gaps in the eigenvalues of the Dyson Brownian motion:
Lemma 3.2 (Thoorem 4.4.5 of E special case D. Let W e Rdxd with iid. 1(), entrics. Then P([]W]|2 > 2(vd + 8) < 2e-5" for any > O.
Lemma 3.3 (Weyl's Inequality; G).. A, Rdxd two symmetric matrices, and denoting the i i'th-largest eigenvalue of any symmetric matrir M by o;(M), we have (,(A) o. s ( B) S {(() + (B).
4 Proof of Theorem 2.2
along with the main technical lemmaas used to prove this result. Section 4.1 outlines the different steps in our proof. In Steps and 2 construct the matrix-valued diffusion used in our proof. Steps 3,4, and 5 present the main technical lemmas, and in step we explain how to complete the proof. The statements of the lemmas and the highlights of their proofs, are given in Sections
We give an overview of the proof of Theorem 2.2
4.4. In section we explain how to complete the proof. The full proofs are deferred to the appendix.
4.1 Outline of proof
1. Step 1: Exprcssing the Gaussian Mechanism as a Dyson Brownian Motion. To obtain our utility bound, we view the Gaussian mechanism as matrix-valued Brownian motion P initialized at the input matrix M: ((1) == M + -()
AI 0. If we run this Brownian motion for time T = ( we have that ( = (V2log( (G+
recovering the output of the Gaussian mechanism. In other words, the input to the Gaussian mechanism is .M = (0), and the output is M = (TT).
2. Step 2: Expressing the post-processed mechanism as a matrix diffusion (t).. Our goal is to bound [ V VAV [[x where M = VEVT and M = VDVT are spectral decompositions of M and M. To bound the error | - VAVT]| || we will define a stochastic process (t) such that (0)) = VAVT and (t()) VAPT, and then bound the Frobenius distance [T) (())] by integrating the (stochastic) derivative of (t) over the time interval [0,
Towards this end, at every time I, let (()) (U) be a spectral decomposition of the symmetric matrix ((t,, where T(t) is a diagonal matrix with diagonal entries (t 2 ... 2 Ta(t) that are the eigenvalues of D(t), and (tt) = [t), ua(t)] is a d x orthogonal matrix whose columns 81 (t), ua((t an orthonormal basis of eigenvectors of (t). At every time t, define (t) to be the symmetric matrix with eigenvalues A and eigenvectors given by the columns of U(t): (t) (t) Vt E [0.
Step 3: Computing the stochastic derivative (t). To bound the expected squared Frobenius distance Ei]| (T) - (0) 1 we first compute the stochastic derivative d' of the matrix diffusion & (T) (Lemma
4. Step 4: Bounding the eigenvalue gaps. The equation for the derivative dV in- cludes terms with magnitude proportional to the inverse of the eigenvalue gaps (t) == (t) (t) for each i,j E [d], which evolve over time. In order bound these terms,
we use Weyl's inequality (Lemma 3.3 to show that w.h.p. the gaps in the top k +
eigenvalues A,y (t) satisfy (t) Ma - о,) for every time E [0, 7] (Lemma
'The theorem is stated for sub- Gob-Gasssian entries in terms of constant C; this constant is C - in the special case where the entries N 1) Gaussian.

---

provided that the initial gaps are sufficiently large (Assumption 2.1 (See Appendix for discussion on why we need this assumption for our proof to work).
Step 5: Integrating the stochastic differential equation. Next, we express the expected squared Frobenius distance B|] ( (O)l as integral
E
10' (t)
We then apply Ito's Lemma (Lemma 3.10 to obtain formula for this
integral. Roughly speaking, the formula we obtain (Lemma 4.5 is
B B(IV(T) ((0)
(A: 211² A (1)
X
E
d1+T
E
di
j
im
(5)
6. Step 6: Completing the proof. Plugging the bound At)(1) 2 N( ..)
into
5 and
noting that the first term on the r.h.s. of is least as large the second term since o, jj 2 Vd, we obtain the bound in Theorem 2.2
4.2
Step 3: Computing the stochastic derivative dv((t)
(t) is itself matrix-valued diffusion. We use the eigenvalue and eigenvector dynamics 3 and g together with Itô's Lemina (Lemına 3.1p to compute the Itō derivative this
diffusion. Towards this end, we first decompose the matrix (t) as sum of its eigenvectors:
(t) = Et (t), (t). Thus, we have
dv Σ (td(u(t)
(6)
We begin by computing the stochastic derivative (t), (t)) for each i E [d], by applying the formula for the derivative of ut(t) in e together with Itô's Lemma (Lemma 3.1
Lemma 4.1 (Stochastic derivative of uz(()uz (1)). For all 1 E [0, T, d(u,(t)u, (1) =
dt,,(t) Ejtt (0) (t), (t) + u, (t) (t)) + E (xx0) (t), (t) - (t)t (t)).
The proof in Appendix Plugging Lemma 4.1 into 6
we get an expression for d()(()):
Lemma 4.2 (Stochastic derivative of (1() see Appendix for proof). For all t E [0, we have that (t) = 1/2 Σ Ej 1))00)0 (u.(f)u, (t) + (t))u, + dt
dB,(()
E Ej X1) (x(0) (x)))= uz (f)u, [t),
4.3 Step 4: Bounding the eigenvalue gaps
The derivative in Lemma 1.2 contains terms with magnitude proportional to the inverse of the cigenvalue gaps Ay (t) := (y) To bound these terms, we would like to show that in., (t) 2 D(a=-00 for each < k+1 with high probability. Towards this end, we first apply the spectral norm concentration bound for Gaussian random matrices (Lemma 3.2 which provides high-probability bound for [B(t)]
any time i, together with Doob & submartingale inequality, to show that the spectral norm of the matrix-valued Brownian motion B(t) does not exceed TVd at any time t E [0, T w.h.p.:
Lemma 4.3 (Spectral norm bound). For every T
0,
we have,
(uupreoo, |IB())] 27 2T + < 22/TE" ST.
The proof appears in Appendix Next, we use Lemma 4.3 to bound the eigenvalue gaps:
Lemma 4.4 (Eigenvalue gap bound). Whenever (0) (0)
> 4T
for every i E S and T > 0 and some subset S C (d - 1}, we have
P (Uies (nfre)o.rnuu(t)) (t) < ((x((0) (0)) a)}) < 2 -yaa
8

---

To prove Lemma 4.4 we plug Lemma 4.3 into Weyl's Inequality (Lemma 3.3 to show that
71(1) - (+) 2 o, 0++1 - B()12 2 D(a; 0++ TV 2 0(0 0(+1),
with high probability for each i < k (Lemma 1.4) The last inequality holds since Assump-
tion 2.1 ensures o, - -++1 2 1TVV for S k. The full proof is in Appendix D
4.4 Step 5: Integrating the stochastic differential equation
Next, we would like to integrale the derivative (v(()) to obtain an expression for ((I( (()) [, and to then plug in our high-probability bounds (Lemma 4.4 for the gaps (t)(). To allow us to later plug in these high-probability bounds after we integrate and take the expectation, we define a new diffusion process (t) which has nearly the same stochastic differential equation as 4.2. except that cach cigenvaluc gap (t)(t) is not permitted to become smaller than the value Th 2o, - max(o,, oxx()) for each <-
Towards this end, fix any 17 E Rdddd define the following matrix-vale valued Itō diffusion (,)
via its ltō derivative dZ,, (t):
(B dl,(() = 2 Ejj; Mr X max AA, (i) (w: (1) (1) + uz((),] (!)
Σ ii=1 Σ Estt(2 (A+ X1) max (0,, u4 (t)u,, (t),
de
(7)
with initial condition (0) (0). Thus, Z,(()= (0) + So (s) for all 0. We then integrate (t), over the time interval [0, 7], and apply Itô's Lemma (Lemma 3.1 to obtain an expression for the Frobenius norm of this integral:
Lemma 4.5 (Frobenius distance integral). For any T 0, E
Zn (T) Zn (0)l
2 2
Ei Ejji max A2,
(2-21 dt
+ 10
E
(Ejze
max (1) )3}
27
dt.
-i=1
To prove Lemma 4.5 we write
(T) - Z0) = 2 h Σ
dB,
Dr A,1
max A.y (t),, my)) (un(t)u} (t) + (t(4 (t))
2
:=1 jf
T
dt
Σ
(D: X1)
u, ut(t)u (t).
(8)
max (t)
To compute the Frobenius norm of the first term on the r.h.s. of S we use Itô's Lemma
(Lemma 3.10, with (() = for Σd Ejet |A
A m
(s) (us (s) (s) + (s) (s))
and the function S(X)= = || = E Ej= x²- By Itô's Lemma, we have
E(IX (x(0)
ΣΣ
Ox
f.r 0.3
f(X(6))
+ 2.0 2,T bJ
(9)
OXi,OXa0
14.-2,1 where R(or)(s) (t) == Imax(|A.(00)mm (u, (t) + (t) (6)) [e, rl, and where we denote by either Her or [[ the (e, rhth entry any matrix H.
The first term on the r.h.s. of g is equal to zero since (s) is independent of both X and R(t) for all s 2 t and the time-integral of each Brownian motion increment d (s) has zero mean. To compute the second term on the r.h.s. of 9 we use the fact that
2 0x, f(X) is equal to 2 for i j and O for i $
To compute the Frobenius norm of the second term on the r.h.s. of Schwarz inequality. The full proof appears in Appendix B
we use the Cauchy-
9

---

4.5
Step 6: Completing the proof
To complete the proof, we plug in the higg--robbbbility bounds on the sigenvalue gaps from
Section 4.3 into Lemma 4.5 Since by Lemma 4.4 (1) 2 2 - -oy w.h.p. for each
i,j S +++ 1, and Thi = (o; max(d,, 0k+1)), we must also have that (t) (t) for
all L E [), w.h.p. Plugging in the high-probability bounds A,y(1) 2 { oz) for each
i 2 k + 1, and noting that X X 0 for all i.j > k, we get that
E [IVAVT
VAV
T
13
E
1 (T) ((O)
(oz o,)² )
2
T
(): 22)²
T E
A; Aj
2
E
dt + T
Σ
dt
(o; - o,)²
0
jæi
jzi
k
d
(): 2,)²
A
A X (0; max ok+1))?
(10)
(0: - max j. 0k+1))
1=1+1
j=1+1
Since (a; max( ((vd) for all i S h and E [d], can use the Cauchy- Schwarz inequality to show that the second term is (up to a factor of T) smaller than the
2, first term: Ej=tt1 (o: -xxxm((())
Plugging E E (o. max-
(A.-2,)²
T = Vllog( into 10 we obtain the bound in Thcorem 2.2 For the full proof of
Theorem 2.2 see Appendix
5 Conclusion and Future Work
We present a new analysis of the Gaussian mechanism for a large class of symmetric matrix approximation problems, by viewing this mechanism Dyson Brownian motion initialized at the input matrix M. This viewpoint allows us to leverage the stochastic differential equations which govern the evolution of the cigenvalues and eigenvectors of Dyson Brownian motion to obtain new utility bounds for the Gaussian mechanism. To obtain our utility bounds, we show that the gaps Aiy(t) (t) in the eigenvalues of the Dyson Brownian motion stay at least as large as the initial gap sizes (up to a constant factor), as long as the initial gaps in the top k ++ 11 eigenvalues of the input matrix are 2 2(vZ) (Assumption 2.1
While we observe that our assumption the top-k+11 cigenvalue gaps holds multiple real- world datasets, in practice one may need to apply differentially private matrix approximation any matrix where the "effective rank" of the matrix is k- that is, on any matrix where the k'th eigenvalue gap a 0k+1 is large- including on matrices where the gaps in the other eigenvalues may not be large and may even be zero. Unfortunately, for matrices with initial gaps in the top-k eigenvalues smaller than O(vd), the gaps (i)(t) in the eigenvalues of the Dyson Brownian motion become small enough that the expectation of the (inverse) second moment term 10,0) appearing in the Itô integral (Lemma 4.5) in our analysis may
be very large even infinite. Thus, the main question that remains open is whether one can obtain similar bounds on the utility for differentially private matrix approximation for any initial matrix M where the k'th gap σx okt1 is large, without any assumption on the gaps between the other eigenvalues of M.
Finally, this paper analyzes a mechanism in differential privacy, which has many implications for preserving sensitive information of individuals. Thus, we believe our work will have positive socictal impacts and do not foresce any negative impacts to society.
Acknowledgments and Disclosure of Funding
This research was supported in part by NSF CCF- CCF-2204528 and awards.
10

---

References
[4] Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approx- imations. Journal of the ACM (JACM), 54(2):1-19, 2007.
[2] Kareem Amin, Travis Dick, Alex Kulesza, Andres Munoz, and Sergei Vassilvitskin Disferentially private covariance estimation. Advances in Neural Information Processing Systems, 32, 2019.
3] Grog W Anderson, Alice Guionnet, and Ofer Zeitouni. An introduction to random matrices. Number 118. Cambridge university press, 2010.
[4] Ludwig Arnold. On wigner's semicircle law for the eigenvalues of random matrices. Zeitschrift für Wadhrschennicckeetstheeee und verwandte Gebiete, 19(3):191-199 1971.
5) James Bennett and Stan Lanning. The Netflix Prize. In Proceedings of KDD cup and workshop, volune 2007, page 35. New York, NY, USA., 2007.
66 Rajendra Bhatia. Matris analysis, volume 169. Springer Science & Business Media, 2013.
7 Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the beenty-fourll ACM SIGMOD-SIGACT- SIGART symposium on Principles of database systems, pages 128 128-138, 2005.
88 Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. Cambridge University Press, 2020.
19] Paul Bourgade. Extreme gaps between eigenvalues of Wigner matrices. Journal of the European Mathematical Society, 2021.
[10] Emmanuel J Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEFE, 08(6))925-933) 2010.
[11] Kamalika Chaudhuri, Anand Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. Advances in neural information processing systems, 25, 2012.
[12] Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal of Selected Topics in Signal Processing, 10(4):608 622, 2016.
[13] Chandler Davis and William Morton Kahan. The rotation of eigenvectors by pertur- bation. iii SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[14] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[15] Cynthia Dwork. Differential Privacy. In ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 1-12. Springer, 2006.
[16] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Arneal In- lernational Conference on the Theory and Applications of Cryplographic Techniques, Springer, 2006.
pages 486-503
[17] 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.
[18] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trendso in Theoretical Computer Science, 9(3 4):211-4400 407, 2014.
[19] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze Gauss: optimal bounds for privacy-preservin principal component analysis. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May June 03, 2014, pages 11 11-20, 2014.
11

---

[20] Freeman J Dyson. A nownian-motion model for the eigenvalues of a random matrix. Journal of Mathematical Physics, 3(6):1191-1198, 1962.
[21] László Erdös and Horng-Two Tzer Yau. Universality of local spectral statistics of random matrices. Bulletin of the American Mathematical Society, 49(3):377 414, 2012.
[22] Renjie Feng, Gang Tian, and Dongyi Wei. Small gaps of GOE. Geometric and Func- tional Analysis, 29(6)179 1827, 2019.
[33] Alessio Figalli and Alice Guionnet. Universality in several- models via approxi- mate transport maps. Acta mathematica, 217 2016.
[24] Alon Gonem and Ram Gilad-Bachrach, Smooth sensitivity based approach for differ- entially private pea. In Algorithmic Learning Theory, pages 438-450. PMLR, 2018.
[25] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1255-1268, 2012.
[26] Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 331 340, 2013.
[27] Jiaoyang Huang, Benjamin Landon, and Horng- Yau. Bulk universality of sparse random matrices. Journal of Mathematical Physics, 56(12):123301, 2015.
[28] Mia Hubert and Sanne Engelen. Robust PCA and classification in biosciences. Bioin- formatics, 20(11):1728-1736 2004.
[29] Gareth James, Danicla Witten, Trevor Hastic, and Robert Tibshirani. An introduction statistical learning, volume 112. Springer, 2013.
(30] Michael Kapralov and Kunal Talwar. On differentially private low rank approxima- tion. In Proceedings of the twenby-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1395 1414. SIAM, 2013.
[31] Gregory F Lawler. Stochastic calculus: An introduction with applications. American Mathematical Society, 2010.
[32] Jonathan Leake, Colin S. McSwiggen, and Nisheeth K. Vishnoi. Sampling matrices from Seahhhhhhadrr--tttttee and differential privacy. In STOC, pages
Zuber densities with applications to quantum inference
ACM, 2021.
[33] Jonathan Leake and Nishocth K. Vishnoi. On the computability of continuous maxi- mum entropy distributions with applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Compuling, pages 930 943, 2020.
[34] Peter Mörters and Yuval Peres. Brownion motion, volume 30. Cambridge University Press, 2010.
[35] LA Pastur and VA Martchenko. The distribution of eigenvalues in certain sets of random matrices. Math. USSR-Sbornia 1(4):457 -83, 1967.
[36] Haipeng Shen and Jianhua Z Huang. Sparse principal component analysis via regular- ized low rank matrix approximation. Journal of multivariate analysis, 1661110115), 2008.
[37] Azer P Shikhalicv, Loe Potter, and Yucjic Chi. Low-rank structured covariance matrix estimation. IEEE Signal Processing Letters, 26(5):700-704, 2019.
[88 Jack W Silverstein. The smallest eigenvalue of a large dimensional wishart matrix. The Annals of Probability, pages 1364-1368, 1985.
(39] Terence Tao. Topics random matria theory, volume 132. American Mathematical Soc., 2012.
12

---

[40] Terence Tao and Van Vu. Random matrices: universality of local eigenvalue statistics.
Acta mathematico, 206(1):127-200) 2011.
[41] Terence Tao and Van Vu. Random covariance matrices: Universality of local statistics of eigenvalues. The Annals of Probability, 40(3):1285 1315, 2012.
[42] Craig A Tracy and Harold Widom. Level-spacing distributions and the airy kernel. Communications in Mathematical Physics, 159(11:111174, 1994.
[43] Roman Vershynin. High-dimennsoonll probabilily: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[44] Pierpaolo Vivo, Satya N Majundar, and Oriol Bohigas. Large deviations of the maxi- mum eigenvalue in wishart random matrices. Journal of Physics A: Mathematical and Theoretionl, 40116)33317, 2007.
[45) Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low- rank gradient compression for distributed optimization. Advances in Neural Informa- tion Processing Systems, 32, 2019.
[46] Ke Wang. Random covariance matrices: Universality of local statistics of cigenvalues up to the edge. Random Matrices: Theory and Applications, 1(01):1150005, 2012.
[47] John Wishart. The generalised product moment distribution in samples from normal multivariate population. Biometrika, pages 32 52, 1928.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for infor- mation on how to answer these questions. For each question, change the default [TODO] to [Yes]] [No] or [N/A]- You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [N/A]
Did you include the license to the code and datasets? [N/A]
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the guestions/answers answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(See Section 5
(d) Have you read the ethics review guidelines and ensured that your paper con-
forms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set assumptions all theoretical results? Yes] (See
Section 2 and Assumption 2.1
(b) Did you include complete proofs of all theoretical results?
[Yes]
(See Section
and Appendix A
H
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes]
(See Appendix !
(b) Did you specily all the training details (e.g., data splits, hyperparameterss, how they were chosen)? [Yes] (See Appendix !
(c) Did you report error bars (e.g,, with respect to the random seed after rumning
experiments multiple times)? [Yes] (See Appendix [
(d) Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] (See Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as
URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/ soougg/curatnng [N/A]
(c) Did you discuss whether the data you are using/curatin /uraatig contains personally 5. Tf you used crowdsourcing or conducted research with human subjects...
identifiable information or offensive content? [N/A]
(a) Did you include the full text of instructions given to participants and screen- shots, if applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total
amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "mxMZX53_kn7", "reviewer": "Reviewer_6MaL", "summary": "The authors consider the problem where, given a symmetric matrix $M$ and a vector of eigenvalues $\\lambda$, we want to privately estimate a matrix that shares the same set of orthogonal unit eigenvectors as $M$ and has eigenvalues $\\lambda$. They obtain new bounds for this problem thanks to a novel interpretation of the Gaussian noise as a Dyson Brownian motion. They apply their results to obtain bounds for covariance estimation, low-rank approximation and subspace recovery.", "questions": "The thing I mainly want to ask from the authors it to justify Assumption 2.1 in the context of the problems they are considering e.g., by giving pointers to other papers with similar assumptions that are from the covariance estimation/PCA literature. Currently, I am leaning towards rejecting the paper, but I am willing to raise my score if the authors can convince me that their assumption is justified within the context of the problems considered and has not simply been imported from SDEs/random matrix theory.\n\n=== UPDATE ===\n\nAfter taking into account the rebuttal and discussion with other reviewers and the AC, I decided to raise my score from 4 to 6.", "limitations": "This is a purely theoretical paper, so it doesn't have an obvious societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The interpretation of the Gaussian mechanism as an SDE is novel to the best of my knowledge and the way it is leveraged to obtain new bounds for these classic problems in private statistics is interesting.\n\nWeakness: My main issue with the paper is that I feel that Assumption 2.1 is contrived. The authors argue that this condition is satisfied whp by Wishart matrices. However, other works I've read e.g., on the topics of PCA or subspace recovery assume that we have a range of eigenvalues (say the top $k$ eigenvalues) which are similar in magnitude, whereas there are gaps between them and the smaller eigenvalues. Judging based on that, I feel it's unnatural to assume the existence of additive gaps among the ``large\" eigenvalues.\n\nComment: I have not gone through the proofs in the appendix in detail, because I am not too familiar with SDEs, so I can't really follow their low-level aspects. However, the high level picture described in the main body seems reasonable and I couldn't find any obvious faults.", "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": "jeB79LIeRjA", "reviewer": "Reviewer_RW4L", "summary": "This paper gives a new analysis of the Gaussian noise mechanism for approximating covariances matrices with differential privacy. The basic mechanism is quite simple: given a private covariance matrix $M$, add a Gaussian noise matrix $E$ to form $\\hat{M} = M + E$. For an appropriate choice of the variance of the Gaussian, $\\hat{M}$ preserves differential privacy. Then one can use post-processing to compute some function of $f(\\hat{M})$ and hope that this approximates $f(M)$. For example, $f( . )$ could be projection on the span of the top $k$ eigenvalues, or the best rank $k$ approximation.\n\nThe performance of the Gaussian noise mechanism for this class of problems was analyzed in an important prior paper of Dwork, Talwar, Thakurta, and Zhang. They also showed that, for some problems, the mechanism is worst-case optimal, and gave improved guarantees when the input matrix satisfies some spectral assumptions (large gaps between eigenvalues). \n\nThe present paper gives a different analysis of the Gaussian noise mechanism, based on viewing the $\\hat{M}$ as the value of a matrix-valued Brownian motion at some time $T$, where the Brownian motion starts at $M$. This induces an Ito process on the eigenvalues and eigenvectors of the matrix, and allows using Ito calculus to bound the error of the Gaussian noise mechanism for problems of the type described above. Generally, the bounds are better than prior work, but, as far as I understand, require stricter assumptions on the spectrum of $M$.", "questions": "Can you give an argument why the stochastic calculus techniques give results that could not be proved with the techniques of [15], even under the stronger assumptions made in this paper? An informal argument would also be helpful. \n\nHow can one use your analysis to give error bounds for covariance approximation, given that the eigenvalues of $M$ are private information and should not be used in post-processing without adding noise to them?", "limitations": "I don’t have concerns. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The new method of analysis via stochastic calculus is, in my opinion, the strongest point about this paper. This is a new approach, and may prove fruitful for other problems, or for deriving tighter error bounds.\n\nOn the other hand, the results themselves are hard to compare with prior work, since they require significantly stronger spectral assumptions. The authors also don’t clarify why these types of results cannot be proved using the techniques of reference [15]. This makes it hard to appreciate what is gained by adopting the machinery of stochastic calculus. It would be nice to have at least one application where the new analysis gives better results than prior work, without making any additional assumptions.\n\nI also don’t understand how the results in this paper can be used for covariance approximation. The algorithm seems to require public knowledge of the eigenvalues of the input covariance matrix, but this is private information. The authors make one cryptic comment about this, but I still don’t understand how their framework can be used for this problem to get an actual differentially private algorithm.", "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": "I8SSxNiixCM", "reviewer": "Reviewer_uAWo", "summary": "This paper provides a new upper bound on the Frobenius-distance utility of the Gaussian mechanism for the general matrix approximation problem under differential privacy. The analysis utilize Dyson Brownian motion to track the evolution of the utility, which is, to my best knowledge, the first application of this mathematical tool. ", "questions": "1. Can the author provide more examples and concrete justification  on the assumption 2.1?\n2. The bound achieved in [15] is high probability bound while Theorem 2.2 is an expectation bound? Is it fair to direct compare these results?", "limitations": "The major limitation is the assumption seems to be too strong.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nOriginality: This paper's contribution is original given that this is the first improvement of the utility bound of Gaussian mechanism. It is very interesting to see the application of stochastic differential equations together with dyson brownian motion to be applied in the proof.\nQuality: I briefly checked the proof, it looks sound to my best knowledge.\nClarity: Overall the paper is well organized. The problem studied, existing results, the major contribution are clearly stated. I have no difficulty in reading the paper.\nSignificance: From my own perspective, I would value this improvement of the utility bound. First, the matrix recovery problem and its privacy problem are critical in applications such as recommender systems. Second, existing result is definitely not tight and thus an improvement should be expected.\n\nWeakness:\nSignificance: My major concern is on the assumption 2.1. It requires very specific eigengap conditions. Though the paper proves that Wishart matrices  satisfy this condition. It would be better to provide more justifications and examples on the assumption.", "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": "FfuPio0V_cl", "reviewer": "Reviewer_utx8", "summary": "This paper discusses a matrix approximation in the context privacy using Dyson Brownian motion. By assuming a gap in eigenvalues, the authors established an error bound in privacy.", "questions": "The paper is well written and I don’t have questions.", "limitations": "NA", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, easy to understand, and scientifically correct. In addition, it is the first time I have seen that DBM is used to prove results in privacy setting.\nHowever, I have two concerns. First the paper is not that relevant to ML community, and it is essentially a problem of matrix approximation, and privacy just provides some possible context. Second the results in the paper are conceptually easy, and not too profound (most based on well known properties of stochastic calculus and DBM).", "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