mlsanityData to 7 Oct 2026

Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Data

arXiv 2201.03204 ↗First posted 10 Jan 2022cs.LG cs.CR stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

We study the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) with heavy-tailed data. Specifically, we focus on the ℓ1-norm linear regression in the ε-DP model. While most of the previous work focuses on the case where the loss function is Lipschitz, here we only need to assume the variates has bounded moments. Firstly, we study the case where the ℓ2 norm of data has bounded second order moment. We propose an algorithm which is based on the exponential mechanism and show that it is possible to achieve an upper bound of tildeO(√fracdnε) (with high probability). Next, we relax the assumption to bounded θ-th order moment with some θ∈ (1, 2) and show that it is possible to achieve an upper bound of tildeO((fracdnε)^fracθ-1θ). Our algorithms can also be extended to more relaxed cases where only each coordinate of the data has bounded moments, and we can get an upper bound of tildeO(fracd√nε) and tildeO(fracd(nε)^fracθ-1θ) in the second and θ-th moment case respectively.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 16 of its 28 references that are in the map. First posted on arXiv 10 Jan 2022.

Builds on

16 of 28 references.

References · 16

  1. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  2. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  3. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  4. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  5. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  6. 2021Robust and Differentially Private Mean Estimationcited by 66
  7. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  8. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  9. 2021Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 51
  10. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  11. 2021Private Adaptive Gradient Methods for Convex Optimizationcited by 46
  12. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
4 more
  1. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  2. 2020Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descentcited by 27
  3. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  4. 2021Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Stepscited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 1; 2025: 3; 2026: 1.

8 papers.

  1. 2023Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisitedcited by 8
  2. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  3. 2024Efficient Sparse Least Absolute Deviation Regression with Differential Privacycited by 4
  4. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  5. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  6. 2025Differentially Private Sparse Linear Regression with Heavy-tailed Responsescited by 1
  7. 2025Private Sketches for Linear Regressioncited by 0
  8. 2026Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tailscited by 0