Linear Mode Connectivity in Differentiable Tree Ensembles

Thank you for your review.

The main weakness of this work is lack of theoretical support and practical implications. However, I acknowledge that these are the same limitations that are attributed to LMC in neural networks, which is a significantly more broad and well-studied field than LMC in tree ensembles. I hope that future work will address these disadvantages in some way.

Thank you for your understanding.

Also, I believe that the text could be slightly polished to eliminate typos and small inaccuracies. For instance, the value in line 127 is not defined at its first occurrence.

Sorry, $D$ refers to the depth of the tree. This will be corrected in the camera-ready version.

It is indeed surprising that mode connectivity can worsen compared to a naive interpolation after accounting for the permutation invariance (e.g., Fig. 1). To my view, the barriers of naive interpolation (realizing an identity permutation) must upper bound the barriers after permutation search. I would ask the authors to give a small comment on this.

Since we are only looking at the similarity of activations and weights, it does not necessarily mean there will be an improvement in the loss landscape. For example, in Figure 1, even though the distance between parameters is smaller after considering permutations (top right model to the Target), the barrier is larger compared to the naive interpolation from the Origin to the Target (bottom left to the Target). This might be the situation occurring here.

Is the weighting strategy described in Sec. 3.2 remains the same for oblivious DTEs that share the same parameters for all nodes at equal depth, so every parameter affects all leaves?

Yes, your understanding is correct. In the case of an oblivious tree, the contribution of all splitting rules is equal.

Interestingly, according to Figure 5, non-oblivious DTE shows better LMC than oblivious DTE when accounting for the same invariances. I suppose that this benign over-parameterization effect is similar to increasing in DTE or width in NN. What do the authors think?

I believe the reason is that non-oblivious trees exhibit a greater number of invariance patterns, which increases the likelihood of achieving LMC through parameter transformation. When considering a tree of depth $D$ , the number of subtree flip invariance patterns in an oblivious tree is $2^D$, whereas for a non-oblivious tree, it is $2^{2^{D}-1}$. As you mentioned, this could be seen as a benefit of overparameterization.

Figure 7: I would suggest adding the result of common (combined data) training for comparison alike [1].

Thank you for your comment. Please check our uploaded PDF in the rebuttal. Through model merging, it demonstrates similar performance to full data training even with split data training.

Does LMC in DTE suffer from the same variance collapse issues reported by [2]? If do, how could it be repaired and could it additionally improve LMC in DTE?

Although this study does not investigate deeply into the topic, Equation (5) suggests a similarity between tree ensembles and neural networks. Therefore, techniques such as REPAIR could potentially enhance matching performance. Our research can be integrated with existing studies, including those on matching algorithms.

It is a little astonishing how much worse Activation Matching performs in DTE compared to Weight Matching. In NN LMC (based on literature and my personal experience), this difference is not so prominent. Could the authors comment on this a little more?

In activation matching, we use the output of each individual tree, but the number of parameters required to obtain the output of each tree is greater compared to typical MLP activation matching. In MLPs, we only need to consider the parameters corresponding to the width of each layer for calculating an activation, but the tree structure adds complexity. This likely makes the matching problem more challenging in our case.

At the same depth, (modified) decision lists contain less total parameters than oblivious trees and especially non-oblivious trees. However, all DTE architectures perform very similarly according to Tab. 3 and 4. Could the authors give any explanation of this effect?

Considering both representational capacity and training dynamics, such an outcome is possible. Additionally, since Table 3 and Table 4 consider trees of depth 2, the change in the number of parameters might not be significant, which could be another reason. Given the consistent results of other barrier-related experiments, it does not appear to be due to an implementation error (the reproducible code is also provided).

Would adding subtree flip invariance in the terminal splitting node of regular decision lists improve their LMC reported in Tab. 3 and 4?

There is a possibility of improvement. However, the impact of this invariance is likely to be less significant compared to a perfect binary tree, so the performance gain may be smaller.

Thank you for your review.

Due to the 6000 character limit, we will address minor points during the discussion phase. Below in the rebuttal, we have included responses to the aspects we consider important.

