# Shrub Ensembles for Online Classification

arXiv: https://arxiv.org/abs/2112.03723 · HTML: https://mlsanity.com/paper/2112.03723/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 58 references that are in the map.
- First posted on arXiv 7 Dec 2021.

## Builds on (most cited first, 10 of 10)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Distilling a Neural Network Into a Soft Decision Tree](https://mlsanity.com/paper/1711.09784/) (2017)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Adaptive Neural Trees](https://mlsanity.com/paper/1807.06699/) (2018)
- [Extremely Fast Decision Tree](https://mlsanity.com/paper/1802.08780/) (2018)
- [Deep Regression Forests for Age Estimation](https://mlsanity.com/paper/1712.07195/) (2017)
- [Neural Random Forests](https://mlsanity.com/paper/1604.07143/) (2016)
- [Online Gradient Boosting](https://mlsanity.com/paper/1506.04820/) (2015)
- [Dropout Regularization in Hierarchical Mixture of Experts](https://mlsanity.com/paper/1812.10158/) (2018)

## Built on by (most cited first, 1 of 1)

- [Lift What You Can: Green Online Learning with Heterogeneous Ensembles](https://mlsanity.com/paper/2509.18962/) (2025)

## Abstract (arXiv)

Online learning algorithms have become a ubiquitous tool in the machine learning toolbox and are frequently used in small, resource-constraint environments. Among the most successful online learning methods are Decision Tree (DT) ensembles. DT ensembles provide excellent performance while adapting to changes in the data, but they are not resource efficient. Incremental tree learners keep adding new nodes to the tree but never remove old ones increasing the memory consumption over time. Gradient-based tree learning, on the other hand, requires the computation of gradients over the entire tree which is costly for even moderately sized trees. In this paper, we propose a novel memory-efficient online classification ensemble called shrub ensembles for resource-constraint systems. Our algorithm trains small to medium-sized decision trees on small windows and uses stochastic proximal gradient descent to learn the ensemble weights of these `shrubs'. We provide a theoretical analysis of our algorithm and include an extensive discussion on the behavior of our approach in the online setting. In a series of 2~959 experiments on 12 different datasets, we compare our method against 8 state-of-the-art methods. Our Shrub Ensembles retain an excellent performance even when only little memory is available. We show that SE offers a better accuracy-memory trade-off in 7 of 12 cases, while having a statistically significant better performance than most other methods. Our implementation is available under https://github.com/sbuschjaeger/se-online .