Sharper Utility Bounds for Differentially Private Models
This work addresses utility limitations in differentially private algorithms for non-smooth settings, offering incremental improvements for privacy-preserving machine learning.
The paper tackles the problem of improving utility bounds for differentially private models under non-smooth conditions by proposing a new gradient perturbation method called m-NGP, achieving the first O(1/n) high probability excess population risk bound and showing improved performance on real datasets.
In this paper, by introducing Generalized Bernstein condition, we propose the first $\mathcal{O}\big(\frac{\sqrt{p}}{nε}\big)$ high probability excess population risk bound for differentially private algorithms under the assumptions $G$-Lipschitz, $L$-smooth, and Polyak-Łojasiewicz condition, based on gradient perturbation method. If we replace the properties $G$-Lipschitz and $L$-smooth by $α$-H{ö}lder smoothness (which can be used in non-smooth setting), the high probability bound comes to $\mathcal{O}\big(n^{-\fracα{1+2α}}\big)$ w.r.t $n$, which cannot achieve $\mathcal{O}\left(1/n\right)$ when $α\in(0,1]$. To solve this problem, we propose a variant of gradient perturbation method, \textbf{max$\{1,g\}$-Normalized Gradient Perturbation} (m-NGP). We further show that by normalization, the high probability excess population risk bound under assumptions $α$-H{ö}lder smooth and Polyak-Łojasiewicz condition can achieve $\mathcal{O}\big(\frac{\sqrt{p}}{nε}\big)$, which is the first $\mathcal{O}\left(1/n\right)$ high probability excess population risk bound w.r.t $n$ for differentially private algorithms under non-smooth conditions. Moreover, we evaluate the performance of the new proposed algorithm m-NGP, the experimental results show that m-NGP improves the performance of the differentially private model over real datasets. It demonstrates that m-NGP improves the utility bound and the accuracy of the DP model on real datasets simultaneously.