Sharper Utility Bounds for Differentially Private Models
  In this paper, by introducing Generalized Bernstein condition, we propose the
first $\mathcal{O}\big(\frac{\sqrt{p}}{n\epsilon}\big)$ high probability excess
population risk bound for differentially private algorithms under the
assumptions $G$-Lipschitz, $L$-smooth, and Polyak-{\L}ojasiewicz condition,
based on gradient perturbation method. If we replace the properties
$G$-Lipschitz and $L$-smooth by $\alpha$-H{\"o}lder smoothness (which can be
used in non-smooth setting), the high probability bound comes to
$\mathcal{O}\big(n^{-\frac{\alpha}{1+2\alpha}}\big)$ w.r.t $n$, which cannot
achieve $\mathcal{O}\left(1/n\right)$ when $\alpha\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 $\alpha$-H{\"o}lder smooth and Polyak-{\L}ojasiewicz condition can
achieve $\mathcal{O}\big(\frac{\sqrt{p}}{n\epsilon}\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.
