mlsanityData to 7 Oct 2026

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

arXiv 2302.01463 ↗First posted 2 Feb 2023cs.LGcited by 18

Not on the map. Why?

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.

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

Builds on

35 of 55 references.

References · 35

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2016Deep Learning with Differential Privacycited by 2,682
  4. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  5. 2018Sparsified SGD with Memorycited by 373
  6. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  7. 2018Subsampled R'enyi Differential Privacy and Analytical Moments Accountantcited by 234
  8. 2019Differentially Private Learning with Adaptive Clippingcited by 218
  9. 2021Federated Learning with Buffered Asynchronous Aggregationcited by 188
  10. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  11. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  12. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
23 more
  1. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  2. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  3. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  4. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  5. 2020Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shufflingcited by 96
  6. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  7. 2018Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGDcited by 68
  8. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  9. 2020Linearly Converging Error Compensated SGDcited by 61
  10. 2022Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streamscited by 59
  11. 2022Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learningcited by 48
  12. 2020Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFTcited by 43
  13. 2022Anticorrelated Noise Injection for Improved Generalizationcited by 41
  14. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  15. 2019The Power of Factorization Mechanisms in Local and Central Differential Privacycited by 30
  16. 2018Optimizing error of high-dimensional statistical queries under differential privacycited by 29
  17. 2022Explicit Regularization in Overparametrized Models via Noise Injectioncited by 25
  18. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  19. 2021HDMM: Optimizing error of high-dimensional statistical queries under differential privacycited by 11
  20. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  21. 2016Convex Optimization for Linear Query Processing under Approximate Differential Privacycited by 5
  22. 2022On the Theoretical Properties of Noise Correlation in Stochastic Optimizationcited by 5
  23. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 7; 2026: 4.

18 papers.

Sort:

  1. 2024Banded Square Root Matrix Factorization for Differentially Private Model Trainingcited by 12
  2. 2024DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reductioncited by 10
  3. 2025Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGDcited by 7
  4. 2024Locally Differentially Private Online Federated Learning With Correlated Noisecited by 6
  5. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  6. 2024The poison of dimensionalitycited by 3
  7. 2025Unified Privacy Guarantees for Decentralized Learning via Matrix Factorizationcited by 2
  8. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  9. 2024Data value estimation on private gradientscited by 1
  10. 2025Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellationcited by 1
  11. 2025Correlating Cross-Iteration Noise for DP-SGD using Model Curvaturecited by 1
  12. 2025Cocoon: A System Architecture for Differentially Private Training with Correlated Noisescited by 1
6 more
  1. 2026DP-λCGD: Efficient Noise Correlation for Differentially Private Model Trainingcited by 1
  2. 2026Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysiscited by 1
  3. 2026FIBER: A Differentially Private Optimizer with Filter-Aware Innovation Bias Correctioncited by 1
  4. 2024Differentially Private Online Federated Learning with Correlated Noisecited by 0
  5. 2025Balancing Utility and Privacy: Dynamically Private SGD with Random Projectioncited by 0
  6. 2026Robustifying Asynchronous SGD via Soft Throttlingcited by 0