Sharper Utility Bounds for Differentially Private Models: Smooth and Non-smooth

In this paper, by introducing Generalized Bernstein condition, we propose the first O(root p/n is an element of) high probability excess population risk bound for differentially private algorithms under the assumptions G-Lipschitz, L-smooth, and Polyak-Lojasiewicz condition, based on gradient perturbation method. If we replace the propertiesG-Lipschitz and L-smooth by alpha-Holder smoothness (which can be used in non-smooth setting), the high probability bound comes to O(n-alpha/1+2 alpha) w.r.t. n, which cannot achieve O (1/n) when alpha is an element of (0, 1]. To solve this problem, we propose a variant of gradient perturbation method, max{1,g}-Normalized Gradient Perturbation (m-NGP). We further show that by normalization, the high probability excess population risk bound under assumptions alpha-Holder smooth and Polyak-Lojasiewicz condition can achieve O(root p/n is an element of), which is the first O (1/n) high probability excess population risk bound w.r.t. n for differentially private algorithms under non-smooth conditions. Moreover, experimental results show that m-NGP improves the performance of the differentially private model over real datasets.