Using Noise to Infer Aspects of Simplicity Without Learning
Authors: Zachery Boner
Harry Chen
Lesia Semenova
Ronald Parr
Cynthia Rudin
Venue: NeurIPS 2024 poster (2024)
Keywords: interpretable ML
simple models
Rashomon sets
Primary area: interpretability_and_explainability
TL;DR: Our work offers insights on whether simple-yet-accurate machine learning models are likely to exist, based on knowledge of noise levels in the data generation process.

Abstract: Noise in data significantly influences decision-making in the data science process. In fact, it has been shown that noise in data generation processes leads practitioners to find simpler models. However, an open question still remains: what is the degree of model simplification we can expect under different noise levels? In this work, we address this question by investigating the relationship between the amount of noise and model simplicity across various hypothesis spaces, focusing on decision trees and linear models. We formally show that noise acts as an implicit regularizer for several different noise models. Furthermore, we prove that Rashomon sets (sets of near-optimal models) constructed with noisy data tend to contain simpler models than corresponding Rashomon sets with non-noisy data. Additionally, we show that noise expands the set of ``good'' features and consequently enlarges the set of models that use at least one good feature. Our work offers theoretical guarantees and practical insights for practitioners and policymakers on whether simple-yet-accurate machine learning models are likely to exist, based on knowledge of noise levels in the data generation process.

