HedgeCut: Maintaining Randomised Trees for Low-Latency Machine Unlearning
Open accessAbstract
Software systems that learn from user data with machine learning (ML) have become ubiquitous over the last years. Recent law such as the "General Data Protection Regulation" (GDPR) requires organisations that process personal data to delete user data upon request (enacting the "right to be forgotten"). However, this regulation does not only require the deletion of user data from databases, but also applies to ML models that have been learned from the stored data. We therefore argue that ML applications should offer users to unlearn their data from trained models in a timely manner. We explore how fast this unlearning can be done under the constraints imposed by real world deployments, and introduce the problem of low-latency machine unlearning: maintaining a deployed ML model in-place under the removal of a small fraction of training samples without retraining.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the case of unlearning a training sample, HedgeCut will not revise robust splits but will update those leaf statistics.
“In the case of unlearning a training sample, HedgeCut will not revise robust splits but will update those leaf statistics.”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
Schelter et al. [57] proposed Hedgecut, a classification model based on extremely randomized trees (ERTs).
“To improve the efficiency of the unlearning process for tree-based machine learning models, Schelter et al. [57] proposed Hedgecut , a classification model based on extremely randomized trees (ERTs) [100].”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
A robust split indicates that the subtree's structure will not change after unlearning a small number of samples, while for non-robust splits, the structure may be changed.
“A robust split indicates that the subtree's structure will not change after unlearning a small number of samples, while for non-robust splits, the structure may be changed.”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
For non-robust splits, HedgeCut recomputes the split criterion of the maintained subtree variants, which were previously kept inactive, and selects a subtree variant as a new non-robust split of the current model.
“For non-robust splits, HedgeCut recomputes the split criterion of the maintained subtree variants, which were previously kept inactive, and selects a subtree variant as a new non-robust split of the current model.”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
In Hedgecut, during the training process, the tree model is divided into robust splits and non-robust splits based on the proposed robustness quantification factor.
“First, during the training process, the tree model is divided into robust splits Request and non-robust splits based on the proposed robustness quantification factor.”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
Schelter et al. [57], Brophy et al. [58], and Wu et al. [60] only provide evaluations in terms of runtime and accuracy, and they do not provide reasonable experimental or theoretical verifiability guarantees of their unlearning processes.
“Schelter et al. [57], Brophy et al. [58], and Wu et al. [60] only provide evaluations in terms of runtime and accuracy, and they do not provide reasonable experimental or theoretical verifiability guarantees of their unlearning processes.”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
The above two schemes (Hedgecut and DaRE) need to compute a large number of possible tree structures in advance, which would cost a large number of storage resources.
“The above two schemes need to compute a large number of possible tree structures in advance, which would cost a large number of storage resources [57, 58].”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
They do not consider the security of this intermediate information and whether an attack would recover any information about the unlearned samples.
“However, they do not consider the security of this intermediate information and whether an attack would recover any information about the unlearned samples [30, 57].”
From Machine Unlearning: A Survey (2024) · cites this paper as [57]
Cites
Breiman, L. (2001) · Machine Learning · doi:10.1023/a:1010933404324 · Cited by 133,538 · see citing works
XGBoost: A Scalable Tree Boosting System
Chen, T., & Guestrin, C. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939785 · Cited by 54,569 · see citing works
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162 · see citing works
Classification and Regression Trees.
Ryzin, J. V., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1986) · Journal of the American Statistical Association · doi:10.2307/2288003 · Cited by 21,028 · see citing works
Geurts, P., Ernst, D., & Wehenkel, L. (2006) · Machine Learning · doi:10.1007/s10994-006-6226-1 · Cited by 9,300 · see citing works
Scikit-learn: Machine Learning in Python
(2011) · Journal of Machine Learning Research · doi:10.5555/1953048.2078195 · Cited by 8,539 · see citing works
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272 · see citing works
The Elements of Statistical Learning
Hastie, T. J., Tibshirani, R. J., & Friedman, J. H. (2009) · Springer series in statistics · doi:10.1007/b94608 · Cited by 4,111 · see citing works
Mining time-changing data streams
Hulten, G., Spencer, L. A., & Domingos, P. (2001) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502529 · Cited by 1,784 · see citing works
Incremental and Decremental Support Vector Machine Learning
Cauwenberghs, G., & Poggio, T. (2000) · Cited by 1,156 · see citing works
(2015) · neural information processing systems · Cited by 912 · see citing works
Theoretical Comparison between the Gini Index and Information Gain Criteria
Raileanu, L. E., & Stoffel, K. (2004) · Annals of Mathematics and Artificial Intelligence · doi:10.1023/b:amai.0000018580.96245.c6 · Cited by 649 · see citing works
Maintenance of Materialized Views: Problems, Techniques, and Applications
Gupta, A. K., & Mumick, I. S. (1999) · The MIT Press eBooks · doi:10.7551/mitpress/4472.003.0016 · Cited by 644 · see citing works
Towards Making Systems Forget with Machine Unlearning
Cao, Y., & Yang, J. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.35 · Cited by 622 · see citing works
MonetDB/X100: Hyper-Pipelining Query Execution
Boncz, P. A., Żukowski, M., & Nes, N. J. (2005) · Data Archiving and Networked Services (DANS) · Cited by 484 · see citing works
Decision Tree Induction Based on Efficient Tree Restructuring
Utgoff, P. E., Berkman, N. C., & Clouse, J. A. (1997) · Machine Learning · doi:10.1023/a:1007413323501 · Cited by 361 · see citing works
DeltaGrad: Rapid retraining of machine learning modelsPreprint
Wu, Y., Dobriban, E., & Davidson, S. (2020) · International Conference on Machine Learning · doi:10.48550/arxiv.2006.14755 · Cited by 278 · see citing works
Implementing database operations using SIMD instructions
Zhou, J., & Ross, K. A. (2002) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/564691.564709 · Cited by 246 · see citing works
Data Lifecycle Challenges in Production Machine Learning: A Survey
Polyzotis, N., Roy, S., Whang, S. E., & Zinkevich, M. (2018) · ACM SIGMOD Record · doi:10.1145/3299887.3299891 · Cited by 214 · see citing works
Multiple Incremental Decremental Learning of Support Vector Machines
Karasuyama, M., & Takeuchi, I. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2010.2048039 · Cited by 176 · see citing works
On Challenges in Machine Learning Model Management
Schelter, S., Bießmann, F., Januschowski, T., Salinas, D., Seufert, S., & Szarvas, G. (2015) · IEEE Data(base) Engineering Bulletin · Cited by 139 · see citing works
Self-citationProbabilistic demand forecasting at scale
Böse, J.-H., Flunkert, V., Gasthaus, J. A., Januschowski, T., Lange, D., Salinas, D., Schelter, S., Seeger, M., & Wang, Y. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3137765.3137775 · Cited by 126 · see citing works
Self-citationDescent-to-Delete: Gradient-Based Methods for Machine Unlearning
Neel, S., Roth, A., & Sharifi-Malvajerdi, S. (2020) · arXiv · doi:10.48550/arxiv.2007.02923 · Cited by 96 · see citing works
Instability of decision tree classification algorithms
Li, R.-H., & Belford, G. G. (2002) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/775047.775131 · Cited by 93 · see citing works
Stoyanovich, J., Howe, B., & Jagadish, H. V. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3415478.3415570 · Cited by 82 · see citing works
Runtime Optimizations for Tree-Based Machine Learning Models
Asadi, N., Lin, J., & de Vries, A. P. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.73 · Cited by 73 · see citing works
Decision trees and transient stability of electric power systems
Wehenkel, L. A., & Pavella, M. (1991) · Automatica · doi:10.1016/0005-1098(91)90010-y · Cited by 69 · see citing works
Everything you always wanted to know about compiled and vectorized queries but were afraid to ask
Kersten, T., Leis, V., Kemper, A., et al. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3275366.3275370 · Cited by 39 · see citing works
Classification and Regression Trees
Gehrke, J. E. (2011) · IGI Global eBooks · doi:10.4018/9781605660103.ch031 · Cited by 29 · see citing works
Ye, T., Zhou, H., Zou, W. Y., et al. (2018) · ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD) · doi:10.1145/3219819.3219857 · Cited by 25 · see citing works
"Amnesia" - Machine Learning Models That Can Forget User Data Very Fast.
Schelter, S. (2020) · Conference on Innovative Data Systems Research · Cited by 14 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining
Liu, Y., Xu, L., Yuan, X., Wang, C., & Li, B. (2022) · IEEE INFOCOM 2022 - IEEE Conference on Computer Communications · doi:10.1109/infocom48880.2022.9796721 · Cited by 202 · see citing works
Xu, H., Zhu, T., Zhang, L., Zhou, W., & Yu, P. S. (2024) · ACM Computing Surveys · doi:10.1145/3603620 · Cited by 164 · see citing works
“However, they do not consider the security of this intermediate information and whether an attack would recover any information about the unlearned samples [30, 57].”
BackgroundMethodInfluentialHard to Forget: Poisoning Attacks on Certified Machine Unlearning
Marchant, N. G., Rubinstein, B. I. P., & Alfeld, S. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i7.20736 · Cited by 64 · see citing works
“Examples of such models include ensembles of randomized decision trees (Schelter, Grafberger, and Dunning, 2021), variants of 𝑘 -means clustering (Ginart et al., 2019), and a modeling framework called SISA that takes advantage of data sharding and caching (Bourtoule et al., 2021).”
A Survey of Machine Unlearning
Nguyen, T. T., Huynh, T. T., Ren, Z., Nguyen, P. L., Liew, A. W.-C., Yin, H., & Nguyen, Q. V. H. (2022) · arXiv · doi:10.48550/arxiv.2209.02299 · Cited by 193 · see citing works
“[132] proposed an unlearning solution for extremely randomized trees by measuring the robustness of the split decisions.”
InfluentialPatient Similarity Learning with Selective Forgetting
Qian, W., Zhao, C., Shao, H., Chen, M., Wang, F., & Huai, M. (2022) · 2022 IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm55620.2022.9995016 · Cited by 11 · see citing works
Making Recommender Systems Forget: Learning and Unlearning for Erasable Recommendation
Li, Y., Zheng, X., Chen, C., & Liu, J. (2022) · arXiv · doi:10.48550/arxiv.2203.11491 · Cited by 43 · see citing works
“To overcome the issue of inefficiency, two classes of MU methods, i.e., retrain unlearning and reverse unlearning, have been proposed [Bourtoule et al., 2021; Schelter et al., 2021; Sekhari et al., 2021].”
BackgroundMethod
- Authors
- Schelter, S., Grafberger, S., & Dunning, T.
- Affiliations
- University of Amsterdam (NL)
- Hewlett-Packard (United States) (US)
- Venue
- Proceedings of the 2021 International Conference on Management of Data
- Publisher
- ACM
- Published
- 2021-06-09
- Pages
- 1545-1557
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W3176739818
- Cited by
- 89
- References
- 31
- Citations by year
- 2026: 13 · 2025: 27 · 2024: 19 · 2023: 19 · 2022: 9 · 2021: 1 · 2020: 1
- FWCI
- 5.50
- Type
- conference paper
- Language
- en
- Open access
- green
- handle.uba.uva.nl
- Locations
- ACM SIGMOD International Conference on Management of Data (SIGMOD) (publishedVersion)
- UvA-DARE (University of Amsterdam) (submittedVersion, other-oa)
- Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Keywords
- machine unlearning, right to be forgotten, GDPR, data deletion, privacy-preserving machine learning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
