# uniform convergence and model selection question

I am working on the Question 1(c) of problem set 3 from cs229. A screenshot of the question is

I am not sure how this formula came to be

\begin{align*} \left|\epsilon(\hat h_j) - \hat \epsilon_{S_{train}}(h_j^*) \right| \le \sqrt{\frac{2}{(1 - \beta) m} \log {\frac{4 \left|\mathcal{H}_j \right|}{\delta}}} \end{align*}

A solution is written at https://see.stanford.edu/materials/aimlcs229/ps3_solution.pdf, but I still don't quite get the (c) part. There seems to be also a typo as it confuses $\beta$ with $\gamma$.

The corresponding class note is https://see.stanford.edu/materials/aimlcs229/cs229-notes4.pdf

OK, you have a few different questions:

I am not sure how this formula came to be.

It's given in the question. It looks like they derived it by applying the bound on the top of pp. 7 of the notes.

I still don't quite get the (c) part.

There are 2 bounds (found in part a, and given for part c), each guaranteed with probability of $\geq 1-\frac{\delta}{2}$. If both bounds apply at the same time (i.e probability of "x" AND "y" in this case) then the joint probability is $\geq (1-\frac{\delta}{2})(1-\frac{\delta}{2}) > 1-\delta$.

And they do apply them at the same time, giving the bound they want to show.

There seems to be also a typo as it confuses $\beta$ with $\gamma$.

I agree with you there.

• Thanks! As for the 1st question. I am aware that it's given in the question, but I don't see how it's derived obviously. Do you mind posting your derivation? – zyxue Jan 30 '18 at 16:59