Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification

By Yingxue Zhou, Zhiwei Steven Wu, Arindam Banerjee. 2020

122 citations recorded by the source corpus.

Differentially private SGD (DP-SGD) is one of the most popular methods for solving differentially private empirical risk minimization (ERM). Due to its noisy perturbation on each gradient update, the error rate of DP-SGD scales with the ambient dimension $p$, the number of parameters in the model. Such dependence can be problematic for over-parameterized models where $p \gg n$, the number of training samples. Existing lower bounds on private ERM show that such dependence on $p$ is inevitable in the worst case. In this paper, we circumvent the dependence on the ambient dimension by leveraging a low-dimensional structure of gradient space in deep networks---that is, the stochastic gradients for deep nets usually stay in a low dimensional subspace in the training process. We propose Projected DP-SGD that performs noise reduction by projecting the noisy gradients to a low-dimensional subspace, which is given by the top gradient eigenspace on a small public dataset. We provide a general sample complexity analysis on the public dataset for the gradient subspace identification problem and demonstrate that under certain low-dimensional assumptions the public sample complexity only grows logarithmically in $p$. Finally, we provide a theoretical analysis and empirical evaluations to show that our method can substantially improve the accuracy of DP-SGD.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Differentially Private Fine-tuning of Language Models (2021, background): “Another recent idea uses a small amount of public data to identify a lower-dimensional subspace of the gradients in which to perform private descent (Zhou et al., 2021; Yu et al., 2021a; Kairouz et al., 2021).”
Unlocking High-Accuracy Differentially Private Image Classification through Scale (2022, background): “Consequently, many works have focused either on developing specialized architectures for private training (Papernot et al., 2021; Tramèr and Boneh, 2021), or on reducing the dimensionality of the model during training (Golatkar et al., 2022; Yu et al., 2021b; Zhang et al., 2021; Zhou et al., 2021).”
Large Language Models Can Be Strong Differentially Private Learners (2021, background): “On the other hand, Zhou et al. (2020); Kairouz et al. (2020) remove the ambient dimension dependence of DP noise by identifying subspaces in which private gradients lie and would be privatized.”