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

• URL: http://arxiv.org/abs/2605.31239v1
• Date: Fri, 29 May 2026 12:40:27 GMT
• Title: Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference
• Abstract summary: Bagging-based ensembles, most notably Adaptive Random Forests, are among the strongest performers for learning from data streams.<n>We introduce a principled alternative based on anytime-valid inference.<n>Our method provides: (i) anytime-valid control of false splits under arbitrary data streams, including non-stationary settings; (ii) finite commitment time under a predictive advantage; and (iii) under stationary i.i.d. data, risk is monotone decreasing and strictly improves at every split.
• Score: 19.423472728159528
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bagging-based ensembles, most notably Adaptive Random Forests, are among the strongest performers for learning from data streams. A common denominator across these methods is their reliance on Hoeffding Trees as base learners, which grow decision trees incrementally by testing whether a candidate split is significantly better than its alternatives using concentration inequalities. Despite their empirical success, existing variants lack valid statistical guarantees. Current analyses rely on fixed-sample concentration bounds, while split decisions are made using data-dependent stopping rules, which invalidates their guarantees and can drive the probabilty of incorrect splits to one. We introduce a principled alternative based on anytime-valid inference. Our method provides: (i) anytime-valid control of false splits under arbitrary data streams, including non-stationary settings; (ii) finite commitment time under a predictive advantage; and (iii) under stationary i.i.d. data, risk is monotone decreasing and strictly improves at every split. Empirically, we evaluate both standalone trees and their use within Adaptive Random Forests on non-stationary streams. Our method improves performance while producing substantially smaller trees.

Related papers

• How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings? [58.740078141879984]
  Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on.<n>Recent work in causality-based domain generalization has shown how shared causal structure can induce invariant predictors.<n>In this paper, we study when full or partial causal knowledge can provably improve supervised domain adaptation.
  arXiv  Detail & Related papers  (2026-06-10T21:07:49Z)
• Decision-Path Patterns as Tree Reliability Signals: Path-based Adaptive Weighting for Random Forest Classification [0.9607593117607193]
  Random forests construct each tree with a different, randomised representation of the feature space.<n>Their uniform voting cannot correct errors in regions where trees with incorrect representations outnumber correct ones.<n>This paper proposes using the structural pattern of each tree's decision path as a per-sample reliability signal.
  arXiv  Detail & Related papers  (2026-05-20T05:15:09Z)
• Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees [68.04613115686509]
  Self-consistency boosts inference-time performance by sampling multiple reasoning traces in parallel and voting.<n>We propose Distinct Leafion (DLE), a deterministic decoding method that treats truncated sampling as a pruned tree and systematically enumerates distinct leaves instead of sampling with replacement.<n>DLE explores higher-quality reasoning traces, yielding better performance on math, coding, and general reasoning tasks.
  arXiv  Detail & Related papers  (2026-04-22T12:42:03Z)
• 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)
• Partition Trees: Conditional Density Estimation over General Outcome Spaces [46.1988967916659]
  We propose Partition Trees, a tree-based framework for conditional density estimation over general outcome spaces.<n>Our approach models conditional distributions as piecewise-constant densities on data adaptive partitions and learns trees by directly minimizing conditional negative log-likelihood.
  arXiv  Detail & Related papers  (2026-02-03T22:12:30Z)
• Principled Federated Random Forests for Heterogeneous Data [19.544248463207612]
  We propose FedForest, a new federated Random Forest algorithm for horizontally partitioned data.<n>We prove that our splitting procedure, based on aggregating carefully chosen client statistics, closely approximates the split selected by a centralized algorithm.<n>We also show that FedForest allows splits on client indicators, enabling a non-parametric form of personalization.
  arXiv  Detail & Related papers  (2026-02-03T08:41:59Z)
• Size-adaptive Hypothesis Testing for Fairness [8.315080617799445]
  We introduce a unified, size-adaptive, hypothesis-testing framework that turns fairness assessment into an evidence-based statistical decision.<n>We prove a Central-Limit result for the statistical parity difference, leading to analytic confidence intervals and a Wald test whose type-I (false positive) error is guaranteed at level $alpha$.<n>For the long tail of small intersectional groups, we derive a fully Bayesian Dirichlet-multinomial estimator.
  arXiv  Detail & Related papers  (2025-06-12T11:22:09Z)
• A Powerful Random Forest Featuring Linear Extensions (RaFFLE) [1.2233362977312945]
  RaFFLE is a novel framework that integrates PILOT trees as base learners within a random forest ensemble.<n> PILOT trees combine the computational efficiency of traditional decision trees with the flexibility of linear model trees.<n>RaFFLE proves to be a versatile tool for tackling a wide variety of regression problems.
  arXiv  Detail & Related papers  (2025-02-14T14:22:51Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs.<n>We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint.<n>We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• Adaptive Split Balancing for Optimal Random Forest [8.916614661563893]
  We propose a new random forest algorithm that constructs the trees using a novel adaptive split-balancing method. Our method achieves optimality in simple, smooth scenarios while adaptively learning the tree structure from the data.
  arXiv  Detail & Related papers  (2024-02-17T09:10:40Z)
• Theoretical and Empirical Advances in Forest Pruning [0.0]
  We revisit forest pruning, an approach that aims to have the best of both worlds: the accuracy of regression forests and the interpretability of regression trees.<n>We prove the advantage of a Lasso-pruned forest over its unpruned counterpart under weak assumptions.<n>We test the accuracy of pruned regression forests against their unpruned counterparts on 19 different datasets.
  arXiv  Detail & Related papers  (2024-01-10T20:02:47Z)
• Consensus-Guided Correspondence Denoising [67.35345850146393]
  We propose to denoise correspondences with a local-to-global consensus learning framework to robustly identify correspondence. A novel "pruning" block is introduced to distill reliable candidates from initial matches according to their consensus scores estimated by dynamic graphs from local to global regions. Our method outperforms state-of-the-arts on robust line fitting, wide-baseline image matching and image localization benchmarks by noticeable margins.
  arXiv  Detail & Related papers  (2021-01-03T09:10:00Z)
• Fair Densities via Boosting the Sufficient Statistics of Exponential Families [72.34223801798422]
  We introduce a boosting algorithm to pre-process data for fairness. Our approach shifts towards better data fitting while still ensuring a minimal fairness guarantee. Empirical results are present to display the quality of result on real-world data.
  arXiv  Detail & Related papers  (2020-12-01T00:49:17Z)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)

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.