We introduce a general theoretical framework, designed for the study of gradient optimisation of deep neural networks, that encompasses ubiquitous architecture choices including batch normalisation, weight normalisation and skip connections. Our framework determines the curvature and regularity properties of multilayer loss landscapes in terms of their constituent layers, thereby elucidating the roles played by normalisation layers and skip connections in globalising these properties. We then demonstrate the utility of this framework in two respects. First, we give the only proof of which we are aware that a class of deep neural networks can be trained using gradient descent to global optima even when such optima only exist at infinity, as is the case for the cross-entropy cost. Second, we identify a novel causal mechanism by which skip connections accelerate training, which we verify predictively with ResNets on MNIST, CIFAR10, CIFAR100 and ImageNet.
Paper
Similar papers
Peer review
Summary
This paper studies optimisation in deep architectures, and presents a framework for theoretically capturing the role of architectural components like skip connections and normalisation layers/weight normalisation. This framework considers the curvature (smootness) and regularity properties of multi-layer networks (networks that are compositions of per-layer blocks), but differs from existing results for deep NN optimisation as it enables convergence to be shown for trajectories far away from initialisation (useful for settings when global minima only exist at infinity, like with Cross entropy loss). Finally, the authors use their theoretical results to argue that the empirically observed optimisation benefits of skip connections may be due to improving the conditioning of the loss landscape, and reinforce this argument through motivating modified skip connections which (slightly) improve performance empirically in practice.
Strengths
- The paper is well motivated; it address an important question (that of bridging the gap between theory and practice in deep learning optimisation) - The paper is well written and places itself clearly and fairly within the existing literature (in section 3) - The paper makes contributions towards answering this question, such as: 1) building upon existing work in optimisation theory to enable global analyses that can hold for convergence far from initialisation, and 2) connecting their theoretical results to practical considerations concerning architectural design, e.g. skip connections.
Weaknesses
- I'm not sure the extent to which the theoretical bounds e.g. showing the benefits of skips in terms of regularity (i.e. looking at minimum eigenvalues) translate into practice, due to the assumptions made that may not hold in practice, and also the fact that they are worst-case bounds (see lines 265-271 for the authors own words on this). I should add that this isn't really a huge criticism of this work as it applies to most works in this area. - I'm not sure if the statement in section 6 'skip connections aid optimisation by improving loss regularity' is itself a big contribution. As the authors write in lines 138-146, there have been several works to make this statement/similar statements. Moreover, as far as I understand the theoretical arguments in Theorems 4.7 and 5.1, the arguments goes like: "Each residual layer's jacobian can be written as <identity + something bound to have eigenvalues norms less than 1>, which will have positive minimum eigenvalue, and by the chain rule their product will be too", which is quite a simple argument (forgive me if I have misunderstood, and of course it is good to formalise these things). - The experimental results seem a bit thin, particularly I'm a bit hesistant to read too much into comparisons of training speed on ImageNet if learning rates haven't been tuned (and indeed it seems most hyperparameters were not tuned for the CIFAR results, in Appendix A.1). It would also be good to verify the empirical gains of the proposed skip architectures across different optimisers (e.g. Adam), and more depths/different residual architectures like PostAct, and also other data settings (e.g. language tasks with residual transformers), to be more convincing empirically. - I think the Deep Kernel Shaping recent line of work (https://arxiv.org/abs/2110.01765, https://arxiv.org/abs/2203.08120) is highly relevant, and complements the current paper, so probably should be cited. Likewise, the reparameterised VGG works (https://arxiv.org/abs/2101.03697, https://arxiv.org/abs/2205.15242).
Questions
- Can the authors comment on the fact that their results are designed for parameters converging to global minima at infinity, with the fact that they require bounded weights (or normalised weights/normalisation layers) in their analysis? - Can the authors clarify what they mean by 'I is an average pool', do you pool over all pixels or only within a set filter size? It would be good just to provide a formula for this. - Please can the authors respond to my comments in the weaknesses section. I will be happy to update my score if the rebuttal can address these. **Update: after clarifications in the rebuttal, additional experiments, and reading the other reviews, I am increasing my score to 7**
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Please see weaknesses, though the authors are quite fair about the limitations of their work and also future directions.
Summary
Paper deals with convergence of deep learning making use of neural Tangent Kernels (NTK) theory and its recent advances. It is a theoretical work, claiming to provide ... "l: 7-11 Abstract: ... the only proof of which we are aware that a class of deep neural networks can be trained using gradient descent to global optima even when such optima only exist at infinity, as is the case for the cross-entropy cost." The proof, that holds for normalised networks with dense skip connections, uses an interesting approach showing that there exists sufficiently small learning rate that induces both gradient Lipschitzity and PL lower bound on gradient norm. Interestingly the paper admits that main theorem (claiming above) is unrealistic for many reasons, i.e., more data points than input dimensions, not skipping every layer etc. The experimental results are to demonstrate that some ideas used in the main theorem could hold in practical settings as well, forming the Hypothesis 6.1.
Strengths
First I'd like to thank authors for the submission of interesting paper. It has well written introduction and background knowledge sections, recalling the key building blocks (Lipschitz gradients and PL inequality) and how are they treated in related works. Also the approach of proving the main theorem as highlighted in summary is interesting. However its 'globality' is less surprising when normalisation layers are required (than any point is weight space is translated and rescaled to lie nearby origin in probability and thus near origin NTK theory applies).
Weaknesses
Impact: From my perspective and despite the nice work of proving the Main Theorem, the main weakness of this work lies in its impact. The Theorem relies on unrealistic assumptions, admitted by authors as well between lines 265-275. Then paper reduces to "just another" hypothesis why in "practice" deep learning converges to global optima. Recall that regularisation of skip connections have been reported and theoretically argued in multitude of previous works (see, Related Work sections or Principles of riemannian geometry in neural networks, Hauser, Michael and Ray, Asok, Advances in neural information processing systems, vol. 30, 2017 just to mention one out of many uncited, for instance). Clarity: To improve the impact the work would benefit from more accessible presentation. I leave it to authors to consider that for next iteration.
Questions
Q1: The paper strives to establish new toolkit for a convergence theory in DL. One way to increase the impact and importance for ML community would be to elaborate and suggest research directions newly opened up by this approach. Could authors elaborate on open problems briefly mentioned in Discussion and suggest the ways to leverage results in the paper to advance them?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
1 poor
Limitations
As per above, the main results relies on highly unrealistic assumptions and thus impact is limited mostly to 'proof technique' for certain problems within NTK realm. This could be powerful, but should be elaborated more, see Questions section.
Summary
The paper provides a novel proof strategy showing the guaranteed convergence to a global optima if a particular class of deep neural networks with non-linear activation functions provided there are skip connections. Such results have been known for linear networks so it is nice that it also applies to non-linear networks even when using a cross-entropy loss where some of the weights might diverge. The paper goes on to show empirically that by adding in skip connections where the do not currently exist it is possible to speed up convergence of Resnets albeit marginally.
Strengths
This is a very accomplished paper, clearly written by people who know what they are doing. The paper provides a novel proof strategy to prove convergence.
Weaknesses
Although technically elegant, the proof strategy only currently works in the strictly over-parameterised regime. This is not a regime where most people work and it seems unlikely that convergence fails when we have more data-points. I would therefore class this as a proof strategy that unfortunately doesn't really work. Obviously, I might have misunderstood and would change my judgement if the authors could convince me that I am wrong. The proof also seems to sacrifice linear convergence, which makes the proof slightly less interesting. Again, maybe I am wrong about this. More generally it is a difficult judgement call as to the value of this paper. Clearly in deep networks people run in a regime where there is most likely many local and global optima and where they never run long enough to reach an optima (given the number of parameters, there use of mini-batches and typical size of the momentum parameter). It is also not clear that reaching a global optimum is desirable (early stopping was a common regularisation strategy in small neural networks---it maybe unnecessary in deep neural networks because we always stop early). In addition, Relu activation functions are usually found to give superior performance to those with Lipschitz gradients. It thus seems that the direction of this line of research is telling us little about deep learning optimisaton. I accept that it is interesting whether there exists a deep network with a unique minima that can be solved efficiently that demonstrates some of the power of deep learning. This could be shown empirically, but conditions such as strict over-parameterisation makes this less useful. I also appreciate the challenge involved in proving anything and I admire the attempt, but I still need some convincing that the direction of research is leading somewhere. I found the empirical part of the paper slightly underwhelming. The effect of adding a skip connection did lead to systematic improvement, but rather minor. However, there are many explanations out there of why skip connections are beneficial and while it is plausible that the improvement is due to improved regularisation, I suspect other explanations could also be put forward (e.g. further breaking of symmetry). This was by far the hardest paper I had to review and it took an order of magnitude longer to do it. Even then I am at my limit of understanding so my critique might be unfounded. If you can convince me then I am happy to change my score.
Questions
Is the regime where there are more training data than free parameters physically different (i.e. we would expect in some cases we would not converge)? If not is not the success of the proof a mathematical artefact rather than capturing the physics? Is it the case that convergence might be sub-linear? If so are there any guarantees on the speed of convergence?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
2 fair
Limitations
N/A
Summary
This paper proposes a formal theoretical framework to analyze gradient and convergence properties of multilayer deep networks. The authors make the following contributions: (1) they provide the first proof that certain deep networks can be trained to global optima at infinity using gradient descent; (2) the authors show that skip connections improve the loss regularity and thus improve the optimization speed; (3) they empirically show that improving the mean singular values of layer Jacobians can practically improve the convergence of ResNets on practical datasets like MNIST/CIFAR/ImageNet.
Strengths
The paper has following strengths: 1. The authors present a detailed study of smoothness and regularity of deep networks with skip connections and normalization layers. By connecting these properties to singular values of layer Jacobians, authors demonstrate that skip connections improve loss regularity. This insight is interesting, and the authors verified this empirically on practical networks on MNIST, CIFAR, ImageNet datasets. 2. The proposed theoretical framework may be useful for further theoretical studies on models with skip connections. 3. The authors also conducted an interesting experiment where they augment the 1x1 convolutions with a deterministic mapping which has singular values = 1 (they used average pool that was rescaled to give singular values = 1). The authors showed that this improved training convergence as well as the final loss for all networks considered.
Weaknesses
The paper has following weaknesses: 1. Some of the assumptions (as identified by the authors themselves) are not practical (lines 265-271). However, this is to be expected due to difficulty of this kind of theoretical studies. A few other assumptions include: d_{l-1} >= d_{l} (line 241) which generally does not hold (models usually have increasing number of neurons/feature maps). Also, in Theorem 5.1, can authors elaborate more on the implications of using convex cost function on the practicality of their theoretical results (line 252)? 2. Instead of using a deterministic map (avg pool rescaled to give singular values = 1), did the authors try directly using orthogonal initialization on the 1x1 convolutions in the skip connections? Would that significantly improve convergence compared to regular ResNets with default 1x1 initializations? Why did the authors use avg pool based parameterization of the skip connections? 3. There are a few important related works that the authors should discuss in section 3. Specifically, one paper defines “Layerwise Dynamical Isometry” [ICLR 2020, https://arxiv.org/abs/1906.06307] that talks about singular values of layer Jacobians and shows how improving those singular values can significantly improve training convergence of highly sparse networks. Another paper that is highly related defines NN-Mass [CVPR 2021, https://arxiv.org/abs/1910.00780] which explicitly relates singular values of layer Jacobians to skip connections. Although their theory is formulated for DenseNet-type networks, empirically, they show that their metric works for ResNets and MobileNets too. These methods show that such theory-grounded “training-free” metrics can identify efficient models directly at initialization without expensive training-based search methods. Other newer papers from this domain conduct full-blown zero-shot (training-free) Neural Architecture Search like ZenNAS (ICCV 2021, https://arxiv.org/abs/2102.01063), ZiCo (ICLR 2023, https://arxiv.org/abs/2301.11300), MAE-DET (ICML 2022, https://arxiv.org/abs/2111.13336), etc. These papers provide more insight towards expressive power or gradient properties of complex deep networks. Although the above papers may not have as much formal theory as the proposed work, it would be good to see relationship between more practical papers and the present theoretical study.
Questions
Please see above.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Yes.
Thank you for your detailed and candid response. I am sympathetic to theoretical papers getting published in NeurIPS even when they make unrealistic assumptions (proofs are hard), although it is important that they address a real issue and are not just mathematicians talking to themselves. It is an interesting insight that you might get converge to a unique optimum in the over-parameterised case, but not in the under-parameterised case (I was thinking about what convergence means in the wrong way). I am not very convinced that over-parameterisation is a common situation in image applications as image augmentation is nearly always used, but I accept that some sacrifice to reality is often required. I appreciate your attempt to break free of local regularity. It does seem surprising that such a large class of models converges to a global optima, although I need to reflect on whether this is an important observation. I am a bit slow so I need some time to consider if I should increase my rating of this paper.
Thank you for the consideration you are giving to our paper. We agree with your comment regarding image augmentation: perhaps this is one reason why minibatching is important, so that "effective overparameterisation" is available at each step. We do not believe that we are only talking to ourselves with this paper. The point we were trying to make is that convergence analyses with more practical architectural choices (skip connections and normalisation) and the cross-entropy cost have been impossible with previously-existing techniques. Given the prevalence of these choices in practice, we felt this lack of analysis to be a real issue and worthy of our time in addressing it. Thank you again for your time.
With the discussion deadline coming up soon, have you had time to reconsider your assessment?
Thank you for your detailed response. Including the correcting comments on NTK and PL bounds. It was not claimed your were establishing $\textbf{uniform}$ bound, however. What's meant is using PL-ineq. step-wise and thus obtaining "never vanishes" for finite $T$. The point is that involving $\textit{normalisation}$ enables to apply "NTK"-like techniques step-wise (after rescaling by normalisation, which keeps the "normalized" weights closed to the origin, despite arbitrary large absolute values - the main contribution points of your approach, I guess) and taking the limit. Also, cited work on skip connections [Hauser] takes indeed a different geometric perspective, yet it shows that adding skip connections increases smoothness the loss landscape, and thus regularity. I agree a differential geometry perspective is quite far from approach in the manuscript but may be relevant to be cited, due to same claims. Not questioning the lack of novelty either. The opposite is correct, the novelty of your method has been appraised in the rebuttal. It is rather the Impact that was pointed out to be in question. Overall and after reading your response, I can see that one can view the work from the opposite angle. That is, including the normalisation and skip connections and thus generalising previous convergence results to more general architectures is a relevant contribution, despite these two conditions make the proofs more straightforward. Also thank you for additional comments on Q1. Overall, due to change of perspective above, I am ready to increase my rating by one notch to "4" giving more weight to other reviewers' opinions.
We thank the reviewer for their further time and consideration. Should the paper be accepted, we will include citation and discussion of [Hauser] with the additional space provided.
It seems the reviewer has not yet updated their score to 4, as they said they would. With the deadline of the discussion period arriving soon, we ask that the reviewer please update their score at their earliest convenience. We thank the reviewer again for their time.
Thanks, a few more questions
Thank you for the reply to my review. I have a few more questions which I would appreciate replies to: 1. In Theorem 5.1, can you provide an intuitive explanation for what $\mu_t$ correspond to? The notation is suggestive of local PL-coefficients, but as I understand it these are chosen 'hyperparameters'. Also, I think it should be $\mu_i$ not $\mu_t$ in the equation below line 256. 2. What is the difference in order of LN computation in PostAct/PreAct ResNets? I am more familiar with the PostLN/PreLN difference in Transformers so I may be misunderstanding here. In particular, PreLN is the one which has the normalisation inside the residual branch, whereas PostLN uses LN on the sum of the residual branches (outside of any single branch). Is PostAct=PostLN and PreAct=PreLN in your definition? I can also check a reference/figure if you have one. It is not obvious to me why PostAct/PostLN doesn't satisfy Hypothesis 6.1 Thanks
We thank the reviewer for their additional time and attention. 1. The $\mu_t$ are indeed similar to local PL coefficients: at each step $t$, $\mu_t$ is just the smallest singular value of the derivative of the parameter-function map (see Theorem 2.4) at the parameter $\theta_t$, and is therefore a lower bound for $\|\nabla\ell(\theta_t)\|^2/\ell(\theta_t)$, which determines the speed of convergence. It is not quite true that these are hyperparameters. They are instead determined by the architecture. And it is correct that it should be $\mu_i$ and not $\mu_t$ below line 256, thank you. 2. The problem we are referring to is only an issue with the 1x1-convolutional skip-connected blocks (i.e. the blocks that reduce the feature dimension: there are 4 in each ResNet architecture). This is because we only apply our Hypothesis 6.1 to these specific blocks, and leave the others alone. In the PreAct ResNet, these 1x1-convolutional skip-connected blocks have the form: $$ x\mapsto c(x)+f(x) $$ where $c(x)$ is the 1x1 convolution applied to $x$, and $f(x)$ is the residual banch (a composite of BNs, ReLUs and Conv2ds) applied to $x$. On the other hand, in the PostAct (original) ResNet, the 1x1-convolutional skip-connected blocks have the form: $$ x\mapsto BN(c(x)) + f(x) $$ where $c(x)$ and $f(x)$ are the same as above, and BN is an additional batchnorm. Our modification is to add an additional linear map $I$, with singular values equal to 1, to the 1x1 convolution $c$. In the PreAct case this yields: $$ x\mapsto I(x) + (c(x)+f(x)) $$ while in the PostAct case this would yield: $$ x\mapsto BN(I(x) + c(x)) + f(x) \neq I(x) + (BN(c(x)) + f(x)) $$ In the first case, our Hypothesis predicts an upwards-shifting of the singular value distribution of the Jacobian of this block, because we have effectively added $I$, with all singular values equal to 1, to the forward pass of this block. But due to the nonlinearity of BN, the same cannot be said for the PostAct case (note the "$\neq$" above), so that our Hypothesis does not apply.
Thanks
Thanks for the clarifications: I think the intuitive explanation for $\mu_i$ will help readers so would suggest including in the paper. I have increased my score to 7.
Thank you very much for your time and consideration. We will include the intuitive explanation of $\mu_i$ in the paper.
Thanks for the clarifications. I will keep my original rating.
I have read the author response and other reviews. I will maintain my original rating.
Decision
Accept (poster)