Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams

Sergey DenisovH. Brendan McMahanJohn RushAdam D. SmithAbhradeep Guha Thakurta

article2022NeurIPS85 citations

Develops an efficient fixed-point algorithm to compute optimal matrix factorizations for the Gaussian matrix mechanism under adaptive streams, significantly outperforming tree-based methods and narrowing the utility gap to non-private training in federated learning.

Listen

Modern privacy-preserving machine learning frequently relies on differential privacy—a mathematical standard ensuring that individual training records cannot be reconstructed or memorized by a model. Iterative training methods like stochastic gradient descent require cumulative updates across streaming data where future computations adaptively depend on previous outputs. Existing differential privacy mechanisms for streaming data rely predominantly on binary tree structures, which introduce structural estimation errors and inefficiencies, or offline matrix mechanisms whose theoretical guarantees were previously not proven to hold in adaptive, real-time streaming settings.

The article demonstrates that the matrix mechanism with Gaussian noise guarantees differential privacy over adaptive data streams, introduces an efficient method to compute optimal matrix factorizations for optimization algorithms, and shows substantial accuracy gains in privacy-preserving language modeling. Specifically, the analysis establishes mathematical equivalence between nonadaptive and adaptive privacy guarantees for Gaussian noise addition over lower-triangular query operations. To compute optimal factorizations, the article formulates a parameter-free fixed-point algorithm with a quantifiable duality gap that rapidly minimizes expected reconstruction error. The framework extends beyond simple cumulative gradient additions by directly factoring matrices representing optimization mechanics such as momentum and planned learning rate schedules.

The findings establish that any lower-triangular linear query mechanism utilizing calibrated Gaussian noise retains its differential privacy guarantees even under adaptive adversarial streams. In numerical evaluations, the fixed-point optimization algorithm converged to lower error solutions in under three minutes on large matrices, outperforming prior optimization methods that required over eighty minutes. When applied to real-world language modeling within federated learning on the StackOverflow benchmark, the optimal matrix mechanism combined with learning rate cooldown closed roughly two-thirds of the utility gap between previous private state-of-the-art methods and non-private training baselines across various privacy budgets.

These results provide a practical and theoretically grounded foundation for deploying differentially private optimization algorithms without incurring large utility losses. By mathematically absorbing momentum and learning rate schedules directly into the noise-calibrated linear operator, organizations can achieve tighter privacy protections with higher model accuracy. Stakeholders should adopt optimal matrix factorization algorithms in place of conventional tree-based streaming aggregations for production deployments of differentially private machine learning. Where model dimensionality or sequence lengths present computational bottlenecks, teams should utilize banded, low-rank approximations to maintain scalable execution. Further work is recommended to validate these techniques across multi-pass training environments, as the primary guarantees in this evaluation assume single-pass data processing.

Boston University Google University of Wisconsin Madison data stream differential privacies differential privacy private SGD optimal private linear operators

arXiv: 2202.08312

Paper: Deep Learning with Differential Privacy, Martín Abadi et al. (2016). Introduces differentially private stochastic gradient descent (DP-SGD) with gradient clipping and calibrated Gaussian noise, establishing the foundational optimization paradigm that the source improves via optimal matrix mechanisms.
Paper: Adaptive Federated Optimization, Sashank Reddi et al. (2020). Establishes adaptive federated optimization techniques and empirical benchmarks (such as Stack Overflow tag prediction) that the source directly targets and enhances with private linear operators.
Paper: What Can We Learn Privately?, Shiva Prasad Kasiviswanathan et al. (2008). Provides the theoretical foundations and sample complexity bounds for learning under differential privacy constraints, essential for understanding formal DP guarantees.
Paper: Differentially Private Federated Learning: A Client Level Perspective, Robin C. Geyer et al. (2017). Examines client-level differential privacy in federated optimization via clipped model updates and noise addition, motivating the source's focus on streaming private mechanisms.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). Introduces adaptive subgradient methods and historical gradient accumulation for optimization, which the source extends into noise-calibrated linear streaming operators.
Paper: Differentially Private Empirical Risk Minimization, Kamalika Chaudhuri et al. (2009). Pioneers objective and output perturbation techniques for empirical risk minimization under differential privacy, providing core intuition for private optimization mechanics.
Paper: Federated Learning With Differential Privacy: Algorithms and Performance Analysis, Kang Wei et al. (2019). Analyzes the convergence trade-offs of noising model updates before aggregation in distributed networks, establishing key context for private federated learning.
Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). Presents core principles of online convex optimization and regret minimization over dynamic and adversarial data streams.

