On the Convergence of CART under Sufficient Impurity Decrease Condition
This work addresses theoretical convergence guarantees for decision trees, which is incremental as it refines existing bounds and conditions for a widely used machine learning method.
The paper tackles the convergence rate of CART in regression by establishing an improved upper bound on prediction error under a sufficient impurity decrease condition, with examples showing the bound is tight up to constant or logarithmic factors, and provides verifiable conditions for this condition using additive models and locally reverse Poincaré inequality.
The decision tree is a flexible machine learning model that finds its success in numerous applications. It is usually fitted in a recursively greedy manner using CART. In this paper, we investigate the convergence rate of CART under a regression setting. First, we establish an upper bound on the prediction error of CART under a sufficient impurity decrease (SID) condition \cite{chi2022asymptotic} -- our result improves upon the known result by \cite{chi2022asymptotic} under a similar assumption. Furthermore, we provide examples that demonstrate the error bound cannot be further improved by more than a constant or a logarithmic factor. Second, we introduce a set of easily verifiable sufficient conditions for the SID condition. Specifically, we demonstrate that the SID condition can be satisfied in the case of an additive model, provided that the component functions adhere to a ``locally reverse Poincar{é} inequality". We discuss several well-known function classes in non-parametric estimation to illustrate the practical utility of this concept.