DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction
Authors: Xinwei Zhang
Zhiqi Bu
Mingyi Hong
Meisam Razaviyayn
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
optimization
low-pass filter
signal processing
Primary area: privacy

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.

DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction
Xinwei Zhang University of Southern California
Zhiqi Bu
Mingyi Hong University of Minnesota
Amazon
Meisam Razaviyayn" University Southern California
Abstract
Privacy is 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 op- timizers, including DP stochastic gradient descent (DPSGD) and its variants, pri- vatize the training procedure by gradient clipping and DP noise injection. How- ever, 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 pre- training. In this paper, we provide novel signal processing perspective the design and analysis of DP optimizers. We show that "frequency domain" oper- ation called low-pass filtering can be used effectively reduce the impact DP noise. More specifically, by defining the "frequency domain" for both the gradient and differential privacy (DP) noise, we have developed DOPPLER. This component is designed for DP algorithms and works by effec- tively 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 by 3% - 10% in test accuracy on various models and datasets. Both theoretical and practical ev- idence suggest that the DOPPLER is effective in closing the gap between DP and non-DP training.
component, called
Introduction
A rapidly growing number of modern machine learning applications in computer vision, natural language processing, and their mixtures rely on the development large foundation models, whose performance heavily depends 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 al. 2020). To alleviate the possible privacy leakage in the model training procedure, Srivccy-peseerve
the huge amounts of data collected from individual users. The
optimization has attracted both researchers' and practitioners' interests.
Differential Privacy (DP) Dwork and Roth (014)) provides 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 AAbadi 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
xinweiz, aazaviya@uee edu, 'This work is not affiliated with Zhiqi Bu's position at Amazon.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

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 (Ahadi et al., 2016). Thus, the performance of large foundation models trained with DP optimizers degrades severely. To put it in perspective, pretraining foundation model for an image classification task on the CIFAR dataset from randomly initialized weights takes around 100 epochs, with 300 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 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. 202 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 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 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) op- timizers. 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 filter- ing 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.
We provide novel theoretical analysis for the proposed low-pass filtering approach. Specifically, by introducing certain frequency domain assumptions on the gradients, 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.
Theoretical Analysis:
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.
2
Preliminaries
In this section, we discuss notations, assumptions, and some related prior work on DP optimization:
2.1 Notations & assumptions
In this paper, we aim optimize the Empirical Risk Minimization (ERM) problem:
1 N
min F(x), where F(x) XER
(x)
(1)
Here, D= ( is the training dataset with N samples. Further denote the lower bound of the problem fr = inf f(x). Throughout the paper, use (+); to denote the update steps, A (u,

---

to denote the Gaussian distribution with mean jr and variance o². We also assume the problem satisfies the following assumptions.
(Smoothness) F()) is L-smooth, i..,, [VF(() VF S -|| yll, Vx,y E ER.
(Bounded Variance) The per-sample gradient has bounded variance, i.e.
BEED [v((x; F S dODD= 7x TR..
(Bounded Gradient) The per-sumple grudient has a bounded norm, i.e,
|V 5)ll S G, Vx E EED
Let us briefly comment on these assumptions: AT and A2 are standard in non-convex optimiza- tion (Allen-Zhu and Hazan 2016 Zaheer al. 2018 Abadi al. 2016); and A3 is commonly used in analyzing the convergence of DP algorithms (Abadi et 2016 Wang et al. 20200 [Andrww jet al. 2021) to avoid introducing the clipping bias. Since the impact clipping not the major focus of this paper, we follow the existing analyses and use A3 to simplify our theoretical analysis.
2.2 Differential privacy (DP) and differentially private SGD (DPSGD)
Differential privacy is gold standard of privacy to protect the privacy of individuals:
Definition ((e. DD Dwork and Roth 2014 A randomized mechanism . is said to be (e, 8) -iffferrrnntially private, if for any two neighboring datasets D, D' (D, differ only by one sam- ple) and for any measurable output set S, it holds that Pr(M(()) S] PP((M(() E S]
A popular practical differentially private approach to finding an (approximate) solution to the ERM optimization problem (T) 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) each iteration of the stochastic gradient descent method. The Gaussian mech- anism provides DP guarantee by injecting additive noise into the algorithm output.
Definition 2 (Gaussian Mechanism (Dwork and Roth 2014 Zhao et al. 2019)) Suppose an al- gorithm
Idd has b sensitivity A Le., maXp,p [[(D) A(D')l I A Then, for any c > 0 and 8 I 0.05, by adding random Gaussian noise to the ousput of the algorithm ((x) A(x) w, with w NN0 (bla), where opp Aay 2ln(122)) (c, D)...
AA, V2c'
the algorithm M
The DPSGD algorithm, presented in Algo- rithm 1 first samples a mini-batch B of size B and computes the per-sample gradient at each step t. Then, applies the Gaus- sian mechanism by clipping the per-sample gradient and injecting DP noise. The clip- ping operation bounds the sensitivity of the stochastic gradients to C, e.g., clip (V).C)
Algorithm DPSGD algorithm
Input: xo, D, C,C, ODP for t = O,...,
do Uniformly draw minibatch B, from D g: = = Exte,, clip (Vf(x;;;)) C) + w. where W. ~ NO, ob Ia)
X1+1 = =x 7/.t. end for
min {1, [ V or I V Finally, the
algorithm updates the model parameter with the privatized mini-batch gradient. It has been shown that DPSGD guarantees (c, 6D with sufficiently large injected noise (Abadi et al.) 2016).
Theorem (Privacy Guarantee (Abadi et al., 2016)) Given N. B,T and C, there exist positive T
(2Tlm())) Algorithm is
constants u, u, such that for any e < N 8 > 0, by choosing or 2 v No
guaranteed to be (e, DDP.
2.3 Related work
Effective DP training: Improving the performance DP training has been widely studied. Adap- tive 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 gra- dient becomes small; HHon et al. (2022) proposes using 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 parame- ters with adapters, low-rank weights, or quantized models has also been used to reduce the DP noise magnitude Yuu et al. 2022 Luo et al. [202]] Yu et al. (02I). De et al. (2022); Papernot et al. (202 )); Wang et al. (220)) 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.
3 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 frequency- domain analysis of the stochastic gradients. Specifically, in the frequency domain, we treat the (stochastic) gradients from t = 0 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 f: 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 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 Xt+1 = 7T.. with g, = F + We and w, being the Gaussian noise. We will come back the clipping
Section 3.2 In what fol- lows, we decompose the sequence of stochastic gradients {g:) } into two parts: 1) the gradient signal (VF(x:)) and the noise {g. Fxx)). We employ the power spectral density (PSD) to character- ize the distribution of power into frequency components of a continuous signal. Mathematically. the power spectral density (PSD) of a sequence (=,,....... is Pv(v) F(),(T)). where F denotes the Fourier transform from time domain (r) to frequency domain (V) (Oppenheim et al. 1996), and & is the auto-correlation coefficient as (T) = E (8t, 8t-7).
On the one hand, the gradient sequence (VF(x:)): where we apply the Cauchy Schwarz inequality to get
can be treated as a low-frequency signal,
(T) E(F((x), VF E [IVF(xx)]] || - FF(x |F
2 |F [V 12-1²= Σ g 1
This indicates that long as the stepsize n is small, the auto-correlation coefficients decrease as increases (as illustrated in Figure Ta blue line). Therefore, the PSD also decreases as v increases, i.c., (V (xx)) } is www-frequency signal (as illustrated in Figure lb blue line).

---

6,0%
00/
Pey
0.005
10-1
File
F50 Pl
10:4
150 mi
0.002
0,001
1m
10'
0.000
500
-200
11
250
300
-2
Time
Normaizal Frecusvcy
Norroloed fequnnyy
(a) Auto-correlation coefficients
(h) PSD coefficients
(c) PSD & ideal low-pass filter
Figure 1: An illustration of the auto-correlation (b(T) and power spectrum density P(v) of (VF(x')) and w' where Φvy decays proportional to 7² and w, 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,] = {g: VF(x;)) is white noise, where its auto- correlation is non-zero when r 0 and is zero otherwise (as illustrated in Figure la red line):
I do +
Sop B
T = 0
( = (We, We-r)
otherwise.
Therefore, Pw (v) do Fago yv (as illustrated in Figure lb red line).
3.1 Low-pass filter and noise reduction
From the above discussion, we observed that although the gradient and the DP noise are not separa- ble in each step (time-domain), they 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 high- frequency part. Figure scowwws an ideal low-pass filter that keeps the frequencies where the gradient larger (v/ [-0.6, 0.6]) and blocks the frequencies where the noise is larger (v < -0.6Vv > 0.6). Sgmal-to-Noiss Ratio (SNR) is a useful measure to characterize the quality of noisy signal, i.e., the privatized gradient {ge } in DP optimization. Given the PSD of the gradient and the noise, the Σ., Por(2)
SNR of the privatized gradient is E. PwrP) As illustrated in Figure ] when there is no low-pass filter (i.e., in Figure [b). the SNR is small as the noise dominates in the high-ffrequeny. In contrast, by applying the low-pass filter (i.e., in Figure [c). 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: } can be written as a recursive linear combination of the history signals:
m
0 m
T=U
where the sequence {m,} is the filtered output, {ar}, }. {b-} are the filter coefficients. Additinally, the "order" of the filter is defined as max (Na. n.). J. By carefully designing the coefficients, the low-pass (aax
filter can take different shapes and filter different frequencies.
In contrast low-pass filters, the existing approaches improving the performance of DP optimiza- tion 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 fil- ter 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.
3.2
The impact of per-sample gradient clipping
The above analysis assumes that the clipping operation inactive by choosing large enough clip- ping threshold C. In practice, the clipping operation is usually active. By assuming the clipped
5

---

gradient (x)(x) has zero curl, the DP optimizer optimizes an alternative problem:
min Fx(x), where Fc(x) [. Fcc(2x) xdz, VFc(x) = N XER-
Σ clip (V)(vE() (2) EED
Then the signal of the DP optimizer becomes the gradient of the alternative problem (VFc(x)))
and the noise becomes [w,] {g. Fxx(x))) As clipping is non-expansive operator, i.e., ||elip (x, C) - clip (y, C)Il - ||x yll, the alternative problem (.(.) is also T''smooth with < L. Therefore, similar argument could be made the gradient signal (x:)(x)) and the noise
{wr]) when the clipping threshold is small and the clipping operation is active.
The proposed DOPPLER approach
Building on the discussions in Section proposed universal approach to improve DP optimiza- tion performance: DP OPtimizer with Low-Pass fel for noisE Reduction (DOPPLER) Taking DPSGD 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 computes the filtered update direction m, as a recursive linear combination of the current gra- dient, past gradients, and past update directions. m, estimates the first moment of the privatized gradient and can be expanded as moving average of gt. i.c., = E K, Krgr-r. However, as [m, }. {g.} are initialized with zeros (Line 2), m, biased towards zero, especially in the early steps. To correct the initialization bias, in Line 7, the optimizer computes the bias correction factor Ca.t that used in Line 8 to guarantee the weights Ky the moving average are summed to
The DOPPLER approach a generalized version of the mo- mentum method from first-order filter higher orders. The momentum method uses one buffer m. to store the exponential moving average of gt, while DOPPLER multiple buffers {m, 1 to compute a more complex moving average of ge-
Connection to momentum method:
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 ZZaao ct al. 2024). serves as base component DP optimizers to improve their performance.
Theoretical analysis
5.1 Convergence analysis
In this section, we analyze the convergence of DPSGD with DOPPLER, First, we make the follow- ing assumption on the gradient auto-correlation coefficients.
A 4 (Gradient auto-correlation) For all t. {O,..., T 1}, there exists sequences {c+}; (c-r}
such that the following condition holds:
(VF(x)) VF(x 2 e 1 +c- IVF Vr 2 0,
(3)
20. O, VT 2r20 0.
(4)
Algorithm DPSGD with DOPPLER
1: Input: Xo; D, CDD (ar nu
(br -
2: Initialize: ) na = 0, fg = 0, (ca.- 10n 0, fcr - -
3: fo 0,........ T - do
4: Randomly draw minibatch B, from
5: g: शि. EeEB, clip (V (x](x;)), C) + Wt
# Compute private grudient
where We ~ [0 oh La)
6: m, - -ee a,m--r Σ Dyge-T
# Apply filter # Compute bias
7: Ch 1, Ca,t Die Cr + Di b-Ch.-7
8:
m. Ca,t
# Correct initialization bias # Parameter update
9:
X:41 X; mm
10: end for

---

Clearly, we have = > 0. From the discussion in Section can be satisfied as long as 17 is small enough, i.e.,
we see that the above assumption
V 2c_ [VF + (c7) ( [V
(V=2)
IV - VF(x,-n) )l + T + SaD /B)
The pattern of the sequence {cr} characterizes the frequency the gradients discussed in Sec- tion 3 If Cr is are all positive and slowly decreasing, then Vx(xx) and (x((xrr) are highly corre- lated, {V (x,)) lies in lower frequencies. However, c, necessarily positive. When some of C- s are negative, or c, 's are oscillating between positive and negative values, it means that V (F(x)) and V (x are negatively correlated, and (VF(x;)) may contain high-freyuency signals.
Before we present the theorem, let us define the normalized SNR as
T 1==
C2
SNR
(5)
1=
T==
and define the expanded coefficients Kiz as
minfmo.Ff
The
Ro
R4
Σ
brg
Σ
Za. (Pam
s.t.
Za,
(6)
Po x
1 1
D
0,
T2=0
T1=1
which satisfies me Er= complex, but K, are guaranteed to be real. With A44 we have the following convergence result for Algorithm 2
a-
Er=o 0-
Σ'
K- Note that Pa,r might be
Theorem (Convergence) Assume the problem satisfies A min 2ne }, and running Algorithm for iterations, the algorithm satisfies:
By choosing C 2 G. n S
P()) [F
F(xo) - F
T
(dopp
GGD
S1a 2SNR
B
where we define ST = 2i=0 2' Et Crty = O(T); the expectation is taken over t = O,..., T 1,
such that P(t) Σ==0 C.N-
Sr
The proof of Theorem 2 given in Appendix Compared with vanilla DPSGD (Abadi et al, 2016), by adopting DOPPLER the noise is scaled by factor of 2SNR Thus, long SNR > 2'
the noise is reduced. Next, will use the above result obtain privacy-utility tradeoff.
5.2 Privacy guarantee
Our low-pass filter is post-processioe on the privatized gradient. Since DP is immune post- processing Dwork and Roth (2014). Algorithm 2 provides the same DP guarantee as DPSGD, sat- isfying Theorem IJ By directly combining Theorem and Theorem 2 privacy-utility trade-off for Algorithm
we can obtain the following
Theorem (Privacy-utility trade-off) Assume the problem satisfies A7.44 By choosing C G,
ohp = 12211(1/ S min{ m and running Algorithm for T O
N (e())N((((x))F
N²2
CVLLLn(1//
iterations, the algorithm satisfies (e, 8)DD and the expected gradient satisfies:
EmP(()) |VF((x)) (CVaL(F(x))) FF))-FF1110)
VSNRNE
El and k, SNR are defined
where P(I)
6 respectively.
EE Ei C,R,
Theorem implies that DPSGD with DOPPLER O
shares the same convergence rate
Cdddmn11/) as the vanilla DPSGD Abadi et al. 2016). However, by using the low-pass
Nc
filter, the performance of DPSGD improves by a constant factor
SNR which is discussed next.

---

5.3 Impact of the low-pass filter
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 Ko = 1, and K = 0, VT 0. Then, the normalized SNR is SNR 2' This recovers the convergence result for DPSGD in Abadi et al. (2016).
Momentum-SGGi Cutkosky and Mchta (2020) is a special case of the low-pass filter, with filter coefficients: d1 0.9, bo = 0.1. and K, 0.1 0.97. Then, the normalized SNR is SNR 2 1.9 x 2 + E 0.9 (r) 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:
Na a
max (o- (.-)
SNR,
s.t.
b
1.
(8)
T=0
From (8). we observe that the pattern of the auto-correlation coefficients &, determines the choice of SNR is maximized. However, in general, finding the optimal filter coefficients by optimizing (8) before training is difficult, as {cr} is determined by the problem
the filter coefficients. When
and the DP optimizer's 's updates and can be time-varying.
Optimal FIR filter: When the filter takes the form of a finite impulse response (FIR) (i.e., On 0), can estimate {cr
and optimize b, 's according to (8) during training. To estimate Cr, we have:
(V)())) VF(xx-))) c.. [VF(xx)))) /[VFF(x))
(HI, (-))) c-r (1|g--||1 doip- 2sRv/ B)) / || doie 0
1 max (nax(llg:-// gt- - doir 0} / max ||g: do h.h
E gg g:-r)
2
where the last approximation we set c_, = and assume do dominates / B; the max taken 11-11 2 and choose E = 10 as small positive number for numerical stability. After obtaining e.s. 6y.s have a closed-form solution b, = Σ 6, This estimation only relies on
the stored privatized gradients - so it does not spend an extra privacy budget or memory. Therefore, it can also be implemented along with DOPPLER, filter coefficients for an optimal performance.
adaptive approach to adjust the
6 Numerical experiments
In this section, we investigate how the low-pass filter affects the performance of various DP op- timizers 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 atttps://anonynonn 4oper science/r/Loo-- pass SGD-C7A1
6.1 Experiment Settings
Dataset: We conduct experiments on computer vision datasets (MNIST, CIFAR-10, and CIFAR- 100 (Krizhevsky et al. 2009h) and natural language processing datasets, GLUE (Wang al. 2018
Model: We conduct experiments on various models, including the 5-layer CNN described in De
ct al. (2022). the modified ResNet in Kolesnikov et al. (2019), EfficientNet with group normaliza- tion Tan and Le 2019), and ViT (Dosovitskiy et al. (002)) for the CV tasks and RoBERTa-baa (Liu et al. 2019) for the GLUE dataset. If not specified, the models initialized with random weights without pretraining.
We compared the impact of DOPPLER several base algorithms, including the DP version of SGD, Adam, and GaLore. The updates the algorithms are given Algorithm 2 and Algorithm Bnn in Appendix C.2
Algorithm:
We use LP- to denote the DP optimizer with DOPPLER.

---

101
10-11
PSD Ro)
Peyle)
10-1
10
10
10-1
SGD
10-5
LP-SGD
-2 Normalized frecuency
Aoomollzed froquency
(a) PSD of w. and gi.
(b) PSD of g. of SGD and LP-SGD.
Figure 2: The recorded PSD of Gaussian noise (we)- and the stochastic gradients of SGD and LP- SGD of ResNet-50 training on CIFAR-IC 10 dataset.
Test Accurcc
Test Accuney
50
330
30
DPSGD
DPSGD
LP-DPSGD
LP-DPSGD
P. P-DPSGD
0
10
30
60
120
150
20
30
40
50
Epoch
Epach
Epoch
CIFAR-10 with 8.
(b) CIFAR-100 with = 8.
(c) MNIST with
Figure 3: Comparision between DPSGD and LP-DPSGID for pre-training on different datasets.
Test Accurazy
Tost Mesrrn
35
DPGiseeee
EiNia enc nola
DPAdam L.PDDPdda
LE DDGGLoos 48
LP P-DPSGD
Lislere P-PIPss 1-190
Epsilon
(a) DPSGD and DPSGD.
(b) DPAdam and LP-DPAdam.
(c) DPGalore and LP-DPGalore.
Figure 4: Comparision between DP optimizers and w/o low-pass filters for pre-training with different e's on CIFAR-10 10 dataset.
Hyper-parameters choices:
The choices of the filter coefficients a;, by are empirical; specific choices used in the experiments are listed in Table Appendix [..]
The learning rate, batch size, and number of training epochs are tuned for best testing accuracy using grid search. Detailed typer-parameten and search grids are given in Appendix C.I For all experiments, we fix the privacy parameter 8 1/N1.1 to obtain a reasonable privacy notion.
6.2 Numerical results
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) the CIFAR-10 dataset. Then, we compute the PSD of the recorded stochastic gradients. The results are given in Figure / We observe that the recorded PSD of w, is filling all frequencies, and g: is low-frequency signal. After applying the low-pass filter, the PSD of the filtered gradient lies in the low-frequency domain, and the high-frequente
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, 10, and CIFAR- 100 datasets under the same privacy budget e = 8. The results on the GLUE
dataset is in Appendix C33
Results for different algorithms: The comparisons between DP optimizens, including DPSGD, DPAdamBC (Tang et al.) 2024), and DPGalore (an extension of Gal Lore (Zhao et al. 2024 with and without DOPPLERS shown in Figure We can observe that all DP optimizers with DOPPLE ROPPLERRoutperfom the baseline under different levels of privacy budget e's.

---

7 Conclusion and discussion
In this paper, we introduce a signal processing perspective understand and analyze DP optimizers. By identifying the difference between the gradient and noise signal in the frequency domain, we propose DOPPLER, low-pass filter approach, to filter out the DP noise and improve the signal- to-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.
Designing higher-order filters requires hyper-parametee tuning prior knowledge of the gradients' -uto-correlation patter;; implementing a high-order low-pass filter is memory ineffi- cient (requires storing + ny optimization states for each trainable parameter), which eliminates the usage of the proposed method when optimizing very aare--scale foundation models with limited memory resource.
Limitations:
Acknowledgements
This work supported by gift from the USC-Meta Center for Research and Education in AI, and gift from Google. Mingyi Hong is supported partially by NSF under the grants EPCN-2311007 and CCF-1910385.
References
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learn- ing with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308 018-318,77 2016.
Z. Allen-Zhu and E. Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707. PMLR, 2016.
W. An, H. Wang, Q Sun, Xu, Q Dai, and L. Zhang. A pid controller approach for stochastic optimization of deep networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8522-8553 2018.
G. Andrew, O. Thakkar, B. McMahan, and S. Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455-17466, 2021.
Z. Bu, Y.-X. Wang. S. Zha, and G. Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. Advances in Neural Information Processing Systems, 36, 2024.
N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert-Voss. K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 2/), pages 2633-2650, 2021.
C. A. Choquette- Chhoo, K. D. Dvijotham, K. Pillutla, A. Ganesh, T. Steinke, and A. G. Thakurta. Correlated noise provably beats independent noise for differentially private learning. In The Twelfth International Conference on Learning Representations.
A. Cutkosky and H. Mehta. Momentum improves normalized sgd. In International conference on machine learning, pages 2260-2268. PMLR, 2020.
S. De, L. Berrada, J. Hayes, S. L. Smith, and B. Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 136500 2022.
Denisov, H. B. McMahan, J. Rush, A. Smith, and A. Guha Thakurta. Improved diffcrential privacy for sgd via optimal private linear operators on adaptive streams. Advances in Neural Information Processing Systems, 35:59 10-5924, 2022.
Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional trans- formers for language understanding. In Proceedings of the 2019 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I ( (Long and Short Papers), pages 4171-4186, 2019.
10

---

A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghami, M. Minderer, G. Heigold, S. Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Theoretical Computer Science, 9(3-4):211 1-407, 2014.
O. Gannot, frequency-domain analysis of inexact gradient methods. Mathematical Programming, 194(1))955-1016, 2022.
J. Hong, Z. Wang, and J. Zhou. Dynamic privacy budget allocation improves data efficiency of differentially private gradient descent. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1 11-3,, 2022.
B. Hu and L. Lessard. Control interpretations for first-order optimization methods. In 2017 Ameri- can Control Conference (ACC), pages 3114-3119. IEEE, 2017.
Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213-5225. PMLR, 2021.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
A. Kolesnikov, L. Beyer, X. Zhai, J. Puigcerver, J. Yung. S. Gelly, and N. Houlsby. Big transfer (bit): General visual representation learning. In European Conference Computer Vision, 2019.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
X. Li, F. Tramer, P. Liang, and TT. Hashimoto. Large language models be strong differentially private learners. In International Conference on Learning Representations, 2021.
Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoy- anov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 11692, 2019.
I. Loshchilov and F. Hutter. SGDR: stochastic gradient descent with warm restarts. In 5th In-
ternational Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL httpss//opeereviiet net/foorumiddS$$$$ccxz
Z. Luo, D. J. Wu, E. Adeli, and L. Fei-Fei. Scalable differential privacy with sparse network finetun- ing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5059-5068, 2021.
A. V. Oppenheim, A. S. Willssy, and S. H. Nawab. Signals & systems (2nd ed.). Prentice-Hall, Inc., USA, 1996. ISBN 0138147574.
X. Pan, M. Zhang. S. Ji, and M. Yang. Privacy risks of general-purpost language models. In 2020 IEEE Symposium Security and Privacy (SP), pages 1314-1331. IEEE, 2020.
N. Papernot, A. Thakurta, S. Song, S. Chien, and Ó. Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 9312-93211 93211 2021.
O, Russakovsky, Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 115:211 152,, 2015.
M. Tan and Q Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference machine learning, pages 6105-6114, PMLR, 2019.
Q. Tang, F. Shpilevskiy, and M. Lécuyer. Dp-adambe: Your dp-adam is actually dp-sgd (unless you apply bias correction). In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15276-15283, 2024.
11

---

H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 353-355, 2018.
B. Wang, Q. Gu, M. Boedihardjo, L. Wang, F. Barekat, and S. J. Osher. Dp-Issgd: A stochastic optimization method lift the utility in privacy-preserving erm. In Mathematical and Scientific Machine Learning, pages 328-351. PMLR, 2020.
S. Winder. Analog and digital filter design. Elsevier, 2002.
X. Yang, H. Zhang, W. Chen, and T.-Y. Liu. Normalizeddclipped sgd with perturbation for differen- tially private non-convex optimization. arXiv preprint arXiv:2206. /3033, 2022.
D. Yu, S. Naik, A. Backurs, S. Gopi, H. A. Inan, G. Kamath, J. Kulkarni, Y. T. Lee, A. Manoel, L. Wutschitz, et al. Differentially private fine-tuning of language models. In International Con- ference on Learning Representations, 2021.
M. Zaheer, S. Reddi, D. Sachan, S. Kale, and S. Kumar. Adaptive methods for nonconvex optimiza- tion. Advances in neural information processing systems, 31, 2018.
Zhao, T. Wang, T. Bai, K.-Y. Lam, Z. Xu, S. Shi, Ren, X. Yang, Y. Liu, and H. Yu. Reviewing and improving the gaussian mechanism for differential privacy. arXiv preprint arXiv: 2019.
Zhao, Z. Zhang, B. Chen, Z. Wang, A. Anandkumar, and Y. Tian. Galore: Memory-efficieet IIm training by gradient low-rank projection. In 5th Workshop practical ML for limited/low resource settings, 2024.
12

---

A Additional Background
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, discuss the filter method in signal processing.
A.1 Frequency domain analysis
In signal processing, frequency domain analysis is used to analyze the periodical or long-term be- havior of a (time series) signal/data. In the frequency domain analysis, we use the frequency as the indices of the signal, e.g.. {X(w), (v) E C. where each term (v) records the amplitude and phase of the sine
of frequency that composes the signal; in contrast, in the time domain, use time t as the indices of signal, c.g., { where each term Tt records the value of the signal at given time t. In this paper, we treat each coordinate i [l..... d] of the privatized gradient over the iterates as an individual signal, i.e. {or (2 ..---r [i]] Thus, the gradient over iterates gives d one-dimensional signals, and we can look their frequency domain representation of each signal.
Benefit of frequency-domain analysis:
Certain properties of a signal can be hard to observe/characterizz in the time domain. For example, a long-time correlation or cyclic behavior of the signal 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 2₁ sin(t) has nonzero entries in almost all times. However, the frequency domain representation of this signal has only one entry that is non- zero, i.c., X
and all other entries are zero, i.c., ((v) 0, Vv + 1. This means x, has only one periodic signal in it.
Certain mathematical analyses be significantly simplified in the frequency domain. For ample, linear differential equations the time domain are converted to algebraic equations in the frequency domain; filters as convolutions in the time domain are converted to point-wise multipli- cation in the frequency domain. These properties greatly simplify the analysis the dynamics of the signals and filters (Oppenheim al. 1996).
Transform from time to frequency domain: To obtain a frequency domain representation of discrete signal, one can apply the Discrete Fourier transform (DFT) (F(x,) : X(v) Ei x(t)e= =pp"""))))) to the signal. By directly applying DFT to signal and obtaining (X(),, one can identify how the signal is composed of waves of different frequencies with their am-
plitudes and phases. In the paper, we apply DFT to the auto- nuto-coorelltion of signal and obtain its power spectrum density (PSD). The PSD of signal shows the distribution of the power of signal on different frequencies. For example, the PSD of (t) sin(t) is Pvv) = 1/2 for // = + and 0 elsewhere.
A.2 Low-pass filter
Frequency filter: A frequency filter is transformation of signal that only allows certain frequencies to pass and blocks/attenuates the remaining frequencies. For exam- ple, for a signal z(t) sin(t), + sin(10t), we can apply an (ideal) low-pass fil- ter F(v) = 1 when |p| < 2 and 0 otherwise. Then, after applying the fil- ter, F x(t)
sin(t). the output signal only keeps the low-frequency signal.
DP Noise x
In this work, DP noise reduction. linear filter attenuates certain frequencies by using linear combination of the input signal. Considering as the time signal, the general form of linear filter on gi is
(time-invariant linear filters for
Clipped Gradients
Low-Pass Filter
nu
m
Kr St
ar Mp
+
b
Figure 5: Illustration the low-pass filter.
r=0
13

---

where K, are the filter coefficients. The second formula is recursive way of writing the filter.
Filter design: The property of the filter depends on the choice of the filter coefficients. Designing filter consists of the following steps:
Decide filter order/tab Tay 7i6- Larger Tha Pb give the filter more flexibility and better possible performance, at a cost of more memory consumption. In our experiment, we tested on Oth-3rd order filters, i.e., max m mb} S 3.
Decide filter coefficients {az}, {. Filter design can, in general, be a complex procedure, and it involves deciding on trade-off' among different properties of the filter (Winder) 2002). Two standard constraints on the filter coefficients are: a) - Σ 0, + Σ b- = 1, to ensure the filter has unit gain, i.e., the mean of the signal remains unchanged; and b) the solutions to 1 + aa," = satisfies |r| < 1, to ensure the filter is stable, i... > |siel < oo. 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.3 Additional related work
DP optimization with correlated noise: DP optimization with correlated noise have been investi- gated in Kairouz et al. (202I): Denisov et al. (2022); Choquette- Choo et al.) These works treat the DPSGD update releasing a weighted prefix with DP noise, i.e., A(GGo + Wo.)), where A is the prefix sum matrix (a triannlr all-one matrix) and Wo. is the i.i.d. DP noise. Kairouz et al. 2021); Denisov al. (2022) apply certain decomposition A = BC and change the update to B(CGu:t + Wo:t) AGo:: + BWox.. and Choquette- Choo et al. provides a theoretical justification that when B is a high-pass filter, and 9i correlated, the algorithm outperforms original DPSGD. In contrast, our method can be written as AM + Woz), 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-procest 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 (Od))og()) to (dt)), which is unrealistic for large scale training, and 3) only work for SGD update, since Adam cannot be written as such 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 (dd extra memory, which independent of t, and 3) is compatible with any first-order optimizer since it just post-processes the gradient.
B Missing proof details in the main paper
In this section, we provide the proof for Theorem First, by AT
we have
L
F(x++1) - F(x,)= S FV)())) x x,)
E
1
-x,1
2
In²
(VF(FF(())) (x). m,) +
|m
2
We can expand m, as follows:
my b,gr-r
m
a m
nu
m;
+
a M
by g-gi-
1=1
+=U
(1
a MM2)
b G(()
1=1
7=0
nl
M(=)
b G(()
1 1+
0, 2-
0=0
14

---

20.7
((2)
6 G((2)
Pa,
7=0
(d)
M(2)
Z0,71
(Pa,71
br
G
1=
Ta=
72 0
M(2)
b
20.71
(Pom
10
G(z)
12=0
T==0
bT2
2a,71 Pe.,:.a,T:B1---11 81-
0
Ki gi B1-T1
where in (a) we applies the z-transform 2 to both side of the sequence and use the property that { = z (=) (Oppenheim et al. 1996;; (b) divides both sides by 1 + Σr= a,2 ii (d) expands T-p = 1+ ai
in (c) we define { J. {Pa.r} such that Σ+= 1-pa,r=
P'; in (e) we rearrange there terms; in (f) we apply the inverse z-transform and notice that g<o 0; and in the last equation we define K,, - Dmin(ms. (na.7) bra Dm==1 Za,r ) )===a, Plug the expansion of m, back to (9), we have
Lui
B[F(x++1) F(xx)) -1 VF(x)), E
Kygt-11
+
E
R gi
2
Lnj²
Krr (VF(x)), vF(x.-)))
Σ
Kr
2
r=0
r=0
Ky (x)())), VF(x.-))
7/
==0
2
Ln²
+ 2
Σ F
Σ
2 do +
B
1=0
T=0
Cr |F(x))]1
Σ
C-r |F((x-1) )1
17
T=0
T=0
+
Ln
Σ K4 [[F(x--))] )1
2
do + SGD
B
r=0
7=0
(1)
Ln
-50D
11
C |F
Rir
do +
(10)
where in (a) we apply A3 and set C > G, so that Efg:] Vx(x); (b) applies A2 to the last term, and use the fact that w, (N Ia), and the noise are independent; (c) applies A to
the first term and uses Jensen's 's incquality to the second term with 11-112 being convex; in (d) we set y S min, ( [===) }. Clearly, we have Ei= Kr I- deciding both side by y, then the theorem is proved.
D b
Averaging over O,... 1, and
C Missing experiment details in the main paper
In this section, we provide the missing details for the experiments in the main paper and additional experiments.
15

---

Momeebum SGD
088
fist-order ver
-31
second crder
0.0
Momestum S6D
0.2
ver
Sccond ondor
Frequency [Hg]
(a) Time response Ry of Tab.
(b) Frequency response of Tab.
0.5
Arpiitze (68)
-20
600
15
10
10
30
Frequacy [+]
(c) Time response of Tab.
(d) Frequency response of Tab.
Figure 6: The time and frequency response of the filters used in the paper.
Experiments compute resources: Each experiment is conducted on an EPYC-7513 CPU with one NVIDIA A100 (80 GB) GPU. The runtime ranges from hour 48 hours. The codes for the optimizers and the job scripts are given in the supplementary.
C.1 Hyper-parameter choice
In this section, we provide the hyper- parameter choices and search grids for different experiment settings. The search grids for the experiments are given Table
Table 1: Search grids for each hyper-parameter.
Hyper-parameter
Search grid
Epoch
{50, (0,,80, 120, 150] {500, 1000, 2000, 5000] {1024, 2048, 4096)
CIFARIO/CIFAR batch size
GLUE batch size
SGD stepsize
{0.8, 0.5, 0.4, 0.2, 0.1
Adam/Gal stepsize
{3e 3, 1e
3, 3e
4, le 4, 3e
5)
The filter coefficients used in the experiments are given in Table
Table 2: Possible choice of the coefficients for the filter of different orders.
Filter
br
a,
SGD
N/A
Momentum-SGHi
0.1
-0.9
sr-order ver.1
[1,11/11
-9/11
st-order ver.2
[3,
(3,11/111
-9/11
gad-order
[1,2,1)/58
(-92,38)/58
C.2 Algorithm variants
We provide the update rules for different DP optimizer variants used in main paper Algo- rithm 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 al. 2024) optimizer.
16

---

Algorithm DP-GeLore with DOPPLER
Input: Xo, D,1,, C, ODP. {a, =m {or r 3, EAdam- 1
2: Initialize: (m= th = 0, (g-r)-=1 = 0, -6=-- {cb, (cb.-TT= V-1 =0
3: for I. 1= ......, 7 - do
4: Randomly draw minibatch B, from
5: g: [B, CeEB, clip {x; C) + Wt where w; ~ (0, op Ia)
Compute private gradient
6:
if Use Galore then
7:
if mod 7 = then
8:
P FindProoector((g..)))
9:
end if
g: R-PT.g: g:
# Low-dimension projection
11:
else
gi = gr
13:
end if
V: (1
3(g:)
Compute And-order moment # Apply filter # Compute bias
15:
m, = -Et= d-114-- + E+= b-81-
16:
Cb = Ca,t = - - C- + 2rmo b,
M. mr Co,t
# Correct initialization bias
18:
V v1/(1- 39
# Correct initialization bias
19:
d, m. max ( (vV, (Adam)
if Use GaLore then
21:
d, Pd,
# Inverse projection to original dimension
22:
else
23:
d, d:
24:
end if
25:
Xt+1 X2 nd
# Parameter update
26:
end for
C.3
Additional experiments: the GLUE dataset
We also conduct experiments on the GLUE dataset (Wang et al. 2018). We fine-tune a RoBERTa- base model (Liu al.] 2019) with the pretrained weights from https: htt.//hugggggggge co/
FacebookAT/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
al. (202I). From the result of DPAdamBC and LP-DPAdamBC, we observe slight accuracy improvement by using DOPPLER. However, in the fine-tuning tasks, do see significant improvement by using DOPPLER compared with the result reported in Li et al. (2021).
Table 3: Test accuracy language tasks with RoBERTa-base, {3, 8).
3
Method
MNLI
QQP
QNLI
SST-2
MNLI
QQP
QNLI
SST-2
DPAdam (Li et al. 2021
82.45
85.56
87.42
91.86
83.20
86.08
87.94
92,09
DPAdamBC
82.39
85.29
86.44
91.10
82.48
85.94
87.06
91.25
L.P-DPAdaMBC
83.55
85.71
87.63
91.71
83.80
86.50
87.76
91.82
C.4 Additional experiments: ablation studies
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 We observe that DOPPLERumifomly improves the DP pretraining performance for different model structures in pre-training.
A Abltion study on filter coefficients. The results for DPSGD accompanied with different low-pass filter coefficients in Table are given in Figure Sa We observe that different filters have different impacts on the algorithm's 's performance. For training on the CIFAR-10 dataset, the first-order filter is sufficient to have good performance, while different coefficient choices for filters of the same
17

---

65
60
Test Accuracy
Test Accuracy
-00
55
40
DPAdam LPDDPAdam
30
DPSGD LL--DPSG
45
20
20
40
60
80
30
60 Epoch
90
120
Epochs
(a) 5-layer CNN
(b) Vit-small
35
Test Accuraty
-40
Text Accuracy
30
25
30
20
20
DPSGD LP-DPSGD
15
DPSGD
LP-DPSGD
10
10
0
40
80
120
40
80
120
Epoch
Epoch
EfficientNet
ResNet-50
Figure 7: Comparision between DPSGD LP-DPSGD for pre-training different models on CIFAR-10 dataset with
order also have different performances. The second-order filter provides an over-smoothing to the gradient, leading to slow convergence in the early stage of training. Although the second-order filter does not have good performance, could have better performance when the number of training steps is longer (e.g., when training on the Imagenet dataset (Russakovsky et al. 2013)). 55
45
55
Test Accuracy
Accurcy
445
35
335
Order 0
25
Order I ver.
Order 1 ver.2
225
Order 2
17
15
30
60
150
20
40
60
80
Epoch
Epoch
(a) Filters in Tab.
(b) Filters Tab.
Figure 8: LP-DPSGD for pre-training CIFAR-10 with different filter coefficients.
An additional set of first- and second-order filters with different coefficients in Table 4 Coefficient choices fl and f2 compare different values of by; f3 and f4 compare the impact of the values of a,; f5 and 16 compare the impact of filter orders n,, and n..
Table Possible choice of the coefficients for the filter of different orders.
Filter
b-
fl
(0.075, 0.025]
00.9
f2
1.025,0.0755
-0.9
f3
(0.1, 0.1)
0.8
f4
{0.2, 0.2)
00.6
f5
(0.025, 0.05, 0.025)
0.9
f6
(0.025,
1.8, 0.85)
Impact of different clipping operations. The results for LP-DPSGD with different clipping meth-
ods are given in Figure We observe automatic clipping (Bu et al. 2024 (Norm) is better than
18

---

vanilla clipping described in (Abadi et al. 2016) (Clip); treating all layers as one vector (Flat) is better than clipping each layer separately (Layer).
Accuracy
35
Flat Clip
Leyer Clip
Flat Norm
Layer Norm
25
50
75
100
Epoch
Figure 9: DPLPSGD for pre-training on CIFAR-10 with different clipping strategies.
Impact of learning rate and scheduler: We report part of our hyper- parameter search pro- cess. First, we report the test accuracy for different learning rates with fixed epochs (150) and (8, (5,1/50000"-1--DD The results shown in Figure 10 The optimal learning rate is 10 10-3; 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 a learning rate scheduler. Specifically, we use the Cosine-Annealing with warmup from Loshchilov and Hutter (2017). From the result, scheduler improves the training performance, while in the early stage, the scheduler slows down the convergence.
compare the optimizer with and without
when the number of epochs is large, the learning rate
55
Test Accuracy
40
0.005
0.003
1-00001
1=-0.0033
0.0001
150
Epoch
Figure 10: LP-DPAdamBC for pre-training on CIFAR- 10 with different learning rates.
55
50
Teat Accuracy
45
40
35
30
w scheduler
25
w/b Ir scheduler
20
30
60
90
120
150
Epoch
Figure 11: LP-DPSGD with and without learning rate scheduler
Finetuning on CIFAR dataset: We also provide the experiment result for fine-tuning ViT models on the CIFAR-10 10 dataset under different privacy budgets. As illustrated Figure [1] the perfor- mance of LP-DPSGD improves by less than 1% for small c's. For larger é's, the gap is smaller. DOPPLER works has more improvement when the injected DP noise large (i.e., 6 small).
19

---

96.5
Test Accuracy
96
95.5
95
DPSGD
LP D-DSS
94.5
0.2
0.4
0.6
0.8
Epsilon
Figure 12: DPSGD and LP-DPSGD for fine-tuning VIT on CIFAR-10 with different e's.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claim matches with the results in the main paper
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Yes, we provide a discussion at the end the paper. And the limitation of the assumptions are discussed right after the the definitions.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
21

---

We provide assumption in the statement of the theorems and proofs in the appendix.
Justification:
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 cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
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 conclu- sions 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 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 make their results reproducible 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, other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors 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 have some path reproducing verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Yes, we included the code for the experiment the supplementary
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. ctaips.cc//ublic//guu Sttpii///guuieee/eeeeuttttttt Cau///edeeSbiiiiic ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The parameters are either provided the citations or given the appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: We did not report the error bar, partially due to the unknown distribution of the error. In addition, most our experimental results were done with one run due to the large size nature of them.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
23

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
The training details are included in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Stthics/httss//nneeeeee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 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 spe- cific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility MI).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [Yes]
Justification:
The code provided contains the license information.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, wwwppppwppiiaaeee thoode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of 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.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
The code of the algorithm is well-documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "7bWqH1Sosn", "reviewer": "Reviewer_kR6J", "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.", "questions": "Section 3:\n- 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.\n- 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?\n- Line 168-169: How do you compute PSD? How do you go from the first equation in Section 3 to drawing Figure 1b, 1c? \n- Line 187-188: Why can a linear low pass filter be written as in the first equation of section 3.1? \n\nSection 6:\n- What are the sizes of the models used?\n- Why do you not compare with SOTA methods, e.g., De et al. 2022 or Shejwalkar et al. 2022? \n\nShejwalkar et al., Recycling Scraps: Improving Private Learning by Leveraging Intermediate Checkpoints, arXiv 2022", "limitations": "- Proposed method, although motivated from enabling DP for large models, cannot be used for large models due to computation inefficiency.\n- Current set of results lacks depth and should be improved. \n- Paper writing/clarity can be improved (see questions/weaknesses).\n  - Equations are not properly numbered.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Interesting signal processing perspective for DP optimization problem and observation about gradients and noise in frequency domain\n- DOPPLER is a post-processing method, hence can be used with SOTA DP methods\n- Experimental results show that in training-from-scratch settings DOPPLER is useful", "weaknesses": "- Connection between time/frequency domains is difficult to understand; adding some background might be useful \n- Motivation of the paper is to enable DP training for large, foundation models, but experiments are performed on relatively small models\n- DOPPLER can be combined with any SOTA DP training, but results with such SOTA methods are missing", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n$\\quad$\n> 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.\n\nGreat 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.\n\n> 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?\n\nLet 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.\n\n> Line 168-169: How do you compute PSD? How do you go from the first equation in Section 3 to drawing Figure 1b, 1c?\n\nAs 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.\n\n> Line 187-188: Why can a linear low pass filter be written as in the first equation of section 3.1?\n\nA 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.\n\n> What are the sizes of the models used?\n\nIn 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.\n\n> Why do you not compare with SOTA methods, e.g., De et al. 2022 or Shejwalkar et al. 2022?\n\nWe 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.\nHowever, 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. \n\n> Proposed method, although motivated from enabling DP for large models, cannot be used for large models due to computation inefficiency.\n\nWe 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. \nHowever, 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.\n\n> Current set of results lacks depth and should be improved.\n\nWe 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.\n\n> Paper writing/clarity can be improved (see questions/weaknesses). Equations are not properly numbered.\n\nWe 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.\n\n$\\quad$\n\nThank 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zmdm9rlG3a", "reviewer": "Reviewer_ahhw", "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.", "questions": "I will happily increase the score if the authors can address the following questions:\n\n•\tThe 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]\n\n•\tUsing 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.\n\n•\tThere 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.\n\n•\tFor 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?\n\n•\tThe 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.\n\n[1] Explicit loss asymptotics in the gradient descent training of neural networks, NeurIPS 21\n\n[2] Measurements of Three-Level Hierarchical Structure in the Outliers in the Spectrum of Deepnet Hessians, ICML 18\n\n[3] Implicit Jacobian regularization weighted with impurity of probability output, ICML 23\n\n[4] Differentially Private Sharpness-Aware Training, ICML 23", "limitations": "The authors clarify the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "•\tThe paper presents a very simple and effective theory based on the optimization of DP-SGD and the similarities between gradients $\\nabla F(x_t)$.\n\n•\tThe authors investigate the optimization dynamics in terms of the frequency domain rather than the time domain.\n\n•\tThe paper conducts experiments on various datasets and existing well-known optimizers, demonstrating the effectiveness of the frequency-aware optimization.\n\n•\tThe authors establish an interesting relationship between SNR and frequency domain approaches.", "weaknesses": "Please refer to the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> 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 ...\n\nLet us review our main assumptions:\nAssumptions 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.\nAs 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.\n\n> Using a low-frequency signal ... I cannot agree that this approach is orthogonal to conventional approaches depending on timestamps...\n\nWe 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. \nInstead, 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.\n\n> There are some existing papers that investigated the use of previous gradients in DP-SGD that are missing from the discussion...\n\nThank 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. \n\n\n> 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?\n\nThank you for this nice and critical comment. We would like to clarify how the filters are designed:\n 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. \n 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.\n 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.\n\n> 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.\n\nThank 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.\nMoreover, 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.\n\n$\\quad$\n\nFinally, 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gsOCAQfc1F", "reviewer": "Reviewer_vvxz", "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. \n\nThe 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.\n\nThe paper also shows broad empirical improvements from the proposed techniques in the vision setting.", "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.\n\n1. There is no batch size factor in the privacy-utility tradeoff of Theorem 3. How?\n\n1. 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": "Yes, but a more detailed empirical investigation would be good, as detailed above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A strength of the proposed method is its simplicity: it gives a simple add-on to the iterates of DP-SGD. It includes momentum as a special case but allows for more sophisticated running averages of the gradients.\n- The paper is well-written: the main idea comes across easily (although clarity can be improved; suggestions to follow).\n- The theoretical analysis looks sound.\n- I think the presented results are significant: The experiments demonstrate a clear win from the proposed approach. They also nicely corroborate the intuition behind the auto-correlation of the gradients vs. noise.\n- The first-order filters that work quite well empirically only need a modest additional storage cost (two extra buffers) over DP-SGD.", "weaknesses": "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.\n\n1. 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.\n\n1. 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.\n\n1. Clarity: There is much scope for improvement to make the paper more reader-friendly (especially for those unfamiliar with signal processing). Examples:\n    - A review section in the appendix recapping the basic ideas of the signal processing tools used (in the appendix)\n    - 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.\n   - Theorem 2 could be restructured to make it easier to parse. A lot of quantities are used before their definitions.\n   - 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?\n   - 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)? \n\n1. 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.\n\n1. 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:\n    - An empirical investigation of the proposed adaptive filter.\n    - 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.\n    - A plot of the performance vs. the order of the filter.\n    - Some investigation on observed auto-correlation vs. choice of filter coefficients.\n\n1. Minor comments and Potential typos: \n    - what is $t$ in lines 263 and 265?\n    - Top of page 13, in equation (c): should $\\kappa_\\tau \\| \\nabla F(x_{t-\\tau})\\|^2$ be $\\kappa_\\tau^2$ instead?\n    - Top of page 13, eq 10: Extra $+$ sign between $\\frac{L\\eta^2}{2}$ and what follows.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n> Error bars\n\nThe 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. \n\n> Autocorrelation assumption\n\nGreat 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.\n\n> Clarity\n\nThank you for providing such detailed constructive feedback. We will address these points as discussed next:\n\n> * A review section in the appendix\n\nWe will do it as described in our general response to the reviewers.\n\n> * Example coefficients for low-pass filters\n\nWe 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.\n\n> * Restructuring Thm. 2\n\nAgreed. We will put the definition of quantities ($\\underline{SNR}$ and $\\kappa$) before the theorem.\n\n> * Construction of $\\kappa, p_{a,\\tau}$\n\nIndeed, $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.\n\n> * Constraints on the filter coefficients\n\nGreat 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.\n> Parameter tuning...\n\nThe 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. \n\n> Originality: the proposed ... For example:\n> * Empirical investigation of the adaptive filter\n\nWe 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. \n\n> * On the choice of the filter coefficients\n\nIn 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. \n\n> * A plot of the performance vs. the order of the filter\n\nFig. 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$.\n> Minor points\n> * $t$ in lines 263 and 265\n    \nFrom 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.\n> * should $\\kappa_\\tau |\\nabla F(x_{t-\\tau})|^2$ be $\\kappa_\\tau^2$ instead?\n\nWe 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.$\n> * Top of page 13, eq 10, extra $+$ sign\n\nAgreed, we will fix it.\n> It would be nice to have a more detailed comparison to correlated noise approaches for DP optimization\n\nThanks 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. \n> No batch size in Thm. 3\n\nFrom 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.\n> LP filter on iterates of DP-SGD?\n\nThank 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. \n\n$\\quad$\n\nThank 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L5dQgrJspL", "reviewer": "Reviewer_WMCW", "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.", "questions": "- Do the adaptively selected filter coefficients from Section 5.3 have the same convergence guarantee?\n- Did you experiment with adaptively selected filter coefficients from Section 5.3?\n- Why does the performance of LP-DPSGD drop with larger epsilons when fine-tuning on CIFAR-10 in Figure 10?", "limitations": "The paper clearly mentions the most important limitations of the work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Investigating the behaviour of DP-SGD in the frequency domain is interesting, and to my knowledge novel. The proposed low-pass filter is justified theoretically and consistently improves performance across several models, datasets and optimisers. Since the filter is just a post-processing of the noisy gradients, the privacy analysis does not change, and the filter should be easy to implement with different variants of DP-SGD.", "weaknesses": "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.\n\nThe 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.\n\nMinor points:\n- Line 43: 250K steps for LLAMA training sounds like a typo.\n- 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.\n- As far as I know, the Gaussian mechanism bound in Definition 2 has only been proven for $\\epsilon \\leq 1$.\n- 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n$\\quad$\n> 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.\n\nWe 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.\n\n$\\quad$\n>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.\n\nGreat 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.\n\n$\\quad$\n> Minor points\n>Line 43: 250K steps for LLAMA training sounds like a typo.\n\nAccording 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.\n\n$\\quad$\n> 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.\n\nAgreed! We will discuss this point in our revised paper.\n\n$\\quad$\n> As far as I know, the Gaussian mechanism bound in Definition 2 has only been proven for $\\epsilon\\leq 1$.\n\nYou 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.\n\n$\\quad$\n>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$.\n\nWe 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.\n\n$\\quad$\n> 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?\n\nThis 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.\n\n$\\quad$\n> Why does the performance of LP-DPSGD drop with larger epsilons when fine-tuning on CIFAR-10 in Figure 10?\n\nGood 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.\n\n$\\quad$\n\nThank 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Response to all reviewers
We would like to thank the reviewers for their constructive and detailed feedback. We are glad that the reviewers found our approach novel and  effective despite its simplicity. Before responding to the individual reviewers' questions, we would like to thank the reviewers for their suggestion on adding a discussion on the signal processing background. We completely agree that such a discussion would improve the paper. Therefore, in our revised version, we plan to include an additional appendix discussing the background. Below is our suggested appendix on the background:

## Background in signal processing
### Frequency domain analysis
* **What is frequency domain analysis.** 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 $\nu$ as the indices of the signal, e.g., $\{X(\nu)\}, X(\nu)\in \mathbb{C}$, where each term $X(\nu)$ records the amplitude and phase of the sine wave of frequency $\nu$ that composes the signal; in contrast, in 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 the paper, we treat each coordinate $i \in [1, \dots, d]$ of the privatized gradient over the iterates as an individual signal, i.e. $\{g_1[i], g_2[i], \dots, 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.
* **Why converting a signal to the frequency domain is beneficial.** 
    1) 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 non-zero, i.e., $X(1) = 1$ and all other entries are zero, i.e., $X(\nu) = 0, \forall \nu \neq 1.$ This means  $x_t$ has only one periodic signal in it. 
    2) Certain mathematical analysis can be significantly simplified in the frequency domain. For examples, linear differential equations in the time domain are converted to algebratic 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 simplifies the analysis of the signals and filters' dynamic. See Sec. 3.7, 10.5 in Oppenheim et al., 1996 for detailed discussion.
* **How to obtain a frequency domain representation of a signal.** To obtain a frequency domain representation of a discrete signal, one can apply Discrete Fourier transform (DFT) ($\mathcal{F}\{x_t\}: X(\nu) = \sum^{T-1}_{t=0} x(t)e^{\frac{-2\pi i t}{T}\nu}$)) to the signal. By directly applying DFT to a signal and obtaining $\{X(\nu)\}$, one can identify how the signal is composed of sin waves of different frequencies $\nu$ 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(\nu) = 1/2$ for $\nu = \pm\frac{1}{2\pi}$ and 0 elsewhere.

### Low-pass filter
* **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(\nu) = 1$ when $|\nu| \leq \frac{1}{2\pi}$ 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 combinations of the input signal. Considering $g_t$ as the time signal, the general form of a linear filter on $g_t$ is $$m_t = \sum_{\tau=0}^t \kappa_\tau g_{t-\tau} = -\sum_{\tau=1}^{n_a}a_\tau m_{t-\tau} + \sum_{\tau=0}^{n_b}b_\tau g_{t-\tau},$$ where $\kappa_\tau$ 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:
    1. 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\} \leq 3$.
    2. Decide filter coefficients $\{a_\tau\}, \{b_\tau\}$.  Filter design can in general be a complex procedure and it involves deciding on trade-offs among different properties of the filter. Two standard constraints on the filter coefficients are: a) $-\sum a_\tau + \sum b_\tau = 1$, to ensure the filter has unit gain, i.e., the mean of the signal remains unchanged; and b) the solutions $x$ to $1 + \sum a_\tau x^\tau = 0$ satisfies $|x|<1,$ to ensure the filter is stable, i.e., $\sum|\kappa_t| < \infty.$ In the paper, we directly follow the design of Chebyshev filter and Butterworth filter, and tuning their cut-off frequency (and ripple) to achieve the best performance and maintaining these properties. See Winder, 2002 for detailed discussion. 
* **Plot of the frequency response of the filters.** In the PDF response, we provide the time response ($\kappa_\tau$) and frequency response of the filters used in Tab. 2 in the original paper and additional experiments.

Meta-review: 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.
Decision: Accept (poster)