Correlated Noise Provably Beats Independent Noise for Differentially Private Learning

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

abstract algorithm algorithms arxiv correlations cs.ai cs.cr cs.lg factorization independent iteration math.oc matrix noise process type utility while work