Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach
Authors: Xinwei Zhang
Zhiqi Bu
Steven Wu
Mingyi Hong
Venue: ICLR 2024 poster (2024)
Keywords: Differential Privacy
Error-feedback
Differentially private training
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We proposed a clipped error-feedback approach to debias the clipping biase in DPSGD and proved both convergence and privacy guarantee.

Abstract: Differentially Private Stochastic Gradient Descent with Gradient Clipping (DPSGD-GC) is a powerful tool for training deep learning models using sensitive data, providing both a solid theoretical privacy guarantee and high efficiency. However, existing research has shown that DPSGD-GC only converges when using large clipping thresholds that are dependent on problem-specific parameters that are often unknown in practice. Therefore, DPSGD-GC suffers from degraded performance due to the {\it constant}  bias introduced by the clipping. In our work, we propose a new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC, which offers a diminishing utility bound without inducing a constant clipping bias. More importantly, it allows for an arbitrary choice of clipping threshold that is independent of the problem. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on R{\'e}nyi DP. And we demonstrate that under mild conditions, our algorithm can achieve the same utility bound as DPSGD without gradient clipping. Our empirical results on standard datasets show that the proposed algorithm achieves higher accuracies than DPSGD while maintaining the same level of DP guarantee.

Published as a conference paper at ICLR 2024
DIFFERENTIALLY PRIVATE SGD WITHOUT CLIPPING BIAS: AN ERROR-FEEDBACK APPROACH
Xinwei Zhang
Zhiqi Bu Amazon Al. woodyx21 80 comm
Zhiwei Steven Wu
University of Minnesota than62344 umn. edu
Carnegie Mellon University
eevenw cmu edu
Mingyi Hong
University of Minnesota mhong@umn. edu
ABSTRACT
Differentially Private Stochastic Gradient Descent with Gradient Clipping (DPSGD- GC) is a powerful tool for training deep learning models using sensitive data, providing both solid theoretical privacy guarantee and high efficiency. However, using DPSGD-GG to ensure Differential Privacy (DP) comes at the cost of model performance degradation due to DP noise injection and gradient clipping. Existing research has extensively analyzed the theoretical convergence of DPSGD-GC, and has shown that it only converges when using large clipping thresholds that are dependent on problem-specific parameters. Unfortunately, these parameters are often unknown in practice, making it hard to choose the optimal clipping threshold. Therefore, in practice, DPSGD-GC suffers from degraded performance due to the constant bias introduced by the clipping. In our work, we propose new error-feedback (EF) DP algorithm as an alternative to DPSGD-GC, which not only offers a diminishing utility bound without inducing a constant clipping bias, but more importantly, it allows for an arbitrary choice of clipping threshold that is independent of the problem. We establish an algorithm-specific DP analysis for our proposed algorithm, providing privacy guarantees based on Rényi DP. Additionally, we demonstrate that under mild conditions, our algorithm can achieve nearly the same utility bound as DPSGD without gradient clipping. Our empirical results on standard datasets show that the proposed algorithm achieves higher accuracies than DPSGD while maintaining the same level of DP guarantee.
INTRODUCTION
Background. Deep learning models have demonstrated exceptional promise in understanding various types of data, including images, texts, speech, and others. The exploding data volume has significantly accelerated the development of deep learning and has led to remarkable success in various tasks, including computer vision (Dosovitskiy et al. 2020), natural language processing (Vaswani al. 2017), and speech recognition (Gulati et al. 2020). However, recent research (Nasr et al. 2018 Zhu al. 2019) has shown that the training and inference processes of deep learning models may leak sensitive information in the training data, such as typing history, financial records, medical records, and social network data. To address this concern, the concept of differential privacy (DP) introduced by Dwork (2006) has become a widely accepted privacy requirement for releasing datasets (Dwork 2008. Wang al. 2016) and training machine learning models (Bassily et al. 2014 Abadi al.
2016, Wang et al. 2020: Chen et al. 2020). The DP notion provides a quantitative measurement that reflects the abstract privacy requirement in a general setting. Intuitively, DP prevents adversarial third parties from identifying whether any piece of data has appeared in the dataset has been used for training the model, with access to all released information. The notion of DP has also been integrated into the procedure of training deep learning models, such as DPSGD (Abadi et al.) 2016) in centralized training and DP-FedAvg (Andrew et al. 2021 McMahan et al. (018b) in distributed optimization.

---

Published as a conference paper at ICLR 2024
The DP guarantee of DPSGD relies on injecting DP noises into the released updates at each iteration, and the variance of the injected noise depends crucially on the sensitivity of the algorithm. In the practical implementation of DP-SGD, the gradient clipping operation is used for bounding the algorithm sensitivity of each update in DPSGD (Abadi et al., 2016). Although enjoying a promising theoretical privacy guarantee and simple implementation, the DPSGD algorithm with gradient clipping (DPSGD-GC) still faces critical challenges in theoretical analysis and practical implementation.
Challenges. In terms of theory, although the inclusion of clipping operation in DPSGD-GC ensures a strong DP guarantee. considerably complicates the convergence analysis compared to the vanilla SGD algorithm. This is because the expected update direction. which is the expected clipped per- sample gradient DPSGD-GC, may change dramatically, and additional effort required to analyze its alignment with the true gradient. Therefore, the early works on DPSGD with convergence analysis assume that the clipping threshold is chosen to be larger than the magnitude of each per-sample
gradient, essentially making the clipping operation ineffective during training (Bassily al. [0144]
Wang et al. 2016; Feldman et al. 2020 Iyengar et al., 2019 Xu et al., 2021 Zhang et al. 2022]
et al.] 20022). Recent works use altemattve assumptions and improve the convergence analysis for DPSGD-GC. but the convergence results still rely on an
choice of the clipping
threshold (Fang al. 2022; Chen et al., 2020 Yang al., 2022 Qian al., 2022 Zhang et al.
2020 Koloskova et al. 2023). However, the bounds in the assumptions of real-world problems are
hard estimate, and such a choice of clipping threshold is impossible to be satisfied in practice.
Recent work Koloskova et al. (2023) has shown a negative result that, under the general assumptions for SGD, regardless of the choice of clipping threshold and stepsize. DPSGD-GC converges with a
constant bias term, meaning in the limit the DPSGD-GC algorithm only converges to a neighborhood of the optimal or stationary solution. References Chen al.] (2020); [Song et al. (2013) also provide justification that the gradient clipping shifts the stationary solution of the original problem, thus causing an unavoidable constant bias (see our fixed-point analysis in Section 2.2
In terms of practical implementation, empirical studies have shown that DPSGD- GC suffers from a severe accuracy drop compared with its non-private counterparts (Abadi et al. 2016 Bagdasaryan let al., 2019 Zhang al. 2022). The additional terms consist of the bias caused by gradient clipping (as mentioned in the previous paragraph), as well as the term caused by the injected DP noise. It follows that when implementing DPSGD-GE GC in practice, one often has to carefully tune the clipping threshold so to balance between these two terms. If a small clipping threshold is chosen, DPSGD-GC injects small DP noise into the system, leading clipping bias. On the other hand, choosing a large clipping threshold reduces the clipping bias, but to ensure the desired DP guarantees, large DP-noise has to be injected, leading to a large performance drop. Therefore, how to properly choose the clipping threshold in practice is more of an art than a science. Recently, more advanced clipping operations have been used to improve the empirical performance of DPSGD-GG GC, including adaptive clipping threshold (Andrew et al., 202I). group clipping (McMahan et al., 201 Sa), micro-batch clipping (Lee et al., (021). and gradient normalization (Yang et al. 2022; Das et al. 2021). However, the theoretical properties of these approaches are less understood. Additionally, these approaches either entail a trade-off in terms of a weaker DP guarantee or necessitate substantial amount of parameter tuning.
small DP error term, but at the cost of increased
In summary, extensive research has shown that DPSGD-GC only converges when the clipping thresholds are tuned based constants appear in various assumptions (such as the magnitude of the
gradients (Bassily et al., 2014| Wang et al. 2016 Feldman et al.) 2020 [yengar et al. 2019. Xu et al.
2021 Zhang et | 2022] Li et al. 2022). the coefficient of the gradient symmetricity (Chen et al. 2020). or per-sample gradient alignment angles (Qian et al. (021)). Unfortunately, the thresholds are
difficult to choose in practice because the aforementioned assumptions are hard to verify, thus the coefficients are typically unknown. Therefore, DPSGD-GE GC often suffers from degraded performance due to the constant bias introduced by the clipping. This fact strongly motivates a new class of DP algorithms that enjoys both DP guarantee without performance degradation, while being free of clipping threshold tuning.
Our Contributions. In this work, we propose DiceSGD algorithm for DP training with both utility and privacy guarantees using a coobllm-inneeendeen clipping threshold. DiceSGD is motivated by the error-feedback (EF) mechanism 1997, Laakso & Hartimo 1992) for cancelling quantization bias. Specifically, we propose a novel clipped EF mechanism which accumulates the error between the clipped update to the unclipped
classical procedure in signal processing (Howze & Bhattacharyyal
2

---

Published as a conference paper at ICLR 2024
one at each iteration, and feeds the clipped error back to the next update. The proposed clipped EF mechanism satisfies the DP guarantee, while still preserving the ability to compensate for the per- sample gradient clipping bias and eventually eliminating the convergence bias caused by clipping. In contrast to existing works, the proposed DiceSGD provides DP guarantee and convergence guarantee without constant bias, while allowing flexible choice of the clipping threshold. More importantly, we have observed that when the algorithm is applied to a number of applications, including image classification and natural language processing tasks, it does not suffer from performance degradation; nor does it require careful clipping threshold tuning.
We emphasize that the theoretical analysis for the proposed DiceSGD is challenging in the follow- ing sense: the clipping operation does not satisfy the firmly contracting assumption used in the typical analysis of EF algorithms; additionally, directly applying the conventional DP analysis to DiceSGD leads to an extremely loose bound. Therefore, new convergence and privacy analysis for the designed algorithm is required. We summarize our major contribution as follows:
We propose novel DiceSGD algorithm, where new clipped EF mechanism is designed to eliminate the clipping bias, while still providing the algorithm with standard DP guarantee. We provide the convergence proof for DiceSGD under general non-convex and Lipschitz-smooth assumption, and show that DiceSGD eliminates the constant clipping bias compared with DPSGD- GC with arbitrary constant clipping threshold.
We develop an segooithmm-spccjj Rényi-DP analysis for the proposed method, where the update consists of privatized state and a non-privatized hidden state. We show that DiceSGD satisfies (e, dD by injecting a slightly (i.e., a constant depending on the clipping threshold of the feedback error signal) larger DP noise compared with DPSGD-GC.
Finally, we perform rigorous empirical comparisons of our method to DPSGD-GC on a number of publicly available datasets to demonstrate the ability of our method to train models with a high privacy guarantee and good performance. Further, we conduct ablation studies on DiceSGD to show its stability in the choice of hyper-parameters.
PRELIMINARIES
2.1 NOTATIONS AND ASSUMPTIONS
Problem formulation Throughout the paper, we consider the following empirical risk minimization (ERM) problem on dataset D == i E [I.....N]] consisting of N samples of &y:
min f(x) = N XER
((:EE)
EED
where x Rdd denotes the model parameter of dimension d. Further, we denote the per-sample gradient evaluated at x and sample &, as g! [x((', E.). The clipping operation applied to vector is defined as:
clip (v,C) = min C
|
Throughout the paper, we use superscript (-)* denote the variables in iteration f, and denote the index set of the sampled minibatch from dataset D. The formal definition of differential privacy (DP) stated below:
Definition 2.1 (c, 6-DP (Dwork 2006)). A randomized mechanism M is said to guarantee (c, 6)- differentially private, if for any two neighhoring datasets D, D' (D, D'' differ by one sample instance) and for any output measurement S, it holds that Pr(M(D) E S) S PM(() E S] + á.
To protect DP, we consider the commonly used Gaussian mechanism (work 2006 2016), which injects additive noise into the output of the algorithm.
Abadi et al.
Definition 2.2 (Gaussian Mechanism sensitivity A
(Doork 2006)). Suppose an algorithm f D + Rd has &
max [ - f(D') A D,D
Then for any > 0,8 S 1, by adding random Gaussian noise to the output of the algorithm
M(x) (xx w, with o2 where A, A 22222m2225/// the algorithm f fi (c, 8)...
3

---

Published as a conference paper at ICLR 2024
Algorithm DPSGD Algorithm with Gradient Clipping
1: Input: x DDDCC
2: for I - 17--10 do
3: Uniformly draw minibatch B from D
4: of clip (V
5: x = x' iE o +w),,)
6:
where w ~ NO of
7:
end for
2.2 DPSGD-GC ALGORITHM
The update of DPSGD-GG algorithm (Abadi al., 2016) is given in Algorithm I first samples mini-batch B of size B and computes the per-sample gradient at each step. Then, it applies the Gaussian mechanism by clipping the per-sample gradient with (2) and injecting the DP noise. Finally, the algorithm updates the model parameter with the averaged privatized mini-batch gradient. It has been shown that DPSGD-GC guarantees (e, O)PP with sufficiently large injected noise (Abadi et al. 2016).
The algorithm
Theorem 2.3 (Theorem Abadi et al. (2166). Given N, B,T and C, there exist positive constants TB2T N
> 0, by choosing of 2 (²) Algorithm is guaranteed to N22
u, v, such that for any < be OD.
Although providing a strong DP guarantee, the convergence property of DGSGD-GC is less satisfac- tory. Recent work Koloskova et al. (2023) has shown that without any extra assumption, DPSGD-GC with an arbitrary clipping threshold converges with a constant clipping bias, regardless of the convex- ity of the problem. Prior works that show the convergence of DPSGD-GE rely on extra assumptions on the problem and clipping thresholds that depend on these assumptions. Specifically, CCen et al.) (2020) proves the convergence of DPSGD-GC under the assumption that the per-sample gradients have symmetric distribution; Jin al. 2022) gives a high probability convergence result assuming that the per-sample gradients have a bounded domain and sufficiently large clipping threshold; Yang al. (2022) establishes the convergence of DPSGD-GC by assuming that the deviation of per-sample gradient from the true gradient is bounded, and using a clipping threshold larger than the per-sample gradient deviation to ensure that clipped gradient "aligns" with the true gradient; light-tailed gradient variance assumption and large clipping threshold has been used by Fang et al. (2022) to provide high probability bound without constant bias.
To intuitively understand why DPSGD GC requires additional assumptions on the per-sample gradients and large clipping threshold, let us consider the exintpoint of DPSGD-GC. From the algorithm's 's update in Algorithm
Fixed-poin analysis
[
at the fixed point of DPSGD-GC, we have:
Σ clip (VI(x;)),C) w )]
E x 17
clip
E[x]
Σ (V)((x)))
indicates that EN (V
is the fixed-point of DPSGD-GC. but it is clear
that such an equality does not imply Vf(x) = 0 in general. Thus DPSGD-GC is not guaran- teed to converge to the solution of the problem ( where fx(x) O. Additionally, from the fixed-point of DPSGD-GC, we can also understand how the extra assumptions and clipping thresh- olds guarantee convergence. For example, by using a clipping threshold larger than the deviation of per-sample gradient (Yang et al. [|V Ex) ff(x)]l [[]]]
2022), it guarantees that when (x() 0, it holds that
I C. and
N
N
(Vp
= = O,
N
becomes the fixed-point DPSGD-GC.
Although providing theoretically sound convergence analyses, the theoretical results in Chen et al.) (2020); Jin et al. (2022): Yang et al. (2022); Fang et al. (2022) do not provide practical guidance on choosing the clipping threshold in real-world applications. In these works, the choices of clipping
4

---

Published as a conference paper at ICLR 2024
thresholds depend the problem parameters, which are hard impossible estimate. Therefore, these analyses cannot guarantee that clipping thresholds used in real-world training satisfy the requirements. Thus, DPSGD-GC still suffers from constant clipping bias, and there is strong need to design a new DP algorithm that does not suffer from clipping bias.
2.3
ERROR-FEEDBARN FEEDBACK (EF) SGD
The EF mechanism has been used to debias the quantization error in signal processing (Laakso & Hartimo 1992) and has been introduced to optimization algorithms for bias compensation when
transmitting biased compressed gradients (Karimireddy et al. [2199] Stich & Karimireddy] 2020 Li
et al. 2022). The EF mechanism for compressed SGD (EFSGD) writes (Karimireddy al. 2019
x x² ryv" e' = e' g v
where V := Compress(e' + g¹) is a biased compressor and g' is the (estimated) gradient. By using the EF mechanism, the bias caused by compression be controlled by the stepsize 17 and fully climinated, thus providing better convergence performance than the original compressed SGD algorithm. In the recent works RRichtárik et al. (.2TT) Markov EF mechanism proposed for simpler implementation and is used for both compression and clipping. However, this EF mechanism fails deal with stochastic noise in the gradient estimation. EF has also been used in distributed DP algorithm with compression (Li et al. 2022), where the proposed SoteriaFL framework adopts a "shifted compression" mechanism eliminate the compression bias when transmitting the privatized local updates. Although showing promising potential in dealing with biased updates caused by compression, the existing EF mechanism has not been directly applied debias the gradient clipping operation; nor has it been used as a component in DP algorithms.
DIFFERENTIALLY PRIVATE CLIPPING ERROR -EEORFFE SGD
In this section, we present the proposed Differentially Private Clipping Error-Feedback SGD (DiceSGD) algorithm inspired by the EF mechanism, which has both convergence and DP guarantee under an arbitrary choice of clipping threshold. We show that under mild assumptions, DiceSGD can fully eliminate the clipping bias in DPSGD-GC even when a small and threshold is used.
clipping
3.1 ALGORITHM DESCRIPTION
Our DiceSGD algorithm is described in Algorithm 2 and Figure D At round t, the algorithm first computes the update direction v by adding the clipped stochastic gradient with the clipped feedback error. Then, the algorithm updates the model parameters xf with v and injects the DP noise w'. Finally, it computes the clipping error * for the next iteration. The algorithm only releases x' at iteration and does not release e' nor v
In the proposed algorithm, we introduce extra variable e' that records the clipping error. We keep it unclipped and privatize it when computing the update direction in the next iteration. As an important algorithm design considera- tion for DP requirement, unlike the original EF mechanism, we do not feed e' back directly to each per-sample gra- dient clipping operation (Line 5), because would break the sensitivity of the algorithm. Rather, we first clip e' and add to the averaged clipped gradient. Using such clipped EF mechanism for privacy guarantee, can balance the functionality of EF and the DP requirement of the algorithm.
Clipped
Irmiion
caplis
leentiont
-ptel w()
Figure 1: The flow diagram of DiceSGD. The clipped EF components high- lighted red, and DP components are marked in yellow. =-1 denotes the unit delay.
To see why the proposed algorithm has the potential of eliminating the clipping bias, let again study the fixed- point the DiceSGD algorithm. At the fixed-pont soint, we have the following relation, where the expectation E[.] is
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 DiceSGD Algorithm
1: Input: x", D, C, 2)
2: Initialize: e 0
3: for m- (or:=,,..... -o..=0..,,'-1
4: Randomly draw minibatch B from D
5: v² = 1 EiEs: clip (V](x';;),, C1) clip (e', C2)
6:
x =x -n' + w'), where w² ~ W(0 of I)
7: e =e + BB LieB v
8:
end for
taken on the randomness of the samples the current iteration.
E[x] [ 1
w| - [[[v],
Elee] = E ee + EE|
Σ
V)(x; - v] E[e] E v)(x Ely)
BEB
Therefore, from the above two equations, we can derive that
Nv
E v
Clpp(V/(x:))),))) + (e, = =0,
N
1
clip clip C2)
vx(&),
N
which indicates that the fixed-point of DiceSGD is given by
N
Σ clip (VI((;;)),)) = -clip (e, C2), and Σ V((x))
We can show that when C2 2 C1, there exists x, e such that the fixed point is achieved. Specifically, by choosing x satisfies V /x(x) 0; and e is chosen as e = - Em clip (V fx(x;; Ex), that
E,), C1). Note
1 N
Σ ||l| = N
clip (V/((;)),C)
<
|llip (V)( CI.
we have clip (e, C2) guarantee that the two equations are satisfied and the fixed point is achieved. The fixed-point analysis indicates that, unlike DPSGD-GC, clipped EF can potentially fully compensate the shift of the stationary solution caused by gradient clipping independent of any problem assumptions, and [x( 0 the fixed point of DiceSGD.
long as C2 > Cj. and the first equation is satisfied. These choices
long C2 C1, condition that is problem independent,
3.2 THEORETICAL ANALYSIS
In this section, provide analysis for the proposed DiceSGD algorithm. We emphasize again that the challenge here two-fold: 1) is difficult to analyze convergence due to the combination of the EF mechanism and the clipping operation; 2) the DP analysis is non-trivial due the presence of the non-privatized update of e' as hidden state. To see the first challenge, more specifically, the analyses of the convergence of the existing EF algorithms (Karimireddy al. 2019 Li al. 2022) relies on the assumption that the feedback error c+1 in (3) is firmly contractive mapping on g
E B = E Eleet g' Compress(e + +g s a ||ee + +
where a E (0, 1) is constant strictly less than 1. However, in DiceSGD, the clipping error does satisfy this property. To see this, note the following:
Σ (f(())) clip (e') (dip(oo) + Σ clip (vf(x')))) FE8
KE

---

Published as a conference paper at ICLR 2024
Sa
Σ CEB
V
a (0.1),
B
which is non-expansive, i.e., a - 1 when I EieB: v cc. Therefore, the existing convergence analyses for the EF algorithms cannot be directly applied to our case. On the other hand, privacy analysis for DPSGD is provided in Abadi et al. (2016), where the sequential updates are released, and recent works studying the privacy amplification by iteration provide last- iterate DP analyses for DP algorithms where only the final state is released to public (Feldman et al. 2018 Ye & Shokri, (022). However, the update of DiceSGD is more complicated than the above two cases, as the sequential update of xf is released and privatized, while c', the hidden- state with non-privatized updates, is not released to the public. It is insufficient to directly use the existing DP analyses for DiceSGD, because when applying the privacy analysis for DPSGD to the sequence {(x', e in DiceSGD, the composition theorem does work et is not privatized. To tackle the above difficulties, we conduct novel analyses for DiceSGD, which consists of the convergence analysis for clipped EF and DP analysis for algorithms with privatized public state and a non-privatized hidden state.
We briefly discuss the assumptions used in the analyses of DiceSGD algorithm: Assumption 3.1 (Lower Bounded), The loss function f(-) is bounded from below by some finite constant f*:
Assumptions
f(x 2 I" -00, V x E Rd_
Assumption 3.2 (Smoothness). The loss function f(-) is L-Lipschitz smooth, i.., it satisfies:
[V](()= - V S L ||x - yll x, E Rd.
Assumption 3.3 (Strong Convexity). The loss function f-) is p-strongly convex:
) 2 f(x) + (V/(x). x) x - yl? ex
Assumptions [ and 3.2 are standard assumptions used for analyzing the convergence first-order
optimization algorithms. The strong convexity assumption has also been widely used in analyzing
SGD-type algorithms in both private <Wang et al., 2020 [Son et al. 2020; Kamath et al., 2022
Koloskova et al. 2023) and non-private (Rakhlin al.) 2011) settings.
Assumption 3.4 (Bounded Variance). The stochastic gradient estimation is unbiased, i.e., E ggi
fx(),, and its variance satisfies that there exists constant 0, such that E f ,, V x E Rdd
Assumption 3.5 (Bounded Gradient). The gradient of the function is bounded in the sense that there exists positive constant G = suPxER* [ co.
Assumptions 3.4 and 3.5 are commonly used for analyzing clipping operation Zhang et al. 2020
Qian et al. 2 Song al. 2020). the convergence of DP algorithms (Yang al. 2022), and dis- tributed optimization (Li et al. 2022, Zhang et al.) 2022). Assumption 3.4 assumes a smaller variance compared with the typical assumption (i.e., E [ g.11² < g²), it implies that |1
[V g. < <²,, V i, and it is necessary for bounding the clipping bias in the existing works (c.g..in Yang et al. (2022)) ). Although these assumptions are also used in our analysis, contrasting with existing works, the clipping thresholds C1, C2 in DiceSGD do not depend G a.
We now present the convergence theorem of the proposed DiceSGD algorithm under the non-convex smooth setting Assumption 3.2
Theorem 3.6. Assume the problem satisfies Assumption 3.7
3.2 3.4 and 3.5 Given any constant
DP noise multiplier 01, by running DiceSGD (Algorithm 2 for T iterations, choosing stepsize
2(f(x*)) TM224 330 +dofy. clipping thresholds C2 2 3C, + 1 0. It satisfies
7
S2 2L(f(x)) (2C + 3C3 + dof)
E, [|((})]]
(4)
T
where the expectation E, is taken over & (0, (O,...,T T-....T-11) 1}, following distribution {Ac) E (0, 1] being strictly positive sequence defined in 12 Appendix A
with
A,
7

---

Published as a conference paper at ICLR 2024
Table 1:
The comparison between DPSGD, DPSGD-GC, and DiceSGDin terms of convergence, privacy noise, and clipping thresholds. (G 20 Cf)
Algorithm
Convergence Rate
Privacy Noise Variance
Assumptions
Clipping
G 1//
G logl
DPSGD
O
3.4
3.5
C2 G+o
Ne
DPSGD-GC
O
C Pogtl//88 Nt
O(1)
C V Topl 22
3.4 3.5
C<G+a
/ G (og((1)))
GT logl
DiceSGD
0
3.4
3.5
Independent of G
Proof sketch of Theorem 3.6
1. We first apply the convergence analysis of biased SGD for non-convex problems with update direction B[v"]. Due to the EF mechanism, the convergence result for DiceSGD directly depends on the recursion of c², which corrects the bias iteration 1.
2. With the update of e', we can derive a recursive bound on the key term (V)(x') E[e')). Unlike EF for contracting error, which depends on the gradients with a constant factor independent T, the error e' caused by clipping operation requires much tighter recursion directly the inner product between ef and fx(x)) for analysis. And the coefficients before the gradient heavily depend on the clipping factor.
3. By substituting the bound of (x'),,, E(e"]) into the convergence result in step 1, and choosing sufficiently small stepsize and adequate clipping factor ratio that compensates for the stochastic noise and the clipping bias, we are able to derive non-trivial convergence result for DiceSGD.
Theorem 3.6 indicates that the overall convergence rate for DiceSGD is + for the general
non-convex setting, which matches the O 7 lower bound convergence rate of DPSGD without
gradient clipping under non-convexity (Bassily et al. 2014 Rakhlin et al.) 201T). However, compared
with DPSGD-GC (Koloskova et al. 2023). DiceSGD fully eliminates the constant bias and improves
the convergence rate from ((1) to O The comparison is shown in Table 1
Privacy guarantee Let us proceed with the privacy analysis of DiceSGD, We start with the notion of Rényi Differential Privacy (Mironov] (017]. By accounting for the distribution divergence of the stochastic gradient at iteration f and the accumulated difference of e' starting from e", we are able to bound the Rényi divergence of - given two adjacent datasets D, D' and start with the same x". Then by using the composition theorem of Rényi divergence, we provide the privacy guarantee for DiceSGD in the next result.
Theorem 3.7. Assume the problem satisfies Assumptions 3.4 and 3.5 given constant C, by fixing the B clipping thresholds 0 < C1 S C2 I C/B. independent of G, a, and assume N S Choose DP noise standard deviation di as
32T (og(1/6)
of N
2
where à = + 2 (C2,0"2) G22), and G' defined in Theorem iteration, the algorithm guarantees (c, (6,8)-diffrrentilly private.
3.6 Running DiceSGD for T
Note that although Assumptions 3.4| and 3.5 are used in the proof, the result does not rely on the specific values of the bounds, which can be arbitrarily large. Due to the accumulated influence of the update of e., the DiceSGD requires larger DP-noise than the DPSGD algorithm (larger by a constant multiplicative factor). The detailed proof is given in Appendix A.2 By optimizing T we have the following uiiitt--rivacy trade-off for Dice
Corollary 3.8. Under the same assumptions of Theorem 3.6 choose the stepsize v =0 (+7)) and
clipping thresholds 0 < 3C1 < C2 S <C/B, and choose noise multiplier of as Theorem 3.7 By iterations, the algorithm guarantees (e, 6DP while
running DiceSGD for T = 0 [log(1/8)
N²2
8

---

Published as a conference paper at ICLR 2024
Table 2: Test accuracy DPSGD-GC and DiceSGD on Cifar-10 and Cifar- 100 datasets with different clipping thresholds and (2, 10 D-DD.
Dataset
Clipping.
DPSGD-GC
DiceSGD
SGD
Cifar-10 10
1.0
95.2%
97.4%
99.0%
Cifar-10
C = 0.1
94.5%
97.5%
99.0%
Cof
= 1.0
92.0% 79.0%
86.3%
Cifar-100
C' = 0.1
78.9%
86.5%
92.0%
converging to solution where the loss function satisfies:
[VGlo(118)
E|| {(())
Ne
The corollary indicates that when N + oc, the expected loss converges with rate O lost N
with
arbitrary clipping thresholds C2 2 C1 > 0 and eliminates the constant clipping bias in DPSGD-GC.
4 NUMERICAL EXPERIMENTS
In the experiment, we use the similar Adam variant DPSGD-GC developed following Bu et al. (2021) to implement both DPSGD-GC and DiceSGD (see Appendix C.3 for details). We perform extensive evaluations of DiceSGD on image classification, and natural language processing (NLP) tasks to demonstrate its advantage W-2102 CPU with an NVIDIA TITAN GPU for image classification, and on an NVIDIA A100 GPU for NLP tasks. We conduct extra ablation studies the choice of the clipping threshold Ci C2 and learning rate yj on Cifar- 10 and Cifar- 100 datasets, which show that DiceSGI) benefits from using smaller clipping threshold and choosing C2 C1 gives the best result most cases. More results and discussions are given in Appendix C.I due to the space limitation.
OPSGD-GC. The experiments were
an Intel Xeon
Image classification. We both Cifar-10 10 and Cifar-100 datasets for experiments and use ViT- small (Dosovitskiy et al. (020) as the training model, which is pre-trained on Imagenet. We fine-tune the model for 3 epochs with batch size B 1000. The stepsize for DPSGD-GC and DiceSGD are selected through grid search from 1) E (10-2, 2, 10-3 10-1). The experiment results are shown in Table
Natural language processing. To validate the ability of DiceSGD for training larger models on different tasks, we further conduct experiments on the NLP task. Specifically, we fine-tune the GPT-2 model (Radford et al. 2018) on the E2E NLG Challenge for 10 epochs with batch size B = 1000, and report the standard metrics such as BLUE, ROUGE-L, etc., used Hu et al. (202T) for evaluation. The results in Table 3 show that DiceSGD has better performance than DPSGD-GC.
To summarize the results of our experiments, we see that both image classification and the NLP tasks, DiceSGD outperforms DPSGD-GC. and sometimes by significant margin.
5 CONCLUSION
In this paper, we propose the DiceSGD algorithm for DP training. The algorithm uses a clipped crror-feedback mechanism eliminate the bias in gradient clipping. We provide novel convergence analysis in the strongly convex setting or under PL condition for DiceSGDwith a problem-independent clipping threshold and provide the DP guarantee independent the problem type. Numerical results show superior performances of DiceSGD compared with DPSGD-GC on image classification and NLP tasks and the robustness DiceSGD to the clipping threshold.
Table Scores fine-tun tne-tuning GPT-2 on E2E NLG Challenge, with C 1.0 and (8, 8 10-6) -D-DP.
Algorithm DPSGD-GC
BLEU
NIST
METEOR
ROUGE-L
CIDEr
56.8
4.83
36.2
65.2
1.43
DiceSGD
62.6
7.05
38.5
66.6
1.83
SGD (Hu et al. 2021
70.4
8.85
46.8
71.8
2.53

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
M. Hong and Zhang are supported by NSF grants CCF 1910385 and EPCN 231 X. Zhang supported by Doctoral Dissertation Fellowship 2023, University of Minnesota.
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMAhan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318- 2016.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455- 17466, 2021.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in neural information processing systems, 32, 2019.
Raef Bassily, Adam Smith, and Abhradeep 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. IEEE, 2014.
Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Hanwen Shen, and Uthaipon Tantipong- pipat. Fast and memory efficient differentially private-sgd via projections. Advances in Neural Information Processing Systems, 34: 14:11980-19660 2021.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. Advances in Neural Information Processing Systems, 36, 2024.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances Neural Information Processing Systems. 33:13773-13782 2020.
Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, and Inderjit S Dhillon. On the convergence of differentially private federated learning on non-lipschitz objectives, and with normalized client updates. arXiv preprint arXiv:2106.00 07094, 2021.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint 20t::22044136300 2022.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Cynthia Dwork. Differential privacy. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings. Part II 33, pp. 1-12. Springer, 2006.
Cynthia Dwork. Differential privacy: A survey of results. Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi an. China, April 25-29, 2008. Proceedingss pp. 1-19. Springer, 2008
Huang Fang, Xiaoyun Li, Chenglin Fan, and Ping Li. Improved convergence of differential private sgd with gradient clipping. In The Eleventh International Conference on Learning Representations, 2022.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEBE, 2018.
10

---

Published as a conference paper at ICLR 2024
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
Manuel Gil. On rényi divergence measures for continuous alphabet sources. PhD Thesis, 2011.
Anmol Gulati, James Qin, Chung- Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: Convolution-augmenned transformer for speech recognition. Proc. Interspeech 2020, pp- 5036-5040, 2020.
J.W. Howze and S.P. Bhattacharyya. Robust tracking, error feedback, and woo-degree-of-freedme controllers. IEEE Transactions Automatic Control, 42(7):980-983, 1997. doi: 10.1 599977.
Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang. Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2021.
Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 299-316. IEEE, 2019.
Chenhan Jin, Kaiwen Zhou, Bo Han, James Cheng, and Ling-Chang Yang. Efficient private sco for heavy-tailed data via clipping, arXiv preprint arXiv:2206. 13011, 2022.
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference Machine Learning, pp. 10633-10660. PMLR, 2022.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp.
PMLR, 2019.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. arXiv preprint arXiv:2305.01588 2023.
Timo Laakso and liro O Hartimo. Noise reduction in recursive digital filters using high-order error feedback. IEEE Transactions on Signal Processing, 40(5):1096-1100 1992.
Edward H Lee, Mario Michael Krell, Alexander Tsyplikhin, Victoria Rege, Errol Colak, and Kris- W Yeom. Nanobatch dpsgd: Exploring differentially private learning on imagenet with low batch sizes on the ipu. arXiv Computer Science, 2021.
Zhize Li, Haoyu Zhao, Boyue Li, and Yuejie Chi. Soteriafl: A unified framework for private federated learning with communication compression. Advances in Neural Information Processing Systems, 35:4285-4300, 2022.
H Brendan McMahan, Galen Andrew, Ulfar Brlingsson, Steve Chien, Ilya Mironov, Nicolas Papernot, and Peter Kairouz. A general approach to adding differential privacy to iterative training procedures. arXiv preprint arXhv:1812.062110 2018a.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference Learning Representations, 2018b.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263-275. IEEE, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv:1908 10530, 2019.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning.
In Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP), pp. 1-15, 2018.

---

Published as a conference paper at ICLR 2024
Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clipping in incremental gradient methods. In International Conference on Artificial Intelligence and Statistics, pp. 1504-1512. PMLR. 2021.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, al. Improving language understanding by generative pre-training. 2018.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint / 2011.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34: 4384 4396, 2021.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differen- tially private updates. In 2013 IEEE global conference on signal and information processing, pp. 245-248. IEEE, 2013.
Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gradient descent on convex generalized linear problems. arXiv preprint arXiv:2006.06678, 2020.
Sebastian Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. The Journal of Machine Learning Research, 21 (1):9613-9648, 2020.
Wataru Takahashi. A convexity in metric space and nonexpansive mappings, i. In Kodai mathemat- ical seminar reports, volume 22, pp. 142-1442 149. Department of Mathematics, Tokyo Institute of Technology, 1970.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Di Wang. Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pp. 10081-10091. PMLR, 2020.
Qian Wang, Yan Zhang, Xiao Lu, Zhibo Wang, Zhan Qin, and Kui Ren. Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy. IEEE Transactions on Dependable and Secure Computing, 15(4):591-606, 2016.
Asynchronous decentralized parallel stochastic Jie Xu, Wei Zhang, and Fei Wang. A (DP)² SGD:
gradient descent with differential privacy. IEEE Transactions on pattern analysis and machine intelligence, 44(1 1):8036-804 2021.
Xiaodong Yang, Huishuai Zhang, Wei Chen, and Tie-Yan Liu. Normalized/clipped sgd with per- turbation for differentially private non-convex optimization. arXiv preprint 2033332206.1033,, 2022.
Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). In Advances in Neural Information Processing Systems, volume 35, pp. 703-715, 2022.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 33:155 1-15521, 2020.
Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. In International Conference on Machine Learning, ICMI. 2022, 2022.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2024
Symbol w
Meaning
model variable, privacy noise, feedback error objective function dataset, minibatch, data sample
f(-)
N, B,i
Dataset size, minibatch size, data index
g+ f((
gradient evaluated & parameters of (e, 6D-DP total iteration, iteration index strong convexity (PL condition), Lipschitz, variance constants clipping thresholds
6 T,t
n. L. C,
clipping factors of g/. i.e., min(1, }, min C2 |
lie|1
A
update of x*+1 and e'+1, i.c. lines 4,5,6 and 4,5,7 of Algorithm 2
H
sequence of {x", x² )
A A
difference of g' with D, D', i... Lies clip (g', C1) π Lie clip (gf Ci)
update difference of e' with neighboring datasets, i.e. et - e²"
Table 4: Symbols used in the paper.
A PROOF OF RESULTS IN SECTION
In this section, we provide detailed proofs of the theorems in Section We find the following relations usefull:
||a + b11 s (1 (1+ ||al2 (1 x)= |1b| 1101,,
(5)
(a, b) = 1 (lall + [|b|12 - 11a b1())
(6)
Lemma A.1. Given a random variable X Tedd Ifc()) Rd TRd a non-expansive mapping, such that [[c(a) c(b) s ||a bll, then Var(c(X)) Var(X). Additionally, function c(x)
x clip (z, C`) is non-expansive mapping for any positive constant clipping threshold >
The proof is given in Appendix A.4
Theorem A.2. Assume the problem satisfies Assumption 3.7
3.2 3.4 and 3.5 Given any constant
DP noise multiplier σ1, by running DiceSGD (Algorithm 2 for T iterations, choosing stepsize
2(f(x9)-f") 7 v TL1207+3C3+ad clipping thresholds C2 2 3C1 + 8 > 0. It satisfies
2L(f(x)) (20 + 300 + do
E, [|V S 22
T
where the expectation E, is taken over i E {0, ,O. 1}. with probability Ar/ ETD Ac, with {AA} E (0, being positive sequence defined in 12..
Theorem A.3. Under Assumptions 3.4 and 3.5 given constant C, choose the clipping thresholds
0 < C < C2 < C/B. Choosing DP noise multiplier a
32T(C? 22 log)//)
N2,2
Running DiceSGD for T iteration, the algorithm guarantees (c, D)D.
Let us denote the clipping factors as of == min 1, ||s
. = min {
||lll| } so that
Co
clip (e', C2) = =a''', clip (g). C1) = aggí, and ++1 (1 a +
E (1-a()
ag)g
B
188
(8)
Note that we have the following bound of: Let consider two cases:
1) ||e'l| < C2 and
||e|l > Cg. For case 1), is clear that of 1. For case 2), we have a
C2 We can further ||''l|
13

---

Published as a conference paper at ICLR 2024
bound ||e||
recursively
|
(1 - 1- ) 1
+ Σ
(1 - af of
B
iEB'
S (1 - 1
1 le-
a1-a )ot
iEBt11
(2)
C1
e
|||
+
B
1- 1-min(4, 1,
110
-
93 x-1
1EB
(6)
I
(1 de
||ee -
||
max (0,
1EB-1
WV
||e
C2 + max (0, / // ||| -
IVg
max (0, [vf(x + - - -1- C2)
m,, G ( ( (1)) 10" - (I - 1)C2.
where (a) substitutes the definition of a²: (b) expands the last term; (c) applies Assumption
3.4
in (d) we recursively expand ||e to |e'|| and notice that |e'|| || Eiesi (1 - )9
5
max (0, Therefore, we have
(e) we apply Assumption 3.5 and define G' = max (0, G+a Ci).
C2 > e
C2 GG (1 - 1)C2
C2 C2 + 1('' -2) C2)
d²
(9)
A.1 PROOF OF THEOREM 3.6
With smoothness Assumption 3.2 we have the following descent property, where the expectation E.11] is taken on the randomness over iteration conditioned on all past histories from 0 to t:
Ex S f(x') + f E,
x'1>
+
E2
|
11
2
(0) fxx') n (V (1
Ln7
Er
||1v-12 112]
+
Ldn2
2 ot
2
Lap²
Ldn
-(xx) (V (v
Br
Σ
clip (g), Ci) clip (e', C2)
+
2 oj
B
EE
( 3 f(x)) 17 (Vf((), +
Lnd
2 (C1 C2) + Ldn o
(10)
where (a) applies the update rule of x and uses the fact that w' follows zero-mean Gaussian and is independent of v and (b) bounds |'|| by C1 + C2 with clipping operation. Next, we bound the inner-product between fx(x") and E[v'] as:
(Vf(x').
Vf((t) E. Ealet + E, age' ogde)
iEB
= (x)(''), Ea Bafg! + Ea(e")
(Vf(x'), (Vf(x²) -V (f Da'e'" - (Vf((x=') (,
(0) (Vf(x'), Bofg!) 1 /
E E(( 17(x--1)11 nt ||ag
2 1
N
( Eaa (1- --)
1 ( - N Σ a g!
14

---

Published as a conference paper at ICLR 2024
(
n
2 E =B|aaa
+
o²((1 - -
(Vf(x' Ba - - - | + a (Vf(x(-)) E,, "g )
ae
(0)
n ((C) + C2)² + doj 03) a' Vf ||
(Vf(x"),Ba(ee
2
o1(1 - a1
(vf ,, Ba - + a V 1x Ea g ;
0e 1-1
where (a) applies (6) the second term and expand e¹ with 8 (b) applies the smoothness Assump-
tion 3.2 to the second term; (c)uses the fact that w'-1 follows zero-mean Gaussian and is independent
of v and that v' = clip (e--1, C2) + 1 Eies clip (g! Ci) has magnitude less or equal
B
to C Cz.
By recursively expanding the term- - (, above as
-VVf(x"), S n ((C) + C2) + dof + 02) -a [
og - -6(1--0-1) 1 (V E E. 1 + a (Vf(x' B, ag g.
a
and note that e² = 0, al = 1, we have:
(VI(('),, E(v")) = (VI(x'), Ba -
S - (Vf(('). Eaig!) + n
2 ( + C2)3 C3) a' Vf(x''1)) >)
d1(1 1
Ba g Eaig')
ae
1-1
[-]
Σ de
II (1 (1- (1-2.-) a.:)
T=U
++=++1
II (1 )2))
( (1-)
+C + (VS( (B)()))
(ID)
Substitute
back to 10 and sum over iterations, we have:
T-1
II (1 - (0= |V/((>))
t-1
B(((xT) S f(xx) - 1)
d ΣI
n+
Ln
(1 (1- az))
(2C + 3C2 + dof) + +2C7+ + do?
de
2 t=1
1=1
T-1
1-1
Σ
(Vf(''), Eafg!
Ede
d
[1 (1-- (VF()),
T=1
T-1 T-1
f(x²) 7
Σ
Σ
II (1 (1- (1-02) ||/f(e\]1
(=0 r=
7=/+1
+ 1n Σ
Σ d
|2 + +303 + dof) + +20 + +C2 + do?
2
r=1
T-1
II (1 -3-) 02)) (V)(x))
T-1
Σ 00
II
+=
m
(8)
T-1
+ 2 BT + +30 + +doî) + Σ C.C, [[f(|()(('']]
2 1(x)) n Σ
A \
2
15

---

Published as a conference paper at ICLR 2024
where in (a) we rearrange the terms; in (b) apply Cauchy-Schwan inequality to the last term and define A,, Br, Ct accordingly. Specifically, we have
T-1 T-1
A = Σ
%
II
(1-03))
(1 (1-02) a
(12)
+=
T-1
T
Bp: = T +
I (1-03)
T +
A
(13)
1= T=1
1=0
T-1
C== 1- Σ
0
II +1=
(1 - a.. (1-
= 1 - A A.l
(14)
T=H+1
Next, we bound A,, Br, Ct, respectively. To begin with, we provide the upper and lower bounds
on A.. First, note that by definition of ag in 8.. we have o E (0. 1]. therefore the product
I (1 -a is strictly less than 1. Let T E {O.... 1} denote the iteration where 1, VI > and of = 1. Then A, can be expressed as:
T-1
4: =
Σ %
II (1 (1-08 0..) 7
(1-06')
-=
T-2
=1 - 1 de
+ +0
1 (1 0e 1+1) +
0
T-1
II og)
7=1+1
T-2
1 - (1 de
|+1)
+ +
142
- a 1+1) ................................
0
T-1
(1 o
-=|+1
T-1
t <<T,
II -=1+
(1 a²)
1 1 a.),
T2T.
Therefore, BT < 2T. C. 1 A [0, 1). Next, we show that the following relation holds: Case I: t< <<T, A = 1. it is clear that
A Vf(x') | 2 A,)C [| =.
Case ll: T', then A, < 1, we want to show the following relation holds:
a 1+1 Σ II (1-23)] > (1 A.G. /
T==++=++
Let us consider the worst case where / = TV, i.e., when the left-hand-side only has one term then, we have
at ||V](**)]
C2
a
|ett1
C2
oe a-'c'' +
Eies:
(g)
agg!
C2 (0)
<
1 e
Σ
(g) agg:)
iEB
C2 <
(
Vf +
Σ
(g) vf(x))
-
B
iEB
C2 (0)
V fx(x))
+
Σ
|
B
B
(d)
C2
C
|f((*)]|
(15)
B
16

---

Published as a conference paper at ICLR 2024
where (a) uses the fact that 0²2 a T (b) we add and subtract ff(x'); ); (c) applies triangle inequality and Assumption 3.4 and (d) we arrange the terms and use the fact that || || I C1. By
setting C2 2 3C, + z. have V f (x'')l 2C,. Further, from (15), also have that
C2
Oke
e' - a + EiE (g) - a
C2
(16)
Vf(x*) + C
where we apply triangle inequality to the denominator in the second inequality. Therefore, we have for the worst case:
C2
c+1 [[(((||
[f(x']] Vf
[
C1 +
(3C1 + 22
| > 201 | > 2(1 A,CC ||]](()||
3C1 + 8
where (a) uses the fact that [V(())++C++ [x(((]]| is monotonically increasing w.r.t // (x')) |||-
When > Ty, similar proof can be applied to show that a Σ II =
V II 2 2C1. Putting the above results together, we have:
[[((x")){((x)
"
T-1
Σ
TLi2 (20 +03 doî);
2
t=0
(17)
E, [ [1 - +
L2C + +3C2 + do?);
r/T
where C2 2 3C1 + 3. and the expectation is taken over / E t0,..., - 1}, with probability
A,/ //E A.. The theorem is proved.
A.2 PROOF OF THEOREM 3.7
In this section, we provide the privacy analysis for DiceSGD algorithm and the proof of Theorem 3.7 Specifically, we adopt the Rényi differential privacy (RDP) notion for our analysis. The definition of Rényi-DP is given as follows:
Definition A.4 (Rényi-DP Mironov (017)). A randomized mechanism M said to guarantce (a, R)DP with order > I. if for any two neighboring datasets D, D' (D, D' differ by one sample instance), holds that
(((M 1
I( ( )1
log E
Sc.
Rényi-DP can be translated into the more popular (e, 8)D Def. 2.1 with the following lemma: Lemma A.S (Proposition Mironov (017))) ). randomized mechanism M guarantees (a, R)-RDP
then it guarantees (e + log(1 log(1/))/(a - 1)) 8DPP for all ā E (0, 1).
To derive privacy guarantee for the proposed DiceSGD algorithm, we first reformulate the algorithm the following procedures. In specific, define
Ai xXx x gt x D - X' the evolution xf, i.e., lines 4,5,6 of Algorithm 2
AB X x Et x D > gh+1
1 as the evolution of e', i.e., lines 4,5,7 of Algorithm
1
H' :
II X' as the sequential observation of x i.e., (x"; x² x*).
In addition, define p and D. D'' be the two neighhoring datasets where D' contains unique sample g', i.e., D' D Then recursively bound the RDP guarantee of HC fort 1...., with three steps.
We first provide the sketch of the proof as follows:
17

---

Published as a conference paper at ICLR 2024
1. We show that the output sequence the first iteration H. satisfies (a, e c by using the RDP of the sub-sampled Gaussian mechanism.
We assume that the output of Ai conditioned on the past output sequence H satisfies (a, c')- RDP. Then we derive the RDP guarantee for the output sequence iteration + 1, i... H1 = (H' Ai [H") by the composition theorem of RDP.
We provide the RDP bound for Ao Ai conditioned on H', which consists of the sub-sampled gradients at iteration and the update of e' with A from iteration Gaussian noise. Therefore, we bound the sensitivity and Rényi divergence of .Af by accounting for the impact of the neighboring datasets on both the sub-sampled gradients at iteration t and the updates of e' conditioned on H. Using the update of e', we can recursively derive the Rényi divergence of e' from et-1 ,...,,..
1, , , combined with the
The above three steps enable to bound the (a, c²) c-D-RDP for H', the output of DiceSGD algorithm. Finally, by applying Lemma A.5 we obtain the (c, 6DD guarantee for DiceSGD algorithm.
Step I: First, when t= 1, H Al. Apply Lemma A.10 and we obtain that H. satisfies (a, c(o))- scfo
is function depending on the size of the injected noise o, and we assume RDP where <(r) z No
Step II: Claim: Suppose Ht satisfies (a, e)-RDP, A conditioned on H satisties (a, r'D-RD,, then H1 satisfies (a,e+ e'D-RDP.
Proof. Let us define Ex11xx11115 and 1 be the conditional probability-density function (PDF) of the output of Ai with neighboring datasets D and D' conditioned on the past outputs, respectively; similarly, define H,(H(), HH')') be the PDF of the output of 7t with datasets D and D'. Then H2+1(H = (H xx+1) H.(H+) ((1H))))+1(()) (xxx(x+11224 and we have
expl(a - (H (D)II****()) 1)
[ [ ( -a X (x 134'0 (x/)) dzddxtt1
=
= - 11(H4)) (( / x++1(x+11171)) X (x ( dHt' (18)
118x
(0)
S exp((( exp((a 1)²')
= exp((a - ()(c+) d)),
where (a) applies the assumptions that H' satisfies (a, (... and X satisfies (a,, R'D-RDP to the first and the second integration, respectively. Thus H++1 satisfies (a, e + RDD.
Step H:: In the above step, we use the assumption that conditioning on H", X satisfies (o, R'D-RDP In this step, we explicitly bound e' in the (a,e')-RDP of Ai conditioning on H'. We first expand the Rényi divergence of A₁ (x', D) and Ax(", D') as
(x)A( D') Da(N(x' T/V" noo (II - 7/"" nn", (a)
1)
DN - v- 1).- 02 1))
(19)
where in (a) we first shift the mean of the Gaussian distributions by -x' a factor of Let Ng be the PDF of (0 of I) and (-) denote N/ of I). Define
x' + ny² and rescale them by
8 = 1 Σ
clip (g) Ci) B
Σ clip (g) BE
B
SEB
4 e' "
Then v can be expressed
v v" = clip (e', C2)
clip (e",C2) + 4/
18

---

Published as a conference paper at ICLR 2024
Substitute the above relation of v' to 19). we have
Da - 1|ml = Da (NV (clip (e', C2) - clip (e",
(No (e'; C2) clip (2)
+ 2D. (NG (c': C2) clip ,,",C,, C2) + A
(c), clip (c" C2))
(b) 2D (No. (e', C2) clip (e", C2,, H 2D
[H"),
(20)
where (a) applies Lemma A.8 with clip (e', -cip (e", C2)
0, = clip (e' C2)
clip (e" C2): (b) shifts the mean of the Gaussian distributions the second term by -clip (e', C2)
clip (e" C2). Next, we bound the two terms in (0) separately.
Bounding the first term in 20 : To bound Da (N C2) clip (e", (c)))luao)??) First
notice that clipping operation is non-expansive with factor a.. so we have
(Nll (e', C2) clip (e", , C2) | (H')
S DD - ll = DN, (NN(((A)))))))
Then, we start with bounding the update with the following lemma: Lemma A.6. Let x², ,e, ,e,,"" be bounded by
be the input of A2. Then the Rényi divergence (a(No(Att))lln can
2G"
Da (No 11mo)) & Da((1 ( (11 (1 - + o') +
)
B
(21)
where
B N be the sub-sampling rate of the minibatch, G' max (0, G + o Ci3 and o' defined
The proof is given in Appendix A.3.1 Da (A.) (o) (H'), we have:
By applying the recursion of et given in Lemma A.6 to
+ 11 (0)
2G'
DN (A.
((((11))N.(11 ab) PNN ((1 at)s:
)1H
(1 + Da ((1 od)4t)l(ml
20' (1 4c)
+ (1 ((1 - p)) ab)=))) + PNG((11 of)4 -
@ (1+ L.
+ +(+ Do (11 - p0 + NNa( 20"
BB }1p0)
2G'
(1 - (N.
+(1+ Da
(1 p0
a
B
( $ (1 (Q=o6))D(Nc(433))
8p2
+(1 (1 + a o²
(22)
where (a) applies Lemma A.6 (b) applies Lemma A.8 and choose af; (c) shifts the mean of
the Gaussian distributions by a A in the second term; (d) applies Corollary A.9 to move the factor (1 of) the first term outside the Rényi divergence, and notice
2 a = (1 (a a²) s a.):
(e) applies Lemma A. the second term. Towards this end, we have already derived the change of Rényi divergence for the one-step update of A. Then, we further recursively expand A to A and notice A and we have:
((a 11 D (N (po) (a) S (ot+1 Gp 2
8(a
Σ
[1
II 71
B²
19

---

Published as a conference paper at ICLR 2024
(6) 8p² aG
Σ
1
(a
1 1+ ae
II
1
ai max G' C2]
oiB²²
06
C2 + 7, 00, G² -
11=++1
(0) 8p
C2(C2 + T max (0, G¹ - -2)
TI max (0, G¹ C2}
oi 7=0
(C + ma 1)(G' (c)))
C2 + ti O,
71=T-1
(4) 8p²a
C2C2 + ma (0, G' -2))
m (0, G¹ C2]
t-r
B²(C2 + max (0, (t 1)(G' C2)))
C2 + tmax (0, G' C2)
(e) 8p a min (C2, G²) / B²} 20² + (t + 1) max (0, G' c
o
C2 + max 0, (t l) C2)
8p a min (C2 G²3 2 (1 + max (G' GG' C2.0)
1+ max (t- G'-CC)) (t (t-1)
C2
(23)
B²
where (a) expand
A to Ao. (6), (c) substitute the bound of a in ( (d) relaxes
m C22
C2+ max (0.0' C2] Vn tt; sums over and bound
mmax Cc
O2t max (0,0' C2]
max (0, G' C2)
1+1 t max Co) Catl max Cax(max(U, U,,
C2 + max G¹ C2]
7=0
and
t mmxx G
1-
Σ r=0
C2 + ma G' C2]
1
Bounding the second term in (0): Next, let us bound the second term (20) by directly applying
Lemma A.10 More specifically,
Da (N
Da(Nol
Σ clip (g/. Ci))INNG(
Σ clip (g. ci)1(())
B
'EB*
iED
which is the difference between the sub-sampled Gaussian mechanism denoted as M(D) = 1 Eier clip Ci) + w' and M(D') Eier clip (g,,Ci) C1) + w'. The sensitivity of the B By choosing a > 8C,
subsampled Gaussian mechanism is 2C,, Lemma A. A.100and obtain
B and S 1. we directly apply
Da(M(D))MM(')) = Da Da
(a)
201,
(b) 8p
Da((1 p)1o + PNo
(24)
B
B2o
where (a) and (b) directly applies 25 in Lemma A.10
By substituting the bound of the two terms
23
24 to
we obtain:
Da(A1( D) (')
2D. (No A |0 (2') 7*) Da (No (vt v (7?
2D. (4.
max 0.. 1) 22 16p² min (CBB², G2)
16p²
C2
+
max
(2)((t-1))) 13.0] +1)
B²
B²o7
C2
Therefore, by the definition of RDP (Definition A.4) Af guarantees ea,e') RDDP where
16a
max(G'-CCa
C2
(t + 1) +
min min(C2 G7a
N2
1)
C2
Substitute the above bound to Step II, we have H' satisfies (a, Σ RDD, where
16a
( c9 Cf+
( max (T + +1) 2)
Σ
E
min (CB G/2)
NN
C.) 1).0 +
7=0
0=0
C2
20

---

Published as a conference paper at ICLR 2024
2 max m -C200
16atC]
16a m G²
1
Cg
of
ofN2
max
+ 1) C. 11.00
r=0
(a) 16atCt
32ta (C2 G
N2N2
of
where (a) bounds Σi=o (1+
2 mmax (G' -0'00.001 +1
0g
by 2t and bounds C2 by C2 C/B.
[C Cnllt
17.01 +1)
Therefore, by choosing of > (2T min m log((111)))
DiceSGD guarantees 5)DP) for T
N222
iterations. The proof of the theorem is completed.
21

---

Published as a conference paper at ICLR 2024
A.3 ADDITIONAL LEMMAS
Lemma A.7 (Proposition B. B.4. 10. tions with the same variance (aa
Gil
2011 ). The Rényi divergence between two Gaussian distribu-
V. o²)
a(a a(a-b) -b2
Da Da(
20²
Proof. By definition of Rényi divergence and Gaussian distribution, we have:
V2T0² / (exp(- - -a)2/2o²)) (x-pp-(x>))//200 1- dx a(x a)² (1 (x) b)2
Da(N(a, (1)
log
1
1
log
cxp
dx
a 1
2
202
1
(x (aa + (1 a)b))2 + a(1 a) b)2 do
log
exp
a 1
V
20²
a(1
(a b)2
(x (an (1 cr)b))
log
exp
exp
dr
a 1
20²
V
20
x
1
a(1
(a - b)
(x
(aa + (1 - a))))2
(1-a)b))²
+ log
exp
dx
1
202
V2TO2
20²
(0)
1
aa1 (a - 6)²
+ log(1)
1
20²
a(a - b)2
202
where in (a), we notice the second term is the PDF of N(aa + (1 - (2)b,02) so its integral is 1. This completes the proof for the lemma.
Lemma A.8. Given three Gaussian distributions distributions (((o we have that
and constant
3 (1 ((+ (1 (tw.://Weeee))t-///aoooeeeo o2
Proof. Directly apply Lemma A.7
we have
O a(a- 6)²
202
a (1 B) - c)2 (1+ )c - b)2)
202
(1 ( (L43)))aN(a. + (1+ 1 310.
The proof is completed.
Corollary A.9. For the Rényi divergence between N(a, o²) and N N(0 0²), ) we have
DalN(a, ) (1)(
Proof. Directly applies Lemma
A.7 for the special case = 0, the corollary is proved.
Lemma A.10 (Theorem 11 Mironov et al. (019)). P < 1 > 4C and a satisfies
1 1 In In
1 5 a < 00'ss - -nno, and a <
2
C3 + In(pa) 1/ 1/(202)
22

---

Published as a conference paper at ICLR 2024
where C3 =+ pla-1}+ then the sub-sampled Gaussian mechanism M applied function of Ez-sensitivity C with the sub-sampling rate p satisfies
C²
Da(M(D))M(()) S (O, C c2 -
σ² (25)
Therefore, it satisfies (a, RD-D where C2a
0²
A.3.1 PROOF FOR LEMMA A.6
Proof. First note that using the update rule of c' in Algorithm 2 we have
e = e'
1 E ()) - e n+ e=t1=e" B
Σ
V)( - v". SEB
TEB
Recall D and D' differs by a single sample, and let g denote this particular sample in D'. That is, D' = DU {g'). Recall B is random subset of 'D where each element is independently selected with probability p. Similarly, B' is a random subset of D', and with probability p. B' samples ç": and with probability 1- p. B' does not sample e". Then taking expectation with respect to B, B", the mean of e'+1 e follows
Egi [1 Egg
c²
1
Σ
-vt -v
B
iEB
Eg "+ = EB8
e"
+
ff (6) - vn)
B
iE
(26)
=e" =e" + Egg
Ee.
f(( - vm)
B
iEB
Eg (1 (1-p)(c"
1
Σ
(f(x'()) - v") p(c" +
Σ V - v*t)
iEB'
(EB'(EE))
Recall that Act1 = = - e"+1 Then by the quasi-convexity of Rényi divergence, we have
(a(N (1+1 [|Ho) Da(No at
(e ()
(0)
I 2D, Eg
(Va +
Σ
+1 + 1 [ v4y
B
vEBLU(E))
KEB
- -v (n)
Egg
Na(e" +
Σ
B
REB
(b)
I sup Da PNolo"+
1
Σ
vf(x'() - -V++ po) 1
Σ vf(('()) -v")
B
iEBlUSE7
SEB
No(ee'
1
-v
B
iE8'
( sup D.. (NN((11 -
(V6(((1a()4) A +
Σ
- (cpp
iEBtU(S)
1
clip
B
iEB
(1-p)NG(() - (o))
(
2 Do (No (N
-6 + 1/2 (Vf(xt:)) - clip (V)(())))) Ci))
1
23

---

Published as a conference paper at ICLR 2024
+ ((1- (a)
(c) 2 Da (1 (1-p)No((1 ((1))))))) + P.V. ((1 ((1-a)) +
2G'
B
where (a), (b) uses the quasi-convexity of Rényi divergence that D, (Eo(P(O)) E. (Q0))) ( max((D((P())(Q10)))
with 0 = (:(c) shifts the mean of Gaussian distributions by (1 - og)ee + # Eie v
v"; (d) cancels the identical terms in B; (e) bounds (Vf(xx55) - -lip (") by its sensitivity 2G'
A.4 PROOF OF LEMMA
For the first part the lemma, by definition, we have:
Var(c(X)) = E [|c(X) - B[c
[X]c(X)= - c(E[x1)1
(27)
(6)
E||X |[X]||== Var(X),
where (a) uses the fact that IE(X - B < E(X Y)2 v Y; (b) applies the fact that c()) is non-expansive mapping, so that lc(a) - cbb)ll < ||a - bl|
For the second part of the lemma, we notice that clipping operation is projection operation to convex set, so it is non-expansive (Takahashi) 1970).
clip (x, C) = -arg min 1 || - =||2,
||=||S 2
where set {a| ||>||| I C'} is convex. Therefore, c(x) x clip (z, C) is also non-expansive (Tkk hashi 1970p that
[|<(x) - c(y))l $ ||x vll. N.yy
B PROOF OF RESULTS IN SECTION 2
B.1 EXAMPLE OF CONSTANT CLIPPING BIAS
For any fixed positive clipping threshold C, let us consider the following function
-C'(x E + ) [ E)2
x S E C'
(xx,
x El S C²
C"(x - C²
x 2 5 C'
with C' [C1 + 1. The per-sample gradient of this problem is
CC,
{ C
vf(x,
x E C²
l - 5 C" x 2
"....,,,, C", and Eo C², verify that (x) satisfies Assumptions 3.1 3.5 with certain constants.
By setting the dataset size as N O + 1, and the samples are E = = -i,ii 1...,
Next, we analyze the stationary solution to this problem with and without clipping operation, i.e., the expected stationary solution of SGD and Clipped SGD. The stationary solution of SGD is On the other hand, by running clipped SGD with C' clipping threshold C, the stationary solution is ; टhम > This indicates that with small enough clipping threshold C. clipped SGD converges to a neighborhood the stationary solution of the problem, with ((1) clipping bias.
ff(x*) 0, EN (x* - { 0, xx
24

---

Published as a conference paper at ICLR 2024
95
90.62
95.55
94.76
95.11
90
23.61
48.93
47.11
53.63
40
88.79
94.7
95.3
95.23
C/C
80
C/CC
3
20.99
34.24
50.34
48.71
30
75
10
85.65
93.34
94.48
95.29
3.37
11.14
33.18
37.97
20
30
59.63
88.95
93.19
95.25
65
30
1,24
1,55
18.27
19.1
10
60
100
10
1
0.1
100
10
0.1
C
(a) Cifar-10
(b) Cifar-100
Figure 2: The testing accuracy for Cifar- 10 and Cifar- 100 trained with DiceSGD under different
C1, C2 with fixed effective stepsize.
C ADDITIONAL EXPERIMENTS
C.I ABLATION STUDY
In this section, we provide the ablation study on the choices of the clipping threshold C1, C2 and the learning rate 7). The experiments conducted the Cifar-10 and Cifar-100 datasets, with fixed (2, 10 DDDP. We fine-tune the ViT-small model for 2 epochs with batch size B = 1000, i.e., 200000 1000
100.
In the experiment, we first use a se-parameterizatioo method in De et al. 2022) to fix the product of the step size and the clipping threshold C1. By doing this, we normalize the update v + w ny the clipping threshold C₁ and fix the "effective stepsize" of the algorithm, i.e.,
x x -'-nn'C
C
where v and w scales with Cj. We study the impact of different combinations of C1 and C2- We choose Ci {100, 1, 1.1.) and C2 = {1,3, 1,,0,,330 30) C1, and the results are shown in Figure From the figure, we see that choosing C2 C1 gives the best performance in most cases. Additionally, choosing larger C gives a worse result, and DiceSGD benefits from using small clipping threshold.
Next, we fix C2 = C1 and study the impact of different combinations between the clipping threshold C1 and stepsize 77. We choose C1 {100, 10, 0.1} and n f3.0. 1.0, 0.3, 0.1, 0.03, 0.01) (..1)//C, The result is shown in 3 From the figure, we see that DiceSGD benefits from using a small clipping threshold, and exists best 7) C1 that gives the best performance.
C.2 TRAINING GPT-2
We train GPT-2 model with the E2E dataset. which contains template-lik information in the restaurant domain to be mapped to natural language with end-to-ent training that has 42000 training samples. The GPT model is fine-tuned for 10 epochs, with batch size B = 1000, T 42000x10 420. We use the similar AdamW variant of DPSGD and DiceSGD for training and set initial stepsize n = 2 10-3 with learning rate warm-up and linear decay. The algorithm is guaranteed (8, x 10-61-10000 -DP. We report the testing loss for each epoch in Figure
Ablation study for GPT-2 In this section, we provide the ablation study on the choices of the clipping threshold C₁ and the learning rate 7 with GPT-2. We fine-tune the GPT-2 model for 5 epochs with batch size B = 1000, i.e., 7 5x42000
1000 210. We use the Adam W variant of DiceSGD for training with learning rate warm-up and linear decay. The algorithm is guaranteed (8, 10 -D- We fix C2 C₁ and study the impact of different combinations between the clipping threshold Ci
25

---

Published as a conference paper at ICLR 2024
100
70
Toslinng Accuracy (%)
60
80
Testing Accoracy (%)
50
11
0.1
60
G 100
40
G 0.1
0.01
0.03
0.1
0.3
1.0
0.03
0.1
0.3
1.0
3.0
x Ci
1)
C1
(a) Cifar- 10
(b) Cifar- 100
Figure 3: The testing accuracy for Cifar-10 10 and Cifar- trained with DiceSGD under different C 7 with fixed C2- = C₁.
1.34
Dic DPSGD-GC
1.32
1.3
Test Loss
1.28
1.26
1.24
1.22
2
4
8
10
Epochs
Figure 4: Testing loss of DPSGD and DiceSGD fine-tuning GPT-2 on E2E dataset, with clipping
thresholds C = C₁ = C2 1 and guarantees (8, 8 x 10-
and stepsize We choose C = {100, 10, 1, 0.13 and
1,,5, (10-2,10 10-33. We report the testing loss for each combination the initial stepsize 17 and clipping threshold C in Figure [ From the result, we see that using smaller clipping threshold gives better result for DiceSGI..
C.3 ADAM VARIANT DICESGD
In this section, we provide detailed updates of the Adam variant of DiceSGD in Algorithm
Algorithm Adam variant DiceSGD Algorithm
Input: x", D, Ci, C2, 17, B1, B2,
2: Initialize: e 0, m = 0, m =
3: for to - 0,
..,
do
4: Randomly draw minibatch B from D
5: v E clip (v((x()))) Ci) + clip (c',C2) + ww', where w' NN(0,f I)
6: m = =Bmm + (1 )v
I/ Update first-order moment estimate // Update second-order moment estimate
7: m = =B2m + (1 82) (vt)z
x++1 =x' nf m' (11)))))))
9:
e1+1 el EieB: vx(x(()) (1 Eieg clip (V)(())))) + clip (e', C2)
10: end for
26

---

Published as a conference paper at ICLR 2024
6
100
6.17
4.98
3.16
1.54
1.41
1.41
5
10
3.48
2.44
1.26
1.25
1.28
2.56
2.44
1.64
1.26
1.25
3
2.56
2.43
1.62
1.26
1.24
1.28
0.02
0.005
0.002
0.001
0.0005
Figure 5: Testing loss (smaller the better) of DiceSGD E2E dataset with different combinations of clipping thresholds and initial stepsizes.
C.4 EFFICIENCY ANALYSIS
Hyperparameter tuning efficiency In our ablation study. we observe two patterns achieve good
accuracy: (1) C2 needs to be close to C1. (2) Cj needs to be small. Therefore we can write C1
C2 C and derive an automatic version of DiceSGD: in vf B Eieg. clip (V (x': C)
clip (e', C*) where clip (r, C)
C known as the automatic clipping in Bu et al. 2024)) Setting
the injected noise 0 absorbs C:
327 327-3C (18)1/8)
96T log(1/8]C satisfies DP. Let the learning rate r/
Nº
Algorithm 4 Automatic DiceSGD Algorithm (without C2 C2)
1: Input: x", ",
2: Initialize: e =
3: for = -0...,,'- do
4: Randomly draw minibatch 1 from D
5: v² = 1
B EiEBi clip (Vf(x
clip (e', 1) /96T (16) Ne 10,
6:
x x+11 = x'' -1/((v= + w'), where w ~
7: e = + EieB Ex( v'
8: end for
Computational efficiency In this part, let us briefly discuss the complexity of DiceSGD.
Memory: DiceSGD requires 3 times the memory of DPSGD-GC (which has similar time/space efficiency to the standard SGD), i.c., besides the summed clipped per-sample gradient, DiceSGD requires extra memory for both summed unclipped gradient and the feedback signal e¹. Computation: The computation overhead of DiceSGD is minor compared with the cost of the per-sample clipped gradient computation. Specifically, the total computation of DiceSGD consists B Exper-sample (clipped) gradient computation +2(B 1) x gradient summation + SGD update +e' update, where DiceSGD requires extra (B-1 B-1)x gradient summation and one e update compared with DPSGD-GC. Additionally, in the distributed learning regime that necessary train large models, we expect that the gap in computational efficiency is insignificant, given that the communication cost acts as dead computation cost + communication cosl
weight (e.g. non- computation communication
~ 1.0 if communication cost >> computation cost).
27


Reviews:
[{"review_id": "Sv105l16oI", "reviewer": "Reviewer_abPz", "summary": "The paper proposes a differentially private optimization algorithm with error feedback as a means to combat the clipping bias. The resulting algorithm is shown to converge without a bias at all values of the clip norm (whereas DP-SGD analyses show convergence at particular clip norm values). Experiments show that the proposed approach outperforms DP-SGD. The theoretical analysis requires a strong assumption that amounts to requiring that all per-example gradients are almost surely bounded.", "questions": "I've given several questions in the \"weaknesses\" section. Some more questions:\n- p. 18, Step III: In the definition of $\\Delta^t_g$, are the $g_i^t$ under both $D$ and $D'$ assumed to be the same? If the differing example was sampled in iteration $k < t$, then the iterates $\\mathbf{x^t}, \\mathbf{x'^t}$ are both distinct. Then, their corresponding gradients in iteration $t$ are also distinct. \n\nOverall, I think this idea is great. If the authors can develop the theory further, run comprehensive experiments, and improve the clarity, I think this paper can be really impactful.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The result is quite significant. Clipping is a known problem in the literature both in theory (where existing analyses are inadequate) and in practice (where the clip norm needs to be tuned carefully). This paper addresses this important problem.\n- The main paper is reasonably well-written and clear to understand. The fixed point analysis used to motivate the method does a great job of explaining the key ideas. The proofs could use some rewriting to improve clarity (details below).\n- The optimization proofs look right to me, although I have not verified them line-by-line. I was unable to parse the privacy proofs which could use some rewriting.\n- I would rate the originality as moderate since the paper is the application of a well-known technique from optimization (and signal processing before that) to DP optimization. This application introduces some technical challenges in the proof which the paper handles well.", "weaknesses": "**Theory**:\n- _Discussion of assumptions_: The assumption that $\\|\\nabla f(x) - g_i\\|_2 \\le \\sigma$ everywhere is rather strong. It needs to be better and more transparently justified. Its ramifications need to be discussed more carefully. For instance, under such an assumption, it is not inconceivable that DPSGD with [adaptive clipping](https://arxiv.org/abs/1905.03871) also converges favorably (see e.g. [Varshney et al.](https://arxiv.org/abs/2207.04686) who used this trick for linear regression). A comparison to this approach both theoretically and empirically is missing.\n- _Convergence rates_: I believe that $\\eta = O(T^{-(1-\\nu)})$ is a suboptimal choice and the right rate should be something like $\\exp(-c\\sqrt{t}) + \\log t /t$. See e.g. [Section 3 of Stich](https://arxiv.org/pdf/1907.04232.pdf) for notes on tuning the step size carefully to get the best rates.\n- _Setting of parameters: How does the convergence rate vary with $C_1$ and $C_2$? What are their optimal values? How much does the rate suffer when these constants differ from their optimal values?\n- _Potentially incorrect statements_: Page 8 says \"the result does not rely on the specific values of [$\\sigma$ and $G$]\". I do not think this is true: $\\sigma_1$ depends on $\\tilde G$, which depends on $G'$ which depends on $G$ and $\\sigma$.\n- _Effect of the clip norm on the learning rate_: Suppose the clip norm is so small that all gradients are effectively clipped. Then, reducing the clip norm any further has the role of reducing the learning rate. Do the bounds capture this dependence? More generally, how does the clip norm determine the optimal learning rate?\n\n**Inadequate experiments**:\n- The experimental results are promising but many more experiments are needed to paint a convincing picture. It is fine to run some detailed experiments on smaller-scale settings that can be tested more extensively (I would argue that these have more value for this particular paper than inadequate experiments on larger models but the authors can feel free to disagree). \n- Standard deviations across multiple repetitions need to be reported as the algorithms are noisy\n- How is the clip norm of DPSGD tuned? That is, is the optimal choice one of $C \\in \\{0.1, 1\\}$. If the claim is that DiceSGD converges regardless of the clip norm, one needs to show the results for a broad range of clip norms (including the best possible for DPSGD) ranging over several orders of magnitude.\n- How do these results translate to different values of $\\epsilon$?\n\n**Clarity (main paper)**:\n- The distinction between \"DPSGD\" (without clipping) and \"DPSGD-GC\" (with clipping) is confusing. DPSGD is always presented in the literature with clipping and theoretical analyses use Lipschitz functions (=> bounded gradients) to avoid the technicalities induced by clipping. It would be much more natural to refer to both as DPSGD and make a distinction in the setting (i.e., whether the clipping is active or not).\n- Section 2.1: why even mention $(\\epsilon, \\delta)$-DP? It would be much cleaner to describe the background in terms of RDP and the proofs use this as well.\n- $\\mathbb{E}_i$ and $\\mathbf{g}_i$ are not defined but are used in various places (.e.g Assumption 3.5). This is also poor notation because it implicitly hides the dependence on $\\mathbf{x}$.\n\n**Clarity (proofs)**:\n- The definitions of key quantities such as $\\Delta^t$ and $\\alpha^t_e$ should be featured more prominently. Right now, they are hidden somewhere amid the proof and are hard to find. E.g. bottom of p.18, $\\alpha^t_e$ is used but it is defined in the proof of Theorem 3.7.\n- Lemma A.6: $\\mathcal{A}_1^t, \\mathcal{A}_2^t, \\mathcal{H}^t$: I do not understand this notation. Some examples will be helpful.\n- p.18, Step II: This proof is very hard to parse and the quantities do not make sense to me. Please consider standardizing notation across various proofs for the reader's convenience and simplifying the notation in this proof in particular.\n\n**Missing refs**:\n- Using normalized gradients instead of clipping: https://arxiv.org/pdf/2106.07094.pdf\n- Section 2.3: there is some literature on joint DP + compression e.g. https://arxiv.org/abs/2111.00092\n\n**Minor**:\n- Why is $\\tilde g_i^t$ not boldfaced in Algorithm 1?\n- There is $\\mathbb{E}$ missing in the \"e\" terms in the first display equation of page 6.\n- Assumption 3.1: typo $\\mathbb{R} -> \\mathbb{R}^d$. Btw, Assumption 3.1 always holds under strong convexity (which is assumed), so it does not have to be explicitly specified\n- Assumption 3.2: reads like a definition more than an assumption\n- Theorem 3.7: $\\frac{1}{2\\mu} \\ge \\frac{3}{32 L}$ always, so that condition on $\\eta$ can be dropped.\n- Theorem 3.7: $\\kappa$ is typically used to refer to the condition number and can be quite misleading here. Besides, there is no need to define a new variable if it is used only once.\n- $\\nu$ and $\\tilde G$ are not defined in Table 1\n- Theorem 3.8: $\\sigma_1$ is not a noise multiplier, it is the noise standard deviation. See [here](https://arxiv.org/pdf/2303.00654.pdf) for details on the terminology.\n- Formating math: proper-sized brackets (using \\left, \\right), etc.\n- Some references need to be updated (citing arxiv versions instead of the published ones, etc.)\n- Typo on p.18, step 1: $\\sigma -> \\sigma_1$\n-Typos in Lemma A.11: do you need $\\sigma > 4$ and $\\epsilon = 2p^2 \\alpha / \\sigma^2$.", "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": "", "extra_scores": {}}, {"review_id": "ggg265l3RF", "reviewer": "Reviewer_uaba", "summary": "The paper to add a state accumulating the error caused by clipping in DP-SGD and adding it back later, which is called DiceSGD. It is designed to reduce the clipping bias of DP-SGD", "questions": "Is it possible to get a rigorous bias-variance trade-off to confirm that DiceSGD is better than DP-SGD?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This is an interesting attempt at analyzing and mitigating the clipping bias in DP-SGD.\n2. The convergence analysis and privacy analysis are non-trivial.", "weaknesses": "1. My major concern is that although clipping bias can cause privacy degradation in DP-SGD, the major drop is still caused by the added noise. Thus I am not sure how useful it is to trade noise variance for clipping bias. The empirical study partially answers the question but might not be generalizable.\n2. I think DiceSGD should be compared with DP-FTRL and matric mechanism as well since they are all stateful algorithms. In terms of implementation, DP-SGD is more efficient than all of them since it is stateless.", "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": "", "extra_scores": {}}, {"review_id": "wg7r4S4GaJ", "reviewer": "Reviewer_w9rc", "summary": "This paper proposes a new variant of DP-SGD algorithm that eliminates the clipping bias during training. The key idea is to borrow the error-feedback mechanism for compressed SGD. Theoretically, under some common assumptions, this paper provides novel convergence analysis and privacy analysis. Finally, the effectiveness of the proposed algorithm is demonstrated on empirical experiments.", "questions": "Please see weaknesses", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written.\n2. The proposed algorithm is relatively simple and scalable. The algorithm itself does not require fine-tuning the clipping threshold.\n3. Proofs of utility and privacy both require non-trivial effort and novel technique.", "weaknesses": "Compared to DP-SGD with a properly chosen clipping threshold, the error rate is larger, and the convergence is slower. This is due to the larger noise needs to be added. I was wondering if there is any practical implication in the experiments.", "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": "", "extra_scores": {}}, {"review_id": "hgvOp2T1sS", "reviewer": "Reviewer_KeFV", "summary": "A novel algorithm for stochastic differentially private model training is proposed that eliminates the bias caused by clipping. The essential idea is to maintain the clipped component in a separate accumulator that is also added (with its own clipping) to the update at each iteration. A convergence proof is provided (for strongly convex loss) showing that the algorithm does not suffer from the O(1) term caused by clipping in typical DP-SGD. Experimental results show that the method closes the gap to non-private SGD on several tasks.", "questions": "* It is stated that DiceSGD requires a constant multiplicative factor more noise than DPSGD. What is that factor?\n* Given that DiceSGD maintains a private state anyway, and the convergence analysis assumes strong convexity, could the privacy guarantee be strengthened by NOT releasing the model after every step, similar to Feldman et al. \"Privacy Amplification by Iteration\" (which is cited)? The analysis you already have -- for non-convex objectives and releasing all iterates -- seems to me primarily useful because it bounds the privacy loss for non-convex objectives *without* releasing all iterates. I can't imagine a scenario where you can protect the private state but nevertheless want to release all model iterates. On the other hand, if it were possible, an analysis of the convex case where all model iterates are private could give you a tighter bound.\n* In the NLP experiment, it is stated that GPT-2 is fine-tuned. By default I would assume that means all-parameter fine-tuning, but Hu et al. (2021) is cited twice (referencing the metrics and in the table) which makes me wonder if it is Lora fine tuning. Which is it?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm is novel and, while not terribly surprising in hindsight (like many good ideas) is a useful contribution. More original is the DP analysis, which is complicated due to the non-privatized hidden clipping-error-accumulator state. The experimental results (on non-convex objectives) are encouraging, and it is in particular very exciting that the dependence on the clipping threshold appears to be weak. If future results continue to show such a pattern, that would be particularly advantagous, as DP-SGD can be quite sensitive to the clipping threshold.", "weaknesses": "It is unfortunate that the convergence result depends on strong convexity. This limits the usefulness of the result. Fortunately the DP guarantee does not require the strong convexity assumption, and the experimental results use non-convex models.\n\nThe experiments don't seem to be very careful about how $C$ is chosen. For example, in Table 3, it is just stated that C=1. Considering the whole point of the paper is a better method for clipping, I would like to see more exploration into this. In Table 2, we just look at two points C=1.0 and C=0.1 for each dataset. But there could be an interesting curve there because there is a tradeoff between clipping error (which is hopefully alleviated by DiceSGD) and the amount of noise you have to add for DP.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)