Title: DP-LSSGD: AN OPTIMIZATION METHOD TO LIFT THE UTILITY IN PRIVACY-PRESERVING ERM

Abstract: Machine learning (ML) models trained by differentially private stochastic gradient descent (DP-SGD) have much lower utility than the non-private ones. To mitigate this degradation, we propose a DP Laplacian smoothing SGD (DP-LSSGD) to train ML models with differential privacy (DP) guarantees. At the core of DP-LSSGD is the Laplacian smoothing, which smooths out the Gaussian noise used in the Gaussian mechanism. Under the same amount of noise used in the Gaussian mechanism, DP-LSSGD attains the same DP guarantee, but in practice, DP-LSSGD makes training both convex and nonconvex ML models more stable and enables the trained models to generalize better. The proposed algorithm is simple to implement and the extra computational complexity and memory overhead compared with DP-SGD are negligible. DP-LSSGD is applicable to train a large variety of ML models, including DNNs.

1. INTRODUCTION:

Many released machine learning (ML) models are trained on sensitive data that are often crowdsourced or contain private information (Yuen et al., 2011; Feng et al., 2017; Liu et al., 2017) . With overparameterization, deep neural nets (DNNs) can memorize the private training data, and it is possible to recover them and break the privacy by attacking the released models (Shokri et al., 2017) . For example, Fredrikson et al. demonstrated that a model-inversion attack can recover training images from a facial recognition system (Fredrikson et al., 2015) . Protecting the private data is one of the most critical tasks in ML.

Differential privacy (DP) (Dwork et al., 2006 ) is a theoretically rigorous tool for designing algorithms on aggregated databases with a privacy guarantee. The idea is to add a certain amount of noise to randomize the output of a given algorithm such that the attackers cannot distinguish outputs of any two adjacent input datasets that differ in only one entry.

For repeated applications of additive noise based mechanisms, many tools have been invented to analyze the DP guarantee for the model obtained at the final stage. These include the basic and strong composition theorems and their refinements (Dwork et al., 2006; 2010; Kairouz et al., 2015) , the moments accountant (Abadi et al., 2016) , etc. Beyond the original notion of DP, there are also many other ways to define the privacy, e.g., local DP (Duchi et al., 2014) , concentrated/zeroconcentrated DP (Dwork & Rothblum, 2016; Bun & Steinke, 2016) , and Rényi-DP (RDP) (Mironov, 2017) .

Differentially private stochastic gradient descent (DP-SGD) reduces the utility of the trained models severely compared with SGD. As shown in Figure 1 , the training and validation losses of the logistic regression on the MNIST dataset increase rapidly when the DP guarantee becomes stronger. The convolutional neural net (CNN)1 trained by DP-SGD has much lower testing accuracy than the non-private one on the MNIST. We will discuss the detailed experimental settings in Section 4. A natural question raised from such performance degradations is:

Can we improve DP-SGD, with negligible extra computational complexity and memory cost, such that it can be used to train general ML models with improved utility? We answer the above question affirmatively by proposing differentially private Laplacian smoothing SGD (DP-LSSGD) to improve the utility in privacy-preserving empirical risk minimization (ERM). DP-LSSGD leverages the Laplacian smoothing (Osher et al., 2018) as a post-processing to smooth the injected Gaussian noise in the differentially private SGD (DP-SGD) to improve the convergence of DP-SGD in training ML models with DP guarantee.

1.1. OUR CONTRIBUTIONS:

The main contributions of our work are highlighted as follows:

• We propose DP-LSSGD and prove its privacy and utility guarantees for convex/nonconvex optimizations. We prove that under the same privacy budget, DP-LSSGD achieves better utility, excluding a small term that is usually dominated by the other terms, than DP-SGD by a factor that is much less than one for convex optimization. • We perform a large number of experiments logistic regression and CNN to verify the utility improvement by using DP-LSSGD. Numerical results show that DP-LSSGD remarkably reduces training and validation losses and improves the generalization of the trained private models.

In Table 1 , we compare the privacy and utility guarantees of DP-LSSGD and DP-SGD. For the utility, the notation Õ(•) hides the same constant and log factors for each bound. The constants d and n denote the dimension of the model's parameters and the number of training points, respectively. The numbers γ and β are positive constants that are strictly less than one, and D 0 , D σ , G are positive constants, which will be defined in Section 3. 

-SGD ( , δ) convex Õ √ (D 0 +G 2 )d ( n) optimality gap Bassily et al. (2014) DP-SGD ( , δ) nonconvex Õ √ d/( n) 2 -norm of gradient Zhang et al. (2017) DP-LSSGD ( , δ) convex Õ √ γ(Dσ +G 2 )d ( n) optimality gap This Work DP-LSSGD ( , δ) nonconvex Õ √ βd/( n) 1 2 -norm of gradient This Work

1 Measured in the norm induced by A -1 σ , we will discuss this in detail in Section 4.

1.2. RELATED WORK:

