Thank you for reviewing our paper and providing constructive feedback to us. Below, we answered your questions. Please take a look at them and let us know if there are any remaining questions, and we would be more than happy to continue the discussion.

$\quad$

Many of the signal processing concepts are introduced too briefly, considering the audience, which makes fully understanding the theory difficult. Adding a section to the appendix explaining them clearly would make the theory much easier to understand for people not familiar with signal processing.

We agree with the reviewer that the discussion on the signal processing would be very helpful to readers with no background in the signal processing domain. We provided a more detailed discussion on the background in our general response to the reviewers. We will expand and add this discussion to the revised manuscript of our paper.

$\quad$

The method used to compute the privacy bounds and the subsampling method in the experiments are not mentioned clearly in the paper. "Uniformly draw minibatch" or "randomly draw minibatch" from the algorithm listings is ambiguous, and could mean any of Poisson, with replacement or without replacement subsampling.

Great point! To clarify, we are using the subsampling without replacement strategy. The privacy guarantee is discussed in Balle, et al. 2018. We will clarify this in our revision.

$\quad$

Minor points Line 43: 250K steps for LLAMA training sounds like a typo.

According to Touvron et al., 2023, LLAMA-7B/13B are pre-trained with 1T tokens, with a batch size of 4M tokens. Therefore, the total pre-training steps is 1T/4M=250K.

$\quad$

It would be good to mention that there are multiple ways to interpret "neighborhood" (substitute or add/remove), and that the paper's results do not depend on the precise definition.

Agreed! We will discuss this point in our revised paper.

$\quad$

As far as I know, the Gaussian mechanism bound in Definition 2 has only been proven for $\epsilon\leq 1$.

You are correct that in the original proof in Dwork and Roth, 2014, the guarantee for the Gaussian mechanism is provided only for case $\epsilon \in (0,1)$. While the refined proof for general $\epsilon >0,$ and improved bounds are given by Abadi et al., 2016, and Mironov et al., 2019. We will update the citations in the revised version.

$\quad$

It is not clear how Algorithm 3 should be read for DPAdam or LP-DPAdam. The update on line 17 uses $d_t$, but the Adam lines only compute $\tilde{d}_t$.

We apologize for the confusion. If only LP-DPAdam or DPAdam is used, then $\tilde{g}_t = g_t$ in line 9, and $d_t =\tilde{d}_t$ in line 16 in Algorithm 3. We will revise the description of the algorithm.

$\quad$

Do the adaptively selected filter coefficients from Section 5.3 have the same convergence guarantee? Did you experiment with adaptively selected filter coefficients from Section 5.3?

This is a great question. Currently, we have neither theoretical results nor numerical experiments for the optimal FIR filter approach proposed in Sec. 5.3. The major focus of this paper is to propose the frequency domain perspective and analysis for DP noise reduction. The filters investigated and analyzed in the paper are time-invariant, while the adaptive filter is time-varying. We will discuss this briefly in the paper and will leave it as a potential and promising future direction of the paper.

$\quad$

Why does the performance of LP-DPSGD drop with larger epsilons when fine-tuning on CIFAR-10 in Figure 10?

Good observation! Notice that the test accuracy drop in such a high accuracy for fine-tuning is quite small (only 0.1%). And the training accuracy in such cases did not drop. Therefore, the performance drop should be attributed to overfitting.

$\quad$

Thank you for reading our rebuttal. We hope the above responses have addressed your concerns. If you have any questions, we would be more than happy to continue discussing them with you.

Thank you for your kind response and for providing additional feedback.

We apologize that we misunderstood your question on $\epsilon <1$ for DP guarantee. Our original response was on Thm.1, which is correct and used in the later proof of our paper.

You are correct on Def. 2 of the Gaussian mechanism that requires $\epsilon <1$. A refined analysis of the Gaussian mechanism is given in Thm. 2, [R1], which states that $\sigma = \frac{\Delta}{\epsilon}\cdot \frac{\sqrt{2}(a+\sqrt{a^2+\epsilon})}{2},$ with $\mathrm{erfc}(a) - e^\epsilon \mathrm{erfc}(a^2+\epsilon) = 2 \delta.$ This bound works for all $\epsilon>0 , \delta <1.$ We will follow your comment and fix the error in our Def. 2. We would like to point out that we did not use this result in our experiments or proofs in the paper. We just used this definition to introduce the Gaussian mechanism. So we can easily fix this issue and cite proper references. Please also let us know if other references should be included for such a revision.

