# How Uniform Random Weights Induce Non-uniform Bias:
Typical Interpolating Neural Networks Generalize with Narrow Teachers

Gon Buzaglo 1 Itamar Harel11footnotemark: 111footnotemark: 1 1 Mor Shpigel
Nacson11footnotemark: 1 1
Alon Brutzkus1 Nathan Srebro2 Daniel Soudry1

1Technion Institute of Technology, Haifa, Israel
2Toyota Technological Institute at Chicago, Chicago IL, USA Equal Contribution

###### Abstract

Background. A main theoretical puzzle is why over-parameterized Neural
Networks (NNs) generalize well when trained to zero loss (i.e., so they
interpolate the data). Usually, the NN is trained with Stochastic Gradient
Descent (SGD) or one of its variants. However, recent empirical work examined
the generalization of a random NN that interpolates the data: the NN was
sampled from a seemingly uniform prior over the parameters, conditioned on
that the NN perfectly classifying the training set. Interestingly, such a NN
sample typically generalized as well as SGD-trained NNs.
Contributions. We prove that such a random NN interpolator typically
generalizes well if there exists an underlying narrow “teacher NN" that agrees
with the labels. Specifically, we show that such a ‘flat’ prior over the NN
parametrization induces a rich prior over the NN functions, due to the
redundancy in the NN structure. In particular, this creates a bias towards
simpler functions, which require less relevant parameters to represent —
enabling learning with a sample complexity approximately proportional to the
complexity of the teacher (roughly, the number of non-redundant parameters),
rather than the student’s.

##  1 Introduction

A central theoretical question in deep learning is why Neural Networks (NNs)
generalize, despite being over-parameterized, and even when perfectly fitted
to the data (Zhang et al., 2017). One of the leading explanations for this
phenomenon is that NNs have an “implicit bias" toward generalizing solutions
(e.g., Gunasekar et al. (2017); Soudry et al. (2018); Arora et al. (2019); Lyu
and Li (2020); Chizat and Bach (2020); Vardi (2023)). This bias stems from
underlying interactions between the model and the training method — including
the type of optimization step, the initialization, the parametrization, and
the loss function.

Previous works (Valle-Perez et al., 2019; Mingard et al., 2021; Chiang et al.,
2023) suggested, based on empirical evidence, that a significant part of this
implicit bias in NNs is the mapping from the model parameters to the model
function. Specifically, suppose we randomly sample the NN parameters from a
‘uniform’ prior111A truly uniform prior does not exist for infinite sets, so
the prior is chosen similarly to standard ‘uniform-like’ initializations: in
each layer, the prior is Gaussian (uniform on the $\ell_{2}$ sphere) or
uniform in the $\ell_{\infty}$ ball., and accept only parameter samples in
which the NN perfectly classifies all the training data — i.e., samples from
the posterior composed of the same prior and the likelihood of a 0-1 loss
function. Then, Chiang et al. (2023) found that the sampled NNs generalize as
well as SGD in small-scale experiments.

These results may suggest that such a uniform sampling of the NN parameters
induces simple and generalizing NN functions. In this paper, we prove this is
indeed the case, and aim to uncover the mechanism behind this phenomenon. In
short, we prove typical NN interpolators sampled this way (“students")
generalize well, given there exists a “narrow” NN teacher that generates the
labels. In more detail,

  * •

In Section 3 we prove that a typical NN sampled from the posterior over
interpolators generalizes well (i.e., has a small test error with high
probability) with

$\\#\textrm{samples}=O\left(-\log\tilde{p}\right)\,,$

where $\tilde{p}$ is the probability that a random NN (sampled from the
‘uniform’ prior) is equivalent to the teacher function.222Proof idea: the
number of hypotheses sampled until a successful interpolation is
$\left|\mathcal{H}\right|\lessapprox 1/\tilde{p}$. Plugging this into the
standard sample complexity of a finite hypotheses class
$O\left(\log\left|\mathcal{H}\right|\right)$, we obtain the result. The actual
proof is slightly more complicated since $\left|\mathcal{H}\right|$ here
weakly depends on the training set. Thus, to obtain generalization guarantees
for NNs, we proceed to upper bound $\left(-\log\tilde{p}\right)$.

  * •

Next, in Section 5, we examine the case where both the student and teacher
parameters are quantized to $Q$ levels, including zero (as in standard
numerical formats), and we assume the prior is uniform over all possible
quantized values. We examine several architectures:

    * –

For a fully connected multi-layer network with a scalar output, hidden neuron
layer widths $\\{d_{l}\\}_{l=1}^{L}$ and $\\{d^{\star}_{l}\\}_{l=1}^{L}$
respectively for the student and teacher, input width $d_{0}=d_{0}^{\star}$,
and any activation function $\sigma$ that satisfies $\sigma\left(0\right)=0$,
we prove

$-{\log\tilde{p}}\leq\sum_{l=1}^{L}\left(d_{l}^{\star}d_{l-1}^{\star}+2d_{l}\right){\log
Q}.$ (1)

    * –

For convolutional NNs, we obtain analogous results, where channel numbers
replace layer widths, with an additional multiplicative factor of the kernel
size.

    * –

The proofs in both cases are simple333Proof idea, for a two-layer FC net
without biases: The NN function is identical to the teacher NN function, if we
set $d_{1}^{\star}$ hidden neurons with the same ingoing and outgoing weights
as in the teacher; and for the other $d_{1}-d_{1}^{\star}$ hidden neurons we
set the outgoing weights (for the zeroed neurons, the input weights do not
matter). The probability of this is $\tilde{p}=Q^{-d_{0}d_{1}^{\star}-d_{1}}$,
which satisfies (1)., and can be extended for more general architectures.

  * •

Combining these relatively easy-to-prove results, we get a surprisingly novel
result: typical NN interpolators have sample complexity approximately
proportional to the number of teacher parameters times the number of
quantization bits, with only a weak dependence on the student width. Thus, the
student generalizes well if there exists a teacher that is sufficiently narrow
and under-parameterized in comparison to the sample number.

  * •

Finally, in Section 6 we examine a two-layer neural network with continuous
weights and derive similar results, except a margin factor replaces $Q$ in the
bound.

##  2 Preliminaries

Notation. We use boldface letters for vectors and matrices. A vector
$\mathbf{x}\in\mathbb{R}^{d}$ is assumed to be a column vector, and we use
$x_{i}$ to denote its $i$-th coordinate. We denote by
$\mathrm{Vec}\left(\cdot\right)$ the vectorization operation, which converts a
tensor into a column vector by stacking its columns. The indicator function
$\mathbb{I}\left[A\right]$ is $1$ if statement $A$ is true and $0$ if
statement $A$ is false. Additionally, we use the standard notation
$[N]=\\{1,\dots,N\\}$ and take $\left\|\cdot\right\|$ to be the Euclidean
norm. We use the symbols $\odot$ to denote the Hadamard product, i.e.
elementwise multiplication, $\otimes$ to denote the Kronecker product, and $*$
to denote the convolution operator. For a pair of multi-indices
$D^{\prime}=\left(d_{1}^{\prime},\dots,d_{L}^{\prime}\right),D^{\prime\prime}=\left(d_{1}^{\prime\prime},\dots,d_{L}^{\prime\prime}\right)\in\mathbb{N}^{L}$
we denote $D^{\prime}\leq D^{\prime\prime}$ if for all $l\in\left[L\right]$,
$d_{l}^{\prime}\leq d_{l}^{\prime\prime}$.

Data. Let $\mathcal{D}$ be some data distribution. We consider the problem of
binary classification over a finite training set $\mathcal{S}$ that contains
$N$ datapoints sampled i.i.d. from $\mathcal{D}$:

$\mathcal{S}\triangleq\\{\mathbf{x}_{n}\\}_{n=1}^{N}\sim\mathcal{D}^{N}\,,$

where $\mathbf{x}_{n}\in\mathbb{R}^{d_{0}}$. Since we are interested in
realizable models we assume there exists a teacher model, $h^{\star}$,
generating binary labels, i.e. $h^{\star}(\mathbf{x})\in\\{\pm 1\\}$ for any
$\mathbf{x}\sim\mathcal{D}$.

Evaluation metrics. For a predictor $h:\mathbb{R}^{d_{0}}\mapsto\left\\{\pm
1\right\\}$, we define the risk, i.e. the population error
$\mathcal{L}_{\mathcal{D}}(h)\triangleq\mathbb{P}_{\mathbf{x}\sim\mathcal{D}}\left(h(\mathbf{x})\neq
h^{\star}\left(\mathbf{x}\right)\right),$ and the empirical risk, i.e. the
training error
$\mathcal{L}_{\mathcal{S}}(h)\triangleq\frac{1}{N}\sum_{n=1}^{N}\mathbb{I}\left[h(\mathbf{x}_{n})\neq
h^{\star}\left(\mathbf{x}_{n}\right)\right]\,.$

Hypothesis parametrization. We discuss parameterized predictors
$\bm{\theta}\mapsto h_{\bm{\theta}}$, where $\bm{\theta}\in\mathbb{R}^{M}$.
Distributions over $\bm{\theta}$ therefore induce distributions over
hypotheses via

$\displaystyle\mathcal{P}\left(h\right)\triangleq\mathbb{P}_{\bm{\theta}}\left(\bm{\theta}\mid
h_{\bm{\theta}}=h\right)~{}.$

##  3 Generalization Bounds for Random Interpolating Hypotheses

In this paper, we study the generalization of interpolating predictors sampled
from the posterior of NNs:

$\mathcal{P}_{\mathcal{S}}\triangleq\mathcal{P}(h\mid\mathcal{L}_{\mathcal{S}}(h)=0)\propto\mathcal{P}(h)\mathbb{I}\left[\mathcal{L}_{\mathcal{S}}(h)=0\right]\,,$
(2)

where $\mathcal{P}(h)$ is some prior over the hypotheses class. That is, our
“learning rule” amounts to sampling a single predictor from the posterior,

$\mathcal{A}_{\mathcal{P}}(\mathcal{S})\sim\mathcal{P}_{S},$ (3)

and we would like to analyze the population error
$\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(\mathcal{S}))$ of this
sampled predictor.

Samples from the posterior $\mathcal{P}_{\mathcal{S}}$ can be obtained by the
Guess and Check procedure (G&C; Chiang et al. (2023)), defined in Algorithm 1,
which can be viewed as a rejection sampling procedure for (2). That is, we can
think of drawing a sequence $\left(h_{t}\right)_{t=1}^{\infty}$ of hypotheses
i.i.d. from the prior $\mathcal{P}$ and independent of $\mathcal{S}$ (i.e.
before seeing the training set). Then, given the training set $\mathcal{S}$,
we pick the first hypothesis in the sequence that interpolates the data. We
will employ this equivalence in our analysis, and view samples from the
posterior $\mathcal{P}_{\mathcal{S}}$ as if they were generated by this
procedure.

Algorithm 1 Guess and Check (G&C)

Input: (1) $\mathcal{P}$, Prior over hypotheses (2) $\mathcal{S}$, Training
set.

Output: $\mathcal{A}_{\mathcal{P}}(S)$

Algorithm:

Draw $h_{1},h_{2},\dots\overset{\textrm{i.i.d.}}{\sim}\;\mathcal{P}$.

Choose
$T\triangleq\min\left\\{t\,|\,\mathcal{L}_{\mathcal{S}}(h_{t})=0\right\\}$

Return: $\mathcal{A}_{\mathcal{P}}(S)\triangleq h_{T}$

We will be particularly interested in the case in which $\mathcal{P}(h)$ is
defined through a ‘uniform’ (or otherwise fairly ‘flat’ or benign) prior on
the parameters $\bm{\theta}$ in some parametrization $h_{\bm{\theta}}$. But in
this section, we analyze posterior sampling, or equivalently Guess and Check,
directly through the induced distribution $\mathcal{P}$ over predictors. In
particular, we analyze generalization performance in terms of the probability
that a random hypothesis $h\sim\mathcal{P}$ is equivalent to the teacher
model. Formally:

######  Definition 3.1.

We say that a predictor $h$ is teacher-equivalent (TE) w.r.t. a data
distribution $\mathcal{D}$, and denote $h\equiv h^{\star}$, if
$\mathbb{P}_{\mathbf{x}\sim\mathcal{D}}\left(h\left(\mathbf{x}\right)=h^{\star}\left(\mathbf{x}\right)\right)=1\,.$
and denote the probability of a random hypothesis to be TE by

$\displaystyle\tilde{p}\triangleq\mathbb{P}_{h\sim\mathcal{P}}\left(h\equiv
h^{\star}\right)\,.$

As we show in the next result, $\tilde{p}$ plays an important role in G&C
generalization. Specifically, in Appendix A.2 we derive the following
generalization bound.

######  Theorem 3.2 (G&C (i.e. Posterior Sampling) Generalization).

Let $\epsilon\in\left(0,1\right)$ and $\delta\in\left(0,\frac{1}{5}\right)$,
and assume that $\tilde{p}<\frac{1}{2}$. For any $N$ larger than

$\displaystyle\frac{-\log\left({\tilde{p}}\right)+3\log\left(\frac{2}{\delta}\right)}{\epsilon}\,,$

the sample complexity, we have that

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)<\epsilon\right)\geq
1-\delta\,.$

We observe that the sample complexity required to ensure
$(\epsilon,\delta)$-PAC generalization depends on
$\left(-\log\left(\tilde{p}\right)\right)$. Thus, we define the effective
sample complexity as

$\tilde{C}\triangleq-\log\left(\tilde{p}\right)\,.$

Moreover, we notice the above theorem implies (from Markov inequality, see
Appendix A.3):

######  Corollary 3.3 (Volume of Generalizing Interpolators).

For $\epsilon,\delta$ as above, and any $N$ larger than

$\displaystyle\frac{-\log\left({\tilde{p}}\right)+6\log\left(\frac{2}{\delta}\right)}{\epsilon}\,,$

the sample complexity, we have that

$\displaystyle\mathbb{P}_{\mathcal{S}}\left(\mathbb{P}_{h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)\geq\epsilon\right)<\delta\right)\geq
1-\delta\,.$

Corollary 3.3 implications. Corollary 3.3 examines, for a single sample of the
data $\mathcal{S}$, the relative volume of ‘bad’ interpolators out of all
interpolators — i.e. the probability to sample an interpolator for which
$\mathcal{L_{D}}\left(h\right)\geq\epsilon$, given the data $\mathcal{S}$. It
states that this relative volume is small ($\delta$) with high probability
($1-\delta$) over the sampling of the data. And $\delta$ can be quite small,
since for any $\epsilon$, we have that $\delta$ decays exponentially fast in
$N$

$\displaystyle\delta=2\exp\left(-\frac{\epsilon
N+\log\left(\tilde{p}\right)}{6}\right).$

Proof idea of Theorem 3.2 and relationship to PAC-Bayes. In Appendix A.2, we
prove Theorem 3.2 by noting that the expected number of hypotheses we will
consider is $1/\tilde{p}$, and so we are essentially selecting an
interpolating hypothesis from the effective hypothesis class
$\mathcal{H}=\\{h_{1},\ldots,h_{\tau}\\}$ with $\tau\approx 1/\tilde{p}$,
where the hypotheses in this class are chosen before seeing the training set.
The sample complexity is thus
$\log\left|\mathcal{H}\right|=\log\tau\approx-\log\tilde{p}$. The only
complication is that the stopping time $\tau$ of G&C is random and depends on
$\mathcal{S}$. But it is enough to bound $\tau$ very crudely (which we do with
high probability), as a multiplicative factor to $\tau$ results only in an
additive logarithmic factor.

The analysis here is similar to PAC-Bayes analysis (McAllester, 1999), which
also studies the behavior of a posterior over hypotheses, except that in
typical PAC-Bayes analysis the bound is over the expected population error
$\mathbb{E}_{h\sim\mathcal{P}_{\mathcal{S}}}\left[\mathcal{L}_{\mathcal{D}}(h)\right]$
for a sample from the posterior. In fact, noting that
$\mathrm{KL}(\mathcal{P}_{\mathcal{S}}\|\mathcal{P})=-\log\mathbb{P}_{h\sim\mathcal{P}}(\mathcal{L}_{\mathcal{S}}(h)\\!=\\!0)\geq-\log\tilde{p}$,
a standard PAC-Bayes bound (Langford and Seeger, 2002; McAllester, 2003) will
yield that with the same sample complexity as in Theorem 3.2,

$\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\;\mathbb{E}_{h\sim\mathcal{P}_{\mathcal{S}}}\left[\mathcal{L}_{\mathcal{D}}(h)\right]<\epsilon\;\right)\geq
1-\delta.$ (4)

The difference is that Theorem 3.2 holds with high probability for a single
posterior sample, instead of just in the expectation over the posterior. That
is, Theorem 3.2 establishes that not only are random interpolators good on
average, but only a small fraction of them are bad.

Using Markov inequality one can derive from (4) a high probability bound for a
for a single draw from the posterior (as in Theorem 3.2), but that bound is
less tight then Theorem 3.2 (see Appendix A.4). Also, a variant of the PAC-
Bayes theorem that holds with high probability for a single draw from the
posterior has also been presented by Alquier (2023, Theorem 2.7). As is,
Alquier’s result yields a much looser bound, since it is more generic (it
applies to any posterior, not just conditioning on interpolation). Theorem 3.2
can be viewed as a tighter specialization to interpolators.

A sample complexity of $\left(-\log\tilde{p}\right)$ should not be surprising,
and can also be obtained by a Minimum Description Length (MDL)/Occam Razor
learning rule
$\textsc{MDL}_{\mathcal{P}}(\mathcal{S})=\arg\max_{\mathcal{L}_{\mathcal{S}}(h)=0}\mathcal{P}(h)$
(Blumer et al., 1987) (see also Section 7.3 in Shalev-Shwartz and Ben-David
(2014)). But importantly, this requires using the induced probability mass
function over hypotheses, and not the distribution over parametrizations—see
discussion in the next Section.

##  4 Redundancy and Description Length

Before we state our main results for NNs in Section 5, in this section, we
pause to give a broader perspective on the effect of the parametrization on
$\tilde{p}=\mathbb{P}_{h\sim\mathcal{P}}\left(h\equiv h^{\star}\right)$. As we
saw, the parametrization controls the generalization behavior of G&C and
posterior sampling, and how a seemingly uniform prior over parameters can
induce a rich prior over hypothesis via redundancy. We first consider a
conceptually very direct parametrization.

