On Dynamic Noise Influence in Differential Private Learning
Authors: Junyuan Hong
Zhangyang Wang
Jiayu Zhou
Venue:  (2021)
Keywords: privacy
private learning
dynamic policy

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 adds noise according to 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.

Under review as a conference paper at ICLR 2021
ON DYNAMIC NOISE INFLUENCE IN DIFFERENTIAL PRIVATE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Protecting privacy in learning while maintaining the model performance has be- come 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 used. We empirically show the connection exists for general non-convex losses, and the influence is greatly impacted by the loss eurvature.
INTRODUCTION
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, piterrential-rrivatte (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-preservigg 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, 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 specific privacy budget. One example is (Lee & Kifer, 2018), which reduced the noise magnitude when the loss does not decrease, due the observation that the gradients become very small when approaching convergence, and static noise scale will overwhelm these gradients. Another example (Yu et al., 2019), which periodically decreased the magnitude following a predefined strategy, e.g., exponential decaying 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 utiliry?
To answer these questions, in this paper we develop principled approach to construct dynamic schedules and quantify their utility bounds in different learning algorithms. Our contributions

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison of utility upper bound using different privacy schedules. The algorithms are T-iteration R-xCDP under the PL. condition (unless marked with *). The O notation this table drops other terms.
Unless otherwise specified, all algorithms terminate at step T = OIIn R. Assume loss functions are 1-smooth and I-Lipschitz continuous, and all parameters satisfy their numeric assumptions. Key notations: O,- bound occurs probability p. D feature dimension; N sample size; privacy budget; a: constant; other notations can be found Section 4. An extended table and explanation are available in Appendix A. Schedule (of)
Algorithm
Utility Upper Bound
GD+MA (Wang et al., 2017)
O
D N N
R
Adam+MA (Zhou al., 2020)
0 R,,
O₂ DInn(ND/(11-P N
GD, Noiv-rivvate
0 T
( (
GD+zCDP, Static Schedule
D
R
N
GD+zCDP, Dynamic Schedule
n T)/2
( (NER)
R T
Momentum+ZCDDP Static Schedule
P N + In NI (
Momentum+zZDDP, Dynamic Schedule
612 Legn (T- 0/2
D N
(1 + N T
are summarized as follows. 1) For the class of loss functions satisfying the condition (Polyak, 1963), we show that 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 dynamic schedule and result in an improved utility bound. 3) We empirically validate results on convex and non-conver (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).
RELATED WORK
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) 1) 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
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 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 char- acterizes the maximum utility that 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 more accurate estimation of the dynamic influence of step noise. Remarkably, by introducing 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
2

---

Under review as a conference paper at ICLR 2021
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-ar algorithms based on private gradients. Our work shows that considering the dynamic influence can lead to a tighter bound.
PRIVATE GRADIENT DESCENT
Notations. We consider learning task by empirical risk minimization (ERM) S(0)
1 = f(0;; xn) on a private dataset {an \ J==1 and 0 E RD, The gradient methods are defined as N
0++1= = 02- - 7)t V., where V. = (O() = N Σn =.) denotes the non-private gradient at iteration 4, n/ the step learning rate. V(()) = (((;;;,,, denotes the gradient on a sample V. Ta 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 learning task, only finite amount of privacy cost is allowed where the maximum cost is called privacy budget and denoted as R. (3) Generally, continuous and f(0) (the empirical loss) is M -smoohh.
assume that loss functions f(0; 2) (sample-wis loss) G-Lipschitz
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 (l - [=)]l S Glly ==|².
Definition 3.2 (m-strongly convexity). A function f(.) is m-strongly convex if f(v) 2 f(x) +
f)(x)) (y- x) + 122 y - 2=|2,, for some m > and all x. y in the domain of f()).
2
Definition 3.3 (M (M-smoothesss))
A function is M M-smooth w.r.t. l2 norm if f(y < f(x) +
Vf(=)" - x) + T
M
ly - x| for some constant M > 0 and all x, y in the domain of f(-).
For private algorithm M(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 rero-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 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 (p-zCDP (Bun & Steinke, 2016)). Let p >> 0. A randomized algorithm M: D" + R satisfies p-zCDP if, for all adjacent datasets d, d' E D D, (M(d)))M(d)) S pa, Vo E (1, 00) where (-1l-) denotes the Rényi divergence (Rényi, 1961) of order a.
zCDP provides linear composition of privacy costs of sub-route algorithms. When the input vector is privatized by injecting Gaussian noise of (0, of I) for the t-th iteration, the composed privacy cost is proportional E. Pt where the step cost is Pa- A. 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 = ....T:
0e411 0, neg = O. т) (V, + Gu,,NN),
where oe = g: is the gradient privatized from V, as shown in Algorithm 1, G/N is the bound of sensitivity of the gathered gradient excluding one sample gradient, and v, ~ -0, I) is a vector element-wisely subject to Gaussian distribution. We use d; to denote the noise scale at step and use a to collectively represents the schedule (oi....,oy) 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 modification, o6-), to enhance its utility. In this paper, consider two types of ((-):
o(m, 9.) = g. (GD), a(m, gt) = [3(1- 31-1 mm + - (1)))//((11 - (1)) (Momentum)
We now show that the PGD using Algorithm guarantees privacy cost less than R:
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Privatizing Gradients
Input: Raw gradients [v()) the full budget is R and R1 R.
[ (n N by default), uz residual privacy budget Rg assuming
1: Pr < 1/0 V 1/ - V
Budget request
2:
if Pr < R4 then
3:
R1+1 + R4 Pt
4: 9t 4 V Go.M/N, vi ~ 1)
Privacy noise
5:
M4-1 @(m,, 9th or 91 ift =
6:
return 1,, Re+1
Utility projection
7: else
8: Terminate
Theorem 3.1. Suppose f(0; x)) is G-Lipschitz continuous and the PGD algorithm with privatized gradients defined by Algorithm I, stops step T. The PGD algorithm outputs Or and satisfies p-zCDP where p S R..
Note that Theorem 3.1 allows or to be different throughout iterations. Next we present principled approach for deriving dynamic schedules optimized for the final loss f(0r).
DYNAMIC POLICIES BY MINIMIZING UTILITY UPPER BOUNDS
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 al., 2017). Due to the presence the noise and the limitation of learning iterations, optimization using private gradients is expected to reach point with higher loss (i.e., excess risk) compared to the optimal solution without private protection. Define 0" arg ming f(), after Algorithm is iterated for T times in total, the EER gives the expected utility degradation:
EER (0010(0+)))00000
Due to the variety of loss function and complexity of recursive iterations, exact EER with noise is intractable for most functions. Instead, we study the worst case scenario, i.c., the upper bound of the EER, and goal is minimize the upper bound. For consistency, call the upper bound of EER divided by the initial error as ERUB. Since the analytical form EER is either intractable or complicated due the recursive iterations of noise, studying the ERUB convenient and tractable alternative. The upper bound often has convenient functional forms which are (I) 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 al., 2019; Wang et al., 2017) for choosing proper parameters. Moreover, we let ERUB be the achievable optimal upper bound by specific choice of parameters, e.g., the and T.
In this paper, consider the class of loss functions satisfying the Polyak- Lojasewwjaii (PL) condition which bounds losses by corresponding gradient norms. is more general than the m-strongly convexity. If f is differentiable and M Mssmoohh then m-strongly convexity implies the PL condition.
Definition 4.1 (Polyak-Lojasienw) condition (Polyak, 1963)). For f(),, there exists μ and for every 0, (() 2 2n(s(0) - ((0)))
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 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 tighten the upper bound in gradient descent and its momentum variant.
4

---

Under review as a conference paper at ICLR 2021
4.1 GRADIENT DESCENT METHODS
For the brevity of our discussion, we first define the following constants:
1 O DG²
2RMN2 (f(61) - f(0)), K x and y - 1
1 K
(2)
which satisfy R 2 1 and y E [0, 1). Note that K. is the condition number of f(-) if f(: is strongly convex. A tends to be large if the function is sensitive to small differences in inputs, and 1 1/a tends to be large if more samples are provided and with 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 (Wang et al., 2017) by considering dynamic influence of noise and relax oG to be dynamic:
Theorem 4.1. Let a, K. and 7 be defined Eq. (2), and T = M. Suppose f(0; x:)) is G-Lipschitz and f(0) is M-smooth satisfying the Mojyak--oojsiewicz condition. For PGD, the following holds:
ERUB = TT + + qo, where qt 2
(3)
In Eq. (3), the step noise magnitude of has exponential influence, qt, on the EER. The dynamic characteristic of the influence is the key to prove tighter bound. Plus, on the presence of the dynamic influence, is natural to choose dynamic of. When relaxing qe to static 1, static of was studied by Wang al. They proved a bound which is nearly optimal except a In² N factor. To get the optimal bound, in the following sections, we look for the and T that minimize the upper bound.
4.1.1 UNIFORM SCHEDULE
The uniform setting of o, has been previously studied Wang et al. (2017). Here, we show that bound can be further tightened by considering the dynamic influence of iterations and proper T. Theorem 4.2. Suppose conditions in Theorem 4. are satisfied. When of T/ R, let a, 7 and be defined in Eq. (2) and let T be:
T = 0 [x(xl| (1+ ((++1)
(4)
Kix
Meanwhile, i I-c > 1, 1/a > 1/0r0 for some constant E (0, 1) and og > 0, the correspond- ing bound is:
x2
ERUB uniform
In
(5)
+ 1/a
KOx
Sketch of proof. The key of proof to find proper T minimize
ERUB = E = TT + + T- = -- + al - 7 = 7T + axx(1 - y'I
1-7
where we use 0e = -VTRR. Vanishing its gradient is to solve 7" 7 - In = 0. which however is intractable. (Wang al., 2017). T is chosen be (In(1/a)) and ERUB is relaxed as 77" ax?2 2 The approximation results in a less tight bound as O(a(1 + x (nn()/)))) which explodes - oc.
We observe that for a super sharp loss function, i.e., large n. any minor perturbation may result in tremendously fluctuating loss values. In this case, not-stepping forward will be good choice. Thus,
we choose T = in(1/>) In (1 [1+ In(1/>) s O (I:I (1+ + ) which converges to 0 as K + too. The full proof is deferred to the appendix.
4.1.2 DYNAMIC SCHEDULE
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, weighted sum, comes from error propagated from noise at each iteration. Now we show for any {gelg. > 0, I,...,T) (not limited to the y, defined in Eq. (3)), there is unique o; minimizing the weighted sum:
5

---

Under review as a conference paper at ICLR 2021
Lemma 4.1 (Dynamic schedule). Suppose or satisfy Σt=1 {gc). the following equation holds:
0=2 ?² RR Given positive sequence
Σ goo
T
(Ein (eevaa va) when oi
R
9:
min R
(6)
Remarkably, the difference between the minimum and T TE 9t. (uniform σ+) monotonically in- creases by the variance of qq: w.r.t. t.
We see that the dynamics in or come from the non-uniform nature of the weight qt. Since 9: presents the impact of the o, on the final error, we denote as influence. Given the dynamic schedule in Eq. (6), it is of interest which extent the ERUB can be improved. First, we present Theorem 4.3
to show the optimal I and ERUB.
Theorem 4.3. Suppose conditions in Theorem 4. I are satisfied. Let a, and 7 be defined in Eq. (2).
When t/e = M de (based on Eqs. (3) and (6)) and the T minimizing ERUB are, ie.
V(1/))T
[( 2 1+ 1
1
of = R 1- VT,T=
Meanwhile, when K 2 1 and 1/a 2 1/a0 for some positive constant Ogg, the minimal bound is:
( x²
ERUBdwnami min
R2 + 1/
4.1.3 DISCUSSION
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 limited number of samples. Formally, it is of interest to study when K is fixed and is large enough such that a >> Then we have the upper bound in Eq. (5) as DG In(N)) In(N)) M
s 0o =0('2a
[ka (1))
ERUBaniform min
s
(9)
where ignore and other logarithmic constants with Ô done in Wang al. (2017). As result, we get a bound very similar to (Wang et al., 2017), except that R is replaced by RMA = e²/ [I(0//) using Moment Accountant. In comparison, based on Lemma B.3, R 2p 2e 4 1m(6//) 4/ ln(16) Or satisfies p-zCDP. Because (1 R = RECDP > RMA when S 2 2l((1/5). As compared to the one reported in (Wang et al., 2017), our bound saved a factor of In N and thus require less sample to achieve the same accuracy. Remarkably, the saving is due to the maintaining of the influence terms shown in the proof of Theorem 4.2.
is easy to see
DG (NNR) which saved another In N factor in comparison to the one using the uniform schedule Eq. (9). As shown in Table such advantage maintains when comparing with other baselines.
Using the dynamic schedule, we have ERUDdynamic min
dynamic
<((a)= = o
Robustness. Besides sample efficiency, 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.c., a small M or has 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 mean higher final loss (the red dashed line) than the flatten curve (purple and blue lines). Such changes have more critical impact when only less number of iterations can be executed due to the privacy constraint. Assume a is some constant while k 1 1/a, we immediately get:
ERUBuniforr O (w:1 1+ 1 = ( 0
M
ERUB dynamic +(1).
DG2

---

Under review as a conference paper at ICLR 2021
Both robust, but the dynamic schedule has smaller factor since 1/a could be large number. In addition, the factor implies that when more samples are used, the dynamic schedule is robuster.
4.2 GRADIENT DESCENT METHOSS WITH MOMENTUM
Section 4.1 shows that the step noise has exponentially increas- ing influence on the final loss, and therefore a decreasing noise magnitude improves the utility upper bound by In N factor. How- ever, the proper schedule can be hard to find when the curvature information, e.g., K, absent. A parameterized method that less de- pends on the curvature information is preferred. On the other hand, long-term iterations will result 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.
Figure 1: Private gradient descent repeated 100 times on two differently-curved loss functions. Solid lines optimization trajectories and dashed horizontal lines are the averaged final losses.
Alternative to GD, the momentum method can mitigate the two is- sues. It was originally proposed to stabilize the gradient estimation (Polyak, 1964). 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 mo- mentum 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 based on gradient norm, which results a looser bound (see Table 1).
The momentum method stabilizes gradients by moving average history coordinate values and thus greatly reduces the variance. The @(m,, 9t) can be rewritten as:
M++11 <(m), 9c) Vt+1
Be 0++1 3v, + (1 B) = (1 - E g gt 9v, 0, (10)
where 3 E [o, 1]. Note ut+1 is biased estimation of the gradient expectation while m4+1 is unbiased.
Theorem 4.4 (Convergence under PI. condition). Suppose f(0;; xx.) is G-Lipschitz, and f(0) is M- smooth and satisfies the Polyak-Lojasiewicc condition. Assume 3 + " and B E (0, 1). Let 1 2nd
nt.
and 1jo < 8 (VI+ 6487(1 -)- -1)-
Then the following holds:
T
EER (T" + 2Rmoo Us(o,T) (((())) f(())) -
-52M
o E 10
(11)
2M
noise
momention effect
70
1
where
7
1=
3(1 - 8)3 110
1/0 2 0,
(12)
K
4
Us = Σ T- (1
3)2
Σ
82(1-0)
(13)
(1- 3t)2 i=1
The upper bound includes three parts that influence the bound differently: (I) Convergence. The convergence term mainly determined by no and k. Yo should be in (0. s)) such that the upper bound converge. A large Too will be preferred to speed up convergence if it does not make the two terms worse. (2) Noise Variance, The second term compressed in U3 is the effect of the averaged noise, Ei=1 g2(t-1) One difference introduced by the momentum is the factor (1 3) 8t) which is less than 7¹ at the beginning and converges to a non zerz constant 1 - B. Therefore, in Us. TT- - 31 - will be constantly less than 7 meanwhile. Furthermore, when > T. the moving average Σ - (3((--t) smooths the influence of each o,. In Appendix D, we will see that the influence dynamics is less steep than that of GD. (3) Momentum Effect. The momentum effect term improve the upper bound when ?o is small. For example, when B = 0.9 and
0.99, then To & 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 insight the effect of dynamic schedule, we provide the following utility bounds.
7

---

Under review as a conference paper at ICLR 2021
Theorem 4.5 (Uniform schedule). Suppose the assumptions in Theorem 4.4 are satisfied. Let of = R,R, and let:
Ki t max s.I. 7 1-1 2 - T 0 (0(m) In (1+
10
)1
1 - gr
KO:
Given some positive constant and (o) > 0 with 1/a > 1/000. the following inequality holds:
ERUBmin S S nk+aa/a [Trrr + ---11nn In (1
n²
1/0
Theorem 4.6 (Dynamic schedule). Suppose the assumptions in Theorem 4.4 are satisfied. Let 1-8
Use the following schedule: a' 7(1 71179991 B < 2f and T = maxt t s.I. yf 1-
2000
qi of R Σ i=1 V
Tohn
o
70
170
KO
where 9: = - T
St + -T-lo2r
c2
TTyF for some positive constants C1 and Cz. The following
inequality holds:
T ERUB S - + 21 Σ Rqio ERUBmin 00
KO
Ko
TT + [rss
POCE + Y/0
KO + 1J0
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 3) 1 9 3²), increase the influence of the under-presented initial steps and decrease the one of the sensiivve last steps. Counterintuitively, the preferred dynamic schedule should be increasing since d decreases when & S T.
4.3 PRIVATE STOCHASTIC GRADIENT DESCENT (NEW SECTION ON REBUTTAL)
Though PGD provides guarantee both for utility and privacy, computing gradients of the whole dataset 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 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, focus the random subsampling with replacement since 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 a by n because the term is from the sensitivity of batch data (see Eq. (I)). For elarity, we assume that T is the number of iterations rather than epochs and that V, is mean stochastic gradient.
When a batch of data are randomly sampled, the privacy cost of one iteration is ep² /a, where c some constant, p = n/N is the sample rate, and 1/a is the full-batch privacy cost. Details of the sub-sampling theorems are referred to the Theorem of (Yu et al., 2019) and their empirical setting. Threfore, we can replace the privacy constraint E, p² /o?
by E, 1/0? R' where R' R/p² 2² R. Remarkably, we omit the constant because it will not affect the results regarding uniform or dynamic schedules. Notice 22 in the is replaced by n nt' N2 R. Thus, the form of a not changed which provides convenience for the following derivations.
n²
Now we study the utility bound of PSGD. To quantify the randomness of batch sampling, we define D such that V, V, oyEt/ for some positive constant 0 Because & has similar property to the privacy noise V/, we can easily extend the PGD bounds to PSGD bounds by following theories.
random vector with [E[x]] 0 and E || <
Theorem 4.7 (Utility bounds of PSGD). Let a, K and r be defined in Eq. (2), and n) +.4 Suppose f(; is G-Lipschitz and (Ø) is M-smooth satisfying the Polyak- Lojasiewicz condition. For PSGD, when batch size satisfies
max(NvR, 1), the following holds:
ERUB = TT + Og
R Σ 9:07 where qr 2 TTa, 11/0 R.'
(14)
where 0ig 2uV'R(((0)-1(00))
D
8

---

Under review as a conference paper at ICLR 2021
Theorem 4.8 (PSGD with momentum). Let ag 3 f(01)) Suppose assumptions in Theorem 4.4 holds. When butch size satisfies n max VR, 13, the Us(o,T) has to be replaced by
D
Ü3 - Ug + U3, with aR'U3 S a
(15)
when PSGD is used.
As shown above, the utility bound of PSGD differs from the PGD merely by 0g Note dg O( D NZR which fits the order of dynamic-schediee bounds. In addition, a and other variables are not changed. Hence, the conclusions w.r.t. the dynamic/uniform schedules maintain the same.
EXPERIMENTS
We empirically validate the properties of privacy schedules and their connections to learning algo- rithms. 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 q: (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 1. 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 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.
We lastly evaluate the impacts from momentum in the Right Pane, using 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 (expinff) has comparable performance of the influence modeled by linear combination of two reverse exponential functions (momexpinff)). The latter only shows advantage in the setting that data scale is 25 and the number of iteration 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.
110-
-225
1%
vanacom
18. 15D 13.5
Figure 2: Comparison of dynamic schedule and uniform schedule on different data scale. Left pane is the influence by iteration estimated by retraining. The rest two are the relative loss by varying data seale (left axis with solid lines) and the variance of influence (right axis with dashed lines). The middle is the MNIST35 dataset consisting of 1000 digit 3 and 5 images using quadratic regression. The right is the final loss on subsampled MNIST dataset of 1000 training samples and 50, 000 test samples when using DNN and momentum methods.
6 CONCLUSION
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 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 results through empirical studies.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang, Deep Learning with Differential Privacy. In CCS: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pp. 308-318, New York, NY, USA, 2016. ACM.
R. Bassily, A. Smith, and A. Thakurta. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473, October 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private Stochastic Convex Optimization with Optimal Rates. In Advances in Neural Information Processing Systems 32, pp. 11282-1 1129.. Curran Associates, Inc., 2019.
Mark Bun and Thomas Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography, volume 9985, pp. 635-658. Springer Berlin Heidelberg, Berlin, Heidelberg, 2016.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially Private Empirical Risk Minimization. Journal of Machine Learning Research, 12(Mar):1069-11100 2011.
Rachel Cummings, Sara Krehbiel, Kevin A Lai, and Uthaipon Tantipongpipat. Differential Privacy for Growing Databases. In Advances in Neural Information Processing Systems 31, pp. 8864 8873. Curran Associates, Inc., 2018.
Damien Desfontaines and Balázs Pejó. SoK: Differrntial Privacies. arXiv:1906.01337 [cs]. June 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography, Lecture Notes Computer Science, pp. 265-284. Springer Berlin Heidelberg, 2006.
Cynthia Dwork, Alan Karr, Kobbi Nissim, and Lars Vilhuber. On Privacy in the Age of COVID-19. Journal of Privacy and Confidentiality, 10(2), June 2020.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 439 449, New York, NY, USA, June 2020. Association for Computing Machinery.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model Inversion Attacks That Exploit Confidence Information and Basic Countermeasures. In CCS: Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, CCS '15 pp. 1322-1333, New York, NY, USA, 2015. ACM.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the Last Iterate of SGD Information Theoretically Optimal. In Conference on Learning Theory, pp. 1752-1755 June 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear Convergence of Gradient and Proximal- Condition. In Machine Learning and Knowledge
Gradient Methods Under the Discovery in Databases, Lecture Notes in Computer Science, pp. 795-811, Cham, 2016. Springer International Publishing.
Diederik Kingma and Jimmy Ba. Adam: Method for Stochastic Optimization. 14X1v:1412.6990 [cs], December 2014.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( (6(11))2278-22) 23244, November 1998.
Jaewoo Lee and Daniel Kifer. Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 1656-166600 1665, New York, NY, USA, 2018
ACM.
10

---

Under review as a conference paper at ICLR 2021
Yurii Nesterov and B.T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming. (08(1):177-2055 August 2006.
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiv Kumar. AdaCliP: Adaptive Clipping for Private SGD. arXiv: /908. 07643 [es, stat], October 2019.
B. T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathemat- ics and Mathematical Physics, 3(4):864 878, January 1963.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 4(5):1-17, January 1964.
Ning Qian. On the momentum term in gradient descent learning algorithms. Neural Networks, 12(1): 145-151, January 1999.
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poezos, and Alex Smola. Stochastic Variance Reduction for Nonconvex Optimization. In International Conference on Machine Learning, PP. 314-323, June 2016.
Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium Mathematical Statistics and Probabiliry. Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, May 2014.
Shai Shalev-Shwartz, Nathan Srebro, and Karthik Sridharan. Stochastic Convex Optimization. In Proceedings of the 22nd Annual Conference on Learning Theory, COLT '09, pp-
2009.
R. Shokri, M. Stronati, C. Song, and V. Shmatikov. Membership Inference Attacks Against Machine Learning Models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18, May 2017.
Om Thakkar, Galen Andrew, and H. Brendan McMahan. Differentially Private Learning with Adaptive Clipping. arXiv:/905.088 03871 [cs, staf], May 2019.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially Private Empirical Risk Minimization Revisited: Faster and More General. In Advances in Neural Information Processing Systems 30, pp. 2722- 2731. Curran Associates, Inc., 2017.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially Private Empirical Risk Minimization with Non-convex Loss Functions. In International Conference Machine Learning, pp. 6526-6535. May 2019.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-based Analytics, In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17, pp. 1307-1322, New York, NY, USA, 2017, ACM.
Lei Yu, Ling Liu, Calton Pu, Mehmet Emre Gursoy, and Stacey Truex. Differentially Private Model Publishing for Deep Learning, proceedings of 40th IEEE Symposium on Security and Privacy, April 2019.
Yingxue Zhou, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Arindam Banerjee. Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds. arXiv:2006. 13501 [cs, stat], August 2020.
11

---

Under review as a conference paper at ICLR 2021
A COMPARISON OF ALGORITHMS
Table 2: Comparison of empirical excess risk bounds. The algorithms are T T-iteration R-zCDP or equivalently (c, 6D- under the PL condition (unless marked with for convexity). The O notation in this table drops other In terms. All algorithms in the second part terminate at step T = OIn R²R) Assume loss functions are 1-smooth and 1-Lipschitz continuous, and all parameters satisfy their numeric assumptions. Key notations: Op - bound occurs in probability p; D feature dimension; N sample size; - privacy budget: G constant.
Algorithm
Schedule (of)
Utility Upper Bd.
*GD+Adv (Bassily al., 2014)
In(N/6) Regs
0
D N NH,55 Dia NER D (1((())
GD+MA (Wang et al., 2017)
O Re, 2 In(m/8)
*GD+Adv+BBlmp (Cummings et al., 2018)
RLONI-E
Adam+MA (Zhou et al., 2020)
T O R
O₂
DIn(NDs/(11 (c/(1-D))))) N N
GD, Non-Private
0
O
D NER
GD+2CDP, Static Schedule
Dln NER
Ii
(t- T)/2
GD+*CDP, Dynamic Schedule
O
1
N
Momentum+ZZDDP Static Schedule
T
NJR (c+ In N NI
R
Momentum+zCDDP, Dynamic Schedule
O
T-t +00
(T (7-
N N I (T>t))
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 Re,5 with R R are the privacy budgets R when the private algorithm is of corresponding algorithms. Specifically, R..5 = 22/In(1/0)
(e, 6)- with e < 2 (1)6))
PGD+Adv. Adv denotes the Advanced Composition method (Bassily al., 2014). The method assumes that loss function is I-strongly convex which implies the PL condition and optimized variable in convex set of diameter w.r.t. 12 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 enhanced utility bound, as result.
PGD+Adv+BBlmp. 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
Adam+MA. The authors prove convergence bound for the gradient norms which is extended to loss bound by using 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,
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.
Mome 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 bound degraded the GD bound.
12

---

Under review as a conference paper at ICLR 2021
Table 3: Comparison of true excess risk bounds. The algorithms are Titteration 1 Rt2CDP or equivalently (e, 8)-D under the j-stroonlyy-conexx condition. The O notation in this table drops other In terms. Assume loss functions are 1-smooth and 1-Lipschitz continuous, and all parameters satisfy their numeric assumptions. marks the method with convex assumption. Utility Upper Bd.
Algorithm
T
GD+Adv (Bassily et al., 2014)
D Nin11/2 PUN R
N
SVRG+MA (Wang al., 2017)
DiuN
O N
SSGD+zCDP (Feldman et al., 2020)
+
2/D VIIN
In
N²
VN
16D/R'+4N
* *SG+MM (Bassily et al., 2019)
o
max
min g 32D
R J.
GD+zCDP, Static Schedule
O 1p-p
G²
+
O(n 2
GD+zCDP, Dynamic Schedule
O1-p
G2
Din(1/p)
O "D²)
PN
Momentum+77CDP, Static Sch,
1
11-p
G²
Din(1pp) NR
(c + In NT. x
O N²R)
BN
Momentum+ZCDDP Dynamic Sch.
O1-p
G²
Din(1/m) NR
cD (1
Oln R)R)
RN
NER
GD, Non-Private
O N
O(n D
xAR)
GD+zCDP, Static Schedule
0
DlaN)
O(n D
NER
GD+zCDP, Dynamic Schedule
O(n A²R)
N
Momentum+ZCDP, Static Sch.
0 (c Ia N
O(n N²R
NºR
MoDe Dynamic Sch.
0
N (
cD
O(n D
NaR
N
A.1 COMAPRISON OF GENERALIZATION BOUNDS
In addition 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 the inherent data distribution. By leveraging the generic saaming-theory tools, we extend our results to the True Excess Risk (TER) for strongly convex functions as follows. For model 0, its TER is defined as follows:
TER A Ex=xx [[]( miing Ez-x(f(0;a))
where the second expectation is over the randomness of generating 0 (e.g.. the noise and stochastic batches). Assume a dataset consist of N samples drawn i.i.d. from the distribution X. Two approaches could be used extend the empirical bounds 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 al. (2014) achieved In N bound with 22 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 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-Shward et al., 2009) (restated in Theorem A. we relate the EER to the TER.
Theorem A.1. Let f(0:2) be G-Lipschitz, and f() be p-strong convex loss function given any & E X. With probability at least 1 over the randomness of sampling the data set d, the following inequality holds:
2G TER(0) S uN V1(0) - S(0-)
4G
(16)
PHN
13

---

Under review as a conference paper at ICLR 2021
where 0" arg ming (0).
To apply the Eq. (16), we need to extend EER, the expectation bound, high-probability bound. Following (Bassily et al., 2014) (Section D), we repeate the PGD with privacy budget R/ k for ls times. Note, the output of all repetitions is still of R budget. When denoted as (RR). Then the EER of one execution of the & repetitions is F(R/k) where privacy is accounted by zCDP. When = logg( (1/p) for p E [0, 1]. by Markov's inequality, there exists one repetition whose EER is F(R/ logz (1/p)) with probability at least 1/2 1 p. Combined with Eq. (16), we use the bounds of uniform schedule and dynamic schedules in Section 4.1.3 to obtain:
1, let the EER of the algorithm be
G
Dln((N) In(l/)) 4 p
)
TER uniform
(17)
unN
NR
Dln(1/p) -)
G2
TER TER dynamic
(18)
uuN
NR
where we again ignore the x and other constants. Similarly, we can extend the momentum methods.
(2) True Risk by Unfirom Stability. Following Bassily al. (2019), we the uniform stability (defined in Definition A.I) 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 s-
uniformly stable w.r.t. the loss function f if for any neighor datasets d and d', we have:
suPzex ([((M(();=)) - [(M(d);; S
where the expectation over the internal randomness of M.
Theorem A.2 (See, e.g., (Shalev-Shwarts & Ben-David, 2014)). Suppose M DD + θ is
s-uniformly stable algorithm w.rt. the loss function f. Let be any distribution from over data space and let d ~ DN, The following holds true.
EA-DD [MM - - d)ll S 8,
where the second expectation is over the internal randomness of M. f(M(d); D) and J 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 nj < 2/M for M smooth, G-Lipschitz f [0; z)). Then PGD is s-umiformly stable with = G²Tn/N.
Combining Theorems A.2 and A.3, we obtain the following:
TER S EER +G2 TI N
Because EER in this paper compresses a y or similar exponential terms, unlike (Bassily et al., 2019), cannot directly minimize the TER upper bound w.r.t. T and r in the presence of a polynomial form of TT and Therefore, we still use T OIn N²R) and rj for minimizing EER. Note that
GanIT S SOI N
G N
G
In
D D-
SO
MN
M
where we assume N > D and use IN < N. Because the term O (G2/M) is constant and independent from dimension, we follow (Bassily 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 additional method: Snowball Stochastic Gradient Descent (SSGD). SSGD dynamically schedule the batch size to achieve 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 In 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 N to In()). That implies fewer iterations are required for converging the same generalization error.
14

---

max Under review as a conference paper at ICLR 2021
B PRELIMINARIES
B.1 PRIVACY
Lemma B.1 (Composition & Post-processing). Let two mechanisms be M D - y and M'
Dr x y + Z. Suppose M satisfies (pt,a)-<CDP and (' satisfies (p2, -DPP for Vy y. Then, mechanism M" :D" 2 (defined by (z) (x, M(x)) satisfies (Pi + P2)-
Definition B.1 (Sensitivity). The sensitivity of gradient query V. to the dataset {a, [r: is
(v. = max
1 N
N D
1 Σ
(
max V
(19)
N
j=
N
where v!(") denotes the gradient of the n-th sample.
Lemma B.2 (Gaussian mechanism (Bun & Steinke, 2016)). Let f D + Z have sensitivity A.
Define a randomized algorithm M D - Z by M(x) f(z) + N0, 13. Then M satisfies
20 CCP.
Lemma B.3 ((Bun & Steinke, 2016)). If . is a mechanism satisfying p-zCDP, then M (p-
2/ p ///((1))), 8D for any
By solving p + 2/ pln(1/6) e, we can get p + (2 12/mm//00++
B.2 AUXILIARY LEMMAS
Lemma B.4. If max, |Ia and n Σn Tn 0, then the gradient sensitivity of the squared loss will be
a)) |1:11 < 1 A2(V) = max N xx) xx)
where OM is the set of all possible parameters 0, generated by the learning algorithm M.
Proof. According to the definition of sensitivity in Eq. (19), we have
(v max
|
A
Iz
x n
where we use i denotes the index of sample in the dataset. Here, we assume it is constant 1. We may get
A400- zi 2= =112,(0, - 101122 (x - 1)² 10:11 2f(0; ||
where f(0;x:;) {xxT 2 Thus,
1 22; 1|m,111
A V) i N
Since ||5 < and N
EN= Zn 0.
f(0)
1 2N
Σ
[1] - 2n, 0
1|
1 2N
Σ
1( ||11111110000001 + +]] [
1 (DM |1al| 1)
Lemma B.S. Assume assumptions in Theorem 4.4 are satisfied. Given variables defined in Theo- rem 4.4, the following inequality holds true:
Σ TT T+ 2(1 - B)m
T
E. gt-i
V
V.1l
<
3y
T-1 Σ
1 1|
b 1-
- 3)²
1=1
15

---

Under review as a conference paper at ICLR 2021
Proof. We first handle the inner summation. By smoothness, the inequality [V/ vf(vill M I| - yl holds true. Thus.
E B IV.
V.ll
S M
B 10, 0.1
M
8 10, 02 #
M
8h Σ ist-k 7/22+1 1/bs
S M
Bh
E
Σ 1-1
jー ni n6/03)
(Eire f-1
where the last inequality is by
inequality.
Because b.
I-m S I-B and
7o 2M
Σn 8 V
VeIl =
y 4(1
Σ
8k Σ
G |1++1|?
3)
3hh
|| 1| T(i 2 L - k:)
4(1 B)
||:+11|| 11
g* 2t t - i)
4(1
By²
h=0
|| 11
(20)
4(1 BY²
where I[-) 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 -
110
|1ue41 11
B*
b,
4M
3)
k=t-
1=1
%0
T
|1441
2
k
4M - 3
where we relax the upper bound by 1r conclusion:
I- S
1-3.
Using Lemma B.6 can directly lead to the
38
T 1 T |
LHS <
2
2M
3)3
13
1=1
Lemma B.6. Given variables defined in Theorem 4.4, the following inequality holds true:
T Σ x
1e:41 " Ein k3sh < (y
2,3
T-1 7 T-i
1041
(3- 3)
(
t=1
1=1
16

---

Under review as a conference paper at ICLR 2021
Proof. We first derive the summation:
(1(1,)) - Σ k= 3*k
3
801 S k)
k= 14
gmax((-is) -g
1 1-8 18
(t (t- 11-i),-- + Br- i+1
Bt
8 Bt
1- 3
1 B
1 1 3
(t 1) + BL-it1 -
1- 3
1- B
Now, we substitute U1 it, into LHS and replace t - by i.c.,, t = j + i, to get
T
( (t - 1)s8+1+ ge-it1 33
LHS-
10
1
1 1 3
|eeeall
1
T
T-
1
(1 - (0=1) + 1- 8
gr-it1 - B
1- 8
1=++1
|M44111 2
T-
Σ
7
T-
(i+))
1
j +
8i+1 8
1- B
1 1 3
1=1
11 T-i
g5+1 3
Σ
T-
||0++1
133
1-3
1 3
1
T-1
T-1
3 8
3 3
7
|1+41
1
8
1
7
Let B/7, we show
T-i
T-i
ja
ΣΣ
1=1
j=1
T-iT-i
0=1
T-i+1
T-411
aT T-i11
(T' 1)
a
(1 a)2
17

---

Under review as a conference paper at ICLR 2021
Thus,
LHS
<
1
T-1
||s+1|1
8
Σ
T-i
B 1=1
(1- a)
1 3
==1
1
T-1
Σ
7
|1++1| |
a
+
8
a
1
8
(1 0)
1 8
1=1
T-1
T-
|1++| 1|
(1
1=1
Because 7 8, < 3/y and
8
a <
2a
(1 a)
1
8 1
0
(1 a)²
Therefore,
LHS <
20
T-1 1
||:41
11
287
T-1
T-
1
2
(1 21 B)
33 3)
==1
Lemma B.7, Suppose y E (0, and B e (0. Define
1 1 8
max s.t. x01 2 3
Ift S 1 S -
for t 2
1 I,.... 1ft T, 1-3
8-
Proof. Define h(t) 1- (1 ) whose derivatives are h'(t) 11
In 2- In
= 11 [In 331 + In 3)]
= t- [] - (3((1 + +og, [3]] Iny.
Simple calculation shows - (1( + log, 3) = - log B < 0 and lim; 1 - 8 (1- log,, 3) = 1. When t = log,s(1 + log, B) denoted to. 1 - 3e (1 + log, B) = 0. Be- cause (3(1 + log, (8 is monotonically increasing by and -0 Iny is negative, 1/(1) 2
if t0. Otherwise, (t) < 0. Therefore, /t(() is concave function. Because h(1) 1 8 and Thus, for all f E [1, we
T(T) = - 1
21 B 0, (t) 2 1 - 33 for f = 1.... Ā.
have 1-8 < 1- T-
Fort > f. because
1- B monotonically increases by t, we have 1-8 1-8
1-9 1-97
C PROOFS
Proof of T'heorem 3./. Because all sample gradient G-Lipschitz continuous, the sensitivity of the
averaged gradient is upper bounded by G/N. Based on Lemma B.2, the privacy cost of g: is 20
I
Here, we make the output of each iteration tuple of (0++1, 1t=1). For the 1st iteration, because 0, does not embrace private information by random initialization, the mapping,
02
= 0,
m
For brevity, when say the privacy cost of some value, e.g. gradient, actually refer to the cost of mcchanism that output the value.
18

---

Under review as a conference paper at ICLR 2021
is P1 P1-DCDP where A 20?
Suppose the output of the t-th iteration, (ft, U.). is -ZDP. At each iteration, we have the following mapping (fr, t2) (fe+1, 0(41) defined as
u++1
o(vr,
]
Oc+1
O2
( 9t)
Thus, the output tuple (0s+1, ut+1) is (Ōe + 20?
}-ZCDP by Lemma B.I.
Thus, the recursion implies that (0T+1, VT+1) has privacy cost as
1
PT+1 Pr
R
RT)
S R.
2
2
2
2
2
[=
1m
Let pr+1- Then we can get the conclusion.
C.I GRADIENT DESCENTS
Proof of Theorem 4.1. With the definition of smoothness in Definition 3.3 and Eq. (1), have
f(0++1) - f(0,) & n V. (V, + Gows/N) + _ M IV + Go,u/N112
-1 Mnd V. (1 - V. GoLuLN Mn² ||Go,u//N|* S 2-2pmel1 Mm))((())) f(0))) MM Gown/N
+ Mnj ||Go,u/N|].
2
where the last inequality is due to the Polyak- condition. Taking expectation on both sides, we can obtain
M
+ M 2
E[f(0++1) -(((()))) < 2pmo(1
2 ne ( -
(n, |M|
which can be reformulated by substacting f(0*) on both sides and re-arranged as
M n.)
[E]f(0))--((8)) f(0)) + M 2 Gn
[[f(0++1] - f(())=(()))))))))))r)))) < 2pm (1
2
Recursively using the inequality, we can get
M (1)) (E[f(0))] f(()))
E(f(Or+)) S II
2pmie1
MD T
II
(1- 2pm: 11-2
M n1)
(n.Goi/N)..
2
2
Let 17 1/M. Then the above inequality can be simplified as
T
MD
T G
[] f(0)) ~ (((T()))))))) -
2
2R
N
1=1
- R
00? (B f(0r))
= =(1" R Σ T 20? (f(0)) -(())))((0))
19

---

Under review as a conference paper at ICLR 2021
Proof of Theorem 4.2. The minimizer of the upper bound of Eq. (3) can be written as
T arg min TT + axx(1 (11--1--
(21)
where we substitute o² = T/R in the second line. To find the convex minimization problem, we need to vanishing its gradient which involves equation like Ty for some real constant However, the solution Wx(C) for some integer k where W is Lambert W function which does not have simple analytical form. Instead, because 7² O, we can minimize surrogate upper bound as following
In(1/7) In (m1(1/1) if ka + In <
T = arg min 7 + arT
(22)
ka
where the surrogate upper bound in the second line and utilize 7 1 However, the minimizer of the surrogate objective is not optimal for the original objective. When is large, the term, -ax""T, cannot be neglected as we expect. On the other hands, T suffers from explosion + xo and meanwhile 1/7 + 1. The tendency is counterintuitive since small T should be taken for sharp losses. To fix the issue, we change the form of T as
(1 In(1/7)
(23)
In(1/7)
which gradually converges to K + co.
Now we substitute Eq. (23) into the original objective function, Eq. (21), to get
1 1 + +* (1+ In(1/7) ]
(24)
1+ In(1/7)/aa
Notice that
1 (n(x)))(((((((0))00 In(1 + 1/(K - 1)) because i 2 1-c >
S
for some constant c E (0, 1). In addition,
In(1/r) In 1/k) 2 1/k.
Now, we can get the upper bound of Eq. (24)
ERUB uniform
R
1 1 k In
1
1/a
сka
K
< + 1/a
In
1
+
In
Kax
x²
< C
02
In
1
K 1/a
for some constants C1, Cg and large enough
1. a. Also, we can get the lower bound
ERUBuniomm
CAS
+ xInn (1+ (+11)
K + 1/a In (1 (1+ 1
x²
_ Kix
CK + 1/a
where we use the condition c E (0,1), 1). Thus, ERUBunifom. = (M In (1 ma))
Kt1/a
Proof of Lemma 4.1. By ΣT - ET and Cauchy-Schward inequality, we can derive the achiev- able lower bound as
R
Σ 9:0
Σ
1 Σ
got >
Σ
q
o
1=1
20

---

Under review as a conference paper at ICLR 2021
where the inequality becomes equality if and only if s/o qoo, i.e., (s/qi) 1/4 for some positive constant The equality Σ of R immediately suggests v3= R 2Er vq.. Thus, we get the d,.
Notice
(EE)va))
2 V
T
2
EE9 9t
=
9:
T
Σ
9i
T Varlge]
(25)
where the variance is w.r.t.
Proof of Theorem 4.3. The upper bound of Eq. (3) can be written
T
ERUB -
TT
1=
= 7
E
T
V/T-t
T/2 2
where we make use of Lemma 4.1. Then, the minimizer of the ERUB is
T/2 2
T arg min T +a a
V7
a a /72
2 log,
(26)
We can substitute Eq. (26) into ERUBdya to get
ERUB dyn
a
+a - v/ )
1 )(1
/²
a
min
a //
a v7)
-aa(1 (7)
a(1 vワ)
a(l /7) -2)-
+
(a(1 -2 + 1)2
a(1 -2
a(1 - --)-2+1
Notice that (1 17) = x² + x² + 2N K(K = <(2x - 1 + 2/k(m= and it is
bounded by
n(2x - 1 + 2 K(N 1)) S 4n²
R(2k - 1+ 2 |< 1)) x(2x (3k 2) 2) 2 (N 1)( 1)) K(-K +2 2n 2) =k?
Therefore, N (1-,1) (1-v7) -1 2x, with which can derive
x²a <
ERUB4yn dyn
min
k2 x2a +1
ka a
1 R2a
4y dyn min
4x +1
4
2x²a
Thus, ERUB min
? Ka+1
21

---

Under review as a conference paper at ICLR 2021
C.2 GRADIENT DESCENTS WITH MOMENTUM
Proof of Theorem 4.4. Without loss of generality, we absorb the Co,/N into the variance of v/ such that 24 NO, Co? N I) and gi V. + vt. Define by = -
By smoothness and Eq. (1), we have
1(0++)) - ((0,) S (0(+) - -0) +
M
|0++1 - 0el
2
mh by V u++1 + M
1
m0
||ee+1 11?
07
2
(164 1e41 112
bbbe Vel12 - -112421l1
+ M 1h
1
|1tt2ll
1?
83
2
0y
V1 - - "tt 63
1tt (1 Mn.)
(27)
62
2
Ui(()
where only the U1 (t) is non-negative. Specifically, U1(t) describes the difference between current gradient and the average. We can expand 1/ to get an upper bound:
(i(1) 14 V.- 11
(1 B) Σ
8 - -11- B) Σ. 8r
Σ ge (V. (Vi- -.).|
(1 8)8
Σ g (V (iA + Σ/ -e-1(V, -..)l"
(1 8)
| 8 w./l" + 8 - -gi)
2(1 8)8
< 2(1 1 9)
be Σ i=1 8 -... +(1 3)
Σ i vi
U2(t) (gradient variance)
variance
where we use || 21 (||= + |1ll1) < 2[|1=|| + 1l The last inequality can be proved by Cauchy-Sehwarde inequality for each coordinate.
We plug the U1 (t) into Eq. (27) and use the PL condition to get
f(0++1) - f(0)) < Ui (t)
Th |.
2
Me by
(1
- Mnt) ||te+1l1
1
2
brU2(1) + (1-3) / 3 wi] [
< m | + :7
2(1 3)
Tt (1 Mn)) 11
b3 2
< --2mm)(f(0)) - )(0))) +
2(1 3) (2(() +
2(1 - -1)22tt
Σ 1=1
g 's
b,
83
(1 (Mn) |1
22

---

Under review as a conference paper at ICLR 2021
Rearranging terms and taking expectation to show
+ 2(1 2(1 (LL-9)- T)
B[S(0++1)] - -((0)= S (EL[ - [(0)))
Σ i=1
B ||
biž
2(1 101-3100 33m7 E[U2(t)] b8
1tt (1
Mr) ) ||t++11 2
b,
2
(B[[((0))] - -((0))))))))))))))))))))))))-- +
2(1 8)
T/t
Σ i=1
32(1-0) C2 Do?
bj
N2
2(1 ((1--)mm E[U2(())
11 (1 Mn, E ||1+111 1
b,
b 2
where y = 1 -n// 1- - 24m7. The recursive inequality implies
T 2(1 - 3) n
C² C2
B[f(Or+1) ) f(0)) S ~~((((0)) f(0))) +
82(1-1)
by
N2
Σ 1=1
7T T 2(1 - 3)me B[[2(()]
Σ
7
T-t 11
(1
1
|F |
2
TT
+ 21o Σ 1=1=1
T T-
(1
11-99
-3)²
32(1-00 oo
s(0")
by
Us
+
7T T- 2(1 - -mym B[U2(t)]
Σ
I mt
1
Mn
|E |
be
bi
2
(a(Aa)
where we utilize
DC
and ne
nio 2M
ZMNTH ((01)-
By Lemma B.5, we have
Σ
T
2(1
3)T Uz(t) S 2M - () 3)2
T-1 38
Σ
7
T-
|0 2
b
1=1
1=1
Thus, by 1 2 1,
b.
T-1 7T T- |0:+1|| 11
Un(1) < 2M(1 - () - 33
770
(1
170
T
E |041 1
2M
T
700
7
T-E 11 2
2M
where
By
3/4
< 1
4 710
(7- () 3)3
10 =
4 770
(1 - (1-)) By3 nd
When small enough no. e.g., Specifically.
(7 (1-=3)((1- - -333
64,7
7o <
1+ ( (1 3)3
888
V1 + -1)66(1-8)--1(11111
33 11
We can have ( 2 O. By the definition of (2(T, o), we can get
T
Elf(O++)) -(0") < (TT + 2n (f(Oz) -((0))))
110
T
11
2M
1=1
23

---

Under review as a conference paper at ICLR 2021
Proof of Theorem 4.5. Since or is static, by definition of U3 in Theorem 4.4,
1 (1 - B)²
U3
2(( 0²
(1 81)2
T-t (1 - g)
0
32(1-1)
(1- B1y² 1=1
T
T-t (1- 8)² 1 g
(1 (1- f/)2 32
T-t 1 1+ 3
0²
1 f 1+B
Because 1-8 1+,9 1- Bt 1+3
< 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
T
1
- B
U3 S 0²
T
1=1 1 g
7 T- 1- B
T E
y T-t 1- B
2
+ 0²
1=1
1- 1- Br
1- 3
x-110-1 0² Σ 1=++1 -=1
T
--gst-1
T-P --
0² 07
T-1
d²
1-
T
F-T -1 T
-- 1-7
TT
7
where we use T//R R in the last line. Without assuming T > T. we can generally write the upper bound
T TT -" min((fTT max U3 S RR
? p-T -1
01)
1 1-7
By Theorem 4.4, because Ç 2 0, we have
ERUB < ~n + 2RRnaasss
- L T ?
y FT -
1 1-7 .0} )
min T) + max
where a' = 2naa.
First, we consider T S T. Use T
lm[1/7]
In (1 +
Ro ka
= [o
In
+
Ra
to get
ERUB
a
1 I+a'y in(1/r)
In 1 +
170
)²
a + no/R
ka
VI
a
1
8k a
2
(1 +
no
+ no/R
170
ka
8k2a a
In²
2
[
+
770
K + 7o/a /
no?
ka
4k
0
1 +
A + no/o
7
2²
0
K + 1//a
24

---

Under review as a conference paper at ICLR 2021
where we used In(1/7) 2 no/n and In(1 + x) S / for any > 0. Second, when T f,
ERUB S (1+ o' I T+ - -1
1-7 7
0 TT 20 Tkl7 - - 77))
Make use of T
1
In (1 +
1b
show
In(1/5)
ERUB < 0
K
4 a
(r
K
In (1+ no)
maa
K K 70/0 /
NOT
K+
k
no/a a
0
R²
f- 1 In
(1+
770
Ki + 70/0a
ka
Proof of Theorem 4.6. By Lemma B.7, can rewrite U3 as
- + (1 - 3)
U3- = Σ 1=1 11 - 8')
T 7 T- (t--1 1)
32 320t-110 + 2
-= T (T-222(0-1) 2(
32(1-1)
p 2 2 1)
32(t- 0, +, 21
E
T
2 T't
(2(t-0)
1=
V/2
We derive V1 and V/2 separately.
For V1, we can obtain the upper bound by
2(1-11 E' i=1 32(1-0)
Vi2
2-2
7d
B2(1-0) 2
t=1
g 8-20 2 4
f-2
t=1 (7/82)*
i=1
(782) (7/82) f+1
3 24
1=1
1 7112
- f-1 +1(
2 3
1- 7/2
(7/82)7+1-8
2 3
31 - 0
i=1
1 1- 7/2
1-1 7007
71 7,32)
Σm im)
%00
7(7 - 322
For V2, we can derive
V2
T
T-t
1=1 (2(( oo
1=
92(1
Σ x
|= TT !
32(1-1)
Lizl
1=1
Σt
T
T
2 1
T- + I
+- E'
32
|-|
25

---

Under review as a conference paper at ICLR 2021
We first consider the first term
Σ
T
B2(1-00
i=1
T
-11((((-1) (0(1-
T
T
2i 2
t= T -B22
T
0
( 17)
(82/7)T+1
(82/7)
T41-
g2 41
7 - B2
Similarly, we have
T-T
1
f-1 E 32(1-1)0
1=1
++ 32(
i=1
7- 82
1 g2 g2(1+1-1)
02.
1=1
7- 32
Thus,
Σ i=l
T
T+1-i 12(T+1-1)
f
7
T+1-i TT- -F--222(+1)1
1/2
7- 32
i=1
7- g2
T
T++--
32(T+1-1)
t
xT- (2(T-1) g2(T+1-00
2
7-80 -82
q 32
- -22(4+1-1)
Σ
f
1 T-P
ga 0.-
0 +
f+1
7 182
iml
Substitute V1 and V2 into Us to get
y -
U3 S T
7 0 + 2
"
7/7 ,2) i=1
7- B2
+ 1. T+T-2
82(
i=1 7 - 13
nt
T++-- -82(T+1-1)
Σ i=1
(7 +
132(f+1-1))
+ 22 2
0?
7(7 - )
- B3
2TT
2F-2 7 o'
7 T+1- - (-((T-11) 1-1)
0,
7/7 32)
i=1
1=1+1
7- B3
T
1=1 400
where
TSp + 2(1-1) 2 T+1-i- -82(T+1--)
7 T+t
T- I T
7(7 82)
32
S 0n T ++
I T + T 022 T T TTss
27
where C1
and C2 7-33
705-84
26

---

Under review as a conference paper at ICLR 2021
When T > T, by Lemma 4.1, the lower bound of R ET= 9:0 is
Σ 1=1
Vt
7
Van'
+ E =+ V V
1=1
T/22
g( -T-T-1117
C17
+ V02
1 VT
V7 -1
1 - 7-/2
71f (P-TT-1)/2
VC1
02
1 V7
1 V7
-11//
11/2 - T// 2
0
C2
1 v
which is achieved when
of R
T
qi
By Theorem 4.4, because Ç 2 0, we have
ERUB S n" + 2 2RgouUs
= + 20 Σ
Rgoo
And the minimum of the upper bound is
/(T-1)/2 - T/2 (1T-11/2-977
ERUB =7- +a0 +''0
V
2 where a' = 21)ocaa. Tet Tn(1/7]
In (1+ +
mm. Then,
ko
2
K0
2
a'
(f-11)/2 (1
11/2 11122/150) voc
ERUBmin = 0
Ki + 170
(1 v7)2
ka + no
2
21p02aa
7(1-11// 1)/2
KOO + 170
(1 vT)²
Nice + 170
Ka
(1 --7)² 7 ((8-1))
21102/K
ka +
(Ror + 77)
Ka
(Rax + c37)0)
(Ro + 77)2
<
Kd + 770
where 03 is some constant.
When T <<> T.
U3 USS-T- T-T
2(1 T Tt
3211- 0z
[=1
i==
nT T-
T'0?
1 BB2
1=1
with which we obtain
ERUB < TT + Ru
--2
ΣT T
< <9- T + 21p0
ogo 2
1- 122
-
27

---

Under review as a conference paper at ICLR 2021
where we let 9: -T By Lemma 4.1,
EE 1=1
Ryco >
V
=7- T
Σ [ml 73122
1 - 7/2
2
= r+1
1 - V-
Thus.
1 - 7/2 2
ERUBmin S + 2na - -182
1 V7
1-2 2
7 1
2muncia
1- /5
Let
In(1/]] (1 + no )
Then.
ERUB min
ka Ka + Tlo
1+
(1 --7)2 kia + 1 )²)
210oc1a 1
Ka
Ka -
1
1 1 O
AaO + T/o
Kick
< O
k0 + 1)0
In summary,
ERUB min S 50
Ka [Irst ka + 170
+ Irss)
Ka + 770
C.3 STOCHASTIC GRADIENT DESCENTS
Proof of Theorem 4.7. Let V, be the stochastic gradient of the step t. By the smoothness, have
[(0++1) - -(0.) < 7/h V. (v, Ga,u/n) Mn² | Gomn/n!
= / (V, + 0gt/n/ Govu/ + 2 Mrx V + agLi/n + Gowe/n||
Note that of generality, write σy5t Go o.c. where ő / oo3 (Go,)² and is random
= 0 and EE + Go,u/n)) = oy + (Go,/n)². Without loss
vector with EG, = and |c |1 < D. Therefore.
-(0.) < - V (v, + 5.G./ + IVV. +
-1 マタ Mmd V.l12 - - 1M-M) V ocLe/n + 1 M || 21 Mmn)(((a)) -((0)) (1 -Mne) V. V.ōiGe/n
1
1 Mn² 2
(lo.G////
28

---

Under review as a conference paper at ICLR 2021
Then following the same proof of Theorem 4.1, can get
1
-[1(0r+1)1-1(07 (B(())))))
+ R'
G
-
t=1
1
Rt
al
a
(BIS(01)] ~(('))
G2 3
7
T + R'a
1
2
1
7
+ R'
Σ
T- a0?? 20?
(B[S(O))- -
G 9
1
-
t=l
R' ka
T
S
7
0
+
R'
T
(E(((O)))1((()))
G
t=1
where Rxa
D
min N- 1) S 2p(F(())- N- +/4 (0(f(())-((00)))
(a(J(1))-(00)))
Proof of Theorem 4.8. Without loss of generality, we can write σgE. + Go as ōzs where o, & V0z + (2o,)² and Se is a random vector with Eg, = 0 and E ||sell Il = D. Therefore, we replace vi by Se and of by 0² = = /²2 + oz. Now, we only need to update Uz(a, T) as
1 Σ T- (1 (1-88) 8)
Ú
82(C-0)0?
G
(1-
> 1=1
T'
T-t (1 - 3)
Σ
82
o + of)
(1 81-3
G2
U3 + U3
where we define
Ug _ Go
7 T-1
Σ i=1
(2(1-1)
(=1
31-3
We can upper bound Ug by
T
T- (1 (1- 3)2 g2t
Ug-
G 9
t=1
(1- 32
T
1+
G
t=
1- 1+3
T-
0 1=1
1
<
G 91-7
G Ko
Combine with the factors of U3 in the PGD bounds:
RRUg v RR'
aR'
Doy
Do (()
G G2 RO²
RO² =
- (f
D EXPERIMENTS
Dataset. (1) Synthetic data. We generate 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
29

---

Under review as a conference paper at ICLR 2021
logistic loss. (2) Real data. We create 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 attack and the private learning will require larger noise (see the 1/N factor in Eq. (I)) Following the preprocessing in (Abadi et al., 2016), we project the vectorized images into 60-dimensional subspace extracted by PCA.
Setup. The samples are first normalized so that -m=1 2n, and the standard deviation 1. Then the sample norms are scaled such that max, ||ر = 10 (i.c., 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. 09663-7CD (equal to (4, 10- 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 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 averaged afterwards.
1453
Sro
140
32%
A.1G
0.5
3.59
0.9
060 100
2-16
24
-14
109
75
123
12
150
175
353
0.3-
25 Brn
-0.0
3.5-
A38
100
200
140
34 353 12A 15D 22 20
Figure 3: Experiments with Logistic loss on synthetic data and squared, Logistic loss and DNN on MNIST35 by rows. (left) The final loss is fitted by quadratic function formulated as c20² + cg- (middle) The influence values are estimated using the Hessian eigenvalues (squared loss) and by retraining (logistic loss). The larger is the data scale, the larger the influence variance. (right) The relative final training losses versus the data scale where uniform schedule (uni), dynamic schedule (dyn) and exponential-decaynng schedule (exp) are compared. The relative loss is computed w.r.t the losses of the uniform schedule. For example, if the dynamic loss is e1 and the uniform loss is eg, then the relative loss is (e1 - eo)/ cg. The dashed lines are with the right axis to present influence-relate term.
30

---

Under review as a conference paper at ICLR 2021
Estimate of influences by retraining. In the left pane of Fig. 3, we estimate the influence of or by retraining multiple times. When keeping o, for * t fixed (as the tine-tuend uniform schedule σ), the value of o, is varied from 20 to 200. Then we fit quadratic function of o, where the coefficient is treated as estimation of şt- Repeating the estimation for all & 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(0r+1)) is approximately a quadratic function of the or with small relative variance (i.e., the variance divided by the mean value, 0.14, 0.032, 0.016 for / = 10, 60, 90, respectively). When o, 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 dr. It turns out the relative variances of the quadratic coefficient (approximately the influence) is small which are 0.025, 0.024, 0.027 for 10, 60, 90, respectively.
The middle pane shows the relationship between the estimated dr and learning steps. The qe of squared loss computed by analytical solution using the Hessian eigen values. The q 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 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 o; = og (xp(-kt) using the least squares method. The final losses are picked by grid searching the best T E [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 Var(q:) 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(Tqu 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 f,, the variance is small and less dependent the data scale in comparison shallow models. Though the dynamic schedule estimated by retraining influences does not performs stably, the exp method still decreasingly depends the variance of influence as expectation.
31


Reviews:
[{"review_id": "PYfWHpkd-VF", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nI will keep my reviews limited to the current submission. My first objection to the paper is that gradient descent requires computation of gradients over the entire dataset. As such, every iteration is very costly and not practical at all, given the training data set can be very large. \n\nThe paper considers Polyak-Lojasiewicz's condition, a more general form than strongly convex loss function. However, I find some of the comparison misleading. For example, Feldman et al. (STOC 2020) and Zhou et al. show an excess \"population loss\" of order $O(1/n)$. On the other hand, if I understand the paper correctly, the current submission only give excess empirical risk. Further, Feldman et al's two algorithms achieve optimal excess loss while running in nearly \"linear\" time, which is not the case in the current submission. \n\nThere might be some interesting idea in this paper, especially, looking at the dynamic schedule for PPML. However, I fail to see the strength of the result in the view of prior work as the comparison done in the paper is between apples and oranges.   \n\nI did not verify the proof very carefully. There are some typos that I found. For example, line following equation (1), $v_t$ should be $\\nu_t$. \n\n$\\alpha$ depends on $f(\\theta_t)- f(\\theta^*)$ and $T, \\sigma_t$ depends on $\\alpha$. How are we going to set these parameters when we do not know the minimum value of the objective function?", "extra_scores": {}, "extra_text": {}}, {"review_id": "Kim9mEkpMB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary \n\n\nGradient 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. \n\nPros\n- improves over previous soa analysis of private gradient descent (wang 2017) by $log N^2$ factor\n- Novel analysis for an important practical problem that also yields intuition via the notion of noise influence / propagation\n\nCons \n- Grammatical Errors throughout: e.g. sentence fragment page 6 “because our bound saved a factor of log N and is thus tighter, as compared to Wang”\n- Overall the clarity of the writing and explanations, both in terms of prefacing the technical content, and readability could be improved. \n- Experimental section needs more detailed fleshing out: 1) how does the middle pane show the trend of variance of influence? 2) how are we modeling influence for DNN and how are we then computing the optimal dynamic schedule 3) does plot #1 perform a sensitivity analysis on the ERR via retraining to estimate $q_t$ empirically? Explain this. \n\n\nComments\n- why does the utility bound for non-private GD in table 1 have a factor of $R$ (privacy budget) in the denominator?\n- What is the difference between $v_t$ and $g_t$? $v_t = g_t$ it says on the bottom of page 3\n- $v_t$ and $\\nu_t$ look very similar, choose more distinct notation \n- write out the definition of the ERUB in the main text on page 4\n- 4.11 uses the improved analysis to sharpen the utility analysis of a uniform schedule by choosing an optimal value of T. Please contrast the Wang bound more clearly with (5) and state the improvement factor. We can read this from the analysis but it should be stated more prominently.\n- Discussion of robustness on page 6 is a little imprecisely worded. Is the takeaway that when the condition number is very high relative to the sample size, the dynamic schedule ERUB doesn’t blow up? Since we are calling this robustness, is it obvious that noise in the samples or labels leads to high loss curvature? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4D2h78AmwLZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strong Points:\n\n1. The problem studied is interesting and important for the privacy community - private gradient descent is an important mechanism for private convex optimization, and one of the only mechanisms for non-convex optimization.  \n2. The authors do a good job engaging with prior work, identifying gaps in related work (i.e., theoretical justification for dynamic noise schedules) and putting their contributions in that context.  \n3. The analysis seems technically correct and pretty strong, although I did not check this closely.  \n\nWeak Points:\n1. Excess risk upper bound is probably quite loose, so improving that may not necessarily improve actual excess risk.\n2. log(N) improvement may be an artifact of the analysis, and not an inherent advantage of dynamic schedules.  Needs more clarification (see below). \n\nOther Notes:\n\nIt’s not clear to me where the log(N) term in the excess risk upper bound comes from for the uniform noise schedule.  In other works on this topic, it is not there (e.g., https://arxiv.org/pdf/2005.04763.pdf) .  Since we are dealing with upper bounds, I wonder if it is just an artifact of the analysis of Wang et al., rather than an improvement offered by dynamic scheduling.  Are there other ways to remove this dependence other than dynamic noise?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "06hVqjtcuLn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper investigates the idea that a dynamic privacy schedule of decreasing noise can help private gradient descent. The main contribution is a theoretical analysis of a dynamic privacy schedule which helps reduce the utility upper bound of private gradient descent (with or without momentum).\n\nStrengths:\n1)\tPrivate gradient descent is an important optimization technique in differentially private ML, therefore, understanding its behavior is broadly interesting.\n2)\tThe paper investigates both the vanilla private gradient descent as well as a version with momentum.\n\nConcerns:\n1)\tWhile there is some improvement with the dynamic schedule vs. fixed schedule, the improvement does not seem to significant (ref. Table 1). \n2)\tResults hold only under PL condition (which is a more general condition than strong convexity) and smoothness.\n\nThe results look correct. My current scores are because I see limited value/interest in these results. \n\nQuestions:\n- Maybe relaxing the assumptions might be a way to strengthen the paper.  Is that possible?\n- What is the advantage of using the momentum method in terms of the utility upper bound (ref. Table 1). It looks like (within constant factors) vanilla GD with dynamic schedule works as well as using the momentum.\n- Do these results hold with a stochastic gradient?\n\nMinor comment: hat{T} not defined in Table 1", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes algorithms for solving ERM with continuous losses satisfying the PL condition. The first algorithm achieves that by using a chainging noise variance and thus the paper frames the contribution in terms of the advantages of non-constant noise rate.

The problem is a well-studied one and the result is a nice if relatively modest improvement over Wang et al. However, as pointed out in reviews, in the context of convex optimization the same rate has already been established (Feldman,Koren,Talwar STOC 2020). This work is cited and briefly discussed but the discussion only includes one of the algorithms in the paper (that does have an additional log N factor). The overall assumptions in this paper are not comparable (weaker in some ways and stronger since they only require PL instead of strong convexity) but still the overall the contribution appears to be incremental.
Decision: Reject