[R1] Zhao, J., Wang, T., Bai, T., Lam, K. Y., Xu, Z., Shi, S., ... & Yu, H. (2019). Reviewing and improving the Gaussian mechanism for differential privacy. arXiv preprint arXiv:1911.12060. Again, thank you for pointing out this issue.

Thank you for providing feedback to us. We are glad that you found our paper well-written, the results significant, and the theory meaningful. We are also very excited to hear that you really liked the paper. Below, we respond to your main comments:

Error bars

The attached PDF provides the error bar for the experiments in Fig.3 (a). We will repeat the other single-run experiments and report all error bars in our revised manuscript.

Autocorrelation assumption

Great question! The way to look at this assumption is as follows: since there is flexibility in choosing $c_\tau, c_{-\tau}$, we can always choose a small $c_\tau$ so that $c_{-\tau}$ is non-negative, and our theory applies. As you correctly pointed out, the constraint on $c_{-\tau}$ is not restrictive, and is only necessary for simplifying the proof.

Clarity

Thank you for providing such detailed constructive feedback. We will address these points as discussed next:

• A review section in the appendix

We will do it as described in our general response to the reviewers.

• Example coefficients for low-pass filters

We provided the filter coefficients in Table 2 of the paper. A more detailed discussion on filter design is given in our general response to the reviewers and will be included in the revised manuscript.

• Restructuring Thm. 2

Agreed. We will put the definition of quantities ($\underline{SNR}$ and $\kappa$) before the theorem.

• Construction of $\kappa, p_{a,\tau}$

Indeed, $p_{a,\tau}$, as the solutions to $1 + \sum a_\tau x^\tau = 0$, might not be real. But the resulting weights $\kappa_\tau$ are guaranteed to be real. This is because $\kappa_\tau$ are the weights of the past gradients by recursively expanding $m_t = -\sum_{\tau=1}^{n_a}a_\tau m_{t-\tau} + \sum_{\tau=0}^{n_b}b_\tau g_{t-\tau} = \sum_{\tau=0}^{t}\kappa_\tau g_{t-\tau}.$ Since $a_\tau, b_\tau$ are real, $\kappa_\tau$'s are also real. We will add this discussion in our revised definition of $\kappa$ before Thm. 2.

• Constraints on the filter coefficients

Great question! The design of the filter coefficients and the constraints are provided in our general response to the reviewer. In short, our constraints imply that the filter is stable and has a unit gain.

Parameter tuning...

The design of the filter coefficients and the constraints are provided in the general response. The other hyper-parameters are tuned using grid search (See App. B.1 Tab. 1 in the original paper) jointly to achieve the optimal performance.

Originality: the proposed ... For example:

• Empirical investigation of the adaptive filter

We agree that adaptive filters are worth further investigation. However, we leave this investigation to future work. This is because this paper focuses on frequency domain analysis, and the investigated filters are time-invariant. However, the adaptive time-varying filters require a different set of analysis tools.

• On the choice of the filter coefficients

In our PDF response, we further investigated different choices of first-order filter coefficients, in Fig 2. We would expand this and include it in the paper.

• A plot of the performance vs. the order of the filter

Fig. 6 in the paper investigates the performance of filters of different orders. We observe that a first-order filter performs better than no or second-order filter. A refined version is included in the PDF response, where we compare filters with different combinations of $n_a$ and $n_b$.

Minor points

• $t$ in lines 263 and 265

From the definition of $\kappa_\tau: m_t = \sum_{\tau=0}^{t}\kappa_\tau g_{t-\tau},$ we see that $\kappa_\tau$ is also a function of $t.$ We apologize for the confusing choice of notations, we will replace $\kappa_\tau$ with $\kappa_{t,\tau}$ in the revised paper.

• should $\kappa_\tau |\nabla F(x_{t-\tau})|^2$ be $\kappa_\tau^2$ instead?

We used Jensen's inequlity: $\|\sum\kappa_\tau\nabla F(x_{t-\tau})\|^2 \leq \sum\kappa_\tau\|\nabla F(x_{t-\tau})\|^2,$ with $\sum \kappa_\tau \leq 1, \kappa_\tau \geq 0.$

• Top of page 13, eq 10, extra $+$ sign

Agreed, we will fix it.

It would be nice to have a more detailed comparison to correlated noise approaches for DP optimization

