Dyn-D^2P: Dynamic Differentially Private Decentralized Learning with Provable Utility Guarantee

1 Introduction

Distributed learning has recently attracted significant attention due to its great potential in enhancing computing efficiency and has thus been widely adopted in various application domains [Langer et al., 2020]. In particular, it can be typically modeled as a non-convex finite-sum optimization problem solved by a group of n nodes as follows:

∗Corresponding author.

with fi (x) = 1 J ∑Jj=1 fi (x; j), where J denotes the local dataset size of each node, fi(x; j) denotes the loss function of the j-th data sample at node i with respect to the model parameter x ∈ Rd , and fi (x) and f (x) denote the local objective function at node i and the global objective function, respectively. All nodes collaborate to seek the optimal model parameter to minimize the global loss f (x), and each node i can only evaluate local stochastic gradient ∇fi (x; ξi) where ξi ∈ {1, 2, ..., J} is a randomly chosen sample.

Bottlenecks such as high communication overhead and the vulnerability of central nodes in parameter server-based methods [Zinkevich et al., 2010; McMahan et al., 2017] motivate researchers to investigate fully decentralized methods [Lian et al., 2017; Tang et al., 2018] to solve Problem (1), where a central node is not required and each node only communicates with its neighbors. We thus consider such a fully decentralized setting in this paper, with a particular focus on general and practical time-varying directed communication networks for communication among nodes. Decentralized learning involves each node performing local stochastic gradient descent to update its model parameters, followed by communication with neighboring nodes to share and mix model parameters before proceeding to the next iteration [Zhu et al., 2024]. However, the frequent information exchange among nodes poses significant privacy concerns, as the exposure of model parameters could potentially be exploited to compromise the privacy of original data samples [Wang et al., 2019]. To protect each node from these potential attacks, differential privacy (DP), as a theoretical tool to provide rigorous privacy guarantees and quantify privacy loss, can be integrated into each node within decentralized learning to enhance privacy protection [Cheng et al., 2018; Yu et al., 2021].

Existing decentralized learning algorithms with differential privacy guarantee for non-convex problems tend to employ a constant/fixed gradient clipping bound ¯ C [Yu et al., 2021; Xu et al., 2022; Li and Chi, 2025] to estimate the l2 sensitivity of gradient update and uniformly distribute privacy budgets across all iterations. As a result, each node injects fixed-level DP Gaussian noises with a variance proportional to the estimated sensitivity (i.e., constant clipping bound ¯ C) before performing local SGD at each iteration. However, our empirical observations indicate that the norm of gradient typically decays as training progresses and ultimately converges to a small value (c.f., Figure 1). This observation suggests that using a constant clipping bound to estimate l2 sensitivity throughout the training process may be overly conservative, as gradient norms are often smaller than the constant ¯ C, especially in the later stages of training. Therefore, the added fixed-level Gaussian noise becomes unnecessary and instead degrades the model accuracy without providing additional privacy benefits. The following question thus arises naturally: Can we design a decentralized learning method that dynamically adjusts the level of DP noise during the training process to minimize accuracy loss while maintaining privacy guarantee?

To this end, we develop a new dynamic differentially private learning method for solving Problem (1) in fully decentralized settings, which enhances model accuracy while adhering to a total privacy budget constraint. The main contributions of this work 1 are threefold:

• We propose a differentially private decentralized learning method with a dynamic DP Gaussian noise strategy (termed Dyn-D2P), tailored for general time-varying directed networks. In particular, each node adds noise with a variance calibrated by a dynamically decaying gradient clipping bound and an increasing per-step privacy budget appropriately allocated across iterations. This mechanism enables each node to apply dynamically decreasing noise, thereby enhancing model accuracy without compromising the total privacy budget.
• Theoretically, we investigate the impact of dynamic noise strategy on model utility for a general form of Dyn-D2P where clipping bounds and noise levels can be arbitrary sequences (c.f., Theorem 1), revealing the advantages of using dynamically decaying clipping bounds (c.f., Remark 1). By employing exponentially decaying sequences, we prove the utility bound of Dyn-D2P with explicit dependency on the network-related parameter, exhibiting a scaling factor of 1/√n in terms of the num-

