  The empirical risk minimization (ERM) principle has been highly impactful in
machine learning, leading both to near-optimal theoretical guarantees for
ERM-based learning algorithms as well as driving many of the recent empirical
successes in deep learning. In this paper, we investigate the question of
whether the ability to perform ERM, which computes a hypothesis minimizing
empirical risk on a given dataset, is necessary for efficient learning: in
particular, is there a weaker oracle than ERM which can nevertheless enable
learnability? We answer this question affirmatively, showing that in the
realizable setting of PAC learning for binary classification, a concept class
can be learned using an oracle which only returns a single bit indicating
whether a given dataset is realizable by some concept in the class. The sample
complexity and oracle complexity of our algorithm depend polynomially on the VC
dimension of the hypothesis class, thus showing that there is only a polynomial
price to pay for use of our weaker oracle. Our results extend to the agnostic
learning setting with a slight strengthening of the oracle, as well as to the
partial concept, multiclass and real-valued learning settings. In the setting
of partial concept classes, prior to our work no oracle-efficient algorithms
were known, even with a standard ERM oracle. Thus, our results address a
question of Alon et al. (2021) who asked whether there are algorithmic
principles which enable efficient learnability in this setting.
