DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction

Authors: xinwei  zhang
zhiqi  bu
amazon mingyi hong
meisam  razaviyayn
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 06:36:25

Abstract: Privacy is a growing concern in modern deep-learning systems and applications. Differentially private (DP) training prevents the leakage of sensitive information in the collected training data from the trained machine learning models. DP optimizers, including DP stochastic gradient descent (DPSGD) and its variants, privatize the training procedure by gradient clipping and *DP noise* injection. However, in practice, DP models trained using DPSGD and its variants often suffer from significant model performance degradation. Such degradation prevents the application of DP optimization in many key tasks, such as foundation model pretraining. In this paper, we provide a novel *signal processing perspective* to the design and analysis of DP optimizers. We show that a ''frequency domain'' operation called *low-pass filtering* can be used to effectively reduce the impact of DP noise.  More specifically, by defining the ''frequency domain'' for both the gradient and differential privacy (DP) noise, we have developed a new component, called DOPPLER. This component is designed for DP algorithms and works by effectively amplifying the gradient while suppressing DP noise within this frequency domain. As a result, it maintains privacy guarantees and enhances the quality of the DP-protected model. Our experiments show that the proposed DP optimizers with a low-pass filter outperform their counterparts without the filter on various models and datasets. Both theoretical and practical evidence suggest that the  DOPPLER is effective in closing the gap between DP and non-DP training.

Main paper: 
 introduction: 
 A rapidly growing number of modern machine learning applications in computer vision, natural language processing, and their mixtures rely on the development of large foundation models, whose performance heavily depends on the huge amounts of data collected from individual users. The leakage of potentially sensitive information in training data has become an increasingly critical issue when releasing and using machine learning models. Unfortunately, modern complex models have a strong ability to memorize the exact training data during the training processing Carlini et al. (2021) ; Pan et al. (2020) . To alleviate the possible privacy leakage in the model training procedure, privacy-preserving optimization has attracted both researchers' and practitioners' interests.Differential Privacy (DP) Dwork and Roth (2014) provides a strong theoretical guarantee with an easy and nearly plug-and-play mechanism, i.e., gradient clipping and noise injection, for existing optimization algorithms to guarantee the privacy of training procedures Abadi et al. (2016) . By directly applying the DP mechanism to existing optimizers, DP optimizers have achieved decent performance in fine-tuning foundation models (Yu et al., 2021; Bu et al., 2024) or training small models (De et al., 2022) . However, the performance of the pretraining tasks and training large foundation models using DP optimizers still remain unsatisfactory. This is because, as the DP theory suggests, the amount of injected DP noise is proportional to the number of model parameters and the total update steps (Abadi et al., 2016) . Thus, the performance of large foundation models trained with DP optimizers degrades severely. To put it in perspective, pretraining a foundation model for an image classification task on the CIFAR dataset from randomly initialized weights takes around 100 epochs, with 300K steps (Dosovitskiy et al., 2020) ; the pretraining of BERT for natural language processing task takes 1M steps (Devlin et al., 2019) , and pretraining LLAMA takes more than 250K steps (Touvron et al., 2023) . The number of trainable parameters is also huge for these tasks, ranging from 300M to 70B. Therefore, the huge amount of injected DP noise severely degrades the performance of the final model trained with DP optimizers.To improve the performance of DP optimizers, existing research takes two approaches: 1) designing models that are less sensitive to DP noise, e.g., using group normalization, weight standardization, weight smoothing, and smooth activation layers (De et al., 2022; Papernot et al., 2021; Wang et al., 2020) , and 2) designing adaptive DP optimizers that inject relatively smaller noise, e.g., adaptive clipping, sparse gradient, and dynamic privacy budget (Andrew et al., 2021; Yu et al., 2021; Luo et al., 2021; Hong et al., 2022) . However, existing methods only work for certain models and tasks at the cost of consuming more privacy budget. Moreover, most of the methods only demonstrate empirical improvements and do not provide theoretical justification for improving DP optimization. Therefore, there is a strong need for an approach that improves the performance of DP optimizers, which has the following properties: 1) has a solid theoretical guarantee, 2) is easy to implement, and 3) is compatible with most existing DP optimization improving methods. Motivated by the above needs, in this paper, we develop a module that can easily be integrated into the DP training optimizers. We provide both theoretical and empirical justification for our proposed module. Specifically, our contributions are as follows:• Frequency-domain analysis: We introduce the notion of frequency domain analysis on (DP) optimizers. This analysis sheds light on how "noise" affects the "signal" part of the update directions viewed as a sequence of update steps, rather than independent update steps. • Low-pass filter approach: Based on our frequency-domain analysis, we propose a low-pass filtering approach named DOPPLER, that post-processes the privatized gradient to reduce DP noise and improve DP optimizers' performance. Our low-pass filter reduces noise in the frequency domain, which is orthogonal to existing DP noise reduction approaches in the time domain and, therefore, can be easily combined with other existing techniques to further reduce noise. • Theoretical Analysis: We provide a novel theoretical analysis for the proposed low-pass filtering approach. Specifically, by introducing certain frequency domain assumptions on the gradients, we provide the convergence and privacy guarantee for DPSGD with the low-pass filter. Unlike existing methods that involve trading off noise with bias (e.g., adaptive clipping), or based on approximation (e.g., low-rank decomposition), our proposed algorithm does not introduce extra bias, model modification, or extra privacy cost. • Numerical results: Our extensive numerical experiments compare the performance of a variety of DP optimizers with and without the low-pass filter on different models and datasets. Our results show that DP optimizers equipped with the low-pass filter outperform the ones without the filter. 
