Timezone: »

 
Spotlight
Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
Oren Mangoubi · Nisheeth Vishnoi

Tue Dec 06 05:00 PM -- 07:00 PM (PST) @
in Lightning Talks 2A-1 »
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.
Keywords: differential privacy · Rank-k Covariance Approximation · Dyson Brownian Motion · Subspace Recovery · Random Matrices
[ Slides] 

Author Information

Oren Mangoubi (Worcester Polytechnic Institute)
Nisheeth Vishnoi (Yale University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors