Linear Mode Connectivity in Differentiable Tree Ensembles
Authors: Ryuichi Kanoh
Mahito Sugiyama
Venue: ICLR 2025 Spotlight (2025)
Keywords: Linear Mode Connectivity
Soft Tree
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: Considering additional invariances beyond tree permutation, we achieve linear mode connectivity for tree ensembles.

Abstract: Linear Mode Connectivity (LMC) refers to the phenomenon that performance remains consistent for linearly interpolated models in the parameter space. For independently optimized model pairs from different random initializations, achieving LMC is considered crucial for understanding the stable success of the non-convex optimization in modern machine learning models and for facilitating practical parameter-based operations such as model merging. While LMC has been achieved for neural networks by considering the permutation invariance of neurons in each hidden layer, its attainment for other models remains an open question. In this paper, we first achieve LMC for soft tree ensembles, which are tree-based differentiable models extensively used in practice. We show the necessity of incorporating two invariances: subtree flip invariance and splitting order invariance, which do not exist in neural networks but are inherent to tree architectures, in addition to permutation invariance of trees. Moreover, we demonstrate that it is even possible to exclude such additional invariances while keeping LMC by designing decision list-based tree architectures, where such invariances do not exist by definition. Our findings indicate the significance of accounting for architecture-specific invariances in achieving LMC.

Published as a conference paper at ICLR 2025
LINEAR MODE CONNECTIVITY IN DIFFERENTIABLE TREE ENSEMBLES
Ryuichi Kanoh Mahito Sugiyama" 122 National Institute of Informatics The Graduate University for Advanced Studies, SOKENDAI (kanoh, mahito) @nii.ac. jp
ABSTRACT
Linear Mode Connectivity (LMC) refers to the phenomenon that performance remains consistent for linearly interpolated models in the parameter space. For in- dependently optimized model pairs from different random initializations, achieving LMC is considered crucial for understanding the stable success of the non-convex optimization in modern machine learning models and for facilitating practical parameter-basse operations such as model merging. While LMC has been achieved for neural networks by considering the permutation invariance of neurons in each hidden layer, its attainment for other models remains an open question. In this paper, we first achieve LMC for soft tree ensembles, which are tree-based differen- tiable models extensively used in practice. We show the necessity of incorporating two invariances: subtree flip invariance and splitting order invariance, which do not exist neural networks but are inherent to tree architectures, addition to permutation invariance of trees. Moreover, to exclude such additional invariances while keeping LMC by designing decision list- bared tree architectures, where such invariances do not exist by definition. Our findings indicate the significance of accounting for ceritectuur-specife invariances in achieving LMC.
demonstrate that it is possible
INTRODUCTION
A non-trivial empirical characteristic of modern machine learning models trained using gradient methods that models trained from different random initializations could achieve nearly identical performance, even though their parameter representations differ. This empirical phenomenon can be understood the outcomes all training sessions converge the same local minima. However, considering the complex non-convex nature of the loss surface, the optimization results are unlikely to converge to the same local minima. In recent years, particularly within the context of neural networks, the transformation of model parameters while preserving functional equivalence has been explored by considering the permutation invariance of neurons in each hidden layer (Hecht-Niclsen 1990; Chen al., 1993). Notably, only slight performance degradation has been observed when using weights derived through linear interpolation between permuted parameters obtained from different training processes (Entezari al. 2022 Ainsworth al.) 2023 This demonstrates that the trained models reside in different, yet equivalent, local minima. This situation is referred to as Linear Mode Connectivity (LMC) (Frankle et al. 2020). From theoretical perspective, LMC is crucial for understanding the stable and successful application of non-convex optimization. As noted by Entezari al. (2022) and Ainsworth al.) (2023). achievement of LMC suggests that loss landscapes often contain (nearly) a single basin after accounting for all possible invariances, which can be an intuitive reason for the robustness of gradient methods to different random initialization and data batch orders. In addition, LMC also holds significant practical importance, enabling techniques such model merging (Wortsman et al. 2022 Ortiz-Jimenez et al. 2023) by weight-space parameter averaging.
Although neural networks have been studied most extensively studied among the models trained using gradient methods, other models also thrive in real-world applications. A representative decision tree ensemble models, such as random forests (Breiman 2001). A decision tree ensemble makes predictions by combining the outputs of multiple trees that recursively split the data into subsets at each node and make final predictions at their leaves. While they are originally trained by greedy

---

Published as a conference paper at ICLR 2025
algorithms, not by gradient algorithms, their differentiable variant - called soft tree ensembles, which learn parameters of the entire model through gradient- based optimization - have recently been actively studied. Not only empirical studies regarding accuracy and interpretability (Popov et al. 2020 Hazimeh et al. 2020] Chang et al. 2022), but also theoretical analyses have been performed (Kanoh & Sugiyama 2022] 2023). Moreover, the differentiability of soft trees allows for integration with various deep learning methodologies, including fine-tuning (Ke et al.) 2011)). dropout (Srivastava et al. 2014), and various stochastic gradient descent methods (Kingma & Ba 2015; Foret et al.] (021). Furthermore, the soft tree represents the most elementary form of hierarchical mixture of experts (Jordan Jacobs 1993). Investigating soft tree models not only
advances our understanding of this particular structure but also contributes to broader research on the key components that are essential to developing large-scale models (Jiang et al. 2024).
A research question that we tackle in this paper is: "Can LMC be achieved for soft tree ensem- bles?". While achieving LMC has advanced the understanding of non-convex optimization and the use of model merging in neural networks, it has yet to be explored in tree ensemble mod- els. The reasons behind achieving LMC, even in neural networks, are not fully understood, and it also unclear whether LMC can be realized in soft tree ensembles, given their distinct architec- tures. Thus, our contribution of examining LMC in soft tree ensembles provides not only novel insights and techniques for tree ensemble mod- els but also broadens the understanding of the LMC phenomenon by introducing perspectives beyond neural networks for the first time.
Full dataser
Targei
Oatx
Split dataset
Ouly Pemndaaia
Origin
Interpottion
+
Naire
Tree Pormutation
Ous
Figure I: A representative experimental result on the MiniBooNE (Roe) 2010) dataset (left) and con- ceptual diagram of LMC for tree ensembles (right).
Our results, which are highlighted with a green line in the top left panel of Figure clearly show that the answer to research question is "Yes". This plot shows the variation in test accuracy when interpolating weights of soft oblivious trees, perfect binary soft trees with shared parameters at each depth, trained from different random initializations. The green line is obtained by the method introduced in this paper, where there is almost zero performance degradation. Furthermore, as shown in the bottom left panel of Figure T the performance can even improve when interpolating between models trained on split datasets.
The key insight is that, when performing interpolation between two model parameters, considering only tree permutation invariance, which corresponds to the permutation invariance of neural networks, not sufficient achieve LMC, as shown in the orange lines in the plots. An intuitive understanding of this situation is also illustrated in the right panel of Figure [] To achieve LMC, that is, the green lines, we show that two additional invariances beyond tree permutation, subtree flip invariance and splitting order invariance, which inherently exist for tree architectures, should be accounted for.
Moreover, we demonstrate that it possible to exclude such additional invariances while preserving LMC by modifying tree architectures. We realize such an architecture based on decision list, binary tree structure where branches extend in only one direction. By designating one of the terminal leaves empty node, we introduce customized decision list that omits both subtree flip invariance and splitting order invariance, and empirically show that this can achieve LMC by considering only tree permutation invariance. Since incorporating additional invariances is computationally expensive, we can efficiently perform model merging on our customized decision lists.
Our contributions are summarized follows:
First achievement of LMC for tree ensembles with additional invariances beyond tree permutation.
Development of decision bist- architecture that does not involve additional invariances.
A thorough empirical investigation of LMC across various tree architectures and real-world datasets.
PRELIMINARY
We prepare the basic concepts of LMC and soft tree ensembles.
2

---

Published as a conference paper at ICLR 2025
2.1 LINEAR MODE CONNECTIVITY
Let us consider two models, A and B, which have the same architecture. In the context of evaluating LMC, the concept of a "barrier" is frequently used (Ainsworth et al. 2023 Guerrero Peña al. 2023). Let A and Ø be the parameters of models A and B. respectively. Their shapes can be defined arbitrarily. In this paper, for tree ensemble models, A, O B E R 1 for the number P of parameters per tree and the number M of trees. Assume that C : 1 x - IR measures the performance of the model, such as accuracy. higher values of C()) mean better performance, the barrier between two parameter vectors A and OB is defined as:
1 BB) = sup (AC(@A) + (1 - A)C(OB) C(A + (1 - 1)OB)] XE
(1)
We can simply reverse the subtraction order if lower values of C(-) mean better performance like loss.
Several techniques have been developed to reduce barriers by transforming parameters while pre- serving functional equivalence. Two main approaches are activation matching (AM) and weight matching ( (WM). AM takes the behavior of model inference into account, while WM simply com- pares two models using their parameters. The validity of both AM and WM has been theoretically supported by Zhou et al. (2023). Numerous algorithms are available for implementing AM and WM. For instance. Ainsworth et al. (2023) used formulation based the Linear Assignment Problem (LAP), also known as finding the minimum-coss matching in bipartite graphs, to determine suitable permutations. Guerrero Peña et al. (2023) employed differentiable formulation that allows for the optimization of permutations using gradient-based methods.
Existing research has focused exclusively neural networks such multi-layer perceptrons (MIP) and convolutional neural networks (CNN). No studies have been conducted for soft tree ensembles.
2.2 SOFT TREE ENSEMBLE
Unlike typical hard decision trees, which explicitly determine the data flow the right left each splitting node, soft trees represent the proportion of data flowing to the right or left as continuous values between and This approach enables a differentiable formulation. We use a sigmoid
function, R - (0, 1) to formulate a function & Wm, bm) : IR. x R PxN x R Ix + (0, 1)
that represents the proportion of the ith data point æ; flowing to the éth leaf of the mth tree as a result of soft splittings:
N
E Wns bm) = II oo m.n 2i + m,, 1e/n (1 (w m. T; + bm, ))
Tare
(2)
flow to the
to the right
where N denotes the number of splitting nodes in each tree. The parameters Wm,n IR and 6m. E I correspond to the feature selection mask and splitting threshold value for woth node in a mtth tree, respectively. The expression 16/"" (resp. N,) is an indicator function that returns 1 if the fth leaf is positioned to the left (resp. right) of a node n, and 0 otherwise.
If parameters are shared across all splitting nodes at the same depth, such perfect binary trees called oblivious frees. Mathematically, Wm.n = Wm.n' and bnn. = by,, for any nodes n and n' at the same depth in oblivious tree. Oblivious trees can significantly reduce the numher of parameters from an exponential to a linear order of the tree depth, and they are actively used in practice (Popoy al. 2020 Chang et al. 2022).
Input R
To classify C categories, the output of the with tree is computed by the function fm : IR" x FFN R. IxN x RCC_ + C as sum of the leaves Tm. weighted by the outputs of pm,, Wess bm)):
Inner Node Mas but e.3
Leaf Kac g
Leaf' Mas
[x Wmss Dmy T Rm)
Σ (a Wmss bm T
(3)
Output
where is the number of leaves in a tree. To facilitate understanding, the formulation for tree depth is D = is illustrated in Figure]
Figure 2: A soft decision tree with a single inner node and two leaf nodes.
3