preliminaries: 
 In this section, we discuss notations, assumptions, and some related prior work on DP optimization:In this paper, we aim to optimize the Empirical Risk Minimization (ERM) problem:EQUATIONHere, D = {ξ i } N i=1 is the training dataset with N samples. Further denote the lower bound of the problem as f ⋆ = inf f (x). Throughout the paper, we use (•) t to denote the update steps, N (µ, σ 2 ) to denote the Gaussian distribution with mean µ and variance σ 2 . We also assume the problem (1) satisfies the following assumptions.A 1 (Smoothness) F (•) is L-smooth, i.e., ∥∇F (x) -∇F (y)∥ ≤ L ∥x -y∥ , ∀x, y ∈ R d .A 2 (Bounded Variance) The per-sample gradient has bounded variance, i.e.,E ξ∈D ∥∇f (x; ξ) -∇F (x)∥ 2 ≤ σ 2 SGD , ∀x ∈ R d .A 3 (Bounded Gradient) The per-sample gradient has a bounded norm, i.e.,∥∇f (x; ξ)∥ ≤ G, ∀x ∈ R d , ξ ∈ D.Let us briefly comment on these assumptions: A1 and A2 are standard in non-convex optimization (Allen-Zhu and Hazan, 2016; Zaheer et al., 2018; Abadi et al., 2016) ; and A3 is commonly used in analyzing the convergence of DP algorithms (Abadi et al., 2016; Wang et al., 2020; Andrew et al., 2021) to avoid introducing the clipping bias. Since the impact of clipping is not the major focus of this paper, we follow the existing analyses and use A3 to simplify our theoretical analysis.Differential privacy is a gold standard of privacy to protect the privacy of individuals:Definition 1 ((ϵ, δ)-DP (Dwork and Roth, 2014 )) A randomized mechanism M is said to be (ϵ, δ)-differentially private, if for any two neighboring datasets D, D ′ (D, D ′ differ only by one sample) and for any measurable output set S, it holds thatPr[M(D) ∈ S] ≤ e ϵ Pr[M(D ′ ) ∈ S] + δ.A popular practical differentially private approach to finding an (approximate) solution to the ERM optimization problem (1) is Differentially Private Stochastic Gradient Descent (DPSGD) (Abadi et al., 2016) and its variants, including DP-Adam and DP-Lora (Yu et al., 2021) . To protect DP, DPSGD considers applying the commonly used Gaussian mechanism (Dwork and Roth, 2014; Abadi et al., 2016) at each iteration of the stochastic gradient descent method. The Gaussian mechanism provides a DP guarantee by injecting additive noise into the algorithm output.Definition 2 (Gaussian Mechanism (Dwork and Roth, 2014; Zhao et al., 2019) ) Suppose an algorithmA : D → R d has ℓ 2 sensitivity ∆ A , i.e., max D,D ′ ∥A(D) -A(D ′ )∥ ≤ ∆ A .Then, for any ϵ > 0 and δ ≤ 0.05, by adding random Gaussian noise to the output of the algorithmM (x) = A(x) + w, with w ∼ N (0, σ 2 DP I d ), where σ DP = ∆ A √ 2 ln(1/2δ) ϵ + ∆ A √ 2ϵ , the algorithm M is (ϵ, δ)-DP. Algorithm 1 DPSGD algorithm Input: x 0 , D, C, η, σ DP for t = 0, . . . , T -1 do Uniformly draw minibatch B t from D g t = 1 B ξi∈Bt clip (∇f (x t ; ξ i ), C) + w t where w t ∼ N (0, σ 2 DP • I d ) x t+1 = x t -η t g t , end forThe DPSGD algorithm, presented in Algorithm 1, first samples a mini-batch B t of size B and computes the per-sample gradient at each step t. Then, it applies the Gaussian mechanism by clipping the per-sample gradient and injecting DP noise. The clipping operation bounds the sensitivity of the stochastic gradients to C, e.g., clip (∇f, C) = min 1, C ∥∇f ∥ ∇f or C ∥∇f ∥ ∇f. Finally, the algorithm updates the model parameter with the privatized mini-batch gradient. It has been shown that DPSGD guarantees (ϵ, δ)-DP with sufficiently large injected noise (Abadi et al., 2016) .Theorem 1 (Privacy Guarantee (Abadi et al., 2016) ) Given N, B, T and C, there exist positive constants u, v, such that for any ϵ < uB 2 T N 2 , δ > 0, by choosing σ 2 DP ≥ vC 2 T ln( 1 δ ) N 2 ϵ 2, Algorithm 1 is guaranteed to be (ϵ, δ)-DP.Effective DP training: Improving the performance of DP training has been widely studied. Adaptive gradient clipping (Andrew et al., 2021) estimates the size of the gradient privately and adaptively changes the clipping threshold to avoid injecting large DP noise; automatic clipping (Bu et al., 2024) replaces the clipping operation with normalization to avoid injecting large DP noise when the gradient becomes small; Hong et al. (2022) proposes using a time-varying privacy budget at each step which injects non-static DP noise based on the gradient to reduce the impact of the DP noise. As the injected DP noise variance scales with the model size, reducing the number of trainable parameters with adapters, low-rank weights, or quantized models has also been used to reduce the DP noise magnitude (Yu et al., 2021; Luo et al., 2021; Yu et al., 2021) . De et al. (2022) ; Papernot et al. (2021) ; Wang et al. (2020) use special model structures that are less sensitive to DP noise, including group normalization, weight standardization, smoothed activation, and smoothed weights.These methods aim to reduce the magnitude of the injected DP noise or make the model and/or the DP algorithm less sensitive to large DP noise. However, the improvement is either empirical or only works for specific model structures and is unable to be generalized to other DP training tasks.Signal processing for optimization: A few existing works analyze the optimization procedure from the signal processing perspective. They mainly focus on optimizing strongly convex problems using deterministic algorithms (Hu and Lessard, 2017; An et al., 2018) ; Gannot (2022) provides stability and convergence analysis from the frequency domain for inexact gradient methods. However, the results are still restricted to non-DP optimization and to strongly convex problems. 
