Private Stochastic Non-convex Optimization with Improved Utility Rates

1 Introduction

Many machine learning models have the underlying goal of minimizing the population loss of the form minω∈Rd FE(ω) := Ez∼Z[f(ω, z)], where f is a nonconvex loss function of the d-dimension variable ω, and z is data sample from the distribution Z. It is often known as the stochastic nonconvex optimization (SNCO) problem. In practice, SNCO is approached by solving the nonconvex empirical risk minimization (ERM) problemminω∈Rd FS(ω) := 1n ∑ni=1 f(ω, zi), where zi ∈ S for i = 1, ..., n are drawn from Z and S is the n-size training dataset.

∗Corresponding Author

The privacy breach of sensitive information contained by the data samples in the training dataset has become a growing concern. To provide rigorous privacy protection, differential privacy (DP) [Dwork et al., 2006] has become a standard technique in privacy-preserving SNCO and ERM training [Abadi et al., 2016], abbreviated as DP-SNCO and DP-ERM hereafter. DP works by injecting additional perturbation to the training process to hide in probability the presence or absence of any single data sample. For example, DP-SGD [Abadi et al., 2016], one of the most popular DP algorithms for deep learning, injects calibrated Gaussian noise to the stochastic gradient in each iteration. The DP perturbation inevitably degrades the utility of the private model compared to the nonprivate counterpart. Therefore, quantifying the utility of the DP-SNCO and DP-ERM becomes an important problem for understanding their capability and limitation, which will be the focus of this paper. The expected excess empirical risk (empirical risk for short) and expected excess population risk (population risk) are common utility measures for DP-ERM and DP-SNCO, respectively, which are summarized in the following definition.

Definition 1.1. (Utility measures and their relationship [Hardt et al., 2016]) The definitions of the expected excess population risk, expected excess empirical risk, along with testing error, and generalization error, as well as their relationship are presented as follows,

where ω∗S ∈ argminω FS(ωS) denotes a minimizer of the empirical risk FS, A denotes the randomized optimization algorithm, EA denotes the expectation with respect to A; and S denotes the training set randomly drawn from the population distribution Z, ES denotes the expectation with respect to S; EA,S denotes expectation with both randomness of A and S.

For the convex loss function, the empirical risk has been extensively studied [Bassily et al., 2014; Wang et al., 2017], while the population risk is much less. Very recently, [Bassily et al., 2019] improves the result in [Bassily et al., 2014] and shows that the population risk of DP stochastic convex optimization (DP-SCO) is the larger of the nonprivate population loss of order O( 1 √n ) and the optimal excess empirical

loss of order O( √d log(1/δ) nϵ ) under common assumptions. It indicates that it is possible for DP-SCO to obtain the same excess population risk as its nonprivate counterpart in most parameter regime. [Feldman et al., 2020] shows the same population loss performance with lower computational complexity. For the nonconvex loss function, despite their practical popularity and success in various applications, the theoretical understanding of the utility of the DP-ERM and DP-SNCO is much less, among which the results of the excess risks are even rare, especially for the population risk. There are some work that use different utility measures [Wang et al., 2017; Wang and Xu, 2019; Wang et al., 2019a; Wang et al., 2019b] (e.g., the gradient norm), which are not as meaningful as the excess risks, as pointed out by [Wang et al., 2019a]. To the best of our knowledge, [Wang et al., 2019a] is the only existing work that studies the population risk and [Wang et al., 2017; Wang et al., 2019a] are the only known results for the empirical risk, which are detailed as follows.

1.1 RelatedWorks and Gaps

Existing Excess Empirical Risk for Nonconvex Loss

