RashomonGB: Analyzing the Rashomon Effect and Mitigating Predictive Multiplicity in Gradient Boosting

Authors: hsiang  hsu
ivan  brugere
shubham  sharma
freddy  lecue
chun-fu  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:36:58

Abstract: The Rashomon effect is a mixed blessing in responsible machine learning. It enhances the prospects of finding models that perform well in accuracy while adhering to ethical standards, such as fairness or interpretability. Conversely, it poses a risk to the credibility of machine decisions through predictive multiplicity. While recent studies have explored the Rashomon effect across various machine learning algorithms, its impact on gradient boosting---an algorithm widely applied to tabular datasets---remains unclear. This paper addresses this gap by systematically analyzing the Rashomon effect and predictive multiplicity in gradient boosting algorithms. We provide rigorous theoretical derivations to examine the Rashomon effect in the context of gradient boosting and offer an information-theoretic characterization of the Rashomon set. Additionally, we introduce a novel inference technique called RashomonGB to efficiently inspect the Rashomon effect in practice. On more than 20 datasets, our empirical results show that RashomonGB outperforms existing baselines in terms of improving the estimation of predictive multiplicity metrics and model selection with group fairness constraints. Lastly, we propose a framework to mitigate predictive multiplicity in gradient boosting and empirically demonstrate its effectiveness.

Main paper: 
 introduction: 
 Large-scale, complex data and the pursuit of superior performance in machine learning (ML) models have led to increased complexity in both the models themselves and the training algorithms [44] . As a result, it is more likely to find a plethora of distinct models, such as those found in local minima, that exhibit statistically indistinguishable performance (e.g., test accuracy) [23] . This phenomenon, known as the Rashomon effect [12] , has urged researchers to reconsider its impact on ML models when deployed in real-world scenarios [22, 10, 30, 26] .The impacts of the Rashomon effect reveals two sides of the same coin in responsible ML. On one hand, it benefits the current trend of developing algorithms that prioritize responsible ML principles beyond merely optimizing for accuracy. These principles often include interpretability [64] , causality [37] , group fairness [20] , counterfactual explanations [39] , and feature interactions [51] . The abundance of models with competing performance allows compliance with these principles without significant compromises in performance. For instance, algorithmic fairness often faces a trade-off with accuracy; the Rashomon effect allows a fairness intervention algorithm to identify a more optimal balance among models with statistically similar performance [20] . On the other hand, the Rashomon effect presents a risk to the credibility of machine decisions known as predictive multiplicity [56] , where competing models, generated by simply varying randomness 1 in the training processes, yield conflicting predictions for some individual samples. If left unaddressed, conflicting predictions can lead to discrimination and unfairness, hidden under the guise of algorithmic randomness. This can adversely affect certain individuals without revealing significant statistical differences from nondiscriminatory models [22] . The negative societal impacts of predictive multiplicity and inconsistent decisions have been recently studied under various frameworks2 such as prediction uncertainty [35, 2] , predictive churn [59, 75] , and predictive multiplicity [56, 67, 9, 42] .To understand the Rashomon effect and address predictive multiplicity, recent studies have focused on characterizing competing models and efficiently searching for them across different ML models. For instance, predictive multiplicity caused by linear classifiers can be computed via mixed integer programming [56, 74] . Competing models from sparse decision trees are exactly characterized and searched by sub-tree pruning [76] . In special cases such as ridge regression and generalized additive models, the forms of the set of competing models are analytically derived [67, 16] . More recently, test-time dropout has been utilized to search for competing models for neural networks [43] .In this paper, we focus on another ML algorithm, gradient boosting [65] , which is widely applied to tabular datasets [36] . Gradient boosting differs fundamentally from other ML algorithms in its sequential approach: rather than training a model as a single entity, gradient boosting breaks down the training process into a sequence of sub-learning problems. This sequential training pipeline not only facilitates the analysis of the Rashomon effect but also offers new methodologies for model selection and reducing predictive multiplicity. To the best of our knowledge, our work is the first to explore the Rashomon effect for gradient boosting. The main contributions of this work include:1. We formalize and investigate the Rashomon effect induced by gradient boosting, employing statistical learning and information theory to analyze its behavior (Section 3). Specifically, we leverage information-theoretic measures to characterize the impact of dataset properties on the Rashomon effect. 2. We introduce RashomonGB, an efficient method that explores an exponential search space versus baseline methods which search linearly. (Section 3.1). 3. We implement RashomonGB on several real-world (large-scale) tabular and image datasets, and empirically demonstrate the competing models obtained with RashomonGB can greatly improve the estimation of predictive multiplicity (Section 4.1), and model selection with additional responsible ML principles such as group fairness (Section 4.2). 4. We propose two methods to mitigate predictive multiplicity for gradient boosting and experimentally validate the methods on 18 tabular datasets (Section 4.3).Omitted proofs, additional explanations and discussions, details on experiment setups and training, and additional experiments are included in the Appendix. Code to reproduce our experiments can be accessed at https://github.com/jpmorganchase/Rashomon-gradient-boosting. 
background and related work: 
 Consider a dataset S = {s i } n i=1 drawn i.i.d. from P S , where each s i is a pair (x i , y i ) consisting of a feature vector x i = [x i1 , • • • , x id ] ⊤ ∈ X ⊆ R d and a target y i ∈ R. Let X and Y be the random variables for the feature x i and target y i respectively, and S = X × Y . We denote by H a hypothesis space of functions that map from X to Y. The loss function used to evaluate model performance is denoted by ℓ : H × S → R + and L P S (h) ≜ E P S [ℓ(h, S)] the population risk. As usual, the population risk is approximated by the empirical risk L S (h) ≜ 1 n n i=1 ℓ(h, s i ). We denote the empirical risk minimizer as h * = argmin h∈H L S (h) ∈ H. We denote ∇ x v(x) the gradient of v(x) w.r.t. x, and 1[•] the indicator function. For two random variables X and Y , the mutual information between them is defined as I(X; Y ) = D KL (P X,Y ∥P X P Y ) [21] , where D KL (P ∥Q) = E P [log P/Q] is the Kullback-Leibler (KL) divergence [47] . Finally, we let[k] ≜ [1, • • • , k].The Rashomon sets and exploring models therein. The studies on the Rashomon effect typically start with searching for models in the Rashomon set [67] , the set of all models in the hypothesis space H whose population risks are comparable to that of a given model3 h * ∈ H, i.e., R(H, S, h * , ϵ) ≜ {h ∈ H; L P S (h) ≤ L P S (h * ) + ϵ},where ϵ ≥ 0 is a Rashomon parameter that determines the size of the Rashomon set. However, when the hypothesis space H is large (e.g., neural network architectures, tree ensembles, etc.), exhaustively identifying all models within the Rashomon set becomes computationally infeasible. Therefore, it is customary to approximate the full Rashomon set by a subset with m models called an empirical Rashomon set, R m (H, S, h * , ϵ)≜ {h 1 , • • • , h m ∈ H; h i ∈ R(H, S, h * , ϵ), ∀i ∈ [m]}.In practice, the m models in the empirical Rashomon set are mainly obtained by re-training (See Appendix B.2 for more discussions). The re-training strategy re-trains models with different random initializations and rejects those that disobey the loss deviation constraint in Eq. ( 1) until m models are collected [67, 48] . However, re-training models repeatedly is time-consuming with large datasets or complex architectures. To improve efficiency, a recent strategy involves collecting distinct models with competing performance during the inference phase. For example, Hsu et al. [43] proposed an inference-time dropout strategy for convolutional neural networks (CNNs). Despite these advances, exploring Rashomon sets for ensemble learning methods like boosting remains unexplored.Predictive multiplicity. Predictive multiplicity undermines the credibility of decisions made by ML algorithms, making its measurement an active research area. Predictive multiplicity metrics can be categorized based on whether they are defined on output decisions (i.e., thresholded predictions/scores after argmax) or on output scores in the probability simplex. For example, ambiguity and discrepancy, measure the proportion of samples with conflicting decisions from models within the Rashomon set [56] . Disagreement, in a similar flavor, assess the probability of conflicting decisions per sample [48] . In contrast, score-based metrics estimate various aspects such as score variance/std. [52, 17, 9] , the viable range of scores (termed viable prediction range (VPR) by Watson-Daniels et al. [74] )), or score spread in the probability simplex (referred to as Rashomon Capacity (RC) by Hsu and Calmon [42] ). Due to space constraints, we defer the mathematical formulations of these predictive multiplicity metrics and discussions on estimating these metrics with the empirical Rashomon sets to Appendix B.2. These predictive multiplicity metrics are often estimated using the empirical Rashomon set R m (H, S, h * , ϵ). As m increases, the empirical Rashomon set better approximates the Rashomon set, leading to more precise estimations of predictive multiplicity metrics.Mitigating predictive multiplicity. Mitigating predictive multiplicity ensures that decisions made by ML algorithms are consistent. The main strategy for this is to combine decisions from competing models. Roth et al. [63] reconcile conflicting decisions from two different models in the Rashomon set to improve the disagreement in predictions. Combining decisions from multiple models falls under the umbrella of model averaging in ensemble learning [9, 42, 52] . Model averaging is a special ensemble learning that collects multiple base models, often referred to as weak learners, and combines them in parallel. As averaging model outputs reduces the variance, it is a natural choice for diminishing predictive multiplicity and has been reported in several studies. For instance, Black et al. [9] proposed a selective averaging that leverages certifiably-robust predictions to mitigate the problem of inconsistency with a probabilistic guarantee. Hsu and Calmon [42, Section A.4.5] observe that random forest classifiers exhibit a lower Rashomon Capacity compared to decision tree classifiers. Furthermore, Long et al. [52] demonstrate that the probability of significant deviated predictions in model averaging diminishes exponentially with the number of models in the average.Ensemble learning is not limited to parallel combinations. Another popular branch involves combining models sequentially, known as boosting algorithms. Despite the widespread use of boosting algorithms and their superior performance over neural networks on tabular datasets [36] , boosting algorithms have been mostly overlooked in the literature on the Rashomon effect and predictive multiplicity. This paper aims to address this gap, as outlined in the next section. The works most closely related to ours involve prediction uncertainty estimation in gradient boosting, such as NGBoost [27, 55] , PGBM [70] , and IBUG [13] , which consider probabilistic predictions from regression trees in Bayesian settings. However, these studies do not frame the concept of arbitrariness in predictions within the context of the Rashomon effect and may overestimate arbitrariness with models that do not have similar performance. To the best of our knowledge, this work is the first that investigates the impact of the Rashomon effect and predictive multiplicity on gradient boosting.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We include a discussion of limitations regarding theoretical extensions and computational overhead in the last section.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
