Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies a problem called lattice partition recovery, where piecewise constant signals over a d-dimensional lattice are corrupted by noise and require to be recovered. A method called dyadic classification and regression tree (DCART) is studied. It is shown that DCART achieves one-sided consistency, but suffers from over-partitioning. To achieve partition recovery, this paper proposes an additional merging stage, where dyadic rectangles that are close are merged. This is shown to achieve partition recovery under mild conditions. A minimax lower bound is also given, and numerical experiments are shown to support the methodology.
main_review: This paper studies a very interesting and fundamental statistical estimation problem. It appears that this paper provides a natural improvement of DCART so that partition recovery is achieved. It is further supported by solid theory and experiments. I think that this paper could make a potential impact in the statistical and machine learning community.

However, there is certain ambiguity in the description of the method. This may be caused by the page limit, but I do hope the authors would clarify some points from a possibly quick revision.

- What is exactly the space of partitions in the optimization problem (4) and (8)? Does the space contain all the possible choices of rectangle $R_u$ in each split? If so, then the space can be quite large, is that correct? What is the size of the space?

- Following the previous question, how do we find the optimizer of (4) and (8) algorithmically? Do we do greedy splits, or do we search the space exhaustively? The reference [14] says the algorithm has complexity $O(n^2)$ in 2-D grid. So here the algorithm has complexity $O(n^d)$?

- On line 178--179, it is unclear what it means by "instead of DCART, it is possible to deploy the ORT estimator [12] or the NP-hard estimator (2) in our algorithms". 

- It seems to me, intuitively, that the penalty $\lambda_1 | \Pi |$ in (8) already discourages over-partitioning. Why do we need the additional merging step to achieve partition recovery?

- In the merging stage, we merge, say, rectangles $R_i$ and $R_j$. From (9), they are close but they are not required to be neighbors. Is that a bit strange?

- In Theorem 2, I think there are typos, one should be $\lambda_1$ and another $\lambda_2$.
limitations_and_societal_impact: Not applicable
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose to study the use of CART to recover the partition underlying piecewise constant noisy data. They perform empirical validation and provide extensive theoretical analysis of the algorithm showing its benefits and pitfalls.
main_review: The main critic I have is the lack of motivation in the task of recovering the underlying partition of the data. Can this be employed to then produce better denoising for example by finding new criterion that would make the tree converge faster?

Additionally a discussion on dealing with non axis-aligned partition would have been appreciated. For example to see how good/bad can this estimator become in the worst case and what could be some simple strategies to mitigate this (like oblique trees?). This is not missing from the current manuscript but would have elevated the impact of the paper.

Also the experiments are missing cases in which the piecewise constant regions have different support sizes between regions. This seems like an important case to study especially to know which conditions the data need to follow in order to have best performances. It seems that as the number of regions grows (and their size reduces) for the true data, as the CART produced partition would potentially diverge whenever the noise std is not negligible. Also, it seems that some naive baselines (e.g. low pass denoising followed by thresholding) allowing to recover the data partition would have helped to measure the actual benefit of the proposed algorithm.

Beyond that point I believe that the manuscript is well written and overall thorough and clear. 

"partition recover problem" -> "partition recovery problem"



------------- UPDATE AFTER DISCUSSION -------------

I thank the authors for their answers, I have updated my score as I believe that with those discussions, the paper would be above the acceptance level, **especially the link between partition geometry and performances**. One last thing that would be very interesting (even though probably only to be discussed in a future work/discussion section alongside with non-axis aligned data) is on how one could combine the proposed approach with decision trees that can be learned in a differentiable way (e.g. https://ieeexplore.ieee.org/document/817409, https://arxiv.org/pdf/1702.07360.pdf).
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers a piecewise constant signal on a $d$-dimensional lattice. The observed signal is corrupted by additive Gaussian noise. The task is to recover the partition of the lattice such that the signal within a partition is constant. The paper proposes an algorithm that builds upon the scalable DCART algorithm.

The contributions of the paper are threefold:

(i)	The authors first analyze the performance of the vanilla DCART algorithm to recover the partitions. They prove the one-sided consistency of the vanilla DCART algorithm. One-sided consistency guarantees that the recovered partitions have large subsets which have constant signal, but a partition of the ground truth signal could potentially be over-partitioned by the DCART algorithm. They demonstrate by an example that it is indeed the case.

(ii)	In order to address the issue of over-partitioning, the authors propose a two-step algorithm where the first step is the vanilla DCART algorithm while restricting to partitions with size above a threshold. In the second step, the partitions which are close and whose signals have a small difference are merged. They prove that this estimator is consistent.

(iii)	They prove that the proposed 2 step estimator is minimax optimal if the number of partitions is constant.
Finally, they demonstrate the efficacy of their algorithm by simulations.

main_review: Originality: The authors tackle the problem of partition recovery for a general dimensional lattice which (most likely) has not received attention before. An important question that authors do not address in the paper is why is it an interesting problem to recover the partition, what are the settings where having an estimate of the signal itself is not good enough? Furthermore, it is not clear how distinct is the task of partition recovery from that of signal recovery. When we have access to the exact signal, recovering the partition from the signal is easy. Similarly, one could potentially perform a simple post-processing step after signal reconstruction where one merges the neighboring lattice points with close estimated signal values to form a partition. A clearer discussion on these lines would help in motivating the problem better.

While the DCART algorithm itself is not new, its application to the task at hand and the theoretical analysis is novel. The paper clearly delineates itself from previous work and the related work is well cited.

Quality: The paper is technically sound and the proofs are clear and interesting. The authors do bring up the issue of the estimator being minimax optimal only under the restrictive setting of $k_{dyad}(\theta^*)$ being constant. I believe that this is a significant bottleneck, especially as $d$ scales. For instance, if the partitions are hypercubes, the number would grow exponentially in $d$. Thus, the suboptimality could potentially be very large. 

Clarity: The paper is fairly well written. It is well organized and includes all the details.

Significance: The results are important because the paper uses the scalable DCART algorithm for a new task. It would really help the paper if more thought goes into motivating the problem.

Minor points-

(i)	I could not really understand what the second sentence of Definition 1 was trying to say. It switches from $\theta \in \mathbb{R}^{L_{d,n}}$ in the first sentence to $\theta \in {L_{d,n}}$ in the second sentence. Probably $k(\theta)$ is the smallest cardinality of $\{R_l\}$ defined in the first sentence?

(ii)	Line 327 onwards – the signal patterns are in the second column the third and fourth column depict the vanilla DCART and the 2 step estimator respectively.

Overall I really like the technical contributions of the paper but the paper is held back by the lack of motivation of the problem and the suboptimality of the estimator.

limitations_and_societal_impact: There does not seem to be any potential negative societal impact of this work.
review_title: null

Meta-review: The paper provides an interesting framework for studying the problem of partition recovery for piecewise constant signals (in dimension >1). They propose a few modifications to the DCART algorithm and prove a few interesting theoretical results about their proposed algorithm. Given that the authors address the concerns of the reviewers satisfactorily, the paper should be accepted for presentation at Neurips.
Decision: Accept (Poster)