1 Supplementary appendix can be found in our full version [Zhu et al., 2025].

• ber of nodes up to a bias error term induced by gradient clipping (c.f., Corollary 1). To our knowledge, this is the first provable utility guarantee in the realm of dynamic differentially private decentralized learning.
• Extensive experiments are conducted to verify the performance of the proposed Dyn-D2P. The results show that, under the same total privacy budget, Dyn-D2P achieves superior accuracy compared to its counterpart using fixed-level DP Gaussian noise, especially under strong privacy guarantees. Moreover, we validate the robustness of Dyn-D2P against certain hyper-parameters related to the varying rates of gradient clipping bound and per-step privacy budget, and verify the performance of Dyn-D2P over different graphs and node numbers, which aligns with our theoretical findings.

2 Preliminary and RelatedWork

Differential privacy. Differential privacywas originally introduced in the seminal work by Dwork et al. [2006] as a foundational concept for quantifying the privacy-preserving capabilities of randomized algorithms, and has now found widespread applications in a variety of domains that necessitate safeguarding against unintended information leakage [Li et al., 2020; Shin et al., 2018; Wei et al., 2021b]. We recall the standard definition of DP as follows.

Definition 1 ((ϵ, δ)-DP [Dwork et al., 2014]). A randomized mechanism M with domain D and range R satisfies (ϵ, δ)- differential privacy (or (ϵ, δ)-DP), if for any two adjacent inputs x, x′ ∈ D differing on a single entry and for any subset of outputs O ⊆ R, it holds that

where the privacy budget ϵ denotes the privacy lower bound to measure a randomized query and δ is the probability of breaking this bound. Note that a smaller value of ϵ implies a stronger privacy guarantee.

The following proposition provides the Gaussian DP (GDP) mechanism to ensure privacy guarantee.

Proposition 1 (µ-GDP [Dong et al., 2022]). Let f : D → Rd be a function and S be its l2 sensitivity. Then, drawing a random noise N from Gaussian distribution with N ∼ N (0, σ2 Id ) and adding it to f such that M(x) = f(x) +N satisfies µ-GDP if σ is set as

where µ is the privacy budget in the GDP framework, and a smaller value of µ implies a stronger privacy guarantee.

The above proposition shows that the variance σ of the added noise required to ensure µ-GDP is dependent on both privacy budget µ and sensitivity S. It should be noted that the above privacy guarantee in the sense of GDP can be transformed into the standard DP by the following proposition which shows that there is a one-to-one correspondence between ϵ and µ values when fixing δ.

Proposition 2 (From µ-GDP to (ϵ, δ)-DP [Bu et al., 2020]). A random mechanism is µ-GDP if and only if it is (ϵ, δ)-DP for all ϵ ⩾ 0, where

and Φ (·) is the Gaussian cumulative distribution function.

In what follows, we will review existing works related to achieving DP guarantees in machine learning and highlight the limitations in decentralized scenarios.

Decentralized learning methods with DP guarantee. DP guarantee is initially integrated into a centralized (singlenode) setting for designing differentially private stochastic learning algorithms [Abadi et al., 2016; Wang et al., 2017; Iyengar et al., 2019; Chen et al., 2020; Wang et al., 2020]. Further, DP guarantee is considered in distributed learning with server-client structures and the representative works include [McMahan et al., 2018; Li et al., 2019; Wang et al., 2023; Wu et al., 2020; Wei et al., 2020; Zeng et al., 2021; Wei et al., 2021a; Li et al., 2022; Liu et al., 2022; Zhou et al., 2023; Wei et al., 2023]. Recently, there have been efforts to achieve DP guarantees for fully decentralized learning algorithms. For example, Cheng et al. [2018; 2019] achieve DP in fully decentralized learning for only strongly convex problems. Wang and Nedic [2024] achieve DP in fully decentralized architectures by tailoring gradient methods for deterministic optimization problems. For non-convex stochastic optimization problems as we consider in this work, Yu et al. [2021] present a differentially private decentralized learning method (DP2 -SGD) based on DPSGD [Lian et al., 2017], which relies on a fixed communication topology and uses the basic composition theorem to bound the overall privacy loss. To have a tight privacy guarantee, Xu et al. [2022] propose a differentially private asynchronous decentralized learning method (A(DP)2SGD) based on AD-PSGD [Lian et al., 2018], which provides privacy guarantee in the sense of R´enyi differential privacy (RDP) [Mironov, 2017]. However, it should be noted that the aforementioned two algorithms [Yu et al., 2021; Xu et al., 2022] work only for undirected communication graphs which is often not satisfied in practical scenarios. Most recently, Li and Chi [2025] achieve DP guarantee as well as communication compression in decentralized learning for non-convex problems with the total privacy cost calculated via the moments accountant technique [Abadi et al., 2016], while their methods are only applicable to time-invariant graphs.

