Originality: The paper is fairly original in that it proposes a new tree-splitting criterion that seems to work very well when the leaves are linear models rather than constants. It also provides a novel application of several pieces of previous work, including LASSO and random forests. There are adequate citations of related work. Quality: I did not carefully check the math or read the proofs in the supplemental material, but I did not observe any technical mistakes. There is not much discussion of the limitations of their approach.

The paper proposes and investigates how to learn tree structure for linear regression trees based on a conditional Kendall's tau statistics with theoretical analysis.The ideas were new and generally satisfying to reviewers. While some reviewers would have liked to see even more experiments and experimental comparisons and details, other reviewers felt that the author response about the experiments was satisfying.

I am updating my score from 7 to 8. --- # Originality The main contributions are all original. While the take-home message of the study is in retrospect simple and obvious ( compute MDI importances on out-of-bag samples), the paper provides an original analysis that explains and justifies this modification of the computation of MDI importances. Some remarks however: - I would have appreciated a controlled experiment where G0(T) can be computed exactly in order to empirically appreciate the (supposed) tightness of the bound. More specifically, what if A1 and A2 are not satisfied? In real-word setups, A1 is very unlikely to hold.

The paper studies theoretically the bias of the popular MDI importance measures in the presence of noisy features and proposes a very simple practical solution to reduce it. Two reviewers are very enthusiastic about the paper, even more so after reading the authors' response. One reviewer has several valid concerns about missing links between theory and practice but still recommends acceptance. I therefore recommend accepting the paper. The author are asked to take into account the reviewers comments when preparing the final version of their paper and, in particular, to address the specific request of reviewer 2 (to clarify how MDI-oob is computed).

Conformal prediction provides a framework for uncertainty quantification, specifically in the forms of prediction intervals and sets with distribution-free guaranteed coverage. While recent cross-conformal techniques such as CV+ and Jackknife+-after-bootstrap achieve better data efficiency than traditional split conformal methods, they incur substantial computational costs due to required pairwise comparisons between training and test samples' out-of-bag scores. Observing that these methods naturally extend from ensemble models, particularly random forests, we leverage existing optimized random forest implementations to enable efficient cross-conformal predictions. We present coverforest, a Python package that implements efficient conformal prediction methods specifically optimized for random forests. coverforest supports both regression and classification tasks through various conformal prediction methods, including split conformal, CV+, Jackknife+-after-bootstrap, and adaptive prediction sets. Our package leverages parallel computing and Cython optimizations to speed up out-of-bag calculations. Our experiments demonstrate that coverforest's predictions achieve the desired level of coverage. In addition, its training and prediction times can be faster than an existing implementation by 2--9 times. The source code for the coverforest is hosted on GitHub at https://github.com/donlapark/coverforest.

Additional Feedback: The paper is not interesting enough for a competitive conference. It is good to have these results in the literature, but I suggest to send it to a journal. Having read the reviews, and following the discussion, I still think that this does not below in a competitive conference. Indeed, as the authors stress in their response, the power of the result is due to the specific algorithm developed here. Nevertheless, I cannot be excited by it, given the monotonicity assumption and the fact that it applies only to the uniform distribution setting. I agree that it's an interesting result, but I think that it's not interesting enough nor important enough for a top conference.

The submission got four reviews that were quite polarised in their recommendations, with two against accepting and two strongly in favour. The disagreement did not concern the technical quality of the paper. The reviewers agree that the theoretical work in this paper has been very competently performed and in the context of the problem the authors consider, the results are interesting and advance the state of the art. The disagreement is over whether the results are significant enough for NeurIPS or would be more appropriate for a specialised theory conference. The main objections against accepting are (i) the results are not surprising, (ii) the assumptions (monotonicity and uniform distribution) are strong and (iii) the overall computational complexity is high.

As a main contribution, the authors derive an exact attack algorithm on ensembles of decision stumps for \ell_\infty perturbations. In contrast, this problem is known to be NP-Hard for trees with at least 3 internal nodes, via previous work by Kantchelian et.

Thank you for your submission to NeurIPS. After the author response and discussion, the reviewers and I are in agreement that this work presents an interesting and substantial contribution to the work on provably robust adversarial learning. The extension of such methods from the typical NN setting to one of boosted decision stumps is an interesting one, and certainly worthy of publication. The author response in particular was good at addressing the points of one of the initially most negative reviewer, and it would be good to include these points into the final version.

Decision trees are fundamental tools in machine learning (ML), prized for their interpretability and simplicity in classification tasks. By providing clear decision paths, they enable users to understand and trust the reasoning behind predictions. However, their effectiveness diminishes when applied to heterogeneous datasets comprising entities with varying characteristics. Uniform decision paths often fail to account for the nuanced differences among diverse segments, leading to oversimplified or misleading classifications. Unsupervised clustering methods, on the other hand, excel in discovering latent structures within complex datasets. These methods, including hierarchical clustering, k-means, and DBSCAN, are powerful tools for segmenting populations into meaningful clusters without requiring predefined labels. While they are effective for uncovering hidden patterns, their primary drawback is a lack of explainability. Clusters produced by unsupervised methods often lack intuitive descriptions or actionable insights, making it difficult to interpret their relevance or apply them in practical decision-making scenarios.