Gradient Perturbation is Underrated for Differentially Private Convex Optimization
Year: 2019

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 expected curvature 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 a significantly improved utility guarantee. 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.

text: 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 expected curvature 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 a significantly improved utility guarantee. 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.

heading: 1 Introduction
text: Machine learning has become a 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 et al., 2015; Wu et al., 2016; Shokri et al., 2017; Hitaj et al., 2017). It is known that Differential privacy (DP) (Dwork et al., 2006a;b) is a golden standard for privacy preserving data analysis. It 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. Census Bureau (Erlingsson 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 & Monteleoni, 2009; Chaudhuri et al., 2011; Kifer et al., 2012; Bassily et al., 2014; Talwar et al., 2015; Wu et al., 2017; Zhang et al., 2017; Wang et al., 2017; Smith et al., 2017; Jayaraman et al., 2018; Feldman et al., 2018; Iyengar et al., 2019; Wang & Gu, 2019). DP-ERM minimizes 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 adversaries (Hitaj et al., 2017; Rahman et al., 2018). In order to guarantee privacy, it is necessary to introduce randomness to the algorithm. There are usually three ways to introduce randomness according to the time of adding noise: output perturbation, objective perturbation and gradient perturbation.
Output perturbation (Wu et al., 2017; Zhang et al., 2017) first runs the learning algorithm the same as in the non-private case then adds noise to the output parameter. Objective 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 et al., 2018) perturbs each intermediate update. If each
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/objective perturbations. Firstly, gradient perturbation does not require strong assumption on the objective because it 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 as differential privacy is immune to post processing (Dwork et al., 2014). Thus, it is a more favorable choice for certain applications such as distributed 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 1. This motivates us to ask
“What is wrong with the theory for gradient perturbation? Can we justify the empirical advantage of gradient 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 as follows.
• We introduce an expected curvature that can characterize the optimization property accurately when there is 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 to 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 expected curvature, we show that some of the non-strongly convex objectives can achieve the same order of utility guarantee as the strongly convex objectives, matching the empirical observation. This is because the expected curvature could be relatively large even for non-strongly convex objectives.
As we mentioned earlier, prior to our work, there is a mismatch between theoretical guarantee 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.

heading: 1.1 Paper Organization
text: 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 DP-GD and DP-SGD based on such expected curvature. Then we give some discussion on three perturbation approaches. We conduct extensive experiments in Section 4. Finally, we conclude in Section 5.

heading: 2 Preliminary
text: We introduce notations and definitions in this section. Given dataset D = {d1, . . . , dn}, the objective function F (x;D) is defined as F (x;D) =∆ 1n ∑n i=1 f(x; di), where f(x; di) : Rp → R is the loss of model x ∈ Rp for the record di. For simplicity, we use F (x) to denote F (x;D). We use ‖v‖ to denote the l2 norm of a vector v. We use X ∗f = arg minx∈Rp f(x) to denote the set of optimal solutions of f(x). Throughout this paper, we assume X ∗f non-empty.
Definition 1 (Objective properties). For any x,y ∈ Rp , a function f : Rp → R
• is L-Lipschitz if |f(x)− f(y)| ≤ L ‖x− y‖.
• is β-smooth if f(y) ≤ f(x) + 〈∇f(x),y − x〉+ β2 ‖y − x‖ 2.
• is convex if 〈∇f(x)−∇f(y),x− y〉 ≥ 0.
• is µ-strongly convex (or µ-SC) if 〈∇f(x)−∇f(y),x− y〉 ≥ µ ‖x− y‖2.
The strong convexity coefficient µ is the lower bound of the minimum curvature of function f 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 ( , δ)-differential privacy as follows.
Definition 2 ( ( , δ)-DP (Dwork et al., 2006a;b)). A randomized mechanismM : D → R guarantees ( , δ)-differential privacy if for any two neighboring input datasets D,D ′ and for any subset of outputs S ⊆ R it holds that Pr[M(D) ∈ S] ≤ e Pr[M(D′) ∈ S] + δ.
We note that δ can be viewed as the probability that original -DP fails and a meaningful setting requires δ 1n . By its definition, differential privacy controls the maximum influence that any individual record can produce. Smaller , δ implies less information leak but usually leads to worse utility. One can adjust , δ to trade off between privacy and utility.
DP-ERM requires the output xout ∈ Rp is differentially private with respect to the input dataset D. Let x∗ ∈ X ∗F be one of the optimal solutions of F (x), the utility of DP-ERM algorithm is measured by expected excess empirical risk : E[F (xout) − F (x∗)], where the expectation is taken over the algorithm randomness.

