Understanding Machine Learning: From Theory to Algorithms

8.7 Exercises 113

larger than RP. In particular, it is believed that NP-hard problems cannot be
solved by a randomized polynomial time algorithm.

• Show that if a classHisproperlyPAC learnable by a polynomial time
  algorithm, then the ERMHproblem is in the class RP. In particular, this
  implies that whenever the ERMHproblem is NP-hard (for example, the
  class of intersections of halfspaces discussed in the previous exercise),
  then, unless NP = RP, there exists no polynomial time proper PAC
  learning algorithm forH.
  Hint: Assume you have an algorithmA that properly PAC learns a
  classHin time polynomial in some class parameternas well as in 1/
  and 1/δ. Your goal is to use that algorithm as a subroutine to contract
  an algorithmBfor solving the ERMHproblem in random polynomial
  time. Given a training set,S∈(X ×{± 1 }m), and someh∈ Hwhose
  error onSis zero, apply the PAC learning algorithm to the uniform
  distribution overSand run it so that with probability≥ 0 .3 it finds a
  functionh∈Hthat 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 ERMH.