mlsanityData to 14 Oct 2026

Faster Rates of Convergence to Stationary Points in Differentially Private Optimization

arXiv 2206.00846 ↗First posted 2 Jun 2022cs.LG cs.CR math.OCcited by 32

Not on the map. Why?

Abstract (arXiv)

We study the problem of approximating stationary points of Lipschitz and smooth functions under (varepsilon,δ)-differential privacy (DP) in both the finite-sum and stochastic settings. A point widehatw is called an α-stationary point of a function F:ℝdrightarrowℝ if |nabla F(widehatw)|≤ α. We provide a new efficient algorithm that finds an tildeObig(big[frac√dnvarepsilonbig]2/3big)-stationary point in the finite-sum setting, where n is the number of samples. This improves on the previous best rate of tildeObig(big[frac√dnvarepsilonbig]1/2big). We also give a new construction that improves over the existing rates in the stochastic optimization setting, where the goal is to find approximate stationary points of the population risk. Our construction finds a tildeObig(frac1n1/3 + big[frac√dnvarepsilonbig]1/2big)-stationary point of the population risk in time linear in n. Furthermore, under the additional assumption of convexity, we completely characterize the sample complexity of finding stationary points of the population risk (up to polylog factors) and show that the optimal rate on population stationarity is tilde Thetabig(frac1√n+frac√dnvarepsilonbig). Finally, we show that our methods can be used to provide dimension-independent rates of Obig(frac1√n+minbig(big[frac√ranknvarepsilonbig]2/3,frac1(nvarepsilon)2/5big)big) on population stationarity for Generalized Linear Models (GLM), where rank is the rank of the design matrix, which improves upon the previous best known rate.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). Builds on 26 of its 53 references that are in the map. First posted on arXiv 2 Jun 2022.

Builds on

26 of 53 references.

References · 26

  1. 2016Deep Learning with Differential Privacycited by 2,728
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  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. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  8. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 128
  9. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  10. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  11. 2016A Geometric Analysis of Phase Retrievalcited by 92
  12. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
14 more
  1. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
  2. 2017Efficient Private ERM for Smooth Objectivescited by 61
  3. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  4. 2015Between Pure and Approximate Differential Privacycited by 56
  5. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  6. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  7. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  8. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  9. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
  10. 2020A Primer on Private Statisticscited by 30
  11. 2020Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Boundscited by 26
  12. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  13. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  14. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 10; 2024: 10; 2025: 7; 2026: 3.

32 papers.

Sort:

  1. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 153
  2. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  3. 2023On the Privacy-Robustness-Utility Trilemma in Distributed Learningcited by 24
  4. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  5. 2024The Privacy Power of Correlated Noise in Decentralized Learningcited by 18
  6. 2022Stochastic Differentially Private and Fair Learningcited by 16
  7. 2024Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuningcited by 14
  8. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  9. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 12
  10. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  11. 2023Differentially Private Non-convex Learning for Multi-layer Neural Networkscited by 10
  12. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
20 more
  1. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  2. 2023Private Federated Learning with Autotuned Compressioncited by 5
  3. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  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 Optimization with Sparse Gradientscited by 2
  9. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  10. 2024Differentially Private Bilevel Optimizationcited by 2
  11. 2024Adaptive Batch Size for Privately Finding Second-Order Stationary Pointscited by 2
  12. 2025Private Evolution Convergescited by 2
  13. 2025Memory-Efficient Differentially Private Training with Gradient Random Projectioncited by 2
  14. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  15. 2023Simulation-based Bayesian Inference from Privacy Protected Datacited by 1
  16. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGDcited by 1
  17. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  18. 2026Efficient DP-SGD for LLMs with Randomized Clippingcited by 1
  19. 2025On the Inherent Privacy of Zeroth Order Projected Gradient Descentcited by 0
  20. 2026Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimizationcited by 0