Using Noise to Infer Aspects of Simplicity Without Learning
Zachery Boner Harry Chen Lesia Semenova"* Ronald Parr Cynthia Rudin'
'Department of Computer Science, Duke University, Microsoff Research
zachery. bonerdduke edu, harry. chen0840duke edu, 1semenova@mi cwosoft. com, ronald, parrlduke edu, rudin@dkkd edu
Abstract
Noise data significantly influences macciiinn-makigg. in the data science process. In fact, it has been shown that noise in data generation processes leads practi- tioners to find simpler models. However, an open question still remains: what is the degree of model simplification In this work, we address this question by investigating the relationship between the amount of noise and model simplicity across various hypothesis spaces, fo- cusing on decision trees and linear models. We formally show that noise acts as an implicit regularizer for several different noise models. Furthermore, we prove that Rashomon sets (sets of near-optimal models) constructed with noisy data tend to contain simpler models than corresponding Rashomon sets with non- noisy data. Additionally, we show that noise expands the set of "good" features and consequently enlarges the set of models that use least one good feature. Our work offers theoretical guarantees and practical insights for practitioners and policymakers on whether simple-ye simple-yet-accurall machine learning models are likely to exist, based on knowledge of noise levels in the data generation process.
expect under different noise levels?
Introduction
Machine learning (ML) is being used more and more for high-stakes decisions, and there is a need for clear policy guidance. Simple models have advantages: they much easier to troubleshoot and use. However, there is a concern that they are not as accurate as more complex black box models, which makes it challenging to provide guidance for policy makers recommend simple models.
We believe we have barely scratched the surface of understanding simplicity in machine learning. Recent work suggests we consider the Rashomon Effect [Breiman] [200]] which is the phenomenon that datasets often admit many different good models. (Semenova et al. [2022) shows that when there are lot of good models, some of them are probably simple, meaning that there is no accuracy- simplicity trade-off. But we do not know in advance how simple these models can get. For some applications, very sparse additive models or decision trees perform as well the best black box models; these datasets do not benefit from complex models at all. When does that happen? How extreme on the simplicity scale do we expect these models to go?
A key insight into this question comes from Semenova et al. [2023], who showed that the simplicity we can expect seems to be related the amount outcome noise in the data generation process, which we denote informally as "p." When is larger, we can get simpler models with performance comparable the best models. However, while Semeenva al. (0033 showed that noise levels are important, they did not provide a quantitative relationship between noise and simplicity.
In this work, ask question that allows us to better understand the connections among noise in the data generation processes, model simplicity, and the Rashomon Effect. The question is as
These authors contributed equally to this work. The names are listed in alphabetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Given the noise level p. how much simpler can our ML models get compared to the non-noisy case while still maintaining similar generalization performance? SSemenoaa et al. [2023) proves only that the hypothesis space could be simplified in the presence of noise, but does not discuss how much.
follows:
To answer this question, we formally prove for two common hypothesis spaces that noise is an im- plicit regularizer, thus leading simpler models. We quantify how much regularization added to models as a precise function of the amount of noise, for several types of noise and regularization. Table D summarizes the main results of this paper. For various combinations of hypothesis spaces, losses, and types of noise, we show that if we have regularization À and noise p. the optimization problem on noisy data is equivalent to optimizing over the cleaner data with stronger regularization (described in the rightmost column). This means that if we have noisy data, we get simpler model than if the data were cleaner and we had performed the same optimization.
Since the Rashomon Effect seems to be an important mechanism to understand simplicity, we also is the set of models that have comparable performance to the best models within a class. In this work, we show that, in the presence of noise, the Rashomon set tends consist of simpler models than in the non-noisy setting. This means that if user is look- ing for a model in the Rashomon set that obeys specific constraints (e.g., fairness or monotonicity), these models will be simpler (and this task is likely be easier) in the presence of noise.
study how noise affects it. The Rashomon
We also study how noise changes the relationship between features and outcomes in an unregularized setting. Specifically, we show that, for decision trees, the number of "good features" (having high AUC relative to other features) increases with noise, and the set of models that use at least one good feature grows larger. Since most models in the Rashomon set the Rashomon set of the unregularized hypothesis space might also increase size with increased noise. This attempts shed more light on the results that previous work [Semenova et al., 2023 only observed empirically.
least good feature,
We confirm our results empirically and provide practical guidance for the datasets from domains of criminal justice and lending, where we expect outcome noise due to the random nature of the data generation process. We hope that our results are the initial steps that will help machine learning practitioners, and possibly policymakers, to reason about the simplicity of models they can expect encounter for many high-stakes decision domains.
Table 1: Summary of paper contributions and answers to the key question.
Complex hypothesis space/model Loss Any model optimized on regular- ized 0-1 loss (e.g. sparse deci- sion trees with leaf penalty, rule lists with length penalty, scoring systems with sparsity penalty) with regularization penalty À
Noise, P Random label noise
Effective regularization
Misclassifi- cation error
Model optimized with regulariza- tion penalty I-2p
A
2
Linear models
Exponential loss
Additive attribute noise
Linear models that minimize log- arithm of exponential loss with & regularization, where jp² is the regularization parameter
2
Related Work
There are several bodies of related literature.
Rashomon sets. The Rashomon set the set of all near-optimal models has been studied primar-
ily in the context of its usefulness for solving downstream problems. Examples include developing
stable measures of variable importance [Donnelly al. 2023 Dong and Rudin 2020 Fisher al.
2019
Smith et al. 2020]. quantifying predictive multipiccty Marx et al. 2020 Hsu and Calmon
2022
Watson-Daniels et al. 2023], and understanding fairness [Aīvodji et al.) 2021 Coston al,
2021
Shamsabadi et al. 2022]. There are also algorithms for computing complete or approximate
Rashomon sets for a variety of hypothesis spaces [Mata et al., 2022 Xin et al. 2022 Zhong et al.,
2023 The most related prior work to this paper is the work of SSmenove et al. [2022 and Semen-
ova et al. [0023. which together demonstrate the existence of large Rashomon sets, and therefore simple models, when there is significant amount of randomness in the data generation process. In

---

comparison to prior work, ours is the first to provide a quantitative relationship between noise levels and quantities related to simplicity such as regularization and the contents of the Rashomon set.
Policy and interpretable MI., With new regulations including "right to explanation." " users can request an explanation if an automated decision has been made about them. However, such explana- tions are often post-hoc and may be misleading [Rudin et al. 2022, Rudin 2019 Han et al. 2022,
Adebayo et al. 2018 contradictory (Krishna et al. 2022 incomplete [Rudin| 2019 or failing in adversarial contexts Bordt et al. 2022 Interpretable models do not have these problems, and em- pirically, interpretable models high-stakes decision domains tend be as accurate as black-box models; this has been shown in lending [e.g.. Chen et al., 2022). criminal justice [e.g.. Angellnno al., [017]] and healthcare [e.g., ZZu et al., [023 However, policy makers still permit black boxes for high-stakes domains, possibly based on accuracy-simplicte trade-off concerns. Thus, more evi- dence about when this trade-off does and does not exist will be helpful.
Noise and regularization. The influence of noise on regularization has been studied for the hy- pothesis space of neural networks, though no prior work is directly relevant to our aims. [Bihhop [1995] showed that injecting a small amount of random attribute noise into the training data for a neural network was equivalent in the infinite data limit a form of Tikhonov regularization on the magnitude of weights. Dhifallah and Lu [021] extended these results to arbitrary noise for random feature models, which are restricted class of neural networks. These papers supplement work de- signing loss functions robust to noisy data for training neural networks [Wang et al. [2019] Ma et al.) 2020 Jin et al. 202T Zhou et al., 2023 and greedily-grown decision trees [Wilton and Yel 2024]. Here, we study the effect of noise on the regularization of sparse models based on ()- loss, such as sparse decision trees [Lin et al., 2020). and on linear models trained under exponential loss.
Noise and SGD. There has also been recent work focused on analyzing the behavior of the stochastic gradient descent (SGD) algorithm in the presence of artificially injected noise during the training
process. More specifically, HaoChen et al. [202T] found that applying label noise at each step of
be approximated arbitrarily well, while Gaussian parameter noise may instead lead to poor generalization. Blanc et al. (2020) showed that SGD with label noise acts as an implicit regularizer for models with training error. Damian et al. 2 and Vivien et al. [2022] generalize this result by showing that SGD implicitly optimizes a regularized objective function under various regimes. Our work instead focuses on noisy data generation processes, independent of the algorithm used to optimize the objective.
SGD allows the ground truth function of a data distribution
3 Definitions and Notation
Consider a dataset S (2+ = (I,, y)) where each 2; E 2 X x y is drawn ii.d. from an unknown true distribution D. Here, X E Ruxp is the input space, and y E {-1,1)" is the output space. Let F be hypothesis space, where f F is model mapping inputs to outputs, f X - y. Define o : ) x y + R as a loss function. For the misclassification error or 0-1 loss, have (()())))
[(()))))) The true risk Lf(f) is the expected loss over the true distribution D, given by [f) = (d))( v),, and the empirical risk (f( is the average loss on the dataset S drawn from D, calculated as (f) = J E._ ((f()))))). We denote by R(f) an arbitrary regularization term with regularization parameter À E RR. Regularization induces simplicity in this work; for example, R(.) can represent the number of leaves in a decision tree, the length of rule list, or fo. L1, or l norms. We are interested in learning model fö that minimizes the true objective Objo(f) that combines risk and regularization:
Objo(S) ID(s) + AR(J),
where fbb arg minjer (f) Since this model depends on an unknown distribution D, we estimate it using the empirical risk minimizer fs. defined as: fs E argminser Objs(f), where Objs(f) -s(() + AR()).
Following Fisher et al. 2211 Semenova et al. [2022 2023 Rashomon set Rootp (F, F.0) to be
Xin et al. [2022). we define the true
Racto (F,0) = (f F Ofjo(f) z Objo(ft) + 0].
(2)
that is, if T.D(J) + AR(S) S I.D({b) + AR(S3) + 0, the model f is included in the Rashomon
set. 0 2 0 is the additive Rashomon parameter defined by the user. Similarly, the empirical
3

---

Rashomon set Riets (F,0), contains models within & of the regularized empirical risk minimizer: Riess ( (bjs(s)
Objs(fs) + 0). Past work has shown that the true and em- pirical Rashomon sets may be similar (Semenova et al. 2022 Donnelly et al. 2023 We will omit "true" or "empirical" and use only "Rashomon set" when it is not significant over which distribution the set is computed.
We will model noise in the labels of data with uniform label noise model, where each label is flipped independently with the fixed probability, p E (0, 2)- To sample data with random label noise from the distribution D, we sample = (z, v) ~ DD then with probability p we change the label of y. We denote the noisy version of this data distribution as D,, By this definition, for x, y D, with probability of y = 1|r denoted as Py. when sampling from Dp, we have Py (1 (1-112)) 2p) + P [Semenova denote Sp to be dataset sampled according to distribution Dpp- Let Dr be the distribution of datasets Sp under this noise model. As shorthand notation, define Es, mean ES,-Dy We assume that in practice receive noisy data Sp and not cleaner data S. (Here, S does not have the uniform random label noise, but it is not necessarily clean in other ways.)
eet al. 2023]. For finite dataset,
In this work, we measure how noise impacts the simplicity of the best model in the hypothesis space as well as the models in the Rashomon set. First, in Section we consider random label noise and 0-1 loss, and then examine additive attribute noise for the exponential loss in Section [6] For both of these cases, we show that with more noise, we can expect simpler models.
4 Random Label Noise and Regularized 0-1 Loss
Noisy labels are common real-world datasets, especially in high-stakes decision domains. There are many sources of this noise, including subjective judgments, typographical and clerical errors, and systematic biases. Next, we show that when there is noise in the labels, the regularization of the optimal model is implicitly stronger.
4.1 Noise Increases Regularization
We study the effect of random label noise on the optimal models for 0-1 misclassification loss. We first show that optimizing over the noisy data distribution is equivalent to optimizing over the cleaner data distribution with stronger regularization. Formally:
Theorem 1 (Regularized 0-1 loss under random label noise). Consider true data distribution D, and uniform label noise with noise parameter E 1/2. Let D, denote the noisy version of D. Consider 0-1 loss L and let R. : F + IR be a regularization function with X E R+ regularization parameter. Formally,
JEF arg min I.D, (f) + XR()) = arg min [.D[J) + 1- R()). JEF
Similarly, given a dataset sampled according to D. and S, the noisy version of S, arg migminges Es, (s, + AR(f) = argmineer Ls(f) + 1-2p 22 R(f).
Theorem D applies to any model class and any regularization function over the models in the model class. This includes model classes such sparse decision trees, which regularize the number of leaves [Lin et al. 2020). rule lists, which regularize the number of rules [Angelino et al., 201](217). and scoring systems, which regularize the fo-norm of the parameter vector [Ustun and Rudin [0166]. We prove Theorem
[ in Appendix A This result proves the first row of Table [ as each of these hypothesis spaces optimize 0-1 loss with hypothesis-space--peeiii regularization function.
A consequence of Theorem [ intuitively, is that the optimal model with a higher regularization penalty should be simpler and fit the original data less precisely. Formally.
Theorem (Optimal model simplifies under random label noise). Under the same assumptions as T. let I be the optimal model in F over distribution 'D and let fo, be the optimal model
in Theorem in F over D p- Then either R(fb,) R(fB) and LD(fō,) LD(ff) (same complexity model) or R(Sb,) < R(f)) and LD(JE,) > ID( (strictly simpler model).
An identical result applies for finiee data when fš, is optimized over the loss function Es, Ls, (f).
proof of Theorem 2 is Appendix B. Corollary 10 Appendix gives a bound for how much simpler the noisy optimal model will be, based on its performance on the cleaner training data.

---

4.2 Noise Simplifies the Rashomon Set
In the previous section, we considered optimizing for one model, namely the best-perforning model in the class. However, the Rashomon set of models provides a lot of benefits, including deeper insights into the data, flexibility in model selection by choosing a more fair, robust model or model that obeys better domain constraints, and quantification of prediction uncertainty over this set of well-performing models (Rudin et al. 2024]. Therefore, we further study how label noise influences the complexity of the models in the true Rashomon set. More specifically, we show that the models in the true Rashomon set arising from noisy distribution cannot be more complex than those in the Rashomon set for the corresponding cleaner distribution.
Consider two true Rashomon sets Ruer (F,0) and ReeD,, (F, 0) over cleaner data distribution D and noisier data distribution Dp. We may partition these two sets of models into three disjoint sets: Fboth = {f E F f E Roet (F,0) 0) ReCDD (F,0)} (the set of models in both the cleaner and noisier Rashomon sets), Fout = {f E f RsetD (F, 0) Ryeto, (F, (the set of models in the Rashomon set over the cleaner data distribution, but not the noisy one), and F.. {s F e Ryep, (F, 0) Ri (F, 0)} (the set of models in the Rashomon set over the noisy data distribution, but not the cleaner one).
We interested in studying the relationship between the complexity of models in Rashomon sets over cleaner and noisy data. In this direction, we show that under mild assumptions, any models that are in the Rashomon set over the noisier data distribution, but not the cleaner one (Fin), will be simpler than the optimal model over the cleaner data. Since models in Footh have the same complexity in both Rashomon sets, and models in Fout tend to be complex (see Theorem IT in Appendix C). this result shows that the Rashomon set over noisy data will tend to contain lower complexity models than the Rashomon set over cleaner data. Formally,
Theorem 3 (Models that enter the noisier true Rashomon set are simple). Consider true data dis- tribution D, 0-1 loss function, regularization R(-) and regularization parameter X. Consider also uniform label noise, where each label is flipped independently with probability p (0, 2). Let Dr be the noisier data distribution. If Objp, (ft) > Objp, (fD,) 2p8, i.e., the optimal model over the cleaner data distribution is not in the Rashomon set of the noisy distribution with Rashomon parameter 2p0, then every model from F in the noisier true Rashomon set Rict, (F,0) is simpler than fB:
VFEF : < R(Fo).
where More specifically, BC)) < ((55) ( -). where A = Objo, -fb (Fb,)) Note that
A 0. An identical result applies for finite data when models are optimized over Es, Lss,())
2p
The proof of Theorem 3 is Appendix C Note that we showed in the previous section that an optimal model over the noisier data distribution tends to be simpler than an optimal model of the cleaner data distribution, R(fb,) < R(ft). Therefore, we believe the assumption that fō is not in the noisier true Rashomon set with the Rashomon parameter 2p0 is plausible in practical noisy settings. For smaller amounts of noise, the cleaner and noisier Rashomon sets may be similar enough to violate the assumption in Theorem 3 in this case, we expect the two Rashomon sets to overlap a lot, leading to larger F both and similar model complexity between the Rashomon sets.
When the data is noisy, practitioners can expect to find simple-and-accurate models within the Rashomon sets for regularized 0-1 loss. We experimentally support our results in Sections 4. and for empirical datasets and the expected empirical Rashomon set in Section 7 and Appendix
Unregularized Decision Trees and the Set of Grounded Models
The Rashomon ratio measures the size of the Rashomon set relative to the size of the hypothesis space [Semenova et al. 2022 2023 Rudin et al. 2022). For regularized 0-1 loss, we demonstrated that random label noise is equivalent to an increase in the regularization parameter. A larger regular- ization parameter penalizes more complicated models and effectively shrinks the hypothesis space, which tends to increase the Rashomon ratio [Semenova et al. 2023) In turn, larger Rashomon ratios correspond to a higher probability of obtaining a desired (e.g., interpretable or simpler) model and correlate with the existence of
models [Semenova et al. 2022
5

---

However, what happens if there is no regularization in the first place and the hypothesis space does not change in size (for example, consider fully-grown decision trees without penalties on the number of leaves)? In this scenario, in the presence of noise, we show that practitioners can still expect to find simple models within the Rashomon set. However, the reason is not due to noise affecting regularization, but rather because noise makes the Rashomon set increase in size. We give theoretical evidence for this claim in Section where we show that the set of grounded models (as defined in Section (.2) grows with noise. This set usually contains the Rashomon set (see Appendix (.3]. We begin with an observation about features in our dataset: noise distorts signal in high-quality Teatures faster than in lower-quality features. This leads to an increase in the size of the set of (relatively) features, which we define formally next.
5.1 The Set of Good Features Increases under Noise
X x Y, let G {o denote the set of features, where each g3 [x..} is the jth column of the feature matrix X. Note that X can be continuous or binary. For every feature g. we can evaluate its quality based on how close it is the label vector Y according to a similarity function Ms(g) = .Mg. Y). Different metrics can be used as M(.) including area under the receiver operating characteristic (ROC) curve (AUC), normalized Hamming similarity (one minus the normalized Hamming distance, which is the normalized count of different element values between two binary vectors) if gj are binary (gj E (-1,13), and correlation if both the labels and the feature are continuous. Given (s) we define a set of good features as follows:
For dataset
Definition 4 (Set of good features). Assume tures G = {g = {z..D/=z. a feature quality metric Ms(g) and a parameter 7. Let و = arg max Ms(g). Then we define the set of good features G GM (), to be (9,79 = (g E 9: MMs(g) 2 (ls(9)-7}
given dataset S = X Y, of fea-
We can think of the set of good features similarly to the Rashomon set, where the former contains all relatively good features based on the quality metric, and the Rashomon set contains all relatively good models (combinations of features) with respect to risk.
Intuitively, we expect that datasets originating from less noisy data generation processes will have higher quality features. For example, there exists feature with a very high AUC, then the accu- racy of learned models utilizing this feature will also be high. In the presence of label noise, we can precisely calculate how the quality of each feature changes for specific cases, including unnormal- ized AUC (as demonstrated in Theorem below. proven in Appendix D) and normalized Hamming similarity with binary features (direct consequence of proof in Theorem [T]. For balanced dataset S, where the number of positive and negative samples are the same and equal to rz/2, we define the unnormalized AUC as (UCs(g) -² (g) (AUC between & and the label on S).
Theorem 5 (Unnormalized AUC for continuous features increases with label noise). Consider a balanced dataset S = X x Y, i.e. Pr(y =) Pr(y - 1). Let g Z..j be continuous feature with distinct values gو <... < g" Let AUCs(9) denote the unnormalized AUC value of on the labels Y. Consider uniform label noise, where each label is flipped independently with probability p 3.
Let Sp be a noisier datasel. Then for every feature g 9:
Es, (AUCs,
(1- 2p)
- C(p.n),
where C(p, n) = ( ( + p- 1) is constant for a given p and n.
An important corollary directly follows from Theorem 5 which states that under noise, good features with higher AUC lose signal faster than features with lower AUC.
Corollary 6. Under the same amount of uniform random label noise p. the expected unnormalized AUC of features with higher initial value decreases faster than the expected unnormalized AUC of features with lower initial value. For two two features 91, I2. if AUCs(9))) < AUCs(92) then
AUCs(91) Es, AUC (91) < AUCs( Es, AUC
The different rate of change of features with different values of AUC also means that under noise, the set of good features increases. Since the quality metric MEs,, (g) decreases with noise for a given feature g, this implies that in the noisier dataset there are more features with equivalently weak signals as compared to a cleaner dataset.

---

Corollary 7. Consider dataset S = XxX. Let {AUCs(9))) be in decreasing order and spaced by distances at most 6, meaning that S AUCs(g)) AUCs(gg+1) I for each j = I,....P 1. Assume that we apply uniform label noise with flip probabilities P1 and P2 to S to ((1-2p.) obtain Sp, and Spz and that (GEs, AUCS (9,7) < p. If P2 2 v(p1) = 2 (1 7+6(1 (1)))))))))))) noting that v(p1)= > pt, then the size of the set of features which are good expectation strictly larger with more noise,
Esp AUC (9,7)1 < Espp AUCs (9,7)1-
The proof of Corollary is in Appendix [ and more experimental results are in Appendix I.3 Note that Corollaries 6 and 7 apply as well the case of normalized Hamming similarity.
Interestingly, Corollary 7 provides one possible explanation for the existence of large Rashomon sets. If there are more features that can explain the labels serrooiimmtel--uullly-wwwar then multiple good models could be composed of these features, as we will discuss next.
5.2 The Fraction of Grounded Models Increases for Unregularized Decision Trees
Consider a dataset with binary features and a hypothesis space Fa of fully grown decision trees of depth d. For example, fully grown tree of depth has three (internal) nodes (root and two child nodes) and four leaves (two leaves for each child node). Let the set of grounded models (set of models that use good features), Heeto (Fa), consist of models that (1) use least one feature from the set of good features Gans (9.7), (2) use labels determined by majority vote of data in the leaves. Let Hratiog (Fa) be the fraction of such models in the hypothesis space, meaning that, similar to the Rashomon ratio, Hratsos (F2)
[Huets (Fa)l Often, the set of grounded models FFal
contains most of the Rashomon set, because the trees in the Rashomon set usually rely on least one feature with a strong relationship with the label (measured by AUC; see Appendix I.3).
Next, we formally show that the fraction of grounded models increases with more random label noise. We again use the set of good features discussed above, with features ordered by AUC values.
Theorem 8 (Fraction of grounded models increases when the set of good features increases). For dataset S = X x Y with binary feature matrix X E {-1,1]nxp, consider a hypothesis space F a of fully grown trees of depth d Consider uniform random label noise with noise parame- ter Let Homes, (Fa) denote the set of grounded models, based on the set of good features GES, AUCsp (G.7)- Under the assumptions of Corollary 7 on the set of good features, the fraction of grounded models increases with uniform random label noise. More formally, for p2 2 v(pi).
(Fa) < Hoerssyp
(Fa)) and HeatsoEs
(Fa) < Hratioo 02 (Fa)-
The proof of Theorem 8 in Appendix The key observation made in our proof of Theorem is that the set of grounded models increases in size as the set of good features grows. Since the set of grounded models typically contains the Rashomon set, this tends to increase the Rashomon ratio in unregularized hypothesis spaces. As reminder, larger Rashomon ratios are associated with the existence of hypothesis spaces as well, e.g., tree ensembles. So far we have considered 0-1 loss with random label noise. Unsurprisingly, we can expect simpler, more regularized, models for other losses and noise models as well. In particular, next demonstrate that additive attribute noise acts as an implicit regularizer for the hypothesis space of linear models optimized for exponential loss.
models. We expect the results of this section hold for other
6 Additive Attribute Noise and the Exponential Loss
It has been known since the 1990s that additive attribute noise to a dataset in the setting of ridge regression acts as an implicit regularizer (Bishop] 1995. Semenova et al., 2023). More specifically, adding noise ~ AO, I2I), where 0 is a zero vector and / is identity matrix, to every sample J; (and thus creating new sample x = x; + c) implicitly increases the l2 regularization pa- rameter from C to C' + o². Semenova et al. [0233 have also shown that using additive attribute noise increases the Rashomon ratio for ridge regression. However, this work does not address other continuous losses for classification. In this section, we prove that for exponential loss and binary
7

---

classification, additive attribute noise similarly functions implicit & regularization on the loga- rithm of the loss for an otherwise unregularized setting. We give an explicit characterization of the regularization parameter based the variance of the noise added.
Theorem (Exponential loss under additive attribute noise). Consider the dataset S and a hypoth- esis space F of linear models, F == (f w x,w E J. For given model f E F, consider the exponential loss Ls(f)= = - mww"s Let C, such that N I 1) (ar >> 0, I is identity matrix), be ii.d. noise vectors added to every sample: x, + Ef IiS (f) ) is the expected exponential loss under additive Gaussian noise, then
Ei
E, L (f) Ls( e w
where for simplicity we denote (g.....-~((00022) as E..
A proof of Theorem iss in Appendix Immediately from Theorem 9 we have that
argminjer E. Ls, (f) = argmin (1og (s(() + o² 11w122
In other words, additive noise introduces l regularization on the logarithm of the exponential loss. Furthermore, the &2 regularization parameter is explicitly given as o² This shows that additive attribute noise encourages linear models to become simpler when there is more noise present.
7 Experimental Results
We now present experimental results supporting the results in Section for uniform label noise and 0-1 loss and Section 6 for additive attribute noise and exponential loss. We give evidence for our finding that noise acts as an implicit regularizer and that the optimal model optimized over data with injected noise is simpler than the optimal model without additional noise. We focus our experiments in this section criminal recidivism and financial datasets to emphasize the applicability of our work to high-stakes domains with human data. Please see Appendix for additional experiments.
7.1 Sparse Decision Trees, 0-1 Loss, Random Label Noise.
We used the GOSDT-guesses algorithm by McTavvih over varying amounts of label noise (between 0.0 and 0.3). In order to correctly simulate the results in Theorem the experiment estimates the size of model optimized over the expectation over
[022 optimize sparse decision trees
Recidivism data
Credit default data
Souared Norm Rolevant weighes weights
10a
10:
10a
Leaves
10t
#
10%
10
1
0.0
0.2
0.0
0.1
0.3
Noise Level
Noise Level
0.0
0.2
0.4
Standard Deviation,
Actual
Broward COMPAS
Actual
German
Banknate Iranian GivaMesomaCradlt
Occupancy
Predicted
Predicted
GMSC
FICO
Amsterdam
NU
Australian
FICO
Austrollan
(a)
(b)
(c)
Figure I: (a), (b): For the hypothesis space of sparse decision trees and 0-1 loss, the number leaves in optimal models for several datasets decreases with increased label noise. The solid lines depict the observed number of leaves in an optimal model over noisy data. The dashed lines depict the number of leaves of the optimal model over the cleaner data with regularization T-2p (see Theorem
D. (c): For the hypothesis space of linear models and exponential loss, the sum of the squares of the weights corresponding to the continuous features decreases as additive noise with standard deviation is applied the dataset.

---

amsterdam
Complexity; 0,0011
Complexity: A: 0,0038
6.10
0.64
Accurocy
Count
5
Leat
Predicted
Accuracy
4,42
Count
Lear
Preliceed
5,00
Test
650
3ett
Trin
Noky Tan
Tib
5.0
60
57 Noise Leval
Noise Level
Noise Level
Noise Level
compas
Complexity; A: 0,0077
NIj Recidivism
Complexity; A: 0.0011
Actul
Accuracy
0.23
Count
Accuraty
0.65
Count
0000
Test
Actual #ooowess
0.75
Nakay
Train
0.00
Notay Trais
F3
Prsticies PLooves
Ncise Level
Ncise Level
Noise Level
Noise Level
Figure 2: Experimental results for Section on recidivism datasets. accuracy plots (left), blue accuracy on cleaner test data, orange accuracy on cleaner train data, and green is accuracy on noisy train data. In complexity plots, blue corresponds to leaves in optimal model over noisy data, orange optimal model over cleaner data with higher regularization as in Figure [ Green is the leaf upper bound from Corollary I0 Lambda is regularization parameter optimized via 5-fold CV.
noise draws of the loss (i.e., R(fš.). where f3, E arg min Es, L.s, AR(f)). This different from taking the expectation of the size of models optimized over data with only a single noise draw (Es, R()*), where f E arg min L.s,( (f) + XR(J))- To approximate optimization over ex- pected noise draws, we concatenated 250 noise draws into single dataset upon which to optimize decision tree. The full experimental design is presented in Appendix The results of this experiment are shown Figure [ These results demonstrate simplification in accordance with Theorem and the aligmment between models trained on cleaner data with varying regularization and models trained on noisy data with consistent regularization (Theorem
An interesting observation from these experiments is that as we increase the label noise parameter, the generalization gap between the accuracy on the cleaner train and test set tends to shrink and the test accuracy remains very stable (see Figures 2 6 7p. This is what would expect given Theorems T and 2 since optimizing over the expectation of noise increases the effective regularization in the cleaner problem.
7.2 Linear Models, Exponential Loss, Additive Attribute Noise
To show that additive attribute noise has a regularizing effect on linear models under the exponential loss, we computed the optimal models on datasets under different noise levels and compared their complexities, measured by the norm of the weights. For each dataset, we sampled 100 independent noise draws for 10 different noise levels with E [0.05, 0.5). For each noise draw, we computed the optimal linear model on the noisy dataset using gradient descent. In Figure [[c). we observe that, the noise level a increases, the complexity of the optimal model rapidly decreases. This corroborates the regularizing effect of noise demonstrated in Theorem 9
7.3 Empirical Evidence that Rashomon Sets Over Noisier Data Contain Simpler Models
In Figure we show empirical evidence that the complexity of the Rashomon set of sparse decision trees tends to decrease with the injection of label noise. Moreover, the more noise added to the dataset, the simpler the models in the Rashomon set become. We provide detailed descriptions of the experiments in this section in Appendix [
8 Limitations and Future Work
One limitation of our work is that the theoretical results in Section 4 apply to models optimized over the expected loss over the distribution possible noise draws with label-flip probability p. For larger sample sizes, we expect optimizing over the expectation of noise draws to behave similarly to optimizing over a single noise draw. However, for smaller sample sizes, the optimal model optimized over single noise draw may deviate from the optimal model over the expectation of noise draws.

---

1.0
1.0
0 0.0
0% noise
5 0.0
0%
0.6
In 1306)
0.6
(n-9c6)
0.4
1.0
0 0.00
20%
0 0.0
1.0%
8 0.6
(rem 1531
8 0.6
[n-919)
0.4-
5.0 0.6
@ 0.2
2 0.2
0.0
0.0
20% noie
13721
0.4
2
2 0.2
0.0
0.0
2 0.8
1.0
50% noise
0.8
1.0
50% nose (mm4117)
0.6
(re 1030)
0.6
044
2.
Leaves (all dotasets)
Leaves per (real-world dotasets)
(a)
(b)
Figure 3: A visual demonstration of the simplifying effect of noise on Rashomon sets. This shows a bar chart of the discrete probability distribution of the number of leaves among models in the Rashomon set. Results are shown aggregated in (a) for 23 real-world and synthetic datasets, and in (b), just real-world data, for 9 recidivism and finance datasets.
One possible future direction is bound the expected complexity of model optimized over single noise draw terms of sample size and the probability of flipping labels.
natural extension of our work adapt our results to other losses, like hinge loss and logistic loss. These results are not immediate, because in loss functions more complicated than 0-1 loss, the error considers distances the decision boundary. Focusing on specific hypothesis spaces rather than on particular choices of loss function (e.g., rule lists optimized on logistic loss, or GAMs optimized on exponential loss) can also help to produce more specific and possibly tighter results similar those as in S
We can also try to generalize to other noise models (i.e. random flipping noise the inputs, or constrained non-uniform noise in the outputs). Dropping the assumption of uniform random label noise needs other techniques as opposed to those that are used in Theorem [ as the optimization problems no longer equivalent. If there is non-uniform noise at least p, it can be decomposed into the non-uniform distribution plus p uniform label noise, and our results in Theorem [ can be applied. However, such decomposition is not always realistic as, for example, it is very likely that some features are not noisy.
Practical Guidance for High-Stakes Decision Domains
The fallacy of the premise of the movie Minority Report is that it is possible to predict with perfect accuracy whether someone will commit a crime in the future. In reality, predictions recidivism made ~2 3 years in advance, giving time for multitude of random interactions in the world to take place. This unpredictability leads, as we showed this paper, to inherent regularization, and provably simpler models than if noise were present. Rather than assuming that increased algorithmic sophistication types of data, it is more realistic assume that the distributions of data in the future generally similar to those in the present, and that our best ML methods already reach an approximate per- formance maximum for these types of data. This latter view clears the way for policy-makers to regulate the use of simpler models. Already the use of black box models has led to individuals being denied freedom based on typographical errors [Wexler 2017a b Rudin al., 2020 and patients being deceived about the value of expensive medical treatment options [Afnan et al. 2021
the future can potentially lead to improved accuracy using the same
Our findings underscore the critical importance of using simpler models for datasets affected by noise, thereby prioritizing model interpretability and transparency. We believe that this understand- ing can empower policymakers advocate for the use of simple, interpretable models, ensuring the trustworthy, accessible, and equitable deployment of Al systems in high-stakes decision domains.
10

---

Acknowledgments and Disclosure of Funding
We acknowledge funding from the Department of Energy under grant DE-SC0023194, the National Institutes of Health under grant 5R01-DA054994, and grant from Fujitsu.
References
Iranian Churn. UCI Machine Learning Repository, 2020. DOI: https://bbirrg//022443///33Z
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Michael Anis Mihdi Afnan, Cynthia Rudin, Vincent Conitzer, Julian Savulescu, Abhishek Mishra, Yanhe Liu, and Masoud Afnan. Ethical implementation of artificial intelligence to select embryos in in vitro fertilization. In AAAI/ACM Conference on Artificial Intelligence, Ethics and Society (AIES), 2021.
UIrich Aivodji, Hiromi Arai, Séhastien Gambs, and Satoshi Hara. Characterizing the risk of fair- washing. In Advances in Neural Information Processing Systems, volume 34, pages 14822- 14834, 2021.
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-444 2017.
Chris M Bishop. Training with noise is equivalent to Tikhonov regularization. Neural Computation, 7(1):108-116 116, 1995.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an pages 483-513. PMLR, 2020.
like process. In Conference on Learning Theory,
Marko Bohanec. Car Evaluation. http://ddoo.rr111.243333///
UCI Machine Learning Repository, 1997.
DOI:
Sebastian Bordt, Michèle Finck, Eric Raidl, and Ulrike von Luxburg. Post-hoc explanations fail to achieve their purpose in adversarial contexts. In Proceedings of the 2022 ACM Conference Fairness, Accountability, and Transparency, pages 891-905, 2022.
Leo Breiman. Statistical modeling: The two cultures (with comments and a rejoinder by the author).
Statistical Science, (6(3):199-231, 2001.
Luis Candanedo. Occupancy detection. http:://b...gg/1.22433/0C000
UCI Machine Learning Repository, 2016. DOI:
Chaofan Chen, Kangcheng Lin, Cynthia Rudin, Yaron Shaposhnik, Sijia Wang, and Tong Wang. A holistic approach to interpretability in financial lending: Models, visualizations, and summary- explanations. Decision Support Systems, 152: 122:1136 13647, 2022.
Amanda Coston, Ashesh Rambachan, and Alexandra Chouldechova. Characterizing fairness over the set of good models under selective labels. In International Conference on Machine Learning. pages 2155-2155. PMLR, 2021.
Will Cukierski Credit Fusion. Give me some credit, 2011. URL https://kaggle.com
competitions Beiians/Gvieeeeeee GiveMeeommCredit
Alex Damian, Tengyu Ma, and Jason D Lee. Label noise sgd provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 11:27449-27466 2021.
Oussama Dhifallah and Yue Lu. On the inherent regularization effects of noise injection during training. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Con- ference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages PMLR. 18-24 Jul 2021.

---

Jiayun Dong and Cynthia Rudin. Exploring the cloud of variable importance for the set of all good models. Nature Machine Intelligence, 2(12):810- 824, 2020.
Jon Donnelly, Srikar Katta, Cynthia Rudin, and Edward P Browne. The rashomon importance
distribution: Getting RID of unstable, single model-based variable importance. In shirty- Conference on Neural Information Processing Systems, 2023.
FICO. Explainable Machine Learning Challenge, 2018. URL MRLLittpp://commuiitty
com/
s/explainablee www.aaamaaaaaaaaeeeeeeee-e-eeeee Learniig--ennnn-----ee chalgeng
Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models are wrong, but many are useful: Learning variable's 's importance by studying an entire class of prediction models simultaneously. Journal of Machine Learning Research, 20(177):1-81, 2019.
Tessa Han, Suraj Srinivas, and Himabindu Lakkaraju. Which explanation should choose? a func- tion approximation perspective to characterizing post hoc explanations. Advances in Neural In- formation Processing Systems,3::525600 35:5256-5268, 2022.
Mengjing Hao. Welfnusee-dloo--usttome----- 2024. URL httppp//://dx doi.
0q5y- 3529
Jeff Z HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. In Conference on Learning Theory, pages 2315-2357. PMLR, 2021.
Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOI:
https://oii.rr// wtt.:/i..or/111.14..3.. 14..24432//CNCC7
Hsiang Hsu and Flavio Calmon. Rashomon capacity: A metric for predictive multiplicity in classifi- cation. In Advances Neural Information Processing Systems, volume 35, pages 28988-29000, 2022.
Lifeng Jin, Linfeng Song. Kun Xu, and Dong Yu. instance-adaptive training with noise-robust losses against noisy labels. In Francine Moens, Xuanjing Huang. Lucia Specia, and Scott Wen- tau Yih, editors, Proceedings of the 202 Conference on Empirical Methods in Natural Language Processing, pages 5647-5663, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
Satyapriya Krishna, Tessa Han, Alex Gu, Javin Pombra, Shahin Jabbari, Steven Wu, and Himabindu Lakkaraju. The disagreement problem in explainable machine learning: A practitioner's perspec- tive. arXiv preprint arXiv:2202.01602. 2022.
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 6150- 6160. PMLR, 2020.
Volker Lohweg. Banknote Authentication. https:/ddo..rr/11224443/31
UCI Machine Learning Repository, 2013. DOI:
Xingjun Ma. Hanxun Huang, Yisen Wang, Simone Romano, Sarah Erfani, and James Bailey. Nor- malized loss functions for deep learning with noisy labels. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6543-6553 PMLR, 13-18 Jul 2020.
Charles Marx, Flavio Calmon, and Berk Ustun. Predictive multiplicity in classification. In Interna- tional Conference on Machine Learning, pages 67744 PMLR, 2020.
Kota Mata, Kentaro Kanamori, and Hiroki Arimura. Computing the collection of good models for rule lists. arXiv preprint arXiv:2204. 1285, 2022.
Surya Mattu, Julia Angwin, Lauren Kirchner, and Jeff Larson. How We Analyzed the COMPAS Recidivism Algorithm, 2016. URL algorithm
12

---

Hayden McTavvih, Chudi Zhong, Reto Achermann, Ilias Karimalis. Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast Sparse Decision Tree Optimization via Reference Ensembles. Proceed- ings of the AAAI Conference on Artificial Intelligence, 36(9):9604 9613, June 2022.
Moros, Rita, and P Cortez. Bank Marketing. UCI Machine Learning Repository, 2012. DOI:
NIJ. NIJ's Recidivism Challenge Full Dataset Office of Justice Programs, 2011. URL https:
7/data. ojj.at...jp.........
maf5-u@nk//bbuut_dee Cea
Full-Datastt
Ross Quinlan. Statlog (Australian Credit Approval). UCI Machine Learning Repository, 2006. DOI: https//bbi.og/1122442///991
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1:206-215, May 2019.
Cynthia Rudin, Caroline Wang, and Beau Coker. The age of secrecy and unfairness in recidivism prediction. Harvard Data Science Review, 2(1), 1 2020.
Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. In- terpretable machine learning: Fundamental principles and 10 grand challenges. Staristics Surveys, 16:1-85, 2022.
Cynthia Rudin, Chudi Zhong, Lesia Semenova, Margo Seltzer, Ronald Parr, Jiachang Liu, Srikar Katta, Jon Donnelly, Harry Chen, and Zachery Boner. Amazing things come from having many good models. In Proceedings of the International Conference on Machine Learning (ICML), 2024.
Lesia Semenova, Cynthia Rudin, and Ronald Parr. On the existence of simpler machine learning models. In 2022 ACM Conference Fairness, Accountability, and Transparency, pages 1827- 1858, 2022.
Lesia Semenova, Harry Chen, Ronald Parr, and Cynthia Rudin. A path to simpler models starts with noise. Advances in Neural information Processing Systems, 36, 2023.
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 Neural Information Processing Systems, volume 35, pages 14170-14182, 2022.
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.
Nikolaj Tollenaar and Peter G.M. Heijden. Which method predicts recidivism best?: A comparison of statistical, machine learning and data mining predictive models. Journal the Royal Statistical Society Series (General), 176:565-584. 02 2013. doi: 10. (0.11111.1667-98X2222220000
Sebastian Tomezak. Polish Companies Bankruptcy. UCI Machine Learning Repository, 2016. DOI: http:///oo.org//0.2444//////
Berk Ustun and Cynthia Rudin. Supersparse linear integer models for optimized medical scoring systems. Machine Learning, (02(3)3499333) 391. March 2016.
Loucas Pillaud Vivien, Julien Reygner, and Nicolas Flammarion. Label noise (stochastic) gradient descent implicitly solves the lasso for quadratic parametrisation. In Conference on Learning Theory, pages 2127-2159. PMLR, 2022.
Caroline Wang, Bin Han, Bhrij Patel, and Cynthia Rudin. In Pursuit of Interpretable, Fair and Accurate Machine Learning for Criminal Recidivism Prediction. Journal of Quantitative Crimi- nology, 39(2):519-581 June 2023. ISSN 1573-7799, doi: 10. 10.1007774099400002200555544444 w. URL. 0 1007 ottp:///0..110700100000000000--0
https:
13

---

Tong Wang, Rudin Cynthia, Finale Doshi-Velez, Yimin Liu, Erica Klampfl, and Perry Mac- Neille. In-iill Coupon Recommendation, UCI Machine Learning Repository. 2020. DOI:
http://00...g/1122233335554
Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey, Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF international conference on computer vision, pages 922-330. 2019.
Jamelle Wanies, David C Parkes, and Berk Ustun. Predictive multiplicity in probabilistic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10306-10314, 2023.
Rebecca Wexler. Code of silence: How private companies hide flaws in the software that govern- ments use to decide who goes to prison and who gets out. Washington Monthly, June/July/August 2017a.
Rebecca Wexler. When a computer program keeps you in jail: How computers are harming criminal justice. New York Times, June 2017b.
Jonathan Wilton and Nan Ye. Robust loss functions for training decision trees with noisy labels. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15859-15867, 2024.
J. Wnek. МONK's Problems.
UCI
Machine
Learning Repository, 1992.
DOL:
WIlliam Wolberg. Breast Cancer Wisconsin (Original). UCI Machine Learning Repository, 1992.
DOI: http://doo.ogg/00244332//CC/2-
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-14084, 2022.
Chudi Zhong, Zhi Chen, Jiachang Liu, Margo Seltzer, and Cynthia Rudin. Exploring and interacting with the set of good sparse generalized additive models. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Xiong Zhou, Xianming Liu, Deming Zhai, Junjun Jiang, and Xiangyang Ji. Asymmetric loss func- tions for noisc-tolerant learning: Theory and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Chloe Qinyu Zhu, Muhang Tian, Lesia Semenova, Jiachang Liu, Jack Xu, Joseph Scarpa, and Cyn- thia Rudin. Fast and interpretable mortality risk scores for critical care patients. arXiv e-prints, pages arXiv-2311 2023.
14

---

A Proof of Theorem 1
Theorem [ (Regularized 0-1 Loss under Random Label Noise). Consider true data distribution DD, and uniform label noise with noise parameter p E (0, 1/2). Let D, denote the noisy version of Consider 0-1 loss and R: F - be a regularization, function with Rt regularization parameter. Formally,
À R(S).
arg min LD, (f) + XR(J) arg min [D(J) 1 2p
JEF
JEF
Similarly, given a dataset sampled according to D. and Sp the noisy version of S, arg menr Es, (f) + AR(f) = arg minser Ls(f) + 1-2p R(f)-
Proof. Recall that the true risk for 0-1 loss Lp(f) = -==(2,))~ Dll [[]+ = - Semenova et al. 2023) show that (f) = (1 (1-2p) 2p) + p. This is independent of regulariza- Tron, have
Ld,(f) + AR()) = (1 (D-)p)(((())>> XR()+ +
Since the minimization procedure is invariant to shifts and scales by constants, conclude
arg min (J) + XR()) = arg min (1 2p) + AR()) + lef
arg min 2p) + AR(f)
JCF
arg min (n) + 1- 2p R(f).
JEF
An identical argument applies to the finite data case, where we use the remark in the proof of Theorem of [Semenova et 2023
B Proof of Theorem 2
Theorem 2 (Optimal model simplifies under random label noise). Under the same assumptions as in Theorem let fo be the optimal model in F over distribution 'D and let J be the optimal model in F over Dp Then either R(ft,) =R(ft) and LD(fD.) = -D((ft) (same complexity model) or
R(fb,) < R(F)) and LD(fo,) > LD(ft) (strictly simpler model).
An identical result applies for finite data when fās optimized over the loss function IF Es, L.s,(1) (f).
Proof. Consider optimal models
fo E arg min feF (R())
A
B. E mig Lo(
R()).
(by Theorem 1
FEF
1 2p
Then, by definition,
LD(ft) + +R(($) S (MR())
and
À R(fb,) < LD( + LD(fb,) 1 - 2p
A R(f5).
1- 2p
This gives
A (((Fz) (((S)))((,))) s Lo(fo,) - LD(fb) < 1- 2p
À
( -R(b)))
(3)
15

---

Assume for contradiction that R(fb,) > R(f)) = R(fo) - R(fD.) < 0. Then
Lo(fØ, LD(5T) 2 (R(f5) -R(S3,)
To([D,) (DD(T)
R(F)) R(S5,) S
and
A
LD(fb,) - LD(fD) - 1 - 2p
(R(f)) - R(fo.)
LD(fb,) LD(f))
Σ 1 2p
R(f)) (((5))
Since A
I-2p ffr p 1.2 this is contradiction. Thus, R(fb,) S R(ft) which immediately
gives (D(f),) 2 (D(f)) The two cases in the lemma follow from An identical argument holds for the finite data case.
We now highlight an intermediate step in the proof Theorem which gives us an upper bound on the complexity of optimal model over noisy data distribution.
Corollary 10. Under the same assumptions in Theorem 2
1-2p 2p
R(fb,) S R(fb)
(LD(Fb,)-LD(C
X
This follows immediately from 3 As we expect, the same result holds for finite sample S and Sp sampled from distributions D and Dp-
Note that, for a fixed amount label noise, this bound depends only on the complexity of the optimal model over cleaner data, and the difference in loss the cleaner distribution between optimal models optimized over noisy and cleaner data. The amount of implicit simplification due noise depends on the degradation of generalization performance caused by noise. We plot this noting that the bound loosens as increases and the generalization
bound in Figures 2 6 and 7 difference remains constant.
C Proof of Theorem 3
Theorem (Models that enter the noisier true Rashomon set are simple). Consider true data dis- tribution D. 0-1 loss function, regularization R(-) and regularization parameter X. Consider also uniform label noise, where each label flipped independently with probability p E (0, 2). Let DD be the noisier data distribution. If Objp,, (ft) > Objo, (fD ) + 2p0, iee, the optimal model over the cleaner data distribution D is not in the Rashomon set of the noisy distribution with Rashomon parameter 2p0, then every model from in the noisier true Rashomon set Bieto, (F,0) 0) is simpler than fb:
VJ F RC) < R(F)).
More specifically, R()) < (((5)) 1 0). where A = Objo, Objo, (Fb,). Note that
2p 0. An identical result applies for finite data when models are optimized over Es, Ls, (f).
Proof. Consider f E Fin. Then we have that f & Ryerop (F,0). Rieto, (F,0), and therefore:
Ip(f) + x TD(55) + AR(F3) + +0,
(4)
LD, (f) + + & (fb.)) + AR(fb,)
(5)
Additionally, from Semenova et al.
2023 we have:
(D, (1 (D))
(6)
16

---

Thus we have:
Obj,,(53,) + (0= +R((JB))+
D 2DD + +
_ (1- (1-22))1 (1-2p))D(()) +
( 2p) (ID((3)+ AR(SF) + -AR(1)) + +
AR(F)
(1 (p)Objo(f$) (1 (1- + +p+ 2+22AR(f).
Therefore, we get that
RS) 1 2pd (20 pO (1-22))))))11-
Let's focus on the difference between two objectives:
Objo, - (1 Op) = Objo, (1 LD - (1 20)))p(RR
Objp, (fb,) (1 - LD p (1 - 2p)AR(f6) +p
B Objo, (fb.) LD, AR(SS) + (2PR((fS) +
Objd, Objo, (fb) + 2pAR(FD) +P 2pAR(55) + p- A,
where = =Obj,, Objo.bjj,... (fb,). Since by assumption fo &f Riev, (F, (F,2))). then A > 2p0
and 2p
-0> 0. Therefore in 7 have:
R(F) 1 2pd (2p8 - p+ (Obj,, (1- Obpp)bjjo(Fb)
2p (2p0- p 2pAR(ʃE) - -
-((3) 3 2p 0) < R(fb).
1 (D A -0)
An identical proof applies to the finite dataset S, where the model f is in the noisier ex- pected Rashomon set if Es, (s, + R() I Es, Ls, (TEs,) + R(JEs,). ), where JEs, E arg min Fs, i.s, (f) + R()))
Models in Fout complex. As the theorem above states, models in Fin in the noisy Rashomon set tend to be simpler. Now, we will show that the models in Fout in the cleaner Rashomon set complex models that potentially will overfit the noisier data. We illustrated this empirically in Section 7.3 and now prove it more formally in the next theorem.
Theorem 11 (Models that exit the cleaner true Rashomon set are complex). Consider true data distribation D. 0-1 loss function, regularization R(-) and regularization parameter X. Consider also uniform label noise, where each label is flipped independently with probability p 1.2 Let D be the noisier data distribution. If Objo (ft,) Objp(ft) + 2p0, i.e. the optimal model over noisy data distribution Dp is not in the cleaner true Rashomon set with Rashomon parameter 2p0 (note that this is symmetric assumption the assumption in Theorem 3. then every model from F out in the cleaner true Rashomon sel Reetp (F,0) is more complex than J'D,"
AA E Fout -RJ) > R(D,) + p)
Proof. Let ʃ E Fout. By the definition of Fout, we have
(fb,) + Objp, (f) (bb,,
17

---

and
Objo(f) - Objo(ft) +..
(9)
From
8 66 and by the definition of the objective, we have that,
-1-20 ( + > (1-20)Lo(fb)) +R(fE,) + 0,
and
(1 (0=2)))0i(()++2o)((() (1000000000000(00000------000000 (2NN()))
We use Equation
to substitute in (bjp(/D) + 0 for Objr(f) and obtain
(1 +)) 2pAR(f)
(1 (p)) 2p)R(fb,) +
We can rearrange this inequality to solve for the regularization R(f) the models that exit the cleaner true Rashomon set:
0 1 2p (Objo(fš,) Objo(ft)).
R()) R(fb,) + A 2p²
By assumption, Objo({b,) Objo 2p0 and, therefore we get that
R(f) R(fb,) ) + 1- 2p0 -Rfb,)) 2(1 p)8
2p1
D Proof of Theorem 5
For given continuous feature y with values n² .... Sd and of binary labels Y for each sample, the AUC of g is defined as the area under the ROC curve of g. where the ROC curve is plotted against the false positive rate (FPR) and true positive rate (TPR) of decision stump g- We can choose instead to plot the absolute number of negatively and positively classified camples, forming the uunormalized ROC curve of g. The resulting unnormalized AUC of g detined as the area under the unnormalized ROC curve of g. which can be written as
AUCs(g) = ntn AUCs(g),
where n and n are the number of positively and negatively labelled samples respectively. For more explicit notation in this section, we will use AUC(g, Y) to denote unnormalized AUC, where AUC(g, AUCs(g). If g has T distinct values, then the unnormalized AUC has closed-form:
T
AUC Y)
1
-,
(10)
1=++1
Intuitively, equation 10 counts the number of unit squares below the unnormalized ROC curve. We now recall and prove Theorem 5
Let = I..j be a continuous feature with distinct values g¹ <... < <g" Let AUCs(9) denote the unnormalized AUC value of g on the labels Y. Consider uniform label noise, where each label flppedd independently with probability < Let Sp be a noisier dataset. Then for every feature
Theorem Consider a balanced dataset S = x Le. Pr(y= =
g E G:
Es, (AUCs, (1 (0-2p)AUCs(0) C(p.n),
where = ( + is constant for given p and n.
18

---

Proof. Under the noise model, each label is flipped independently with probability P, where 1 -
then the probability that the label was not flipped. Using equation T0,
we can write
= Ep|AUC((, = Lp
Σ icj
1=
F [1;;=1A0==-1]
Σ Pr(Us = 1, U, = -1)
Σ( (1 y - 1,8, 1-- =-1
Pr(yi F ÿt. y) ū3)
-=1,,==1 Pr(y: = Dr Vj ú1)
+ 1,,-1 Pr(y) + Ut. Vo + ز/
1=11,1111 Pr(y: = D1 U1 + أز}ة
Dip(1= -p)_y==-..==-11 + (1 - p)3 --=
+
+ + y
p)
Consider each of the terms separately. We have that
nn/2)
U 1,g
Σ 1 11
since there are / positive and negative samples, so there are (n/²) unordered pairs of each. We also have by definition that
Σ An= = AUC Y),
and since there are (z)² unordered pairs of exactly one positive and one negative value, lastly have that
2 - AUC(g, Y). Σ 1 = (2)
Thus, putting it all together, we obtain the following for the unnormalized AUC:
Ey [) (1- Y) +)+ x² ((5) AUG(g,)) +2p(1 - p) 3/
2
=(1-20)AUC(e +2
n2
p(1 - p)
2 _
n
-1)
2
(11-2))AUC(, Y)+ + (
?
( + p p-
If the dataset is not balanced, then we can use identical proof to show that
Ey AUC 8) (1 (1- 2p) Y) C(p,nt ,n
where Cl,, n== -p(1 -p(1-2p)m + p(1 () 2 ).
19

---

E Proof of Corollary 7
Corollary 7 Consider dataset S = X x Y. Let (AUCs( be in decreasing order and spaced by distances at most 6, meaning that 0 S sU))( AUCs(gg+1) S for each j 1,.... - L. Assume that we apply uniform label noise with flip probabilities p1 and P2 to S to obtuin Sp1 and Sp2 and that |GEs,, AUCS. (9,7) < p. If p2 2 v(pi) = 2 7+6(1-2p1) noting that v(p1) > P1, then the size of the set of features which are good in expectation strictly larger with more noise,
=11-2p-)
GESR AUCsp (9,7)] < [GEsyy AUCs (9,7)1-
Proof. Note that the features I1.... 9p are decreasing order by their unnormalized AUC, since by the corollary statement, S AUCs( - AUCs(g)+1) & From Theorem we know that E S. AUCs, (g) = (1 - AUCs() + C(p,n);
where C(p.n) n) = ( + --1 1) is constant that depends only on p and n. Given that (1 2p)xr + C(p, n) nondecreasing with respect x E IR when S p < 0.5 is held constant, Ø1 remains the best feature under noise (i.e. has the highest unnormalized AUC value), and the feature ranking is maintained. Thus, the of good features is the set of features gj. where each gj satisfies the following:
Es, AUCs,(91) - Ass,AUSs (0:) ST
This is equivalent to
+ C(p.n) AUC
- (U))))) C(p,n) Sn
and
(1- (()) AUCs(gg)) 5%
(11)
For ease of notation let, 0, AUCC AUC (g))) Let be the size of the set of good features under noise level Pl, so that [G A 8p1
(g, 7) = k. Then, from (11) and the feature ranking,
we have that:
- 1p-21a)a1- S ... (1-
- 2p1 5 < (1 2p1)2=+11555 S ... S (1-2p))pp
(12)
To show that |GF A (9,^)) 2 k + 1, it suffices to show that gk+1 is in the set of good features under noise level p2. which equivalent to the statement
(1- - 2p )xx1) S %
Note that by the assumption of the corollary, for each = 1, ..... PP- 1, we have that
a j++1= aj = AUCs(g,) - AUCs( S
Then, from 11 and
12 we get
(1 2p1 Ja++1 = (1 - 2p1 )ak + (1 - 22p1 (ax+1 -xx) S + (1 - 20
which means that
a 1 5 γ
8.
2p1
If 02 v(1), then we have
7
- 1--22))x+1 S (1 - 2p2))
+ 8
1 2p1
$ (1 22(p)))
1 2p1 +
7
(1- (1
7(1 2p1)
1 1 2p1 +6)
2 8(1 2p1)
(13)
7(1 2p1)
1 11-2p1 2p1 +8)
7 + 8(1 2p1)
7(1 2p1)
+ 5(1 2p1)
7 5(1 2p1)
1 1- 2p1
7.
20

---

Therefore, we proved that (1 - -222)ox+> S 7 which means that | Esps A (9,7)) ++1
and consequently iGrs,, AUCs.. (9,7)] < GEgp2 1cCs (9,7) as claimed.
F Proof of Theorem 8
Theorem 8 (Empirical Rashomon ratio increases when the set of good features increases). For datusel S X Y with binary feature matrix X E [-1,1]=x,, consider hypothesis space Fa of fully grown trees of depth d. Consider uniform random label noise with noise parame- ter Let HAstEs (Fa) denote the set of grounded models, based on the set of good features GEs, AUCsp (9.7). Under the assumptions of Corollary 7 n the set of good features, the fraction of grounded models increases with uniform random label noise. More formally, for p2 2 v(pi),
Hartesp (Fa) Hooresp (Fa) and Hratiorsp, (Fa) Hratioespy (Fa)-
Proof. As in Proposition of Semenova et 2023 the hypothesis space of fully-grown trees of depth d contains
d II
F = 22
(P k + 1)
A=1
trees, where symmetric trees not included, meaning that split 0 is the left and is the right.
The trees in the set of grounded models must have at least good feature. Moreover, the labels in the set of grounded models are assigned to the trees based on the data, meaning that it contains
Haeetes
II (p k 1)2t- k=
had k + 1)2- (
k=1
trees, where bad PES,
= - |Grs, AUCs, (9,7)1- Therefore the fraction of grounded models is:
Haetes, (FR)
Il (p - 1 k 1) II == (1ris) had STA k + 1)2--1
H Hratioe 3p
(F2)
FP
2
(p K + 1)2
[1
d
bad
k + 1)2* -
1
22d
(p 1: + 1)2
- k 24-1
bad PEs,
II
-
22d
p k +1
k=1
For noise levels PI, P2 from Corollary
if P2 2 v(pi), then GG AUCs (9.7) <
[GEs, AUCs (G, and lptd badd
Therefore,
d
Hastes
(p - l + 1)20
bad (IEEs,,
| - k + 1)2
1==1
(p 1: 1)2a
II
bad (IPES
- k + 1)2
|Hantesp2 (Fa),
k=1
and
24-1
d II
| - 1:
Hratior 5p1
(F))
22d
k +
km
21

---

2
bad | - k + Pess,
II
Hratiorsp2
(Fr).
2
p p-k+1
k=1
Thus, with noise, the size of the set and fraction of grounded models increases.
G Proof of Theorem
Theorem 9 (Exponential loss under additive attribute noise). Consider the dataset S and hypoth- esis space F of linear models, F {f w x, E (R). For given model f E F, consider the
exponential loss Lg(J)= = Ei= v. x, Let 6, such that N(0 o² (a >> 0, I is identity matrix), be ii.d. noise vectors added to every sample: x4 = + If E. L (f) is the expected exponential loss under additive Gaussian noise, then
Eg Ls (f) Ls(f) e 1l
where for simplicity we denote E. (n as Ec.
Proof. We can write the following:
Eg Lis (w) =
Eg yew (m,t) (a,te)
i=1
Niw zi Eg (e==w
71 i=1
1
Blw" Eg -e
Fy(e-=" u
$]
Biw
1=1
= Ls(w) IEg 1=
From here, note that for any multivariate Gaussian random variable ~ [(,, 2) and matrix A, we have that Ad (Ap, AEA"). Repeated usage of this identity yields
Eg Ee " 9 EE ow E5 lw 1B) [-=] Eo
We can directly compute the latter term by integrating. For any k.
15
C d=²
kz
00
e ((o-k)+++p
dx
22T
600
- ka= dx
e
22TT
-00
If we set k: = - ||w||2: then we obtain the claim.
Note that there is immediate generalization of Theorem 9 when the standard deviation of noise applied is unequal across each feature. If feature j receives independent Gaussian noise with standard deviation oj. then
1 Σ
Eg (Sstoo)(w) (w) Ls(f) exp
2
We can observe that higher degree of noise of feature corresponds to greater degree of reg- ularization of the corresponding weight. particular, given feature not subject to additive Gaussian noise, then the weight corresponding to that feature is not regularized at all.
22

---

Data Name
# samples
#features
Processing notes
Amsterdam (Recidivism)
20000
9
Broward County (Recidivism)
1954
NU Recidivism Challenge
16264
15
Fill missing prison offenses with 'Unknown'
Australian Credit
640
15
Outliers in columns 'A13' and 'A14' removed
German Credit
1000
7
GiveMeSomeCredit
18040
7
Downsample to balance classes Downsample to balance classes
Polish Companies
1597
26
Iranian Churn
3150
8
Telco Churn
7032
12
Occupancy Detection
20560
26
Drop 'date' column entirely Downsample to balance classes
Bank- full
9042
Banknote Authentication
1372
4
COMPAS (Recidivism)
6907
13
Same as
Xin et al.
2022
Semenova et al.
2023
FICO (Credit)
10459
18
Same as
Xtn ct
2022
Semenova et
202.
monks1
169
12
Same as
Xin et
2022
Semenova
2023
monks2
124
12
Same as
Xin ct al.
2022
Semenova ct al.
2023
monks3
122
12
Same as
Xin et al.
2022
Semenova et al.
2023
Breast Cancer Wisconsin
699
11
Same as
Xin et al.
2022
Semenova et al.
2023
Car Evaluation
1728
16
Same Xin et al.
2022
Semenova
2023
bar
1913
Same as
Xin ct al.
2022
Semenova ct al.
202.5
bar7
1913
15
Same as
Xin ct al. 2022
Semenova ct al.
2023
Carryout Takeaway
2280
16
Same as
Xin ct al. 2022
Semenova ct al
2023
Coffee House
3816
16
Same as
Xin el al. 2022
Semenova el al.
2023
Restaurant 20
2653
16
Same as
Xin et
2022
Semenova et al.
2023
Table 2: Summary count statistics of all datasets after preprocessing
H Datasets
In Table 2. we provide the description of the datasets used this paper and pre-processing steps. one-hot encoded, and all continuous data was binned into one-hot binary encoding using thresholds determined by the GOSDT-guesses algorithm [McTavvish et al., 2022 All rows with missing values were removed from the datasets unless otherwise indicated in the processing notes. The GOSDT-gueesses algorithm was also used to perform feature selection. The dataset statistics presented in Table 2 reflect the data used in the experiments after all pre- processing, including feature selection. When necessary, we downsampled to balance classes to avoid trivial optimal sparse decision trees.
All categorical variables
I Additional Experiments
I.1 The Complexity of Models in the Expected Empirical Rashomon Set
We now present an experiment demonstrating the results of Section 4.2 where we showed that the complexity of models in the true Rashomon set tends to decrease with the injection of label noise. In the experimental setting, we may only observe samples from the true data distribution, and thus we only have access empirical Rashomon sets. To simulate the Rashomon set of models trained on the expected distribution of datasets under label noise, 150 noise draws were independently sampled then concatenated for every dataset to create a training set for sparse decision trees. We used multiplicative Rashomon parameter of 0.05 and regularization parameter of 0.02 throughout these experiments. Figure 3 shows how the discrete probability distribution of the number of leaves of models in the expected empirical Rashomon set skews simpler as noise is injected into the data. This result holds both for the aggregated number of leaves in all of our datasets (a), recidivism and credit default datasets (b), and in individual datasets, some of which are displayed in Figure
I.2 Model Simplification Under Expected Label Noise
0-1 Loss and Sparse Decision Trees We now discuss the set-up of the experiment conducted to review Theorems I [ This experiment was conducted with sparse optimal decision trees trained on a subset of the complete feature set, with continuous features binarized via the binning procedure of the GOSDT-guesses algorithm [McTavish et al. 2022 Throughout the experiment, we allowed a maximum depth of 5, which we did not find to a limiting factor. Each dataset is split into a training set and test set, where the training set consists of roughly 80% of the data. Before injecting
23

---

Data Name
License DANS
Citation
Amsterdam (Recidivism)
Tollenaar and Heijden
2013
Broward County (Recidivism)
Publicly Available Publicly Available CC BY 4.0 CC BY 4.0
Wang et al.
2023
NU Recidivism Challenge
ND 2011
Australian Credit
Quiilan 2006
German Credit
Hofmann
1994
GiveMeSomeCredit Kaggle Competition Rules
Credit Fusion
Polish Companies
CC BY
lomczak
2016
Iranian Churn
CC BY 4.0
01S
2020
Telco Churn
Publicly Available CC BY 4.0
11ao
2024
Occupancy Detection
Candanedo
2016
Bank- full
CC BY 4.0
Moros
Banknote Authentication
CC BY 4.0
Lohweg
2013
COMPAS (Recidivism)
Publicly Available
Mattu et al.
2016
FICO (Credit)
FICO
FCO
2018
monks1
CC 4.0
Wnek
T992
monks2
CC BY
Wnek
1992
monks3
CC BY 4.0
Wnek
1992
Breast Cancer Wisconsin
CC BY 4.0
Wolberg
1992
Car Evaluation
CC BY 4.0
Bohanec
1997
bar
CC BY 4.0
Wang et al.
2020
bar7
CC BY 4.0
Wang ct al. 2020
Carryout Takeaway
CC BY 4.0
Wang ct al 2020
Coffee House
CC BY 4.0
Wang et al. 2020
Restaurant 20 Table 3: Licensing and Data Source Information for all Datasets
CC 4.0
Wang al.
2020
any noise, the optimal value À of the regularization parameter for the GOSDT algorithm was chosen using 5-fold cross validation on the training set. Then, for 51 parameters for label noise linearly spaced between and 0.3, inclusive, we run the following procedure:
1. Sample 250 i.i.d. draws of random label noise with parameter
2. Stack of these draws of random label noise into a single dataset.
3. Find the optimal sparse decision tree on this new, concatenated dataset.
4. Report the accuracy of the tree on its noisy training set (green), on the original (cleaner) training set (orange), and on the held out test set (blue).
5. Report the number of leaves (blue) of the optimal model trained on the noisy concatenated dataset.
6. Separately find the optimal sparse decision tree over the original training set with regular- ization parameter X/(1 2p), and report the number of leaves in this model (orange).
7. Compute the upper bound from Corollary TO (green) based on the loss difference between the noisy optimal model and the baseline optimal model on the original data (difference in orange accuracy line from its initial value).
Complete results of these experiments for all datasets are shown in Figure and
Exponential Loss and Linear Models For the experiment corresponding to Theorem 9 we use simpler setup to demonstrate that additive noise has regularizing effect. We seek to optimize the exponential loss of given binary classification dataset over the set of linear models. To do this, we directly use gradient descent with the exponential loss. We optimize for 1000 epochs with an initial learning rate of 0.1 with the ADAM optimizer (Kingma and Ba 2015). We furthermore decrease the learning rate by factor of 0.3 if the exponential loss plateaus for over 50 epochs. Using this optimization procedure, our experiment is follows:
Sample 100 i.i.d. draws of additive Gaussian noise with standard deviation on all contin- uous features.
2. For each noisy draw, find the optimal linear model using the gradient descent procedure described above.
24

---

3. Report the sum of the squares of the weights of the optimal model corresponding to con- tinuous noisy features.
1.3 Empirical Evidence that the Set of Grounded Models Tend to Contain the Rashomon Set
Trees in the Rashomon set tend to rely on features with good signals; therefore, the set of grounded models tends to overlap significantly with the Rashomon set. We demonstrate this empirically based on 19 classification datasets in Table 4 To compute the set of good features, we used the AUC as a feature quality metric and set 7 to 0.05. To compute the Rashomon set, we considered the hypothesis space of sparse decision trees of depth 4 with a regularization parameter of 0.01. We used TreeFARMS and set the Rashomon parameter to 5%. For every tree in the Rashomon set, we verified whether it relies on least one feature from the set of good features. The results are reported in the fourth column of Table 4 At least 95% of trees in every Rashomon set contains at least one feature from the set of good features.
Data name
# of features
Size of the of good features
Percentage of trees in the Rashomon set, that rely on at least one feature from the set of good features
Carryout Takeaway
15
99.87% (18344/18368)
Amsterdam
8
100% (1153/1153)
Coffee House
15
100% (3483/3483)
Australian Credit
14
100% (6296/6296)
COMPAS
100% (19859/19859)
NIJ Recidivism
14
99.98% (112065/1 (2667))
Bank-full
6
99.90% (1003/1004)
FICO
100% (125809/1
Occupancy Detection
25
13
99.99% (205762/205791)
bar?
14
100% (3939/3939)
German Credit
95.21% (1807/1898)
Polish Companies
25
10
99.55% (2 21179372211555)
bar
15
100% (13950/13950)
GiveMeSomeCredit
6
99.68% (1247/1251)
Restaurant 20
15
99.81% % (112971/113189
BCW-hin
10
97.21 % (22552/23200)
Telco Churn
11
95.82% (11830/12346)
Broward
15
14
100% (4161 16/4181/111)
Iranian Churn
95. 16% (531/558)
Table 4: The set of grounded models is likely to contain the Rashomon set for various datasets.
1.4 Noise Distorts the Signal in Features and Increases the Size of the Set of Good Features
We now present an empirical demonstration of the effect of label noise on relative feature quality, which we measure as feature's is AUC with the labels (see Section 5.T). The uniformity assumption in our results in that section was designed to avoid situations where one feature is clearly more predictive than all of the others, which negates the effect of small amounts of label noise on the set of good features. Therefore, theoretical results by intentionally removing features that were clear outliers in predictive quality. We are left with a somewhat uniform distribution of cleaner-data AUC values in Figure With label noise, the distribution skews left as predicted - this indicates that the high-quality features degrade towards 0.5 AUC faster than low-quality features, as predicted in Theorem
designed our experiments to align with the assumptions in our
1.5 Computation Resources
We performed experiments on Duke University's ' Computer Science Department cluster. We re- quested 200GB of shared total memory, and one compute core per dataset (23 datasets) so that we could run the experiments for each dataset in parallel. It took up to 10 hours to compute the optimal models for all different noise levels and draws (Figures D. simplicity of models in the Rashomon set (Figures 3 For the experiments corresponding to Fig- ure TT. it took up to 3 hours per dataset to compute the optimal models for all different noise levels and draws.
6 and 2 hours to compute the
25

---

Clean labels; 15
15% label noise; [G]
27
AUC, clean
AUC.
15% label noise
25
KDE
25
KDE
20
20
Density
Density
15
10-
10-
0.5
0.6
0.7
0.8
0.5
0.6 0.7
0.8
AUC
Figure 4: Feature AUC distribution before (left; blue) and after (right; orange) injecting 15% label noise, aggregated across criminal recidivism and financial datasets with feature quality parameter y = 0.05 (total of 109 features). All features degrade towards 0.5 AUC when label noise is intro- duced, and better features tend to degrade faster. This increases the size of the set of features within y AUC of the best feature (green shaded regions) from 15 features with original (cleaner) labels to 27 features with noisy labels, which aligns with prediction in Corollary
0.88
0% noice
20.8
0% ralic
0.6
0.6
0.2
0.2
10% noses
20.8
10% nose
(n- (4)
(h-2171
30.4-
2a.
0.6-
(n-214)
20.6
(s-1571
3.44
2.4
202
g g02
0.0
0.0
1.0
1.0
2.88
300 naise
20.8
30% nalie
8.6
0.s
20.4
E.2-
per (amsterdami)
Recidivisnt
(a)
(b)
2% noise
20.8
rolse
(n-14)
10
20.8
0.6-
(n=28)
20.6
In-1690 1601
0.44
804
2.2
202
0.0
0.0
1.0
1o0
20.8
2006 noise
20.8
2016 noise
8.6
206
0.4
204
0.2
E02
1.0
1.0
20.8
50% noise
208
50% nolse Ini
(9-
10
Leaves per tree (GivetMesomerrest)
Leaves per free (monles2)
(c)
(d)
Figure 5: A selection of individual datasets from the findings in Figure 3 (a) is recidivism dataset collected from the city of Amsterdam. (b) is a recidivism dataset from the NIJ's Recidivism Chal- lenge. (c) is credit default dataset from a Kaggle competition. (d) synthetic dataset. Datasets were chosen to represent an array of domains, including real-world and synthetic data.
26

---

australian credit
Complexity; 0,0079
bankfull
Complexity; 0,0005
Actuai Ploaess
10.0
0.80
Count
Preditted #Loaves
Jesf UB
20.075
Count
8.5
Arhal Plawess Tredicted
0.75
0.0
925
0.75
0.55
Vekay
03
611
83
01
83
fico
Complexity: A: 0.0023
german credit
Complexity: A: 0,0077
0.725
0.22
Acco
07655
Count
aucavos
0.000
Poskted Laonss
Ist
Test
Actiol Pleaves Leavess
Train
Boky
0.90
Noby Tha
Noise Level
Noise Level
Noise Level
Noise Level
GiveMeeSoeerrddtt
Complexity; A: 0.0112
polish companies
Complexity: x: 0,0014
Adual Poavess
Accuraty
0.75
Count
200.:
Court
Altual Ploaess Predicted mLaoves Lest UB
0.75
Text Train
0.62
Noky Taan
Noky Th
010
0.2
00
0.2
2-1
5:1
122
Figure 6: Experimental results for Section 4 financial datasets. See experimental design in Ap-
pendix 1.2 for description each line.
27

---

Complexity; 0.0020
Complexity: 0.0008
0.75
Accurso
Count
Accurana
0.70
Count
0.82
Actual Ploanes
3.05
Teat
Astuel #acaves
0.63
64
0.3
01
63
23
06
2.3
0.3
Noise Level
Noise Level
Noise Level
Noise Level
bcw bin
Complexity; A: 0.0008
car evaluation
Complexity; A: 0.0020
0.90
0.7
22
0.85
Count
Count
2.5
Test Tral
Actusi P1 Plewues Predicted stenvee
0.23
Teet
Artual Plesvee
Thii
Precicted #Lasves
Nody Tain
Leal UB
Nady Ta
Loal UB
0.1 Noise Level
Noise Level
Noise Level
Noise Level
carryout takeaway
Complexity: 0,0020
coffee house
Complexity: 0,0032
Count 1
Actual Buaaess
kcouray
0.70
Leaf US
Predicted sLoswes
Accuracy
3.85
Count
5
Piecidas Loaves Loal UB
Actial
0.65
3.40
Nony
Melay
03
8.3 Level
03
Level
Noise Level
Noise
iranian churn
Complexity, X: 0.0017
monks1
Complexity: A: 0,0249
80
Count
Actual #LeevOs
Accurayy
Count
Leaf
0.75
Prockied ALzuns
Test
Test Train
Noby Tann
3.8
Noby Tha
Noise Level
Noise Level
Noise Level
Noise Level
monks2
Complexity; A: 0,0154
monks3
Complexity; x: 0.0300
Adual euaaris
0.35
3.2
Accurabt
Findctedd in mixeee
Count
Count
Artual Plessee Precicted #LAsves
0.75
0.73
Test
Loafiu
0.5
Falt
Train
Ro Trai
Noky Ta
50
U.L
0.
30
0.1
110
U.I.
U.
Level
occupancy_detection
occupancy detection
Complexity: 0,0005
restaurant
Complexity: 0.0094
*scuro
0.22
Count
Fredicted
Leaf
0.75
0.22
Count
3.2
Leaf
Achul mlwees
Fredicted
0.73
2.5
6.2
0.3
0.2
0.
0.1
6.2
03
0.1
0.2
Noise Level
Noise Level
Noise Level
Noise Level
telco, churn
Complexity; x: 0.0017
0.85
75
Count
Test
Actusl Wteauve Prolitial #icoess Leaf Us
Train
Noby Tain
Noise Level
Noise Level
Figure 7: Experimental results for Section on miscellancous datasets. See experimental design in Appendix 1.2 for description of each line.
28

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed throughout the work, and we provide limitation paragraph in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiscless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-teex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Appendices A give proofs for all theorems, with detailed assumptions in the statements theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Experimental designs are detailed in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
30

---

(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Code and data may be found in the supplemental materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
publicc/uides//Coeeesuaee http://oooeaaaaiisssooooooogogg. for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. cc/ wwwpccccppppppeeeeeeeeeeeeeeeeee
wttpc//pwp.pgggideee/e/e//eppeee http:/ggiiee/e/eeee Codeeeeee/oeSubmiimicc asi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
Experimental designs are detailed in Appendix !|
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
31

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
For experiments performed over multiple trials, error bars are described in the experimental design. Many of the experiments in this paper are performed by fitting model on the concatenated version of many independent noise draws performing this op- eration many times measure the error is prohibitively expensive. The error is sufficiently mitigated by sampling very large number of noise draws.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It OK to report I-sigma error bars, one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer:
[Yes]
Justification: We discuss pendix !
our compute time and resources in a separate subsection in Ap-
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
32

---

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics ott.gitttteeeeerrrr...ooo/oo//ia
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Section details the practical implications of our work for policy decisions.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
33

---

Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use open access datasets and cite the sources of all the datasets we used in the paper.
Guidelines:
The answer means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
wwwrswitthccde.oooo com datasets has
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
34

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "A87QEsmxBM", "reviewer": "Reviewer_aFkG", "summary": "This work uses Rashomen sets ($R_{set_D} (\\mathcal{F}, \\theta) = \\{ f \\in \\mathcal{F} : Obj_D(f) \\leq Obj_D(f^*_D) + \\theta\\}$) to understand how the complexity of the optimal classifier simplifies with random label noise and additive gaussian noise. They show that label noise has explicit and implicit regulatory effects. They contribute the following conclusions\n1. (Explicit) The optimal classifier for the Error (0-1 loss) + Reg with random label noise is equal to solving the same problem without label noise but scaling up the regularization term by 1/(1-2p) where p is the probability of flipping the label. \n     - As a result, the optimal classifier with random label noise achieves has higher Error and smaller Reg than without label noise. \n     - Any model in the Rashomen set under label noise and not in the Rashomen set without label noise has smaller Reg than optimal model without label noise. \n2. (Implicit) In the setting without Reg in Decision Trees. The \"predictability\" of a feature, measured by AUC, degrades with label noise at different rates. Good features with higher AUC lose signal faster than features with lower AUC. As a result, the set of \"best\" features increases and accordingly the set of \"good\" models also increases. \n3. (Implicit) In the setting of exponential loss in linear models with additive gaussian noise, there is an implicit L2 weight regularization.", "questions": "See above", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is clearly written and technically solid. Experiments conducted in linear models and decision trees substantiate that label noise does indeed regularize models consistent with theoretical claims.", "weaknesses": "- My main concern is the related works section, which I think is missing a large portion of work that has studied this problem. The current paragraph called \"Noise and Regularization\" section could delve more into previous theoretical works on the implicit regularization of label noise and gaussian noise, and discuss less about designing robust loss functions if space does not allow, since designing label-noise methods is less relevant to the paper. For example,\\\n[1] Loucas Pillaud-Vivien, Julien Reygner, Nicolas Flammarion. Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrization. 2022. \\\n[2] Jeff Z. HaoChen, Colin Wei, Jason D. Lee, Tengyu Ma. Shape Matters: Understanding the Implicit Bias of the Noise Covariance. 2020. \\\n[3] Alex Damian, Tengyu Ma, Jason D. Lee. Label Noise SGD Provably Prefers Flat Global Minimizers. 2021. \\\n\n- It also seems that the work largely extends upon a previous work Semenova et al. It may also be good to explicitly discuss what the additional contributions of the paper's theorems are on top of previous conclusions. such as Theorem 8 in Semenova.  \n\n- In Theorem 1 and 2, should there be some additional constraints on the regularization function? Such as nonnegative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We address the weaknesses point-by-point below.\n\n**W1: Related literature.** Thank you, we will definitely add more relevant literature on implicit regularization as we will gain an extra page of space if the paper gets accepted. We will cite suggested papers on noise's effect on stochastic gradient descent as well as others related to them. *While this prior work considers a specific algorithm (SGD), our analysis in Sections 3 and 6  is algorithm independent.* It instead connects noise and regularization. Results in Section 3 are general for any algorithm that optimizes 0-1 loss alongside any regularization function. And results in Section 6 hold for any algorithm that optimizes exponential loss with $\\ell_2$ regularization.\n\n**W2: Connection to work of Semenova from FaccT.** For *non-regularized* hypothesis spaces: Theorem 8 in the paper of Semenova et.al., 2022 says that the Rashomon set does not decrease in size with more noise. In our paper, we provide stronger results. We illustrate theoretically that for the non-regularized case, both the Rashomon set and the Rashomon ratio tend to increase with noise due to the increase of the size of the set of good features. This result is also stronger than the result in the paper of Semenova et.al., 2023 which observed an increase in sets and ratios only empirically. \n\nFor *regularized* hypothesis spaces: For the regularized case, we are different from both papers as we show how much regularization changes with noise. Additionally, in Theorem 3 we prove that the complexity of the models in the Rashomon set tends to decrease.\n\nWe communicated these differences in the Introduction and we will emphasize them more in the theorems framing text during revision.\n\n\n**W3: Non-negativity of the regularization function.**\nThank you for pointing this out. Indeed, in all our examples (such as decision trees and linear models) we considered non-negative regularization. However, Theorems 1 and 2 do not require a negative regularization function. We will point this out in the revised paper. \n\nThank you again for the review, we'd be happy to engage in the discussion regarding any points mentioned.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cLSY1vd7AW", "reviewer": "Reviewer_HAB8", "summary": "The paper explores the role of dataset noise in the possibility of training simpler models. They show that more noisy settings are more likely to contain simpler models due to an increase in the regularization factor for learning algorithms that employ regularization. In the same setting, they also show that the optimal model under noise is simpler (or at least, not more complex) than the clean data and that the Rashomon is likely to contain simpler models when there is noise in the data. The authors complete their discussion by showing similar trends even in the absence of regularization, by viewing it from the perspective of ‘good features’. All theoretical claims are supported by empirical evidence.", "questions": "Please see the weaknesses.", "limitations": "Please see the weaknesses.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well presented and most theoretical discussions were easy to follow, given of course the page limit of a conference paper. For a paper as theoretical as this, I'd recommend proof sketches in the main paper to allow a better reading experience. However, the authors do a good job of wading through the claims even without them.\n- The insights of the paper are highly motivating for the real-world applications of ML. Real-world data can be noisy, partly because of the noise in the data collection pipeline, but also partly because it is not possible to always predict certain events. As shown by the authors, the Rashomon set in such a world is more likely to contain simpler models, which is quite promising and creates better incentives to search for those simpler models.\n- Most theoretical claims in the paper are supported by experiments towards the end of the paper. While I did go through the theoretical claims to the best of my expertise, having the empirical evidence to support that the expected behaviour is indeed present in practice is always good.", "weaknesses": "- At certain points in the paper, the authors claim more than they actually show through their proofs. For example, Theorem 3 says that models that enter the Rashomon set under noise (F_in) are likely to be simpler than the optimal model. The authors use this theorem to claim that the Rashomon set under noise would tend to contain less complex models. However, just theorem 3 is not enough to make such a claim. What about the models that leave the Rashomon set, i.e., F_out? Were they complex models, which would support the authors' claims? Or were they simple models, in which case maybe there is no straightforward expectation of whether the overall set has become simpler or complex? Another example is Theorem 1, which the authors prove for the distribution-based Rashomon sets, and then claim that the same can be extended to empirical Rashmon sets. However, their proof relies on a relationship between loss under noisy data vs clean data that they borrow from Semenove et al. This relationship does not directly transfer to the empirical setting, where an additional expectation term across different datasets sampled from the distribution is introduced. While these small issues do not directly impact the overall message of the paper, I would highly recommend that the authors be extra careful with the language they use and the claims they make. Edit after rebuttal: Acknowledged.\n- The empirical results provided by the authors are very targeted towards only the final claims in their theoretical discussion. However, a more complete picture through the empirical results would have made the paper so much stronger. For instance, what are the accuracy scores for models with and without noise? How much does the accuracy suffer due to noise, and while the Rashomon sets do contain simpler models, do they still even have some predictive power left, or is it too noisy? What fractions of models belong to F_in, F_both, and F_out in practice? There are many other questions that I would have liked to have seen empirically. Although I do understand the choice to focus more on the theory, and this isn't a big weakness of the paper. Edit after rebuttal: The empirical results were present in the Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We appreciate your points and feedback.\n\n**W1. Theorem 3 conclusion**.\n\nThank you for pointing this out.\n\nWe expect $F_{out}$ to mostly contain more complex models, since more complex models are a \"closer\" fit (overfit) to the data and therefore perform worse when noise is injected. Our experimental results support this hypothesis for the distribution of model complexities (see Figure 2 and Figure 4 in the Appendix). We can also show theoretically that models in $F_{out}$ are more complex than the optimal model for the noisier data under similar assumptions as Theorem 3 (please see the global rebuttal response). We will include more explanation in the text around Theorem 3 about the complexity of models in $F_{out}$.\n\n\n\n\nFor Theorem 1, we will add the language to address the limitation of the empirical setting.\n\n**W2. Empirical results.**\n\nThank you for asking all these interesting questions! Please see answers to them below, which we believe can be inferred from Figures 4-7 in the Appendix. We will add more discussion of these points to the paper.\n\n\"How much does the accuracy suffer due to noise?\" -  The test accuracy usually remains relatively stable until a very destructive amount of noise (around 25\\% in most cases) is injected into the training set (please see Figures 5-7 in the appendix).\n\n\"While the Rashomon sets do contain simpler models,\ndo they still even have some predictive power left, or is it too noisy?\" - The test accuracy remains stable with a lower amount of noise (see Figures 5-7). Since Theorems 1 and 2 show equivalence of the noisy optimization problem to the clean problem with higher regularization, we expect that the optimal model should still have predictive power unless the noise is large enough to make the effective regularization dominate the misclassification error. The models in the Rashomon set are close in accuracy to the optimal model, so we expect them to also have predictive power.\n\n\"What fractions of models belong to $F_{in}$,\n$F_{both}$, and $F_{out}$ in practice?\" - One can infer an estimate of sizes of $F_{in}$,\n$F_{both}$, and $F_{out}$ from Figure 4 in the appendix by observing the shift in the distribution of model complexities in the Rashomon set to the left. Increases in bars correspond to $F_{in}$, decreases to $F_{out}$, and the rest to $F_{both}$. Behavior varies by dataset and noise level. To provide more specific numbers, for the COMPAS dataset with $\\rho = 0.2$,  $F_{in}$ contains approximately 502 models (average number of leaves over $F_{in}$ is 4.98), $F_{out}$ has 593 models (average number of leaves over $F_{out}$ is 6.46), and $F_{both}$ has 2230 models (average number of leaves over $F_{both}$ is 5.41) (The Rashomon parameter is set to 0.03, decision tree depth to 4 and sparsity regularization to 0.01).\n\n\nMuch of our empirical exploration is in the Appendix, due to space constraints. We will gladly expand on some empirical questions in the paper with an additional page if accepted.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ku59iNtRDV", "reviewer": "Reviewer_R9J1", "summary": "This work sets out to the study the effect learning with noise entails from the perspective of model complexity. This paper invokes formalism from Rashomon sets and derives theoretical results that show an equivalence between noise (in the form of labels flipped) and regularization and in particular show that models that are trained on noisy data are necessarily underperforming on original losses. The theory is then applied to decision trees and linear models.", "questions": "(1) Is there any intuition how this can be applied to mainstream regularization techniques like drop-out?\n(2) While the theory is developed for general regularization penalties, can something more specific be said for specific choices?\n(3) Can the Theorems be adopted to regularization schemes beyond those that involve a loss such as augmentation?", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "[+] A very important and open-ended problem is pursued, involving the essence behind generalization trade-offs in machine learning.\n\n[+] The theoretical results are very general with no assumptions made on the hypothesis class (Theorem 1)\n\n[+] The paper is well-written and very easily accessible to a large variety of audiences.", "weaknesses": "[-] Analysis is a bit limited to models where the trade-offs are already well-understood such as decision trees. \n\n[-] The theory seems to be focused on regularization where a penalty is involved only.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We address the questions point-by-point below.\n\n**W1. Limitations of analysis**.\nWe've been studying decision trees for over a decade and we are not convinced that the trade-off is, thus far, well understood. From our experience, often for tabular datasets, there exists a sparse model that performs as well as black boxes. We believe that this phenomenon requires further investigation into how sparse models we can actually find before spending a lot of engineering time and effort. Our work provides an answer to this question when data come from noisy data generation processes.\n\n\n**W2. The regularization function generalization**.\nYes, in this paper we consider explicit regularization in the classic sense as a function \nadded to the loss (see Tikhonov et.al., Solutions of ill-posed problems, 1977). Note that this technique encompasses an enormous number of methods. \nWe would need to know what explicit or implicit regularization method you have in mind to offer more detailed comments.\n\n**Q1. Can we apply results to drop-outs?**  Dropout is a modification to neural network training which has a regularizing effect, but is not an explicit regularizer. Our results apply to explicit regularization penalties added to the objective function. \n\nPlease note that in this paper, we mainly work with tabular datasets, where one does not usually benefit from using neural networks, so techniques like dropout do not apply. Tabular data are very common in real-world applications, especially in lending and criminal justice which we mainly considered in the paper.\n\n\nNote that for $\\ell_2$-regularized neural nets on image data, in an initial experiment, we observed a significant regularizing effect of label noise. Please see the global rebuttal response for details of this experiment.\n\n**Q2. More specific results for the regularization**. \nFor Theorems 1 and 2 we can use our results to understand specific hypothesis spaces, like decision trees with regularization on the number of leaves. The results in these theorems are tight with respect to the regularization function. For specific regularization functions and specific hypothesis spaces, it might be possible to get more measurable results on simplification (for example questions like how many leaves will the optimal tree have with 25\\% intrinsic noise). We are indeed working towards these kinds of results.\n\n\n**Q3. Can we generalize to augmentation?**\nIn the tabular domain with meaningful features, we do not know of many augmentation techniques except adding noise. From Sections 3 and 6, we know that our results will hold under such augmentation.\n\nThank you again for the review, we'd be happy to engage in the discussion regarding any points mentioned.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ok124kpBUm", "reviewer": "Reviewer_5HeG", "summary": "This paper explores the relationship between data noise and model simplicity across different hypothesis spaces, focusing on decision trees and linear models. The authors demonstrate that noise functions as an implicit regularizer for various noise models and show that Rashomon sets built from noisy data typically include simpler models than those from non-noisy data. Additionally, they reveal that noise broadens the set of \"good\" features and increases the number of models utilizing at least one good feature. This research offers theoretical assurances and practical insights for practitioners and policymakers on the likelihood of simple yet accurate machine learning models, based on understanding the noise levels in data generation processes.", "questions": "- How robust are your theoretical results to the assumption of uniform random label noise?\n- Do you have any preliminary insights (or hypotheses) about how your findings might generalize to other more complex models and datasets such as neural networks?", "limitations": "See weaknesses above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper delves deeply into the theoretical aspects of how noise influences model complexity, offering insights into the regularization effects of noise and its impact on the selection of simpler models in machine learning. This is interesting as it quantifies the effects of noise on model simplicity and expands the understanding of the Rashomon effect. Personally, I found the latter connection to be interesting in particular.\n\n- The theoretical results are robust and well-presented. The proofs are detailed and appear sound.", "weaknesses": "- The connection between regularization and noise is well established using plenty of prior work (as demonstrated by the paper as part of the related work section). I feel like the paper sometimes stresses this insight too much as a novel idea. While the more detailed exploration of the connection to Rashomon sets is interesting and appears to be novel, I would strongly encourage the authors to not blur the lines between what has been shown in prior work already and what their contribution is. In my opinion, it should focus on the Rashomon set connection more strongly.\n\n- The experimental section seems comparatively short and limited. Both the model types and datasets are very simple. For a more convincing evaluation, it would have been great to see a more comprehensive experimental panel. It seems to me that this claim of simpler models arising under noise would be especially interesting where the base models are already complex in nature (and not linear models or decision trees which can already be considered easily interpretable).\n\n- The paper relies on limiting assumptions, such as uniform random label noise, which may not always hold in real-world scenarios. Discussing these limitations more explicitly would help in understanding the boundaries of the applicability of the results in more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. We address the questions point-by-point below.\n\n**W1. Connection to the previous works.**\nTheorems 1 and 2 do show that noise acts as an implicit regularizer (similar to Bishop, Training with noise is equivalent to Tikhonov regularization, 1995; Dhifallah and Lu, On the inherent regularization effects of noise injection during training, 2021). However, Theorem 1 quantifies the exact relationship between noise and regularization $(\\lambda / (1-2p))$ for 0-1 loss. These results are *general to the regularization function and algorithm independent*. In comparison, there are a lot of works that depend on *using specific algorithms like SGD* and regularization functions such as the $\\ell_2$ norm. That is, our results depend on the noise in the data, not the noise imposed onto the algorithm, like the recent literature on neural network convergence. Also, our results apply to discrete hypothesis spaces like decision trees and rule lists which have not, to our knowledge, been addressed by prior works.\n\n\nWe will also cite more works on noise acting as an implicit regularizer in the related works and comment on our differences in the paper revision.\n\n\n**W2. Empirical results.**\nThe phenomenon described in the paper is exactly the reason why we do not need complex models on tabular datasets. The datasets we used represent a wide array of tabular data problems, including (but not limited to) criminal justice and lending decisions, boolean circuits, and survey results on restaurant attendance. These datasets were not picked for convenience. Our results aim to help explain why we are able to find well-performing simple models on most noisy tabular decision problems. By simple model we mean a very sparse model, like a decision tree with five to seven leaves, or a scoring system with 10-20 \ncomponents, while compared to the more complex models such as the decision tree of depth ten ($\\sim 1024$ leaves for binary, fully grown tree) or linear model with 100 components. In practice, such model size differences can be crucial for interpretability.\n\nAs an initial experiment to show simplification of more complex models, we evaluated a CNN trained on CIFAR-10 with clean vs. noisy labels. We found that training on noisy labels resulted in significantly more near-zero weights (see global response file for details).\n\n\n**W3. Noise model.**\nIn reality, many datasets contain a high level of label noise. Please note that our results do not preclude the original distribution from having some base (potentially non-uniform) noise. Our results apply when uniform label noise is added on top of some existing noise.\n\nTo show that our results hold for other losses and noise models, we also considered Gaussian feature noise for classification with exponential loss in Section 6, and we generalized this result to non-uniform Gaussian feature noise in Appendix G. Overall, we expect that the paper's results will hold for other label noise models. For example, please see Figure 1 in the global rebuttal response, where we considered a new noise model with different noise rates for different groups of the population. \nAs in the experiments in our paper, we found simpler optimal models under a form of non-uniform label noise. \n\nWe will emphasize more in the paper the potential of future work exploring other, more complicated noise models.\n\n\n\n**Q1. Robustness to noise models.**\nOur proof techniques for Theorems 1 and 2 are not easily generalizable to other noise models. This is because in the proof we rely on the equivalence of optimization problems, which holds under uniform label noise, but does not happen, for example, when noise can change marginal label distributions differently.\nHowever, we expect the empirical behavior of decision tree optimization under non-uniform random label noise to be similar to uniform random label noise. This is because, in regularized hypothesis spaces, noise (uniform or not) cannot add any useful signal to data that would require a complex model; it can only destroy signal and make it more difficult to distinguish the true decision boundary. Please see Figure 1 in the global rebuttal response for more empirical evidence.\n\n**Q2. Generalization to neural networks.**\nOur results hold for any hypothesis space optimized over regularized 0-1 loss. We expect our findings to generalize somewhat to more complex models like neural networks optimized on other loss functions (like mean squared error or cross-entropy) based on initial empirical evidence (please see global response file). For some non-rigorous intuition for neural networks: if you represent a neural network as an embedding layer followed by a linear classifier, then our results apply directly to label noise in the final embedding before classifications (which may be carried through from noise in the inputs in some non-uniform way). \nIn general, though, our work aims to discuss the likely existence of a simple and accurate interpretable model for tabular datasets. If such a model exists, this knowledge can help a practitioner (or policymaker) decide to search for a simple model instead of a complex neural network or tree ensemble, for example. For this reason, much of our work is focused on the simpler hypothesis spaces instead of on the more complex ones.\n\nThank you again for the review, we'd be happy to engage in the discussion regarding any points mentioned.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for the reviews. Below, we provide proof that models that exit the clean Rashomon set are complex and an initial experiment on neural networks under random label noise. In the response file, we also include empirical analysis for the mixed label noise model.

**Models in $F_{out}$ in Section 4 are complex.** In the setting of Section 4, we empirically verified that models that exit the Rashomon set are complex models that potentially will overfit the noisier data in Figure 4. Here, we show mathematically that models in $F_{out}$ tend to be more complex (have a higher regularization penalty) than the empirical risk minimizer over the noisier data in Theorem 1. 

**Theorem** (Models that exit the clean true Rashomon set are complex). Consider true data distribution $D$, 0-1 loss function, regularization $R(\cdot)$ and regularization parameter $\lambda$. Consider also uniform label noise, where each label is flipped independently with probability 
$\rho < \frac{1}{2}$. Let $D_{\rho}$ be the noisier data distribution. If the optimal model over noisy data distribution $D$ is not in the clean true Rashomon set with Rashomon parameter $2\rho\theta$, i.e., $f_{D_{\rho}}^* \not\in R_{set_{D}}(\mathcal{F},2\rho\theta)\subset R_{set_{D}}(\mathcal{F},\theta)$ (note that this is a symmetric assumption to the assumption in the Theorem 3 in the paper), then every model from $F_{out}$ that exits the clean true Rashomon set $R_{set_{D}}(\mathcal{F},\theta)$ is more complex than $f_{D_{\rho}}^*$:
$$\forall \tilde{f} \in F_{out}: R(\tilde{f}) > R(f_{D_{\rho}}^*) + 2(1-\rho)\frac{\theta}{\lambda}.$$

**Neural networks experiments.** To investigate the effect of random label noise, in the distributional sense explored in the paper, we trained a CNN, utilizing cross-entropy loss and $\ell_2$ regularization, on the CIFAR-10 dataset with and without noise. The noisy data was constructed by randomly sampling label noise 100 times and stacking these samples, as in the experiments in the paper. We only added noise to the training data - the test data is clean. The architecture had a total of 62006 trainable parameters - to measure simplicity, we counted the number of parameters less than 1e-5 (near-zero parameters). For the model trained on the clean data, we found 37958 near-zero parameters. The model trained on the stacked noisy data, in contrast, had 51614 near-zero parameters. Both networks had around 60\% test accuracy. This, empirically, is an example of the regularizing effect of label noise, even for neural networks trained on cross-entropy loss. We present this experiment as initial evidence that our results can apply to more complex hypothesis spaces and loss functions.

Meta-review: This paper studies the interaction between data set noise and model complexity, specifically in the context of decision trees and linear models. First, the papers proves for some particular settings that noise acts as an implicit regularizer and leads to simpler models. In addition, the paper shows that under noise, the set of near-optimal models consist of simpler models than in the non-noisy setting. In the unregularized setting, the paper studies the number of "good" features changes with noise. The results are then validated empirically.

Reviewers unanimously recommended this paper for acceptance. Reviewers have suggested that the paper should expand its discussion of related work (and make it more explicitly clear how this contribution differs from existing work), clarify and discuss the assumptions needed for the theorems, and incorporate more of the empirical results in the appendix into the main paper. We strongly encourage the authors to incorporate these revisions into the final version of the manuscript.
Decision: Accept (poster)