---

Published as a conference paper at ICLR 2025
Inoquality Sign Flip
Reordering
Subtrce Flip
Leaf Swap
permutation invariance
(b) flip
(c) Splitting under invariance
Figure Invariances inherent to tree ensembles.
(mn,e(Z;, Wm bm) takes the value of 1.0 for one leaf and 0.0 for the others, the leaf value itself becomes the prediction output, making the model behavior equivalent to that of standard oblique decision tree (Murthy et al. 1994).
By combining this function for M trees, we realize the function ʃ R RAXXXN x MXIXX x RMMxX XCXX + I2C as an ensemble model consisting of M trees:
M
f( w. b)
Σ
(ai, Wm, bm, Tm))
(4)
with the trainable parameters w (Wi,..,, wM) (b).... bm), and π = (711....) TM) being
randomly initialized.
As shown Equation tree ensembles exhibit permutation invariance when the order of the M trees is rearranged, which is similar to the permutation invariance observed in the hidden neurons of neural networks. However, as discussed in the next section, tree ensembles exhibit several other types of invariance beyond permutation, setting their behavior apart from that of neural networks. In addition to these invariances, there are several key differences between tree ensembles and neural networks. Due the hierarchical binary tree structure, the influence of each node parameter on the overall model depends on its node position. Moreover, unlike neural networks, tree ensembles lack the concept of activation and intermediate layers. These factors make it challenging to directly apply the matching strategies used for neural networks to achieve LMC.
3 INVARIANCES INHERENT TO TREE ENSEMBLES
In this section, discuss additional invariances inherent trees (Section 3.1 and introduce matching strategy specifically for tree ensembles (Section[3.2 We also show that the presence of additional invariances varies depending on the tree structure, and present tree structures where no additional invariances beyond tree permutation exist (Section 3.3
3.1 PARAMETER MODIFICATION PROCESSES
When we consider perfect binary trees, there are three types of invariance:
Tree permutation invariance. In Equation 4 the behavior of the function does not change if the order of the M trees altered, as shown in Figure This corresponds to the permutation of hidden neurons in neural networks, which has been subject previous studies on LMC.
Subtree flip invariance. When the left and right subtrees are swapped simultaneously with the inversion of the inequality sign at the split, the functional behavior remains unchanged, which we refer to subtree flip invariance. Figure presents a schematic diagram this invariance, which is not found in neural networks but is unique binary tree-based models. Since o--)) = (c) for E IR due to the symmetry sigmoid, the inversion of the inequality is achieved by inverting the signs of Wm,n and bm. Yadav et al. (2023) also focused the sign of weights, but in different way from ours. They paid attention to the amount of change from the parameters at the start of fine-tund finetunnig, rather than discussing the sign of the parameters.
4

---

Published as a conference paper at ICLR 2025
Splitting order invariance. Oblivious trees share parameters at the same depth, which means that the decision boundaries are straight lines without any bends. With this characteristic, even the splitting rules at different depths swapped, functional equivalence can be achieved if the positions of leaves are also swapped appropriately as shown in Figure 3). This invariance does not exist for non-oblivious perfect binary trees without parameter sharing, the behavior of the decision boundary varies depending on the splitting order.
Note that MLPs also have additional invariance beyond just permutation. Particularly in MLPs that employ ReLU as an activation function, the output of each layer changes linearly with a zero crossover. Therefore, it is possible to modify parameters without changing functional behavior by multiplying the weights in one layer by a constant and dividing the weights in the previous layer by the same constant. However, since the soft tree is based the sigmoid function, this invariance does not apply. Previous studies (Entezari et al. [022] Ainsworth et al. 2023) Guerrero Peña et al., 2023) have consistently achieved significant reductions barriers without accounting for this scale invariance. This could be because changes in parameter scale are unlikely due to the nature of optimization via gradient descent. Conversely, when we consider additional invariances inherent to trees, the scale is equivalent to the original parameters.
3.2 MATCHING STRATEGY
When considering subtree flip invariance and splitting order invariance, it is necessary to compare multiple functionally equivalent trees and select the most suitable one for achieving LMC. Although comparing tree parameters is straightforward approach, since the contribution of all the parameters in a tree is not equal, we apply appropriate weighting for each node, By interpreting tree as rule set with shared pa- rameters as shown in Figure we determine the weight of each splitting node by counting the number of leaves to which the node affects. For example, in the case of the example in the left-hand side of Figure 4 the root node affects eight leaves, nodes at depth 2 affect four leaves, and nodes at depth 3 affect two leaves. This strategy can apply to even trees other than perfect binary trees. For example, in the right example of Figure 4 the root node affects four leaves, a node at depth 2 affects three leaves, and node at depth 3 affects two leaves.
Parancar Skaingg
Purasata Starity
Figure 4: Weighting strategy.
Using the weighting operation described above, we present the straightforward matching procedure in Algorithms] I and [ We performed an exhaustive search explore all patterns with subtree flip invariance and splitting order invariance, while handling tree permutation invariance with the LAP. We treat the output of each individual tree like the activation value of a neural network in the case of AM. Note that although it is necessary to solve the LAP multiple times for each layer in MLPs to perform coordinate descent (Ainsworth et al. 2023). tree ensembles require only a single run of the LAP since there is no concept of intermediate layers.
Notations used Algorithms M 2
Multidimensional array elements are accessed using square brackets [-]. For example, for G E [xJ, G[i] refers to the ith slice along the first dimension, and G|:Aj] refers to the jth slice along the second dimension, with sizes RJ and TR.. respectively. Furthermore, it can also accept vector E N' as an input. In this case, G(v] E ( The FLATTEN function converts multidimensional input into a onnedimmnsional vector format. As the ANNARSUMASSIGNMEER
function, scipy. optimize. linear samear_sum___a stun_ssmu___ assignmen is used to solve the LAP. In the ADJUSTTREE function, the parameters of a tree are modified according to the uth pattern among the enumerated U N total additional invariances patterns. Additionally, in the WEIGHTING function, parameters are multiplied by the square root of their weights to simulate the process of assessing a rule set. If the first argument for the product, is larger than any previously input inner product values, then is updated with u, the second argument. not, u' remains unchanged.
function, the input inner
https::/docss scipy. wwwppy.oroo.. __r____ssssggnettttt...mmm
ze.
linear_suu _usu_assiii___ee gnment.....mmm html
5

---

Published as a conference paper at ICLR 2025
Algorithm I: Activation matching for soft tree ensembles
ACTVATTONMATCCINNIOAA E MRMP OB E ERMXP Drampled E R Nompki) Initialize A E IR RRM X and Og E RRMX MaMNea x to store outputs for m 1 to M do
for i = to Nampled do
Set the output of the with tree with O [m]] using seampled i to Oa [m, i). Set the output of the mtth tree with θg m using saampled 1, to Og (m, i
5
Initialize similarity matrix S IRMMM for m. = to M do for mB M do
L S(m.. mB] + FLATTEN(OA(mA)) FLATTEN(O mmm)))
p < LINEARSUMASSIINMEENTI
// p N Optimal assignments
12
A θ + WEIGHTING( B) Initialize operation indices E N for m to M do
13
for 1 to U do
// E N: Number of possible operations u' UPDATBBSSOOFFAATTAADDUUTTTEEEEER
|mmmm) u) [g[m]. u)
17
Append u' to
q E N Optimal operations
return p.q
Algorithm 2: Weight matching for soft tree ensembles
WEIGHTMATCHING(O.. E IR MP θ E RMXP)
A Og WEIGHTING( θ Initialize similarity matrix for each operation S E X for to U do
U/ E N: Number of possible operations
5
for mn = to M do + (DJUSTTREE
0 E R.: Adjusted tree-wise parameters
for mB to M do
S Slu. m. mB] + Og[mg]
S' max (S, axis=0) p LINEARSUMASSIGNENNTSS)
S' E MxM; Similarity matrix between trees 11 NM, Optimal assignments
< argmax(S, (S, (p) return p.q
11 q NM, Optimal operations
Complexity. The time complexity of solving the LAP is ((M)) using modified Jonker- Volgenant algorithm without initialization (Crouse) 2016), where M is the number trees. This process needs to be performed only once in both WM and AM consider tree permutation invariance. However, the number additional invariance patterns U scales rapidly as increases. In non-oblivious perfect binary tree with depth D, there are 2 splitting nodes, resulting in 22- possible combinations of sign flips, giving total additional invariances pattern U 22 Additionally, in the case of oblivious trees with depth D, the number of splitting rules that consider sign flipping is reduced from 22 -1 to 2D due to the splitting rule sharing the same depth. Considering the D! distinct splitting order invariance patterns, we have U 2 D!. Therefore, for large values of D, becomes impractical to conduct exhaustive search consider additional invariances.
In Section 3.3
we will discuss methods to eliminate additional invariance by adjusting the tree structure. This enables efficient matching even for deep models. Additionally, in Section 4.2] will present numerical experiment results and discuss that the practical motivation to apply these algorithms is limited when targeting deep perfect binary trees.

---

Published as a conference paper at ICLR 2025
3.3 ARCHITECTURE-DEPENTEE
OF THE INVARIANCES
In Section 3.1 we focused on perfect binary trees as they are most commonly used in soft trees (Frosst & Hinton 2017 Popoy et al. 22200; Hazimeh et al.] (020). However, tree architec- tures can be flexible, and we show that we can specifically design architecture that has neither subtree flip nor splitting order invariances. This allows efficient matching as it is computation- ally expensive to consider two such invariances.
Invuriance exists
Empty Nade
Figure 5: Tree architecture where neither subtree flip invariance nor splitting order invariance exists.
Our idea is to modify a decision list shown on the left side of F which is tree structure where branches extend in only one direction. Due to this asymmetric structure, the number of parameters does not increase exponentially with the depth, and the splitting order invariance does not exist. Moreover, subtree flip invariance also does exist for any internal nodes except for the terminal splitting node, as shown in the left side of Figure(3] To completely remove this invariance, we virtually eliminate one of the terminal
Table I: Invariances inherent each model archi- tecture.
Perm
Flip
Order
Non-Oblivious Tree Oblivious Tree Decision List
( X
X
Decision List (Modified)
leaves by leaving the node empty, that is, a fixed prediction value of zero, as shown on the right side of Figure [ Therefore only permutation invariance exists for our proposed architecture. We summarize invariances inherent to each model architecture in Table
4 EXPERIMENT
We empirically evaluate barriers in soft tree ensembles to examine LMC.
4.1 SETUP
(Grinsztajn et al. 2022). collection of tabular datasets suitable for evaluating tree ensembles. Details of datasets are provided in Section A in Appendix. As proposed in Grinsztajn et al. (202)), we randomly sampled 10, 000 instances for train and test data from each dataset. If the dataset contains fewer than 20, 000 instances, they are randomly divided into halves for train and test data. We applied quantile transformation to each feature and standardized
Datasets. In our experiments, we employed
follow normal distribution.
Hyperparameters. We used three different learning rates v E (0.01, 0.001, 0.0001) and adopted the one that yields the highest training accuracy for each dataset. The batch size is set at 512. is known that the optimal settings for the learning rate and batch size are interdependent (Smith et al. 2018). Therefore, it is reasonable to fix the batch size while adjusting the learning rate. During AM, we set the amount of data used for random sampling to be the same the batch size, thus using 512 samples to measure the similarity of the tree outputs. As the number of trees M and their depths D vary for each experiment, these details will be specified in the experimental results section. During training, we minimized cross-entropy using Adam (Kingma & Ba 2015) with its default typerparameter&& Training is conducted for 50 epochs. To measure the barrier using Equation | experiments were conducted by interpolating between two models with À E {0, 1/24, 23/24, 1T. which has the same granularity in Ainsworth al. (202).
Randomness. We conducted experiments with five different random seed pairs: E {1, 5, 9. and FB (2, 4, 6, 8, 10). As a result, the initial parameters and the contents of the data batches during training are different in each training. In contrast to spawning (Frankle et al.) 2020) that branches off from the exact same model partway through, we used more challenging practical conditions. The parameters w, b, and π were randomly initialized using uniform distribution, identical to the procedure for a fully connected layer in the MLF
htt.s////wcccoooo//////aaa//aaee www...atttt...mmmmmmmmmmmmmmmmmm Adam htm html

---

Published as a conference paper at ICLR 2025
(M-26/TTak
44-25% (Tom
X0.4
Fandl
D-1
AM
Figure Barriers averaged across 16 datasets with respect to considered invariances for non- oblivious (top row) and oblivious (bottom row) trees. The error bars show the standard deviations of 5 executions.
espooas
Higgs
MogicTelssospe
bank-markecting
covertype
55
Interelarior
Intepelaton
Intepolatton
Intepelanoe
esedit
electrielly
eye movemeass
heloe
house 16H
jannis
pol
70
20
10
60
Intepllai
Intrpolatonn
Incrpibtionn
Intepedation
Ineepolation
Inorpolaionn
Intoppiotion
Intepelation
Nave
Thoe Permatation
Figure 7: Interpolation curves of test accuracy for oblivious trees 16 datasets from Tabular- Benchmark (Grinsztajn et al. 2022). Two model pairs are trained on the same dataset. The error bars show the standard deviations of executions.
conducted system equipped with Intel Xeon E5-2698 CPU at 2.20 GHz, 252 GB of memory, and Tesla V100-DGXS-330 32GB GPU, running Ubuntu Linux (version 4.15.0- 17--geeric.. The reproducible PyTTorch (Paszke al., 2019) implementation is provided in the supplementary material.
Resources. All experiments
4.2 RESULTS FOR PERFECT BINARY TREES
F shows how the barrier between two perfect binary tree model pairs changes in each operation. The vertical axis each plot in Figure shows the averaged barrier over datasets for each considered invariance. The results for both the oblivious and non-oblivious trees plotted separately in vertical layout. The panels on the left display the results when the depth D of the tree varies, keeping M 256 constant. The panels the right show the results when the number of trees M varies, with D fixed at 2. For both oblivious and non-oblivious trees, we observed that the barrier decreases significantly as the considered invariances increase. Focusing on the test data results, after accounting for various invariances, the barrier is nearly zero, indicating that LMC has been achieved. In particular, the difference between the case of only permutation and the case where additional invariances are considered tends to be larger in the case of A.M. This is because parameter values are not used during the rearrangement of the tree in AM. Additionally, it has been observed that the barrier increases as trees become deeper and that the barrier decreases the number of trees increases. These behaviors correspond to the changes observed in neural networks when the depth varies or when the width of hidden layers increases (Entezari et al., 2022 Ainsworth et al. 2023). Figure shows interpolation curves for AM in oblivious trees with D and M 256. In our figures and tables, "Naive" refers straightforward parameter interpolation without any specific optimization; "Tree Permutation"
8

---

Published as a conference paper at ICLR 2025
Biocesponic
MagicTolessppe
MiniBooNE
califonni
covertpe
crediti
Sullleofeeelllecceeellettt electricily
eye movernets
heloc
16H
jannic
$7.5
$5
TO
Nave
Troe Permutation
+
Ouee
Figure 8: Interpolation curves of test accuracy for oblivious trees on 16 datasets from Tabular- Benchmark (Grinsztajn et al., 2022). Two model pairs are trained on split datasets with different class ratios. The error bars show the standard deviations of 5 executions. Performance of a model trained with the full dataset shown in the red dashed horizontal lines as a reference.
or "Perm" considers only the permutation invariance; and "Ours" incorporates both the permutation of the trees and tree-inherent invariances. Other details, such as performance for each dataset, are Appendix.
provided in Section
Furthermore, we conducted experiments with split data following the protocol in Ainsworth et al. (2023) and Jordan et al. (2023), where the initial split consists of randomly sampled 80% negative and 20% positive instances, and the second split inverts these ratios. There is overlap between the two split datasets. We trained two model pairs using these separately split datasets and observed an improvement performance by interpolating their parameters. Figure 8 iillusrates the interpolation curves under AM in oblivious trees with parameters D and M 256. Through model merging, it demonstrates similar performance full data training even with split data training for the majority of datasets. Note that the data split is configured to remain consistent even when the training random seeds differ. Detailed results for each dataset using WM AM are provided in Section B in Appendix.
Table compares the average test barriers of an MLP with ReLU activation function, whose width is equal to the number of trees, M 256. The procedure for MLPs follows that described in Section 4..1 The permutation for MLPs optimized using the method described in Ainsworth et al. (2023). Since Ainsworth et al. (2023) indicated that WM outperforms A.M in neural networks, WM was used for the com- parison. Overall, tree models exhibit smaller barriers compared to MLPs while maintaining similar accuracy levels. is important to note that MLPs with D tend to have more param- eters at the same depth compared to trees, lead- ing to more complex optimization landscapes. Nevertheless, the barrier for the non-oblivious tree D is smaller than that for the MLP at D = 2, even with more parameters. Further- more, at the same depth of D 1, tree models have smaller barrier. Here, the model size is evaluated using = 44, the average input feature size of datasets used the experiments.
Table 2: Barriers, accuracies, and model sizes for MLP, non-oblivious trees, and oblivious trees.
Depth
Accuracy
Size
Naive
Perm
8,755 0.877 0.691 a 2.002 76.296
0.094 12034
75.981
15.915 = 2.479
3,40 2 75,935 = 0.117
143618
Non-Oblivious Tree
Depth
Barrier
Accuracy
Size
Naive
Perm
Ours
8.905 = 0.963 0,449 e 0.235
E.18) a 0.078
76.464 a 0.167
12544
0.464
0,811 0.333
0,455 0.108
0.052
36608
0.926
Oblivious Tree
Depth
Barrier
Accuracy
Size
Naive
Perm
Ours
R 365 = 0.963 D.449 + 0.35 0.181 + 0078 76.464 + 0.167 12544
7.881 = 0.86
0.918 e 0.02 0.348
172
76,623 (104 25088
1,283
38656
In Section 3.2 we have shown that considering additional invariances for deep perfect binary trees computationally challenging, which may suggest developing heuristic algorithms for deep trees. However, we consider this to be low priority, supported by our observations that the barrier tends to increase as trees deepen even if we consider invariances. This trend indicates that deep models are fundamentally less important for model merging considerations. Furthermore, deep perfect binary trees are rarely used in practical scenarios. Kanoh & Sugiyamal (2022) demonstrated that generalization performance degrades with increasing depth in perfect binary trees due to the

---

Published as a conference paper at ICLR 2025
Table Barriers averaged for 16 datasets under WM with 2 and M 256.
Architecture
Barrier
Barrier
Accuracy
Accurncy
Naive
Perm
Ours
Naive
Perm
Oues
Non-Oblivious Tree
13,079 a 0:755
4,207 a 0.332 3.303 0.104
RS 0,800 6801 0.464
0.511 +0333
0.455 0.105
76.431
0.052 76.623
Oblivious Tree
14,580
48344
2.74
7,881
0.866
0919
0.348
Decision List
13,835 2 0.788
3.687 4: 0.230
85.337 & 1..134
7,513 0.964
0446 00120
76.629 2 0.119
Decision List (Moditied)
12,922 à 1.131
3,328 a 0.204
85.563 + 0,141 6,734 1.0%
0.468 0.150
76.773 0.051
Table 4: Barriers averaged for 16 datasets under AM with D and M 256.
Test
Architecture
Barrier
Barrier
Accuracy
Accuracy
Naive
Perm
Ours
Naive
Perm
Ours
Non-ONliviou Tree
13,079 a 0,755
14,963 a 1,500
4 4,500 a 0,527
646
0,090 6.801
0,464
8631 e: 1,444
0.943 e 0:435
76.61 : 0.052 0.305
Oblivious
10
0,509
3.557
808
10.349
0.476
76.623 0.042
Decision 13,835 0.788
12.785
1,924
0.134
7.513
0.944
1880
0.119
Decision List (Modified)
12,922 + 1.131
6. 36364 0.194
85 563 e 0.141
6.734 1.096
1.1 0.243
76.773 e 0.051
degeneracy of the Neural Tangent Kernel (NTK) (Jacot et al. 2018 This evidence further supports
the preference for shallow perfect binary trees, and increasing the number of trees can enhance the expressive power while reducing barriers.
4.3 RESULTS FOR DECISION LISTS
WM
AM
We present empirical results of the original de- cision lists and our modified decision lists, as shown in Figure 5 As we have shown in Table they have fewer invariances.
Accusty Busier
10.3
550
16-
Figure 9 illustrates barriers as a function of depth, considering only permutation invariance, with M fixed at 256. In this experiment, we have excluded non-oblivious trees from compar- ison as the number of their parameters exponen- tially increases trees deepen, making them infeasible computation. Our proposed modified decision lists reduce the barrier more effectively than both oblivious trees and the original deci- sion lists. However, the barriers of the modified decision lists are still larger than those obtained by considering additional invariances with perfect binary trees. Tables 3 and 4 show the averaged barriers for 16 datasets, with D 2 and M 256. Although the barriers of modified decision lists are small when considering only permutations (Perm), perfect binary trees such as oblivious trees with additional invariances (Ours) exhibit smaller barriers, which supports the validity using oblivious trees as in [Popov et al. (2020) and [nann et al. 2.22). To summarize, when considering the practical use of model merging, if the goal is to prioritize efficient computation, we recommend using our proposed decision list. Conversely, if the goal is to prioritize barriers, it would be preferable to use perfect binary trees, which have a greater number of invariances that maintain the functional behavior.
0a.
Oidiviozz
Decason
Dacuson Lar (Moditeed)
Figure 9: Averaged barrier for 16 datasets as a function of tree depth. The error bars show the standard deviations of 5 executions. The solid line represents the barrier in train accuracy, while the dashed line represents the barrier in test accuracy.
5 CONCLUSION
We have presented the first investigation of LMC for soft tree ensembles. We have identified additional invariances inherent in tree architectures and empirically demonstrated the importance of considering these factors. Achieving LMC is crucial not only for understanding the behavior of non-convex optimization from learning theory perspective but also for implementing practical techniques such as model merging. By arithmetically combining parameters of differently trained models, wide range of applications have been explored, such as federated leanning (McMahan et al. 2017) and continual learning (Mirzadeh al. (021). Our research extends these techniques soft tree ensembles. Future work will explore empirical investigations, including the perspective of general mode connectivity (Garipov al. 2018).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was supported by JSPS, KAKENHI Grant Number HO3500 Japan and JST, CREST Grant Number JPMJCR22D3, Japan.
ETHICS STATEMENT
This study provides a fundamental analysis of ensemble learning, and we believe that our discussion will not result in detrimental uses.
REPRODUCIBILITY STATEMENT
Source codes are available in the supplementary material reproduce the numerical experiments and visualizations.
REFERENCES
Samuel Ainsworth, Jonathan Hayase, and Siddhartha Srinivasa. Git Re-Basin: Merging Models modulo Permutation Symmetries. In International Conference on Learning Representations, 2023.
Leo Breiman. Random Forests. In Machine Learning, 2001.
Chun-Hao Chang, Rich Caruana, and Anna Goldenberg. NODE-GAM: Neural generalized additive model for interpretable deep learning. In International Conference on Learning Representations, 2022.
An Mei Chen, Haw-minn Lu, and Robert Hecht-Nielsen. On the Geometry of Feedforward Neural Network Error Surfaces. Neural Computation, 1993.
David Crouse. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 2016.
Rahim Entezari, Hanie Sedghi, Olga Saukh, and Behnam Neyshabur. The Role of Permutation Invariance Linear Mode Connectivity of Neural Networks. In International Conference on Learning Representations, 2022.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware Minimization for Efficiently Improving Generalization. In International Conference on Learning Representations, 2021.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear Mode Con- nectivity and the Lottery Ticket Hypothesis. Proceedings of the 37th International Conference on Machine Learning. 2020.
Nicholas Frosst and Geoffrey E. Hinton. Distilling Neural Network Into Soft Decision Tree. CoRR, 2017.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs. In Advances in Neural Information Processing Systems, 2018.
Leo Grinsztajn, Edouard Oyallon, and Gael Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
Fidel A. Guerrero Peña, Heitor Rapela Medeiros. Thomas Dubail, Masih Aminbeidokhti, Eric Granger, and Marco Pedersoli. Re-basin via implicit Sinkhorn differentiation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The Tree Ensemble Layer: Differentiability meets Conditional Computation. In Proceedings of the 37th International Conference Machine Learning, 2020.

---

Published as a conference paper at ICLR 2025
Robert Hecht-Nielsen. On the algebraic structure of feedforward network weight spaces. In Advanced Neural Computers. 1990.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernll: Convergence and Generalization Neural Networks. Advances in Neural Information Processing Systems, 2018.
Albert Q. Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, Gianna Lengyel. Guillaume Bour, Guillaume Lample, Lélio Renard Lavaud, Lucile Saulnier, Marie- Anne Lachaux, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Théophile Gervet, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mixtral of experts, 2024.
Keller Jordan, Hanie Sedghi, Olga Saukh, Rahim Entezari, and Behnam Neyshabur. REPAIR:
REnormalizing permuted activations for interpolation repair. In International Conference Learning Representations, 2023.
M.I. Jordan and R.A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. In Proceedings of International Conference on Neural Networks, 1993.
Ryuichi Kanoh and Mahito Sugiyama. A Neural Tangent Kernel Perspective of Infinite Tree Ensembles. In International Conference on Learning Representations, 2022.
Ryuichi Kanoh and Mahito Sugiyama. Analyzing Tree Architectures in Ensembles via Neural Tangent Kernel. International Conference on Learning Representations, 2023.
Guolin Ke, Zhenhui Xu, Jia Zhang, Jiang Bian, and Tie- Yan Liu. DeepGBM: Deep Learning Framework Distilled by GBDT for Online Prediction Tasks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations, 2015.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--Eficee Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference Artificial Intelligence and Statistics, 2017.
Seyed Iman Mirzadeh, Mehrdad Farajtabar, Dilan Gorur, Razvan Pascanu, and Hassan Ghasemzadeh. Linear Mode Connectivity in Multitask and Continual Learning. In International Conference Learning Representations, 2021.
Sreerama K. Murthy, Simon Kasif, and Steven Salzberg, A system for induction of oblique decision trees. Journal of Artificial Intelligence Research, 1994.
Guillermo Ortiz-Jimenez, Alessandro Favero, and Pascal Frossard. Task Arithmetic the Tan- gent Space: Improved Editing of Pre-Trained Models. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep Learning Library. Advances in Neural Information Processing Systems, 2019.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data. In International Conference Learning Representations, 2020.
Byron Roe. MiniBooNE particle identification. UCI Machine Learning Repository, 2010.
Samuel L. Smith, Jieter-Jan Kindermans, and Quoc V. Le. Don't Decay the Learning Rate, Increase the Batch Size. In International Conference Learning Representations, 2018.
12

---

Published as a conference paper at ICLR 2025
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research, 2014.
Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo-Lopes Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, and Ludwig Schmidt. Model soups: averaging weights of multiple fine-tuned models improves aceuracy without increasing inference time. In Proceedings of the 39th International Conference on Machine Learning, 2022.
Prateek Yadav, Derek Tam, Leshem Choshen, Colin Raffel, and Mohit Bansal. TIES-merging: Resolving interference when merging models. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023.
Zhanpeng Zhou, Yongyi Yang, Xiaojiang Yang, Junchi Yan, and Wei Hu. Going Beyond Linear Mode Connectivity: The Layerwise Linear Feature Connectivity. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
13

---

Published as a conference paper at ICLR 2025
A DATASET
Details of datasets used in experiments are provided Table
Table 5: Summary of the datasets used in the experiments.
Dataset
N
F
Link
Bioresponse
3434
419
https://www.on http:://ww.geemmocoz///////////
DiaUetes130US
71090
7
Higgs
940160
24
wwwp
MagicTTelescope
13376
10
Httpst//www.opemml..om
MiniBooNE
72998
50
https: www. openm.p.em... wttpppmmm.m.///1122222223
bank-marketing
10578
7
www. HELps::/www.openm.. http://wwww.oeee.l.....././/./.
california
20634
8
https: htsps://www.opp www. https://www.oopml.ooo//////////
covertype
566602
10
https: http://wwwwoeemm..o3////////////
credit
16714
10
https: wwwp https//www..eemml.oo///////////1
13272
20
https: http://ww.wpp..mm /ttp:://ww.cooem..oo23///////4/
electricity
38474
7
htLp://www.opemmcccc3////1111111
_e__moeements
7608
20
https: /ww:///www... openm wttp:/ppmmmoo.///111111133
heloc
10000
22
house_166 16H
13488
16
https: www www.:/oop.m..rrg/.ee.
jannis
57580
54
http://www.ppmmm.czzp/ooo h
/twp://wwwww. /ttps://ww..opa
pol
10082
26
https: www. http://www.emmmmo//////0/00/
B ADDITIONAL EMPIRICAL RESULTS
Tables 6 and present the barrier for each dataset with D = 2 and M = 256. By incorporating additional invariances, it has been possible to consistently reduce the barriers.
Tables 00 and I1 detail the characteristics of the barriers in the decision lists for each dataset with D and M 256. The barriers
modified decision lists tend be smaller.
Tables 12 and 13 show the barrier for each model when only considering permutations with D = 2 and M = 256. It is evident that focusing solely on permutations leads to smaller barriers in the modified decision lists compared to other architectures.
Figures 10
16 and 17 show the interpolation curves of oblivious trees with and M 256 across various datasets and configurations. Significant improvements are particularly noticeable in AM, but improvements are also observed in WM. These characteristics are also apparent in the non-oblivious trees, shown in Figures T8 training, the dataset for each of the two classes is initially complete (100%).
24 and 25 Regarding split data then divided into splits of 80% and 20%. and 20% and 80%, respectively, Each model trained using these splits. 16 22 and 24 show the training accuracy evaluated using the full dataset (100% for each class). In split data training, the performance reference of full data training is shown only for the performance on the test data. This is because, in split data training, even the training dataset used for evaluation includes portions that are not used for training each model, which differs from the conditions in full data training. In contrast, when evaluating performance on the test data, all of the test data have not been used equally for the training each model, which allows for fair
19
20
21
22
Figures 14
comparison between the two approaches. Figures 26 27 28
29
30 31
33 34 35
36 37 38
39 40 and 41 visualize the same to that perfect binary trees for the decision lists.
Figures 42 and 43 show the interpolation curves for MNIST (LeCun & Cortes 2010 with various tree architectures where D and M = 256. Although MNIST consists of dimensional image data, it is input 1-dimensional vector.
14

---

Published as a conference paper at ICLR 2025
Table 6: Accuracy barrier for non-oblivious trees with WM.
Train
Dutaset
Naive
Perm
Ferm&&Fiip
Naive
Perua
Perm&&Fiip
Bicresponse
18,944 10
5,876
1.477
4.132 0.893
8:235 e 6,456
1,285 a 0.65
0.314 0:432
Diabses
2,148
1.159
0.9677 0.888
1.014
0,540
0.784
liggs
27,578 a. 1.742
18,470 a 0.769
14.722 1.419
4,055 1.089
0.662 1 0.550
0.292 0.421
MagicTelescoge
2,995 1.198
0 0.556
0.307 + D.540
2,056 = 1,025
0.361 a 0.6118
0.229 0,348
MiniBooNE
18.238 44.570
2.272 0.215
1.506 0:21
12,592 4,199
0.231 0..314
0.000 0.000
bank murketing
1.183
1.521
1.566
1.843 1.001
0.953
califoraaa
6.396 2: 2.472
0.875 0.551
0,520 + 0.527
5:226 =: 2.377
0.224
: 0.248
0.2066 1M16+0..133 0.131
covertype
16.823 a 14.159
L.839 0.336
0.914 0,.56
14,500 4.001
1,035 0.100
0.376 0.333
credit
7,317 2.77::2:44 2:425
3.172 2,636
2.615 0.K3]
5.861 2.064
2.202 3.103
1 0.588
default credit-car--cleeee card-clienss
14.318 4.509
5,419 1.318
3,273
4.200
0.937 1.026
0.243
electricity
10,050 2,9900
L.035 0.543
0.221 & 0.1.9
9,422 s 2.795
0.771 = 0.478
0.130 0.977
eye_ movement
18.743 =: 1.994
11,605 :: 1.927
7.866 + 1 301
1 = 0.467
0,463 0. 0.183
O. IND 2,206
heloe
1.611
1012 0:48]
0,530
0,475 0.447
0.922 0.338
house_ [oll
4.230
0.219
0.4N
jeanis
17.756 + 3.322
10,442 1.404
00221
3.205 2,849
0.025 + 0.004
0L007 + 0:0116
pol
20,542 2:887
4.612 0.912
2225 1,000
15,300 2,562
1,708 a 0.399
1012 0.859
Table 7: Accuracy barrier for non-oblivious trees with AM.
Train
Dutaset
Naive
Perma
Perm& Fllp
Naive
Perna
Perm& Flli
Hicresponse
18.944 : 10.076
14,066
7.045
5,710 0.915
8,235 = 6.456
5,057 + 3.141
0.966 0,316
Diubeees
2.148 0.601
3,086 2,566
1.014
1,936 2.878
0.105 : 0.152
Hgggs
27,578 1.742
30,704 1 2.899
18.435 4 1.599
4,055 2 1.089
7,272 : 1.089
1. 1014 1 0,483
MagicT:lescog
2.995 = 1.198
3,309 1 1.486
0.778 4 0.315
2,096 =: 1.055
2,693 # 1,190
0.428 + 0.327
MiniBooNE
18,238 4.570
34,934 8.157
23332 + 0.3383
12.592 44119
28.721 7,368
0.014 a 0.081
murtoning
13,990 14.110
7,638
0.539
13.590 4.566
12,810
2.643 0.70M
califorzia
6,396 : 2.472
5,800 + 2.036
0.097 + +.,335
5:236 2 2.377
4,858 + 2.017
0.261 + 0,285
Dovettype
16,823
19,708 6.392
1420 0.619
14,500 4.015
17.765 2 6.000
0.758 a 0,540
credit
2.425
10,356
3.640 1.624
5,861 2.064
9,378
+ 1,987
credit clients
14,318 4.2509
14,106 2.297
1.247 1.678
6,227 4.205
2.514:22.0199
0.885 +
electricity
10,090 2.930
12,955 1 4,558
0.762 1 0,332
9,22 :: 2.795
12:26] à 4.555
0.459 a 0,200
eye movements
18,743 1.594
18.757 1,277
10 1.41
1,495 0.467
1,583 # 1.011
0L 146 + D. 107
heloc
4,434 11.61
6.564 2,404
1.714 00,672
0,830 0.727
2,179 2,100
0.385 0,370
bouse_ l6ll
8.935 2.501
10.184
0.8.6
2.461
a 0,693
janais
17.756 #: 5.322
19.004 1.246
9.390 + 1,036
3.205 = 2.849
4,047 1.415
0.346 + 0.445
pol
20.542 2:2873
16.267 3.914
7.567 4.2200
15,830 2.5562
12,863 3:983
1.539 2.727
Table 8: Accuracy barrier for oblivious trees with WM.
Test
Dataset
Naive
Perm
Perm& Oreder
Naive
Perm
Perm&& Oremm&&Od&&&FFl
Bioresponse
16.642 1 4.362
4.800
0,895
3,289 0,680
7,165 2.547
L.06 1,020
0.299 0,247
Diabries 13UUS
3.304
0.216 0.177
3.476
0.882 1.309
0.181
Higgs
28.640 0.914
19:754 1.023
13,699 0.814
4,648 0.966
1,270 a 0.808
0.266 & 0,
Magic Telessope
2.659 1 1.637
0.473 1 0.632
0.077 = 0.110
2,012 =: 1.343
0,534 1 0..66
0U053 + 1.1
MiniBooNE
22.364 7.001
2.388 0.195
1628 g 0.208
16.454 6.706
0,075 0.086
0.012 & 0,019
bank-markeeing
13.512 6.416
2.998
0.225 0.688
12,856 6.609
2.324 1.618
0.024
califfrnnia
8,281 4 4,253
03744 1 0.524
0.351 = 2.266
6.578 = 4,264
0.342 1 0.209
0.034 + 0,026
covertype
23,977 a 2.565
2.033 1 0.657
0.916 : 0.523
21,790 2.253
0.992 1 0.196
0.122 & 0.319
credit
6.912
2:369 0.887
1,622 0.6066
1.324 0.674
0.N22
default
credit clients
1 4,462
4.512
2,002 0.620
7.618
0,728 0.331
0,331 0.357
electricity
3.835 1.824
1.060 1: 1.684
0.279 : 0.266
7,952 = 1.995
0.731 a 0.383
0.285 & 0,200
eye movements
22,604 1.436
12.687 + 1.645
826 + M22
2.884 = 1.646
0,825 a 0.771
OLOBY & D. 2525
heloe
6,282
2.177 1.156
500 = 0.499
1,625 1.480
0,869 0.997
0.727 0,765
house_
13.600
3.302
e
8,055
0.330 0.441
0.158
janais
19,590 =: 1.003
11.358 + 0.577
1,440 e 0.538
1,999 1.237
0,305 : 0.409
0.214 0,255
pol
20.125 4 2.902
5,089 1: 1.482
2544 & 1.005
15,887 3.061
2,100 1.358
0,751 & 0,892
Table 9: Accuracy barrier for oblivious trees with AM.
Train
Dataset
Naive
Perm
Perm& Perm&&Order& Flip
Naive
Perm
Perm&& Ordme&Orde&&Flppp
Bioresponse
16.642 4,362
10.033&8.550
6,358 1.915
7,165 : 2.547
6.904 1 5,380
1.038 0.591
Diabetes1300 130US
3,170 3.304
2.831
5,290
1 0,29)
Higes
28.640 0.914
33.234 3.164
15,60% 213
4.648 0.566
8.113 2.614
0.415 + 0,454
Maçi MagxTellesoog Telescoge
2.659 + 1.637
3,902 & 1.931
0.224 = 0.556
2,012 1.343
3.687 1 1,576
0.334 + 0.454
MiniBooNE
22.346 à 7.001
41.022 3.398
2.184 =
16,45 6.706
34,152
3.161
0.033 1 0.056
bunk-markkting
13.512 6.416
12:248 6,748
1,500
12,856 6.009
11,356
7.168
0.055 +
california
8.281 4: 4,253
9.539 : 4.798
0.371 2 0.365
6.578 4,264
8,354 à 4.648
0.112 + 0.181
cuvertope
23,977 à 2.565
27 590 2.172
[05] 4 107
21,790 : 2.253
25.269 1 1.787
0.403 & 0.256
credit
6.912 4,003
9.839 6,698
1 0.839
5,739
8.291 7.268
0.549 + 0.75]
default-dd of credit clients
4,662
21.346
3,666
12.183
0,372
electricity
8.835 +: 1.834
18.177 5.979
1.472 = 0.502
7.952 1.995
17.396 + 800
0. 0.4 + 9.35
eye_movements
22.604 1.486
23:221 3.024
N. MLS8S + 248
2.884 1.646
2.761 4 1.828
0 0.29% + 0.455
haloe
6.38242..33
9.074 3.894
2.54] 0.177
1.625 1.490
3.891 2.655
0.185 1 0.397
house_
13,600 + 5.135
17.963 5.099
2,841
8,055
12,192
0,292 0.157
jannis
19.390 + 1.013
22.482 3.113
0.316
1,999 1,237
4,292 4 2,509
0.069 + 0.154
20.125 4 2,902
19.558 5.765
3,056 2 0.510
15.887
3.061
14,358 5.552
0.961 0.722
15

---

Published as a conference paper at ICLR 2025
Table 10: Accuracy barrier for decision lists with WM.
Train
Datasel
Naive
Porm
Nuive (Modifiel)
Perm (Modified)
Nuive
Porm
Naivo (Modified)
(Modified)
Rioresponse
21,323 6.563
4.259 + +0,698
14-578- 3,930
4.641 +0.118
9.325 3,088
0. 0.346 + 0.237
7.546 4.261
1.509 0,827
130Us
5.182 4 3.745
1 1 1000
2.754
1,098
1.088
1.0.08
4
1.293 2 1.332
1,476 a 108
0.849 : 0.885
Higgs
27.778 1.036
16 110 0.518
28.915 + 1.314
14.071
+ 0.395
+.777+0.900
0.106 e 0.203
5.136 0.946
0.039 + 0.081
Magic Telescope
4,855 + 3.388
0.355 + 0.682
5.138 2.655
0.182 0:144
4,157 3.763
0.250 + 0.519
4,534 + 2.588
0.157 + 0.162
MimBoNNE
23,059
1,91 0.1388
1,580 0.177
17,248
0,025 0:036
3.585
0:035 0.042
hank-marketing
11,953 3.794
0,979 0-478
11.580 2.167
0.373 0.448
11,387 4
0.536 + 0.472
10.540 2.067
0.
califoenia
6,522 a 3.195
0.621 0.366
8.425 3.273
0.538 1.
5.167 2,962
0.236 a 0.146
6,844 a 3:087
0.151 a 0.147
3.839
1.341 0.433
11.114 a 2,689
1.257
8.0, 904
11,162 3,600
0,472 a 0,340
8.826 2.729
0,477 8 0,889
credit
11.258 8.15
1.668
146676 5.448
0.423
10.880
1.421
13.667 5.051
0.940 0,612
default of uredit card-clliett
5.16
3,107 +. 1.123
11.378 1 2.133
3.793 0.881
5.161 a 4.300 0.328 a 0.512
3.197 a: 1996
0,566 2 0.651
elcctriity
6,524 e 1.863
0.725 e 0:451
9.101 2.665
0.944 0.557
5.834 à 138
0,420 e 0.354
8.487 8: 2.460
0.543 e 0.511
eye movemonts
19.125 1.791
9.433 + 1,385
19.738 + 1.490
5.755 1.399
1,990 + 1,23
0.329 + 102
1.916 1.492
0.277 + 0 302
heloc
4,513 1.826
1,564 0.617
0.799
0.154
0.725 0.598
0.155 0 190
1,263 0.711
0.359 = 0.346
house 16ff
9.195 e 2.408
2,530 0.446
8,693 1.302
2.322 à 0.730
4.629 a 2:314
0.063 = 129
4,192 e: 1.517
0.183 = 0.296
jannis
20.766 2 2.097
9.484
2 0.371
20.520 +: 1.017
7.400 0.3324
3.947 4 2.605
0,006
a 0.013
4,451 2 1,300
0.004 a 0.009
pol
23,401
5.448
3.137 L.038
20.137 4,200
3:435 0.6675
18,933 5:249 0.952 a 0.925
16.522 3 3.502
1,143 a 0,565
Table 11: Accuracy barrier for decision lists with AM.
Train
Datasel
Naive
Nuive (Modified)
Perm (Modified)
Nuive
Perm
Nulve (Modifed) Perm (Modified)
Rioresponse
21,323 6.563
13.549
5.943
14:578 3,930
063363+2 + 7.25%
9.325
3.088
4.817 2.825
7.346 4.261
3,871 4.608
1habetes/30UUS
5.182 e 3.745
5.500
e 3.328
2.754 1,088
1.371 0.507
4,910
4:244
4.926 : 3.796
1,476
1.308
0.694 : 0.649
Higgs
27.778
1.036
28:910
2.132
28.915 + 1.314
131 + 1.693
0.903 4,777
6.722 + 1.231
5.136 + 0.946
1.755 + 1.4
Mapic Telescupe
4,855 a 3.388
3,349
3.227
5,138 2.655
1.451 0,2005
4,137
3.763
3:001 3.476
4.534 2.588
1,090 1 0.457
MimBoNNE
23,059 1.479
7,500 9.782
3,870
1.683 17,248
13,868 7.222
3.585 10.540
0,860
bonk-murketing
11,953 3.794
6.722
11.580 2.167
2.815 0.957
11,387
4:111
9.151
7.2004
2.521 + 1.055
califoenia
6,522 a 3.195
5.812 2.366
8.425 3.273
0.8813
5.167 2:962
4,899
:: 2.01
6,84 a: 3.087
1. 1.186 a 0.643
coveriyee
13,408 3.839
14:727
7.029
11.114 e: 2.689
4.036 1.450
11,162 3,600
13.352 7.056
8.876 2.729
2 2.656 e: 1,302
credir
11.258 8.115
18.630
9.8006
146676 5.448
5.979
10,880 9.040
10.015
13,667
8.113 6.633
default-of uredit card-clients
5.16
12,580
5.070
11.378 1: 2.13
6,055 1.78
5.161 1
5,465 5.062
3.197 1.916
0.533 a 0.239
elcctrictty
6.524 = 1,863
4.988
e 2.732
9. 0.101 2.685
3,041
#: 0.676
5.834 1.838
4.561
:: 2.532
8.487 e: 2.460
2.637 : 0,750
movements
19,125 1.791
18.694
1,774
19.738 à 1.490
13,408 1.195
1,990 1.623
3,016 :: 1.625
1.916 L.492
1,807 :: 1.312
heloc
4,513 1.826
L.650
3,287 0.755
0.725 0.598
1,711 :: 1.278
0.711
0.528 a
house 16f
9.195 e 2.408
8.591
3,370
8,693 1.302
3.917 0.8
4.629 e 2:314
4.547 +: 2.726
4.192 +: 1.517
0,751 = 0.508
jannis
20.766 2 2.09
20.768
2,200
20 30.520 à: 1.017
12.008 0.892
3,947 4
6,472 +: 2.342
4.451 1: 1,300
0. 0.106- + 0.162
pol
23,401
5.488 17.384.16.44
20.137 4.4200
10.339 2.744
13:285 3.863
16.522 3.500
6 6.492 g 2.536
Table 12: Training accuracy barrier for permuted models with WM. The numbers in parentheses represent the original accuracy.
Dataset
Non- Oblivious Tree
Oblivious Tree
Decision List
Decision List (Modified)
Bicresponse
5,876 1 1.477 (930055
4,800 0.895 (91.753)
4,259 a 0.698 (91.771)
4.641 a 0.918 (90.489)
DiassteS13OUS
1,388 + 1.159 (60.086)
1,120 1.123 (60.567)
L e 1,00 (60)42)
LUBS + 0.005 (61.178)
Higgs
18,470 0.769 (97 (32)
19.754 à (97616)
16.110 0.518 (95.838)
14.071 0.395 (91)831)
0.576 + 0.556 (84-963)
0.475 + 0.632 (54-460)
0.355 e (1.83 (84 999)
0.182 + 1.144 (15.411)
MiniBooNE
2,272 0.215 (99.980)
2.388 0.194 (999 (99)980)
1911 a (99.977)
1,500 1 0.173 (995766)
bank-markkting
2,11 1.183 (79.490)
2,995 1.552 (79.351)
0.979 0.478 (79: (6))
0.375 + 0.445 (79.700)
califomia
0,875 a 0.551 (87.897)
0,814 a 0.224 (87.909)
0,621 a 0.263 (88.012)
0.538 + 0.214 (88.054)
covertype
1.839 0.336 (79.445)
2.073 0.657 (79.151)
L.341 0.433 (79.618)
1,257 1 (79
credit
3.172 2,636 (78.679)
2.360 0.25 (78.231)
1.968 s 0.950
1,590 + (78550)
default of credit card clients
5,419 1.318 (78.017)
4.512 1,033 (78.657)
3,107 1.123 (79.315)
3.793 1 0.58] (78-208)
electricity
1.035 0.543 (80.375)
L,060 0.644 (80.61)
0S25 0.451 (80.396)
0,944 + 0.557 (8U661)
pne_movements
11,605 2: 1.929 (81 ($1.693)
12.687 à 1.645 (83.230)
9,433 a 1.385 (81.075)
8,755 1 1,391 ($1441)
helne
1.652 0.475 (77.430)
2.517 1.156 (78.367))))) 370)
1,564 0.617 (77.968)
1,574 1.154
house_I6e 16H
3.362 : 0.482 (95.093)
3.302 a 0.376 (93. 351)
2.520 0.44 (92.7855
2.222 + 0.730 (93.008)
jannis
10,412 1,404 (1000000
11,358 0.377 (100.000)
9,184 0.371 (100.000)
7.400 0.324 (100.00))
pol
4.612 0.912 (98.348)
5.059 1.482 (98.340)
3.137 1,088 (97.883)
3.435 4 0.675 (97)881)
Table 13: Training accuracy barrier for permuted models with AM. The numbers in parentheses represent the original accuracy.
Dataset
Non Oblivious
Oblivious
Decision List
Decision List (Modiñee))
Ricresgonee
14.066 + 7.045 (935005)
19:033 + 8,533 (91 753)
13.340 + (91.771)
10. 36.366 + 7.256 489)
3,086 + 2.566 (61
5,475 + 3.200 (60.567)
5,590 3.328 (60.42)
T,311 0.507 (61.178)
Higgs
30,704 + 2.899 (97 (32)
33.234 4 (9116 (97.616)
28,910 a: 2.132 (95.838)
20.131 + 1,693 (95 8918
MagicTeiessooe
3,309 + 1.486 (843663)
3.902 + 1.931 (64)460)
3,349 + 3.273 (99)
1,451 + 0.705 (85 (15.411)
MiniBooNE
24,934 8.157 (995900)
41.022 3,298 (19) 980)
18.149 7.500 (99.977)
3,870 1.108 (79)976)
hank-mtrdecting
13.598 + 7.638 (79 4000)
12.248 + 6.748 (70 351)
9.782 + 6.723 (70. 166)
2,815 0:957 (79 709)
california
5,800 2,036
9.539 a 4,798
5 2:365 (88.012)
2.154 0.813 (88)04)
awertyps
19.708 + 6.302. (79.44))
27.500 2.172 (70 754)
14:727 7,099 (70.618)
4.03% 1,4 (79 550)
credit
10,556 + 8.753 (78.679)
9,839 + 6,608 (78.231)
18.620 9 (78. 166)
3,59 6.919 (7S 905)
default credit clients
14.166 2:297 (75.017)
21.745 7.075 (78.657)
5.000
6.055 1.178 (78
elecrisity
12,955 + 4,558 (80.575)
18.177 + 5,079 (80361)
4.988 (80 396)
3.041 + 0.676 (8065T)
eye_movements
18.757 1.273 (81
23.221 3,024
18.694 1.7744
13.408 a 1,196 (51,45))
heloc
6.564 2.404 (77.430)
9.074 3.894 (78.370)
5.504 + 1,650 (77.968)
3,287 0.758 (78, 550)
bouse_16s 16H
10.184 + 2.607 (93.093)
17.965 + 5,099 (93.351)
8,591 + 3.3710 (92.783)
3.937 0.816 (54)
jonnis
19.004 (,246(1100000)))
23.482 3.113 (100.000)
20.768 2:200 (100.000)
12.008 0.892 (00)
pol
16.267 + 3.914 (95. (98.348)
19.558 + 5,785 340)
17.384 a 6.441 (97.883)
T0.5599 = 2.743 (913
16

---

Published as a conference paper at ICLR 2025
Biocespense
DOUs
Higes
MagicTolsseppe
MiniBooNE
bank markeeing
califomnia
covertyp
10]
Arenney
80
70
Intepelasos
Iniorsolation
Inteppllatinn
Interelaaion
hneppllaioo
Inaroolatinn
intepplation
Intepelatioz
credit
de Saullt--
clients
heloc
house 16H
6o
Ico
Azcemay
7O
60
Interolaiizz
Inierpllaion
Interplation
ixeeplliio
Intepolaaoo
Inarnolatin
intepelation
Intepelatioz
Nave
Figure 10: Interpolation curves of train accuracy for oblivious trees with AM.
Biocesponse
Duabetes BOULS
Higes
MagscTllsespee
MiniBooNE
bank-markecinng
califonnia
75
6S
CU
Estepolaioo
broapolation
beoopelation
Intepelation
Intepelaiin
postolation
Iropplation
Istepelasion
credit
house 16H
m
Lteepllaio
Inapolation
bespelution
Ixtepeltioo
Lilepolaion
Inspoltion
intppiation
Istepelation
Naive
Nermatation
Figure Interpolation curves test accuracy for oblivious trees with AM.
Diorespon.se se
liie
Magic Telescage
MiniDooNI
bunks marketing
califomia
covertype
50
Agurayy
Islopolaiin
Inteppaatoon
Lalopolaion
Ieterpoation
Latepllaion
Intepoltiinn house 1611
Istepllaion jannis
Intopolatios
credit
Bofaal--fff credit crudit-car--ie carenst
electricity
heloc
Mi
100
V
Eneoolaion
Lntepoation
Latopolaion
Estepelaion
lntepokiioz
Intepolaii
Inzepolaton
Figure 12: Interpolation curves train accuracy for oblivious trees with WM.
Bioreggense
Diabetes10USS
Higes
MagicTelescope
MiniDosNE
bank markotin
califomiia
Dovertype
75
Intepiatton
Toee Treeppaatio
Tneeppietion
Insorpotaton
Emerpebation
Inaryilaion
Entrgetatoo
Inteyelation
credit
defanl of candellients electricity
house 1611
70
Integetatonn
Inoeplation
Insqpilttn
Emoppoation
Inseytation
Ineeelron
Inaeyslation
Figure 13: Interpolation curves of test accuracy for oblivious trees with WM.
17