Thanks for bringing up these related references. Roughly speaking, these methods (KMST+, DMRST, and CDPG+) can be viewed as releasing a weighted prefix sum with DP noise, i.e., $A(G_{0:t}+W_{0:t}),$ where $A$ is the prefix sum matrix and $W_{0:t}$ is the i.i.d. DP noise. KMST+ and DMRST apply certain decomposition $A = BC$ and change the update to $B(CG_{0:t}+W_{0:t}) = AG_{0:t}+BW_{0:t},$ and CDPG+ provides a theoretical justification that when $B$ is a high-pass filter, and $g_t$ are correlated, the algorithm outperforms original DPSGD. In contrast, our method can be written as $AM(G_{0:t}+W_{0:t})$, where $M$ is a low-pass filter. We will discuss these methods in our revised paper. Due to response limitation, the detailed discussion is given in the comment below.

No batch size in Thm. 3

From eq(5) in theorem 2, we see that the only place $B$ appears in the proof is in the last term $\sigma^2_{SGD}/B$, which is dominant by the previous term $d\sigma^2_{DP}$. Therefore, the choice of $B$ does not play a critical role in the privacy-utility trade-off in Thm. 3. Similar results can also be found in e.g., Bassily et al., 2014, where $B$ also does not appear in the final bound.

LP filter on iterates of DP-SGD?

Thank you for pointing out this interesting direction. The exponential averaging version of your suggestion has been tried in De et al. 2022. Since our paper aims at gradient denoising, LP filter on the model for inference is out of the scope of the current paper, and we would like to leave it as a possible future direction.

$\quad$

Thank you for reading our rebuttal. We hope the above responses addresses your concerns, and if there are any remaining questions, we would be more than happy to continue discussing with you.

Thank you for your timely response and for increasing your score! We sincerely appreciate the time you spent reading our response and providing additional feedback.

We apologize for not elaborating further on our original response. We mistakenly assumed that you are asking about the power spectral density (PSD) plots, which are related to the auto-correlation coefficients and show the low-frequency property of the stochastic gradients in the frequency domain (as shown in Fig. 2 in the original manuscript and Fig. 4 in the PDF response). This was the reason we added Fig.4 in our rebuttal. The PSD plots are obtained by applying FFT to the auto-correlation coefficients. So, they are directly related to the auto-correlation plots. Having said that, it seems, unfortunately, we are unable to include more figures in the response, but by applying inverse FFT (iFFT) to the PSD, we can easily obtain the auto-correlation coefficients, and $c_\tau, c_{-\tau}.$ We will follow your suggestion and put the original auto-correlation coefficients directly showing $c_\tau$ and $c_{-\tau}$ in our revised paper.

Regarding your comment on the investigation of the auto-correlation vs filter coefficients, a frequency-domain illustration is given in Fig. 2(b) in the original paper, which plots the auto-correlation of the stochastic gradients after applying the filter. By an inverse FFT on it, we can observe the relation between the coefficients of the low-pass filter and the resulting auto-correlation coefficients.

To further address your question, we copy the first 10 coefficients of the auto-correlation of the stochastic gradients, and $\kappa_\tau$ of the filter:

It can be observed that the auto-correlation and the filter coefficients are all gradually decreasing as $\tau$ increases. We would include these discussions in our revision. Please let us know if our response answers your question.

Thank you again for your invaluable feedback.

Thank you for recognizing the contribution of our paper and providing detailed feedback to improve the paper. Our responses to your specific comments are listed below.

The authors use assumptions of bounded variance and gradient norm. However, these assumptions might not be true in real DP-SGD situations. The strong underlying assumption of the authors is that the whole-batch gradient directions are similar between timestamps ...

Let us review our main assumptions: Assumptions A.2 and A.3 require bounded gradient and bounded variance. These assumptions are standard for non-convex optimization and for DPSGD analysis, as discussed at the end of Sec. 2.1 of the manuscript. Specifically, the bounded variance assumption is standard for non-convex optimization. Notice that as long as the input is finite (e.g. pixels with finite RGB values), the variance is guaranteed to be bounded. The bounded gradient assumption is widely used in the analysis of DPSGD, and when the model parameters have a finite value, the gradient is always bounded. As you pointed out, A.4 is another major assumption that requires certain properties on the auto-correlation of the gradient. Notice that this assumption is on the gradient itself (and not noisy/stochastic versions). We provided a theoretical justification in the worst-case, in Sec. 3 and lines 232-235, that when the learning rate is sufficiently small, A.4 always holds. Moreover, we have provided the empirical verification in Fig. 2, where the mini-batch gradients are correlated. We provided more figures illustrating the auto-correlation of the mini-batch gradient in the attached PDF. Please let us know if this addresses your concern.