Learning with dynamic DP Gaussian noise levels. For the aforementioned differentially private decentralized methods designed for non-convex stochastic optimization problems [Yu et al., 2021; Xu et al., 2022; Li and Chi, 2025], the injected fixed-level noise may exceed what is actually needed for privacy requirements as training progresses, especially during the later stages of training, since their estimated sensitivity based on constant/fixed gradient clipping bound ¯ C may not reflect the actual value of sensitivity (c.f., Figure 1). The overestimate of sensitivity may, indeed, lead to a waste of unnecessary privacy budget during the training process [Wei et al., 2023]. Therefore, a tighter sensitivity estimate is useful for improving model accuracy without sacrificing privacy. There have been few works dedicated to tightly estimate the sensitivity in a dynamic manner. For instance, a scheme of decaying gradient clipping bounds has been employed to estimate the sensitivity in differentially private centralized learning [Du et al., 2021; Wei and Liu, 2021], resulting in a decreasing amount of noise injection. In the realm of distributed learning, a similar strategy of dynamic clipping bounds is utilized in [Andrew et al., 2021] to estimate sensitivity. Most recently, Wei et al. [2023] use the minimum of decaying clipping bounds and current gradient norms to estimate the l2 sensitivity, leading to a less amount of noise injection. However, these distributed methods [Andrew et al., 2021; Fu et al., 2022; Wei et al., 2023] only focus on server-client architecture and, most importantly, they do not provide any theoretical guarantee on model utility. In this paper, we aim to design a differentially private decentralized learning method that incorporates dynamic noise strategies in fully decentralized settings, and provide rigorous theoretical guarantee on model utility, as well as its utility-privacy trade-off.

3 AlgorithmDevelopment

In this section, we develop our differentially private decentralized learning methods using the Gaussian DP (GDP) framework as depicted in Proposition 1, which measures the privacy profile (ϵ, δ) in terms of µ according to Proposition 2. We consider solving Problem (1) over the following general peer-to-peer network model.

Network model. The communication topology is modeled as a sequence of time-varying directed graph G k = (V, E k ), where V = {1, 2, ..., n} denotes the set of nodes and E k ⊂ V×V denotes the set of directed edges/links at iteration k. We associate each graph G k with a non-negative mixing matrix P k ∈ Rn×n such that (i, j) ∈ E k if P k i,j > 0, i.e., node i receiving a message from node j at iteration k. We assume that each node is an in-neighbor of itself.

The following assumptions are made on the mixing matrix and graph for the above network model to facilitate the subsequent utility analysis for our proposed algorithm.

Assumption 1 (Mixing matrix). The non-negative mixing matrix P k , ∀k is column-stochastic, i.e., 1⊤P k = 1⊤, where 1 is an all-one vector.

Assumption 2 (B-strongly connected). There exist positive integers B and △ such that the graph formed by the edge set ⋃(l+1)B-1 k=lB E k is strongly connected and has a diameter of at most △ for ∀l ⩾ 0.

Now, we present our differentially private decentralized learning algorithm (termed Dyn-D2P) with a dynamic noise strategy, which works over the above general network model. The complete pseudocode is summarized in Algorithm 1. At a high level, Dyn-D2P is comprised of local SGD and the averaging of neighboring information, following a framework similar to SGP [Assran et al., 2019] which employs the PushSum protocol [Kempe et al., 2003] to tackle the unblanceness of directed graphs. However, the key distinction lies in the gradient clipping operation and the injection of DP Gaussian

