Sharper Utility Bounds for Differentially Private Models
Authors: Yilin Kang
Yong Liu
Jian Li
Weiping Wang
Venue: ICLR 2022 Submitted (2022)

Abstract: 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{2\alpha}{1+2\alpha}}\big)$ w.r.t $n$, which cannot achieve $\mathcal{O}\left(1/n\right)$ when $\alpha\in(0,1]$. %and only better than previous results when $\alpha\in[1/2,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 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.

Under review as a conference paper at ICLR 2022
SHARPER UTILITY BOUNDS FOR DIFFERENTIALLY PRIVATE MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, by introducing Generalized Bernstein condition, we propose the first (()²) ne high probability excess population risk bound for differentially private al- gorithms under the assumptions G-Lipschitz, I-smooth, and condition, based on gradient perturbation method. If we replace the properties G-Lipschitz and L-smooth by a-Hölder smoothness (which can be used non- 2a
142a w.r. which smooth setting), the high probability bound comes to On cannot achieve O (1/n) when a E (0, 1]. To solve this problem, we propose a variant of gradient perturbation method, max 9) -Normalized Gradient Per- turbation (m-NGP). We further show that by normalization, the high probability excess population risk bound under assumptions a-Hölder smooth and Polyak-
Lojasiewicz condition can achieve O (PP) which is the first O (1/n) high proba- bility utilltyy bound w.r. 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.
ne
INTRODUCTION
Machine learning has been widely used and found effective in many fields in recent years (Singha jet al., 202T)] Swapna & Soman [002]] Ponnusamy al. 202T). When training machine learning models, tremendous data was collected, and the data often contains sensitive information of individ-
uals, which may leakage personal privacy (Shokri et al. 2017 Carlini et al. 2019).
Differential Privacy (DP) (Dwork al. 2006 Dwork & Lei 2009 Dwork al. 2014) is theo-
retically rigorous tool to prevent sensitive information. It introduces random noise to the machine leamning model and blocks advessaries from inferring any single individual included in the dataset by observing the model. The mathematical definition of DP is well accepted and relative technologies performed by Google (Erlingsson al.] 2014), Apple (McMillan) (016)) and Microsoft (Ding) cet al., (017). As such, DP has attracted attention from the researchers and has been applied to nu-
merous machine learning problems (Ullman & Sealfon 2019 Xu et 2019 Bernstein & Sheldon
2019 Wang & Xu 2019 Heikkilä 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 (Chaud- huri et al. 201T), objective perturbation (Chaudhuri al. (01I), and gradient perturbation (Song et al. 2013). Considering that gradient descent is widely used optimization method, the gradient perturbation method can used for wide range of applications, and adding random noise to the gradient allows the model to escape local minima (Raginsky al. 2017). we focus the gradient perturbation method to guarantee DP in this paper.
In this paper, 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 gen- eralization 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 gener- alization error. On one hand, Chaudhuri al. (2011) applied the complexity theory and achieved

---

Under review as a conference paper at ICLR 2022
an O( m Vn
2/2 2// high probability excess population risk bound under the assumption of
strongly convex; Kifer et al. (2012) achieved O y/2
ne 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 Bass-
ily et al.
2019 Feldman et al. 2020: Bassily et al. 2020 Wang et al. 2021 are O (Y> VT or
O(
containing an inevitable O
term, which is a bottleneck on the utility analysis. Thus,
vnee/
Vn
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 JP 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( vP) troducing Generalized Bernstein condition (Koltchinskii, 2006), we remove the O
.i rate of convergence in the setting of DP. By in-
1 VA term in
the generalization eгror and furthermore improve the high probability excess population risk bound. Comparing with previous high probability bounds, the improvement is approximately up (vn).
CONTRIBUTIONS
We first prove that by introducing Generalized Bernstein condition (Koltchinski, 2006), under the assumptions G-Lipschitz, L-smooth, and Polyak-Lojasievizz (PL) condition, the high probability excess population risk bound can be improved O vP) To the best of our knowledge, this the ne
first O yP) high probability excess population risk bound in the field of DP.
Then, we relax the assumptions G-Lipschitz and L-smooth, by introducing a-Hölder smooth. Un- der these assumptions, we prove that the high probability excess population risk bound comes to Considering that a E (0, 1). the result cannot achieve O w/²).
( n 1426
To overcome the bottleneck, we design 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 a a-Hölder smooth, PL condition, and generalized Bernstein condi- tion, the high probability excess population risk bound can be improved to O / To the best of our knowledge, this is the first O vP high probability excess population risk bound for non-smooth loss in the field of DP.
Moreover, to evaluate the performance of our proposed max ( Norrmalzee Gradient Perturba- tion 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 pre- liminaries 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,9)- Normalized Gradient Perturbation. The experimental results are shown in Section 5. Finally, we conclude the paper in Section 6.
2 RELATED WORK
Dwork et al. (006)) proposed the mathematical definition of DP for the first time. Then, 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); 4) Abadi et al. (2016); Wang et al. (2017) Zhang et al. (2017): Wu et al. (2017); Bassily et al. (2019); Feldman et al. 20200 Bassily ly et al. (2020) further improved the results under different assumptions.
2

---

