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 ( 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.