arXiv preprint ·
Efficient Robust Learning at the Information-Theoretic Limit
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $η+ \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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
A quantitative tree-likeness bound from average hyperbolicity
A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.