Riemann-Lebesgue Forest for Regression
Authors: Tian Qin
Wei-Min Huang
Venue: Accepted by TMLR ()

Abstract: We propose a novel ensemble method called Riemann-Lebesgue Forest (RLF) for regression. The core idea in RLF is to mimic the way how a measurable function can be approximated by partitioning its range into a few intervals. With this idea in mind, we develop a new tree learner named Riemann-Lebesgue Tree (RLT) which has a chance to perform ``Lebesgue'' type cutting,i.e., splitting the node from response Y at certain non-terminal nodes. In other words, we introduce the ``splitting type randomness'' in training our ensemble method. Since the information of Y is unavailable in the prediction step, weak local models such as small random forests or decision trees are fit in non-terminal nodes with ``Lebesgue'' type cutting to determine which child node should we proceed to. We show that the optimal ``Lebesgue'' type cutting results in larger variance reduction in response Y  than ordinary CART cutting (an analogue of Riemann partition) in fitting a base tree. Such property is beneficial to the ensemble part of RLF, which is verified by extensive experiments.  We also establish the asymptotic normality of RLF under different parameter settings.  Two one-dimensional examples are provided to illustrate the flexibility of RLF. The competitive performance of RLF with small local random forests against original random forest (RF) and boosting methods such as XGboost is demonstrated by extensive experiments in simulation data and real-world datasets. Additional experiments further illustrate that RLF with local decision trees could achieve decent performance comparable to that of RF with less running time, especially in large datasets.

