TR#:  CS0811 
Class:  CS 
Title:  ONLINE LEARNING VERSUS
OFFLINE LEARNING. 
Authors:  S. BenDavid, E. Kushilevitz and Y. Mansour 
CS0811.pdf  
Abstract: 
We present an offline variant of the mistakebound model of learning. Just like in the well studied online model, a student in the offline 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 online model only the set of possible queries is known, in the offline 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 offline model. We apply this characterization to solve several natural questions that arise for the new model. First, we compare the mistake bounds of an offline student to those of a student learning the same concept classes in the online scenario. We show that the number of mistakes in the online learning is at most a \log n factor more than the offline learning, where n is the length of the sequence. In addition, we show that if there is an offline algorithm that does not make more than a constant number of mistakes for each sequence then there is an online 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 offline student. It turns out that there are sequences on which an offline 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 offline mistake bounds on permutations of the same sequence of nmany queries, cannot be larger than a multiplicative factor of \log n, and we present examples that obtain such a gap.

Copyright  The 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 (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1994/CS/CS0811), 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