heading: 3 Main Results
text: In this section, we first define the expected curvature ν and explain why it depends only on the average curvature. We then use such expected curvature to improve the analysis of both DP-SGD and DP-GD.

heading: 3.1 Expected Curvature
text: In non-private setting, the analysis of convex optimization relies on the strongly convex coefficient µ, 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 is related to the average curvature instead of the minimum curvature. Definition 3 uses ν to capture such average curvature with Gaussian noise. We use x∗ = arg minx∈X∗ ‖x− x1‖ to denote the closest solution to the initial point. Definition 3 (Expected curvature). A convex function F : Rp → R, has expected curvature ν with respect to noise N (0, σ2Ip) if for any x ∈ Rp and x̃ = x− z where z ∼ N (0, σ2Ip), it holds that E[〈∇F (x̃), x̃− x∗〉] ≥ νE[‖x̃− x∗‖2], (1) where the expectation is taken with respect to z. Claim 1. If F is µ-strongly convex, we have ν ≥ µ.
Proof. It can be verified that ν = µ always holds because of the strongly convex definition.
In fact, ν represents the average curvature and is much larger than µ. We use x′ to denote the transpose of x. Let Hx = ∇2F (x) be the Hessian matrix evaluated at x. We use Taylor expansion to approximate the left hand side of Eq (1) as follows
E[〈∇F (x̃), x̃− x∗〉] ≈ E[〈∇F (x)−Hxz,x− z − x∗〉] = 〈∇F (x),x− x∗〉+ E[z′Hxz] = 〈∇F (x),x− x∗〉+ σ2 tr(Hx).
For convex objective, the Hessian matrix is positive semi-definite and tr(Hx) is the sum of the eigenvalues of Hx. We can further express out the right hand side of Eq (1) as follows
E[‖x̃− x∗‖2] = E[‖x− z − x∗‖2] = ν ( ‖x− x∗‖2 + pσ2 ) .
Based on the above approximation, we can estimate the value of ν in Definition 3: ν . tr(Hx)σ 2+µ‖x−x∗‖2
pσ2+‖x−x∗‖2 . For relatively large σ2, this implies ν ≈ tr(Hx)p that is the average curvature at x. Large variance is a reasonable setting because meaningful differential privacy guarantee requires non-trivial amount of noise.
The above analysis suggests that ν can be independent of and much larger than µ. 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 l2 regularizer. Thus, the minimum curvature (strongly convex coefficient) is the regularization coefficient λ. Sharmir et al. [1] shows the optimal choice of λ is Θ(n−1/2) (Section 4.3 in [1]). In practice, typical choice of λ is even smaller and could be on the order of n−1. Figure 1 compares the minimum and average curvatures of regularized logistic regression during the training process. The average curvature is basically unaffected by the regularization term λ. In contrast, the minimum curvature reaches λ in first few steps. Therefore removing the dependence on minimum curvature is a significant improvement. We also plot the curvatures for another dataset KDDCup99 in the Appendix C. The resulting curvatures are similar to Figure 1.
Perturbation noise is necessary to attain ν > µ. We note that ν = µ when the training process does not involve perturbation noise (corresponding to σ = 0 in Definition 3). For
example, objective/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 ν = 0. A concrete example is given in Figure 2 (from Negahban et al. (2012)). It provides an illustration of the loss function in the high-dimensional (p > n) setting, i.e., the resticted strongly convex scenario: the loss is curved in certain directions but completely flat in others. The average curvature of such objective is always positive but the worst curvature is 0. 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 a good illustration for the case of ν > µ = 0. Moreover, as shown in Figure 1, the average curvature of logistic regression on Adult dataset is above 0 during the training procedure even the regularization term is 0. As we will show later, a positive ν over the optimization path is sufficient for our optimization analysis.

