# Improved Robust Algorithms for Learning with Discriminative Feature Feedback

arXiv: https://arxiv.org/abs/2209.03753 · HTML: https://mlsanity.com/paper/2209.03753/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 17 references that are in the map.
- First posted on arXiv 8 Sep 2022.

## Builds on (most cited first, 5 of 5)

- [Making deep neural networks right for the right scientific reasons by interacting with their explanations](https://mlsanity.com/paper/2001.05371/) (2020)
- [ALICE: Active Learning with Contrastive Natural Language Explanations](https://mlsanity.com/paper/2009.10259/) (2020)
- [Teaching Categories to Human Learners with Visual Explanations](https://mlsanity.com/paper/1802.06924/) (2018)
- [Robust Learning from Discriminative Feature Feedback](https://mlsanity.com/paper/2003.03946/) (2020)
- [Crowdsourcing Feature Discovery via Adaptively Chosen Comparisons](https://mlsanity.com/paper/1504.00064/) (2015)

## Built on by (most cited first, 1 of 1)

- [Discriminative Feature Feedback with General Teacher Classes](https://mlsanity.com/paper/2510.07245/) (2025)

## Abstract (arXiv)

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.