"Philosophical" data contamination question I'm going through Yaser Abu-Mostafa's Learning from Data course, and I'm having some trouble getting my head around data contaimination.
So we know stuff like VC-analysis can give us some gaurentee that hypotheses in a set $\mathcal{H}$ will generalize, but the point was made that $\mathcal{H}$ must be chosen without examining the data. Intuitively this makes perfect sense. Eg, if I look at my data, notice some random 17th order polynomial $p$ fits it, and choose $\mathcal{H} = \{p\}$, we'd have very strong generalization gaurentees even without something more involved like VC-analysis. But clearly this isn't really going to generalize.
I'm just wondering where in the argument for generalization this is happening though. Ie, where in VC-analysis arguments do we assume that $\mathcal{H}$ was chosen without looking at our data?
 A: One of the purposes of VC analysis is to estimate the generalization error.
Suppose the variance of the noise in your data is $\delta^2$, then the expected in-sample error (training error) is $\delta^2 (1- \frac {1+d}{N})$, and the out-of-sample error (validation error) is $\delta^2 (1+\frac {1+d}{N})$, where $d$ is the VC dimension, and $N$ is your sample number.
In your example it is correct that you may have very strong generalization gaurentee, but it is also very possible you suffer from overfitting.
Note that the VC dimension in 2D space is 3, but when you look at the data during fitting, you may notice that some 17-th order polynomial items better fits the data, then you will implement a non-linear transform in order to map the data in $X$ space into higher space $Z$. Now the VC dimension $\hat d$ is generally larger than $d$ (both measured in $X$ space). From the formula shown above, you may have a better training accuracy. However, if your sample size is not large enough, your out-of-sample error will become huge (overfitting).
It can be said that when you choose 17th-order because you know that the target is a 17th-order polynomial. On the other hand, you choose 2nd order because you are aware of the number of points available in the training set, for example let's say it is 15. Choosing a 2nd-order polynomial provides three parameters, such that the ratio of points to degrees of freedom is 5:1, which is less than the general rule of thumb $N \geq 10d_{VC}$. But in fact you don't choose 2nd order because you feel like a simple line cannot fit the 'observed' 17th-order polynomial. In other words, you are trying to match the data resources rather than the target complexity.  
One possible method that you choose the model without looking at data is to do several fittings by gradually increasing the order (2nd order, 3rd order, ...17th order), and compare the out-of-sample error of them. If the out-of-sample error for the 17th order is smaller than the 2nd order, it indicates that your complicated model does not overfit, otherwise the complicated model may overfit by just fitting the noise.