Algorithm 1 Dyn-D2P

• 1: Initialization: DP budget (ϵ, δ), x0i = z0 i ∈ Rd , w0 i = 1, step size γ > 0, total number of iterations K, initial clipping bound C0 and hyper-parameters ρc > 1 and ρµ > 1.
• 2: for k = 0, 1, ...,K -1, at node i, do
• 3: Randomly samples a local training data ξ k i with the sampling probability 1 J ;
• 4: Computes stochastic gradient at zk i : ∇fi(zk i ; ξ k i );

5: Calculates the clipping bound by: Ck = C0 · (ρc)- kK ;

• 6: Clips the stochastic gradient:

• 7: Calculates the per-step privacy budget by: µk = µ0 · (ρµ) kK with µ0 the solution of (8);
• 8: Calculates the DP noise variance by:

• 9: Draws randomized noise N k i from the Gaussian distribution: N k i ∼N (0, σ2 k Id ) ;
• 10: Differentially private local SGD:

• 11: Sends (xk+ 12 i , wk i ) to all out-neighbors and receives (xk+ 1 2 j , wk j ) from all in-neighbors ;
• 12: Updates xk+1 i by: xk+1 i = ∑nj=1 P k i,j xk+ 12 j ;
• 13: Updates wk+1 i by: wk+1 i = ∑nj=1 P k i,j wk j ;
• 14: Updates zk+1 i by: zk+1 i = xk+1 i /wk+1 i .
• 15: end for

noise before performing local SGD. In particular, each node i maintains three variables during the learning process: i) the model parameter xki ; ii) the scalar Push-Sum weight wk i and iii) the de-biased parameter zk i = xki /wk i , with the initialization of x0i = z0 i ∈ Rd and w0 i = 1 for all nodes i ∈ V. At each iteration k, each node i updates as follows:

where γ > 0 is the step size and gk i is the clipped gradient (c.f., (5)). N k i denotes the injected random noise to ensure µk-GDP guarantee for node i at iteration k. This noise is drawn from a Gaussian distribution with variance σ2 k , calibrated according to the dynamic clipping bound Ck and perstep privacy budget µk. We note that the two key mechanisms in the proposed Dyn-D2P to achieve dynamic noise levels and enhance model accuracy include: i) dynamically decreasing clipping bounds (c.f., line 5 in Algorithm 1); ii) dynamically increasing per-step privacy budget (c.f., line 7 in Algorithm 1). The detailed design and motivation for these mechanisms will be explained as follows.

Dynamic decreasing clipping bounds. For differentially private decentralized learning algorithms, the gradient clipping operation is necessary for each node to bound the l2 sensitivity of local SGD update and inject noise accordingly calibrated with l2 sensitivity (i.e., clipping bound) and privacy budget. According to the previous discussion in Section 1 that the norm of stochastic gradient of each node typically decreases as training proceeds, we know that the stochastic gradient would not be clipped after some iteration k if we use the constant clipping bound ¯ C as Yu et al. [2021]; Xu et al. [2022]; Li and Chi [2025] did, thus resulting in adding unnecessary excessive noise calibrated with ¯ C in the later stage of training. To address this issue, we employ a dynamic gradient clipping scheme for each node to reduce the clipping bounds Ck across the updates. Compared to the fixed clipping bound ¯ C used in [Yu et al., 2021; Xu et al., 2022; Li and Chi, 2025], it can reduce the noise level after a particular k when Ck < ¯ C, which is beneficial for stabilizing the updates. In particular, we set the clipping bound Ck as Ck = C0 · (ρc)- kK , where ρc > 1 is the hyper-parameter to control the decay rate of the clipping bound, C0 is the initial clipping bound, and K is the total number of iterations.

Dynamic increasing per-step privacy budget. Given a total privacy budget, the existing differentially private decentralized learning methods [Yu et al., 2021; Xu et al., 2022; Li and Chi, 2025] uniformly distribute privacy budgets across all training steps. However, recent works [Zhu et al., 2019; Wei and Liu, 2021; Wei et al., 2023] point out that it is relatively easier to leak privacy at the initial stage of the training process, and it becomes increasingly difficult as the training progresses. To this end, we allocate a small privacy budget in the early stages and gradually increase privacy budgets, i.e., setting µk+1 ⩾ µk for all k ∈ {0, 1, 2, ...,K - 1}. In addition, according to (3), we observe that small (resp. large) µk means adding large (resp. small) noise. Therefore, setting µk+1 ⩾ µk implies adding large (resp., small) noise in the early (resp., later) stages of decentralized training, which helps improve model accuracy. The intuition is that at the beginning of training, the model is far away from the optimum, and the gradient magnitudes are usually large (c.f., Figure 1); larger noise is thus allowed and even helps to quickly escape the saddle point [Ge et al., 2015]. As training proceeds, the model approaches the optimum and the gradient magnitude converge, smaller noise is then desired to stabilize the update for convergence.

The following proposition provides a way for privacy accounting of dynamic non-uniform µk-GDP costs throughout the whole training process.

Proposition 3 (Composition theorem for GDP with varying µk [Du et al., 2021]). Consider a series of random mechanisms Mk for k ∈ {0, 1, 2, ...,K -1}, where Mk is µk-GDP, and each mechanism works only on a subsampled dataset by independent Bernoulli trial with probability p. After K steps by composition of Gaussian mechanism, M ≜ MK-1 ⊗ · · · ⊗M1 ⊗M0 satisfies µtot-GDP where

To this end, we set the per-step privacy budget µk as

where ρµ > 1 is the hyper-parameter controlling the growth rate of µk, and µ0 is the initial privacy budget. Given the target total privacy budget (ϵ, δ), the corresponding privacy budget in the GDP framework µtot can be obtained by (4). Substituting (7) into (6) with p = 1 J , we have

and µ0 can be computed using a numerical method such as binary search. With a specific value of µ0 and ρµ, the value of µk at each iteration k can be calculated by (7).

In addition, we provide two by-product differentially private decentralized learning algorithms (termed Dyn[C]-D2P and Dyn[µ]-D2P), which employ only dynamic clipping bound reduction method and dynamic per-step privacy budget growth method, respectively:

• Dyn[C]-D2P: we set the clipping bound Ck as Ck = C0 · (ρc)- kK (c.f., Algorithm 1), while maintaining the per-step privacy budget µk the same for all iterations, i.e., fixing µk = ¯µ, ∀k. By substituting µk = ¯µ into (6) in Proposition 3 with p = 1 J , we obtain the closed-form solution of ¯µ:

With specific values of Ck and ¯µ, we can calibrate the DP noise variance at each iteration by σk = Ck ¯µ = C0 ¯µ ·

(ρc)- kK . The pseudocode of Dyn[C]-D2P can be found

• in Appendix D in our full version [Zhu et al., 2025].
• Dyn[µ]-D2P: we set the per-step privacy budget µk as µk = µ0 · (ρµ) kK (c.f., Algorithm 1), where µ0 is the solution of (8), while employing the fixed clipping bound, i.e., Ck = ¯ C, ∀k. Therefore, the DP noise variance σk at each iteration can be calculated by σk = ¯ C µk = ¯ C µ0 · (ρµ)- kK . The pseudocode of Dyn[µ]-D2P can be found in Appendix D in our full version [Zhu et al., 2025].

It can be observed that, given ρc and ρµ, the noise decay rate of Dyn-D2P is faster than that of Dyn[C]-D2P and

Algorithm 2 General Form of Dyn-D2P

• 1: Initialization: DP budget (ϵ, δ), x0i = z0 i ∈ Rd , w0 i = 1, step size γ > 0, total number of iterations K, clipping bounds C0, ..., CK-1, and noise levels ˜σ · ˜σ0, ...., ˜σ · ˜σK-1.
• 2: for k = 0, 1, ...,K -1, at node i, do
• 3: Follows from line 3 and 4 in Algorithm 1;
• 4: Gradient clipping: gk i = Clip (∇fi (zk i ; ξ k i ) ;Ck );
• 5: Draws randomized noise N k i from the Gaussian distribution: N k i ∼N (0, ˜σ2 Id );
• 6: Differentially private local SGD:

• 7: Follows from line 11-14 in Algorithm 1.
• 8: end for

Dyn[µ]-D2P. We also present an algorithm termed ConstD2P as our baseline, which employs constant clipping bound (i.e., fixing Ck = ¯ C, ∀k) and uniformly distributes privacy budgets across updates (i.e., µk = ¯µ, ∀k) as usually did in most of existing DP-based decentralized methods [Yu et al., 2021; Xu et al., 2022; Li and Chi, 2025]. According to the values of ¯ C and ¯µ (c.f., (9)), the constant DP noise variance is ¯σ = ¯ C¯µ . The pseudocode of Const-D2P can be found in Appendix D in our full version [Zhu et al., 2025].

4 Theoretical Analysis

In this section, we theoretically investigate the impact of our dynamic noise strategy on model utility guarantee and provide the utility bound for proposed Dyn-D2P given a certain privacy budget. We first present a general form of DynD2P where Ck and σk can be arbitrarily predefined sequences (c.f., Algorithm 2). Different from Algorithm 1, we denote σk = ˜σ · ˜σk for convenience in subsequent analysis, and we term ˜σ as noise scale without loss of generality.

Then, we show that the DP guarantee for each node in Algorithm 2 can be achieved by setting the noise scale ˜σ properly according to the given total privacy budget (ϵ, δ) as well as the equivalent privacy parameter µtot, which is summarized in the following proposition.

Proposition 4 (Privacy guarantee). Let K be the total number of iterations. Algorithm 2 achieves (ϵ, δ)-DP guarantee for each node if we set the noise scale as

where µtot is the solution of (4) with µ = µtot.

Proof. Refer to Appendix C in our full version [Zhu et al., 2025].

Next, we make the following commonly used assumption for the utility analysis of Algorithm 2.

Assumption 3 (L-smoothness). For each function fi, i ∈ V, there exists a constant L > 0 such that ∥∇fi (x) - ∇fi (y)∥ ⩽ L ∥x - y∥.

Suppose Assumptions 1-3 hold, and assume that each persample gradient is upper-bounded, i.e., ∥∇fi (z; ξi)∥ ⩽ Λ. Then, we are ready to provide the following theorem to characterize the utility guarantee of Algorithm 2.

Theorem 1 (Model utility). If we set the noise scale ˜σ as in (10), Algorithm 2 can achieve (ϵ, δ)-DP guarantee for each node and has the following utility guarantee

[0, 1) are positive constants 2 depending on the diameter of the network △ and the sequence of mixing matrices P k , whose definition can be found in Lemma 2 in the appendix in our full version [Zhu et al., 2025], P k i (Ck) denotes the probability of a stochastic gradient being clipped with clipping bound Ck for node i at iteration k.

Proof. Refer to Appendix A in our full version [Zhu et al., 2025].

Remark 1 (On clipping bounds Ck). The clipping of gradients will destroy the unbiased estimate of the local full gradient for each node, resulting in a constant bias error (reflected by T2 in (11)). It is obvious that the smaller the clipping bound Ck, the greater the probability P k i (Ck) that clipping occurs at iteration k. Based on this fact, we know that in general, the bias term T2 in (11) will be small if Ck's are large and vise versa, given the same distribution of gradients. This implies that we can use large clipping bounds to reduce the bias term T2. However, this may make the privacy noise error term T1 in (11) become larger. It is thus essential to choose a proper sequence of Ck that could effectively balance T1 and T2. However, finding an optimal sequence of clipping bounds to achieve the best trade-off necessitates knowledge of the distribution of the stochastic gradient, which is impossible to obtain in practice. The existing literature [Andrew et al., 2021] points out that a noteworthy practical way is to keep the probability P k i (C k i ) approximately constant. Considering that the norm of the gradient is decreasing as training progresses, Ck should also be decreasing so as to keep P k i (Ck) roughly constant, which supports the design of our algorithm (c.f., Algorithm 1).

2 q characterizes the speed of information propagation over the network. A smaller value of q indicates faster propagation.

Next, we specify the sequences Ck and ˜σk in Algorithm 2, yielding a special instance of dynamic clipping bound and noise scheduling as used in Algorithm 1. We then provide the corresponding utility bound in the following corollary.

Corollary 1. Under the same conditions of Theorem 1, by setting Ck = Θ ((ρc)- kK ) and ˜σk = Θ ((ρc · ρµ)- kK ) for some ρc > 1 and ρµ > 1, if we set γ = 1 √nJµtot , γK = √nJµtot and assume that Jµtot > √n, we have

Proof. Refer to Appendix B in our full version [Zhu et al., 2025].

Remark 2 (Tight utility bound). Setting aside the nonvanishing bias term T2, the utility bound derived in Corollary 1 exhibits explicit dependency on the network-related parameter q, and reveals a scaling factor of 1/√n with respect to the number of nodes n, which has never been observed in the previous differentially private decentralized algorithms [Yu et al., 2021; Xu et al., 2022]. By setting n = 1 which corresponds to the centralized/single-node case, our utility result (12) can be reduced to O(1/Jµtot), sharing the same polynomial order as existing analysis [Zhang et al., 2017; Du et al., 2021]. To our best knowledge, we provide the first theoretical utility analysis for decentralized non-convex stochastic optimization with dynamic gradient clipping bounds and noise levels, highlighting the utility-privacy trade-off.

Remark 3 (Non-trivial analysis). The exponential decay scheme of the sequences Ck and ˜σk aligns with that of the sequences Ck and σk in Algorithm 1, up to a constant factor. Therefore, the theoretical result (utility bound) in Corollary 1 corroborates the parameter settings in Algorithm 1. We note that our analysis is non-trivial and can not be directly derived by extending the existing analysis [Du et al., 2021] for the centralized/single-node case. The authors in [Du et al., 2021] assume Ck and ˜σk to be constant when deriving utility bounds, thereby simplifying the analysis (c.f., Theorem 1 in [Du et al., 2021]). In contrast, our analysis involves a more precise setting of Ck and ˜σk as outlined in Corollary 1, which requires a more sophisticated analysis (c.f., Eq.(35) to (36) in the appendix in our full version [Zhu et al., 2025] for the derivation). We will also evaluate the impact of two hyper-parameters ρµ and ρc on algorithm performance in the experimental section. The fixed schedule for the clipping bound and noise level in Corollary 1 is not the only option for our general algorithm form (Algorithm 2). Exploring alternative dynamic clipping bound mechanisms-such as using more complex schedules than exponential decaying method or adaptive clipping bound calculated based on the real-time gradient norm-would require additional heuristic efforts and complicate the theoretical utility analysis. We leave these explorations for future work.

5 Experiments

We conduct extensive experiments to verify the performance of proposed Dyn-D2P (c.f., Algorithm 1), with comparison to our two by-product algorithms Dyn[C]-D2P and Dyn[µ]- D2P, and two baselines: i) Const-D2P, which employs fixedlevel noise; ii) non-private decentralized learning algorithm, which does not use gradient clipping or add DP noise, and thus serves as the upper bound of model accuracy. All experiments are deployed in a server with Intel Xeon E5-2680 v4 CPU @ 2.40GHz and 8 Nvidia RTX 3090 GPUs, and are implemented with distributed communication package torch.distributed in PyTorch [Paszke et al., 2017], where a process serves as a node, and inter-process communication is used to mimic communication among nodes.

5.1 Experimental Setup

We compare five algorithms in a fully decentralized setting composed of 20 nodes, on two benchmark non-convex learning tasks: i) training ResNet-18 [He et al., 2016] on Cifar-10 [Krizhevsky, 2009] dataset; ii) training shallow CNN model (composed of two convolution layers and two fully connected layers) on FashionMnist [Xiao et al., 2017] dataset. We split shuffled datasets evenly to 20 nodes. For communication topology, unless otherwise stated, we use a time-varying directed exponential graph (refer to Appendix E in our full version [Zhu et al., 2025] for its definition). The learning rate is set to be 0.05 for ResNet-18 training and 0.03 for shallow CNN model training. Privacy parameters δ is set to be 10-4 , and we test different values for ϵ which implies different levels of privacy guarantee. Other parameters such as ¯ C, C0, ρc and ρµ are detailed in Appendix F.1 in our full version [Zhu et al., 2025]. Note that all experimental results are averaged over five repeated runs.