​​In my opinion, the main contribution of this paper is a showcase that different architectures need to account for different invariances when LMC is analyzed, e.g. MLP and soft trees have different invariances. I think that this insight alone is not enough for a paper, because it sounds quite obvious even without analysis.

We would like to emphasize that even if invariances exist, it is non-trivial whether they have an impact on LMC, and investigating it could provide a valuable contribution to the community. For example, ReLU networks exhibit permutation invariance and scaling invariance, but scaling invariance is not important for achieving LMC. While it was known that permutation invariance exists in neural networks, ascertaining whether its consideration could achieve LMC was a challenging question. Research investigating this question has had a significant impact on the community [1]. Moreover, architectures like transformers have different modules, such as attention mechanisms, and demonstrating the importance of considering these architecture-inherent invariances for matching has been highly valued and accepted at a recent conference [2].

Our research contributes new insights regarding the existence of invariances and demonstrates that considering them can indeed achieve LMC. Additionally, we have shown that by adjusting the tree structure, we can optimize both the amount of invariance and computational efficiency, which is an essential consideration for practical applications and this idea can be applied to other model structures as well. We believe these findings are valuable and bring novel aspects to the community.

It is very important to make sure that interpolation results are not computed between the models which are almost identical (that can happen if there is not enough diversity in training recipes). Could you please provide results with distances (any kind of them, e.g. L2 or cosine similarity) between the solutions in Figure. 5 for "Naive", "Tree Permutation" and "Ours" parameter transformations?

Thank you for your suggestion. We conducted an additional experiment using the MiniBooNE dataset, as referenced in Figure 1. The experimental settings are the same as those used for creating Figures 1 and 6.

L2 Distances:

• Naive: 98.01
• Tree Permutation: 96.13
• Ours: 78.04

Cosine Similarity:

• Naive: 0.0035
• Tree Permutation: 0.0414
• Ours: 0.3682

These results indicate that the models are not nearly identical, as the distances do not approach zero even after matching. Therefore, we do not believe we are facing the issue you are concerned about. Additionally, it is known that achieving LMC does not strictly require the distances to be exactly zero [3].

What do you mean by crucial for the stable success of non-convex optimization? Since this motivates your analysis, could you justify the main text, please?

Despite the challenges of non-convex optimization, our machine-learning community empirically observes that models consistently achieve similar performance even with different random initializations. This phenomenon is quite non-trivial, and understanding the underlying reasons is crucial. Achieving LMC implies that the solutions attained by training from different initial values are fundamentally equivalent. This suggests that the abundance of functional invariance is one of the reasons for the stable success of non-convex optimization. This perspective is also highlighted as a motivation in existing LMC research [1] and is mentioned in our introduction.

Why do you study LMC between ensembles of trees and not single trees? That would remove the need for accounting for permutation invariance.

We can consider a single tree. However, as shown in previous studies [1] and Figure 5, the large number of trees (or the large width of neural networks) is known to be important for achieving LMC. Therefore, LMC is less likely to be achieved when considering only a single tree.

There is no theoretical justification for why and in which scenarios linear mode connectivity exists for soft trees.

You are correct; the current community lacks a strong theoretical explanation for why LMC is achieved in neural networks, let alone in tree ensembles. Reviewer Varw has mentioned this perspective, and I hope you can check his/her comment: The main weakness of this work is lack of theoretical support and practical implications. However, I acknowledge that these are the same limitations that are attributed to LMC in neural networks, which is a significantly more broad and well-studied field than LMC in tree ensembles. I hope that future work will address these disadvantages in some way. .

As shown in equation (5), soft tree ensembles and MLPs share fundamental similarities. Therefore, a deeper understanding of soft tree ensembles could also lead to a better understanding of neural networks.

[1] Ainsworth et al., Git Re-Basin: Merging Models modulo Permutation Symmetries, ICLR2023

[2] Imfeld et al., Transformer Fusion with Optimal Transport, ICLR2024

[3] Ito et al., Analysis of Linear Mode Connectivity via Permutation-Based Weight Matching, arXiv 2402.04051

Thank you for your rebuttal, it clarified some of my questions. I will keep my score and here is my justification for it:

About sufficient contribution