There is a massive volume of research over the past decade on designing algorithms for privacypreserving ML. Objective perturbation, output perturbation, and gradient perturbation are the three major approaches to perform ERM with a DP guarantee. Chaudhuri & Monteleoni (2008) ; Chaudhuri et al. (2011) considered both output and objective perturbations for privacy-preserving ERM, and gave theoretical guarantees for both privacy and utility for logistic regression and SVM. Song et al. (2013) numerically studied the effects of learning rate and batch size in DP-ERM. Wang et al. (2016) studied stability, learnability and other properties of DP-ERM. Lee & Kifer (2018) proposed an adaptive per-iteration privacy budget in concentrated DP gradient descent. Variance reduction techniques, e.g., SVRG, have also been introduced to DP-ERM (Wang et al., 2017) . The utility bound of DP-SGD has also been analyzed for both convex and nonconvex smooth objectives (Bassily et al., 2014; Zhang et al., 2017; Wang et al., 2019) . Jayaraman et al. (2018) analyzed the excess empirical risk of DP-ERM in a distributed setting. Besides ERM, many other ML models have been made differentially private. These include: clustering (Su et al., 2015; Y. Wang & Singh, 2015; Balcan et al., 2017) , matrix completion (Jain et al., 2018) , online learning (Jain et al., 2012) , sparse learning (Talwar et al., 2015; Wang & Gu, 2019) , and topic modeling (Park et al., 2016) . Gilbert & McMillan (2017) exploited the ill-conditionedness of inverse problems to design algorithms to release differentially private measurements of the physical system. Wang & Xu (2019) considered sparse linear regression in the local DP models. Shokri & Shmatikov (2015) proposed distributed selective SGD to train deep neural nets (DNNs) with a DP guarantee in a distributed system, however, the obtained privacy guarantee was very loose. Abadi et al. (2016) Laplacian smoothing (LS) can be regarded as a denoising technique that performs post-processing on the Gaussian noise injected stochastic gradient. Denoising has been used in the DP earlier: Postprocessing can enforce consistency of contingency table releases (Barak et al., 2007) and leads to accurate estimation of the degree distribution of private network (Hay et al., 2009) . Nikolov et al. (2013) showed that post-processing by projecting linear regression solutions, when the ground truth solution is sparse, to a given 1 -ball can remarkably reduce the estimation error. Bernstein et al. (2017) used Expectation-Maximization to denoise a class of graphical models' parameters. Balle & Wang (2018) showed that in the output perturbation based differentially private algorithm design, denoising dramatically improves the accuracy of the Gaussian mechanism in the high-dimensional regime. To the best of our knowledge, we are the first to design a denoising technique on the Gaussian noise injected gradient to improve the utility of the trained private ML models.

1.3. NOTATION:

We use boldface upper-case letters A, B to denote matrices and boldface lower-case letters x, y to denote vectors. For vectors x and y and positive definite matrix A, we use x 2 and x A to denote the 2 -norm and the induced norm by A, respectively; x, y denotes the inner product of x and y; and λ i (A) denotes the i-th largest eigenvalue of A. We denote the set of numbers from 1 to n by [n] . N (0, I d×d ) represents d-dimensional standard Gaussian.

1.4. ORGANIZATION:

This paper is organized in the following way: In Section 2, we introduce the DP-LSSGD algorithm.

In Section 3, we analyze the privacy and utility guarantees of DP-LSSGD for both convex and nonconvex optimizations. We numerically verify the efficiency of DP-LSSGD in Section 4. We conclude this work and point out some future directions in Section 5.

2. PROBLEM SETUP AND ALGORITHM:

2.1 LAPLACIAN SMOOTHING STOCHASTIC GRADIENT DESCENT (LSSGD)

In this paper, we consider empirical risk minimization problem as follows. Given a training set S = {(x 1 , y 1 ), . . . , (x n , y n )} drawn from some unknown but fixed distribution, we aim to find an empirical risk minimizer that minimizes the empirical risk as follows,

EQUATION

where F (w) is the empirical risk (a.k.a., training loss), f i (w) = (w; x i , y i ) is the loss function of a given ML model defined on the i-th training example (x i , y i ), and w ∈ R d is the model parameter we want to learn. Empirical risk minimization serves as the mathematical foundation for training many ML models that are mentioned above. The LSSGD (Osher et al., 2018) for solving (1) is given by

EQUATION

)

where η is the learning rate, ∇f i k denotes the stochastic gradient of F evaluated from the pair of input-output {x i k , y i k }, and B k is a random subset of size b from [n]. Let A σ = I -σL for σ ≥ 0 being a constant, where I ∈ R d×d and L ∈ R d×d are the identity and the discrete one-dimensional Laplacian matrix with periodic boundary condition, respectively. Therefore,

EQUATION

When σ = 0, LSSGD reduces to SGD.

Note that A σ is positive definite with condition number 1 + 4σ that is independent of A σ 's dimension, and LSSGD guarantees the same convergence rate as SGD in both convex and nonconvex optimization. Moreover, Laplacian smoothing (LS) can reduce the variance of SGD on-thefly, and lead to better generalization in training many ML models including DNNs (Osher et al., 2018) .

For v ∈ R d , let u := A -1 σ v, i.e., v = A σ u. Note A σ is a convolution matrix, therefore, v = A σ u = u -σd * u, where d = [-2, 1, 0, • • • , 0, 1]

T and * is the convolution operator. By the fast Fourier transform (FFT), we have

A -1 σ v = u = ifft (fft(v)/(1 -σ • fft(d)))

, where the division in the right hand side parentheses is performed in a coordinate wise way.

2.2. DP-LSSGD:

DP ERM aims to learn a DP model, w, for the problem (1). A common approach is injecting Gaussian noise into the stochastic gradient, and it resulting in the following DP-SGD

EQUATION

)

where n is the injected Gaussian noise for DP guarantee. Note that the LS matrix A -1 σ can remove the noise in v. If we assume v is the initial signal, then A -1 σ v can be regarded as performing an approximate diffusion step on the initial noisy signal which removes the noise from v. We will provide a detailed argument for the diffusion process in the appendix. As numerical illustrations, we consider the following two signals:

• 1D: v 1 = {sin(2iπ/100) + 0.1N (0, 1)|i = 1, 2, • • • , 100}. • 2D: v 2 = {sin(2iπ/100) sin(2jπ/100) + 0.2N (0, I 2×2 )|i, j = 1, 2, • • • , 100}.

We reshape v 2 into 1D with row-major ordering and then perform LS. Figure 2 shows that LS can remove noise efficiently. This noise removal property enables LSSGD to be more stable to the noise injected stochastic gradient, therefore improves training DP models with gradient perturbations.

We propose the following DP-LSSGD for solving (1) with DP guarantee

w k+1 = w k -ηA -1 σ 1 b i k ∈B k ∇f i k (w k ) + n .

(5)

In this scheme, we first inject the noise n to the stochastic gradient ∇f i k (w k ), and then apply the LS operator A -1 σ to denoise the noisy stochastic gradient, ∇f i k (w k ) + n, on-the-fly. We assume that each component function f i in (1) is G-Lipschitz. The DP-LSSGD for finite-sum optimization is summarized in Algorithm 1. Compared with LSSGD, the main difference of DP-LSSGD lies in injecting Gaussian noise into the stochastic gradient, before applying the Laplacian smoothing, to guarantee the DP. 

Algorithm 1 DP-LSSGD Input: f i (w) is G-Lipschitz for i = 1, 2, • • • , n.

w 0 : initial guess of w, ( , δ): the privacy budget, η: the step size, T : the total number of iterations.

Output: ( , δ)-differentially private classifier w priv .

for k = 0, 1, • • • , T -1 do w k+1 = w k -ηA -1 σ 1 b i k ∈B k ∇f i k (w k ) + n ,

where n ∼ N (0, ν 2 I) and ν is defined in Theorem 1, and

B k ⊂ [n]. return w T

3. MAIN THEORY:

In this section, we present the privacy and utility guarantees for DP-LSSGD. The technical proofs are provided in the appendix. Definition 1 (( , δ)-DP). (Dwork et al. (2006) ) A randomized mechanism M : S N → R satisfies ( , δ)-DP if for any two adjacent datasets S, S ∈ S N differing by one element, and any output subset O ⊆ R, it holds that

P[M(S) ∈ O] ≤ e • P[M(S ) ∈ O] + δ.

Theorem 1 (Privacy Guarantee). Suppose that each component function f i is G-Lipschitz. Given the total number of iterations T , for any δ > 0 and privacy budget 2 ≤ 5T log(1/δ)b 2 /n 2 , DP-LSSGD, with injected Gaussian noise N (0, ν 2 ) for each coordinate, satisfies ( , δ)-DP with ν 2 = 8T αG 2 /(n 2 ), where α = 2 log(1/δ)/ + 1. Remark 1. It is straightforward to show that the noise in Theorem 1 is in fact also tight to guarantee the ( , δ)-DP for DP-SGD.

For convex ERM, DP-LSSGD guarantees the following utility in terms of the gap between the ergodic average of the points along the DP-LSSGD path and the optimal solution w * . Theorem 2 (Utility Guarantee for convex optimization). Suppose F is convex and each component function

f i is G-Lipschitz. Given any 2 ≤ 5T log(1/δ)b 2 /n 2 and δ > 0, if we choose η k = 1/ √ T and T = (D σ + G 2 )n 2 2 / 24dG 2 log(1/δ) , where D σ = w 0 -w * 2

Aσ and w * is the global minimizer of F , the DP-LSSGD output w =

T -1 k=0 η k / T -1 i=0 η i w k satisfies the following utility E F ( w) -F (w * ) ≤ 2G 6γ(D σ + G 2 )d log(1/δ) n , where γ = 1/d d i=1 1/[1 + 2σ -2σ cos(2πi/d)]. Proposition 1. In Theorem 2, γ = 1+ω d (1-ω d ) √ 4σ+1 , where ω = 2σ+1- √ 4σ+1 2σ

< 1. That is, γ converge to 0 almost exponentially as the dimension, d, increases. Remark 2. In the above utility bound for convex optimization, for different σ (σ = 0 corresponds to DP-SGD), the only difference lies in the term γ(D σ + G 2 ). The first part γD σ depends on the gap between initialization w 0 and the optimal solution w * . The second part γG 2 decrease monotonically as σ increases. σ should be selected to get an optimal trade-off between these two parts. Based on our test on multi-class logistic regression for MNIST classification, σ = 0 always outperforms the case when σ = 0.