analyzing the rashomon effect in gradient boosting: 
 We begin with a brief introduction to gradient boosting and discuss how its sequential combination approach can inspire a new method for finding competing models in the Rashomon set. We then provide a high-probability bound on the Rashomon set using information theory, making the first connection between the size of the Rashomon set and data quality as measured by mutual information. The proofs of the propositions in this section are included in Appendix A.Boosting algorithms select a sequence of weak learners4 , h 0 , • • • , h T ∈ H, such that the additive expansion f T (x) = T t=0 αh t (x) ∈ F with α > 0 minimizes the empirical risk L S (f T ) [34, 57, 66, 19] . Different choices of H and the method for selecting h t ∈ H have led to various boosting algorithms (see Appendix B.1). Here, our focus lies on gradient boosting [66, 34] , which starts with a constant model h 0 (x) = argmin h0∈R n i=1 ℓ(h 0 , s i ), and iteratively extends the model f t (x i ) withf t (x) = f t-1 (x) + argmin ht∈H ∥ -∇L S (f t-1 ) -h t ∥ 2 2 = f t-1 (x) + argmin ht∈H n i=1 ∥h t (x i ) -r ti ∥ 2 2 ,(2) where r ti = -∂ℓ(ft-1,si) ∂ft-1 is the pseudo-residual of sample i from weaker learner h t . Indeed, for a regression problem with a mean squared error (MSE) loss function, h * 0 = n i=1 y i /n and r ti = 2(y if t-1 (x i ))-the part of the y i that cannot be explained by the current model f t-1 (x i ). For a binary classification problem with a cross-entropy (CE) loss,h * 0 = log n i=1 1[y i = 1]/ n i=1 1[y i = 0],and can be understood as regression on the log-likelihoods. We set α = 1 in this section for the sake of theoretical analysis. For the convergence and consistency analysis of gradient boosting, see, e.g., Zhang and Yu [79] and Telgarsky [71] .The iterative training procedure of gradient boosting in Eq. ( 2) allows us to convert the original learning problem min f ∈F L S (f ) into a sequence of learning problemsmin ht∈H L St (h t ), for t ∈ [1, 2, • • • , T ],where S t = {(x i , r ti )} n i=1 . In other words, the weak learner h t aims to fit the pseudoresiduals in each iteration, and inducing a residual Rashomon set (cf. Figure 1 ),EQUATIONwhere h * t is any given model such as the empirical risk minimizer in each iteration. Eq. ( 3) suggests an alternative to building the entire Rashomon set R(F, S, f * T , T ϵ) by iteratively building the residual Rashomon sets for each iteration, i.e.EQUATION) Eq. ( 4) comes from the fact that, for classification tasks, gradient boosting actually performs a regression on the log-likelihood using the MSE loss. The pseudo-residual of the MSE loss exhibits a linear relationship between the prediction and the output of each iteration, allows us to aggregate the losses across iterations. Equation (4) will be clarified further in Proposition 2.In practice, if we perform m re-training in each iteration, and obtain the empirical residual Rashomon set R m t (H, S t , h * t , ϵ), the model f T (x) can be expressed asf T (x) = h 0 (x) + T t=1 h t (x), ∀h t ∈ R m t (H, S t , h * t , ϵ).Since in each of the T iterations, there are m candidate models in R m t (H, S t , h * t , ϵ), there are a total of m T possibilities for f T (x) ∈ R(F, S, f * T , T ϵ) (see Appendix B.3 for visualization). We term the process of building the empirical residual Rashomon sets for the entire Rashomon set R(F, S, f * T , T ϵ) as Rashomon gradient boosting or RashomonGB in short. RashomonGB can be straightforwardly implemented by training m models (i.e., weak learners) at each iteration that meet the loss constraints defined by the Rashomon set. This is fundamentally different from simply performing m re-training of gradient boosting to solve the original learning problem min f ∈F L S (f ), since the m models at each iteration obtained by RashomonGB share the same residual from the previous iteration. During the inference phase RashomonGB carries a significant benefit over simply performing m re-training of gradient boosting-both re-training of gradient boosting and RashomonGB requires m × T training when considering all the iterations. However, RashomonGB, using a different way to output the predictions at the inference phase, yields exponentially many more models with the same training cost. So far, we have informally introduced RashomonGB. In the rest of this section, we provide a rigorous analysis to show the effectiveness of RashomonGB by characterizing the Rashomon sets of gradient boosting (or more generally, the Rashomon sets of the iterative training procedure). The analysis collectively ensure that RashomonGB is not only practical but also robust, enhancing its applicability in various real-world scenarios.Characterizing the entire Rashomon set, given a learning problem and dataset, has posed as a significant computational challenge (refer to Section 2). Specifically, for gradient boosting, delineating the Rashomon set R(F, S, f * T , ϵ) entails identifying all models f T ∈ F such that L P S (f T ) ≤ L P S (f * T ) + ϵ for a given model f * T . However, Eq. ( 4) presents a novel approach to approximating the Rashomon set by decomposing it into residual Rashomon sets concerning the weak learners-this method offers valuable insights into analyzing the Rashomon effect in gradient boosting.Existing literature explores how various hypothesis spaces influence the Rashomon set but frequently neglects the impact of datasets, despite the Rashomon set being inherently tied to the dataset itself (cf. Eq. ( 1)). In this context, we derive a novel bound on the size of the Rashomon set by expanding the scope of the Rashomon set beyond mere consideration of hypothesis spaces, incorporating the influence of datasets through the lens of statistical learning and information theory. Particularly in the analysis of information-theoretic generalization error bounds [77] , a learning algorithm A(S) is conceptualized as a random variable H that generates models within the hypothesis space H. Moreover, the loss function ℓ(h, S) is also treated as a random variable, and is further assumed to be σ-sub-Gaussian5 [73] , a property that effectively generalizes the boundedness assumption of the loss function in information-theoretical analysis. Sub-Gaussianity is a practical property since for a bounded loss function ℓ ∈ [a, b], which can be readily satisfied by clipping the loss 6 , ℓ(h, S) is guaranteed to be (b -a)/2-sub-Gaussian. With these properties in place, the mutual information I(S; H) between H and the random variable of dataset S emerges as a pivotal metric for assessing generalizability. By establishing a connection between generalization error bounds and the definition of a Rashomon set in Eq. ( 1), and leveraging the properties of a sub-Gaussian loss, we derive the following high-probability bound for a Rashomon set. Proposition 1. For a dataset S, given an empirical risk minimizer h * = argmin h∈H L S (h) and a σ-sub-Gaussian loss ℓ, with probability at least 1 -ρ, we haveEQUATIONIn contrast to existing analyses of the Rashomon set primarily focused on optimization perspectives, Proposition 1 offers a characterization of the size of the Rashomon set in terms of the controllable probability of the Rashomon parameter ϵ. This sheds light on understanding the Rashomon set from a statistical learning standpoint. Furthermore, the mutual information I(S; H) in Eq. ( 5) quantifies the uncertainty of the learning algorithm with respect to the dataset S. In essence, I(S; H) serves as a metric for the multiplicity of models, thereby contributing to predictive multiplicity. By chain rules, we can decompose the mutual information into two components, each delineating a distinct source responsible for inducing multiplicity, i.e., IEQUATIONProposition 2 suggests that the Rashomon set grows with the boosting iterations-it is due to the increased complexity of the overall model f t . Unless the number of samples n goes to infinity, the Rashomon set has a non-zero size.The information-theoretic analysis presented in the previous section underscores the importance of the mutual information I(H; Y |X) in determining the size of the Rashomon set and hence the severity of predictive multiplicity. However, existing literature lacks an in-depth analysis of the information contained within the pseudo-residuals for gradient boosting algorithms. Let R t represents the random variable associated with the residuals {r ti } n i=1 . As t grows, fitting R t with X becomes progressively challenging, akin to the gradient vanishing problem observed in deep learning [31, 40] , thereby resulting in larger conditional mutual information with data X. We formalize this observation in the following proposition. Proposition 3. For both the MSE and CE losses, the mutual information between H and the pseudoresiduals conditioned on the features X is non-decreasing with respect to the boosting iteration, i.e., let0 ≤ t 1 ≤ t 2 ≤ T , then I(H; R t1 |X) ≤ I(H; R t2 |X).The essence of Proposition 3 lies in the fact that the information contained in R t2 can be understood as a combination of the information in R t1 and the additional information provided by the models fitted to the residuals between iterations t 1 and t 2 . Proposition 3, Proposition 1, and Eq. ( 6) collectively hint at a counter-intuitive observation: the size of the residual Rashomon set could potentially increase with more boosting iterations, i.e., for0 ≤ t 1 ≤ t 2 ≤ T , we have ϵ t1 ≤ ϵ t2 and hence R t H, S t1 , h * t1 , ϵ t1 ⊆ R t H, S t2 , h * t2 , ϵ t2. This implies that conducting additional boosting iterations 7 may not only exacerbate over-fitting but also result in a larger Rashomon set and heightened predictive multiplicity. Note that we do not start with the assumption that ϵ increases with each iteration; rather, this conclusion emerges from Proposition 3. With a constant ρ-as defined in Proposition 1-additional iterations result in increased conditional mutual information, which in turn necessitates a larger ϵ.Figure 2 provides a simulation with a 20-dimensional Gaussian synthetic datasets with 100 samples, trained with gradient boosting for 10 iterations, where each iteration contains m = 100 models. Here, we show the conditional entropy 8 g(R t |X) instead of the mutual information I(R t , X; H) in Eq. ( 6) as the estimation of the mutual information is in general a hard task [60] . It is clear that the conditional entropy-and consequently the mutual information-increases as the boosting procedure iterates, leading to a larger Rashomon set. This occurs because the Rashomon effect accumulates across the sequential learning problems addressed in each iteration, highlighting the cumulative impact on diversity within the model space. The Ablation study in Appendix E.4 further clarifies the selection of ϵ through its iterations. Figure E.9 demonstrates that fixing ϵ while re-training with different random seeds results in a decreasing percentage ρ of models in the Rashomon set. This implies that to maintain a consistent ρ, the chosen Rashomon parameter ϵ must increase. As a remark, consider training m models per iteration, and construct the overall Rashomon sets using models obtained from the T 1 -th and T 2 -th iterations with T 1 < T 2 . With the same threshold ϵ for the Rashomon set, let ρ 1 and ρ 2 represent the probabilities for iterations T 1 and T 2 , respectively, then by Proposition 3, we have 1 -ρ 1 ≥ 1 -ρ 2 . the number of models from the T 1 -th iteration that are included in the Rashomon set with threshold ϵ will be m T1 × (1 -ρ 1 ). Similarly, for the T 2 -th iteration, the count will be m T2 × (1 -ρ 2 ). It is important to note that although ρ decreases, this reduction is linear with respect to the number of iterations (as suggested by the term 1 -T ρ in Proposition 2). However, the number of models generated by RashomonGB grows exponentially with the number of iterations. Thus, the total number of models in the Rashomon set will still asymptotically increase with the number of iterations.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: We cover the positive and negative impacts of the Rashomon effect and predictive multiplicity in the introduction and related work Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