Using a low-frequency signal ... I cannot agree that this approach is orthogonal to conventional approaches depending on timestamps...

We believe there is some misunderstanding about our claim of orthogonal to noise reduction method in the time domain. First, we agree with the reviewer that our approach is not orthogonal to the momentum method, and other possible methods that depend on timestamps, as we discussed its connection with the momentum method in Sec. 4, lines 218-221, Sec. 5.3, lines 265-268. Instead, our approach is orthogonal to the approaches that do not rely on timestamps, e.g., modifying clipping operation, changing model structures, and using noise scheduler. These approaches aims at reducing the impact of the DP noise for each step independent of other steps and DOPPLER can be combine with these approaches. We will further clarify this point in our revision.

There are some existing papers that investigated the use of previous gradients in DP-SGD that are missing from the discussion...

Thank you for bringing up this relevant literature. We will cite these papers and discuss them in our revised version. Notice that the philosophy and motivation behind DP-SAT and DOPPLER are different: DP-SAT aims at finding a "flat" minimizer. Moreover, their approach is different. In particular, the momentum used in DP-SAT is only for an estimation of the perturbation direction for SAM, which is not used for DP noise reduction. In contrast, DOPPLER aims to denoise the gradient using the past gradient with a low-pass filter.

For the momentum approaches, why don’t you use $\alpha$ and $1-\alpha$ for the popular setup in EMA? In the appendix, I saw that tuning both $\alpha$ and $\beta$ requires quite a large search space. I wonder if the effectiveness of your methods comes from the enlarged search space. Could you provide an ablation study for this search space?

Thank you for this nice and critical comment. We would like to clarify how the filters are designed:

1. As discussed in Sec. 4 and 5.3, Momentum-SGD (choose $\alpha, 1-\alpha$) is a special case of the low-pass filter. However, such a choice might not achieve the best performance. Therefore, filters with more coefficients are needed, which admits a larger search space and possibly better performance.
2. The effectiveness of the method indeed comes from the enlarged search space and the frequency-domain viewpoint to efficiently design the filter coefficients. As discussed in the general response, there exists a series of mature methods to choose the filter coefficient.
3. In Fig. 6 in the original paper, we provide an ablation study to the choice of filter coefficients, and more choice of filter coefficients are provided in the PDF response.

The authors try to make a theoretical analysis (line 233), however, it may not be true in the real application. The learning rate of private training is much larger than standard training, where it cannot be lower than $O(\sqrt{1/\tau})$ as far as I know.

Thank you for your detailed feedback on our paper. In our paper, the requirement of the learning rate is $\eta = O(\sqrt{1/\tau})$, which ensures the auto-correlation to be positive in the worst case. This requirement aligns with what the reviewer has suggested. Moreover, in real-world applications, the gradient can still be positively correlated for larger values of the learning rate. For example, for quadratic problem $1/2\|Ax+b\|^2$, by choosing $\eta \leq 1/\|A^\top A\|,$ it is guaranteed that the grdients are positively correlated. This does not invalidate our result as we only provide a bound. Moreover, as illustrated in Fig. 2 (blue line), the PSD of the stochastic gradient is low-frequency, indicating the positive correlation of the stochastic gradients in real-world applications. Similar observations were also made in other papers, e.g., [DPDR] Liu et al. 2024, Fig. 1.

$\quad$

Finally, we would like to thank you for reading our rebuttal and providing detailed feedback to us. We did our best to respond to all your comments. Please let us know if there are still any remaining questions and we would be more than happy to continue the discussion.

Thank you for recognizing the contribution of our signal processing perspective, and the precious advice for improving the presentation. We would like to address the reviewer's concerns as follows. $\quad$

