mlsanityData to 14 Oct 2026

Second-Order Convergence in Private Stochastic Non-Convex Optimization

arXiv 2505.15647 ↗First posted 21 May 2025cs.LG cs.AIcited by 3

Not on the map. Why?

Abstract (arXiv)

We investigate the problem of finding second-order stationary points (SOSP) in differentially private (DP) stochastic non-convex optimization. Existing methods suffer from two key limitations: (i) inaccurate convergence error rate due to overlooking gradient variance in the saddle point escape analysis, and (ii) dependence on auxiliary private model selection procedures for identifying DP-SOSP, which can significantly impair utility, particularly in distributed settings. To address these issues, we propose a generic perturbed stochastic gradient descent (PSGD) framework built upon Gaussian noise injection and general gradient oracles. A core innovation of our framework is using model drift distance to determine whether PSGD escapes saddle points, ensuring convergence to approximate local minima without relying on second-order information or additional DP-SOSP identification. By leveraging the adaptive DP-SPIDER estimator as a specific gradient oracle, we develop a new DP algorithm that rectifies the convergence error rates reported in prior work. We further extend this algorithm to distributed learning with heterogeneous data, providing the first formal guarantees for finding DP-SOSP in such settings. Our analysis also highlights the detrimental impacts of private selection procedures in distributed learning under high-dimensional models, underscoring the practical benefits of our design. Numerical experiments on real-world datasets validate the efficacy of our approach.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 39 of its 57 references that are in the map. First posted on arXiv 21 May 2025.

Builds on

39 of 57 references.

References · 39

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  3. 2016Deep Learning with Differential Privacycited by 2,728
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  6. 2017How to Escape Saddle Points Efficientlycited by 285
  7. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  9. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  10. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  11. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  12. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
27 more
  1. 2016A Geometric Analysis of Phase Retrievalcited by 92
  2. 2018Escaping Saddles with Stochastic Gradientscited by 66
  3. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  4. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  5. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  6. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  7. 2018Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learningcited by 32
  8. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  9. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  10. 2020FLAME: Differentially Private Federated Learning in the Shuffle Modelcited by 27
  11. 2020Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Boundscited by 26
  12. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  13. 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
  14. 2018Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Casecited by 19
  15. 2023Practical Differentially Private and Byzantine-resilient Federated Learningcited by 18
  16. 2020Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacycited by 16
  17. 2019Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimizationcited by 15
  18. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  19. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  20. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  21. 2023DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learningcited by 10
  22. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  23. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  24. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  25. 2023Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compressioncited by 4
  26. 2022Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learningcited by 2
  27. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGDcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  2. 2025Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validationcited by 0
  3. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0