Gradient Perturbation is Underrated for Differentially Private Convex Optimization
Authors: Da Yu
Huishuai Zhang
Wei Chen
Tie-yan Liu
Jian Yin
Venue:  (2020)
Keywords: minimum curvature
gradient perturbation
DP-GD
DP-SGD

Abstract: Gradient perturbation, widely used for differentially private optimization, injects noise at every iterative update to guarantee differential privacy. Previous work first determines the noise level that  can satisfy the privacy requirement and then analyzes the utility  of noisy gradient updates as in non-private case.  In this paper, we explore how the privacy noise affects the optimization property. We show that for differentially private convex optimization, the utility guarantee of both DP-GD and  DP-SGD is determined by an \emph{expected curvature} rather than the minimum curvature. The \emph{expected curvature} represents the average curvature over the optimization path, which is usually much larger than the minimum curvature and hence can help us achieve a significantly improved utility guarantee. By using the \emph{expected curvature}, our theory justifies the advantage of gradient perturbation over other perturbation methods and closes the gap between theory and practice. Extensive experiments on real world datasets corroborate our theoretical findings.

Under review as a conference paper at ICLR 2020
GRADIENT PERTURBATION IS UNDERRATED FOR DIFFERENTIALLY PRIVATE CONVEX OPTIMIZATION
Anonymous authors Paper under double-blind review
A ABSTRACT
Gradient perturbation, widely used for differentially private optimization, injects noise at every iterative update to guarantee differential privacy. Previous work first determines the noise level that can satisfy the privacy requirement and then analyzes the utility of noisy gradient updates in non-private case. In this paper, we explore how the privacy noise affects the optimization property. We show that for differentially private convex opti- mization, the utility guarantee of both DP-GD and DP-SGD is determined by an expected curvalure rather than the minimum curvature. The expected curvature represents the average curvature over the optimization path, which is usually much larger than the minimum curvature and hence can help us achieve significantly improved utility guarantce. By using the expected curvature, our theory justifies the advantage of gradient perturbation over other perturbation methods and closes the gap between theory and practice. Extensive experiments on real world datasets corroborate our theoretical findings.
INTRODUCTION
Machine learning has become powerful tool for many practical applications. The training process often needs access to some private dataset, e.g., applications in financial and medical fields. Recent, work has shown that the model learned from training data may leak unintended
information of individual records (Fredrikson al.) 2015 Wu et al. 2016 Shokri et al., 2017 Hitaj et al. 2017). It. is known that Differentaal privacy (DP) (work et al.) 20066 is golden standard for privacy preserving data analysis. provides provable privacy guarantee by ensuring the influence of any individual record is negligible. It has been deployed into real world applications by large-scale corporations and U.S. Consus Bureau EEllingsson et al.
2014 McMillan 2016: Abowd. 2016 Ding et al. 2017).
We study the fundamental problem when differential privacy meets machine learning: the differentially private empirical risk minimization. (DP-ERM) problem (Chaudhuri & Mon- Kifer et al.
teleoni 2009 Chaudhuri et al.
2011
2012 Bassily et al., 2014
Talwar et al. 2015
Wu al. 2017 Zhang et al.
2017
Wang
2017 Smith
2017 Jayaraman et al.
2018 Feldman et al. 2018 Iyengar et al.) 2019
Wang & Gu 2019). DP-ERM mininizes
the empirical risk while guaranteeing that the output of learning algorithm is differentially
private with respect to the training data. Such privacy guarantee provides strong protection against potential adversarics (Hitaj al.) 2017 Rahman privacy, it is necessary to int rotuee randomness to the algorithm. There are usually three ways to introduce randomness according to the time of adding noise: output perburbation, objective perturbation and gradient perturbation.
al. 2018). In order guarantee
Output perturbation (Wu et al.
2017
first runs the learning algorithm then adds noise to the output parameter. Objective
Zhang et al. 2017
the same as in the non-private case
perturbation (Chaudhuri et al. 2011
Kifer et al. 2012: Iyengar et al.] 2019 perturbs the
objective (i.e., the empirical loss) then release the minimizer of the perturbed objective.
Gradient perturbation (Song et al.
2013
Bassily et al. 2014 Abadi et al., 2016 Wang et al.
2017
Lee & Kifer 2018 Jayaraman
al. 2018) perturbs each intermediate update. Il each

---

Under review as a conference paper at ICLR 2020
update is differentially private, the composition theorem of differential privacy ensures the whole learning procedure is differentially private.
Gradient perturbation comes with several advantages over output, cntpuut/objectinnn 'ojeecivve perturbations. Firstly, gradient perturbation does not require strong assumption on the objective because only needs to bound the sensitivity of gradient update rather than the whole learning process. Secondly, gradient perturbation can release the noisy gradient at each iteration without damaging the privacy guarantee differential privacy is immune to post processing (Dwork et al., 2014). Thus, it is a more favorable choice for certain applications such as distribuled optimization (Rajkumar & Agarwal 2012] Agarwal et al.) 2018 Jayaraman et al., 2018). At last, gradient perturbation often achieves better empirical utility than output/ objective perturbations for DP-ERM.
However, the existing theoretical utility guarantee for gradient perturbation is the same as or strictly inferior to that of other perturbation methods as shown in Table This motivates us to ask
"What is wrong with the theory for gradient perturbation? Can we justify the empirical advantage of gradient pert perturbation theoretically?"
We revisit the analysis for gradient perturbation approach. Previous work (Bassily et al. 2014 Wang et al. 2017 Jayaraman et al. 2018) derive the utility guarantee of gradient perturbation via two steps. They first determine the noise variance at each step that meets the privacy requirement and then derive the utility guarantee by using the convergence analysis the same as in non-private case. However, the noise to guarantee privacy naturally affects the optimization procedure, but previous approach does not exploit the interaction between privacy noise and optimization of gradient perturbation.
In this paper, we utilize the fact the privacy noise affects the optimization procedure and establish new and much tighter utility guarantees for gradient perturbation approaches. Our contribution can be summarized follows.
We introduce an expected cureature that can characterize the optimization property accurately when there perturbation noise at each gradient update.
We establish the utility guarantees for DP-GD for both convex and strongly convex objectives based on the expected curvature rather than the usual minimum curvature.
We also establish the the utility guarantees for DP-SGD for both convex and strongly convex objectives based on the expected curvature. To the best of our knowledge, this is the first work remove the dependency on minimum curvature for DP-ERM algorithms.
In DP-ERM literature, there is a gap between the utility guarantee of non-strongly convex objectives and that of strongly convex objectives. However, by using the ezpected curvature, we show that some of the non-strongly convex objectives can achieve the same order of utility guarantee the strongly convex objectives, matching the empirical observation. This bocause the expected curvature could be relatively large even for non-strongly convex objectives.
As we mentioned earlier, prior to our work, there is a mismaich between theoretical guar- antee and empirical observation of gradient perturbation approach compared with other two perturbation approaches. Our result theoretically justifies the advantage of gradient perturbation and close the mismatch.
1.1 PAPER ORGANIZATION
The rest of this paper is organized as follows. Section 2 introduces notations and the DP-ERM task. In Sections 3 we first introduce the expected curvature and establish the utility guarantee of both DD-GD and DP-SGD based on such expected curvature. Then give some discussion on three perturbation approaches. We conduct extensive experiments in Section 4 Finally, we conclude in Section
2

---

Under review as a conference paper at ICLR 2020
Table Expected excess empirical risk bounds under (e, (e, where n. and are the number of samples and the number of parameters, respectively, and 3 and are the smooth coefficient, the strongly convex coefficinnt and the expected curvature, respectively, and v 2 f (see Section 3.1p. We note that μ denotes the convex but not strongly convex objective. The Lipschitz constant L is assumed to be 1. We omit log (1/6) for simplicity.
Authors
Perturbation
Algorithm
Utility (μ 0)
Utility (μ 0)
Chaudhuri
2011
Objective
N/A
vP
nc
un=
Zhang al.
2017
Output
GD
O
v/2p y2/3
Bp !
ne
Bassily et al.
(2014)
Gradient
SGD
o
log" ((n) ne
o
plog" (m) pn
lylog" (n) #
Jayaraman et al.
2018
Gradient
GD
N/A vP Splog(n)
Ours
Gradient
GD
o
Sp log(()) 8²
Th
Ours
Gradient
SGD
o
y/ log(n)
plog(n]
log(n) in
nc
un
PRELIMINARY
We introduce notations and definitions in this section. Given dataset {di, ".l....,,d,,, dn1, the objective function F(x; ; D) is defined as F(x; D) A E f(æ; di), where f(x; d.) R² - R is the loss of model
Rº for the record d,.
For simplicity, we use F(x) to denote F(w; We use || to denote the l2 norm of a vector We Xj arg min fxx to denote the set of optimal solutions of f(x). Throughout this paper, assume Xj non-emply.
Definition (Objective properties). For any æc y E TRP, function f RP -
is L-Liscchitz if [f()) - f(y)) < L | - yll-
is 3-smooth if f(y) S fx) + (Vf(z), y - z) + 2 lly x1?
conver if (v)(x) f x y) 0.
j-strongly convex (or SCS if (v)(=) Vf(y), x 2 2 -
The strong convexity coefficient yu is the lower bound of the minimum curvature of function I over the domain.
We say that two datasets D. D' are neighboring datasets (denoted as D ~ D') if D can be obtained by arbitrarily modifying one record in D' (or vice versa). In this paper we consider (e, d)ddifferelttal privacy as follows.
Definition 2 (c,8)-DP (Dwork et al. 2006a bl). A randomized mechanism M: D
guarontees (e, diffeefert privacy for any two neighboring input datasets D, D and for any subset of outputs 5 R holds that Pr[((D) e S s PHMM(D') $] +
We note that 8 can be viewed as the probability that original c-DP fails and a meaningful setting requires d < 1. By its definition, differential privacy controls the maximum influence that any individual record can produce. Smaller e, implies less information leak but usually lcads to worse utility. One can adjust o to trade off between privacy and utility.
DP-ERM requires the output Bout E R is differentially private with respect to the input dataset D. Let x E X be one of the optimal solutions of F(x), the utility of DP-ERM algorithm is measured by expected excess empirical risk: [((F F(x.)), where the expectation is taken over the algorithm randomness.
3

---

Under review as a conference paper at ICLR 2020
3 MAIN RESULTS
In this section, we first define the erpected curvalure v and explain why it depends only on the average curvature. We then such expected curvature to improve the analysis of both DP-SGD and DP-GD.
3.1 EXPECTED CURVATURE
In non-private setting, the analysis of convex optimization relies on the strongly convex coefficient μ4, which is the minimum curvature over the domain and can be extremely small for some common objectives. Previous work on DP-ERM uses the same analysis as in non-private case and therefore the resulting utility bounds rely on the minimum curvature. In our analysis, however, we avoid the dependency on the minimum curvature by exploiting how the privacy noise affects the optimization. With the perturbation noise, the expected curvature that the optimization path encounters related to the average curvature instead of the minimum curvature. Definition 3 uses to capture such average curvature with Gaussian noise. We use I. arg min || - æ1ll to denote the closest solution to the initial point.
Definition (Expected curvature). conver function IR. + R, has expected curvature with respect to noise (10 Ip) if for any Rp and o x where NO0 o² I)), holds that
B((VF()), ã x.,) uBlll x. 111.
(1)
where the expectation is taken with respect to z.
Claim 1. If F is p-strongly convex, we have v 2 μ.
Proof. can be verified that = y always holds because of the strongly convex definition.
In fact, represents the average curvature and is much larger than μ.. We use xf to denote the transpose of x. Let H = F2F(x) be the Hessian matrix evaluated at æ. We use Taylor expansion to approximate the left hand side of Eq ① follows
((VF(()) - -x.)| = (VF())
H
xx))
FV)(x), x.) HE
(VF()),==.))+++ tr(HH))
For convex objective, the Hessian matrix is posilive semi-definile and Ir Hx) is the sum of the eigenvalues of Hz. We can further express out the right hand side of Eq as follows
E x=1 Elll ==.1111-- (I x.11 + po²)
Based on the above approximation, we can estimate the value of v in Definition t(H.)o*+tllee-..] For relatively large o², this implies v (x(H)) that is the average po2+|æ=0.1
curvature at æ. Large variance is reasonable setting because meaningful differential privacy guarantee requires non-trivial amount of noise.
The above analysis suggests that v can be independent of and much larger than p. This is indeed true for many convex objectives. Let us take the l2 regularized logistic regression as an example. The objective is strongly convex only due to the 12 regularizer. Thus, the minimum curvature (strongly convex coefficient) is the regularization coefficient x. Sharmir el al. [1] shows the optimal choice of À is - (Section 4.3 in [1]). In practice, lypical choice of À is even smaller and could be on the order of m1 Figure compares the minimum and average curvatures of regularized logistic regression during the training process. The average curvature basically unaffected by the regularization term X. In contrast, the minimum curvature reaches À in first few steps. Therefore removing the dependence minimum curvature is a significant improvement. We also plot the curvatures for another datasct KDDCup99 in the Appendix C The resulting curvatures similar to Figure [
Perturbation noise is necessary to attain v > μ. We note that v = p when the training
process does not involve perturbation noise (corresponding to 0 in Definition 3 For
4

---

Under review as a conference paper at ICLR 2020
19
A-0
A-1e-3
88
A= 1e-
6-1
10
0
20
40
60
80
Rurning stops
-55
Figure 1: Curvatures of regularized lo- gistic regression on Adult dataset over training. Dot/cross symbol represents erage/ minimum curvature respectively.
Figure 2: Illustration of a generie loss
function in the high dimensional setting (p>-n, Figure 3 in Negahban et al. (2012)
example, objective jojjctive/output output perturbation cannot utilize this expected curvature condition as no noise is injected in their training process. Therefore, among three existing perturbation methods, gradient perturbation is the only method can leverage such effect of noise.
We note that / 0 does not necessarily lead to v = 0. A concrete example is given in Figure 2 (from Negahban et al. (2012)). provides an illustration the loss function in the high-dimensional (p n. setting, i.e., the resticted strongly convex scenario: the loss is curved certain directions but completely flat in others. The average curvature of such objective is always positive but the worst curvature is O. Though some recent work shows the utility guarantee of high dimensional DP-ERM task may not depend on the worst curvature (Wang & Gu 2019), Figure 2 still provides good illustration for the
of μ O. Moreover, as shown in Figure [ the average curvature of logistic regression on Adult dataset above during the training procedure even the regularization term is O. As we will show later, a positive over the optimization path is sufficient for our optimization analysis.
3.2 UTILITY GUARANTEE OF DP-GD BASED ON EXPECTED CURVATURE
In this section we show that the expected curvature can be used to improve the utility bound of DP-GD (Algorithm
Algorithm 1: Differentially Private Gradient Descent (DP-GD)
Input: Privacy parameters c, 8; running steps T; learning rate Loss function F(x) with Lipschitz constant L.
for t= to T do
Compute 9: = VF (xt).
Update parameter I+41 x; - -7 (gt + zt), where 2, N (0.))11). end for
1. T (lng(1/8))
Algorithm 1 (PP8)-DP if we set o, ④
JJaaaaaaan al. 2018). Let
ne
F1...., Ey be the training path and y min (1 (M,...,, Fre be the minimum expected curvature over the path. Now we present the utility guarantee of DP-GD for the case of v 0
0.). Suppose F L-Lipschilz and B-smooth with Theorem (Utility guarantee, 2log(n) and o, = - (LVT (og(1/6)/nc) we have
expected curvature. Set n S 1 g: T
F (xTT1) - F [==)]=( 0 (Splog (n) L2 log (1/8)
v2n22
Proof. All proofs in this paper relegated to Appendix A
Remark 1. Theorem y only depends on the expected curvature over the training path
5

---

Under review as a conference paper at ICLR 2020
The expectation is taken over the algorithm randomness if without specification. Theorem significantly improves the original analysis DP-GD because of our arguments in Section 3.1 If v 0, then the curvatures which is used by Bassily et al. (0144) to derive their utility lower bound. Such simple function may not be commonly used loss function in practice. Nonetheless, we give the utility guarantee for the case of y = 0 in Theorem 2
flatten in all directions. One example is the linear function,
Theorem 2 (Utility guarantee, y = 0.). Suppose F is I-Lipschitz and B-smooth. Set 3.
T
nãe and of θ (LVTloog(/8)//m Let x E Li+1, we have vp
(OVVV (1/8)
E[F (z) F (ax))
We use parameter averaging to reduce the influence of perturbation noise because gradient update does not have strong contraction effect when
3.3 UTITTTY GUARANTER OF DP-SGD BASED ON EXPECTED CURVATURE
Stochastic gradient descent. has become one of the most popular optimization methods because the cheap one-iteration cost. In this section we show that expected curvature can also improve the utility analysis for DP-SGD (Algorithm 2). We note that V ff(x) represents an element from the subgradient set evaluated at æ when the objective not smooth. Before stating our theorem, we introduce the moments accountant technique (Lemma 1 that is essential to establish privacy guarantee.
Lemma (Abadi et al. 2016 There exist constants 01 and 02 so that given running steps is (e, defff-diiferenttially private for any 8 0 if we choose
T, for any T/T/"" Algorithm (109(1/8)
C2
Algorithm Differentially Private Stochastic Gradient Descent (DP-SGD)
Input Dataset D = {di,..., ). Individual loss function: fi (x) f (æ; di) with
Lipschitz constant L. Number iterations: T', Learning rate: T/c-
for t 1 to T do
Sample & from [n] uniformly.
2
Compute g. Vf, (z,).
Update parameter x++1 = x; - T7 (g. + zt), where 2; ~ (0,
end
For the case of v/ > 0, Theorem presents the utility guarantee of DP-SGD.
Theorem (Utility guarantee, v> 0.). Suppose F I.-Täpschita with v expected curvature. Choose a based on Lemma to guaranter (c, 5)-D. Set = and T = n²??, we have
pL 1LLL log (n) log (1/8)
F (xT) - F (xx)) 0
nie2v
Remark 2. Theorem does not require smooth assumplion.
Theorem shows the utility guarantee of DP-SGD also depends rather than p. We T' = O following Bassily et al. (2014h. We note that T' = O(n²) is necessary even for non-private SGD to reach I/ne precision. We next show for a relatively coarse precision, the running time can be reduced significantly.
Theorem 4. Suppose F' is L-Lipschitz with v expected curvature. Choose based on Lemma to guarantee (e, Set t vs and T = vp Suppose p < n² we have
(VDL log())
([F(xT) - F (xx.) = ==c,)]=0
nav

---

Under review as a conference paper at ICLR 2020
yBL log"
We note that the analysis of Bassily et al. (2014) yields (x)( - (x+)) = O if setting T me vp. which still depends on the minimum curvalure. Theorem shows the utility for the case of V = Theorem 5 (Utility guarantee, V 0.). Suppose F is L--Lipschitz. Assume ||+ S D
for t E [T]. Choose based Lemma 1 to guarantee (c,8)-DP. Let G = LV1 + po? set D and T n²è? we have
7 GVi
(VDlog (1/0)L log (n)
(xT) - F (xx)) = -xx))]=0)
nc
This utility guarantee can be derived from Theorem in (Shamir & Zhang 2013
3.4 DISCUSSION ON THREE PERTURBATION APPROACHES.
In this section, we briefly discuss two other perturbation approaches and compare them to the gradient perturbation approach.
Output perturbation (Wu et al.) 2017 Zhang et al. 2017) perturbs the learning algorithm after training. It. adds noise to the resulting model of non-private learning process. The magnitude of perturbation noise is propositional to the maximum influence one record can cause on the learned model. Take the gradient descent algorithm as an example. At each step, the gradient of different records would diverge the two sets of parameters generated by neighboring datasets, the maximum distance expansion is related to the Lipschitz coefficient. At the same time, the gradient of the same records in two datasets would shrink the parameter distance because of the contraction effect of the gradient update. The contraction effect depends the smooth and strongly convex coelficient. Smaller strongly convex coefficient leads to weaker contraction. The sensitivity of output perturbation algorithm the upper bound on the largest possible final distance between two sets of parameters.
Objective perturbation (Chaudhuri et al. 2011 Kifer et al. 2012 lyengar et al. 2019 perturbs the objective function betore training. It requires the objective function to be strongly convex to guarantce the uniqueness of the solution. It first adds L2 regularization to obtain strong convexity if the original objective is not strongly convex. Then it perturbs the objective with a random lincar term. The sensitivity of objective perturbation is the maximum change of the minimizer that one record can produce. Chaudhuri al. (2011) and Kiler et. al. (2012) use the largest and the smallest eigenvalue (i.e. the smooth and strongly convex coellicient) of the objective's Hessian matrix to upper bound such change.
In comparison, gradient perturbation is more flexible than output objective perturbation. For example, bound the sensitivity, gradient perturbation only requires Lipschitz coefficient which can be casily obtained by using the gradient clipping technique. However, both output and objective perturbation further need to compute the smooth coefficient, which is hard for some common objectives such as soflmax regression.
More critically, output/obyy /objective perturbation cannot utilize the expected curvature condition because their training process does not contain perturbation noise. Moreover, they have to consider the worst performance of learning algorithm. That because DP makes the worst case assumption learning algorithm as a single query to private dataset. This explains why their utility guarantee depends on the worst curvature of the objective.
query function and output/ objective perturbation treat the whole
4 EXPERIMENT
In this section, we evaluate the performance of DP-GD and DP-SGD on multiple real world datascts. We use the benchmark datasets provided by Tyengar et al. (2019). Objective functions are logistic regression and softmar regression for binary and multi-caass datasots, respectively.
Datasets. The benchmark datasets includes two multi-class datasets (MNIST, Covertype) and five binary datasets, and three of them are high dimensional (Gisette, Real-sim, RCV1).
7

---

Under review as a conference paper at ICLR 2020
Table 2: Algorithm validation accuracy (in %) on various kinds of real world datasets. Privacy paramcter c is 0.1 for binary datasct and for multi-classos datasets.
KDDCup99
Adult
MNIST
Covertype
Gisette
Real-sim
RCVI
Non private
99.1
84.8
91.9
71.2
96.6
93.3
93.5
AMI
97.5
79.3
71.9
64.3
62.8
73.1
64.5
Out-SGD
98.1
77.4
69.4
62.4
62.3
73.2
66.7
DP-SGD
98.7
80.4
87.5
67.7
63.0
73.8
70.4
DP-GD
98.7
80.9
88.6
66.2
67.3
76.1
74.9
KDDCup99
300
MNIST
14.
60
85
DP
AMM
BP
NP
OLL-00
DUL-SD
26
20
70
101-0
Yori5.5
10%0
Figure 3: Algorithm validation accuracy (in %) with varying NP represents non-private baseline. Detailed description about evaluated dalasets can be found in Table 3
Following Iyengar et al. (2019), we use 80% data for training and the rest for testing. Detailed description of datasets can be found in Appendix B
Implementation details. We track Rényi differentialy privacy (RDP) Mironov 2017 and convert it to (c, 8)... Running step T is chosen from (50, 200, 800} for both DP-GD and DP-SGD. For DP-SGD, we use moments accountant to track the privacy loss and the sampling ratio is set 0.1. The standard deviation of the added noise is set to be the smallest value such that the privacy budget is allowable to run desired steps. We ensure each loss function is Lipschitz by clipping individual gradient. The method in Goodfellow (2015) allows us to clip individual gradient efficiently. Clipping threshold is set as 1 (0.5 for high dimensional datasets because of the sparse gradient). For DP-GD, learning rate is chosen from f0.1, 1.0, 5.0} (10.2, 2.0, 10.0} for high dimensional datasets). The learning rate of DP-SGD is twice as large DP-GD and it is divided by 2 at the middle of training. Privacy parameter 5 is set as n² The 12 regularization coefficient. is set as 1 x 10-1. All reported numbers are averaged over 20 runs.
1
Baseline algorithms. The bascline algorithms include state-of-tho-art objective and output perturbation algorithuss. For objective perturbation, we use Approzimate Minima Perturba- fion (AMP) [yengarr et al. 2019). For output perturbation, use the algorithm in Wu et al.) (2017) (Output perturbation SGD). We adopt the implementation and hyperparameters in Lyengar et al. (2019) for both algorithms. For multi-class classification tasks, Wu et al. (2017) and Iyengar et al. (2019) divide the privacy budget evenly and train multiple binary classifiers because their algorithms need to compute smooth coefficient before training and therefore are not directly applicable to softmax regression.
Experiment results. The validation accuracy results for all evaluated algorithms with e = 0.1 (1.0 for multi-class datasets) are presented in Table 2 We also plot the accuracy results with varying in Figure 3. These results confirm our theory in Section 3 gradient perturbation achieves better performance than other perturbation methods as it leverages the average curvature.
5 CONCLUSION
In this paper, we show the privacy noise actually helps optimization analysis, which can be used to improve the utility guarantee of both DP-GD and DP-SGD. Our result theoretically
For multi-class datas sets MNIST and Covertype, we use the numbers reported in Tyengar et al. (219 directly because of the long running time of AMP especially on multi-class datasets.
8

---

Under review as a conference paper at ICLR 2020
justifies the empirical superiority of gradient perturbation over other methods and advance the state of the art utility guarantee DP-ERM algorithms. Experiments on real world datasets corroborate our theoretical findings nicely. In the future, it is interesting to consider how to utilize the expected curvature condition to improve the utility guarantee of other gradient perturbation based algorithms.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In ACM SIGSAC Conference on Computer and Conanuiications Securify, 2016.
John M Abowd. The challenge of scientific reproducibility and privacy protection for statistical agencies. Census Scientific Advisory Committee, 2016.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. epsgd: Communicationn-fficceett and differentially-private distributed sgd. In Advances in Neurul Information Processing Systems, 2018.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Differentially private empirical risk mini- mization: Efficient algorithms and tight error bounds. Annual Symposium on Foundations of Computer Science, 2014.
Kamalika Chandhuri and Claire Monteleoni. Privacy-preseeving logistic regression. In Advances in Newral Information Processing Systems, 2009.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 2011.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances in Neurol Information Processing Systems, 2017.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual Internationl Conference on the Theory and Applications of Cryptographic Techniques, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptogrophy conference, 2006b.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy, Foundations and Trendsay in Theoretical Computer Science, 2014.
Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response, In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, 2014.
Vitaly Feldman, Tyy Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In ACM SIGSAC Conference on Computer and Communications Security, 2015.
Ian Goodfellow. Efficient per-example gradient computations. arXiv preprint arXiv:1510.01 019.9199, 2015.
Briland Hitaj, Giuseppe Ateniese, and Fernando Pérez-Cruz. Deep models under the gan: information leakage from collaborative deep learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017.
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In IEFE Symposium on Security and Prinacy, 2019.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-preserving empirical risk minimization. In Advances in Neural Information Processing Systems, 2018.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, 2012.
Jaewoo Lee and Daniel Kifer. Concentrated differentially private gradient descent with adaptive per-iteration privacy budget. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledgee Discovery & Data Mining, 2018
10

---

Under review as a conference paper at ICLR 2020
Robert McMillan. Apple tries to peek at user habits without violating privacy. The Wall Street Journal, 2016.
Ilya Mironov. Rényi differential privacy. In IEEE 30th Computer Security Foundations Symposium (CSF), 2017.
Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, Bin Yu, et al. A unified framework for nigh-dimensional analysis of m-estimators with decomposable regularizers. Statistical Science, 27(4):538-55) 2012.
Md Atiqur Rahunan, Tanzila Ralunan, Robert Laganiere, Noman Mohammeed, and Yang Wang. Membership inference attack against differentially private deep learning model. Transactions on Data Privacy, 2018.
Arun Rajkumar and Shivani Agarwal. A differentially private stochastic gradient descent algorithm for multiparty classification. In Artificial Intelligence and Statistics, 2012.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes, In International Conference on Machine Learning, 2013.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikor, Membership inference attacks against machine learning models. In IEEE Symposium Security and Privucy (SP), 2017.
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In JEEE Symposium Security and Privacy (SP). LEEE, 2017.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE, 2013.
Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang, Nearly optimal private lasso. In Advances in Neural Information Processing Systems, 2015.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Adeances in Neural Information Processing Systems, 2017.
Lingxiao Wang and Quanquan Gu. Differentially private iterative gradient hard Uhresholding for sparse learning. In 28th International Joint Conference Artificial Intelligence, 2019.
Xi Wu, Matthew Fredrikson, Somesh Jha, and Jeffrey F Naughton. A methodology for formalizing model-inversion attacks. In 2016 IEEE 29th Computer Security Foundations Symposium (CSF), 2016.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-basen analytics. ACM International Conference on Management of Data, 2017.
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. In International Joint Conference on Artificial Intelligence, 2017.
11

---

Under review as a conference paper at ICLR 2020
APPENDIX A PROOFS RELATED TO DP-GD AND DP-SGD
Proof of Theorem Let , be the path generated by optimization procedure. Since
contains Gaussian perturbation noise žt-1, Definition 3 gives
R ( x., VF (x+))) 2 12 l1 2.11
Since F is 8-smooth, we have
22, (F))) 2 [
Take linear combination of above inequalities,
Ez,-1 [(2: 2., VF (xx)) 2 8u, [| 2211 (1- 0)
8 Ezi- [II
(2)
(1- 0)
2 OvRB, ||| a..1% 12]
R2,
VF
B
Let rı = || x.Il be the solution error at step We have the following inequalities between r141 and rt.
2 |x, V/
|ate x. 1|2 (7 V (xt+) + Ze, Te - xx.) + V ( + 2
Take expectation with respect to Ze: have
E. Ez (r S ||.,- ..11 2 VF (xx) De a.) + n² VFF (ax) pnpoot
Further take expectation with respect to zt-1 and use Eq have
E [2211] S Fxzz1 [|| x.113]- 21 (VFF
x. TZ.. (ax)) prtot,
$ (1 21 0) m7)) Rz._ (r]] (12 2n10
E (
(5)
Set 0 = 2 and A
Ex, [r241] S (1 yju) Ex,-, 1ril + prj O?. oz
(6)
Applying Eq 6 and laking expectation with respect to z1; 21-1. iteratively yields
Elrial S (1 - mp)* rf + pri Σ (1 - --m o².
Uniform privacy budget allocation schemne sets
TL= log( log(1/8)
o = θ
n²
Therefore
pptTL? log(1/6)
S uulr" o
(8)
?n?
Set
> 2log(n)
np we have
(1 - mp) , = exp (1-
log(1 log(1-mp)
mu) log(n?)
r =exp
(log(1/n²)
log(1 +
I 17v
)u))
rt.
n/
mp
v/u
log(1+ p
1
7
n2
Last inequality holds because
log(1 + nv
for
2
qp
12

---

Under review as a conference paper at ICLR 2020
Therefore, for T 2log(n) ny
have the excepted solution error E(r++1] satisfies
F|r++1]= prjl' log(1/6)
(10)
Since F(x)) is 3-smooth, we have
F(x) - F(x.) S 8
2 1| - x.11.
(11)
Using Eq 10 and Eq we have the excepted excess risk satisfies
B[F(#r+1) F(x.)] = o [mmTL² log(1/6)
vn?c?
for T 2log(n) The utility bound is minimized when T 2 log(n)
Proof of Thwrem
The smooth condition gives us,
F(z++1) < F(xs) (VF())) xxe) + B
|| -xell"
(12)
.n² VF((x.) + +
F((s)) //( (V (.:), VF(e.) + =z)
2
Take expectation with respect to and substitute J
1
[2,[F(((+1) = F(x.) 23
|VF(()))
2,3 poi.
(13)
Subtract F(x.) on both sides and use convexity,
[2,[F(4111) F(xx))] F(w:) F(x.)
v
F' (<:)):
23 "0g
23
(14)
VF(x,))1 + 1
$ (VF(x)),
v.)
20
23
Substitute VF(w:) = ((x: - xe+1)
Ex, (F((+1)) F(x.)] < ((x, #141, W2 x.)
1
Ez, [1x x(+1) - =ell 20p00
2/
B(x 11 D1 xx)
a x4 112 Bx, (00111, 21)
8
f(x: #141, W. - x.)
a1: x
11
Be, (0: 1 172 2i)
8
1 Zoo?
B(w, #441 - x.)
|| w441 1p
(1|=r) a. 11. || a. + po??
(15)
Summing over = 1, I,...,? T and take expectation with respect to #1,..., 2T,
9 ||
1
B[F(#1+1) - F(w.)) )] - 2
x.11
+
3 poi.
(16)
Use convexity,
8
E(F(()) - F(x))] -
||00 - x.11² + 300
27
(17)
9
L3 L3ppToog(1/8
<
||l - m..1 +
2T
Choose T ade
vp we have
(VBL (VDL2log(1/8) log(1/8)
E[F(e) F(w.)] 0
(18)
13

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 2
and We start by giving useful lemmaa.
Lemma 2.
Choose Tpp we the expected solution error of æ, in Algoritlem 2 for any > satisfies
El|m 2..1 2L (1+ +ppp)
tu2
Proof of Lemma We have
|141 x. = at 1/.h - 7/21 - =x-11²
(19)
at æ=112 2nps (ce: g. + zi) + 1/é ||::1| 21/ (gt, z.) + nē ||
Take expectation with respect to pertur noise and uniform sampling, we have
Ex Øo+1
=.1l"] Bs || righ 1/z ==1l²]
(20)
||0 x.
2np (x. x., (xx)) tt pnù 1220
Further take expectation to x and apply Definition
Ex 111 - x.11 & (1 21/T):) 13,-- |||a - x-11²
+ + n² (1 +1+ pa²)
(21)
< (1 2/m))) Ez, [||eee - x. 11 + L² (1 pa²))
Now we use induction to conduct the proof. Substitute Tne into Eq 21 have Lemma for = 2.
2 hold
22 (1-po")
Assume [[[[ v.. 11.1
holds for 2, then
2
122 (1 +po")
E||| - x=.1² v
B Biil2 - x.1171
1/213
2L (1 + +po²)
L3 po²)
(22)
t²
1/2
1222
2
3
2 (1 po²))
2L (1 + po²)
i
1/2
(1 + 1)
It's easy to check that Eq 20 holds for arbitrary rather than æ.. Rearrange Eq 20 and take expectation, we have
Eliaa - 1=13] Elll=e+1 - m113 mLL (1+
B (z:)) S
(23)
27
Let & be arbitrarily chosen from (L...., [T/2]}. Summing over the last + 1 iterations and use convexity to lower bound (æe, V (xx)) by F (w.) F (x),
Σ E[F (x:) Fx)) <
| x
1
Σ
Bliaa - x (1 1111
20pr-
2
ne-1
1-T k+1
(24)
E #T41
a
L (1 po
T
n
2nz
2
T=
Substitute 7t = 1. and follow the idea in Shamir Zhang 2013 by choosing æ = ær-k, we arrive
at
F - F(xr-x)) =0
Σ
x1-+
1 + po?)
Σ T=
1
(25)
2y
(-T-
14

---

Under review as a conference paper at ICLR 2020
Now we bound || -r-+|l lor T k
Bllla - x $ 2R| |0 v..1% [1 + 21R]
ØT - 22.1
4L2 (1 + pa²)
(1
T - k. ) -
1
81. (1+ po²)
V²
v²
T T-k
(26)
16L (1 poo)
Tv²
Substitute Eq 26
into Eq 25
8kL2 (1 + po²)
L2 (1+ 11+pp* po?)
Σ
E|P (ac.) F (00T
Σ
(27)
Tv
2v
Let St = E+I E
B (xx)] be the averaged expected values of the last lo + iterations. We are interested F (a.) = E[F (Ir)) (æ.)). Now we derive an inequality between Ss and Sk-1. By definition,
kSt (k + 1) Sz E[Ør-t].
(28)
Rearrange Eq 27
to upper bound -E(pT-u),
-1
Sk-1
Sk
k
+
1
8T, (1 [1+ po7)
1 (1 + pa3
Σ
k
1k+1)TV
2k (k: + 1)
(29)
T-
L (1 + pot))
16
T Σ
Sx
2v
KT
k (k++1)
T-T-
Summing over k I,... -T/2],,
So S S T/2) +
1,2 (1 + pp0)
16
17/2|
Σ
Σ
(30)
2v
KT
k (lc 1)t
k=1
T=
Now we bound S - F(x.). Choose x. = D. and
in Eq 24
to
R| 0TTy2|
x. =x.111]
E (mi) F (x.))
Bl[aa: x=11
2
2
I- 12/2
im
[2/2
L + poo)
Σ
178
2
t=1T/21
2 + p
Σ
(31)
V
21
[-T2/2
L + pO²)
T Σ
7
1
t=/T/21
4L (1 po²)
V
The second inequality uses Lemma log(2). Dividing Eq 31 by [T/2].
The last inequality holds because the fact that ΣT
5
81. + p
S S F(w.) <
(32)
Tv
15

---

Under review as a conference paper at ICLR 2020
We have Σ
12/2 kl
16(1 (T)
because it is harmonic sequence. Lastly,
12/2
Σ
T
[7/2
1og(2)
k
1)8
k:(1: + 1)
(33)
1/22
log(2)
S 2 (20]
k2
Am
Plugging these bounds into Eq 30 we have
So F(x.) =0
(1 po 1 log(1)
(34)
Tv
Choose 0² = 0 (Tlog(1/6) n² (Faggty/a) to guarantee (c, Set T = n²ē, we have
So F(x.) = o pL loggo log(l)))ooooo (1/8)
(35)
n²6av
Set T= vp
and assume n², we have
(VDL." \og()) nev
So -xx.
(36)
APPENDIX B DETAILED DESCRIPTION ON BENCHMARK DATASETS
Table Detailed description of seven real world datasets.
dalasel
Adul KDDDKD)Dp999MN
Covertype
Gisette
Real-sim
records
45220
70000
65000
581012
6000
72309
50000
features
104
114
784
54
5000
20958
47236
# classes
2
2
10
2
A APPENDIX C COMPARISON BETWEEN AVERAGE AND MINIMUM CURVATURES ON DIFFERENT DATASET
In this section plot the average and minimum curvatures in Figure f for another dataset KDDCup99. The objective function is still regularized logistic regression.
As shown in Figure the average curvature is still larger than the minimumn curvature (especially when the regularization term small). Despite this, the average curvature of KDDCup99 is smaller than Adult, this may be the reason why the improvement in Section 4 is larger for the Adult dataset.
16

---

Under review as a conference paper at ICLR 2020
10-1
cunneture
A-1-4
16:4
10
40
60
Figure 4: Curvatures of regularized logistic regression KDDCup99 dataset over training. Dot symbol represents average curvature and cross symbol represents minimum curvature.
17


Reviews:
[{"review_id": "rkgbIe-x9B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of differentially private optimization in the (strongly) convex setting. The authors focus on the gradient perturbation methods, i.e., DP-GD and DP-SGD, and provide the utility guarantees of DP-GD and DP-SGD under the so called expected curvature assumption. However, it is very hard to verify the expected curvature assumption, and thus the theoretical results may be invalid. I summarize my main concerns as follows:\n\n1. All the theoretical results provided in this paper are based on the expected curvature assumption (Definition 3). However, it is unclear what kind of loss functions will satisfy this assumption. If the authors can prove that this assumption can hold for some specific loss functions, such as logistic loss or square loss, the contributions of the current paper will be much stronger.\n2. Again it is unclear how large $\\nu$ will be compared to $\\mu$, and thus the theoretical results can be useless.\n3. Since the authors use the approximation form of the gradient in equation (2), why the first inequality in equation (2) holds according to Definition 3?\n4. How do you get the average and minimum curvatures in Figure 1?\n5. I don’t think the argument in the last paragraph in section 3.1 is sound. Because for the restricted strongly convex function, we will ensure the loss curvatures stay in certain directions during the training process.\n6. The contribution of the current paper is very incremental. All the proofs are just replacing the strongly convex condition with the expected curvature condition.\n7. There are several gradient perturbation based DP algorithms [1,2] for solving high-dimensional problems are missing in the related work.\n\nReference:\n[1].Talwar, Kunal, Abhradeep Guha Thakurta, and Li Zhang. \"Nearly optimal private lasso.\" Advances in Neural Information Processing Systems. 2015.\n[2].Wang, Lingxiao, and Quanquan Gu. \"Differentially Private Iterative Gradient Hard Thresholding for Sparse Learning.\" 28th International Joint Conference on Artificial Intelligence. 2019.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJl7v3nptS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Differential privacy (DP) can be achieved by perturbing the objective function, the output or the gradient. In this paper, the authors consider gradient perturbation and claim that it is more advantageous than other methods. To prove this claim, they present a novel utility analysis by taking the noise into account. The previous papers (like Bassily et. al) present utility guarantees in DP context, but their analysis follow the same steps used for non-noisy setting. In non-noisy setting, the analysis is based on strong convexity parameter \\mu which is the minimum curvature. However, in this study they present ”expected curvature” which is computed by considering the noise variance and based on averaging the curvatures along the number of iterations. The order of utility is given for both convex and strongly convex objectives and it has become smaller than the previous studies. Since other perturbation methods does not add noise at intermediate steps, expected curvature is the same with \\mu and the utility advantage is not valid.\n\nComments (Positive)\n\n- The paper is well-written and easy to follow. I didn’t see typos or mistakes (I didn’t check the last proof).\n\n- They claim that they are the first study showing the advantage of gradient perturbation theoretically (I haven’t seen such a study either).\n\n- Since they remove the dependency to minimum curvature \\mu, they present utility order for both convex and strongly convex objective for DP-GD and DP-SGD.\n\n- With the help of privacy noise, they obtain a better utility which is an interesting contribution.\n\nComments (Negative)\n\n- In the numerical experiments, number of iterations are taken as 20, 200 and 800. It might be checked for more iterations. The chosen privacy levels are tight enough (0.1 - 1).\n\n- The learning rate of DP-SGD is divided by 2 at the middle of training. The reason and whether it is applied to other SGD method is not clear.\n\n\nOverall, this type of utility analysis exists in the DP literature, but their novelty comes from the idea of averaging the curvature.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxSHXMe5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a quantity called expected curvature to analyze the convergence of gradient perturbation based methods that achieves differential privacy. Comparing to minimum curvature, which was used in previous convergence analyses, expected curvature better captures the properties of the optimization problem, and thus offers an explanation for the advantage of gradient perturbation based methods over objective perturbation and output perturbation.\nUsing expected curvature is a pretty interesting idea, and having more refined convergence bound is useful. I have the following questions.\n1. It seems to me that the convergence bound is similar to previous bound, except that \\mu is replaced by \\nu and one log(n) disappears. Could you explain more intuitively how hard the new analysis is? Is it similar to just replacing any \\mu by \\nu in the previous analysis? And why do they differ by log(n)?\n2. How are the experiments (in terms of setup and results) differ from those in Iyengar et al? It seems to me the paper is proposing a method for convergence analysis and the DP algorithms remain the same. I feel like in Iyengar et al, there is no clear difference between gradient perturbation and objective perturbation. Maybe I was wrong about that, but could you elaborate more?\n3. I agree that the expected curvature better captures the convergence of gradient-based DP methods. Yet I don’t see clearly how this can be used to show that they have more advantages than objective perturbation. Is it possible that the analyses of objective perturbation can also be improved (maybe with other techniques)? Since all we have are upper bounds, I feel like it is a bit early to conclude that it is less powerful. You mentioned that “That is because DP makes the worst-case assumption on query function and output/objective perturbation treat the whole learning algorithm as a single query to private dataset. ” I didn’t follow this part. I feel like DP is always making a worst-case assumption; even for gradient perturbation, you need to add noise to protect the worst case. Could you elaborate more on that?\n4. My understanding is that for different dataset the curvatures would be different. I think it might be interesting if you plot something similar to Figure 1 for other datasets and compare how they match with the training curve. Do you expect them to look very different on different dataset / optimization problem?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors showed that for differentially private convex optimization, the utility guarantee of both DP-GD and  DP-SGD is determined by the expected curvature rather than the worst-case minimum curvature. Based on this motivation, the authors justified the advantage of gradient perturbation over other perturbation methods. This is a borderline paper, and has been discussed after author response. The main concerns of this paper include (1) the authors failed to show any loss function that can satisfy the expected curvature inequality; (2) the contribution of this paper is limited, since all the proofs in the paper are just small tweak of existing proofs; (3) this paper does not really improve any existing gradient perturbation based differentially private methods. Due to the above concerns, I have to recommend reject.
Decision: Reject