Discriminative Feature Feedback with General Teacher Classes

Omri Bar Oz, Tosca Lechner, Sivan Sabato
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-32, 2026.

Abstract

We study the theoretical properties of the interactive learning protocol Discriminative Feature Feedback (DFF). 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 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 non-realizable setting, and obtain novel structural results, as well as insights into the difference 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 the realizable dimension is insufficient to characterize the optimal non-realizable mistake bound or the existence of no-regret algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-bar-oz26a, title = {Discriminative Feature Feedback with General Teacher Classes}, author = {Bar Oz, Omri and Lechner, Tosca and Sabato, Sivan}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--32}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/bar-oz26a/bar-oz26a.pdf}, url = {https://proceedings.mlr.press/v313/bar-oz26a.html}, abstract = {We study the theoretical properties of the interactive learning protocol Discriminative Feature Feedback (DFF). 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 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 non-realizable setting, and obtain novel structural results, as well as insights into the difference 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 the realizable dimension is insufficient to characterize the optimal non-realizable mistake bound or the existence of no-regret algorithms.} }
Endnote
%0 Conference Paper %T Discriminative Feature Feedback with General Teacher Classes %A Omri Bar Oz %A Tosca Lechner %A Sivan Sabato %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-bar-oz26a %I PMLR %P 1--32 %U https://proceedings.mlr.press/v313/bar-oz26a.html %V 313 %X We study the theoretical properties of the interactive learning protocol Discriminative Feature Feedback (DFF). 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 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 non-realizable setting, and obtain novel structural results, as well as insights into the difference 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 the realizable dimension is insufficient to characterize the optimal non-realizable mistake bound or the existence of no-regret algorithms.
APA
Bar Oz, O., Lechner, T. & Sabato, S.. (2026). Discriminative Feature Feedback with General Teacher Classes. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-32 Available from https://proceedings.mlr.press/v313/bar-oz26a.html.

Related Material