Technical Report CS0811

Authors: S. Ben-David, E. Kushilevitz and Y. Mansour

We present an off-line variant of the mistake-bound model of learning. Just like in the well studied on-line model, a student in the off-line model has to learn an unknown concept from a sequence of ``guess and test'' trials. In both models, the aim of the learner is to make as few mistakes as possible. The difference between the models is that, while in the on-line model only the set of possible queries is known, in the off-line model the sequence of queries (i.e., the identity of the queries as well as the order in which they are to be presented) is known to the learner in advance. We give a combinatorial characterization of the number of mistakes in the off-line model. We apply this characterization to solve several natural questions that arise for the new model. First, we compare the mistake bounds of an off-line student to those of a student learning the same concept classes in the on-line scenario. We show that the number of mistakes in the on-line learning is at most a \log n factor more than the off-line learning, where n is the length of the sequence. In addition, we show that if there is an off-line algorithm that does not make more than a constant number of mistakes for each sequence then there is an on-line algorithm that also does not make more than a constant number of mistakes. The second issue we address is the effect of the ordering of the queries on the number of mistakes of an off-line student. It turns out that there are sequences on which an off-line student can guarantee at most one mistake, yet a permutation of the same sequence forces him to err on many queries. We prove, however, that the gap, between the off-line mistake bounds on permutations of the same sequence of n-many queries, cannot be larger than a multiplicative factor of \log n, and we present examples that obtain such a gap.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1994
To the main CS technical reports page

Computer science department, Technion