---

Published as a conference paper at ICLR 2025
Biocespense
Higes
MagicTolsseppe
MiniBooNE
mankmnnkeeing
califomnii
covertype
Acorney
TU
75
Interolaioos
Iritrsolatoon
Inteppllation
Interpelaioe
hntepelaiio
Inaroolation
interpiation
Intepelatio
credit
de Saultl Feeeelt---eriiiie.oo
clients
house 16H
m
Arcmmay
60
Interplliiaz
Inierpolation
Interelation
interplaiio
Interolaaoo
Inarmolaiinn
insepelation
Intepelation
Naie
Perratation
Figure 14: Interpolation curves train accuracy for oblivious trees with AM by use of split dataset.
Biocesponse
DuabenestBUUJS
Higes
MagscTllsssppe
MiniBooNE
bank-markekingg
califannia
covertype
60
Eiteppoliioa
bri polation
brorpelction
Intepelation
Intepeliiin
Ioapolation
Intepelation
Istepelaiioz
credit
de Ferel--oeeeddi-eaad -ieeedi-ii-dd---stss
heuse 16H
70
II
$2.5
62
Litepolaios
Inapolation
Inspolition
Istepelation
Litepolaiio
postpoltion
intppiation
Istepelatin
Naive
l'rmmtatiion
Figure 15: Interpolation curves of test accuracy oblivious trees with AM by use of split dataset.
Dioresonse
Diabrees130US
Higgs
MagicTolesscpee
MiniDooNE
hank-markotin
california
covertape
TO
Isterpoltioa
Ini polution
Insepelatiin
Incepelaiis
Iatepelaiio
Iroepolation
Intepplation
Isteppllsios
credit
de Se-ulll-ofrrriiieee oereedi-ccrde
clients electricity
heloc
house 16ll
jannis
TO
Isterolaiiu
Insppoltion
insrpolation
Intepelation
Litepolaina
insrooation
insqeiation
Istepelatoo
Penratation
Figure 16: Interpolation curves of train accuracy for oblivious trees with WM by use split dataset.
Biocesponse
Diabeees
Higes
MagicTolssesee
MiniBooNE
bank marketing
california
covertype
60
70
B0
60
Interpllaoo
Insegotation
Troepeistinn
Ineepetation
Integotation
Inorgolation
Tnteppiation
Intepetation
credit
ofdault-ofereeii card clivets
house 16H
22
60
Intepllii
Insepilation
Irspelition
Ineepettion
Ineeoteiin
Inapotation
Trneptatioon
Trtepetttoon
Figure 17: Interpolation curves of test accuracy for oblivious trees with WM by use of split dataset.
18

---

Published as a conference paper at ICLR 2025
Biorespon.e
300S
Hige
Mapic Telescope
MiniBosNE
bank mazketing
califomia
covertipe
100
Inkepolaton
Interpdatioe
Ialepllaion
Interpdaiiss
Intepelaiin
Interoliiiz
hiippllaio
Inzepolatiz
credit
defaylk- ad cardd---add-lients
house 16H
80
160
50
Inkepolazon
Interpaazioz
intepolaiin
isteppaiion
Etiepolazon
Intepootioz
hiepolrin
Inzepolatzz
Figure 18: Interpolation curves of train accuracy for non-oblivious trees with AM.
Biocesponse
BUUSs
Higes
Magccellsespe
MiniBooNE
bank-markeeinng
califonnia
covertppe
Isterplatios
bri polaion
bnoopelation
Intepelttio
Intepeliiio
bootolation
Iropplation
Istepetasion
credit
house 16H
Litepoliiu
Inapolatio
bespelution
Istepelatios
Litepolaion
intepittion
Istepelation
Naive
N'rrmtatiion
Figure Interpolation curves test accuracy for non-oblivious trees with AM.
Diorespons
130US
Higgs
Magic Tolesoope
MiniDooNE
Nank-markoting
califomia
covertspe
100
OO
K25
$0.0
Isterpolaios
Ini polution
hntopelatinn
Intepeliiio
Iraepiation
Intepplation
credit
Saull
feredii-catte clients electricity
house 16ll
I60
11,5
12.5
Istopolaio
Ioapolation
inspolution
lstepelatios
latepolaina
hoazolaion
inqpettion
Istepelaionz
Figure 20: Interpolation curves train accuracy non-oblivious trees with WM.
Bioreggense
Diabetes30USS
Higes
MagicTelescope
MiniDosNE
bank markotnn
califooiia
Dovertype
75
Intepiatton
Toee Tneeppaatio
Tneeppietion
Insorpotaton
Emerpebation
Inaryilaion
Entrgetatoo
Inteyelation
credit
defanl of candellients electricity
house 1611
70
Integetatoon
Inoeplation
Insqpilttn
Emoppoation
Inseytation
Ineeelran
Inaeyslation
Figure 21: Interpolation curves of test accuracy for non-oblivious trees with WM.
19

