Learning Attribute-Efficiently with Corrupt Oracles

Abstract

We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature, and efficient solutions were found to most of their variants. Nonetheless, their reasonable combination is yet to be studied, and combining the existing solutions either fails or works with complexity that can be significantly improved. In this paper we prove equivalence of EXACT learning attribute-efficiently with and without corrupt oracles. For each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. We also generalize and improve previous non attribute-efficient algorithms for learning with corrupt oracles.