Year: 2020

Abstract:
Protecting privacy in learning while maintaining the model performance has become increasingly critical in many applications that involve sensitive data. Private Gradient Descent (PGD) is a commonly used private learning framework, which noises gradients based on the Differential Privacy protocol. Recent studies show that dynamic privacy schedules of decreasing noise magnitudes can improve loss at the final iteration, and yet theoretical understandings of the effectiveness of such schedules and their connections to optimization algorithms remain limited. In this paper, we provide comprehensive analysis of noise influence in dynamic privacy schedules to answer these critical questions. We first present a dynamic noise schedule minimizing the utility upper bound of PGD, and show how the noise influence from each optimization step collectively impacts utility of the final model. Our study also reveals how impacts from dynamic noise influence change when momentum is used. We empirically show the connection exists for general non-convex losses, and the influence is greatly impacted by the loss curvature.

heading: 1 INTRODUCTION
text: In the era of big data, privacy protection in machine learning systems is becoming a crucial topic as increasing personal data involved in training models (Dwork et al., 2020) and the presence of malicious attackers (Shokri et al., 2017; Fredrikson et al., 2015). In response to the growing demand, differential-private (DP) machine learning (Dwork et al., 2006) provides a computational framework for privacy protection and has been widely studied in various settings, including both convex and non-convex optimization (Wang et al., 2017; 2019; Jain et al., 2019).
One widely used procedure for privacy-preserving learning is the (Differentially) Private Gradient Descent (PGD) (Bassily et al., 2014; Abadi et al., 2016). A typical gradient descent procedure updates its model by the gradients of losses evaluated on the training data. When the data is sensitive, the gradients should be privatized to prevent excess privacy leakage. The PGD privatizes a gradient by adding controlled noise. As such, the models from PGD is expected to have a lower utility as compared to those from unprotected algorithms. In the cases where strict privacy control is exercised, or equivalently, a tight privacy budget, accumulating effects from highly-noised gradients may lead to unacceptable model performance. It is thus critical to design effective privatization procedures for PGD to maintain a great balance between utility and privacy.
Recent years witnessed a promising privatization direction that studies how to dynamically adjust the privacy-protecting noise during the learning process, i.e., dynamic privacy schedules, to boost utility under a specific privacy budget. One example is (Lee & Kifer, 2018), which reduced the noise magnitude when the loss does not decrease, due to the observation that the gradients become very small when approaching convergence, and a static noise scale will overwhelm these gradients. Another example is (Yu et al., 2019), which periodically decreased the magnitude following a predefined strategy, e.g., exponential decaying or step decaying. Both approaches confirmed the empirically advantages of decreasing noise magnitudes. Intuitively, the dynamic mechanism may coordinate with certain properties of the learning task, e.g., training data and loss surface. Yet there is no theoretical analysis available and two important questions remain unanswered: 1) What is the form of utility-preferred noise schedules? 2) When and to what extent such schedules improve utility?
To answer these questions, in this paper we develop a principled approach to construct dynamic schedules and quantify their utility bounds in different learning algorithms. Our contributions
are summarized as follows. 1) For the class of loss functions satisfying the Polyak-Lojasiewicz condition (Polyak, 1963), we show that a dynamic schedule improving the utility upper bound is shaped by the influence of per-iteration noise on the final loss. As the influence is tightly connected to the loss curvature, the advantage of using dynamic schedule depends on the loss function consequently. 2) Beyond gradient descent, our results show the gradient methods with momentum implicitly introduce a dynamic schedule and result in an improved utility bound. 3) We empirically validate our results on convex and non-convex (no need to satisfy the PL condition) loss functions. Our results suggest that the preferred dynamic schedule admits the exponentially decaying form, and works better when learning with high-curvature loss functions. Moreover, dynamic schedules give more utility under stricter privacy conditions (e.g., smaller sample size and less privacy budget).

heading: 2 RELATED WORK
text: Differentially Private Learning. Differential privacy (DP) characterizes the chance of an algorithm output (e.g., a learned model) to leak private information in its training data when the output distribution is known. Since outputs of many learning algorithms have undetermined distributions, the probability of their privacy leakages is hard to measure. A common approach to tackle this issue is to inject randomness with known probability distribution to privatize the learning procedures. Classical methods include output perturbation (Chaudhuri et al., 2011), objective perturbation (Chaudhuri et al., 2011) and gradient perturbation (Abadi et al., 2016; Bassily et al., 2014; Wu et al., 2017). Among these approaches, the Private Gradient Descent (PGD) has attracted extensive attention in recent years because it can be flexibly integrated with variants of gradient-based iteration methods, e.g., stochastic gradient descent, momentum methods (Qian, 1999), and Adam (Kingma & Ba, 2014), for both convex and non-convex problems.
Dynamic Policies for Privacy Protection. Wang et al. (2017) studied the empirical risk minimization using dynamic variation reduction of perturbed gradients. They showed that the utility upper bound can be achieved by gradient methods under uniform noise parameters. Instead of enhancing the gradients, Yu et al. (2019); Lee & Kifer (2018) showed the benefits of using a dynamic schedule of privacy parameters or equivalently noise scales. In addition, adaptive sensitivity control (Pichapati et al., 2019; Thakkar et al., 2019) and dynamic batch sizes (Feldman et al., 2020) are also demonstrated to improves the convergence.
Utility Upper Bounds. A utility upper bound is a critical metric for privacy schedules that characterizes the maximum utility that a schedule can deliver in theory. Wang et al. (2017) is the first to prove the utility bound under the PL condition. In this paper, we improve the upper bound by a more accurate estimation of the dynamic influence of step noise. Remarkably, by introducing a dynamic schedule, we further boost the sample-efficiency of the upper bound. With a similar intuition, Feldman et al. (2020) proposed to gradually increase the batch size, which reduces the dependence
on sample size accordingly. Recently, Zhou et al. proved the utility bound by using the momentum of gradients (Polyak, 1964; Kingma & Ba, 2014). Table 1 summarizes the upper bounds of methods studied in this paper (in the last block of rows) and results from state-of-the-art algorithms based on private gradients. Our work shows that considering the dynamic influence can lead to a tighter bound.

heading: 3 PRIVATE GRADIENT DESCENT
text: Notations. We consider a learning task by empirical risk minimization (ERM) f(θ) = 1 N ∑N n=1 f(θ;xn) on a private dataset {xn}Nn=1 and θ ∈ RD. The gradient methods are defined as
θt+1 = θt − ηt∇t, where ∇t = ∇f(θt) = 1N ∑ n∇f(θt;xn) denotes the non-private gradient at iteration t, ηt is the step learning rate. ∇(n)t = ∇f(θt;xn) denotes the gradient on a sample xn. Ic denotes the indicator function that returns 1 if the condition c holds, otherwise 0.
Assumptions. (1) In this paper, we assume f(θ) is continuous and differentiable. Many commonly used loss functions satisfy this assumption, e.g., the logistic function. (2) For a learning task, only finite amount of privacy cost is allowed where the maximum cost is called privacy budget and denoted as R. (3) Generally, we assume that loss functions f(θ;x) (sample-wise loss) are G-Lipschitz continuous and f(θ) (the empirical loss) is M -smooth. Definition 3.1 (G-Lipschitz continuity). A function f(·) is G-Lipschitz continuous if, for G > 0 and all x, y in the domain of f(·), f(·) satisfies ‖f(y)− f(x)‖ ≤ G‖y − x‖2. . Definition 3.2 (m-strongly convexity). A function f(·) is m-strongly convex if f(y) ≥ f(x) + ∇f(x)T (y − x) + m2 ‖y − x‖
2, for some m > 0 and all x, y in the domain of f(·). Definition 3.3 (M -smoothness). A function is M -smooth w.r.t. l2 norm if f(y) ≤ f(x) + ∇f(x)T (y − x) + M2 ‖y − x‖ 2, for some constant M > 0 and all x, y in the domain of f(·).
For a private algorithmM(d) which maps a dataset d to some output, the privacy cost is measured by the bound of the output difference on the adjacent datasets. Adjacent datasets are defined to be datasets that only differ in one sample. In this paper, we use the zero-Concentrated Differential Privacy (zCDP, see Definition 3.4) as the privacy measurement, because it provides the simplicity and possibility of adaptively composing privacy costs at each iteration. Various privacy metrics are discussed or reviewed in (Desfontaines & Pejó, 2019). A notable example is Moment Accoutant (MA) (Abadi et al., 2016), which adopts similar principle for composing privacy costs while is less tight for a smaller privacy budget. We note that alternative metrics can be adapted to our study without major impacts to the analysis. Definition 3.4 (ρ-zCDP (Bun & Steinke, 2016)). Let ρ > 0. A randomized algorithmM : Dn → R satisfies ρ-zCDP if, for all adjacent datasets d, d′ ∈ Dn, Dα(M(d)‖M(d′)) ≤ ρα, ∀α ∈ (1,∞) where Dα(·‖·) denotes the Rényi divergence (Rényi, 1961) of order α.
zCDP provides a linear composition of privacy costs of sub-route algorithms. When the input vector is privatized by injecting Gaussian noise of N (0, σ2t I) for the t-th iteration, the composed privacy cost is proportional to ∑ t ρt where the step cost is ρt =
1 σ2t . For simplicity, we absorb the constant coefficient into the (residual) privacy budget R. The formal theorems for the privacy cost computation of composition and Gaussian noising is included in Lemmas B.1 and B.2.
Generally, we define the Private Gradient Descent (PGD) method as iterations for t = 1 . . . T : θt+1 = θt − ηtφt = θt − ηt(∇t + σtGνt/N), (1)
where φt = gt is the gradient privatized from ∇t as shown in Algorithm 1, G/N is the bound of sensitivity of the gathered gradient excluding one sample gradient, and νt ∼ N (0, I) is a vector element-wisely subject to Gaussian distribution. We use σt to denote the noise scale at step t and use σ to collectively represents the schedule (σ1, . . . , σT ) if not confusing. When the Lipschitz constant is unknown, we can control the upper bound by scaling the gradient if it is over some constant. The scaling operation is often called clipping in literatures since it clips the gradient norm at a threshold. After the gradient is noised, we apply a modification, φ(·), to enhance its utility. In this paper, we consider two types of φ(·):
φ(mt, gt) = gt (GD), φ(mt, gt) = [β(1− βt−1)mt + (1− β)gt]/(1− βt) (Momentum)
We now show that the PGD using Algorithm 1 guarantees a privacy cost less than R:
Algorithm 1 Privatizing Gradients
Input: Raw gradients [∇(1)t , . . . ,∇ (n) t ] (n = N by default), vt, residual privacy budget Rt assuming the full budget is R and R1 = R.
1: ρt ← 1/σ2t ,∇t ← 1n ∑n i=1∇ (i) t . Budget request 2: if ρt < Rt then 3: Rt+1 ← Rt − ρt 4: gt ← ∇t +Gσtνt/N , νt ∼ N (0, I) . Privacy noise 5: mt+1 ← φ(mt, gt) or g1 if t = 1 6: return ηtmt+1, Rt+1 . Utility projection 7: else 8: Terminate
Theorem 3.1. Suppose f(θ;x) is G-Lipschitz continuous and the PGD algorithm with privatized gradients defined by Algorithm 1, stops at step T . The PGD algorithm outputs θT and satisfies ρ-zCDP where ρ ≤ 12R.
Note that Theorem 3.1 allows σt to be different throughout iterations. Next we present a principled approach for deriving dynamic schedules optimized for the final loss f(θT ).

