论文标题
重新分析高斯：通过Dyson Brownian Motion的私人矩阵近似的界限
Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson Brownian Motion
论文作者
论文摘要
给定对称矩阵$ m $和vector $λ$，我们在高斯机制的Frobenius-Distance效用上提出了新的界限，该机制可通过矩阵近似$ m $的矩阵，其频谱为$λ$，低于$（\ varepsilon，δ）$ - 差异私密。我们的界限取决于$λ$和$ m $的特征值的差距，并且只要$ m $的最高$ k+1 $ eigenvalues都会有足够的差距。当应用于私人排名问题-K $协方差矩阵近似和子空间恢复时，我们的界限比以前的界限会提高。我们的边界是通过将高斯噪声视为连续时间矩阵布朗尼运动来获得的。该观点使我们能够跟踪基质的特征值和特征向量的演变，这些矩阵由戴森发现的随机微分方程控制。这些方程式使我们能够将效用作为平方根的扰动总和与特征向量的平方根，而不是通过Davis-Kahan型定理获得的扰动范围之和。
Given a symmetric matrix $M$ and a vector $λ$, we present new bounds on the Frobenius-distance utility of the Gaussian mechanism for approximating $M$ by a matrix whose spectrum is $λ$, under $(\varepsilon,δ)$-differential privacy. Our bounds depend on both $λ$ 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.