For nonconvex ERM, DP-LSSGD has the following utility bound measured in gradient norm. Theorem 3 (Utility Guarantee for nonconvex optimization). Suppose that F is nonconvex and each component function f i is G-Lipschitz and has L-Lipschitz continuous gradient. Given any 2 ≤ 5T log(1/δ)b 2 /n 2 and δ > 0, if we choose η = 1/ √ T and T = (D F + Lν 2 )n 2 2 / 12dLG 2 log(1/δ) , where D F = F (w 0 ) -F (w * ) with w * being the global minimum of F , then the DP-LSSGD output w = T -1 k=0 w k /T satisfies the following utility

E ∇F ( w) 2 A -1 σ ≤ 4 G 6βdL(2D F + LG 2 ) log(1/δ) n ,

where

β = 1/d d i=1 1/[1 + 2σ -2σ cos(2πi/d)] 2 . Proposition 2. In Theorem 3, β = 2ω 2d+1 -ξω 2d +2ξdω d -2ω+ξ σ 2 ξ 3 (1-ω d ) 2

, where ω = 2σ+1-

√ 4σ+1 2σ and ξ = - √ 1+4σ σ

. Therefore, β ∈ (0, 1).

It is worth noting that if we use the 2 -norm instead of the induced norm, we have the following utility guarantee

E ∇F ( w) 2 2 ≤ E ∇F ( w) 2 A -1 σ λ min (A -1 σ ) ≤ (1 + 4σ)E ∇F ( w) 2 A -1 σ ≤ 4ζ G 6dL(2D F + LG 2 ) log(1/δ) n where ζ = 1 d d i=1 (1+4σ) 2 (1+2σ-2σ cos(2πi/d)) 2 > 1.

In the 2 -norm, DP-LSSGD has a bigger utility upper bound than DP-SGD (set σ = 0 in ζ). However, this does not mean that DP-LSSGD has worse performance. To see this point, let us consider the following simple nonconvex function

EQUATION

For two points a 1 = (2, 0) and a 2 = (1, √ 3/2), the distance to the local minima a * = (0, 0) are 2 and √ 7/2, while ∇f (a 1 ) 2 = 1 and ∇f (a 2 ) 2 = √ 13/2. So a 2 is closer to the local minima a * than a 1 while its gradient has a larger 2 -norm.

4. EXPERIMENTS:

In this section, we verify the efficiency of DP-LSSGD in training multi-class logistic regression and CNNs for MNIST and CIFAR10 classification. We use v ← v/ max (1, v 2 /C) (Abadi et al., 2016) to clip the gradient 2 -norms of the CNNs to C. The gradient clipping guarantee the Lipschitz condition for the objective functions. We train all the models below with ( , 10 -5 )-DP guarantee for different . For Logistic regression we use the privacy budget given by Theorem 1, and for CNNs we use the privacy budget in the Tensorflow privacy (Andrew & et al., 2019) . We checked that these two privacy budgets are consistent.

4.1. LOGISTIC REGRESSION FOR MNIST CLASSIFICATION:

We ran 50 epochs of DP-LSSGD with learning rate scheduled as 1/t with t being the index of the iteration to train the 2 -regularized (regularization constant 10 -4 ) multi-class logistic regression. We split the training data into 50K/10K with batch size 128 for cross-validation. We plot the evolution of training and validation loss over iterations for privacy budgets (0.2, 10 -5 ) and (0.1, 10 -5 ) in Figure 3 . We see that the training loss curve of DP-SGD (σ = 0) is much higher and more oscillatory (log-scale on the y-axis) than that of DP-LSSGD (σ = 1, 3). Also, the validation loss of the model trained by DP-LSSGD decays faster and has a much smaller loss value than that of the model trained by DP-SGD. Moreover, when the privacy guarantee gets stronger, the utility improvement by DP-LSSGD becomes more significant.

Next, consider the testing accuracy of the multi-class logistic regression trained with ( , 10 -5 )-DP guarantee by DP-LSSGD includes σ = 0, i.e., DP-SGD. We list the test accuracy of logistic regression trained in different settings in Table 2 . These results reveal that DP-LSSGD with σ = 1, 2, 3 can improve the accuracy of the trained private model and also reduce the variance, especially when the privacy guarantee is very strong, e.g., (0.1, 10 -5 ). 

4.1.1. THE EFFECTS OF STEP SIZE:

We know that the step size in DP-SGD/DP-LSSGD may affect the accuracy of the trained private models. We try different step size scheduling of the form {a/t|a = 0.5, 1.0, 1.5, 2.0, 2.5, 3.0}, where t is again the index of iteration, and all the other hyper-parameters are used the same as before. Figure . 4 plots the test accuracy of the logistic regression model trained with different learning rate scheduling and different privacy budget. We see that the private logistic regression model trained by DP-LSSGD always outperforms DP-SGD.

4.2. CNN FOR MNIST AND CIFAR10 CLASSIFICATION:

In this subsection, we consider training a small CNN2 with DP-guarantee for MNIST classification. We implement DP-LSSGD and DP-LSAdam (Kingma & Ba, 2014) (simply replace the noisy gradient in DP-Adam in the Tensorflow privacy with the Laplacian smoothed surrogate) into the Tensorflow privacy framework (Andrew & et al., 2019) . We use the default learning rate 0.15 for DP-(LS)SGD and 0.001 for DP-(LS)Adam and decay them by a factor of 10 at the 10K-th iteration, norm clipping (1), batch size (256), and micro-batches (256). We vary the noise multiplier (NM), and larger NM guarantees stronger DP. As shown in Figure 5 , the privacy budget increases at exactly the same speed (dashed red line) for four optimization algorithms. When the NM is large, i.e., DP-guarantee is strong, DP-SGD performs very well in the initial period. However, after a few epochs, the validation accuracy gets highly oscillatory and decays. DP-LSSGD can mitigate the training instability issue of DP-SGD. DP-Adam outperforms DP-LSSGD, and DP-LSAdam can further improve validation accuracy on top of DP-Adam. 

