Generative Forests

Summary

This paper proposes a generative model for tabular data based on a forest of trees. It is evaluated on the quality of the generated samples (using an optimal transport based distance to a held out test set), on data imputation and density estimation.

Strengths

Generative modeling for tabular data is an important research topic, and exploiting the strengths of trees (ubiquitous in this modality) for this generative task is a promising direction. The framework inherits the flexibility of boosting, and the theoretical results (under weak learning assumptions) provide guarantees that the underlying distribution can be approximated well enough with enough trees.

Weaknesses

Further empirical comparison could be conducted. For example, recent works have applied diffusion for tabular data (Kotelnikov et al.) as well as flow matching (Jolicoeur-Martineau et al.). It might be worth comparing to these more recent approaches. Furthermore, more metrics could be included for the LifeLike experiment to provide more nuanced results. See Jolicoeur-Martineau et al. for examples of such metrics. References: Kotelnikov, A., Baranchuk, D., Rubachev, I., & Babenko, A. (2023, July). Tabddpm: Modelling tabular data with diffusion models. In International Conference on Machine Learning (pp. 17564-17579). PMLR. Jolicoeur-Martineau, A., Fatras, K., & Kachman, T. (2024, April). Generating and imputing tabular data via diffusion and flow-based gradient-boosted trees. In International Conference on Artificial Intelligence and Statistics (pp. 1288-1296). PMLR.

Questions

What is the computational cost for training and inference compared to Generative Trees? (It would be interesting to provide wall-clock times) How are the parameters chosen (number of trees, number of splits, ...)?

Rating

7

Confidence

1

Soundness

3

Presentation

3

Contribution

3

Limitations

See questions

Summary

This paper introduces generative forests (GF), a new class of generative models designed for tabular data and based on sets of trees (forests), and a training algorithm called GF.BOOST. The algorithm is designed to be simple, making it easy to implement with minor modifications to existing CART-style decision tree induction schemes. The GF models and GF.BOOST algorithm are evaluated across various domains, demonstrating their capability in tasks such as data generation, missing data imputation, and density estimation. The results show that even a small number of trees within a generator can be effective, highlighting the potential of the proposed approach in handling tabular data.

Strengths

- I believe the paper is a nice addition to the ML community. Prevailing methods in data imputations for DTs are based on heuristics and tricks, whereas this paper approaches this problem with sounding probabilistic point of view, which makes a lot of sense to me. This naturally leads to the ability of generating more data, which may have serious implications in synthetic data generation literature. - The method is relatively easy to implement and can be done by straightforward extension of CART-style tree induction methods.

Weaknesses

- Experiments section may need some improvements: - Most datasets in Table 2 (which seem to be the main results table) are standard ML benchmarks. It would be really nice to have real-world kaggle-style datasets with missing values and compare with strong baselines therein. - Adding traditional forests is also necessary to compare against established methods (xgboost, lightgbm, etc.) - I find most of the math notations hard to follow and can be significantly simplified.

Questions

- How computationally efficient to compute Eq. 4? From my understanding it is used for splitting a tree - Is there any mechanism to prune some trees in a forest (reduce T)? Traditional tree boosting builds trees sequentially, so there is opportunity for early stopping. I was wondering how critical here to have predefined T... - Is there any separate ablation how well this method works for categorical features?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

- there seems to be some limitations in convergence analysis (e.g. symmetry of l). - otherwise, having separate (sub)section on limitations would be nice (e.g. runtime compared to traditional boosting methods).

Summary

The paper proposes a generative model based on an ensemble of trees (forest) for tabular data. The proposed model enjoys the following peculiar properties: 1. Compared to generative models based on a single tree, it offers improved **expressiveness** in terms of partitioning the input space (linear for generative trees vs. polynomial for generative forest in terms of decision nodes in a tree). 2. The model offers **unbiased** density estimation for sufficient large capacity, thanks to the fact that each node in each tree leverage decisions in proportion to the empirical distribution. 3. Learning the structure of the trees is performed by minimizing an objective function based on the likelihood ratio risk. 4. Computationallly speaking, data generation and density estimation can be performed in **parallel** with respect to the different trees. Indeed, results can be aggregated a posteriori by taking the intersection of selected regions. 5. Apart from **data generation** and **density estimation**, the model can be extended to deal missing data and perform **data imputation**. Experiments are conducted on a series of tabular datasets from the UCI repository. The proposed solution is shown to outperform/being on par with existing tabular data generation (the most relevant being adversarial random forests), data imputation (e.g. MICE) and density estimation baselines (e.g. kernel density estimation).

