On the equivalence of Occam algorithms

Many of these analyses have focused on th e implications and uses of complexity-based algorithms defined by Blumer et a l. in two seminal papers [4, 5]. Their algorithms were defined such that they a chieved zero training error on a sample, and outputted a hypothesis whose complexity (VC dimension for continuous alphabets; description length for disc rete ones) was at most a polynomial in the target concept complexity, multiplied b y a sub-linear factor in the sam. These "Occam algorithms" are weak approx imations of the minimum-consistent-hypothesis problem [6]. In this paper, we focus on the continuous-alphabet Occam algorithms. In 1989, Blumer et al. [5] showed that if a concept was learnable by th eir Occam algorithm, then it was polynomially learnable; they left open the question of whether the converse of this theorem was true.