DynFrs: An Efficient Framework for Machine Unlearning in Random Forest
Authors: Shurong Wang
Zhuoyang Shen
Xinbao Qiao
Tongning Zhang
Meng Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: Machine Unlearning
Random Forest
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: An efficient framework enabling online machine unlearning and continual learning for Random Forests.

Abstract: Random Forests are widely recognized for establishing efficacy in classification and regression tasks, standing out in various domains such as medical diagnosis, finance, and personalized recommendations. These domains, however, are inherently sensitive to privacy concerns, as personal and confidential data are involved. With increasing demand for the right to be forgotten, particularly under regulations such as GDPR and CCPA, the ability to perform machine unlearning has become crucial for Random Forests. However, insufficient attention was paid to this topic, and existing approaches face difficulties in being applied to real-world scenarios. Addressing this gap, we propose the DynFrs framework designed to enable efficient machine unlearning in Random Forests while preserving predictive accuracy. Dynfrs leverages subsampling method Occ(q) and a lazy tag strategy Lzy, and is still adaptable to any Random Forest variant. In essence, Occ(q) ensures that each sample in the training set occurs only in a proportion of trees so that the impact of deleting samples is limited, and Lzy delays the reconstruction of a tree node until necessary, thereby avoiding unnecessary modifications on tree structures. In experiments, applying Dynfrs on Extremely Randomized Trees yields substantial improvements, achieving orders of magnitude faster unlearning performance and better predictive accuracy than existing machine unlearning methods for Random Forests.

Published as a conference paper at ICLR 2025
DYNFRS: AN EFFICIENT FRAMEWORK FOR MACHINE UNLEARNING IN RANDOM FOREST
Shurong Wang', Zhuoyang Shen', Xinbao Qiao', Tongning Zhang' & Meng Zhang"*
'IJI Institute. Zhejiang University
(shurong. 22, mengzhang) @intl ju. edu. en
ABSTRACT
Random Forests are widely recognized for establishing efficacy in classification and regression tasks, standing out in various domains such medical diagnosis, finance, and personalized recommendations. These domains, however, are inher- ently sensitive to privacy concerns, as personal and confidential data are involved. With increasing demand for the right to be forgotten, particularly under regula- tions such as GDPR and CCPA, the ability perform machine unlearning has be- come crucial for Random Forests. However, insufficient attention was paid to this topic, and existing approaches face difficulties in being applied real-world sce- narios. Addressing this gap, we propose the DYNFRS framework designed to en- able efficient machine unlearning in Random Forests while preserving predictive accuracy. DYNFRS leverages subsampling method OCC(ç) and lazy tag strategy 1.Z,, and is still adaptable to any Random Forest variant. In essence, (CC(4) en- sures that each sample in the training set occurs only in a proportion of trees so that the impact of deleting samples limited, and L.ZY delays the reconstruction of subtree until demanded, thereby avoiding unnecessary modifications tree structures. experiments, applying DYNFRS on Extremely Randomized Trees yields substantial improvements, achieving orders of magnitude faster unlearn- ing performance and better predictive accuracy than existing machine unlearning methods for tree-based models. Our code is available here.
INTRODUCTION
Machine unlearning is an emerging paradigm of removing specific training samples from a trained model as if they had never been included in the training set (Cao and Yang, 2015). This concept emerged as response to growing concerns over personal data security, especially in light of regula- tions such as the General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA). These legislations demand data holders to erase all traces of private users' data upon request, safeguarding the right to be forgotten. However, unlearning single data point in most ma- chine learning models is more complicated than deleting it from the database because the influence of any training samples is embedded across countless parameters and decision boundaries within the model. Retraining the model from scratch on the reduced dataset achieve the desired objective, but is computationally expensive, making it impractical for real-world applications. Thus, the abil- ity of models efficiently "unlearn" training samples has become increasingly crucial for ensuring compliance with privacy regulations while maintaining predictive accuracy.
Over the past few years, several approaches to machine unlearning have been proposed, particu- larly focusing on models such as neural networks (Mehta et al., 2022; Cheng et al., 2023), support vector machines (Cauwenberghs and Poggio, 2000), and k-nearest neighbors (Schelter al., 2023). However, despite the progress made in these areas, machine unlearning in Random Forests (RFs) has received insufficient attention. Random Forests, due to their ensemble nature and the unique tree structure, present unique challenges for unlearning that cannot be addressed by techniques de- veloped for neural networks (Bourtoule et al., 2021) and methods dealing with loss functions and gradient (Qiao et al., 2024) which RFs lack. This gap is significant, given that RFs are widely used in critical, privacy-sensitive fields such as medical record analysis (Alam et al., 2019), financial
"Corresponding author.

---

Published as a conference paper at ICLR 2025
market prediction (Basak et al., 2019), and recommendation systems (Zhang and Min, 2016) for its effectiveness in classification and regression.
To this end, we study efficient machine unlearning framework dubbed DYNFRS for RFs. One of its components, the OCC(g) subsampling technique, limits the impact of each data sample to small portion of trees while maintaining similar better predictive accuracy through ensemble. DYNFRS resolves three kinds of requests on RFs: to predict the result of the query, to remove samples (machine unlearning), and add samples (continual learning ) the model. The highly interpretable data structure of Decision Trees allows us to make the following two key observations on optimizing online (require instant response) RF (un)learning. (1) Requests that logically modify the tree structure (e.g., sample addition and removal) can be partitioned. coalesced, and lazily applied up to later querying request. (2) Although fully applying a modifying request on a tree might have to retrain an entire subtree, a querying request after those modifications can only observe the updates on a single tree path in the said subtree. Therefore, we can amortize the full update cost on a subtree into multiple later queries that observe the relevant portion (see Fig. 1).
To this effect, we propose the lazy tag mechanism LZY for fine-grain tracking of pending updates on tree nodes to implement those optimizations, which provides a low latency online (un)learning RF interface that automatically and implicitly finds the optimal internal batching strategy within nodes.
We summarize the key contributions of this work in the following:
Subsampling: We propose subsampling method OCC(g) that guarantees 1/q times (where < 1) training speedup and an expected l times unlearning speedup compared to naïve retraining approach. Empirical results show that OCC(q) brings improvements to predictive performance for many datasets.
Lazy Tag: We introduce the lazy tag strategy LZY that avoid subtree retraining for unlearn- ing in RFs. The lazy tag interacts with modification and querying requests to obtain the best internal batching strategy for each tree node when handling online real-time requests.
Experimental Evaluation: DYNFRS yields a 4000 1500000 times speedup relative to the naïve retraining approach and is orders of magnitude faster than existing methods in se- quential unlearning and multiple times faster in batch unlearning. In the online mixed data stream settings, DYNERS achieves averaged 0.12 ms latency for modification requests and 1.3 ms latency for querying requests on a large-scale dataset.
2 RELATED WORKS
Machine unlearning concerns the complicated task of removing specific training sample from a well-trained model (Cao and Yang, 2015). Retraining the model from scratch ensures the complete removal of the sample's ' impact, but it is computationally expensive and impractical, especially when the removal request occurs frequently. Studies have explored unlearning methods for support vector machines (Cauwenberghs and Poggio, 2000), and k-nearest neighbor (Schelter et al., 2023). Lately, SISA (Bourtoule et al., 2021) has emerged as a universal unlearning approach for neural networks. SISA partitions the training set into multiple subsets and trains a model for each subset (sharding), and the prediction comes from the aggregated result from all models. Then, the unlearning is ac- complished by retraining the model on the subset containing the requested sample, and a slicing technique is applied in each shard for further improvements. However, as stated in the paper, SISA meets difficulties when applying slicing to tree- based models.
Schelter et al. (2021) introduced the first unlearning model for RFs based on Extremely Randomized Trees (ERTs), and used a robustness quantification factor to search for robust splits, with which the structure of the tree node will not change under a fixed amount of unlearning requests, while for non-robust splits, subtree variant is maintained for switching during the unlearning process. However, HedgeCut only supports removal and Lowd (2021) introduced DaRE, an RF variant similar to ERTs, using random splits and caching to enhance unlearning efficiency. Random splits in the upper tree layers help preserve the structure, though they would decrease predictive accuracy. DaRE further caches the split statistics, resulting in less subtree retraining. Although DaRE and HedgeCut provide a certain speedup for unlcarning, they are incapable of batch unlearning (unlearn multiple samples simultaneously in one request).
small fraction (0.1%) of the entire dataset. Brophy
2

---