---

Published as a conference paper at ICLR 2025
Bioce clocespone
DaabetesBOOL
Higei
MagiTTelssspe
MiniBooNE
bank-mLikcching
caliCennk
Interpolaios
Iri polution
brsepelution
Lacrplliios
Iatepelliin
inatplition
intepplation
lstepelasios
credii
Feredii Se-aull-oFerreiiiee
clients electricity
heloc
house 18l1
TO
Istepolaiis
Inappolation
insrpelation
istepeltiioz
Intepolazin
insrooation
insepiation
Istepelniizz
Figure 22: Interpolation curves of train accuracy for non-oblivious trees with AM by use split dataset.
Bieresponse
Diabetes 1OOIS
Higes
MagieTolssepp
MiniBooNE
bank-marketing
caliCornis
ES
Intepolatio
Irarpolation
bropplitiin
Entepelaiion
Intepolaion
Inorpolaion
Inteppittion
Tetepelation
sye
TM
96
Aoumiry
TO
S0
Nave
Troe Pomnataiio
Ouri
Figure 23: Interpolation curves test accuracy for non-oblivious trees with AM by use of split dataset.
esponec
BOOUS
MagisTolkisspe
MiniRooNE
bank-mirketinn
califoenik
eovertyne
OF
Suulle-fenelllleneeeeeee electricity
eye movements
16k
jannis
pol
75
Intepelrioc
Insepolation
Incepiittin
Incpplation
Inseoleooo
Inqqpittion
Intepetation
Nave
Tro Pemmattiin
+
Gues
Figure 24: Interpolation curves of train accuracy for non-oblivious trees with WM by use of split dataset.
Blocesponic
Higgs
MagicTolssospe
bank-marketing
covertype
Accmmyy
credit
de fereeeefeeed---ddeeeeeeett
electricity
eye movements
heloc
81.5
house 16H
jannis
pol
$2.
Arsmyy
556
NQ
50
Ineepllaan
Interpolation
Incrpsiation
Incepeiatio
Intepoliaoon
Inorsslation
Incrppittion
Intepelanee
Nave
Pommatation
Figure 25: Interpolation curves of test accuracy for non-oblivious trees with WM by use of split dataset.
20