How parameter redundancy works: a minimal example. Consider a predictor
$h_{\sigma}$ specified by a description language (i.e. parametrization) using
bit strings $\sigma$, where descriptions end with the string “END” (encoded in
bits), and this string never appears elsewhere in the description444This can
be a Turing complete programming language, or perhaps better to think of
simpler descriptions such as boolean formulas or strings encoding decision
trees.. We will consider students that use fixed-length descriptions, i.e.,
$\sigma\in\\{0,1\\}^{C}$, where we only consider the description up to the
first “END”, i.e. $h_{\sigma}=h_{\tilde{\sigma}}$ where $\tilde{\sigma}$ is a
prefix of $\sigma$ ending with the first “END”.555If $\sigma$ does not contain
“END”, or $\tilde{\sigma}$ is not a valid description, we can set $h_{\sigma}$
to the constant 0 predictor. Let us now consider a uniform prior over this
parametrization, i.e. $\mathcal{P}(\sigma)=2^{-C}$ for all
$\sigma\in\\{0,1\\}^{C}$. Although this prior is uniform over
parametrizations, it is easy to see that it induces a highly non-uniform prior
over predictors: for a predictor $h_{\tau}$ with a short description
$\tau\in\\{0,1\\}^{{\left\lvert{\tau}\right\rvert}}$,
${\left\lvert{\tau}\right\rvert}\ll C$, it’s $C$-bit description is highly
redundant, as the final $C-{\left\lvert{\tau}\right\rvert}$ bits can be set
arbitrarily, as long as the first bits are $\tau$, and so
$\mathcal{P}(h_{\tau})\geq 2^{-{\left\lvert{\tau}\right\rvert}}$. For a
teacher with a short description $h^{\star}=h_{\tau^{\star}}$,
$\tau^{\star}\in\\{0,1\\}^{C^{\star}}$, we thus have $-\log\tilde{p}\leq
C^{\star}$. The sample complexity of learning a small teacher thus depends
only on the complexity of the teacher and not the complexity of the (possibly
much larger) student.

Why would MDL fail here? Returning to the MDL/Occam principle mentioned at the
end of Section 3, it is important to note that applying this principle to the
distribution over parameters would not work here. Consider the MDL/Occam/MAP
rule which selects the most likely interpolating parameters
$\arg\max_{\mathcal{L}_{\mathcal{S}}(h_{\sigma})}\mathcal{P}(\sigma)$. This
rule would be useless here, since for all $\sigma$ in our parameter space
$\\{0,1\\}^{C}$ have the same prior probability, and its associated sample
complexity would be $O(-\log\mathcal{P}(\sigma^{\star}))=C$ (not
$\mathcal{P}(h_{\sigma^{\star}})$ !), where $\sigma^{\star}$ is a description
of $h^{\star}$ in our parameter space (e.g.
$\sigma^{\star}=\tau^{\star}+$‘0’$\cdot(C-C^{\star})$). The important
distinction is that Occam considers the probability mass function over
parameters (roughly, the density under a specific parametrization or base
measure). On the other hand, even if we sample $h_{\sigma}$ by sampling
parameters $\sigma$, posterior sampling (i.e. G&C) can be thought of directly
in terms of the distribution over hypotheses.

When would redundancy fail? To see how changing the parametrization can change
the induced distribution over hypothesis, consider instead a non-redundant
parametrization, where we take $\sigma$ to be uniform over valid descriptions,
of length at most $C$, ending with “END” (i.e. strings ending with “END” and
that do not otherwise contain “END”). The induced prior over hypothesis is now
uniform666We might still have further redundancies in that multiple valid
descriptions can describe the same function, again introducing non-uniformity.
Consider here a non-redundant description language, e.g. a read-once branching
program. and even using posterior sampling/G&C would have sample complexity
determined by the complexity of the student, rather than the teacher.

When would MDL succeed? Finally, we note that we could of course learn a short
teacher with an Occam rule that is explicitly biased towards short
descriptions, e.g. using the Kraft prior777We again absorb any remaining
probability in the constant zero predictor. Here we are thinking of an
unbounded student and the parameter space being any string ending with the
first occurrence of “END”. We can also of course bound the size of the
student. $\mathcal{P}(\sigma)=2^{-{\left\lvert{\sigma}\right\rvert}}$. Using
such a prior, the Occam rule also enjoys a sample complexity of $O(C^{\star})$
that depends only on the length of the teacher. But here the prior over
parameters is non-uniform and explicitly biased, and our interest in this
paper is in how seemingly uniform priors over parameters can induce non-
uniform priors and generalization over predictors due to the choice of
parametrization.

##  5 Quantized Nets Sample Complexity

Recall that the generalization bound in Theorems 3.2 depends on the effective
sample complexity $\tilde{C}\triangleq-\log\left(\tilde{p}\right)$. In this
section, we derive an upper bound on $\tilde{C}$ for quantized multi-layer
Fully Connected (FC) Neural Networks (NNs) with a single binary output, with
and without additional per-node scaling.

######  Definition 5.1 (Vanilla FC).

For a depth $L$, widths $D=\left(d_{1},\dots,d_{L}\right)$, and activation
function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$, a fully connected NN is a
mapping $\bm{\theta}\mapsto h^{FC}_{\bm{\theta}}$ from parameters

$\displaystyle\left\\{\bm{\theta}=\left\\{\mathbf{W}^{\left(l\right)},\mathbf{b}^{\left(l\right)}\right\\}_{l=1}^{L}\,\middle|\,\mathbf{W}^{\left(l\right)}\in\mathbb{R}^{d_{l}\times
d_{l-1}},\mathbf{b}^{\left(l\right)}\in\mathbb{R}^{d_{l}}\right\\}$

defined recursively, starting with
$f^{(0)}\left(\mathbf{x}\right)=\mathbf{x}\,,$ then

$\displaystyle\forall
l\in\left[L\\!-\\!1\right]:\;f^{(l)}\left(\mathbf{x}\right)$
$\displaystyle=\sigma\\!\left(\mathbf{W}^{\left(l\right)}f^{(l-1)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(l\right)}\right)$
$\displaystyle h_{\bm{\theta}}^{FC}\left(\mathbf{x}\right)$
$\displaystyle=\operatorname{sign}\\!\left(\mathbf{W}^{\left(L\right)}f^{(L-1)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(L\right)}\right)\\!.$

The total parameter count is $M(D)=\sum_{l=1}^{L}d_{l}(d_{l-1}+1)$. We denote
the class of all fully connected NNs as $\mathcal{H}^{\mathrm{FC}}_{D}$.

As we will show, considering NNs in which each neuron is multiplied by a
scaling parameter can significantly improve the bound. This architecture
modification is common in empirical practices, e.g. batch-normalization (Ioffe
and Szegedy, 2015), weight-normalization (Salimans and Kingma, 2016), and
certain initializations (Zhang et al., 2019). Formally, we define a Scaled-
neuron Fully Connected (SFC) NN as

######  Definition 5.2 (Scaled-neuron FC).

For a depth $L$, widths $D=\left(d_{1},\dots,d_{L}\right)$, and activation
function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$, a scaled neuron fully
connected neural network is a mapping $\bm{\theta}\mapsto
h^{FC}_{\bm{\theta}}$ from parameters

$\displaystyle\bm{\theta}=\left\\{\mathbf{W}^{\left(l\right)},\mathbf{b}^{\left(l\right)},\bm{\gamma}^{\left(l\right)}\right\\}_{l=1}^{L}\,,$

where $\mathbf{W}^{\left(l\right)}\in\mathbb{R}^{d_{l}\times
d_{l-1}},\mathbf{b}^{\left(l\right)}\in\mathbb{R}^{d_{l}},\bm{\gamma}^{\left(l\right)}\in\mathbb{R}^{d_{l}}\,,$
defined recursively, starting with
$f^{(0)}\left(\mathbf{x}\right)=\mathbf{x}\,,$ then

$\displaystyle\forall l\in\left[L-1\right]\;f^{(l)}\left(\mathbf{x}\right)$
$\displaystyle=\sigma\left(\bm{\gamma}^{\left(l\right)}\odot{\mathbf{W}^{\left(l\right)}f^{(l-1)}\left(\mathbf{x}\right)}+\mathbf{b}^{\left(l\right)}\right)$
$\displaystyle h_{\bm{\theta}}^{FC}\left(\mathbf{x}\right)$
$\displaystyle=\operatorname{sign}\left(\mathbf{W}^{\left(L\right)}f^{(L-1)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(L\right)}\right).$

The total parameter count is $M(D)=\sum_{l=1}^{L}d_{l}(d_{l-1}+2)$. We denote
the class of all scaled neuron fully connected NNs as
$\mathcal{H}^{\mathrm{SFC}}_{D}$.

We consider $Q$-quantized networks where each of the parameters is chosen from
a fixed set $\mathcal{Q}\subset\mathbb{R}$ such that $0\in\mathcal{Q}$ and
${\left\lvert{\mathcal{Q}}\right\rvert}\leq Q$. This can be the set of
integers $\\{-\frac{Q}{2},-\frac{Q}{2}+1,\ldots,(\frac{Q}{2}-1)\\}$ for even
$Q$, or the set of numbers representable as $\log_{2}Q$-bit floats (for, e.g.
$\log_{2}Q=32$). Fully connected quantized NNs thus have parameters
$\bm{\theta}\in\mathcal{Q}^{M}$ corresponding to a complexity $C=M\log Q$
(from the classic log cardinality bound, see Appendix A.1).

We consider a teacher $h^{\star}=h_{\bm{\theta}^{\star}}$ that is a
$Q$-quantized network of some depth $L$ and small widths
$D^{\star}=(d^{\star}_{1},\ldots,d^{\star}_{L})$, and a wider student of the
same depth $L$ but widths $D\gg D^{\star}$. For the student, we consider a
uniform prior over $Q$-quantized parametrizations, i.e.
$\bm{\theta}\sim\textrm{Uniform}\left(Q^{M(D)}\right)$. In other words, to
generate $h_{\bm{\theta}}\sim\mathcal{P}$, each weight (and bias) in the NN is
chosen independently and uniformly from $\mathcal{Q}$.

(a) Teacher network

(b) Vanilla student network

(c) Scaled neuron student network

Figure 1: Illustration of vanilla and scaled neuron three-layer quantized
teacher and student neural networks. Note that the visualization does not show
the bias units. The proof of Theorem 5.3 relies on counting student networks
which are functionally equivalent to the teacher network. Figure 1(a) depicts
a narrow teacher. In Figure 1(b), we visualize a FC student network that
replicates the teacher by zeroing out all outgoing weights of any neuron that
does not exist in the teacher. Specifically, the blue edges are weights
identical to the teacher, and the orange edges are set to zero. Therefore, the
white neurons do not affect the network output. In Figure 1(c), we visualize
an SFC student network that replicates the teacher by setting the scaling
parameter to zero (each zero marked with a red ‘x’) for any neuron that does
not exist in the teacher. In both cases, the gray edges do not affect the
function. In this specific example, we can see how the redundancy is higher in
SFC than in the vanilla FC network, hinting at better generalization
capabilities.

###  5.1 Main Results

Using the definitions above, we can state the following.

######  Theorem 5.3 (Main result for fully connected neural networks).

For any activation function such that $\sigma(0)=0$, depth $L$, $Q$-quantized
teacher with widths $D^{\star}$, student with widths $D>D^{\star}$,
$d_{0}^{\star}\triangleq d_{0}$, and prior $\mathcal{P}$ uniform over
$Q$-quantized parametrizations, we have that:

  1. 1.

For Vanilla Fully Connected Networks:

$\displaystyle\tilde{C}\leq\hat{C}^{\mathrm{FC}}\triangleq\left(\sum_{l=1}^{L}{\left(d_{l}^{\star}d_{l-1}+d_{l}^{\star}\right)}\right)\log
Q\,.$ (5)

  2. 2.

For Scaled Neuron Fully Connected Networks:

$\displaystyle\tilde{C}\leq\hat{C}^{\mathrm{SFC}}\triangleq\left(\sum_{l=1}^{L}\left(d_{l}^{\star}d_{l-1}^{\star}+2d_{l}\right)\right)\log
Q\,.$ (6)

And, by Theorem 3.2, $N=(\tilde{C}+3\log 2/\delta)/\epsilon$ samples are
enough to ensure that for posterior sampling (i.e. G&C),
$\mathcal{L}(\mathcal{A}_{\mathcal{P}}(\mathcal{S}))\leq\epsilon$ with
probability $1-\delta$ over $\mathcal{S}\sim\mathcal{D}^{N}$ and the sampling.

Proof idea. The idea is simple and centers on counting the necessary number of
constraints on the parameters of the student network to ensure it is TE. A
fundamental illustration of this concept is provided in the caption of Figure
1. Full proof is in Appendix B.

###  5.2 Discussion: Comparing Sample Complexities

To understand the sample complexity bound $O(\hat{C}^{\mathrm{FC}})$ and
$O(\hat{C}^{\mathrm{SFC}})$ implied by Theorem 5.3, let us first consider the
complexities (number of bits, or log cardinalities) of the teacher and student
models:

$\displaystyle
C^{\star}=\left(\sum_{l=1}^{L}\left(d_{l}^{\star}d_{l-1}^{\star}+kd_{l}^{\star}\right)\right)\log
Q\quad;\quad C=\left(\sum_{l=1}^{L}\left(d_{l}d_{l-1}+kd_{l}\right)\right)\log
Q$

where $k=1$ for Vanilla FC Networks and $k=2$ for Scaled FC Networks.

Either way, the dominant term is the quadratic term $\sum_{l}d_{l}d_{l-1}$.
Lacking other considerations, the sample complexity of learning with the
student network would be $C$. However, we see here that thanks to the
parametrization and prior, the student network implicitly adapts to the
complexity of the teacher, with $\hat{C}\ll C$ when $D^{\star}\ll D$ and in
any case $C^{\star}\leq\hat{C}^{\mathrm{}}\leq C$. With Vanilla FC Networks,
the sample complexity $\hat{C}^{\mathrm{FC}}$, although smaller than $C$, is
still significantly larger than the complexity $C^{\star}$ of the teacher,
which is what we could have hoped for. The quadratic (dominant) terms in
$\hat{C}^{\mathrm{FC}}$ are roughly geometric averages of terms from $C$ and
$C^{\star}$, and so we have that, very roughly,
$\hat{C}^{\mathrm{FC}}\approx\sqrt{CC^{\star}}$. We can improve this using
scaling, which creates more redundancy since zero scales can deactivate entire
units. Indeed, for Scaled Fully Connected Networks, we have that
$\hat{C}^{\mathrm{SFC}}=C^{\star}+\sum_{l=1}^{L}d_{l}\ll\hat{C}^{\mathrm{FC}}\ll
C$ (when $D^{\star}\ll D$). We still pay a bit for the width of the student,
but only linearly instead of quadratically. In particular, even if the width
of the student is quadratic in the width of the teacher, the sample complexity
of learning by sampling random NNs is almost the same as that of using a much
narrower teacher.

Minimum widths. We note that, just as in the description length example in the
previous section, an explicit narrowness prior could have of course been fully
adaptive to the width of the teacher and ensured learning with the ideal
sample complexity $C^{\star}$. E.g., this is achieved by allowing the student
to choose the width of each layer, and using the Occam rule

$\displaystyle\min_{D^{\prime}\leq
D,\bm{\theta}\in\mathcal{Q}^{M(D^{\prime})}\text{with
widths}D^{\prime}}M(D^{\prime})\;\;\text{s.t.~{}}\mathcal{L}_{S}(h_{\bm{\theta}})=0.$
(7)

But from Theorem 5.3 we see that even without such an explicit bias, choosing
weights uniformly induces significant inductive bias toward narrow networks.

Maximum sparsity. It is also insightful to compare this to using an explicit
sparsity bias, e.g. with an Occam rule of the form:

$\displaystyle\min_{\bm{\theta}\in\mathcal{Q}^{M(D)}}\left\|\bm{\theta}\right\|_{0}\;\;\text{s.t.~{}}\mathcal{L}_{S}(h_{\bm{\theta}})=0.$
(8)

The sparsity-inducing rule (8) would have the following bound for the
effective sample complexity.

$\displaystyle\hat{C}^{\textrm{sparse}}\triangleq
O\left(M\left(D^{\star}\right)\log\left(M\left(D^{\star}\right)+d_{0}\right)+M\left(D^{\star}\right)\log
Q\right)\,.$ (9)

See Appendix D for a derivation of this equation. Note that
$\hat{C}^{\textrm{sparse}}$ in (9) does not depend on the size of the student,
but rather only on the size of the teacher, which is smaller, that is
$M\left(D^{\star}\right)\ll M\left(D\right)$. For comparison, recall our
previous bound for posterior sampling, in the case of FC scaled-neuron
networks from (6):

$\displaystyle\hat{C}^{\mathrm{SFC}}=\left(\sum_{l=1}^{L}\left(d_{l}^{\star}d_{l-1}^{\star}+2d_{l}\right)\right)\log
Q=O\left(C^{\star}+\sum_{l=1}^{L}2d_{l}\log Q\right)\,.$

When $\log Q=O(1)$, we can rewrite $\hat{C}^{\textrm{sparse}}$ as follows:

$\displaystyle\hat{C}^{\textrm{sparse}}=O\left(C^{\star}\left(1+\frac{\log
M\left(D^{\star}\right)}{\log{Q}}\right)\right)=O\left(C^{\star}\log
C^{\star}\right)\,,$

that is $\hat{C}^{\textrm{sparse}}$ has an additional multiplicative factor
bounded by $\log C^{\star}$, and so can be worse than the bounds for posterior
sampling. Specifically, in the regime where $2\sum_{l=1}^{L}{d_{l}}\log
Q\leq\frac{\log M\left(D^{\star}\right)}{\log Q}$, we have that
$\hat{C}^{\mathrm{SFC}}<\hat{C}^{\textrm{sparse}}$. For example, when
$\sum_{l=1}^{L}{d_{l}}\log Q=O\left(C^{\star}\right)$, we have that
$\hat{C}^{\mathrm{SFC}}$ is suboptimal with a factor of 2 with respect to
$C^{\star}$, whereas $\hat{C}^{\textrm{sparse}}$ is off by a larger factor of
$\log C^{\star}$.

