Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?

This paper investigates efficient learning in PAC settings without full empirical risk minimization, using a weaker oracle that provides a single bit of information about concept realizability. The authors present a polynomial sample and oracle complexity algorithm for binary classification, agnostic learning, and partial concept classes, resolving a question from [AHHM21]. The study extends to multiclass and real-valued settings, highlighting the potential of alternative algorithmic principles. Key contributions include a randomized variant of the one-inclusion graph algorithm and improved sample complexities for various settings. The paper also establishes lower bounds, showing that even with a strong ERM oracle, learning certain classes with low dimensions is challenging. The work leaves open questions about the trade-offs between oracle efficiency and sample complexity in specific settings, and the implications of weak oracles for learning and security.