---

Published as a conference paper at ICLR 2025
Biocespense
Dub
Higes
MagicTolssopp
MiniBooNE
bank markeeing
califomnia
covertype
P0
To
Intepellaoos
Intepplation
Interpllaion
hitepelaaion
Inaraolation
interplation
Intepelation
credit
Sellll---feeeeee card clients
house 16H
Ico
100
V
M
15.0
Iniepolation
Interolation
ixerpliiio
Intepllai
Inarmolatinn
intepelation
Intepelatin
Natre
Pormention
Figure 26: Interpolation curves of train accuracy for decision lists with AM.
Biocesponse
Higes
MagocTllsceppe
MiniBooNE
bank-markekingg
califonnia
covertppe
Istepplaiio
lri polation
brorpelation
Intepelation
Inteplliio
Ioapolation
Iropplation
Istepelasion
credit
de fenel---feedi--aadeeee
house 16H
$7.5
92.9
Iitepolaios
Inapolation
bespolution
Istepelatio
Lilepolaion
iroppoltion
intepiation
Istepelation
Natre
Permention
Figure Interpolation curves test accuracy for decision lists with AM.
Diorespon.se se
Magic Telescope
MiniDooNI!
bunks marketing
califomis
sovertype
90
102
10
Lskopolaion
Inteppation
Lalopolaion
Intepedation
Lateolliion
lntepolttinn
Iscepllaion jannis
Incopolliius
credit
defaglkoo credi crudit-car--lee and-cliens electricity
heloc
house 1611
100
9
Eteooolaion
Inteppdatios
Latopolaicn
Istepolation
Estepolaion
lntepoktion
Intepllzin
Inzepolatio
Parnutatios
Figure 28: Interpolation curves train accuracy for decision lists with WM.
Biocesponse
Higes
MagicTolsseope
MiniBooNE
bank marketing
califomnia
covertype
Intepettaio
Inargolation
Tnorppistiin
Ineepetation
Inorgotation
Trteplattion
Irtepetttion
credit
dedault
clivnts
house 1611
Intepeliio
Insppilaton
Iropelation
Intepetation
Ineeootiin
Inipotation
Imneplttion
Intepetation
Penmataioon
Figure 29; Interpolation curves of test accuracy for decision lists with WM.
21

