View Single Post
Old 04-12-2013, 04:19 PM
grozhd grozhd is offline
Junior Member
Join Date: Apr 2013
Posts: 4
Default Re: How does Hoeffding's inequality work if we have a fixed sample?

Originally Posted by Rahul Sinha View Post
Let us try and decode the experiment: X is not the whole input space but just a fraction of it. card(X) = 10000 and not infinity. Usually, we will neither have the time nor the energy to flip a coin infinite number of times.
I don't understand why do you suppose that whole input space should be infinite and neither do I understand how this coin tossing relates to learning In particular what is X and what is the target function.

Yes, you did memorize the mu but if N is large, it can not be too bad! That's the key
I beleive it's not true. For example no matter how much data you give me I can always come up with a polynomial of degree equal to the number of training examples which is perfect in sample. Suppose you gave me 20 points (x, y) from linear function and I generate a polynomial of degree 20. I think it will be really bad out of sample.

Also, I found a question similar to mine and posted a reply here.
Reply With Quote