(a) What is the VC dimension of the class of 2-dimensional axis-aligned boxes? Provide a proof of your answer. This proof requires two parts: a proof that at least d points can be shattered, and a proof that no more than d points can be shattered for some d. (b) Let A be any algorithm that learns 2-dimensional axis-aligned boxes in the consistency model (suppose labels are correct, i.e., non-agnostic setting). Let D be a fixed, unknown distribution, let c be a fixed, unknown n-dimensional axis-aligned box, and let & be a fixed parameter in (0,1/2). Suppose A is given as input m points x1, x2, . . ., xm drawn i.i.d. from D and their corresponding labels c( x1), c( x2),, c( xm), and it outputs a function h. Recall that we have n = 2. Use the VC dimension that you derived in part (a) of this question. State a rough upper bound (big-O notation is ok) for the sample size m to achieve PAC-guarantees with parameters € and 8. How does this bound compare to the bound you derived in Part(b) of Question 4 in Assignment 2? (Don't worry about constants in your comparison.) In this problem, we consider the class of n-dimensional axis-aligned boxes. Each function c in this class is specified by a set of 2n values l1,..., l and u₁, ..., un in [0, 1], which defines an axis-aligned n-dimensional box. Given an n-dimensional input vector a, c(a) is defined to be 1 (or '+') if for every i = {1,...,n} the i'th coordinate of a lies in [,]. Otherwise, c(z) is defined to be 0 (or '-'). An example of a 2-dimensional axis-aligned box is shown in the figure below. 12 (0,0) 11 (1,1)

(a) What is the VC dimension of the class of 2-dimensional axis-aligned boxes? Provide a proof of your answer. This proof requires two parts: a proof that at least d points can be shattered, and a proof that no more than d points can be shattered for some d. (b) Let A be any algorithm that learns 2-dimensional axis-aligned boxes in the consistency model (suppose labels are correct, i.e., non-agnostic setting). Let D be a fixed, unknown distribution, let c be a fixed, unknown n-dimensional axis-aligned box, and let & be a fixed parameter in (0,1/2). Suppose A is given as input m points x1, x2, . . ., xm drawn i.i.d. from D and their corresponding labels c( x1), c( x2),, c( xm), and it outputs a function h. Recall that we have n = 2. Use the VC dimension that you derived in part (a) of this question. State a rough upper bound (big-O notation is ok) for the sample size m to achieve PAC-guarantees with parameters € and 8. How does this bound compare to the bound you derived in Part(b) of Question 4 in Assignment 2? (Don't worry about constants in your comparison.) In this problem, we consider the class of n-dimensional axis-aligned boxes. Each function c in this class is specified by a set of 2n values l1,..., l and u₁, ..., un in [0, 1], which defines an axis-aligned n-dimensional box. Given an n-dimensional input vector a, c(a) is defined to be 1 (or '+') if for every i = {1,...,n} the i'th coordinate of a lies in [,]. Otherwise, c(z) is defined to be 0 (or '-'). An example of a 2-dimensional axis-aligned box is shown in the figure below. 12 (0,0) 11 (1,1)