Strengths

1. The problem of learning a good generative model for tabular data is relevant **Relevance** 2. The solution based on a tree ensemble represent a significant advance over solutions based on a single decision tree **Significance**. 3. The proposed model offers the possibility to tackle three different tasks, including density estimation, data generation and data imputation. Moreover, experiments demonstrate the efficacy of the solution when compared with corresponding baselines for each task **Significance**. 4. The theory of the paper seem correct, however I haven’t gone through the proofs **Correctness** 5. Code is available at the time of submission. No additional check has been conducted to verify the reproducibility of the results **Reproducibility**

Weaknesses

1. One of the major concerns is with the novelty of the proposed solution **Novelty**. What is the relation with the work in [1]? The work in [1] is also providing a model able to tackle the three above-mentioned tasks. Would it be possible to provide a comparison? 2. The paper is sometimes overloaded by unnecessary formalism, rendering the text hard to follow **Clarity**. For instance, 1. Line 92-109, why is the whole theory about risk minimisation for binary classification introduced, when the goal is to perform density estimation? Would simple likelihood learning suffice? 2. Definition of tree. “…labeled with subsets of their tail node’s variable domain”. Do you mean “”labeled with subset of attribute value for the corresponding variable? 3. Line 160-163. Can you make an example or in case leave out the sentence? Am I correct to say that the permutation invariance property is due to the final intersection operation or am I missing something? 4. Algorithm 3 in Step 2.1 How is node selection performed, uniformly at random? Moreover, can you provide some more details about the resulting trees, are they balanced? 5. Can you elaborate on the motivation of proving theorem 5.2 and discuss the significance of its results or link with the results in the experiments? 3. All experiments are conducted on datasets with less 34 variables **Soundness**. Would it be possible to provide some comparisons with [1] on larger dimensional datasets (see the reference for example) and/or discuss the computational requirements? **Reference** [1] Generating and Imputing Tabular Data via Diffusion and Flow-based Gradient-Boosted Trees. AISTATS 2024

Questions

Overall, I like the extension of generative trees to ensembles. I’m willing to raise my score if all weaknesses are addressed during the rebuttal phase.

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

3

Limitations

There are no additional suggestions.

Summary

The paper presents a novel boosting algorithm based on ensembles of generative trees, addressing tasks such as data binary classification, missing data imputation, and density estimation. The proposed algorithm optimizes specific loss functions and leverages the structure of the models to efficiently estimate densities given a generative model and partially specified observations. The authors demonstrate the practicality of their approach through comprehensive experiments, highlighting its effectiveness in binary classification compared to diverse state-of-the-art methods, including their competitors like Adversarial Random Forests (ARF), CT.GAN, Vine copulas auto-encoders (VCAE) or Kernel Density Estimations(KDE). The authors introduce a unique training methodology for these generative models, which is based on class probability estimation (CPE) in binary classification tasks. The loss functions are decomposed into partial losses for positive and negative classes, with the Bayes risk function defined as the optimal achievable loss given a certain positive base-rate. Properness and strict properness of the loss functions are critical properties, ensuring that the loss is minimized when the predicted probability matches the true class probability. The paper discusses various proper losses, such as square loss, logarithmic loss, and Matusita's loss, which are symmetric and differentiable. Furthermore, the paper explores loss functions in the context of density ratio estimation and introduces the likelihood ratio risk for assessing the performance of generative models. Using Bregman divergence and the generalized perspective transform, the authors propose a framework for evaluating the density ratios of different distributions. This theoretical foundation supports the practical applications of their models, which show competitive performance over the dataset proposed. The authors carried out experiments on a total of 21 datasets from sources such as UCI, Kaggle, OpenML, and the Stanford Open Policing Project, or simulated datasets. These include datasets like iris, ringGauss, gridGauss, forestfires, tictactoe, ionosphere, student performance, winered, abalone, kc1, sigma-cabs, compas, artificial characters, jungle chess, open-policing-hartford, and electricity, with varying attributes and missing data conditions. The paper concludes that their models, trained with the novel generative tree algorithm, are strong contenders against existing state-of-the-art techniques.

