acceptodds
Under review as a conference paper at ICLR 2027

Minimax-Optimal Multiclass Classification with Cyclic Oblique Forests

Abstract

Oblique splits can represent classification boundaries that are poorly aligned with the input coordinates. A key challenge is to combine this geometric flexibility with sharp statistical guarantees that exploit smooth class probabilities. We introduce the Cyclic Oblique Forest, a purely randomized approach to multiclass classification that combines cyclic oblique splitting with regularized local polynomial estimation. Under uniform design, we establish minimax rates for expected multiclass excess risk over H\"older classes of conditional class probabilities for every fixed finite smoothness order, without additional logarithmic factors. These rates are attained with midpoint cuts along a basis of splitting directions, with depth and polynomial degree chosen for the specified smoothness. We further derive a sharper excess-risk bound under an additional multiclass margin condition with a positive exponent. Real data analysis on classic UCI datasets shows that the proposed method achieves lower mean test error than existing random forest baselines.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Random forests, Oblique decision trees, Multiclass classification, Minimax optimality

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_YcDCOpenReview ↗
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

1. 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"?

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[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 (log⁡n)a(\log n)^a, with a>0a>0, in an error bound, where nn 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.

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.

Reviewer_5iYPOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes forests combining cyclic, data-independent oblique splits with regularized polynomial class-score estimation. Under uniform design, midpoint splitting along a fixed basis achieves the minimax expected multiclass excess-risk rate n−s/(2s+d)n^{-s/(2s+d)} for arbitrary fixed Hölder smoothness, without logarithmic factors. It also provides margin-dependent bounds and benchmark experiments.

Critical strengths
  • The paper extends oblique-forest guarantees to arbitrary fixed finite smoothness, multiclass classification, and the full input domain, including boundaries. The irregular-cell estimation analysis is a useful component of this extension.
  • The analysis carefully handles irregular, undersampled, and empty leaves. The no-margin upper and lower bounds match, and the leverage, majority-vote, and margin arguments appear valid under the stated assumptions.
  • Geometry, estimation, and risk conversion are clearly separated. The paper appropriately distinguishes its minimax no-margin result from its non-minimax margin bound. Shared-partition simulations help illustrate the effect of polynomial degree.
Critical weaknesses

The principal remaining reservation concerns the precise incremental contribution relative to existing balanced polynomial-leaf forests. The irregular-cell, full-domain estimation analysis appears to be the meaningful advance, but its distinction from existing results could be articulated more explicitly. A fixed linear transformation makes the splits coordinate-aligned, but does not by itself establish equivalence of the estimator or its boundary analysis. Therefore, I would not regard this observation, or the use of familiar ingredients, as sufficient evidence of inadequate novelty.

Questions for authors
  1. Relative to existing balanced polynomial-leaf forest methods, which parts of the full-domain oblique estimation analysis are new, and which follow from established approximation and plug-in arguments?
  2. How are the population-orthonormal bases in Equation (3) constructed for the higher-dimensional benchmark experiments? If numerical or empirical approximations are used, do they modify the analyzed ridge penalty?
2 comments

Thank you for pointing out where we need to clarify our contribution and numerical implementation.

1. Relative to existing balanced polynomial-leaf forest methods, which parts of the full-domain oblique estimation analysis are new, and which follow from established approximation and plug-in arguments?

Thank you for asking us to make this comparison more precise. Although both methods use balanced splitting and polynomial leaves, their estimation analyses address different leaf geometries and sample-count conditions. Zhang et al. (2024) use rectangular leaves with controlled sample counts. Their Theorem 3.1 provides a minimax-order integrated squared regression error bound in probability under the condition k≫log⁡Nk\gg\log N, where kk is the minimum number of estimation observations per leaf and NN is the training sample size. Our oblique partitions can produce nonrectangular convex cells and do not enforce a minimum leaf sample count.

A change of coordinates does not eliminate these differences. For q=dq=d, the transformation z=Bxz=Bx, where BB has rows bj⊤b_j^\top, aligns the cuts with the coordinate axes but changes the support to B[0,1]dB[0,1]^d. Each transformed leaf is the intersection of this support with an axis-aligned box, so boundary leaves may remain nonrectangular. The transformation also preserves leaf membership and sample counts. Thus, even when the conditional measure, polynomial basis, and penalty are transported consistently to preserve the estimator, the resulting cells still require analysis.

The principal additional work lies in establishing the expected integrated squared estimation bound in Lemma 3.5. Three components underpin this result. First, Lemma A.2 applies an established polynomial norm inequality to obtain uniform leverage control on convex cells, with constants independent of leaf aspect ratios. Second, ridge regularization and joint coefficient projection control estimation in undersampled or poorly conditioned leaves, while the specified fallback handles empty leaves. Third, averaging over binomial leaf counts and weighting each leaf's error by its probability bounds each leaf's sampling-error contribution by a constant times the inverse subsample size. Summing these contributions yields the overall estimation bound without requiring all leaves to be well conditioned simultaneously.

2. How are the population-orthonormal bases in Equation (3) constructed for the higher-dimensional benchmark experiments? If numerical or empirical approximations are used, do they modify the analyzed ridge penalty?

Thank you for raising this implementation question. We have clarified the benchmark construction in Appendix A.2 and added a corresponding classification analysis in Appendix A.7.

In the benchmark experiments, we replace the population basis with a polynomial basis orthonormal under a finite auxiliary measure QAQ_A. For κ>0\kappa>0, each occupied leaf uses mA=max⁡{256,4D}m_A=\max\lbrace256,4D\rbrace auxiliary geometric points, where D=(d+κκ)D=\binom{d+\kappa}{\kappa}. Scrambled Sobol points are routed through the partition, and hit-and-run sampling within the leaf supplies any remaining points. These points are unlabeled and separate from the fitting observations. We center the nonconstant monomials using their auxiliary means and apply Cholesky whitening to their auxiliary covariance matrix. This gives exact orthonormality under QAQ_A in exact arithmetic. All polynomial terms are retained, without covariance jitter or rank truncation. The construction requires full-rank auxiliary moments, but does not require DD labeled observations per leaf. For κ=0\kappa=0, the basis is simply the constant function.

The finite auxiliary measure does change the regularization. For a polynomial class score gg, the population-basis penalty is λVar⁡PA(g)\lambda\operatorname{Var} _{P_A}(g), where PA=Unif⁡(A)P_A=\operatorname{Unif}(A), whereas the implemented penalty is λVar⁡QA(g)\lambda\operatorname{Var} _{Q_A}(g). The scalar λ\lambda and the unpenalized intercept remain unchanged.

Theorem A.12 addresses this finite auxiliary version directly. Under the original distribution, partition, and smoothness assumptions, with auxiliary points supported within the leaf closure and full-rank auxiliary moments, it establishes the same expected multiclass excess-risk rate in exact arithmetic. The proof controls the induced penalty through the polynomial leverage bound and requires no prescribed approximation rate for the auxiliary moments. This guarantee concerns class predictions and majority voting; the original integrated score-error lemma retains its population-basis formulation.

References:

Zhang, Y., Ji, W., and Bradic, J. (2024). Adaptive Split Balancing for Optimal Random Forest. arXiv preprint arXiv:2402.11228.

Thank you again for your time and comments. We would appreciate your feedback on whether our responses have addressed all your concerns, and would be happy to provide further explanations if any questions remain.

Reviewer_ST1vOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper works on some classic statistical learning topic. The authors develop cyclic oblique forest. It is essentially a random forest that utilizes cyclic splits with local polynomial estimation for multi-class classificaiton. This is a typical theoretic work, with dense math proof. The authors provide proofs for mini-max-optimal rates for expected multiclass excess risk over Hölder-smooth function classes, without additional logarithmic factors. The experiments are only conducted on several UCI datasets.

Critical strengths

I would summarize the strong points of this work as below.

  1. The work has strong theoretical contribution. It establishes sharper excess-risk bound. The result covers arbitrary fixed finite smoothness and avoids additional logarithmic factors, which is a meaningful theoretical advance.

  2. The setting of the problem is general and the proposed soluion (cyclic oblique forest) is straightforward to be deployed. Thus it has great potential in solving binary muliti-class problems. The constraints in the analyis are loose, and local polynomial estimator works under a variaty of cases. This makes the proposed model useful in practice.

Critical weaknesses

I have to say that I am not an expert on this topic. Below is the list of key weaknesses from my standpoint as a researcher on applications.

  1. The theoretic results are elegant. However, I notice that it enforces several rigid conditions. For example, the minimax guarantee relies on uniform feature distribution. The splitting directions should satisfy a nondegeneracy condition. Tuning some parameters in the key steps is generally hard in practice, despite the elegant theory.

  2. It requires the feature is in binary, which further limited the applicaiton in practice.

  3. The experiments are rather limited. The authors only provide an iilustrative examples and some superficially treated experiments on selected UCI datasets. The chosen baselines are also simple and out-dated. In general, they are not sufficient to establish broad practical advantages over existing random forests.

  4. The performance gap between the proposed method and Breiman RF is quite limited. Pperformance gains are noted in most cases, yet the gains are very marginal.

Questions for authors

See my detailed comment in section "Critical Weaknesses".

3 comments

Thank you for your careful review and for recognizing the theoretical contribution. We address your concerns below.

1. The theoretic results are elegant. However, I notice that it enforces several rigid conditions. For example, the minimax guarantee relies on uniform feature distribution. The splitting directions should satisfy a nondegeneracy condition. Tuning some parameters in the key steps is generally hard in practice, despite the elegant theory.

Thank you for raising these concerns. The design assumption, the condition on splitting directions, and parameter selection have different roles.

(i) The main minimax result is indeed established under uniform design, as stated in the abstract and Theorems 3.7 and 3.9. However, Remark 3.8, proved in Appendix A.4, extends the upper bound to nonuniform distributions whose densities are bounded above and away from zero on [0,1]d[0,1]^d, without changing the convergence exponent.

(ii) Assumption 3.1 requires the splitting directions to span Rd\mathbb{R}^d and can be satisfied directly by construction. Any orthonormal basis, including a rotated coordinate basis, satisfies this condition with Λ=1\Lambda=1 (Example 3.2). In our experiments, we generate such bases through QR decomposition of Gaussian matrices, as described in Appendix A.2. Thus, this condition does not require estimating an unknown property of the data. Its purpose is to ensure that splitting contracts cells in every direction.

(iii) The parameters of our method can be tuned straightforwardly using standard validation-based search, consistent with established practice in related tree and forest methods. For example, Grinsztajn et al. (2022) include maximum depth in the random forest search space and select configurations by validation performance. Friedberg et al. (2021) recommend cross-validation for selecting ridge penalties in local linear forests, and Cai et al. (2023) use cross-validation for hyperparameter selection in extrapolated random trees.

In our experiments, we evaluate polynomial degrees κ∈{0,1,2}\kappa\in\lbrace0,1,2\rbrace separately and use validation error to select tree depth pp, ridge regularization strength λ\lambda (for κ=1,2\kappa=1,2), and the splitting basis from finite candidate sets. The remaining settings are fixed. Appendix A.2 and Table 3 provide the complete selection procedure and candidate grids, making the tuning process explicit and reproducible.

2. It requires the feature is in binary, which further limited the applicaiton in practice.

Thank you for the opportunity to clarify this point. Our method does not require binary features. Section 1 defines the feature vector as X∈[0,1]dX\in[0,1]^d, allowing real-valued coordinates. The method supports binary classification, multiclass classification, and regression, with experiments covering all three settings in Section 4.2.

References:

Cai, Y., Ma, Y., Dong, Y., and Yang, H. (2023). Extrapolated Random Tree for Regression. Proceedings of the 40th International Conference on Machine Learning, PMLR 202, 3442-3468.

Friedberg, R., Tibshirani, J., Athey, S., and Wager, S. (2021). Local Linear Forests. Journal of Computational and Graphical Statistics, 30(2), 503-517.

Grinsztajn, L., Oyallon, E., and Varoquaux, G. (2022). Why do tree-based models still outperform deep learning on typical tabular data?. Advances in Neural Information Processing Systems, 35, 507-520.

3. The experiments are rather limited. The authors only provide an iilustrative examples and some superficially treated experiments on selected UCI datasets. The chosen baselines are also simple and out-dated. In general, they are not sufficient to establish broad practical advantages over existing random forests.

Thank you for suggesting broader comparisons with recent methods. We have completed additional experiments on Voice Gender and Rice Gonen against six baselines: JARF, Extra Trees, PPforest, SPORF, RF (Breiman, 2001), and SRFS. Our method achieves the lowest mean classification error among these methods on both datasets. The new comparisons include JARF from ICLR 2026, which learns a global linear transformation before fitting a forest (Rauniyar, 2026). SPORF uses sparse random projections (Tomita et al., 2020). PPforest selects projections that separate the classes (da Silva et al., 2021). Extra Trees randomizes split thresholds (Geurts et al., 2006).

We use 20 shared splits per dataset and 200 trees per method in total. For each method and dataset, the parameter grid is fixed across the 20 repetitions. Our method achieves the lowest mean test error among the compared methods on both datasets. On Voice Gender, it reduces mean test error by 66.48% relative to SRFS and 36.51% relative to PPforest. On Rice Gonen, the reductions are 35.40% relative to SRFS and 19.76% relative to PPforest. Our method also improves on all remaining baselines. On Voice Gender, the reductions relative to JARF and RF are 19.46% and 14.89%, respectively. Those relative to SPORF and Extra Trees are 11.44% and 9.09%. On Rice Gonen, the reductions relative to JARF and RF are 10.48% and 10.12%, respectively. Those relative to SPORF and Extra Trees are 8.14% and 7.76%. All reductions compare mean test errors over the 20 shared splits.

These results show gains over all six baselines on the two added datasets, including recent forest methods. Together with the controlled experiments in Section 4.1, they provide broader experimental support for our method.

4. The performance gap between the proposed method and Breiman RF is quite limited. performance gains are noted in most cases, yet the gains are very marginal.

Thank you for your comment on the performance gains. In Table 2, the quadratic cyclic oblique forest reduces mean classification error by 17.31% relative to Breiman RF on Iranian Churn. On the Carbon-u regression task, the relative reduction in mean MSE is approximately 14.1%. Both methods use 200 trees, and Table 3 specifies the RF tuning grid. These results show practical gains over a tuned RF baseline in both classification and regression.

Moreover, our paper's principal contribution is the establishment of matching upper and lower bounds for expected multiclass excess risk over Hölder classes of arbitrary fixed finite smoothness, without additional logarithmic factors. The experiments complement this theoretical contribution by demonstrating competitive predictive performance. We interpret these results as descriptive improvements on the evaluated benchmarks.

References:

Breiman, L. (2001). Random Forests. Machine Learning, 45(1), 5-32.

da Silva, N., Cook, D., and Lee, E.-K. (2021). A Projection Pursuit Forest Algorithm for Supervised Classification. Journal of Computational and Graphical Statistics, 30(4), 1168-1180.

Geurts, P., Ernst, D., and Wehenkel, L. (2006). Extremely randomized trees. Machine Learning, 63, 3-42.

Rauniyar, S. (2026). Jacobian Aligned Random Forests. International Conference on Learning Representations.

Tomita, T. M., Browne, J., Shen, C., Chung, J., Patsolic, J. L., Falk, B., Priebe, C. E., Yim, J., Burns, R., Maggioni, M., and Vogelstein, J. T. (2020). Sparse Projection Oblique Randomer Forests. Journal of Machine Learning Research, 21(104), 1-39.

Thank you again for your time and comments. We would appreciate your feedback on whether our responses have addressed all your concerns, and would be happy to provide further explanations if any questions remain.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.