On the Implicit Biases of Architecture & Gradient Descent
Authors: Jeremy Bernstein
Yisong Yue
Venue: ICLR 2022 Submitted (2022)
Keywords: generalisation
function space
PAC-Bayes
NNGP
orthants
margin

Abstract: Do neural networks generalise because of bias in the functions returned by gradient descent, or bias already present in the network architecture? $\textit{¿Por qué no los dos?}$ This paper finds that while typical networks that fit the training data already generalise fairly well, gradient descent can further improve generalisation by selecting networks with a large margin. This conclusion is based on a careful study of the behaviour of infinite width networks trained by Bayesian inference and finite width networks trained by gradient descent. To measure the implicit bias of architecture, new technical tools are developed to both $\textit{analytically bound}$ and $\textit{consistently estimate}$ the average test error of the neural network--Gaussian process (NNGP) posterior. This error is found to be already better than chance, corroborating the findings of Valle-Pérez et al. (2019) and underscoring the importance of architecture. Going beyond this result, this paper finds that test performance can be substantially improved by selecting a function with much larger margin than is typical under the NNGP posterior. This highlights a curious fact: $\textit{minimum a posteriori}$ functions can generalise best, and gradient descent can select for those functions. In summary, new technical tools suggest a nuanced portrait of generalisation involving both the implicit biases of architecture and gradient descent.

Under review as a conference paper at ICLR 2022
ON THE IMPLICIT BIASES OF ARCHITECTURE & GRADIENT DESCENT
A Anonymous authors Paper under double-blind review
ABSTRACT
Do neural networks generalise because of bias in the functions returned by gradient descent, or bias already present in the network architecture?
iPor qué no los dos?
This paper finds that while typical networks that fit the training data already gener- alise fairly well, gradient descent can further improve generalisation by selecting networks with large margin. This conclusion is based a careful study of the behaviour of infinite width networks trained by Bayesian inference and finite width networks trained by gradient descent. To measure the implicit bias of architecture, new technical tools are developed to both analytically bound and consistently estimate the average test error of the neural network Gaussian process (NNGP) posterior. This error is found to be already better than chance, corroborating the findings of Valle-Pérez et al. (2019) and underscoring the importance of archi- tecture. Going beyond this result, this paper finds that test performance substantially improved by selecting a function with much larger margin than is typi- cal under the NNGP posterior. This highlights curious fact: minimum posteriori functions can generalise best, and gradient descent can select for those functions. summary, new technical tools suggest nuanced portrait of generalisation involving both the implicit biases of architecture and gradient descent.
be
INTRODUCTION
Following an influential paper by ZZhng et al. (2017). the basic question of why neural networks generalise is generally regarded to be open. The authors demonstrate surprising fact: deep learning generalises even when the neural network expressive enough to represent functions that do not generalise. In turn, this implies that the theory of Vapnik & Chervonenkis (1971) based uniform convergence of train error to population error- dror--des not explain generalisation in neural networks.
Several hypotheses have since been proposed to fill this theoretical vacuum. One prominent hypothesis states that, while most neural network solutions do not generalise well, there is an implicit bias in the kinds of functions returned by gradient descent (Soudry al.. 2018). In sharp contrast, a second hypothesis states that the solution space of a neural network is dominated by simple functions, while the complex kinds of functions that overfit are relatively rare (Valle-Pérez et al. 2019).
This latter hypothesis dovetails with a particular "PAC-Bayesian" theorem of McAllester 1998). which bounds the average population error of all classifiers consistent with training sample. If this bound is small, then the complex functions that overfit must indeed be rare. In more technical terms, the PAC-Bayesian theorem can provide a meaningful certificate of generalisation even for machine learning models with an infinite Chnnk--Chervonenkis dimension, or an arbitrarily large number of parameters, by properly accounting for the measure of those very complex functions.
This paper takes more nuanced position between these two hypotheses. While the average pop- ulation error of all neural networks that fit a training sample found to be good (and certifiably good by the PAC-Bayesian theorem), it is still possible for certain networks with special properties to perform substantially better than average (and likewise substantially better than the PAC-Bayes bound). Moreover, gradient descent may be used to specifically target these special networks. This subtly counters a position put forward by Mingard et al. (202T). which suggests that gradient descent may be well-modelled sampling randomly from a particular Bayesian posterior distribution.

---

Under review as a conference paper at ICLR 2022
To support these claims, careful study of the behaviour of both infinite width and finite width neural networks is conducted. In particular, this paper makes the following technical contributions:
Section 3
Implicit Bias of Architecture A purely analytical PAC-Bayes bound (Theorem on the population error of the neural network Gaussiann process (NNGP) posterior for binary classification is derived. The bound furnishes an interpretable measure of model complexity that depends on both the architecture and the training data. This exact analytical bound improves upon approximate computational approach due to Valle-Pérez et al. (2019).
Section
Testing the Bound The new bound is found to be both non-vacuous and correlated with the test error of finite width multilayer perceptrons trained by gradient descent. This provides supporting evidence for the important role of architecture in generalisation, as put forward by Valle-Pérez et al. (2019). Still, a gap exists with the performance of gradient descent.
Section 5
Implicit Bias of Gradient Descent Going further beyond the work of Valle-Pérez et al. (211)) a new theoretical tool (Theorem 3 is developed to enable consistent estimation of the average error of the NNGP posterior on given holdout set. The average is found to be significantly worse than the holdout performance of Gaussian process draws with large margin. The experiment is repeated for finite width neural networks trained by gradient descent, and the same qualitative phenomenon persists. This finding demonstrates the ability of gradient descent select large margin functions with vanishing posterior probability that nonetheless generalise significantly better than the posterior average.
2 RELATED WORK
Margin-based generalisation theory A rich body of work explores the connection between margin and generalisation. For instance, Bartlett et al. (2017) propose a margin-based complexity measure for neural networks derived via Rademacher complexity analysis, and Neyshabur al. (2018) derive a similar result via PAC-Bayes analysis. Neyshabur et al. (2019) test these bounds experimentally, finding them to be vacuous and to scale poorly with network width. Biigss & Guedj (202T) further develop this style of bound. Margin-based PAC-Bayes bounds go back at least to the work of Herbrich (200T), who derived such a bound for linear classification. The standard idea that a solution with large margin implies the existence of nearby solutions with the same training error (but perhaps smaller margin), facilitating a more spread out PAC-Bayes posterior. This style of margin- PAC-Bayes bound does not provide guidance on whether the original large margin classifier should generalise better or worse than the additional nearby classifiers included in the posterior.
Non-vacuous bounds for neural networks Aside from PAC-Bayes, many styles of generalisation bound for neural networks are vacuous (Dziugaite & Roy 2017). Even many PAC-Bayes bounds are vacuous (Ahille & Soatto 2018 Foret et al. 2021) due to their choice of PAC-Bayes prior.
Dziugaite & Roy (2017) construct a non-vacuous weight space PAC-Bayes bound by iteratively optimising both the PAC-Bayes prior and posterior by gradient descent. Wu et al. (2020) extend this approach to involve Hessians. Meanwhile, Valle-Pérez et al. (2019) instantiate a non-vacuous PAC-Bayes bound in the function space of neural networks via the NNGP correspondence (Neal)
1994
Lee et al. 2018). The evaluation of this bound involves an iterative and statistically inconsistent expectation-propaaation approximation. Unlike this paper's purely analytical bound in Theorem 2 these non-vacuous bounds are all evaluated by iterative computational procedures.
Implicit bias of gradient descent Much research has gone into the role that gradient descent plays in neural network generalisation. For instance, instance,/Zhang et al. (2017) suggest that gradient descent may converge to solutions with special generalisation properties, while Wilson et al. (2017) suggest that gradient descent may have a more favourable implicit bias than the Adam opumiier. Azizan et al. (202T) make a related study in the context of mirror descent. Keskar et al. (2017) point to an implicit bias present in mini-batch stochastic gradient descent, but (eeipigg et al. (2021) argue against the importance of stochasticity. Meanwhile, Saanwwiie,SSudrryy et al. (2018) observe how gradient descent combined
with certain loss functions converges to max- marxin solutions; Wei et al. (0188) make similar
observation. On a different tack. Mingard et al. (2021). Valle-Pérez & Louis (2020) and Valle-Pérez eet al.] (219)) argue that the implicit bias of neural architecture is more important than that of gradient descent for understanding generalisation, and so long as gradient descent does not select solutions pathologically, generalisation should occur.
2