Strengths

Regarding to the originality, the paper introduces a novel approach to generative modeling by creating a generative forest based on Class Probability Estimation (CPE). This method represents a significant advancement over current state-of-the-art algorithms. By leveraging ensemble methods and decision tree induction for generative tasks, the paper presents a fresh perspective that has not been extensively explored in the literature. The combination of well-known techniques in a new context adds substantial value to the field and showcases the authors' innovative approach to generative modeling. The quality of the submission is commendable. The paper is well-organized and meticulously indexed, with a comprehensive appendix that supports the main content. The methodology is robust, encompassing a detailed mathematical explanation, pseudocode for the proposed algorithm, and extensive experimental validation. The authors have tested their model on 21 diverse datasets from reputable sources such as UCI, Kaggle, OpenML, and the Stanford Open Policing Project. This thorough evaluation across various tasks, including data generation, missing data imputation, and density estimation, provides strong evidence of the model's performance and versatility. Additionally, the paper continues the line of research in generative models, building on previous work and demonstrating significant progress in this domain. The paper is clearly written and well-organized, ensuring that readers can easily follow the authors' reasoning and methodology. The detailed descriptions of the mathematical foundation, the pseudocode, and the experimental setup are particularly noteworthy. These elements allow that an expert can reproduce the results. Furthermore, the inclusion of a comprehensive appendix adds to the clarity by providing additional details without cluttering the main text. The results presented in the paper are of high value. In that line, the authors have made a commendable effort by comparing their method with the closest approaches (ARF, copycat) cited in [42] and [29]. Furthermore, they have clearly outlined the distinctions and enhancements of their algorithm in comparison to these approaches. The authors suggest that generative forest can effectively eliminate "the slack" when utilizing decision trees as discriminators. This implies that decision trees exhibit a more regulated and foreseeable behavior in contrast to neural networks. Decision trees are inherently more calibrated and provide more deterministic outcomes. As a result, the feedback they provide to the generator during training is more accurate and reliable. The proposed method seems to enhance binary classification performance compared to existing approaches and also addresses challenging tasks such as missing data imputation and density estimation. The model's ability to produce competitive results across a diverse array of datasets and tasks underscores its potential impact on both the research community and practical applications.

Weaknesses

In section 1, the authors delve into the use of generative AI in the ML community and highlight two significant features of their generative forest. They emphasize its simplicity and the strong convergence guarantees it offers in a weak/strong learning model, akin to Valiant’s PAC learning boosting model. However, it remains unclear whether this generative forest, based on Class Probability Estimation (CPE), can effectively handle multiclass scenarios. Section 3 introduces the supervised loss for the generative tree. Nevertheless, from a synthesized perspective, the drafting in line 75 lacks clarity. The authors should consider enhancing the clarity of these lines. Moving on to Section 4, in line 125, the authors refer to 'c', but it is not clearly connected to the context provided in the text. Regarding the supplementary material, Table A3 is challenging to read as the footnotes overlap with the image.

Questions

In Table 2, the final row displays the wins and losses for us. I am not closely following the numbers as you have already chosen the green one, which includes p-values indicating significance. Another query pertains to comparing the number of trees. It seems unfair to compare T=500 with competitors having fewer trees (10, 50, 100, 200). In simpler terms, I coudn’t comprehend why you mentioned that all these approaches rely on models that are vastly distinct from each other. I know that in the article the authors mentioned that ARFs are trained with a varying number of trees T ∈ {10, 50, 100, 200}. Additionally, ARFs incorporate an algorithm for tree size selection, eliminating the need for manual selection. On the other hand, CT-GANs undergo training with a different number of epochs E ∈ {10, 100, 300, 1000} but I don't follow why these models are then compared with generative forests comprising T = 500 trees and trained over a total of J = 2000 iterations. That approach was done for Table 2 and 4.

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

