Improved Convergence of Differential Private SGD with Gradient Clipping
Authors: Huang Fang
Xiaoyun Li
Chenglin Fan
Ping Li
Venue: ICLR 2023 poster (2023)

Abstract: Differential private stochastic gradient descent (DP-SGD) with gradient clipping (DP-SGD-GC) is an effective optimization algorithm that can train machine learning models with a privacy guarantee. Despite the popularity of DP-SGD-GC, its convergence in unbounded domain without the Lipschitz continuous assumption is less-understood; existing analysis of DP-SGD-GC either impose additional assumptions or end up with an utility bound that involves an non-vanishing bias term. In this work, for smooth and unconstrained problems, we improve the current analysis and show that DP-SGD-GC can achieve a vanishing utility bound without any bias term. Furthermore, when the noise generated from subsampled gradients is light-tailed, we prove that DP-SGD-GC can achieve nearly the same utility bound as DP-SGD applies to the Lipschitz continuous objectives. As a by-product, we propose a new clipping technique, called value clipping, to mitigate the computational overhead caused by the classic gradient clipping. Experiments on standard benchmark datasets are conducted to support our analysis.

Published as a conference paper at ICLR 2023
IMPROVED CONVERGENCE OF DIFFERENTIAL PRIVATE SGD WITH GRADIENT CLIPPING
Huang Fang, Xiaoyun Li, Chenglin Fan, Ping Li
Cognitive Computing Lab Baidu Research
No. 10 Xibeiwang East Road, Beijing 100193, China
10900 NE 8th St. Bellevue, Washington 98004, USA
[fangazg877, 1ix.iiiiiiii 111771y1xxiccc fanchenglin, pingeegggiiiinnnnigggiii pingli98 @gmai com
ABSTRACT
Differential private stochastic gradient descent (DP-SGD) with gradient clipping (DP-SGD-GC) is an effective optimization algorithm that can train machine learn- ing models with privacy guarantee. Despite the popularity DP-SGD-GC, its convergence in the unbounded domain without the Lipschitz continuous assump- tion is less-understood; existing analysis of DP-SGD-GC either impose additional assumptions or end up with a utility bound that involves a non-vanisi non-vanishing bias term. In this work, for smooth and unconstrained problems, we improve the cur- rent analysis and show that DP-SGD-GC can achieve vanishing utility bound without any bias term. Furthermore, when the noise generated from subsampled gradients is light-tailed, utility bound as DP-SGD applies to the Lipschitz continuous objectives. As a by-product, we propose new clipping technique, called value clipping, mitigate the computational overhead caused by the classic gradient clipping. Experiments on standard benchmark datasets are conducted to support our analysis.
prove that DP-SGD-GE can achieve nearly the
INTRODUCTION
Training machine learning models that can achieve decent prediction accuracy while preserving data privacy is fundamental in many modern machine learning applications. The concept of differential privacy (DP) from Dwork (2006); Dwork & Roth (2014) offers elegant mathematical framework to characterize the privacy-preserving ability of randomized algorithms, which has been widely applied to tasks including clustering, regression, principle component analysis, empirical-risk mini- mization, matrix completion, graph distance estimation, optimization and deep learning (Chaudhuri & Monteleoni, 2008; Chaudhuri et al., 2011; 1; Agarwal et al., 2018; Ge al., 2018; Jain al., 2018; Fan & Li. 2022: Fan et al., 2022). For the empirical-risg minimization (ERM) problem, among many proposed methods, differential private stochastic gradient descent (DP-SGD) is an effective algorithm that can solve the ERM problem with privacy guarantee and achieve reasonable utility bound. DP-SGD has received substantial interest recent years due to its simplicity and effectiveness (Song al., 2013; Bassily et al., 2014; Abadi et al., 2016; Wang et al., 2017; Bassily et al., 2019; Feldman et al., 2020; Asi et al., 2021).
In the classic analysis of DP-SGD, the variance of the Gaussian noise used in each iteration of DP-SGD relies crucially on the Ez-sensitivity of the loss function. Therefore most early works on DP-SGD assume each individual loss function to be Lipschitz continuous in its domain (Song et al., 2013; Bassily et al., 2014). However, many real-world problems are only smooth but not globally Lipsehitz continuous; for example, the unconstrained linear regression problem. There are two techniques to circumvent the Lipschitz continuous assumption: (i) imposing an additional bounded domain constraint to the original problem; (ii) clipping gradients in their 2-norm and using the clipped gradients to update the model (Abadi et al., 2016). In practice, the gradient clipping technique is usually more preferred than imposing bounded domain constraint because the latter requires prior knowledge of the distance between initialization and solution, which is typically unavailable for unconstrained problems. In summary, the ttate-of-the-as implementations of DP-SGD all advocate the gradient clipping technique.

---

Published as a conference paper at ICLR 2023
Table 1: The utility bound and assumptions needed by different algorithms for convex problems, where d is the problem size, n is the number of data points and measures the ability; see Section for more details. "f" based on a trivial extension of Bassily et al. (2014).
Algorithms
Domain
Objective function
Light-tail-noise
Utility
DP-SGD (Bassily et al., 2014)
Bounded
Lipschitz cont.
No
(Vd/(ne))
DP-SGD
Bounded
Smooth
No
o (Vd/(ne)
DP-SGD (Wang et al., 2022)
Bounded
Hölder smooth
No
Ö (Vd/(me)
DP-SGD-GC (Ours)
Unbounded
Smooth
Yes
0 (Vd/(ne))
Despite the popularity of DP-SGD with gradient clipping (DP-SGD-GC), the convergence of DP-SGD- GC for unconstrained problems that are not globally Lipschitz continuous has not been well-studied. In fact, recent works (Chen et al., 2020; Song et al., 2021) have reported that DP-SGD-GC can suffer from a constant utility in the worst case. With these negative results on the convergence of DP-SGD-GC, one may consider DP-SGD BP-SGD as an algorithm with a fundamental non non-convergence issue. In this work, we show that this is not the case. With careful choice of the clipping threshold, we prove that DP-SGD-GC can achieve the same utility bound as its non-clipped counterpart DP-SGD. Formally, summarize our contributions as follows.
For unconstrained problems that are convex and smooth but not necessarily globally Lipschitz continuous, we show that DP-SGD-GC can achieve Ö (ne)) utility bound when the noise generated from the subsampled gradients is light-tailed (Assumption 4. 4)',,, which is the same as the utility bound of DP-SCE SGD applies to the Lipschitz continuous problems. See Table 1 for a comparison to existing results. Our convergence analysis of DP-SGD-GC for convex, smooth and unconstrained problems, to our knowledge, provide the first utility bound without non-vanishing bias term.
We show that our analysis also applies to unconstrained smooth problems that can potentially be nonconvex. Consequently, DP-SGD-GC can achieve a ((vd/ (ne) gradient norm bound for smooth problems under the light-tail-noise assumption.
This work is theoretical in essence but also includes a practical contribution (Section 5). We develop a novel value clipping technique for problems that satisfy the weak growth condition (Definition 3.1). The proposed value clipping technique can be implemented within one forward- backward propagation on existing learning platforms and can alleviate the computation overhead caused by gradient clipping. The efficiency of value clipping is demonstrated on real datasets.
RELATED WORK
DP-SGD with gradient clipping was initially proposed by Abadi al. (2016). Gradient clipping and its variants have been widely adopted by many privacy-aware training algorithms (Andrew et al., 2021). Despite the popularity of gradient clipping, the convergence rate of DP-SGD-GC without the Lipschitz continuous and bounded domain assumptions remains challenging task; see (Wang et al., 2022, Remark 5) for a short discussion on the hardness of removing the bounded domain assumption. This challenging research question was not carefully studied until the recent works from Chen et al. (2020) and Song et al. (2021), who provided counter-examples showing that DP-SGD-GC can suffer from constant utility in the worst case. Chen al. (2020) studied the convergence of DP-SGD-GC to a stationary point in the nonconvex setting and showed that an additional assumption on gradient distribution sufficient to derive a meaningful utility bound. Song al. (2021) showed that DP-SGD-GC converges to a perturbed objective function for the generalized linear model and can suffer from constant utility for the original objective in the worst case. Note that there are some other recent works that study the convergence of DP-SGD-GC for smooth objective (Du et al., 2021; Wu et al., 2021; Yang et al., 2022), the rates in these works usually involve a bias term due to clipping. A concurrent work from Bu et al. (2022) suggests that small clipping threshold can yield promising performance for DP-SGD-GE
in certain scenarios, such as training language models. Their empirical discovery contrasts with the theoretical analysis in this work as our proof technique relies on a large clipping threshold. Bu et al. (2022)'s 's experiments indicate that the analysis in this
'The light-tail assumption standard for deriving high probability error bound of SGD the literature.
2

---

Published as a conference paper at ICLR 2023
work may be further improvable; rigorous theoretical justification for the phenomenon described by Bu et al. (2022) is worth future investigation. Another concurrent work from Yang et al. (2022) studied the convergence of DP-SGD-GC under the generalized smooth condition, their analysis relies on a different set of assumptions and do not overlap with this work.
On the practical side, the original implementation of gradient clipping was inefficient as one needs to calculate the norm of each individual sample in every iteration. Many works (Goodfellow, 2015; Abadi et al., 2016; Rochette et al., 2019; Bu al., 2021; Subramani al., 2021) have been carried on to improve the efficiency of DP-SGD-GC from either engineering or algorithmic perspective. Our proposed value clipping technique can be viewed as an alternative to the classic gradient clipping.
3 PRELIMINARIES
Notation Throughout this paper, for any positive integer n, we denote [x]] == n). We denote || |I be the vector 2-norm or matrix operator norm if not otherwise specified. We use the
notation (.) to hide poly-logarithmic terms.
We consider the empirical-risk minimization (ERM) problem
minimize f(w) = - I.(w). f((w), wER"
(P)
where n is the number of training samples, fi's are differentiable functions and w is the model we wish train. Throughout the paper, we assume that bounded below and its minimum is attainable. We let W to be the set of solutions for problem (P), and denote the optimal function value as f³. We assume that lower bound of f* is known as prior. Note that this assumption holds in many realistic settings, for example the ERM problems are usually lower bounded by zero
Next we introduce the weak growth condition (WGC), which is the cornerstone for our analysis.
Definition 3.1. A function h Rd + RR is (81, 32)-WGG for some B1 0, B2 0f
[2(W0)]2 < 31 (M(w) inf h(u)) B2 Vw Rd.
The weak growth condition bounds the norm of the gradient by a linear function of the objective value. WGC is gaining increasing interest in recent years as multiple works have demonstrated that WGC and its variants can improve the classic analysis of SGD-type algorithms (Schmidt & Roux, 2013; Needell et al., 2014; Vaswani et al., 2019; Qian et al., 2019; Stich, 2019; Khaled & Richtárik, 2020; Fang al., 2021; Gower al., 2021). is easy to show that smooth functions that are bounded below necessarily satisfy WGC; the following Lemma makes this precise.
Lemma 3.2. If a function inf h(w)= -00. Then is (2L, -G-W
Rd + R is L-smooth for some > and bounded below, e.g..
We stress that WGC is not a strong assumption. In fact, a wide range of nonconvex and nonsmooth problems arising from the ERM problem also satisfy WGC, e.g., the Lipschitz continuous model with smooth and convex loss function; see Fang et al. (2021, & 4. and Section D for more details.
We recall the standard definition of differential privacy (DP).
Definition 3.3 (Dwork, 2006), A randomized algorithm A is (c, d)-differentially private if for all neighboring datasets D, D' and for all events in the output space of A, we have
Pr(A(D) e $] S e Pr[A(D') E +8.
If 8 = 0, then A is said to be e-differentially private.
The detailed algorithm of DP-SGD-GC is shown in Algorithm 1. It has been shown that DP-SGD-GC (e, 8)-DP long as the noise level a is larger than certain threshold (Theorem 3.4).
Theorem 3.4 (Abadi et al., 2016, Theorem 1). Let q B/n, where B is the batch size and n is the number of data points. There exist constants e and C22 such that for any < en Algorithu is
(e, DDP for any 8 > 0 iio 2 log((188)
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 Differential- SGD with gradient clipping (DP-SGD-GC)
1: Input: number of iteration T N, clipping threshold C > 0, noise level
>
0, batch size
B E [1, nl, learning rate > 0, initial iterate w(O)
2: for t ....., do
3: Sample mini-batch B,, where each data has probability B/n to be sampled;
4: 9: f((w()) Vi Bi;
(() 9t max (1, 1 II/), E B;;
5: 9t
6:
((++1) = w(() 7B E.EB, 0f + (
where g(t) ~ (O, C
7: end for
8: Return: w(( where is uniform randomly sampled from {0, (0.1...,7Y)
MAIN THEORETICAL RESULTS
We present our main theoretical contributions in this section. Denote wpriv as the output of Algo- rithm 1. We are interested in the upper bound of the excess empirical risk [wpptv) f and the gradient norm square V f (Wpriv) )l(² without assuming fi's to be Lipschitz continuous I& Part of our analysis relies on assuming the noise generated from subsampled gradients is "light-tailed" Guub-Gaussinn). Formally, we introduce the following assumption".
Assumption 4.1. There exist > 0 such that
E; exp [VV[(()) - V ([( se,
Vw E Rd.
We note that the above light-tail assumption is widely used assumption for the analysis of high probability utility bound of SGD (Nemirovskii al., 2009; Juditsky & Nesterov, 2014; Ghadimi & Lan, 2013; Harvey et al., 2019; Feldman et al., 2020). Assumption 4.1 does not imply fi 's to be globally Lipschitz continuous on R and therefore will not trivialize our analysis. Note that there is recent trend on analyzing SGD and its variants with heavy-tail gradient noise (Gürbüüzzalabb) abaa et al., 2021). Our analysis does not apply to the heady-tail setting because our Proposition 4.2 relies erucially on the light-tail-noot tois- assumption.
The idea our proof is concise. We first summarize the proof sketch as follows, and then explain the technical details step by step.
Proof sketch:
Assuming that the initial objective gap (w)(0) f is bounded. We are able to prove that, with high probability, the iterates generated from SGD have bounded objective values that only logarithmically depend on T.
The weak growth condition allows gradient norm upper bound. Thus, with high probability, gradient clipping will never happen during the process DP-SGD if the clipping threshold C' is chosen appropriately.
convert the objective value upper bound to the
Finally, we can apply the classic convergence analysis of SGD (without gradient clipping) and obtain a non-trivial excess empirical risk or gradient norm upper bound.
To begin with, we develop uniform upper bound on the objective values, e.g., f(w(() where (t)'s are the iterates generated from the vanilla SGD algorithm (Algorithm 2) with sub-Gaussian noise.
Proposition 4.2 (Uniform upper bound on objective values of SGD with sub- Gaussian noise). Assume I is L-smooth for some L > O and there exist ā > O such that [[exp([[ç() | < e eforr any t E N. Denote {w) yr as the iterates generated from Algorithm with S min 2E TVT
Then for any E (0,1),
(f(w(()) -5") S (1(w(0)) - (r)) 0000+0000000000 (log(T/5))
max (E........,T
with probability at least
Note that there several equivalent (up to constant) definitions of sub-Gaussian variable; see Vershynin, 2018, Proposition 2.5.2. These definitions often used interchangeably in the literature.
4

---

Published as a conference paper at ICLR 2023
Algorithm 2 Stochastic gradient descent
1: Input: total iterations T E N,, learning rate r7 > 0, initial iterate (0))
2: for ...... T 1 do
3: w((++1) = (()) V (w(()) + <()));
4: end for
5: Return: wit) where uniform randomly sampled from {0, 10.1...,777 T}.
The conclusion stated in Proposition 4.2 may seem obvious at first glance the training algorithm is expected to produce almost decreasing objective values during the optimization process. However, we note that deriving a nearly constant upper bound of (w((() - f that holds uniformly over without assuming Lipschitz continuity or bounded domain is nontrivial. Our proof relies on a recently proposed technical tool called the generalized Freedman inequality (Harvey et al., 2019); see Section B.I for the detailed proof of Proposition 4.2. We also remark that Proposition 4.2 holds for the standard SGD algorithm without considering differential privacy, and thus may be of independent interest.
t E {0, 1 ......77 7
Based Proposition 4.2, can further obtain upper bound on each individual loss f((w(t)) under Assumption 4. 1. and therefore also upper bound V (w)(f)) via the weak growth condition.
Proposition 4.3. Assume fi's are L-smooth for some L. > 0 and there exist ā O such that fi=o as the iterates generated from Algorithm [) [|///>)] S for any t E N. Denote (w
with S min 22 oVT
Then for any E (0,1).
(v)
& v (f - fr) + 0 (Vlog(110)) + Vlog T + vlogn) (1)
max SE(M)AE([T]
holds with probability at least - 8 for any E (0, 1).
When Assumption 4.1 holds, Proposition 4.3 suggests that the upper bound of the maximum gradient norm logarithmically depends on 6, T and n (eq. (1)).
Now we are ready to present our excess empirical risk bound and gradient norm bound for DP-SGD- GC in terms of conditional expectation.
Proposition 4.4 (Convergence on conditional expectation). Assume that Assumption 4.1 holds. De-
note wpiv as the oulpul of Algorithm and define & == (ll < C'vi E [n], E {0, 10.1...,777 T as the event of no clipping happens during the training of Algorithm I. Let Dj = f(w(()) f Given any c and 8, (0.5,1) 1).
Assume Ji's ss's are convex and L-smooth for some L> 0. set set T e/C1.
C2ByT (log(1)) C Vos ca
B V(Bp' C
σ
min
nE
22
where C1, C2 Cs are some absolute constants and C3 C4 are constants that depend on L and Dj- We have that Algorithm is (c,8)-DP, Pr[E] -8', and
(Vlog(1/8) + Vlg((Tn) / //log(1//)
1 T
1
E [[[[prrv) S
O
BT
Assume fi's are L-smooth for some is (e, 8)-P, Pr[E] Z - 6', and
0. Setting E, a, C, m in eq. (2). holds that Algorithm
(Vlog(1/8) + + vlog(Tn)
(llo((1/6)
E 12 s o
=
T
BT
5

---

Published as a conference paper at ICLR 2023
While the bounds stated in Proposition 4.4 are close our objective, note that these bounds are expressed in terms of conditional expectation where the conditioning event happens with high probability, which is different from the classic notion of convergence in expectation. Fortunately, show that it easy to convert the bounds in Proposition 4.4 to expected utility bound when the random variable (Wpriv) f (or V ((priv)]l3 (|2 is sub-exponential, which is true under Assumption 4.1. Lemma A.9 serves as the main technical tool for this conversion.
Theorem 4.5 (Convergence on expectation). Suppose that Assumption 4.1 holds. Denote wprv as the output of Algorithm 1. Let Dj == (() - f". Given any e > and 6 E (0.5, 1). Setting T, o, o in the same way as eq. (2) and let C = -ccs + ca log(nT)) where c1, C22 C3 are some absolute constants and ca, ca are constants that depend on L, Dy.
Assume Ji 's are convex and L-smooth for some I, >> O. Then Algorithm is (e, 8)-PP and
1 T
vd
E [f((pri))) - 84] - ④
VT
Consequently, we have E (fWprivv - fa ō (d (dd/2 by setting T= - (n?
Assume Ji's 's are L-smooth for some O. Then Algorithm 1 is 5)-DP and
vd
E [IV ) S Ö +
BT
TEE
Consequently, we have E [W (nc)) by setting T = T= (n²
Remark 4.1. Our results suggest that, when the problem is smooth, the Lipschitz continuous and bounded domain assumptions can be removed almost for free when analyzing DP-SGD-CO with light-tuiled gradient noise; the only cost is some logarithmic terms.
Remark 4.2. Our analysis also holds for DP-GD-GC. When analyzing DP-GD-GC, Assumption 4.1 is no longer required. However, when Assumption 4.1 does not hold, there will be additional multiplicative term /n appear in eq. (1) and the final utility bound is ((Vd/(((//)))))
Theorem 4.5 is the main theoretical contributions of this paper. The bounds stated in Theorem 4.5 which is the best-known bound of DP-SGD with
nearly match the rate the Lipschitz continuous or bounded domain assumption (Bassily et al., 2014). To our knowledge, for unconstrained smooth problems, this is the first utility bound of DP-SGD-GE without a non- vanishing bias term. Note that existing lower bound analyses for DP-SGD either assume the domain is bounded (Bassily et al., 2014) or the loss is Lipschitz continuous (Song et al., 2021). I). Therefore those lower bounds are not comparable with the upper bounds stated Theorem 4.5. We leave the lower bound of DP-SGD-GC for unconstrained smooth problems as future direction to explore.
5 VALUE CLIPPING
This section focuses the practical side of DP-SGD-GC, A well-known implementation issue of Algorithm is that the gradient clipping step (line of Algorithm 1) requires to access the norm of each individual gradient from the sampled batch, and naive implementation of DP-SGD-GC on current deep learning platforms cannot fully exploit the parallelism of GPU; see some attempts that try mitigate this issue (Goodfellow, 2015; Rochette et al., 2019; Bu al., 2021). The state-of-the-an implementation of DP-SGD-GC is from Subramani et al. (2021), who developed a highly engineered approach to exploit language primitives, compilation, and vectorization on certain deep learning platforms. In this section, we propose value clipping technique for functions that satisfy the weak growth condition (Definition 3.1). The proposed value clipping can be viewed as an alternative the classic gradient clipping technique that is easy to implement on all existing deep learning platforms such as PaddlePaddle.
The intuition behind value clipping is simple - when fi's satisfy the weak growth condition, the norm of their gradients can be bounded by a function of their objective values, e.g., (w)]l S / - ff") ) + 32, therefore scaling the gradient by (f,(f( f!) + Bg ensures the scaled gradient has bounded norm. Formally,

---

Published as a conference paper at ICLR 2023
Algorithm 3 Differential-privall SGD with value clipping (DP-SGD-VC)
1: Input: number of iteration T E N, clipping threshold C' > 0, noise level a > 0, batch size
B E [1, nl, learning rate 17 > 0, initial iterate w("), WGC parameters 31 > 0, 32 2 0, fib E R that lower bound fo Vi [m].
2: for i 4- .,.... T do
3: Sample mini-batch B,, where each data have probability B/n to be sampled;
4: g! = f((w(()// max {I, (L(((1())) - fib) + B2/C] E B;;
5: (((++1) = (()) - - (Eres, a. + { where g(t) ~ (00 Taxd);
6: end for
7: Return: wit) where uniform randomly sampled from {0, 10,1...,Th,
Vw E Rd g= /i(ws// max 1, V /i(l(ww= (2) + 32
| S.
The detailed algorithm of DP-SGD with value clipping, termed DP-SGD-VC, is shown in Algorithm 3. Note that DP-SGD-VC requires knowing the WGC parameters 31, 32 and lower bound of fe's as its input. The WGC parameters for simple models, including linear and logistic regression, are easy to calculate. For feed-forward neural networks, the calculation of WGC parameters is achievable but more involved; see Appendix D for details. It is easy to verify that DP-SGD-VC is (e, 6)-DP because the of the clipped gradient is guaranteed to be bounded by C; the following corollary is direct consequence of Theorem 3.4 and describes the DP property of DP-SGD-VC.
Corollary 5.1. Assume fo 's are (51,33)-WGG for some 31 > 0, 82 2 0. Let BBnn where B is the batch size and is the number of data points. There exist constants 0₁ and C22 such that for any T. Algorithm is (c, 6DD for any d > 0 if 2 c24//Tlogg1
log log()/))
Remark 5.1. DP-SGD-VC is easy to implement on existing auto-differentiation based deep learning platforms. The value clipping step (line of Algorithm 3) can be realized within one forward- backward propagation if the WGC parameters are given in advance. Therefore DP-SGD-VV VC can be as fast as the vanilla SGD algorithm.
6 NUMERICAL STUDY
We conduct experiments on two standard image classification benchmark datasets: MNIST (LeCun, 1998) and CIFARIO (Krizhevsky & Hinton, 2009). In Appendix, we also present some experimental results synthetic data with light-tailed noise. For MNIST, layer MLP with 128 hidden nodes respectively. For CIFAR 10, to achieve decent accuracy, we use a pre-trained VGG16 network (Simonyan & Zisserman, 2015) to extract informative high-level features. Based on the 512-dimensional extracted features, we train a linear classifier and a two-layer MLP with 128 hidden nodes respectively.
train linear classifier and two-
Implementation details For all experiments, we the batch size B 128, the noise level o 1.0 and the confidence level ò = 10- For MNIST, we try learning rate in {2 x 10-3, 5 x 10-3 10-3,10-2 10-23 for each experiment and report the best result. For CIFAR10 we fix the learning rate to be 0.1. All experiments are conducted on server with 4 CPUs and one NVIDIA Tesla P100 GPU.
6.1 THE EVOLUTION OF CLIPPING FREQUENCY DURING TRAINING
We run DP-SGD-GC with different clipping thresholds. In particular, we try C E {1,5, 5, 20, 40} and CE (0.1, 0.4, 1.0} for MNIST and CIFAR 10 respectively. The evolutions of training accuracy and clipping frequency per epoch with different clipping thresholds are shown in Figure 1. We can observe that, in most cases, the clipping frequency decreases as the training accuracy goes up. This observation aligns with the WGC as lower training loss implies a smaller average gradient norm and further results in lower clipping frequency. We also see that, in most cases, the clipping frequency can become close to when the clipping threshold chosen appropriately; this observation is consistent with our theoretical analysis. Another interesting observation is the result of training the two-layer neural network with MNIST and C E {20, 40). The clipping frequency is small initially and becomes stable at 155 instead of decreasing to zero. We conjecture that this phenomenon is because the WGC
7

---

Published as a conference paper at ICLR 2023
MNIST, Linear Model
MNIST, Two-Layer NN
CIFAR, Linear Model
CIFAR, Two-Layer NN
0.4 0.6 08 1.0
08 1.0
1.0
2222
1.0
100
Clopping frocusncy
Tiieing wcoumity
100
Cieping Recuersy
Traning acourety
100
08
Cloprg frecuenyy
Traniing acounay
100
0.8
Clophn frsouency
8
80
06
80
0.6
00
0.8
Traning
04
04
0.0 0.2 0.4
60
0. 02
60
0. 02
60
00 0.2
60
9
40
Epochs
Epochs
Epoche
Epoccts
Figure I: The evolution of training accuracy and clipping frequency during DP-SGD-GC, where the solid line represent training accuracy and the dashed line denote the clipping frequency per epoch. The left two figures present the results on the MNIST dataset, the algorithm is about (1.0379, 10 10010-0-000 --D.. The right two figures show the results the CIFAR10 10 dataset (feature extracted by a pretrained VGG16 network), the algorithm is about (0.9580, 10 9--DP
MNIST, Linear Model
MNIST, Two-Layer
CIFAR, Linear Model
CIFAR, Two-Layer NN
001
89
Training accuracy
89
Traliing accurddy
To
00
80
80
60
0-00
ONL
Ong
80
680
50
0nr0
(12)
CYC0
(-4)
40
40
10
15
20
2
10
#
Epochs
# Epachs
#
Epachs
# Epachs
Figure 2: Value clipping (VC) versus gradient clipping (GC) in terms of training accuracy.
MNIST, Linear Model
MNIST, Two-Layer NN
CIFAR, Linear Model
CIFAR, Two-Layer NN
100
100
80
Texling accuracy
Testing acouracy
96
Tesling 80
O-5
MC C-11
883
V5 Crd.4
88
VC CrE4
C-43
C-58
V5 Cr44
VC CHL6
C-00
Vc 044
V0, C4de
VC, Crd6
Epochs
# Epachs
#
Epachs
# Epachs
Figure 3: Value clipping (VC) versus gradient clipping (GC) in terms of testing accuracy.
parameters of the neural network grow the training goes and thus prevent some gradient norms from being smaller than the clipping threshold.
6.2 THE EVALUATION OF DP-SGD-VC
We set fi 0 for all experiments with DP-SGD-VC. The calculation of the WGC parameters for feed-forward neural network with cross-entropy loss is given in Section D, where B3 0 and 31 depends on the spectral norm of each layer of neural networks. Compared with vanilla SGD, DP-SGD-VC has an additional cost to calculate the spectral norm of each layer in each iteration. As shown in the following content, the overhead of calculating the spectral norm is not significant.
Training and testing accuracy The training and testing accuracy of DP-SGD-GC and DP-SGD- VC with different clipping thresholds are shown in Figure 2 and Figure 3. We can observe that DP-SGD-VC converges slightly slower than DP-SGD-GE
terms of the epoch. This observation should not be surprising DP-SGD-VC uses upper bound of the gradient norm for clipping and will result in a smaller effective learning rate than DG-SGD. For CIFAR10, the training and testing are easy the model is trained pre- trained features; both DP-SGD- and DP-SGD-GG can achieve similar accuracy at the end of training. For MNIST, there is an unfortunate loss of training and testing accuracy. For MNIST with the linear model, there is ~ 2% loss training and testing
8

---

Published as a conference paper at ICLR 2023
Table 2: Per epoch runtime of different methods. SGD without gradient clipping the baseline method;
is the naive implementation of DP DC: GC and VC are the classic gradient clipping and the proposed value clipping, respectively. We bold the shortest per epoch runtime among methods besides SGD,
Data
Model
SGD
Micro- Micro-batching
GC-Opacus
DP-SGD-VE
MNIST
Linear
6,83s
34.82s
12.80s
8.62s
MNIST
2-layer NN
6.91s
43.75s
16.61s
8.96s
CIFAR
Linear
0.58s
23.99s
4.13s
1.25s
CIFAR
2-layer NN
0.65s
30.86s
7.47s
1.70s
accuracy. For MNIST with two-layer NN, there a 3% loss in training and testing accuracy for C E {20, 40} and a ~ 4% loss for C = 10. The gap between DP-SGD-GE and GP-SGD-V VC more obvious when the clipping threshold is small. We conjecture that the loss of training and testing accuracy is due to our estimation of f"- The estimation fib = O is accurate for CIFARIO 10 as the model can almost perfectly fit all pre-trained data. However, the estimation is inaccurate for MNIST and thus results in a loose upper bound of the gradients' norm.
Comparing the computational time per epoch We report the per epoch runtime of different algorithms in Table 2. All experiments are conducted on server with one NVIDIA Tesla P100 GPU, The vanilla SGD without privacy consideration is the baseline method and is the fastest among all algorithms. Micro-batching is the naive implementation of DP-SGD--GE and significantly slower than SGD. GC-Opacus is the implementation of DP- PP-DGDD-C from the (highly optimized) Opacus package; we can see that there is still a gap between the performance of GC-Opacus and the standard non-private SGD algorithm. DP-SGD-VC is our implementation of DP-SGD with the proposed value clipping technique. We can observe that DP-SGD-VE VC is slightly slower than the standard SGD algorithm and faster than other private training methods.
Limitations Despite the efficiency of DC-SGD-VC it also has certain limitations: (i) as shown in the experiments, DP-SGD-VC may cause some loss in training/testing accuracy if our estimation for the WGC parameters is loose; (ii) DP-SGD-VC requires calculating the WGC parameters, which we show is available for feed-forward neural works with cross-entropy loss. However, would be hard to apply VC to more complicated network architectures with arbitrary loss in a black-box manner, e.g., transformers with ranking loss. Overall, we consider DP-SGD-VC as an alternative for DP-SGD-GC that is computationally cheap; DP-SGD-VC can perform similarly to DP-SGD-GC in certain scenarios but can also be not applicable in other situations.
7 CONCLUSION AND FUTURE WORK
This paper studied the convergence behavior of a widely used privacy-preserving learning algorithm called DP-SGD-GC. Our analysis extended the convergence of DP-SGD-GC to smooth and uncon- strained problems without assuming the objective to be globally Lipschitz continuous. We believe that our theoretical results improved the current understanding of DP-SSD-GG and provided new insights for practitioners and researchers to use DP- SGDGGG and design new algorithms. Our analysis can potentially be used for other et al., 2021) and DP-SGD with subspace identification (Zhou et al., 2021; Song et al., 2021).
learning algorithms such as adaptive DP-SGD (Asi
Our work implies some future directions. Firstly, the light-tail tail noise condition may not hold in some machine learning applications (Gürbüzzalaban et al., 2021). In these scenarios, the utility bound of DP-GD-GC (Remark 4.2) /n worse than the best-known bound of DP-SGD-GC for Lipschitz functions. Whether it is possible to further improve the utility bound with heavy-tail-non interesting question. Another direction is to explore the lower bound of DP-SGD-GG with a carefully tuned clipping threshold for smooth and unconstrained problems. Lastly, we may also combine analysis with more methods and schemes in optimization, e.g., adaptive gradient methods, gradient compression, and distributed optimization (Kingma & Ba, 2015; Agarwal et al., 2018; Zhou et al., 2020; Li et al., 2022).
is an
9

---

Published as a conference paper at ICLR 2023
ETHIC STATEMENT
This paper studied a class of crivate-preservig machine learning algorithms called differential private SGD. We provide improved convergence analysis and some new theoretical insights into DP-SGD. We are not aware of any potential negative social impact of this work. The datasets used for the experiments not contain personally identifiable information or offensive content.
REFERENCES
Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, lly Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 308-318, Vienna, Austria, 2016.
Naman Agarwal, Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, and Brendan McMahan. cpSGD: Communication-efficcennn and differentially-private distributed SGD. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7575-7586, Montréal, Canada, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 242-2222222222222222 252, Long Beach, CA, 2019.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. In Advances in Neural Information Processing Systems (NeurIPS), pp. 17455-17466, virtual, 2021.
Hilal Asi, John C. Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In Proceedings the 38th International Conference Machine Learning (ICML), pp. 383-392, Virtual Event, 2021.
Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 464-473, Philadelphia, PA, 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 (NeurIPS), pp. 11279-11288, Vancouver, Canada, 2019.
Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Judy Hanwen Shen, and Uthaipon Tantipongpipat. Fast and memory efficient differentially private-SGD via JL projections. In Advances in Neural Information Processing Systems (NeurIPS), pp. 19680-19691, virtual, 2021.
Zhiqi Bu, Yu- Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. arXiv preprint arXiv:2206.07/16, 2022.
Kamalika Chaudhuri and Claire Monteleoni. Neural Information Processing Systems (NIPS), pp. 289-296, Vancouver, Canada, 2008
logistic regression. In Advances in
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn, Res., 12:1069-1109, 2011.
Xiangyi Chen, Zhiwei Steven Wu, and Mingyi Hong. Understanding gradient clipping in private SGD: A geometric perspective. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Frank H Clarke. Generalized gradients of lipschitz functionals. Advances in Mathematics, 40(1): 52-67, 1981.
Jian Du Song Li, Xiangyi Chen, Siheng Chen, and Mingyi Hong. Dynamic lifferential-priverr preserving sgd. arXiv preprint 11Xiv:2111.00173. 2021.
Cynthia Dwork. Differential privacy. In Proceedings of the 33rd International Colloquium on
Automala, Languages and Programming (ICALP), Part 11, pp. 1-12, Venice Italy, 2006.
10

---

Published as a conference paper at ICLR 2023
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor: Comput. Sci., 93-44)3211 2014.
Chenglin Fan and Ping Li. Distances release with differential privacy in tree and grid graph. In IEEE International Symposium on Information Theory (ISIT), pp. 2190-2199, 2195, 2022.
Chenglin Fan, Ping Li, and Xiaoyun Li. Private graph all wall-paariie-See paitssee-shoorestt path distance release with improved error rate. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, 2022.
Huang Fang, Zhenan Fan, and Michael P. Friedlander. Fast convergence of stochastic subgradient method under interpolation. In Proceedings of the 9th International Conference Learning Representation (ICLR), Virtual Event, Austria, 2021.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 439-449, Chicago, II., 2020.
Jason Ge, Zhaoran Wang, Mengdi Wang, and Han Liu. Minimax-optimal privacy-preserving sparse PCA in distributed systems. Proceedings of the International Conference on Artificial Intelli- gence and Statistics (AISTATS), pp. 1589-1598, Playa Blanca, Lanzarote, Canary Islands, Spain, 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 2334))2341-2368, 2013.
Ian Goodfellow. Efficient per-example gradient computations. arXiv preprint arXiv:1510.01799 2015.
Robert M. Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: the 24th International Conference Learning rates, minibatching and interpolation. In Proceedings the
Artificial Intelligence and Statistics (AISTATS), pp. 1315-1323, Virtual Event, 2021.
Mert Gürbüübalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in SGD. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 3964-3975, Virtual Event, 2021.
Nicholas J, A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Proceedings of the Conference on Learning Theory (COLT), pp. 1579-1613, Phoenix, AZ, 2019.
Prateek Jain, Om Dipakbhai Thakkar, and Abhradeep Thakurta. Differentially private matrix comple- tion revisited. Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 2220-2229 Stockholmsmässan, Stockholm, Sweden, 2018.
Anatoli Juditsky and Yuri Nesterov. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stochastic Systems, 4(1):44-80, 2014.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint 22XY:20002.03329, 2020.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Proceedings of the 3rd International Conference Learning Representations (ICLR), San Diego, CA, 2015,
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report, University Toronto. 2009, 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exxb/mmist// 1998.
Xiaoyun Li, Belhal Karimi, and Ping Li. On distributed adaptive optimization with gradient compres- sion. In Proceedings of the Tenth International Conference on Learning Representations (ICLR), Virtual Event, 2022.
11

---

Published as a conference paper at ICLR 2023
Deanna Needell, Rachel Ward, and Nathan Srebro. Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. In Advances in Neural Information Processing Systems (NIPS), pp. 1017-1025, Montreal, Canada, 2014.
Arkadi Nemirovskii, Anatoli B. Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 1944)1574-1609, 2009.
Xun Qian, Peter Richtárik, Robert M. Gower, Alibek Sailanbayev, Nicolas Loizou, and Egor Shulgin. SGD with arbitrary sampling: General analysis and improved rates. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 5200-5209, Long Beach, CA, 2019,
Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. arXiv preprint arXiv: 1912.06015 2019.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint orXiv:1308.660 6370, 2013.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, In Proceedings of the 3rd International Conference on Learning Representations (ICLR), San Diego, CA. 2015.
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In Proceedingy of the IEEE Global Conference on Signal and Information Processing (GlobalSIP). pp. 245-248, Austin, TX, 2013.
Shuang Song. Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2638-2646, Virtual Event, 2021.
Sebastian U Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint 197.04290. 2019.
Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private SGD via just-in-time compilation and vectorization. In Advances in Neural Information Processing Systems (NeurIPS). pp. (64099224421, 2021.
Sharan Vaswani, Francis R. Bach, and Mark Schmidt. Fast and faster convergence of SGD for wver-parameterized models and an accelerated perceptron. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1954-1204 Naha, Okinawa, Japan, 2019.
Roman Vershynin. fligh-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems (NIPS), pp. 2722-2731, 2017.
Puyu Wang, Yunwen Lei, Yiming Ying, and Hai Zhang. Differentially private sgd with non-smooth losses. Applied and Computational Harmonic Analysis, (6:306-336, 2022.
Xiaoxia Wu, Lingxiao Wang, Irina Cristali, Quanquan Gu, and Rebecca Willett. Adaptive differen- tially private empirical risk minimization. arXiv preprint arXiv:2110.07435, 2021.
Xiaodong Yang. Huishuai Zhang, Wei Chen, and Tie-Yan Van Liu. Normalized/clipped SGD with perturbation for differentially private non-convex optimization. arXiv preprint arXiv:2206.13033. 2022.
Yingxue Zhou, Belhal Karimi, Jinxing Yu, Zhiqiang Xu, and Ping Li. Towards better generalization of adaptive gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification. In Proceedings of the 9th International Conference on Learning Representations (ICLR), Virtual Event, Austria, 2021.
12

---

Published as a conference paper at ICLR 2023
8 APPENDIX
APPENDIX A LEMMAS
A.I STANDARD FACTS
Lemma A.1. For any a, b E RR it is true that (a + b)2 2a² + 262.
Lemma A.2. It holds that Ei=1 (i/2") 2.
Lemma A.3. Given random events A1, A An- It holds that
Pr] = Pr[Ai] + Pr[Af n.A2] +... Prin A.
A.2 SE--GAUSSINN AND SUB- EXPONENTIALLL PROPERTIES
Lemma A.4 (Sub-Gaussian properties, Vershynin, 2018, Proposition 2.5.2). Let X be random variable. Then the following properties are equivalent; the parameters K2, = 1,..., 4 differ from each other by at most absolute constant factor.
The tails of X satisfy
Pr| 2 f) 2 2xxp( (kkK)
#20.
The moment generating function (MGF) of X2 satisfies
Elexp(AX3)) < exp(K3>)
AY E 001/K33)
The MGF of x2 is bounded at some point, e.g.,
E elexp(X2/10 x²/K3))
I
E [[ 0 and the MGF of satisfies
E Elexp(AX)) & exp(K?>²)
AA E R.
Lemma A.5 (Harvey et al., 2019, Lemma A.4). Let X1, X2...., Xn, be random variables. Assume that there exist K₁, K2.... K,, >> O such that Elexp( (XX)) ] I exp(AK,) for all 0 S I Then Rlexp(> Ei= X,)] exp(A Σi= K,) all 0 S X S E/E Ks.
Lemma A.6 (Harvey et al., 2019, Claim A.7). Suppose X is random variable such that there exists constants and K such that E[exp(AX]]] I cexp(AK) for all 0 I X A 1/K. Then for any 8 E (0, 1), Pr[X > K log[1/8)] < cEò.
Note that the original lemmas from Harvey et al. (2019) assume [Texx(XX)) I exp(AK) for A A 1/K. It is easy to check that their results also hold for X such that Elexp(AXX) S exp(AK)
for all 0 & X A 1/K.
Lemma A.7. Let X2, Xy be random variables such that ([exp((XX)) exp(AK) AA J0, K] for all i E T). Then there exists absolute positive constant such that
Pr
X, 2 TK TK log(1/5) S ceō for any E (0,1).
Proof. By Lemma A.5,
E
exp
A
x.)
X;
< Exx((TXA)
(0TK)
Then Lemma A.6 gives
Pr
Σ X; 2 TK log(11)/)
sed
9A (0E(0,1)
The above finishes the proof.
13

---

Published as a conference paper at ICLR 2023
Lemma A.8 (Tail bound for the maximum of Gabssinn variables). Ler X1, X2,X2 X2,..., Xn be random variables. Assume that there exist > 0 such that Elexp(AX,)) S exp(A K2) (2) for all A E R and i E [n]. Then there exist some absolute positive constant such that
Pr
max KE(m
Xi| 2 cK log(2n)
{d]
S exp(-t//K²)
W20. O.
Proof. By Lemma A.4, there exist some absolute constant c > such that
Pr[[X,| 2 4 s 2xp (-e/(CK
A4 2 0, E [m].
Then we simply apply union bound to obtain the conclusion. For any 2 0,
Pr
max [n(n]
Xi| ck 1og(2n) ct
Pr
[xi 2 ck v /lg + +ct
1=1
< 2n exp
(ccKVlog(( + cc)²/(c²(3))
K log(2n)
2tK v (llg((22)))
t²
s exp(log(2n)) exp
K2
K2
K2
2tK /log(2n)
t²
exp
K2
K2
S exp(-t/
which yields the desired result.
Lemma A.9. Let X be random variable and & be random event such that [| E| < and
Pr[E] 2 1 for some a > 0,6 E (0, 1). If X satisfies Pr| - B 2 t] < 2 2exp( -t K) Vt
for some B, K > 0. Then
E [| & a + 63 log(8/6)
Proof. Let Q: [0, 1] R U (oo) be the quantile function for the random variable [X], e.g..
Q(p) inf {i E I p Pr|X - x|}
Ap E [0.
By the assumption that [X| 8 is sub sub-exponential, we have that
Q(1 8') - K log(2/8')
vo' E (0, 1).
(3)
Now we are ready to prove the conclusion. First notice that
[[[]] Pr[E][[[X] 8) + Pr(8 | E4)
< + B[X 1==),
(4)
where 1 the indicator function with the event E The remaining to bound E[[
1ee].
Define a new set of events A; {|X]] E [Q أ Q (1 4 })]} ; 1.2,.... and denote
the probability measure space as F.)... Then
( |X| 1g-du(w)
B | 18e] =
X 1 1x122(1-)du(())
| Ls.du(w)
8
Q
2
2
1=1
14

---

Published as a conference paper at ICLR 2023
8
2
- 8, +
K log
i=1
2 88 + 8K
Σ 2
((i 1) log(2) + log(1/6))
(i)
1 83 + 83 + log(1/6)),
where is by eq. (3) and (ii) is by the standard scalar inequality (Lemma A.2). The above together with eq. (4) yields the desired result.
A.3 THE GENERALIZED FREEDMAN INEQUALITY
We restate the generalized Freedman inequality and its corollary from Harvey al. (2019).
Lemma A.10 (Generalized Freedman Inequality, Harvey et al., 2019, Theorem 3.2). Let {ds, Fi) be a martingale difference sequence. Suppose 8;-1 2 0, Vi E [T] are Fi-1-measurable random variables such that E(exp(Ad;) Fi-1l S exp( 2² 2 1-1) for all i E [T], > O. Let St = Ei= ds
and Ei 11-1. Let ag and a max ai Then
St 2 x and V Σ o;d; + B of]
σ 4a 83/z
Pr
s exp
Vx, 3 > 0.
i=1
The following lemma is an immediate consequence from the generalized Freedman inequality.
Lemma A.11. Let {di, FiJT be a martingale difference sequence. Suppose f--1 2 0, E [T] are messuualee random variables such that Elexp(Xd:) Fi-1] I exp( 2 1-11) for all i E [T O. Let S. Ei- di and V, Ei 12-1- Let 8 (0, 1) and suppose there are positive values R(6)) > 0 and non-negative values {a , = 1.2...., T,t = 1,,, T) such that
}
Pr
V1
(1) d. R(0) R
2 1-6.
Let a mTx Of;
Then
Pr
U [=1
(S 2 21
Vx, > 0. S (-Aa- 4a + 8R(6)/2)
Proof. Given d E (0,1),
R. (Ve S E i== ai d; + R(6)} Then
Define the events A.
{ 2 σ) and B.
(1)
T
Pr U (S. 2 x}
Pr
U
A
T
T
T
T
]
Pr
A
n
B
+P
U A₂
n
0 [=1
B,
T
Pr
A
n
B
+6
T
<
Pr
A
Bi
+8
T
<
Pr
Ax
B.)
+
15

---

Published as a conference paper at ICLR 2023
Algorithm 4 Stochastic gradient descent
1: Input: total iterations T E N,, learning rate r7 > 0, initial iterate (0).
2: for ...... T 1 do
3: w((++1) = (()) (W((()) + c(0);;
4: end for
5: Return: wit) where uniform randomly sampled from {0, ......... l3.
(8) S
T
Pr
44
B:
+
I
8 +
T
exp
Vz, 3 > 0,
4a 8R(0)/x
where (i) is by the assumption Pr [n B:]
2 1 --
6, (ii) is by union bound (note that we can not
directly use Lemma A. 10 since relies on aj ,..., ai Lemma A.10 for T times.
(t) (e) instead of a1....: Qz), (iii) is by applying
A.4
OTHER LEMMAS
Recall Lemma 3.2.
Proof of Lemma 3.2. By the smoothness of h, have
h(v) S h(u)) + (Vh(u), - u) + 1| u/1
u E Rd
Making the identification that Vh(u)/L. We obtain
h(u vh(u)/L) h(w) 1
2L Vh(w))1
1
inf M(V) & h(u - vh(u)/L) & h(u)
Vh(u)]?
2L
= |Vhl2)]] 2L (h(w) inf M(w) oER
Vu E Rd.
Next, we review the standard convergence rate of SGD algorithm in the following lemma.
Lemma A.12 (Ghadimi & Lan, 2013, Theorem 2.1). Denote á as the output of Algorithm 4. Assume that fo are L-smooth for some 0, r S 1/L and there exist 2 0 such that [[][{(*||]] & o² for all t N.
If fe's are further convex, then
inf |l w112 + o²n
[[f(w) frl <
(T+ 1)7
where W is the set of solutions.
If fs 's are not necessarily convex, then
2 ( + Lodn.
[1
(T+1)
The following lemma connects the WGC parameters of fi's the WGC parameters of f. Lemma A.13. Assume that ft's are (31, 32) for all E [n]. Then = Em is
(8,, Bg + 131)-WGG where I' = Em (f* f?).
16

---

Published as a conference paper at ICLR 2023
Proof.
1
Vf((2)]1
71
31(f(ww) - -f:) + 32
s 31 (f(w) 5*) + 131 + 82,
where (i) is by the convexity of || 112 and (ii) is by the assumption that fi 's are (31, 32)-
APPENDIX B PROOFS FOR SECTION 4
B.I PROOF OF PROPOSITION 4.2
Proof. We begin with the smoothness of f,
f(u(t+1)) s f(w + (Vf(w()), wl(+1) -w) + L
-w
11= 7VV 5(0) In7²
= f(w!0) - -/[[f(((())) -
[V((w(() + c(0))2
2
L1d²
L
-((w!)) - 7
[)(
10 + - - ()f(((())) ((0)
2
2
20
(5)
Let
Z
Zi1
U =
U1
1=0
1=0
Recursively apply eq. (5) gives
(6) All we need is to show that Zr-1 and Ut-1 are bounded above with high probability. First, we bound Z- Notice that ((t's are Sab-Gaussian variables, therefore -y is sub-exponential. We apply Lemma A.7, there exist some absolute constant ej 0 such that for any 8' (0,).
(ww S ()) + + U,-1,
VI =1= 0, I...,T
Lai
7T
log(1o))
C1 L log(1//))
(By the definition of 1))
2
with probability at least 1 1-88
Next bound the term U--1- Noticing that (U.) is martingale sequence, bound it by the generalized Freedman inequality (Lemma 10).). Denote F,-1 to be the o-Algebra generated from w(1) (1) ( Then by the definition of (19) we have
E exp (uZ/((Ln2 2 [V Fr-1] e,
where we use the inequality |uuel1 I (LT2² - IVV (w) 112 ( By the properties of sub- Gaussian variable (Lemma A.4), there exist some absolute constant > 0 such that
E Texp (Au)) F(-1] s exp ( x2
m)
V.ER.
Let U:-1 = (L() - 2 ((w Then
Vt-1 < Ln 0 ( fr)
(By the weak growth condition)
2024
<
T (1( -
(By 1/(vV)
17

---

Published as a conference paper at ICLR 2023
Furthermore, for any t 0, I...., T 1,
Vi-1
1=0
- -fr
2L
T
1=0
2L
T (o(w(0) - 1 + ZT-1 + +Ui-1)
<
(By eq. (6)
1=
2022
- 202L(f(w!0)) f -
Σ
Uj
T
1=0,,
==
2022
- 202L(f(w!0) fr + -T-1) +
(t -i)u
(Rearranging)
T
1=0
s 202 f + 1-- + 202
1
T
1=
Combining the above with eq. (7), with probability 8
1
Vi s 202L (f(w)0))- - f (1g_)0)(1/))/)) 202
Σ
t
41
Vt 0.1..... T
T
1=0
Now we are ready to apply Lemma A.1I. Making the identification
(t) = 202 t i-i
202h, R(0') 202L (f(w(0)) - f + (coooog(1/))/2)
d: Uii aj
T
and apply Lemma A. gives
T U
Pr
(U. 2 2)
5 <8' + Texp
(- 4a + 8R(8)/²
Vz O.
is easy to verify that with the choice max {4v R(8)) log(T ( (8), 8a log()//)) we have
T-1
Pr
U t=0
(U, 2 x}
28'
(8)
Therefore, with probability at least 28',
max ((xo(t)) Sr
1=0.1....
(1)
f() -
+ max
( (og(T/)))) 16 (og(//8))
[((((0)) f +/
(i11 2 ()) fr + logg 32c log(T/8))
where (i) is by eq. (6) and eq. (8), (ii) is by the fact that max(a.
(a b) S a + and va+b < Va + vb for any b 2 0, (iii) is by Lemma A.1. Substitute 8 with 5/2, we obtain the desired result. 1
18

---

Published as a conference paper at ICLR 2023
B.2 PROOF OF PROPOSITION 4.3
Proof. By the assumption that fi's are L-smooth, we know that f is also L-smooth. Therefore f is (2L, OW-WCC (By Lemma 3.2), e.g..
[V & V2L (f(wl)) - f*)
V -.0.,,.....
Apply Proposition 4.2. We obtain that
[V( < V AL (f(w(o)) - f logg()/))) + 64c2 L2 log(2T/0)
(9)
with probability at least 5 for some absolute positive constants c1, C2.
The remaining is bound the individual gradient norm we have that
[ When Assumption 4.1 holds,
(
f
[Vf((u(0)) f(w
max
max (E(0.1....T)
max KE(M) 1E0.
r=0,1
By Assumption 4.1, we know that V V fww)l is sub-Gaussian for all w E Rd. Therefore can apply Lemma A.8 to bound the maximum of sub-Gaussian variables, which gives
max
Vf((w())) f(w(1))l < cspv/og(n(T 1)) + ca pav/pogg11/6)
(10)
iE(n] 0=0,
for some absolute positive constant c3 and any ô E (0, Combining eq. (9) and eq. (10). We obtain that
[V)(((()) s v (T. f ca Tl + 64cz 1,2 log(2T/0)
max xe(n],t=
+ capy/oog(n(T + 1)) + ca plo((1)))
with probability at least 26, which yields the desired result eq. (1) under Assumption 4.1.
B.3 PROOF OF PROPOSITION 4.4
Proof. We first consider the case that /; s are convex and smooth. By Lemma 3.2, we know that Si's are (2T. WGC in this scenario. Setting
C VAL -
+ c3p log(n 1)) + ca
(1I)
9V Tlog(1/8)
where Cj C22 C3 correspond to the absolute positive constants that appeared in the proof of Proposi- tion 4.2, C4 some positive constant that appeared in Theorem 3.4.
Next we need to apply Proposition 4.3. Denote B; as the batch sampled at the t-th iteration and let
(00)
Σ VEB.
(0) + gg(0) - V)(w(())
= Byl
By the definition of (t)) and Assumption 4.1, ((''s satisfy
csp²
csC"
E
IP/
Se
(by the property of Poisson sampling)
B
B2
where is some positive absolute constant. Let
p²
do
1
x² = Cs
min
(12)
B
B
21
ōVT
19

---

Published as a conference paper at ICLR 2023
Then Proposition 4.3 tells us that Algorithm 2 with the above setup of & and will produce iterates such that
[V S C,
E [n].t= 0.1...........
with probability 8'.
The above analysis based on Algorithm Next, we draw the connection between Algorithm with the above setup of parameters and Algorithm I with the parameter setup in eq. (11) and defined as eq. (12). We introduce some new notation to help our analysis. distinguish between Algorithm 2 (SGD) and Algorithm (DP-SGD-GC)) we denote (T= as the iterates from Algorithm/ and (wi+t)
J as the iterates from Algorithm 1. We further let & and & as the event < C, vi E [n]} respectively. For two random variables A and B, denote A B if A and B are independent and identically distributed. Consider two independent runs of Algorithm 2 and Algorithm with ( = w()), we are going to show that
(i(()) || s C, Vi E [n]} and fi
(1)(0) (w)()) (T)
[T]
conditioned on the event o has the same distribution as conditional on the event ni
Pr[n &r.
The first conclusion should be obvious. Given ((()) = (0))), we can conclude that (i()) ~ w((1) condi- tioned on Eg and En (both gradients are bounded), which further implies w (2() conditioned on E, and & and so on.
For the second conclusion, prove by induction. Given w( (())) the base case Pr[Eu] = Pr[Eo] obviously true. Next, given Pr[m Pr[ we are going to prove Pr(n & Pr[n &g]. Knowing that
Pr(n &d] = Pr[um++ E
= (Pr(ae) + Pr(Eo +...+ Pr(n n Em+il)
(by Lemma A.3)
We only need to prove that Prin e
pt1l = Prin n Eltal Vp = 0, 0, m, which & n ge
equivalent Pri p+1 | _= Pr[n = Pr[eş C Prin By induction, suppose Pr[[[_oe] E holds. Conditioning on the events & and _ it is
obvious that (P+1)) ~ (p(+1)) and therefore Pr(Eş+1 | [ = P [. Combining the above together, we prove that Pr(n & and finish the induction.
With the above two conclusions, we can transfer the convergence of Algorithm 2 conditioned on the event E to Algorithm conditioned on the event E
Next, the conditional convergence of SGD. The proof is simply based on the law of total expectation. Denote Wout as the output of Algorithm 2 and E E
[fflt) f" Ε Pr[E] [if(
E9 Eff( fr]
(lf(t)))) - fr ह [r < (Wott) f*1
(wout) f" Ε < 2E (out)) f*),
(13)
where is by the fact that Pr(š] 2 1 8' 0.5.
Now we can transfer the convergence conditional SGD conditional DP-SGD-GC. Notice that the term (1]le()) [2] in Lemma A.12 is bounded by σ² then the classic convergence rate of SGD
20

---

Published as a conference paper at ICLR 2023
(Lemma A.1 gives that
E ((ppriv) - _ 8]
EE [(oont) - 8r E
I 2E [f - fr
(by eq. (13))
2D
+ +25211
(by Lemma A.12)
(T' 1)m
4LD
2D
20
+
T
VT
VT
2LD
D
DoVa
Covd BVT
0
T
VBT
BVT
VTB
BVV
2LD
D
Cav PaCaydlog(11 (lo((1/8)
P
Cav llo((11/
+
T
VBT
Be
VTB
Be
2LD
D
D D.C. (Cloog(1//)
Cvd
+
T
VBT
VTB
D2
DeeP
D (log((()))) + log(n) + log ( (log(1/0)
T
BT
where (i) by the definition 1). (ii) by the definition of ã (iii) by the definition of a (eq. (11)), (iv) is by the definition of q B n,, (v) is by noticing C = eq. (11).
log(n) + log((")) from
When fi's are L-smooth but not necessarily convex. We set the parameters the same as for the convex case. Apply the convergence rate of SGD for smooth but not necessarily convex functions (Lemma A.12). Following the same proof template as for the convex case, can we obtain the desired result.
B.4 PROOF THEOREM 4.5
Proof. The outline of the proof is summarized as follows.
First we show that the excess empirical risk e.g., f(uprix) f gradient norm square e.g..//V [ (Wpriv)) are sub-exponential random variables. We also derive a pessimistic upper bound of their sub-exponential parameters (Lemma B.1)².
Next, develop technical tool to convert conditional expected bound (the condi- tioning event happens with high probability) to expected error bound for sub-exponential random variables (Lemma A.9).
Finally, by tuning 8' (the probability that gradient clipping happens during training; see Proposition 4.4), Lemma A.9 together with Lemma B.I and Proposition 4.4 yield the desired result.
We do not try to optimize the bound in Lemma B.1 as we show that loose bound is enough for purpose. The bound in Lemma B.1 should be improvable.
21

---

Published as a conference paper at ICLR 2023
Now proceed to the detailed proof. Consider the case that fi's convex and L-smooth. Let T, a, C, 77 satisfy eq. (2). We apply Lemma A.9 by making the identification
X = [Wppriv) f
D (Vlog(188)
+ Vlog(Tn) v llg(/1/))
D
D
a =
T
VBT
8 = 2(f(w(()) f*) + T2
L
K = d2
CLB
where the choice of is by Proposition 4.4 and the choice of and K is by Lemma B.1. Then Lemma A.9 gives that
E B|]
a a 8'
1
Vd
0
T
V BT
m
where (i) is true by setting
1 T
Vd TEE
Vd TEE
8' = min 8-1
K-1
BT
V BT
Note that the above proof template works as long as we can construct B, K that polynomially depends on T, n, e - we can tune 8' to convert all polynomial terms and K to polylogarithm terms by Lemma A.9. We find Lemma A.9 a quite convenient technical tool for our analysis and we are not aware if this result exist in the literature.
When fi's are smooth but not necessarily convex. The proof follows exactly the same as the convex case (just need to let X = ([Pe(()) 8 == (L)) f*) + CT K, 2 apply eq. (15) instead of eq. (14)), We omit the details to avoid tedious repetition.
and
Lemma B.1 (A pessimistic bound for DP-SGD GC), Assume that fi are L-smooth. Let Upriv be the output from Algorithm I with S L/L. Then
C
to LB2
Pr f(uppe)) - f 2(f(w(())) -f +
+t
< 2exp
vt 0. (14)
L
Furthermore,
to B
Pr (wprv)) )| (124(//u f*) + 22 +t] < 2exp
V2 2 0.
222
(15)
22

---

Published as a conference paper at ICLR 2023
Proof. We begin with the smoothness of f. for any t {0, .0......:.] rT
f(wll1) v f(w(o)) + (V w(() w (0)) + L
_ (l - - w
2
1
f(w(o)) +
V (1 + /||w((
10
21
< (ww())
+ 2T.
V w 10) 212 + L
11
+
1
c())
B
B
1=U
JEB
(1)
I f(w(0)) 1
ff((w(')11 Ln TT
T-1
Σ
1
Σ
(0)
1
(3)
9j
72
B
B
JEB.
(1)
L T-1
$ ((w(00 + 2T.
[ T2
|| ||
B²
(iv)
S ((1(00) + ( - -²) + C2 + L
T-1
B
1=0
f( (f(w)(0) - 5*) T
T
+
11
(16)
L
LB
i=U
where (i) is by the fact that (a, 6) S 2x ||/|2 2 + | > 0, (ii) is by the convexity of || ||2, (iii)
because of [| || S C due to gradient clipping, (iv) by the weak growth condition, (v) by the assumption on learning rate (n S 1/L).
By the definition of (0)) Zr follows from the sub-exponential distribution. By Lemma A.4, there exist some absolute constant C₁ > 0 such that
| 20 S 2exp (-
tc LB2
(T
Combining with eq. (16), we have that
T
Lc LB
Pr [[ipriv) - f" (((
+t +t]
S 2exp
Vt 2 0,
L
do
which finishes the proof for eq. (14).
By the weak growth condition, we further have that
[VS(Wpriv) )112 < 2T -ra)
Therefore
to LB2
Pr [ (wprivv))
+20
5 2exp
(TT'''
14 0,
which finishes the proof for eq. (15).
APPENDIX C MISSING EXPERIMENTS
C.I EXPERIMENTS ON SYNTHETIC DATA
The light-tail-nois. assumption may not hold when training neural networks on real-world data. To keep consitent with our theory, we conduct experiment with synthetic data and artificial Gaussian noise. Our synthetic data has 10, 000 samples and each sample is generated from a 256-2 566-dimensional standard Gaussian distribution and ground truth linear model. To simulate stochastic gradient with light-tailed noise, we perform linear regression and add standard Gaussian noise (light-tailed) for the true gradient. The experimental results are shown in Figure 4. The conclusion is the same in
23

---

Published as a conference paper at ICLR 2023
Synthetic data, Linear Model
Synthetic data, Linear Model
0.6
0.6
GC. Dat
VC, CeT
6-20 O
Clipping frequency
GC, D-2
Training loss
0.4
0.4
Training loss
0.4
GC, C-4.0
VC, Cm2
VC, C=4.0
0.2
0.2
0.2
0.0
0
5
10
15
20
# Epochs
Epochs
Figure 4: The evolution of clipping frequency and the comparison of gradient clipping (GC) and value clipping (VC).
Section 6: the evolution of clipping frequency has decreasing trend and our value clipping technique can achieve similar accuracy as gradient clipping. The experiment in this part indicates that training neural networks on MNIST and CIFAR also enjoys fight-tail-non muile the hight-tail-non assumption is removable.
C.2 MORE EXPERIMENTS TESTING ACCURACY
In this section, compare the testing accuracy of DP-SGD-CE (the baseline method) and DP-SGD- VC with different setup of e and 8. We set the noise level {0.5, 1, 2, 4, 8} and confidence level 5 E (10-3, 10-4 1001 ;; each (o, 8) pair decides privacy parameter c, which be calculated by the Opacus package. The result are shown in Figure 5.
MNIST, Linear Model
MNIST, Two-Layer NN
95
90
Testing accuracy
90
Testing accuracy
80
38
70
80
deltamfe-5
dolarfo-55
75
60
dotta:fo-4
delta=Te-
della-fe-3 VC doltarte-2
GC delo--f-33
50
VC detta-fe-3
0.05
0.50
0.50
5.00
Epsilon
Epsilon
Figure 5: Testing accuracy of gradient clipping (GC) value clipping (VC) with varying and 6.
We can observe that the performance gap between WGC and VC grows as the privacy level becomes larger. For linear model, the testing accuracy gap is ~ 2% when c ~ 10 and the gap is ~ 5% when e 0.01. For two-layer neural networks, the performance gap is larger, the testing accuracy gap is ~ 3% when c ~ 10 and the gap is about ~ 9% when ~ 0.01. The experimental result should not be surprising: imposing smaller implies adding more noise the gradient, which will further increase the gradient norm and clipping frequency, and will eventually amplify the error created by VC.
APPENDIX D MORE ON THE WEAK GROWTH CONDITION
We review some existing results and describe the weak growth condition for feed-forward neural networks with cross-entropy loss. First, we review the generalized growth condition (Fang al.,
24

---

Published as a conference paper at ICLR 2023
2021, Proposition 4.1). Consider the objective
min f(w) WER!
f(()) n Σ
1 n ((((w))
(17)
where e: R. + I2s is a nonnegative 1-dimensional loss function that is convex, 1-smooth, and satisfies inf é = The functions h are assumed be g-Lipschitz continuous for some / > Then Ji's and / are shown to satisfy the following weak growth condition.
Lemma D.1 (Fang et al., 2021, Proposition 4.1). For any E CRd [[0f(w))ll s f(w)) Vi
and [
where (f() the Clarke's 's generalized gradient (Clarke, 1981).
We refer readers to Fang et al. (2021) for more details on the derivation of the above lemma. Note that fi's and eq. (17) can be nonconvex, and the above lemma suggests that the weak growth condition holds for certain class of nonconvex ERM.
WFAK GROWTH CONDITION FOR FEED-FORWARD NEURAL NETWORKS WITH D.1
CROSS-ENTROPY T.OSS
We give simple extension of Lemma D.1 to feed-forward neural networks with cross-entropy loss.
We denote the number of classes as K. For simplicity, we consider a feed-forward neural network with fixed width We denote the parameter of H-layer feed-forward neural network as W == (Wi,... W H). where W1 E Rm Xd
WH H E I2 xm and W; E Rmxx, 2,..... H 1. We further denote [ Σ 1I. With little abuse of notation, denote the ReLU activation, c.g., (z)) = (max{=1 OJ.... max( 0}). Note that neural networks with the ReLU activation is not differentiable everywhere its domain. We define the "gradient" of ReLU neural networks in the same way as in Allen-Zhu et al. (2019, Fact 2.6).
We consider single training sample (which is enough for our purpose) and define the architecture of the H -laye feed-forward neural network as
hg x, h, = o(2)), z W ÿ W WHhhh WWhh-1
Vj E H -1,
where hy is the hidden variables of the j-th layer, ÿ is the prediction produced by the network.
Without loss of generality, assume that the label for our training sample is the first class. Then by the definition of the cross-entropy loss, we have that
exp(i1) (xpp(n))))) _ exp((t)
K
f(W) log
log
1+
Σ
exp(i: vi)
Making the identification
K expl ii 81)
E(ax) = loog1 + exp(a))
and g(0) = log
Σ
Then
s(W) = ((g())).
It is obvious that & satisfy the assumptions made by Lemma D.1. In order to apply Lemma D. all the remaining is to bound
dg(() aw
First, we notice that
exp(02 - in)
exp(Us 11)
exp(ūK - 111)
Voo(0) = -1,
Σk cxp(1s - 01) E (0: (1)
E cxp(0: K2)
[V =2
[oo(0)] 2.
(18)
25

---

Published as a conference paper at ICLR 2023
Then we need to bound
Oy aw
Directly applying Allen-Zhi et al. (2019, Fact 2.6) gives that
H
14 ll2
II
[W
||||
II j=1.%%
[Wyll
(19)
oW;
j=i+1
for all E [H]-
Combining Lemma D.1, eq. (18) and eq. (19), obtain the following weak growth condition
H
[[af(W) Σ
1lw. ((W S 8|
Σ II
IW
Furthermore, by V (0)ll) S 2 and Allen-Zhu et al. (2019, Fact 2.6). We also have
H II
[|8((W)
Σ
((w.f(())
4|
Iw
To sum up, we obtain
H Σ
H Σ II 1=1 11
[as(w)
10w, 1ow,f(Wilf S 4|1=112
To access the WGG-parameters, we need to compute [W,il2.1 E [H] each iteration, the overhead can be amortized by increasing batch size.
26


Reviews:
[{"review_id": "Xuhmw3XzR8", "reviewer": "Reviewer_aq32", "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": "This paper studies the problem of DP optimization in the convex setting. This paper considers the problem in the setting that the loss function  is smooth but not Lipschitz and the domain is not bounded. Instead the author assumes a growth condition which basically relates the gradient of a point to the optimal gap of that point.\n\nThen, under these conditions the authors show that noisy SGD can be used to achieve an optimization gap of sqrt(d)/sqr(n)eps. Also, assuming light tail noise for the gradients the optimization gap can be improved to sqrt(d)/n eps. \n\nTheir analysis provide an approach to better clip the gradients, and using this result the authors propose a practical algorithm DP-SGD.", "summary_of_the_review": "This paper considers the DP-Optimization problem. The main result is that under a natural growth condition, the lipschitzness and boundedness assumption can be removed and we can obtain a nearly optimal convergence rate.\nI think this paper is interesting.", "strength_and_weaknesses": "The paper is well-written and the results are clear. In general the paper is good and provides some new insights.\n\nQuestions:\n\n1)In the following paper the authors provide some lower bounds for DP optimization. In which they show that the boundedness of the diameter space is necessary. It should be discussed in the paper why the lower bound does not hold under the growth condition.\n \nBassily, Raef, Adam Smith, and Abhradeep Thakurta. \"Private empirical risk minimization: Efficient algorithms and tight error bounds.\" 2014 IEEE 55th annual symposium on foundations of computer science. IEEE, 2014.\n\n2) In Prop 4.2, the authors provide a \"uniform\" upper bound on the excess error of every iteration. This result and growth condition imply that we can choose a clipping norm such that with a high probability, we \"never\" clip the gradients. I think given that we are operating under this event, the standard convergence results for smooth convex function work. I want to understand how the analysis in the paper differs from this.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DBzUnSA80D", "reviewer": "Reviewer_49Nb", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper provides a convergence analysis of DP-SGD and proposes a certain value-clipping method as an alternative to gradient clipping of DP-SGD. The convergence analysis leads to the same or better asymptotics than state-of-the-art results with slightly weaker assumptions, and the value-clipping leads to faster compute with similar experimental results however requires certain growth condition to be satisfied (for the loss function).\n\nThe convergence analysis relies on the assumption that the SGD noise of the gradients is 'light-tailed' meaning it is sub.Gaussian and also on the RDP analysis of the subsampled Gaussian mechanisms provided by Abadi et al. (2016) which connects the level of DP noise and epsilons. This way convergence bounds w.r.t. epsilons and deltas can be provided. ", "summary_of_the_review": "All in all, I feel this is a borderline case and I hope the authors can clarify some of my concerns.", "strength_and_weaknesses": "Pros:\n\n- The paper is generally well written and easy to follow.\n- The convergence analysis seems solid, it is impressive that same asymptotics are obtained as in (Bassily et al., 2014) for Lipschitz continuous loss functions.\n\nCons:\n\n- The value clipping part is perhaps a bit weak part of the paper, e.g. the drop in test accuracy for MNIST is quite big (around 5%).\n- Experiments could be improved: instead of showing all those training accuracy figures, would be more interesting to see how the value clipping behaves for different values of $\\sigma$ and different values of $\\varepsilon$.\n- Some parts are a bit unclear, the presentation could be improved here and there. Let me elaborate:\n\nHow are actually the growth condition parameters $\\beta_1$ and $\\beta_2$ determined for the neural networks? I looked at Appendix E, and I only see bounds on the gradients, but there is nothing that explicitly says how to a priori bound $\\beta_1$ and $\\beta_2$. Could you elaborate on this and explicitly show how to determine them? How big is then the gap to the actual gradient norm, i.e. how loose are the bounds?\n\nYou write: \"The value clipping step (line 4 of Algorithm 3) can be realized within one forward-backward propagation if the GC parameters are given in advance. Therefore DP-SGD-VC can be as fast as the vanilla SGD algorithm.\"\n\nBut are they given in advance in the experiments? Or do you compute them using the expressions of Appendix E at each iteration? As far as I see, to have rigorous DP guarantees, that is required.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AeYukKmMRqo", "reviewer": "Reviewer_bKYj", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper suggests convergence analysis of Differentially Private SGD with gradient clipping (DP-SGD-GC) in a smooth, unconstrained setting without bounded domain and Lipschitz continuity assumptions. Obtained results match the previously obtained bounds (for a more restrictive case) under an additional light-tail-noise assumption. In addition, the authors suggest a novel value-clipping technique and compare it to standard gradient clipping in a simple numerical study with neural networks on  MNIST and CIFAR-10 datasets.", "summary_of_the_review": "Overall this is a good submission with a strong theoretical contribution and a good practical potential worth accepting to a conference.\n\n**Minor comments**\n\nI would like to ask the authors to adjust some of the citations by using the `\\citet` LaTeX command not to duplicate text. Especially in the Related Work section.\n\nSmall typos on page 18 (top): lower indexes for $z_t \\to z_i, u_t \\to u_i$ and $Z_{T-1} \\to Z_{t-1}$", "strength_and_weaknesses": "## Strengths\n\n- Removal of the restrictive bounded domain and Lipschitz continuity assumptions seems a novel and significant contribution.\n- Proposed Value Clipping may be practically useful for certain settings. There is a potential for better scalability in comparison to standard gradient clipping.\n\n## Weaknesses\n\n- Numerical results are quite simple which is fine for me, as the main contributions are theoretical. Though they serve a well-illustrative purpose.\n\n- Assumption 4.1 needs to be discussed in more detail. In my view, it is not enough to mention some not-very-recent references as the optimization field progressed quite a lot from that time. Namely, when does this assumption hold in practice? I see how it makes sense for a simple case of additive Gaussian noise for stochastic gradient estimates. But what are the assumptions on the distribution involved in the expectation? Does $i \\sim \\mathcal{U}[1, \\dots, n]$ or other mini-batch samplings (better suitable from a differential privacy perspective) fit into this framework?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster