Page 102 - Understanding Machine Learning

The Runtime of Learning
84

The k-coloring problem is known to be NP-hard for every k ≥ 3 (Karp 1972).
We wish to reduce the k-coloring problem to ERM H : that is, to prove that if
n
k
there is an algorithm that solves the ERM H problem in time polynomial in k, n,
n
k
and the sample size m, then there is a polynomial time algorithm for the graph
k-coloring problem.
Given a graph G = (V, E), let {v 1 ...v n } be the vertices in V . Construct a sample
n
m
S(G) ∈ (R ×{±1}) ,where m =|V|+|E|, as follows:
For every v i ∈ V, construct an instance e i with a negative label.
For every edge (v i ,v j ) ∈ E, construct an instance (e i + e j )/2 with a positive
label.
n
1. Prove that if there exists some h ∈ H that has zero error over S(G)then G is
k
k-colorable.
k n
Hint: Let h = j=1 h j be an ERM classifier in H k over S. Define a
coloring of V by setting f (v i ) to be the minimal j such that h j (e i ) =
−1. Use the fact that halfspaces are convex sets to show that it cannot
be true that two vertices that are connected by an edge have the same
color.
n
2. Prove that if G is k-colorable then there exists some h ∈ H that has zero error
k
over S(G).
Hint: Given a coloring f of the vertices of G, we should come up
with k hyperplanes, h 1 ...h k whose intersection is a perfect classifier for
S(G). Let b = 0.6 for all of these hyperplanes and, for t ≤ k let the
i’th weight of the t’th hyperplane, w t,i ,be −1if f (v i ) = t and 0
otherwise.
3. On the basis of the preceding, prove that for any k ≥ 3, the ERM H problem
n
k
is NP-hard.
8.4 In this exercise we show that hardness of solving the ERM problem is equivalent to
hardness of proper PAC learning. Recall that by “properness” of the algorithm we
mean that it must output a hypothesis from the hypothesis class. To formalize this
statement, we first need the following definition.
Definition 8.2. The complexity class Randomized Polynomial (RP) time is the class
of all decision problems (that is, problems in which on any instance one has to find
out whether the answer is YES or NO) for which there exists a probabilistic algo-
rithm (namely, the algorithm is allowed to flip random coins while it is running) with
these properties:
On any input instance the algorithm runs in polynomial time in the input size.
If the correct answer is NO, the algorithm must return NO.
If the correct answer is YES, the algorithm returns YES with probability a ≥ 1/2
and returns NO with probability 1 − a. 1

Clearly the class RP contains the class P. It is also known that RP is contained in the
class NP. It is not known whether any equality holds among these three complexity
classes, but it is widely believed that NP is strictly 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 class H is properly PAC learnable by a polynomial time algorithm,
then the ERM H problem is in the class RP. In particular, this implies that when-
ever the ERM H problem is NP-hard (for example, the class of intersections of

1 The constant 1/2 in the definition can be replaced by any constant in (0,1).