For the Empirical risk, E-1) [Wang et al., 2019a] analyzes the DP gradient langevin dynamics (GLD) and obtains O( 1 nϵ2 + d log(n) ) for general nonconvex and smooth loss, under T → +∞ and log(n) ≥ d to be meaningful. In addition, they improve the excess empirical risk to C0(d) nτ ϵτ under the number of iterations T → +∞ for τ ∈ (0, 1) by a finer analysis of the same DP-GLD algorithm. E-2) With the additional assumption of the loss satisfying the Polyak-Łojasiewicz (PL) condition, [Wang et al., 2017] obtains O( d log2 (n) log(1/δ) n2 ϵ2 ) by analyzing the DP full gradient descent. E-3) Although [Wang et al., 2019a] shows that there exists algorithm that provides the ˜O( d nϵ ) excess empirical risk for general non-convex and smooth loss, which matches the rate under general convex setting, it is inapplicable in practice since it has an exponential computational complexity of O((1 + nd )dn).

Existing Excess Population Risk for Nonconvex Loss

For the Population risk, P-1) [Wang et al., 2019a] obtains O( 1 nϵ2 + d log(n) ) for general non-convex and smooth loss by analyzing DP-GLD. P-2) For two special non-convex losses of the generalized linear model [Foster et al., 2018] and the robust regression [Loh and Wainwright, 2015], [Wang et al., 2019a] obtains O( d 14 √nϵ ) population loss by analyzing the DP FrankWolfe algorithm, which can be improved to O( √log(nd) √nϵ ) if the constraint is the ℓ1 norm ball.

Gaps

In addition to the under-studied situation, there are some key limitations of the above existing work, which raise the following three gaps.

The first gap lies between the private algorithms analyzed in existing theory and the ones applied in practice. The algorithms analyzed above may not best suit large-scale machine learning problems nowadays, e.g., deep neural networks (DNN). In fact, these algorithms all require full gradient computation, which results in high per-iteration computation and poor scalability. In practice, SGD-based optimization algorithms are more popular in such large-scale problems. For example, DP-SGD has been offered by Tensorflow for private deep neural network training. For the convex case, it is possible to obtain the optimal excess risks by analyzing DP-SGD [Bassily et al., 2019]. It is unknown in theory how the DPSGD-based algorithms perform in terms of the excess risks under the nonconvex loss setting, despite its scalability and practical popularity.

The second gap lies in the SGD algorithm design differences between the private and nonprivate settings. For the nonprivate SGD, there are many popular algorithm designs that further improve its performance. For one example, it is popular for the nonprivate SGD to utilize the stagewise learning rate scheduling (also known as the geometric step decay learning rate) [Yuan et al., 2019; Ge et al., 2019; Davis et al., 2019; Zhao et al., 2020], which decreases the learning rate by a certain factor after certain iterations. Such stagewise stepsize scheduling has been popularly adopted in practice (e.g., offered by Tensorflow, PyTorch) and has recently been analyzed in theory [Yuan et al., 2019; Zhao et al., 2020; Davis et al., 2019; Chen et al., 2019], where O( 1 √n ) population risk [Yuan et al., 2019; Zhao et al., 2020] is obtained under well-conditioned nonconvexity assumptions known to be held by some of deep neural networks. However, all existing excess risks analysis of SGD/GD-based algorithms in both convex and nonconvex settings only analyzes the constant step-size setting. For another example, the momentum technique [Polyak, 1964] is also popular in nonprivate SGD for DNN training, but there is only a few private counterpart [Bu et al., 2019] providing merely empirical utility results under constant learning rate. It is unknown how the designs of the stagewise step-size and momentum affect the DP-SGD and whether it is possible to obtain improved excess risks in theory given these designs.

The third gap lies between the existing excess risks of the private algorithms and the ones for nonprivate algorithms. Under the high-dimensional setting of n = Θ(d) considered by [Bassily et al., 2019; Feldman et al., 2020], all existing private population risks (i.e., P-1,P-2) are worse than the nonprivate risks of O( 1 √n ) [Yuan et al., 2019; Zhao et al., 2020] obtained under well-conditioned nonconvexity assumptions. However, for the convex losses, the private population risk can match the nonprivate one in most parameter regimes [Bassily et al., 2019; Feldman et al., 2020]. For the empirical risks, although E-2 has achieved a smaller rate, it is still worse than the O( d log(1/δ) n2 ϵ2 ) rate achievable for strongly convex losses [Zhang et al., 2017]. It is unknown whether it is possible to improve the excess risks to match the nonprivate ones at least for well-conditioned nonconvexity problems.

1.2 Our Contributions

Overview

In this paper, we progress towards answering the open problem that for nonconvex loss, whether the private optimization has a chance to achieve the same excess population risk as the nonprivate optimization. We provide much improved rates of both the expected excess empirical and population risks for the non-convex loss compared to existing works. We theoretically analyze the DP-SGD with stagewise learning rate and momentum under the same assumptions used by nonprivate optimization [Yuan et al., 2019; Zhao et al., 2020; Ramezani-Kebrya et al., 2018]. We also conduct experiments on both shallow (2-layer convolution neural network [Lawrence et al., 1997]) and deep neural networks (residual net ResNet-20 [He et al., 2016]) for simple (MNIST [LeCun et al., 1998]) and complex (CIFAR-10 [Krizhevsky et al., 2009]) datasets, respectively.

Algorithm Design

We propose a Differentially Private stagewise SGD with Early Momentum (DpageEM). To close Gap 2, we consider 1) stagewise learning rate scheduling in DP-SGD, which decreases the learning rate by a factor after certain iterations; 2) the early momentum strategy [Ramezani-Kebrya et al., 2018], which switches the momentum on during the early iterations and switches it off for the later iterations in each stage. The early momentum not only facilitates the need to strike a trade-off between the training efficiency and generalization performance, but also includes the DP-SGD without momentum as a special case. Thus, our theoretical results obtained for DpageEM can be easily applied to DP-SGD.

Assumptions

We analyze its excess empirical and population risks under the same set of assumptions adopted by nonprivate optimization, which include common mild assumptions like Lipschitz smoothness and continuity in Assumption 2.1 & 2.2, together with the Polyak-Łojasiewicz (PL) condition in Assumption 2.4 and one point weakly quasi-convex Assumption 2.5. The latter two have been observed and proved for shallow and deep neural networks as detailed in Remark 1.

Excess Risks

To the best of our knowledge, our excess risks are the first known theoretical results for the momentum technique under the private setting, especially for nonconvex losses. Analyzing both excess risks is a nontrivial task. Neither the convergence nor the uniform stability is known for the stagewise early momentum SGD even without the private restriction. As a result, it requires us to develop the following two new results as the stepping stone towards the private excess risks: 1) We provide the convergence of DpageEM in Theorem 3.2, which is general enough to include the momentum always-on and always-off as special cases. 2) We provide the uniform stability result of DpageEM in Thoerem 3.3, which shows the tradeoff between the number of iterations of momentum-on and the generalization error. By neglecting the DP noise, these two results can be of independent interest for nonprivate stagewise early momentum SGD for DNN optimization.

We obtain O( d log(1/δ) n2 ϵ2 ) excess empirical risk for DpageEM with (ϵ, δ)-DP, which is the same order in the dependence of the training data size n and model dimension d with the strongly convex loss setting [Zhang et al., 2017]. However, our assumptions are much weaker than [Zhang et al., 2017] as discussed in Remark ??.

We obtain O(max{ d log(1/δ) n2 ϵ2 , 1 √n }) excess population risk, where the O( d log(1/δ) n2 ϵ2 ) term is the same as its private excess empirical risk and the O( 1 √n ) term matches the population risk of the nonprivate stagewise SGD [Yuan et al., 2019; Zhao et al., 2020]. Thus, it indicates that it is possible for the private SNCO to have the same rate of the population risk as the nonprivate SNCO in most parameter regimes in practice. In the same high-dimensional regime considered in [Bassily et al., 2019; Feldman et al., 2020] where n = Θ(d), our population risk is better than the O( d1/4 √nϵ ) = O( 1 n 14 ϵ 12 ) rate (i.e., P-2) in [Wang et al., 2019a], which is obtained for the specific generalized linear model [Foster et al., 2018] and robust regression [Loh and Wainwright, 2015] problems by the DP Frank-Wolfe algorithm that is not popular for DNN.

