Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.24737 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915313758502912 |
|---|---|
| author | Wang, Erchi Zhu, Yuqing Wang, Yu-Xiang |
| author_facet | Wang, Erchi Zhu, Yuqing Wang, Yu-Xiang |
| contents | This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification. We obtain an efficient $(\varepsilon,δ)$-DP algorithm with an empirical zero-one risk bound of $\tilde{O}\left(\frac{1}{γ^2\varepsilon n} + \frac{|S_{\mathrm{out}}|}{γn}\right)$ where $n$ is the number of data points, $S_{\mathrm{out}}$ is an arbitrary subset of data one can remove and $γ$ is the margin of linear separation of the remaining data points (after $S_{\mathrm{out}}$ is removed). Here, $\tilde{O}(\cdot)$ hides only logarithmic terms. In the agnostic case, we improve the existing results when the number of outliers is small. Our algorithm is highly adaptive because it does not require knowing the margin parameter $γ$ or outlier subset $S_{\mathrm{out}}$. We also derive a utility bound for the advanced private hyperparameter tuning algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_24737 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning Wang, Erchi Zhu, Yuqing Wang, Yu-Xiang Machine Learning This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification. We obtain an efficient $(\varepsilon,δ)$-DP algorithm with an empirical zero-one risk bound of $\tilde{O}\left(\frac{1}{γ^2\varepsilon n} + \frac{|S_{\mathrm{out}}|}{γn}\right)$ where $n$ is the number of data points, $S_{\mathrm{out}}$ is an arbitrary subset of data one can remove and $γ$ is the margin of linear separation of the remaining data points (after $S_{\mathrm{out}}$ is removed). Here, $\tilde{O}(\cdot)$ hides only logarithmic terms. In the agnostic case, we improve the existing results when the number of outliers is small. Our algorithm is highly adaptive because it does not require knowing the margin parameter $γ$ or outlier subset $S_{\mathrm{out}}$. We also derive a utility bound for the advanced private hyperparameter tuning algorithm. |
| title | Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.24737 |