Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel
Authors: Yutong Wang
Clayton Scott
Venue: NeurIPS 2022 Accept (2022)
Keywords: Ensemble methods
kernel methods
interpolation

Abstract: Recent research in the theory of overparametrized learning has sought to establish generalization guarantees in the interpolating regime. Such results have been established for a few common classes of methods, but so far not for ensemble methods. We devise an ensemble classification method that simultaneously interpolates the training data, and is consistent for a broad class of data distributions. To this end, we define the manifold-Hilbert kernel for data distributed on a Riemannian manifold. We prove that kernel smoothing regression using the manifold-Hilbert kernel is weakly consistent in the setting of Devroye et al. 1998. For the sphere, we show that the manifold-Hilbert kernel can be realized as a weighted random partition kernel, which arises as an infinite ensemble of partition-based classifiers.

Consistent Interpolating Ensembles via the Manifold-Hilbens Kernel
Yutong Wang University of Michigan yutongweumi ch. edu
Clayton D. Scott University of Michigan clayscot@umich edu
Abstract
Recent research in the theory overparametrized learning has sought to establish generalization guarantees in the interpolating regime. Such results have been estab- lished for a few common classes of methods, but so far not for ensemble methods. We devise ensemble classification method that simultaneously interpolates the training data, and is consistent for a broad class of data distributions. To this end, define the manifold manifold-Hilbert Hilbert kernel for data distributed manifold. We prove that kernel smoothing regression and classification using the manifold- kernel are weakly consistent in the setting of Devroye al. [22]. For the sphere, we show that the manifold-Hilbon kernel can be realized weighted random partition kernel, which arises infinite ensemble of partition-based classifiers.
Riemannian
Introduction
Ensemble methods are among the most often applied learning algorithms, yet their theoretical properties have not been fully understood [12). Based on empirical evidence, Wyner et al. [42) conjectured that interpolation of the training data plays key role in explaining the success of AdaBoost and random forests. However, while a few classes of learning methods have been analyzed in the interpolating regime 6 ensembles have not.
Towards developing the theory of interpolating ensembles, we examine an ensemble classification method for data distributed on the sphere, and show that this classifier interpolates the training data and is consistent for a broad class of data distributions. To show this result, we develop two additional contributions that may be of independent interest. First, for data distributed kernel K H. a manifold extension of the Hilbert kernel [39]
Riemannian manifold
M, we introduce the manifold-
Under the same setting as Devroye al. (22). we prove that kernel smoothing regression with K M weakly consistent while interpolating the training data. Consequently, the classifier obtained by taking the sign the kernel smoothing estimate has zero training error and is consistent.
Second, we introduce class of kernels called weighted random partition kemnlls. These are kernels that can be realized as an infinite, weighted ensemble of partition- histogram classifiers. Our main result is established by showing that when M So the d-dimensional sphere, the manifold- Hilbert kernel a weighted random partition kernel. In particular, we show that on the sphere, the manifold-Hill Hilbert kernel is weighted ensemble based on random hyperplane arrangements. This implics that the kernel smoothing classifier a consistent, interpolating ensemble on Sd. To our knowledge, this is the first demonstration of an interpolating ensemble method that is consistent for broad class of distributions in arbitrary dimensions.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

