A Unified Fast Gradient Clipping Framework for DP-SGD
Authors: Weiwei Kong
Andres Munoz medina
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
dp-sgd
gradient clipping
computational complexity
TL;DR: This paper presents a framework that unifies existing gradient clipping techniques and improves upon them.

Abstract: A well-known numerical bottleneck in the differentially-private stochastic gradient descent (DP-SGD) algorithm is the computation of the gradient norm for each example in a large input batch. When the loss function in DP-SGD is consists of an intermediate linear operation, existing methods in the literature have proposed decompositions of gradients that are amenable to fast norm computations. In this paper, we present a framework that generalizes the above approach to arbitrary (possibly nonlinear) intermediate operations. Moreover, we show that for certain operations, such as fully-connected and embedding layer computations, further improvements to the runtime and storage costs of existing decompositions can be deduced using certain components of our framework. Finally, preliminary numerical experiments are given to demonstrate the substantial effects of the aforementioned improvements.

A Unified Fast Gradient Clipping Framework for DP-SGD
Weiwei Kong Google Research weixe:kong@google.com
Andres Muñoz Medina Google Research ammedina@google. com
Abstract
A well-known numerical bottleneck in the differentially-prives stochastic gradient descent (DP-SGD) algorithm is the computation of the gradient norm for each example in large input batch. When the loss function in DP-SGD consists of an intermediate linear operation, existing methods in the literature have proposed decompositions of gradients that are amenable to fast norm computations. In this paper, we present a framework that generalizes the above approach to arbitrary (possibly nonlinear) intermediate operations. Moreover, we show that for certain operations, such as fully-connected and embedding layer computations, further improvements to the runtime and storage costs of existing decompositions can be deduced using certain components of our framework. Finally, preliminary numerical experiments are given to demonstrate the substantial effects of the aforementioned improvements.
Introduction
Machine learning models more specifically, neural network-based models becoming more popular in industrial applications, in user-facing products, and different scientific fields. The popularity of these models lies on their flexibility and ability to be trained which may contain personal information about individuals. As these models become bigger and more descriptive, MI. practitioners need to ensure that the models, and their black-box interactions, do not reveal information about the data used to train the model. In fact, it has been shown repeatedly [18] that large neural-network models can be used know if a particular example was used in the training data. Another line of attacks has demonstrated that one can actually reconstruct some training instances with simple interactions with a trained model [3].
ever bigger datasets,
The only known robust way of protecting against these attacks is to train models using differential privacy [10, 11]. Using this approach, ML practitioners provide information theoretic guarantee that ensures that the final model does not depend on any individual example'. To date, the most popular method for training models with differential privacy is the differentially private stochastic gradient descent (DP-SGD) [1] method. In theory, the DP-SGD algorithm requires only minimal changes with respect its non-private counterpart; one only requires to clip gradients observed in the training process and add some noise proportional to the clipping value. However, in practice, the (naïve) gradient clipping step has been shown increase memory and computational costs in all popular learning platforms (JAX, Tensorflow, and Pytorch). More precisely, for a batch of size a naive implementation of DP-SGD requires calculating n gradients (one for each example in the batch) so they can be clipped. This is in stark contrast with most back- propagation based training algorithms which calculate single gradient. This implies dependency on the runtime and memory in proportion to the batch size used to train the model, and for large models, this cost makes the
In particular, it is impossible distinguish whether reconstruct it.
individual example is in the dataset, let alone
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

