# Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 26 references that are in the map.
- First posted on arXiv 7 Apr 2026.

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

- [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)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (2021)
- [Private Adaptive Gradient Methods for Convex Optimization](https://mlsanity.com/paper/2106.13756/) (2021)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap](https://mlsanity.com/paper/2302.12909/) (2023)
- [Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data](https://mlsanity.com/paper/2201.03204/) (2022)
- [Output Perturbation for Differentially Private Convex Optimization: Faster and More General](https://mlsanity.com/paper/2102.04704/) (2021)
- [Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions](https://mlsanity.com/paper/2406.02789/) (2024)
- [Faster Algorithms for User-Level Private Stochastic Convex Optimization](https://mlsanity.com/paper/2410.18391/) (2024)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)
- [Purifying Approximate Differential Privacy with Randomized Post-processing](https://mlsanity.com/paper/2503.21071/) (2025)
- [Differentially Private Bilevel Optimization: Efficient Algorithms with Near-Optimal Rates](https://mlsanity.com/paper/2506.12994/) (2025)

## Abstract (arXiv)

We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure varepsilon-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded k-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. Prior work characterized the minimax optimal rate for ρ-zero-concentrated DP SCO up to logarithmic factors in this setting, but the pure varepsilon-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure varepsilon-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in deterministic polynomial time when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes -- including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes -- we achieve deterministic polynomial time even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our upper bound with a nearly matching high-probability lower bound.