Paper: Hyperparameter Tuning with Renyi Differential Privacy, Nicolas Papernot et al. (2022). Builds on private iterative optimization by addressing the cumulative privacy loss incurred during repeated hyperparameter selection using Rényi differential privacy.
Paper: Deep Unlearning via Randomized Conditionally Independent Hessians, Ronak Mehta et al. (2022). Applies differential privacy noise mechanisms and localized parameter updates to achieve efficient post-hoc deep machine unlearning.
Paper: Label Leakage and Protection in Two-party Split Learning, Oscar Li et al. (2022). Investigates gradient leakage and develops optimized noise-perturbation defenses in distributed, multi-party learning settings.
Paper: DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learning, Robert Hönig et al. (2022). Explores doubly-adaptive quantization in federated learning, addressing complementary communication efficiency bottlenecks in distributed private training.

Cover for Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams

Abstract

Motivated by recent applications requiring differential privacy over adaptive streams, we investigate optimal instantiations of the matrix mechanism [1] in this setting. We prove fundamental theoretical results on the applicability of matrix factorizations to adaptive streams, and provide a parameter-free fixed-point algorithm for computing optimal factorizations. We instantiate this framework with respect to concrete matrices which arise naturally in machine learning, and train user-level differentially private models with the resulting optimal mechanisms, yielding significant improvements in a notable problem in federated learning with user-level differential privacy.

Topics

data stream differential privacies

Keywords

differential privacy private SGD optimal private linear operators adaptive streams optimal matrix factorization Gaussian DP continual-release algorithms event-level privacy momentum SGD

1 Introduction and background
2 Privacy for adaptive streams
3 Computing optimal factorizations
4 The matrix mechanism for SGD
5 Experimental results
6 Conclusions
Acknowledgements
References
Checklist

Knowls

Knowl 1 — Adaptive Privacy of Gaussian Noise Matrix Mechanisms
theoretical result
Let $A \in \mathbb{R}^{n \times n}$ be a lower-triangular full-rank query matrix, and let $A = BC$ be any factorization where $B \in \mathbb{R}^{n \times m}$ and $C \in \mathbb{R}^{m \times n}$ . Suppose that for any two neighboring streams of input matrices $G, H \in \mathbb{R}^{n \times d}$ (differing by at most one row with $\ell_2$ difference bounded by $\zeta$ ), the Frobenius sensitivity satisfies $\|C(G - H)\|_F \le \kappa$ .

Let $Z \sim \mathcal{N}(0, \kappa^2 \sigma^2)^{m \times d}$ . If the nonadaptive continual-release mechanism $\mathcal{M}(G) = AG + BZ = B(CG + Z)$ satisfies $(\epsilon, \delta)$ -differential privacy (or $\rho$ -zero-concentrated DP, or $\mu$ -Gaussian DP) against nonadaptive input streams, then $\mathcal{M}$ satisfies the exact same differential privacy guarantee with identical parameters against an adaptive adversary that selects the rows of $G$ sequentially as arbitrary functions of all previous mechanism outputs $a_1, \dots, a_{i-1}$ .

This result relies on the rotational invariance of the spherical Gaussian distribution (and does not hold for arbitrary noise distributions).
Knowl 2 — Fixed-Point Formulation and Optimality Certificate for Matrix Mechanism Factorization
theoretical result
For a full-rank query matrix $A \in \mathbb{R}^{n \times n}$ , finding the optimal factorization $A = BC$ minimizing the expected squared reconstruction error under unit-sensitivity single-pass inputs reduces to the convex program:

$X^* = \arg\min_{X \succ 0, X_{i,i} \le 1, 1 \le i \le n} \text{tr}(A^* A X^{-1})$

where $X = C^* C$ , with optimal reconstruction matrix given by $B^* = A C^\dagger$ . The unique minimizer $X^*$ corresponds to the unique fixed point $v^* \in \mathbb{R}^n_+$ of the operator $\phi : \mathbb{R}^n_+ \to \mathbb{R}^n_+$ defined by:

