LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 1 - The Learning Problem (http://book.caltech.edu/bookforum/forumdisplay.php?f=108)
-   -   Chapter 1 - Exercise 1.9 (http://book.caltech.edu/bookforum/showthread.php?t=4412)

 goldsj3 09-11-2013 09:31 AM

Chapter 1 - Exercise 1.9

Based on the marbles example, I understand that u is the probability of choosing a red marble from the bin of marbles and v is the fraction of red marbles in the sample of chosen marbles. And I think that the LHS of the Hoeffding Inequality represents the probability of v deviating from u being greater than the error bar epsilon. Now, I am not sure how I should choose an epsilon to evaluate this probability and where I should begin. Can someone point me in the right direction?

 magdon 09-11-2013 11:31 AM

Re: Chapter 1 - Exercise 1.9

If and , it implies that (any number slightly less than 0.8). By the implication bound,

By looking at the RHS, one can identify for applying the Hoeffding bound.

 eshmrt 09-15-2015 01:51 PM

Re: Chapter 1 - Exercise 1.9

Since we're only looking at epsilon applied in one direction, meaning that we're only interested in nu being mu - 0.8 and not mu + 0.8, should we drop the leading 2 from the bound calculation? I'm not sure if I'm interpreting this bound correctly or simply overthinking things.

 magdon 09-21-2015 03:27 PM

Re: Chapter 1 - Exercise 1.9

You are right. If al you want is the "one sided deviation", you could drop the factor of 2. However keeping the factor of 2 is a worse but still valid bound.

Quote:
 Originally Posted by eshmrt (Post 12036) Since we're only looking at epsilon applied in one direction, meaning that we're only interested in nu being mu - 0.8 and not mu + 0.8, should we drop the leading 2 from the bound calculation? I'm not sure if I'm interpreting this bound correctly or simply overthinking things.

 henry2015 11-05-2017 06:17 AM

Re: Chapter 1 - Exercise 1.9

Quote:
 Originally Posted by magdon (Post 11480) If and , it implies that (any number slightly less than 0.8). By the implication bound, By looking at the RHS, one can identify for applying the Hoeffding bound.
Hi, I am a bit confused.

I thought when it says , it means because smallest probably is 0; hence, ....I am sure I miss something.

Any pointer?

Thanks!

 mike7 09-11-2018 02:03 PM

Re: Chapter 1 - Exercise 1.9

Quote:
 Originally Posted by magdon (Post 11480) If and , it implies that (any number slightly less than 0.8). By the implication bound, By looking at the RHS, one can identify for applying the Hoeffding bound.
If I am understanding the implications of this correctly, is too large within the Hoeffding bound, correct? One would need to select some , perhaps arbitrarily?

 All times are GMT -7. The time now is 08:16 PM.