mlsanityData to 14 Oct 2026

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

arXiv 2605.11617 ↗First posted 12 May 2026cs.LG math.ST stat.THcited by 0

Not on the map. Why?

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.

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

47 of 73 references.

References · 47

  1. 2016Overcoming catastrophic forgetting in neural networkscited by 4,787
  2. 2016Learning without Forgettingcited by 2,496
  3. 2016iCaRL: Incremental Classifier and Representation Learningcited by 2,333
  4. 2017Gradient Episodic Memory for Continual Learningcited by 1,898
  5. 2016Progressive Neural Networkscited by 1,361
  6. 2018Continual Lifelong Learning with Neural Networks: A Reviewcited by 1,330
  7. 2017Continual Learning with Deep Generative Replaycited by 1,158
  8. 2017Memory Aware Synapses: Learning what (not) to forgetcited by 1,105
  9. 2018Experience Replay for Continual Learningcited by 1,095
  10. 2018Efficient Lifelong Learning with A-GEMcited by 1,058
  11. 2021Learning to Prompt for Continual Learningcited by 944
  12. 2020Dark Experience for General Continual Learning: a Strong, Simple Baselinecited by 911
35 more
  1. 2017PackNet: Adding Multiple Tasks to a Single Network by Iterative Pruningcited by 898
  2. 2018Riemannian Walk for Incremental Learning: Understanding Forgetting and Intransigencecited by 742
  3. 2013An Empirical Investigation of Catastrophic Forgetting in Gradient-Based Neural Networkscited by 722
  4. 2017Lifelong Learning with Dynamically Expandable Networkscited by 694
  5. 2022DualPrompt: Complementary Prompting for Rehearsal-free Continual Learningcited by 642
  6. 2019Three scenarios for continual learningcited by 614
  7. 2019Gradient based sample selection for online continual learningcited by 571
  8. 2018Progress & Compress: A scalable framework for continual learningcited by 520
  9. 2022CODA-Prompt: COntinual Decomposed Attention-based Prompting for Rehearsal-Free Continual Learningcited by 450
  10. 2019Online Continual Learning with Maximally Interfered Retrievalcited by 379
  11. 2016Expert Gate: Lifelong Learning with a Network of Expertscited by 372
  12. 2019On Tiny Episodic Memories in Continual Learningcited by 307
  13. 2021Online Continual Learning in Image Classification: An Empirical Surveycited by 245
  14. 2018Selective Experience Replay for Lifelong Learningcited by 241
  15. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 229
  16. 2018Re-evaluating Continual Learning Scenarios: A Categorization and Case for Strong Baselinescited by 228
  17. 2021New Insights on Reducing Abrupt Representation Change in Online Continual Learningcited by 219
  18. 2019REMIND Your Neural Network to Prevent Catastrophic Forgettingcited by 197
  19. 2022FeTrIL: Feature Translation for Exemplar-Free Class-Incremental Learningcited by 121
  20. 2022Self-Sustaining Representation Expansion for Non-Exemplar Class-Incremental Learningcited by 118
  21. 2019Latent Replay for Real-Time Continual Learningcited by 97
  22. 2019Lifelong Machine Learning with Deep Streaming Linear Discriminant Analysiscited by 92
  23. 2023FeCAM: Exploiting the Heterogeneity of Class Distributions in Exemplar-Free Continual Learningcited by 87
  24. 2022ACIL: Analytic Class-Incremental Learning with Absolute Memorization and Privacy Protectioncited by 57
  25. 2013Estimating Continuous Distributions in Bayesian Classifierscited by 54
  26. 2023Real-Time Evaluation in Online Continual Learning: A New Hopecited by 47
  27. 2018Extremely Fast Decision Treecited by 43
  28. 2024GACL: Exemplar-Free Generalized Analytic Continual Learningcited by 22
  29. 2021Class-Incremental Experience Replay for Continual Learning under Concept Driftcited by 17
  30. 2023Prediction Error-based Classification for Class-Incremental Learningcited by 14
  31. 2016Optimal Quantile Approximation in Streamscited by 12
  32. 2021Continual Learning for Unsupervised Anomaly Detection in Continuous Auditing of Financial Accounting Datacited by 7
  33. 2024Overcoming Catastrophic Forgetting in Tabular Data Classification: A Pseudorehearsal-based approachcited by 5
  34. 2024Online Learning of Decision Trees with Thompson Samplingcited by 3
  35. 2025Continual Contrastive Learning on Tabular Data with Out of Distributioncited by 2

Built on by

Not cited yet.