# Generalization bounds for deep learning

Guillermo Valle-Pérez
<EMAIL_ADDRESS>
Department of Theoretical Physics
University of Oxford
Ard A. Louis
<EMAIL_ADDRESS>
Department of Theoretical Physics
University of Oxford

###### Abstract

Generalization in deep learning has been the topic of much recent theoretical
and empirical research. Here we introduce desiderata for techniques that
predict generalization errors for deep learning models in supervised learning.
Such predictions should 1) scale correctly with data complexity; 2) scale
correctly with training set size; 3) capture differences between
architectures; 4) capture differences between optimization algorithms; 5) be
quantitatively not too far from the true error (in particular, be non-
vacuous); 6) be efficiently computable; and 7) be rigorous. We focus on
generalization error upper bounds, and introduce a categorisation of bounds
depending on assumptions on the algorithm and data. We review a wide range of
existing approaches, from classical VC dimension to recent PAC-Bayesian
bounds, commenting on how well they perform against the desiderata. We next
use a function-based picture to derive a marginal-likelihood PAC-Bayesian
bound. This bound is, by one definition, optimal up to a multiplicative
constant in the asymptotic limit of large training sets, as long as the
learning curve follows a power law, which is typically found in practice for
deep learning problems. Extensive empirical analysis demonstrates that our
marginal-likelihood PAC-Bayes bound fulfills desiderata 1-3 and 5. The results
for 6 and 7 are promising, but not yet fully conclusive, while only
desideratum 4 is currently beyond the scope of our bound. Finally, we comment
on why this function-based bound performs significantly better than current
parameter-based PAC-Bayes bounds.

## 1 Introduction

While deep learning can provide remarkable empirical performance in many
machine learning tasks, a theoretical account of this success remains elusive.
One of the main metrics of performance in machine learning is generalization,
or the ability to predict correctly on new unseen data. Statistical learning
theory offers a theoretical framework to understand generalization, with the
main tool being the derivation of upper bounds on the generalization error.
However, it is now widely acknowledged that “classical” approaches in learning
theory, based on worst-case analyses, are not sufficient to explain
generalization of deep learning models, see e.g. Bartlett (1998); Zhang et al.
(2017). This observation has spurred a large amount of work on applying and
developing other learning theory approaches to deep learning, some of which
are showing promising results. However, current approaches are still lacking
in many ways: generalization error bounds are often vacuous or offer little
explanatory power by showing trends opposite to the true error as one varies
important quantities. For example, Nagarajan and Kolter (2019) show that some
common spectral norm-based bound predictions increase with increasing training
set size, while the measured error decreases. Moreover, many bounds are
published without being sufficiently tested, so that it can be hard to assess
their strengths and weaknesses.

There is therefore a need for a more systematic approach to studying
generalization bounds. Two important recent studies have taken up this
challenge. Firstly, Jiang et al. (2019) preformed extensive empirical tests of
the predictive power of over $40$ different generalization measures for a
range of commonly used hyperparameters. They mainly studied flatness and norm-
based measures, and compared them by reporting an average of the performance.
In their comparisons, they focused mostly on training hyperparameters.
Architectures were only compared by changing width and depth of an
architecture resembling the Network-in-Network (Gao et al., 2011), and they
did not systematically study variation on the data (dataset complexity or
training set size).

Secondly, in a follow-up study Dziugaite et al. (2020), argue that average
performance is not a sufficient metric of generalization performance. They
empirically demonstrate that generalization measures can exhibit correct
correlations for certain parameter changes and seeds, but badly fail for
others. In addition to some of the hyperparameter changes studied by Jiang et
al. (2019), they also consider the effect of changing dataset complexity and
training set size.

In this paper we also perform a systematic analysis of generalization bounds.
We first describe, in section 2, a set of seven qualitatively different
desiderata which, we argue, should be used to guide the kind of
experiments111Here, ‘experiment’ can be interpreted in the formal sense which
Dziugaite et al. (2020) introduce needed to fully explore the quality of the
predictions of a theory of the generalization. These include four desiderata
for making correct predictions when varying architecture, dataset complexity,
dataset size, or optimizer choice, as well as three further desiderata, which
describe the importance of quantitative agreement, computational efficiency
and theoretical rigour. Our set of desiderata is broader than those used in
previous tests of generalization theories, and will, we hope, lead to a better
understanding of the strengths and weaknesses of competing approaches.

Rather than empirically testing the many bounds that can be found in the
literature, we take a more general theoretical approach here. We first, in
section 3, present an overall framework for classifying the many different
approaches to deriving frequentist bounds of the generalization error. This
framework is then used to systematically organize the discussion of the
different approaches in the literature. For each approach we review existing
results in the literature and compare performance for the seven desiderata we
propose. Such an analysis allows us to draw some more general conclusions
about the kinds of strategies for deriving generalization bounds that may be
most successful. In this context we also note, that for some proposed bounds,
there is not enough empirical evidence in the literature to determine whether
or not they satisfy our desiderata. This lacuna highlights the importance of
the proposals put forward by Jiang et al. (2019) and Dziugaite et al. (2020)
of large scale empirical studies, which we also advocate for in this paper.

Inspired by our analysis of existing bounds we present in section 5 a high-
probability version of the realizable PAC-Bayes bound introduced by McAllester
(1998) and applied to deep learning in Valle-Pérez et al. (2018). Because our
bound, which is derived from a function-based picture, is directly
proportional to the Bayesian evidence or marginal likelihood of the model, we
call it the _marginal likelihood PAC-Bayes bound_. While our bound has
frequentist origins, the connection between marginal likelihood and
generalization is an important theme in Bayesian analyses, and can be traced
back to the work of MacKay and Neal (MacKay, 1992; Neal, 1994; MacKay and Mac
Kay, 2003), as well as the early work on PAC-Bayes (Shawe-Taylor and
Williamson, 1997; McAllester, 1998). See also an important recent discussion
of this connection in Wilson and Izmailov (2020).

Recent large-scale empirical work has shown that learning curves for deep-
learning have an extensive power-law regime (Hestness et al., 2017; Spigler et
al., 2019; Kaplan et al., 2020; Henighan et al., 2020). The exponents in the
power-law depend mainly on the data rather than on architectures, with smaller
exponents for more complex datasets. Under the assumption of a power-law
asymptotic behaviour with training set size, we are able to prove that our
marginal-likelihood PAC-Bayes bound is asymptotically optimal up to a constant
in the limit of large training sets.

In order to test our marginal-likelihood PAC-Bayes bound against the full set
of desiderata, we perform over 1,000 experiments comparing 19 different
architectures, ranging from simple fully connected networks (FCNs) and
convolutional neural networks (CNNs) to more sophisticated architectures such
as Resnet50, Densenet121 and Mobilenetv2. We are thus including variations in
architecture hyperparameters such as pooling type, the number of layers, skip
connections, etc…. These networks are tested on 5 different computer vision
datasets of varying complexity. For each of these 95 architecture/data
combinations, we train on a range of training set sizes to study learning
curves. We additionally study the effect of label corruption on two of the
data sets, MNIST and CIFAR-10. Our bound provides non-vacuous generalization
bounds, which are also tight enough to provide a reasonably good quantitative
guide to generalization. It also does remarkably well at predicting
qualitative trends in the generalization error as a function of data
complexity, architecture (including, for example, differences between average
and max pooling), and training set size. In particular, we find that we can
estimate the value of the learning curve power law exponent for different
datasets.

In our concluding section, we argue that the use of a function based
perspective is a key to understanding the relatively good performance of our
marginal likelihood bound across so many desiderata. This approach contrasts
with many other PAC-Bayesian bounds in the deep learning theory literature,
which use distributions in parameter space, mostly as a way to measure
flatness. We also discuss potential weaknesses of our approach, such as its
inability to capture the effect of DNN width or of optimiser choice (but see
Mingard et al. (2020)). Finally, we argue that capturing trends in
generalization when architecture and data are varied is not only theoretically
interesting, but also important for many applications including architecture
search and data augmentation.

## 2 Desiderata for predictive theories of generalization error

The fundamental question of what constitutes a “good” theory of generalization
in deep learning is a profound and contested one. Jiang et al. (2019) and
Dziugaite et al. (2020) both consider this question and suggest that a good
theory should capture the causal mechanisms behind generalization. Jiang et
al. (2019) use a measure of conditional independence to estimate the causal
relation between different complexity measure and generalization. Dziugaite et
al. (2020) consider a stronger notion that tries to capture whether a theory
predicts well the generalization error over _all_ possible experimental
interventions. To formalize this notion they look at distributional robustness
which quantifies the worst-case predictive performance of a theory.

Here we take a slightly different approach to this question by defining a
seven key desiderata that a “good” theory of generalization should satisfy.
This set is broader than that considered by Jiang et al. (2019) and Dziugaite
et al. (2020) in that it considers desiderata beyond simply the predictive
performance.

Furthermore, rather than focusing only on the average case or worst-case
performance of a predictive theory, we argue that a precise formulation of the
performance of a generalization measure necessarily depends on the
application. Therefore in our discussions in section 4, and in the extensive
experiments in section 7, we aim to paint a fine-grained picture of how well
the theory predicts generalization for different experimental settings, and
how it fares at other important desiderata.

We focus our attention on generalization error upper bounds, but the same
ideas could apply to other types of theories that aim to predict
generalization error (for example, those based on Bayesian assumptions on the
data distribution).

The seven desiderata which we propose a good predictive theory of
generalization for deep learning should aim to satisfy are listed below:

D.1

data complexity: The predicted error should correctly scale with data
complexity. In other words, the predicted error should correlate well with the
true error when the dataset is changed. For example, a fixed DNN, for a fixed
training set size, will typically have higher error for CIFAR10 than for
MNIST, and an even higher error for a label-corrupted dataset. The bound
should capture such differences.

D.2

training set size: The predicted error should correctly scale with training
set size. That is, the predicted error should follow the same trend as the
true error as the number of training examples increases. For example, it has
been found empirically that the generalization error often follows a power law
decay with training set size with an exponent which depends on the dataset,
but not strongly on the architecture (Hestness et al., 2017; Novak et al.,
2019; Rosenfeld et al., 2019; Kaplan et al., 2020).

D.3

architectures: The predicted error should capture differences in
generalization between architectures. Different architectures can display
significant variation in generalization performance. For example, CNNs with
pooling tend to generalize better than CNNs without pooling on image
classification tasks. The predicted error should aim to predict these
differences. Furthermore, one of the more puzzling properties of DNNs is that
the performance depends only weakly on the number of parameters used for an
architecture, provided the system is large enough (Belkin et al., 2019;
Nakkiran et al., 2019). Since this question of why DNNs generalize so well in
the overparameterised regime is one of the central questions in the theory of
DNNs, it is particularly important that a predicted error can reproduce this
relative insensitivity to the number of parameters.

D.4

optimization algorithms: The predicted error should capture differences in
generalization between different optimization algorithms. Different
optimization algorithms used in training DNNs, as well as different choices of
training hyperparameters such as SGD batch size and learning rates, or
regularization techniques, can lead to differences in generalization, which
the theory should aim to predict.

D.5

non-vacuous: The predicted error should be quantitatively close to the true
error. For generalization error upper bounds, it is commonly required that the
error is less than $100\%$, as any upper bound higher than that is satisfied
by definition and thus can be considered “vacuous”. Beyond this requirement,
the bound should aim to be as close as possible to the true error (a property
often referred to as being a _tight_ bound).

D.6

efficiently computable: The predicted error should be efficiently computable.
This requirement is particularly important if the prediction or bound is to be
useful in practical applications (for example, in architecture search). It is
of little use having a bound that cannot in practice be calculated.

D.7

rigorous: The prediction should be rigorous. For the case of upper bounds,
this means that the bound comes with a theorem that guarantees its validity
under a well-specified set of assumptions, which should be met on the domain
where it is applied. In practice, theoretical results are often applied to
domains where the assumptions aren’t known to hold (or are known _not_ to
hold), but rigorous guarantees offer the highest level of confidence on one’s
predictions, and should be aimed for whenever possible.

A theory of generalization error should aim to satisfy as many of these
desiderata as possible. However, the trade-offs that one is willing to make
depend on the domain of application of the theory. For example, a rigorous
proof may be more valuable for theoretical insight than for a practical
application, where computational efficiency may be more important. As another
example, for an application to neural architecture search one may care more
about the scaling with architecture, while for an application to decision
making for data collection one may care more about correct scaling with
training set size.

## 3 Classifying generalization bounds for deep learning

In this section, we provide an overview of existing approaches to predict
generalization error. After some preliminary sections describing notation and
definitions we present a general taxonomy which classifies generalization
error upper bounds based on the key assumptions they make.

###  3.1 Notation for the supervised learning problem

Supervised learning deals with the problem of predicting outputs from inputs,
given a set of example input-output pairs. The inputs live in an input domain
$\mathcal{X}$, and the outputs belong to an output space $\mathcal{Y}$. We
will mostly focus on the binary classification setting where
$\mathcal{Y}=\\{0,1\\}$222See section C for a brief comment on extensions to
the multi-class setting for the generalization bounds we study here. We assume
that there is a _data distribution_ $\mathcal{D}$ on the set of input-output
pairs $\mathcal{X}\times\mathcal{Y}$. The _training set_ $S$ is a sample of
$m$ input-output pairs sampled i.i.d. from $\mathcal{D}$,
$S=\\{(x_{i},y_{i})\\}_{i=1}^{m}\sim\mathcal{D}^{m}$, where
$x_{i}\in\mathcal{X}$ and $y_{i}\in\mathcal{Y}$. We will refer to the data
distribution as _noiseless_ if it can be factored as
$\mathcal{D}((x,y))=\mathcal{D}_{X}(x)\mathcal{D}_{Y|X}(y|x)$ where
$\mathcal{D}_{Y|X}$ is deterministic, that is it has support on a single value
in $y=f(x)$. In this case $f$ is called the _target function_.

We define a _loss function_ $L:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}$,
which measures how “well” a prediction $\hat{y}\in\mathcal{Y}$ matches an
observed output $y\in\mathcal{Y}$, by assigning to it a score $L(\hat{y},y)$
which is high when they don’t match. In supervised learning, we define a
_hypothesis_ 333This is sometimes also called a predictor, or classifier, in
the context of supervised learning $h$ as a function from inputs to outputs
$h:\mathcal{X}\to\mathcal{Y}$ and the _risk_ $R$ of a hypothesis as the
expected value of the loss of the predicted outputs on new samples
$R(h)=\mathbf{E}_{(x,y)\sim\mathcal{D}}[L(h(x),y)]$. For the case of
classification, where $\mathcal{Y}$ is a discrete set, we focus on the _0-1
loss_ function (also called _classification loss_)
$L(\hat{y},y)=\mathbbm{1}[\hat{y}\neq y]$, where $\mathbbm{1}$ is the
indicator function. We define the _generalization error_ $\epsilon$ as the
expected risk using this loss, which equals the probability of
misclassification.