a signal processing perspective: 
 As discussed in Section 2.3, most of the existing works that aim to improve the performance of DP training are reducing the per-iteration injected DP noise. These approaches treat the update directions in each step independently, omitting the underlying dynamics and correlations between the steps. However, the gradient directions typically change smoothly due to the smoothness of the machine-learning model; therefore, the update directions are not independent over time.With the intuition that the gradients over iterations are not independent, we provide the frequencydomain analysis of the stochastic gradients. Specifically, in the frequency domain, we treat the (stochastic) gradients from t = 0 to t = T as a time series and analyze the long-term correlation and dependencies across all gradients. In contrast, the time domain refers to the analyses that only focus on the gradient at step t: for instance, Bu et al. (2024) ; Yang et al. (2022) leverage the L-Lipschitz smoothness or the second-order Taylor expansion to bound/approximate the objective function in step t after the update is performed. By analyzing the DP optimizers' updates in the frequency domain, we can make use of our prior knowledge of the correlation among the update directions.To explain our motivation in a simplified manner, we temporarily ignore the per-sample gradient clipping and focus our narrative on the noise: suppose x t+1 = x tη t g t with g t = ∇F (x t ) + w t and w t being the Gaussian noise. We will come back to the clipping in Section 3.2. In what follows, we decompose the sequence of stochastic gradients {g t } into two parts: 1) the gradient signal {∇F (x t )} and the noise {g t -∇F (x t )}. We employ the power spectral density (PSD) to characterize the distribution of power into frequency components of a continuous signal. Mathematically, the power spectral density (PSD) of a sequence {s t } t=0,1,... is P s (ν) = F{ϕ s (τ )}, where F denotes the Fourier transform from time domain (τ ) to frequency domain (ν) (Oppenheim et al., 1996) , and ϕ is the auto-correlation coefficient as ϕ s (τ ) = E ⟨s t , s t-τ ⟩ .On the one hand, the gradient sequence {∇F (x t )} t=0,1,... can be treated as a low-frequency signal, where we apply the Cauchy Schwarz inequality to getϕ ∇f (τ ) = E ⟨∇F (xt), ∇F (xt-τ )⟩ = 1 2 E ∥∇F (xt)∥ 2 + ∥∇F (xt-τ )∥ 2 -∥∇F (xt) -∇F (xt-τ )∥ 2 ≥ 1 2 E ∥∇F (xt)∥ 2 + ∥∇F (xt-τ )∥ 2 -L 2 η 2 τ τ i=1 ∥gt-i∥ 2 .This indicates that as long as the stepsize η is small, the auto-correlation coefficients decrease as τ increases (as illustrated in Figure 1a , blue line). Therefore, the PSD also decreases as ν increases, i.e., {∇F (x t )} is a low-frequency signal (as illustrated in Figure 1b , blue line). Figure 1 : An illustration of the auto-correlation ϕ(τ ) and power spectrum density P (ν) of {∇F (x t )} and w t where ϕ ∇f decays proportional to τ 2 and w t is a white noise. (c) illustrates how an ideal low-pass filters out the high-frequency noise and keeps the low-frequency signal.On the other hand, the noise signal {w t } := {g t -∇F (x t )} is a white noise, where its autocorrelation is non-zero when τ = 0 and is zero otherwise (as illustrated in Figure 1a , red line):ϕ w (τ ) = E ⟨w t , w t-τ ⟩ ≤ dσ 2 DP + σ 2 SGD B , τ = 0 = 0, otherwise. Therefore, P w (ν) = dσ 2 DP + σ 2 SGD B, ∀ν (as illustrated in Figure 1b , red line).From the above discussion, we observed that although the gradient and the DP noise are not separable in each step t (time-domain), they are distinguishable in the frequency domain. In particular, the noise power is equally distributed over all frequencies, while the gradient is concentrated around the lower frequencies. Therefore, we can apply the classical signal processing tools, such as frequency domain low-pass filters, to help improve the performance of DP optimization.A low-pass filter amplifies the low-frequency component of the signal and suppresses the highfrequency part. Figure 1c shows an ideal low-pass filter that keeps the frequencies where the gradient is larger (ν ∈ [-0.6, 0.6]) and blocks the frequencies where the noise is larger (ν < -0.6∪ν > 0.6).Signal-to-Noise Ratio (SNR) is a useful measure to characterize the quality of a noisy signal, i.e., the privatized gradient {g t } in DP optimization. Given the PSD of the gradient and the noise, the SNR of the privatized gradient is ν P ∇f (ν) ν Pw(ν) . As illustrated in Figure 1 , when there is no low-pass filter (i.e., in Figure 1b ), the SNR is small as the noise dominates in the high-frequency. In contrast, by applying the low-pass filter (i.e., in Figure 1c ), most of the signals in the low-frequencies are kept, and the noise in the high frequencies is filtered, so the SNR increases. A linear low-pass filter on {g t } can be written as a recursive linear combination of the history signals:m t = - na τ =1 a τ m t-τ + n b τ =0 b τ g t-τ ,where the sequence {m t } is the filtered output, {a τ }, {b τ } are the filter coefficients. Additinally, the "order" of the filter is defined as max{n a , n b }. By carefully designing the coefficients, the low-pass filter can take different shapes and filter different frequencies.In contrast to low-pass filters, the existing approaches improving the performance of DP optimization can be viewed as increasing the SNR in the time domain, i.e., reducing the magnitude of the noise injected in each step while preserving most of the gradient signal. Because the low-pass filter reduces noise in the frequency domain, and the existing noise reduction approaches lie in the time domain, the two approaches are orthogonal to each other. Therefore, the low-pass filter can be combined with existing approaches to further improve the DP optimizers' performance.The above analysis assumes that the clipping operation is inactive by choosing a large enough clipping threshold C. In practice, the clipping operation is usually active. By assuming the clipped gradient ∇F C (x) has zero curl, the DP optimizer optimizes an alternative problem:min x∈R d F C (x), where F C (x) = 1 0 ∇F C (zx) ⊤ xdz, ∇F C (x) = 1 N ξ∈D clip (∇f (x; ξ), C) . (2)Then the signal of the DP optimizer becomes the gradient of the alternative problem {∇F C (x t )} and the noise becomes{w t } = {g t -∇F C (x t )}. As clipping is a non-expansive operator, i.e., ∥clip (x, C) -clip (y, C)∥ ≤ ∥x -y∥ , the alternative problem F C (•) is also L ′ -smooth with L ′ ≤ L.Therefore, a similar argument could be made on the gradient signal {∇F C (x t )} and the noise {w t }} when the clipping threshold is small and the clipping operation is active. 
the proposed doppler approach: 
 Building on the discussions in Section 3, we proposed a universal approach to improve DP optimization performance: DP OPtimizer with Low-Pass fiLter for noisE Reduction (DOPPLER). Taking DPSGD as an example, by applying DOPPLER, the main steps of the modified DPSGD algorithm are illustrated in Algorithm 2. The key steps of the low-pass filter are described in Lines 6-8. Line 6 computes the filtered update direction m t as a recursive linear combination of the current gradient, past gradients, and past update directions. m t estimates the first moment of the privatized gradient and can be expanded as a moving average of g t , i.e., m t = t+n b τ =0 κ τ g t-τ . However, as {m τ }, {g τ } are initialized with zeros (Line 2), m t is biased towards zero, especially in the early steps. To correct the initialization bias, in Line 7, the optimizer computes the bias correction factor c a,t that is used in Line 8 to guarantee the weights κ τ in the moving average are summed to 1.Connection to momentum method: The DOPPLER approach is a generalized version of the momentum method from a first-order filter to higher orders. The momentum method uses one buffer m t to store the exponential moving average of g t , while DOPPLER uses multiple buffers {m t-τ } na-1 τ =0to compute a more complex moving average of g t .Compatibility: Algorithm 2 demonstrates how DOPPLER can be combined with the DPSGD algorithm while it is not restricted to DPSGD. The DOPPLER approach is compatible with other advanced DP optimizers, e.g., Adam (Kingma and Ba, 2015; Tang et al., 2024) and GaLore (Zhao et al., 2024) . It serves as a base component for DP optimizers to improve their performance.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We provide the codes in the supplementary and the parameters are given in the experiment section and the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
