Agnostic Learning from Tolerant Natural Proofs

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova


Abstract

We generalize the ``learning algorithms from natural properties'' framework of Carmosino et al. (CCC, 2016) to get agnostic learning algorithms from natural properties with extra features. We show that if a natural property (in the sense of Razborov and Rudich (JCSS, 1997)) is useful also against functions that are \emph{close} to the class of ``easy'' functions, rather than just against ``easy'' functions, then it can be used to get an agnostic learning algorithm over the uniform distribution with membership queries.


Versions