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

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

## Key facts

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

## Builds on (most cited first, 24 of 24)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Generalized Resilience and Robust Statistics](https://mlsanity.com/paper/1909.08755/) (2019)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Efficient Privacy-Preserving Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1910.13659/) (2019)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Wide Network Learning with Differential Privacy](https://mlsanity.com/paper/2103.01294/) (2021)
- [Robust descent using smoothed multiplicative noise](https://mlsanity.com/paper/1810.06207/) (2018)

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

- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (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)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [Choosing Public Datasets for Private Machine Learning via Gradient Subspace Distance](https://mlsanity.com/paper/2303.01256/) (2023)
- [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)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (2023)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Optimal Differentially Private Model Training with Public Data](https://mlsanity.com/paper/2306.15056/) (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)
- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (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)
- [Differentially Private Online-to-Batch for Smooth Losses](https://mlsanity.com/paper/2210.06593/) (2022)
- [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)
- [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)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)

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