2 Preliminaries

2.1 Stochastic Nonconvex Optimization

To show that private optimization has the same order of utility with nonprivate optimization, we invoke the same set of assumptions for both by following [Yuan et al., 2019; Zhao et al., 2020; Ramezani-Kebrya et al., 2018]. For the nonconvex loss function f(ω, z), we assume it is bounded and without loss of generality, |f(ω, z)| ≤ 1. We also make the following common assumptions.

Assumption 2.1. (Lipschitz continuous) f(ω, z) is LLipschitz continuous in ω for any z, i.e., ∀ω,ω′ ∈ Rd , we have |f (ω, z) - f (ω′ , z)| ≤ L‖ω - ω′ ‖2.

Assumption 2.2. (Lipschitz smoothness) f(ω, z) is βLipschitz smooth in ω for any z, ∀ω,ω′ ∈ Rd , we have ‖∇f (ω, z) - ∇f (ω′ , z)‖2 ≤ β‖ω - ω′ ‖2.

Assumption 2.3. (Bounded variance) The variance of the stochastic gradient is bounded, i.e., Ei[‖∇f(ω, zi) - ∇FS(ω)‖22 ] ≤ σ2 , for any ω.

In addition, the loss function is well-conditioned nonconvex as depicted by the following two assumptions.

Assumption 2.4. (Polyak-Łojasiewicz (PL) condition) FS(ω) satisfies µ-Polyak-Łojasiewicz (PL) condition, i.e., 2µ(FS(ω) - minω FS(ω)) ≤ ‖∇FS(ω)‖22 .

Assumption 2.5. (One point weakly quasi-convex) FS(ω) is one point θ-weakly quasi convex, i.e., for any ω, 〈∇FS(ω),ω - ω∗S 〉 ≥ θ(FS(ω) - FS(ω∗S )), where ω∗S is the optimal solution.

Remark 1. (Consistency of the assumptions with some deep neural networks) Both assumptions are satisfied with some deep learning losses. For the PL condition, it has been empirically observed or theoretically proved for shallow (e.g., two-layer) and deep neural networks (DNN) [Hardt and Ma, 2017]. In fact, throughout the paper, the assumption only needs to hold locally instead of in the entire space. That is, [Allen-Zhu et al., 2019] shows that this relaxed local PL condition holds for two-layer and deep overparameterized neural networks in a ball that contains the global optimum and centers around a random initial solution. For the one point weakly quasi-convex assumption, [Yuan et al., 2019] shows that it is satisfied by some deep neural networks (e.g., ResNet [He et al., 2016]) together with the PL condition. As for the range of the parameters, we consider µ ≪ 1 (i.e., ill-conditioned) and θ ≈ 1 which are consistent with the empirical observations about DNN [Yuan et al., 2019].

2.2 Differential Privacy

Definition 2.1. (Neighboring datasets) Let the data universe be Z and S, S′ be two datasets of n observed data samples drawn from Z with distribution Pz. Then, S and S′ are called neighboring datasets if they differ in exactly one data sample.

Definition 2.2. (Differential privacy) A randomized algorithmA is (ϵ, δ)-differentially private, if for all neighboring datasets S, S′ , and for any events O in the output range of A, we have P[A(S) ∈ O] ≤ eϵ · P[A(S′ ) ∈ O] + δ, where the probability is over the random coins of A.

Definition 2.3. (Gaussian mechanism) Given a query q : Z n → Rd , the Gaussian mechanism is defined as: M(S, q) = q(S) + ξ, where ξ is drawn from Gaussian distribution N (0, π2 Id).