heading: 3.2 Utility Guarantee of DP-GD Based on Expected Curvature
text: In this section we show that the expected curvature can be used to improve the utility bound of DP-GD (Algorithm 1).
Algorithm 1: Differentially Private Gradient Descent (DP-GD) Input: Privacy parameters , δ; running steps T ; learning rate η. Loss function F (x) with Lipschitz constant L. for t = 1 to T do Compute gt = ∇F (xt). Update parameter xt+1 = xt − ηt (gt + zt), where zt ∼ N ( 0, σ2t Ip ) .
end for
Algorithm 1 is ( , δ)-DP if we set σt = Θ ( L √ T log(1/δ)
n
) (Jayaraman et al., 2018). Let
x1, . . . ,xT be the training path and ν = min{ν1, . . . , νT } be the minimum expected curvature over the path. Now we present the utility guarantee of DP-GD for the case of ν > 0 . Theorem 1 (Utility guarantee, ν > 0.). Suppose F is L-Lipschitz and β-smooth with ν expected curvature. Set η ≤ 1β , T = 2 log(n) ην and σt = Θ ( L √ T log(1/δ)/n ) , we have
E[F (xT+1)− F (x∗)] = O ( βp log (n)L2 log (1/δ)
ν2n2 2
) .
Proof. All proofs in this paper are relegated to Appendix A.
Remark 1. Theorem 3 only depends on the expected curvature over the training path ν.
The expectation is taken over the algorithm randomness if without specification. Theorem 1 significantly improves the original analysis of DP-GD because of our arguments in Section 3.1. If ν = 0, then the curvatures are flatten in all directions. One example is the linear function, which is used by Bassily et al. (2014) to derive their utility lower bound. Such simple function may not be commonly used as loss function in practice. Nonetheless, we give the utility guarantee for the case of ν = 0 in Theorem 2. Theorem 2 (Utility guarantee, ν = 0.). Suppose F is L-Lipschitz and β-smooth. Set η = 1β ,
T = nβ √p and σt = Θ ( L √ T log(1/δ)/n ) . Let x̄ = 1T ∑T i=1 xi+1, we have
E[F (x̄)− F (x∗)] = O (√ pL2 log (1/δ)
n
) .
We use parameter averaging to reduce the influence of perturbation noise because gradient update does not have strong contraction effect when ν = 0.

heading: 3.3 Utiltiy Guarantee of DP-SGD Based on Expected Curvature
text: Stochastic gradient descent has become one of the most popular optimization methods because of 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 ∇f(x) represents an element from the subgradient set evaluated at x when the objective is not smooth. Before stating our theorem, we introduce the moments accountant technique (Lemma 1) that is essential to establish privacy guarantee. Lemma 1 (Abadi et al. (2016)). There exist constants c1 and c2 so that given running steps T , for any < c1T/n2, Algorithm 2 is ( , δ)-differentially private for any δ > 0 if we choose
σ ≥ c2 √ Tlog(1/δ)
n .
Algorithm 2: Differentially Private Stochastic Gradient Descent (DP-SGD) Input :Dataset D = {d1, . . . , dn}. Individual loss function: fi (x) = f (x; di) with
Lipschitz constant L. Number of iterations: T . Learning rate: ηt. 1 for t = 1 to T do 2 Sample it from [n] uniformly. 3 Compute gt = ∇fit (xt). 4 Update parameter xt+1 = xt − ηt (gt + zt), where zt ∼ N ( 0, L2σ2Ip ) . 5 end
For the case of ν > 0, Theorem 3 presents the utility guarantee of DP-SGD. Theorem 3 (Utility guarantee, ν > 0.). Suppose F is L-Lipschitz with ν expected curvature. Choose σ based on Lemma 1 to guarantee ( , δ)-DP. Set ηt = 1νt and T = n 2 2, we have
E[F (xT )− F (x∗)] = O ( pL2 log (n) log (1/δ)
n2 2ν
) .
Remark 2. Theorem 3 does not require smooth assumption.
Theorem 3 shows the utility guarantee of DP-SGD also depends on ν rather than µ. We set T = Θ(n2) following Bassily et al. (2014). We note that T = Θ(n2) is necessary even for non-private SGD to reach 1/n2 precision. We next show for a relatively coarse precision, the running time can be reduced significantly. Theorem 4. Suppose F is L-Lipschitz with ν expected curvature. Choose σ based on Lemma 1 to guarantee ( , δ)-DP. Set ηt = 1νt and T = n √ p . Suppose p < n 2, we have
E[F (xT )− F (x∗)] = O (√ pL2 log(n)
n ν
) .
We note that the analysis of Bassily et al. (2014) yields E[F (xT )−F (x∗)] = O (√ pL2 log2(n)
n µ ) if setting T = n √p , which still depends on the minimum curvature. Theorem 5 shows the utility for the case of ν = 0. Theorem 5 (Utility guarantee, ν = 0.). Suppose F is L-Lipschitz. Assume ‖xt‖ ≤ D for t ∈ [T ]. Choose σ based on Lemma 1 to guarantee ( , δ)-DP. Let G = L √ 1 + pσ2, set ηt = D G √ t and T = n2 2, we have
E[F (xT )− F (x∗)] = O
(√ p log (1/δ)L log (n)
n
) .
This utility guarantee can be derived from Theorem 2 in (Shamir & Zhang, 2013).

