Algorithm 2 Reduce s k Turing optimal learning to Turing optimal learning . Input learner A

The reduction used in Claim 1 to show the equivalence of Turing-optimal and (s, k)-Turing-optimal, is shown in Algorithm 2. Note that the algorithm was chosen for its simplicity rather than optimizing parameters. Finally, clearly Algorithm 2 runs in polynomial time, i.e., time poly(d, m + M) due to the timeout and number of iterations. We now move to the poof of Claim 2. Note that the Turing-optimal learner A is a PAC learner though A does not even require, as inputs. By the union bound, this means that with probability 1, it outputs a classifier with error at most as required by PAC learning. In this section we will give a complete proof of 1.