DynFrs: An Efficient Framework for Machine Unlearning in Random Forest

## Abstract

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 ) occ 𝑞 \textsc{occ}(q) occ ( italic_q ) and a lazy tag strategy lzy , and is still adaptable to any Random Forest variant. In essence, occ ⁢ ( q ) occ 𝑞 \textsc{occ}(q) occ ( italic_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.

## 1 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, ).
This concept emerged as a response to growing concerns over personal data security, especially in light of regulations 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 a single data point in most machine 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 can achieve the desired objective, but is computationally expensive, making it impractical for real-world applications.
Thus, the ability of models to 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, particularly focusing on models such as neural networks (Mehta et al., ; Cheng et al., ), support vector machines (Cauwenberghs and Poggio, ), and $k$-nearest neighbors (Schelter et al., ).
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 developed for neural networks (Bourtoule et al., ) and methods dealing with loss functions and gradient (Qiao et al., ) 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., ), financial market prediction (Basak et al., ), and recommendation systems (Zhang and Min, ) for its effectiveness in classification and regression.

To this end, we study an efficient machine unlearning framework dubbed DynFrs for RFs.
One of its components, the $\textsc{occ}(q)$ subsampling technique, limits the impact of each data sample to a small portion of trees while maintaining similar or better predictive accuracy through the ensemble.
DynFrs resolves three kinds of requests on RFs: to predict the result of the query, to remove samples (machine unlearning), and to add samples to 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 a 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 a subsampling method $\textsc{occ}(q)$ that guarantees a $1/q$ times (where $q<1$) training speedup and an expected $1/q^{2}$ times unlearning speedup compared to naïve retraining approach. Empirical results show that $\textsc{occ}(q)$ brings improvements to predictive performance for many datasets.
- •
Lazy Tag: We introduce the lazy tag strategy lzy that avoid subtree retraining for unlearning 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$ to $1500000$ times speedup relative to the naïve retraining approach and is orders of magnitude faster than existing methods in sequential unlearning and multiple times faster in batch unlearning. In the online mixed data stream settings, DynFrs achieves an 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, ). 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, ), and $k$-nearest neighbor (Schelter et al., ).
Lately, SISA (Bourtoule et al., ) 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 accomplished 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. () 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, a subtree variant is maintained for switching during the unlearning process.
However, HedgeCut only supports removal of a small fraction ($0.1\%$) of the entire dataset.
Brophy and Lowd () 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 unlearning, they are incapable of batch unlearning (unlearn multiple samples simultaneously in one request).

Laterly, unlearning frameworks like OnlineBoosting (Lin et al., ) and DeltaBoosting (Wu et al., ) 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 computational cost for unlearning individual instances limits its practical use in real-world applications. In the literature, Sun et al. () attempted to lazily unlearn samples from RFs, but their approach still requires subtree retraining and suffers from several limitations in both clarity and design.

Different from others, our proposed DynFrs excels in 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 $\mathcal{D}\subseteq\mathbb{R}^{d}\times\mathcal{Y}$ represent the underlying sample space. The goal is to find a hypothesis $h$ that captures certain properties of the unknown $\mathcal{D}$ based on observed samples. We denote each sample by $\langle\mathbf{x},y\rangle$, where $\mathbf{x}\in\mathbb{R}^{d}$ is a $d$-dimensional vector describing features of the sample and $y\in\mathcal{Y}$ represents the corresponding label or value. Denote $S$ as the set of observed samples, consisting of $n$ independent and identically distributed (i.i.d.) samples $\langle\mathbf{x}_{i},y_{i}\rangle$ for $i\in[n]$ drawn from $\mathcal{D}$, where $[n]\triangleq\{i\mid 1\leq i\leq n,i\in\mathbb{Z}\}$. For clarity, we call the $k$-th entry of $\mathbf{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:\mathcal{S}\to\mathcal{H}$ maps a training set $S\in\mathcal{S}$ to a hypothesis $A(S)\in\mathcal{H}$. We then define $A^{-}:\mathcal{H}\times\mathcal{S}\times\mathcal{D}\to\mathcal{H}$ as an unlearning algorithm, where $A^{-}(A(S),S,\langle\mathbf{x},y\rangle)$ produces the modified hypothesis with the impact of $\langle\mathbf{x},y\rangle$ removed. The algorithm $A^{-}$ is termed an exact unlearning algorithm if the hypotheses $A(S\cup\langle\mathbf{x},y\rangle)$ and $A^{-}(A(S),S,\langle\mathbf{x},y\rangle)$ follow the same distribution. That is,

$$ $\Pr\left[A(S\,\backslash\langle\mathbf{x},y\rangle)\right]=\Pr\left[{A^{-}(A(S ),S,\langle\mathbf{x},y\rangle)}\right].$ (1) $$

### 3.2 Random Forest

Prior to discussing Random Forests, it is essential to first introduce its base learner, the Decision tree (DT), a well-known tree-structured supervised learning method.
It is proven that finding the optimal DT is NP-Hard (Hyafil and Rivest, ; Demirović et al., ); thus, studying hierarchical approaches is prevalent in the literature.
In essence, the tree originates from a root containing all training samples and grows recursively by splitting a leaf node into new leaves until a predefined stopping criterion is met.
Typically, DTs take the form of binary trees where
each node branches into two by splitting $S_{u}$ (the set of samples obsessed by the node $u$) into two disjoint sets. Let $u_{l}$ and $u_{r}$ be the left and right child of node $u$, and call $(a_{u}^{\star},w_{u}^{\star})$ the best split of $u$ that splits it. Then, the split partitions $S_{u}$ into

$$ $S_{u_{l}}=\{\langle\mathbf{x},y\rangle\in S_{u}\mid\mathbf{x}_{a_{u}^{\star}} \leq w\},\qquad S_{u_{r}}=\{\langle\mathbf{x},y\rangle\in S_{u}\mid\mathbf{x}_ {a_{u}^{\star}}>w\}.$ $$

The best split $(a_{u}^{\star},w_{u}^{\star})$ is found among all possible splits $\{(a,w)\mid a\in[p],w\in\mathbb{R}\}$ by optimizing an empirical criterion $I(S,\langle\mathbf{x},y\rangle)$ such as the Gini index $I_{G}$ Breiman et al. (), or the Shannon entropy $I_{E}$ Quinlan ():

$$ $\begin{gathered}I_{G}(S_{u},(a,w))=\sum_{v\in\{u_{l},u_{r}\}}\frac{|S_{v}|}{|S _{u}|}\left(1-\sum_{c\in\mathcal{Y}}\frac{|S_{v,c}|^{2}}{|S_{v}|^{2}}\right), \\ I_{E}(S_{u},(a,w))=\sum_{\begin{subarray}{c}v\in\{u_{l},u_{r}\},c\in\mathcal{Y }\end{subarray}}\left(-\frac{|S_{v,c}|}{|S_{v}|}\log_{2}\frac{|S_{v,c}|}{|S_{v }|}\right),\end{gathered}$ $$

where $S_{u,c}\triangleq\{\langle\mathbf{x},y\rangle\in S_{u}\mid y=c\}$.
The prediction for sample $\langle\mathbf{x},y\rangle$ starts with the root and recursively goes down to a child until a leaf is reached, and the traversal proceeds to the left child if $\mathbf{x}_{a^{\star}_{u}}\leq w^{\star}_{u}$ and to the right otherwise.

Random forest (RF) is an 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 error (Breiman, ). One method involves selecting the best split $(a_{u}^{\star},w_{u}^{\star})$ among $p$ randomly selected attributes rather than all $d$ attributes.
Additionally, subsampling methods such as bootstrap (Breiman et al., ), or $m$-out-of-$n$ bootstrap (Genuer et al., ), are used to introduce more randomness.
Bootstrap creates a training set $S^{(t)}$ for each tree $\psi_{t}$ by drawing $n$ i.i.d. samples from the original dataset $S$ with replacement. A variant called $m$-out-of-$n$ bootstrap randomly picks $m$ different samples from $S$ to form $S^{(t)}$.
These subsampling methods increase the diversity among trees, enhancing the robustness and generalizability of the model.
However, all existing RF unlearning methods do not adopt subsampling, and Brophy and Lowd () claims this exclusion does not affect the model’s predictive accuracy.

### 3.3 Extremely Randomized Tree

Extremely randomized trees (ERTs) (Geurts et al., ) is a variant of the Decision Trees, but ERTs embrace randomness when finding the best split.
For a tree node $u$, both ERT and DT find the best splits on $p$ randomly selected attributes $a_{1\cdots p}\subseteq[d]$, but for each attribute $a_{k}$, ($k\in[p]$), ERT considers only $s$ candidates $\{(a_{k},w_{k,i})\mid i\in[s]\}$, where $w_{k,1\cdots s}$ are uniformly sampled from range $[\min\{x_{i,a_{k}}\mid\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}\},\max\{x_{i
,a_{k}}\mid\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}\}]$.
Then, the best split $(a_{u}^{\star},w_{u}^{\star})$ is set as the candidates with optimal empirical criterion score (where $I$ could be either $I_{G}$ or $I_{E}$):