P2
D( P1)
M P2)
(
ú(x D KM
(1))
Figure 1: An example of the weighted infinite-ensemlle [(x|] D", KT) (defined in Eqn. 4 of his-
togram classifiers h(r]]] D", P) (defined in Eqn. 2). The partitions Pi, , P2 are induced by hyperplane arrangements (denoted by dotted lines).
1.1 Problem statement
Consider the problem binary classification on a Riemannian manifold M. Let (X, Y) be random variables jointly distributed on M x {+1}. Let D == {(X,, YO) be the (random) training data consisting of i.i.d copies of X.Y. A classifier, i.e., a mapping from D to function f() : M + {=1]. has the anterpolating-connitter
property if, when X has a continuous distribution, both of the following hold: 1) f(X,ll Y,, for all E (1....,n] n). and 2) Pr(S(X)+Y) in probability
inf Pr(f(XIID") XY} [-M-{=1) measurable
+ co.
Our goal is to find an interpolating-conse
ensemble of histogram classifiers, to be defined below.
partition on M,, denoted by P, is set of subsets of M such that P Pn p for all P. P' P and M = -UPEP P. Given r E .M, let P[x] denote the unique element P E P such that x E P. The set of all partitions on a space M is denoted Part(M). The histogram classifier with respect to D over
P is the sign of the function [[ D" P) M + RR given by
D P) = Σ Y, Me E P(X,))
where is the indicator function. See Figure left panels.
Definition 1.1. A weighted random partition (WRP) over M is 3-tuple (θ, G.a) consisting of (i)
parameter space of partitions: set ④ where Pe E Part(M) for each 6, (ii) random partitions: a probability measure & on O, and (iii) weights: a nonnegative function a θ + R2 that is integrable with respect to the measure Q. Example 1.2 (Regular partition
the d-cube). Let M = [0, 1]d and = (1.2...) N4. For each n E N., denote by P,, the regular partition of M into n d-cubes side length 1/n. For any probability mass function Q on N+ and weights N - Rzo, the 3-tuple (0, B, a)) is WRP.
Below, WRPs will be denoted with 2-letter names in the sans-serif font, e.g., "rp" for generic WRP, and "ha" for the weighted hyperplane arrangement random partition (Definition 5.1) The weighted random partition kernel associated rp (9, Q a) is defined
KPP .M x M + Rzo U [oo), K (I, z) == Es (o][] E Pa[=]]]-
(3)
When a = L, we recover the notion of unweighted random partition kernel introduced in [1]] Note
that the kernel is symmetric since If E p I(z e Po(x]]}. If KP < oc, then KTP is a positive definite (PD) kernel. When KP can evaluate to oc, the definition of PD kernel is not applicable since the positive definite property is defined only for to kernels taking finite values (10).
Let agn [Ro {+1) be the sign function. For a WRP, define the weighted infinite-ensemble
n
d< D KP Σ Y: K (z. X2) Ee-q /a (0)) Po)].
Note that the equality on the right follows immediately from linearity of the expectation and the definition of hi("] Pe) in Equation See Figure right panel.
Main problem. Find WRP such that sgn ( (f(* (P) has the cetepollatig-consisttee property.

---

1.2 Outline of approach and contributions
In the regression setting, we have (X, Y) jointly distributed on M x R. Let m(x) :- - z].
Recall from Belkin et al. [8] Equation (7)] the definition of the kernel smoothing estimator with
so-called singular kernel K M M [0, +oo]:
Y
Bi E [m] such that X;
Σド K(x, >
(5)
K(,
otherwise.
We note that Equation 5 is referred as the Nadaraya- Walson estimate in Now, we simply write mi (1)) instead of DD" K) when there is no ambiguity. Similarly, we write (x)) instead of ū D" K) from earlier. Note that sgn (f,(())
(gn(2n if ンØ= K(, X,) 0.
Observe that m, is interpolating by construction. Let μax denote the marginal distribution of X. The Ln-error of m, in approximating m is Jn : JM mm (z) m=x) pa (dx). For M R& and the quul (z, 2) == || - =|| Devroye et al. [22) proved L1 Li-onssisyynyy for regression: J, + 0 in probability when Y is bounded and X is continuously distributed.
Hilbert kernel defined by K
Our contributions. Our primary contribution is to demonstrate an ensemble method with the property. Toward this end, in Section[] we introduce the manifold- Hilbert on a Riemannian manifold M. When show that when M is complete, connected, and smooth, kernel smoothing regression with K has the same consistency guarantee (Theorem 3.2) as KH, mentioned in the preceding paragraph. Section 5 we consider the case when M S and show that the manifold-Hilbes kernel K is a weighted random partition kernel (Proposition 5.2).
consistent-interollaan
kernel K H
Devroye et al. [22] Section 7] observed that the In In-consistency of m, for regression implies the consistency for classification of sgn 7, Furthermore, m, is interpolating for regression implies that sgn o U, is interpolating for classification. These observations together with our results demonstrate the existence of weighted
classifier with the pherpolating-consitteee property.
1.3 Related work
Kernel regression. Kernel smoothing regression, or simply kernel regression, is an interpolator when the kemel used is singular, a fact known to Shepard (39] in 1968. Devroye et al. [22] showed that kernel regression with the Hilbert kernel is interpolating and weakly consistent for data with a density and bounded labels. Using singular kernels with compact support, Belkin et al. showed that minimax optimality can be achieved under additional distributional assumptions.
Random forests. Wyner et al. [42 proposed that interpolation may be key mechanism for the success of random forests and gave a compelling intuitive rationale. Belkin et al. (6) studied empirically the double descent phenomenon in random forests by considering the generalization performance past the interpolation threshold. The PERT variant of random forests, introduced by Cutler and Zhao (20). provably interpolates in 1-dimension. Belkin et al. [7] pose interesting question whether the result of Cutler and Zhao (20) extends to higher dimension. Many work
have established consistency of random forest and its variants under different settings 15
38
However, none of these work addressed interpolation.
Boosting, For classification under the noiseless setting (i.e., the Bayes error is zero), A AdaBoost is interpolating and consistent (see Freund and Schapire [26, first paragraph Chapter 12]). However, this setting is too restrictive and the result does not answer if consistency is possible when fitting the noise. Bartlett and Traskin (5) proved that AdaBoost with early stopping universally consistent, however without the interpolation guarantee. To the best of our knowledge, whether AdaBoost or any other variant of boosting can be interpolating and consistent remains open.
Random partition kernels. Breiman [16] and Geurts et al. (28) studied infinite ensembles of simplified variants of random forest and connections to certain kernels. Davies and Ghahramani (21) formalized this connection and coined the term random partition kernel. Scoree (37) further developed the theory of random forest kernels and obtained upper bounds on the rate of convergence. However, it is not clear if these variants of random forests are interpolating.
'The "singular" modifier refers the fact that K (Ir, x)) +oo for all x M.
3

---

Previously defined (unweighted) random partition kernels are bounded, and thus cannot be singular. On the other hand, the Hanifold-Hilber kernel is always singular. To bridge between ensemble methods and theory on interpolating kernel smoothing regression, we propose weighted random partitions (Definition T.I whose associated kernel (Equation 33 can be singular.
Learning on Riemannian manifolds. Strong consistency of a kernel-based classification method on manifolds has been established by Loubes and Pelletier (32). However, the result requires the kernel to be bounded and thus the method is not guaranteed to be interpolating. See Feragen and Hauberg 25 for a review of theoretical results regarding kernels on Riemannian manifolds.
Beyond kernel methods, other classical methods for Euclidean data have been extended to Riemannian manifolds, e.g., regression [40]. classification [4), , and dimensionality reduction and clustering To the best of our knowledge, no previous works have demonstrated an interpolating- consistent classifiers manifolds other than TR..
44 34
In many applications, the data naturally belong to a Riemannian manifold. Spherical data arise from range of disciplines in natural sciences. See the influential textbook by Mardia and Jupp [33] S4J. For applications of the Grassmanian manifold in computer vision, see Jayasumana et al. 30) and the references therein. Topological data analysis [4] presents another interesting setting of conifold-values data in the form of persistence diagrams 3:31
2 Background on Riemannian Manifolds
We give intuitive overview of the necessary concepts and results Riemannian manifolds. A longer, more precise version of this overview is in the Supplemental Materials Section A.
A smooth d-dimensional manifold M is topological space that is locally diffeomorphic to open subsets of IRd, For simplicity, suppose that M embedded in RR for some N 2 d, e.g., S C Rd+1 Let E M be a point. The lungent space at x, denoted T2 M. is the set of vectors that is tangent to MM x. Since linear combinations of tangent vectors are also tangent, the tangent space Tz M is vector space. Tangent vectors can also be viewed as the time derivative of smooth curves. In particular, let x E M. If E > 0 is an open set and y (-c,e) + M is a smooth curve such that (0) I, then d1 at (0) E T.M.
A Riemanniun metric M is choice of inner product (., 122 T.M for each x such that T.M. The length of a piecewise smooth curve y [a, b] + M is defined by len(7) == Se (t) Define dist (I. {) == inf (1)e(7)) : y is a piecewise smooth curve from x to {). which a metric on M in the sense of metric spaces (see Sakai (36] Proposition 1.1]). For x E M and E (0, oo), the open metric ball centered at x of radius is denoted B (r, M) = {e E M dist (x, <r..
( )r varies smoothly with Naturally, | v 2z defines
A curve 7 [a, bj + M is geodesic if is locally distance minimizing and has constant speed, i.e., dy
M and v E T. are such that there exists geodesic y: [0, 1] + M where 7() = x and dy (0) = v. Define exp,, (v) := (1), the element reached by traveling along at time = See Figure 2 for the case when M = -2_
de (T)ll>(r) is constant. Now, suppose
at
For fixed z E M, the above function exp,.. the exponential map, can be defined on an open subset of T.M containing the origin. The Hopf-Rinow theorem [[3 Ch. 8, Theorem 2.8J) states that M is connected and complete with respect to the metric distM, then exp, can be defined on all of T.M.
3 The Manifold-Hilbert kernel
Throughout the remainder of this work, assume that M is complete, connected, and smooth Riemannian manifold of dimension d.
Definition 3.1. We define the manifold-Hilben kernel KH M x M + [0, oo) for each x, E E M by K (z. E) == dist (x) dd if x + & and KH (z, == oo otherwise.
?A diffeomorphism is smooth bijection whose inverse is also smooth.

---

1.
2.
3.
4.
5.
x
R2 = T,5² 2 Bo R
expr
log
S
x
An illustration of the exponential map exp, for the manifold M = S2 where is the "northpole" (blue) and -x the "southpole" (orange). The logarithm map log,, discussed in Section is a right-inverse to exp,, i.e,, exp, o log, is the identity. Panel I. The tangent space T,S²² visualized as g2. The dashed circle encloses disc of radius т. Panel 2. The tangent space realized as the hyperplane tangent to sphere at æ. Panels 3-5. Animation showing exp a bijection from the open disc of radius π to 8 \ {-I). The entire dashed circle in Panel i mapped to -r southpole. Thus, log, maps the southpole = to point on the dashed circle.
Figure 2:
Let AMr be the Riemann-Lebeseee volume measure of M. Integration with respect to this measure is denoted [M fd for function f M + R. For details of the construction AMs see Amann and Escher [1 Proposition 1.5J. When M = RR_ AM is the ordinary Lebesgue measure and JR fdAga is the ordinary Lebesgue integral. For this case, simply write À instead of Xqu.
now state our first main result, a manifold theory extension of Devroye et al. (22] Theorem 1].
Theorem 3.2. Suppose that X has density fx with respect to AM and that Y is bounded. Let Pr|x be a conditional distribution of Y given X and myjx be its conditional expectation. Let (x(x)) = fr ). Then
1. almost all M with fx(x) O, we have mx(x) - my) in probability. probability.
2. J, : J (x) myjx (=
In words, the kernel smoothing regression estimate m. based on the manifold-Hilber kernel is consistent and interpolates the training data, provided X has density and Y is bounded. As consequence, following the same logic as in Devroye et al. [22]. the associated classifier sgn o ün has the interpolating contsistentn property. Before proving Theorem 3.2 we first review key concepts in probability theory on Riemannian manifolds.
3.1 Probability on Riemannian manifolds
Let BM be the Borel o-algebra of M, i.e., the smallest o-algebra containing all open subsets of M. We recall the definition of M-valued random variables, following Pennec (35) Definition 2]:
Definition 3.3. Let (S2, IP, A) be probability space with measure IP and alagebra A. A M M-valued random variable X a Borel-menn measurable function Q > M, i.c., X XB) E for all E By.
Definition 3.4 (Density). A random variable X taking values in M has density if there exists nonnegative caarll-mcaurablle function f M + [0, oo] such that for all Borel sets B in M, we have Pr(X E B) = fg fdAM. The function f is said to be probability density function (PDF) of X.
Next, we recall the definition of conditional distributions, following Dudley [24 Ch. 10 $2]:
Definition 3.5 (Conditional d Let (X,Y) be random variable jointly distributed on M x R. Let Px(-) be the probability measure corresponding to the marginal distribution of X. A conditional distribution for Y given X is collection of probability measures Py]x(-1z) I indexed by x E M satisfying the following:
1. For all Borel sets A C RR the function M 9 x + Py (A E 10 is mers--
2. For all A C R and B C M Borel sets, Pr(Y A, E B) (Ax
The conditional expectation")
it is defined as myjx (x) == S y (dyl.))
also known as disintegration measures according to Chang Pollard [88
Moore often, the conditional expectation is denoted x æ). However, our notation is more convenient for function composition and compatible with that of 22

---

The existence of conditional probability for joint distribution (X, Y) is guaranteed by Dudley [24] Theorem 10.2.2]. When (X Y) has joint density fxy and marginal density fx. the above definition gives the classical formula Pyxx (A/x)) SA fxY v) (x))xx when co [x(x) 0.
See the first example Dudley 24 Ch. 10 $2).
Lebesgue points on manifolds
Devroye et al. [22] proved Theorem 3.2 when M = Rd and, moreover, that part holds for the so-called Lebesgue points, whose definition we now recall.
Definition 3.6. Let f M + be an absolutely integrable function and M. We say that is Lebesgue point of f if f(r) = lim,-0 (r,(B_() B.. fddas-
For integrable function, the following result states that almost all points are its Lebesgue points. For the proof, see Fukuoka [27] Remark 2.4].
Theorem 3.7 (Lebesgue differentation). Let f -M + R be an absolutely integrable function. Then there exists set A C M such that AM (A) and every M \ A is Lebesgue point of
Next, for the reader's 's convenience, we restate Devroye et al. 22 Theorem 1J, emphasizing the connection to Lebesgue points. The result will be used in our proof of Theorem 3.2 the next section.
Theorem 3.8 (Devroye et al. ). Let M Rd be the flat Euclidean space. Then Theorem 3.2
holds. Moreover, Part I holds for all x that is Lebesgue point to both fx and myjx fx.
4 Proof of Theorem 3.2
The focal point of the first subsection is Lemma which shows the Borel measurability of extensions of the so-called Riemannian logarithm. The second subsection contains two key results regarding densities of M-valued random variables transformed by the Riemannian logarithm. The final subsection proves Theorem 3.2 leveraging results from the preceding two subsections.
4.1 The Riemannian logarithm
Throughout, is assumed to be arbitrary point of M. Let U.M = E TTM: |o|, = = T.M denote the set of unit tangent vectors. Define function Tu U, - (0, oo) as follows 5
Ta (w) == st ft 0 distar (xp,,
The tangent cut locus is the set C₂ C M defined by č. = (Ta(u)u: E U,M, Tz(u) < co).
Note that it is possible for Ta (u) = do for all U.M in which case Cn is empty. The cut locus is the set Cp := (C,) C M.
The tangent interior set is I, = (tu S t < Tz(u), E U.M} and the interior set is the set I == (T.). Finally, define D2 == i U Note that for each = Lu E I, we have
| = = dist (z, exp,, = dist (x, (x).
(6)
Consider the example where 2 as in Figure 2 Then Tu (w) for all u E U, M. Thus, the tangent interior set I_ Bu ,,, R the open disc of radius x centered at the origin.
When restricted to i.. the exponential map expx li, i. + I, is diffeomorphism. Its functional inverse, denoted by log, lr, is called the Riemannian Logarithm 9 45 In previous works, log, l is only defined from I, to Ig. The next result shows that the domain of log, 11. Ig + I, can be extended to log, M + Dr while remaining Borel-measurable.
Lemma 4.1. For all E M, there exists Borel measurable map log, :M + T&M such that log, (M) C D and exp,, olog, is the identity on M. Furthermore, for all x, E M, we have dist (x. log, (E)]l..
Posiitivity of 7= is asserted Sakai 36 eq. (4.1))

---

Proof sketch. The full proof of the lemma is provided in Section A.2 of the Supplemental Material K Below, we illustrate the idea of the proof using the example when M S as in Figure 2
Let S be the "northpole" (the blue point). The tangent eut locus C2 is the dashed circle in the
left panel of Figure 2 The exponential map exp,, is one-to-one on D2 except the dashed circle, which all gets mapped to -2, the "southpole" (the orange point). A consequence of the measurable selection theoren is that log, can be extended be Borel-measurable right inverse of exp, by selecting point on C₂ such that log, (-x) 2,
Thus, we've shown that log," : :M - T M is Borel-measurable. Now, recall that Tę M is equipped with the inner product (5')a= i.e., the Riemannian metric. Below, for each x M choose an orthonormal basis on T. with respect to (.-). Then T M is isomorphic as an inner product space to Rd with the usual dot product.
Our next two results are Ofhange-of-variabeee formulas" for computing the densities/condiitonal distributions M-valued random variables after the log, transform. Recall that XM is the Riemann- Lebesgue measure on M and À is the ordinary Lebesgue measure on Rd = T,M.
Proposition 4.2. Let M be fixed. There exists a Borel measurable function V2 M - R with the following properties:
(i) Let X be random variable on M with density fx and let Z : log, (X). Then Z is a random variable on M.M with density fz(2) := (cxp,,,))) (xxpp,,,,,))
(ii) Let f M + IR be an absolutely integrable function such that is Lebesgue point of f- Define f T + by h(()) == [[eexxx - (x)) Then E T,M a Lebesgue
point for ht
Proposition 4.3. Let (X, have joint distribution M x R such that the marginal of X has a density fx on M. Let Pr (+1-) be conditional distribution for given X. Let x E M. Define / == log (X) and consider the joint distribution (Z, Y) on T,M x R. Then Priz(-1-) == (xxx(1/xxp,
a conditional distribution for given Z. Consequently, myjx o cxp, myjzz
The above propositions are straightforward manifold-theoretic extensions of well-known results on Euclidean spaces. For completeness, the full proofs are in Supplemental Materials Section A.4 An anonymous reviewer brought to our attention that Proposition 4.2 is the consequence of a well-known formula from geometric measure theory, called the area formula (2) p. 44-45].
4.2 Proof of Theorem 3.2
Fix . such that is a Lebesgue point of fx and myjx fx. Note that by Theorem 3.7 almost
all x E M has this property. Next, let Z = lx) and fz be as in Proposition 4 Then
1. fz = (fx o exp.) (vz o expx), and
2. (myjx o exp.) fz = (my exp.) (fx o expx) (vz expx).
Now, proposition 4.2 implies that 0 is Lebesgue point of both fz and (mylx expx) fzz Furthermore, by Proposition 4.3 we have myjx exp, = mylz. Thus, 0 is Lebesgue point of fz and mylz fz-
Now, let D, {(x, Yi) [a])- Define Z, log, (X,), which are i.dd copies of the random variable := log, (X). and let Dn = ((Z (.))s))))))))) Then we have
Σ = Y, dist (z, X,) (b)
En Y Z d
mxx D", K
==1 distM (z, (x)
Σ) 12
Σ == Y1 distg (0, Z;) -d
(c)
j==1 dist (0, 2,) m "",
6 "An revie reviewer has provided shorter, alternative proof of Lemma 4.1
See /tensttts:///eeerevvvee
net/
Kuratowski Nard-ward measurable selection theorem (see 14 Theorem 6.9.3)
7

