Differentially Private SGD with Sparse Gradients
Authors: Junyi Zhu
Matthew B. Blaschko
Venue: ICLR 2022 Submitted (2022)
Keywords: differential privacy
differentially private SGD
privacy-preserving training

Abstract: A large number of recent studies reveal that networks and their optimization updates contain information about potentially private training data. To protect sensitive training data, differential privacy has been adopted in deep learning to provide rigorously defined and measurable privacy. However, differentially private stochastic gradient descent (DP-SGD) requires the injection of an amount of noise that scales with the number of gradient dimensions, while neural networks typically contain millions of parameters.  As a result, networks trained with DP-SGD typically have large performance drops compared to non-private training. Recent works propose to first project gradients into a lower dimensional subspace, which is found by application of the power method, and then inject noise in this subspace. Although better performance has been achieved, the use of the power method leads to a significantly increased memory footprint by storing sample gradients, and more computational cost by projection. In this work, we mitigate these disadvantages through a sparse gradient representation. Specifically, we randomly freeze a progressively increasing subset of parameters, which results in sparse gradient updates while maintaining or increasing accuracy over differentially private baselines. Our experiment shows that we can reduce up to 40\% of the gradient dimension while achieve the same performance within the same training epochs. Additionally, sparsity of the gradient updates is beneficial for decreasing communication overhead when deployed in collaborative training, e.g. federated learning. When we apply our approach across various DP-SGD frameworks, we maintain accuracy while achieve up to 70\% representation sparsity, which proves that our approach is a safe and effective add-on to a variety of methods. We further notice that our approach leads to improvement in accuracy in particular for large networks. Importantly, the additional computational cost of our approach is negligible, and results in reduced computation during training due to lower computational cost in power method iterations.