$$ $(a_{u}^{\star},w_{u}^{\star})\triangleq\arg\min\{I(S_{u},(a_{k},w_{k,i}))\mid k \in[p],i\in[s]\}.$ $$

Compared to DTs considering all $\mathcal{O}(p|S_{u}|)$ possible splits, ERTs consider only $\mathcal{O}(ps)$ candidates while maintaining similar predictive accuracy.
This shrink in candidate size makes ERT less sensitive to sample removal, and thus makes ERT outstanding for efficient machine unlearning.

## 4 Methods

In this section, we introduce the DynFrs framework, which is structured into three components — the subsampling method $\textsc{occ}(q)$, the lazy tag strategy lzy, and the base learner ERT.
$\textsc{occ}(q)$ allocates fewer training samples to each tree (i.e., $S^{(1)},\cdots,S^{(T)}$) with the aim to minimize the work brought to each tree during both training and unlearning phrase while preserving par predictive 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 auto tree structure modification and suiting DynFrs for online fixed data streams.
ERTs require fewer adjustments towards sample addition/deletion, making them the appropriate base learners for the framework.
In a nutshell, DynFrs optimize machine unlearning in tree-based methods from three perspectives — across trees ($\textsc{occ}(q)$), across requests (lzy), 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 ().
Developing novel subsampling methods can further enhance this effect.
Recall that $S\in\mathcal{D}^{n}$ represents the training set, and $S^{(t)}$ denotes the training set for the $t$-th tree $\psi_{t}$.
Empirical results (Section 5.2) indicate that having a reduced training set (i.e., $|S^{(t)}|<|S|$) does not degrade predictive performance and may even improve accuracy as more randomness is involved.
In the following, we demonstrate that $\textsc{occ}(q)$ leverages smaller $|S^{(t)}|$ and considerably shortens training and unlearning time.

One observation is that if sample $\langle\mathbf{x}_{i},y_{i}\rangle\in S$ does not occurs in tree $\psi_{t}$ (i.e., $\langle\mathbf{x}_{i},y_{i}\rangle\notin S^{(t)}$), then tree $\phi_{t}$ is unaffected when unlearning $\langle\mathbf{x}_{i},y_{i}\rangle$.
Therefore, it is natural to constrain the occurrence of each sample $\langle\mathbf{x}_{i},y_{i}\rangle\in S$ in the forest.
To achieve this, $\textsc{occ}(q)$ performs subsampling on trees instead of training samples, as it is how other methods did.
The algorithm starts with iterating through all training samples, and for each sample $\langle\mathbf{x}_{i},y_{i}\rangle\in S$, $k$ different trees (say they are $\psi_{i_{1}},\ldots,\psi_{i_{k}}$ with $i_{1\cdots k}\in[n]$) are randomly and independently drawn from all $T$ trees (Algorithm 1: line 5), where $k$ is determined by the proportion factor $q$ ($q<1$) satisfying $k=\lceil qT\rceil$.
Then, $\textsc{occ}(q)$ appends $\langle\mathbf{x}_{i},y_{i}\rangle$ to all of the drawn tree’s own training set ($S^{(1)},S^{(2)},\ldots,S^{(k)}$) (Algorithm 1: line 6-8).
When all sample allocations finish, The algorithm terminates in $\mathcal{O}(nk)=\mathcal{O}(nqT)$.
Intuitively, $\textsc{occ}(q)$ ensures that each sample occurs in exactly $k$ trees in the forest, and thus reduces the impact of each sample from all $T$ trees to merely $\lceil qT\rceil$ trees.

Further calculation confirms that $\textsc{occ}(q)$ provides an expected $1/q^{2}$ unlearning speedup toward naïvely retraining.
When unlearning an arbitrary sample with $\textsc{occ}(q)$, w.l.o.g (tree order does not matter), assume it occurs in the first $k=\lceil qT\rceil$ trees $\psi_{1},\ldots,\psi_{k}$.
Calculation begins with finding the sum of all affected tree’s training set sizes:

$$ $\displaystyle N_{\text{occ}}=\sum_{t=1}^{k}\big{|}S^{(t)}\big{|}=\sum_{i=1}^{| S|}\sum_{t=1}^{k}\big{[}\langle\mathbf{x}_{i},y_{i}\rangle\in S^{(t)}\big{]}.$ $$

As for each sample $\langle\mathbf{x}_{i},y_{i}\rangle\in S$, $\textsc{occ}(q)$ assures that $\Pr[\langle\mathbf{x}_{i},y_{i}\rangle\in S^{(t)}]=k/T=q$, giving,

$$ $\displaystyle\mathbb{E}\left[N_{\text{occ}}\right]=\sum_{i=1}^{|S|}\sum_{t=1}^ {k}\mathbb{E}\left[1\big{[}\langle\mathbf{x}_{i},y_{i}\rangle\in S^{(t)}\big{] }\right]=\sum_{i=1}^{|S|}\sum_{t=1}^{k}\Pr\left[\langle\mathbf{x}_{i},y_{i} \rangle\in S^{(t)}\right]=qk|S|=q^{2}T|S|.$ $$

For the naïve retraining method, the corresponding sum of affected sample size $N_{\text{nai}}$ is $T|S|$ as all trees and all samples are affected.
As the retraining time complexity is linear to $N_{\text{occ}}$ and $N_{\text{nai}}$ (Appendix A.2, Theorem 2), the expected computational speedup provided by $\textsc{occ}(q)$ is $\mathbb{E}[N_{\text{occ}}/N_{\text{nai}}]=1/q^{2}$, when $\textsc{occ}(q)$ and the naïve method adopt the same retraining method.

The above analysis also concludes that training a Random Forest with $\textsc{occ}(q)$ will result in a $1/q$ times boost.
In practice, we will empirically show (in Section 5.2) that by taking $q=0.1$ or $q=0.2$, the resulting model would have a similar or even higher accuracy in binary classification, which benefits unlearning with a $100\times$ or $25\times$ boost, and make training $10\times$ or $5\times$ faster.

### 4.2 Lazy Tag Strategy

Figure: Figure 1: Left: (a) A sample addition/deletion request arises. (b) The nodes it impacts are covered in the blue path. (c) There is a change in best split in the purple node (but not in other visited nodes), and a tag is placed on it. (d) The subtree of the tagged node is deleted. Middle: (a) A querying request arises. (b) A node that determines the prediction is covered in the orange path. (c) The tag is 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 tree recursively) the tree.
Refer to caption: x1.png

There are two observations on the differences between tree-based methods and neural network 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. 1 left, blue path, and deleted nodes).
(2) During the inference phase, only a small portion of the whole model determines the prediction of the model (Fig. 1 middle, orange path).
Along with another universal observation “(3) Adjustments to the model is unnecessary until a querying request arises”, we are able to develop the lzy lazy tag strategy that minimizes adjustments to tree structure when facing a mixture of sample addition/deletion and querying requests.

