Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the implicit bias of neural architectures using a Bayesian approach.
The paper provides bounds on the average population error of infinite width neural networks that fit the training set under a Gaussian process.
The 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.
main_review: The paper is interesting and well written. Results seem mostly novel and technically correct.

The 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.

Strengths:
- Well written and motivated.
- Elegant theoretical results on the average error of the solution space.
- Combining landscape approach for architectural implicit bias along with trajectory induced implicit bias by GD is very interesting.

Weaknesses:
- 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.
- 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.


Additional comments:
- Related work does not cover relevant works such as Neural Tangent Kernels and many trajectory based analyses of GD.
Minor
- Theorem 2 - why repeat the assumptions instead of referring to the assumptions of theorem 1?
- Figure 3, bottom right plot is missing a legend.

summary_of_the_review: Interesting paper which suffers slightly from overpromise.
Landscape analysis is insightful but the gradient descent analysis is limited and does not explain the gap between architectural error bounds and actual error obtained.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

The 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.

main_review: ## Strengths

1. 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.

1. The paper is clearly and carefully written, and I notably appreciate the authors injecting notes to provide intuition for their bounds.

1. 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.

## Weaknesses

1. 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:

	1. 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. 
    	* 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.
    
    1. Even "Nero" optimizer aside, I find presented evidence quite limited:
    
    	1. 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. 

		1. 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,
https://arxiv.org/abs/1810.05148,
https://arxiv.org/abs/1910.01663,
https://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".

	1. 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).


1. 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.


## Other

1. 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.

summary_of_the_review: # Post-rebuttal update

I 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). 

Given 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.

# Original review

While 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).

Otherwise, 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).

Finally 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.

Together, I commend the three efforts above, but I do not find them significant enough for publication at this time.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: Strong points

The provided PAC-Bayes bound is non-vacuous, which is something that is remarkable in this context. 
The PAC-Bayes bound takes into account the architecture of the network, and the empirical evaluation validates how this proposal is able to capture this. 
Theorem 3 is an interesting result, although not sure if this is something useful outside this specific problem. 
The analysis of GD is interesting and provides some novel insights. 



Weak Point:

The 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. 

The 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)?


When 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? 


The 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. 


References:

David G.T. Barrett, Benoit Dherin (2021) Implicit Gradient Regularization

Samuel L Smith, Benoit Dherin, David Barrett, Soham De (2021) On the Origin of Implicit Regularization in Stochastic Gradient Descent

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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

**Pros**:
- The paper is very well written and easy to follow. The presentation of all the results and how they fit together is very clear.
- 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.
- 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).

**Cons**:
- 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.
- 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?
- 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?

**Questions**:
- 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?
- 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.
- 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]?

**Reference**:

[1] Uniform convergence may be unable to explain generalization. Nagarajan et al.

-------------

**Update**

I 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.

Regarding 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.

Due to these reasons, I intend to keep my score.


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.
review_title: null

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