convergence analysis: 
 In this section, we analyze the convergence of DPSGD with DOPPLER. First, we make the following assumption on the gradient auto-correlation coefficients.A 4 (Gradient auto-correlation) For all t ∈ {0, . . . , T -1}, there exists sequences {c τ }, {c -τ } such that the following condition holds:⟨∇F (x t ), ∇F (x t-τ )⟩ ≥ c τ ∥∇F (x t )∥ 2 + c -τ ∥∇F (x t-τ )∥ 2 , ∀τ ≥ 0, (3) c -τ ≥ 0, ∀τ ≥ 0. (4) Algorithm 2 DPSGD with DOPPLER 1: Input: x 0 , D, η, C, σ DP , {a τ } na τ =1 , {b τ } n b τ =0 2: Initialize: {m -τ } na τ =1 = 0, {g -τ } n b τ =1 = 0, {c a,-τ } an τ =1 = 0, {c b,-τ } bn τ =0 = 0 3: for t = 0, . . . , T -1 do 4:Randomly draw minibatch B t from D 5:g t = 1 |Bt| ξ∈Bt clip (∇f (x; ξ), C) + w t # Compute private gradient where w t ∼ N (0, σ 2 DP • I d ) 6: m t = - na τ =1 a τ m t-τ + n b τ =0 b τ g t-τ # Apply filter 7: c b,t = 1, c a,t = - na τ =1 a τ c a,t-τ + n b τ =0 b τ c b,t-τ # Compute bias 8: mt = m t /c a,t # Correct initialization bias 9:x t+1 = x tη mt # Parameter update 10: end for Clearly, we have c 0 = 1 2 > 0. From the discussion in Section 3, we see that the above assumption can be satisfied as long as η is small enough, i.e.,η ≤ (1 -2c -τ ) ∥∇F (x t-τ )∥ 2 + (1 -2c τ ) ∥∇F (x t )∥ 2 L τ τ1=1 ∇F (x t-τ1 ) 2 + τ (dσ 2 DP + σ 2 SGD /B) = O 1 τ .The pattern of the sequence {c τ } characterizes the frequency of the gradients as discussed in Section 3. If c τ 's are all positive and slowly decreasing, then ∇F (x t ) and ∇F (x t-τ ) are highly correlated, so {∇F (x t )} lies in lower frequencies. However, c τ is not necessarily positive. When some of c τ 's are negative, or c τ 's are oscillating between positive and negative values, it means that ∇F (x t ) and ∇F (x t-τ ) are negatively correlated, and {∇F (x t )} may contain high-frequency signals.Before we present the theorem, let us define the normalized SNR asEQUATIONand define the expanded coefficients κ τ asκ τ = min{n b ,τ } τ2=0 b τ2 na τ1=1 z a,τ1 (p a,τ1 ) τ -τ2 , s.t. na τ =1 z a,τ 1 -p a,τ x = 1 1 + na τ =1 a τ x τ , (6) which satisfies m t = - na τ =1 a τ m t-τ + n b τ =0 b τ g t-τ = t τ =0 κ τ g t-τ .Note that p a,τ might be complex, but κ τ are guaranteed to be real. With A4, we have the following convergence result for Algorithm 2.Theorem 2 (Convergence) Assume the problem satisfies A1-A4. By choosing C ≥ G, η ≤ min{ 2c-τLκτ }, and running Algorithm 2 for T iterations, the algorithm satisfies:EQUATIONwhere we defineS T = T -1 t=0 t τ =0 c τ κ τ = O(T ); the expectation is taken over t = 0, . . . , T -1, such that P (t) = t τ =0 cτ κτ S T .The proof of Theorem 2 is given in Appendix B. Compared with vanilla DPSGD (Abadi et al., 2016) , by adopting DOPPLER the noise is scaled by a factor of 1 2SNR . Thus, as long as SNR > 1 2 , the noise is reduced. Next, we will use the above result to obtain privacy-utility tradeoff.Our low-pass filter is post-processing on the privatized gradient. Since DP is immune to postprocessing Dwork and Roth (2014) , Algorithm 2 provides the same DP guarantee as DPSGD, satisfying Theorem 1. By directly combining Theorem 1 and Theorem 2, we can obtain the following privacy-utility trade-off for Algorithm 2.Theorem 3 (Privacy-utility trade-off) Assume the problem satisfies A1-A4. By choosing C = G,σ 2 DP = C 2 T ln(1/δ) N 2 ϵ 2 , η ≤ min{ 2c-τ Lκτ }, and running Algorithm 2 for T = O N ϵ √ SNR(F (x0)-F ⋆ ) C √ dL ln(1/δ)iterations, the algorithm satisfies (ϵ, δ)-DP and the expected gradient satisfies:E t∼P (t) ∥∇F (x t )∥ 2 = O C dL(F (x 0 ) -F ⋆ ) ln(1/δ) √ SNRN ϵ ,whereP (t) = t τ =0 cτ κτT -1 t=0 t τ =0 cτ κτ and κ, SNR are defined in (6), (5), respectively. Theorem 3 implies that DPSGD with DOPPLER shares the same convergence rateO C √ d ln(1/δ) N ϵas the vanilla DPSGD (Abadi et al., 2016) . However, by using the low-pass filter, the performance of DPSGD improves by a constant factor 1 √ SNR , which is discussed next.Here, we provide SNR value for some choices of the filter coefficients and discuss how to design low-pass filters.• For SGD (no filter), we have κ 0 = 1, and κ τ = 0, ∀τ > 0. Then, the normalized SNR is SNR = 1 2 . This recovers the convergence result for DPSGD in Abadi et al. (2016) . • Momentum-SGD Cutkosky and Mehta ( 2020) is a special case of the low-pass filter, with filter coefficients: a 1 = -0.9, b 0 = 0.1. and κ τ = 0.1 × 0.9 τ . Then, the normalized SNR is SNR ≥ 1.9 × 1 2 +t-1 τ =0 0.9 τ c τ , which is larger than vanilla DPSGD. This indicates that DPSGD with momentum can reduce the impact of DP noise compared with DPSGD w/o momentum.• We can further improve the SNR by optimizing the filter coefficients under a fixed order:EQUATIONFrom ( 8), we observe that the pattern of the auto-correlation coefficients c τ determines the choice of the filter coefficients. When κ τ ∝ c τ , SNR is maximized. However, in general, finding the optimal filter coefficients by optimizing (8) before training is difficult, as {c τ } is determined by the problem and the DP optimizer's updates and can be time-varying.Optimal FIR filter: When the filter takes the form of a finite impulse response (FIR) (i.e., a n = 0), we can estimate {c τ } and optimize b τ 's according to (8) during training. To estimate c τ , we have:cτ A4 ≤ ⟨∇F (xt), ∇F (xt-τ )⟩ -c-τ ∥∇F (xt-τ )∥ 2 / ∥∇F (xt)∥ 2 A2 ≤ E ⟨gt, gt-τ ⟩ -c-τ ∥gt-τ ∥ 2 -dσ 2 DP -σ 2 SGD /B / E ∥gt∥ 2 -dσ 2 DP -σ 2 SGD /B ≈ E ⟨gt, gt-τ ⟩ - 1 2 max{∥gt-τ ∥ 2 -dσ 2 DP , 0} / E max{∥gt∥ 2 -dσ 2 DP , ϵ1},where in the last approximation we set c -τ = 1 2 and assume dσ 2 DP dominates σ 2 SGD /B; the max are taken as ∥•∥2 ≥ 0 and we choose ϵ 1 = 10 -3 as a small positive number for numerical stability. τ =0 , so it does not spend an extra privacy budget or memory. Therefore, it can also be implemented along with DOPPLER, as an adaptive approach to adjust the filter coefficients for an optimal performance.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Yes, we included the code for the experiment in the supplementary Guidelines:• The answer NA means that paper does not include experiments requiring code. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: There is no significant societal impact of the work performed. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
