LFD Book Forum What does it mean to "satisfy" Hoeffding's Inequality?
 Register FAQ Calendar Mark Forums Read

#1
04-16-2012, 07:20 AM
 gordonbr Junior Member Join Date: Apr 2012 Posts: 3
What does it mean to "satisfy" Hoeffding's Inequality?

I'm confused about the process of determining whether a particular random sample "satisfies" Hoeffding's inequality.

In particular, when we run some experiments and determine the average proportion of green marbles, we generate some averages for several values. Can't we say that all of these values satisfy Hoeffding's Inequality, since Hoeffding's Inequality only says that the probability of something bad happening (i.e., not tracking ) for a random sample is small? I would think that any satisfies this condition, regardless of how we determined the sample.

I suppose my question is: how does a particular value fail to satisfy an inequality that seems to be a blanket statement for all possible values?
#2
04-16-2012, 10:10 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: What does it mean to "satisfy" Hoeffding's Inequality?

Quote:
 Originally Posted by gordonbr I'm confused about the process of determining whether a particular random sample "satisfies" Hoeffding's inequality. In particular, when we run some experiments and determine the average proportion of green marbles, we generate some averages for several values. Can't we say that all of these values satisfy Hoeffding's Inequality, since Hoeffding's Inequality only says that the probability of something bad happening (i.e., not tracking ) for a random sample is small? I would think that any satisfies this condition, regardless of how we determined the sample. I suppose my question is: how does a particular value fail to satisfy an inequality that seems to be a blanket statement for all possible values?
If the expression "satisfies Hoeffding's inequality" is used for a particular , it is informal or figurative. It just says that this particular is within of . Hoeffding asserts that this is likely to be the case, hence the word "satisfies."

The formal statement would not involve an individual , but rather a full experiment, and it would be a statement that Hoeffding's inequalty holds under the conditions of such experiment. For instance, the multiple-bin experiment does not satisfy the basic Hoeffding inequality.
__________________
Where everyone thinks alike, no one thinks very much
#3
04-16-2012, 11:39 AM
 gordonbr Junior Member Join Date: Apr 2012 Posts: 3
Re: What does it mean to "satisfy" Hoeffding's Inequality?

Thanks, professor! That clears it up.
#4
01-14-2013, 10:26 AM
 ripande Senior Member Join Date: Jan 2013 Posts: 71
Re: What does it mean to "satisfy" Hoeffding's Inequality?

Is Hoeffding's Inequality true for every experiment and hypothesis ? Is it possible that P[Ein -Eout] for some hypothesis is not bounded by 2exp( -2e2N) ?
#5
01-14-2013, 10:37 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: What does it mean to "satisfy" Hoeffding's Inequality?

Quote:
 Originally Posted by ripande Is Hoeffding's Inequality true for every experiment and hypothesis ? Is it possible that P[Ein -Eout] for some hypothesis is not bounded by 2exp( -2e2N) ?
If you fix any hypothesis then run the experiment, the probability will always be bounded by that term.
__________________
Where everyone thinks alike, no one thinks very much
#6
01-15-2013, 11:37 AM
 ripande Senior Member Join Date: Jan 2013 Posts: 71
Re: What does it mean to "satisfy" Hoeffding's Inequality?

I am sorry, but I still dont get it. Let us say one person is tossing a fair coin 10 times and got all heads. Here one coin refers to one hypothesis correct ?, so that is fixed. N is also fixed to 10. Does this mean that this experiment would satisfy hoefding's inequality ?

I am confused by the statement that hoeffding's inequlity is universally true for fixed hypothesis and experiment.
#7
01-15-2013, 12:22 PM
 ripande Senior Member Join Date: Jan 2013 Posts: 71
Re: What does it mean to "satisfy" Hoeffding's Inequality?

Thinking on it more...does it mean that if the experiment involves multiple iterations of flipping the same coin 10 times then it will be bounded by hoeffding's inequality?
#8
01-15-2013, 01:56 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: What does it mean to "satisfy" Hoeffding's Inequality?

Quote:
 Originally Posted by ripande Thinking on it more...does it mean that if the experiment involves multiple iterations of flipping the same coin 10 times then it will be bounded by hoeffding's inequality?
If you are applying Hoeffding to the 10 flips, and you are considering multiple attempts at 10 flips, then we are in the "multiple bin" rather than single bin regime. You can apply the regular (single bin) Hoeffding to all the flips considered together (N would be multiple of 10 given your description).
__________________
Where everyone thinks alike, no one thinks very much

 Thread Tools Display Modes Linear 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 08:38 AM.