Lattice partition recovery with dyadic CART
Authors: OSCAR HERNAN MADRID PADILLA
Yi Yu
Alessandro Rinaldo
Venue: NeurIPS 2021 Poster (2021)
Keywords: Classification and Regression Trees (CART)
Recursive Dyadic Partitions
Piecewise Constant Signals
Partition Recovery

Abstract: We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and  estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.~of estimating the partition of the lattice induced by the constancy regions of the unknown signal, using the computationally-efficient dyadic classification and regression tree (DCART)  methodology proposed by \citep{donoho1997cart}.   We prove that, under appropriate regularity conditions on the shape of the partition elements, a DCART-based procedure consistently estimates the underlying partition at a rate of order $\sigma^2 k^* \log (N)/\kappa^2$, where $k^*$ is the minimal number of rectangular sub-graphs obtained using recursive dyadic partitions supporting the signal partition, $\sigma^2$ is the noise variance, $\kappa$ is the minimal magnitude of the signal difference among contiguous elements of the partition and $N$ is the size of the lattice. Furthermore,  under stronger assumptions, our method attains a sharper estimation error of order $\sigma^2\log(N)/\kappa^2$, independent of $k^*$, which we show to be minimax rate optimal.  Our theoretical guarantees further extend to the partition estimator based on the optimal regression tree estimator (ORT) of \cite{chatterjee2019adaptive} and to the one obtained through an NP-hard exhaustive search method.  We corroborate our theoretical findings and the effectiveness of  DCART for partition recovery in simulations.