Minimum norm. One might also ask whether a similar adaptation to teacher width
can be obtained by regularizing the norm of the weights. Indeed, Neyshabur et
al. (2015); Golowich et al. (2018) obtain sample complexity bounds that depend
only on the $\ell_{2}$ norm $\left\|\bm{\theta}\right\|$ of the learned
network, without any dependence on the width of the student (but with an
exponential dependence on depth!). These guarantees are not directly
applicable in our setting, since applying them to get guarantees on the
misclassification error we study here requires bounding the margin. Even with
a discrete teacher, without further assumptions on the input distribution, we
cannot ensure a margin. If we did consider only integer inputs and integer
weights, we could at least ensure a margin of 1. In this case: on one hand,
the norm-based sample complexity would scale as $Q^{O(L)}$, i.e. exponential
in the $L\log Q$ dependence of $\hat{C}^{\mathrm{}}$. On the other hand, the
norm-based guarantee would not depend at all on the student widths $D$, while
even $\hat{C}^{\mathrm{SFC}}$ increases linearly with the student widths.

###  5.3 Extension to convolutional neural networks

In Appendix B, we extend Theorem 5.3 to convolutional neural networks (CNN)
and convolutional neural networks where each neuron input is multiplied by a
learned parameter (SCNN). Specifically, we show that for quantized
convolutional networks, we get similar bounds on the sample complexity
$\hat{C}$ with channel numbers substituting layer widths.

$\displaystyle\hat{C}^{\mathrm{CNN}}=$
$\displaystyle\left(d_{s}+1+\sum_{l=1}^{L}\left(k_{l}c_{l}^{\star}c_{l-1}+c_{l}^{\star}\right)\right)\log
Q$ $\displaystyle\hat{C}^{\mathrm{SCNN}}=$
$\displaystyle\left(d_{s}^{\star}+1+\sum_{l=1}^{L}\left({k_{l}c_{l}^{\star}c_{l-1}^{\star}+2c_{l}}\right)\right)\log
Q\,,$

where $d_{s}$ is the number of neurons in the last convolutional layer (i.e.,
the width of the last layer which is a fully connected layer with a single
output), $k_{l}$ and $c_{l}$ are the $l^{\text{th}}$ layer kernel size and
number of channels. See Appendix B for precise definitions of the model and
statement of the result. Importantly, similar to the fully connected
architecture we observe that $\hat{C}^{\mathrm{SCNN}}$ is again near to the
teacher complexity, with only a weak dependency on the student channel
numbers. The proof here is analogous to the proof of Theorem 5.3, where
neurons are replaced with channels.

##  6 Continuous Nets Sample Complexity

So far, we focused on quantized uniform priors. However, per-layer continuous
spherical priors (e.g., Gaussian) are also quite common in practice and
theory. Therefore, in this section, we show how to extend our results beyond
the quantized case into a continuous setting, for the special case of two-
layer NNs without bias and with the leaky rectifier linear unit (Maas et al.,
2013) activation function. Formally, let
$h_{\bm{\theta}},h_{\bm{\theta}^{\star}}$ be fully connected (Definition 5.1)
two layer NNs with input dimension $d_{0}$, output dimension $d_{2}=1$ and
hidden layer dimensions $d_{1}$ and $d_{1}^{\star}$, respectively.

$h_{\bm{\theta}}\left(\mathbf{x}\right)=\operatorname{sign}\left(\mathbf{W}^{\left(2\right)}\sigma\left(\mathbf{W}^{\left(1\right)}\mathbf{x}\right)\right)$
$h_{\bm{\theta}^{\star}}\left(\mathbf{x}\right)=\operatorname{sign}\left(\mathbf{W}^{\left(2\right)}_{\star}\sigma\left(\mathbf{W}^{\left(1\right)}_{\star}\mathbf{x}\right)\right)$

where

$\mathbf{W}^{\left(1\right)}=\left[\mathbf{w}_{1},\dots,\mathbf{w}_{d_{1}}\right]^{\top}\in\mathbb{R}^{d_{1}\times
d_{0}}\,,\,\mathbf{W}^{\left(2\right)}\in\mathbb{R}^{d_{2}\times d_{1}}\,,$
$\mathbf{W}^{\left(1\right)}_{\star}=\left[\mathbf{w}_{1}^{\star},\dots,\mathbf{w}_{d_{1}^{\star}}^{\star}\right]^{\top}\in\mathbb{R}^{d_{1}^{\star}\times
d_{0}}\,,\,\mathbf{W}^{\left(2\right)}_{\star}\in\mathbb{R}^{d_{2}\times
d_{1}^{\star}}\,,$

and $\sigma\left(\cdot\right)$ is the common leaky rectifier linear unit
(LReLU, Maas et al. (2013)) with parameter $\rho\notin\\{0,1\\}$ .

As in the previous sections, our goal is to obtain generalization guarantees
by lower bounding $\tilde{p}$ and then combining this results with Theorem
3.2. To this end, we first need to define some prior on G&C hypothesis
sampling.

######  Assumption 6.1 (Prior over parameters, continuous setting).

Suppose that the weights of $h_{\bm{\theta}}$ are random such that each row of
the first layer, $\mathbf{w}_{i}$, is independently sampled from a uniform
distribution on the unit sphere $\mathbb{S}^{d_{0}-1}$, and the second layer
$\mathbf{W}^{\left(2\right)}$ is sampled uniformly888Sampling
$\mathbf{W}^{\left(2\right)}$ from the unit sphere is equivalent to sampling
it from a Gaussian distribution. In fact, any spherically symmetric
distribution in $\mathbb{R}^{d_{1}}$ will suffice, as it amounts to scaling of
the output without affecting the classification. from $\mathbb{S}^{d_{1}-1}$.
Both $\mathbf{w}_{i}$ and $\mathbf{W}^{\left(2\right)}$ are independent of the
teacher and data.

Figure 2: A two-dimensional illustration of the first layer angular margin. In
2, we show how the angle $\alpha$ is defined for a single
$\mathbf{w}_{i}^{\star}$. Note that $\alpha$ is defined as the minimal angle
when considering all rows of $\mathbf{W}_{\star}^{\left(1\right)}$. In 2, we
illustrate how $\alpha$ margin creates a cone around $\mathbf{w}_{i}^{\star}$
in which any $\mathbf{w}_{i}$ results in the same activation pattern as
$\mathbf{w}_{i}^{\star}$ (i.e., as the teacher) on a training set.

To extend this notion of teacher-equivalence from the quantized setting to the
continuous setting, we assume an “angular margin" exists between the training
set $\mathcal{S}$ and the teacher, similarly to Soudry and Hoffer (2017).

######  Definition 6.2 (First layer angular margin).

For any training set $\mathcal{S}=\\{\mathbf{x}_{n}\\}_{n=1}^{N}$, we say that
$\mathcal{S}$ has _first layer angular margin $\alpha$_ w.r.t. the teacher if

$\forall
i\in[d_{1}^{\star}]\,,\,n\in[N]:\left|\frac{\mathbf{x}_{n}^{\top}\mathbf{w}_{i}^{\star}}{\left\|\mathbf{x}_{n}\right\|_{2}\left\|\mathbf{w}_{i}^{\star}\right\|_{2}}\right|>\sin\alpha\,.$
(10)

In words, we say that $\mathcal{S}$ has _first layer angular margin $\alpha$_
if all datapoints $\mathbf{x}_{n}$ are at an angle of at least $\alpha$ from
any hyperplane induced by a row $\mathbf{w}_{i}^{\star}$ of the matrix
$\mathbf{W}^{\left(1\right)}_{\star}$. Here, the rows of
$\mathbf{W}^{\left(1\right)}_{\star}$ represent the normals to the
hyperplanes. As illustrated in Figure 2, we require some angular margin
$\alpha>0$ to guarantee that the first layer of the student network can be
within a certain angular margin of the first layer of the teacher network and
still achieve accurate classification on the training set. This assumption
prevents degenerate neurons in the first layer of the teacher network.

Similarly, for the output of the teacher network, we define the second layer
angular margin.

######  Definition 6.3 (Second layer angular margin).

For any training set $\mathcal{S}=\\{\mathbf{x}_{n}\\}_{n=1}^{N}$, we say that
$\mathcal{S}$ has _second layer angular margin $\beta$_ w.r.t. the teacher if

$\forall
n\\!\in\\!\left[N\right]\\!:\left|\frac{\mathbf{W}^{\left(2\right)}_{\star}\sigma\big{(}\mathbf{W}^{\left(1\right)}_{\star}\mathbf{x}_{n}\big{)}}{\big{\|}\mathbf{x}_{n}\big{\|}_{2}\big{\|}\mathbf{W}^{\left(2\right)}_{\star}\big{\|}_{2}}\right|>\\!\sqrt{d_{1}\\!\left(1\\!+\\!\rho^{2}\right)}\sin\beta.\\!$
(11)

In essence, this ensures some margin in the output of the teacher network.
With this definition, our main assumption for the continuous case is stated
below.

######  Assumption 6.4.

Let $\alpha<\beta\in\left(0,\frac{\pi}{2}\right)$. There exist
$\lambda\in\left(0,1\right)$ such that, with probability at least $1-\lambda$
over $\mathcal{S}\sim\mathcal{D}^{N}$, $\mathcal{S}$ has first layer angular
margin $\alpha$ (Definition 6.2) and second layer angular margin $\beta$
(Definition 6.3).

######  Remark 6.5.

Note that $\alpha$ is the minimal margin of all hidden neurons, while $\beta$
is the margin of the single network output. Thus, intuitively, $\beta$ is
usually larger than $\alpha$. For Gaussian data, we show empirically in Figure
3 in Appendix C, that the assumption $\beta>\alpha$ holds with high
probability.

This assumption allows us to extend the results from the previous section to a
continuous setting.

######  Definition 6.6.

For some random hypothesis $h$ from the prior $\mathcal{P}$, the interpolation
probability is defined as

$\displaystyle\hat{p}\triangleq\mathbb{P}_{h\sim\mathcal{P}}\left(\mathcal{L}_{\mathcal{S}}(h)=0\right)$

######  Theorem 6.7 (Interpolation of Continuous Networks).

Assume that $\hat{p}<\frac{1}{2}$ and $d_{0}\gg d_{1}^{\star}\gg 1$ 999This
assumption is used to simplify the bound. A non-asymptotic version that does
not require this assumption is in Appendix C.. Then under Assumption 6.4, for
any $\epsilon,\delta\in\left(0,1\right)$ we have

$\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\right)\geq
1-\delta\ -\lambda,$

whenever $N$ is larger than the sample complexity

$\displaystyle\frac{\hat{C}^{\mathrm{cont}}+2\log\left(\hat{C}^{\mathrm{cont}}\right)+4\log\left(\frac{8}{\delta}\right)}{\epsilon}\,,$

with $\gamma=\arccos{\frac{\cos{\beta}}{\cos{\alpha}}}$ and

$\displaystyle\hat{C}^{\mathrm{cont}}$
$\displaystyle=-d_{1}^{\star}d_{0}\log\left(\sin\left(\alpha\right)\right)-d_{1}\log\left(\sin\left(\gamma\right)\right)+\frac{1}{2}d_{1}^{\star}\log\left(d_{0}\right)+O\left(d_{1}^{\star}+\log{\left(d_{1}\right)}\right)\,.$

The full proof is in Appendix C.

######  Remark 6.8.

Since Assumption 6.4 gives margin only in high probability, we use a different
generalization guarantee than the one in Theorem 3.2 which takes into account
the interpolation probability $\hat{p}$, instead of $\tilde{p}$. See Appendix
A.6 for more details.

Implications. Our results in this section rely on a margin assumption instead
of quantized weights. This margin assumption can improve the quantized bound
given the data $\mathcal{S}$ has a large enough margin from the teacher.
However, for a generic input distribution without any pre-set margin (e.g.,
standard Gaussian) we observed empirically the resulting margin is near the
numerical precision level, so the resulting bound is not better than the
quantized approach.

##  7 Related work

Random interpolating neural networks. Chiang et al. (2023) empirically studied
a few gradient-free algorithms for the optimization of neural networks,
suggesting that generalization is not necessarily due to the properties of the
SGD. For the G&C algorithm, they also empirically investigated the effect of
the loss on the generalization. We focus on the 0-1, rather than some
surrogate loss function. Chiang et al. (2023) focused only on small-scale
datasets since it is not possible to run their experiments when the training
set is larger than a few dozen samples. Theisen et al. (2021) provided a
theoretical analysis of random interpolating linear models. In contrast, our
work focuses on deeper models with non-linear activation functions, and our
teacher assumption relies on depth, such that it is possible to have many
zeroed-out hidden neurons and obtain generalization guarantees that stem from
the redundancy in parameterized deep networks. Valle-Perez et al. (2019);
Mingard et al. (2021) used a connection between neural networks and Gaussian
processes to model random interpolating networks, which usually requires the
width of the network to be infinite, in contrast with our finite width
setting.

Redundancy in neural networks. The Lottery Ticket Hypothesis (Frankle and
Carbin, 2019) suggests that for any random neural network, there exists a
sparse sub-network capable of competitive generalization with the original. A
related hypothesis was conjectured by Ramanujan et al. (2020) and later proven
by Malach et al. (2020) and states that it is possible to prune an initialized
neural network without significantly affecting the obtained predictions. In
contrast, our work, while also focusing on random neural networks, is oriented
towards providing assurances regarding the generalization of these random
networks, when conditioned on the event of perfectly classifying the training
data. Also, we operate under the assumption of a narrow teacher, which is
sparse in the number of neurons — in contrast to the sub-network in the
Lottery Ticket Hypothesis which is sparse in the number of weights.

##  8 Discussion

Summary. In this work, we examined the generalization of samples from the NN
posterior with the 0-1 loss (2). We proved that even when using a uniform (or
‘uniform-like’) prior for the parameters, typical samples from the NN
posterior are biased toward low generalization error — if there exist
sufficiently narrow NN teachers.

Implications of narrowness. Assuming a narrow teacher may sometimes limit the
class of possible target functions. For example, in a fully connected NN, if
the first hidden layer width is smaller than the input width
$\left(d_{0}>d_{1}^{\star}\right)$ then the teacher NN must be constant on the
$d_{0}-d_{1}^{*}$ nullspace of the first weight layer. However, this is not an
issue for a convolutional NN, since typically the number of input channels is
small (e.g., $c_{0}=3$ for RGB images), and so $c_{0}<c_{1}^{*}$ is
reasonable. In any case, to represent potentially complex target functions
with narrow NNs we require depth (Kidger and Lyons, 2020) — both for student
and teacher. This might suggest another reason why deep architectures are more
useful in realistic settings.

Quantized models. Our results in section 5 rely on NNs to have a quantized
numerical format. The sample complexity we obtain is a product of the
parameter count of the model (mainly the teacher) and the quantization bits.
The simplicity of the bound allows it to be applied to other architectures as
well. For example, we can add pooling layers to the CNN models we analyzed.
Also, using the same considerations, we may obtain similar results for multi-
head attention layers. Moreover, using quantization-aware methods (Hubara et
al., 2018) one can reduce numerical precision to improve the bound. For
example, using 2bits weights (and activations) in ResNet50 on ImageNet results
in only 0.5% degradation in accuracy (Liu et al., 2022)). Such quantization
approaches are common in compression-type bounds (e.g. Lotfi et al. (2022)).
However, there the goal is to compress the learned model (the student), while
here we only need some compressed model to exist (i.e. the narrow teacher).

Beyond interpolators. In this work we focus for simplicity on NN
interpolators, but in many scenarios, the training loss does not reach zero.
It should be straightforward to generalize our results to this non-realizable
case, where the teacher NN does not reach zero loss (i.e., there is some
irreducible error). Additionally, the implicit bias of SGD is partially known
in some cases (e.g., Lyu and Li (2020)), so it would be interesting to
understand the generalization of a typical NN interpolator that also obeys
this implicit bias.

## Acknowledgements

The authors would like to thank Itay Evron and Yaniv Blumenfeld for valuable
comments and discussions. The research of DS was Funded by the European Union
(ERC, A-B-C-Deep, 101039436). Views and opinions expressed are however those
of the author only and do not necessarily reflect those of the European Union
or the European Research Council Executive Agency (ERCEA). Neither the
European Union nor the granting authority can be held responsible for them. DS
also acknowledges the support of the Schmidt Career Advancement Chair in AI.
Part of this work was done as part of the NSF-Simons funded Collaboration on
the Theoretical Foundations of Deep Learning. NS was supported in part by NSF
IIS awards.