Intuitively, A tree node $u$ can remain unchanged if adding/deleting a sample does not change its best split $(a_{u}^{\star},w_{u}^{\star})$.
Then, the sample addition/deletion request would affect only one of the $u$’s 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.
Unfortunately, if the change in best split occurs in node $u$, we need to retrain the whole subtree rooted by $u$ to meet the criterion for exact unlearning.
Therefore, a sample addition/deletion request affects only a path and a subtree of the whole tree, which is observation (1).

As retraining a subtree is time-consuming, we place a tag on $u$, denoting it needs a reconstruction (Algorithm 2: line: 8-9).
When another sample addition/deletion request reaches the tagged $u$ later, it just simply ends here (Algorithm 2: line 7) since the will-be-happening reconstruction would cover this request as retraining is the most effective unlearning method.
But when a querying request meets a tag, we need to lead it to a leaf so that a prediction can be made (observation (3)).
As we do not retrain the subtree, 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 $u$ 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 $u$ since it has been split and push down the tags to both of its children, indicating further splitting on them is needed (Algorithm 2: line 26-27).
As depicted in Fig. 1 right side, the desired path reveals when the recursive pushing-down process reaches a leaf.

To summarize, within a node, only queries activate node reconstruction, and between two queries that visit this node, lzy automatically batch all reconstructions into one and saves plenty of computational efforts.
From the tree’s perspective, lzy replaces the subtree retraining by amortizing it into path constructions in queries so that the latency for responding to a request is reduced. Unlike $\textsc{occ}(q)$’s reducing work across trees and believing in ensemble, lzy relies on tree structures, dismantling requests into smaller parts and digesting them through time.

### 4.3 Unlearning in Extremely Randomized Trees

Despite $\textsc{occ}(q)$ 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 remaining competitive in predictive performance.
This robustness ensures the whole DynFrs framework undergoes fewer changes in the tree’s perspective when unlearning.

In essence, each ERT node finds the best split among $s$ (usually around 20) candidates on one attribute instead of all possible splits (possibly more than $10^{5}$) so that the best split has a higher chance to remain unchanged when a sample addition/deletion occurs in that node.
Additionally, It takes a time complexity of $\mathcal{O}(ps)$ for ERTs to detect whether the change in best split occurs if all candidate’s split statistics are stored during the training phase, which is much more efficient than the $\mathcal{O}(p|S_{u}|)$ detection for Decision Trees.
To be specific, for each ERT node $u$, we store a subset of attributes $a_{1\cdots p}\subseteq[d]$, and for each interested attribute $a_{k}$, $s$ different thresholds $w_{k,1\cdots s}$ is randomly generated and stored.
Therefore, a total of $p\cdot s$ candidates $\{(a_{k},w_{k,i})\mid k\in[p],i\in[s]\}$ determine the best split of the node.
Furthermore, the split statistics of each candidate $(a_{k},w_{k,i})$ 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 a sample addition/deletion occurs, each candidate’s split statistics can be updated in $\mathcal{O}(1)$, and we assign the one with optimal empirical criterion score as the node’s best split.

However, one special case is that a resampling on $w_{k,1\cdots s}$ is needed, when a change in range of $a_{k}$ occurs. ERT node $u$ find the candidates of attribute $a_{k}$ by generating i.i.d. samples following a uniform distribution on $[a_{k,\min},a_{k,\max}]$, where $a_{k,\min}\triangleq\min\{x_{i,a_{k}}\mid\langle\mathbf{x}_{i},y_{i}\rangle\in
S
_{u}\}$ and $a_{k,\max}$ is defined similarly. Therefore, we keep track of $a_{k,\min}$ and $a_{k,\max}$ and resample candidates’ threshold when the range $[a_{k,\min},a_{k,\max}]$ changes due to sample addition/deletion.

### 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 deletion suits the definition of exact (un)learning (Section 3.1), validating the unlearning efficacy of DynFrs:

###### Theorem 1 .

Sample deletion and addition for the DynFrs framework are exact.

Next, we 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 of attribute $a$ requires a time complexity of $\mathcal{O}(|S_{u}|\log|S_{u}|)$. In this work, we propose a more efficient $\mathcal{O}(|S_{u}|\log s)$ algorithm (see Appendix A.2, Lemma 1) to find the desired split utilizing data structure that performs $\mathcal{O}(1)$ range addition, and $\mathcal{O}(s)$ range query. Since $|S_{u}|\gg s$ in most cases, and usually $\log_{2}s\leq 5$, this new algorithm is advantageous in both theoretical bounds and practical performance.

For DynFrs with $T$ trees, each having a maximum depth $d_{\max}$, and considering $p$ attributes per node, the time complexity for training on a training set with $n=|S_{u}|$ is derived as:

###### Theorem 2 .

Training DynFrs yields a time complexity of $\mathcal{O}(qTd_{\max}pn\log s)$.

Thanks to $\textsc{occ}(q)$ that significantly reduces the workload for each tree and lzy that avoids subtree retraining, DynFrs achieves an outstanding time complexity for sample addition/deletion and an efficient one for querying. For clarity, we define $n_{\text{aff}}$ as the sum of sample size $|S_{u}|$ of all node $u$ s.t. $u$ is met by request, and a change in range occurs, and $c$ be the number of attributes whose range has changed. Further, denote $n_{\text{lzy}}$ as the sum of sample size $|S_{u}|$ of all node $u$ s.t. $u$ is met by the request, and is tagged. Based on observations described in Section 4.2, we claim the following:

###### Theorem 3 .

Modification (sample addition or deletion) in DynFrs yields a time complexity of $\mathcal{O}(qTd_{\max}ps)$ if no attribute range changes occur while $\mathcal{O}(qTd_{\max}ps+cn_{\text{aff}}\log s)$ otherwise.

###### Theorem 4 .

Query in DynFrs yields a time complexity of $\mathcal{O}(Td_{\max})$ if no lazy tag is met, while $\mathcal{O}(Td_{\max}+pn_{\text{lzy}}\log s)$ otherwise.

###### Theorem 1 .

###### Theorem 2 .

###### Theorem 3 .

###### Theorem 4 .

## 5 Experiments

In this section, we 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 is moved to Appendix A.3.

#### 5.1.1 Baselines

We use DaRE (Brophy and Lowd, ), HedgeCut (Schelter et al., ), and OnlineBoosting (Lin et al., ) as baseline models. Although OnlineBoosting employs a different learning algorithm, it is included due to its superior performance in batch unlearning. Additionally, we included the Random Forest implementation from scikit-learn to provide an additional comparison of predictive performance. For all baseline models, we adhere to the instructions provided in the original papers and use the same parameter settings. More details regarding the baselines are in Appendix A.4.

#### 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 | 13 | 107 | 8 |
| Bank | 32950 | 8238 | .113 | 20 | 63 | 10 |
| 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 | 40 | 40 | 0 |
| Higgs | 8800000 | 2200000 | .530 | 28 | 28 | 0 |

