Online Gradient Boosting Decision Tree: In-Place Updates for Adding/Deleting Data

W4: We will address all these writing issues in the revised paper.

 

Thank you for your feedback. We would like to emphasize that Section 4.3, 4.4, 4.6 and 4.7 are not repetitive:

• Section 4.3 Test Error Rate: The goal of this experiment is to validate the accuracy of the trained model and the model after performing incremental and decremental learning.
• Section 4.4 Batch Addition & Removal: Unlike Section 4.3, which performs a one-time incremental/decremental learning, this experiment demonstrates that our method supports continual incremental/decremental learning. This capability is crucial for tasks involving datasets where the data or distribution may change over time.
• Section 4.6 Verifying by Backdoor Attacking: In this experiment, unlike previous experiments where data samples are randomly selected, we verify that our method can add or remove specific data samples, such as poisoned (backdoor) data, which are not randomly chosen from the dataset.
• Section 4.7 Verifying by Membership Inference Attack: This experiment provides a different perspective to confirm that data can be successfully deleted and added back.

Our paper includes extensive experiments, and we will strive to make these sections clearer for readers. We will add this clarification in our revised paper and consider reorganizing the experimental sections if necessary.

 

Thank you once again for your feedback. If you have any remaining concerns, please don't hesitate to let us know. We are more than happy to address and clarify them.

 

[1] Grinsztajn, Léo, Edouard Oyallon, and Gaël Varoquaux. "Why do tree-based models still outperform deep learning on typical tabular data?." Advances in neural information processing systems 35 (2022): 507-520.

[2] Shwartz-Ziv, Ravid, and Amitai Armon. "Tabular data: Deep learning is not all you need." Information Fusion 81 (2022): 84-90.

[3] McElfresh, Duncan, et al. "When do neural nets outperform boosted trees on tabular data?." Advances in Neural Information Processing Systems 36 (2024).

[4] Zoppi, Tommaso, Stefano Gazzini, and Andrea Ceccarelli. "Anomaly-based error and intrusion detection in tabular data: No DNN outperforms tree-based classifiers." Future Generation Computer Systems 160 (2024): 951-965.

[5] Gorishniy, Yury, et al. "Revisiting deep learning models for tabular data." Advances in Neural Information Processing Systems 34 (2021): 18932-18943.

[6] Štrumbelj, Erik, and Igor Kononenko. "Explaining prediction models and individual predictions with feature contributions." Knowledge and information systems 41 (2014): 647-665.

[7] Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. "" Why should i trust you?" Explaining the predictions of any classifier." Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 2016.

[8] Lipovetsky, Stan, and Michael Conklin. "Analysis of regression in game theory approach." Applied stochastic models in business and industry 17.4 (2001): 319-330.

[9] Konstantinov, Andrei V., and Lev V. Utkin. "Interpretable machine learning with an ensemble of gradient boosting machines." Knowledge-Based Systems 222 (2021): 106993.

[10] Delgado-Panadero, Ángel, et al. "Implementing local-explainability in gradient boosting trees: feature contribution." Information Sciences 589 (2022): 199-212.

[11] Blockeel, Hendrik, et al. "Decision trees: from efficient prediction to responsible AI." Frontiers in Artificial Intelligence 6 (2023): 1124553.

[12] Lundberg, Scott M. and Su-In Lee. “A Unified Approach to Interpreting Model Predictions.” Neural Information Processing Systems (2017).

[13] Aburass, Sanad, and Osama Dorgham. "Performance Evaluation of Swin Vision Transformer Model using Gradient Accumulation Optimization Technique." Proceedings of the Future Technologies Conference. Cham: Springer Nature Switzerland, 2023.

[14] Hermans, Joeri R., Gerasimos Spanakis, and Rico Möckel. "Accumulated gradient normalization." Asian Conference on Machine Learning. PMLR, 2017.

[15] Lin, Yujun, Song Han, Huizi Mao, Yu Wang and William J. Dally. "Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training." International Conference on Learning Representations, ICLR, 2018.

Thank you very much for your valuable feedback. Here are our responses that could hopefully address your concerns.

 

W1: Thank you for pointing it out. We appreciate the opportunity to clarify the motivation for our research. There is substantial evidence supporting the claim that GBDT can outperform deep learning models in certain tasks, particularly those involving tabular data. For example, studies [1, 2, 3, 4, 5] demonstrate scenarios where GBDT achieves superior accuracy due to its inherent ability to handle heterogeneity and sparsity in data more effectively than neural networks.

