mlsanityData to 7 Oct 2026

Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks

arXiv 2302.09699 ↗First posted 20 Feb 2023cs.LG cs.CR math.OCcited by 12

Not on the map. Why?

Abstract (arXiv)

We consider the problem of minimizing a non-convex objective while preserving the privacy of the examples in the training data. Building upon the previous variance-reduced algorithm SpiderBoost, we introduce a new framework that utilizes two different kinds of gradient oracles. The first kind of oracles can estimate the gradient of one point, and the second kind of oracles, less precise and more cost-effective, can estimate the gradient difference between two points. SpiderBoost uses the first kind periodically, once every few steps, while our framework proposes using the first oracle whenever the total drift has become large and relies on the second oracle otherwise. This new framework ensures the gradient estimations remain accurate all the time, resulting in improved rates for finding second-order stationary points. Moreover, we address a more challenging task of finding the global minima of a non-convex objective using the exponential mechanism. Our findings indicate that the regularized exponential mechanism can closely match previous empirical and population risk bounds, without requiring smoothness assumptions for algorithms with polynomial running time. Furthermore, by disregarding running time considerations, we show that the exponential mechanism can achieve a good population risk bound and provide a nearly matching lower bound.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 32 of its 58 references that are in the map. First posted on arXiv 20 Feb 2023.

Builds on

32 of 58 references.

References · 32

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  3. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  4. 2013The Composition Theorem for Differential Privacycited by 290
  5. 2017How to Escape Saddle Points Efficientlycited by 284
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  8. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  9. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  10. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  11. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  12. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
20 more
  1. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  2. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  3. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  4. 2021Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descentcited by 71
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  7. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  8. 2022Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimizationcited by 35
  9. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  10. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  11. 2019Efficient Privacy-Preserving Stochastic Nonconvex Optimizationcited by 27
  12. 2020Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Boundscited by 26
  13. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 23
  14. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 19
  15. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  16. 2022Private Convex Optimization in General Normscited by 13
  17. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  18. 2022Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracycited by 10
  19. 2017The Price of Selection in Differential Privacycited by 7
  20. 2023Differentially Private Optimization for Smooth Nonconvex ERMcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 2; 2026: 1.

12 papers.

  1. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  2. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  3. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  4. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  5. 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
  6. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  7. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  8. 2024Differentially Private Bilevel Optimizationcited by 2
  9. 2024Adaptive Batch Size for Privately Finding Second-Order Stationary Pointscited by 2
  10. 2024Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batchescited by 1
  11. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGDcited by 1
  12. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0