We note that the training data size \(N\)  in Equation (REF ) scales as \(1 / \epsilon \)  rather than \(1 / \epsilon ^2\) , an improvement over the standard scaling typically encountered in
statistical learning theory [1]}, [2]}.
The \(1 / \epsilon ^2\)  comes naturally when we sample over the different inputs \(x_i\)  and apply a concentration inequality on the ideal training error \(\frac{1}{N} \sum _{i=1}^N |f(x_i) - f_{\operatorname{{\mathcal {E}}}}(x_i)|^2\)  to guarantee an \(\mathcal {O}(\epsilon )\)  statistical fluctuation around the prediction error \(\operatornamewithlimits{{\mathbb {E}}}_{x \sim \operatorname{{\mathcal {D}}}} |f(x) - f_{\operatorname{{\mathcal {E}}}}(x)|^2\) .
The main reason for the improved scaling is that any function \(f\)  with a small prediction error \(\operatornamewithlimits{{\mathbb {E}}}_{x \sim \mathcal {D}} |f(x) - f_{\operatorname{{\mathcal {E}}}}(x)|^2 \le 4 \epsilon \)  also has a small variance (e.g., a highly biased coin that almost always come out heads has a variance close to zero, which is much smaller than for an unbiased coin), so we need only \(N=\mathcal {O}(1/\epsilon )\)  to achieve \(\mathcal {O}(\epsilon )\)  statistical fluctuations. Furthermore, by examining Equation (REF ), we see that if function \(f\)  has a large prediction error then the statistical fluctuations in the training data may also be large.
This is a price we pay to avoid a training set with size \(N\)  scaling as \(1/\epsilon ^2\) .
The increased statistical fluctuations for a function \(f\)  with a large prediction error are not problematic, because the statistical fluctuation are still smaller than the prediction error in that case.
We find that functions with small prediction error have small ideal training error, while functions with large prediction error have large ideal training error, which is adequate for our purposes.