Published as a conference paper at ICLR 2025
Laterly, unlearning frameworks like OnlineBoosting (Lin et al., 2023) and DeltaBoosting (Wu al., 2023) are proposed, specifically designed for GBDTs, which differ significantly from RFs in training mechanisms. OnlineBoosting adjusts trees by using incremental calculation updates in split gains and derivatives, offering faster batch unlearning than DaRE and HedgeCut. However, it remains an approximate method that cannot fully eliminate the influence of deleted data, and its high computa- tional cost for unlearning individual instances limits its practical use in real-world applications. In the literature, Sun et al. (2023) attempted lazily unlearn samples from RFs, but their approach still requires subtree retraining and suffers from several limitations in both clarity and design. Dif- ferent from others, our proposed DYNERS excels in both sequential and batch unlearning settings and supports learning new samples after training.
3 BACKGROUND
Our proposed framework is designed for classification and regression tasks. Let S R x y represent the underlying sample space. The goal is to find hypothesis h that captures certain properties of the unknown based on observed samples. We denote each sample by (x. where E Fd is d-dimensional vector describing features of the sample and y Y represents the corresponding label or value. Denote S as the set of observed samples, consisting of n independent and identically distributed (i.id.) samples (x,, n.) for i E [n] drawn from D, where [n]] 2 {i E Z 1 1 i S n). For clarity, we call the k-th entry of x attribute k.
3.1 EXACT MACHINE UNLEARNING
The objective of machine unlearning for a specific learning algorithm A is to efficiently forget certain samples. An additional constraint is that the unlearning algorithm must be equivalent to applying A to the original dataset excluding the sample to be removed.
Formally, let the algorithm A S H maps training set S E S to hypothesis A(S) H.
We then define A H x S x D + H as an unlearning algorithm, where A AA(ASS) xx,y) produces the modified hypothesis with the impact of (x, y) removed. The algorithm A termed an exact unlearning algorithm the hypotheses A(S) { {xx, y)3) and A- (A(S). S, (x, y)) follow the same distribution. That is, for arbitrary hypothesis h H. we have the following:
Pr [A(S (((x = h) = Pr [A (A(S), (x,u)) h]
3.2 RANDOM FOREST
Prior to discussing Random Forests, it is essential first introduce its base learner, the Decision Tree (DT), a well-known tree-structured supervised learning model. It is proven that finding the optimal DT is NP-Hard (Hyafil and Rivest, 1976; Demirović et al., 2022); thus, studying hicrarchical approaches is prevalent in the literature. In essence, the tree originates from root containing all training samples and grows recursively by splitting a leaf node into new leaves until a predefined stopping criterion is met. Typically, DTTs take the form of binary trees where each node branches into two by splitting S, (the set of samples obsessed by the node u) into two disjoint sets. Let u, and u, be the left and right child of node and we say split (a, w) partitions S,, into Suy and Su, if
S., = {(x,)) y) E S. X2 S [w),
Sy. = -(x, v) E Su x, > w)-
The best split (at, w A arg min ()) a E [p]. w E R} is found among all possible splits by optimizing an empirical criterion score 1(S, (x, v)) such the Gini index lo (Breiman et al., 1984), or the Shannon entropy LE (Quinlan, 1993):
|Sa
S SSa
To(Sun (a,
Σ
1
Σ oE>
[Sul
1
|Se.el |S.]
|So.c] [Sa]]
IE(Su, ())
Σ
logg
w JeE
where Sa. & ((x,8) E Su y = c}. The prediction for sample (x, y) starts with the root and recursively goes down to a child until a leaf is reached, and the traversal proceeds to the left child Xag E " and to the right otherwise.
3

---

Published as a conference paper at ICLR 2025
Random Forest (RF) is ensemble of independent DTs, where each tree is constructed with an element of randomness to enhance predictive performance. This randomness reduces the variance of the forest's predictions and thus lowers prediction enrrr (Breiman, 2001). One method involves selecting the best split (a), w() among p randomly selected attributes rather than all d attributes. Additionally, subsampling methods such as bootstrap (Breiman al., 1984), m-out-of-n boot- strap (Genuer et al., 2017), are used to introduce more randomness. Bootstrap creates a training set s(t) for each tree Sf by drawing n iidd samples from the original dataset S with replacement. A variant called mn-out-ofnn bootstrap randomly picks m different samples from S to form S((), These subsampling methods increase the diversity among trees, enhancing the robustness and generaliz- ability of the model. However, all existing RF unlcarning methods do not adopt subsampling, and Brophy and Lowd (2021) claims this exclusion does not affect the model's predictive accuracy.
3.3 EXTREMELY RANDOMIZED TREE
Extremely Randomized Tree (ERT) (Geurts et al., 2006) is a variant of the Decision Trees, but ERTs embrace more randomness when finding the best split. For tree node u, both ERT and DT find the best splits on randomly selected attributes a1..p S [d]. but for each attribute a% (k E [p],, ERT considers only s candidates {(ak, WK,s) i E [s]], where wk.1 are uniformly sampled from range [min(xi,,, (x,, M1)) E S. max (x,, Mb) S. Then, the best split (a w;) is set as the candidates with optimal empirical criterion score (where / could be either Ia or IE):
(a w A arg min ((S., (ax, wk,,)) k E [p]. i [s]].
Compared to DTs considering all (p))S,)) possible splits, ERTs consider only Opps) candidates while maintaining similar predictive accuracy. This shrink in candidate size makes ERTs less sensi- tive to sample removal, and thus makes ERTs outstanding for efficient machine unlearning.
4 METHODS
In this section, we introduce the DYNFRS framework, which is structured into three components - the subsampling method OcC(g), the lazy tag strategy 1.ZY, and the base learner ERT. occ(g) allocates fewer training samples to each tree (i.e., s(I).... ,())) with the aim to minimize the work brought to each tree during both training and unlearning phrase while preserving par predic- tive accuracy. The lazy tag strategy LZY takes advantage of tree structure by caching and batching reconstruction needs within nodes and avoiding redundant work, and thus enables an efficient au- tomatic tree structure modification and suiting DYNFRS for online fixed data streams. ERT require fewer adjustments towards sample addition/removal, making it the appropriate base learner for the framework. In a nutshell, DYNFRS optimize machine unlearning in tree-based methods from three perspectives across trees (OCC(g)). across requests (LZZY), and within trees (ERT).
4.1 TRAINING SAMPLES SUBSAMPLING
Introducing divergence among DTs in the forest is crucial for enhancing predictive performance, as proven by Breiman (2001). Developing novel subsampling methods can further enhance this effect. Recall that represents the training set, and 5(4) denotes the training set for the t-th tree fp. Empirical results (Section 5.2) indicate that having reduced training set (i.e., |S(0] < [S)) does not degrade predictive performance and may even improve accuracy as more randomness is involved. In the following, we demonstrate that ocC(4) leverages smaller |5(0] and considerably shortens training and unlearning time.
The key idea is that if sample (x v,) E S does not occurs in tree y (i.e., (x, & S(1), then tree sp: unaffected when unlearning (x4, v1)) Therefore, it natural to constrain the occurrence of each sample (x,, v,) S in the forest. To achieve this, ocC(g) performs subsampling of training samples, The algorithm starts with iterating through all training samples, and for each sample (x, J.) E S, k different trees (say they are Pi...... PPs, with i S [m]) are randomly and independently drawn from all T trees (Algorithm 1: line 5), where is determined by the proportion factor (q < 1) satisfying & = [qT]. Then, occ(g) appends (x,, v.) to all of the drawn tree's 's own training set (8th), 8662) , Stie) (Algorithm 1: line 6-8). When all sample allocations finish, The
trees instead
4

---