---

Under review as a conference paper at ICLR 2022
f(x(2);-)
weight space ! volume P[[)
solution space Vs volume P[[ss]
f(xl1):))
solution space Vs volume P[(ss
function space Fs volume IP[Fs] =
Figure I: The solution space Vs of learning task denotes the subset of classifiers that attain zero error dataset S. While the solution space have complicated geometry when described in weight space, in function space the solution space of binary classification task is just an orthant.
3 IMPLICIT BIAS OF ARCHITECTURE
This section derives an analytical bound on the population error of an infinitely wide neural network averaged over all weight configurations that attain 0% train error-in other words, the average population error of the NNGP posterior. Since this quantity assesses the performance of all solutions rather than just those returned by gradient descent, it is intended to measure the implicit bias of architecture. In Section 4 the bound is found to be non-vacuous for multilayer perceptrons. The source of a substantial gap with the results of gradient descent training is investigated in Section 5 and ultimately attributed to an additional implicit bias of gradient descent: namely margin.
3.1 PRELIMINARY NOTATION
The inputs 2 do are embedded in Euclidean do-space, while to simplify the analysis the paper shall restrict binary labels (8) [=1]. classifier shall depend on weight vector w Ω2 where f denotes the weight space. In particular, for an input the prediction is given by sign (x;
Consider a training dataset S of n input- pairs: (()()) (oc""),("))
One is interested the relationship between the truin error Es of classifier on dataset S to the population error on a data distribution D.. For a weight vector w E Ω these are defined as:
10
ES(W)
Σ sign fx w) y0
(D(W) = (a.g)~> [sign f(; w) + v]
(1)
The solution space Vs = {w E Ω [<ss(w) = 0} denotes those classifiers that attain zero train error.
3.2 GEOMETRY OF SOLUTIONS IN FUNCTION SPACE
The function space Fs is defined be the set of outputs that the classifier f can realise on dataset S:
Fs = (= w).... (w) f(x(n), w)) w E 2 C RR.
(2)
In weight space the geometry of solutions can be arbitrarily complicated, but in function space the solutions occupy the single orthant picked out by the binary training labels.
To measure the volume of the solution space, one can define measure P weight space. It convenient to enforce P [ = so that IP is a probability measure. In the absence of a better alternative, P is usually set to a multivariate Gaussian uniform distribution. The measure P on weight space induces a measure P on function space via the relation:
w) PF C Fsl Fs]:= =P Ω (0 (f) ...
(n) w)) f(.
F].
The volume of solutions is denoted P[V3], and can be computed either in weight or function space. In function space, P(V3] is an orthant probability. The situation is visualised in Figure

---

Under review as a conference paper at ICLR 2022
3.3 PAC-BAYES THEORY
PAC-Bayes relates the volume of solutions to their average population error. The following result was derived by Valle-Pérez al. (2019) corollary of theorem due to Langford & Seeger (0001).
The result is similar in form to a theorem of McAllester (1998).
Theorem (A PAC- PAC-BByyssian theorem). First, fix probability measure P over the weight space Ω of classifier. Let S denote a training set of n datapoints sampled iid from the data distribution D and let Vs denote the corresponding solution space. Consider the population error 0 S &p (w) < 1
of weight setting w Ω and its average over the solution space eD(Vs = Ew- w Vsl. Then, for proportion ô of draws of the training set S.
1
In
P[Va
In
ED S In
(4)
1 (Ds)
For large n, the In 2n/ó term is negligible and the result says that the population error averaged over solutions is less than the ratio of the negative log volume of solutions to the number of training points.
3.4 VOLUME OF SOLUTIONS VIA GAUSSIAN ORTHANT PROBABILITIES
Since infinitely wide neural networks induce Gaussian measure on function space, computing the volume of the solution space P P[Vs] amounts to computing a Gaussian orthant probability.
In more detail, let I' denote measure on the weight space Ω of infinitely wide neural network satisfying the conditions of the NNGP correspondence- see Theorem 4 in Appendix AA.3 for an example. Then for weight vector w P, the network outputs a training set S are distributed:
; w). fa w) ~ (0,
(5)
with covariance Eig == Bwwwe//w(se (x; w)) ;xx1);; w)].
Therefore, under the NNGP correspondence, the volume of solutions computed in function space is just the Gaussian probability of the orthant picked out by the binary training labels:
P[Vs] Po (siign Φ =y(",, ...., sign Prn =y(").
(6)
To facilitate estimating and bounding this probability, this paper has derived the following lemma. Lemma 1 (Gaussian orthant probability). For covariance matrix E RR"x and binary vector E {+1)", ,, let denote the corresponding Gaussian orthani probability:
p IP (o, (sign((p) = y].
(7)
Letting denote the n X n identity matrix, @ the elementwise product and value, then p may be equivalently expressed as:
|-| the elementwise absolute
1 p 2n Eu-Nion [o- {vvo uI)T Vd EE +))) =: -Co(E.))
(8)
and p may be bounded as follows:
p 2 0
VdetDl11 u(
2n o Cx.,))
2
The proof given in Appendix orthant probabilities, and Inequality defined for later use.
A.2 Equation g yields an unbiased Monte Carlo estimator of Gaussian 9 yields lower bound. The complexity measures Co and C1 are
To gain intuition about the lemma, observe that 1/2" is the orthant probability for isotropic Gaussian. Depending on the degree of anisotropy V'dtEE- matrix Σ, Equation & captures how the orthant probability may either be exponentially amplified or suppressed compared to 1/2".
inherent in the covariance
As an aside, using Inequality 9 to lower bound Equation 6 has a Bayesian interpretation. Since the volume of solutions may be written [P[Vs]] = So dl dP(w) I[w Vs), may be interpreted as the Bayesian evidence for the network architecture under the likelihood function I[w E Vs). A Bayesian would then refer to Inequality as an evidence lower bound.
The following generalisation bound is basic consequence of Theorem
1 Equation 6 and Lemma
4

---

Under review as a conference paper at ICLR 2022
Theorem 2 (Upper bound on the average population error of an infinitely wide neural network), First, fix a probability measure P over the weight space St of an infinitely wide neural network. Let S denote training set of datapoints sampled iid from the data distribution D, let y E { denote the binary vector of training labels, and let Vs denote the corresponding solution space. Consider the population error 0 S ED <D(w) I 1 of weight setting w E S2 and its average over the solution space EDs)s == Eu- [w] w E Vs]. Let ) denote the NNGP covariance matrix (Equation 5). Then, for a proportion 1-6 of draws of the training set S,
Co(2. y) + In 2n
C1
y) + In 2n
<VsVs S 1 - --e
eV()s S
(10)
n1
where the complexity measures Co and Ci are defined in Lemmal
Since the complexity measure Cj an analytical function of the NNGP covariance matrix Σ and the binary vector of training labels y. Theorem 2 is an analytical generalisation bound for the NNGP posterior. For large n, the result simplifies to: (Vs)) & Co v)/n S 1/5 + C, ((Ey))/r y)/n. So the bound depends on the ratio of complexity measures Co and C1 to the number of datapoints
To gain further intuition about Theorem 2 consider two special cases. First, suppose that the neural architecture induces no correlation between any pair of distinct data points, such that Σ = T. Then (Vs)s) & Co /)/n = In2 R3 0.7 and the bound is worse than chance. This corresponds to pure memorisation of the training labels. Next, suppose that the neural architecture induces strong intra-class correlations and strong inter-class anti-correlations, such that Di = YsUly Although this Σ is singular, it may be seen directly that P[Vs] 1/2. Then by Theorem (Vs)) & is much better than chance for large n. This corresponds to pure generalisation from the training labels. Interpolating between these two extremes would suggest that good neural architecture would impose a prior on functions with strong intra-class and weak inter-class correlations.
In 2/2 which
4 TESTING THE BOUND
This section compares the generalisation bound for infinite width networks (Theorem 2 to the performance of finite width multilayer perceptrons (MLPs) trained by gradient descent. The bound is found to be non-vacuous and correlated with the effects of varying depth and dataset complexity. Still, there is substantial gap between the bound and gradient descent, which is investigated in Section 5
Three modified versions of the MNIST handwritten digit dataset (LeCun et al.. 1998) of varying "hardness" were used in the experiments, as detailed in Figure (top (top left). MLPs were trained with L layers and W hidden units per layer. Specifically, each 28px x 28px input image x was flattened to lie in R. 781, and normalised to satisfy || = v784. The networks consisted of an input layer in I 784x W (T. - 2) layers in IR W xW and an output layer in RWx1 The nonlinearity &o was set to p(2) :- 12 max(0, z). For this architecture, the width W - oc kernel is the compositional arccosine kernel described in Theorem | in Appendix A.3 For the finite width networks, the training loss was set to square loss using the binary training labels as regression targets, and the networks were trained for 100 epochs using the Nero optimiser (Liu et al. 202T) with an initial learning rate of 0.01 decayed by factor of 0.9 every epoch, and mini-batch size of min(50 training set size) data points. The final train error was 0% in all reported experiments. All bounds were computed with a failure probability of 0.01, and Co was estimated using 10 Monte-Carlo samples. All experiments were run on one NVIDIA Titan RTX GPU.
The
The generalisation bound of Theorem 2 was first compared across three datasets of varying complexity. The network architecture was set to a depth L = 7 MLP, and the bound was computed via Monte- Carlo estimation of Co. The results are shown in Figure 2 (top right). The bound was found reflect the relative hardness of the datasets. For random labels, the bound was vacuous as desired. Next, the generalisation bound was compared against the empirical performance of a depth I, = 7 MLP trained on the decimal digits dataset. The results are shown in Figure (bottom left). While loose compared to the holdout error of the finite width network, the bound is still non-vacuous. Finally, the effect of varying network depth was investigated on the decimal digits dataset. Two depths were compared: L = 2 and L = 7. The results are shown in Figure 2 (bottom right). The bounds (computed via Monte-Carlo estimation of Co) appear to predict the relative holdout performance of the two architectures at finite width. These results corroborate those of Valle-Péé & Louis (2020) but without the use of the statistically inconsistent ippectation-propggatiin approximation.
5

---

Under review as a conference paper at ICLR 2022
Varying the dataset complexity
0.6
MNIST Variant
Inputs
Labels
0.4
Error
random labels
{0, 1, ..... 9)
coin flip
Random labels
decimal digits
(0.1..... ........ 9}
parity
Chance
binary digits
(0.1)
parity
Decimal digits
Binary digits
0.0
100
200
300
400
500
Number of training examples
Comparing to gradient descent
Varying the number layers
0.6
0.4
0.4
Error
Chance
Error
Chance L=2, We bound
W- bound estimatar
L-2, W- 5000
0.2
W=5000
0.2
L=7, W- bound
1-00000
L-7, W- 5000
0.0
0.0
100
200
300
400
500
100
200
300
400
500
Number of training examples
Number of training examples
Figure 2: Testing Theorem 2 the bound on the average population error of the NNGP posterior. The bound is found be non-vacuous and correlated with the effects of varying network depth and dataset complexity. For all curves, the mean and range are plotted over three global random seeds. A substantial gap is visible between the bound and the results of gradient descent training, which is investigated in Section 5
Top left: The three datasets used in the experiments, listed in order of hardness. For random labels there is no meaningful relationship between image and label, so generalisation is impossible. Binary digits is easier than decimal digits because each class is less diverse.
Top right: Comparing generalisation bounds from Theorem 2 for datasets of varying hardness. The curves are computed by Monte-Carre estimation of C. for an infinite width depth 7 MLP. The ordering of the bounds reflects the dataset hardness. For random labels the bound is rightfully vacuous.
Bottom left: Comparing generalisation bounds from Theorem 2 to the results of training finite width (W = 5000 and W = 10000) networks by gradient descent. The bounds are computed by both Monte- Carlo estimation of Co (referred to W Do estimator) and exact computation of C₁ (referred to as W = oc bound). The comparison is made for depth 7 MLPs on the decimal digits dataset. The exact bound computed via C₁ is looser than the Co bound computed via Monte-Carke estimation but only slightly, and both are non-vacuous above 150 datapoints. While the bounds follow the same trend as the results of training finite width networks, substantial gap is visible.
Bottom right: Comparing generalisation bounds from Theorem to the results of training finite width networks by gradient descent on decimal digits, for networks of varying depth. The bounds are computed by exact computation of C. The ordering the bounds matches the finite width results, but again a substantial gap is visible between the bounds and the results of gradient descent training.

---

Under review as a conference paper at ICLR 2022
5 IMPLICIT BIAS OF GRADIENT DESCENT
In Section 3 bound was derived on the average population error of all infinitely wide neural networks that fit a certain training set. Since the bounded quantity measures the performance of all solutions rather than just those returned by gradient descent, it is intended to assess the implicit bias of architecture. Section 4 this bound was tested and found to non-vacuous. Still a substantial gap found between the bound and the performance of finite width networks trained by gradient descent. This gap could arise for several potential reasons:
slackness in the bounding technique; ii) a difference between infinite width and finite width neural networks;
iii) an additional implicit bias of gradient descent.
This section tests these various possibilities, ultimately concluding that gradient descent does have an important additional implicit bias: the ability control the margin of the returned network.
5.1 AN EXACT FORMULA FOR THE AVERAGE HOLDOUT ERROR OF SOLUTIONS
To investigate whether slackness in the bounding technique is responsible for the gap, an additional theoretical tool was developed: formula for the holdout error of a binary classifier averaged over the solution space. contrast Theorem which gives an upper bound on population error, Theorem is an equality and therefore does not suffer from slackness. The proof is given in Appendix A.1
Theorem (Average holdout enror of a binary classifier). First. fix probability measure IP over the weight space S2 of a binary classifier. Let S denote a training set and Vs denote the solution space. For holdout set T of m datapoints, consider the holdout error 0 S er(w) & 1 of weight setting w E Q and its average over the solution space ET(Vs) == (w--P(T( w E Vsl. Then:
PIVsu(a,- P[Vs]
eT(Vs)
Σ (R.J)T
(1I)
m
In words, the average holdout error over solutions equals the reduction in the volume of solutions when the training set is augmented with negated holdout point, averaged over the holdout set. For an infinitely wide neural network, Equation I1 involves computing a sum of ratios of Gaussian orthant probabilities. These probabilities can consistently estimated by Equation in Lemma]]
5.2 THREE- WAY COMPARISON OF HOLDOUT ERROR
Armed with Theorem 3 this subsection makes a three-way comparison between the holdout error of infinite width networks averaged over solutions, the holdout error of finite width networks averaged over solutions, and the holdout error of finite width networks trained by gradient descent.
To compute the holdout error of finite width networks averaged solutions, weight vectors were randomly sampled and all non-solutions were discarded. To make this process computationally tractable, very small training set used consisting of only 5 samples from binary digits. A holdout set of 50 datapoints was used, and the network was set to a 7-layer MLP. The results were:
average holdout error at infinite width:
0.337 + 0.001;
average holdout error at width 10,000:
0.33 + 0.01;
gradient descent holdout error at width 10,000:
0.178 + 0.007.
Based on these results, three comments are in order. First, the close agreement between the average holdout error at finite and infinite width suggests that the infinite width limit may not responsible for the significant gap observed in Section 4 Second, the significant gap between the gradient descent holdout error and the holdout error averaged over solutions suggests slackness the bounding technique in Theorem 2 may also not be the main culprit. Third, the significant gap between the gradient descent holdout error and the holdout enror averaged over solutions suggests that gradient descent does have extra implicit bias. The next subsection attempts diagnose this implicit bias.

---

Under review as a conference paper at ICLR 2022
)(x());-)
Holdaut error along the label ray
Chance
label
Average holdout error orthant
Network holdout scale
ray
0.4
Network train error scale
;.)l):))
Error
NNGP holdout error scale a
0.2
10-2
10-1
10
101
10a
Label scale
Varying the label scale at depth? 2
Varying the label scale depth
0.4
0.4
Error
Chance
Error
Win so estimatoo for
W 000. label scale 0.1
0.2
W 000. label
0.2
0.0
0.0
100
200
300
400
500
100
200
300
400
500
Number of training examples
Number of training examples
Figure 3: Exploring generalisation performance along the label ray defined in Section 5.3 Functions further along the ray are found to generalise substantially better than average, for both NNGP draws and finite width networks trained by gradient descent.
Top left: Schematic diagram illustrating the label ray function space. While all functions in the grey shaded orthant attain zero train error, the darker shaded solutions have small margin and thus-under a Gaussian process model moldo-holdout predictions are expected to be driven by random fluctuations.
Top right: Holdout error along the label ray of the small learning task described in Section 5.2 Results are shown for both networks trained by gradient descent and NNGP posterior samples. The label scale a defined in Section [53 and measures the distance of the function along the label ray. NNGP posterior samples were generated by sampling from a Gaussian distribution with mean and covariance given by Equations 12 and 13 Networks trained by gradient descent were found by training with the loss function given in Equation 14 Shading shows the standard deviation over 100 random intialisations or posterior samples. Deep into function space (large a) the holdout error is significantly better than for functions close the origin (small o:). The average holdout error over the orthant, as computed in Section 5.2 is also plotted. Large margin networks and NNGP posterior samples both significantly outperform the orthant average. Finally, a gap visible between large margin NNGP posterior samples and large margin networks trained by gradient descent-this may be due to an additional and undiagnosed implicit bias of gradient descent.
Bottom: Repeating experiments from Section with a smaller label scale to sanity check the findings. For depth 2 and depth 7 MLP on the decimal digits dataset, the experiment from Section was repeated with the loss function set L.=0.1 as defined in Equation 14 The infinite width W oo curve shows the Theorem 2 bound estimated via Cp. The other two curves show the results of networks trained by gradient descent with Ca=0.1 and La=1- Despite all networks attaining 0% train error, holdout error was significantly worse for networks trained using Ca=0.1- Also, the networks trained using Ca=0.1 exhibit substantially smaller gap with the Theorem upper bound.
8

---

Under review as a conference paper at ICLR 2022
5.3 DIAGNOSIS: MARGIN
This subsection finds that gradient descent has an important implicit bias in determining the margin of the returned network. This conclusion is made by studying the generalisation error of functions along the label ray in function space- space-depicted in Figure 3 (top left). For a training set S with a vector of binary labels y E {+1]", a function a-far along the label ray refers to the point ay E Fs.
For the case of a zero mean NNGP, the predictive distribution on a holdout set T conditioned on training labels o-far along the label ray is given by Bishop (2066 Chapter 2.3.1):
posterior mean = a x Ers Eyy
(12)
posterior covariance = Σrr - ETS
(13)
where Eys is the covariance between holdout and train inputs, and EsT, Ess and Err are defined analogously. For large a, predictions are driven by the posterior mean, whereas for small a, they driven by random fluctuations. So one expects that letting a - oo should improve holdout error.
For the case of gradient descent training, functions a-far along the label ray can be returned by minimising the following loss function:
(W) = 1 Σ (I((0: -ry)))
(14)
subtle but important point is that for gradient descent training with Nero (Liu et al. (022]) the norms of the weight matrices are constrained, thus controls properly normalised notion of margin.
An experiment was performed to measure the holdout error of networks a-far along the label ray-raay for both NNGP draws and neural networks selected by Nero-for for ranging from 10-2 to 10². As can be seen in Figure (top right), varying a appears to directly control the holdout error, despite all solutions attaining 0% train error. Moreover, large a solutions significantly outperform the average holdout error over the solution space. This suggests that gradient descent possesses a significant implicit bias in its ability to control margin saargin-ooing beyond the implicit bias of architecture.
To sanity check this result, experiments from Section 4 were repeated with the loss function Ca=0.1 replacing La=1- As can be seen in Figure 3 (bottom), the holdout performance was significantly diminshed at a = 0.1, as was the gap with the PAC-Bayes bound from Theorem 2
6 DISCUSSION AND CONCLUSION
This paper has explored the separate implicit biases of architecture and gradient descent. Section derived analytical generalisation bound on the NNGP posterior, Section 4 found this bound be non-vacuous, while Section 5 showed that large margin functions substantially outperform the bound.
The findings in this paper support the importance of the implicit bias of architecture: reproducing the findings in Valle-Pérez & Louis (2020) but with improved technical tools, the average generalisation already found to be good. But the implicit bias of gradient descent
performance of architecture was also found to be important. In particular, in contrast to an assumption made by Valle- & Louis (2020) that gradient descent "samples the zero-error region close uniformly", it was found that gradient descent can be used to target zero-error functions with large margin. This also subtly counters a proposal by Mingard et al. (2021) that gradient descent acts like "Bayesian sampler". In particular, gradient descent can target functions with margin - oc for which the Bayesian posterior probability - And indeed, these minimum a posteriori functions seem to generalise best.
One direction of future work suggested by these results is an improvement to the function space PAC-Bayes theory to account for margin. While margin-based PAC-Bayes bounds do already exist 2003 Neyshabur et al. 2018), these bounds operate in
(Herbrich) 2001] Langford & Shawe-Tay weight space and further do not seem to imply an advantage to selecting the max-margin classifier the other classifiers included in the PAC-Bayes posterior.
Ultimately, a generalisation theory that properly accounts for the various implicit biases of deep learning could provide more principled basis for both neural architecture design as well as the design of new regularisation schemes. is hoped that the new analytical results as well as experimental insights included in this paper contribute step towards reaching that goal.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alessandro Achille and Stefano Soatto. Hmergence of invariance and disentanglement in deep representations. Journal of Machine Learning Research, 2018
Navid Azizan, Sahin Lale, and Babak Hassibi. Stochastic mirror descent on overparameterized nonlinear models. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spercrally-normaaiiee margin bounds for neural networks. Neural Information Processing Systems, 2017.
Felix Biggs and Benjamin Guedj. On margins and derandomisation in PAC-Bayes, arXiv:2107.03955, 2021.
Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer- Verlag, 2006.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Neural Information Processing Systems, 2009.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Uncertainty in Artificial Intelligence, 2017.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awart aware minimization for efficiently improving generalization. International Conference on Learning Representations. 2021.
Jonas Geiping, Micah Goldblum, Phillip E. Pope, Michael Moeller, and Tom Goldstein. Stochastic training is not necessary for generalization. 1.Xiv:2109.14199 2021.
Ralf Herbrich. Learning Kernel Classifiers: Theory and Algorithms. MIT Press, 2001.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
John Langford and Matthias Seeger. Bounds for averaging classifiers. Technical report, Carnegie Mellon University. 2001.
John Langford and John Shawe-Taylor. PAC-Bayes & margins. In Neural Information Processing Systems, 2003.
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. MNIST handwritten digit database, 1998.
Jaehoon Lee, Jascha Sohl-Dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks Gaussian processes. In International Conference Learning Representations, 2018.
Yang Liu, Jeremy Bernstein, Markus Meister, and Yisong Yue. Learning by turning: Neural architecture aware optimisation. International Conference on Machine Learning, 2021.
David A. McAllester. Some PAC-Bayesian theorems. In Conference Computational Learning Theory, 1998.
Chris Mingard, Guillermo Valle-Pérez, Joar Skalse, and Ard A. Louis. Is SGD Bayesian sampler? Well, almost. Journal of Machine Learning Research, 2021.
Radford M. Neal. Bayesian Learning for Neural Networks. Ph.D. thesis, Department of Computer Science, University of Toronto, 1994.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to noertral margin bounds for neural networks. In International Conference on Learning Representations, 2018.
10

