Page 103 - Understanding Machine Learning

8.7 Exercises 85

halfspaces discussed in the previous exercise), then, unless NP = RP, there exists
no polynomial time proper PAC learning algorithm for H.
Hint: Assume you have an algorithm A that properly PAC learns a class H in
time polynomial in some class parameter n as well as in 1/
and 1/δ. Your
goal is to use that algorithm as a subroutine to contract an algorithm B for
solving the ERM H problem in random polynomial time. Given a training set,
m
S ∈ (X ×{±1} ), and some h ∈ H whose error on S is zero, apply the PAC
learning algorithm to the uniform distribution over S and run it so that with
probability ≥ 0.3 it finds a function h ∈ H that has error less than
= 1/|S| (with
respect to that uniform distribution). Show that the algorithm just described
satisfies the requirements for being a RP solver for ERM H .