Balancing Utility and Privacy: Dynamically Private SGD with Random Projection
Authors: Zhanhong Jiang
Md Zahid Hasan
Nastaran Saadati
Aditya Balu
Chao Liu
Soumik Sarkar
Venue: Accepted by TMLR ()

Abstract: Stochastic optimization is a pivotal enabler in modern machine learning, producing effective models for various tasks. However, several existing works have shown that model parameters and gradient information are susceptible to privacy leakage. Although Differentially Private SGD (DPSGD) addresses privacy concerns, its static noise mechanism impacts the error bounds for model performance. Additionally, with the exponential increase in model parameters, efficient learning of these models using stochastic optimizers has become more challenging. To address these concerns, we introduce the Dynamically Differentially Private Projected SGD (D2P2-SGD) optimizer. In D2P2-SGD, we combine two important ideas: (i) dynamic differential privacy (DDP) with automatic gradient clipping and (ii) random projection with SGD, allowing dynamic adjustment of the tradeoff between utility and privacy of the model. It exhibits provably sub-linear convergence rates across different objective functions, matching the best available rate. The theoretical analysis further suggests that DDP leads to better utility at the cost of privacy, while random projection enables more efficient model learning. Extensive experiments across diverse datasets show that D2P2-SGD remarkably enhances accuracy while maintaining privacy. Our code is available here.

Published in Transactions on Machine Learning Research (09/2025)
Balancing Utility and Privacy: Dynamically Private SGD with Random Projection
Zhanhong Jiang
dhjiong&iastale Giastate. edu sahid @iastate. edu nsaadati Giastate. edu baditya Giastate. edu cliu5 @tsinghua edu. soumiks Giastate. edu *Deparmment of Mechanical Engineering, Translalional AI Center, *Depertment of Electrical and Computer Engineering, Iowa State University
Md Zahid Hasan**
Nastaran Saadati*
Aditya Balu*
Chao Liu***
Soumik *
** Deportment of Emergy and Power Engineering, Tsinghua University
Reviewed OpenReview: https: // openreview. net/ forum? id=w60SRdhAul
Abstract
Stochastic optimization is pivotal enabler in modern machine learning, producing effective models for various tasks. However, several existing works have shown that model param- eters and gradient information are susceptible to privacy leakage. Although Differentially Private SGD (DPSGD) addresses privacy concerns, its static noise mechanism impacts the error bounds for model performance. Additionally, with the exponential increase in model parameters, efficient learning of these models using stochastic optimizers has become more challenging. To address these concerns, we introduce the Dynamically Differentially Private Projected SGD (D2P2-SGD) optimizer. In D2P2-SGD, we combine two important ideas: (i) dynamic differential privacy (DDP) with automatic gradient clipping and (ii) random pro- jection with SGD, allowing dynamic adjustment of the tradeoff between utility and privacy of the model. It exhibits provably sub-linear convergence rates across different objective functions, matching the best available rate. The thcoretical analysis further suggests that DDP leads to belter utility at the cost privacy, while random projection enables more ficient model learning. Extensive experiments across diverse datasets show that D2P2-SGT) remarkably enhances accuracy while maintaining privacy. Our code is available here
1 Introduction
Deep learning models Thirmavukarasu et al. (2023 Menghani 2023 enabled by stochastic optimization techniques, have achieved remarkable success in many fundamental machine learning tasks. Though these models empirically show incredibly appealing capabilities, there are critical concerns regarding the privacy of these models. In numerous applications, such as healthcare Chen et al. (2021) and finance Goodell et al. (202T), training datasets often contain highly sensitive information that must. remain confidential. However, duc the widespread use of deep lcarning models, their rich representations can possibly disclosc private information under privacy attakks, as demonstrated in the prior works Zhao al. (2020); Wang et. al.) how
(2022a). Additionally, as the number of model parameters increases exponentially, it is unclear privacy and model performance affect each other as the learning becomes more computationally complex.
Related Works. To miligate these privacy concerns, differential privacy (DP) Dwork (2006; 2008) was introduced, and has gained considerable attention Ji et al. (2014); Blanco-Justicia et al. (2022) to pro- vide principled and rigorous privacy guarantees. Intuitively speaking, DP a mochanism to ensure that all data samples have no significant impact on the ultimate trained model. Differentially private SGD (DPSGD) Abadi et al. (2016); Bassily et al. (2014) is one of the most acknowledged methods to solve the

---

Published in Transactions on Machine Learning Research (09/2025)
5 Update
Model parameters
Sample & Clip
sampled mini-batch B D
X
X =
X
2
S
Avg. & Project
Add Noise
Project Back
S2
gR
B
Ev-B
Ri
1 A v0
+ g1
B: A
1
A
Be
+
ck
v/8
vp A
Gaussian noise e ~ NO, o2 2 (p)
Private gradient
S B
(s(e))s)
Random matrix
g
[V
Ak
Figure 1: D2P2-SGD method involves five steps. For more technical details, please see Algorithm
private empirical risk minimization (ERM) problems. Specifically, it perturbs each gradient update with a static random noise vector (with the same dimension as that of the gradient) sampled from a distribution. The dimension of the noise vector is typically the same as that of the gradicnt, which could be extremely large and problematie. More advanced variants on top of DPSGD have also been developed to consider other key issues, such commmication--fficiee distributed setting Agarwal et al. (2018): |
Li & Chi (2025)
non-smooth losses Wang et al. (2022b), uniform Lipschitz condition Das et al. (2023), and compilation and vectorization Subramani et al. (2021) Using the perturbed gradient updates, we can compute the tradeoff between the utility and privacy of the model. This tradeoff can be adjusted via a noise mechanism, typically sampled from a static distribution with properly chosen yet fixed variance. While this approach is technically simple and provably effective, the noise variance significantly impacts the ultimate error bound. A challeng- ing issue that remains in various private machine learning tasks is how to achieve a desirable tradeoff between privacy and utility, which becomes particularly important in largo-scale deep learning models Flemings et al. b2024b; bs Mattern et al. (2022). Recent work Du et al. (2021) proposed a dynamic DP mechanism to adjust the tradeoff on the fly, reducing the model performance loss gap at the cost of increased privacy loss. Further, the dimension of the noise vector is typically the same as that of the gradient, which could be extremely large to cause intensive computational complexity. This issuc motivates us to seok out an approach that assists in reducing the complexity while maintaining privacy. Inspired by the work Blocki el al. (2012), we pay attention model compression techniques as follows. Though numerous prior works have extensively studied the tradcoff, most attempts rarcly investigated how to dynamically adjust it along the optimization using dynamic DP mechanism.
Model compression Buciluã et al. (2006): Choudhary et al. (2020) has been utilized to reduce the computa-
tional complexity, including quantization Chmiel et al. (2020). regularization Moradi et al. (2020); Orvieto et al. 2023), and projection Gu et al. (023); Tsfadia (2024) Though these methods aim to reduce com- putational complexity, their technical details can differ significantly depending on the specific focus. For example, in Gu et al. (2023), the authors used projection to identify the dominating gradient subspace, which facilitated improving model accuracy without changing the dimension of model parameters. This is akin to L1-norm regularization Xu et al. (2008), which forces certain model parameters to become exactly zero. Although model compression offers promising performance, it comes at the expense of possible accuracy reduction and sophisticated compression techniques, necessilating an effective optimizer that can balance the dynamic trade-off between privacy and utility. Additionally, the dimension of the noise vector is typically the same as that of the gradient, which could be extremely large and problematic. Consequently, effective approaches should be studied further to look into the tradcoff between privacy and utility while lowering the dimension of the additive noise. Additional related works are provided in Appendix A.1
2

---

