# Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks arXiv: https://arxiv.org/abs/2302.09699 · HTML: https://mlsanity.com/paper/2302.09699/ ## Key facts - Cited by 12 papers in the map (data through 14 Oct 2026). - Builds on 32 of its 58 references that are in the map. - First posted on arXiv 20 Feb 2023. ## Builds on (most cited first, 30 of 32) - [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015) - [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016) - [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019) - [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013) - [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018) - [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017) - [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015) - [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019) - [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020) - [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020) - [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018) - [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019) - [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020) - [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021) - [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021) - [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022) - [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022) - [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021) - [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021) - [Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2206.13033/) (2022) - [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022) - [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017) - [Efficient Privacy-Preserving Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1910.13659/) (2019) - [Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds](https://mlsanity.com/paper/2006.13501/) (2020) - [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021) - [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021) - [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023) - [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022) - [Momentum Aggregation for Private Non-convex ERM](https://mlsanity.com/paper/2210.06328/) (2022) - [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022) ## Built on by (most cited first, 12 of 12) - [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023) - [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023) - [How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization](https://mlsanity.com/paper/2402.11173/) (2024) - [Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates](https://mlsanity.com/paper/2311.13447/) (2023) - [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024) - [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025) - [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025) - [Differentially Private Bilevel Optimization](https://mlsanity.com/paper/2409.19800/) (2024) - [Adaptive Batch Size for Privately Finding Second-Order Stationary Points](https://mlsanity.com/paper/2410.07502/) (2024) - [Optimal Rates for O(1)-Smooth DP-SCO with a Single Epoch and Large Batches](https://mlsanity.com/paper/2406.02716/) (2024) - [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024) - [Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimization](https://mlsanity.com/paper/2602.01339/) (2026) ## 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.