[2604.04535] Learning from Equivalence Queries, Revisited

Computer Science > Machine Learning arXiv:2604.04535 (cs) [Submitted on 6 Apr 2026] Title:Learning from Equivalence Queries, Revisited Authors:Mark Braverman, Roi Livni, Yishay Mansour, Shay Moran, Kobbi Nissim View a PDF of the paper titled Learning from Equivalence Queries, Revisited, by Mark Braverman and 4 other authors View PDF Abstract:Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. This differs from standard supervised learning frameworks, which focus on loss or regret minimization over a fixed sequence of prediction tasks. Motivated by this setting, we revisit the classical model of learning from equivalence queries, introduced by Angluin (1988). In this model, a learner repeatedly proposes hypotheses and, when a deployed hypothesis is inadequate, receives a counterexample. Under fully adversarial counterexample generation, however, the model can be overly pessimistic. In addition, most prior work assumes a \emph{full-information} setting, where the learner also observes the correct label of the counterexample, an assumption that is not always natural. We address these issues by restricting the environment to a broad class of less adversarial counterexample generators, which we call \emph{symmetric}. Informally, such generators choose counterexamples based only on the symmetric difference between the hypothesis and the target. This class ...