$\epsilon(h)=\mathbf{P}_{(x,y)\sim\mathcal{D}}[h(x)\neq y]$ (1)

This is the central quantity which we study here. We also define the _training
error_ $\hat{\epsilon}(h,S)=\frac{1}{m}\sum_{(x,y)\in S}\mathbbm{1}[h(x)\neq
y]$. For a more general loss function, we also define the _empirical risk_
$\widehat{R}(h,S)=\frac{1}{m}\sum_{(x,y)\in S}L(h(x),y)$, as the empirical
average of the loss function over the training set. To simplify notation, we
often simply write $\widehat{R}(h)$ and $\hat{\epsilon}(h)$ for
$\widehat{R}(h,S)$ and $\hat{\epsilon}(h,S)$, respectively.

Finally, we define a _learning algorithm_ to be a mapping
$\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{*}\to\mathcal{Y}^{\mathcal{X}}$
from training sets of any size to hypothesis functions. For simplicity, we
mainly describe deterministic hypotheses and learning algorithms, but most
results should be easily generalizable to stochastic versions. A stochastic
learning algorithm will map training sets to a probability distribution over
hypothesiss, while a stochastic hypothesis maps inputs in $\mathcal{X}$ to
proability distributions over outputs in $\mathcal{Y}$. For PAC-Bayes we will
consider stochastic learning algorithms.

The supervised learning problem consists of finding a learning algorithm
$\mathcal{A}$ that produces low generalization error $\epsilon(h)$ (in
expectation, or with high probability), under certain well defined assumptions
(including none) on the data distribution $\mathcal{D}$.

###  3.2 General PAC learning framework

The modern theory of statistical learning theory originated with Leslie
Valiant’s probably approximately correct (PAC) framework (Valiant, 1984), and
Vapnik and Chervonenkis’ uniform convergence analysis (Vapnik, 1968; Vapnik
and Chervonenkis, 1974; Vapnik, 1995). Here we describe a general frequentist
formulation of generalization error bounds of the type studied in supervised
learning theory. Although the original PAC framework included the condition of
computational efficiency of the learning algorithm in its definition, the term
is used more widely now (Guedj, 2019). In the most general case, the PAC
learning framework we present here proves confidence bounds that establish a
relationship between observed quantities (derived from the training set) and
the unobserved generalization error $\epsilon(h)$, which is the real quantity
of interest. Specifically we consider bounds on $D$, a function measuring the
difference between generalization and training error (which we refer to as the
_generalization gap_), which state that, under some (or no) assumptions on the
data distribution $\mathcal{D}$ and algorithm $\mathcal{A}$, the following
bound holds:

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}[D(\epsilon(\mathcal{A}(S)),\hat{\epsilon}(\mathcal{A}(S)))\leq\frac{f_{\mathcal{A}}(S)}{m^{\alpha}}]\geq
1-\delta$ (2)

with probability at least $1-\delta\in[0,1]$. Here the probability
$\mathbf{P}_{S\sim\mathcal{D}^{m}}$ is for the event inside the square
brackets when $S$ is sampled from $\mathcal{D}^{m}$. $f_{\mathcal{A}}$ is a
function which, following common practice in the literature, we will call
_capacity_. The capacity measures some notion of the “complexity” of the
algorithm, the data, or both. $\delta$ is called the confidence parameter and
measures the probability with which the bound may fail because of getting an
“unusual” training set. Finally, the exponent $0<\alpha\leq 1$. The most
common measure of generalization gap $D$ is the absolute difference between
the generalization and training error, but in some general PAC-Bayesian
analyses $D$ may be any convex function (Rivasplata et al., 2020). The
capacity $f_{\mathcal{A}}$ can also take many forms. Some common examples
include the VC dimension (section 4.1.1) and the KL divergence of a posterior
and prior for PAC-Bayes bounds (section 4.2.1.1). Sometimes the dependence on
training set is fully absorbed into $f_{\mathcal{A}}$ so that $1/m^{\alpha}$
is omitted.

We also distinguish two types of bounds

  * •

_generalization gap bounds_ are bounds on
$D(\epsilon(\mathcal{A}(S)),\hat{\epsilon}(\mathcal{A}(S)))=|\epsilon(h)-\hat{\epsilon}(h)|$
or some other measure of discrepancy $D$ between the generalization and
training error

  * •

_generalization error bounds_ are bounds on a function of $\epsilon(h)$ alone.

Note that a generalization gap bound immediately implies a generalization
error bound, but not necessarily vice versa. If $\hat{\epsilon}(h)=0$
(realizability assumption), the distinction between these bounds doesn’t
exist.

Finally, in order to simplify notation, we typically omit dependence of the
capacity on the parameter $\delta$ throughout the paper.

###  3.3 A classification of generalization bounds

In this section we classify the main types of bounds which are possible under
the general PAC framework described above, according to the different
assumptions they make on the data distribution or algorithm, and on the
different quantities the capacity $f_{\mathcal{A}}(S)$ may depend on.

#### 3.3.1 According to assumptions on the data $\mathcal{D}$

The PAC framework is characterized by bounds which make as few assumptions
about the data distribution $\mathcal{D}$ as possible. There are two main
approaches: agnostic and realizable bounds.

  * •

Agnostic bounds. For _agnostic_ or _distribution-free_ bounds, no assumption
is made on the data distribution. In this case, the No Free Lunch theorem
(Wolpert and Waters, 1994) implies that we can’t guarantee a small
generalization error, but may still be able to guarantee a small difference
between the training and generalization error (generalization gap), or a small
generalization error for some training sets (for data-dependent bounds).

  * •

Realizable bounds. For _realizable_ bounds, the data distribution and the
algorithm are assumed to be such that $\hat{\epsilon}(\mathcal{A}(S))=0$ for
any $S$ which has non-zero probability. This is saying that the algorithm is
always able to fit the data perfectly. Note that this is a combined assumption
about the algorithm (for instance the expressivity of its hypothesis class)
and the data distribution. If the algorithm is _fully expressive_ (able to
express any function), and minimizes the training error (it belongs to the
class of _empirical risk minimization_ (ERM) algorithms), then this condition
doesn’t put any constraint on $\mathcal{D}$ beyond being noiseless.

For the realizable case, bounds usually take the form

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\epsilon(\mathcal{A}(S))\leq\frac{f_{\mathcal{A}}(S)}{m}\right]\geq
1-\delta$ (3)

where we have omitted (without loss of generality), the exponent $\alpha$,
because realizable bounds have $\alpha=1$ in most cases (The reason for this
exponent comes fundamentally from the non-Gaussian behaviour of the tail of
the binomial distribution when the mean is close to zero (Langford, 2005).).

Statistical learning theory has focused on these two classes of assumptions,
because they are considered to be minimal, and cover most cases of interest.
However, other assumptions on $\mathcal{D}$ are sometimes used in more
advanced analyses, typically involving data-dependent and non-uniform bounds
(see below).

In this context it is interesting to compare a frequentist to a Bayesian
approach to assumptions on the data. In the former case, one only assumes that
$\mathcal{D}$ belongs to a restricted set of possible data distributions. This
approach naturally leads to to studying the worst case generalization over
that set. In a Bayesian approach, one assumes a prior over data distributions,
and then studies the typical or average case generalization. Most of bounds we
will describe here use the frequentist approach, but there have been some
interesting results using a Bayesian prior over data distributions, see
section 4.5.

#### 3.3.2 According to assumptions on the algorithm $\mathcal{A}$

As is the case for $\mathcal{D}$, supervised learning theory often makes very
minimal assumptions on the learning algorithm $\mathcal{A}$, though there are
also a rich set of algorithm-dependent analyses. The minimal assumptions made
on $\mathcal{A}$ is that it outputs hypotheses within a set of hypothesiss
called the _hypothesis class_ $\mathcal{H}$. As this is the minimal assumption
often made, we will refer to it as “algorithm-independent” to distinguish it
from the approaches which make stronger assumptions. We thus classify bounds
on the following two classes.

  * •

Algorithm-independent bounds. These bounds only assume that
$\mathcal{A}(S)\in\mathcal{H}$, for all $S$444or for all $S$ within a set of
$S$ which have support $1-\delta$, as in Nagarajan and Kolter (2019).
Furthermore, the capacity $f_{\mathcal{A}}(S)$ can only depend on
$h=\mathcal{A}(S)$ and $S$, and not in a general way on $\mathcal{A}$555We
include this constraint because otherwise there wouldn’t be any useful
distinction with algorithm-dependent bounds. We could just take a set of
algorithm-dependent bounds that cover all algorithms with outputs in
$\mathcal{H}$, and make an “algorithm-independent bound”. We choose the
definition to avoid this possibility.. This definition means that bounds in
this class must bound the generalization gap or the generalization
error666Under these definitions, realizable bounds should technically be
algorithm-dependent, because they assume something beyond the hypothesis class
of the algorithm – they assume that the algorithm is ERM. However, we will
still refer to bounds that only add this extra assumption as algorithm
dependent, as the ERM assumption may be considered as being relatively weak.
However, this distinction becomes important when discussing some subtleties,
like those in section 3.3.4. for the worst case hypothesis $h$ from a
hypothesis class $\mathcal{H}$. We can therefore write bounds in this class in
the following way

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\forall
h\in\mathcal{H},~{}D(\epsilon(h),\hat{\epsilon}(h))\leq\frac{f(S,h)}{m^{\alpha}}\right]\geq
1-\delta$ (4)

Algorithm-independent bounds are commonly classified in two classes, according
to the dependence of the capacity $f(S,h)$ on $h$:

    * –

Uniform convergence bounds (or _uniform bounds_ for short) are algorithm-
independent bounds where the capacity is independent of $h$. This includes VC
dimension bounds (section 4.1.1) and Rademacher complexity bounds (section
4.1.2). Here the nomenclature "uniform" means the value of the bound is
independent of the hypothesis.

    * –

Non-uniform convergence bounds (or _non-uniform bounds_ for short) are
algorithm-independent bounds where the capacity depends on $h$. Common
examples include bounds for structural risk minimization (section 4.2.1.1).

  * •

Algorithm-dependent bounds. This type of bounds generalizes the above class of
bounds by considering stronger, or more general, assumptions on $\mathcal{A}$,
as well as more general dependence of the capacity on $\mathcal{A}$. We can
express this general class of bounds as

$\forall\mathcal{A}\in\mathfrak{A},~{}\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[D(\epsilon(\mathcal{A}(S))),\hat{\epsilon}(\mathcal{A}(S)))\leq\frac{f_{\mathcal{A}}(S)}{m^{\alpha}}\right]\geq
1-\delta$ (5)

where $\mathfrak{A}$ is a set of algorithms that represents our assumptions on
$\mathcal{A}$. An example of this class of bounds are stability-based bounds
(section 4.3.1), which rely on the assumption that the algorithm’s output
$\mathcal{A}(S)$ doesn’t depend strongly on $S$. The case where
$\mathfrak{A}=\\{\mathcal{A}\\}$ corresponds to the analysis of a particular
algorithm. We will refer to this special case as _algorithm-specific bounds_.
However, in almost all cases, analyses of particular algorithms rely only on a
subset of the properties of the algorithm, so that the results often apply
more generally and are not restricted to a specific algorithm.

#### 3.3.3 According to dependence of capacity on training set $S$

Another classification on bounds is according to the dependence of the
capacity $f$ on the training dataset $S$. For any of the classes of bounds
discussed above, we further distinguish the following two classes of bounds.

  * •

Data-independent bounds are bounds in which the capacity does not depend on
$S$. Common examples include VC dimension bounds, and the simple (algorithm-
independent) bounds based on SRM (e.g. eq. 10, and eq. 12).

  * •

Data-dependent bounds are bounds in which the capacity depends on $S$. Common
examples are Rademacher complexity bounds. The PAC-Bayes bounds for Bayesian
algorithms (such as the one we present in theorem 5.1) is another example.

Note that in this paper we do not consider explicitly data-distribution-
dependent bounds, because we only consider bounds that depend on quantities
derivable from $S$. However, we will consider the behaviour of bounds under
different assumptions on the data distribution $\mathcal{D}$. In particular,
we could look at the expected value of the bound, or its whole distribution,
for different $\mathcal{D}$. This is the sense in which we will discuss “data
distribution dependence” in this paper. Note that only data-dependent bounds,
which depend on $S$, can depend on the data distribution in this sense.

#### 3.3.4 Further comments on non-uniform bounds and algorithm-dependent
bounds

A common way to derive algorithm-dependent bounds is to start with non-uniform
convergence bounds, and then make further assumptions on the algorithm which
restrict the set of $h$ that may be returned for a given $S$. We can then use
the maximum value of the bound among those $h$ as an algorithm-dependent bound
valid for algorithms which satisfy the assumptions. Note that this makes the
bound automatically data-dependent. This can be expressed by bounds of the
form

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\forall
h\in\mathcal{H}(S),~{}D(\epsilon(h),\hat{\epsilon}(h))\leq\frac{f(S,h)}{m^{\alpha}}\right]\geq
1-\delta$ (6)

where $\mathcal{H}(S)$ is a set which includes $\mathcal{A}(S)$ for the class
of algorithms $\mathfrak{A}$ which we are considering. This is what is done,
for example, for margin bounds (section 4.2.1.2) for max-margin classifiers,
like SVMs, where we assume the algorithm will output an $h$ which maximizes
margin, and then plug that condition into a non-uniform margin bound (by
setting $\mathcal{H}(S)$ to be the set of max margin classifiers for $S$).

Non-uniform bounds are often designed with particular assumptions on the
algorithm and dataset in mind. This is because the value of non-uniform bounds
depends on both $\mathcal{A}$ and $\mathcal{D}$. This in turn means that the
notion of optimality for non-uniform (and algorithm and data-dependent bounds
in general) should also depend on $\mathcal{A}$ and $\mathcal{D}$ as argued in
section 6.

In the applications to deep learning theory we study, non-uniform convergence
bounds are only used as a way to obtain algorithm-dependent bounds, though we
still present the fundamental non-uniform bounds in section 4.2.1.1 as useful
background for the algorithm-dependent bounds based on them.

