On the Convergence of CART under Sufficient Impurity Decrease Condition

Summary

This paper improved the rate of consistency of CART based on a sufficient impurity decrease (SID) condition under regression settings. Then, the authors provided examples, which are mostly special additive models, that can satisfy the SID condition, and showed that the rate of consistency cannot be improved by more than a log factor.

Strengths

The strengths of this paper are summarized as follows: - The "locally reverse Poincare inequality" shown in this paper is intuitive and can be more general than previous studies. - The results are intuitive and improved the results in Chi et al. 2022 when the noise is sub-Gaussian.

Weaknesses

The weaknesses of this paper are summarized as follows: **About contributions** 1. The examples in this paper that satisfy the SID condition are still restricted to special additive models, which can be somehow not so practical. And it seems that extending the results to non-additive models is not easy. 2. The discussions about optimality in [Line 279-285] are not so strict. Note that the lower bound of order $\Omega(n^{-2 / (p + 2)})$ shown in Tan et al. 2022 is based on general additive models which may not satisfy the SID condition. In other words, when the SID condition satisfies, the lower bound may be better. Typos: - $\kappa$ in [Line 242] seems to be not defined and it seems to be $\tau$.

Questions

I would like to ask the authors the following questions: - Can the SID condition be satisfied in multi-dimensional settings without assuming additive models? See Weaknesses #1. - May the curse of dimensionality be avoided when the SID condition verifies? See Weaknesses #2.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

Summary

The paper studies the convergence rate of CART, a greedy algorithm for building decision trees, under a regression setting. It introduces a sufficient impurity decrease (SID) condition on the underlying function that ensures the consistency and polynomial convergence of CART. It also provides examples and sufficient conditions to verify the SID condition for various function classes, such as additive models, polynomials, and smooth and strongly convex functions.

Strengths

1. The paper provides a refined analysis of CART under the SID condition, which improves the prediction error bound over the previous work by Chi et al. (2022) and shows its optimality up to logarithmic factors. 2. The paper decodes the mystery of the SID condition by introducing a locally reverse Poincare (LRP) class of univariate functions and showing that additive functions with LRP components satisfy the SID condition. This connects the two types of assumptions in the literature: additive model and SID condition. 3. The paper demonstrates the practical utility of its results by providing examples and sufficient conditions to check the LRP property for various well-known function classes, such as polynomials, smooth and strongly convex functions, and strongly increasing functions. 4. The paper is well-written and clear, with detailed proofs and explanations in the appendix. It also includes simulations and figures to illustrate its main findings and compare them with existing results.

Weaknesses

1. The paper relies on some technical assumptions and conditions, such as bounded errors, bounded signal function, and LRP property, which may not hold or be easy to verify for some function classes. It would be helpful to provide more intuition and motivation for these assumptions and conditions, and discuss their implications and limitations for the applicability of the results. 2. The improvement of the convergence rate in this paper still heavily relies on the SID condition. Although the paper decomposes and illustrates the SID condition with some examples, they are still mathematical forms in 1-dimensional situations. If the paper could further analyze the SID condition in relation to the structure of real data, then its contribution to the SID condition would be more convincing.

Questions

1. Do Examples 3.1 - 3.3 still hold if they are generalized to high-dimensional situations? 2. The additive model assumption in Section 3 is still quite strong, is it possible to use milder assumptions? 3. The intuition behind the LRP condition needs further explanation, does this mathematical property have any implications for improving the CART algorithm? Maybe it can help explain why CART tends to handle data with certain structural characteristics.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NAN.

Summary

The paper performs theoretical analysis of the well-known CART algorithm. The authors show a convergence rate of CART under the condition called 'sufficient impurity decrease' (SID), which is tighter than known ones. The authors further provide the condition for a class of functions that satisfies SID.

Strengths

- The paper seems technically sound and the analysis of CART would be important. - The paper elaborately explains differences from past work in particular from [10].

Weaknesses

- Experimental verification is only in one quite simple figure for the simplest case. Of-course, the paper is a theoretical paper, but if richer empirical evidences had been provided, it would have been convincing more (such as different true functions and comparison with past bounds).

Questions

- Is there any insight that can be derived by the proposed analysis for tree ensemble models such as random forest?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

A limitation about lambda is discussed in Section 5.

Summary

The paper focuses on the analysis of the prediction error of Classification and Regression Trees (CART) for regression problems under a sufficient impurity decrease (SID) condition. The SID condition is a strong assumption on the approximation power of tree splits, which can ensure the consistency of CART. The paper establishes an upper bound on the prediction error of CART under the SID condition and shows that the error bound is tight up to log factors. The paper also discusses a few sufficient conditions under which an additive model satisfies the SID condition. The paper's first contribution is a refined analysis of CART under the SID condition, which improves upon the known result by providing a tighter error bound. The paper's second contribution is the decoding of the mystery of the SID condition, which builds a connection between the two types of assumptions in the literature: the additive model and the SID condition. The paper discusses a few examples of how the locally reverse Poincare inequality can be verified. Overall, the paper provides a refined analysis of CART under the SID condition and sheds light on the connection between two types of assumptions in the literature: additive model and SID condition.

Strengths

The paper has several strengths. First, it provides a refined analysis of the prediction error of Classification and Regression Trees (CART) under a sufficient impurity decrease (SID) condition for regression problems. The paper establishes an upper bound on the prediction error of CART under the SID condition and shows that the error bound is tight up to log factors. Second, the paper discusses a few sufficient conditions under which an additive model satisfies the SID condition. Third, the paper provides examples of how the locally reverse Poincare inequality can be verified.

Weaknesses

I think the work is significant. I don’t have many concerns, but I have some questions about the method. 1. Can this method be extended to classification problems? 2. In theorem 2.3, why do you need to suppose n satisfies such a complicated condition? 3. Also, in theorem 2.3, why should d be fixed to a function of data size? 4. In line 32, is it [0,1]^p?

Questions

Referred to Strengths and Weaknesses

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Referred to Strengths and Weaknesses

Summary

In this paper, the approximation of the model obtained from the decision tree learning algorithm CART is analyzed. More precisely, in Theorem 2.3, a convergence rate of the decision tree approximation compared to the true model is obtained. This analysis is performed under two assumptions of the paper (already introduced in the literature), with the Sufficient Impurity Decrease (SID) assumption in particular. Finally, examples of true models that satisfy the SID assumption are proven.

Strengths

1. The paper is well-written and easy to follow (although I did not check the proofs). 2. The analysis of Theorem 2.3 improves the result (i.e., the convergence rate) of [10]. 3. Proposition 3.1 links the SID condition and the class of functions satisfying the Locally Reverse Poincaré condition (that is proven for some classes).

Weaknesses

1. The additive structure assumption of $f^*$ seems restrictive (but is also assumed in previous works).

Questions

Typos and minor comments: - l38: the the -> the - l104: Chi et al.[10] -> Chi et al. [10] - l144: the notations $\bar{y}\_{\mathcal{I}\_A}$, $\bar{y}\_{\mathcal{I}\_{A\_L}}$ and $\bar{y}\_{\mathcal{I}\_{A\_R}}$ are not introduced - l163: "as" -> "at" - l193: "Assumptions‘2.1" -> "Assumptions‘ 2.1" - l240/246/247: Poincare -> Poincaré - l242: $\kappa$ -> "$\tau$" - l704: there is an indefinite reference "??" - The references are not "standardized", e.g. for JMLR it is written "The Journal of Machine Learning Research" or "Journal of Machine Learning Research"

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The limitation about the the SID condition is discussed in Section 5. Moreover, I do not see any potential negative societal impact of their work.