LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 1 (http://book.caltech.edu/bookforum/forumdisplay.php?f=130)
-   -   Satisfying Hoeffding's inequality (http://book.caltech.edu/bookforum/showthread.php?t=4415)

diado 09-13-2013 11:51 PM
Satisfying Hoeffding's inequality
 
I've read the thread here, but still being confused
After using the union bound, we get the sum of individual terms and apply Hoeffding's inequality to each of them. Why is it valid? Aren't they still the multiple bins cases? It seems to me that they transfrom from multiple bins to single bin after using the union bound, but I don't know why.

Thanks!

yaser 09-14-2013 08:28 PM
Re: Satisfying Hoeffding's inequality
 
Quote:
Originally Posted by diado (Post 11485)
I've read the thread here, but still being confused
After using the union bound, we get the sum of individual terms and apply Hoeffding's inequality to each of them. Why is it valid? Aren't they still the multiple bins cases? It seems to me that they transfrom from multiple bins to single bin after using the union bound, but I don't know why.

Thanks!
Each term involves one fixed bin (hypothesis), so Hoeffding applies to it by itself, irrespective of what happens to the others. What the union bound does is to get the answer for the multiple bins if you know what happens to each bin by itself.


All times are GMT -7. The time now is 11:04 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.