Timezone: »

 
Poster
Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm
Akash Kumar · Yuxin Chen · Adish Singla

Tue Dec 07 04:30 PM -- 06:00 PM (PST) @
in Poster Session 2 »

We study the sample complexity of teaching, termed as "teaching dimension" (TD) in the literature, for the learning-with-equivalence-queries (LwEQ) paradigm. More concretely, we consider a learner who asks equivalence queries (i.e., "is the queried hypothesis the target hypothesis?"), and a teacher responds either "yes" or "no" along with a counterexample to the queried hypothesis. This learning paradigm has been extensively studied when the learner receives worst-case or random counterexamples; in this paper, we consider the optimal teacher who picks best-case counterexamples to teach the target hypothesis within a hypothesis class. For this optimal teacher, we introduce LwEQ-TD, a notion of TD capturing the teaching complexity (i.e., the number of queries made) in this paradigm. We show that a significant reduction in queries can be achieved with best-case counterexamples, in contrast to worst-case or random counterexamples, for different hypothesis classes. Furthermore, we establish new connections of LwEQ-TD to the well-studied notions of TD in the learning-from-samples paradigm.

Keywords: Theory

Author Information

Akash Kumar (University of California San Diego)
Yuxin Chen (Caltech)
Adish Singla (MPI-SWS)

More from the Same Authors