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?

  • 1
    $\begingroup$ If the domain of $H$ continuous, you can't construct a countable order, as we know the $\mathbb{R}$ is not countable! $\endgroup$
    – OmG
    Commented Apr 16, 2020 at 13:12
  • $\begingroup$ @OmG : $H$ consists of certain class of functions defined on a $m$ dimensional Torus. The functions are of the form $\mathbb{T}^m \to \mathbb{R}$ with some other properties. There can be countable ordered subspaces. $\endgroup$
    – Rajesh D
    Commented Apr 16, 2020 at 13:16
  • $\begingroup$ You need to clear this part by a concrete example. $\endgroup$
    – OmG
    Commented Apr 16, 2020 at 13:27

1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .