Learning from Equivalence Queries, Revisited

• URL: http://arxiv.org/abs/2604.04535v1
• Date: Mon, 06 Apr 2026 08:55:41 GMT
• Title: Learning from Equivalence Queries, Revisited
• Abstract summary: We study learning from equivalence queries under both full-information and bandit feedback.<n>Our analysis combines a game-theoretic view of symmetric adversaries with adaptive weighting methods and minimax arguments.
• Score: 62.46207559138802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 captures natural mechanisms such as random counterexamples (Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024), as well as generators that return the simplest counterexample according to a prescribed complexity measure. Within this framework, we study learning from equivalence queries under both full-information and bandit feedback. We obtain tight bounds on the number of learning rounds in both settings and highlight directions for future work. Our analysis combines a game-theoretic view of symmetric adversaries with adaptive weighting methods and minimax arguments.

Related papers

• Distribution-Free Sequential Prediction with Abstentions [7.110627876507878]
  We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d. instances.<n>At each round, the learner may also emphabstain from making a prediction without incurring any penalty if the instance was indeed corrupted.<n>We propose an textscAbstainBoost based on a boosting procedure of weak learners, which guarantees sublinear error for general VC classes.
  arXiv  Detail & Related papers  (2026-02-20T00:28:27Z)
• Rademacher learning rates for iterated random functions [0.0]
  We consider the case where the training dataset is generated by an iterated random function that is not necessarily irreducible or aperiodic.<n>Under the assumption that the governing function is contractive with respect to its first argument, we first establish a uniform convergence result for the corresponding sample error.<n>We then demonstrate the learnability of the approximate empirical risk minimization algorithm and derive its learning rate bound.
  arXiv  Detail & Related papers  (2025-06-16T19:36:13Z)
• Generation from Noisy Examples [2.3020018305241337]
  We show that generatability is largely unaffected by the presence of a finite number of noisy examples.<n>For finite and countable classes we show that generatability is largely unaffected by the presence of a finite number of noisy examples.
  arXiv  Detail & Related papers  (2025-01-07T23:16:14Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  A key challenge in machine learning is the prevalence of one-sided feedback.<n>We introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels.<n>We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case.
  arXiv  Detail & Related papers  (2024-11-20T04:21:07Z)
• Revisiting Optimism and Model Complexity in the Wake of Overparameterized Machine Learning [6.278498348219108]
  We revisit model complexity from first principles, by first reinterpreting and then extending the classical statistical concept of (effective) degrees of freedom. We demonstrate the utility of our proposed complexity measures through a mix of conceptual arguments, theory, and experiments.
  arXiv  Detail & Related papers  (2024-10-02T06:09:57Z)
• Adversarial Resilience in Sequential Prediction via Abstention [46.80218090768711]
  We study the problem of sequential prediction in the setting with an adversary that is allowed to inject clean-label adversarial examples. We propose a new model of sequential prediction that sits between the purely and fully adversarial settings.
  arXiv  Detail & Related papers  (2023-06-22T17:44:22Z)
• When are ensembles really effective? [49.37269057899679]
  We study the question of when ensembling yields significant performance improvements in classification tasks. We show that ensembling improves performance significantly whenever the disagreement rate is large relative to the average error rate. We identify practical scenarios where ensembling does and does not result in large performance improvements.
  arXiv  Detail & Related papers  (2023-05-21T01:36:25Z)
• Characterizing Datapoints via Second-Split Forgetting [93.99363547536392]
  We propose $$-second-$split$ $forgetting$ $time$ (SSFT), a complementary metric that tracks the epoch (if any) after which an original training example is forgotten. We demonstrate that $mislabeled$ examples are forgotten quickly, and seemingly $rare$ examples are forgotten comparatively slowly. SSFT can (i) help to identify mislabeled samples, the removal of which improves generalization; and (ii) provide insights about failure modes.
  arXiv  Detail & Related papers  (2022-10-26T21:03:46Z)
• Benign Overfitting in Adversarially Robust Linear Classification [91.42259226639837]
  "Benign overfitting", where classifiers memorize noisy training data yet still achieve a good generalization performance, has drawn great attention in the machine learning community. We show that benign overfitting indeed occurs in adversarial training, a principled approach to defend against adversarial examples.
  arXiv  Detail & Related papers  (2021-12-31T00:27:31Z)
• Adversarial Example Games [51.92698856933169]
  Adrial Example Games (AEG) is a framework that models the crafting of adversarial examples. AEG provides a new way to design adversarial examples by adversarially training a generator and aversa from a given hypothesis class. We demonstrate the efficacy of AEG on the MNIST and CIFAR-10 datasets.
  arXiv  Detail & Related papers  (2020-07-01T19:47:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.