# Differentially Private Sparse Linear Regression with Heavy-tailed Responses

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 59 references that are in the map.
- First posted on arXiv 7 Jun 2025.

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

- [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)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Adaptive Huber Regression](https://mlsanity.com/paper/1706.06991/) (2017)
- [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)
- [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)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy](https://mlsanity.com/paper/2011.05934/) (2020)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [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)
- [A Knowledge Transfer Framework for Differentially Private Sparse Learning](https://mlsanity.com/paper/1909.06322/) (2019)
- [Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2503.18317/) (2025)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Nearly Optimal Differentially Private ReLU Regression](https://mlsanity.com/paper/2503.06009/) (2025)
- [Truthful High Dimensional Sparse Linear Regression](https://mlsanity.com/paper/2410.13046/) (2024)

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

- [Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition](https://mlsanity.com/paper/2509.04668/) (2025)

## Abstract (arXiv)

As a fundamental problem in machine learning and differential privacy (DP), DP linear regression has been extensively studied. However, most existing methods focus primarily on either regular data distributions or low-dimensional cases with irregular data. To address these limitations, this paper provides a comprehensive study of DP sparse linear regression with heavy-tailed responses in high-dimensional settings. In the first part, we introduce the DP-IHT-H method, which leverages the Huber loss and private iterative hard thresholding to achieve an estimation error bound of ( tildeObiggl( s^* frac1 2 · biggl(fraclog dnbiggr)^fraczeta1 + zeta + s^* frac1 + 2zeta2 + 2zeta · biggl(fraclog2 dn varepsilonbiggr)^fraczeta1 + zeta biggr) ) under the (varepsilon, δ)-DP model, where n is the sample size, d is the dimensionality, s^* is the sparsity of the parameter, and zeta ∈ (0, 1] characterizes the tail heaviness of the data. In the second part, we propose DP-IHT-L, which further improves the error bound under additional assumptions on the response and achieves ( tildeOBigl(frac(s^*)3/2 log dn varepsilonBigr). ) Compared to the first result, this bound is independent of the tail parameter zeta. Finally, through experiments on synthetic and real-world datasets, we demonstrate that our methods outperform standard DP algorithms designed for ``regular'' data.