Furthermore, GBDT models offer significant advantages in interpretability. Their structured, rule-based nature facilitates straightforward analysis, making them inherently more transparent compared to the often opaque nature of deep learning models. This transparency is further enhanced by the compatibility of GBDT with advanced interpretability tools such as SHAP (SHapley Additive exPlanations) [12] and LIME (Local Interpretable Model-agnostic Explanations) [7], which provide actionable insights into feature importance and model decision-making [6, 8, 9, 10, 11].

We will expand the motivation section in our revised paper to include these points. We sincerely thank you for bringing this to our attention.

W2:

• Our method provides a unified in-place update mechanism for adding and deleting data in GBDT. To the best of our knowledge, this is the first method to support both incremental and decremental learning for GBDT. Conventional GBDT requires loading the entire dataset during the training process and does not permit adding or deleting data after training. Even existing online GBDT methods only support adding new data to the model but do not allow data deletion. This highlights the novelty of our method.
• Section 2.3 provides an overview of our framework, while Section 3.1 delves into the detailed implementation of updating the model without touching the training data. However, due to page limitations, the detailed implementation is included in Appendix E. We will add a clarification to this section. Thank you for pointing it out.
• We would like to argue that these optimizations are not minor innovations. For instance, we propose an adaptive lazy update inspired by gradient accumulation in deep learning. However, unlike gradient accumulation in deep learning, which introduces a new hyperparameter -- the number of accumulation steps [13, 14, 15] -- our adaptive lazy update does not introduce any hyperparameters. We confirm its effectiveness in Appendix K. Similarly, we present split candidate sampling and split robustness tolerance based on our observations as mentioned in the paper. We provide the motivation for the presented optimizations (Section 3, Appendices C and E), theoretical proof of the relationships among these optimizations (Definitions 1 and 2, Appendix D), performance gains achieved through these optimizations (Appendices F, I, J), and comprehensive experiments on their impact (Appendix K). Together, these demonstrate that our optimizations substantially improve efficiency while maintaining the model's performance.

W3: We agree that the discussion on hyperparameters $\sigma$ and $\alpha$ is important. However, due to the extensive experiments included in our paper and the page limitations of the conference, we report the ablation study in Appendix K. This study covers (1) the size of the online dataset $|D'|$, (2) the split random sample rate $\alpha$, (3) the split robustness tolerance $\sigma$, (4) the number of bins $B$, and (5) the number of leaves $J$. We will add a discussion in the main content to highlight the significance of hyperparameters $\sigma$ and $\alpha$ and inform readers about the comprehensive experiments detailed in Appendix K.

Thank you for your reply. We sincerely appreciate your valuable feedback and want to express our gratitude for your dedication. We understand that reviewing a paper in an unfamiliar field requires substantial time and effort. We are happy to engage in further discussion with you and will do our best to address all your concerns.

We would like to clarify that we will reorganized the ablation study on the key parameters you highlighted to the main text, while moving some of the other experiments to the appendix to better manage page space.

For split candidate sampling, similar to the other sampling methods used on GBDT to enhance model performance, reduce overfitting, and improve computational efficiency [1, 2, 3], such as data sampling, feature sampling, one-side sampling, etc., our split candidate sampling is specifically designed to enhance computational efficiency while maintaining model performance. As shown in Figure 6 of the paper, varying the sampling rate yields a substantial speedup in online learning, with rates decreasing from 100% to 5% while maintaining identical performance. We also provide theoretical analyses in Definitions 1 and 2 to explain how split candidate sampling affects the robustness of the best split. To gain a deeper understanding of split candidate sampling, we conducted an experiment combining it with feature sampling, as both methods aim to reduce the number of splits. We report the impact of different feature sampling (10%, 20%, 50%, 100%) and split sampling (10%, 100%) on incremental learning (Add 1%) in Table R1. This table demonstrate that lower feature sampling rates result in faster training and incremental learning but with higher error rates. Conversely, lower split sampling rates achieve faster speeds with comparable error rates. Using 50% feature sampling and 10% split sampling strikes a good balance between speed and accuracy. All of these results shows that, our split candidate sampling in online learning is effective and efficient.

We sincerely appreciate you effort and time on reviewing our work. If you have any specific concerns or have identified particular limitations, please do let us know. We are more than happy to conduct further experiments or analyses to address them, as we believe this will not only strengthen our paper but also provide more depth and value to our readers.

Thank you once again for your time and for engaging in this discussion with us. Your input is invaluable, and we look forward to hearing your further suggestions and comments.