Published as a conference paper at ICLR 2025
Normal Node
Deleted Node
Tagged Node
Figure 1: Left: (a) A sample addition/remooal request arises. (b) Nodes it impacts are covered in the blue path. (c) There is change in best split in the purple node (but not in other visited nodes), so a tag is placed on it. (d) The subtree of the tagged node is deleted. Middle: (a) A querying request arises. (b) Nodes that determine the prediction are covered in the orange path. (c) The tag pushed down recursively until the query reaches a leaf. Right: A detailed process of how the querying request grows (split tagged node, push down its tag its children recursively) the tree.
algorithm terminates in ((n)) = O Intuitively, occ(g) ensures that each sample occurs in exactly & trees in the forest, and thus reduces the impact of each sample from all T trees to merely [q7] trees.
Further calculation confirms that occ(g) provides expected 1 1/ unlearning speedup toward naively retraining. When unlearning an arbitrary sample with occ(g), without loss of generality (Iree order does not matter as they are independent), assume it occurs in the first = [4T"] trees PP, P Pkk Calculation begins with finding the sum of all affected tree's training set sizes:
|s|| ΣΣ
Now
St0
1 (() E es(").
As for each sample (x,, v.) E S, occ(g) assures that Pr((x,, E -000== k/T = giving,
[s] ΣΣ E [((x))))) E s -00-=11
[S] k
=Σ Pr (x, E sw) = -
E [cce [c]]
==
For the naïve retraining method, the corresponding sum of affected sample size is TISI (Naii T(S)) as trees are affected. As the retraining time complexity linear to Noce and Nmm (Appendix A.2, Theorem 2), the expected computational speedup provided by OCC(g) is when OCC(4) and the naive method adopt the same retraining method.
= 1/9²,
The above analysis also concludes that training Random Forest with OCC(g) will result in 1/g times boost. In practice, we will empirically show (in Section 5.2) that by taking = 0.1 or q 0.2, the resulting model would have a similar even higher accuracy in binary classification, which benefits unleaming with a 100x or 25x boost, and make training 10x or 5x faster.
4.2 LAZY TAG STRATEGY
There observations on tree-based methods that make LZY possible. (1) During the unlearning phase, the portion of the model that is affected by the deleted sample is known (Fig. left, blue path, and deleted nodes). (2) During the inference phase, only a small portion (a tree path) of the whole model determines the prediction of the model (Fig. middle, orange path) (Louppe, 2015). Along the model unnecessary until a querying able to develop the LZY lazy tag strategy that minimizes adjustments to tree
with another universal observation request arises, structure when facing a mixture sample addition/removal and querying requests. In contrast, neural network based methods do not fully possess the properties mentioned in observation (1) and (2), although encouraging exploration on similar properties has been reported (Morcos et al., 2018; Goh et al., 2021; Zhu et al., 2024).
(3) Adjustments
Intuitively, tree node u can remain unchanged if adding/removing sample does not change its best split (at, w Then, the sample addition/removal request would affect only one of the w's
5

---

Published as a conference paper at ICLR 2025
children since the best split partitions u into two disjoint parts. Following this process recursively, the request will go deeper in the tree until a leaf is reached or a change in best split occurs. Unfortu- nately, if the change in best split occurs in node u, we need to retrain the whole subtree rooted by to meet the criterion for exact unlearning. Therefore, a sample addition/removal request affects only path and subtree of the whole tree, which is observation (1).
As retraining a subtree is tome-consuming, we place a tag on u, denoting it needs a reconstruction (Algorithm 2: line: 8-9). When another sample addition/removal request reaches the tagged later, it just simply ends there (Algorithm 2: line 7) since the will-be-happening reconstruction would cover this request as retraining is the most effective unlearning method. But when querying request meets a tag, we need to lead it to a leaf for an accurate prediction (observation (3)). As we do not retrain the subtree, and recall that observation (2) states that the query only observes a path in the tree, so the minimum effect to fulfill this query is to reconstruct the tree path that connects and a leaf, instead of the entire subtree u. To make this happen, we find the best split of u and grow the left and right child. Then, we clear the tag on since it has been split and push down the tags to both of its children, indicating further splitting on them is needed (A (Algorithm 2: line 26-27). As depicted in Fig. right side, the desired path reveals when the recursive pushing- process reaches leaf.
To summarize, only queries activate node reconstruction within a node, and LZY automatically batches all node reconstructions between two visiting queries, saving plenty of computational ef- forts. From the tree's perspective, L,ZY replaces the subtree retraining by amortizing it into path constructions in queries that the lateney for responding modification requests is reduced. Un- like OcC(2), which takes advantage of ensemble and brings less workload to each tree, LZY relies on tree structures, dismantling requests into smaller parts and handling these parts in batches for smaller workload.
4.3 UNLEARNING IN EXTREMELY RANDOMIZED TREES
Despite OCC(g) and LZY making no assumption on the forest's base learner, we opt for Extremely Randomized Trees (ERTs) with the aim of achieving the best performance in machine unlearning. Different from Decision Trees, ERTs are more robust to changes in training samples while remain- ing competitive in predictive performance. This robustmess ensures the whole DYNFRS framework undergoes fewer changes in tree structures when unlearning.
In essence, each ERT node finds the best split among (usually around 5 to 20) candidates on one attribute instead of all possible splits (possibly more than 10") so that the best split has a higher chance to remain unchanged when a sample addition/remooal occurs in that node. Additionally, takes a time complexity of (ps)) for ERTs to detect whether the change in best split occurs all candidate's 's split statistics are stored during the training phase, which is much more efficient than the S.,) detection for Decision Trees. To be specific, for each ERT node u, we store a subset of attributes d1--p S [d], and for each interested attribute as (k E [p)), different thresholds 1....... are randomly generated and stored. Therefore, a total of p- 8 candidates {(as, wR.i) | k E [p]. [s]] determine the best split of the node. Furthermore, the split statistics of each candidate (ak, wK,s) are also kept, which consists of its empirical criterion score, the number of samples less than the threshold, and the number of positive samples less than the threshold. When sample addition/removal occurs, each candidate's 's split statistics can be updated in (1), and we assign the one with optimal empirical criterion score as the node's best split.
However, one special case is that when a change in range of ag occurs, a resampling on Wk.1-..s is needed. ERT node find the candidates of attribute 0₁ by generating i.idd samples following a uniform distribution on [ag,min: dgg,mxx], where 0g,min 2 min(xi,a, I (x,, v;) E S.) and 0g.max is defined similarly. Therefore, we keep track of 0g,min and ma, and resample candidates' threshold when the range [ax,min: max] changes due to sample addition/removal.
4.4 THEORETICAL RESULTS
Due to the page limit, all detailed proofs of the following theorems are provided in Appendix A.2.
We first demonstrate that DYNFRS's approach to sample addition and removal suits the definition of exact (un)learning (Section 3.1), validating the unlearning efficacy of DYNFRS:
Theorem 1. Sample addition and removal for the DYNFRS framework are exact.
6

---

Published as a conference paper at ICLR 2025
Next, establish the theoretical bound for time efficiency of DYNFRS across different aspects. Conventionally, for an ERT node u and a certain attribute a, finding the best split attribute a re- quires time complexity of [[ log (w,l). In this work. propose more efficient O[S log s) algorithm (see Appendix A.2, Lemma 1) to find the desired split by turning it into a range addition and query problem. Since [S,. > in most cases, and usually log2 I this new algorithm is advantagcous in both theoretical bounds and practical performance.
For DYNERS with T trees, each having maximum depth dmaxx and considering p attributes per node, the time complexity for training on a training set with n = |S] is derived as:
Theorem 2. Training DYNERS yields time complexity of Ogg dm s).
DYNFRS also achieves an outstanding time complexity for sample addition/removal. For clarity, we define nafr as the sum of sample size ([S..) of node a s.t. u is met by the sample addition/removal request, and change in range occurs, and be the number of attributes whose range has changed.
Further, denote Tazy as the sum of sample size ((Sw) of all node u s.t. is tagged due to this request. Based observations described in Section 4.2, claim the following:
Theorem 3. Modification (sample addition removal) in DYNFRS yields time complexity of
Og if no attribute range changes occur while OqTTdmaxPS + caay logllog 8) otherwise.
Theorem 4. Query in DYNERS yields time complexity of O(Tdmax) if no lazy tag is met, while O(Tamax + pTuy log s) otherwise.
5
EXPERIMENTS
In this section, empirically evaluate the DYNFRS framework on the predictive performance, machine unlearning efficiency, and response latency in the online mixed data stream setting.
5.1
IMPLEMENTATION
Due to the page limit, this part moved to Appendix A.3.
5.1.1 BASELINES
We use DaRE (Brophy and Lowd, 2021), HedgeCut (Schelter et al., 2021), and OnlineBoosting (Lin et al., 2023) as baseline models. Although OnlineBoosting employs a different learning algorithm, it is included due to its superior performance in batch unlearning. Additionally, Random Forest Classifier implementation (we call it Vanilla in tables below) from scikit-learn to provide additional comparison of predictive performance. For all baseline models, adhere the instructions provided in the original papers and use the same parameter settings. More details regarding the baselines are in Appendix A.4.
included the
5.1.2 DATASETS
Table 1: Datasets specifications. (# train: number of training samples; test: number of testing samples; % pos: percentage of positive samples; # #attr: number of attributes; # attr-hot: number of attributes after one-hot encoding: # cat: number of categorical attributes.)
Datasets
# train
# test
% pos
# attr
# attr-hot
# #cat
Purchase
9864
2466
.154
17
17
0
Vaccine
21365
5342
466
36
184
36
Adult
32561
16281
.239
107
Bank
32950
8238
Heart
56000
14000
.500
12
12
0
Diabetes
81412
20354
.461
43
253
36
NoShow
88421
22106
.202
17
98
2
Synthetic
800000
200000
.500
0
Higgs
8800000
2200000
.530

---

Published as a conference paper at ICLR 2025
We test DYNERS 9 binary classification datasets that vary in size, positive sample proportion, and attribute types. The technical details these data sets can be found in Table For better pre- dictive performance, we apply one-hot encoding for categorical attributes (attributes whose values are discrete classes, such as country, occupation, etc.). Further details regarding datasets are offered in the Appendix A.5.
5.1.3 METRICS
For predictive performance, we evaluate all the models with aceuracy (number of correct predictions divided by the number of tests) if the dataset has less than 21 % positive samples or AUC-ROC (the area under receiver operating characteristic curve) otherwise.
To evaluate models' unlearning efficiency, we follow Brophy and Lowd (2021) and use the term boost standing for the speedup relative to the naïve retraining approach (i.e., the number of samples unlearned when naively retraining unlearns sample). Each model's naive retraining procedure is implemented the same programming language as the model itself. Additionally, we report the time elapsed during the unlearning process for direct comparison.
5.2 PREDICTIVE PERFORMANCE
Table 2: Predictive performance (1) comparison between models. Each cell contains the accuracy or AUC-ROC score with standard deviation a smaller font. The best-performing model is bolded.
Online Boosting
DYNFRS (q = 0.1)
DYNFRS (q = 0.2)
Datasets
DaRE
HedgeCut
Vanilla
Purchase
9327=.001 .01
9118= n011
.9372= 0011
.9207=0000
.9327..om
.3359..om
Vaccine
.7916=.00s
.7706=.00z .002
.7939=.00
.80122.000
.7911#.0m1
.79344.002
Adult
.8628
.8428
.001
.8637=
.8503+.000 .000
.8633..00
.8650
Bank
.9420:.00 .000
.9350=.cm
.000
.9414#.00
.9436 +.06+0000
.9417+.000
9.3664000
Heart
.7344#.001
.7195 e: 0001
.7342 + .0001
.7301
.7358 +.02
.73664.000
Diabctes
.6443=.001
.6190=
000
.6435=.00 001
.64622+000
.6453=.001
.6470=.002
NoShow
.73
.7170= 000
.7387 0000
.72692.000
.7335=.001
.73562.000
Synthetic
0451=.000
.9441 000
.9309+.000
.94244.000
.9454..000
Higgs
.7441 :000
.7434
.7255+.000
.7431#.000
77475#0000
Effect of 9 on Predictive Accuracy
Unlearning v.s. Retraining
8666
.86-
Accuracy
.863
Accuracy
.84-
860
Adult
82
857-
Unlearned DYNFRS
854
Adult
80
Retrained DYNFRS
.648
66
Accuracy
6645
Accuracy
.64
.642
.33
Diabetes
.639
Unlearned DYNFRS
.636
Diabetes
.61
Retrained DYNFRS
0.01
0.10
0.20
0.30
0.50
0.75
1.00
0.01
0.10
0.90
0.99
9
Proportion of samples unlearned
Figure 2: DYNERS with different is tested on Figure 3: DYNFRS's unlearning exactness. The the dataset Adult and Diabetes, and the tendency blue-gray solid line represents the accuracy ten- is shown by the curve with the standard deviation dency of the unlearned model, while the orange shown by error bars.
dotted line represents that of the retrained model.
We evaluate the predictive performance of DYNFRS in comparison with other models in 9 datasets.
The detailed results listed in Table 2. In out of datasets, DYNFRS(q 0.2) outperforms all other models in terms of predictive performance, while OnlineBoosting shows an advantage in the Vaccine and Bank dataset, and scikit-leamn Random Forest comes first in Purchase and NoShow.
8

---

Published as a conference paper at ICLR 2025
These results show that (CC(0.2) sometimes improves the forest's predictive performance. Looking closely at (Y = 0.1), we observe that its accuracy is similar to that of DaRE and the scikit- learn Random Forest. All the hyperparameters used in DYNFRS are listed in the Appendix A.12.
The effects of q are assessed on the two most commonly tested datasets (Adult and Diabetes) in RF classification. From Fig. Adult dataset, DYNFRS's predictive accuracy peaks at g = 0.4, while a similar tendency is observed for the Diabetes dataset with the peak at q 0.2. However, avoid tuning on g, we suggest choosing 0.2 to optimize accuracy and 0.1 to improve unlearning efficiency.
acute drop in predictive accuracy is obvious when 0.1. For the
To determine whether DYNERS(y 0.1) achieves exact unlearning (Section 3.1), compare it model with different sample removal proportions. Specifically, Let S denote the of samples requested for removal, and we compare the predictive performance of an unlearned model trained on complete training set S and subsequently unlearning all samples in S with the retrained model, which is trained directly on S Note that both models adopt the same training algorithm. As depicted in Fig. 3. the performance of both models is nearly identical across different removal proportions (i.e., |S 1/(S). This close alignment suggests that, empirically, the unlearned model and the retrained model follow the same distribution (Equation 1).
with a ferain-ffrom-soee
5.3
SEQUENTIAL UNLEARNING
Sequential Unlcarning Boost
Speedup v.s. Naive
106
DaRE
DYNFRS(q 0.1)
10
DyNFRS( 0.2)
104
103
102
Purchase
Vaccine
Adult
Bank
Heart
Diabetes
NoShow
Synthetic
Higgs
Figure 4: Comparison sequential unlearning boost (1) between DYNFRS with different g and DaRE, and error bars represent the minimum and maximum values among five trials.
In this section, we evaluate the efficiency DYNFRS in sequential unlearning settings, where mod- els process unlearning requests individually. In experiments, models are fed with a sequence of unlearning requests until the time elapsed exceeds the time naive retraining model unlearns one sample. To ensure that DYNFRS does not gain an unfair advantage by merely tagging nodes without modifying tree structures, we disable LZY and use a Random Forest without occ(4) as the naïve retraining method for DYNFRS. As shown in Fig. 4, DYNFRS consistently outperforms DaRE, the state-of-the--at method in sequential unlearning for RFs, across all datasets in both = 0.1 and q 0.2 settings, and achieves 22x 523x speedup relative DaRE. Furthermore, DYNFRS demonstrates a more stable performance compared to DaRE who exhibits large error bars in Higgs.
HedgoCut excluded from the plot as is unable unlearn more than 0.1% of the training set, making boost calculation often impossible. OnlineBoosting is also omitted due to poor performance, achieving boosts of less than 10. This inefficiency stems from its slow unlearning efficiency of individual instances (see Fig. upper-left plot). Appendix A.6 contains more experiment results.
5.4 BATCH UNLEARNING
We measure each model's batch unlearning performance based on execution time (DYNFRS's run- time includes retraining all the tagged subtree), where one request contains multiple samples to be unlearned. The results indicate that DYNFRS significantly outperforms other models across all datasets and batch sizes (see Appendix A.6 for complete results). In the lower-left and lower-right plots of Fig. 5, DaRE demonstrates excessive time requirements for unlearning 0.1% and 1% of samples in the large-scale datasets Synthetic and Higgs, primarily due to its inefficiency when deal- ing large batches. In contrast, OnlineBoosting achieves competitive performance on these datasets, but DYNERS completes the same requests in half the time. Furthermore, OnlineBoosting shows

---

Published as a conference paper at ICLR 2025
Instance
100 Instances
Batch Unlearning Efficiency Comparison
106
DaRE
-10s
10
Online Boosting
DYNFRS I-
11
Unlearning time (ms)
FI0
10
10
10
0.1% of All Samples of All Samples
-10
100
10
DaRE
OnlineBoosting
105
11
DYNERS w/o LZY
DYNFRS
102
10a
10
10a
103
10
10
106
Adult Diabetes
Synthetic
Higgs
Adult
Diabetes
Synthetic
Higgs
Number of samples unlearned
Comparison of the batch unlearning runtime tendency (4) between models using dif- ferent numbers of unlearned samples in Higgs. Runtimes are measured in milliseconds (ms).
Figure 6:
Figure 5: Comparison of the batch unlearning runtime (4) of DYNFRS and two baseline meth- ods under with 4 different unlearning batch sizes.
the poorest performance single-instance unlearning (Fig. 5 upper-left), and this inability limits its effectiveness in sequential unlearning. Overall, Fig. demonstrates that DYNFRS is the only model that excels in both sequential and batch unlearning contexts.
Further investigation of each model's behavior across different unlearning batch sizes is presented in Fig. 6. Both DaRE and DYNFRS w/o LZY exhibit linear trends the plot, indicating their lack of specialization for batch unlearning. Mcanwhile, the curve of OnlineBoosting maintains station- ary performance for batch sizes up to 10a but experiences a rapid increase in runtime beyond this threshold. Notably, the curve for DYNFRS stays below those of all other models, demonstrating its advantage across all batch sizes in dataset Higgs. Additionally, DYNFRS the only model whose runtime converges for large batches, attributed the presence LZY.
5.5 ONLINE MIXED DATA STREAM
In this section, we introduce the online mixed data stream setting, which satisfies: (1) there are types of requests: sample addition, sample removal, and querying: (2) requests arrive in mixed sequence, with no prior knowledge of future requests until the current one is processed; (3) the amount of addition and removal requests are roughly balanced, allowing unchanged model's hyper- parameters; (4) the goal is to minimize the latency in responding to each request. Currently, no other tree-based models but DYNFRS can handle sample addition/removal and query simultancously.
Due to the page limit, this part is moved to Appendix A.
CONCLUSION
In this work, we introduced DYNFRS, framework that supports efficient machine unlearning in Random Forests. Our results show that DYNFRS is 4-6 orders of magnitude faster than the naive re- training model and 2-3 orders of magnitude faster than the state-of-the-arr Random Forest unlearning approach DaRE (Brophy and Lowd, 2021). DYNFRS also outperforms OnlineBoosting (Lin al., 2023) in batch unlearning. In the context of online data streams, DYNFRS demonstrated strong per- formance, with an average latency of 0.12 ms on sample addition/removal in the large-scale dataset Higgs. This efficiency is due the combined effects of the subsampling method ocC(g), the lazy tag strategy LZY, and the robustness of Extremely Randomized Trees, bringing Random Forests closer to real-world applicability in dynamic data environments.
For future works, we will investigate more strategies that take advantage of the tree structure and accelerate Random Forest in the greatest extent for real-world application.
10

---

Published as a conference paper at ICLR 2025
7 REPRODUCIBILITY STATEMENT
Code: We provide pseudocode to help understand this work in Appendix A.I. All our code is publicly available at: https: /github.....//g com/ shurongwang/DyaFF
Datasets: All datasets are either included in the repo, or a description for how to download and preprocess the dataset is provided. All datasets public and raise ethical concern..
Hyperparameters: All parameters of proposed framework are provided in Appendix A.12, Table 15.
Environment: Details of our experimental setups are provided in Appendix A.3.
Random Seed: C++'s mt19937 module with random device for all random be- havior, with the random seed determined by system time.
REFERENCES
Md. Zahangir Alam, M. Saifur Rahman, and M. Sohel Rahman. A random forest based predictor for medical data classification using feature ranking. Informatics in Medicine Unlocked, 15: 100180, 2019. ISSN 2352-9148. doi:
100110. URL https:
www. www.ssseeeeeeieee.ooo.o com/
E. Alpaydin and Fevzi. Alimoglu. Pen-Based Recognition of Handwritten Digits. UCI Machine Learning Repository, 1996. URL
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature Communications, 5:4308, 2014. doi: 10. 10..8///momm5508..
URL https:ttp/...m /oi. wwt//o..g000ooooo.o 1038 (0//3///coo /30oms5308.
Suryoday Basak, Saibal Kar, Snehanshu Saha, Luckyson Khaidem, and Sudeepa Roy Dey. Predict- ing the direction of stock market prices using tree-based classifiers. The North American Journal of Economics and Finance, 47:552-567, 2019, ISSN 1062-9408. doi: https://do..or//0..000 j j.majef.2018.0660133. URL https: www. wcwenceeieeet...............ie.e com/ science/article.
p
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI:
http:://ob..r//1224444//5111
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Chov Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning, In 2021 IEEE Sym- posium Security and Privacy (SP), pages 141-159, 2021. doi: 10.1 (0.1109/SP4000 2021100019.
L. Breiman, J. Friedman, C.J. Stone, and R.A. Olshen. Classification and Regression Trees. Taylor & Francis, 1984. ISBN 9780412048411 URL https://books: www.eeggogooooooooooooooooo
Leo Breiman. Random Forests. Machine Learning, 45(1):5-32, October 2001. ISSN 1573-0565.
doi: 10. 00.10033/A11000933444444 URL https://link.. http//iinnn..iinggeeeeeeee springer com/ artaiiie/iii.
Company: Springer Distributor: Springer Institution: Springer Label: Springer Number: 1 Publisher: Kluwer Academie Publishers.
//023/::100 0133/:1111093340433
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1092-1104. PMLR, 18-24 Jul 2021. URL https: http:///ppceeeeeeeeeee mesiingsm.l.........mmmm.... mlr wrwssp/ssss..................... /v..//v1///// https///ww1////pppylllla...
Bull, Slavitt, and Lipstein. Harnessing the power of the crowd increase capacity for data science in the social sector. In ICML #Data4Good Workshop, 2016.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. 2015 IEEE Symposium Security and Privacy, pages 463-480, 2015. doi: 10. 109/5,2005.335.

---

Published as a conference paper at ICLR 2025
Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support tor machine learning. In T. Leen, T. Dietterich, and Tresp, editors, Advances in Neural Information Processing Systems. volume 13. MIT Press, 2000. URL https:: / htppppocedings... inturrpps. cc ccc/paper_fill filerr_fills/eeeeeee wttpaaaeepppp/p////eaaaaaa/ 155fa09596c7el 1eff
pdf.
Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, and Marinka Zitnik. GNNDELETE: A GENERAL STRATEGY FOR UNLEARNING IN GRAPH NEURAL NETWORKS. 2023.
Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher
Leckie, Kotagiri Ramamohanarao, and Peter J. Stuckey. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26): 1-77) 2022. papers / vv23//22///// 20- 520 .0mml.
URL http://////// jmir..moiog. pttppppers/////////paaoooessssse
DrivenData. Flu shot learning: Predict hinl and seasonal flu vaccines. https: //wp::://www drivendata wwt.ooog//oo//oooo wttp/tttpptiiooooooooooooo 66/f ff/ffu-shoot-eo baahoot-eaannnn/dtaaalllll 2019.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2019. http://archive.
ics.ucti www.uuci.dmmm..
Hadi Fanaee-T. Bike Sharing.
UCI Machine Learning Repository, 2013.
DOI:
http://dbb.rr//0224322/CWW3
Robin Genuer, Jean- Poggi, Christine Tuleau-Malot, and Nathalie Villa- Vialanei.. Random forests for big data. Big Data Research, http://wwww/.../
2017. ISSN 2214-5796. doi: https://doi.
URL http://wwwwwieeeeieeeeee.ee. wttp://eeetrttcccieeeeeeeecomsee com/science/ article/ss11/2221557911333
htg///0.00166.bbd:211..0...
Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine Learning,
63(1):3-42, April 2006. ISSN 1573-0565, doi: 10.10077.00944-06-622--1. URL https: 10. 1//oii.rr/100.100/1119999 -006-0000000000 6226-1.
Gabriel Goh, Nick Cammarata, Chelsea Voss, Shan Carter, Michael Petrov, Ludwig Schubert, Alec Radford, and Chris Olah. Multimodal neurons in artificial neural networks. Distill, 6(3)e30, 2021.
Laurent Hyafil and Ronald L.. Rivest. Constructing optimal binary decision trees np-complete. Information Processing Letters, 5(1):15-17, 1976. ISSN 0020-0190. doi: https///oi.oog// 10.101660020-0011777999999888 URL htttaa///www.eceeeeedeeeee.oom
arricile/p110002011997999999
Kaggle. Medical appointment no shows. httpss//www..kkgglee.co///oooooe
noshovappointments. 2016.
Kaggle. Cardiovascular discase dataset. https://wwet
http://wwww.klll.c.coooooo/o/ sulianova/ auulaanovaacarrdovasscuo http///aroovvaaaaaaaaaa wwweass-daaasee.........
Huawei Lin, Jun Woo Chung, Yingjie Lao, and Weijie Zhao. Machine unlearning in gradient
boosting decision trees. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, page 1374-1383, New York, NY, USA, 2023. Associa- tion for Computing Machinery. ISBN 9798400701030. doi: (0.1145/3580305.359944 URL.
https: waw.ooooogg/100 1145 /t/////58330055553
Gilles Louppe. Understanding Random Forests: From Theory to Practice. PhD thesis, arXiv, June 2015. URL
org abs / 1407. 7502. arXiv:1407.7502 [stat].
Ronak Mehta, Sourav Pal, Vikas Singh, and Sathya N. Ravi. Deep unlearning via randomized conditionally independent hessians. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10422-10431, June 2022.
Ari S. Morcos, David G.T. Barrett, Neil C. Rabinowitz, and Matthew Botvinick. On the importance of single directions for generalization. In International Conference on Learning Representations, 2018. URL https: /tcttps://opereviiii wwwpreveeveeeeeeeeeeee ew net wtt.:/iommmmrmmmmmmmmm wigpjcc...c....
12

---

Published as a conference paper at ICLR 2025
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014. ISSN 0167-9236. doi: https://doi.
htgp:/0..011fjdds2211....... article/pii/s00 (7921//311011111110111110 400066xx.
URL https: / /ttp///www//./////////////tt www.sciiiiics. www.:.ceeeeeiieeeec..cc wttps/....ooo/cceeeeeeeeee
Xinbao Qiao, Meng Zhang, Ming Tang, and Ermin Wei. Efficient online unlearning via hessian-frre recollection of individual data statistics. arXiv preprint arXiv:2404.01712, 2024.
Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. ISBN 1558602402.
C. Sakar and Yomi Kastro. Online Shoppers Purchasing Intention Dataset. UCI Machine Learning Repository, 2018. DOE: http:///...orrro..2444/3////////
Sebastian Schelter, Stefan Grafberger, and Ted Dunning. Hedgecut: Maintaining randomised trees for low-latency machine unlearning. In Proceedings of the 2021 International Conference on Management of Data, SIGMOD '21, page 1545-1557, New York, NY, USA, 2021. Associa- tion for Computing Machinery. ISBN 9781450383431. doi: 10.114453344801634452222 URL http://....................4.11. https: http::://doi.ooe org/10 10e111144411111 11155/3448811.34552533 3457239.
Sebastian Schelter, Mozhdeh Ariannezhad, and Maarten de Rijke. Forget me now: Fast and exact unlearning in neighborhood-bare recommendation. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Information Retrieval, SIGIR '23, page 201 1-2055, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394086. doi: (A1145//33961883551998) URL https: httt:s://dc..oogg /ttp://////i...r/11.1111111 3539618. 3591989.
David Slate. Letter Recognition. UCI Machine Learning Repository, 1991. URL https:///oi. org/ /1/./11..00 2 24432/242222
Beata Strack, Jonathan P. DeShazo, Chris Gennings, Juan L. Olmo, Sebastian Ventura, Krzysztof J. Cios, and John N. Clore. Impact of hbalc measurement hospital readmission rates: Analysis of 70,000 clinical database patient records. BioMed Research International, 2014(1):781670, 2014. doi:
11tp///00011115/17711111000 URL https: http:///nnnnnnneeeee
http:///wo.....taaooo/ooaaaaaaaa wiley..wweeyy.......... com/
Nan Sun, Ning Wang, Zhigang Wang, Jie Nie, Zhiqiang Wei, Peishun Liu, Xiaodong Wang, and Haipeng Qu. Lazy machine unlearning strategy for random forests. In Long Yuan, Shiyu Yang. Ruixuan Li, Evangelos Kanoulas, and Xiang Zhao, editors, Web Information Systems and Appli- cations, pages 383-399 Singapore, 2023. Springer Nature Singapore. ISBN 118-998-999-6229
Zhaomin Wu, Junhui Zhu, Qinbin Li, and Bingsheng He. Deltaboost: Gradient boosting decision trees with efficient machine unlearning. Proc. ACM Manag, Data, 1(2), June 2023, doi: 10. 144/ 3589313. URL https:tp///. /woi wtt.or/g.//...........
Heng-Ru Ru Zhang and Fan Min. Three-way recommender systems based on random forests. Knowledge-Booe Based Systems, 91:275-286, 2016. ISSN 0950-7051. doi: http:://do..rr/110..00 knosys.2015.06.019. URL https: www. sci sciencedi rect. com/ / scisncceeeece//ccc artticl///eee/aaeaaa Three-way Decisions and Granular Computing.
D21//09507051150022
Wentao Zhu, Zhining Zhang, and Yizhou Wang. Language models represent beliefs of self and others. arXiv preprint 24i: 2024.
13

---

Published as a conference paper at ICLR 2025
A
APPENDIX
A.1 PSEUDOCODE
Algorithm Training DYNERS and Unlearning Algorithm 2 Unlearning and Querying in Trees
Samples with OCC(4)
with LZY
1: procedure DISTRIBUTE(S, T.
1: procedure REMOVE(J, (x,y) ADD is similar DELETE(ROOT(()) (x,
2:
T x
2:
((l)) ..... ( + 00
3: end procedure
4: for (4) E do
4:
5: J1...k + randomly and independently
5: procedure REMOVE(u, (x,
sample & different integers from (T]
6:
implementation of DYNERS does not actually store S.. this line
S. Su\(x, v)
6:
for & ji...k do
7:
5 S(t U [(x
stands for updating all split statistics of node u
7: if LZY, = then return
8: end for
8: else if BESTSPLITCHANGED then
end for
return 50)) ...,,..777
1.ZY,, -[SLEAF(w) then 11: X.,; I w. then REMOVE(u, (x. u))
9:
11:
end procedure
12:
13: procedure TRAIN(S, T.
12:
13:
else
14:
15:
((1) S(T) DISTTRIBUTE(SST..
14:
REMOVE(U,, (x, (x)
16:
for 1 < 1... do
15:
end
17:
(t BUILDTREE(S"))
16: end
18:
$ U (Pt)
17: end procedure
end for
18:
procedure QUERY({,, (x,
20: return
20: QUERY(ROOTE) (x,9))
21: end procedure
22:
21: end procedure
23: procedure ADD(O, (x, y
22:
23: procedure QUERY(,, (x,
24: J1...; f- randomly independently sam-
ple different integers from [T]
if then
25:
SPLIT(u)
25:
for l <- ji... do
26:
ADD(IPL, (x.y)) 27: end for
26:
LZY,, + -0 LZY.; 1. LZY end if
27:
28:
28:
end procedure
29:
if (SLEAF()) then
29:
30: procedure REMOVE( (x, v))
30:
return S. end if
31:
31:
for 1...T do
32:
if (xx E 5t) then REMOVE((P; ())
32:
if x.: w then
QUERY (x.8))
33:
34:
end if end for end procedure
34:
else
35:
QUERY (ur, (x, 9))
35:
36:
end if
36:
37:
end procedure
A.2 PROOFS
Theorem 1. Sample addition and removal for the DYNFRS framework are exact.
Proof. We prove that the subsampling method occ(g) maintains the exactness of DYNFRS. Let random variable o,2 A [(x; M&i) 5(0) denotes whether (x,: Mi) occurs S(1), occ(g), each sample (x, y/) is distributed to [qT"] distinct trees, with the selection of these trees being inde- pendent of other samples (x,, E S for + Thus, o,,- is independent from oj,- for j # However, 0,,1, 0j,2, or are dependent on each other, constrainted by Vt E [T], Og, E {0,1),
ΣT 0,, [qП and say they follow a joint distribution (TT,q). Now, let
..... (*( denotes the training sets for each tree generated by applying occ(g)
the modified training set S², and let o,, - [(x yn) 5T00.. Then, when removing sample
14

---

Published as a conference paper at ICLR 2025
(x,, Mi) (i.e., S' = (xx,,, U.)), we have (0,.1....,,99.))) B(T,q) q) and (d (dA,....,,0 dY.T) B(T, g) for i o J. and oz = (because (x,, Vi) is removed) and of = O. Notably, B(T, q) depends on
T and y only, but not on training samples S. This shows that simply setting or,- = 0 ensures that oCC(g) with sample removed maintains the same distribution as applying ocC(q) the modified training set.
Similarily, when adding (x,; M/) (i.e., S' (U,,,,,)) (o,.,....,... and (d),))..., .g.T) follow the same distribution ((T;,) q) for + i. While (0H.1..... 0g.T) ) is generated from ( q) for addi- tion, it is equivalent to (o),1).... ) for following the same distribution. Therefore, OCC(g) with
sample added maintains the same distribution as applying OcC(g) on the modified training set.
Next, we prove that the addition and removal operations are exact within specific DYNFRS tree. When no change in range of attribute a (Jmnin(x...) I (x,, U,) E S.). max (xi,a (4) E {) occurs, the candidate splits are sampled from the same uniform distribution making DYNFRS and the retraining method are identical in distribution node's split candidates. However, when change in range occurs, DYNERS resamples all candidate splits and makes them stay in the same uniform distribution as those in the retraining method. Consequently, DYNFRS adjusts itself to remain in the same distribution with the retraining method. Thus, sample addition and removal in DYNERS are exact.
For a certain Extremely Randomized Tree node u, and a specific attribute a, the time complexity of finding the best split of attribute is O([Su] log s). assuming that [Sul >> s.
Lemma 1.
Proof. Conventionally, for each tree node u and an attribute a, we uniformly samples thresholds
Wa.1... from fm.n (x,, v,) E S,,,, max(x;,a (x,, E S. Then, we try to split S, with each threshold and look for split statistics that are: (1) the number of samples in the left or right child (i.e., [Sug] and (S,, D), and (2) the number of positive samples in left or right child ((S,, and
[Sa,.+D. D. which are the requirements for calculating the empirical criterion scores.
One approach, as used by prior works, first sort all samples S, by x., in ascending order, and then sort thresholds 1o.1 in ascending order. These sortings has time complexity of O(SS,, log (S,l) and ((s log s), respectively. After that, a similar technique used in the merge sort algorithm is used to find the desired split statistics in O(SSal + s).
To get rid of the costly sorting on Su, we sort Wa.1... O(s log s) and then iterate through all samples and calculate the changes each sample brings to candidates" split statistics. For convenience, let
by - [ (xxx U/) (x,, V.) E Su A Xi, S Wo,k
C* - ((xx,,)) (x,, E S. A X;,a S Wo,k A = +}|,
which are crucial split statistics for calculating the empirical criterion score. We start with setting bi... and cı... all zeros. Then, for sample (x,, v.) Su, it will cause increment in by.... for some s' satisfying Xr,a I Wy and Xi,a > W. -1- Given that Wa, are sorted, all k, (s' S k < s) satisfy Xi,a S Wa,k, while Xi,a Wa,k for all < k < 8'. s' can be easily found by binary search in Ollg 8), then adding 1 to by, b.. b. is the only thing left. Use a loop for range addition is clearly Oss), but insteading of finding by.... we keep track of dj.... where de - by - 6 So increment b..... can be replace by de + d, + 1, which (1). When all samples are processed, we construct bi. from di...s, where prefix sums by + - + d, help solve it in O(s).
v1) E S. we need find s' in O(log)) s) (Algorithm 3: line 10). and perform increment in d' in (11) (Algorithm 3: line 11), which results in time complexity of O([S.. log s) line 9-14). Meanwhile, the prefix sum executed after samples are processed (Algorithm 3: line 15-18), and its execution time is bounded by Oss). Luckily, ci... can be calculated in a similar manner, and with both bl...e and Ci... ready, we can obtain the empirical criterion score for each candidate split (Algorithm 3: line 21-28), and this has time complexity of (s) assuming calculating criterion scores to be (1).
For every sample (x)
in this part (Aigorithm
Since [Sul >> s, the term O[SSa] log s) dominates in time complexity, with the binary search (Al- gorithm 3: line 10) being the threshold. It is noteworthy that adopting exponential search to find s' can result in expected Olog log s) time complexity since Wa.l... are uniformly distributed.
15

---

Published as a conference paper at ICLR 2025
However, binary search outperforms exponential search in practice, conclude with time complexity of [[ log s) for finding the best split of attribute a node u when |Sul >> s.
Algorithm 3 Find the best split for attribute
1: procedure FNNDATTRIBUTBBSTSSSSUN
H f (x.,. (x,, M.) e S.). max(x.,a (x,, Ub) S.H
3: Wu,1...a -- sample s Li.d. values from H
4: Wa.1.... t- SORT 1...)
sort Wa,1 in ascending order. b create 1-D array of size
5: bi-..s f (0.-...0
6:
Ci--s - {0,-..,0
create 1-D array of size
n f [Su]
8:
+ 0
9:
for
(x) E S., do f- LOWERBOUUD(WNI---ee
10:
find the largest position & s.t. w Xi,0
b, +- by +
12:
C₁' + Ce' + yi
13:
n4 + n.4 +
14:
end for
15:
for k 2. do
find prefix sum
16:
by - b4 + b
17:
+ a + ck-1
18:
end for
19:
I' 20
20:
waa f-0
21:
for
k
+ 1...8 do
22:
Ta + I(b,, cb2 bb Cb)
23:
> I([S... [S 1 [Su,.t] returns the empirical critierion score for split (a, Wa.k) in O(1)
using either Gini index Ig (this work) Shannon's 's entropy Ig-
24:
I
then I < Is
25:
26:
W. + Wa.k
27:
end end for
28:
29:
return (a, wX)
30:
end procedure
Given < 1, the proportion of trees each sample is assigned to, T. the number of trees in the forest, dmax= the maximum depth of each tree, p. the number of candidate attributes, 8, the number of candidate splits for each attribute (usually I 30), and n = SS, size of the training set, we now prove the following:
Theorem 2. Training DYNFRS yields a time complexity of O log s).
Proof. For certain tree and a specific node u, we find the best split among randomly selected attributes 01--pp. and we call
0;, 8) (Algorithm 3) times for each i [p]. From Lemma 1, finding the best split for the node u has time complexity of Op)SSa log s). Then, summing [S.] over all tree nodes on that tree, have Σ., S. S dmaxqm, since the root of the tree contains about [qT] R3 gn samples, and each layer has at most the same amount of samples as the root (layer 0). Therefore, the time complexity for training
DYNFRS tree can be bounded by (ddmax: log s). Since there are T independent trees in the forest, the time complexity for training DYNFRS forest is OggTdmaxPPn s).
Theorem 3. Modification (sample addition or removal) in DYNFRS yields a time complexity of O dmssps) no attribute range changes occurs while OlgIdmaxDS Caag log s) otherwise (where e denotes the number of attributes affected, and nu denotes the sum of sample size among all affected nodes met by this modification request).
16

---

Published as a conference paper at ICLR 2025
Proof. When attribute range change occurs each tree, the modification request traverses path from the root to a leaf with at most dmax nodes. For each node, we need to recalculate all the empirical criterion scores for all candidate splits Opps). Since OCC(q) guarantees that only [q]" trees are affected by the modification requests, at most gTdmax nodes need the recalculation. So, the time complexity for modification request yields Q(qTdmaxxPs)
When an attribute range occurs on u, it is necessary to call FINDATTRRIBBBEEESSSSSST....... a, s) for u and the affected attribute a. Given that the affected nodes' sample sizes sum up to Raffs and for each affected node, we need to resample at most e S attributes, and then Lemma entails that the time complexity for completing all resampling is an additional (cn log
Theorem 4. Query in DYNFRS yields time complexity of ((dd)))) if no lazy tag is met, while (mdaxx + phay log s) otherwise (where nkyy denotes the sum of sample size among all nodes with lazy tag and met by this query).
Proof. On each tree, the query starts with the root and ends at leaf node, traversing a tree path with at most dmax nodes, and the query on DYNFRS aggregates the results of all T trees, therefore querying without bumping into a lazy tag yields time complexity of O(Tdmax).
However, if the query reaches on a tagged node u, we need to perform a split on it, and by the proof of Theorem 2 and Lemma 1, finding the best split of node calls function FINDATTRBBUBBESSSPPUTY.... 8) p times and results in a time complexity of Opp]S.] log s). As Tay denotes the sum of sample sizes of all nodes with lazy tags met by the query, handling these lazy tags requires an additional time complexity Oppnay s).s).
A.3 IMPLEMENTATION
All of the experiments are conducted on a machine with AMD EPYC 9754 128-core CPU and 512 GB RAM in Linux environment (Ubuntu 22.04.4 LTSS, and all codes of DYNFRS are written in C++ and compiled with the g++ 1 11.40 compiler and the -03 optimization flag enabled. To guarantee fair comparison, all tests are run on a single thread and are repeated 5 times with the mean and standard deviation reported.
DYNFRS is tuned using 5-fold cross-validation for each dataset, and the following hyperparameters are tuned using grid search: Number of trees in the forest 7 E {100, 150, 250), maximum depth of each tree dmax {10, 15, 20, 25, 30, 40), and the number of sampled splits s {5, 15, 20, 30, 40].
A.4 BASELINES
HedgeCut and OnlineBoosting can not process real continuous input. Thus, all numerical attributes are discretized into 16 bins, as suggested their works (Schelter et al., 2021; Lin al., 2023). Both of them are not capable of processing samples with sparse attributes, one-hot encoding is disabled for them. Additionally, it is impossible to train Hedgecut on datasets Synthetic and Higgs in our setting due to its implementation issue, its complexity degenerates to Opn?) sometimes and consumes more than 256 GB RAM during training.
A.5 DATASETS
Purchase (Sakar and Kastro, 2018; Dua and Graff, 2019) is primarily used predict online shop- ping intentions, i.e., users' determination to complete transaction. The dataset was col- lected from online bookstore built on osCommerce platform.
Vaccine (Bull et al., 2016; DrivenData, 2019) comes from data-mining competition in Driven- Data. It contains 26,707 survey responses, which were collected between October 2009 and June 2010. The survey asked 36 behavioral and personal questions. We aim to deter- mine whether person received seasonal flu vaccine.
17

---

Published as conference paper at ICLR 2025
Adult (Becker and Kohavi, 1996; Dua and Graff, 2019) is extracted from the 1994 Census database by Barry Becker, and is used for predicting whether someone's ' income level is more than 50,000 dollars per year not.
Bank (Moro et al., 2014; Dua and Graff, 2019) is related to direct marketing campaigns of Por- tuguese banking institution dated from May 2008 to November 2010. The goal predict if the client will subscribe to term deposit based on phone surveys.
Heart (Kaggle, 2018) is provided by Ulianova, and contains 70,000 patient records about cardio- vascular diseases, with the label denoting the presence of heart disease.
Diabetes
(Strack et al., 2014; Dua and Graff, 2019) encompasses a decade (1999-2008) of clinical diabetes records from 130 hospitals across the U.S., covering laboratory results, medica- tions, and hospital stays. The goal is to predict whether patient will be readmitted within 30 days of discharge.
Synthetic (Kaggle, 2016) focuses the patient's appointment information, such date, number SMS sent, and alcoholism, aiming to predict whether the patient will show up after making an appointment.
Higgs (Baldi et al., 2014; Dua and Graff, 2019) consists of 1.1 x 10 signals characterized by 22 kinematic properties measured by detectors in particle accelcrator and 7 derived attributes. The goal is to distinguish between background signal and Higgs boson signal.
A.6 RESULTS
In this section, Table 3 presents the training time for each model, with OnlineBoosting being the fastest in most datasets while DYNFRS ranks first among Random Forest based methods. Table 4, 5, 6, and 7 despicts the runtime for model simultancously unlearning 1, 10, 100 instances or 0.1% and 1% of all samples, where DYNERS consistently outperforms all others in all settings and all datasets.
Table 3: Training time (4) of each model, measured in seconds (s), and the standard deviation is given with the same unit in a smaller font. "y" means the model is unable to train on that dataset.
Online Boosting
DYNFRS (q = 0.1)
DYNFRS
Datasets
DaRE
HedgeCut
0.2)
Purchase
3.10=0.0
1.05
0.27
0.38
0.72:1..0
Vaccine
4.78_0.D
431
1.05=a.0
1.1220.0
2.27=0.0
Adult
5.02-o.1
11.820.
0.77
0.61
1.1540.0
Bank
8.26_0.2
8.4420.3
0.92=0.0
1.1520..
2.37-20.0
Heart
12.1=0.2
3.51
1.02
1.04+0.0
1,96+0.0
Diabetes
123+1..0
16243.3
3,51
8,6740.0
18.2+0.0
NoShow
65.4=u.4
28.1+0.3
1.68=0.0
3.08+0.0
6.10+a.0
Synthetic
133446.3
40.7=0.9
66.310.2
128
Higgs
10793148
460=18
548+1.2
1120+1.
Table 4: Runtime (() for each model to unlearn I sample measured in milliseconds (ms), and the standard deviation is given with the same unit in smaller font. "f" means the model is unable to train on that dataset or unlearning takes too long.
Online Boosting
Datasets
DaRE
HedgeCut
DYnFRS
Purchase
35.0
1245
83.419.0
0.40
Vaccine
16,0+15
33445+14372
222
1.40=0.o
Adult
10.6#5.0
3596:+2306
249
1.10
Bank
33.2+17
2760=371
227+7..4
2.40=3.7
Heart
16.8110
972.a154
4111:3
0.50 2.2
Diabetes
293
27654110968
753
7.30
NoShow
3301176
1243
570
0.30
Synthetic
2265-4352
52254241
2.50
Higgs
174+135
73832224155
1.60
18

---

Published as a conference paper at ICLR 2025
Table 5: Runtime (L) for each model to unlearn 10 samples measured in milliseconds (ms), and the standard deviation is given with the same unit in smaller font. "/" means the model is unable to train on that dataset or unlearning takes too long.
Online Boosting
Datasets
DaRE
HedgeCut
DYNFRS
Purchase
295
10973
183
12.3
Vaccine
285
222333++6475
418
9.20=2.8
Adult
148=79
51831 22796
389
4.80
Bank
320+108
18091 4-1244
423 4:47
7.6:22.7
Heart
162++46
5524#335
1:38
6.80 +:2.8
Diabetes
2773
211640#77902
1096#1172
85,5
NoShow
2217=723
17235
712=74
18.2::123
Synthetic
92279:142634
6015:3301
77.3134
Higgs
20119:31807
104063#1258
32. 1:8.
Table 6: Runtime (4) for each model to unlearn 100 samples measured in milliseconds (ms), and the standard deviation is given with the same unit in smaller font. "f" means the model is unable to train on that dataset or unlearning takes too long.
Online Boosting
Datasets
DaRE
HedgeCut
DYNFRS
Purchase
3591
83649
275
70.4+11
Vaceine
2385 11408
1703355
792.115.0
82,6111
Adult
954
219392.134600
632.124
32.2:4.0
Bank
35461:302
195014 158544
740:20
78.8
Heart
1502
3380626385
986475
59.3+
Diahetes
23833=10338
2071
578
NoShow
23856
57021
1120.192
117=10
Synthetic
1073356 420053
7609#171
889 4:287
Higgs
165122+119092
145386+5677
642
Table 7: Left: runtime (L) for unlearning 0.1% of the training set between models. Right: runtime
(4) for unlearning 1% of the training set between models. Each cell contains the elapsed time in seconds (s), and the standard deviation is given with the same unit in smaller font. "/" means the model is unable to train on that dataset unlearning takes long.
Online Boosting
Online Boosting
Datasets
DaRE
HedgeCut
DYNFRS
DaRE
HedgeCut
DyNFRS
Purchase
0.35
11.25
0.17
10.0
2.3
76.023.0
0.28
0.07=0.0
Vaccine
0.47
404.73+
0.61 #0.1
0.02
5.01 +1.0
4054+
0.98+a.0
0.13
Adult
0.44
18.1
0.49
0.01 +o.0
3.39
516+23
0.80
=.09
Bank
1.15+4..
47.3+
0.61
0.02+e.0
14.7+2.3
418+25
0.96+0.u
0.16#0.0
Heart
0.70=0.2
20.0=1.7
0.85
0.03
8.43
145
1.23
0.20
Diabetes
23.812.7
694_a1
2.12:0.1
0.57.10.1
258
3.51
2.50
NoShow
18.8 18.8+2.7
57.0=6.3
1.1020.1
0.10
268
1.90
0.56
Synthetic
10790
13.1
5.68
44.2:1.4
27.4
Higgs
188+7.1
39,24
456+4.7
201
A.7 SPACE COMPLEXITY AND MEMORY CONSUMPTION
The space complexity of DYNFRS is O(gTn + Teps) where the number of trees the forest, is the number of samples in the training sets, 9 is the factor used in OCC, is the average number of nodes each tree, p is the number of attributes considered by each node, and s is the number of candidate splits. Since store training samples each leaf, and each tree occupies gn samples
19

---

Published as a conference paper at ICLR 2025
average, then the leaf statistics sums up O(qIn). As mentioned in section 4.3, store extra (ps)) split statistics on each node so that these split statistics contribute up to ((Teps) space.
We compare the maximum resident space of DYNFRS and DaRE for building the training set. We found that DaRE, which has a space complexity of (I + Tups), has larger memory consumption than DYNFRS in all datasets. We use set size.
imm in Linux evaluate the maximum resident
Table 8: The maximum resident set size (L) of each model measured megabytes with standard deviation shown in smaller font.
Datasets
DaRE
DYNFRS
Purchase
1.8.421.4
83.221.66
Vaccine
782.2+1.6
492.8
Adult
460.622.2
232.0
Bank
801.0=1.8
300.0
Heart
254.4++
252.2++1.6
Diabetes
7148+
2512++7.6
NoShow
3792+119
761.6+2.0
Synthetic
8526.165
5827.17.8
Higgs
60528:178
58263:52
A.8 MULTI-CLASS CLASSIFICATION
DYNFRS is capable of handling multi-class classification tasks since OCC(g) and LZY do not af- fect the functionality of the forest. We tested DYNFRS's prediction performance and unlearning boost on 3 datasets Optical (Hyafil and Rivest, 1976). Pen (Alpaydin and Alimoglu, 1996), and Letter (Slate, 1991). Unfortunately, existing random forest unlearning methods (DaRE and Hedge- Cut) have implementation for multi-class classification, Classifier implementation (we call Vanilla in the following) in scikit-learn as our baseline.
only include the Random Forest
Table 9: Datasets specifications. (# train: number of training samples; test: number of testing samples; # attr: number of attributes; class: number of label classes.)
Datasets
#train
test
attr
#class
Optical
3823
1797
64
10
Pen
7494
3498
10
Letter
15000
5000
16
26
Table 10: Each model's predictive performance, training time, and unlearning boost with standard deviation shown in smaller font.
Accuracy (1)
Train Time (l.ms)
Unleam Boost (1)
Datascts
Vanilla
DYNFRS
Vanilla
DYNFRS
Vanilla
DYNFRS
Optical
96944..uu
.970+
585.4+1.9
445.4
1
292.5++1.1
Pen
.002
.696
996.2+1.7
813.2::.00
120
603.0:144.8
Letter
9603...02
.92241.001
166627.6
1530:220
110
1006.154.2
Results show that DYNFRS outperforms the vanilla Random Forest in terms of predictive perfor- mance and training time for all datasets. Additionally, DYNFRS still shows splendid unlearning efficiency on these datasets. In all datasets, DYNFRS outperforms Vanilla by 2-3 order of magni- tudes in terms of unlearning efficiency. Also notice that DYNFRS is poorly optimized for multi-class classification tasks.
In the multi-class classification setting, suggest picking q 0.5 for oCC(g), because the rise in class number leads to the drop of sample size to each class (roughly n/c, where n is the number of training samples and is the number of classes) and rising q enable each tree is accessible more samples belonging to a specific class and lead to better predictive performance eventually. For all datasets, set the hyperparameters of DYNFRS T 100, dmax 20, and 1.
20

---

Published as a conference paper at ICLR 2025
A.9 REGRESSION
Regression tasks are not implemented and evaluated by any of the existing tree-based unlearning methods. Since there is no such baseline, we compare DYNFRS's predictive performance (via mean squared error) and unlearning efficiency (via unlearning boost) against the naive retraining method. We used a large and popular dataset Bike (Fanaee-T, 2013) for the regression task.
Table 1I: Datasets specifications. (# train: number of training samples; # test: number testing samples; # attr: number of attributes.)
Datasets
train
# tost
#attr
Bike
13903
3476
16
Table 12: Each model's predictive performance, training time, and unlearning boost with standard deviation are shown in a smaller font.
MSE (L)
Train Time (4.ms)
Unlearn Boost (t)
Datasets
Vanilla
DYNERS
Vanilla
DYNFRS
Vanilla
DYNFRS
Bike
3.004
3.011
6796
3412
140
2368
Results show that DYNERS outperforms the vanilla Random Forest in terms of predictive perfor- mance and training time. Note that the implementation of DYNFRS regressor is rough and poorly optimized due to short time slots. However, DYNFRS still shows outstanding unlearning efficiency on regression task, DYNFRS achieves an averaged 2368 unlearning boost in dataset Bike.
In the regression setting, we suggest picking g = 0.5 for lower mean squared error. In the experi- ment, set the hyperparameters of DYNERS T 100, dmax 15, and 5.
A. ONLINE MIXED DATA STREAM
Table 13: DYNFRS's latency (L) of sample addition/removal and querying scenarios measured in microseconds (js)). # #add/del/qry: the number of sample additon/removallqueryngg requests; add/del/qry lat.: the latency of sample additon/removalqqerring Each cell contains the averaged latency with its minimum and maximum values listed smaller font.
No.
# add
# del
# qry
add lat. (J. jus)
del lat. (4, pS)
qry lat. (J. JuS)
5 10
5- 10
106
406.2 |150, 450684
437.6 [134, 394801]
3680 1885030]
10
5- 10
105
122.7 [30, 168984]
120.2 [25, 146300]
1218 [23, 1026964)
3
5 10
5- 50
106
140.0 (30, 81661]
139.2 [32, 101 4214
299.5 [21, 861151]
5-10"
10a
145.5 (44, 55954)
140.5 (38, 29810)
72.3 [19, 212915]
To simulate a large-scale database, we use the Higgs dataset, the largest in our study. We train DYNFRS on 88, 000, 000 samples and feed it with mixed data streams with different proportions of modification requests. Scenario 1 is the vanilla single-thread setting, while scenarios 2, 3, and employ threads using OpenMP. DYNFRS achieves an averaged latency of less than 0. 0.15 ms for modification requests (Table 13 column # add and del) and significantly outperforms DaRE, which requires 180 ms to unlearn a single instance on average. Query latency drops from 1.2 ms to 0.07 the number of modification requests declines, fewer lazy tags introduced to trees.
These results are striking: while it takes over an hour to train a vanilla Random Forest on Higgs, DYNERS maintains exceptionally low latency that is measured in μss in the sinleethreedee setting. This makes DYNFRS highly suited for real-world scenarios, especially when querying con- stitutes large proportion of requests (Table 13 Scenario 4).
21

---

Published as a conference paper at ICLR 2025
A.11 EFFECTS ON NUMBER CANDIDATES
We assessed the predictive performance of DYNFRS with differnet candidate number 8. We tested DYNFRS(G 0.1) with {1,5, 10, 20, 30, 50} and report the predictive performance all the binary classification datasets (same settings as in Section 5.2). The results are summarized in the table below:
Table 14: The predictive performance (1) of DYNERS( = 0.1) with E {1,5, 10, 20, 30, 50).
Datasets
== 1
5
== 10
8 20
30
50
Purchase
.92421.001
.93132.00 .000
.9323 000
.9329_001 .00
.9328 001
.9330.001 .001
Vaccine
.7911 1 002
.7910=.00 .000
.7908 .011
.7910=000 002
.791 1 000
.7912::.00
Adult
185581.001
88610..0
.8624..000 .011
.8635
.8635
.8640=.00
Bank
90323=.000
.9399=
.9409 000
.9414=.00
.9417.000
.9417=0001
Heart
.7365#.001
.7359=.001
.7357=.001
.7359=.02
.7357=0008 .000
.7351=000
Diahetes
.64292.001
.6453=2.011
(6451=000
.6446=.00
.64422.001 .01
.6443=.00
NoShow
17288..000
.7332#.000
.7328 .000
.7332
.7323 0001
.7328
Synthetic
.93524.000
.9415
.9421
.9422
.9424
.9423
Higgs
.7277+.000
.7409 0000
.7423 4: .000
.7431
.000
.7431 + .000
.7431 4.00
From the result, we find that the performance peaks around s 20 in most datasets, and the result of 30 and 50 has no significant difference. However, in datasets Heart, Diabetes, and NoShow, a smaller has an even higher predictive performance, suggesting that considering more candidates might not always be the best choice. These results indicate that the optimal is dataset-specific and can be tuned for improved predictive performance in DYNFRS.
A.12 HYPERPARAMETERS
All hyperparameters of DYNERS listed in Table 15. Specially, the minimum split size of each node to be 10 for all datasets.
Table 15: Hyperparameters used by DYNFRS with both g = 0.1 and 0.2 setting.
Datasets
dmax
$
Purchase
30
Vaccine
250
20
5
Adult
100
20
30
Bank
250
25
30
Heart
150
Diabctes
250
5
NoShow
250
20
5
Synthetic
150
40
30
Higgs
100
20
22


Reviews:
[{"review_id": "NRu9WogyP6", "reviewer": "Reviewer_JhHN", "summary": "This paper presents a novel unlearning approach for random forests. The authors employ a variant of bootstrapping, named OCC(q), to control the number of trees that each sample is used to train. This bootstrapping technique significantly decreases the number of trees that require unlearning, addressing a gap in existing random forest unlearning methods. Additionally, the authors propose lazy tagging, LZY, to defer re-training of subtrees until needed, enabling batched deletion and speeding up addition and deletion requests. The authors theoretically prove the exactness of their algorithm and analyze its time complexity. They conclude with comprehensive experiments demonstrating their method's superior performance compared to existing approaches.", "questions": "* Can the authors address the points raised in the weakness section above?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The method is simple yet effective, yielding an exact unlearning method for random forests.\n* The approach reduces required re-training from the source by limiting the number of trees each data point influences.\n* The method defers subtree re-computation until queries require that portion, making it suitable for online settings.\n* Theoretical proofs demonstrate the algorithm's exactness and time complexity.\n* Comprehensive experiments show superior performance compared to baselines, which suffer from numerical value binning.\n* The algorithm demonstrates significantly faster performance than baselines.", "weaknesses": "* Standard bootstrapping should be included as a baseline for performance comparison. The method involves two key changes: fixing the number of trees each sample is used in and using extremely randomized trees. Including separate comparisons would provide insights towards the impact of each modification.\n* Space complexity analysis is missing from the paper. While the authors mention what additional information is stored for each node in Section 4.3, an explicit discussion would be valuable.\n* The evaluation lacks testing on regression datasets.\n* Line 204: \\in -> \\subset", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9GJXHigouK", "reviewer": "Reviewer_7Tpx", "summary": "This paper focuses on the unlearning of random forests and proposes the DYNFRS framework. DYNFRS is based on extremely randomized trees and includes subsampling and lazy tagging to improve the efficiency of unlearning procedures. This paper also proves the efficiency advantages of DYNFRS in both theoretical and experimental results.", "questions": "1.  What are the performance comparisons on the sequential unlearning, batch unlearning, and mixed online stream unlearning settings? The current draft only provides efficiency comparisons.\n\n2. How the proposed method handles the changes of optimal split is not clear. This is the key point about the soundness of the proposed method.\n \n3. In the experiment, what are the detailed settings for the unlearning request in each dataset? \n\n4. In the baselines, this paper chooses four methods corresponding to different tree construction approaches. Thus, does it mean such baselines also contain different initialized well-trained models? In addition, does the random forest stand for the retrained model?\n \n5. In the experiment results in Table 2, why does higher prediction performance stand for better unlearning performance? In addition, in the unlearning of a tree-based method, which has more transparent structures, is it a better way to prove the success of unlearning by showing that the unlearned trees have the same structures as the retrained trees?\n\nI am not familiar with the extremely randomized trees, so I might change my assessment based on other reviewers' comments.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The motivation and the contributions of this paper are clearly shown.\n2. This paper provides both theoretical and experimental results to show the huge efficiency improvements compared with the retrained model.", "weaknesses": "1. This paper targets the unlearning in random forests. However, the proposed method relies on extremely randomized trees instead of the general decision trees, which limits the applicability.\n\n2.  The technical part, as well as the pseudo-code in the appendix, are hard to follow. An overall pipeline or workflow can be better used to understand the proposed method.\n\n3. The experiment, especially the performance comparisons, lacks many essential results, and it cannot prove the effectiveness of the proposed methods. Please refer to questions 3, 4, and 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hvVrGJRbpZ", "reviewer": "Reviewer_DnwV", "summary": "The paper introduces  DYNFRS, a framework that enables efficient machine unlearning in Random Forest models. The objective is to propose a framework that supports the unlearning of a noticeable amount of data, i.e., above 0.1% of the original training set, without harming the performance of the model. Moreover, the framework should support real-world requests, such as adding data to the training set and querying the model. This is achieved through the three components of the framework: (i) the One-Class Constraint subsampling (OCC) that restricts each data sample to appear only in a subset of trees within the forest, reducing the influence of each sample on the model and thereby simplifying the unlearning process; (ii) the Lazy Tag Strategy (LZY) that marks only the nodes affected by data deletion or addition, allowing the algorithm to defer modifications until a relevant query necessitates them; (iii) the adoption of Extremely Randomized Trees (ERTs) as base learners in the forest that enable resilience to train data variations due to their inherent randomness in split selection. The time complexity of the data deletion, data addition, and querying of the model is formally proven, as well as the exactness of the unlearning procedure.\n\nOn nine binary classification datasets, DYNFRS is evaluated against other state-of-the-art machine unlearning approaches (DaRE, HedgeCut, and OnlineBoosting). The experimental results show that forests trained with DYNFRS present predictive performance that is at least equal to the ones of the other frameworks. Moreover, DYNFRS outperforms the other methods in sequential and batch unlearning tasks, demonstrating speedups up to 10^6x over traditional retraining and low growth of the unlearning runtime with a high number of requests with respect to the competitors. DYNFRS also supports requests in dynamic environments where data deletion, addition, and querying requests interleave, achieving a very low latency for modifications and making it practical for real-world applications.", "questions": "- Do the models trained by each framework in the experimental evaluation have the same hyperparameter values, e.g., number of trees and maximum depth?\n- How much memory does DYNFRS consume during training compared to the baselines? How much memory does DYNFRS consume during a stream of mixed requests?\n- The tables and figures in the experimental evaluation sections show error bars. However, the description of the experimental methodology makes how these error bars are computed unclear. How many times each experiment is repeated? What differs in each repetition of the experiments?  \n- Why are multiclass datasets not used in the experimental evaluation? Does DYNFRS also support multiclass classification tasks? If yes, how do models trained with DYNFRS perform in terms of accuracy, unlearning efficiency, and latency on a stream of mixed requests?\n- In Section 4.1, the speedup is computed as $N_{occ}/N_{nai}$. Instead, should it be computed as $N_{nai}/N_{occ}$? Moreover, is the speedup achieved by OCC over the naive method $1/q^2$ or  $1/q$? In Section 4.1, both the values are used.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This is a good paper that presents a significant contribution to the unlearning field. \n\nThe novelty of this work stands in the proposed framework. Even though DYNFRS includes some techniques already presented in DaRE, in particular the random splits and the storage of the updated statistics of the nodes involved in the unlearning phase, the combination of these two techniques with constrained subsampling (OCC) and the tagging strategy (LZY) is novel and it has never been explored in the literature. Moreover, the framework supports not only data unlearning but also data addition and can handle a mix of requests in sequence, capabilities that are not supported by the considered state-of-the-art baselines.\n\nThe significance of the framework is highlighted by its performance with respect to the baselines. In sequential unlearning and batch unlearning, DYNFRS presents a speedup of up to 10^5 times with respect to the baselines. Fast learning and unlearning make the framework directly usable in real-world applications. However, more details about the experimental methodology need to be assessed to understand if the comparison with the baselines is completely fair (see the Weaknesses Section).\n\nFinally, the presentation of the algorithms is clear, but the presentation throughout the paper can be improved in general (see the Weaknesses Section). It is appreciable that the authors have formally proven the complexity of the data unlearning, data addition and model querying procedures.", "weaknesses": "Even though the proposal of the paper is good, the paper presents some weaknesses and unclear points that the authors should address.\n\n**Noteworthy weaknesses**\n\nThe first point regards the presentation of the experimental methodology, which is not deepened and not clear. In Section 5.1.1., it is written that `For all baseline models, we adhere to the instructions provided in the original papers and use the same parameter settings.`. Thus, it is not guaranteed that the baselines are using the same hyperparameter values of the forests trained by DYNFRS, like the number of trees and maximum depth, since, for example, DaRE expects to tune these parameter values. While this is acceptable to compare the accuracy of the best performing models trained by different frameworks, the models should all have the same hyperparameter values when comparing the training and unlearning time cost since the complexity of training and unlearning depends on the number of trees and maximum depth of the models. I invite the authors to clarify this point and provide experimental results related to a fairer comparison. Moreover, it is unclear how often the experiments are repeated to obtain the error bars and standard deviations shown in tables and figures and what is different among each repetition.\n\nSecond, it would be appreciated if the authors could provide the space complexity of a DYNFRS forest, as done in the DaRE paper for the DaRE forests. Indeed, it is not clear if the gain in time efficiency obtained by DYNFRS comes at the cost of a higher memory consumption. The suggested analysis would allow the authors to clarify this point. Moreover, an experimental comparison of the memory consumption of DYNFRS during the training phase with the baselines and an example of the memory consumption of a DYNFRS forest during a mix of requests of different types may highlight the practicality of the proposed framework.\n\nFinally, the framework is tested only on binary classification tasks. It is not clear from the paper if the framework supports also multiclass classification tasks. The authors should provide clarifications about this point and, if the framework supports multiclass classification tasks, replicate the presented experiments including some multiclass datasets. If the framework does not support multiclass classification tasks, it is not a big limitation, but the authors should clearly state the reason of this limitation.\n\n**Minor points**\n\nThe paper contains a lot of typos, especially in the notation of the Section 3. I invite the authors to fix them. Examples of typos are:\n- page 3, line 132, $S, <x, y>)$: $<x, y>$ is missing curly brackets.\n- page 3, line 134: $A(S \\cup <x, y>)$: $<x, y>$ is missing curly brackets.\n- In Section 3.2, $(a^*_u, w^*_u)$ and $p$ are not properly introduced.\n- page 5, line 4: $D^n$ has never been defined.\n- Page 5, line 142: Is the indicator function missing?\n- In Section 4.2., the sentence `Unlike OCC(q)’s reducing work across trees and believing in ensemble, LZY relies on tree structures,\ndismantling requests into smaller parts and digesting them through time.` does not make any sense and should be rephrased.\n\n**Update after authors' response**\nThe authors have clarified the weaknesses listed above and the questions below in a satisfactory way, so I have increased my score. I leave the weaknesses written above to keep a trace of the discussion.\n\n**Arguments for the score**\n\nThe proposal is novel and significant. Even though the proposed framework combines existing ideas, this combination gives rise to a new solution that is more efficient and effective than state-of-the-art solutions. Moreover, the framework supports operations not supported by other unlearning frameworks in the literature and presents a notable speedup over recent baselines. The experimental results are convincing about the improved efficiency and accuracy of the trained forests with respect to state-of-the-art forests. Thus, I recommend the acceptance of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oZoeMgo6Uv", "reviewer": "Reviewer_THi8", "summary": "This paper addresses the unlearning problem in Random Forests for privacy concerns, focusing on efficient data point removal or addition. The DYNFRS framework is proposed for efficient machine unlearning in Random Forests while maintaining predictive accuracy.", "questions": "See my Weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper presents a comprehensive set of experiments, encompassing various types of unlearning scenarios.\n\n2. The proposed method, DYNFRS, demonstrates significant efficiency improvements compared to existing baselines.", "weaknesses": "1. My primary concern is the limited novelty of this paper. DYNFRS appears to be an assemblage of components with minor modifications. The framework consists of three main components: OCC which performs subsampling on trees instead of training samples, essentially randomly selecting $k$ trees; LZY which utilizes the lazy tag concept and  replaces subtree retraining with reconstructing the tree path that connects the modified node u and a leaf; ERT which  is an existing method, with modifications like  only s candidates on one attribute instead of all possible splits. DYNFRS, therefore, seems to be a combination of existing techniques with relatively minor alterations. While the integration of these components may offer some benefits, it is questionable whether the contribution of these improvements meets the standard expected at ICLR.\n\n2. The clarity of the paper's writing could be further improved:\n\n- It would be better if some redundant theorems and formulas could be avoided. For instance:\n\n  (a) Theorem 1's conclusion is trivial, especially given the assumptions of sample independence and the splitting characteristics of tree models.\n\n    (b) Lemma 1 is also trivial, since the major difference in the complexity stems from the introduction of $s$ candidates compared to classic methods.\n\n  If the authors could more directly and concisely highlight these key points instead of using extensive formulas and theorems, it may be further enhance the clarity of the paper.\n\n- Section 4.2 requires a necessary introduction to the lazy tag, particularly since lazy tagging is a classic technique in segment tree problems.\n\n- The sources of observations in Line 209 and Line 260 are unclear. These assertions need proper citations to relevant literature. For example, in point (2) in Line 260, there are considerable research demonstrating the existence of a small portion of neurons or attention heads in neural networks that also can significantly influence inference outputs during the inference phase [1,2,3].\n\n3. The experimental section focuses solely on binary classification, neglecting multi-class scenarios. It would be beneficial to consider multi-class problems.\n\n4. *OCC(0.2) sometimes improves the forest's predictive performance.*  Could the authors provide some insights  for  latent reasons?\n\n5. In section 4.3, introducing consideration of only $s$ candidates, although has a higher chance to remain unchanged when adding or removing data points, it is also entirely possible to not obtain the best split in all possible splits. The authors should discuss this additional loss caused by only $s$ candidates.\n\n[1] Morcos, A. S., Barrett, D. G., Rabinowitz, N. C., & Botvinick, M. (2018, February). On the importance of single directions for generalization. In *International Conference on Learning Representations*.\n\n[2] Goh, Gabriel, Nick Cammarata, Chelsea Voss, Shan Carter, Michael Petrov, Ludwig Schubert, Alec Radford, and Chris Olah. \"Multimodal neurons in artificial neural networks.\" *Distill* 6, no. 3 (2021): e30.\n\n[3] Zhu, W., Zhang, Z., & Wang, Y. Language Models Represent Beliefs of Self and Others. In *Forty-first International Conference on Machine Learning*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)