I still tend to think that the discovery of weights invariances influencing LMC is not a significant contribution by itself.

Firstly, it is intuitive without any analysis: instead of computing the barrier between two fixed models, you are allowed to permute one of them before that. The bigger the set of permutations you consider, the higher the probability of finding a model that will have a lower barrier than the first one.

Secondly, in [1] it has already been supported by extensive numerical experiments.

I also want to note down, that of course, permutation search space is enormous in general, and I agree that the current paper did a good job in reducing this search space for the soft trees, but I don't think that it is enough for a paper.

Example with ReLU

I am not sure that scaling invariance for ReLU is a relevant example, because it is applied to layer outputs, not to model parameters.

About empirical analysis

In my original review, I did not mention some of the points below, because I was confused by some results and also missed some of them, for that I am sorry.

• Almost no ablations are made (e.g. for the size of the ensemble).
• In general, instead of a more detailed analysis of different cases, authors often average accuracy across all 16 datasets losing a lot of information.
  • For example, the authors do not explain why and when the interpolated model has higher accuracy than the models it is interpolated from (e.g. for MagicTelescope it happens but for bank-marketing it does not in Figure 5) - this explanation is crucial as model merging is the main application of this paper.
  • There is no explanation of when a barrier between models exists (e.g. it exists for Bioresponse, Higgs, eye_movement in Figure 5).

About questionable results

I find results strange in general and I am not satisfied with authors explanations for the reported numbers:

• 2 layer MLP performs worse than 1 layer MLP in Table 2.
• Decision list while being a version of a tree with much fewer parameters (see Figure 4) performs on par with the full version (see Table 3, 4).

It shows that datasets used for evaluation are not representative, because they can be solved already by 1 layer MLP and decision list. That leads me to the problem of too simplistic datasets.

Too simplistic datasets

The selected set of datasets for experiments is different from the ones used by the soft trees community, for example, why were not Yahoo, Click and Microsoft used (see e.g. Table 5 in [2]). I think using such datasets is important for validating LMC hypothesis on a more realistic scale of at least 500K samples (in contrast to 14/16 datasets from your paper having less than 100K samples - see Table 5).

I must admit that Higgs dataset was used as well as in [2], but I have two questions regarding it. Firstly, why does it have 940K samples (see Table 5) but in [2] it has 10.5M samples (see Table 5 in [2]). Secondly, whya your models exhibit accuracy of 66% (see Figure 5 for Higgs) while in the paper from 2020 they achieved 76% (see Table 1 in [2])? Does it mean that models are undertrained?

About paper structure

Even though authors considered these points as minor, I think that they are important and require a major rewriting of the paper:

• Main parts of matching proposed in this paper are not explained in the main text: algorithms for weights and activation matching are hidden in Appendix, linear assignment problem (LAP) is not formulated at all (in [1] it was stated in eq. 1).
• Related work section does not exist.

Soft tree can be seen as hierarchical mixture of experts

I think that it is a huge stretch. Can we say that boosting algorithms are instances of hierarchical mixtures of experts and studying them helps improve Mistral?

Question about code

According to the checklist the code is provided but I could not find it and the authors did not comment on this in the rebuttal.

[1] Ainsworth et al., Git Re-Basin: Merging Models modulo Permutation Symmetries, ICLR2023

[2] Popov, Sergei, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning on tabular data. ICLR2020

Thank you for your review.

This paper does not provide any insights into the question of LMC in neural networks, as it is exploring a totally different model. Although it is always interesting to consider LMC in another senario, I find the contribution of this paper rather insignificant and incremental, since it is basically applying the same idea of [1] to another model. I do not want to deny the author's valueable efforts in exploring symmetry in a new model and using it to achieve LMC, but I just feel that the contribution of this paper may not be sufficient for it to be accepted by this conference.

First, we would like to emphasize the importance of our research. As noted in the introduction, while soft tree ensembles are distinct from neural networks, they are also highly regarded models in their own right. Understanding their behavior is of great importance for the ML community.

Our contribution is not merely the application of the results from [1] to another model. We identify the necessity of unique invariances in the context of tree ensembles and demonstrate its importance. This perspective was previously unknown in the community. Additionally, we propose an approach to modify tree structures to adjust the number of patterns of invariance required to achieve LMC, which is an essential consideration for practical applications and this idea can be applied to other model structures as well.