[1] Chen, Tianqi, and Carlos Guestrin. "Xgboost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. 2016.

[2] Ke, Guolin, et al. "Lightgbm: A highly efficient gradient boosting decision tree." Advances in neural information processing systems 30 (2017).

[3] Han, Cuize, et al. "Scalable feature selection for (multitask) gradient boosted trees." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

Table R1. The impact of different levels of feature sampling (10%, 20%, 50%, 100%) and split sampling (10%, 100%) on adding 1% of dataset.

(Total Training Time (s) / Total Incremental Learning Time (s) / Error Rate)

Thank you again for your valuable feedback on our paper. Inspired by the comment from Reviewer PGvm, we would like to provide additional motivation for our online GBDT to offer deeper insights into its importance. GBDT has been widely used in industry for applications, such as recommender systems and fraud detection. However, in dynamic and real-time applications where data distributions change frequently, traditional GBDT models require retraining from scratch whenever the dataset changes, which is computationally expensive and inefficient for real-time applications. Furthermore, although prior works have introduced either incremental or decremental learning methods (the baselines in our paper), they often neglect efficiency and do not handle both incremental and decremental learning simultaneously. To the best of our knowledge, our framework is the first to propose an efficient online GBDT supporting both incremental and decremental learning, making it ideal for scenarios where data distribution changes rapidly. Here are some practical examples that highlight the need for our framework:

1. Real-Time Fraud Detection: For Online payment platforms or banking systems, when new transactions occur, our method can incrementally learn patterns from the new data without retraining the model from scratch. Additionally, outdated data, such as older fraud patterns, may become irrelevant, and our method can remove them to improve accuracy and efficiency.
2. Stock Market Prediction: Financial markets generate new data continuously (e.g., prices, volumes, and news). Our method can incrementally learn these new trends in real time, keeping predictions up to date.
3. Dynamic Recommender Systems: User behaviors evolve constantly. When users produce new interactions, our model can incrementally learn these behaviors in real time, enabling personalized recommendations that reflect the most recent data.
4. Data Deletion Compliance: Decremental learning is particularly relevant for complying with regulations like GDPR (General Data Protection Regulation) and CCPA (California Consumer Privacy Act), which mandate the "right to be forgotten." When users request their data to be removed, our method can perform decremental learning to delete their data from the model in real time without retraining.
5. Secure Federated Learning: In federated GBDTs, participants may withdraw their data contributions. Our method allows this data to be removed in real time without retraining, ensuring both efficiency and privacy.

These examples highlight the critical need for efficient online GBDTs in industrial applications handling with dynamic data. We will include these clarifications into our revised paper. Thank you again for bringing this to our attention. Please let us know if you have any further concerns, we would be more than happy to address them.

Thank you so much for your constructive feedback and support for our work. We deeply value your insightful comments. Here are our response to your questions:

 

W1: We agree that the parameters of our method require careful tuning. To address this, we include a comprehensive ablation study in Appendix K. Additionally, we recommend settings such as $\alpha = 0.1$ and $\sigma = 0.1$, which provide substantial speedup for both incremental and decremental learning while maintaining the model's performance. Depending on the specific requirements of a task, $\alpha$ and $\sigma$ can be adjusted accordingly. Both parameters exhibit the same behavior: smaller values result in faster processing, but at the cost of reduced performance. We will include this discussion in the revised paper. Thank you for highlighting this point.

W2: To confirm the performance of our methods on real-world datasets with varying data distributions, we conducted experiments on two time series datasets: (1) GlobalTemperatures [1]: This dataset records the average land temperatures from 1750 to 2015. (2) WebTraffic [2]: This dataset tracks hourly web requests to a single website over a span of five months.

For this experiment, we constructed the input data $X$ using the time series values from the previous 15 time steps, with the goal of predicting the corresponding output value $y$. Initially, we randomly sample 10% of the data as the test dataset, with the remaining 90% used as the training dataset. Similar to Section 4.4, we evenly divided the training data into 10 subsets, each containing 10% of the training samples. It is important to note that we did not shuffle these time series datasets, meaning the 10 subsets were arranged sequentially from older to more recent data. We trained an initial model using the first subset, then incrementally added each subsequent subset one by one. After incorporating all training data, we sequentially removed each subset in reverse order. As expected, since the test dataset spans all time steps, the error rate decreases as more subsets are added to the model. This is because the model learns the updated distribution from the newly added subsets. After removing each subset, the error rate increases, reflecting the loss of information associated with the removed data and the model's adjustment to the remaining subsets. As shown in Table R1, these results confirm the effectiveness of our method in adapting to changing data distributions.