---

Under review as a conference paper at ICLR 2022
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrriztion in generalization neural networks. In International Conference on Learning Representations, 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 2018.
Guillermo Valle-Pérez and Ard A. Louis. Generalization bounds for deep learning. arXiv:2012.04115, 2020.
Guillermo Valle-Pérez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. In International Conference Learning Representations, 2019.
Aad W. van der Vaart. Asymptotic Statistics. Cambridge University Press, 1998.
Vladimir N. Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 1971.
Colin Wei, J. Lee, Qiang Liu, and Tengyu Ma. On the margin theory feedforward neural networks. 1rXiv:1810005366, 2018.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stem, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Neural Information Processing Systems, 2017.
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang. and Rong Ge. Dissecting Hessian: Understanding common structure of Hessian in neural networks. arXiv:2010.0426/, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.

---

Under review as a conference paper at ICLR 2022
APPENDIX A PROOFS
A.1 FUNCTION SPACE ORTHANT ARITHMETIC
The following PAC-Bayesian theorem is due to Valle-Pérez et al. 2019)
Theorem (A PAC-Bayesian theorem). First, fix probability measure P' over the weight space Q of classifier. Let denote a training set of ni datapoints sampled iid from the data distribution D and let Vs denote the corresponding solution space. Consider the population error 0 S ( I of weight setting w E Q, and its average over the solution space (VV) == (w=FlED(()) w E Vs]- Then, for proportion 5 of draws of the training set S,
In
In 2n
PlVs]
(Vs) S In
(4)
1 1 EVss)
Proof. The first inequality is a basic property of logarithms. The second inequality follows from Theorem 3 of Langford & Seeger 22011) by setting the prior measure to P(-) P(-) and the posterior
measure to the conditional QQ Vs).ss. Under these settings, the average training error rate over the posterior zero and KL(Q P) In FIVe]
Theorem (Average holdout enror of a binary classifier). First, fix a probability measure IP over the weight space St of binary classifier. Let S denote training set and let Vg denote the solution space. For a holdout set T of m datapoints, consider the holdout error 0 S (r(w) < 1 of weight setting Ω and its average over the solution space er(ss) = (eo-r(sT(w)) w E Vs). Then:
er (Vs)ss
1
Σ
P|Vsu(a,-v)
(11)
m
P(Vs)
(x.N)E
Proof.
The result follows by interchanging the order of expectations, rewriting the expectation of an indicator variable as a probability and finally applying the definition of conditional probability:
1
ET (Vs)= == (wwel)T(w) w Vsl
Σ (T
Ewwe [[[sign f(x, w) = =-yl e Vs]
m
1
IP Isign f(x, w) - w Vss
m (T.
1
Σ
[sign fxx w) -3 and w E Vs)
m
P [w E Vs]
(*,8)ET
1
P(Vsu(a, F[Vs]
(Z.8)ET
A.2 GAUSSIAN ORTHANT PROBABILITIES
Lemma 1 (Gaussian orthant probability). For covariance matrix E E RR and binary vector y E {+1}", let p denote the corresponding Gaussian orthant probability:
IP. (.)) v]-
Letting I denote the x n identity matrix, C the elementwise product and |-| the elementvise absolute value, then p may be equivalently expressed as:
2n Eu-N(O.) (e (vo w yddt Mx -1))_))l) = -CoEE)))
p
(8)
and p may be bounded as follows:
p Σ
- V 1) =: 2
c (C,,E)))
(9)
2
12

