@inproceedings{
choquette-choo2023correlated,
title={Correlated Noise Provably Beats Independent Noise for Differentially Private Learning},
author={Christopher Choquette-Choo and Krishnamurthy Dvijotham and Krishna Pillutla and Arun Ganesh and Thomas Steinke and Abhradeep Guha Thakurta},
booktitle={International Workshop on Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023},
year={2023},
url={https://openreview.net/forum?id=AbrnDOw8R9}
}
Differentially private learning algorithms inject noise into the learning where the most common private learning algorithm, DP-SGD, adds independent Gaussian noise in each iteration. Motivated by the practical considerations in federated learning, recent work on matrix factorization mechanisms has shown empirically that introducing correlations in the noise can greatly improve their utility. We characterize the asymptotic objective suboptimality for any choice of the correlation function, giving precise analytical bounds for linear regression. 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 in prior work. We validate these theoretical results with experiments on private deep learning in both centralized and federated settings. Our work matches or outperforms prior work while being efficient both in terms of computation and memory.
Correlated Noise Provably Beats Independent Noise for Differentially Private Learning
Christopher A. Choquette-Choo Krishnamurthy Dj Dvijotham Krishna Pillutla Arun Ganesh Thomas Steinke Abhradeep Guha Thakurta