- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies the theoretical guarantees of a certain class of "Cyclic Oblique Forests", which can express affine linear boundaries in feature space, rather than simply axis-aligned rectangles. The paper's primary results establish upper bounds on the multiclass excess risk of such random forests under certain smothness assumptions. These are complemented by some empirical results on UCI data.
Critical strengths
The paper's main claims are precisely stated and seem to be sound.
Critical weaknesses
Writing: I had a very difficult time reading the paper. Consider just the abstract, lines 16-20. What is "uniform design"? What is the "smoothness order" and what are the "additional logarithmic factors"? Terminology is being used without being properly introduced. The central question of the paper is also not particularly well-motivated; the question on lines 44-46 seems to come somewhat out of nowhere, particularly the part about "Holder classes of conditional class probabilities with arbitrary finite smoothness." The same issues appear throughout the rest of the paper. For example, all of page 2 seems to be an extended related work section that is exceedingly dry and hard to make sense of for the uninitiated reader. On page 3, the first bullet point on "Geometric control and local polynomial estimation" was inscrutable to me. What are "terminal-cell diameters"?
Results: The paper's main result is a sample complexity bound for a fairly specific class of models under certain smoothness assumptions. The significance of these results is not clear to me, and I fear that they may not be of interest to much of the ICLR audience. I encourage the authors to argue for the significance / interest / intuition of these results, as I may be mistaken.
Questions for authors
- Are the authors familiar with the technical content of the paper? Have they confirmed that it is correct? Have they made an honest effort to provide the necessary exposition for the results?
- How significant are the paper's results? Do they resolve any open questions? Did they require any new techniques? Which steps were particularly challenging or difficult?
5 comments
2. The paper's main result is a sample complexity bound for a fairly specific class of models under certain smoothness assumptions. The significance of these results is not clear to me, and I fear that they may not be of interest to much of the ICLR audience. I encourage the authors to argue for the significance / interest / intuition of these results, as I may be mistaken.
Thank you for encouraging us to explain the significance more clearly. The main result establishes that a concrete oblique forest construction attains the minimax rate under the stated assumptions. The matching lower bound applies to all classifiers over the same distribution class. Thus, the result identifies an optimal rate, rather than only providing an upper bound for the proposed model family. For each fixed finite smoothness order, with the corresponding degree and tuning choices, this guarantee covers multiclass classification over the entire input domain without additional logarithmic factors.
The intuition is that three design choices play complementary roles. Oblique splits provide geometric flexibility; cycling through spanning directions ensures that leaves shrink in every direction; and polynomial leaf models exploit smooth variation in class probabilities. The difficult step is making these ingredients work together when leaves are irregular, thin, or contain very few observations. Our analysis controls their contribution to prediction error without imposing a minimum leaf sample count. A small leaf can be difficult to estimate accurately, but its contribution to integrated error is also weighted by its probability.
We believe this is relevant to researchers studying tree-based models and statistical learning because it explains how partition geometry and local model flexibility jointly determine learning efficiency. It also provides a principled relationship between tree depth, polynomial degree, sample size, and prediction accuracy. The contribution is therefore both a sharp guarantee for the proposed construction and an analysis of the design principles that make that guarantee possible.
3. Are the authors familiar with the technical content of the paper? Have they confirmed that it is correct? Have they made an honest effort to provide the necessary exposition for the results?
Thank you for raising these questions. Yes, we are familiar with the construction, assumptions, and mathematical arguments, and we take responsibility for the theorem statements and proofs. The appendix provides detailed derivations, including the treatment of undersampled and empty leaves and the conversion from estimation error to classification risk.
We intended the paper to be self-contained, but acknowledge that the original exposition did not adequately communicate these arguments to readers outside this area. We have revised the terminology and motivation and will make the proof structure more explicit.
4. How significant are the paper's results? Do they resolve any open questions? Did they require any new techniques? Which steps were particularly challenging or difficult?
Thank you for asking us to clarify the significance and technical contributions of our results.
(i) The broader significance concerns how useful structure translates into accurate predictions with limited data. A model's ability to represent a pattern does not by itself establish how much data are needed to learn it. Our results show that oblique partitions and polynomial leaf models can jointly attain the minimax expected multiclass excess-risk rate under the stated assumptions. The matching lower bound applies to all classifiers over the same distribution class, establishing optimality up to constants without additional logarithmic factors.
(ii) The results address a specific gap in oblique-forest theory. Section 6 of Local Linear Forests (Friedberg et al., 2021) identifies higher-order smoothness and further optimality results as research directions. O'Reilly and Tran (2024) establish oblique-forest guarantees up to smoothness order two; their higher-smoothness binary-classification result in Corollary 14 is formulated on interior regions. We address whether oblique forests can attain the minimax expected multiclass excess-risk rate for arbitrary fixed finite smoothness over the entire input domain. Our results give a positive answer under uniform design and the stated assumptions, with degree and tuning choices matched to each fixed smoothness order.
(iii) The principal technical contribution is the expected integrated estimation analysis in Lemma 3.5. It uses polynomial leverage control on convex cells, ridge regularization, coefficient projection, and probability-weighted averaging over leaf counts. The new analysis yields an expected estimation bound for irregular oblique cells that requires neither minimum leaf probabilities nor minimum sample counts, with constants independent of leaf aspect ratios.
(iv) Two steps are particularly challenging. First, oblique splitting creates nonrectangular cells, including thin boundary leaves. Lemma 3.4 converts the width contraction along cyclic splitting directions into a deterministic diameter bound for every leaf, enabling control of polynomial approximation error. Second, small leaves may contain fewer observations than polynomial coefficients or be empty. Regularization, coefficient projection, and the specified fallback handle these cases, while averaging over leaf counts controls their aggregate contribution. The key intuition is that a small cell may be difficult to estimate accurately, but its contribution to integrated error is also weighted by its probability. This avoids requiring every leaf to be well conditioned simultaneously.
References:
Friedberg, R., Tibshirani, J., Athey, S., and Wager, S. (2021). Local Linear Forests. Journal of Computational and Graphical Statistics, 30(2), 503-517.
O'Reilly, E., and Tran, N. M. (2024). Minimax Rates for High-Dimensional Random Tessellation Forests. Journal of Machine Learning Research, 25(89), 1-32.
Thank you for identifying these specific presentation issues. We agree that the original abstract and introduction assumed too much familiarity with statistical learning terminology. We have revised the wording to explain the concepts and their roles more directly.
Uniform design means that features are uniformly distributed over [0,1]d, as assumed in Section 2. Smoothness order controls the variation of the class probabilities and, at higher orders, their derivatives. Higher smoothness allows more accurate approximation using suitable local polynomials; Definition 3.6 gives the formal condition. Additional logarithmic factors are multipliers such as (logn)a, with a>0, in an error bound, where n is the training sample size. Our upper and lower bounds match without these factors. The revised abstract explains these concepts in plain language.
A terminal cell is the input region corresponding to a tree leaf. Its diameter is the largest distance between two points in that region. Controlling this distance controls local polynomial approximation error, as explained in Section 3.1 and Lemma A.7. The first contribution now defines leaf diameter directly and explains its role alongside the estimation bound.
We have also strengthened the motivation preceding the central research question. The geometric example in Figure 1 motivates oblique splits, while smooth variation in class probabilities motivates polynomial leaf predictions. However, oblique leaves can have irregular shapes and contain few or no observations, making reliable polynomial estimation challenging. This leads naturally to the question of whether these forests can exploit smoothness while attaining the best possible multiclass classification rate.
Finally, we have clarified how the discussion of prior work and Table 1 distinguish existing guarantees from the gap addressed by our paper. The comparisons focus on partition geometry, the smoothness that leaf models can exploit, and the resulting statistical guarantees, helping readers understand how each line of work relates to the research question.