Decision Tree Learning

Follow this topic Ask about this topic

Decision tree learning studies how to divide data into a hierarchy of tests so that predictions can be made from clear decision paths. Common approaches include greedy CART-style splitting, globally optimized trees found with mixed-integer programming or search, and differentiable or oblique trees that learn more complex splits; Hoeffding trees adapt these ideas to streaming data. Current work also explores uncertainty, ensembles of near-optimal trees, and uses such as causal subgroup analysis, recourse, and policy design. A central tension is how to improve predictive accuracy and stability without making trees too large, costly to train, or difficult to explain.

Latest papers

69 papers5 papers in the last four weeks, down 55% on the four weeks before. 0.0% of all new papers.

On the Statistical Optimality of Optimal Decision Trees
Mar 5, 2026Zineng Xu, Subhro Ghosh, Yan Shuo TanDecision Tree Learning Statistical Learning Theory
Department of Statistics and Data Science, National University of Singapore · Department of Mathematics, National University of Singapore
De-paradox Tree: Breaking Down Simpson's Paradox via A Kernel-Based Partition Algorithm
Mar 2, 2026Xian Teng, Yu-Ru LinCausal Inference Causal Reasoning
University of Pittsburgh, Pittsburgh, Pennsylvania, USA
FastODT: A tree-based framework for efficient continual learning
Feb 27, 2026Daniel Bretsko, Piotr Walas, Devashish Khulbe +3Online Continual Learning Decision Tree Learning
Masaryk University, Brno, Czech Republic · Warsaw University of Technology, Warsaw, Poland · Mycroft Mind, Brno, Czech Republic +2
On Imbalanced Regression with Hoeffding Trees
Feb 25, 2026Pantia-Marina Alchirch, Dimitrios I. DiochnosDecision Tree Learning Kernel Density Estimation
University of Oklahoma
A Hybrid Tsallis-Polarization Impurity Measure for Decision Trees: Theoretical Foundations and Empirical Evaluation
Feb 19, 2026Edouard Lansiaux, Idriss Jairi, Hayfa Zgaya-BiauDecision Tree Learning
Emergency Department, Lille University Hospital, France · Lille University, France · LIRMM +2
Towards Scalable Meta-Learning of near-optimal Interpretable Models via Synthetic Model Generations
Nov 6, 2025Kyaw Hpone Myint, Zhe Wu, Alexandre G. R. Day +1Decision Tree Learning Meta-Learning
Capital One
Optimal hypersurface decision trees
Sep 15, 2025Xi HeDecision Tree Learning
Department of Computer Science, Peking University, Beijing, China, 1000871
Integrated Multivariate Segmentation Tree for Heterogeneous Credit Data Analysis in Small- and Medium-Sized Enterprises
Aug 30, 2025Lu Han, Xiuying WangFinancial Services Interpretable ML
School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, China · School of Computer Science, University of Sydney, NSW 2006, Australia
Experiments with Optimal Model Trees
Mar 17, 2025Sabino Francesco Roselli, Eibe FrankInterpretable ML Decision Tree Learning
Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden. · Department of Computer Science, University of Waikato, Hamilton, New Zealand.

Mar 5, 2026J/K move · Enter open · S save

On the Statistical Optimality of Optimal Decision Trees

Zineng Xu, Subhro Ghosh, Yan Shuo Tan

Department of Statistics and Data Science, National University of Singapore · Department of Mathematics, National University of Singapore

Decision Tree Learning Statistical Learning Theory Empirical Risk Minimization Minimax Estimation

Open paper AskPDF arXiv

While globally optimal empirical risk minimization (ERM) decision trees have become computationally feasible and empirically successful, rigorous theoretical guarantees for their statistical performance remain limited. In this work, we develop a comprehensive statistical theory for ERM trees under random design in both high-dimensional regression and classification. We first establish sharp oracle inequalities that bound the excess risk of the ERM estimator relative to the best possible approximation achievable by any tree with at most

L

leaves, thereby characterizing the interpretability-accuracy trade-off. We derive these results using a novel uniform concentration framework based on empirically localized Rademacher complexity. Furthermore, we derive minimax optimal rates over a novel function class: the piecewise sparse heterogeneous anisotropic Besov (PSHAB) space. This space explicitly captures three key structural features encountered in practice: sparsity, anisotropic smoothness, and spatial heterogeneity. While our main results are established under sub-Gaussianity, we also provide robust guarantees that hold under heavy-tailed noise settings. Together, these findings provide a principled foundation for the optimality of ERM trees and introduce empirical process tools broadly applicable to other highly adaptive, data-driven procedures.