# Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy

arXiv: https://arxiv.org/abs/2302.01463 · HTML: https://mlsanity.com/paper/2302.01463/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 55 references that are in the map.
- First posted on arXiv 2 Feb 2023.

## Builds on (most cited first, 30 of 35)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Differentially Private Learning with Adaptive Clipping](https://mlsanity.com/paper/1905.03871/) (2019)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling](https://mlsanity.com/paper/2012.12803/) (2020)
- [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams](https://mlsanity.com/paper/2202.08312/) (2022)
- [Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning](https://mlsanity.com/paper/2211.06530/) (2022)
- [Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT](https://mlsanity.com/paper/2006.07134/) (2020)
- [Anticorrelated Noise Injection for Improved Generalization](https://mlsanity.com/paper/2202.02831/) (2022)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Explicit Regularization in Overparametrized Models via Noise Injection](https://mlsanity.com/paper/2206.04613/) (2022)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)

## Built on by (most cited first, 18 of 18)

- [Banded Square Root Matrix Factorization for Differentially Private Model Training](https://mlsanity.com/paper/2405.13763/) (2024)
- [DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reduction](https://mlsanity.com/paper/2410.03883/) (2024)
- [Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD](https://mlsanity.com/paper/2505.12128/) (2025)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)
- [DP-λCGD: Efficient Noise Correlation for Differentially Private Model Training](https://mlsanity.com/paper/2601.22334/) (2026)
- [Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization](https://mlsanity.com/paper/2510.17480/) (2025)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Data value estimation on private gradients](https://mlsanity.com/paper/2412.17008/) (2024)
- [Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation](https://mlsanity.com/paper/2506.02563/) (2025)
- [Correlating Cross-Iteration Noise for DP-SGD using Model Curvature](https://mlsanity.com/paper/2510.05416/) (2025)
- [Cocoon: A System Architecture for Differentially Private Training with Correlated Noises](https://mlsanity.com/paper/2510.07304/) (2025)
- [Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis](https://mlsanity.com/paper/2603.19648/) (2026)
- [FIBER: A Differentially Private Optimizer with Filter-Aware Innovation Bias Correction](https://mlsanity.com/paper/2605.03425/) (2026)
- [Differentially Private Online Federated Learning with Correlated Noise](https://mlsanity.com/paper/2403.16542/) (2024)
- [Balancing Utility and Privacy: Dynamically Private SGD with Random Projection](https://mlsanity.com/paper/2509.09485/) (2025)
- [Robustifying Asynchronous SGD via Soft Throttling](https://mlsanity.com/paper/2609.39357/) (2026)

## Abstract (arXiv)

We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically.