PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Authors: Jing Qiao
Yu Liu
Zengzhe Chen
Mingyi Li
YUAN YUAN
Xiao Zhang
Dongxiao Yu
Venue: ICML 2025 poster (2025)
Keywords: Decentralized unlearning
Primary area: theory->learning_theory

Abstract: This paper investigates decentralized unlearning, aiming to eliminate the impact of a specific client on the whole decentralized system. However, decentralized communication characterizations pose new challenges for effective unlearning: the indirect connections make it difficult to trace the specific client's impact, while the dynamic topology limits the scalability of retraining-based unlearning methods.
In this paper, we propose the first **P**rovable **D**ecentralized **U**nlearning algorithm under **D**ynamic **T**opologies called PDUDT. It allows clients to eliminate the influence of a specific client without additional communication or retraining. We provide rigorous theoretical guarantees for PDUDT, showing it is statistically indistinguishable from perturbed retraining. Additionally, it achieves an efficient convergence rate of $\mathcal{O}(\frac{1}{T})$ in subsequent learning, where $T$ is the total communication rounds. This rate matches state-of-the-art results. Experimental results show that compared with the Retrain method, PDUDT saves more than 99\% of unlearning time while achieving comparable unlearning performance.

PDUDT:
Provable Decentralized Unlearning under Dynamic Topologies
Jing Qiao Yu Liu'
Zengzhe Chen
Mingyi Li' Yuan Yuan 34 Xiao Zhang' Dongxiao Yu
Abstract
of their personal data in any form. For instance, users might wish to delete location information from navigation apps ask smart voice assistants to "forget" sensitive conversation content. Simply deleting data does not ensure the right to be forgotten, as its influence remains embedded in the col- laboratively trained models (Tao et al., 2024). Therefore, several studies have empirically explored ways to ensure the right be forgotten for collaborative learning, using techniques such as knowledge distillation (Wu et al., 2022a), class-discriminatiee pruning (Wang et al., 2022), projected gradient ascent (Wu et al., 2022b), or second-order AdaHes- sian optimizer (Liu et al., 2022).
This paper investigates decentralized unlearning. aiming to eliminate the impact of specific client the whole decentralized system. However, de- centralized communication characterizations pose new challenges for effective unlearning: the in- direct connections make it difficult to trace the specific client's s impact, while the dynamic topol- ogy limits the scalability of retraining- -aasd un- learning methods. In this paper, we propose the first Provable Decentralized Unlearning algorithm under Dynamic Topologies, called PDUDT. It al- lows clients to eliminate the influence of a spe- cific client without additional communication or retraining. We provide rigorous theoretical guar- antees for PDUDT, showing it is statistically in- distinguishable from perturbed retraining. Addi- tionally, it achieves an efficient convergence rate of (++) in subsequent learning, where 7 is the total communication rounds. This rate matches state-of- results. Experimental results show that compared with the Retrain method, PDUDT saves more than 99% of unlearning time while achieving comparable unlearning performance.
However, the existing works usually rely on a trustworthy central server for coordination, which is not always guaran- teed in real-world scenarios (Qiao et al., 2024). To further remove the dependence the central server, the researchers began to explore how to achieve efficient unlearning in full decentralized framework. For example, HDUS (Ye et al., 2024) uses distilled seed models to create erasable ensem- bles for all clients. Similarly, BlockFUL (Liu et al., 2024a) is novel framework with a dual-chain structure, compris- ing live chain and an archive chain, to enable unlearning in Blockchained FL. Although these studies provide prac- tical solutions for decentralized unlearning, the theoretical performance analysis still lacks in-depth exploration.
Therefore, we aim to design an efficient decentralized un- learning framework, while also theoretically guaranteeing the effectiveness and soundness of the unlearning process. To achieve this, we need to address the following challenges: (1) Indirect connections complicate the impact chain. In decentralized system, some clients may not be directly connected to the client initiating the unlearning request, yet they can still be influenced through the information flow. The complexity and unpredictability of model propagation paths make challenging to accurately trace and mitigate the influence of a specific client. (2) Dynamic topologies make retraining- methods infeasible. The con- stantly changing topologies among clients pose significant barriers to retraining based unlearming methods. Clients that have exited the decentralized system are often unreachable, making it infeasible to revert to an earlier training state (Tao et al., 2024) or retrain the model from scratch. This lack of access previously participating clients undermines the consistency and feasibility of retraining approaches, espe-
1. Introduction
With the surge in data volume and increasing geographic dispersion of data sources, some collaborative learning paradigms, such as Federated Learning (McMahan et al., 2017) and Decentralized Learning (Lian et al., 2017), have attracted widespread attentions. In the above collaborative scenarios, privacy regulations like GDPR (Voigt & Von dem Bussche, 2017) grant clients the right to withdraw the use
"School of Computer Seience and Technology, Shandong University, Qingdao, China *Zhongtai Securitics Institute for Financial Studies, Shandong University, Jinan, China 'School of Software, Shandong University, Jinan, China "Joint SDU- NTU Centre for Artificial Intelligence Research (C-FAIR), Shan- dong University, Jinan, China. Correspondence to: Yuan Yuan <yyuan @ edu.en.dd Xiao Zhang <xiaozhang @ edd.eedu.cn...
Proceedings of the nnnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Table Comparison with some related works
Theoretical guarantee
Dynamic
Algorithm
w/o retrain
Unlearning time
topology
Unlearning guarantee
Convergence rate
Space overhead
Comp.
Comm.
Fedlinssr (Läu al., 2021)
FedRemover (Yuan et ol., 2024)
FedUnl (Wa al., 2022a)
HIDU (Ye et al., 2024)
/
FATS-Unl (Tao ol., 2024)
Exact unlearning
10 Vaaltsa
> min(), A25)
- (b, d)) "OO maxx (K dy) (tgrid)
FodRecovery (Zhang et al., 202.3)
(e. ---machine untearning
O(G)
PDUDT (Thi paper)
(e.)hnnc unlearning
O())
O(6)
Note that "2" means result or not applicable, "SL." means "Severless", "RT" means "Retmining time", "1," is the round when client in the lenmiig system iseess an unlearning request, and N mox,, [N]] denotes the maximum number of neighters over rounds in deventralized learning syseem.
unlearning and space ownthea The original convergence rote in Tho al's paper shown O11/ VptVV For easy compariisnn,
calumns, consider
single
whether
elieni, needs perfoem unlearning openaions.
1, it further derived number clients purricipuiing each round training, and is the sample buich size used lo calculase the gradienl (in our theoretical resali, we ect 1), Their convergence result is for the total
of Algoeithm in their paper. Here, the
tmiining roudd. Since we hive proved the stafisical indisingsishahiiit of the unlearingg algunithm. we only focus on the evevergence behavior after the unlearning operation.
Tho et all's result relies on the time it takes to retrain the parameterized neural neework, which often much longer than curs. In their result, "R" demotes the total communication runns,, and it holds
n = T paper.
space overhead OR max(b, d]} for each cliest and O(R max (K, d)) for the server.
cially when client participation is voluntary and transient. (3) Global unlearning performance is difficult to quantify theoretically. In a decentralized setting, each client must independently "forget" the effects of a specific client locally. However, there is currently no unified metric to evaluate how these local unlearning operations collectively achieve the desired global unlearning effect. Without centralized oversight, ensuring that local actions align to produce the intended global impact remains significant open challenge.
dynamic topologies. It modifies local models using only historical information, eliminating the influence of specific client. Notably, PDUDT requires no extra communication or neural network retraining, ensuring high efficiency dynamic settings.
We provide rigorous theoretical guarantee for the PDUDT algorithm. First, we prove that it is statis- tically indistinguishable from the perturbed retraining method. Then, we derive that the subsequent learning process converges to the scaled difference among the unlearning models from all remaining clients at a rate of O +). which matches the state-of-the-art results.
Along this line, we propose a provable unlearning algorithm, called PDUDT, for the decentralized framework under dy- namic topologies. To make the whole system "forget" the unlearned client, each client locally uses its own historical gradient submissions, along with those of its neighbors, to perform unlcarning operations. Specifically, we compute sequence of gradient residual approximations using the expected retraining update rule. At the unlearning moment, we subtract the weighted sum of the corresponding approxi- mations from each client's model, where the weights mea- sure the clients' contributions to the system. This process only involves using saved historical information, with additional communication and training process, making it readily adaptable to dynamic topology settings. To provide a theoretically rigorous umlearning guarantee, we first de- rive an upper bound on the difference between the retrained model and the output model of the proposed algorithm from global perspective. Then, we use the Gaussian mechanism to mask this gap in the parameter space, ensuring statistical indistinguishabilityy Finally, we analyze the impact of the unlearning models on the subsequent convergence behavior of decentralized learning.
We conduct extensive experiments to verify the per- formance superiority of the proposed PDUDT algo- rithm. Specifically, compared with the Retrain method, PDUDT saves over 99% unlearning time, while main- taining outstanding unlearning performance.
2. Related Work
Depending on the precision of forgetting, existing unlearn- ing techniques the collaborative frameworks can cate- gorized into two types: Exact Unlearning and Approximate Unlearning.
2.1. Exact Unlearning
Exact unlearning requires that the clients in a collaborative system completely remove the influence of a specific client. To achieve this, the model typically needs to be retrained or partially retrained, which may incur high computational costs and time expenses (Liu et al., 2024b; Yuan et al., 2024; Tao et al., 2024). For example, one exact unlearning tech- nique is the leave-one-out retraining approach, where the model is retrained on the complete dataset, omitting the
Our main contributions can be summarized as follows:
To the best of our knowledge, we propose PDUDT, the first provable decentralized unlearning algorithm under
2

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
user's data that needs to be unlearned (Liu al., 2024b). FedRemover (Yuan et al., 2024) designs real-time mali- cious client detection scheme quickly perform unlearning operations and implement global model of unlearning in a minimum number of rounds. FATSS-nl (Tao et al., 2024) aims to backtrack to the point before the client who initi- ates the unlearning request first participates collaborative training, performing retraining to achieve exact unlearning. While these methods can fully eliminate the influence of specific clients, their implementation faces challenges. First, heavy reliance on retraining results in high computational overhead and time costs (Liu et al., 2024b). Second, due to the dynamic nature of client participation in collaborative training, recalling previous clients for retraining is often impractical (Zhang et al., 2023).
3. Decentralized Unlearning
3.1. Problem Setup
In this paper, we consider a decentralized learning scenario with n clients, denoted as V = (1. ... ,n). The communi- cation mode in round is modeled by a doubly stochastic matrix W (Wy)) )axn. where W7; 0 if client-i and client-j can directly communicate. Specially, we consider general dynamic scenario where the connections between clients can vary arbitrarily after each round, i.e., the neigh- boring set N = [ > 0, E V,j + i} of client-i and weight matrix W of clients vary with the rounds. All clients participating in the training collaboratively find a solution to the following general learning problem:
min f(0) DER
BE E:)
(I)
2.2. Approximate Unlearning
Approximate unlearning provides a more efficient solution, with methods that are typically faster and more computation- ally economical than exact unlearning (Liu al., 2024b). Although it may not completely eliminate the influence of specific clients, approximate unlearning is sufficiently ef- fective for most practical scenarios and meets the necessary requirements. Some works have been proposed to improve the understanding of federated approximate unlearning. Fed- Eraser (Liu et al., 2021) relies on the central server to store historical submissions of each client, which are then cal- ibrated to accelerate the unlearning process. FedRecov- ery (Zhang et al., 2023) provides a federated unlearning scheme to eliminate the influence of specific client by removing the weighted sum of gradient residuals from the global model.
In round t, each client-i receives gradients from all its neigh- bors, subsequently updating its model through local training that combines these gradients with its own local information according to the communication matrix:
0: = 1
Σ
W VE,O0 1) 3=1
(2)
After several rounds of training, client may submit an un- learning request withdraw its data consent. At this point, due to privacy regulations like GDPR (Voigt & Von dem Bussche, 2017), the decentralized learning system must re- move this client's contribution to the global model. Without loss of generality, assume client-n makes the unlearning request at round f1. Ideally, retraining by the n - 1 clients, excluding client-n, ensures that the contribution of client-n is fully removed, thus guaranteeing privacy. The retraining process can be expressed as follows:
Considering that the reliability of central servers in practical applications is often not guaranteed, researchers have begun to focus implementing unlearning in the decentralized frameworks (Wu et al., 2022a; Ye et al., 2024; Lin et al., 2024). For instance, HDUS (Ye et al., 2024) introduces a decentralized unlearning mechanism that leverages distilled seed models to construct erasable ensembles BlockFUL (Liu et al., 2024a) supports unlearning in Blockchained Feder- ated Learning, with an innovative framework featuring dual-chain structure. Similarly, Lin et al. (2024) addresses unlearning in privacy-preserving AIGC systems via coded computing, which requires additional storage and recon- struction overhead. While these studies offer practical so- lutions for decentralized unlearning, a thorough theoretical performance analysis remains underexplored.
0: = = 1J
Σ j=1
W
VP, (--1))
(3)
where we can set the initial model 0 0P. Theoretically, the communication matrix W = (W;) (m (m))xxx(-- (n-(1 can still be a doubly stochastic one. For example, the Metropolis- Hastings method (Awan et al., 2006) can be utilized to generate it. And we denote the neighbor set of client-i (i E V {n}) in round as N = [ > 0.j E Vinn). o t).
In Table 1, we provide comprehensive comparison of approach against some related works across multiple dimensions, including implementation architecture, com- munication patterns, theoretical unlearning guarantees, and efficiency metrics.
However, retraining from scratch incurs prohibitively high computation and communication costs. Therefore, our goal is to adjust the local model 8 for each client that continues training, so that from a global perspective, the adjusted models perform similarly to those retrained by n clients.
3

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Algorithm 1 The Perturbed Retraining Algorithm
Algorithm 2 Decentralized Unlearning Algorithm PDUDT
1: Input: The number of clients participating in retrain-
1: Input: The number of clients n, the initial local pa- rameters 6. 80 IR (i V), the round t when client-n submits unlearning request, the step size f) the privacy budget e, and the confidence parameter B.
ing n 1, the initial local parameters d 6f E Rd (i ()(n)), the round ( when client-n submits unlearning request, the step size 17. the privacy budget e, and the confidence parameter B.
2: for client i = 1. n (In Parallel) do
2: for client = 1, ... n 1 (In Parallel) do
3: for round = 1, 1, .t do
3: for round f = 1, 1,... 1 do
4: Compute and storage its VF, 5 -
local gradient
4: Compute its local gradient VP. -0
15 2)
5: Receive all the gradients V ( .5 UE
Et (1-1)
U
Receive and storage all its neighbors' gradients VF, (0) 0F, (j NY
1) from its neighbors;
6: Update each local model parameter following 0
Update each local model parameter following Of
0.
17
n-1
Σ
W
0:- Σ W P0 15-)
7: end for
7:
end for
8: end for
8:
Set o V2 Alg(1//) / (1/(3/ where d1 is
9: Receive the unlearning request from client-n.
the upper bound discussed in Theorem 4.9;
10:
for client i 1,... ... n
(In Parallel) do
9:
Add perturbation to each local model parameter
11: Compute the approximations (6:) of the gradi-
= 0 + 2,, where 2 ~ NO0 (n I))? a noise from the Gaussian distribution.
0
ent residuals by Equation (7);
12: Compute the weight P for each approximation 8
end for
0, 41 - 1) according to Equation (8);
13: Subtract weighted sum of 6 from 0 to obtain 0/
based on Equation (9);
3.2. Algorithm Design
14: Set
V2 (og(11/))+e- /lo((//3) where di is the upper bound discussed in Theorem 4.9; Add perturbation to each local model parameter 0N
When client-n issues an unlearning request in round t1, for any client-i (i E (n)) in the decentralized learning system, its local model can be expressed
15:
0:1 + 2i, where 2, ~ NO (n - 1)o²Ta) is a noise from the Gaussian distribution.
n
0-1 0- 0
W VF,
(4)
16: end for
j=1
the local model 0f by subtracting the accumulated gradi- Instead, we provide an approximation of the gradient residual r/. denoted by
Correspondingly, if retrained from scratch to round 4, for any client-i (i E Vi (n))))) it holds that
ent residual, i.e., 0²: - -ELo' rf.
0. 0
0:
(5)
n-1
5. = q
W (F).
n Σ W (C, (7)
To investigate the effect of client-n, we can subtract Equa- tion (4) from Equation (5), and have
However, this approximation 8f does not fully capture the intricate dynamics and interactions among clients during training, especially the influence of client-n over different rounds. To this end, we use P to denote the weight of 8 in the t-th round of the learning process. Since each client relies on the gradient information from its neighbors to up- date its local model, || Σソ= W ff, (0), E5) I|2 naturally weights the contributions client-i's neighbors' gradients in each round. Formally, pf is expressed as follows:
Wi V (0,
w VF, (0)
1=0
(6)
To make an adjustment the local model 0 of each client-i (i E ((n)), we introduce i
11 1Σ W V VE, (05, 5 1|2
()) E WH .{) to rep- resent the gradient residual. Calculating rf involves the trajectory dynamics of all neighbors of client-i obtained by retraining. Therefore, it is not feasible to directly adjust
P
(8)
2 Σイ= (0,, 1|
Therefore, when an unlearning request submitted by client-n in round f,, each client will perform the following
4

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
operation shown in Equation (9) remove the influence of client-n to the learning process over rounds.
Assumption 4.5. (Lipschitzian gradient). Loss function fi(.)s are with Lipschitzian gradients, i.e., For V0, & TR. it holds that
0. 01=0" 0
iE P
(9)
II V
Assumption 4.6. (Bounded variance). For any 0 E R the variance of the stochastic gradient is bounded follows:
To achieve the indistinguishabiliyy described in Defini- tion 4.1, we introduce random Gaussian noise to 0 and 0 to mask the gap between them. Specifically, Algorithm outlines the perturbed retraining method, while Algorithm 2 presents our proposed decentralized unlearning algorithm that does not rely on retraining. From global perspective, the output models of the two algorithms are indistinguish- able, as will be discussed in detail in Section 4.
E | (F((0,g) - V/((0) 1
E || V\(00- f 1
Assumption 4.7. (Symmetric double stochastic matrix). In each round t, the communication matrices W and W are real double stochastic matrices.
4. Theoretical Guarantee
Assumption 4.8. (Spectral gap). For any symmetric dou- bly stochastic matrices W and V aforementioned, we assume that Pt,1 max max[|A22 (W,, < 1 and Pt. = max (2 (1'A)((W),,, 1 [VV < 1. Specifically, we denote f1 max Pt, and P2 max Pt.2-
Before delving into the unlearning performance and conver- gence behavior, we present some definitions and assump- tions required for our theoretical analysis.
Definition 4.1. ((c, Jl--Imiisiinguushabiittt (Neel et al., 2021)): Let X and Y be random variables over domain R. We say that X and Y are (c, -y--Indisinguuihhbll if, for every possible subset S C R. the following holds:
4.1. Unlearning Performance
To explore the unlearning performance of Algorithm 2, we analyze the gap between
0 and - 0 in
Pr(X E ES) S exp(() Pr(Y E ES) +
Theorem 4.9. We then use Definitions 4.1-4.4 to estab- lish the statistical indistinguishabbiity between the two algo- rithms, as described Corollary 4.10.
Pr(Y E S) & exp(e) Pr(X E S) + B.
Definition 4.2. (Sensitivity (Dwork, 2006)): For a given
function q: D + R,,, the sensitivity A of g
Before obtaining the formal indistinguishabiiiy result, we first explore the difference between the average of the re- maining n 1 models in Algorithm 2 when client-n revokes data consent and the average model retrained by n- clients in Algorithm 1, as shown in Lemma B. of Appendix B. We then measure the weighted gradient residual approximation in Lemma B.2 of Appendix B. Based on these two lemmas, we can derive the following result for the gap between the averages
A = max ll - (D') ll. D
where D and D' differ in single entry. Definition 4.3. (Gaussian Mechanism (Bun & Steinke, 2016)): Given random variables X ~ [(1,, ola) and Y ~ N(H2, TaT, satisfying |l μn - -2² I A, then X and Y are (e, Indistinguishable if it holds
0 and
0
A
A
Theorem 4.9. Let
2 llg(11/))
2
D1 = - 22-12 T.2 pinti,
D2 = 1 - 36 1-36,236 L2p2(n - 1)t1,
Definition 4.4. (Client-Level (c, (e.cinM Unlearn- ing (Zhang et al., 2023)): An unlearning algorithm My satisfies (c, mammhhee unlearning with respect the learn- ing algorithm Mr if, for any possible subset of outputs S C Rd,, the following holds
Ej (6 + 4p1)p?
D3 = o + p2 +
(n-1)² 1)2
D1
2
8(1+ + +p?p?
E2 D2
Eg nD1
We can obtain the following result if the step size n satisfies
(M()) E S) S exp(e) Pr(Mo S)+
O mint
121.1
241.-
3612
P9)Mu E S) < exp(c) (V))))))))) E E) +
where Q denotes the set of cached statistics of each client, such as gradients and intermediate model parameters.
1
0 |I
im
5

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Considering that client-n has exited the collaborative learn- ing system, we replace f(-) in Equation (1) with f(),, which is defined as:
1107 + + + -B/(
[{EE((0)) - Bf Bf - 1)
f(0) 1 _ f((0), 0 DER"
(1I)
noo 1203 + |5(ES(09) - = Σ ))
As result, after eliminating the client-n influence through Algorithm 2, the convergence of decentralized learning in the subsequent T rounds is characterized by Theorem 4.
where
11 =(24n) n1t 1441 (F1 + F2 + Fz)+
Theorem 4.11. Let
(5 2p
1 D4 2
161j² L22 - 1)T
1 iL 2
D3
1/- - 144m/ L2 ntt (Li + 3E, 21zz + 48 (1+ +21
1 1-32 1/2 1)T
Dg 1--1--200 --0 L3 (3(n 1)T.
13 - 2887 L' nt (E1 + Es) + 192n(1 + p?)e?
If the step size satisfies f V 32L2 1yT it holds for
4 - 2881) 3 L' nt Ez
the subsequent T rounds of training:
1 =6 + 3n L- 121 L22 L2p
72n L33 12pints Duti
n-1
D1
D1
D4
11++
1/ = (1877n + 432n/* 2 -12 12222n2 Dzt
D2
T-1
n-1
8641 1.2 122pp1213 R2
Do
EI
Σ
VI()) 1?
1/2 = (36mmt1 +
D3
D1
1=0
1=1
3L
1
Σ
0 112 1++ 2(n
no
In Theorem 4.9, the terms o and of reflect the impact of random sampling. the terms I203 and [203 capture the local loss heterogeneity, and the remaining terms represent the decentralized training dynamics. And according The- orem 4.9, the formal indistinguishabiiiyy guarantee can be summarized as follows.
2Ds
n- 1=1
n-1 1=1
Σ 01)
20¹² L22 12 - 1)T
ifT
Do
16A L2 p2o 1)T
16 (n-1)Dg
Corollary 4.10. From a global perspective, our PDUDT and its early stopping variant PDUDT (ES) (described in Section 4.3) satisfies (c, (c,3)- -machine unlearning with respect to the perturbed retraining algorithm. For every possible subsel S C R. it holds that
De
We choose an appropriate step size nj in Theorem 4.9 to derive the following result.
Corollary 4.12. If the step size satisfies of n=1 and the number of training round further satisfies T z max 64(1-C)1, 1C),,, pi(n-1) (n - 1)L} with the constant C e
Pr(
n
0 E ES S eep(e))PPr(
1
Σ
n-1
0 E S)+B
1-2C
n
n
(0,4), the following holds for the subsequent T rounds:
1-1
T-1
Pr(
0 S) S expp(e)
0% E S)+B.
C.
1
Σ
E
V
Σ
0 12
T
1=0
s=1
4.2. Convergence Analysis
Σ
0 f
Lof
n-1
(1 2C
After each client-i (i E V((n)) eliminates the influence of client-n (Line 12 in Algorithm 2), we assume that it continues T rounds of decentralized collaborative learning with the communication topology W (t = 1,.... T)) To simplify the analysis, we regard 0/ as the initial model of each client-i (i E (n((n)) in these T rounds of training. Then the model update rules are as follows:
+
+
2T
n
2(n 1)2
16
(1 2C)
3(1 - C)L2 R-1
E ||
0
1
n-1 1
Σ
0 11
2
n
1=1
In Corollary 4.12, the bound sharply decreases as the num- ber of clients n - 1 and training rounds T increase. Specifi- cally, it indicates a rate of O converging to the scaled difference among the unlearning models from all n - 1 clients.
0.+1= = 0 -n
(0). {)
8. 00=00 8: (10)
j=1
6

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
4.3. Discussion
and subtract a weighted sum of oj from 0
obtain 0
In this part, we provide a discussion of our decentralized unlearning algorithm PDUDT regarding privacy considera- tions, unlearning time, space overhead, and early stopping benefits.
0: = 0
Σ
p. o iEVMn).
Furthermore, we can prove that the weighted gradient resid- ual approximation with early stopping is also bounded by the right-hand side of the inequality in Lemma B.2, as de- tailed in Appendix D.
Privacy considerations. Some works have shown that transmitting the raw gradient can also lead to privacy infor- mation leakage. Differential privacy technology. as the most commonly used privacy protection method for distributed learning, provides solution to this concern by adding noise to perturb the gradient. For these decentralized learning frameworks based on differential privacy, the perturbed in- formation of client-n can be regarded as its contribution to the system. As result, our proposed mechanism can still be used to eliminate the noisy impact of client-n.
5. Experiments
In this section, we evaluate PDUDT from many aspects, such as its statistical indistinguishabiliyy from the perturbed retraining algorithm, as well as its efficiency and effective- ness of unlearning.
Unlearning time. The proposed algorithm involves only simple operations (Lines 7-12 in Algorithm 2) to achieve unlearning. Let L, denote the training round when client-n submits an unlearming request. For each client, the time complexity to remove the contribution of client-n is O(t)). Specifically, subtracting the weighted gradient residual ap- proximation requires (t1) time, while computing the dis- tance dj and sampling noise from Gaussian distribution each require (1) time. Furthermore, the unlearning opera- tions are only performed on each client side, so the required communication overhead is O.
5.1. Experimental Setup
According to the complexity of the learning tasks, we train the CNN model for MNIST (Lecun et al., 1998) and Fashion- MNIST (Xiao et al., 2017) datasets, and the ResNet-18 model (He et al., 2016) for CIFAR-10 (Krizhevsky & Hin- ton, 2009) and SVHN (Netzer et al., 2011) datasets. To show the advantages of our proposed PDUDT algorithm, we compare it with some baseline methods, including Ori- gin (Lian al., 2017), Retrain, FATS- Unl (Tao et al., 2024), FedRecovery (Zhang et al., 2023) and HDUS (Ye et al., 2024). Multiple metrics are used to evaluate the perfor- mance of the proposed decentralized unlearning algorithm, including accuracy, unlearning time, communication over- head, and attack success rate. More details can be found in Appendix I.
Space overhead. The proposed decentralized unlearning algorithm requires each client-i to save the gradients of its neighbors. Let Nmax max;, |77) denote the maxi- mum number of neighbors over rounds .4 For each client, it costs (mz in memory space to perform the unlearning operations. Although N Nmax S al- ways holds, especially in the scenarios like social networks, the required memory increases linearly as the number of neighbors grows. To further reduce memory usage, each client may consider an early stopping strategy based on its resource constraints and model performance.
In our experiments, we work with total 10 clients. Specifically, in each round t, whether there is a connection between any two clients is randomly generated. Then, in order to ensure that the communication situation can be mod- cled as a doubly stochastic matrix, we use the Metropolis- Hastings method (Awan et al., 2006) to generate the com- munication weights among clients. Each client trains with batch size of 256 for 1 epoch per round, with step size of 0.001. The unlearning request from client-n is set to occur at round t 100. To save storage space, each client can apply an early stopping strategy by retaining its neighbors' information only for the first 80 rounds. After performing the unlearning operations, the remaining n - clients con- tinue training collaboratively for an additional 200 rounds. We conduct 100 membership inference attacks, presenting both the average performance and standard deviation.
Early stopping benefits. For neural networks in over- parameterization regime, the NTK theory (Lee et al., 2019) suggests that gradient-basee methods converge exponen- tially to zero training error, with minimal variation in the model's 'ss parameters (Zhang et al., 2023). Therefore, each client needs to store only the gradients of its neighbors for the first 1,, S 4 rounds to save memory. Under this setup, can redefine Lines 8-10 in Algorithm 2: each client- i computes the approximations {6) (6-) of the gradient residuals using Equation (7). Then, calculates the weight pf for every approximation 6% (t = 0, t1. 1) as
Our experiments are conducted using Py PoTch 2.5.1, Python 3.12, and Cuda 12.1. The experiments run on a cloud server equipped with an Intel(R) Xeon(R) Platinum 8358P CPU and 10 RTX 3090 GPUs, operating on Ubuntu 22.04.
Σ W VI, (0), 55) 1|?
' p Dhi プラ W ff E) IP2
7

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
MNIST
Deshion-MNIS
CIFAR-10
SVHN
0
0.69
0.6
Accurcyy
0.6
DOUDT
EDADT $30
0.6
PXUDT FOODY 330
0.4
FSUDT
PALDT 330
0.4
0.4
0.4
0.2
0.2
01.2
0.002
0.004
0.006
0.205
0,510
0.2
0.002
0.004
0.505
0.005
0.010
0.0
0.005
0.006
0.009
0.012
0.155
0.0
0.053
0.006
0.009
0.012
0.015
0
Figure 1. The accuracy of unlearned models using PDUDT, PDUDT (ES), and perturbed retrained models.
MNIST
Dishion-MNIST
CIFAR-10
SVHN
1.0
Accuricy
Ro
0.4
04
0.2
02
0.2
FOLIT
0.0
0,0
0.0
0.0
Cass
Class
Class
Class
Figure The accuracy on each class using PDUDT, PDUDT (ES), and perturbed retrained models.
of our PDUDT algorithm from the Perturbed Retraining method under varying noise scales a. Across all datasets, PDUDT achieves comparable accuracy to the Perturbed Re- training method under all noise conditions, demonstrating its ability to maintain statistical indistinguishabiiiy effec- tively. Similarly, PDUDT (ES), the ppace-saving version of PDUDT, also shows comparable performance, though with slight degradation in MNIST dataset. Overall, the results confirm that both PDUDT and PDUDT (ES) can maintain statistical indistinguishability with perturbed retrained mod- els across all noise conditions.
Table Comparison of the unlearning time across different learning methods.
Unleaming time (s)
Method
MNIST
Fashion-MNIST
CIFAR-10
SVHN
Retrain
1322,2
1299.8
1696.2
2747.8
FATS-Ual
573.6
573.4
884.0
1233.2
FedRecovery
3.5
3.9
8.5
HDUS
19.3
19.9
24.1
38.0
PDUDT
3.0
3.3
9.6
9.8
PDUDT (ES)
2,3
2.6
7.5
7,8
2) The Effectiveness of Unlearning: tiveness of PDUDT and its space-saving version PDUDT (ES), we record the average accuracy on each class. In this experiment, data from class 9 is exclusively owned by the client who requests unlearning. Therefore, the unlearning performance can be assessed based on the accuracy of this class. From Figure 2, it can be observed that both PDUDT and PDUDT (ES) maintain high performance on Classes 0-8, while their accuracy drops significantly on Class 9, exhibiting behavior similar the retraining method. This demonstrates that PDUDT and PDUDT (ES) effectively en- able the entire system to forget what it has learned from the client initiating the unlearning request.
To evaluate the effec-
Table Comparison of the attack precision of MIA across differ- ent unlcarning methods.
Attack precision (%i
Method
MNIST
MasIion-MNIST
CIFAR-10
SVHN
Origin
65.3 0.9
67.1 1.9
65.3
68.1 1 0.5
Retrain
49.4
2.2
51.0 0.6
49.5 0.7
FATS-Unl
51.3 1.2
1.3
51.81. 1.6 13.1=12
FedRecovery
0.71
4.94
0.6
0.3
HDUS
60.2-+1.11
6..2++U.7
50.6+0.3
51.2 1..2+133
PDUDT
49.9 0.6
49.0
50.1 1.6
51.3 1.33-0.33
0.3
PDUDT (ES)
50.8 11.8:00. 0.6
0.9
51.1
51.51.4
5.2. Experimental Results
To verify the efficiency of PDUDT and PDUDT (ES), we evaluate the time required for unlearning operations. In Table 2, our PDUDT and its space- saving version PDUDT (ES) show impressive performance in both unlearning time. Specifically, they reduce unlearning time by over 99% compared to the Retrain method. The time consumption of FedRecovery, HDUS, PDUDT and PDUDT (ES) primarily arises from computing gradient residuals or
3) The Efficiency of Unlearning:
Statistical indistinguishabiiit:: To examine the effect of different noise scales on the statistical indistinguishability between unlearned models and perturbed retrained models, we vary the values of from 0.001 to 0.015. The perfor- mance is evaluated in terms of the average model accuracy. Specifically, we start decentralized learning from pre-trained models to control the injected noise and ensure good perfor- mance. Figure illustrates the statistical indistinguishability
8

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
the stored distilled seed models ensemble. In contrast, the time consumption for Retrain and FATS-Unl is mainly due to parameter training within the networks.
References
Awan, A., Ferreira, R. A., Jagannathan, S., and Grama, A. Distributed uniform sampling in unstructured peer-to- to- peer networks. In Proceedings of the 39th Annual Hawaii International Conference on System Sciences (HICSS volume 9, pp. 223c-223c. IEEE, 2006.
4) The Performance of MIA on Unlearned Models: In this experiment, we conduct 100 membership inference at- tacks, presenting both the average performance and standard deviation across different unlearning methods. As shown in Table 3, the MIA achieves high attack precision on the original models, indicating that the attacker can successfully determine whether the target client's data was used during training. In contrast, after unlcarning, its attack precision drops to approximately 50%, demonstrating that the pro- posed unlearning methods successfully remove the impact of the target client. Notably, the performance of PDUDT and PDUDT (ES) is comparable that of Retrain and FATS- Unl, highlighting that our PDUDT and PDUDT (ES) meth- ods achieve similar unlearning effectiveness without relying on retraining.
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pp. 635-658. Springer, 2016.
Dwork, C. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegus, NV, USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016.
6. Conclusion
Krizhevsky, A. and Hinton, G. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
In this paper, we propose the first provable decentralized unlearning algorithm PDUDT under dynamic topologies. Theoretically, we derive its statistical indistinguishabiliy and the convergence of its subsequent learning process. We conduct extensive experiments to verify the performance superiority of the proposed unlearning algorithm.
Lecun, Y., Bottou, L.,, Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Pro- ceedings of the IEEE, 86(11):227-2334, 1998. doi: 10.1109/5.726791.
Our work inspires future research on provable decentralized unlearning. paves the way for investigating adaptive mech- anisms that enhance unlearning efficiency under dynamic topologies and for extending the unlearning framework to broader decentralized paradigms.
Lee, J., Xiao, L.. Schoenholz, S., Bahri, Y., Novak, R., Sohl- Dickstein, J., and Pennington, Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Acknowledgements
Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J,, Zhang, W., and Liu, J. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
This work was supported in part by Joint Key Funds of National Natural Science Foundation of China under Grant U23A20302 and U24B20149, in part by the Na- tional Natural Science Foundation of China under Grant 62202273 and 62302247, in part by the National Key Re- search and Development Program of China under Grant No. 2022YFF07122 12100, in part by the Postdoctoral Fellow- ship Program of CPSF under Grant GZC2023146/ 4600, in part by the China Postdoctoral Science Foundation under Grant 2024M761806.
Lin, Y., Du, H., Gao, 7., Yao, J., Jiang, B., Niyato, D., Li, R., and Zhang, P. Decentralized unlearning for trustworthy ai- generated content (aige) services. IEEE Network, 2024.
Liu, G., Ma, X., Yang, Y., Wang. C., and Liu, J. Fed- eraser: Enabling efficient client-level data removal from federated learning models. In 2021 IEEE/ACM 29th in- ternational symposium on quality of service (IWQOS),
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
pp. 1-10. IEEE, 2021.
Liu, X., Li, M., Wang, X., Y., Ni, W., Li, L.,, Peng, H., and Liu, R. Decentralized federated unlearning on blockchain. arXiv preprint arXiv:2402.1 16294, 2024a.

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Liu, Y., Xu, L., Yuan, X., Wang, C., and Li, B. The right to be forgotten in federated learning: An efficient realization with rapid retraining. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pp. 1749- 1758. IEEE, 2022.
Ye, G., Chen, T., Hung Nguyen, Q. V., and Yin, H. Het- erogeneous decentralised machine unlearning with seed model distillation. CAAI Transactions Intelligence Technology, 2024.
Yuan, Y., Wang, B., Zhang, C., Xiong, Z., Li, C., and Zhu, L. Towards efficient and robust federated unlearning in iot networks. IEEE Internet of Things Journal, 2024.
Liu, Z., Jiang, Y., Shen, J. Peng, M., Lam, K.-Y., Yuan, X., and Liu, X. survey on federated unlearning: Chal- lenges, methods, and future directions, ACM Computing Surveys, 57(1):1-38, 2024b.
Zhang, I.., Zhu, T., Zhang, H., Xiong, P., and Zhou, W. Fedrecovery: Differentially private machine unlearning for federated learning frameworks. IEEE Transactions Information Forensics and Security, 2023.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effiice learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Neel, S., Roth, A., and Charif--aalvajerde S. Descent-to- delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021.
Netzer, Y., Wang, T., Coates, A., Bissacco, A., Wu, B., Ng, A. Y., et al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop on deep learning and fnsupervised feature learning, pp. 4. Granada, 2011.
Qiao, J., Zhang, Z., Yue, S., Yuan, Y., Cai, Z., Zhang, X., Ren, J., and Yu, D. Br-defedrl: Byzantine-robus decen- tralized federated reinforcement learning with fast conver- gence and communication efficiency. In IEEE INFOCOM 2024-IEEE Conference on Computer Communications, pp. 141-150. IEEE, 2024.
Tao, Y., Wang, C.-L., Pan, M., Yu, D., Cheng, X., and Wang, D. Communication efficient and provable federated un- learning. Proceedings of the VLDB Endowment, 17(5): 1119-1131, 2024.
Voigt, and Von dem Bussche, A. The eu general data protection regulation (gdpr). Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152676): 10-5555, 2017.
Wang, J., Guo, S., Xie, X., and Qi, H. Federated unlearning via dlus-diisriminaaiiee pruning. In Proceedings of the ACM Web Conference 2022, pp. 622-622266622 222-632,70 2022.
Wu, C., Zhu, S., and Mitra, P. Federated unlearning with knowledge distillation. arXiv preprint Nii::2201.09441 2022a.
Wu, L., Guo, S., Wang, J., Hong. Z., Zhang, J., and Ding, Y. Federated unlearning: Guarantee the right of clients to forget. IEEE Network, 36(5):129-133 2022b.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1708:00777777 2017.
10

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Appendix A summarizes the main notations in this paper.
Appendix B lists some important theoretical results, including Lemma B.1 and Lemma B.2.
Appendix C shows the proof of Lemma B.I.
Appendix D shows the proof of Lemma B.2.
Appendix E shows the proof of Theorem 4.9.
Appendix shows the proof of Corollary 4.10.
Appendix G shows the proof of Theorem 4.11.
Appendix H shows the proof of Corollary 4.12.
Appendix I shows the experimental details, including datasets and models, baseline methods, metrics and additional experimental results.
A. Notation Table
Table 4. Notations and descriptions.
Notations
Descriptions
The time when client-n issues an unlearning request
The step size for Algorithms 1-2
The noise scale Algorithms 1-2 The privacy budget of indistinguishability The confidence parameter of indistinguishabiiity
B
0
The local model of client-i in round (t ... (1) in Algorithm 1
8
The local model of client-i in round (t = 1..... ,,,) .t)) in Algorithm 2
g
The perturbed retrained model of client-i in Algorithm 1
r
The gradient residual in round i. related to client-i's ss neighbors' information The approximation of the gradient residual rł in round t, which is computed by client-i The weight of 6%. which measures the contributions of client-i's neighbors' gradients in round /
pl
0:
The local model of client-i after removing the influence of client-n based Equation (9)
8t
The unlearned model of client-i i in Algorithm 2
The local gradient of client-i related to model 0 and sample E in round I.
B. Some important theoretical results
Before obtaining the formal indistinguishabiiity result, we first explore the difference between the average of the remaining models in Algorithm 2 when client-n revokes data consent and the average model retrained by clients in Algorithm 1, as shown in Lemma B.1. We then measure the weighted gradient residual approximation in Lemma B.2.
Lemma B.1. Let
D1 = 1--1 pint
D2 = 1 - -2nn L2 1)t1.
If0 < n < minf
121 V 2113 36L3)3(n-1)4, }. it holds that
1
1 n-1
1
0:
n
n
T.2 + 144n 1,3o(t4) ( 16+100000
ea s(++iiee + 87) 22f) 48 + 04)
+ D2
+
144m"L20334
(6+4p2l0f2 D2
30²(a-1)
+ 1611 1011+pf00 23004 1² 1p Dr
576n 12 (3+
<
D2
D.
1920(1+2i1cc
(E)( E Σ 0(1) +
288m 1 pá 1) (Ef(0") E + Σ 0)
D2
Lemma B.2. Let
Dj 1 24 T?2 p2pnti,
D2 = 3. - 1)41

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
1
D3 - pi + P2 + (n
1)2"
If0 < <1 < minly 121.444 V piti V 3622 36L=pg(n-111
136 }. the norm of the weighted gradient residual approximation (with
early stopping, discussed in Section 4.3) holds that
ΣΣ
t=0
n n-1 11
(Early stopping:
p. II)
n-1
1=0
6(72n 2 - 12n" Li'ppppp 12ppnnts
+
?2n 12n"'1"pp pint
D2o + (181)n+ +
432n' 12ppin" 11
Dz02t9+
D1
D3
D2
(36mml) + L2 (3(B
- R Σ 02))
C. Proof of Lemma B.1
Based on Equation (5), (9), (4) and (7), we can directly obtain Equation (12)-(15):
4-1n-1
0
2)
(12)
n
1=1
n-
n n
0
T
(0,
Σ
Wt ny
(0) En00
n1
n
8
V
(0 j. ()
Wt VF, (0..55) Σ p1
(13)
n
h-11
0
7
VF (
Σ
FF (0),
(14)
n
n-1 1=0 f=
1=1
t= j=1
1-1
m-1R-1
a n2
n Σ
6
W1 (0,,
"
ΣΣ
W (O,
"
Wt V (0) (t)
n1
n
nj
j=1
5=1
VF
(8,, - (F. (h)
(15)
n
Substitute Equation (15) into Equation (13) get
n
t
7 4-1
00
1
(0,
FV (. + (1
- p1)0
(16)
n
n
n
i=1
Consider the gap
n-1
0
11-
n1
f--1 1
7
(O 4-)
(0, 55
Wt V (0)
1=
1=0 j=1
f- n-1
f--
77
(FF,
(F,(0,))))
Wt nJ
VF, (8), (F,
(17)
n
j=1
1=0
12

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Then we have
n
hh ||
n
1=1
2
E
V55(0) + V1 V.3(
Σ
0)
1
1 Σ 03)
1=
1=1
Vsf( n1 1 1=1
1
Σ 83)
n-1
1
Σ
n-1
07) + V
n-1 Σ
8))
+ ( V - (3) I|
12
1
1 j=1
12
j=1
2
4-1
E
Why VF,(0 5))
1
Σ
VF, 00, {3) + ト Σ
- - <h 11?
(n 1)2
j=1
224 +
12t
4- 1a-1
E 01
1
Σ
12
12t
B
05
Σ 03 12
n 1
1= j=1
j=1
1=0
j=1
L2t 4-1 Σ
1
L2th
41-1 11-1n- n-1 n n Σ
1 3
E 8%
12+
+
E 11 0
1
(n 1)3 t=0
n i=1
11 1=1
t=
412h 4-1
1s GG 11 + (n 1)2
41
1T
E | (c Wt
E
n
G 1|
(n- 1)2 1=0
t=0
224 +
127 4-laa1
Σ
E ||| 8
1 n-1
Σ
0
11
12my 12 L2t
ΣΣ
4-1r-1
E
1
0
1 n-
0
112 +
n1 1
n
n
n2
1
1= 1=1
i=1
1= 1=1
122 4-11: n
n
41 + R7)
4--1
Σ ΣΣ
E
||
8
n Σ 0 11
Σ E Gi Him) + ((()) 11
(18)
n n-1
(n- 1)2
t=
Bound E || G - H + H 11::
E || G - H())) + H(m) 1|
2 E (F, f(()))) 1
n
Vla( E V)
Σ
x
0
V -
n Σ 09) V
n
_
Σ 0
n
+ V
/
1 n
の
12
n
1 n
22no + 6T.22 Σ
E ||
0
Σ
0
12
+ono + 6n. ||
4 n
Σ
0 11
(19)
1
Bound E |1 05
1
Σm-1 0 112:
n
n
E
0
0: 1|
--1
-EI |1
VF,
(0, 2)
Σ
VF 1
1=0
1=1
[-1
=1/2E 'E
W 1) - -1 1) + H (m))))) 1|2
n
1-0
t-1
<2n
E
ह
( (- - H)(m-))) 112 +
Σ
E ||
--
- H (n-1) 112 +
-
n-1
1=
1
13

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
1-1 1--1 Σ
fn-1 n 1 - a W 1):
B(C
2 W 1))))
1--1
1'91
E || H (n-1) 112 + 1-1
T B((
1h-1 1)
22n 020 106 + 21 (
n-1
1
W.
( (20)
n-
1=0
#1
And
E 11 1|
1
V.(( V/
Σ
03 ||
11
<3L Σ
n-n--
E || 8
Σ
n-1
0 +30 1010-1y--
V 1
1-1
E
1
n-1
12 12
(21)
11
1=0
T n
- w H 1)
n-1
o
W MM
1
E
27
Wt
H (1
- 25 W || m- II
H7 (n-1)
1| + || AT! (n-1) 1) 11
2
B(
2
2
Σ
E
||
(1)
1|
(22)
N'
Substitute Equation (21) and (22) into Equation (20) to get
E 0
1
0 1s
1=1
(n- 1)t + 2222p222 1)t+
t-1 n-1
12n
2
2
E 0
Σ 0
E
V
1
Σ
||?
(23)
Summing over t = t f1- - 1 and i == 1 1 yields:
ΣΣ E
0
1
Σ x 1|?
[=0 i=1
<2n
(n 1) + 12n 12 1)
f-1n-1
n-1
1,2 - 1)4
Σ
Σ
E 0
Σ क +12n2
Σ
E
V
12
(24)
n
n
1=1
Therefore, it holds that
4-11=1
(1- (1-12 12-1212L'
B1| 0
0 ||
0= 1ml
14

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
4-- - 12 1
1
Σ
E
1
(25)
==
Bound E 0g - 1 Σ
0 1|::
1=1
B 0-
0 1
1=1
vF - -E W (F) 1?
<B
1=0
j=1
1-1
1
-
o
(w (G') - Hmm) + Hmm)) 1|
n
1=0
1s
E || 1s
2
2
||
n
c
(G H(m)) 11a +2n² Σ
-e. w w'H (n) 12+ +
1=0
1=0
1
_sr n
21 3
Σ
B((
W
H
(n))
ee T (H(
n
1'
1-1
22/pp1001 + 4n²2p
Σ
E
Hmm) 1|
(26)
1=0
And
1-1
4n/² p
E || H (n) 1|
1=0
1-1
<417² 2 Pi
2
E ||
(0.)
VS(( Σ )
fi
(1(-))
0))
V
Σ
0))
V
Σ
) 1|2
1=0
1=1
1=1
Y=1
t- œ
<12n²
ΣΣ
E 0-
1 Σ
0. 21 +127 pioznt 120
E
| n
Σ 0) 12
(27)
1=0
Substitute Equation (27) into Equation (26) get
E
8
8 12
t-1 ΣΣ
2nn 2 pia + 12n² pi + 12n2
E
0
1
Σ
0
11
+127
P
Σ
E
V
f((
-
Σ
1|
(28)
1=0 1=1
1=0
1=1
Summing over t = to t - 1 and = 1 to n yields:
4-1
0
0 1
1=0 1=
1=1
22n
22 + 12
20 2 + 12 12 12
2
ΣΣ
E
||
0f
1
1 71
Σ
0f
21
+
+12
22n 21
Σ
o3 12
77
1=
1=1
(29)
Therefore, it holds that
11-12121 ('tz))
Σ
E
||
0
0 112
1=0
x=1
15

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
1
+ 12n pin
E V
||
(30)
According to Equation (18), we have
E
0
11
+E|
1
Σ
0 11
t=1
5241
121 L
11-1mm n-1
E |1 0
1
n-1
Σ
0 11a +12,
2
h-1
E
n-
1
n
0
11 +
n-1 1
n
71
12
1=
12 4-11
n
41 + RP
4-1
Σ Σ
||
8
Σ 8 1| +
Σ E
G (n)
H (m)
+ H(,))
11
(31)
n 1 1
71 1=1
(n 1n-1)² 1)3
(n)
t= im1
1=0
If
1-
127 2 0= 1
V
12L21
we have
1
n-1
1
E
80
0 ||
n-
n1
1=1
2241221907
12
12
4-11-1
Σ
E
B1 0f
1
Σ
0 21
12
4-1
1-11 ΣΣ
E 0
1
Σ
0
112 +
1
0= t=1
0 +=1 1=1
1=1
41)
4--1 Σ
E
(m))
Mi))
H 1
(32)
(n 1)2
Then we need to explore the relationship between || 0 - 1 Σ
0 || and || [
Σ 0 12:
i=1
0- 0 11
w! (0,
t= j=1
1-1
1
Σ
0 = 80
(F,(0),
11
j=1
1 2-2
0
00
Σ
(),
n f=
Based on Assumption 4.5, we can derive the following:
ES(
- Σ 0)
Ef( 1
1
11
11
1=1
R
B(-
17
VF
)
vf(
E
ΣΣ
VF
71
1=1
B
B2
B1 -B(
Σ
V
( 11, Vl( ブ
i=1
16

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
11 t 1 +E
"
n 1
12 1)
" (
1 112)
" E
-V
1|
7
71
B2
L
B
" Σ
(VF
- - V 1|
11
1=1
LoP
r2
E
vi((0 1|
2n
2
1=1
Therefore, holds that
11 Σ
1 n
Ef(
01)
Ef(
0
72
12
1 L
nT
E 0
1
0
1
171 nT.
E
n
v
-
1?
ワ 12
0
(33)
2n
2n
1=1
Summing over t to 1 yields:
Ef(
Σ 1=1
0 - Ef(
6
i=1
Lofhi
77
17(1
TT)
E || 0
0
1|
Σ
E
Σ
V
(0 1 12-2
Σ
E
V
0,) 1|
2n
2n
2
1= 1=1
1=1
t=
(34)
Then we have
1
1/(1
41
E
||
V
-
0
1|a
E
V ((())) 1|
2 t=
2
1=1
t=0
(=1
1
1 Bf(
2
4-1
- Σ
n
1)
Loft
BBf
Σ
8
Σ
0
E
0
0
11
(35)
n
n
2n
2n
1=0
im
If the above condition about step size 17 is satisfied, that is, 17
then it holds that
Σ E V n
Σ
))
M 09)
Es( 12
0
1 f
Σ Σ
n
1
Σ
0
11
+
Lofh
(36)
n
n
n
1=1
Then we can further derive the Equation (30) as follows:
1 - Σo! 1
(1 (1-121) L2=
Σ
E
0
t=
+ 6o 22n2pi(07
120?
12n?
11] [Ef(
0 -
-
Σ
2
2--1-
E 0
1
Σ
||2 +
nLot
2
2=1
1=1
1=0 1=1
1=1
(37)
Therefore, it holds that
4- n ΣΣ
(1 -1-246
E 0
12
t=1
12
12ny Lptointt + 2t
Σ
).) Ef
Σ
87:))
(38)
i=1
i=
17

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
1 and V 5 8) 12:
Next, we need to explore the relationship between
0
1-1
=
0
VF 2)
1=0
1=1
Σ
0 0
7
11
5=
n-1
1-2n-1
0
ΣΣ
n
1=1
1=0 j=1
Based on Assumption 4.5, we can derive the following:
ES(
E
11
E
VF, (0) - ).
Vf
1
E
VF, - 1 1|
2
i=1
1=1
1=1
13
Bg
=E
11
1
Σ
n
=-2
"B
||
1
(1 1|2 7B
Σ
2
n2
n-1
- (1:001)--
Σ
7
E
(1(0:-1) 1|2 7
1|
2
11
1
BI
(V
1
2
"
B
|| 2
1 Σ
1 +
1T..2 n-1
Σ
Σ 0 ||
2
n
n
n
1=1
i=1
B4 B
L
E
11
(V -ー
- 1|
2
n1
2
L
n-1
< 2(n - 1) 2
+ E
n Σ
Therefore, it holds that
1
n-1
E
ES(
(1-1)
11
n 1
i=1
1=1
< 11(1 LL
Lo
E
V f
1| 1---
" V
Σ 0
1
+ n
2
2
n
2(n 1)
18

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
1/,
1
E
6
12
(39)
1 1=1
i=1
Summing over 1 to / yields:
n- 1
1
E/(
0
1 1m
im1
< - n11 - n
4
E
V (i))
112
" Σ
E
-
1
Σ 2)) 12 + ,TT0991
+ nožtz
2
2 1=
2(22 - 1)
1=0
i=1
11 4 4-1u-1
E
0
0 112
(40)
n
Then we have
7 11-1
R-1
8 1| 71(1 LL)
41-1
1
n-1
EI
E
f.((()) 1|
2
12
t=
n-1
1 n-1
1 Loftt
nI
4-1nn1
<
Σ
0.
Ef(
8.t
+
+
+nost1
E
8 1|
(41)
n1
n
n-1
2(n - 1)
1
12
t=U
Similarly, if the above condition about step size r) is satisfied, that is, 17 S
then it holds that 12L
V
E
0 1|
1=0
1=1 Ef(
<² [B Σ
n-
Looit +
2L
h 1 n-1
n
09)
+
+20211+ +
E ||
0
Σ
0
||
(42)
"/
1
11
t=0 i=1
1=1
Then we can further derive the Equation (25) as follows:
4-1n-1
(1 12=1222 1)t1)
Σ
8
Σ
8 1|
12
1=
1=1
p3 - 1) + 12n 230 (n - 11) + 1201 12
1)
2 EEf(
n-1
Σ
00)
Ef(
n- ))
1
Σ
17
n
1=1
1=1
nLoih +
n n- + 20
2T. 4-1n-1
Σ
E 0
1 - og 113
(43)
n
t=0
==1
Therefore, holds that
f=-1-1
(1 (1-360 13 - 1)tt)
ΣΣ E B
Σ 12
n 1=1
1=0 1=1
<2n 22022207(m - 1) + 122 11
1 L.poff 1) + 24
(n -
Ampp3(n-1)2n (B n - Ef
1
(44)
Then based on Equation (19), we can further derive the following:
4n + 2 t nn 1)2
Σ Ell ((,) Himm) + Hi,n) 1|2
19

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
- +
2
E || (( 7f,(" 1 Σ 8 Vf(
12 Σ 03) Vf( 1 Σ
1
0
n VJ(
Σ
8)) 1?
i=1
1=1
:=1
(1 + p pi)
24n + p 10311
241 122 + pF
8-1 n
n Σ
E
0
0 11
(n - 11)2
(n 1)²
(
24 (1 + pi) ml?
4-1
E V
0) 1|
(45)
(n 1
72
(=0
Due to the fact
2
(n
1)2
n
n n22
n1
n
2
4
<
(n 1)2
1
we can further derive the Equation (32) as
R-1
0 1
11
120p2L' 41-1 1- Σ
+ 0 <8r + 2 + (8
E B 05
1
0 1|2 +
71
n
1=0 1=1
1=1
24r + 2
E 0
- Σ
0 1|
24 + p)
E
V
1
Σ
1|
(46)
(n 1)2
1=1
1=1
1=1
According to Equation (38) and (47), let
1
D1 = 1 22n2222
>0 >0=イ<
V
2AL2pInn
D2 = 1 -
1)t V
36L2 36L2p2 (n- - 1)
4-1 R
E 8
1
Σ
8 11
n
n
2n7 pioint?
12n² pinntt
12n Lpio
24npinta
(Ef( 1 Σ o9) - Ef( ))
(Bf(=))
(47)
D1
D1
D1
D
4-1n=1
n-1
1
Σ
E 8
Σ
0 112
n
n1
211² přoi(n 1)t2
12n² 2
(n- 1)t2
12n Lpiofth
24n 1)th
+
D2
D2
D2
D2
24np3(n 1)t1
8-1 Σ
09)
ES
1
R-1
Σ
0+)
(48)
D2
n1
20

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Substitute Equation (36), (47) and (48) into Equation (46) to get
R-1
n-1
E
0
1|
71
12
(6 + 4p))ps
2 +
8(1+ + pi)e?
L2 = 144n) 1444)LL89tt
+ 81 226)0299 + 48 + oi)03(9+
Di
D2
nD1
144h L3 (6+ 4p))pfn
(n
16(1 + pt)pp
+
)+
D1
D2
D1
2304n pf(1 (1+ + p/)
5767 57 p/ + 2p9)m1
192n(1 + AA) (Ef(0") - E8 Σ 07))+
+
+
D1
D1
1=1
28817² 2 (2 1)th
(Ef(0") Ef( n1
1)
(49)
D2
where 0 < 17 < minty 12T2r7 V 247.2/mm11 V 361 n- 136
Then, using Jensen's inequality, we can directly obtain
Lemma B.1.
D. Proof of Lemma B.2
p 21?
n1
t1
E 0 1|?
11
E 6
W (),,
VF,03,55) Σ
VF,(0,,5)
Σ
WH
j=1
j=1
VF, (
n n
31
Σ
4-1
Σ
B (ef Hr
1T 1
G (n-1) +E (ef'W
1 G 112 +
1
E ( 1Td
(=n
2
G 113)
1
(n
1)2
1=1
t=0
231 2
E
(mn)
Him + Hin) 1|?
(50)
1)2
t=
Substitute Equation (19) and (47) into Equation (50) to get
a- 1+:
Σ
11
n1
<6(n'n + 377" -+ 12n L2 12 L2ppntti
72 L'pntt
D3o + (1872n + 432m/ L2 12p2nits
D30
Di
D.
D2
(36mtt: + 864m7 L2 p?ntt
Da(Ef(( - Ef(
((11)
(51)
D1
where D3 = pi + लー and step size 0 < < mint 12
Then, using Jensen's
24T
361 n- 135
inequality, we can directly obtain Lemma B.2 without early stopping.
21

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
For an early stopping setup, it holds that
11 n-1
E
p 1|
n
1=1
1=0
R-1
(n 1)
Σ
f1
p 1 83 1|
(n 1)²
< 4 n-14--
エ E 0
(52)
This result shows the same bound with Equation (50). As a result, Lemma B.2 still holds for the early stopping setup.
E. Proof of Theorem 4.9
Subtracting Equation (12) from Equation (13) yields
72
n
T-
72
(53)
71-
Y1
71
Y1
i=1
i=1
0 < 1/ < min(
it holds that
12
24L pint"
36L pg
174
n-1
0.1
71
11
1=1
1
1
||
p
n1
n1
1=1
1=
(24m + 1447
16+107202 Di
+
22
+
+ 2 + 487 (1+ +f)
D2
nll
1441
(G+1p)
(n-
D2 +
16(1+p]00]
2301 L ('
576 L2 L. (3+22))mm
111
D1
D1
(ES(09) - Es{ n- Σ 0T:)) 1920(1+/111)) (OO - ( Σ ((1)) + 2888, 2 L2 (n
D2
6172n + 3 + 12.) 1222ttt + 72n 22n2ri2/ D3o + (18122 + 432m"112p,m211 D20
D2
(36mmt + 16 Dz(Ef(00) = Σ 0(2)) D1
1=1
which completes the proof.
F. Proof of Corollary 4.10
Corollary 4.10 guarantees the (c, inn.innniistinnuiabblllttt of Algorithm 2, since it is essentially based the Gaussian mechanism.
From a global perspective, the average model (Algorithm 2) and
0y is obtained by our proposed decentralized unlearning algorithm
0 is produced by the retraining algorithm (Algorithm 1).
According to the generation rule of Tth and 0:::
0 0: + 21, where 2, ~ N'(0, (n 1)0²
8 = 0 + zi, where 2; ~ N(O, (n - I))
22

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
We can derive that the average models
and
satisfy:
0 +
1
1
4
0 +2
71
where 2 ~ Ia)..
n-1
Therefore, the average models
1 8
Σ
and n-1
Σ
0 follow the distributions
M 0 Id)
n-1
and
0 ~
Laa))
What's more, according to Theorem 4.9, we can denote di as the upper bound discussed in Theorem 4.9, which satisfies
(2fnf1 + L
4p+4ne2 al s(1+Alel + (5 + 48 pf)oßti+
D2 + nD
D1
122 (G+tpi)eii
30)(n-1)
L² 4 16(1+eilei + L" 22
576 (3
d1 2
D2
D1
D1
288n L2 (n- (Bf(8") - Ef( n-1 1927(1+0111) (Ef( Ef(, Σ 0(1))+
n
Σ 8h)))
D2
6(1ín + 311² L + 12n" p2ppn"t
D30 + (1812n + 432n' p2ppnn 2t
+
D1
D2
+
(36mnt1 + 12 Ds(Ef((0)) -Bf( - 022)
D1
Based on Gaussian mechanism (Definition 4.3), the average models - Σ Indistinguishability, and thus Algorithm satisfies (c, machhne unlearning with
0
and n-1 Σ
00
are (e,
1=1
d1 V2 /log(1/3) + +e- Vlog(1/B)
1
That completes the proof.
G. Proof of Theorem 4.11
Based Equation (10), have
n-
0:
0
f
W 1 VP,(0-11.))
[=1
n-1
0
1
n-1
00
Σ
V 10,00
71
1
n
1 ==
n-1
n-
1
0
A
VF 1
Therefore, it holds that
23

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
=00
1
1j
+
VF,
:
1
Σ
1
F=1
1=
==1
n-
1 n-1
-0
0
Wh
(54)
(n-1)
n
1 11-
n-1
0
VF, (0)- -g--)
(55)
11
n
1=1
1=1
j=1
According to Assumption 4.5, we have
1
E
Ef(
12
<TE(
Σ
)
Σ
E
VP 1 1|?
n
n1
n-
a-1
B
0 1|
(0: 1) 112
2
72
2
n
i=1
R-1
B
VJ
Σ 0
Σ
( 1|
2
n
1-
E
Σ
VE
V vi(00 -1)
V vf( 11 1|2
2
n
1=1
1
- 1|?
2
2
Σ
Σ
- 7) 1|
FL
n-1
1 E
n-1
E
- )) 1|
( 112
2
n
2
n
Lo
n-1 Σ
1(1 - A
1
n-1
E
f((
8111 2|
f ||
2(n 1)
2
1
2
n
1
1m1
1T?
R-1 Σ
1 n-1
E ||
0 -1
8 1 1
(56)
2(n2 1)
n
21
1=1
Bound
E ||
0
1
Σ
0 11::
1-1
n-1 Σ
E
0 0:
0 11
71
R-1
8N) 9 Σ (ef W- 1
|| (0th
Σ
GL-1
11- 1|?
1
n n-
1=1
E
||
1
n-1 Σ
8 112 +402 Σ
E ||
(
Wi
1 |G/|--1) -A(-11)) ||
11
1=1
24

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
4r)
2
E
-n-1)ft W
n- - 11?
1=1
22 Σ
B 111
1
0 1| +4i p40)2220 1) 4rj
E ||
(2
n n-1 (n-1) 112 +
I 1 )
n
1=1
1
1
11+t111
| (n-1)' (e
( (()))
n-
n
1/1
2
B ||
ON
1
Σ
0 1| +4i () 8
E
(c) Wh+
n n- ) (m()) 11?
-
n2
1=1
2
n-1
E
|| 0
1
Σ
n-1
0 1|2 +41)22200000
(n
p3 1)
n-1
|| V 11?
(57)
n
Bg
Bound Bg:
BB-
2-1
E -
V5(( 71 -
n-1
+
fi(
n-1 Σ
8
VJ(
-
Σ
n-1
1)+
n 1-1
7
f
Σ
8
ví 1
Σ
n-1
8.-
0 1|
n
B
Σ
2|
+4
E
Σ
Σ 8 )
112 +
1=1
1=1
Σ
0
) ||?
1
1
Σ
E
Σ
Σ
8 11 +
n
E n
1
(v
n-1
n-1
1 n-1
Σ
8 12
1
n
n
n
72
n-1
n-1
40²
R-1
n-1 Σ
<4L²
Σ
E ||
-1-1
8.-1
||a
+4(n
1)0 +
+
8'-
1|
(58)
π
n - 1
n
Substitute Equation (58) into Equation (57) to get
1
E
0
0
1s
n2
B-1
E
0g
1
1-1
0y 11
+4i
+4i2p307(11 320 1) p2021+
n1
1 n-1
32 L2 L2
1)
E || 0
Σ
0. 2 +
+320 13
+320)
1)2 Σ
E
V
1|
(59)
n 1
1=1
Therefore, it holds that
T Σ
E 6
0 l|2
n1
25

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
27
E ||
05
1
0 21
44/ 1
+46
+ 32 1
i=1
T-1a-1
32 1,2 P2(n
1)T)
Σ
E || 0
1
72 V
0 112 +32 03(
1
Σ
0:) 11
(60)
12
1= i=1
1=1
Then
T
7- 1
E || 05
0 11?
1=0 i=1
n-1
1
n-1
S37
E || 04
0. 112 +4
+411 pn - - +
- + 32f/ p3
1)
(=1
1=1
T-1n-1
321 122 - 1)T)
E 0
- Σ
0
) 1|?
(61)
t=0 1=1
1=1
1=0
1=1
If it satisfies i) <
321.2 p2 1j7 the following holds: V
1
T-1n-
(1 - (1-32n) 32 1)T)
E EIO 0
Σ 0g 11?
1=
<37 Σ
E 0
0 112 441 - 1)2T² 320 13 1 320
i=1
- 12 12
32 p3(n T)
E ||
(62)
1=0
Summing from = 1 to 1 T for Equation (56) and substituting Equation (62) into yields
n-1 n1
Ef
Ef(
0
n2
161 L2 p3 1)T
T-1 Σ
R-1
1(1 AL)
T-1
n-1
<
E
Σ
8 1
Σ
E
1 112
(2pg(n - 1)T
72
2
T2
1=0
1=1
[=0
3/
n-1
8-1 Σ
2/ - 1)T2
Σ
E 1
8 1|
2(n 10) 1)' 12-3 1)T
1 32 P2 1)T
1=1
1=1
- 1
16 T.2 L. 2
1 Lo
+
(63)
1 122 1)T
(n- 1)(1 32/ 1.2
p2 17T)
2(n
where 1 < 12
Then let
1 13 1)T D4 = 2 1 122
1L D5 = 2
Dg = 1 - 327 L2 (2
If the step size i satisfies f <
3212 (3L1-p(n--)""" 1 we have the following convergence result of the subsequent T rounds of
training:
T D1
1 T T
Σ
E
E
1
B 1|
+D
Σ
E
Σ
Vi(i)) 1|
T
0=0
t=0
26

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
nT. Σ 8
f
31?
n-1
26 1.
p2o
(n- 1)T
0 E
0 1|
2Dg
11
11
2(n - 1)
qT
Do
16n L2 P220
(n
1)T
167 L p2o2T
De
(n 1)D8
which completes the proof.
H. Proof of Corollary 4.12
We assume that D4 2 C, where C' E (0, 22) Then it holds
16 1)T
1-
1-20
D4 S
+ q 5
32n 1\T
2
64(1 C)1
and Do = 1 32 1)T 2
2(1 -)
If we set fj ===- _ the following should be satisfied
(n-
1)3
1
-0
64(1 - C)L?p3 1)3
+ TT>
T
64(1
(2
1)T
1-20
1
iL
1
(n 1)L
D;
0
T2 12 1)L
2
2
2
2T
As result, it holds that
n-1
f( Σ 84) -
Σ 07) -
i/T
n 1
i Lo²
2(n - 1) 2T
21/2 L2 12 - 1)T
0f
(1 21-20)
(-
D1)
<
De
2
8
16
167/ 1.2 1223003(1 - 1)T
- 2C)
=
- D4)
0f <
D6
2
16 1.2 T2
1
02
(1 2C)
=(2 D4)
<
(n Ds
(n 1)2
2(n 1)²
Therefore, if the number of training round T satisfies T > max
64(1 12 1)
(n 1)L} with C (0, }), and the
1-20
step size i further satisfies i n-1
T then Corollary 4.12 holds.
I. Experimental Details
L.. Datasets and Models
We train the ResNet-18 model (He al., 2016) and the CNN model on the real- world datasets, including MNIST (Leeun
et al., 1998), CIFAR-10 (Krizhevsky & Hinton, 2009), SVHN (Netzer et al., 2011) and MaSHion-MNIST (Xiao et al., 2017).
MNIST a handwritten digit dataset containing 60, 000 training images and 10, 000 images of grayscale digits (0 9), each with resolution of 28 28 pixels.
Fushion-MNIST consists of 60, 000 training images and 10,000 testing images, with each being 28 x 28 pixel grayscale image representing various clothing items such as T-shirts, pants, dresses, and more.
27

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
CIFAR-I0 includes 60, 000 colored images of 10 common object classes, with 50, 000 images for training and 10, 000 for testing, each 32 32 pixels with three color channels (RGB).
SVHN consists of real-world house number images from street views, containing 73, 257 training images and 26, 032 test images, also at 32 x 32 pixels with RGB channels.
1.2. Baseline methods
To show the advantages of our proposed algorithm, we compare it with the following baseline methods:
Origin. The baseline is actually the D-PSGD algorithm (Lian al., 2017), which does not involve any unlearning operations.
Retrain. This method retrains the decentralized models from scratch on the remaining n - 1 clients after removing the target client-n. It can achieve exact unlearning but requires significant time and resources.
FATS-Unl (Tao et al., 2024). It saves the historical global models and the sets of clients that participated in past training rounds on the central server. When a client initiates an unlearning request, the algorithm retrieves the latest model from before the client's initial participation in training and then retrains.
Recoveyy (Zhang et al., 2023). It relies central server remove the weighted sum of the gradient residuals from the global model to eliminate the influence of certain client, and adds specific Gaussian noise to make the unlearned model and the retrained model statistically indistinguishable.
HDUS (Ye et al., 2024). Each client's main model relies entirely on local and public datasets and remains unaffected by its neighbors. The collaboration among clients is solely reflected in the integration of distilled seed models from neighbors to make decisions. Therefore, the decision results of the client initiating the unlearning request can be removed by adjusting the integration process.
L.3. Metries
In our experiments, we use multiple metries to evaluate the performance of the proposed decentralized unlearning algorithm, including accuracy, unlearning time, communication overhead, and attack success rate.
Accuracy. To examine the statistical indistinguishabiiity, we evaluate the overall accuracy of the unlcarning models and the retrained models. To show the effectiveness of our PDUDT, we record the average accuracy on each class after performing a specified number of rounds.
Unlearning time. We evaluate the running time required for the proposed Algorithm 2 to perform the unlearning operations and compare it with other baseline algorithms. For FATS-Unl and FedRecovery, this is measured on the server side, while for others, it is tracked on the client with the most neighbors.
Attack success rate. Membership Inference Attack (MIA) is employed to determine whether the data samples of a client slated for forgetting were part of the training process. A higher MIA success rate indicates that the global model still retains considerable information about this client's 's training data, signifying an inadequate unlearning effect. In contrast, a success rate of 50%5500%vvo equivalent to random inssingg that the model no longer carries exploitable traces of the client's data, thereby demonstrating effective client removal. We perform the membership inference attack on the unlearned model to verify if the proposed unlearning algorithm successfully removed the targeted client's influence.
I.4. Additional experimental results
To show the scalability of PDUDT, we conducted experiments with 20 clients performing natural language processing (NLP) task. Specifically, we evaluated PDUDT using the Yahoo! Answers dataset with the Bert-tiny model.
For the Yahoo! Answers dataset, Figure 3 demonstrates that our method is statistically indistinguishable from the Perturbed Retraining approach across a range of noise scales. Moreover, Figure 4 highlights the effectiveness of both PDUDT and
28

---

PDUDT: Provable Decentralized Unlearning under Dynamic Topologies
Yahoo! Answers
Yahoo! Answers
1.
5.4
Will
Ascuracy
62
FAADYT
5,005
5.01
Class
Figure 3. The accuracy of unlearned models using PDUDT, PDUDT (ES), and perturbed retrained models on Yahoo! An- swers dataset.
Figure 4. The accuracy on each class using PDUDT, PDUDT (ES), and perturbed retrained models on Yahoo! Answers dataset.
Table Comparison unlearning time attack precision MIA across different unlearning methods on Yahoo! Answers datasct. "-" means no results not applicable.
Method
Unleaming time (6)
Attack precision (%)
Origin
69.2 0.2
Retrain
2852.2
50.3 0.8
FATS-Unl
51.2
FedRecovery
518 0.7
HDUS
27.5
51.5 0.3
PDUDT
11.8
50.7 0.7
PDUDT (ES)
10.2
51.1 # 0.5
its space-efficient variant, PDUDT (ES): While they maintain high performance on classes 0-8, their accuracy noticeably declines for Class Finally, Table summarizes the substantial time savings afforded by our unlearning operations and further confirms the unlearning effectiveness of PDUDT and PDUDT (ES) through comparable membership inference attack (MIA) precision relative the Retrain method. The results confirm the superior performance of PDUDT, showing good scalability to larger networks and NLP task.
29


Reviews:
[{"review_id": "pWPFFC022D", "reviewer": "Reviewer_rNoR", "summary": "This work focuses on the provable unlearning in decentralized learning under dynamic topologies. The proposed PDUDT algorithm addresses this by using historical gradient information of clients and their neighbors to eliminate a specific client's influence without extra communication or retraining. The authors provide rigorous theoretical guarantees, showing its statistical indistinguishability from perturbed retraining and $\\(O(\\frac{1}{T})\\)$ convergence rate.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer rNoR for the time and valuable feedback! We would try our best to address the comments one by one.\n\n**1. Response to “Claims And Evidence”＆ “Questions For Authors”:**\nThank you for your insightful feedback. As we discussed in Related Work, approximate unlearning  has demonstrated sufficient effectiveness in many practical scenarios and has thus motivated further work by many researchers, such as Liu et al. (2021) and Ye et al. (2024). Therefore, in this work, we primarily employ the weighted gradient residual approximation to adjust the local model, further achieving approximate unlearning in the decentralized paradigm. Corollary 4.10 shows the unlearning performance that our algorithm can achieve, which is statistically indistinguishable from perturbed retraining. In addition to the theoretical guarantee, we experimentally verify its statistical indistinguishability and further analyze the utility and efficiency of PDUDT. We hope our answer can clarify your confusion.\n\n\n\n**2. Response to “Theoretical Claims”:**\nThank you for your valuable feedback. We note that Assumption 4.7 is a standard and widely adopted assumption in decentralized learning frameworks. Furthermore, many methods have been proposed to construct a doubly stochastic communication matrix, such as the Metropolis-Hastings method. However, under extremely harsh communication conditions, the use of Assumption 4.7 has certain limitations, since it may be challenging to guarantee the doubly stochastic nature of the communication matrix. We have included a discussion on this limitation in the revised version. Thank you once again for your insightful comments.\n\n\n\n**3. Response to “Experimental Designs Or Analyses”:**\nThank you for your insightful feedback. We hope that the following explanation of MIA design can clarify your confusion: Membership Inference Attack (MIA) is employed to determine whether the data samples of a client slated for forgetting were part of the training process. A higher MIA success rate indicates that the global model still retains considerable information about this client's training data, signifying an inadequate unlearning effect. In contrast, a success rate of 50%—equivalent to random guessing—implies that the model no longer carries exploitable traces of the client's data, thereby demonstrating effective client removal. Thank you again for your valuable comments, we have added this explanation in the revised version.\n\nIf there are any further confusions/questions, we are happy to clarify and try to address them. Thank you again and your recognition means a lot for our work.", "claims_and_evidence": "The claim that PDUDT can eliminate the influence of a specific client without additional communication or retraining is supported by the algorithm design. The algorithm uses historical gradient submissions to compute gradient residual approximations and weights, which are then used to adjust the local models. However, the approximation of gradient residuals may not fully capture the complex interactions among clients in all cases. This could potentially lead to incomplete elimination of the client's influence, especially in scenarios with highly non-linear model dynamics.", "methods_and_evaluation_criteria": "Yes, I think the experiments are sufficient, the proposed methods and evaluation criteria in the paper are highly relevant and make sense.", "theoretical_claims": "The proof assumes that the communication matrices are doubly stochastic and symmetric (Assumption 4.7). While this is a common assumption, it may not hold in all real-world decentralized systems, especially under dynamic topologies. A discussion of how the proof generalizes to non-symmetric or non-doubly stochastic matrices would be beneficial.", "experimental_designs_or_analyses": "Yes, The paper's experimental designs and analyses generally show soundness. The selection of datasets (MNIST, FashionMNIST, CIFAR - 10, and SVHN) ,  models (CNN and ResNet - 18), the baselines are appropriate. But I do not understand the Attack precision design, which need more details.", "relation_to_broader_scientific_literature": "The key contribution is that this work is the first provable decentralized unlearning algorithm under dynamic topologies. The concept of (\\epsilon, \\beta)-indistinguishability (Neel et al., 2021) used in the paper to prove that PDUDT is statistically indistinguishable from perturbed retraining. This builds on the existing literature on differential privacy in distributed learning.", "essential_references_not_discussed": "I think the highly related works have been cited and discussed.", "other_strengths_and_weaknesses": "No any other comments or suggestions.", "other_comments_or_suggestions": "No any other comments or suggestions, overall, I think this work is well-written.", "questions_for_authors": "My major concern is still about the PDUDT algorithm design, the claim that PDUDT can eliminate the influence of a specific client without additional communication or retraining is supported by the algorithm design. The algorithm uses historical gradient submissions to compute gradient residual approximations and weights, which are then used to adjust the local models. However, the approximation of gradient residuals may not fully capture the complex interactions among clients in all cases. This could potentially lead to incomplete elimination of the client's influence, especially in scenarios with highly non-linear model dynamics. If this can be well addressed, I can consider changing my evaluation.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ouzx0BtUoo", "reviewer": "Reviewer_vxha", "summary": "The authors introduce a novel algorithm PDUDT, which is designed to enable efficient and provable unlearning in decentralized learning systems with dynamic network topologies. PDUDT allows clients to remove the influence of a specific client without retraining or additional communication by using historical gradient submissions to approximate gradient residuals and adjusting local models accordingly. Theoretical guarantees show PDUDT achieves $\\mathcal{O}(\\frac{1}{T})$  convergence rate. Experiments on datasets like MNIST, CIFAR-10, and SVHN demonstrate that PDUDT reduces unlearning time by over 99% compared to retraining.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer vxha for the valuable feedback! We would try our best to address the comments one by one.\n\n**Response to “Claims And Evidence (1)” ＆ “Essential References Not Discussed” ＆ “Questions For Authors (1)”:**\nWe have carefully examined these works and provide a detailed comparison below to clarify our unique contributions. \n**(1) vs. HDUS (Ye et al., 2023):** HDUS relies on seed model distillation and additional training steps, without theoretical guarantees. PDUDT, by contrast, eliminates influence using saved historical gradients—without retraining—and offers formal guarantees on unlearning and convergence under dynamic topology.\n**(2) vs. AIGC Unlearning (Lin et al., 2024):** The AIGC work focuses on privacy-preserving AIGC systems via coded computing, incurring storage and reconstruction overhead. It lacks theoretical unlearning guarantees and is tailored to AIGC tasks. In contrast, PDUDT is application-agnostic, retraining-free, and provides provable client-level unlearning.\n**(3) vs. BlockFUL (Liu et al., 2024):** BlockFUL depends on blockchain infrastructure and consensus, which may be impractical in dynamic or asynchronous networks. In contrast, PDUDT is lightweight and naturally supports dynamic peer-to-peer topologies.\nTherefore, we claim that our work presents the first **provable** decentralized unlearning algorithm under **dynamic topologies**.\nIn our current manuscript, although HDUS and BlockFUL have been cited, we agree that adding more detailed discussion will improve the quality. More generally, we also fill in the missing discussion on AIGC Unlearning (Lin et al., 2024).\n\n**Response to “Claims And Evidence (2)”:**\nThe statistical indistinguishability guarantee in Corollary 4.10 relies on the fact that the difference between the PDUDT output (model corrected by gradient residual estimation) and the output of retraining can be bounded (as shown in Theorem 4.9), and then obfuscated by adding Gaussian noise with a corresponding scale. Specifically, the Gaussian mechanism ensures that, after adding noise drawn from $\\mathcal{N}(0,\\sigma^2\\mathbb{I}_d)$, the two outputs become close in distribution—making them statistically indistinguishable.\nThis approach follows the standard principles of the Gaussian mechanism in differential privacy. In our case, Theorem 4.9 gives an upper bound on this difference, and we use it to determine a noise scale, thereby masking any deviation between the PDUDT output and the retraining output. \n\n**Response to “Theoretical Claims”:** We fully understand your concern about the accuracy of the difference between the retrained and the unlearned models, as it affects the subsequent noise scale. But in fact, we cannot get the exact value because $\\tilde{\\theta}_i^{t_1}$ is a retrained model. Therefore, we need to approximately seek the upper bound of it through the model iteration rule. Our Theorem 4.9 provides a conservative upper bound on the difference between the retrained and the unlearned models, which ensures that the noise scale $\\sigma$ selected suffices to achieve the desired level of statistical indistinguishability.\nWhile the bound might not be tight in some scenarios, this conservativeness is intentional and aligns with the standard approach in differential privacy, where upper bounds are used to ensure worst-case guarantees. We also highlight that the Gaussian mechanism is chosen due to its robustness under such uncertainty—it provides meaningful guarantees as long as the upper bound is valid.\n\n**Response to “Experimental Designs Or Analyses” ＆ “Questions For Authors (2)”:**\nDue to limited computational resources and funding constraints, we are currently unable to simulate scenarios involving hundreds of clients. However, to show the scalability, we conducted experiments with 20 clients on a NLP task. Specifically, we evaluated PDUDT using the Yahoo! Answers dataset with the Bert-tiny model. The results can be found at: https://anonymous.4open.science/r/Unlearning-47E3, confirming that PDUDT has good scalability to larger networks and NLP task.\n\n**Response to “Other Strengths And Weaknesses”:** We would like to clarify that Corollary 4.10 in our paper also applies to the early stopping variant PDUDT (ES). The key difference between them lies in their cumulative weighted gradient residual approximation ($\\frac{1}{n-1}\\sum\\limits_{i=1}^{n-1}\\sum\\limits_{t=0}^{t_1-1}p_i^t \\delta_i^t$ for PDUDT and $\\frac{1}{n-1}\\sum\\limits_{i=1}^{n-1}\\sum\\limits_{t=0}^{t_{1,i}-1}p_i^{'t} \\delta_i^t $ for PDUDT (ES)). Despite it, they both can be bounded by the same upper bound in Theorem 4.9. This is formally justified in Appendix A (Lemma A.2) and further supported by the derivations in Appendix C. We note that the current manuscript did not explicitly state that Corollary 4.10 also holds for PDUDT (ES). We have clarified this in the revised version.\n\nIf you have further confusions, we are happy to clarify them. Thank you again for your support.", "claims_and_evidence": "This work is generally supported by rigorous theoretical analysis. However, I still have some concerns: \n(1) The authors claim that they are the first provable decentralized unlearning algorithm under dynamic topologies. Some related works, such as “Decentralized Federated Unlearning on Blockchain, arxiv 2024; Decentralized Unlearning for Trustworthy AI-Generated Content (AIGC) Services, IEEE Network 2024; Heterogeneous Decentralized Machine Unlearning with Seed Model Distillation, arxiv 2023” need to be carefully addressed and compared. \n(2) The claim that PDUDT is statistically indistinguishable from perturbed retraining, the authors utilize Gaussian mechanism to achieve it. However, the connection between the Gaussian noise and the indistinguishability guarantee could be explained more clearly.", "methods_and_evaluation_criteria": "The chosen baselines and the evaluation criteria are well-suited for the decentralized unlearning problems.", "theoretical_claims": "Almost check the correctness, I have questions about the Corollary 4.10, The choice of the noise scale \\sigma is based on the upper bound from Theorem 4.9. If the bound in Theorem 4.9 is not accurate, the noise scale might not be appropriate, and the statistical indistinguishability claim could be affected. Also, in practice, the Gaussian mechanism's effectiveness might be limited by the actual distribution of the data and model parameters.", "experimental_designs_or_analyses": "(1) While the paper demonstrates the effectiveness of PDUDT on a network of 10 clients, the scalability to much larger networks (e.g., hundreds of clients) is not thoroughly explored. \n(2) The experiments are conducted on specific models and datasets. While the results are convincing for these cases, the generalizability to other models and tasks (e.g., natural language processing or more complex architectures) is not fully addressed.", "relation_to_broader_scientific_literature": "Theoretical guarantees for unlearning have been explored in centralized settings, with methods like Exact Unlearning (Guo et al., 2020) and Approximate Unlearning (Sekhari et al., 2021) providing formal guarantees for removing data points from trained models. PDUDT provides provable guarantees for decentralized unlearning, including statistical indistinguishability and convergence rates. This extends prior theoretical work to the decentralized setting, where the lack of a central server introduces additional challenges.", "essential_references_not_discussed": "Some decentralized unlearning algorithms have also been proposed, such as “Decentralized Federated Unlearning on Blockchain, arxiv 2024; Decentralized Unlearning for Trustworthy AI-Generated Content (AIGC) Services, IEEE Network 2024; Heterogeneous Decentralized Machine Unlearning with Seed Model Distillation, arxiv 2023”, what are the main contributions of PDUDT?", "other_strengths_and_weaknesses": "While the early stopping strategy is introduced to save memory, the paper does not provide a detailed analysis of its impact on unlearning performance. A more thorough discussion of the trade-offs between memory savings and performance would enhance clarity.", "other_comments_or_suggestions": "None.", "questions_for_authors": "(1) Some decentralized unlearning algorithms, such as “Decentralized Federated Unlearning on Blockchain, arxiv 2024; Decentralized Unlearning for Trustworthy AI-Generated Content (AIGC) Services, IEEE Network 2024; Heterogeneous Decentralized Machine Unlearning with Seed Model Distillation, arxiv 2023”, need to be addressed.\n(2) While the paper demonstrates the effectiveness of PDUDT on a network of 10 clients, the scalability to much larger networks (e.g., hundreds of clients) is not thoroughly explored. The experiments are conducted on specific models and datasets. While the results are convincing for these cases, the generalizability to other models and tasks (e.g., natural language processing or more complex architectures) is not fully addressed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XldVKCyZX2", "reviewer": "Reviewer_6f9d", "summary": "The paper proposes PDUDT, a Provable Decentralized Unlearning algorithm under Dynamic Topologies. The key contribution is a decentralized method that eliminates the influence of a specific client without additional communication or retraining. The authors provide rigorous theoretical guarantees demonstrating that PDUDT is statistically indistinguishable from perturbed retraining and achieves a convergence rate of O(1/T), matching state-of-the-art results. Experimental results show that PDUDT saves over 99% unlearning time compared to retraining while maintaining comparable unlearning performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer 6f9d for the time and valuable feedback! We would try our best to address the comments one by one.\n\n**1. Response to “Experimental Designs Or Analyses”:**\nThank you for your constructive feedback. We agree that providing more details on topology evolution and the impact of noise would further strengthen our results. In the experiments, we randomly generate connections among clients and then assign communication weights using the Metropolis-Hastings method. More details are provided in our subsequent response (Response to “Other Weaknesses 1.” ＆ “Questions For Authors 2.”). As for the impact of noise, our Figure 1 demonstrates that increased noise leads to a decline in model accuracy. However, under all noise conditions, the performance of PDUDT and Perturbed Retraining method is always comparable. This indicates that under the same noise conditions, these two approaches can achieve statistical indistinguishability. We hope our response addresses your concerns.\n\n\n**2. Response to “Other Weaknesses 1.” ＆ “Questions For Authors 2.”:**\nThank you for your constructive feedback. In fact, our experiments are based on dynamic connections. In each round, whether there is a connection between any two clients is randomly generated. Then, in order to ensure that the communication situation can be modeled as a doubly stochastic matrix, we use the Metropolis-Hastings method cited in the paper to generate the communication weights between clients. We have provided this detail of dynamic topology construction in the revised version.\n\n\n**3. Response to “Other Weaknesses 2.” ＆ “Other Comments Or Suggestions 1.”:**\nThank you for your valuable feedback. We agree that the extensive use of mathematical symbols can be challenging for readers. In our revised version, we have added a comprehensive notation table that summarizes all key variables and parameters, which enhance both readability and accessibility. Thank you again!\n\n**4. Response to “Questions For Authors 1.”:**\nThank you for your insightful question. Network dynamism is explicitly modeled in our theoretical analysis by allowing the communication matrices $\\mathcal{W}^t$ (and the corresponding retraining matrices $\\tilde{\\mathcal{W}}^t$ ) to be time-varying. This reflects the fact that the network topology can change at each round. We introduce spectral gap upper bounds (e.g., $\\rho_1$ and $\\rho_2$) in our Assumption 4.8, which quantify the connectivity properties of these matrices. These bounds directly influence the convergence rate and error bounds derived in Theorem 4.9 and subsequent results. We hope our answer can clarify your confusion.\n\n\n**5. Response to “Other Comments Or Suggestions 2.＆3.”:**\nWe thank the reviewer for these valuable suggestions. In response, we have added a concise overview at the beginning of the appendix that outlines the contents and purpose of each section, making it easier for readers to navigate the supplementary material. Additionally, we carefully proofread the entire paper to correct any minor spelling or grammatical errors, ensuring clarity and a professional presentation. We hope these improvements meet your expectations.\n\nIf there are any further confusions/questions, we are happy to clarify and try to address them. Thank you again and your recognition means a lot for our work.", "claims_and_evidence": "The claims made in the paper are largely supported by theoretical analysis, experimental results, and comparative evaluations. Here’s an assessment of the key claims and their supporting evidence:\n1. PDUDT enables decentralized unlearning without additional communication or retraining: The proposed algorithm uses historical gradient information to approximate gradient residuals and eliminate a client’s contribution without retraining. The method does not require extra communication beyond standard decentralized learning updates. The algorithm’s efficiency is demonstrated theoretically and empirically, showing that it performs unlearning in O(t1) time, significantly reducing computational overhead compared to retraining-based methods.\n2. PDUDT is statistically indistinguishable from the perturbed retrained method: The paper provides a rigorous proof that PDUDT satisfies (epsilon, beta)-machine unlearning, ensuring that the output model is statistically close to one that would have been obtained by retraining from scratch. A Gaussian noise mechanism is added to further enhance indistinguishability, following the principles of differential privacy.\n3. PDUDT effectively removes the influence of the unlearned client: The membership inference attack (MIA) evaluation shows that after unlearning, the attack success rate drops to approximately 50%, indicating that the model has effectively \"forgotten\" the removed client’s data. The accuracy on the unlearned client’s class drops significantly, while accuracy on other classes remains stable, reinforcing that the client's influence has been successfully removed.", "methods_and_evaluation_criteria": "This paper effectively tackles the challenge of data unlearning in decentralized machine learning environments. The proposed methods are well-structured, and the evaluation criteria are comprehensive. Here’s why:\n1. The paper focuses on decentralized unlearning under dynamic topologies, a complex and underexplored issue. The proposed PDUDT introduces a gradient residual approximation technique that enables unlearning without retraining or additional communication, ensuring scalability and efficiency. Theoretical analysis guarantees that PDUDT is statistically indistinguishable from retraining-based unlearning.\n2. The paper employs multiple experimental metrics to assess the performance of the proposed unlearning algorithm, including:\n— Accuracy: Ensuring that the model retains high performance on unaffected data while effectively forgetting the targeted data.\n— Unlearning Time: Demonstrating that PDUDT achieves significant efficiency gains compared to retraining-based methods.\n— Attack Resistance: Validating unlearning effectiveness using membership inference attacks (MIA) to confirm that the removed data is no longer recoverable.\n\nOverall, the paper provides a well-founded, efficient, and theoretically sound approach to decentralized unlearning, supported by rigorous evaluation and empirical evidence.", "theoretical_claims": "The theoretical claims in the paper are well-supported and logically consistent, following standard mathematical frameworks from differential privacy and decentralized optimization. The proofs provide strong guarantees on statistical indistinguishability and convergence:\n1. The (epsilon, beta)-machine unlearning guarantee is based on differential privacy principles, ensuring that the model after unlearning is statistically indistinguishable from a retrained model. The proof constructs an upper bound on the difference between PDUDT’s output and a fully retrained model and then introduces Gaussian noise to mask this difference. By leveraging the Gaussian mechanism theorem, the authors establish that no one can reliably distinguish between the two models within a given probability bound.\n2. The convergence analysis aims to prove that PDUDT maintains a O(1/T) convergence rate after an unlearning operation. The proof follows a decentralized gradient descent approach, deriving an upper bound on the expected gradient norm over T communication rounds. By incorporating assumptions of Lipschitz smoothness and bounded variance, the analysis confirms that the learning process continues to converge at the same rate as standard decentralized optimization methods. The step-size conditions are carefully derived to ensure stability.", "experimental_designs_or_analyses": "The experimental designs and analyses in this paper appear well-structured and methodologically sound. The paper employs a variety of evaluation metrics and benchmark datasets to assess the effectiveness of the proposed PDUDT algorithm. Below is an assessment of the soundness and validity of these experiments:\n1. The experiments are conducted on standard benchmark datasets: MNIST, Fashion-MNIST, CIFAR-10, and SVHN, ensuring generalizability. The models used (CNN for simpler datasets and ResNet-18 for more complex datasets) align well with the dataset complexity. The experiments simulate decentralized environments with dynamic topologies, making the setup realistic for real-world applications. PDUDT is compared against multiple baseline methods (Retrain, FATS-Unl, FedRecovery, and HDUS), allowing for a comprehensive performance evaluation.\nWhile the decentralized learning setup is reasonable, the details on how the topology evolves dynamically over time are limited. More information on how client connections change could improve reproducibility.\n\n2. The paper evaluates PDUDT using three primary metrics:\n— Accuracy: To assess whether the model successfully forgets the unlearned data while maintaining overall performance.\n— Unlearning Time: To measure computational efficiency, showing that PDUDT is significantly faster than retraining-based methods.\n— Attack Resistance: Using membership inference attacks (MIA) to verify if the target client’s data has truly been forgotten.\nThese metrics effectively capture both efficiency and security aspects of unlearning. However, the impact of different levels of noise injection (used for statistical indistinguishability) on model utility and unlearning effectiveness could be further analyzed.\n\nIn summary, the experimental design is methodologically sound, and the analyses provide strong empirical evidence supporting PDUDT’s effectiveness. While the paper presents robust results, additional details on topology evolution and noise impact could further enhance validity.", "relation_to_broader_scientific_literature": "The key contributions of PDUDT relate to several areas of research, including machine unlearning, decentralized learning, efficient model updates, and theoretical guarantees. Prior works in machine unlearning, such as FedEraser (Liu et al., 2021) and FedRecovery (Zhang et al., 2023), primarily focus on removing client contributions in federated learning, often relying on gradient residual removal or retraining, but they assume the presence of a central server, limiting their applicability to fully decentralized systems. Recent decentralized unlearning approaches, such as HDUS (Ye et al., 2024) and BlockFUL (Liu et al., 2024a), propose heuristic solutions using distilled models or blockchain structures, but they lack rigorous theoretical guarantees. PDUDT addresses these limitations by introducing the first provable decentralized unlearning method, leveraging gradient residual approximations and a weighted removal mechanism to eliminate a client’s influence without requiring retraining or additional communication overhead, making it highly efficient in dynamic decentralized networks.", "essential_references_not_discussed": "The paper provides a comprehensive discussion of prior work in federated/decentralized unlearning, there do not appear to be critical missing references that would significantly alter the context or evaluation of the paper’s contributions. The theoretical and experimental analysis is well-grounded in previous research, making the discussion of related work sufficient and appropriate for the scope of the study.", "other_strengths_and_weaknesses": "Strengths:\n1. PDUDT is the first provable decentralized unlearning algorithm that operates under dynamic topologies, addressing a significant gap in privacy-preserving decentralized learning.\n2. The theoretical results of this article are detailed and in-depth. The paper derives an upper bound on the deviation between PDUDT’s output and a retrained model, providing rigorous guarantees on its unlearning performance (Theorem 4.9). The convergence proof (Theorem 4.11) ensures that after unlearning, the decentralized learning process continues to perform optimally, matching state-of-the-art decentralized learning results.\n3. The experimental section is comprehensive, covering multiple datasets and comparing against strong baselines. The performance advantages of the proposed PDUDT are demonstrated from multiple perspectives.\n4. The paper is well-structured, with clear theoretical formulations, algorithm descriptions, and proofs that make the methodology easy to follow.\n\n\nWeaknesses:\n1. Some experimental details are missing. For example, the paper does not explicitly clarify whether the experiments fully simulate dynamic network connections, which is crucial for demonstrating the adaptability of PDUDT in real-world decentralized settings.\n2. While the theoretical analysis is rigorous, some notations in the proofs are complex and could be slightly simplified for readability, especially for readers less familiar with decentralized optimization.", "other_comments_or_suggestions": "1. Given the extensive use of mathematical symbols throughout the paper, a notation table summarizing key variables and parameters could improve readability and accessibility.\n2. Since the appendix contains many sections with detailed proofs and experimental setups, it would be helpful to add a brief overview at the beginning of the appendix summarizing the role of each section. This would make it easier for readers to navigate the supplementary material.\n3. A careful proofreading of the paper may help identify and correct any minor spelling or grammatical errors to ensure clarity and professionalism.", "questions_for_authors": "1. How is network dynamism reflected in the theoretical results? The paper discusses dynamic topologies, but could you clarify where this is explicitly incorporated into the theoretical analysis? \n2. Additionally, was the dynamic nature of network links simulated in the experiments? If so, how frequently were connections updated or changed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a provable decentralised unlearning approach. The reviewers found this paper (1) proposes an interesting and meaningful algorithm, (2) the experiments are comprehensive and solid, (3) the algorithm is supported by solid theory, etc. I agree with the authors. So, I recommend to accept this paper.
Decision: Accept (poster)