applications of rashomon gradient boosting: 
 We present three use cases demonstrating how RashomonGB can be deployed in practice to explore models more effectively in the Rashomon sets: (i) improving the estimation of predictive multiplicity metrics, (ii) fair model selection, and (iii) mitigating predictive multiplicity. Given that there are no existing algorithms specifically designed to explore the Rashomon set for gradient boosting, apart from re-training with different seeds [67, 48] , we use the re-training strategy as our primary baseline for comparison through this section. It's noteworthy that both the re-training strategy and RashomonGB share the same training complexity. However, during the inference phase, RashomonGB exponentially expands the empirical Rashomon set (i.e., with a large m following Section 3.1). In our experiments, we adopt the settings in Friedman [34] with decision tree regressors as weak learners for tabular datasets and CNNs for images. See Appendix D.1 for detailed descriptions and pre-processing of the datasets, Appendix D.2 for detailed training setups, and Appendix E for additional experiments including ablation studies.We estimate the predictive multiplicity metrics (cf. Appendix B.2) on three tabular datasets with binary classes. Two of these datasets are from the financial domain (ACS Income [24] and Credit Card [78] ), while the other is from the medical domain (Contraception [5] ). The datasets are particularly chosen as predictive multiplicity in these domains could have profound implications for fairness and justice. Note that the ACS Income dataset is an extension of the widely-used UCI Adult dataset [5] with many more samples (≈1.6 million vs. <50k in the UCI Adult), allowing us to compare methods with higher precision. Beyond binary classification and decision-tree weak learners, we use CIFAR-10 [46] as a multi-class case study with CNNs as weak learner, i.e., a setting similar to Badirli et al. [6, GrowNet] . 2 T = 1024 (and 972 models for CIFAR-10) models 9 . The leftmost column shows the CE loss vs. accuracy for the models obtained by the two methods. It is clear that with the same training cost, RashomonGB offers many more models in the Rashomon set that spread wider in the loss-accuracy plane. The rest of the four columns show the estimates of predictive multiplicity metrics given different loss deviation constraints. Since VPR, Rashomon capacity, and disagreement are defined per sample, we plot the mean and std. of the top 10% samples instead 10 .As observed in Figure 3 , RashomonGB consistently outperforms re-training in the ACS Income and Credit Card datasets for all predictive multiplicity metrics. The RashomonGB has more advantages especially when re-training is incapable of exploring enough models under the loss deviation constraint. For example, in the Contraception dataset, when the loss constraint is under 0.585, there is only one model obtained from re-training, and therefore the corresponding values of predictive multiplicity metrics remain 0. As the loss constraint increases, the Rashomon set from re-training has more models and its estimates converge with that of RashomonGB. The explanations above indicate that the exploration of diverse models under the same loss constraint largely affects the estimation of predictive multiplicity metrics. For the CIFAR-10 dataset, both VPR and RC values are small, while decision-based metrics, such as disagreement and discrepancy, are large. This implies that despite small score variations, a significant number of samples have scores close to the decision boundary. Consequently, a slight perturbation in scores from a different model in the Rashomon set could lead to a different class after applying argmax.We include additional results on three other UCI datasets in Appendix E.2 and a comparison of the computational time 11 to obtained one model from re-training and from RashomonGB in Appendix E.3. The ablation studies on different types of weak learners H (e.g., linear regression), depths of decision tree weak learners, the number of boosting iteration T and the number of model in each iteration m are also include in Appendix E.5 to E.8. To elucidate the distinctions between predictive multiplicity and prediction uncertainty estimation in gradient boosting (cf. Section 2), we have compared our re-training strategy, RashomonGB against NGBoost [27, 55] , PGBM [70] , and IBUG [13] with the UCI Contraception dataset in Appendix E.9.We conduct re-training and RashomonGB on two standard datasets in the algorithmic fairness community, the UCI Adult and COMPAS recidivism datasets [3] , with the goal of selecting a model that exhibits better fairness-accuracy trade-offs. We follow the same training procedure and gradient boosting architecture in Section 4.1. We assess the bias across different groups (e.g., female vs. male) by two group-fairness metrics 12 , mean equalized odds (MEO) [38] and statistical parity (SP) [29] (cf. Appendix B.4 for details). In both datasets, the group attributes are the binary "race" label. Figure 4 illustrates that with RashomonGB, a practitioner has a greater chance to select a model that better satisfies group-fairness constraints without a significant drop in accuracy. The RashomonGB framework, which involves training m distinct models in each iteration, offers the added benefit of reducing predictive multiplicity in gradient boosting. The m models in the empirical Rashomon set for R m (H, S t , h * t , ϵ) for the t th iteration can either be selected (based on the least losses) or aggregated (similarly to model averaging in Section 2). Building on these concepts, we propose two approaches to reduce predictive multiplicity in gradient boosting: (i) model selection with reweighted loss (MS), and (ii) intermediate ensembles during boosting iterations (IE).Let ℓ i,j = ℓ(h j , s i ) be the loss evaluated at sample s i for model h j ∈ R m (H, S t , h * t , ϵ), and let li = 1 m m j=1 ℓ i,j be the mean loss. The MS method considers the reweighted loss for each model in the empirical Rashomon set using ℓ hj ≜ n i=1 ℓ i,j (ℓ i,j / li ) λ , and selects the top k models with the smallest ℓ hj , where k ≤ m. MS simplifies to re-training at λ = 0. The model with the smallest ℓ hj is used to compute the residuals for the next iteration, and we return the top k models at the last boosting iteration. The intuition of this reweighting is that the loss contribution of sample s i is rewarded at an exponential scaling factor λ ≥ 0 when the model h j produces lower loss than the average for s i over all models in R m (H, S t , h * t , ϵ). In contrast, the IE method constructs U ensembles h u , u ∈ [U ] in each iteration, where each ensemble consists of E randomly selected We observe that IE outperforms MS in disagreement reduction while both methods yield a similar accuracy to re-training. However, IE has the cost of increasing the overall model complexity by a factor of E = 20, which may be undesirable for interpretability or auditing. It is noteworthy that a small ∆accuracy could lead to a great reduction in disagreement. For example, in "epilepticseizure", re-training has a 0-disagreement of 0.208 and IE reduces it to 0.041 with only a slight improvement of 0.014 ± 0.002 in accuracy. For ablation studies on the hyperparameters E, k and λ and more explanations, see Appendix E.10. 