Theorem 2.1. ([Abadi et al., 2016]) For an L-Lipschitz continuous loss function f, there exists constants c1 and c2 so that given the sampling probability q = Bn and the number of total iterations T, for any ϵ < c1q2T, a stochastic gradientbased algorithm with batch size B and stochastic gradient injected with noise from Gaussian mechanism with standard deviation Lπ, is (ϵ, δ)-differentially private for any δ > 0 if π ≥ c2 q√T log(1/δ) ϵ .

2.3 Stability and Generalization

The uniform stability is a well-known technique exploited to study the generalization performance of the SGD algorithms [Hardt et al., 2016].

Definition 2.4. (Uniform stability) A randomized algorithm A is called to satisfy α-uniform stability, if for any neighboring datasets S, S′ ∈ Z n the following holds,

Theorem 2.2. (Generalization error by uniform stability, Theorem 2.2 in [Hardt et al., 2016]) If an algorithm A : Z n → W satisfies α-uniform stability with respect to loss f : W × Z → R, its generalization error is bounded by α:

Algorithm 1 DPageEM

Input: Dataset S = {z1, ..., zn}, step-size series {ηk }, number of inner iterations {T k }, number of iterations with momentum on {tkMon }, momentum parameter ϱ, DP noise

parameter π, batch size B, initialization ω0 ; 1: for k = 1, ...,K do 2: ωk = DP-EMSGD(FS,ωk-1 ,ωk-1 , ηk , T k , tkMon , ϱ); 3: end for Output: ωK ;

Algorithm 2 DP-EMSGD(FS, ω0, ω-1, η, T, tMon, ϱ)

• 1: for t = 1, ..., T do
• 2: Draw mini-batch with index It ∈ {n} uniformly random, where |It| = B;
• 3: DrawDP noise ξt ∼N(0, π2 Id);
• 4: ωt+1 = ωt -η( 1B ∑i∈It ∇f (ωt, zi) + ξt) + ϱt(ωt - ωt-1), where ϱt = ϱ · True(t ∈ {1, . . . , tMon});
• 5: end for

Output: ωO randomly sampled from ω1, ..., ωT ;

3 DP Stagewise EarlyMomentum SGDwith Step Decay Step-size

3.1 AlgorithmDescription

Algorithm 1 presents the DP-SGD with stagewise learning rate and early momentum (DpageEM), which runs T k inner iterations under the learning rate ηk at stage k and iterates for K outer iterations. Within each stage k, we use the DP early momentum SGD (Algorithm 2), which switches the momentum on for iterations t = 1, ..., tkMon by setting the momentum parameter ϱt = ϱ, and switches the momentum off for iterations t = tkMon +1, ..., T k by setting ϱt = 0 (Mon is short for Momentum on).

3.2 AlgorithmAnalysis

Privacy Analysis

The following theorem provides the privacy guarantee of Algorithm 1, which follows 1) the moments accountant analysis in Theorem 3.1 from [Abadi et al., 2016]; and 2) the privacy amplification result in [Balle et al., 2018] that the amplification ratio is the same under the uniform sampling without replacement and under the Poisson sampling when Bn = q.

Theorem 3.1. (Differential privacy of Algorithm 1) Suppose Assumptions 2.1 and 2.2 hold. There exist some constants c1, c2 > 0 such that given the sampling ratio Bn and the number of total iterations ∑Kk=1 T k , for any ϵ < c1( Bn )2 ∑Kk=1 T k , Algorithm 1 is (ϵ, δ)-differentially private for any δ > 0 under the choice of

Remark 2. We emphasize that the privacy design and DP analysis are not the main tasks of this paper, so we follow this widely accepted DP technique in deep learning. It enables a direct comparison with the existing works on excess risks [Wang et al., 2019a] which also utilize moments accountant for DP analysis. It is possible to use more advanced DP analysis for a tighter privacy amplification result derived for the uniform sampling without replacement in [Wang et al., 2019c], as well as tighter privacy composition, e.g., the Gaussian DP [Dong et al., 2019] used in [Bu et al., 2019].

Excess Empirical Risk

