Differentially Private Sparse Linear Regression with Heavy-tailed Responses

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 $\tilde{O}(s^{\ast \frac{1}{2}}\cdot (\frac{\log d}{n}{)}^{\frac{\zeta }{1+\zeta }}+s^{\ast \frac{1+2\zeta }{2+2\zeta }}\cdot \left(\frac{{\log }^{2}d}{n\epsilon }{)}^{\frac{\zeta }{1+\zeta }}\right)$ under the $(\epsilon ,\delta )$-DP model, where $n$ is the sample size, $d$ is the dimensionality, $s^{\ast }$ is the sparsity of the parameter, and $\zeta \in (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 $\tilde{O}\left(\frac{(s^{\ast }{)}^{3\mathrm{/}2}\log d}{n\epsilon }\right)\mathrm{.}$ 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.