5. CONCLUSIONS:

In this paper, we integrated Laplacian smoothing with DP-SGD for privacy-presrving ERM. The resulting algorithm is simple to implement and the extra computational cost compared with the DP-SGD is almost negligible. We show that DP-LSSGD can improve the utility of the trained private ML models both numerically and theoretically. It is straightforward to combine LS with other variance reduction technique, e.g., SVRG (Johoson & Zhang, 2013) .

α, log(1/δ)/(α-1)T -RDP provided that ν 2 ≥ 1/1.25, because τ = b/n. Let α = 2 log(1/δ)/ + 1, we obtain that Mk satisfies 2 log(1/δ)/ + 1, /(2T ) -RDP as long as we have

ν 2 ∆(q) 2 = T α(α -1)b 2 n 2 log(1/δ) = T 2 log(1/δ) + 2 log(1/δ)b 2 n 2 log(1/δ) 2 ≥ 1 1.25 .

Therefore, the following condition suffices

2 ≤ 5T b 2 log(1/δ) n 2 .

Therefore, according to Lemma 2, we have w k satisfies 2 log(1/δ)/ + 1, k /(2T ) -RDP. Finally, by Lemma 3, we have w k satisfies k /(2T ) + /2, δ -DP. Therefore, the output of DP-SGD, w, is ( , δ)-DP.

Remark 3. In the above proof, we used the following estimate of the 2 sensitivity

∆(q k ) = A -1 σ ∇f i (w k ) -A -1 σ ∇f i (w k ) 2 /n ≤ 2G/n. Indeed, let g = ∇f i (w k ) -∇f i (w k ) and d = A -1

σ g, then according to Osher et al. (2018) we have

d 2 + 2σ D + d 2 2 d + σ 2 Ld 2 2 d = g 2 ,

where d is the dimension of d, and

D + =      -1 1 0 . . . 0 0 0 -1 1 . . . 0 0 0 0 -1 . . . 0 0 . . . . . . . . . . . . . . . . . . 1 0 0 . . . 0 -1     

.

Moreover, if we assume the g is randomly sampled from a unit ball in a high dimensional space, then a high probability estimation of the compression ratio of the 2 norm can be derived from Lemma. 5.

Numerical experiments show that A -1 σ ∇f i (w k )-A -1 σ ∇f i (w k ) 2 is much less than ∇f i (w k )-∇f i (w k ) 2 , so for the above noise, it can give much stronger privacy guarantee.

A.2 UTILITY GUARANTEE -CONVEX OPTIMIZATION:

To prove the utility guarantee for convex optimization, we first show that the LS operator compresses the 2 norm of any given Gaussian random vector with a specific ratio in expectation. Lemma 4. Let x ∈ R d be the standard Gaussian random vector. Then

E x 2 A -1 σ = d i=1 1 1 + 2σ -2σ cos(2πi/d)

,

where x 2 A -1 σ . = x, A -1 σ

x is the square of the induced norm of x by the matrix A -1 σ .

Proof of Lemma 4. Let the eigenvalue decomposition of

A -1 σ be A -1 σ = UΛU T , where Λ is a diagonal matrix with Λ ii = 1 1+2σ-2σ cos(2πi/d) We have E x 2 A -1 σ = E[Tr(x UΛU x)] = d i=1 Λ ii = d i=1 1 1 + 2σ -2σ cos(2πi/d) = γ.

Proof of Theorem 2. Recall that we have the following update rule

w k+1 = w k - η k A -1 σ (∇f i k (w k ) + n)

, where i k are drawn uniformly from [n], and n ∼ N (0, ν 2 I). Observe that

w k+1 -w * 2 Aσ = w k -η k A -1 σ (∇f i k (w k ) + n) -w * 2 Aσ = w k -w * 2 Aσ + η 2 k A -1 σ ∇f i k (w k ) 2 Aσ + A -1 σ n 2 Aσ + 2 A -1 σ ∇f i k (w k ), n -2η k ∇f i k (w k ) + n, w k -w * .

Taking expectation with respect to i k and n given w k , we have

E w k+1 -w * 2 Aσ = E w k -w * 2 Aσ -2η k E ∇F (w k ), w k -w * + η 2 k E ∇f i k (w k ) 2 A -1 σ + η 2 k E n 2 A -1 σ ≤ E w k -w * 2 Aσ -2η k E F (w k ) -F (w * ) + η 2 k G 2 + γdν 2

, where the second inequality is due to the convexity of F , and Lemma 4. It implies that

2η k E F (w k ) -F (w * ) ≤ E w k -w * 2 Aσ -E w k+1 -w * 2 Aσ + η 2 k (G 2 + γdν 2

). Now taking the full expectation and summing up over T iterations, we have

