This is an ICML02 paper by Garg, Har-Peled & Roth: http://sarielhp.org/p/01/bounds/bounds.pdf
The equation after eq. (3) is the well-known symmetrization trick for $\sup_{h\in {\mathcal H}} |E(h)-\hat{E}(h)|$ using a ghost sample, and holds for all $\epsilon>0$. The notation is this: ${\mathcal H}$ is a function class, $E[h]$ is the generalization error of $h$, and $\hat{E}[\cdot]$ is empirical error on a training set. $\epsilon>0$ is a fixed small positive constant.
Now, in the next equation they chose to replace $\epsilon$ by $\rho$ --- but the problem is, this $\rho$ is a function of $h$ and of the training sample $S$, (through the expression of $\epsilon_1(S,\delta)$ on the top of the previous page, which depends on $\nu$, which depends on $h$). In consequence, in the probability on the r.h.s. now we have an inequality that has $\sup_h$ on its l.h.s. but $\rho=\rho(h,S)$ on its r.h.s.
Is this faulty or am I missing something?
First I thought it's just sloppy notation -- if the $\rho$ did not depend on the training sample then one could replace it with a constant $c$, restrict the function class $\mathcal H$ to have $\rho(h)<c$, and do Structural Risk Minimization over values of $c$. But since $\rho$ also depends on $S$ this is not workable as we cannot have $\mathcal H$ defined to depend on $S$. It seems to me that the only fix would be to restrict $\mathcal H$ to have $\rho(h,S)<c$ $\forall S$ of size $N$? -- that would be very strong and impractical. Any thoughts would be much appreciated.
