Answers.Body: <h1>Introduction</h1>
  
  <p>The paper <a href="https://arxiv.org/pdf/1710.05468.pdf" rel="nofollow noreferrer">Generalization in Deep Learning</a> provides a good overview (in section 2) of several results regarding the concept of generalisation in deep learning. I will try to describe one of the results (which is based on concepts from <a href="http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf" rel="nofollow noreferrer">computational</a> or <a href="http://www.econ.upf.edu/~lugosi/mlss_slt.pdf" rel="nofollow noreferrer">statistical</a> learning theory, so you should expect a technical answer), but I will first introduce and describe the <strong>general machine learning problem</strong> and I will give a definition of the <strong>generalisation gap problem</strong>. To keep this answer relatively short, I will assume the reader is familiar with certain basic machine learning and mathematical concepts, such as <a href="http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf" rel="nofollow noreferrer"><em>expected risk minimization</em></a>, but, nonetheless, I will refer the reader to more detailed explanations of the concepts (at least the first time they are mentioned). If you are familiar with the basic concepts of <a href="http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf" rel="nofollow noreferrer">computational learning theory (e.g. hypotheses)</a>, you will be advantaged.</p>
  
  <h1>Machine Learning Problem</h1>
  
  <p><em>In the following description, unless stated otherwise, I do not make any assumption about the nature of the variables. However, I will occasionally provide examples of concrete values for these variables.</em></p>
  
  <p>Let <span class="math-container">$x \in \mathcal{X}$</span> be an input and let <span class="math-container">$y \in \mathcal{Y}$</span> be a target. Let <span class="math-container">$\mathcal{L}$</span> be a loss function (e.g. MSE). </p>
  
  <p>Then the <a href="http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf" rel="nofollow noreferrer"><strong>expected</strong> risk</a> of a function (or hypothesis) <span class="math-container">$f$</span> is defined as</p>
  
  <p><span class="math-container">\begin{align}
  R[f] 
  &amp;= \mathbb{E}_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f(x), y) \right] \\
  &amp;= \int \mathcal{L}(f(x), y) d\mathbb{P}(X=x, Y=y),
  \end{align}</span> </p>
  
  <p>where <span class="math-container">$\mathbb{P}(X, Y)$</span> is the <em>true</em> <a href="https://en.wikipedia.org/wiki/Joint_probability_distribution" rel="nofollow noreferrer">joint probability distribution</a> of the inputs and targets. In other words, each <span class="math-container">$(x, y)$</span> is drawn from the joint distribution <span class="math-container">$\mathbb{P}(X, Y)$</span>, which contains or represents all the information required to understand the relationship between the inputs and the targets.</p>
  
  <p>Let <span class="math-container">$A$</span> be a learning algorithm or learner (e.g. gradient descent), which is the algorithm responsible for choosing a hypothesis <span class="math-container">$f$</span> (which can e.g. be represented by a neural network with parameters <span class="math-container">$\theta$</span>). Let </p>
  
  <p><span class="math-container">$$S_m = \{(x_i, y_i) \}_{i=1}^m$$</span> </p>
  
  <p>be the training dataset. Let </p>
  
  <p><span class="math-container">$$f_{A(S_m)} : \mathcal{X} \rightarrow \mathcal{Y}$$</span> </p>
  
  <p>be the <a href="http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf" rel="nofollow noreferrer">hypothesis</a> (or model) chosen by the learning algorithm <span class="math-container">$A$</span> using the training dataset <span class="math-container">$S_m$</span>.</p>
  
  <p>The <a href="http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf" rel="nofollow noreferrer"><strong>empirical</strong> risk</a> can then be defined as</p>
  
  <p><span class="math-container">$$
  R_{S_m}[f] = \frac{1}{m} \sum_{i=1}^m \mathcal{L} (f(x_i), y_i) 
  $$</span></p>
  
  <p>where <span class="math-container">$m$</span> is the total number of training examples.</p>
  
  <p>Let <span class="math-container">$F$</span> be the <a href="http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf" rel="nofollow noreferrer">hypothesis space</a> (for example, the space of all neural networks).</p>
  
  <p>Let </p>
  
  <p><span class="math-container">$$
  \mathcal{L_F} = \{ g : f \in F , g(x, y) = \mathcal{L}(f(x), y)\}
  $$</span> be a <a href="https://en.wikipedia.org/wiki/Family_of_sets" rel="nofollow noreferrer">family</a> of loss functions associated with the hypothesis space <span class="math-container">$F$</span>.</p>
  
  <h2>Expected Risk Minimization</h2>
  
  <p>In machine learning, the goal can be framed as the <strong>minimization</strong> of the <a href="http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf" rel="nofollow noreferrer">expected risk</a></p>
  
  <p><span class="math-container">\begin{align}
  f^*_{A(S_m)} 
  &amp;= \operatorname{argmin}_{f_{A(S_m)}} R[f_{A(S_m)}] \\
  &amp;= \operatorname{argmin}_{f_{A(S_m)}} \mathbb{E}_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f_{A(S_m)}(x), y) \right] \tag{1}\label{1}
  \end{align}</span></p>
  
  <p>However, the expected risk <span class="math-container">$R[f_{A(S_m)}]$</span> is <a href="https://en.wikipedia.org/wiki/Computability" rel="nofollow noreferrer">incomputable</a>, because it is defined as an <a href="https://en.wikipedia.org/wiki/Expected_value" rel="nofollow noreferrer">expectation</a> over <span class="math-container">$x, y \sim \mathbb{P}(X, Y)$</span> (which  is defined as an integral), but the true joint probability distribution <span class="math-container">$\mathbb{P}(X, Y)$</span> is <strong>unknown</strong>.</p>
  
  <h2>Empirical Risk Minimization</h2>
  
  <p>Therefore, we solve the approximate problem, which is called the <a href="http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf" rel="nofollow noreferrer"><strong>empirical risk minimization</strong></a> problem </p>
  
  <p><span class="math-container">\begin{align}
  f^*_{A(S_m)} &amp;= \operatorname{argmin}_{f_{A(S_m)} \in F} R_S[f_{A(S_m)}] \\
  &amp;= 
  \operatorname{argmin}_{f_{A(S_m)} \in F} \frac{1}{m} \sum_{i=1}^m \mathcal{L} (f_{A(S_m)}(x_i), y_i) 
  \end{align}</span></p>
  
  <h1>Generalization</h1>
  
  <p>In order to understand the generalization ability of <span class="math-container">$f_{A(S_m)}$</span>, the hypothesis chosen by the learner <span class="math-container">$A$</span> with training dataset <span class="math-container">$S_m$</span>, we need to understand when the <strong>empirical risk minimization</strong> problem is a good proxy for the <strong>expected risk minimization</strong> problem. In other words, we want to study the following problem</p>
  
  <p><span class="math-container">\begin{align}
  R[f_{A(S_m)}] -  R_S[f_{A(S_m)}] \tag{2}\label{2}
  \end{align}</span></p>
  
  <p>which can be called the <strong>generalization gap</strong> problem. So, in generalization theory, one goal is to study the gap between the expected and empirical risks. </p>
  
  <p>Clearly, we would like the expected risk to be equal to the empirical risk <span class="math-container">$$R_S[f_{A(S_m)}] = R[f_{A(S_m)}]$$</span> because this would allow us to measure the performance of the hypothesis (or model) <span class="math-container">$f_{A(S_m)}$</span> with the empirical risk, which can be computed. So, if <span class="math-container">$R_S[f_{A(S_m)}] = R[f_{A(S_m)}]$</span>, the generalization ability of <span class="math-container">$f_{A(S_m)}$</span> roughly corresponds to <span class="math-container">$R_S[f_{A(S_m)}]$</span>.</p>
  
  <p>Therefore, in generalization theory, one goal is to provide <a href="https://en.wikipedia.org/wiki/Upper_and_lower_bounds" rel="nofollow noreferrer">bounds</a> for the generalisation gap <span class="math-container">$R[f_{A(S_m)}] -  R_S[f_{A(S_m)}]$</span>.</p>
  
  <h1>Dependency on <span class="math-container">$S$</span></h1>
  
  <p>The hypothesis <span class="math-container">$f_{A(S_m)}$</span> is explicitly dependent on the training dataset <span class="math-container">$S$</span>. How does this dependency affect <span class="math-container">$f_{A(S_m)}$</span>? Can we avoid this dependency? Several approaches have been proposed to deal with this dependency. </p>
  
  <p>In the following sub-section, I will describe <strong>one</strong> approach to deal with the generalization gap problem, but you can find a description of the <strong>stability</strong>, <strong>robustness</strong> and <strong>flat minima</strong> approaches in <a href="https://arxiv.org/pdf/1710.05468.pdf" rel="nofollow noreferrer">Generalization in Deep Learning</a>.</p>
  
  <h2>Hypothesis-space Complexity</h2>
  
  <p>In this approach, we try to avoid the dependency of the hypothesis <span class="math-container">$f_{A(S_m)}$</span> by considering the <strong>worst-case</strong> generalization problem in the hypothesis space <span class="math-container">$F$</span></p>
  
  <p><span class="math-container">$$
  R[f_{A(S_m)}] -  R_S[f_{A(S_m)}] \leq \sup_{f \in F} \left( R[f] -  R_S[f] \right)
  $$</span>
  where <span class="math-container">$\sup_{f \in F} \left( R[f] -  R_S[f] \right)$</span> is the <a href="https://en.wikipedia.org/wiki/Infimum_and_supremum" rel="nofollow noreferrer">supremum</a> of a more general generalization gap problem, which is greater or equal to \ref{2}. In other words, we solve a more general problem to decouple the hypothesis (or model) from the training dataset <span class="math-container">$S$</span>.</p>
  
  <h3>Bound 1</h3>
  
  <p>If you assume the loss function <span class="math-container">$\mathcal{L}$</span> to take values in the range <span class="math-container">$[0, 1]$</span>, then, for any <span class="math-container">$\delta &gt; 0$</span>, with probability <span class="math-container">$1 - \delta$</span> (or more), the following bound holds</p>
  
  <p><span class="math-container">\begin{align}
  \sup_{f \in F} \left( R[f] -  R_S[f] \right) \leq 2 \mathcal{R}_m \left( \mathcal{L}_F \right) + \sqrt{\frac{\log{\frac{1}{\delta}} }{2m}} \tag{3} \label{3}
  \end{align}</span>
  where <span class="math-container">$m$</span> is the size of the training dataset, <span class="math-container">$\mathcal{R}_m$</span> is the <a href="https://en.wikipedia.org/wiki/Rademacher_complexity" rel="nofollow noreferrer">Rademacher complexity</a> of <span class="math-container">$\mathcal{L}_F$</span>, which is the family of loss functions for the hypothesis space <span class="math-container">$F$</span> (defined above).</p>
  
  <p>This theorem is proved in <a href="https://mitpress.ublish.com/ereader/7093/?preview=#page/29" rel="nofollow noreferrer">Foundations of machine learning</a> (2nd edition, 2018) by Mehryar Mohri et al.</p>
  
  <p>There are other bounds to this bound, but I will not list or describe them here. If you want to know more, have a look at the <a href="https://arxiv.org/pdf/1710.05468.pdf" rel="nofollow noreferrer">literature</a>.</p>
  
  <p>I will also not attempt to give you an intuitive explanation of this bound (given that I am also not very familiar with the <a href="https://en.wikipedia.org/wiki/Rademacher_complexity" rel="nofollow noreferrer">Rademacher complexity</a>). However, we can already understand how a change in <span class="math-container">$m$</span> affects the bound. What happens to the bound if <span class="math-container">$m$</span> increases (or decreases)?</p>
  
  <h1>Conclusion</h1>
  
  <p>There are several approaches to find bounds for the generalisation gap problem \ref{2}</p>
  
  <ul>
  <li>Hypothesis-space complexity</li>
  <li>Stability</li>
  <li>Robustness</li>
  <li>Flat minima</li>
  </ul>
  
  <p>In section 2 of the paper <a href="https://arxiv.org/pdf/1710.05468.pdf" rel="nofollow noreferrer">Generalization in Deep Learning</a>, bounds for problem \ref{2} are given based on the stability and robustness approaches.</p>
  
  <p>To conclude, the study of the generalization ability of deep learning models is based on <a href="http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf" rel="nofollow noreferrer">computational</a> or <a href="http://www.econ.upf.edu/~lugosi/mlss_slt.pdf" rel="nofollow noreferrer">statistical</a> learning theory. There are many more results related to this topic. You can find some of them in <a href="https://arxiv.org/pdf/1710.05468.pdf" rel="nofollow noreferrer">Generalization in Deep Learning</a>. The studies and results are highly technical, so, if you want to understand something, good knowledge of mathematics, proofs, and computational learning theory is required.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T16:23:38.920Z