4

Limitations

The work presented by the authors is highly promising since they have introduced a novel methodology for constructing generative tree models based on class probability estimation (CPE) as a loss function in binary classification tasks. However, the paper would benefit from a dedicated section discussing the current limitations of this method. Specifically, it would be useful to understand whether this approach can be applied with the same efficacy to multiclass classification or, with some modifications, to regression tasks. Additionally, it would be valuable to identify the types of tabular data that the proposed method might struggle with or the conditions under which its performance may be suboptimal. For instance, are there specific data types or distributions where this model does not perform as well? A thorough examination of these aspects could enhance the article. Moreover, while the authors have laid a strong foundation for binary classification problems in their work, constructive suggestions for improvement include providing an analysis or discussion on how the current method could be extended or adapted to handle multiclass classification tasks or regression problems, which would be helpful. In that line, another interesting thing could be identifying the specific types of tabular data that might present challenges for the proposed method, which would be beneficial. Under what conditions does the model's performance decline, and what are the characteristics of datasets where this approach is less effective?

Summary

The authors introduce a novel generative model (Generative Forests - GF) for sampling and density estimation, leveraging an ensemble of trees. Their method partitions the input domain by considering all possible intersections of the supports of the leaves across the ensemble, resulting in a much finer partitioning than a single tree could achieve. For each subset of the input domain thus obtained, the model estimates a uniform density based on an empirical training measure. Efficient algorithms for sampling from such a model and evaluating the densities are derived. To train the model, the authors propose an algorithm that iteratively splits a selected leaf node in one of the ensemble's trees. This splitting is guided by minimizing a strictly proper loss for a binary class probability estimation task. The authors evaluate their method's performance against competing approaches across three main dimensions: the quality of synthetic data generation, missing data imputation, and density estimation.

Strengths

- I find that the paper reads resonably clearly. The language and notation used throughout the paper is very precise although it occasionally appears overly complex. - The proposed method is interesting and I believe enjoys reasonable novelty. - The method and theoretical results all appear to be sound. - The proposed method's ability to estimate densities makes it more versatile than other generative methods commonly used for tabular synthetic data generation. Few methods can match its generality in handling various types of tabular data, except for other tree-based methods like Adversarial Random Forests (ARF). In this context, the positive results presented in comparison to ARF are promising. - The authors have made their implementation code available.

Weaknesses