numerical experiments: 
 In this section, we investigate how the low-pass filter affects the performance of various DP optimizers on different datasets, privacy budgets, and models. Due to the page limitation, detailed implementation and extra numerical results are given in Appendix C. The code for the experiments is available at https://anonymous.4open.science/r/Low-pass-SGD-C7A1.Dataset: We conduct experiments on computer vision datasets (MNIST, CIFAR-10, and CIFAR-100 (Krizhevsky et al., 2009) ) and natural language processing datasets, GLUE (Wang et al., 2018) .We conduct experiments on various models, including the 5-layer CNN described in De et al. (2022) , the modified ResNet in Kolesnikov et al. (2019) , EfficientNet with group normalization (Tan and Le, 2019) , and ViT (Dosovitskiy et al., 2020) for the CV tasks and RoBERTa-base (Liu et al., 2019) for the GLUE dataset. If not specified, the models are initialized with random weights without pretraining.Algorithm: We compared the impact of DOPPLER on several base algorithms, including the DP version of SGD, Adam, and GaLore. The updates of the algorithms are given in Algorithm 2 and Algorithm 3 in Appendix C.2. We use LPto denote the DP optimizer with DOPPLER. The learning rate, batch size, and number of training epochs are tuned for best testing accuracy using grid search. Detailed hyper-parameters and search grids are given in Appendix C.1. For all experiments, we fix the privacy parameter δ = 1/N 1.1 to obtain a reasonable privacy notion.PSD of the stochastic gradient: First, we record the stochastic gradients of SGD and SGD with DOPPLER training ResNet-50 for 40 epochs (T = 4000 steps) on the CIFAR-10 dataset. Then, we compute the PSD of the recorded stochastic gradients. The results are given in Figure 2 . We can observe that the recorded PSD of w t is filling all frequencies, and g t is a low-frequency signal.After applying the low-pass filter, the PSD of the filtered gradient lies in the low-frequency domain, and the high-frequency signals (and noise) are suppressed.Results for different datasets. The comparisons between LP-DPSGD and DPSGD on different datasets are given in Figure 3 . We can observe that LP-DPSGD outperforms DPSGD on MNIST, CIFAR-10, and CIFAR-100 datasets under the same privacy budget ϵ = 8. The results on the GLUE dataset is in Appendix C.3.The comparisons between DP optimizers, including DPSGD, DPAdamBC (Tang et al., 2024) , and DPGaLore (an extension of GaLore (Zhao et al., 2024) ), with and without DOPPLERis shown in Figure 4 . We can observe that all DP optimizers with DOPPLERoutperform the baseline under different levels of privacy budget ϵ ′ s. 