Published in Transactions on Machine Learning Research (09/2025)
In this work, we highlight the need for effective optimizer to balance among complexity, privacy and utility; answering the critical question:
Can we design an adaptive differentially private optimizer to allow a small model performance reduction gap and maintain privacy?
Contributions. In this work, we answer the above question affirmatively. Specifically, we propose a novel stochastic optimizer termed Dynamically Differentially Private Projected SGD (D2P2-SGD) (as shown in Figure D, which, for the first time, integrates the dynamic DP mechanism with automatic gradient clipping and random projection for optimization. The dynamic DP mechanism involves an isotropic Gaussian distribution with properly chosen lime-varying variance that decreases along with the iterations, reducing noise effects as privacy loss increases. To further warrant differential privacy and bound the influence of each individual example on the stochastic gradiont, we resort to a recently developed automatic gradient clipping mechanism Bu et al. (2024). This is different from the traditional clipping method Abadi et al.] (2016). where an upper bound is imposed for gradients. Additionally, the stochastic gradient is projected into a lower-dimensional space, reducing the dimension of additive noise and mitigating the increase in privacy loss. Concretely, the main contributions are as follows:
1.
We introduce novel DP optimizer, D2P2-SGD, that employs dynamic DP mechanism with a time- varying noise variance and random projection. This approach minimizes model performance loss and reduces the dimensionality of noise vectors added to the stochastic gradients. Additionally, the per- sample gradient normalization serves as an automatic gradient clipping mechanism to regulate the influence of individual examples on the stochastic gradient.
Theoretically, we prove that D2P2-SGD achieves sub-linear convergence rates for both generally convex and non-convex functions, matching the best available convergence rate of regular SGD. The results for the dynamic DP mechanism can immediately degenerate to those for static scenarios, revealing the consolidation among complexity, utility, and privacy.
3. Extensive evaluations on wide spectrum of datasets confirm that D2P2-SGD significantly improves model accuracy compared to baseline methods.
While building on prior work Du al. (2021 : Kasiviswanathan (2021), our framework introduces funda- mental innovations: (1) The first unified integration of dynamic DP with random projection, where time- varying noise (which is different from the used in Du al. (2021)) is explicitly optimized for dimension- reduced gradients, which enables synergistic privacy amplification unaddressed in isolated approaches; (2) Novel theoretical insights into the petpensionn-ivvccytttee
trilemma under convex (Theorem 2 and non- convex (Theorem 3] objectives, revealing how projection reshapes dynamic DP trade-offs; (3) flexible mcchanism-agnosticc design supporting arbitrary noise/prac projeection variants. Extensive validation confirms these co-adaptations consistently outperform conventional combinations, offering new pathways for efficient privacy-utility balancing. We believe this represents a meaningful conceptual and practical advance in scal- able private learning. In this paper, our approach prioritizes theoretical exploration over scalability to larger datasets and models, including transformers and large language models Kasneci et al. (0223) While progress has been made in this domain Yu et al. (2021). designing a differentially private optimizer for such models remains a significant challenge and is deferred to future work.
2 Problem Formulation and Preliminaries
Given a private dataset D = (51, .2., } sampled in an i.idd manner from a distribution P such that we want to solve the empirical risk minimization (ERM) problem subject to differential privacy:
1 miny Σ f(x,s),
(1)
SED
where x #d and f(..) the loss for single sample. We aim to optimize Eq. 1 with gradient- based algorithm in differentially private manner. We denote by x the model parameters' iterate and ge the
3

---

Published in Transactions on Machine Learning Research (09/2025)
Table 1: Comparison among different methods.
Method
Noisc
Compression
Rate
DPSGD
Static
N
O
PDP-SGD2
Static
Y
O
VR N/A 0 0 0 0
DPKD
Static
N
Anti-PGD4
Static
VR
Dynamic DPSGD
Dynamic
N
T
PrivSGD
Static
RQP-SGD"
Static
Y
ADP-SGD*
Static
N
0 VR
PORTER"
Static
Y
0 VK
D2P2-SGD (Convex) D2P2-SGD (Non-convex)
Dynamic
0
R
Dynamic
0 VK
lnk
1: Bassily et al.
(2014;; 2: Zhou et al. (2020): 3: Mireshghallai et al. (022
4: Koloskova et al. (2023b); 5: Du et al. (2021) 6: Kasiviswanathan
22021): 7: Feng
& Venkitasubramanianl (2024); 8: Bu et al. (2024);
9: Li & Chi (022 N: no; Y:
yes; K: the number of iterations.
mini-batch gradient at each time step k. Throughout the analysis, assume that g: is the unbiased estimate of fx(x)), i.e., Vf(x)) B(g.). In this context, we resort to gradient clipping mechanism to constrain the magnitude of the stochastic gradient ga. To provide the guarantce of differential privacy, it requires bounding the influence of each individual example on gk- A fairly popular clipping operation Abadi eet al. 2016) applied to vector v E IRd as: clip(v, G) = min(1, [ } where G > 0, || is the l2 norm. However, when applying this to the stochastic gradient, such an operation will inevitably result in a "lazy region" issue, particularly if [|v|| > G. This means the parameters will not updated even if the true gradients are non-zero. Therefore, to mitigate this issue, we leverage a recently developed per-sample gradient normalization Bu et al. (2024) an automatic clipping mechanism described as: clip(v, G.?) = ||v __ V. where y a positive stability constant, which is practically small. Additionally, the authors even showed that any constant choice is equivalent to choosing follow their setup to directly set G while still keeping G in the theoretical analysis, particularly for the generally convex objective, which is missing in Bu et al. (2024). Additionally, y 0, when the objective is non-convex, the gradient norm will converge to neighborhood of the optimal solution affected by To characterize the analysis for the proposed scheme, we introduce the necessary background and preliminary knowledge in the sequel, starting with the standard definition of differential privacy.
G
In this work, for the algorithmic framework,
will reveal that for any
Definition 1. ((e, diffffeernttia privacy Dwork 2006)) randomized algorithm M is (c. -iifffrrreetl privole if for any two neighboring dalasets D, D' and for all events y C Range(M) in the oulput range of M, we have Pr(M(D })) S exp(e) e })} + 6, where the probabilily is taken over the randomness M.
Range(M) refers to the set of all possible outcomes of M. Technically speaking, the set y in Definition [ must be measurable. This definition implies that the probability of observing specific output any two neighboring datasets
differ by at most multiplicative factor of exp(s). Intuitively, sufficiently small value suggests that cither including or excluding single data point from the dataset does not likely affect the output. Hence, an adversary only accessing the outpul of M makes it difficult. to infer whether any data point is present in the dataset. The parameter = called privacy budget and its practical selection varies significantly, depending on different scenarios Ponomareva et al. (2023). Additionally, & represents the probability that the privacy guarantee differentially private mechanism might be violated and controls the strength of the relaxation, with smaller values leading to stronger privacy guarantees. A generally

---

Published in Transactions on Machine Learning Research (09/2025)
recommended 8 value in the literature is to choose 8 < 1 Ponomareva et al. (2023). ). In our analysis, we will establish the privacy guarantee for the proposed algorithm presented in the next section. Before that, we present preliminaries on random projection and formally define the projection matrix. Random projection (RP) Achlioptas (2001) is an effectively fundamental tool that has been used in numerous applications to analyze dalasets and then characterize their major features. It. projects data points to random directions that are independent of the dataset, which renders simpler and computationally faster trends than classical methods such as singular value decomposition (SVD). RP is based upon the Johnson-Lindenstraune (JL)
a
lemma Larsen & Nelson (2017) as follows.
Lemma 1.
Lemma Larsen & Nelson (017)) For any 0 < < 1, a sel S of m points in Rd and an integer > 8(lum)/{² there exists a linear map h Rd + R,, such that (1 - O) u1 -
[[h(u) - h(v)ll = (1 (1++6) +1 - u for all u.u
JL lemmn states that a set of points in a high-dimensional space can be projected into a lower-dimensional subspace such that their relative distances are nearly preserved.
While do not directly apply the above definition in our algorithm design, it motivates and underpins our use of RP for model parameters or gradients Kasiviswanathan (2021). Crucially, RP's foundation in the JL lemma originally conceived for data rests on its guarantee of distance preservation. Without this guarantee, RP would degrade into a lossy and unreliable heuristic. The JL. lemma mathematically ensures that geometric fidelity survives dimensionality reduction, enabling scalable and accurate computation. When applying RP to parameters or gradients, our goal remains the same: to find an effective linear map that minimizes information loss. Lemma [ thus justifies extending RP's application from data to gradients, while highlighting the critical importance of the lincar map defined subsoquently.
Lemma 2. Let A be Gaussian random matrix of order d x p, Le., Ag ~ (O and be any fized vector in Rd. Define the lineor mapping h(-) such that r = h(o)= = ATo. Thus, r E R and r; = 1 E, Aijoy.
We notice that each element of A is sampled from the same normal distribution NNO,,), while we use a slightly different variance, o instead of in our theoretical analysis for a more generic purpose. Combining Lemma 1 and Lemma 2 with a high probability (at least 1 ) Johnson et al. (1984), , can maintain the precise model expressivity even if applying RP to project parameters or gradients to low-dimensional space during updates. This allows us to use RP in our proposed algorithm. We will have a detailed discussion in the following section regarding how RP contributes to our method.
3 Algorithm and Main Results
3.1 Algorithmic Frameworks
D2P2-SGD shown in Algorithm Line 4 states the key gradient clipping operation control the influence of the gradient magnitude. Compared to the clipping mechanism applied in Abadi et al. (2016), we do not need to tune the clipping threshold. In Line 5, mini-batch stochastic gradient is calculated after the per- sample gradient clipping. In Line 6, the stochastic gradient ge is projected to the lower-dinensionall space Rº by using the random projector from Lemma 2 such that we have J ge: which is followed by adding the noise sampled from a Gaussian distribution with time-varying distribution of, where or,k = St With this, is independent of a high dimension d, but dependent on lower dimension p < d, which fundamentally reduces the noise. The fact that we resort to the decay of 1 for the variance is motivated by the same setup as the learning rate in stochastic optimizers Bottou al. (2018), which manipulates the tradeoff between the convergence speed and optimality. Analogously, o²,x controls the impact of the noise mechanism on the tradeoff between privacy and utility in different phases of the optimization. Since the update for x is operated in the original dimension Rd, we multiply the projected stochastic gradicnt by As to project it back to the original one. It is noted that such an implementation will cause projection errors that impact the error bound (which will be observed in the theoretical analysis). However, similar to Wang et al. (2019b). D2P2-SGD implics more efficient model lcarning as it has now focused primarily on the subspace in Rd instead of the whole space. Note that the temporal evolution of A is due to its elements being sampled from a constant ribuutin per iteration. We give geometric intuition here to facilitate
V
5

---

Published in Transactions on Machine Learning Research (09/2025)
the understanding of why RP is critical in D2P2-SGD. If we regard gradients vectors in high-dimensional space, the isotropic noise in I& corrupts all directions equally. However, RP projects gradients onto random low-dimensional subspace where based on Lemma I 'important" directions of gradients are preserved. This ensures that the noisc only corrupts the compressed dimensions such that the gradient signal still remains strong as the original noise has been defused. To summarize,, RP induced by JL Lemma acts as an efficient dimensionality compressor in SGD updates to shrink the injected noise but with gradient preservation.
We claim that D2P2-SGD represents unified framework over existing methods. When p 1 and A = ... Ax = I, D2P2-SGD degenerates to dynamically differentially private SGD (D2P-SGD) Du et al. (2021), though the original approach has another gradient clipping mechanism to prevent dynamic DPSGD from diverging and different formula for o²,-- On top of D2P-SGD, if we set fixed variance for Ej.- it becomes DPSGD without any random projection. On the other hand, PrivSGD Kasiviswanathan (2021) can also be obtained if D2P2-SGD has a fixed variance with the random projection. However, compared to PrivSGD, which involves an extra optimization to convert from the low-dimensional to high-dimensional spaces, our scheme simply uses As lo replace the optimization, which signifieantly atlenuates the practical implementation complexity. We also use DP2-SGD (differentially private projected SGD) to represent this case. Please see these two variants in Appendix A.2 We also remark on the additional computational overhead due to RP. A₁ is regenerated per iteration by sampling from the same distribution. The total computational overhead incurred is (dp). In practice, the implementation is layer-wise so the matrix multiplication not one-shot with all parameters, mitigating the memory issue.
Algorithm D2P2-SGD
INITIALIZE: Model parameters X1, step size a, number of epochs K, lower dimension p, random matri- oes A,, A2...., Ag, mini-batch size B, training dataset DD noise sequence o?, o2,....... Lek gradient clipping parameter y
2: for k: == 1,......,A K do
3: Split the dataset D into mini- batches size B and randomly sample one mini-batch B
4: Compute per-sample clipped gradients: & [7](++))]|+77 8 E
Vf(x((e)
5: Calculate the mini-batch stochastic gradient: ga - E5n888 8f
6: Project noisy gradient using A&: gx = A vp
A gk + +()) cc ~ N(0,02.
Update model parameters: Xk+1 Xx: ags
end for
9:
return XK
3.2
Main Results
We next show the convergence behavior for our proposed D2P2-SGD, with generally convex and non-convex objective functions, and start with assumptions. All proof is deferred to the appendix.
Assumption 1. (a): f(x) is smooth with modulus T. for all x E Rd, i.e., for any x1, E TRd, we have [V - f(x2) = x X2ll; : (b) throughout the analysis, the minimum value of the objective f exists and is bounded below, é.c., f := f(x"),x* = minxeR* and f -00
Assumption (a) is generic many previous works Wang et al. 2019b) Du el al. (2021); Kasiviswanathan (2021h imply that the variations of gradients along with optimization are bounded above by L. Many models, even including deep neural networks, can at least be approximately smooth for the corresponding losses.
Assumption 2. The variance of stochastic gradient Vf s) is bounded above by a constant a > 0, i.e., (Vx( o², Ys D.
Assumption 2 is popular when analyzing the convergence behavior of SGD-type algorithms due to the mini- batch sampling (Line in Algorithm [T.. In some recent works, the boundod gradient assumption is also leveraged Zhou et al. (2020); Zhang et al. (2023), remaining a strong condition for the analysis. For example, if the objective is in quadratic form, f(x x Mx, where M is real symmetric matrix, then vf(x)

---

Published in Transactions on Machine Learning Research (09/2025)
is in linear form, which violates such an assumption. The author in Kasiviswanathan 20021 used an extra bounded second moment assumption for gradients besides the bounded variance assumption, though it is weaker than the bounded gradient assumption. We would like to clarify that in D2P2-SGD, the full noise distribution (Line 6 in Algorithm I we have added in the update is specifically for differential privacy. Besides, we also quantify the dimension distortion error due to random projection with the variance of the sampling distribution. In the sequel, we start the main result with the privacy guarantec.
Theorem 1. (Privacy) Let Assumption 2 hold. There exist constants C1. > such that for any e S GBBKK D2P2-SGD is (5, differrentil private for any 6 > 0, if of CyB2K21m(1/0)
n²g²
The detailed proof is deferred to Appendix A.3 The core idea of the proof is that at each iteration, Line 6 in Algorithm| 1 post-processos the Gaussian noise mechanism that perturbs the stochastic gradient gi by adding noise ej- Subsequently, the sequence of vp A 8* + K is released to have a privacy guarantee by following the same privacy proof of Theorem in Abadi et al. (2016). However, the significant difference in our work is that the noise variance is time-varying, i.e., -²,A- With the explicit. form of noise variance we have defined in this work, i.e., o²+ = of, it immediately obtained that 0²1 > o².2 > ... > xe.x- In Wang et al. (2019b) and Abadd et al. (2016), the static variance has the lower bound with respect to some key constants such K and G. Thus, as long o²,k= 2 C2KB91n(1/1) the privacy guarantee is attained. Equivalently, a² >
n²c2
C2k212ln(1/6)) in this context. A constant noise variance throughout optimization risks diminishing xt=* the final model's utility. To mitigate this, we employ decrcasing noise variance schedule. This dynamic approach provides essential flexibility, enabling adaptive privacy budgeting that more effectively balances the privacy-utility trade-off compared to static mechanisms. A natural question arises regarding RP's impact on DP guarantecs. Critically, the stochasticity inherent in RP does not compromisc the DP analysis. This is a direct consequence of DP's fundamental post-processing immunity: any computation applied to the output of a DP mechanism retains the original privacy guarantee. This well-established property that has been validated in prior works Zhou et al. (2020); Kasiviswanathan (2021); Feng & Venkitasubramaniam (2024) ensures use of RP maintains the rigorous privacy bounds for the core mechanism.
Another observation from Theorem D is that the size of mini-batch B has an impact on E. When B enlarges, s has a larger upper bound such that the model performance improves with the cost of privacy, which will be evidently validated in the results section. This also intuitively validates the fact that a larger batch typically improves deep learning model performance. Though the authors in Du et al. 2021 for the first time proposed to leverage dynamic DP mechanism to reduce the model performance loss gap, privacy guarantee has been ensured by the dynamic power following an exponential mechanism G.,k x Op--)), where p is a positive constant. As they still utilized the clipping mechanism from Abadi et al. (016)), they also had to establish a similar exponential mechanism for the clipping threshold, which makes their algorithm framework more complex. While in our work, thanks to the automatic clipping mechanism, there is no such requirement. We are now ready to state the results for the utility with different functions.
Theorem 2. (Utility for conver. functions) Let Assumptions) 7 and 2 hold. Suppose that f is a conver function and that A is a random matria with each element being sampled from a normal distribution (0, o²).. Also, let the additive noise of DP mechanism have the variance o²,x- If the step size a S 2,, then for the ilerates 1e= { K 21 1 generated by D2P2-SGU the following relationship holds true
X1 - x (P(11
2aKoavp + ap2-5(1 + 7]nK + +1)0² + apd 0² (1 +
[(((8)) -
(2)
2K
2
where XK = 1/2 Ek X3.
Theorem suggests that the error bound involves three terms: the initialization error, the error of additive noise due to the DP mechanism, and the random projection approximation error. We first turn to the second term and see how it impacts the error bound. If 22 o²: this term becomes (0p ?)o which is a constant. Instead, if 02 = - it can be bounded by O loK) ); which also relaxes the dependence on a to decay the magnitude. Though the model performance loss gap is reduced, dynamic variance can breach privacy. To maintain the (e, d)ddifferenttal privacy for D2P2-SGD, as implied in Theorem 1 the additive
K
7

---

The following Published in Transactions on Machine Learning Research (09/2025)
noise should be sampled with larger of to offset the privacy loss, particularly in the early phase during the optimization, compared to DPSGD. When de x (1),, we can immediately know that with a higher privacy (which corresponds to a smaller e), the utility decreases. In this scenario, RP becomes more advantageous because noise reduction with a small counters strict privacy. Conversely, with a lower privacy (which corresponds to a larger e), the utility increases. However, RP may hurt utilily as the dimension distortion error dominates the noise already small. Thus, prioritizing one forces tradcoffs in the others, making dimension p the pivotal lever in this trilemma. We include the details of how privacy budget e and dimensions (d.p) impact the error bound and the comparison to DPSGD in Appendix AA.5 The last term is associated with RP approximation error, while the term o² d2 due to model compression can cause significant error. One empirical remedy is to leverage a small a, but this leads to slow convergence. Eq. [ implies that when K - xo, D2P2-SGD converges to the neighborhood of x" asymplotically with the rale of O(1/K + Ink/K) K), up to a constant apd"o (1 + 7)/2. Additionally, a small initialization error ||x] -x*ll and a larger batch size lead to better performance, which stresses the implication from Theorem I Overall, the consolidation among complexily, utility, and privacy in D2P2-SGD is reflected explicitly in Theorem 2
corollary summarizes the explicit convergence rate when O ((R))
Corollary 1. With conditions defined in Theorem when O O(<R); the sollowing relationship holds true, L.e., Bif(xx) - f 0 JR + k.
The conclusion in Corollary 1 requires the constant learning rate a to have format x O (T))) which is a quite popular choice in stochastic optimization Garrigos & Gower (2023) After carefully reviewing some recent works Koloskova et al. (2023ap; Bu et al. (2024); Xiao et al. (2023); Chen et al. (2020), though they have also focused on the investigation of convergence guarantee for differentially private SGD with gradient clipping, all of them paid only attention to nonconvex cases. Our result explicitly and rigorously establishes the convergence rate of D2P2-SGD for convex functions. Without dynamic differential privacy and model compression, our result resembles exactly the same convergence rate of regular SGD in O ((R)) Particularly, if a desired accuracy Ç > is defined specifically for E[f(xk) - f*] S Ç, the complexity bound for K is 0 + (In())) (In(5))2/0
(3/3 ). In comparison, our rate improves the one reported in Kasiviswanathan (2021), which is O(kkk) ). Note that in their caso, they use a decaying step size 0% x assumption. We will now present the main result. for non-convex functions.
VE and there is no smoothness
Theorem 3. (Utility for non-conver functions) Let Assumptions 7 and hold. Suppose that A is random
matria with each element being sampled from normal distribution (O,,2)) Also, let the additive noise
of the DP mechanism have the variance o²,,. If the step size a S 2L, then for the iterates {x*]K K 2 1 generated by D2P2-SGD, the following relationship holds true
minkep.<(E1lVV/xx)))) -(x))-f-
+ +1) + La 0'
20 VB
Koa +
+7
(3)
K
We immediately have the following result when the step size satisfies a certain condition.
Corollary 2. With conditions defined in Theorem 3 when a O (x)) ) the following relationship hold true, EII S O + + InK
R +0+7).
Similarly, the error bound from Theorem dictated by the initialization error, the error of addictive noise, the random projection approximation error and the clipping bias. Especially, the clipping bias 2n + 7 vB
is determined by the variance, the batch size and the stability constant. To mitigate the clipping bias, one immediate solution is to properly increase the batch size. Due to y, in practical implementation, one can choose a small value for 7- When ? is ((+)) in Corollary 2 the clipping bias resembles the result in Koloskova et al. (2023a), up lo some absolute constants. Also, The convergence rate of non-convex functions remains similar to that of generally convex functions. However, comparing results from Corollary [ and Corollary 2 the error of non-convex functions larger due to the clipping bias, which illustrates that the convergence for non-convex functions is more challenging. We summarize the clipping bias for different methods in Table 4 in Appendix A.7 for comparison (we only compare for non-convex functions most
8

---

Published in Transactions on Machine Learning Research (09/2025)
of the existing methods only discussed non-convex objectives). Practically, non-asymptotic convergence is preferred such that we can resort to pre-defined small constant. & 0 to define metric, i.e. the norm of gradient [|V] s Ç for non-convex functions. Suppose that B = o and = (( If the computational complexity is defined the total number of gradient computations, it can be observed that the computational complexity is KB O(1/5²), which retains the same complexity as in Ghadimi & Lan (201)) The tradeoff between privacy and utility is analogous to that for convex functions, only differing in some absolute constants. Thus, we do not repeat the same remarks in this context, but provide the impact of privacy budget & and dimensions (d, p) on the error bound in Appendix A.8
4 Numerical Experiments
We present extensive empirical results to thoroughly validate our proposed approaches with a comparison basclincs. The basclines we use in this study consist of SGD, vanilla DPSGD, D2P-SGD, and DP2-SGD. D2P-SGD is equivalent alternative to Dynamic DPSGD in Du et al. (0221) DP2-SGD also be re- garded equivalence of PrivSGD Kasiviswanathan 2021 since the compression technique they adopted is also random projection, with static DP. We leverage the Opacus library Yousefpour et al. (2021) and build the framework on top of it. We use a 4-layer Convolutional Neural Network (CNN) as the model, which has been widely used in testing optimizers. A more detailed explanation of the architecture is pro- vided in Appendix A.9 Additionally, the datasets for testing our algorithms include FashionMNIST and SVHN Figueroa 2019 As we have particularly identified the critical relationship between the privacy loss and other parameters, ablation study this is shown to reveal their impacts the performance. Hyperparameters have significant impact deep learning models' performance. In the interest of brevity, have chosen most hyperparameters used in the model via manual luning, although note that an auto- mated hyperparameter tuning framework would likely be beneficial for these models. Additional information, including network architecture and specific hyperparameter setup, and results on other larger models and datasets are in Appendix A.9
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
1.0
3.0
static dynamic
2.5
Testing Accuracy
0.8
Training Loss
2.0-
2.0
1.5-
w 1.5
1.0-
1.0
0.5
0.2
0.5
0.0
0.0
0.0
10
Epoch
Epoch
Epoch
Figure 2: Comparison among methods for SVHN data: on the right side, the privacy loss is shown for static and dynamic scenarios.
Comparative Evaluation. Figure shows the model performance and privacy loss for different methods. We train five different instances of each algorithm with different random seeds. The solid curves correspond to the mean and the shaded region to the minimun and maximun values over the five runs. For the privacy loss, the standard deviation is fairly small. Also, the dynamic mechanism for D2P-SGD and D2P2-SGD is the same. Similarly, DPSGD and DP2-SGD have the same static mechanism. According to Figure 2 D2P2-SGD significantly improves the model accuracy compared to DPSGD, D2P-SGD, and DP2-SGD. While this comes at the expense a larger privacy loss, which is expected. This is attributed to the decrcasing variance o2/// along with iterations. However, the testing accuracy of D2P2-SGD much closer SGD, while having a gap due to projection error and clipping bias. Notably, D2P2-SGD spends lesser number of epochs, reaching higher accuracy at the early phase, even earlier than SGD, which implies that

---

Published in Transactions on Machine Learning Research (09/2025)
DPSGD
D2P-SGD
DP2-5GD
D2P2-SGD
3.0
static dynamic
Testing Accuracy
Training Loss
2.0-
2.0
1.5
w 1.5
1.0
1.0
0.5
0.2
0.5
0.0
10
40
20
30
10
20
Epoch
Epoch
Epoch
Figure 3: Comparison among methods for PNsHionMNIST data: on the right side, the privacy loss is shown for static and dynamic scenarios.
0.8
0.8
0.6
0.6
0.4-
0.4
0.2-
BP520
0.2-
BP500
D392 500
0272 503
0.0
0.0
6
10
6
30
(a) SVHN
(b) FashionMNIST
Figure 4: Accuracy vs. standard deviation
BTSCO
072-500 0292
E272.503
2
(a) SVHN
(b) FNshionMNIST
Figure 5: Privacy loss standard deviation
random projection enables more efficient model learning. Similar conclusions be made from Figure 3 Comparing DP2-SGD and D2P2-SGD, we see that with random projection, if the noise variance from the DP mechanism static, the performance deteriorates accordingly. However, with a dynamic mechanism, it performs robustly throughout training. This validates the conclusion from Theorem 3 where the second term decays faster when the number of iterations increases. However, DP2-SGD remains with the rate of O(1/VK)
K) (If a is in (LI/VK), this term in D2P2-SGI is in (In(K/K)) while DP2-SGD O(1)). Figures 2 and reveal comparable performance between DPSGD and D2P-SGD. This alignment stems from our privacy configuration. In DPSGD, the fixed noise variance o² CsK l))1 yields a static privacy- n²
utility tradeoff. Conversely, D2P-SGH employs dynamic noise variance o2 optimization (k < K), initialization error dominates, masking performance differences despite divergent noise mechanisms. As k K, privacy error dominates, but the noise variances converge, explaining the sustained similarity in performance. Turning to the privacy loss (e) in both figures, observe that the
C.K² In(1/8) During early =
10