T -1 k=0 2η k E F (w k ) -F (w * ) ≤ D σ + T -1 k=0 η 2 k (G 2 + γdν 2 ),

where

D σ = w 0 -w * 2 Aσ . Let v k = η k / T -1 k=0 η k , we have T -1 k=0 v k E F (w k ) -F (w * ) ≤ D σ + T -1 k=0 η 2 k (G 2 + γdν 2 ) 2 T -1 k=0 η k .

According to the definition of w and the convexity of F , we obtain

E F ( w) -F (w * ) ≤ D σ + T -1 k=0 η 2 k (G 2 + γdν 2 ) 2 T -1 k=0 η k ≤ D σ + T -1 k=0 η 2 k G 2 2 T -1 k=0 η k + T -1 k=0 η 2 k 2 T -1 k=0 η k • 24γdT G 2 log(1/δ) n 2 2 . Let η = 1/ √ T and T = (D σ + G 2 )n 2 2 / 24γdG 2 log(1/δ) , we can obtain that E F ( w) -F (w * ) ≤ 2G 6γ(D σ + G 2 )d log(1/δ) n .

A.3 UTILITY GUARANTEE -NONCONVEX OPTIMIZATION:

To prove the utility guarantee for nonconvex optimization, we need the following lemma, which shows that the LS operator compresses the 2 norms of any given Gaussian random vector with a specific ratio in expectation. Lemma 5. Let x ∈ R d be the standard Gaussian random vector. Then

E A -1 σ x 2 2 = d i=1 1 (1 + 2σ -2σ cos(2πi/d)) 2 . Proof of Lemma 5. Let the eigenvalue decomposition of A -1 σ be A -1 σ = UΛU T , where Λ is a diagonal matrix with Λ ii = 1 1+2σ-2σ cos(2πi/n) We have E A -1 σ x 2 2 = E[Tr(x UΛU UΛU x)] = E[Tr(x UΛ 2 U x)] = d i=1 Λ 2 ii = d i=1 1 (1 + 2σ -2σ cos(2πi/d)) 2 = β.

Proof of Theorem 3. Recall that we have the following update rule w t+1 = w kη k A -1 σ (∇f i k (w k ) + n), where i k are drawn uniformly from [n], and n ∼ N (0, ν 2 I). Since F is L-smooth, we have

F (w k+1 ) ≤ F (w k ) + ∇F (w k ), w k+1 -w k + L 2 w k+1 -w k 2 2 = F (w k ) -η k ∇F (w k ), A -1 σ (∇f i k (w k ) + n) + η 2 k L 2 A -1 σ ∇f i k (w k ) 2 2 + A -1 σ n 2 2 + 2 A -1 σ ∇f i k (w k ), A -1 σ n .

Taking expectation with respect to i k and n given w k , we have

EF (w k+1 ) ≤ EF (w k ) -η k E ∇F (w k ), A -1 σ ∇f i k (w k ) + η 2 k L 2 E A -1 σ ∇f i k (w k ) 2 2 + E A -1 σ n 2 2 ≤ EF (w k ) -η k 1 - η k L 2 E ∇F (w k ) 2 A -1 σ + η 2 k L 2 (G 2 + dβν 2 ) ≤ EF (w k ) - η k 2 E ∇F (w k ) 2 A -1 σ + η 2 k L(G 2 + dβν 2 ) 2 ,

where the second inequality uses Lemma 5 and the last inequality is due to 1 -η k L/2 > 1/2. Now taking the full expectation and summing up over T iterations, we have

EF (w T ) ≤ F (w 0 ) - T -1 k=1 η k 2 E ∇F (w k ) 2 A -1 σ + T -1 k=1 η 2 k L(G 2 + dβν 2 ) 2 .

If we choose fix step size, i.e., η k = η, and rearranging the above inequality, and using

F (w 0 ) - EF (w T ) ≤ F (w 0 ) -F (w * ), we get 1 T T -1 k=1 E ∇F (w k ) 2 A -1 σ ≤ 2 ηT F (w 0 ) -F (w * ) + ηL(G 2 + dβν 2 ), which implies that E ∇F ( w) 2 A -1 σ ≤ 2D F ηT + ηL(G 2 + dβν 2 ) ≤ 2D F ηT + ηL G 2 + 24dβT G 2 log(1/δ) n 2 2 . Let η = 1/ √ T and T = (2D F + LG 2 )n 2 2 / 24dLβG 2 log(1/δ) , where D F = F (w 0 ) -F (w * ), we obtain E ∇F ( w) 2 A -1 σ ≤ 4 G 6βdL(2D F + LG 2 ) log(1/δ) n .

B CALCULATIONS OF β AND γ

B.1 CALCULATION OF γ:

To prove Proposition 1, we need the following two lemmas. Lemma 6 (Residue Theorem). Let f (z) be a complex function defined on C, then the residue of f around the pole z = c can be computed by the formula

EQUATION

)

where the order of the pole c is n. Moreover,

EQUATION

where {c i } be the set of pole(s) of f (z) inside {z||z| < 1}.

The proof of Lemma 6 can be found in any complex analysis textbook.

Lemma 7. For 0 ≤ θ ≤ 2π, suppose

EQUATION

We compute (11) by using Residue theorem. First, note that because

F (θ) is real valued, f [k] = f [-k]

