1
$\begingroup$

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

enter image description here

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – zyxue Jan 30 '18 at 16:59

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.