LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 1 - The Learning Problem (http://book.caltech.edu/bookforum/forumdisplay.php?f=108)
-   -   Proof of Hoeffding's inequality is required (http://book.caltech.edu/bookforum/showthread.php?t=2960)

eakarahan 11-20-2012 09:11 AM

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.

htlin 11-20-2012 02:46 PM

Re: Proof of Hoeffding's inequality is required
 
Quote:

Originally Posted by eakarahan (Post 7404)
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.

You can refer to homework e/2 of my current class

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 z_i or in the learning context [ y_n \neq h(\mathbf{x}_n) ]) to be "fixed" before starting the proof, and of course z_i needs to come independently from the distribution. If a different h is used, P(z) is different, and if many different h are considered altogether, we need to be cautious about the independence assumption. Hope this helps.

eakarahan 11-21-2012 04:49 AM

Re: Proof of Hoeffding's inequality is required
 
It seems a proof requires very strong probability background. But now I know at least that [ y_n \neq h(\mathbf{x}_n) ] 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.

donthireddy 01-01-2013 11:38 AM

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 2-3 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.


All times are GMT -7. The time now is 10:00 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.