On the Statistical Optimality of Optimal Decision Trees

• URL: http://arxiv.org/abs/2603.05340v1
• Date: Thu, 05 Mar 2026 16:16:25 GMT
• Title: On the Statistical Optimality of Optimal Decision Trees
• Abstract summary: We develop a comprehensive statistical theory for globally optimal empirical risk minimization trees under random design.<n>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.<n>We derive minimax optimal rates over a novel function class: the piecewise sparse heterogeneous anisotropic Besov (PSHAB) space.
• Score: 6.920276126310231
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Preference Data Selection for Mitigating the Alignment Tax in Large Language Models [52.18310687523229]
  BALIGN is a balanced data selection strategy that mitigates catastrophic forgetting while optimizing alignment efficacy.<n>By aggregating three key data-centric features into a unified composite risk score, BALIGN systematically filters out high-risk preference samples.<n>Experiments on standard human preference datasets demonstrate that BALIGN strongly preserves foundational capabilities without compromising alignment gains.
  arXiv  Detail & Related papers  (2026-08-25T07:58:42Z)
• Stochastic Emulation using Generalized Stratified Sampling for Performance-Based Risk Optimization of Structures [0.0]
  This study proposes a framework that combines Generalized Stratified Sampling (GSS) with Polynomial Chaos Expansion (SPCE)<n>The proposed framework is applied to the optimal design of buckling-trained brace cross-sectional areas in a two-story steel building.
  arXiv  Detail & Related papers  (2026-08-05T16:12:30Z)
• Efficient Thought Space Exploration through Strategic Intervention [54.35208611253168]
  We propose a novel Hint-Practice Reasoning (HPR) framework that operationalizes this insight through two synergistic components.<n>The framework's core innovation lies in Distributional Inconsistency Reduction (DIR), which dynamically identifies intervention points.<n> Experiments across arithmetic and commonsense reasoning benchmarks demonstrate HPR's state-of-the-art efficiency-accuracy tradeoffs.
  arXiv  Detail & Related papers  (2025-11-13T07:26:01Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  We propose novel loss formulations that align directly with ranking metrics.<n>We integrate the proposed RG losses with the highly efficient Alternating Least Squares (ALS) optimization method.<n> Empirical evaluations on real-world datasets demonstrate that our approach achieves comparable or superior ranking performance.
  arXiv  Detail & Related papers  (2025-06-11T06:59:17Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Tuning for Trustworthiness -- Balancing Performance and Explanation Consistency in Neural Network Optimization [49.567092222782435]
  We introduce the novel concept of XAI consistency, defined as the agreement among different feature attribution methods.<n>We create a multi-objective optimization framework that balances predictive performance with explanation.<n>Our research provides a foundation for future investigations into whether models from the trade-off zone-balancing performance loss and XAI consistency-exhibit greater robustness.
  arXiv  Detail & Related papers  (2025-05-12T13:19:14Z)
• Risk-Averse Certification of Bayesian Neural Networks [70.44969603471903]
  We propose a Risk-Averse Certification framework for Bayesian neural networks called RAC-BNN.<n>Our method leverages sampling and optimisation to compute a sound approximation of the output set of a BNN.<n>We validate RAC-BNN on a range of regression and classification benchmarks and compare its performance with a state-of-the-art method.
  arXiv  Detail & Related papers  (2024-11-29T14:22:51Z)
• Fair Risk Minimization under Causal Path-Specific Effect Constraints [3.0232957374216953]
  This paper introduces a framework for estimating fair optimal predictions using machine learning. We derive closed-form solutions for constrained optimization based on mean squared error and cross-entropy risk criteria.
  arXiv  Detail & Related papers  (2024-08-03T02:05:43Z)
• Statistical Properties of Robust Satisficing [5.0139295307605325]
  The Robust Satisficing (RS) model is an emerging approach to robust optimization. This paper comprehensively analyzes the theoretical properties of the RS model. Our experiments show that the RS model consistently outperforms the baseline empirical risk in small-sample regimes.
  arXiv  Detail & Related papers  (2024-05-30T19:57:28Z)
• Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation [54.61816424792866]
  We introduce a general framework on Risk-Sensitive Distributional Reinforcement Learning (RS-DisRL), with static Lipschitz Risk Measures (LRM) and general function approximation. We design two innovative meta-algorithms: textttRS-DisRL-M, a model-based strategy for model-based function approximation, and textttRS-DisRL-V, a model-free approach for general value function approximation.
  arXiv  Detail & Related papers  (2024-02-28T08:43:18Z)
• Bayesian Nonparametrics Meets Data-Driven Distributionally Robust Optimization [29.24821214671497]
  Training machine learning and statistical models often involve optimizing a data-driven risk criterion. We propose a novel robust criterion by combining insights from Bayesian nonparametric (i.e., Dirichlet process) theory and a recent decision-theoretic model of smooth ambiguity-averse preferences. For practical implementation, we propose and study tractable approximations of the criterion based on well-known Dirichlet process representations.
  arXiv  Detail & Related papers  (2024-01-28T21:19:15Z)
• f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization [9.591164070876689]
  This paper presents a unified optimization framework for fair empirical risk based on f-divergence measures (f-FERM) In addition, our experiments demonstrate the superiority of fairness-accuracy tradeoffs offered by f-FERM for almost all batch sizes. Our extension is based on a distributionally robust optimization reformulation of f-FERM objective under $L_p$ norms as uncertainty sets.
  arXiv  Detail & Related papers  (2023-12-06T03:14:16Z)
• Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysis [21.913563167426872]
  Asynchronous distributed algorithm named Asynchronous Single-looP alternatIve gRadient projEction is proposed.<n>New uncertainty set, i.e., constrained D-norm uncertainty set, is developed to leverage the prior distribution and flexibly control the degree of robustness.<n> empirical studies on real-world datasets demonstrate that the proposed method can not only achieve fast convergence, but also remain robust against data as well as malicious attacks.
  arXiv  Detail & Related papers  (2023-07-25T01:56:57Z)
• On the Variance, Admissibility, and Stability of Empirical Risk Minimization [57.63331017830154]
  Empirical Risk Minimization (ERM) may attain minimax suboptimal rates in terms of the mean squared error.<n>We prove that under relatively mild assumptions, the suboptimality of ERM must be due to its large bias.
  arXiv  Detail & Related papers  (2023-05-29T15:25:48Z)
• Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence [66.83161885378192]
  Area under ROC (AUROC) and precision-recall curves (AUPRC) are common metrics for evaluating classification performance for imbalanced problems. We propose a technical method to optimize AUPRC for deep learning.
  arXiv  Detail & Related papers  (2021-04-18T06:22:21Z)

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.