Introduction
The paper Generalization in Deep Learning 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 or statistical 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, 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), 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 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 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 (or model) chosen by the learning algorithm $A$ using the training dataset $S_m$.
The empirical risk 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 (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 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
\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, because it is defined as an expectation 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 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 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.
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 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 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 (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.
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). 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, 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 or statistical learning theory. There are many more results related to this topic. You can find some of them in Generalization in Deep Learning. 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.
