View Single Post
#1
04-11-2013, 05:47 PM
 grozhd Junior Member Join Date: Apr 2013 Posts: 4
How does Hoeffding's inequality work if we have a fixed sample?

As far as I understand Hoeffding's inequality tells us about the probability of "big" differences between a random variable value (mean of N independent r.v.'s) and a number (it's expected value).

Since it is a probabilistic inequality it means that if we try to do the expirement we will get this "big" difference only with certain limited probability. And "doing the experiment" assumes that we have a probability space X with a probability function P, then some outcome x from X happens, our random variables have some value on this x.

But when we are talking about learning we have a fixed data set so it seems to me that we don't observe a new outcome x each time, but we use one fixed which corresponds to our learning data set. And as we go from first hypothesis to second we can't use Hoeffding's inequality no more unless we select another random sample. For example is sample is finite and I have big hypothesis set I will easily go from one hypothesis to another and find one which is equal to target function on that sample. But as professor said in first lecture I didn't learn anything, I just memorized the data. But in lecture 2 it seems that we do the same and we are saying that inequality should work which is obviously not true for my example.

I know that I may have stated it fuzzily but that's because I don't actually understand the formalism here: what is our probability space, what is P, what are the random variables, - so that's why I can't formulate my question precisely. But I have a feeling that using this same data set somehow violates the probabilistic picture.

So, if anyone could clarify that it would be great, thanks in advance.