# High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 68 references that are in the map.
- First posted on arXiv 23 Jul 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2010.11082/) (2020)
- [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)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent](https://mlsanity.com/paper/2006.06783/) (2020)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery](https://mlsanity.com/paper/1603.08315/) (2016)
- [Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy](https://mlsanity.com/paper/2011.05934/) (2020)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [Robust descent using smoothed multiplicative noise](https://mlsanity.com/paper/1810.06207/) (2018)
- [A Knowledge Transfer Framework for Differentially Private Sparse Learning](https://mlsanity.com/paper/1909.06322/) (2019)
- [Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guarantees](https://mlsanity.com/paper/2010.13520/) (2020)

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

- [Multi-hop Question Answering under Temporal Knowledge Editing](https://mlsanity.com/paper/2404.00492/) (2024)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (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)
- [Prompt-SAW: Leveraging Relation-Aware Graphs for Textual Prompt Compression](https://mlsanity.com/paper/2404.00489/) (2024)
- [Towards User-level Private Reinforcement Learning with Human Feedback](https://mlsanity.com/paper/2502.17515/) (2025)
- [High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization](https://mlsanity.com/paper/2202.13157/) (2022)
- [Leveraging Logical Rules in Knowledge Editing: A Cherry on the Top](https://mlsanity.com/paper/2405.15452/) (2024)
- [Dialectical Alignment: Resolving the Tension of 3H and Security Threats of LLMs](https://mlsanity.com/paper/2404.00486/) (2024)
- [DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learning](https://mlsanity.com/paper/2302.03884/) (2023)
- [Differentially Private Non-convex Learning for Multi-layer Neural Networks](https://mlsanity.com/paper/2310.08425/) (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)
- [Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations](https://mlsanity.com/paper/2310.19978/) (2023)
- [MONAL: Model Autophagy Analysis for Modeling Human-AI Interactions](https://mlsanity.com/paper/2402.11271/) (2024)
- [SoK: A Review of Differentially Private Linear Models For High-Dimensional Data](https://mlsanity.com/paper/2404.01141/) (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)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [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)
- [Efficient Sparse Least Absolute Deviation Regression with Differential Privacy](https://mlsanity.com/paper/2401.01294/) (2024)
- [Private Stochastic Optimization With Large Worst-Case Lipschitz Parameter](https://mlsanity.com/paper/2209.07403/) (2022)
- [Private Language Models via Truncated Laplacian Mechanism](https://mlsanity.com/paper/2410.08027/) (2024)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)
- [Second-Order Convergence in Private Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2505.15647/) (2025)
- [An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise](https://mlsanity.com/paper/2508.10879/) (2025)
- [Understanding Private Learning From Feature Perspective](https://mlsanity.com/paper/2511.18006/) (2025)
- [DPFormer: Learning Differentially Private Transformer on Long-Tailed Data](https://mlsanity.com/paper/2305.17633/) (2023)

## Abstract (arXiv)

As one of the most fundamental problems in machine learning, statistics and differential privacy, Differentially Private Stochastic Convex Optimization (DP-SCO) has been extensively studied in recent years. However, most of the previous work can only handle either regular data distribution or irregular data in the low dimensional space case. To better understand the challenges arising from irregular data distribution, in this paper we provide the first study on the problem of DP-SCO with heavy-tailed data in the high dimensional space. In the first part we focus on the problem over some polytope constraint (such as the ℓ1-norm ball). We show that if the loss function is smooth and its gradient has bounded second order moment, it is possible to get a (high probability) error bound (excess population risk) of tildeO(fraclog d(nε)^frac13) in the ε-DP model, where n is the sample size and d is the dimensionality of the underlying space. Next, for LASSO, if the data distribution that has bounded fourth-order moments, we improve the bound to tildeO(fraclog d(nε)^frac25) in the (ε, δ)-DP model. In the second part of the paper, we study sparse learning with heavy-tailed data. We first revisit the sparse linear model and propose a truncated DP-IHT method whose output could achieve an error of tildeO(fracs*2log dnε), where s^* is the sparsity of the underlying parameter. Then we study a more general problem over the sparsity (em i.e., ℓ0-norm) constraint, and show that it is possible to achieve an error of tildeO(fracs^*frac32log dnε), which is also near optimal up to a factor of tildeO(√s^*), if the loss function is smooth and strongly convex.