$\phi(v) = \text{diagpart}\left( \sqrt{\text{diag}(v)^{1/2} A^* A \, \text{diag}(v)^{1/2}} \right)$

where $\text{diag}(v)$ embeds vector $v$ on the diagonal, and $\text{diagpart}(M)$ extracts the diagonal vector of matrix $M$ . Given $v$ , the matrix $X(v)$ is constructed as:

$X(v) = \text{diag}(v)^{-1/2} \left( \text{diag}(v)^{1/2} A^* A \, \text{diag}(v)^{1/2} \right)^{1/2} \text{diag}(v)^{-1/2}$

At the fixed point $v^*$ , $X^* = X(v^*)$ satisfies the relation $A^* A = X^* \text{diag}(v^*) X^*$ .

Furthermore, for any positive vector $v \in \mathbb{R}^n_+$ , the primal objective value is lower-bounded by:

$\text{tr}(A^* A X^{-1}) \ge \text{tr}\left( \text{diag}(v) (2 X(v) - I) \right)$

and this bound is tight at $v = v^*$ , providing an explicit, parameter-free optimality gap stopping criterion.
Knowl 3 — Differentially Private Matrix Factorization SGD
algorithm
Differentially Private Matrix Factorization SGD releases private iterates during streaming optimization by applying an optimal lower-triangular linear query factorization $M = BC$ .
Input: Factorization matrices $B, C \in \mathbb{R}^{n \times n}$ such that $M = BC$ , overall learning rate $\eta > 0$ , noise standard deviation $\sigma > 0$ , gradient clipping norm $\zeta > 0$ , training examples $\chi_1, \dots, \chi_n$ .
Output: Sequence of model parameter iterates $\theta_1, \dots, \theta_n \in \mathbb{R}^d$ .
$\theta_0 \leftarrow 0 \in \mathbb{R}^d$
Sample noise matrix $Z \in \mathbb{R}^{n \times d}$ with i.i.d. entries $Z_{i,j} \sim \mathcal{N}(0, \sigma^2)$
for $i = 1, \dots, n$ do
    Evaluate gradient $\hat{g} \leftarrow \nabla_\theta \ell(\theta_{i-1}; \chi_i)$ (if $\chi_i = \perp$ , set $\hat{g} \leftarrow 0$ )
    Clip gradient $G_{i,:} \leftarrow \hat{g} \cdot \min\left(1, \frac{\zeta}{\|\hat{g}\|_2}\right)$
    Update iterate $\theta_i \leftarrow -\eta \left( M_{i, 1:i} G_{1:i, :} + B_{i, 1:i} Z_{1:i, :} \right)$
end for
return $\theta_1, \dots, \theta_n$
Under the replace-with-zero DP model where each user's data affects a single round's gradient with clipped $\ell_2$ -norm $\le \zeta$ , releasing the sequence of iterates $\theta_1, \dots, \theta_n$ satisfies differential privacy equivalent to the Gaussian mechanism with noise variance $\sigma^2$ on records with $\ell_2$ -sensitivity at most $\zeta \gamma(C)$ , where $\gamma(C) = \max_{i \in [n]} \|C_{[:,i]}\|_2$ is the maximum column norm of $C$ .
Knowl 4 — Matrix Mechanism Formulation of Momentum SGD and Learning Rate Schedules
model/method
Polyak heavy-ball momentum SGD with per-iteration learning rates $\eta_1, \dots, \eta_n$ and momentum parameter $\beta \in [0, 1)$ updates momentum $m_i = \beta m_{i-1} + g_i$ and iterates $\theta_i = \theta_{i-1} - \eta_i m_i$ . This process can be expressed as a single linear operator $\theta = -MG$ on the matrix of gradients $G \in \mathbb{R}^{n \times d}$ , where $M = M^{(\eta)} M^{(\beta)} \in \mathbb{R}^{n \times n}$ is the product of two lower-triangular matrices:

$M^{(\eta)}_{i,j} = \begin{cases} \eta_j & \text{if } i \ge j \\ 0 & \text{otherwise} \end{cases} \qquad M^{(\beta)}_{i,j} = \begin{cases} \beta^{i-j} & \text{if } i \ge j \\ 0 & \text{otherwise} \end{cases}$

