Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper presents an efficient construction of coresets for decision trees. For general decision trees, coresets are useless because they cannot be very small. However, the result in this paper focuses on decisions trees for a restricted form of signal, namely, a function on the discrete grid of points $\{1,2,\dots, n\} \times \{1,2,\dots, m\}$. The result is derived by relating this problem to the problem of constructing balanced partition trees for planar point sets. The theoretical result is also evaluated on synthetic and real datasets, showing impressive gains in runtime and storage requirements.
main_review: I find the result interesting, both from the perspective of discovering a useful subset of decision trees that can be shown to have coresets, and from the perspective of the elegant solution relating the problem to a geometric one. The result is perhaps not surprising, but useful.
limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces small data summaries known as coresets for decision trees on a two dimensional data domain. It does so by summarizing rectangular blocks of data with their mean value as an approximation for each cell's individual value, hereby approximating up to (1+-eps) relative error the squared loss induced by each k-partition that can be formed by a decision tree with k leaves.
The construction is done in linear time in the input parameters and data and the size of the summary is poly(k log(n)/eps).
Some experiments show that the coresets are useful in practical settings where decision tree heuristics are compared on the coreset vs the original data.

main_review: The paper reads very well and the work is well-motivated. In the introduction to coresets maybeit should be added that C is much smaller than the data D (right in lines 66-69).

it is just the squared error, not the MSE (l. 104)

The paper says there is no coresets in general, even in 1 dimension. but then for m x n-signals a coreset construction is presented. I find the discussion too vague. I didn't learn what was the problem that implies impossibility. And more importantly, what exactly is the relaxation that makes it possible again?
Can you explain? (and modify the paper accordingly)

Is an extension to d>2 tensor data even possible? Why is this only an outlook for future work and not dealt with? This is currently also vague (but minor).

since the coreset constructions are claimed to be different from existing sampling and greedy optimization, shouldn't there be some references on the appropriate surveys with more diverse coresets methods instead?

I found it weird that we have mxn signals and then nxm sub-signals. maybe the authors could use some other letters to denote the input dimenions?

Definition of the O-notation should have c>0 and x_0 such that the inequality holds for all x>x_0. (199-200)

t is overloaded  on page 6 before Sec. 3

Algo 2 inner while loop looks like the last iteration is run, but the result is not considered in the output. Please double check.

Fig 3  It seems that in the lower right corner there should be a low constant value and the lower left high value should be removed since it is covered by the other high value (22 and 21).

regarding those tuples (b|b^2|1) it seems very similar to k-means "clustering features" used for example in BIRCH. Another reference that should be cited in this context is https://dl.acm.org/doi/10.1145/1132863.1132873 which stores the sum of values, sum of squared values and number of elements, i.e., the sum of those tuples in your paper.

generally I suggest strongly to browse sudipto guha's DBLP for "histogram". There are a lot of extensions to other loss functions, fitting polynomials instead of constant values per bucket, streaming, more than one dimension. This seems very similar and strongly related to the contents of this submission or possible extensions.

alpha, beta >0  -> alpha, beta >1 (eg in Def4 and Lem7)

Coreset size: the authors claim that usually the theoretical bounds are much worse than in practice. Is this because the analysis is sloppy or loose? Are there any lower bounds? Or is this maybe since many "real-world" data sets from the usual ML repositories are easy to approximate?
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the coreset construction for the decision tree problem. In the 2D k-decision tree problem, the goal is to partition the input n x m matrix into k submatrices (with some restrictions) such that the summation of the cost over all submatrices is minimized. This paper gives the first coreset construction: it outputs a small subset of indices of the matrix with new weights such that the cost of any decision tree over the coreset is a (1+-eps)-approximation of the cost over the input matrix. The running time is O(knm) and the coreset size is polynomial in klog(nm)/eps.
main_review: Pros:
-Decision tree is a fundamental problem in computer science. To the best of my knowledge, this paper gives the first coreset construction for the decision tree problem. Authors provided a novel partitioning scheme and connected it to the techniques in the theory of VC dimension. Such combination is non-trivial and I really like their partitioning algorithm which is simple and clever. 
-The algorithm is deterministic.
-The experiments showed that the running time can be significantly improved.
-The paper is well-written in general.

