DiSK: Differentially Private Optimizer with Simplified Kalman Filter for Noise Reduction
Authors: Xinwei Zhang
Zhiqi Bu
Borja Balle
Mingyi Hong
Meisam Razaviyayn
Vahab Mirrokni
Venue: ICLR 2025 Poster (2025)
Keywords: Differential privacy
Kalman filter
noise reduction
nonconvex optimization
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: This paper uses Kalman filter to denoise privatized gradients in DP optimization and improves training performance

Abstract: Differential privacy (DP) offers a robust framework for safeguarding individual data privacy. To utilize DP  in training modern machine learning models, differentially private optimizers have been widely used in recent years. A popular approach to privatize an optimizer is to clip the individual gradients and add sufficiently large noise to the clipped gradient. This approach led to the development of DP optimizers that have comparable performance with their non-private counterparts in fine-tuning tasks or in tasks with a small number of training parameters. However, a significant performance drop is observed when these optimizers are applied to large-scale training. This degradation stems from the substantial noise injection required to maintain DP, which disrupts the optimizer's dynamics.
This paper introduces DiSK, a novel framework designed to significantly enhance the performance of DP optimizers. DiSK employs Kalman filtering, a technique drawn from control and signal processing, to effectively denoise privatized gradients and generate progressively refined gradient estimations. To ensure practicality for large-scale training, we simplify the Kalman filtering process, minimizing its memory and computational demands.
We establish theoretical privacy-utility trade-off guarantees for DiSK, and demonstrate provable improvements over standard DP optimizers like DPSGD in terms of iteration complexity upper-bound.
Extensive experiments across diverse tasks, including vision tasks such as CIFAR-100 and ImageNet-1k and language fine-tuning tasks such as GLUE, E2E, and DART, validate the effectiveness of DiSK.  The results showcase its ability to significantly improve the performance of DP optimizers, surpassing state-of-the-art results under the same privacy constraints on several benchmarks.

Published as a conference paper at ICLR 2025
DISK: DIFFERENTIALLY PRIVATE OPTIMIZER WITH SIMPLIFIED KALMAN FILTER FOR NOISE REDUCTION
Xinwei Zhang
Zhiqi Bu
Borja Balle
University of Southern California xinwei seveizquse weuuscc.e... edu
Amazon AI
Google DeepMind
woodyx21 2oodyx218@gmai com
bball Sealoo@go
Mingyi Hong
Meisam Razaviyayn
Vahab Mirrokni
University of Minnesota mhongeumn. edu
University of Southern Califoria razaviya@use. edu
Google Research
mirrokni@google...
ABSTRACT
Differential privacy (DP) offers robust framework for safeguarding individual data privacy. To utilize DP in training modern machine learning models, dif- ferentially private optimizers have been widely used in recent years. A popular approach to privatize an optimizer is to clip the individual gradients and add suf- ficiently large noise to the clipped gradient. This approach led to the development of DP optimizers that have comparable performance with their non-private coun- terparts in fine-tuning tasks or in tasks with a small number of training parame- ters. However, significant performance drop is observed when these optimizers are applied to large-scale training. This degradation stems from the substantial noise injection required maintain DP, which disrupts the optimizer's 's dynam- ics. This paper introduces DiSK, a novel framework designed to significantly enhance the performance of DP optimizers. DiSK employs Kalman filtering, a technique drawn from control and signal processing, to effectively denoise priva- tized gradients and generate progressively refined gradient estimations. To ensure practicality for large-scale training, we simplify the Kalman filtering process, min- imizing its memory and computational demands. We establish theoretical privacy- utility trade-off guarantees for DiSK, and demonstrating provable improvements over standard DP optimizers like DPSGD in terms iteration complexity upper- bound. Extensive experiments across diverse tasks, including vision tasks such CIFAR- and ImageNet- 1k and language fine-tuning tasks such as GLUE, E2E, and DART, validate the effectiveness of DiSK. The results showcase its ability significantly improve the performance of DP optimizers, surpassing state-of-th art results under the same privacy constraints several benchmarks.
INTRODUCTION
Data privacy has become one of the major concerns in modern machine learning systems. Differen- tial Privacy (DP), with its rigorous mathematical foundation, offers a powerful solution. DP provides a framework for developing training algorithms that safeguard the privacy of individuals' data used train machine learning models. Among various algorithms, Differentially Private Stochastic Gra- dient Descent (DPSGD) (Abadi et al., 2016) and its variants (Li et al. 2021 Yu et al.) [222 Tang al. 2024) have emerged as popular choices for training various models, including computer vi- sion (De et al., 2022) and language models (Bu et al., 2023 2024). These algorithms inject noise into the training process to guarantee privacy. However, this noise injection often comes at signif- icant cost to model performance, limiting the widespread adoption of DP optimizers (Jayaraman & Evans 2019). For example, (McMahan et al. 2018 De et al. 2022) observed that DP training led to 15% drop in model accuracy on the Reddit dataset and 30% drop CIFAR-10 compared to non-private training. This challenge has limited the application of DP optimizers primarily to small models or parameter-efficient fine-tuning, highlighted by (Li et al.
2021).
Many recent works aim to improve differentially private (DP) training performance. These include applying low-pass filters to separate gradients from noise (Zhang al. 2024a), injecting correlated

---

Published as a conference paper at ICLR 2025
noise with algorithms like DP-FTLR (Koloskova al. 2023 Choquette-Choe et al. 2024), using sharpness- aware minimization for flatter loss landscapes that are less sensitive to DP noise (Park)
et al. 2023), adaptive clipping (Andrew et al., 2021] Lin et al. 2022; Hu et al. 2021 and model structure optimization (Bu et al. Papernot et al. 2021 De et al. 2022). However, these meth- ods often require extra memory, lack theoretical guarantees, have limited applicabilityy Therefore, there is strong demand to design new approach that 1) is memory and computation efficient for implementation, 2) has a theoretical guarantee, and is compatible with wide range of existing DP optimization algorithms and models. To meet this demand, we leverage the Kalman filter, tool from control theory, to improve gradient estimates in DP optimization. We further simplify our algorithm for memory and computational efficiency, while maintaining theoretical grounding and broad compatibility with existing DP algorithms and models.
The tools in signal processing and control theory have been leveraged to design novel optimization algorithms. In the context of DP optimization, the error- freob-fe approach has been adopted to reduce the bias caused by the clipping operation (Zhang al. 2024by; the low-pass and high-pass filters have been used to separate the gradient from the DP noise (Zhang et al. 2024a Koloskova et al. 2023 Ccoqueete-Choor et al. 2024); the low-pass spatial filter, including Gaussian and Laplace filters have been used to smooth the privatized model or gradient across dimensions (Wang et al,,
2020a
2021 Liu al. 2022). These methods effectively improve DP optimizers' performance.
1.1
CONTRIBUTIONS
Our approach centers on constructing a dynamic system where the gradient serves as its state. We treat the privatized gradient as noisy observation of the true gradient within this system. By applying Kalman filter, we obtain a more accurate estimate of the true gradient by leveraging the gradient dynamics and past estimates, thereby enhancing the performance of DP optimizers. To address the inherent inefficiency of the Kalman filter, we introduce a series of simplifications that reduce memory and computational overhead. Our main contributions can be summarized as follows:
Algorithm Design: We introduce a novel Kalman filter-based approach designed mitigate DP noise and enhance the performance of various DP optimizers.
Algorithm Simplificatinn: We simplify the Kalman filtering process to significantly reduce mem- ory and computational overhead. This simplified approach, DiSK, requires only one additional forward step and two extra optimizer states.
We provide theoretical analyses of DiSK, demonstrating that the algorithm is convergent. Morcover, we showed that, compared to DPSGD, DiSK improves the iteration complexity upper-bound by problem-dependee constant factor.
Theoretical Analysis:
Extensive experiments actoss various models, datasets, and optimizers demonstrate that DiSK significantly boosts DP training performance. Specifically, under the same (or tighter) privacy budgets 8,8 1/N1.1, DiSK exhibits substantial improvements in test accuracy for traninng-romm-scaachh scenarios: a notable increase from 33.56% to 36.89% on the ImageNet-Ik Ik dataset, a considerable rise from 63% to 75% CIFAR-IO, and remarkable im- provement from 21% to 42% on CIFAR-100. Furthermore, in fine-tuning tasks, DiSK demon- strates remarkable improvements: an increase from 85% to 89% on CIFAR-100 and an improve- ment from 81 % to 86% on the GLUE dataset. These results surpass state-of-the-e DP training performance under the same privacy guarantees.
Numerical Results:
2 PRELIMINARIES
2.1 PROBLEM DEFINITION & NOTATIONS
Typical training procedures require solving the empirical risk minimization (ERM) problem
1 F(x)=
Σ f(x: E)
min
XERd
N
EED
where E Rd is the optimization variable, D ........ samples, and f(() denotes the (possibly non-convex) loss function parameterized by x and evaluated sample e. For solving the above optimization problem, we rely on iterative procedures, such as
EN } is the training dataset with |D] N
2

---