---

Under review as a conference paper at ICLR 2022
Proof. The orthant probability may first be expressed using the probability density function of the multivariate Normal distribution as follows:
e 0=2 "op"x=' dyp.
(2 " det NOP20
By the change variables may be expressed as:
MOy
or equivalently p= Vdl Eyy a u). the orthant probability
Vet
((oo)) Vilet Ey ((row) du
p
(2T) Ja20
(vollu)" ((etEs-((GGll) du
2"
(2xT
R"
Eun
(e (vol)))) (y
2
where the second equality follows by symmetry, and the third equality follows by inserting factor of e-2 /2 into the integrand.
Next, by Jensen's 's inequality.
+ (. VdetEE- -ii)
p z
c
2
Eng Fun (wws Vilt [,s)]
2
-
E Vitet 532,7' E Vilet ز
e
2
- Vict -x) Egg vaay Vieyy
e
2n
Vdd Se n - (1-
n
c Viet -
2
The third equality follows by noting Eu-N(on |ullu, En u² 1. while for i +
(u |ueluuy] (E=,))1011) |u|]² 2/T.
L
A.3 NEURAL NETWORKS AS GAUSSIAN PROCESSES
The essence of the following lemma is due to Neal (1994). The lemma will be used in the proof of Theorem
Lemma 2 (NNGP correspondence). For the neural network layer given by Equation 18 randomly sampling the weight matrix W!), If the following hold:
consider
(i) for every x E Rdo the activations and second moment;
(z)- ,..,;p (=) are with finite first
(ii) the weights (!!)) are drawn iid with zero mean and finite variance;
(iii) for any random variable with finite first and second moment, ip(2) also has finite first and second moment;
then, in the limit that d oo, the following also hold:
(1) for every RRdo, the activations yp (z)) ,... =cc second moment;
(x)) are iid with finite first and
(2) for any collection of k inputs x(0) ..... (kk), the distribution of the ith pre-activations
( (z((1)), ,.., 20) (2,2)()))))))))))))))))))))))( (x((k) jointly Normal.
13

---

Under review as a conference paper at ICLR 2022
While condition (i) may seem non-trivial, notice that the lemma propagates this condition to the next layer via entailment (1). This means that provided condition (i) holds for (x)()((x)) at the first layer, then recursive application of the lemma implies that the network's pre-activations are jointly Normal at all layers via entailment (2).
Proof of Lemma 1 (x)
To establish entailment (I), consider the di-dimensional vector 2 =
di
x
Observe that Z1 satisfies:
[iy (x)) dij ( at (w))
21
(15)
By conditions and (ii), the summands in Equation 15 are iid random vectors with zero mean, and any two distinct components of the same vector summand have the same variance and zero covariance. Then by the multivariate central limit theorem (van der Vaart 1998] p- 16), in the limit that d + oo, the components of Zi are Gaussian with covariance equal to scaled identity matrix. In particular, the components of Zı are iid with finite first and second moment. Applying condition (iii then implies that the same holds for (Z1)). This establishes entailment (1).
To establish
entailment
(2), consider instead the k-dimensional vector Z2
( 2/ (z
2 ( (z(k)) Observe that Zz satisfies:
d1
W (200 (z()) ..... w ( (x()))
Z2 =
(16)
Again by combining conditions (i) and (ii), the summands in Equation 16 are iid random vectors with finite mean and finite covariance. Then as di-1 + oo, the distribution Ze is jointly Normal- again by the multivariate central limit theorem. This establishes entailment (2).
The essence of the following theorem appears in a paper by Lee et al. (2018), building on the work of Cho & Saul (2009). The theorem and its proof are included for completeness.
Theorem 4 (NNGP for relu networks). Consider L-layer MLP defined recursively via:
(x)
1
W
(1)
(17)
ddl
1=1
d:-1
(x) v /
1
Σ
(1) W
4p (2) (=))))))
(18)
where E dR denotes input, 2(0(x) (x) Rd: denotes the pre-activations at the Ith layer, W()) denotes the weight matrix at the Ith layer, and denotes the nonlinearity.
Set the output dimension dr, = and set the nonlinearity to scaled relu (pz) == V2. max (0, 2). Suppose that the weight matrices W(1), .... (LL) have entries drawn iid (0, and consider any collection of k inputs ,,.,,... (k) each with Euclidean norm ddg.
If d1, .... di-1 + oo, the distribution of outputs 21 (x("))..... ...,. (L) (e) E R induced by random sampling of the weights is jointly Normal with mean zero and covariance:
x''
E
(L) (x)
hho..oh
(19)
do
L- 1 times
where h(()) = [1 + arccos t)]-
Proof. Condition (ii) of Lemma 2 holds at all layers for iid standard Normal weights, and condition (ii) holds trivially for the scaled retu nonlinearity. Provided one can establish condition (i) for
the first layer activations
(x)) . 2d (x)) then condition (i) will hold at all layers by
(1)
14

---

Under review as a conference paper at ICLR 2022
recursive application of Lemma 2 thus establishing joint Normality of the pre-activations at all layers (including the network outputs). But condition (i) holds at the first layer, since quick to check by Equation 17 that for any satisfying || = do. the pre-activations 2i (zz), .... 2d, (x) are iid N (0, 1), and preserves both iid-ness and finite-ness of the first and second moment.
(1)
Since the pre-activations at any layer are jointly Normal, all that remains to compute their first and second moments. For the ith hidden unit in the ith layer, the first moment E[z (x) = 0. This can be seen by taking the expectation of Equation 18 and using the fact that the w the previous layer's activations and have mean zero.
sy are independent of
Since the pre-activations z! (xx) and 2j (x') are jointly Normal with mean zero, their distribution is completely described by their covariance matrix Ex(x, 2'), defined by:
(1(z,
2 (x))
Ex 20) = (1((, pi(a, (((2, pi(a", (aa,,²)
where the hidden unit index i is unimportant since hidden units in the same layer are identically distributed.
The theorem statement will follow from an effort to express Ee(e, x') in terms of Σ1-1 (I, x'), and then recursing back through the network. By Equation 18 and independence of the W!)) the covariance pi (x, may be expressed
pr = EE o (2) (x))
( (a)))
(20)
where j indexes an arbitrary hidden unit in the (1 1)th layer. To make progress, it helps to first evaluate:
27
(xx E
(x)
= 2 p=-)
2
which follows by the definition of and symmetry of the Gaussian expectation around zero. Then, by recursion:
pı(2, x)) = 1 x) = = 11
where the final equality holds because the first layer pre-activations are iid (((0 1) by Equation 17 Therefore, the covariance Σ₁-1 layer is just:
p p Pt m=1(2,x²']
E,-1 x')
Equation 20 may now be used express (1 2²) in terms of p111(x,x'). Dropping the (x, indexing for brevity:
PI En
10 (w) (v)
1
11 u,020
x2 2pt 110 + x²
T T/ or_
du exp
2(1 - pf-2)
wv.
By making the substitution PI-1 cos f, this integral becomes equivalent to 1 (+) as expressed in
x Equation 15 of Cho Saul (2009). Substituting in the evaluation of this integral (Cho & Saul 2009 Equation 6), one obtains:
(xx = ((p1_1(x,=)))
(21)
where ((t) = 1
+t arccos t)].
All that remains is to evaluate Pr (2. Since E W w(( ozk, this is given by:
(1 x') = E
(1)
(x)) (1) (z')
1
Σ
E
W
w(
nTx' 2.a
do j,k=1
do
The proof is completed by combining this expression with the recurrence relation in Equation 21
15


Reviews:
[{"review_id": "S2XdThR02sC", "reviewer": "Reviewer_Lxe3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points\n\nThe provided PAC-Bayes bound is non-vacuous, which is something that is remarkable in this context. \nThe PAC-Bayes bound takes into account the architecture of the network, and the empirical evaluation validates how this proposal is able to capture this. \nTheorem 3 is an interesting result, although not sure if this is something useful outside this specific problem. \nThe analysis of GD is interesting and provides some novel insights. \n\n\n\nWeak Point:\n\nThe PAC-Bayesian bound does not directly upper bounds the generalization error of a given neural network with null training error. It is an expectation over the generalization error of neural networks with null training error. \n\nThe PAC-Bayesian bound directly builds on previous results (Valle-Pérez et al. (2019)). The contribution is mainly on the improvement of the computation of the bound. Even though, a version of the presented bound also needs of approximate (Monte Carlo)  computations. Why are not you comparing with the previous bound presented in (Valle-Pérez et al. (2019)?\n\n\nWhen evaluating the difference between the provided bound and the results using GD, authors attribute the difference to GD: “the significant gap between the gradient descent holdout error and the holdout error averaged over solutions suggests slackness in the bounding technique in Theorem 2 may also not be the main culprit.” This is a bit confusing statement. To what extent can we be sure that the slackness of the bound is not a relevant reason for this gap? \n\n\nThe analysis of the implicit bias of GD looks a bit arbitrary. Recent literature (Smith et al, 2021, Barret et al. 2021) offers much more solid explanations about this implicit biased. Which are the advantages of your analysis of GD? Authors do not discuss how their contributions relate to these existing works. \n\n\nReferences:\n\nDavid G.T. Barrett, Benoit Dherin (2021) Implicit Gradient Regularization\n\nSamuel L Smith, Benoit Dherin, David Barrett, Soham De (2021) On the Origin of Implicit Regularization in Stochastic Gradient Descent\n", "summary_of_the_paper": "This work starts by introducing a new PAC-Bayes bound over the generalization performance of a neural network that takes into account the architecture of the model. The provided bound is analytically tractable and provides non-vacuous high-probability bounds.  However, when evaluated, authors note that this bound is not tight, and proceed to evaluate the reasons for this gap. According to this work, the main reason for this gap is the implicit biased introduced by the gradient descent algorithm. Then, authors show how the implicit biased of SGD is directly related to its ability to control the margin.", "summary_of_the_review": "I acknowledge that this work introduces some relevant contributions, but, based on the above weak points,  I lean to reject this paper. I find that the main contribution (Theorem 2) to be incremental and that the rest of the analysis do not provide novel and relevant insights. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FWduua5Q1j4", "reviewer": "Reviewer_WQvV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n1. The main finding of the paper, namely the huge disparity between the GD NN and NNGP in section 5.2 is novel, and thought-provoking.\n\n1. The paper is clearly and carefully written, and I notably appreciate the authors injecting notes to provide intuition for their bounds.\n\n1. The question of disentangling architecture from the training procedure in the context of generalization is an active and important area of research to which this paper is relevant.\n\n## Weaknesses\n\n1. My main concern with the paper is that, based on presented experiments, I believe the central claim about GD providing a boost to generalization through large margin-seeking behavior (section 5) is likely very specific to the precise setting considered in the paper. Namely:\n\n\t1. The authors use a very recent \"Nero'' optimizer (https://arxiv.org/abs/2102.07227) instead of GD or even SGD. From skimming the paper \"Nero'' appears to substantially differ from (S)GD, and provide generalization benefits itself over other optimizers. The authors also mention its importance after Equation (14) since it constrains the norms of weights. Further, but on a minor note, the authors use mini-batching, and learning rate (LR) decay. Overall, this setting is very far from what I consider to be vanilla GD, and not adequate to draw conclusions about GD in general. \n    \t* I think to properly discuss the inductive bias of GD, the authors should first clearly define what they mean by GD, and then ablate against different settings that lie between NNGP and GD. For example, GD could be defined as infinite-width, full-batch gradient flow, which yields the Neural Tangent Kernel (https://arxiv.org/abs/1806.07572; NTK), in which case one would only need to compare NNGP and NTK. Alternatively, one could consider finite-width, full-batch, gradient flow, in which case it would be best to compare three settings of NNGP, NTK, and finite-width, full-batch, small LR GD NN. If one defines GD to be simply full-batch, finite-width, then experiments should contain NNGP, NTK, and a set of results for full-batch, finite-width GD for various LRs, since a specific LR is not defined to be a part of GD. If GD stands for just any first-order optimizer, then other optimizers like GD, SGD, Adam etc. should be considered along with “Nero”. And so on. In other words, the point of this tedious comment is that there are many conceptual steps between NNGP and \"Nero'' (infinite Bayesian (NNGP) -> infinite gradient flow (NTK) -> finite gradient flow -> finite GD -> finite SGD -> finite SGD with a specific learning rate -> ... -> \"Nero\" with a specific LR, LR schedule, weight normalization, and a mini-batch size), and by looking only at the extremes of this spectrum (NNGP and \"Nero\") it is hard to understand what aspect of \"Nero\" is responsible for the observed effect. For instance, perhaps it's all about constraining the norms of the weights as mentioned after Equation (14), and perhaps vanilla GD suffers from the same issues as NNGP.\n    \n    1. Even \"Nero\" optimizer aside, I find presented evidence quite limited:\n    \n    \t1. Section 5.3 indeed shows a setting where NNGP will fail for large $\\alpha$, but I find it quite artificial. One could easily define inputs/outputs rescaling as part of the model, and it is in fact an extremely common practice in ML to normalize the data to lie within appropriate ranges. So any effect observed as a consequence of simple data rescaling is not very significant in my opinion, notably when one of the methods (\"Nero\") does weight norm-constraining. Perhaps one way to improve this is to consider datasets where different labels $y_i$ are multiplied by different $\\alpha_i$, resulting in no change in scale on average (not sure at the top of my head what would be the fair setting i.e. $\\sum_i \\alpha_i = 1$, or $\\sum_i \\alpha_i^2 = 1$, or maybe even something dependent on $\\Sigma_{SS}$), while still giving opportunity for margin-seeking methods to show benefits. \n\n\t\t1. Section 5.2 does show a very strong advantage of GD (\"Nero\") over NNGP in an apparently realistic setting. However, this result is contrary to quite a bit of existing literature (e.g. https://arxiv.org/abs/1711.00165,\nhttps://arxiv.org/abs/1810.05148,\nhttps://arxiv.org/abs/1910.01663,\nhttps://arxiv.org/abs/2007.15801) claiming that MLP NNGP / NTK perform on par or better than GD MLPs, especially on small datasets. For this reason I believe this kind of claim requires more substantial evidence, i.e. evaluation over different datasets of different sizes, different architectures, etc. Further, given my argument about section 5.3 above, I would appreciate experimental details / evidence showing that the performance disparity _cannot_ be eliminated by simply rescaling the data, and, as above, that it's indeed the disparity between NNGP and GD and not e.g. between SGD and \"Nero\".\n\n\t1. Please note that preferably, in all claims regarding NNGP generalization relative to GD, for fair comparison the strength $\\lambda$ of the matrix inversion regularizer, i.e. $\\left(\\Sigma_{SS} + \\lambda I\\right)^{-1}$ should be tuned, since it is an important hyper-parameter for NNGP/NTK methods (see e.g. Figure 7 in https://arxiv.org/pdf/2007.15801.pdf).\n\n\n1. IIUC Equation (11) still requires Monte Carlo sampling - could you elaborate on how this compares to simply sampling from the NNGP posterior on the test set and computing the average error over the samples? Is your formula computationally cheaper, does the estimator converge faster, etc? Since it is mentioned as one of the core contributions, it would be good to know how your approach is better.\n\n\n## Other\n\n1. When citing NNGP works, please also cite https://arxiv.org/abs/1804.11271, as this work was concurrent with https://arxiv.org/abs/1711.00165.\n", "summary_of_the_paper": "There is a tension in existing literature regarding the relative importance of (a) architecture and (b) gradient descent (GD) for neural network (NN) performance. This paper presents empirical evidence and theoretical reasoning in favor of GD providing a substantial benefit to generalization on top of the architecture bias. Precisely, the authors demonstrate a setting in which  finite, GD-trained NNs substantially outperform Bayesian finite and infinite-width models of the same architecture.\n\nThe authors also propose two bounds on the expected classification error of a Gaussian process (precisely, infinite-width Bayesian NNs, \"neural network-Gaussian process\"; NNGP), and a way to estimate the expected classification error of the NNGP. There is a big gap between the bounds and empirical performance of wide GD-trained NNs, and the authors conjecture that the gap is due to the beneficial \"large margin-seeking\" bias of GD, enabling superior performance of GD NNs over NNGPs mentioned above.\n", "summary_of_the_review": "# Post-rebuttal update\n\nI thank the authors for correctly pointing out that I misunderstood their work I my initial review. Given their correction, I see this as a stronger submission, and raise my score. However, I still find it lacking comprehensive experiments to claim that their bound/estimator reflect the implicit bias of the architecture, and the discussion about margin is either lacking rigor or is not completely clear to me at this time (namely, I see why for NNGP concentration on the mean is beneficial, but I struggle to understand the precise analogy with the GD, given that NTK posterior mean can often underperform compared to GD networks). \n\nGiven that I post this update late in the discussion period, the paper contains otherwise decent ideas, and I may be misunderstanding some aspects of the margin discussion, I am willing to score this as a weak accept but with low confidence.\n\n# Original review\n\nWhile I think the paper investigates interesting and important ideas, and the writing appears of high quality, I find that experimental evidence for the claim that GD provides a substantial benefit beyond NNGP (section 5.2 and 5.3) is limited to a highly specific setting. I see this as the  the main theme of the paper, and believe it requires much better evidence in terms of both quality (\"Nero\"/SGD/GD/NTK/... ablations, NNGP regularization tuning, controlling for trivial settings like dataset rescaling) and preferably quantity (different datasets, sizes, architectures etc).\n\nOtherwise, the paper also proposes a formula for computing the average classification error of a GP in section 5.1, but I am not sure how this is better than just Monte Carlo sampling the error (perhaps the authors could address this in the rebuttal, although my main concern remains the lacking experiments above).\n\nFinally the authors also propose two bounds on the average GP classification error. However, these bounds aren’t compared to NNGP performance (instead, finite-width GD NNs are used). If NNGP performance is similar to GD NNs in those settings or worse, then IIUC these bounds are not tight and do not appear very practical. Since I’m not an expert in this area, I am also open to being convinced of their importance in the rebuttal, however, I again emphasize that my main concern is the limited experimental setting.\n\nTogether, I commend the three efforts above, but I do not find them significant enough for publication at this time.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DUn8aea4n4M", "reviewer": "Reviewer_CXBm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper explores an important open question in deep learning which is what factors are contributing to the impressive generalization error for deep learning even though no existing theories can adequately explain it. The paper has quite a few strong points but also some weaknesses, both of which I will discuss below.\n\n**Pros**:\n- The paper is very well written and easy to follow. The presentation of all the results and how they fit together is very clear.\n- The experiments on the comparison of different widths of MLP and the infinite width limit are very interesting. It suggests that using infinite width may be a reasonable approximation for what happens at finite width.\n- The discussion of margin is very insightful and it demonstrates that a pure NNGP based approach is insufficient as an explanation for generalization (even though in relatively simplistic settings).\n\n**Cons**:\n- The claim is that the bound can accurately reflect the influence of architectures but in reality, it only applies to MLPs of different depths. While this may be due to the fact that MLPs are amenable to theoretical analysis, it also precludes the results from explaining actual neural networks architectures having different generalization performances. For example, in the bottom-right of figure 2, the separation between the actual performance of depth 2 and depth 7 MLPs are not that large and are clearly vanishing as the number of data points increase (which implies for large numbers of data points the two architectures are not too different). I think the results would be much stronger if similar results can be shown for say CNN (which has intuitive inductive biases for images) or ResNet, although I concede that the analytical bounds may be highly non-trivial to derive.\n- Only Nero is used for optimization, which is a quite new algorithm. What is the reasoning behind this design choice? Do the same experiments hold for other optimization methods? Furthermore, if different optimization algorithms exhibit different generalization performances, where does the phenomenon fit in the proposed framework?\n- The non-vacuousness of the bound feels like a consequence of the dataset (i.e., it’s much simpler than regular tasks) rather than the consequence of the bounding technique, so I am not sure if it’s significant. For example, would this still work if you use cifar 10 or imagenet?\n\n**Questions**:\n- It is not clear to me what the significance of theorem 3 is. With access to held-out data, one could always easily compute the test error. Perhaps the importance is that this can be applied to infinitely wide neural networks?\n- In practice, we know that architecture plays a huge role in how well the model generalizes, which under the paper’s framework would suggest that these architectures would naturally induce high intraclass correlation. It feels like this is something that can be empirically tested for popular architectures (e.g., VGG vs Resnet) even if the analytical bound cannot be computed. Likewise, it would indirectly suggest that as the architecture gets better, the effect of max-margin would be diminishing. This might also explain why some NNGP works have performance comparable to or even better than GD.\n- In [1], the authors discuss the potential insufficiency of existing generalization bounds. In the appendix, there was a discussion about similar problems of PAC-Bayes bounds. Can you discuss how your result fits in [1]?\n\n**Reference**:\n\n[1] Uniform convergence may be unable to explain generalization. Nagarajan et al.\n\n-------------\n\n**Update**\n\nI thank the authors for the response. My questions have been answered but I feel my concerns are not adequately addressed. First, regarding analytical solutions for CNN, the response does not really address the question which is that the technique in its current form does not apply to CNN. If expectation-propagation approximation does just as well then the value of having an analytical bound would be small. If that is the case, then the main contribution of this paper would be the discussion of margin. I have read the discussion between the authors and reviewer HuiV and agree with reviewer HuiV that the discussion of margin could use more careful treatment. This is more true if the authors believe or the experiments show that expectation-propagation is good enough for computing the bound.\n\nRegarding Nero, I am not convinced that it is sufficient to use the observed results to generalize all of the gradient-based optimization methods. If the authors believe that it is, relevant empirical results should be included in the paper.\n\nDue to these reasons, I intend to keep my score.\n\n", "summary_of_the_paper": "The paper investigates the roles of architecture and gradient descent in generalization through the lens of infinitely wide neural networks (i.e., neural network gaussian process). The paper first presents an analytical unbiased estimator of the NNGP’s generalization error and shows that the generalization depends on both the training data and how well the architecture induces correlation between the data points. The approach also offers statistical consistency for the Monte Carlo estimation which previous methods do not. The paper then investigates why these bounds are still very loose compared to the actual generalization error and finds that gradient descent favors solutions with large margins and concludes that the property explains the gap between the NNGP bound and observed performance.", "summary_of_the_review": "The paper presents some insightful results on the implicit bias on architecture and gradient descent as an optimization method. The theoretical discussion is interesting but the experimental validation could be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0pacoWrNQqG", "reviewer": "Reviewer_HuiV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting and well written. Results seem mostly novel and technically correct.\n\nThe fusion of the different implicit biases brought forth by neural architecture and optimization is an interesting topic. In my opinion the paper over promises analysis of both, while providing only analysis of implicit bias of neural architecture under a Gaussian process and asserting that GD maximizes margin without theoretical support and with limited experimental evidence.\n\nStrengths:\n- Well written and motivated.\n- Elegant theoretical results on the average error of the solution space.\n- Combining landscape approach for architectural implicit bias along with trajectory induced implicit bias by GD is very interesting.\n\nWeaknesses:\n- The bounds obtained by the theoretical derivation are only slightly better than chance and there is a very significant gap from the empirical results observed.\n- The analysis of the implicit bias of gradient descent due to margin is confusing and not very convincing. The improvement over the holdout set as a function of increasing margin constant $\\alpha$ is not clear, how does this explain the inductive bias? This seems as a suggestion to improve the margin via this constraint rather than an explanation to what happen when using GD in the discussed setup.\n\n\nAdditional comments:\n- Related work does not cover relevant works such as Neural Tangent Kernels and many trajectory based analyses of GD.\nMinor\n- Theorem 2 - why repeat the assumptions instead of referring to the assumptions of theorem 1?\n- Figure 3, bottom right plot is missing a legend.\n", "summary_of_the_paper": "This paper studies the implicit bias of neural architectures using a Bayesian approach.\nThe paper provides bounds on the average population error of infinite width neural networks that fit the training set under a Gaussian process.\nThe paper also discusses the role of gradient descent in the implicit bias, suggesting it controls the margin of the returned network from the solution space.", "summary_of_the_review": "Interesting paper which suffers slightly from overpromise.\nLandscape analysis is insightful but the gradient descent analysis is limited and does not explain the gap between architectural error bounds and actual error obtained.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting paper aiming to further advance the knowledge of implicit bias in deep networks.  Unfortunately, the reviewers had many concerns about technical details and presentation.  One concern was about section 5, on margins and implicit bias.  Oddly, this section 5 does not cite the extensive literature on margin maximization, implicit bias, and implicit regularization in deep learning (despite a mention of Soudry et al earlier on), whereas the choice of paper title and also this section title would suggest an advance over this work, or at least reference to this work (which goes far beyond that one paper); instead, that section left me a bit confused about the suggested bias and its implications on generalization.  As such, I suggest the authors spend more time on their submission, aiming to further separate their work from prior work, and address the comments of reviewers.
Decision: Reject