Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
This work addresses privacy-preserving machine learning for binary classification, offering an incremental improvement in handling outliers under differential privacy constraints.
The paper tackles differentially private empirical risk minimization for binary linear classification by developing an efficient algorithm that adaptively achieves an empirical zero-one risk bound of ̃O(1/(γ^2εn) + |S_out|/(γn)), improving existing results when outliers are few, without needing prior knowledge of the margin or outliers.
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.