Nearly Optimal Differentially Private ReLU Regression
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908401628348416 |
|---|---|
| author | Ding, Meng Lei, Mingxi Wang, Shaowei Zheng, Tianhang Wang, Di Xu, Jinhui |
| author_facet | Ding, Meng Lei, Mingxi Wang, Shaowei Zheng, Tianhang Wang, Di Xu, Jinhui |
| contents | In this paper, we investigate one of the most fundamental nonconvex learning problems, ReLU regression, in the Differential Privacy (DP) model. Previous studies on private ReLU regression heavily rely on stringent assumptions, such as constant bounded norms for feature vectors and labels. We relax these assumptions to a more standard setting, where data can be i.i.d. sampled from $O(1)$-sub-Gaussian distributions. We first show that when $\varepsilon = \tilde{O}(\sqrt{\frac{1}{N}})$ and there is some public data, it is possible to achieve an upper bound of $\tilde{O}(\frac{d^2}{N^2 \varepsilon^2})$ for the excess population risk in $(ε, δ)$-DP, where $d$ is the dimension and $N$ is the number of data samples. Moreover, we relax the requirement of $ε$ and public data by proposing and analyzing a one-pass mini-batch Generalized Linear Model Perceptron algorithm (DP-MBGLMtron). Additionally, using the tracing attack argument technique, we demonstrate that the minimax rate of the estimation error for $(\varepsilon, δ)$-DP algorithms is lower bounded by $Ω(\frac{d^2}{N^2 \varepsilon^2})$. This shows that DP-MBGLMtron achieves the optimal utility bound up to logarithmic factors. Experiments further support our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06009 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nearly Optimal Differentially Private ReLU Regression Ding, Meng Lei, Mingxi Wang, Shaowei Zheng, Tianhang Wang, Di Xu, Jinhui Machine Learning In this paper, we investigate one of the most fundamental nonconvex learning problems, ReLU regression, in the Differential Privacy (DP) model. Previous studies on private ReLU regression heavily rely on stringent assumptions, such as constant bounded norms for feature vectors and labels. We relax these assumptions to a more standard setting, where data can be i.i.d. sampled from $O(1)$-sub-Gaussian distributions. We first show that when $\varepsilon = \tilde{O}(\sqrt{\frac{1}{N}})$ and there is some public data, it is possible to achieve an upper bound of $\tilde{O}(\frac{d^2}{N^2 \varepsilon^2})$ for the excess population risk in $(ε, δ)$-DP, where $d$ is the dimension and $N$ is the number of data samples. Moreover, we relax the requirement of $ε$ and public data by proposing and analyzing a one-pass mini-batch Generalized Linear Model Perceptron algorithm (DP-MBGLMtron). Additionally, using the tracing attack argument technique, we demonstrate that the minimax rate of the estimation error for $(\varepsilon, δ)$-DP algorithms is lower bounded by $Ω(\frac{d^2}{N^2 \varepsilon^2})$. This shows that DP-MBGLMtron achieves the optimal utility bound up to logarithmic factors. Experiments further support our theoretical results. |
| title | Nearly Optimal Differentially Private ReLU Regression |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2503.06009 |