We test DynFrs on 9 binary classification datasets that vary in size, positive sample proportion, and attribute types. The technical details of these data sets can be found in Table 1. For better predictive 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 accuracy (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 () and use the term boost standing for the speedup relative to the naïve retraining approach (i.e., the number of samples unlearned when naïvely retraining unlearns 1 sample). Each model’s naïve retraining procedure is implemented in 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 ($\uparrow$) comparison between models. Each cell contains the accuracy or AUC-ROC score with standard deviation in a smaller font. The best-performing model is bolded.**
| Datasets | DaRE | HedgeCut | Random<br>Forest | Online<br>Boosting | DynFrs<br>$(q=0.1)$ | DynFrs<br>$(q=0.2)$ |
| --- | --- | --- | --- | --- | --- | --- |
| Purchase | .9327$\pm.001$ | .9118$\pm.001$ | .9372$\pm.001$ | .9207$\pm.000$ | .9327$\pm.001$ | .9359$\pm.001$ |
| Vaccine | .7916$\pm.003$ | .7706$\pm.002$ | .7939$\pm.002$ | .8012$\pm.000$ | .7911$\pm.001$ | .7934$\pm.002$ |
| Adult | .8628$\pm.001$ | .8428$\pm.001$ | .8637$\pm.000$ | .8503$\pm.000$ | .8633$\pm.001$ | .8650$\pm.001$ |
| Bank | .9420$\pm.000$ | .9350$\pm.000$ | .9414$\pm.001$ | .9436$\pm.000$ | .9417$\pm.000$ | .9436$\pm.000$ |
| Heart | .7344$\pm.001$ | .7195$\pm.001$ | .7342$\pm.001$ | .7301$\pm.000$ | .7358$\pm.002$ | .7366$\pm.000$ |
| Diabetes | .6443$\pm.001$ | .6190$\pm.000$ | .6435$\pm.001$ | .6462$\pm.000$ | .6453$\pm.001$ | .6470$\pm.002$ |
| NoShow | .7361$\pm.001$ | .7170$\pm.000$ | .7387$\pm.000$ | .7269$\pm.000$ | .7335$\pm.001$ | .7356$\pm.000$ |
| Synthetic | .9451$\pm.000$ | / | .9441$\pm.000$ | .9309$\pm.000$ | .9424$\pm.000$ | .9454$\pm.000$ |
| Higgs | .7441$\pm.000$ | / | .7434$\pm.000$ | .7255$\pm.000$ | .7431$\pm.000$ | .7475$\pm.000$ |

Figure: Figure 2: DynFrs with different $q$ is tested on the dataset Adult and Diabetes, and the tendency is shown by the curve with the standard deviation shown by error bars.
Refer to caption: x2.png

We evaluate the predictive performance of DynFrs in comparison with 4 other models in 9 datasets. The detailed results are listed in Table 2.
In 6 out of 9 datasets, $\textsc{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-learn Random Forest comes first in Purchase and NoShow.
These results show that $\textsc{occ}(0.2)$ sometimes improves the forest’s predictive performance.
Looking closely at $\textsc{DynFrs}(q=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.8.

The effects of $q$ are assessed on the two most commonly used datasets (Adult and Diabetes) in RF classification.
From Fig. 3, an acute drop in predictive accuracy is obvious when $q<0.1$.
For the Adult dataset, DynFrs’s predictive accuracy peaks at $q=0.4$, while a similar tendency is observed for the Diabetes dataset with the peak at $q=0.2$.
However, to avoid tuning on $q$, we suggest choosing $q=0.2$ to optimize accuracy and $q=0.1$ to improve unlearning efficiency.

To determine whether $\textsc{DynFrs}(q=0.1)$ achieves exact unlearning (Section 3.1), we compare it with a retrain-from-scratch model with various sample removal proportions.
Specifically, Let $S^{-}$ denote the set 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\backslash 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^{-}|/|S|$).
This close alignment suggests that, empirically, the unlearned model and the retrained model follow the same distribution (Equation 1).

### 5.3 Sequential Unlearning

Figure: Figure 4: Comparison of sequential unlearning boost ($\uparrow$) between DynFrs with different $q$ and DaRE, and error bars represent the minimum and maximum values among five trials.
Refer to caption: x4.png

In this section, we evaluate the efficiency of DynFrs in sequential unlearning settings, where models process unlearning requests individually.
In experiments, models are fed with a sequence of unlearning requests until the time elapsed exceeds the time naïve 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 $\textsc{occ}(q)$ as the naïve retraining method for DynFrs.
As shown in Fig. 4, DynFrs consistently outperforms DaRE, the state-of-the-art method in sequential unlearning for RFs, across all datasets, in both $q=0.1$ and $q=0.2$ settings, and achieved a $22\times$ to $523\times$ speedup relative to DaRE.
Furthermore, DynFrs demonstrates a more stable performance compared to DaRE who exhibits large error bars in Higgs.

HedgeCut is excluded from the plot as it is unable to 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. 6 upper-left plot).
Appendix A.6 contains more experiment results.

### 5.4 Batch Unlearning

Figure: Figure 5: Comparison of the batch unlearning runtime ($\downarrow$) of DynFrs and two baseline methods under with 4 different unlearning batch sizes.
Refer to caption: x5.png

We measure each model’s batch unlearning performance based on execution time (DynFrs’s runtime includes retraining of 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. 6, 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 dealing large batches.
In contrast, OnlineBoosting achieves competitive performance on these datasets, but DynFrs completes the same requests in half the time.
Furthermore, OnlineBoosting shows the poorest performance in single-instance unlearning (Fig. 6 upper-left), and this inability limits its effectiveness in sequential unlearning.
Overall, Fig. 6 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 in the plot, indicating their lack of specialization for batch unlearning.
Meanwhile, the curve of OnlineBoosting maintains a stationary performance for batch sizes up to $10^{4}$ 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 is the only model whose runtime converges for large batches, attributed to the presence of lzy.

### 5.5 Online Mixed Data Stream

In this section, we introduce the online mixed data stream setting, which satisfies:
(1) there are 3 types of requests: sample addition, sample deletion, and querying;
(2) requests arrive in a mixed sequence, with no prior knowledge of future requests until the current one is processed;
(3) the amount of addition and deletion requests are roughly balanced, allowing unchanged model’s hyperparameters;
(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/deletion and query simultaneously.

Due to the page limit, this part is moved to Appendix A.7.

## 6 Conclusion

In this work, we introduced DynFrs, a framework that supports efficient machine unlearning in Random Forests.
Our results show that DynFrs is 4-6 orders of magnitude faster than the naïve retraining model and 2-3 orders of magnitude faster than the state-of-the-art Random Forest unlearning approach DaRE (Brophy and Lowd, ).
DynFrs also outperforms OnlineBoosting (Lin et al., ) in batch unlearning. In the context of online data streams, DynFrs demonstrated strong performance, with an average latency of 0.12 ms on sample addition/deletion in the large-scale dataset Higgs.
This efficiency is due to the combined effects of the subsampling method $\textsc{occ}(q)$, 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.

## 7 Reproducibility Statement

- •
Code: We provide pseudocode to help understand this work. All our code is publicly available at: [https://anonymous.4open.science/r/DynFrs-2603](https://anonymous.4open.science/r/DynFrs-2603).
- •
Datasets: All datasets are either included in the repo, or a description for how to download and preprocess the dataset is provided. All datasets are public and raise no ethical concerns.
- •
Hyperparameters: All parameters of our proposed framework is provided in Appendix A.8, Table 9.
- •
Environment: Details of our experimental setups are provided in Appendix A.3.
- •
Random Seed: we use C++’s mt19937 module with a random device for all random behavior, with the random seed determined by the system time.

## Appendix A Appendix

### A.1 Pseudocode

Figure: Algorithm 1 Training DynFrs and Unlearning Samples with $\textsc{occ}(q)$

Figure: Algorithm 2 Unlearning and Querying in Trees with lzy

### A.2 Proofs

###### Theorem 1 .

Sample deletion and addition for the DynFrs framework are exact.

###### Proof.

We prove that the subsampling method $\textsc{occ}(q)$ maintains the exactness of DynFrs.
Let random variable $o_{i,t}\triangleq[\langle\mathbf{x}_{i},y_{i}\rangle\in S^{(t)}]$ denotes whether $\langle\mathbf{x}_{i},y_{i}\rangle$ occurs in $S^{(t)}$.
In $\textsc{occ}(q)$, each sample $\langle\mathbf{x}_{i},y_{i}\rangle$ is distributed to $\lceil qT\rceil$ distinct trees, with the selection of these trees being independent of other samples $\langle\mathbf{x}_{j},y_{j}\rangle\in S$ for $j\neq i$.
Thus, $o_{i,\cdot}$ is independent from $o_{j,\cdot}$ for $j\neq i$.
However, $o_{i,1},o_{i,2},\ldots,o_{i,T}$ are dependent on each other, constrainted by $\forall t\in[T]$, $o_{i,t}\in\{0,1\}$, $\sum_{t=0}^{T}o_{i,t}=\lceil qT\rceil$, and we say they follow a joint distribution $\mathcal{B}(T,q)$.

Now, let $S^{\prime(1)},S^{\prime(2)},\ldots,S^{\prime(T)}$ denotes the training sets for each tree generated by applying $\textsc{occ}(q)$ to the modified training set $S^{\prime}$, and let $o^{\prime}_{i,t}\triangleq[\langle\mathbf{x}_{i},y_{i}\rangle\in S^{\prime(t)}]$.
Then, when deleting sample $\langle\mathbf{x}_{i},y_{i}\rangle$ (i.e., $S^{\prime}=S\backslash\langle\mathbf{x}_{i},y_{i}\rangle$), we have $(o_{j,1},\ldots,o_{j,T})\sim\mathcal{B}(T,q)$ and $(o^{\prime}_{j,1},\ldots,o^{\prime}_{j,T})\sim\mathcal{B}(T,q)$ for $i\neq j$, and $o_{i,\cdot}=0$ (because $\langle\mathbf{x}_{i},y_{i}\rangle$ is removed) and $o^{\prime}_{i,\cdot}=0$.
Notably, $\mathcal{B}(T,q)$ depends on $T$ and $q$ only, but not on training samples $S$.
This shows that simply setting $o_{i,\cdot}=0$ ensures that $\textsc{occ}(q)$ with sample removed maintains the same distribution as applying $\textsc{occ}(q)$ on the modified training set.

Similarily, when adding $\langle\mathbf{x}_{i},y_{i}\rangle$ (i.e., $S^{\prime}=S\cup\langle\mathbf{x}_{i},y_{i}\rangle$), $(o_{j,1},\ldots,o_{j,T})$ and $(o^{\prime}_{j,1},\ldots,o^{\prime}_{j,T})$ follow the same distribution $\mathcal{B}(T,q)$ for $j\neq i$.
While $(o_{j,1},\ldots,o_{j,T})$ is generated from $\mathcal{B}(T,q)$ for addition, it is equivalent to $(o^{\prime}_{i,1},\ldots,o^{\prime}_{i,T})$ for following the same distribution.
Therefore, $\textsc{occ}(q)$ with sample added maintains the same distribution as applying $\textsc{occ}(q)$ on the modified training set.

Next, we prove that the addition and deletion operations are exact within a specific DynFrs tree. When no change in range of attribute $a$ ($[\min\{\mathbf{x}_{i,a}\mid{\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}}\},
\max\{\mathbf{x}_{i,a}\mid\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}\}]$) 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 a change in range occurs, DynFrs 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 deletion in DynFrs are exact.

∎

###### Lemma 1 .

For a certain Extremely Randomized Tree node $u$, and a specific attribute $a$, the time complexity of finding the best split of attribute $a$ is $\mathcal{O}(|S_{u}|\log s)$, assuming that $|S_{u}|\gg s$.

###### Proof.

Conventionally, for each tree node $u$ and an attribute $a$, we uniformly samples $s$ thresholds $w_{a,1\cdots s}$ from $[\min\{\mathbf{x}_{i,a}\mid\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}\},\max
\{\mathbf{x}_{i,a}\mid\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}\}]$.
Then, we try to split $S_{u}$ with each threshold and look for split statistics that are: (1) the number of samples in the left or right child (i.e., $|S_{u_{l}}|$ and $|S_{u_{r}}|$), and (2) the number of positive samples in left or right child ($|S_{u_{l},+}|$ and $|S_{u_{r},+}|$), which are the requirements for calculating the empirical criterion scores.

