Editing Statistical learning theory (section)

==Bounding empirical risk==
Consider a binary classifier <math>f: \mathcal{X} \to \{0, 1\}</math>. We can apply [[Hoeffding's inequality]] to bound the probability that the empirical risk deviates from the true risk to be a [[Sub-Gaussian distribution]]. 
<math display="block">\mathbb{P} (|\hat{R} (f) - R(f)| \geq \epsilon) \leq 2e^{- 2 n \epsilon^2}</math>
But generally, when we do empirical risk minimization, we are not given a classifier; we must choose it. Therefore, a more useful result is to bound the probability of the supremum of the difference over the whole class. 
<math display="block">\mathbb{P} \bigg( \sup_{f \in \mathcal{F}} | \hat{R} (f) - R(f) | \geq \epsilon \bigg) \leq 2 S(\mathcal{F}, n) e^{-n \epsilon^2 / 8} \approx n^d e^{-n \epsilon^2 / 8}</math>
where <math>S(\mathcal{F},n)</math> is the [[shattering number]] and <math>n</math> is the number of samples in your dataset. The exponential term comes from Hoeffding but there is an extra cost of taking the supremum over the whole class, which is the shattering number.