# Noise in Classification

arXiv: https://arxiv.org/abs/2010.05080 · HTML: https://mlsanity.com/paper/2010.05080/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2020.

## Built on by (most cited first, 11 of 11)

- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise](https://mlsanity.com/paper/2101.01152/) (2021)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [Learning Linear Utility Functions From Pairwise Comparison Queries](https://mlsanity.com/paper/2405.02612/) (2024)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [Regularized Robustly Reliable Learners and Instance Targeted Attacks](https://mlsanity.com/paper/2410.10572/) (2024)
- [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025)
- [Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measure](https://mlsanity.com/paper/2511.01847/) (2025)
- [Robustly Reliable Learning for Regression](https://mlsanity.com/paper/2610.17381/) (2026)

## Abstract (arXiv)

This chapter considers the computational and statistical aspects of learning linear thresholds in presence of noise. When there is no noise, several algorithms exist that efficiently learn near-optimal linear thresholds using a small amount of data. However, even a small amount of adversarial noise makes this problem notoriously hard in the worst-case. We discuss approaches for dealing with these negative results by exploiting natural assumptions on the data-generating process.