Correlated Noise Provably Beats Independent Noise for Differentially Private Learning

arXiv:2310.06771v2 Announce Type: replace-cross
Abstract: 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 …

algorithm algorithms arxiv can cs.ai cs.cr cs.lg inject math.oc matrix noise private process utility work