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.wwwwk..c...mo ac
oscar o madrid@stat. wulpstttttttt..........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 Rha,", 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; Ri............................ 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 oo2K-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 SEC, 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)a( 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,r is a rectangle and |S| A Let PRAA. denote the corresponding joint distribution. Consider the class of distributions
P = K.A.
A A < x² A/0² 2 log(NN/6}
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 Ci 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:7955.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": "aeNtCPKp8Zl", "reviewer": "Reviewer_SRUt", "summary": "The authors consider the problem of recovering the partition underlying a piecewise constant function over a $d$-dimensional lattice, _i.e._, a signal with support $L_{d,n} = \\lbrace 1, \\dots, n\\rbrace^d$. That is, we wish to recover the structure such that within each rectangular partition of the lattice, the function $\\theta^* \\in \\mathbb{R}^{L_{d,n}}$ is piecewise constant, from noisy measurements ${y_i = \\theta_{i}^* + \\epsilon_i}$ for $i \\in L_{d,n}$ where $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma^2)$ i.i.d. A straightforward formulation would be NP-hard, so they the consider the dyadic CART (DCART) algorithm, which simplifies the search space by restricting it to partitions that can be formed by repeated bisections of partitions, starting with a single partition containing all $N = n^d$ points in the lattice.\n\nThe authors provide a number of bounds of the form $\\sigma^2 k_{\\mathrm{dyad}}(\\theta^*) \\log(N) / \\kappa^2$, where $\\kappa$ is the minimum jump size (difference between signal in adjacent partitions) of $\\theta^*$. First, they show that using DCART, the number of lattice points in recovered partitions where the true signal is not actually piecewise constant scales at most with the above expression (\"one-sided consistency\"). They then propose a two-step estimator that adds a step merging rectangles in recovered partitions whose measurements are \"close\" to each other, and show that under certain assumptions, the Hausdorff distance between the recovered (estimated) partition and the actual partition (accounting for the need to merge rectangles to assure definitional uniqueness) scales at most with the above expression. Finally, they provide a simple example to demonstrate an order-matching lower bound.", "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": "**Clarity:** The ideas were mostly comprehensible, but I felt that a lot of the definitions would have benefited from more straightforward explanations than were given in Section 1.1. I appreciate that while the ideas are simple, the lattice- and graph-based nature of the problem makes it challenging to keep notation succinct. Nonetheless, I felt that the underlying ideas weren't that esoteric (which is good), but the descriptions made them feel more dense than necessary for a reader without extensive familiarity with this area of research. My suggestion would be that more diagrams like Figures 1 and 2 to explain notions like induced partitions, dyadic splits and the like would be disproportionately helpful.\n\nAt the same time, I wanted to acknowledge that there were certainly useful discussions in the paper, for example, the discussions in lines 186–193 and 267–276 are appreciated. Also, the notation itself was consistent and clear throughout, so nothing was ambiguous or notationally confusing, it was just that some of the ideas came across as requiring a lot of abstract setup.\n\nA minor structural suggestion: The definitions of $\\kappa$ and $\\Delta$ should be separated from the rest of Definition 1, because the notion of induced partitions is a heavy (even if intuitive) concept in its own right.\n\n**Quality:** Theorem 1 looks sound to me.\n\nFor Theorem 2, I notice that the assumptions in Assumption 1 have the same scaling as the Theorem 2 result, and I would have appreciated some discussion of this in the main paper (not relegated to supplementary). The assumptions are briefly explained, but the choice of scaling here is not, and one naturally wonders if the result of Theorem 2 follows from whatever is assumed in Assumption 1. I'm sure there is a good explanation for this and it is not a simple matter of, \"whatever you assume in Assumption 1 is what comes out in Theorem 2\", but I thought this was quite a critical detail and it would be helpful for the authors to address it. On the other hand, the core ideas for the two-step estimation are comfortably explained in lines 231–249 and this is helpful.\n\nFor Proposition 3, I would appreciate a discussion of how the example offered relates to Assumption 1. I see that it vacuously satisfies (12) (since no such $A, B$ exist) but the (13) wasn't immediately obvious to me. If I'm not mistaken, Assumption 1 makes the recovery problem easier, so any example for a lower bound that doesn't satisfy the assumption could be too conservative, and hence not relevant to Theorem 2. This is probably a straightforward misunderstanding—I suspect the clarification here will be brief and I look forward to hearing it.\n\nFor the experiments, although the experiments are straightforward I think they give some idea of what is going on. However, I felt the discussion of the evaluation was overly brief. What was it about setting 2 that made it more challenging under the $\\mathrm{dist}_1$ metric, but not the $\\mathrm{dist}_2$ metric? It is good that standard errors were reported, but some of the standard errors are very large—do the error bars between the two comparted methods overlap? The noise level is reported but the \"signal level\" (I suppose by this I mean $\\Delta$) was not clearly indicated—I had to zoom in a lot to see the numbers on the color bars in the second column. I felt that it wasn't clear from the experiments that the theoretical findings of the authors were mirrored in experiments.\n\nI didn't peruse the supplementary material, other than to quickly check Theorem S1 and Assumption S1 and to try and get some idea of how the expressions in Assumption 1 were motivated (I didn't succeed on the last part), so I haven't checked the proofs in detail.\n\nFinally: A quick discussion on (what is known, if anything) about the relationship between the task of estimating $\\theta^*$ and partition recovery would be useful. Do better partition recoveries tend to support lower $\\lVert \\hat\\theta - \\theta^* \\rVert$, or vice versa, or are they so fundamentally different that it is easy to imagine examples where one task is extremely easy and the other is very difficult?\n\n**Originality/Significance.** I am not sufficiently familiar with the surrounding literature to provide a confident assessment of how original this is given the prior art, so the following is mostly a guess. However, the authors were clear about their focus on partition recovery and the case $d \\ge 2$, and how this relates to prior work, and I'm satisfied that this is a novel contribution. I think there is a lot to build on here, and I think the direction taken by the authors is a probably a good contribution to our understanding of the recovery of piecewise constant signals. What is much less clear to me is the degree to which the case $d > 3$ is valuable, since all of the examples of applications given are imagery based and in these contexts I'm only aware of up to 3 (spatial) or maybe at most 4 (including color) dimensions. So I couldn't be confident that the authors' extension to general $d$ will be of wide interest.\n\n**Typos:** (for benefit of authors, not part of assessment)\n- Line 127: \"DACRT\"\n- Line 129: \"of _he_ procedure\"\n- Line 148: \"broader _then_ the ones\"\n- Line 239: Should $(i,j)$ in the definition of $E$ be $c$ (or vice versa)?\n- Line 252: should the second $\\lambda_1$ be $\\lambda_2$?\n\n_Edit, 02 Sep 2021: Raise rating from 5 to 6, as discussed in comments/responses below._", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is almost entirely theoretical in nature and I don't foresee any direct societal impact as a result of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Vh7rFZyqC2V", "reviewer": "Reviewer_jHsk", "summary": "In this work the authors consider the problem of learning the partition of a\npiecewise constant signal supported on a $d$-dimensional lattice $\\{1, \\ldots,\nn\\}^d$.  They assume access to a noisy signal $y = \\theta^\\ast + \\epsilon$, where\n$\\epsilon \\sim \\mathcal{N}(0, \\sigma^2 I)$ is a Gaussian noise vector and\n$\\theta^\\ast$ is the true signal that is assumed to be piecewise constant\nover a rectangular partition of the latice.  The goal is to recover the\nunderlying partition.  This work focuses on the performance of (variants of)\nthe Dyadic CART (DCART) algorithm for the task of partition recovery.\n\nPrior work [1] has shown that the DCART estimator achieves the optimal error\nfor the task of recovering the true signal $\\theta^\\ast$.  The authors argue\nthat the partition produced by the vanilla DCART algorithm may contain a large\nnumber of rectangles.  However, they show that inside each rectangle of the\npartition of the vanilla DCART, the signal is indeed almost constant.  The\nsecond result of this work proposes simple modifications for DCART so that the\ncorresponding partition is close to the true underlying partition.  In\nparticular they enforce a lower bound on the size of the rectangles of DCART\nand, at the end, merge cells that are close and have similar value.  They show\nthat the modified DCART algorithm outputs a partition at distance roughly\n$\\sigma^2 k^\\ast \\log(N) / \\kappa^2$, where $N = n^d$ is the size of the grid,\n$\\kappa$ is the minimum signal difference between contiguous cells of the true\nsignal, and $k^\\ast$ is the minimum number of dyadic cells required to create a\npartition consistent with the true signal.  The authors show a lower bound of\n$\\sigma^2 \\log(N)/\\kappa^2$ for the error. Therefore, their upper and lower\nbounds differ by a factor of $k^\\ast$.  Finally, the authors are able to remove\nthe extraneous factor $k^\\ast$ under the additional assumption that the\nunderlying partition is not very dense, i.e., around every rectangle of the\ntrue underlying partition there are not many other rectangles.\n\n\n[1]: Sabyasachi Chatterjee and Subhajit Goswami\nAdaptive estimation of multivariate piecewise polynomials and bounded variation functions by optimal decision trees", "questions": "", "limitations": "", "rating": 6, "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": "There is a lot of recent research studying estimation of structured signals;\nthe model and the problem proposed in this work fit in this line of research.\n I think it is an interesting observation that DCART tends to \"over-partition\" signals.  \nHowever, I found the proposed fix of (roughly) merging the cells produced by DCART a bit\nstraightforward.  Another weak point of this work is the gap of $k^\\ast$ in the\nupper and lower bounds.  I think it would be interesting to bound the error of\nsome (possibly) innefficient estimator for this problem in order to have a\nbetter benchmark for the perfomance of DCART.  Overall, the paper is\nwell-written and the presentation of the results and assumptions clean.  Since\nthe problem is interesting and a well-known algorithm is studied, I believe that\nthis work is above the threshold but I would not push for it to be accepted.\n\n\nQuestions/Comments\n\nI believe it would be beneficial for the paper to add some more high-level\ndiscussion on the difference of partition estimation and recovering the whole\nsignal, applications of partition recovery, etc. \n\nIs it easier to bound the error of some inefficient estimator (for example the NP-Hard\nestimator of Equation (2)) for this problem?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "-NnHPs00kCJ", "reviewer": "Reviewer_mM4N", "summary": "This article investigates the problem of the recovery of constancy regions of a noisy high dimensional piecewise constant signal. The authors proposed to use the DCART estimator to build up a rectangular partition and proved a weak consistency result. Then, they proposed a two steps estimator based on an appropriate merging of the rectangles that DCART output. For this variant (DCARTAM), they proved consistency: the estimator converges to the ground truth partition in the sense of Hausdorff (after an appropriate normalization by the number of rectangles in the partitions). \nFinally, DCART and DCARTAM were compared to the TV-based estimator empirically using two metrics. The first one is the Hausdorff distance between the estimator and the ground truth partition, and the second one is the difference between the cardinality of the estimator and the cardinality of the ground truth partition. Visually, DCARTAM seems to be superior to DCART. Moreover, DCARTAM seems to be superior to the TV-based estimator using the second distance, yet it does not show a systematic superiority if the first distance was used.", "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": "Overall, the big picture and the intuitions behind the results were well-explained. Moreover, the empirical results look promising. However, the statements of the results are heavily technical and ambiguous: for example, it is unclear how the result of Theorem 2 implies the consistency of DCARTAM: the upper bound (15) ( even taking into account the inequality (14)) is not enough to prove the consistency as defined by (3).\nThere are some further remarks/suggestions:\n- In practice, the two steps estimator requires the evaluation of (9) and (10) to be implemented, which seem to be computationally expensive. It would be interesting to add a complete analysis of the complexity of this algorithm.\n- It would be interesting to illustrate the optimality of the upper bounds by numerical simulations that show the dependency on N.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of recovering the partition of a piecewise constant signal supported on a multi-dimensional lattice.
Specifically, the true signal is assumed to be piecewise constant over an unknown rectangular partition of the lattice. Given access to noisy measurements, the goal is to recover the underlying partition. This work analyzes the performance of the Dyadic CART algorithm for this task. Overall, modulo some issues with the presentation, the reviewers agreed that this work is slightly above the acceptance threshold.
Decision: Accept (Poster)