Correlating Cross-Iteration Noise for DP-SGD using Model Curvature

Differentially private stochastic gradient descent (DP-SGD) is used to train deep learning models while mitigating many privacy risks. One popular line of work, designed to chip away at the accuracy gap between DP-SGD and normal SGD training, is known as DP-MF. To each update, it adds privacy noise that is correlated across training iterations, so that later noise partially cancels out earlier noise. The noise correlation structure is determined by solving an optimization problem, but a key question is not well-understood: what important properties does the noise correlation need in order to improve accuracy? In this paper, we identify two ways that noise affects the training trajectory --- noise alters the *value* of the gradient, and also alters the *location* at which subsequent gradients are computed. Prior works addressed the first but overlooked the second effect, realizing only limited benefits. Our analysis results in a new objective function for determining cross-iteration noise correlation. Our technique, NoiseCurve, consistently improves accuracy over DP-BandMF, the state-of-the-art DP-MF scheme, on various computer vision and NLP tasks. NoiseCurve uses an upper bound $\hat{H}$ on the Hessians of the loss that could be encountered during training. We show how to estimate $\hat{H}$ using public data and evaluate robustness to errors in $\hat{H}$. To avoid direct computation of $\hat{H}$, or even its eigenspectrum, we show how to adapt the Lanczos method.