Answers.Text: Thanks! While it does make sense, I'll continue looking for a concrete example to understand **how** $P(X,Y)$ contains or represents **all the information** required to understand the relationship between the inputs and the targets. Maybe I should also try asking this particular follow-up question on stats SE? Or maybe I'll see if I can find info on that in the book you linked to.
Answers.UserDisplayName: Shirish
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T16:27:22.957Z
Answers.Text: @ShirishKulhari $P(X, Y)$ is a probability distribution of both the random variables $X$ and $Y$. In other words, given a specific realisation of $X$ and $Y$, e.g. $X=x$ and $Y=y$, then $P(X=x, Y=y)$ tells you the probability (or density) that the random variables $X$ and $Y$ take the values $x$ and $y$ at the same time, so it tells you how probable these two realisations are, in this sense $P(X, Y)$ contains the way $X$ and $Y$ vary together (see the concept of independence). So, in a certain way, you can find a function $f(x) = y$ based on the probabilities that $x$ and $y$ appear together.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T17:06:36.237Z
Answers.Text: @ShirishKulhari Regarding your second question, where you say "but I'm not sure how the entire hypothesis space can change with change in". In my answer, I am not saying that the entire hypothesis space, denoted by $F$ (capital $f$), depends on $S$. I am just saying that the single hypothesis $f_{A(S_m)} \in F$, where $F$ is the hypothesis space, explicitly depends on the training dataset $S_m$, **by definition**. Have a look at how $f_{A(S_m)}$ is defined in my answer. So, there are hypothesis $f \in F$, which do not depend on $S_m$, but maybe depend on another dataset.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-24T03:51:20.990Z
Answers.LastActivityDate: 2019-11-25T16:23:00.320Z
Answers.LastEditDate: 2019-11-25T16:23:00.320Z
Answers.UserDisplayName: nbro
Body: <p>I've read a few classic papers on different architectures of deep CNNs used to solve varied image-related problems. I'm aware there's some paradox in how deep networks generalize well despite seemingly overfitting training data. A lot of people in the data science field that I've interacted with agree that there's no explanation on <strong>why</strong> deep neural networks work as well as they do.</p>
  
  <p>That's gotten me interested in the theoretical basis for why deep nets work so well. Googling tells me it's kind of an open problem, but I'm not sure of the current state of research in answering this question. Notably, there are these two preprints that seem to tackle this question:</p>
  
  <ul>
  <li><p><a href="https://arxiv.org/pdf/1710.05468.pdf" rel="noreferrer">Generalization in Deep Learning</a> (2019)</p></li>
  <li><p><a href="https://arxiv.org/pdf/1905.11427.pdf" rel="noreferrer">Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness</a> (2019)</p></li>
  </ul>
  
  <p>If anyone else is interested in and following this research area, could you please explain the current state of research on this open problem? What are the latest works, preprints or publications that attempt to tackle it?</p>
  