Lattice partition recovery with dyadic CART
Oscar Hernan Madrid Padilla
Yi Yu Department Statistics
Department of Statistics University California, Los Angeles
University of Warwick yi. www.wwwww..c...mo ac
oscar o madrid@stat. wulpssttttttt..........e..e.. ucla. edu
Alessandro Rinaldo
Department of Statisties & Data Science Carnegie Mellon University
arinaldo@cmu.er edu
Abstract
We study piece-wise constant signals corrupted by additive Gaussian noise over a d-dimensional lattice. Data of this form naturally arise in host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e. of estimating the parti- tion of the lattice induced by the constancy regions the unknown signal, using the computationally--fficee -efffiicill dyadic classification and regression tree (DCART) methodology proposed by [4] We prove that, under appropriate regularity condi- tions the shape of the partition elements, a DCART-based procedure consistently estimates the underlying partition
rate of order "² log NN/x², where k- is the minimal number of rectangular sub-graphs obtained using recursive dyadic partitions supporting the signal partition, o² is the noise variance, i the minimal magnitude of the signal difference among contiguous elements of the partition and is the size of the lattice. Furthermore, under stronger assumptions, our method attains sharper estimation error of order o² (Ng(2)/k²² independent of k*, which we show to minimax rate optimal. Our theoretical guarantees further extend to the partition estimator based the optimal regression tree estimator (ORT) of [12] and to the one obtained through an NP-hard exhaustive search method. We corroborate theoretical findings and the effectiveness of DCART for partition recovery in simulations.
Introduction
Suppose we observe noisy realization of structured, piece-wise constant signal supported over d-dimensional square lattice (or grid graph) La,n = {l,..., n1) Data that can be modeled this
manner arise several application areas, including in satellite imagery [e.g. . 30 37, computer vision [e.g. [ 33), medical imaging [e.g. 26 22), and neuroscience [e.g. 16] 32]. Our goal is to estimate the
constancy regions the underlying signal. Specifically, we assume that the data y IR hain are such that, for each coordinate i La,..
yi == 07 G.
where ( E Ld,n)) are i...d. (O o²) noise variables and the unknown signal 0" E BRba is assumed be piece-wise constant
unknown rectangular partition of Ld,.- We define a subset
R C Lan to be a rectangle if R = _ [a, where (a, = {j E Z : a S j < 6}. a. e Z. rectangular partition of Ld,ns P, is a collection of disjoint rectangles {Ri} La satisfying UREPR R Ld,n- To each vector in La,a, there corresponds a (possibly trivial) rectangular partition.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Figure 1: Rectangular partitions associated vector not necessarily unique.
Definition A rectangular partition associated with a vector 0 E RR is a rectangular partition (RiheeL of In such that 0 takes on constant values over each Rı. For a vector 0 RLa,", we let k(0) be the smallest positive integer such that there exists rectangular partition with k(0) elements and associated with O.
In this paper, we are interested in recovering a rectangular partition associated with the signal 0 in (I) A complication immediately arises when d 2 2: the rectangular partition associated with given l is not necessarily unique. This fact illustrated Figure where the left-most plot depicts the lattice supported vector 0, consisting of rectangle of elevated value (in grey) against background (in white). For such we show three possible rectangular partitions, each of which comprised of five rectangles (the second, third and fourth plots). In fact, the partition recovery problem is well defined, as long as we consider coarser partitions comprised by unions of adjacent rectangles instead of individual rectangles: see Definition 2
below for details. We remark that this issue does not occur in the univariate (d = 1) case, for which the partition recovery task has been thoroughly studied in the change point literature; see section 1.3 below. Thus, assume that d 2 2.
For the purpose of estimating the rectangular partition associated with 0* (or, more precisely, its unique coarsening as formalized in Definition 2, we resort to the dyadic classification and regression tree (DCART) algorithm of [14. This is polynomial-time
braee- algorithm developed for de-noising purposes for signals over lattices, and is variant of the classification and regression trees (CART) 77. See Section T.T below for a description of DCART. The optimal regression trees (ORT) estimator, recently proposed in [2], further builds upon DCART and delivers sharp theoretical guarantees for signal estimation while retaining good computational properties though we should mention that in our experiments we have found DCART to be significantly faster. Both DCART and its more sophisticated version ORT can be seen as approximations to the NP-hard estimator
arg minlee"'.... {2~ ly - 0112 Ak(O))
where k(f) is given in Definition 1 || the vector (or Euclidean) 4--norm and X >> 0 tuning parameter. DCART modifies the above, impractical optimization problem by restricting only to dyadic rectangular partitions. This leads to significant gains in computational efficiency without sacrificing on the statistical performance, Indeed, decisionn-reeebaae be optimal under various settings for the purpose of signal estimation; further demonstrate their effectiveness for the different task of partition recovery. In particular, we show how simple modifications of the DCART (or ORT) estimator yield practicable procedures for partition recovery with good theoretical guarantees and derive novel localization rates.
algorithms have been shown to 222 20 In this paper,
Note that, there is a wide array of applications focusing on detecting the regions rather than estimating the background signals, especially in surveillance and enviromment monitoring. Our work is motivated by all the applications/problems considered in the large literature on biclustering, where the underlying signal assumed to be piecewise constant. Estimating the boundary the partition is the most refined and difficult task in these settings. Thus, any of the many scenarios in which biclustering is relevant can be used to motive our task. An analogous observation holds also for the more general problem of identifying an anomalous cluster (sub-graph) in network, problem that has been tackled (for testing purposes only) by [4) the reference therein provide numerous examples of applications. On a high-level, the relationship between the partition and signal recoveries can be thought of the relationship between the estimation consistency and support consistency in a high- nigh-dimensional linear regression problems. They be done by almost identical algorithms but the theoretical results rely on different sets of conditions.
The paper is organized follows. In the rest of this section we formalize the problem settings and the task of partition recovery, and describe the DCART procedure. We further summarize our main findings and discuss related literature. Section 2 contains our main results about one- and

---

two-sided consistency of DCART and its modification. In Section 2.3 we derive a minimax lower bound stemming from the case of one rectangular region of elevated signal against pure background. Illustrative simulations corroborating our findings can be found in Section 3 The Supplementary Material contains the proofs.
Notation
We set N ndd the size of the lattice Ld,,, where we recall that d is assumed fixed throughout.
For any integer m E N", let [m]] = [m. Given a rectangular partition II of Ld let S(1)) be the linear subspace of Rd consisting of vectors with constant values on each rectangle in II and let (-(m)(-) be the orthogonal projection onto S(IT). For any R C T=d,n and 0 E IR Lai, let R = - fz. where - is the cardinality of a set. Two rectangles R1, Rg adjacent if there exists 1 [d] such that RS and Rg share a boundary along e and one is subset of the other in the hyperplane defined by et. the Ith standard basis vector in Rd. See Definition [S1 for a rigorous definition. This concept of adjacency is specifically tailored to and in fact only valid for dyadic (and hierarchical, in the sense specified by (12)) rectangular partitions, which are most relevant for this paper. For any subsets A, B C Ld define dist B) = mi ||a bl]- Throughout this paper, will use the E--norm the vector norm.
are said be
1.1 Problem setup
We begin by introducing two key parameters for the model specified TT and a well-defined notion of rectangular partition induced by 8".
Definition 2 (Model parameters, induced partitions) Let 0* as in 1p and (R] j[[m)] be rectan- gular partition of Ldd, associated with 6* Consider the graph G = (E", V*), where V = [m]] and E" = =(i,j) pk; RRzz R and R are adjacent). Let {C} he(r) be all connected components of G and define A = (0")) = {Ubec; Bi............................ Ujecz U as the partition (not necessarily rectangular) induced by dr, We say that the union of rectangles Usec; Rt and Ujec; Riz, s,t t E [L], s + t, are adjacent, if and only if there exists (i.j) E C2 x Ct such that R and R2 are adjacent.
Let is and A be the minimum jump size and minimal rectangle size, respectively, formally defined as
K
min BE A,BEA"00;40, 10- 05 and A "minn Rg]. JE(m)
is important to emphasize the difference between partition associated with 8", as described in Definition [ which may not be unique, and the partition A induced by H* of Definition 2 which is instead unique and thus describes a well-defined functional of 8*. The parameters λ and capture two complementary aspects of the intrinsic difficulty of the problem of estimating A#: intuitively, one would expect the partition recovery task to be more difficult when x and A are small (and o is large). Below, we will prove rigorously that this intuition is indeed correct. When d 1, both parameters, along with o,, have in fact been shown to fully characterize the change point localization task: see, e.g. [36] 35).
The partition recovery task can therefore be formulated that of constructing an estimator Î of A*, the induced partition of 0*, such that, as the sample size N grows unbounded and with probability tending to one,
A | and dHoua (,A') A max min |AAB| 0,
(3)
AEA BEA
where AAB is the symmetric difference between A and B. We refer to dHaus (A, as the localization error for the partition recovery problem.
The dyadic classification and regression trees (DCART) estimator. In order to produce a compu- tationally efficient estimator of A" satisfying the consistency requirements 3.. we deploy the DCART procedure [14, which can be viewed as an approximate solution to the problem in (2). Instead of optimizing over all vectors in R La.., DCART minimizes the objective function only over vectors asso- ciated with a dyadic rectangular partition, which is defined as follows. Let R = Ilee[a [a:, bi] C La, be rectangle. A dyadic split of R chooses coordinate [d]. [ the middle point of [a,, by]. and
3

---

splits R into
R1 = II Ja by] x 1x
II [a by] and R2 = 1,(++1,d]
II 2E x-
[a byl x 1,, x
II 1EG+1,44
[as, bel,
xEG-1
with [0] = [c2, c = 0. 02 > C1 Assuming that n is a power of 2, starting from Ldnr itself, we proceed iteratively follows. Given the partition [Rutkeljk, one chooses rectangle R, and performs a dyadic split on R, that leads to the largest reduction in the objective function. Any partition constructed through sequence of such steps is called dyadic rectangular partition. With pre-specified À > 0, the DCART estimator is
S (V), where IT i = 0
arg min Ie Plyaddd
12-
where P P.yadic.d.n is the set of all dyadic rectangular partitions of Ld As shown in [4] and [12]. the DCART estimator can be obtained via dynamic programming with computational cost of (
Given any solution to 4 natural (though, as we will see, sub-optimal) estimator of the induced partition of 0" is II, the partition associated with the resulting DCART estimator Ó. Importantly, by the property of DCART, and using the fact that the Gaussian errors have Lebesgue density, II is in fact a dyydiicreetangullr partition and unique with probability one, and thus the resulting estimator well-defined. (Equivalently, the partition associated with @ and the one induced by 0 coincide.)
1.2 Summary of our results
We briefly summarize the contributions made in this paper.
One-sided consistency DCART. Though DCART is known to be minimax rate-optimal es- timator [12], for the task of partition recovery its associated partition II has sub-optimal performance. Indeed, due the nature of the procedure, it is easy construct cases in which the DCART over-partitions. See Figure 2] In these situations, DCART falls short with respect to the target conditions for consistency described in (3) Nonetheless, is possible to prove weaker one-sided consistency guarantee, in the sense that every resulting DCART rectangle is almost con- stant. In detail, let R = Htem be the rectangular partition defined by II in (4). Then, we show in Section 2.1 that, for any R, E RR there exists S; C R3 such that 07 0 u, E S, and Σiem m) RR S S x x=20 (f") log (N). Throughout, the quantity kayad (f") refers to the smallest positive integer & such that there is belyaadde-eettanull---airiiiii with 0*
of Ld,a associated
Two-sided consistency of DCART: A two-step estimator. In order to resolve the unavoidable over- partitioning issue with the naive DCART partition estimator and in order to prevent the occurrence of spurious clusters, we develop more sophisticated two-step procedure. In the first step we use variant of DCART that discourages the creation of rectangles of small volumes. In the second step, we apply a pruning algorithm merging rectangles when their values are similar and the rectangles not far apart. With probability tending to
N + 0o, the final output À satisfies (3) with dHaus (A, < o-222kkyad (0=) log(N). This result is the first of its kind in the setting of lattice with arbitrary dimension d 2 2. This is shown in Section 2.2
Optimality: A regular boundary case. In Section 2.3 we consider the special case in which, for each rectangle in the rectangular partitions induced by 6* only has O(1)-many rectangles within distance of order o²x PP-"Rkaydd (@*)) log(NV. While more restrictive than the scenarios we study in Sections 2.T and 2.22 this setting is broader than the ones adopted in the cluster detection literature [e.g. 2 In this case, with probability approaching one as N + oo, the estimator À satisfies (3) and dHass A*) < 2222 log(N) This error rate is shown to be minimax optimal, with a supporting minimax lower bound result in Proposition
1.3 Related and relevant literature
The problem at hand is closely related to several recent research threads involving detection and estimation of structured signal. When d 2, our settings can be viewed as generalization of those used for the purpose of biclustering, i.c. detection and estimation of sub-matrices. Though

---

relatively recent, the literature on this topic is extensive, and the problem has been largely solved, both theoretically and methodologically. See, e.g.. (28]
18
13
and
28
In the more general settings postulating structured signal supported over a graph (including the grid graph), sharp results for the detection problem of testing the existence of a sub-graph or cluster which the signal is different from the background are available in the literature: see, [3] [2], M
15 and others, focused on de-noising the data and upper-bounding ||0 6" |l.. where is an estimator of 8 and ||~ is some vector norm. In yet
Concerning the estimation problem, 34
another stream of work (e.g. 19 22 concerned with empirical risk minimization, the problem usually formulated as identifying single subset. More discussions can be found in Section [ST]
What sets our contributions apart from those in the literature referenced above, which have primarily targeted detection and signal estimation, is the focus on the arguably different task of partition recovery. As a result, the estimation bounds we obtain are, to the best of our knowledge, novel as they do not stem directly from the existing results.
It is also important to mention how the partition recovery task can be cast univariate change point localization problem. Indeed, when d = 1, the two coincide; see [6 335. However, the case of d 2 2 becomes significantly more challenging due the lack of a total ordering over the lattice. Consequently, our results imply also novel localization rates for change point analysis in multivariate settings.
2 Consistency rates for the partition recovery problem
In this section, we investigate the theoretical properties of DCART and of a two-step estimator also based on DCART for partition recovery. We remark that instead of DCART, it is possible to deploy the ORT estimator [12 or the NP-hard estimator (2) in our algorithms. Our theoretical results still hold by simply replacing the term kayad (0*), in both the upper bound and the choice of tuning parameters, with the smallest k such that there is a phicrarchiccll-rcttannllaar
(Khier (0*) )) or k-rectangular-parttioo (k(O")) )) of Ld,-. associated with 0", respectively. Thus, using these more complicated methodologies that scan over larger classes of rectangular partitions will result in smaller upper bounds in Theorems and See [12 for details about the relationship of k(0*), kdyad and (inee((")))
2.1 One-sided consistency: DCART
As illustrated in Figure 2 the DCART procedure will produce too fine partition in many situations, even the signal is directly observed (i.e., there is no noise). Thus, the naive partition estimator based on the constancy regions of the DCART estimator 0 as in { will inevitably suffer from the same drawback. Nonetheless, it is still possible to demonstrate one-sided type of accuracy and even consistency for such a simple and computationnally-effiieee estimator. Specifically, in our next result show that in every dyadic rectangle supporting the DCART estimator, 0" has almost constant mean. The reverse does not hold however, as there is no guarantee that every rectangle in the partition induced by the true signal 0 mostly covered by one dyadic DCART rectangle.
Theorem Suppose that the data satisfy ① and that θ is the DCART estimator 4 obtained with tuning parameter X= = Coo² log(N), where C' > O is sufficiently large absolute constant. Let (R3 (Rg))yen j be the associated partition. For any E [k(0)), let S₁ C Rí be the largest subset of R, such that 0 is constani on Sy. Then there exist absolute constants C1, C1,C2, Ca, Ca, Cs >> O such that, with probability at least C1 exp(- C2 (o), the following hold:
global one-sided consistency:
Σ JE(K(O)
|R,SS1| -2 ooaK-add (f0) log(N);
(5)
local one-sided consistency: for any j E [k(00), R2 \S + 0, then
R CaRy" - 0² Kakaaa ( (0Rz) log((N)
(6)
5

---

The left panel is the true signal. The first dyadic split always cuts rectangle into two and ends up with over-partitioning, with the right panel as an example.
Figure 2:
where 85 = men, :0000 10 - 07 and
control on over-partitioning:
(0))= S 2hddadd (0*) + Cs.
(7)
We remark that k-(0) kayad (0) due to the construction of f. Theorem consists of three results. We have mentioned the over- wver-partitioning issue of DCART. The bound ( shows that the over-pavee verrpartitionnng is upper bounded, in the sense that the size of the partition induced by DCART is in fact of the same order of the size of the dyadic rectangular partition associated with e".
For each resulting rectangle Ry (6) shows that it is almost constant, in the sense that if the signal possesses different values in Ry. then RS includes a subset Sj which has constant signal value and log((V), where Ki the smallest jump size within Ry. We note that since kayad (0xz) S kayad (0*). if (ay) ( is assumed to constant as in the cluster detection literature [e.g. 44. then for general d E N" (6) has the same estimation error rate that in the change point detection literature [e.g. 35)
the size RR \ SyI upper bounded by K, 2 (0
The result in 6 provides an individual recovery error, with the individual jump size Kj. while paying the price kayad (0,,) ). In (5) we show that globally, when we add up the errors in all resulting
rectangles, the overall recovery error is of order x 2 (0") log(N). When d = 1, [35] shows the minimax rate of the Li-aasserteein distance between the vectors of true change points and of the change point estimators of order x- x==0² K, where Comparing with this result, 5 can be seen as delivering a "one-sided" nearly optimal rate, saving for a logarithmic factor.
the true number of change points.
In the change point localization case, i.e. when d = 1. one can show that k(0 R, S 3 [see, e.g. 36 just assuming mild conditions on A. However, soon as d 2 2 this is no longer the case. As an illustration, consider the left plot of Figure 2 where the whole rectangle Rg and the white one in the middle is Sy. Without further constraints each component, having only conditions A will not prevent very fragmented boundary, which can increase the term Aayaa(O), in (6)
2.2 Two-sided consistency: A two-step estimator
As we have seen Section 2.1 despite having the penalty term À II| to penalize over werrpartitioning in the objective function ④ since the optimization of DCART only restricts to all dyadic partitions, the naive DCART estimator still suffers from over-partitioning. To address this issue, we propose a two-step estimator which builds upon DCART and merges the corresponding rectangles if they are close enough and if their estimated means are similar. The procedure will not only be guaranteed to return, with high probability, the correct number of rectangles in the partition induced by the signal 0", but also fulfill the target for (two-sided) consistency specified in (3)
The two-step estimator. Our two-estimator starts with constrained DCART, prohibiting splits resulting in rectangles that are too small. The first step estimation defined as
=00sth (v),
= O
with π E
arg min
{2 [yy - Os( (v) + A
(8)
Me (n)
where >1, > are tuning parameters and d (1) is the set of rectangular partitions where every rectangle is of size at least 77.
The second step merges rectangles the partition associated with the estimator from the first step to overcome vver-partitioning. To be specific, let (Ri (Ri (e((()) be a rectangular partition of I.d

---

associated by 0. For each (i,j) [k(0]] x [k(0)), i j, let ((.)) = =
dist(R Rg) S
(9)
and
1
Σ (Y +
Y2,)²
+ A2
Σ (Yi (R--R.OR,).. IERUUR;
(10)
2
IER,
LER;
where 22 is a tuning parameter; otherwise, we let ((i.j) With this notation, let {(i.j) [k:0)] x [x(0): =((J) = and let (Ci) be the collection of all the connected components of the undirected graph (I+(0)), E). The final output can be written as
A = {USEC, Ry Ry ,EC, R₂ R.).
(11)
Notice that the main computational burden is to find the DCART estimator which has cost of O(N). From the output of DCART, the computation of the quantities (9) and (10) can be done in ((k(0)²). Before describing the favorable properties of the estimator, we state our main assumption.
Assumption IfA, B E A with A + B and 0 Üz. then we have that
dist(A, B) 2 ckdyad (0" )n -22 '===0pp log(N),
(12)
for some large enough constant Furthermore, we assume that
k A > chidyad Jo² log(N).
(13)
Assumption simply states that if elements of A have the same signal values then they should be sufficiently apart from each other. Assumption also specifies a signal-to-noin ratio type of condition. When d = 1, it is well known the change point literature [e.g. (36] that the optimal noise ratio for localization is of the form R² A 2 o² log( The condition in (13) has an additional kayad (0*) factor.
an interesting open problem to determine whether this additional term can be avoided when d 2 2.
Theorem 2 Assume that Assumption
D holds, Suppose that the data satisfy ① and À is the two-step estimator, with tuning parameters A1 C1a² log(N), N), x2 = C2kayad (0" )a log(N and
Cikayad (0" J0²x log(N) In S/c2.
(14)
where C1, C2 C1, C2 > are absolute constants. Then with probability at least N o holds that
A = A and dHaue (A, & fo"==-2kyadd log(N),
(15)
where c, C are absolute constants.
Theorem shows that the two-step estimator overcomes the over-partitioning issue of DCART and is consistent for the partition recovery problem provided that x k=aoaak (0*) logg()og))))))) - 0. The resulting estimation error is of order at most x -2 kayad(f") log(NV).
In view of Assumption I and Theorem 2 intuitively speaking, (14) ensures that if there are two separated regions where the signal takes the same value, then the they should be far apart; otherwise, our algorithm would not be able to tell if they should be merged together or keep separated. Eq. (15) requires that the signal strength is large enough. Technically speaking, if (14p changed to another quantity, denoted by w. then the final result of Theorem 2 would be
d (,A') < C ((w ( A) d²x Kayaa log(N))
where the term w A A due to the definition of A. This means that the final rate in Theorem is determined jointly by Assumption [ and optimal rate.
There are three tuning parameters required by the two-step estimator. Practical guidance on how to pick them will be provided in Section S6.2. The tuning parameter λ₁ in 8 is the same as the one in (4) and their theoretical rates are determined by the maximal noise level of a Gaussian distribution over all possible rectangles using union bound argument. The tuning parameter d2 is used in

---

the merging step [00,, penalizing over vertitatitioning. Since the candidate rectangles in (TO) are the estimators from the first step, these rectangles carry the estimation error from the first step. An intermediate result from the proof of Theorem 2 Junveils a similar result to Theorem I that for each R2 involved in (0)) there exists a subset S C R2 having constant signal values satisfying that
Σ (E(K())
R oo kayad (0") log(NN.
This suggests that the right choice for A2 should he able to counter this extra (fy) factor. Finally, the tuning parameter 1/ appears twice in the estimation procedure:
lower bound the size of the rectangles obtained in first step as (8) and as an upper bound on the distance between two rectangles in ( see (14). The value 7) should be at least as large the one-sided upper bound on the recovery error, in order to ensure that over-partitioning cannot occur. As the same time, it should not be chosen too large, or otherwise the procedure may erroneously prune small true rectangles. By this logic, should not exceed the minimal size of the true rectangles; this is indeed the upper bound in condition (T4). Finally, we would like to point out that, similar conditions are even necessary in some change point localization (d = 1) procedures, see [e.g. 36].
In practice, one may be tempted abandon the tuning parameter 7, and only prune the DCART output using (TO). If one still wants the result to satisfy (3. then stronger conditions are needed and worse localization rates are obtained. We include this result in Section i4 the supplementary material.
2.3 Optimality in the regular boundary case
We use two-step procedure to improve the partition recovery performances of DCART and show the error is of order x o- kayaa (8*) log(N) natural question order is whether one can further expect to improve this rate. In Proposition 3
we show minimax lower bound result.
Proposition 3 Let fyi satisfy 7 and
=K, i;
0 =0, 0,
if Ld, SS
(16)
where C. Ld,n is a rectangle and |S| A Let PRAA. denote the corresponding joint distribution. Consider the class of distributions
P = K.A.
A A N/2, x² A/0² 2 2log(N)/63
Then for N 2 26, it holds that inf suppeps Ep
|SAS]] 2 (ok=2)og(NN/333 where the infimum
over all estimators $ of S.
Theorem 3 shows that when the induced partition 0= consists of one rectangle and its comple- ment, i.e. when kayaa (0*) O(1), the minimax lower bound on the estimation error is of order n ==20 (N). Recalling the estimation errors we derived for DCART and the two-step estimator in Theorems ladd 2 when kayya (0*) = 0(1), the results thereof are minimax optimal.
The assumption kayad = O(1) is fairly restrictive, though, using our notation, the case of |A*| = 2 in fact used in the cluster detection literature 34 In fact, in order to achieve the optimal estimation rate indicated in Theorem 3 we only need a boundary regularity condition, in the sense that for every rectangle in the partition induced by 0", there are only Ol1)-many other rectangles nearby. This condition is formally stated in Assumption 2
Assumption 2 There exists constant C, c O such that any A A it holds that
[[B AMMA) dist(A, A, B) S - "Kayad (f*) log(N) H S C.
Assumption 2 asserts that within es 2 (0*) (N distance, each element of A only has O(1)-many elements nearby. This condition shares the same spirit of requiring the cluster boundary to be bi-Lipschitz function in the cluster detection literature [c.g. 2

---

Table I: Performance evaluations over 50 repetitions under different scenarios. The performance
metries dist, and distz are defined in the text. The numbers parenthesis denote standard errors.
Setting
dist
dist2
Setting
dist:
distz
TV.hased
X
TV.huedd
7
TV-
Ä TV-hased
51.6(21.9)
0.0k0.0)
0.1(0.3)
0.5
462. 462.6(637.77
418.6(246.9)
0.2(0.4)
0.4(0.6)
1
1.0
(46.1()).88)
582.3(2429.5)
0.000.2)
0.3(0.5)
1.0
2617.7(:047.7)
8630.6(6049.3)
0.7(0.6)
1.4(0.7)
1.5
(98.0(878.7)
4513.6(5970.9)
0.1(0.3)
0.5(0.5)
1.5
4706.7(5213.7)
11477.3(5213.6)
1.2/0.9)
1.910.4)
3
62.1(231.4)
123.0(44.1)
0.060.1)
0.210.4)
0.5
86.30
52.8(21.7)
0.200.4)
0.3(0.4)
8
1.0
150.8(227.3)
1012.7(752.5)
0.1(0.3)
0.7(0.5)
1.0
119.6(189.3)
87.8(82.0)
0.2(0.4)
1.1(1)
3
270.8(479.0)
12732.6(3296.88
0.2(0.5)
1.900.4)
1.5
399.3(437.1)
217.6/233.5)
0.4(0.7)
1.4(1)
Corollary Assume that Assumptions 1 and 2 hold. Suppose that the data satisfy I and À
is the two-step estimator defined in 11I, with tuning parameters d C1o21og(1 N), X2
C2lidyya (0 jo² log(N) and Cı kayad )o²) log(N) S "f S A/2,, where 01, C2 C1 C2 >
absolute constants. Then with probability at least 1 S, it holds that [A] A and
Goo2og((M
max min ALA'S MEA AEA
min k(O)), BEA dist(A,B) hayma log(N) BB/n
R2
(17)
where c, C are absolute constants. In particular, in x and |A for all A E A", then
dHaus (A, S Co²k log(N).
(18)
Corollary 4 shows that even if kayad (0*) is diverging as the sample size grows unbounded, one can still achieve the minimax optimal estimation error rate x =0² log(N), with properly chosen tuning parameters and additional regularity conditions on the partition. An interesting by-product in deriving this rate is (17), which characterizes the effect of the number of nearby rectangles in the estimation error for individual elements in A
3 Experiments
In this section, we demonstrate in simulation the numerical performances of the two-step estimator for the task of partition recovery. The code is by courtesy of the authors of [12] and all of our experiments are done in 2.3 GHz 8-Core Intel Core 19 machine. Our code can be found in wtthtttt:/// : //git thub com/ com/hernanmp/ PactiemmppPaaatttt Patttattiiioooo cetartitioo_rrroverrr
We focus the naive two-step estimator detailed in Section S4 and denoted here as A. The implementation details regarding choice of tuning parameters are discussed in S6.2
We adopt dist; ditaus (A, A*) and dist2 || depicted in Figure we report the mean and standard errors of dist, and distz over 50 Monte Carlo simulations.
|| as the measurements. For each scenario
As a competitor benchmark, we consider a similar pruning algorithm based on the total variation estimator 227 33), namely TV-based, instead of ours based on DCART. The implementation details are discussed Section 3
For each scenario considered, we vary the noise level as E {0.5, 1.5] and set (d, n) (2, 2²). In each instance, the data are generated as y NN(6', o² I'IL..)). Detailed descriptions are in Section S..I] and visualizations of the signal patterns are in the second column in Figure 3 while the third and fourth columns depict 0, the DCART estimator, and 0, our two-step estimator, respectively. We can see that our two-step estimator correctly identifies the partition and improves upon DCART for the purpose of recovery partition. It is worth noting that even when the partition is not rectangular, as shown in the second row in Figure 3 our two-step estimator is still able to accurately recover good rectangular partition.
From Table we see that in terms the metric distg our two-step estimator outperforms TV-based estimator in all cases. Furthermore, the same is also true for most cases in terms of the metric dist

---

Figure 3: From top to bottom: Scenarios 4. From left to right: instance of y, the signal 0" DCART, and DCART after merging. In each case the data are generated with 1.
4 Conclusions
this paper we study the partition recovery problem over d-dimensional lattices. We show how simple modification of DCART enjoys one-sided consistency. To correctly identify the size of the true partition and obtain better consistency guarantees, we further propose more sophisticated two-step estimator which is shown to be minimax optimal in some regular cases.
Throughout this paper, we discuss partition recovery on lattice grids. In fact, deal with non axis-aligned data, one can construct a lattice in the domain of the features, average the observations within each cell of the lattice and ignore the cells without observations. More details can found in the supplementary materials.
Finally, an important open question remains regarding the necessity include the factor kayad (0*) in the signal-to-noise condition (13) and in the estimation rates. We leave for future work to investigate what the optimal estimation rates are in general when (0") is allowed to diverge.
Supplementary material
The supplementary material contains all the technical details, additional simulation results and code of this paper.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: NSF DMS 2015489 and EPSRC EP/V013432/1.
10

---

References
[1] Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, and Gábor Lugosi. On combinatorial testing problems. The Annals Statistics, 38(5):3063-300 2010.
[2] Ery Arits-Castro, Emmanuel Candes, and Arnaud Durand. Detection of an anomalous cluster in network. The Annals of Statistics, pages 278-304, 2011.
[3] Ery Arias- Castro, Emmanuel Candes, Hannes Helgason, and Ofer Zeitouni. Searching for a trail of evidence in maze. The Annals of Statistics, pages 7726-1757, 2008.
[4] Ery cisas-Cattro, Emmanuel Candès, and Yaniv Plan. Global testing under sparse alternatives: Anova, multiple comparisons and the higher criticism. The Annals of Statistics, 39():35333 2556, 10 2011.
[5] Ery Castro and Yuchao Liu. Distribution-free detection of submatrix. Journal of Multivariate Analysis, 156:29-38. 2017.
[6] Jia JiaWang Bian, Wen- Wen-Yan Lin, Yasuyuki Matsushita, Sai-Kit Yeung, Tan-Dat Nguyen, and Ming- Ming Cheng. Gms: Grid-based motion statistics for fast, ultra-robust feature correspondence. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4181 -191- 2017.
[7] Leo Breiman, Jerome Friedman, Charles Stone, and Richard A Olshen. Classification and regression trees. CRC press, 1984.
[8] Victor-Emmanuel Brunel. Adaptive estimation of convex polytopes and convex sets from noisy data. Electronic Journal of Statistics, 7:1301-1327, 2013.
[9] C. Butucea, Y. I. Ingster, and A. Suslina. Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix. ESAIM: Probability and Statisties, (19):115-134 2015.
[10] Cristina Butucea and Yuri Ingster. Detection of a sparse submatrix of high-dimensional noisy matrix. Bernoulli, 19(5B):2652-2663 11 2013.
[11] Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Computational and statistical boundaries for submatrix localization in large noisy matrix. The Annals of Statistics, 45(4):1403 1430, 2017.
[12] Sabyasachi Chatterjee and Subhajit Goswami. Adaptive estimation of multivariate piece- wise polynomials and bounded variation functions by optimal decision trees. arXiv preprint /911. 1566,, 2019.
[13] Yudong Chen and Jiaming Xu. Statisicullcoomputaatinnaal tradeoffs in planted problems and submatrix localization with growing number of clusters and submatrices. Journal of Machine Learning Research, 17:27:1-27:57, 2016.
[14] David I. Donoho. Cart and best-ortho-basis: a connection. The Annals of statistics, 25(5):1870- 1911, 1997.
[15] Zhou Fan and Leying Guan, Approximate 4n-penll estimation of piecewise-constant signals on graphs. The Annals of Statisties, 46(68):3217-3245, 2018
[16] Evelina Fedorenko, John Duncan, and Nancy Kanwisher. Broad domain generality focal regions of frontal and parictal cortex. Proceedings of the National Academy of Sciences, 2013.
110(41):16116-1662)
[17] Chao Gao, Yu Lu, Zongming Ma. and Harrison H. Zhou. Optimal estimation and completion of matrices with biclustering structures. Journal of Machine Learning Research, 17(161):1-29, 2016.
[18] Bruce Hajek, Yihong Wu, and Jiaming Xu. Submatrix localization via message passing. Journal of Machine Learning Research, 18(186):1-52, 2018.

---

[19] Qiyang Han. Global empirical risk minimizers with "shape constraints" " are rate optimal in general dimensions. arXiv preprint wrXiv:795..12825 2019.
[20] Abhishek Kaul. Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees. arXiv preprint arXiv:2105.0001, 2021.
[21] Mladen Kolar, Sivaraman Balakrishnan, Alessandro Rinaldo, and Aarti Singh. Minimax localization of structural information in large noisy matrices. In J. Shawe-Taylor, R. S. Zemel,
L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 909-919991 917. Curran Associates, Inc., 2011.
[22] Aleksandr P Korostelev and Aleksandr B Cybakov. Asymptotically minimax image reconstruc- tion problems. Sonderforschungsberrich 123, 1991.
[23] Andrew Lang, Aaron Carass, Peter A Calabresi, Howard S Ying, and Jerry L. Prince. An adaptive grid for graph-based segmentation in retinal oct. In Medical Imaging 2014: Image Processing, volume 9034, page 903402. International Society for Optics and Photonics, 2014.
[24] Yuchao Liu and Ery Arias-Castro. A multiscale scan statistic for adaptive submatrix localization. arXiv preprint arXiv: / 996.000844.44 2019.
[25] Zongming Ma and Yihong Wu. Computational barriers in minimax submatrix detection. The Annals of Statistics, 43(3))1089 1116, 2015.
[26] Vincent Roullier, Olivier Lézoray, Vinh-Thong Ta, and Abderrahim Elmoataz. Multi-resolution traph-based analysis of histopathological whole slide images: Application to mitotic cell extraction and visualization. Computerized Medical Imaging and Graphics, 35(7-8):603-615. 2011.
[27] Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1 14):2299---68 1992.
[28] Andrey A. Shabalin, Victor J. Weigman, Charles M. Perou, and Andrew B. Nobel. Finding large average submatrices in high dimensional data. The Annals of Applied Statistics, 3(3)9885- 1012, 2009.
[29] James Sharpnack, Aarti Singh, and Alessandro Rinaldo. Sparsistency of the edge lasso over graphs. In Artificial Intelligence and Statistics, pages 1028-1036. PMLR, 2012.
[30] Jonathan R Stroud, Michael Stein, and Shaun Lysen. Bayesian and maximum likelihood estimation for gaussian processes Graphical Statistics, 26( )): -20888-120,20 2017.
incomplete lattice. Journal of computational and
[31] Xing Sun and Andrew B. Nobel. On the maximal size of large-average and ANOVA-fit submatrices in Gaussian random matrix. Bernoulli, 19(1):275 294, 2013.
[32] Wesley Tansey, Oluwasanmi Koyejo, Russell Poldrack, and James G Scott. False discovery rate smoothing. Journal of the American Statistical Association, 1 113(523):1156-177) 2018.
[33] Wesley Tansey and James G Scott. A fast and flexible algorithm for the graph-fused lasso. arXiv preprint
2015.
[34] Ryan J Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. The annals of statistics, 39(3):1335 1371, 2011.
[35] Nicolas Verzelen, Magalie Fromont, Matthieu Lerasle, and Patricia Reynaud- Bouret. Optimal change-point detection and localization. arXiv preprint arXiv:2010.1 1/400, 2020.
[36] Daren Wang, Yi Yu, and Alessandro Rinaldo. Univariate mean change point detection: Penal- ization, cusum and optimality. Electronic Journal of Statistics, 14())1911-1191, 2020.
[37] Timothy G Whiteside, Andrew J Esparon, and Renée E Bartolo. A semi-automated approach for quantitative mapping of woody cover from historical time series aerial photography and satellite imagery. Ecological Informatics, 55:101012, 2020.
12

---

[38] Sascha Wirges, Tom Fischer, Christoph Stiller, and Jesus Balado Frias. Object detection and classification in occupancy grid maps using deep convolutional networks. In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pages 3530-3535. IEEE, 2.
13


Reviews:
[{"review_id": "w_22TmW92z8", "reviewer": "Reviewer_2a7D", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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?\n\nAdditionally 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.\n\nAlso 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.\n\nBeyond that point I believe that the manuscript is well written and overall thorough and clear. \n\n\"partition recover problem\" -> \"partition recovery problem\"\n\n\n\n------------- UPDATE AFTER DISCUSSION -------------\n\nI 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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Tg4PCFZ0D8y", "reviewer": "Reviewer_qw8i", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nHowever, 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.\n\n- 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?\n\n- 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)$?\n\n- 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\". \n\n- 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?\n\n- 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?\n\n- In Theorem 2, I think there are typos, one should be $\\lambda_1$ and another $\\lambda_2$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "BS8Bgqp2IVc", "reviewer": "Reviewer_ZZUp", "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.\n\nThe contributions of the paper are threefold:\n\n(i)\tThe 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.\n\n(ii)\tIn 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.\n\n(iii)\tThey prove that the proposed 2 step estimator is minimax optimal if the number of partitions is constant.\nFinally, they demonstrate the efficacy of their algorithm by simulations.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nWhile 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.\n\nQuality: 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. \n\nClarity: The paper is fairly well written. It is well organized and includes all the details.\n\nSignificance: 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.\n\nMinor points-\n\n(i)\tI 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?\n\n(ii)\tLine 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.\n\nOverall 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There does not seem to be any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}]

Author rebuttal:

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)