In the following, we provide the excess empirical risk and excess population risk results of DpageEM. To obtain the excess risks, we analyze the convergence and uniform stability of the SGD with early momentum. As the early momentum has not been analyzed with stagewise step-size before, both results are new and the analysis is also nontrivial even without the DP consideration. The detailed proof (and all proofs for the remaining results) can be found in Supplement 1 .

We first analyze the excess empirical risk of DpageEM, which has better rate than existing ones (E-1 to E-3).

Theorem 3.2. (Excess empirical risk) Suppose Assumptions 2.1-2.5 hold. By setting π in eq.(4), ηk = ( 12 )k η0 , T k = (2)k T 0 , tkMon = (2)k t0Mon , where η0 ≤ max{ θ(1-ϱ)2 2β , 1} and η0 ((T 0 - t0Mon ) + 1 2(1-ϱ) t0Mon ) = 1 c4θµ for some 0 < c4 < 2 (which gives η0 (T 0 - t0Mon + t0Mon 1 2(1-ϱ) ) > 1 2θµ ), in Algorithm 1, with Γ = 1 4θµη0 1 (T 0-t0Mon )+ t0Mon 2(1-ϱ) < 12 ,

By setting K = Ω(log( n2 ϵ2 θ2 µ dL2 log(1/δ) )), we obtain the excess empirical risk: E[FS(ωK ) -FS(ω∗S)] ≤ O( dL2 log(1/δ) θ2µn2ϵ2 ).

Remark 3. The above theorem shows that the excess empirical risk of DpageEM is O( d log (1/δ) n2 ϵ2 ), which matches the result in [Zhang et al., 2017]. However, we obtain it under assumptions of weak quasi-convexity and PL-conditions, which are much weaker than their strongly convex assumption. Compared with nonconvex settings under different utility measures and different assumptions, our result is also much better. It indicates that it is possible to achieve good excess empirical risk by the practical step-size scheduling.

Remark 4. By the generality of the analysis, the above result also implies that the two special cases, i.e., stagewise DP-SGD with momentum always on and always off, also have the same order of excess empirical risk. Thus, our result can also be flexibly applied to DP-SGD with stagewise learning rate.

Excess Population Risk

In this part, we provide the excess population risk of DpageEM. We utilize the uniform stability technique to obtain the generalization error (i.e., Thm.2.2) [Hardt et al., 2016]. The following Theorem 3.3 presents the α-uniform stability of DpageEM, which is nontrivial because it not only deals with the additional DP noise, but also extends the stability result from the constant step-size SGD with early momentum [Ramezani-Kebrya et al., 2018] to the stagewise setting with step decay step-size scheduling. Although the momentum technique has been considered in the stagewise setting [Chen et al., 2019; Zhao et al., 2020], they only provide the convergence result, while we also study the stability, generalization and population risk. To the best of our knowledge, this is the first uniform stability and generalization result for the momentum SGD with stagewise step-size.

1 https://www.dropbox.com/sh/ldtrfa3ihx51dkz/ AADWQD1qvNEeiLFYgRn5I30ba?dl=0

Theorem 3.3. (α-Uniform stability) With the same assumptions and parameter settings as in Theorem 3.2, Algorithm 1 is α-uniformly stable with

Remark 5. Theorem 3.3 reflects the tradeoff between the stability, generalization performance, excess population risk against the training efficiency. According the first term in Theorem 3.3, α increases when tKMon becomes larger, i.e., the stability of the algorithm gets worse when the momentum switches on for more iterations. By Theorem 2.2, the generalization performance is negatively affected by the momentum, which further implies that the population risk will be larger.

Theorem 3.4. (Excess population risk) Under the same assumptions and parameter setting as in Theorem 3.2, we have the excess population risk of Algorithm 1,

