A Path to Simpler Models Starts With Noise
Authors: Lesia Semenova
Harry Chen
Ronald Parr
Cynthia Rudin
Venue: NeurIPS 2023 poster (2023)
Keywords: Rashomon Set
Simplicity
Interpretable Machine Learning
Model Selection
Model Multiplicity

Abstract: The Rashomon set is the set of models that perform approximately equally well on a given dataset, and the Rashomon ratio is the fraction of all models in a given hypothesis space that are in the Rashomon set. Rashomon ratios are often large for tabular datasets in criminal justice, healthcare, lending, education, and in other areas, which has practical implications about whether simpler models can attain the same level of accuracy as more complex models. An open question is why Rashomon ratios often tend to be large. In this work, we propose and study a mechanism of the data generation process, coupled with choices usually made by the analyst during the learning process, that determines the size of the Rashomon ratio. Specifically, we demonstrate that noisier datasets lead to larger Rashomon ratios through the way that practitioners train models. Additionally, we introduce a measure called pattern diversity, which captures the average difference in predictions between distinct classification patterns in the Rashomon set, and motivate why it tends to increase with label noise. Our results explain a key aspect of why simpler models often tend to perform as well as black box models on complex, noisier datasets.

A Path to Simpler Models Starts With Noise
Lesia Semenova Harry Chen Ronald Parr Cynthia Rudin
Department of Computer Science, Duke University chen084, 0aer ronald, parr, cynthia wywthia.rudin1 rudin edu
Abstract
The Rashomon set is the set of models that perform approximately equally well given dataset, and the Rashomon ratio is the fraction of all models in given hypothesis space that are in the Rashomon set. Rashomon ratios are often large for tabular datasets in criminal justice, healthcare, lending, education, and in other areas, which has practical implications about whether simpler models can attain the same level of accuracy as more complex models. An open question is why Rashomon ratios often tend to be large. In this work, we propose and study a mechanism of the data generation process, coupled with choices usually made by the analyst during the learning process, that determines the size of the Rashomon ratio. Specifically, we demonstrate that noisier datasets lead to larger Rashomon ratios through the way that practitioners train models. Additionally, we introduce measure called pattern diversity, which captures the average difference in predictions between distinct classification patterns in the Rashomon set, and motivate why it tends to increase with label noise. Our results explain a key aspect of why simpler models often tend to perform well as black box models on complex, noisier datasets.
Introduction
is possible that for many datasets, a simple predictive model can perform as well the best black box model - we simply have not found the simple model yet. Interestingly, however, we may be able infer whether such a simple model exists without finding it first, and may be able determine conditions under which such simple models are likely to exist.
We already know that many datasets exhibit the "Rashomon effect" (7]. which is that for many real-world tabular datasets, many models can describe the data equally well. there are many good models, it is more likely that least of them is simple (e.g., sparse) [3). Thus, key question in determining the existence of simpler models is to understand why and when the Rashomon effect happens. This is difficult question, and there has been little study of it. The literature Rashomon effect has generally been more practical, showing either that the Rashomon effect often exists practice (39
the
13 45). showing how to compute or visualize the of good models for a given 48). or trying to reduce underspeciffcatiio by learning diverse ensemble of models 225 37 However, no prior works have focused on understanding what causes this phenomenon in the first place.
dataset [52 14
15
32
53
54
Our thesis is that noise is both theoretical and practical motivator for the adoption of simpler models. Specifically, in this work, we refer to noise in the generation process that determines the labels. In noisy problems, the label is more difficult predict. Data about humans, such as medical data criminal justice data, are often noisy because many things worth predicting (such as whether someone will commit a crime within 2 years of release from prison, or whether someone will experience medical condition within the next year) have inherent randomness that is tied to random processes in the world (Will the person get new job? How will their genetics interact with their diet?). It might sound intuitive that noisy data would lead to simpler models being useful, but this is not
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

something most machine learning practitioners have internalized - even on noisy datasets, they often use complicated, black box models, to which post-hoc explanations are added. Our work shows how practitioners who understand the bias-variance trade-off naturally gravitate towards more interpretable modes in the presence of noise.
We propose path which begins with noise, is followed by decisions made by human analysts to compensate for that noise, and that ultimately leads to simpler models. In more detail, our path follows these steps: 1) Noise in the world leads to increased variance of the labels. 2) Higher label variance leads to worse generalization (larger differences between training and test/validation performance). 3) Poor generalization from the training set to the validation set is detected by analysts on the dataset using techniques such as pross-validation As a result, the analyst compensates for anticipated poor test performance in way that follows statistical learning theory. Specifically, they choose a simpler hypothesis space, either through soft constraints (i.e., increasing regulation), hard constraints (explicit limits on model complexity, or model sparsification), or by switching to simpler function class. Here, the analyst may lose performance on the training set but gain validation and test performance. 4) After reducing the complexity of the hypothesis space, the analyst's new hypothesis space has a larger Rashomon ratio than their original hypothesis space. The Rashomon ratio is the fraction of models in the function class that perform close to the empirical risk minimizer. It is the fraction of functions that performs aeproximatell-equaalee equally-well to the best one. This set of "good" functions is called the Rashomon set, and the Rashomon ratio measures the size of the Rashomon set relative to the function class. This argument (that lower complexity function classes leads to larger Rashomon ratios) is not necessarily intuitive, but show it empirically for 19 datasets. Additionally, we prove this holds for decision trees of various depths under natural assumptions. The argument boils down showing that the set of non-Rashomon set models grows exponentially faster than the set of models inside the Rashomon set. As a result, since the analyst's 's hypothesis space now has a large Rashomon ratio, relatively large fraction of models that are left in the simpler hypothesis are good, meaning they perform approximately as well as the best models in that hypothesis space. From that large set, the analyst may be able to find even a simpler model from a smaller space that also performs well, following the argument of Semenova et al. [39. As a reminder, in Step 3 the analysts discovered that using a simpler model class improves test performance. This means that these simple models attain test performance that is at least that of the more complex (often black box) models from the larger function class they used initially.
In this work, we provide the mathematics and empirical evidence needed to establish this path, focusing Steps 1, 2, and 4 because Step 3 follows directly (however, we provide empirical evidence for Step 3 as well). Moreover, for the case of ridge regression with additive attribute noise, we prove directly that adding noise the dataset results in increased Rashomon ratio. Specifically, the additive noise acts as f--regularization, thus it reduces the complexity of the hypothesis space (Step 3) and causes the Rashomon ratio to grow (Step 4).
Even if the analyst does not reduce the hypothesis space in Step 3, noise still gives us larger Rashomon sets. We show this by introducing pattem diversity, the average Hamming distance between all classification patterns produced by models in the Rashomon set. We show that under increased label noise, the pattern diversity tends to increase, which implies that when there is more noise, there more differences in model predictions, and thus, there could be more models in the Rashomon set. Hence, much shorter version of the path also works: Noise in the world causes an increase in pattern diversity, which means there are more diverse models in the Rashomon set, including simple ones.
It is becoming increasingly common to demand interpretable models for high-stakes decision domains (criminal justice, healthcare, etc.) for policy reasons such as faireess or transparency. Our work is possibly the first to show that the noise inherent in many such domains leads to technical justifications for demanding such models.
2 Related Work
Rashomon set. The Rashomon set, named after the Rashomon effect coined by Leo Breiman 77 is
based on the observation that often there are many equally good explanations of the data. When these
are contradictory, the Rashomon effect gives rise to predictive multiplicity [30 6 [8] Rashomon
sets have been used to study variable importance [55 14 42), for characterizing fairness 40 9 2
to improve robustness and generalization, especially under distributional shifts 37 25 to study
2

---

connections between multiplicity and counterfactual explanations [3 53 8 and to help in robust decision making [46.. Some works focused on trying to compute the Rashomon set for specific hypothesis spaces, such as sparse decision trees 52 generalized additive models [54], and decision lists [22 Other works focus on near-optimality find diverse set of solutions to mixed integer problems [1. set of targeted predictions under Bayesian model (3) or estimate the Rashomon volume via approximating model Reproducing Kernel Hilbert Space [II. Black et al. [6] shows that the predictive multiplicity metric defined as expected pairwise disagreement increases with expected variance over the models in the Rashomon set. On the contrary, we focus on probabilistic variance in labels in the presence of noise.
Metrics of the Rashomon set. To characterize the Rashomon set, multiple metrics have been pro- 49
18 [6. The Rashomon ratio [39]. and the pattern Rashomon ratio [38] measure the Rashomon set as a fraction of models or predictions within the hypothesis space; ambiguity and discrepancy R0 49 indicate the number of samples that received conflicting estimates from models in the Rashomon set; Rashomon capacity [8] measures the Rashomon set for probabilistic outputs. Here, we focus the Rashomon ratio and pattern Rashomon ratio. We also introduce pattern diversity. Pattern diversity is close to expected pairwise disagreement (as in Black et al. [6)) however, it uses unique classification patterns (see Appendix G
posed [39 38 30
Learning with noise. Learning with noisy labels has been extensively studied 34 especially for linear regression [5] and, more recently. for neural networks [44] to understand and model effects of noise. Stochastic gradient descent with label noise acts as an implicit regularizer [12 and noise has been added to hidden units [35], labels [41] or covariances (50) to prevent overfitting in deep
learning. When the labels are noisy, constructing robust loss [16]. adding slack variable for each
training sample [19], or early stopping [27] also helps to improve generalization. In this work, we
study why simpler models are often suitable for noisier datasets from the perspective of the Rashomon effect.
3 Notation and Definitions
Consider a training set of n data points S = {21, 22, .2.... 2n such that each 2; = (xx, y:) is drawn
i..d. from unknown distribution D, where X' R and we have binary labels ) {-1,1}, Denote F as hypothesis space, where f F obeys f X' + y. Let ő D x 3 + R be a 0-1 loss function, where for point & = (z, y) and hypothesis f. the loss function is (ff()) = = [(()))))) Finally, let iff) be empirical risk L(f) 1 Σ (ff())) and let f be an empirical risk minimizer: f E arg min yer L()). . If we want to specify the dataset on which ff was computed, we will indicate it by an index, fs-
The Rashomon set contains all models that achieve near-optimal performance and can be defined as: Definition 1 (Rashomon set). For dataset S, a hypothesis space F, and a loss function é. given 0 2 0, the Rashomon set Reea 0) is:
(F,()) (F i(s) i(f) + 0).
where f is an empirical risk minimizer for the training data S with respect to loss function Φz f E argmin L(f), and 0 is the Rashomon parameter.
Rashomon parameter 0 determines the risk threshold (L(ff) 9), such that all models with risk lower than this threshold are inside the set. For instance, if we stay within 1 % of the accuracy of the best model, then 0.01. Given parameter the true Rashomon set, containing all models with a bound on true risk Rsee (F,7) = (f E F L(f) < L(F)))+ 73 where f" is optimal model, f = arg min L(f).
O, we extend the definition to the true risk by defining
In this work, we study how noise influences the Rashomon set and choices that practitioners make in the presence of noise. We measure the Rashomon set in different ways, including the Rashomon ratio, pattern Rashomon ratio, and pattern diversity (defined in Section 6). For a discrete hypothesis space, the Rashomon ratio (39] is the ratio of the number of models in the Rashomon set compared
(F.0) where | denotes cardinality. It is possible to weight the hypothesis space by prior to define weighted Rashomon ratio if desired.
to the hypothesis space, Aratio 0) RR, F
3

---

Given hypothesis f and a dataset S, a predictive pattern (or pattern) is the collection of outcomes from applying f to each sample from S: p' = =f((z)) f..
We say that pattern p achievable on the Rashomon set if there exists f E Reet (F, 0) such that p' = p. Let pattern Rashomon set π (F, 0) = (r' : E (F, ( [xx))]]]=1 be all unique patterns achievable by functions from (J,, 0) on dataset S. Finally, let (FF be the pattern hypothesis set, meaning that it contains all patterns achievable by models in the hypothesis space, ( = {p' : E F, p (aar))];i1 The pattern Rashomon ratio is the ratio of patterns in the pattern Rashomon set to the
pattern hypothesis set: Rratio (F, 0)
TW
In the following sections, we walk along the steps of our proposed path. Rather than trying to prove these points for every possible situation (which would be volumes beyond what can handle here), we aim to find at least some way to illustrate that each step is reasonable in natural setting.
4 Increase in Variance due to Noise Leads to Larger Rashomon Ratios
4.1 Step 1. Noise Increases Variance
One would think that something as simple as uniform label noise would not really affect anything in the learning process. In fact, we would expect that adding such noise would just uniformly increase the losses of all functions, and the Rashomon set would stay the same. However, this conclusion is (surprisingly) not true. Instead, noise adds variance to the loss, which, in turn, prevents us from generalizing.
For infinite data distribution D consider uniform label noise, where each label is flipped independently with probability P < 2- If ÿ a flipped label, P(ù + y) = p. If the empirical risk of f is over 1 after adding noise, we transform f to -.. For given model f E let (J; D) be the variance of the loss, meaning that (f, D) Varz-D {J,, z). We show in the following theorem that, for given f F. label noise increases the variance of the loss.
Theorem 2 (Variance increases with label noise). Consider infinite true data distribution D, and uniform label noise, where each label flipped independently with probability p. Let D, denote the noisy version of DD Consider 0-1 loss I, and assume that there exists at least one function f F such that [f( < } -V, For a fixed f E F, let o² (J, be the variance of the loss, (f, = VaraaD, (f,,)) 2) on data distribution D. For any < p1 < p2 < 2
(f( < (f,,
The proof of Theorem 2 is in Appendix A This covers the uniform noise case, but variance increases more generally, and we prove this for several other common cases in Appendix A More specifically, we show that the variance increases with other types of label noise, such as non-uniform label noise (see Theorem 12 in Appendix A) and margin noise (see Theorem [5] in Appendix [A). For non- uniform label noise, for sample 2 = (zz y), each label y is flipped independently with probability Pa. meaning that noise can depend on x. This noise model is more realistic than uniform label noise and allows modeling of cases when one sub-population has much more noise than another. We model margin noise such as that which arises from high-dimensional Gaussians. Because of the central limit theorem, data often follow Gaussian distributions, therefore this noise is realistic and models mistakes near decision boundary. Label noise in datasets is common. In fact, real-world datasets reportedly have between 8.0% and 38.5% label noise 44 43
We hypothesize that a significant amount of label noise in real world datasets is combination of Gaussian (due the central limit theorem) and random noise (for example, because of clerical errors causing label noise).
24
28 51
For the true Rashomon set Rsee (F, 7),, we consider the maximum variance for all models in the true set: x² suppe Var,-D z). Then, from Theorem 2 we have that maximum expected variance over the Rashomon set increases with noise.
Corollary 3 (Maximum variance increases with label noise). Under the same assumptions as in Theorem 2 we have that
sup f fe (F,1)
d((,Dp))
sup SERar (F
d² dJ(..Dp2))
The next step is to show that this increased maximum variance leads to worse generalization.

---

4.2 Step 2. Higher Variance Leads to Worse Generalization
Here we use an argument based on generalization bounds. Generalization bounds have been the key theoretical motivation for much of machine learning, including support vector machines (SVMs), because the margin that SVMs optimize appears in bound. While bounds themselves are not directly used in practice, the terms in the bounds tend to be important quantities in practice. Our bound cannot be calculated in practice because it uses population information on the right side, but it still provides insight and motivation.
Unlike standard bounds, we will use the fact that the user is using empirical risk minimization, and cross- validation to assess overfitting. Thus, for f. there are two possibilities: f is in the true Rashomon set, or it is not. it is not, then for the empirical risk minimizer f. the difference between the true and the empirical risk must be at least y which will be detected with high probability in vross-validation (20 33 In that case, the user will reduce their hypothesis space and we move to Step 3. If f is in the true Rashomon set, it obeys the following bound.
Theorem 4 (Variance-based "generalization bound"). Consider dataset S, 0-1 loss I, and finite hypothesis space F. With probability least 1 - 6, we have that for every f E Reee (F))):
[Rsa((F.)) )
20
RRset [Rsce(F, (F,1)l)
L(f) L(f) - 3n
log
log
(I)
where 0² = -usssupeeeeeee Sua Var ((f 2). and n is number of samples in S = {2)) ~ D.
The proof of Theorem is in Appendix C Note that generalization bounds are usually based on Hoeffding's 's inequality (see Lemma 17), which is special case of Bernstein's 's inequality (see Lemma
16). In fact, we show in Appendix B that Bernstein's inequality, which we used to prove Theorem for given f. Theorem 4 is easily generalized to continuous hypothesis spaces through a covering argument over the true Rashomon set (as an example, see Theorem 20)o where the complexity is measured as the size of the cover over the true Rashomon set instead of the number of models in the true Rashomon set.
4 can be sharper than Hoeffding's when the variance is less than of
Let Let n) 2 log ([Reee(F())) which is the first term in the bound I in Theorem 4 According
3n. to Theorem in Semenova al. [39 under random label noise, the true Rashomon set does not decrease in size. Therefore, c(F, m)) at least does not decrease with more noise as it depends only on complexity. However, the second term / /3o2c(FF.n n) depends on the maximum loss variance, which increases with label noise, as motivated in the previous section. This means with more noise in the labels, we would expect worse generalization, which would generally lead practitioners who using a validation set to reduce the complexity of the hypothesis space.
As discussed earlier, we use cross voliddaalo to assess whether of overfits. From Proposition 5 (proved in Appendix D) we infer that if the empirical risk minimizer (ERM) does not highly overfit, it has high chance to be in the true Rashomon set and thus Theoremaappo applics.
Proposition (ERM can be close to the true Rashomon set). Assume that through the cross-validation
process, we can assess & such that L(f) - i(f) < E with high probability (at least 1 - Eg) with
respect to the random draw of data. Then, for any >> 0, with probability at least 1 - e 2ne= 6g
with respect to the random draw of training data, when E + S 7, then f E Raee(F,
4.3 Step 3. Practitioner Chooses Simpler Hypothesis Space
We have shown earlier that noisier datasets lead to higher variance and worse generalization. The question we consider here is whether one can see the results of these bounds in practice and would actually reduce the hypothesis space. For example, considered four real-world datasets and the hypothesis space of decision trees of various depths. In Figure | (a) we show that as label noise increases, so does the gap between risks (1- accuracy) evaluated on the training set and on hold out dataset for a fixed depth tree, and thus, as a result, during the validation process, the smaller depth would be chosen by a reasonable analyst. We simulated this by using cross validation to select the optimal tree depth in CART, as shown in Figure T (b). As predicted, the optimal tree depth decreases as noise increases. We also show that similar trend happens for the gradient boosted trees in Figure
5

---

in Appendix K
More specifically, with more noise, the best number of estimators, as chosen based on cross vross-aali decreases. We describe the setup in detail in Appendix K.2
Vall Accurary
0.015
Compas
FICO
Compas FiCD
0.010
0.005
Talco Bin
0.005
Tolco Bin
Monks
6.1
6.00
0.05 0.10
0.15 0.ã 0.25
0.00
0.05
020 Label noise,
0.10
0.15
0.5
0.00
0.55
0.10 0.1s 0.20 0.25
Label noise,
Label noise,
(h)
Practitioner's validation process in the presence of noise for CART. For fixed tree depth, as we add noise, the gap between training and validation accuracy increases (Subfigure a). As we use cross validation to select tree depth, the best tree depth decreases with noise (Subfigure b).
Figure 1:
4.4 Step 4. Rashomon Ratio is Larger for Simpler Spaces
For simpler hypothesis spaces, it may not be immediately obvious that the Rashomon ratio is larger, i.e., a larger fraction of simpler model class consists of "good" models. Intuitively, this because the denominator of the ratio (the total number of models) increases faster than the numerator (the number of good models) as the complexity of the model class increases. As we will see, this is because the good models in the simpler model class tend to give rise to more bad models in the more complex class, and the bad models do not tend to give rise to good models as much. We explore two popular model classes: decision trees and linear models. The results thus extend to forests (collections of trees) and generalized additive models (which are linear models in enhanced feature space).
Consider data that live a hypercube (e.g.. the data have been binarized, which is a common and a hypothesis space fully grown trees (complete trees with the last level also filled) of given depth d. Denote this hypothesis space as Fa. For example, a depth I tree has node and 2 leaves. Under natural assumptions on the quality of features classifiers and the purity of the leaves of trees in the Rashomon set, show that the Rashomon ratio is larger for hypothesis spaces of smaller-depth trees.
pre-processing step 29 3 2
Proposition 6 (Rashomon ratio is larger for decision trees of smaller depth). For dataset S XXY with binary feature matrix X E {0, 1] 1m consider a hypothesis space Fa of fully grown trees of depth d. Let the number of dimensions
< 2²" Assume: (Leaves are correct) all leaves in all trees in the Rashomon set have at least [On] more correctly classified points than incorrectly classified points; (Bad features) there is a set of 1isd 2 d "bud" features such that the empirical risk minimizer of models using only the bad features is not in the Rashomon set. Then Ryotio (F++1.0) < Ryatio (F (Fa50).
The proof of Proposition 6 in Appendix Both assumptions are typically satisfied in practice.
To demonstrate our point, we computed the Rashomon ratio and pattern Rashomon ratio for 19 different datasets for hypothesis spaces of decision trees and linear models of different complexity (see Figure 2). As the complexity of the hypothesis space increases, we see an obvious decrease in the Rashomon ratio and pattern Rashomon ratio.
To compute the Rashomon ratio, for trees, we used TreeFARMS [52), which allows us to enumerate the whole Rashomon set for sparse trees. For linear models, designed two-step approach that allows us to compute all patterns in the Rashomon set. First, for every sample z; we solved a simple optimization problem that checks if there exists model in the Rashomon set that misclassifies this sample. If there is no such model, changing the label 2; will not add more patterns to the Rashomon set, therefore, lead to patterns outside of the Rashomon set. We describe our approach for pattern computation in detail in Appendix K. and discuss the experimental setup in Appendix K.4
ignore 24. In the second step, grew search tree and bounded all paths that
Completion the Path. After reducing the complexity of the hypothesis space Step 3, the practitioner has already arrived at simpler hypothesis space, which is the goal. Continuing on the

---

log Rashemen ratio. %
log pattem Aratio. 5%
-100
-200
Wine
-300
Seeds
-10
Penglán
Digis
-400
Immunotherapy
12
2
3
5
6
Tree death
Number of non-zero coefficients
(a)
(b)
Figure 2: Calculation showing that the Rashomon ratio (a) and pattern Rashomon ratio (b) decrease for the hypothesis space of decision trees fixed depth from to for 14 different datasets (a) and for the hypothesis space of linear models of sparsity from represents a different dataset, each dot represents the log of the Rashomon ratio or pattern Rashomon move a more complex hypothesis space.
4 for 5 different datasets (b). Each line
ratio. Both ratios decrease
path, they can reduce complexity further. Specifically, they find a larger Rashomon ratio for the newly chosen lower complexity hypothesis space according to Step 4. As reminder of the thesis of Semenova et al. [39], with large Rashomon ratios, there are many good models, among which may exist even simpler models that perform well. Thus, the path, starting from noise, is powerful way to explain what we see practice, which is that simple models often perform well 17
Note that to follow the path, the machine learning practitioner does not need to know the exact amount of noise. As long they suspect some noise present in the dataset, the results of this paper apply, and the practitioner would expect good performance from simpler models.
Rashomon Ratio for Ridge Regression Increases under Additive Attribute Noise
For linear regression, adding multiplicative or additive noise the training data known to be equivalent to regularizing the model parameters [5]. Moreover, the more noise is added, the stronger this regularization is. Thus, noise leads directly to Step and choice of a smaller (simpler) hypothesis space. Also, for ridge regression, the Rashomon volume (the numerator of the Rashomon ratio) can be computed directly (39) and depends on the regularization parameter. Building upon these results, prove that noise leads to an increase of the Rashomon ratio (as in Step 4 of the path).
Given dataset S, the ridge regression model is learned by minimizing the penalized sum of squared errors: L(w) = (..s(w) + CwTw, w. where (LS(w) = = Ei= (xT - y:) is the least squares loss, C' is regularization parameter, and w I. is parameter vector for a linear model = wTx.
We will assume that there is a maximum loss value f.max. such that any linear model that has higher regularized loss than Lmax is not being considered within the hypothesis space. For instance, an upper bound for Luxx is the value of the loss at the model that is identically Ô, namely L = 1 Σ, v². Thus, for every reasonable model best possible value of the least squares loss is f... O, and therefore we get that Cw Tw S f or alternatively, wf w S Lmax//C. This defines the hypothesis space as an torn ball m- dimensional space, the volume of which we can compute.
w²'x.. E
i(w) < Lmaxx- On the other hand, the
To measure the numerator of the Rashomon ratio we will use the Rashomon volume ((Reet (ise(( (F, O)),
as defined Semenova et (39]. In the case of ridge regression, the Rashomon set an ellipsoid in m-dimensions, thus the Rashomon volume can be computed directly. Therefore, we have the Rashomon ratio as the ratio of the Rashomon volume to the volume of the norm ball that defines the hypothesis space.
Next, we show that under additive attribute noise, the Rashomon ratio increases:
Theorem 7 (Rashomon ratio increases with noise for ridge regression). Consider dataset S X X.V, X is non-zero matrix, and hypothesis space of linear models F {f = w
IR" w o.
7

---

Lmax/Cu Let such that (O) (A added to every sample: x', ===;, =1+ much noise we add to the dataset. For ridge regression, if X1 < X2, then the Rashomon ratios obey Ryatios, (F,0)) < Brations (F.0)).
O, I is identity matrix), be i..dd. noise vectors + G. Consider options X 0 and X2 > that control how
The proof of Theorem is in Appendix F Note that while in Theorem 7 we directly show that adding noise to the training data is equivalent stronger regularization leading us directly Step 3, Steps I and 2 of the path identified in the previous section are automatically satisfied. We formally prove that additive noise still leads to an increase the variance of losses for least squares loss (similar to Theorems 2 12 and 15 in Theorem 19 Appendix (F) and we show that an increase in the maximum variance of losses leads worse generalization bound (similar Theorem 4 for the squared loss in Theorem 20 in Appendix F
Returning to the Path. For ridge regression, have built direct moise-to-Rashomone argument showing that, in the presence of noise, the Rashomon ratios are larger. As before, for larger Rashomon ratios, there are multiple good models, including simpler ones that are easier find.
Rashomon Set Characteristics in the Presence of Noise
Now we discuss a different mechanism for obtaining larger Rashomon sets, Suppose the practitioner knows the data noisy. They would then expect a large Rashomon set, which we speculate in this section is explained by noise in the data. To show this, we define pattern diversity as a characteristic of the Rashomon set and show that it is likely to increase with label noise. Pattern diversity is empirical measure of differences in patterns on the dataset. It computes the average distance between the patterns, which allows not only to assess how large the Rashomon set is but also how diverse it is. Once the practitioner knows they have a large Rashomon set, they could hypothesize from the reasoning in Semenova al. 33 that simple model might perform well for their dataset.
6.1 Pattern Diversity: Definition, Properties and Upper Bound
Recall that n (F,0) is the set of unique classification patterns produced by the Rashomon set of F with the Rashomon parameter 0.
Definition 8 (Pattern diversity). For Rashomon set Ree((F,0). 0). the pattern diversity div (F,0) is defined as:
div( (F, n IIIIII
1
Σ
Σ
H Pk),
JEn
AIII (F.
and H (p3. PP)) = -i= 1l (nttril is the Hamming distance (in our case it computes the number of samples at which predictions are different), and denotes cardinality.
where n = | II IT=
0},, (
Pattern diversity measures pairwise differences between patterns of functions in the pattern Rashomon set. Pattern diversity is in the range [0, 1). where is 0 the pattern set contains one pattern or no patterns. Among different measures of the Rashomon set, the pattern diversity is the closest to the pattern Rashomon ratio (38) and expected pairwise disagreement (as in (6]). In Appendix G we discuss similaritics and differences between pattern diversity and these measures.
Given a sample 2,. let a, i Ek= [pj:= where p is 7th index of the hthh pattern, denote the probability with which patterns from the pattern Rashomon set classify 2, correctly. We will call a, sample agreement over the pattern Rashomon set. When a, = 1, then all patterns agreed and correctly classified 2;. If a; 2.2 only half of the models were able correctly predict the label. As will show, when more samples have sample agreement near 1, we have higher pattern diversity. We can compute pattern diversity using average sample agreements instead of the Hamming distance according to the theorem below.
Theorem 9 (Pattern diversity via sample agreement). For 0-1 loss, dataset S, and pattern Rashomon set NI (F,60 8), pattern diversity can be computed as div( RRe((F,6)) n "E a3(1 az), where a, 1 En =p: is sample agreement over the pattern Rashomon set.
8

---

The proof of Theorem 9 is in Appendix H In Theorem 23 in Appendix | we show that average sample agreement (over all samples 2,) inverslly proportional to the average loss of the patterns from the pattern Rashomon set. Using this intuition, we can upper bound the pattern diversity by the empirical risk of the empirical risk minimizer and the Rashomon parameter
Theorem 10 (Upper bound on pattern diversity). Consider hypothesis space F, 0-1 loss, and empirical risk minimizer f. For any 0 z 0, pattern diversity can be upper bounded by
diu(R (F, 0)) 2(((f) + 0) (1()) 8)) 28.
(2)
The proof of Theorem i0 is in Appendix [ The bound (2) emphasizes how important the performance of the empirical risk minimizer is for understanding pattern diversity. dataset is well separated so that the empirical risk is small, then pattern diversity will also be small, there not many different ways to misclassify points and stay within the Rashomon set. As dataset becomes noisier, on average, we expect the empirical risk to increase and thus pattern diversity well. We will show theoretically and experimentally that pattern diversity is likely to increase under label noise.
6.2 Label Noise is Likely to Increase Pattern Diversity
Let Sp be a version of S with uniformly random label noise, creating randomly perturbed labels y with probability < p < 1: P( * y4) = p. Let ((S)) be the uniform distribution over all Sp- From Theorem 10 denote the upper bound on pattern diversity as Unio (Rger (F,0))
(i(( + () (i()) 0)) + 20. We show that increases with uniform label noise.
Theorem 11 (Upper bound on pattern diversity increases with label noise). Consider a hypothesis space F, 0-1 loss, and a dataset S. Let E (0, 1) be the probability with which each label yi is flipped independently, and let Sp ~ (2(Sp) denote a noisy version of S. For the Rashomon parameter
0 2 O, if fer Es, I.s, (f) < - and is((ss) < 3, then adding noise to the dataset increases the upper bound on pattern diversity of the expected Rashomon set:
Usio (Reett (F,0)) < Univ Udiv -acs,) 8p (F,0)).
The proof of Theorem I1 is in Appendix | In the general case, it is challenging to find a closed-form formula for pattern diversity design a lower bound without strong assumptions about the data distribution or the hypothesis space. Therefore, we empirically examine the behavior of pattern diversity alongside other characteristics of the Rashomon set for different datasets and show these characteristics tend to increase with more noise.
6.3 Experiment for Pattern Diversity and Label Noise
We expect many different datasets to have larger Rashomon set measurements as data become more noisy. As before, we consider uniform label noise, where each label is flipped independently with probability p. For different noise levels, we computed diversity, and the number of patterns in the Rashomon set for 12 different datasets for the hypothesis space of sparse decision trees of depth 3 (note that we underfitted for some of the datasets); see Figure 3 (a)-(b). For every dataset, we introduced up to 25% label noise (p E [0, 0.25)), or Accuracy( ( 50%, whichever is smaller. This means that data with lower accuracy (before adding noise) will have shorter plots, since noise along the horizontal axis of our plots in Figure 3 For each noise level p. we performed 50 draws of Sp. and for each draw Sp we recomputed the Rashomon sct. For decision trees we used TreeFARMS (52), which allows us to compute the number of trees in the Rashomon set. We set the Rashomon parameter to 5%. We discuss results for the hypothesis space of linear models in Appendix K.3
Some key observations from Figure 3 First, the number of trees and patterns in the Rashomon set on average increases with noise. This means that the Rashomon ratio and pattern Rashomon ratio increase with noise as well since the hypothesis space stays the same. Second, datasets, that initially had higher empirical risk (e.g., COMPAS, Coffee House, FICO) tend to have more models in the Rashomon set (and thus higher Rashomon ratios) as compared to datasets with lower empirical risk (Car Evaluation, Monksl, Monks3). Finally, pattern diversity, on average, tends to increase with noise for the majority of the datasets.

---

300
Monks
0.2
Monks
Number pattems
BGW
Number of trees
100
Restaurant
Diversity
0.0
0.1
0.2
0.0
0.1
0.2
0.1
0.2
300
Monkss
200
FKO
100
0.2
Bar
100
0.1
0.00
0.05
0.10
0.25
0.00
0.05
0.10
0.15
0.00
0.05
0.10
0.15
Label noise,
Label noise,
Label noise,
(a)
(b)
(c)
Figure 3: Rashomon set characteristics such the number of trees in the Rashomon set (Subfigure
a), the number of patterns in the Rashomon set (Subfigure b), and pattern diversity (Subfigure c) tend to increase with uniform label noise for hypothesis spaces of sparse decision trees. For readability, the top row of the figure shows datasets with lower empirical risk and the bottom row shows datasets with higher empirical risk.
Returning to the Path. If the practitioner observes more noise in the data, it could already the case that the Rashomon set is large. Then, there many good models, among which simpler or interpretable model are likely to exist [39]
7 Limitations
While believe our results have illuminated that the Rashomon effect often exists when data are noisy, the connection between noise and increased Rashomon metrics is mostly supported by experiments, rather than a tight set theoretical bounds. Specifically, we do not have a lower bound on diversity nor a correlation between diversity and the pattern Rashomon ratio (or Rashomon ratio) yet. This connection deserves further exploration and strengthening.
In previous sections, we showed that we expect an increase in pattern diversity while adding more label noise. In Section 6..] we also observe an increase in the number of trees and patterns in the Rashomon set under label noise. In both cases, we used (-1 loss. While in Section 5 we studied ridge regression (and thus used squared loss), ways to extend our results (both experimental and theoretical) to different distance-based classification loss functions are not yet fully clear. In the case of classification with distance-based losses, such as exponential loss, the effect of label noise can be difficult to model without taking properties of the data distribution into account. For example, regardless the amount of noise the dataset, single misclassified outlier could essentially define the Rashomon set. The exponential loss could be very sensitive to the position of this outlier, leading to a small Rashomon set. This does not apply to the analysis this paper, since the 0-1 loss we used is robust to outliers. Perhaps techniques that visualize the loss landscape [26) can be helpful in characterizing Rashomon set for distance-based classification losses.
Conclusion
Our results have profound policy implications, they underscore the critical need to prioritize interpretable models in high-stakes Docision-making In world where black box models are often used for high-stakes decisions, and yet the data generation processes are known to noisy, our work sheds light on the false premise of this dangerous practice that black box models are likely to be more accurate. Our findings have particular relevance for critical domains such as criminal justice, healthcare, and loan decisions, where individuals are subjected to the outputs of these models. The use of interpretable models these areas can safeguard the rights and well-heing of these individuals and ensure that decision maainn processes are transparent, fair, and accountable.
10

---

Acknowledgments
We gratefully acknowledge support from grants DOE DE-SC0023194, NIH/NIDA ROI DA054994, and NSF IIS-2130250.
References
[1] Izuwa Ahanor, Hugh Medal, and Andrew C Trapp. DiversiTree: A new method to efficiently compute diverse sets of near-optimal solutions to mixed-integer optimization problems. IN- FORMS Journal on Computing, 2023.
[2] UIrich Aïvodji, Hiromi Arai, Sébastien Gambs, and Satoshi Hara. Characterizing the risk of fairwashing. In Advances in Neural Information Processing Systems, volume 34, pages 14822 14834, 2021.
[3] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 35-44 2017.
[4] Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651-1666 1998.
[5] Chris Bishop. Training with noise is equivalent to Tikhonov regularization. Neural Compu- lation, 7(1):108-116, 1995.
[6] Emily Black, Manish Raghavan, and Solon Barocas. Model multiplicity; Opportunities, con- cerns, and solutions. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 850-863, 2022.
[7] Leo Breiman. Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical Science, 16(3):199-231 2001.
(8] Marc-Etienne Brunet, Ashton Anderson, and Richard Zemel. Implications of model indetermi- nacy for explanations of automated decisions. In Advances in Neural Information Processing Systems, volume 35, pages 7810-7823, 2022.
[9] Amanda Coston, Ashesh Rambachan, and Alexandra Chouldechova. Characterizing fairesss over the set of good models under selective labels. International Conference on Machine Learning, pages 2144-2155 PMLR, 2021.
[10] Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Trans. Electron. Comput., 14:326-333 1965.
[11] Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(11:1-49 2002.
[12] Alex Damian, Tengyu Ma, and Jason D Lee. Label noise sgd provably prefers flat global minimizers. In Advances Neural Information Processing Systems, volume 34, pages 27449- 27461, 2021.
[13] Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al. Under- specification presents challenges for credibility in modern machine learning. The Journal of Machine Learning Research, 23(1)10237-10297 2022.
[14] Jiayun Dong and Cynthia Rudin. Exploring the cloud of variable importance for the set of all good models. Nature Machine Intelligence, 2(12):810-2) 2020.
[15] Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models are wrong, but many are useful: Learning a variable's importance by studying an entire class of prediction models simultancously. Journal of Machine Learning Research, 20(177):1-81, 2019.

---

[16] Aritra Ghosh, Himanshu Kumar, and P Shanti Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 31, 2017.
[17] Robert C. Holte. Very simple classification rules perform well on most commonly used datasets. Machine Learning, 1 11()):63-1, 1993.
[18] Hsiang Hsu and Flavio Calmon. Rashomon capacity: A metric for predictive multiplicity classification. In Advances in Neural Information Processing Systems, volume 35, pages 28988- 290000, 2022.
[19] Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference on Learning Representations, 2020.
[20] Michael Kearns. A bound on the error of cross validation using the approximation and esti- mation rates, with consequences for the training-tess split. In Advances in Neural Information Processing Systems, volume 8, 1995.
[21] Fahime Khozeimeh, Roohallah Alizadehsani, Mohamad Roshanzamir, Abbas Khosravi, Pouran Layegh, and Saeid Nahavandi. An expert system for selecting wart treatment method. Computers in biology and medicine, 81:167-175, 2017.
[22] Fahime Khozeimeh, Farahzad Jabbari Azad, Yaghoub Mahboubi Oskouei, Majid Jafari, Shahrzad Tehranian, Roohallah Alizadehsani, and Pouran Layegh. Intralesional immunotherapy compared to cryotherapy in the treatment of warts. International journal of dermatology. 56(4):
474 478, 2017.
[23] Daniel R Kowal. Fast, optimal, and targeted predictions using parameterized decision analysis. Journal of the American Statistical Association, 11 1875 1886, 2022.
[24] Kuang-Huel Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for scalable image classifier training with label noise. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5447-5456, 2018
[25] Yoonho Lee, Huaxiu Yao, and Chelsea Finn. Diversify and disambiguate: Out-of-distribution robustness via disagreement. In The Eleventh International Conference on Learning Represen- tations, 2023.
[26] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, volume 31, 2018.
[27] Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping provably robust to label noise for overparameterized neural networks. International conference artificial intelligence and statistics, pages 4313-4324. PMLR, 2020.
[28] Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool. Webvision database: Visual learning and understanding from web data. arXiv preprint arXiv:1708.02888 2017.
[29] Jimmy Lin. Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pages 1150-6160. PMLR, 2020.
[30] Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification, In International Conference on Machine Learning, pages 6765-6774. PMLR, 2020.
[31] Blake Mason, Lalit Jain, Subhojyoti Mukherjee, Romain Camilleri, Kevin Jamieson, and Robert Nowak. Nearly optimal algorithms for level set estimation. In International Conference on Artificial Intelligence and Statistics, pages 7625-7658. PMLR, 2022.
[32] Kota Mata, Kentaro Kanamori, and Hiroki Arimura. Computing the collection of good models for rule lists. arXiv preprint arX1v:2204.11288 2022.
12

---

[33] Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25:161-193, 2006.
[34] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in Neural Information Processing Systems, volume 26, 2013.
[35] Hyeonwoo Noh, Tackgeun You, Jonghwan Mun, and Bohyung Han. Regularizing deep neural networks by noise: Its interpretation and optimization. In Advances Neural Information Processing Systems, volume 30, 2017.
[36] Martin Pawelczyk, Klaus Broelemann, and Gjergii Kasneci. On counterfactual explanations under predictive multiplicity. In Conference on Uncertainty in Artificial Intelligence, pages 809-818, PMLR, 2020.
[37] Andrew Ross, Weiwei Pan, Leo Celi, and Finale Doshi-Velez. Ensembles of locally independent prediction models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5527-5536, 2020.
[38] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistics Surveys, 16:1 1-8,, 2022.
[39] Lesia Semenova, Cynthia Rudin, and Ronald Parr. On the existence of simpler machine learning models. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 1827-1858, 2022.
[40] Ali Shahin Shamsabadi, Mohammad Yaghini, Natalie Dullerud, Sierra Wyllie, Ulrich Aīvodji, Aisha Alaagib, Sébastien Gambs, and Nicolas Papernot. Washing the unwashable On the (im)possibility of fairwashing detection. In Advances in Neural Information Processing Systems, volume 35, pages 14170-14182, 2022.
[41] Christopher J Shallue, Jachoon Lee, Joseph Antognini. Jascha Sohl-Dickstein Roy Frostig, and George E Dahl. Mcasuring the effects of data parallelism on neural network training. arXiv preprint arXiv: 036600, 2018
[42] Gavin Smith, Roberto Mansilla, and James Goulding. Model class reliance for random forests. In Advances in Neural Information Processing Systems, volume 33, pages 22305-22315,, 2020.
[43] Hwanjun Song, Minseok Kim, and Jae-Gil Lee. Selfie: Refurbishing unclean samples for robust deep learning. In International Conference on Machine Learning, pages 5907-5915. PMLR, 2019.
[44] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae- Gil Lee. Learning from noisy lahels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[45] Damien Teney, Maxime Peyrard, and Ehsan Abbasnejad. Predicting is not understanding: Recognizing and addressing underspecification machine learning. Computer ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Purt XXIII, pages 358-476.77 Springer, 2022.
[46] Theja Tulabandhula and Cynthia Rudin. Robust optimization using machine learning for uncertainty sets. In Proceedings of the International Symposium on Artificial Intelligence and Mathematies (ISAIM), 2014.
[47] Sicco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In Integration of Al and OR Techniques in Constraint Programmiing: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings 14, pages 103. Springer, 2017.
[48] Zijie J Wang, Chudi Zhong, Rui Xin, Takuya Takagi, Zhi Chen, Duen Horng Chau, Cynthia Rudin, and Margo Seltzer. TimberTrek: Exploring and curating sparse decision trees with interactive visualization. 2022 IEEE Visualization and Visual Analytics (VIS), pages 60-64. IEEE, 2022.
13

---

[49] Jamelle Watson-Daniels, David Parkes, and Berk Ustun. Predictive multiplicity in probabilistic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10306-10314, 2023.
[50] Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba. An empirical study of large-batch stochastic gradient descent with structured covariance noise. arXiv preprint arXiv: petp::902000000 2019.
[51] Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, pages 2691-2699, 2015.
[52] Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi. Margo Seltzer, and Cynthia Rudin. Exploring the whole rashomon set of sparse decision trees. In Advances in Neural Information Processing Systems, volume 35, pages 14071 1-071-160 1-14444, 2022.
[53] Tom Yan and Chicheng Zhang. Margin- aargin-dittancing for safe model explanation. In Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 5104-5134. PMLR, 28-30 Mar 2022.
[54] Chudi Zhong, Zhi Chen, Jiachang Liu, Margo Seltzer, and Cynthia Rudin. Exploring and interacting with the set of good sparse generalized additive models. Advances in Neural Information Processing Systems, 2023.
14

---

Supplemental materials
A Path to Simpler Models Starts With Noise
A Proof for Theorem 2
We state and prove Theorem below.
Theorem 2 (Variance increases with label noise). Consider infinite true data distribution DD and uniform label noise, where each label slipped independently with probability p. Let DD denote the noisy version of DD Consider 0-1 loss I, and assume that there exists at least one function E such that Lp( < %. For a fixed f E F, let of. be the variance of the loss, o² (J, = Var [ff, 2) on data distribution D For any < Pr < P2 < 2
< <
Proof. Recall that the true risk for 0-1 loss [D( = (==(,,))= ([]] :)]
(
Without loss of generality, let y E {0, 13. Drawing from 2p Dp equivalent to drawing D and changing label to y with probability p. More explicitly, let r Bernouli(p). then the flipped label XOR(y, n) [w For any given f
have that:
(f) BerrBer'y (( X
Ber (
[z()) (1 7)] + (er)Bo(()) ((aN) [[]
E E Be [ (1 -1]]] + E Bew [[)
E(r.))> [(((())))]] Be) [11 -)]] + B( [1 [1(()))=)) Ey Ber(e) [v]]
= (1 p) (aay)>D [((()))))]] + ( [=(
(1 p) ((ay)) [((())))))
+ + (11--(E,))DD (ay)) ((())))))
(1 ()) + (1-
(1 (p)
Note, following the technique above, a similar statement is true about dataset S instead of true distribution D, meaning that for a given f E F,
Es, (s, = (1- +
(3)
Recall that we take expectation with respect to different ways of adding noise to labels, therefore Sp and S have the same but different y. We do not use (3) for the proof of Theorem but use it in Appendix[]
For true distribution D, since is 0-1 loss, then for given model f. [(f,)) is Bernoulli distributed with mean PBe En-D [(f, z) LD(J) and variance of = PBer (1- (1-PBer) = LD (f)((((1 Therefore, the expected variance for given model f E [Fe 7) on distribution Dp is:
Varz~D, [( =]]= = ED, Lo, ( - (f))
ED, LD, (f) ED, RD, (J))
ED, LD, (f) ED, (LD, (f))²
LE, Lf. (Ep, LD, - Vord,
-Lo(f)1 -p) + (Lp(f)(1 2p) p)) VarD,, (LD,
=Lo(f) (p) -ppp1 - 2p)) [1) -2p)² p -'a'-VarD,, (LD,))
= -1 - (Lpp)))L((() - L3()))
+ -Vuu-rr,,(
= - = (o(f)(1-Lo(0))))) ((1-)) - -Varr,,,ILDptth
(1 (1-2p)² (Lo(f(1- = +pp)))pp1111 p),
15

---

Note that, by our assumption, there exists f such that Lx(f) < s0 Lo( < - 7 where f is optimal model. Then for any fixed f F, get LD(f) LD( + < 1 which implies that (o(s)(1 Lo)() <
For (0, 2), Var=~D, [1( 2)] is monotonically increasing in p. since:
① 3p
i
Var Var [f]=)]]]
0p -()))))())))()L))))))))))
p)]
-4(1 - 2p) + 2p)
21) (1 ALD(f)(1 LD(f)))
11-2x x ) (1 4x =0. =
Consider P1 < p2. Since Vars~D, [l[ 2)] is monotonically increasing in p for fixed f, then (f, < < p,)), and we proved that variance increases with random uniform label noise.
In Theorem the statement the theorem correct for any fixed f E F. Corollary 3 follows directly from Theorem 2 Here, instead of fixed model F, we consider models in the Rashomon sets that maximize expected variance.
Corollary 3 (Maximum variance increases with label noise). Under the same assumptions as in
Theorem 2 have that
fe SeR (F.t) (f,Dp.)
(f
sup
sup SERueD (Fr)
Proof. Let f and f be maximizers of the variance of the loss in their respective Rashomon sets:
frup E arg
sup /ERectD (Fir)
VarznD, [((f2)).
muu E arg
sup PERect (Fr)
Var Varz~D, [1({.))]
Given that for any f Reato (F, 7), Varzaa,, [((,,) 2) < Varz~Dey [122", ,=]] and since
Var:wP, []] is monotonically increasing in we have that:
sup fER (F:))
D2()DDp)) VaraD, [(S ,2]
VarzwD,n [[sruup [2]
VarenDoy [(Seeup =)]
sup (f. D Pp2)
SERuiopp (Fr)
Next, we generalize the statement of Theorem to the non-uniform label noise case, where each sample = (x. y) is flipped with probability Pzr that depends on æ. We show that under this non-uniform label noise, the variance of the loss increases in Theorem [2
Theorem 12 (Variance increases with non-unt non-uniform label noise). Consider 0-1 loss I, infinite true data distribution D, and hypothesis space F. Assume that there exists at least one function f E F such that LD(f) < -n. For a fixed f E F, let o² (f, (f) be the variance of the loss: (J()D = -arz=pl(f label is flipped independently with probability Pa. (x, () D. Let D, denote the noisy version of D. For any d > 0, let D D be a noisier data distribution than D p- meaning that for every sample
data distribution D. Consider non-uniform label noise, where each
16

---

(z. v) the probabilities of labels being flipped are higher by 8: P-2 = Pz + 6. ffr fixed model LD, (f) 0.5, then o <
<
Proof. Recall that the true risk for 0-1 loss LD(f) = (x.=
= B(e.))=
Without loss of generality, let y E {0, 1]. Drawing from 2p ~ Dr is equivalent to drawing 2 ~ 'D and changing label y to y with probability Pz- More explicitly, let 1 ~ Bernoullipaa). then the flipped label is X XOR(y, 7) = [vzt)] For any given f E FF we have that:
(f) E(r,y)/ Bep-Be((on)
= ((a,))~
Enj Ber
[ [(())))))) (1 1)] + ( E Byr [1(m
E(a.y)>D
[(()))))) BepBBrres [[1 -1)]] + E (a.g)~D [1 [(())))) Be [n]]
B(x,y)~D
[[(0))y) B Ber(e) [[1 [[l]]]]] + B( (1 [((0))/ Ber(o))) [v]]
E(x,y)-D
(((()))))) Ber(()) [[1 -))]] + (r.y)~ (er [m] (((())))))) Ber( [n]]
E(r.y)>
(((e))t)) Ber(p)) [[1 100-2111 -2))]] + B(aa)) (ep- [n]]
[[(a)+v) (1 2px)] + B(x,,))DDD Pw:
Now we will show that LD 0 (f) > LD,(f)
ID (f) = E( [1 (r(a))a)) (1 2p²)]] + ((.,))D P
E(aNy>D [((())))))) (1- -2pp))]] + (. Pz
E(e,y)D [[(x)))o)) (-2p) + +2pz)] + B(x,)) (p'- Pz)
E(z.y)>D [[((()))U) (-26) + (zz,)) (6)
(-26) (( [A(()))))) +
5(1 2l) 0.
Note that, by our assumption, there exists f such that (f( < 2 7, so Lo(f*) <
2 - 7, where
f is an optimal model. Then for any fixed f E (F, (F, we get (p(f) S (f)) + < T. and then (f) > 0. Since ō >
have shown that LD. (f) LD,(f). (f).
For true distribution D, since is 0-1 loss, then for given model f. [(f, 2) is Bernoulli distributed with mean PBer EZ=D [(f, 2) (f))) and variance of PBer (1- - -Ber) = Therefore, the expected variance for given model f E F on distributions D, and D p is:
Varz~D, [(f{2)]
Lp,(f)
< LD,, , (f) - LD, (f)
-Vrz=D, [((f. 2]].
where the inequality arises from the fact that the parabola x x) is monotonic along the interval x E [0, 0.5). This implies that o² (JJ, (p) < <o,,)D
We also show that the variance of losses increases under margin noise for data that come from Gaussian distributions (in Theorem 15). We model margin noise by moving two Gaussians closer together along the vector that connects the two means. Before stating and proving the theorem we discuss two lemmas that are helpful for the proof.
Lemma 13. Consider distribution X' E The and a linear model f = wT x bb, where w E I." + 0 and b E TR. Let x + Ax be bijective affine transformation, where E m and E Rm For the linear model g(x) f(A-1(x (x c)) and the distribution Z AX + have that:
Pa~x (f(x) 0) Po~z(g(2) 0).
17

---

Proof. The proof follows from the lemma's statement and the assumption that A is a bijective affine transformation, and thus is invertible:
P=wz(g(=2 P P (g(Axtc) > 0) Pa==a
0) P > 0)-
Lemma 14. Consider Gaussian distribution X' ~ (H, 1), where P E R., and a linear model w x b, where R", w + and E. Let u+b be the signed distance from μ to |wll
the decision boundary of f. Then,
Po=x(((a)>0))
where T is the CDF of the univariate normal distribution (O, 1).
Proof. Let O IR m be matrix with the first row equal w and let the other rows be chosen so that the rows of form an orthonormal basis of R.". Note that O an orthogonal matrix, so O is bijective and O" 00 I. Let g(t) f(O (t Oμ)) and e1 be unit vector e1 (l., 0}, then:
s(t) = Oz)) =-) f(0')
= 1"=0"t+="p+bb || (cT w
= =|[w||t w" u
where 1 is the first element of t, and TT = | eî comes from the fact that w is orthogonal to every of O except for the first row. Note that g(t) when || + w a >> 0, which leads to 4 > "² a+ -r. Correspondingly. g(() < 0 when 1 < -r.
|-l
Now, let 2 0 p.). From the properties of the normal distribution, 2 ~ (0 since:
Z = 0 - μ) NN(OOp μ)) 010") ) N((
Moreover, since the standard multivariate normal distribution is the joint distribution of independent univariate normal distributions, 21 ~ (0.
From Lemma 13 and definitions of O, g, 2, we get that Pa. Pa>>x(((x) 0) = -P==z((=)) 0). Therefore:
Pa~x(((x) > 0) Pa~z(g(2) 0) Panz(21 -r) Pa.NN(..) > -r) = = Ps3~~N10,1 r)
= =r())
where the strict inequality becomes non-strict since for the Gaussian distribution, the probability P (21)NN(.11)22 = r) = 0. Thus, Pa>x(f(( > 0) ((r) as desired.
Now, we show that the variance of losses increases under margin noise the theorem below:
x y, where, X' E RT y E 1), classes are balanced P(Y = -1)= P(Y = =) and generated by Gaussian distributions P(X = -1) = (O, M) P(X = N )). where 2 is diagonal matrix with non-zero elements. Let the hypothesis space F be the set of linear models. f f= w x + b, where w R=" w F 0 and b E IR. We add margin noise by moving the means of the Gaussians towards each other by a factor of where 0 < k 1. meaning that the mean of the positive class becomes μ4 = k. μ. For fixed f E F, (f) < 0.5, we get that the variance of losses increases with more noise,
Theorem 15. Consider data distribution
o(f.)) (ff.))
Proof. Without loss of generality, we will show that the variance of the losses increases for data generated from two Gaussian distributions P(X -1) (O, /) and P) NN,, 7) (where I is the identity matrix) when we move them towards each other. More specifically, since normalization by variance
bijective linear transformation, by Lemma 13 we can work
18