discussion: 
 Here we reflect on the limitations and highlight interesting avenues for future work.Limitations. While re-training with different random seeds offers a "global" exploration of models within the Rashomon set, RashomonGB conducts a "local" exploration. Therefore, the effectiveness of RashomonGB depends on selecting diverse models in each iteration; similar models reduce its efficiency in exploring Rashomon sets. However, RashomonGB demonstrates greater efficiency than the re-training strategy, highlighting a trade-off between the efficiency of exploring the Rashomon set and the effectiveness of capturing model diversity. Finding the (sub-)optimal strategy for exploring the Rashomon set remains an active area of research. Our theoretical analysis, developed for gradient boosting, needs an extension to other algorithms like adaptive boosting to validate its applicability. Additionally, the large number of models generated by RashomonGB poses storage challenges, requiring new data structures for efficient management.Future directions. First, our analysis in Section 3 links the size of the Rashomon set to dataset quality, providing a foundation for studying how dataset properties impact the Rashomon effect. Second, combining models in each RashomonGB iteration is similar to model stitching [50] , suggesting potential insights if adapted for neural networks. Third, varying the number of models selected per iteration could enhance RashomonGB's flexibility and effectiveness.The appendix is divided into the following parts. Appendix A: Omitted proofs and theoretical results;We start with the Rashomon set of fitting models to the pseudo-residuals at T -th boosting iteration. With the MSE loss, we have r ti = -∂ℓ(ft-1,si) ∂ft-1 = 2(y i -f t-1 (x i )). We neglect the factor 2 as it is just a constant. From Proposition 1, we know that for h T ∈ H, with probability at least 1 -ρ,1 n n i=1 (h T (x i ) -r ti ) 2 ≤ 1 n n i=1 (h * T (x i ) -r T i ) 2 + ϵ T , (A.10)where ϵ T = 8σ 2 n 2I(S T ;H) ρ + ln 4 ρ + σ 2 n ln 4 ρ is the Rashomon parameter. By plugging in the recursive relation of the pseudo-residuals , we have1 n n i=1 (h * T (x i ) -r T i ) 2 + ϵ T = 1 n n i=1 (h * T (x i ) -(y i - T -1 t=0 h * t (x i )))) 2 + ϵ T = 1 n n i=1 ( T t=0 h * t (x i ) -y i ) 2 + ϵ t = 1 n n i=1 (f * T (x i ) -y i ) 2 + ϵ t . (A.11)On the other hand, for the left-handed term in Eq. (A.10), we have for h T -1 ∈ H, with probability at least 1 -ρ1 n n i=1 (h T (x i ) -r ti ) 2 = 1 n n i=1 (h T (x i ) -r (T -1)i + h * T -1 (x i )) 2 ≥ 1 n n i=1 (h T (x i ) -r (T -1)i + h T -1 (x i )) 2 -ϵ T -1 = 1 n n i=1 ( T t=T -1 h t (x i ) -r (T -1)i ) 2 -ϵ T -1 , (A.12)where the inequality in Eq. (A.12) comes again from Proposition 1. By repeating the decomposition of the pseudo-residuals in Eq. (A.12), we have for f T ∈ F, with probability at least 1 -(T -1)ρ,1 n n i=1 (h T (x i ) -r ti ) 2 ≥ 1 n n i=1 ( T t=1 h t (x i ) -y i ) 2 - T -1 t=1 ϵ t = 1 n n i=1 (f T (x i ) -y i ) 2 - T -1 t=1 ϵ t . (A.13)Finally, combining Eq. (A.10), Eq. (A.11), and Eq. (A.13) with probability union bounds, we have for f T ∈ F, with probability at least 1 -T ρ1 n n i=1 (f T (x i ) -y i ) 2 ≤ 1 n n i=1 (f * T (x i ) -y i ) 2 + T t=1 ϵ t , (A.14)where the overall Rashomon parameterT t=1 ϵ t = T σ 2 n ln 4 ρ + T t=1 8σ 2 n 2I(St;H) ρ + ln 4 ρ .With loss of generality, let t 1 = t -1 and t 2 = t. If the loss function ℓ is the MSE loss, the pseudo-residuals of the t-th boosting iteration have the formr ti = - ∂ℓ(f t-1 , s i ) ∂f t-1 = 2(y i -f t-1 (x i )) = 2(y i -f t-2 (x i ) -h t-1 (x i )) = r (t-1)i -2h t-1 (x i ).(A.15)We provide addition background and discussions on gradient boosting, predictive multiplicity, the Rashomon gradient boosting algorithm, and group fairness.The minimization of L S (f T ) can be viewed as functional gradient descent (FGD), which is a computationally infeasible optimization problem in general [58] . A common alternative to approximate a FGD is applying steepest descent to find a local minimum of the loss function by iterating on a given f t-1 (x), i.e., f t (x) = f t-1 (x) -η∇ ft-1 L S (f t-1 ) with a learning rate η ∈ R + . This way, in a forward stage-wise manner, we can fit a basis function h t ∈ H that is closest to the functional gradient ∇ ft-1 L S (f t-1 ) subject to a distance measure d with h t = argmin h∈H d(∇L S (f t-1 ), h).Varying the choices of ℓ and d recovers most widely-used boosting algorithms. For instance, if ℓ(h t , s i ) = e -yiht(xi) and d(∇L S (f t-1 ), h t ) = -∇L S (f t-1 ) • h t , the FGD recovers adaptive boosting (AdaBoost) [32] , and if ℓ(h t , s i ) = log(1 + e -yih(xi) ), it recovers LogitBoost [33] . Finally, if d is the ℓ 2 -norm ∥ -∇L S (f t-1 ) -h t ∥ 2 2 instead of the inner product, it recovers the gradient boosting [34] . One of the most popular variants of gradient boosting is by further applying LASSO and ridge regularizations, called the eXtreme Gradient Boosting (XGB) [15] .We summarize existing predictive multiplicity metrics, from their background, mathematical formulation, operational meanings, to computational details. Predictive multiplicity metrics can be categorized into two groups: score-based and decision-based, where a decision is a thresholded score or the score vector after argmax. Precisely, consider a binary classification, if we have a score q, then the decision can be obtained by 1[s > τ ], where τ is a threshold. For a c-class classification problem where c > 2, the score is a vector, say q ∈ ∆ c , and the decision can be obtained by argmax i∈[c] [q] i . In the following, we start with the decision-based metrics, see Table B .1.Decision-based predictive multiplicity metrics essentially measure the "conflictions" of the decisions either for the whole dataset or per sample. Marx et al. [56] propose two metrics: ambiguity and discrepancy; both of them measure the fraction of conflicting decisions across a dataset. Ambiguity is the proportion of samples in a dataset that can be assigned conflicting predictions by competing classifiers in the Rashomon set. Discrepancy is the maximum number of predictions that could change in a dataset if we were to switch between models within the Rashomon set. More precisely, given a pre-trained model h w * , the ambiguity α(D) and the discrepancy δ(D) are respectively defined in [56, Definitions 3 and 4] . Both ambiguity and discrepancy can be estimated by a mixed integer program [56, Section 3] . The implementation of estimating ambiguity and discrepancy can be accessed at https://github.com/charliemarx/pmtools. DefinitionsAmbiguity [56] α(D) ≜ 1 |D| x i ∈D max hw ∈R 1 [argmax hw(xi) ̸ = argmax hw * (xi)] Discrepancy [56] δ(D) ≜ max hw ∈R 1 |D| x i ∈D 1 [argmax hw(xi) ̸ = argmax hw * (xi)]Disagreement [10, 48] measures (in the sense of KL divergence) the spread of the scores of a sample x i given a distribution P R over all the models h w in the Rashomon set, where the minimizing q acts as a "centroid" for the outputs of the classifiers. The supremum picks the worst-case distribution P R over all possible distributions in the Rashomon set. They proposed the adversarial weight perturbation (AWP), which perturbs the weights of a pre-trained model such that the output scores of a sample are thrust toward all possible classes. The outputs of the perturbed models can then be used to compute RC by the Blahut-Aromoto algorithm [11, 4] . The implementation of AWP and the Blahut-Aromoto algorithm can be accessed at https://github.com/HsiangHsu/rashomon-capacity.µ(xi) ≜ 2 Pr{argmax hw(xi) ̸ = argmax h ′ w (xi); hw, h ′ w ∈ R}The estimation of all these predictive multiplicity metrics is, in practice, computed with the empirical Rashomon set, as the true Rashomon set in Eq. ( 1) is computationally infeasible. Note that, however, the size of the empirical Rashomon set is not a proxy for multiplicity. For instance, an empirical Rashomon set with 100 globally diverse (e.g., obtained by re-training with different seeds) models might exhibit a higher predictive multiplicity metric (e.g., VPR) compared to another empirical Rashomon set containing 1000 models that differ only locally. The size of the true Rashomon set, on the other hand, representing an ideal scenario achievable with unlimited computational and storage resources, can indeed act as a proxy for predictive multiplicity. In this context, predictive multiplicity metrics are non-decreasing with a larger size of the true Rashomon set (i.e., a larger ϵ).We provide visualizations of RashomonGB in training in total. The right hand side is RashomonGB that generates m T = 2 3 = 8 models, i.e., {M 11 , M 12 }+{M 21 , M 22 }+{M 31 , M 32 }. In essence, building the Rashomon set with RashomonGB is similar to expanding the tree in each iteration (i.e., layers) until it is a complete m-ary tree.Consider a triple of sample (x, a, y), where x and y are the usual feature and label pair, and a is an additional attribute, such as race or sex, that can be used to split the datasets into different groups (e.g., female vs. male if a is sex). Group fairness is measured by the gap of a certain quantity evaluated on different groups. For example, statistical parity (SP) considers the the probability of the model outputting class 1, and mean equalized odds (MEO) considers the sum of True Positive Rate (TPR) and False Positive Rate (FPR). For simplicity, denote Ŷ argmax h(X) the prediction label the model h, and assume that there are B groups. Then the equalized odds (EO) and (SP) can be formally defined as:Definition B.1 (SP [29]). Pr Ŷ = 1|A = a = Pr Ŷ = 1|A = a ′ , ∀a, a ′ ∈ [B].Definition B.2 (EO [38] ).Pr Ŷ = 1|A = a, Y = y = Pr Ŷ = 1|A = a ′ , Y = y , ∀a, a ′ ∈ [B]and ∀y ∈ [c].The operational meaning of the two group fairness metrics is as follows: Statistical Parity (SP) requires that the predicted label Ŷ be independent of the group attribute A, while Equalized Odds (EO) conditions on both the group attribute and the true label for independence. EO improves upon SP by allowing for perfect classifiers when the true label Y is correlated with the group attribute A.In practice, we measure fairness by quantifying the level of EO and SP violations, as reported in Figure 4 . The violation of EO is also referred to as the mean EO.MEO ≜ max a,a ′ ∈[B] 1 2 (|TPR A=a -TPR A=a ′ | + |FPR A=a -FPR A=a ′ |) . SP violation ≜ max a,a ′ ∈[B] 1 2 Pr Ŷ = 1|A = a -Pr Ŷ = 1|A = a ′ . (B.19)Fairness intervention algorithms aim to make the outputs of a machine learning model satisfy either MEO or SP violation smaller than a given budget. The fairness interventions can be categorized into three categories: pre-processing, in-processing and post-processing. Pre-processing mechanisms, such as the one proposed by Calmon et al. [14] , transform the dataset using a random mapping to reduce group fairness metrics while preserving utility. This approach is the most flexible within the data science pipeline, as it is independent of the modeling algorithm and can be integrated with data release and publishing mechanisms. In-processing mechanisms such as Reduction incorporate fairness constraints directly into the training process. This typically involves adding a fairness constraint to the loss function, resulting in a fair classifier. Post-processing mechanisms such as EqOdds and rejection treat the model as a black box and adjust its predictions (by, e.g., tilting) to meet the desired fairness constraints.Here, we provide more details on the fairness intervention baselines used in Section 4.2. Reduction [1] , short for exponentiated gradient reduction, is an in-processing technique that converts fair classification into a sequence of cost-sensitive classification problems. It produces a randomized classifier that achieves the lowest empirical error while satisfying the desired fairness constraints. Although this technique effectively achieves fairness with minimal accuracy loss, it is computationally expensive due to the need for re-training multiple models. Rejection [45] is a post-processing technique that achieves fairness constraints by adjusting the outcomes of samples within a confidence band around the decision boundary. It assigns favorable outcomes to unprivileged groups and unfavorable outcomes to privileged groups, resulting in thresholded predictions rather than probabilities over binary labels. EqOdds [38] is a post-processing technique that addresses empirical risk minimization with a fairness constraint by formulating it as a linear program. It adjusts predictions based on the derived probabilities to achieve equalized odds. FaiRS [20] develops a framework for characterizing predictive fairness properties across models in the Rashomon set. They also propose a variant of FaiRS that addresses the issue of selective labels, achieving the same guarantees with oracle access to the outcome regression function.We summarize the dataset descriptions and training setups in Section 4.In this paper, we use 18 tabular datasets from the UCI machine learning repository [5] , the ACS Income dataset [24] and the COMPAS recidivism dataset [3] . We summarize the descriptions of all tabular datasets, including the number of features, training/test split (seed = 42), and the label description in Table D .3.The UCI machine learning repository (accessible at DuBois [28] ; license: CC BY 4.0) is a wellknown and widely used collection of 650 datasets for machine learning research and experimentation, and contains a diverse and extensive collection of datasets across various domains. We select 18 datasets in specific domains, including medicine, economics, society, etc., that may possess critical consequences if predictive multiplicity is not accounted for. For these UCI datasets, we remove samples with missing values, one-hot encoded nominal features, re-scale numeric features, and set the target label name to be 1 and the rest to be 0.The ACS Income dataset (accessible at https://github.com/fairlearn/fairlearn; license: MIT license) and the UCI Adult dataset are collected from the United States Census Bureau. The goal of both datasets is to predict the income with demographic features of people. The UCI Adult dataset has a smaller size and a binary record of the income label (Y = 1 if income > $50K and Y = 0 otherwise). The ACS Income dataset has more than 1.6 million samples. The income attribute is real-valued rather than a binary label. We transform the income to a binary labels by Y = 1 if income > $39K (the median income) and Y = 0 otherwise.The COMPAS Recidivism dataset (accessible at https://www.propublica.org/datastore/ dataset/compas-recidivism-risk-score-data-and-analysis; license: CC-BY-4.0) contains the prior criminal history for criminal defendants and the demographic makeup of prisoners in Brower County, Florida from 2013-2014. we select gender, age, number of prior crimes, length of custody and likelihood of recidivism to be the features. We pre-process the dataset by dropping missing/incomplete records, and convert categorical variables by one-hot encoding. For the group fairness experiments in Section 4.2, we only keep two races, African American (S = 0) and Caucasian (S = 1).CIFAR-10 dataset (accessible at https://www.cs.toronto.edu/~kriz/cifar.html; license: MIT License) contains 60,000 images and equally distributed to 10 classes, such as cars, cats, etc. The dataset is split into 50,000 and 10,000 images for training and validation, respectively. Each image is a colored image with size of 32×32. For the pre-processing, we normalize each channel of image by the mean and standard deviation of the whole training set.The weak learners used for all tabular datasets are decision trees with the Python Scikit Learn package [62] . The decision trees are expanded up to a maximal depth of 2, and the criterion for splitting is the squared loss with a impurity gain greater than 10 -7 . The minimum number of samples required to split an internal node is 2 and the maximum number of leaf nodes is 3. The number of iterations for re-training and RashomonGB is T = 10. In each iteration we train models with different random seeds for the splitting at each depth, and use a filtering process in place that screens out models with an MSE loss greater than 0.1 (i.e., ϵ t = 0.1) and retains models with an MSE loss smaller than 0.01 until m = 10 models are collected at each iteration.For RashomonGB, we randomly pick 2 out of m models in each iteration. For all experiments, we set the learning rate to be α = 0.8, and the loss function is the binary cross-entropy lossL CE (h) ≜ 1 n n i=1 [-y i log softmax(h(x i )) -(1 -y i ) log(1 -softmax(h(x i )))].For experiments in Section 4.2, we use the AIF360 [7] and Fairlearn [8] packages to implement the fairness intervention algorithms.The weaker learner used for CIFAR-10 experiment is a 3-stage convolutional neural network with Python Pytorch package [61] , each stage is composed by a convolutional layer with kernel size 3×3 and output channel 64, a batch normalization layer and a ReLU layer, and the residual shortcut is added before ReLU for stage 2 and 3; at the end of each stage, an average pooling layer reduces the spatial dimension by 2 with kernel size 3. After stage 3, a global average pooling is applied to reduce the spatial dimension to 1×1, following by a linear layer for regression the pseudo-residual of each class. For each weaker learner, we train with batch size 256 for 50 epochs, and we use the AdamW [54] optimizer with fixed learning rate, 10 -3 and weight decay, 10 -4 . Due to its complexity, we use T = 6 and m = 50 for both re-training and RashomonGB. During inference for RashomonGB, we random pick 3 out of m models for each boosting iteration but 4 for the last iterations, which results in 972 models. We adopt the same learning rate (0.8) used in the experiments for the tabular datasets. We include an illustration on how to interpret Figure 3 , additional experiments on other UCI datasets (UCI Adult, Bank Marketing, Mammography), computational time comparison between re-training and RashomonGB, ablation studies on different types of weak learners, number of boosting iterations T , number of models in each iteration m, comparison with predictive uncertainty estimation methods, and hyperparameters for mitigation predictive multiplicity (E, k, and λ).E.1 How to interpret Figure 3 We provide an explanation on how to properly interpret Figure 3 We include additional results in Figure E.8 on comparing the effectiveness of estimation prediction multiplicity metrics between re-training and RashomonGB (similar to Figure 3 ) for UCI Adult, Bank marketing, and Mammography datasets [5] . The UCI Adult dataset aims to predict whether the income of an individual exceeds 50,000 per year based on 1994 census data. The Bank Marketing dataset is related with direct marketing campaigns of a Portuguese banking institution based on phone calls in order to predict if the client will subscribe a bank term deposit or not. The Mammography dataset aims to discriminate between benign and malignant mammographic masses based on BI-RADS attributes and the patient's age. Our observation is that for decision-based predictive multiplicity metrics such as disagreement and discrepancy, RashomonGB outperforms re-training in terms of the effectiveness. For score-based predictive multiplicity metrics, when the CE loss constraint is small, RashomonGB performs better for all three datasets. When CE loss constraint is large, the size of the Rashomon set grows fast, and re-training captures more diverse models in the Rashomon set. These observations are consistent with the results shown in the main text. We compare the training time, and the time to obtained one model for re-training and RashomonGB with T = 10, m = 10, α = 0.8 and depth-2 decision tree as weak learners. We repeated the experiments 3 times with different random seeds and report the time (in seconds) in Table E . 4 . Note that re-training and RashomonGB share the same training time, and the values we show for the columns re-training and RashomonGB are the inference time. It is clear that the time cost to obtain a model from RashomonGB is consistently and significantly smaller than that from re-training. All the runtimes we reported here are computed on the same machine in an Amazon EC2 g4dn.8xlarge instance. We validate our discussion in Section 3. Higher predictive multiplicity values mean a better estimate. For the leftmost column, it is clear that RashomonGB covers a widest range of models, leading to consistently higher estimates of VPR and the Rashomon Capacity. For decision-based metrics such as disagreement, RashomonGB has the better estimate when CE Loss is higher; however, for discrepancy IBUG has the better estimate.E.10 Hyperparameter sensitivity results related to mitigation methods in Section 4.3 Figure E.15 illustrates the effect of model hyperparameters on our two measures of interest: 0disagreement and accuracy. We report mean of each measure over 20 random train/test splits. We evaluate several datasets with larger ∆0-disagreement in Figure 5 . In (a), varying the ensemble size E tends to reduce disagreement on the 5 datasets evaluated. From this result, we use E = 20 when fixing E in our experiments. In (b), 0-disagreement increases over increasing k. We select the k weak learners from the candidate set in ascending order of loss. Therefore, increasing k tends to add models of decreasing quality. Furthermore, the 0-disagreement measure is strict; it requiring every additional model to have the same prediction on the sample. In (c), 0-disagreement tends to decrease to around λ = 5. From this result, we tune on λ ∈ [0, ..., 5] in our experiments. Finally, the bottom row demonstrates that accuracy is not sensitive to changes in any of these hyperparameters. Justification: We include a list of contributions at the end of the introduction, where each contribution and the claims made therein are specifically referred to a section in this paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: We provide proper citations for all datasets including licenses and how to access, and programming packages (Python, Pytorch, Scikit Learn, AIF360, and Fairlearn) used in this paper. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.Such randomness includes different seeds, weight initialization, splits of mini-batches, etc. 38th Conference on Neural Information Processing Systems (NeurIPS2024).Both prediction uncertainty and predictive multiplicity consider the arbitrariness of machine outputs, with predictive multiplicity specifically addressing models with competing performance. Predictive churn, on the other hand, focuses on the instability of decisions before and after updating models with new data.It is common to choose the model as an empirical risk minimizer.The weak learners in gradient boosting are usually decision tree regressors. However, the choice of the weak learners can be generalized to more complex families of functions[49] such as neural networks with[25] or without regularizations[6, GrowNet], and Gaussian processes[69].A random variable U is σ-sub-Gaussian if log E e λ(U -EU ) ≤ λ 2 σ 2 /2 for all λ ∈ R.The MSE loss is also qualified as a sub-Gaussian loss function.A similar phenomenon where additional information impacts the performance of boosting algorithms, has also been noted in previous studies such as Friedman et al.[33] and Long and Servedio[53].Estimated with local linear regression[18], which has consistently smaller MSE for small datasets.For 3 models per iteration, RashomonGB produces 3≈ 59k models, exceeding our storage limit.10 Predictive multiplicity occurs only on a small portion of samples. The choice of 10% is data-dependent.For the ACSIncome dataset, the inference time per model is 0.4 seconds for re-training, compared to just 0.02 seconds for RashomonGB. This indicates that, with the same training cost (54.67 seconds), RashomonGB is 20 times more efficient in generating models from the Rashomon set than the re-training strategy.MEO and SP respectively quantifies the discrepancy in the sum of True Positive Rate and False Positive Rate, and in the probability of the model outputting class 1.d(S, 0) counts the fraction of samples that have zero disagreement among the models in the Rashomon set. 
 
 Appendix:  


Decision: The authors introduce a novel approach to characterizing predictive multiplicity for gradient boosting. The paper also explores the implications for finding a group fair model with a sufficient level of accuracy. Reviewers appreciated the information theoretical analysis of the Rashomon effect in this setting, and saw a potential for impact of the proposed method given the prevalence of GB in tabular learning, along with the importance of fairness in tabular settings. Some concerns around the presentation and attention to detail seem to have been resolved during the rebuttal period.

Reviews: review: paper_summary: paper_summary: The paper explores the concept of predictive multiplicity in gradient boosting models. The Rashomon effect refers to the existence of multiple models that perform similarly well on a given dataset. The authors formalize this effect in the context of gradient boosting, introduce a new method called RashomonGB to efficiently explore this multiplicity, and demonstrate its application on various datasets. The paper aims to improve the estimation of predictive multiplicity and model selection, especially with considerations for group fairness.
strength_weakness: strength_weakness: 1. While the paper discusses the positive societal impacts of RashomonGB, it lacks a thorough exploration of potential negative impacts or misuse of the method.
2. The theoretical analysis relies on several assumptions that may not hold in all practical scenarios, potentially limiting the generalizability of the findings.
3. The paper mentions the intention to release code post-review, but the lack of immediate open access to code and data can hinder reproducibility and independent validation by other researchers.
4. Implementing RashomonGB might be complex for practitioners without a strong background in the theoretical aspects of machine learning and gradient boosting, potentially limiting its adoption in the industry.
questions: questions: 1. Can the method be extended or adapted for other types of machine learning models beyond gradient boosting?
2. How does the choice of hyperparameters in RashomonGB affect the stability and reliability of the results?
3. What are the practical challenges faced during the implementation of RashomonGB, and how can they be addressed to facilitate broader adoption?
limitations: limitations: NA
paper_summary: paper_summary: The paper studies the Rashomon effect in gradient boosting, a commonly used algorithm for tabular datasets, but something that has not received enough attention in multiplicity literature. The paper provides several theoretical discussions on the size of the Rashomon set and the impact of the number of iterations on multiplicity in GBRTs. Furthermore, the paper proposes RashomonGB, a method to create an exponential number of ‘near-optimal models’ by training only a polynomial number of models. With more models in the Rashomon set, the use of RashomonGB can create several downstream benefits without any extra cost of training, shown empirically by the authors.
strength_weakness: strength_weakness: - While the presentation of the rest of the concepts and the theoretical discussion were easy to follow, important details about the RashomonGB method and the details of the empirical setup were either missing (even from the Appendix) or imprecise. For instance, the Rashomon set of the gradient boosting algorithm isn’t going to simply be the iterative extension of Rashomon sets at every residual level, i.e., equation 4 is imprecise. Similarly, it seems that the epsilon value of the Rashomon set increases with more iterations, and thus it is confusing to me whether the insight that more iterations create bigger Rashomon sets is a result of multiple iterations or simply a result of bigger epsilon. See the section ‘Questions’ for more detailed comments and some follow-up questions. Edit after rebuttal: Acknowledged, correct and clarified.
- There are other methods to measure predictive uncertainty in gradient-boosted algorithms. Some examples based on a cursory search (there might be more, as I’m not too familiar with GBRTs) - https://arxiv.org/abs/2205.11412 https://arxiv.org/pdf/1910.03225 https://arxiv.org/abs/2106.01682 - While I understand that prediction uncertainty is not the same as predictive multiplicity, the two are closely related, and when proposing a better method to measure multiplicity, the paper should compare itself with other stronger baselines than just retraining. Just as previous works have proposed using Monte Carlo Dropout (which was initially created as a method to measure uncertainty) as a measure of multiplicity, uncertainty measurement baselines for GBRTs could have been adopted to create reasonable baselines, and would have made the results a lot stronger. Edit after rebuttal: Acknowledged and added.
questions: questions: My questions and comments mostly revolve around the RashomonGB formulation.
- I don’t believe equation 4 is correct. A model formed from residual models that are present in their Rashomon sets at every step does not necessarily make a model that will be present in the Rashomon set overall. That’s because the composition of GBRTs occurs at the prediction level, while Rashomon sets are defined by the authors at the loss level. Equation 4 probably would have been true if the loss function had a linear relationship with the model predictions, which is not an assumption I see being made anywhere in the paper. This also makes me question the empirical results, because if the RashomonGB formulation isn’t precise, do the models across which the authors calculate multiplicity even belong to the same Rashomon set? Edit after rebuttal: Acknowledged and corrected.
- Can the authors comment on why they compare two situations with different Rashomon parameters and make claims on their multiplicity? For example, Proposition 3 and the following paragraph. A Rashomon set would of course be bigger with a larger value of epsilon, and having that variability when talking about other trends doesn’t seem convincing to me. Edit after rebuttal: Confusion clarified.
- What was the exact epsilon value used for the experiment? I couldn’t find it anywhere in the paper. Moreover, I hope that given the Rashomon sets for the RashomonGB setup were defined with T*epsilon as the new epsilon value, the same freedom was also given to retraining. Again, if the comparison was done across methods with different epsilon values (which might not be the case, but I don’t know the details), that does not make sense to me. Edit after rebuttal: Appropriate information added.
limitations: limitations: - A central piece of the paper is their method RashomonGB. While the authors do try to emphasize the importance of this method by highlighting the number of models that can be created using their method, just the number alone is not enough to imply a better method for measuring multiplicity. Even assuming that the comparisons are indeed fair (see Questions), the differences in multiplicity are not very severe, and that makes me wonder if combining pieces of various residual models actually gives us new interesting models or do we just end up with similar models as already seen during retraining. The authors acknowledge this briefly in their limitations paragraph. Edit after rebuttal: Appropriate details added and clarified.
paper_summary: paper_summary: This paper presents an approach that compute Rashomon set for gradient boosting algorithm where the set can be obtained through products over weak learners at each step rather than sampling them through retraining. The authors further proposed a dataset related Rashomon bound through sub-Gaussian assumption, where mutual information between hypothesis space and dataset shows the predictive multiplicity, which can further decomposed into model uncertainty and quality of data. Experiments show the proposed solution offers more models in Rashomon set than retraining given the same computation budget.
strength_weakness: strength_weakness: I got some difficult time to understand the introduction and abstract of this paper even I have read some literatures about Rashomon effect and predictive multiplicity. It is simply hard to read given the narrative there. Especially the second paragraph of introduction; it gets me confused and self-questioning my understanding of Rashomon effect from other works.
questions: questions: Why boosting algorithms? 
Further justification about the dataset related Rashomon set bound?
limitations: limitations: No hard limitation I can see.
paper_summary: paper_summary: This paper proposes a method (RashomonGB ) to estimate the Rashomon sets/predictive multiplicity of gradient boosting models. It estimates multiple ($m$) models at each stage (effectively performing a local exploration) and then combine all such models in the end to construct $m^T$ models for Rashomon set computation, where $T$ is the number of iterations of the boosting. On several datasets the paper shows that RashomonGB performs better than re-training with $m$ seeds, in that at the fix $\epsilon$ (loss difference) level, RashomonGB tends to show more predictive multiplicity.
strength_weakness: strength_weakness: 1. The current exploration strategy is fast to compute, but I'm not sure if this follows the motivation of Rashomon set very well. While the authors mention one example on the Contraception dataset where re-training underestimates the predictive multiplicity, in general RashomonGB might create models that are more correlated than normal (because the "backbone" is the same GB model), thus underestimating the predictive multiplicity. Right now, the conclusion shows otherwise probably because the number of re-training is too small. 

