View Single Post
Old 04-04-2013, 12:51 AM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Relation between feasibility of learning and Hoeffding's Inequality.

Originally Posted by jlaurentum View Post

I understand that learning is picking out a function from a candidate set of functions that most closely resembles the target function. The feasibility of learning would be related to how close this resemblance is.

I understand also that Hoeffding's Inequality is an upper bound to the probability that the in-sample error rate deviates significantly from the real error rate. In the end, this upper bound simply implies that given a large enough sample, estimating the real error rate is feasible.

Is there any misconception in anything here so far?

So my question is: what does the Hoeffding inequality say about the feasibility of learning? Shouldn't it be feasibility of verifying hypothesis?

Your understanding is correct. The contrast between learning and verification that you allude to is precisely why the union bound was used in Lecture 2. The notion of the feasibility of learning will be further discussed next week in Lecture 4, where the question is split into two parts. Stayed tuned!
Where everyone thinks alike, no one thinks very much
Reply With Quote