- **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*)

Proof of Hoeffding's inequality is requiredRef: 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. |

Re: Proof of Hoeffding's inequality is requiredQuote:
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. |

Re: Proof of Hoeffding's inequality is requiredThanks 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 07:37 AM. |

Powered by vBulletin® Version 3.8.3

Copyright ©2000 - 2021, 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.