One approach, as used by prior works, first sort all samples $S_{u}$ by $\mathbf{x}_{\cdot,a}$ in ascending order, and then sort thresholds $w_{a,1\cdots s}$ in ascending order. These sortings has a time complexity of $\mathcal{O}(|S_{u}|\log|S_{u}|)$ and $\mathcal{O}(s\log s)$, respectively. After that, a similar technique used in the merge sort algorithm is used to find the desired split statistics in $\mathcal{O}(|S_{u}|+s)$.

To get rid of the costly sorting on $S_{u}$, we sort $w_{a,1\cdots s}$ $\mathcal{O}(s\log s)$ and then iterate through all samples and calculate the changes each sample brings to candidates’ split statistics. For convenience, let

$$ $\displaystyle b_{k}$ $\displaystyle\triangleq\big{|}\{\langle\mathbf{x}_{i},y_{i}\rangle\mid\langle \mathbf{x}_{i},y_{i}\rangle\in S_{u}\land\mathbf{x}_{i,a}\leq w_{a,k}\}\big{|},$ $\displaystyle c_{k}$ $\displaystyle\triangleq\big{|}\{\langle\mathbf{x}_{i},y_{i}\rangle\mid\langle \mathbf{x}_{i},y_{i}\rangle\in S_{u}\land\mathbf{x}_{i,a}\leq w_{a,k}\land y_{ i}=+\}\big{|},$ $$

which are crucial split statistics for calculating the empirical criterion score.
We start with setting $b_{1\cdots s}$ and $c_{1\cdots s}$ as all zeros.
Then, for a sample $\langle\mathbf{x}_{i},y_{i}\rangle\in S_{u}$, it will cause an increment in $b_{s^{\prime}\cdots s}$ for some $s^{\prime}$ satisfying $\mathbf{x}_{i,a}\leq w_{s^{\prime}}$ and $\mathbf{x}_{i,a}>w_{s^{\prime}-1}$.
Given that $w_{a,1\cdots s}$ are sorted, all $k$, ($s^{\prime}\leq k\leq s$) satisfy $\mathbf{x}_{i,a}\leq w_{a,k}$, while $\mathbf{x}_{i,a}>w_{a,k}$ for all $1\leq k<s^{\prime}$. $s^{\prime}$ can be easily found by binary search in $\mathcal{O}(\log s)$, then adding $1$ to $b_{s^{\prime}},b_{s^{\prime}+1},\ldots,b_{s}$ is the only thing left.
Use a loop for range addition is clearly $\mathcal{O}(s)$, but insteading of finding $b_{1\cdots s}$, we keep track of $d_{1\cdots s}$, where $d_{k}\triangleq b_{k}-b_{k-1}$.
So increment $b_{s^{\prime}\cdots s}$ can be replace by $d_{s^{\prime}}\leftarrow d_{s^{\prime}}+1$, which is $\mathcal{O}(1)$.
When all samples are processed, we construct $b_{1\cdot s}$ from $d_{1\cdots s}$, where prefix sums $b_{k}\leftarrow b_{k-1}+d_{k}$ help solve it in $\mathcal{O}(s)$.

For every sample $\langle\mathbf{x}_{i},y_{i}\rangle\in S$, we need to find $s^{\prime}$ in $\mathcal{O}(\log s)$ (Algorithm 3: line 10), and perform increment in $d_{s}^{\prime}$ in $\mathcal{O}(1)$ (Algorithm 3: line 11), which results in a time complexity of $\mathcal{O}(|S_{u}|\log s)$ in this part (Algorithm 3: line 9-14).
Meanwhile, the prefix sum is executed after all samples are processed (Algorithm 3: line 15-18), and its execution time is bounded by $\mathcal{O}(s)$.
Luckily, $c_{1\cdots s}$ can be calculated in a similar manner, and with both $b_{1\cdots s}$ and $c_{1\cdots s}$ ready, we can obtain the empirical criterion score for each candidate split (Algorithm 3: line 21-28), and this has a time complexity of $\mathcal{O}(s)$ assuming calculating criterion scores to be $\mathcal{O}(1)$.

Since $|S_{u}|\gg s$, the term $\mathcal{O}(|S_{u}|\log s)$ dominates in time complexity, with the binary search (Algorithm 3: line 10) being the threshold.
It is noteworthy that adopting exponential search to find $s^{\prime}$ can result in an expected $\mathcal{O}(\log\log s)$ time complexity since $w_{a,1\cdots s}$ are uniformly distributed.
However, binary search outperforms exponential search in practice, so we conclude with a time complexity of $\mathcal{O}(|S_{u}|\log s)$ for finding the best split of attribute $a$ in node $u$ when $|S_{u}|\gg s$.

Figure: Algorithm 3 Find the best split for attribute $a$

∎

