mlsanityData to 7 Oct 2026

Private Stochastic Convex Optimization with Optimal Rates

arXiv 1908.09970 ↗First posted 27 Aug 2019cs.LG cs.CR cs.DScited by 183

Not on the map. Why?

Abstract (arXiv)

We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d. samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss. However a significant gap exists in the known bounds for the population loss. We show that, up to logarithmic factors, the optimal excess population loss for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of 1/√n as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of 1/n1/4. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization.

Key facts. Cited by 183 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Aug 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 32; 2022: 46; 2023: 35; 2024: 31; 2025: 25; 2026: 14.

183 papers.

Sort:

By area:

  1. 2021Remember What You Want to Forget: Algorithms for Machine Unlearningcited by 360
  2. 2021A Field Guide to Federated Optimizationcited by 312
  3. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
  4. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  5. 2021Machine Unlearning via Algorithmic Stabilitycited by 128
  6. 2021Deep Learning with Label Differential Privacycited by 113
  7. 2022Toward Training at ImageNet Scale with Differential Privacycited by 87
  8. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  9. 2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
  10. 2021Federated Reconstruction: Partially Local Federated Learningcited by 78
  11. 2021Learning with User-Level Privacycited by 72
  12. 2022Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Losscited by 60
38 more
  1. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  2. 2021Public Data-Assisted Mirror Descent for Private Model Trainingcited by 49
  3. 2023(Amplified) Banded Matrix Factorization: A unified approach to private trainingcited by 49
  4. 2022When Does Differentially Private Learning Not Suffer in High Dimensions?cited by 48
  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. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  8. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  9. 2022Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)cited by 45
  10. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  11. 2022Algorithms that Approximate Data Removal: New Results and Limitationscited by 39
  12. 2021Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Taskscited by 36
  13. 2023Why Is Public Pretraining Necessary for Private Model Training?cited by 36
  14. 2022Faster Rates of Convergence to Stationary Points in Differentially Private Optimizationcited by 32
  15. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  16. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  17. 2021Differentially private inference via noisy optimizationcited by 27
  18. 2022Reconstructing Training Data from Model Gradient, Provablycited by 27
  19. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  20. 2023DPZero: Private Fine-Tuning of Language Models without Backpropagationcited by 26
  21. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  22. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  23. 2022Differentially Private SGDA for Minimax Problemscited by 23
  24. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  25. 2022Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax Optimizationcited by 22
  26. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21
  27. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  28. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 19
  29. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  30. 2022Easy Differentially Private Linear Regressioncited by 19
  31. 2023Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacycited by 18
  32. 2023Tight Bounds for Machine Unlearning via Differential Privacycited by 18
  33. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  34. 2021Shuffle Private Stochastic Convex Optimizationcited by 17
  35. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  36. 2022Private Online Prediction from Experts: Separations and Faster Ratescited by 17
  37. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  38. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16

50 most cited of 183 All 183 (JSON)