Research map / Learning theory and algorithms / Prediction and decision losses
Using Noise to Infer Aspects of Simplicity Without Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically and empirically that label or attribute noise acts as an implicit regularizer, so noisy-data optima and Rashomon sets tend toward simpler models and noise enlarges the set of good features.
Problem
How much simpler can ML models become under different noise levels while keeping comparable generalization performance, relative to the noise-free case?
Approach
Random label noise under 0-1 loss is equivalent to rescaling the regularization parameter by 1/(1-2ρ), so noisy optimization equals cleaner optimization with stronger regularization; additive attribute noise under exponential loss acts as ℓ2 regularization on the log-loss with parameter σ²/2. The paper also shows noise enlarges the set of good features and hence the grounded-model fraction for unr
Key results
- Theorem 1 shows noisy 0-1 loss optimization with penalty λ equals clean optimization with penalty λ/(1-2ρ); sparse tree leaf counts decrease with label noise in experiments on recidivism and credit datasets.
- For linear models under exponential loss, the squared norm of relevant weights decreases as additive Gaussian noise σ increases (Figure 1c).
- Rashomon sets built on noisy data (Figure 3, 23 datasets) skew toward fewer leaves as noise rises from 0% to 30%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add uniform random label noise to the labels | models optimized with regularized 0-1 loss · general hypothesis spaces | effective regularization | Helped |
| add uniform random label noise to the labels | sparse decision trees trained with 0-1 loss · recidivism and credit datasets | number of leaves | Helped |
| add uniform random label noise to the labels | optimal models under regularized 0-1 loss · general hypothesis spaces | loss on cleaner data | Hurt |
| add uniform random label noise to the labels | regularized sparse decision trees · recidivism and finance datasets | Rashomon-set model complexity | Helped |
| add uniform random label noise to the labels | unregularized fully grown decision trees · binary-feature datasets | fraction of grounded models | Helped |
| add uniform random label noise to the labels | features ranked by AUC · classification datasets | number of good features | Helped |
| add Gaussian attribute noise to input features | linear models trained with exponential loss · binary classification datasets | squared norm of continuous-feature weights | Helped |
| increase uniform label-noise probability | sparse decision trees · recidivism datasets | test accuracy | No clear effect |
Surprising findings
- Test accuracy remains stable as label noise increases while the train-test generalization gap shrinks.
Limitations
- Theory for label noise applies to models optimized on expected loss over noise draws; single-draw behavior at small sample sizes may differ.
- Results proven only for 0-1 loss with uniform label noise and exponential loss with Gaussian attribute noise; other losses and noise models are left to future work.
- Decomposing non-uniform noise into uniform noise plus a base rate may not be realistic because some features are likely noise-free.
Experimental setup
Datasets: Amsterdam (Recidivism) Broward County (Recidivism) NIJ Recidivism Challenge COMPAS FICO Australian Credit German Credit GiveMeSomeCredit Polish Companies Iranian Churn Telco Churn Occupancy Detection
Benchmarks: recidivism datasets credit default datasets 23 real-world and synthetic tabular datasets
Metrics: number of leaves accuracy squared norm of relevant weights Rashomon set leaf distribution
Baselines: optimal sparse decision trees on clean data with adjusted regularization
Builds on: Semenova et al. 2023 Rashomon sets and noise GOSDT-guesses Bishop 1995 noise as regularization
Closest papers by meaning
- Position: Amazing Things Come From Having Many Good Models (ICML 2024 · similarity 0.85)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 2025 · similarity 0.85)
- Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noise (NeurIPS 2026 · similarity 0.84)
- Position: The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning (ICML 2024 · similarity 0.84)
- How Much is a Noisy Image Worth? Data Scaling Laws for Ambient Diffusion. (ICLR 2025 · similarity 0.84)
- DataDecide: How to Predict Best Pretraining Data with Small Experiments (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.