---

Published as conference paper at ICLR 2025
eiocespenee
Hipes
MagicTolsseope
MiniBooNE
bank-merkkdding
califennia
eovertye
Aouray
SF
60
Intepelatios
politon
idtepiiation
Istepelltioss
credit
de Serellieeeeellldd---llil
electricity
movemments
heloc
house 16H
jannis
pol
Acurry
70
55
Istepplaion
liia polation
intepelatiin
Letepeliiis
Intepelaiins
Inaepiation
intepplation
lstepelasioz
Figure 30: Interpolation curves train accuracy for decision lists with AM by use split dataset.
Biocesponse
Higes
MagicTolsseppe
MiniBooNE
bank- marketing
california
covertspe
A
Intepllrooo
Iratgolation
brorpelstion
Incrpeltion
Inepellioo
Inorolation
Irceplettion
Ertepetation
credit
dedault-oeeneii-cee clietti
16H
80
70-
$50
815
Intepolaion
Inappilation
Irspolation
Ixeepeltion
Inteolliio
Inseooatin
Intepiation
Intepetation
Natre
Pormunaion
Figure 31: Interpolation curves of test accuracy for decision lists with AM by use of split dataset.
Diorespense
Drabetes130U8
MagicTolisospe
MiniDooNE
Nank-markeing
california
60
B
Interplaioo
Inaepilation
Insqpiotion
Iriepelation
Interplation
Inorysiaion
Intepiotionn
Trlepetanoon
Suilt- feredeieeeet electricity
eye
16H
SE
$5.0
$255
Natre
Time Permettioo
Figure 32: Interpolation curves of train accuracy for decision lists with WM by use of split dataset.
Duubetes1BOUS
MapicTolasospe
MiniHooNi
bank-marketingg
califoenia
covertype
70
Interpolaoer
Incerpiation
Interpllaee
Incezslation
Inseppiation
Iniepelaton
Seuuttooffeediiccu--iiiiee clectricity
eye movements
16H
jannis
pol
85.0
$5.6
Intepolasoo
Natre
Thes Pormenation
Figure 33: Interpolation curves of test accuracy for decision lists with WM by use of split dataset.
22

---

Published as a conference paper at ICLR 2025
Biocespense
DUS
Higes
MagicTolsseppe
MiniBooNE
bank markenin
califomni
coventpe
I0]
Aueuney
to
Intepelasos
Iniorsolaionn
Intrpllation
Interelaaion
hilepelaiio
Inaroolation
interplation
Intepelatioz
credit
defaltt- clients
house 16H
Ico
Auretay
75
15.
00
12.9
Intepolai
Incepolation
Iscepliiio
Inarnolaionn
intepplation
Intepelatioz
Pormention
Figure 34: Interpolation curves train accuracy for modified decision lists with AM.
Biocesponse
Higes
MagicTolsssppe
MiniBooNk
bank-markecingg
califonnia
covertpe
85
Acueay
6
Istepolatio
lri polation
bnoopelaticn
Intepelation
Intepeliiin
boopolation
Iroeplation
Istepelation
credit
Renel---eeedii-euddde 10.
16H
t0
81.5
725
61.5
10
82.5
Inapilatinn
brspplutiin
Istepelatioz
Lilepolaion
intppiction
Istepelation
Natre
Permention
Figure 35: Interpolation eurves of test accuracy for modified decision lists with AM.
Dioresonse
130US
Higgs
MiniDooNE
bank- markotin
califomii
covertspe
100
NI
Isterpoltios
Inappolaion
Intepelaiin
bospplation
Intepplttion
lstepelatios
cnedit
Saull faeell--feeiiicrre clients
heloc
house 16ll
jannis
Ic0
11.
15
Istopolaius
Ioapolaiio
inspplution
lstepelatio
12.3
litepolainn
Iosmolaton
intqelation
Istepelatioz
Pasnstaioon
Figure 36: Interpolation curves of train accuracy for modified decision lists with WM.
Biocespense
130S
Higes
MazicTolsseppe
MiniBooNE
bank marketing
california
covertppe
M
Interettaoo
Inarpetation
Inoepeistion
Intepedation
Integtaatoo
Inorgolatinn
Troepiationn
Ireepettion
credit
dedault card clivnts
house 1611
760
TO
825
Ineeplaii
Inappiltion
Iropelation
Inepetation
Ineeotrion
Inipotaton
Irnqplation
Intepetation
Pemmaaiin
Figure 37: Interpolation curves of test accuracy for modified decision lists with WM.
23

