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 $\mathcal{ D}$ are simply more difficult to learn than realizable distributions -- even when one discounts a learner's error by $\mathrm{ err}(h^*_{ \mathcal{ D}})$, the error of the best hypothesis in $\mathcal{ H}$ for $\mathcal{ D}$. Thus, optimal agnostic learners are permitted to incur excess error on (easier-to-learn) distributions $\mathcal{ D}$ for which $\tau = \mathrm{ err}(h^*_{ \mathcal{ D}})$ is small. Recent work of Hanneke, Larsen, and Zhivotovskiy (FOCS `24) addresses this shortcoming by including $\tau$ itself as a parameter in the agnostic error term. In this more fine-grained model, they demonstrate tightness of the error lower bound $\tau + \Omega \left(\sqrt{ \frac{ \tau (d + \log(1 / \delta))}{ m}} + \frac{ d + \log(1 / \delta)}{ m} \right)$ in a regime where $\tau > d/m$, and leave open the question of whether there may be a higher lower bound when $\tau \approx d/m$, with $d$ denoting $\mathrm{ VC}(\mathcal{ H})$. In this work, we resolve this question by exhibiting a learner which achieves error $c \cdot \tau + O \left(\sqrt{ \frac{ \tau (d + \log(1 / \delta))}{ m}} + \frac{ d + \log(1 / \delta)}{ m} \right)$ for a constant $c \leq 2.1$, thus matching the lower bound when $\tau \approx 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.
Categories: cs.LG stat.ML