Rather than computing private prefix sums $S = B_S C_S$ and forming momentum iterates via post-processing as $\hat{B} = M S^{-1} B_S$ , the matrix mechanism framework computes the direct optimal factorization $M = B^*_M C^*_M$ . Directly optimizing the factorization of $M$ substantially reduces the total squared reconstruction error $\gamma^2(C) \|B\|_F^2$ compared to post-processed prefix sums and binary-tree estimators.
Knowl 5 — Lower-Triangular Factorization Equivalence via LQ Decomposition
theoretical result
For any lower-triangular full-rank matrix $A \in \mathbb{R}^{n \times n}$ and any arbitrary factorization $A = BC$ where $B \in \mathbb{R}^{n \times m}$ and $C \in \mathbb{R}^{m \times n}$ , there exists an alternative factorization $A = \hat{B}\hat{C}$ where both $\hat{B} \in \mathbb{R}^{n \times n}$ and $\hat{C} \in \mathbb{R}^{n \times n}$ are strictly lower-triangular, and which induces a distributionally identical matrix mechanism under spherical Gaussian noise.

This lower-triangular factorization $\hat{B}, \hat{C}$ can be explicitly constructed from $A = BC$ via an LQ decomposition of $C$ . When the diagonal entries of $\hat{C}$ are constrained to be strictly non-negative, this lower-triangular factorization is unique.
Knowl 6 — Local Contraction and Dimension-Independent Convergence of Fixed-Point Factorization Map
theoretical result
The fixed-point operator $\phi : \mathbb{R}^n_+ \to \mathbb{R}^n_+$ defined by:

$\phi(v) = \text{diagpart}\left( \sqrt{\text{diag}(v)^{1/2} A^* A \, \text{diag}(v)^{1/2}} \right)$

is a local contraction around its unique fixed point $v^*$ in a suitable metric. Consequently, the fixed-point iteration $v^{(k+1)} = \phi(v^{(k)})$ converges to $v^*$ from any initialization within a neighborhood of $v^*$ .

The contraction factor and the radius of the convergence neighborhood depend exclusively on the extremal eigenvalues $\lambda_{\min}(A^*A)$ and $\lambda_{\max}(A^*A)$ , and are completely independent of the matrix dimension $n$ (holding generally for bounded linear operators on Hilbert spaces with bounded inverses).
Knowl 7 — Regret Bound for Convex Differentially Private Matrix SGD
theoretical result
In the setting of Differentially Private Matrix Factorization SGD with prefix-sum matrix $M = S$ , constant learning rate $\eta > 0$ , noise standard deviation $\sigma > 0$ , and a sequence of convex loss functions $\ell(\cdot; \chi_t)$ each having $\ell_2$ -Lipschitz constant $L$ , the sequence of iterates $\theta_t = \theta_{[t,:]}$ satisfies the following expected regret bound for any comparator $\theta^* \in \mathbb{R}^d$ :

$\frac{1}{n} \sum_{t=1}^n \mathbb{E}\left[ \ell(\theta_t; \chi_t) - \ell(\theta^*; \chi_t) \right] \le \eta L^2 + \frac{\|\theta^*\|_2^2 - \|\theta_1\|_2^2}{2 \eta n} + \frac{L \sigma \eta}{\sqrt{n}} \|B\|_F$

where $B$ is the reconstruction matrix of the lower-triangular factorization $S = BC$ with normalized column sensitivity $\gamma(C) = 1$ .
Knowl 8 — Equivalence of Nonadaptive and Adaptive Continual Release under Pure Differential Privacy
theoretical result
Every mechanism $\mathcal{M}$ that is $(\epsilon, 0)$ -differentially private in the nonadaptive continual release model is also $(\epsilon, 0)$ -differentially private in the adaptive continual release model with the exact same privacy parameter $\epsilon$ .

In contrast, this equivalence does not hold in general for approximate $(\epsilon, \delta)$ -differential privacy with $\delta > 0$ , where certain additive-noise mechanisms can be nonadaptively $(\epsilon, \delta)$ -DP but fail to remain private under adaptive streams.
Knowl 9 — Banded Plus Low-Rank Structured Approximation of Reconstruction Matrices
model/method
For high-dimensional machine learning settings (e.g., model parameter dimension $d \ge 10^6$ and iterations $n \ge 2048$ ), generating correlated Gaussian noise via full matrix multiplication $B Z$ can be memory- and compute-intensive.

