Using Noise to Infer Aspects of Simplicity Without Learning

Thank you for the review. We address the questions point-by-point below.

W1. Connection to the previous works. Theorems 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.

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

W2. Empirical results. The 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 components, 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.

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

W3. Noise model. In 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.

To 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. As in the experiments in our paper, we found simpler optimal models under a form of non-uniform label noise.

We will emphasize more in the paper the potential of future work exploring other, more complicated noise models.

Q1. Robustness to noise models. Our 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. However, 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.

Q2. Generalization to neural networks. Our 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). In 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.

Thank you again for the review, we'd be happy to engage in the discussion regarding any points mentioned.

Thank you for the review. We address the questions point-by-point below.

W1. Limitations of analysis. We'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.

W2. The regularization function generalization. Yes, in this paper we consider explicit regularization in the classic sense as a function added to the loss (see Tikhonov et.al., Solutions of ill-posed problems, 1977). Note that this technique encompasses an enormous number of methods. We would need to know what explicit or implicit regularization method you have in mind to offer more detailed comments.

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.

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

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

Q2. More specific results for the regularization. For 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.

Q3. Can we generalize to augmentation? In 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.

Thank you again for the review, we'd be happy to engage in the discussion regarding any points mentioned.

Thank you for the review. We appreciate your points and feedback.

W1. Theorem 3 conclusion.

Thank you for pointing this out.

We 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}$.

For Theorem 1, we will add the language to address the limitation of the empirical setting.

W2. Empirical results.

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

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

"While the Rashomon sets do contain simpler models, do 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.

"What fractions of models belong to $F_{in}$, $F_{both}$, and $F_{out}$ in practice?" - One can infer an estimate of sizes of $F_{in}$, $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).

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

Thank you for the review. We address the weaknesses point-by-point below.

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.

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.

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

We communicated these differences in the Introduction and we will emphasize them more in the theorems framing text during revision.

W3: Non-negativity of the regularization function. Thank 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.

Thank you again for the review, we'd be happy to engage in the discussion regarding any points mentioned.