heading: 3.4 Discussion on three perturbation approaches.
text: 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 on the smooth and strongly convex coefficient. Smaller strongly convex coefficient leads to weaker contraction. The sensitivity of output perturbation algorithm is the upper bound on the largest possible final distance between two sets of parameters.
Objective perturbation (Chaudhuri et al., 2011; Kifer et al., 2012; Iyengar et al., 2019) perturbs the objective function before training. It requires the objective function to be strongly convex to guarantee 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 linear term. The sensitivity of objective perturbation is the maximum change of the minimizer that one record can produce. Chaudhuri et al. (2011) and Kifer et al. (2012) use the largest and the smallest eigenvalue (i.e. the smooth and strongly convex coefficient) of the objective’s Hessian matrix to upper bound such change.
In comparison, gradient perturbation is more flexible than output/objective perturbation. For example, to bound the sensitivity, gradient perturbation only requires Lipschitz coefficient which can be easily 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 softmax regression.
More critically, output/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 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. This explains why their utility guarantee depends on the worst curvature of the objective.

heading: 4 Experiment
text: In this section, we evaluate the performance of DP-GD and DP-SGD on multiple real world datasets. We use the benchmark datasets provided by Iyengar et al. (2019). Objective functions are logistic regression and softmax regression for binary and multi-class datasets, 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).
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 ( , δ)-DP. 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 as 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 {0.1, 1.0, 5.0} ({0.2, 2.0, 10.0} for high dimensional datasets). The learning rate of DP-SGD is twice as large as DP-GD and it is divided by 2 at the middle of training. Privacy parameter δ is set as 1n2 . The l2 regularization coefficient is set as 1 × 10
−4. All reported numbers are averaged over 20 runs.
Baseline algorithms. The baseline algorithms include state-of-the-art objective and output perturbation algorithms. For objective perturbation, we use Approximate Minima Perturbation (AMP) (Iyengar et al., 2019). For output perturbation, we use the algorithm in Wu et al. (2017) (Output perturbation SGD). We adopt the implementation and hyperparameters in Iyengar 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 = 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.

heading: 5 Conclusion
text: 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
1For multi-class datas sets MNIST and Covertype, we use the numbers reported in Iyengar et al. (2019) directly because of the long running time of AMP especially on multi-class datasets.
justifies the empirical superiority of gradient perturbation over other methods and advance the state of the art utility guarantee of 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.