Because the optimal reconstruction matrix $B^*$ for prefix sums exhibits strong diagonal dominance, it can be approximated as $\hat{B} = B_{\text{band}} + B_{\text{low-rank}}$ , where:
1. $B_{\text{band}}$ is a lower-triangular banded matrix with band width $k \ll n$ preserving entries near the diagonal.
2. $B_{\text{low-rank}}$ captures the remaining lower-triangular entries via an alternating-least-squares (ALS) low-rank factorization.
This structured representation enables sampling and applying per-iteration noise additions in $\mathcal{O}(d)$ time per step, matching the per-step asymptotic computational cost of binary-tree noise mechanisms.
Knowl 10 — Empirical Performance on User-Level Differentially Private Language Modeling
empirical result
On the StackOverflow next-word prediction federated learning benchmark ( $d \approx 4 \times 10^6$ parameters, $n = 2048$ training rounds, single-pass user-level DP, evaluated at target privacy $\epsilon = 18.9, \delta = 10^{-6}$ ):
1. At constant learning rates with 100 clients/round, optimal matrix factorization of the prefix-sum matrix ( $M=S$ ) and momentum operator ( $M=B^*_M C^*_M$ ) yields significantly higher test accuracy than Honaker Online (DP-FTRL baseline) and Honaker Full tree mechanisms across privacy budgets $\epsilon \in [0.8, 18.7]$ .
2. Incorporating learning rate decay (reducing learning rate by $0.15\times$ for the last 512 rounds) or learning rate cooldown (linear drop from $1.0\times$ to $0.05\times$ over the last 512 rounds) directly into the matrix operator $M$ further boosts test accuracy.
3. Combining the optimal momentum matrix factorization with learning rate cooldown and maximum cohort size (167 clients/round for single pass) achieves test accuracy $\approx 0.245$ , closing over two-thirds ( $> 66\%$ ) of the accuracy gap between the previous state-of-the-art DP method (accuracy $\approx 0.223$ ) and non-private training (accuracy $\approx 0.252$ ).

Coverage note — None was omitted; all key theoretical proofs, fixed-point algorithms, operator formulations, regret bounds, computational approximations, and benchmark results were converted into self-contained knowls.

References

