Efficient Robust Learning at the Information-Theoretic Limit

Summary

This theory paper resolves the main open problem left by Blanc (FOCS 2026): whether the information-theoretically optimal error η+ε is achievable in polynomial time for supervised learning under bounded contamination, where an η-fraction of the training set may be replaced arbitrarily. In the fixed-distribution model, where the learner also receives a clean unlabeled reference sample, the authors give two algorithms. First, a polynomial-time algorithm with access to an ERM oracle that learns any finite-VC-dimension concept class to error η+ε using O((VCdim·log(2/ε)+log(1/δ))/ε⁴) samples (Theorem 1.3). Second, an oracle-free algorithm for classes admitting low-degree sandwiching polynomials under hypercontractive marginals, with sample complexity (A(d+1))^O(L)/ε⁵ (Theorem 1.4). The key idea recasts Blanc's inefficient search over hypothesis mixtures as online convex optimization: per-round rewards are affine, an online Frank-Wolfe procedure with regret O(T^(3/4)) reduces each step to a weighted ERM call, and iterative polynomial filtering combined with projected gradient ascent handles the oracle-free case. Consequences include the first polynomial-time η+ε learner for halfspaces under Gaussian marginals, plus runtime guarantees for intersections of halfspaces and AC0 circuits (Table 1). Limitations: output hypotheses must be randomized (deterministic hypotheses face a 2η barrier), ε-dependence is heavy, and Table 1 runtimes rely on sandwiching constructions cited from prior work.