2. Regarding the experiment, if I read this correctly, currently we use more compute for RashomonGB as well (by combining different weak models), so it is also not quite a fair comparison in my opinion. I would be very interested to see some estimate of how much compute RashomonGB saves against re-training, by running more re-training and see when are the metrics in Fig3 in the two methods become comparable.



minor: one "RashomonGB" in L290 should be "re-training".
questions: questions: 1. What's $\epsilon_{t_1}$ (and $\epsilon_{t_2}$) in L243-L244? Isn't epsilon a quantity set by the user? 


2. In L282-283, do we construct 10 final models and 1024 for re-training and RashomonGB, respectively? If only 2 out of $m$ models are used why train $m$ of them (L282-283) for RashomonGB? 

3. Related to the above, I originally thought there is a model "filtering" step in each iteration $t$, and wonder how $\epsilon_t$ is set for each iteration. However, from L282-283 it seems like we just randomly pick a few models and brute-force combine all weak models for the final Rashomon set exploration. Could the authors clarify?

4. Are Fig 4 measured on the test set? If so, then it's not clear how useful this is as we cannot choose models basing on test performance - did the authors try picking models on the frontier basing on the validation set and then plot this on the test set? Right now, due to the sheer number of final models generated by RashomonGB, it's unclear if the models with better trade-off are just lucky.
limitations: limitations: N/A

