Sparse Forest: Efficient Online Learning and Unlearning Framework for Tree Ensembles

Evolving data and limited computational resources pose two coupled challenges for deploying machine learning system in reality. Online learning and unlearning enable models to incorporate new observations and remove obsolete records, while the computational efficiency of tree ensembles makes them attractive for resource-constrained deployment. However, inexpensive training and inference do not imply inexpensive maintenance: a single sample insertion or deletion can trigger costly whole tree reconstruction. We introduce *Sparse Forest* that addresses this bottleneck through three complementary forms of sparsity. *Structural sparsity* limits the complexity of the maintained trees, reducing the fundamental cost of node statistics updates. *Reconstruction sparsity* prunes the reconstruction through in-place subtree repair, reusing existing descendants and propagating changes in sample membership. *Split-change sparsity* reduces the frequency of structural changes by retaining satisfactory splits under a controlled suboptimality tolerance. Together, these principles control how much structure must be maintained, how much work each repair requires, and how often repairs necessiates. By formalizing $(\epsilon ,\phi )$-suboptimality for tree ensembles, Sparse Forest makes exactness an explicit, configurable property rather than a fixed design choice. At $\epsilon =0$, Sparse Forest maintains a model that is *bit-identical* to retraining from scratch on the updated dataset. To our knowledge, this is the first such guarantee for online learning and unlearning in tree ensembles, going beyong equality in distribution. Relaxing this condition ($\epsilon >0$) trades retraining equivalence for substantially fewer structural changes at negligible accuracy cost. Experiments demonstrate orders-of-magnitude speedups over the state-of-the-art online learning and unlearning baseline, establishing Sparse Forest as a practical alternative for real-world deployment.