## References

  * Alquier (2023) P. Alquier.  User-friendly introduction to pac-bayes bounds.  _arXiv preprint arXiv:2110.11216_ , 2023.
  * Arora et al. (2019) S. Arora, N. Cohen, W. Hu, and Y. Luo.  Implicit regularization in deep matrix factorization.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Blumer et al. (1987) A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth.  Occam’s razor.  _Information processing letters_ , 24(6):377–380, 1987.
  * Chiang et al. (2023) P. Chiang, R. Ni, D. Y. Miller, A. Bansal, J. Geiping, M. Goldblum, and T. Goldstein.  Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Chizat and Bach (2020) L. Chizat and F. Bach.  Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss.  In J. Abernethy and S. Agarwal, editors, _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pages 1305–1338. PMLR, 09–12 Jul 2020.
  * Frankle and Carbin (2019) J. Frankle and M. Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  In _International Conference on Learning Representations_ , 2019.
  * Golowich et al. (2018) N. Golowich, A. Rakhlin, and O. Shamir.  Size-independent sample complexity of neural networks.  In _Conference On Learning Theory_ , pages 297–299. PMLR, 2018.
  * Gunasekar et al. (2017) S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro.  Implicit regularization in matrix factorization.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Hubara et al. (2018) I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio.  Quantized neural networks: Training neural networks with low precision weights and activations.  _journal of machine learning research_ , 18(187):1–30, 2018.
  * Ioffe and Szegedy (2015) S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _International conference on machine learning_ , pages 448–456. pmlr, 2015.
  * Kidger and Lyons (2020) P. Kidger and T. Lyons.  Universal approximation with deep narrow networks.  In _Conference on learning theory_ , pages 2306–2327. PMLR, 2020.
  * Langford and Seeger (2002) J. Langford and M. Seeger.  _Bounds for averaging classifiers_.  CMU Technical Report CMU-CS-01-102, 2002, 2002.
  * Liu et al. (2022) Z. Liu, K.-T. Cheng, D. Huang, E. P. Xing, and Z. Shen.  Nonuniform-to-uniform quantization: Towards accurate quantization via generalized straight-through estimation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 4942–4952, June 2022.
  * Lotfi et al. (2022) S. Lotfi, M. Finzi, S. Kapoor, A. Potapczynski, M. Goldblum, and A. G. Wilson.  Pac-bayes compression bounds so tight that they can explain generalization.  _Advances in Neural Information Processing Systems_ , 35:31459–31473, 2022.
  * Lyu and Li (2020) K. Lyu and J. Li.  Gradient descent maximizes the margin of homogeneous neural networks.  In _International Conference on Learning Representations_ , 2020.
  * Maas et al. (2013) A. L. Maas, A. Y. Hannun, A. Y. Ng, et al.  Rectifier nonlinearities improve neural network acoustic models.  In _Proc. icml_ , volume 30, page 3. Atlanta, GA, 2013.
  * Malach et al. (2020) E. Malach, G. Yehudai, S. Shalev-Schwartz, and O. Shamir.  Proving the lottery ticket hypothesis: Pruning is all you need.  In _International Conference on Machine Learning_ , pages 6682–6691. PMLR, 2020.
  * McAllester (2003) D. McAllester.  Simplified pac-bayesian margin bounds.  In B. Schölkopf and M. K. Warmuth, editors, _Learning Theory and Kernel Machines_ , pages 203–215, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.  ISBN 978-3-540-45167-9.
  * McAllester (1999) D. A. McAllester.  Some pac-bayesian theorems.  _Machine Learning_ , 37(3):355–363, Dec 1999.  ISSN 1573-0565.  doi: 10.1023/A:1007618624809.
  * Mingard et al. (2021) C. Mingard, G. Valle-Pérez, J. Skalse, and A. A. Louis.  Is sgd a bayesian sampler? well, almost.  _The Journal of Machine Learning Research_ , 22(1):3579–3642, 2021.
  * Neyshabur et al. (2015) B. Neyshabur, R. Tomioka, and N. Srebro.  Norm-based capacity control in neural networks.  In _Conference on learning theory_ , pages 1376–1401. PMLR, 2015.
  * Ramanujan et al. (2020) V. Ramanujan, M. Wortsman, A. Kembhavi, A. Farhadi, and M. Rastegari.  What’s hidden in a randomly weighted neural network?  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 11893–11902, 2020.
  * Salimans and Kingma (2016) T. Salimans and D. P. Kingma.  Weight normalization: A simple reparameterization to accelerate training of deep neural networks.  _Advances in neural information processing systems_ , 29, 2016.
  * Shalev-Shwartz and Ben-David (2014) S. Shalev-Shwartz and S. Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Soudry and Hoffer (2017) D. Soudry and E. Hoffer.  Exponentially vanishing sub-optimal local minima in multilayer neural networks.  In _ICLR workshop paper_ , 2017.
  * Soudry et al. (2018) D. Soudry, E. Hoffer, and N. Srebro.  The implicit bias of gradient descent on separable data.  In _International Conference on Learning Representations_ , 2018.
  * Theisen et al. (2021) R. Theisen, J. Klusowski, and M. Mahoney.  Good classifiers are abundant in the interpolating regime.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3376–3384. PMLR, 2021.
  * TV (2017) M. TV.  If $x,y$ are independent $\chi^{2}$ with $m$ and $n$ degrees of freedom, then $\frac{X}{X+Y}\sim\beta(m/2,n/2)$.  Mathematics Stack Exchange, 2017.  URL https://math.stackexchange.com/q/2263641.  URL:https://math.stackexchange.com/q/2263641 (version: 2017-05-03).
  * Valle-Perez et al. (2019) G. Valle-Perez, C. Q. Camargo, and A. A. Louis.  Deep learning generalizes because the parameter-function map is biased towards simple functions.  In _International Conference on Learning Representations_ , 2019.
  * Vardi (2023) G. Vardi.  On the implicit bias in deep-learning algorithms.  _Communications of the ACM_ , 66(6):86–93, 2023.
  * Zhang et al. (2017) C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations_ , 2017.
  * Zhang et al. (2019) H. Zhang, Y. N. Dauphin, and T. Ma.  Residual learning without normalization via better initialization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=H1gsz30cKX.

##  Appendix A Generalization Results

This section contains:

  * •

A restatement and discussion on the connection to a well-known result from
[Shalev-Shwartz and Ben-David, 2014, Corollary 2.3] in Appendix A.1.

  * •

The proof of our primary generalization result (Theorem 3.2) in Appendix A.2.

  * •

The proof of Corollary 3.3 in Appendix A.3.

  * •

A further discussion on the relation of Theorem 3.2 to PAC-Bayes is brought in
Appendix A.4

  * •

In Appendix A.5 we prove a refined version of Theorem 3.2 and discuss its
implications.

  * •

The proof of an alternative generalization result, used for proving
generalization in the continuous setting, in Appendix A.6.

###  A.1 Finite Hypothesis Class PAC Generalization Bound

Here we present a classic generalization bound for finite hypothesis class
adapted from Shalev-Shwartz and Ben-David [2014], which we will use throughout
our paper.

######  Theorem A.1.

$[$adapted from [Shalev-Shwartz and Ben-David, 2014, Corollary 2.3]$]$ Let
$\mathcal{H}$ be a finite hypothesis class. Let $\delta\in\left(0,1\right)$
and $\epsilon>0$ and let $N$ be an integer that satisfies

$\displaystyle
N\geq\frac{\log\left({\left\lvert{\mathcal{H}}\right\rvert}/\delta\right)}{\epsilon}\,.$

Then, for any realizable data distribution $\mathcal{D}$, with probability of
at least $1-\delta$ over the choice of an i.i.d sample $S$ of size $N$, we
have that for every interpolating101010[Shalev-Shwartz and Ben-David, 2014,
Corollary 2.3] is more general, but we focus on interpolating hypotheses.
hypothesis, $h_{\bm{\theta}}$, it holds that

$\displaystyle\mathcal{L}_{\mathcal{D}}\left(h_{\mathcal{S}}\right)\leq\epsilon\,.$

Applying Theorem A.1 to quantized neural networks. It is possible to directly
obtain a generalization bound for any quantized model, such as those presented
in Section 5. Note that the hypothesis class of quantized models with a finite
number of parameters, for example, neural networks with finite width and
depth, with $M$ parameters and $Q$ quantization levels is finite and of size
$\left|\mathcal{H}\right|=Q^{M}$. Therefore, the sample complexity from
Theorem A.1 becomes

$\displaystyle
N\geq\frac{M\log\left(Q\right)+\log\left(\frac{1}{\delta}\right)}{\epsilon}$
(12)

Note that Theorem A.1 is used to prove Theorem 3.2.The sample complexity in
(12) is dependent on the student parameters, and therefore much worse than the
sample complexities we derive throughout our paper.

###  A.2 Proving the Generalization of Algorithm 1

In this section, we rely on the existence of the teacher to provide guarantee
on the generalization of Algorithm 1. We will first restate Theorem 3.2:

######  Theorem A.2 (Theorem 3.2 restated).

Let $\epsilon\in\left(0,1\right)$ and $\delta\in\left(0,\frac{1}{5}\right)$,
and assume that $\tilde{p}<\frac{1}{2}$. For any $N$ larger than

$\displaystyle\left(-\log\left({\tilde{p}}\right)+3\log\left(\frac{2}{\delta}\right)\right)\frac{1}{\epsilon}\,,$

the sample complexity, we have that

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\right)\geq
1-\delta\,.$

Proof Outline. The idea is to show that the probability to sample a TE model
within a finite number of steps $\tau$ is large. Conditioning on that event,
we treat those models as a realizable finite hypothesis class, obtaining the
sample complexity using Theorem A.1, which is then bounded, and after some
technical details the theorem is obtained.

We first recall Def. 3.1 and add some notation:

######  Definition A.3.

$[$Def. 3.1 extended$]$ For any hypothesis class $\mathcal{H}$, we say that
$h\in\mathcal{H}$ is a teacher-equivalent w.r.t $\mathcal{D}$ (TE) model, and
denote $h\equiv h^{\star}$, if

$\mathbb{P}_{\mathbf{x}\sim\mathcal{D}}\left(h\left(\mathbf{x}\right)=h^{\star}\left(\mathbf{x}\right)\right)=1\,.$

We denote the probability of a random hypothesis to be TE by

$\displaystyle\tilde{p}=\mathbb{P}_{h\sim\mathcal{P}}\left(h\equiv
h^{\star}\right)\,$

and denote

$\displaystyle h^{\star}\in\mathcal{H}\;\Longleftrightarrow\;\exists
h\in\mathcal{H}\;:\;h\equiv h^{\star}\;.$

######  Definition A.4.

Recall the sequence $\left(h_{t}\right)_{t=1}^{\infty}$ from Algorithm 1 is
sampled such that $h_{t}\overset{\textrm{i.i.d.}}{\sim}\mathcal{P}$. For any
$\tau\in\mathbb{N}$ we define

$\displaystyle\mathcal{H}_{\tau}=\\{h_{1},\dots,h_{\tau}\\}\sim\mathcal{P}^{\tau}$

as the finite hypothesis class created from the first $\tau$ hypotheses.

We first show that the probability of sampling a TE model early enough is
large.

######  Lemma A.5.

For
$\tau=\left\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right\rceil$
it holds that

$\displaystyle\mathbb{P}_{\mathcal{H}_{\tau}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)\geq
1-\delta_{h}\,.$

That is, the probability to have a TE model within the first $\tau$ sampled
model is at least $1-\delta_{h}$.

###### Proof.

Since $h_{t}$ is sampled $i.i.d$ from $\mathcal{P}$, we have that

$\displaystyle\mathbb{P}_{\mathcal{H}_{\tau}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)$
$\displaystyle=1-\mathbb{P}\left(\forall t=1,\dots,\tau\ h_{t}\not\equiv
h^{\star}\right)$
$\displaystyle=1-\prod_{t=1}^{\tau}\mathbb{P}\left(h_{t}\not\equiv
h^{\star}\right)$ $\displaystyle=1-\left(1-\tilde{p}\right)^{\tau}.$

Choosing
$\tau=\left\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right\rceil$
we get

$\displaystyle\left(1-\tilde{p}\right)^{\tau}$
$\displaystyle=\left(1-\tilde{p}\right)^{\left\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right\rceil}$
$\displaystyle\leq\left(1-\tilde{p}\right)^{\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}}$
$\displaystyle=\exp\left(\log\left(1-\tilde{p}\right)\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right)$
$\displaystyle=\delta_{h}$

which means

$\mathbb{P}_{\mathcal{H}_{\tau}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)\geq
1-\delta_{h}.$

∎

We now use Theorem A.1 to obtain the sample complexity.

######  Lemma A.6.

Let $\epsilon\in\left(0,1\right)$, and let $\tau\in\mathbb{N}$ and
$\mathcal{H}_{\tau}$ such that $h^{\star}\in\mathcal{H}_{\tau}$. Then for any
interpolating model $h_{\mathcal{S}}\in\mathcal{H}_{\tau}$, and
$N\geq\frac{\log\left({\tau}/{\delta_{\mathcal{S}}}\right)}{\epsilon}$

$\displaystyle\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}\left(h_{\mathcal{S}}\right)\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\,,$

###### Proof.

If $h^{\star}\in\mathcal{H}_{\tau}$ then $\mathcal{H}_{\tau}$ is realizable,
so we get from Theorem A.1 with

$\displaystyle
N\geq\frac{\log\left(\frac{{\left\lvert{\mathcal{H}_{\tau}}\right\rvert}}{\delta_{\mathcal{S}}}\right)}{\epsilon}=\frac{\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)}{\epsilon}$

we get the lemma. ∎

We now wish to upper bound the sample complexity.

######  Lemma A.7.

For
$\tau=\left\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right\rceil$,
under the assumption that $\tilde{p}<\frac{1}{2}$, it holds that

$\displaystyle\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)\leq\log\left(\frac{1}{\tilde{p}}\right)+\log\left(\frac{1}{\delta_{\mathcal{S}}}\right)+\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)+\frac{\tilde{p}}{\log\left(\frac{1}{\delta_{h}}\right)}$

###### Proof.

First, we bound

$\displaystyle\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)$
$\displaystyle=\log\left(\frac{\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\rceil}{\delta_{\mathcal{S}}}\right)$
$\displaystyle\leq\log\left(\frac{\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}+1}{\delta_{\mathcal{S}}}\right)\,,$

which, after some simplification, becomes

$\displaystyle\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)\
\leq\log\left(\frac{\log\left(\delta_{h}\right)+\log\left(1-\tilde{p}\right)}{\delta_{\mathcal{S}}\log\left(1-\tilde{p}\right)}\right)\,.$
(13)

We now recall the Taylor expansion of $\log\left(c+x\right)$ around $x=0$ for
some $c>0$,

$\displaystyle\log\left(c+x\right)=\log\left(c\right)+\frac{x}{c}-\frac{x^{2}}{2c^{2}}+O\left(x^{3}\right)\,,$
(14)

plugging $c=1$ and $x\leftarrow-x$ into (14) we get the following bounds for
any $x\in\left[0,\frac{1}{2}\right]$:

$\displaystyle-x-x^{2}\leq\log\left(1-x\right)\leq-x\,.$ (15)

Combining (15) with (13) we get

$\displaystyle\log\left(\frac{\log\left(\delta_{h}\right)+\log\left(1-\tilde{p}\right)}{\delta_{\mathcal{S}}\log\left(1-\tilde{p}\right)}\right)$
$\displaystyle\leq\log\left(\frac{\log\left(\delta_{h}\right)-\tilde{p}}{\delta_{\mathcal{S}}\left(-\tilde{p}-{p^{\star}}^{2}\right)}\right),$

which can be written as

$\displaystyle\log\left(\frac{\log\left(\delta_{h}\right)+\log\left(1-\tilde{p}\right)}{\delta_{\mathcal{S}}\log\left(1-\tilde{p}\right)}\right)\leq\log\left(\frac{1}{\delta_{\mathcal{S}}\left(\tilde{p}+{p^{\star}}^{2}\right)}\right)+\log\left(\tilde{p}+\log\left(\frac{1}{\delta_{h}}\right)\right)\,.$
(16)

We now recall that $\log(c+x)$ is a concave function, and therefore its graph
in any $x$ is below the graph of its tangent in $x=0$, that is, from (14),

$\displaystyle\log(c+x)\leq\log\left(c\right)+\left(\frac{d}{dx}\left(\log(c+x)\right)\mid_{x=0}\right)x=\log\left(c\right)+\frac{x}{c}\,.$
(17)

Setting $c=\log\left(\frac{1}{\delta_{h}}\right)\in\left[0,\frac{1}{2}\right]$
and $x=\tilde{p}$ into (17), we obtain

$\displaystyle\log\left(\tilde{p}+\log\left(\frac{1}{\delta_{h}}\right)\right)\leq\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)+\frac{\tilde{p}}{\log\left(\frac{1}{\delta_{h}}\right)}\,.$
(18)

Note that

$\displaystyle\log\left(\frac{1}{\tilde{p}+{p^{\star}}^{2}}\right)\leq\log\left(\frac{1}{\tilde{p}}\right)\,,$
(19)

and therefore combining (19), (18) and (16) together with 13 we finish the
proof:

$\displaystyle\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)\ $
$\displaystyle\leq\log\left(\frac{\log\left(\delta_{h}\right)+\log\left(1-\tilde{p}\right)}{\delta_{\mathcal{S}}\log\left(1-\tilde{p}\right)}\right)$
$\displaystyle\leq\log\left(\frac{1}{\delta_{\mathcal{S}}\left(\tilde{p}+{p^{\star}}^{2}\right)}\right)+\log\left(\tilde{p}+\log\left(\frac{1}{\delta_{h}}\right)\right)$
$\displaystyle\leq\log\left(\frac{1}{\delta_{\mathcal{S}}}\right)+\log\left(\frac{1}{\tilde{p}}\right)+\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)+\frac{\tilde{p}}{\log\left(\frac{1}{\delta_{h}}\right)}\,.$

∎

We are now ready to prove Theorem A.2:

###### Proof.

(of Theorem A.2) Note that $h\sim\mathcal{P}_{\mathcal{S}}$ is interpolating
by definition, and therefore, from Lemma A.6, we have that for any
$\tau\in\mathbb{N}$ it holds that

$\displaystyle\forall\,\epsilon\geq\frac{\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)}{N}\quad\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}\left(h\right)\leq\epsilon\middle|h^{\star}\in\mathcal{H}_{\tau}\right)=\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}\left(\bar{h}(S)\right)\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\,,$ (20)

Where $\bar{h}\left(S\right)\in\mathcal{H}_{\tau}$ is some arbitrary
interpolate, since from Lemma A.6 this probability is equal for any
interpolator. For
$\tau=\left\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right\rceil$
we similarly get

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\right)$
$\displaystyle=$ $\displaystyle\left[\text{Total Probability}\right]$
$\displaystyle=\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\middle|h^{\star}\in\mathcal{H}_{\tau}\right)\mathbb{P}_{h\sim\mathcal{P}_{\mathcal{S}}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)$
$\displaystyle\,+\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\middle|h^{\star}\notin\mathcal{H}_{\tau}\right)\mathbb{P}_{h\sim\mathcal{P}_{\mathcal{S}}}\left(h^{\star}\notin\mathcal{H}_{\tau}\right)$
$\displaystyle\left[\text{Probability is non-negative}\right]$
$\displaystyle\geq\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\middle|h^{\star}\in\mathcal{H}_{\tau}\right)\mathbb{P}_{h\sim\mathcal{P}_{\mathcal{S}}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)$
$\displaystyle\left[\text{Lemma~{}\ref{lem: eta bound}}\right]$
$\displaystyle\geq\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\middle|h^{\star}\in\mathcal{H}_{\tau}\right)\left(1-\delta_{h}\right)$
$\displaystyle\left[\text{\eqref{eq:mention lemma in main gen bound prop
proof}}\right]$
$\displaystyle\geq\left(1-\delta_{\mathcal{S}}\right)\left(1-\delta_{h}\right)\,.$

And as before, this is true for any
$N\geq\frac{\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)}{\epsilon}$.
specifically, by Lemma A.7, it is true for $N$ greater than

$\displaystyle\frac{\log\left(\frac{1}{\delta_{\mathcal{S}}}\right)+\log\left(\frac{1}{\tilde{p}}\right)+\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)+\frac{\tilde{p}}{\log\left(\frac{1}{\delta_{h}}\right)}}{\epsilon}\,,$

the sample complexity. Now we can choose
$\delta_{\mathcal{S}},\delta_{h}=\frac{\delta}{2}$, and then for any $N$
greater than