prospect of training with differential privacy simply not viable. Several papers [8, 17, 21] have also observed that large models need be trained with large batch sizes obtain competitive levels of utility, under reasonable amounts of privacy.
In [12], it was recognized that one could clip gradients without actually materializing every example gradient. This technique is referred to as ghost clipping. The initial proposal from [12] was specialized to fully connected, feed-forward neural networks that consist of only dense layers. The ghost clipping algorithm was later extended to handle convolution layers [13, 15] and attention layers [14].
However, each of the above solutions required an ad-hoc analysis on the correctness of their implementation. In this work present a general analysis of the ghost clipping algorithm. To produce our results, we study this algorithm from the lens of linear operator theory. Our paper has three main contributions:
1. We unify years of ad-hoc analysis and interpretations of the ghost clipping algorithm under a single framework.
2. We provide a future-proof way of expanding the ghost-clipping technique to new layers with (possibly) nonlinear dependencies on their weights.
3. We demonstrate that by framing the ghost clipping problem in the language of linear operators, we can obtain a better performance of DP-SGD on models with embedding layers (crucial for personalization models consisting of embeddings of tens of millions of parameters) and fully connected layers with linear bias broadcasting operators.
Additionally, we show in our Appendix how to apply our framework to more complex tranforms/layers such as layer normalization and multi-head attention.
To complement the results of this paper, we open-sourced the general interface of the code using the TensorFlow Keras API By introducing an abstract interface, we also expect practitioners to easily extend the ghost clipping algorithm to any type of layer.
Notation and preliminaries
Throughout the paper, (W, (.,-)) denotes Hilbert space and || denotes its induced norm. Examples of W are IRd with the standard dot product and the space of matrices W = RPx4 with the Euclidean (Frobenius) inner product between A, B E W given by (A, tr(AT)) B). For two
matrics A, B we let ||A|] denote the Frobenius norm of A.
Given two Hilbert spaces (W, (:,(--/w), (2), (-)))y), denote linear operators between them by italicized letters (A: W -> and A" : - W to be the adjoint of A. That is, A is the unique linear operator that satisfies
(1) Let (W, (w) and (J), ()) denote two Hilbert spaces with respective induced norms Ilw and || [,y. Moreover, let 1/ W + Y' be an arbitrary function. The Fréchel derivative of a/s at wo E W given by the unique bounded linear operator (wo): W-4 satisfying
(y, Aw) =
( (A"y, w)
EWW, Vy EV.
[ + 5) - v(ww)) - Dws =0.
lim
We say di is differentiable its Fréchet derivative exists for all wn E W. Throughout this paper we will use two special properties of the Fréchet derivative: the chain rule and the existence of gradients. Let (Z, (x-)2) 2) be another Hilbert space and Φ: y + Z be given. The chain rule provides us with a simple way to calculate the derivative of the function @ o w: W + Z, namely,
D( (wa) = (ub
The Fréchet derivative of vi at wi with respect to a subset of variables u is denoted by Duo(wo). Finally, (vw(w)) E W denotes the (unique) gradient of a function & at Wa. which satisfies
Dub(wg) = (Vo)(w)) d' Vd W
The existence of the gradient is guaranteed by the well-known Riesz-Fréchet Representation Theorem [16]. The gradient of vb at we with respect to a set of variables is denoted by V (uo()
"See the repo in www.lppyyhhcccoooooeooooooooeeee

---

Algorithm DP-SGD algorithm
Data sample S. parameter initialization wo, number of rounds T, learning rate t, noise multiplier o, clipping norm C.
Input:
Set ulp for t = ,....,To doo do
Get batch of inputs B C Calculate per example gradients = Vil(lr w) for every x E B
Clip gradients 92 min 19 1 1
Calculate private batch gradient 9 [B]
1
ΣZEB Oz + NN,0 Cº |B
Update model w w 119
end for return w
Private Stochastic Gradient Descent We now turn our attention to the DP-SGD algorithm and specifically, to its instantiation for neural network-based models. Let X' be an arbitrary space and S = (x In C X' be sample of examples. Let W denote parameter space and h: X x W denote arbitrary function. The stochastic gradient descent (SGD) algorithm solves the optimization problem
" Σ h(2,, w)
min wEW 72
by iteratively updating the model paramters using gradients of the loss over a batch C S data.
The celebrated DP-SGD algorithm was introduced by [1] as a simple modification on the SGD algorithm to make private Specifically, the DP-SGD algorithm, given in Algorithm identical to the SGD algorithm except in two steps:
1. The DP-SGD algorithm needs to calculate [B] (so-called) per-example gradients in order to clip them to have bounded norm.
2. Adding Gaussian noise N (0, C2 /|B for some noise multiplier o 0.
Notice that the first step has a prohibitively large cost for large networks. Specifically, in the per example gradient calculation, notice that that the computational and memory usage of naïve implementation" of DP-SGD algorithm increases as [B), where nu is the number of parameters in the network. This increase in resources effectively negates the advantages of the backpropagation algorithm. In this paper we show how to run the DP-SGD algorithm with only small constant increment in both the memory footprint and runtime of traditional SGD.
We will focus on the scenario where the learner is trying to minimize the loss across the space of neural networks. That is, the parameter vector is concatenation of k parameters (wi,..., wa) and there exists k functions d1,... ,N. and a loss function & such that
h( w) = E(x, Φx (wk, ( oi (w1 x))).
Note that { correspond to the layers of the network and {wy} are the vectors parameterizing these layers.
3 Previous work
The DP-SGD algorithm was first introduced by [1]. Due to its simplicity to adapt to standard machine learning frameworks now probably the most popular method for training private
When talking about privacy we are referring the concept of differential privacy. We refer the reader to [11] for comprehensive guide differential privacy. this work focus the computational aspects and not privacy properties of DP-SGD algorithm
'Atternativeyy one could consider sequentially computing the gradient norms to remove the linear memory scaling BB However, this approach may prohibitively increase the runtime cost in practice.

---

machine learning models. In the past few years, a large number of papers have been devoted to improving the privacy-utlitty trade-offs of DP-SGD [4] as well as demonstrating that DP-SGD can be used on multiple tasks [7. 9, 21. While the main focus on this line of research has been in understanding the privacy-utility trade-offs, some authors did touch on the performance issues of calculating per-example gradients. A simple solution to reduce the memory and computational blow-up of the DP-SGD algorithm is to calculate the gradient with respect to a micro-batch of examples instead. While this reduced the computational cost of running DP-SGD, it came at the cost of decreased quality of the model learned. Some authors [2] got around this performance issues by using some JIT compilation features of JAX. However these authors still observed an increase in the memory use of their private implementations.
In order to speed up the gradient clipping step without sacrificing quality, [12] proposed the ghost clipping technique (see Section 4). IT's general idea is that one can obtain private gradient estimate ğ without materializing each per example gradient as long one knows the norm of each per-example gradient. Moreover, the authors show that one can easily calculate these norms by using information already materialized in the forward and backward passes of the back propagation algorithm for training neural networks. The results however were limited to neural networks consisting of only dense layers. The ghost clipping trick was later on applied to train transformers [14] and image classification models which consist of networks with convolution layers [15].
The above works provide ad-hoc proofs that their implementation of the ghost clipping algorithm is correct for their particular layer implementation but do not attempt to extend their results arbitrary layers. In this work we present a way to extend the ghost clipping techinque to arbitrary layers and pinpoint what properties of each layer are crucial for enabling an efficient implementation of the DP-SGD algorithm.
Finally, it is also worth mentioning that paper [6] presents an efficient implementation of the ghost clipping technique in PyTorch for models with fully-connected, embedding, convolution, and normalization layers using variable caching avoid recomputing certain intermediate parameter gradients. Our implementation also takes advantage of variable caching, but does this implicitly through TensorFlow's 's GradientTape APIS.
4 The Ghost Clipping Algorithm
Algorithm 1 suggests that in order implement DP-SGD one must calculate every per-example gradient, clip it to achieve a bounded norm and then aggregate it to obtain the private gradient estimate g. The main observation from [12] was that, with knowledge of the norms llgl|z one could estimate 9 without explicitly materializing each per example gradient. To do this, the authors define weights r= min (C/I1g=l1.)) 1} and new weighted sum
5(w)= = Σ rah(a, w). aEB
Treating the weights rz as fixed (with respect to the parameters w), one can use the linearity of the gradient operator to that VS(w) g. Crucially, for neural networks, the gradient of S can be efficiently calculated using a single back-propagation step. The second contribution of [12] was showing that, for neural networks consisting of dense layers, one can also efficiently calculate ||g=|] for every x E B using only single forward and backward pass of the back propagation algorithm. That is, the cost of calculating a private gradient simply twice that of calculating a non-private gradient step.
In the subsections below, we present general formulation for calculating [9g ll in a single forward and backward pass for arbitrary feed-forward neural networks, under the assumption that:
f(x, ), &i (...)..... ( (.,z) x) are Fréchet differentiable for every & E X';
> each function (-).z) can be decomposed as the composition of at least two Fréchet differentiable subfunctions.
SSee https//wwww.aaatloooogggopp/pp/t

---

Algorithm 2 General Gradient Norm Framework
Input: Data x E X, parameter w = (Wi,.... wx), and functions (32,,)imm ZZ Vi satisfying h(2, w) l2 U2,t o Zz (1xz, i l....,k for any 10 (wi...... wx) W, where (x(+) ((x,)).
(5)
for 1,..., do
Compute (r,i Zzz;(
Store "nice" representation (.), (-) of the squared- qguared-norm function + ([ (g)ll
for any gradient g of the function lx o v)xx(())
end for for 1,.... do
Compute 9z,i = V Vi, (Kx (Sa,) and Tu,a == (g
end for return (Ein To,
4.1 The General Norm Calculation Algorithm
Let w (Wi,..., wk) parameterize a neural network. We first note that VV,, w)ll Σ Vi,, h(x, w)ll? Hence, we can focus on efficiently calculating the norm of the gradient corresponding to the parameters of each layer. Let us then fix layer and denote w E W to be its parameter vector for some restricted space W. Moreover, let the input x be fixed. We see that, as function of the layer parameters tē only, the loss h has the form
h(x, w) = la o (10) Ve E.
where oe corresponds to operations performed by the fixed layer and all subsequent layers in the network, and (-))) f(x,-) corresponds to the loss function, e.g., mean-squared error, for the input example x. The following result, whose proof can be found in the Appendix, gives an expression for the gradient of under any decomposition of Φz-
Proposition 4.1. Let E X be fixed and let (lz,0z) be pair of Fréchet differentiable functions satissfyng (3). Moreover, let (1b, Zz) be a pair of Fréchet differentiable functions satisfying 6r = 1z Zn and denote
A Ao( (z), = g=) V(lo (z)
(4)
Then, Vah((, w) A"g
The above result gives us alternative way of computing V m)|l namely, (i) pick decomposition (Vz, Z.) of Φ₂ and (ii) compute g|2 in some efficient manner. In later subsections, provide examples of layers and decompositions where this two-step approach is drastically more efficient than the naive approach of materializing Vah(æ, 1) and computing its Euclidean norm.
In view of the decomposition Proposition 4.1, we present a unified method for computing [VV((z, will in Algorithm 2. Specifically, it consists of two loops over the parameters w;. The initial loop is performed to obtain the intermediate outputs Grz and some sort of "nice" or efficient representation of the squared-nore functions 22,2. The follow-up loop, also wi, computes some necessary intermediate gradients and combines them with the functions Q4., to obtain the gradient decomposition (and subsequent norm computation) given by Proposition 4.1.
the parameters
4.2 Efficient Implementation of Algorithm 2
We now describe how Algorithm 2 can be implemented efficiently when h(:,-) formed by neural network N. First, it is shown in Appendix B.1 that the intermediate quantities (Gi,z ) be computed in single forward and backward pass of A (as opposed to naively traversing the network @(k) times). Second, it is shown in Appendix B.2 that for any i, the batch gradients {Vc... (Eg o (z.i) hoe) can be obtained single (batched) backward pass of A if (i condition (5) holds for every x E B and (ii) the gradient 9r. is replaced by V 1 lx we (S))))) Consequently, if we ignore the costs of forming and evaluating (-) for each x E B
and (9r,z
5

---

and = 1..... k, then the above facts imply that we can obtain the norms Vl(,, w)ll using only one additional forward and (batched) backward pass of N..
Efficient Squared-Norm Functions
This section presents efficient representations of the functions (-) in Algorithm 2 for some basic layer functions da (w) = di (o, r). Examples involving more complicated layer functions (e.g., layer normalization and multi-head attention) can be found in the Appendix.
Each subsection begins with a precise description of oz(+). presents decomposition o(-) = Uh (-).), and gives analysis of the runtime and storage costs of an efficient representation of the function 2r (-) = =|| Dz oz (-)1?. For the sake conciseness, the proofs of these decompositions given in the Appendix.
In addition, we make comparisons of our approach with the naive approach (of computing gradients for each example) and other ghost clipping-like approaches. The results of these comparisons are summarized Tables 1-2 (see the first paragraphs in Subsections 5. 5.1-5.3 for descriptions of the variables/dimensionns
Naive
Ghost Clipping
Ours @((Brr))
Fully-Comnn "onnected
O B (pg m))
(r + B (rg))
Embedding'
e gd)
O(IBI4
@(
Rank-k Approx.
e mk)
O(1)
Table I: Asymptotic storage costs for computing Vll, W>DB... For ghost clipping and our approach, this is the storage cost of representing the squared-norm function (.)(.) the entire batch B.
Naive
Ghost Clipping
Ours O [B(g]) O log q qd}) ( + (B)
Tully-Connected Embedding"
O (pq 1 + m))
0(r [B4") + mfrg)²)
@ ([g)
O B
Rank-k Approx.
B(Bnn2
Table 2: Asymptotic runtime costs for computing {I) (l,,, b For ghost clipping and approach, this includes the time used to generate. represent, and evaluate the squared-norm function Pa (-) on the entire batch B.
5.1 Fully-Connected Layers
Given variables V IRxx and b E Th" layer input U, E RR'P, an activation function a : Rrxy + RRxx and linear broadcasting operator Q IRm +> RRxx satisfying m rgg the standard fully-connected layer function (-(-) is given by
(v = aUU Qb).
(6)
Typically, p. q. r, and called the imput dimension, output dimension, channel dimension, and bias dimension, respectively. Usually, it is the case that r < min(p, q} and a common case is r = 1.
We now consider the squared-norm function Ω2 IR IR generated by the choice of (v, := U + Q6. Denoting A as (4), for some ú = (V, b). we have that
2| Pr (g) = ||4"" g|| = || 2 + 1 g|| 2 = (U.U2. + 91"
for any 9 E RTX", Hence, (-) can be efficiently represented by U,U and an efficient representation of the function g || Q² -l For an example of the latter, suppose Q is the operator that repeats in an r-by-q matrix row-wise == rg/m times. Then, defining the row/column maps
(TE, k) = 1+ (E - 1) 1) + (k 1)
E(E,k) = 1 {[[E - 1)m + (k - 1)] mod r),
Based on the example in Section 5. Using Algorithm 3 for ours.

---

it follows from the definition of the adjoint that
g) = Σ IT(C))) AA E
k 1=,....,70 m.
For this example, incur compute (resp. storage) cost of (r²2p) (resp. ()r²)) for materializing UgU" and a compute and storage cost of ((1) for the function + 1 gll?, which does not depend on the data z. On the other hand, evaluation of (-2()) incurs: (i) a compute (resp. storage) cost of O( (resp. ( )) for materializing each gg" in the batch B and then computing the inner product term (UaUrz 99") and (ii) a compute
of (rql for evaluating || gll, which only requires a single pass through the entries of g for each example. Consequently. the total runtime (resp. storage) cost for batch of examples B is
O(r'p + rr B| ra] Bl) = ( + (B44))
(resp. O(1 0(1+ + + Bl) = ([
Let us now make comparison of this decomposition with the naive and ghost clipping approaches. For our discussion, suppose as in the previous example.
In the naive approach of computing V h(,, (V, b)) for each x E B, it straightforward" to show that the compute (resp. storage) costs are ( {pq + m)) (resp. ([ + r)
For the classic ghost clipping approach considered in [12, 13], our approach is identical in the case of Q = 0. When @ * O. this approach instead groups Q together with Ug and suggests the decomposition in (7) but with Un [U2; Q] and Q 0. Let now analyze the costs in the worst-case scenario when QQ' is dense, e.g., when m = 1. order to evaluate (QQ", .99") using consistent representation of QQ*, column vector) and compute QQ* E RT (resp. gg" E RR"x"))) using matrix multiplication. Clearly, the compute (resp. storage) costs for (QQ", .g"") are then (mffrg)² + |B] (rg})) (resp. O @(mrq + [r(rg]²) given Q which, together with the costs for |U*91 yield the complexity in Table 2 (resp. Table l).
must materialize Q (resp. g) rg-by-m matrix (rg-by-1
5.2 Embedding Layers
Given variables W E Rrxd, input indices Txx) = [m] ........... [x(x)] E r],, the standard embedding layer function (x). is given by
dh (W) (x))
where (x()) Rexr is the one-hot matrix whose f-th row is the Tz(x)-th basis vector in IR.. Typically, r, d, and 9 are called the vocabulary size, embedding dimension, and number of queries, respectively. Usually, it the case that max(d, (d..g /} < r, and common case == 1.
We now consider the squared-nore norm function Ω2 Roxd + R generated by the choice of Z. dx Yr(z) W for any gradient g = (f., 1/ Zz (W)). First, define the quantities
(x(x) (x) == Ki (x)x) = k, i 1, 1,.....911 g.6l
:= I(i: n (x) > 07}.
for k = =, ................... where (x) denotes the number times index & appears in (x). Next, notice that contains at most ñ unique rows, due to the definition of the gradient and the fact that (W) has most q unique rows. Denoting as (4), for some wi W, can be shown that
2x -11)) 922 || (9)
Σ nZ(x) 11.11
where ÿ denotes any row j of g where (x) i (note that all rows of y that satisfy this condition
are the same). Hence, Q2, can be efficiently represented by the nonzero values of {nu (x)) )= An
efficient algorithm using O(ğ log q) runtime and O(ğ) extra storage, for computing (x)) [=) for a fixed x E B, is given in Algorithm 3 of the Appendix. On the other hand, the evaluation of (2 only requires evaluating the q unique rows of an input g E Raxd (given by π (x)) and multiplying
'Hint: the cost of storing the gradients for single batch is equal the cost of storing the weights
7

---

them with the & nonzero cached values {m which can be done with a O gd) runtime cost for batch B. Consequently, the total runtime (resp. storage) cost for batch of examples B is (q log / (d}) (resp. ((() using Algorithm 3.
Let make comparison of this decomposition with the naive approach and the ghost clipping approach in [13].
In the naive approach of computing Vwh(x, W) for each E B, it straightforward" to show that the compute (resp. storage) costs are ((B)) (resp. ((BB)d)).
In the classic ghost clipping approach, we treat (=(-) a linear operator, compute Y=()) X 7(x)> and choose the representation (g)
(Y<(s) may) "9"). In the worst-case scenario, it is straightforward to see that Y= R(x)) can be fully dense, e.g., q 1. In this setting, even Ya(a) sparsely represented by a small set of ý unique indices, computing Yx(x) y m(a) still incurs compute and storage cost of (4²)) Now, since each example gradient g consists of embedding vectors in IR. for batch B, the compute (resp. storage) cost of materializing øg" is @(IBlq²d)
(resp. O Ol) Combining the above complexities with the O e(Bl)² runtime cost of computing
the desired inner products, i.e. (7) with U, Y x()) for x E B, we obtain the complexities in
Tables 1-2.
5.3 Low Rank Approximation Layer
Given input matrix U2 E " one way [19, 20] to encourage rank-k (or lower) approximation of U2 is to add the intermediate layer transform
(V) ||U - +
for some V E Raxk, where p(.) is a sparsity promoting regularizer (e.g.. l norm, SCAD, MCP) and (-) is the function that maps matrices to their singular values. Expanding the norm term, note that the above function can be equivalently (ignoring terms depending solely on U2) expressed as
Φr (V) = 2 (U2, VV*) + R(V,,
(8)
for some function R : Ra + R. Note that R(V) does not depend on a and, hence, its computation does not depend the batch B.
In view of (8), we now consider the squared-nore norm function Ω2 R + R generated by the choice of (V) = (Uz, VV /2, where, clearly, one has (z(V) -4 (V) R(V). Denoting A as in (4), for some w = V. it can be shown that
g² _ 4 (UU++U))1)
Pz(g) = 1AA'g1
for g E RR. Hence, (.)(.) can be efficiently represented by the scalar [|U VI It is straightforward to see that computing [U,, + VII requires only a O(n²k) runtime cost and ((1) storage cost. Moreover, evaluation of (z)()) given (U, V2) requires only a O(1) runtime cost.
In the naive approach of computing Vvh(æ, V) for each E B, it is straightforward to that the compute (resp. storage) costs is O[BB)22) (resp. O( due to the excessive computation (resp. storage) of g(U, + V for B. The authors not aware of any ghost clipping- liieeng-like techniques in the nonlinear setting.
6 Numerical Experiments
This section presents numerical experiments that compare our proposed adjoint-based framework (Adjoint) against the naive implementation of DP-SGD (Naive), which computes gradients for each example in a batch, and the classic ghost clipping frameworks (GhostClip) that are described in Subsections 5.1 and 5.2. Specifically, it presents runtimes and memory costs for the gradient norm computation of fully-connecte
and embedding layers.
Hint: need to store (and take the norm of) embedding vectors in d for each example in the batch B.
8

---

Each problem instances was run on a cloud computing platform consisting of (i) 112 Intel(R) Xeon(R) Platinum processors with 28 cores each, (ii) 64 GB of RAM, (iii) Python 3.10.11, and (iv) Tensorflow 2.14. For simplicity, memory usage was measured the peak amount of heap memory utilized the run of single gradient norm computation. We also simplify our computations by utilizing batches of size B 1 for the first two subsections. The loss function used in our experiment, (-), is the meea--squred-error To reduce the variance of the results in the first two subsections, we repeat each problem instance 20 times and report only the median runtime and memory cost over the repetitions.
6.1 Fully-Connected Layer
Figure presents numerical results for the setting considered in Subsection 5.1, where Q is the (linear) broadcasting operator that duplicates the bias rg/m times to match the dimension of the layer outputs. It specifically plots the effect of the bias dimension m for various values of the output dimension q. For simplicity, all problem instances fix input and channel dimension of and 4096, respectively. Additional experiments, involving the effect of batch size, are given in Appendix F.
Effect of Bias Dimension on Runlime
Effect of Blas Dimension on Memery
5000
Runtine (pccodd)
20
4000
15
3000
10
500
1000
1500
2000
500
1000
1500
2000
Bas Dimension
Dimersion
ChostClp, qm3
GrestClip, am5
Adjoint, Adjoint, Q-5
ChostClpp q-3 GhostClip, q-d
GhastCiip. q-5
Adjoitt, q-
GhestCiip, q-4
Adjoint, Q-3
Adjirt, q=3
Aijoitt q-5
Figure/ 1: Runtime and memory graphs for fully-connected layer computations with bias dimensions m = (2!,2? .?.....,?2ff 2"1) and output dimensions g = 3, 4, 5.
The results in Figure 1 demonstrate that the runtime and memory costs of Adjoint are marginal compared to those of GhostClip for fully-connected layers. These results also support the analysis of Subsection 5.1 in that: (i) GhostClip's runtime has a stronger positive dependence on the bias dimension m than Adjoint's runtime and (iii) GhostClip's runtime has a strong positive dependence on the output dimension
6.2 Embedding Layer
Figure 2 presents numerical results for the setting considered in Subsection 5.2. It specifically plots the effect of the number of queries q for various values of the vocabulary size r. For simplicity, all problem instances fix the embedding dimension to be 10 and the embedding indices {x)()) chosen uniformly at randomly from the set (1.....r).
Effect of Query Size on Runtime
Effect Query Size on Memory
6-
600
400
Pantina
200
8000
Query
GhostCip. r=5000
GrostClp, m=00000
Adjott,, r=7500
GhoeCCio, 5000
ChostCiip r=10000
Mjjint 7500
ChostCip. r=7500
odiit 5-5000
Adjoint, r=10000
GhostCip. 7-7500
Adjont, 5-0000
Adjaint, 100000
Figure 2: Runtime and memory cost graphs for embedding computations with query sizes (1000, 2000, 10000} and vocabulary sizes r = 5000, 7500, 10000.
The results in Figure 2 demonstrate that the runtime and memory costs of Adjoint are marginal compared to those of GhostClip for embedding layers. Moreover, the memory cost graph supports

---

the analysis in Subsection 5.2 in that ChostClip's memory cost has a significantly stronger positive dependence on the query size q compared Adjoint's memory cost.
6.3 Small BERT model
Figure 3 presents numerical results for an end-to-end training run of a small BERT model that consists of dense, embedding, normalization, and multi-head attention sublayers. specifically plots the effect of the batch size [ on the runtime and peak memory usage of training the model. To be more precise, the BERT model an instance of the TensorFlow BertEncoder model with a vocabulary size of 100, one intermediate transformer layer, and all other parameters set to their default values. Each experiment consists of single training loop of 50 iterations with uniformly sampled random input data of query size of 5. The efficient squared norm functions were taken from the descriptions in Section and Appendices E.1 and E.2.
Effect of Batch Size on Runtime and Peak Memory
125
Pask memory (MB)
Rundime (veconds)
6000
0000
0
1400
Batch size (B)
lpeak mamory!
(nuntima) Adjint (runtima)
Adjoint (peak mamory)
Figure 3: Runtime and memory cost graphs for training small BERT model with batch sizes
[B] = (100, 200, 400, 800, 1600).
The results in Figure demonstrate that the runtimes and peak memory usages of Adjoint scale better and are comparatively smaller than the corresponding ones for Naive.
Concluding Remarks
The analysis in Subsection 5.1 may also be applied transformations dx (-) primarily involve linear transforms. For example, is shown in [5, Subsection 2.3] that 2D-convolution layers equivalent to fully-connected layers when the example image is appropriately transformed to form the matrix Uz in (6) and, hence, our storage and runtime savings for fully-connected layers easily apply to 2D- (and generally nD-) convolution layers. Another example is the multihead attention layer, whose parameter transforms are simple matrix multiplications (see Appendix E.1 for derivation).
complex layers whose parameter
7.1 Limitations
The proposed framework only applies to layers with at least one differentiable intermediate transformation and models with differentiable losses. Moreover, the framework does not support shared trainable layers.
10

---

Acknowledgements
The authors acknowledge the generous support from Walid Krichene (Google) and Li Zhang (Microsoft), who have meticulously reviewed the derivation and implementation of the proposed framework.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differentially private bert. arXiv preprint 2XXv:2208..01224.. 2021.
[3] Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1138-1156. IEEE, 2022.
[4] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
[5] Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35:38305-38315 2022.
[6] Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization on large model at small cost. In International Conference on Machine Learning, pages 3192- 3218. PMLR, 2023.
[7] Aldo Gael Carranza, Rezsa Farahani, Natalia Ponomareva, Alex Kurakin, Matthew Jagielski, and Milad Nasr. using differentially private large language models. arXiv preprint arXiv:2305.05973, 2023.
recommender systems with synthetic query generation
[8] Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint wxXiv:2244.33650 2022.
[9] Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash Varadarajan, and Chiyuan Zhang. Private ad modeling with dp- sgd. arXiv preprint a.Xiv:2211.11886. 2022.
[10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[11] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends Theoretical Computer Science, 9(3 933-4):21-407, 2014.
[12] Ian Goodfellow. Efficient per-example gradient computations.
arXiv preprint
111.::1510.01799. 2015.
[13] Jaewoo Lee and Daniel Kifer. Scaling differentially private deep learning with fast per- example gradient clipping. Proceedings on Privacy Enhancing Technologies, 2021(1), 2021.
[14] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models be strong differentially private learners. arXiv preprint arXiv:21 2021.
[15] Gaspar Rochette, Andre Manoel, and Eric W Tramel. Efficient per-example gradient computations in convolutional neural networks. arXiv preprint arXiv:1912.00015, 2019.
11

---

[16] Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
[17] Tom Sander, Pierre Stock, and Alexandre Sablayrolles. Tan without burn: Scaling laws of dp-sgd. In International Conference on Machine Learning, pages 29937-29949, PMLR, 2023.
[18] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[19] Fei Wen, Lei Chu, Peilin Liu, and Robert C Qiu. A survey on nonconvex regularization-based sparse and low-rank recovery in signal processing, statistics, and machine learning. 1EEE Access, 6:69883-69906, 2018.
[20] Quanming Yao and James Kwok. Efficient learning with a family of nonconvex regularizers by redistributing nonconvexity. In International Conference on Machine Learning, pages 2645- 2654. PMLR, 2016.
[21] Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, and Chuan Guo. Vip: A differentially private foundation model for computer vision. arXiv preprint arXiv:2306.08888 2023.
12


Reviews:
[{"review_id": "jF3ycIzgXP", "reviewer": "Reviewer_zMyL", "summary": "This work unifies the analysis of the ghost clipping algorithm, which was previously analyzed for specific architectures only. The proposed framework extends previous results to a wide class of network architectures including new applications and provides asymptotically faster computation times than the previous case-by-case approaches. Some numerical simulations confirm the effectiveness of the proposed algorithm demonstrating faster computation time in practice. ", "questions": "- Why in Tables 1 and 2 some entries come with $\\Theta(\\cdot)$ and some $O(\\cdot)$? Are there lower bounds for storage and runtime costs for these settings? \n\n- Does equation (3) hold for the last layer only? \n\n- Typo in line 54. \n\n\n---\nUpdate: The authors addressed my concerns and I would like to increase my score from 5 to 6 to further support the acceptance. ", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is nicely structured and well motivated. The considered family of functions (NN architectures) is quite general and the proposed approach introduced by Proposition 4.1 seems to be very principled. Despite of the generality, the strategy proposed in Proposition 4.1 can be implemented for a number of important special classes of functions such as fully-connected networks, embedding layers and low rank approximation layers. The authors demonstrate improved runtime and storage costs for this algorithm in these three special cases. \n", "weaknesses": "-- The main motivation of the work is that when the batch sizes of DP-SGD is large, the runtime and storage can be large. Why this problem cannot be simply solved by using parallel computing (assigning different batches to different workers)? If this is one possible approach, I believe this should be mentioned and discussed in the related work. \n\n-- It seems that the assumptions on the loss function and the layers $\\phi_x$ are not explicitly stated. It is unclear to me if it is sufficient to have all $\\phi$ and the loss function to be Frechet differentiable or any additional technical assumptions are needed for Proposition 4.1. Why the sub gradient of $Z_x$ might not be unique while $\\nabla h$ and $g$ in this proposition are unique? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to thoroughly review our manuscript. We hope that our responses below will help improve your impression of our work.\n\n> The main motivation of the work is that when the batch sizes of DP-SGD is large, the runtime and storage can be large. Why this problem cannot be simply solved by using parallel computing (assigning different batches to different workers)? If this is one possible approach, I believe this should be mentioned and discussed in the related work.\n\nIn short, parallel computing does not solve the scalability issues of naive clipping compared to our approach, especially when certain dimensions of the problem (aside from batch size) are large (on the order of thousands or tens of thousands). This issue is explicitly made clear in Tables 1 and 2, where our proposed framework scales much better with other problem constants (e.g., $r$, $q$, $p$ and $d$) compared to the naive and ghost clipping approaches.\n\nAlso note that all three approaches considered in Tables 1 and 2 will (asymptotically) have the same benefits from switching to a parallel computing framework. Specifically, if batches were split among $s$ workers in parallel, the constant $|B|$ in Tables 1 and 2 would change to $|B|/s$ for all algorithms.\n\n> It seems that the assumptions on the loss function and the layers $\\phi_x$ are not explicitly stated. It is unclear to me if it is sufficient to have all $\\phi$ and the loss function to be Frechet differentiable or any additional technical assumptions are needed for Proposition 4.1. Why the sub gradient of $Z_x$ might not be unique while $\\nabla h$ and $g$ in this proposition are unique?\n\nTo be more precise, we will add some explicit assumptions just before Subsection 4.1 and make the differentiability of the key functions in Proposition 4.1 more clear. Specifically, we will make the explicit assumption that\n\n* $\\ell(x,\\cdot)$, $\\phi_1(\\cdot, x)$, \\ldots, $\\phi_k(\\cdot, x)$ are Fréchet differentiable;\n* each function $\\phi_i(\\cdot, x)$ can be decomposed into the composition of at least two Fréchet differentiable functions;\n* the functions $\\ell_x$, $\\phi_x$, $\\psi_x$, and $Z_x$ are Fréchet differentiable.\n\nIn the revision, we will assume $Z_x$ is differentiable so that its (sub)gradient is unique. \n\nAs an aside, note that the choice of $Z_x$ itself is not unique. Indeed, if $\\phi_x = \\psi_x \\circ Z_x$ then for any $\\alpha > 0$ the functions $Z_x’=\\alpha Z_x$ and $\\psi_x’ = \\psi_x / \\alpha$ also satisfy $\\phi_x = \\psi_x’ \\circ Z_x’$.\n\n> Why in Tables 1 and 2 some entries come with $\\Theta(\\cdot)$  and some $O(\\cdot)$? Are there lower bounds for storage and runtime costs for these settings?\n\n$\\Theta(\\cdot)$ is used for computations where we know the exact (up to universal constants) amount of storage/runtime needed to compute gradient norms with respect to certain dimensions. $O(\\cdot)$ is used when the storage/runtime may depend on other features of the problem that are not dimensions (e.g., sparsity of the queries for embeddings layers). For these cases, an upper bound is more appropriate.\n\nAs far as we know, there are no informative lower bounds for computing gradient norms. Naively, though, there is the $\\Omega(|B|)$ lower for storing/computing the scalars corresponding to each example’s gradient norm in a batch.\n\n> Does equation (3) hold for the last layer only?\n\nRelation (3) may hold for any layer in a neural network. However, the functions $\\phi_x$ between layers may differ. Note that this is why the corresponding $\\phi_x$ functions in Algorithm 2, specifically $\\{\\psi_{x,i} \\circ Z_{x,i}\\}$, are indexed by the layer index $i$.\n\n> Typo in line 54.\n\nThis will be fixed in the revision.\n"}, {"review_id": "dOcBnX21bw", "reviewer": "Reviewer_PneF", "summary": "The paper studies the memory/time complexity of the per-sample gradients norm computation step in the DP-SGD algorithm. The authors present a general theoretical framework that generalizes the idea of ghost norm computation (computing the norm of the persample gradients without having to store the gradients), and can be applied to arbitrary layers of a DNN (if an ad hoc decomposition can be found). The authors show early experiments on the benefits of their methods compared to previous ghost clipping techniques.", "questions": "- Typically Opacus (storing per sample gradients) or ghost norm will be 2x slower than non DP training. How can the proposed method be 150x faster? That would mean that the proposed method is faster than non DP training?\n- Why does the green curve start decreasing at some point in the memory figure for the embedding layer?\n- For the embedding layer, the authors state that q=1 in practice but show memory/runtime for q = {1000, 2000, …, 10000}. Can you please clarify on these choices for comparison?\n- The paper states that it can be applied to arbitrary layers, but the examples are linear layers (which were already tackled in ghost norm previous work). What are the conditions for the existence of the decomposition in proposition 4.1? What do the authors have in mind by “efficient manner” (line 156)? When is that possible? \n", "limitations": "The paper does not include a limitation section. \nSuggestions for improvement would be to perform a rigorous empirical study of the proposed method, with entire architectures and using micro batches, and see if can easily used with an existing DL library (pytorch, JAX...). ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "originality: - Computing persamble gradient norms is a real bottleneck when training DNNs with DP-SGD. Typically, the Opacus library (Pytorch for privacy) stores the gradients per sample before computing the norms, which can be memory intensive, especially for large architectures. Other methods have been proposed to compute the norm without storing the gradients (ghost norm), but no general framework has been proposed yet. This paper gives a clear problem formulation and a general theoretical framework to approach this problem. I was very happy to see a theoretical work that tries to tackles this issue.\nquality: The math are correct\nclarity:  ok\nsignificance: using the theory of linear operator to improve time and space complexity of DP-SGD is good novelty that could benefit the community", "weaknesses": "- Typos: l108 “authors”\n- Overall, the experiments are very insufficient. They are performed with batches of size 1, for which the vanilla per-sample gradient storage method has a better running time, but with which it is never compared. The authors should investigate in detail how their method would work with GPUs to see how it would be beneficial in practice: the complexity bounds given are linear in the batch size, but in practice we benefit greatly from parallel computation/optimized matrix multiplication. \n- Experiments should be performed on whole (even small) networks used in practice, with batches of size greater than one. In Li et al (2022), they compare ghost norm to opacus when training a GPT2-like architecture and find similar runtimes; a similar comparison could be done here (even with much smaller versions of GPT2 when computational power is limited). \n- It is not the same abstract in OpenReview and in the article. The first states that savings can be as high as 150x: this could be the case in very specific situations chosen for the experiments, but the authors do not elaborate on why these choices are realistic in practice. \n- The section on related work is sparse, with very few papers cited (no mention of why gradients need to be clipped, no mention of the whole deep learning literature where this is a real bottleneck (Opacus))\n- No code for reproduction\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments towards improving the quality of our manuscript. We hope that the comments and considerations below will help improve your overall opinion of our work.\n\n> Typos: l108 “authors”\n\nThis will be fixed in the revision.\n\n> Overall, the experiments are very insufficient...\n\nWe will add additional experiments that vary the batch size as well as compare GPU costs against CPU costs. As a preview of the results, here are the fully-connected memory and runtime profiles of ghost clipping (GC) vs. our method (A) for varying bias dimensions $m$ and batch sizes $|B|$.\n\n**Runtimes (in seconds)**\n\n| m | GC (\\|B\\|=250) | A (\\|B\\|=250) | GC (\\|B\\|=500) | A (\\|B\\|=500) | GC (\\|B\\|=1000) | A (\\|B\\|=1000) |\n|-|-|-|-|-|-|-|\n| 16 | 0.224 | 0.061 | 0.369 | 0.094 | 0.865 | 0.154 |\n| 32 | 0.230 | 0.064 | 0.370 | 0.089 | 0.907 | 0.156 |\n| 64 | 0.239 | 0.063 | 0.430 | 0.092 | 0.850 | 0.154 |\n| 128 | 0.285 | 0.061 | 0.562 | 0.090 | 1.354 | 0.156 |\n\n**Peak Memory (in MB)**\n\n| m | GC (\\|B\\|=250) | A (\\|B\\|=250) | GC (\\|B\\|=500) | A (\\|B\\|=500) | GC (\\|B\\|=1000) | A (\\|B\\|=1000) |\n|-|-|-|-|-|-|-|\n| 16 | 1705 | 190 | 3410 | 380 |7569 | 761 |\n| 32 | 1717 | 190 | 3433 | 380 | 7616 | 761 |\n| 64 | 1740 | 190 | 3480 | 380 | 7710 | 761 |\n| 128 | 1787 | 190 | 3574 | 380 | 7898 | 761 |\n\n> Experiments should be performed on whole (even small) networks ...\n\nWe will add additional experiments on a small BERT model to see how our framework performs in practice. We do want to point out that Li et al (2022) show that some models couldn’t be trained with Opacus simply because the per example clipping made GPUs run out of memory. We expect our results to be very similar in nature.  \n\n> ...the authors do not elaborate on why these choices are realistic in practice...\n\nThe numerical experiments in Section 6 were specifically chosen to demonstrate the better scalability of our implementation compared to ghost clipping and, hence, the parameter choices may not be typically observed in other literature.\n\nWe will add additional end-to-end experiments that utilize more practical parameter choices.\n\n> The section on related work is sparse...\n\nThe importance of clipping gradients is discussed in the second paragraph of the “Introduction” section (Section 1). Moreover, the steps in Algorithm 1 clearly show that DP-SGD cannot be implemented without gradient clipping (hence, its importance).\n\nWe will add additional references to works where the clipping step is a serious bottleneck to training DP models. Also, we would be happy to consider specific works the referee has in mind. \n\n> No code for reproduction\n\nCode will be made publicly available if the paper is accepted.\n\n> Typically Opacus (storing per sample gradients) ... will be 2x slower than non DP training...\n\nAs far as we are aware, there do not appear to be any studies that compare Opacus / ghost norm / non-DP gradient norm computations on individual layers. Hence, the “2x” slower performance is not informative of the layer-specific efficiency of ghost norm / Opacus vs non-DP for different choices of layer parameters.\n\nConsequently, the 150x improvement of our framework is due to the large layer (or query) dimension sizes that are tested in our experiments. A simple analogy (with rough guesses) is that BubbleSort is only 2x slower than QuickSort when the number of elements $n$ is less than 20, but can be more than 1000x slower when $n$ is greater than 5000.\n\nIn view of the above arguments, we do not agree that our experiments imply our proposed framework is faster than non-DP training. In fact, our framework is strictly slower because it performs one more backward and forward pass of the model compared to non-DP training (see lines 117, 137, 140, 169, and 175 in the original submission for references of this).\n\n> Why does the green curve start decreasing at some point in the memory figure for the embedding layer?\n\nWe believe it is due to the randomness of the generated embedding indices.\n\n> For the embedding layer, the authors state that q=1 in practice...\n\nFor added clarification, it is stated (in Subsection 5.2) that a commonly used case is q=1. In practice, models may also use embedding layers with q >> 1. For instance, transformer models require q to be the size of the sentence and personalization  models, such as those used in online advertising, may encode arbitrary information about a webpage’s context which can result in multiple queries to a model. \n\n> The paper states that it can be applied to arbitrary layers, but the examples are linear layers...\n\nWe respectfully disagree about the first statement. Subsection 5.3 gives the analysis of a nonlinear layer, and the analyses on ghost clipping from prior works did not consider the sparsity of the related linear operators (this is why we are able to make a drastic improvement for embedding layers in particular).\n\nIn general, the decomposition in Proposition 4.1 is feasible when $\\phi_x$ can be decomposed into the composition of at least two Fréchet differentiable functions.\n\nExamples are given in Section 5 about what “efficient manner” means (on line 156). In short, this is the case when the operator $A^*$ in Proposition 4.1 admits a low-rank decomposition or is sparse. When exactly this is the case will depend on the characteristics of the layer function $\\phi_x$ (in Proposition 4.1) and the chosen decomposition $\\phi_x = \\psi_x \\circ Z_x$ (see the examples in Section 5 and Appendix E for some details).\n\n> The paper does not include a limitation section...\n\nWe will add a section discussing the limitations of our framework. Moreover, we will add experiments that compare our method on more complex model architectures. "}, {"review_id": "oUAbDsqzXZ", "reviewer": "Reviewer_mrhy", "summary": "This paper unifies a framework that enables us to apply ghost clipping algorithms to new layers of neural networks, apart from fully connected, feed-forward layers. In particular, the paper discusses efficient implementations of computing norms for running DP-SGD to train neural networks. ", "questions": "N/A ", "limitations": "N/A ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The contributions of this paper are as follows: \n\n1. It shows how to utilize the proposed framework to apply ghost clipping techniques to new layers for DP-SGD on training neural networks. Three main examples are included to discuss how to implement efficient algorithms to compute the gradient norm and to run DP-SGD. \n\n2. Experimental results evaluate the effectiveness of their proposed framework over the classical ghost clipping framework in run time and memory requirements. ", "weaknesses": "Literature on the importance of DP-SGD and clipping operators is lacking in this paper. It is better to include them in Section 3 (Previous work) or in the introduction section to motivate the study of this paper in a broader impact.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive impression of our work! Below you will find our comments addressing your main concern.\n\n> Literature on the importance of DP-SGD and clipping operators is lacking in this paper. It is better to include them in Section 3 (Previous work) or in the introduction section to motivate the study of this paper in a broader impact.\n\nIn the second paragraph of the “Introduction” section (Section 1), we discussed the importance of DP-SGD, motivated the use of gradient clipping, and remarked on the importance of private training. Moreover, in the third paragraph of the “Introduction” section and the “Previous work” section (Section 3), we discussed why the process of clipping is hard to scale to large models. If you have any specific pointers related to the importance of DP-SGD we would be happy to add them as additional references.\n\n"}, {"review_id": "PjQkYbWWJn", "reviewer": "Reviewer_zBGn", "summary": "This paper provides a unified framework for efficiently computing the gradient norms of individual examples for a wide range of neural network architectures, which significantly decreases runtime and storage costs for implementing DP-SGD.", "questions": "1. What is the overall reduction in runtime/storage cost provided by the proposed framework?\n2. How does the empirical performance of the proposed framework compare to that of ghost clipping for convolution layers and attention layers?", "limitations": "There is no discussion of societal impact beyond the underlying (implied) importance of user privacy. However, I don't think any further discussion of societal impact is necessary for this work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The considered problem is important: Computing per-example gradients is a computation bottleneck for previous implementations of DP-SGD.\n2. Theoretical and empirical improvements over baselines are clearly presented and significant. Tables 1 and 2 summarize the time and storage complexity for previous work and the proposed algorithm, and Figures 1 and 2 summarize the observed improvements in experiments. The theoretical and the empirical improvements are both convincing.\n3. The presentation is rigorous and clear.", "weaknesses": "1. The experimental evaluation does not provide a big-picture idea of the end-to-end savings provided by the proposed framework. Figures 1 and 2 exhibit the runtime/storage costs only for the gradient computation operation, and it does not show how the overall costs are affected. If gradient computation accounts for a small portion of the overall runtime, then the overall time savings will not be significant. As it stands, the experimental results do not give a concrete idea for the overall savings in runtime, which is the metric of interest for practitioners.\n2. It would be nice to see an empirical evaluation for the more popular layer types mentioned in the text, e.g. convolution and attention.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive evaluation of our work. We hope the below comments will address the issues you brought forth.\n\n> The experimental evaluation does not provide a big-picture idea of the end-to-end savings provided by the proposed framework. Figures 1 and 2 exhibit the runtime/storage costs only for the gradient computation operation, and it does not show how the overall costs are affected. If gradient computation accounts for a small portion of the overall runtime, then the overall time savings will not be significant. As it stands, the experimental results do not give a concrete idea for the overall savings in runtime, which is the metric of interest for practitioners.\n\nFor feed forward neural networks the forward and backward steps use a similar amount of compute and memory, thus highlighting the results of decreased gradient computation time seemed reasonable to us. However, in order to provide a more complete picture we can add end-to-end runtime analysis of our technique compared to the naive clipping technique.\n\n> It would be nice to see an empirical evaluation for the more popular layer types mentioned in the text, e.g. convolution and attention.\n\nAs the convolution operator is equivalent to a fully-connected layer (see [1] below) and the parameter transforms of multihead attention layers are merely matrix multiplications (see our Appendix E.1), we expect their empirical performance to be similar to what is shown for fully connected layers (see Figures 1 and 2).\n\n[1] Bu, Z., Mao, J., & Xu, S. (2022). Scalable and efficient training of large convolutional neural networks with differential privacy. Advances in Neural Information Processing Systems, 35, 38305-38318.\n\n> What is the overall reduction in runtime/storage cost provided by the proposed framework?\n\nIn our experiments, the large majority of the work performed in the algorithm was in the computation of the gradient norms. Hence, the graphs in Figures 1 and 2 are also indicative of the overall cost reduction provided by our framework. \n\n> How does the empirical performance of the proposed framework compare to that of ghost clipping for convolution layers and attention layers?\n\nSee our response above about convolution and attention layers.\n"}, {"review_id": "6WLkVO9EY6", "reviewer": "Reviewer_6FUB", "summary": "The paper provides a unification of ad-hoc analysis and interpretations of the ghost clipping algorithm under a single framework. It also shows that for certain operations, such as fully-connected and embedding layer computations, further improvements to the runtime and storage costs of existing decompositions can be deduced using certain components of the proposed framework.", "questions": "How can the proposed framework be generalized beyond the ghost-clipping algorithm?", "limitations": "Limitations are not discussed by the authors. Perhaps the possible relation or extension to other clipping algorithms can be mentioned in the final as a separate concluding section which is now missing.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Originality**: The paper proposes a novel framework for fast gradient clipping used in DP-SGD. This is a significant theoretical contribution to the field of privacy of machine learning.\n- **Quality**: The paper is well-organized. A thorough explanation of the proposed framework, including mathematical derivations and experimental results is provided.\n- **Clarity**: The paper is easy to follow and understand, even for readers who are not experts in the field. The authors provide clear explanations of the background, motivations, concepts, and techniques used, and the experimental results are presented in a concise and understandable manner.\n- **Significance**: The paper has significant implications for the specific field of privacy of machine learning. It provides a unified perspective on the ghost clipping algorithm in DP-SGD.", "weaknesses": "The paper focuses only on a specific technique of gradient clipping, i.e., ghost clipping. Whether this ghost clipping lies at the heart of the big field of privacy of deep learning or not is unclear to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our manuscript. Below, you find some responses to some of your questions and concerns.\n\n> The paper focuses only on a specific technique of gradient clipping, i.e., ghost clipping. Whether this ghost clipping lies at the heart of the big field of privacy of deep learning or not is unclear to me.\n\nAs far as we are aware, there are no other techniques in the literature for quickly clipping gradients in neural networks aside from ghost clipping.\n\n> How can the proposed framework be generalized beyond the ghost-clipping algorithm?\n\nI am unsure what the reviewer is asking here. The ghost-clipping technique is a special instance of our proposed framework, and not the other way around.\n"}]

Author rebuttal:

Meta-review: The paper performs a synthesis of ad hoc analyses and interpretations of ghost clipping algorithms, bringing them together in a single, comprehensive framework.
This family of methods aim at solving the computational bottleneck in DP stemming from the computation of per-sample gradient norms. Furthermore, the authors establish that, for particular architectures, the proposed framework enhances the efficiency of existing decompositions, yielding improvements in terms of execution time and storage.

The reviewers and I concur that the paper is an interesting contribution and should be accepted. 

Please take into consideration reviewers' comments before submitting the final version of your manuscript.
Decision: Accept (poster)