Remark 6. The above theorem shows that the excess population risk of DpageEM is the larger one between the excess empirical risk of DpageEM and the excess population risk of the nonprivate stagewise SGD. Thus, we have shown that DPSGD-based method is able to match the nonprivate population risk in most parameter regimes for the nonconvex losses with the same assumptions with the nonprivate algorithms. This result greatly improves the O( log(1/δ) nϵ2 + d log(n) ) in P-1 which is for general nonconvex loss and obtained by DP-GLD with constant step-size and full gradient descent. It also improves over the O( (d log(1/δ)) 14 √nϵ ) and O( √log(nd) √nϵ ) in P-2, which are obtained for the special nonconvex generalized linear model [Foster et al., 2018] and nonconvex robust regression [Loh and Wainwright, 2015] by the DP Frank-Wolfe algorithm.

4 Numerical Experiments

4.1 Experiments Setup

Datasets andModels We conduct experiments on two real datasets: MNIST and CIFAR-10. For the simpler MNIST dataset, we consider a shallow convolution neural network (2-layer CNN); For the more complex CIFAR-10 dataset, we use a deeper neural network of ResNet-20. ELU activation function is used. The assumptions made for theoretical analysis are (approximately) satisfied by the empirical settings [Yuan et al., 2019]. The experiment details and additional experiment results can be found in Supplement.

Compared Methods We compare the proposed methods: DPageEM with momentum always off (DPageS) and DP early momentum SGD with stagewise learning rate (DpageEM) with the following methods: 1) nonprivate SGD with stagewise learning rate (nonpri-SGD-stage); 2) DP-SGD with constant learning rate (DP-SGD-const); 3) DP-SGD with linear decayed learning rate with respect to the training iteration t (DP-SGD-c/t); 4) DP-SGD with polynomial decayed learning rate with respect to the square root of the training iteration (DP-SGD-c/√t); 5) DP momentum SGD with constant learning rate (DP-SGDM-const); 6) DP early momentum SGD with constant learning rate (DP-SGDEM-const).

4.2 Experiments Results and Discussions

We plot the training and testing accuracy versus the number of iterations for all algorithms under different privacy parameters ϵ in Figure 1-2. The key observations and discussions are summarized as follows:

1. DPageS achieves the best training and testing accuracy among the private algorithms in all experiment settings, which indicates that stagewise learning rate indeed improves the training performance. Thus, this empirical observation corroborates the improved excess empirical and population risks.
2. DpageEM has better accuracy than DP-SGDM-const and DP-SGDEM-const in all experiment settings. Also, DPSGDM-const performs the worst compared to the early momentum methods. The early momentum methods perform worse than DP-SGD without any momentum. Thus, it indicates that momentum trades the utility for efficiency and early

Figure 2: Training/Testing accuracy of ResNet-20 on CIFAR-10. ϵ = 10.

momentum can help make an explicit trade-off by adjusting the ratio of the momentum-on iterations.

3) The performance gap between private and nonprivate models corresponding to the training and testing accuracy is smaller for shallow neural networks (2-layer CNN) applied to simpler dataset (MNIST), while becoming larger for deeper neural networks (ResNet-20) applied to more complex dataset (CIFAR-10). It indicates opportunities of future improvements for DP optimization targeted at deeper neural networks.

5 Conclusion

In this paper, we studied the expected empirical and population risks of nonconvex DP-ERM and DP-SNCO by designing and analyzing DP-SGD-based algorithms. In order to reduce the gap between the nonprivate algorithms with designs popular in practice and the private algorithms analyzed in theory, we introduced and analyzed the DP-SGD with the stagewise stepsize and momentum designs. Under the same assumptions that are observed and proved for nonprivate nonconvex learning, the proposed algorithm is able to reach improved excess risks over existing results and the excess population risk can match the nonprivate setting. Experiments on both shallow and deep neural networks when respectively applied to simple and complex datasets corroborate the theoretical results. In the future, we will study the excess risks for other types of nonconvex optimization algorithms and under more general assumptions, e.g., nonsmooth loss function.

Acknowledgements

This work is partially supported by the NSF under CNS1952192, IIS-1838200, and NIH under R01GM118609 and CTSA Award UL1TR002378.