mlsanityData to 14 Oct 2026

Noise is All You Need: Private Second-Order Convergence of Noisy SGD

arXiv 2410.06878 ↗First posted 9 Oct 2024cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

Private optimization is a topic of major interest in machine learning, with differentially private stochastic gradient descent (DP-SGD) playing a key role in both theory and practice. Furthermore, DP-SGD is known to be a powerful tool in contexts beyond privacy, including robustness, machine unlearning, etc. Existing analyses of DP-SGD either make relatively strong assumptions (e.g., Lipschitz continuity of the loss function, or even convexity) or prove only first-order convergence (and thus might end at a saddle point in the non-convex setting). At the same time, there has been progress in proving second-order convergence of the non-private version of ``noisy SGD'', as well as progress in designing algorithms that are more complex than DP-SGD and do guarantee second-order convergence. We revisit DP-SGD and show that ``noise is all you need'': the noise necessary for privacy already implies second-order convergence under the standard smoothness assumptions, even for non-Lipschitz loss functions. Hence, we get second-order convergence essentially for free: DP-SGD, the workhorse of modern private optimization, under minimal assumptions can be used to find a second-order stationary point.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 52 of its 78 references that are in the map. First posted on arXiv 9 Oct 2024.

Builds on

52 of 78 references.

References · 52

  1. 2019Advances and Open Problems in Federated Learningcited by 3,046
  2. 2016Deep Learning with Differential Privacycited by 2,728
  3. 2018Neural Network Acceptability Judgmentscited by 958
  4. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 864
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  6. 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 468
  7. 2021Remember What You Want to Forget: Algorithms for Machine Unlearningcited by 371
  8. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  10. 2017How to Escape Saddle Points Efficientlycited by 285
  11. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  12. 2016Deep Learning without Poor Local Minimacited by 234
38 more
  1. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  2. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 158
  3. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  4. 2020Understanding Gradient Clipping in Private SGD: A Geometric Perspectivecited by 142
  5. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  6. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  7. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  8. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  9. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  10. 2022Automatic Clipping: Differentially Private Deep Learning Made Easier and Strongercited by 88
  11. 2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
  12. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  13. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  14. 2018Escaping Saddles with Stochastic Gradientscited by 66
  15. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  16. 2020Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorizationcited by 58
  17. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  18. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  19. 2015Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picturecited by 49
  20. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  21. 2023FFCV: Accelerating Training by Removing Data Bottleneckscited by 49
  22. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  23. 2015Efficient Per-Example Gradient Computationscited by 42
  24. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  25. 2019A New Analysis of Differential Privacy's Generalization Guaranteescited by 36
  26. 2022Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimizationcited by 36
  27. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  28. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  29. 2021Fast and Memory Efficient Differentially Private-SGD via JL Projectionscited by 29
  30. 2016Efficient approaches for escaping higher order saddle points in non-convex optimizationcited by 23
  31. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  32. 2018Differential Privacy Techniques for Cyber Physical Systems: A Surveycited by 21
  33. 2019Efficient Per-Example Gradient Computations in Convolutional Neural Networkscited by 17
  34. 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12
  35. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  36. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  37. 2020First-Order Methods for Nonconvex Quadratic Minimizationcited by 10
  38. 2021Differential Privacy for Industrial Internet of Things: Opportunities, Applications and Challengescited by 10

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3

Similar, not cited

Close in wording, no citation either way

  1. 2025An Improved Privacy and Utility Analysis of Differentially Private SGD with Bounded Domain and Smooth Losses
  2. 2025Can SGD Handle Heavy-Tailed Noise?
  3. 2024Too Good to be True? Turn Any Model Differentially Private With DP-Weights
  4. 2022Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise
  5. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees
  6. 2026Closed-Form Noise Calibration Against Membership Inference for Random-Allocation DP-SGD
  7. 2024RQP-SGD: Differential Private Machine Learning through Noisy SGD and Randomized Quantization
  8. 2025On the Gradient Complexity of Private Optimization with Private Oracles