5.2 Superior Performance against Baseline Methods

For the ResNet-18 training task, we present the experimental result of final model accuracy in Table 1, and provide the plots of training loss/testing accuracy versus iteration in Figure 2 with a privacy budget of ϵ = 1 (the plots with other values of ϵ can be found in Appendix G in our full version [Zhu et al., 2025]). It can be observed that our Dyn-D2P and two by-product algorithms (Dyn[C]-D2P and Dyn[µ]-D2P) consistently outperform the baseline algorithm Const-D2P which employs constant noise. Among these above DP algorithms, Dyn-D2P achieves the highest model accuracy while maintaining the same level of privacy protection. Furthermore, a comparison of experimental results with different privacy budgets (i.e., varying values of ϵ) shows that the stronger the level of required privacy protection (i.e., the smaller the value of budget ϵ), the more pronounced the advantage in model accuracy with our dynamic noise strategy. In particular, when setting a small ϵ = 0.3 which implies a strong privacy guarantee, our Dyn-D2P achieves a 25% higher model accuracy than Const-D2P employing constant noise strategies. These results verify the superiority of our dynamic noise approach.

For the shallow CNN training task, we present the experimental result of final model accuracy in Table 2, and provide the plots of training loss/testing accuracy in terms of iteration in Figure 3 with a privacy budget of ϵ = 1 (the plots with other values of ϵ can be found in Appendix G in our full version [Zhu et al., 2025]). The takeaways from the experimental results are similar to previous experiments on the ResNet18 training task, and our proposed Dyn-D2P performs much better than the baseline algorithm Const-D2P while maintaining the same level of privacy protection, which again highlights the superiority of our dynamic noise approach. In particular, under a strong level of required privacy guarantee with budget ϵ = 0.3, our Dyn-D2P achieves a 39% higher model accuracy compared to Const-D2P.

5.3 Sensitivity to Hyper-parameters

In this part, we test the robustness of our algorithm (c.f., Algorithm 1) to different values of hyper-parameters ρc and ρµ. We use grid search to demonstrate the impact of these two parameters on the final model accuracy. It follows from the results as shown in Figure 4 that, our algorithm can almost maintain the final model accuracy and consistently improve model accuracy compared to Const-D2P across a wide range of ρc and ρµ, which implies that our proposed algorithm is robust to the value of hyper-parameter ρc and ρµ.

5.4 Performance over Different Graphs and Node Numbers

First, we implement Dyn-D2P over a static directed ring graph, a time-varying directed exponential graph, and a fully connected graph, where the q value w.r.t. these three graphs decreases in sequence. The experimental result shown in Figure 5(a) demonstrates that the model accuracy (utility) increases in sequence across these graphs. Then, we implement Dyn-D2P on a time-varying directed exponential graph consisting of different numbers of nodes (refer to Appendix F.2 in our full version [Zhu et al., 2025] for more details on the setup). It can be observed from Figure 5(b) that, increasing the number of nodes improves the model accuracy (utility). Note that both of these above observations align with the theoretical insights outlined in Corollary 1 and Remark 2.

6 Conclusion

In this work, we proposed a differentially private decentralized learning method Dyn-D2P, for non-convex optimization problems, which dynamically adjusts gradient clipping bounds and noise levels across the update. The proposed dynamic noise strategy allows us to enhance the model accuracy while maintaining the level of privacy guarantee. Extensive experiments show that our Dyn-D2P outperforms the existing counterparts with fixed-level noises, especially under strong privacy levels. Our analysis shows that the utility bound of Dyn-D2P exhibits an explicit dependency on the networkrelated parameter and enjoys a scaling factor of 1/√n, up to a bias error term induced by gradient clipping. To our knowledge, we provide the first theoretical utility analysis for fully decentralized non-convex stochastic optimization with dynamic gradient clipping bounds and noise levels, highlighting the utility-privacy trade-off. We will focus on eliminating the bias term induced by gradient clipping in the future.

Acknowledgments

This work is supported in parts by the National Key R&D Program of China under Grant No. 2022YFB3102100, and in parts by National Natural Science Foundation of China under Grants 62373323, 62088101, U244120033, 62402256.