---

Published in Transactions on Machine Learning Research (09/2025)
0.80
DaP2 Sel Hish Lok0n
S4D Hizud 2.02500)
0.78-
aecurery
6,76-
2.55
2.50
0.74
6.72-
2.40
0.1
0.3
0.5
0.7
0.5
Dimenston reduction rates
(a) Batch size vs. privacy loss for FashionM-(b) Dimension NIST
V8.
accuracy/privagge for
SVHN
Figure 6: Impacts of parameters in D2P2-SGD
maximum privacy losses of the dynamic mechanism end up with respectively 2.45 (for SVHN) and 2.75 (for Fashion MNIST). Compared to values with the static DP mechanism (1.06 and 0.95, respectively), the privacy loss of D2P2-SGD grows sharply. However, given the bound for E in Theorem I as long as the constant C (2 314, see Appendix A.9 is selected properly, D2P2-SGD still remains ddffferrirrelllllllly private. While the value of 2.45 or 2.75 offers a reasonable, rather than exceptionally strong privacy guarantee, it reflects our focus on balancing privacy and utility. However, in highly private domains such as medical applications, D2P2-SGD can still be adopted to bias towards privacy by setting large dynamic noise. These two values are the only resulting values based on the data we have applied in this work. Thus, our proposed scheme improves the accuracy over baselines while successfully maintaining differential privacy. Table 2 Summmarizes the performance for different optimizers at the same privacy loss e values (a, 3.0), showing that D2P2-SGD outperforms other differentially private optimizers and validates our theoretical finding.
Table 2: Testing accuracy (averaged through random seeds) at different values (FashionMNIST dataset)
Test acc. at E 1.0
Test acc.
Test acc.
Test acc.
Test acc.
Optimizers
at ε 2.0
at & 4.0
at 6.0
at æ 8.0
DPSGD
0.6910
0.5291
0.5331
0.5704
0.5849
D2P-SGD
0.6549
0.7063
0.5242
0.5656
0.5573
DP2-SGD 0.6042
0.6736
0.5884
0.5461
0.6297
D2P2-SGD 0.7132
0.7322
0.7417
0.7851
0.7566
Impact of o.. From Figure 4 it shows that as a. value increases, the final model accuracy drops for DP2- SGD and D2P2-SGD. This first validates the coupling between projection error o² and the noise variance o², in Theorem 3 and shows the trade-off between the utility and privacy. When a, < 6, which can be treated as a low privacy regime, D2P2-SGD maintains better performance than DPSGD and D2P-SGD, while underperforming in the high privacy regime after ae > 6. This intuitively shows us a careful selection of o. is required to balance the trade-off. Figure 5 delivers a similar conclusion in terms of privacy loss.
Impact of B. As suggested by Theorem 1 we can adjust the privacy loss by setting the batch size B. In Figure 6al we can observe that when batch size increases from 256 1024, it increases the upper bound for B such that the privacy loss is relatively higher through all a, for D2P2-SGD, leading to the better performance. This esscntially validates the condition B = o2/52, where o² decreases in the error bounds, leading to better convergence due to the smaller g.
8 n
Impact of p. Figure 6b shows the impact of different lower dimensions the testing accuracy and privacy loss. It immediately suggests that the performance of random projection varies with different p values. The imal one is a 30% reduction rate, which implies that random projection can assist in model learning efficiency if the p value is chosen properly. Instead, the privacy loss is independent of the dimension change based on Figure 6b Thus, D2P2-SGD allows us to reduce the computational complexity by random projection while maintaining privacy. The dimension can be chosen in a wide range and will not affect model performance significantly, including accuracy and privacy.
11

---

Published in Transactions on Machine Learning Research (09/2025)
Limitation. Though D2P2-SGD has shown good performance compared to the existing baselines, some potential limitations exist, which can also help close such gaps in future work. First, D2P2-SGD may not work well in scenarios with high privecy restrictions. As we have the decaying noise variance that ensures decent model performance, privacy loss will inevitably be the resulting outcome. One can carefully tunc these parameters to obtain acceptable values, but is still lairly challenging to scale. One way to get rid of this is to develop more effective dynamic DP mechanisms such that the tradcoff between utility and privacy can be handled better. Second, getting an optimal p value for random projection may be difficult as well. Though based on Johnson-Lindenstenn different scenarios have not yet been accessible in principled manner.
Lemma, p can be analytically obtained, its practical values for
5 Conclusions and Broader Impacts
This work presents novel diffcrentially private optimizer termed D2P2-SGD with a dynamic DP mechanism, automatic gradient clipping, and model compression, which reveals the synthesis among privacy, utility, and complexity. Specifically, we establish the dynamic privacy guarantee such that relatively larger variance is required in the early phase of optimization to compensate for the privacy loss in the latter phase. Given a pre-defined dynamic variance, D2P2-SGD enables a slightly tighter error bound compared to vanilla DPSGD with a static DP mechanism. Empirical results are shown to validate the theory first and then compared with baselines using popular models and benchmark datasets. Compared to vanilla DPSGD, our D2P2-SGD is more robust against larger noise variance but with slightly larger privacy loss. However, the accuracy is significantly improved without dependence on the large dimension. The broader vision of this work is to advance the field of differentially private machine learning with the potential impact of building privacy- aware deep learning models with highly sensitive information for critical sectors such as healthcare and national security.
Acknowledgments
We sincerely thank the anonymous reviewers for their thorough evaluation and insightful recommendations, which have helped improve the presentation and clarity of this work. This work was supported by the CO- ALESCE: COntext Aware LEarning for Sustainable SybEi-Agricultural Systems (CPS Frontier #1954556).
References
Martin Abadi, Andy Chu, Ian Goodfellow, H 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.
Dimitris Achlioptas. Databaso-friendly random projections. In Proceedings of the twenticth ACM SIGMOD- SIGACT-SIGART symposium Principles of dalabase systems, pp. 274 281, 2001.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. opsgd: Communication-effiienn and differentially-private distributed sgd. Advances in Neural Information Processing Systems, 31, 2018.
Racf Bassily, Adam Smith, and Abhradecp Thakurta. Private empirical risk minimization: Efficient algo- rithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pp. 464-473. IEEE, 2014.
Alberto Blanco-Justicia, David Sánchez, Josep Domingo-Ferrer, and Krishnamurly Muralidhar. A critical review the use (and misuse) of differential privacy in machine learning, ACM Computing Surveys, 55 (8):1-1,,200 2022.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The jolnson-lindenntrauss transform itsclf preserves differential privacy. In 2012 IEEE 53rd Annual Sympostum on Foundations of Computer Science, pp. 410-419. IEFE, 2012.
12

---

Published in Transactions on Machine Learning Research (09/2025)
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. STAM revieu, (0(2))223-311) 2018.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. Advances in Neural Information Processing Systems, 36, 2024.
Cristian Buciluä, Rich Caruana, and Alexandru Niculescu-Mizzi. Model compression. In Proceedings of the 12th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 535-541, 2006.
Irene Y Chen, Emma Pierson, Sherri Rose, Shalmali Joshi, Kadija Ferryman, and Marzych Ghassemi. Ethical machine learning in healthcare. Annual review of biomedical dala science, 4:123-144 -244,,4, 2021.
Xiangyi Chen, Steven 7. Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 33:13773 13782, 2020.
Brian Chmiel, Ron Banner, Gil Shomron, Yury Nahshan, Alex Bronstein, Uri Weiser, et al. Robust quan- tization: One model to rule them all. Advances in neural information processing systems, 33:5308-5317, 2020.
Tejalal Choudhary, Vipul Mishra, Anurag Goswami, and Jagannathan Sarangapani. comprehensive survey on model compression and acceleration. Artificial Intelligence Review, 53:5113 5155, 2020.
Rudrajit Das, Satyen Kale, Zheng Xu, Tong Zhang, and Sujay Sanghavi. Beyond uniform lipschitz condition in differentially private optimization. In International Conference Machine Learning, pp- 7066 7101. PMLR, 2023.
Sanjoy Dasgupta, Daniel Hsu, and Nakul Verma. concentration theorem for projections. arXiv preprint ar0iv: 18066681,, 2012.
Jian Du, Song Li, Xiangyi Chen, Siheng Chen, and Mingyi Hong. Dynamic differential-privacy preserving sgd. arXiv preprint xrXi:22111.00133 2021.
Cynthia Dwork. Differential privacy. In International colloquium on anlomala, languages, and programming, pp. 1-12. Springer, 2006.
Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and appli- cations of models of computation, pp. 1-19. Springer, 2008.
Ce Feng and Parv Venkitasubramaniam. Rqp-sgd: Diffcrential private machine learning through noisy sgd and randomized quantization. arXiv preprint 0xxx:2402.06600 2024.
Jhosimar Arias Figueroa. Semi-supervised learning using deep generative models and auxiliary tasks. NewrIPS Workshop on Bayesian Deep Learning, 2019.
James Flemings, Meisam Razaviyayn, and Murali Annavaram. Differentially private next-token prediction of large language models. arXiv preprint arXiv:2403. 15638, 2024.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. XrXiv prepriat ar arx::22301.1120 11235, 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. STAM journal on optimization, 23(4):2341 -2368, 2013.
John W Goodell, Satish Kumar, Weng Marc Lim, and Debidutta Pattnaik. Artificial intelligence and machine learning in finance: Identifying foundations, themes, and research clusters from bibliometric analysis. Journal of Behavioral and Experimental Finance, 32:100577, 2021.
Xin Gu, Gautam Kamath, and Zhiwei Steven Wu. Choosing public datasets for private machine learning via gradient subspace distance. Xixiv preprint 203 2023.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Zhanglong Ji, Zachary C Lipton, and Charles Elkan. Differential privacy and machine learning: survey and review. arxie preprint arXiv:1422. 7584, 2014.
William B Johnson, Joram Lindenstrauss, et al. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
Shiva. Prasad Kasiviswanathan. Sgd with low-dimensional gradients with applications to private and dis- tributed learning. In Uncertainty in Artificial Intelligence, pp. 1905 1915. PMLR, 2021.
Enkelejda Kasneci, Kathrin Seßler, Stefan Küchemann, Maria Bannert, Daryna Dementieva, Frank Fischer, Urs Gasser, Georg Groh, Stephan Günnemann, Eyke Hillermeier, et al. Chatgpt for good? on oppor- lunities and challenges of large language models for education. Learning and individual differences, 103: 102274, 2023.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 17343-17363. PMLR, 2023a.
Anastasiaa
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, 2023b.
Kasper Green Larsen and Jelani Nelson. Optimality of the Gohnson-lindenstramne lemma. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 383-638. IEEE, 2017.
Boyue Li and Yuejie Chi. Convergence and privacy of decentralized nonconvex optimization with gradient clipping and communication compression. IEEE Journal of Selected Topics in Signal Processing, 2025.
Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schoelkopf, and Mrinmaya Sachan. Differ- entially private language models for secure data sharing. arXiv preprint arXiv:2210. 13918, 2022.
Gaurav Menghani. Efficient deep learning: A survey on making deep learning models smaller, faster, and better. ACM Computing Surveys, 55(12):1-37, 2023.
Fatemehsadat Mireshghallah, Arturs Backurs, Huseyin Inan, Lukas Wutschitz, and Janardhan Kulkarni. Differentially private model compression. Advances in Neural Information Processing Systems, 35:29468- 29483, 2022.
Reza Moradi, Reza Berangi, and Behrouz Minaei. A survey of regularization strategies for deep models. Artificial Intelligence Review, 53(6):3947-3956, 2020.
Mahmoud Nabil. Random projection and its applications. arXiv preprint arXic:1710.0311 2017.
Antonio Orvieto, Anant Raj, Hans Kersting, and Francis Bach. Explicit regularization in overparametrized models via noise injection. In International Conference on Artificial Intelligence and Statistics, pp. 7265- 7287. PMLR, 2023.
Natalia Ponomareva, Husscin Hazimch, Alex Kurakin, Zheng Xu, Carson Denison, Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 11:1113-1201, 2023.
Pranav Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and voctorization. Advances in Neural Information Processing Systems, 34:26409- 26421, 2021.
Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature medicine, (9)9:11300)) 2023.
Eliad Tsfadia. On differentially private subspace estimation without distributional assumptions. arXiv preprint ar X0Xi:22402.00465, 2024.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Bao Wang, Zuoqiang Shi, and Stanley Osher. Resnets ensemble via the feynman-kad -ac formalism to improve natural and robust accuracies. Advances in Neural Information Processing Systems, 32, 2019a.
Ji Wang, Weidong Bao, Lichao Sun, Xiaomin Zhu, Bokai Cao, and S Yu Philip. Private model compression via knowledge distillation. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 33, pp. 1190 1197, 2019b.
Junxiao Wang, Song Guo, Xin Xie, and Heng Qi. Protect privacy from gradient leakage attack federated learning. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pp. 580 589. IEEE, 2022a.
Puyu Wang, Yunwen Lei, Yiming Ying, and Hai Zhang. Differentially private sgd with non-smooth losses. Applied and Computational Harmonic Analysis, 56:306-335 336, 2022b.
Hanshen Xiao, Zihang Xiang, Di Wang, and Srinivas Devadas. A theory to instruct differentially-prieee learning via clipping bias reduction. In 2023 IEEE Symposium on Security and Privacy (SP), pp. 2170- 2189. IEEE, 2023.
Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and lasso. Advances in neural information processing systems, 21, 2008.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: User-friendly differential privacy library in pytorch. arXiv preprinl arXiv:2109. 12298, 2021.
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. arxiv preprint arXiv:2110.06500 2021.
Xinwei Zhang, Zhiqi Bu, Zhiwei Steven Wu, and Mingyi Hong. Differentially private sgd without clipping bias: An error-feedback approach. Xiv preprint ar xrXoo:2311.14632, 2023.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. preprint XrXiv:2001.028 02610,, 2020.
idlg: Improved deep leakage from gradients. arXiv
Yingxue Zhou, Zhiwci Steven WI, and Arindam Banerjec. Bypassing the ambient dimension: Private sgd with gradient subspace identification. arXiv preprint ar Xiw:2007.03813 2020.
A Appendix
A.1
Additional Related Works
Beyond the works presented in the main content, differential privacy with dimension reduction has received considerable attention recently due to the emerging data-centric deep learning techniques, which require privacy-preserving yet efficient learning. Inspired by DPSGD Bassily et al. (2014), Zhou et al. Zhou et al. 22020) proposed projected DPSGD performing noise reduction by projecting the noisy gradients to a low- dimensional subspace, which induced by the top gradient eigenspace on a small public dataset. Though PDP-SGD is theoretically and empirically validated well, the adoption of a public dataset may not be feasible some scenarios, particularly those being data privacy-critical. Another work Mireshhhallah et al. 2022) developed technique called differentially private model compression specifically for pre-trained large language models such GPT-2, leveraging knowledge distillation algorithm. However, the lightweight model comes at the cost of accuracy loss. To mitigate this issuc, the authors developed the diffcrontially private iterative magnilude pruning, which produces compressed models whose performance is comparable lo the original models. Similarly, the author from Kasiviswanathan (2021) found that with a constraint set, SGD can be operated with the lower-dimensional (compressed) stochastic gradients, and applicd it to differentially private learning with nonconvex functions to improve error bounds. However, the additive noise mechanism is still static such that the model performance gap cannot be shrunk along with iterations. In terms of
15