Comments: title: Further response to Reviewer JGsC
Further response to Reviewer JGsC's comments
comment: Thank you for your detailed reply. The rebuttal is very appreciated. I increased my score to 6.
We appreciate the reviewer for guiding us to improve the quality of this manuscript, and for the summary of our discussions. We have fixed the typo in our comment above and left a note. We would definitely include our discussion and the reviewer's suggestion in the revised version! Thanks again!
Your response helped me narrow down where my confusion came from. I had not considered the exponentially growing number of models themselves, which despite a decreasing probability of a model being in the Rashomon set, would still overall make a bigger Rashomon set. Thank you for the clarification.

Small correction: I believe the authors meant to write $1-p_1 \geq 1-p_2$, and not the other way around. Probably a small typo.

To summarize our discussion, make sure to fix equation 4 and add appropriate information on how to interpret the figures. As for my concerns and confusion with increasing epsilon, it might be an artifact of my own reading of the work and not necessarily anything missing in the paper, but I’d encourage the authors to add appropriate clarifications and incorporate a discussion of how things evolve under a fixed epsilon, which, in my opinion, is a more realistic setting. 

Good work!
We appreciate the additional feedback from the reviewer!
Consider a scenario where we train $m$ models per iteration for $T\_1$ iterations, and subsequently extend the training up to $T\_2$ iterations, where $T\_1 < T\_2$. 
We can construct the overall Rashomon sets using models obtained from both the $T\_1$-th and $T\_2$-th iterations. 
With the same threshold $\epsilon$ for the Rashomon set, we can infer from Propositions 2 and 3 that the probability $1-\rho$ of a model belonging to the Rashomon set will decrease over the iteration. 
Let $\rho\_1$ and $\rho\_2$ represent the probabilities for iterations $T\_1$ and $T\_2$, respectively, then $1-\rho\_1 \geq 1-\rho\_2$.
Consequently, the number of models from the $T\_1$-th iteration that are included in the Rashomon set with threshold $\epsilon$ will be $m^{T\_1} \times (1-\rho\_1)$. Similarly, for the $T\_2$-th iteration, the count will be $m^{T\_2} \times (1-\rho\_2)$.
It is important to note that although $1-\rho\_1 \geq 1-\rho\_2$, indicating a decrease, this reduction is linear with respect to the number of iterations (as suggested by the term $1-T\rho$ in Proposition 2). However, the number of models generated by RashomonGB grows exponentially with the number of iterations (Line 158). Thus, despite the decreasing probability, the total number of models in the Rashomon set ($m^{T\_2} \times (1-\rho\_2)$) will asymptotically increase with the number of iterations.
We hope the explanation reduces the confusion, and will add the clarification in the revised version.


