Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)
This work addresses the challenge of achieving tighter DP guarantees for iterative learning algorithms, which is crucial for privacy-preserving machine learning in sensitive domains.
The paper tackles the problem of overly conservative differential privacy (DP) bounds in stochastic gradient descent (SGD) by proving that hiding the algorithm's internal state leads to converging privacy bounds, which are substantially smaller than prior composition-based bounds after a few training epochs.
Prior work on differential privacy analysis of randomized SGD algorithms relies on composition theorems, where the implicit (unrealistic) assumption is that the internal state of the iterative algorithm is revealed to the adversary. As a result, the Rényi DP bounds derived by such composition-based analyses linearly grow with the number of training epochs. When the internal state of the algorithm is hidden, we prove a converging privacy bound for noisy stochastic gradient descent (on strongly convex smooth loss functions). We show how to take advantage of privacy amplification by sub-sampling and randomized post-processing, and prove the dynamics of privacy bound for "shuffle and partition" and "sample without replacement" stochastic mini-batch gradient descent schemes. We prove that, in these settings, our privacy bound converges exponentially fast and is substantially smaller than the composition bounds, notably after a few number of training epochs. Thus, unless the DP algorithm converges fast, our privacy analysis shows that hidden state analysis can significantly amplify differential privacy.