Published as a conference paper at ICLR 2025
SGD, where the parameters are updated over the iterations t 1.2..... Throughout the paper, use (+)e to denote the variables at iteration t, and use Ia to denote the identity matrix of dimension d.
2.2 DIFFERENTIALLY PRIVATE OPTIMIZATION
Let us start by recalling the definition of (c, d)Differennia Privacy:
Definition 1 ((c, 6DD (Dwork& & Roth 2014)) A randomized mechanism M is said be (c, 5)- differentially private if for any two neighboring datasets DD DD' (D, DD' differ only by one sample) and or any measurable oulput set S, it holds that Pr(M(DD) 8) S ePPr[M(D)) +))+ +
A widely used approach achieving differential privacy (DP) when solving ERM problem I is to employ differentially private stochastic gradient descent (Abadi et al. 2016) and its variants, such as DP-Adam and DP-Lora (Yu et al.) (02I). To ensure DP, DPSGD leverages the Gaussian mechanism (Dwork & Roth 2014] Abbadi et al. (0166), injecting carefully calibrated Gaussian noise into the gradients each iteration of the optimization process. This noise injection effectively masks the contribution of individual data points, thereby providing the desired privacy guarantee.
Definition 2 (Gaussian Mechanism (Dwork & Roth, 2014; Balle & Wang 2018 ) Suppose
an algorithm A D + Idd has l sensitivity A. i.c. maxp, xy [[( AAD)) S AA. O and 5 E [0, 1}, by adding carefully chosen random Gaussian
Then, for any noise to the output of the algorithm, we can make the algorithm (c.8)-DP. More specif- A(x) + w, with edw S 8 is (c,8)-DP, where ((t) = P[W(0,1) S $1] T DA edor c (- AA
ically, the mechanism (x)
((0,)) and app satisfies
20 =AA)
the cumulative density function of normal distribution.
The DPSGD algorithm, outlined in Algo- rithm [ operates by first sampling mini-batch B, of size B and computing the per-sample gra- dients at each iteration l. To guarantee differen- tial privacy, it then applies the Gaussian mecha- nism, which involves clipping each per-sample gradient to bound its sensitivity to maximum value C' and subsequently injecting Gaussian noise. The clipping operation clip (VJ,C) =
Algorithm DPSGD algorithm
Input: Xp, D, C, ODP for / == 0,...,T- 1 do
Uniformly draw minibatch B, from
g: = EEEB, clip (V {x);;)) C*) + w: where We ~ NO0, of Ia)
X++1 x; f/tBt. end for
min [1, |
f,, often implemented by scaling the gradient when its norm exceeds C, limits the influence of any single data point, while the added noise further masks individual contributions, ensuring the desired privacy level (Abadi et al., 2016).
Theorem (Privacy Guarantee (Abadi al. 2016)) Given the number of samples N, the batch- size B, total number of iterations T and clipping threshold C, there exist positive constants u, v,
C2T Algorithu is (e, 6D- TB2T and 0 < by choosing ohr 2 U Nº22 such that for any E < N2
Theorem implies that the variance of the DP noise injected into the gradients, B[[[w, do scales linearly with both the number of iterations T and the number of parameters d. This presents a significant challenge in modern deep learning, where models size d is large (e.g., 22.M-632.1 for VIT (Dosovitskiy et al., 2020). 1377M-1.6 for GPT-2 (Radford et al., (2019) and require extensive training (e.g.. 300K for VIT (Dosovitskiy et al. (020)) and 250K for training Llama (Touvron et al.)
2023 ) Consequently, the magnitude of the injected DP noise can become substantial, leading to considerable degradation in model performance.
2.3 KALMAN FILTER
The Kalman filter is a powerful algorithm that provides estimates of unknown variables by iteratively incorporating a series measurements over time (Kalman 1960) Welch et al. 1995). To illustrate its application, let us consider linear dynamic system characterized by the System update and Observation equations:
0. AO.- u. + Vt, (System update)
(2)
3, = CO, +Wr
(Observation)
3

---

Published as a conference paper at ICLR 2025
where A Rddexdo C E Rdo the transition and observation matrices; 0₂ R is the unknown variable to tracked/estimated; 2b, E Rev denotes the observation of the system; u, E Rd denotes the known input; and V, R W, E R are the process and observation noises that follow Gaussian distribution (0, 2, Ew respectively. Then, the Kalman filter uses the following updates track [0.) (Kalman 1960 Welch et al. 1995):
0 a| A + u
(Prediction)
P Paj--1 = AP, Ev
K, = Pajc-1C' (CP f/c-1 C + Dw)
(3)
0: = (Ido KKC))0 K.4h
(Correction)
P. = (Ldo (K,
The filter first predicts the state Oejc-1 by system dynamics, and compute the filter gain K, E Rdexds based on the covariance matrix P, E Rdexdo, and corrects the prediction with system observation & to obtain the estimate 0, at time L. The Kalman filter makes use of both the noisy observation and the prior knowledge of the system dynamies obtain an accurate estimation of the state O,.
key innovation this work is to treat the privatized gradients in the DP optimization as noisy observations of the true underlying gradients. By constructing gradient dynamics using Taylor ex- pansion, we establish a framework for applying the Kalman filter to refine these noisy observations and obtain more accurate gradient estimates. To ensure practical applicability for large-scale mod- els, we simplify the Kalman filter, significantly reducing its memory and computational footprint. These improved gradient estimates ultimately lead to enhanced performance in differentillly private optimizers.
2.4 RELATED WORKS
Optimization with filters and controllers: The use of filters and controllers designing and analyzing optimization algorithms has rich history. Researchers have leveraged high-pas, pass and low-pass filters to enhance gradient estimation in zeroth-order optimization (Chen et al.) 2022), employed PID controllers for both centralized and distributed optimization (Wang al. 2020b). and analyzed optimizers through the lens of control theory, treating them as dynamic systems (Lessard)
al. 2016 Hu Lessard
2017 7 Muchlebach & Jordan (0ha et al. 2024 Badithela
& Seiler 2019; Cyrus et al. 2018 Scherer et al. 2023 Zhang et al. 2023).
Kalman filter for optimization: The Kalman filter has been utilized in convex optimization for re- ducing stochastic gradient noise (Bittner & Pronzato 2004 Vuckovic 2018). Vuckovic (2018) uses the dynamics of the optimization variable and the gradient to construct the Kalman filter analyze and improve the performance of momentum methods. Bittner & Pronzato (2004) uses gradient and Hessian as its states to construct the dynamic system for SGD to construct a stopping rule. However, these approaches, with their direct application of the Kalman filter, incur prohibitively high compu- tational and memory costs, ranging from (d to O(d)) rendering them impractical for training large-scale machine learning models.
Improving DP optimization: Numerous techniques have been proposed to enhance DP optimiza- tion by mitigating the impact of DP noise. These include adaptive gradient clipping methods that dynamically adjust clipping thresholds (Andrew et al., 2021] Bu et al.) 2024), barameter-efficin training strategies employing adapters, low-rank weights, or quantization Yu al. 2021 Luo al.) 2021 Yu et al.) 2021). 1) and the design of specialized model architectures less susceptible to noise perturbations (De al. 2022 Papernot et al., 202T Wang al.) (020a). Furthermore, drawing inspiration from signal processing, researchers have explored the use of colored high figh-freeuency DP
noise to separate from the gradient (Koloskova et al. (223) and the application of low-pass filters
to extract the gradient signal from noisy observations (Zhang et al. 2024a).
AL.GORITHM DESIGN
This section introduces the general Noise Reduction for Differentially Private Optimizers with Simplified Kalman Filter (DiSK) framework. This approach leverages the inherent dynamics of the gradient and employs Kalman filtering to obtain denoised estimates of the true gradients from
4

---

Published as a conference paper at ICLR 2025
their noisy, privatized counterparts. To enhance its practicality for modern deep learning, Sectionn..2 details simplified version of the Kalman filter updates, designed for memory and computational efficiency.
3.1 GRADIENT DYNAMIC AND KALMAN FILTER
To explain our idea of using the Kalman filter for denoising the gradient, let us start by first establish- ing a dynamic system for the gradients, comprising a "system update" equation and an "observation" equation: The system update of the gradient dynamics can be derived by the Taylor expansion and quantifying the change of the gradient at iteration t:
(x))))
(xx, + H, xx-1) Vo,
where H, == F(x E Rddd and v, = 2 So (xx + = is the remainder and (.)s denotes the tensor vector product. The observation the system is defined as the privatized gradient gt, which is a stochastic mapping the true gradient:
g:
clip (Vf(x,: 5), C) + w. = C.VF((;) + +w/
(5)
EEB.
where w/ is the observation noise containing the DP noise and sub-sampling noise; C, is the obser- vation matrix. If the clipping operation inactive and B DD i.e., the full batch gradient used, then C = I Otherwise, C, depends on the clipping factor and the mini-batch B. Combining the system update (4) and the observation (5). we can model the system dynamic of the gradient as: Vx(x)) (x + Hx xx-1) Vt.
(System update)
(6)
g: (x)F((x)) w/
(Observation)
Let us compare our dynamic system with the general one in (2: In our dynamic system, the gradient F((;)) plays the role of the state θ, Other parameters in (2) have the following correspondence
to gradient dynamics: A = Ia, C = Ct. the input u, = H2(x; - x1)),, and the observation bb, = gr- With the above mapping.
apply the Kalman filter that combines the system update and the observation of the gradient to improve the overall estimation quality of the actual gradient beyond only using the observation g:- However, there
key challenges when applying Kalman filter to (6): 1) the input (x, - x;-1) is hard to obtain as computing the Hessian matrix H. is challenging for large models, and can only approximate (x,x; resulting a noisy input; 2) the observation matrix C, is an unknown time-varying random matrix, resulting a multiplicative observation noise. Due these differences, the traditional Kalman filter (Kalman) 1960) cannot be directly applied. Instead, we apply the Kalman filter with noisy input and multiplicative observation noise proposed in Wu et al. (2016) to our system (6), leading to the update rules:
tr = 8:-1 + (x(
x(-1)
(Prediction)
P cj|-1 = P.-1 + En E.v
K; = P.t:--EECC (Ew E[C,] (EeS, P.t. E[C,]T Σn)
g: (I C,, Bqj-1 Kig.
(Correction)
P. -I- (.,KKEC,.)P.. (--1
S. E-EEgr g
where P. denotes the covariance matrix of gi, EH,Ew Ec, Ey denote the covariance matrices of the random variables H,, w,. C₁ v,, respectively, and H, is an instantiaiion/obseratioon of the unknown Hessian matrix H, The difference between the above Kalman filter and the original magenta color. The variance of the Hessian H, plays a role in updating P Pt|t-1 Ke, and the expectation E E[C,] of the random observation matrix C, is used for the updates and its variance Eg also appears in the update of K,, Compared to the noisy gradient gi, the output of the Kalman filter g: has smaller variance, resulting in improved performance when used DP optimizers.
Kalman filter 33 highlighted
The resulting optimizer with the Kalman filter is given in Algorithm The hyper- paramepprameters of the Kalman filter are the expected observation matrix E[C] and the variances the noises in the system, i.e. oy Ec, Σ.. Here, we dropped subscript & for C, for simplicity in our modeling.
5

---

Published as a conference paper at ICLR 2025
Algorithm 2 Optimizer with Kalman Filter
1: Input: Xo. D, E C o Ec. Σh
2: Initialize: g-1 d 0,P-1 -o
3: for 10=0 -'. do
4: Randomly draw minibatch B, from
5: Compute privatized gradient g: = EeEB, clip (V)( w.
# Gradient
observation
6: gelt-1 gt-1 + H1d11
Prediction
7:
Pap-1 = P1-1 ΣH
8:
K P
P B[C]] + to EH) # Compute gain Compute denoised private gradient # Parameter update
9:
gi = Bijt- + (g
E| B((-))
X
SrlimizerUpdaterr (,8)))
11:
d, Xt-1
# Record update direction
12:
P. p (I- K2 [[C)))
# Update covariance matrix
13: end for
3.2 ALGORITHM SIMPLIFICATION
While Algorithm 2 provides a general framework for applying Kalman filtering to various opti- mizers, faces significant challenges in terms of computational and memory demands. Specifically, accurately computing the Hessian matrix (H) for large models under DP constraints is infeasible, the matrix inversion step introduces cubic computational complexity (O(d)), and storing the covari- ance matrix (Pt) at each iteration requires quadratic memory (O(d2). To address these limitations and arrive at a practical and memory- algorithm, we propose the following simplifications:
Constant C,: We simplify the random matrix C₁ to identity matrix Lg, and simply model the randomness in the observation as additive noise only. This simplification is achieved in two steps corresponding to the sources of randomness in C,. First, we remove the impact of clipping in C, This is justified when 1) the clipping threshold C' is large enough so that clipping is inactive; or when the clipped gradient V (x) has zero curl, that our method optimizes Fc(x), where
Fe(x) = S Fox(e T xd2, FFc(x) = N
1
Σ clip ()); EED
Under this assumption, the minibatch clipped gradient 1/ EeEr clip (x, is unbiased estimation of VFf(x). Thus, E[C,] La- Second, the randomness of sub-sampling in C, is removed by assuming that the sub-sampled mini-batch gradient only causes additive noise, i.e., 1 EçEs clip (V,((,)),C) VFc(x) WSGD, that C Ia and Σc
Hessian estimation: We apply the following "trick" to bypass the explicit computation of the Hes- sian matrix, H.: we approximate the Hessian-vector product, (d,,,)), using a finite difference method (Pearlmutter) 1994):
H.d. V 7d.-1) 1 VF(x)) + 0((+) ~
1 Vf(xi + - ()(x(()
B
?
This estimation eliminates the need for expensive Hessian computations and significantly reduces both memory and computational complexity.
Simplification of Σy: A few matrix computation steps in Algorithm consuming and memory inefficient. Specifically, the matrix inversion in Line 8 of Algorithm 2 incurs cubic computational cost (O())), which becomes prohibitive for large models with bil- lions of parameters. Therefore, we simplify the algorithm by assuming that the covariance matrix in the Kalman filter is time-invariant identity matrix scaled with a constant, i.c.. Σh L Under this assumption, the matrices P; and K, become P,Ie, k,I,, for some scalars Pt, k2 Thus, we re- duce all matrix computations efficient scalar-vector multiplications and the memory complexity storing these matrices to O(1), making our algorithm a viable option for DP training of large-scale models.
extremely time-
Filter gain simplification:
With the above simplification, the updates of Pt. ke simplify to Pt (o2-o (p- -où) = Pe-1+oš+og
it03+og. Therefore, k converges to its stable value with linear
++03+00
20 +30 (102
rate, i.e., like kooll = O(c)), where C₁
(0, 1) (see
20 +30 +o8
to3 30%)

---

Published as a conference paper at ICLR 2025
Algorithm 3 DiSK: Differentially private optimizer with Simplified Kalman filter
Input: Xo, 7, C, ODP
2: Initialize: g-1 go, d-1
3: for ........7 T do
4: Randomly draw minibatch B3 from D
5: gi= = EeEB, clip ( f 1:)+ + (1- byy ()xx))) + we
where w, ~ (N0, Ia)
6:
g: (1 K) Kgr
# Apply Kalman filter # Update model # Record update direction
7:
X OptimizerUpdatef/e
8:
d, X X
9: end for
derivations in Appendix A.3).
constant k Ki V / to further simplify the algorithm and avoid iteratively updating ps and recomputing hy for each step.
So
With the above simplifications, the complex Algorithm 2 simplifies to DiSK in Algorithm [ For detailed walkthrough of this simplification process, please refer to Appendix A..3 This simplified algorithm computes and privatizes the linear combination of the gradient evaluated two points,
X1, X, tdd Then, this privatized combination undergoes exponential weighted averaging to obtain
ge. which serves as the input the base optimizer (Line 7 of Algorithm Bp.
3.3 ADDITIONAL DISCUSSION
Memory and computation cost: Compared with the base DP optimizer, Algorithm one additional forward step to compute f(x; + -d)-1;E). This means that the algorithm has at most twice the computational cost of the baseline DP-SGD algorithm. Moreover, Algorithm 3 Jnlyy requires two additional states to store: gi and d, Compared DPSGD, which requires storing the model and the gradient, DiSK has at most twice the memory cost; and compared to DPAdam, which requires storing the first- and second-order moments, the algorithm has at most 1.5x the memory cost.
3 requires
Connection to NAG and STORM: Remarkably, Algorithm 3 has an implicit connection to the (uni- fied) Nesterov accelerated gradient (NAG) method (Shen et al. |023| Sutskever et al. 2013) and the Stochastic Recursive Momentum (STORM) algorithm (Cutkosky & Orabonal (2019). Specifically, by letting the OptimizerUpdate be SGD, assuming clipping is inactive, and setting W, = 0 (i.e., without privatizing the gradient) in Algorithm 3 we can make a clear connection: On one hand, DiSK reduces NAG by choosing 7 x 17 K, 1 K μ4, and B N. On the other hand, the update of DiSK matches STORM by choosing = -1, == a, and B = 1. A detailed deriva- tion and discussion is provided in Appendix A.4 This observation reveals an intriguing connection between NAG (designed for acceleration) and STORM (focused on variance reduction), unifying them within the framework of DiSK, Kalman filtering- -asee algorithm.
Connection to DOPPLER: DOPPLER (Zhang et al. 2024a) and DiSK both use filter to separate the gradient signal from the DP noise. If g: only evaluates the gradient x, instead of using the linear combination of gradients at two points, Xt, Xx +-d in Algorithm 3 Line 5, DiSK becomes DOPPLER with first-order filter. The key difference is that DOPPLER assumes an underlying low-frequency dynamic of the gradient and applies time-invariant low-pass filter. Designing the optimal low-pass filter relies on the prior knowledge of the gradient frequency spectrum, which is hard to obtain in practice, and implementing such high-order low-pass filter results in large memory overhead. While DiSK, we do not assume the frequency property of the gradient signal. Instead, we incorporate the gradient dynamics into the filtering procedure and use the Kalman filter, a predictive filtering approach, to reduce the impact of DP noise.
4 THEORETICAL ANALYSIS
This section includes theoretical analyses of Algorithm 3 provable noise reduction, and the privacy-utilip trade-off of the algorithm. To facilitate analysis, we make the following assumptions:
Our study establishes the convergence,
A (Smoothness) f(r,) is L-smooth for any &. i.e., (xx - ff(y)))) < ||x -yl, AA E
D, Vx,y E Rdd.

---

Published as a conference paper at ICLR 2025
A 2 (Bounded Variance) The per-sample gradient has bounded variance with ERED f 2 SGD Yx R*, where EgEDl:] denotes the expectation taken on the randomness over & that is uniformly sampled from dataset D.
3 (Bounded Gradient) Each per-sample gradient has a bounded norm, i.e. [V E)ll <
G, Vx E Rdd VV D.
Let us briefly comment on these assumptions: A and A2 are standard non-convex optimiza- tion (hl & Hazan 2016 Zaheer et al. 2001 Abadi et al. (016)): and A commonly used in analyzing the convergence of DP algorithms (Abadi et al. 2016; Wang et al. 2020a [nnreww eet al. (02T) to avoid introducing the clipping bias. Since the impact of clipping not the major focus this paper, we follow this tradition and use AB simplify our theoretical analysis.
4.1 CONVERGENCE ANALYSIS
We provide the following convergence results for Algorithm assuming OD being a constant.
JG, Ks 11 satisfy Theorem Assume 1 A hold. Fix hr and choose C 2 (1 2(1-x)
x
1 < 2L(1+ 2(1 -000-x)333B00 x2) 11 + - M, K. 1
+ > (x + 2)2
and run Algorithm for T iterations. Then,
Σ E [ S 2(F(xo) + [VF(X))
T
M1r/T
+ 2( + +
(2 (12+11+ 110 + doip
(8)
MI1
B
where M, 1+ 4(2+1 1 M1 = (1 + 2n [.) -433 (1) (2 + + My)
7 L(1 (1
0, and B > n(1 n11-n)/2+-/
1+ 11- (M- M.M.)
0 are some non-negative constants.
(111==)
The proof of Theorem 2 is relegated to Appendix B
Notice that when A 1, we have 3 = 0, M,
2(1 nL) and the convergence result recovers that of DPSGD (Ghadimi & Lan 2013 Zhang al. 2017). With this theorem, we can choose specific parameters and obtain the following corollary:
Corollary Under the conditions of Theorem
2
choose 7 =-1,
1
2M, (((x)) F*) [[VF(x))]
n min
L(2 + 4/M, MM)' M.LV
2T do
1)(1 -k))/2 + L(1 (1 + L
1- (1 x) L3)
2M
|VFF(x))
20 d
K MM,L S 1, = (x(((xo) F+) S 1, and B 2 max
2L(F(xo)- F*]
si. (1xx)(
and sufficiently large T
then Algorithm
satisfies:
da
T T
$8 Mr.(FF(xo) F d =0
EEIIF(<))) T=
T
T
Convergence improvement: The above result implies that the order of the number of iterations T needed for convergence of Algorithm 3 is the same of DPSGD (Ghadimi & Lan 2013 Zhang
et al. 2017). However, Algorithm 3 has a constant factor improvement in the upper bound of its iteration complexity
DPSGD. This improvement results from the presence of Mr. < 1 in the numerator in the RHS of (g). More specifically, if Mx < i... |
then the convergence bound reduces by a factor of /1/Mz, and DiSK has clear theoretical im- provement over vanilla DPSGD. Case I: For (u-strongly) convex problems, it is guaranteed that (x(F(xx) F+) < |VF(())) <
(L F*). Therefore, the factor M,. Ju/ L,/L,J 1]. Case II: When training highly non-convex deep learning models, the Lipschitz constant can be large (Her- rera et al. 2020). and (F( - F*) can be much larger than VF(x,)]| which results a considerable algorithm performance improvement compared vanilla DPSGD.
8

---

Published as a conference paper at ICLR 2025
While the above corollary is for the case of y = -1, we can obtain performance improvement
for 7 * -1 as well. The choice y = -1 is optimized for the worst case (function satisfying our assumptions) based on our upper-bound in (8) However, it is possible that for functions satisfying additional assumptions, other choices of 7 lead to better convergence results. This fact further explained after presenting the proof of the theorem in Appendix [B.2]
As the last remark this subsection, notice that our iteration complexity improvement does not require any additional assumption on the problem. In contrast, existing works with convergence improvement require additional assumptions, e.g., on the correlation between the gradients (Zhang al. 2024a). or on the trace of Hessian (Choquette- Choo et al., 2024
al. 2022).
4.2 PRIVACY-UTILITY TRADE-OFF
To provide DP, the Subsampled Gaussian mechanism is used in Lines and of Algorithm Instead of V fxx;;)) E), we treat 1- f yd)-1: + (1 1-x f as the per-sample gradient and apply the Subsampled Gaussian mechanism to privatize it. Therefore, Algorithm and DPSGD share similar privacy guarantee, the privacy proof directly follows the Subsampled
Kry
Gaussian mechanism and the composition of 7 iterations in Theorem [
Specifically, by combining obtain the following privacy-utility trade-off:
Theorem and Theorem
2
V2Ne Theorem 3 Assume AL holds. With sufficiently large N, Algorithm for T
Cy/aln(155)
iterations, and choose E. G according to the choices in Corollary then
BIIF((x) 4C ((F
F* In
d'i((1/)) Ne
(10)
Ne
Similar to our convergence result, compared vanilla DPSGD, the privacy-utility trade-off of Al- gorithm reduces by a constant factor of /I/Mg- To the best of our knowledge, this is the first
theoretical result on the utility improvement of DPSGD-type algorithm without any additional assumptions on the problem.
NUMERICAL EXPERIMENTS
We perform extensive pre-training and fine-tuning experiments on various image classification (CV) and natural language processing (NLP) tasks using different base algorithms, privacy budgets, and models. The implementation details of the experiments are given in Appendix C.I An imple- mentation of the algorithm is in httpppps//ggL.bb....oorrrccccc/p research/ disk__ppppp imizer)
5.1 EXPERIMENT SETTINGS
Dataset: We train the models on one synthetic dataset, four CV datasets, including MNIST (Deng
2012), CIFAR-110CIIAR-1000 (Krizhevsky al. 2009). and ImageNet-lk (Deng al. 2009
and three NLP dataset, including GLUE (Wang et al. 2018), E2E (Novikova et al. DART (Nan et 202T).
2017 and
Model: For the CV tasks, we use three different models, including 5-layer CNN, WideResNet (WRN) (De et al. 2022), and ViT (Dosovitskiy al.) 2020), representing three typical CV model structures. For the tLP we use the RoBERTa (Liu et al. 2019) and the GPT-2 (Radford et al., 2019) models. For pre-training, the models are initialized with random weights. fine-tuning ViT, RoBERTa, and GPT-2, we directly use the checkpoints on HuggingFacc (Wolf et al. 2020).
We use the DP version of SGD and Adam for CV tasks, and Adam for NLP tasks as baselines. Then, we apply DiSK to compare their performance. Additional results on LoRA (Li ctt al. 2021) are given in Appendix C.4 In the results, we use KF- to denote the privatized version of the algorithms with DiSK. We use sample without replacement with fixed batch size.
Algorithm:
Hyper-parameter choices:
We tune the harareparameters using a grid search. Specifically, we conduct grid search on the batch size B, total epochs E NT/B, B. and step size 17 for each given privacy budget e. For all experiments, we fix the privacy parameter = 1/M1.1 to obtain a reasonable privacy notion. Detailed hyper-parameter choices discussed in Appendix C.2

---

Published as a conference paper at ICLR 2025
KF-DPAdam DPAdam Improvereenn
KF- CF-DPAdam DPAdam
.93
2.3
A Bingeno
Test Agemmyy
Aucunay Ioprove
Tosl Accurncy
-55
-Empovemeey
-8
Accuriry Enrerove
Test TestAceuusy
92
KF-DPAdam
1.3
Enpervveeent
0.5
0.5
0.5
1
(a) MNIST
(b) CIFAR-I0
(c) CIFAR-100
Figure I: Test accuracy of training from scratch MNIST, CIFAR-10, and CIFAR-100 datasets
with and without DiSK for different privacy e. The green lines show the improvement of DiSK.
KFF-PAdamW
-DPAdamW
Toxl Accurccy
90
Too Acsuany
10
Teot Accuncy
30
80
XF-DPSGD
KF DPAdam
DPSGD
DPAdam
75
40
90 Epoch
120
160
Epoch
Epoch
(a) MNIST. 0.5
(b) CIFAR-100. 8
(c) ImageNet-IK,
Figure 2: Test accuracy on MNIST, CIFAR-100, and validation accuracy on ImageNet- datasets training from scratch with and without DiSK for fixed privacy budgets.
Table 1: Test accuracy of fine-tuning result on the GLUE dataset.
(E = 20)
= 6.7
1
Task
Non-DP
KF-DP
KF-DPLora
DP
KF-DP
KF-DPLora
MNLI
87.6
83.2
84.8
85.9
80.7
82.0
84.7
QNLI
92.8
87.5
88.9
90.5
86.0
88.7
90.3
SST-2
94.8
91.5
92.8
93.1
91.4
91.5
92.9
QQP
91.9
85.8
88.5
89.0
84.2
86.9
87.8
5.2 NUMERICAL. RESULTS
CV tasks: We first train the CV models with randomly initialized weights on different image datasets. The results for 5-layer CNN the MNIST dataset, CNN the CIFAR-10 dataset, and WRN-16-4 on the CIFAR-100 datasets with different privacy budgets are given in Figure [ DiSK significantly outperforms the base algorithm across all used privacy budgets.
The test accuracy curves during the training for 5-layer CNN on the MNIST dataset, WRN-16-4 on the CIFAR-100 dataset, and ViT-small the ImageNet-I kk dataset optimizer with DiSK converges faster than the base algorithm on all tasks and reaches higher final accuracy given privacy budget. The test accuracy of CIFAR- 100 achieves 41.8%, and ImageNet- 1K achieves 36.89, which outperforms the SOTA results that apply data augmentation under the same privacy budget (40.6% for CIFAR-100 (Bao et al., (024) and 33.56% for ImageNet- 1 (De al. ))22)). Additional comparisons on different models, algorithms, and fine-tuning CIFAR-100 are given in Appendix
given Figure 2 The
C.3
NLP tasks: We fine-tune a pre-trained RoBERTa-base model the GLUE datasets. The final test accuracy for is given in Table We follow the same training script and byper-parameter choices in the experiments Bu et al. 2024). Compared with the base algorithm (DPAdamW), DiSK im- proves the final accuracy on all tasks by at least 3.8% when e = 1 and 1.3% when 6.7. Addi- tional results for text generation tasks on the E2E ad DART datasets given in Appendix C.4
Ablation study: We conduct ablation studies on the choice of the ically, how k impact the algorithm performance. The results are presented in Appendix C.3
of DiSK, specif-
Improvements over the SOTA: Table in Appendix C.5 summarizes the improvements of DiSK over the SOTA on different tasks.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
X. Zhang and M. Razaviyayn's work is supported by a gift from Meta, gift from Google, and a gift from Amazon. M. Hong acknowledges the Minnesota Supercomputing Institute (MSI) the University of Minnesota for providing resources that contributed to the research results reported within this paper. URL: http: /www://ww.....moo msi umn edu M. Hong's work is partially supported by NSF grants CIF-2414372, 2426644,, and NSF EPCN-2311000
REPRODUCIBILITY STATEMENT
For the algorithm implementation, we provide a link to an anonymous downloadable source code in Section We also discussed the data, model, and algorithms used in the experiment in Section andd and in Appendix C For our theoretical results provided in Section 4 of the assumptions in the section. The complete proof of the theorems can be found in Appendix B
we also include clear explanations
BROADER IMPACT
This paper presents work that aims advance the field of Machine Learning, combining optimiza- tion with signal processing and control societies. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pp. 699-707. PMLR, 2016.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455- 17466, 2021.
Apurva Badithela and Peter Seiler. Analysis of the heavy-ball algorithm using integral quadratic constraints. In 2019 American control conference (ACC), pp. 4081-4083 IEEE, 2019.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Ana- lytical calibration and optimal denoising. In International Conference Machine Learning, pp- 394-403. PMLR, 2018
Wenxuan Bao, Francesco Pittaluga, Vijay Kumar BG, and Vincent Bindschaedler. Dp-mix: mixup- based data augmentation for differentially private learning. Advances in Neural Information Pro- cessing Systems, 36, 2024.
Barbara Bittner and Luc Pronzato. Kalman filtering in stochastic gradient algorithms: construction of stopping rule. In 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing, volume 2, pp. 709 IEEE, 2004.
Zhiqi Bu, Yu-Xiang Wang, Sheng 7ha, and George Karypis. Differentially private optimization on large model small cost. In International Conference on Machine Learning, pp. 3192-3218. PMLR, 2023.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially pri- vate deep learning made easier and stronger. Advances in Neural Information Processing Systems, 36, 2024.
Xin Chen, Yujie Tang, and Na Li. Improve single-point zeroth-order optimization using high-pass pass and low-pass filters. In International Conference on Machine Learning, pp. 3603-3620. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2025
Christopher A Proquuette-hho. Krishnamurthy Dj Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Correlated noise provably beats independent noise for differentially private learning. In The Twelfth International Conference Learning Representations, 2024.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Saman Cyrus, Bin Hu, Bryan Van Scoy, and Laurent Lessard. A robust accelerated optimization algorithm for strongly convex functions. In 2018 Annual American Control Conference (ACC), pp. 1376-1381. IEEE, 2018.
Soham De. Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle, Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6): 141-142, 2012.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani. Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An im- age is worth 16x16 words: Transformers for image recognition at scale. In International Confer- ence on Learning Representations, 2020.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Theoretical Computer Science, 9(3-4)211-440) 2014.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM journal on optimization, 23(4):2341-238 2013.
Calypso Herrera, Florian Krach, and Josef Teichmann. Estimating full lipschitz constants of deep neural networks. arXiv preprint 133355, 2020.
Bin Hu and Laurent Lessard. Dissipativity theory for nesterov's accelerated method. In International Conference on Machine Learning, pp. 1549-1557. PMLR, 2017.
Yuhang Hu, Zhou Tan, Xianxian Li, Jinyan Wang, et al. Adaptive clipping bound of deep learning with differential privacy. In 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 428-435, IEEE, 2021.
Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pp. 1912, 2019.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learning, pp. 5213-5225 PMLR, 2021.
R. E. Kalman. A New Approach to Linear Filtering and Prediction Problems. Journal of Basic Engineering, 82(1):35 03 1960. ISSN 0021-9223. doi: 36.1152 URL https: //doi. otwpii.org/1...111 111.....111111..1111.1
Anastasiia Koloskova, Ryan McKenna, Zachary Charles, John Rush, and H Brendan McMahan. Gradient descent with linearly correlated noise: Theory and applications to differential privacy. Advances in Neural Information Processing Systems, 36, 2023.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Laurent Lessard, Benjamin Recht, and Andrew Packard. Analysis and design of optimization algo- rithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
12

---

Published as a conference paper at ICLR 2025
Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2021.
Xuechen Li, Daogao Liu, Tatsunori Hashimoto, Huseyin A Inan, Janardhan Kulkarni, Yin-Tat Lee. and Abhradeep Guha Thakurta. When does differentially private learning not suffer in high dimensions? Advances Neural Information Processing Systems, 35:28616-2888 2022.
Guanbiao Lin, Hongyang Yan, Guang Kou, Teng Huang, Shiyu Peng, Yingying Zhang, and Changyu Dong. Understanding adaptive gradient clipping in dp-sgd, empirically. International Journal of Intelligent Systems, 37(1 1):9674-9700, 2022.
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 197.11907.1192,, 2019.
Yuanyuan Liu, Jiacheng Geng, Fanhua Shang, Weixin An, Hongying Liu, Qi Zhu, and Wei Feng. Laplacian smoothing stochastic admms with differential privacy guarantees. IEEE Transactions on Information Forensics and Security, 17:1814-1826, 2022.
lyy Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. In Interna- tional Conference on Learning Representations, 2022.
Zelun Luo, Daniel J Wu, Ehsan Adeli, and Li Fei-Fei. Scalable differential privacy with sparse network finetuning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5059-5068, 2021.
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Harsh Mehta, Abhradeep Guha Thakurta, Alexey Kurakin, and Ashok Cutkosky. Towards large scale transfer learning for differentially private image classification. Transactions Machine Learning Research, 2023.
Hesameddin Mohammadi, Meisam Ruzaviyayn, and Mihailo R Jovanović. Tradeoffs between vergence rate and noise amplification for momentum- accelerated optimization algorithms. IEEE Transactions Automatic Control, 2024.
Michael Muchlebach and Michael Jordan. A dynamical systems perspective on nesterov accelera- tion. In International Conference on Machine Learning, pp. 4656-4662. PMLR, 2019.
Linyong Nan, Dragomir Radev, Rui Zhang, Amrit Rau, Abhinand Sivaprasad, Chiachun Hsieh, Xiangru Tang, Aadit Vyas, Neha Verma, Pranav Krishna, Yangxiaokang Liu, Nadia Irwanto, Jessica Pan, Faiaz Rahman, Ahmad Zaidi, Mutethia Mutuma, Yasin Tarabar, Ankit Gupta, Tao Yu, Yi Chern Tan, Xi Victoria Lin, Caiming Xiong, Richard Socher, and Nazneen Fatema Ra- jani. DART: Open-domain structured data record to text generation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 432-44447,, Online, June 2021. Association for Computational org/
Linguisties. doi: 10.18653/v 1/2021 1.aac2n.aaccmmaaii maacI-main.37. URL https: htttss://aclanthon
2021. nwacl naacl-main.37
Jekaterina Novikova, Ondrej Dušek, and Verena Rieser. The E2E dataset: New challenges for end- to-end generation. In Proceedings of the 18th Annual Meeting of the Special Interest Group on Discourse and Dialogue, Saarbrticken, Germany, 2017. URL. https: http///xvvvv.o/// wwrriiiorrg/ee abs/ 1706.09257 arXiv:1706.09254,
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tem- pered sigmoid activations for deep learning with differential privacy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9312-9321, 2021.
Jinseong Park, Hoki Kim, Yujin Choi, and Jaewook Lee. Differentially private sharpness-an aware training. In International Conference on Machine Learning, pp. 27204-27224, PMLR, 2023.
13

---

Published as a conference paper at ICLR 2025
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. models unsupervised multitask learners. 2019.
Language
Maria Isabel Ribeiro. Kalman and extended kalman filters: Concept, derivation and properties. Institute for Systems and Robotics, 43746))3736-3771, 2004.
Carsten W Scherer, Christian Ebenbauer, and Tobias Holicki. Optimization algorithm synthesis based integral quadratic constraints: A tutorial. In 2023 62nd IEEE Conference Decision and Control (CDC), pp. 2995-3002. IEEE, 2023.
Li Shen, Congliang Chen, Fangyu Zou, Zequn Jie, Ju Sun, and Wei Liu. A unified analysis of adagrad with weighted aggregation and momentum acceleration. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp- 1139-1147, PMLR, 2013.
Qiaoyue Tang, Frederick Shpilevskiy, and Mathias 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, pp. 15276-15283, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). arXiv preprint 1. 2020.
James Vuckovic. Kalman gradient descent: Adaptive variance reduction in stochastic optimization. arXiv preprint arXiv:1810.1222 2018.
Eric A Wan and Rudolph Van Der Merwe. The unscented kalman filter. Kalman filtering and neural networks, pp. 221-280, 2001.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, 2018.
Bao Wang, Quanquan Gu, March Boedihardjo, Lingxiao Wang, Farzin Barekat, and Stanley J Os- her. Dp-lssgd: A stochastic optimization method to lift the utility in privacy-preserving erm. In Mathematical and Scientific Machine Learning, pp. 328 351. PMLR, 2020a.
Haoqian Wang, Yi Luo,, Wangpeng An, Qingyun Sun, Jun Xu, and Lei Zhang. Pid controller- based stochastic optimization acceleration for deep neural networks. IEEE transactions on neural networks and learning systems, 31012)55079-500 2020b.
Wenxiao Wang. Tianhao Wang, Lun Wang, Nanqing Luo, Pan Zhou, Dawn Song, and Ruoxi Jia. Dplis: Boosting utility of differentially private deep learning via randomized smoothing. Pro- ceedings on Privacy Enhancing Technologies, 4:163-183, 2021.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd international conference on artificial intelligence and statistics, pp. 1226-1235. PMLR, 2019.
Greg Welch, Gary Bishop, al. An introduction to the Kalman filter. Chapel Hill, NC, USA, 1995.
14

---

Published as a conference paper at ICLR 2025
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma. Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gug- ger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-art natural language processing- In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38-45, Online, October 2020. As- sociation for Computational Linguistics. URL https: //www///www///////.///////// aclweb. owg/anthologyy. 2020 smnlp-demos. 6
Yilin Wu, Qian Zhang, and Zhiping Shen. Kalman filtering with multiplicative and additive noises. In 2016 12th World Congress on Intelligent Control and Automation (WCICA), pp. 483-487.
IEEE, 2016.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2021.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive meth- ods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objec- tives. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 2017.
Xinwei Zhang, Mingyi Hong, and Nicola Elia. Understanding class of decentralized and federated optimization algorithms: A multirate feedhack control perspective. SIAM Journal on Optimiza- fion, 33(2):652-683, 2023.
Xinwei Zhang, Zhiqi Bu, Mingyi Hong, and Meisam Razaviyayn. Doppler: Differentially private optimizers with low-pass filter for privacy noise reduction. arXiv preprint arXiv:2408. 13460, 2024a.
Xinwei Zhang, Zhiqi Bu, Steven Wu, and Mingyi Hong. Differentially private sgd without clip- ping bias: An error-feedback approach. In The Twelfth International Conference Learning Representations, 2024b.
A ADDITIONAL DISCUSSION
A.1 BACKGROUND ON KALMAN FILTER
In this section, provide introduction and derivation of the Kalman filter. Kalman filter is introduced in (alman 1960) and widely used for control systems in accurately estimating system states with noisy observation and known system dynamics. Kalman filter assumes the system is linear (time-invariant) system:
0, A0 U1 + V
(System update)
1b CO, + Wt:
(Observation)
where A, C are known matrix, and V. N(O, W. NN1 NN,,w) Ew) are independent white noise following Gaussian distributions with known covariance matrices Σv, Ew, and u, is known input signal. The goal of the Kalman filter is estimate 6, with the observation of th, with the least mean-square error and serves as the Best Linear Unbiased Estimator (BLUE) (Welch et al. 1995).
Derivation: First, we denote the estimation of 0, as 0,, and the covariance of 6, 0 as P. E[(O, (e, e,)"] Then, based on the knowledge at time / - 1, the system dynamics give an unbiased prediction: and its covariance
0 f-j-1 = AO, + u,
(11)
P E[ ( AP + Ey.
AP,
(12)
With Osjt-1, we have an (unbiased) prediction of the observation deec-11 = C0 at time - 1.
At time I, by observing t/, have the prediction emror Atb, 1/. 1//1111 1/. CO
15

---

Published as a conference paper at ICLR 2025
Since the system is linear, would like to use the prediction error to correct the prediction:
0, 0 1|--1 + K, K - -I- (
(13)
The goal of the Kalman filter is to minimize the mean mean-square error: mink Ei 0/ll1, which is equivalent to minimizing tr (). From the definition of 0,, we have:
P. E (0: 0,)_
E[(O; - K + (1- K, C) (1- - K, + (1 (1,K,
B[(O, -
01((-) (.w,) 0 2/1-1 K.C(O, 0c((-1) K.w:)]]
= Prtt-1 K, C, - (K, 1) + (CC 1 C + Ew K,
Taking partial derivative to the trace of P. with respect to K,, and set it zero, have:
@tr(P,) 0K, 2(CP)))1) +(CCPt
K = =0,
which gives
= Pep P (CP CTCP 1 + E.w)
(14)
Substitute K, back to Pt, we can simplify
P. P||11 (/CP,/11
(C(C Ew]
(15)
dt-1 K,CP f|--1 (I K,C)
Combining
together, we have the update of the Kalman filter:
p e|r-1 AO,-1 +
P f/--1 AP. AP +
K, = Pate-1C' ( i C + --
(CP/)e1
0: (I - K,C) + K,tb
P. = [I-K,C)P:H-- :/--1.
Variants of Kalman filter: Kalman filter is designed for estimating the states following linear dynamics and achieves optimal performance, i.e., gives the smallest mean square error of the esti- mation when the system linear (Welch al. 1995). Extended Kalman filter (EKF) and unscented Kalman filter (UKF) are developed to deal with non-linear systems. EKF linearizes the non-linear system each step and performs the Kalman filter on the linearized system (Ribeiro) (004), while UKF takes the effect of the system non- non-lineari to the noise distribution into consideration and ap- plies the unscented transform on the noise distribution and applics the Kalman filter on the system and the noise distribution (Wan & Van Der Merwe 200T). Other extensions of the Kalman filter have been developed for special cases, including multiplicative noise and noisy input u, (Wu et al., 2016).
A.2 OTHER SYSTEM DYNAMICS FOR DPSGI
In this section, we would like to discuss other possible formulations of the system dynamics for DPSGD to apply the Kalman filter.
Optimization variable and gradient version 1: Other than only using the gradients' dynamics in the main paper, we can construct the dynamic system with both the optimization variable x and the gradient Fx)) as its states (Vuckovic) 2018):
X1+1
-
0
1[
X F
]
[
(x(x+))
I
Y1 = Xt.
However, this dynamic is inaccurate the dynamics of the gradient are simplified to F Fx;)). Although the update can further incorporate with the momentum methods, i.e., by adding momentum m, into the system, it fails reveal the actual dynamic of the system.
Optimization variable and gradient version 2: Instead of treating the gradient as a constant, we
assume the Hessian H constant and utilize the Hessian reveal the gradient dynamics:
X++1
T/H
1/l
1
X
r/W,
1
0
X
0
H
-H
(x
0
16

---

Published as a conference paper at ICLR 2025
Yt X2-
This system is more accurate in evaluating the gradient at the cost of using an extra X state and a larger transition matrix. For non-linear problems F F(x), where H is not constant, extended Kalman filter and replace H with H, that linearizes the problem at each step t.
apply the
Gradient and Hessian: In work (Bittner & Pronzato 2004). the dynamics of the gradient and Hessian have been used to construct the system:
V FX
AX, I
F ].
h++1
O
h,
gr
(x;)) + Wt:
Ha,a] with E [O,...,d represents the entries in the upper triangular part of the Hessian matrix. AX, is constructed such that AX,h, = (xxx++1 -x.). The system treats the Hessian matrix as a constant matrix (i.e., h441 h,), and the transition matrix is of size (d + d(d 1)/2) d + d(d 1)/2.
where h, [1 H4itjs...
Although there are different ways to construct the Kamlan filter for gradient noise reduction, the above systems are not implementable in practical deep-learning applications. Because the transition matrices of these systems are non-diagonal, the Kalman filters have non-diagonal gain K₁ and P.- Therefore, the matrix inversion operation is unavoidable when Kalman filters are implemented based on these systems. The computation complexity for the matrix inversion can be (dd) to Odd), and the memory consumption is (dd)) (dd) for storing the matrices of the Kalman filter.
A.3 ALGORITIM SIMPLIFICATION
In this section, we explain how the simplification proceeds from Algorithm to Algorithm that updates of Algorithm is
Recall
Br|r-1 = - + H, (X: x1-1)
(Prediction)
P P = Pt-1 + H En
K, = P C
T (Ew + E[C,] (EeS, P,tr-1) E[C,] Σx)
g: = gt)-11 + Kg - E(Cr(
(Correction)
P. = (I - K, E(C,,))PHtLL
S, = Egg.gil
where B EςEB, clip (Vf(x;))) C) w., We apply four steps of simplification, including
1. Replacing random C, with constant Ia-
2. Use finite difference estimate H,d,-1-
3. Replace Σn with diagonal matrix Id Ey with LeI and Ew with o Id.
4. Use fixed filter gain sI.
Step By replacing C, with La, and Ec 0, the update becomes
gi g--1 H, (x, xx-1)
(Prediction)
P P Pt-1 Σh + Vi
K, Pr|r-1 (Ew + P Ppje-1 Σh)
B1jt- Kg (((-1)
(Correction)
P. (I- K,) 111-1-
Step By using the finite difference estimate H,d, the prediction step becomes: 1
Vf(x: + 7d:-1:)) Vf(x(E)
gdj-1 g:-1 B
(Prediction).
EEB,
Step By replacing E's with diagonal matrix o I the update becomes: V/(x, + 77,,13. (x(x;
B 8.-1 Σ
(Prediction)
EEB.
17

---

Published as a conference paper at ICLR 2025
Prjt-1 Pt-1 +0 ov. P
2
r|t-1 Prjt-
Prp
Pt-1 + 04 02
kt Pijt-1 + ow - 0
K, kela
Pt-1 + ow +
g: Bijt-1 (g -i((-1)
(Correction)
Pt (1 Pe]p---1= (a
0 (P o +
Pt-1 + o t
Step 4. As discussed in the main paper, the update of kr Pt becomes:
k; Pt-1 + 0 + o²
P + ow + o
(o 0 +
Pt Pr-1 + o + o
Therefore, solving the recurrence relation of the sequence (pe). we have converges to Poo V0 +0 403
p. to with rate oa Poo pottatt
k, converges to hoo
20 +30 La (40g o0 30p,1
202 +o? (0 (1o (100 +o? -33
0.9
Value
0.8
0.7
0.6
6
Stop
Figure 3: Convergence of kt: Pt-
Therefore, define ń h2 and replace k, with K, and the update becomes:
V Vf(x: + 7d1-1:E) - fx(x(()
Sijt-1 1 +
(Prediction)
B
SEB,
ğ: 1 k(gr B()(-1)
(Correction)
Rearrange the terms, we have:
Vf(x, 7d:-1: - v)(x;()
13) Σ
g: = k)gg
kg. +
EER
= =1 k) Kg: with
K
Vs(x: + (d)- (x(ri)
g: = g +
B
SEB.
1
Ki V + (d.11: (1 -1-1- V v((x;:5) + w.,
1-x
B
Ki77
ney
SEB,
where we substitute
B Σçes, clip (vf(x;E)) C) +w., Then, by privatizing g, and rename
it as ge, we have:
1- --- dd.1;:)) + (1-1 1-
g: Σ clip
Vf(xx:)).) w.
Ny
SEB,
g. = (1-K)g: Rgi which is the update Algorithm (Lines 5 and 6).
A.4 CONNECTION BETWEEN DISK AND NAG AND STORM
Algorithm 3 has an implicit connection to the (unified) Nesterov Accelerated Gradient (NAG)
method (Shen et al. 2023: Sutskever al. 2013) and the Stochastic Recursive Momentum
18

---

Published as a conference paper at ICLR 2025
(STORM) algorithm (Cutkosky & Orabona 2019). The update of (half-shifted) NAG can be written as (Sutskever et al. 2013):
= pm 1 Pxx: (mm-1)
(16)
X++1 = X m.
and the update of STORM writes (Cutkosky & Orabona 2019):
my = (1 a) a- + f
a](V (xx,, vf(x
(17)
X++1 X₃ 7
In comparison, Algorithm [] by letting the update of OptimizerUpdate be SGD, and assuming
clipping is inactive, w. 0, i.e. without DP, + co, the DiSK becomes:
8: = (1 - x)
K
v f(x, + +
1 1-
B
KrY
Key
EEB,
= =11 - K)
R
Vx(xxt) +
1-
(V + 7d(1i))) 100--ff(cee v((xx()) (18)
B
BY
SEB,
EEB.
Xt+1 X2 T/:
Comparing the above updates, we observe that (6) and 17 are two special cases of (18) with
specific choices of the parameters. Specifically, by letting 7 I-n 0, = K; 1 == μ, N,
we have I- = 0. and the update of 8. becomes g: --gr-1 + V/ - BB) and DiSK
N7
becomes NAG; on the other hand, by letting = -1, = a. B = 1, we have x + 7d,1 = a (1
X, (x,- x X 1, and the update g: becomes g: = (1 a g +
a) {x) V 1x: {)), which matches the update of STORM. From this discussion, we see that NAG and STORM, two algorithms for accelerated gradient and variance reduction, respectively,
can be unified by DiSK, an algorithm based on Kalman filtering.
With this discussion, we observe that the key difference between NAG and STORM is the choice of y. When 7 O, the algorithm is close to NAG, which focuses on "exploring" and "accelerating". When y < 0, the algorithm is close to STORM, which focuses on "exploiting" and "reducing noise".
B PROOF FOR SECTION
In this section, we provide detailed proof for the results in Section
We will use the following incqualities in our proofs:
(a, b) - 2a |a
2 a 2
|bll
(19)
la + b1|2 < (1 + a:) ||a]| + (1+1/a)
(20)
In the following sections, we use E, to denote the expectation conditioned on all the information
before iteration t. To prove Theorem 2 we first provide the following lemma to bound the difference
between g: defined in Line 6 of Algorithm and VF(x).. Let us define A, vF(x.) gc. We have:
Lemma
Assume AL
A and A3 holds and choose C 2 2(1-x) G, we have:
E2 A
< (1 x:) (1 + 4ny 1,2 + 11 + 7 (K + 2n M,)) 1|
+ 2n k²)² (2 + |1 11 71 M,) [F
+ x²
(2 71)
+ do
(21)
B
where define M.-
( /2+1/
B. PROOF OF LEMMA II
First notice that when choosing C > (1+21=n))
G, the clipping operation is inactive. By the
update of g. in Line 6 of Algorithm 3 have:
E, |
19

---

Published as a conference paper at ICLR 2025
K
Ex (x())) - -1--))---1
(x(x,,
k..
B
SEB.
1-K K
7 v((x)iE))
B
SEB.
Ee
|1(1 x)
(VF(x))) VF(x:-1)) (1- (VF(((( 11-1)
3/ Σ V)(x),)) We
1
+
(x(x))
B
EEB.
K
(Vf(x + 7 - vf(x(;()) |
BB
EEB,
(b)
E x)
VF(x,) - (F(x B
Σ
(V -V((x::)--(((x-111))1) v(((x-)iE)
EEB.
D=
(1 x)
+
(F(x)) 1
Σ
(((x)(E)
-WW,
B
SEB.
DD
(1 k)
B Σ
1 + (f(x--1:))
vx(x))))
y
EEB,
( (1 +
B/
+ | (D, Ae-1)
+ 1(11 -
2(1 E, Dz) 1,)"0,00000010111===0001)1)-11-0
(1 (1))))))))))))
(
x (1 x) + 11
E. | 71
+ -1- x1 +1 x2² +1++ E, D2
x
+ x1=x)2 1+ [1 7
+
E, | 2 + x do
(22)
K [ +
where (a) we add and subtract (1 x) (x) and rearrange the terms; (b) adds and sub-
tracts 1-x
B Eges, (V vf(xx-1:E)); (c) directly expands the square and use the fact that
[.[w]] = and is independent of other terms; and in (d), we notice that E, [ O, EE, [D]]
0, so the first two inner products are zero, and we apply (99 to the other four inner products, with
a = K| + 71, 1, [1 + yl. respectively. Next, we bound each term separately. For Eg[l D2 || we
have:
D E,
vF(x)) - VF(X Σ EEB
(x(())))) v(((x-
B
96 E,
(Vf(x:E)) (x(()))))
(23)
B
EEB.
(b) <
127 111
21 VV 1))
20

---

Published as a conference paper at ICLR 2025
where (a) uses the fact that E E|| - X[X]| < BIXI with VF(x)
VF(xx-1)
E EeEB, (V(()))) - ff( E))l: (b) applies and (c) adds and subtracts (F(x;11),
and applies (20). For B, D2 1. we have:
1 Σ (x(x,)
o SGD B
D2ll E. (x(x))
(24)
B
EEB,
For E, D3l1), we have:
E, = E.
1
Σ
1 77d-11)) + VS(((-
1 1 7
V V (xxi:E)
B
SEB+
(a)
+
v (x(
SEB,
1+7 (x(x)- - 1+7 V E)
7
M0
2
1
2
[z 7 1;)
V fx: +)
7
7
EEB,
+
2
Σ
1 1
V fx
1+1 7
(xx: E)
2
B
?
ŞEB,
40 2L2
21 + 7)
||x: + +dd---111 X 111
||x xr|1
722
72
(6) 4L + 30
| ||
72
1 812 + ?,p (I + 1112 11
(x
(25)
72
where (a) applies Jensens' inequality to 11-11, and we add and subtract (x (b) apples
20); (b) uses the fact that d: X Xt-1 = -17g. and (c) adds and subtracts (x(x,
and applies (2).. Plug in (3 (25 to [2).. we have:
E2 A S R)
2 (2 + E. DI + (1 x) x))(11 (1+ +
11 + n² do
+ +2 + [1+ E. D + (1 x)² 1+ |1+ x|1+>// E, |
< (1 x) x)²
+ 1 (16 27,) ||A--1
+ 2 (2 x2 7 M, |z
+x² (2 (2+11+ |1+
71)
SCD + do
(26)
B
where we define My : (1 412+1/
This completes the proof of Lemma
7²
B.2 PROOF OF THEOREM 2
Now, we are ready prove Theorem 2 By choosing C 2 G(1 2(1-x)), the clipping is inactive. Recall that from the update rule, we have
xy
E g
(1 x) + (V + (1 (1-x) (L-x))(F(())) - (x
(27)
F (1 - A.-
Then, by A we have F(-) is also L-smooth, so it satisfies
I. Fly) < F(x) + (VF(x), x) 2 ly x||2.
21

---

Published as a conference paper at ICLR 2025
Substitute y = X(+1; X2 the above relation and take expectation over the randomness in iteration t, we have:
TfL E. l1@:11
E. (F((x+t)) Fxx,) S (V.
11 + 1711 1)) (VF (x+), ),-1) + T²L
R2 ||::1 11
2
(V )1 + x)) k)
|VF(x,)] )1² + 17(1 _ -x)
||||-1|
+
E, |
2
2
2
7711 k)
|VF((x)] )1( + 17(1 - R)
|V+((())] )1
||
2
2
T/
+
E, 11:
Fx(x), + VF(x))11
2
(e)
2 (1 + K L)
(xt 2| + 1/(1 - xx)
|| + L |A.l
(28)
2
2
where (a) substitute 27 : (b) we add and subtract F((x)) to the last term and (c) applies (00) to
the last term.
Define Le == Fxxx) + 3 (| 11? we have:
[x[4++]] - Li
(7(1 + - L.)
V F (xx) (3 711 - 13)
|A,-1 11 LB) 11
2
2
(4)
n11 + K 2
[VF(x))]' )11 - (B 71l
R)
||
2 + (8 + 100+n" L) - -x)
2
+ 41' +11 + 7l (K 2n²² M,) 1|
(2 11 + 110 SGD + do
+ (8+
B
+ +2(3+ - -k))T,,,7 (2 + +
M,) | |VF(
= n11 + T.)
- (8+ |,
2
711
R)
8
11
2
(2 |1 11+1100000 dobp
+ (8 + 7² L)n²
(29)
B
where (a) applies Lemma and (b) rearrange the terms. By choosing
1
n
21(1 + 2(1 - kx) |1 + 1-
V 1T
7/ (Ks + 277
8 11 - =11- (2+22(
1= 21,2,,,))
we have:
(111 + k6 1 -1 > O,
2
1 1- - kk)= 1 ||1
> 0,
(30)
B 11 - ki)
(1 -1 (1 -
+ + (k+ + 2 2 0.
2
Average from
= 0 to T - and rearrange the terms, we have:
(x)F(( 2(Lo - E[[r+1)) + 2(3 + 172 L)R? 1=
+ |1 + 71)03a + do
MinT
Min
B
2(F(x)) + 3 (V(xx)) FP)) 2(B + 12 L)
(2 1 + 7 100 DO doir (31)
Mjn
Mi
B
22

---

Published as a conference paper at ICLR 2025
where we define M1 - ===+
and in the last
inequality we notice that Lr+1 F(xx++1 |Ar 1 F* and Lo F(xo) + V F (xx))l
as we initialize go = 0. This completes the proof of Theorem
On the choice y -1. From the above proof, we see that in Appendix B.1 22 (c). we directly
apply (19) to upper bound the cross-product terms by positive terms for the worst case, which results the optimal choice of 7 -1. However, the inner products may be smaller than zero some cases, making 7 -1 sub-optimal in practice.
C ADDITIONAL NUMERICAL RESULTS
C.1 EXPERIMENT DETAILS
The code for the experiments will be provided online. We use PyTorch as the code base and the FastDP package (Bu al. 2023 to privatize the optimizers. We use the Renyi differential privacy (RDP) accountant in the Opacus and FastDP packages to numerically calculate the required injected DP noise the gradient for fixed 8)DP budget. A detailed derivation of the RDP accountant can be found in Wang al. (2019). The Algorithm is implemented as a PyTorch opti- mizer, which can be easily combined with any training scripts based on PyTorch. The modification is minimum:
Coding:
from XFOptimizes import wrap_optimizer
define base aptimizer
optimizer wrap_optimizer (base_aptimizee kappa, gamma)
5
in training loop:
def closure() # warp the less and backward computation loss - model (input)
lcss.backward() return loss
10
loss = wpt.miier. (closure)
The link to the full code of the experiments can be found https://anonymer 4oper. Alternative implementation in Opacus can be found at htt httpp//hww.aaaaccccc///////////a
Sclence/r/KalmanDP-
Hardware: All the experiments except the ImageNet-Ik 1k dataset are rumning with one Nvidia A40 (48GB memory) or one Nvidia V100 (32GB memory). The experiment on the ImageNet- 1k dataset is running on one Nvidia H100 (80GB memory) GPU. The training time varies for different tasks depending on the data size and model size.
Training method: We use gradient accumulation to deal with the large batch size and use learning rate warm-up for 1/20 the training steps when training from randomly initialized weights. We also the Cosine Annealing learning rate scheduler (Loshchilov & Hutter, 2022), which gradually decreases the learning rate.
C.2 CHOICE OF HYPER-PEE EYPER-PARAMERN PARAMETERS
The main aaper-parameter in the algorithms are: epoch E. batch size B, step size 7) clipping threshold C, Kalman filter parameters K, and In all experiments, we fix the clipping method as automatic clipping used in Bu et al. (2024), i.e., clip (Vf(x;)), C*) vf(x || and set
C' == 1 for all experiments. We fix 8 = 1/1 for reasonable privacy notions. This choice matches or is tighter than the SOTA results using = 1/2N or 1/N1. Li ct al. 2021 Bu et al. 2024 Yu
al. 2021 We list the 8's used in the experiments in Tab.
For each set of experiments, we conduct a grid search on the hyper-parameter E, B, 17 and choose the optimal ones for the DP optimizer without DiSK based on the test set. The search grids of each hyper-parameter are listed in T
Then, fix F,, B.n and conduct the ablation study K, 7 as shown in Figure
23

---

Published as a conference paper at ICLR 2025
Table 2: Search grid of the CV pre-training experiments, the optimal
are in bold.
Search gird CIFAR
MNIST
ImageNet
E
(1, x 20
{1,2,3, 4] x 40
{3. 4} x 40
B
(2.5) 10
10.5,1,2,80 x 103
{5, 10) 10
7
{3,
2,, 0.1) X 10
(1.3,5, 7, 10 999.9,8,7,6,550 x 10-1 (0.2, 0.3, 0.5, 1,2,3, 1-N
(10,3, 0.33, 0.1) 10
(0.7) (0.5)
(0.7) {0.5)
C.3 ADDITIONAL EXPERIMENTS ON CV TASKS
Training different models from scratch: We additionally train the WRN-16-4 and the ViT-small models on the CIFAR-I 10 with randomly initialized weights, and the test accuracies during the train- we can see that DiSK consistantly outperforms
ing are shown Figure for From Figure the base optimizer.
75
65
Test Accumey
95
Text Accuncy
45
35
KF-DPAdam
KF-DPddm
KF- D--Aaddmm
DPAdam
DPAdam
DPAdam
15
15
15
20
40
60
30
20
20
40
60
80
(a) 5-layer CNN
(b) WRN-16
(c) ViT-small
Figure 4: Test accuracy of pre-training 5-layer CNN, WRN-16, and ViT-small on CIFAR-I0 dataset with and without DiSK for fixed privacy budget = 4.
Besides training from scratch, we also compare the performance of fine-tuning pre-trained ViT-small model the CIFAR-100 dataset. The results for different shown in Figure [5] For fine-tuning on the complex CIFAR-100 dataset, DiSK still improves the performance compared with DPAdam, and has less performance drop under large DP noise.
Fine-tuning on CIFAR-100:
We conduct comparisons with existing approaches for improving DP training performance. In Figure 6al we train linear regression model with syn- thetic data and compared the performance of Noisy GD, Noisy GD with DOPPLER (NoisyLP), and with DiSK KFo We inject Gaussian noise with different variances into the gradient and compare the final performance. We observe that DiSK has the lowest regression loss under all noise levels, indicating that the Kalman filter performs better in noise reduction than the Low-pass filter. In Figure 6b) we compare the test accuracy of different methods, including DOPPLER (Zhang al.) 2024a) and DP-FTRL (Kairouz et al., 2021; Choquette-Choo et al., 2024) on the CIFAR 10 dataset training the WRN from scratch. We observe that DiSK significantly outperforms the SOTA algo- rithms on all privacy budgets. As discussed Section
Comparison with existing methods and SOTA:
DOPPLER refers to the case that DiSK only
90
20
85
16
Accuracy Improve
Test Accuracy
80
KF-DPAdan
12
DP Adam
Improvement
70
65
0.5
Figure 5: Fine-tuning ViT-small on CIFAR-100 with different e. provement of DiSK.
The green line indicates the im-
24

---

Published as a conference paper at ICLR 2025
0.12
No NoisyLP
0.09
Test Aecurayy
NoisyKF
0.06
60
KF-DPAdam
DPAdam
0.03
DRAFTRL
LP-DPAdam
0.01
0.02
0.03
0.5
8
Synthetic data
(b) CIFAR-10
Figure 6: Comparison with existing approaches. a) Kalman filter and low-pass filter, b) Kalman filter, DP-FTRL, and low-pass filter.
36
Velidation Accuracy
30
KF (F-Deetal al. 2022)
2022)
10
20
30
40
50
80
70k
Steps
Figure 7: Comparison with the SOTA approach in De et al. 2022) the ImageNet- 1k dataset.
estimates gradient at one point x; instead of performing weighted average of gradient estimated at two points x,, X2 + -d;-1 before clipping. The results Figure 6a and Figure 6bb indicate that the weighted average before clipping may be more important (i.e., Y is more important).
Comparison with SOTA on ImageNet: formance of DiSK with SOTA result training from scratch the ImageNet-1k dataset in De et al. (2022) The result is shown in Figure 7
Additionally, we conduct experiments to compare the per-
We note that the reported test accuracy in the et al. (2022) 32.4% for privacy level = 8. However, proved in their GitHub repository and hence we re-ran their experiment using the new accountant obtain baseline. We kept all their options on, including group normalization, larger batch size. weight standardization, augmentation multiplicity, and model exponential moving average. In addition, also follow their normalized clipping strategy, i.c.
noticed that their accounting procedure has been im-
clip (V
C min
Their updated code results in 36.35% 35% validation accuracy and the test accuracy of 33.56% (as the SOTA result). In comparison, adding DiSK on top of their method results validation accuracy of 40% (3.7% improvement) and a test accuracy of 36.89% (3.3% improvement). This sets new SOTA result for differentially private training on the ImageNet- 1k dataset.
We conduct ablation studies on the choice of the hyper-parameteri of DiSK, specif- ically, how K, 7 impact the algorithm performance. In Figure g we plot the accuracy on different combinations of (x, 7), and (x, e). We observe clear trend of performance change for different combinations of the parameters, and there is an optimal choice of k, for different e's.
Ablation study:
C.4 ADDITIONAL EXPERIMENTS ON NLP TASKS
In this section, we provide additional results for NLP tasks.
25

---

Published as a conference paper at ICLR 2025
70
0.6
53.9
59.5
64.2
67.9
65
0.6
42.9
67.1
67
65.5
65.9
0.7
50.6
65.
74.9
68.9
66.8
63.5
65.7
50.8
56.2
60.2
65
60
0.8
69.2
74
69.5
67.7
66.6
66
63.7
55
1 0.8
48.3
54.1
59.6
63.7
67.7
55
0.9
69.4
68.
67
66.5
66.6
66.
66
50
45
63
63
63
63
40
42.8
48.8
53.8
59.6
633
45
0.2
0.3
0.5
2
0.5
2
(a) (K.
6=
(b) 7x=
Figure 8: Test accuracy for different combinations of the hyper-parameters when training CNN on the CIFAR-10 dataset.
Parameter-eflichine fine- tuning on GLUE. We fine-tune RoBERTa-base and a RoBERTa-large model from the Huggingface checkpoints the GLUE dataset. We follow the same training scripts choices of B, E on the tasks and use rank r = 16 for LoRA. We choose 0.7, Y 0.5 for DiSK. The results are listed in T With privacy budget 6.7, DPLoRA with DiSK significantly outperforms SOTA results with vanilla DPLoRA on all tasks.
in Bu et al. 2024) on the
Table 3: Test accuracy of fine-tuning result on the GLUE dataset.
6=1
c= 6.7
Algorithm
MNLI
QNLI
SST2
QQP
MNLI
QNLI
SST2
QQP
RoBERTa-base
AdamW (c oc)
87.6
92.8
94.8
91.9
87.6
92.8
94.8
91.9
Lora (e oo)
87.5
93.3
95.1
90.8
87.5
93.3
95.1
90.8
DoLa
81.1
85.5
90.9
83.9
83.5
87.4
91.5
85.7
KF-DPLora
84.7
90.3
92.9
87.8
85.9
90.5
93.1
89.0
RoBERTa- large
Adam (e oc)
90.3
94.7
96.4
92.2
90.3
94.7
96.4
92.2
Lora 00)
90.6
94.9
96.2
91.6
90.6
94.9
96.2
91.6
DPLora 85.6
89.5
90.9
85.1
87.8
90.8
94.3
87.4
KF-DPLora 87.9
92.5
95.2
88.2
89.4
92.6
95.4
89.6
Fine-tuning GPT-2 on text generation tasks. We fine-tune a GPT-2-small model with 137M two text generation datasets, E2E and DART.
parameters from the Huggingface checkpoint We follow the same training scripts in Li et al. (202I) on the hyper-parameter choices of 7, B, E on the tasks and choose dataset are given in Table[4] and the results for the DART dataset are Table With privacy budget 3, 8, DPAdamW with DiSK significantly outperforms SOTA results with vanilla DPAdam W on all metrics.
0.7, 7 0.5 for DiSK. The results different metrics for the E2E
Table 4: Performance of fine-tuning gpt-2 on the E2E dataset. (All metrics are higher the better)
Algorithm
BLEU (%)
ROUGE-L (%)
METEOR
NIST
CIDEr
A (e o0)
69.46
71.36
0.461
8.780
2.422
DPAdamW W (c 3)
61.52
65.87
0.417
7.071
2.167
KF-DPAdamW (c
68.35
70.23
0.456
8.636
2.399
DPAdam (c 8)
64.99
67.34
0.425
8.387
2.192
KF-DPAdamW (c 68.73
70.58
0.460
8.697
2.463
Vaceboolal//roberta-larre
http:s//oaggnnnaee...e///eaaaoom ty/mm
26

---

Published as a conference paper at ICLR 2025
Table 5: Performance of fine-tuning gpt-2 on the DART dataset. Val. Perp. stands for validation
perplexity. (All metrics except Val. Perp. are higher the better)
Algorithm
Val. Perp. 4
BLEU (%)
ROUGE-L (%)
METEOR
NIST
CIDEr
AdamW (c = oc)
0.921
44.56
58.66
0.379
8.733
2.773
DPAdamW 3)
1,427
33,96
52.38
0.310
6.090
1.864
KF-DPAdamW
1.149
41.01
57.53
0.359
7.949
2.553
DPAdam W 8)
1.362
35.30
54.58
0.320
6.365
1.995
KF-DPAdamW (c- 1.102
42.12
58.11
0.364
8.111
2.628
C.5 IMPROVEMENT OVER SOTA
In the following Table provide list of the experiment settings where algorithm outper- forms SOTA results. The paper that provides the SOTA results is cited for each setting, or the same the line above. We observe that DiSK provides SOTA for CV datasets, including CIFAR-10, CIFAR-100, and ImageNet-lk, and NLP datasets, including GLUE (MNLI, QNLI, QQP, SST-2), DART, and E2E.
Table 6: Tasks DISK improves SOTA, PT=pre-training, FT=fine-tuning.
Dataset
TASK
Model
Ours (%)
SOTA (%)
CIFAR-10
PT
CNN
0.5
59.7
N/A
CIFAR- 10
PT
CNN
2
68.8
67.2
Tramer & Boneh 2020
CIFAR-100
PT
WRN
0.5
14.7
N/A
CIFAR-100
PT
WRN
1 22.7
14.1
(Boo al.
2024
CIFAR-100
PT
WRN
2
30.0
21.5
CIFAR-100
PT
WRN
4
37.1
33.3
CIFAR-100
PT
WRN
8
42.0
40.6
CIFAR-100 100
FT
ViT
0.5
83.49
78.3
Mehta
2023
CIFAR-100
FT
VIT
85.36
81.8
Bao et al. 2024
CIFAR-
VIT
2 86.77
83.5
CIFAR-100
FT
VIT
4
87.56
84.5
CIFAR- 100
FT
ViT
8
88.49
84.6
ImageNet-
PT
ResNet-50
8
36.89
33.56 De al. 2022
MNLI
FT
RoBERTa-base
84.7
83.2 (E 3)
[Bu et al. 2023
QNLI
FT
RoBERTa-base
90.3
87.4 (E 3)
QQP
FT
RoBERTa-base
87.8
85.8 (E 3)
SST-2
FT
RoBERTa-bas
92.9
92.3 (C 3)
MNLI
FT
RoBERTa- base
6.7
85.9
83.8 (c 8)
Bu et al.
2023
QNLI
RoBERTa-base
6.7
90.5
87.9 (E S)
QQP
FT
RoBERTa-base
6.7
89.0
86.6 (E S)
SST-2
FT
RoBERTa-base
6.7
93.1
93.0 E 8) Li Li al
2021
MNLI
FT
RoBERTa-large
87.9
86.8 Yu et al. 2021
QNLI
FT
RoBERTa-large
92.5
88.0
QQP
FT
RoBERTa-large
88.2
85.2
SST-2
FT
RoBERTa-large
95.2
93.1
MNLI
FT
RoBERTa-large
6.7
89.4
89.0
Yu al.
2021
QNLI
FT
RoBERTa-large
6.7
92.6
92.5
QQP
FT
RoBERTa-large
6.7
89.6
88.4
SST-2
FT
RoBERTa-large
6.7
95.4
95.3
E2E (BLEU)
FT
GPT-2
3
68.35
61.52
Li ct al. 2021
E2E (ROUGE-L)
FT
GPT-2
3
70.23
65.87
Bu al. 2024
E2E (BLEU)
FT
GPT-2
8
68.73
63.60
Bu et al
2024
E2E (ROUGE-L)
FT
GPT-2
8 70.58
67.53
Li al.
2021
DART (BLEU)
FT
GPT-2
3
41.01
32.33
Li al.
2021
DART (ROUGE-L)
FT
GPT-2
3
57.53
52.06
DART (BLEU)
FT
GPT-2
8
42.12
35.06
DART (ROUGE-L)
FT
GPT-2
8
58.11
54.57
27

---

Published as a conference paper at ICLR 2025
Table 7: The privacy parameter ö's used in our experiments and in SOTA results.
Dataset
Our
SOTA 8
MNIST
5.5 10 10-6
10-5
CIFAR-1O/
6.8 10
10
Imagenet- lk
1.9 10-7
X 10-7
MNLI
6.3 10-7
1.1 x 10-6
QNLI
4.8 10-7
9 X 10
SST-2
4.9 x 10-6
7.4 x 10-6
QQP
7.6 10
X x 10
E2E
1.2 10T6
1.2 X 10-5
DART
6.1 X 10
6.1 X 10
28


Reviews:
[{"review_id": "Vj1sLt9YNU", "reviewer": "Reviewer_pdcW", "summary": "This paper introduces DiSK, a novel framework for enhancing differentially private (DP) optimizers by applying Kalman filtering to denoise privatized gradients, producing refined gradient estimates with reduced noise interference. By simplifying Kalman filtering for large-scale tasks, DiSK maintains efficiency and improves privacy-utility trade-offs, achieving significant performance gains over standard DP optimizers like DPSGD. Experimental results on vision and language tasks demonstrate DiSK's superiority under equivalent privacy constraints, achieving state-of-the-art performance across multiple benchmarks.", "questions": "I’m very impressed with these results and somewhat surprised about why they work so much better than existing methods. In developing new methods, or building on top of this, what parts of this method can be extended - what are they key things that differentiate this from existing methods that don’t work as well. This may seem a bit naive, but my question is effectively - based on how big of an improvement this algorithm produces, what should next steps focus on?\n\nComment: I did not go through the utility proofs in great detail and could have missed something there.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Empirical results are very strong and very significant. Computational costs (e.g. time/memory/parallelizability) of the method are quite good too. You mention this in theory, it may be good to make even a small empirical statement about this as well.", "weaknesses": "Why don’t people use Kalman filters for non-DP optimization? I don’t see why the same tricks you employed to not incur d^6 computational costs are not applicable to other non-private settings. \nThis feels like an important consideration to understand for contextualizing the empirical claims made in this work", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "z7J6LADDfs", "reviewer": "Reviewer_Nhmw", "summary": "The paper proposes to use the Kalman filter for denoising gradient computation in differentially private optimization. Specifically, the Kalman filter views the gradient vector as the state and derives the system update equation based on the Taylor expansion of the gradient. The observation is then written as Gaussian perturbation of the gradient. However, naive incorporation of the Kalman filter involves computing the Hessian matrix, which is computationally infeasible for large models under DP constraints. To address the computational challenge, the authors proposed to use a simplified Kalman filter with noisy input, multiplicative observation noise, and diagonal covariance matrix. Theoretical analysis shows that the proposed algorithm satisfies $O\\left(\\sqrt{d/T}\\right)$ convergence rate for smooth loss function with bounded per-sample gradient and bounded per-sample gradient variance, which has a constant factor improvement over DP-SGD under certain assumptions. Experiments validate the improvement of the proposed algorithm compared to DP-SGD and DP-Adam over a variety of DP vision and language tasks.", "questions": "1. In Algorithm 2, are $\\mathbb{E}[C]$ and $H_t$ data-dependent? If so, does Algorithm 2 satisfy differential privacy?\n\n2. In Figure 2 (b), both the proposed algorithm KL-DPAdam and the baseline DP-Adam seem to achieve lower test accuracy than the SOTA results in De et al. 2022 Figure 1 (a). Does this contradict the claim that the proposed algorithm enables improvement compared to SOTA?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper proposed an interesting way of viewing gradient update in differentially private training as a linear dynamics system. The proposed algorithm provides a novel and computationally efficient way of (approximately) incorporating the Kalman filter into DP training for denoising gradient.\n- Extensive numerical experiments that validate the effectiveness of the proposed method.", "weaknesses": "- The reason for the gain of the proposed denoising algorithm is not perfectly clear from the presentation -- could the authors elaborate more on (1) why does the Kalman filter (as described in Algorithm 2) effectively denoise the gradient observation? (E.g., what is the minimized objective under denoising), (2) what are the assumptions for the simplifications made in Algorithm 3 and why are the assumptions meaningful?\n- The authors mention that the algorithm performs better than all SOTA methods, including the DP-FTRL algorithm. However, DP-FTRL is also effectively a gradient denoising method that is proved optimal in terms of l2 error for releasing linear queries (gradient estimation in the context). Consequently, it is not very clear why the proposed Kalman filter method would be beneficial compared to another denoising method, and how much the improvement is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "ag15KDG27g", "reviewer": "Reviewer_j3TA", "summary": "This paper proposes using a Kalman filter to enhance the privacy-accuracy trade-off of DP optimizers. While traditional Kalman filtering introduces significant computational and memory demands, the authors provide a simplified approach that reduces these costs while retaining its advantages. Theoretically, they show that their method achieves better iteration complexity than DP-SGD by a constant factor. Experimentally, their method outperforms DP-SGD on various datasets.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper effectively applies Kalman filtering from control theory to improve DP optimization algorithms, presenting an interesting connection between DP optimization and control theory. \n- The algorithm improves upon the traditional Kalman filter and requires only a constant factor more space and computation than DP-SGD. \n- The method is versatile and can be integrated with various DP optimization techniques, not just DP-SGD.", "weaknesses": "- The privacy analysis of algorithm 3 is not clear to me. Is it possible to express $\\sigma_{DP}$ explicitly in terms of other variables? \n\n- While the conditions in Theorem 2 and Figure 8 offer some guidance on hyperparameter selection, the interactions between different hyperparameters ($\\gamma, \\epsilon$ and $\\kappa$) remain complex and unclear, making practical hyperparameter tuning challenging.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "XnUh9Eut6B", "reviewer": "Reviewer_PnV2", "summary": "This paper proposes DiSK. DiSK is inspired by an application of a Kalman filter to the DP-SGD process. While the Kalman filter includes computationally intensive steps and requires knowledge of some unknown matrices, the simplification steps result in DP-SGD with two seemingly small changes. The first is that the clipped gradient is computed from an average of the gradient at two carefully chosen nearby points. The second is a momentum applied to the clipped gradient before being passed into an optimizer.\n\nWith these changes, the authors prove an upper bound on convergence rate. The provable constant in the upper bound for DiSK is smaller than the provable constant in the upper bound for vanilla SGD. Although this does not mean that the paper proved that DiSK has faster convergence (a claim that should be fixed), it does suggest that DiSK would converge faster. The analysis suggests that the pre-clipping averaging step may be the more important of the differences between DiSK and DP-SGD.\n\nThe paper also performs extensive experiments to compare against prior work to establish SOTA. It is not clear that the experiments match the deltas of the prior SOTA. I wasn't able to match the reported SOTA numbers to the papers that I checked, and some SOTA numbers are missing.", "questions": "My initial rating is a weak reject that I am willing to raise with good responses to these questions.\n\n# Questions about ambiguity\n- The way neighbors are defined has been left ambiguous. Are two datasets neighbors if adding/removing a record turns one into the other? Are two datasets neighbors if modifying one record turns one into another? The choice can result in significant differences in sensitivity and applicability of subsampling amplification results.\n\n- What form of subsampling was used for the creation of minibatches. Simple random sample with a fixed size? Poisson sampling?\n\n- What privacy accountant was used?\n\n- Algorithms 1,2,3 should use parentheses to more clearly resolve the ambiguity of whether the noise term belongs\nin the summation or outside.\n\n\n# Experimental questions\n- Did you match neighbor definitions in the comparisons to prior SOTA?\n\n- Have you tried any of the privacy auditing frameworks (e.g., relatively recent NeurIPS papers) to check for possible errors? For example, depending on when you add noise and when you average over a batch, an error could easily appear to be SOTA and this is not uncommon in DP-SGD.\n\n- The algorithms is 2 changes away from vanilla DP-SGD. The paper has hyperparmaeter tuning studies that are named ablation studies, but it does not have true ablation studies. There are 4 possible comparisons that can shed light on what is responsible for most of the apparent performance improvements. (1) vanilla dp-SGD (k=1, gamma=0); (2) weighted average before clipping, but no momentum on the gradient after clipping; (3) only momentum in the gradient and no pre-clipping averaging (gamma=0), (4) DiSK. \n    - Corollary 1 implies that gamma may be the more important parameter.\n\n- The paper does not explain how hyperparameters were selected. Were they chosen based on validation data (good) or testing data (thus favoring any approach that has more hyperparameters).\n\n- I tried to match up some of the SOTA numbers in the appendix as a spot check. \n    - Specifically, I looked at De et al. because they have a few prior SOTA numbers in the same place. I couldn't match their Imagenet numbers (32.4% top-1 accuracy to the 36.5 written in Appendix C5). \n   - I also noticed that some of the high CIFAR-10 training from scratch numbers in De et al. are completely missing from the Appendix.\n   - It is not clear to me whether DiSK is appropriately compared to the prior SOTA. Do you match deltas? Do you match neighbor definitions and batch subsampling? Do you match privacy accountants?\n   - Delta is a big difference maker, so you should put its numerical value(s) in every table.\n   - Table 6 does not match imagenet for table 2.\n\n# Other questions/comments\n- What is that wacky green line in Figure 1?\n- The paper uses C for too many different purposes. In some cases it is a clipping threshold, other times a constant in theoretical bounds, and other times a constant on properties of the data. This can get confusing even with subscripts.\n- Line 121: where is the delta < 0.05 restriction coming from? If I am not mistaken, Definition 2 is all Balle & Wang and does not use the results from Dwork and Roth.\n-Line 086-089: such comparisons are incomplete without specifying privacy parameters and adding citations.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper reads very nicely. The authors take the reader through a tour of their intuition when explaining the algorithm. The theoretical results are also discussed nicely. Most papers simply present a Big-O result and switch topics. This paper explained the significance of the theorem conclusion.\n\nI like the fact that the resulting algorithm is simple, increasing the chance of it being widely adopted.\n\nThe theoretical analysis is nice (theorem 2 and corollary 1) and shows that the provable convergence upper bound can be improved by a constant factor that depends on the model and data. It is not the same as claiming that faster convergence has been proved (Line 419, but that claim can be reworded to be accurate)\n\nThe model technique achieves state of the art in many settings (there is a small asterisk because I am not fully convinced yet, see below)..", "weaknesses": "There is a lot of ambiguity in the paper. Critical details are not discussed to ensure comparisons are apples to apples (see below).\n\nThere are discrepancies in the experiments and comparisons to prior SOTA (see below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)