1.Chao Li, Gerome Miklau, Michael Hay, Andrew Mcgregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24:757–781, 2015.
2.Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-32732-5.
3.T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. on Information Systems Security, 14(3):26:1–26:24, November 2011.
4.Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC’10), pages 715–724, 2010.
5.Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Proc. of the 25th Annual Conf. on Learning Theory (COLT), volume 23, pages 24.1–24.34, June 2012.
6.Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In ICML, 2021.
7.Adam Smith and Abhradeep Thakurta. (nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems, pages 2733–2741, 2013.
8.Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. ArXiv CoRR, abs/2112.00828, 2021. URL https://arxiv.org/abs/2112.00828.
9.Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In International Conference on Machine Learning, pages 32–40. PMLR, 2017.
10.Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 11–20, 2014.
11.Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Answering range queries under local differential privacy. Proceedings of the VLDB Endowment, 12(10):1126–1138, 2019.
12.Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. CoRR, abs/2103.16787, 2021. URL https://arxiv.org/abs/2103.16787.
13.Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pages 58–77. IEEE, 2017.
14.Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https://proceedings.neurips.cc/paper/2013/file/c850371fda6892fbfd1c5a5b457e5777-Paper.pdf.
15.Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245–248. IEEE, 2013.
16.Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pages 464–473, 2014.
17.Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016. doi: 10.1145/2976749.2978318. URL http://dx.doi.org/10.1145/2976749.2978318.
18.Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. Stadium: A distributed metadata-private messaging system. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 423–440, 2017.
19.Úlfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song. That which we call private, 2019.
20.Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner. Local differential privacy for evolving data. Advances in Neural Information Processing Systems, 31, 2018.
21.Differential Privacy Team Apple. Learning with privacy at scale, 2017.
22.James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2015.
23.H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:1002.4908, 2010.
24.Brendan McMahan. Follow-the-regularized-leader and mirror descent: Equivalence theorems and l1 regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 525–533, 2011.
25.John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
26.Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, 2010.
27.Ganzhao Yuan, Yin Yang, Zhenjie Zhang, and Zhifeng Hao. Optimal linear aggregate query processing under approximate differential privacy. CoRR, abs/1602.04302, 2016. URL http://arxiv.org/abs/1602.04302.
28.Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. HDMM: optimizing error of high-dimensional statistical queries under differential privacy. CoRR, abs/2106.12118, 2021. URL https://arxiv.org/abs/2106.12118.
29.Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The Power of Factorization Mechanisms in Local and Central Differential Privacy, page 425–438. Association for Computing Machinery, New York, NY, USA, 2020. ISBN 9781450369794. URL https://doi.org/10.1145/3357713.3384297.
30.Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation, 2022. URL https://arxiv.org/abs/2202.11205.
31.Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. on Theory of Cryptography (TCC), pages 265–284, 2006. URL http://dx.doi.org/10.1007/11681878_14.
32.Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology—EUROCRYPT, pages 486–503, 2006.
33.Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635–658. Springer, 2016.
34.Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs/1603.01887, 2016.
35.Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263–275. IEEE, 2017.
36.Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. CoRR, abs/1905.02383, 2019. URL http://arxiv.org/abs/1905.02383.
37.Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference on Artificial Intelligence and Statistics, pages 3358–3366. PMLR, 2021.
38.S. L. Campbell and C. D. Meyer. Generalized inverses of linear transformations / S. L. Campbell, C. D. Meyer. Pitman London ; San Francisco, 1979. ISBN 0273084224.
39.Richard Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics, 41(12):2315–2323, 1994. doi: 10.1080/09500349414552171. URL https://doi.org/10.1080/09500349414552171.
40.Yeong-Cherng Liang, Yu-Hao Yeh, Paulo E M F Mendonça, Run Yan Teh, Margaret D Reid, and Peter D Drummond. Quantum fidelity measures for mixed states. Reports on Progress in Physics, 82(7):076001, jun 2019. doi: 10.1088/1361-6633/ab1ca4. URL https://doi.org/10.1088/1361-6633/ab1ca4.
41.Jimmie D. Lawson and Yongdo Lim. The geometric mean, matrices, metrics, and more. The American Mathematical Monthly, 108(9):797–812, 2001. doi: 10.1080/00029890.2001.11919815. URL https://doi.org/10.1080/00029890.2001.11919815.
42.Ando Tsuyoshi Kubo, Fumio. Means of positive linear operators. Mathematische Annalen, 246:205–224, 1979. URL http://eudml.org/doc/163339.
43.B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964. ISSN 0041-5553.
44.Andrew Hard, Kanishka Rao, Rajiv Mathews, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. CoRR, abs/1811.03604, 2018. URL http://arxiv.org/abs/1811.03604.
45.Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H. Brendan McMahan, and Françoise Beaufays. Training production language models without memorizing user data, 2020.
46.Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In Proceedings of the 28th USENIX Conference on Security Symposium, SEC’19, page 267–284, USA, 2019. USENIX Association. ISBN 9781939133069.
47.Congzheng Song and Vitaly Shmatikov. Auditing data provenance in text-generation models. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 196–206, 2019.
48.Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Úlfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633–2650. USENIX Association, August 2021. ISBN 978-1-939133-24-3. URL https://www.usenix.org/conference/usenixsecurity21/presentation/carlini-extracting.
49.H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06963, 2017.
50.H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, pages 1273–1282, 2017. URL http://proceedings.mlr.press/v54/mcmahan17a.html.
51.Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization. ˇ CoRR, abs/2003.00295, 2020. URL https://arxiv.org/abs/2003.00295.
52.Alex Ingerman and Krzysztof Ostrowski. Introducing tensorflow federated, Mar 2019. URL https://blog.tensorflow.org/2019/03/introducing-tensorflow-federated.html.
53.Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large-cohort training for federated learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https://openreview.net/forum?id=Kb26p7chwhf.
54.Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konecný, Andrew Hard, and Tom Goldstein. ˇ Diurnal or nocturnal? federated learning of multi-branch networks from periodically shifting distributions. In International Conference on Learning Representations, 2022.
55.Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, Keith Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. CoRR, abs/2102.03448, 2021. URL https://arxiv.org/abs/2102.03448.
56.Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347–450. Springer, 2017.
57.Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1990. ISBN 0521386322. URL http://www.amazon.com/Matrix-Analysis-Roger-Horn/dp/0521386322%3FSubscriptionId%3D192BW6DQ43CK9FN0ZGG2%26tag%3Dws%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D0521386322.
58.Thomas Steinke. Composition of differential privacy &; privacy amplification by subsampling, 2022. URL https://arxiv.org/abs/2210.00597.
59.Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.
60.Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. ISBN 0521833787. URL http://www.amazon.com/exec/obidos/redirect?tag=citeulike-20&path=ASIN/0521833787.
61.D.P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.
62.Jorma Merikoski and Ravinder Kumar. Inequalities for spreads of matrix sums and products. Applied Mathematics E-Notes [electronic only], 4, 01 2004.
63.Nathan Srebro, Jason Rennie, and Tommi Jaakkola. Maximum-margin matrix factorization. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2005. URL https://proceedings.neurips.cc/paper/2004/file/e0688d13958a19e087e123148555e4b4-Paper.pdf.
64.Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8), 2009. ISSN 0018-9162. doi: 10.1109/MC.2009.263. URL https://doi.org/10.1109/MC.2009.263.
65.Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, 2013. ISBN 9781450320290.
66.Google. Tensorflow-privacy. https://github.com/tensorflow/privacy, year=2019.
67.Om Thakkar, Galen Andrew, and H Brendan McMahan. Differentially private learning with adaptive clipping. arXiv preprint arXiv:1905.03871, 2019.

