An Almost Optimal PAC Algorithm

It is shown that every consistent algorithm L (even a provably suboptimal one) induces a family of PAC algorithms which come very close to optimality: the number of labeled examples needed by LK exceeds the general lower bound only by factor ‘K(1= ) where ’K denotes (a truncated version of) the K-times iterated logarithm.