While the authors adequately explain their ensemble tree-based model and its sampling and density computation methods, the explanation of the training algorithm is less thorough. There is insufficient discussion on how the method scales computationally with the number of trees and splitting iterations (see my first question). Additionally, more discussion on the motivation behind the formulation of the CPE task would be welcome. According to the paper's Lemma 4.4, GF estimates a different density value at each non-empty intersection of the supports of each leaf, derived directly from the empirical training measure. This is similar to ARF or other works such as [1] or [2] when using uniform densities at the leaves with the exception that these methods would output an averaged density estimated independently from leaves of each tree in the ensemble. It is unclear why the proposed approach should be better. From a generalization perspective, I would intuitively assume that averaging densities from multiple trees has a regularizing effect compared to using a single tree (see [2]). On the other hand, GF's density estimation is based on a finer partitioning, whose cardinality grows with the product of the depths of all trees in the ensemble. While this could providing greater representational capacity, it would seem to make the method more susceptible to overfitting. The theoretical analysis provided also focuses only on approximating this empirical training measure, without addressing overfitting and the approximation of the data-generating measure. For a model such as described above, it seems obvious that the less coarse the partitioning becomes, the more faithfully an empirical distribution can be approximated. I am therefore unsure of the practical significance of these results and I think the paper would benefit more from a discussion of generalization ability. My main concern with the paper, however, lies with the evaluation and comparison to other methods: - For the many analyses presented in the main paper and the appendices, different methods are compared against and for each method/scenario combination different datasets are used. This lack of consistency in comparisons and datasets in the presented results, leaves an impression that results are missing. - The choice of datasets focuses on relatively small numbers of data points and mixes both synthetic toy data and real datasets together. This is compounded by some of the main results being presented only as summary data (#wins/#ties/#losses) over this heterogeneous group of datasets. - There is no serious attempt to compare the proposed method with state-of-the-art approaches for synthetic data generation, particularly neural network-based ones: - The comparison is limited to CT-GAN, which has been shown to underperform almost every other popular neural network method, including the TVAE method put forward as a baseline in the same paper. - Additionally, the authors do not tune any hyperparameters for CT-GAN beyond the number of epochs. As a GAN, CT-GAN can have convergence issues, and without proper tuning, it may fail to converge. This lack of tuning undermines the fairness of the comparison, especially since it is unclear how much the authors optimized the hyperparameters of their own method. - The authors also report unusually long training times on a very small dataset, presumably because no GPU is used to train these models and possibly training for too long to no avail. While I understand that the proposed method can be trained on a CPU alone, and maybe that is the point being made, I don't think this remark is made in good faith. In my experience, methods like CT-GAN, TVAE, and TabDDPM can achieve reasonable performance quickly (within minutes to tens of minutes) when trained on a consumer GPU (e.g., 2080) even on larger datasets than those used in the reported experiments. - Results for CT-GAN on the two larger datasets are not reported, so the comparison primarily relies on very small datasets where neural networks might perform worse. A comparison with TabDDPM [3], a strong neural network-based generative method, would be valuable, as it is currently a standard benchmark in papers evaluating synthetic data and, in my opinion, a consistent contender for a state-of-the-art method. - The evaluation of generated samples relies solely on an Optimal Transport distance metric. Although I am not well-versed in the practical computation of this metric, the authors' comment about selecting an entropic regularization parameter that avoids numerical instabilities across all domains is not particularly reassuring. It raises the question of why other metrics were not used in conjunction. - Additionally, the setup described by the authors (GEN-DISCRIM), which uses Random Forests to distinguish real from synthetic data, appears both reasonable and well-founded. I am curious why this wasn't the primary evaluation method for comparing with other approaches. Instead, it is only used to compare GF against optimistic and pessimistic baselines. - On this topic, the authors might also want ot look at e.g., [4] for utility metrics in machine learning tasks that are common in comparing synthetic data generators, although I wouldn't personally fault them if they choose to disregard such metrics. - Finally, given that the proposed model is able to estimate densities and that evaluating the log-likelihood of held-out data is the gold standard for objectively measuring the quality of such models I don't understand why this evaluation doesn't have a more prominent place in the paper: - The authors only compare their method to KDE, which GF seems to underperform on several datasets, particularly those with a moderate number of dimensions. This is concerning, and I think it is important to investigate how the proposed method scales to higher-dimensional data compared to KDE. - ARF is missing as a baseline in these evaluations which is strange since it is another model that is capable of estimating densities. Additionally, other methods, such as [2], report consistently outperforming KDE, making it worthwhile to include as an additional comparison in my view. - Finally, the evaluation setup is not throughly explained in the main paper and only summary results against KDE are presented. It seems that the authors don't always use log-likelihood to compare these models due to their proposed model predicting 0 density for test samples (see question 3 below). This issue is only mentioned in the appendix but should, in my view, be disclosed in the main paper. [1] Alvaro H. C. Correia, Robert Peharz, Cassio de Campos. Joints in Random Forests, 2020 (https://arxiv.org/abs/2006.14937) [2] Hongwei Wen, Hanyuan Hang. Random Forest Density Estimation, 2022 (https://proceedings.mlr.press/v162/wen22c.html) [3] Akim Kotelnikov, Dmitry Baranchuk, Ivan Rubachev, Artem Babenko. TabDDPM: Modelling Tabular Data with Diffusion Models, 2022 (https://arxiv.org/abs/2209.15421) [4] Lasse Hansen, Nabeel Seedat, Mihaela van der Schaar, Andrija Petrovic. Reimagining Synthetic Tabular Data Generation through Data-Centric AI: A Comprehensive Benchmark, 2023 (https://arxiv.org/abs/2310.16981)

Questions

1. In line 218 the authors mention regarding finding the optimal split in $\text{splitPred}$ that "the optimisation is no more computationally demanding" than for decision tree induction. I'm not sure if this is a typo but it seems to me that, as the trees in the ensemble grow deeper, finding the best split could quickly become intractable. As an example, in the case where only single stumps are used, the potential cardinality of $\mathcal{P}(\mathcal{T})$ at iteration $j$ is $2^j$ which means that intersections with that many subsets have to be considered when finding the best split point. This seems like an untenable scaling of the computation with the iteration number but maybe I am misunderstanding something about how the best split is selected as the authors' explanation is not clear. 2. Regarding density modelling the authors only compare with KDE. Since ARF also provides density estimates why not compare against this method as well? Additionally [2] could also be worthwhile comparing against. 3. Could the authors clarify what they mean by "expected densities" that are used "to cope with the eventuality of zero (pointwise) density predictions" in appendix section V.V.3.7? If their proposed model assigns 0 probability to a subset of the domain that has non-zero mass under the data generating distribution I would say that this is a defect of the model and a sign of poor regularization. Changing from the commonly used log-likelihood metric to one that doesn't penalize this so harshly should be surfaced and discussed in the main text in my opinion. Furthermore, it seems that this choice is made on a dataset-by-dataset basis, I can only assume depending on whether the proposed model yields $-\infty$ log likelihoods which seems to happen for most non-toy datasets. As it stands, these details are hidden in the appendix while the main paper presents a potentially misleading picture based only on #wins. 4. Still regarding 0 density predictions, the authors propose a way to avoid this issue for GFs in line 173. It would be interesting if this was explored further and the resulting (more regularized) density model compared to other approaches for density estimation based on log-likelihood. [2] Hongwei Wen, Hanyuan Hang. Random Forest Density Estimation, 2022 (https://proceedings.mlr.press/v162/wen22c.html)

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

3

Limitations

I find that the authors hardly discuss the limitations of their method. Most importantly there is little discussion of training times and how they scale with the number of iterations/data dimensions/number of samples. There is also no discussion of how performance and generalization is expected to scale with these factors.

Sincerer apologies for "Official Comments" not visible for tag finding -- now fixed

In our rebuttals to reviews uJTo and 6MHb, we provided tags pointing to Official Comments we lodged to reviewer kTDz. After double checking, we realized those Official Comments were visible only to reviewer kTDz. We have hopefully fixed the problem and all tags should now be visible. We sincerely apologize to reviewers for this mistake in lodging those.

Thank you for your response

Dear Authors, Thank you for your detailed response. I'd be happy to see the results against Forest-Flow if the other reviewers also agree.

Additional Questions

Dear authors, Thank you for the answers, that have addressed some of my concerns about clarity. There are still a number of questions that I would like to see addressed and that refrain me to raise the score, also in light of the other reviews. **Novelty** While it is clear the difference between the proposed solution and Forest-Flow from a model perspective, I don’t understand the difference in terms of properties, especially regarding generalization (as also pointed out by reviewer kTDz). Firstly, Theorem 5.2 provides a result about the weak monotonic reduction on the density distance. Since the reduction is not strict, how do you ensure that the learnt model is unbiased? Secondly, does the mentioned consistency property imply that Forest-Flow is biased, whereas Generative Forests is not? As far as I understand, training Forest-Flow reduces the distance between the model and the empirical data distribution leveraging standard KL divergences through an ELBO-like formulation. Consistency results clearly hold in the infinite sample regime and for sufficiently large network capacity. Can you please clarify this aspect? **Clarity** It is mentioned that during learning, leaves with largest empirical mass are selected among all trees. How does this ensure that learning is unbiased as uncertainty is not taken into account? Moreover, how does this criterion influences the topology of the trees, are they balanced? Can you provide some synthetic visualisations on the convergence results of Theorem 5.2 and the benefits of the strict properness property against other common generative losses, such as KL divergence? This could help to add value my making the concepts clearer. From an implementation perspective, how are the different trees initialised and how is diversity across trees ensured throughout learning? **Experiments** Comparison results against Forest-Flow are promised, but it is not clear whether they will be released during the discussion phase or afterwards. Providing these during the discussion phase could definitely help in the decision.

[Exp-0] Explanations related to Experiments [Exp-1], [Exp-2] and [Exp-3] (summary: more contenders, more metrics)

This Comment addresses the following reviewers' requests: - uJTo: request to compare vs Forest-Flow - Sk9u: request to compare vs Forest-Flow - kTDz: points (1) (Jolicoeur-Martineau et al. substantially beat TVAE and CATB-GAN) and (3.2) (more evaluation metrics, time), request to compare vs ARF on new metrics We use the shorthands for papers: [jfkGA] A. Jolicoeur-Martineau, K. Fatras and T. Kachman. Generating and imputing tabular data via diffusion and flow-based gradient-boosted trees. AISTATS24 [noucyRF] M.F. Naeem, S.J. Oh, Y. Uh and Y. Choi. Reliable Fidelity and Diversity Metrics for Generative Models. ICML20 For the data generation experiment, [Exp-1] and [Exp-2] provide experiments vs Forest Flow or (non exclusive) on new metrics. **Forest-Flow**: we used the R code provided in [jfkGA], run on the same machine we ran our experiments (the Laptop). Parameters were set following the default values in https://htmlpreview.github.io/?https://github.com/SamsungSAILMontreal/ForestDiffusion/master/R-Package/Vignette.html. We also followed the recommendation that fixing 50 trees per XGBoost model led to state of the art performances [jfkGA, Section 3.2]. With trees of depth at most 7, this represents a maximum number of $J=$6 750 splits per model used. Times displayed are times to learn a model on each fold. Forest-Flow requires numerically reencoding domains with categorical/text values and all our contenders used so far process our domains "natively", without reencoding. To avoid encoding bias affecting results, we have run Forest-Flow on the fully numerical domains of our benchmark (also, the computation of some of our new metrics is better suited to fully numerical domains). This included domains with binary outcomes encoded as 0/1. **CT-GAN**: we considered the domains in the intersection of Table A6 and those we used for Forest-Flow. **ARF**: we considered the domains in the intersection of Table 2 and those we used for Forest-Flow. **Metrics**: we added three metrics to our synthetic data generation experiment: - The Coverage and Density metrics from [noucyRF], which present better alternatives to precision and recall for generative models evaluation. We computed those metrics following the paper, using the training / test samples as built from our experiments; In the $k$-NN rule, we picked $k=5$ following suggestion in [noucyRF, Section 3.4]. - The F1 metric from [jfkGA], which if $F1_{disc}$ in their experiments. Since our domains are fully numerical, we used for prediction a $k$-NN rule with the same $k$ as in our Coverage + Density experiment. We also ran those metrics on our full set of experimental results of CT-GAN and ARF. We only provide the results for 1000 epochs for CT-GAN and $T$=200 trees for ARF for readability but we have computed all other results as well (as in Tables 2 and A6). The parameters we fix for our models are the same as in our submission ($T=500, J=2000$ as in Table 2, $T=200, J=500$ as in Table A8). Discussion: - vs Forest-Flow: there seems to be two different behaviours. On "small" domains ($m\times d$ small, $d$ small, our simulated domains), there is a slight tendency for our method to beat Forest-Flow on Sinkhorn, Coverage and F1 whereas the tendency is reversed for Density. On larger domains (e.g. artificial_characters, $m \times d$>80K), it seems we do significantly beat Forest-Flow by large margins (p<0.01 for most metrics, even with our small models). Also, execution times are slightly at our advantage (more if we consider our smallest models). Caution advised for comparing times since Forest-Flow is implemented in R and our code is in Java. - vs CT-GAN: we had to remove artificial_characters from our benchmark because of issues with CT-GAN (Table A6 in our paper). We also do not report times for comparison because the algorithms were ran on different computers. The conclusion follows the broad lines of our conclusion in our paper with the additional metrics we have considered. - vs ARF: the picture resembles that of Table 2 when we traing our GFs with $T$=500 trees (we significantly beat ARF on >1/3 of the cases and are never statistically significantly beaten). When reducing the number of our trees to $T$=200, we still observe that our models beat GFs in many cases (statistical significance on 5 of them).

[Th-0] A consistency result for our models / setting

This Comment addresses the following reviewers' requests: - uJTo: comments on ``Novelty'' - kTDz: review on the need to discuss generalization ability and our reply [kTDz-A2] We use the shorthands for papers: [cpdJI] A.H.C. Correia, R. Peharz and C. P. de Campos. Joints in Random Forests. NeurIPS 2020 [llmDT] J.S. Leboeuf, F. LeBlanc and M. Marchand. Decision trees as partitioning machines to characterize their generalization properties. NeurIPS 2020 [lnCO] G. Lugosi and A. Nobel. Consistency of Data-driven Histogram Methods for Density Estimation and Classification. Ann. of Stats. 1996 We provide a consistency result of exactly the same nature as [cpdJI, Theorem 2]. Like in [cpdJI,lnCO], we assume for simplicity that the domain is $R^d$. Hereafter, the size $|\Upsilon|$ of a (binary) tree $\Upsilon$ is its whole number of nodes. A key feature of our models that allow us to branch directly on the proof of strong consistency of [lnCO] is that a GF has density equal to the empirical density measured in each bin of the partition it induces. In [lnCO]'s notations, this is the empirical histogram $f_n$. We need one Lemma that connects our GFs with classical binary trees. **Lemma A** The partition achieved by a GF with trees $\Upsilon_1, \Upsilon_2, ..., \Upsilon_T$ can be achieved with a single tree $\Upsilon_*$ of size at most $\prod_i |\Upsilon_i|$. **Proof** the proof is simple and constructive. Suppose without loss of generality that $T=2$. Add one copy of $\Upsilon_2$ at each leaf of $\Upsilon_1$. The partition generated is exactly the same as that of the GF (L128-L129) and the size of this tree is no more than $|\Upsilon_1| \cdot |\Upsilon_2|$. The construction generalizes to more than 2 trees [end of the proof of Lemma A]. Suppose without loss of generality that all trees have the same size, $N$, so that $|\Upsilon_*| \leq N^T$. Like in [cpdJI,lnCO], proving consistency involves computing and bounding a combinatorial parameter function of the model class, the growth function $\Delta^*$ (See Definition 1 in [cpdJI] or Section 2 in lnCO]). Lemma A tells us that the growth function of the trees in a GF is bounded by that of a tree partitioning the domain. Proposition 2 in [cpdJI] bounds the growth function for any such tree. The VC dimension of size-$N$ decision trees is $O(N \log N)$ [llmDT]. Using [cpdJI], we obtain from Sauer's Lemma the bound $\Delta^* \leq m^{CN^{2T}\log N}$. There are three conditions to get to strong consistency in [lnCO] (Theorem 1). Condition 2 reads $(1/m) \log \Delta^* \rightarrow 0$ (as the training size $m \rightarrow +\infty$). To satisfy Condition 2, we thus need our models parameters to vanish as a function of $m$, namely $N_m^{2T_m}\log N_m \rightarrow 0$ (indexes are used as in [cpdJI] to indicate the dependence of model parameters in $m$). This is similar to condition i) in [cpdJI, Theorem 2]. Condition 1 imposes that the maximal empirical mass in one element of the partition must also manish with $m$. In our case, it is guaranteed by our condition (c) in our weak learning assumption and the fact that our algorithm splits the heaviest leaf at each iteration. Condition 3 imposes that the true mass in any ``big'' element of the partition must also vanish with $m$. This is also condition ii) in [cpdJI, Theorem 2] (our formulation would be no different. We spare the reviewers with additional notations). [Consistency result 1] Hence, we are able to prove, under the same conditions as Theorem 2 in [cpdJI] that, with our notations and those of [lnCO], $\int |{\color{red} R}(x) - {\color{blue} G}(x)|dx \rightarrow 0$ with probability 1. (the statement + explanations can fit in 1/2 page; the proof could go in appendix)