We agree with the reviewer's comment that the size of the "empirical" Rashomon set (see Line 82) is not a proxy for multiplicity.
For instance, an empirical Rashomon set with 100 globally diverse (e.g., obtained by re-training with different seeds) models might exhibit a higher predictive multiplicity metric (e.g., VPR) compared to another empirical Rashomon set containing 1000 models that differ only locally. The size of the "true" Rashomon set (see equation (1)), on the other hand, representing an ideal scenario achievable with unlimited computational and storage resources, can indeed act as a proxy for predictive multiplicity. In this context, predictive multiplicity metrics are non-decreasing with a larger size of the true Rashomon set (i.e., a larger $\epsilon$).
We are grateful to the reviewer for highlighting the ambiguity in our discussion. We will clarify the distinction between the true and empirical Rashomon sets in Section 3 and in the sections discussing empirical studies in the revised manuscript.

For Question 3, we are thankful for the reviewer's feedback in the initial review round, which guided us in enhancing the presentation of Figure 3. We are glad that the reviewer acknowledges the clarity brought by the additional figure and explanation. In the revised version, we will ensure to include detailed explanations on how to interpret Figure 3 effectively.

=== changing the typo in $1-\rho\_1 \leq 1-\rho\_2$ to $1-\rho\_1 \geq 1-\rho\_2$ as pointed out by Reviewer JGsC in the discussion. ===
Thank you for your response. Some of my concerns have been answered and I will raise my scores. However, I still have some followup questions for other concerns.

> Question 2

Consider I'm a user who wants to deploy these GBRTs. I would have some $\epsilon$ value in mind before I begin, eg, I can allow a 0.1 difference in loss if it allows me benefits elsewhere, say choosing fairer models. I train multiple GBRTs for 50 iterations each and get a set of models. I then filter them to find 'good models', i.e., those in my Rashomon set and would use them to calculate multiplicity, choose the model with the best fairness scores, etc.

Now instead of training for 50 iterations, what if I had trained for 100 iterations? What I don't understand is why would I change my threshold ($\epsilon$) to 0.2. Wouldn't I still only want to find benefits while making sure I'm just a 0.1 loss difference away from the best model? Maybe a different way to interpret this could be that under the fixed $\epsilon$, I'm less likely to get models (as noted by the authors that the same $\epsilon$ means smaller $\rho$). In other words, I'd have less number of models to choose from if I forced the same $\epsilon$ threshold. But I feel this is a more realistic setting, and in this case, my Rashomon set has shrunk, not grown!

One thing to note, the size of the Rashomon set is NOT a proxy for multiplicity. Thus, despite being a smaller set, this set of models can still have higher multiplicity, a bigger range of coverage in terms of fairness, and so on. So all the following results can, in principle, still exist. And of course, they do exist. But the narrative of increasing Rashomon set size is bothering me.

I may be missing or misinterpreting something. Happy to hear more clarification from the authors.

> Question 3

Ahh, I see, now the results make more sense. This was confusing at first. Please make sure to add the clarification and proper explanation on how to interpret the figure in the final version.