heading: 4 DYNAMIC POLICIES BY MINIMIZING UTILITY UPPER BOUNDS
text: To characterize the utility of the PGD, we adopt the Expected Excess Risk (EER), which notion is widely used for analyzing the convergence of random algorithms, e.g., (Bassily et al., 2014; Wang et al., 2017). Due to the presence of the noise and the limitation of learning iterations, optimization using private gradients is expected to reach a point with a higher loss (i.e., excess risk) as compared to the optimal solution without private protection. Define θ∗ = arg minθ f(θ), after Algorithm 1 is iterated for T times in total, the EER gives the expected utility degradation:
EER = Eν [f(θT+1)]− f(θ∗).
Due to the variety of loss function and complexity of recursive iterations, an exact EER with noise is intractable for most functions. Instead, we study the worst case scenario, i.e., the upper bound of the EER, and our goal is to minimize the upper bound. For consistency, we call the upper bound of EER divided by the initial error as ERUB. Since the analytical form of EER is either intractable or complicated due to the recursive iterations of noise, studying the ERUB is a convenient and tractable alternative. The upper bound often has convenient functional forms which are (1) sufficiently simple, such that we can directly minimize it, and (2) closely related to the landscape of the objective depending on both the training dataset and the loss function. As a consequence, it is also used in previous PGD literature (Pichapati et al., 2019; Wang et al., 2017) for choosing proper parameters. Moreover, we let ERUBmin be the achievable optimal upper bound by a specific choice of parameters, e.g., the σ and T .
In this paper, we consider the class of loss functions satisfying the Polyak-Lojasiewicz (PL) condition which bounds losses by corresponding gradient norms. It is more general than the m-strongly convexity. If f is differentiable and M -smooth, then m-strongly convexity implies the PL condition.
Definition 4.1 (Polyak-Lojasiewicz condition (Polyak, 1963)). For f(θ), there exists µ > 0 and for every θ, ‖∇f(θ)‖2 ≥ 2µ(f(θ)− f(θ∗)).
The PL condition helps us to reveal how the influence of step noise propagates to the final excess error, i.e., EER. Though the assumption was also used previously in Wang et al. (2017); Zhou et al. (2020), neither did they discuss the propagated influence of noise. In the following sections, we will show how the influence can tighten the upper bound in gradient descent and its momentum variant.

heading: 4.1 GRADIENT DESCENT METHODS
text: For the brevity of our discussion, we first define the following constants: 1
α ,
2RMN2
DG2 (f(θ1)− f(θ∗)), κ ,
M µ , and γ , 1− 1 κ , (2)
which satisfy κ ≥ 1 and γ ∈ [0, 1). Note that κ is the condition number of f(·) if f(·) is strongly convex. κ tends to be large if the function is sensitive to small differences in inputs, and 1/α tends to be large if more samples are provided and with a less strict privacy budget. The convergence of PGD under the PL condition has been studied for private (Wang et al., 2017) and non-private (Karimi et al., 2016; Nesterov & Polyak, 2006; Reddi et al., 2016) ERM. Below we extend the bound in (Wang et al., 2017) by considering dynamic influence of noise and relax σt to be dynamic: Theorem 4.1. Let α, κ and γ be defined in Eq. (2), and ηt = 1M . Suppose f(θ;xi) is G-Lipschitz and f(θ) is M -smooth satisfying the Polyak-Lojasiewicz condition. For PGD, the following holds:
ERUB = γT +R ∑T
t=1 qtσ
2 t , where qt , γ T−tα. (3)
In Eq. (3), the step noise magnitude σ2t has an exponential influence, qt, on the EER. The dynamic characteristic of the influence is the key to prove a tighter bound. Plus, on the presence of the dynamic influence, it is natural to choose a dynamic σ2t . When relaxing qt to a static 1, a static σ 2 t was studied by Wang et al. They proved a bound which is nearly optimal except a ln2N factor. To get the optimal bound, in the following sections, we look for the σ and T that minimize the upper bound.

heading: 4.1.1 UNIFORM SCHEDULE
text: The uniform setting of σt has been previously studied in Wang et al. (2017). Here, we show that the bound can be further tightened by considering the dynamic influence of iterations and a proper T . Theorem 4.2. Suppose conditions in Theorem 4.1 are satisfied. When σ2t = T/R, let α, γ and κ be defined in Eq. (2) and let T be:
T = ⌈ O ( κ ln ( 1 + 1
κα
))⌉ . (4)
Meanwhile, if κ ≥ 11−c > 1, 1/α > 1/α0 for some constant c ∈ (0, 1) and α0 > 0, the corresponding bound is:
ERUBuniformmin = Θ
( κ2
κ+ 1/α ln
( 1 + 1
κα
)) . (5)
Sketch of proof. The key of proof is to find a proper T to minimize ERUB = E = γT + ∑T
t=1 γT−tαRσ2 = γT + αT
1− γT
1− γ = γT + ακ(1− γT )T
where we use σt = √ T/R. Vanishing its gradient is to solve γT ln γ+ακ(1−γT )−ακTγT ln γ = 0, which however is intractable. In (Wang et al., 2017), T is chosen to be O(ln(1/α)) and ERUB is relaxed as γT + ακT 2. The approximation results in a less tight bound as O(α(1 + κ ln2(1/α))) which explodes as κ→∞. We observe that for a super sharp loss function, i.e., a large κ, any minor perturbation may result in tremendously fluctuating loss values. In this case, not-stepping-forward will be a good choice. Thus, we choose T = 1ln(1/γ) ln ( 1 + ln(1/γ)α ) ≤ O ( κ ln ( 1 + 1κα )) which converges to 0 as κ → +∞. The full proof is deferred to the appendix.

heading: 4.1.2 DYNAMIC SCHEDULE
text: A dynamic schedule can improve the upper bound delivered by the uniform schedule. First, we observe that the excess risk in Eq. (3) is upper bounded by two terms: the first term characterizes the error due to the finite iterations of gradient descents; the second term, a weighted sum, comes from error propagated from noise at each iteration. Now we show for any {qt|qt > 0, t = 1, . . . , T} (not limited to the qt defined in Eq. (3)), there is a unique σt minimizing the weighted sum:
Lemma 4.1 (Dynamic schedule). Suppose σt satisfy ∑T t=1 σ
−2 = R. Given a positive sequence {qt}, the following equation holds:
min σ R ∑T t=1 qtσ 2 t = (∑T t=1 √ qt )2 , when σ2t = 1 R ∑T i=1 √ qi qt . (6)
Remarkably, the difference between the minimum and T ∑T t=1 qt (uniform σt) monotonically in-
creases by the variance of √ qt w.r.t. t.
We see that the dynamics in σt come from the non-uniform nature of the weight qt. Since qt presents the impact of the σt on the final error, we denote it as influence. Given the dynamic schedule in Eq. (6), it is of our interest to which extent the ERUB can be improved. First, we present Theorem 4.3 to show the optimal T and ERUB. Theorem 4.3. Suppose conditions in Theorem 4.1 are satisfied. Let α, κ and γ be defined in Eq. (2). When ηt = 1M , σt (based on Eqs. (3) and (6)) and the T minimizing ERUB are, i.e.,
σ2t = 1
R √ (1/γ)T − 1 1−√γ √ γt, T = ⌈( 2κ ln ( 1 + 1 κα ))⌉ . (7)
Meanwhile, when κ ≥ 1 and 1/α ≥ 1/α0 for some positive constant α0, the minimal bound is:
ERUBdynamicmin = Θ
( κ2
κ2 + 1/α
) . (8)