Citation

MLA

Denisov, S., et al. “Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 5910–24, https://proceedings.neurips.cc/paper_files/paper/2022/file/271ec4d1a9ff5e6b81a6e21d38b1ba96-Paper-Conference.pdf.

APA

Denisov, S., McMahan, H. B., Rush, J., Smith, A., & Guha Thakurta, A. (2022). Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams. Advances in Neural Information Processing Systems, 35, 5910–5924. https://proceedings.neurips.cc/paper_files/paper/2022/file/271ec4d1a9ff5e6b81a6e21d38b1ba96-Paper-Conference.pdf

Chicago

Denisov, S., H. B. McMahan, J. Rush, A. Smith, and A. Guha Thakurta. 2022. “Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams”. Advances in Neural Information Processing Systems 35: 5910–24. https://proceedings.neurips.cc/paper_files/paper/2022/file/271ec4d1a9ff5e6b81a6e21d38b1ba96-Paper-Conference.pdf.

Harvard

Denisov, S. et al. (2022) “Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 5910–5924. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/271ec4d1a9ff5e6b81a6e21d38b1ba96-Paper-Conference.pdf.

Vancouver

1. Denisov S, McMahan HB, Rush J, Smith A, Guha Thakurta A (2022) Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 5910–5924

BibTeX

@inproceedings{denisov2022improved,
  title = {Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams},
  author = {Denisov, Sergey and McMahan, H. Brendan and Rush, John and Smith, Adam and Guha Thakurta, Abhradeep},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {5910-5924},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/271ec4d1a9ff5e6b81a6e21d38b1ba96-Paper-Conference.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Adaptive Privacy of Gaussian Noise Matrix Mechanisms

Knowl 2 — Fixed-Point Formulation and Optimality Certificate for Matrix Mechanism Factorization

Knowl 3 — Differentially Private Matrix Factorization SGD

Knowl 4 — Matrix Mechanism Formulation of Momentum SGD and Learning Rate Schedules

Knowl 5 — Lower-Triangular Factorization Equivalence via LQ Decomposition

Knowl 6 — Local Contraction and Dimension-Independent Convergence of Fixed-Point Factorization Map

Knowl 7 — Regret Bound for Convex Differentially Private Matrix SGD

Knowl 8 — Equivalence of Nonadaptive and Adaptive Continual Release under Pure Differential Privacy

Knowl 9 — Banded Plus Low-Rank Structured Approximation of Reconstruction Matrices

Knowl 10 — Empirical Performance on User-Level Differentially Private Language Modeling

References

Citation

BibTeX

Access the Paper