conclusion and discussion: 
 In this paper, we introduce a signal processing perspective to understand and analyze DP optimizers. By identifying the difference between the gradient and noise signal in the frequency domain, we propose DOPPLER, a low-pass filter approach, to filter out the DP noise and improve the signalto-noise ratio of the privatized gradient. Our proposed filtering method is compatible with existing DP optimizers, and extensive experiments have shown that the low-pass filter could improve DP optimizers' performance in the case when the DP noise is large, e.g., in the pertaining stage and for training large models.Limitations: Designing higher-order filters requires hyper-parameter tuning or prior knowledge of the gradients' auto-correlation pattern; implementing a high-order low-pass filter is memory inefficient (requires storing n a + n b optimization states for each trainable parameter), which eliminates the usage of the proposed method when optimizing very large-scale foundation models with limited memory resource. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The code provided contains the license information.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: In this section, we provide the details of the frequency-domain analysis and low-pass filter approach. First, we discuss the basic concepts in signal processing. Then, we discuss the filter method in signal processing.In signal processing, frequency domain analysis is used to analyze the periodical or long-term behavior of a (time series) signal/data. In the frequency domain analysis, we use the frequency ν as the indices of the signal, e.g., {X(ν)}, X(ν) ∈ C, where each term X(ν) records the amplitude and phase of the sine wave of frequency ν that composes the signal; in contrast, in the time domain, we use time t as the indices of a signal, e.g., {x t }, where each term x t records the value of the signal at a given time t. In this paper, we treat each coordinate i ∈ [1, . . . , d] of the privatized gradient over the iterates as an individual signal, i.e. {g 1 [i], g 2 [i], . . . , g T [i]}. Thus, the gradient over iterates gives us d one-dimensional signals, and we can look at their frequency domain representation of each signal.Benefit of frequency-domain analysis:• Certain properties of a signal can be hard to observe/characterize in the time domain. For example, a long-time correlation or a cyclic behavior of the signal is not easy to directly observe in the time domain. By converting the signal to the frequency domain, such properties can easily be captured and analyzed. For example, the signal x t = sin(t) has nonzero entries in almost all times. However, the frequency domain representation of this signal has only one entry that is nonzero, i.e., X(1) = 1 and all other entries are zero, i.e., X(ν) = 0, ∀ν ̸ = 1. This means x t has only one periodic signal in it.• Certain mathematical analyses can be significantly simplified in the frequency domain. For example, linear differential equations in the time domain are converted to algebraic equations in the frequency domain; filters as convolutions in the time domain are converted to point-wise multiplication in the frequency domain. These properties greatly simplify the analysis of the dynamics of the signals and filters (Oppenheim et al., 1996) .Transform from time to frequency domain: To obtain a frequency domain representation of a discrete signal, one can apply the Discrete Fourier transform (DFT) (F{x t } :EQUATIONν )) to the signal. By directly applying DFT to a signal and obtaining {X(ν)}, one can identify how the signal is composed of sin waves of different frequencies ν with their amplitudes and phases. In the paper, we apply DFT to the auto-correlation of a signal and obtain its power spectrum density (PSD). The PSD of a signal shows the distribution of the power of a signal on different frequencies. For example, the PSD of x(t) = sin(t) is P (ν) = 1/2 for ν = ± 1 2π and 0 elsewhere.Frequency filter: A frequency filter is a transformation of a signal that only allows certain frequencies to pass and blocks/attenuates the remaining frequencies.For example, for a signal x(t) = sin(t) + sin(10t), we can apply an (ideal) low-pass filter F (ν) = 1 when |ν| ≤ 1 2π and 0 otherwise.Then, after applying the filter, F * x(t) = sin(t), the output signal only keeps the low-frequency signal. In this work, we use (time-invariant) linear filters for DP noise reduction. A linear filter attenuates certain frequencies by using a linear combination of the input signal. Considering g t as the time signal, the general form of a linear filter on g t ism t = t τ =0 κ τ g t-τ = - na τ =1 a τ m t-τ + n b τ =0 b τ g t-τ ,where κ τ are the filter coefficients. The second formula is a recursive way of writing the filter.Filter design: The property of the filter depends on the choice of the filter coefficients. Designing a filter consists of the following steps:• Decide filter order/tab n a , n b . Larger n a , n b give the filter more flexibility and better possible performance, at a cost of more memory consumption. In our experiment, we tested on 0th-3rd order filters, i.e., max{n a , n b } ≤ 3. • Decide filter coefficients {a τ }, {b τ }. Filter design can, in general, be a complex procedure, and it involves deciding on trade-offs among different properties of the filter (Winder, 2002) . Two standard constraints on the filter coefficients are: a)a τ + b τ = 1, to ensure the filter has unit gain, i.e., the mean of the signal remains unchanged; and b) the solutions x to 1+ a τ x τ = 0 satisfies |x| < 1, to ensure the filter is stable, i.e., |κ t | < ∞. In the paper, we directly follow the design of the Chebyshev filter and Butterworth filter and tune their cut-off frequency (and ripple) to achieve the best performance and maintain these properties.A In contrast, our method can be written as AM (G 0:t + W 0:t ), where M is a low-pass filter.• The correlated noise methods and our proposed method can all be viewed as processing the signal in the frequency domain to "separate" the noise and the gradient. • The existing correlated noise methods 1) pre-process the gradient/noise to separate the gradient and the DP noise in the frequency domain, and therefore require careful design of the matrices B, C for each problem and optimizer, 2) require extra memory (O(d log(t)) to O(dt)), which is unrealistic for large scale training, and 3) only work for SGD update, since Adam cannot be written as such a prefix sum of privatized gradient. In contrast, our method 1) post-processes the noisy signal to extract the gradient from the noise from the frequency domain, 2) only requires O(d) extra memory, which is independent of t, and 3) is compatible with any first-order optimizer since it just post-processes the gradient.In this section, we provide the proof for Theorem 2. First, by A1, we haveEQUATION)We can expand m t as follows:m t = - na τ =1 a τ m t-τ + n b τ =0 b τ g t-τ m t + na τ =1 a τ m t-τ = n b τ =0 b τ g t-τ (1 + na τ =1 a τ z -τ )M(z) (a) = ( n b τ =0 b τ z -τ )G(z) M(z) (b) = 1 1 + na τ =1 a τ z -τ ( n b τ =0 b τ z -τ )G(z) M(z) (c) = na τ =1 z a,τ 1 -p a,τ z -1 ( n b τ =0 b τ z -τ )G(z) M(z) (d) = na τ1=1 z a,τ1 ∞ τ0=0 (p a,τ1 z -1 ) -τ0 ( n b τ2=0 b τ2 z -τ2 )G(z) M(z) (e) = n b τ2=0 b τ2 na τ1=1 z a,τ1 ∞ τ0=0 (p a,τ1 ) τ0 z -τ0-τ2 G(z) m t (f ) = n b τ2=0 b τ2 na τ1=1 z a,τ1 p τ0 a,τ1 g t-τ0-τ2 = t τ =0 κ τ g t-τ ,where in (a) we applies the z-transform Z{•} to both side of the sequence and use the property that Z{x t-k } = z -k X(z) (Oppenheim et al., 1996) ;(b) divides both sides by 1 + na τ =1 a τ z -τ ; in (c) we define {z a,τ }, {p a,τ } such that na τ =1 za,τ 1-pa,τ z -1 = 1 1+ na τ =1 aτ z -τ ; (d) expands 1 1-p = ∞ t=0 p t ;in (e) we rearrange there terms; in (f ) we apply the inverse z-transform and notice that g <0 = 0; and in the last equation we defineκ τ = min{n b ,τ } τ2=0 b τ2 na τ1=1 z a,τ1 (p a,τ1 ) τ -τ2. Plug the expansion of m t back to (9), we haveEQUATION)where in (a) we apply A3 and set C ≥ G, so that E[g t ] = ∇F (x t ); (b) applies A2 to the last term, and use the fact that w t ∼ N (0, σ 2 DP • I d ), and the noise are independent; (c) applies A4 to the first term and uses Jensen's inequality to the second term with ∥•∥ 2 being convex; in (d) we setη ≤ min τ { 2c-τ Lκτ }. Clearly, we have t τ =0 κ τ ≤ n b τ =0 bτ 1-na τ =1 aτ. Averaging over t = 0, . . . , T -1, and deciding both side by η, then the theorem is proved.In this section, we provide the missing details for the experiments in the main paper and additional experiments. In this section, we provide the hyper-parameter choices and search grids for different experiment settings. The search grids for the experiments are given in Table 1 . The filter coefficients used in the experiments are given in Table 2 . We provide the update rules for different DP optimizer variants used in the main paper in Algorithm 3. Different components of the optimizers are highlighted with different colors. the blue lines are additional steps for the Adam update, and brown lines are the components of the GaLore (Zhao et al., 2024) optimizer.Algorithm 3 DP-GaLore with DOPPLER 1: Input:x 0 , D, η, C, σ DP , {a τ } na τ =1 , {b τ } n b τ =0 , β, ϵ Adam , I, r 2: Initialize: {m -τ } na τ =1 = 0, {g -τ } n b τ =1 = 0, {c a,-τ } an τ =1 , {c b,-τ } bn τ =0 , v -1 = 0 3: for t = 0, . . . , T -1 do 4:Randomly draw minibatch B t from D 5:g t = 1 |Bt| ξ∈Bt clip (∇f (x; ξ), C) + w t # Compute private gradient where w t ∼ N (0, σ 2 DP • I d ) 6:if Use GaLore then 7:if t mod I ≡ 0 then 8: end if 14:P = FindProjector(g t ,v t = (1 -β)v t-1 + β(g t ) 2# Compute 2nd-order moment 15:m τ = - na τ =1 a τ m t-τ + n b τ =0 b τ gt-τ # Apply filter 16: c b,t = 1, c a,t = - na τ =1 a τ c a,t-τ + n b τ =0 b τ c b,t-τ # Compute bias 17: mt = m t /c a,t # Correct initialization bias 18: vt = v t /(1 -β t ) # Correct initialization bias 19: dt = mt / max{ √ vt , ϵ Adam } 20:if Use GaLore then 21:d t = P dt # Inverse projection to original dimension 22:else 23:d t = dt 24:end if 25:x t+1 = x tηd t # Parameter update 26: end forWe also conduct experiments on the GLUE dataset (Wang et al., 2018) . We fine-tune a RoBERTabase model (Liu et al., 2019) with the pretrained weights from https://huggingface.co/ FacebookAI/roberta-base. We follow the training script provided in Li et al. (2021) . The results are shown in Table 3 . For comparison, we also include the results from Li et al. (2021) . From the result of DPAdamBC and LP-DPAdamBC, we observe a slight accuracy improvement by using DOPPLER. However, in the fine-tuning tasks, we do not see significant improvement by using DOPPLER compared with the result reported in Li et al. (2021) .Table 3 : Test accuracy on language tasks with RoBERTa-base, ϵ = {3, 8}.Method ϵ = 3 ϵ = 8 MNLI QQP QNLI SST-2 MNLI QQP QNLI SST-2DPAdam (Li et al., 2021) In this section, we provide additional numerical results for several ablation studies w.r.t. the impact of different components in the experiment.Results for different models. The results for pretraining different models are given in Figure 7 . We observe that DOPPLERuniformly improves the DP pretraining performance for different model structures in pre-training.Ablation study on filter coefficients. The results for DPSGD accompanied with different low-pass filter coefficients in Table 2 are given in Figure 8a . We observe that different filters have different impacts on the algorithm's performance. For training on the CIFAR-10 dataset, the first-order filter is sufficient to have a good performance, while different coefficient choices for filters of the same 9 . We observe automatic clipping (Bu et al., 2024 ) (Norm) is better than vanilla clipping described in (Abadi et al., 2016) (Clip) ; treating all layers as one vector (Flat) is better than clipping each layer separately (Layer). Impact of learning rate and scheduler: We report part of our hyper-parameter search process. First, we report the test accuracy for different learning rates with fixed epochs ( 150) and (8, 1/50000 1.1 )-DP. The results are shown in Figure 10 . The optimal learning rate is 10 -3 ; a larger learning rate speeds up the training in the early stage but hurts the final performance; a smaller learning rate results in slow convergence. In Figure 11 , we compare the optimizer with and without a learning rate scheduler. Specifically, we use the Cosine-Annealing with warmup from Loshchilov and Hutter (2017) . From the result, we see when the number of epochs is large, the learning rate scheduler improves the training performance, while in the early stage, the scheduler slows down the convergence. Finetuning on CIFAR dataset: We also provide the experiment result for fine-tuning ViT models on the CIFAR-10 dataset under different privacy budgets. As illustrated in Figure 12 , the performance of LP-DPSGD improves by less than 1% for small ϵ ′ s. For larger ϵ ′ s, the gap is smaller. DOPPLER works has more improvement when the injected DP noise is large (i.e., ϵ is small). Justification: We provide assumption in the statement of the theorems and proofs in the appendix.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 