Given $q<1$, the proportion of trees each sample is assigned to, $T$, the number of trees in the forest, $d_{\max}$, the maximum depth of each tree, $p$, the number of candidate attributes, $s$, the number of candidate splits for each attribute (usually $s\leq 30$), and $n=|S|$, size of the training set, we now prove the following:

###### Theorem 2 .

Training DynFrs yields a time complexity of $\mathcal{O}(qTd_{\max}pn\log s)$.

###### Proof.

For certain tree and a specific node $u$, we find the best split among $p$ randomly selected attributes $a_{1\cdots p}$, and we call $\textsc{FindAttributeBestSplit}(S_{u},a_{i},s)$ (Algorithm 3) $p$ times for each $i\in[p]$.
From Lemma 1, finding the best split for the node $u$ has a time complexity of $\mathcal{O}(p|S_{u}|\log s)$.
Then, summing $|S_{u}|$ over all tree nodes $u$ on that tree, we have $\sum_{u}|S_{u}|\leq d_{\max}qn$, since the root of the tree contains about $\lceil qT\rceil n/T\approx qn$ samples, and each layer has at most the same amount of samples as the root (layer 0).
Therefore, the time complexity for training one DynFrs tree can be bounded by $\mathcal{O}(d_{\max}qn\log s)$.
Since there are $T$ independent trees in the forest, the time complexity for training a DynFrs forest is $\mathcal{O}(qTd_{\max}pn\log s)$.

∎

###### Theorem 3 .

Modification (sample deletion or addition) in DynFrs yields a time complexity of $\mathcal{O}(qTd_{\max}ps)$ if no attribute range changes occurs while $\mathcal{O}(qTd_{\max}ps+cn_{\text{aff}}\log s)$ otherwise (where $c$ denotes the number of attributes affected, and $n_{\text{aff}}$ denotes the sum of sample size among all affected nodes met by this modification request).

###### Proof.

When no attribute range change occurs on each tree, the modification request traverses a path from the root to a leaf with at most $d_{\max}$ nodes.
For each node, we need to recalculate all the empirical criterion scores for all candidate splits $\mathcal{O}(ps)$.
Since $\textsc{occ}(q)$ guarantees that only $\lceil qT\rceil$ trees are affected by the modification requests, at most $qTd_{\max}$ nodes need the recalculation.
So, the time complexity for one modification request yields $\mathcal{O}(qTd_{\max}ps)$.

When an attribute range occurs on $u$, it is necessary to call $\textsc{FindAttributeBestSplit}(S_{u},a,s)$ for $u$ and the affected attribute $a$.
Given that the affected nodes’ sample sizes sum up to $n_{\text{aff}}$, and for each affected node, we need to resample at most $c\leq p$ attributes, and then Lemma 1 entails that the time complexity for completing all resampling is an additional $\mathcal{O}(cn_{\text{aff}}\log s)$.

∎

###### Theorem 4 .

