
#1




Proof of Hoeffding's inequality is required
Ref: Page 22, Chp 1, last paragraph.
What are the assumptions that are needed to prove Hoeffding's inequality that no longer hold if we are allowed to change h after we generate the data set? Please give a proof of Hoeffding inequality in this context, explicitly showing these assumptions. 
#2




Re: Proof of Hoeffding's inequality is required
Quote:
http://www.csie.ntu.edu.tw/~htlin/co...oc/hw0_5_e.pdf for guided steps of the proof. The proof needs the distribution that generates the random variable (in the problem or in the learning context ) to be "fixed" before starting the proof, and of course needs to come independently from the distribution. If a different is used, is different, and if many different are considered altogether, we need to be cautious about the independence assumption. Hope this helps.
__________________
When one teaches, two learn. 
#3




Re: Proof of Hoeffding's inequality is required
It seems a proof requires very strong probability background. But now I know at least that to be "fixed" before starting the proof. I will defer the proof until I will reach the required math level, and will refresh my probability knowledge reserving an eye on the guidelines you send. Before I write this reply, I've reviewed some probability books that I've possess. I Could find the Markov's inequality, and Chernoff bound in some of them. I could not find Hoeffding's bound in any of them. Thus, I especially interested if you have a probability book (tailored for ML) you can recommend. The main difficulty in ML is the level of required math and I think it is never enough.

#4




Re: Proof of Hoeffding's inequality is required
Thanks to eakarahan for asking, and to Prof. Lin for designing a great exercise.
I think I have managed to complete the proof. Most of the steps pushed my math skills to the limit. Took 23 hours spread over a couple of days. The first one made me think harder about what a probability distribution is. A fair bit of algebraic manipulation in the other steps, some optimization in step 4. I needed to think of using the Taylor expansion for one of the steps. Overall, it was excellent exercise for the brain. 
Tags 
hoeffding's inequality, proof 
Thread Tools  
Display Modes  

