Using Noise to Infer Aspects of Simplicity Without Learning

Authors: zachery  boner
harry  chen
lesia  semenova
ronald  parr
cynthia  rudin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 02:50:19

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.

Main paper: 
 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 are 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 to 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, 2001] , which is the phenomenon that datasets often admit many different good models. Semenova et al. [2022] shows that when there are a lot of good models, some of them are probably simple, meaning that there is no accuracysimplicity 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 as 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 to the amount of outcome noise in the data generation process, which we denote informally as "ρ." When ρ is larger, we can get simpler models with performance comparable to the best models. However, while Semenova et al. [2023] showed that noise levels are important, they did not provide a quantitative relationship between noise and simplicity.In this work, we ask a 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 follows: Given the noise level ρ, how much simpler can our ML models get as compared to the non-noisy case while still maintaining similar generalization performance? Semenova et al. [2023] proves only that the hypothesis space could be simplified in the presence of noise, but does not discuss how much.To answer this question, we formally prove for two common hypothesis spaces that noise is an implicit regularizer, thus leading to simpler models. We quantify how much regularization is added to models as a precise function of the amount of noise, ρ, for several types of noise and regularization. Table 1 summarizes the main results of this paper. For various combinations of hypothesis spaces, losses, and types of noise, we show that if we start with regularization λ and inject ρ label noise, the optimization problem on noisy data is equivalent to optimizing over the clean data with stronger regularization (described in the rightmost column).Since the Rashomon Effect seems to be an important mechanism to understand simplicity, we also study how noise affects it. The Rashomon set 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 to consist of simpler models than in the non-noisy setting. This means that if a user is looking for a model in the Rashomon set that obeys specific constraints (e.g., fairness or monotonicity), it will likely also be simpler in the presence of noise.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 use at least one good feature, the Rashomon set of the unregularized hypothesis space might also increase in size with increased noise. This attempts to shed more light on the results that previous work [Semenova et al., 2023] only observed empirically.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 to encounter for many high-stakes decision domains. 2 Linear models Exponential lossLinear models that minimize logarithm of exponential loss with ℓ2 regularization, where 1 2 ρ 2 is the regularization parameter 
