Timeline for $L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2020 at 18:12 | history | edited | Clement C. | CC BY-SA 4.0 |
edited body
|
| Oct 11, 2020 at 17:33 | comment | added | Jack M | That is a remarkable lemma. By definition if $H$ is not PAC learnable, there must be some degree of reliability $(\epsilon, \delta)$ small enough that for any $n$, the algorithm fails to be that reliable on samples of size $n$. Your version of the NFL theorem implies that $(\epsilon, \delta)$, if it exists, can always be chosen to be $(1/8, 1/7)$. That's as if there were some "magic number" like $1/8$ such that any sequence which isn't eventually within $1/8$ of a number $L$ does not converge to $L$, or equivalently, any sequence which is eventually within $1/8$ of $L$ does converge to $L$. | |
| Oct 29, 2017 at 15:04 | vote | accept | raja.damanik | ||
| Oct 25, 2017 at 4:36 | history | answered | Clement C. | CC BY-SA 3.0 |