Efficient Gradient Clipping Methods in DP-SGD for Convolution Models

We would like to thank the reviewer for their review. Please find our answers to your questions below.

Weakness 1: Thank you for raising this point. Improving the runtime and memory complexity of the clipping step of DP-SGD merits attention and is not merely a matter of the underlying implementation. Typically, after the back-propagation step, the learner has access to the partial derivative of the output, denoted as $g$ in our algorithms. The “direct” approach you allude to, whose in-place implementation we provide in Algorithm 3.1, can in some cases be significantly slower than the other two methods we propose in this paper. This happens even if the batch size is 1, so the size of the batches is not the only bottleneck for the performance overhead., Several works discuss the difficulties of using DP algorithms in practical applications mention that the running time of clipping is one of the major issues and blockers to deploying machine learning models trained on sensitive data, e.g., in medical fields (see, for example https://arxiv.org/pdf/2303.00654, Section 4.5, in particular the discussion about slower training).

Weakness 2: We were measuring the peak memory of the operations. Moreover, our theoretical analysis of the algorithms proves that the in-place algorithms have less memory overhead than prior work. We will release the code in the next version of our work.

Weakness 3: Even though the first two methods appear to be similar to prior work, we followed a different conceptual path to obtain them. Prior work considered “unrolling” the gradients to large matrices, and performing matrix multiplication, which required a large amount of additional memory and computation. On the other hand, our approach is to analyze the updates as abstract linear operators and, consequently, to develop a more efficient scheme for evaluating them. We acknowledge the limitations of the FFT method with small kernels, but disagree that this makes it impractical. Large kernels have recently gained attention, particularly in applications involving long-context inputs [https://arxiv.org/pdf/2203.06717] and could further have an impact with language modeling for capturing complex long-range dependencies. Our bounds and experiments demonstrate that in these specific scenarios our FFT approach exhibits superior performance compared to baselines. This highlights the practicality and relevance of this approach, in addition to its novelty.

$\ell_x$ in 4 denotes the loss function for a fixed $x$.

A similar interface is used for TensorFlow privacy (https://github.com/tensorflow/privacy/blob/master/tensorflow_privacy/privacy/fast_gradient_clipping/registry_functions/dense.py), so we do not expect any issues.

As far as we know, JAX Privacy does not have a framework for fast clipping. However, it does support the (naive) per-example clipping algorithm and, hence, we can integrate our Algorithm 3.1.

The term of additional storage refers to the extra storage space needed to compute the norm of the gradients on top of the storage used by non-private SGD. More precisely, after the back-propagation step, non-private SGD has access to $x$ and $g$ in Algorithm 3.1 in our manuscript. We will elaborate on this in the next version of our manuscript.

“Ghost clipping” refers to a gradient norm computation trick introduced by Goodfellow in 2015 for efficiently computing the gradient norms of fully connected layer weights. Our work uses a similar trick in Algorithm 3.1 that avoids directly computing the norm. In the current version of our work we give a reference to Goodfellow’s paper, but we will elaborate more in the next version of our draft.

We would like to thank the reviewer for their comments. Below we address the points they raised.

In the next version of our manuscript, we will give a description of DP-SGD and describe where our improvements fit inside the DP-SGD. For a preview, we give an outline of this description below. "DP-SGD is a variant of SGD in which the per-example gradients in the SGD update are replaced by a set of privatized per-example gradients. These privatized gradients are obtained by (i) projecting each of the original per-example gradients onto a Euclidean ball of some radius C (commonly known as the L2 clip norm) and (ii) adding Gaussian noise Z to the sum of the projected gradients with variance depending on C and the size of the input batch used to compute the original gradients. One efficient method of projecting the per-example gradients is to compute the per-example gradient norms and compute the gradient of a weighted loss function whose weights depend on the norms and radius C. For training machine learning models specifically, the computation of the squared gradient norms can be decomposed by the different layers in the model. Because of this decomposition, there have been several works that proposed efficient methods for computing gradient norms of specific model layers. This work develops several methods for efficiently computing the gradient norms of the convolutional layer under different parameter regimes. These methods can be directly incorporated in optimization libraries that implement per-layer gradient and gradient norms operations, such as Opacus, tensorflow-privacy, and jax-privacy, and benefit from these libraries resources, such as parallelization."

Regarding the nuances between “actual runtime” and “time complexity”, we disagree about the (constant-factor) equivalence between standard training and per-example clipping. For this discussion, let us consider the non-private/private gradient computation step, and suppose the model under consideration has N model weights and that input batches are of size B.

In standard (non-private) training, one typically computes the gradient of a scalar loss function with respect to model weights, incurring roughly N storage/runtime cost (auxiliary quantities during this computation are typically on the same order of magnitude).

On the other hand, in the (naive) implementation of DP-SGD, the training step consists of a for-loop over the B per-example (or per-sample) losses where the gradients of each per-example losses are materialized, clipped (by projection), and then aggregated. Since materialization of the gradients and computing the subsequent norms is an Ω(N) operation, the storage/runtime complexity is Ω(N*B) operation, which scales linearly with the batch size.

The algorithm in Bu et al. (2023b) is a hybrid of the naive per-example gradient clipping algorithm and the ghost norm clipping algorithm for convolution layers. Specifically, the Bu et al. algorithm conditionally invokes either the naive or ghost norm algorithm for each convolution layer depending on the number of channels, input dimension, output dimension, and kernel dimension of that layer (see Section 3 of Bu et al. (2023b)). Consequently, we believe a fair comparison would be to compare each of the clipping algorithms in Bu et al. (2023b) against our algorithms in the regimes that they perform the best in (see the three settings in our Section 4). This is equivalent to making the comparison to the clipping algorithms in Bu et al. (2022) over the best performing regimes.

Opacus code for convolution layers (see https://github.com/pytorch/opacus/blob/main/opacus/grad_sample/conv.py) applies the ghost norm clipping algorithm for linear/dense layers under the framework that the convolution layer is a linear layer whose inputs are the “unfolded” versions of the input images. Thus, the performance of the Opacus implementation would be similar to that of what we label “Bu et al. (2022) ghost norm” in Figures 4.1-4.3 of the current version of our paper. In the next version, we will add a detailed comparison of our approach to existing implementations in Opacus and JAX privacy.

In terms of integration efforts, we do not see any issues that prevent us from integrating with existing fast clipping software packages such as Opacus and TensorFlow privacy. For convenience, we give some details of what the integration would look like with respect to the interfaces of the aforementioned packages.

In Opacus (https://github.com/pytorch/opacus/blob/main/opacus/grad_sample/conv.py), the interface of the per-example (convolution) gradient norm computer consumes (i) metadata about the layer, (ii) layer inputs (activations), and (iii) backpropagation gradients. Items (i)–(iii) are clearly sufficient for implementing our Algorithms 3.1–3.2 whereas the implementation of Algorithm 3.3 only requires an additional Fast Fourier Transform oracle, for which we can use NumPy’s implementation (numpy.fft).

Thanks for the response.

• I generally like the proposed outline; it will help clarify how your work fits within the broad DP-SGD framework. A few additional comments: 1) I didn’t quite follow the part about "computing the gradient of a weighted loss function whose weights depend on the norms and radius C" — I thought computing the per-sample gradient norm would suffice. 2) Including a flow chart alongside the outline would be great. 3) It would be even better to highlight the challenges not addressed by your work (e.g., parallelization of samples, as this is mentioned in the introduction).

• I think you’re still referring to "time complexity", as the discussion pertains to a naive, sequential implementation of per-sample gradient clipping. In practice, however, parallelization is applied at this step. This is precisely why I think it’s important to distinguish between "worst-case time complexity" and "actual runtime".

• It would be helpful to discuss the choices of baseline selection and include comparisons with Opacus in the revised version. I believe this will further strengthen the paper.

• Thanks for answering my remaining questions.

We would like to thank the reviewer for their review. Please find our response to the weaknesses and the questions you have mentioned below.

Weakness 1: While the first two methods use existing formulas in the literature to derive gradient norm estimates, our focus for these methods was on more efficient implementations in practice. More specifically, prior work involved “unrolling” the gradients to large matrices and performing matrix multiplication, which required storing large auxiliary matrices in order to perform the computations in these operations. On the other hand, our approach is to analyze the updates as abstract linear operators and, consequently, develop a more efficient scheme for evaluating them. Note that one of the relevant topics listed on the ICLR website is “implementation issues” for which this paper is relevant (see the third last bullet point on https://iclr.cc/Conferences/2025).

Weakness 2: Since we ran relatively small-scale experiments, we believed that it was not informative to include the performance of the in-place ghost norm algorithm, at the cost of extra consumption of resources. The main advantage of these two methods is the storage efficiency compared to prior work. We will include this runtime in the next version of our work.

Weakness 3: The y-axes of our plots have negative values since we are plotting the log of the runtime and the memory consumption. This allows us to view improvements on a multiplicative scale rather than an additive one.

Weakness 4: In the experimental setting, we only test a single layer of the CNN since the complexity of our approach (and of prior work) scales linearly with the number of layers. Moreover, there are no computations involving more than one layer at a time. We believe that this comparison gives a more accurate understanding of the running time and memory storage improvements of our methods. The parameters of the particular layer we use for the experiment are provided in Section 4 (please refer to $d_{in}, d_{out}, n_{in}, n_{out}, d_k$.)

Weakness 5: We apologize for using the wrong template. We have now uploaded a new version of our manuscript using the correct template.

Question 1: Please see our answer to weakness 1.

Question 2: Please see our answer to weakness 2.

Question 3: Please see our answer to weakness 3.

Question 4: Please see our answer to weakness 4.

Question 5: We are unsure about what you mean by scalability in this context. In terms of memory and runtime scaling, we have asymptotic bounds in Table 1.1 (page 2) and further analysis in section 3.3.

Thank you for providing the author response. I would keep my scores.

We would like to thank the reviewer for their review. Please find our response to the weaknesses and the questions you have mentioned below.

Indeed, since the only step we modify is the gradient clipping step, comparing layer-level performance is more direct than end-to-end performance. Moreover, if we run DP-SGD for the same number of steps and under different clipping subroutines, then the utility of the algorithm will be unaffected by the change since the clipped gradients will be identical. Nevertheless, we will include experiments with end-to-end training in the next version of our work.

We respectfully disagree with the reviewer’s comment. In Section 3.3 we provide a comparison of the runtime of the different algorithms in terms of the architecture of the underlying layer of the CNN. Moreover, in Section 4 we illustrate different regimes in which different algorithms perform better. If there are any further comparisons the reviewer would like to see, we would be happy to provide them.

Thank you for your rebuttal. It solves my second concern, but for first concern, I think more comprehensive experiments, e.g., generalization performance are needed.