In a recent influential paper, Nagarajan and Kolter (2019) showed that for
SGD-trained networks, the tightest777“Tightest” in their analysis refers to
the fact that their bound is specific for the particular algorithm they study
(SGD-trained DNNs), and the particular dataset (which was synthetically
constructed) double-sided bounds based on uniform convergence give loose
bounds for certain families of data distributions. In appendix G.4 they extend
this result to include all algorithm-dependent bounds for which the capacity
is only allowed to depend on the output of the algorithm $\mathcal{A}(S)$ and
has no other data-dependence beyond this, while in Appendix J, they show that
these limitations also apply to standard deterministic PAC-Bayes bounds based
on the general KL-divergence-based PAC-Bayes bound (eq. 13). The intuition
behind these results is that this kind of bounds can encode little information
about the algorithm beyond the hypothesis class, as they can not explicitly
capture the dependence of $\mathcal{A}(S)$ on $S$.

Most algorithm-dependent bounds derived from non-uniform bounds that we will
study are based on data-independent non-uniform bounds. This fact
automatically makes the algorithm-dependent bounds have a capacity that only
depends on $\mathcal{A}(S)$, and so they would suffer from the limitations
pointed out in Nagarajan and Kolter (2019). Inspired by this result, we chose
to classify algorithm-dependent bounds into those that are based on non-
uniform convergence and those that are not.

It is also worth noting that there are several different ways to “get around”
the limitations in Nagarajan and Kolter (2019). 1) The analysis of Nagarajan
and Kolter (2019) finds a family of distributions where the class of bounds we
discuss above fail. However, it doesn’t discard the possibility that these
bounds may give tight predictions for other data distributions. 2) We can
allow an algorithm-dependent bound to depend on the data in other ways than
via $h$ (e.g. by having explicit dependence on $S$ as in Shawe-Taylor et al.
(1998); Shawe-Taylor and Williamson (1997)) 3) Negrea et al. (2019) showed
that one can still seize uniform convergence for the distributions that
Nagarajan and Kolter (2019) study by bounding the risk difference between
$\mathcal{A}(S)$ and an $h$ in a class for which uniform convergence gives
tight bounds. 4) We can consider non-double-sided bounds. Bounds derived from
an analysis assuming realizability can satisfy 2) and 4). They can satisfy 2)
because they only guarantee convergence on a hypothesis class which depends on
the data (the set of $h\in\mathcal{H}$ with $0$ error). Bounds considered by
Nagarajan and Kolter (2019), even if they can depend on $h$, are worst-case
over training sets. However, an analysis which assumes realizability can bound
the generalization gap only for those training sets $S$ where
$\hat{\epsilon}(h)=0$. Realizable bounds can satisfy 4) because they can use
the one-sided version of the Chernoff bound for $0$ mean (Langford, 2005), as
can be seen for example in the Corollary 2.3 in Shalev-Shwartz and Ben-David
(2014). Note that realisable bounds derived from agnostic bounds (by setting
$\hat{\epsilon}(h)=0$) will still suffer from the limitations that Nagarajan
and Kolter (2019) point out, because agnostic bounds themselves do not satisfy
the conditions above. Therefore, only bounds which take full advantage of the
realizable assumption may avoid the limitations in Nagarajan and Kolter
(2019).

We note that the marginal likelihood PAC-Bayes bound we present in section 5
is based on a realizable analysis using one-sided bounds and thus avoids the
limitations of double-sided bounds discussed above. In fact, our bound holds
with high probability over the Bayesian posterior, rather than universally
over a whole family of hypothesis-dependent posteriors, as usually considered
by deterministic PAC-Bayes bounds (Nagarajan and Kolter, 2019).

#### 3.3.5 Overview of bounds

|  Algorithm-independent |  |
---|---|---|---
(section 4.1) |  Algorithm-dependent |  |
(section 4.2) |  |  |  |
|  Based on uniform convergence |  Based on non-uniform |
convergence |  Other |  |  |
Data- independent |  VC dimension bound* (section 4.1.1) |  SRM-based bounds$\dagger$ (section 4.2.1.1) | \-  |  uniform stability bounds$\ddagger$ and compression bounds$\mathsection$ (section 4.3.1)
Data-dependent |  Rademacher complexity bound$\mathparagraph$ (section 4.1.2) |  data-dependent SRM-based bounds** (section 4.2.1.1) |  margin bounds$\dagger\dagger$ (4.2.1.2),
sensitivity-based bounds$\ddagger\ddagger$ (section 4.2.1.4),
NTK-based bounds$\mathsection\mathsection$ (section 4.2.1.3),
other PAC-Bayes bounds$\mathparagraph\mathparagraph$ (section 4.2.2) |  non-uniform stability bounds*** (section 4.3.1),
marginal-likelihood PAC-Bayes bound$\dagger\dagger\dagger$ (section 5)
Table 1: Classification of the main types of generalization bounds treated in
this paper. Roughly speaking, the number of assumptions grows going from left
to right, and from top to bottom. Note that, as we discussed in section 3.3.4,
algorithm dependent bounds based on non-uniform convergence are automatically
data-dependent, which is why there is an empty cell. *Vapnik and Chervonenkis
(1974); Blumer et al. (1989); Harvey et al. (2017) $\dagger$Vapnik (1995);
McAllester (1998) $\ddagger$Bousquet and Elisseeff (2002); Hardt et al.
(2016); Mou et al. (2018) $\mathsection$Littlestone and Warmuth (1986);
Brutzkus et al. (2018) $\mathparagraph$Bartlett and Mendelson (2002) **Shawe-
Taylor et al. (1998); Shawe-Taylor and Williamson (1997)
$\dagger\dagger$Bartlett (1997, 1998); Bartlett et al. (2017); Neyshabur et
al. (2018a); Golowich et al. (2018); Neyshabur et al. (2018b); Barron and
Klusowski (2019) $\ddagger\ddagger$Neyshabur et al. (2017); Dziugaite and Roy
(2017); Arora et al. (2018); Banerjee et al. (2020)
$\mathsection\mathsection$Arora et al. (2019); Cao and Gu (2019)
$\mathparagraph\mathparagraph$Zhou et al. (2018); Dziugaite and Roy (2018)
***Kuzborskij and Lampert (2017) $\dagger\dagger\dagger$Valle-Pérez et al.
(2018)

In the next sections of this paper, we will describe the major families of
generalization error bounds that have been applied to DNNs. While we don’t
claim that the list is exhaustive, we tried to cover all the major approaches
to generalization bounds.

In section 3.3.5 we present a high-level overview of where different general
classes of bounds found in the literature fit within the classification
introduced above. It also lists which bounds we treat explicitly in the rest
of the paper, and where they sit in our taxonomy. Thus the table helps
illustrate what kinds of general assumptions go into the different bounds.

Given this hierarchy of the main types of bounds, we next turn to a comparison
of their performance. As expected, the overall empirical performance of the
bounds improves as more assumptions are added.

## 4 Comparing existing bounds against desiderata

In this section we use the taxonomy from section 3 (illustrated in table
section 3.3.5) to organise a discussion on how different bounds fare against
the desiderata proposed in section 2. We use a ✗ when there is strong evidence
that bounds in this family fail to satisfy most important aspects of the
desiderata, ✓ when there is strong evidence that bounds in the family satisfy
most important aspects of the desiderata, and ⚫ otherwise. We are aware these
are not formally defined notions, and the marks should just be taken as an aid
for the reader.

###  4.1 Algorithm-independent bounds

#### 4.1.1 Data-independent uniform convergence bounds: VC dimension

One of the iconic results in the theory of generalization is the notion of
uniform convergence introduced by Vapnik and Chervonenkis (Vapnik and
Chervonenkis, 1974) which, expressed in the language of PAC learning (Blumer
et al., 1989), considers _data-independent_ uniform convergence bounds, where
the capacity $f_{\mathcal{H}}(S)$ doesn’t depend on $S$, but only on the
hypothesis class $\mathcal{H}$. The main result of this theory is that the
optimal bound of this form (up to a multiplicative fixed constant) for the
generalization gap, in the case of binary classification is

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\sup_{h\in\mathcal{H}}|\epsilon(h)-\hat{\epsilon}(h)|\leq
C\sqrt{\frac{\text{VC}(\mathcal{H})+\ln{\frac{1}{\delta}}}{m}}\right]\geq
1-\delta$ (7)

for some constant $C$, and where $\text{VC}(\mathcal{H})$ is a combinatorial
quantity called the Vapnik-Chervonenkis dimension (Shalev-Shwartz and Ben-
David, 2014), which depends on the hypothesis class $\mathcal{H}$ alone. In
the realizable case, they also proved that the optimal realizable data-
independent uniform bound is

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\sup_{h\in\mathcal{H}_{0}(S)}\epsilon(h)\leq
C\frac{\text{VC}(\mathcal{H})+\ln{\frac{1}{\delta}}}{m}\right]\geq 1-\delta$
(8)

for some constant $C$, and where $\mathcal{H}_{0}(S)$ is the set of all
$h\in\mathcal{H}$ with zero training error on $S$. The particular
realizability assumption here is that $\mathcal{D}$ should be such that for
all $S$, $\mathcal{H}_{0}(S)$ is non-empty.

How does this bound do at the desiderata?

  * •

D.1 ✗ The bound is data-independent by construction, and therefore its value
is the same for any data distribution or training set.

  * •

D.2 ✗ The bound decreases with training set size, but a rate $O(1/m)$ which is
independent of the dataset, unlike what is observed in practice
($O(m^{-\alpha})$ for a range of $m$, for $\alpha$ often significantly smaller
than $1$). Recently, Bousquet et al. (2020) pointed out that a fundamental
reason why data-independent uniform convergence bounds don’t capture the
behaviour of learning curves is because the worst-case distribution
$\mathcal{D}$ can depend on $m$, so that the VC bound bounds an ‘envelope’ of
the actual learning curves for individual $\mathcal{D}$, and this envelope may
have a markedly different form with respect to $m$ than the individual
learning curves.

  * •

D.3 ✗ The VC dimension can capture differences in architectures. However, it
doesn’t appear to capture the correct trends. For example, VC dimension grows
with the number of parameters (Baum and Haussler, 1989; Harvey et al., 2017),
while for neural networks the generalization error tends to decrease (or at
least not increase) with increased overparametrization (Neyshabur et al.,
2019).

  * •

D.4 ✗ The bound is only dependent on the algorithm via the hypothesis class.
Therefore it won’t capture any algorithm-dependent behaviour except for
regularization techniques that restrict the hypothesis class.

  * •

D.5 ✗ The VC dimension of neural networks used in modern deep learning is
typically much larger than the number of training examples (Zhang et al.,
2017), thus leading to vacuous VC-dimension bounds.

  * •

D.6 ✓ Although computing the exact VC dimension of neural networks is
intractable, there are good approximations and bounds which are easily
computable (Harvey et al., 2017).

  * •

D.7 ✓ The VC dimension offers a rigorous bound with minimal assumptions.
Therefore, its guarantees are rigorously applicable to many cases.

A common way to interpret the VC dimension bound is in terms of bias-variance
tradeoff (Neal et al., 2018; Neal, 2019), which is a simple heuristic that is
widely used in machine learning. Bias-variance tradeoff captures the intuition
that there is a tradeoff between a model being too simple, when it cannot
properly represent the data (large bias), and a model being too complex (large
capacity) when it will tend to overfit, leading to large variance on unseen
data. For the bound eq. 7 we can identify $\hat{\epsilon}(h)$ as measuring the
bias, and the term involving the VC dimension as indicative of the variance.
Intuitively, increasing the VC dimension can make $\hat{\epsilon}(h)$ smaller
by increasing the capacity, at the expense of higher variance (the second
term), so that one may expect to see a U-shaped curve of generalization error
versus model complexity.

Many empirical works have shown that, once in the overparameterized regime,
DNNs in fact typically show a monontonic decrease in generalization error as
overparametrization increases, unlike what the VC dimension bound would
suggest (Lawrence et al., 1998; Neyshabur et al., 2019; Belkin et al., 2019).
As the VC dimension bound is optimal among data-independent algorithm-
independent bounds, these results tell us that this class of bounds is
fundamentally unable to explain the generalization of overparametrized neural
networks.

Intuitively, it is not surprising that the VC dimension bound cannot capture
this behaviour. As overparametrization increases, the model is able to express
more functions, and so the worst-case generalization in the hypothesis class
can only get worse. What the VC dimension measure (or for that matter naive
applications of the bias-variance tradeoff heuristic in terms of
overparameterization) is not capturing is: 1) the strong inductive bias within
the hypothesis class which DNNs have; 2) that the effective expressivity of
the model can depend on the data. That is, we need to look for bounds that are
algorithm-dependent and/or data-dependent. In the following section, we will
look at algorithm-independent data-dependent bounds, and we will see that
data-dependence alone is not enough, so that a bound which takes the inductive
bias into account is necessary to explain generalization of overparamtrized
DNNs.

#### 4.1.2 Data-dependent uniform convergence bounds: Rademacher complexity

As a first step to include data dependence, we consider a classic data-
dependent uniform convergence bound of the form eq. 4 for algorithm
independent uniform bounds, where $D$ is the absolute value function, and the
capacity $f(S,h)$ is independent of $h$. It is given by:

$\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\sup_{h\in\mathcal{H}}|\epsilon(h)-\hat{\epsilon}(h)|\leq
2\mathcal{R}(L\circ\mathcal{H}\circ
S)+4c\sqrt{\frac{2\ln{(4/\delta)}}{m}}\right]\geq 1-\delta$ (9)

where $c$ is a constant, and $\mathcal{R}(L\circ\mathcal{H}\circ S)$ is the
Rademacher complexity of the set of vectors $L\circ\mathcal{H}\circ
S=\\{(L(x_{i},h(x_{i})))_{i=1}^{m}:h\in\mathcal{H}\\}\subseteq\mathbb{R}^{m}$
where $x_{i}$ are the input points in $S$ (Bartlett and Mendelson, 2002;
Shalev-Shwartz and Ben-David, 2014). There is also a lower bound which matches
it up to a constant and up to an additive term of $O(1/\sqrt{m})$ (Bartlett
and Mendelson, 2002; Koltchinskii, 2011). Therefore whether this bound is the
optimal data-dependent uniform generalization gap bound up to a constant,
depends on the rate of the Rademacher complexity with $m$. Bounds on the
Rademacher complexity tend to be of $O(1/\sqrt{m})$ but they often dominate
the second term, so that the lower and the upper bound match in their first
order behaviour, suggesting that the bound in eq. 9 may often be close to
optimal within this class of bounds.

Rademacher complexity bounds for neural networks typically rely on a bound on
the norm of the weights (Bartlett and Mendelson, 2002), which typically grows
with overparametrization. The lesson we learn is that although Rademacher
bounds are data-dependent, they are still worst-case over algorithms with
hypothesis class $\mathcal{H}$. Given that DNNs can express functions that
generalize badly (Zhang et al., 2017), it is thus not surprising that
Rademacher complexity bounds are vacuous, and suffer from similar problems as
VC dimension bounds.