Decision: The reviewers were overall positive about the paper. There were some valuable concerns raised during the rebuttal period, especially by reviewer vvxz, in regards to the autocorrelation assumption. The authors diligently addressed most of the concerns raised. We would recommend the authors to include most or all of the discussion from the rebuttal in the next iteration of the paper.

Reviews: review: paper_summary: paper_summary: This paper proposes DOPPLER mechanism to post-process DP gradients and reduce noise in them, before updating the model. The work makes an observation that, in frequency domain, there is a clear distinction between distribution of SGD gradients and DP noise; the earlier lies in a small window of lower frequencies while the latter is distributed uniformly over all frequencies. Based on this observation, the DOPPLER mechanism uses a low-pass frequency filters that filters all high frequency signals, and hence, most noise is filtered while only some of the useful gradient is filtered thereby increasing overall SNR. Paper presents theoretical connection between SGD gradients and DP noise in the time and frequency domains, privacy analysis and empirical evaluation on standard benchmarks to showcase efficacy of DOPPLER.
strength_weakness: strength_weakness: - Connection between time/frequency domains is difficult to understand; adding some background might be useful 
- Motivation of the paper is to enable DP training for large, foundation models, but experiments are performed on relatively small models
- DOPPLER can be combined with any SOTA DP training, but results with such SOTA methods are missing
questions: questions: Section 3:
- 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.
- 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?
- Line 168-169: How do you compute PSD? How do you go from the first equation in Section 3 to drawing Figure 1b, 1c? 
- Line 187-188: Why can a linear low pass filter be written as in the first equation of section 3.1? 

Section 6:
- What are the sizes of the models used?
- Why do you not compare with SOTA methods, e.g., De et al. 2022 or Shejwalkar et al. 2022? 

Shejwalkar et al., Recycling Scraps: Improving Private Learning by Leveraging Intermediate Checkpoints, arXiv 2022
limitations: limitations: - Proposed method, although motivated from enabling DP for large models, cannot be used for large models due to computation inefficiency.
- Current set of results lacks depth and should be improved. 
- Paper writing/clarity can be improved (see questions/weaknesses).
  - Equations are not properly numbered.
paper_summary: paper_summary: This paper suggests the effects of a low-pass filter for private training with DP-SGD. After investigating the noise and true gradients during training, the authors propose using previous gradients and momentum to distinguish effective gradients from random noise. They empirically prove their idea across various settings, including different optimizers and datasets.
strength_weakness: strength_weakness: Please refer to the Questions section.
questions: questions: I will happily increase the score if the authors can address the following questions:

•	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 $\nabla F(x_t)$ and $\nabla F(x_{t-\tau})$. This is widely known in GD settings, but it may not be obvious in SGD (and DP-SGD) settings. Can the authors provide evidence with mini-batch gradients $\nabla f(x_{t})$? [1,2,3]

•	Using a low-frequency signal typically requires the use of FFT and iFFT to distinguish patterns in the frequency domain. While I understand that the authors try to investigate the auto-correlation and PSD of gradients (as shown in Figure 1), I cannot agree that this approach is orthogonal to conventional approaches depending on timestamps. As the authors mentioned momentum, this approach seems somewhat similar to the learning dynamics of DP-SGD, rather than the frequency domain. The authors should clarify this issue.

•	There are some existing papers that investigated the use of previous gradients in DP-SGD that are missing from the discussion. [1] investigated the use of previous gradients and their momentum approaches for sharpness-aware training. They explored the correlation between previous private gradients and the current gradient during optimization.

•	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?

•	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.

[1] Explicit loss asymptotics in the gradient descent training of neural networks, NeurIPS 21

[2] Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians, ICML 18

[3] Implicit Jacobian regularization weighted with impurity of probability output, ICML 23

[4] Differentially Private Sharpness-Aware Training, ICML 23
limitations: limitations: The authors clarify the limitations.
paper_summary: paper_summary: This paper augments DP-SGD with a low-pass filter-based postprocessing on the iterates of DP-SGD. This design is based on the intuition that the noise contributes more to the high frequencies, while the gradients (assuming sufficient smoothness of the objective) contribute more to the lower frequencies. 

The paper gives a theoretical convergence analysis, showing an improvement corresponding to a signal-to-noise ratio factor depending on the gradient auto-correlation. Importantly, precise knowledge of the gradient autocorrelation is not needed to run the algorithm, but it helps design better filters.

The paper also shows broad empirical improvements from the proposed techniques in the vision setting.
strength_weakness: strength_weakness: While I really like this paper, my opinion is that it is currently lacking in some aspects. Given below are some suggestions to improve the paper along these dimensions.

1. Error bars: DP is a noisy process, so it would be good to see error bars across multiple repetitions of the experiments. This is especially important since the gaps appear to be small. Further, it would be good to see the final accuracies for the vision experiments in a table as it is hard to judge how much the gap between the proposed method and baseline is.

1. Autocorrelation assumption: The general form of Assumption A4 is quite natural given the intuition developed in the preceding sections. However, it is not clear why $c_\tau$ is unconstrained while $c_{-\tau}$ is required to be non-negative. This looks like a trick for the proof to go through but further justification and empirical evidence (potentially in toy problems) are necessary.

1. Clarity: There is much scope for improvement to make the paper more reader-friendly (especially for those unfamiliar with signal processing). Examples:
    - A review section in the appendix recapping the basic ideas of the signal processing tools used (in the appendix)
    - Example coefficients used in typical low pass filters on page 5, and the kinds of weighted averages (the $\kappa_\tau$ coefficients) they would lead to. Also, a few figures to visualize the types of filters that work well with different types of auto-correlations could be helpful.
   - Theorem 2 could be restructured to make it easier to parse. A lot of quantities are used before their definitions.
   - The partial fraction decomposition of eq (7) is not guaranteed to be real. It would be worth clarifying that complex coefficients are allowed. Also, how are the $\kappa_\tau$ coefficients are real?
   - What constraints are necessary on the filter coefficients so that the $\kappa_\tau$ coefficients define a proper weighted average (i.e. non-negative and sum to one)? 

1. Parameter tuning: How are the filter coefficients tuned? It is only mentioned that the choices are ``empirical'' in Line 298. Ideally, for momentum SGD, we would tune the momentum and learning rate together; I would expect that tuning the filter coefficients and learning rate together would help.

