mlsanityData to 7 Oct 2026

Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data

arXiv 2106.01336 ↗First posted 2 Jun 2021cs.LG cs.CR cs.DScited by 47

Not on the map. Why?

Abstract (arXiv)

We study stochastic convex optimization with heavy-tailed data under the constraint of differential privacy (DP). Most prior work on this problem is restricted to the case where the loss function is Lipschitz. Instead, as introduced by Wang, Xiao, Devadas, and Xu citeWangXDX20, we study general convex loss functions with the assumption that the distribution of gradients has bounded k-th moments. We provide improved upper bounds on the excess population risk under concentrated DP for convex and strongly convex loss functions. Along the way, we derive new algorithms for private mean estimation of heavy-tailed distributions, under both pure and concentrated DP. Finally, we prove nearly-matching lower bounds for private stochastic convex optimization with strongly convex losses and mean estimation, showing new separations between pure and concentrated DP.

Key facts. Cited by 47 papers in the map (data through 7 Oct 2026). Builds on 24 of its 50 references that are in the map. First posted on arXiv 2 Jun 2021.

Builds on

24 of 50 references.

References · 24

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  4. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  5. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 157
  6. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  7. 2016Concentrated Differential Privacycited by 139
  8. 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
  9. 2014Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Boundscited by 104
  10. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  11. 2018Privately Learning High-Dimensional Distributionscited by 103
  12. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
12 more
  1. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  2. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  3. 2019Private Hypothesis Selectioncited by 60
  4. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  5. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  6. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  7. 2019Generalized Resilience and Robust Statisticscited by 37
  8. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  9. 2019Efficient Privacy-Preserving Stochastic Nonconvex Optimizationcited by 27
  10. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21
  11. 2021Wide Network Learning with Differential Privacycited by 17
  12. 2018Robust descent using smoothed multiplicative noisecited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 11; 2023: 18; 2024: 6; 2025: 6; 2026: 1.

47 papers.

Sort:

  1. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  2. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  3. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  4. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  5. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  6. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  7. 2023Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distancecited by 14
  8. 2023Differentially Private SGD Without Clipping Bias: An Error-Feedback Approachcited by 13
  9. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  10. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  11. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  12. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
35 more
  1. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  2. 2023DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learningcited by 10
  3. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  4. 2023Optimal Differentially Private Model Training with Public Datacited by 9
  5. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  6. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  7. 2022On the Statistical Complexity of Estimation and Testing under Privacy Constraintscited by 6
  8. 2023On Private and Robust Banditscited by 6
  9. 2023Byzantine-Resilient Federated Learning at Edgecited by 6
  10. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  11. 2021On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updatescited by 5
  12. 2022Differentially Private Online-to-Batch for Smooth Lossescited by 5
  13. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  14. 2024Delving into Differentially Private Transformercited by 5
  15. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  16. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  17. 2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 4
  18. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  19. 2023Private Statistical Estimation of Many Quantilescited by 3
  20. 2024Learning with User-Level Local Differential Privacycited by 3
  21. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  22. 2022DPVIm: Differentially Private Variational Inference Improvedcited by 2
  23. 2023DPFormer: Learning Differentially Private Transformer on Long-Tailed Datacited by 2
  24. 2023About the Cost of Central Privacy in Density Estimationcited by 2
  25. 2025Learning with Differentially Private (Sliced) Wasserstein Gradientscited by 2
  26. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  27. 2025Understanding Private Learning From Feature Perspectivecited by 2
  28. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  29. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  30. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  31. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  32. 2022Efficient Private SCO for Heavy-Tailed Data via Averaged Clippingcited by 0
  33. 2023Learning across Data Owners with Joint Differential Privacycited by 0
  34. 2025Privately Estimating Black-Box Statisticscited by 0
  35. 2026Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tailscited by 0