From on-line to batch learning

Abstract

We contrast on-line and batch settings for concept learning, and describe an on-line learning model in which no probabilistic assumptions are made. We briefly mention some of our recent results pertaining to on-line learning algorithms developed using this model. We then turn to the main topic, which is an analysis of a conversion to improve the performance of on-line learning algorithms in a batch setting. For the batch setting we use the PAC-learning model. The conversion is straightforward, consisting of running the given on-line algorithm, collecting the hypotheses it uses for making predictions, and then choosing the hypothesis among them that does the best in a subsequent hypothesis testing phase. We have developed an analysis, using a version of Chernoff bounds applied to supermartingales, that shows that for some target classes the converted algorithm will be asymptotically optimal.