We note that Rademacher complexity has also been used as a tool in analyses
which take into account more properties of the algorithm, for example for
bounds based on non-uniform convergence. In this paper we will treat these
other bounds separately, mainly in section 4.2.1.2, when looking at margin
bounds. We will nevertheless briefly comment on these margin bounds in the
desiderata below, as they have been studied more thoroughly, and may give
insights into Rademacher complexity more generally.

The performance of the Rademacher complexity-based bounds on our desiderata
can be found below:

  * •

D.1 ✗ The bound is data-dependent, and could capture some dependence in the
dataset. However, it only depends on the distribution over inputs, and
therefore it can’t depend on the complexity of the target function, when the
input distribution is fixed. This is unlike real neural networks which
generalize worse when the labels are corrupted (Zhang et al., 2017).

  * •

D.2 ✗ Bounds on the Rademacher complexity are typically $O(1/\sqrt{m})$, thus
not capturing the behaviour of learning curves. Furthermore, margin-based
bounds (which are based on norm-based bounds to the Rademacher complexity),
often _increase_ with $m$. See section 4.2.1.2.

  * •

D.3 ✗ As Rademacher complexity captures a notion of expressivity, similarly to
VC dimension, it often grows with overparametrization and number of layers
(see for example, the norm-based bounds on section 4.2.1.2). It seems unlikely
it could capture other architectural differences.

  * •

D.4 ✗ Like the VC dimension bound, it is only dependent on the algorithm via
the hypothesis class. The most studied hyperparameter to compare hypothesis
classes in this context is the norms of the weights of the DNN. As we comment
in section 4.2.1.2, these bounds appear to anti-correlate with the true error
when changing several common optimization hyperparameters.

  * •

D.5 ✗ Like the VC dimension bound, these bounds are typically vacuous in the
overparametrized regime. In fact, it has recently been shown that there are
data distributions where the _tightest_ double-sided distribution-dependent
uniform convergence bounds for several SGD-trained models are provably vacuous
(Nagarajan and Kolter, 2019). This implies that the distribution-dependent
data-independent version of the Rademacher complexity bound (Shalev-Shwartz
and Ben-David, 2014), and thus that the eq. 9 is also vacuous for that data
distribution. Although for other data distributions the bounds may not be
vacuous, this work suggest that uniform convergence bounds have some
fundamental limitations (see section 3.3.4 for further discussion on this
issue).

  * •

D.6 ✓ Same as for VC dimension bounds.

  * •

D.7 ✓ Same as for VC dimension bounds.

Although some fundamental limitations of VC dimension are overcome by
Rademacher bounds, the bounds that currently exist for neural networks based
on Rademacher complexity have very similar problems to those based on VC
dimension. Although their capacity measure is data-dependent, for the problems
in which DNNs are applied, these bounds still give vacuous predictions and
grow with the number of parameters. This observation, combined with the fact
that the bounds may be optimal among uniform generalization gap bounds,
suggests that to overcome the limitations highlighted here we will need to
consider data-dependent non-uniform and algorithmic-dependent bounds.

Note that, although one can prove that the VC dimension (and perhaps for
Rademacher complexity) bound is optimal within its class of bounds, for data-
dependent bounds this won’t be in general possible. As we discuss in section 6
whether one bound is tighter than another depends on what prior assumptions
are made on the data distribution, so that a unique notion of optimality may
not exist.

###  4.2 Algorithm-dependent bounds

In this section we consider the major classes of algorithm-dependent bounds
and how they fare at satisfying the desiderata. We focus on realizable bounds
(which assume zero training error), because modern deep learning often works
in this regime (Zhang et al., 2017). For many of the recent bounds for deep
learning, the lack of experiments means that we can’t conclusively answer
whether they satisfy several of the desiderata. We hope that future work can
fill these gaps.

#### 4.2.1 Algorithm-dependent bounds based on non-uniform convergence

We start by looking at algorithm-dependent bounds derived from non-uniform
convergence bounds (see also section 3.3.4). We begin by presenting in the
next section the basic types of non-uniform bounds, before seeing the two main
applications for deep learning in the next two sections: margin bounds, and
sensitivity-based bounds. We will also briefly comment on some other
approaches to apply PAC-Bayes to deep learning that have been proposed.

#####  4.2.1.1 Basic non-uniform convergence bounds and structural risk
minimization

The simplest and most fundamental idea to make non-uniform bounds is related
to a learning technique called structural risk minimization (SRM) developed by
Vapnik and Chevonenkis (Vapnik, 1995). The derivation of this bound is very
similar to the classic textbook PAC bound (see e.g. corollary 2.3 in Shalev-
Shwartz and Ben-David (2014)), but rather than using a uniform union bound, it
uses a nonuniform union bound over the hypothesis class to prove that for any
countable hypothesis class $\mathcal{H}$ and any distribution over hypotheses
$P$ (McAllester, 1998; Shalev-Shwartz and Ben-David, 2014):

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\forall
h\in\mathcal{H}~{}\textrm{such that
}\hat{\epsilon}(h)=0,~{}\epsilon(h)\leq\frac{\ln{\frac{1}{P(h)}}+\ln{\frac{1}{\delta}}}{m}\right]\geq
1-\delta.$ (10)

First, as expected, this bound reduces to the standard uniform finite-class
PAC bound (Valiant, 1984), when $P$ is a uniform distribution
$P(h)=1/|\mathcal{H}|$. What eq. 10 tells us is that if we have a learning
algorithm and a problem for which we have prior knowledge that some functions
$h$ are more likely to be learned than others, then we can obtain tighter
bounds by choosing a $P$ that assigns a higher value to these $h$. One way to
intuitively understand how this knowledge affects the bound is to consider the
limit where $P$ is highly concentrated on a subset of $\mathcal{H}$, and
approximately uniform within that subset. Then eq. 10 approaches the finite-
class uniform PAC bound for a reduced hypothesis class and the capacity can be
interpreted as measuring an “effective size” of the hypothesis class.

Another way to think about this is that choosing a $P$ amounts to “betting”
that some $h$ are more likely to appear. If we are right, then our bound will
be better in practice than the standard finite-class PAC bound, while if we
are wrong and we get $h$ with low $P$, then this bound will perform worse. In
other words, unlike the uniform finite-class PAC bound, eq. 10 depends on the
$h$ we get, so that in order to evaluate its performance, we need to take into
account the data distribution and the algorithm (which together determine the
probability distribution over $h$ which the learning algorithm outputs), and
work with an expected value of the generalization error.

To define an expected value of the bound, we assume a distribution over data
distributions $\mathcal{D}$, which we call the prior $\Pi$. For example, this
may be fully supported on a single $\mathcal{D}$ if we know the distribution
fully (perhaps we are looking only at the images in CIFAR10). In more real-
world settings, we will have uncertainty over what the true distribution is,
but we may believe that certain distributions (e.g. simpler ones) are more
likely. We consider a stochastic learning algorithm which, for training set
$S$, outputs hypotheses with a probability $Q(h|S)$ (called the _posterior_
(which need not be the Bayesian posterior). Under these two assumptions, it is
not hard to see that, for a given distribution $P$ over hypotheses, the
expected value of the capacity $\ln{\frac{1}{P(h)}}$ in the bound eq. 10 is
given by

$\mathbf{E}_{\mathcal{D}\sim\Pi,S\sim\mathcal{D}^{m},h\sim
Q(h|S)}\left[-\log{P(h)}\right]=\mathbf{E}_{h\sim\tilde{Q}}\left[-\log{P(h)}\right]\equiv
H(\tilde{Q},P)$ (11)

where $H(\cdot,\cdot)$ is the cross-entropy, and
$\tilde{Q}(h)=\mathbf{E}_{\mathcal{D}\sim\Pi,S\sim\mathcal{D}^{m}}[Q(h|S)]$ is
the posterior averaged over training sets and data distributions. The second
equality follows from the definition of cross-entropy. We can immediately see
that the optimal bound of this form, for a given prior $\Pi$ and algorithm
with posterior $Q(h|S)$ is obtained by the choice $P=\tilde{Q}$, in which case
we obtain $H(\tilde{Q})$ where $H$ is the entropy. This calculation formalizes
the intuition that we should choose $P$ to be as close as possible to the
probabilities of obtaining different $h$ for the algorithm and task at hand.
It also strengthens the intuition that this bound is capturing a notion of
effective size, as $H(\tilde{Q})$ is often interpreted as the logarithm of the
effective number of elements where $\tilde{Q}$ is concentrated.

Furthermore, we can consider the case where $Q(h|S)$ is given by the Bayesian
posterior for prior $\Pi$. In this case, $\tilde{Q}=\tilde{\Pi}$, where
$\tilde{\Pi}$ is the prior distribution over hypotheses $h$, obtained by
marginalizing over input distributions $\mathcal{D}_{X}$888Note that, unless
we restricted to the noiseless case, these would be stochastic hypotheses
corresponding to $\mathcal{D}_{Y|X}$ as defined in section 3.1.. The average
capacity in this case is $H(\tilde{\Pi})$. This is conceptually similar to the
No Free Lunch theorem, in that it tells us that for the optimal algorithm, the
bound only guarantees good generalization if we make enough assumptions about
the data distribution (which corresponds to a low entropy $H(\tilde{\Pi})$).
We note, however, that the Bayesian posterior may not give the optimal value
of the bound, as can be seen from the fact that $H(\tilde{Q},P)$ is always
lowered by making $Q(h|S)$ deterministic (as it would lower $H(\tilde{Q})$),
while the Bayesian posterior is not deterministic in general.

The problem with the basic non-uniform SRM bound eq. 10 is that it does not
capture the idea that some functions may be more similar to others, which
quantities such as VC dimension and Rademacher complexity do capture999For
example, the VC dimension of a set of functions which are very similar to each
other will typically be lower than a set of very dissimilar functions. The
generalized version of SRM bound which we present below has the advantage of
being non-uniform but being able to capture some notion of similarity among
function within the subclasses $\mathcal{H}_{i}$.

A more commonly-used extension of the basic SRM bound considers dividing the
(now potentially uncountable) hypothesis class $\mathcal{H}$ into a countable
set of (usually nested) subclasses $\mathcal{H}_{i}$, $i\in\mathbb{N}$, such
that $\bigcup_{i}\mathcal{H}_{i}=\mathcal{H}$. The result is that for any
distribution $P$ over $\mathbb{N}$ (Shalev-Shwartz and Ben-David, 2014), we
have:

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\forall
i\in\mathbb{N}~{}\forall h\in\mathcal{H}_{i}~{}\textrm{such that
}\hat{\epsilon}(h)=0,~{}\epsilon(h)\leq\frac{\ln{\frac{1}{P(i)}}+f_{i}(S)+\ln{\frac{1}{\delta}}}{m}\right]\geq
1-\delta$ (12)

where $f_{i}(S)$ is any (potentially data-dependent) capacity for class
$\mathcal{H}_{i}$ which guarantees uniform convergence within
$\mathcal{H}_{i}$ (for example, a bound on its VC dimension or Rademacher
complexity). Results of this form are proven in Shawe-Taylor et al. (1998) and
Shalev-Shwartz and Ben-David (2014).

We can also compute the expected value of the bound eq. 12, analogously to eq.
10. For the numerator of the bound (ignoring the confidence term), we obtain
$H(\tilde{Q}^{\prime},P)+\mathbf{E}_{i\sim\tilde{Q}^{\prime}}\left[f_{i}(S)\right]$,
where
$\tilde{Q}^{\prime}(i)\equiv\textbf{P}_{h\sim\tilde{Q}}\left[\text{class}(h)=i\right]$
and $\text{class}(h)$ represents the index of the subclass
$\mathcal{H}_{\text{class}(h)}$ to which $h$ belongs. Analogously to before,
the optimal value of $P$ is given by $\tilde{Q}^{\prime}$, and the Bayesian
posterior will in general not result in the optimal average value of the
bound.

One shortcoming of eq. 12 is that the decomposition of $\mathcal{H}$ into
$\mathcal{H}_{i}$ has to be defined a priori, that is, it cannot depend on
$S$. Shawe-Taylor et al. (1998) proposed an extension to the SRM framework
which addressed this shortcoming, and defined a potentially infinite hierarchy
of subclasses $\mathcal{H}_{1}(S)\subseteq\mathcal{H}_{2}(S)\subseteq...$
which could depend on the data $S$. This framework includes as a special case
the margin bounds we will see in section 4.2.1.2.

Shawe-Taylor and Williamson (1997) applied the data-dependent SRM framework to
obtain bounds for a parametrized model, where the capacity was related to the
volume in parameter space of a sphere contained within the set of parameters
producing zero training error. This work inspired the development of the first
PAC-Bayes bounds in McAllester (1998)101010Although Shawe-Taylor and
Williamson (1997) is often cited as a precursor to PAC-Bayes (Shawe-Taylor,
2019), it offers a distinct analysis (for example, it gives deterministic
bounds rather than bounds on expected error), which as far as the authors know
hasn’t been shown to necessarily give stronger or weaker bounds than PAC-
Bayes, and hasn’t been applied to neural networks.. These bounds apply for
stochastic learning algorithms, and bound the expected value of the
generalization error under the posterior $Q(h|S)$, uniformly over posteriors.
The standard form of the general PAC Bayes bound was proven by Maurer (2004)
and states, for any distribution $P$ over $\mathcal{H}$,

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\forall
Q~{}KL(\mathbf{E}_{h\sim Q}[\epsilon(h)],\mathbf{E}_{h\sim
Q}[\hat{\epsilon}(h)])\leq\frac{KL(Q||P)+\ln{\frac{1}{\delta}}+\ln{(2m)}}{m-1}\right]\geq
1-\delta$ (13)

where $KL(Q||P)$ is the KL-divergence between $Q$ and $P$. On the left hand
side we use the standard abuse of notation to define $KL(a,b)\equiv
a\ln{(a/b)}+(1-a)\ln{((1-a)/(1-b))}$, for $a,b\in[0,1]$.

