Differentially Private Optimization on Large Model at Small Cost
Authors: Zhiqi Bu
Yu-Xiang Wang
Sheng Zha
George Karypis
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep learning
differential privacy
complexity
computation efficiency

Abstract: Differentially private (DP) optimization is the  standard paradigm to learn large neural networks that are accurate and privacy-preserving. The computational cost for DP deep learning, however, is notoriously heavy due to the per-sample gradient clipping. Existing DP implementations are $2-1000\times$ more costly in time and space complexity than the standard (non-private) training. In this work, we develop a novel Book-Keeping (BK) technique that implements existing DP optimizers (thus achieving the same accuracy), with a substantial improvement on the computational cost. Specifically, BK enables DP training on large models and high dimensional data to be roughly as efficient as the standard training, whereas previous DP algorithms can be inefficient or incapable of training due to memory error. The computational advantage of BK is supported by the complexity analysis as well as extensive experiments on vision and language tasks. Our implementation achieves state-of-the-art (SOTA) accuracy with very small extra cost: on GPT2 and at the same memory cost, BK has 1.0$\times$ the time complexity of the standard training (0.75$\times$ training speed in practice), and 0.6$\times$ the time complexity of the most efficient DP implementation (1.24$\times$ training speed in practice). We will open-source the codebase for the BK algorithm.