Tags: <deep-learning><research><reference-request><computational-learning-theory><generalization>
Title: What are the state-of-the-art results on the generalization ability of deep learning methods?
UserDisplayName: Shirish
ThreadText: # What are the state-of-the-art results on the generalization ability of deep learning methods?
  
  (Asked by: username_0 on 2019-11-15)
  
  I've read a few classic papers on different architectures of deep CNNs used to solve varied image-related problems. I'm aware there's some paradox in how deep networks generalize well despite seemingly overfitting training data. A lot of people in the data science field that I've interacted with agree that there's no explanation on **why** deep neural networks work as well as they do.
  
  That's gotten me interested in the theoretical basis for why deep nets work so well. Googling tells me it's kind of an open problem, but I'm not sure of the current state of research in answering this question. Notably, there are these two preprints that seem to tackle this question:
  
  * [Generalization in Deep Learning](https://arxiv.org/pdf/1710.05468.pdf) (2019)
  * [Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness](https://arxiv.org/pdf/1905.11427.pdf) (2019)
  
  If anyone else is interested in and following this research area, could you please explain the current state of research on this open problem? What are the latest works, preprints or publications that attempt to tackle it?
  
  **Tags:** deep-learning, research, reference-request, computational-learning-theory, generalization
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-24. Score: 6 | Accepted answer
  
  # Introduction
  
  The paper [Generalization in Deep Learning](https://arxiv.org/pdf/1710.05468.pdf) provides a good overview (in section 2) of several results regarding the concept of generalisation in deep learning. I will try to describe one of the results (which is based on concepts from [computational](http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf) or [statistical](http://www.econ.upf.edu/~lugosi/mlss_slt.pdf) learning theory, so you should expect a technical answer), but I will first introduce and describe the **general machine learning problem** and I will give a definition of the **generalisation gap problem**. To keep this answer relatively short, I will assume the reader is familiar with certain basic machine learning and mathematical concepts, such as [*expected risk minimization*](http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf), but, nonetheless, I will refer the reader to more detailed explanations of the concepts (at least the first time they are mentioned). If you are familiar with the basic concepts of [computational learning theory (e.g. hypotheses)](http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf), you will be advantaged.
  
  # Machine Learning Problem
  
  *In the following description, unless stated otherwise, I do not make any assumption about the nature of the variables. However, I will occasionally provide examples of concrete values for these variables.*
  
  Let $x \in \mathcal{X}$ be an input and let $y \in \mathcal{Y}$ be a target. Let $\mathcal{L}$ be a loss function (e.g. MSE).
  
  Then the [**expected** risk](http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf) of a function (or hypothesis) $f$ is defined as
  
  \begin{align}
  R[f]
  &= \mathbb{E}\_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f(x), y) \right] \\
  &= \int \mathcal{L}(f(x), y) d\mathbb{P}(X=x, Y=y),
  \end{align}
  
  where $\mathbb{P}(X, Y)$ is the *true* [joint probability distribution](https://en.wikipedia.org/wiki/Joint_probability_distribution) of the inputs and targets. In other words, each $(x, y)$ is drawn from the joint distribution $\mathbb{P}(X, Y)$, which contains or represents all the information required to understand the relationship between the inputs and the targets.
  
  Let $A$ be a learning algorithm or learner (e.g. gradient descent), which is the algorithm responsible for choosing a hypothesis $f$ (which can e.g. be represented by a neural network with parameters $\theta$). Let
  
  $$S\_m = \{(x\_i, y\_i) \}\_{i=1}^m$$
  
  be the training dataset. Let
  
  $$f\_{A(S\_m)} : \mathcal{X} \rightarrow \mathcal{Y}$$
  
  be the [hypothesis](http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf) (or model) chosen by the learning algorithm $A$ using the training dataset $S\_m$.
  
  The [**empirical** risk](http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf) can then be defined as
  
  $$
  R\_{S\_m}[f] = \frac{1}{m} \sum\_{i=1}^m \mathcal{L} (f(x\_i), y\_i)
  $$
  
  where $m$ is the total number of training examples.
  
  Let $F$ be the [hypothesis space](http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf) (for example, the space of all neural networks).
  
  Let
  
  $$
  \mathcal{L\_F} = \{ g : f \in F , g(x, y) = \mathcal{L}(f(x), y)\}
  $$ be a [family](https://en.wikipedia.org/wiki/Family_of_sets) of loss functions associated with the hypothesis space $F$.
  
  ## Expected Risk Minimization
  
  In machine learning, the goal can be framed as the **minimization** of the [expected risk](http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf)
  
  \begin{align}
  f^\*\_{A(S\_m)}
  &= \operatorname{argmin}\_{f\_{A(S\_m)}} R[f\_{A(S\_m)}] \\
  &= \operatorname{argmin}\_{f\_{A(S\_m)}} \mathbb{E}\_{x, y \sim \mathbb{P}(X, Y)} \left[ \mathcal{L}(f\_{A(S\_m)}(x), y) \right] \tag{1}\label{1}
  \end{align}
  
  However, the expected risk $R[f\_{A(S\_m)}]$ is [incomputable](https://en.wikipedia.org/wiki/Computability), because it is defined as an [expectation](https://en.wikipedia.org/wiki/Expected_value) over $x, y \sim \mathbb{P}(X, Y)$ (which is defined as an integral), but the true joint probability distribution $\mathbb{P}(X, Y)$ is **unknown**.
  
  ## Empirical Risk Minimization
  
  Therefore, we solve the approximate problem, which is called the [**empirical risk minimization**](http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf) problem
  
  \begin{align}
  f^\*\_{A(S\_m)} &= \operatorname{argmin}\_{f\_{A(S\_m)} \in F} R\_S[f\_{A(S\_m)}] \\
  &=
  \operatorname{argmin}\_{f\_{A(S\_m)} \in F} \frac{1}{m} \sum\_{i=1}^m \mathcal{L} (f\_{A(S\_m)}(x\_i), y\_i)
  \end{align}
  
  # Generalization
  
  In order to understand the generalization ability of $f\_{A(S\_m)}$, the hypothesis chosen by the learner $A$ with training dataset $S\_m$, we need to understand when the **empirical risk minimization** problem is a good proxy for the **expected risk minimization** problem. In other words, we want to study the following problem
  
  \begin{align}
  R[f\_{A(S\_m)}] - R\_S[f\_{A(S\_m)}] \tag{2}\label{2}
  \end{align}
  
  which can be called the **generalization gap** problem. So, in generalization theory, one goal is to study the gap between the expected and empirical risks.
  
  Clearly, we would like the expected risk to be equal to the empirical risk $$R\_S[f\_{A(S\_m)}] = R[f\_{A(S\_m)}]$$ because this would allow us to measure the performance of the hypothesis (or model) $f\_{A(S\_m)}$ with the empirical risk, which can be computed. So, if $R\_S[f\_{A(S\_m)}] = R[f\_{A(S\_m)}]$, the generalization ability of $f\_{A(S\_m)}$ roughly corresponds to $R\_S[f\_{A(S\_m)}]$.
  
  Therefore, in generalization theory, one goal is to provide [bounds](https://en.wikipedia.org/wiki/Upper_and_lower_bounds) for the generalisation gap $R[f\_{A(S\_m)}] - R\_S[f\_{A(S\_m)}]$.
  
  # Dependency on $S$
  
  The hypothesis $f\_{A(S\_m)}$ is explicitly dependent on the training dataset $S$. How does this dependency affect $f\_{A(S\_m)}$? Can we avoid this dependency? Several approaches have been proposed to deal with this dependency.
  
  In the following sub-section, I will describe **one** approach to deal with the generalization gap problem, but you can find a description of the **stability**, **robustness** and **flat minima** approaches in [Generalization in Deep Learning](https://arxiv.org/pdf/1710.05468.pdf).
  
  ## Hypothesis-space Complexity
  
  In this approach, we try to avoid the dependency of the hypothesis $f\_{A(S\_m)}$ by considering the **worst-case** generalization problem in the hypothesis space $F$
  
  $$
  R[f\_{A(S\_m)}] - R\_S[f\_{A(S\_m)}] \leq \sup\_{f \in F} \left( R[f] - R\_S[f] \right)
  $$
  where $\sup\_{f \in F} \left( R[f] - R\_S[f] \right)$ is the [supremum](https://en.wikipedia.org/wiki/Infimum_and_supremum) of a more general generalization gap problem, which is greater or equal to \ref{2}. In other words, we solve a more general problem to decouple the hypothesis (or model) from the training dataset $S$.
  
  ### Bound 1
  
  If you assume the loss function $\mathcal{L}$ to take values in the range $[0, 1]$, then, for any $\delta > 0$, with probability $1 - \delta$ (or more), the following bound holds
  
  \begin{align}
  \sup\_{f \in F} \left( R[f] - R\_S[f] \right) \leq 2 \mathcal{R}\_m \left( \mathcal{L}\_F \right) + \sqrt{\frac{\log{\frac{1}{\delta}} }{2m}} \tag{3} \label{3}
  \end{align}
  where $m$ is the size of the training dataset, $\mathcal{R}\_m$ is the [Rademacher complexity](https://en.wikipedia.org/wiki/Rademacher_complexity) of $\mathcal{L}\_F$, which is the family of loss functions for the hypothesis space $F$ (defined above).
  
  This theorem is proved in [Foundations of machine learning](https://mitpress.ublish.com/ereader/7093/?preview=#page/29) (2nd edition, 2018) by Mehryar Mohri et al.
  
  There are other bounds to this bound, but I will not list or describe them here. If you want to know more, have a look at the [literature](https://arxiv.org/pdf/1710.05468.pdf).
  
  I will also not attempt to give you an intuitive explanation of this bound (given that I am also not very familiar with the [Rademacher complexity](https://en.wikipedia.org/wiki/Rademacher_complexity)). However, we can already understand how a change in $m$ affects the bound. What happens to the bound if $m$ increases (or decreases)?
  
  # Conclusion
  
  There are several approaches to find bounds for the generalisation gap problem \ref{2}
  
  * Hypothesis-space complexity
  * Stability
  * Robustness
  * Flat minima
  
  In section 2 of the paper [Generalization in Deep Learning](https://arxiv.org/pdf/1710.05468.pdf), bounds for problem \ref{2} are given based on the stability and robustness approaches.
  
  To conclude, the study of the generalization ability of deep learning models is based on [computational](http://www2.denizyuret.com/ref/angluin/coltsurvey.pdf) or [statistical](http://www.econ.upf.edu/~lugosi/mlss_slt.pdf) learning theory. There are many more results related to this topic. You can find some of them in [Generalization in Deep Learning](https://arxiv.org/pdf/1710.05468.pdf). The studies and results are highly technical, so, if you want to understand something, good knowledge of mathematics, proofs, and computational learning theory is required.
  
  > **Comments:**
  > **username_0**: Thanks! While it does make sense, I'll continue looking for a concrete example to understand **how** $P(X,Y)$ contains or represents **all the information** required to understand the relationship between the inputs and the targets. Maybe I should also try asking this particular follow-up question on stats SE? Or maybe I'll see if I can find info on that in the book you linked to.  
  > **username_1**: @ShirishKulhari $P(X, Y)$ is a probability distribution of both the random variables $X$ and $Y$. In other words, given a specific realisation of $X$ and $Y$, e.g. $X=x$ and $Y=y$, then $P(X=x, Y=y)$ tells you the probability (or density) that the random variables $X$ and $Y$ take the values $x$ and $y$ at the same time, so it tells you how probable these two realisations are, in this sense $P(X, Y)$ contains the way $X$ and $Y$ vary together (see the concept of independence). So, in a certain way, you can find a function $f(x) = y$ based on the probabilities that $x$ and $y$ appear together.  
  > **username_1**: @ShirishKulhari Regarding your second question, where you say "but I'm not sure how the entire hypothesis space can change with change in". In my answer, I am not saying that the entire hypothesis space, denoted by $F$ (capital $f$), depends on $S$. I am just saying that the single hypothesis $f_{A(S_m)} \in F$, where $F$ is the hypothesis space, explicitly depends on the training dataset $S_m$, **by definition**. Have a look at how $f_{A(S_m)}$ is defined in my answer. So, there are hypothesis $f \in F$, which do not depend on $S_m$, but maybe depend on another dataset.  
  
  ---
  
  