  Discriminative Feature Feedback is a setting proposed by Dastupta et al.
(2018), which provides a protocol for interactive learning based on feature
explanations that are provided by a human teacher. The features distinguish
between the labels of pairs of possibly similar instances. That work has shown
that learning in this model can have considerable statistical and computational
advantages over learning in standard label-based interactive learning models.
  In this work, we provide new robust interactive learning algorithms for the
Discriminative Feature Feedback model, with mistake bounds that are
significantly lower than those of previous robust algorithms for this setting.
In the adversarial setting, we reduce the dependence on the number of protocol
exceptions from quadratic to linear. In addition, we provide an algorithm for a
slightly more restricted model, which obtains an even smaller mistake bound for
large models with many exceptions.
  In the stochastic setting, we provide the first algorithm that converges to
the exception rate with a polynomial sample complexity. Our algorithm and
analysis for the stochastic setting involve a new construction that we call
Feature Influence, which may be of wider applicability.