Cons:
-There is a lack of discussion of previous work which uses the techniques from PAC learning and VC dimension to construct coresets for other problems. For example, Feldman and Langberg STOC'2011 gives a unified framework to construct coresets for k-clustering by reducing estimating the clustering objective to the range query problem in the field of VC dimension. Although the technical details are totally different, the high level structures of the algorithms are similar: both first require a good bicriteria approximation, then partition the data and finally handle each part separately. 
-Although authors claim that the techniques can be easily extended to higher dimensions (tensors), there is no formal statements. I think the precise statements for coreset size and running time for higher dimension d would be really appreciated in most applications with feature dimension > 2. 

Other comments:
-What is the best possible dependency of the coreset size on k? I guess it is easy to prove that Omega(k) is a lower bound. But is linear dependence on k achievable? If we allow randomization, is it achievable?
-Typo: Definition 6 (i): "|\mathcal{B}|\leq c_1 n m" -> "|\mathcal{B}|\leq c_1"
limitations_and_societal_impact: I did not find any potentially negative societal impact of the work
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper provides a new perspective on scalability for computing decision trees, and discusses how to build coresets for these objects.  The problem is posed as a data set over R^d x R, and the goal is to decompose R^d into rectangles with constant values so that the sum of squared errors from each rectangle to the points within it is minimized.  
main_review: The paper devises a greedy approach.  It greedy decomposes data into contiguous sets columns with, then roughly the same procedure is applied on each column set, dividing into contiguous sets of rows.  It recurses alternating on dimensions.  The algorithm and examples seem to be described in the d=2 case, but the discussion and experiments apply to larger d (15 and 18).  

Given the multi-dimensional histogram found, (with small extension) standard decision tree (and even random forest) algorithms can be run, and can be much more efficient.  Experiments show only a small loss in quality (say 3%) with about a factor 10 reduction in space and time.  

There are some size bounds on the coreset assuming nice properties of the data.  The polynomial terms  in terms of log N  (Where N is the data set size) and k (the number of leaves) is not specified, but is constant.  


Overall, I like the idea for coresets for decision trees.  I can imagine a series of follow-on work to refine this work.  However, I have several concerns about this work itself:

 - the algorithmic description is not written in a way that is easy to understand.  It took several reads to (Hopefully correctly) decipher what I think is going on.  Also, it seems only described for 2 dimensions/features.  

 - there is related work in databases that looks at quite similar problems, and the relation is not discussed.  Namely work in R-trees and in sketching multi-dimensional histograms (e.g., https://dl.acm.org/doi/abs/10.1145/564691.564741 or https://dl.acm.org/doi/pdf/10.1145/564691.564741).  Given that this paper seems to propose a fairly simple greedy method, it would be useful to compare with this fairly extensive line of work.  

 - the paper claims a deep connection with partition trees, but does not really explain it in the main 9 pages.  I find this odd in that partition trees were mainly developed to deal with halfspace queries (of *any* orientation) and other objects which can be lifted to be halfspaces or composed of them.  There is a mostly different but parallel line of work that developed range queries techniques for axis-aligned queries, which seem to align with the axis-aligned rectangles used in decision trees and the proposed coresets.  

 - The paper's presented analysis is for a restricted set of decision tree problems.  It should work for any decision tree given that structure holds.  However, then experimentally they apply them to random forests.  It is not completely clear that (or how) the coresets apply to random forests.  There are two concerns: the multiple queries and the correlation between classifiers.  The first concern should probably be simple using a union bound or something.  But the second one I understand less - that is, if a coreset is too course, does it prevent the random forest from reaching as a high a precision since the difference between categories has been smoothed out.  
  On the other hand, even vanilla decision trees still have an important place in ML since they are very explainable and favored among scientists who want a procedural explanation.  (random forests do not have this advantage -- this may be slightly conflated in the introduction).  


Overall, I definitely like this direction, and I strongly encourage the authors to continue pursuing this.  However, I feel the writing of the paper could be significantly improved, so am not convinced this paper is ready for publication in NeurIPS.  
limitations_and_societal_impact: The authors did not engage on this topic.
review_title: null

Meta-review: The paper was considered to have technical novelty and strength as "absolutely above the bar" of NeurIPS. However, there were very substantial concerns about the writing quality of the paper, almost of the level of being considered unpublishable in the current form. The authors are highly encourage to polish the paper and address all the writing concerns from the reviews (including comparison to past work).
Decision: Accept (Spotlight)