mlsanityData to 7 Oct 2026

Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings

arXiv 2107.05585 ↗First posted 12 Jul 2021cs.LG math.OC stat.MLcited by 45

Not on the map. Why?

Abstract (arXiv)

We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the ℓ2 setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. Our algorithm for the ℓ1 setting has nearly-optimal excess population risk tildeObig(√fraclogdnvarepsilonbig), and circumvents the dimension dependent lower bound of citeAsi:2021 for general non-smooth convex losses. In the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. For the ℓ1-case with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, tilde Obig(fraclog2/3d(nvarepsilon)1/3big) in linear time. For the constrained ℓ2-case with smooth losses, we obtain a linear-time algorithm with rate tilde Obig(frac1n1/3+fracd1/5(nvarepsilon)2/5big). Finally, for the ℓ2-case we provide the first method for em non-smooth weakly convex stochastic optimization with rate tilde Obig(frac1n1/4+fracd1/6(nvarepsilon)1/3big) which matches the best existing non-private algorithm when d= O(√n). We also extend all our results above for the non-convex ℓ2 setting to the ℓp setting, where 1 < p ≤ 2, with only polylogarithmic (in the dimension) overhead in the rates.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). Builds on 17 of its 42 references that are in the map. First posted on arXiv 12 Jul 2021.

Builds on

17 of 42 references.

References · 17

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  5. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  6. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  8. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  9. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  10. 2017Efficient Private ERM for Smooth Objectivescited by 61
  11. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  12. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
5 more
  1. 2019One Sample Stochastic Frank-Wolfecited by 32
  2. 2017Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problemscited by 30
  3. 2020Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Boundscited by 26
  4. 2014Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometrycited by 24
  5. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 16; 2023: 8; 2024: 8; 2025: 8; 2026: 4.

45 papers.

Sort:

  1. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  2. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  3. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  4. 2022Differentially Private Learning with Per-Sample Adaptive Clippingcited by 21
  5. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  6. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  7. 2024Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuningcited by 14
  8. 2022Private Convex Optimization in General Normscited by 13
  9. 2023Tangent Transformers for Composition, Privacy and Removalcited by 13
  10. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  11. 2022Differentially private Riemannian optimizationcited by 12
  12. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
33 more
  1. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  2. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  3. 2023Differentially Private Non-convex Learning for Multi-layer Neural Networkscited by 10
  4. 2024How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimizationcited by 10
  5. 2023Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networkscited by 9
  6. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  7. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  8. 2022Differentially Private Learning with Margin Guaranteescited by 7
  9. 2024Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problemscited by 7
  10. 2024Public-data Assisted Private Stochastic Optimization: Power and Limitationscited by 5
  11. 2023Differentially Private Non-Convex Optimization under the KL Condition with Optimal Ratescited by 4
  12. 2025Towards Understanding Generalization in DP-GD: A Case Study in Training Two-Layer CNNscited by 4
  13. 2022Private Domain Adaptation from a Public Sourcecited by 3
  14. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  15. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  16. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  17. 2023The importance of feature preprocessing for differentially private linear optimizationcited by 2
  18. 2024Convex Approximation of Two-Layer ReLU Networks for Hidden State Differential Privacycited by 2
  19. 2025Private Evolution Convergescited by 2
  20. 2025Understanding Private Learning From Feature Perspectivecited by 2
  21. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  22. 2022Differentially Private Stochastic Gradient Descent with Low-Noisecited by 1
  23. 2022Truthful Generalized Linear Modelscited by 1
  24. 2023Simulation-based Bayesian Inference from Privacy Protected Datacited by 1
  25. 2024Enhancing DP-SGD through Non-monotonous Adaptive Scaling Gradient Weightcited by 1
  26. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  27. 2025PrAda-GAN: A Private Adaptive Generative Adversarial Network with Bayes Network Structurecited by 1
  28. 2026Optimization, Generalization and Differential Privacy Bounds for Gradient Descent on Kolmogorov-Arnold Networkscited by 1
  29. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  30. 2023Learning across Data Owners with Joint Differential Privacycited by 0
  31. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 0
  32. 2026Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Datacited by 0
  33. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0