1. Originality: the proposed approach is a straightforward application of classical ideas from signal processing to private optimization. While this can be viewed as a strength, I would have liked to see a more detailed investigation into the use of low-pass filters. For example:
    - An empirical investigation of the proposed adaptive filter.
    - A detailed empirical study on the choice of the filter coefficients. Only 3 different choices are explored (apart from DP-SGD and momentum), but it would be good to see the effect of changing filter coefficients for a first-order filter.
    - A plot of the performance vs. the order of the filter.
    - Some investigation on observed auto-correlation vs. choice of filter coefficients.

1. Minor comments and Potential typos: 
    - what is $t$ in lines 263 and 265?
    - Top of page 13, in equation (c): should $\kappa_\tau \| \nabla F(x_{t-\tau})\|^2$ be $\kappa_\tau^2$ instead?
    - Top of page 13, eq 10: Extra $+$ sign between $\frac{L\eta^2}{2}$ and what follows.
questions: questions: 1. It would be nice to have a more detailed comparison to correlated noise approaches for DP optimization e.g. [KMST+](https://arxiv.org/abs/2103.00039) or [DMRST](https://arxiv.org/abs/2202.08312). For instance, can those approaches be interpreted as some filtering of the noise? Also [CDPG+ (Fig. 1 right)](https://arxiv.org/abs/2310.06771) appear to use a high-pass filter on the noise for DP optimization. This seems to be similar in spirit to the proposed low-pass filter approach and a detailed comparison would be nice.

1. There is no batch size factor in the privacy-utility tradeoff of Theorem 3. How?

1. How does the low-pass filter work on the iterates of DP-SGD instead of the gradients? For instance, it is common to obtain a sequence $x_1, x_2, ...$ from SGD but use the average $\frac{x_1 + \cdots + x_t}{t}$ for inference. I wonder if a sophisticated average from the low-pass filter can help for inference alone (without using it for training).
limitations: limitations: Yes, but a more detailed empirical investigation would be good, as detailed above.
paper_summary: paper_summary: The paper looks at the sequence of DP-SGD noisy gradients through a signal processing perspective, and argues that the exact gradients are likely a low-frequency signal, while the noise has higher frequencies. As a result, the paper proposes filtering the high-frequencies with a low-pass filter to improve the signal-to-noise ratio. The filter is a post-processing of the noisy gradients, so there is not extra privacy cost. The paper then studies the convergence rate of DP-SGD with the filter under standard assumptions, and finds that the filter can improve the constants of the convergence rate if the hyperparameters of the filter are chosen well. The paper also contains experiments comparing several DP first-order optimiser with and without the filter on several datasets and models. The filtered variant consistently outperforms the unfiltered one.
strength_weakness: strength_weakness: 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.

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.

Minor points:
- Line 43: 250K steps for LLAMA training sounds like a typo.
- It would be good to mention that there are multiple ways to interpret "neighbourhood" (substitute or add/remove), and that the paper's results do not depend on the precise definition.
- As far as I know, the Gaussian mechanism bound in Definition 2 has only been proven for $\epsilon \leq 1$.
- It is not clear how Algorithm 3 should be read for DPAdam or LP-DPAdam. The update on line 17 uses $\mathbf{d}_t$, but the Adam lines only compute $\tilde{\mathbf{d}}_t$.
questions: questions: - 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?
- Why does the performance of LP-DPSGD drop with larger epsilons when fine-tuning on CIFAR-10 in Figure 10?
limitations: limitations: The paper clearly mentions the most important limitations of the work.

Comments: title: Response
Thanks for the response
Further response to Reviewer WMCW
Further response to Reviewer vvxz
Thanks for the response
Additional comment to Reviewer vvxz
comment: Thank you for the response and the additional details. I'm in favor of acceptance: I will maintain my score as I feel that it is a fair assessment of the paper. 

Some additional suggestions: Further justification of the autocorrelation assumption would be nice. Why is it always possible to choose $c_{-\tau}$ to be positive? I would have expected some sort of symmetry in $c_{\tau}$ and $c_{-\tau}$. Further details about this, and exploration for toy examples (e.g. simple quadratic functions or logistic regression for a slightly harder problem) would be quite helpful for a reader.
Dear reviewer,

We would like to thank you again and kindly remind you that the discussion period will end soon. We hope our response has addressed your concerns. Thank you very much for the time you spent reviewing our work and providing constructive feedback to us.
Thank you for your kind response and for increasing your score! We sincerely appreciate the time you spent reading our response. Please let us know if you have any further comments and suggestions, and we would be more than happy to include them in our revised manuscript.
I carefully read the rebuttal of the authors, including the general response and answers to my questions and those of the other reviewers. Although I thought some of the mathematical support was still limited, I understand the authors' novelty points and the experimental results of the proposed method. Personally, the authors effectively addressed the questions, including mine and those of the other reviewers.

 Thus, I have raised the score.
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 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:

| Auto-correlation | 0.0436| 0.0273| 0.0194| 0.0151| 0.0131| 0.0058| 0.0026| 0.0021| 0.0005| 0.0004|
| - | - | - | - | - | - | - | - | - | - | - |
| Filter coefficients $\kappa_\tau$ | 0.0909| 0.1652| 0.1352| 0.1106| 0.0905| 0.0740| 0.0606| 0.0495| 0.0405| 0.0331|

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 the detailed response! I have updated my score.


I would still like to see empirical evidence for the autocorrelation assumption, potentially in toy problems.
Right now, it looks too much like a trick for the math to go through without enough practical justification of the details.


Some investigation on observed auto-correlation vs. choice of filter coefficients for real data would also be valuable.
Thank you for the response. You have addressed most of my concerns. I especially appreciate the background to signal processing you have in the general response.

> 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.

Can you point you which of their results you mean? I looked through them quickly and did not find a result which has the same constants as your Definition 2. I'm assuming that by Mironov et al. (2019) you are referring to "Rényi Differential Privacy of the Sampled Gaussian Mechanism", since there is no Mironov et al. (2019) your bibliography.
> Detailed comparison to correlated noise approaches for DP optimization

We would like to provide a detailed discussion between our method and the correlated noise method  (KMST+, DMRST, and CDPG+) in this comment. As discussed in the above response, the update of correlated noise method can be written as $B(CG_{0:t}+W_{0:t}) = AG_{0:t}+BW_{0:t},$ where $B$ is a high-pass filter and our method is $AM(G_{0:t}+W_{0:t})$, where $M$ is a low-pass filter.

**Connection:** 

The correlated noise methods and our proposed method can all be viewed as processing the signal in the frequency domain to "separate" the noise and the gradient.

**Differences:** 

The existing correlated noise methods 1) pre-process the gradient/noise to separate the gradient and the DP noise in the frequency domain, and therefore require careful design of the matrices $B, C$ for each problem and optimizer, 2) require extra memory ($O(d\log(t))$ to $O(dt)$), which is unrealistic for large scale training, and 3) only work for SGD update, since Adam cannot be written as such a prefix sum of privatized gradient. 

In contrast, our method 1) post-processes the noisy signal to extract the gradient from the noise from the frequency domain, 2) only requires $O(d)$ extra memory, which is *independent* of $t$, and 3) is compatible with any first-order optimizer since it just post-processes the gradient.