Table R1. Error rate after every online learning step.

W3: Thank you for pointing it out. We will resize the tables to improve clarity and fix all minor issues in the revised paper.

Q1: Yes, we first train a model offline, recording the time consumption and memory usage during the training process. Subsequently, we perform incremental learning and decremental learning, recording their respective time consumption.

Q2: For the task under rapidly changing data distributions, we consider two scenarios: (1) Immediate Updates: The model requires updates after every incoming data sample to maintain optimal performance in real-time. In this scenario, our method is substantially faster than retraining the model from scratch. (2) Batch Updates: The model can wait and accumulate a batch of data samples before performing an update. In this scenario, our method supports batch updates and remains substantially faster than retraining the model from scratch, even when adding or removing 1% of the data samples. It is important to note that, unlike conventional online learning, the updates in this context can involve either adding or removing data.

 

Thanks again for your valuable comments. We truly appreciate your detailed feedback.

 

[1] GlobalTemperatures: https://www.kaggle.com/datasets/berkeleyearth/climate-change-earth-surface-temperature-data?resource=download&select=GlobalTemperatures.csv

[2] WebTraffic: https://www.kaggle.com/datasets/raminhuseyn/web-traffic-time-series-dataset

Q1: Thank you for your insightful question. We outline the key differences between our method and the previous method [1] as follows:

1. Different Target: To the best of our knowledge, our method is the first to consider in-place updates for both adding and removing data. The previous method [1] is similar to other online methods [2, 3], focusing solely on adding new data to the model without supporting data deletion. However, the distribution of datasets in certain tasks can change over time. Simply adding new data to adapt to a new distribution is often insufficient; it may also require the removal of outdated data to maintain accuracy and relevance.

2. Different Setting: Our method emphasizes updating models dynamically by adding or removing data, whereas method [1] addresses data imbalance by extending batch-mode algorithms like bagging and boosting to their online cost-sensitive versions, handling class imbalances in streaming data.

3. Complexity and Practical Implications: Our method incorporates several optimizations to reduce computational costs while maintaining high accuracy, making it scalable for large datasets. In contrast, method [1] may face scalability challenges due to the repetitive resampling and retraining of models with updated weight distributions.

In summary, our method is more scalable and efficient, enabling seamless updates to trained models through incremental and decremental learning for both adding and removing data. We will include this discussion in the revised paper.

Q2: Thank you for your question. As shown in Table 4 (in paper), after initial training across 10 datasets, our method achieves the best error rate on two datasets (CreditInfo and Pendigits) and obtains the second-best error rate on five datasets (Adult, HIGGS, Optdigits, Letter, and Abalone). Additionally, our experiments reveal that no single method achieves the best error rate across all datasets. To provide a comparative measure, we calculate the mean absolute error (MAE) relative to the best error rate for each method: $\text{MAE}\_{\text{method}} = \frac{\sum_\text{datasets} \text{Error Rate}_\text{dataset} - \text{Best Error on Dataset}}{\text{Number of Datasets}}$ as presented in Table R5. Our Method achieves the lowest MAE of 0.0028, demonstrating our method's superior performance and robustness relative to the other methods across the tested datasets.

Table R5. Mean absolute error (MAE) relative to the best error rate for each method: $\text{MAE}\_{\text{method}} = \frac{\sum_\text{datasets} \text{Error Rate}_\text{dataset} - \text{Best Error on Dataset}}{\text{Number of Datasets}}$.

Q3: We agree that parameter sensitivity analysis is crucial for understanding performance under different parameter settings. We have included a comprehensive ablation study on various settings in Appendix K.

• Split Random Sampling: Split random sampling is designed to reduce the frequency of retraining by limiting the number of splits. A smaller sampling rate, $\alpha$, results in more stable splits, leading to fewer nodes requiring retraining and shorter online learning times. While accuracy remains largely unaffected, a substantial speedup is observed for $\alpha = 5$ and $10$ across datasets. Therefore, we recommend setting $\alpha = 10$.
• Split Robustness Tolerance: Split robustness tolerance enhances the robustness of splits during online learning. Higher tolerance levels result in faster learning by reducing the need for retraining but come with a trade-off of decreased functional similarity. Based on our findings, we suggest that $\sigma$ should not exceed 0.15.
• Number of Bins: The number of bins has minimal impact on both accuracy and the speed of online learning.
• Number of Leaves: When the number of leaves exceeds 20, accuracy tends to stabilize. Increasing the number of leaves further results in greater acceleration without significant loss of accuracy.
• Size of Online Dataset $|D'|$: Online learning time increases as the size of $|D'|$ grows.