$\displaystyle\frac{\log\left(\frac{2}{\delta}\right)+\log\left(\frac{1}{\tilde{p}}\right)+\log\left(\log\left(\frac{2}{\delta}\right)\right)+\frac{\tilde{p}}{\log\left(\frac{2}{\delta}\right)}}{\epsilon}\,,$

we have that

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N},h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\right)$
$\displaystyle\geq\left(1-\frac{\delta}{2}\right)^{2}$
$\displaystyle=1-\delta_{\mathcal{S}}+\frac{\delta^{2}}{4}$ $\displaystyle\geq
1-\delta\,.$

Note that for any $\delta\in\left(0,\frac{1}{5}\right)$ we have that

$\displaystyle\log\left(\log\left(\frac{2}{\delta}\right)\right)+\frac{\tilde{p}}{\log\left(\frac{2}{\delta}\right)}\leq
2\log\left(\frac{2}{\delta}\right)\,,$

bounding the sample complexity for simplification with

$\displaystyle\left(-\log\left({\tilde{p}}\right)+3\log\left(\frac{2}{\delta}\right)\right)\frac{1}{\epsilon}\,.$

∎

###  A.3 Proof for the Volume of Generalizing Interpolators (Corollary 3.3)

We first restate Corollary 3.3, and then we will give its formal proof:

######  Corollary A.8 (volume of generalizing interpolators restated).

For $\epsilon,\delta$ as above, and any $N$ larger than

$\displaystyle\frac{-\log\left({\tilde{p}}\right)+6\log\left(\frac{2}{\delta}\right)}{\epsilon}\,,$

the sample complexity, we have that

$\displaystyle\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\mathbb{P}_{h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)\geq\epsilon\right)\geq\delta\right)\leq\delta\,.$

###### Proof.

Using Theorem 3.2, for any

$\displaystyle
N\geq\frac{-\log\left({\tilde{p}}\right)+6\log\left(\frac{2}{\delta}\right)}{\epsilon}\geq\frac{-\log\left({\tilde{p}}\right)+3\log\left(\frac{2}{\delta^{2}}\right)}{\epsilon}$

we have that

$\displaystyle\delta^{2}$
$\displaystyle\geq\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N},h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)\geq\epsilon\right)$
$\displaystyle=\mathbb{E}_{\mathcal{S}\sim\mathcal{D}^{N},h\sim\mathcal{P_{S}}}\left[\mathbb{I}\left\\{\mathcal{L_{D}}\left(h\right)\geq\epsilon\right\\}\right]$
$\displaystyle=\mathbb{E}_{\mathcal{S}\sim\mathcal{D}^{N}}\left[\mathbb{E}_{h\sim\mathcal{P_{S}}}\left[\mathbb{\mathbb{I}}\left\\{\mathcal{L_{D}}\left(h\right)\geq\epsilon\right\\}\right]\right]$
$\displaystyle=\mathbb{E}_{\mathcal{S}\sim\mathcal{D}^{N}}\left[\mathbb{P}_{h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)\geq\epsilon\right)\right]$

and then we use Markov’s inequality

$\displaystyle\mathbb{P}_{\mathcal{S}}\left(\mathbb{P}_{h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)\geq\epsilon\right)\geq\delta\right)\leq\frac{\mathbb{E}_{\mathcal{S}\sim\mathcal{D}^{N}}\left[\mathbb{P}_{h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)\geq\epsilon\right)\right]}{\delta}\leq\delta\,,$

That is,

$\displaystyle\mathbb{P}_{\mathcal{S}}\left(\mathbb{P}_{h\sim\mathcal{P_{S}}}\left(\mathcal{L_{D}}\left(h\right)<\epsilon\right)\geq
1-\delta\right)\geq 1-\delta\,.$

∎

###  A.4 Relationship to PAC Bayes

As stated in Section 3, a similar result to Theorem 3.2 could be derived with
PAC-Bayes analysis [McAllester, 1999], which typically focuses on the expected
population error
$\mathbb{E}_{h\sim\mathcal{P}_{\mathcal{S}}}\left[\mathcal{L}_{\mathcal{D}}(h)\right]$
of a sample from the posterior. A standard PAC-Bayes bound [Langford and
Seeger, 2002, McAllester, 2003] yields the following result:

######  Proposition A.9.

Let $\epsilon>0$ and $\delta\in\left(0,1\right)$. Then with sample complexity

$\displaystyle
O\left(\frac{-\log\left(\tilde{p}\right)+\log\left(\frac{1}{\delta}\right)}{\epsilon}\right)$

we have that

$\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\;\mathbb{E}_{h\sim\mathcal{P}_{\mathcal{S}}}\left[\mathcal{L}_{\mathcal{D}}(h)\right]<\epsilon\;\right)\geq
1-\delta.$

We can naively use this bound together with Markov’s inequality to get a
single sample bound.

######  Corollary A.10.

Let $\epsilon>0$ and $\delta\in\left(0,1\right)$. Then with sample complexity

$\displaystyle
O\left(\frac{-\log\left(\tilde{p}\right)+\log\left(\frac{1}{\delta}\right)}{\epsilon\delta}\right)$

we have that

$\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\;\mathbb{P}_{h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)<\epsilon\right)\geq
1-\delta\;\right)\geq 1-\delta.$

###### Proof.

Using Prop. A.9,

$\displaystyle\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\;\mathbb{E}_{h\sim\mathcal{P}_{\mathcal{S}}}\left[\mathcal{L}_{\mathcal{D}}(h)\right]<\epsilon\delta\right)\;\geq
1-\delta\,.$

Then using Markov’s inequality, w.p. $1-\delta$ over
$\mathcal{S}\sim\mathcal{D}^{N}$,

$\displaystyle\mathbb{P}_{h\sim\mathcal{P}_{\mathcal{S}}}\left(\mathcal{L}_{\mathcal{D}}(h)\geq\epsilon\right)\leq\frac{\mathbb{E}_{h\sim\mathcal{P}_{\mathcal{S}}}\left[\mathcal{L}_{\mathcal{D}}(h)\right]}{\epsilon}<\frac{\epsilon\delta}{\epsilon}=\delta\,.$

By using the complement probability we get the result. ∎

Note that the sample complexity in Corollary A.10 is larger than the one in
Corollary 3.3. Instead of additive $\log\left(\frac{1}{\delta}\right)$ factors
in Corollary 3.3, here we have a multiplicative $\frac{1}{\delta}$ factor.

###  A.5 Proving a Refined Version of Theorem 3.2

Motivation. Note that two sources of randomness affect the sample complexity
in Theorem 3.2: the random sampling of hypotheses from the prior $\mathcal{P}$
in G&C algorithm and the random sampling of the dataset from
$\mathcal{D}^{N}$. To understand how each of these sources affects the
obtained random complexity, we derive a refined generalization bound:

######  Theorem A.11 (_G &C Generalization, refined_).

Let $\epsilon,\delta_{\mathcal{S}}\in\left(0,1\right)$, and
$\delta_{h}\in\left(0,\frac{1}{5}\right)$, and assume that
$\tilde{p}<\frac{1}{2}$. For any $N$ larger than

$\displaystyle\left(-\log\left(\tilde{p}\right)+\log\left(\frac{1}{\delta_{\mathcal{S}}}\right)+2\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)\right)\frac{1}{\epsilon}\,,$

the sample complexity, we have that

$\displaystyle\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(S))<\epsilon\right)\geq
1-\delta_{\mathcal{S}}\right)\geq 1-\delta_{h}\,.$

######  Remark A.12.

Note that the randomness in $\mathcal{A}_{\mathcal{P}}$ is only from the
sampling of the sequence $\left(h_{t}\right)_{t=1}^{\infty}$, and not from the
dependence of $\mathcal{A}_{\mathcal{P}}\left(\mathcal{S}\right)$ on
$\mathcal{S}$.

Discussion. Theorem A.11 guarantees generalization with probability at least
$1-\delta_{h}$ over the hypothesis sampling and probability
$\delta_{\mathcal{S}}$ over the data sampling. This separation between
$\delta_{h}$ and $\delta_{\mathcal{S}}$ highlights how both sources of
randomness play a role in generalization. Interestingly, the sample complexity
term $N$ exhibits a logarithmic dependence on $\delta_{\mathcal{S}}$ and only
a doubly logarithmic dependence on $\delta_{h}$. Thus, for any
$\delta_{\mathcal{S}}$ and $\epsilon$, the probability of not sampling a PAC
interpolator decays extremely fast (doubly exponential in $N$):

$\displaystyle\delta_{h}=\exp\left(-\exp\left(\frac{1}{2}\left(\epsilon
N+\log\left({\tilde{p}}\right)+\log\left({\delta_{\mathcal{S}}}\right)\right)\right)\right)\,.$

In other words, the sampled interpolator is ‘typically PAC’, i.e., PAC with
overwhelmingly high probability over the sampled interpolator sequence
$\left(h_{t}\right)_{t=1}^{\infty}$.

###### Proof.

Recall that the hypothesis chosen by G&C, $h\sim\mathcal{P}_{\mathcal{S}}$, is
interpolating by definition. Set
$\tau=\left\lceil\frac{\log\left(\delta_{h}\right)}{\log\left(1-\tilde{p}\right)}\right\rceil$,
then

$\displaystyle\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(S))\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\right)$ $\displaystyle\left[\text{Total
probability}\right]=$
$\displaystyle\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(S))\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\middle|h^{\star}\in\mathcal{H}_{\tau}\right)\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)$
$\displaystyle+$
$\displaystyle\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(S))\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\middle|h^{\star}\notin\mathcal{H}_{\tau}\right)\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(h^{\star}\notin\mathcal{H}_{\tau}\right)$
$\displaystyle\left[\text{Probability is non-negative}\right]\geq$
$\displaystyle\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(S))\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\middle|h^{\star}\in\mathcal{H}_{\tau}\right)\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(h^{\star}\in\mathcal{H}_{\tau}\right)$
$\displaystyle\left[\text{Lemma~{}\ref{lem: eta bound}}\right]\geq$
$\displaystyle\mathbb{P}_{\mathcal{A}_{\mathcal{P}}}\left(\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(S))\leq\epsilon\right)\geq
1-\delta_{\mathcal{S}}\middle|h^{\star}\in\mathcal{H}_{\tau}\right)\left(1-\delta_{h}\right)$
$\displaystyle\left[\text{Lemma~{}\ref{lem: app use finite hypothesis for gen
bound}}\right]=$ $\displaystyle 1-\delta_{h}\,.$

This holds for any
$N\geq\frac{\log\left(\frac{\tau}{\delta_{\mathcal{S}}}\right)}{\epsilon}$.
Specifically, by Lemma A.7, it holds for any $N$ larger than

$\displaystyle\frac{\log\left(\frac{1}{\tilde{p}}\right)+\log\left(\frac{1}{\delta_{\mathcal{S}}}\right)+\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)}{\epsilon}+\frac{\tilde{p}}{\epsilon\log\left(\frac{1}{\delta_{h}}\right)}\,,$

Note that for any $\delta_{h}\in\left(0,\frac{1}{5}\right)$ it holds that

$\displaystyle\frac{\tilde{p}}{\log\left(\frac{1}{\delta_{h}}\right)}\leq\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)\,,$

bounding the sample complexity by

$\displaystyle\left(\log\left(\frac{1}{\delta_{\mathcal{S}}}\right)+2\log\left(\log\left(\frac{1}{\delta_{h}}\right)\right)-\log\left(\tilde{p}\right)\right)\frac{1}{\epsilon}\,.$

∎

###  A.6 Proofs Using Nonuniform Learnability

In the next pages, we will show a result that does not use the teacher
assumption for the generalization of randomly sampled networks. The result is
more general than Theorem 3.2 and A.11, which were both tailored for the
teacher assumption. However, the price to pay for relaxing this assumption is
that the following result is slightly less tight.

Instead of the teacher assumption, we rely on the probability of
interpolation, defined as:

######  Definition A.13.

For some random hypothesis $h$ from prior $\mathcal{P}$, the interpolation
probability is defined as

$\displaystyle\hat{p}\triangleq\mathbb{P}_{h\sim\mathcal{P}}\left(\mathcal{L}_{\mathcal{S}}(h)=0\right)$

######  Theorem A.14 (Generalization of Guess & Check, restated).

Under the assumption that $\hat{p}<\frac{1}{2}$, for any
$\delta,\eta\in\left(0,1\right)$, and $N\in\mathbb{N}$, we have with
probability at least $1-\eta$ over $h\sim\mathcal{P}_{\mathcal{S}}$ that:

$\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\right)\geq
1-\delta\,,$

where

$\displaystyle\epsilon=\epsilon_{\delta,\eta}=\frac{\log\left(\frac{1}{\hat{p}}\right)+\log\left(\frac{4}{\delta}\right)+\log\left(\log\left(\frac{2}{\eta}\right)\right)+2\log\log\left(\frac{\log\left(\frac{2}{\eta}\right)}{\hat{p}}+1\right)}{N}\,.$
(21)

Theorem A.14 proof sketch: We first show that

$\mathbb{P}_{\mathcal{S}\sim\mathcal{D}^{N}}\left(\mathcal{L}_{\mathcal{S}}(h_{t})=0\textrm{
and
}\mathcal{L}_{\mathcal{D}}(h_{t})>\tilde{\epsilon}_{t}\right)\leq\delta_{t}\,,$

where we define

$\tilde{\epsilon}_{t}=\frac{\log{1/\delta_{t}}}{N}\,.$

Set $\delta_{t}=\frac{\delta}{4t\log^{2}(t+1)}$ to obtain

$\tilde{\epsilon}_{t}=\frac{\log
t+2\log\log\left(t+1\right)+\log{4/\delta}}{N}\,,$

and use a union bound, which yields, for any $\delta>0$ and any sequence
$(h_{t})_{t\in\mathbb{N}}$ of hypotheses,

$\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\exists_{t}\left(L_{S}(h_{t})=0\textrm{
and }L_{D}(h_{t})>\tilde{\epsilon}_{t}\right)\right)\leq\delta\,.$

Importantly, since this holds for any $h_{t}$ we can use our $h_{t}$ sequence
from Algorithm 1 and for $t=T$ to get with probability at least $1-\delta$
over $S\sim\mathcal{D}^{N}$ that

$\mathcal{L}_{\mathcal{D}}(\mathcal{A}_{\mathcal{P}}(\mathcal{S}))\leq\tilde{\epsilon}_{T}\,.$

Finally, we use the fact that $T\mid\mathcal{S}$ is a geometric random
variable with success parameter $\hat{p}<\frac{1}{2}$ to obtain

$\mathbb{P}_{h_{t}}\left(T>\frac{\log 2/\eta}{\hat{p}}\right)\leq\eta\,.$

Taking the complementary of the probability above, combined with the fact that
$\tilde{\epsilon}_{T}$ is a an increasing function of $T$ concludes the
theorem.

For full derivation, we proceed with some lemmas before proving Theorem A.14.

######  Lemma A.15.

For any $\delta>0$ and any sequence $(h_{t})_{t\in\mathbb{N}}$ of hypotheses:

$\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(\exists_{t}L_{S}(h_{t})=0\textrm{ and
}L_{D}(h_{t})>\tilde{\epsilon}_{t}\right)\leq\delta$

where

$\displaystyle\tilde{\epsilon}_{t}=\frac{\log
t+2\log\log\left(t+1\right)+\log{4/\delta}}{N}$ (22)

###### Proof.

Set $\delta_{t}=\frac{\delta}{4t\log^{2}(t+1)}$ and we will show that
$\sum_{t}\delta_{t}<\delta$. From the Integral test for convergence:

$\sum_{t=1}^{\infty}\frac{\delta}{4t\log^{2}(t+1)}\leq\frac{\delta}{4\log^{2}(2)}+\frac{\delta}{8\log^{2}(3)}+\int_{3}^{\infty}\frac{\delta}{4t\log^{2}(t)}\mathrm{d}t=\frac{\delta}{4}\left(\frac{1}{\log^{2}\left(2\right)}+\frac{0.5}{\log^{2}\left(3\right)}+\frac{1}{\log\left(3\right)}\right)\leq\delta\,,$

where by the change of variables
$u=\log\left(t\right),\mathrm{d}u=\frac{\mathrm{d}t}{t}$, we solved the
integral

$\int_{3}^{\infty}\frac{1}{t\log^{2}(t)}\mathrm{d}t=\int_{\log\left(3\right)}^{\infty}\frac{1}{u^{2}}\mathrm{d}u=\frac{1}{\log\left(3\right)}\,.$

For each $h_{t}$ separately,

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{S}(h_{t})=0\textrm{
and }L_{D}(h_{t})>\frac{\log{1/\delta_{t}}}{N}\right)$
$\displaystyle=\prod_{n=1}^{N}\mathbb{P}_{\mathbf{x}\sim\mathcal{D}}\left(h_{t}\left(\mathbf{x}\right)=h_{\bm{\theta}^{\star}}\left(\mathbf{x}\right)\right)$
$\displaystyle=\prod_{n=1}^{N}\left(1-\mathcal{L}_{\mathcal{D}}(h_{t})\right)$
$\displaystyle=\left(1-\mathcal{L}_{\mathcal{D}}(h_{t})\right)^{N}$
$\displaystyle\leq\left(1-\frac{1/\delta_{t}}{N}\right)^{N}$
$\displaystyle\leq\exp\left(-N\frac{1/\delta_{t}}{N}\right)$
$\displaystyle=\delta_{t}\,.$

Taking a union bound yields the lemma. ∎

######  Lemma A.16.

For any $\delta>0$, and any $h_{i}$, with probability at least $1-\delta$ over
$S\sim\mathcal{D}^{N}$,

$L_{\mathcal{D}}(h)\leq\tilde{\epsilon}_{T}\,.$

where $\tilde{\epsilon}_{t}$ is defined in (22) and T is defined in Algorithm
1.

###### Proof.

Lemma A.15 applies to any sequence of hypotheses, and since $S$ is independent
of the sequence $h_{t}$, we can also apply it to $h_{t}$. Since the Lemma
applies to all $t$, it also applies to any random $T$, even if it depends on
the sample. For the $T$ used by G&C from Algorithm 1, we always have
$L_{S}(h_{T})=0$, so we get the lemma from Lemma A.15. ∎

We now wish to explain the dependence on $T$ in Lemma A.16. We will do so by
the following Lemma:

######  Lemma A.17.

For any $\eta$, and any $S$, under the assumption that $\hat{p}<\frac{1}{2}$,
we have that $\mathbb{P}_{(h_{t})}\left(T>\frac{\log
2/\eta}{\hat{p}}\right)\leq\eta$