Under review as a conference paper at ICLR 2022
Table 1: Previous excess population risk bounds and ours under different assumptions
Assumptions
Method
Utility Bound
Bassily et al.
(2019)
Lipschitz, smooth, convex
Gradient
O
yP
+
vn
Feldman et al.
2020
Lipschitz, convex
Gradient
o
yv mc
Vn.
Bassily et al.
2000
Lipschitz, convex
Gradient
o
+
vn
Wang et al.
2021
a-Hölder smooth, convex
Gradient
o
vF Te
vn
Wang et al.
2021
G-Hölder smooth, convex
Output
vnc
Ours
Lipschitz, smooth, PL condition
Gradient
0
v/p
mc
Ours
a-Hölder smooth, PL condition
Gradient
vP
1+
Ours (m-NGP)
a-Hölder smooth, PL condition
Gradient
y/
In Table is the size of the dataset, is the privacy budget, and is the dimension of the data.
Among the works mentioned above, some of them only analyzed the privacy guarantees (Song et al. Abadi et al.) 2016), some of them only discussed the excess empirical risk bound (Wang al, 2017 Zhang et al., 2017 Wu et al. 2017). Some works discussed the excess population risk un- der expectation, from different points of view, such as complexity theory, optimization theory, and stability theory: Kifer et al. (012)) achieved an O (P))) expected excess population risk bound via complexity theory; Bassily et al. (2014) achieved similar expected bound under convexity assump- tion, via optimization theory; and Wang et al. (2019) proposed O (oog(ne=)) expected excess pop-
2013
ulation risk bound under non-convex condition, Langevin Dynamics (Gelfand & Mitter 1991) and the stability of Gibbs algorithm.
Considering that the high probability bound is more concerned by researchers, focus 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 an O { term, details can
vnn
be found in Table [ 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 (Koltchinskij 2006), we remove the term from the generalization error, and further improve the excess population risk bound of
DP models. The improved convergence rate is up to O 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
Table first shows that by adding more assumptions (we assume the loss function be Lipsehitz, smooth, and satisfy Polyak- Dolyak-Lojasiewicz (PL) condition, while previous results require a-Hölder smoothness and convexity), we achieve a better high probability excess population risk bound, p which is state-of-the-art to the best of our knowledge. Then, we replace the Lipschitz high probability excess pop- [ 1], our result is better than previous ones, but it cannot achieve
and smooth property by a-Hölder smoothness and achieve O
ulation risk bound, when
3

---

Under review as a conference paper at ICLR 2022
the same bound (O (1/n) w.r. 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 result under the same assumptions: a-Hölder smooth and PL condition.
O( LP)
Moreover, although 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.
PRELIMINARIES
In this paper, we assume that there are n data instances in dataset D.i.e D {z1.... , 2n} where (xr, v) with input E X and label y E V, and Z = X' x y. The data space is denoted by D and the parameter space denoted by C, the loss function is defined as ((::-): x RR Databases D. D' E D differing by one data instance are denoted as D D', called adjacent databases. For
given vector
[21, xall" its fy-norm is ||0|||
|2;13) And A B represents
that there exists c > 0, A S cB.
Definition (Differential Privacy (Dwork et 2006)), ). randomized algorithmm: A D + R2 is (e, d)-differential privacy (DP) if all D ~ D' and events S E range(AA):
P[A(D) S] s ('((''')) + 8.
Definition I immlies that the adversaries cannot infer whether an individual participates when train- ing 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 al. 2016: Jayaraman & Evans, 2019 Carlini et al. 2019).
Throughout this paper, we focus gradient perturbation method to guarantee (c,d)-DP, the paradigm is based on gradient descent: at iteration 6,
è. 8 - (0)))
(1)
where T) is the learning rate, is the random noise injected into the gradient, 0 is corresponding model with privacy, and R, (0) is the empirical risk, defined as (0) = Σ {(z,, 0).
In this paper, we focus on minimizing the population risk: R(0) = Eg-D [C(2, 0)] In the setting of DP, the excess population risk is defined by R((0) minsec R(0), which can be decomposed into:
R((m) R((0)= R((,)) Rn (0,) + Rr, (0.) R2 (0 (0 R(00)
s R(,,.) - Rr, (0.) ) + Rr (0.)) Rr (0%) R., (0*) R((0),
(2)
GE
OE
where 0" arg mingee R(0), 0 arg minlaee Rr (0), and the last inequality is becasuse of the definition of 6;, In 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 a popular tool, which uniform stability yields exponential generalization bounds and is commonly used.
Definition 2 (Uniform Stability (Bousquet & Elisseeff (002)). An algorithm On is r-uniformly stable if for any 2, Z1, 26, Fn, 2, Z and 1,'." n, it holds that
10(z, (z) ,2,) 022 (21, ... Zi-11 2 Zi41, zx))) 5
In this paper, we use notation 6, for both algorithm and model parameter. By Definition 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 (G-Lipschitz). The loss function e E D and 0, 02 C. have: (0(2,0)) ((z)2))
D x C - R is G-Lipschitz over 8 if for any
< G 02112.
4

---

Under review as a conference paper at ICLR 2022
Assumption 2 (L-smooth). The loss function P: C - R is L-smooth over if for any D and 01, 82 E C. we have: VVll(z, 01) - Vol(z, 02)1l _ L| - 82112-
l is differentiable, smoothness yields: f(2, - - (Vof(z, 02), 01 02) + |0 0211-0211 2
Assumptions G-Lipschitz and L-smooth 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
al. Bassily et al. 2020). To relax the Lipschitz and smoothness assumptions, we introduce
the a- Hölded smoothness of the loss function:
C - R is o-Hölder smooth over O with parameter H if for any E DD and 01, 0,.02 E C, we have: [Voo(zz 01) Vol(z, 02)1l2 S H - -0211-
Assumption (a-Hölder smooth). Let a (0, 1]. The loss function E
Lemma 1. the loss function -(---) is differentiable, then Assumption Aanittiiionnnlll Byields -(2,)))((z,02)) s (Vol(z, 02), 01 02)
H |00 02112=1
By the definition, it is easy to follow that a = 1, it is equivalent to H-smooth; and if a - O. satisfies the Lipschitz property given in Assumption [ Besides, with bounded parameter space, ie. ||e|l2 < Mc. a-Hölder smoothness immediately implies max(2F) Mc. H H]JLipschitz. More- over, Assumption 3 instantiates many non-smooth loss functions. For example, the q-norm hinge loss {(2 0) = [max (0,1- 1-01-100,0 2))) for classification and the q-th power absolute distance loss f(2, 8) V (0 2) for regression (Lei & Ying 2020a), whose & are (q - 1)-Hölder smooth E (1, (Li Liu 2021). Lemma shows that Hölder smoothness shares similar property with details of the proof can found in Appendix A.I.
smoothness defined in Assumption 2
SHARPER UTILITY BOUNDS FOR DIFFERENTIALLY PRIVATE MODELS
4.1 PRIVACY GUARANTEES
Before analyzing the excess population risk bound, we first discuss the privacy guarantees in this section. Abadi al. (2016) proposed the moments accountant method to measure the privacy costs of DP model training by stochastic gradient descent (SGD), Wang et al. (2177) 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 (Wang et al. (017)). In gradient perturbation method in (7). for e, O, it is (e, 8J-DP the random noise b is zero mean Gaussian noise, i.e. b ~ (O, o² Ip), and for some constant c.
0² 0= G2 Goglog(1/8)
n²22
Remark 1. 3 assumes the loss function be G-Lipschitz. we only assume that ((..-) -) is Hööder smooth with parameter H, then G can be replaced by max (2H H) as discussed above.
4.2 ANALYSIS OF THE EXCESS POPULATION RISK
To remove the O11 /n) term in previous results, we further need the Generalized Bernstein condi- tion when amalyzing the excess population risk. Assumption 4 (Generalized Bernstein condition (Koltchinskii 2006 We say the loss function E satisfies the generalized Bernstein condition for some B > 0 for any 0 C, we have:
E (((2,)) {(2,0))) < B (R(0) R())))
Assumption 4 a general condition, the loss function ((.-)) G-Lipschitz and bounded by Mj. 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) R, (f,) R,, (f;). this paper, we use the Lojsse--.. (PI.) condition replace the convexity assumption.
5

---

Under review as a conference paper at ICLR 2022
Assumption 5 (Polyak-Lojasiewii) condition). The empirical risk (0) satisfies the Polyak- Lojasiewica (PL) condition if there exists μ > 0 and for every 8,
(0)112 2 2p (R,, (0) - (07))
The Delyak-Lojjsiewiies 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' KKleinberg 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 & Papailiopoulls) 2018: Lei & Ying 2020b Lei & Tang 2021 and
many popular non-convex objective functions satisty the 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 ct al. 2018).
and blind deconvolution (Li et al. 2019).
Remark 2. With G- G-Lipschitz and X-strongly convex, we have -) 0)) S SG
0) S
0" l2. and R(O))), )) Assumption 4 is naturally satisfied. And Pl. condition can be directly derived from strongly convex (Krrimi et at. 2016). so all strongly convex loss functions satisfy Assumptions f and 5 si- multaneously 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 [nd (1) 1-layer neural networks with squared error loss and leaky ReLU activations. Charles & Papailiopoulos (2018) shows that 1-layer neural networks with 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 leust squares minimiza- tions. Charles Papailiopoulas (2018) shows that least squares minimization satisfy Assumption 5 and Bartlett et al. (2006) shows that the quadratic functions satisfy Assumption 4, (2) holds. (3) Squared piecewise-linedd 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- -ineer functions satisfy Assumption 4. We prove that if a function satisfies Assumption 4, then with regularized term 2110122. it also satisties Assump- tion+ 4 (details can be found in Appendix A.5). Thus, (3) holds.
Z 2110-0 which implies ([(((=,))-(((,00)))
Theorem 1. If Assumptiinss 1
2 and hold, the loss function is bounded, i.e. 0 E(.,,) S Mr. T (log(n) (1)) 7/1 =...-=
taking a given by Lemma 2
........ Ty I. 2.ifC= (cxp(-p/8), 1), then with
probability at least 1-C:
G G2plog(n) log(1/8)
(l0g(T(()) 1/21
R(O.) -R(00) S
1+
n2e2
p
G2 log 2 (n)
+ Me
+ C2
n
G2 2.5 (n) holyplogii plg((1/0)
(8log(1/() 1/4)
)mm)
+ C3
1+
ne
p
for some constants C12 C2, C3 > 0.
Detailed proof can be found in Appendix A.2, give proof sketch here. First, we discuss the stability of the gradient perturbation based DP algorithm and show that it is O (Tn/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(O,)) (f,). (the gener- alization error of 0) and term R, (0*) R((0)) in ( together, to remove the O (1/ /T) term in the generalization error. In this way, better excess population risk bound is achieved by combining the optimization error together.
The proof is motivated by Klochkov & Zhivotovskiy (222)) 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 (202T), key step to analyze the generalization emror is summing

---

Under review as a conference paper at ICLR 2022
X; 1E=EE'(eee =E'(((,, E(2,, 8] for 1,.... n. where 8,, is derived from independent copy of the original dataset and E'' means the expectation taken over the independent copy. When summing, X; is required to be zero mean. However, in the cases of DP, if we replace 6' by 6/. then X; are not zero mean. Besides, for output perturbation, a common way decompose the excess population risk is R(O,) -(xx)-R(0)) R(0*) R(O,)= R((,) + R(,,) R., (0.)) + R, (0,.) R., (f%) 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 can- not 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.
R.,
By Theorem it is easy to follow that with high probability. R(O,) - R(0*) O vP the first O (1/n) high probability excess population risk bound over DP algorithm w.r.t n, to the best of our knowledge.
( which is ne
Theorem 2. If Assumptions 3 4 5 hold, the loss function and the parameter space are bounded,
Lee. 0 S ((.-) & Mr. ||C||2 - Mc. Taking a given by Lemma 2 T O
n (ni ) and nue = p((+x)
where K 2 2H'/" if( E pppp(-p8)).r 1). then with probability at least 5:
G (PVlog((18))
(1 (
(Slog(T/C) 1/4
R(O.) - R(0") $ 0
n 1itzue
(n) G² log" (n)
B + Me
+ 02
+
T
n
2² log" (n) V plog(1/0)
8 (log(1/() 1/4
+ C3
1+
111420
p
for some constants C12 C22 C3 > 0, where G' max m M2H H..
Detailed proof can be found in Appendix A.3. The proof is similar to Theorem T the challenge that the properties G-Lipschitz and L-smooth are replaced by the assumption a- Hö-Hör smooth when analyzing the optimization eπror (the excess empirical risk). To overcome the challenge, use Lemma to bound the optimization error and Young's inequality is used to normalize the expo- nential rate, details are shown in the Appendix.
By Theorem 2. it is easy to follow that with high probability,
VP
R(O..) R(0") O
n
By the definition of a-Hölder smooth, E (0, 11, so if a E [1. 1}. R(θ..) - R(0")= O
20 T
I 0 n
w.r.t n, which implies that our result is better than previous results when a E [t. 1].
Via the discussion mentioned above, we observe that under the assumption a-Hölder smooth, our result is better than O(1//n) w.r.t n only the case that a E 1]. 1]. Besides, the best result is O (n 2/3), which comes when a = 1. And it cannot achieve the convergence rate O vP The reason is that when applying Young's inequality in the optimization error analysis, an additional term Hng+ (1-a) appears, leading a loose excess population risk bound.
2(a+1)
Motivated by this, we design variant of gradient perturbation method given in (. called max -Noommalize Gradient Perturbation DP algorithm, to overcome the loose excess pop- ulation risk bound. Details shown in Algorithm
Remark 3. The difference between Algorithm And (7) is that in lines 4 and 5, we normalize the Eg- norm of the gradient if it is less than 1. In this way, we can 'bypass' the Young's inequality when scaling 110, 0,,12+a (derived from Lemma J, further remove term H (1 in the theoretical analysis. Detaily can be found in Appendix A.4.
2
7

---

Under review as a conference paper at ICLR 2022
Algorithm m -Normalzze Gradient Perturbation
Require: dataset D, learning rate at iteration t: TJ, the variance of the Gaussian noise injected to the gradient:
1:
function M 0))
2:
Initialize 0o.
3:
for /
0 to T - do
4:
if
V VoRn (0x) 1 then
Veli (e)n((0))/ (o
5:
6:
endif
8.+1 t 0: nt (v. b). where b ~~ N (0)
7:
8:
endfor
return fn 0r.
9:
10:
end function
Then, via Algorithm
1 can improve the excess population risk bound shown below.
Theorem 3. If Assumptions 3
S
hold, the loss function and the parameter space bounded,
Le. O S ((:,)) S Me. ||C||2 S
Me. Taking a given by Lemma 2 T = O (log(n)), and tn
fr B, where (
2-1/0
1/a
1/a ifC (exp(-p/8), 1), then with probability n < (#)
1770-177
at least -- 5.
G' G'vplog(()) log(1/0)
14 (1
8 8log(T/S) 2/4
)/))
R(O.)) - R(00) s ca-
p
G²2 log (n)
B + Mr
+ 02
n
n
2 log 2.5 (n) (n) plog(11/)
(1
(8log(1/S) 1/4
)
+ C3
1+
N1
p
for some constants C12 022 C3 > O, where [2H H}.
Detailed proof can be found Appendix A.4. The proof is similar to Theorems D and the key difference is that by gradient normalization in Algorithm|1 I Young's 's inequality is abandoned in the theoretical analysis (as discussed Remark 3), which implies a better excess population risk bound.
By Theorem 3 it is easy to follow that with high probability, R(O.) - R(O') = O /P The bound
of the same order as the result given in Theorem This is also the first O (1/n) high probability excess population risk bound over DP algorithm w.r.t without smoothness assumption.
EXPERIMENTS
In this section, we perform experiments on real datasets evaluate the difference between our proposed m-NGP algorithm and the traditional gradient perturbation (TGP), like
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 al. (0144) and Adult (Dua & Graff 2017), the number 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 8 is set and we choose = 0.1 to 1.0.
We apply the regularized logistic regression method to the classification task, the loss function sat- isfies the assumptions mentioned before, and the experimental results shown in Figure [ We show the experimental results over datasets Iris and Adult in this section and experiments on other datasets shown in Appendices B.I and B.2. For convergence rate, the shadow area represents the
8

---

Under review as a conference paper at ICLR 2022
0.715
Accursey
Accuracy
0.71
0.6
0.705
TGP
m-NGP
0.2
0.5
0.7
0.8
0.9
0.3
0.4
0.8 0.9
(a)
(b) Adult
1.2
TGP
0.85
TGP
1.1
m-NGP
m-NGP
1.0
0.80
0.9
Loss
0.75
0.8
0.7
0.70
0.6
0.65
10
20
30
40
50
60
70
80
90
100
50
60
70
80
90
100
Iterations
lterations
(c) Iris
(d) Adult
Figure 1: Comparisons between Traditional Gradient Perturbation (TGP) method and max (1. Normalized Gradient Perturbation (m-NGP) method.
maximum and minimum loss over mutiple experiments, reflecting the variance. The shadow area in part (d) of Figure iss not obvious, the reason is that the variances are small. Over most datasets, the accuracy and the convergence rate of max g) Normaazzze 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 c, which is in line with the theoretical analysis.
CONCLUSIONS
In this paper, we first propose a state-of-the siitte-ff-hheee oo-thh--atteteee O (PP) high probability excess population risk bound for gradient perturbation based DP algorithms, under the assumptions of G-Lipschitz, L-smooth, Solyyk--.-jasewwiie condition, and generalized Bernstein condition. The result positively answers for
the open problem: Can achieve high probability excess risk bound with rate O(1/n) DP models via uniform stability? Then, we extend the result to a more general case, requiring a- Hölder smoothness, Polyak- Sojyak--jjjsiwiizz condition, and generalized Bernstein condition. However,
high probability utility bound, which is better than previous results when [ 1] and cannot achieve an O (1/n) bound. To get better result, we further propose a new algorithm: max(1. ( -orrmalize Gradient Perturbation (m-
the result not as satisfactory as before, we achieve an O 1+26
-20
NGP). Detailed theoretical analysis shows that m-NGP can achieve O /P high probability excess population risk bound, under the assumptions of a-Hölder smoothness. Dolyak-Lojasiewicz condi- tion, 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 m-NGP algorithm better than traditional gradient perturbation method. Thus, our proposed max (1, g) Norrmllized Gradient Perturbation method improves the excess population risk bound and the accuracy of the DP model over real datasets, simultaneously.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318 2016.
Michael Backes, Pascal Berrang, Mathias Humbert, and Praveen Manoharan. Membership privacy in microrna-based studies. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 319-330, 2016.
Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu. Statistical guarantees for the em algo- rithm: From population to sample-based analysis. The Annals of Statistics, pp. 77 - 120, 2017.
Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Localized rademacher complexities. In Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, pp. 48, 2002.
Peter L Bartlett, Michael Jordan, and Jon D McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, pp. 138-156, 2006.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pp. 11279-112221 1288, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. In Advances in Neural Information Processing Systems, pp- 4381-4391, 2020.
Garrett Bernstein and Daniel R Sheldon. Differentially private bayesian linear regression. In Ad- vances Neural Information Processing Systems, pp. 523-533, 2019.
Gianluca Bontempi and Worldline. ULB the machine learning group, 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, pp. 499-526, 526, 2002.
Mark Bun, Marek Elias, and Janardhan Kulkarni. Differentially private correlation clustering. In Proceedings of the 38th International Conference on Machine Learning, pp. 1136-1146, 2021.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pp. 267-284, 2019.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Proceedings of the 35th International Conference on Muchine Learning. pp. 745-754, 2018.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, pp. 1069-1109, 2011.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems, pp. 3571-3580, 2017.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. 2017
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 371-380, 2009.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284, 2006.
10

---

Under review as a conference paper at ICLR 2022
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and R in Theoretical Computer Science, pp. 211-407,2000
Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-presevinng ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067, 2014.
Vitaly Feldman. Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
Saul B Gelfand and Sanjoy K Mitter. Recursive stochastic algorithms for global optimization in r'd.
SIAM Journal on Control and Optimization, pp. 999-1018, 1991.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In 5th International Conference on Learning Representations, 2017, 2017.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. In Proceedings The 33rd International Conference Machine Learning, pp- 1225-1234, 2016.
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, pp. 29:1-29:44, 2018.
Mikko Heikkilä, Joonas Jälkö, Onur Dikmen, and Antti Honkela. Differentially private markov chain monte carlo. In Advances in Neural Information Processing Systems 32, pp. 4115-4125. 2019.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Proceedings Thirty Third Conference on Learning Theory, pp. 1894- 1938, 2020.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In Proceedings of the 28th USENIX Conference on Security Symposium, pp. 1895-1912, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the aayaak--ojasiewicz condition. In Joint European Conference on Ma- chine Learning and Knowledge Discovery in Databases, pp. 795 811, 2016.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp. 25
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does SGD escape local minima? In Proceedings of the 35th International Conference on Machine Leurning, pp. 2698- 2018.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with conver- gence rate o(1/n). arXiv preprint arXiv:2103. /2024, 2021.
Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities risk minimization. 2006.
The Annals of Statistics, pp.
Tejas Kulkarni, Joonas Jälkö, Antti Koskela, Samuel Kaski, and Antti Honkela. Differentially pri- vate bayesian inference for generalized linear models. In Proceedings of the 38th International Conference on Machine Learning, pp. 1838-5849, 2021.
Yunwen Lei and Ke Tang. Learning rates for stochastic gradient descent with nonconvex objectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent, In Proceedings of the 37th International Conference on Machine Learning, pp- 5809-5819, 2020a.
11

---

Under review as a conference paper at ICLR 2022
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient-dominated objective functions. In International Conference on Learning Representations, 2020b.
Shaojie Li and Yong Liu. Improved learning rates for stochastic optimization: Two theoretical viewpoints, 2021.
Xiaodong Li, Shuyang Ling, Thomas Strohmer, and Ke Wei. Rapid, robust, and reliable blind deconvolution via nonconvex optimization. Applied and computational harmonic analysis, pp- 893-934, 2019.
Yuanzhi Li and Yang Yuan. Convergence analysis two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems 30, 20/7, pp. 597-607, 2017.
Huikang Liu, Weijie Wu, and Anthony Man-Cho So. Quadratic optimization with orthogonality
constraints: Explicit lojasiewicz exponent and linear convergence of line-search methods. In Proceedings of the 33nd International Conference on Machine Learning, 2016, pp. 1158-1167, 2016.
Olvi L Mangasarian and William H Wolberg. Cancer diagnosis via linear programming. Technical report, University of Wisconsin- Maddiso Department of Computer Sciences, 1990.
Robert McMillan. Apple tries to peek at user habits without violating privacy. The Wall Street
Journal, 2016.
Sérgio Moro, Paulo Cortez, and Paulo Rita. data-driven approach to predict the success of bank telemarketing. Decision Support Systems, pp. 22-31, 2014.
Dung Nguyen and Anil Vullikanti. Differentially private densest subgraph detection. In Proceedings of the 38th International Conference on Machine Learning, pp. 3140-8151. 2021.
Vijayakumar Ponnusamy, J. Christopher Clement, K. C. Sriharipriya, and Sowmya Natarajan. Smart Healthcare Technologies for Massive Internet of Medical Things, pp. 71-101. Springer Interna- tional Publishing, 2021.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. Proceedings of the 2017 Conference Learning Theeory, pp. 1674-1703, 2017.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference tacks against machine learning models. In 2017 IEEE Symposiun on Security and Privacy, 2017,
pp. 3-18, 2017.
Monoj Kumar Singha, Priyanka Dwivedi, Gaurav Sankhe, Aniket Patra, and Vineet Rojwal. Role of Sensors, Devices and Technology for Detection of COVID-19 Virus, pp. 293-312. Springer International Publishing, 2021.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pp. 245-24422255 2013.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008
Ju Sun, Qing Qu, and John Wright, A geometric analysis of phase retrieval. Foundations of Com- putational Mathematics, pp. 1131-1198, 2018.
G. Swapna and K. P. Soman. Diabetes Detection and Sensor-Based Continuous Glucose Monitoring
- A Deep Learning Approach, pp. 245-268. Springer International Publishing, 2021.
Jonathan Ullman and Adam Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. In Advances in Neural Information Processing Systems, pp. 3765-3775, 2019.
Di Wang and Jinhui Xu. Principal component analysis in the local differential privacy model. The- oretical Computer Science, 2019.
12

---

Under review as a conference paper at ICLR 2022
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, pp. 2722-2731, 2017.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In Proceedings of the 36th International Conference on Machine Learning. ICML 2019. pp. 6526-6533, 2019.
Puyu Wang, Yunwen Lei, Yiming Ying, and Hai Zhang. Differentially private sgd with non-smooth loss. arXiv preprint arXiv:2101.0892)) 2021.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-basee analytics. Proceedings of the 2017 ACM International Conference Management of Data, pp. 1307-1322, 2017.
Chugui Xu, Ju Ren, Deyu Zhang. Yaoxue Zhang, Zhan Qin, and Kui Ren. Ganobfuscator: Miti- gating information leakage under gan via differential privacy. IEEE Transactions on Information Forensics and Security, pp. 2358-2371, 2019.
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objec- tives. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 3922-3928, 2017.
Yi Zhou, Junjie Yang. Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. SGD converges to global minimum in deep learning via star-convex path. In 7th International Conference Learning Representations, 2019, 2019.
13


Reviews:
[{"review_id": "q2WfmiN1MfS", "reviewer": "Reviewer_9ZFZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThis paper is well-written and easy-to-follow. The presentation of results and proof sketches is clear. \n\nThe results of this paper are significant, improving an $O(1/\\sqrt{n})$ term over previous utility bounds, with the help of introducing the Generalized Bernstein condition and the Polyak-Łojasiewicz condition.\n\nWeakness:\n\nThe proof of Theorem 1 mainly follows Klochkov & Zhivotovskiy 2021, extending their result to the DP case using the same method. Theorem 2&3 have more novelty, but are less important than Theorem 1 in my opinion. The technical difficulties should be discussed in more details, to convince the readers that 1: the two new conditions are not too strong, 2: extending the results in Klochkov & Zhivotovskiy 2021 to the DP setting is non-trivial.", "summary_of_the_paper": "This paper extends the results in Klochkov & Zhivotovskiy 2021 to the DP case, proving the first $O(1/n)$ high probability excess population risk bound for differentially private algorithms, assuming Lipschitzness, smoothness, Generalized Bernstein condition and Polyak-Łojasiewicz condition. Then the authors relax the assumptions of Lipschitzness+smoothness to $\\alpha$-Holder smoothness, and propose a new normalized gradient pertubation algorithm that also achieves the $O(1/n)$ bound.", "summary_of_the_review": "The presentation of results is clear. Extending existing results to the DP case and getting the first O(1/n) utility bound is significant. The method is mostly based on Klochkov & Zhivotovskiy 2021, thus not very novel.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "cLHF7Y-XigT", "reviewer": "Reviewer_n773", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The problem is interesting and natural. This paper proposes the first $O(p^{0.5}/(n\\epsilon))$ high probability excess population risk bound for DP algorithms under the assumptions Holder smooth, and PL condition (or Lipschitz, smooth, and PL condition). Comparing with previous results ($O(p^{0.5}/(n^{0.5}\\epsilon))$), the improvement is significant, of the order $O(n^{0.5})$.\n\n2. For the provided utility bounds, convexity of the loss function is replaced with the PL condition, so the results can be applied to many non-convex settings.\n\n3. The paper also generalizes the $O(p^{0.5}/(n\\epsilon))$ result to the non-smooth settings, by assuming the loss function to be Holder smooth and introducing normalization to traditional gradient perturbation method.\n\n4. The results of this work are clear, novel concepts (techniques) are introduced to overcome the technical difficulties, and the technical contributions overall seem very solid. In this paper, the algorithmic stability is applied to bound the gap between the generalization error and its expectation, and via the Generalized Bernstein condition, the expectation one is solved. Another important part to achieve the superior theoretical results is to combining the generalization error together with term $R_n(\\theta^*)$. Besides, the optimization error is solved under different assumptions, for smooth loss function, the proof is similar to previous works. But for non-smooth loss function, Holder smoothness is introduced and Young's inequality is applied to get the bound, and an additional term with $\\eta$ exists. So the authors choose $\\eta$ for each iteration carefully in Theorem 2 to get the claimed result. This is also the motivation of their proposed algorithm: to eliminate the additional term. After eliminating it, the proof of the new algorithm is similar to previous works.\n\n5. Experiments on real datasets are performed to evalute their proposed algorithm m-NGP, the results show that the accuracy is better than traditional gradient perturbation DP method.\n\nWeaknesses:\n1. From my perspective, Holder smoothness implies $\\max\\{2HM_\\mathcal{C},H\\}$-Lipschitz if the parameter space is bounded by $M_\\mathcal{C}$ (In Section 3, the authors claim it is $\\max\\{HM_\\mathcal{C},H/2\\}$-Lipschitz). The claim should be explained or corrected.\n\n2. The paper overall read clearly, though the proof sketches should be more clear. For example, in Theorem 1, the authors say that 'the gradient perturbation based DP algorithm is $\\mathcal{O}(T\\eta/n)$ uniformly stable w.t.t n with high probability', but what are the connections between the uniformly stability and the given result? While the algorithmic stability is indeed closely related to the generalization error, the descriptions should be more detailed.\n\n3. There are minor mistakes when analyzing the gap between $\\theta_n$ and $\\hat{\\theta}_n$, although it does not affects the results signifacantly, the mistakes should be corrected.\n\n4. Some of the notations should be defined before used. For example, $R_n(\\hat{\\theta}_{t-1})$ in (1) is formally defined after it, and $\\eta_t$ in (1) is not explained throughout the paper. The authors should check them carefully.\n\n5. Although the understandability of the current manuscript is acceptable, I encourage the authors to correct the typos and the grammatical errors in future versions.", "summary_of_the_paper": "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.", "summary_of_the_review": "The results given by this paper are clear, the theoretical analysis seems solid, the organization and the presentation are fine. But the proof sketches should be more clear, the notations, the typos, and the grammatical errors should be checked. Although there are some minor issues, I recommend this paper to be accepted because of the superior theoretical results and the novel technologies.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CO2cW-S77TS", "reviewer": "Reviewer_AguJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the problem statement of the paper is interesting and important. The authors aim to solve the important open problem in DP community: to achieve high probability excess population risk bounds with tighter upper bound. The paper is well-written and has clear writing logical.  The authors make solid theoretical contribution and based on the logical in theoretical analysis, they propose the new algorithm to achieve better excess risk bound. It would be good to bring the experiments on real datasets to verify theoretical results. But there are some limitations in the paper. Firstly, the authors do not give existence of function under Assumption 4 and Assumption 5 simultaneously. Secondly, the authors only give the upper bound of excess risk bound and there is no lower bound, so it is unknown that their bound is optimal. Thirdly, in experiment part, the authors do not descript the loss function task and if the function in experiments satisfies these assumptions in theoretical part. Besides, they should give the performance about changing privacy parameter and dimension parameter.", "summary_of_the_paper": "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.", "summary_of_the_review": "It is not sure that there is the function satisfying assumption 4 and assumption 5,so the problem setting may be not reasonable. And the authors do not give the loss function task in detail in experimental part. There is no lower bound so we do not know if this upper bound is optimal. And the authors should give more experiments about different parameter. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BxneQaQhqDr", "reviewer": "Reviewer_wceT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\nThe authors discussed each assumption in detail, which gives the result under various assumptions.\nThe analysis hints that the generalized Bernstein inequality could provide a new tool for improving population risk bound and other differentially private algorithms.\nThe algorithm is empirically evaluated on a number of datasets and achieved noteworthy results.\n\nQuestions:\nIt seems that mNGP is proposed solely for the sake of bypassing Young’s inequality. However in the empirical evaluation it seems that the normalization works well on various datasets. Could the authors elaborate on this and provide some intuition on why normalization works in practice?\nFor the experiment results, could you report the variance and the number of random seeds used? Will it be open source?\nThe paper shows that normalization helps with improving population risk bound, though the convergence rate of the algorithm is yet to be discussed. Could the authors provide an insight on whether the normalization will affect the convergence rate? If so, to what extent should we expect normalization to affect the rate?\n\nTechnical questions:\nFor Theorem 3, in the step where you get R_n(\\hat{\\theta}_t) - R_n(\\theta^\\ast_n), the authors refer to Lemma 7, which gives us the bound on R_n(\\theta_t) - R_n(\\theta^\\ast_n). This along with R_n(\\theta_n) - R_n(\\theta^\\ast_n) does not give a bound for R_n(\\hat{\\theta}_n) - R_n(\\theta^\\ast_n). How did it go through?\nIn the proof of Lemma 3, why do we need to assume $i=n$? This condition is not used in (4) and the remaining proofs.\nBousquet lemma is referred both as lemma 4 and lemma 7 in the section.\nAppendix A.2 Lemma 3: Consider stating lemma 4 first and then state and prove lemma 3 for the sake of clarity. The same goes for Lemma 5 and 6. It is also unclear to me why ``Bounding’’ is in bold text.\n• For (17), is \\psi is defined prior to this equation?", "summary_of_the_paper": "This paper gives a high probability excess population risk bound for differentially private optimization algorithm under $G$-Lipschitz, $L$-smooth and PL condition with gradient perturbation. This paper also gives a result under $\\alpha$ Holder smoothness, with an optimized bound and a new normalized gradient perturbation scheme.", "summary_of_the_review": "This manuscript provides a sharper utility analysis up to some clarity in the proofs. There's also some reservation on the significance of the techniques presented in the proofs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives high probability bounds on excess risk for differentially private learning algorithms, in the setting where the loss is assumed to be Lipschitz, smooth, and assumed to satisfy the Polyak-Łojasiewicz (PL) condition. The key idea in the paper is to leverage the curvature in the loss (PL condition) and the generalized Bernstein condition. 

Authors show that they get sharper bounds of the order \sqrt{p}/(n\epsilon) when the loss is assumed to satisfy the PL condition besides being convex Lipschitz/smooth. Without using some curvature information about the loss function, the best upper bounds we can get are in the order of \sqrt{p}/(n\epsilon) + 1/\sqrt{n} — and this is tight at least in terms of the dependence on n given the nearly matching lower bounds — in fact, the dependence on n is tight as it matches the non-private settings.  

So, I find it a bit misleading when authors say that they improve over the existing results. That statement is not true in its generality — it is true that we can leverage the PL condition to give faster rates but that is not the setting of prior work. Again, the bounds that authors compare against are for smooth/Lipschitz convex loss functions and without any assumption on the curvature of the loss. 

If we do look at the literature for when and/or how can curvature help, we can compare against the existing bounds for strongly convex losses. The best-known result in the setting that is most closely related is that of Feldman et al. (STOC 2020): https://dl.acm.org/doi/pdf/10.1145/3357713.3384335. As we can check from Theorem 4.9 in that paper, the bounds we get are in the order of 1/n + d/n^2 which is actually better — not surprising since PL condition is a weaker condition. There is merit to the results in this paper but the current narrative is quite misleading and a more careful comparison with the existing literature is needed. The bounds are hard to parse — for example, what is the dependence on the strong convexity parameter (\mu)? It would also help to instantiate specific loss functions so that we can fix some of the parameters in the bound to have a clear comparison with the existing bounds.
Decision: Reject