---

Published as a conference paper at ICLR 2025
Biocesponic
Duabetes BOUIS
Higes
MogsTelssepee
MiniBooNE
bank-miiicciinng
caliCenni
TO
prtepplliin
Iria politionn
brsepelution
latereliiis
Intepelliin
Iraepolatinn
intepplation
letepelaiio
credii
Sa Ceuull---rreeii-aae clients electricity
heloc
house 1611
jannis
TO
62.5
$1.5
S75
Istepolaiis
Inippolation
insrpolation
lstepelttios
Litepolaion
insrooation
insppiatinn
Istepelatioz
Postenation
Figure 38: Interpolation curves of train aceuracy modified decision lists with AM by use of split dataset.
Bieresponse
Dishetes BO01S
Highs
MagieTolsssppe
MiniBooNE
bank-marketing
californis
C0
Intepolltios
Mrarpolation
brsepllation
Entepelaiion
Inteooliion
Inorpolaion
Inteplatioon
Tetepelation
Suull-o
sye
II
70
Aoumryy
$50
$25
Naive
Thee Pecmcaaionn
Figure 39: Interpolation curves of test accuracy for modified decision lists with AM by use of split dataset.
esponee
180U1
MagisTelessspe
MiniRooNE
bank-marketinng
califoenik
covertype
76
Treewistion
AaBull--fetellleneddeleett electricity
eye movements
16H
janni
pol
Antronyy
K2.5
87.5
70
TO
$2.
Intepetrion
Intepoiation
Inepelstion
Intepolaioo
Irqqpittion
Irsepetaten
Naire
Thee Pormeration
Figure 40: Interpolation curves of train accuracy for modified decision lists with WM by use of split dataset.
Blocesponie
Higes
MagicTolssospe
bank-marketing
covertype
m
Accine
20
BO
credit
Se-Sutt-ooeerediiooo decleets
electricity
eye movements
heloe
house: 16H
jannis
pol
$2.5
Antmyy
30
T0
Intepelaree
Inverpalatoon
Incppsttion
Incepeiation
Ineepllaoon
Inorsolation
Inteppiotion
Intepettaee
Naire
Uhe Bormetaioon
Figure 41: Interpolation curves of test accuracy for modified decision lists with WM by of split dataset.
24

---

Published as a conference paper at ICLR 2025
Non- Obllvbbiv
Oblivious
Decision List
Decision List (Modilied)
100
100
100
98
98
98
96
96
96
94
Intespolatinn
Interpolatin
Interpolation
Intepolation
Navee
Tree Permatation
Ous
Figure 42: Interpolation curves of accuracy with WM for MNIST (LeCun & Cortes 2010 dataset.
Non-Oblivious
Oblivious
Decision
Decision (Modified)
100
100
100
100
98
98
98
98
96
96
96
96
94
94
94
92
92
92
Interpolation
Interpolation
Inserpolation
Intorplltion
Naive
Tree Permatation
Ours
Figure 43: Interpolation curves of test accuracy with AM for MNIST (LeCun & Cortes 2010) dataset.
25


Reviews:
[{"review_id": "wlfp3orC0Z", "reviewer": "Reviewer_y2Hs", "summary": "This paper explores Linear Mode Connectivity (LMC) in soft tree ensemble models. LMC is well studied in neural networks, but achieving it in tree models presents unique challenges due to their architectural differences. The authors identify additional invariants, subtree flip and splitting order, that are necessary to achieve LMC in tree structures that differ from neural networks, including permutation invariance. With a matching algorithm that takes these invariants into consideration, the authors show that LMC can also be achieved in soft tree ensembles. And they further present a modified decision list architecture that preserves LMC without these additional invariances, aiming to simplify model merging and other parameter-based applications.", "questions": "- In Figure 6, I don't quite understand why AM considering only permutation increases the barrier more than naive interpolation. Why does considering only activation result in a worse match than identity? The authors explain this in the main text as follows, but I would like a more detailed explanation.\n    \n    > This is because parameter values are not used during the rearrangement of the tree in AM.\n    > \n- Why do the authors think that the barrier after matching increases as depth increases? Ainsworth et al. (2023) showed that the barrier decreases as width increases, but they did not experiment with depth, and Entezari et al. (2022) measured the barrier for changes in width and depth without matching, which is different from the experiment in Figure 6, which measured the barrier after matching.\n- Is there a compelling reason to use activation matching over weight matching, given that it does not seem to offer any clear advantages? Or is it simply intended to replicate the methodology of Ainsworth et al. (2023) for validation purposes?\n- It would be useful to know the actual runtime required for matching. Compared to neural networks commonly considered in standard LMC research, such as ResNet, the number of parameters here is significantly lower. Given this, even with a large number of invariance patterns, it may not take very long to check all of them.\n- Some minor suggestions:\n    - In Figure 6, the x-axis represents different categories without a clear order, making the use of a line plot appear unnatural. A bar plot or box plot would be more appropriate in this case.\n    - In the tables and figures, the notation \"Ours\" does not clearly give the intended meaning. While I understand that it stands for \"Perm & Flip & Order\", it is somewhat confusing. This is especially noticeable in Tables 3 and 4, where \"Decision List (Modified)\" is also the proposed method (\"Ours\"), which makes the absence of results in the corresponding cell seem unnatural. Furthermore, I assume that \"Naive\" is meant to indicate the results without matching, but this is not explained anywhere. To improve clarity, it would be helpful either to label it more explicitly as \"naive interpolation\", as in the cited papers, or to provide additional clarification in the main text.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The approach of exploring linear mode connectivity, which has been mainly studied in neural networks, in a different architecture is novel.\n- The organization and flow of the paper effectively explains the existing research and the proposed method and is easy to understand.\n- Through various experiments, the authors show that linear mode connectivity can be achieved in soft tree ensembles.\n- The authors show that soft tree ensembles trained on different data splits can be merged to form better performing models.", "weaknesses": "- The authors do not provide a more efficient matching algorithm other than exhaustive search.\n- The paper does not provide sufficient justification for using the proposed modified decision list. Specifically, the proposed architecture presents a higher barrier compared to an oblivious tree that includes all invariants. Furthermore, it lacks a compelling practical use case demonstrating more efficient matching relative to other tree-based architectures, such as model merging, which can be used to improve performance. To strengthen the argument, it would be necessary to include some experiment similar to the one shown in Figure 8, applied to the proposed architecture.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gukRYXxLMU", "reviewer": "Reviewer_rJGW", "summary": "This work studies the phenomenon of linear mode connectivity (LMC) in decision tree models (as opposed to neural networks, where they have been studied extensively). Specifically, they investigate whether soft-tree ensembles can be interpolated, while retaining accuracy. Unlike in neural networks, where permutation invariance is sufficient, the authors show that additional invariances unique to decision tree models are necessary for LMC to hold - in fact, this is the key finding of the work.", "questions": "See the Weaknesses section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper has several strengths:\n\n- The problem addressed in this work is of general interest, and illuminates an interesting property of decision trees.\n- The paper is very clearly written, and easy to follow\n- This paper hinges upon it's empirical evaluation: the experiments are quite thorough, and clearly show how incorporating *additional* invariances into model interpolation leads to better accuracy (the key claim of the work).\n- The notion of the *modified decision list* architectures is an interesting and potentially highly useful one (as it seems to reduce computation cost per inference)", "weaknesses": "There is one significant weakness in this work:\n\n- Lack of Rigorous Theory: the paper would have been strengthened significantly had the authors provided a rigorous analysis of the effect of the stated invariances (permutation, subtree flip, and splitting order) on the ability to interpolate 2 (or more) models - even if only on extremely simple cases. Were that so, the empirical results would have been used to support rigorous theory, which would have been a much more powerful argument.\n-  Linear Mode Connectivity was proposed to understand how deep neural networks could be sparsified (Frankle et al, 2020). Can a similar analysis of methods to sparsify decision trees be done, provided the insights proposed in this work? An analysis of this sort - where the need to interpolate models becomes evident - would have also noticeably improved this work.\n- The authors do not highlight specific tasks for which interpolation of trees would be of significant benefit. This weakens the argument motivating the need for this work. For instance, does model interpolation in tree ensembles improve robustness to distribution shift?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SLPGpNeoA3", "reviewer": "Reviewer_rPCT", "summary": "This paper investigates Linear Mode Connectivity (LMC) in the context of differentiable tree ensemble models, particularly focusing on soft tree ensembles. LMC refers to the property where linearly interpolating two models (in parameter space) does not degrade performance, a phenomenon previously established for neural networks. The authors extend this concept to tree-based models, identifying specific architectural invariances unique to trees—namely, subtree flip invariance and splitting order invariance—as critical for achieving LMC. They further propose a novel decision list-based architecture that bypasses these invariances, simplifying the conditions necessary for LMC. Through empirical evaluation, the paper demonstrates that LMC can be achieved in tree ensembles, broadening the understanding of LMC beyond neural networks. In summary, I believe that both the research topic and methods are relatively novel and will significantly contribute to the deep learning community.", "questions": "See Weakness.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality:** This work is original in extending the concept of LMC to tree-based models, an area previously unexplored. By identifying invariances specific to tree structures, the paper introduces a new perspective on achieving functional equivalence in non-neural models.\n\n**Clarity:** Despite the complexity of the topic, the paper is clearly written, with detailed explanations of both the mathematical framework and empirical results. Figures and diagrams (such as Figure 3 on invariances) effectively support comprehension.\n\n**Significance:** The work expands the applicability of LMC, which is valuable for understanding stability in non-convex optimization and facilitating practical applications such as model merging. The findings on tree-specific invariances could have a substantial impact on future research in tree ensemble models and their integration with neural network techniques.", "weaknesses": "**Empirical Validation Scope:** The empirical results are primarily based on tabular datasets. Extending the validation to additional types of data (e.g., image or sequential data processed via tree ensembles) could further strengthen the findings.\n\n**Scalability of Additional Invariance Handling:** The paper discusses the computational expense associated with handling additional invariances for deeper trees. However, a more detailed discussion of potential optimizations or heuristic approaches to manage this complexity would be beneficial.\n\n**Comparative Analysis:** While the results demonstrate LMC in tree ensembles, the paper could benefit from a more in-depth comparison with related methods or model architectures, particularly alternative approaches to model merging or parameter interpolation that do not rely on LMC.\n\n**Equation Reference:** Please use \"Equation (1)\" instead of \"Equation 1.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)