###### Proof.

Given $S\sim\mathcal{D}^{N}$, we observe that $T$ is geometric with parameter
$\hat{p}$. Using the cumulative distribution function of geometric random
variables, we can bound:

$\displaystyle\mathbb{P}_{(h_{t})}\left(T>\frac{\log\left(2/\eta\right)}{\hat{p}}\right)=\left(1-\hat{p}\right)^{\left\lfloor\frac{\log\left(2/\eta\right)}{\hat{p}}\right\rfloor}\leq\left(1-\hat{p}\right)^{\frac{\log\left(2/\eta\right)}{\hat{p}}-1}$

And now we use a basic property of exponents $\left(1-x\right)\leq e^{-x}$,
which can be rewritten as $\frac{-1}{\log\left(1-x\right)}\leq\frac{1}{x}$, to
further bound

$\displaystyle\mathbb{P}_{(h_{t})}\left(T>\frac{\log\left(2/\eta\right)}{\hat{p}}\right)$
$\displaystyle\leq\left(1-\hat{p}\right)^{\frac{\log\left(2/\eta\right)}{\hat{p}}-1}$
$\displaystyle\leq\left(1-\hat{p}\right)^{\frac{\log\left(\frac{\eta}{2}\right)}{\log\left(1-\hat{p}\right)}-1}$
$\displaystyle=\exp\left(\left(\frac{\log\left(\frac{\eta}{2}\right)}{\log\left(1-\hat{p}\right)}-1\right)\log\left(1-\hat{p}\right)\right)$
$\displaystyle\leq\exp\left(\frac{\log\left(\frac{\eta}{2}\right)}{\log\left(1-\hat{p}\right)}\log\left(1-\hat{p}\right)-\log\left(1-\hat{p}\right)\right)$
$\displaystyle=\exp\left(\log\left(\frac{\eta}{2}\right)-\log\left(1-\hat{p}\right)\right)$
$\displaystyle=\frac{\frac{\eta}{2}}{1-\hat{p}}\leq\eta$

∎

Having proved Lemma A.17 and Lemma A.16 we are ready to prove our main result.

###### Proof.

$[$of Theorem A.14$]$ From Lemma A.16 we have that

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\tilde{\epsilon}_{T}\right)\geq
1-\delta\,.$ (23)

We can now use Lemma A.17 to obtain with probability of at least $1-\eta$ over
the sampling of $h_{t}$ that $T\leq\frac{\log\left(2/\eta\right)}{\hat{p}}$
and therefore

$\displaystyle\tilde{\epsilon}_{T}$ $\displaystyle=\frac{\log
T+2\log\log\left(T+1\right)+\log{4/\delta}}{N}$
$\displaystyle\leq\frac{\log\left(\frac{\log\left(2/\eta\right)}{\hat{p}}\right)+2\log\log\left(\frac{\log\left(2/\eta\right)}{\hat{p}}+1\right)+\log{4/\delta}}{N}$
$\displaystyle\leq\frac{\log\left(\frac{1}{\hat{p}}\right)+\log\left(\frac{4}{\delta}\right)+\log\left(\log\left(\frac{2}{\eta}\right)\right)+2\log\log\left(\frac{\log\left(\frac{2}{\eta}\right)}{\hat{p}}+1\right)}{N}\,,$

and therefore with probability of at least $1-\eta$ we have that

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\eta,\delta}\right)\geq\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\tilde{\epsilon}_{T}\right)\,.$

Finally, from (23) we get

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\eta,\delta}\right)\geq
1-\delta\,.$

∎

######  Lemma A.18.

Let $x>1$ and $y>0$. Then

$\displaystyle\log\left(x+y\right)\leq\log\left(x\right)+\log\left(1+y\right)\,.$

###### Proof.

Let $x,y>0$.

$\displaystyle\log\left(1+x+y\right)\leq\log\left(1+x+y+xy\right)=\log\left(\left(1+x\right)\left(1+y\right)\right)=\log\left(1+x\right)+\log\left(1+y\right)\,.$

Now, suppose that $x>1$ and $y>0$.

$\displaystyle\log\left(x+y\right)$
$\displaystyle=\log\left(1+\left(x-1\right)+y\right)$
$\displaystyle\leq\log\left(1+\left(x-1\right)\right)+\log\left(1+y\right)$
$\displaystyle=\log\left(x\right)+\log\left(1+y\right)\,.$

∎

######  Proposition A.19.

For any $\delta>0$, with probability at least $1-\delta$ over
$S\sim\mathcal{D}^{m}$ and $h\sim\mathcal{P}_{\mathcal{S}}$

$\mathcal{L}_{\mathcal{D}}(h)\leq\epsilon\,,$

where

$\displaystyle\epsilon=\frac{\log\left(\frac{1}{\hat{p}}\right)+4\log\left(\frac{8}{\delta}\right)+2\log\left(\log\left(\frac{1}{\hat{p}}\right)\right)}{N}\,.$

###### Proof.

Here we take an alternative approach to the one presented in the proof of
Theorem A.14. Denote

$\displaystyle\tilde{\epsilon}_{T}=\frac{\log
T+2\log\log\left(T+1\right)+\log{4/\delta}}{N}\,.$

Now note that from the proof of Theorem A.14,

$\displaystyle
T\leq\frac{\log\left(2/\eta\right)}{\hat{p}}\Rightarrow\tilde{\epsilon_{T}}\leq\epsilon_{\eta,\delta}\,.$
(24)

We use the law of total probability to write

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\eta,\delta}\right)$
$\displaystyle=$
$\displaystyle=\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\eta,\delta}\middle|T\leq\frac{\log\left(2/\eta\right)}{\hat{p}}\right)\mathbb{P}_{h_{t}}\left(T\leq\frac{\log
2/\eta}{\hat{p}}\right)$
$\displaystyle+\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\eta,\delta}\middle|T>\frac{\log\left(2/\eta\right)}{\hat{p}}\right)\mathbb{P}_{h_{t}}\left(T>\frac{\log
2/\eta}{\hat{p}}\right)$
$\displaystyle\geq\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\eta,\delta}\middle|T\leq\frac{\log\left(2/\eta\right)}{\hat{p}}\right)\mathbb{P}_{h_{t}}\left(T\leq\frac{\log
2/\eta}{\hat{p}}\right)$ $\displaystyle[\text{ \eqref{eq: T bound under
condition}}]$
$\displaystyle\geq\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\tilde{\epsilon_{T}}\right)\mathbb{P}_{h_{t}}\left(T\leq\frac{\log
2/\eta}{\hat{p}}\right)$ $\displaystyle[\text{Lemma~{}\ref{lem: bound with T}
and Lemma~{}\ref{lem: T bound}}]$
$\displaystyle{\geq}\left(1-\delta\right)\left(1-\eta\right)$

Now we can choose $\delta,\eta\leftarrow\frac{\delta}{2}$, and we obtain

$\displaystyle\mathbb{P}_{S\sim\mathcal{D}^{N}}\left(L_{\mathcal{D}}(h)\leq\epsilon_{\frac{\delta}{2},\frac{\delta}{2}}\right)$
$\displaystyle\geq\left(1-\frac{\delta}{2}\right)\left(1-\frac{\delta}{2}\right)$
$\displaystyle=1-\delta+\frac{\delta^{2}}{4}$ $\displaystyle\geq 1-\delta\,.$

Applying Lemma A.18 multiple times we get

$\displaystyle\epsilon_{\frac{\delta}{2},\frac{\delta}{2}}$
$\displaystyle=\frac{\log\left(\frac{1}{\hat{p}}\right)+\log\left(\frac{8}{\delta}\right)+\log\left(\log\left(\frac{4}{\delta}\right)\right)+2\log\log\left(\frac{\log\left(\frac{4}{\delta}\right)}{\hat{p}}+1\right)}{N}$
$\displaystyle\leq\frac{\log\left(\frac{1}{\hat{p}}\right)+2\log\left(\frac{8}{\delta}\right)+2\log\left(\log\left(\frac{\log\left(\frac{4}{\delta}\right)+1}{\hat{p}}\right)\right)}{N}$
$\displaystyle=\frac{\log\left(\frac{1}{\hat{p}}\right)+2\log\left(\frac{8}{\delta}\right)+2\log\left(\log\left(\frac{1}{\hat{p}}\right)+\log\left(\log\left(\frac{4e}{\delta}\right)\right)\right)}{N}$
$\displaystyle\leq\frac{\log\left(\frac{1}{\hat{p}}\right)+2\log\left(\frac{8}{\delta}\right)+2\log\left(\log\left(\frac{1}{\hat{p}}\right)\right)+\log\left(\log\left(\log\left(\frac{4e}{\delta}\right)\right)+1\right)}{N}$
$\displaystyle\leq\frac{\log\left(\frac{1}{\hat{p}}\right)+4\log\left(\frac{8}{\delta}\right)+2\log\left(\log\left(\frac{1}{\hat{p}}\right)\right)}{N}$

∎

##  Appendix B Proofs for Generalization of Quantized Neural Networks (Section
5)

This section contains the proofs for the results in Section 5, focusing on
upper bounding the effective sample complexity $C$. Specifically,

  * •

In Appendix B.1 we derive the upper bound for vanilla fully connected networks
as stated in Theorem 5.3.

  * •

In Appendix B.2 we derive the upper bound for Neuron-Scaled fully-connected
networks as stated in Theorem 5.3.

  * •

In Appendix B.3 we derive the upper bound for convolutional neural networks.

  * •

In Appendix B.4 we derive the upper bound for Channel-Scaled convolutional
neural networks.

###  B.1 Vanilla Fully-Connected Neural Networks

Notation Following definition 5.1, for all $l=1,\dots,L$, write the weight
matrices and bias vectors in block form as

$\displaystyle\mathbf{W}^{\left(l\right)}=\left[\begin{array}[]{cc}\mathbf{W}_{11}^{\left(l\right)}&\mathbf{W}_{12}^{\left(l\right)}\\\
\mathbf{W}_{21}^{\left(l\right)}&\mathbf{W}_{22}^{\left(l\right)}\end{array}\right]\in\mathbb{R}^{d_{l}\times
d_{l-1}},\mathbf{b}^{\left(l\right)}=\left[\begin{array}[]{c}\mathbf{b}_{1}^{\left(l\right)}\\\
\mathbf{b}_{2}^{\left(l\right)}\end{array}\right]\in\mathbb{R}^{d_{l}},$ (29)

such that

$\displaystyle\mathbf{W}_{11}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{d_{l}^{\star}\times d_{l-1}^{\star}}\,,$
$\displaystyle\mathbf{W}_{12}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{d_{l}^{\star}\times\left(d_{l-1}-d_{l-1}^{\star}\right)}\,,$
$\displaystyle\mathbf{W}_{21}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{\left(d_{l}-d_{l}^{\star}\right)\times
d_{l-1}^{\star}}\,,$ $\displaystyle\mathbf{W}_{22}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{\left(d_{l}-d_{l}^{\star}\right)\times\left(d_{l-1}-d_{l-1}^{\star}\right)}\,,$
$\displaystyle\mathbf{b}_{1}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{d_{l}^{\star}}\,,$
$\displaystyle\mathbf{b}_{2}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{d_{l}-d_{l}^{\star}}\,.$

######  Remark B.1.

The blocks have a simple interpretation with reference to Figure 1.
$\mathbf{W}_{11}^{\left(l\right)}$ represents the blue edges, and
$\mathbf{W}_{12}^{\left(l\right)}$ represents the orange edges.
$\mathbf{W}_{21}^{\left(l\right)},\mathbf{W}_{22}^{\left(l\right)},$ both
represent gray edges. As for the biases, $\mathbf{b}_{1}^{\left(l\right)}$
corresponds to the bias terms of gray vertices, and
$\mathbf{b}_{2}^{\left(l\right)}$ corresponds to the bias terms of white
vertices.

######  Definition B.2.

Define the coordinate-projection operator
$\pi_{l}:\mathbf{\mathbb{R}}^{d_{l}}\rightarrow\mathbb{R}^{d_{l}^{\star}}$ for
$d_{l}\geq d_{l}^{\star}$ as

$\pi_{l}\left(\left(x_{1},\dots,x_{d_{l}}\right)^{\top}\right)=\left(x_{1},\dots,x_{d_{l}^{\star}}\right)^{\top}\,.$

Notice that this projection commutes with the component-wise activation
function $\sigma$. In order to keep the proofs focused, we restate and prove
each result in Theorem 5.3 separately. We first restate only the first part of
Theorem 5.3.

######  Theorem B.3.

For any activation function such that $\sigma(0)=0$, depth $L$, $Q$-quantized
teacher with widths $D^{*}$, student with widths $D>D^{*}$ and prior
$\mathcal{P}$ uniform over $Q$-quantized parametrizations, we have for Vanilla
Fully Connected Networks that:

$\displaystyle\tilde{C}\leq\hat{C}^{\mathrm{FC}}\triangleq\left(\sum_{l=1}^{L}{\left(d_{l}^{\star}d_{l-1}+d_{l}^{\star}\right)}\right)\log
Q\,.$ (30)

where we defined $d_{0}^{\star}\triangleq d_{0}$. And by Theorem 3.2,
$N=(\tilde{C}+3\log 2/\delta)/\epsilon$ samples are enough to ensure that for
posterior sampling (i.e. G&C),
$\mathcal{L}(\mathcal{A}_{\mathcal{P}}(\mathcal{S}))\leq\epsilon$ with
probability $1-\delta$ over $\mathcal{S}\sim\mathcal{D}^{N}$ and the sampling.

###### Proof.

The outline of our proof is as follows: we first show a sufficient condition
on the parameters of the student to ensure it will be TE, and then count the
number of parameter configurations for which this condition holds. This yields
a lower bound on the number of TE models, and since the hypothesis class of
quantized networks with fixed widths and depths is finite, we are able to
calculate the probability of a sampled model to be TE.

We now begin our proof. For all $l=1,\dots,L$, recall that

$\mathbf{W}^{\star\left(l\right)}\in\mathbb{R}^{d_{l}^{\star}\times
d_{l-1}^{\star}},\mathbf{b}^{\star\left(l\right)}\in\mathbb{R}^{d_{l}^{\star}}$

are the weights and biases of $h_{\bm{\theta}^{\star}}$ respectively. Define

$\mathcal{E}=\left\\{h_{\bm{\theta}}\in\mathcal{H}_{D}^{\text{FC}}\middle|\forall
l=1,\dots,L\;\mathbf{W}_{11}^{\left(l\right)}=\mathbf{W}^{\star\left(l\right)},\;\mathbf{W}_{12}^{\left(l\right)}=\mathbf{0}_{d_{l}^{\star}\times\left(d_{l-1}-d_{l-1}^{\star}\right)},\;\mathbf{b}_{1}^{\left(l\right)}=\mathbf{b}^{\star\left(l\right)}\right\\}\,.$

We claim that any $h_{\bm{\theta}}\in\mathcal{E}$ is TE. To prove this, we
show by induction over the layer $l$, that for all
$\mathbf{x}\in\mathbb{R}^{d_{0}}$,

$\displaystyle\pi_{l}\left(f_{D}^{\left(l\right)}\left(\mathbf{x}\right)\right)=f_{D^{\star}}^{\left(l\right)}\left(\mathbf{x}\right)\,.$

Let $h_{\bm{\theta}}\in\mathcal{E}$. Begin from the base case, $l=1$. Since
$d_{0}=d_{0}^{\star}$,

$\mathbf{W}^{\left(1\right)}=\left[\begin{array}[]{c}\mathbf{W}_{11}^{\left(1\right)}\\\
\mathbf{W}_{21}^{\left(1\right)}\end{array}\right]$

so using the notation from Def. 5.1 we find that

$\mathbf{W}^{\left(1\right)}f_{D}^{\left(0\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(1\right)}=\mathbf{W}^{\left(1\right)}\mathbf{x}+\mathbf{b}^{\left(1\right)}=\left[\begin{array}[]{c}\mathbf{W}_{11}^{\left(1\right)}\\\
\mathbf{W}_{21}^{\left(1\right)}\end{array}\right]\mathbf{x}+\left[\begin{array}[]{c}\mathbf{b}_{1}^{\left(1\right)}\\\
\mathbf{b}_{2}^{\left(1\right)}\end{array}\right]=\left[\begin{array}[]{c}\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\\\
\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\end{array}\right]$

and

$f_{D}^{\left(1\right)}\left(\mathbf{x}\right)=\sigma\left(\left[\begin{array}[]{c}\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\\\
\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\end{array}\right]\right)=\left[\begin{array}[]{c}\sigma\left(\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\right)\\\
\sigma\left(\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\right)\end{array}\right]\,.$

Therefore, using the definition of $\pi_{1}$, we get

$\displaystyle\pi_{1}\left(f_{D}^{\left(1\right)}\left(\mathbf{x}\right)\right)=\sigma\left(\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\right)\,.$
(31)

Since $h_{\bm{\theta}}\in\mathcal{E}$, we have that
$\mathbf{W}_{11}^{\left(1\right)}=\mathbf{W}^{\star\left(1\right)}$ and
$\mathbf{b}_{1}^{\left(1\right)}=\mathbf{b}^{\star\left(1\right)}$, so from
(31) the coordinate projection is

$\pi_{1}\left(f_{D}^{\left(1\right)}\left(\mathbf{x}\right)\right)=\sigma\left(\mathbf{W}^{\star\left(1\right)}\mathbf{x}+\mathbf{b}^{\star\left(1\right)}\right)=f_{D^{\star}}^{\left(1\right)}\left(\mathbf{x}\right).$

Next, assume that
$\pi_{l-1}\left(f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)\right)=f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)$
for some $l\leq L-1$. Since $h_{\bm{\theta}}\in\mathcal{E}$, for any
$l\in\left[L\right]$ we have that
$\mathbf{W}_{12}^{\left(l\right)}=\mathbf{0}$. Therefore, following a similar
argument we get

