# MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 47 of its 73 references that are in the map.
- First posted on arXiv 12 May 2026.

## Builds on (most cited first, 30 of 47)

- [Overcoming catastrophic forgetting in neural networks](https://mlsanity.com/paper/1612.00796/) (2016)
- [Learning without Forgetting](https://mlsanity.com/paper/1606.09282/) (2016)
- [iCaRL: Incremental Classifier and Representation Learning](https://mlsanity.com/paper/1611.07725/) (2016)
- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [Progressive Neural Networks](https://mlsanity.com/paper/1606.04671/) (2016)
- [Continual Lifelong Learning with Neural Networks: A Review](https://mlsanity.com/paper/1802.07569/) (2018)
- [Continual Learning with Deep Generative Replay](https://mlsanity.com/paper/1705.08690/) (2017)
- [Memory Aware Synapses: Learning what (not) to forget](https://mlsanity.com/paper/1711.09601/) (2017)
- [Experience Replay for Continual Learning](https://mlsanity.com/paper/1811.11682/) (2018)
- [Efficient Lifelong Learning with A-GEM](https://mlsanity.com/paper/1812.00420/) (2018)
- [Learning to Prompt for Continual Learning](https://mlsanity.com/paper/2112.08654/) (2021)
- [Dark Experience for General Continual Learning: a Strong, Simple Baseline](https://mlsanity.com/paper/2004.07211/) (2020)
- [PackNet: Adding Multiple Tasks to a Single Network by Iterative Pruning](https://mlsanity.com/paper/1711.05769/) (2017)
- [Riemannian Walk for Incremental Learning: Understanding Forgetting and Intransigence](https://mlsanity.com/paper/1801.10112/) (2018)
- [An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networks](https://mlsanity.com/paper/1312.6211/) (2013)
- [Lifelong Learning with Dynamically Expandable Networks](https://mlsanity.com/paper/1708.01547/) (2017)
- [DualPrompt: Complementary Prompting for Rehearsal-free Continual Learning](https://mlsanity.com/paper/2204.04799/) (2022)
- [Three scenarios for continual learning](https://mlsanity.com/paper/1904.07734/) (2019)
- [Gradient based sample selection for online continual learning](https://mlsanity.com/paper/1903.08671/) (2019)
- [Progress & Compress: A scalable framework for continual learning](https://mlsanity.com/paper/1805.06370/) (2018)
- [CODA-Prompt: COntinual Decomposed Attention-based Prompting for Rehearsal-Free Continual Learning](https://mlsanity.com/paper/2211.13218/) (2022)
- [Online Continual Learning with Maximally Interfered Retrieval](https://mlsanity.com/paper/1908.04742/) (2019)
- [Expert Gate: Lifelong Learning with a Network of Experts](https://mlsanity.com/paper/1611.06194/) (2016)
- [On Tiny Episodic Memories in Continual Learning](https://mlsanity.com/paper/1902.10486/) (2019)
- [Online Continual Learning in Image Classification: An Empirical Survey](https://mlsanity.com/paper/2101.10423/) (2021)
- [Selective Experience Replay for Lifelong Learning](https://mlsanity.com/paper/1802.10269/) (2018)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Re-evaluating Continual Learning Scenarios: A Categorization and Case for Strong Baselines](https://mlsanity.com/paper/1810.12488/) (2018)
- [New Insights on Reducing Abrupt Representation Change in Online Continual Learning](https://mlsanity.com/paper/2104.05025/) (2021)
- [REMIND Your Neural Network to Prevent Catastrophic Forgetting](https://mlsanity.com/paper/1910.02509/) (2019)

## Abstract (arXiv)

Streaming decision trees are natural candidates for open-world continual learning, as they perform local updates, enjoy bounded memory, and static decision boundaries. Despite these, they still fail in online class-incremental learning due to two coupled miscalibrations: (i) their split criterion grows unreliable as the class count K expands, and (ii) the absence of knowledge transfer at split time. Both failures share a common root: the range of Information Gain intrinsically scales with log2 K. Consequently, any Hoeffding-style confidence radius derived from it must inevitably grow with the class count, making a K-independent split criterion structurally impossible, taking away the potential benefits of applying streaming decision trees to continual learning. To fix this issue, we present MIST (McDiarmid Incremental Streaming Tree), which resolves both failures through three integrated components: (i) a tight, K-independent McDiarmid confidence radius for Gini splitting that acts as a structural regulariser; (ii) a Bayesian inheritance protocol that projects parent statistics to child nodes via truncated-Gaussian moments, with variance reduction guarantees strongest precisely when splitting is most conservative; and (iii) per-leaf KLL quantile sketches that support both continuous threshold evaluation and geometry-adaptive leaf prediction from a single data structure. On standard and stress-test tabular streams, MIST is competitive with global parametric methods on near-Gaussian benchmarks and uniquely robust on non-Gaussian geometry where SOTA benchmarks collapse.