3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are you saying that their Lemma 3.5 is problematic? The step you mentioned is no more than a direct application of Lemma 3.5. $\endgroup$
    – Henry.L
    May 2, 2017 at 2:37
  • $\begingroup$ Lemma 3.5 is fine -- there h is fixed. It becomes problematic when it is applied in a context where the bound needs to be uniform over all $h$ in $\mathcal H$. $\endgroup$
    – axk
    May 2, 2017 at 2:40
  • 1
    $\begingroup$ Suppose the attainment of supremum occurs at $h_{0}\in\mathcal{H}$,$Pr\left[sup_{h\in\mathcal{H}}\left|\widehat{E}(h,S_{1})-\widehat{E}(h,S_{2})\right|>\frac{\epsilon}{2}\right]=Pr\left[\left|\widehat{E}(h_{0},S_{1})-\widehat{E}(h_{0},S_{2})\right|>\frac{\epsilon}{2}\right]\leq_{1-2\delta}Pr\left[\left|\widehat{E}(h_0',S'_{1})-\widehat{E}(h_0',S'_{2})\right|>\rho(h_{0})\right]\leq Pr\left[sup_{h'\in\mathcal{H}}\left|\widehat{E}(h',S'_{1})-\widehat{E}(h',S'_{2})\right|>\rho(h_{0})\right]$ is what they argued. $\endgroup$
    – Henry.L
    May 2, 2017 at 3:10

1 Answer 1

2
$\begingroup$

No, they just used sloppy notations. They omitted what we called "attainment argument".

Suppose the attainment of supremum occurs at $h_{0}\in\mathcal{H}$,$$Pr\left[\sup_{h\in\mathcal{H}}\left|\widehat{E}(h,S_{1})-\widehat{E}(h,S_{2})\right|>\frac{\epsilon}{2}\right]=\operatorname{Pr}\left[\left|\widehat{E}(h_{0},S_{1})-\widehat{E}(h_{0},S_{2})\right|>\frac{\epsilon}{2}\right]\leq_{1-2\delta}\text{(by Lemma 3.5)}\operatorname{Pr}\left[\left|\widehat{E}(h_0',S'_{1})-\widehat{E}(h_0',S'_{2})\right|>\rho(h_{0})\right]\\\leq \operatorname{Pr}\left[\sup_{h'\in\mathcal{H}}\left|\widehat{E}(h',S'_{1})-\widehat{E}(h',S'_{2})\right|>\rho(h_{0})\right]$$ is what they argued.

$\endgroup$
9
  • $\begingroup$ Should that be $\mathcal H'$ in the last line? $\endgroup$
    – axk
    May 2, 2017 at 3:35
  • 1
    $\begingroup$ Yes, but we could also regard the projected image as a subspace in $\mathcal{H}$. @axk $\endgroup$
    – Henry.L
    May 2, 2017 at 3:38
  • $\begingroup$ Okay, this makes sense now. But with this argument then in their final bound eq. (2) the $h$ in $\mu_k$ should be the $h_0$ and not the same $h$ as in the empirical average? $\endgroup$
    – axk
    May 2, 2017 at 3:40
  • 1
    $\begingroup$ @axk I believe so unless they assumed what you mentioned in OP. $\endgroup$
    – Henry.L
    May 2, 2017 at 3:41
  • $\begingroup$ Still I think they make a hidden assumption here, because $h_0$ depends on $S_1,S_2$ -- so $\rho(h_0)$ is non-random only if they assume so. The last line on the page after eq.(3) only makes sense it $\rho$ is a constant. $\endgroup$
    – axk
    Jul 19, 2017 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.