mlsanityData to 7 Oct 2026

High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data

arXiv 2107.11136 ↗First posted 23 Jul 2021cs.LG cs.CR stat.MLcited by 42

Not on the map. Why?

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.

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

Builds on

28 of 68 references.

References · 28

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  3. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  4. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  5. 2017Collecting Telemetry Data Privatelycited by 147
  6. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  7. 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 88
  8. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  9. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  10. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  11. 2013Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optimacited by 66
  12. 2021Robust and Differentially Private Mean Estimationcited by 66
16 more
  1. 2014On Iterative Hard Thresholding Methods for High-dimensional M-Estimationcited by 53
  2. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  3. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  4. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2017Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12cited by 42
  7. 2014Empirical risk minimization for heavy-tailed lossescited by 37
  8. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  9. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  10. 2016A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recoverycited by 23
  11. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  12. 2020The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Boundscited by 15
  13. 2020Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacycited by 15
  14. 2018Robust descent using smoothed multiplicative noisecited by 6
  15. 2019A Knowledge Transfer Framework for Differentially Private Sparse Learningcited by 5
  16. 2020Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guaranteescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 10; 2023: 8; 2024: 13; 2025: 8; 2026: 3.

42 papers.

Sort:

By area:

  1. 2024Multi-hop Question Answering under Temporal Knowledge Editingcited by 36
  2. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  3. 2023Differentially Private Natural Language Models: Recent Advances and Future Directionscited by 20
  4. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  5. 2024Prompt-SAW: Leveraging Relation-Aware Graphs for Textual Prompt Compressioncited by 18
  6. 2025Towards User-level Private Reinforcement Learning with Human Feedbackcited by 13
  7. 2022High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantizationcited by 11
  8. 2024Dialectical Alignment: Resolving the Tension of 3H and Security Threats of LLMscited by 11
  9. 2024Leveraging Logical Rules in Knowledge Editing: A Cherry on the Topcited by 11
  10. 2023DIFF2: Differential Private Optimization via Gradient Differences for Nonconvex Distributed Learningcited by 10
  11. 2023Differentially Private Non-convex Learning for Multi-layer Neural Networkscited by 10
  12. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
30 more
  1. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  2. 2023Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterationscited by 8
  3. 2024MONAL: Model Autophagy Analysis for Modeling Human-AI Interactionscited by 7
  4. 2024SoK: A Review of Differentially Private Linear Models For High-Dimensional Datacited by 5
  5. 2024Delving into Differentially Private Transformercited by 5
  6. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  7. 2022High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descentcited by 4
  8. 2022Differentially Private Deep Learning with ModelMixcited by 4
  9. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  10. 2023Improved Analysis of Sparse Linear Regression in Local Differential Privacy Modelcited by 4
  11. 2024Efficient Sparse Least Absolute Deviation Regression with Differential Privacycited by 4
  12. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  13. 2024Private Language Models via Truncated Laplacian Mechanismcited by 3
  14. 2025Nearly Optimal Differentially Private ReLU Regressioncited by 3
  15. 2025Second-Order Convergence in Private Stochastic Non-Convex Optimizationcited by 3
  16. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  17. 2023DPFormer: Learning Differentially Private Transformer on Long-Tailed Datacited by 2
  18. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  19. 2025Understanding Private Learning From Feature Perspectivecited by 2
  20. 2022On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Banditscited by 1
  21. 2022Truthful Generalized Linear Modelscited by 1
  22. 2024Better Locally Private Sparse Estimation Given Multiple Samples Per Usercited by 1
  23. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  24. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  25. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  26. 2022Efficient Private SCO for Heavy-Tailed Data via Averaged Clippingcited by 0
  27. 2024SPriFed-OMP: A Differentially Private Federated Learning Algorithm for Sparse Basis Recoverycited by 0
  28. 2024Private Linear Regression with Differential Privacy and PAC Privacycited by 0
  29. 2026Understanding the Impact of Differentially Private Training on Memorization of Long-Tailed Datacited by 0
  30. 2026Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tailscited by 0