Published in Transactions on Machine Learning Research (06/2025)
Riemann-Lebesgue Forest for Regression
Tian Qin
tig218@lehigh.ede edu
Deportment of Mothematics
Lehigh University
Wei-Min Huang
wh02@lehigh..cm edu
Department of Mathematics Lehigh University
Reviewed on OpenReview: https: // openreview. net/ bet/foruee forum? id- JTnC9
Abstract
We propose novel ensemble method called Riemann-Lebesgue Forest (RLF) for regression. The core idea in RLF is mimic the way how a measurable function can be approximated by partitioning its range into few intervals. With this idea in mind, develop new tree learner named Rieeann-Leebsguee Tree (RIT) which has chance to perform "Lebesgue" type cutting,...., splitting the node from response Y at certain non-terminal nodes. In other words, we introduce the "splitting lype randomness" in training our ensemble method. Since the information of Y is unavailable the prediction step, weak local models such as small random forests or decision trees are non-terminal nodes with "Lebesgue" type cutting to determine which child node should proceed to. We show that the optimal "Lebesgue" type cutting results in larger variance reduction in response Y than ordinary CART (Breiman et al. 1984) cutting (an analogue of Riemann partition) in fitting base tree. Such property is beneficial to the ensemble part of RLF, which is verified by extensive experiments. We also establish the asymptolic normality of RLF under different, parameter settings. Two one-dimensional examples are provided to illustrate the flexibility of RLF. The competitive performance of RLF with small local random forests against original random forest (RF) (Breiman 22011) and boosting methods such XGboost (Chen & Guestrin 2016 is demonstrated by extensive experiments in simulation data and real-world datasets. Additional experiments further illustrate that RLF with local decision trees could achieve decent performance comparable to that of RF with less running time, especially in large datasets.
1 Introduction
Random Forest (Breiman 2001 has been successful ensemble method in regression and classification tasks for decades. Combination of weak decision tree learners reduces the variance of a random forest (RF) and results a robust improvement in performance. "Feature bagging" further prevents RF from being biased toward strong leatures which might cause fitted subtrees are correlated. However, the benefit of "feature bagging" may be limited when only small proportion of features are informative. In that case, RF likely to learn noisy relationship between predictors and response which in the end makes RF underfit the true functional relationship hidden in the data.
Many methods have been proposed to tackle this issue. Heaton 2016 proposed to rule out irrelevant features or perform feature engineering at the beginning of fitting RF Another type of ideas is to adjust the way RF selecting informative features. Amaratuugg et al. (2008): Ghosh & Cabrera (2021) employed weighted random sampling choosing the cligible features at cach node. Besides the feature weighting method, Xu et al. (2012) used different types of trees such as C4.5, CART, and CHAID build a hybrid forest. The resulted forest performs well in many high-dimension datasets. Zhou & Feng 2017 employed sequential multi-grained

---

Published in Transactions on Machine Learning Research (06/2025)
y.
(b)
Figure 1: Two types of function (aa type approximation. (b): "Lebosgue" type
approximation
scanning to discover the feature relationships. Most of those methods only deal with classification tasks. In this paper, we fill the gap by proposing a novel forest for regression tasks named Lebesgue Forest (RLF) whose main idea is to exploit the information hidden in the response Y rather than the predictors alone. In most types of tree algorithm, people approximate the regression function in the "Riemann" sense. That means the fitted function f(x) can be written as follows:
P Σ Jn, (xER.)
f(x)
where each R₂ is hypercube in feature space, UR. represents the mean value of responses lying in the region R2 and P is the total number of hypercubes partitioned. Fig I(a) gives example of smooth function fitted by step functions in one dimension.
As we can see, partitioning x-axis may underfit the true function unless we keep partitioning, which means we take the limit of step functions. Many decision tree algorithms follow this idea by choosing optimal splitting value of optimal feature at each non-terminal node. On the other hand, we know that any measurcable function R2 R can be approximated by sequence of simple functions (x(x), 1,2, Equation gives example of simple functions:
n2"
6 (x)
Σ
j j-1
2n XASM + nXB.
(2)
j=1
where Ajn = f- ( for 1,, and B, - ([n
It is now standard analysis exercise to show that on converges to f. Note that if f is finite (which is typically case in practice), XB., will vanish for large In other words, we can actually obtain the partitioned feature space indirectly by partitioning the response space (real line) in regression tasks. For comparison, we borrow the term analysis and name this kind of partition procedure as "Lebesgue" type. Fig. [(b) gives an example of approximating function in "Lebesgue" sense. One characteristic for partitioning feature space from response is, the shape of resulted region is not limited to hypercube, which actually enriches the structure of trees in forest. To overcome the limited structures learned by ordinary RF in sparse models, we incorporate the idea of "Lebesgue" partition in constructing each decision tree. To implement the "Lebesgue" type splitting rule shown in 1(b) we can apply the CART-split criterion on response Y which is simple but efficient. However, the information of Y is unavailable in the prediction step, weak local models should be employed for nodes with "Lebesgue" type cutting to determine which child node should we proceed to. See detailed discussion in section 2.2 and 2.3
The remaining sections of this paper are organized as following schema. In section we introduce some preliminaries and illustrate the idea of Riemann-Tebessue Forest (RLF) in detail. Tn section we present. the
2

---

Published in Transactions on Machine Learning Research (06/2025)
potential of Lebesgue cutting in reducing the variance of response Y. Theoretical results such asymptotic normality of RLF and time complexity analysis are discussed as well. Extensive experiments are conducted in section f to illustrate the competitive performance of RLF under small local random forests against other ensemble methods. The simulation results of tuned RLF in models with a small signal-to-noise ratio and mixture distribution are also provided. Section discusses some characteristios and limitations of RLF and proposes future directions. The codes for the implementation of RLF, selected real datasets and the simulation results are available in supplementary materials. All simulations and experiments are performed a laptop with 12th Gen Intel(R) Core(TM) 17-12700H (2.30 GHz) ,16.0 GB RAM and NVIDIA 4070 GPU.
2
Methodology
In section
2.1 we first introduce essent ial preliminary used in the rest of the paper. We will illustrate how to incorporate "Lebesgue" partition and local models in constructing a CART type tree in section 2.2 Then we apply this new type of tree to the algorithm of Riemann-Lebesgue Forest in section 2.3
2.1 Preliminary
In this paper, we only consider the regression framework where the data consist of n i.i.d pairs of random variables Z; = (X,, Yi) E X' x IR,i = 2, n. Let Fz be the common distribution of Z4. WT.OG, we can assume the feature space X' = [0, 1]4, where d is the dimension of feature space.
The procedure of generating a Random Forest regression function from Breiman's original algorithm can be summarized as follows:
1. Bootstrapping N times from original dataset.
2. For each bootstrapped dataset, build CART decision tree based on those subsamples.
3. Take the average of N built trees as the ensemble regressor.
At bootstrapping time i, denote (Xi, Yi.), (Xixs Yi,) ) be a corresponding subsample of the training set, where & is the subsampling size. If we write the corresponding grown CART tree as T(w)) T():((,,, Yi.)..., (Xix+ Y),),, then the final random forest estimator Rn evaluated at point x" can be written as:
N
1 N
Rx(x')
Y, (Xi,s Y(,)
(3)
where random variables wi represents the randomness from the construction of i-th CART tree. For growing a CART tree, at each node of tree, the CART-split criterion is applied. mery features will be randomly picked as potential splitting directions. Typically mary = [d/3]. On the other hand, the structure of a single
CART tree in original forests relies on both predictors and responses in the corresponding subsample, i.e the randomness also comes from resampling (bootstrapping procedure). By assumption in Breiman (2001). (w)) are i.id and independent of each bootstrapped dataset.
A detailed description of the CART-split criterion is as follows. In CART, node represents point in the decision making process of CART tree. For each CART tree, we have non-terminal node where a split point occurs and a decision is made. Terminal nodes are the nodes only having predicted values and don't have child nodes. Let A be a generic non-terminal node in a decision tree and N(A) be the number of observations lying in node A. A candidate cut is a pair s),8) where j represents a dimension in {1,..., d} and s is the splitting point along the j-th coordinate of feature space. Since CART-split criterion in RF focuses on splitting predictors, we can view such cutting method as the "Riemann" type splitting rule. Let (pi,...,PParr 8() x(i) consist of all possible cuts in node A and denote X; = (x(1) ..... x(d)), where the set {pI,.... Prncay } represents randomly picked feature index in CART, then for any (),8) E CR. the CART-split criterion (Breiman el. al. 1984h chooses the optimal (j*, 8*,8*) such that
the set CR = {(j s(i))
s",,") E arg max L(j,s) (.a)ECR
where
3

---

Published in Transactions on Machine Learning Research (06/2025)
1 n [Y: 1x)= L(1,8) ((A)
1 N(A) E YA, x(10ss YAn X 1x,ed
(4)
Ag Ex A (3)) < s 1,2, n), AR (x E A x(1) 2 s, 1.2,
n). x represents the j-th
dimension of i-th observation in the given node with size and YA, , the averages of responses Y with the corresponding features are in sets AL and AR, respectively.
2.2 Riemann-Lebesgue Tree
To implement the "Lebesgue" type splitting rule as shown in l(b) we can apply the CART criterion on response Y. Note that we only need to choose the optimal splitting point for Y in this case. Denote C, ((,s) :j (0), E Y be the set consist of all possible splitting points for response, then choose the optimal splitting point 87, al node A such that
15 arg max ((s) sEC,
where
" (Y, 21) N(A) Σ(r
1 n (Y, YA 1r:c 1y.20) 2
[(s) ((A) Σ(y
(5)
n). Ao (x, E A 2 1.2....,) and YA, YAD VAu are the averages of responses Y; with the corresponding features are in sets A, AD and Au, respectively. As we can see from equation (4) and equation (5) the "Lebesgue" type splitting rule will go through all potential cutting points for while the "Riemann" type splitting can only check part of them. We can conclude that [(j",s") < (s$)).
ÅD = (x, E A: Y, <
One issue for the "Lebesgue" type splitting rule is overfitting. Suppose the response Y at A' only takes two distinet values, say Y 0 Y = 1, node A' The CART-split criterion for Y give perfect split s2 0.5 under some appropriate sets of Cr. In other words, we will have L(s") = प (Y; 1yyed' This phenomenon restricts the potential application of "Lebesgue" partitioning in classification task.
To overcome the potential overfitting from the "Lebesgue" type splitting, we apply "Riemann" and "Lebesgue" splitting in hybrid way. Since we will eventually construct an ensemble learner from Lebesgue trees, it's acceptable to introduce a Bernoulli random variable B to determining splitting types at each non-terminal node A. More specifically,
i(st) B ~ Bernoulli()), P = L(i i(s))
If B = 1, the "Riemann" type splitting will be employed, and vice versa. The reason why we define above is to control the number of nodes taking "Lebesgue" type splitting. We already seen that T(J",, < T(x so it's expected that there won't be too many "Lebesgue" type nodes and ğ will play a role of regularization.
Another issue for the Riemann-Lebesgue Tree(RLT) is the prediction. When a testing point (x, y) falls into a non-terminal node with "Lebesgue" type splitting trained RI.T, we are not allowed to use the information of its response y. That enforces us to estimate the value of response locally so that we can compare the locally estimated response with St and determine which child node should that testing point proceed to. Linear regression is one of the candidates for the local model. However, it is unstable when the sample size is relatively small. Another choice is the K-Nearest Neighborhood algorithm (KNN). However, the performance of KNN relies on the distance function we used which can be unstable in high-dimensional cases.
this paper, we choose small random forest (with few subtrees) as the local model to obtain an estimate of the response value of a new incoming point since the random forest parameter-free and robust for small sample size. When we set the number of subtree be 1, the local random forest reduces to the local decision tree. Experiments in Table S5 implies that local decision tree is good enough in practice. However,
4

---

Published in Transactions on Machine Learning Research (06/2025)
introducing local models complicate the interpretation, implementation and analysis of RLF, which be a potential limitation and will be discussed in detail in section 5 We believe that there exist more efficient. local models, which is our future work. Algorithm summarizees the procedure of fitting a Riemann-Lebesge Tree where local random forests are employed in non-terminal nodes with "Lebesgue" type cutting. To our best knowledge, this the first type of base learner exploring information directly from response.
Algorithm Eieemann-ebesguee Tree (Fitting)
Require:
Training data P, {X,, Y I,,.,,,, n). Minimum node size Madde Mary {1, 2, .... d]. Let (A) denote the number of sample points at node A and A is the root of the tree at the beginning. Miccat is the number of trees used in local random forests.
1: ((A) > Mnode then
2: Select Mery C {1, ..., df of cardinality mary without replacement uniformly.
Perform CpRT-split criterion among the selected features, and obtain j". L(j", L()",s")
Perform -plit criterion with respect Y E A, and obtain si, L(st). (677) Calculate p L((7))))+(()))
and sample B Bernoulliū)).
6:
if = then
7:
Cut the node A according to j" Denote AL and Ar as the two resulting nodes. Repeat steps 14 for nodes A, and AR-
8:
9:
else
10:
Cut the node A according to s. Denote Ap and Ay as the two resulting nodes. Fit a local random forest with Mioeal trees w.r.t points in current node A. Call it RFFical.
11:
12:
Repeat steps 1 14 for nodes AD and Au.
13:
else
14: Set the current node as a terminal node.
15:
Return: collection nodes and fitted CART-splitting rules
Algorithm Riemann-Lebesgue Forest prediction at x
Require: Original Training data D, {X,, Yi), i.....n) n with X, E [0, 1]6. Minimum node size Mnodes Mary E (1,2,..,dd, d]. Number of trees M >> O, Number of trees used in local random forests Moxea 0 k E (1.2,..., and x.
1: for i i= to M do
2: Select points (X,,, Y.).... (Xi,, Y..) without replacement from D,, Use selected points to fit Riemann- Leomann-Lebesgue Tree described in Algorithm| 1 Hyperparameters
such as Mnode, Mary of RLF are shared with each Riemann-Lebesgue Tree. if node A is terminlli node with Riemann type cutting then Suppose the optimal splitting direction is j" and optimal splitting value at j" direction is 8".
5:
6:
if x(() < s* then
7:
We send x to A,, and repeat steps 4-15 until x arrives al a terminal node
8:
else
We send x to An and repeat steps 4-15 until x arrives at terminal node
10:
if node A is a non-terminal node with Lebesgue type cutting then Suppose optimal splitting value of response is s7 and the fitted local random forest with Moccat subtrecs is R.iocalt
11:
12:
if R.Focca (x) < s then
13:
We send x to Ap and repeat steps 4-15 until x arrives at terminal node else
14:
15:
We send to As and repeat steps 4-15 until x arrives at terminal node Denote the averaged values of Y falling in the terminal node x as H(#)) ((X,, Yr, (...)..,,,,,, (Y..))))
16:
Return: RLFM(() + -M (wx) ((Xi, Y:.),.., (Xig, Y2)),, which the final predicted value of from Riemann-Leber Lebessue Forest.
17:
5

---

Published in Transactions on Machine Learning Research (06/2025)
2.3 Riemann-Lebesgue Forest
Once we establish the way to build Riemann-Lebesge Tree, the ensemble version follows immediately. Following the spirit in Breiman (2001). we build M trees from different subsamples. Each tree is grown illustrated in Algorithm We employ sampling without replacement (subagging) in ensembling part. The cor- responding procedure of predicting x value from a Riemann-Lebesgue Forest (RLF) is described Algorithm the fitting of local models only relies on subsamples (Xa, Y,,)........ (Xig Yy).. Thus
Note that in Algorithm 2 can denote the prediction from i-th RLT function ( ((X,, Yu),,.., (Xix Y,,)) where randomness wi comes from feature bagging and the random choice of "Riemann" type cutting and "Lebesgue" type cutting.
3 Theoretical analysis of RLF
For the sake of theoretical analysis, we give theoretical version of Riemann-LLebesuue Forest. Suppose (Zi,... Zn) are ii.d from common underlying distribution Fz, where Z, (X,, Yt). Let h(w) be the random kernel corresponding to the randomness wN induced by i-th subsample ] where (w+)²= are i.id with Fw and independent of each subsample. Denote N subagging times and k as subagging size. Since uniformly samples & distinct data points with replacement, the incomplete U-statistic with random kernel (See detailed explanations in Appendix C at the query point x is
Un
1 N
h (w(l)) (x; Zzz: ... Zin)
(6)
We (((((()) (x; Zie Zine
p
where p N/(2) and vector
W (W1,... W W(2)) ~ Mullinomial(N, N,
Note that in asymptotic theory, both N and &o can rely on sample size We first show Lebesgue cuttings induce smaller L2 training error than Riemann cutting in section In section 3.2 we further give the convergence rate of the asymptotic normality of RLF. To see the time efficiency of RLF in different sizes of data, a complexity analysis is given in section 3.3 Since the Lebesgue part cach Riemann- Riemann-Lebesgue Tree is essentially splitting the response Y with CART-criterion, many consistency results for traditional RF can be applied to RLF directly. We provide version of consistency adapted to RLF according the results of Scornet et al. (2014) in Appendix D
3.1 Variance reduction of response Y by Lebesgue cuttings
In section 2.2 we conclude that s(j",s") < L(st) for each partition in constructing a Riemann-Lbbeguue formalizes the above conclusion.
Tree. Theorem 3.1
Theorem 3.1. Let the regression function be = f(X++ whhre X E Rd, Y E R. and f is bound measurable
function and = is an independent noise term. Under the procedure defined in equation 4 and equation 5 let
A = (Y a²), AG = (Y < a"} be the optimal Lebesgue culting and B = (x()) > b B3 = (X0") bA} be the optimal SieeaannCARRT cutting ,then we have:
Var(Y) Var(Y1A;) Var(Y1;;) Var(Y) Var(Y 1n;) Var(Y
where 14;, 1Ag. 1B; 1B; are indicator functions for event Ai, Bi, Bi, respectively.
I More specifically, the randomness Riemann- Lebessgee given fixed subsampling comes from feature bagging and random choice Riemann type cutting and Lebesgue type cutting.

---

Published in Transactions on Machine Learning Research (06/2025)
In other words, the variance reduction of response Y induced by the optimal "Lebesgue" type cutting will be greater or equal to that of optimal "Riemann" type cutting. It follows immediately that for given training set, a RLT will have smaller L2 training eтror than a ordinary CART tree given other tree parameters are the same. According to the bias-variance decomposition, RLF is expected to have smaller mean squared error than RF after the ensembling step. Real-world data experiments in section verify this conjecture. The proof of Theorem 3.1 is based on a variance decomposition formula.
3.2
Convergence rate of the asymptotic normality
Peng et (2019) provided sharp Berry-Essee Esseen bounds for of RF under the Bernoulli sampling (Chen & Kato 2019 The main idea follows from the Stein's method (Chen et al. (2100) and Hoeffding decomposition
Vaart 2000). Getting inspired by the results in Peng et al. (2019) and Mentch & Hooker (2016), derive
improved Berry-Faseen bounds of RLF for small-N settings (i.e, relatively small number of trees in RIF)
where lim N = and a > 0 or Oc in Theorem 3.2
Theorem 3.2. Suppose Z1. Zn iidd
~ Pz and Un is defined as in equation 6 with random kernel
(w) [Z1 ..., Zz). Denote 0 = E[h(Z, 11, Zx:w)] Let Sk = var (arh((2 Z1, w); me = (Z)) where
g(z) = Elh(z, Z2, ..., Zziw) w]] - And p = N/(2). Denole Un = b. If ÇR < 00, C1, > 0,0 < vo < 1/2 and Elih- mm2m] | | is uniformly bounded for m 2,3, we have the following Berry Esseen bound for
N
supzER P
F /K/// + +G
VN -0) Sz) - (())
S Ō
El
+
k
SK
-1)
-
-1]]
1)
1/2
11 1/2 3/2
n
+ N + +
hi
1/3
El 0
(7)
N1/2 0/2)3/2
12
(1- P)
N2
1
where Ō a positive constant and (z) represents the curnulative distribution function (CDF) for a standard
normal distribulion.
The proof follows the idea in (Pnng et al. 2019 which decomposes the generalized incomplete U-statistic sum of complete U-statistic and remainder. See Appendix G for details. Two asymptotic results can be induced from inequality 7
1. 1f0 < lim an < and G + O, then (VUnNNNW 4 N(O,1). Vkeciwatts
2. If lim an and G. then VN(Un. 4 1(.
VSa
where we implicitly assume that Tim SE * 00. More generally, if k/n -> 0.12/n n - 0o and N - oc, the asymptotic normality still holds under some conditions on moments of h. In summary, Theorem 3.2 generalizes the results in Mentch & Hooker (2016); Peng al.
(219); Ghosal & Hooker 20221 by directly
assuming the resampling scheme is sampling without replacement and providing sharp Berry-Esseen bounds
for asymptotic normality of RLF. Unlike the bounds in Peng et al. (2019), incquality 7 provides one
extra term which comes from the difference between uniformly sampling without replacement and Bernoulli sampling (See Appendix G). It is worth mentioning that the asymptotic results in small-N setting provide a theoretical support for people employing less number of base learners as long as the subsample size k is appropriately designed.
3.3 Complexity analysis
The essential difference between RLF and RF is, a local RF is randomly determined to be fitted at certain nodes of each CART tree. Whether local RF is fitted relies on Bernoulli random variable. To analyze the
7

---

Published in Transactions on Machine Learning Research (06/2025)
computation time for fitting a RLF, assume that local RF will be fit at each non-terminal node of RI...
We borrow the notations used in Algorithm | and Algorithm 2 In the best case of balanced tree, the time flexibility of building a CART tree is O n loggn) (Trevor Hastie & Friedman 2009). the optimal splitting leads to the extreme imbalanced cutting, the worst. time flexibility would be O(mrry : n²²) where the tree depth n.
In the best case of building Riemann-Lebesgue Tree, have the following recursion relation
T(n) = ( + O merr n loggn)
where T(-) is measurement of the runtime of Riemann-Lebesgue Tree. By the limited fourth case in Master theorem (Cormen et al., 2009), T(n) (MMical Mery logīn). Then the best time complexity of RLF is O(M Miocal Myrr m) which has polylogarithmic runtime. With similar argument, we can see the worst time complexity of RLF is O(M Miccl -Mtry" n² log2n).
In summary, we observe that the exact difference in complexity in best and worst comes from the factor Miocal logyn. This implies that the difference of complexity between classical RF and RLF increases when the size of dataset n or the number of local trees Miscal increases. Table [55 in Appendix E compares the time efficiency and prediction performance of RLF with Moccal and traditional RF in many datasets. The empirical results show that RLF performs better than RF in general and requires less running time, especially in large datasets. And Table S6 compares the training time of RLF and RF a simulated dataset with increasing sample size. The results show that the RLF with local decision trees is indeed much more efficient than the RF in large sample size. The possible reason is the efficiency of Lebesgue splitting, which only scans the response instead of screeming randomly selected features. In this sense, the scalability of RLF with efficient local models is acceptable than RF. Those obscrvations promote the potential of RLF. How to implement RLF in parallelization speed up training and prediction is one of our future directions.
4 Experiments
4.1
Sparse model
To explore the performance of RLF in sparse model, we consider the following regression model in Trevor Hastie
& Friedman
2009):
35
Y = 10 II 2x + >XE X e~ N(0,0)
j=6
where Xj is the j-th dimension of an observation X. The response Y E R and random sample X will be i.i.d and uniformly distributed on the 100-dimension unit cube [0, 10 In this case, the effective dimension is 35. And o is set to be 1.3 so that the signal-to-noise ratio is approximately 2. Fig. summarizes the testing MSEs for RLF and RF as functions of different hyperparameters. As we can see, given data-driven p, RLF outperforms RF in almost all settings. See detailed experiment set and analysis in Appendix B
4.2 Real Data Performance
We used 10-folds stratified cross-validation to compare the performance of RLF and RF on 30 benchmark real datasets from Fischer et al. (2023). The size of datasets ranges from five hundred to nearly fifty thousand observations. For time efficiency and consistency, we set the number of trees RLF and RF to be 100 and subtrees in local RF in Lebesgue part of RLF to be 10, i. Mocc//=0.. See Appendix A for the detail of datasets and statistical significance tests employed. We observe that RLF reaches roughly the same mean-squantt suu-sud--uurrrrrrrrrere as RF for most datasets and outperforms RF in 20 datasets where eight of them are icalll significant. The binomial test for win/loss ratio of RLF also shows that RLF does better job than RF statistically.
Thhat means stratified sampling method was employed to ensure the distribution of response is the same across the training and testing sets
8

---

Published in Transactions on Machine Learning Research (06/2025)
Mcan squared error
10-
5.0
Mean squares errrr
5.0
Moen squereed CTTOR
5.0
RF RLF
RF RLF
RF
RF
8-
4.5
4.5-
RLF
4.5
RLF
4.0
4.0
4.0
6-
Mcan
3.5
3.5
3.5
3.0
3.0
23.0
0 100 200 300 400 500 Number of trees
0
10
20
30
40
50
20
40
60
0.4
0.6
0.8
1.0
Number of local trees
Number of noisy variables
Subagging ratio (RLF)
(a)
(b)
(c)
(d)
Figure 2: Test MSEs for RLF and RF. (a) Test MSE as function of Number of trees, (b) Test MSE rate function
of Number of local trees, (c) Test MSE as a function of Number noisy variables, (d) Test MSE as a function of Subagging ralio.
Table Mean squared error corresponding 95% margin error (based on 10-folds cross-validation) for Riemann Riemann-Lebesgue Forest(100,10) vs. Ra.nam Forest(100)
Dataset
RLF((10,10)
RF(100)
Dataset
RLF(100,10)
RF(100)
PF
4205.21
15612.77
4303.31 1403.31154332.1
CPU
5.7210.66
5.9210..5
SP
1.90
1.88:1.82
KRA
0.0188 10.00062*
0.0214 10.00059
EE
1.258=0.32
1.262=0.35
PUMA
4.97e-4 11.38e-5*
5.14e-4+1.67e-
CAR
5374313
1787019.9
5390741 1840508.3
GS
1.2e-4 #4.06e-6**
1.5e-4444.7ee-6
QSAR
0.7568100. 1..14
0.7594110.13
BH
0.01 10.01
0.01110.012
CCS
28.34.14.87
28.19 14.09
NPP
5.97e-7 5.97e-716. 16.4ee--
6.5e-719.
SOC
587.87 203.5533
565.08 +204.29
MH
0.02+0.00093
0.022 #0.0011
GOM
240.67=38.74
247.61=39.16
FIFA
0.5775=0.026
0.5796+00024
SF
0.66+t..21
0.67 #0.2
KC
0.041=00.0013
0.037-0.0013
ASN
11.87 11.28
13.02=1.300
SUC
83.16:12.26
82.38.1..27
WINER
0.3319+40.034
0.3299 +0.035
CH
0.056=0.0026
0.009=0.0026
AUV
8073182-1513348
93650244$33367..
HI
217.64444.91
112.12+4.422
SG
0.01367++.0005
0.0136440.0046
CPS
0.2766=0.0077
0.2772=00.066
ABA
4.63 +0.54
0.56
PP
11.94110.16
12.0910.113
WINEW
0.3670110.021
0.3612:0.022
SA
6.13=00116
6.26
*The better performing values highlighted bold and significant results marked with 1**
4.3
Tuning of Splitting control probability p
Instead of using data-driven p, we can set the control probability P as tunable parameter when constructing RLT. That is to say, we set ý be fixed value for all nodes in RLT. For instance, under the same sparse model defined in section 4.1 Fig ((a) indicates that the sparse model favors more "Lebesgue cuttings This is consistent with the intuition that noisy variables weaken the effectiveness of "Riemann" cutting. In this section, we provide two one-dimensional examples to illustrate the flexibility of RLF with tuned p. One is designed to have small signal-to-noise ratio. The other is a mixture model with prior probability where we anticipate that RLF will perform better because of nature the Lebesgue type cutting. Test MSEs of RLF as functions of p Fig [S4(a) and (S4(b) exhibit the potential benefit of tuning control probability p. See details of tuning procedure in Appendix
SSince R.F doesn't have parameter f so the Test MSE curve of RF
function w.r.t 0

---

Published in Transactions on Machine Learning Research (06/2025)
Mean squared eroo
5.0
4.5
RF RLF
2
20
10
4.0
0
0
3.5
-2
-10
3.0
4
0.25
0.50
0.75
1.00
0.00
0.25 0.50 0.75 1.00
-2
0
2
Control probability p
x
(a) Sparse model
(b) Example 1
(c) Example 2
Figure 3: (a) Testing MSFs for RLF and RF as functions of control probability p. Orange points in (b) and (c)
represent test samples generated by two models. Blue solid lines the underlying functions; Green lines are the predicted curves for optimal RLFs while the red lines are the predicted curve of optimal RF in two examples.
Example 1: Small signal-to to-noise ratio
Figure 3(b) demonstrates the predicted regression curves from tuned RLF and tuned RF one-dimensional case. Our synthetic model is based on the sine function used in Cai et al. 2023
Y = sin(1XX +
where X Uniff0, 1] and 1. Predicted curves Fig show that tuned RLF is robust relative high level of noise and it is capable to identify the pattern in response while traditional RF too conservative in this case. Table S7 in Appendix H lists validation MSE of top 10 models with tuning parameters for RF and RLF, Based on the top 10 models, MSE under best RF is 1.283 while the testing MSE of best RLF is 1.018 (See Table S8 in Appendix H Another interesting phenomenon is when the noise level is high, RLF prefers using more Riemann type cuttings to achieve better performance as top 5 tuned RLFs in Table 58 have relatively large value p.
see RLF generally outperforms RF in this case. Indeed, the testing
Example 2: Mixture model with prior probability
In second example, we consider a mixture model as follows:
Y 5X if C =1
(8)
10+5x+e if C
where X,ε Lidd N(0,1) 1) and the random variable C is uniformly distributed on {1,2}. To generate observation of response, we first randomly pick value of state variable C from {1,2} and generate Y according to the model defined in equation (8). In this way, Y will follow a mixture Gaussian distribution. Figure 3(c) illustrates that RLF is capable of capturing the complicated distribution of response with the help of Lebesgue cuttings, while traditional RF fails detecting the complex pattern in response.
Similarly, Table 59 n Appendix H lists validation MSEs of top 10 models with tuning parameters and the lesting error of best RLF (29.87) is smaller than that of best RF (35.17) showing that RLF also beats RP in this case. It is worth mentioning that Table S9 gives us clue that when response Y has mixture distribution, RLF favors more Lebesgue cuttings since top 5 tuned RLF models tend to employ relatively small value of p.
4.4 Extra experiments of RLF with tuned p
We perform extra experiments on 26 datasets listed in Table 1 to show the strength of RLF after parameter tuning. Four large datasets are excluded due to the time efficiency of parameter tuning. Table [ shows that tuned RLF still outperforms tuned RF in many real-world datascts and wins more often than in original experiments. More specifically, tuned RLF wins in 23 datasets among which 12 of them are statistically significant. See Appendix for detailed settings for tuning process.
10

---

Published in Transactions on Machine Learning Research (06/2025)
Tahle 2: Averaged MSFs and 95% marginal errors for Best RLF and Best RF
Datasel:
Best. R.F.
Best
Dataset
Best RLF
Best R.
FF
4221.49 19191.91
4376.29-8922.
ABA
4.66::0.39
4.63==0.38
SP
1.78 +0.78
0.98
WINEW
0.398=0.0255
0.403=0.0024
EE
0.54 +0.29*
1.50=t.335
CPU
5.67=0.58*
6.15=00443
CAR
5194266 11287865
5622327
KRA
0.01910.0000
0.024110.0013
QSAR
0.79 10.10
0,80=1,133
PUMA
0.00048
0.00053:11 82cc00
CCS
27.11 =3.52*
37 27::03
GS
0.00011=7.96e-00
0.00016::807c-066
SOC
105.63-336..21
621.75=5528.35
0.0061=:00032
0.0069=0.0000
GOM
255.49 15.660
263. 64.10
NPP
7.79c-07
1.08-00611..5ee
SP
0.67
0.62 0.62.10.21
MH
0.02110.00117
0.023
ASN
1.67
14.1412 00
PIFA
0.578:10.011
0,58111.0010
WINER
0.347=0.002
0.349-t0.026
SUC
89.67:11..00
91 10.36
AUV
4192163: 1236743*
1878887=11702611
CH
0.056:0.018
0.062+000019
SG
0.0137
0.0143:10.0041
CPS
0.27910.0061
0.27
The better performing values are highlighted in bold and significant results are marked with
4.5
Comparison with Boosting methods
To see the potential of RLF among various tree- based models, we conducted experiments comparing the testing (1E(ooss cross-validaiton) of RLF,, Gradient GBB (Trevor Hastie & Friedman 2009) and XGboost Chen & Guestrin 2016). The number of base tress in GB and XGboost are 1000 and the subagging ratio is 0.8. Other parameters are set by default. The number of RLTs 100 in RLF and Mtocal
for local RFss in RLF. The control probability ý = 0.8. Table shows that RLF is comparable to XGboost in general and RLF outperforms EradientBoostinng in most cases. The competitive performance of RLF in large datasets further illustrates the potential of RLF.
Table 3: Testing MSEs and 95% marginal error for RLF, GB and XGboost
Dataset
#Observations
#Features
RI.
GB(1000,0.8)
(1000.)()000.0.8)
FF
517
11
4293 1557755
4694.76 1894.78.11 5363.52
4624.42.15518.72
SP
649
31
1.7610.79
2.13.10.99
2.27-10.90
EE
768
0.74110227 18
1.09:10,22
0,09:10.03
CAR
804
4916065-1766988.4
418148911
5802233-08859337
QSAR
908
0.75:10.13
0.85
0.97:10.17
CCS
1030
23.73114.28
28.87
20.05.18.49
SOC
1056
422. 02.9441164.77
160.711135.08
325.541167.66
GOM
1059
117
240. 13-
266.72+337.29
269.68-24.99
SF
1066
0. 11
0.61+0.19
0.
ASN
1503
0.95 12
20.94412.25
1.58:10.39
WINER
1599
0.32-10.13
0.411L0.033
0.38:10.04
AUV
2043
43245424711281.7
27726-183+ 1730233
(65060.7733876.38
SG
3107
0.013+00005
0.016+00000
0.012+0.003
ABA
4177
4.6=0.58
4.79:+0.43
5.76++0.65
WINEW
4898
0.36-10.02
0.50-10.03
0.440.02
CPU
8192
5.45-0.449
6.25-10.47
6.00-11145
KRA
8192
2017=0.000S
0.04=000000
0.016+0.0007
PUMA
8192
33
0.00047
0.001 12.10 .008
0.00056.10.0007
CS
10000
13
0.0001113.81c-6
0.0003 19.69c-6
8.97e-5 12.22e-6
BH
10692
0.01-10.01 10
0.014:10.000 008
0.00410.006
NPP
11934
15
1.81e-7t5.120-8
8.67e-718.1Ies
MH
13932
16
0.02+10.0008
0.032::00.011
0.023:+0.011
FIFA
19178
0.5710.026 29
0.60:10.025
0.61100.27
SUC
20263
82.1816.60 82
286.6.18.7
94.10.15.62
CH
20460
0.053=0.0026
0.13+00003
0.052+0.0027
KC
21613
22
0.036+0.0012
0.055++0.0011
0.028+0.0000
HI
22272
12
226.82-44.39
220.68++3.66
220.42+t5.1 52
CPS
28155
0.27710.004
0.282+:0.0047
0.283:10.005.
PP
45730
11.59+0.21
28.60++0.32
15. 12400.2
SA
48933
5.34+00074
68.55+2.47
7.72+0.23
The best performing values are highlighted in bold.
11

---

Published in Transactions on Machine Learning Research (06/2025)
4.6 Ablation study with feature selection
To see how much gain comes from using response Y to guide splits instead of filtering noisy features, we conducted extra comparisons between RLF and two-stage RF where we first do a fcature selection to remove most noisy features and then fit. a RF. In the feature selection part, we follows the strategy of laking the top 30% important features based variable importance score from fitted RF. The other training details follow Appendix E for the sake of time efficiency. The results summarized in Table SS1 in Appendix J illustrates that the original RLF still outperfomms RF(with feature selection) in most real datasets and if we apply the same feature selection method to RIF, the performance of RLF will be better than that of RF as well, which another strong evidence of the superiority of RLF.
What's more, in sparse model example (section we took the top 35 most important features through variable importance score. The 10-fold cross-validation testing MSE of RIF is less than that of RF with feature selection which strengthens the advantage of RLF. See Table S12 in Appendix J
5 Discussion and Limitation
Theorem 3.1 has shown the benefit of Lebesgue cutting in reducing the L2 error of RLF. Section 43 further demonstrates the flexibility of RLF in many complicated models and real world datasets with tuned p. The asymptotic normality in section 3 is useful for statistical inference such as confidence intervals and hypothesis lestings (Mentch & Hooker 2016). It's possible to oblain a Berry-Easeen bound of RLF in large N-selting by similar arguments. However, this bound can be worthless in practice as it's requires N > n and we decide not to pursuc it this paper.
Although the experiment results show that tuned p superior than data-driven p, the cross-validation tuning process is less time efficient than data-driven methods in large datasets. How to choose the optimal value of P is an interesting problem. On the other hand, employ Bernoulli random variable to determine the splitting type at each non-terminal node. It's possible that there are other better regularization methods to control the overfitting resulted from Lebesgue splitting. Connecting RLT with boosting would be another riveting direction as RLT is essentially a new kind of base learner in ensemble methods.
Developing a more efficient local model for RLF would benefit RLF in large datasets. As we discussed in section 3.3, the time efficiency of current RLF can be improved by employing less number of subtrees in local forest and setting larger value of control probability P that cach RLT won't perform too many Lebesgue splittings. For example, if we set Moxet = 1, that is, we employ a local decision tree as the local model in RLF, the results in Table [55 still demonstrate that RLF could achieve comparable testing MSEs with less running time, especially in large datasots, which illustrates the potential of RLF under efficient local models.
Readers may view the use of Riemann-Lebesgur Tree as counterintuitive if the local models (e.g local forests or local decision tree) can estimate response Y precisely. However, the local models don't have to be as good as the RLF or RLT since we only require the local models to indicate the direction, not the precise prediction of new points. What's more, when the response is complicated, indicated in example 2 (mixture model with prior probability), we can employ more Lebesgue type splittings in RLF to partition the range of response Y. As a result, the local distribution of Y becomes simpler, which will relax the requirement of the precision of local models. The flexibility of RLF comes from the control probability 9, which controls the number of Lebesgue type splittings in each RLT and can be tailored to different cases. However, we confess that the introduction of local models in the prediction part of RLF can complicate the interpretation, implementation and analysis of RLF. This is a potential limitation of our method. Theorem 3.1 only discusses the variance reduction in training data. As for the generalization error of RLF, , we need to derive the variance of individual RLT according to the bias-variance decomposition formula proposed by Louppe (2015). which is complex due to the local models. Deriving the generalization error of RLF and simplitying the implementation and interpretation of RLF would be our future works.
In more general scenarios, how to cope with possible missing values descrves deep inspection since RLF replies heavily on the information from all variables and it's possible that the prediction of local RF in RLF could be misled by missing values. Actually, in practice, we can perform imputation by rough average/mode,
12

---

Published in Transactions on Machine Learning Research (06/2025)
S13 in Appendix by an averaging/ based on proximities during the data preprocessing. Table
illustrates the promising performance of RLF with simple median imputation strategy in two real datasets with missing values as described in Fischer et al. (2023). How to further generalize the implementation of RLF in missing value cases is one our future work and is out of the scope our current paper.
Broader Impact Statement
In summary, this paper aims to provide new ideas designing base tree learners. We analyze few theoretical properties of RLF. which should have no societal impacts. As to the application of RLF in regression tasks, we think most possible impacts may come from the ethics of datasets. It's possible that some public datasets be biased during data collection process. For example, information from minority may be inappropriately ignored or processed. In this sense, users should be careful in selecting datasets. In our paper, all datasets used in experiments are available on openml (Fischer et al. 2023
References
Dhammika Amaratunga, Javier Cabrera, and Yung-Seop Lee. Enriched random forests. Bioinformatics, 24 (18):2010-200) 2014, 07 2008. ISSN 1367-4803. doi hit.://///ooiioooaaaeess//aaa//e bbtn356 URL 1003/bioinformaticcs/oonao
L. Breiman. Random forests. Machine Learning, 45:5 32, 2001. URL http:://app.sseannicccchooo CorpusID:89144
L. Breiman, Jerome H. Friedman, Richard A. Olshen, and C. J. Stone. Classification and regression trees. 1984.
Yuchao Cai, Yuheng Ma, Yiwei Dong, and Hanfang Yang. Extrapolated random tree for regression. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (ods.), Proceedings of the 40th International Conference on Machine Learning, volume 202
Proceedings of Machine Learning Research, pp. 3442 3468. PMLR, 23 29 Jul 2023. URL https //prccediigg. mlr wttpppess/////2/0//p/ caiodd. html
Louis H. Y. Chen, Larry Goldstein, and Qi-Man Shao. Normal approximation by stein's method. 2010. URL sttps://aph wew.aattticcccolla..oooooo/rpopp 11853311844
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 785 355-794, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322. doi 10. 00.1145/2939772.2337777
URL http://///oo..rrro.1114////99999
Xiaohui Chen and Kengo Kato. Randomized incomplete u-statistics high dimensions. The Annals of Statistics, 47(6).pp. 3127-3156, 2019. ISSN 00905364, 21688966. URL https://www. jstor. org/stable! 26867161
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithums, Third Edition. The MIT Press, 3rd edition, 2009. ISBN 0262033844.
Bradley Efron and Robert Tibshirani. Improvements on cross-validation: The .632+ bootstrap method.
Journal of the American Statistical Association, 92(438):548 560, 1997. ISSN 01621459. URL http:
//www.jste www.orro//sttabee22e6666
Sebastian Felix Fischer, Liana Harutyunyan Matthias Feurer, and Bernd Bischl. OpenML-CTR22 a curated tabular regression benchmarking suite. In AutoML Conference 2023 (Workshop), 2023. URL
https://openreviee hwt..e//foorur///ddeeooooooo http:///ppppaeeeeeeeeeee///atttn
Indrayudh Ghosal and Giles Hooker. Boosting random forests to reduce bias; onc-step boosted forest and its variance estimate. Journal of Computational and Grophical Statistics, 30(2):493-50) 2021. 10. 101008001161800 1tt///16166000 8600.2000.18200222200
URL http::/://oolalooo/o..////////aa 2020. 1820345
13

---

Published in Transactions on Machine Learning Research (06/2025)
Debopriya Ghosh and Javier Cabrera. Enriched random forest for high dimensional genomic data.
IREE/ACM Trans. Compud. Biol. Bioinformalics, 19(5):2817- 2828 jun 2021. ISSN 1545-5963. doi 10.1109/TTCBB TTA.:///TCC...2211389988821
URL ptttp:://boi..rr/11.110000 10. 110.9/CC9/BBBB 200.000220090
Jeff Heaton. An empirical analysis of feature engineering for predictive modeling. In SoutheastCon 2016, pp- 1-6, 2016. doi (0.1100//ECOON22066..660000
Niels Landwehr, Mark A. Hall, and Eibe Frank. Logistic model trees. Machine Learning, 59:161 205, 2003. URL
Alan J. Lee. U-statistics: Theory and practice. 1990. URL http::///ppp....eaa...o.oooooooa
125216198
Gilles Louppe. Understanding random forests: From theory to practice, 2015. URL https://arxiv.org
abs/ ftts/107.7755
Lucas Mentch and Giles Hooker. Quantifying uncertainty in random forests via confidence intervals and hypothesis tests. J. Mach. Learn. Res., 17(1) 881, jan 2016. ISSN 1532-4435.
Claude Nadeau and Y. Bengio. Inference for the generalization error. Machine Learning, 52:239-22 281, 01 2003. doi 10.033// A: 1:1024068626366
Weiguang Peng, Tim Coleman, and Lucas K. Mentch. Rates of convergence for random forests via generalized u-statistics. Electronic Journal of Statistics, 2019. URL httpp:://op...mmmaticcccit org/ org/CorpusID;
209944194
Erwan Scornet, Gérard Biau, and Jean-Philippe Vert. Consistency of random forests. Annals of Statistics, 43: 2014. URL
Robert Tibshirani Trevor Hastie and Jerome Friedman. The Elements of Statistical Learning. Springer New York, 2009. ISBN 9780387848587. doi 10.1007/b94660
CRL
A. W. van der Vaart. Asymptotic Statistics. Number 9780521784504 in Cambridge Books, Cambridge University Press, July 2000. https: /
repec. bttt::://daas..rrpe..ooooobb/bb ott.o//aaae///eaaaa.....ooooooor
Baoxun Xu, Joshua Zhexue Huang, Graham J. Williams, and Yumming Ye. Hybrid weighted random forests for classifying very high-dimensional data. 2012. URL http:://appp.semaanicccccccccloe org/ hatg//orpussD. 10700381
Zui-Hua Zhou and Ji Feng. Deep forest: Towards an alternative deep neural networks. In Proceedings of the Twenty-Sirth International Joint Conference Artificial Intelligence, 1JCAI-17, pp. 2017. doi 10. 24963496///
URL. sttps://dol..org/11.2455555
249p3/1....9331111 iicae/////jaaaa../e/ 2017/449
14

---

Published in Transactions on Machine Learning Research (06/2025)
Appendix
A
Data preparation and statistic tools used in real data experiments
Table summarizes the datasets we used in experiments. Note that there are 35 datasets original benchmarks. We didn't perform comparison on the datasets with the number of instances more than 50,000 since the complexity of RLF is relatively higher than RF. We also excluded datasets with missing values whose results might be unfair. We took logarithm transformation for some datasets alleviate the impact of skewness. As described in Algorithm we set the subagging ratio to be 0.632, which should have the same efficiency with bootstrapping (Efron & Tibshirani 1997
Table S4 Real datasets used for the experiments,sorted by size
Observations
Numerical
Symbolic features
Log transformation
Forestfire (FF)
517
No
Student performance (SP)
No
Energy efficiency (EE)
768
9
No.
CarR(CAR)
804
18
No
QSAR fish toxicity (QSAR)
908
7
No
Concrete Compressive Strength (CCS)
1030
9
No
Socmob(SOC)
1056
No
Geographical Origin OF Music (GOM)
1059
No
Solar Flare (SF)
1066
3
No
Airfoil Self-Noise (ASN)
1503
6
No
Red wine quality (WINER)
1599
12
No
Auction Verification (AUV)
2043
No
Space (SG)
Abalone (ABA)
4177
No
Winequality-white (WINEW)
4898
12
No
CPU Activity (CPU)
8192
22
No
Kinematics of Robot Arm (KRA)
8192
9
No
Pumadyo32oh (PUMA)
8192
33
No
Stability (GS)
Brazil Housing (BH)
10692
6
Yes
Naval propulsion plant (NPP)
11931
15
No
Miami housing (MH)
13932
16
Yes
Fifa (FIFA)
191 78
28
Yes
Kings county (KC)
Yes
Supercondduttvvity (SUC)
20263
82
No
Califonia housing (CH)
20460
9
Yes
Health insurance (HT)
22272
5
No
CpsSSwages (CPS)
28155
3
Yes
Physiochemical Protein (PP)
45730
No
Sarcos (SA)
22
No
We employed corrected resampled t-test (Naccau Bengio 2003 Landwehr al. 2003). identify whether one method significantly outperforms another 5% significance level. This test rectifies the dependencies of results induced by overlapped data points and has correct size and good power. The corresponding statistic is
15

---

Published in Transactions on Machine Learning Research (06/2025)
Σ -1=1
V 22 )02
where V is the number of validation experiments performed (ten in our case), Va is the difference in MSE between RLF and RF t-th fold. & is the sample standard deviation of differences. is the number ofdata points used for training and ngis the number of testing cases. In our case, n2/n1 = 1/9 since we used 10-folds cross-validation.
B
Experiment details in sparse model
There are 1000 training cases and 500 test observations. Each subplot in Figure 2 illustrates the curves of mean squared error for RLF and RF, as functions of a single hyperparameter. The default setting for RLF is M = 100, Mtocol 10, 0. 6.632, Mnode 5. Same setting except Miccal applies to RF. To obtain, for example the test MSE as a function of number of global trees, we set M = 1,2, 500 while other parameters remain the same with default setting. Similar strategy was applied to the other three hyperparameters we are interested.
In Fig 2(a) we let RLF and RF share the same the number of trees. We observe that the MSE for RLF decreases more than that of RF as the number of trees inereases. In Fig 2(b) RF is fitted under default. setting while we only changed the number of local trees used in local random forest of RLF. As
see, large number of local trees indeed benefits the performance of RLF. On the other hand, in order to control the computation time burden, the number of local trees should not be too large. Fig ((c) implies that increasing the number of noisy variables the regression model will impair both the performance of RIFF and RF. Nevertheless, RLF always outperforms RF, which is anticipated. To see the impact subagging ratio on RLF, we first controlled the result from ordinary RF under default setting and increased subagging ratio, which determines the subsample size in RLF, from 0.4 to The test MSE curve for RLF in Fig 2(d) indicates that even small subagging ratio could generatea decent result. We therefore set the subagging ratio relatively small to make RLF efficient.
C Incomplete U-statistics
Before give the definition of incomplete U-statistics, we first give a brief introduction of U-statistics. We borrow notations from (Vaart 2000). Suppose we have i.i.d samples Xi..., X, from an unknown distribution, and we want to estimate parameter defined as follows
0 = Eh,,,,...,.. X,,
where the function h is permuutation symmetric in its arguments and we call h as kernel function with order r. Then a U-statistic with kernel h is defined as
U = Σ B
S(, X8.)
where the sum is taken over all all unordered subsets 3 with r distinct elements from {1, n...,,
Note that the U-statistic is an unbiased estimator for and has smaller variance than a single kernel h. practice, it's unrealistic average all (") kernels (trees). To make U-statistics more useful in applications, can define an incomplete U-statistic which utilizes smaller number of subsets follows:
N
1
Un =
h h(X (X..
N
when N (*), we obtain complete U-statistic.
16

---

Published in Transactions on Machine Learning Research (06/2025)
When the total number of subsamples of size taken from sample of size is large, it may be convenient to use instead an 'incomplete' U-statistic based on N suitably selected subsamples. Asymptotically, it can be shown that an incomplete U'-statistic may be asymptotically efficient compared with the 'complete" one even when increases much less rapidly than the total number. See more explanations and applications for /inollett///coplltte U-statistics in (Vaart, 2000 Riemann-Lebesgu Forest, each tree can be viewed a random kernel since is permutation symmetric w.r.t inputs. The randomness of the kernel comes from feature bagging and subsampling and cutting types. Similar definition can be applied to RF well.
Lee 1990 Peng et al. 2019 Chen et al. 2010p. In a
D Consistency of RLF
Based on the results from (Scornet al. 2014), it's relatively easy to derive the consistency of RLF under additive regression model follows:
= Σ m +
where X = (X,, Xp) is uniformly distributed over [0, 1J", the noise e N(0, o2) has finite variance and is
independent of X. Each component function my is continuous.
When there are only 8(< p) effective dimensions of the model, the sparse version of equation becomes
Y= Σ my (X,) te
which is exactly the condition where RLF may perform better. Therefore the additive regression model is a good framework for studying the consistency of RLF. Since the Lebesgue part of each Riemann-Lebesgue Tree is essentially splitting the response Y with CART-criterion, many consistency results for CART can be applied to RLT directly.
For example Breiman et al. (1844) proved the consistency of CART under the assumptions of shrinking diamcter of cell partition and lower bounds of empirical distribution of X. Scornet et al. (2014) shown the consistency of RF under the assumption of additive regression model and appropriate complexity of the tree partition.
We now state version of consistency adapted to RLF where assume that the total number of nodes t, in each RLT approaches to infinity more slowly than the subsample size kn. The proof follows immediately from the argument for Theorem in Scornet et al.) 2014
Theorem D.1. Assume the response Y is generated from the sparse model defined in equation g Then, given kn + xo, In + oo and L (logk,))) /kin + 0 where kn is the subagging size and in is the namber of lerminal nodes in each Riemann-Tebesguee Tree, we have
lim Ex m n
where m(X) [E]] hi (X) Eu, (h(w) (x; (X; The consistency of empirical averaged RLF estimate follows from the law of large numbers.
Note that Theorem D.1 still holds even when select all data points for each tree, which means controlling the number of nodes by via minimal size of nodes Mnode is sufficient for the error bound of RLF. According to (Scornet et al. 2014h. the term (logk,) results from the assumption of Gaussian noise. We can replace it by bounded random variable so that the term (Iogk,)) becomes logkn, which can be regarded as the complexity a single RLT partition,
17

---

Published in Transactions on Machine Learning Research (06/2025)
E Running time for RLF and RF
For completeness, Table S5 compares averaged running time (in seconds) and margin of error with 95% confidence level of RLF, RRF on our selected datasets in manuscript. For RLF, M 100, Mical = and p = 0.8. For RF, M 100. Other parameters are set by default. values. We ran 10-fold cross-van validatiio,, We calculated the running time as sum of training time and prediction time.
Table Average running time (in seconds) and Testing MSE for RLF RLF(110, (100,1),
Dataset
Observations
Features
RLF(s)
(s)
RLP(TTssiig MSE)
RF[Testing MSE
517
11
0.11=000005
0.0941 0.028
1206.94 6398.57
4431.81 + 5163.97
SP
649
31
0.20::0.028
0.19:10.004
1.78:10.78
1.7810.75
EE
768
9
0.051110.002
0.032:10.00
0.95
1.28:10..4
CAR
804
18
0.099-:0.0025
0.085+0.003
5180401
808978.6
6380755:::000
QSAR
908
7
0.12#0.001
0.08
0.75:t0.12
0.76:t..12
CCS
1.1840.11
0.13:10.038
23.73:11.18
28.09:44.02
SOC
1056
6
0.07+0.01
0,048+0.006
523.30+196.
579.314202.
GOM
1059
117
1.85:$0009
1.56:10.077
244=26.31
247.17:-27.6
SF
1066
11
0.1110.0004
0.0910.005
0.67:0.2
0.67
ASN
1503
6
0.1200.003
0.08:10.001
9.6:11.1
12.86:: 2220
WINER
12
0.40=0.051
0.30#0.03
0.327:00.033
0.329+00008
AUV
2013
8
0.21
0.15=000008
6148974: 7
94515511962651.
0.01410.0047
ABA
1177
9
1.60
1.28
4.56+00.54
1.59+0.35
WINEW
4898
12
2.40:10199
2.49:00500
0.36410.002
0.36410.0119
CPU
8192
22
9.77.0..47
16.6311.09
5.79.10.53
5.95100.9
KRA
8192
9
4.42:10.51
1.2
0.0215::0 0006
0.0214:0..o 0000
PUMA
12.1941.37
1.12
0.0005=1.31e-
1.0005#1.31es
GS
10000
13
8.45:10.21
16.8122.118
1.47e-413.39e-
1.5e-424.88e-
22.47
0.01110.011
NPP
11931
15
12.62=11009
1..4
6.85e-74:9. 1555-749944844
6.5de-719.05e-
MH
13932
16
15.5110.55
36.2413.72
0.02110.001
0.022.10.00
FIFA
19178
29
43.63-15.05
226.641
0.57:10.224
0.58:10.023
SUC
20263
82
151.14:18.22
216, 166.39-116
85.1925.89
83.96:5..2
20.000000000
0.058+0.000%
0.059
KC
21613
22
114.52 10.46
147.151199.8
0.03610..01
0.037:10.00
209.71
326. 78.
215.79.1..51
212.65
CPS
28155
7
28.55
39 6.72
0.271
0.28-10..000
45730
10
311.77 1 48.19
1439.81 142.50
12.2710.18
12.04.1.11
48933
22
462.79-110..85
2349 2349.6331900 950.85
6.43::0.32
6.33+0.32
Table Training time RLF and RF under simulated
Sample size
Training time of (secondddss)
Training time RF(ssconds)
1000
0.29
0.20
10000
8.9
20000
26.51
123.98
40000
90.72
829.43
50000
222.75
1649.24
60000
298.40
2583.99
70000
536 60
5050.07
80000
7141.25
90000
1499.06
9714.01
Simulated data are generated by the following regression model
10
== 10
II e 2x3 te. E~ N(0,00
where X, is the j-th dimension of an observation x. Random sample X will be i.dd and uniformly distributed on the 10-dimension unit discrete cube [1, 3, 500 and =1
F Proof of Theorem 3.1
For simplicity, we assume one-dimension case, i. Y = f(X) + E. Since the noise term is independent of and Var(Y)= Var(f(X)) + o² where a is the variance of 8, it's harmless to ignore it in the derivation
18

---

Published in Transactions on Machine Learning Research (06/2025)
of variance reduction of Y. In other words,, consider Y f(X). Let A2 be nontrivial partition (mutually exclusive) of the initial outcome space, then we have
Var(Y) Var((Y(A,))) + 1A.)) Var(Y Hor +Cou(Y (Coo(Y1oo Y1Az) -arr(Y1A,) Var(Y1A,) + (E(Y 1 L|YLA, Aall
where A1, AA are indicator functions for events A and A2, respectively.
Note that A1 and A2 are mutually exclusive, 14, 1A, = 0. It follows that
Var(Y) Var(Y + Var (ar(Vallaa Ao) (
Var(Y1A,) Var Y Y 2E[Y1A,] (p E 1A.))
WLOG, we can assume E| = μ 0, then we have
Var(Y) Var(Y Var(Y1AA) 2(E
In Lebesgue cutting, have A =Y 2 a2 {Y < a). Then the theoretical variance reduction of Y in the initial outcome space be written as following:
Var(YlA,) 2(E
To find optimal splitting point which gives the maximal variance reduction, we should solve the following optimization problem.
max [L(a]]
where
L(a) 2(E
Similar argument applies for Riemann cutting. Let Riemann partition be B = = 2 b). B2 = (X < b}, then the corresponding optimization problem for Riemann cutting would be
max ( max [R(b]]
b
where
R(b) = 2x
Let b* be the optimal Riemann cutting, i.e. R(b') maxt [[(b]]. It's not hard to see
Yly<o Y1x22 & Ylv20-
Then it follows that
EYY1y< <o) E|y1x E|Y1r20
By the assumption: 0= E Ely + E ly we have
-E[Y1val & E|1xgrl S E[Ylye
As a result, the following inequality always holds:
(E|1xx>-1)) {E)
And we have
max[L(a)] 2 L(0) 2(
max[R(b)] R(b))
(10)
a
19

---

Published in Transactions on Machine Learning Research (06/2025)
In other words, the optimal Lebesgue cutting reduce least the same variance as the optimal Riemann cutting (CART). We can also see the noise doesn't 't affect the conclusion since Y already absorbed noises in practice.
Another analysis of equation 10 from a discrete case:
In discrete case; we need to compare L(j", 8*) and [(st,) as defined equation and equation
Note that the set of possible partitions of current set of responses induced by the Riemann cutting of covariate X is subset of that of Lebesgue cutting whose feasible set is essentially induced by response directly. Note that the objective functions L(j, s) and L(s) have the same form, the one with larger feasible set should have larger optimal value.
Suppose we have n points {(X1, Y1), ..., (Xn, K,)) whose values are all distinct a certain non-terminal node and both cutting types employ CART split critcrion, then Lebesgue cutting will go through all (n + 1) splitting points in Y directly, which essentially gives the largest feasible set of optimization problem. On the other hand, in Riemann type cutting, the space of Y is indirectly partitioned by going through all possible splitting points in direction X It's not necessary that this procedure will take care all (n + 1) splitting points in Y. For example, when X is direction with only three distinct values 200 can only have four choices of splitting point which will restrict the possible values of YA, VAR in optimizing Líj, 8) and leads to a smaller feasible set.
G Proof of Theorem 3.2
We basically follows the idea (Peng et al., 2019 as sum of complete U-statistic and remainder. To deal with the random kernel, we utilize the conclusions based extended Hoeffding decomposition (Peng et al. 2019 For the simplicity of notation, it's harmless to assume that 0 O.
which dccomposes the generalized incomplete U-statistic
For < V/u < 1,, we first decompose Un..NN.w. V //2 n + St/N2w as follows:
Pi (ip(ws) (Zi. ..., Zi,) + 1 E(,,))
E((nk)
Wi-Pe ((() (Zi,, .... Zi,)
Nn
(R)
p
(2)
ASLL + Ct
72
N
(11)
A
Wi-ei ((w) (ll))(2))) (Zi, ..., Z1ee)
(n,k)
p
+ S4
where
Pi h (wx) (Zi,: Line
A
P
k))
(12)
(ch(we)
ZZi, .... Ziee
N
(m)))
and Pt Bernoullipp), p= N/(W) and N E(m,y) Ps. We can see F[N] = N. WT.OG, we can assume
sidd
0 On.k.N 0. Then we have
A
B
(13)
where
B =
1
Σ
pih (wx) (2ig, (Zig...., 7in)
N
(n.))
20

---

Published in Transactions on Machine Learning Research (06/2025)
and B is complete generalized U-statistic with Bernoulli sampling as described in Peng et al. According to Theorem 4 in Peng et al. (2019), we have
2019
supsem p
B /keraw//n St/N (PVVe
E 3
x(z)
S C
(1
n
SK
]
1/2
k
1/3
(14)
+
+
N
+
n
92
= Eo
where 0 1/0 < 1/2.
By definition, we have So var(h) = E|// Σ k,n
Denote
T
WA
R SA/N
where
B
W /1/ + C//N
A =
1)W
N
According to the argument in proof of Theorem 4 in Peng et al.
2019
it's easy to verify that
P -- salwws s=)
|
P U S SS p W <=
< P
= = w S S 1
Thus we only need to consider bounding P(: < W S 2 1A)). By Bernstein's inequality, we have
- P 1 E < <eep
N
(1-p+e/3
Let 6 N-8 and note that P(Z) 2 Na) S 2exp( -N2a 12), we have
N
P([ N- <P
- 1/ 2 N-9 + P([W 2 No)
N
N1-28
< 2exp
+ 2 No) + 250
1 - p N N/113)
(15)
2exp
(1- (1-p)N2--1+++1 +N3-1/3 -2ex((-V20/2) + 25D
= E1 + 250
Eventually, we can bound P(z < W < + A follows:
P(2 <z+1A) < P < < < + AI S NN P(I Z N-8+9)
< P(2 < W = N N- + + 25D
< 2en P(= 7 = N- + 250
(16)
1 B-ta
S 450 +61 +
= 450 + El +
Let B 3=0 0.5 + mn and m, where m > It's easy see 61 62 when N is large and therefore
21

---

Published in Transactions on Machine Learning Research (06/2025)
A Gr Sx/N
sup sER
2(2)
= sup sER
P(T - 2) -((2)
sup sER
P(W Σ ((2)
+
sup SER
P(T S 2) - P(W s
$ 550
+ 51 +
(17)
Blg 3
/2//2///2 2//2
n
Ck -
1/2
k
1/3
1 + + N +
+
+
n
kG1
?2
= Eg
We observe that the factor of Ñ /N only produces the extra term N in the final bound, which is similar Peng et al. 2019). We employ this technique one more time to achieve the bound for N.
Denote
Un
D VK2Ge//n + Cx/N
+C=
Ce
Ce N
+
5t N
where A is defined as above and
W. [(w)) (Zi, .... Ziee
km
P
Pt (w)) (Zi,: (wm))) W
C
D
Zen
V //2Gi// + Cx/N
p
(n.
Again, we only need to bound P 25
s +11)
Let 0 < no < 1,, by Jensen's inequality, we
Re Ez
have
P([C) 2 112-
< N10-121))
E C|| < N To C|
(18)
Note that Ghosal & Hooker (0021) illustrates that these two selection schemes (sampling without replacement and Bernoulli sampling) are asymptotically the same. More specifically, one can show that
B R ( E (., (2))))2))) = K
N
(*)
where Z; represents the i-th subsample from (Zz, ..., Zn) and K E((h(=))Z (Z.)) Var(h(()((z)) Se since assume that 0 = 0.
22

---

Published in Transactions on Machine Learning Research (06/2025)
It follows that
P(C N10-1/2) S N 22:2m -0o k(
$1
Ck
+
NV.
. _ $1
22 Sk
= (K(1 -p))
N
Sww
-K((1 p))
+
NN 12
n/N2nm
(19)
I (K(1 p))
nnN22m
n
= (K(1 - p))
(1 P)
N22m k2 S1.
2 P(2S
Eventually, we can bound P
S <2+101) as follows:
| $
A
A
P
s=+ 101
SP4 =
S
11.,10
P([C) N-1/2)
S1. +
+
n
N
A
12 12++21122 +
(1 p)sk
P
220
+
CE
S + P(2 S 7 < 2 N 1/2) 1-1/2] +
n
p)Sk
22m
1
(N - p)sk (1-M)<))
E3 +
N 1-122 +
N20 k:2
(20)
Note that E3 also includes terms of order 1/2 and therefore
sup P UnA.NN
A
+())
I sup =ER
P(
2 - 4(=)
( (12Si// Ct/N
R
+ 1V
A
sup =ER
P(Un,K.Nw 5z) Pl
I 2)
R n
+
NV
1
1 N-1/2
(1
S + E3
22
2
k2
(21)
Elg/3
EJM|3
1/2
3/2
N
)
1/2
1/3
+
+
N
$ 10
7
11
(1
S)
1/2
22n
1:2 C1.
23

---

Published in Transactions on Machine Learning Research (06/2025)
where C is positive constant.
H
Tuning results for two examples
Mean squared error
2.00
Mean squared emro
50
RF
RF
1.75
45
RLF
RLF
40
1.50
35
1.25
30
1.00
0.25
0.50 0.75 1.00
0.25
0.50 0.75
1.00
Control probability p
Control probability p
(a) Example 1
(b) Example 2
Figure S4: Test MSE function of control probability in two examples
Table S7 Top 10 tuned models for RLF and RF for Example 1
Rank of Validation MSE
RF
M wodie
M
RLF
Mooca
1.308092
0.5
15
100
1.081210
0.4
10
1.309780
0.5
50
1.085926
0.4
20
1.313989
0.5
15
200
1.08009
L.315487
0.63
5
200
1.117446
0.6
50
1.3166665
1.125599
1.316748
0.63
10
50
1.127603
0.6
20
1.320919
0.8
10
200
1.128331
0.2
10
1.326341
0.5
10
50
1.150248
20
9
1.327373
0.8
150
1.164717
0.2
50
L.327539
0.63
1.197099
Table
Testing under optimal model for Example 1:
Bset
Best RLF
Testing MSE
1,283
1,088
Table
Top tuned models for RLF and RF Example
Rank Validation MSE
RFF
a
Moodo
ILL
Micent
33. 18551
0.63
15
100
28. 18683
0.1
10
34.40944
29.34517
34.53584
0.63
5
200
29.53972
0.4
20
34.61853
0.63
10
100
29.72733
0.4
50
5
34.64231
0.63
50
29.98644
20
34.76124
0.8
50
30. 30.22297
0.6
10
31668
0.63
30.31668
8
34.86602
0.5
15
150
30.33824
0.6
50
34.99652
30.94450
10
35. 19693
0.63
15
150
32.03 02
0.8
10
Table S10 Testing MSE under optimal model for Example
RF
Best RLF
Testing
35.17
24

---

Published in Transactions on Machine Learning Research (06/2025)
Tuning procedure: For each example, we generated 3000 samples from the corresponding model and divide in into three parts for training, validation and testing. The ratio is 6:2:2. For R.F, we set subagging ratio E {0.5, 0.63, ).8), minimal node size Mnode E (5, 10, 15} and number of trees M E {50, 100, 150, 200]. For RLF, we keep M = 100 and a = 0.63 all the time for efficioncy. We set á E {0.2, 0.4, 0.6, 0.8] and
Mocal {10, 20, 50} which are two new parameters roduced RLF. Fig. (4(a) and S4(b) are Test MSFs for RLF as functions p with M 100, Mocct 10. For RF, we use the default setting.
Extra experiments with tuned RLF and RF
We performed extra experiments on 26 datasets (due to the time efficiency of parameter tuning) to compare best RF and best RLF.
We performed 5-fold cross validations to ensure 20% of observations are used as testing set. For the rest of 80% points, we further randomly pick 25% of them as validation set, which is used to select best models among parameter space. As a result, the ratio of training, validation and testing 6:2:2.
valiiingvalldation
Tuning parameters for RLF: P E {0.4, 0.6, 0.8). We set M 100, Moeel 10, Mrode 5 all the time for RLF due to the time efficiency. Tuning parameters for RF: M E {50, 150, 200), Mnode E (5, 10, 15). Other parameters for RLF and RF follow the default value. Note that the implementation of RF in R doesn't 't have parameter of tree depth but we control and depth of tree by the value of minimal size of node Mnode.
J Extra experiments: Ablation study with feature selection
Table S11 Testing MSE for ablation study(10-fold cross-validation)
Dataset
feature selection
RFF-ffaature selection
RIF((10,, 10)
FF
4246.508 1. 292
4255.631 15497.251
4205.21 21 1: 5612.77
SP
1.60 10.62
1.724 0.62
1.90=0.87
CARS
18396078 = 2977821
205419912 3358102
5374818+187019.
ABA
7.24
7.264
4.63
KRA
0.05 + 0.0018
0.0511 0.0019
0.0188 10.00062
NPP
6.77e-6 1.0e-75
1.92e-5tt 9.58e-7
5.97e-7=0.81e-
GOM
234.149 + 26.31
236.124: 28 65
240.67113.74
SF
0.6178 1 0.224
0.61831 0.225
0.66
CCS
79.56 7.21
82.361 7.38
28.3424.87
SOC
618.86 + 180.31
635.3544 175.10
587.87=205.
EE
4.25
6.00:
QSAR
0.97 1 0.15
0.981 0.15
0.7568 10.14
ASN
28.02 + 2.31
28. 03 2.28
11.87 +1.28
WINER
0.35 1 0.032
0.34 0.033
0.331910.034
AUV
14457235 2492794
17803133122 202213311222322
8073182 11513348
SG
0.0183 + 0.005
0.01824 0.005
0.01367 +0.0045
WINEW
0.41 + 0.018
0.42+ 0.018
0.367=0.021
CPU
249.68.1 21.71
251.671:
5.72
PUMA
0.000495-1 1.17c-5
0.0005= 1.24c-5
4.97o-4=
GS
0.000741 2.10e-5
0.00075::: 2.13E-5
1.2e-414..66--6
BH
0.0127 0.00961
0.01421 0.010
0.01 10.01
MH
0.041= 0.0023
0.045: 0.0022
0.02 +0.0009
FIFA
0.588
0.593
0.6776=0.026
Table S12 Testing MSE for sparse model ablation study(10-fold cross-validation)
RF ffeatrr selection
RLF+feature selection
RLF
Testing MSE
3.90 + 0.35
3.78 + 0.33
4.17 0.40
25

---

Published in Transactions on Machine Learning Research (06/2025)
K
Extra experiments: Missing value case
Table $13: Testing MSF((1-fold cross-valiaation) of RLF and RF under missing value cases
Dataset
RLF
Moneyball
656.91 + 84.90
670.1 + 94.46
FPSbenchmark
11.04 0.55
20.24 0.95
26


Reviews:
[{"review_id": "dZD4NVTqUe", "reviewer": "Reviewer_1tDv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe idea of mimicking the way of partitioning in the Lebesgue integral is clever, although at first sight it is hard to implement for prediction problems since the response is not available. The paper resolves this issue by leveraging a local model such as the random forest to first obtain an estimate of the response and then apply the proposed method.\n\nWeaknesses:\n\nI have major concerns about the impact of the local model, the relevance of the theoretical results, and presentation of the paper.\n1) The choice of the local model seems crucial for the performance of the proposed method. The current implementation uses the random forest as the local model and yields an improvement over random forests as expected. The algorithm is adaptive in its nature and cannot perform well if the local model performs poorly.\n\n2) The theoretical results in Section 3 are not directly related to generalization of the proposed method. In particular, Theorem 3.1 concerns only the variance reduction in the training data. The asymptotic normality in Theorem 3.2 is proved under the randomness in the algorithm itself rather than the randomness in the data, and hence does not lead to valid inference about the prediction.\n\n3) For random forests equation (1) gives an explicit form of the prediction rule. The paper never gave a clear definition of the proposed prediction rule.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Riemann-Lebesgue forests for regression, which replaces the prediction space partitioning in random forests by response space partitioning. Theoretically, the paper shows that this new type of tree splitting rule results in larger variance reduction than optimal CART splitting. Berry-Esseen bounds for asymptotic normality as well as complexity analysis are provided. Numerical experiments and comparisons with random forests and boosting methods are carried out using simulated and real data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) I wonder how robust the proposed method is to different choices of the local model. More experiments could be done to examine the impact of the local model on performance.\n\n2) Is it possible to provide theoretical guarantees directly for the generalization error of the proposed method?\n\n3) What is different in Theorem 3.2 from those for random forests? The authors discussed some improvements over the existing results, but these do not seem to relate to the Lebesgue splitting rule.\n\n4) It would be clearer to give an explicit expression of the proposed prediction rule, similar to (1).\n\n5) Algorithm 2, line 4: It is unclear how the predicted value of the tree is computed at point $\\mathbf{x}$. Is the local model used here to first obtain an estimate of the response?\n\nMinor issues:\n1) Abstract, “We also generalize the asymptotic normality of RLF”: Is there an existing result for RLF which you can generalize? Otherwise, “establish” is more appropriate.\n\n2) Page 2, line 5, “… take the limit of step functions. But that is nearly undoable in practice”: Taking a limit is a mathematical device and certainly not exactly implemented in practice. I don’t quite get the point of this discussion.\n\n3) Theorem 3.2 should end after “a positive constant.” “The proof follows …” should appear on a new paragraph.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wyF0vWOAMg", "reviewer": "Reviewer_MpUW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nS1. Conceptual Insight: The idea of splitting on the response variable in a decision tree is new in the context of ensemble methods. This is a novel twist on decision tree learning, whereas almost all tree-based methods partition the feature space (Riemann-style approximation), this work explores a different partitioning strategy (Lebesgue-style approximation) within the ensemble framework. This novel perspective opens up a new dimension for improving regression trees.\n\nS2. Well Motivation: The paper is well-motivated by a practical concern: Random Forests can struggle when the signal is sparse across features. By exploiting information from the response, RLF addresses a gap not fully tackled by many existing methods. Most prior attempts to improve RF in such settings involve feature selection or weighting, but not altering the splitting mechanism itself.\n\nS3. Theoretical Contributions: The paper provides a solid theoretical grounding for RLF. The authors prove the consistency of RLF under certain conditions. The result suggests that as data grows, RLF can approximate the true function given appropriate settings. The authors also establish asymptotic normality of the RLF and derive a Berry-Esseen bound. These results could allow us to construct confidence intervals for RLF predictions or perform hypotheses tests, analogous to existing methods for RF.\n\n\n**Weaknesses**\n\nW1: Computational Complexity: A notable downside of RLF is its increased computational overhead relative to standard Random Forests. The training of local random forest models at each Lebesgue-split node, and the evaluation of two splitting criteria at the nodes, can significantly slow down RLF. The authors acknowledge that RLF’s time efficiency is a concern. In experiments, larger datasets are not being used (more than 50,000 instances).\n\nW2. Limited Comparisons and Ablations: the experiments, while extensive in the number of datasets, is narrow in scope of methods compared. The paper primarily compares RLF to the original Random Forest. This makes sense as a baseline, but it would have been enlightening to see comparisons to other baseline strategies for dealing with many noisy features in regression. For instance, one could compare to a simple two-stage approach: first do a feature selection or screening (to remove most noisy features) and then fit a Random Forest, to see if RLF still provides an advantage beyond what careful feature selection gives.\n\nW3. Handling of Missing Values: The current method does not gracefully handle missing values in the features. This can be a limitation because in practice many real-world datasets do have missing entries. A standard RF can often handle missing values by surrogate splits or by the nature of averaging, but in RLF, a missing value could be problematic if it occurs in the features that the local model uses to predict y.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel ensemble method called Riemann-Lebesgue Forest (RLF), designed to improve regression tasks. The central innovation is the introduction of Lebesgue-type splits, where nodes are partitioned based on the response variable rather than solely on predictors. The authors demonstrate theoretically and empirically that this strategy can achieve better variance reduction and predictive accuracy compared to traditional Random Forest (RF) and other boosting methods like XGBoost, particularly in sparse and high-noise regression contexts.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "For W1: address the scalability concern: it would be beneficial if the authors could strengthen the discussion of computational overhead or conduct experiments on larger datasets to help us understand the scalability of the proposed method.\n\nFor W2 and W3: expand empirical evaluation (if possible): to solidify the paper’s claims, it would be beneficial to add or partially address a couple of additional experiments:\n1. Baseline or ablation study: consider adding one comparison to a Random Forest + feature selection baseline. This could isolate how much gain comes from using $Y$ to guide splits vs. simply not using noisy features. If an oracle is too much, perhaps use a simple feature selection on that data (like take the top 35 features correlated with Y) then train RF. If RLF still outperforms that, it’s strong evidence of the method’s value.\n2. Missing value robustness: test RLF on a dataset with missing values or simulate some missingness in an existing dataset and observe its behaviour. Alternatively, implement a simple strategy (e.g., use median imputation before training RLF, or adapt the local RF to ignore missing values) and report the results.", "broader_impact_concerns": "The submitted paper includes a Broader Impact Statement that adheres to established guidelines for addressing ethical, societal, and environmental implications of the research. Based on the analysis of the work and its alignment with current standards, no additional concerns requiring further elaboration are identified.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HMjXYsPyhx", "reviewer": "Reviewer_CcxQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths\n---\n\noverall it's an interesting idea to bring in biases based on the idea of Lebesgue versus Riemann integral. the paper contains a rich mix of algorithm, theoretical analysis, and thorough experiments.\n\nthe experiments show that the proposed algorithm is sometimes on par, and sometimes better than baselines, on a rich set of datasets.\n\n\nweaknesses\n---\n\nfirst, i think the writing needs to be cleaned and improved quite strongly, e.g., see the points below.\n\nsecond, i see an issue on a conceptual level: while i feel the ingredient ideas presented in the paper are interesting, i see an issue with the fact that the Lebesgue splitting approach alone does not seem to determine an actual hypothesis (function) from the hypoethesis class. is this correct? instead, to get to the actual hypothesis, an additional regression method has to be used. this is not per se a problem - it can be a valid approach as well. \n\nhowever, in the abstract, i read the claim that RLT/Lebesgue type cutting results in larger variance reduction than CART. but generally, the core problem is the variance of the *function estimator*, right? and as far as i understand, the RLT/Lebesgue type cutting alone does actually not determine a function. instead, just another form of variance is reduced (e.g., theorem 3.1).\n\nthird, a minor thing: i feel that theorem 3.1 intuitively is correct. however, i would say that the crucial paragraph of the proof (\"To maximize function L(a), a will go through all possible values of Y ...\") should be more formal, because the quantities differ, once its P ( Y ...), and once P ( X ...). probably its just a little extension, but showing the informal statement formally would be an improvement point.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "the paper presents a variant of random decision forests, termed Riemann-Lebesgue forest. instead of splitting the datapoints based on a line in feature (X) space, splitting is done based on a threshold in response (Y) space - inspired by how Lebesgue integrals simple functions approximate the integrand. it is shown that this reduces the loss, that it reduces the variance of Y given the split, and that asymptotic normality results can be derived for this estimator, for confidence bounds etc.\n\nnote that to my understanding, while classic (\"Riemann\") splitting directly implies a hypothesis selected fom the hypothesis class, Lebesgue splitting does not imply a unique selected hypothesis (it only splits Y / the set of empirical data points).\n\nre. proofs, i only checked that of thm 3.1", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "unclearities/improvement suggestions for writing:\n- what is \"random Kernel\", what is \"F_\\omega\"? p5\n- i'd suggest formally introducing the key terms that are used w.r.t. random trees. for instance, on p3 it says\n\"Le A be a generic non-terminal node in a decision tree ...\", but \"node\" etc. das not been introduced formally. informally it's understandable for those familiar with the matter but in the light of this being a theoretical paper i suggest formality as well.\n- $\\bf X^{(j)}$ is defined where? is this a random variable, or a projection (or both)? also $\\bf x_i^{j}$\n- \"part (b) in Fig. 1(b)\"\n- \"Denote N be ...\" p5\n- z is the splitting point in feature space, Z_i denotes (X_i, Y_i). i think that double-use of z/Z is suboptimal notation for the reader to follow.\n- what is $\\Phi(z)$ in eq. 7? the erf?\n- minor: typesetting: i think the quotation marks should rather be those `` '', and not \".", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)