heading: 4.1.3 DISCUSSION
text: In Theorems 4.2 and 4.3, we present the tightest bounds for functions satisfying the PL condition, to our best knowledge. We further analyze the advantages of our bounds from two aspects: sample efficiency and robustness to sharp losses.
Sample efficiency. Since dataset cannot be infinitely large, it is critical to know how accurate the model can be trained privately with a limited number of samples. Formally, it is of interest to study when κ is fixed and N is large enough such that α 1. Then we have the upper bound in Eq. (5) as
ERUBuniformmin ≤ O ( κ2α ln ( 1
κα
)) ≤ Õ ( DG2 ln(N)
MN2R
) , (9)
where we ignore κ and other logarithmic constants with Õ as done in Wang et al. (2017). As a result, we get a bound very similar to (Wang et al., 2017), except that R is replaced by RMA = 2/ ln(1/δ) using Moment Accountant. In comparison, based on Lemma B.3, R = 2ρ = 2 + 4 ln(1/δ) + 4 √ ln(1/δ)( + ln(1/δ) if θT satisfies ρ-zCDP. Because ln(1/δ) > 1, it is easy to see R = RzCDP > RMA when ≤ 2 ln(1/δ). As compared to the one reported in (Wang et al., 2017), our bound saved a factor of lnN and thus is require less sample to achieve the same accuracy. Remarkably, the saving is due to the maintaining of the influence terms as shown in the proof of Theorem 4.2.
Using the dynamic schedule, we have ERUBdynamicmin ≤ O(α) = O ( DG2 MN2R ) , which saved another lnN factor in comparison to the one using the uniform schedule Eq. (9). As shown in Table 1, such advantage maintains when comparing with other baselines.
Robustness. Besides sample efficiency, we are also interested in robustness of the convergence under the presence of privacy noise. Because of the privacy noise, the convergence of private gradient descent will be unable to reach an ideal spot. Specifically, when the samples are noisy or have noisy labels, the loss curvature may be sharp. The sharpness also implies lower smoothness, i.e., a small M or has a very small PL parameter. Thus, gradients may change tremendously at some steps especially in the presence of privacy noise. As illustrated in the left figure, the highly-curved loss function (the green curve) results in mean higher final loss (the red dashed line) than the flatten curve (purple and blue lines). Such changes have more critical impact when only a less number of iterations can be executed due to the privacy constraint. Assume α is some constant while κ 1/α, we immediately get:
ERUBuniformmin = Θ
( κ ln ( 1 + 1
κα
)) = Θ ( 1
α
) ≤ O ( MN2R
DG2
) , ERUBdynamicmin = Θ(1).
Both are robust, but the dynamic schedule has a smaller factor since 1/α could be a large number. In addition, the factor implies that when more samples are used, the dynamic schedule is robuster.
4.2 GRADIENT DESCENT METHODS WITH MOMENTUM
Section 4.1 shows that the step noise has an exponentially increasing influence on the final loss, and therefore a decreasing noise magnitude improves the utility upper bound by a lnN factor. However, the proper schedule can be hard to find when the curvature information, e.g., κ, is absent. A parameterized method that less depends on the curvature information is preferred. On the other hand, long-term iterations will result in forgetting of the initial iterations, since accumulated noise overwhelmed the propagated information from the beginning. This effect will reduce the efficiency of the recursive learning frameworks.
Alternative to GD, the momentum method can mitigate the two issues. It was originally proposed to stabilize the gradient estimation (Polyak, 1964). In this section, we show that momentum (agnostic about the curvature) can flatten the dynamic influence and improve the utility upper bound. Previously, Pichapati et al. used the momentum as an estimation of gradient mean, without discussions of
convergence improvements. Zhou et al. gave a bound for the Adam with DP. However, the derivation is based on gradient norm, which results in a looser bound (see Table 1).
The momentum method stabilizes gradients by moving average history coordinate values and thus greatly reduces the variance. The φ(mt, gt) can be rewritten as:
mt+1 = φ(mt, gt) = vt+1
1− βt , vt+1 = βvt + (1− β)gt = (1− β) ∑t i=1 βt−igt, v1 = 0, (10)
where β ∈ [0, 1]. Note vt+1 is a biased estimation of the gradient expectation while mt+1 is unbiased. Theorem 4.4 (Convergence under PL condition). Suppose f(θ;xi) is G-Lipschitz, and f(θ) is M - smooth and satisfies the Polyak-Lojasiewicz condition. Assume β 6= γ and β ∈ (0, 1). Let ηt = η02M and η0 ≤ 8 (√ 1 + 64βγ(γ − β)−2(1− β)−3 + 1 )−1 . Then the following holds:
EER ≤ ( γT + 2Rη0α U3(σ, T )︸ ︷︷ ︸
noise varinace
) (f(θ1)− f(θ∗))− ζ
η0 2M ∑T t=1
γT−tE ‖vt+1‖2︸ ︷︷ ︸ momentum effect
(11)
where γ = 1− η0 κ , ζ = 1− 1 β(1− β)3 η20 − 1 4 η0 ≥ 0, (12)
U3 = ∑T
t=1 γT−t
(1− β)2 (1− βt)2 ∑t i=1 β2(t−i)σ2i . (13)
The upper bound includes three parts that influence the bound differently: (1) Convergence. The convergence term is mainly determined by η0 and κ. η0 should be in (0, κ) such that the upper bound can converge. A large η0 will be preferred to speed up convergence if it does not make the rest two terms worse. (2) Noise Variance. The second term compressed in U3 is the effect of the averaged noise, ∑t i=1 β
2(t−i)σ2i . One difference introduced by the momentum is the factor (1− β)/(1− βt) which is less than γt at the beginning and converges to a non-zero constant 1− β. Therefore, in U3, γT−t(1− β)/(1− βt) will be constantly less than γT meanwhile. Furthermore, when t > T̂ , the moving average ∑t i=1 β
2(t−i)σ2i smooths the influence of each σt. In Appendix D, we will see that the influence dynamics is less steep than that of GD. (3) Momentum Effect. The momentum effect term can improve the upper bound when η0 is small. For example, when β = 0.9 and γ = 0.99, then η0 ≤ 0.98/M which is a rational value. Following the analysis, when M is large which means the gradient norms will significantly fluctuate, the momentum term may take the lead. Adjusting the noise scale in this case may be less useful for improving utility.
To give an insight on the effect of dynamic schedule, we provide the following utility bounds.
Theorem 4.5 (Uniform schedule). Suppose the assumptions in Theorem 4.4 are satisfied. Let σ2t = T/R, and let:
T̂ = max t s.t. γt−1 ≥ 1− β 1− βt , T =
⌈ O ( κ η0 ln ( 1 + η0 κα ))⌉ .
Given some positive constant c and α0 > 0 with 1/α > 1/α0, the following inequality holds: ERUBmin ≤ O ( κ2
κ+ η0/α
[ IT≤T̂ + γ T̂−1 ln ( 1 + η0 κα ) IT>T̂ ]) .
Theorem 4.6 (Dynamic schedule). Suppose the assumptions in Theorem 4.4 are satisfied. Let α′ = 2η0αγ(1−γβ2) , β < γ and T̂ = max t s.t. γ t−1 ≥ 1−β1−βt . Use the following schedule:
σ2t = 1
R ∑T i=1 √ qi qt , T dyn = ⌈ O ( 2κ η0 ln ( 1 + η0 κα ))⌉ ,
where qt = c1γT+tIT≤T̂ + γ T̂−1c2γ T−tIT>T̂ for some positive constants c1 and c2. The following inequality holds:
ERUB ≤ γT + 2η0α ∑T
t=1 Rqtσ
2 t , ERUBmin ≤ O
( κα
κα+ η0
( κα
κα+ η0 IT≤T̂ + IT>T̂
)) .
Discussion. Theoretically, the dynamic schedule is more influential in vanilla gradient descent methods than the momentum variant. The result is mainly attributed to the averaging operation. The moving averaging, (1 − β) ∑t i=1 β
t−igi/(1 − βt), increase the influence of the under-presented initial steps and decrease the one of the over-sensitive last steps. Counterintuitively, the preferred dynamic schedule should be increasing since qt decreases when t ≤ T̂ .

heading: 4.3 PRIVATE STOCHASTIC GRADIENT DESCENT (NEW SECTION ON REBUTTAL)
text: Though PGD provides a guarantee both for utility and privacy, computing gradients of the whole dataset is impractical for large-scale problems. For this sake, studying the convergence of Private Stochastic Gradient Descent (PSGD) is meaningful. The Algorithm 1 can be easily extended to PSGD by subsampling n gradients where the batch size n N . According to (Yu et al., 2019), when privacy is measured by zCDP, there are two ways to account for the privacy cost of PSGD depending on the batch-sampling method: sub-sampling with or without replacement. In this paper, we focus on the random subsampling with replacement since it is widely used in deep learning in literature, e.g., (Abadi et al., 2016; Feldman et al., 2020). Accordingly, we replace N in the definition of α by n because the term is from the sensitivity of batch data (see Eq. (1)). For clarity, we assume that T is the number of iterations rather than epochs and that ∇̃t is mean stochastic gradient. When a batch of data are randomly sampled, the privacy cost of one iteration is cp2/σt where c is some constant, p = n/N is the sample rate, and 1/σ2t is the full-batch privacy cost. Details of the sub-sampling theorems are referred to the Theorem 3 of (Yu et al., 2019) and their empirical setting. Threfore, we can replace the privacy constraint ∑ t p 2/σ2t = R by ∑ t 1/σ 2 t = R
′ where R′ = R/p2 = N 2
n2 R. Remarkably, we omit the constant c because it will not affect the results regarding uniform or dynamic schedules. Notice N2R in the α is replaced by n2R′ = N2R. Thus, the form of α is not changed which provides convenience for the following derivations.
Now we study the utility bound of PSGD. To quantify the randomness of batch sampling, we define a random vector ξt with E[ξt] = 0 and E ‖ξt‖2 ≤ D such that ∇̃t ≤ ∇t + σgξt/n for some positive constant σg. Because ξt has similar property to the privacy noise νt, we can easily extend the PGD bounds to PSGD bounds by following theories. Theorem 4.7 (Utility bounds of PSGD). Let α, κ and γ be defined in Eq. (2), and ηt = 1M . Suppose f(θ;xi) is G-Lipschitz and f(θ) is M -smooth satisfying the Polyak-Lojasiewicz condition. For PSGD, when batch size satisfies n = max{N √ R, 1}, the following holds:
ERUB = γT + αgσ 2 g +R
′ ∑T
t=1 qtσ
2 t , where qt , γ T−tα, ∑ t 1/σ2t = R ′. (14)
where αg = D2µN2R(f(θ1)−f(θ∗)) .
Theorem 4.8 (PSGD with momentum). Let αg = D2µN2R(f(θ1)−f(θ∗)) . Suppose assumptions in Theorem 4.4 holds. When batch size satisfies n = max{N √ R, 1}, the U3(σ, T ) has to be replaced by Ũ3 = U g 3 + U3, with αR
′Ug3 ≤ αgσ2g (15) when PSGD is used.
As shown above, the utility bound of PSGD differs from the PGD merely by αgσ2g . Note αg = O( DN2R ) which fits the order of dynamic-schedule bounds. In addition, α and other variables are not changed. Hence, the conclusions w.r.t. the dynamic/uniform schedules maintain the same.

heading: 5 EXPERIMENTS
text: We empirically validate the properties of privacy schedules and their connections to learning algorithms. In this section, we briefly review the schedule behavior on quadratic losses under varying data sensitivity. Details of experimental setups and empirical results are available in Appendix D.
We first show the estimated influence of step noise qt (by retraining the private learning algorithms, ref. Appendix D) in Fig. 2 Left. We see the trends of influence are approximately in an exponential form of t. This obvervation motivates the use of exponential decay schedule in practice.
We then show the trends on the variance of influence (dashed lines with the right axis) and relative final losses (solid lines with the left axis) in the Middle Pane, where uni denotes the uniform schedule baseline, exp is an exponential schedule, dyn denotes the dynamic schedule minimizing the ERUB. The influences increases steeply when the data scale is large and therefore have a large variance. Meanwhile, dynamic schedules show improvements of the final loss when the variance is large. It reveals the connection between the influence and the dynamic advantage (refer to Lemma 4.1).
We lastly evaluate the impacts from momentum in the Right Pane, using a Deep Neural Network (DNN) with 2 layers and 100 hidden units. Because of time costs of training deep networks, we do not estimate the influence by retraining and then compute schedules. Instead, we grid-search for the schedule hyper-parameters to find the best one. We see that influence modeled by an exponential function (expinfl) has comparable performance of the influence modeled by linear combination of two reverse exponential functions (momexpinfl). The latter only shows advantage in the setting that data scale is 25 and the number of iteration is only 100, which is expected by our analysis Theorems 4.5 and 4.6. The inherent reason is that the dynamic schedule is more effective when T is larger.

heading: 6 CONCLUSION
text: When a privacy budget is provided for a certain learning task, one has to carefully schedule the privacy usage through the learning process. Uniformly scheduling the budget has been widely used in literature whereas increasing evidence suggests that dynamically schedules could empirically outperform the uniform one. This paper provided a principled analysis on the problem of optimal budget allocation and connected the advantages of dynamic schedules to both the loss structure and the learning behavior. We further validated our results through empirical studies.

heading: A COMPARISON OF ALGORITHMS
text: We present Table 2 as an sumpplementary to the Table 1. Asymptotic upper bounds are achieved when sample size N approaches infinity. Both R and R ,δ with R ,δ < R are the privacy budgets of corresponding algorithms. Specifically, R ,δ = 2/ ln(1/δ) < R when the private algorithm is ( , δ)-DP with ≤ 2 ln(1/δ). PGD+Adv. Adv denotes the Advanced Composition method (Bassily et al., 2014). The method assumes that loss function is 1-strongly convex which implies the PL condition and optimized variable is in a convex set of diameter 1 w.r.t. l2 norm.
PGD+MA. MA denotes the Moment Accoutant (Abadi et al., 2016) which improve the composed privacy bound versus the Advanced Composition. The improvement on privacy bound lead to a enhanced utility bound, as a result.
PGD+Adv+BBImp. The dynamic method assumes that the loss is 1-strongly convex and data comes in stream with n ≤ N samples at each round. Their utility upper bound is achieved at some probability p with any positive c.
Adam+MA. The authors prove a convergence bound for the gradient norms which is extended to loss bound by using PL condition. They also presents the results for AdaGrad and GD which are basically of the same upper bound. Out theorems improve their bound by using the recursive derivation based on the PL condition, while their bound is a simple application of the condition on the gradient norm bound.
GD, Non-Private. This method does not inject noise into gradients but limit the number of iterations. With the bound, we can see that our utility bound are optimal with dynamic schedule.
GD+zCDP. We discussed the static and dynamic schedule for the gradient descent method where the dynamic noise influence is the key to tighten the bound.
Momemtum+zCDP. Different from the GD+zCDP, momentum methods will have two phase of utility upper bound. When T is small than some positive constant T̂ , the bound is as tight as the non-private one. Afterwards, the momentum has a bound degraded as the GD bound.
A.1 COMAPRISON OF GENERALIZATION BOUNDS
In addition to the empirical risk bounds in Table 2, in this section we study the true risk bounds, or generalization error bounds. True risk bounds characterize how well the learnt model can generalize to unseen samples subject to the inherent data distribution. By leveraging the generic learning-theory tools, we extend our results to the True Excess Risk (TER) for strongly convex functions as follows. For a model θ, its TER is defined as follows:
TER , Ex∼X [E[f(θ;x)]]−minθ̂ Ex∼X [f(θ̂;x)], where the second expectation is over the randomness of generating θ (e.g., the noise and stochastic batches). Assume a dataset d consist of N samples drawn i.i.d. from the distribution X . Two approaches could be used to extend the empirical bounds to the true excess risk: One is proposed by Shalev-Shwartz et al. (2009) where the true excess risk of PGD can be bounded in high probability. For example, Bassily et al. (2014) achieved a ln
2N N bound with N 2 iterations. Alternatively, instead of relying on the probabilistic bound, Bassily et al. (2019) used the uniform stability to give a tighter bound. Later, Feldman et al. (2020) improve the efficiency of gradient computation to achieve a similar bound. Both approaches introduce an additive term to the empirical bounds. In this section, we adopt both approaches to investigate the two types of resulting true risk bounds.
(1) True Risk in High Probability. First, we consider the high-probability true risk bound. Based on Section 5.4 from (Shalev-Shwartz et al., 2009) (restated in Theorem A.1), we can relate the EER to the TER. Theorem A.1. Let f(θ;x) be G-Lipschitz, and f(θ) be µ-strong convex loss function given any x ∈ X . With probability at least 1− p over the randomness of sampling the data set d, the following inequality holds:
TER(θ) ≤
√ 2G2
µN
√ f(θ)− f(θ∗) + 4G 2
pµN , (16)
where θ∗ = arg minθ f(θ).
To apply the Eq. (16), we need to extend EER, the expectation bound, to a high-probability bound. Following (Bassily et al., 2014) (Section D), we repeate the PGD with privacy budgetR/k for k times. Note, the output of all repetitions is still of R budget. When k = 1, let the EER of the algorithm be denoted as F (R). Then the EER of one execution of the k repetitions is F (R/k) where privacy is accounted by zCDP. When k = log2(1/p) for p ∈ [0, 1], by Markov’s inequality, there exists one repetition whose EER is F (R/ log2(1/p)) with probability at least 1 − 1/2k = 1 − p. Combined with Eq. (16), we use the bounds of uniform schedule and dynamic schedules in Section 4.1.3 to obtain:
TERuniform ≤ Õ
( G2
µN
(√ D ln(N) ln(1/p)
NR +
4
p
)) , (17)
TERdynamic ≤ Õ
( G2
µN
(√ D ln(1/p)
NR +
4
p
)) , (18)
where we again ignore the κ and other constants. Similarly, we can extend the momentum methods.
(2) True Risk by Unfirom Stability. Following Bassily et al. (2019), we use the uniform stability (defined in Definition A.1) to extend the empirical bounds. We restate the related definition and theorems as follows. Definition A.1 (Uniform stability). Let s > 0. A randomized algorithm M : DN → Θ is suniformly stable w.r.t. the loss function f if for any neighor datasets d and d′, we have: supx∈X E[f(M(d);x)− f(M(d′);x)] ≤ s, where the expectation is over the internal randomness ofM. Theorem A.2 (See, e.g., (Shalev-Shwartz & Ben-David, 2014)). Suppose M : DN → Θ is a s-uniformly stable algorithm w.r.t. the loss function f . LetD be any distribution from over data space and let d ∼ DN . The following holds true.
Ed∼DN [E[f(M(d);D)− f(M(d); d)]] ≤ s, where the second expectation is over the internal randomness ofM. f(M(d);D) and f(M(d); d) represent the true loss and the empirical loss, respecitvely. Theorem A.3 (Uniform stability of PGD from (Bassily et al., 2019)). Suppose η < 2/M for M smooth, G-Lipschitz f(θ;x). Then PGD is s-uniformly stable with s = G2Tη/N .
Combining Theorems A.2 and A.3, we obtain the following:
TER ≤ EER +G2 ηT N .
Because EER in this paper compresses a γT or similar exponential terms, unlike (Bassily et al., 2019), we cannot directly minimize the TER upper bound w.r.t. T and η in the presence of a polynomial form of γT and T . Therefore, we still use T = O(ln N
2R D ) and η for minimizing EER. Note that
G2 ηT N ≤ O( G
2 MN ln N2R D ) ≤ O
( G2
M ) where we assume N D and use lnN ≤ N . Because the term O ( G2/M ) is constant and independent from dimension, we follow (Bassily et al., 2019) to drop the term when comparing the bounds. After dropping the additive term, it is obvious to see that the advantage of dynamic schedules still maintains since TER ≤ EER. A similar extension can be derived for (Wang et al., 2017). We summarize the results and compare them to prior works in Table 3 where we include an additional method: Snowball Stochastic Gradient Descent (SSGD). SSGD dynamically schedule the batch size to achieve an optimal convergence rate in linear time.
Discussion. By using uniform stability, we successfully transfer the advantage of our dynamic schedules from empirical bounds to true risk bounds. The inherent reason is that our bounds only need lnN iterations to reach the preferred final loss. With uniform stability, the logarithmic T reduce the gap caused by transferring. Compared to the (Feldman et al., 2020; Bassily et al., 2019), our method has remarkably improved efficiency in T from N or N2 to ln(N). That implies fewer iterations are required for converging to the same generalization error.

heading: B PRELIMINARIES
text: B.1 PRIVACY
Lemma B.1 (Composition & Post-processing). Let two mechanisms be M : Dn → Y and M ′ : Dn × Y → Z . Suppose M satisfies (ρ1, a)-zCDP and M ′(·, y) satisfies (ρ2, a)-zCDP for ∀y ∈ Y . Then, mechanism M ′′ : Dn → Z (defined by M ′′(x) = M ′(x,M(x))) satisfies (ρ1 + ρ2)-zCDP. Definition B.1 (Sensitivity). The sensitivity of a gradient query∇t to the dataset {xi}Ni=1 is
∆2(∇t) = max n ∥∥∥∥ 1N ∑Nj=1,j 6=n∇(j)t − 1N ∑Nj=1∇(j)t ∥∥∥∥ 2 = 1 N max n ∥∥∥∇(n)t ∥∥∥ 2
(19)
where∇(n)t denotes the gradient of the n-th sample. Lemma B.2 (Gaussian mechanism (Bun & Steinke, 2016)). Let f : Dn → Z have sensitivity ∆. Define a randomized algorithm M : Dn → Z by M(x)← f(x) +N (0,∆2σ2I). Then M satisfies 1 2σ2 -zCDP. Lemma B.3 ((Bun & Steinke, 2016)). If M is a mechanism satisfying ρ-zCDP, then M is (ρ + 2 √ ρ ln(1/δ), δ)-DP for any δ > 0. By solving ρ+ 2 √ ρ ln(1/δ) = , we can get ρ = + 2 ln(1/δ) + 2 √ ln(1/δ)( + ln(1/δ).
B.2 AUXILIARY LEMMAS
Lemma B.4. If maxn ‖xn‖2 = 1 and 1 N ∑ n xn = 0, then the gradient sensitivity of the squared loss will be
∆2(∇) = max i
1
N
√ 2f(θ;xi) ‖xi‖2 ≤ 1
2 (DM ‖θ‖2 + 1),
where ΘM is the set of all possible parameters θt generated by the learning algorithmM.
Proof. According to the definition of sensitivity in Eq. (19), we have
∆2(∇) = max i ∥∥∥∇(i)∥∥∥ 2 = max n 1 n ∥∥∥A(i)θ − xi∥∥∥ 2
where we use i denotes the index of sample in the dataset. Here, we assume it is constant 1. We may get ∥∥∥A(i)θ − xi∥∥∥2 2 = ∥∥xi(x>i θ − 1)∥∥22 = (x>i θ − 1)2 ‖xi‖22 = 2f(θ;xi) ‖xi‖22
where f(θ;xi) = 12 (x > i θ − 1)2. Thus,
∆2(∇) = max i
1
N
√ 2f(θ;xi) ‖xi‖2
Since ‖xn‖2 ≤ 1 and 1 N ∑N n=1 xn = 0,
f(θ) = 1
2N N∑ n=1 [(x>n θ) 2 − 2x>n θ + 1] ≤ 1 2N N∑ n=1 [(‖xn‖ ‖θ‖)2 + 1] ≤ 1 2 (DM ‖θ‖2 + 1)
Lemma B.5. Assume assumptions in Theorem 4.4 are satisfied. Given variables defined in Theorem 4.4, the following inequality holds true:
T∑ t=1 γT−t 2(1− β)ηt bt ∑t i=1 βt−i ‖∇t −∇i‖2 ≤ η30βγ 2M(1− β)3(γ − β)2 T−1∑ i=1 γT−i ‖vi+1‖2 .
Proof. We first handle the inner summation. By smoothness, the inequality ‖∇f(x)−∇f(y)‖ ≤ M ‖x− y‖ holds true. Thus,
∑t i=1 βt−i ‖∇t −∇i‖2 ≤M2 ∑t i=1 βt−i ‖θt − θi‖2
= M2 ∑t−1
k=0 βk ‖θt − θt−k‖2
= M2 ∑t−1 k=0 βk ∥∥∥∥∑t−1i=t−k ηivi+1/bi ∥∥∥∥2 ≤M2 ∑t−1 k=0 βk (∑t−1 j=t−k η2j /b 2 j )(∑t−1 i=t−k ‖vi+1‖2 )
where the last inequality is by Cauchy-Schwartz inequality. Because 1bt = 1 1−βt ≤ 1 1−β and ηt = η0 2M ,
∑t i=1 βt−i ‖∇t −∇i‖2 ≤ η20 4(1− β)2 ∑t−1 k=0 βkk ∑t−1 i=t−k ‖vi+1‖2
= η20 4(1− β)2 ∑t−1 k=0 βkk ∑t−1 i=1 ‖vi+1‖2 I(i ≥ t− k)
= η20 4(1− β)2 ∑t−1 i=1 ‖vi+1‖2 ∑t−1 k=0 βkkI(k ≥ t− i)
= η20 4(1− β)2 ∑t−1 i=1 ‖vi+1‖2 ∑t−1 k=t−i βkk (20)
where I(·) is the indicating function which output 1 if the condition holds true, otherwise 0. Denote the left-hand-side of the conclusion as LHS. We plug Eq. (20) into LHS to get
LHS ≤ T∑ t=1 γT−t 1 bt η30 4M(1− β) ∑t−1 i=1 ‖vi+1‖2 ∑t−1 k=t−i βkk
≤ η 3 0 4M(1− β)2 T∑ t=1 γT−t ∑t−1 i=1 ‖vi+1‖2 ∑t−1 k=t−i βkk
where we relax the upper bound by 1bt = 1 1−βt ≤ 1 1−β . Using Lemma B.6 can directly lead to the conclusion:
LHS ≤ η 3 0βγ 2M(1− β)3(γ − β)2 T−1∑ i=1 γT−i ‖vi+1‖2 .
Lemma B.6. Given variables defined in Theorem 4.4, the following inequality holds true:
T∑ t=1 γT−t ∑t−1 i=1 ‖vi+1‖2 ∑t−1 k=t−i kβk ≤ 2βγ (γ − β)2(1− β) T−1∑ i=1 γT−i ‖vi+1‖2 .
Proof. We first derive the summation:
U1(t, i) , ∑t−1
k=t−i βkk = ∑t−1 k=t−i ∑k j=1 βk
= ∑t−1
k=t−i ∑t−1 j=1 βkI(j ≤ k)
= ∑t−1
j=1 ∑t−1 k=max(t−i,j) βk
= ∑t−1
j=1
βmax(t−i,j) − βt
1− β
= 1
1− β
( (t− i)βt−i + β t−i+1 − βt
1− β − β − β t 1− β ) = 1
1− β
( (t− i)βt−i + β
t−i+1 − β 1− β
)
Now, we substitute U1(t, i) into LHS and replace t− i by j, i.e., t = j + i, to get
LHS = T∑ t=1 γT−t t−1∑ i=1 ‖vi+1‖2 1 1− β ( (t− i)βt−i + β t−i+1 − β 1− β )
= T−1∑ i=1 ‖vi+1‖2 T∑ t=i+1 γT−t 1 1− β ( (t− i)βt−i + β t−i+1 − β 1− β )
= T−1∑ i=1 ‖vi+1‖2 T−i∑ j=1 γT−(j+i) 1 1− β ( jβj + βj+1 − β 1− β )
= T−1∑ i=1 γT−i ‖vi+1‖2 T−i∑ j=1 γ−j 1 1− β ( jβj + βj+1 − β 1− β )
≤ 1 1− β T−1∑ i=1 γT−i ‖vi+1‖2 T−i∑ j=1
( j ( β
γ
)j + β
1− β
( β
γ
)j)
Let a = β/γ, we show
T−i∑ j=1 jaj = T−i∑ j=1 j∑ o=1 aj
= T−i∑ o=1 T−i∑ j=o aj
= T−i∑ o=1 ( ao − aT−i+1 1− a ) = a− aT−i+1
(1− a)2 − (T − i)a
T−i+1
1− a
≤ a (1− a)2 .
Thus,
LHS ≤ 1 1− β T−1∑ i=1
γT−i ‖vi+1‖2  a
(1− a)2 +
β
1− β T−i∑ j=1 aj  ≤ 1
1− β T−1∑ i=1 γT−i ‖vi+1‖2 (
a
(1− a)2 +
β 1− β a 1− a
)
≤ a (1− a)2(1− β) T−1∑ i=1 γT−i ‖vi+1‖2
Because γ < 1, β < a = β/γ and
a
(1− a)2 +
β 1− β a 1− a ≤ 2a (1− a)2 .
Therefore,
LHS ≤ 2a (1− a)2(1− β) T−1∑ i=1 γT−i ‖vi+1‖2 = 2βγ (γ − β)2(1− β) T−1∑ i=1 γT−i ‖vi+1‖2
Lemma B.7. Suppose γ ∈ (0, 1) and β ∈ (0, 1). Define
T̂ = max t s.t. γt−1 ≥ 1− β 1− βt .
If t ≤ T̂ , 1−β1−βt ≤ γ t−1 for t = 1, . . . , T . If t > T̂ , 1−β1−βt < γ T̂−1.
Proof. Define h(t) = γt−1(1− βt) whose derivatives are
h′(t) = γt−1(1− βt) ln γ + γt−1(−βt) lnβ = γt−1 [ ln γ − βt(ln γ + lnβ) ] = γt−1 [ 1− βt(1 + logγ β) ] ln γ.
Simple calculation shows 1− βt(1 + logγ β) ∣∣ t=0
= − logγ β < 0 and limt→+∞ 1 − βt(1 + logγ β) = 1. When t = − logβ(1 + logγ β) denoted as t0, 1 − βt(1 + logγ β) = 0. Because 1 − βt(1 + logγ β) is monotonically increasing by t and γt−1 ln γ is negative, h′(t) ≥ 0 if t ≤ t0. Otherwise, h′(t) < 0. Therefore, h(t) is a concave function. Because h(1) = 1− β and h(T̂ ) = γT̂−1(1 − βT̂ ) ≥ 1 − β > 0, h(t) ≥ 1 − β for t = 1, . . . , T̂ . Thus, for all t ∈ [1, T̂ ], we have 1−β1−βt ≤ γ t−1.
For t > T̂ , because 1−β1−βt monotonically increases by t, we have 1−β 1−βt < 1−β 1−βT̂ ≤ γT̂−1.

heading: C PROOFS
text: Proof of Theorem 3.1. Because all sample gradient are G-Lipschitz continuous, the sensitivity of the averaged gradient is upper bounded by G/N . Based on Lemma B.2, the privacy cost of gt is 12σ2t 1.
Here, we make the output of each iteration a tuple of (θt+1, vt=1). For the 1st iteration, because θ1 does not embrace private information by random initialization, the mapping,[
v2 θ2
] = [ g1
θ1 − η1g1
] ,
1For brevity, when we say the privacy cost of some value, e.g., gradient, we actually refer to the cost of mechanism that output the value.
is ρ̂1-zCDP where ρ̂1 = 12σ2t .
Suppose the output of the t-th iteration, (θt, vt), is ρ̂t-zCDP. At each iteration, we have the following mapping (θt, vt)→ (θt+1, vt+1) defined as[
vt+1 θt+1
] = [ φ(vt, gt)
θt − ηtφ(vt, gt)
] .
Thus, the output tuple (θt+1, vt+1) is (ρ̂t + 12σ2t )-zCDP by Lemma B.1.
Thus, the recursion implies that (θT+1, vT+1) has privacy cost as
ρ̂T+1 = ρ̂T + 1
2σ2T = · · · = T∑ t=1 1 2σ2t = 1 2 T∑ t=1 ρt ≤ 1 2 (R−RT ) ≤ 1 2 R.
Let ρ = ρ̂T+1. Then we can get the conclusion.
C.1 GRADIENT DESCENTS
Proof of Theorem 4.1. With the definition of smoothness in Definition 3.3 and Eq. (1), we have
f(θt+1)− f(θt) ≤ −ηt∇>t (∇t +Gσtνt/N) + 1
2 Mη2t ‖∇t +Gσtνt/N‖
2
= −ηt(1− 1
2 Mηt) ‖∇t‖2 − (1−Mηt)ηt∇>t Gσtνt/N +
1 2 Mη2t ‖Gσtνt/N‖ 2
≤ −2µηt(1− 1
2 Mηt)(f(θt)− f(θ∗))− (1−Mηt)ηt∇>t Gσtνt/N
+ 1
2 Mη2t ‖Gσtνt/N‖ 2 .
where the last inequality is due to the Polyak-Lojasiewicz condition. Taking expectation on both sides, we can obtain
E[f(θt+1)]− E[f(θt)] ≤ −2µηt(1− M
2 ηt)(E[f(θt)]− f(θ∗)) +
M
2 (ηtGσt/N)
2E ‖νt‖2
which can be reformulated by substacting f(θ∗) on both sides and re-arranged as E[f(θt+1)]− f(θ∗) ≤ ( 1− 2µηt(1− M
2 ηt)
) (E[f(θt)]− f(θ∗)) + M
2 (ηtGσt/N)
2D
Recursively using the inequality, we can get
E[f(θT+1)]− f(θ∗) ≤ T∏ t=1 ( 1− 2µηt(1− M 2 ηt) ) (E[f(θ1)]− f(θ∗))
+ MD
2 T∑ t=1 T∏ i=t+1 ( 1− 2µηi(1− M 2 ηi) ) (ηtGσt/N) 2.
Let ηt ≡ 1/M . Then the above inequality can be simplified as
E[f(θT+1)]− f(θ∗) ≤ γT (E[f(θ1)]− f(θ∗)) +R T∑ t=1 γT−t MD 2R ( ηtG N )2 σ2t
= γT (E[f(θ1)]− f(θ∗)) +R T∑ t=1 γT−tασ2t (E[f(θ1)]− f(θ∗))
= ( γT +R ∑T t=1 qtσ 2 t ) (f(θ1)− f(θ∗))
Proof of Theorem 4.2. The minimizer of the upper bound of Eq. (3) can be written as
T ∗ = arg min T γT + ακ(1− γT )T (21)
where we substitute σ2 = T/R in the second line. To find the convex minimization problem, we need to vanishing its gradient which involves an equation like TγT = c for some real constant c. However, the solution is Wk(c) for some integer k where W is Lambert W function which does not have a simple analytical form. Instead, because γT > 0, we can minimize a surrogate upper bound as following
T ∗ = arg min T
γT + ακT = 1
ln(1/γ) ln
( ln(1/γ)
κα
) , if κα+ ln γ < 0 (22)
where we use the surrogate upper bound in the second line and utilize γ = 1 − 1κ . However, the minimizer of the surrogate objective is not optimal for the original objective. When κ is large, the term, −ακγTT , cannot be neglected as we expect. On the other hands, T suffers from explosion if κ→∞ and meanwhile 1/γ →+ 1. The tendency is counterintuitive since a small T should be taken for sharp losses. To fix the issue, we change the form of T ∗ as
T ∗ = 1
ln(1/γ) ln
( 1 + ln(1/γ)
α
) , (23)
which gradually converges to 0 as κ→∞. Now we substitute Eq. (23) into the original objective function, Eq. (21), to get
ERUBuniform = 1
1 + ln(1/γ)/α
[ 1 + κ ln ( 1 + ln(1/γ)
α
)] . (24)
Notice that
ln(1/γ) = ln(κ/(κ− 1)) = ln(1 + 1/(κ− 1)) ≤ 1 κ− 1 ≤ 1 cκ
because κ ≥ 11−c > 1 for some constant c ∈ (0, 1). In addition,
ln(1/γ) = − ln(1− 1/κ) ≥ 1/κ.
Now, we can get the upper bound of Eq. (24) as
ERUBuniform ≤ κ κ+ 1/α
[ 1 + κ ln ( 1 + 1
cκα )] ≤ c1 κ
κ+ 1/α κ
[ ln ( 1 + 1
κα
) + ln( 1
c )) ] ≤ c1c2 κ2
κ+ 1/α ln
( 1 + 1
κα ) for some constants c1, c2 and large enough 1α . Also, we can get the lower bound
ERUBuniform ≥ cκ cκ+ 1/α
[ 1 + κ ln ( 1 + 1
κα
)] ≥ c κ 2
κ+ 1/α ln
( 1 + 1
κα
) .
where we use the condition c ∈ (0, 1). Thus, ERUBuniform = Θ ( κ2 κ+1/α ln ( 1 + 1κα )) .
Proof of Lemma 4.1. By ∑T t=1 σ
−2 = R and Cauchy-Schwarz inequality, we can derive the achievable lower bound as
R ∑ t qtσ 2 t = ∑ t 1 σ2t ∑ t qtσ 2 t ≥ ( T∑ t=1 √ qt )2
where the inequality becomes equality if and only if s/σ2t = qtσ 2 t , i.e., σt = (s/qt) 1/4, for some positive constant s. The equality ∑T t=1 σ −2 t = R immediately suggests √ s = 1R ∑T t=1 √ qt. Thus, we get the σt.
Notice
T T∑ t=1 qt − (∑T t=1 √ qt )2 = T 2 1 T T∑ t=1 ( √ qt − 1 T T∑ i=1 √ qi )2 = T 2 Var[qt] (25)
where the variance is w.r.t. t.
Proof of Theorem 4.3. The upper bound of Eq. (3) can be written as
ERUBdyn = γT + ∑T
t=1 γT−tαRσ2
= γT + α (∑T t=1 √ γT−t )2 = γT + α ( 1− γT/2
1−√γ )2 where we make use of Lemma 4.1. Then, the minimizer of the ERUB is
T ∗ = arg min T γT + α
( 1− γT/2
1−√γ )2 = 2 logγ ( α
α+ (1−√γ)2
) . (26)
We can substitute Eq. (26) into ERUBdyn to get
ERUBdynmin =
( α
α+ (1−√γ)2
)2 + α ( 1
1−√γ
)2( 1− α
α+ (1−√γ)2 )2 = ( α(1−√γ)−2
α(1−√γ)−2 + 1
)2 +
α(1−√γ)−2( α(1−√γ)−2 + 1 )2 = α(1−√γ)−2
α(1−√γ)−2 + 1
Notice that ( 1−√γ )−2 = κ2 + κ2 − κ + 2κ √ κ(κ− 1) = κ(2κ − 1 + 2 √ κ(κ− 1)) and it is bounded by
κ(2κ− 1 + 2 √ κ(κ− 1)) ≤ 4κ2,
κ(2κ− 1 + 2 √ κ(κ− 1)) ≥ κ(2κ− (3κ− 2) + 2 √ (κ− 1)(κ− 1)) = κ(−κ+ 2 + 2κ− 2) = κ2. Therefore, κ ≤ ( 1−√γ
)−1 ≤ 2κ, with which we can derive ERUBdynmin ≤ 4 κ2α
κ2α+ 1 ,
ERUBdynmin ≥ κ2α 4κ2α+ 1 ≥ 1 4 κ2α κ2α+ 1 .
Thus, ERUBdynmin = Θ ( κ2α κ2α+1 ) .
C.2 GRADIENT DESCENTS WITH MOMENTUM
Proof of Theorem 4.4. Without loss of generality, we absorb the Cσt/N into the variance of νt such that νt ∼ N (0, Cσ 2 t N I) and gt ← ∇t + νt. Define bt = 1− β t.
By smoothness and Eq. (1), we have
f(θt+1)− f(θt) ≤ ∇>t (θt+1 − θt) + 1
2 M ‖θt+1 − θt‖2
= −ηt b2t bt∇>t vt+1 + 1 2 M η2t b2t ‖vt+1‖2
= ηt b2t
( ‖bt∇t − vt+1‖2 − ‖bt∇t‖2 − ‖vt+1‖2 ) + 1
2 M η2t b2t ‖vt+1‖2
= ηt b2t ‖bt∇t − vt+1‖2︸ ︷︷ ︸
U1(t)
−ηt ‖∇t‖2 − ηt b2t (1− 1 2 Mηt) ‖vt+1‖2 , (27)
where only the U1(t) is non-negative. Specifically, U1(t) describes the difference between current gradient and the average. We can expand vt+1 to get an upper bound:
U1(t) = ‖bt∇t − vt+1‖2 = ∥∥∥(1− β)∑t
i=1 βt−i∇t − (1− β) ∑t i=1 βt−igi ∥∥∥2 = (1− β)2 ∥∥∥∑t i=1 βt−i(∇t − gi) ∥∥∥2
= (1− β)2 ∥∥∥∑t
i=1 βt−i(∇t −∇i) + ∑t i=1 βt−i(∇i − gi) ∥∥∥2
≤ 2(1− β)2 [∥∥∥∑t
i=1 βt−i(∇t −∇i) ∥∥∥2 + ∥∥∥∑t i=1 βt−i(∇i − gi) ∥∥∥2]
≤ 2(1− β) bt∑ti=1 βt−i ‖∇t −∇i‖2︸ ︷︷ ︸ U2(t) (gradient variance) +(1− β) ∥∥∥∑t i=1 βt−iνi ∥∥∥2︸ ︷︷ ︸ noise variance 
where we use ‖x+ y‖2 ≤ (‖x‖+ ‖y‖)2 ≤ 2(‖x‖2 + ‖y‖2). The last inequality can be proved by Cauchy-Schwartz inequality for each coordinate.
We plug the U1(t) into Eq. (27) and use the PL condition to get
f(θt+1)− f(θt) ≤ ηt b2t U1(t)− ηt ‖∇t‖2 − ηt b2t (1− 1 2 Mηt) ‖vt+1‖2
≤ −ηt ‖∇t‖2 + ηt b2t
2(1− β) [ btU2(t) + (1− β) ∥∥∥∑t i=1 βt−iνi ∥∥∥2] − ηt b2t (1− 1 2 Mηt) ‖vt+1‖2
≤ −2µηt(f(θt)− f(θ∗)) + 2(1− β)ηt
bt U2(t) + 2(1− β)2ηt b2t ∥∥∥∑t i=1 βt−iνi ∥∥∥2 − ηt b2t (1− 1 2 Mηt) ‖vt+1‖2 .
Rearranging terms and taking expectation to show
E[f(θt+1)]− f(θ∗) ≤ γ(E[f(θt)]− f(θ∗)) + 2(1− β)2ηt
b2t
∑t i=1 βt−iE ‖νi‖2
+ 2(1− β)ηt
bt E[U2(t)]− ηt b2t (1− 1 2 Mηt)E ‖vt+1‖2
= γ(E[f(θt)]− f(θ∗)) + 2(1− β)2ηt
b2t
∑t i=1 β2(t−i) C2Dσ2t N2
+ 2(1− β)ηt
bt E[U2(t)]− ηt b2t (1− 1 2 Mηt)E ‖vt+1‖2
where γ = 1− η0/κ = 1− 2µηt. The recursive inequality implies
E[f(θT+1)]− f(θ∗) ≤ γT (f(θ1)− f(θ∗)) + T∑ t=1 γT−t 2(1− β)2ηt b2t ∑t i=1 β2(t−i) C2Dσ2t N2
+ T∑ t=1 γT−t 2(1− β)ηt bt E[U2(t)]− T∑ t=1 γT−t ηt b2t (1− 1 2 Mηt)E ‖vt+1‖2
= ( γT + 2η0αR ∑T t=1 γT−t (1− β)2
b2t
∑t i=1
β2(t−i)σ2t︸ ︷︷ ︸ U3
) (f(θ1)− f(θ∗))
+ T∑ t=1 γT−t 2(1− β)ηt bt E[U2(t)]− T∑ t=1 γT−t ηt b2t (1− 1 2 Mηt)E ‖vt+1‖2︸ ︷︷ ︸
U4(t)
.
where we utilize α = DC 2
2MN2R 1 f(θ1)−f(θ∗) and ηt = η0 2M .
By Lemma B.5, we have T∑ t=1 γT−t 2(1− β)ηt bt U2(t) ≤
η30βγ 2M(1− β)3(γ − β)2 T−1∑ i=1 γT−i ‖vi+1‖2 .
Thus, by 1bt ≥ 1,
U4(t) ≤ η30βγ 2M(1− β)3(γ − β)2 T−1∑ i=1 γT−iE ‖vi+1‖2 − η0 2M (1− η0 4 ) T∑ t=1 γT−tE ‖vt+1‖2
= − η0 2M ζ T∑ t=1 γT−tE ‖vt+1‖2
where
ζ = 1− 1 4 η0 −
βγ
(γ − β)2(1− β)3 η20 = 1−
1 4 η0 −
β/γ
(1− β/γ)2(1− β)3 η20
When a small enough η0, e.g., Specifically,
η0 ≤ (γ − β)2(1− β)3
8βγ
[√ 1 +
64βγ
(γ − β)2(1− β)3 − 1
]
= 8√
1 + 64βγ(γ − β)−2(1− β)−3 + 1 We can have ζ ≥ 0. By the definition of U3(T, σ), we can get
E[f(θT+1)]− f(θ∗) ≤ ( γT + 2η0αRU3(T, σ) ) (f(θ1)− f(θ∗))−
η0 2M ζ T∑ t=1 γT−tE ‖vt+1‖2 .
Proof of Theorem 4.5. Since σt is static, by definition of U3 in Theorem 4.4, U3 = ∑T
t=1 γT−t
(1− β)2 (1− βt)2 ∑t i=1 β2(t−i)σ2
= σ2 ∑T
t=1 γT−t
(1− β)2 (1− βt)2 ∑t i=1 β2(t−i)
= σ2 ∑T
t=1 γT−t
(1− β)2 (1− βt)2 1− β2t 1− β2
= σ2 ∑T
t=1 γT−t 1− β 1− βt 1 + βt 1 + β .
Because 1−β1−βt 1+βt
1+β ≤ 1, the U3 will be smaller than the corresponding summation in GD with uniform schedule.
By Lemma B.7, when T > T̂ , we can rewrite U3 as U3 ≤ σ2 ∑T
t=1 γT−t 1− β 1− βt
= σ2 ∑T̂
t=1 γT−t 1− β 1− βt
+ σ2 ∑T
t=T̂+1 γT−t 1− β 1− βt
≤ σ2 ∑T̂
t=1 γT−tγt−1 + σ2 ∑T t=T̂+1 γT−tγT̂−1
= σ2γT−1T̂ + σ2γT̂−1 ∑T−T̂
t=1 γT−T̂−t
= σ2γT−1T̂ + σ2 γT̂−1 − γT−1
1− γ
= T
γR γT
( T̂ +
γT̂−T − 1 1− γ ) where we use σ2 = T/R in the last line. Without assuming T > T̂ , we can generally write the upper bound as
U3 ≤ T
γR γT
( min{T̂ , T}+ max{γ
T̂−T − 1 1− γ , 0}
) .
By Theorem 4.4, because ζ ≥ 0, we have ERUB ≤ γT + 2Rη0αU3
= γT (1 + α′
γ T
( min{T̂ , T}+ max{γ
T̂−T − 1 1− γ , 0}
) )
where α′ = 2η0α.
First, we consider T ≤ T̂ . Use T = 1ln(1/γ) ln ( 1 + η0κα ) = ⌈ O ( κ η0 ln ( 1 + η0κα ))⌉ to get
ERUB ≤ (
α
α+ η0/κ
)( 1 + α′γ−1( 2 ln(1/γ) ln ( 1 + η0 κα ) )2 )
≤ (
α
α+ η0/κ
)( 1 + 8κ2α η0γ ln2 ( 1 + η0 κα )) ≤ O ( κ
κ+ η0/α
( 1 + 8κ2α η0γ ln2 ( 1 + η0 κα ))) = O ( κ
κ+ η0/α
( 1 + 4κ
γ )) = O ( κ2
κ+ η0/α
)
where we used ln(1/γ) ≥ η0/κ and ln(1 + x) ≤ √ x for any x > 0.
Second, when T > T̂ ,
ERUB ≤ γT (1 + α ′
γ T
( T̂ +
γT̂−T − 1 1− γ
) )
≤ O ( γT + 2α′
γ Tκ(γT̂ − γT )
) .
Make use of T = ⌈
1 ln(1/γ) ln ( 1 + η0κα )⌉ to show
ERUB ≤ O (
κ
κ+ η0/α +
4κ2α
η0γ (γT̂ − κ κ+ η0/α ) ln ( 1 + η0 κα )) ≤ O ( κ2
κ+ η0/α γT̂−1 ln
( 1 +
η0 κα
)) .
Proof of Theorem 4.6. By Lemma B.7, we can rewrite U3 as U3 = ∑T
t=1 γT−t
(1− β)2 (1− βt)2 ∑t i=1 β2(t−i)σ2i
≤ ∑T̂
t=1 γT−tγ2(t−1) ∑t i=1 β2(t−i)σ2i + ∑T t=T̂+1 γT−tγ2(T̂−1) ∑t i=1 β2(t−i)σ2i
≤ γT−T̂ ∑T̂
t=1 γT̂−tγ2(t−1) ∑t i=1
β2(t−i)σ2i︸ ︷︷ ︸ V1
+γ2(T̂−1) ∑T
t=T̂+1 γT−t ∑t i=1
β2(t−i)σ2i︸ ︷︷ ︸ V2
We derive V1 and V2 separately.
For V1, we can obtain the upper bound by V1 = ∑T̂
t=1 γT̂−tγ2(t−1) ∑t i=1 β2(t−i)σ2i
= γT̂−2 ∑T̂ t=1 γt ∑t i=1 β2(t−i)σ2i
= γT̂−2 ∑T̂
i=1 β−2iσ2i ∑T̂ t=i ( γβ2 )t = γT̂−2 ∑T̂ i=1 β−2iσ2i ( γβ2 )i − (γβ2)T̂+1 1− γβ2
= γ2T̂−3 ∑T̂
i=1
γi−T̂−1 − β2(T̂+1−i)
1− γβ2 σ2i
= γ2T̂−3 ∑T̂
i=1
1− (γβ2)T̂+1−i
1− γβ2 γi−T̂−1σ2i
≤ γ T̂ γ2(1− γβ2) ∑T̂ i=1 γiσ2i
≤ γ T̂ γ(γ − β2) ∑T̂ i=1 γiσ2i
For V2, we can derive V2 = ∑T
t=T̂+1 γT−t ∑t i=1 β2(t−i)σ2i
= ∑T
t=1 γT−t ∑t i=1 β2(t−i)σ2i − ∑T̂ t=1 γT−t ∑t i=1 β2(t−i)σ2i
= ∑T
t=1 γT−t ∑t i=1 β2(t−i)σ2i − γT−T̂ ∑T̂ t=1 γT̂−t ∑t i=1 β2(t−i)σ2i .
We first consider the first term∑T t=1 γT−t ∑t i=1 β2(t−i)σ2i
= ∑T i=1 σ2i ∑T t=i γT−tβ2(t−i)
= ∑T
i=1 γTβ−2iσ2i ∑T t=i γ−tβ2t
= ∑T
i=1 γTβ−2iσ2i
(β2/γ)i − (β2/γ)T+1
1− (β2/γ) = ∑T
i=1
γT+1−i − β2(T+1−i)
γ − β2 σ2i .
Similarly, we have
γT−T̂ ∑T̂
t=1 γT̂−t ∑t i=1 β2(t−i)σ2i
= γT−T̂ ∑T̂
i=1
γT̂+1−i − β2(T̂+1−i)
γ − β2 σ2i
= ∑T̂
i=1
γT+1−i − γT−T̂β2(T̂+1−i)
γ − β2 σ2i .
Thus,
V2 = ∑T
i=1
γT+1−i − β2(T+1−i)
γ − β2 σ2i − ∑T̂ i=1 γT+1−i − γT−T̂β2(T̂+1−i) γ − β2 σ2i
= ∑T
i=T̂+1
γT+1−i − β2(T+1−i)
γ − β2 σ2i + ∑T̂ i=1 γT−T̂ − β2(T−T̂ ) γ − β2 β2(T̂+1−i)σ2i
≤ ∑T
i=T̂+1
γT+1−i − β2(T+1−i)
γ − β2 σ2i + ∑T̂ i=1 γT−T̂ γ − β2 β2(T̂+1−i)σ2i .
Substitute V1 and V2 into U3 to get
U3 ≤ γT 1 γ(γ − β2) ∑T̂ i=1 γiσ2i + γ 2T̂−2 ∑T i=T̂+1 γT+1−i − β2(T+1−i) γ − β2 σ2i
+ ∑T̂
i=1
γT+T̂−2
γ − β2 β2(T̂+1−i)σ2i
≤ (
γT γ(γ − β2) ∑T̂ i=1 (γi + γT̂−1β2(T̂+1−i))σ2i + γ 2T̂−2 ∑T i=T̂+1 γT+1−i − β2(T+1−i) γ − β2 σ2i ) ≤ ( 2γT γ(γ − β2) ∑T̂ i=1 γiσ2i + γ 2T̂−2 ∑T i=T̂+1 γT+1−i − β2(T+1−i) γ − β2 σ2i
) = ∑T
t=1 qtσ
2 t
where
qt = 2
γ(γ − β2) γT+tIT≤T̂ + γ
2(T̂−1) γ T+1−i − β2(T+1−i)
γ − β2 γT−tIT>T̂
≤ c1γT+tIT≤T̂ + γ T̂−1c2γ T−tIT>T̂
where c1 = 2γ(γ−β2) and c2 = γ2T̂ γ−β2 .
When T > T̂ , by Lemma 4.1, the lower bound of R ∑T t=1 qtσ
2 t is(∑T
t=1
√ qt )2 = γT (∑T̂ t=1 √ c1γt + ∑T t=T̂+1 √ γT̂−1c2γ−t )2 = γT ( √ c1γ 1− γT̂ /2
1−√γ + √ c2 1− γ(T̂−T−1)/2 √ γ − 1
)2
= γT ( √ c1γ 1− γT̂ /2
1−√γ + √ c2 γ(T̂−T−1)/2 − 1 1−√γ
)2
≤ O c2{γ(T̂−1)/2 − γT/2 1−√γ }2 which is achieved when
σ2t = 1
R ∑T i=1 √ qi qt .
By Theorem 4.4, because ζ ≥ 0, we have ERUB ≤ γT + 2Rη0αU3
= γT + 2η0α ∑T
t=1 Rqtσ
2 t .
And the minimum of the upper bound is
ERUBmin = γ T + α′O {γ(T̂−1)/2 − γT/2 1−√γ }2 where α′ = 2η0c2α. Let T = 2ln(1/γ) ln ( 1 + η0κα ) . Then,
ERUBmin = O ( κα κα+ η0 )2 +
α′
(1−√γ)2
{ γ(T̂−1)/2 − (1− γ(T̂−1)/2)κα
κα+ η0 }2 ≤ O ( κα κα+ η0 )2 + 2η0c2α (1−√γ)2 { γ(T̂−1)/2 κα+ η0
}2 = O ( κα
(κα+ η0)2
( κα+ 2η0c2/κ
(1−√γ)2 γ(T̂−1) )) = O ( κα
(κα+ η0)2 (κα+ c3η0) ) ≤ O ( κα
κα+ η0 ) where c3 is some constant.
When T ≤ T̂ ,
U3 ≤ γT−T ∑T
t=1 γT−tγ2(t−1) ∑t i=1
β2(t−i)σ2i︸ ︷︷ ︸ V1
≤ γ T−2 1− γβ2 ∑T i=1 γiσ2i
with which we obtain ERUB ≤ γT + 2Rη0αU3
≤ γT + 2η0α γ−2 1− γβ2 ∑T t=1 Rqtσ 2 t .
where we let qt = γT+t. By Lemma 4.1,∑T i=1 Rqtσ 2 i ≥ (∑T t=1 √ qt )2 = γT (∑T t=1 γt/2 )2
= γT+1 ( 1− γT/2
1−√γ
)2 .
Thus,
ERUBmin ≤ γT + 2η0α γT−1
1− γβ2
( 1− γT/2
1−√γ )2 = γT ( 1 + 2η0γc1α ( 1− γT/2
1−√γ
)2)
Let T = ⌈
2 ln(1/γ) ln ( 1 + η0κα )⌉ . Then,
ERUBmin ≤ ( κα
κα+ η0
)2( 1 + 2η0γc1α
(1−√γ)2 (
1 κα+ 1 )2 )
≤ ( κα
κα+ η0
)2( 1 +O( 1
κα+ 1 ) ) ≤ O ( κα
κα+ η0
)2 .
In summary,
ERUBmin ≤ O ( κα
κα+ η0
( IT≤T̂ κα
κα+ η0 + IT>T̂
))
C.3 STOCHASTIC GRADIENT DESCENTS
Proof of Theorem 4.7. Let ∇̃t be the stochastic gradient of the step t. By the smoothness, we have
f(θt+1)− f(θt) ≤ −ηt∇>t (∇̃t +Gσtνt/n) + 1
2 Mη2t ∥∥∥∇̃t +Gσtνt/n∥∥∥2 = −ηt∇>t (∇t + σgξt/n+Gσtνt/n) + 1
2 Mη2t ‖∇t + σgξt/n+Gσtνt/n‖ 2 .
Note that E(σgξt/n+Gσtνt/n) = 0 and E(σgξt/n+Gσtνt/n)2 = σ2g + (Gσt/n)2. Without loss of generality, we can write σgξt + Gσtνt as σ̃tζt where σ̃t , √ σ2g + (Gσt) 2 and ζt is a random
vector with Eζt = 0 and E ‖ζt‖2 ≤ D. Therefore,
f(θt+1)− f(θt) ≤ −ηt∇>t (∇t + σ̃tζt/n) + 1
2 Mη2t ‖∇t + σ̃tζt/n‖
2
= −ηt(1− 1
2 Mηt) ‖∇t‖2 − (1−Mηt)ηt∇>t σ̃tζt/n+
1 2 Mη2t ‖σ̃tζt/n‖ 2
≤ −2µηt(1− 1
2 Mηt)(f(θt)− f(θ∗))− (1−Mηt)ηt∇>t σ̃tζt/n
+ 1
2 Mη2t ‖σ̃tζt/n‖ 2 .
Then following the same proof of Theorem 4.1, we can get
E[f(θT+1)]− f(θ∗) ≤ γT (E[f(θ1)]− f(θ∗)) +R′ T∑ t=1 γT−tα 1 G2 σ̃2t (E[f(θ1)]− f(θ∗))
= [ γT +R′
T∑ t=1 γT−tα( 1 G2 σ2g + σ 2 t )
] (E[f(θ1)]− f(θ∗))
= [ γT +R′α 1
G2 σ2g
1− γT
1− γ +R′ T∑ t=1 γT−tασ2t
] (E[f(θ1)]− f(θ∗))
≤ [ γT + R′κα
G2 σ2g +R ′ T∑ t=1 γT−tασ2t
] (E[f(θ1)]− f(θ∗)).
where R ′κα G2 = D 2µ(f(θ1)−f(θ∗)) 1 n2 = D 2µ(f(θ1)−f(θ∗)) min{ 1 N2R , 1} ≤ D 2µ(f(θ1)−f(θ∗)) 1 N2R .
Proof of Theorem 4.8. Without loss of generality, we can write σgξt + Gσtνt as σ̃tζt where σ̃t ,√ σ2g + (Gσt)
2 and ζt is a random vector with Eζt = 0 and E ‖ζt‖2 ≤ D. Therefore, we replace νt by ζt and σ2t by σ̃ 2 t /G 2 = σ2g/G 2 + σ2t . Now, we only need to update U3(σ, T ) as
Ũ3 = 1
G2 ∑T t=1 γT−t (1− β)2 (1− βt)2 ∑t i=1 β2(t−i)σ̃2i
= ∑T
t=1 γT−t
(1− β)2 (1− βt)2 ∑t i=1 β2(t−i)( 1 G2 σ2g + σ 2 t )
= Ug3 + U3
where we define
Ug3 , 1 G2 σ2g ∑T t=1 γT−t (1− β)2 (1− βt)2 ∑t i=1 β2(t−i).
We can upper bound Ug3 by
Ug3 = 1 G2 σ2g ∑T t=1 γT−t (1− β)2 (1− βt)2 1− β2t 1− β2
= 1 G2 σ2g ∑T t=1 γT−t 1− β 1− βt 1 + βt 1 + β
≤ 1 G2
σ2g ∑T
t=1 γT−t
≤ 1 G2 σ2g 1 1− γ
= 1
G2 κσ2g .
Combine with the factors of U3 in the PGD bounds:
αR′Ug3 ≤ αR′
G2 κσ2g =
αR′
G2 κσ2g = Dσ2g 2µn2(f(θ1)− f(θ∗)) ≤ Dσ2g 2µN2R(f(θ1)− f(θ∗)) .

heading: D EXPERIMENTS
text: Dataset. (1) Synthetic data. We generate a 100-dimensional dataset including linearly separable data points using sckit-learn package. The data points are distributed in two points in the hyper-cubic with Euclidean distance of 10. In total, 1000 samples are generated for training with the
logistic loss. (2) Real data. We create a subset of the MNIST dataset (Lecun et al., 1998) including 1000 handwritten images of digit 3 and 5 (MNIST35). Compared to the original dataset (70, 000 samples), the small set will be more vulnerable to attack and the private learning will require larger noise (see the 1/N factor in Eq. (1)). Following the preprocessing in (Abadi et al., 2016), we project the vectorized images into a 60-dimensional subspace extracted by PCA.
Setup. The samples are first normalized so that ∑N n=1 xn = 0 and the standard deviation is 1. Then the sample norms are scaled such that maxn ‖xn‖ = 10 (i.e., data scales). We fix the learning rate to 0.1 based on the corresponding experiments of non-private training (same setting without noise). The total privacy budget is 0.1963-zCDP (equal to (4, 10−8)-DP) which implies R = 0.3927. To control the sensitivity of the gradients, we clip gradients by a clipping norm fixed at 4. Formally, we scale down the sample gradients to length 4 if its norm is larger than 4. Because the schedule highly depends on the iteration number T , we grid search the best T for compared methods. Therefore, we ignore the privacy cost of such tuning in our experiments which protocol is also used in previous work (Abadi et al., 2016; Wu et al., 2017). All the experiments are repeated 100 times and metrics are averaged afterwards.
t)
t)
t)
Estimate of influences by retraining. In the left pane of Fig. 3, we estimate the influence of σt by retraining multiple times. When keeping σi for i 6= t fixed (as the fine-tuend uniform schedule σ), the value of σt is varied from 20 to 200. Then we fit a quadratic function of σt where the coefficient is treated as estimation of qt. Repeating the estimation for all t in range 1 to 100 could provide us the trend of influence in the middle pane.
Results. In the left pane of Fig. 3, the squared final loss (i.e., f(θT+1)) is approximately a quadratic function of the σt with small relative variance (i.e., the variance divided by the mean value, 0.14, 0.032, 0.016 for t = 10, 60, 90, respectively). When σt increases, the frequency of clipping increases as well which leads to more variance in the final losses. We use the least square method to fit the relation shown as the solid lines. The final logistic loss is more sensitive to the noise because of the additional uncertainty from the changing Hessian. We still fit a quadratic function on σt. It turns out the relative variances of the quadratic coefficient (approximately the influence) is small which are 0.025, 0.024, 0.027 for t = 10, 60, 90, respectively.
The middle pane shows the relationship between the estimated qt and learning steps. The qt of squared loss is computed by analytical solution using the Hessian eigen values. The qt of logistic loss is computed by retraining based on uniform schedule. Both loss functions show an increased influence as learning continues, which indicates that the dynamic schedule should be decreasing accordingly. The squared loss has a rather steep trend while the logistic has a relative flatten one. The reason is that the logistic loss has a larger variance in the gradient norm and therefore clipping happens more frequently (approximately more than 80% gradients are clipped). As a result, the variance of influence will be relative small for logistic losses. Moreover, we vary the data scale (scale all samples uniformly such that all sample norms are less than a specific value), changing the variance of influence, as seen in the figures.
The last pane compares uniform, dynamic and exponential decay schedules Yu et al. (2019) using final losses relative to the uniform schedule. We set the exponential decay schedule to approximate the dynamic schedule by fitting σ̂t = σ0 exp(−kt) using the least squares method. The final losses are picked by grid searching the best T ∈ [1, 100]. We see that the advantage of the dynamic schedule over the uniform one increases when data scales less than 15. But we also notice some loss gaps decrease, suggesting that the data scale is not the inherent reason for the dynamic advantage. According to Lemma 4.1, the advantage should be proportional to T 2 Var(qt) which is shown to be decreasing when the data scale is larger than 15. When the data scale continues to increase, gradient clipping will change the curvature of the loss function. Therefore, a increasing Var(Tqt) is witnessed. Meanwhile, the loss gap decreases.
In the last row of Fig. 3, the DNN is experimented with the same setting. Though the influence increases by t, the variance is small and less dependent on the data scale in comparison to shallow models. Though the dynamic schedule estimated by retraining influences does not performs stably, the exp method still decreasingly depends on the variance of influence as expectation.

Review summaries:
Gradient Descent and related variants are the defacto standard algorithms for optimizing empirical risk functions. Since published models have been shown in the literature to leak private information, the problem of performing gradient descent under privacy constraints is an important one. Given a fixed privacy budget R, private gradient descent adds noise to the gradients at each round, ensuring overall privacy budget R by composition. However, this still leaves the question of what privacy schedule is best open, since any schedule whose privacy budgets sum up to R achieves the privacy objective. In this paper they compute the optimal privacy schedule from an accuracy perspective via a novel analysis of the convergence of private gradient descent on loss functions that satisfy the PL condition, which turns out to be exponentially decaying noise (increasing privacy budget for each round). These results extend to a privatized variant of the momentum-based gradient descent algorithm, although the dynamic privacy schedule has less improvement there. Experimental results show that dynamic privacy schedules lead to enhanced accuracy even absent convexity. 

The paper studies private gradient descent when the noise added to each of the iteration is dynamically scheduled. Prior to this work, the work of Zhou et al. tries to achieve the same for DP-SGD and they analyze their algorithm for many variants of adaptive gradient descent based method. The difference with Zhou et al. is that they do not gradient norm and the generalization property of DP. As a result, the authors claim that Zhou et al. achieves suboptimal utility guarantee.