# Robust Learning with Optimal Error

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 58 references that are in the map.
- First posted on arXiv 2 Apr 2026.

## Builds on (most cited first, 15 of 15)

- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Calibration Error for Decision Making](https://mlsanity.com/paper/2404.13503/) (2024)
- [Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance](https://mlsanity.com/paper/2006.03781/) (2020)
- [On the power of adaptivity in statistical adversaries](https://mlsanity.com/paper/2111.10352/) (2021)
- [Adaptive and oblivious statistical adversaries are equivalent](https://mlsanity.com/paper/2410.13548/) (2024)
- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)

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

- [Efficient Robust Learning at the Information-Theoretic Limit](https://mlsanity.com/paper/2609.17655/) (2026)

## Abstract (arXiv)

We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of textslrandomized hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. - For η-rate malicious noise, we show the optimal error is frac12 · η/(1-η), improving on the optimal error of deterministic hypotheses by a factor of 1/2. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can improve error by a factor of 6/7. - For η-rate nasty noise, we show the optimal error is frac32 · η for distribution-independent learners and η for fixed-distribution learners, both improving upon the optimal 2 η error of deterministic hypotheses. This closes a gap first noted by Bshouty et al. (Theoretical Computer Science 2002) when they introduced nasty noise and reiterated in the recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. (SODA 2026). - For η-rate agnostic noise and the closely related nasty classification noise model, we show the optimal error is η, improving upon the optimal 2η error of deterministic hypotheses. All of our learners have sample complexity linear in the VC-dimension of the concept class and polynomial in the inverse excess error. All except for the fixed-distribution nasty noise learner are time efficient given access to an oracle for empirical risk minimization.