heading: Appendix A Proofs Related to DP-GD and DP-SGD
text: Proof of Theorem 1. Let x1, . . . ,xt be the path generated by optimization procedure. Since xt contains Gaussian perturbation noise zt−1, Definition 3 gives us
Ezt−1 [〈xt − x∗,∇F (xt)〉] ≥ νtEzt−1 [‖xt − x∗‖ 2].
Since F is β-smooth, we have
〈xt − x∗,∇F (xt)〉 ≥ 1
β ‖∇F (xt)‖2 .
Take linear combination of above inequalities,
Ezt−1 [〈xt − x∗,∇F (xt)〉] ≥ θνtEzt−1 [‖xt − x∗‖ 2] + (1− θ) β Ezt−1 [‖∇F (xt)‖ 2]
≥ θνEzt−1 [‖xt − x∗‖ 2] + (1− θ) β Ezt−1 [‖∇F (xt)‖ 2].
(2)
Let rt = ‖xt − x∗‖ be the solution error at step t. We have the following inequalities between rt+1 and rt.
r2t+1 = ‖xt − η∇F (xt)− ηzt − x∗‖2 , = ‖xt − x∗‖2 − 2η〈∇F (xt) + zt,xt − x∗〉+ η2 ‖∇F (xt) + zt‖2 .
(3)
Take expectation with respect to zt, we have
Ezt [r 2 t+1] ≤ ‖xt − x∗‖2 − 2η〈∇F (xt) ,xt − x∗〉+ η2 ‖∇F (xt)‖2 + pη2σ2t . (4)
Further take expectation with respect to zt−1 and use Eq 2, we have
Ezt,zt−1 [r 2 t+1] ≤ Ezt−1 [‖xt − x∗‖ 2]− 2ηEzt−1 [〈∇F (xt) ,xt − x∗〉] + η 2Ezt−1 [‖∇F (xt)‖ 2] + pη2σ2t ,
≤ (1− 2 (1− θ) ην)Ezt−1 [r 2 t ] +
( η2 − 2ηθ
β
) Ezt−1 [‖∇F (xt)‖ 2] + pη2σ2t .
(5)
Set θ = 1 2 and η ≤ 1 β ,
Ezt,zt−1 [r 2 t+1] ≤ (1− ην)Ezt−1 [r 2 t ] + pη 2σ2t . (6)
Applying Eq (6) and taking expectation with respect to zt,zt−1, · · · ,z1 iteratively yields
E[r2t+1] ≤ (1− ην)t r21 + pη2 t∑ i=1 (1− ην)t−i σ2i . (7)
Uniform privacy budget allocation scheme sets
σ2t = Θ
( TL2 log(1/δ)
n2 2
) .
Therefore
E[r2T+1] ≤ (1− ην)T r21 + Θ ( pηTL2 log(1/δ)
νn2 2
) . (8)
Set T ≥ 2 log(n) ην , we have
(1− ην)T r21 = exp (
log(1− ην) log(n2) ην
) r21 = exp ( log(1/n2) 1
ην log(1 +
ην 1− ην ) ) r21,
≤ ( 1
n2
) 1 ην log(1+ ην 1−ην )
r21 < r21 n2 .
(9)
Last inequality holds because 1 ην log(1 + ην 1−ην ) > 1 for 1 ην ≥ β ν ≥ 1.
Therefore, for T ≥ 2 log(n) ην , we have the excepted solution error E[r2T+1] satisfies E[r2T+1] = O ( pηTL2 log(1/δ)
νn2 2
) . (10)
Since F (x) is β-smooth, we have
F (x)− F (x∗) ≤ β
2 ‖x− x∗‖2 . (11)
Using Eq (10) and Eq (11), we have the excepted excess risk satisfies E[F (xT+1)− F (x∗)] = O ( βpηTL2 log(1/δ)
νn2 2 ) for T ≥ 2 log(n)
ην . The utility bound is minimized when T = 2 log(n) ην .
Proof of Theorem 2. The smooth condition gives us,
F (xt+1) ≤ F (xt) + 〈∇F (xt),xt+1 − xt〉+ β
2 ‖xt+1 − xt‖2
= F (xt)− η〈∇F (xt),∇F (xt) + zt〉+ βη2
2 ‖∇F (xt) + zt‖2 .
(12)
Take expectation with respect to zt and substitute η = 1β ,
Ezt [F (xt+1)] = F (xt)− 1
2β ‖∇F (xt)‖2 +
1
2β pσ2t . (13)
Subtract F (x∗) on both sides and use convexity,
Ezt [F (xt+1)− F (x∗)] = F (xt)− F (x∗)− 1
2β ‖∇F (xt)‖2 +
1
2β pσ2t
≤ 〈∇F (xt),xt − x∗〉 − 1
2β ‖∇F (xt)‖2 +
1
2β pσ2t .
(14)
Substitute ∇F (xt) = β(xt − xt+1)− zt,
Ezt [F (xt+1)− F (x∗)] ≤ β〈xt − xt+1,xt − x∗〉 − 1
2β Ezt [‖β(xt − xt+1)− zt‖
2] + 1
2β pσ2t
= β〈xt − xt+1,xt − x∗〉 − β
2 ‖xt − xt+1‖2 − Ezt〈xt+1,zt〉
= β〈xt − xt+1,xt − x∗〉 − β
2 ‖xt − xt+1‖2 − Ezt〈xt − η∇F (xt)− ηzt,zt〉
= β〈xt − xt+1,xt − x∗〉 − β
2 ‖xt − xt+1‖2 +
1 β pσ2t
= β
2 (‖xt − x∗‖2 − ‖xt+1 − x∗‖2) +
1 β pσ2t .
(15)
Summing over t = 1, . . . , T and take expectation with respect to z1, . . . , zT , T∑ t=1 E[F (xt+1)− F (x∗)] ≤ β 2 ‖x1 − x∗‖2 + T∑ t=1 1 β pσ2t . (16)
Use convexity,
E[F (x̄)− F (x∗)] ≤ β
2T ‖x1 − x∗‖2 +
1 β pσ2
≤ β 2T ‖x1 − x∗‖2 + Θ
( L2pT log(1/δ)
βn2 2 ) (17) Choose T = nβ √
p , we have
E[F (x̄)− F (x∗)] = O
(√ pL2 log(1/δ)
n
) . (18)
Proof of Theorem 3 and 4. We start by giving a useful lemma.
Lemma 2. Choose ηt = 1νt , the expected solution error of xt in Algorithm 2 for any t > 1 satisfies
E[‖xt − x∗‖2] ≤ 2L2
( 1 + pσ2 ) tν2 ,
Proof of Lemma 2. We have
‖xt+1 − x∗‖2 = ‖xt − ηtgt − ηtzt − x∗‖2
= ‖xt − x∗‖2 − 2ηt〈xt − x∗, gt + zt〉+ η2t ‖gt‖2 − 2η2t 〈gt,zt〉+ η2t ‖zt‖2 . (19)
Take expectation with respect to perturbation noise zt and uniform sampling, we have
Ezt,it [‖xt+1 − x∗‖ 2] = Ezt,it [‖xt − ηtgt − ηtzt − x∗‖ 2]
≤ ‖xt − x∗‖2 − 2ηt〈xt − x∗,∇F (xt)〉+ η2tL2 + pη2tL2σ2. (20)
Further take expectation to zt−1 and apply Definition 3,
Ezt,zt−1,it [‖xt+1 − x∗‖ 2] ≤ (1− 2νtηt)Ezt−1 [‖xt − x∗‖ 2] + η2tL 2 (1 + pσ2)
≤ (1− 2νηt)Ezt−1 [‖xt − x∗‖ 2] + η2tL 2 (1 + pσ2) . (21) Now we use induction to conduct the proof. Substitute ηt = 1tν into Eq 21, we have Lemma 2 hold for t = 2.
Assume E[‖xt − x∗‖2] ≤ 2L2(1+pσ2)
tν2 holds for t > 2, then
E[‖xt+1 − x∗‖2] ≤ (
1− 2 t
) E[‖xt − x∗‖2] + L2 ( 1 + pσ2 ) ν2t2
≤ ( 1
t − 2 t2
) 2L2 ( 1 + pσ2 ) ν2 + L2 ( 1 + pσ2 ) ν2t2
=
( 2
t − 3 t2
) L2 ( 1 + pσ2 ) ν2 ≤ 2L2 ( 1 + pσ2 ) (t+ 1) ν2 .
(22)
It’s easy to check that Eq 20 holds for arbitrary x rather than x∗. Rearrange Eq 20 and take expectation, we have
E[〈xt − x,∇F (xt)〉] ≤ E[‖xt − x‖2]− E[‖xt+1 − x‖2] 2ηt + ηtL
2 ( 1 + pσ2 ) 2 . (23)
Let k be arbitrarily chosen from {1, . . . , bT/2c}. Summing over the last k + 1 iterations and use convexity to lower bound 〈xt − x,∇F (xt)〉 by F (xt)− F (x),
T∑ t=T−k E[F (xt)− F (x)] ≤ E[‖xT−k − x‖2] 2ηT−k + 1 2 T∑ t=T−k+1 E[‖xt − x‖2] ( 1 nt − 1 nt−1 )
− E[‖xT+1 − x‖ 2] 2ηT + L2 ( 1 + pσ2 ) 2 T∑ t=T−k ηt.
(24)
Substitute ηt = 1νt and follow the idea in Shamir & Zhang (2013) by choosing x = xT−k, we arrive at
T∑ t=T−k E[F (xt)− F (xT−k)] ≤ ν 2 T∑ t=T−k+1 E[‖xt − xT−k‖2] + L2 ( 1 + pσ2 ) 2ν T∑ t=T−k 1 t . (25)
Now we bound E[‖xt − xT−k‖2] for t ≥ T − k,
E[‖xt − xT−k‖2] ≤ 2E[‖xt − x∗‖2] + 2E[‖xT−k − x∗‖2]
≤ 4L2
( 1 + pσ2 ) ν2 ( 1 t + 1 T − k ) ≤ 8L2 ( 1 + pσ2 ) ν2 ( 1 T − k ) ≤ 16L2 ( 1 + pσ2 ) Tν2 .
(26)
Substitute Eq 26 into Eq 25,
T∑ t=T−k E[F (xt)− F (xT−k)] ≤ 8kL2
( 1 + pσ2 ) Tν + L2 ( 1 + pσ2 ) 2ν T∑ t=T−k 1 t . (27)
Let Sk = 1k+1 ∑T t=T−k E[F (xt)] be the averaged expected values of the last k + 1 iterations. We are interested in S0 − F (x∗) = E[F (xT )]− F (x∗). Now we derive an inequality between Sk and Sk−1. By definition,
kSk−1 = (k + 1)Sk − E[xT−k]. (28)
Rearrange Eq 27 to upper bound −E[xT−k],
Sk−1 = k + 1
k Sk − E[xT−k] k
≤ k + 1 k Sk − Sk k
+ 8L2
( 1 + pσ2 ) (k + 1)Tν + L2 ( 1 + pσ2 ) 2k (k + 1) ν T∑ t=T−k 1 t
≤ Sk + L2 ( 1 + pσ2 ) 2ν ( 16 kT +
1
k (k + 1) T∑ t=T−k 1 t
) .
(29)
Summing over k = 1, . . . , k = bT/2c,
S0 ≤ SbT/2c + L2 ( 1 + pσ2 ) 2ν bT/2c∑ k=1 16 kT + bT/2c∑ k=1 T∑ t=T−k
1
k (k + 1) t  . (30) Now we bound SbT/2c − F (x∗). Choose x = x∗ and ηt = 1tν in Eq 24 ,
T∑ t=dT/2e E[F (xt)− F (x∗)] = νdT/2eE[ ∥∥xdT/2e − x∗∥∥2] 2 + ν 2 T∑ t=dT/2e+1 E[‖xt − x∗‖2]
+ L2 ( 1 + pσ2 ) 2 T∑ t=dT/2e ηt
≤ L 2(1 + pσ2)
ν (1 + T∑ t=dT/2e+1 1 t + T∑ t=dT/2e 1 2t )
≤ L 2(1 + pσ2)
ν (1 +
3
2 T∑ t=dT/2e 1 t )
≤ 4L 2(1 + pσ2)
ν .
(31)
The second inequality uses Lemma 2. The last inequality holds because the fact that ∑T t=dT/2e 1 t ≤ log(2). Dividing Eq 31 by dT/2e,
SbT/2c − F (x∗) ≤ 8L2(1 + pσ2)
Tν . (32)
We have ∑bT/2c k=1 16 kT ≤ 16(1+log(T )) T because it is harmonic sequence. Lastly,
bT/2c∑ k=1 T∑ t=T−k
1 k (k + 1) t ≤ bT/2c∑ k=1 log(2) k(k + 1)
≤ bT/2c∑ k=1 log(2) k2 ≤ 2 log(2).
(33)
Plugging these bounds into Eq 30, we have S0 − F (x∗) = O ( (1 + pσ2)L2 log(T )
Tν
) . (34)
Choose σ2 = Θ ( Tlog(1/δ)
n2 2
) to guarantee ( , δ)-DP. Set T = n2 2, we have
S0 − F (x∗) = O ( pL2 log(n)log (1/δ)
n2 2ν
) . (35)
Set T = n √ p and assume p < n2, we have
S0 − F (x∗) = O
(√ pL2 log(n)
n ν
) . (36)

heading: Appendix B Detailed description on benchmark datasets

heading: Appendix C Comparison between Average and Minimum
text: In this section we plot the average and minimum curvatures in Figure 4 for another dataset KDDCup99. The objective function is still regularized logistic regression.
As shown in Figure 4, the average curvature is still larger than the minimum curvature (especially when the regularization term is 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.

Review summaries:
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.