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

• URL: http://arxiv.org/abs/2605.11617v2
• Date: Mon, 18 May 2026 14:29:14 GMT
• Title: MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound
• Abstract summary: Streaming decision trees are natural candidates for open-world continual learning.<n>They still fail in online class-incremental learning due to two coupled miscalibrations.<n>We present MIST (McDiarmid Incremental Streaming Tree), which resolves both failures through three integrated components.
• Score: 6.276425555068115
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Learning Auditable Classifier Models: Source-Disjoint Tree Ensembles [0.0]
  Predictive models in clinical and regulated settings must be accurate and fully auditable.<n>We introduce Residual Pattern Tree Ensemble (RPTE), a three-stage learning approach.<n>RPTE builds on three key principles: bounded feature budget, source disjointness, and separate coefficient estimation.
  arXiv  Detail & Related papers  (2026-08-16T12:56:49Z)
• The Art of Not Forgetting A Local Learning Architecture for Continual Learning [0.0]
  We introduce CMP, a continual-learning architecture that repre?sents inputs as sparse relational codes.<n>We investigate whether combining sparse representations, local learning, and persistent memory can reduce catastrophic forgetting.
  arXiv  Detail & Related papers  (2026-07-29T06:42:23Z)
• Conformal Changepoint Localization and Root Cause Analysis with Corrupted Observations [55.76952683833966]
  This paper proposes weighted CONCH (W-CONCH) and weighted CROC (W-CROC) to reduce confidence set size when data may be corrupted.<n>Experiments on image-based and real-world changepoint and root-cause benchmarks show that uncertainty-based weighting substantially reduces confidence set size.
  arXiv  Detail & Related papers  (2026-07-29T05:16:59Z)
• Multimodal Learning on Low-Quality Data with Conformal Predictive Self-Calibration [72.0672328514289]
  Multimodal learning often grapples with the challenge of low-quality data.<n>We propose a unified framework, termed Conformal Predictive Self-Calibration.<n>Our framework consistently outperforms existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-05-05T14:48:52Z)
• Learning from Emptiness: De-biasing Listwise Rerankers with Content-Agnostic Probability Calibration [76.08899010904652]
  CapCal is a training-free framework that mechanically decouples positional bias from ranking decisions.<n>It achieves superior performance among training-free methods while preserving single-pass efficiency.
  arXiv  Detail & Related papers  (2026-04-11T10:47:22Z)
• SCOPE: Semantic Coreset with Orthogonal Projection Embeddings for Federated learning [0.7799711162530713]
  Current ML approaches either require impractical data aggregation or fail due to class imbalance.<n>We introduce SCOPE, a coreset framework for federated data that filters anomalies and adaptively prunes redundant data to long-tail skew.<n>SCOPE yields competitive global accuracy and robust convergence, all while achieving exceptional efficiency with a 128x to 512x reduction in uplink bandwidth.
  arXiv  Detail & Related papers  (2026-03-13T13:24:12Z)
• CIRCUS: Circuit Consensus under Uncertainty via Stability Ensembles [1.3011345529764784]
  We show that CIRCUS produces a threshold-robust "core" circuit while explicitly surfacing contingent alternatives.<n>On Gemma-2-2B and Llama-3.2-1B, strict consensus circuits are 40x smaller than the union of constructs all configurations while retaining comparable influence-flow explanatory power.<n>We further validate causal relevance with activation patching, where consensus-identified nodes consistently beat matched non-consensus controls.
  arXiv  Detail & Related papers  (2026-02-28T07:44:04Z)
• Generalizing GNNs with Tokenized Mixture of Experts [75.8310720413187]
  We show that improving stability requires reducing reliance on shift-sensitive features, leaving an irreducible worst-case generalization floor.<n>We propose STEM-GNN, a pretrain-then-finetune framework with a mixture-of-experts encoder for diverse computation paths.<n>Across nine node, link, and graph benchmarks, STEM-GNN achieves a stronger three-way balance, improving robustness to degree/homophily shifts and to feature/edge corruptions while remaining competitive on clean graphs.
  arXiv  Detail & Related papers  (2026-02-09T22:48:30Z)
• Decision Tree Embedding by Leaf-Means [11.318593165494724]
  Decision Tree Embedding (DTE) is a fast and effective method that leverages the leaf partitions of a trained classification tree to construct an interpretable feature representation.<n>By using the sample means within each leaf region as anchor points, DTE maps inputs into an embedding space defined by the tree's partition structure.<n>We establish several population-level theoretical properties of DTE, including its preservation of conditional density under mild conditions.
  arXiv  Detail & Related papers  (2025-12-01T15:57:33Z)
• DAG DECORation: Continuous Optimization for Structure Learning under Hidden Confounding [0.0]
  We study structure learning for linear Gaussian SEMs in the presence of latent confounding.<n>We propose textscDECOR, a single likelihood-based estimator that jointly learns a DAG and a correlated noise model.
  arXiv  Detail & Related papers  (2025-10-02T15:23:30Z)
• Towards Continual Learning Desiderata via HSIC-Bottleneck Orthogonalization and Equiangular Embedding [55.107555305760954]
  We propose a conceptually simple yet effective method that attributes forgetting to layer-wise parameter overwriting and the resulting decision boundary distortion. Our method achieves competitive accuracy performance, even with absolute superiority of zero exemplar buffer and 1.02x the base model.
  arXiv  Detail & Related papers  (2024-01-17T09:01:29Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
  Semi-supervised domain adaptation (SSDA) is a challenging problem requiring methods to overcome both 1) overfitting towards poorly annotated data and 2) distribution shift across domains. We introduce an adaptive structure learning method to regularize the cooperation of SSL and DA.
  arXiv  Detail & Related papers  (2021-12-12T06:11:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.