---

Published in Transactions on Machine Learning Research (09/2025)
differential privacy, the authors in Koloskova et al.
(2023b) proposed new stochastic optimization method that is coupled with linearly correlated noise and showed explicit convergence rates in both convex and non- convex objective functions. They also devised new objective for the offline matrix factorization, improving the convergence property. Du et al. Du et al. (2021) presented for the first time a dynamic differentially private mechanism for SGD that. can adaplively trade off between the utility and the privacy. However, implement. A more recent work Feng & Venkitasubraamaiiam (2024) proposed a novel differentially private optimizer by combining noisy SGD and randomized quantization, which is close to our work. They theoretically analyzed the utility-privacy tradeoff of the proposed scheme specifically convex losses and empirically showed results regarding the impact of different randomized quantization parameters. Unfortunately, there is no reported result on the nonconvex objectives using the developed method.
their additive noise mechanism involving an exponential function could be sophisticated
A.2 Additional Algorithms
In this section, we present additional algorithm frameworks degenerated from D2P2-SGD, including D2P- SGD (in Algorithm 2 and DP2-SGD (in Algorithm 3). We also list out the differences among these three
algorithrs in Table 3
Algorithm 2 D2P-SGD
1: Input: Model initializationxi, step size the number of epochs K, size of mini-batch B, training set
D, noise sequence o0,1:0?,2. "?....,,, for each & in to K do Split the dataset D into multiple mini-batches with size and randomly sample one
Clip the per-sample gradient e ()))l/
+ +7), E
Calculate the mini-batch stochastic gradient gk B E.- Sk
6: Perturb the gradient ge using dynamic noise: g.: gi + C2, where ~ ((0, Tp,
7: Update parameter using projected noisy gradient: X X agk
8: end for
Output: XK
Algorithm 3 DP2-SGD
1:
Input: Model initializationx,, step size the number of epochs K K,lower dimension p, random matrices
A1, A Ak, size of mini-batch B, training set D, noise variance o² 7
2: for each & in to K do
Split. the dataset D into multiple mini-batches with size and randomly sample one
Clip the per-sample gradient g Vf(x ( (x): + +7), B
Calculate the mini-batch stochastic gradient g: B Enm S
Project noisy gradient using AI gx A& ( gx ck), where eN o))
Update parameter using projected noisy gradient: X X agı
end for
Output: XK
Table 3: D2P2-SGD and its different variants.
Method
o
A
D2P2-SGD
2 1
dd
D2P-SGD
N/A
a:
I E Rdd
VB
DP2-SGD
2
Rdxp
16

---

Published in Transactions on Machine Learning Research (09/2025)
A.3 Proof for privacy guarantee
In this subsection, provide proof of the privacy guaranlee. Before that, we present some existing results to characterize the proof. We begin with a function defined in the following.
Definition 2. Denote by M randomized mechanism and by DD and 'D' two adjacent inputs. The parame- terized Rényi divergence between two distributions is defined as:
em(n) = supp D,, (MM())))())
[ (MDD)() )
(4)
s' 1 loglBo-M(Dn)
where (())(() refers to the density at 0 of this distribution.
With the above definition, the first result follows is from Theorem 2.1 in Abadi et al. (0016 Lemma 3. Let M Mr MM o oo Mi be defoned in an interactively compositional way, then for ony fized n 2
K
() - (M)
(5)
(M(T) is defined as in Definition
Proof. The proof directly follows from the proof of Theorem 2.1 (Composabilitty) in Abadi et al. (0016).
The K iterations of D2P2-SGD can be decomposed into K compositions of sub-sampled Gaussian mech- anisms with uniform sampling without replacement. We denote by G(a.) S(n, B). With the abuse of
notations, we denote by ě(π) the privacy-accountant functional of Eq. in Definition 2 Another lemma
in the following introduces sufficient and necessary condition for a mechanism to be (e, 6)- differentially private.
Lemma 4. Let M be randomized mechanism. M (c, DD if and only if 2 expl(n - 1)(em())) =)], for some 7) >
Proof. Let P= M(x) and Q M(x') for adjacent datasets x, x' and define the privacy loss random variable M()) = log Pr[P=[] Definition we know that
Pr[Q=[] We first show the sufficiency, i.e., if the condition holds, then M is (c, D)-D.. Based on
exp((n - (n) E e ())))
(6)
We then apply Markov's inequality to the privacy loss under P such that
EgnP e(n ((n-1)n())
Preur I(C) > é Pręur ( eln-1)e 5
(7)
c(a-1)6
Transforming the expectation under P to one under Q yields
Benp c (n- (101) = Eeno / (enns)) = expl(n 1)))(1))
(8)
Substituting Eq. to Eq. and simplifying it grants us the following
Preur L(C) { o
< expp((n1)exxa (7) 5.
(9)
The second inequality is based on the condition 8 2 exp((n- 1xp((n- (E)]. Thus, this implies Pr[L s| 8, which is equivalent to (c, 5)-D. We now show the necessity, i.e., If M is (e,8)-DP, then the condition holds
17

---

Published in Transactions on Machine Learning Research (09/2025)
for some 7, > 1. By the definition of (e, the privacy loss L satisfies Prewp(((s) > S 6. Then, we have for any c <>1 1
expl(e- - 1)em(c)) Bece ((c=)
elc-1)L
/
els-1)4
(10)
I.Sc
We next bound the integrals. For the first term, we have
J ele 1)4 S ( elc-1)e
While for the second integral, with the fact that dP = eQ and Pr(L > s) S ô, we can obtain
J( elc-1)L = I dl-22)L dp S sup;: el ()-
L>e
We will now optimize in the following to conclude the proof. The supca(()> ((--))(()) 2)4(() may be large, but for a fixed 8 > 0, there exists c <> (sufficiently close to 1) such that
expl(c- - 1)em(c)) (c- + H(c),
where Hc) is constant depending on c and 6. Therefore, we can rearrange the above relationship to obtain the following:
eM(c) Sst log(1 1 + Hc()))
c-1
Hence, for sufficiently large c, i..,, 1 + (22og(1/))/) this implics that d > exp[(c 1)(em(c) c): which completes the proof.
Before the formal proof for the privacy guarantee in Theorem we present another auxiliary tochnical lemma, which dictates the privacy amplification by uniformly sub-sampling without replacement.
Lemma 5. For the mechanism induced by D2P2-SGD, G(a.) o S(n, B), with < 1 the following privacy accountant holds:
10:
7B
de log 2
ε(σ)
Vn <
(11)
02n2
B
Proof. As per-sample gradients are clipped to la norm D2P2-SGD, this ensures the sensitivity A = for the mini-batel sum. Let q = B/n. n. Based on Lemma 3 from Abadi et al. (2016), we can obtain that
q²n + ε(π) s oā
3,5g²1² of
q²11 1 o?
3.5qm o?
The condition s o log(n/BB B) implies n v
_ log(1/g). As 1/4 < 1/10, then we have:
3.5qn 3.5q o² log(1/g) 10177/glll//// < 1.75 0.24 & 0.42.
a² o? 2
Hence, ē(n) < Iq'n which completes the proof.
With this in hand, we are now ready to prove Theorem 1 We restate il in the following for completeness.
Theorem 1: (Privacy) Let Assumption hold. There exist constants C₁ C2 > such that for any S C,B"K D2P2-SGD is (c, difffeeerentilllyy private for any 8 > 0, if o² > CyB*K3lu(1,)
n²ga
18

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. With the explicit form of noise variance we have defined in this work, i.e, o², = o2
K. immediately
obtained that 2² > 2²22 > > L Tf o²,k 2 CaB' Kln(14) then o², 2 CaB' (ln(1)) for all k. Thus, the
n²g²
n²g²
core of the proof has now turned to o.. As discussed before, D2P2-SGD can be treated as composition, denoted by M. In light of Lemma 3 and Lemma 5 it is easily obtained that
BK2B²n em(1) S o?nn
0 Vn
n1
log
(12)
2
B
K is due to the K iterations in D2P2-SGD and K < K2. Additionally, based Lemma can know 2
that D2P2-SGD is (c, 6)-DP if there exists I log B
such that
2
7K2 o,n²
(- 1)e
E// exp
(13)
It is now easy to verify that if C,B²k2/n²,, all these conditions can be satisfied by setting d. C.BK /1g(1//) for some explicit constants Ci and C2.
n5
A.4 Proof for convex objectives
In this section, we will present the convergence proof for convex functions. Differont from the traditional analysis to DPSGD, in D2P2-SGD, the difficulties and complexities of the proof arise from the matrix projection caused by Aş and the inner product between X x* and | The matrix product requires random projection propertics and the relationship with the outer product of vectors. While for the inner product between X - x" and gt Ia Ity we need to decompose gi to gi: V and Vf(xx). Also, we have
to handle the denominator ||g + which is a varying constant with ||g:|]
We start with a well-known result regarding the convexity is presented in the following to characterize the analysis.
If Rd + R is convex and differentiable, then for Lemma 6. (converily Garrigos & Gower (2023)) x,y E Rd,
f(x) 2 f(y) - (VS(y,,
(14)
Theorem 2: (Utility for convex functions) Let Assumptions and 2 hold. Suppose that f is a convex function and that a random matrix with each element being sampled from a normal distribution N(O0, ).). Also, let the additive noise of DP mechanism have the variance o2 If the step size S z. then for the itcrates {x K 2 1 generated by D2P2-SGD, the following relationship holds true
|X| 11
+ 1p 7InK + 1)o? + and 2 (1 + +
[[((x)) -1
(15)
2aKoa 2V
2K
where Xx DK Xt-
19

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. Let gi fxx;:s s) and define C.
||s +1 Using the update law we have:
[1||x+11 x [1 = B (ARl
Cagi + Ex) - xx11
B
[| 10 Ax
1
Ak
1
Σ
Cagi + - -211B( 1
A
1
Σ
Cogi ARE,, -
vp
B
B
[[[|x 1xx=xI11 11 +
E1
a|
A A
1 B
Σ Cegi + A&ch)1 (
B
x111
vp
VP
gg
+7
[E[[|x x"1 ||9 a
A& k
1
C.gt + ARCH)|1 [
1
poo1
gk
Xx: x 1
vp
B
VP
|g / +
= [B[|| x-11 + (
A Ak
1
E
Cggi + AREW)19 - 2a 2 (x -x",
gk
B
+
[[[|xx x [1
Ag Ak
C. g 1 a B1
/
[x(
xx,
gh
||
+
7
(16)
The third equality follows from that E[A = based on the Concentration Theorem for Projections Das- Øt 1|+T" According
gupta et al. (2012), the independence between A and g(xe), and E Σ. C.gāl =
to Lemma 2 know that E[A pa / Nabil (2017). which yields the fourth equality. The last equal-
ity follows similarly from [[[A<*] = 0. As [I A [|²] = P A R
S p Ei=n Elll AR. AR, [[,1 < - [1 [I = p²dPo' Also, |[|| || Elc AI ANCR] Bley BIA AnJeul = cg po IEN =
Elpo A 11 With |[C.gll I the following relationship holds:
8k vS((K) + (
B[][xe+1- 1 < B Bl||x x* 1|
+ a² 15 Po' + a² Q2ppo0a0en
20x /To' T
x",
gg +
vf((x)
$ E[l|x x1119] 25p d
a p 0 2 + 20 2oo -x:,
|g +
V (xx)
20 3Dr Xki gg +
}]
(17)
As Ejgx] VF fxxx), the last term the right hand side of the above incquality equals 0. Using Lemma and Cauchy-Schwartz inequality yields the following,
6
2002 AVP Elf f(xx)]
- - El|xx x +1 a
+
(18)
|gg +7
Then, we can obtain
200% 2 B(f(x))
+ El|x - xx xx1 a 222550o + + o2p² - (19)
gg +
Based on the definition of the clipping mechanism, we know that g + g lilllty ensures |ggb < for all k > 0. Therefore, diving both sides of the last inequality by following
2ag vF and applying ||gx|| < 1 produces the TRa ++
[[f(xx) - [4] E|[[x x-1 Xx+1 - -x11
o (1 + 7)
00 77)
(1 +77 +
+
2v
2
2
(20)
El[Ix - x"11 112 | x=13] (1 + +)++
(1+
ap..b 02 e +7)
2
2
2
20

---

Published in Transactions on Machine Learning Research (09/2025)
Summing over & from 1 to K and dividing both sides by K produces the following relationship:
K - 5 E|[[x] x²1 -(f()
ap +7)
apt.6 +
+7)
K
K Σ
Koppp (1 (1+7)+
+
Σ o
(21)
2
2K
Using Jensen's inequality f(xx) f (ie.,, xxxx)) k
Σx= k= E Exf(x*) f*1 completes the proof. ]
Corollary 1. With conditions defined in Theorem 2 when 0 (()) ) the following relationship holds true, i.e, [[I((k) f - O + kK).
Proof. Based on the conclusion from Theorem substituting a O (RR into it and applying the upper bound of the partial sum leads to the desirable result.
A.5 Impact of Privacy and Dimensions for Convex Functions
In this subsection, we derive the explicit impact of the privacy budget and dimensions, and p on the error bound and compare it to that in DPSGD. Recall the conclusion from Theorem 2 in the following:
E[f(xk) - f' | - (x(+
2aKo + 552-5(1 + 7lnK + 1)o² op
(22)
2K
2
Let D = ||x x=1 and set 7 = 0 for simplicity such that the last inequality can be rewritten as
op a + oopdo2).
-
(23)
aKoa AVD
K
Let o/ (²B1k2)n(1/8) n
C2 23/3 KlnK Vlu(1/8) and = ((). Also, based on Corollary
me
we set step size
1/2 P/R
Substituting o² C2, B, into the last incquality, have
1 VK
Dd
Vpln(1/8)
B[((k))
(24)
PO
dnns
Privacy Projection crror
Initialization error
The last inequality states that the error bound impacted by initialization error, privacy error, and pro- jection error. Recalling from Bassily al. 20144, know that the vanilla. DPSGD has achieved the optimal convergence rate of o LD
1+ y //n(1188)
Comparing the privacy errors in both D2P2-SGD
VK
and DPSGD yiclds that the former has roduced the negative impact of privacy error significantly due to the random projection, but at the cost of additional approximation error p3/20% caused by the random projec- tion. Additionally, the initialization error in D2P2-SGD is also impacted by the dimensions and p. With random projection, the tradeoff between utility and privacy in D2P2-SGD becomes more complex compared to DPSGD. This also requires careful selection of reduced dimension p and a proper sampling distribution for the projection matrix A in D2P2-SGD to achieve better performance.
A.6 Proof for non-convex objectives
In this subsection, we present the missing proof for the non-convex objectives. Unlike the convex setting, our non-convex analysis faces distinct challenges arising from the interaction between the inner product of batch gradient and stochastic gradient, (Vf(x)), 8x) and the random projection matrix product. To resolve these, we must simultaneously leverage: (i) the independence between random projections and mini-batch sampling, and (ii) triangle inequality decomposition of the gradient norms [ and ||g+]]
Theorem 3: (Utility for non-convex functions) Let Assumptions 1 and hold. Suppose that random matrix with each element being sampled from normal distribution (O G.)- Also, let the additive noise of
21

---

Published in Transactions on Machine Learning Research (09/2025)
the DP mechanism have the variance o. If the step size 22: and, then for the iterates {x) } K 2
generated by D2P2-SGD, the following relat ionship holds true
( f(x1)-f" aLp' o (InK + +1)
La + +7
(25)
Koaypa
K
Proof. Due to the smoothness condition, we have the following relationship:
I. 2
f(x++1) - fxx+) + (xx),,, xx+1 xx)
| - xx112
(26)
Also, we know that Xk+1 -a v
A
h E. C.g. tx).
Substituting the above equality into the smoothness equation yields the following relationship:
f(xx+1) S f(xx) + (xxx) -aAs(
AK C.si + Ex))
vp
(27)
2
||
E C.gi + cx)l2
Vp
B
Taking expectation on both sides, with the proof from Theorem we can obtain the following relationships
[xx+xx+))] - [x]( - aE (VS(x)))
A
C.si + AnEa)
VD
La²
+ 2
A B
Σ
Cogi + AREAl1?
< [[f((x)] - (xx),
1
A
Σ
C.gill
+
La
E
AR
Σ C.gill 2 + ||AAEx|1
/p
B
2
VD
B
= [[[(xx)] - AB (V/
1
A
1
Σ
C.g.ll
+
Laz
EE
A Σ C.gfl1
Laz
2 E
[I] Asea [|
vp
B
Vp
E[f(xx)] - (V(())
1
E[A
gk
+
La²
E
1 A
C.g.
+
La
E
Agcs |2|
Vp
||Ba||
+ ?
2
(28)
The second inequality is due to the expectation of AREa equal to 0, as shown in the generally convex case. From random projection property we know A[A,A]] = po 1 so we will have:
[xf(xx+1)] < [xf(xx)) )] a po (VF
g: + gk:
gg +
(29)
La
La
A A
C.
+
E
[1] AnEe [2]
Vp
B
2
As -a, b) < |||||||||| and g gh = || we have:
E[f(x*+1)] (lff(x)) ((xxx))){aaal) & gall
1g
La²
pd
1 +
La
p
-aypo E
gg + 7
||g
1gk
+
2
2
1g + 7
a Ig + |Bx|
(30)
Since
|gell Iy [
< 1, we have a Ell - gall |lg
lgg.
||ا < 3 gxlll
Hence, with
[x)())) gal || + || the following relationship can be obtained:
a a V[xx)) < Elf(xx) - f(xx+11) 2a 2 V - g+lll
La²
La²
(31)
+ 2 2o +
p² 20 + 3
gh ||
2
gx
+
22

---

Published in Transactions on Machine Learning Research (09/2025)
Dividing both sides of the last inequality by avpo3 yields:
E[f(x*) [x]V](
f(xx++1) V[xl - -B
avpo
(32)
Lavido
Lap
02
+
2
which is due to Tx
Bkll S 7. Since BI|| V (xx) gx
lll /EllV/((x))
1x1 - a Summing the last
VB equation over from to K and dividing both sides by K grants us the following relationship:
1
K
B
<
f(x))
+2-
+
La Laypdlo'
K Lophi
Σ 2
(33)
K
aoAyTR
VB
2
2K
k=1
k=1
With the fact that Σk= 2 S (Ink + 1)o2 and that the minimum is less than the average, the desirable result is obtained.
Corollary 2. With conditions defined Theorem 3 when a = O (x))) the following relationship hold V +
true, minke[u.K V(xx)( s 0
Ink K +
Proof. Using the conclusion from Theorem 8 and substituting the step size a into the conclusion yields the desirable result.
A.7 Comparison of the Clipping Bias
In this subsection, show the comparison among different methods for the clipping bias in Table 4 It suggests that our clipping bias is proportional to which is the same as in existing works. However, due to the adoption of per-sample gradient normalization, the stability constant, also affects the clipping bias. practice, 7 is a small positive constant similar to the one in the Adam optimizer.
Table 4: Comparison among different methods.
Method
Clipping Bias
Chen et al.
2020
Wasserstein distance
Koloskova
2023a
or a² f/a 15a
Xíao el.
2023
Bu et al.
2024
a a/r
D2P2-SGD
(Durs)
20 B +
0 is the clipping threshold;
A.8 Impact Privacy and Dimensions for Non-conver Functions
In this subsection, we derive the explicit impact of the privacy budget & and dimensions, and p on the error bound. Recall the conclusion from Theorem in the following:
f( a + 1), + La
20 /B
minkennxxBB[[V//(xx]]]]] <
+ 7.
(34)
Ko²
K
Let D = f(xi) fr such that the last inequality can be rewritten as
[[((xk) - [4] 00
D
+ ap 2/2
La TxdP
σ +7)
(35)
aKo
K
VB
23

---

Published in Transactions on Machine Learning Research (09/2025)
Let 0²-
C.B² 1BB2/" n=2²
C2 yP/2KlnR (I(11/6T and O(1). Also, based on Corollary
we set step size
1 dVR
Substituting C2 C, into the last inequality, have
Dd
Vpin(1/0)
Blf(xk)- -
(36)
VK
&ne
Projection
Clipping bius
Initialization error
Privacy
The last inequality reveals that the error bound is dictated by initialization error, privacy error, projec- tion error, and clipping bias. Different from convex functions, the asymptotic convergence for non-convex functions leads to the clipping bias, which worsens the utility when K is sufficiently large. When K is small, corresponding to the early phase of optimization, the tradeoff between utility and privacy dominates. Analogously, this requires a meticulous selection of dimension p and a proper sampling distribution for the projection matrix in D2P2-SGD to achieve better performance non-asymptotic convergence is favored. If y is set O 1 the clipping bias a, which resembles the result in Koloskova et al. (2023a)..
VK
A.9 Additional Results
All the experiments were conducted machine equipped with Intel Xeon Silver 4110 CPU and an NVIDTA Tilan RTX GPU.
A.9.1 Additional Datasets
Figure 7 shows the performance with ResNet20 Wang al. (2019a) the CIFAR-10 dataset. From the plots, observe that D2P-SGD slightly performs better than D2P2-SGD due to the random projection error in the error bound, which also deteriorates the performance of DP2-SGD. The dynamic variance mechanism plays a central role in enhancing performance closer to SGD. However, the tradcoff between random projection and privacy drives the performance of D2P2-SGD between those in D2P-SGD (upper) and DP2-SGD (lower).
In Figures and g rosults for the CIFAR-10 datasot are provided, showing a similar trend to the other datasets. We also compare them to disclose the impact of the reduction rate. The reduction rate is the number of dimensions that have been compressed in random projection. For example, if d 10000 and the reduction rate is 0.3, then
7000. The chosen hyperparameters arc: batch size = 1024, a, = 2.0, and dimension reduction rate = 0.3 in Figure g If we decrease the dimension reduction rate to 0.1 in Figure g we can observe that the performance is enhanced, but the privacy loss remains the same, which aligns with our findings in the main contents.
In Figure 10 when reducing ae 1.0, we can see significant accuracy improvement, but with a sacrifice of privacy loss instead. However, D2P2-SGD achieves the best performance over baselines and is favorably comparable to SGD. Similarly, for Figures [ 18 (KMNIST, EMNIST, MNIST), D2P2-SGD is favorably comparable to outperforms all baselines, which strengthens our clains.
A.9.2 Calculation of C₁ value
From Figures 2 and 3 given the batch size equal to 1024, the number of epoch 40, and the training data sizes 60000 and 73257, based on the upper bound for & Theorem [ =< Ci long as C₁ 314, & values for both datasets will remain within the bound.
n² we can obtain that as
A.9.3 Detail of network architecture
A.9.4
Hyperparameter Setup
In this section, we detail the key hyperparameters have used in this work. All hyperparameters are subject to manual tuning, though hyperparameter optimization method is likely beneficial for potential performance improvements.
24

---

Published in Transactions on Machine Learning Research (09/2025)
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
3.0
1.0
3.0
static
Testing Accuracy
0.8
2.5
dynamic
Training Loss
2.0
0.6
1.5
1.5
0.4
1.0
1.0
0.5
0.2
0.5
0.0
0.0
0.0
10
Epoch
Epoch
Epoch
Figure Comparison among different methods for CIFAR10 data with ResNet20: on the right side, the privacy loss shown for static and dynamic scenarios.
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
10
1.0
10
static dynamic
8-
Testing Accuracy
0.8
Training Loss
6-
0.6
0.4
0
0.0
10
20
30
40
10
20
30
10
20
30
Epoch
Epoch
Epoch
Figure 8: Comparison among different methods for CIFAR10 data with reduction being 0.3, with CNN: the right side, the privacy loss is shown for static and dynamic sccnarios.
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
10
1.0
10
dynamic
8
Testing Accuracy
0.8
8
Training Loss
6-
0.6
6
4-
0.4
4
2-
0.2
2
0
0.0
10
20
30
40
10
20
30
40
0
10
20
30
40
Epoch
Epoch
Epoch
Figure 9: Comparison among different methods for CIFAR10 data with reduction rate being 0.1, with CNN: on the right side, the privacy loss is shown for static and dynamic scenarios.
25

---

Published in Transactions on Machine Learning Research (09/2025)
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
3.0
1.0
2.5-
Testing Accuracy
0.8
Training Loss
2.0-
0.6
1.5-
0.4
1.0-
0.5-
0.2
0.0
0.0
10
15 Epoch
20
25
5
20
30
Epoch
Figure 10: Comparison among different methods for CIFAR10 data with CNN: training loss and testing accuracy.
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
1.0
2.5
Testing Accuracy
0.8
Training Loss
2.0
1.5
1.0
0.5
0.2
0.0
5
10
15
20
35
40
10
15
20
25
30
Epoch
Epoch
Figure 11: Comparison among different methods for KMNIST data with CNN: training loss and testing accuracy.
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
3.0
1.0
2.5
Testing Accuracy
0.8
Training Loss
2.0
0.6
0.4
0.2
0.0
5
10
15
20 Epoch
25
30
35
40
10
15
20 Epoch
25
30
35
40
Figure 12: Comparison among different methods for EMNIST data with CNN: training loss and testing accuracy.
26

---

Published in Transactions on Machine Learning Research (09/2025)
SGD
DPSGD
D2P-SGD
DP2-SGD
D2P2-SGD
3.0
1.0
2.5
Testing Accuracy
0.8
Training Loss
2.0
0.6
1.5
0.4
1.0-
0.2
0.0
5
10
15
20 Epoch
25
30
35
40
10
15
20
25
30
35
40
Epoch
Figure 13: Comparison among different methods for MNIST data with CNN: training loss and testing accuracy.
Table 5: Network architecture for FashionMNIST,, SVHN, and CIFAR-10 datasets.
Layer
Parameters
Convolution
16 filters of 3 x 3, strides 1
Average Pooling
2 x 2
Convolution
32 filters of x 3, strides 1
Average Pooling
2 x 2
Convolution
32 filters of 3 x 3, strides 1
Average Pooling
2 x
Convolution
64 filters of x 3, strides
Adaptive Average Pooling
1
Fully connected
64 units
Softmax
10 units
Table 6: Hyperparameters for experiments.
Hyperparameter
Value
Learning rate a
0.01
Clipping parameter 7 Batch size B
0.01
(256, 512, 1024)
Number of Epoch K Injected noise variance d.
40
3.0
Sampling variance
1
Percentage dimensionality reduction
0.7
Number of random seeds
27


Reviews:
[{"review_id": "aN5nDXcPs2", "reviewer": "Reviewer_uWeG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is easy to follow and well written. The proposed method seems reasonably designed and the authors support their method with both theoretical and empirical results. Although the method shows better performance in the empirical setting of the paper, I have some questionable things:\n1. How does Definition 3 support the use of random projection in DPSGD? In particular, why the preservation of distance is important?\n2. How does the random mapping in Definition 4 provide the mapping $h$ in Definition 4? What is the probability guarantee happening it?\n3. Performance comparison (e.g. Figure 2, 3) under the same $\\epsilon$ setting should be made. Is the proposed method performing better than baselines with the same $\\epsilon$? \n4. (minor) In section 3.1, line 5 or line 7 seem to indicate different sentences in the algorithm 1. For example Line 9 in the algorithm 1 is return $x_K$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies differentially private optimizer with focus on the trade-off between privacy, utility, and complexity. The authors propose D2P2-SGD algorithm, which combines the idea of random projection and dynamic noise variance. The method naturally encompasses the existing two methods. They provide theoretical results of the proposed method, including privacy bound and utility bound. Through empirical results, the proposed methods is shown to outperform other baselines when strong privacy guarantee does not needed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would request the authors to address my concerns listed in the Strengths and Weaknesses section above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L1gG4XThAQ", "reviewer": "Reviewer_b8zr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: A new method D2P2-SGD is proposed by combining DPP, automatic gradient clipping via per-sample normalization, and random projection. In particular, random projection is used to lower the dimensionality of gradients, which avoids excessive random noise being added for each dimension of the gradient. Experiments show the effectiveness of the proposed method. \n\nWeakness\n\n1. The core idea of the paper appears to be a straightforward combination of existing techniques—specifically, the dynamic differential privacy mechanism from Bu et al. (2024) and the random projection approach from Kasiviswanathan (2021). This integration, while practical, may come across as lacking in novelty or conceptual innovation.\n\n2. The theoretical contribution of the results is somewhat unclear. For instance, in convex optimization settings, it is well-established that DP-SGD can achieve the optimal convergence rate of $O(\\frac{\\sqrt{d\\log(1/\\delta)}}{n\\epsilon})$. In contrast, Theorem 2 in this paper presents a bound that depends on additional factors such as variance, iteration count, dimensions d and p, and other parameters. It would strengthen the paper to re-express the results in this standard form to enable a direct and meaningful comparison with known bounds in the literature.\n\n3. Another concern is the overall writing quality of the paper, which is inconsistent and contains numerous typos and grammatical issues. see below for more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents D2P2-SGD, a new differentially private optimization framework. The method integrates three key components: a dynamic differential privacy mechanism with decaying noise variance to reduce utility loss over time, automatic gradient clipping via per-sample normalization to stabilize updates without manual tuning, and random projection to lower the dimensionality of gradients, thereby reducing the amount of added noise and computational overhead. Privacy and utility guarantees are provided for the proposed method. Empirical evaluations on benchmark datasets demonstrate that D2P2-SGD significantly improves model accuracy compared to existing DP methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. page 3, Table 1, $K$ is not defined.\n\n2. page 4, a paragraph below Eq(1), the form of the automatic clipping mechanism seems not correct. Please check\n\n3. Definition of $\\epsilon$-DP is ot necessary since the paper focuses on $(\\epsilon, \\delta)$-DP\n\n4. Definitions 3 and 4 should be written as Lemmas.\n\n5. The explanation of random projection in the paper lacks clarity. The authors should provide a more detailed discussion, including illustrative examples or intuitive explanations to better convey how random projection contributes to the method.\n\n6. Section 3.1 primarily focuses on the description of Algorithm 1, but the comparisons with existing methods are interwoven into this section. For better clarity and structure, the comparisons should be presented in a separate subsection or paragraph.\n\n7. Smooth with modulus L is not defined. \n\n8. The paragraph below Thm1, line 9 should be line 6?\n\n9. Algorithm 1 output $x_K$, while Thm 2 focuses on $\\bar{x}_K$, is there any possible to consider $x_K$? \n\n10. There seems to be some problems with the discussion of Thm 2. There is no $\\sigma_{\\epsilon,k}^2$ in the bound of Thm 2. Further, Eq(10) is not given.  Besides, the tradeoff between utility and privacy should be more detailed. \n\n11. In Appendix A.3, Thm 1, 'Assumption 2(b)' should be 'Assumption 2'.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mlFmTLy9Im", "reviewer": "Reviewer_JbaZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Timely research : Improving the privacy-utility tradeoff in private optimization is an important topic of research.\n- Empirical Results: Extensive experiments across multiple datasets (FashionMNIST, SVHN, CIFAR-10) validate the method's superior accuracy compared to baselines.\n- Practical Relevance: The focus on reducing noise dimensionality via random projection is well-suited for large-scale models.\n\nWeaknesses:\n- Clarity Issues: The writing could be improved for readability, particularly in definitions (e.g., Definition 4 is ambiguous and lacks clarity on the random projection matrix).\n- Privacy Analysis Limitations: The privacy guarantee in Theorem 1 holds only for a restrictive upper bound on $\\varepsilon$, which counterintuitively tightens with more data. The impact of random projection stochasticity on privacy is not explicitly addressed, or not clear to the reader.\n- Missing Proof Details: The proof of Lemma 3 is not provided, and its source is unclear, undermining the privacy analysis.\n- Experimental Clarity: The near-identical performance of DPSGD and D2P-SGD in experiments is not explained, and hyperparameter tuning details are insufficient.\n- Dynamic Noise Rationale: The use of decreasing noise variance is not well-justified, especially since the privacy analysis seems to consider the worst-case (smallest) variance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission introduces D2P2-SGD, a novel differentially private stochastic gradient descent optimizer that integrates dynamic differential privacy (DDP) with automatic gradient clipping and random projection. This approach aims to balance privacy, utility, and computational complexity in large-scale deep learning models. D2P2-SGD employs a dynamic noise mechanism with time-varying variance and random projection to reduce noise dimensionality, coupled with per-sample gradient normalization for automatic clipping. The authors prove sub-linear convergence rates for both convex and non-convex objectives, matching standard SGD rates. Experiments on datasets like FashionMNIST, SVHN, and CIFAR-10 demonstrate improved accuracy over baselines (DPSGD, D2P-SGD, DP2-SGD) while maintaining differential privacy, though with increased privacy loss due to dynamic noise.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Improved Proof of Theorem 1 (Critical): Please, provide a complete proof of Theorem 1 with full bibliographical references for Lemma 3. Explicitly address the stochasticity of random projections in the privacy analysis to clarify its impact on the $(\\varepsilon, \\delta)$-DP guarantee.\n2. Clarify Definition 4 (Critical): Revise Definition 4 to clearly define the random projection matrix and its role in the algorithm, ensuring it is mathematically precise. In particular, with what probability does a random matrix like that satisfy the Johnson-Lindenstrauss property.\n3. Justify Dynamic Noise (Critical): Explain why a decreasing noise variance is used when the privacy analysis focuses on the smallest variance.\n4. Address Assumption 2: Isn't an exponent $2$ missing in the expectation ? Furthermore, I do not understand why this assumption is necessary given that we know the full noise distribution, which is Gaussian.\n5. Explain Experimental Results (Recommended): Discuss why DPSGD and D2P-SGD perform similarly in experiments (e.g., Figures 2 and 3). Provide details on hyperparameter tuning, especially given that DPSGD is known to be very sensitive to a poor hyper parameters choice.\n6. Highlight Convergence Proof Challenges (Recommended): If there are specific technical difficulties in the convergence proof unique to D2P2-SGD, highlight them to clarify the novelty of the analysis.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)