An infinite VC dimensional space vs using hierarchical subspaces of finite but growing VC dimensions

Question

I have the following scenario. I have a binary classification problem, whose underlying function is a step function. The probability distribution of feature vectors is a uniform over the domain.

Case 1: I have a classifier which fits the training samples perfectly, no matter what the size of the data. The space of functions $H$ has an infinite VC dimension. As the data points going to infinite, the hypothesized function converges pointwise to the underlying step function.

Case 2: Here I have divided the same hypothesis space into a number of hierarchical subspaces $H_1 \subset H_2 \subset H_3 \subset \dots \subset H_n$ ($n$ goes to infinity). The VC dimension of each of the spaces is finite and grows with $n$ to infinity. Now, given any data of $n$ points, I compute the minimum number of VC dimension required to fit the data exactly, say, $d_n$ and use that space $H_{d_n}$ as the hypothesis. Do the same as data size $n$ goes to infinity, at each $n$ using the hypothesis space that just enough VC dimension to fit the data. In this approach also, as the data size goes to infinity, the hypothesized function converges pointwise to the underlying step function.

Is the difference between these two approaches to the same problem? Is there any theoretical difference? Which method is any better than others, in some sense?

Answer 1

In the first case, the VC dimension of $H$ being infinite implies that $H$ is not (agnostic) PAC learnable (see p. 48 of Understanding Machine Learning: From Theory to Algorithms). So, in general, your classifier is not guaranteed to succeed.

In the second case, your division of $H$ implies that $H$ is nonuniformly learnable (chapter 7 of the cited book). This implies that you can get a generalization bound by using structural risk minimization.