Total: 1
Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case. Roughly speaking, this owes itself to the fact that non-realizable distributions D are simply more difficult to learn than realizable distributions -- even when one discounts a learner's error by err(h∗D), the error of the best hypothesis in H for D. Thus, optimal agnostic learners are permitted to incur excess error on (easier-to-learn) distributions D for which τ=err(h∗D) is small. Recent work of Hanneke, Larsen, and Zhivotovskiy (FOCS `24) addresses this shortcoming by including τ itself as a parameter in the agnostic error term. In this more fine-grained model, they demonstrate tightness of the error lower bound τ+Ω(√τ(d+log(1/δ))m+d+log(1/δ)m) in a regime where τ>d/m, and leave open the question of whether there may be a higher lower bound when τ≈d/m, with d denoting VC(H). In this work, we resolve this question by exhibiting a learner which achieves error c⋅τ+O(√τ(d+log(1/δ))m+d+log(1/δ)m) for a constant c≤2.1, thus matching the lower bound when τ≈d/m. Further, our learner is computationally efficient and is based upon careful aggregations of ERM classifiers, making progress on two other questions of Hanneke, Larsen, and Zhivotovskiy (FOCS `24). We leave open the interesting question of whether our approach can be refined to lower the constant from 2.1 to 1, which would completely settle the complexity of agnostic learning.