Under review as a conference paper at ICLR 2022
DIFFERENTIALLY PRIVATE SGD WITH SPARSE GRA- DIENTS
Anonymous authors Paper under double-blind review
ABSTRACT
To protect sensitive training data, differentially private stochastic gradient descent (DP-SGD) has been adopted in deep learning to provide rigorously defined pri- vacy. However, DP-SGD requires the injection of an amount of noise that scales with the number of gradient dimensions, resulting in large performance drops compared to non-private training. In this work, propose random freeze which randomly freezes progressively increasing subset parameters and results sparse gradient updates while maintaining cally prove the convergence of random freeze and find that random freeze exhibits signal loss and perturbation moderation trade-off in DP-SGD, Applying ran- dom freeze across various DP-SGD frameworks, we maintain accuracy within the same number iterations while achieving up to 70% representation sparsity, which demonstrates that the tradc-off exists in a variety of DP-SGD methods. We further note that random freeze significantly improves accuracy, in particular for large networks. Additionally, axis-aligned sparsity induced by random freeze leads to various advantages for projected DP-SGD or federated learning terms of computational cost, memory footprint and communication overhead.
increasing accuracy. We theoreti-
INTRODUCTION
The success of machine learning, and deep neural networks in particular, combined with ubiqui- tous edge computation and digital record keeping, has led to a surge in privacy sensitive learning applications. Internet-scale data promises to accelerate the development of data-driven statistical approaches, but the need for privacy constrains the amalgamation of such datasets. 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 can also be exposed through releasing the model trained local dataset (Fredrikson et al. 2013) Shokri al. 2017),
reconstructed when gradients generated during training are shared (Zhu et al. 2019 Geiping et al.,
2020
Zhu & Blaschko 2021).
To address these issues, many applications of machine learning are expected to be privacy- preserving. While differential privacy (DP) provides a rigorously defined and measurable privacy guarantee for database operations (Dwork & Roth 2014). it also contains intriguing properties, such as robustness to post-processing and composability. which enables conveniently computing an over- all privacy guarantee for several DP components. Differential privacy defines privacy with respect to the difficulty of distinguishing the outputs. For pair of neighboring databases X, X' E X, i.e. X can be obtained from X' by adding or removing element.
Definition 1. A randomized mechanism M X + R is (e, (c.)))ifiereenialll private, if for any subset of ouiputs S C R it holds that:
Pr(M(X) E EJ Pr(M(X') E 5] +
common paradigm for a randomized mechanism M in deep learning is perturbed gradient descent:
M(X) f(X) + N0, (N00, 2)
In this work only consider approximate differential privacy which includes the 5 term.

---

Under review as a conference paper at ICLR 2022
. The isotropic Gaus- sian distributed noise EDP ~ (O, Sz0² is calibrated to f's sensitivity S7. which is the maximal l2 distance (X) - f(X)Il, i.e. the maximal l norm of gradient among all individual exam- ples. X' could be batches of training data, for instance, in our experiments they are batches of image-label pairs. The factor a is a noise multiplier controlling the strength of the privacy guarantee: higher o leads lower privacy loss. Differentially private stochastic gradient descent (DP-SGD) up- per bounds the certainty of connecting data with arbitrary subset of gradient space using the privacy budget variables (e, ().
where f X' - R computes aggregated gradient given database X or X'.
Bassily et al. 2014) show that in a convex setting, DP-SGD achieves excess risk of Ō ((vd, Vd/ne) for a model w I that minimizes the empirical risk Σ ((w,,;) 2;), where 21, .2...., In are drawn from X. While we show that in non-convex general setting, the mean square error (MSE) of perturbed gradient 9 9 + EDP is between Q(d) and ((dd)) by assuming the gradients follow Gaussian distribution:
Theorem 1. Assuming that the gradient is drawn from N(Vw: w. E), centered at the true gradient Ve and with respect the covariance matrix E whose trace goes linearly up with dimension d. The MSE of perturbed gradient ğ = + ÉDP can be lower bounded by:
MSE 2 TH + do?).
(2)
from which we conclude that the lower bound on MSE is between linear and quadratic in d in practice. For the proof and conclusion, refer to Appendix A In terms of deep learning, d is large number for modern network architectures, this can lead to a significant increase in error.
The work Afadb et al. (2016) proposed to clip the gradient of each individual example in l norm to preset bound C, i.c. 9 = g min(1, (1, [Tllaa) They then apply this clipping bound to compute the variance of Gaussian distributed noise. The Gaussian noise mechanism can be expressed as:
M(D)= == f(D) + (0, C2 -O²1a).
DP-SGD with gradient clipping has been empirically verified to be effective as it constraints the amount of injected noise by setting a small clipping bound. However, clipping removes the mag- nitude information of the gradient and therefore results in gradient estimation bias. Setting a small clipping bound with a deeper network will not result in better performance. The expected MSE of the perturbed gradient is only constrained to O(d), the impact of perturbation is non-negligible in practice. The biggest network where this strategy is successfully applied so far is CNN with Tanh proposed by PPapernot et al. (2021). which reaches 66% accuracy on CIFAR1O in low privacy regime and is regarded as the state-of-the-arr (SOTA) end-to-end network with DP-SGD. To address this curse of dimensionality, most recent works concentrate on gradient dimension reduction.
1.1 RELATED WORKS
Abadi et al. (2016) propose to pretrain a network on an auxiliary dataset and then transfer the feature extraction, that only linear classifier will be replaced and trained on the private data. Tramer & Boneh (202T) adopt ScatterNet (Oyallon et al., 2019) to extract handcrafted features and train a relatively shallow network based on the features. Both work decrease d by excluding the majority of parameters during DP learning, which also constrains the learning ability of network.
Inspired by the empirical observation that the optimization trajectory is contained in lower- dimensional subspace (Vogels et al. 2019) Gooneratne et al.) 22020 Li et al. 2020), a line of work intend to reduce d by exploiting the low-rank property of the gradient while considering privacy. Several recent works (Zhou et al. [202T] Yu et al.) [021a]] Kairouz et al. 202T) project the gradient into subspace which is identified by auxiliary data or released historical gradients. In practice, they use the power method to search for the subspace. The computational cost of running the power method and projecting gradients as well as the memory footprint of storing the projection matrix limits the application of such method to large models. Zhang et al. (2021) target an NLP task where networks are heavily over-parant wver-parameterized and gradients are extremely sparse, and propose to adopt DP selection to privately select top-k significant gradients for optimization. Also targeting an NLP task, Yu et al. (20216) propose a low-rank reparameterization of weights via released historical gradients.
2

---

Under review as a conference paper at ICLR 2022
In addition to the aforementioned works, McMahan et al. 2017 y Yang et al. (2019) and others study how to incorporate differential privacy in collaborative training. e.g. federated learning, in the interest of protecting the privacy of participants. Federated learning also suffers from large d, it is usually deployed on edge devices and local models are periodically synchronized, so communication cost becomes expensive both in time and power usage (Pathak al. 2012). Therefore, gradient dimension reduction can have large benefits in federated learning involving power-restricted edge devices. A line of work studies how tackle this issue by utilizing the low-rank property (Shokri &
Shmatikov 2015 Yang et al. 2019 Liu et al. 2020).
1.2 OUR CONTRIBUTION
In this work, demonstrate axis-aligned gradient dimension reduction method. Our work is orthogonal to previous works, we do not extract any characteristic information of the gradient or model. approximate the gradient from subspace. Instead, randomly zero-out a fraction of the gradient during training and force the gradient to have a sparse representation. We provide a theoretical study this strategy and reveal that random freeze exhibits trade-off between signal loss and perturbation moderation in DP-SGD. We remark that our theory and approach do not nec- essarily rely on the low-rank assumption. To the best of knowledge, we the first to study this trade-off in DP-SGD and provide an effective approach.
We use the benchmark CIFARIO (Krizhevsky 2012) which is date standard benchmarking DP learning and show that well implemented random freeze exhibits various advantages and can be widely applied. More specifically, we maintain accuracy when we adapt projected DP-SGD with random freeze, while we reduce the computational cost and memory footprint induced by the power method and projection. Applying it to various frameworks, we achieve a high representation sparsity of gradient without loss in performance. Federated learning can take advantage of the resulting sparse representation to reduce communication costs. We further note that the random freeze strategy improves the accuracy of large networks, which we demonstrate with the SOTA End-to-end CNN proposed by Papernot et al. (02I).
ANALYSIS OF RANDOM FREEZE
In this section we theoretically prove that to certain freeze rate r, DP-SGD with random freeze will converge if the approach without random freeze can converge. Then we investigate the trade- off between signal loss and perturbation moderation induced by random freeze. Furthermore, we empirically demonstrate benefits of applying random freeze from the perspective of the gradient distribution.
2.1 CONVERGENCE RATE OF DP-SGD WITH RANDOM FREEZE
Let C be the objective function L(w) == MEgwa[Le(us x)}. m E {0, 13d the freeze mask and the freeze rate, we randomly draw rp indices and these positions in the mask to 0 and others to 1 so that mm = (1 r)d. We assume an oracle telling the true gradient Vw and individual gradient St.j = Vw + (xx), where & is independent gradient deviation with zero mean. Let p be the distribution of & For random freeze the sparse gradient is L', = Vwl + ((x)), where + (z4). Denote for DP-SGD the averaged clipped gradient of B samples Gt. := B E, St.i min(1, (1, [Iee.T] ). and for DP-SGD with random freeze ÿ. Σ, Pl min(1, Ilo...).. We have for DP-SGD with random freeze the following inequality:
Vw, O Vw, ((()))
Theorem 2. Assume G-Lipschitz smoothness of V Vw such that || [| - Vwull S Gl| wzll Consider an algorithm with clipping bound C. learning rate r and choose symmetric probability such that:
density distribution 5(-) satisfying P.(E.) = p.(-E.) VE, E Rdd Then 3x 2 1
T Perro (11&ell < t=1
C (Vv. <
A 7T +1
T
Σ t=l
Em [be)), (4)
T
3

---

Under review as a conference paper at ICLR 2022
where we define b, : (VW'i, sh: min(1, - ()(((())) PI(E))dEE Pe, p% are corresponding projected distribution, and define Ac == E[C1 min [(w)], Ao = GC 2 ADP = C²
lls...
2B
((Ww)) min(I]Vw,lll ) The proof can be found in Appendix B
When no freeze r O. i.c. m is a vector filled with value 1. Note that K for r = 0, we can obtain the inequality 4 in the following form:
T Pe PPrri.(lEEll (VVVV.)))
+ + ADP) 77
A
bt
(5)
T
which describes DP-SGD without random freeze. Chen al. (0220)) argue that by tweaking it possible to bound Pe.-p, away from zero which means the l.h.s. is proportional to |/Vwe or [|Vi,, each iteration, while letting the convergence bias term -b; tend be small as Pt is approximately symmetric. They then prove that by setting a certain learning rate the r.h.s. diminishes to zero, so the network under DP-SGD can converge. Adapted from that, we see the r.h.s. of inequality f random freeze, EE,,.. [by] also tends to be small as P. is expected to be approximately symmetric if Pr is. Additionally. 1/x will not be large as along as r not extremely close to 1. So with the same learning rate and y adapted for DPDSGD without random freeze, the r.h.s. of inequality 4 will also tend to zero, which proves the convergence of DP-SGD with random freeze.
Epoch 25
Epoch: 50
Epoch: 80
Epoch 25
Epoch: 50
Epoch: 80
0.00
0.5
-0.55
0.4
DNGE
0.3
-0.15
-0.5
3.4
0.6
1.0
0.6 Freeze rate
Freeze rate
(a) As
(b) AMSE
Figure 1: (a): Signal loss of no freeze minus random freeze. (b): MSE of gradient estimation of no freeze minus random freeze.
2.2 TRADE-OFF BETWEEN SIGNAL LOSS AND PERTURBATION MODERATION
From Theorem 2 see that by applying random freeze the injected noise term App is reduced by 1- < 1 while other terms could be increased by 1/K. From an operational view, random freeze moderates perturbation while removing some signal. Therefore, the convergence rate of random freeze is trade-off between signal loss and perturbation moderation. Consider that ApP proportional to the number parameters which large for neural networks. might be worthwhile to remove some signal while moderating perturbation. To investigate this question, consider the MSE of gradient estimation of DP-SGD with and without random freeze iteration l:
Co
MSEpP == Ell Vil - (g (DP) B(l
gl
(6)
B2
C2o2d
MSERF B[[ Vul (g + Enp)
E B
3 (1 -r)
B2
Two statistics of interest are: First, the difference signal loss As [[] g|l -Ell/ gll2). DP-SGD induces signal noise due to clipping bias while random freeze has additional loss due to freezing. Second, the difference of MSE ÂMSE := MSEPP M MSERF which implies the trade-off between signal loss and perturbation moderation. We train the End-to-end CNN with 80 epochs on a privacy budget (s = 7.53, 5 = 10-5) and measure these two statistics with respect to empirical distribution
the end of three training stages (see Figure []. The result shows that although random freeze has more signal loss as the freeze rate increasing, due to a large amount of injected noise, MSE of gradient estimation with random freeze is clearly lower. The result reflects
4

---

Under review as a conference paper at ICLR 2022
that injected noise is dominant during optimization. Combining this with Theorem 2 it shows the possibilitty that we achieve better convergence by removing some signal while mitigating noise. For example, in addition to taking advantage of noise mitigation, can also raise the noise to SDr so more iterations T the same privacy In section 4 we will demonstrate that
that [|]] O DDell matches Eil II]- This allows
budget, which also implies better convergence by Theorem 2 when d is large, which implies large ADP, we can improve the performance by applying random freeze.
2.3 A GRADIENT DISTRIBUTION VIEW OF RANDOM FREEZE
We also observe the potential benefit of random freeze from the perspective of the gradient distri- bution. Compared to no freeze, random freeze leads to less clipping bias and gradient distortion, as shown in Figure
adopt the same clipping bound for random freeze and no freeze. As fewer dimensions contribute to the norm computation, random freeze reduces the clipping probability and therefore alleviates clipping bias (Zhang et al., 2020). We also note that the norm sparse gradi- ents not equally scaled down, weak gradients spontaneously become larger during training, which mitigates the distortion of gradients due to perturbation, while the perturbation of random freeze is already moderated compared no freeze.
Epoch:
10
10"
10.2.
1017.
Auu www
Epoch: 20
Density
10
Freeze rate
10
10
0.9
Epoch: 40
10
10
10"
10
10a
Norm
Figure 2: Gradient norm distribution of DP-SGD with without the random freeze strategy. The vertical dashed line indicates the clipping bound. With the random freeze strategy, later epochs the variance of the norm magnitude decreases. A lower number of high-magnitude gradient norms implies less clipping bias, while the decrease in low magnitude gradient norms implies a higher signal-to-noise ratio of the perturbed gradients. The plots overlap in the subfigure corresponding to the first epoch as the freeze rate is 0 and the networks are initialized equally. The freeze rate at the 20th epoch is 0.45 and reaches 0.9 the 40th epoch. Note that both axes are in log scale.
TECHNICAL DETAILS
Algorithm outlines our approach. Since the coordinates that have been selected to freeze do depend on the dataset, their indices can be exposed or transferred in clear text and do not lead additional privacy loss the dataset. We apply random freeze to optimization with SGD with or without momentum. In case of non-zero momentum, the velocity is updated with the sparse gradient as normal. That means, parameters that have been frozen can still updated long as their velocity has not decayed to zero. Next, we discuss the properties and implementation details of random freeze, compare different variants and provide insight into the strategy.
GRADUAL COOLING
We find that if initiate the training with constant freeze rate r, the network converges slowly and performs poorly when the privacy budget has been fully consumed. The reason is that in the early stages of training, the network is far from its optimal position, it is better to let all parameters stay
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Random freeze
Input: Initialized parameters: We; Loss function: Iterations per epoch: Epochs E; Freeze
rate: r*; Cooling time: e"; Clipping bound: C; Momentum: Learning rate
for e O-.. do
r(e) = r" minn(T-T..)
Randomly generate a freeze mask m E {0, 13d subject to Σ m = d (1--r(r))
for / = 0..7-/ do
For each z, in minibatch size B, compute Io (2x) Ve(we, my);
Partially zero out each gradient (x,))) m gr (z,);;
Clip each individual gradient 9e (2x) (xx.) min(1, [
Add noise 9: = B ( (x;) + m @ (0, c²)2
Update 2t+1 2t + 9h, W1+1
end end
active. we present gradual cooling, which is inspired by the gradual warm-up of the learning rate adopted for non non-privacy cett--riacy-peeeeeeee preseeving training (Goyal et al. 2017). Gradual cooling linearly ramps up the freeze rate from 0 to r* within predefined cooling time and stays at r* for the remaining training epochs, i.e. r* .mim( min((-_111)
3.2 PER-ITERATION RANDOMIZATION VS. PER-EPOCH RANDOMIZATION
Although conducting random freeze leads to negligible additional computational cost and memory footprint, we find that it is sufficient generate freeze mask per epoch, while re-randomizing the freeze mask at each iteration slightly decreases the performance. As we have shown in Section 2.2 noise dominates throughout training. Therefore, by per-iteration randomization, parameters have been perturbed at this round could be frozen during subsequent iterations and stay biased. By con- trast, per-epoch randomization lets the selected parameters update for one epoch, allowing the noise of multiple iterations to be averaged out.
Another strength of per-epoch randomization is that for one epoch there are certainly (1 (I-r)d pa- rameters updated, which is favorable in collaborative learning schemnes communication cost is a significant issue, and data are not transmitted every iteration. While for per-iteration random- ization, the cumulative number of updated parameters depends the freeze rate r and iterations between two communication rounds, resulting in higher communication overheads than per-epoch randomization.
Non-privalely Ranked Freeze
Random Freeze
Ranked Freeze
# parameters
10 10*
10
10
10
10
100
# of times parameter is frozen
Figure 3: Histogram of the number of parameters versus the number of times parameter is frozen. We present non coi-privately ranked freeze, i.e. ranking after excluding noise, for comparison.
3.3 RANDOM FREEZE VS. RANKED FREEZE
Based the observation of the low-rank property of gradients (Vogels al. 2019 Gooneratne et al.
2020 Li et al. 2020). freezing the parameters with respect to the mean of past perturbed gradients instead of random draw might be helpful: First, taking the mean of past perturbed gradients will

---

Under review as a conference paper at ICLR 2022
average out zero- mero noise. Second, the magnitude of the gradients is diagonal approximation to the principal components and may be indicative of a useful working subspace. We therefore consider ranking the dimensions of the gradient by their magnitude and freezing the smallest ones.
However, empirical results do not match these intuitions. Comparing Table with Table 4 ranked freeze performs similarly to random freeze. We further find that ranked freeze is itself inherently random as the ranking is dominated by Gaussian noise. To demonstrate this, we run random freeze and ranked freeze] on End-to-end CNN for 100 epochs, then statistically analyse the distribution of how many times a parameter is frozen. The result shows the equivalency between these two strategies, which implies even averaging the perturbed gradients over a full epoch cannot sufficiently mitigate the noise added in gradient perturbation (see Figure B). This result also reflects that even in a low privacy regime, noise has significant impact throughout training.
90
60
50-
50-
50
Accuracy (%)
Accuracy
60
Accuracy
40
30-
30
30
μ:: 0, C:
0.9, C:
C. C:
H: C: 0.5
20
C.
U.O.S. C.
μ:
μ: 0.9, c:
μ::
10
μ:: 0.98, 0:0.1
10-
#: 0, 0:0.11
I:: 0.98, C:
20 Epoch
30
10
30
40
10
30
Epoch
Epoch
(b) μr = 0.9
(c) C 0.1
Figure 4: Test accuracy with respect to various clipping bound and momentum pairs. The network
architecture is End-to-end CNN, and the privacy budget is (8 3, = 10 We adjust the clipping
bound C and momentum μ based on their optimal values C 0.1, p = 0.9 (Tramer & Boneh
2021 (a) is adjusted with respect to an inversely proportional scaling rule I- 1-0.9 = 1, (b) has momentum fixed j = 0.9 and varies the clipping bound, (c) has clipping bound fixed to C' = 0.1 and varies momentum. These figures demonstrate that the inversely proportional scaling rule can achieve good performance, otherwise the network performance is degraded. We also observe that no momentum l = 0 results better performance, probably due to less clipping bias induced by higher clipping bound. We find out that this rule is relatively general and independent privacy level. For experiment on low privacy budget (a = 7.53, 8 = 10 $), refer to Appendix
3.4 INVERSELY PROPORTIONAL SCALING RULE FOR ADJUSTING THE CLIPPING BOUND AND MOMENTUM
Previous works commonly adopt first order momentum in the optimization, because momentum can alleviate oscillation and accelerate gradient descent (Sutskever al. 2013). As a result, it is believed reduce the number of iterations of training and therefore achieve less privacy loss. However, for privacy- presecrirr training. momentum will also exaggerate the additive i.i.d. Gaussian noise by incorporating current and all historical noise. For instance, using the Pytorch (Paszke et al. 2019) implementation of SGD, the velocity update can be written as: 0++1 = μ - It++1, where Ht denote perturbed velocity, momentum and perturbed gradients, respectively. Using the expression of one step noise in Equation 3 and denoting by ú, the velocity after separating the noise, we have - La). After many iterations, the sealar approximates 1 -N C² o² d²I.). Pulling the clipping bound C' out geometric series, i.e. Ut-1 61+1 I-p
Vt+11 - 0t+1 = (1+ +..+++))) +u")+===++.++"")N(( -N) C² _2_g2
and forming the noise as I- (0, I²),), we present an inversely proportional scaling rule for adjusting C and 1 - H4 i.e. with other hyperparameters fixed, networks trained with same value of the ratio T- perform similarly (see Figure 4). Our conjecture that the inversely proportional scaling rule ensures the same amount of injected noise.
C
Foor implementation details of ranked freeze, refer Appendix
7

---

Under review as a conference paper at ICLR 2022
It is worth noticing that the inversely proportional scaling rule is general and amenable to no freeze and random freeze. Tuning hyperparameters in the context of privacy perseeringg training has been observed to be brittle. This rule helps reduce the tuning workload.
4 EXPERIMENTAL RESULTS
Privacy budget According to Definition we have that each iteration of training is (E, (5, differentially private with respect a batch of training data, while shuffling and partitioning the dataset into batches implies that each iteration is (O(ge), qō) ged-differentiallyy private with respect to the full dataset according to the privacy amplification theorem (Balle et al. [2118] Wang et al. 2019). where q = B/N, B is the batchsize and N is the size of dataset. To track the cumulative privacy loss over multiple training epochs, we adopt Rényi differential privacy (Mironov 2017). which is more operationally convenient and quantitatively accurate.
Advantages of sparsity Projected DP-SGD induces a significant additional computation cost by running the power method and projecting gradients into and out of subspace. For the power method, the basic operation is W WWTVV W E _ denotes sample gradients, V E Rdd denotes eigenvec- tors, the computational cost is (dbs). Similarly, for projection V X; X R denotes original gradients, the computational cost is (ddn).. Applying random freeze, a random selection of rows of X are deleted, while corresponding rows of V, W be removed as no information of gradient exits in that subspace. We note that 6, 8 might also be able to be reduced. Overall, the computational cost is between O r) and O(1 )) Another issue of projected DP-SGD the memory footprint of V. Saving sparse V by random freeze can be achieved by storing non-zero values and indices of zeros. The cost of indexing is logarithmic of the number of parameters, consider that 1og2109 < 32, we can decrease the memory footprint by removing a single 32 bit float gradient. Communication overhead can similarly be reduced. We note that random freeze uses the same mask during one training epoch, which could contain multiple groups of eigenvectors and communication rounds. Therefore, the cost of indexing is negligible: communication overhead and memory foot- print are Ó(1 - r). Further, we define the total density as the total amount of non-zero gradients by random freeze over the total amount of gradients by the original dense representation to reflect these advantages of sparsity.
Our experiments are implemented in the Pytorch framework. To compute the gradients of an in- dividual example in a minibatch, which is required for gradient clipping, we use the BackPACK package (Dangel et al., (2020). The privacy loss of multiple iterations has been tracked with Opacus We use the benchmark CIFAR 10, which is to date standard in benchmarking DP learning. Our code is available for download from http: httt::://aooymm /anonym
zed. for. revi ew/
To validate the reliability of random freeze, we conduct experiments on several SOTA networks cross different frameworks, including End-to-end CNN (Papernot al. 2021): Handcrafted CNN (Tramer) & Bonch] (02I) which incorporates ScatterNet (Oyallon et al. (019) as feature extractor; Gradient Embedding Perturbation (GEP) proposed by Yu al. (2021a) which injects noise in projected gradi- ent; DP- Learning which adopts pretrained network and replaces the linear classifier layer, in particular we use SIMCLR (Chen al., (020a) pretrained on unlabeled ImageNet (Deng et al.) 2009). which has been benchmarked by Tramer & Boneh (202T).
For fair comparison, we run every experiment 5 times then compute the average of best accuracy and the standard error. We do not tune the hyperparameters when adapting the SOTA works with random freeze, instead we adopt the optimal hyperparameters for DP-SGD without random freeze provided in the respective works. Random freeze is applied as follows: if the optimal number of epochs from the previous work is set as e", we linearly ramp up the freeze rate r from r = 0 at epoch 0 r = r* at epoch = e*, i.e. r" -- These straightforward experiments allow us to demonstrate that random freeze is safe add-on in variety of methods. We summarize the performance results in [able and the corresponding total density by random freeze in Table We document the hyperparameters in Appendix
We find that when the network is large, for instance End-to-end CNN has the most parameters among all frameworks, random freeze is able to improve the accuracy. To demonstrate this, further tune the End-to-end CNN. We still adopt the best hyperparameters from the previous work, then first adjust the clipping bound and momentum from (C 0.1, μ 0.9) to (C 1= 0)
8

---

Under review as a conference paper at ICLR 2022
Test Accuracy
Approaches
E-DP
# of parameters
Baseline
Random freeze
Freeze rate r*
End-to-end CNN
7.53
550K
66.9 = 0.4
66.7 = 0.3
0.7
3.0
60.4 0.2
61.1 = 0.2
0.7
Handcrafted CNN
3.0
187K
69.4
69.4 - 0.2
0.6
GEP
8.0
268K
73.5 + 0.4
73.4 0.3
0.4
DP-Transfer Learning
2.0
41K
92.6 0.0
92.7 = 0.0
0.7
Test accuracy of SOTA works before and after adopting random freeze. We maintain the accuracy with high freeze rate. Communication overhead, computational cost and memory footprint of the projected DP-SGD are accordingly reduced as implied by total density in Table 2
Table I:
Total density
End-to-end CNN
Handcrafted CNN
GEP 0.8
DP-Transfed Learning
0.65
0.7
0.65
Table 2: Total representation density of random freeze. This table is aligned with Table
Test Accuracy
Approaches E-DP
Baseline
Our adjusted baseline
Random freeze 70.2 + 0.1
End-to-end CNN
7.53
66.9 1 0.4
69.7 1 0.1
3.0
60.4 1 0.2
63.1 0.2
64.5 + 0.3
Table 3: Test accuracy of End-to-end CNN adjusted with respect inversely proportional scaling
rule and trained with random freeze. Our adjusted baseline performs better than original work while with random freeze further improve the accuracy. Altogether obtain significantly better utility.
with respect the inversely proportional scaling rule proposed in Section 3.4 accuracy. Secondly, we apply random freeze. Similar to the previous experiment we also linearly ramp up the freeze rate r" but then we extend the training for 20 additional epochs at freeze rate r", this help us to improve the performance further. The result is summarized in Table 3 Note that, after extending the training epochs, the noise multiplier a has been increased accordingly to ensure the same privacy budget will be consumed. As result, more epochs without random freeze will decrease the performance. Moreover, we achieve lower total density with higher freeze rate. For hyperparameters, total density and accuracy as a function of privacy loss, refer to Appendix
which leads to better
5 DISCUSSION AND CONCLUSIONS
In this work propose random freeze which is an axis-aligned random gradient dimension duction method. We provide fundamental theoretical study on random freeze and investigate the trade-off between signal loss and perturbation moderation. Although simple to implement, random freeze can be safely (without further tuning) applied across different frameworks and architectures. Even in conjunction with other gradient space reduction methods performance is maintained. With the sparse representation of the gradient update, random freeze can reduce the computational cost and memory footprint of projected DP-SGD. Also, it able reduce the total amount of transferred data in federated learning or other collaborative learning frameworks. Moreover, we significantly improve the performance of SOTA End-to-end CNN using the random freeze strategy and inversely proportional scaling rule that we have proposed. We note that the computational cost of the random freeze procedure is negligible. Therefore we believe that random freeze can be incorporated as a general method in DG-SGD. and expect random freeze to exhibit strong improvements DG-SGD is adapted to larger and deeper networks in the future. We also hope this work can shed light on gradient dimension reduction in DP-SGD and motivate further research in this direction.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. Proceedings Anmual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 464-473 2014. 2014.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong supe-supee learners. In Advances in Neural Information Processing Systems 33, 2020a.
Xiangyi Chen, Steven Z. Wu, and Mingyi Hong. Understanding gradient clipping in private SGD: A geometric perspective. In NeurlPS, 2020b.
Felix Dangel, Frederik Kunstner, and Philipp Hennig. Backpack: Packing more into backprop. In International Conference on Learning Representations, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255, 2009.
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 confi- dence information and basic countermeasures. Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer 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-efficient on-device training of deep neural network. In /CASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3017-3021, 2020.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. 06 2017.
Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension in- dependent private erm with adagrad rates via publicly estimated subspaces. In Proceedings of Thirty Fourth Conference on Learning The- ory, volume 134, pp. 2717-2746, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 2012.
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 Data Mining (SDM), pp. 190-198, 2020.
Ruixuan Liu, Yang Cao, Masatoshi Yoshikawa, and Hong Chen. Fedsel: Federated SGD under local differential 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.), Database Systems for Advanced Applications, 2020.
10

---

Under review as a conference paper at ICLR 2022
Arak Mathai. Storage capacity of a dam with gamma type inputs, Annals of the Institute of Statistical Mathematics, pp. 591-597, 1982.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-Effiicin Learning of Deep Networks from Decentralized Data. In Proceed- ings of the 20th International Conference on Artificial Intelliencce and Statistics, pp. 1273-1282, 2017.
Iyya Mironov. Rényi differential privacy. 2017 IEEE 30th Computer Security Foundations Sympo- sium (CSF), 2017.
Panagis Moschopoulos. The distribution the sum of independent gamma random variables. An- nals of the Institute of Statistical Mathematics, pp. 141-544, 1985.
P.G. Moschopoulos and W.B. Canada. The distribution function of a linear combination of chi- squares. Computers & Mathematics with Applications, pp. 983-386, 1984.
Opacus. Opacus PyTorch library. Available from composuuuu.
Edouard Oyallon, Sergey Zagoruyko, Gabriel Huang, Nikos Komodakis, Simon Lacoste-Julien, Matthew Blaschko, and Eugene Belilovsky. Scattering networks for hybrid representation learn- ing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tem- pered sigmoid activations for deep learning with differential privacy. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 9312-9321, 2021.
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 Vitooo Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, gigh-peffrmance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. 2019.
Abhinav Pathak, Y. Charlie Hu, and Ming Zhang. Where is the energy spent inside my app? fine grained energy accounting on smartphones with eprof. Proceedings of the 7th ACM European Conference Computer Systems, EuroSys 12, pp. 29 42, 2012.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 909-910, 2015.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks 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 initial- ization and momentum deep learning. In Proceedings of the 30th International Conference on Machine Learning, pp. 1139-1147, 2013.
Florian Tramer and Dan Boneh. 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 Gradi-
ent Compression for Distributed Optimization. 2019.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled renyi differential privacy and analytical moments accountant. Proceedings of the Twenty-Sccond International Conference Artificial Intelligence and Statistics, 2019.
Qiang Yang. Yang Liu. Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 2019.
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 Represen- fations, 2021a.
11

---

Under review as a conference paper at ICLR 2022
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Yan Liu. Large scale private learning via low-rank reparametrization. In International Conference on Machine Learning (ICML), 2021b.
Huanyu Zhang, Ily Mironov, and Meisam Hejazinia. Wide network learning with differential pri- vacy, 2021.
Jingzhao Zhang, Tianxing Hc, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Rep- resentations, 2020.
Yingxue Zhou, Steven Wu, and Arindam Banerjee. 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, In International Conference Learning Representations, 2021.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, 2019.
A MEAN SQUARE ERROR OF GRADIENT IN DP-SGD
Theorem Assuming that the gradient is drawn from (VW,, E), centered at the true grudient Vw and with respect to the covariance matrix E whose trace goes linearly up with dimension d. The MSE of perturbed gradient g = + EDP can be lower bounded by:
MSE 2 [1 + do²).
(2)
Proof. Assuming oracle can tell the gradient Vw given a network with parameters w Rd, while the individual gradient can be seen as drawn from the Gaussian distribution centered at Vw with respect to the covariance matrix Σ, i.c. 9 ~ (VW,,, E). Denote Eg as gradient deviation, i.c. Eg Ww, the perturbed gradient ğ in SGD can be expressed as:
V + Egg EDp
(8)
and the mean square error of perturbed gradient is:
MSE = + 2EJEEP + <DCDPP
(9)
Since for and & are independent and plugging the definition of injected noise. i.c. DD
N' max(gT g)o= Ia), into Equation
we have:
MSE [[[ 5 + E(p
(10)
Tr|E] + do mmax (g 9)]
(11)
Tr| + do 2 [max w + Vu [ww]
(12)
2 Tr[E] + do do E[maxx(]xx))
(13)
where equality can be achieved when the network converges to stationary point, i.c. Vw- +
Applying spectral decomposition to Σ, we obtain Q AQ Σ. where Q is an orthonormal basis and A is diagonal matrix of cigenvalues of E. Denote by z random vector drawn i.i.d. from normal distribution, we can further derive:
CT ~ TT 2 =TQTAQ= 2 Az
(14)
As random variable with respect to the same distribution leads to the same expectation, plugging Equation [4]nno Equation 13 we have:
MSE Tr[E]
+ do d E[maxx22 2T Az)]
(15)
1
Tr
1 + d max
A
(16)
Tr
1
1)
T>[
1 do2E max
Tr|A] AT
(17)
12

---

Under review as a conference paper at ICLR 2022
Since =T X1 222 +... Adep: 2 NO0 1), have:
1 Ty(A]
A=
TY(A] Σ
Gamma (
(18)
2' 2X,
So far either the exact PDF of Gamma distribution summation can only be represented with (an- other) series of gamma distributions (Moschopoulos) 1985 Mathai 1982), or its exact CDF has series representation (Moschopoulos & Canada 1984). For the convenience of further derivation
of the expected maximum, we use the Welch-Sateen weleh-Satterhwwite approximation which provides a certain Gamma distribution:
(1 2' 2X
(A TM(A} 2Tr(A3} 2Tr(A?}
Σ Gamma
Gamma
(19)
Tr A
Tr[A]
It TP 2TH(A3 2TH(A?)
Gamama
(20)
(T (P (
). While (2Th(A2)> 2Tr(A2)
Denote M,, max(11, F2, ... In), where 2; is drawn from Gamma
Probability density function
40-
20000
15000
10000
20
5000
0.90
0.95
1.00
1.05
1.10
Figure 5: series of Gamma distributions with the form Gamma (ke, k))
from the Cauchy-Schwand inequality, we have:
(Lu, (ia)(A)) & (Ia, Ia) (diag[A}, (Aa)(A))
(21)
[+ < d. dT[AA]
(22)
Tt 2 d 2 Tr[A?]
(23)
(A) 2TT(A7] Figure
Denote k Gammaak, k).
illustrates the PDF of Gamma distribution with parameters
As A becomes large, the distribution becomes more concentrated, and we have the following in- equality:
M = max(2 (1) (1) =((2),, x Gammal TA2 TH
2TT(A2} 2Tr(A
M( max(2) (2) (2)
(2)) x
Gammal
d d
2' 2
EiM > B >
E
x
(2) =
(24)
13

---

Under review as a conference paper at ICLR 2022
Substituting inequality 24 back into Equation 17 have:
MSE 2 [1
+ do²).
(25)
The proof is completed.
We note that Tr[ is the trace of a d-dimensional covariance matrix. In the extreme case that XT, this will scale linearly in d, while the opposite extreme of a rank deficient covariance matrix, the trace is constant in d. Thus, in the former case
MSE 2 Ad + Ao2
(26)
while in the latter we have
MSE 2 x Xo d,
(27)
which leads to conclusion that the lower bound on MSE is between linear and quadratic in d in practice.
B THE CONVERGENCE RATE OF DP-SGD WITH RANDOM FREEZE
Lemma 1. u, B EE Rd are too arbitrary vectors, m is {0, 1)dh random mask independent from u, v, and subject to Σ m (1 r.d, where denotes the freeze rate. We have the following expectation:
[m @ w\} (1 (u,
(28)
Proof.
E 3 u. w>] = E[(m @ u, v}},
(29)
Σ B(m m: [u.ue))
(30)
(1 r) E[ n/}.
(31)
The proof is completed.
n
Corollary 1.1. Following the notation of lemmall 7 we have the expectation below:
Bi(m @ u, m v)] = ( (),
(32)
Proof.
B[(m O., v)]
[m 2 u, v}},
(33)
P8
E w)}
(34)
The proof is completed.
Lemma 2. u E IRd is an arbitrary vector, m is a {0,1) random mask independent from u and subject Σ m (1 r)d, where denotes the freeze rate. We have the following inequality:
E|llm O ull] 2 (1 -r]]
(35)
Proof.
Blllm @ alll
|| Elll o u|][[||],
(36)
Elllm u| u|l?],
(37)
|| ||
(1 ku, 1)),
(38)
|ul
(1 r) [w|]-
(39)
Equality is taken when 0. The proof is completed.
n
14

---

Under review as a conference paper at ICLR 2022
Theorem 2.
Assume G-Lipschitz smoothness of Vw such that Vwi+1 - -well - G w well ||
Consider an algorithu with clipping bound C. learning rate n and choose a symmetric probability density distribution p(-) satisfying Pr(Ee) = p.(- VE, R. Then 3x 2 1-1 such that:
T
T
Pe (llsell < (VV(va)) S ( 7T
1 A
+rAc + +1-r+(1 dp
Bm [e)) (4)
4
T
Proof. Denote the injected noise at each iteration EDP B 2, where is drawn from C0 Ia), follow from the smoothness assumption, we have:
G 2
10-1- L411 S C, (Vw,, wh+1 - -w)) + || - =w,1?
(40)
G?2
= Li - (i--(Vurr,6 9c + 3 (DP) +
1l9 + + @ EDPll
(41)
2
G72 ll.. + @ EDPl?
= - 91) (Vur, m 2 EDP)
(42)
Taking expectations on both sides and rearranging, we have:
G7
(V 9.91 - E[c, [141] - E(,,,, m O EDP)
+
Bllg: + +m o (Drl1%
(43)
7
2
G7
P8
Bic: f441 - (1 - | V W/ EDr)
+
Bllla + m o Eprll)
(44)
2
G7
Blci C441l - -0+
[ | + Elll O EDP - 0),
(45)
7
2
Gy [Bllge [| + (1 C2o²d
Blc C++1] +
(46)
2
132
1
Gy (C2 + (1-r) 0 C²o²d
$ B[c, - fit1l +
(47)
2
B²
Now focusing on the l.s.s,, we have:
B((Ver, 9c3] (Vu,, Elūr}
(48)
1 Σ B|m @ ge. ge....imnn min(1, <Vur, B
C
I o gr,il )))
(49)
C
= =E((Vu,, m @ ge. min(1, I| & ge.al M)
(50)
= =m(mm O Vw,, m 3 9e. min(1,
I| @ ge,il })1,
(51)
C (V.l Lh.s min(1, (1,
Em
IIs6 mm
(52)
Em
Beinot /1 (WW/ Hh. min(1, 1T66 mm] + (mel
(53)
where we have defined b, = J(Vwls sixx min(1, To..
C (G(())) - (((E))),E Equation 52 is
achieved because & and m are independent. We note that for any given m. & is still independent deviation with zero mean and (t((()) ( since projection of symmetric distribution to sub- space symmetric. According to Theorem from Chen et al. (2020b), for given m we have the following inequality:
C Egg=pt (VW Ah. min(1, |10%
9 min([| 4
3C )|
mm Per (IEEll
V//Vll (54)
4
15

---

Under review as a conference paper at ICLR 2022
Back to Inequality 47 and considering the overall T steps, we have:
T
1
Blc - Cr) _ (0=+
Ca
B[(Vw, w. ai)l - 7T
(11-))
(55)
2
B²
7 Ac Ac + (1-r)/ApP,
1
(56)
where we have defined 4g : E[c1 min [(w)), Ac
GC
ADP =
C² 2B
Plugging
Inequality 54 Equation 53 and combining with Inequality [6
T
C Em P (15/ < 4 (Vu))))VVVV
A 7T
T
+r + 11-
Em [br],
T
T
(57)
where we have defined h( ((Ww)) min(| Vurll, 3C) step with respect to the following cases:
Now we look at the Lhs., and consider each
case 1: ||Veell S C, then P.. (I. Vl/Vl s - 1,
Em E... (11E/11 < - (((VV)
C
2 PErNE (llsell
<
Im (u][V
(58)
Par-ni (llsell
<
|| /|| V Vull9
(59)
4
C
8PJ
Permpe (1Eell <
(1 r) r) wuyl?
(60)
4
C
= - (1--r) (l|sell
[[VV) Vwyll-
(61)
case 2: /ielll > 3 C, consider two events A1: /will S 0 A2: || /uulll
C then we have:
Em [Pst PELMa (IIS/1l < G (V(V))))
C
> P Pamp (11aal < Bm (h( (VVDV(VV
(62)
Parpp (113al (PP(A)(( (1a)))1--/////// (63)
P(A2) C E,E (V'lll)
2 PEIND, (11&:ll < C ((P(A))L-))VVm]] (64)
3 C(1 ([]]-)///.lll. P(Ag)
2 Parnp (11 - (1)--r)
r)) 3 Cl Vwrl.
(65)
C. )/ ((Vw)))) (Vel))/Vell.l
(1 - T) (11E:l1 < 4
(66)
from which we conclude that:
PmiPPt- (llE')l < S VMVVV)VVVVl 2 (1 P& (1lsel
C (/(V)
(67)
4
4
The inequality above implies that 3x 2 1 - r such that:
Em P (11561 < C (V Vwilll = Σ Par-n (11& <
C (VV.))))VVllll
(68)
4
1=1
We note that lifr= O. Plugging equation 68 into inequality 57 we obtain:
T
Perup (1|sell < G (VV Vurll < 41 (1
1 A
B [bx]). (69)
T
T
T
1
The proof is completed.
16

---

Under review as a conference paper at ICLR 2022
It is worthwhile note that the l.h.s. can also be written the general form below and the inequality still holds:
1
-))] Σ Pamp (leall 2C) min( (1-3)// v2 (0,
(70)
T
C RANKED FREEZE
Algorithm describes ranked freeze, the performance is recorded in Table Note that for aggre- gated gradient estimation we also inject noise to gradient estimation g" of frozen coordinates. If not, the coordinates get frozen at the first iteration will receive aggregated gradient estimation as O and never get updated for all the remaining iterations, which will degrade the network. Adding noise to frozen coordinates can give these coordinates a chance to be ranked higher positions, while in turn the coordinates in updating but with low magnitude of true gradient may get frozen in the next iteration.
Algorithm 2: Ranked freeze
Input: Initialized parameters: We; Loss function: Iterations per epoch: T; Epochs E; Freeze rate: r²: Cooling time: et; Clipping bound: C; Momentum: μı; Learning rate Y.
for e = O...EE/ do
gº (0)4:
r(e) = r* min( II 1);
if 0 then
(1)
else
Sort the indices [l....dd] with respect to corresponding aggregated gradient of the last epoch gd- in ascending order then the first d r(e) positions mask to 0 and the rest to 1;
end
for == 0... do
For each v; in minibatch of size B, compute de (2.. Vi(wi,
Partially zero out each gradient gl (x;; = m 3 gr (x:);
Clip each individual gradient De (x;)) = (z:) min(1, [
Add noise Jr E. (x:;) + m @ (0, 22
Update
Ut+1 = + ge, Wt+1 7 g" = g" + (1 + +N C&o +
end end
Test Accuracy
Approaches
E-DP
Baseline
Our adjusted baseline
Random freeze
End-to-end CNN
7.53
66.9 4 0.4
69.7 0.1
70.0 + 0.1
3.0
60.4 + 0.2
63.1 = 0.2
64.6 - 0.1
Table 4: Test accuracy of End-to-end CNN adjusted with respect inversely proportional scaling rule and trained with ranked freeze. We adopt hyperparameters recorded Table p Our adjusted baseline performs better than original work while with ranked freeze further improve the accu- racy, However, we note that ranked freeze performs similarly as random freeze (see Table 3).
D HYPERPARAMETERS FOR TABLE
The term is 10 for all settings. There exist two ways of determining the injected noise scale per iteration: 1. Set the privacy budget and noise multiplier then stop the training when the privacy
17

---

Under review as a conference paper at ICLR 2022
budget is fully consumed; 2. Set the privacy budget and iterations of training then compute the noise multiplier so that the privacy budget will be fully consumed at the last iteration. In this work we refer to the second method when talking about hyperparameters. Hyperparameters There is a minor difference for hyperparameters adopted from Tramer & Boneh (2021). For instance, they set batchsize=1024 for End-to-end CNN, which leads to non-exact batch partitions. We set batchsize=1000 1000 to avoid that and achieve equally good or slightly better baseline performance. Additonally, their hyperparameters of End-to-end CNN are tuned for = 3 and then applied to 7.53, we find out that based on their hyperparameters for batchsize, clipping bound and momentum, setting the number of epochs to 80 can achieve the best accuracy.
listed separately
for each framework, see Table
End-to-end CNN
Ir
Batchsize
Epoch 40
Momentum
Clip
3
1.54
1000
0.9
0.1
7.53
1.10
1000
80
0.9
0.1
Table Hyperparameters of End-to-end CNN adopted from
Tramer Boneh 2021
DP-Transfer Learning
Ir
Batchsize 1000
Epoch 50
Momentum
Clip
Source model SIMCLR
Aux. dataset ImageNet
2.30
0.9
0.1
Table 6: Hyperparameters of DP-Transfer Learning adopted from Tramer & Boneh 2021
Handcrafted CNN
E
Batchsize 8000
Epoch 80
Momentum
Clip 0.1
Input norm
BN norm 8
Architecture ScatterNet CNN
3
5.65
4
0,9
BN
Table 7: Hyperparameters of Handcrafted CNN adopted from Tramer & Boneh (0021)
Gradient Embedding Perturbation
Ir
Batchsize 1000
Epoch 200
Momentum 0.9
ClipO
Clip1
Subspace 1000
Sample gradients 2000
Aux. dataset ImageNet
0.1
Table 8: Hyperparameters of GEP adopted from Yu et al. 2021a
E IMPROVING THE ACCURACY OF END-TO-END CNN
Table includes the hyperparameters and total density of ajusted End-to-end CNN with random freeze. Figure 6 shows the accuracy as function of privacy loss.
Adjusted End-to-end CNN with random freeze
Ir Batchsize
Epoch
Momentum
Clip
Freeze rate 0.9
Cooling time 40
Total density
1.81
1000
60
0.6
7.53
1.18
1000
100
0
0.9
80
0.58
Table 9: Hyperparameters for adjusted End-to-end CNN with random freeze
18

---

Under review as a conference paper at ICLR 2022
Method: Adjusted Baseline
Baseline
Random Freeze
Accuracy (%)
50-
40-
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
3.0
Figure 6: Accuracy as a function of privacy loss. We run five experiments and computes the mean value. The result shows that random freeze outperforms the baseline and adjusted baseline in all high privacy levels.
INVERSELY PROPORTIONAL SCALING RULE
We include here an additional experiments of inversely proportional scaling rule on low privacy budget (see Figure 7
60-
Recuracy
Accuracy
Accuracy
40-
Moris 0.3.3,
30
U: 0.5. 0.0.5
It 0.9, C: 0.5 Ii 0.9 C: 0.1
J: U.S.S. C:0.1
ji n.8. 0:
20
ji n.9. 0:0.1
0.0.9,, C:0.01
0.9; C: a.0
0,99 C.O.1
0
20
80 80
20
40
60
15
0
Epoch
Epoch
Epoch
(b)
0.9
(c) C = 0.1
Figure 7: Test accuracy with respect to various clipping bound and momentum pairs The network
architecture is End-to-end CNN, and the privacy budget is (e 7.53, 8 = 10-3). We adjust clipping bound C and momentum μ based on their optimal values C = 0.1, /z 0.9 (Tramer & Bonch 2021 (a) is adjusted with respect to an inversely proportional scaling rule I- 0.9
0.1
(b) has momentum fixed = 0.9 and varies the clipping bound, (c) has clipping bound fixed to C 0.1 and varies momentum. These figures demonstrate that the inversely proportional scaling rule can achieve good performance, otherwise the network performance is degraded. Combining
with Figure 4 see this rule is relatively general and does dependent on privacy level.
G A NUANCE OF RANDOM FREEZE
Gradient clipping is usually the first step need to do after backpropagation in DP-SGD. However. random freeze first zeros out part of the gradient then clips with respect to the respective norm. We note that the strategy of first clipping then freezing appears in recent work (Zhang et al. 2021) as a baseline for comparison, but shows no improvement in performance. We name this strategy posterior random freeze for convenience. For DP-SGD with posterior random freeze, denote the
19

---

Under review as a conference paper at ICLR 2022
gradient 9e B E, @ 96.2 min(1, C
||0 assume G-Lipschitz smoothness, have:
G Bllß: + m o EDPli)
V 3.)
B|c, [++1] - El ① EDP)
+
(71)
2
28
Blcr [(+1] - |
W/ {DP)
Bllā. + m (DPll
(72)
G7
Blfc C(+1] - 0 +
[B || + Elll 3 EDPl - 0),
(73)
2
Elct L(+1] + G7 (1illdd + (1 r)
C²o²d
(74)
2
B
Similarly for DP-SGP with random freeze, we have:
BK 9x)1 | Ce+1]
G7
(B[lgel1)) -r) 2
C²
(75)
B²
We see both methods moderate the perturbation, while E| S Elllg: [|_] but complicated to compare [[(Vu: We, (+)) and [[[ ((WWe,,:)l
9x)]. we leave this for future work. From an operational view, denote St. ④ Dt. min(1, Tm... and Ōt. = @ 9t, min(1, |m we see that (Gr, /t.,)//l3e. ||ل|
C
and | S | S llg..:l. i.e. random freeze and posterior random freeze contain the same direction information of individual gradient, but random freeze retains more distance information. Therefore, we suppose random freeze to perform better than posterior random freeze.
20


Reviews:
[{"review_id": "gxJbjYAXC7", "reviewer": "Reviewer_w3pG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes a dimension reduction technique for private machine learning called random freeze. The basic idea is to randomly select a subset of model parameters and zero out corresponding gradients during the training process. Another contribution is a method to counter the residual effect of added noise when momentum is used for gradient updates.\n\nStrength: \n+ The problem the paper aims to address is an important one. Machine learning with differential privacy is a very active research area, and this paper is a valuable addition to the literature in this field.\n\n+ The proposed method is simple to understand and implement. It is also general and applicable to all types of neural networks. If proven effective, it could be adopted into many existing frameworks to improve the utility private machine learning.\n\nWeakness:\n- The experiments do not sufficiently demonstrate the benefits of the proposed method. As a dimension reduction technique, random freeze could be compared with other similar techniques (e.g., [1]) for private learning in terms of utility. Among the four models used in the experiments, only one (GEP) is a belongs to this category, and random freeze shows a drop in utility (from 73.5 to 73.4, third row of table 1). As such, it is unclear if random freeze can be used in place of, or together with other dimension reduction techniques. \n\n- The proposed scaling of gradient clipping bound is not convincing. The paper argues that, because of the use of momentum in gradient updates, the noise added in previous iterations has residual effects in later iterations. Therefore, the noise scale needs to be adjusted to counter this effect. In the paper, the way to adjust the noise is to use a single constant to scale all noises, and this constant is inverse to the cumulative effect when the number of iterations go to infinity. However, this method for adjusting the noise does not make sense to me. For example, the noise added in the first iteration of training would have much more cumulative effect than the noised added in the final interaction. Also, due to random freeze, fewer and fewer (and different) parameters are receiving updates as the training progress. Thus, while the concern raised by the paper is a valid one, I am not sure the proposed method is the right solution.\n\n- The paper claims (in Section 1.2, Our Contribution) that the proposed method “reduce the computational cost and memory footprint induced by the power method”. However, this claim is neither theoretically analyzed nor empirically demonstrated using experiments.\n\n- Discussion on related work is missing.\n\n\nTypos:\nPage 8 footnote: “There exist too ways…”-> “There exist two ways…”\nPage 9 last paragraph: “It is interested to observe…” -> “It is interesting to observe…”\n\nReferences:\n[1] LoRA: Low-Rank Adaptations of Large Language Models.\n", "summary_of_the_paper": "The paper aims to improve the effectiveness of deep learning under differential privacy. It proposes a simple dimension reduction method that could potentially improve model accuracy as well as mitigate the computational and memory overhead of some previous power method. ", "summary_of_the_review": "This paper has two core contributions: a dimension reduction technique (random freeze) and a method to scale gradient clipping norm. However, as mentioned in the discussion on weakness, this paper does not sufficiently demonstrate the benefits of the proposed methods. Therefore, it does not meet the standard for publication at a top conference like ICLR in my opinion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TopaogEetjm", "reviewer": "Reviewer_rw2E", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this paper has made the following contributions:\n1. This paper proposes a new algorithm of differentially privately training neural networks, which randomly freezes a progressively increasing subset of parameters. This light-weight algorithm can be easily implemented, which dramatically reduces the communication cost while maintaining the accuracy. The idea of gradual cooling and inversely proportional scaling rule are also very interesting.\n2. The paper justifies its statement with detailed experiments.\n\nI think the paper can be improved in the following ways:\n1. First, the idea of the random freezing is not complex. Therefore, I am not sure how much algorithmic contribution it has made. Besides, this idea is not fully novel, at least it has appeared in other papers. For example, in this paper (https://arxiv.org/pdf/2103.01294.pdf), I remember they also used some similar approach in the experiment section.\n2. Personally I am very curious about the performance comparison between random freeze and ranked freeze, which is not provided in this paper. The paper justifies why they do not adopt the ranked freeze in section 2.3, which I do not fully follow. I do not think it is enough to just show they have a similar histogram. Consider the following example, in each iteration, each coordinate is 1 with prob 0.5; else 0. Note that the random freeze and ranked freeze with constant gamma = 0.5 give you exactly the same histogram. However, there is much more information left in the ranked freeze.\n3. Some related work is missing, at least the paper I just mentioned, and this paper (https://scholar.google.com/citations?view_op=view_citation&hl=en&user=m8NUgw0AAAAJ&sortby=pubdate&citation_for_view=m8NUgw0AAAAJ:u_35RYKgDlwC).\n\n", "summary_of_the_paper": "This paper considers the problem of differentially privately learning deep neural networks. In order to improve the accuracy and reduce the communication cost, this paper proposes to randomly freeze a progressively increasing subset of parameters, which results in sparse gradient updates. Empirical results also show that the new algorithm can largely reduce the communication cost, while maintaining the performance. Furthermore, the extra computation cost is negligible.", "summary_of_the_review": "Overall, I think it is a borderline paper. So I am fine with either accepting or rejecting this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ae59Bn-U0oQ", "reviewer": "Reviewer_omCe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe method boasts empirical success \nPaper is well-written \n\nWeakness:\nThe proposed method, although reasonable, seems rather ad hoc. Thus, without a guiding first-principles motivation for the method, one should wonder how generally the method works and why it works.\nThe paper does not do a sufficiently thorough job at the systems considerations of the work.\n", "summary_of_the_paper": "This work introduces the idea of randomly pruning gradients in order to reduce the dimensionality, which, in turn, results in greater efficiency for DP-SGD. The work provides an empirical analysis to support the method.", "summary_of_the_review": "Overall, this method seems purely heuristic. Without a theoretical or first-principles explanation, this paper relies mostly on an empirical analysis. Theorem 1 is included, but the Gaussian assumption for SGD is extremely limiting and deviates from the accepted standards of analysis for SGD, which generally assume unbiased estimates with bounded variance, but not Gaussian shape in particular. Furthermore, the connection between Theorem 1 and the proposed method of random freezing does not seem that solid.\n\nFor the systems analysis, the authors do not report two key quantities: (1) the memory consumption (in bytes) of the method and (2) the runtime of the method. For (1), sparse representations must generally pay a memory overhead because an index is also required. A sparsity % of X% does not imply X% of the memory used. For (2), it seems that although a sparse representation can reduce memory, I am not sure how the runtime of the sparse gradient computations might also be affected here in the DP-SGD. It is important to also benchmark and report this, or at least mention that the runtime is not significantly affected if that is the case.\n\nTo summarize, the work is neither a complete systems analysis nor provides a sufficient fundamental analysis. I feel that at least one of these two aspects should be present.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "8e8MUkMPFK8", "reviewer": "Reviewer_A5Uk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- A relevant problem is addressed in this work. \n- The idea is simple but interesting and shows potential. \n\nWeaknesses:\n- The appendix proves a result for the MSE, but there is no insight or discussion into how this result would look for the proposed method.\n- The \"curse of dimentionality\" is not explored in detail (i.e. performance of the method for different numbers of parameters). Relatedly, the conclusion mentions \"... random freeze can reduce the computational cost and memory footprint of the power method in GEP\" but this is not explored in much detail in the results. \n- While the inversely proportional scaling rule is mentioned, more results would be beneficial about the choices of hyperparameters and also how robust the method is to certain parameter choices. Similarly: how many gradients can we drop before we start losing accuracy? \n- In the results in Table 1 the proposed method does not improve on the accuracy and a significant accuracy improvement is also only shown for one model. It thus remains unclear if a higher DP-guarantee be obtained with higher/similar accuracy. Test accuracy as a function of privacy loss would be interesting to see. \n\nComments: \n- A very minor comment: I am not sure I understand the positioning of section 2.5; if you see it as numerical, better to have it in the numerical section; if it is part of the discussion then let it be in the discussion. ", "summary_of_the_paper": "This paper proposes to use sparse gradients in combination with differential privacy techniques in order to mitigate performance drop that comes from applying DP to a large number of parameters. ", "summary_of_the_review": "Interesting idea but numerical experiments are not yet fully convincing and a lack of theory and discussion", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a new differentially private training method. The key idea is sparse gradient updates---that is, their variant of differentially private SGD (DP-SGD) only updates on a random subset of the parameters in each iteration. The authors argued that their method has a benefit in terms of memory and communication efficiency. The reviews suggested that the paper may require further evidence to motivate and justify the novelty of the proposed method. First, the reviewers are not fully convinced that the proposed method reduced both memory and communication. In particular, would the technique of random freeze require running DP-SGD for more iterations? Even though the authors added a new theoretical result (mostly adapted from Chen et al.), the newly added Theorem 2 does not explain the benefits of the freezing technique. Thus, the paper can benefit from more extensive theoretical analyses or justification. The authors should also consider including the additional related work brought up by the reviewers. In summary, the paper is not ready for publication at ICLR.
Decision: Reject