Improving Differentially Private SGD via Randomly Sparsified Gradients
Authors: Junyi Zhu
Matthew B. Blaschko
Venue: Accepted by TMLR ()

Abstract: Differentially private stochastic gradient descent (DP-SGD) has been widely adopted in deep learning to provide rigorously defined privacy, which requires gradient clipping to bound the maximum norm of individual gradients and additive isotropic Gaussian noise. With analysis of the convergence rate of DP-SGD in a non-convex setting, we identify that randomly sparsifying gradients before clipping and noisification adjusts a trade-off between internal components of the convergence bound and leads to a smaller upper bound when the noise is dominant. Additionally, our theoretical analysis and empirical evaluations show that the trade-off is not trivial but possibly a unique property of DP-SGD, as either canceling noisification or gradient clipping eliminates the trade-off in the bound. This observation is indicative, as it implies DP-SGD has special inherent room for (even simply random) gradient compression. To verify the observation an utilize it, we propose an efficient and lightweight extension using random sparsification (RS) to strengthen DP-SGD.  Experiments with various DP-SGD frameworks show that RS can improve performance. Additionally, the produced sparse gradients of RS exhibit advantages in reducing communication cost and strengthening privacy against reconstruction attacks, which are also key problems in private machine learning. 

Published in Transactions on Machine Learning Research (06/2023)
Improving Differentially Private SGD via Randomly Sparsi- fied Gradients
Junyi Zhu
jungi.zhu@@estt.uuueeeee www.uuwen.....uuuun....
Center for Processing Speech and Images, Deportment of Electrical Engineering ( (ESAT) KU Leuven, Belgium
Matthew B. Blaschko
Center for Processing Speech and Images, Deportment of Electrical Engineering (ESAT) KU Lewven, Belgium
Reviewed on OpenReview: https: // openreview. net/ forum? id=sY35BA:If4
Abstract
Differentially private stochastic gradient descent (DP-SGD) has been widely adopted in deep learning to provide rigorously defined privacy, which requires gradient clipping to bound the maximum norm of individual gradients and additive isotropic Gaussian noise. With analysis of the convergence rate of DP-SGD in a non-convex setting, we identify that randomly sparsifying gradients before clipping and noisification adjusts tradc-off between internal components of the convergence bound and leads to smaller upper bound when the noise is dominant. Additionally, our theoretical analysis and empirical evaluations show that the trade-off not trivial but possibly a unique property of DP-SGD, as either canceling noisification or gradient clipping eliminates the trade-off in the bound. This observation is indicative, it implies DP-SGD has special inherent room for (even simply random) gradient compression. To verify the observation an utilize it, propose efficient and weight extension using random sparsification (RS) to strengthen DP-SGD. Experiments with various DP-SGD frameworks show that RS can improve performance. Additionally, the produced sparse gradients of RS exhibit advantages reducing commuication cost and strengthening privacy against reconstruction attacks, which are also key problems private machine learning.
1 Introduction
Internet-scale data promises to accelerate the development of data-driven statistical approaches, but the nced for privacy constrains the amalgamation of such datascts. As a result, private data are in fact isolated, constraining our ability to build models that learn from a large number of instances. On the other hand, the information contained in locally stored data also be exposed through releasing the model trained local dataset (Fredrikson et al., 2015; Shokri et al., 2017), or even reconstructed when gradients generated during training are shared (Zhu et al., 2019; Zhu & Blaschko, 2021; Zhu et al., 2023).
To address these issues, many applications of machine learning are expected to grivacy-preserve while differential privacy (DP) provides rigorously defined and measurable privacy guarantce. As described Definition 1, DP defines privacy with respect to the difficulty of distinguishing the outputs of different data:
Definition ((E, DP (Dwork & Roth, 2014)). For a pair of neighboring datasets X, X' X. X is obtained from X' by adding removing clement. A randomized mechanism M X + R is (c, diffeddifcceentially private, if for any subset of outputs S C R it holds that:
Pr[M(X)
Pr(M(X') E E +5
(1)

---

Published in Transactions on Machine Learning Research (06/2023)
A
Noise contour
81
1.0
3.0
Epoch
Billl I/ [lgglll
EI 11E 111
0.8
40
80
0.6
2.0
Clipping bound
0.1
0.0
0.0
0.2
0.4
0.6
82 82
W2
W2
Sparsification rater
Sparsification rater
(a) DP-SGD
(b) DP-SGD with RS
noise norm ratio
(d) gradient norm ratio
Figure (a) Schematic of DP-SGD. We denote g as the gradient vector and omit the notation for imput data, I1 and 92 are two entries in 9 corresponding to the coordinates wi and w2, 9 is the clipped gradient vector. (b) Schematic of DP-SGD with RS, 91 and Ø2 are two possible results under RS. (c) Empirical ratio of noise norm with RS || and without RS || i.e. I/ we take d = 5.5 x 10 which is the dimension of DP-CNN. (d) Empirical ratio of the gradient norm of relaxed coordinates with RS ( and without RS [ل i.. I /to.ss///l/// /l measured on DP-CNN with dataset CIFAR10. We remark that for is representative, as in high-dimensional space [gl >> max([1g:1]1 while the two strengths still exist for C being smaller.
(a) and (b) clipping bound C within range (max(1
(1 [9: Dr ( I)
A common paradigm for applying DP in deep learning differentially private stochastic gradient descent (DP-SGD) proposed by Abadi al. (2016b), which lets the randomized mechanism M output perturbed gradients:
f(x) : Eg(x), ZEX M(X): f(x) + N(0,, S3o² Ia),
(2)
(3)
where X now stands for a batch of data and g(x) - RRd computes gradient given an individual example in the batch. The isotropic Gaussian distributed noise (0, Sf0²1) is calibrated to f's sensitivity St := m
f(X))l while the noise multiplier controls the strength of the privacy guarantce. As S is usually unknown, DP-SGD commonly clips the gradient of each individual example in Euclidean norm to preset bound C, such that f(X)= == Σxex g(x) min(1, C/Ilg(x)]) Then Sy can be safely replaced by C and the randomized mechanism M can thus be expressed as:
M(X)= f(x) + NNO,
(4)
However, gradient clipping gives rise to a squeezed gradient distribution, while noisification further blurs the gradient distribution, both cause adverse effects for optimization. Understanding the influence of these two operations bocomes crucial for the progress of DP-SGD.
1.1 Our contribution
In this work we present special property of DP-SGD that is established jointly by gradient clipping and noisification. In particular, we analyze DP-SGD in non-convex and smooth setting and identify that randomly sparsifying gradients before clipping and noisification can trigger trade-off between internal components of the convergence bound and possibly result in a smaller upper bound. This observation suggests that in the context of DP-SGD randomly sparsified gradients could lead to faster convergence than the full gradient. This also implies that DP-SGD has inherent room for (even simply random) gradient compression. We further note that the same property not present in other popular SGD schemes.
First, we describe the process of random sparsification (RS) and illustrate its impact on DP-SGD. RS uniformly selects random subset S from the full coordinates set D and zeros their gradients, we define
2

---

Published in Transactions on Machine Learning Research (06/2023)
sparsification rate == [S|/|D] as the percentage of coordinates we would like to sparsify. Figure 1a, 1b schematically illustrate the vanilla DP-SGD and DP-SGD with RS using 2D example. In this 2D example RS can either have 91 or 92 zeroed-out so r can only be set to 0.5. In digheerdimennsoonll cases it will be possible to set r to other values within the range (0, 1). Compared with vanilla DP-SGD, the drawback of RS is indeed apparent as RS removes some gradient information. However, on the other side RS has two strengths: (i) due to the isotropic Gaussian noise Es. the amount of noise in term of Euclidean norm scales with the gradient dimension d [P] With RS the effective d is reduced not receive any gradient information, and noisification in those dimensions is no longer necessary. Figure 1c demonstrates the empirical ratio of the noise norm with RS over without RS ||& || I (ii) Due to gradient clipping, for the coordinates D \ S that are relaxed, i.e. corresponding gradients are not zeroed out, their gradients have a higher magnitude than without RS (see Ø > | or T22l > lñzl), implying the relaxed coordinates are better optimized, Figure 1d demonstrates an empirical ratio of the gradient norm of relaxed coordinates with RS over without RS of the drawback and strengthens of DP-SGD with RS for non-convex and smooth problems and as we will see RS gives rise to trade-off between internal components of the convergence bound of DP-SP OP-SGD. Another interesting observation we will present is that for other popular SGD schemes, i.e. SGD with gradient clipping (same as canceling noisification in DP-SGD), noisy SGD (same as canceling clipping in DP-SGD), and vanilla SGD, the respective convergence bounds are only enlarged by applying RS. This observation highlights the fact that the reason for RS improving DP-SGD is not trivially due to the reduced noise, and suggests that the trade-ofJ ruised by RS in the context of DP-SGD is special, which manifests under two preconditions: gradient clipping and noisification.
the sparsified coordinates do
In Section 3, we will discuss the integrated impact
An alternative to random sparsification would be c.g. to sparsify the smallest entries of the gradient, W2 in Figure 1. It is worth emphasizing that the selection of significant coordinates is also privacy related. It could be done by using a public dataset (Zhou et al., 2021; Kairouz et al., 2021) which we do not assume exists, or by providing additional privacy budget for sparse vector techniques (Dwork & Roth, 2014) or DP selection (Zhang et al., 2021), which have certain technical difficulties of defining the threshold and privacy loss for the selection, and are thus only applied when the gradient is obviously sparse, e-g. the embedding layer of language model. Perhaps most importantly, the analysis of these methods assumes the original sparsity of the gradients (c.g. g lies in wi in Figure 1) or low-rank property (c.g. g always lies in subspace). In contrast, our analysis, and the strengths of RS as illustrated in Figure 1, do not rely on these assumptions, which makes the contribution of this work complementary to previous works.
Paper organization: In Section 2, we discuss related work. In Section 3, we elaborate on the impact of RS on popular SGD) schemes and finally present the special trade-off of DP-SGD induced by RS. In Section 4, we provide an efficient and lightweight RS algorithm based on our analysis. In Section 5, we discuss the additional advantages of sparsified gradients. In Section we empirically verify our analysis and show the utility of our proposed algorithm. All proofs are deferred to the Appendix.
2 Related works
Chen et al. (2020) analyze the convergence rate of DP-SGD in a non-convex setting with characterization of the adverse effect of the gradient clipping. Many works study adaptive clipping bounds (Andrew et al., 2021; Pichapati et al., 2019). Other works study the adverse effect of noisification and prove that the performance of DP-SGD dependent on the gradient dimension d as, according to Equation (4), the amount of noise scales with d. Bassily et al. (2014) show that in convex sctting, DP-SGD achieves excess risk of Ó(v ((V//ne), where n is the dataset size. Wang & Xu (2019) show that the empirical gradient norm decreases to Ö( /ne) for DP-SGD with smooth non-convex loss function.
A line of work builds on gradient space compression to improve the utility of DP-SGD. Abadi et al. (2016b) propose DP linear probing to pre-train a network on an auxiliary dataset, then transfer the feature extractor and only re-train the linear classifier on the private data. Similarly, Tramer & Boneh (2021) adopt ScatterNet (Oyallon et al., 2019) to extract handerafted features. Both works docrease d by excluding the majority of parameters during DP learning. Inspired by the empirical observation that the optimization trajectory is contained in lower-dimensional subspace (Vogels et al., 2019; Gooneratne et al., 2020; Li et al., 2020),
3

---

Published in Transactions on Machine Learning Research (06/2023)
several recent works (Zhou et al., 2021; Yu et al., 2021a; Kairouz et al., 2021; Yu et al., 2021b) project the gradient into a subspace which is identified by auxiliary data or released historical gradients. Zhang et al. (2021) target NLP tasks where gradients are extremely sparse, and propose a DP selection method.
In contrast to the strategy of reducing gradient space dimension, Papernot et al. (2021) propose a dedicated DP-CNN with tempered activation function which is deemed as robust to the adverse effects of gradient clipping and noisification in DP-SGD. Li et al. (2022) observe that DP-SGD works well on full fine-tuning of large language models. Furthermore, Yu et al. (2022) propose incorporating parameter-cffiiient fine-tuming (PEFT) techniques, such as low-rank adaptation (Hu et al., 2022) and adapter- based fine-tur fine-tuning (Houlsby et al., 2019). Bu et al. (2022) propose private bias-term only fine-tuning. Both approaches improve the performance of DP fine-tuning and largely reduce the computational cost with large models, as well as the communication overhead in distributed settings. However, PEFT methods require a pre-trained model as a backbone and cannot be applied in scenarios where the network must be trained from scratch.
The studies of Damaskinos et al. (2021) and Mangold et al. (2022) on DP coordinate descent compute the gradient of random coordinate in backpropagation and in this aspect similar to RS. However, there is notable difference between these existing works and our work. Damaskinos et al. (2021) study the generalized linear model which includes a convex problem and investigate the dual formulation. Mangold et al. (2022) also analyze convex optimization problem and rely on precise coordinate-wise regularity measures of the objective function such that each coordinate can be noisified accordingly. Both works derive a modified update step (beside sparsification). In this work, we study DP-SGD with RS in a non-couvex setting. We do not assume detailed characterization of the optimization landscape, e.g. coordinate smoothness. And RS is applied directly on the gradient computed with the loss function of the network's prediction. Our analysis is thereby more general.
3 Applying random sparsification to gradient descent methods
Notation & Terminology Let L be the objective function L(w) = Enex( x) which is G-Lipschitz smooth, and x denotes a training example sampled from the dataset X. We define It.i == Ve(wy mx) the gradient at step t with example x; and define the true gradient Vw; := 19,1) We assumee the gradient deviation Gt,i - Vw, is sampled from a zero-mean random variable & The averaged gradient of B samples at the step is denoted as 9t := Ee It.s and the averaged clipped gradient as 9. == B Es gt, mmin(1, Clll.,..l). To conduct RS, we use random mask m E 1) and uniformly draw rd indices and set these positions in the mask to 0 while others to 1 that ||m]]i (1 - r)d, r is the predefined sparsification rate. The average of sparsified and clipped gradients can thus be expressed as 9: := B E, min(1, C/Ils(,,ll) where we define g'., := m O It.i, the Hadamard product is denoted using @. For noisification, isotropic Gaussian noise is denoted as Eo, when RS is applied we do m &.. As this work involves multiple ways of processing gradients, we summarize their notation in Table for convenience. We do not bold vectors or matrices in the analysis since it is clear from the context. As RS modifies DP-SGD, we clarify that RS does not breach privacy with the following theorem:
Thcorem 3.1. For a Gaussian mechanism: M(x) = Ex g(z) . min(1, (/I(L,CC/l((=)1) +N C²o2 which satisfies (c, (),P),DP, after applying RS with a mask m E f0, 1]d, the modified Gaussian mechanism M2)x): = EBEx m ② g(x)- min(1, C/Ilmm O g(x)))) + m NO, C2 C2 also satisfies (c, (DP.
Proof. Note that M' is equivalent to (²) == = Exex (D)s(x) min(1, min(11C//l99 terms of privacy, then it casy to observe that M² and M(x) provide the same level of DP. It should be noted that the scenario of 0 is not considered in our analysis as it does not align with the objectives of optimization.
s/ + (O C2 sisss) (
3.1 Applying random sparsification to vanilla SGD and noisy SGD
We first note that for vanilla SGD (Bottou et al., 2018), applying RS the same as randomly dropping gradi- ent information, thus RS cannot provide any benefits. Next, we consider the impact of RS under noisification and gradient clipping separately. If we cancel the gradient clipping in DP-SGD, the resulting optimization
4

---

Published in Transactions on Machine Learning Research (06/2023)
Gradient
ge.i
Gradient step with example wi, L... Vi(we,
Vw
True gradient at step 6, i.e. Bsex [9t.:]
Mini-batch gradient at step i, L.e. Σ, 91,
9t.
gt
Clipped mini-batch gradient at step t, i.e. E2 9t. min(1,
ge,s
Sparsified gradient due to random mask m, Le.
ge,s-
Vw'
Sparsified true gradient due to random mask m, iee. m @ Exexlocal
Or
Sparsified and clipped mini-batch gradient at step t, 1/2 Eis min(1, C/Ilo/all).
Gradient deivation
Assumed random variable generating gradient deviations, i.c. gt. Vws. Assumed random variable generating sparsified gradient deviations, i.e. g/, Vul- True probability distribution of &t-
Pt
A symmetric proxy of pt which approximates while satisfies (Ex) = (-
pl
True probability distribution of ç.
P.
A symmetric proxy of pl which is projected from pr by random mask
Table Notations for gradients.
method noisy SGD which has been used in Bayesian learning, e.g. stochastic gradient Langevin dynamics (Welling & Teh, 2011). When RS is applied (pseudo code is given in Appendix F),, the amount of noise will be reduced as illustrated in Figure 1, however such benefit seems insufficient to compensate the loss of gradient information, which we show in Theorem 3.2.
Theorem 3.2. Consider noisy SGD with RS on G-smooth function L with isotropic Gaussion noise & NO, o² La), learning rate 7 GVT' batch size B and sparsification rate r, assume upper bound of individual gradient deviation || < gr we have:
2G
do
Vw, 12
A
(5)
T
(1 (1-r)VT
VT B B
where we define Ag = E[[(w])) min., L(w). We note that the noise term do² /0² on the r.h.s. was reduced by a factor of - r due to the RS, but this factor is canceled out by the same factor from the Lhs. (see Appendix A). Additionally, Equation (5) can also be used to describe the case of vanilla SGD with RS by removing the last term do² /22 at the r.h.s. Overall, we have the following observation:
Remark 1. Theorem 3.2 suggests that in applying RS to noisy SGD vanilla SGD, the network may converge more slowly, as [|W,, has larger upper bound for 0 <r<l.
3.2 Applying random sparsification to SGD with gradient clipping
If we cancel the noisification in DP-SGD, then the optimization method becomes SGD with gradient clipping, which has been widely adopted for large network training to prevent exploding gradients or stabilize opti- mization (Zhang et al., 2020; Pascanu et al., 2013). If RS is applied (pscudo code is given in Appendix E), relaxed coordinators can be better optimized as illustrated in Figure 1, however such benefit also seems insufficient to compensate the loss gradient information.
First consider the convergence of gradient clipping without sparsification.
Lemma 3.1. Consider SGD on G-smooth function C with gradient clipping of bound C, learning rate y, we have:
1 E[. L+t1l + +7 +7
GC2
(V 3.)I <
(6)
As the distribution of the gradient is unknown, the expectation involving gradient clipping, i.c. V g.).. impedes the estimation of the convergence rate. Let pt be the true distribution of the gradient deviation &
5

---

Published in Transactions on Machine Learning Research (06/2023)
Chen et al. (2020) firstly observe that Pt appears to be symmetric and use this property to relate B[(Vw,, to w/ Lemma 3.2 (Chen et al. (2020)). Assume (Et) = pi(-Et). Ag, E R3, gradient clipping with bound C has the following property:
E(V B.Yl 2 PeINp. < 3CC44
(7)
where k()w) == min([ C//l
We see the r.h.s. of Equation (7) is proportional to || or V| as long as (llell < 3C/4) is not close to zero. Combining Lemma 3.1 with Lemma 3.2, it is possible to form upper bound for finding the critical point. However, the real gradient distribution cannot be exactly symmelrie. Instead of using Pt in Equation (7), we can choose a proxy á which is symmetric and use an error term b, to represent the difference as be == Be,~p. (VW, 9t)] EV~,,((Vu, 9:)l.
Theorem 3.3 (Chen et al. (2020)). Consider SGD on a G-smooth function with gradient clipping bound C and learning rate 7. Choose symmetrrc distribution 5(-) satisfying pe(E,) = pe(-Et), V&, E Rd, and consider T Uleralions:
T Perppe (1eael < VV/
A 7T
GC
1
T
+1
by.
(8)
T
2
T
Chen et al. (2020) argues that there exists Pe which is a close approximation of pt such that b, is small while Ps.~p. < 3C/4) bounded away from zero, as in practice pt tends to be approximately sym- metric. They also empirically demonstrate that pt becomes approximately symmetric during training. So Theorem 3.3 indicates the convergence rate of SGD with gradient clipping. To make sure this property of Pt is generally valid in our case, we have also verified that becomes approximately symmetric in our experimental environments in Section 6 (see Appendix F).
Now consider the convergence rate after applying RS, note that the sparsification happens before clipping, so the conclusion cannol be straightforwardly derived from Theorem 3.3. Since m, E. are independent:
EKVw,, 9c)] = Em [KEe-o [VW,, GchI] + Em]6..
where we define Vwy == m & Vw,, E == m @ & with corresponding true distribution 26 and proxy V which are projected from Pt and pt, i/ == E (Vw', 9.)] - Bej [(V'', de)]. Since the projection of a symmetric
distribution to a subspace symmetric, we have ((())) E)), following Lemma 3.2, we have for the first term on the r. h.s. of Equation (9):
Em [ wiw.eyVVVee [Vw(, 9.)l] 2 E...Pee- Cl < 3C/4)(VV))IVV'
(10)
Then to solve the expectation over the random mask m in the Equation (10), we provide Lemma 3.3:
Lemma 3.3. Apply RS with sparsification rate r, choose P. such that Pe.-p. (Ilxel < 3C/4) 2 vI-n. /1-r, then 3xe E (1-r,1) such that:
EmiPe (11E')l < 3C/4))(VVL) V = =x; PEPE (l&&ll 3C/4)/(Vw:)[[]ull))
(11)
Kt takes the value 1 when r = 0. Based on Lemma 3.3, we provide Theorem 3.4 to characterize the convergence of SGD with gradient clipping and RS.
Theorem 3.4. Consider SGD on G-smooth function with gradient clipping of bound C, learning rate 7, and apply RS with sparsification rate r. Choose symmetric distribution. p(.) satisfying Pe(Ee) < 3C/4) 2 VI-T, and consider T iterations, then 3x E (1 r, 1) s.t.: (-(,,,, VE, E Rd, while (1
1 T
Perpp (llEel 33/44)(VV=: Vu,ll S 1 Ac TT'
GC2
1 T
Σ
E BT).
(12)
2
Remark 2. Consider that by 8, tend to be small and negligible, compared with Theorem 3.3, Theorem 3.4 suggests that RS could impede the convergence of SGD with gradient clipping as 1/k > for r > 0.
6

---

Published in Transactions on Machine Learning Research (06/2023)
3.3 Applying random sparsification to DP-SGD
Although there is seemingly no advanlage of using RS for noisy SGD or SGD with gradient clipping, show that in case of DP-SGD, i.e. when noisification and gradient clipping are both presented, RS can induce a tradc-off between internal components of the convergence bound and possibly achieve a smaller upper bound.
Lemma 3.4. Consider DP-SGD on G-smooth function & with clipping bound C, isotropic Gaussian noise & ~ NO0 Ia), learning rule 7, batch size B, sparsificulion rule v, we have:
GC
[[(, We, (iVWw,,))l "[C,, - G4i1+ + 2 + (1 (1-r),A..
(13)
Now we provide Theorem 3.5 to characterize the convergence rate of where we have defined Ag == C'o'dG 28"
DP-SGD with RS.
Theorem 3.5. Consider DP-SGD on G-smooth function L with clipping bound C, isotropic Gaussian moise &a ~ NO0 Ia), learning rale 7, batch size B, and apply RS with sparsification rale Choose symmetric distribution p(.) satisfying Pe(Ee) (e(-,,), V&, E TRd, while Cempe(IlEA) < 3C/4) 2 v1 -r-r, and
consider T iterations, then 3x E (1 r, 1), such that:
1 T Σ Pera (I|&/l < <CC/4) S
A 7T
GC2
1 T
T A.. K
Em Uill +
(14)
2
It is worth noting that in Theorem 3.5 on the r.h.s. the noise term A, has a factor 1 1 which is induced by sparsification, but unlike under noisy SGD (see Theorem 3.2), this factor is not fully canceled out as K > l-r. Also note that with no sparsification (r = 0), we have K = 1, Theorom 3.5 has the following form:
T Σ Perpp (IE&ll 3C/4))(Vu))] <
1
A TT ( (GC2 + Ao)
+
T
bc
(15)
which recovers the convergence bound of vanilla DP-SGD (Chen et al., 2020), implyyng that our convergence bound over RS is as tight as before. Comparing Equation (15) with Theorem 3.5, we observe:
Remark 3. RS introduces two factors on the r.h.s.: 1/K, (1-r)/k. The noise term A is reduced by (1-r)/K: k while the remaining terms are enlarged by by 1/x: a trade-off established. The respective magnitude of A, and other terms determines whether is a gain or loss to apply RS. It. worthwhile to note that A, scales with o and the gradient dimension and is inversely proportional to B²,
We also present the upper bound using privacy budget variables (c,0) in Appendix C with Corollary C.1.1.
4 Implementation of random sparsification for DP-SGD
Theorem 3.5 reveals that RS induces a trade-off between the internal components of the convergence bound and has a chance to accelerate the convergence. However, the best sparsífication rate infcasible to be computed priori and possibly varying during optimization. In this section, we present a practically efficient and light RS approach. The additional cost of running RS is negligible.
Algorithm 1 outlines our approach. RS is also compatible with SGD with gradient momentum and Adam (Kingma & Ba, 2014). In case of non-zero momentum, coordinates that have been selected can still be updated as long as their velocity has not decayed to zero. To make the algorithm efficient in practice, we adopt gradual cooling (Line 3) and per-epoch randomization (Line 5), which we discuss in the sequel.
4.1 Gradual cooling
In practice we find that if we initiate the training with a constant large sparsífication rate r, the network converges slowly and performs poorly when the privacy budget has been fully consumed. According to The- orem 3.5 and Remark 3, we see sparsification is beneficial once A, is significant compared with the other
7

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm DP-SGD with Random Sparsification
Input: Initial parameters wo: Epochs E; Sparsification rate: r"; Clipping bound: C Noise multiplier
0; Momentum: μ4; Learning rate 7,
1: for e= 0 to 1 do
2: > Gradual cooling
r(e) = E-T:
Generate random mask every epoch
E {0, , s.t. ||m]]] d (1 r(c)); for = 0 to T - do
7:
> For each T; in the Poisson-sampled batch B
4
8:
ge,i Ve(w,,
9.
b Sparsify gradient
4
10:
Fe. m ④ 9t.s:
11:
Clip each individual gradient
12:
9e [8] EieB P2; min(1, C/1lg,
13:
Add sparsified noise
14:
9e = 91 + O NO, [8 Ia);
15:
b Update parameters
16:
u++ = μ vi + Ie, wi+1 = we 70++1;
terms in the convergence bound. At early training stages the network converges fast: B(G, L(+1] is large, while during training the optimization reaches a plateau: IE[C, L++1] decays. In contrast, Do always fixed and therefore its relative significance grows progressively. To fit this dynamics, we use simple gradual cooling strategy which linearly ramps up the sparsification rate from 0 to r* during training, i.e. r" E We provide more detailed discussion in Appendix G.
4.2 Per-epoch randomization
RS alternates the optimization direction. As SGD takes several steps to reach the local minimum, frequently alternating optimization direction might be harmful, which we have also observed in the experiments. Con- sidering that tuning over the number of iterations for refreshing the random mask can be expensive, in this work set the refresh to be per-epoch. Another strength of per-epoch randomization is that for epoch there are certainly (1-r)d coordinates updated, which is favorable in distributed learning communication overhead is key issue, and data are not transmitted every iteration. For per-iteration randomization, the cumulative number of updated parameters depends on the sparsification rate r and iterations between two communication rounds, resulting in higher communication overheads than per-epoch randomization.
5 Advantages of sparsified gradients
Sparse representation of the gradient generally offers additional advantages. Our analysis Section 3 demonstrates that DP-SGD provides an inherent potential for trivial random gradient compression. In the soquel, we discuss the benefits of sparsified gradients in terms of private machine learning.
Reduced communication overhead of DP federated learning A line of work studies how to incor- porate differential privacy in federated learning, which is distributed learning scheme with the interest of protecting the privacy of participants (McMahan et al., 2017; Yang et al., 2019; Shokri & Shmatikov, 2015; Liu et al., 2020). While a major issue in federated learning is the communication bottleneck, sparse repre- sentation produced by RS can be transferred in form of non-zero values and indices. The cost of indexing is logarithmic the number of parameters. Considering that logz109 < 32 and for per-epoch randomiza- tion multiple rounds of communication could share the same indices, the cost of indexing negligible, and communication overhead by RS is reduced to Ō(1 r).
8

---

Published in Transactions on Machine Learning Research (06/2023)
Strengthened privacy against gradient reconstruction attacks A gradient reconstruction attack is one of the most hazardous privacy attacks, which assumes that the adversary has access to victim's gradient and intends to recover the victim's training data through gradient matching (Zhu et al., 2019; Geiping et al., 2020; Zhu & Blaschko, 2021; Yin et al., 2021; Zhu et al., 2023). This is a common scenario in distributed learning schemes, as participants need to share their local update when computing the global model. Zhu & Blaschko (2021) provide a closed-form solution of a gradient reconstruction attack: for certain layer one can form a constraint matrix K over the input ø given 9, so that K = 9: where 2, I are flattened vectors (Zhu & Blaschko, 2021, Equation (15)). When K is overdetermined, after receiving the gradient g, the imput can be reconstructed through least squares: x = (K K) ' To prevent such an attack, DP-SGD can be introduced so that g will be perturbed by Gaussian noise Eo. which leads to a squared reconstruction error:
| e = |[ K) K E012.
(16)
If we add more noise, the expected squared error Eiii - = will be increased, but at the cost that the network will lose performance. However, under certain noise level, applying RS can further amplify the reconstruction error (although the noise will also be sparsified).
To demonstrate this, we consider a single layer network with a one digit input I E R, a constraint vector & Id and corresponding gradient vector g E Rdd
Theorem 5.1. Conduct on attack using Equation (16) on the larget data x, consider that the gradient is perturbed by isotropic Gaussian noise Eo ~ NO0 Ia) and further sparsified with sparsification rate 10. The expected squared ervor of reconstruction is:
- - 2 (1- (|
(17)
We see the expected squared error has a lower bound which increases monotonically with the sparsification rate r. We also verify this phenomenon under a more general attacking scenario in Section 6.3.
6 Experiments
Setup: Our code is implemented in PyTorch (Paszke al., 2019b). To compute the gradients of an individual example in mini-batch we use the BackPACK package (Dangel et al., 2020). Cumulative privacy loss has been tracked with the Opacus package, which adopts Rényi differential privacy (Mironov, 2017; Balle et al., 2020). Poisson-sampled batch of data at each iteration implies privacy amplification (Balle et al., 2018; Wang et al., 2019; Mironov et al., 2019). In the implementation of many previous works (Papernot et al., 2021; Tramer & Bonch, 2021; Yu al., 2021a), sampling conducted by randomly shuffling and partitioning the dataset into batches of fixed size, we follow this convention. We focus on DP image classification and run all experiments on cluster within the same container environment times using the same group of 5 random seeds. Our code is available at https://gi htt.://.gttttt..//// thub.
6.1 Evidence of the trade-off and its uniqueness for DP-SGD
Theorem 3.5 implies that when the noise term A is dominant in the convergence bound, the trade-off induced by RS can achieve a smaller upper bound on the convergence rate. In the context of DP training, the number of iterations limited, so faster convergence means better accuracy. Since A, x o²C², we various combinations of and C' to verify our analysis. When conducting RS, we always adopt gradual cooling discussed in Section 4.1 to reach the final sparsification rate. Based on Figure 2, except the last Figure 2i, where due to excessive noise the network does not converge after few training epochs, we see: (i) from left to right, as goes up, more RS is preferred; (ii) from top to bottom, as C' increases, more can be gained from RS; (ifi) the trade-off has the same tendency for the same value of d²C². These observations verify our analysis. We note that as o²0² increases 22, i.c Figure 2f and 2h, RS can improve the performance of DP-SGD by more than 4%. Additionally, when C²0² 1, i.c. Figure 2c, 2e, 2g, The performance is maintained under RS (or slightly increased). It should be noted that
conduct experiments
9

---

Published in Transactions on Machine Learning Research (06/2023)
Train Acc. (%)
Train Acc. (%)
-58
56
Train Apc.
54
156
59
58
52
57
0.1
0.3
0.5
0.7 0.9
0.1
0.3
0.5 0.7
0.9
0.1
0.3
0.5
0.7
0.9
Final Rate!
Final Rate 1"
Final Rale 1"
20, , C= 2-
(b)
20, 2
(c) 0 2", 2-
Train Ace (%)
68
Train Acc. 196)
70
Train Acc. (99)
55
54
66
68
53
67
64
52
86
62
65
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1 0.3
0.5
0.7
0.9
Final Rate
Final Rate
Final
Rate
(d)
=
(e)
= 21,
C
= 2-1
(f) 0 = 2 C = 2-1
Train Acc. (96)
78
Train Acc. (%)
77
63
76
62
75
61
Train
43
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
0.1
0.3
0.5
0.7
0.9
Final
Final
(g) 2", C
20
(h)
2 C
2
2 C 2
Figure 2: Train accuracy vs. final sparsification rate r* over various combinations of noise multiplier a and clipping bound C, red dashed line marks the performance no sparsification. We set batch size to 1000 and train for 100 epochs, the network is DP-CNN. The result shows that the trade-off favors RS as A, x o²C² increasing, except the last Figure 2i, where due to excessive noise the network degrades after few epochs.
Train Ace. (%6)
54
Train Acc. (%)
Train Acc. (%)
76
52
74
50
72
0.3
0.7 0.9
0.3
0.9
0.1
0.3
0.5
0.9
Final Rate 1*
Final Rate 1"
Final Rate 1"
(a) C' 2-
(b) C' 2
(c)
2
100
100
Train Acc. (%)
Train Acc. (%)
Train Acc. (%)
98
98
98
96
96
96
94
94
94
0.3 0.5 0.7
0.9
0.1
0.5 0.7
0.9
0.1
0.7 0.9
Final Rate
Finel Rate
Final Rate
(d) σ 20
(e) 2
(f) a 2
Figure 3: Train accuracy vs. final sparsification rate r* over SGD with gradient clipping or noisy SGD (sce Algorithms 2 and 3 for pseudo code), other settings are the same Figure 2. The red dashed line marks the performance of no sparsification. Without noisification or gradient clipping RS only leads to utility drop, which matches our theoretical analysis and indicates that the trade-off is unique property of DP-SGD.
10

---

Published in Transactions on Machine Learning Research (06/2023)
Dataset
Approaches
Baseline
RS (ours)
Difference
3.0
69.7 + 0.19
70.0 = 0.11
+0.3
H-CNN
187K
1.0
62.4 + 0.13
63.2 0.10
+0.8
CIFARIO
3.0
62.8 = 0.10
64.3 = 0.17
+1.5
DP-CNN
550K
52.5 = 0.25
55.1 0.11
+2.6
85.9 + 0.06
86.8 0.13
+0.9
H-CNN
187K
1.0
80.7 = 0.15
82.2 0.19
+1.5
SVHN
3.0
83.4 = 0.11
84.5 0.14
+1.1
DP-CNN
550K
1.0
76.0 = 0.05
79.1 = 0.13
+3.1
3.0
88.9 + 0.09
89.2 0.07
+0.3
H-CNN/S
33K
1.0
85.8 + 0.17
87.0 = 0.08
+1.2
FMNIST
DP-CNN/S
26K
=
87.4 0.10
+0.8
1.0
83.2 = 0.10
84.5 = 0.16
+1.3
Table 2: Test accuracy (% + SEM) before and after adopting random sparsification. The difference of mean
accuracy presented in the last column.
such a flat trend also desirable as sparse gradients produced by RS are beneficial for private learning as discussed in Section 5.
Theorems 3.2 and 3.4 suggest that the trade-off of DP-SGD jointly established by noisification and clipping, with either absent, RS just reduces performance. To verify this, conduct experiments two ablation variants of DP-SGD: noisy SGD and SGD with gradient clipping (pseudo code is given in Appendix E). Figure 3 demonstrates that in the absence of either noisification or gradient clipping, RS always makes the convergence slower, which indicates that the trade-off is unique property of DP-SGD.
6.2 Improving performance of DP networks
In practice, the clipping bound C and noise multiplier a are tuned as hyperparameters for the networks to achieve the best performance under a certain privacy budget. To investigate whether RS has chance to achieve better performance in practical settings, we conduct experiments on the following baselines of DP image classification: (i) DP-CNN (Papernot et al., 2021): a network for training from scratch; (ii) H- CNN (Tramer & Bonch, 2021): a network for training solely on private dataset, which uses handcrafted features. Both are representative SOTA frameworks in high privacy regimes (De et al., 2022). We adopt the best hyperparameters provided in previous works, then we do grid search for baselines and RS over the clipping bound Ce E {0.1, 0.5, 1} where C' = 0.1 is given in previous works, and epochs E E (E", 1.2- E", 1.5. E*} (a is adapted accordingly), where E" is the best given in previous works for different frameworks. When conducting RS we use gradual cooling and search for the final sparsification rate r" E (0.5, 0.7, 0.9). Wo also find an interesting scaling rule to efficiently find the optimal hyperparameters for DP frameworks which is given in Appendix H. As a result, some baseline performances we give are higher than reported in previous works. As in the previous section, we observe that RS is beneficial when A, dominant, thus we conduct experiments at high privacy regimes, i.c. (1,3).
Table 2 shows that RS improves the performance of baselines and the gain is significant for smaller where more noise is added. We further note that DP-CNN generally gains more from RS, as it has comparatively more parameters and A, scales with the gradient dimension d.
6.3 Advantages of sparse gradients
Beyond the improvement in performance, sparse gradients also offer additional advantages in the area of private machine learning as discussed Section To investigate the sparsity we can achieve, we directly plugged RS into various frameworks, including: DP-TI. (Tramer & Bonch, 2021): a transfer lcarning frame- work, and GEP (Yu al., 2021a): projected DP-SGD framework, as well DP-CNN and H- H-CNN, using the hyperparameters of no sparsification given in previous works (so the same iterations). Figure 4 shows
11

---

Published in Transactions on Machine Learning Research (06/2023)
61.0
69.6
92.75
74.5
60.8
0 69.5
92.70
74.0
g 69.4
92.65
73.5
69.3
92.60
73.0
60.4
69.2
92.55
72.5
0.1 0.3 0.5 0.7 0.9
0.1 0.3 0.5 0.7
0.9
0.1 0.3 0.5 0.7 0.9
0.1
0.3 0.5 0.7 0.9
Final Rate
Final Ratee" 1"
Final Rate 1"
Final Rate 1"
(a) DP-CNN, E =
(b) H-CNN,
(c) DP-TL, =
(d) GEP, E
Figure Test accuracy (% + SEM) vs. final sparsification rate r' when random sparsification is directly plugged into different frameworks using the hyperparameters of no sparsification given in previous works.
Rete: 0
0.1
Q.3
2.5
2.0
MSE
Original
1.5
1.0
0.5
0.7
0.9
0.5
0.0
0.0
0.3
0.5 Rate r
0.7
0.9
Figure 5: MSE of reconstruction using IG (Geiping et al., 2020) vs. sparsification rate r. In the non-private learning scheme, the MSE is 0.02 represented by the red dashed line. The victim's 's network is ResNet34 and added noise is sampled from (O, 10-3). The results computed 200 images from CIFAR10, four example images are: ship, dog, car, horse.
that we can achieve up to 0.7 0.9 final sparsification rale, i.e. 0.35 or 0.45 average sparsity under gradual cooling, while maintaining the same performance.
In Section we have theorctically proven that with sparse representation, the communcattio overhead of DP federated learning improves. We also provide Theorem 5.1 show that the sparse gradients produced by RS strengthen the privacy against gradient reconstruction attacks through an example of reconstruction using the linear relation between data and gradient. To verify this advantage under a general setting, we conduct experiments Nes.e (He et al, 2016) using the attack approach Inverting Gradients (IG) (Geiping et al., 2020), see Figure 5.
7 Discussion and conclusion
During DP training, it is possible to save the perturbed gradients and accordingly find the coordinates whose gradients were small and possibly continue being insignificant in subsequent iterations. One might therefore expect better performance from ranked sparsification algorithm, which for example ranks the mean of the perturbed gradients of last epoch and sparsifies accordingly. However, we find that due to the dominant noise, such ranking is in fact random, while on the other hand the resulting random sparsification still improves the performance. Similarly, other methods that select unimportant coordinates more precisely, c.g. DP selection or methods with public datascts, also cannot fully climinate randomness. However, such random sparsification may still be beneficial for DP-SGD, which was not realized previously. More discussion are provided in Appendix I.
In this work, we present a thcoretical analysis of DP-SGD with random sparsifi- cation, uncovering a special trade-off between internal components in the convergence bound not observed in other popular SGD schemes. Our findings are supported by empirical evidence. By employing the proposed efficient and lightweight RS approach, we succossfully enhance the performance of bascline models across various realistic settings. Additionally, the sparse gradients generated offer further advantages for addressing key challenges in private learning. However, our analyses do not guarantee that RS always converges faster
Scope and Limitations:
12

---

Published in Transactions on Machine Learning Research (06/2023)
than non-sparsifted approaches. In certain scenarios, such DP transfer learning, RS may be less efficient, as discussed in the Appendix J. Developing a lower bound analysis of the convergence rate can also be inter- esting in terms of the uniqueness of the trade-off, which we leave for future work. Despite these limitations, we believe our insights on the intriguing interaction between RS and DP-SGD hold significant implications for the broader research community and can inspire further investigation of DP-SGD.
It is important to note that DP only reduces, rather than eliminates, the statistical dependency between its imput and output. To ensure robust privacy protection, other techniques like cryptographic methods, including homomorphic encryption and secure multi-party computation, should be considered based on specific requirements and expectations for each individual application and policy context.
Acknowledgments
This research received funding from the Flemish Government. (AT Research Program) and the Research Foundation Flanders (FWO) through project number GOG2921N.
References
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Cor- rado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint Stff::6603.4466 2016a.
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Tlya 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. 908-318, 2016b.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswany. Differentially private learning with adaptive clipping. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2021.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, 2018.
Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpretations and renyi differential privacy. In Proceedings of the Twenly Third International Conference on Arlificial Intelligence and Statistics, pp. 2496-2506. PMLR, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient al- gorithms and tight error bounds. Proceedings Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 464-473, 2014.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Avizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 560-569. PMLR, 10-15 Jul 2018.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning, SIAM review, 60(2):223-3) 311, 2018.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private bias-term only fine-tuning of foundation models. arXiv preprint arXiv:2210000036 2022.
Xiangyi Chen, Steven 7. Wu, and Mingyi Hong. Understanding gradient clipping in private SGD: A geometric perspective. In Advonces in Neural Information Processing Systems, 2020.
Georgios Damaskinos, Celestine Mendler-Dünner Rachid Guerraoui, Nikolaos Papandrcou, and Thomas Parnell. Differentially private stochastic coordinate descent. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):7176-77 7184, May 2021. doi: 10.1609/aaa aaaii./3ii........ 16888.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Felix Dangel, Frederik Kunstner, and Philipp Hennig. Backpack: Packing more into backprop. In Interna- tional Conference on Learning Representations, 2020.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint 2xxu:2224.13650, 2022.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and
Trends@ in Theoretical Computer Science, 9:211-407, 2014.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference on Compuler and Communications Security, pp. 1322 1333, 2015.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is it to break privacy in federated learning? In Advances in Neural Information Processing Systems, pp. 16937-16947 2020.
Mary Gooneratne, Khe Chai Sim, Petr Zadrazil, Andreas Kabel, Françoise Beaufays, and Giovanni Motta. Low-rank gradient approximation for memory- on-device training of deep neural net- work. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3017-3021, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Ges- mundo, Mona Attariyan, and Sylvain Gelly. Parameter-effiiinnt transfer learning for NLP. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2790-27907700 2799. PMLR, 09-15 Jun 2019.
Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates via publicly estimated subspaces. In Proceedings of Thirty Fourth Conference Learning Theory, volume 134, pp. 2717 2746, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXio preprinl orXiv:1412.600 6980, 2014.
Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis of sgd for deep nets: Dynamics and generalization. In Proceedings of the 2020 SIAM International Conference on Dala Mining (SDM), pp. 190 198, 2020.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimolo. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2022.
Ruixuan Liu, Yang Cao, Masatoshi Yoshikawa, and Hong Chen. Fedsel: Federated SGD under local differ- ential privacy with top-k dimension selection. In Yunmook Nah, Bin Cui, Sang- Won Lee, Jeffrey Xu Yu, Yang-Sae Moon, and Steven Euijong Whang (eds.), Dulabase Systems for Advanced Applications,, 2020.
Paul Mangold, Aurélien Bellet, Joseph Salmon, and Marc Tommasi. Differentially private coordinate de- scent for composite empirical risk minimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 44948-14978. PMLR, 17-23 Jul 2022.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-Fifiiie Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1273 1282, 2017.
Nya Mironov. Rényi differential privacy. 2017 IEEE 30th Computer Security Foundations Symposium (CSF).
2017.
Nya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint Xrxi::1000 10530, 2019.
Opacus. Opacus PyTorch library. Available from opacus.ai.
Edouard Oyallon, Sergey Zagoruyko, Gabriel Huang, Nikos Komodakis, Simon Lacoste-Julien, Matthew Blaschko, and Eugene Belilovsky. Scattering networks for hybrid representation learning. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 2019.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 9312 2122-,,11,-- 2021.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference Machine Learning, 2013.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjic Bai, and Soumith Chintala. Pytorch: An imperative style, high-performanc deep learning library. In Advonces in Newral Information Processing Systems, pp. 8024 8035. 2019a.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Autiga, el al. Pytorch: An imperative style, high-performance deep learning library. 32, 2019b.
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X Yu, Sashank Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv: Xix:::190.00666 07643, 2019.
Reza Shokri and Vitaly Shmatikov. Privacy-preservee deep learning. In 2015 53rd Annual Allerton Con- ference on Communication, Control, and Computing (Allerton), pp. 909-9099 110-910,-0 2015.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov, Membership inference attacks against machine learning models. In IEEE Symposium on Security and Privacy, 2017.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, pp. 1139-1147, 2013.
Florian Tramer and Dan Bonch. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations, 2021.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compres- sion for distributed optimization. In H. Wallach, H. Larochelle, A. Beygekimee, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Di Wang and Jinhui Xu. Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view. Proceedings of the AAAI Conference on Artificiol Intelligence, pp. 1182- 1189, 2019.
15

---

Published in Transactions on Machine Learning Research (06/2023)
Yu-Xiang Wang, Borja Balle, and Shiva. Prasad Kastviswanathan. Subsampled renyi differential privacy and analytical moments accountant. In Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, 2019.
Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 30th International Conference Machine Learning, 2011.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 2019.
Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M. Alvarez, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. In Proceedings of the IEEE/CVP Conference on Computer Vision and Pattern Recognition (CVPR), pp.
2021.
Da Yu, Huishuai Zhang, Wei Chen, and Tie-Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Representations, 2021a.
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Yan Liu. Large scale private learning via low-rank reparamctrization. In International Conference Machine Learning (ICML), 2021b.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang, Differ- entially private fine-tuning of language models. In International Conference on Learning Representations, 2022.
Huanyu Zhang, Ilya Mironov, and Meisam Hejazinia. Wide network learning with differential privacy. arXiv preprint Xrx:: 01294, 2021.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
Yingxue Zhou, Steven Wu, and Arindam Banerjoe. Bypassing the ambient dimension: Private SGD with gradient subspace identification. In International Conference on Learning Representations, 2021.
Junyi Zhu and Matthew B. Blaschko. R-GAP: Recursive gradient attack on privacy. International Conference on Learning Representations, 2021.
Junyi Zhu, Ruicong Yao, and Matthew B. Blaschko. Surrogate model extension (SME): A fast and accurate weight update attack on federated learning. In International Conference on Machine Learning, 2023.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, 2019.
16

---

Published in Transactions on Machine Learning Research (06/2023)
Appendix
In this appendix we provide full statements and proofs of our analyses (Appendix A-D). The pscudo code for noisy SGD, SGD with gradient clipping and DP-SGD with ranked sparsification are presented in Appendix E. Experimental results to verify the approximately symmetric property of the gradient deviation distribution P(C)) are demonstrated in Appendix F. More insights of gradual cooling are presented in Appendix G. Scaling rule for efficient hyperparameter tuning is discussed in Appendix H. More details of DP-SGD with ranked sparsifcation and connection between RS and selective sparsification or compression methods given in Appendix I. Limitations of applying RS to DP transfer learning discussed in Appendix J. Comparison between Poisson sampling and random shuffle is given in Appendix K.
Contents
A Proof of applying random sparsification to noisy SGD
18
A.1 Proof of Theorem 3.2
18
B Proof of applying random sparsification SGD with gradient clipping
19
B.1 Proof of Lemma 3.1
19
B.2 Proof of Equation (9) and Equation (10)
20
B.3 Proof of Lemma 3.3
20
C Proof applying random sparsification to DP-SGD
22
C.1 Proof of Lemma 3.4
22
C.2 Proof of Theorem 3.5
22
C.3 Convergence bound with privacy budget variables.
22
D Proof of privacy against gradient reconstruction attacks
23
D.1 Proof of Theorem 5.1
23
E Additional algorithms
25
F Approximately symmetric distribution of the gradient deviation
27
G Further discussion of gradual cooling
28
H Scaling rule for hyperparameter tuning
29
DP-SGD with ranked sparsification
31
J DP transfer learning with random sparsification
31
K Poisson sampling and random shuffle
32
17

---

Published in Transactions on Machine Learning Research (06/2023)
A Proof of applying random sparsification to noisy SGD
Lemma A.1. U U Rd are two arbitrary vectors, m E (0, 1]dd is a random mask with sparsification rate We have the following expectation, E
Bm o u, b)) (1 (u, x)}.
(18)
Proof.
Bl o u. = Bm o u, w)
(19)
Σ B mm E [
(20)
= - -1-r) [u, v)}.
(21)
Corollary A.2. Following the nolations of Lemma A.1, we have the expectation below: u, Gm v)] = [u, u)}.
B[(m
(22)
Proof.
E[ @ u., = [m o u, u3}
(23)
1 - (1-r)B((u,u) u))
(24)
A.1 Proof of Theorem 3.2
Proof. From the G-pischitz smoothness, and noting that Gaussian noise is added to the aggregated gradient and will be divided by batch-size B before updating the model, we have:
G |1++1 1
Cu-1 S Cs + (Ww, W141 w)) +
(25)
Gy2 Il (Vu, + 1 Σ Ee, + +6))1.
= = - m (Ww; Σ Ecs + (o))
(26)
Taking expectations on both sides and rearranging:
1 [B( 2 (Vwi +
Σ Eex Eo)))
B
(27)
G²2 Blll 2 (Vw, + Σ Se,+ S (6))
S [[c L441l
from which we can obtain:
18 (1 (1-rhl we 2| 2 B(c L441 + (1 (1-r)
do²
[|/e BEll Σ 11.1
(28)
2
B²
< Efc, L441l + (1 - G²
a2 do
(l/ +
B² )
(29)
2
B
We apply the same learning rate = aVT as in Bernstein et al. (2018), with which we can derive better convergence under large noise. Combining Vw, I2, we have:
1 1
1 1- r o² do
Vw,| 2 < (1 - r)( GVT 2GT
&
2 EELL
L++1)+
(30)
2GVT
2GT B
B²
18

---

Published in Transactions on Machine Learning Research (06/2023)
Moving all the coefficients to the r r.h.s.:
2GVT
oe VT
do²
| < 1-r BlC, L441]
(31)
B
B
It is worth emphasizing that the factor 1 1-r the r.h.s of Equation (30) is canceled out by the same factor from the hh.ss Consider the average over T steps:
2G
do²
V ww v
Σ Elc 6441] +
Σ
(32)
T
r)TT
TVT
B
B
:
2G
1
02
do²
Blci CT+1]+
(33)
(1-r)) ---r
VT
B
B
2G
d2
do²
$ (1 r)vT
B[4i] - min [(w) +
g
(34)
VT
B
B²
B Proof of applying random sparsification SGD with gradient clipping
Lemma B.1. E Rd is arbitrary vector, have the following inequality:
{0, 1]a is random mask with sparsification rate We
Blllm o ull] 2 (1 |u]l
(35)
Proof.
[I]l O uIll
E B O w||l||]]
(36)
E [[[mm O u|l"]
(37)
22
(1 (u, u)
(38)
||/|
= (1 - [u[l-
(39)
Equality holds when 0.
B.1 Proof of Lemma 3.1
Proof. Following from the G-smoothness assumption, we have:
G
Lut1 S C, + (Vu, W1+1 - -w,) + - [ - - w/
(40)
2
= = - + G-2
2 11
(41)
Taking expectations on both sides and rearranging, we have:
Gy 10ll
E VVV,,, 9.)] - BTC, C.41]
11 1|
(42)
BlC, -L+1]] + G02
(43)
19

---

Published in Transactions on Machine Learning Research (06/2023)
B.2 Proof of Equation (9) and Equation (10)
Similar to Lemma 3.1, consider gradient sparsification then clipping, can obtain:
BkVWe, 9c3] 7
Bl[C. Le41] +
GC
(44)
Now focusing the h...s. we have:
V 9.)l = (Ver, E[g=])
(45)
(Vwi, Σ Elm @ gr. min(1,
I|m @ gu,il )
(46)
C
=K(Vw, ① 9t. min(1,
I @ sm,ll" )
(47)
Bm O Vwr, Hr. min(1, IIm @ ge.e ommell M
(48)
E (Vl Ph. min(1, |196 C' )>]
Em
(49)
Em
Re (V w/y L. min(1, II |l }>)
+ Tm [4].
(50)
where we define Vwy = m 3 Vwi, & =- & with corresponding true distribution p6 and proxy 1% which are projected from ps and Pe: by := (VV (.)) Ex,z; [(Vw,, (o'',e))), G.)). Equation (49) holds because and m are independent. Since the projection of symmetric distribution to a subspace is symmetric, i.c. (E() = - We can adapt Theorem 3.3 for the first term:
C
E Bec-p,((Vuul d.. min(1,
|o%h,111 }>]
2 Em (Pe--; (l& <3//4MMVv))
(51)
B.3 Proof of Lemma 3.3
Proof.
Consider the following two cases:
case 1: Vwell s C/4, then (I S
=
Em [P < VC/AVVVVVVV/VVVVVVVVVVVVVII 2 Parp (1 3//4
(52)
Psrmps (1(&+] 3C/4)E,..|/V'//fP
(53)
2 Per~p (l|Eell < -1--
(54)
= (1 - PEenpi (Il&al < VV:)) Vwyll-
(55)
case 2: /uxl > C/4, consider two events Ai: || S C/4; A2: |v > C/4 then we have:
Em (P (1E)l) 3C/4))Vvx]]]VVV[
2 Ps.Mp (leEll) 3C/44)E..
(56)
54
Ε Par-p (I|E -))
(57)
35 2 Psospe (11Eol 3C/A))P(AA/11
(58)
P(A2) - (1rr)[[Vw.l])
2 PeInpo (11Eell < 30/44(1--)) C 1V
(59)
= (1 - (1-r))Pr-p. (1lEl1 < <3C/4)((vw:)]lvuu
(60)
20

---

Published in Transactions on Machine Learning Research (06/2023)
from which conclude that:
Em PmilPtint (115'1l < The inequality above implies that ks, 2 such that:
2 (1- PErDE (lesel < vv:)
(61)
Em p (IlE/ll < 3C/4)/(Vv/) Vwlill = Kt KePErrD (11s:ll 3C/4))(Vw))lVvvll
(62)
We note that N2 if and under natural assumption, e.g. Perwy (I|+/ll <C//4) > Pa.p. (leElll 3C/4). have Ki > 1
0.
Now we form the lower bound for 6x using the condition Pe-- (I&& < 3C/4) > --- We emphasize that as the network converges during training, the following property will be satisfied with the true probability distribution pr:
Peopp (llEell 3C/4) 2 VI-r.
(63)
So the condition of choosing Pt will not lead to significant bias term by Based on the condition, we have:
PEIOS (lesell < 3C/4)VV 2 vI-r Consider two cases:
(64)
case 1: //ll 2 C/4, r.h.s. of Equation (64) has:
rh(Vw)) ((Ww) /
(65)
22 h (w) 11
(66)
2 h (Vww) Vw/I|]
(67)
Em Vw/II]
(68)
Em [ V V
(69)
where Equation (67) is taken according to Jensens' inequality.
case 2: |//l| S C/4, so we have ||V || S C/4, then:
rl(VVv)))Vvve v1 11--| Vwl
(70)
2 (1 v/
(71)
22 Em ||/ [|3]
(72)
Em (V V
(73)
Combing two cases, we can obtain the following property:
Parmi < 3C/4M)VV))]IVVr
V1 rh(Vw)]lVur
(74)
E (h (Vw')I
(75)
2 E., PE:~ (1S VC/4))[V""]IVV
(76)
It is worth noting that the above inequality can also be obtained under other conditions, the one we provided, i.e. Perup, (II&.ll < 3C/4) 2 vI --rr r, a sufficient but not necessary condition, which will be definitely satisfied the network converges, i.e. ||Vw]] 0, ||& O.
Combining Equation (76) with Equation (61), obtain: 3xd E (1 rr,
Em Em(Pet-w (lEE'll < (C/4) = K Pernes (1Eell 3C/44)(V::][Vvv/
(77)
St. takes 1 when 0.
21

---

Published in Transactions on Machine Learning Research (06/2023)
C Proof of applying random sparsification to DP-SGD
C.1 Proof of Lemma 3.4
Proof. Following from the smoothness assumption, have:
G
L4t $ L. + (Vwi, wh+1 - wi) +
|10411 - will
(78)
2
Gy²
= L. 7->(( 0r + EDP) +
11 + m @ Enpll
(79)
2
Gh² l @
-. - 7V (x) (Vw,, Enp)
(80)
taking expectations on both sides and rearranging, have:
BI(V wi, 0:)1 ~ B(c, Ce+1 B(VV @ {np)) + G7 Elll + @ EnPlA)]
(81)
7
2
Blcr - L(+1] +
(Blll: 13 Elllm @ Enp 0)
(82)
2 Elc, C++1l
G7
(B ||_] + r)
-)) C²o2d
(83)
2
B
G7 (C2 (1 - r) C²d
$ Blc c+t1
(84)
2
B3
0
C.2 Proof of Theorem 3.5
Proof. Combine Equation (9), 10 and Lemma 3.3:
K2 Pe (l&&ll < <CC44) + Em [M S EKVWw, 9.)]
(85)
Substitute Lemmma 3.4 and rearrange:
RePeiNg (IlEell 3C/4) E B(V 9.31 - Em [b.b
(86)
GC
ke PePerne (IKeel) <3C/4)]Vv::]\ ElC. L1+1] +
+ (11r))4,
-Em [b]]
(87)
ElC, L+t1l
GC
Em [bl)) + 1 >
(IEEl < <3C/4)
+
(88)
7
Ait
Since KI.T E (1 r), then 3x E (1 r, 1), such that consider all T iterations, have:
1
Pernp (Ie&ll < 3C/4) <
1
Ac 7/'
+
GC
1
Σ Em b1))
1-7
(89)
T
2
K
7
C.3 Convergence bound with privacy budget variables
Theorem C.1 (Abadi et al. (2016b)). There exist constants u and v so that give sampling probability
q == B/N and the number of steps T, for any E < TTT, DP-SGD is (e, diffeerrrytt private for any > if we choose:
0 2 u Qv Tlog(1/8)
(90)
E
22

---

Published in Transactions on Machine Learning Research (06/2023)
So to achieve (c, dddiieerentt privacy, choose u 1. log(o//))) and note that for DP-SGD, large batch is preferred in practice, the following corollary proves that the upper bound of true gradient norm Vw, decreases w.r.t. iterations T:
Corollary C.1.1. Follow Theorem 3.5, consider the overall T iterations with learning rate y GVT
batch-size B vT, privacy budget (e, 5), we have:
T Σ
1 1.4G
C
1 T
1
Pe (11&ll < 3C/44M(Vw)IVVVV S VT
Em [[]] +
De
(91)
T
2vT
T
t=1
dC 1/8(1/8)
where we define A
2v
Proof.
Pe PELOEi (lksell < <3C/4))(Vu:)) [wy
(92)
A
GC
T
1 l-r r +
<
+
Σ
Bm(1/))
7..
(93)
TT
2
T
ki
1=1
1
DeG
C²
T Σ
+ 1-1
Em [b(]]
(94)
VT
2/T
T
K
[=1
Focusing on y2o:
CC
u TlggToog(1/)
AA
(95)
2B2
g²
C2 u log(1/8)
(96)
2
E²
u x² log(1/0)
(97)
T
Plugging Equation (97) into Equation (94):
T Σ Pg. Perps (
1 A
C2 T
1 r
<
+
A. T
Em [b]] +
(98)
T
K VT
2T
1=1
Proof of privacy against gradient reconstruction attacks
D.1 Proof of Theorem 5.1
Proof. Analogous to K g (Zhu & Blaschko, 2021, Equation (15)), we have the following system of linear equations:
m ④ kr = m ② g-
(99)
Assume that m O k + 0 (otherwise the reconstruction will fail, i.. arbitrary reconstruction error), can be estimated through least squares:
f ((n @ k) (0 @ k)) (m k) (m @ ())T)mm
+ Ex))-
(100)
23

---

Published in Transactions on Machine Learning Research (06/2023)
The squared error of reconstruction can be expressed as:
|| - 2| 2||²= = 2 ((m 2 k) (m оk) (m (m0A)(m0(++)))
(101)
= | - (m) (m
(102)
= (tm
(m (m)
(103)
Take expectations on both sides:
B||| - & =1² = IBIl ((m O k)
(m k))
(m o TT 1
(104)
m O k
(m O k) T
E
(105)
m k||2
② k
(m O K)T
mm k| H
(106)
Im O kl2
(m O k) [m O k|
k
-Tr(B[S,,, E
(107)
Im @ k| (m k)
-Tr(o" L
(108)
|| @ k||²
Im + 1
TTE
m
(m k)
の kl H
(109)
m @
oFB m @ k|j
(110)
We that more gradients are zeroed out, the expected squared error increases. In particular, according to Jensen's 's incquality and the convexity of 1/|[m @ kll
E
2|
(111)
E m 1| (1 (1-1)
d²
(112)
The lower bound of expected squared error increases monotonically with increasing sparsification rate r.
0
24

---

Published in Transactions on Machine Learning Research (06/2023)
E
Additional algorithms
We provide pscudo codes for Noisy SGD with RS (Algorithm 2), SGD with gradient clipping and RS (Algorithm 3), and DP-SGD with ranked sparsification (Algorithm 4).
Algorithm 2 Noisy SGD with Random Sparsification
Input: Initial parameters Wo; Epochs E; Batch size B; Sparsification rate: r"; Momentum: μr; Learning rate 7, Noise multiplier a.
for to do
Gradual cooling
r(e) = r E-Ti
4:
> Generate random mask every epoch
5:
m E [0, s.t. [|m]]| = d (1 (1-r()));
6:
for 0 T do
7:
> Compute aggregated grudients
gr = Σ; Vi(w,, xz); Sparsify gradient
10:
5/ m 9ti
11:
Add sparsified noise
12:
Jc- +(g m (O, oala));
13:
b Update parameters
14:
14+1 = 14 14 + Dr, w++1 = wt 71++1
Algorithm SGD with Gradient clipping and Random Sparsilication
Input: Initial parameters wi; Epochs E; Batch size B; Sparsification rate: r"; Clipping bound: C Momentum: μr; Learning rate 7.
for to E - do
> Gradual cooling
r(e) rr E-T:
4: > Generate random mask every epoch
4
5: m E {0, s.t. ||m]] = d (1 - r(c));
for = to - do
For each x; in the minibatch of size B gr, vl(w,,;;); Sparsify gradient
10:
K', =m ④ 9t.s;
11:
D Clip each individual gradient
4
12:
he- = 1/b Eishs
13:
b Update parameters
14:
U++1 = p Ut + gr, w++1 = wt 70+11
25

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm 4 DP-SGD with Ranked Sparsification
Input: Initial parameters wo; Epochs E; Batch size B; Sparsification rate: r"; Clipping bound: C; Momentum: μd; Learning rate 7; Noise multiplier a.
1: for to
do
2: Ee = {0]a;
Gradual Cooling
r(e)= = E
Generate ranked mask every epoch if is 0 then
7:
m = {1]d
8:
else
9.
Sort the indices [1.... d] with respect to the magnitude of aggregated gradient the last epoch | ascending order then set the first d r(e) positions in mask m to and the rest. to 1 for to T do
10:
11:
For each 2; in the minibatch of size B
12:
De, v+)w;
13:
b Sparsify gradient
14:
Le, m ④ 9t.s:
15:
Clip each individual gradient
4
16:
Ge,i 14...min (1in(1 C/1lss..lll; Add sparsified noise
17:
18:
Gr 0r, + @ NO, Ca)= Update parameters
19:
20:
e++1 = 4.22 + ge, w++1
70t+1
21:
b Save perturbed gradients
22:
z" = 2" + He + t m) @ (0, C2
26

---

Published in Transactions on Machine Learning Research (06/2023)
F Approximately symmetric distribution of the gradient deviation
As the gradient deviation distribution P(E)) is high-dimensional, demonstrating and verifying its symmetricity is in general intractable. We therefore adopt random projection onto & 2D for the visualization, which is also adopted by Chen et al. (2020). Our experiments reproduce their observation that the gradient deviation distribution approximates symmetry during training with DP-SGD (see Figure and 7). We verify that this property also valid for DP-SGD with RS (see Figure 8 and 9). We have repeated the experiments times, all results qualitatively the same as presented here.
(a) Epoch
(b) Epoch 3
(c) Epoch 6
(d) Epoch
(e) Epoch 20
(1) Epoch 40
(g) Epoch 60
(h) Epoch 79
Figure Gradient deviation distribution during training, projected onto a 2D using a random matrix.
Network is DP-CNN, method DP-SGD, dataset CIFAR10.
(a) Epoch
b Epoch 3
(c) Epoch 6
(d) Epoch
(e) Epoch
(f) Epoch
(g) Epoch 60
(h) Epoch
Figure Gradient deviation distribution during training, projected onto 2D using random matrix.
Network is DP-CNN method is DP-SGD, dataset is CIFAR10.
27

---

Published in Transactions on Machine Learning Research (06/2023)
(a) Epoch
b Epoch 3
(c) Epoch 6
(d) Epoch
131
(e) Epoch 20
(l) Epoch 40
(g) Epoch 60
(h) Epoch 79
Figure 8: Gradient deviation distribution during training, projected onto 2D using a random matrix.
Network is DP-CNN, method DP-SGD with RS, dataset is CIFAR10.
(a) Epoch
b Epoch 3
(c) Epoch 6
(d) Epoch
(e) Epoch 20
(f) Epoch 40
(g) Epoch 60
(h) Epoch 79
Figure Gradient deviation distribution during training, projected onto a 2D using a random matrix.
Network is DP-CNN, method DP-SGD with RS, dataset is CIFAR10.
G Further discussion of gradual cooling
For the convenience we restate Equation (14) here, and for the clarity we define Ac = Ar
78 + 7 GC
1 Dx Em](y]] [b]] to denote the terms that are enlargod by RS:
T
1 1-r K
Do Σ PeImp (1e&/l < 3C/4)MVV
~A.
(113)
K
We see A, = C22 can be computed given the constants, assume Ac is also given, to deduce the optimal sparsification rate, we need to relate to However, beyond giving range x E (1 11-r, 1), it is not possible to represent x by r without supposing an additional assumption over the shape of the distribution of the gradient deviation, which is difficult to make. We therefore start from the empirical evidence in Figure 3.
28

---

Published in Transactions on Machine Learning Research (06/2023)
Recall that the factor introduced by RS for noisy SGD is 1/(1 - r) (see Theorem 3.2) and for SGD with gradient clipping is 1/k (see Theorem 3.4). From Figures 3a, 3b, 3c, we see that as r increases SGD with gradient clipping also obviously converges slower, which implies that 1/k also grows with r. From Figure 3d, 3c, 3f, we find that the performance of noisy SGD tends to drop more dramatically in a high sparsification regine, like a parabolic shape, which implies 1/k comparatively more stable than 1/(1- -r) as changes.
Based on these observations from Figure 2, suppose that R /1 -r, r, which complies with the theoretical analysis that 1 when 0 and (1 (1-r,17 1). Using this relation we express the convergence bound as function of sparsification rate r:
U(r) = vI
Ac Ac V1-rAp
(114)
To find the optimal r", we can simply compute the derivative of U:
U'(r) = 1/2 - - -1/2 1/)
(115)
Consider the first order condition, we have:
=1 Ac/Ao.
(116)
So when Ac > A,, i.e. the noise term is insignificant in the convergence bound, we have r" = 0 is opti- mal. While when A, > Ac, we have r* = =1 Ac is optimal, and as A, becomes dominant, higher sparsification rate is preferred. We see this conclusion matches our empirical evidence in Figure 2.
Although in practice Ac is unknown and r* therefore cannot be precisely estimated, the observation and conclusion above reason and support the gradual cooling. At carly training stages, the network converges fast: EE[.- - L++1] is large, while at late training stages, the optimization reaches & plateau: E[C, Le+ decays, in contrast Ag is constant and becomes relatively large, the best sparsification rate r" thus should be increasing during training.
H Scaling rule for hyperparameter tuning
First order momentum is commonly adopted in the optimization with DP-SGD, because momentum can alleviate oscillation and accelerate gradient descent (Sutskever et al., 2013), it is therefore believed to reduce the number of iterations training and therefore achieve less privacy loss. However, for training, momentum will also exaggerate the added Gaussian noise by incorporating current and all historical noise.
Denote velocity update: u+41 = μ Ue + 9t+1, where v, μ, ğ denote perturbed velocity, momentum and perturbed gradients, respectively, common implementation of SGD with momentum includes 1, c.g. for Pytorch (Paszke et al., 2019a) or a -7, e.g. for Tensorflow (Abadi et al., 2016a). Using the expression of one step noise in Equation (4) and denoting by fr the velocity after separating the noise, we have:
U++1 θ.+1 (1 + n²² + +... + n²) (N, C
(117)
After many iterations, the scalar approximates geometric scries, i.c.:
Ut+1 l.f1 ~
1- (N
(118)
with residual decaying exponentially. Pulling the clipping bound C out and forming the noise C(1 u) aN(0, o I2), we present scaling rule for adjusting C. and μ. namely the local optimal values of C, p satisfy the same C/(1 - μ): the same amount of noise. As shown in Figure 10, the local optima of every column or row is located on the diagonal, where C/(1 p.) = C* /(1 - v²)) (C*, jr" are given in previous works).
The scaling rule suggests a workload saving pipeline for tuning, as it decomposos a 2D scarch into a line search: i) Set either C or μ fixed and search for the other (search in a row or column); ii) Adjust C, p jointly according to the scaling rule to find the optimal combination (searching along the diagonal).
29

---

Published in Transactions on Machine Learning Research (06/2023)
0.01
28.8
32.0
42.7
56.1
Acc.
0.01
02.0
35.5
46.8
64.5
Acc.
0.01
84.0
67
91.1
92.8
AcC.
0.01
11.5
46.7
56.5
66.4
Acc.
80
82
g
0.1
42.9
47.2
36.
0.1
47.0
51.2
90.0
0.1
91.5
02
92.6
90.2
90
57.4
63.3
69.4
59.3
60
57.1
61.6
0.5
67.4
$1.2
50
0.5
88
1
62.6
56.8
36.7
16.4
68.4
63.6
41.5
31.4
40
92.0
90
8
88.2
87.4
86
69.8
67.2
57.4
51.9
50
0
0.5 0.9 0.99
0.5
0.9
0.99
0.5 0.9
0.99
0.5
0.9
0.99
Momentum
Momentum
Momentum
Momentum
(a) DP-CNN, 8
(b) DP-CNN, 7.53
(c) DP-Transfe Learning,
(d) Handcrafted CNN,
6 2
Figure 10: Accuracy (%) under different combinations of clipping bound and momentum p.. The diagonals represent combinations adjusted by the scaling rule based on values of and μ given in previous works. The red dashed square marks the given hyperparameters, and the red solid square the optimal hyperparameters.
We note that the scaling rule assumes noise being directly added to velocity, for projected DP-SGD where the noise has been projected, this rule may not be applied. Additionally, for some adaptive optimizers, e.g. Adam (Kingma & Ba, 2014), computing of velocity is implemented as follows:
1++1 = 1 1/2 + (1 - 14)0e.
(119)
u = 0141/(1 -1'))
(120)
If we ignore the scaling in Equation (120) where the factor - 1r¹ increases rapidly to 1, we have:
1++1 - 82t1 = (1+ + 122 + +... (1-)))1-)))((0 C² o²Ia)
(121)
1
1- (1- 1)N(0, C² oPIa)
(122)
=N(0 o0)
(123)
Here we see C and μ are decoupled in term of the noise amount, which suggests that they can be tuned independently. So searching for the best combination be decomposed into searching in row followed by its column vice versa, as the best μ is the same for different C and vice versa, see Figure 11.
2
2
81.5
59.4
59 68.4
2'
68.8 75 66.8 68.4
Acc.
Acc.
2
62.1
59.8
59.5
58.8
2
68.8 7 67.0 66.7
60
2
62.7
60.6
60.2 60.0
55
68.6 67.3 67.5 68.7
64
62
2
60.5
59.7 59.2 58.2
2
67.5 66.9 9 66.8 66.4
60
2
54.0
64.5
2²
48.7 8 48.7 46.3
2
89.6 59.9 60.0 58.6
0.5 0.9 0.99 Momentum
0.5 0.9 0.99
Momentum
(a) =3
(b) E = 7.53
Figure 11: Accuracy (%) under different combinations of clipping bound and first order momentum. The network is DP-CNN and the optimizer Adam (Kingma & Ba, 2014).
30

---

Published in Transactions on Machine Learning Research (06/2023)
DP-SGD with ranked sparsification
For ranked sparsification, we consider a straightforward implementation which ranks the (absolute) mean of the perturbed gradients of last epoch and sparsifies accordingly. As DP is robust post-processing, such ranked sparsification does not consume the privacy budget.
Algorithm 4 describes the proposed ranked sparsification. Note that the noise added to the gradient mean estimation 2" is not sparsified (Line 22), otherwise the coordinates that get masked out at the first iteration will receive gradient mcan cstimation as 0 and never get updated for all the remaining iterations, which will degrade the network. Adding noise to sparsified coordinates can give these coordinates a chance to be ranked in higher positions, while in turn the coordinates being updated but with low magnitude of their true gradient may get masked out in the next iteration.
However, il lurns out that ranked sparsification cannol outperform random sparsification, more precisely it performs the same as RS. We further find that it seems the ranking is fundamentally random as the ranking is dominated by Gaussian noise. To demonstrate this, we run random sparsification and ranked sparsification for 100 epochs, then statistically analyze the distribution of how many times a parameter is masked out. The result shows the equivalency between these two strategies, which implies even averaging the perturbed gradients over full epoch cannot sufficiently mitigate the noise added in gradient perturbation, see Figure 12.
Non-orivately Ranked Sparsiiization Random Sparsilization Ranked Sparsification
10
10*
parameters
10
10"
10
10
0
20
40
80
of times parameter is masked out
Figure 12: Histogram of the number of parameters vs. the number of times a parameter is masked out during 100 epochs training. For comparison we present non-privately ranked sparsification, i.c. ranking after excluding noise. Random sparsification and ranked sparsífication mostly overlap.
This indicates that the context of DP-SGD selecting the unimportant coordinates is difficult and stochas- ticity cannot. be fully eliminated. Although there exist options to increase the precision of ranking, for example using public dataset (Zhou et al., 2021; Yu et al., 2021a) or via sparse vector techniques (SVT) and DP selection (Zhang et al., 2021; Dwork & Roth, 2014), there is probably mismatch of the empirical distributions of public dataset and private dataset, while SVT and DP selection definitely contains random- ness. However, as we show with RS, under such randomness, sparsífication could still be beneficial for the optimization, which was not realized before.
J DP transfer learning with random sparsification
Differentially private (DP) transfer learning has recently gained popularity due to its effectiveness in various downstream lasks (Tramer & Boneh, 2021; Li et al., 2022; Yu el al., 2022; Bu et al., 2022). DP linear probing reuses the feature extractor, significantly reducing the gradient dimension (Abadi et al., 2016b; Tramer & Bonch, 2021). Li al. (2022) demonstrated that DP finc-tuning of pro-trained large language models can achieve performance close to non-private fine-tuning, Meanwhile, Yu al. (2022); Bu et al. (2022) showed that parametee--fffiient fine-tuning outperforms full fine-tuning.
31

---

Published in Transactions on Machine Learning Research (06/2023)
However, when applying RS to DP transfer learning, we have not observed significant performance improve- ment with high sparsification rates. The reason is that the configurations of DP transfer learning reduce the efficiency of RS. Based on Remark 3, RS is beneficial when the clipping bound C, noise multiplier Ø, and gradient dimension are large, while the batch size B is small. Although DP transfer learning adopts large models, linear probing or parameter-efliient methods constrain the gradient dimension to be less than 1% (Yu et al., 2022) or even 0.1% (Bu al., 2022) of the original parameter space, rendering small. Fur- thermore, since pre-trained networks converge quickly on downstream tasks, DP transfer learning methods typically employ hyperparameters such large batch size B, small clipping bound C, and noise multiplier o, making random sparsification less efficient. In contrast, in training-from-ssratch scenario, networks require more iterations to train. Large batch size B and small noise multiplier result in fewer iterations for a given privacy budget while small clipping bound C limits the gradient magnitude, therefore they are not preferred in the hyperparameter tuning. And random sparsification more favorable for training from scratch.
RS may be beneficial for DP full fine-tuning where the gradient dimension sufficiently large. However, this work focuses on the unique interaction between DP-SGD and RS, we leave more comprehensive study of practical usage of RS for future research.
K Poisson sampling and random shuffle
In the analysis of DP-SGD Abadi et al. (2016b), Poisson sampling is used to induce the privacy amplification (Balle et al., 2018; Wang et al., 2019; Mironov et al., 2019). In the implementation of our baselines and many previous works (Papernot et al., 2021; Tramer & Boneh, 2021; Yu et al., 2021a), sampling is implemented by random shuffling the dataset and partitioning with fixed batch size, i.e. uniform sampling without replace- ment. It is reported that the model performance remains approximately the same under these two sampling schemes (Tramer Boneh, 2021). In this work, we follow the baselines validate that the benefit of RS is consistent under this difference, we redo the experiments with DP-CNN on CIFAR10. The results are given in Table 3. We note that there is no significant difference in performance between "partition" and "Poisson" settings, and that the advantages of RS hold in both.
conduct the experiments. To
Sampling
Baseline
RS (ours)
Difference
3.0
62.8 1 0.10
64.3 0.17
+1.5
Parition
1.0
52.5 + 0.25
55.1 i 0.11
+2.6
3.0
62.8 + 0.27
64.6 + 0.25
+1.8
Poisson
1.0
52.8
+ 0.24
55.2 + 0.25
+2.4
Table 3: Test accuracy (% + SEM) before and after adopting random sparsification with different sampling schemes. Partition indicates random shuffling the dataset and partitioning into batches of fixed size per epoch.
32


Reviews:
[{"review_id": "5cmFCBRJ7b", "reviewer": "Reviewer_6o4t", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The message is clear and simple. \n- The contribution is clear too. \n- Improving theoretical upper-bounds (even by a constant) is very important in DP-SGD because of the DP guarantees limit the number of steps that can be performed (or ask for larger batch size). \n- Experiments support the theory. \n\nWeaknesses:\n- The arguments are based on the fact that space gradients hurt the upper-convergence bound for clipped or noisy gradients. However, with another proof technique, one may be able to show that sparse gradients improve the convergence rates in that case. The authors could try to provide lower bounds to strengthen the significance of their claims and contributions. \n\n\n\n**Question:**\nIs there a way to improve Theorem 1.1? It seems the algorithm is seeing less information regarding the gradient and, thus, the data.\nWhat is state of the art in terms of DP on CIFAR? It seems that your technique could be applied to SOTA techniques. If not, what is the issue? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper shows the positive impact that randomly sparsified gradients may have on the upper-convergence bounds of Differentially Private SGD. An improvement in the convergence rate can have a significant impact since the differential privacy requirements require increasingly larger batch-sizes that depend on the final number of iterations. Moreoever, sparsified gradients have some practical, appealing properties, because they are compressed versions of the original stochastic gradients. \n\nMore precisely, the authors show that, 1) spacification does not hurt the differential privacy guarantees (Thm 1.1) 2) spacification of the gradients degrades the upper-convergence bound of SGD for either noisz or clipped gradient but 3) improves the convergence upper bound of DP-SGD (SGD with clipped noisy gradient), specifically in the case of large noise. Finally, the authors validate their findings with experiments. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not have any significant requested change. \n\n\nMinor notes:\n- Caption of Figure 1: some quantities are only defined later  (e.g., $\\xi_\\sigma'$)\n- Caption of Figure 3: with gradient clipping ~~and~~ or noisy SGD.\n", "broader_impact_concerns": "This work does not describe any potential negative social impact of the results presented. However, since this paper is theoretical it may be interesting to wonder how these theoretical results may be misinterpreted to justify some actions or policies. For instance, the authors could develop the limitation of the differential privacy framework and to what extent it corresponds to a specific notion of privacy.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EED2t65VCS", "reviewer": "Reviewer_YD2n", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This work tackles an important and under-studied topic, i.e. the convergence of DP-SGD in the non-convex (deep-learning-related) setting. Therefore the impact can be significant. The overall structure is clear and convincing.\n\nWeaknesses:\n\n1. My major concern is the result in Theorem 3.1 and any theorems that use it. I believe **Theorem 3.1 is correct but not optimal nor sufficiently novel**. Similar analysis (under almost if not completely the same assumptions) has been presented in Appendix D of [1] and Theorem C.1 of [2]. In both cases, the learning rate is set to $1/G\\sqrt{T}$. This is fundamentally different from Theorem 3.1: this work only shows $\\|\\nabla w\\|^2\\leq O(1/T)+constant$, which does not vanish as $T\\to\\infty$ so the algorithm does not converge; however, those work shows $O(1/\\sqrt{T})$ after some trivial rewriting. Therefore, I believe Theorem 3.1 must be rewritten and further modification may be needed in following theorems and the trade-off. This won't address the novelty but improves the result.\n\n2. Only toy datasets are experimented, where the improvement is rather marginal. This weakness does not necessarily mean a bad thing, but the authors should consider a different optimization regime **with pre-training**, given that all experiments here are training from random initialization. For example, CIFAR10/CIFAR100 can achieve 99%/90% accuracy under DP with 3 epochs fine-tuning. The computation cost is low and RS may have better results in this fine-tuning regime.\n\n3. Related to the above fine-tuning, a popular topic is DP PEFT (parameter-efficient fine-tuning). This is briefly discussed in Section 2 but not extensively. For example, some particular methods like DP-LoRA, DP-Adapter, DP-BiTFiT should be discussed as alternative sparsified gradient. The comparision between DP PEFT and RS as examples: (1) RS is random and can invoke Lemma B.1. (2) RS cannot leverage the compute acceleration because the sparse mask is different at every iteration/epoch whereas DP PEFT sparsifies a fixed subset of parameters, so some tensor multiplication during back-propagation can be avoided. (3) RS and PEFT both enjoy communication benefit in distributed settings.\n\n4. Minor: In the main text, try mentioning DP-Adam since RS directly works and some people don't regard Adam as SGD.\n\n\n\n[1] Bu, Zhiqi, et al. \"Automatic clipping: Differentially private deep learning made easier and stronger.\" arXiv preprint arXiv:2206.07136 (2022).\n\n[2] Bernstein, Jeremy, et al. \"signSGD: Compressed optimisation for non-convex problems.\" International Conference on Machine Learning. PMLR, 2018.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies DP optimization with randomly sparsified (RS) gradient. The main contribution is theoretical and breaks the algorithm into two operations -- the per-sample gradient clipping and the noise addition. The authors claim that RS introduces a unique trade-off in the convergence bound and support their analysis with some empirical evidence.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Rewrite Theorem 3.1 and all relevant parts.\n\n2. Experiments on some fine-tuning tasks.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5imzsjdRcE", "reviewer": "Reviewer_gxEp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. A new DP-SGD algorithm based on randomly sparsified gradients is proposed.\n2. Convergence analysis for the proposed algorithm for the nonconvex case is provided. The convergence rate implies that DP-SGD with RS can recover the vanilla DP-SGD when $r=0$ and outperform the vanilla DP-SGD when $r>0$. \n3. An interesting phenomenon is observed: Applying RS technique for noise SGD (without clipping) and SGD with clipping (without noising) will not improve the convergence rate.\nThe trade-off raised by RS in the context of DP-SGD is special.\n\nWeakness\n1. The basic DP-SGD algorithm used in the paper is proposed by Abadi et al.(2016). However, the sampling scheme used in Abadi et al.(2016) is Poisson sampling instead of uniform sampling without replacement, i.e., in each iteration $t$, we do a Bernoulli experiment with probability $q=L/N$ for each example $x_i$. With this sampling scheme, we cannot guarantee a minibatch with size $B$ is sampled from the whole dataset as we do in Algorithm 1. This problem will not affect the results of the main Theorem 3.4, but it will affect the results of the experiments since the variance of the Gaussian noise (see Theorem C.1 in Appendix C) is different for the two sampling schemes. Please check the results of Abadi et al.(2016), and let me know if I misunderstood.\n\n2. The organization of the paper is not good enough, for example, Theorem 1.1 is not the main result of the paper, so it’s better to move it to Sec 3. Further, I would suggest the author first present the pseudo-code of DP-SGD with RS at the beginning of Sec 3 and then provide its convergence analysis, which is the main result of the paper. Then presenting the results in Sec 3.1 and 3.2. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a differentially private SGD algorithm with randomly sparsified (RS) gradients, i.e, randomly sample some coordinates of the gradient in each iteration and then use these selected coordinates to update the variables. The convergence rate of the proposed algorithm is established. In addition, an interesting phenomenon is found: the trade-off raised by RS in the context of DP-SGD is special, which manifests under two preconditions: gradient clipping and noisification. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please check the sampling scheme in Algorithm 1\n2. Since the proposed algorithm is similar to random coordinate descent with DP, there need more discussions in the main paper to emphasize the difference between them.\n3. In Remarks 1 and 2, it’s better to compare the established rates with the desirable rate. \n4. Please go through the paper, some statements are not rigorous (e.g, Thm 3.4, “Combine Lemma 3.3, Lemma 3.4, and Equations 9, 10……”). Also, there are many typos in the paper. Pay attention to citing the equations (e..g, it should be “equation (7)” instead of “equation 7” in page 5). \n5. $f(X)$ in equation (2) should be $\\frac{1}{B}\\sum_{x}g(x)$? Since the average gradient is used in Alg 1.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the feedback from the reviewers, it appears that two of them have recommended accepting the paper after the rebuttal. While one reviewer still has a concern regarding algorithmic improvement, they acknowledge the interesting theoretical benefit shown by the Random Sparsification (RS) approach. Considering that the primary contribution of the work is mainly theoretical and has identified a unique and interesting interaction between random sparsification and DP-SGD, which sets it apart from other SGD schemes, I concur with the majority of the reviewers and recommend accepting the paper.
Decision: Accept (poster)