Differentially Private Sparse Linear Regression with Heavy-tailed Responses
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908398694432768 |
|---|---|
| author | Tian, Xizhi Ding, Meng Tao, Touming Xiang, Zihang Wang, Di |
| author_facet | Tian, Xizhi Ding, Meng Tao, Touming Xiang, Zihang Wang, Di |
| contents | 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}\biggl(
s^{* \frac{1 }{2}}
\cdot \biggl(\frac{\log d}{n}\biggr)^{\fracζ{1 + ζ}}
+
s^{* \frac{1 + 2ζ}{2 + 2ζ}}
\cdot \biggl(\frac{\log^2 d}{n \varepsilon}\biggr)^{\fracζ{1 + ζ}}
\biggr) \) under the $(\varepsilon, δ)$-DP model, where $n$ is the sample size, $d$ is the dimensionality, $s^*$ is the sparsity of the parameter, and $ζ\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}\Bigl(\frac{(s^*)^{3/2} \log d}{n \varepsilon}\Bigr). \) Compared to the first result, this bound is independent of the tail parameter $ζ$. Finally, through experiments on synthetic and real-world datasets, we demonstrate that our methods outperform standard DP algorithms designed for ``regular'' data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06861 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Sparse Linear Regression with Heavy-tailed Responses Tian, Xizhi Ding, Meng Tao, Touming Xiang, Zihang Wang, Di Machine Learning Cryptography and Security 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}\biggl( s^{* \frac{1 }{2}} \cdot \biggl(\frac{\log d}{n}\biggr)^{\fracζ{1 + ζ}} + s^{* \frac{1 + 2ζ}{2 + 2ζ}} \cdot \biggl(\frac{\log^2 d}{n \varepsilon}\biggr)^{\fracζ{1 + ζ}} \biggr) \) under the $(\varepsilon, δ)$-DP model, where $n$ is the sample size, $d$ is the dimensionality, $s^*$ is the sparsity of the parameter, and $ζ\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}\Bigl(\frac{(s^*)^{3/2} \log d}{n \varepsilon}\Bigr). \) Compared to the first result, this bound is independent of the tail parameter $ζ$. Finally, through experiments on synthetic and real-world datasets, we demonstrate that our methods outperform standard DP algorithms designed for ``regular'' data. |
| title | Differentially Private Sparse Linear Regression with Heavy-tailed Responses |
| topic | Machine Learning Cryptography and Security |
| url | https://arxiv.org/abs/2506.06861 |