While the existence of permutation invariance in neural networks was known, investigating whether considering this invariance could achieve LMC was a non-trivial question. Studies addressing this perspective have made significant impacts on the community [1]. For example, architectures like transformers, with their various modules such as attention mechanisms, have shown the importance of considering their unique invariances. This work has been highly regarded and accepted in a recent top-tier conference (ICLR2024) [2]. Moreover, reviewer Varw, who has certain expertise in LMC, also praised our contribution: Honestly, I enjoyed reading this paper. Although I am not specialized in tree ensembles, I have certain expertise in LMC, and was pleased to find that it is also relevant for DTE models. I think that this contribution is novel and significant.. This also supports the impact our research has on the community.

We believe our diverse contributions have significance that deserve the conference.

One possible direction I can suggest for the authors to enhance the current paper is, if any non-trivial theory about LMC can be made on the tree ensemble model setting, then this work will be much more exciting. The underlying reason why neural networks can be made linear connected is not yet clear, and the is hard to study due to the non-linear nature of deep NNs. If the authors can show that the tree ensemble model can be an alternative model to study LMC from a theoretical perspective, then this will make the current work more valuable and intresting.

You are right that the community currently struggles to theoretically explain why LMC can be achieved in neural networks. As shown in Equation (5), soft tree ensembles and MLPs have fundamental similarities. Thus, deepening our understanding of soft tree ensembles will simultaneously lead to a better understanding of neural networks. Our contribution enables the community to consider whether soft tree ensembles can serve as an alternative model to neural networks for studying LMC, which can serve as a milestone for future research.

[1] Ainsworth et al., Git Re-Basin: Merging Models modulo Permutation Symmetries, ICLR2023

[2] Imfeld et al., Transformer Fusion with Optimal Transport, ICLR2024

After reading the rebuttal provided by the authors and discussing with other reviewers, I decide to raise my rating to this paper to borderline reject, for the following reason:

1. Previously, I didn't think it is very meaningful to explore LMC on DTE, but that I'm not interested in DTE does not mean other researchers are not interested in it, and those who are working on DTE might feel excited about this work.
2. The techniques and findings of this paper can be helpful to future researchers in this field.

I decide to maintain my opinion in the negative side because in my view this paper is still relatively incremental and contributes very little the core issues of LMC.

Thank you for your review.

I am not familiar with differentiable tree ensembles, therefore, I would suggest the authors put more efforts on explaining tree ensembles and illustrating the invariances.

Thank you for your comment. We will include an explanation with diagrams similar to Figure 1 in [1] in the Appendix of the camera-ready version. Please note that the paper is self-contained, with all definitions provided. There is already a diagram regarding invariances; please see Figure 2.

Another concern is about the motivation. This study is motivated by the question "Can LMC be achieved for soft tree ensembles?" but why would we achieve LMC for the tree ensembles? I would expect more elaboration on the motivation.

As stated in the introduction section, achieving LMC justifies the non-trivial phenomenon that model training consistently succeeds despite non-convex optimization nature. Additionally, it enables the application of model merging. These theoretical and practical aspects motivate the investigation of LMC for various models including soft tree ensembles. These aspects are also highlighted as motivations in existing LMC studies like [2].

The soft tree is a model used in typical supervised learning that is distinct from neural networks, particularly noted for its application to tabular datasets. Soft trees have gained attention for combining the interpretability and inductive biases of decision tree ensembles with the flexibility of neural networks. As a result, they are implemented in well-known open-source software, such as PyTorch Tabular [3], highlighting the importance of deepening our understanding of this model. We plan to add this information in the introduction of the camera-ready version.

[1] Frosst and Hinton, Distilling a Neural Network Into a Soft Decision Tree, CEX workshop at AI*IA 2017 conference

[2] Ainsworth et al., Git Re-Basin: Merging Models modulo Permutation Symmetries, ICLR2023

[3] Manu Joseph, PyTorch Tabular: A Framework for Deep Learning with Tabular Data, arXiv 2104.13638