Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams
Serguei Denissov, Hugh Brendan McMahan, J Keith Rush, Adam Smith, Abhradeep Guha Thakurta
Abstract
Motivated by recent applications requiring differential privacy in the setting of adaptive streams, we investigate the question of optimal instantiations of the matrix mechanism in this setting. We prove fundamental theoretical results on the applicability of matrix factorizations to the adaptive streaming setting, and provide a new parameter-free fixed-point algorithm for computing optimal factorizations. We instantiate this framework with respect to concrete matrices which arise naturally in the machine learning setting, and train user-level differentially private models with the resulting optimal mechanisms, yielding significant improvements on a notable problem in federated learning with user-level differential privacy.
BibTeX
@inproceedings{
denissov2022improved,
title={Improved Differential Privacy for {SGD} via Optimal Private Linear Operators on Adaptive Streams},
author={Serguei Denissov and Hugh Brendan McMahan and J Keith Rush and Adam Smith and Abhradeep Guha Thakurta},
booktitle={Advances in Neural Information Processing Systems},
editor={Alice H. Oh and Alekh Agarwal and Danielle Belgrave and Kyunghyun Cho},
year={2022},
url={https://openreview.net/forum?id=i9XrHJoyLqJ}
}