Query in DynFrs yields a time complexity of $\mathcal{O}(Td_{\max})$ if no lazy tag is met, while $\mathcal{O}(Td_{\max}+pn_{\text{lzy}}\log s)$ otherwise (where $n_{\text{lzy}}$ 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 a leaf node, traversing a tree path with at most $d_{\max}$ nodes, and the query on DynFrs aggregates the results of all $T$ trees, therefore querying without bumping into a lazy tag yields a time complexity of $\mathcal{O}(Td_{\max})$.

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 $u$ calls function $\textsc{FindAttributeBestSplit}($) $p$ times and results in a time complexity of $\mathcal{O}(p|S_{u}|\log s)$.
As $n_{\text{lzy}}$ 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 of $\mathcal{O}(pn_{\text{lzy}}\log s)$.

∎

###### Theorem 1 .

###### Proof.

###### Lemma 1 .

###### Proof.

###### Theorem 2 .

###### Proof.

###### Theorem 3 .

###### Proof.

###### Theorem 4 .

###### Proof.

### A.3 Implementation

All of the experiments are conducted on a machine with AMD EPYC 9754 128-core CPU and 512 GB RAM in a Linux environment (Ubuntu 22.04.4 LTS), and all codes of DynFrs are written in C++ and compiled with the g++ 11.4.0 compiler and the -O3 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 a grid search: Number of trees in the forest $T\in\{100,150,250\}$, maximum depth of each tree $d_{\max}\in\{10,15,20,25,30,40\}$, and the number of sampled splits $s\in\{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 in their works [Schelter et al., , Lin et al., ].
Both of them are not capable of processing samples with sparse attributes, so 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, as its complexity degenerates to $\mathcal{O}(pn^{2})$ sometimes and consumes more than 256 GB RAM during training.

### A.5 Datasets

Sakar and Kastro [], Dua and Graff [] is primarily used to predict online shopping intentions, i.e., users’ determination to complete a transaction. The dataset was collected from an online bookstore built on an osCommerce platform.

Bull et al. [], DrivenData [] comes from data-mining competition in DrivenData. 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 determine whether a person received a seasonal flu vaccine.

Becker and Kohavi [], Dua and Graff [] 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 or not.

Moro et al. [], Dua and Graff [] is related to direct marketing campaigns of a Portuguese banking institution dated from May 2008 to November 2010. The goal is to predict if the client will subscribe to a term deposit based on phone surveys.

Kaggle [] is provided by Ulianova, and contains 70,000 patient records about cardiovascular diseases, with the label denoting the presence of heart disease.

Strack et al. [], Dua and Graff [] encompasses a decade (1999-2008) of clinical diabetes records from 130 hospitals across the U.S., covering laboratory results, medications, and hospital stays. The goal is to predict whether a patient will be readmitted within 30 days of discharge.

Kaggle [] focuses on the patient’s appointment information, such as date, number of SMS sent, and alcoholism, aiming to predict whether the patient will show up after making an appointment.

Baldi et al. [], Dua and Graff [] consists of $1.1\times 10^{7}$ signals characterized by 22 kinematic properties measured by detectors in a particle accelerator and 7 derived attributes. The goal is to distinguish between a background signal and a 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 simultaneously unlearning 1, 10, 100 instances or $0.1\%$ and $1\%$ of all samples, where DynFrs consistently outperforms all others in all settings and all datasets.

**Table 3: Training time ($\downarrow$) of each model, measured in seconds (s), and the standard deviation is given with the same unit in a smaller font. “/” means the model is unable to train on that dataset.**
| Datasets | DaRE | HedgeCut | Online<br>Boosting | DynFrs<br>$(q=0.1)$ | DynFrs<br>$(q=0.2)$ |
| --- | --- | --- | --- | --- | --- |
| Purchase | 3.10$\pm 0.0$ | 1.05$\pm 0.0$ | 0.27$\pm 0.0$ | 0.38$\pm 0.0$ | 0.72$\pm 0.0$ |
| Vaccine | 4.78$\pm 0.0$ | 431$\pm 14$ | 1.05$\pm 0.0$ | 1.12$\pm 0.0$ | 2.27$\pm 0.0$ |
| Adult | 5.02$\pm 0.1$ | 11.8$\pm 0.5$ | 0.77$\pm 0.0$ | 0.61$\pm 0.0$ | 1.15$\pm 0.0$ |
| Bank | 8.26$\pm 0.2$ | 8.44$\pm 0.3$ | 0.92$\pm 0.0$ | 1.15$\pm 0.0$ | 2.37$\pm 0.0$ |
| Heart | 12.1$\pm 0.2$ | 3.51$\pm 0.0$ | 1.02$\pm 0.0$ | 1.04$\pm 0.0$ | 1.96$\pm 0.0$ |
| Diabetes | 123$\pm 1.0$ | 162$\pm 3.3$ | 3.51$\pm 0.0$ | 8.67$\pm 0.0$ | 18.2$\pm 0.0$ |
| NoShow | 65.4$\pm 0.4$ | 28.1$\pm 0.3$ | 1.68$\pm 0.0$ | 3.08$\pm 0.0$ | 6.10$\pm 0.0$ |
| Synthetic | 1334$\pm 6.3$ | / | 40.7$\pm 0.9$ | 66.3$\pm 0.2$ | 128$\pm 0.4$ |
| Higgs | 10793$\pm 48$ | / | 460$\pm 13$ | 548$\pm 1.2$ | 1120$\pm 1.0$ |

**Table 4: Runime ($\downarrow$) for each model to unlearn 1 sample measured in milliseconds (ms), and the standard deviation is given with the same unit in a smaller font. “/” means the model is unable to train on that dataset or unlearning takes too long.**
| Datasets | DaRE | HedgeCut | Online<br>Boosting | DynFrs |
| --- | --- | --- | --- | --- |
| Purchase | 35.0$\pm 15$ | 1245$\pm 343$ | 83.4$\pm 9.0$ | 0.40$\pm 0.2$ |
| Vaccine | 16.0$\pm 15$ | 33445$\pm 14372$ | 222$\pm 53$ | 1.40$\pm 0.9$ |
| Adult | 10.6$\pm 5.0$ | 3596$\pm 2396$ | 249$\pm 62$ | 1.10$\pm 1.5$ |
| Bank | 33.2$\pm 17$ | 2760$\pm 371$ | 227$\pm 7.4$ | 2.40$\pm 3.7$ |
| Heart | 16.8$\pm 10$ | 972$\pm 154$ | 411$\pm 13$ | 0.50$\pm 0.2$ |
| Diabetes | 293$\pm 168$ | 27654$\pm 10969$ | 753$\pm 143$ | 7.30$\pm 5.4$ |
| NoShow | 330$\pm 176$ | 1243$\pm 94$ | 570$\pm 69$ | 0.30$\pm 0.0$ |
| Synthetic | 2265$\pm 3523$ | / | 5225$\pm 241$ | 2.50$\pm 3.7$ |
| Higgs | 182$\pm 156$ | / | 73832$\pm 4155$ | 4.90$\pm 3.9$ |

**Table 5: Runime ($\downarrow$) for each model to unlearn 10 samples measured in milliseconds (ms), and the standard deviation is given with the same unit in a smaller font. “/” means the model is unable to train on that dataset or unlearning takes too long.**
| Datasets | DaRE | HedgeCut | Online<br>Boosting | DynFrs |
| --- | --- | --- | --- | --- |
| Purchase | 295$\pm 54$ | 10973$\pm 643$ | 183$\pm 21$ | 12.3$\pm 4.8$ |
| Vaccine | 285$\pm 160$ | 222333$\pm 64756$ | 418$\pm 41$ | 9.20$\pm 2.8$ |
| Adult | 148$\pm 79$ | 51831$\pm 2795$ | 389$\pm 48$ | 4.80$\pm 2.4$ |
| Bank | 320$\pm 108$ | 18091$\pm 1524$ | 423$\pm 47$ | 7.6$\pm 2.7$ |
| Heart | 162$\pm 46$ | 5524$\pm 335$ | 625$\pm 36$ | 6.80 $\pm 2.8$ |
| Diabetes | 2773$\pm 877$ | 211640$\pm 79652$ | 1096$\pm 172$ | 85.5$\pm 38$ |
| NoShow | 2217$\pm 723$ | 17235$\pm 17905$ | 712$\pm 74$ | 18.2$\pm 123$ |
| Synthetic | 92279$\pm 42634$ | / | 6015$\pm 301$ | 77.3$\pm 34$ |
| Higgs | 6089$\pm 6174$ | / | 104063$\pm 1258$ | 32.1$\pm 8.6$ |

**Table 6: Runime ($\downarrow$) for each model to unlearn 100 samples measured in milliseconds (ms), and the standard deviation is given with the same unit in a smaller font. “/” means the model is unable to train on that dataset or unlearning takes too long.**
| Datasets | DaRE | HedgeCut | Online<br>Boosting | DynFrs |
| --- | --- | --- | --- | --- |
| Purchase | 35912$\pm 186$ | 83649$\pm 2047$ | 275$\pm 12$ | 70.4$\pm 11$ |
| Vaccine | 2385 $\pm 408$ | 1703355$\pm 157274$ | 792$\pm 15.06$ | 82.6$\pm 11$ |
| Adult | 954$\pm 158$ | 219392$\pm 34630$ | 632$\pm 24$ | 32.2$\pm 4.0$ |
| Bank | 3546$\pm 302$ | 195014$\pm 15854$ | 740$\pm 20$ | 78.8$\pm 13$ |
| Heart | 1502$\pm 543$ | 33806$\pm 5385$ | 986$\pm 75$ | 59.3$\pm 11$ |
| Diabetes | 23833$\pm 10330$ | / | 2071$\pm 115$ | 578.6$\pm 50$ |
| NoShow | 23856$\pm 3978$ | 57021$\pm 6327$ | 1120$\pm 92$ | 117$\pm 10$ |
| Synthetic | 1073356$\pm 420053$ | / | 7609$\pm 171$ | 889$\pm 287$ |
| Higgs | 29971$\pm 15559$ | / | 145386$\pm 5677$ | 642$\pm 317$ |

**Table 7: Left: runtime ($\downarrow$) for unlearning $0.1\%$ of the training set between models. Right: runtime ($\downarrow$) 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 a smaller font. “/” means the model is unable to train on that dataset or unlearning takes too long.**
| Datasets | DaRE | HedgeCut | Online<br>Boosting | DynFrs | DaRE | HedgeCut | Online<br>Boosting | DynFrs |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Purchase | 0.35$\pm 0.1$ | 11.25$\pm 1.5$ | 0.17$\pm 0.0$ | 0.01$\pm 0.0$ | 3.39$\pm 0.7$ | 76.0$\pm 3.0$ | 0.28$\pm 0.0$ | 0.07$\pm 0.0$ |
| Vaccine | 0.47$\pm 0.1$ | 404.73$\pm 69$ | 0.61$\pm 0.1$ | 0.02$\pm 0.0$ | 5.01$\pm 1.0$ | 4054$\pm 427$ | 0.98$\pm 0.0$ | 0.13$\pm 0.0$ |
| Adult | 0.44$\pm 0.3$ | 88.1$\pm 27$ | 0.49$\pm 0.1$ | 0.01$\pm 0.0$ | 3.39$\pm 0.6$ | 516$\pm 23$ | 0.80$\pm 0.0$ | 0.09$\pm 0.0$ |
| Bank | 1.15$\pm 0.3$ | 47.3$\pm 6.0$ | 0.61$\pm 0.1$ | 0.02$\pm 0.0$ | 14.7$\pm 2.3$ | 418$\pm 25$ | 0.96$\pm 0.0$ | 0.16$\pm 0.0$ |
| Heart | 0.70$\pm 0.2$ | 20.0$\pm 1.7$ | 0.85$\pm 0.0$ | 0.03$\pm 0.0$ | 8.43$\pm 1.2$ | 145$\pm 10$ | 1.23$\pm 0.0$ | 0.20$\pm 0.0$ |
| Diabetes | 23.8$\pm 2.7$ | 694$\pm 61$ | 2.12$\pm 0.1$ | 0.57$\pm 0.1$ | 258$\pm 20$ | / | 3.51$\pm 0.1$ | 2.50$\pm 0.1$ |
| NoShow | 18.8$\pm 2.7$ | 57.0$\pm 6.3$ | 1.10$\pm 0.1$ | 0.10$\pm 0.0$ | 268$\pm 7.5$ | / | 1.90$\pm 0.1$ | 0.56$\pm 0.0$ |
| Synthetic | 10790$\pm 5348$ | / | 13.1$\pm 0.6$ | 5.68$\pm 0.2$ | / | / | 44.2$\pm 1.4$ | 27.4$\pm 0.9$ |
| Higgs | / | / | 188$\pm 7.1$ | 39.2$\pm 0.7$ | / | / | 456$\pm 4.7$ | 201$\pm 9.6$ |

### A.7 Online Mixed Data Stream

**Table 8: DynFrs’s latency ($\downarrow$) of sample addition/deletion and querying in 4 scenarios measured in microseconds ($\mu$s). # add/del/qry: the number of sample addition/deletion/querying requests; add/del/qry lat.: the latency of sample addition/deletion/querying. Each cell contains the averaged latency with its minimum and maximum values listed in a smaller front.**
| No. | # add | # del | # qry | add lat. | del lat. | qry lat. |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | $5\cdot 10^{5}$ | $5\cdot 10^{5}$ | $10^{6}$ | 406.2 $[150,450894]$ | 437.6 $[134,394801]$ | 3680 $[209,1885030]$ |
| 2 | $5\cdot 10^{5}$ | $5\cdot 10^{5}$ | $10^{6}$ | 122.7 $[30,168984]$ | 120.2 $[25,146300]$ | 1218 $[23,1026964]$ |
| 3 | $5\cdot 10^{4}$ | $5\cdot 10^{4}$ | $10^{6}$ | 140.0 $[30,81661]$ | 139.2 $[32,101429]$ | 299.5 $[21,861151]$ |
| 4 | $5\cdot 10^{3}$ | $5\cdot 10^{3}$ | $10^{6}$ | 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 4 employ 25 threads using OpenMP.
DynFrs achieves an averaged latency of less than 0.15 ms for modification requests (Table 8 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 ms as the number of modification requests declines, as fewer lazy tags are introduced to trees.

These results are striking: while it takes over an hour to train a vanilla Random Forest on Higgs, DynFrs maintains exceptionally low latency that is measured in $\mu$s, even in the single-threaded setting.
This makes DynFrs highly suited for real-world scenarios, especially when querying constitutes a large proportion of requests (Table 8 Scenario 4).

### A.8 Hyperparameters

All hyperparameters of DynFrs are listed in Table 9. Specially, we set the minimum split size of each node to be $10$ for all datasets.

**Table 9: Hyperparameters used by DynFrs with both $q=0.1$ and $q=0.2$ setting.**
| Datasets | $T$ | $d_{\max}$ | $s$ |
| --- | --- | --- | --- |
| Purchase | 250 | 10 | 30 |
| Vaccine | 250 | 20 | 5 |
| Adult | 100 | 20 | 30 |
| Bank | 250 | 20 | 40 |
| Heart | 150 | 15 | 5 |
| Diabetes | 250 | 30 | 5 |
| NoShow | 250 | 20 | 5 |
| Synthetic | 150 | 40 | 30 |
| Higgs | 100 | 30 | 20 |

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: * Can the authors address the points raised in the weakness section above?
soundness: 3
strengths: * The method is simple yet effective, yielding an exact unlearning method for random forests.
* The approach reduces required re-training from the source by limiting the number of trees each data point influences.
* The method defers subtree re-computation until queries require that portion, making it suitable for online settings.
* Theoretical proofs demonstrate the algorithm's exactness and time complexity.
* Comprehensive experiments show superior performance compared to baselines, which suffer from numerical value binning.
* The algorithm demonstrates significantly faster performance than baselines.
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.
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.
* 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.
* The evaluation lacks testing on regression datasets.
* Line 204: \in -> \subset

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
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.

2. 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.
 
3. In the experiment, what are the detailed settings for the unlearning request in each dataset? 

4. 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?
 
5. 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?

I am not familiar with the extremely randomized trees, so I might change my assessment based on other reviewers' comments.
soundness: 2
strengths: 1. The motivation and the contributions of this paper are clearly shown.
2. This paper provides both theoretical and experimental results to show the huge efficiency improvements compared with the retrained model.
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.
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.

2.  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.

3. 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.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
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?
- How much memory does DYNFRS consume during training compared to the baselines? How much memory does DYNFRS consume during a stream of mixed requests?
- 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?  
- 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?
- 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.
soundness: 4
strengths: This is a good paper that presents a significant contribution to the unlearning field. 

The 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.

The 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).

Finally, 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.
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.

On 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.
weaknesses: Even though the proposal of the paper is good, the paper presents some weaknesses and unclear points that the authors should address.

**Noteworthy weaknesses**

The 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.

Second, 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.

Finally, 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.

**Minor points**

The 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:
- page 3, line 132, $S, <x, y>)$: $<x, y>$ is missing curly brackets.
- page 3, line 134: $A(S \cup <x, y>)$: $<x, y>$ is missing curly brackets.
- In Section 3.2, $(a^*_u, w^*_u)$ and $p$ are not properly introduced.
- page 5, line 4: $D^n$ has never been defined.
- Page 5, line 142: Is the indicator function missing?
- In Section 4.2., the sentence `Unlike OCC(q)’s reducing work across trees and believing in ensemble, LZY relies on tree structures,
dismantling requests into smaller parts and digesting them through time.` does not make any sense and should be rephrased.

**Update after authors' response**
The 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.

**Arguments for the score**

The 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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See my Weaknesses.
soundness: 2
strengths: 1. The paper presents a comprehensive set of experiments, encompassing various types of unlearning scenarios.

2. The proposed method, DYNFRS, demonstrates significant efficiency improvements compared to existing baselines.
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.
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.

2. The clarity of the paper's writing could be further improved:

- It would be better if some redundant theorems and formulas could be avoided. For instance:

  (a) Theorem 1's conclusion is trivial, especially given the assumptions of sample independence and the splitting characteristics of tree models.

    (b) Lemma 1 is also trivial, since the major difference in the complexity stems from the introduction of $s$ candidates compared to classic methods.

  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.

- Section 4.2 requires a necessary introduction to the lazy tag, particularly since lazy tagging is a classic technique in segment tree problems.

- 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].