; therefore, it suffices to compute (11)) for nonnegative k. Set z = e iθ . Observe that cos(θ) = 0.5(z + 1/z) and dz = izdθ. Substituting in (11) and simplifying yields that

EQUATION

where the integral is taken around the unit circle, and

α ± = 2σ+1± √ 4σ+1 2σ

are the roots of quadratic -σz 2 + (2σ + 1)z -σ. Note that α -lies within the unit circle; whereas, α + lies outside of the unit circle. Therefore, because k is nonnegative, α -is the only singularity of the integrand in (12) within the unit circle. A straightforward application of the Residue Theorem, i.e., Lemma 6, yields that

f [k] = -α k - σ(α --α + ) = α k √ 4σ + 1 .

This completes the proof.

Proof of Proposition 1. First observe that we can re-write γ as

EQUATION

)

It remains to show that the above summation is equal to

1+α d (1-α d ) √

4σ+1 . This follows by lemmas 7 and standard sampling results in Fourier analysis (i.e. sampling θ at points {2πj/d} d-1 j=0 ). Nevertheless, we provide the details here for completeness: Observe that that the inverse discrete-time Fourier transform of

G(θ) = d-1 j=0 δ θ - 2πj d .

is given by g

[k] = d/2π if k divides d, 0 otherwise.

Furthermore, let

F (θ) = 1 1 + 2σ(1 -cos(θ))

, and use f [k] to denote its inverse discrete-time Fourier transform. Now,

1 d d-1 j=0 1 1 + 2σ(1 -cos( 2πj d )) = 1 d 2π 0 F (θ)G(θ) = 2π d DTFT -1 [F • G][0] = 2π d (DTFT -1 [F ] * DTFT -1 [G])[0] = 2π d ∞ r=-∞ f [-r]g[r] = 2π d ∞ =-∞ f [-d] d 2π = ∞ =-∞ f [-d].

The proof is completed by substituting the result of lemma 7 in the above sum and simplifying.

We list some typical values of γ in Table 1 . The proof of Proposition 2 is similar as the proof of Proposition 1. The only difference is that we need to compute . Therefore, we have

f [k] = 1 2π

β = 2α 2d+1 -ξα 2d + 2ξdα d -2α + ξ σ 2 ξ 3 (1 -α d ) 2 .

We list some typical values of β in Table 2 . where v 0 is the discretization of f (x), and v ∆t is the numerical solution of (15) at time ∆t. Therefore, we have v ∆t = (I -∆tL) -1 v 0 , which is the LS with σ = ∆t.

D CNN FOR CIFAR10 CLASSIFICATION:

In this section, we will show that LS can also improve the utility of the DP-CNN trained by DP-SGD and DP-Adam for CIFAR10 classification. We simply replace the CNN architecture used above for MNIST classification with the benchmark architecture in the Tensorflow tutorial3 for CIFAR10 classification. Also, we use the same set of parameters as that used for training DP-CNN for MNIST classification except we fixed the noise multiplier to be 2.0 and clip the gradient 2 norm to 3. As shown in Figure 7 , LS can significantly improve the validation accuracy of the model trained by DP-SGD and DP-Adam, and the DP guarantee for all these algorithms are the same (dashed line in Figure 7 ). 

:

github.com/tensorflow/privacy/blob/master/tutorials/mnist_dpsgd_ tutorial.py

github.com/tensorflow/privacy/blob/master/tutorials/mnist_dpsgd_ tutorial.py

github.com/tensorflow/models/tree/master/tutorials/image/cifar10

Figures and Tables:

Figure 1: Training (left) and validation (middle) losses of the logistic regression on the MNIST trained by DP-SGD with ( , δ = 10 -5 )-DP guarantee. (right): testing accuracy of a simple CNN on the MNIST trained by DP-SGD with ( , δ = 10 -5 )-DP guarantee.

Illustration of LS (σ = 10 for v 1 and σ = 100 for v 2 ). (a): 1D signal sampled uniformly from sin(x) for x ∈ [0, 2π]. (b), (c), (d): 2D original, noisy, and Laplacian Smoothed noisy signals sampled uniformly from sin(x) sin(y) for (x, y) ∈ [0, 2π] × [0, 2π].

Figure 3: Training and validation losses of the multi-class logistic regression by DP-LSSGD. (a) and (b): training and validation curves with (0.2, 10 -5 )-DP guarantee; (c) and (d): training and validation curves with (0.1, 10 -5 )-DP guarantee. (Average over 5 runs)

Figure 4: Accuracy of the logistic regression on MNIST when different learning rates are used to train the model. Left: (0.1, 10 -5 )-DP; Right: (0.2, 10 -5 )-DP.

Figure 5: Performance comparison (validation accuracy) between different DP optimization algorithms in training CNN for MNIST classification with a fixed δ = 10 -5 .

theorem, for k > 0 (note that f [-k] = f [k] ), we have f

t ∈ [0, +∞) u(x, 0) = f (x), x ∈ [0, 1] (15)If we apply the backward Euler in time and central finite difference in space to discretize the governing equation in (15), we get v ∆t -v 0 = ∆tLv ∆t ,

Figure 7: Performance comparison between different differentially private optimization algorithms in training CNN for CIFAR10 classification with a fixed δ = 10 -5 .

Utility and Differential Privacy Guarantees.

