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

Technical Summary: MIST – Reliable Streaming Decision Trees for Online Class-Incremental Learning

1. Problem Statement

The paper addresses the challenge of Online Class-Incremental Learning (Online CIL) in tabular settings under strict constraints: single-pass processing, no access to historical data (exemplar-free), and bounded memory. While streaming decision trees are theoretically ideal for this regime due to their local updates and static decision boundaries, the authors argue they fail in practice for Online CIL due to two coupled failures:

1. Premature Splits (K-Scaling Instability): Existing streaming trees (e.g., VFDT, EFDT) rely on Hoeffding bounds derived from Information Gain. Since the range of Information Gain scales with $\log_2 K$ (where $K$ is the number of classes), the confidence radius grows as $K$ increases. This makes the split criterion unreliable in open-world settings where $K$ is unbounded, leading to either delayed necessary splits or premature, noisy splits.
2. Cold-Start Instability: When a leaf splits, standard streaming trees initialize child nodes with no prior information. In an exemplar-free setting, these children must rebuild predictive distributions from scratch using sparse data. This "cold-start" phase produces unreliable predictions and inflates impurity estimates, triggering further premature splits and compounding instability.

2. Methodology: The MIST Framework

The authors propose MIST (McDiarmid Incremental Streaming Tree), which resolves these failures through three integrated components:

A. Tight, K-Independent Split Criterion (McDiarmid Calibration)
Instead of Information Gain, MIST uses Gini impurity, which has a range bounded in $[0, 1)$ regardless of $K$. The authors derive a tight bounded-difference constant for the Gini split gain under single-sample replacement.

• Theoretical Result: They prove that the bounded-difference constant is $c_i = 4/n$ for arbitrary $K$, improving upon previous bounds of $8/n$ (Rutkowski et al.) or $4/n$ only for $K=2$ (De Rosa and Cesa-Bianchi).
• Operational Radius: This yields a confidence radius $\epsilon = \sqrt{32 \ln(2dm/\delta)/n}$ that is independent of the global class count $K$. This acts as a "structural regularizer," preventing premature splits as the class space expands.

B. Bayesian Knowledge Inheritance
To address the cold-start problem, MIST implements a parent-to-child projection protocol at the moment of splitting:

• Truncated-Gaussian Projection: For continuous features, the parent's Gaussian parameters (mean $\mu$ and variance $\sigma^2$) are projected onto the child nodes using exact truncated-Gaussian conditional moments based on the split threshold.
• Mass Rescaling: Class mass and Dirichlet pseudo-counts are rescaled based on the probability mass flowing to each child.
• Variance Reduction: Theoretically, the variance of the child's posterior estimates scales inversely with the parent's sample count ($O(1/\alpha n_{parent})$). This ensures that conservative splits (triggered only on data-rich parents) yield strong, statistically grounded priors for the children, minimizing post-split uncertainty.

C. Unified Label-Aware Sketching (KLL Quantiles)
To handle continuous threshold evaluation without retaining raw data, MIST employs KLL quantile sketches at each leaf:

• Dual Role: The same sketch structure serves two purposes: (1) generating candidate split thresholds from empirical class-conditional distributions, and (2) powering a non-parametric leaf predictor (MIST-K) for geometry-adaptive inference.
• Memory Efficiency: The sketches support continuous threshold evaluation without raw data retention. As leaves purify, the number of active classes per leaf ($K_{local}$) decreases, naturally bounding memory usage.
• Adaptive Prediction: MIST offers two configurations: MIST-G (parametric, using Gaussian accumulators for prediction) and MIST-K (non-parametric, using sketch-derived CDFs for prediction), allowing the system to adapt to Gaussian or non-Gaussian data geometries.

3. Key Contributions

1. Tight McDiarmid Calibration: The derivation of a sharp, $K$-independent bounded-difference constant ($4/n$) for Gini split gain, enabling a split criterion that does not degrade as new classes arrive.
2. Bayesian Post-Split Stabilization: A formal inheritance mechanism using truncated-Gaussian moments and Dirichlet rescaling, with proven variance reduction guarantees that scale with the parent's sample count.
3. Unified Sketching Architecture: A single data structure (KLL sketches) that enables both continuous split evaluation and distribution-free leaf prediction, eliminating the need for raw data retention.
4. Regime-Aware Empirical Characterization: Identification of conditions where parametric (Gaussian) vs. non-parametric (sketch-based) predictors are preferable, validated through stress tests on non-Gaussian geometries.

4. Experimental Results

The authors evaluate MIST on standard tabular benchmarks (e.g., Covertype, Split-MNIST, HAR) and synthetic stress tests with non-Gaussian geometries (Multimodal, Skewed, AngularSectors, Antipodal).

• Standard Benchmarks: MIST-G and MIST-K are competitive with global parametric methods (SLDA, SQDA) on near-Gaussian datasets. Notably, MIST achieves this with significantly lower forgetting compared to other tree-based methods (VFDT, EFDT) and global methods.
• Non-Gaussian Stress Tests: On datasets with complex geometries (e.g., AngularSectors, Multimodal), global parametric methods and ensemble trees (ARF-NR) collapse to near-chance performance. MIST-K, leveraging its non-parametric sketch-based predictor, remains uniquely robust, substantially outperforming all baselines.
• Ablation Studies:
  • Removing inheritance causes a ~9.5% drop in accuracy, confirming cold-start instability as a primary failure mode.
  • Replacing GNB leaves with majority voting causes a ~72% collapse, highlighting the necessity of density modeling.
  • The McDiarmid radius acts as a structural regularizer; using Hoeffding bounds leads to significantly larger trees with marginal accuracy gains but higher instability.

5. Significance and Claims

The paper claims that MIST demonstrates streaming decision trees can be a naturally modular architecture for open-world continual learning. By strictly decoupling local predictive modules while enabling statistically grounded knowledge transfer at split time, MIST provides a principled foundation for learners that grow without catastrophic forgetting.

The authors emphasize that their approach is exemplar-free (no raw data buffers), single-pass, and class-set-unbounded. They position MIST as a solution that fills the gap between streaming data mining (which often ignores class incrementality) and continual learning (which often relies on replay or pre-trained backbones). The work validates that local updates and bounded forgetting need not sacrifice accuracy, provided the split criterion is structurally sound and knowledge transfer is formalized.

Limitations Acknowledged:

• MIST-G relies on Gaussian assumptions for its inheritance projection, which MIST-K bypasses via sketching.
• The current implementation uses per-decision union bounds; the authors identify time-uniform confidence sequences via nonnegative supermartingales as a direction for future work to further optimize split timing over infinite horizons.