mlsanityData to 7 Oct 2026

On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data

arXiv 2010.11082 ↗First posted 21 Oct 2020cs.LG cs.CR stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider the problem of designing Differentially Private (DP) algorithms for Stochastic Convex Optimization (SCO) on heavy-tailed data. The irregularity of such data violates some key assumptions used in almost all existing DP-SCO and DP-ERM methods, resulting in failure to provide the DP guarantees. To better understand this type of challenges, we provide in this paper a comprehensive study of DP-SCO under various settings. First, we consider the case where the loss function is strongly convex and smooth. For this case, we propose a method based on the sample-and-aggregate framework, which has an excess population risk of tildeO(fracd3nε4) (after omitting other factors), where n is the sample size and d is the dimensionality of the data. Then, we show that with some additional assumptions on the loss functions, it is possible to reduce the textitexpected excess population risk to tildeO(frac d2 nε2 ). To lift these additional conditions, we also provide a gradient smoothing and trimming based scheme to achieve excess population risks of tildeO(frac d2nε2) and tildeO(fracd^frac23(nε2)^frac13) for strongly convex and general convex loss functions, respectively, textitwith high probability. Experiments suggest that our algorithms can effectively deal with the challenges caused by data irregularity.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 11; 2023: 13; 2024: 6; 2025: 10; 2026: 3.

51 papers.

Sort:

  1. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  2. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  3. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  4. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  5. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  6. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  7. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  8. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  9. 2022Differentially Private SGDA for Minimax Problemscited by 23
  10. 2023Differentially Private Natural Language Models: Recent Advances and Future Directionscited by 20
  11. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  12. 2023Differentially Private SGD Without Clipping Bias: An Error-Feedback Approachcited by 13
38 more
  1. 2021Faster Rates of Private Stochastic Convex Optimizationcited by 12
  2. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  3. 2023DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learningcited by 10
  4. 2023Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compressioncited 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. 2023Safeguarding Data in Multimodal AI: A Differentially Private Approach to CLIP Trainingcited by 7
  8. 2023Byzantine-Resilient Federated Learning at Edgecited by 6
  9. 2024Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductionscited by 6
  10. 2021On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updatescited by 5
  11. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  12. 2024Delving into Differentially Private Transformercited by 5
  13. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  14. 2022Differentially Private Deep Learning with ModelMixcited by 4
  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. 2024PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Boundscited by 4
  18. 2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 4
  19. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  20. 2022Private optimization in the interpolation regime: faster rates and hardness resultscited by 3
  21. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  22. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  23. 2022Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problemscited by 2
  24. 2023DPFormer: Learning Differentially Private Transformer on Long-Tailed Datacited by 2
  25. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  26. 2025Understanding Private Learning From Feature Perspectivecited by 2
  27. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  28. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  29. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  30. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  31. 2025DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communicationcited by 1
  32. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  33. 2022Efficient Private SCO for Heavy-Tailed Data via Averaged Clippingcited by 0
  34. 2023Learning across Data Owners with Joint Differential Privacycited by 0
  35. 2024Private Linear Regression with Differential Privacy and PAC Privacycited by 0
  36. 2025On Theoretical Limits of Learning with Label Differential Privacycited by 0
  37. 2025Dyn-D2P: Dynamic Differentially Private Decentralized Learning with Provable Utility Guaranteecited by 0
  38. 2026Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Datacited by 0

50 most cited of 51 All 51 (JSON)