Efficient Robust Learning at the Information-Theoretic Limit
Abstract
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 η+ ε where η is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than 2η+ ε. 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 η+ ε for any constant ε.
Related
- Conditional Fisher-Information Central Limit Theorems under Log-Concavity with Information-Theoretic Consequences
- Learning Rules, Memorizing Facts: An Information-Theoretic View of Hallucination
- Learning What Matters: Adaptive Information-Theoretic Objectives for Robot Exploration
- Dependency, Compression, and Synergy: A Unified Information-Theoretic View of Multimodal Learning
- Fundamental Limits of Information-Theoretic Secure Aggregation with User Dropouts in Federated Learning
BibTeX
@misc{klivans2026efficient,
title = {{Efficient Robust Learning at the Information-Theoretic Limit}},
author = {Adam R. Klivans and Konstantinos Stavropoulos and Sergei Tikhonov and Arsen Vasilyan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17655},
eprint = {2609.17655},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17655},
}
RIS
TY - UNPB
TI - Efficient Robust Learning at the Information-Theoretic Limit
AU - Adam R. Klivans
AU - Konstantinos Stavropoulos
AU - Sergei Tikhonov
AU - Arsen Vasilyan
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17655
UR - https://arxiv.org/abs/2609.17655
AB - 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 η+ ε where η is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than 2η+ ε. 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 η+ ε for any constant ε.
ER -