related work: 
 There are several bodies of related literature.Rashomon sets. The Rashomon set -the set of all near-optimal models -has been studied primarily in the context of its usefulness for solving downstream problems. Examples include developing stable measures of variable importance [Donnelly et al., 2023 , Dong and Rudin, 2020 , Fisher et al., 2019 , Smith et al., 2020] , quantifying predictive multiplicity [Marx et al., 2020 , Hsu and Calmon, 2022 , Watson-Daniels et al., 2023] , and understanding fairness [Aïvodji et al., 2021 , Coston et 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 Semenova et al. [2022] and Semenova et al. [2023] , which together demonstrate the existence of large Rashomon sets, and therefore simple models, when there is a 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 ML. With new regulations including "right to explanation," users can request an explanation if an automated decision has been made about them. However, such explanations 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 empirically, interpretable models in high-stakes decision domains tend to be as accurate as black-box models; this has been shown in lending [e.g., Chen et al., 2022] , criminal justice [e.g., Angelino et al., 2017], and healthcare [e.g., Zhu et al., 2023] . However, policy makers still permit black boxes for high-stakes domains, possibly based on accuracy-simplicity trade-off concerns. Thus, more evidence 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 hypothesis space of neural networks, though no prior work is directly relevant to our aims. Bishop [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 to a form of Tikhonov regularization on the magnitude of weights. Dhifallah and Lu [2021] extended these results to arbitrary noise for random feature models, which are a restricted class of neural networks. These works supplement a large body of work designing loss functions robust to noisy data for training neural networks [Wang et al., 2019 , Ma et al., 2020 , Jin et al., 2021 , Zhou et al., 2023] and greedily-grown decision trees [Wilton and Ye, 2024] . Here, we study the effect of noise on the regularization of sparse models based on 0-1 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. [2021] found that applying label noise at each step of SGD allows the ground truth function of a data distribution to 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. [2021] 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. 
definitions and notation: 
 Consider a dataset S = {z i = (x i , y i )} n i=1 , where each z i ∈ Z = X × Y is drawn i.i.d. from an unknown true distribution D. Here, X ∈ R n×p is the input space, and Y ∈ {-1, 1} n is the output space. Let F be a hypothesis space, where f ∈ F is a model mapping inputs to outputs, f : X → Y. Define ϕ : Y × Y → R + as a loss function. For the misclassification error or 0-1 loss, we have ϕ(f (x), y) = 1 [f (x)̸ =y] . The true risk L D (f ) is the expected loss over the true distribution D, given by L D (f ) = E z∼D [ϕ(f (x), y)], and the empirical risk LS (f ) is the average loss on the dataset S drawn from D, calculated as LS (f ) = 1 n n i=1 ϕ(f (x i ), y i ). We denote by R(f ) an arbitrary regularization term with regularization parameter λ ∈ R + . Regularization induces simplicity in this work; for example, R(•) can represent the number of leaves in a decision tree, the length of a rule list, or ℓ 0 , ℓ 1 , or ℓ 2 norms. We are interested in learning a model f * D that minimizes the true objective Obj D (f ) that combines risk and regularization:EQUATIONwhere f * D ∈ arg min f ∈F Obj D (f ). Since this model depends on an unknown distribution D, we estimate it using the empirical risk minimizer fS , defined as: fS ∈ arg min f ∈F Obj S (f ), where Obj S (f ) = LS (f ) + λR(f ).Following Fisher et al. [2019] , Semenova et al. [2022 Semenova et al. [ , 2023]] , Xin et al. [2022] , we define the true Rashomon set R set D (F, θ) to beEQUATIONthat is, ifL D (f ) + λR(f ) ≤ L D (f * D ) + λR(f * D )+ θ, the model f is included in the Rashomon set. θ ≥ 0 is the additive Rashomon parameter defined by the user. Similarly, the empirical Rashomon set Rset S (F, θ), contains models within θ of the regularized empirical risk minimizer:Rset S (F, θ) := {f ∈ F : Obj S (f ) ≤ Obj S ( fS ) + θ}. Past work has shown that the true and empirical 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 a uniform label noise model, where each label is flipped independently with the fixed probability ρ ∈ 0, 1 2 . To sample data with random label noise from the distribution D, we sample z = (x, y) ∼ D, then with probability ρ 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|x denoted as p y , when sampling from D ρ , we have p y (1 -2ρ) + ρ [Semenova et al., 2023] . For a finite dataset, we denote S ρ to be a dataset sampled according to distribution D ρ . Let D n ρ be the distribution of datasets S ρ under this noise model. As shorthand notation, define E Sρ to mean E Sρ∼D n ρ . 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 4, 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 in 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. 
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 clean 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 ρ ∈ (0, 1/2). Let D ρ denote the noisy version of D. Consider 0-1 loss L and let R : F → R be a regularization function with λ ∈ R + a regularization parameter. Formally,arg min f ∈F L Dρ (f ) + λR(f ) = arg min f ∈F L D (f ) + λ 1 -2ρ R(f ).Similarly, given a dataset S sampled according to D, and S ρ the noisy version of S,arg min f ∈F E Sρ LSρ (f ) + λR(f ) = arg min f ∈F LS (f ) + λ 1-2ρ R(f ).Theorem 1 applies to any model class and any regularization function over the models in the model class. This includes model classes such as sparse decision trees, which regularize the number of leaves [Lin et al., 2020] , rule lists, which regularize the number of rules [Angelino et al., 2017] , and scoring systems, which regularize the ℓ 0 -norm of the parameter vector [Ustun and Rudin, 2016] . We prove Theorem 1 in Appendix A. This result proves the first row of Table 1 , as each of these hypothesis spaces optimize 0-1 loss with a hypothesis-space-specific regularization function.A consequence of Theorem 1, intuitively, is that the optimal model with a higher regularization penalty should be simpler and fit the original data less precisely. Formally, Theorem 2 (Optimal model simplifies under random label noise). Under the same assumptions as in Theorem 1, let f * D be the optimal model in F over distribution D and let f * Dρ be the optimal model in F over D ρ . Then either R(f* Dρ ) = R(f * D ) and L D (f * Dρ ) = L D (f * D ) (same complexity model) or R(f * Dρ ) < R(f * D ) and L D (f * Dρ ) > L D (f * D ) (strictly simpler model).An identical result applies for finite data when f * Sρ is optimized over the loss function E Sρ LSρ (f ). A proof of Theorem 2 is in Appendix B. Corollary 10 in Appendix B gives a bound for how much simpler the noisy optimal model will be, based on its performance on the clean training data.In the previous section, we considered optimizing for one model, namely the best-performing 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 a noisy distribution cannot be more complex than those in the Rashomon set for the corresponding clean distribution.Consider two true Rashomon sets R set D (F, θ) and R set Dρ (F, θ) over clean data distribution D and noisier data distribution D ρ . We may partition these two sets of models into three disjoint sets:F both = {f ∈ F : f ∈ R set D (F, θ) ∩ R set Dρ (F, θ)} (the set of models in both the clean and noisier Rashomon sets),F out = {f ∈ F : f ∈ R set D (F, θ) \ R set Dρ (F, θ)} (the set of models which were in the Rashomon set before adding noise, but not after), andF in = {f ∈ F : f ∈ R set Dρ (F, θ) \ R set D (F, θ)} (the set of models which only entered the Rashomon set after the addition of noise).We are interested in studying the relationship between the complexity of models in Rashomon sets over clean and noisy data. In this direction, we show that under mild assumptions, any models that enter the Rashomon set after the injection of noise (F in ) will be simpler than the optimal model over the clean data. Since models in F both have the same complexity in both Rashomon sets, and models in F out are not relevant after the addition of noise (in fact, models in F out tend to be complex as we show in Theorem 11 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 clean data. Formally, Theorem 3 (Models that enter the noisier true Rashomon set are simple). Consider true data distribution D, 0-1 loss function, regularization R(•) and regularization parameter λ. Consider also uniform label noise, where each label is flipped independently with probability ρ ∈ (0, 1 2 ). Let D ρ be the noisier data distribution. If Obj Dρ (f * D ) > Obj Dρ (f * Dρ ) + 2ρθ, i.e., the optimal model over clean data distribution D is not in the Rashomon set over the noisy distribution with Rashomon parameter 2ρθ, then every model from F in that enters the noisier true Rashomon set R set Dρ (F, θ) is simpler than f * D :∀ f ∈ F in : R( f ) < R(f * D ). More specifically, R( f ) < R(f * D ) -1 λ ∆ 2ρ -θ , where ∆ = Obj Dρ (f * D ) -Obj Dρ (f * Dρ ). Note that ∆ 2ρ -θ > 0.An identical result applies for finite data when models are optimized over E Sρ LSρ (f ).The proof of Theorem 3 is in 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 clean data distribution, R(f * Dρ ) < R(f * D ). Therefore, we believe the assumption that f * D is not in the noisier true Rashomon set with the Rashomon parameter 2ρθ is plausible in practical noisy settings. For smaller amounts of noise, the clean 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. Thus, when the data is noisy, practitioners can expect to find simple-and-accurate models when they enumerate the Rashomon sets for regularized 0-1 loss.We experimentally support our results in Sections 4.1 and 4.2 for empirical datasets and the expected empirical Rashomon set in Section 7 and Appendix I. 
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 regularization 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 simpler-yet-accurate models [Semenova et al., 2022] .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 5.2, where we show that the set of grounded models (as defined in Section 5.2) grows with noise. This set usually contains the Rashomon set (see Appendix I.3). We begin with an observation about features in our dataset: noise distorts signal in high-quality features faster than in lower-quality features. This leads to an increase in the size of the set of (relatively) good features, which we define formally next.For a dataset S = X × Y , let G = {g j } p j=1 denote the set of features, where each g j = {x .,j } is the j th 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 to the label vector Y according to a similarity function M S (g) = M(g, 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 g j are binary (g j ∈ {-1, 1}), and correlation if both the labels and the feature are continuous. Given M S (g), we define a set of good features as follows:Definition 4 (Set of good features). Assume we are given a dataset S = X × Y , set of features G = {g j } p j=1 = {x .,j } p j=1 , a feature quality metric M S (g) and a parameter γ. Let ĝ := arg max g∈G M S (g). Then we define the set of good features G M S (G, γ) to beG M S (G, γ) := {g ∈ G : M S (g) ≥ M S (ĝ) -γ}.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, if there exists a feature with a very high AUC, then the accuracy 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 unnormalized AUC (as demonstrated in Theorem 5 below, proven in Appendix D) and normalized Hamming similarity with binary features (direct consequence of proof in Theorem 1). For a balanced dataset S, where the number of positive and negative samples are the same and equal to n/2, we define the unnormalized AUC as AU C S (g) = n 2 4 AU C S (g) (AUC between g and the label on S). Theorem 5 (Unnormalized AUC for continuous features increases with label noise). Consider a balanced dataset S = X × Y , i.e. Pr(y = 1) = Pr(y = -1). Let g = x .,j be a continuous feature with distinct values g 1 < . . . < g n . Let AU C S (g) denote the unnormalized AUC value of g on the labels Y . Consider uniform label noise, where each label is flipped independently with probability ρ < 1 2 . Let S ρ be a noisier dataset. Then for every feature g ∈ G:E Sρ [AU C Sρ (g)] = (1 -2ρ)AU C S (g) + C(ρ, n), where C(ρ, n) = ρ n 2 n 2 + ρ -1is constant for a given ρ 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 ρ, 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 features g1 , g 2 , if AU C S (g 1 ) < AU C S (g 2 ), then AU C S (g 1 ) -E Sρ AU C Sρ (g 1 ) < AU C S (g 2 ) -E Sρ AU C Sρ (g 2 ).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 M E Sρ 1 (g) decreases with noise for a given feature g, this implies that after adding noise there are more features with equivalently weak signals as compared to a cleaner dataset.Corollary 7. Consider a dataset S = X × Y . Let {AU C S (g j )} p j=1 be in decreasing order and spaced by distances at most δ, meaning that 0 ≤ AU C S (g j ) -AU C S (g j+1 ) ≤ δ for each j = 1, . . . , p -1. Assume that we apply uniform label noise with flip probabilities ρ 1 and ρ 2 to S to obtain S ρ1 and S ρ2 , and that|G E Sρ 1 AU C Sρ 1 (G, γ)| < p. If ρ 2 ≥ ν(ρ 1 ) := 1 2 1 -γ(1-2ρ1) γ+δ(1-2ρ1)noting that ν(ρ 1 ) > ρ 1 , then the size of the set of features which are good in expectation is strictly larger with more noise,|G E Sρ 1 AU C Sρ 1 (G, γ)| < |G E Sρ 2 AU C Sρ 2 (G, γ)|.The proof of Corollary 7 is in Appendix E and more experimental results are in Appendix I.3. Note that Corollaries 6 and 7 apply as well to 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 approximately-equally-well, then multiple good models could be composed of these features, as we will discuss next.Consider a dataset with binary features and a hypothesis space F d of fully grown decision trees of depth d. For example, a fully grown tree of depth 2 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), H set S (F d ), consist of models that (1) use at least one feature from the set of good features G set S (G, γ), (2) use labels determined by a majority vote of data in the leaves. Let H ratio S (F d ) be the fraction of such models in the hypothesis space, meaning that, similar to the Rashomon ratio,H ratio S (F d ) = |Hset S (F d )| | F d |. Often, the set of grounded models contains most of the Rashomon set, because the trees in the Rashomon set usually rely on at 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 a dataset S = X × Y with binary feature matrix X ∈ {-1, 1} n×p , consider a hypothesis space F d of fully grown trees of depth d. Consider uniform random label noise with noise parameter ρ. Let H set E Sρ (F d ) denote the set of grounded models, based on the set of good features G E Sρ AU C Sρ (G, γ). 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 ρ 2 ≥ ν(ρ 1 ),H set E Sρ 1 (F d ) < H set E Sρ 2 (F d ) and H ratio E Sρ 1 (F d ) < H ratio E Sρ 2 (F d ).The proof of Theorem 8 is in Appendix F. The key observation made in our proof of Theorem 8 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 a reminder, larger Rashomon ratios are associated with the existence of simpler-yet-accurate models. We expect the results of this section to hold for other 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, we next demonstrate that additive attribute noise acts as an implicit regularizer for the hypothesis space of linear models optimized for exponential loss.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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/public/guides/CodeSubmissionPolicy) 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 a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 ϵ i ∼ N ( 0, σ 2 I), where 0 is a zero vector and I is identity matrix, to every sample x i (and thus creating a new sample x ′ i = x i + ϵ) implicitly increases the ℓ 2 regularization parameter from C to C + σ 2 . Semenova et al. [2023] 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 classification, additive attribute noise similarly functions as implicit ℓ 2 regularization on the logarithm of the loss for an otherwise unregularized setting. We give an explicit characterization of the regularization parameter based on the variance of the noise added.Theorem 9 (Exponential loss under additive attribute noise). Consider the dataset S and a hypothesis space F of linear models, F = {f = ω T x, ω ∈ R p }. For a given model f ∈ F, consider the exponential loss L S (f ) = 1 n n i=1 e -yiω T xi . Let ϵ i , such that ϵ i ∼ N ( 0, σ 2 I) (σ > 0, I is identity matrix), be i.i.d. noise vectors added to every sample:x ′ i = x i + ϵ i . If E ϵ L S ε(σ) (f )is the expected exponential loss under additive Gaussian noise, thenE ϵ L S ε(σ) (f ) = L S (f ) • e σ 2 2 ∥ω∥ 2 2 ,where for simplicity we denote E ϵ1,...,ϵn∼N ( 0,σ 2 I) as E ϵ .A proof of Theorem 9 is in Appendix G. Immediately from Theorem 9, we have thatargmin f ∈F E ε L Sσ (f ) = argmin f ∈F log L S (f ) + σ 2 2 ∥ω∥ 2 2 .In other words, additive noise introduces ℓ 2 regularization on the logarithm of the exponential loss. Furthermore, the ℓ 2 regularization parameter is explicitly given as σ 2 2 . This shows that additive attribute noise encourages linear models to become simpler when there is more noise present.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Experimental designs are detailed in Appendix I.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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. 
experimental results: 
 We now present experimental results supporting the results in Section 4 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 on criminal recidivism and financial datasets to emphasize the applicability of our work to high-stakes domains with human data. Please see Appendix I for additional experiments.7.1 Sparse Decision Trees, 0-1 Loss, Random Label Noise. We used the GOSDT-guesses algorithm by McTavish et al. [2022] to optimize sparse decision trees over varying amounts of label noise (between 0.0 and 0.3). In order to correctly simulate the results in Theorem 1, the experiment estimates the size of a model optimized over the expectation over For the hypothesis space of sparse decision trees and 0-1 loss, the number of 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 clean data with regularization λ 1-2ρ (see Theorem 1). (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 to the dataset. E Sρ LSρ + λR(f )). This is different from taking the expectation of the size of models optimized over data with only a single noise draw (E Sρ R(f * ), where f * ∈ arg min f ∈F LSρ (f ) + λR(f )). To approximate optimization over expected noise draws, we concatenated 250 noise draws into a single dataset upon which to optimize a decision tree. The full experimental design is presented in Appendix I. The results of this experiment are shown in Figure 1 (a)-(b). These results demonstrate simplification in accordance with Theorem 2 and the alignment between models trained on clean data with varying regularization and models trained on noisy data with consistent regularization (Theorem 1).An interesting observation from these experiments is that, as we increase the label noise parameter, the generalization gap between the accuracy on the clean train and test set tends to shrink and the test accuracy remains very stable (see Figures 2, 6, 7 ). This is what we would expect given Theorems 1 and 2, since optimizing over the expectation of noise increases the effective regularization in the clean problem.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 σ ∈ [0.05, 0.5]. For each noise draw, we computed the optimal linear model on the noisy dataset using gradient descent. In Figure 1 (c), we observe that, as the noise level σ increases, the complexity of the optimal model rapidly decreases. This corroborates the regularizing effect of noise demonstrated in Theorem 9.In Figure 3 , 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 I.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: 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 a model on the concatenated version of many independent noise draws -performing this operation many times to measure the error is prohibitively expensive. The error is sufficiently mitigated by sampling a very large number of noise draws.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is 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).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
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 of possible noise draws with label-flip probability ρ. 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 a single noise draw may deviate from the optimal model over the expectation of noise draws. One possible future direction is to bound the expected complexity of a model optimized over a single noise draw in terms of sample size and the probability of flipping labels.A natural extension of our work is to 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 to 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 to those as in Section 6.We can also try to generalize to other noise models (i.e. random flipping noise in 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 1, as the optimization problems are no longer equivalent. If there is non-uniform noise at least ρ, it can be decomposed into the non-uniform distribution plus ρ uniform label noise, and our results in Theorem 1 can be applied. However, such decomposition is not always realistic as, for example, it is very likely that some features are not noisy.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We discuss our compute time and resources in a separate subsection in Appendix I.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 of compute required for each of the individual experimental runs as well as 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 make it into the paper). 
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 of recidivism are made ∼2 or 3 years in advance, giving time for a multitude of random interactions in the world to take place. This unpredictability leads, as we showed in this paper, to inherent regularization, and provably simpler models than if noise were not present. Rather than assuming that increased algorithmic sophistication in the future can potentially lead to improved accuracy using the same types of data, it is more realistic to assume that the distributions of data in the future are generally similar to those in the present, and that our best ML methods already reach an approximate performance 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 et al., 2020] and patients being deceived about the value of expensive medical treatment options [Afnan et al., 2021] .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 understanding can empower policymakers to advocate for the use of simple, interpretable models, ensuring the trustworthy, accessible, and equitable deployment of AI systems in high-stakes decision domains.Theorem 1 (Regularized 0-1 Loss under Random Label Noise). Consider true data distribution D, and uniform label noise with noise parameter ρ ∈ (0, 1/2). Let D ρ denote the noisy version of D. Consider 0-1 loss L and let R : F → R be a regularization function with λ ∈ R + a regularization parameter. Formally,arg min f ∈F L Dρ (f ) + λR(f ) = arg min f ∈F L D (f ) + λ 1 -2ρ R(f ).Similarly, given a dataset S sampled according to D, and S ρ the noisy version of S,arg min f ∈F E Sρ LSρ (f ) + λR(f ) = arg min f ∈F LS (f ) + λ 1-2ρ R(f ).Proof. Recall that the true risk for 0-1 lossL D (f ) = E z=(x,y)∼D [l(f, z)] = E (x,y)∼D [1 [f (x)̸ =y] ]. Semenova et al. [2023] show that L Dρ (f ) = (1 -2ρ)L D (f ) + ρ.This is independent of regularization, so we haveL Dρ (f ) + λR(f ) = (1 -2ρ)L D (f ) + λR(f ) + ρ.Since the minimization procedure is invariant to shifts and scales by constants, we concludearg min f ∈F L Dρ (f ) + λR(f ) = arg min f ∈F (1 -2ρ)L D (f ) + λR(f ) + ρ = arg min f ∈F (1 -2ρ)L D (f ) + λR(f ) = arg min f ∈F L D (f ) + λ 1 -2ρ R(f ).An identical argument applies to the finite data case, where we use the remark in the proof of Theorem 2 of [Semenova et al., 2023] .Theorem 2 (Optimal model simplifies under random label noise). Under the same assumptions as in Theorem 1, let f * D be the optimal model in F over distribution D and let f * Dρ be the optimal model in F over D ρ . Then either R(f* Dρ ) = R(f * D ) and L D (f * Dρ ) = L D (f * D ) (same complexity model) or R(f * Dρ ) < R(f * D ) and L D (f * Dρ ) > L D (f * D ) (strictly simpler model).An identical result applies for finite data when f * Sρ is optimized over the loss function E Sρ LSρ (f ).Proof. Consider optimal modelsf * D ∈ arg min f ∈F L D (f ) + λR(f ) f * Dρ ∈ arg min f ∈F L D (f ) + λ 1 -2ρ R(f ).(by Theorem 1)Then, by definition,L D (f * D ) + λR(f * D ) ≤ L D (f * Dρ ) + λR(f * Dρ ) and L D (f * Dρ ) + λ 1 -2ρ R(f * Dρ ) ≤ L D (f * D ) + λ 1 -2ρ R(f * D ). This gives λ R(f * D ) -R(f * Dρ ) ≤ L D (f * Dρ ) -L D (f * D ) ≤ λ 1 -2ρ R(f * D ) -R(f * Dρ ) (3) Assume for contradiction that R(f * Dρ ) > R(f * D ) ⇐⇒ R(f * D ) -R(f * Dρ ) < 0. Then L D (f * Dρ ) -L D (f * D ) ≥ λ R(f * D ) -R(f * Dρ ) ⇐⇒ L D (f * Dρ ) -L D (f * D ) R(f * D ) -R(f * Dρ ) ≤ λ and L D (f * Dρ ) -L D (f * D ) ≤ λ 1 -2ρ R(f * D ) -R(f * Dρ ) ⇐⇒ L D (f * Dρ ) -L D (f * D ) R(f * D ) -R(f * Dρ ) ≥ λ 1 -2ρ Since λ 1-2ρ > λ for 0 < ρ < 1 2 , this is a contradiction. Thus, R(f * Dρ ) ≤ R(f * D ) which immediately gives L D (f * Dρ ) ≥ L D (f * D ).The two cases in the lemma follow from ( 3). An identical argument holds for the finite data case.We now highlight an intermediate step in the proof of Theorem 2, which gives us an upper bound on the complexity of an optimal model over a noisy data distribution.Corollary 10. Under the same assumptions as in Theorem 2,R(f * Dρ ) ≤ R(f * D ) - 1 -2ρ λ L D (f * Dρ ) -L D (f * D )This follows immediately from (3). As we expect, the same result holds for finite sample S and S ρ sampled from distributions D and D ρ .Note that, for a fixed amount of label noise, this bound depends only on the complexity of the optimal model over clean data, and the difference in loss over the clean distribution between optimal models optimized over noisy and clean data. The amount of implicit simplification due to noise depends on the degradation of generalization performance caused by noise. We plot this bound in Figures 2, 6 , and 7, noting that the bound loosens as ρ increases and the generalization difference remains constant.Theorem 3 (Models that enter the noisier true Rashomon set are simple). Consider true data distribution D, 0-1 loss function, regularization R(•) and regularization parameter λ. Consider also uniform label noise, where each label is flipped independently with probability ρ ∈ (0, 1 2 ). Let D ρ be the noisier data distribution. If Obj Dρ (f * D ) > Obj Dρ (f * Dρ ) + 2ρθ, i.e., the optimal model over clean data distribution D is not in the Rashomon set over the noisy distribution with Rashomon parameter 2ρθ, then every model from F in that enters the noisier true Rashomon setR set Dρ (F, θ) is simpler than f * D : ∀ f ∈ F in : R( f ) < R(f * D ). More specifically, R( f ) < R(f * D ) -1 λ ∆ 2ρ -θ , where ∆ = Obj Dρ (f * D ) -Obj Dρ (f * Dρ ). Note that ∆ 2ρ -θ > 0.An identical result applies for finite data when models are optimized over E Sρ LSρ (f ).Proof. Consider f ∈ F in . Then we have that f ̸ ∈ R set D (F, θ), f ∈ R set Dρ (F, θ), and therefore:EQUATIONEQUATIONAdditionally, from Semenova et al. [2023] , we have:EQUATION)Thus we have:EQUATIONLet's focus on the difference between two objectives:Obj Dρ (f * Dρ ) -(1 -2ρ)Obj D (f * D ) = Obj Dρ (f * Dρ ) -(1 -2ρ)L D (f * D ) -(1 -2ρ)λR(f * D ) = Obj Dρ (f * Dρ ) -(1 -2ρ)L D (f * D ) -ρ -(1 -2ρ)λR(f * D ) + ρ (6) = Obj Dρ (f * Dρ ) -L Dρ (f * D ) -λR(f * D ) + 2ρλR(f * D ) + ρ = Obj Dρ (f * Dρ ) -Obj Dρ (f * D ) + 2ρλR(f * D ) + ρ = 2ρλR(f * D ) + ρ -∆, where ∆ = Obj Dρ (f * D ) -Obj Dρ (f * Dρ ). Since by assumption f * D ̸ ∈ R set Dρ (F, 2ρθ), then ∆ > 2ρθ and ∆ 2ρ -θ > 0.Therefore in ( 7) we have:R( f ) < 1 2ρλ 2ρθ -ρ + Obj Dρ (f * Dρ ) -(1 -2ρ)Obj D (f * D ) = 1 2ρλ (2ρθ -ρ + 2ρλR(f * D ) + ρ -∆) = R(f * D ) - 1 λ ∆ 2ρ -θ < R(f * D ).An identical proof applies to the finite dataset S, where the model f is in the noisier expected Rashomon set ifE Sρ LSρ (f ) + R(f ) ≤ E Sρ LSρ (f * E Sρ ) + R(f * E Sρ ), where f * E Sρ ∈ arg min f ∈F E Sρ LSρ (f ) + R(f ).Models in F out are complex. As the theorem above states, models that enter the noisy Rashomon set tend to be simpler. Now, we will show that models that exit the clean Rashomon set are complex models that potentially will overfit the noisier data. We illustrated this empirically in Section 7.3 and now prove more formally in the next theorem.Theorem 11 (Models that exit the clean true Rashomon set are complex). Consider true data distribution D, 0-1 loss function, regularization R(•) and regularization parameter λ. Consider also uniform label noise, where each label is flipped independently with probability ρ < 1 2 . Let D ρ be the noisier data distribution. If Obj D (f * Dρ ) > Obj D (f * D ) + 2ρθ, i.e., the optimal model over noisy data distribution D ρ is not in the clean true Rashomon set with Rashomon parameter 2ρθ (note that this is a symmetric assumption to the assumption in Theorem 3), then every model from F out that exits the clean true Rashomon set R set D (F, θ) is more complex than f * Dρ :∀f ∈ F out : R(f ) > R(f * Dρ ) + 2(1 -ρ) θ λ .Proof. Let f ∈ F out . By the definition of F out , we haveEQUATIONandEQUATIONFrom ( 8), ( 6) and by the definition of the objective, we have that,(1 -2ρ)L D (f ) + λR(f ) > (1 -2ρ)L D (f * Dρ ) + λR(f * Dρ ) + θ,and(1 -2ρ)Obj D (f ) + 2ρλR(f ) > (1 -2ρ)Obj D (f * Dρ ) + 2ρλR(f * Dρ ) + θ.We use equation( 9) to substitute in Obj D (f * D ) + θ for Obj D (f ) and obtain(1 -2ρ)(Obj D (f * D ) + θ) + 2ρλR(f ) > (1 -2ρ)Obj D (f * Dρ ) + 2ρλR(f * Dρ ) + θ.We can rearrange this inequality to solve for the regularization R(f ) of the models that exit clean true Rashomon set:R(f ) > R(f * Dρ ) + θ λ + 1 -2ρ 2ρλ (Obj D (f * Dρ ) -Obj D (f * D )).By assumption, Obj D (f * Dρ ) > Obj D (f * D ) + 2ρθ and, therefore we get thatR(f ) > R(f * Dρ ) + θ λ + 1 -2ρ 2ρλ 2ρθ = R(f * Dρ ) + 2(1 -ρ)θ λ .For a given continuous feature g with values g 1 ≤ . . . ≤ g T and a set 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 a decision stump on g. We can choose instead to plot the absolute number of negatively and positively classified camples, forming the unnormalized ROC curve of g. The resulting unnormalized AUC of g is defined as the area under the unnormalized ROC curve of g, which can be written asAU C S (g) = n + n -AU C S (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 AU C(g, Y ) to denote unnormalized AUC, where AU C(g, Y ) = AU C S (g). If g has T distinct values, then the unnormalized AUC has a closed-form:EQUATION)Intuitively, equation 10 counts the number of unit squares below the unnormalized ROC curve. We now recall and prove Theorem 5.Theorem 5. Consider a balanced dataset S = X × Y , i.e. Pr(y = 1) = Pr(y = -1). Let g = x .,j be a continuous feature with distinct values g 1 < . . . < g n . Let AU C S (g) denote the unnormalized AUC value of g on the labels Y . Consider uniform label noise, where each label is flipped independently with probability ρ < 1 2 . Let S ρ be a noisier dataset. Then for every feature g ∈ G:E Sρ [AU C Sρ (g)] = (1 -2ρ)AU C S (g) + C(ρ, n),where C(ρ, n) = ρ n 2 n 2 + ρ -1 is constant for a given ρ and n.Proof. Under the noise model, each label is flipped independently with probability ρ, where 1 -ρ is then the probability that the label was not flipped. Using equation 10, we can writeE Ỹ [AU C(g, Ỹ )] = E Ỹ   i<j 1 ỹi=1∧ỹj =-1   = i<j E Ỹ 1 ỹi=1∧ỹj =-1 = i<j Pr(ỹ i = 1, ỹj = -1) = i<j [1 yi=-1,yj =-1 Pr(y i ̸ = ỹi , y j = ỹj ) + 1 yi=1,yj =-1 Pr(y i = ỹi , y j = ỹj ) + 1 yi=-1,yj =1 Pr(y i ̸ = ỹi , y j ̸ = ỹj ) + 1 yi=1,yj =1 Pr(y i = ỹi , y j ̸ = ỹj )] = i<j [ρ(1 -ρ)1 yi=-1,yj =-1 + (1 -ρ) 2 1 yi=1,yj =-1 + ρ 2 1 yi=-1,yj =1 + ρ(1 -ρ)1 yi=1,yj =1 ].Consider each of the terms separately. We have that i<j1 yi=-1,yj =-1 = i<j 1 yi=1,yj =1 = n/2 2 ,since there are n 2 positive and negative samples, so there are n/2 2 unordered pairs of each. We also have by definition i<j 1 yi=1,yj =-1 = AU C(g, Y ), and since there are ( n 2 ) 2 unordered pairs of exactly one positive and one negative value, we lastly have thati<j 1 yi=-1,yj =1 = n 2 2 -AU C(g, Y ).Thus, putting it all together, we obtain the following for the unnormalized AUC:E Ỹ [AU C(g, Ỹ )] = (1 -ρ) 2 AU C(g, Y ) + ρ 2 n 2 2 -AU C(g, Y ) + 2ρ(1 -ρ) n 2 2 = (1 -2ρ)AU C(g, Y ) + ρ 2 n 2 2 + ρ(1 -ρ) n 2 n 2 -1 = (1 -2ρ)AU C(g, Y ) + ρ n 2 n 2 + ρ -1 .If the dataset is not balanced, then we can use an identical proof to show thatE Ỹ AU C(g, Ỹ ) = (1 -2ρ)AU C(g, Y ) + C(ρ, n + , n -),whereC(ρ, n + , n -) = -ρ(1 -2ρ)n + n -+ ρ(1 -ρ) n + +n - 2 .Corollary 7. Consider a dataset S = X × Y . Let {AU C S (g j )} p j=1 be in decreasing order and spaced by distances at most δ, meaning that 0 ≤ AU C S (g j ) -AU C S (g j+1 ) ≤ δ for each j = 1, . . . , p -1. Assume that we apply uniform label noise with flip probabilities ρ 1 and ρ 2 to S to obtain S ρ1 and S ρ2 , and that|G Sρ 1 AU C Sρ 1 (G, γ)| < p. If ρ 2 ≥ ν(ρ 1 ) := 1 2 1 -γ(1-2ρ1) γ+δ(1-2ρ1)noting that ν(ρ 1 ) > ρ 1 , then the size of the set of features which are good in expectation is strictly larger with more noise,|G E Sρ 1 AU C Sρ 1 (G, γ)| < |G E Sρ 2 AU C Sρ 2 (G, γ)|.Proof. Note that the features g 1 , . . . g p are in decreasing order by their unnormalized AUC, since by Corollary statement, 0 ≤ AU C S (g j ) -AU C S (g j+1 ) ≤ δ. From Theorem 5, we know thatE Sρ AU C Sρ (g) = (1 -2ρ)AU C S (g) + C(ρ, n),where C(ρ, n) = ρ n 2 n 2 + ρ -1 is a constant that depends only on ρ and n. Given that (1 -2ρ)x + C(ρ, n) is nondecreasing with respect to x ∈ R when 0 ≤ ρ < 0.5 is held constant, g 1 remains the best feature under noise (i.e. has the highest unnormalized AUC value). Thus, the set of good features is the set of features g j , where each g j satisfies the following:EQUATIONFor ease of notation let, a j = AU C S (g 1 ) -AU C S (g j ). Let k be the size of the set of good features under noise level ρ 1 , so that|G E Sρ 1 AU C Sρ 1 (G, γ)| = k.Then, from (11) we have that:EQUATIONTo show that |G E Sρ 2 AU C Sρ 2 (G, γ)| ≥ k + 1, it suffices to show that g k+1 is in the set of good features under noise level ρ 2 , which is equivalent to the statement (1 -2ρ 2 )a k+1 ≤ γ.Note that by the assumption of the Corollary, for each j = 1, . . . , p -1, we have thata j+1 -a j = AU C S (g j ) -AU C S (g j+1 ) ≤ δ.Then, from ( 11) and ( 12) we get(1 -2ρ 1 )a k+1 = (1 -2ρ 1 )a k + (1 -2ρ 1 )(a k+1 -a k ) ≤ γ + (1 -2ρ 1 )δ, which means that a k+1 ≤ γ 1 -2ρ 1 + δ.If ρ 2 ≥ ν(ρ 1 ), then we have(1 -2ρ 2 )a k+1 ≤ (1 -2ρ 2 ) γ 1 -2ρ 1 + δ ≤ (1 -2ν(ρ 1 )) γ 1 -2ρ 1 + δ ≤ 1 -1 - γ(1 -2ρ 1 ) γ + δ(1 -2ρ 1 ) γ 1 -2ρ 1 + δ = γ(1 -2ρ 1 ) γ + δ(1 -2ρ 1 ) • γ 1 -2ρ 1 + δ = γ(1 -2ρ 1 ) γ + δ(1 -2ρ 1 ) • γ + δ(1 -2ρ 1 ) 1 -2ρ 1 = γ. (13) Therefore, we proved that (1 -2ρ 2 )a k+1 ≤ γ, which means that |G E Sρ 2 AU C Sρ 2 (G, γ)| ≥ k + 1 and consequently |G E Sρ 1 AU C Sρ 1 (G, γ)| < |G E Sρ 2 AU C Sρ 2 (G, γ)| as claimed.F Proof of Theorem 8Theorem 8 (Empirical Rashomon ratio increases when the set of good features increases). For a dataset S = X × Y with binary feature matrix X ∈ {-1, 1} n×p , consider a hypothesis space F d of fully grown trees of d. Consider uniform random label noise with noise parameter ρ. Let H set E Sρ (F d ) denote the set of grounded models, based on the set of good features G E Sρ AU C Sρ (G, γ). 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 ρ 2 ≥ ν(ρ 1 ),H set E Sρ 1 (F d ) < H set E Sρ 2 (F d ) and H ratio E Sρ 1 (F d ) < H ratio E Sρ 2 (F d ).Proof. As in Proposition 6 of Semenova et al. [2023] , the hypothesis space of fully-grown trees of depth d contains| F d | = 2 2 d d k=1 (p -k + 1) 2 k-1trees, where symmetric trees are not included, meaning that split = 0 is on the left and 1 is on the right.The trees in the set of grounded models must have at least one good feature. Moreover, the labels in the set of grounded models are assigned to the trees based on the data, meaning that it contains|H set E Sρ | = d k=1 (p -k + 1) 2 k-1 - d k=1 (|p bad E Sρ | -k + 1) 2 k-1trees, where |p badE Sρ | = p -|G E Sρ AU C Sρ (G, γ)|.Therefore the fraction of grounded models is:H ratio E Sρ (F p d ) = |H set E Sρ (F p d )| | F p d | = d k=1 (p -k + 1) 2 k-1 - d k=1 (|p bad E Sρ | -k + 1) 2 k-1 2 2 d d k=1 (p -k + 1) 2 k-1 = 1 2 2 d   1 - d k=1 (|p bad E Sρ | -k + 1) 2 k-1 d k=1 (p -k + 1) 2 k-1   = 1 2 2 d   1 - d k=1 |p bad E Sρ | -k + 1 p -k + 1 2 k-1   . For noise levels ρ 1 , ρ 2 from Corollary 7 if ρ 2 ≥ ν(ρ 1 ), then |G E Sρ 1 AU C Sρ 1 (G, γ)| < |G E Sρ 2 AU C Sρ 2 (G, γ)|, and |p bad E Sρ 1 | > |p bad E Sρ 2 |. Therefore, |H set E Sρ 1 (F p d )| = d k=1 (p -k + 1) 2 k-1 - d k=1 (|p bad E Sρ 1 | -k + 1) 2 k-1 < d k=1 (p -k + 1) 2 k-1 - d k=1 (|p bad E Sρ 2 | -k + 1) 2 k-1 = |H set E Sρ 2 (F p d )|,andH ratio E Sρ 1 (F p d ) = 1 2 2 d   1 - d k=1 |p bad E Sρ 1 | -k + 1 p -k + 1 2 k-1    < 1 2 2 d   1 - d k=1 |p bad E Sρ 2 | -k + 1 p -k + 1 2 k-1    = H ratio E Sρ 2 (F p d ).Thus, with noise, the size of the set and fraction of grounded models increases.Theorem 9 (Exponential loss under additive attribute noise). Consider the dataset S and a hypothesis space F of linear models, F = {f = ω T x, ω ∈ R p }. For a given f ∈ F, consider the exponential loss L S (f ) = 1 n n i=1 e -yiω T xi . Let ϵ i , such that ϵ i ∼ N ( 0, σ 2 I) (σ > 0, I is identity matrix), be i.i.d. noise vectors added to every sample:x ′ i = x i + ϵ i . If E ϵ L S ε(σ) (f )is the expected exponential loss under additive Gaussian noise, thenE ϵ L S ε(σ) (f ) = L S (f ) • e σ 2 2 ∥ω∥ 2 2 ,where for simplicity we denote E ϵ1,...,ϵn∼N ( 0,σ 2 I) as E ϵ .Proof. We can write the following:E ε L S ε(σ) (ω) = 1 n n i=1 E ε e -yiω T (xi+ε) = 1 n n i=1 e -yiω T xi E ε [e -yiω T ε ] = 1 n n i=1 e -yiω T xi E ε [e -ω T ε ] = E ε [e -ω T ε ] • 1 n n i=1 e -yiω T xi = L S (ω) • E ε [e -ω T ε ]From here, note that for any multivariate Gaussian random variable δ ∼ N (µ, Σ) and matrix A, we have that Aδ ∼ N (Aµ, AΣA T ). Repeated usage of this identity yieldsE ε [e -ω T ε ] = E δ∼N ( 0,I) [e -σω T δ ] = E δ∼N (0,∥ω∥ 2 2 ) [e -σδ ] = E δ∼N (0,1) [e -σ•∥ω∥ 2 •δ ]We can directly compute the latter term by integrating. For any k,E δ∼N (0,1) [e kδ ] = ∞ -∞ 1 √ 2π e -1 2 x 2 • e kx dx = ∞ -∞ 1 √ 2π e -1 2 (x-k) 2 + 1 2 k 2 dx = e 1 2 k 2 ∞ -∞ 1 √ 2π e -1 2 (x-k) 2 dx = e 1 2 k 2If we set k = -σ • ∥ω∥ 2 , then we obtain the claim.Note that there is an immediate generalization of Theorem 9 to when the standard deviation of noise applied is unequal across each feature. If feature j receives independent Gaussian noise with standard deviation σ j , thenE ε L S ε(σ) (ω) = L S (f ) • exp   1 2 p j=1 σ 2 j ω 2 j  We can observe that a higher degree of noise of a feature corresponds to a greater degree of regularization of the corresponding weight.In particular, if a given feature is not subject to additive Gaussian noise, then the weight corresponding to that feature is not regularized at all. In Table 2 , we provide the description of the datasets used in this paper and pre-processing steps.All categorical variables were one-hot encoded, and all continuous data was binned into a one-hot binary encoding using thresholds determined by the GOSDT-guesses algorithm [McTavish et al., 2022] . All rows with missing values were removed from the datasets unless otherwise indicated in the processing notes. The GOSDT-guesses algorithm was also used to perform feature selection.The dataset statistics presented in Table 2 reflect the data used in the experiments after all preprocessing, including feature selection. When necessary, we downsampled to balance classes to avoid trivial optimal sparse decision trees.I.1 The Complexity of Models in the Expected Empirical Rashomon SetWe 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 to 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 a multiplicative Rashomon parameter of 0.05 and a 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), in recidivism and credit default datasets (b), and in individual datasets, some of which are displayed in Figure 5 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 1 and 2. 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 be a limiting factor. 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 0 and 0.3, inclusive, we run the following procedure:1. Sample 250 i.i.d. draws of random label noise with parameter ρ.2. Stack all 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 clean 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 clean training set with regularization parameter λ/(1 -2ρ), and report the number of leaves in this model (orange).7. Compute the upper bound from Corollary 10 (green) based on the loss difference between the noisy optimal model and the baseline optimal model on clean data (difference in orange accuracy line from its initial value).Complete results of these experiments for all datasets are shown in Figure 2 , 6, and 7.Exponential Loss and Linear Models For the experiment corresponding to Theorem 9, we use a simpler setup to demonstrate that additive noise has a regularizing effect. We seek to optimize the exponential loss of a 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 a factor of 0.3 if the exponential loss plateaus for over 50 epochs. Using this optimization procedure, our experiment is as follows:3. Report the sum of the squares of the weights of the optimal model corresponding to continuous noisy features.Trees in the Rashomon set tend to 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 γ 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 at least one feature from the set of good features. The results are reported in the fourth column of We now present an empirical demonstration of the effect of label noise on relative feature quality, which we measure as a feature's AUC with the labels (see Section 5.1). 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, we designed our experiments to align with the assumptions in our theoretical results by intentionally removing features that were clear outliers in predictive quality.We are left with a somewhat uniform distribution of clean AUC values in Figure 4 . After adding 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 5.We performed experiments on Duke University's Computer Science Department cluster. We requested 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 1a-b , ,2, 6, 7), and 2 hours to compute the simplicity of models in the Rashomon set (Figures 3, 5 ). For the experiments corresponding to Figure 1c , it took up to 3 hours per dataset to compute the optimal models for all different noise levels and draws. : Feature AUC distribution before (left; blue) and after (right; orange) injecting 15% label noise, aggregated across 9 criminal recidivism and financial datasets with feature quality parameter γ = 0.05 (total of 109 features). All features degrade towards 0.5 AUC when label noise is introduced, and better features tend to degrade faster. This increases the size of the set of features within γ AUC of the best feature (green shaded regions) from 15 features with clean labels to 27 features with noisy labels, which aligns with our prediction in Corollary 7.(c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce 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 authors 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 be possible for other researchers to have some path to reproducing or verifying the results.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We use open access datasets and cite the sources of all the datasets we used in the paper.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.Sample 100 i.i.d. draws of additive Gaussian noise with standard deviation σ on all continuous features.2. For each noisy draw, find the optimal linear model using the gradient descent procedure described above. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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
1. (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. 
     - As a result, the optimal classifier with random label noise achieves has higher Error and smaller Reg than without label noise. 
     - 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. 
2. (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. 
3. (Implicit) In the setting of exponential loss in linear models with additive gaussian noise, there is an implicit L2 weight regularization.
strength_weakness: strength_weakness: - 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,\
[1] Loucas Pillaud-Vivien, Julien Reygner, Nicolas Flammarion. Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrization. 2022. \
[2] Jeff Z. HaoChen, Colin Wei, Jason D. Lee, Tengyu Ma. Shape Matters: Understanding the Implicit Bias of the Noise Covariance. 2020. \
[3] Alex Damian, Tengyu Ma, Jason D. Lee. Label Noise SGD Provably Prefers Flat Global Minimizers. 2021. \

- 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.  

- In Theorem 1 and 2, should there be some additional constraints on the regularization function? Such as nonnegative.
questions: questions: See above
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: questions: Please see the weaknesses.
limitations: limitations: Please see the weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: [-] Analysis is a bit limited to models where the trade-offs are already well-understood such as decision trees. 

[-] The theory seems to be focused on regularization where a penalty is involved only.
questions: questions: (1) Is there any intuition how this can be applied to mainstream regularization techniques like drop-out?
(2) While the theory is developed for general regularization penalties, can something more specific be said for specific choices?
(3) Can the Theorems be adopted to regularization schemes beyond those that involve a loss such as augmentation?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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).

- 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.
questions: questions: - How robust are your theoretical results to the assumption of uniform random label noise?
- 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: limitations: See weaknesses above.

Comments: title: Rebuttal response
Thanks
comment: I thank the authors for their response. I think my questions have been largely addressed. I have updated my score to reflect that.
Thank you once again for your feedback and time. As we approach the end of the author-reviewer discussion period, we wanted to check if our response has fully addressed your concerns. If you have any further comments or questions, please let us know. We would be happy to discuss them before the deadline.
Thank you again for your time and feedback on the paper. We are writing as the author-reviewer discussion period is ending soon. If you have any questions or comments, please let us know, as we would be happy to discuss them before the deadline.
Thank you for the clarification! My questions have been answered, and I've raised my score.
Thank you for the additional proofs and for highlighting the empirical trends I missed in the Appendix.

The rebuttal is acknowledged, and I will raise my scores further to reflect it.