Under review as a conference paper at ICLR 2023
DIFFERENTIALLY PRIVATE OPTIMIZATION ON LARGE MODEL AT SMALL COST
Anonymous authors Paper under double-blind review
ABSTRACT
Differentially private (DP) optimization is the standard paradigm to learn large neural networks that are accurate and privacy-pree preeeeypr..r.ing... The computational cost for DP deep learning, however, is notoriously heavy due to the per-sample gra- dient clipping. Existing DP implementations are 2 1000x more costly in time and space complexity than the standard (non-private) training. In this work, we develop a novel Book-Keeping (BK) technique that implements existing DP op- timizers (thus achieving the same accuracy), with a substantial improvement on the computational cost. Specifically, BK enables DP training on large models and high dimensional data be roughly as efficient as the standard training, whereas previous DP algorithms can be inefficient or incapable of training due to memory error. The computational advantage of BK is supported by the complexity analy- sis as well as extensive experiments on vision and language tasks. Our implemen- tation achieves state-of-the-arr (SOTA) accuracy with very small extra cost: on GPT2 and at almost the same memory cost (< 1% overhead), BK has 1.03x the time complexity of the standard training (0.83x training speed in practice), and 0.61 x the time complexity of the most efficient DP implementation (1.36x train- ing speed in practice). We will open-source the codebase for the BK algorithm.
INTRODUCTION
Deep learning with differential privacy (DP: Dwork et al. 2006)) has shown strong performance while guaranteeing rigorous protection against privacy risks, especially on large models that tend to
memorize and leak the training data Carlini al. 2021;; Haim et al. (2022) Shokri et al. (201)). For example, recent advances have shed light on the success of DP GP al. (2021): Bu et al.
(2022b); Yu al. (2021). which achieves 64.6 BLEU score"] at strong privacy guarantee
3),
on the text generation task using E2E restaurant review dataset. This is only marginally below the standard non-private GPT2 (BLEU score 66.8). Similarly, on computer vision tasks (E = 2), DP
vision transformers and ResNets have obtained 97.1% 88.2%% accuracy on CIFARI0/100 by Bu al. 2022a and over 81% accuracy on ImageNet by De et al. (2022); Mehta et al. 2022)).
However, DP training of large neural networks is well-known to be computationally burdensome in comparison the standard training, in terms of both the training time and the memory cost. For instance, training a small recurrent neural network (0.598M parameters) experiences 1000x slowdown using DP optimizers in Pensorflow-Privare (TF-Privacy) library [Bu al. (202T), and training a small convolutional neural network (CNN, 0.605M parameters) on CIFARTO has a 24x slowdown with Tensorflow 2 and the XLA compiler Subramani et al. (202T) Even with SOTA efficient implementations, large models such RoBERTa Liu et al. (2019). GPT2 Radford et al. 2019), ResNetHHe et al. (2016), VGG VGG Simonnan & Zisserman (2014), ViT Dosovitskyy et al. (2020) and its variants, experience about 2 3x slowdown in Pytorch Li et al. (2021)
(202aa) and
2 - 9x slowdown in JAX Kurakin et al. (2022); De et al. (2022), with possibly 4 20x memory (202) if not out of memory.
overhead Bu et al. (2022a) Li et (202 Subramani
The efficiency bottleneck in DP deep learning lies in the per-sample gradientclippingg which restricts the magnitude of each per-sample gradient in the mini-batch. Applying the clipping jointly with the
BB.EU (Bil ingual Evaluation Understudy) is metric (0-100) for automatically evaluating translated text. BLEU 60 considered "very high quality, adequate, and fluent translations, often better than human".

---

Under review as a conference paper at ICLR 2023
Gaussian noise addition, one can privately release the gradient to arbitrary optimizers like SGD and Adam, and thus guarantee the privacy of the training as described in Section 1.3
private gradient:
G = Σ, 9: ((1lg:l))))) + opp T
(1)
private optimizer (e.g. SGD):
W/-1 = W, n/G.
Here w is the model parameters, L; is the per-sample loss, g: = aw is the per-sample gradient, the learning rate, DP is the noise magnitude that defines the privacy loss, and C(Ilg: simply C is the per-sample clipping factor, e.g. min(R//lga) 1| } in Abadi et al. (2016), with a clipping threshold R.
At high level, previous work have tackled the efficiency bottleneck with various approaches.
I. optimizer
IL. parameter efficiency
III. implementation
IV. platform
DP-SGD, DP-Adam
layer, LoRA, Adapter
Opacus, GhosoClip.
Pytorch, JAX, TF
One approach (part II) focuses the parameter efficiency by partially training neural network, in contrast to full fine-tuning all model parameters, e.g. only the last output layer [Tramer & Boneh (2020), the adapter layers Houlsby al. (2019); Mahabadi et al. (2021), the Low-Rank Adapta- tion (LoRA) training on ImageNet Deng
) Hu et al. (2021) Yu et al. (022). For example, Mehta et al. (2022) accelerate the DP
(2099) up x0 by only training the last layer of ResNet1 No- ticeably, parameter efficient fine-tuning does not improve on the efficiency in terms of complexity per parameter, rather than reducing the number of parameters. Furthermore, this approach often- times leads to some accuracy degradation compared to DP full fine-tuning Bu et al. (2020); Mehta ct al. 2022);
al. 2021) );
Yu et al. (20TT.
An orthogonal approach, including this work, focuses on the computation efficiency (part III), i.e. reducing the time and space complexity through efficient implementations, without affecting the DP optimizers (part and thus their performance. We will elaborate multiple methods in Section 1.2 Additionally, these methods can be compiled on different platforms (part IV) such as Tensorflow al. (2021) D); De et al. (2022); Kurakin
2(XLA), JAX and Pytorch [i et al. (202T); Subbamani et al. (022), where remarkable speed difference has been observed in some cases, even with the same implementation. For example, [Subramani et al. (202T) implemented DP-SGD using JAX and claimed its efficiency advantage over the same algorithm using Tensorflow or Pytorch.
1.1 CONTRIBUTIONS
1. [Algorithm] We propose the book-keeping (BK) algorithm that makes existing DP optimizers fast and memory efficient, especially comparable to non-private optimizers. We demonstrate BK via the computation graph in Figure The highlight is that BK only uses one back-propagation and never instantiates per-sample gradients { (CC. LB
(ow J==1
2. [Analysis] We analyze the complexity to show that BK has almost the same time and space complexity as non-DP training, especially when the feature dimension small (see Table 5).
3. [Extension] We strengthen BK using a layerwise decision to mix with Opacus (see Section 3.2 which proves be efficient when the feature dimension is large (and difficult for ChostClip) We also extend BK to the parameter efficient fine-tuning such as DP LoRA and Adapter.
4. [Codebase] We develop Pytorch (Paszke et al. 2019) codebase for our BK algorithm, leverag- ing the auto-differentiation technique on the computation graph and new trick in Appendix
5. [Experiments] We demonstrate the amazing efficiency of BK on training large models, saving the memory up 10x and boosting the speed by 30% 5x than previous DP implementations.
Time /Epoch
Relative Speed
Dataset
SOTA setting
Model
over GhostClip over Opacus
over non-DP
QQP
Li et al.
2021
RoBERTa-larg (355M)
70:04
I.36x
1,96x
0.77 (0.80x
E2E
Li al.
2021
Garg- (774M)
10:01
1.36x
4.41x
0.83 (0.97x)
CIFAR
et
2022a
BaiT-large (304M)
6:35
1.33x
38.3x
0.76 (0.92x)
Table 1: preview of BK's efficiency on DP tasks (complexity in orange; extended Table 9).
2

---

Under review as a conference paper at ICLR 2023
8c
byj
(bm
241
5())
841
0sg)
BC, Ci dw
WO
ac
dsypu dags
Figure 1: Forward pass and pack-propagation of the 1-th linear layer (standard training is in black; DP training by our book-keeping algorithm is added in red). Here a(t) is the activation tensor, 8() is the layer output, (()) b(t are weight and bias, Li, C the per-sample loss and the summed loss. The dotted arrow represents the inter-layer operation such as activation, pooling, or normalization.
1.2 RELATED WORKS
Previous arts have developed different implementations of the same DP optimizer in Equation (T)
TF-Privacy Tensorflow back-propaggtes vectorized loss (..,,...444 Lpl to compute the per-sample gradients, each from one back pack-propagation, which is memory-efficient but slow. Opacus Yousefpourr al. (202T) and Rochette al. (2019) accelerate the training significantly using the outer product trick in Goodfellow et al. (2014), though incurring heavy memory burden so as to store the per- sample gradients. This memory burden is partially alleviated in FastGradClip Lee & Kifer (2020) by sharing the space complexity in two rounds of back nack-propagation. hence almost doubling the time complexity. In ghost clipping Goodfellow (2015): [i et al. (202T); : [u et al. (2022a). the per-sample gradients can be clipped without being instantiated, thus both time and space complexity can be further improved if the feature dimension is small. We refer interested readers to Figure and Appendix for algorithmic details of these implementations.
We now compare BK to different implementations in Table and Figure 2 In what follows, B the batch size Tin is the feature dimensior d(t)= P(t) are the input output dimension of layer.
Non-DP Priiviiyayy Opacus FastGradClip
ChostClip K
BK (ours)
Instantiating per-sample grad Storing every layer's grad Instantiating non-DP grad
X
/
X
x
x
x
X
x
X
Number of back-propagation Time Complexity of Clipping Memory Overhead to non-DP O
1
2
2
6HTPd
8BTpl 6HT Bpd
8BTpd Bpd
10BT + O(BT2)
su 6B7
2BT2
min (2
BTpd)
Scalable to large model Scalable to high-dim input
X
X
X
Table 2: Summary of different DP implementations on linear/convolution layer R Bxy x 7
R PBxTaxXPu XPo), The main bottleneck marked in red.
1.3 PRELIMINARIES
We work with the (c, DDD by Dwork et al. (2006), which makes it difficult for any privacy at- tacker to distinguish or detect an arbitrary training sample, even with full access to the model (see Appendix A for details). In deep learning. DP is achieved by training the private gradient in Equation T with any optimizer such as SGD, Adam, FedAvg, etc. Essentially, the private gradient the addition of Gaussian noise to the sum of clipped per-sample gradients, which guarantces the DP protection through the privacy accounting theorems Abadi et al. (2016); Mironov (0077: Dong
al. (2019); Zhu et al. (202T): Gopi al. (021)); Koskela et (2020).
We report the physical batch size, which affects the efficiency; the accuracy is only affected by the logical batch size, which can he implemented through the gradient accumulation of physical batch size.
For non-sequential data, 7 = 1; for texts, T is the sequence length, which is layer-independent; for images (or videos), T(y is the wightxxiddhh xime) of hidden feature representation, which is layer-dependent.
3

---

Under review as a conference paper at ICLR 2023
Nan-DP BK (oun))
Hamey (08)
GhostC
FartGredCip
Cp
1B 36
liserieet
Spend
Speed Iberiaeci
Speze Iibrbaec
Speed and memory on MI.P and CIFARTO0 (images are flattened into vectors). Left to right: deep network (50 layers, width 1000, 50M parameters, batch size 1 128), shallow network (10 layers, width 1000, 10M parameters, batch size 128), and wide network (10 layers, width 5000, 250M parameters, batch size 128 or 1024; Opacus is OOM). See more ablation study in Appendix F
Figure 2:
2 BOOK-KEEPING: EFFICIENT DP TRAINING IN LOW DIMENSION
The main computational bottleneck of DP training comes from the per-sample gradient clipping. or from the computation of per-sample gradient norms, to be exact. One widely used approach in Opacus, TF-privacy, and FastGradClip. is to instantiate the per-sample gradients and then deriving their norms. forwigh implementation of this approach on mini-batch of per-sample losses requires B rounds of pack-propagation (unacceptable slowdown) or Bx gradient storage (unaccept- able memory burden; see Opacus in Figure 2). Consequently, these implementations are not suitable for large model training. For instance, Li al. (202T) shows that, when training GPT2-large (774M parameters), Opacus Yousefpour et al. (2021) and JAX (Subramani al. (202)) cannot fit even one
single sample into 24GB GPU.
An alternative approach, termed the ghost clipping (GhostClip), directly computes the per-sample gradient norms without computing the gradients themselves. This is made possible, unfortunately, through two rounds of back- propaaatioo. During the first back pack-propagation, one uses the regular loss E; f, and extracts the activation tensor and the output gradient (a. de One can use an algebraic
trick in Equation (2) to compute the per-sample gradient norms {Il s |];; and the clipping factors
{C;}; in Equation (T). During the second back-propagation. one uses the reweighted loss Σ, C,C: whose gradient directly the weighted gradient Σ, Cigg, which constitutes the private gradient we need. Note that this double back- propagation roughly doubles the training time (or to be more
precise, 10/6 1.667x when T small; see T
E
2-
Cigh PROOUL)
Figure 3: Standard (non-DP), Opacus, FastGradClip, GhostClip, BK implementations. Notice that BK learns to directly compute weighted gradient from Opacus, to compute the ghost norm from GhostClip, use auto-differentiation instead of full pack-propagation from FastGradClip.
To make the DP training as efficient as the standard training, we propose the book-keeping technique (BK) that (1) only requires single back poo--prop,g,tion, like Opacus and standard training; (2) does not instantiate the per-sample gradients, like GhostClip.
2.1 BOOK-KEEB KEEPING ALGORITHMS
BK algorithms in their base forms are built on GhostClip and especially the ghost norm trick, so as avoid instantiating the memory costly per-sample gradients: as can be seen in Algorithm and ac. BC, is not computed throughout the training. In comparison to GhostClip, our Figure aw- ag 8a,
4

---

Under review as a conference paper at ICLR 2023
significant improvement is solely on the speed (see Table through two novel tricks: the book- keeping and the ghost differentiation. The entire BK algorithm is built on the understanding of computation graph in Appendix AJ Note that these tricks also offer improved efficiency for existing We now elaborate on these tricks.
implementations, to be presented in Section 2.4
BK (base) = ghost norm + book-keeping + ghost differentiation
from GhusaClip
OuTS
ours
Algorithm 1 Differentially private deep learning with BK algorithm (one iteration)
Parameters: 1-th layer weights W W(1j. number of layers L, noise level a.
I: for layer 1 E 1,2, ... L do
2: Get activation tensor {a. by Pytorch forward hook
3: for layer I L, L 1, ... do
4: Get output gradient { (o by Pytorch backward hook
5: Compute per-example gradient norm ||
@ 9C.,
|| by ghost norm trick in Equation 2
6: Aggregate gradient norm across all layers:
BC lw
|| Σ,
ow (
OC,
|
7: Compute clipping factor: C, = C(I de
|l; R)
8: for layer E L, L - ......... , do
8c 9: Compute sum of clipped gradients G any diag(Cin (1,, .2,...) )a(
10: Delete {a . {
)6_
11: Add Gaussian noise G = G oR RR-NNO,.1
12: Apply SGD/Adam/LAMB with the private gradient G on W
Ghost norm trick The ghost norm trick Goodfellow (2015) computes the gradient norm without the gradient: while the gradient is instantiated by the multiplication in Equation (2), the gradient norm can be computed without a, meeting Bs. including the linear, the embedding Li et al. (02T), and the convolution layers Bu al. (2022a). We demonstrate this trick using a simple linear layer s; a; W. where W E R is the weight matrix, E IR 7xxx is the mini-batch input of this layer (a.k.a. the activation tensor) and Bxxxp ØL
ac This applicable generalized linear layers
is the output. Given that the output gradient 82 is readily available in the back-propagation, for DP and standard training, one can directly derive the per-sample gradient norm
0L; dW
Ös; 0s; 06.) ) vec (a;a,) without computing ow a, Ös:
0C OL
OC: a. Oc
vec
Frobenius
Here 'vec" means flattening the 7 T matrix vector. This trick is particularly efficient when T is small, reducing the space complexity from ((Bdd) to O(BT2) by Table 3
Book-keeping trick This trick improves the time complexity by re- moving the second pack-propagation from GhostClip. Our idea is to ac, which is deleted after the first back-propag of GhostClip and must be re-computed during the second back propppaapaat.on.. The difference between GhostClip and BK is clearly illustrated via line-by-line comparison in Appendix C.I In fact, denoting the total number of model parameters as M --=3 Σ1 P(yd()) our trick reduces the time complexity from 10BTM + O(BT2) by Ghost- Clip 8BTM + O(BT²) according to Table In contrast Opa- cus, which book-keeps the per-sample gradients g. using O(BM) = O(B Σ, (()) memory, we instead book-keep the output gradient with substantially cheaper O(BT EtP()) memory for small T.
book-keep and re-use the output gradient Baco)
ac/os
acraw,
a.//sp
aci Bhye
a.r/W
ac/Os,
ac/dtgr
aL/8
al/aw
aciss
:
azráw;
aL/aw;
Non-DP DP
DP (BK)
Ghost differentiation trick ity on the first propaaaoong in GhostClip. further reducing from 8BTM + O(B2)) to 6BT M + +(BT²2 in T Our idea is to only compute the output gradient ac but not the parameter gradient ac Daay
This trick improves the time complex-
Figure 4: Backward
propagation of BK algo- rithm (C = Σ, C,C.).
aw-
5

---

Under review as a conference paper at ICLR 2023
That is, we break the 4BTM time complexity of the full pack-propagation into sub cub--rrceesss,, each 2BTM complexity, and remove the unnecessary one.
To be more specific, during the back-propagation of Opacus and GhostClip. the output gradient dc ac
and then the parameter gradient eW
0c
are computed. However, we can stop after we obtain ös
ac, only need the output gradient to compute the clipped parameter gradient 0E, C,C. aw in Line of Algorithm|] [ Therefore, the ghost differentiation trick sets all parameters to not require gradients (see technical details in Appendix D.2 including the origin parameter trick that propagates on computation graph even when no parameters require gradients).
2.2 COMPLEXITY OF DP IMPLEMENTATIONS MODULAR ANALYSIS
In this section, we analyze the complexity of DP implementations from their opearation modules. We summarize the time and space complexity Table and give the derivation in Appendix We
will refer to these modules by indices, e.g.
2a for the computation of output gradient.
Module
Forward pass
2 Ghost norm
Per-sample grad
( Weighted sum
(a)output gradient (b)parameter gradient
instantiation 2BT
per-sample grud
Time complexity
pBTpd
2BT pd
2BT pd
2BT d)
2Bpd
Space complexity
pd + BT4
BT BTip- d)
pd
281
Epd
Table 3: Time and space complexity of modules in DP training for one generalized linear layer.
Now we are ready to decompose each implemen- tation, following the flowcharts in Figure 3 Con- sequently, we can easily write down the complex- ity of different implementations in Table Such modular analysis displays the clear effects of the
Standard (non-DP)=
1 +
24
3h
tricks in BK algorithm: the ghost norm trick re-
Opacus= 1 +
2h
moves the memory costly from Opacus and FastGradClip: the book-keeping trick removes the
FastGradClipp + 2n
+
2h
GhostClip- 1 +
2h
2b in the second pack-propagation of FastGrad- Clip and GhostClip; the ghost differentiation trick removes the 2b in the first back-propagation of Opacus and GhostClip.
BK (ours)=
2.3 BK IS OPTIMALLY EFFICIENT IN LOW DIMENSION
When the feature dimension T' is small, we claim that BK is almost as efficient as the standard non-private training, with negligible O time and memory overhead by Table
Memory complexity: non-DP ~ BK ~ GhostClip FastGradClip < Opacus
Time complexity: non-DP 2e BK < FastGradClip = Opacus < Ghosttlip
Now, we discuss the cases where the data has low dimension and thus 7' is small. Generally speak- ing, the feature dimension T depends both the data and the model.
For non-sequential input and ID audio data, T = 1. For sequential data such as texts (T being sentence length) time series (I' being time duration). Tin fixed across layers. In this case. BK is efficient on short-sequence datasets including GLUE Wang et al. (2019) (c.g. SST2/NNLI/MNLIION
and natural language generation datasets (e.g. E2E/DART), since 72 < Payda- For instance, Yu et al. x Li et al. (2021); Bu et al. (202b)) applied GPT2 on E2E dataset, which has a sequence length T 100 and the number of parameters P()) per layer is 2 4M: Yu et al. (2021): Li et al. 2021 applied RoBERTa-large on GLUE datasets, which has sequence length 7 256 and the number of parameters per layer is 4M. As illustrated in Fig- ure 5 and Table (extended in Table 9. BK improves the throughput of existing implementations
by 25 388% on multiple language tasks in Li et al. (202I); Bu et al. (2022b), with minor memory
overhead compared to GhostClip and non-private training.

---

Under review as a conference paper at ICLR 2023
However, the convolution layers with image data, T(t) is the product of hidden feature sizes (c.f. (Bu et al. 2022a, Section 3)), thus Tnn depends on the original image size and network architecture. For example, larger kernel size/dilation//stride in convolution layer reduces Tay, while larger images have larger (n) at each layer. Therefore, BK (and GhostClip) may suffer on when training ResNet on ImageNet (224 x 224), as we show Figure (see also (Bu et al. 2022al Table 7)), although training the same network efficiently on CIFAR10/ION (32 x 32).
Masiiuu bvan pane MMV
glesttip
Opacis
66
80
42 54
40
20-
Max
Thesughpt 5012 Througoutt ONU
Thrugtout
Thrughput
Figure 5: Memory and speed of different implementations. Upper: GPT2 on E2E dataset (fixing B, DP speed is 0.86 ~ 0.89x of non-DP). Lower: RoBERTa-large on GLUE datasets. Note here the hybrid implementations are equivalent to the base ones, because of the short sequence length.
2.4 APPLYING OUR TRICKS TO EXISTING IMPLEMENTATIONS
can also improve other existing implementations, reducing the time com- plexity of GhostClip from 10BTpd 2BT (p + d) to 6BT pd + 2BT (p + d). that of Opacus and FastGradClip from pd to 6BTpd. We highlight that these improved implementations are leveraged to design hybrid implementation in Section 3.2 In addition to DP full fine-tuning, BK is demonstrated in Appendix E.2 to also apply to the parameter efficient fine-tuning like Adapters.
Our tricks in Section 2.1
phost diflerentiation
GhostClip =
+
2
2b
(our BK)
book keeping
Opacus
+
2a
ghost difforentiation
24
FastGradClip = +
2n
7b
book node-keeping
7b
HYBRID BOOK-KEBS KEEPINE EFFICIENT DP TRAINING IN HIGH DIMENSION
In previous section, we have analyzed DP implementations in the small T regime, where ghost norm-based GhostClip and BK are efficient. Nevertheless, in the large T and large model regime, none of the base implementations may be efficient (see Figure 6 and we turn to hybrid methods.
3.1 LARGE T' NECESSITATES NON-GHOST NORM METHOP
closer look the space complexity in Table shows that, the ghost norm trick is favored over the per-sample gradient instantiation if and only if 2T?, < P(r) where P(r)d()) is the number of parameters one layer. When this criterion is violated for large T. GhostClip/BK can significantly under-perform Opacus/FattGradClip as shown in Figure Figure 7 and Table 10
Similar to Section 2.3
discuss two cases where T is large. For paragraph or document-level
language tasks like WikiHop Welbl et al. (2018) and TriviaQA Joshi et al. (2017). ) T can range from 2000 20000, which makes 27 at each layer with large values on top layers, as the features are less compressed by convolution and pooling. Taking ImageNet and the first convolution layer of VGG11 example (Bu al. 2022a
800M. For image tasks, particularly CNN, T(t varies

---

Under review as a conference paper at ICLR 2023
Table 3), (T) = x 10 > P()d(()) = 1.7 103. Consequently, ghost bosm-based implementa- tions (i.e. GhostClip and BK) costs more than 40GB memory ResNet18, under B 32, while Opacus only costs 2.5GB. This curse of dimension grows from a difficult issue on ImageNet to an impossible challenge videos or high-resolution images, e.g. GhostClip cannot train ResNet18 with even one single CelebA-HQ image (1024 x 1024) using a 40GB GPU.
In short, the ghost trick is inefficient for large T and the per-sample gradient instantiation is inefficient for large model. Therefore, we must hy hybridize the base implementations.
MuchborCC
FILLS 1M6EO07
Fisit *jutdwesion"
Figut vireaar
Iigut dineriio
Figure 6: Memory and speed by different implementations on 50000 images. Left: VGGII (133M(Simonyan Zisserman (2014),, right is BEiT-large (304M:Bao et al. (202I)). Memory
cost uses physical batch size I. Throughput uses the maximum phy ohysical batch size.
3.2 HYBRID IMPLEMENTATIONS VIA LAYERWISE DECISION
We adopt the same layerwise decision as Bu et (022a)) known as the mixed ghost norm tech- nique: we use the ghost norm trick on layer if 27 P() and instantiate per-sample gradients otherwise. Therefore, the space complexity of computing the per-sample gradient norm reduces to min
(() ( }. which is significantly cheaper than either the ghost norm or the per-sample gradient instantiation in high dimension, as depicted in Table and Figure 7 Consequently, over all layers, the space complexity is lower than both constituting methods, e.g. saving more than 10x
memory for the per-sample gradient clipping on ResNet18 (see more models in Table I0).
Ouiput
Space complexity
18-layer
34-layer
50-layer
War
Por-sample grad instantiation
Per-sample grad instantiation
Per-sample grad instantiation
Ghost norm
Ghost norm
Ghost norm
22) 242 waa
Poyd params
22
Payda
22
Paydo
convi
112 x 112
3.1 x 10
9.1 x 10"
3.1 x 10
9.1 x 10"
3.1 x 10"
9.4 x 10"
10a
conv2.x
56 56
(2.0 x 10" x
[3.7 x 104]
2.0 x 10 x
[3.7 x 10*) x
12.0 x 10 x
[3.7 x 10
[1.6 x 10
17.4 10*]
10
2.0 10
[3.3 x 10*
conv3.x
28 x 28
[1.2 10" x
[1.5 10
112 10 x
[1.5 x 10 x
109
[6.6 x 10*]
[1.5 x 10
10*)
[2.6 10
[12 109
[1.8 x 10
conv4.x
14 x 14
[7.7 x 10"] x
[5.9 105]
[7.7 x 10 x 12
[5.9 104]
x.7
12.6 10 x
[5.9 10
[1.2
x
conv5.x
7
[4.8 x 10") 4
x 10"] x
[4.8 10 6
[2.4
[4.8 x ]
110 10 x
[2.4 x 10")
Total complexity
52HM
Complexity
mixed ghost
1.0
2.3M
2.8M
Table 4: Space complexity of the per-sample gradient clipping (not the entire DP algorithm) for
B = on ImageNet 224 x 224. Layerwise decision of hybrid BK algorithms is highlighted in bold.
In contrast to the mixed ghost clipping (MixGhostClipp) in Bu al. (202aa). which hybridizes Fast- GradClip and GhostClip. we boost the efficiency by hybridizing our BK with the improved Fast- GradClip/Opacus in Section 2.4 We propose BK-MixOpt (and BK-MixGhostClip as an intermedi- ate product only for comparison) and use MixGhostClip as reference point,
MixGhostClip !
26 min
min (GhostClip, FastGradClip),
BK-MixGhostClip
min
min (BK, improved FastGradClip),
BK-MixOpt=O0 0
min 26
min BK.
min improved Opacus).
8

---

Under review as a conference paper at ICLR 2023
The hybrid BK algorithms are presented in Algorithm 5 We summarize the layerwise complexity in Table from which we derive the overall complexity in Table 8aleeBan and observe that BK has almost the same complexity as non-DP training. Note that in low dimension, the mixed ghost norm is equivalent to the ghost norm, hence MixGhhstClipp/KKMMixxx
is equivalent to GhostClip/BK, respectively.
Method
Type
Modification previous variant
Time complexity
Space complexity
6d77pd
3BT BIp
Opacus
Instantiale per sample gratleeni
537pp
Bpd 33Td BTF
PastGradClip
Not store per-samplc gradiont
8/7pp
Bpd 28T4 BTp
using second pack-propogation
base
Not instantiate per-sample gradient
GhostClip
WBBI 2B
2BT 3BTd BTy
using ghost norm trick
BK (ours)
Simplify the two back propagations
6RTPd (BT
2BT 3/T4 BTp
MisChostCCip
8.1 pdl + (281 pd. 28T "ip dy
min 225T Bpd] 351d 111
BK-MixGhostCiip hybrid
Mix ways compule grad
G33 pd (2B1 2ET "p
min (2BT" Bpd 331d BTP
min
BK Bp-MixOpt
Mix ways compuie weighted grad
6BTpd 10,257 3
min (2BT Bpd] 3BTd BIP
Table 5: Complexity of DP implementations one layer. Here () means between two values. The pd].
time complexity of BK-MixOpt 6BTpd + 2BT2 + d) 1s27
3.3 EFFECT OF MODEL ARCHITECTURE & FEATURE DIMENSION ON HYBRIDIZATION
We dive deeper understand when the hybridization favors the ghost non-ghost norm tricks.
From a model architecture viewpoint, transformers such as ViT, RoBERTa, GPT tend to prefer the ghost norm: for moderate-sequence text data and moderate-dimension image data, hybrid BK algo- rithms are close or equivalent to the base BK algorithm (see right-most plot in Figure 7 However, CNN prefers the per-sample gradient instantiation at top layers, and there exists depth threshold below which the ghost norm is more efficient. Hence the hybridization is necessary to take advan- tages of both worlds. From the feature dimension viewpoint, larger input means this depth threshold is deeper, e.g. from the 9-th layer of ResNet18 to the 17-th layer in Figure 7 when the image size increases from 224 224 to 512 x 512. We visualize this effect of feature dimension on various models in Appendix G
Byer
Figure 7: Layerwise space complexity of computing the sample gradient norm. Left to right: ResNet18 (224 x 224), ResNet18 (512 x 512), VGG11 (224 x 224), and ViT-base (224 x 224).
DISCUSSION
In this work, we propose the Book-Keeping (BK) algorithms to effciently implement DP optimizers using three tricks: ghost norm, book-keeping, and ghost differentiation. Our BK reduces the time and space complexity of DP training to the similar level of the standard training. Specially, we develop hybrid BK to overcome the computational challenge of training large models with high- dimensional data, and we extend BK to parameter efficient fine-tuning such as LoRA and Adapter.
One minor limitation of this work is that BK (and GhostClip) only applies the weights, the biases, of the generalized linear layers, i.e. embedding, linear, and convolution layers, though these weights constitute 99.9% of the trainable parameters (see Table 7 Implementation-wiss, although BK should be as fast as the standard training for small T. e.g. on MLP where T = 1, we observe some gap between the theoretical complexity and the throughput in practice. This gap is mainly due to the mechanism of Pytorch hooks which can be possibly optimized by customizing the CUDA kernel using the symbolic programming.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian 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.
Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei. Beit: Bert pre-training of image transformers.
In International Conference on Learning Representations, 2021.
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23), 2020.
Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Hanwen Shen, and Uthaipon Tan- tipongpipat. Fast and memory efficient differentially private-sgd via jl projections. Advances in Neural Information Processing Systems, 34, 2021.
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. arXiv preprint htt.:2205..0688 2022a.
Zhiqi Bu, Yu- Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. arXiv preprint arXiv:2206.07136, 2022b.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp. (633-2650, 2021.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-2582 Icee, 2009.
Jinshuo Dong. Aaron Roth, and Weijie Su. Gaussian differential privacy. arXiv preprint arXiv:1905.02383, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An im- age is worth 16x16 words: Transformers for image recognition at scale. In International Confer- ence on Learning Representations, 2020.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265 284.. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407 2014.
Ian Goodfellow. Efficient per-example gradient computations. arXiv preprint arXiv: 151.0199,, 2015.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34, 2021.
Niv Haim, Gal Vardi, Gilad Ychudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. arXiv preprint arXiv:2206. 2207:2200..77558 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2023
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, An- drea Gesmundo, Mona Attariyan, and Sylvain Gelly, Parameter-efficient transfer learning for nlp. In International Conference on Machine Learning, pp. 2790-2799. PMLR, 2019.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Wang. and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprini (rXiv:2/06.09668 2021.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of the 55th Annual Meet- ing of the Association for Computational Linguisties (Volume 1: Long Pupers), pp. 1601-1611, 2017.
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pp. 2560-2569. PMLR, 2020.
Alexey Kurakin, Steve Chien, Shuang Song, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta. Toward training at imagenet scale with differential privacy. arXiv preprint arXiv:2201.12328, 2022.
Jaewoo Lee and Daniel Kifer. Scaling up differentially private deep learning with fast per-example gradient clipping. arXiv preprint arXiv:2009. 20t.:20099031066.. 2020.
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be
strong differentially private learners. arXiv preprini arXiv:21 10.0:///00006799 2021.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 16692, 2019.
Rabeeh Karimi Mahabadi, James Henderson, and Sebastian Ruder. Compacter: Efficient low-rank hypercomplex adapter layers. arXiv preprint arXiv:2106.046/4 2021.
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Pro- ceedings of the 18th ACM international conference on Multimedia, pp. 1485-1488, 2010.
Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky. Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:2205.02973, 2022.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundatioss sympo- sium (CSF), pp. 263-275. IEEF, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9 2019.
Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. arXiv preprint arXiv: 2019.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference tacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.

---

Under review as a conference paper at ICLR 2023
Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and vectorization. Advances in Neural Information Processing Systems, 34, 2021.
Tensorflow. Tensorflow/privacyy: Library for training machine learning models with privacy for training data.
com ctt/://ccootttt/eeeeeeteeeeeteet wwwo//tttoortooocoooooooooeeoooe htwp:oowiiiiiaeeeee
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). arXiv preprint 1.Xiv:201 1660, 2020.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. 2019. In the Proceedings of ICLR.
Johannes Welbl, Pontus Stenetorp, and Sebastian Riedel. Constructing datasets for multi-hop read- ing comprehension across documents. Transactions of the Association for Computational Lin- guistics, 6:287-302, 2018.
Ross Wightman. Pytorch image models. 2019.
https:///githb...ommm/ rwi gwtman...
sytorch-image-moode
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gug- ger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38-45, Online, October 2020. As- sociation for Computational Linguistics. https:/ www. aclweb wwt.oorgg//aaa.oo. wwt.e/tooog/ttggg//////o
2020. emnlp-demos.6
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library PyTorch. arXiv preprint
arXiv:2109. 12298, 2021.
Da Yu. Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. arXiv preprint arXiv:2110.06500 2021.
Yuqing Zhu, Jinshuo Dong, and Yu- Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. arXiv preprint arXiv:2106.08567 2021.
12


Reviews:
[{"review_id": "vitGNGZpD-", "reviewer": "Reviewer_ac6D", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new trick to improve the runtime of DP training with GhostClip. One large cost in DP training is the computation of the per example gradient, which must be clipped before being averaged, so that no example can have an outsized influence on the model. The authors enhance a previously known trick to reduce this cost.\n\nGhostClip, proposed in 2015, allows the computation of the norms of the per example gradients efficiently (i.e. without storing the per-example gradient). Then GhostClip uses a second backpropagation pass to compute the gradients of the weighted loss --- the weighted loss is the sum of the loss for each example weighted by the norm of its gradient, thus achieving clipping.\n\nIn the current paper, the authors propose to store the per example gradients of the outputs in the first pass, while computing the norms of the per example gradients. These are used to recompute the gradient of the weighted loss, without needing to use a second backprop pass. Since only the per example gradients of the outputs are stored, and not per example gradients of the parameters, this memory is substantially less than the memory used in standard DP implementations.\n\nThe paper then points out that the GhostClip trick works well only when the number of features in a layer is small (each layer's input is of size batchsize * features * channels). For layers where the number of features is large (e.g. the initial layers of a ResNet for ImageNet), the authors do not use GhostClip, instead keeping per example gradients of the parameters. Thus they are able to reduce the huge memory requirement of GhostClip for these cases.", "summary_of_the_review": "The paper seems to me to be very clear and useful. My only concern is with the question above, hopefully the authors can address it in the discussion.", "strength_and_weaknesses": "The paper explains the implementation very well, comparing nicely against various previous algorithms. It also describe the limitations and the resulting hybrid algorithm well.\n\nThe authors mention two tricks, but it was not easy to distinguish these.  Q: What is the purpose of Line 8 in Algorithm 2? The output is not used anywhere else in the code. This is mentioned as one of the two important tricks in the paper, and adds considerably to the time and memory requirements of GhostClip.\n\nThe main novelty is in the implementation of the tricks --- the trick itself is straightforward --- instead of recomputing the gradients, the authors store them from the previous pass.\n\nIn equation 2, you multiply 2 vectors --- should this be a dot product?", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "bH6TNLqaST", "reviewer": "Reviewer_cPLw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "the paper proposes a (pytorch-based)  implementation for summing clipped per-sample gradients in DP-SGD and demonstrates empirical gains in terms of compute time. ", "summary_of_the_review": "the paper proposes a (pytorch-based)  implementation for summing clipped per-sample gradients in DP-SGD and demonstrates empirical gains in terms of compute time. the trick is new to the best of my knowledge, but the paper has several technical issues. ", "strength_and_weaknesses": "strength: the authors show empirical gains for common setups of DP training in terms of wall-clock time compared to previous approaches. \n\nweakness: the paper has several weaknesses, some of which are technical and the others are related to presentation. \n\ntechnical weaknesses: \n\nwhile the idea for modifying FastGradClip may seem natural, it's worthwhile to note that the current presentation is heavily based on a particular framework -- PyTorch. for instance, Algorithm 1 explicitly states the procedure quoting PyTorch forward and backward hooks. i believe the high-level idea is applicable in other frameworks, but the current algorithmic sol'n is limiting and isn't designed based on shared primitives of automatic-differentiation framework. \n\nin the main text and appendix C, the authors argue that one major difference between BK and GhostClip is that BK doesn't compute non-private gradients. note that GhostClip need not compute non-private gradients at all, since this quantity is not used anywhere. in fact, computing the non-private gradient is likely an artifact of a particular implementation and is not a general drawback of the approach (of course, neither is this a drawback / limitation of FastGradClip). by not considering this point, the authors likely have \"inflated\" their computational advantages. \n\nthe authors make several factually incorrect claims. for instance on page 4, authors say \"For instance, Li et al. (2021) shows that, when training GPT2-large (774M parameters), Opacus Yousefpour et al. (2021) and JAX Subramani et al. (2021) cannot fit even one single sample into a 16GB GPU.\" \n  - note the original paper by Li et al. does not present profile results with GPUs which have 16GB video RAM. the selected GPU is TITAN RTX which has 24GB video RAM.", "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": "7nBfLZy69b", "reviewer": "Reviewer_QN3z", "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": "", "summary_of_the_paper": "This paper implements existing DP optimizers with 1.24x training speed than the most efficient competitor. Previous methods accelerate the DP training speed by using two rounds of back-propagation or sacrificing memory. This paper uses one back-propagation and never instantiates per-sample gradients so that it reduces computational costs. ", "summary_of_the_review": "The novelty of the paper seems low, and the propose solution only achieves minor improvements against the state of the art.", "strength_and_weaknesses": "Strength\n\n1. Table 2 provides a clear and comprehensive comparison of the existing methods.\n\n2. The paper provides a complete comparison of pseudo-codes for their algorithm and the competitors.\n\nWeaknesses\n\nW1. The paper combines some tricks from existing works to save computational costs of deep learning with DP. However, when comparing their code with SOTA, it seems that the proposed algorithm only replaces one summation step with matrix operations, which lacks novelty.\n\nW2. The paper repeatedly emphasizes that it can reduce the time and memory complexity of DP deep learning. However, the actual reduction is only a constant (\"1.24× training speed in practice\").  Moreover, according to the experiments in Figures 2 and 5, when the input dimension is large, the proposed algorithm only shows minor improvement in time or memory compared to the state of the art.\n\nW3. Figure 3 is difficult to read.\n\nW4. The paper is not self-contained in the sense that it refers to a number of tables in the main text, without mentioning that those tables are only available in the supplementary material.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "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:

Decision: Reject