Table content: <table><tr><td>Algorithm</td><td>DP</td><td>Assumption</td><td>Utility</td><td>Measurement</td><td>Reference</td></tr><tr><td>DP</td><td/><td/><td/><td/><td/></tr></table>

Testing accuracy of the multi-class logistic regression trained by DP-LSSGD with ( , δ = 10 -5 )-DP guarantee and different LS parameter σ. Unit: %. (5 runs)

Table content: <table><tr><td/><td colspan="2">0.30</td><td/><td colspan="2">0.25</td><td/><td/><td>0.20</td><td/><td>0.15</td><td>0.10</td></tr><tr><td>σ = 0</td><td colspan="2">81.74 ± 0.96</td><td/><td colspan="7">81.45 ± 1.59 78.92 ± 1.14 77.03 ± 0.69 73.49 ± 1.60</td></tr><tr><td>σ = 1</td><td colspan="2">84.21 ± 0.51</td><td/><td colspan="7">83.27 ± 0.35 81.56 ± 0.79 79.46 ± 1.33 76.29 ± 0.53</td></tr><tr><td>σ = 2</td><td colspan="2">84.23 ± 0.65</td><td/><td colspan="7">83.65 ± 0.76 82.15 ± 0.59 80.77 ± 1.26 76.31 ± 0.93</td></tr><tr><td>σ = 3</td><td colspan="2">85.11 ± 0.45</td><td/><td colspan="7">82.97 ± 0.48 82.22 ± 0.28 80.81 ± 1.03 77.13 ± 0.77</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>0.85</td><td/><td/></tr><tr><td/><td/><td>0.8</td><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>Accuracy</td><td>0.7 0.75 0.65</td><td/><td/><td>&lt;=0 &lt;=1 &lt;=2</td><td>Accuracy</td><td>0.8 0.75</td><td/><td/><td>&lt;=0 &lt;=1 &lt;=2</td></tr><tr><td/><td/><td>0.6</td><td>1</td><td>2</td><td>&lt;=3</td><td>3</td><td>0.7</td><td>1</td><td>2</td><td>&lt;=3</td><td>3</td></tr><tr><td/><td/><td/><td colspan="2">Learning Rate</td><td/><td/><td/><td colspan="2">Learning Rate</td></tr></table>

The values of γ corresponding to some σ and d.

Table content: <table><tr><td>σ</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td>d = 1000</td><td>0.447</td><td>0.333</td><td>0.277</td><td>0.243</td><td>0.218</td></tr><tr><td>d = 10000</td><td>0.447</td><td>0.333</td><td>0.277</td><td>0.243</td><td>0.218</td></tr><tr><td>d = 100000</td><td>0.447</td><td>0.333</td><td>0.277</td><td>0.243</td><td>0.218</td></tr><tr><td colspan="2">B.2 CALCULATION OF β</td><td/><td/><td/><td/></tr></table>

The values of β corresponding to some σ and d. u(x, t) be a function defined on the space-time domain [0, 1] × [0, +∞), suppose it satisfies the following diffusion equation with the Neumann boundary condition

Table content: <table><tr><td>σ</td><td/><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td>d = 1000</td><td colspan="2">0.268</td><td>0.185</td><td>0.149</td><td>0.128</td><td>0.114</td></tr><tr><td>d = 10000</td><td colspan="2">0.268</td><td>0.185</td><td>0.149</td><td>0.128</td><td>0.114</td></tr><tr><td>d = 100000</td><td colspan="2">0.268</td><td>0.185</td><td>0.149</td><td>0.128</td><td>0.114</td></tr><tr><td colspan="6">C LAPLACIAN SMOOTHING AND DIFFUSION EQUATION</td></tr><tr><td/><td>  </td><td colspan="3">∂u ∂t = ∂ 2 u ∂x 2 , (x, t) ∈ [0, 1] × [0, +∞), ∂u(0,t)</td><td/></tr><tr><td/><td/><td>∂x</td><td/><td/><td/></tr><tr><td/><td> </td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposes an algorithm called DP-LSSGD, which can improve upon DPSGD in terms of utility with Laplacian smoothing. The authors provide convergence guarantee and experimental evaluations demonstrating the advantage of the proposed algorithm over DPSGD and DPAdam. The proposed method seems like a good method to have for improving the gradient-based DP learning algorithms. I have some more comments/questions: 1. It seems to me that the experiments mainly considers high privacy (epsilon < 1) regime. This might be a bit too strict in practice. Given that Figure 5 seems to suggest that the advantage of the proposed method is less significant in the higher epsilon regime (though still pretty low to me), I think the authors might consider comment more on this matter. Maybe adding a plot showing final accuracy vs. epsilon (for epsilon going all the way up to 5 or 10) can also help. 2. You mentioned that the accuracy of DPSGD decreases after some epoch. Can this possibly be fixed by a brief hyperparameter selection? I feel like experiments from related work don’t usually have such a problem. Maybe it would look fairer if the best parameter is used for everyone. Besides, since DPSGD seems to work better in the beginning, would you consider using DPSGD first and then change to DPLSSGD or increasing sigma gradually? 3. I’m not very familiar with the field but I guess there might be other existing denoising methods for SGD or other gradient descent method. If so, why did you pick the LSSGD algorithm and do you think other denoising methods can be equally helpful for DP training?