I was reading Andrew Ng's notes and on page 6 he mentions (uniform convergence):

$$Pr[\forall h \in \mathcal{H}_{finite}|\epsilon(h_i)-\hat{\epsilon}(h_j)| \leq \gamma] \geq 1-2ke^{-2\gamma^2m}$$

where $\hat\epsilon(h_i) = \frac{1}{m}\sum^{m}_{j=1}Z_j$ and $Z_{j}$ is a drawn example ${(X_i, Y_i)}$ and $\epsilon(h)$ is generalization/true error of the current h. He says:

Given $\gamma$ and some $\delta> 0$, how large must m be before we can guarantee that with probability at least $1 − \delta$, training error will be within $\gamma$ of generalization error? By setting $\delta = 2\gamma e^{−2\gamma^2m}$ and solving for m, [you should convince yourself this is the right thing to do!]

I guess what I am unsure about is that part where he says we should be convinced that "its the correct thing to do." Can someone explain to me why thats the correct thing to do? I guess I don't really understand the reasoning on how to get the sample complexity. Why is it that if we set to $\delta$ and then rearrange terms, then that is exactly the minimum number of samples in order to achieve a certain level of performance.

I do understand that if you set $\delta = 2\gamma e^{−2\gamma^2m}$ by algebra you get:

$$m = \frac{1}{2\gamma^2}\log{\frac{2k}{\delta}}$$

However, I do not understand how or why it becomes:

$$m \geq \frac{1}{2\gamma^2}\log{\frac{2k}{\delta}}$$

How does the equality becomes an inequality? i.e. I understand the algebra, but not the motivation for such algebra and its relation the sample complexity and generalization guarantees.


If $δ=2k e^{−2γ^2m}$ (you made a small typo), $\mathrm P[ |ϵ(h_i)−\hat ϵ(h_j)|≤γ] ≥1−δ$, as desired ("we can guarantee that with probability at least 1−δ"). If $m' > \frac{1}{2γ^2} \log\frac{2k}{δ}$, then $δ' \equiv 2k e^{−2γ^2m'} < δ$, so the probability is even closer to unity (the concentration bound is tighter).

  • $\begingroup$ Hello @emre can you please guide me that whats the difference between sample complexiy and uniform convergence. both seems same in this document $\endgroup$
    – A.B
    Oct 6 '18 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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