$\displaystyle\pi_{l}\left(\mathbf{W}^{\left(l\right)}f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(l\right)}\right)$
$\displaystyle=\pi_{l}\left(\left[\begin{array}[]{cc}\mathbf{W}_{11}^{\left(l\right)}&\mathbf{W}_{12}^{\left(l\right)}\\\
\mathbf{W}_{21}^{\left(l\right)}&\mathbf{W}_{22}^{\left(l\right)}\end{array}\right]f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\left[\begin{array}[]{c}\mathbf{b}_{1}^{\left(l\right)}\\\
\mathbf{b}_{2}^{\left(l\right)}\end{array}\right]\right)$
$\displaystyle=\left[\begin{array}[]{cc}\mathbf{W}_{11}^{\left(l\right)}&\mathbf{0}\end{array}\right]f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\begin{array}[]{c}\mathbf{b}_{1}^{\left(l\right)}\end{array}$
$\displaystyle=\left[\begin{array}[]{cc}\mathbf{W}^{\star\left(l\right)}&\mathbf{0}\end{array}\right]f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\begin{array}[]{c}\mathbf{b}^{\star\left(l\right)}\end{array}$
$\displaystyle=\mathbf{W}^{\star\left(l\right)}\pi_{l-1}\left(f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)\right)+\begin{array}[]{c}\mathbf{b}^{\star\left(l\right)}\end{array}$
$\displaystyle=\mathbf{W}^{\star\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\begin{array}[]{c}\mathbf{b}^{\star\left(l\right)}\end{array}\,,$

that is

$\displaystyle\pi_{l}\left(\mathbf{W}^{\left(l\right)}f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(l\right)}\right)=\mathbf{W}^{\star\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\begin{array}[]{c}\mathbf{b}^{\star\left(l\right)}\end{array}\,.$
(33)

Using the commutativity between $\sigma$ and $\pi_{l}$, we have

$\displaystyle\pi_{l}\left(f_{D}^{\left(l\right)}\left(\mathbf{x}\right)\right)$
$\displaystyle=\pi_{l}\left(\sigma\left(\mathbf{W}^{\left(l\right)}f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(l\right)}\right)\right)$
$\displaystyle=\sigma\left(\pi_{l}\left(\mathbf{W}^{\left(l\right)}f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(l\right)}\right)\right)$
$\displaystyle\overset{\text{\eqref{eq: projection hidden
layers}}}{=}\sigma\left(\mathbf{W}^{\star\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\star\left(l\right)}\right)$
$\displaystyle=f_{D^{\star}}^{\left(l\right)}\left(\mathbf{x}\right)\,.$

For the last layer, $l=L$, the proof is identical, except for the application
of the activation function $\sigma$ at the end, so an analogue to (33) is
enough. Since we assume that $h_{\bm{\theta}}$ and $h_{\bm{\theta}^{\star}}$
have the same output dimension $d_{L}$, this proves that for all
$\mathbf{x}\in\mathbb{R}^{d_{0}}$

$\displaystyle
h_{\bm{\theta}}\left(\mathbf{x}\right)=\pi_{L}\left(h_{\bm{\theta}}\left(\mathbf{x}\right)\right)=h_{\bm{\theta}^{\star}}\left(\mathbf{x}\right)\,.$

That is,
$\mathcal{E}\subseteq\left\\{h_{\bm{\theta}}\middle|h_{\bm{\theta}}\equiv
h_{\bm{\theta}^{\star}}\right\\}$ and therefore

$\mathbb{P}\left(\mathcal{E}\right)\leq\mathbb{P}\left(h_{\bm{\theta}}\equiv
h_{\bm{\theta}^{\star}}\right)\,.$

Finally, to calculate the probability to sample $h_{\bm{\theta}}$ in
$\mathcal{E}$ we count the number of constrained parameters - parameters which
are either determined by $h_{\bm{\theta}^{\star}}$ or are $0$ in
$\mathcal{E}$. Looking at the dimensions of
$\mathbf{W}_{11}^{\left(l\right)}$, $\mathbf{W}_{12}^{\left(l\right)}$ and
$\mathbf{b}_{1}^{\left(l\right)}$, we deduce that there are exactly

$\displaystyle\mathcal{M}=\sum_{l=1}^{L}d_{l}^{\star}\cdot
d_{l-1}+d_{l}^{\star}=\sum_{l=1}^{L}d_{l}^{\star}\left(d_{l-1}+1\right)$

such constrained parameters, and denote

$\displaystyle\hat{C}^{\mathrm{FC}}\triangleq\left(\sum_{l=1}^{L}{\left(d_{l}^{\star}d_{l-1}+d_{l}^{\star}\right)}\right)\log
Q=\mathcal{M}\log Q\,.$

Under the uniform prior over parameters $\mathcal{P}$,

$\displaystyle\tilde{p}\geq\mathbb{P}\left(\mathcal{E}\right)=Q^{-\mathcal{M}}\,,$

so

$\displaystyle\tilde{C}=-\log\left(\tilde{p}\right)\leq\mathcal{M}\log{Q}=\hat{C}^{\mathrm{FC}}$

∎

###  B.2 Neuron-Scaled Fully-Connected Neural Networks

We now wish to improve our result, introducing some assumptions on the
architecture. We first need to define a new class of architectures.

######  Definition B.4 (Scaled-neuron FC restated).

For a depth $L$, widths $D=\left(d_{1},\dots,d_{L}\right)$, and activation
function $\sigma:\mathbb{R}\rightarrow\mathbb{R}$, a scaled neuron fully
connected neural network is a mapping $\bm{\theta}\mapsto
h^{FC}_{\bm{\theta}}$ from parameters

$\displaystyle\bm{\theta}=\left(\left\\{\mathbf{W}^{\left(l\right)}\right\\}_{l=1}^{L},\left\\{\mathbf{b}^{\left(l\right)}\right\\}_{l=1}^{L},\left\\{\bm{\gamma}^{\left(l\right)}\right\\}_{l=1}^{L}\right)\,,$

where

$\displaystyle\mathbf{W}^{\left(l\right)}\in\mathbb{R}^{d_{l}\times
d_{l-1}},\mathbf{b}^{\left(l\right)}\in\mathbb{R}^{d_{l}},\bm{\gamma}^{\left(l\right)}\in\mathbb{R}^{d_{l}}\,,$

defined recursively, starting with
$f^{(0)}\left(\mathbf{x}\right)=\mathbf{x}\,,$ then

$\displaystyle\forall l\in\left[L-1\right]\;f^{(l)}\left(\mathbf{x}\right)$
$\displaystyle=\sigma\left(\bm{\gamma}^{\left(l\right)}\odot\left(\mathbf{W}^{\left(l\right)}f^{(l-1)}\left(\mathbf{x}\right)\right)+\mathbf{b}^{\left(l\right)}\right)$
$\displaystyle h_{\bm{\theta}}^{FC}\left(\mathbf{x}\right)$
$\displaystyle=\operatorname{sign}\left(\mathbf{W}^{\left(L\right)}f^{(L-1)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(L\right)}\right).$

The total parameter count is $M(D)=\sum_{l=1}^{L}d_{l}(d_{l-1}+2)$. We denote
the class of all scaled neuron fully connected neural network as
$\mathcal{H}^{\mathrm{SFC}}_{D}$.

######  Remark B.5.

We use the notation $f_{D}^{\left(l\right)}\left(\mathbf{x}\right)$ for both
$f_{\mathrm{FC}}^{\left(l\right)}$ and $f_{\mathrm{SFC}}^{\left(l\right)}$ in
a fully connected network with hidden dimensions $D$, as they can be inferred
from context.

######  Theorem B.6.

For any activation function such that $\sigma(0)=0$, depth $L$, $Q$-quantized
teacher with widths $D^{*}$, student with widths $D>D^{*}$ and prior
$\mathcal{P}$ uniform over $Q$-quantized parametrizations, we have for Scaled
Fully Connected Networks that:

$\displaystyle\tilde{C}\leq\hat{C}^{\mathrm{SFC}}\triangleq\left(\sum_{l=1}^{L}{\left(d_{l}^{\star}d_{l-1}^{\star}+2d_{l}\right)}\right)\log
Q\,,$ (34)

where we defined $d_{0}^{\star}\triangleq d_{0}$. And by Theorem 3.2,
$N=(\tilde{C}+3\log 2/\delta)/\epsilon$ samples are enough to ensure that for
posterior sampling (i.e. G&C),
$\mathcal{L}(\mathcal{A}_{\mathcal{P}}(\mathcal{S}))\leq\epsilon$ with
probability $1-\delta$ over $\mathcal{S}\sim\mathcal{D}^{N}$ and the sampling.

###### Proof.

The idea is similar to the proof of Theorem B.3, only that now we can define a
set $\mathcal{E}$ with even more elements, which will tighten our bound. For
any $l\in\left[L\right]$, write $\bm{\gamma}$ as a blocks vector

$\displaystyle\bm{\gamma}=\left[\begin{array}[]{c}\bm{\gamma}_{1}^{\left(l\right)}\\\
\bm{\gamma}_{2}^{\left(l\right)}\end{array}\right]\in\mathbb{R}^{d_{l}}\,,$

where

$\displaystyle\bm{\gamma}_{1}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{d_{l}^{\star}}\,,$
$\displaystyle\bm{\gamma}_{2}^{\left(l\right)}$
$\displaystyle\in\mathbb{R}^{d_{l}-d_{l}^{\star}}\,.$

This time, we are interested in:

$\mathcal{E}=\left\\{h_{\bm{\theta}}\in\mathcal{H}_{D}^{\text{SFC}}\middle|\forall
l=1,\dots,L\;\mathbf{W}_{11}^{\left(l\right)}=\mathbf{W}^{\star\left(l\right)},\;\mathbf{b}_{1}^{\left(l\right)}=\mathbf{b}^{\star\left(l\right)},\;\mathbf{b}_{2}^{\left(l\right)}=\mathbf{0}_{d_{l}-d_{l}^{\star}},\;\bm{\gamma}_{1}^{\left(l\right)}=\bm{\gamma}^{\star\left(l\right)},\bm{\gamma}_{2}^{\left(l\right)}=\mathbf{0}_{d_{l}-d_{l}^{\star}}\right\\}\,.$

As in the proof of Theorem B.3, we claim that any
$h_{\bm{\theta}}\in\mathcal{E}$ is TE. This time, we specifically show by
induction over the layer $l$, that for all $\mathbf{x}\in\mathbb{R}^{d_{0}}$,

$\displaystyle
f_{D}^{\left(l\right)}\left(\mathbf{x}\right)=\left[\begin{array}[]{c}f_{D^{\star}}^{\left(l\right)}\left(\mathbf{x}\right)\\\
\mathbf{0}_{d_{l}-d_{l}^{\star}}\end{array}\right]\,.$

Let $h_{\bm{\theta}}\in\mathcal{E}$. Begin from the base case, $l=1$. Since
$d_{0}=d_{0}^{\star}$,

$\mathbf{W}^{\left(1\right)}=\left[\begin{array}[]{c}\mathbf{W}_{11}^{\left(l\right)}\\\
\mathbf{W}_{21}^{\left(l\right)}\end{array}\right]$

so using the notation from Def. 5.1 we find that

$\bm{\gamma}^{\left(1\right)}\odot\mathbf{W}^{\left(1\right)}f_{D}^{\left(0\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(1\right)}=\bm{\gamma}^{\left(1\right)}\odot\mathbf{W}^{\left(1\right)}\mathbf{x}+\mathbf{b}^{\left(1\right)}=\left[\begin{array}[]{c}\bm{\gamma}^{\left(1\right)}_{1}\odot\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\\\
\bm{\gamma}^{\left(1\right)}_{2}\odot\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\end{array}\right]$

and

$f_{D}^{\left(1\right)}\left(\mathbf{x}\right)=\sigma\left(\left[\begin{array}[]{c}\bm{\gamma}^{\left(1\right)}_{1}\odot\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\\\
\bm{\gamma}^{\left(1\right)}_{2}\odot\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\end{array}\right]\right)=\left[\begin{array}[]{c}\sigma\left(\bm{\gamma}^{\left(1\right)}_{1}\odot\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\right)\\\
\sigma\left(\bm{\gamma}^{\left(1\right)}_{2}\odot\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\right)\end{array}\right]\,.$

Therefore, using the definition of $\pi_{1}$, we get

$\displaystyle\pi_{1}\left(f_{D}^{\left(1\right)}\left(\mathbf{x}\right)\right)=\sigma\left(\bm{\gamma}^{\left(1\right)}_{1}\odot\mathbf{W}_{11}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{1}^{\left(1\right)}\right)\,.$
(35)

Since $h_{\bm{\theta}}\in\mathcal{E}$, we have that
$\mathbf{W}_{11}^{\left(1\right)}=\mathbf{W}^{\star\left(1\right)}$,
$\mathbf{b}_{1}^{\left(1\right)}=\mathbf{b}^{\star\left(1\right)}$ and
$\bm{\gamma}_{1}^{\left(1\right)}=\bm{\gamma}^{\star\left(1\right)}$, so from
(35) the coordinate projection is

$\displaystyle\pi_{1}\left(f_{D}^{\left(1\right)}\left(\mathbf{x}\right)\right)=\sigma\left(\bm{\gamma}^{\star\left(1\right)}\odot\mathbf{W}^{\star\left(1\right)}\mathbf{x}+\mathbf{b}^{\star\left(1\right)}\right)=f_{D^{\star}}^{\left(1\right)}\left(\mathbf{x}\right)\,.$
(36)

In addition, since
$\bm{\gamma}_{2}^{\left(l\right)}=\mathbf{0}_{d_{l}-d_{l}^{\star}}$ and also
$\mathbf{b}_{2}^{\left(1\right)}=\mathbf{0}_{d_{l}-d_{l}^{\star}}$, as well as
$\sigma\left(0\right)=0$, we have that

$\displaystyle\sigma\left(\bm{\gamma}^{\left(1\right)}_{2}\odot\mathbf{W}_{21}^{\left(1\right)}\mathbf{x}+\mathbf{b}_{2}^{\left(1\right)}\right)=\mathbf{0}_{d_{l}-d_{l}^{\star}}\,.$
(37)

Putting 37 and 36 together we have

$\displaystyle
f_{D}^{\left(1\right)}\left(\mathbf{x}\right)=\left[\begin{array}[]{c}f_{D^{\star}}^{\left(1\right)}\left(\mathbf{x}\right)\\\
\mathbf{0}_{d_{1}-d_{1}^{\star}}\end{array}\right]\,.$

Next, assume that
$f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)=\left[\begin{array}[]{c}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)\\\
\mathbf{0}_{d_{l-1}-d^{\star}_{l-1}}\end{array}\right]$, for some $l\leq L-1$.
Following a similar argument we get

$\displaystyle f_{D}^{\left(l\right)}\left(\mathbf{x}\right)$ $\displaystyle=$
$\displaystyle=\sigma\left(\bm{\gamma}^{\left(l\right)}\odot\mathbf{W}^{\left(l\right)}f_{D}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\left(l\right)}\right)$
$\displaystyle=\sigma\left(\bm{\gamma}^{\left(l\right)}\odot\left[\begin{array}[]{cc}\mathbf{W}_{11}^{\left(l\right)}&\mathbf{W}_{12}^{\left(l\right)}\\\
\mathbf{W}_{21}^{\left(l\right)}&\mathbf{W}_{22}^{\left(l\right)}\end{array}\right]\left[\begin{array}[]{c}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)\\\
\mathbf{0}_{d_{l-1}-d^{\star}_{l-1}}\end{array}\right]+\left[\begin{array}[]{c}\mathbf{b}_{1}^{\left(l\right)}\\\
\mathbf{b}_{2}^{\left(l\right)}\end{array}\right]\right)$
$\displaystyle=\sigma\left(\bm{\gamma}^{\left(l\right)}\odot\left[\begin{array}[]{c}\mathbf{W}_{11}^{\left(l\right)}\\\
\mathbf{W}_{21}^{\left(l\right)}\end{array}\right]f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\left[\begin{array}[]{c}\mathbf{b}_{1}^{\left(l\right)}\\\
\mathbf{b}_{2}^{\left(l\right)}\end{array}\right]\right)$
$\displaystyle=\sigma\left(\left[\begin{array}[]{c}\bm{\gamma}_{1}^{\left(l\right)}\odot\mathbf{W}_{11}^{\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}_{1}^{\left(l\right)}\\\
\bm{\gamma}_{2}^{\left(l\right)}\odot\mathbf{W}_{21}^{\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}_{2}^{\left(l\right)}\end{array}\right]\right)$
$\displaystyle=\left[\begin{array}[]{c}\sigma\left(\bm{\gamma}_{1}^{\left(l\right)}\odot\mathbf{W}_{11}^{\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}_{1}^{\left(l\right)}\right)\\\
\sigma\left(\bm{\gamma}_{2}^{\left(l\right)}\odot\mathbf{W}_{21}^{\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}_{2}^{\left(l\right)}\right)\end{array}\right]$
$\displaystyle=\left[\begin{array}[]{c}\sigma\left(\bm{\gamma}^{\star\left(l\right)}\odot\mathbf{W}^{\star\left(l\right)}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)+\mathbf{b}^{\star\left(l\right)}\right)\\\
\mathbf{0}_{d_{l-1}-d^{\star}_{l-1}}\end{array}\right]$
$\displaystyle=\left[\begin{array}[]{c}f_{D^{\star}}^{\left(l-1\right)}\left(\mathbf{x}\right)\\\
\mathbf{0}_{d_{l-1}-d^{\star}_{l-1}}\end{array}\right]$
$\displaystyle=f_{D^{\star}}^{\left(l\right)}\left(\mathbf{x}\right)\,.$

For the last layer, $l=L$, the proof is identical, except for the scalar
product and the application of the activation function, which are removed.
Since we assume that $h_{\bm{\theta}}$ and $h_{\bm{\theta}^{\star}}$ have the
same output dimension $d_{L}$, this proves that for all
$\mathbf{x}\in\mathbb{R}^{d_{0}}$

$\displaystyle
h_{\bm{\theta}}\left(\mathbf{x}\right)=\pi_{L}\left(h_{\bm{\theta}}\left(\mathbf{x}\right)\right)=h_{\bm{\theta}^{\star}}\left(\mathbf{x}\right)\,.$

That is,
$\mathcal{E}\subseteq\left\\{h_{\bm{\theta}}\middle|h_{\bm{\theta}}\equiv
h_{\bm{\theta}^{\star}}\right\\}$ and therefore

$\mathbb{P}\left(\mathcal{E}\right)\leq\mathbb{P}\left(h_{\bm{\theta}}\equiv
h_{\bm{\theta}^{\star}}\right)\,.$

Finally, to calculate the probability to sample $h_{\bm{\theta}}$ in
$\mathcal{E}$ we count the number of constrained parameters - parameters which
are either determined by $h_{\bm{\theta}^{\star}}$ or are $0$ in
$\mathcal{E}$. Looking at the dimensions of
$\mathbf{W}_{11}^{\left(l\right)}$, $\mathbf{b}_{1}^{\left(l\right)}$,
$\mathbf{b}_{2}^{\left(l\right)}$ and $\bm{\gamma}^{\left(l\right)}$, we
deduce that there are exactly

$\displaystyle\mathcal{M}=\sum_{l=1}^{L}\left(d_{l}^{\star}d_{l-1}^{\star}+2d_{l}\right)$

such constrained parameters, and denote

$\displaystyle\hat{C}^{\mathrm{SFC}}\triangleq\left(\sum_{l=1}^{L}{\left(d_{l}^{\star}d_{l-1}^{\star}+2d_{l}\right)}\right)\log
Q=\mathcal{M}\log Q\,.$

As in the proof of Theorem B.3, under the uniform prior over parameters
$\mathcal{P}$,

$\displaystyle\tilde{p}\geq\mathbb{P}\left(\mathcal{E}\right)=Q^{-\mathcal{M}}\,,$

so

$\displaystyle\tilde{C}=-\log\left(\tilde{p}\right)\leq\mathcal{M}\log{Q}=\hat{C}^{\mathrm{SFC}}$

∎

###  B.3 Convolutional Neural Network

We first restate the definition of a CNN.

######  Definition B.7 (CNN restated).

For multi-channel inputs $\mathbf{x}^{j},\,\forall j\in\left[c_{0}\right]$,
depth $L$, activation function $\sigma\left(\cdot\right)$, and multi-index
channels number $D=\left(c_{1},\dots,c_{L},d_{s}\right)$,
$\mathbf{h}^{\mathrm{CNN}}_{\bm{\theta}}$ is a convolutional network (CNN)
defined recursively, starting with $\forall j\in\left[c_{0}\right]$,
$\mathbf{f}_{\mathrm{CNN}}^{\left(0\right),j}\left(\mathbf{x}\right)=\mathbf{x}^{j}$,
and then, for all $l\in\left[L\right]$ and $i\in\left[c_{l}\right]$, as

$\displaystyle\mathbf{f}_{\mathrm{CNN}}^{\left(l\right),i}\left(\mathbf{x}\right)=$
$\displaystyle\sigma\left(\sum_{j=1}^{c_{l-1}}\mathbf{K}_{i,j}^{\left(l\right)}*\mathbf{f}_{\mathrm{CNN}}^{\left(l-1\right),j}\left(\mathbf{x}\right)+b_{i}^{\left(l\right)}\right)$
(38)
$\displaystyle\mathbf{h}^{\mathrm{CNN}}_{\bm{\theta}}\left(\mathbf{x}\right)=$
$\displaystyle\operatorname{sign}\left(\mathrm{Vec}\left(\mathbf{f}_{\mathrm{CNN}}^{\left(L-1\right)}\left(\mathbf{x}\right)\right)^{\top}\mathbf{w}^{\left(L+1\right)}+b^{\left(L+1\right)}\right)\,,$

where for ease of notation the addition of the bias term in (38) is done
element-wise. The network parameters are

$\displaystyle\mathbf{\bm{\theta}}=\left(\left\\{\mathbf{K}^{\left(l\right)}\right\\}_{l=1}^{L},\left\\{\mathbf{b}^{\left(l\right)}\right\\}_{l=1}^{L},\mathbf{w}^{\left(L+1\right)},b^{\left(L+1\right)}\right)\,,$

where $\mathbf{K}_{i,j}^{\left(l\right)}\in\mathbb{R}^{k_{l}}$ are convolution
operators defined by kernels with $k_{l}$ parameters, and
$\mathbf{b}^{\left(l\right)}\in\mathbb{R}^{c_{l}}$ are bias terms.
$\mathbf{w}^{\left(L+1\right)}\in\mathbb{R}^{d_{s}}$ and
$b^{\left(L+1\right)}\in\mathbb{R}$ are the weights and bias of the
convolutional network’s last fully connected layer, where $d_{s}$ is the
dimension of
$\mathrm{Vec}\left(\mathbf{f}_{\mathrm{CNN}}^{\left(L\right)}\left(\mathbf{x}\right)\right)$.
We denote the class of all convolutional networks with multi-index widths $D$
as $\mathcal{H}^{\mathrm{CNN}}_{D}$.

######  Remark B.8.

As in the case of FCNs, we use the ambiguous $\mathbf{f}_{D}^{\left(l\right)}$
in place of $\mathbf{f}_{\mathrm{CNN}}^{\left(l\right)}$ to denote a general
convolutional layer in a convolutional neural network with channel pattern $D$
where the specific type can be inferred from context.

Motivation. In order to tackle the analysis of a convolutional neural network
at ease, we will define some new operations. We observe that our previous
arguments from Section B.1 is agnostic to the convolution itself and relies
only on parameter counting. In general, CNNs are analogous to FCNs in the
sense that with spatial dimension of $1$, a convolutional layer is equivalent
to a layer in a FCN, with each channel analogous to a neuron. Therefore, we
define:

######  Definition B.9.

For any $l\in\left[L\right]$, define

$\displaystyle\mathbf{K}^{\left(l\right)}=\begin{bmatrix}\mathbf{K}_{1,1}^{\left(l\right)}&\cdots&\mathbf{K}_{1,c_{l-1}}^{\left(l\right)}\\\
\vdots&\ddots&\vdots\\\
\mathbf{K}_{c_{l},1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l},c_{l-1}}^{\left(l\right)}\end{bmatrix}$

and

$\displaystyle\mathbf{f}_{D}^{\left(l\right)}=\begin{bmatrix}\mathbf{f}_{D}^{\left(l\right),1}\\\
\vdots\\\ \mathbf{f}_{D}^{\left(l\right),c_{l}}\end{bmatrix}\,.$

We use this notation to concisely write the multi-channel convolution
operation

$\displaystyle\left(\mathbf{K}^{\left(l\right)}*\mathbf{f}_{D}^{\left(l\right)}\right)_{i}=\sum_{j=1}^{c_{l-1}}\mathbf{K}_{ij}^{\left(l\right)}*\mathbf{f}_{D}^{\left(l-1\right),j}\,.$

Notation With these definitions, we define the extension to the block notation
from (29):

$\displaystyle\mathbf{K}^{\left(l\right),\left(11\right)}=\begin{bmatrix}\mathbf{K}_{1,1}^{\left(l\right)}&\cdots&\mathbf{K}_{1,c_{l-1}^{\star}}^{\left(l\right)}\\\
\vdots&\ddots&\vdots\\\
\mathbf{K}_{c_{l}^{\star},1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l}^{\star},c_{l-1}^{\star}}^{\left(l\right)}\end{bmatrix}\;,\mathbf{K}^{\left(l\right),\left(12\right)}=\begin{bmatrix}\mathbf{K}_{1,c_{l-1}^{\star}+1}^{\left(l\right)}&\cdots&\mathbf{K}_{1,c_{l-1}}^{\left(l\right)}\\\
\vdots&\ddots&\vdots\\\
\mathbf{K}_{c_{l}^{\star},c_{l-1}^{\star}+1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l}^{\star},c_{l-1}}^{\left(l\right)}\end{bmatrix}\;,$

$\displaystyle\mathbf{K}^{\left(l\right),\left(21\right)}=\begin{bmatrix}\mathbf{K}_{c_{l}^{\star}+1,1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l}^{\star}+1,c_{l-1}^{\star}}^{\left(l\right)}\\\
\vdots&\ddots&\vdots\\\
\mathbf{K}_{c_{l},1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l},c_{l-1}^{\star}}^{\left(l\right)}\end{bmatrix}\;,\mathbf{K}^{\left(l\right),\left(22\right)}=\begin{bmatrix}\mathbf{K}_{c_{l}^{\star}+1,c_{l-1}^{\star}+1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l}^{\star}+1,c_{l-1}}^{\left(l\right)}\\\
\vdots&\ddots&\vdots\\\
\mathbf{K}_{c_{l},c_{l-1}^{\star}+1}^{\left(l\right)}&\cdots&\mathbf{K}_{c_{l},c_{l-1}}^{\left(l\right)}\end{bmatrix}\;,$

so

$\displaystyle\mathbf{K}^{\left(l\right)}=\begin{bmatrix}\mathbf{K}^{\left(l\right),\left(11\right)}&\mathbf{K}^{\left(l\right),\left(12\right)}\\\
\mathbf{K}^{\left(l\right),\left(21\right)}&\mathbf{K}^{\left(l\right),\left(22\right)}\end{bmatrix}\,.$

Additionally, with

$\displaystyle\mathbf{f}_{D,1}^{\left(l\right)}=\begin{bmatrix}\mathbf{f}_{D}^{\left(l\right),1}\\\
\vdots\\\
\mathbf{f}_{D}^{\left(l\right),c_{l}^{\star}}\end{bmatrix},\;\mathbf{f}_{D,2}^{\left(l\right)}=\begin{bmatrix}\mathbf{f}_{D}^{\left(l\right),c_{l}^{\star}+1}\\\
\vdots\\\ \mathbf{f}_{D}^{\left(l\right),c_{l}}\end{bmatrix},$

and Def. B.9 we can write the multi-channel convolution in block form as

$\displaystyle\mathbf{K}^{\left(l\right)}\mathbf{f}_{D}^{\left(l\right)}$
$\displaystyle=\begin{bmatrix}\mathbf{K}^{\left(l\right),\left(11\right)}&\mathbf{K}^{\left(l\right),\left(12\right)}\\\
\mathbf{K}^{\left(l\right),\left(21\right)}&\mathbf{K}^{\left(l\right),\left(22\right)}\end{bmatrix}*\begin{bmatrix}\mathbf{f}_{D,1}^{\left(l\right)}\\\
\mathbf{f}_{D,2}^{\left(l\right)}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mathbf{K}^{\left(l\right),\left(11\right)}*\mathbf{f}_{D,1}^{\left(l\right)}+\mathbf{K}^{\left(l\right),\left(12\right)}*\mathbf{f}_{D,2}^{\left(l\right)}\\\
\mathbf{K}^{\left(l\right),\left(21\right)}*\mathbf{f}_{D,1}^{\left(l\right)}+\mathbf{K}^{\left(l\right),\left(22\right)}*\mathbf{f}_{D,2}^{\left(l\right)}\end{bmatrix}\,.$

Specifically, we can represent a convolutional layer, as defined in Def. B.7
by

$\displaystyle\mathbf{f}_{D}^{\left(l\right)}\left(\mathbf{x}\right)=\sigma\left(\mathbf{K}^{\left(l\right)}*\mathbf{f}_{D}^{\left(l-1\right)}+\mathbf{b}^{\left(l\right)}\right)\,.$
(39)

Finally, we denote

$\displaystyle\mathbf{w}^{\left(L+1\right)}=\begin{bmatrix}\mathbf{w}^{\left(L+1\right),1}\\\
\mathbf{w}^{\left(L+1\right),2}\end{bmatrix}$

where $\mathbf{w}^{\left(L+1\right),1}\in\mathcal{Q}^{d_{s}^{\star}}$ and
$\mathbf{w}^{\left(L+1\right),2}\in\mathcal{Q}^{d_{s}-d_{s}^{\star}}$.

######  Theorem B.10 (Teacher equivalence probability for CNN restated).

For any activation function and any depth $L$, let
$D^{\star}=\left(c_{1}^{\star},\dots,c_{L}^{\star},d_{s}^{\star}\right),\;D=\left(c_{1},\dots,c_{L},d_{s}\right)\in\mathbb{N}^{L+1}$
such that $D^{\star}\leq D$. If there exists some teacher
$h_{\bm{\theta}^{\star}}\in\mathcal{H}^{\mathrm{CNN}}_{D^{\star}}$ and the
prior is $\mathcal{P}=\mathcal{P}\left(\mathcal{H}^{\mathrm{CNN}}_{D}\right)$
then

$\displaystyle\tilde{C}\leq\hat{C}^{\mathrm{CNN}}\triangleq\left(d_{s}+1+\sum_{l=1}^{L}k_{l}c_{l}^{\star}c_{l-1}+c_{l}^{\star}\right)\log\left(Q\right)$

And by Theorem 3.2, $N=(\tilde{C}+3\log 2/\delta)/\epsilon$ samples are enough
to ensure that for posterior sampling (i.e. G&C),
$\mathcal{L}(\mathcal{A}_{\mathcal{P}}(\mathcal{S}))\leq\epsilon$ with
probability $1-\delta$ over $\mathcal{S}\sim\mathcal{D}^{N}$ and the sampling.

###### Proof.

We follow the same strategy as in the proof of Theorem B.3. We define a
sufficient condition on the parameters of the student network to ensure
teacher equivalence, and then find the probability that this condition holds.
Recall that for all $l\in\left[L\right]$, $\mathbf{K}^{\star\left(l\right)}$
and $\mathbf{b}^{\star\left(l\right)}$, where
$\mathbf{K}_{i,j}^{\star\left(l\right)}\in\mathbb{R}^{k_{l}}$ is a convolution
kernel with $k_{l}$ parameters, and
$\mathbf{b}^{\star\left(l\right)}\in\mathbb{R}^{c_{l}}$, are the teacher’s
$l^{\text{th}}$ layer’s convolution kernels and bias terms, respectively.
Using the notation introduced in Def. B.9, the teacher’s convolution kernels
can be arranged as

$\displaystyle\mathbf{K}^{\star\left(l\right)}=\begin{bmatrix}\mathbf{K}_{1,1}^{\star\left(l\right)}&\cdots&\mathbf{K}_{1,c_{l-1}^{\star}}^{\star\left(l\right)}\\\
\vdots&\ddots&\vdots\\\
\mathbf{K}_{c_{l}^{\star},1}^{\star\left(l\right)}&\cdots&\mathbf{K}_{c_{l}^{\star},c_{l-1}^{\star}}^{\star\left(l\right)}\end{bmatrix}\,.$

Define

$\mathcal{E}=\left\\{h_{\bm{\theta}}\in\mathcal{H}_{D}^{\text{CNN}}\middle|\begin{array}[]{l}\forall
l=1,\dots,L\;\mathbf{K}^{\left(l\right),\left(11\right)}=\mathbf{K}^{\star\left(l\right)},\;\mathbf{K}^{\left(l\right),\left(12\right)}=\mathbf{0},\;\mathbf{b}_{1}^{\left(l\right)}=\mathbf{b}^{\star\left(l\right)},\\\
\mathbf{w}^{\left(L+1\right),1}=\mathbf{w}^{\star\left(L+1\right)},\;\mathbf{w}^{\left(L+1\right),2}=\mathbf{0}_{d_{s}-d_{s}^{\star}},\;b^{\left(L+1\right)}=b^{\star\left(L+1\right)}\end{array}\right\\}\,.$

We claim that any $h_{\bm{\theta}}\in\mathcal{E}$ is TE and can show this by
induction over the layer $l$. With block notation, it is easy to see that this
is identical to the proof of Theorem B.3 when substituting
$\mathbf{W}^{\left(l\right)}$ with $\mathbf{K}^{\left(l\right)}$,
$f_{\mathrm{FC}}^{\left(l\right)}$ with
$\mathbf{f}_{\mathrm{CNN}}^{\left(l\right)}$, and standard matrix
multiplication with convolution. Finally, we turn to finding
$\mathbb{P}\left(\mathcal{E}\right)$. For a CNN
$\mathbf{h}^{\mathrm{CNN}}_{\bm{\theta}}\in\mathcal{E}$, there are
$c_{l}^{\star}\cdot c_{l-1}^{\star}$ convolution kernels set to equal the
teacher’s, $c_{l}^{\star}\cdot\left(c_{l-1}-c_{l-1}^{\star}\right)$ kernels
set to $0$, and $c_{l}^{\star}$ bias terms. Each convolution kernel
$\mathbf{K}_{i,j}^{\left(l\right)}$ is defined by $k_{l}$ parameters. From the
linear layer, we need to account for $d_{s}$ weight parameters and one bias
term. In total,

$\displaystyle\tilde{p}\geq\mathbb{P}\left(\mathcal{E}\right)=\frac{1}{Q^{\mathcal{M}}}$

where

$\displaystyle\mathcal{M}=\sum_{l=1}^{L}c_{l}^{\star}\cdot c_{l-1}\cdot
k_{l}+c_{l}^{\star}+d_{s}+1=d_{s}+1+\sum_{l=1}^{L}c_{l}^{\star}\cdot\left(c_{l-1}\cdot
k_{l}+1\right)\,.$

so

$\displaystyle\tilde{C}=-\log\left(\tilde{p}\right)\leq\mathcal{M}\log{Q}=\hat{C}^{\mathrm{CNN}}$

∎

###  B.4 Channel-Scaled Convolutional Neural Networks

Analogous to the FCN case, we present an additional CNN architecture. For
simplicity, we state the definition of the architecture using the previously
defined notation from B.9 and (39).

######  Definition B.11 (Channel Scaled CNN).

For multi-channel inputs $\mathbf{x}^{j},\,\forall j\in\left[c_{0}\right]$,
depth $L$, activation function $\sigma\left(\cdot\right)$, and multi-index
channels number $D=\left(c_{1},\dots,c_{L},d_{s}\right)$,
$\mathbf{h}^{\mathrm{SCN}}_{\bm{\theta}}$ is a channel scaled convolutional
neural network, or _scaled convolutional network_ (SCN) for short, defined
recursively, starting with
$\mathbf{f}_{\mathrm{SCN}}^{\left(0\right)}\left(\mathbf{x}\right)=\mathbf{x}$,
and then, for all $l\in\left[L\right]$, as

$\displaystyle\mathbf{f}_{\mathrm{SCN}}^{\left(l\right)}\left(\mathbf{x}\right)=$
$\displaystyle\left(\bm{\gamma}^{\left(l\right)}\odot\sigma\mathbf{K}^{\left(l\right)}*\mathbf{f}_{\mathrm{SCN}}^{\left(l-1\right)}+\mathbf{b}^{\left(l\right)}\right)$
(40)
$\displaystyle\mathbf{h}^{\mathrm{SCN}}_{\bm{\theta}}\left(\mathbf{x}\right)=$
$\displaystyle\operatorname{sign}\left(\mathrm{Vec}\left(\mathbf{f}_{\mathrm{SCN}}^{\left(L\right)}\left(\mathbf{x}\right)\right)^{\top}\mathbf{w}^{\left(L+1\right)}+b^{\left(L+1\right)}\right)\,,$

where for ease of notation the addition of the bias term in (40) is done