Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

Researchers propose an anytime-valid inference method to correct split selection in decision trees used for streaming data, addressing a critical statistical gap where existing Hoeffding Trees lack valid guarantees despite empirical success. The approach provides false-split control across arbitrary data streams while producing smaller, more efficient trees than current methods.

The research addresses a fundamental problem in machine learning systems designed for continuous data streams: existing decision tree methods used in production systems operate without proper statistical guarantees. Hoeffding Trees, which power popular ensemble methods like Adaptive Random Forests, make split decisions using data-dependent stopping rules that invalidate traditional concentration inequalities. This creates a scenario where the probability of incorrect splits can approach certainty under certain conditions—a serious issue for systems deployed in real-world applications.

The anytime-valid inference framework solves this by providing statistical guarantees that hold regardless of when a decision is made or how data arrives. This matters because real-world data streams are often non-stationary, with changing distributions over time. The method ensures false-split control under these challenging conditions while maintaining finite commitment times when there is genuine predictive advantage between candidate splits.

For practitioners, this approach has immediate practical value. The empirical results demonstrate both improved performance and substantially smaller tree structures, which reduces memory requirements and inference latency—critical factors for edge computing and real-time analytics. Smaller trees also improve interpretability, a growing concern in regulated industries.

The broader significance lies in closing the theory-practice gap in streaming machine learning. As autonomous systems and real-time decision-making applications proliferate, having mathematically sound guarantees becomes increasingly important for safety-critical deployments. This work provides a principled path forward for building trustworthy streaming algorithms.

• →Anytime-valid inference provides statistical guarantees for decision tree splits under arbitrary, non-stationary data streams.
• →The method produces smaller trees with improved performance compared to current Hoeffding Tree variants.
• →False-split control is maintained regardless of stopping time or data distribution changes.
• →Results apply to both standalone trees and ensemble methods like Adaptive Random Forests.
• →This work closes the gap between theoretical guarantees and practical decision-tree algorithms for streaming data.