Answers.Body: <p>Let <span class="math-container">$\varepsilon$</span> in (17) is equal to <span class="math-container">$\sqrt{\frac{4}{n}\left(\log{(2\mathsf{N}(\mathcal{F},n))}-\log{\delta}\right)}$</span>. We have:</p>
  
  <p><span class="math-container">$$
  P\left(\sup_{f\in\mathcal{F}}|R(f)-R_{emp}(f)| &gt; \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant 
  2\mathcal{N}(\mathcal{F},n) e^{\frac{-n}{4}\left(\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)\right)} = 
  2\mathcal{N}(\mathcal{F},n) e^{\log{\delta} - \log{(2\mathcal{N}(\mathcal{F},n))}}
  $$</span></p>
  
  <p>As we know that <span class="math-container">$e^{\log{n}} = n$</span> (suppose that base of <span class="math-container">$\log$</span> here is <span class="math-container">$e$</span>), we can write:</p>
  
  <p><span class="math-container">$$
  P\left(\sup_{f\in\mathcal{F}}|R(f)-R_{emp}(f)| &gt; \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant 
  2\mathcal{N}(\mathcal{F},n) \left(\frac{\delta}{2\mathcal{N}(\mathcal{F},n)}\right)
  $$</span></p>
  
  <p>Hence:</p>
  
  <p><span class="math-container">$$
  P\left(\sup_{f\in\mathcal{F}}|R(f)-R_{emp}(f)| &gt; \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant \delta
  $$</span>
  As we know that if we have <span class="math-container">$P(x &gt; a) \leqslant c$</span>, we can conlude that <span class="math-container">$P( x&lt;a) \geqslant 1-c$</span>, we will have:</p>
  
  <p><span class="math-container">$$
  P\left(\sup_{f\in\mathcal{F}}|R(f)-R_{emp}(f)| &lt; \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \geqslant 1- \delta
  $$</span></p>
  
  <p>Now, as this inequality is true for supremum of set <span class="math-container">$\mathcal{F}$</span> and <span class="math-container">$R(f) -R_{emp}(f) \leqslant \varepsilon$</span> is subset of  <span class="math-container">$|R(f) -R_{emp}(f)| \leqslant \varepsilon$</span> (in terms of probability state space), we can say the following inequality is correct for any function <span class="math-container">$f$</span> with at least probability of <span class="math-container">$1-\delta$</span>:
  <span class="math-container">$$
  R(f) \leqslant R_{emp}(f) + \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}
  $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-14T20:12:18.767Z
Answers.Text: The only part that is not clear and obvious is why you say that $R(f) -R_{emp}(f) \geqslant 0$ is a subset of $|R(f) -R_{emp}(f)| \geqslant 0$, i.e. you're saying that something greater or equal to zero (a number) is a _subset_ of something else that is greater or equal to zero. Maybe you can clarify this part.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-14T18:59:38.600Z
Answers.LastActivityDate: 2020-04-14T23:31:16.180Z
Answers.LastEditDate: 2020-04-14T23:31:16.180Z
Answers.UserDisplayName: OmG
Body: <p>I am new in the field of Machine Learning so I wanted to start of by reading more about mathematics and history behind it.</p>
  
  <p>I am currently reading, in my opinion, a very good and descriptive paper on Statistical Learning Theory - <strong><em><a href="https://arxiv.org/pdf/0810.4752.pdf" rel="nofollow noreferrer">"Statistical Learning Theory: Models, Concepts, and Results"</a></em></strong>. In section 5.5 Generalization bounds, it states that:</p>
  
  <blockquote>
    <p>It is sometimes useful to rewrite (17) "the other way round". That is, instead of ﬁxing <span class="math-container">$\epsilon$</span> and then computing the probability that the empirical risk deviates from the true risk by more than <span class="math-container">$\epsilon$</span>, we specify the probability with which we want the bound to hold, and then get a statement which tells us how close we can expect the risk to be to the empirical risk. This can be achieved by setting the right-hand side of (17) equal to some <span class="math-container">$\delta &gt; 0$</span>, and then solving for <span class="math-container">$\epsilon$</span>. As a result, we get the statement that with a probability at least <span class="math-container">$1−\delta$</span>, any function <span class="math-container">$f \in F$</span> satisﬁes</p>
  </blockquote>
  
  <p><a href="https://i.sstatic.net/uK2lv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/uK2lv.png" alt="enter image description here"></a></p>
  
  <p>Equation (17) is VC Symmetrization lemma to which we applied union bound and then Chernoff bound:</p>
  
  <p><a href="https://i.sstatic.net/d3OnF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/d3OnF.png" alt="enter image description here"></a></p>
  
  <p>What I fail to understand is the part where we are rewriting (17) "the other way around". I fail to grasp intuitive understanding of relation between (17) and (18), as well as understanding generalization bounds in general. </p>
  
  <p>Could anyone help me with understanding these concepts or at least provide me with additional resources (papers, blog posts, etc.) that can help?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-14T19:49:19.217Z
Comments.Text: Regarding the general idea of generalization bounds, generalization gap, etc., [this answer](https://ai.stackexchange.com/a/16737/2444) I had provided several months ago could be useful.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-16T08:53:20.373Z
Comments.Text: @nbro Thank you! I really want to learn more about Generalization in DL and I think this will help a lot! If you have any more resources, please share. Once again, THANKS!
Comments.UserDisplayName: Stefan Radonjic
Tags: <machine-learning><math><computational-learning-theory><vc-dimension><vc-theory>
Title: Understanding relation between VC Symmetrization Lemma and Generalization Bounds
UserDisplayName: Stefan Radonjic
ThreadText: # Understanding relation between VC Symmetrization Lemma and Generalization Bounds
  
  (Asked by: username_0 on 2020-04-14)
  
  I am new in the field of Machine Learning so I wanted to start of by reading more about mathematics and history behind it.
  
  I am currently reading, in my opinion, a very good and descriptive paper on Statistical Learning Theory - ***["Statistical Learning Theory: Models, Concepts, and Results"](https://arxiv.org/pdf/0810.4752.pdf)***. In section 5.5 Generalization bounds, it states that:
  
  > It is sometimes useful to rewrite (17) "the other way round". That is, instead of ﬁxing $\epsilon$ and then computing the probability that the empirical risk deviates from the true risk by more than $\epsilon$, we specify the probability with which we want the bound to hold, and then get a statement which tells us how close we can expect the risk to be to the empirical risk. This can be achieved by setting the right-hand side of (17) equal to some $\delta > 0$, and then solving for $\epsilon$. As a result, we get the statement that with a probability at least $1−\delta$, any function $f \in F$ satisﬁes
  
  [![enter image description here](https://i.sstatic.net/uK2lv.png)](https://i.sstatic.net/uK2lv.png)
  
  Equation (17) is VC Symmetrization lemma to which we applied union bound and then Chernoff bound:
  
  [![enter image description here](https://i.sstatic.net/d3OnF.png)](https://i.sstatic.net/d3OnF.png)
  
  What I fail to understand is the part where we are rewriting (17) "the other way around". I fail to grasp intuitive understanding of relation between (17) and (18), as well as understanding generalization bounds in general.
  
  Could anyone help me with understanding these concepts or at least provide me with additional resources (papers, blog posts, etc.) that can help?
  
  **Tags:** machine-learning, math, computational-learning-theory, vc-dimension, vc-theory
  
  > **Comments:**
  > **username_1**: Regarding the general idea of generalization bounds, generalization gap, etc., [this answer](https://ai.stackexchange.com/a/16737/2444) I had provided several months ago could be useful.  
  > **username_0**: @username_1 Thank you! I really want to learn more about Generalization in DL and I think this will help a lot! If you have any more resources, please share. Once again, THANKS!  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-04-14. Score: 3 | Accepted answer
  
  Let $\varepsilon$ in (17) is equal to $\sqrt{\frac{4}{n}\left(\log{(2\mathsf{N}(\mathcal{F},n))}-\log{\delta}\right)}$. We have:
  
  $$
  P\left(\sup\_{f\in\mathcal{F}}|R(f)-R\_{emp}(f)| > \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant
  2\mathcal{N}(\mathcal{F},n) e^{\frac{-n}{4}\left(\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)\right)} =
  2\mathcal{N}(\mathcal{F},n) e^{\log{\delta} - \log{(2\mathcal{N}(\mathcal{F},n))}}
  $$
  
  As we know that $e^{\log{n}} = n$ (suppose that base of $\log$ here is $e$), we can write:
  
  $$
  P\left(\sup\_{f\in\mathcal{F}}|R(f)-R\_{emp}(f)| > \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant
  2\mathcal{N}(\mathcal{F},n) \left(\frac{\delta}{2\mathcal{N}(\mathcal{F},n)}\right)
  $$
  
  Hence:
  
  $$
  P\left(\sup\_{f\in\mathcal{F}}|R(f)-R\_{emp}(f)| > \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \leqslant \delta
  $$
  As we know that if we have $P(x > a) \leqslant c$, we can conlude that $P( x<a) \geqslant 1-c$, we will have:
  
  $$
  P\left(\sup\_{f\in\mathcal{F}}|R(f)-R\_{emp}(f)| < \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}\right) \geqslant 1- \delta
  $$
  
  Now, as this inequality is true for supremum of set $\mathcal{F}$ and $R(f) -R\_{emp}(f) \leqslant \varepsilon$ is subset of $|R(f) -R\_{emp}(f)| \leqslant \varepsilon$ (in terms of probability state space), we can say the following inequality is correct for any function $f$ with at least probability of $1-\delta$:
  $$
  R(f) \leqslant R\_{emp}(f) + \sqrt{\frac{4}{n}\left(\log{(2\mathcal{N}(\mathcal{F},n))}-\log{\delta}\right)}
  $$
  
  > **Comments:**
  > **username_1**: The only part that is not clear and obvious is why you say that $R(f) -R_{emp}(f) \geqslant 0$ is a subset of $|R(f) -R_{emp}(f)| \geqslant 0$, i.e. you're saying that something greater or equal to zero (a number) is a _subset_ of something else that is greater or equal to zero. Maybe you can clarify this part.  
  
  ---
  
  