Clarification on margin bound uniform w.r.t. the margin parameter

Question

Theorem 4.5. in the book "Foundations of Machine Learning" by Mohri et al: http://prlab.tudelft.nl/sites/default/files/Foundations_of_Machine_Learning.pdf derives a generalization bound to hold uniformly for all margin parameters $\rho$ of the margin-loss.

My question is, why is this necessary? -- what could go wrong if we choose $\rho$ after seeing the sample, by minimizing the bound in Theorem 4.4. (rather than that bound in Theorem 4.5)?

I understand that the sample could 'mislead' us in choosing $\rho$, but on the other hand, the risk of the margin loss (that both of these theorems upper bound) is always an upper bound on the risk (of the 0-1 loss) on the l.h.s. of these bounds, i.e. for any value f $\rho\in(0,1)$. Therefore I would have thought that even if the sample misleads us to choose a too large or a too small value for $\rho$ the upper bound of Theorem 4.4. still holds. What am I missing?

Answer 1

For every margin parameter, the empirical margin loss upper bounds the empirical 0-1 loss. However, say you want to bound the true 0-1 loss. In order to similarly bound it by the true margin loss, you need to tie the empirical and true margin losses, which (due to the optimization over margin parameters) is presently achieved through a uniform generalization bound.