Year: 2021

Abstract:
To protect sensitive training data, differentially private stochastic gradient descent (DP-SGD) has been adopted in deep learning to provide rigorously defined privacy. 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, we propose random freeze which randomly freezes a progressively increasing subset of parameters and results in sparse gradient updates while maintaining or increasing accuracy. We theoretically prove the convergence of random freeze and find that random freeze exhibits a signal loss and perturbation moderation trade-off in DP-SGD. Applying random freeze across various DP-SGD frameworks, we maintain accuracy within the same number of iterations while achieving up to 70% representation sparsity, which demonstrates that the trade-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 in terms of computational cost, memory footprint and communication overhead.

heading: 1 INTRODUCTION
text: The success of machine learning, and deep neural networks in particular, combined with ubiquitous 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 on a local dataset (Fredrikson et al., 2015; Shokri et al., 2017), or even 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 privacypreserving. 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 overall privacy guarantee for several DP components. Differential privacy1 defines privacy with respect to the difficulty of distinguishing the outputs. For a pair of neighboring databases X,X ′ ∈ X , i.e. X can be obtained from X ′ by adding or removing an element.
Definition 1. A randomized mechanism M : X → R is (ε, δ)-differentially private, if for any subset of outputs S ⊆ R it holds that:
Pr[M(X) ∈ S] ≤ eε Pr[M(X ′) ∈ S] + δ.
A common paradigm for a randomized mechanismM in deep learning is perturbed gradient descent:
M(X) := f(X) +N (0, S2fσ2I), (1)
1In this work we only consider approximate differential privacy which includes the δ term.
where f : X → R computes an aggregated gradient given a database X or X ′. The isotropic Gaussian distributed noise ξDP ∼ N (0, S2fσ2I) is calibrated to f ’s sensitivity S2f , which is the maximal `2 distance ‖f(X) − f(X ′)‖, i.e. the maximal `2 norm of gradient among all individual examples. X,X ′ could be batches of training data, for instance, in our experiments they are batches of image-label pairs. The factor σ is a noise multiplier controlling the strength of the privacy guarantee: higher σ leads to lower privacy loss. Differentially private stochastic gradient descent (DP-SGD) upper bounds the certainty of connecting data with arbitrary subset of gradient space using the privacy budget variables (ε, δ). Bassily et al. (2014) show that in a convex setting, DP-SGD achieves excess risk of Õ( √ d/nε) for a
modelw ∈ Rd that minimizes the empirical risk ∑n i=1 `(w, xi), where x1, x2, ..., xn are drawn from X . While we show that in non-convex general setting, the mean square error (MSE) of perturbed gradient g̃ = g + ξDP is between Ω(d) and Ω(d2) by assuming the gradients follow a Gaussian distribution:
Theorem 1. Assuming that the gradient is drawn from N (∇w,Σ), centered at the true gradient ∇w and with respect to the covariance matrix Σ whose trace goes linearly up with dimension d. The MSE of perturbed gradient g̃ = g + ξDP can be lower bounded by:
MSE ≥ Tr[Σ](1 + dσ2). (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, as d is a large number for modern network architectures, this can lead to a significant increase in error.
The work of Abadi et al. (2016) proposed to clip the gradient of each individual example in `2 norm to a preset bound C, i.e. ḡ = g ·min(1, C‖g‖2 ). 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) +N (0, C2 · σ2Id). (3)
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 magnitude 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 a CNN with Tanh proposed by Papernot et al. (2021), which reaches ∼ 66% accuracy on CIFAR10 in a low privacy regime and is regarded as the state-of-the-art (SOTA) end-to-end network with DP-SGD. To address this curse of dimensionality, most recent works concentrate on gradient dimension reduction.

heading: 1.1 RELATED WORKS
text: Abadi et al. (2016) propose to pretrain a network on an auxiliary dataset and then transfer the feature extraction, so that only a linear classifier will be replaced and trained on the private data. Tramer & Boneh (2021) 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 lowerdimensional subspace (Vogels et al., 2019; Gooneratne et al., 2020; 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., 2021; Yu et al., 2021a; Kairouz et al., 2021) project the gradient into a 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-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. (2021b) propose a low-rank reparameterization of weights via released historical gradients.
In addition to the aforementioned works, McMahan et al. (2017); 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, as 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 et al., 2012). Therefore, gradient dimension reduction can have large benefits in federated learning involving power-restricted edge devices. A line of work studies how to tackle this issue by utilizing the low-rank property (Shokri & Shmatikov, 2015; Yang et al., 2019; Liu et al., 2020).

