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 think the first part of the paper has very good original contributions with correct and nicely-written proofs in the appendix. However, I have the following questions regarding the parts of the paper starting at Section 3. Sorry if these are redundant questions with obvious answers that I missed. The RGD framework is mentioned for both convex and non-convex functions (Lemma 4 doesn't require f to be convex). However, the examples provided are all convex functions, and the focus also seems to be quite heavily on convex functions (because none of the papers on nonconvex optimization are compared with). Do the authors have (1) theoretical results and comparisons with existing work and/or (2)experiments, for non-convex functions?

Additional Feedback: Suggestions: Lack definition (anything that is not'common knowledge' should be defined and explained before using. Should not let readers guess.) 1. In eq(1), w and L is used without defined. Could first introduce the problem and mention L is loss or the target function, and w is the model parameter. 'coincides with' is not a commonly used, mathematically rigorous and clear expression.

The theoretical result of the paper is significant in my opinion. I also agree with the authors that the topic of this paper is at the core of machine learning and thus the paper should be evaluated based on its contributions. The reviewers also adjusted their reviews based on this point. However, I should also mention that the reviewers raised the concern that some of the definitions are omitted and few parts of the paper is not rigorous enough. Therefore, I suggest that the authors take care of such ambiguities in the final version.

Additional Feedback: Fixing the proof of Theorem 1 is not trivial. One can assume that the entire observed data \mathcal{D} is in r-tubular neighborhood of M, but that is out of the point of this paper because we only want the boundary to be in the tubular neighborhood of M. Another possible fix would be as follows: with probability 1, \mathcal{D} {0} will be a subset of {x:p_{X Y}(x 0) 0} and \mathcal{D} {1} will be a subset of {x:p_{X Y}(x 1) 0}. Then the edge {x_i,x_j} is in (kappa sqrt{rho_i rho_j})-tubular neighborhood of \mathfrak{D}, and hence r (kappa sqrt{rho_i rho_j})-tubular neighborhood of M. And hence the entire edge set E, and eventually the labeled Cech complex, is in r (kappa sup_i rho_i)-tubular neighborhood of M. The term sup_i rho_i goes to 0 as n goes to infty, so with proper range of kappa so that r (kappa sup_i rho_i) is bounded by (3-sqrt{8})tau in Assumption 1(b) in line 118 and also that \partial C is r (kappa sup_i rho_i) - dense in M, then the labeled Cech complex will deformation retracts to M, and hence this will appear in the persistent homology as well. This is very rough sketch and if the authors want to use this proof, they should fill the gap by themselves, although I can help to check more details if the authors want in the authors' response phase. And hence I increased my score to 6. Although, I would also like to mention that there is a slight mismatch between the framework of the paper and Theorem 1.

The authors presents an application of active learning to the problem of finding the homology of classifier/dataset decision boundaries. The method shows benefits empirically for learning a homology and is also paired with upper bound guarantees on the required number of labels. There was a concern raised around the correctness of the label complexity proof, which the authors have suggested a fix for in the rebuttal. This has satisfied the reviewer, however, there is an additional gap between theory and the algorithm implementation pointed out. This was not deemed a critical flaw, but please do discuss it in the final version.

Update: Thanks for the feedback and I have read them. Yet I don't think it has convinced me to change my decision. For Q2, if the framework is general, the authors should have extended it more than one case. Otherwise, the authors should focus on PCA instead of claiming the framework to be general. For Q3 and Q4, I think the discussion on how to choose k and d is not sufficient in the paper.

The reviews were mixed, but given the competitive nature of the conference, this paper probably doesn't make the threshold. Since the paper deals with adaptive dimensionality reduction, the following paper seems quite relevant: Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer: Adaptive metric dimensionality reduction.