This bound can be seen to generalize the SRM with data-dependent hierarchies
of Shawe-Taylor et al. (1998), where instead of “hard” subdivisions of
$\mathcal{H}$ into $\mathcal{H}_{i}$, we consider all possible distributions
$Q$ on $\mathcal{H}$. $KL(Q,P)$ is analogous to $\ln{\frac{1}{P(i)}}$ in eq.
12 in that it very roughly measures how much of the total probability mass of
$P$ is in the high probability region of $Q$. The term which penalizes
“classes” of $h$ which are too diverse, analogously to $f_{i}(S)$, is
$\mathbf{E}_{h\sim Q}[\hat{\epsilon}(h)$, the average training error, because
this is only small if the functions agree on $S$, which will only happen with
high probability if they are sufficiently similar. These analogies between the
data-dependent SRM bounds and PAC-Bayes are only intuitive, but we conjecture
that a more formal connection might be possible.

The PAC-Bayes bound in eq. 13 is one of the most general non-uniform data-
dependent bounds, and its different applications give rise to sensitivity-
based bounds (section 4.2.1.4) among others (section 4.2.2). In fact, margin
bounds can also be derived from PAC-Bayes (Langford and Shawe-Taylor, 2003).

We don’t comment on the desiderata for SRM and the PAC-Bayes bounds described
above, because they provide a general framework for the non-uniform data-
dependent bounds we explore next. We will comment on the desiderata for these
bounds individually.

#####  4.2.1.2 Norm-based and margin bounds

A popular method to obtain data-dependent non-uniform bounds is the method of
margin-based bounds. These usually start with _norm-based bounds_ which bound
the Rademacher complexity of sub-classes of a hypothesis class parametrized by
a parameter vector $w\in\mathcal{W}$ (_weights_) corresponding to balls where
$w$ has a bounded norm. One can then either express the bound under an
assumption on the weight norms, or have the bound depend on the weight norms.
The later case is done by applying an SRM-like bound to the family of
hypothesis sub-classes corresponding to different weight norms. For _margin
bounds_ , the bound is applied to a _margin loss_ , which upper bounds the 0-1
loss. The result is a bound on the generalization error which depends on a new
data-dependent property called _margin_ , which measures how confidently the
classifier is classifying examples. The bound, in the agnostic case, has the
general form, for any margin $\gamma>0$ (Shalev-Shwartz and Ben-David, 2014),

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[\forall
w\in\mathcal{W},~{}\epsilon(w)\leq\hat{\epsilon}_{\gamma}(w)+c_{1}\frac{\lambda(w)}{\gamma\sqrt{m}}+c_{2}\sqrt{\frac{2\ln{(4/\delta)}}{m}}\right]\geq
1-\delta$ (14)

where $c_{1}$ and $c_{2}$ are constants (that may depend on the algorithm but
not on $h$ or $S$, $\lambda(w)$ is a _capacity measure_ which usually measures
the norm of the parameters $w$, and the margin error is defined as
$\hat{\epsilon}_{\gamma}(h)=\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}[h(x_{i})y_{i}<\gamma]$,
for a hypothesis $h$. Note that we usually apply this to real-valued
hypotheses where $\mathcal{Y}=\mathbb{R}$, and for which the classification
error is defined as $\epsilon(h)=\mathbf{P}_{(x,y)\sim\mathcal{D}}[h(x)y<0]$,
where $y\in\\{-1,1\\}$ for binary classification. We abuse notation by writing
$\epsilon(w)$ and $\hat{\epsilon}_{\gamma}(w)$ for the quantities evaluated at
the hypothesis corresponding to parameter $w$. One can also make a bound that
holds (non-uniformly) for all values of $\gamma$ by applying a weighted union
bounds over discretized values of $\gamma$ (Shalev-Shwartz and Ben-David,
2014).

The margin loss $\hat{\epsilon}_{\gamma}(w)$ measures the amount of miss-
classification errors plus some examples which were classified correctly but
with low confidence (measured by $h(x)$ being smaller than $\gamma$). In the
case of linear models, where $h(x)=w\cdot x$ and $\lambda(w)=|w|$, the ratio
$\gamma^{\prime}=\lambda(w)/\gamma$ measures a _geometric margin_ , and the
margin loss measures the number of examples that are not on the right side of
the classification boundary by a distance greater than $\gamma^{\prime}$.
Support vector machines are a famous example of an algorithm trying to
maximize this geometric margin (Cortes and Vapnik, 1995).

For neural networks, margin bounds were originally developed based on the
analysis of their fat-shattering dimension (Bartlett, 1997, 1998). These
bounds depend on the $l_{1}$ norm of the weights, and thus typically grows
with overparmetrization. The bounds also grow exponentially with depth. More
recently, more complex norms of the weights were studied, as well as using the
Lipschitz constant of the network as the capacity measure for margin-bounds
(Bartlett et al., 2017; Neyshabur et al., 2018a; Golowich et al., 2018;
Neyshabur et al., 2018b; Barron and Klusowski, 2019). These bounds have shown
some correlation with the complexity of the data, but suffer from their
(implicit or explicit) dependence on width and depth, and are vacuous
(Neyshabur et al., 2017, 2015; Arora et al., 2018). They also show negative
correlation with the generalization error when changing certain training
hyperparmeters (Jiang et al., 2019).

We now summarize the strengths and weaknesses of margin-based bounds on our
desiderata. Note that most of our conclusions are based on empirical results
on existing margin-based bounds, and may not be fundamental to the margin-
based approach itself.

  * •

D.1 ✓ Margin-based bounds have shown to correlate with the true error when
comparing CIFAR versus MNIST, and when comparing uncorrupted versus corrupted
data (Bartlett et al., 2017; Neyshabur et al., 2017). The correlation should
be explored over a wider range of datasets and quantified more precisely.

  * •

D.2 ⚫ The dependence on the training set size $m$ of margin-based bounds
depend on how the capacity measure changes with $m$. In Nagarajan and Kolter
(2019), it has been shown that several types of the margin-based bounds
proposed for deep neural networks actually increase with training set size!
However, in Dziugaite et al. (2020), other norm and margin-based
generalization measures are found to correlate well with the error when
changing training set size, suggesting that it may be possible to prove better
bounds based on these measures.

  * •

D.3 ⚫ While most margin-based bounds increase with layer width, some
($l_{2}$-path norm bound in Neyshabur et al. (2017) and the bound in Neyshabur
et al. (2018b)) actually decrease with layer width. Regarding variations in
depth, all the proposed bounds increase with number of layers, and most of
them do so exponentially (Neyshabur et al., 2015; Arora et al., 2018; Barron
and Klusowski, 2019). However, the empirical results in Jiang et al. (2019);
Maddox et al. (2020); Dziugaite et al. (2020) show that certain measures (e.g.
path-norm) positively correlate with the error when varying depth.
Furthermore, according to Maddox et al. (2020), the log path-norm correlates
with both width and depth significantly better than path-norm. While no bounds
have been derived that scale like these measures, it may be promising to
consider work in this direction.

  * •

D.4 ⚫ Jiang et al. (2019) show that margin-based bounds that have been
proposed to date appear to often _anti_ -correlate with the generalization
error when changing common optimization hyperparameters (dropout, learning
rate, type of optimizer, etc.). On the other hand, in Dziugaite et al. (2020),
it was demonstrated that some measures such as path norm, often predict
certain properties well when changing learning rate (but they didn’t vary the
other hyperparameters studied in Jiang et al. (2019)).

  * •

D.5 ✗ As far as the authors are aware, all of the margin-based bounds
published to date for DNNs are vacuous (Neyshabur et al., 2017, 2015; Arora et
al., 2018).

  * •

D.6 ✓ Margin-based bounds are often based on a notion of the norm of the
weights that is relatively efficiently computable.

  * •

D.7 ✓ Proposed bounds are based on rigorous theorems with typically weak
assumptions.

#####  4.2.1.3 Bounds based on the neural tangent kernel

It was recently demonstrated that infinite-width DNNs, when trained by SGD
with infinitesimal learning rate, evolve in function space as linear models
with a kernel known as the neural tangent kernel (NTK) (Jacot et al., 2018;
Lee et al., 2019). Several works, either inspired by NTK or not, have relied
on the linearization of the dynamics for wide neural networks. The bounds are
similar to the norm-based bounds in the previous section 4.2.1.2 in that they
tend to bound the Rademacher complexity of hypothesis subclasses characterized
by a norm, usually the norm of the deviation of the weights from
initialiation. The analyses based on NTK are often also able to guarantee
_convergence_ of the optimizer, so that we can also bound the empirical risk
for a sufficiently large number of optimizer iterations. For instance, Arora
et al. (2019) proved that for a sufficiently wide two-layer fully connected
neural network and sufficiently many (full batch) gradient descent steps $t$,
we have

$\forall\mathcal{D},~{}\mathbf{P}_{S\sim\mathcal{D}^{m}}\left[R(h_{t})\leq\sqrt{\frac{2\mathbf{y}^{T}(\mathbf{H}^{\infty})^{-1}\mathbf{y}}{m}}+O\left(\sqrt{\frac{\log{\frac{m}{\lambda_{0}\delta}}}{m}}\right)\right]\geq
1-\delta$ (15)

where $h_{t}$ is the hypothesis learnt by the DNN, $\mathbf{y}$ is the vector
of training outputs $y_{i}$, $\mathbf{H}^{\infty}$ is the Gram matrix for the
inputs in the training set $S$, and $\lambda_{0}$ is a lower bound on the
eigenvalues of $\mathbf{H}^{\infty}$. See Arora et al. (2019) (Theorem 5.1)
for the full statement of the result. The connection to the norm-based bounds
comes from the NTK analysis they carried out, which showed that the Frobenius
norm of the deviation of the weights from initializatoin is bounded by
$\sqrt{\mathbf{y}^{T}(\mathbf{H}^{\infty})^{-1}\mathbf{y}}$ plus higher order
terms. They then used this bound to obtain a data-dependent bound on the
Rademacher complexity. NTK analyses could provide tighter bounds on Rademacher
complexity than those we saw in section 4.2.1.2, because the NTK likely
captures the relation between the parameters and the function the network
implements more precisely than the analyses based on bounding the Lipschitz
constant or similar quantities.

More recently, Cao and Gu (2019) sharpened Arora et al. (2019)’s result with a
similar bound, but which applies to networks with any depth trained with SGD.
In their bound, $\mathbf{H}^{\infty}$ is replaced by the NTK matrix, which
gives a tighter bound.

  * •

D.1 ✓ The NTK-based capacity in Arora et al. (2019) was shown to increase with
amount of label corruption on MNIST and CIFAR, and on MNIST for the capacity
measure in Cao and Gu (2019).

  * •

D.2 ⚫ The authors are not aware of any work studying the dependence of NTK-
based bounds on $m$. The $O(m^{-1/2})$ is not necessarily indicative because
the numerator in the bound likely has non-trivial dependence on $m$.

  * •

D.3 ✗ Like norm-based margin bounds, current NTK-bounds grow with depth (Cao
and Gu, 2019). On the other hand, they show very little dependence on network
width, for large enough width. This is a property of NTK analyses which
matches empirical observations well.

  * •

D.4 ⚫ The authors are not aware of any work studying the dependence of NTK-
bounds on the optimization algorithm. Most analyses focus on vanilla versions
of SGD with specific hyperparameter choices which help the theoretical
analysis. Other optimization algorithms have been shown to have NTK limits
(e.g. momentum in Lee et al. (2019)), but we are not aware of generalization
bounds for these.

  * •

D.5 ⚫ The bounds in Cao and Gu (2019) are non-vacuous (at least up to the
dominant term), but they are not very tight (with values close to $1$ above
$20\%$ label corruption).

  * •

D.6 ✓ The NTK of fully connected networks has an analytical form which is
efficiently computable (Lee et al., 2019). However, for more complex
architectures, it may be necessary to estimate the NTK limit (when it exists,
see Yang (2019a)) via Monte Carlo (Novak et al., 2019).

  * •

D.7 ✓ Proposed bounds are based on rigorous theorems, though the assumptions
on the algorithms and the width are sometimes hard to match in practice (too
large width, or too small learning rate).

#####  4.2.1.4 Sensitivity-based bounds

Many generalization error bounds recently developed and applied to deep
learning are based on the idea that neural networks whose outputs (or loss
function values) are robust to perturbations in the weights may generalize
better. This is linked to the observed phenomenon that flatter minima
empirically generalize better than sharper minima (Hochreiter and Schmidhuber,
1997; Hinton and van Camp, 1993; Zhang et al., 2018; Keskar et al., 2016). At
an informal level, it has been argued that the reason for this correlation is
that flatter minima may correspond to simpler functions (Hochreiter and
Schmidhuber, 1997; Wu et al., 2017). In particular, Hochreiter and Schmidhuber
(1997) link flatness to generalization via the idea of _minimum description
length_ (MDL) (Rissanen, 1978). MDL generalization bounds are formally
equivalent to the simple SRM bound in eq. 10, where $-\log{P(h)}$ is often
interpreted as the length of the string representing $h$ under some prefix-
free code (Shalev-Shwartz and Ben-David, 2014).

A more sophisticated argument linking flatness to generalization is found in
the data-dependent SRM analysis of Shawe-Taylor and Williamson (1997). As we
mentioned in section 4.2.1.1, they proved generalization bounds where the
capacity was mainly controlled by the volume of a region (which they took to
be a ball) in weight space in which the training error was zero. A larger
volume corresponds to a flatter minimum. Note that one difference with
previous work is that Shawe-Taylor and Williamson (1997) define flatness in
terms of the classification error, rather than the loss function (for which
one typically uses the Hessian as a measure of flatness).

Recent theoretical works studying the link between sensitivity, flatness, and
generalization focus on PAC-Bayes analyses (Neyshabur et al., 2017; Jiang et
al., 2019). In the PAC-Bayes bound eq. 13, the $KL(Q,P)$ term is typically
larger when the posterior $Q$ has a larger variance, so that it can “overlap”
with the prior $P$ more. On the other hand to control the average training
error $\mathbf{E}_{h\sim Q}[\hat{\epsilon}(h)]$, we need $Q$ to put most of
its weight on regions of low error. If we combine these two considerations,
the bound typically predicts best generalization for large regions of weight
space with low error (flat minima). However, as shown in Neyshabur et al.
(2017), a more careful look at the PAC-Bayesian analysis suggests that
flatness alone is not sufficient to control capacity and should be
complemented with some other measure such as norm of the weights. In
particular, if $Q$ is taken to be a Gaussian around the weights found after
training, and $P$ is taken to be a Gaussian around the origin, then the
$KL(Q,P)$ term also grows with the norm of the weights. This can be seen in
the bound proposed in Neyshabur et al. (2017) which states that, for all
$\mathcal{D}$, with probability at least $1-\delta$, over
$S\sim\mathcal{D}^{m}$, we have

$\displaystyle\mathbb{E}_{\nu\sim
N(0,\sigma)^{n}}\left[R\left(f_{w+\nu}\right)\right]-\widehat{R}\left(f_{w}\right)\leq\underbrace{\mathbb{E}_{\nu\sim\mathcal{N}(0,\sigma)^{n}}\left[\widehat{R}\left(f_{w+\nu}\right)\right]-\widehat{R}\left(f_{w}\right)}_{\text{expected
sharpness
}}+4\sqrt{\frac{1}{m}(\underbrace{\frac{\|w\|_{2}^{2}}{2\sigma^{2}}}_{\text{KL
}}+\ln\frac{2m}{\delta})}$ (16)

where $R$ is the risk, $f_{w}=A(S)$ and $w$ are the function and weights,
respectively, produced by the network after training, and $f_{w+\nu}$ is the
function obtained by perturbing the weights of the network, $w$, by the noise
$\nu$. $\sigma$ is a hyperparameter that can be chosen to take any value
greater than $0$. The first two terms after the inequality are called
_expected sharpness_ by Neyshabur et al. (2017), and measures how much the
loss increases in average by a perturbation of order $\sigma$ to the weights.
Neyshabur et al. (2017) perform experiments that show that this bound
correlates well with the true error when varying data complexity, and number
of training examples, but not when varying the amount of overparametrization.
By optimizing the posterior of a PAC-Bayes bound conceptually similar to eq.
16, Dziugaite and Roy (2017) also obtained bounds on the expected error under
weight perturbations. Their results were noteworthy because the bounds were
non-vacuous.

The bounds in Neyshabur et al. (2017); Dziugaite and Roy (2017) are bounding
the expected value of the generalization error under perturbation of the
weights, rather than the generalization error of the original network.
Obtaining bounds on the latter is addressed by recent work on _determinist_
PAC-Bayes bounds (Nagarajan and Kolter, 2018). However their bounds are
vacuous, and follow the wrong trends when varying depth and width.

In Jiang et al. (2019), it was found empirically that using a worst-case
measure of sharpness, that measures the loss change along the worst weight
perturbation of a certain magnitude, very similar to the one proposed in
Keskar et al. (2016), gives the best correlation (and best results in their
causal analysis) among the many measures they tested.

Arora et al. (2018) developed another approach to prove generalization bounds
based on the robustness of neural networks to perturbations of the weights.
They showed that if the effects of perturbing the weights does not grow too
much as it propagates through every layer111111a condition which they
formalized through a series of measurable quantities, the network could be
compressed to a network with fewer parameters, for which a generalization
error bound could be given that was tighter than other proposed bounds,
although still vacuous. They found that their bound correlates with the true
error as it decreased during training. However, this bound has the
disadvantage that it applies to the compressed network only, and not to the
original network.

Recently, Banerjee et al. (2020) have developed novel deterministic bounds
based on a de-randomization of a PAC-Bayes bound. Their bound is also based on
the flatness of the minimum found after training (measured by Hessian
eigenvalues), and also takes into account the distance moved in parameter
space. They provided evidence that their bound correlates well with the test
error when varying the training set size and label corruption. However, they
didn’t study the tightness of their bound (which depends on certain smoothness
constants of a linearized version of the non-linear DNN).

  * •

D.1 ✓ Neyshabur et al. (2017); Banerjee et al. (2020) provided some evidence
that their PAC-Bayesian bounds correlates with true error when varying the
data complexity. The authors are not aware of similar results for the other
measures.

  * •

D.2 ✓ Neyshabur et al. (2017); Banerjee et al. (2020); Dziugaite et al. (2020)
have shown evidence that different sensitivity-based PAC-Bayesian bounds
correlate with true error when varying the training set size. However, a more
quantitative comparison could be done, over more datasets and different
architectures.

  * •

D.3 ⚫ Both the worst-case and expected sharpness measures appear to correlate
well with the true error when varying depth. However, only the worst-case
sharpness appears to correlate with the error when varying width (Neyshabur et
al., 2017; Jiang et al., 2019). Furthermore, Dziugaite et al. (2020) show that
although the average correlation with depth and width is good for some PAC-
Bayes and sharpness measures, they are not robust, and all of them fail for a
significant number of experiments. The bound in Arora et al. (2018) depends on
quantities whose dependence on the architecture are hard to predict; however,
the bound’s explicit dependence on depth suggests that it may grow linearly
with depth, unlike the empirical observations. Recently, Maddox et al. (2020)
showed that a measure of flatness known as effective dimensionality correlates
better with the error than PAC-Bayes measures, when varying width and depth,
suggesting that it may be a better measure than PAC-Bayes-based flatness
measures to understand generalization.

  * •

D.4 ✓ The worst-case sharpness appears to correlate well with the true error
when varying several algorithm hyperparameters, while other sharpness measures
correlate a bit worse Jiang et al. (2019). In Dziugaite et al. (2020), it was
shown that some flatness measures indeed correlate well with the error over
most experiments.

  * •

D.5 ⚫ Although the sharpness bounds in Neyshabur et al. (2017); Jiang et al.
(2019) are likely vacuous, Dziugaite and Roy (2017) showed that by optimizing
the PAC-Bayesian posterior over a large family of Gaussians, non-vacuous
bounds could be obtained.

  * •

D.6 ⚫ Some sharpness bounds studied in Jiang et al. (2019) are efficiently
computable. However, the more advanced ones such as the ones in Dziugaite and
Roy (2017) require significant computational expense.

  * •

D.7 ⚫ The bounds in Neyshabur et al. (2017); Dziugaite and Roy (2017); Arora
et al. (2018) are based on rigorous theorems. However, they only apply to
either the expected error under random perturbations of the weights, or to the
compressed network. The deterministic PAC-Bayes bounds in Nagarajan and Kolter
(2018); Banerjee et al. (2020) apply to the deterministic error of the
original network, but may be vacuous or not very tight. The worst-case
sharpness measure which appears to correlate best with the generalization
error Jiang et al. (2019) lacks a rigorous theorem that explains this
correlation.

#### 4.2.2 Other PAC-Bayes bounds

There are many recent works applying PAC-Bayesian ideas to obtain
generalization error bounds in novel ways. Zhou et al. (2018) proved non-
vacuous generalization error bounds on compressed networks trained on large
datasets. However, their bounds are still very loose, and their correlation
with the true error hasn’t been studied yet. Dziugaite and Roy (2018) extended
the PAC-Bayesian analysis to include data-dependent priors under the
assumption that they are close to differentially-private priors. Their bounds
are non-vacuous and apply to the expected value of the generalization error
after training with SGLD (Welling and Teh, 2011), but they are very
computationally expensive, and have only been tested on a small synthetic
dataset.

###  4.3 Other algorithm-dependent bounds

We now consider other types of algorithm-dependent bounds, which are not based
on non-uniform convergence. The main class of such bounds are stability-based
bounds, under which we include compression and algorithmic stability bounds.
These bounds include both data-independent and data-dependent bounds. The
data-independent bounds will suffer from many of the same pitfalls as VC
dimension bounds, as DNNs show generalization for some datasets but not
others, while the data-dependent bounds are more promising.

#### 4.3.1 Stability-based bounds

Stability-based bounds offer an alternative way to obtain algorithm-dependent
bounds, different from the non-uniform convergence SRM-like bounds. In fact,
they even allow to obtain data-independent algorithm-dependent bounds.
Stability analyses show that if the output of a learning algorithm depends
weakly on the training set, then it can be shown to generalize. One approach
of this kind was developed by Littlestone and Warmuth (1986), who derived
_compression bounds_. They obtain data-independent bounds on the
generalization error for learning algorithms whose output can be computed via
a fixed function of only $k<m$ out of the $m$ training examples (which $k$
examples they are can depend on the training sample). For the realizable case,
the bound is

$\mathbf{P}_{S\sim\mathcal{D}^{m}}[\epsilon(\mathcal{A}(S))\leq\frac{8k\log{(m/\delta)}}{m}]\geq
1-\delta.$ (17)

See Shalev-Shwartz and Ben-David (2014) for the formal statement and proof.
These bounds are based on the general concept of ‘stability’ described above
because if the output of the algorithm only depends on a small subset of the
training examples, it means the output is insensitive to changes in most of
the outputs. A compression bound has been recently developed for two-layer
neural networks trained with SGD on linearly-separable data, based on a proof
that in this case SGD converges in a bounded number of non-zero weight
updates, which therefore gives a bound on $k$ (Brutzkus et al., 2018).

The most common notion of stability, called _algorithmic stability_ , was
related to generalization by Bousquet and Elisseeff (2002), and considers how
sensitive the output of the learning algorithm is to removing a single example
from the training sample. Most work on algorithmic stability has focused on
the data-independent notion of _uniform stability_ , which has been used to
obtain data-independent bounds for SGD (Hardt et al., 2016; Mou et al., 2018).

Because compression bounds and uniform stability are both data-independent,
they can’t capture the crucial data-dependence of generalization in deep
learning which was pointed out, for example, by Zhang et al. (2017). To this
end, some recent extensions have looked at data-dependent notions of
stability. Kuzborskij and Lampert (2017) applied this idea to obtain
generalization error bounds for SGD-trained models. They obtain bounds of the
form

$\forall\mathcal{D},~{}\mathbf{E}_{(S\sim\mathcal{D}^{m},A)}[R(\mathcal{A}(S))-\hat{R}(\mathcal{A}(S))]\leq\mathcal{O}\left(\sqrt{c(R(w_{1})-R^{*})}\cdot\frac{\sqrt[4]{T}}{m}+c\sigma\frac{\sqrt{T}}{m}\right)$
(18)

where the expectation is also taken over the randomness in the algorithm
$\mathcal{A}$ (as SGD is a stochastic algorithm), $c$ is a constant related to
the step size of SGD, $w_{1}$ is the initial weights of the neural network,
$R^{*}$ is the minimum risk achiveable by the hypothesis class of the
algorithm, $T$ is the training time, and $\sigma$ is a bound on the variance
of the SGD gradients.

The bound in eq. 18 has several limitations which we discuss now. First of
all, it is a bound on the expected value of the generalization error, which
does not immediately imply a bound that holds both with high probability and
logarithmic dependence121212Note that the Markov inequality implies a high
probability bound, but it has a polynomial $1/\delta$ dependence on the
confidence parameter, which is expected to be far from optimal. on the
confidence parameter $\delta$, as the other bounds studied here (Shalev-
Shwartz et al., 2010; Feldman and Vondrák, 2019). The bound applies for smooth
convex losses, but the authors also provide a more complex bound for smooth
non-convex losses. The smoothness is an important limitation, as most neural
networks in practice use ReLU activations, making the loss surface non-smooth.
However, in their experiment they use a CNN with max pooling, which gives a
non-smooth loss surface, and their bounds still work well empirically. The
bound also requires an estimate of $R(w_{1})$. They estimate this with a
validation set, which makes the bound not dependent on $S$ alone. However, in
practice the initialization is usually random and independent of $S$, which
means $R(w_{1})$ could be estimated from the empirical loss on $S$. The bound
can not be directly applied to classification error, which is not Lipschitz,
but it can be applied to cross-entropy loss which in turn implies an upper
bound on classification error. Perhaps the most serious limitation of this
stability bound is that it assumes a single pass over the data $T\leq m$,
which is not the usual case in practice as training and generalization error
often decrease by training on several passes of the data.

Some recent works extended the data-dependent stability analysis of SGD-
trained neural networks in different directions. London (2017); Li et al.
(2019) combined stability bounds with the PAC-Bayesian approach we be
discussed later. Zhou et al. (2019) proved data-dependent stability bounds
that apply to SGD with multiple passes over the data. However, their bound
increases with training time (although logarithmically rather than
polynomially as in Hardt et al. (2016); Mou et al. (2018)), contradicting the
empirical result that generalization error appears to pleateau with training
time (Hoffer et al., 2017). However, their results have not yet been
empirically tested, so that it is hard to evaluate these bounds on the
desiderata.

  * •

D.1 ✓ The data-dependent stability bound in Zhou et al. (2019) correlated with
the true error when varying the amount of label corruption on three different
datasets. Li et al. (2019) also showed that their Bayes stability analysis
gives bound that are larger for randomly labelled CIFAR10 than for uncorrupted
CIFAR10.

  * •

D.2 ⚫ The explicit dependence of many stability bounds on $m$ is given by the
classical $1/m$ or $\sqrt{1/m}$. However, data dependent bounds have
quantities which may change with $m$ in complicated ways. Furthermore, the
bounds for non-convex losses in Kuzborskij and Lampert (2017) have a more
complicated data-dependence with explicit power law dependence on $m$.
Kuzborskij and Lampert (2017) show a good correlation between their bound and
the empirical generalization gap. However, this is only done for one-pass
(online) SGD. To the best of our knowledge, no study has compared the
$m$-dependence of the other bounds with the true error, for the usual case
where SGD is trained over multiple passes to reach low training error.

  * •

D.3 ⚫ The data-dependent stability bounds depend on empirical quantities of
the loss surface and the behavior of SGD, both of which can in principle be
affected by the choice of architecture. However, as far as the authors know
this dependence hasn’t been explored.

  * •

D.4 ✗ Most stability bounds grow with training time. However, empirically the
opposite correlation is found, with longer training time leading to better
generalization Hoffer et al. (2017); Jiang et al. (2019). Charles and
Papailiopoulos (2018) showed situations in which gradient descent (GD) is not
uniformly stable but SGD is. However, whether SGD really generalizes better
than GD is still a controversial topic (Hoffer et al., 2017).

  * •

D.5 ⚫ Many stability bounds Hardt et al. (2016); Mou et al. (2018); Zhou et
al. (2019) grow with training time, and thus will become vacuous for
sufficiently large training times. Kuzborskij and Lampert (2017) have shown
remarkably tight expected generalization gap bounds, which however only apply
to one-pass SGD. These results are very promising, but further empirical
analysis, and work on tight bounds for multi-pass SGD is still needed.

  * •

D.6 ✓ Data-independent stability bounds are typically easy to compute. Data-
dependent ones like the one in Kuzborskij and Lampert (2017) are harder
(depending on empirical quantities like the Hessian and gradient sizes), but
still applicable to reasonably sized problems

  * •

D.7 ⚫ Proposed bounds are based on rigorous theorems. However, these often
have assumptions which are not held in common practice (e.g. one-pass over the
data, smoothness of loss function, linear separability).

###  4.4 Other bounds and generalization measures

Jiang et al. (2018) have recently empirically studied a measure of
generalization based on features of the distribution of margins at different
hidden layers. Their measure shows significantly better correlation between
the bound and the error as data complexity and architecture is varied, than
the margin-based measures in Bartlett et al. (2017). However, they provide
limited results regarding the predictive power when changing individual
features of the data or architecture, and instead provide an aggregate
correlation score when they are all changed simultaneously. The success of the
measure explored in Jiang et al. (2018) may be related to the correlation
observed in Valle-Pérez et al. (2018); Mingard et al. (2020) between the prior
probability of functions for Bayesian DNNs and the critical sample ratio
(CSR), which was proposed as a complexity measure in Krueger et al. (2017).
The critical sample ratio is an aggregate measure of the distances between
input points and the decision boundary, like the distribution of input margins
in Jiang et al. (2018). Furthermore the correlation between the prior
probability and generalization is established in Valle-Pérez et al. (2018);
Mingard et al. (2020), as well as our PAC-Bayes bound in section 5, which
helps understand why CSR may correlate with generalization.

Wei and Ma (2019a, b) offered theoretical bounds based on a similar idea to
Jiang et al. (2018). They considered extending the notion of margins to all
the layers of the DNN. However, no empirical evaluation was presented.

Recently, and in response to the work of Nagarajan and Kolter (2019), Negrea
et al. (2019) proposed a method to apply uniform convergence to cases where it
previously produced vacuous generalization gap bounds. The idea is to show
that an algorithm produces a hypothesis with generalizatoin and empirical
errors close to some hypothesis in a class with a uniform convergence
property. This work has yet to be applied to deep learning, but could offer an
interesting direction.

Finally, several measures investigated by Jiang et al. (2019); Maddox et al.
(2020); Dziugaite et al. (2020), some of which we have discussed in the
sections on margin and sensitivity-based bounds, don’t yet correspond to
rigorous analyses of generalization, but some predict generalization better
than existing bounds, and so are promising directions for future more rigorous
analyses of generalization.

###  4.5 generalization error predictions for specific data distributions

There is recent work on predicting generalization error of DNNs by making
assumptions on $\mathcal{D}$, rather than relying on frequentist PAC bounds
which typically don’t make any assumption on $\mathcal{D}$ (beyond assuming
realizability). Spigler et al. (2019); Bordelon et al. (2020) study kernel
regression with miss-specified priors, based on Sollich (2002)131313A similar
analysis from a physics-inspired perspective has been presented in Cohen et
al. (2019). Bordelon et al. (2020) further apply this idea to the neural
tangent kernel (NTK) of a fully connected network, which approximates the
behaviour of SGD-trained DNNs in the infinite width and infinitesimal learning
rate limit (Jacot et al., 2018), which seems to work well for finite-width but
wide DNNs (Lee et al., 2019). They apply this to MNIST by estimating the NTK
eigenspectrum on a sample of MNIST, and then training the DNN on smaller
samples. Their predicted generalization error closely follows the observed
error of the SGD-trained DNN. As far as the authors are aware this is one of
the most accurate predictions of the generalization error of DNNs based on
well-established theory.

One of the limitations of the analysis in Bordelon et al. (2020) is that it
relies on knowing what the data distribution is, and in particular the
eigenvalues of the NTK kernel, and the eigenspectrum of the target function
(with respect to the eigen basis of the NTK kernel). This can be estimated by
using a sufficiently large sample of the data, but it is not discussed in
Bordelon et al. (2020) how big the sample needs to be for the estimate to be
accurate. They use a sample larger than the training set, which therefore
makes this predictor fall outside the requirements of the kinds of predictons
we have been considering (which only depend on $S$). However, the approach
offers an analytical theory of generalization which can help with
interpretability and gaining understanding of which properties of a DNN
architecture lead to generalization for a particular dataset. The other
limitation of the work in Bordelon et al. (2020) is that the analysis only
applies for MSE loss, which is not commonly used for classification (though
the training with the two losses often results in DNNs with similar learned
functions (Mingard et al., 2020)).

## 5 Marginal-likelihood PAC-Bayesian generalization error bound

In the previous section, we saw that algorithm-independent or data-independent
bounds are clearly insufficient to explain the generalization performance of
DNNs because the hypothesis class of DNNs is too expressive, and the
generalization strongly depends on the dataset, respectively. Furthermore, the
main approaches for algorithm-dependent bounds are based on non-uniform
convergence, which has been shown to have fundamental limitations in its
ability to predict generalization in SGD-trained DNNs for some datasets
(Nagarajan and Kolter, 2019). Although there are ways around this limitation
(see the discussion in section 3.3.4), it suggests that looking at other
approaches to obtain generalization bounds may be promising. Non-uniform
stability bounds offer an interesting alternative to non-uniform convergence,
but their empirical success so far is still limited.

Here we present a new deterministic realizable PAC-Bayes bound which applies
to a DNN trained using Bayesian inference, with high probability over the
posterior. We work in the same set up as Valle-Pérez et al. (2018) and
McAllester (1998). We consider binary classification, and a space of functions
or hypotheses with codomain $\\{0,1\\}$. We consider a “prior” $P$ over the
hypothesis space $\mathcal{H}$, and an algorithm which samples hypotheses
according to the Bayesian posterior, with $0-1$ likelihood. To recall, we
define generalization error as the probability of misclassification upon a new
sample $\epsilon(h)=\textbf{P}_{x\sim\mathcal{D}}[h(x)\neq t(x)]$, where $t$
is the target function. In section A.1, we prove the following theorem:

######  Theorem 5.1.

(marginal-likelihood PAC-Bayes bound)

For any distribution $P$ on any hypothesis space $\mathcal{H}$ and any
realizable distribution $\mathcal{D}$ on a space of instances we have, for
$0<\delta\leq 1$, and $0<\gamma\leq 1$, that with probability at least
$1-\delta$ over the choice of sample $S$ of $m$ instances, that with
probability at least $1-\gamma$ over the choice of $h$:

$-\ln{(1-\epsilon(h))}<\frac{\ln{\frac{1}{P(C(S))}}+\ln{m}+\ln{\frac{1}{\delta}}+\ln{\frac{1}{\gamma}}}{m-1}$

where $h$ is chosen according to the posterior distribution
$Q(h)=\frac{P(h)}{\sum_{h\in C(S)}P(h)}$, $C(S)$ is the set of hypotheses in
$\mathcal{H}$ consistent with the sample $S$, and where $P(C(S))=\sum_{h\in
C(S)}P(h)$

The proof is presented in section A.1. It closely follows that of the original
PAC-Bayesian theorem by McAllister, with the main technical step relying on
the quantifier reversal lemma of McAllester (1998). Note that the bound is
essentially the same as that of Langford and Seeger (2001), except for the
fact that it holds in probability and it adds an extra term dependent on the
confidence parameter $\gamma$, which is usually negligible, but may be
important when considering the effect of optimizer choice. The quantity
$P(C(S))$ corresponds to the marginal likelihood, or Bayesian evidence of the
data $S$, and we will also denote it by $P(S)$, to simplify notation.

In Valle-Pérez et al. (2018), the authors interpreted $Q(h)$ as approximating
the probability by which the stochastic algorithm (e.g. SGD) outputs
hypothesis $h$ after training. The preceding bound relaxes this assumption,
because it shows that in some sense, the bound holds for “almost all” of the
zero-error region of parameter space. More precisely, it holds with high
probability over the posterior. This suggests that SGD may not need to
approximate the Bayesian inference as closely, for this bound to be useful.
Nevertheless, Mingard et al. (2020) gave empirical results showing that, for
DNNs, the distribution over functions that SGD samples from, approximates the
Bayesian posterior rather closely. A fully rigorous generalization error bound
for DNNs would need further analysis of SGD dynamics, but we believe these
theoretical and empirical results strongly suggest that the PAC-Bayes bound
should be applicable to SGD-trained DNNs.

Because it applies to the Bayesian posterior only, the bound in theorem 5.1
does not apply universally over a large family of posteriors, like standard
deterministic PAC-Bayes bounds do, which can be shown to sometimes give loose
bounds (Nagarajan and Kolter, 2019). Furthermore, as we will show in section
6.2, the bound is in a certain sense asymptotically optimal in the limit of
large training set size.

We expect our bound to give significantly tighter results than previous PAC-
Bayes bounds applied to DNNs, because rather than working with parameters, our
bound works directly with posteriors and priors in _function space_. Since the
parameter-function map (Valle-Pérez et al., 2018) of DNNs is many-to-one, with
a lot of parameter-redundancy, it is not hard to construct situations where
$KL(Q_{\text{par}}||P_{\text{par}})$ between a parameter-space posterior
$Q_{\text{par}}$ and prior $P_{\text{par}}$ is high, but $KL(Q||P)$ between
the induced posterior and prior in function-space is low. In fact, in section
A.3, we show that the following inequality holds

$KL(Q||P)\leq KL(Q_{\text{par}}||P_{\text{par}})$ (19)

which implies that it is always better (or at least not worse) to consider
PAC-Bayes bounds in function space for parametrized models, if possible.
Furthermore, in section 7, we will empirically verify that our bound gives
good predictions for SGD-trained DNNs, and satisfies most of our desiderata
for a generalization error bound. Thus our empirical results corroborate our
expectation of better agreement above.

## 6 Optimality of data-dependent bounds

###  6.1 General definitions for optimality

In section 4.1.1 we saw that VC dimension bounds are provably optimal (up to a
constant) among the set of data-independent algorithm-independet uniform
bounds. The question of optimality is more difficult for the other types of
bounds. As will be shown below, the optimal data-dependent bound may depend on
a chosen prior over data distributions, as well as the algorithm. We won’t
consider notions of optimality for data-independent non-uniform, or
algorithmic-dependent bounds (e.g. uniform stability bounds). Instead, the
notion of optimality we treat here is for data-dependent algorithm-dependent
bounds.

To explore this notion of optimality, we make the following two definitions,
using a simplified notation for the right hand side of the inequality in eq.
2, which we refer to as the _value_ of the bound:

$B(S)=\frac{f_{\mathcal{A}}(S)}{m^{\alpha}}.$

######  Definition 6.1.

A PAC bound of the form in eq. 2 with value $B(S)$ is called _distribution-
admissible_ or _distribution-Pareto optimal_ for algorithm $\mathcal{A}$ if
there does not exist another bound for algorithm $\mathcal{A}$ with value
$B^{\prime}$ such that for all $\mathcal{D}$, for all $\delta>0$, and for all
$m$,
$\mathbf{E}_{S\sim\mathcal{D}^{m}}[B^{\prime}(S)]\leq\mathbf{E}_{S\sim\mathcal{D}^{m}}[B(S)]$,
and
$\mathbf{E}_{S\sim\mathcal{D}^{m}}[B^{\prime}(S)]<\mathbf{E}_{S\sim\mathcal{D}^{m}}[B(S)]$
for some $\mathcal{D}$,$\delta$,$m$.

######  Definition 6.2.

A PAC bound of the form in eq. 2 with value $B(S)$ is called _optimal with
respect to a prior $\Pi$_ over data distributions, for algorithm
$\mathcal{A}$, for a training set size $m$ and confidence level $\delta$ if it
minimizes the value of
$\mathbf{E}_{\mathcal{D}\sim\Pi,S\sim\mathcal{D}^{m}}[B(S)]$ over valid PAC
bounds for algorithm $\mathcal{A}$.

We also say that the bound is optimal with respect to a prior $\Pi$ over data
distributions, for algorithm $\mathcal{A}$, if it is optimal in the above
sense for all $m$, and $\delta\in[0,1]$.

Any of these definitions can be extended to require optimality over a family
of algorithms rather than a single one. Analogous definitions can also be made
for data-dependent uniform bounds like eq. 9. For hypothesis classes where the
Rademacher complexity dominates the $O(1/\sqrt{m})$ term (in expectation over
$S$, for any $\mathcal{D}$) so that the lower bound closely matches the upper
bound, then not only is eq. 9 (approximately) distribution-Pareto optimal, but
it’s the unique distribution-Pareto optimal uniform generalization gap bound,
and therefore the optimal uniform generalization gap bound for any prior $\Pi$
(up to lower order terms).

For non-uniform data-dependent bounds, the authors are not aware of any result
showing optimality. However, as we saw in section 4.2.1.1, non-uniform bounds
are typically based on choosing a “prior”, and the expected value of the bound
for different $\Pi$ depends heavily on the choice of this “prior”. This
suggests that perhaps there isn’t a unique notion of optimality (i.e. the
optimal bound could depend on the assumed true prior $\Pi$), but doesn’t prove
this negative result because these are only upper bounds. We will see in the
next section that for some pairs of algorithms and priors over data
distributions, the marginal-likelihood PAC-Bayes bound asymptotically matches
(up to a constant) the expected generalization error (which is a lower bound
on the expected value of any generalization error upper bound) and is thus
asymptotically optimal (up to a constant) according to our definition. This
result, combined with the empirical result that the average value of the bound
empirically depends on the data distribution, also implies that the optimal
PAC bound, for a fixed algorithm, depends on the prior over data
distributions.

###  6.2 Bayesian optimality of the marginal-likelihood PAC-Bayesian bound

In this section, we present a theorem to show that under certain conditions on
the algorithm and distribution, the marginal-likelihood PAC-Bayes bound is
tight. In particular, we will show that if the generalization error decreases
as a power law with training set size $m$, the bound is asymptotically optimal
up to a constant.

We again consider binary classification. Let
$S_{m}=\\{(x_{i},y_{i})\\}_{i=1}^{m}$ be a training set of size $m$. Consider
sampling one more sample $(x_{m+1},y_{m+1})$ to obtain
$S_{m+1}=\\{(x_{i},y_{i})\\}_{i=1}^{m+1}$. We think of $S_{m}$ and $S_{m+1}$
as random variables with distributions determined by $\mathcal{D}$. We also
define $P_{e}(x,y,S):=1-P(y|S;x)$ to be the probability that a Bayesian
posterior $P$ conditioned on a training set $S$ and a test point $x$ predicts
the incorrect label. We will denote $P_{e}(m):=P(x,y,S_{m})$, where the
dependence on $x,y,S_{m}$ is left implicit. Note that
$\mathbf{E}_{(x,y)\sim\mathcal{D}}[P_{e}(m)]=\epsilon(\mathcal{A}(S_{m}))$
where $\mathcal{A}$ is a learning algorithm that returns a function sampled
from the Bayesian posterior $P$ conditioned on training set $S_{m}$, and
$\epsilon$ is the average generalization error (averaged both over posterior
samples). We will let $\epsilon(m)=\epsilon(\mathcal{A}(S_{m}))$ where we omit
the dependence on $\mathcal{A}$ and $S_{m}$ for brevity.

In the following we denote with angle brackets $\langle\cdot\rangle$ an
average over $S_{m+1}$ (which includes average over $S_{m}$). Note that
$\langle P_{e}(m)\rangle=\langle\epsilon(m)\rangle$, and it’s also the same as
$\epsilon(m)$ averaged over $S_{m}$, because $\epsilon(m)$ already includes an
average over one test point sampled from $\mathcal{D}$.

######  Lemma 6.3.

Assume $\langle\epsilon(m)\rangle=o(1)$ as $m\to\infty$. Then, assuming that
for some $E<1$, for all $S_{m+1}$, $P_{e}(m)\leq E$ , there exists a constant
$C$, such that, as $m\to\infty$,

$\langle\log{P(S_{m})}\rangle-\langle\log{P(S_{m+1})}\rangle\sim
C\langle\epsilon(m)\rangle.$ (20)

Furthermore, if $\text{Var}(P_{e}(m))=o(\langle\epsilon\rangle)$, then $C=1$.

The proof is found in section A.2.

######  Theorem 6.4.

Assume $\langle\epsilon(m)\rangle\sim bm^{-\alpha}$ as $m\to\infty$, with
$0<\alpha<1$. Then, assuming that for some $E<1$, for all $S_{m+1}$,
$P_{e}(m)\leq E$ , there exists a constant $C^{\prime}$, such that, as
$m\to\infty$,

$-\langle\log{P(S_{m})}\rangle\sim C^{\prime}bm^{1-\alpha}$ (21)

Furthermore, if $\text{Var}(P_{e}(m))=o(\langle\epsilon\rangle)$, then
$C^{\prime}=\frac{1}{1-\alpha}$.

###### Proof.

We can write $-\langle\log{P(S_{m})}\rangle$ using a telescoping sum

$\displaystyle-\langle\log{P(S_{m})}\rangle$
$\displaystyle=-\langle\log{P(S_{0})}\rangle+\sum_{m^{\prime}=0}^{m-1}\left[-\langle\log{P(S_{m^{\prime}+1})}\rangle--\langle\log{P(S_{m}^{\prime})}\rangle\right]$
(22) $\displaystyle\sim
C\sum_{m^{\prime}=0}^{m-1}\langle\epsilon(m^{\prime})\rangle$ (23)
$\displaystyle\sim\frac{Cb}{1-\alpha}m^{1-\alpha}$ (24)

The second step uses lemma 6.3, and the third uses the assumption in the
theorem. Furthermore, from lemma 6.3, the second part of the theorem directly
follows. ∎

In theorem 6.4, $\langle\epsilon(m)\rangle$ is the actual expected error
averaged over training sets of size $m$. This is a lower bound for the
training-set-averaged value of any upper bound on the expected error, such as
the PAC-Bayes bound (McAllester, 1998). It is also a lower bound on the
average value of high-probability bounds like theorem 5.1. On the other hand,
the PAC-Bayes bound has an expected value with a leading order behaviour given
by

$\mathbf{E}_{S_{m}\sim\mathcal{D}^{m}}\left[\text{PB}(m)\right]\sim\frac{-\langle\log{P(S_{m})}\rangle}{m}\sim
C^{\prime}m^{-\alpha},$ (25)

which up to a constant, matches the asymptotic behaviour of the lower bound
given by $\langle\epsilon(m)\rangle$ itself. Therefore, we can conclude that
the PAC-Bayes bound section 5 is asymptotically optimal (up to a constant,
which may be computable a priori), for pairs of priors and learning algorithms
that satisfy the theorem assumptions.

The main assumption of the theorem is that $\langle\epsilon(m)\rangle$ follows
a power law behaviour asymptotically in $m$. As we mentioned in section 2,
this has been empirically found to be the case for sufficiently expressive
deep learning models. Spigler et al. (2019) could prove that the learning
curve follows a power law for stationary Gaussian processes in a misspecified
teacher-student scenario, and input instances distributed on a lattice. They
could also compute the power law exponents analytically. More recently,
Bordelon et al. (2020) developed a theory of average generalization error
learning curves (see section 4.5) and proposed an explanation for the power
law behaviour based on some assumptions on the data distribution.

The second assumption, which is only necessary to get a smaller value of the
constant is that $\text{Var}(P_{e}(m))=o(\langle\epsilon(m)\rangle)$. This
seems plausible in many situations. For large $m$, most of the variation in
$P_{e}(m)$ should typically come from the choice of test point $x$ (on which
$P_{e}(m)=P_{e}(x,y,S_{m})$ implicitly depends) rather than the choice of
$S_{m}$. We can consider two extreme cases. If $P_{e}(x,y,S_{m})$ is $1$ for
some $x$ and $0$ for all other $x$, then $P_{e}(x,y,S_{m})$ is a Bernoulli
variable, and the variance is of the same order as the mean. On the other
extreme, if $P_{e}(x,y,S_{m})=\epsilon(m)$ for all $x$, then the variance
(coming from the choice of $x$) is $0$. It seems plausible that in many
situations, we find something in between.

In section 7, we will show extensive empirical evidence that the PAC-Bayes
bound follows a power-law behaviour with an exponent closely matching the
empirically-measured test error. We sometimes observe deviations, but these
are likely coming from the use of the expectation-propagation (EP)
approximation, which empirically appears to introduce systematic errors, as a
power law (Mingard et al., 2020). Furthermore, we observe a positive
correlation between the exponent $\alpha$ and the proportionality constant
relating the bound and the error, $C^{\prime}$, as predicted by theorem 6.4.

## 7 Experimental results for the marginal-likelihood PAC-Bayes bound

In section 2 we presented a series of seven desiderata for a generalization
theory of deep learning, and in section 4, we used this framework to compare a
wide range of different bounds from the literature. In this section we perform
extensive experiments that are needed to test the marginal-likelihood PAC-
Bayes bound against the desiderata, especially D.1-3 (performance when varying
dataset, architecture, and training set size). This empirical work provides an
example of how to test a bound in detail against the desiderata. In section 8,
we will discuss the comparison of our bound against all the desiderata.

The key quantity needed to compute the bound theorem 5.1 for DNNs is the
marginal likelihood, which measures the capacity term in the bound. We follow
the same approach as Valle-Pérez et al. (2018) and calculate the marginal
likelihood using the Gaussian process (GP) approximation to DNNs (also called
neural network GP, or NNGP), proposed in several recent works (Lee et al.,
2017; Matthews et al., 2018; Novak et al., 2018; Garriga-Alonso et al., 2018;
Yang, 2019b), and which can be used to approximate Bayesian inference in DNNs.
This approximation requires computing the GP kernel of the NNGP for the inputs
in the training set $S$, which in the infinite width limit, equals the
covariance matrix of the outputs of the DNN with random weights, for inputs in
$S$. This can be computed anlaytically for FCNs, but for more complex
archiectures this is unfeasible, so we rely on the Monte Carlo approximation
used in Novak et al. (2018). We approximate the kernel by an estimator of the
empirical covariance matrix for the vector of outputs of the DNN, computed
from $M$ random initializations of the DNN. The marginal likelihood is then
approximated using the expectation-propagation (EP) approximation, as was done
in previous works (Valle-Pérez et al., 2018; Mingard et al., 2020). See
section B.1 for more details. We note that for some experiments, running the
network to convergence or computing the EP approximation turned out to be too
computationally expensive to achieve within our budget, which is why several
architectures are not present for some of the experiments for larger training
set sizes (e.g. those in section 7.3). Code for the experiments can be found
in https://github.com/guillefix/nn-pacbayes

In the following experiments, the datasets are binarized, and all DNNs are
trained using Adam optimizer to 0 training error. The test error is measured
on the full test set for the different datasets used, while the training set
is sampled from the full training set provided by these datasets. For full
experimental details see section B.

###  7.1 Error versus label corruption (Desideratum D.1)

Desideratum D.1 requires that the bound correlates with the error as we change
the dataset complexity. We test this correlation in two ways: by directly
corrupting a fraction of the labels of a standard dataset, increasing its
complexity, and by comparing different standard datasets differing in
complexity.

(a)

(b)

Figure 1: Generalization error versus amount of label corruption (D1). PAC-
Bayes bound and generalization error versus amount of label corruption, (a)
for a CNN with 4 layers and no pooling and (b) for a FCN with 2 layers, for
three datasets and a training set of size $10000$. See section B for more
details on architectures. The bound follows the expected trends with
complexity, both for increasing label corruption, and for the ordering among
the datasets. The dashed red line denotes the 50% error expected upon random
guessing.

In fig. 1, we show the true test error and the PAC-Bayes bound for a CNN and a
FCN, as we increase the label corruption for three different datasets
(CIFAR10, MNIST, and Fashion MNIST), which have been binarized. We find that
the bound is not only relatively tight, but qualitatively follows the
behaviour of the true error, increasing with complexity, as well as preserving
the order among the three datasets. In fig. 3 and fig. 4, we present more
datasets, and observe that for sufficiently large training set size, the bound
typically can correctly predict in which datasets the networks will generalize
better.

###  7.2 Error versus training set size (Desideratum D.2)

Desideratum D.2 requires that the bound predicts the change in error as we
increase the training set size. As mentioned previously, several works
(Hestness et al., 2017; Novak et al., 2019; Rosenfeld et al., 2019; Kaplan et
al., 2020) have found that learning curves for DNNs tend to show a power law
behaviour with an exponent that depends on the dataset, but not significantly
on the architecture. However, we note that in some work on learning curves for
Gaussian processes (Sollich, 2002; Spigler et al., 2019; Bordelon et al.,
2020), more complex types of learning curves have also been observed
(sometimes involving several regions of non-monotonicity), suggesting that
DNNs may potentially show more complex learning curves, different from power
laws, in some regimes. As a simple example, in Hestness et al. (2017), it was
pointed out that in the low data regime learning curves do not show the
asymptotic power law behaviour. Another example is the double-descent
behaviour with respect to data size observed in Nakkiran et al. (2019).

Figure 2: Learning curves for fully connected network (batch 256). Solid and
dashed line show, respectively, the empirical test error and the PAC-Bayes
bounds for fully connected network (FCN) with 2 hidden layer, versus training
set size $m$, for three different datasets. The DNNs were trained using Adam
and batch size 256 to 0 training error.

We empirically computed the learning curves for many combinations of
architectures and datasets, as well as the corresponding PAC-Bayes bounds. In
fig. 2 and fig. 3, we show the learning curves for three representative
architectures for different datasets. The exponent of the learning curve
clearly depends on the dataset, but less strongly on the architecture. The
PAC-Bayes bound approximately matches the power law exponent of the empirical
learning curves, as predicted by theorem 6.4. For fig. 2, the bound even
predicts the quick drop in generalization for EMNIST between $m=4k$ and
$m=15k$ for the FCN. However, we found that this fine grained agreement
doesn’t typically hold for other architectures, for which the bound only
matches the overall power law behaviour of the learning curve.

In fig. 4, we show the learning curves for several representative
architectures for five different datasets. For each architecture, the bound
and the SGD results have a very similar learning curve exponent, though there
can be a different vertical offset that depends on the architecture. The
relative ordering in generalization performance between different
architectures is typically also predicted by the bound, specially for large
$m$. We will explore this trend in more detail in section 7.3.

Figure 3: Learning curves, compared by dataset, for three architectures. Solid
and dashed lines show, respectively, the empirical test error and the PAC-
Bayes bounds. The architectures are a FCN, Resnet50, and Densenet121. The
datasets show a range in complexity, from simpler (MNIST) to more complex
(CIFAR-10). The DNNs were trained using Adam and batch size 32 to 0 training
error. Figure 4: Comparing different architectures. Learning curves for the
test error and the PAC-Bayes bounds for representative architectures and
different datasets. Solid and dashed line show, respectively, the empirical
test error and the PAC-Bayes bounds. The architectures are FCN, Resnet50,
Densenet121, and MobileNetv2. The DNNs were trained using Adam with batch size
32 to 0 training error. Different architectures show similar learning curve
power law exponents, which are matched well by the PAC-Bayes bound. Note that
we used slightly different y-axis ranges for each dataset, to aid the
distinction of different architectures. The ordering of the PAC-Bayes bound
also agrees reasonably well with the ordering of the true learning curves,
when comparing architectures (Desideratum D.3).

The learning curves we observe in the figs above agree with the previous
empirical observations of power law behaviour in learning curves for DNNs,
with only a few exceptions, where we observe a deviation from power law
behaviour. In particular the learning curve for CIFAR10 for batch 32 appears
to deviate from a power law on this range of $m$. However for batch 256 it
shows cleaner power law behaviour (see fig. 12, fig. 13, fig. 14 in section E)
that agrees better with the PAC-Bayes bound exponent.

In fig. 8 and fig. 9, shown in section D, we present the learning curves for
several variants of ResNets and DenseNets, respectively. Within each family of
similar architectures, the learning curve is even more similar. The PAC-Bayes
bound matches the behaviour of the true error rather closely for the entire
range of architectures and datasets used. In particular, the power law
exponent of the PAC-Bayes bound is close to that of the true learning curves
for these 14 different architectures, just as was found in fig. 3 for three
representative ones, showing that our generalization error theory is robust
and widely applicable.

(a)

(b)

Figure 5: Learning curve exponents of test error vs learning curve exponent
estimated from PAC-Bayes bound. Each marker shows the learning curve exponent,
$\alpha$, measured for all the 19 architectures and 5 datasets in section B.
For the empirical error, the exponent was obtained from a linear fit to the
learning curve corresponding to $\log{\epsilon}$ vs $\log{m}$ and is shown on
the x-axis. For the the PAC-Bayes bound, in (a) the exponent is estimated from
a linear fit to the log of the PAC-Bayes bound vs $\log{m}$. In (b) the
exponent is estimated indirectly from $C^{\prime}$ which is the ratio of the
PAC-Bayes bound and the error (see theorem 6.4). Then, this second method
makes assumptions about how the bounds scale. The error bars are estimated
standard errors from the linear fits. For the ratio estimate the errors due to
fluctuations in dataset are negligible. Note that the exponents cluster
according to dataset. The outliers for MNIST and KMNIST are both the FCN. The
DNNs were trained using Adam and batch size 32 to 0 training error. For some
datasets (e.g. CIFAR10) the power law behaviour is less clear, but we still
chose to include the estimated exponent for completeness.

In fig. 5, we compare the power law exponent $\alpha$ from the empirical
learning curves (calculated with Adam and batch size 32), to the exponent from
the PAC-Bayes bounds. For the empirical learning curves, $\alpha$ is estimated
from a linear fit of $\log{\epsilon}$ vs $\log{m}$. We note that the exponents
cluster according to the dataset, as observed in previous work (Hestness et
al., 2017). However, we also observe some smaller, but statistically
significant variation in exponents within a dataset, indicating that the
architecture nevertheless may play a role in the learning curve behaviour
(though less significant than the dataset). One exception is the FCN which
shows a significantly different exponent than other architectures – a
deviation which is also predicted by the PAC-Bayes bound, but for which we do
not yet have an explanation.

To estimate the learning curve exponent for the PAC-Bayes curves, we used two
methods. In fig. 5(a), we used linear fit to the log of the PAC-Bayes bound vs
$\log{m}$, as was done for the empirical exponents. In fig. 5(b), we estimate