heading: 1.2 OUR CONTRIBUTION
text: In this work, we demonstrate an 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, or approximate the gradient from a subspace. Instead, we randomly zero-out a fraction of the gradient during training and force the gradient to have a sparse representation. We provide a theoretical study on this strategy and reveal that random freeze exhibits a trade-off between signal loss and perturbation moderation in DP-SGD. We remark that our theory and approach do not necessarily rely on the low-rank assumption. To the best of our knowledge, we are the first to study this trade-off in DP-SGD and provide an effective approach.
We use the benchmark CIFAR10 (Krizhevsky, 2012) which is to date standard in 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 a 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. (2021).

heading: 2 ANALYSIS OF RANDOM FREEZE
text: In this section we theoretically prove that to a certain freeze rate r, DP-SGD with random freeze will converge if the approach without random freeze can converge. Then we investigate the tradeoff 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.

heading: 2.1 CONVERGENCE RATE OF DP-SGD WITH RANDOM FREEZE
text: Let L be the objective function L(w) := Ex∼X [`(w, x)], m ∈ {0, 1}d the freeze mask and r the freeze rate, we randomly draw rp indices and set these positions in the mask to 0 and others to 1 so that ∑ m = (1 − r)d. We assume an oracle telling us the true gradient ∇w and individual gradient gt,i = ∇w + ξt(xi), where ξt is independent gradient deviation with zero mean. Let pt be the distribution of ξt. For random freeze the sparse gradient is g′t,i = ∇w′t + ξ′t(xi), where ∇w′t := m ∇wt, ξ′t(xi) := m ξt(xi). Denote for DP-SGD the averaged clipped gradient of B samples ḡt := 1B ∑ i gt,i ·min(1, C ‖gt,i‖ ), and for DP-SGD with random freeze ĝt := 1 B ∑ i g ′ t,i · min(1, C‖g′t,i‖ ). We have for DP-SGD with random freeze the following inequality:
Theorem 2. Assume G-Lipschitz smoothness of∇w such that ||∇wt+1−∇wt|| ≤ G||wt+1−wt||. Consider an algorithm with clipping bound C, learning rate γ and choose a symmetric probability density distribution p̃(·) satisfying p̃t(ξt) = p̃t(−ξt), ∀ξt ∈ Rd. Then ∃κ ≥ 1− r such that:
1
T T∑ t=1 Pξt∼p̃t(‖ξt‖ < C 4 )h(∇wt)‖∇wt‖ ≤ 1 κ ( ∆L γT +γ∆C +(1−r)γ∆DP − 1 T T∑ t=1 Em[bt]), (4)
where we define bt := ∫ 〈∇w′t, g′t,i · min(1, C‖g′t,i‖ )〉(p ′ t(ξ ′ t) − p̃′t(ξ′t))dξ′t, p′t, p̃′t are corresponding projected distribution, and define ∆L := E[L1 − minw L(w)], ∆C := GC 2 2 , ∆DP := C2σ2dG
2B2 , h(∇wt) := min(‖∇wt‖, 3C4 ). The proof can be found in Appendix B. When no freeze r = 0, i.e. m is a vector filled with value 1. Note that κ = 1 for r = 0, we can obtain the inequality 4 in the following form:
1
T T∑ t=1 Pξt∼p̃t(‖ξt‖ < C 4 )h(∇wt)‖∇wt‖ ≤ ∆L γT + γ(∆C + ∆DP )− 1 T T∑ t=1 bt, (5)
which describes DP-SGD without random freeze. Chen et al. (2020b) argue that by tweaking p̃t it is possible to boundPξt∼p̃t away from zero which means the l.h.s. is proportional to ‖∇wt‖ or ‖∇wt‖2 at each iteration, while letting the convergence bias term−bt tend to 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 at the r.h.s. of inequality 4 for random freeze, −Em[bt] also tends to be small as p′t is expected to be approximately symmetric if pt is. Additionally, 1/κ will not be large as along as r is not extremely close to 1. So with the same learning rate and γ adapted for DP-SGD 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.

heading: 2.2 TRADE-OFF BETWEEN SIGNAL LOSS AND PERTURBATION MODERATION
text: From Theorem 2, we see that by applying random freeze the injected noise term ∆DP is reduced by 1−rκ < 1 while other terms could be increased by 1/κ. From an operational view, random freeze moderates perturbation while removing some signal. Therefore, the convergence rate of random freeze is a trade-off between signal loss and perturbation moderation. Consider that ∆DP is proportional to the number of parameters d, which is large for neural networks. It might be worthwhile to remove some signal while moderating perturbation. To investigate this question, we consider the MSE of gradient estimation of DP-SGD with and without random freeze at iteration t:
MSEDP := E[‖∇wt − (ḡ + ξDP )‖2] = E[‖∇wt − ḡ‖2] + C2σ2d
B2 , (6)
MSERF := E[‖∇wt − (ĝ +m ξDP )‖2] 32 = E[‖∇wt − ĝ‖2] + (1− r)
C2σ2d
B2 . (7)
Two statistics of interest are: First, the difference of signal loss ∆S := E[‖∇wt− ḡ‖2]−E[‖∇wt− ĝ‖2]. DP-SGD induces signal noise due to clipping bias while random freeze has additional loss due to freezing. Second, the difference of MSE ∆MSE := MSEDP −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 (ε = 7.53, δ = 10−5) and measure these two statistics with respect to empirical distribution at the end of three training stages (see Figure 1). 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
that injected noise is dominant during optimization. Combining this with Theorem 2, it shows the possibility that we achieve better convergence by removing some signal while mitigating noise. For example, in addition to taking advantage of noise mitigation, we can also raise the noise to ξ+DP so that E[‖m ξ+DP ‖] matches E[‖ξDP ‖]. This allows us to run more iterations T on the same privacy budget, which also implies better convergence by Theorem 2. In section 4 we will demonstrate that when d is large, which implies large ∆DP , we can improve the performance by applying random freeze.

heading: 2.3 A GRADIENT DISTRIBUTION VIEW OF RANDOM FREEZE
text: We also observe the potential benefit of random freeze from the perspective of the gradient distribution. Compared to no freeze, random freeze leads to less clipping bias and gradient distortion, as shown in Figure 2. We 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 of sparse gradients are not equally scaled down, weak gradients can spontaneously become larger during training, which mitigates the distortion of gradients due to perturbation, while the perturbation of random freeze is already moderated compared to no freeze.

heading: 3 TECHNICAL DETAILS
text: Algorithm 1 outlines our approach. Since the coordinates that have been selected to freeze do not depend on the dataset, their indices can be exposed or transferred in clear text and do not lead to additional privacy loss to 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 be updated as 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,

heading: 3.1 GRADUAL COOLING
text: We find that if we 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
Algorithm 1: Random freeze Input: Initialized parameters: w0; Loss function: `; Iterations per epoch: T ; Epochs E; Freeze rate: r∗; Cooling time: e∗; Clipping bound: C; Momentum: µ; Learning rate γ. for e = 0...E-1 do
r(e) = r∗ ·min( ee∗−1 , 1); Randomly generate a freeze mask m ∈ {0, 1}d subject to ∑ m = d · (1− r(e)); for t = 0...T-1 do For each xi in minibatch of size B, compute gt(xi) = ∇`(wt, xi); Partially zero out each gradient gt(xi) = m gt(xi); Clip each individual gradient ĝt(xi) = gt(xi) ·min(1, C‖gt(xi)‖2 ); Add noise g̃t = 1B ( ∑ i ĝt(xi) +m N (0, C2σ2Id));
Update vt+1 = µ · vt + gt, wt+1 = wt − γvt+1; end
end
active. So we present gradual cooling, which is inspired by the gradual warm-up of the learning rate adopted for non-privacy-preserving training (Goyal et al., 2017). Gradual cooling linearly ramps up the freeze rate from 0 to r∗ within a predefined cooling time e∗ and stays at r∗ for the remaining training epochs, i.e. r = r∗ ·min( ee∗−1 , 1).

heading: 3.2 PER-ITERATION RANDOMIZATION VS. PER-EPOCH RANDOMIZATION
text: Although conducting random freeze leads to negligible additional computational cost and memory footprint, we find that it is sufficient to generate one 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 contrast, 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 − r)d parameters updated, which is favorable in collaborative learning schemes as communication cost is a significant issue, and data are not transmitted every iteration. While for per-iteration randomization, the cumulative number of updated parameters depends on the freeze rate r and iterations between two communication rounds, resulting in higher communication overheads than per-epoch randomization.

heading: 3.3 RANDOM FREEZE VS. RANKED FREEZE
text: Based on the observation of the low-rank property of gradients (Vogels et al., 2019; Gooneratne et al., 2020; Li et al., 2020), freezing the parameters with respect to the mean of past perturbed gradients instead of a random draw might be helpful: First, taking the mean of past perturbed gradients will
average out zero-mean noise. Second, the magnitude of the gradients is a 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 3 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 freeze2 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 3). This result also reflects that even in a low privacy regime, noise has a significant impact throughout training.
1−0.9 = 1, (b)
has momentum fixed µ = 0.9 and varies the clipping bound, (c) has clipping bound fixed toC = 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 µ = 0 results in better performance, probably due to less clipping bias induced by a higher clipping bound. We find out that this rule is relatively general and independent on privacy level. For experiment on low privacy budget (ε = 7.53, δ = 10−5), refer to Appendix F.

heading: 3.4 INVERSELY PROPORTIONAL SCALING RULE FOR ADJUSTING THE CLIPPING BOUND AND MOMENTUM
text: Previous works commonly adopt first order momentum in the optimization, because momentum can alleviate oscillation and accelerate gradient descent (Sutskever et al., 2013). As a result, it is believed to reduce the number of iterations of training and therefore achieve less privacy loss. However, for privacy-preserving 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: vt+1 = µ · vt + gt+1, where v, µ, g denote perturbed velocity, momentum and perturbed gradients, respectively. Using the expression of one step noise in Equation 3 and denoting by v̂t the velocity after separating the noise, we have vt+1−v̂t+1 = (1+µ+µ2+...+µt)·N (0, C2 ·σ2Id). After many iterations, the scalar approximates a geometric series, i.e. vt+1 − v̂t+1 ≈ 11−µ · N (0, C
2 · σ2Id). Pulling the clipping bound C out and forming the noise as C1−µ · N (0, σ
2Id), we present an inversely proportional scaling rule for adjusting C and 1 − µ, i.e. with other hyperparameters fixed, networks trained with same value of the ratio C1−µ perform similarly (see Figure 4). Our conjecture is that the inversely proportional scaling rule ensures the same amount of injected noise.
2For implementation details of ranked freeze, refer to Appendix C.
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-perserving training has been observed to be brittle. This rule helps reduce the tuning workload.

heading: 4 EXPERIMENTAL RESULTS
text: Privacy budget According to Definition 1, we have that each iteration of training is (ε, δ)differentially private with respect to a batch of training data, while shuffling and partitioning the dataset into batches implies that each iteration is (O(qε), qδ)-differentially private with respect to the full dataset according to the privacy amplification theorem (Balle et al., 2018; 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 Ré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 WW ᵀV , W ∈ Rd×s denotes sample gradients, V ∈ Rd×b denotes eigenvectors, the computational cost is O(dbs). Similarly, for projection V ᵀX; X ∈ Rd×n denotes original gradients, the computational cost is O(dbn). Applying random freeze, a random selection of rows of X are deleted, while corresponding rows of V,W can be removed as no information of gradient exits in that subspace. We note that b, smight also be able to be reduced. Overall, the computational cost is between O(1 − r) and O((1 − r)3). Another issue of projected DP-SGD is 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 log210
9 < 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 footprint are Õ(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 individual 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 CIFAR10, which is to date standard in benchmarking DP learning. Our code is available for download from http://anonymized.for.review/.
To validate the reliability of random freeze, we conduct experiments on several SOTA networks cross different frameworks, including End-to-end CNN (Papernot et al., 2021); Handcrafted CNN (Tramer & Boneh, 2021) which incorporates ScatterNet (Oyallon et al., 2019) as feature extractor; Gradient Embedding Perturbation (GEP) proposed by Yu et al. (2021a) which injects noise in projected gradient; DP-Transfer Learning which adopts a pretrained network and replaces the linear classifier layer, in particular we use SIMCLR v2 (Chen et al., 2020a) pretrained on unlabeled ImageNet (Deng et al., 2009), which has been benchmarked by Tramer & Boneh (2021).
For a 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 e = 0 to r = r∗ at epoch e = e∗, i.e. r = r∗ · ee∗−1 . These straightforward experiments allow us to demonstrate that random freeze is a safe add-on in a variety of methods. We summarize the performance results in Table 1, and the corresponding total density by random freeze in Table 2. We document the hyperparameters in Appendix D.
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, we 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)
Total density
with respect to the inversely proportional scaling rule proposed in Section 3.4, which leads to better accuracy. Secondly, we apply random freeze. Similar to the previous experiment we also linearly ramp up the freeze rate to 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 σ has been increased accordingly to ensure the same privacy budget will be consumed. As a 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 E.

heading: 5 DISCUSSION AND CONCLUSIONS
text: In this work we propose random freeze which is an axis-aligned random gradient dimension reduction method. We provide a 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 is able to 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 DP-SGD. and expect random freeze to exhibit strong improvements as DP-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.

heading: A MEAN SQUARE ERROR OF GRADIENT IN DP-SGD
text: Theorem 1. Assuming that the gradient is drawn from N (∇w,Σ), centered at the true gradient ∇w and with respect to the covariance matrix Σ whose trace goes linearly up with dimension d. The MSE of perturbed gradient g̃ = g + ξDP can be lower bounded by:
MSE ≥ Tr[Σ](1 + dσ2). (2)
Proof. Assuming an oracle can tell us the true gradient ∇w given a network with parameters w ∈ Rd, while the individual gradient g can be seen as drawn from the Gaussian distribution centered at ∇w with respect to the covariance matrix Σ, i.e. g ∼ N (∇w,Σ). Denote ξg as gradient deviation, i.e. ξg = g −∇w, the perturbed gradient g̃ in DP-SGD can be expressed as:
g̃ = ∇w + ξg + ξDP (8) and the mean square error of perturbed gradient is:
MSE = E[ξᵀg ξg + 2ξᵀg ξDP + ξ ᵀ DP ξDP ] (9)
Since ξDP and ξg are independent and plugging the definition of injected noise. i.e. ξDP ∼ N (0,max(gᵀg)σ2Id), into Equation 9, we have:
MSE = E[ξᵀg ξg] + E[ξ ᵀ DP ξDP ] (10)
= Tr[Σ] + dσ2E[max(gᵀg)] (11) = Tr[Σ] + dσ2E[max(ξᵀg ξg + 2∇wᵀξg +∇wᵀ∇w)] (12) ≥ Tr[Σ] + dσ2E[max(ξᵀg ξg)] (13)
where equality can be achieved when the network converges to stationary point, i.e.∇w → 0. Applying a spectral decomposition to Σ, we obtain QᵀΛQ = Σ, where Q is an orthonormal basis and Λ is diagonal matrix of eigenvalues of Σ. Denote by z a random vector drawn i.i.d. from a normal distribution, we can further derive:
ξᵀg ξg ∼ zᵀΣz = zᵀQᵀΛQz = zᵀΛz (14) As random variable with respect to the same distribution leads to the same expectation, plugging Equation 14 into Equation 13, we have:
MSE ≥ Tr[Σ] + dσ2E[max(zᵀΛz)] (15)
= Tr[Σ] ( 1 + dσ2E [ max ( 1
Tr[Σ] zᵀΛz
)]) (16)
= Tr[Σ] ( 1 + dσ2E [ max ( 1
Tr[Λ] zᵀΛz
)]) (17)
Since zᵀΛz = λ1z21 + λ2z 2 2 + · · ·+ λdz2p; zi ∼ N (0, 1), we have:
1 Tr[Λ] zᵀΛz ∼ 1 Tr[Λ] ∑ i Gamma ( 1 2 , 1 2λi ) . (18)
So far either the exact PDF of a Gamma distribution summation can only be represented with (another) series of gamma distributions (Moschopoulos, 1985; Mathai, 1982), or its exact CDF has a series representation (Moschopoulos & Canada, 1984). For the convenience of further derivation of the expected maximum, we use the Welch-Satterthwaite approximation which provides a certain Gamma distribution:
1
Tr[Λ] ∑ i Gamma ( 1 2 , 1 2λi ) ≈ 1 Tr[Λ] Gamma ( Tr2{Λ} 2 Tr{Λ2} , Tr{Λ} 2 Tr{Λ2} ) (19)
= Gamma
( Tr2{Λ}
2 Tr{Λ2} , Tr2{Λ} 2 Tr{Λ2}
) (20)
Denote Mn = max(x1, x2, ..., xn), where xi is drawn from Gamma ( Tr2{Λ} 2 Tr{Λ2} , Tr2{Λ} 2 Tr{Λ2} ) . While
from the Cauchy-Schwarz inequality, we have:
|〈Id,diag{Λ}〉|2 ≤ 〈Id, Id〉 · 〈diag{Λ},diag{Λ}〉 (21) Tr2[Λ] ≤ d · Tr[Λ2] (22)
Tr2{Λ} 2 Tr[Λ2] ≤ d 2
(23)
Denote k as Tr 2{Λ}
2 Tr{Λ2} , Figure 5 illustrates the PDF of Gamma distribution with parameters Gamma(k, k).
As k becomes large, the distribution becomes more concentrated, and we have the following inequality:
M (1)n = max(x (1) 1 , x (1) 2 , ..., x (1) n ), x (1) i ∼ Gamma( Tr2{Λ} 2 Tr{Λ2} , Tr2{Λ} 2 Tr{Λ2} )
M (2)n = max(x (2) 1 , x (2) 2 , ..., x (2) n ), x (2) i ∼ Gamma(
d 2 , d 2 )
E[M (1)n ] ≥ E[M (2)n ] ≥ E[ 1
n ∑ i x (2) i ] = 1 (24)
Substituting inequality 24 back into Equation 17, we have:
MSE ≥ Tr[Σ](1 + dσ2). (25)
The proof is completed.
We note that Tr[Σ] is the trace of a d-dimensional covariance matrix. In the extreme case that Σ = λI , this will scale linearly in d, while in the opposite extreme of a rank deficient covariance matrix, the trace is constant in d. Thus, in the former case
MSE ≥ λd+ λσ2d2, (26)
while in the latter we have
MSE ≥ λ+ λσ2d, (27)
which leads to our conclusion that the lower bound on MSE is between linear and quadratic in d in practice.

heading: B THE CONVERGENCE RATE OF DP-SGD WITH RANDOM FREEZE
text: Lemma 1. u, v ∈ Rd are too arbitrary vectors,m is a {0, 1}d random mask independent from u, v, and subject to ∑ m = (1− r)d, where r denotes the freeze rate. We have the following expectation:
E[〈mk u, v〉] = (1− r)E[〈u, v〉]. (28)
Proof.
E[〈mk u, v〉] = E[〈m u, v〉], (29) = ∑ i E[mi]E[uivi], (30)
= (1− r)E[〈u, v〉]. (31)
The proof is completed.
Corollary 1.1. Following the notation of lemma 1, we have the expectation below:
E[〈m u,m v〉] = (1− r)E[〈u, v〉]. (32)
Proof.
E[〈m u,m v〉] = E[〈m2 u, v〉], (33) 28 = (1− r)E[〈u, v〉]. (34)
The proof is completed.
Lemma 2. u ∈ Rd is an arbitrary vector, m is a {0, 1}d random mask independent from u and subject to ∑ m = (1− r)d, where r denotes the freeze rate. We have the following inequality:
E[‖m u‖] ≥ (1− r)‖u‖. (35)
Proof.
E[‖m u‖] = 1 ‖u‖ E[‖m u‖‖u‖], (36)
≥ 1 ‖u‖ E[‖m u‖2], (37)
32 =
1
‖u‖ (1− r)E[〈u, u〉], (38)
= (1− r)‖u‖. (39)
Equality is taken when r = 0. The proof is completed.
Theorem 2. Assume G-Lipschitz smoothness of∇w such that ||∇wt+1−∇wt|| ≤ G||wt+1−wt||. Consider an algorithm with clipping bound C, learning rate γ and choose a symmetric probability density distribution p̃(·) satisfying p̃t(ξt) = p̃t(−ξt), ∀ξt ∈ Rd. Then ∃κ ≥ 1− r such that:
1
T T∑ t=1 Pξt∼p̃t(‖ξt‖ < C 4 )h(∇wt)‖∇wt‖ ≤ 1 κ ( ∆L γT +γ∆C +(1−r)γ∆DP − 1 T T∑ t=1 Em[bt]), (4)
Proof. Denote the injected noise at each iteration ξDP := 1B z, where z is drawn from N (0, C2σ2Id), follow from the smoothness assumption, we have:
Lt+1 ≤ Lt + 〈∇wt, wt+1 − wt〉+ G
2 ‖wt+1 − wt‖2, (40)
= Lt − γ〈∇wt, ĝt +m ξDP 〉+ Gγ2
2 ‖ĝt +m ξDP ‖2, (41)
= Lt − γ〈∇wt, ĝt〉 − γ〈∇wt,m ξDP 〉+ Gγ2
2 ‖ĝt +m ξDP ‖2, (42)
Taking expectations on both sides and rearranging, we have:
E[〈∇wt, ĝt〉] ≤ 1
γ E[Lt − Lt+1]− E[〈∇wt,m ξDP 〉] +
Gγ
2 E[‖ĝt +m ξDP ‖2], (43)
28 =
1 γ E[Lt − Lt+1]− (1− r)E[〈∇wt, ξDP 〉] + Gγ 2 E[‖ĝt +m ξDP ‖2], (44)
28 =
1 γ E[Lt − Lt+1]− 0 + Gγ 2 (E[‖ĝt‖2] + E[‖m ξDP ‖2]− 0), (45)
32 =
1 γ E[Lt − Lt+1] + Gγ 2 (E[‖ĝt‖2] + (1− r)
C2σ2d
B2 ), (46)
≤ 1 γ E[Lt − Lt+1] + Gγ 2 (C2 + (1− r)C
2σ2d B2 ). (47)
Now focusing on the l.h.s., we have:
E[〈∇wt, ĝt〉] = 〈∇wt,E[ĝt]〉, (48)
= 〈∇wt, 1
B ∑ i E[m gt,i ·min(1, C ‖m gt,i‖ )]〉, (49)
= E[〈∇wt,m gt,i ·min(1, C
‖m gt,i‖ )〉], (50)
= E[〈m ∇wt,m gt,i ·min(1, C
‖m gt,i‖ )〉], (51)
= Em [ Eξt [〈∇w′t, g′t,i ·min(1, C
‖g′t,i‖ )〉|m]
] , (52)
= Em [ Eξ′t∼p̃′t [〈∇w ′ t, g ′ t,i ·min(1, C
‖g′t,i‖ )〉|m]
] + Em[bt], (53)
where we have defined bt := ∫ 〈∇w′t, g′t,i · min(1, C‖g′t,i‖ )〉(p ′ t(ξ ′ t) − p̃′t(ξ′t))dξ′t. Equation 52 is achieved because ξt and m are independent. We note that for any given m, ξ′t is still independent deviation with zero mean and p̃′t(ξ ′ t) = p̃ ′ t(−ξ′t) since projection of symmetric distribution to subspace is symmetric. According to Theorem 2 from Chen et al. (2020b), for a given m we have the following inequality:
Eξ′t∼p̃′t [〈∇w ′ t, g ′ t,i ·min(1,
C
‖g′t,i‖ )〉|m] ≥ Pξ′t∼p̃′t(‖ξ ′ t‖ <
C 4 ) min(‖∇w′t‖, 3C 4 )‖∇w′t‖. (54)
Back to Inequality 47 and considering the overall T steps, we have:
1
T T∑ t=1 E[〈∇w, ĝt〉] ≤ 1 γT E[L1 − LT ] + Gγ 2 (C2 + (1− r)C 2σ2d B2 ), (55)
≤ 1 γT ∆L + γ∆C + (1− r)γ∆DP , (56)
where we have defined ∆L := E[L1 − minw L(w)], ∆C := GC 2 2 , ∆DP := C2σ2dG
2B2 . Plugging Inequality 54 into Equation 53 and combining with Inequality 56:
1
T T∑ t=1 Em[Pξ′t∼p̃′t(‖ξ ′ t‖ < C 4 )h(∇w′t)‖∇w′t‖] ≤ ∆L γT + γ∆C + (1− r)γ∆DP − 1 T T∑ t=1 Em[bt],
(57)
where we have defined h(∇w′t) = min(‖∇w′t‖, 3C4 ). Now we look at the l.h.s. and consider each step with respect to the following cases:
case 1: ‖∇wt‖ ≤ 34C, then Pm(‖∇w ′ t‖ ≤ 34C) = 1,
Em[Pξ′t∼p̃′t(‖ξ ′ t‖ <
C 4 )h(∇w′t)‖∇w′t‖] ≥ Pξt∼p̃t(‖ξt‖ < C 4 )Em[h(∇w′t)‖∇w′t‖], (58)
= Pξt∼p̃t(‖ξt‖ < C
4 )Em[‖∇w′t‖2], (59)
32 = Pξt∼p̃t(‖ξt‖ <
C 4 )(1− r)‖∇wt‖2, (60)
= (1− r)Pξt∼p̃t(‖ξt‖ < C
4 )h(∇wt)‖∇wt‖. (61)
case 2: ‖∇wt‖ > 34C, consider two events A1: ‖∇w ′ t‖ ≤ 34C; A2: ‖∇w ′ t‖ > 34C then we have:
Em[Pξ′t∼p̃′t(‖ξ ′ t‖ <
C 4 )h(∇w′t)‖∇w′t‖] ≥ Pξt∼p̃t(‖ξt‖ < C 4 )Em[h(∇w′t)‖∇w′t‖], (62)
60 ≥ Pξt∼p̃t(‖ξt‖ < C
4 )(P (A1)(1− r)‖∇wt‖2+ (63)
P (A2) 3
4 C · Em[‖∇w′t‖]),
35 ≥ Pξt∼p̃t(‖ξt‖ < C
4 )(P (A1)(1− r)‖∇wt‖2+ (64)
P (A2) 3
4 C(1− r)‖∇wt‖),
≥ Pξt∼p̃t(‖ξt‖ < C 4 )(1− r)3 4 C‖∇wt‖, (65)
= (1− r)Pξt∼p̃t(‖ξt‖ < C
4 )h(∇wt)‖∇wt‖, (66)
from which we conclude that:
Em[Pξ′t∼p̃′t(‖ξ ′ t‖ <
C 4 )h(∇w′t)‖∇w′t‖] ≥ (1− r)Pξt∼p̃t(‖ξt‖ < C 4 )h(∇wt)‖∇wt‖. (67)
The inequality above implies that ∃κ ≥ 1− r such that: T∑ t=1 Em[Pξ′t∼p̃′t(‖ξ ′ t‖ < C 4 )h(∇w′t)‖∇w′t‖] = κ T∑ t=1 Pξt∼p̃t(‖ξt‖ < C 4 )h(∇wt)‖∇wt‖. (68)
We note that κ = 1 if r = 0. Plugging equation 68 into inequality 57 we obtain:
1
T T∑ t=1 Pξt∼p̃t(‖ξt‖ < C 4 )h(∇wt)‖∇wt‖ ≤ 1 κ ( ∆L γT +γ∆C+(1−r)γ∆DP− 1 T T∑ t=1 Em[bt]). (69)
The proof is completed.
It is worthwhile to note that the l.h.s. can also be written as the general form below and the inequality still holds:
1
T T∑ t=1 Pξt∼p̃t(‖ξt‖ < zC) min(‖∇wt‖, (1− z)C)‖∇wt‖, ∀z ∈ (0, 1) (70)

heading: C RANKED FREEZE
text: Algorithm 2 describes ranked freeze, the performance is recorded in Table 4. Note that for aggregated gradient estimation we also inject noise to gradient estimation ge of frozen coordinates. If not, the coordinates get frozen at the first iteration will receive aggregated gradient estimation as 0 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 in 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: w0; Loss function: `; Iterations per epoch: T ; Epochs E; Freeze rate: r∗; Cooling time: e∗; Clipping bound: C; Momentum: µ; Learning rate γ. for e = 0...E-1 do
ge = {0}d; r(e) = r∗ ·min( ee∗−1 , 1); if e is 0 then
m = {1}d else
Sort the indices [1,...,d] with respect to corresponding aggregated gradient of the last epoch ge−1 in ascending order then set the first d · r(e) positions in mask m to 0 and the rest to 1;
end for t = 0...T-1 do
For each xi in minibatch of size B, compute gt(xi) = ∇`(wt, xi); Partially zero out each gradient gt(xi) = m gt(xi); Clip each individual gradient ḡt(xi) = gt(xi) ·min(1, C‖gt(xi)‖2 ); Add noise g̃t = 1B ( ∑ i ḡt(xi) +m N (0, C2σ2Id)); Update vt+1 = µ · vt + gt, wt+1 = wt − γvt+1, ge = ge + 1B ( ∑ i ḡt,i +N (0, C2σ2Id));
end end

heading: D HYPERPARAMETERS FOR TABLE 1
text: The δ term is 10−5 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
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 are listed separately for each framework, see Table 5, 7, 6, 8. 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 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.
End-to-end CNN
DP-Transfer Learning
E IMPROVING THE ACCURACY OF END-TO-END CNN
Table 9 includes the hyperparameters and total density of ajusted End-to-end CNN with random freeze. Figure 6 shows the accuracy as a function of privacy loss.
F INVERSELY PROPORTIONAL SCALING RULE
We include here an additional experiments of inversely proportional scaling rule on low privacy budget (see Figure 7).
1−0.9 =
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, we see this rule is relatively general and does not dependent on privacy level.

heading: G A NUANCE OF RANDOM FREEZE
text: Gradient clipping is usually the first step we 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 a 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
gradient ḡt := 1B ∑ im gt,i ·min(1, C ‖gt,i‖ ), assume G-Lipschitz smoothness, we have:
E[〈∇wt, ḡt〉] 43 ≤ 1 γ E[Lt − Lt+1]− E[〈∇wt,m ξDP 〉] + Gγ 2 E[‖ḡt +m ξDP ‖2], (71)
28 =
1 γ E[Lt − Lt+1]− (1− r)E[〈∇wt, ξDP 〉] + Gγ 2 E[‖ḡt +m ξDP ‖2], (72)
28 =
1 γ E[Lt − Lt+1]− 0 + Gγ 2 (E[‖ḡt‖2] + E[‖m ξDP ‖2]− 0), (73)
32 =
1 γ E[Lt − Lt+1] + Gγ 2 (E[‖ḡt‖2] + (1− r)
C2σ2d
B2 ) (74)
Similarly for DP-SGP with random freeze, we have:
E[〈∇wt, ĝt〉] ≤ 1
γ E[Lt − Lt+1] +
Gγ
2 (E[‖ĝt‖2] + (1− r)
C2σ2d
B2 ). (75)
We see both methods moderate the perturbation, while E[‖ḡt‖2] ≤ E[‖ĝt‖2] but it is complicated to compare E[〈∇wt, ḡt〉] and E[〈∇wt, ĝt〉], we leave this for future work. From an operational view, denote ḡt,i = m gt,i · min(1, C‖gt,i‖ ) and ĝt,i = m gt,i · min(1, C ‖m gt,i‖ ), we see that 〈ḡt,i, ĝt,i〉/‖ḡt,i‖‖ĝt,i‖ = 1 and ‖ḡt,i‖ ≤ ‖ĝt,i‖ ≤ ‖gt,i‖, 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.

Review summaries:
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.