# Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 39 references that are in the map.
- First posted on arXiv 4 Jun 2024.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [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)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [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)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Adapting to Function Difficulty and Growth Conditions in Private Optimization](https://mlsanity.com/paper/2108.02391/) (2021)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (2023)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Variance Reduction and Low Sample Complexity in Stochastic Optimization via Proximal Point Method](https://mlsanity.com/paper/2402.08992/) (2024)

## Built on by (most cited first, 6 of 6)

- [Faster Algorithms for User-Level Private Stochastic Convex Optimization](https://mlsanity.com/paper/2410.18391/) (2024)
- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)
- [Private Geometric Median in Nearly-Linear Time](https://mlsanity.com/paper/2505.20189/) (2025)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)
- [R'enyi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincar'e Inequalities](https://mlsanity.com/paper/2511.15634/) (2025)
- [Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails](https://mlsanity.com/paper/2604.06492/) (2026)

## Abstract (arXiv)

We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a kth-moment bound on the Lipschitz constants of sample functions rather than a uniform bound. We propose a new reduction-based approach that enables us to obtain the first optimal rates (up to logarithmic factors) in the heavy-tailed setting, achieving error G2 · frac 1 √ n + Gk · (frac√ dnε)1 - frac 1 k under (ε, δ)-approximate differential privacy, up to a mild textuppolylog(frac1δ) factor, where G22 and Gkk are the 2nd and kth moment bounds on sample Lipschitz constants, nearly-matching a lower bound of [Lowy and Razaviyayn 2023]. We further give a suite of private algorithms in the heavy-tailed setting which improve upon our basic result under additional assumptions, including an optimal algorithm under a known-Lipschitz constant assumption, a near-linear time algorithm for smooth functions, and an optimal linear time algorithm for smooth generalized linear models.