3. The experimental section focuses solely on binary classification, neglecting multi-class scenarios. It would be beneficial to consider multi-class problems.

4. *OCC(0.2) sometimes improves the forest's predictive performance.*  Could the authors provide some insights  for  latent reasons?

5. 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.

[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*.

[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.

[3] Zhu, W., Zhang, Z., & Wang, Y. Language Models Represent Beliefs of Self and Others. In *Forty-first International Conference on Machine Learning*.

Meta-review: Summary

The paper introduces an efficient approach to enable machine unlearning in random forests, focusing on speed and maintaining predictive accuracy. It uses a subsampling method, OCC(q), which limits each sample's presence to a subset of trees, simplifying the removal or addition of samples. Additionally, a lazy tag strategy defers the retraining of subtrees until necessary, allowing batched deletions and additions while minimizing computational overhead. The method achieves significant efficiency improvements—up to 1,500,000 times faster—compared to naive retraining, with theoretical guarantees for exact unlearning and time complexity analysis. The efficiency is demonstrated empirically with fast unlearning along with competitive predictive accuracy

Strengths

The paper's strengths lie in its simplicity and effectiveness, achieving substantial efficiency improvements while maintaining predictive accuracy. The method minimizes retraining efforts by limiting the number of trees affected by any update and deferring subtree retraining until necessary, making it particularly suitable for online settings and addition beyond unlearning. The authors provide clear and reasonable motivation, supported by both theoretical proofs and time complexity analysis. Empirical results validate the approach, demonstrating significant efficiency gains.

Weaknesses

The paper has several weaknesses but they were (most) partially addressed in the rebuttal and revisions. Initially, it lacked additional comparison experiments, such as evaluations on multi-class datasets and ablation studies, though these were added later. Space complexity concerns were also addressed in the rebuttal. Presentation clarity was a noted issue, which was reportedly improved in the revisions. However, the paper lacks essential empirical comparisons with other unlearning methods. Additionally, the approach relies on extremely randomized trees rather than general decision trees, raising concerns about its generalizability; while the authors claim any tree type can be used, it remains unclear how performance would compare. The evaluation metrics also require clarification: the paper suggests that post-unlearning performance should match retraining, but the rebuttal's explanation is ambiguous about whether this comparison is with retraining performance or the model's performance prior to unlearning. This ambiguity needs further resolution in future iterations.

Recommendation

The paper is recommended as a poster because, while some reviewers noted that the framework's main components are based on existing methods with minor alterations, the combination of these techniques is novel and enables efficient data addition and sequence handling in unlearning. This combination results in significantly superior performance in efficiency, demonstrating that novel integrations of established methods can yield substantial benefits in the unlearning domain. Despite the limited novelty, the practical efficiency, importance of the problem, and potential applications beyond unlearning justify its acceptance as a poster presentation.

Decision: Accept (Poster)