LFD Book Forum Proof of Hoeffding's inequality is required
 Register FAQ Calendar Mark Forums Read

#1
11-20-2012, 08:11 AM
 eakarahan Junior Member Join Date: Nov 2012 Posts: 3
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
11-20-2012, 01:46 PM
 htlin NTU Join Date: Aug 2009 Location: Taipei, Taiwan Posts: 601
Re: Proof of Hoeffding's inequality is required

Quote:
 Originally Posted by eakarahan 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 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
11-21-2012, 03:49 AM
 eakarahan Junior Member Join Date: Nov 2012 Posts: 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
01-01-2013, 10:38 AM
 donthireddy Junior Member Join Date: Jul 2012 Location: USA Posts: 1
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.

 Tags hoeffding's inequality, proof

 Thread Tools Display Modes Hybrid Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 05:25 AM.