We will provide clearer clarifications and explanations regarding our ablation study in the revised paper. Thank you for highlighting this point.

 

Thank you again for your detailed feedback. We greatly appreciate your valuable insights.

 

[1] B. Wang and J. Pineau, “Online Bagging and Boosting for Imbalanced Data Streams,” in IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 12, pp. 3353-3366.

[2] Leistner, Christian, et al. "On robustness of on-line boosting-a competitive study." 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops. IEEE, 2009.

[3] Zhang, Chongsheng, et al. "On incremental learning for gradient boosting decision trees." Neural Processing Letters 50 (2019): 957-987.

Table R3. The Total training, incremental or decremental learning time (in seconds).

 

Table R4. Accuracy for clean test dataset and attack successful rate for backdoor test dataset. (Section 4.6)

W2: Thank you. We agree that the number of base learners is important in practical applications. We provide additional results for different numbers of base learners in Tables R2 and R3. Table R2 reports the test error rate after training, adding, and deleting base learners in GBDT models with varying iterations, demonstrating that our method achieves a comparable error rate across different iterations. Table R3 shows the time consumption for incremental and decremental learning, illustrating that our methods are substantially faster than retraining a model from scratch, particularly in cases where a single data sample is added or deleted.

Additionally, to confirm that our method can effectively add and delete data samples across various iterations, we report results on backdoor attacks for different iterations, as shown in Table R4. These results confirm that our method successfully adds and removes data samples from the model across different numbers of iterations. We will include these experiments in the revised paper. Thank you for your helpful suggestions.

Table R2. The test error rate after training, adding and deleting on GDBT models with various iterations.

Thank you very much for your insightful comments and support of our work. We truly appreciate your valuable feedback. Here are our responses to your questions:

 

W1: We compare the time complexity of retraining from scratch and our online learning approach in Table R1. Training a tree involves three key steps: Derivatives Computing, Gain Computing & Split Finding, and Prediction Computing. Let $B$ represent the number of bins, $J$ the number of leaves, $|D_{tr}|$ the number of training data points, and $|D'|$ the number of online learning data points ($|D'| \ll |D_{tr}|$).

• Derivatives Computing: in retraining, each point is assigned to one of the $B$ bins, which take $O(\|D_{tr}\|)$ time. In our method, we optimize updates without touching training data, directly adding or subtracting derivatives for the online data points, which takes $O(\|D'\|)$ time.
• Gain Computing & Split Finding: in training, to identify the optimal split for each node, we compute the potential split gains for each bin. As a binary tree is constructed with $2J - 1$ nodes, the total computational complexity for split finding across the entire tree is $O(B(2J - 1)) = O(BJ)$. In our approach, Split Candidates Sampling reduces the number of split candidates from $B$ to $\alpha B$, where $\alpha$ denotes the split sample rate ($0 < \alpha \leq 1$). Additionally, let $P_\sigma$ represent the probability of a split change being within the robustness tolerance, indicating the likelihood that a node does not require retraining (with larger $\sigma$, $P_\sigma$ increases). If retraining is not required, the time complexity for checking a node is $O(|D'|)$. Conversely, if retraining is required, the complexity to retrain a node is $O(\alpha B)$. Consequently, the total time complexity for the entire tree is $O(J|D'| \cdot P_\sigma + J\alpha B \cdot (1-P_\sigma))$. For $P_\sigma \rightarrow 1$, no nodes require retraining, simplifying the complexity to $O(J|D'|)$. Conversely, for $P_\sigma \rightarrow 0$, all nodes require retraining, and the complexity becomes $O(J\alpha B)$.
• Predicted Value Computing: during training, after the tree is built, the predicted value for each leaf is updated. This involves traversing the leaf for the data points that reach it, with the total number being equivalent to all training data points, resulting in a complexity of $O(|D_{tr}|)$. In our method, We update the predicted value only for leaves reached by at least one online data point, and adjust by adding or subtracting the impact of these online data points, resulting in a complexity of $O(|D'|)$.

We present the time complexity comparison in Table R1 and will include this discussion in our revised paper. Thank you for bringing this to our attention.

 

Table R1. Time complexity comparison between retraining and online learning.