1. Suppose that a list contains the values 20 44 48 55 62 66 74 88 93 99 at index positions 0 through 9. Trace the values of the variables….

## show that ERMHnk is computationally hard for every k ≥ 3.

1. In this exercise, we present several classes for which finding an ERM classifier is computationally hard. First, we introduce the class of *n*-dimensional halfspaces, *HSn*, for a domain *X *= R*n*. This is the class of all functions of the form *h*w*,**b*(x) = sign(_w*,*x_+*b*)where w*,*x∈R*n*, _w*,*x_ is their inner product, and *b *∈R. See a detailed description in

2. Show that ERM*H *over the class *H*= *HSn *of linear predictors is computationally hard.More precisely, we consider the sequence of problems in which the dimension *n *grows linearly and the number of examples *m *is set to be some constant times *n*. *Hint*: You can prove the hardness by a reduction from the following problem: *Max FS: *Given a system of linear inequalities, *A*x *> *b with *A *∈ *Rm*×*n *and b∈R*m *(that is, a systemof *m *linear inequalities in *n *variables, x=(*x*1*, . . ., **xn *)), find a subsystem containing as many inequalities as possible that has a

solution (such a subsystem is called *feasible*). It has been shown (Sankaran 1993) that the problem Max FS is NP-hard. Show that any algorithm that finds an ERM*HSn *hypothesis for any training sample *S *∈ (R*n *×{+1*,*−1})*m *can be used to solve the Max FS problem of size *m**,**n*. *Hint*: Define a mapping that transforms linear inequalities in *n *variables into labeled points in R*n*, and a mapping that transforms vectors in R*n *to halfspaces, such that a vector w satisfies an inequality *q *if and only if the labeled point that corresponds to *q *is classified correctly by the halfspace corresponding to w. Conclude that the problem of empirical risk minimization for halfspaces in also NP-hard (that is, if it can be solved in time polynomial in the sample size, *m*, and the Euclidean dimension, *n*, then every problem in the class NP can be solved in polynomial time).

Q35;

1. Let *X *=R*n *and let *Hnk*be the class of all intersections of *k*-many linear halfspaces in R*n*. In this exercise, we wish to show that ERM*Hnk* is computationally hard for every *k *≥ 3. Precisely, we consider a sequence of problems where *k *≥ 3 is a constant and *n *grows linearly. The training set size, *m*, also grows linearly with *n*. Toward this goal, consider the *k*-coloring problem for graphs, defined as follows: Given a graph *G *= (*V**, **E*), and a number *k*, determine whether there exists a function *f *: *V *→{1*. . .**k*} so that for every (*u**,**v*) ∈ *E*, *f *(*u*) _= *f *(*v*). 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 *ERMHnk* : that is, to prove that if

there is an algorithm that solves the *ERMHnk *problem in time polynomial in *k*, *n*,* *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 *. . .**vn *} be the vertices in *V *. Construct a sample *S*(*G*) ∈ (R*n *×{±1})*m*, where *m *= |*V*| + |*E*|, as follows:* *_ For every *vi *∈ *V*, construct an instance e*i *with a negative label.* *_ For every edge (*vi **,**v j *) ∈ *E*, construct an instance (e*i *+e*j *)*/*2 with a positive

label.