Is Learning Feasible?

Properties

We have a dataset with some data D. If we can use the data to learn something outside of D, then learning is feasible.

Hoeffding Inequality $$ Pr(|E_{in} - E_{out}| \geq \epsilon) \leq 2e^{-2n\epsilon^2} $$