# Efficient Robust Learning at the Information-Theoretic Limit

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 15 Sep 2026.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Approximate resilience, monotonicity, and the complexity of agnostic learning](https://mlsanity.com/paper/1405.5268/) (2014)
- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [Testably Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2406.06106/) (2024)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Learning Constant-Depth Circuits in Malicious Noise Models](https://mlsanity.com/paper/2411.03570/) (2024)
- [Is nasty noise actually harder than malicious noise?](https://mlsanity.com/paper/2511.09763/) (2025)
- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Robust Learning with Optimal Error](https://mlsanity.com/paper/2604.02555/) (2026)
- [Iterative Chow Filtering for Learning with Distribution Shift](https://mlsanity.com/paper/2605.17251/) (2026)

## Abstract (arXiv)

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of η + varepsilon where η is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than 2η + varepsilon. Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error η + varepsilon for any constant varepsilon.