On progressive sharpening, flat minima and generalisation

Weaknesses: generalisation bound practicalities: We think it is too strong to say that our bound is superior to others in the literature: what we would instead say is that the two approaches (data complexity versus hypothesis complexity) each have their advantages and disadvantages. Our approach is insensitive to hypothesis complexity which makes bounds based on such approaches so loose, but suffers from a worse rate of decrease in the number of training points.

One way that it may be possible to evaluate our bound in practice would be to generate the data from a GAN whose latent space is the uniform distribution on a hypersphere, or perhaps several GANs (one for each class) to take maximum advantage of the low-dimensionality of the data. If one could estimate the Lipschitz constant of the generators, as well as the local variation terms in our bound, then evaluation of our bound would be possible. However, we believe these evaluations would themselves require substantial additional research and are outside the scope of this paper.

Questions: clarification of contributions in abstract/introduction, and more self-contained narrative Thank you for the recommendations. We agree that they are worth implementing and will consider how to fit them into the tight space limits we are constrained by.

Section 5 being challenging to follow We apologise for the ambiguity. In Theorem 5.1, $\ell$ is just a constant number, such that the loss value at each data point is bounded above by $\alpha\ell^2$ (where $\alpha$ is the coefficient corresponding to the cost function $c$). In Equation (3) we used $\ell$ to denote the empirical loss function of a neural network, which has likely contributed to the ambiguity. We will fix this notation in the next version.

Restrictions on results

• Ansatz 3.1 not rigorous Making the ansatz rigorous will require making explicit the only implicit (and highly nonlinear) relationship between input-output Jacobian and Gauss-Newton conjugate in Equation 4. This is further complicated by the mediating factors we listed in the second paragraph below Ansatz 3.1. Ultimately we believe that sorting this out rigorously in even a simple setting would constitute an entire paper on its own and is outside the scope of this paper, where we seek only to study these objects qualitatively and show their potential in accounting for unexplained phenomena.

• Theorem 4.2 holds only for simple distributions The uniform distribution on the unit sphere has recently been employed to great effect in practical GANs [1], so we do not believe this is a significant restriction. We will include this reference in the next version.

• Experiments only on CIFAR10/100 Running all of our experiments on larger datasets would have been computationally difficult: already our experiments used approximately 3500 GPU hours (see Computational Resources section in appendix).

Minor comments

• Figure 2 Thank you for the recommendation. We will fix that.

• Missing reference Thank you for pointing out that relevant paper. We were previously aware of it but had forgotten to include it. We will include it in the new version.

Would you say that your work essentially points to… Yes, that is a good summary of our work.

Does your work result in… One standout recommendation for practitioners would be to regularise model Jacobian instead of loss sharpness. Our results in Appendix D suggest that doing this even naively can go some of the way to alleviating the poor generalisation associated with small learning rate training. Having said that, sophisticated existing methods (specifically sharpness-aware minimisation) already do an excellent job of regularising model Jacobian (see Fig 5 and Figs 20-27). We believe similarly sophisticated methods targeting model Jacobian would be necessary for state-of-the-art performance.

Another important target audience is theoreticians. The phenomena we explore in this paper are a subject of intense theoretical research, presently concerned mostly with toy models. We hope that our identification of general, architecture-independent mechanisms in this paper will assist in future theoretical research.

[1] Chen et al, SphericGAN: Semi-supervised Hyper-spherical Generative Adversarial Networks for Fine-grained Image Synthesis, CVPR22.

Curse of dimensionality While our bound does suffer from the curse of dimensionality, this is at least qualitatively consistent with empirical work showing that generalisation does indeed get harder with increasing intrinsic data dimension [1]. While we agree that it is not trivial to identify the low dimensional support of a given data distribution, it is possible to approximate this support using a generative model. For instance, the distribution generated by a GAN with latent space dimension $d$ has intrinsic dimension bounded above by $d$. One would then have to quantify how well the GAN approximates its target distribution. This is an active research topic [2] which is outside the scope of our paper.

Theorem 5.1 is hard to parse You have correctly identified the intuition, namely that in order to fit complex data, the Lipschitz constant of the network must grow from a low starting point. Theorem 5.1 just formalises this intuition: if the loss is below a certain threshold across the data points, then the Lipschitz constant of the network must be at least a certain size. That this increase in Lipschitz constant (or Jacobian norm) implies progressive sharpening is something that we only infer from Ansatz 3.1 and is therefore subject to all the conditions that mediate Ansatz 3.1.

We are not sure we understand your intuition behind why progressive sharpening is surprising. As far as we are aware, gradient descent on a neural net for a sufficiently complex dataset will converge to the sharpest minimum to which its learning rate will allow (at least for the square cost, see e.g. [3]), whether or not there are many flat minima in the landscape. Could you please elaborate on your thoughts regarding progressive sharpening and why you think our proposal falls short of explaining it?

Positivity of the right hand side of Eq. (9) No, the right hand side of Eq. (9) need not be positive. For instance, if the dataset consists of only a single class, then the right hand side of Eq. (9) is negative and the bound is vacuous. However, in this setting no sharpening is observed. While this can already be seen to a large extent in our label smoothing experiments (high label smoothing implies the labels are all approximately identical), we are happy to provide additional experimental support for this claim if you feel it would be beneficial.

Ansatz 3.1 in technical terms We agree that this is ultimately desirable, but believe that it is necessary to first establish intuition and a qualitative understanding of how the relevant objects behave, which is our aim in this paper. We believe that technically quantifying Ansatz 3.1 at this early stage in our understanding of it would be of little benefit for future research and is outside the scope of the paper.

[1] Pope et al, The Intrinsic Dimension of Images and Its Impact on Learning, ICLR21.

[2] Biau et al, Some Theoretical Insights into Wasserstein GANs, JMLR, vol 22, 2021.

[3] Cohen et al, Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability, ICLR21.

Lack of quantitative evaluation, looseness of bounds While we agree that a tight, quantitative analysis is ultimately desirable, we are not presently aware of any works which are able to provide such an analysis outside of toy problems. Performing such tight quantitative analysis in the practical settings we consider is impossible without first identifying the correct theoretical objects to study and giving a qualitative account and empirical validation of their behaviour in practical settings. This is what our work proposes to do, and we are aware of no others which do this in the context we are considering. To reject the paper on the grounds that it does not exhibit a complete, quantitatively tight analysis in practical settings would, we believe, be self-defeating given the current state of knowledge.

The Ansatz is pretty crude and the overall narrative overly simplistic: It seems you’re misunderstanding our purposes behind this analysis, especially in relation to the literature. “Whatever does not fit the bill” are known failure modes of the flat minima hypothesis and progressive sharpening, which to date have not been accounted for even qualitatively (see the second paragraph following Ansatz 3.1). Our proposal gives accounts for these diverse failure modes in terms of a single common theoretical object (the conjugate of the Gauss-Newton matrix). Far from being inconveniences to a simplistic narrative, these failure modes and the explanations we give for them point to the subtlety of the mechanism we are proposing and its potential as a target for future research.

The “interactions” you mentioned sound intriguing, and we would appreciate if you could expand on them. Please note though that any one of the qualitative experiments we ran in analysing the failure modes of the ansatz could easily have falsified our proposal (for instance, if in Figures 30 and 31 the parameter derivatives did not scale oppositely to the Jacobians as the data is scaled, with sharpness nonetheless still behaving oppositely). Our experiments therefore do "matter", and provide nontrivial support for our arguments.

Theoretical results are fairly simple: The researchers our work is targeted towards are those who are seeking a greater understanding of deep learning. If we are able to provide such understanding with simple proofs, so much the better.

Unconvincing empirical results:

(a) Figure 1 shows training to 99% train accuracy with full batch gradient descent, following [1]. Figure 29 depicts training with SGD, and its deviation from Figure 1 is precisely the point of that section: the relationship breaks down later in training, as you have pointed out. Of Figures 8-12, the only one that seems noisy is Figure 9: keep in mind that these are randomly initialised networks with only 5 trials, so outliers have an outsized effect and some noise is to be expected. The large scaling difference between Hessian and Jacobian norm does not run counter to any of our arguments and need not be surprising given the nonlinear, implicit relationship we are positing between them in Equation 4. Quantitative explication of this scaling is outside the scope of our already lengthy study.

(b) The trend evident in Figure 2 is that across all learning rates, Jacobian correlates positively with generalisation gap while Hessian correlates negatively, as weight-decay is increased. That is all that the experiment was designed to test. While for fixed weight-decay the relationship across learning rates is indeed unclear, we do not claim that Jacobian norm is the only factor in generalisation (see the variation term in Theorem 6.1) and are instead arguing that loss flatness correlates with generalisation only insofar as it is associated with smaller Jacobian norm. Regarding the Jacobian increase in Figure 5, please see the caption for a possible explanation. Even with this behaviour, the Jacobian correlates more consistently with generalisation than sharpness does, which is all we are claiming in that figure.

(c) We took this consideration into account by terminating training only after the loss was sufficiently small on average over a uniform selection of a number of previous iterations. Please see Appendix B.2 for complete details.

Literature on Jacobian norm: Both Gamba et al (G) and Kromov et al (K) study Lipschitz properties of neural nets via their Jacobians as we do, but with different purposes. Both G and K are concerned with double descent, whereas we are not. Neither G nor K attempts to give an account of progressive sharpening, and neither attempts to give a PAC generalisation bound, whereas we give both. Neither G nor K give theorems on how the Jacobian approximation to the Lipschitz constant scales with number of training points, whereas we do. We will update the paper to cite K as it is indeed relevant.

[1] Cohen et al, Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability, ICLR21