Discriminative Feature Feedback with General Teacher Classes
This work provides foundational theoretical insights into interactive learning with richer feedback, which is incremental but clarifies limitations for researchers in machine learning theory.
The paper tackles the theoretical analysis of the Discriminative Feature Feedback (DFF) interactive learning protocol by studying its optimal mistake bounds in realizable and non-realizable settings, showing that the realizable dimension is insufficient to characterize non-realizable bounds or no-regret algorithms, unlike in online learning.
We study the theoretical properties of the interactive learning protocol Discriminative Feature Feedback (DFF) (Dasgupta et al., 2018). The DFF learning protocol uses feedback in the form of discriminative feature explanations. We provide the first systematic study of DFF in a general framework that is comparable to that of classical protocols such as supervised learning and online learning. We study the optimal mistake bound of DFF in the realizable and the non-realizable settings, and obtain novel structural results, as well as insights into the differences between Online Learning and settings with richer feedback such as DFF. We characterize the mistake bound in the realizable setting using a new notion of dimension. In the non-realizable setting, we provide a mistake upper bound and show that it cannot be improved in general. Our results show that unlike Online Learning, in DFF the realizable dimension is insufficient to characterize the optimal non-realizable mistake bound or the existence of no-regret algorithms.