Can you provide some intuition about what does it mean to convert a series of gradients from time to frequency domain? It might be useful to have this somewhere (even if it's in appendix) to help readers understand the approach better.

Great suggestion! We agree that the paper can benefit from further discussion of the background. Please take a look at our proposed new appendix section in our general response to all reviewers and let us know if you would like to see further discussions on any specific background. The intuition of converting the gradient sequence in the time domain to the frequency domain is that the frequency domain representation helps us to capture and utilize certain properties of the gradient that are hard to observe in the time domain, e.g., the separability of the noise and gradient as discussed in Sec. 3.

Line 167-168: In Figure 1a, auto-correlation coefficient first increases and then decreases with time, but description seems to state something else. Can you clarify?

Let us clarify that in Fig. 1(a) (also in 1b) and 1c)), we shift the x-axis so that $\tau = 0$ ($\nu = 0$) is in the middle of the plots, because the auto-correlation coefficients are symmetric, i.e., $\mathbb{E}[\nabla F(x_t)^\top\nabla F(x_{t+\tau})] = \mathbb{E}[\nabla F(x_t)^\top\nabla F(x_{t-\tau})].$ Therefore, the auto-correlation coefficients decreases as the time-lag $|\tau|$ increases, instead of first increase then decrease.

Line 168-169: How do you compute PSD? How do you go from the first equation in Section 3 to drawing Figure 1b, 1c?

As explained in lines 162-163 in the original manuscript, the PSD of the gradient is computed by applying a Fourier transform to the auto-correlation coefficients in figure 1(a), i.e., $P(\nu) = \mathcal{F}\{\phi(\tau)\}.$ The explicit transform can be found in the general response.

Line 187-188: Why can a linear low pass filter be written as in the first equation of section 3.1?

A linear filter is a filter whose output is a linear combination of the past input signals, which can be written in the general form of $m_t = -\sum_{\tau=1}^{n_a}a_\tau m_{t-\tau} + \sum_{\tau=0}^{n_b}b_\tau g_{t-\tau}.$ The choice of the filter coefficients $\{a_\tau\}, \{b_\tau\}$ determine whether the filter is a high-pass, low-pass, band-pass or band-stop filter. This should be clear after we add the suggested new appendix on the background.

What are the sizes of the models used?

In the experiments, we report the results on a 5-layer CNN (223K), ViT-small (30.1M), EfficientNet (5.33M), and ResNet-50 (25.6M) for the CV experiments (in Appendix B.4 in the original manuscript), and a RoBERTa-base model with 125M parameters. Note that for DP pre-training, these models are considered as large models compared with the ones used in the existing literature.

Why do you not compare with SOTA methods, e.g., De et al. 2022 or Shejwalkar et al. 2022?

We would like to clarify that the SOTA methods, De et al. 2022 and Shejwalkar et al. 2022, implement a series of engineering tricks to improve the performance of DP training, as discussed in Sec 2.3 in the paper. We implemented several methods proposed by these papers in our experiments, including model design, group normalization, bounded activation, and large batch size. However, the rest of the engineering tricks (in JAX) are not memory/time efficient and are incompatible with our implementation in PyTorch. Therefore, although we did not directly compare these SOTA methods with their DOPPLER version, our numerical experiments implicitly adopt part of these SOTA methods in our comparison.

Proposed method, although motivated from enabling DP for large models, cannot be used for large models due to computation inefficiency.

We believe that the reviewer's comment on computation inefficiency is not entirely accurate. We agree with the reviewer that the proposed method requires more memory than the standard DP optimizer. However, the computational cost of applying the Low-pass filter is at the same level as momentum-SGD, with an overhead of combining the past gradients. This cost is negligible compared with the backward and clipping steps. For example, when using DPSGD to train a ResNet with Cifar-10, the backward and clipping takes 16240ms (406ms/50 samples) for one minibatch (2000 samples), while the SGD update takes 52ms, and for LP-DPSGD, the Low-pass filter only takes an extra 74ms, i.e., $\sim0.5\\%$ overhead in computation.

Current set of results lacks depth and should be improved.

We believe our current results covers a wide range of algorithms, models, and datasets. We also provide more numerical results in the PDF response for in-depth investigation on the filter design. However, we understand that this is a bit subjective matter and readers may expect different/additional experiments. We would gladly add more if you could please tell us what is missing in the experiments, and how we can address it.

Paper writing/clarity can be improved (see questions/weaknesses). Equations are not properly numbered.

We agree with the reviewer and appreciate for the valuable feedback, and we will an additional section to the appendix covering the background. Also, we will revise the main manuscript as the reviewer suggested to clarify the points. We will re-label the equations. However, we believe that in the current manuscript, all referred equations have been labeled.

$\quad$

Thank you for reading our rebuttal. We hope the above responses have addressed your concerns.If there are still any questions, we would be more than happy to continue discussing with you.