Grid-based Decision Tree Learning

Qin-Cheng Zheng

doi:10.1007/s10994-026-07165-0

Return

Grid-based Decision Tree Learning

2026-10-08

PRE

DOI：10.1007/s10994-026-07165-0

Original

Save

Abstract

En 中文

Decision tree learning algorithms, such as Classification and Regression Trees (CART), are commonly founded on heuristics that greedily maximize purity gain. Despite their practical success, the theoretical properties of these algorithms, such as consistency, remain unclear. This paper uncovers a substantial obstacle in analyzing the consistency of decision tree learning algorithms, in which the worst-case purity gain can be zero and a gain value of zero usually results in a non-convergent training error. Building upon this observation, our previous work introduced GridCART, a grid-based decision tree that can yield positive purity gain and achieve consistency under Lipschitz smoothness and a product feature distribution. This article extends the grid-based construction to random forests and gradient boosting decision trees, and establishes consistency-rate upper bounds for Grid-based Random Forests (GridForest) and a square-loss specialization of the Grid-based Gradient Boosting Decision Tree (GridGBDT). Experiments on 20 OpenML datasets show that the grid-based ensembles perform comparably to their conventional counterparts.

Keywords:

Decision tree

Consistency

Statistical learning theory

Ensemble learning

Random forest

Gradient boosting decision tree