---

O1
f(x)
91 22)
O
P1 F1
j41
r2
T2
P1
12
21
112
92 92(2)
Before Lemma
After Lemma
Figure 4: An illustration of how Lemma 14 rotates each of the Gaussians N(11, I), W),N(pp) I) and the decision boundary fxx) in order to compute loss CDF of the signed distances (71, 12) from means (μ1, 122 to the rotated boundaries (gn (z), (2),99(=)) (=)).. Note that we apply Lemma 14 separately to each Gaussian, thus there are two rotation operators O1, and O2.
with P(X = -1) = -V 1) and P(X = 1) = N(p, instead of -1)= and P =) = (p, Σ).
Let = || and
طير be the signed distances from the centers of the two Gaussians to the decision boundary. Then, from Lemma 14 (see illustration in Figure 4 the loss can be computed using the CDFs based on the signed distance:
(f) P(f(x) oLY 1) = = P(f()) s 0/8 1) =)
1 ト/ク -1- P(f(s) 0|Y =1))
P(f(x) O/Y -1)
= (((()) + -1- ((2)))))
Next, will show that w p >> If (,) 1.2 then get that (r))) (1 +(r2)) < 1
which means that ((r2) $ ((r1). Since the CDF of the Gaussian distribution (N 7) is strictly increasing, we have that > T1, which means that
w² p+b b
| and so w" 0.
Recall that we induce noise by moving the Gaussians towards each other by decreasing k. Now we will show that loss is monotonically decreasing with respect increasing values of or equivalently
that oh
0 I Ju (f) < 0:
0
(1
Luc (f) =
((((1)) + (1 (((2))]
Ōk
0k 2
kw 1 + 1)
(
+
$b
Ōk
2
||w||
|W|||
1 0 +b
kwT + b
2 |wll| ① kw f +
1 TT.
0.
2 Ok
||w|||
|W|||
since as we showed above, w 4 > O, and & is the PDF of normal distribution A ( I) which is always positive. Therefore, T.p. (f) is monotonically decreasing with respect k. and we have that (f) < La (f) for all 0 < k <
For the true distribution D, since is 0-1 loss, then for given model f. [(f, 2) is Bernouli distributed with mean PBr = E2-D ((f,z) LD(f) and variance of = PBer (1- -Prrr))) = (f)f(1-Lo())) Therefore, the expected variance for a given model f E Roee (F, on distributions Dj, and D D obeys:
(f)
19

---

L L (f)) = pb)
where the inequality arises from the fact that the parabola xx1 x) is monotonically increasing along the interval x E [0, 0.5). and μıu = kp is closer to than Ja.
Note, that can generalize Theorem 15 to the case when Σ is any positive-definite matrix that is not necessarily diagonal (covariance matrices are always positive semi-definite, and we now additionally assume that Σ does not have zero eigenvalues). Since E is real and symmetric, by the spectral theorem, there exists an orthogonal matrix Q I Rmxm such that D = QIQ" where D is diagonal and contains cigenvalues of Σ. The diagonal elements of D must be real and positive since Σ is positive-definite. Then, consider the data distribution (Qx) x V. From the properties of the Gaussian distribution, QX' is Gaussian with mean Qu and covariance matrix QXQ' = D. Thus, we can generalize the results of Theorem 15 to apply to positive-definite non-diagonal matrices E.
For a fixed model, we additionally verify the results of Theorem 13 empirically, by generating Gaussian distributions and introducing margin noise by moving the Gaussians closer together (see Figure b).) The variance of losses increases with additive and uniform random attribute noise as well, as we show empirically in (gguree3c)-(0
While the results of Theorems 15 are for given and fixed model f. they hold for the f that achieves the maximum variance the Rashomon set as well, meaning that Corollary 3 extends to
Theorems 12 15
B Bernstein's and Hoeffding's inequalities
In this section, compare Bernstein's and Hoeffding's inequalities and show that, under certain assumptions on variance, Bernstein's 's inequality tighter than Hoeffding ' inequality. We provide Bernstein's 's inequality in Lemma 16 and Hoeffding" 's inequality in Lemma
Lemma 16 (Bernstein's 's inequality for loss class), Consider hypothesis space F. For a fixed f E F, let loss be bounded by C > such that [[[[, =)1 S C for every z E Z. For any e >> 0,
( - L() S
120//8
(4)
where o3 Var l(f. 2). and is number of samples in S = {2)) ~ D.
Lemma 17 (Hoeffding's inequality for loss class). Consider hypothesis space F. For a fixed f F, let loss I be bounded by b 2 0 such that ((f,z) bor every E Z. For any & > 0,
P (((()- -(f)) >
2nc2
(5)
where n is the number of samples in S { D.
Note that for 0-1 loss in the lemmas above, 0, b 1, and C = 1. Now show that Bernstein's inequality is stronger than Hoeffding 's if variance is lower than (b-a)²
12
Theorem 18 (Bernstein's inequality is stronger than Hoeffding's for lower variance). For a fixed
F, let loss 1 E (a,b) so that < [[f[[ =) S for every E 2. Then, Bernstein's 's inequality is
stronger than Hoeffding's 's inequality for all s E (0, b - a) if < 12 or [(J) -22 where of
(b-a)²
a+h
b-a
V6
Var l(f. 2).
Note that since the true risk and empirical risk can only differ by at most a, e not meaningful 2 b
Proof. According to Hoeffding's 's inequality (5), we have that
p p( - L(S) > s) 2e 22ne?
oj7
20

---

dimension 2
Var the loss
0.20
dim
0.15
dim
U2
0.10
dim
10 dim
0.05
0.00
3.0
2.5
2.0
1.5
1.0
0.5
dimension
Margin noise, m
(b)
Var of the loss
0.06
dim
dim
A1
0.04
dim
0.02
10 dim
0.00
0.0
0.2
0.3
0.4
Additive attribute noise,
(a)
(c)
0.250
Car Eval
Variance of the loss
0.225
Monks 2
0.200
Monks
0.175
Monks
Bar-7
0.150
Compas
FIDD
BCW
Restaurant
0.050
0.00
0.05
0.10
0.15
0.20
Coffee
Uniform attribute Pa
(d)
Figure 5: The variance losses increases with margin (b) and additive attribute (c, d) noise. For (b) and (c) generated data from Gaussians in 3, 5, 7, and 10 dimensions. For margin noise (b), as illustrated (a), the negative class generated from N M(r, T) and positive from A ( I), where is the identity matrix, μá -m/22 1, f/2 m/2 x 1, and controls the distance between Gaussians that determines the amount of margin noise. For additive noise, data generated from (O, 1) and (2, 1). The noise model is x' x + e, where e (O, a!) is the noise vector added to every sample and determines how much noise is added to the data. For evaluation, as a fixed model consider a random linear model from the Rashomon set. For (d), we chose 3 features with the highest AUC value and introduced uniform noise by negating the attribute values with probability Pa. As fixed model, we consider tree generated by the CART algorithm that uses least one of the features to which noise was applied (this is because if the model does not use these features, the variance losses for that model will not change). All plots are based on 0-1 loss and are averaged over 10 iterations.
Recall that Bernstein's 's inequality states
(10 - -()) > 2)) < 2e +2/+30
where C' 0. Without loss generality, let ()) I(f,)) a+b so that 1' e CJ. Then, we get that L'(f) = L(f)- 2 Therefore, we can rewrite Bernstein's 's inequality as
atb Var (f(f. z) = Var l(f. z). and i'(f) L(f) a+t
2
P p( i(n) - i' > 8) 2e
Consider of S (b-a)² 12
Then, we can hound the right side of Bernstein's 's inequality by
2nc2
2nc
2e to 2(
2
(6-0)2/842(0--0000
21

---

-2ne²
where 2e (h-a)² is the bound given by Hoeffding's inequality. Therefore, showed that, of - (b-a)²
12 then Bernstein's inequality is stronger than Hoeffding's 's inequality for (0, -d) a).
We now consider |L()) - -/2 50 Recall that L'(f) = L(f) a+b so we can rewrite this as b-a vo"
[E())>
Since -C S (f. C, we know that
Var (f, = ((" - (Es
s C - (T)
(b - a)²
(b-a) a)²
4
6
(b a)²
12
Then, we can follow the same argument as in the previous case to conclude that Bernstein's 's inequality stronger than Hoeffding's inequality for all & E (0, b a).
C Proof for Theorem
For discrete hypothesis space, Theorem 4 bounds generalization error with a term that depends on the size of the true Rashomon and maximum variance of the loss. Recall Theorem 4
Theorem 4 (Variance-based "generalization bound"). Consider dataset S, 0-1 loss 1, and finite hypothesis space F. With probubility least 1 ō, we have that for every E Reot (eot(FF (F,7):
[Raer(F
202
log [Baea(F,n)))
- - ū() -
log
3n
where 0² = (F) Var ((f,z). 2), and n is number of samples in S = (2)) D.
Proof. For each fixed model f E Roee(F, 7) in the true Rashomon set, from Bernstein's 's inequality, using that the maximum value for the 0-1 loss
have that
P(T()) - i(j) > >)) 5) 203+2013
According to the union bound:
P (3f E (see(F.)) L(f) i(f) > 25) Σ
P(L()-(f)
(ERun((Fr))
nne2
Σ
(E
fER (Fx))
R [F, F,7)] -020 2200-2213
where we used the fact that monotonic.
of Se "F of 2t since the exponential function is
ne²
Let RRset F,
20 42r/5 F,Y))
then we have the following quadratic equation find
[Rnt(FF
202
[Rsc [Raai(F,,)) 0. (F,7)
e²
log
&
log
3n
5
[Ree (Fa)))
Setting
log
we find that the roots of the quadratic equation with respect to
a
1
a
+ 4
2.3
2
3
22

---

23 - 2²))
Since 2ao² 2 O, see that
0 which is not valid root as e >
0. Thus,
1
(F
1
[Reat(F, (
2x²
R (F, (F, .
=
log
log
+
log
3n
3n
8
8
2 3n
RFse(FF
20
[Rser(F,
log
log
n
where the latter inequality arises from the inequality Va + b Va + vb. Therefore, we get that with probability at least - 8:
[Ree((F,)))
2n
[Baci(F.))
Vf E Root (F,)): I(f) i(f) S == 3n
log
+
log
5
n
D Proof for Proposition 5
We recall and provide proof for Proposition 3 below.
Proposition can be close the true Rashomon set). Assume that through the cross-validation process, we can assess such that L(f) i(f) s & with high probability (at least 1 Eg) with
respect to the random draw of data. Then, for any c > O, with probability at least 1 - c 2ne" ce
with respect to the random draw of training data, when & + e S y, then ff E (Fer(F
Proof. For a fixed f E F for loss by Hoeffding's inequality (
p[ - >
((0)-(()
Se 22ne
Therefore, with probability at least 1 1 2nc² with respect to the random draw of data, (())-(()) s This is true for the optimal model as well, thus with high probability i.(s*) T(J*) Sc.
Since f is the empirical risk minimizer, and + & 7 b by assumption, we have that L(f) ((f)). We use that for two events A and B, P(-(A = - - 1- P(A) 1 A is the event that cross-validation gives incorrect generalization bound, and B is the event that f does not generalize. Thus, P(A) < 22m2 and P(B) S cç. Thus, with probability at least
P(B), where
1 e 2nd²
Eg.
( ( +
Therefore f E (Fe((F
E Proof for Proposition 6
For the hypothesis space of decision trees, the number of possible decision trees in the hypothesis space grows exponentially fast with the depth of the tree and the number of features. In Proposition 6 we show that the Rashomon growth rate is smaller than the growth rate of the hypothesis space. and thus this leads to larger Rashomon ratios for simpler hypothesis spaces. We recall Proposition below.
Proposition 6 [Rashomon ratio is larger for decision trees of smaller depth). For dataset S = X with binary feature matrix X (0, 1]axm, consider hypothesis space Fa of fully grown trees of depth Let the number of dimensions m < 22". Assume: (Leaves are correct) all leaves in all trees in the Rashomon set have at least [On] more correctly classified points than incorrectly classified points; (Bad features) there is a set of mbad 2 d "bad" features such that the empirical risk minimizer of models using only the bad features is not in the Rashomon set. Then Rratio (F.+1. < Rratio (F (Fa. F)
23

---

Proof. The hypothesis space of fully-grown trees of depth d contains
Fal - 22
II (m mm mmmk+1 1)
trees, where 2 is the number of label options each leaf can have, 2 is the number of leaves we have, IT== is the product over all depth levels in tree, 2 is the number of nodes have at that level, and (m - (k - 1)) is the number of options we have to choose from given that the previous features were used in the path from the root. We do not count symmetric trees, meaning that always assume that split = 0 is on the left and = is on the right.
Now let's s compute the size of the Rashomon set. First, since each leaf of every tree in the Rashomon set has correctly classified [0n] points more than misclassified, flipping the label of this leaf will add more than 0 to the loss and thus will push the tree out of the Rashomon set. Therefore, for every tree, every leaf label is determined by the data.
Second, since the empirical risk minimizer of models using only the bad features Mood is not in the Rashomon set, every tree that has only features from the set mbad is not in the Rashomon set. Therefore, trees in the Rashomon set must have at least one "good" feature at some node, where good means that the feature is not in myedd The cardinality of the set of good features m m [madd] then the cardinality of the Rashomon set is:
d
d
Reee(Fos 0)
II (m k 1) k=1
II m m
- k + 1)2"
k=1
meaning that among all models, we do not consider those that consist of bad features only (since Whad 2 d, there exists at least one such tree). Then the Rashomon ratio is:
(Fe 0))
(m k + 1)a* IT k= (m 17t - k: + 1)2 1)2t-1
Brasio (Fa
===1
Fal
2
k= (m k + 1)2t-1
1
k= (m m - k + 1)2
2
1i== 1 (m - 1 + 1)2
24-1
1
m
2
m1 k + 1
k=1
1 1-
a(d)
22d
2
where (d) = k==1
(1
m
Since d > 1, > 1, and
> â for h: > 2, we get
m-k+1
m-k+1
that
d
2
d
m7
m
m
a(d)
l +1
k=1
k=1
Note as well that (d) for any d. Recall that <
22d
then for the ratio of ratios:
Bratio (FaatooFFs, F2,0)
RRee(Fa, 0)
Fot1
Bratia (F a+
Fal
Ruae (Fo+1,
1 a(d)
22
1 1- a(d)
1 a(d () = 22
22d
I-a(d 1)
2² (1 aa(d) 2n" (1- (1- 1-(1- m
22 m
22d
1 = 1.
>
22d
m
Thus showed that Pepatio a) Rratio (F (Fa+1 1+1, 0), meaning that the Rashomon ratio grows as we consider less deep trees.
24

---

F Proof for Theorem 7
Recall Theorem
Theorem 7 (Rashomon ratio increases with noise for ridge regression). Consider dataset S = X XY, X is a non-zero matrix, and a hypothesis space of linear models F = (f w x, w E TR" _ S Lmax/ C Let such that added to every sample: x' = I; + eq. Consider options X 0 and X2 > that control how much noise we add to the dataset. For ridge regression, if X1 < X2, then the Rashomon ratios obey Ryatios, (F,0)) < Rrations (F,0)).
(O, AI) (A > O, I is identity matrix), be i..dd noise vectors
= Proof. For simplicity denote Ee (10 as E. To find the optimal solution, under added noise, would like to minimize expected regularized least squares:
E. L(w) E.
((2 + T ui)² OwT
E.
(ao) w y1)² + 26 @e"woof v.) oawaeet eiefi)) + Cw
Σ
(N. w - y:)² + 2E [sil" w(x w u.) + w Ee + OwT w
Σ
((xT - y1)² + w (ND)WW + CwT
i=1
Σ
(a. v1)² + (C A)
Ti i=1
where E, [ee]]] = AI, / is identity matrix, and E, [ex] =0
Therefore, adding attribute noise the training data becomes equivalent to fz-regularization, and the new regularization parameter C' + X. According to Theorem 10 in Semenova et al. [39], the Rashomon volume can be computed as:
(iReet, (F,0)) = (TT)
II
1
[( + 1=1 of +C+
where are singular values of matrix X, and r(-) is the On the other hand, for the regularization parameter C + A, the hypothesis space is defined as (C + X)wT w < Lmax. meaning that w w S Limas in m-dimensional space with radius R. || (Em (0,13) < R, can be computed as:
function.
C+X The volume of the ball defined by the fo-m
(R)
π T 7
Rm
+
Since for 1km1 T w S obeys:
Lanxx we have radius RA C4X:
v
Lemax C4X we get that the Rashomon ratio
Ryation (F,0)) V(Reset (F,0))
V2. (Rx)
(TT) T
m
T +1) (C+
r(m + 1)
of +
7.. TT
(Lmax)
C+
1iaxx
of +C+
i=1
25

---

Since 0 < X1 < 22, C > O. without loss of generality, let A Y + C, and λ + x2 +
where 8 X2 A 0. Consider function
where a > 0. This function monotonically O. Therefore, for all non-zero o/:
a+*"
8 increasing for all x O, since dr
a+z
(a+x)
AC +
A of + 7
Since X is non-zero matrix, there is at least one non-zero singular value of Given monotonicity of square root function, we have that for the Rashomon ratios for noise levels λ and A2:
AC
Rratios, (F,0)) = Rration (F,0)) = Limax
+C
Ac + 6 Lmax of AC + Reationa (F,0)) Reations (F,0)).
Therefore we proved that with the additive attribute noise, the Rashomon ratio increases.
Compared the Rashomon ratio, the relationship between the regularization parameter and the Rashomon volume is inverted: the stronger the regularization, the smaller the Rashomon volume. This means that adding more noise leads to stronger regularization and smaller Rashomon volume. In some ways, this is consistent with what we saw in Figure (b), in the presence of noise.
(b) where CART preferred shorter trees
Next we show that the variance of losses (recall notation of D) Var ((f. f 2)) increases for the least squares loss function under additive attribute noise, as Step 1 of the path in Section
Theorem 19 (Variance of least squares loss increases with noise). Consider dataset S = X Y, where X E Raxm, Y E IR", 2; = (Ri, (i), Let 6; = {Eig ( such that Gjj ~ NO, x2), be i.i.d. noise vectors added to every sample: z I; + G. Consider 0²;; > 0, N22 > 0 that control how much noise added to the dataset. For the least squares loss 1(z,) = (wTT.. y1)² and a fixed model f(x) = w x, where w E IRmh W + Ö, the variance of losses increases with more noise: if Ni < <NN;, then: (J,,))
Proof. For simplicity, denote "ee.....it......a...............
Ex, and Er..y E.. The vari- ance of losses for the least squares loss under the additive normal noise is: (f( Varzæ [(<z; + = - w.²].. Also, for simplicity, we will omit index over samples (but keep index j over the dimensions). Recall that x- w From the definition of the variance we have that:
Varze [(x = = Varz. ((xJ -- -) + ETT = Varzi (r+
(6)
= Ez, (r + (T))= - (Ra. [
Since G ~ of), we have that E,, [cy] = 0, Ee [(,)]]] = oxr- E,, [(c,) 0 (this is a property of Gaussian random variables), and Ee, [(e,)]] 3 Also recall that the multinomial theorem states:
Σ aj
Σ
02
ky hig
km
krtkat..t......
The multinomial theorem helps us to compute coefficients of the first four moments for F More specifically, for the first and second moment:
26

---

E2
[
27
m
Ez [c
w) [<TTw)
= Ez
Σ Ejwig
= RE
Σ
(sww))
+
E
eywyewwk
j
m
E2 [cg] w/ = oxxotat w.
For the third moment, notice that from the multinomial theorem. k1 +.... km
Then there
are three possible combinations of the values of ky: some Ka = 3 and the rest are 0, some KS = 2. k2 1, ke 1 and the rest are 0. All of these
ky 1, and the rest are 0, and finally some ha cases will lead to the presence of either o) or Ej in the product. Since IR,, [c]] = O, and Re, [ 0. we have that
E2 [(<T =
Similarly, for E, (E (jas) 4
we get non-zero terms for some of the combinations and the others are In particular, non-zero terms arise when some ka = and the rest are 0, and some ka 2, Rib 2, and the rest are Os. This gives
Ex [(ETw)]] = Ee
Σ
m
Σ
Be
[ef]
W +6
Σ
Eg
[e}]
WF
[c]]
wf
j=1
j= mr1....k==.... A.I.m...jf jf
m
30
Σ
w
+ 6o
Σ
1=1
jml..m,kmL... Ly.njjh
3o w)
Let's focus on the first term of the variance equation 6
Be,ē [r+ + (T)+
22, [r + 3 w + 6r (EF + (r(ETTT)) ww) + (ET
Eg [r-]] + 4Eg [r E2 [ + 6E. [n²]] E, [(F=))
4E, [r] EE [(eTT) [3]
+ E2 W
E. [r-]] + fo WE, [+²]] + 30 N (w w)
Now, we focus of the second term of the variance equation
Ez,z [I+ ((++cTun) = = (Ez,e [.2 + 2re Tw + (6 21)² 2²
(E, [r2] + Eg [2r] Ee [e w| + Ee [(e w))))
(E, [r]] + ", w)
(E, [r²1)² 2 20 2
WB, [n2]| + (wF
Therefore, for the variance we get that:
Varz,z (r (r+ [w) E, [r*]] 3o WTF, [12] + 30
27

---

(E, (Es [1]) 2 W.,, [1-] o (w w)
-2t 2 wB, [r3] + 2 (E, [+ 1=2) + R [r]]] - 3 3B, [r²]]
= =2 [r²]) B [r*] 3 (E: [r=]]
Next, we will take the derivative of the variance with respect to ox
① (Varza (r+ doy (2 w + E2 [T²]]] + E2 [3 (B,
doy
4 (o)nw" w E. [r²]) w" 0,
since o > 0 by assumption, ww > O sincew + 0, and the risk of the least squares loss E, [T²] 2 0. Therefore, the variance of losses for fixed model f whx monotonically increases for o% > 0. Thus, for 02, oig we have that:
o² (
As before, Corollary easily extendable to the results of Theorem 19 meaning that the maximum variance of losses, o² sup (eR...FFF V (arz=pl(f,z) 2), will also increase for the least squares loss under increasing additive attribute noise.
Next, we show that when the maximum variance x² increases, the generalization bound becomes worse for the least squares loss and the continuous hypothesis space. Cucker and Smale 11 proved the generalization bound based on Bernstein's 's inequality for the least squares loss (Theorem B). We state and provide proof of the theorem for the true Rashomon set. To derive the generalization bound, we use the covering number over the true Rashomon set. Recall that for the functional space F and any e > 0, the foo covering number N (F, e) of is the minimum number of balls of radius e, such that they can cover F, meaning that there exist h1, .... (F.e) E F, such that for every ʃ E F there is h < N(F, e) such that [| theorem.
hg x = max (fr) hy (x)) < Now we focus on the
Theorem 20 (Variance-based "generalization bound" for least squares loss). Consider data distribu- tion D over Z = X x y, dataset S = {z]]== ~ DD, hypothesis space F, and the least squares loss 2(f,2) = (f(x) v)². . Let the loss be bounded by C² such that U(f, 2) S C2 for every z Z.
For any > 0:
E -n(e/3
P sup
L()) - < SN (Beal(F (), 80
e c2L/3
(F
where 0² sUpR).)(F.)) Varzepl(f,z).
Proof. For each fixed model f E Ryer () in the true Rashomon set, from Bernstein's 's inequality and given that loss is bounded by C22 we have that
P(L()) >)) 20 +204
Let B B.....BBr B be an loc cover of radius
8e of the true Rashomon set, meaning that
Roet (F, () C U k=1 ((Raa(Fs))ste)) Br. where N (Beer(F,)) 7), &Õ is the covering number. Since the loss is bounded, 1(f,2)= = (f(x) - y)² < C², then [f(z) - yl < C. For every f E Bg, we have that
Ilf h4llox oc I , where hy the center of the ball Bg. Therefore:
(I(f) i(f)) (I(hx) i(hw)) (I(f) - [(hx)) + (i(ha) -(())
= -ENND 2(f,)) - 1(h,, 2)] + 8 [[[, 2,) - 1(h4, 2,]
=END [(f(x) y²² (fu(2)) y Bas~s [(f(z.) v.)2 (ho(2s) ]]
28

---

= BOND (f(x)= - (x))) ((f(a) y) + (hx(2) - v))
+ Eans ((f(z)) (x,)) ((f(2)) y.) (1x -
I EEND |lls - 10o (C + C)] + E [l]s - hello (C+C))
= =4 - hx I 40
8C 2
Therefore, if L(F) - L(f) e, we have L(hx) - L(hx) 2 (L(f) - -(n) - c = 2 This
holds for every Bk, and thus for arg sup BE as well:
P sup (()- L(f) >5) $ P (I(Ma) I(he) > >g) /EBr
Since the exponential function is monotonic, covering number, according the union bound and
(The
< e 2/2 Based on the definition of the
we have that:
sup I(f) L(f) > P (33 E Reet (F,1) L(f) -()))((f)) L(f)>e) (ERv
P
SP
3f E Bx L(f) - =E
k=
M(Re((F
Σ
P P(ff E Bs -(f))
k=1
((Rec(FFi)
Σ
P ((hb)) L(hu)> "
-nic/3/2
20 t02e/8
N (Raa(FFri)
2
Σ
220
- 2
= N (Racs(FFF)))
@20'/C'E/8. C21/3
80
Therefore we obtained the desired bound.
Since -1/2 monotonically increases for 0, in Theorem 20 the maximum variance of losses increases, the bound on the right side increases as well, and thus the generalization bound becomes worse.
G Pattern Diversity and Other Metrics of the Rashomon set
In this appendix, discuss similarities and differences between pattern diversity and pattern Rashomon ratio as well as expected pairwise disagreement (as in [5])-
Pattern Rashomon ratio. Pattern Rashomon ratio measures how expressive the Rashomon set is compared to the whole hypothesis space. Interestingly, for the hypothesis space of linear models, for different datasets with the same number of samples and attributes, long as no
1 points are ==
collinear, the denominator of the pattern Rashomon ratio is the same and equal to 2 > ("-1) (10] we focus only on the numerator the pattern Rashomon ratio, it is the number of distinct predic- tions, whereas the pattern diversity is the average Hamming distance between distinct predictions.
29

---

Intuitively, the more distinct prediction we have, the more different they are from each other, and the higher pattern diversity we should expect. However, it is not always the case, and there exists datasets such that we can have large number of patterns with very small Hamming distance and small number of patterns with larger Hamming distance.
Similarly to pattern diversity, we can boper-bound the number of patterns in the pattern Rashomon set by bound that depends on the empirical risk of the empirical risk minimizer and the Rashomon parameter 0. We discuss this bound in Lemma 21
Lemma 21. Given the dataset S of size n, the pattern Rashomon set (,), the empirical risk of the empirical risk minimizer L(f), and the Rashomon parameter 0, the cardinality of the pattern Rashomon set obeys:
[KLLf)+n0]
[TF S
Σ
k=
Proof. For every model from the Rashomon J. i.()= i.() + 0, which means that, in the worst case, the Hamming distance between pattern p and vector of true labels Y [>v]=_ is [ni(f)) nd). Thus. patterns in the pattern Rashomon set can make one mistake, two mistakes, and [[L[()++0]
so on up to [nā(f) + nd] mistakes, which means there are at most Σ Ek=1 pattern Rashomon set.
(T) patterns in the
Expected pairwise disagreement (as in [5]). Following [ and 30), empirical expected pair- wise disagreement T(Reatt 0)) over the Rashomon set can be defined as [ff (F,, (F)0)) Ru. Eg-s (t)) Expected pairwise disagreement measures the average dis- agreement between every two hypotheses from the Rashomon set, while pattern diversity measures the average disagreement between two patterns from the Rashomon set. The expected pairwise dis- agreement equivalent to pattern diversity when every pattern is achievable with the same probability by models from the Rashomon set. However, these metrics can be very different and we can have a small expected pairwise disagreement and larger pattern diversity as we show next.
Proposition 22 (Same pattern diversity but different expected pairwise disagreement), Consider finite Rashomon set Raet (F, 0) of size d 2 2. Let x xF,(0) 0) be the pattern set of size II, S II S Assume that every pallern except P1 is achievable by only one hypothesis in the Rashomon set, and thus P1 achievable by d - III + 1 hypotheses. Let d' be the current value of d, then as d + oo (for example, by replicating hypotheses that realize p1 infinite number of times), expected pairwise disagreement converges to zero, I [(R O, and pattern diversity does not change, div(Re (eeeReeeFF 0)) div(R
Proof. The proof proceeds in two steps. Pattern diversity. As d increases, the pattern set does not change, therefore for any d 2 d', div( (F 0)) = div( (Fae
Expected pairwise disagreement. Given a pattern p E (F, 8). let Py (f [p = pl| be probability with which this pattern is achieved by models from the Rashomon set. Since support for all patterns except P1 is 1, then Ps = -P (F,8) [PA = =p' _/ for k = II. And for pı we (p1- = r' d-I++1 Then expected pairwise disagreement:
have P1 = P, P)
d
1(Bset (Fa, 0)) E 1 In T1 P/ Im== = Σ P/ (ps = -p]= (px.
I
I=1
(PP (pi (mi=
1 n
(p).Pi)
30

---

11
+ 2P, f- 1p1 1p1= r1
Σ
P (F =p'l -(((p,p)))
5=2
P P) r²1 1 (ps.
(F,)) = =v
Σ
f=2
d
-
11 + 1
0 2
H(m pj)
d²
d
n
j=2
k=2j=2
11
11
1
1
II
H(I. Pj) +
ΣΣΣ H(px.Pj) k=2
d
d
n
d
5=2
Therefore, as d oc, (Fa, + O.
As we see from Proposition 22] we can change expected pairwise disagreement, for example, by adding multiple copies of the same functions f to the hypothesis space. Expected pairwise disagreement measures predictive multiplicity [6], but it has the issue we showed above that can depend the weighting of hypotheses in the hypothesis space. In the case described in Proposition 22] the multiplicity is small because one subset of hypotheses (which produce the same pattern) weighted very heavily. Thus, expected pairwise disagreement by overparameterization or poor choice of parameter space. We further illustrate the effect of re- parameterization on pairwise disagreement on simple one- min-dimensional example in Figure Pattern diversity does not depend on the parameter space and is computed in the pattern space. It is not compute
be influenced
impacted by any probability distribution weighting on the hypotheses. Moreover, the pattern diversity by enumerating all possible patterns of the given finite dataset as described in Appendix K. We cannot do the same for the pairwise disagreement metric without additional assumptions on the patterns' support.
H Proof for Theorem 9
Recall that a; is sample agreement over the pattern Rashomon set. Then can compute the pattern diversity based on sample agreement as in Theorem 9
Theorem (Pattern diversity via sample agreement). For 0-1 loss, dataset S, and pattern Rashomon
π7 (F, O). pattern diversity can be computed as div( (F, 0) = 2 E a;(1 a4), where
a; 1I _ 1 pp= is sample agreement over the pattern Rashomon set.
Proof. Let y E 13. We can transform y E ( by two.
13 to (0, 1}, simply by adding one and dividing
Recall that Hamming distance H(55, Pk) = Ei= [pr
Alternatively, we can rewrite logical
XOR as ()f+E = (1- +p (1 (1-pp)). p)). Denote b: 1 E p/j. then from the pattern diversity
definition:
div( (F,
j=1 k=1 1=1
11 ΣΣΣ
(1
+ +L - p3)1
j=
ΣΣΣ n
p -
k=1
31

---

P1: ax+1
P2: +x+b
Diversity
0111
0111
0011
0001
0011
0111
0011
0001
0001
(a)
(b)
(c)
Figure 6: Illustration of how reparameterization changes pairwise disagreement metric.
Consider a separable dataset of four data points with a real-valued feature in one dimension: $ = {(1. 0), (2. 0), (3, 1), (4, 1)} and hypothesis space of linear models. Let the Rashomon parameter be = 0.25. There are three patterns in the Rashomon set: 0111, 0011, and 0001. The pattern diversity (c) is 0.444. Consider two different parameterizations for the hypothesis space of linear models: ax + and + + b. These two parameterizations produce the same decision boundaries for the dataset S. For the parameterization + + b (b), each pattern is achieved with the same number of models. For the parameterization az = 1 (a), more models will support patterns that are closer different color. The pairwise disagreement
the origin. The support of each pattern is shown metric is 0.321 for oz + 1 and 0.444 for +x + 6. (For the parameterization a.r + 1, we see that the pattern 0001 occurs when (1, 2), the pattern 0011 occurs when (2 3), and the pattern 0111 occurs when (1: 4). Therefore, the pattern 0001 has probability wi 7
1- 1 0.666, the
1-1 pattern 0011 has probability w2 -ー 0.222, and the pattern 0111 has probability w3
0.111. Recall that H (cdot,) -) is the Hamming distance, then the pairwise disagreement metric is Wi H (0001, 0011) w1 w3 H (0001, 0111) + u2 Wy H (0011, 0111) = wi W22 + 2w W3 + W2W's = 0.321. For the parameterization +r + 6, each pattern has equal probability 3 We can then similarly calculate that the pairwise disagreement metric is 0.444). Note that if the data points are shifted together to the left, the difference in pairwise disagreement metries for parameterizations in (a) and (b) will only grow.
n2
[p} by
2b:1%]
j=1
TI
1T
b;
bpp
n
II 1=1
II 1=1
j=1
(6 + by 26
11
2
4(11 - b.).
On the other hand, according to logical XNOR, have that I [(==v)] pk.s + (1 (p ys). therefore we can rewrite a; as:
0
boj =w]
[pLee + (1 (1-ph)(1 - y)
2pplys + 1 81 pkl
II
2y
Pk +
y18
pk
1=1
32

---

2y,b; + 1 - Vs b;.
Since E {0, then u = and we have that:
a
a:) 2
n
a:(1
By.b; +1 yi -bb(((222ysb + y/s + bs)
71
==1
2 n
(4yybb² b :y + 2y:b/ 2y;h: y/s + b
1=1
+ 2y.bs - yi yob 2y. yob: bz
2
(b; b))
2
b.(1 b1).
1=1
Therefore we get:
2 n (F,
2 8 n1
Σ
b2(1
b.)
Σ
ag a.).
n1
I Proof for Theorem 10
Before providing the proof for Theorem 10 that realize patterns in the pattern Rashomon set is negatively proportional to the average loss of these hypotheses. We use this intuition to derive an upper bound for average sample agreement and then discuss the upper bound for pattern diversity.
we show that average sample agreement over hypotheses
Let hypothesis pattern set (xx C Reet (F, 0) be set of unique hypotheses corresponding to each pattern in x (FF 0), meaning that there is no f J E HxiFF.0) 8), such that ST * 18 yet yet = Theorem 23. Average sample agreement over the pattern Rashomon set is negatively proportional to the average loss of models in the hypothesis pattern Rashomon set H (F,
(Hx((,
n
where Trang (Hx
El ((EE). Moreover, when the Rashomon parameter 0 0, then
Σ -1-111 i(f)-
Proof. For a given (z;; y.), when hypothesis f realizes pattern Pdd Pk. we have that p = 1 (s:). Consider average sample agreement:
Σ
0
1 pi=w
II
1=1
i=1
Am
n
'ince there could be many hypotheses that achieve the same pattern, H is not unique. We can work with any of them, H.CF #) is simply representation of the pattern in the hypothesis space.
33

---

11
by xv
1=1
(x)
11
k=1
(ife)
1 - Lavg (H (F,
When A 0, for any k. i(f) L(fe). therefore E a, 1 L(f).
Given the definition of models in the Rashomon set, can derive upper bound average sample agreement in Corollary 24
Corollary 24. For any parameter 0 >> O, average sample agreement is upper and lower bounded by the empirical loss of the empirical risk minimizer,
1 1 L(f) - 0
Σ
a4 S - i(f).
1m1
Proof. Proof follows directly from Theorem 23 the fact that for every model f from the Rashomon set, L(f) L(f) S L(f) 0.
Finally, we provide proof for Theorem 10
Theorem 10 (Upper bound on pattern diversity). Consider hypothesis space F, 0-1 loss, and empirical risk minimizer f. For any 0 2 0, pattern diversity can be upper bounded by
Riv(Rect(FF 0)) < 2(i(f) + - -11
20.
Proof. From the
inequality, we have that
2
n
Σ
aj
Given this and from the definition of pattern diversity and Corollary 24
we get that:
2
2
2
Bive (Fa (F,0))
05
0.)
01
0
2
11
11
71
2
2
1
Σ
= 2
11
22
1-1
1=1
2 u()) 2(1 i()) 0)2
2-22(f)) - 2+ (++(((()) + - -(((() 0)
-2(i(f) +0 -0-(1()) 00)))
-2(i(/) - ((1((((()))))
+ +0
When 0 = 0, then dév(R (F, (F,0)) 21( (L)()))
34

---

J Proof for Theorem
We state and prove Theorem below.
Theorem 11 Consider a hypothesis space F, 0-1 loss, and a dataset S. Let p E (0, be the probability with which each label ys is flipped independently, and let Sp 2(Sp) denote a noisy version of S. For the Rashomon parameter 2 0, if in sey Es, Ls, (f) < 9 and Ls(fs) < then adding noise the dataset increases the upper bound pattern diversity of the expected Rashomon sel:
Udio (Rsetg (F) Udiv spp))))) 8p (F,
Proof. Given the noise model, hypothesis f is in the expected Rashomon set if Es, (s, - fer Es, L.s, (f) 0. Let f E F be such that E arg inf ser Es, Ls, (f). Since p E (0, 2 and Ls(fs) < 2 by assumption, from (3) and the definition of the empirical risk minimizer, we have that:
inf Es, Ls. Es, (f) feF
20) (f) + (1 (1-2p)
2 (1 (11 2p) +
Ls(fs).
Consider g(x) = 2(x -)= 20. For E [0, 2 - -0).((1) g(x) is monotonically increasing, as 51) = 2(1 - 0) - 2(x + 0)=+0)-41 4
0) > 0. Given monotonicity, assumption of the theorem JEF Es, Ls,(1) (/) < -0 and since Ls(fs) < fin Ls, (f), we have that
(Rintg (F, (is(is) + +0) (1 Ls(ss) - -0) 20
inf Es, Ls, (f) + +0) (1-
inf Es, Ls (s) -0) 20 fEr
FES
= Udiv [Ractss, 9, (F,0))
Interestingly, in the proof of Theorem 11 the empirical risk minimizer of dataset S, fs. also minimizes the expected risks over noisy datasets, meaning that fs E arg sEF Es, Ls,(()) (f). To see this, assume that fs & arg ier Es, f.s, (f), then there is arg inf Es, L.s, (f), such that: Es, Ls (J) < Es, Ls, (fs)-
Applying 3 to both sides of the inequality above, we get that: 2p) < 2p) Ls) +
which after simplification becomes:
Ls(J) Lis(ss).
This is clear contradiction, since fs is the empirical risk minimizer S, and thus Ls(fs) s Ls()) for any ʃ F. including J. Therefore our assumption was incorrect, and fs arg yer Es, Ls,(f). (f).
K
Setup for experiments
K.1 Datasets Description
Please see Table KTT for the description of datasets used in the paper and all the processing steps. We normalize all real-valued features.
35

---

Table 1: Preprocessed datasets
Dataset
Number of Samples
Number of
Notes
Features
Car Evaluation
1728
16
We use one-hot encoding for features We use one-hot encoding for features
Breast
Cancer Wis-
699
11
consin
Monks 1
124
12
We one-hot encoding for features We use one-hot encoding for features We one-hot encoding for features We use one-hot encoding for features Processed in
Monks 2
169
12
Monks 3
122
12
SPECT
267
23
COMPAS
6907
13
22
FICO
10459
18
Processed in
52
Bar (Coupon)
1913
15
Processed in [52
Expensive Restaurant
1417
16
Processed in [22
Carryout Takeaway
2280
16
Processed in [22
Cheap Restaurant
2653
16
Processed in 152
Coffee House
3816
16
Processed in [52
Bar
1913
16
Processed in [52]
Telco Bin
7043
6
We use only the binary features
Iris
100
4
We consider classes Versicolour and Setosa
Wine
130
13
Wine 4
130
4
We PCA create 4 features
Seeds
140
4
We consider classes and 2 and use PCA to create features
Immunotherapy
90
4
We use one-hot encoding for fea- ture "type". We use PCA to create 4 features We use one-hot encoding for feature "island." We consider classes "adelie" and "gentoo" only and use PCA to create 4 features We consider digit 0 and digit 4. We PCA to create 4 features
21 22
Penguin
265
4
Digits 0-4 4
359
4
K.2 Illustration of Cross-Validation Process in Step 3
We considered uniform label noise where each label is flipped independently with probability p. For each dataset, performed five random splits into train set and validation set, where the validation set size is 20% the number of samples. For the tree depth of CART, we considered the values d E [1, .I, m). where is the number of features for given dataset.
For Figure aa), we tuned the parameters and then added noise to see what happens, which that performance degrades. For every train/validation split we performed 5-fold cross-validation
(Train Vai) Accuracy
0.010
Compas
0.010
0.015
FICO
Best # of Estimators
120
Compas
Talco Bin
0.005
0.005
1000
0.005
Telco Bin
Monks
0.000
0.2
40-
0.00
0.05
0.10
0.15
0.20
0.25
0.00
0.05
0.10
0.20
0.25 0.00
0.05
0.20
Label naise,
Label noise, P
Label noise, P
(a)
(b)
Figure 7: Practitioner's validation process in the presence of noise for gradient boosted trees. For fixed number of estimators, we add noise, the gap between training and validation accuracy increases (Subfigure a). As we use cross-validation to select the number of estimators, the best number of estimators decreases with noise (Subfigure b).
36

---

on the training set and computed the best depth. We fixed this depth (and thus hypothesis space). Then, we start adding noise to the dataset. We considered six different noise levels, E {0,0.t 0.03, 0.05, O. 10, 0.15, 0.20.0.25). For every level, we performed 25 draws of Sp- For every noise level, noise draw, and train/validation split, we evaluated train and validation performance and reported the average.
For Figure [b), we tuned the parameters for each noise level. We will see that noisier datasets lead us to use more regularization. We started adding noise to the dataset and then chose the best parameter based on cross-validee vooss-vali, More specifically, we considered six different noise levels, E {0, 0.03, 0.05, 0.10, 0.15, 0.20.0.25). For every level, we performed 25 draws of Sp. Then we performed 5-fold cross- posss-validttion on the training data choose the best depth for CART. For every noise level, noise draw, and main/validation split, we report mean depth based on cross-validation results.
We performed a similar experiment to Tigure[ the gradient boosting algorithm, where we varied the number of tree estimators. We observe similar behaviors, where, with more noise, the best number of estimators (according to cross-validation) decreases. We used the same level of noise and cross-validation procedure as discussed above. For the number of estimators, we considered values d E (5, 10, 20, 150J.
K.3 Branch and Bound Method to Compute Patterns in the Rashomon set
Here describe two-step method that allows to compute all patterns in the pattern Rashomon set. In the first step, we reduce the complexity of the problem, by discarding points that have low sample agreement. In the second step, we patterns and discard prefixes of those patterns that will not be in the Rashomon set based on the Rashomon parameter and the empirical risk of the empirical risk minimizer.
branch-and-boume approach in order to enumerate
Consider a dataset = {z } For every point z; assume that we have sample agreement dz a, 0, it means that all patterns in the pattern Rashomon set assign an incorrect label to sample ze. On the other hand, if a; = 1, all patterns assign the correct label. If we exclude all 2 such that a, 0 or a; from the dataset, then the number of patterns will not change in the Rashomon set. Therefore, for a given point žạ (A- 1..n) we will try to answer a question: is there a model in the Rashomon set such that it classifies set. If there is no such model, then sample 2₁ has no influence on the pattern Rashomon set. Since is harder to optimize for 0-1 loss, instead consider exponential loss. If the problem is separable by 0-1 loss, then exponential loss will converge to separable solution exponentially fast (which is known from the convergence analysis of AdaBoost [4].. Then given hypothesis space of linear models F = [w'xr., for every zg. we aim to solve following optimization problem:
(IR, -2k) correctly and still stays in the Rashomon
min
(8)
2=
31-00 3k S 0,
and then check if wTx is in the Rashomon set defined by 0-1 loss.
Since we optimize exponential loss, is fast to solve the optimization problem with gradient descent. More importantly, we can run the optimization in parallel for samples zą. After, we consider dataset Siside that contains only those samples for which models were the Rashomon set that could accommodate misclassified zg. We formally define the dicard point procedure in procedure DISCART POINTS below:
procedure DISCARD POINTs(dataset S, ERM f, the Rashomon parameter 0)
Initialize Sap-
for every = = (2r, y) E S do
Solve optimization problem 8 Let f be a solution.
if iff) > i(f) + then add to Sáp (this point has single predicted label for the entire Rashomon set).
end if end for return Sap- end procedure
37

---

In the second step, we build search tree over the set of patterns that are formed by samples in Sinside- We use breadth-firs first search over subsets of data. We "bound" (i.e., exclude part of the search space) when the prefix of the pattern (which is the part of the dataset we are working with) misclassifies more samples than the threshold to stay in the Rashomon set, which is L(f) + 0. Since not all patterns can be realized by the model class. We "bound" if the prefix or pattern can not be achieved (the pattern is achievable when all points with labels matching the pattern are classified correctly by some model from the hypothesis space). In order to perform branch and bound more effectively, given empirical risk minimizer (ERM), we sort points in the dataset based on their distance the decision boundary of the ERM. More specifically, we split the points into four categories depending on whether the point is category, we compute the distances from each point to the decision boundary of the ERM and then sort points from least distance greatest distance. Finally, cyclically choose category until all samples have been considered. Conceptually, true positive and true negative samples that are closest the decision boundary determine most of the patterns in the pattern Rashomon set. We add false positives and false negatives early to the order of points as they are more likely to be misclassified, allowing us to bound the prefixes sooner. We describe the branch and bound procedure [T]
positive, false positive, true negative, false negative. Then for every
point from each
in Algorithm[] We use bit vectors to represent prefixes and patterns to speed up computations. Since we apply this approach linear models, we use logistic regression without regularization to check the achievability of the patterns and their prefixes. However, the algorithm in general can be applied to other hypothesis spaces and losses (for example, hinge loss).
Algorithm 1 Branch and bound approach to find the pattern Rashomon set
Input: The Rashomon parameter 0, dataset S = X x Y. ERM f. algorithm A. Output: Pattern Rashomon set π (F,0). 0).
1: Run DISCARD POINTS(S, / 0) to exclude points that have the same predicted label for all models in the Rashomon set. Let Sap be the set of discarded points, and Suside be the rest of the points.
2: Divide points in Sinside into four categories: true positive, false positive, true negative, and false negative.
3: Compute the distance from the decision boundary of f to every point for every category.
4: Sort points in ascending order for every category.
5: Create a new order of the points in Sincide by iteratively choosing points from each of the four categories until all points in Sinside are re-ordered.
6: Concatenate Sdp and Sjnside to form S = X x Y based on the new order, where discarded points are followed by the sorted points.
7: Initialize the prefix Pinit of length (Sppl based on the labels of the samples in Sap-
8: Initialize Q as the queue for the breadth-first search over the prefixes.
9: while S |Sinsidel (loop over all points in Sinsite) do for every elem Q (loop over all prefixes in Q) do for E [0 (loop over possible labels; this is a "branch" step) do Y, k==Ys: Ys., U Uelem U e (consider potential prefix).
11:
12:
13:
Form the training data (Xa, Ya) to check if the prefix is achievable by algorithm A.
Xa consists of the first [Sapl + i samples of sorted X.
14:
Fit algorithm A on (X,, Y.) and compute accuracy and loss.
15:
if accuracy = 1 and loss < L(f)) 0 then Q.append(elem U e) (the prefix is achievable and the pattern has the potential to be achieved in the pattern Rashomon set, thus we add this element to the queue. This is "bound"
16:
step).
17:
end if end for end for
18:
20:
end while
As we have now looped over all samples, Q contains all the achievable patterns that are in the
Rashomon set, set [F, 0) Q.
38

---

K.4 Computation of Rashomon Ratio and Pattern Rashomon Ratio for Step 4
We considered the hypothesis space of sparse decision trees of various depths and the hypothesis space of linear models with given number of non-zero coefficients.
For decision trees (Figure (a)), we varied the depth of the maximum allowed decision tree from 1 to To compute the numerator of the Rashomon ratio, used TreeFARMS [52]. We the Rashomon parameter to 5%. To compute the denominator of the Rashomon ratio, we considered all possible sparse decision up to given depth d and used the following recursive formula to compute the size of hypothesis space with m features:
C(d, m) = 2 - 1,
where C(O,-) 2. In the base case, the only possible trees classify every point as O, or every point 1. Then for decision trees up depth with m 2 features, there are two cases. The first case when the tree has depth 0 which produces 2 possible trees. The other case is when the tree has depth least In this case, there are m possible features to initially split on, and then the left and right features to choose from. The left and right subtrees
subtrees are of depth at most d - 1 with can be chosen independently of each other, we have mC m 1)² trees in this case, which proves the overall recursive formula.
Note that for decision trees of depth exactly equal for every tree path, following recursive formula holds
commllete (d, m) mC mC (d 1, 1)²,
which is equivalent to closed-form solution described in appendix
For the hierarchy of regularized linear models (Figure 2 (b)), we considered regularization for 1 non-zero coefficient, non-zero coefficients, 3 non-zero coefficients, and 4 non-zero coefficients. To compute the numerator of the pattern Rashomon ratio, used the approach described in Section K.3 We set the Rashomon parameter to 3%. To compute the denominator of the Rashomon ratio, used the formula that gives the number of all possible patterns for the hypothesis space of linear models: if no 1 points are coplanar, C(n, m) = "I ("-1) [10].
K.5
Experiments for Pattern Diversity and Label Noise for Linear Models
Number of Patterss
800
Wine
Pattern Diversity
0.07
Wine
600
0.04
0.05
0.04
0.03
0.00
0.05
0.10
0.15
0.05
0.10
0.i5
Label noise, p
Label noise, P
(a)
(b)
Figure 8: Rashomon set characteristics such as the number of patterns in the Rashomon set (Subfigure and pattern diversity (Subfigure b) tend to increase with uniform label noise for hypothesis spaces of linear models.
For the hypothesis space of linear classifiers, we show the pattern diversity and the number of patterns the Rashomon set for different datasets the presence of noise in Figure We considered uniform label noise, where each label is flipped independently with probability
We set noise level p to values {0, 0.02, 0.04, 0.0G, 0.08, 00, 0.15) and performed five draws of S, for every noise level. We then computed the pattern Rashomon set for each draw using the method described in Appendix K.3 and finally computed the pattern diversity. Both the number patterns and pattern diversity tend to increase with label noise.
39

---

log Rratio, %
-100
0-003
Diversity
-130
0.2
0.03
-200
0.1
50-
0.09
0.0
8 0=0.11
-900
8i0
0.20
Tree depth
Label
Label
(a)
(b)
(c)
Figure 9: (a) Curve of the hypothesis space complexity vs. Rashomon ratio (as Figure 2 stays the same shape for different Rashomon parameters for the Monks 3 dataset for the hypothesis space of sparse decision trees. (b, c) Rashomon characteristics tend to increase with uniform label noise for the hypothesis space of decision trees (as in Figure 3) for different Rashomon parameters for the Monks 3 dataset. For (b) and (c), we averaged over 25 iterations.
K.6 The Choice of the Rashomon Parameter does not Influence Results
the Rashomon parameter be 5%. In Figure 9 the example of Monks 3 dataset, we show that the results in Figures 2(a) and hold for different values of the Rashomon parameter.
For Figures 2(a) and
K.7 Computation Resources
We performed experiments on Duke University's Computer Science Department cluster. We paral- lelized computations for the majority of the figures. It took up 3 hours to compute the Rashomon sets for the hypothesis space of sparse decision trees for different noise levels and draws (Figures and 9) and up to 48 hours for the hypothesis space of linear models (Figures and
40


Reviews:
[{"review_id": "4cf9F34InS", "reviewer": "Reviewer_9wZ5", "summary": "The authors explore how the Rashomon Ratio (the fraction of all models that are in the Rashomon set) changes in the presence of label noise. They show that increased label noise causes the expected variance of the ERM’s performance to increase. Then, they hypothesize that this increased variance leads practitioners to use simpler model classes, which are known to have higher Rashomon Ratios. They also introduce pattern diversity as a metric for how diverse the prediction patterns are across members of the Rashomon set. The authors provide empirical support across several datasets that (i) simpler models perform better when a dataset is noisy, (ii) simpler model classes have higher Rashomon ratios for decision trees and linear models, and (iii) Rashomon set size, number of Rashomon patterns, and diversity of these patterns tends to increase with label noise. The authors are also forthright about the limitations of their work, and provide a nice overview of open questions related to Rashomon Ratios in the presence of noise.\n", "questions": "A couple of minor points:\n* In section 5.1, wouldn’t it make more sense to call $a_i$ the sample agreement? (Or otherwise, to change its definition to sum over the indicator function with $p_k^i \\neq y_i$? ) \n* In the equation under line 166, should $p$ (with no subscript) appear at all? \n\nOne bigger question:\n* Do the results hold empirically when labels are not randomly corrupted? E.g., label errors are more likely in some subset of the population.", "limitations": "* Soundness limitations — see weaknesses above\n* The paper only considers random, uniform label noise. This seems more acceptable as a first step for the theoretical contributions, but real-world label noise is often not random and can be correlated with protected demographic group attributes. Given that the Rashomon effect is of particular interest in social prediction tasks, I wish the authors had explored how their findings generalize to realistic noise settings.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Provides one of the first theoretical studies on the Rashomon effect. As the users state, there are important policy implications of the Rashomon effect and understanding the phenomenon is important to being able to craft policy around it.\n* The theoretical results are also shown to hold empirically on real datasets. \n* The “limitations” section is very welcome, as it helps the reader to contextualize what this paper does and does not do. It also provides a good set of ideas for future research.\n* The paper is generally well-written. The \"path\" framework is not perfect (see weaknesses), but I appreciate that the authors try to account for how both theoretical properties of the data and human choices lead to large Rashomon sets.", "weaknesses": "* Certain claims are not proven in a broad sense and this is not clearly delineated (or worse, the authors claim something more general than what they prove)\n  * Uniform label noise vs real-world patterns of noise: Theorem 2 shows that variance of the loss increases with uniformly random label noise, however, in lines 167-168, the authors say that it “holds more generally,” which is not true\n  * The paper is written in a way that assumes that ML practitioners are following the standard ML pipeline (e.g., switching to a simpler model class given poor test set performance) but these claims are not backed up by any data. I would encourage the authors to see if the HCI literature has studied ML practitioner behavior in this situation, and if not, to reframe the paper so that it doesn’t present the human behavior narrative as fact.\n* Presentation \n  * Generalization is a key part of the argument in section 4, but the paper never defines generalization or generalization bounds. \n  * The discussion of learning with noise in the related works section also seemed very brief given the amount of work that this topic has received. For example, there is work that aims to learn more stable models in the presence of label noise.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review. We address the questions point-by-point below.\n\n**Weakness point 1.1 (uniform label noise vs real-world patterns of noise in Theorem 2):** Apologies for the confusion. In the text, we were not trying to assert that Theorem 2 holds more generally, but that variance of losses generally increases with noise. To strengthen this point we added more experiments with other types of noise (please see Figure 1 in the global response pdf file). We considered two other noise models, including margin noise (when mistakes in labels are made near the decision boundary) and attribute noise (when mistakes are made in the feature matrix) noise for high dimensional Gaussians and binary real-world datasets, and show that variance of loss increases with noise.\n\nMargin noise is realistic, common, and occurs when data arises from Gaussians. Because of the central limit theorem, data often follow gaussian distributions. Also, a combination of gaussian and uniform random noise is quite realistic due to the central limit theorem and because of clerical errors causing label noise (extreme points on either side do not necessarily have perfect labels). \n\nAdditionally, we generalized Theorem 2 to non-uniform noise models (please see author rebuttal for Theorem statement). Now, for a sample $(x, y)$, each label $y$ is flipped independently with probability $\\rho_x$ (instead of label $y$ being flipped with uniform probability $\\rho$). We show that the variance of losses increases with this non-uniform label noise. In the non-uniform noise model, noise can depend on $x$. This includes cases related to fairness where one subpopulation has much more noise than another.\n\n**Question 3: (the case when label errors are more likely in some subset of the population):** That’s a good point. Yes, our results will hold in this case. We mentioned above that we generalized Theorem 2 to the case when noise over labels is non-uniform, and each label is flipped independently with probability $\\rho_x$ which depends on $x$. Such change allows one to design noise models differently for subpopulations. Note that Steps 2, 3, and 4 in the path we described in the paper are independent of the noise model.\n\nEven if we consider only uniform label noise, in practice, typically when a practitioner is facing a subgroup that is different from others, they would create a separate model for that subgroup to increase the chances of performing well on all groups. In that case, our results would also apply to each model separately. \n\n**Limitation point 2 (concern about fairness):** Besides the generalization of Theorem 2 and experiments described above, we would like to add that the Rashomon effect is actually very important for fairness [Coston et al, Characterizing Fairness Over the Set of Good Models Under Selective Labels, 2021], and knowing when the Rashomon effect is large is beneficial for the search of a fair model. Unintuitively, even if the noise generation is not fair (we do not support this happening, we are saying if data happen to be this way), large noise will still lead to larger Rashomon ratios as explained in our paper. If the practitioner knows that the Rashomon effect is large, they can explore the Rashomon set in order to find a more fair model [Coston et al, Characterizing Fairness Over the Set of Good Models Under Selective Labels, 2021].\n\n**Weakness point 1.2 (ML practitioners that follow the standard ML pipeline):** Thank you for pointing out the assumption on our part. We did assume that the machine learning practitioner follows the common ML pipeline and is knowledgeable about overfitting and common steps in preventing overfitting. We will add the assumption that we define a machine learning practitioner as someone who operates in the standard machine learning pipeline to the paper - we hope that this should solve the issue. We point out that the pipeline we assumed is extremely common and we haven’t seen someone not following this. Choosing a simpler hypothesis space (basically regularization) is a common step for essentially all ML algorithms. There also could be many ways to control the complexity of the model. For example, for tree boosting, parameters that can control complexity include a number of estimators, maximum tree depth, minimum leaf weight, and so on.\n\n**Weakness point 2.1 (generalization):** In the paper, we say that there is good generalization when the generalization error (as the difference between training and test performance, see Vladimir Vapnik, Statistical Learning Theory) is small. Correspondingly, we say that the generalization is bad when the generalization error is large. We will add the definition to the paper.\n\n**Weakness point 2.2 (learning with noise related works):** The learning with noise literature is only tangentially related, despite the similarity of the name. These papers focus on specialized techniques for cleaning up or compensating for noisy data, while our paper focuses on studying what noisy data tells us about simple models (models created with standard algorithms, not the ones specialized for specific types of noise). Thank you for pointing it out anyway, we will add more citations to the related work section in case the audience of our paper would like to learn more about algorithms with noise correction.\n\n**Question 1:** Yes, we can call a_i sample disagreement.\n\n**Question 2:** Thank you for finding a typo in line 166. We have corrected it.\n\nThank you for the review and for identifying ways to improve our paper. We believe the definitions and clarifications handle both weaknesses you’ve pointed out. Hopefully the new analysis based on different noise models and generalized theorem additionally supports the path that noisy datasets essentially lead to larger Rashomon ratios, which enables the search for simpler (and fair) models."}, {"review_id": "GRV6gaKElS", "reviewer": "Reviewer_y6w5", "summary": "The Rashomon set is the collection of all models that perform almost equally well in a given dataset. The Rashomon ratio is the fraction of models that are members of a given hypothesis class and simultaneously are in the Rashomon set. The paper studies the relationship between noise in the data generation process and the Rashomon ratio. The authors also argue that noisier datasets lead to a larger Rashomon ratio. Finally, the authors also define a measure that captures the average difference in prediction across different classification patterns in the Rashomon set.", "questions": "* How would the results change when other losses (beyond the 0-1 loss) are used? Is it expected that the same/similar results will hold? It might be interesting to illustrate the results using other losses experimentally. \n\n* How can we compute the pattern diversity metric when listing all models in the Rashomon set is impossible? For example, how to compute the pattern diversity metric for SVMs?\n\n* How does Theorem 11 relate to Theorem 10? What should a practitioner expect when there is noise in both the label and the features?\n\n* How tight is the upper bound in Theorem 9?", "limitations": "The authors discuss the limitations of the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper is well-written, and the problem of studying how data noise affects the Rashomon set is interesting. \n\n* Proposition 6 is interesting and confirms (in a specific scenario) that more complex hypothesis classes would lead to smaller Rashomon ratios. The experiments in Figure 2 (a) and (b) help illustrate Proposition 6.\n\n* The idea of defining a pattern Rashomon set is interesting, and using it as a proxy for exploring the Rashomon set can be helpful in other applications.", "weaknesses": "* Some of the provided bounds are non-computable. For example, the bounds in Theorem 4 (as the authors discussed in the paper) and Theorem 9 (the empirical risk minimizer is not always attainable) can not be computable.\n\n* The pattern diversity metric (listed in the Abstract as a contribution) is a slight modification of the pairwise disagreement metric -- specifically, it assumes that all patterns are equiprobable. The result of Proposition 16 shows that these metrics may have different values in a particular (and maybe unrealistic) scenario. I encourage the authors to explore the differences further. Moreover, the authors could discuss when pattern diversity is useful but pairwise disagreement is not. \n\n* The paper shows that when label noise is large enough, the loss variance is larger; hence, the Rashomon ratio may also be larger. With this chain of thought, one can conclude that simple models may exist. However, given a dataset, it needs to be clarified how to decide whether the label noise is high. Moreover, even assuming that there exists a black box that gives practitioners the level of label noise, it is necessary to answer the question: How large the noise needs to be for simpler models to exist? \n\n * Most of the results depend on the fact that the 0-1 loss is being used. However, other losses may be preferred in practice, and discussing how the results extend to other losses is necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n**Weakness 1 (Theorem 4 and 9 bounds):** Theorem 4: Indeed the size of the true Rashomon set is not computable as we pointed out. We also pointed out that it doesn’t really matter - the bound still tells us what’s going on whenever the Rashomon set is large. The paper (Semenova et al, On the Existence of Simple Machine Learning Models, 2022) provides a way to assess whether the Rashomon set is large using several different ML algorithms. So, we often have indirect indicators that the Rashomon set is large, which are sufficient to give confidence that Theorem 4 is meaningful qualitatively. For Theorem 9, we actually might be able to compute the empirical risk minimizer for some hypothesis spaces (for example, it can be computed exactly for sparse decision trees, see the GOSDT algorithm of Lin et al). Even if the algorithm produces an approximation $L^u(f^u)$ of $\\hat{L}(\\hat{f})$, the right-hand side of equation (2) in Theorem 9 is monotonic with respect to $\\hat{L}(\\hat{f})$ when the loss is below 0.5. Therefore, the quantity $2L^u(f^u)(1-L^u(f^u))$ is a tight upper bound that we can compute.\n\n**Weakness 2 (pattern diversity vs pairwise disagreement):** The pairwise disagreement metric and pattern diversity work in different domains. While pairwise disagreement metric compares different functions, the pattern diversity looks into all possible unique classification patterns on the data. Pattern space allows us to avoid problems with reparameterization that can cause issues, even completely change the loss landscape [see Dihn et al, Sharp minima can generalize for deep nets, 2017]. In Figure 4 in the global response file, on a simple example, we show how different parameterizations change the pairwise disagreement metric. The advantage of pattern diversity is more evident when we think about the computation of the two metrics. We can compute the pattern diversity by enumerating all possible patterns on the given finite dataset as described in Appendix K.3. We cannot do the same for the pairwise disagreement metric without additional assumptions on patterns’ support (how many functions achieve this pattern).\n\n**Weakness 3 (the necessity of knowing when noise is high):** Interestingly, the user does not ever need to know the exact level of label noise! If they suspect label noise is present, our results say that when they try to apply an interpretable ML method, they are likely to maintain performance compared to a black box model. So, all the user needs to do is apply an interpretable ML method and see if they get a good performance. They do not need to assess label noise empirically at all.\nOur paper simply explains the reason why they would expect good performance from the simpler models. Since there is a long-held belief in an accuracy-interpretability tradeoff, our goal is to explain that such tradeoff is not always present, and why that is.\n\n**Weakness 4 (dependence on 0-1 loss):** This is true, but hopefully this is not a critical limitation of the paper. 0-1 loss is a useful starting point for understanding many ML concepts and has been actively used in theory. We acknowledge that going beyond 0-1 loss would be worthwhile future work in the Limitations section. There is an *enormous* literature just on 0-1 loss so we are not unique - this reflects that there exist many yes/no prediction problems.\n\n**Question 1 (other losses):** We tried to answer this question in the Limitations section of the paper. For least squares and ridge regression, the noise is equivalent to regularization and we show in Theorem 11 that the Rashomon volume decreases. However, the hypothesis space will change as well with the regularization, so our results might still hold in this case, we just have no way to assess it theoretically yet. \n\n**Question 2 (diversity for continuous space):** The pattern diversity relies on patterns, which are finite for finite datasets. Therefore, we can enumerate all patterns and compute pattern diversity, even if the hypothesis space is infinite. The algorithm described in Appendix K.3 will work for SVM as well as other hypothesis spaces. It will be computationally expensive for larger datasets, so additional optimizations (similar to the procedure to discard non-relevant points in Appendix K.3) might help to handle the complexity. \n\n**Question 3 (Theorem 10 and 11):** Those two theorems have different setups and are designed to make different points. Theorem 11 is for ridge regression and least squares loss, while Theorem 10 is designed for classification and 0-1 loss. For classification and 0-1 loss, if the dataset has attribute and label noise, we expect the results identified in Section 4 to hold. To support this point, we empirically show that the variance from Step 1 increases with attribute noise. We consider additive noise for data generated from Gaussians and uniform random noise for binary real-world datasets (Figure 1(b)-(c) in the global response file). Steps 2, 3, and 4 of our path in Section 4 are noise model independent. For Section 5, under attribute and label noise, we empirically observe that the characteristics tend to increase for the majority of the datasets (Figure 2 in the global response file). Because we use algorithms that regularize the number of leaves, with more attribute noise regularization can distort the trend as we get shallower trees (Figure 2d).\n\n**Question 4 (Bound in Theorem 9):** The bound holds with equality when the Rashomon parameter and the empirical risk are 0. The bound is tighter when the risk is lower and the Rashomon parameter is smaller. Since the bound is general, it becomes looser as the risk increases since we might encounter many different possible scenarios of point disagreement distributions.\n\nThank you for the review and pointing out ways to improve our paper. Hopefully, the new analysis based on different noise models, our answers, and clarification can handle the weaknesses that you identified."}, {"review_id": "U5Apa9NaCI", "reviewer": "Reviewer_CJvU", "summary": "How does noise influence the set of models that have similar performance? This paper presents a study that decomposes the problem in three stages, first showing how noise in labels harms generalisation, second, lower generalisation capability leading to more restrictive model choices, and lastly showing that the restrictive model space has a larger Rashomon ratio (i.e. larger proportion of models in this space with similar performance). The main claim is in presenting a technical argument for use of simpler (interpretable) models in critical domains, as these tend to be noisy. ", "questions": "None.", "limitations": "- While there are some useful analytical results, the paper largely rests on empirical work. The authors have alluded to this in their limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The central idea of promoting simpler models on account of noise in real-world datasets is noteworthy. The use of arguments, albeit limited, to demonstrate a plausible sequence of choices leading to simpler model specification is also interesting.", "weaknesses": "- The presented results use a patchwork of assumptions, model classes and conditions to hold for each result. I appreciate a comprehensive evaluation is out of scope and this is intended to be a plausible mechanism. This implies that the overall conclusions are only weakly supported.\n\n- How does label noise influence the Rashomon ratio? Empirical evidence of this central point should be directly provided. Figure 2 breaks this down by tree depth, and Figure 3 offers characteristics of the set. The paper would benefit from a more direct noise-to-metric plot.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating the goals of our paper, which makes initial steps towards understanding broad trends that we believe have been under-studied. \n\n**Regarding weakness point 1**: Given that we can’t prove things in all generality (though of course, we would like to), we did our best to provide empirical evidence for those steps in the path we described. We hope that the combination of theory and experiments we provided in the paper are valuable and show that there are multiple angles from which this issue can be productively studied, as is often the case with interesting machine learning phenomena. If there are specific experiments you would like to see, we are happy to do them. We further hope that the gap between theory and experiments can be narrowed in future work, and welcome your suggestions for how to do so.\n\n**Regarding weakness point 2**: Figure 3 in the paper provides the noise-to-Rashomon ratio, the noise-to-pattern Rashomon ratio, and the noise-to-diversity plots for uniform random label noise. For Figures 3a and 3b, on the x-axis, we have the probability with which each label is flipped, and on the y-axis the numerator of the Rashomon set metric. Since the hypothesis space is chosen before seeing data, it does not change as we add more noise to the dataset, so the denominator of the Rashomon ratio and pattern Rashomon ratio stays the same. This means that only the numerator of the Rashomon ratio changes, which is the number of trees in the Rashomon set (Figure 3a) and the number of patterns in the Rashomon set (Figure 3b). In other words, the y-axis in Figure 3a and Figure 3b is a constant multiplied by the Rashomon ratio (3a)  and pattern Rashomon ratio (3b). \n\nThank you again for the review."}, {"review_id": "O5WIRkpeeG", "reviewer": "Reviewer_26ns", "summary": "The authors propose a possible explanation for the often large Rashomon ratios in tabular datasets (criminal justice, healthcare, etc.). The explanation involves both the dataset generation process and choices made by the practitioners who train the model. The main thesis is that label noise leads to the adoption of simpler models. The authors provide empirical and theoretical justifications to support this hypothesis. In addition, the authors propose a new Rashomon metric.", "questions": "1. Is there a way to define (an equivalent to) the Rashomon ratio for a continuous hypothesis class?\n1. Does the provided analysis hold for a continuous hypothesis class?\n", "limitations": "Addressed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and well-organized.\n1. The paper focus on an important topic with practical implications for critical domains like criminal justice, healthcare, etc.\n1. The authors provide an in-depth theoretical and empirical analysis to support their claims.\n1. The authors introduce a new Rashomon metric.\n", "weaknesses": "1. It would be beneficial to give some definition/example of a “simple model” in the introduction.\n1. In the definition of the true Rashomon set, did you actually mean to take $L(f)<L(f^*)+\\gamma$ in the definition of $R_{set}$? Otherwise, we should take $\\gamma>=1$.\n1. It would be interesting to see if the results generalize to more complex datasets and models.\n1. Could you provide references to support the claim that the assumptions in Prop. 6 generally holds in practice?\n1. How does the choice of the Rashomon coefficient affect the analysis? For example, could you provide Figures similar to Fig. 1, but for different choices of the Rashomon coeff?\n1. Could you please elaborate on the motivation for defining the pattern diversity and on the connection to larger Rashomon ratios? This is not clear from Sec 5. If I understand correctly, the relation is only established through the analysis which shows that both Rashomon ratios and pattern diversity increase with noise.\n1. While the arguments in Sec 4 regarding the path taken by the practitioner appear plausible, I’m not entirely convinced. \n\nMinor:\n1. Line 41: there’s a missing period before “Our”.\n1. Line 88: “...that often there are often…”\n1. Line 139: $p_f$ -> $p^f$. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review, we really appreciate it. Please see below our response to your questions.\n\n**Weakness point 1 (example of a “simple model”)**: Yes, we will add an example to Introduction. Consider a hypothesis space of linear models with real-valued coefficients in m dimensions. Then a simpler model will be a linear model with at most m’ coefficients, where m’ is significantly less than m.\n\n**Weakness point 2 (definition of the true Rashomon set)**: Yes it is correct, thank you for identifying the typo on our side. We corrected it.\n\n**Weakness point 3 (generalization to more complex datasets and models)**: We used 20+ real-world datasets, the most complex of which involved 10K+ data points and 18 features. We expect that further advances in methods for efficiently computing the number of patterns (e.g., along the lines of Appendix K.3) will permit even larger models and datasets to be considered in the future.\n\n**Weakness point 4 (Proposition 6 assumptions)**: An example of when the leaf assumption of Proposition 6 is satisfied is the GOSDT algorithm (see  Lin et al, Generalized and Scalable Optimal Sparse Decision Trees, 2020). For GOSDT, each leaf is created only if adding this leaf will provide sufficient improvement to the loss compared to the regularization on the number of leaves. We believe that the assumption on features is not strong, as we expect that with high probability trees that have low accuracy (and thus are not in the Rashomon set) will not contain good features. (That is, the model should be at least as good as its best feature, so models that are poor can’t even have one good feature.)\n\n**Weakness point 5 (does Rashomon parameter effect analysis)**: Figure 1 actually does not depend on the Rashomon parameter. It illustrates the practitioners' validation process. Similar trends to Figure 1 hold for other hypothesis spaces as well. Regarding Figures 2 and 3 from the paper, in the global response pdf file we show that for a real-world dataset, the choice of the Rashomon parameter does not influence results (see Figure 3 in the global response file). We illustrate this point for one dataset, but it holds for the other datasets as well.\n\n**Weakness point 6 (Section 4 and 5 connection)**: That is correct. Sections 4 and 5 make two different points, where both of them show that Rashomon set metrics increase in the presence of noise. \n\nIn Section 5, we wanted to show that when the practitioner does not follow the path, there are still large Rashomon sets in the presence of label noise. Therefore, we showed empirically that different Rashomon set metrics tend to increase with noise and this is a connection between diversity and Rashomon ratios. We do not have a bound that connects the two yet, and this is a part of future work. In the case of pattern diversity, we were able to bound it and show an increase in the upper bound with noise in a more general case than our empirical results.\n\n**Weakness point 7 (regarding practitioner following the path)**: With respect to Step 3, we assumed that the machine learning practitioner follows the common ML pipeline and we will add clarification to the paper by defining the practitioner as such. Thank you for pointing this out. Please note that we believe that this ML pipeline is extremely common and we haven't seen someone not following it. Reducing complexity (or regularization) is a very common tactic to prevent overfitting for various ML algorithms.\n\n**Question 1 (definition of the Rashomon ratio for a continuous hypothesis space)**: In the paper we use the pattern Rashomon ratio for continuous hypothesis space and classification, as the set of classification patterns is finite for a finite dataset (for example, for linear models see Figure 2b and Figure 4 in Appendix K.5). There is a general definition of the Rashomon ratio for continuous space (Semenova et al, On the Existence of Simple Machine Learning Models, 2022), however, it depends on the prior over the hypothesis space which might not be known.\n\n**Question 2 (does the analysis hold for continuous hypothesis space)**: Yes, let’s walk the path for the continuous hypothesis space. Step 1 (variance of the loss increases with noise) does not depend on the size of the hypothesis space. For Step 2 (higher variance leads to worse generalization), the generalization bound can be easily extended to the covering number bound when the hypothesis space is continuous (in this case, instead of the cardinality of the hypothesis space, the bound will rely on the size of the cover of the hypothesis space). Step 3 (practitioner chooses a simple space) is a regularization technique that is common for continuous spaces as well. Finally, we show empirically that Step 4 (Rashomon ratio goes up) holds for continuous hypothesis space of linear models in Figure 2b.\n\n**Minor**: Thank you for finding typos, we corrected them.\n\nThank you again for the review. Hopefully provided answers, new analysis, and clarification addressed weaknesses and questions highlighted in the review."}]

Author rebuttal:
We thank all the reviewers for the reviews. Below we provide a generalization of Theorem 2 to non-uniform label noise. In the response file, we also provide additional figures and analysis. 

**Theorem** (Generalized Theorem 2 to non-uniform label noise). Consider 0-1 loss $l$, infinite true data distribution $D$, and a hypothesis space $\mathcal{F}$. Assume that there exists at least one function $\bar{f}\in\mathcal{F}$ such that $L(\bar{f}) < \frac{1}{2} - \gamma$. For a fixed $f \in \mathcal{F}$, let $\sigma^2 (f, D)$ be the variance of the loss, $\sigma^2(f,D) = Var_{z\sim D} l(f,z)$ on data distribution $D$. Consider non-uniform label noise, where each label $y$ is flipped independently with probability $\rho_x$, $(x, y) \sim D$. Let $D_{\rho}$ denote the noisy version of $D$. For any $\delta >0$, let $D_{{\rho}^{\delta}}$ be a noisier data distribution than $D_{\rho}$, meaning that for every sample $(x, y)$ the probabilities of labels being flipped are higher by $\delta$: $\rho_x^{\delta}=\rho_x+\delta$. If for a fixed model $f \in R_{set}(\mathcal{F},\gamma)$, $L_{D_{{\rho}^{\delta}}}(f)<0.5$, then 
$\sigma^2 (f, D_{\rho}) < \sigma^2 (f, D_{{\rho}^{\delta}}).$

Meta-review: The reviewers accepted the paper unanimously and maintained their positive scores post-discussion. Exploring the Rashomon effect is an exciting research direction in machine learning. Rashomon ratios provide a concrete metric for quantifying the impact of the Rashomon effect on different aspects of ML. The paper's intriguing finding that lower complexity function classes lead to larger Rashomon ratios can impact when interpretable models *must* be used in practice, i.e., when there is "no excuse" not to use an interpretable model. The paper's findings and the discussion it promotes are a significant contribution to NeurIPS.

I encourage the authors to take the reviews seriously when reviewing their manuscript and incorporate the answers given in the rebuttal.
Decision: Accept (poster)