New Anytime-Valid Inference Fixes Split Selection in Online Decision Trees

Hoeffding Trees—the backbone of streaming ensembles like Adaptive Random Forests—grow incrementally by testing candidate splits using concentration inequalities. But these tests assume fixed sample sizes, while actual split decisions are based on data-dependent stopping rules. This mismatch invalidates statistical guarantees and can drive the probability of incorrect splits to one, especially under concept drift. The paper by Amoukou, Mishra, and Veloso (accepted as a Spotlight at ICML 2026) identifies this fundamental flaw and proposes a principled replacement based on anytime-valid inference. Their method uses sequential hypothesis testing that remains valid regardless of when you stop, providing three key properties: (i) anytime-valid control of false splits under arbitrary (including non-stationary) data streams, (ii) finite commitment time when there is a genuine predictive advantage, and (iii) under stationary i.i.d. data, strictly monotone decreasing risk after each split.

Empirically, the authors evaluate both standalone anytime-valid trees and their integration into Adaptive Random Forests on non-stationary streaming benchmarks. The new method consistently improves predictive performance while generating substantially smaller trees—indicating that previous approaches were overfitting noisy split decisions. This result has direct practical implications: practitioners using online decision trees for fraud detection, network monitoring, or recommendation systems can now rely on statistically valid splits that adapt robustly to changing environments. By fixing the statistical underpinnings of a widely-used algorithm, the work bridges a critical gap between theory and practice in streaming machine learning.