---

where equations marked by (a) and (d) follow from Equation 5 (b) from Lemma 4.1 and (c) from the fact that the inner product space T with (, is isomorphic I& with the usual dot product. By Theorem 3.8 we have mi k + 2 (0) in probability. In other words, for all e > O,
lim Pr[[ D K (y) c) =0
100
By Proposition 4.3 we have my (0) - my z (exp, (0) = my)z(()) Therefore,
(m) Dr, K
my z (0) > |
M D", KM my (x) }
as events. Thus, m(
K + mylx converges in probability, proving Theorem 3.2 part 1.
As noted in Devroye et al. [22 $2]. part 2 of Theorem 3.2 is an immediate consequence of part 1.
5 Application to the d-Sphere
The d-dimensional round sphere Sd == for E Rd+1 : x +........ ..... 2241 = 1}. Here, a round sphere assumes that gd has the arc-length metric:
distga (x, 2) = (x, = cos (xT E [0.
Let S be a set and a . - S function. The partition induced by a is defined by {o {a-1(s) : Ra))e(a)). For example, when M = Sd and W E ld++1)xh, then the function ow gd + [=1] defined by ow (x) = sgn(W" (W WTTr 2)) induces hyperplane arrangement partition.
Let N = (1,2....] and No = N U {0} denote the positive and non-negative integers.
Definition 5.1 (Random hyperplane arrangement partition), Let d and M Sd. Let q be negative number, and let H be random variable with probability mass function РH No + [0, such that pn (h) > for all h. Define the following weighted random partition ha = (0, P.a):
1. The parameter space θ = - [dd+1)xh is the disjoint union of all (d + 1) h matrices. Element of are matrices
W 1)d+1)xh where the number of columns
{0, 1,...... } varies. By convention, if h = 0, the partition Pg Pw is the trivial partition
( If h > 0, Pw is the partition induced by x + sgn( [W sgn(WT (WTx). x:).
2. The probability } constructed by the procedure where we first sample h pH (h), then sample the entries of W E dx i..d according to Gaussian(O., 1).
3. For 8 E O, define (0) == π pH (-1) (?). where (2) = I1 (q 1).
Note that (-1)* = 1/ 11 (-q q ;) 0 when q < 0.
Theorem 5.2. Let ha (9, D0,R,,0 a) be as in Definition 5.1 Then
2))
(x, 2) # otherwise.
(T, +00
When g = -d, we have Khaa KM where the right hand side is the manifold-Ililber kernel.
Proof of Theorem 5.2 Before proceeding, we have the following useful lemma:
Lemma 5.3. Let rp (O, fo a) be a WRP. Let H be a random variable. Let 0 P. Suppose that for
all x, E M, the random variables axf)) and I(x E ) are conditionally independent given H.
Then we have KTP (xx 2) = Eн (aH)) [Ixx f E Po[x|) H] where (<h) = Egep (a(0) H h] for a realization h of H.
The lemma follows immediately from the Definition of independence assumption. Now, we proceed with the proof of Theorem 5.2
M (xr, 2) in Equation 3 and the conditional
Let Φ == =/, Let H ~ pı and 0 ~ P be the random variables in Definition 5.1 Note that
by construction, the following condition is satisfied: for all xr, M, the random varables a())
8

