Year: 2021

Abstract:
In this paper, by introducing Generalized Bernstein condition, we propose the first O (√p n ) 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 nonsmooth setting), the high probability bound comes to O ( n− 2α 1+2α ) w.r.t n, which cannot achieve O (1/n) when α ∈ (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 α-Hölder smooth and PolyakŁojasiewicz condition can achieveO (√p n ) , which is the firstO (1/n) high probability utility 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 (measured by accuracy) of the DP model over real datasets. It demonstrates that m-NGP improves the excess population risk bound and the accuracy of the DP model on real datasets simultaneously.

text: ) high probability excess population risk bound for differentially private al-
gorithms 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 α-Hölder smoothness (which can be used in nonsmooth setting), the high probability bound comes to O ( n− 2α 1+2α ) w.r.t n, which cannot achieve O (1/n) when α ∈ (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 α-Hölder smooth and PolyakŁojasiewicz condition can achieveO (√p n ) , which is the firstO (1/n) high probability utility 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 (measured by accuracy) of the DP model over real datasets. It demonstrates that m-NGP improves the excess population risk bound and the accuracy of the DP model on real datasets simultaneously.

heading: 1 INTRODUCTION
text: Machine learning has been widely used and found effective in many fields in recent years (Singha et al., 2021; Swapna & Soman, 2021; Ponnusamy et al., 2021). When training machine learning models, tremendous data was collected, and the data often contains sensitive information of individuals, which may leakage personal privacy (Shokri et al., 2017; Carlini et al., 2019).
Differential Privacy (DP) (Dwork et al., 2006; Dwork & Lei, 2009; Dwork et al., 2014) is a theoretically rigorous tool to prevent sensitive information. It introduces random noise to the machine learning model and blocks adversaries from inferring any single individual included in the dataset by observing the model. The mathematical definition of DP is well accepted and relative technologies are performed by Google (Erlingsson et al., 2014), Apple (McMillan, 2016) and Microsoft (Ding et al., 2017). As such, DP has attracted attention from the researchers and has been applied to numerous machine learning problems (Ullman & Sealfon, 2019; Xu et al., 2019; Bernstein & Sheldon, 2019; Wang & Xu, 2019; Heikkilä et al., 2019; Kulkarni et al., 2021; Bun et al., 2021; Nguyen & Vullikanti, 2021).
There are mainly three approaches to guarantee differential privacy: output perturbation (Chaudhuri et al., 2011), objective perturbation (Chaudhuri et al., 2011), and gradient perturbation (Song et al., 2013). Considering that gradient descent is a widely used optimization method, the gradient perturbation method can be used for a wide range of applications, and adding random noise to the gradient allows the model to escape local minima (Raginsky et al., 2017), we focus on the gradient perturbation method to guarantee DP in this paper.
In this paper, we aim to minimize the population risk, and measure the utility of the DP model by the excess population risk. To get the excess population risk, an important step is to analyze the generalization error (the reason is demonstrated in Section 3). Complexity theory (Bartlett et al., 2002) and algorithm stability theory (Bousquet & Elisseeff, 2002) are popular tools to analyze the generalization error. On one hand, Chaudhuri et al. (2011) applied the complexity theory and achieved
an O ( max{ 1√ n , 2/3 √ p n } ) high probability excess population risk bound under the assumption of
strongly convex; Kifer et al. (2012) achieved O (√p n ) expected excess population risk bound via complexity theory. On the other hand, the sharpest known high probability generalization bounds for DP algorithms analyzed via stability theory under different assumptions (Wu et al., 2017; Bassily et al., 2019; Feldman et al., 2020; Bassily et al., 2020; Wang et al., 2021) are O (√p n + 1√ n ) or
O ( 4√p√
n
) , containing an inevitable O ( 1√ n ) term, which is a bottleneck on the utility analysis. Thus,
we are focusing on the following question, which is still an open problem: Can we achieve the high probability excess risk bounds with rate O( √ p
n ) for differentially private models via uniform stability?
This paper answers the question positively under more (or different) assumptions and provides the first high probability bound allowing an O (√p n ) rate of convergence in the setting of DP. By in-
troducing Generalized Bernstein condition (Koltchinskii, 2006), we remove the O (
1√ n
) term in
the generalization error and furthermore improve the high probability excess population risk bound. Comparing with previous high probability bounds, the improvement is approximately up toO ( √ n).
CONTRIBUTIONS
We first prove that by introducing Generalized Bernstein condition (Koltchinskii, 2006), under the assumptions G-Lipschitz, L-smooth, and Polyak-Łojasiewicz (PL) condition, the high probability excess population risk bound can be improved to O (√p n ) . To the best of our knowledge, this is the
first O (√p n ) high probability excess population risk bound in the field of DP.
Then, we relax the assumptions G-Lipschitz and L-smooth, by introducing α-Hölder smooth. Under these assumptions, we prove that the high probability excess population risk bound comes to O (√p n −2α 1+2α ) . Considering that α ∈ (0, 1], the result cannot achieve O (√p n ) .
To overcome the bottleneck, we design a variant of gradient perturbation method, called max {1, g}Normalized Gradient Perturbation (m-NGP) algorithm. Via this new proposed algorithm, we prove that under the assumptions α-Hölder smooth, PL condition, and generalized Bernstein condition, the high probability excess population risk bound can be improved to O (√p n ) . To the best of
our knowledge, this is the firstO (√p n ) high probability excess population risk bound for non-smooth loss in the field of DP.
Moreover, to evaluate the performance of our proposed max {1, g}-Normalized Gradient Perturbation algorithm, we perform experiments on real datasets, the experimental results show that m-NGP method also improves the accuracy of the DP model on real datasets.
The rest of the paper is organized as follows. We discuss some related work in Section 2. Some preliminaries are formally introduced in Section 3. In Section 4, we propose sharper utility bounds under different assumptions and design a variant of gradient perturbation method, max {1, g}Normalized Gradient Perturbation. The experimental results are shown in Section 5. Finally, we conclude the paper in Section 6.

heading: 2 RELATED WORK
text: Dwork et al. (2006) proposed the mathematical definition of DP for the first time. Then, it was developed to protect the privacy in the field of machine learning (e.g. Empirical Risk Minimization (ERM)) via output perturbation, objective perturbation, and gradient perturbation methods. For DP-ERM formulations, Chaudhuri et al. (2011) first proposed output perturbation and objective perturbation methods, and Song et al. (2013) first proposed the gradient perturbation method. Based on these works, Kifer et al. (2012); Bassily et al. (2014); Abadi et al. (2016); Wang et al. (2017); Zhang et al. (2017); Wu et al. (2017); Bassily et al. (2019); Feldman et al. (2020); Bassily et al. (2020) further improved the results under different assumptions.
Among the works mentioned above, some of them only analyzed the privacy guarantees (Song et al., 2013; Abadi et al., 2016), some of them only discussed the excess empirical risk bound (Wang et al., 2017; Zhang et al., 2017; Wu et al., 2017). Some works discussed the excess population risk under expectation, from different points of view, such as complexity theory, optimization theory, and stability theory: Kifer et al. (2012) achieved an O (√p n ) expected excess population risk bound via complexity theory; Bassily et al. (2014) achieved similar expected bound under convexity assumption, via optimization theory; and Wang et al. (2019) proposed anO ( p
log(n) 2
) expected excess pop-
ulation risk bound under non-convex condition, via Langevin Dynamics (Gelfand & Mitter, 1991) and the stability of Gibbs algorithm.
Considering that the high probability bound is more concerned by researchers, we focus on the high probability utility bound. Meanwhile, we concentrate on the stability theory in this paper. Among many notions of stability, uniform stability is arguably the most popular one, which yields exponential generalization bounds. Via uniform stability, the high probability excess population risk bounds under different assumptions given by previous works all contain anO ( 1√ n ) term, details can be found in Table 1. The reason is that when analyzing the generalization error, the technical routes followed works Bousquet & Elisseeff (2002); Hardt et al. (2016). In this paper, by introducing Generalized Bernstein condition (Koltchinskii, 2006), we remove the O (
1√ n
) term from the generalization error, and further improve the excess population risk bound of
DP models. The improved convergence rate is up toO (√p n ) , which positively answers the question: Can the high probability excess population risk bound achieve O (1/n) w.r.t n. The improvements are shown in Table 1.
Table 1 first shows that by adding more assumptions (we assume the loss function to be Lipschitz, smooth, and satisfy Polyak-Łojasiewicz (PL) condition, while previous results require α-Hölder smoothness and convexity), we achieve a better high probability excess population risk bound, O (√p n ) , which is state-of-the-art to the best of our knowledge. Then, we replace the Lipschitz
and smooth property by α-Hölder smoothness and achieveO ( √p n 2α 1+2α ) high probability excess population risk bound, when α ∈ [ 12 , 1], our result is better than previous ones, but it cannot achieve
the same bound (O (1/n) w.r.t n) under the condition that the loss function is Lipschitz, smooth, and satisfies PL condition. To overcome it, we propose an algorithm called m-NGP, and achieve the O (√p n ) result under the same assumptions: α-Hölder smooth and PL condition.
Moreover, although it is hard to directly compare PL condition with convexity, PL condition can be applied to many non-convex conditions (more information can be found in Section 4.2). So, in this paper, we analyze the utility bound of DP algorithm under cases different from previous scenarios.

heading: 3 PRELIMINARIES
text: In this paper, we assume that there are n data instances in dataset D, i.e. D = {z1, · · · , zn} where z = (x, y) with input x ∈ X and label y ∈ Y , and Z = X ×Y . The data space is denoted by D and the parameter space is denoted by C, the loss function ` is defined as `(·, ·) : D×C → R. Databases D,D′ ∈ Dn differing by one data instance are denoted as D ∼ D′, called adjacent databases. For a given vector x = [x1, · · · , xd]T , its `2-norm is ‖x‖2 = ( ∑d i=1 |xi|2) 1 2 . And A . B represents that there exists c > 0, A ≤ cB. Definition 1 (Differential Privacy (Dwork et al., 2006)). A randomized algorithm: A : Dn → Rp is ( , δ)-differential privacy (DP) if for all D ∼ D′ and events S ∈ range(A):
P [A(D) ∈ S] ≤ e P [A(D′) ∈ S] + δ.
Definition 1 implies that the adversaries cannot infer whether an individual participates when training the machine learning model, because essentially the same distributions will be drawn over any adjacent datasets. Some kind of attacks, such as membership inference attack, attribute inference attack, and memorization attack, can be thwarted by DP (Backes et al., 2016; Jayaraman & Evans, 2019; Carlini et al., 2019).
Throughout this paper, we focus on gradient perturbation method to guarantee ( , δ)-DP, the paradigm is based on gradient descent: at iteration t,
θ̂t ← θ̂t−1 − ηt ( ∇θRn(θ̂t−1) + b ) , (1)
where ηt is the learning rate, b is the random noise injected into the gradient, θ̂ is corresponding model with privacy, and Rn(θ) is the empirical risk, defined as Rn(θ) := 1n ∑n i=1 `(zi, θ).
In this paper, we focus on minimizing the population risk: R(θ) = Ez∼D [`(z, θ)]. In the setting of DP, the excess population risk is defined by R(θ̂)−minθ∈C R(θ), which can be decomposed into:
R(θ̂n)−R(θ∗) = R(θ̂n)−Rn(θ̂n) +Rn(θ̂n)−Rn(θ∗) +Rn(θ∗)−R(θ∗) ≤ R(θ̂n)−Rn(θ̂n)︸ ︷︷ ︸
GE
+Rn(θ̂n)−Rn(θ∗n)︸ ︷︷ ︸ OE +Rn(θ ∗)−R(θ∗), (2)
where θ∗ = argminθ∈C R(θ), θ ∗ n = argminθ∈C Rn(θ), and the last inequality is becasuse of the definition of θ∗n. In (2), GE, OE mean the generalization error and the optimization error (also called the excess empirical risk), respectively. Inequality (2) answers the question mentioned in Section 1: Why generalization error is an important step towards excess population risk.
To get the generalization error, algorithm stability theory is a popular tool, in which uniform stability yields exponential generalization bounds and is commonly used. Definition 2 (Uniform Stability (Bousquet & Elisseeff, 2002)). An algorithm θn is γ-uniformly stable if for any z, z1, · · · , zi, · · · , zn, z′i ∈ Z and i = 1, · · · , n, it holds that
|`(z, θn(z1, · · · , zn))− `(z, θn(z1, · · · , zi−1, z′i, zi+1, · · · , zn))| ≤ γ.
In this paper, we use notation θn for both algorithm and model parameter. By Definition 2, it is easy to follow that the uniform stability measures the upper bound of the difference (on the loss function) between the models derived from adjacent datasets. Assumption 1 (G-Lipschitz). The loss function ` : D × C → R is G-Lipschitz over θ if for any z ∈ D and θ1, θ2 ∈ C, we have: |`(z, θ1)− `(z, θ2)| ≤ G‖θ1 − θ2‖2.
Assumption 2 (L-smooth). The loss function ` : D × C → R is L-smooth over θ if for any z ∈ D and θ1, θ2 ∈ C, we have: ‖∇θ`(z, θ1)−∇θ`(z, θ2)‖2 ≤ L‖θ1 − θ2‖2.
If ` is differentiable, smoothness yields: `(z, θ1)−`(z, θ2) ≤ 〈∇θ`(z, θ2), θ1−θ2〉+ L2 ‖θ1 − θ2‖ 2 2.
Assumptions G-Lipschitz and L-smooth are commonly used in the utility analysis of DP machine learning (Chaudhuri et al., 2011; Kifer et al., 2012; Abadi et al., 2016; Bassily et al., 2019; Feldman et al., 2020; Bassily et al., 2020). To relax the Lipschitz and smoothness assumptions, we introduce the α-Hölder smoothness of the loss function: Assumption 3 (α-Hölder smooth). Let α ∈ (0, 1]. The loss function ` : D × C → R is α-Hölder smooth over θ with parameter H if for any z ∈ D and θ1, θ2 ∈ C, we have: ‖∇θ`(z, θ1)−∇θ`(z, θ2)‖2 ≤ H‖θ1 − θ2‖α2 . Lemma 1. If the loss function `(·, ·) is differentiable, then Assumption 3 yields `(z, θ1)− `(z, θ2) ≤ 〈∇θ`(z, θ2), θ1 − θ2〉+ H2 ‖θ1 − θ2‖ α+1 2 .
By the definition, it is easy to follow that if α = 1, it is equivalent to H-smooth; and if α → 0, it satisfies the Lipschitz property given in Assumption 1. Besides, with bounded parameter space, i.e. ‖C‖2 ≤ MC , α-Hölder smoothness immediately implies max{2HMC , H}-Lipschitz. Moreover, Assumption 3 instantiates many non-smooth loss functions. For example, the q-norm hinge loss `(z, θ) = (max (0, 1− y〈θ, z〉))q for classification and the q-th power absolute distance loss `(z, θ) = |y − 〈θ, z〉|q for regression (Lei & Ying, 2020a), whose ` are (q − 1)-Hölder smooth if q ∈ (1, 2] (Li & Liu, 2021). Lemma 1 shows that Hölder smoothness shares similar property with smoothness defined in Assumption 2, details of the proof can be found in Appendix A.1.

heading: 4 SHARPER UTILITY BOUNDS FOR DIFFERENTIALLY PRIVATE MODELS

heading: 4.1 PRIVACY GUARANTEES
text: Before analyzing the excess population risk bound, we first discuss the privacy guarantees in this section. Abadi et al. (2016) proposed the moments accountant method to measure the privacy costs of DP model training by stochastic gradient descent (SGD), Wang et al. (2017) further analyzed it under the setting of gradient descent (GD). In this paper, we focus more on the utility analysis, to improve the excess population risk, so we directly apply it to the gradient perturbation method. Lemma 2 (Wang et al. (2017)). In gradient perturbation method in (1), for , δ > 0, it is ( , δ)-DP if the random noise b is zero mean Gaussian noise, i.e. b ∼ N (0, σ2Ip), and for some constant c,
σ2 = c G2T log(1/δ)
n2 2 . (3)
Remark 1. (3) assumes the loss function to beG-Lipschitz. If we only assume that `(·, ·) is α-Hölder smooth with parameter H , then G can be replaced by max{2HMC , H} as discussed above.

heading: 4.2 ANALYSIS OF THE EXCESS POPULATION RISK
text: To remove the O(1/ √ n) term in previous results, we further need the Generalized Bernstein condition when analyzing the excess population risk. Assumption 4 (Generalized Bernstein condition (Koltchinskii, 2006)). We say the loss function ` satisfies the generalized Bernstein condition if for some B > 0 for any θ ∈ C, we have:
E [ (`(z, θ)− `(z, θ∗))2 ] ≤ B (R(θ)−R(θ∗)) .
Assumption 4 is a general condition, if the loss function `(·, ·) is G-Lipschitz and bounded by M`, then many loss functions satisfy the generalized Bernstein condition, such as exponential loss function, logistic loss function, quadratic loss function, truncated quadratic loss, and hinge loss (Bartlett et al., 2006; Steinwart & Christmann, 2008).
Most of the previous works assumed that the loss function is convex (or strongly convex) when analyzing the optimization error (the excess empirical risk) Rn(θ̂n)−Rn(θ∗n). In this paper, we use the Polyak-Łojasiewicz (PL) condition to replace the convexity assumption.
Assumption 5 (Polyak-Łojasiewicz condition). The empirical risk Rn(θ) satisfies the PolyakŁojasiewicz (PL) condition if there exists µ > 0 and for every θ,
‖∇θRn(θ)‖22 ≥ 2µ (Rn(θ)−Rn(θ ∗ n)) .
The Polyak-Łojasiewicz condition is one of the weakest curvature conditions, so all the results given in this paper can be expanded to strongly convex conditions. (Karimi et al., 2016; Li & Liu, 2021), weaker than ‘one-point convexity’ (Kleinberg et al., 2018), ‘star convexity’ (Zhou et al., 2019), and ‘quasar convexity’ (Hinder et al., 2020). It is widely used in the analysis of non-convex learning (Wang et al., 2017; Charles & Papailiopoulos, 2018; Lei & Ying, 2020b; Lei & Tang, 2021) and many popular non-convex objective functions satisfy the PL condition, such as: matrix factorization (Liu et al., 2016), robust regression (Liu et al., 2016), neural networks with one hidden layer (Li & Yuan, 2017), mixture of two Gaussians (Balakrishnan et al., 2017), ResNets with linear activations (Hardt & Ma, 2017), linear dynamical systems (Hardt et al., 2018), phase retrieval (Sun et al., 2018), and blind deconvolution (Li et al., 2019).
Remark 2. With G-Lipschitz and λ-strongly convex, we have E [( `(z, θ) − `(z, θ∗) )2] ≤ G2‖θ − θ∗‖22, andR(θ)−R(θ∗) ≥ λ2 ‖θ−θ ∗‖22, which implies E [( `(z, θ)−`(z, θ∗)
)2] ≤ (2G2/λ)(R(θ)− R(θ∗) ) , Assumption 4 is naturally satisfied. And PL condition can be directly derived from strongly convex (Karimi et al., 2016), so all strongly convex loss functions satisfy Assumptions 4 and 5 simultaneously and all the results given in this paper can be directly extended to strongly convex condition. Expect for strongly convex functions, several interesting machine learning setups also satisfy Assumptions 4 and 5. (1) 1-layer neural networks with a squared error loss and leaky ReLU activations. Charles & Papailiopoulos (2018) shows that 1-layer neural networks with a squared error loss and leaky ReLU activations satisfy Assumption 5, and Bartlett et al. (2006) shows that quadratic functions satisfy Assumption 4, so (1) holds. (2) Loss functions of least squares minimizations. Charles & Papailiopoulos (2018) shows that least squares minimization satisfy Assumption 5 and Bartlett et al. (2006) shows that the quadratic functions satisfy Assumption 4, so (2) holds. (3) Squared piecewise-linear functions with regularized term. Bartlett et al. (2006) shows that the composition of strongly convex functions with piecewise-linear functions satisfy Assumption 5, and Bartlett et al. (2006) shows that squared piecewise-linear functions satisfy Assumption 4. We prove that if a function satisfies Assumption 4, then with regularized term λ‖θ‖22, it also satisties Assumption 4 (details can be found in Appendix A.5). Thus, (3) holds.
Theorem 1. If Assumptions 1, 2, 4 and 5 hold, the loss function is bounded, i.e. 0 ≤ `(·, ·) ≤ M`, taking σ given by Lemma 2, T = O (log(n)), η1 = · · · = ηT = 1L , if ζ ∈ (exp(−p/8), 1), then with probability at least 1− ζ:
R(θ̂n)−R(θ∗) ≤ c1 G2p log(n) log(1/δ)
n2 2
( 1 + ( 8 log(T/ζ)
p
)1/4)2
+ c2
( G2 log2(n)
n + B +M` n ) + c3 G2 log2.5(n) √ p log(1/δ)
n
( 1 + ( 8 log(1/ζ)
p
)1/4) .
for some constants c1, c2, c3 > 0.
Detailed proof can be found in Appendix A.2, we give a proof sketch here. First, we discuss the stability of the gradient perturbation based DP algorithm and show that it is O (Tη/n) uniformly stable w.r.t n with high probability. Then, we analyze the generalization error via stability theory. Meanwhile, via Assumption 4 and its moments bound, we couple term R(θ̂n)−Rn(θ̂n) (the generalization error of θ̂) and term Rn(θ∗)− R(θ∗) in (2) together, to remove the O (1/ √ n) term in the generalization error. In this way, a better excess population risk bound is achieved by combining the optimization error together.
The proof is motivated by Klochkov & Zhivotovskiy (2021) in the non-private case. The key challenges include that in the setting of DP, the random noise is injected into the algorithm. In Klochkov & Zhivotovskiy (2021), a key step to analyze the generalization error is summing
Xi = E′ [`(zi, θ′n)− `(zi, θ∗)] for i = 1, · · · , n, where θ′n is derived from an independent copy of the original dataset and E′ means the expectation taken over the independent copy. When summing, Xi is required to be zero mean. However, in the cases of DP, if we replace θ′n by θ̂ ′ n, then Xi are not zero mean. Besides, for output perturbation, a common way to decompose the excess population risk isR(θ̂n)−R(θ∗) ≤ R(θ̂n)−R(θn)+R(θn)−Rn(θn)+Rn(θn)−Rn(θ∗n)+Rn(θ∗)−R(θ∗), which naturally solves the problem mentioned above (because the generalization error is discussed over the non-private model). However, when it comes to the gradient perturbation method, we cannot solve the problem easily in this way, because the random noise is coupled with the gradient. So, we decouple the noise terms and overcome the challenge by the moment Bernstein inequality.
By Theorem 1, it is easy to follow that with high probability, R(θ̂n) − R(θ∗) = O (√p n ) , which is the firstO (1/n) high probability excess population risk bound over DP algorithm w.r.t n, to the best of our knowledge. Theorem 2. If Assumptions 3, 4, 5 hold, the loss function and the parameter space are bounded, i.e. 0 ≤ `(·, ·) ≤M`, ‖C‖2 ≤MC . Taking σ given by Lemma 2, T = O ( n 2 1+2α ) , and ηt = 2µ(t+κ) , where κ ≥ 2H 1/α
µ , if ζ ∈ (exp(−p/8), 1), then with probability at least 1− ζ: R(θ̂n)−R(θ∗) ≤ c1 G′2 √ p log(1/δ)
n 2α 1+2α
( 1 + ( 8 log(T/ζ)
p
)1/4)
+ c2
( G′2 log2(n)
n + B +M` n ) + c3 G′2 log2(n) √ p log(1/δ)
n 2α 1+2α
( 1 + ( 8 log(1/ζ)
p
)1/4) .
for some constants c1, c2, c3 > 0, where G′ = max{2HMC , H}.
Detailed proof can be found in Appendix A.3. The proof is similar to Theorem 1, the challenge is that the properties G-Lipschitz and L-smooth are replaced by the assumption α-Hölder smooth when analyzing the optimization error (the excess empirical risk). To overcome the challenge, we use Lemma 1 to bound the optimization error and Young’s inequality is used to normalize the exponential rate, details are shown in the Appendix.
By Theorem 2, it is easy to follow that with high probability, R(θ̂n)−R(θ∗) = O (√ p n −2α 1+2α ) .
By the definition of α-Hölder smooth, α ∈ (0, 1], so if α ∈ [ 12 , 1], R(θ̂n)−R(θ∗) = O ( n −2α 1+2α ) ≤ O ( n− 1 2 ) w.r.t n, which implies that our result is better than previous results when α ∈ [ 12 , 1]. Via the discussion mentioned above, we observe that under the assumption α-Hölder smooth, our result is better than O(1/ √ n) w.r.t n only in the case that α ∈ [ 12 , 1]. Besides, the best result is
O ( n−2/3 ) , which comes when α = 1. And it cannot achieve the convergence rate O( √ p
n ). The reason is that when applying Young’s inequality in the optimization error analysis, an additional term Hη
α+1 t (1−α) 2(α+1) appears, leading a loose excess population risk bound.
Motivated by this, we design a variant of gradient perturbation method given in (1), called max{1,g}-Normalized Gradient Perturbation DP algorithm, to overcome the loose excess population risk bound. Details are shown in Algorithm 1. Remark 3. The difference between Algorithm 1 and (1) is that in lines 4 and 5, we normalize the `2- norm of the gradient to 1 if it is less than 1. In this way, we can ‘bypass’ the Young’s inequality when scaling ‖θt − θ∗n‖1+α2 (derived from Lemma 1), further remove term Hηα+1t (1−α) 2(α+1) in the theoretical analysis. Details can be found in Appendix A.4.
Algorithm 1 max{1,g}-Normalized Gradient Perturbation Require: dataset D, learning rate at iteration t: ηt, the variance of the Gaussian noise injected to
the gradient: σ. 1: function M-NGP(D, ηt, σ) 2: Initialize θ0. 3: for t = 0 to T − 1 do 4: if ∥∥∥∇θRn(θ̂t)∥∥∥ 2 < 1 then
5: ∇θRn(θ̂t)← ∇θRn(θ̂t)/ ∥∥∥∇θRn(θ̂t)∥∥∥
2 .
6: endif 7: θ̂t+1 ← θ̂t − ηt ( ∇θRn(θ̂t) + b ) , where b ∼ N ( 0, σ2Ip ) .
8: endfor 9: return θ̂n = θ̂T .
10: end function
Then, via Algorithm 1, we can improve the excess population risk bound as shown below.
Theorem 3. If Assumptions 3, 4, 5 hold, the loss function and the parameter space are bounded, i.e. 0 ≤ `(·, ·) ≤ M`, ‖C‖2 ≤ MC . Taking σ given by Lemma 2, T = O (log(n)), and η1 = · · · =
ηT = η, where ( 2 H − 2−1/α µH(α−1)/α )1/α < η < ( 2 H )1/α , if ζ ∈ (exp(−p/8), 1), then with probability at least 1− ζ,
R(θ̂n)−R(θ∗) ≤ c1 G′ √ p log(n) log(1/δ)
n
( 1 + ( 8 log(T/ζ)
p
)1/4)
+ c2
( G′2 log2(n)
n + B +M` n ) + c3 G′2 log2.5(n) √ p log(1/δ)
n
( 1 + ( 8 log(1/ζ)
p
)1/4) ,
for some constants c1, c2, c3 > 0, where G′ = max{2HMC , H}.
Detailed proof can be found in Appendix A.4. The proof is similar to Theorems 1 and 2, the key difference is that by gradient normalization in Algorithm 1, Young’s inequality is abandoned in the theoretical analysis (as discussed in Remark 3), which implies a better excess population risk bound.
By Theorem 3, it is easy to follow that with high probability, R(θ̂n)−R(θ∗) = O (√p n ) . The bound is of the same order as the result given in Theorem 1.This is also the first O (1/n) high probability excess population risk bound over DP algorithm w.r.t n without smoothness assumption.

heading: 5 EXPERIMENTS
text: In this section, we perform experiments on real datasets to evaluate the difference between our proposed m-NGP algorithm and the traditional gradient perturbation (TGP), like (1).
The experiments are performed on classification task over datasets Iris (Dua & Graff, 2017), Breast Cancer (Mangasarian & Wolberg, 1990), Credit Card Fraud (Bontempi & Worldline, 2018), Bank (Moro et al., 2014), and Adult (Dua & Graff, 2017), the number of total data instances are 150, 699, 984, 41188, and 45222, respectively. We split the training and testing sets randomly and evaluate the accuracy on the testing set and the convengence rate on the training set. In all the experiments, the privacy budget δ is set 1n and we choose = 0.1 to 1.0.
We apply the regularized logistic regression method to the classification task, the loss function satisfies the assumptions mentioned before, and the experimental results are shown in Figure 1. We show the experimental results over datasets Iris and Adult in this section and experiments on other datasets are shown in Appendices B.1 and B.2. For convergence rate, the shadow area represents the
maximum and minimum loss over mutiple experiments, reflecting the variance. The shadow area in part (d) of Figure 1 is not obvious, the reason is that the variances are small. Over most datasets, the accuracy and the convergence rate of max{1,g}-Normalized Gradient Perturbation method is better than traditional gradient perturbation method. Besides, the accuracy of the DP model increases with the increasing of the privacy budget , which is in line with the theoretical analysis.

heading: 6 CONCLUSIONS
text: In this paper, we first propose a state-of-the-artO (√p n ) high probability excess population risk bound for gradient perturbation based DP algorithms, under the assumptions of G-Lipschitz, L-smooth, Polyak-Łojasiewicz condition, and generalized Bernstein condition. The result positively answers the open problem: Can we achieve high probability excess risk bound with rate O(1/n) w.r.t n for DP models via uniform stability? Then, we extend the result to a more general case, requiring αHölder smoothness, Polyak-Łojasiewicz condition, and generalized Bernstein condition. However, the result is not as satisfactory as before, we achieve an O ( n −2α 1+2α ) high probability utility bound,
which is better than previous results when α ∈ [ 12 , 1] and cannot achieve anO (1/n) bound. To get a better result, we further propose a new algorithm: max{1, g}-Normalized Gradient Perturbation (mNGP). Detailed theoretical analysis shows that m-NGP can achieve O (√p n ) high probability excess population risk bound, under the assumptions of α-Hölder smoothness, Polyak-Łojasiewicz condition, and generalized Bernstein condition, which is the first O (1/n) high probability bound w.r.t n under non-smoothness cases. Experimental results show that the accuracy of m-NGP algorithm is better than traditional gradient perturbation method. Thus, our proposed max{1, g}-Normalized Gradient Perturbation method improves the excess population risk bound and the accuracy of the DP model over real datasets, simultaneously.

Review summaries:
This paper analyzes the utility bounds of the gradient-perturbation based DP algorithm. They first provide DP by previous result (it is not the key point in this paper). Then, by applying the Generalized Bernstein condition, they give $O(p^{0.5}/(n\epsilon))$ high probability excess population risk bound under the properties Lipschitzness, smoothness, and PL condition. Furthermore, under the more general assumption (Holder smoothness), they analyze the utility bound but the result is not so good as before. So they propose an algorithm (called m-NGP) to improve it under the assumption Holder smooth, and it is claimed that the utility bound can be improved to $O(p^{0.5}/(n\epsilon))$. Their results are sharper than previous analyses in different settings: previous results require convex assumption but this paper requires PL condition. Moreover, experiments are performed to evaluate the accuracy of m-NGP.

The paper achieves high probability excess risk bound with rate O(1/n) w.r.t n for DP models via uniform stability by using Generalized Bernstein condition under G-Lipschitz, L-smooth, and PL condition. Then the authors expand the result to a more general case, only requiring α-Ho ̈lder smoothness, Polyak-Łojasiewicz condition, and generalized Bernstein condition. But the result is worse than before, so in order to get a better result, they propose m-NGP algorithm to achieve O(1/n) high probability bound w.r.t n under α-Ho ̈lder smoothness, Polyak-Łojasiewicz condition, and generalized Bernstein condition. The authors also show the experimental better accuracy results of m-NGP compared to traditional gradient perturbation method on real datasets.