Theoretical Analysis of Algorithms for On-line Selection

This note presents a complete and correct theoretical analysis of the algorithms for hypothesis selection that appeared in the paper "Practical Algorithms for On-line Selection" of the same authors [1]. 1 Introduction The purpose of this note is to provide a complete and correct theoretical analysis of the two algorithms for on-line selection presented in [1], the Constrained Selection (CS) algorithm and the Adaptive Selection (AS) algorithm. Our analysis is essentially the same as the one in that paper and we also get similar bounds. That is, algorithm CS has a bound on the number of examples needed of O(1=flfl 0 ) and algorithm AS of O(1=fl 2 0 ) while the usual batch approach discussed there had a bound of O(1=fl 2 ) (ignoring dependency on the confidence value ffi , the hypothesis size n and logarithmic factors). Recall fl 0 was the "advantage" over random guessing of the best hypothesis in the class and fl fl 0 a lower bound on it. The main differences in the analysis present..