Timeline for proving the error bound for a hypothesis
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1, 2013 at 4:49 | vote | accept | seteropere | ||
| Sep 30, 2013 at 5:07 | answer | added | Shaull | timeline score: 5 | |
| Sep 29, 2013 at 20:00 | comment | added | seteropere | @Shaull The second. I am trying to prove that there is some $h$ returned by an ERM strategy with $err_D(h)>\epsilon$. | |
| Sep 29, 2013 at 19:57 | comment | added | Shaull | @seteropere There are two different things here: one is the (probabilistic) upper bound on the error, which you present here. The second is a lower bound, i.e. showing that $err_D(h)>\epsilon$ can actually occur, or a stronger result, stating that $Pr(err_D(h)>\epsilon)>t$ for some $t$. Which of the two are you trying to find a "non-probabilistic" proof for? | |
| Sep 29, 2013 at 19:42 | comment | added | seteropere | @Shaull just to get this straight: so the prove should not address the lower bound of its probability $Pr(err_D(h)>\epsilon)\leq k(1-\epsilon)^m$. I need to prove it in another way | |
| Sep 29, 2013 at 18:20 | comment | added | Shaull | Well, just saying that it happens is not very interesting, as it might be with probability 0 - just construct an example where one very bad hypothesis happens to match the sample. Proving that it happens with some higher probability is proving a lower bound on the learning algorithm, which is of interest. | |
| Sep 29, 2013 at 17:59 | comment | added | seteropere | @Shaull yes my ultimate goal is to prove this. however, all the sources I came through prove it by probabilities (probability of such thing happens). | |
| Sep 29, 2013 at 16:50 | comment | added | Shaull | I also don't understand what you are asking. Are you trying to prove that you might get $err_D(h)>\epsilon$? Clearly there are examples where this happens (even if the probability for it is very small). | |
| Sep 29, 2013 at 8:26 | comment | added | seteropere | @YuvalFilmus Sorry.I have edited the question. Here is a pointer courses.cs.washington.edu/courses/cse546/12wi/slides/… | |
| Sep 29, 2013 at 8:21 | history | edited | seteropere | CC BY-SA 3.0 | added 4 characters in body |
| Sep 29, 2013 at 8:13 | history | edited | seteropere | CC BY-SA 3.0 | tryng to make it more clear |
| Sep 29, 2013 at 7:54 | comment | added | Yuval Filmus | I can't understand the question. Can you explain it to non-experts? | |
| Sep 29, 2013 at 6:56 | history | asked | seteropere | CC BY-SA 3.0 |