标题： 相关噪声在差分隐私学习中确实优于独立噪声 显示英文标题

标题： Correlated Noise Provably Beats Independent Noise for Differentially Private Learning

摘要： 差分隐私学习算法在学习过程中注入噪声。 虽然最常用的隐私学习算法DP-SGD在每次迭代中添加独立的高斯噪声，但关于矩阵分解机制的最新研究表明，在噪声中引入相关性可以显著提高其效用。 我们对任何相关函数选择的渐近学习效用进行了表征，为线性回归给出了精确的解析边界，并为一般的凸函数作为凸规划的解。 我们使用这些边界表明，相关噪声在问题参数（如有效维度和条件数）作为函数时，可以证明优于普通的DP-SGD。 此外，我们对于近似最优相关函数的解析表达式避免了之前工作中用于优化噪声相关矩阵的半定程序的立方复杂度。 我们在私有深度学习上进行了实验来验证我们的理论。 我们的工作在计算和内存方面都高效，同时匹配或超过了之前的工作。 显示英文摘要

摘要： Differentially private learning algorithms inject noise into the learning process. While the most common private learning algorithm, DP-SGD, adds independent Gaussian noise in each iteration, recent work on matrix factorization mechanisms has shown empirically that introducing correlations in the noise can greatly improve their utility. We characterize the asymptotic learning utility for any choice of the correlation function, giving precise analytical bounds for linear regression and as the solution to a convex program for general convex functions. We show, using these bounds, how correlated noise provably improves upon vanilla DP-SGD as a function of problem parameters such as the effective dimension and condition number. Moreover, our analytical expression for the near-optimal correlation function circumvents the cubic complexity of the semi-definite program used to optimize the noise correlation matrix in previous work. We validate our theory with experiments on private deep learning. Our work matches or outperforms prior work while being efficient both in terms of compute and memory.