---

and 11 E Po[z]] are conditionally independent given H. In fact, a(0) = (h) --p=(tt)'(11)) is
constant given H- h. Hence, applying Lemma 5.3 we have
(z, 2) = E" (H) En Po[z)]
(-11)) 9 h Ea Polz]] = h] Σ π h=0
(-1)²
Pr( e Pole]] h}.
h)
h=
Next, we claim that Pr(z E Po
= (1- ")a When h = 0, I E Po is always true since
Pa {$*) is the trivial partition. In this case, we have Pr(æ E Po[= = h3 = 1 (1 o)
When h >> O, we recall an identity involving the cosine angle:
Lemma 5.4 (Charikar 19)). Ler v, 2 E E8 Let w E Rd++1 be random vector whose entries are sampled i.id according to Gaussian(O, 1). Then Pr(sgn(w' r) sgn(w' w 2)} = 1 (4(x, 2) m).
Let W [w,,..., wh. be as in Definition 5.1 where wy denotes the j-th column of W. Then by construction, wi is distributed identically as w in Lemma 5.4 Furthermore, wy and wy are independent for j.j' E [hi where jr. Thus, the claim follows from
Pr(z Polz]| h3 Pr(sgn (WT (T) sgn(W" (WT 2){ h)
h
(b) Pr (r(s u sgn uw 2)} (c)
II
(1 6) = -1-
j=1
where equality (a) follows from Definition 5.1 (b) from W (d+1)xx having i.d standard
Gaussian entries given H = h, and (c) from Lemma 5.4 Putting it all together, we have
(9) (1) - 6)t = "
ppart (x, 2) = Σ (-11)) h=0
(6 - 1)ah =(x
h=0
For the last step, we used the fact that for all g E R the binomial series (1 + t)a = En (2) converges absolutely for [t] < (when ø E (0, 1)) and diverges to +oo for t = - (when Φ = 0). L
Corollary 5.5. Let := -d and Kha be as in Theorem 5.2
The infinite-ensemble classifier sgn T7( ([o0| [[D , k(aaa) (see Equation for definition) has the interpolating-consistt property.
Proof. As observed in Devroye et [22 Section 7], for an arbitrary kernel K, the L conssissty of m Da K") for regression implies the consistency for classification of sgn (en(i [ D K)). Further- more, (m] | K)) is interpolating for regression implies that sgn(" D K)) is interpolating for classification. While the argument there presented in the Rd case, the argument holds in the more general manifold case mutatis mutandis.
Thus, by Theorem 3.2 have sgn( (ū( [D", KH)) )) is consistent for classification, i.e., Equation ① holds. It is also interpolating since m m [|D","" K) is interpolating. By Proposition [.22 we have K = KH Thus (g) Kga)) is an ensemble method having the interpolating property.
6 Discussion
We have shown that using the manifold-Hin Hilbert kernel in kernel smoothing regression, also known as Nadaraya- Watson regression, results in a consistent estimator that interpolates the training data Riemannian manifold M. We proposed weighted random partition kernels, a generalization of the unweighted analogous definition by Davies and Ghahramani (2I) which provided a framework for analyzing ensemble methods such as random forest via kernels. When M = Sd the sphere, we showed that the Hunifold-Hilber kernel is weighted random partition kernel, where the random partitions are induced by random hyperplane arrangements. This demonstrates an ensemble method that has the interpolating-consitt
property.
One limitation of this work is the lack of rate of convergence of the ensemble methods. The analogous Hadaraya-Watson Watson regression have been obtained by Belkin al. (8). However, it is not
result for the Nadaraya-

---

clear if the kernels used in 8 are weighted random partition kernels. Resolving this is an interesting future direction.
Similar to PERT 20 another limitation of this work is that the base classifiers the ensemble are data-independent. Such ensemble methods in these line of work (including ours) easier analyze than the data-dependemt ensemble methods used in practice. See Biau and Scornet [12) and [33 for in-depth discussion. We believe our work offers one theoretical basis towards understanding generalization in the interpolation regime of ensembles of histogram classifiers over data-dependent partitions, e-g., decision trees la CART
Acknowledgements
The authors were supported in part by the National Science Foundation under awards 1838 179 and 2008074. The authors would like to thank Vidya Muthukumar for helpful discussions, as well as an anonymous reviewer for bringing to our attention facts from geometric measure theory that provided context for the ad-hoc technical result Proposition
References
[1] Herbert Amann and Joachim Escher, Analysis III. Springer, 2009, pp. 389-455,
[2] Luigi Ambrosio and Paolo Tilli. Topics on analysis in metric spaces. Vol. 25. Oxford University Press Demand, 2004.
[3] Rushil Anirudh, Vinay Venkataraman, Karthikeyan Natesan Ramamurthy, and Pavan Turaga. "A Riemannian framework for statistical analysis of topological persistence diagrams". In: Proceedings of the IEEE conference on computer vision and pattern recognition workshops.
2016, pp. 68-76.
[4] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. "Benign overfitting in linear regression". In: Proceedings of the National Academy of Sciences 117.48 (2020), pp. 30063-30070.
[5] Peter L Bartleu and Mikhail Traskin. "AdaBoost is consistent". In: Journal of Machine Learning Research 8.0ct (2007), pp. 2347-2368.
[6] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. "Reconciling modern machine- learning practice and the classical bias-variance trade-off". In: Proceedings of the National Academy of Sciences 1 16.32 (2019), pp. 15849-15854,
[7] Mikhail Belkin, Daniel Hsu, and Partha Mitra. "Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate". In: Advances in Neural Information Processing Systems 31 (2018), pp. 2300-2311.
[8] Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. "Does data interpolation con- tradict statistical optimality?" ?" In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1611-1619.
[9] Thomas Bendokat, Ralf Zimmermann, and P-A Absil. "A Grassmann manifold handbook: Basic geometry and computational aspects". In: arXiv preprint Sxxi:2011.13660 (2020). [10] Alain Berlinet and Christine Thomas-Agnan Reproducing kernel Hilbert spaces probability and statistics. Springer Science Business Media, 2011.
[11] Gérard Biau, Luc Devroye, and Gäbor Lugosi. "Consistency of random forests and other averaging classifiers." In: Journal of Machine Learning Research 9.9 (2008).
[12] Gérard Biau and Erwan Scornet. " random forest guided tour". In: TEST 25.2 (2016), pp. 197-
227.
[13] Gérard Biau and Erwan Scornet. "Rejoinder on: random forest guided tour". In: Test 25.2 (2016), pp. 264-268,
[14] Vladimir Igorevich Bogachev and Maria Aparecida Soares Ruas. Measure theory. Vol. 1. Springer, 2007.
[15] Leo Breiman. "Consistency for a simple model of random forests". In: (2004).
[16] Leo Breiman. Some infinity theory for predictor ensembles. Technical Report. Department of Statisties, 2000.
10

---

[17] Leo Breiman, Jerome Friedman, Charles Stone, and Richard A Olshen. Classification and regression trees. CRC press, 1984.
[18] Joseph T Chang and David Pollard. "Conditioning as disintegration". In: Statistica Neerlandica
51.3 (1997), pp. 287-317.
[19] Moses S Charikar. "Similarity estimation techniques from rounding algorithms". In: Pro- ceedings of the thiry-fourth annual ACM symposium on Theory of computing. 2002, pp. 380-
388.
[20] Adele Cutler and Guohua Zhao. "PERT -perfect random tree ensembles". In: Computing Science and Statistics 33 (2001), pp. 490-497.
[21] Alex Davies and Zoubin Ghahramani. "The random forest kernel and other kernels for big data from random partitions". In: arXiv preprint WIXiv:1402.4299 (2014).
[22] Lue Devroye, László Györfi, and Adam Krzyžak. "The Hilbert kernel regression estimate"". In: Journal of Multivariate Analysis 65.2 (1998), pp. 209-227.
[23]
Manfredo Perdigao Do Carmo. Riemannian Geometry. Vol. 6. Springer, 1992.
[24]
Richard Dudley. Real Analysis and Probubility. CRC Press, 2018.
[25]
Aasa Feragen and Søren Hauberg. "Open Problem: Kernel methods on manifolds and met- ric spaces. What is the probability of positive definite geodesic exponential kemne??" In: Conference on Learning Theory. PMLR. 2016, pp. 1647-1650.
[26] Yoav Freund and Robert E Schapire. "Boosting: Foundations and Algorithms". In: MIT Press
1.6 (2012), p. 7.
[27] Ryuichi Fukuoka. "Mollifier smoothing of tensor fields on differentiable manifolds and appli- cations to Riemannian Geometry". In: arXiv preprinl math/0608230 (2006).
[28] Pierre Geurts, Damien Emsst, and Louis Wehenkel. "Extremely randomized trees". In: Machine learning 63.1 (2006), pp. 3-42.
[29] James Hebda. "Parallel translation of curvature along geodesics". In: Transactions of the American Mathematical Society 299.2 (1987), pp. 559-572.
[30] Sadeep Jayasumana, Richard Hartley, Mathieu Salzmann, Hongdong Li, and Mehrtash Harandi. "Kernel methods on Riemannian manifolds with Gaussian RBF kernels". In: IEEE transactions on pattern analysis and machine intelligence 37.12 (2015), pp. 2464-2477.
[31] Tam Le and Makoto Yamada. "Persistence Fisher kernel: A Riemannian manifold kernel for persistence diagrams". In: Advances in Neural Information Processing Systems 31 (2018).
[32] Jean-Michel Loubes and Bruno Pelletier. "A kernel-based classifier on a Riemannian manifold". In: Statistics & Decisions 26.1 (2008), pp. 35-51.
[33] Kanti V Mardia and Peter E Jupp. Directional statistics. Vol. 2. Wiley Online Library, 2000.
[34]
Kanti V Mardia, Henrik Wiechers, Benjamin Elizner, and Stephan F Huckemann. "Principal component analysis and clustering on manifolds". In: Journal of Multivariate Analysis 188 (2022), P. 104862.
[35] Xavier Pennec. "Intrinsic statistics on Riemannian manifolds: Basic tools for geometric measurements".. In: Journal of Mathematical Imaging and Vision 25.1 (2006), pp. 127-154. Takashi Sakai. Riemannian Geometry. Vol. 149. American Mathematical Society, 1996.
[36]
[37]
Erwan Scornet. "Random forests and kernel methods". In: IEEE Transactions Information Theory 62.3 (2016). pp. 1485-1500.
[38] Erwan Scornet, Gérard Biau, and -han-philippe Vert. "Consistency of random forests".. In: The Annals of Statistics 43.4 (2015), pp. 1716-1741.
[39] Donald Shepard. "A two-dimensional interpolation function for irregularly spaced data". In: Proceedings of the 1968 23rd ACM national conference. 1968, pp. 517-524.
[40] P Thomas Fletcher. "Geodesic regression and the theory of least squares on Riemannian manifolds". In: International journal of computer vision 105.2 (2013), pp. 171-185.
[41] Larry Wasserman. "Topological data analysis". In: Annual Review of Statistics and Its Applica- tion (2018), pp. 501-532.
[42] Abraham Wyner, Matthew Olson, Justin Bleich, and David Mease. "Explaining the success of AdaBoost and random forests as interpolating classifiers". In: The Journal of Machine Learning Research 18.1 (2017), pp. 1558 1590..
[43] Zhigang Yao and Zhenyue Zhang. "Principal boundary on Riemannian manifolds". In: Journal of the American Statistical Association 115.531 (2020), pp. 1435-1448.

---

[44] Zhenyue Zhang and Hongyuan Zha. "Principal manifolds and nonlinear dimensionality re- duction via tangent space alignment", In: SIAM journal on scientific computing 26.1 (2004). pp. 313-338.
[45] Ralf Zimmermann. "A matrix-algebrain algorithm for the Riemannian logarithm the Stiefel manifold under the canonical metric". In: SIAM Journal on Matrix Analysis and Applications 38.2 (2017), pp. 322-342.
Checklist
1. For all authors...
(a) the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of theoretical results? [Yes] This is the opening sentence of our first main technical section, Section
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you'ne using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "z5ypf0vM5Nn", "reviewer": "Reviewer_w6Vf", "summary": "In this paper, the authors first define the manifold-Hilbert kernel on a complete, connected, smooth Riemannian manifold of dimension d, as the d-th power reciprocal of the manifold distance between two points. The main result of the paper (Theorem 3.2) is that the Nadaraya-Watson estimator of the conditional mean of Y given X based on this manifold-Hilbert kernel, which by design interpolates the data, is consistent, both pointwise at almost every point and in terms of the L1 distance with respect to the density of X, assumed to exist. \n\nIn Section 5, the authors move onto a particular case of the manifold being the d-dimensional sphere, and it is shown in Theorem 5.2 that the random hyperplane arrangement partition, which corresponds to an ensemble method, actually coincides with the manifold-Hilbert kernel proposed in earlier parts of the paper, thereby showing that ensemble classifiers of this form are interpolating and consistent. ", "questions": "I am not familiar with ensemble methods, having never directly worked with them or used them. Is the form of ensemble used in this work, namely the one based on weighted random partition in (4), a general one in which many ensemble methods fall under? Or is this a particular form, which could limit the scope of your contribution? ", "limitations": "The contributions of this paper are theoretical in nature, thence I do not see any reason to discuss potential negative societal impact. \n\nMinor comments:\n\nline 77: \"When show that\" -> \"We show that\"\nline 135: $\\epsilon>0$ is a real positive number, not an open set, I presume?\n", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I do not actively work with differential/Riemannian geometry in my research, and beyond basic notions which I acquired a number of years ago, I am not familiar with the concepts used in this paper, and due to time constraints, I could not read up on all the background material required to go through every step of the proofs and certify their correctness.\n\nStrengths\n\nI believe the paper is tackling an important problem, although as someone who does not work directly in relevant areas, my judgment on the significance of the results is not well-grounded. \n\nThe paper is technical, but in spite of this, the clarity of the mathematical presentation makes it a pleasure to read. Despite my lack of required background to fully judge its merit, this helped me form a more positive picture of the work, and in parts where I did try to go through the mathematics, helped convince me of its soundness. \n\nWeaknesses\n\nThe main weakness that I can see is the lack of convergence rates. Only consistency is shown in the infinite-sample limit, but I think results would be much stronger if uniform rates were given over some class of distributions. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "wfNIAdS8WTt", "reviewer": "Reviewer_SNA2", "summary": "The authors derive an ensemble classification method for interpolating manifold-valued training data that they denote manifold-Hilbert kernel. The kernel is based on the Riemannian distances. The authors prove a consistency result with the kernel and derive a specific realization of the kernel on spheres.", "questions": "no questions", "limitations": "yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* the authors derive an ensemble method that has the consistent-interpolating property\n* the authors define the manifold-Hilbert kernel\n* the authors derive a specific realization of the kernels on spheres\n\nWeaknesses:\n* the paper is very technical and very hard to read. \n\nAs a non-specialist in this area, I was not able to confirm correctness of the presented results However, I have no reason to believe that the paper is not technically correct.\n\nI have a hard time evaluating the novelty. Proving consistency in this setting seems like a good result, but I don't know the literature well enough to judge how significant this is.\n\nThere is no experimental evaluation. Since the paper is purely theoretical, I believe this is OK.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "tx2cwJPCg4", "reviewer": "Reviewer_fiFy", "summary": "The paper proposes a theoretical analysis of a specific instance of interpolating ensemble methods for classification when the input data lie on a Riemannian manifold. The contributions are two-fold:\n\n- The authors introduce an extension of the Hilbert kernel, denoted the manifold-Hilbert kernel, and show that the classification rule produced by the sign of the Nadaraya-Watson estimator associated with this kernel is both interpolating and consistent.\n\n- They connect ensemble methods to this classification rule through the introduction of weighted random partition, and associated weighted random partition kernels. When a weighted random partition is found to give rise to the manifold-Hilbert kernel, then the corresponding ensemble method is both interpolating and consistent.\n\nThis phenomenon is detailed when the manifold is the $d$-dimensional sphere; in this case the proposed random hyperplane arrangement partition kernel corresponds to the manifold-Hilbert kernel associated to the arc-length metric.", "questions": "Remarks:\n- Links in the pdf are not working.\n- Typo line 77: \"when\" -> we ?\n- Figure 1's placement is suboptimal.\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The problem tackled is of interest to the learning community, with an important consistency result.\n- The paper is well written and accessible despite the underlying sophisticated mathematics, making it a high quality manuscript.\n- Related work in machine learning is well organized and allows to quickly understand the goal of the paper\n\nWeaknesses:\n\n- The heart of the contribution lies in the technical proofs provided by the authors, which I humbly admit to being unable to truly evaluate the novelty of. Essentially, the technical addition of the paper is to extend the results from [19] to the case of the input space being a manifold. While I do not doubt the integrity of the authors, it is hard for me to judge whether the various lemmas (4.1: Riemanniann logarithm, 4.2: change of variable) are groundbreaking in this regard. It would be interesting to have an expert in Riemannian geometry (which I am not) comment on this.\n\n- The theoretical nature of the paper, as well as its technical density may not be the best fit for the NeurIPS community - other learning theory venues such as COLT may be more suited for this.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "sC2AtTWBP0U", "reviewer": "Reviewer_Xx9M", "summary": "The paper \"Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel\" defines the manifold-Hilbert kernel and prove that kernel smoothing regression and classification using it are weakly consistent and hence establishes generalization guarantees in the interpolating regime. For the sphere it is shown that the kernel can be realized as weighted random partition kenrel arising as infinite ensemble of partition-based classifiers, which the authors claim to offer a theoretical basis towards understanding generalization of ensemble of histogram classifiers such as decision trees.", "questions": "The authors believe that their work offers a theoretical basis to understand genearlization of for example decision trees. Is there something more concrete than just a believe?", "limitations": "Limitations are clearly stated. It is a theoretical analysis under simplifying assumptions and the connection to popular ensemble methods used in practice is still unknown.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have to say that this is really for away from my expertise, so it was difficult to follow. \n- detailed theoretical analysis\n- well written, no obvious mistakes I can find\n- attempts to improve readability by explaining with words important theory\n- 1 result: manifold theory extension of Devroye, which showed that kernel regression with the Hilbert kernel is interpolating and weakly consistent for data with a density and bounded labels.\nweaknesses:\n- I found it hard to a bit hard to read, since there is a lot of jargon. That is surely my missing background in that area, but maybe that can be helped by putting the relevant background earlier. That helped a bit to understand the motivation of the manuscript\n- probably easier to have arabic panels in Fig. 1 and upper left corner instead of somewhere on the lower left.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept