# On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data

arXiv: https://arxiv.org/abs/2010.11082 · HTML: https://mlsanity.com/paper/2010.11082/

## Key facts

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

## Built on by (most cited first, 30 of 51)

- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach](https://mlsanity.com/paper/2311.14632/) (2023)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [Safeguarding Data in Multimodal AI: A Differentially Private Approach to CLIP Training](https://mlsanity.com/paper/2306.08173/) (2023)
- [Byzantine-Resilient Federated Learning at Edge](https://mlsanity.com/paper/2303.10434/) (2023)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [On the Convergence of Differentially Private Federated Learning on Non-Lipschitz Objectives, and with Normalized Client Updates](https://mlsanity.com/paper/2106.07094/) (2021)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tails](https://mlsanity.com/paper/2405.17529/) (2024)
- [Delving into Differentially Private Transformer](https://mlsanity.com/paper/2405.18194/) (2024)
- [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025)
- [Differentially Private Deep Learning with ModelMix](https://mlsanity.com/paper/2210.03843/) (2022)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds](https://mlsanity.com/paper/2405.02638/) (2024)

## 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.