On skip connections and normalisation layers in deep optimisation
Authors: Lachlan Ewen MacDonald
Jack Valmadre
Hemanth Saratchandran
Simon Lucey
Venue: NeurIPS 2023 poster (2023)
Keywords: optimisation
optimization
skip
connection
normalisation
normalization
deep
learning
polyak
lojasiewicz
lipschitz

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

On skip connections and normalisation layers in deep optimisation
Lachlan E. MacDonald"
Mathematical Institute for Data Science Johns Hopkins University
1 demdacctoalll com
Jack Valmadre
Hemanth Saratchandran
Australian Institute for Machine Learning University of Adelaide
Australian Institute for Machine Learning University of Adelaide
Simon Lucey
Australian Institute for Machine Learning University of Adelaide
Abstract
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 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, CIFARIO, CIFAR100 and ImageNet.
Introduction
Deep, overparameterised neural networks efficiently trainable to global optima using simple first order methods. That this is true is immensely surprising from a theoretical perspective: modern datasets and deep neural network architectures are so complex and irregular that they are essentially opaque from the perspective of classical (convex) optimisation theory. A recent surge in inspired has elucidated this phenomenon, showing linear convergence of gradient descent on certain classes of neural networks, with certain cost functions, global optima. The formal principles underlying these works are identical. By taking width sufficiently large, one guarantees uniform bounds on curvature (via a Lipschitz gradients- type property) and regularity (via initialisation. Convergence to global optimum in that neighbourhood then follows from well- known chain of estimates
theoretical works (22 14 13 52
51 36
28
29
33
32
Loaaakk-ojsiiiiiz-yyyyr inequality) in a neighbourhood of
Despite significant progress, the theory of deep learning optimisation extant in the literature presents least three significant shortcomings:
Most done while at the Australian Institute for Machine Learning, University of Adelaide
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1. It lacks a.formal framework in which to compare common practical architecture choices. Indeed, none of the aforementioned works consider the impact of ubiquitous (weight/batch) normalisation layers. Moreover, where common architectural modifications such as skip connections are studied, it unclear exactly what impact they have on optimisation. For instance, while in [3] it shown that skip connections enable convergence with width polynomial in the number of layers, as compared with exponential width for chain networks, in M polynomial width is shown to be sufficient for convergence of both chain and residual networks.
2. lacks theoretical flexibility. The consistent use of uniform curvature and regularity bounds are insufficiently flexible to enable optimisation guarantees too far away from initialisation, where the local, uniform bounds used in previous theory no longer hold. In particular, proving globally optimal convergence for deep neural nets with the cross-entropy cost was (until now) open problem [5]. 3. It lacks practical utility. Although it is presently unreasonable to demand quantitatively predictive bounds practical performance, existing optimisation theory has been largely unable to inform architecture design even qualitatively. This is in part due to the first item, since practical architectures typically differ substantially from those considered for theoretical purposes.
Our purpose in this article is to take a step in addressing these shortcomings. Specifically:
1. We provide a formal framework, inspired by [45], for the study of multilayer optimisation. Our framework is sufficiently general to include all commonly used neural network layers, and contains formal results relating the curvature and regularity properties of multilayer loss landscapes to those of their constituent layers. As instances, we prove novel results on the global curvature and regularity properties enabled by normalisation layers and skip connections respectively, in contrast to the local bounds provided in previous work.
2. Using these novel, global bounds, we identify a class of weight-normalin residual networks for which, given a linear independence assumption on the data, gradient descent can be provably trained to global optimum arbitrarily far away from initialisation. From a regularity perspective, our analysis is strictly more moxxilexible than the uniform analysis considered in previous works, and in particular solves the open problem of proving global optimality for the training of deep nets with the cross-entropy cost.
3. Using theoretical insight that skip connections aid loss regularity, conduct a systematic empirical analysis of singular value distributions of layer Jacobians for practical layers. We are thereby able to predict that simple modifications to the classic ResNet architecture (20 will improve training speed. We verify our predictions on MNIST, CIFAR10, CIFAR 100 and ImageNet.
2
Background
In this section we give a summary of the principles underlying recent theoretical advances in neural network optimisation. We discuss related works after this summary for greater clarity.
2.1 Smoothness and the Pl.-inequality
Gradient descent on possibly non-convex function E: RR R20 can be guaranteed to converge to global optimum by insisting that & have Lipschitz gradients and satisfy the inequality. We recall these well-known properties here for convenience.
Definition 2.1. Let > 0. A continuously differentiable function é R' - R is said to have 3-Lipschitz gradients, or is said to be 8-smooth over set S C R2 if the vector field Vê: R² + R is S-Liscchit S is convex, having 3-Lipschitz gradicnts implics that the inequality
3
) < VE(O1)T( (02 01) e(O2) - ((0,)
- 10 - 011
(I)
2
holds for all 01, Og e S.
The {-smoothness of l over 5 can be thought of as a uniform bound on the curvature of E over S: if é is twice continuously differentiable, then it has Lipschitz gradients over any compact set K with (possibly loose) Lipschitz constant given by
B sup |
(2)
aek
where 2 is the Hessian and || denotes any matrix norm.

---

Definition 2.2. Let > 0. A differentiable function f: R2 + Rso is said to satisfy the p--Poly
Lojasiewiez inequality, or is said be μ-PL over a S C R if
[VE(0)] 2 ((0)
inf E(6') A'ES
for all 0 S.
The PE. condition on over S is uniform guarantee of regularity, which implies that all critical points over are S-global minima; however, such function need not be convex. Synthesising these definitions leads easily to the following result (cf. Theorem of (23)).
Theorem 2.3. Let IR" - Rzo be a continuously differentiable function that is 3-smooth and p-PE over convex set Suppose that 8g E and let yoe { be the trajectory taken by gradient
descent, with step size yi < 23 starting at 9g. If (0c (00)r C S, then E(fe) converges to an S-global minimum at a linear rate:
e(0)) --' (1 (1
Bn) )) (e(Ow) - E)
for all t N.
Essentially, while the Lipschitz constant of the gradients controls whether or not gradient descent with given step size can be guaranteed to decrease the loss at each step, the constant determines by how much the loss will decrease. These ideas can be applied to the optimisation of deep neural nets as follows.
2.2 Application to model optimisation
The above theory be applied to parameterised models in the following fashion. Let f RP x Iddo + de. be differentiable, -erpparmeterrieed family of functions iRdo - IR (in later sections, L will denote the number of layers of deep neural network). Given N training data ((zi, w)) C Rd Rde, let F R + RdLxNN be the corresponding parameter-function map defined by
F(O): := f(0, x;).
(5)
Any differentiable cost function e: RRdz x Rdz - R2o. convex in the first variable, extends to differentiable, convex function Rdd XN + R20 defined by
N
((2,)
Σ d(
and one is then concerned with the optimisation of the composite E := FF R gradient descent.
R via
To apply Theorem 2.3 needs to determine the smoothness and regularity properties of É. By the chain rule, the former can be determined given sufficient conditions on the derivatives Dy o F and DF (cf. Lemma of 455 The latter be bounded by Lemma 3 of 45), which we recall below and prove in the appendix for the reader's 's convenience.
Theorem 2.4. Let S C. RP be a set. Suppose that y RdLXN + R20 is p-PE over F(S) with minimum Ys. Let A(DF(O)) denote the smallest eigenvalue of (F)))DF(()T. Then
[[VE()) (A(DF(()) (R(0) 75)
for all 0 E S.
Note that Theorem 2.4 vacuous (A(DF(#)) for all 0) unless in the overparameterised regime (p N). Even in this regime, however, Theorem 2.4 does not imply that é is PL unless X(0) can uniformly lower bounded by a positive constant over S. Although universally utilised in previous literature, such uniform lower bound will not be possible in our global analysis, and our convergence theorem does not follow from Theorem 2.3 contrast to previous work. Our theorem requires additional argumentation, which we believe may be of independent utility.
3

---

3 Related works
Convergence theorems for deep linear networks with the square cost are considered in 4 2] In 22 it is proved that the tangent kernel of multi-layer perceptron (MLP) becomes approximately constant over all of parameter space as width goes to infinity, and is positive-
for certain data distributions, which by Theorem 2.4 implies that all critical points are global minima. Strictly speaking, however, [22] does not prove convergence of gradient descent: the authors consider only
gradient flow, and leave Lipschitz concerns untouched. The papers 14 13 II [22 [5]] (36] prove that
overparameterized neural nets of varying architectures can be optimised to global minima close to initialisation by assuming sufficient width of several layers. While [T] does consider the cross-entropy cost, convergence to global optimum is not proved: it is instead shown that perfect classification accuracy can be achieved close to initialisation during training. Improvements on these works have been made in 33
32
7
wherein large width is required of only a single layer.
It is identified in 28 that linearity of the final layer is key in establishing the approximate constancy of the tangent kernel for wide networks that was used in [4 13 By making explicit the implicit use of the Pt condition present in previous works [14 13 52 51 36), [29] proves a convergence theorem
even with nonlinear output layers. The theory explicated in (29 is formalised and generalised in 45]. A key weakness of all of the works mentioned thus far (bar the purely formal (45) is that their hypotheses imply that optimisation trajectories are always close to initialisation. Without this, there no obvious way to guarantee the PE-inequality along the optimisation trajectory, and hence no way to guarantee one does not converge to a suboptimal critical point. However such training is not possible with the cross-entropy cost, whose global minima only exist at infinity. There is also evidence to suggest that such training must be avoided for ofate-of-the-arr test performance [8] [6] In contrast, our theory gives convergence guarantees even for trajectories that travel arbitrarily far from initialisation, and is the only work of which we are aware that can make this claim.
Among the tools that make our theory work are skip connections 20 and weight normalisation [1] The smoothness properties of normalisation schemes have previously been studied 42] 40), however they only give pointwise estimates comparing normalised do not provide a global analysis of Lipschitz properties as we do. The regularising effect of skip connections on the loss landscape has previously been studied in (35, however this study is not tightly linked to optimisation theory. Skip connections have also been shown to enable the interpretation of a neural network as coordinate transformations of data manifolds [9]. Mean field analyses of
non-normalised layers, and
skip connections have been conducted in [49, (30 which necessitate large width; our own analysis
does not. A similarly general framework to that which we supply is given in 47 48]; while both encapsulate all presently used architectures, that of [47 48 is designed for the study of infinite- width tangent kernels, while ours designed specifically for optimisation theory. Our empirical singular value analysis of skip connections complements existing theoretical work using random matrix theory 18 37 39 34 16]. These works have not yet considered the shifting effect of skip connections on layer Jacobians that we observe empirically.
Our theory also links nicely to the intuitive notions of gradient propagation 20 and dynamical isometry already present in the literature. In tying Jacobian singular values rigorously to loss inequality, our theory provides new link between
regularity in the sense of the dynamical isometry and optimisation theory 43 38 46] specifically dynamical isometry ensures better PE conditioning and therefore faster and more reliable convergence to global minima. In linking this productive section of the literature to optimisation theory, our work may open up new possibilities for convergence proofs in the optimisation theory of deep networks. We leave further exploration of this topic to future work.
Due to this relationship with the notion of dynamical isometry, our work also provides optimisation- theoretic support for the empirical analyses of [24] 6 that study the importance of layerwise dynamical isometry for trainability and neural architecture search (27 4 251. Recent work on deep kernel
shaping shows via careful tuning of initialisation and activation functions that while skip connections and normalisation layers may be sufficient for good trainability, they are not necessary 31 50). Other recent work has also shown benefits to inference performance by removing skip connections from the trained model using a parameter transformation [1] or by removing them from the model altogether
and incorporating them only into the optimiser 12

---

Finally, a line of work has recently emerged on training in the more realistic, large learning rate regime known as "edge of stability" [ [0]. This intriguing line of work diverges from ours, and its integration into the framework we present is promising future research direction.
4 Formal framework
In this section we will define our theoretical framework. We will use R=* to denote the space of matrices, and vectorise rows first. We use Id,,. to denote the x identity matrix, and 1, to denote the vector of ones in RR. We use & to denote the Kronecker (tensor) product of matrices, and given vector v IK" Given matrix A E R and a seminorm || on R || lrow will be used to denote the vector of I| |l-seminorms of each of A. The smallest singular value of A is denoted o (A), and the smallest eigenvalue of AA denoted ((A). Full proofs of all of our results can be found in the appendix.
diag(v) (v) to denote the
matrix whose leading diagonal is
Our theory is derived from the following formal generalisation of a deep neural network.
Definition 4.1. By multilayer parameterised system (MPS) we mean a family {fft R" x R4-1XN + [RdixN 1 of functions. Given a data matrix X E RdoxN, we denote by XN the parameter-funntion map defined by F: R Pi + R A
F(0) == fL((L) ..... (X),
(8)
for 0 (01...., 0L)* E RE
Definition is sufficiently general to encompass all presently used neural network layers, but we will assume without further comment from here on that all layers are continuously differentiable. Before we give examples, we record the following result giving the form of the derivative of the parameter-funette map. which follows easily from the chain rule. It will play a key role in the analysis of the following subsections.
J be a MPS, and X E RdoxN a data matrix. For < L,, denote the derivatives of fi with respect to the TRP and Rid:-s variables by D and f respectively, and let f<((8, X) denote the composite
Proposition 4.2. Let {Ji: IP x RR + RRINN
fei(0, == fi-((---))) o... f (X))
(9)
The derivative DF of the associated parameter-function map is given by
(F = (D), De. F (()).
(10)
where for sl< L, Do, F(O) is given by the formula
1.
II f=,,,,,,,00 (000 (f((0,, J=H+1
(11)
with the product taken that indices arranged in descending order from left right.
All common differentiable neural network layers fit into this framework; we record some examples in detail the appendix. We will see in the next section that insofar as one wishes guarantee
global smoothness, the usual parameterisation of affine layers is poor, although this defect can be ameliorated differing extents by normalisation strategies.
4.1 Smoothness
In this subsection, we give sufficient conditions for the derivative of the parameter-function map of a MPS to be bounded and Lipschitz. We thereby able give sufficient conditions for any associated loss function to have Lipschitz gradients on its sublevel sets. We begin with formal proposition that describes the Lipschitz properties of the derivative of the parameter-function map of MPS in terms of those of its constituent layers.
d2 is canonically isomorphic to the space of valued functions N N-point set.
5

---

Proposition 4.3. Let {fi : x X 1XN - -R I==1. and let {St C RR be subsets of the parameter spaces. Suppose that for each bounded set Bi C RR the maps ft. Dft and J ft are all bounded and Lipschitz on St x Bi. Then for any data matrix X E RdoxN, the derivative DF of the associated parameter-finctinn map F R BALXN is bounded and Lipschitz on S -1= Sg CRº.
Proposition 4.3 has the following immediate corollary, whose proof follows easily from Lemma
B.1
Corollary 4.4. Let e: Rd. + R be any cost function whose gradient is bounded and Lipschitz on its sublevel sets Za :- fz Rd c(2) < a). If {fi R x Rd
XNN + B Ji=1 is any MPS satisfying the hypotheses of Proposition 4.3 and X E Rdox,, then the associated loss function 8 :== y F has Lipschitz gradients over S = 1-1 St.
H
The most ubiquitous cost functions presently in use (the mean square error and cross entropy functions) satisfy the hypotheses of Corollary [444 We now turn to an analysis of common layer types in deep neural networks and indicate what extent they satisfy the hypotheses of Proposition 4.3
Theorem 4.5. Fix e > O. The following layers satisfy the hypotheses of Proposition 4.3 over all of parameter space.
1. Continuously differentiable nonlinearities.
2. Bias-free c-weight-nue nweighh-normmlliedd
--ntryy-ormalline affine layers
3. Any residual block whose branch is composite of any of the above layer types.
Consequently, the loss function of any neural network composed of layers above, trained with cost function satisfying the hypotheses of Corollary 4.4 has globally Lipschitz gradients along any sublevel set.
The proof we give of Theorem 4.5 also considers composites bn aff of batch norm layers with affine layers. Such composites satisfy the hypotheses of Proposition only over sets in data-space R N which consist of matrices with nondegenerate covariance. Since such sets are generic (probability 1 with respect to any probability measure that is absolutely continuous with respect to Lebesgue measure), batch norm layers satisfy the hypotheses of Proposition 4.3 with high probability over random initialisation.
Theorem 4.3 says that normalisation of parameters enables global analysis of the loss, while standard affine layers, due to their unboundedness, are well-suited to analysis only over bounded sets in parameter space.
4.2 Regularity
Having examined the Lipschitz properties of MPS and given examples of layers with global Lipschitz properties, let us now do the same for the regularity properties of MPS. Formally one has the following simple result.
Proposition 4.6. Let {fi: RPI x RdIII Then
R
Jimi be MPS and X E RRdoN data matrix.
L II (0I,(0,,,< j=|+1
Σ
(12)
1=1
is a lower bound (DF(()))
Proposition 4.6 tells us that to guarantee good regularity, it suffices guarantee good regularity of the constituent layers. In fact, since Equation (12) is a sum of non-negative terms, it suffices merely guarantee good regularity of the pariiiiee-derriattive of the first layer") and of the input-output Jacobians of every subsequent layer. Our next theorem says that residual networks with appropriately normalised branches suffice for this.
Theorem 4.7. Let {g: R x R + RRXNN be a MPS and X E RdoxNN data matrix for which the following hold:
'The theorem also holds with normalised biases. We make bias-free assumption assumption purely out of notational convenience.
'The parameter derivatives of higher layers are difficult to analyse, due to nonlincarities.

---

1. dj-1 2 di, and [[ 2) < for all 0, E Rd, Z Rd 1XN and 2 2.
2. N S do. X is full rank, p1 2 dido and fi IP x RdoxN + RdiN is a P-parameterised affine layer, for which DP(01) is full rank for all 01 E EP.
M=z of linear maps whose singular values are all equal to For any sequence {T: RR-1IX - BuxNNE2
1, define new MPS {fi by fi := 91, and X)) == 4 + (i, Let F : R + RR x be the parameter-function map associated {fo)t and X. Then (DF( > 0 (but not uniformly so) for all 0 E IRP.
In the next and final subsection we will synthesise Theorem 4.5 and Theorem 4.7 into our main result: global convergence theorem for gradient descent on appropriately normalised residual networks.
5
Main theorem
We will consider normalised residual networks, which are MPS of the following form. The first layer is an normrt-normlllsed, bias-free affine layer f1 = affen Rd x x Rd + Rd xN (cf. Example A.I). Every subsequent layer is a residual block
fi( = 4 + g))
(13)
Here, for all 2 2, we demand that d 2 4, 1, Rdd-ixN - Rd.xN, is some linear map with all singular values equal to 1, and the residual branch g(O,, X) is composite of weight- or entry- normalised, bias-fred affine layers p (cf. Example A. rescaled so that [P(w)]l2 < 1 uniformly
for all parameters w, and elementwise nonlinearities & for which Dojl < 1 everywhere (Example A.2 These hypotheses ensure that Theorem 4.7 holds for {fi and X: see the Appendix for a full proof.
We emphasise again that our main theorem below does not follow from the usual argumentation using smoothness and the PE inequality, due to the lack of a uniform PE. bound. Due to the novelty of our technique, which we believe may be of wider utility where uniform regularity bounds are unavailable, we include an idea of the proof below.
Theorem 5.1. Let { be a normalised residual network; X a data matrix of linearly independent data, with labels Y; and any continuously differentiable, convex cost function. Then there exists learning rate 17 > 0 such that gradient descent on the associated loss function converges from any initialisation to a global minimum.
Idea of proof. One begins by showing that Theorems 4.5 and 4.7 apply to give globally 3-Lipschitz
gradients and a positive smallest eigenvalue of the tangent kernel at all points in parameter space. Thus for learning rate 7) < 28-1, there exists positive sequence (pt = xX(DF(O:)) (see Theorem 2.4p such that / 2 pel, for which the loss iterates E, therefore obey
1
4, 4- S II maa)(oo-)) - -*),
i=0
where a = 17(1 - 2,8 > 0. show global convergence one must show that IT. (40)
If μe can be uniformly lower bounded (e.g. for the square cost) then Theorem 2.3 applies to give convergence as in all previous works. However, br cannot be uniformly lower bounded in general (e.g. for the cross-entropy cost). We attain the general result by showing that, despite admitting no non-trivial lower bound in general, f4 can always be guaranteed vanish sufficiently slowly that global convergence is assured.
We conclude this section by noting that practical deep learning problems typically do not satisfy the hypotheses of Theorem 5.1 frequently there are more training data than input dimensions (such as for MNIST and CIFAR), and many layers are not normalised or ciip-connected. Moreover our Lipschitz bounds are worst-case, and will generally lead to learning rates much smaller than are used in practice. Our strong hypotheses are what enable a convergence guarantee from any initialisation, whereas in practical settings initialisation is of key importance. Despite the impracticality of Theorem [.T] in the next section we show that the ideas that enable its proof nonetheless have practical implications.
'The theorem also holds with normalised biases.
7

---

Practical implications
Our main theorem is difficult to test directly, as concerns only worst-case behaviour which is typically avoided in practical networks which do not satisfy its hypotheses. However, our framework more broadly nonetheless yields practical insights. Informally, Theorem 4.7 gives conditions under which:
skip connections aid optimisation by improving loss regularity.
In this section, we conduct an empirical analysis to demonstrate that this insight holds true even in practical settings, and thereby obtain novel, causal understanding of the benefits of skip connections in practice. With this causal mechanism in hand, we rec- ommend simple architecture changes practical ResNets that consistently (albeit mod- estly) improve convergence speed as predicted by theory. All code is available at https:
6.1 Singular value distributions
Let us again recall the setting l 7 7 F of Theorem 2.4 In the overparameterised setting, the smallest singular value of D) gives a pessimistic lower hound the ratio [ and hence pessimistic lower bound on training speed (cf. Theorems 2.4 2.3). Indeed, this lower bound only attained when the vector Vy perfectly aligns with the smallest singular subspace of DF: probabilistically unlikely occurence. In general, since V = D Vy, the entire singular value distribution of DF a given parameter will play a role determining the ratio |/Ve]3/(e (-)((--)) (*). and hence training speed.
Now DF is partly determined by products of layer Jacobians (ef. Proposition 4.2 As such, the distribution of singular values of DF is determined in part by the dis- tribution of singular values of such layer Jacobian products, which are themselves de- termined by the singular value distributions of each of the individual layer Jacobians. In particular, if through some architectural in- tervention each layer Jacobian could have its singular value distribution shifted upwards, would expect the singular value distribution of DF to be shifted upwards, too. Our argument in the previous paragraph then suggests that such an intervention will result faster training, pro- vided of course that the upwards-shifting is not so large as to cause exploding gradients.
Frequency
Frequency
20-
Sing. Val.
Sing. Val.
Figure 1: Singular value histogram of 500 500 matrix A (left) with entries sampled iid from
Figure I shows in the linear setting that skip connection constitutes precisely such an inter- vention. We hypothesise that this continues to hold even in the nonlinear setting.
U(-1/v500 /500, 1/v500). Adding an identity ma- trix (right) shifts the distribution upwards.
Hypothesis 6.1. The addition of deterministic skip connection, all of whose singular values are 1, across a composite of possibly nonlinear random layers, shifts upwards the singular value distribution of the corresponding composite Jacobian i thereby improving convergence speed at least initially.
We Hypothesis
6.
in the next subsections.
6.2 MNIST
Recall that the ResNet architecture 20 consists part of a composite residual blocks
S(0, A, AX + X),
(14)
where A is either the identity transformation, in the when the dimension of the output of g(0, X)) is the same as the dimension of its input; or randomly initialised Ixl convolution otherwise.
At least for common initialisation schemes.

---

40
40
2.50
(a)
Frequency
30
Frequency
30-
Frequency
30-
(b)
20
20-
20
Loss
1.25
10
10
0.00
2 Sing. Val.
2
10 Epoch
20
Sing. Val.
Sing. Val.
(a) Chain. Mean: 2.36
(b) Res. Mean: 2.91
(c) ResAvg. Mean: 3.17
(d) Loss
Figure 2: (a)-(c) Singular value histograms of composite layer Jacobians averaged over first 10 training iterations. Distributions are shifted upwards as deterministic skip connections added, resulting in faster convergence (d). Means over 10 trials shown.
100
orig.
orig.
4
orig. mod.
mod.
109
mod.
Loss
10
LOSs
Loss
2
10
10 2.
1
10-2
20
40
60
80
20
40
60
80
20
40 Epech
60
80
Epoch
Epoch
(a) Re CIFARIO
(b) ResNet18, CIFAR100
(c) ResNet50, ImageNet
Figure 3: Mean training loss curves for ResNets on CIFAR (10 trials) and ImageNet trials), with standard deviation shaded. The modifications improve training speed as predicted.
Hypothesis 6. predicts that the additions of the identity skip connections will shift upwards the
singular value distributions of composite layer Jacobians relative the equivalent chain network, thus improving convergence speed. It also predicts that replacing Ixl convolutional skip connections with I + A, where is deterministic with all singular values equal will do the same.
We first test this hypothesis by doing gradient descent, with a learning rate of 0.1, on 32 randomly chosen data points from the MNIST training se We compare three models, all with identical initialisations for each trial run using the default Py Torch initialisation:
1. (Chain) A batch-normed convolutional chain network, with six convolutional layers.
2. (Res) The same as (I), but with convolutional layers 2-3 and 5-6 grouped into two residual blocks, and with additional Ixl convolution the skip connection in the second residual block, in Equation [14).
3. (ResAvg) The same (2), but with the 1xl convolutional skip connection of Equation replaced by
14
F(0, A, = (I+ A)X + g(, X).
(15)
where / is an average pool, rescaled to have all singular values equal to 1.
Hypothesis 6.1 predicts that the singular value distributions of the composite layer Jacobians will be more positively shifted going down the list, resulting in faster convergence. This is indeed what we observe (Figure
6.3 CIFAR and ImageNet
We now test Hypothesis 6. on CIFAR and ImageNet. We replace all of the convolution-skip connections the ResNet architecture 200 with sum(average pool, convolution)-ske connections as in Equation (15) above, leaving all else unchanged. Hypothesis 6. predicts that these modifications will improve training speed, which we verify using default PyTorch initialisation schemes.
We trained PreAct-ResNedt on CIFAR10/100 and PreAct-ResNet500 20 on ImageNet using standard training regimes (details can be found the appendix), performing respectively 10 and 3 trial runs
"The input-output Jacobians of MPS layers scale with the square of the number of training points, making their computation with large number of data points prohibitively expensive computationally.

---

on CIFAR and ImageNet. We performed the experiments at range of different learning rates. We have included figures for the best performing learning rates on the original model (measured by loss value averaged over the final epoch) in Figure 3] with additional plots and validation accuracies in the appendix. Validation accuracies were not statistically significantly different between the two models on CIFARIO/100. Although the modified version had statistically significantly better validation accuracy in the ImageNet experiment, we believe this only due to the faster convergence, as the training scheme was not sufficient for the model to fully converge.
7 Discussion
Our work suggests some open research problems. First, the theory [9] could be used in place of our Lipschitz bounds more realistically characterise training of practical nets with large learning rates. Second, like in pervious works [7]. the heavy-lifting for our Pt.-type bounds all done by parameter-derivatio of single layer, and the bounds would be significantly improved by an analysis that considers all layers. Third, extension of the theory to SGD) desirable. Fourth, the dependence of Hypothesis 6. weight variance should be investigated. Fifth, our empirical results the impact of skip connections on singular value distributions suggests future work using random matrix theory [1]]
edge of stability
Beyond these specifics, our formal framework provides setting in which all neural network layers can be analysed in terms of their effect on the key loss landscape properties of smoothness and regularity, and is the first to demonstrate that uniform bound on regularity is not necessary to prove convergence. We hope the tools we provide this paper will be of use in extending deep learning optimisation theory to more practical settings than has so far been the case.
8 Conclusion
We gave formal theoretical framework for studying the optimisation of multilayer systems. We used the framework to give the first proof that class of deep neural networks can be trained by gradient descent even to global optima at infinity. Our theory generates the novel insight that skip connections aid optimisation speed by improving loss regularity, which we verified empirically using practical datasets and architectures.
9
Acknowledgements
We thank the anonymous reviewers for their time reviewing the manuscript. Their critiques helped to improve the paper.
References
[1] Z. Allen-Zhu, Y. Li, and Z. Song. A Convergence Theory for Deep Learning via Over- Parameterization. In ICML, pages 242-252 2019.
[2] S. Arora, N. Cohen, N. Golowich, and W. Hu. A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks. In ICLR, 2019.
[3] S. Arora, Z. Li, and A. Panigrahi. Understanding Gradient Descent on Edge of Stability in Deep Learning. In ICML, 2022.
[4] L. Bartlett, D. P. Hembold, and M. Long. Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks. In ICML, 2018.
[5] M. Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-244 -28,, 2021.
[6] K. Bhardwaj. G. Li. and R. Marculescu. How does topology influence gradient propagation and model performance of deep networks with densenet-type skip connections? In CVPR, 2021.
[7] S. Bombari, M. H. Amani, and M. Mondelli. Memorization and Optimization in Deep Neural Networks with Minimum Over paraamttettri....onn... In NeurIPS, 2022.
10

---

[8] L. Chizat, E. Oyallon, and F. Bach. On Lazy Training in Differentiable Programming In NeurIPS, 2019.
[9] Cohen, Kaur, Y. Li, J. Kolter, and Talwalkar. Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability. In ICLR, 2021.
[10] A. Damian, E. Nichani, and J. Lee. Self selliStabilization:: The Implicit Bias of Gradient Descent at the Edge of Stability. In NeurIPS, 2022.
[11] X. Ding, X. Zhang, N. Ma, Han, G. Ding, and J. Sun. Repvgg: Making vgg-style convnets great again. In CVPR, 2021.
[12] x. Ding, H. Chen, X. Zhang. K. Huang. J. Han, and G. Ding, Re-parameterizing your optimizers rather than architectures. In ICLR, 2023.
[13] S. S. Du, Lee, Li, L. Wang, and Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. In ICML, pages 1675-1685, 2019.
[14] S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient Descent Provably Optimizes Over- parameterized Neural Networks. In ICLR, 2019.
[15] He and T. Liu and D. Tao. Control Batch Size and Learning Rate to Generalize Well: Theoretical and Empirical Evidence. In NeurIPS, 2019.
[16] Z. Fan and Z. Wang. Spectra of the conjugate kernel and neural tangent kernel for lincar-width neural networks. In NeurlPS, 2020.
[17] E. Hairer, S. Norsett, and G. Wanner. Solving Ordinary Differential Equations I: Nonstiff Problems. Springer, 2008
[18] B. Hanin and M. Nica. Products of Many Large Random Matrices and Gradients in Deep Neural Networks. Communications in Mathematical Physics, 376:287-322, 2020.
[19] M. Hauser and Ray. Principles of riemannian geometry in neural networks. In NeurIPS, 2017.
[20] K. He, X. Zhang, S. Ren, and J. Sun. Identity Mappings in Deep Residual Networks. In ECCV, 2016.
[21] S. Ioffe and C. Szegedy. Batch Normalization: Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In ICMI., page 448-456, 2015.
[22] A. Jacot, F. Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization
in Neural Networks. In NeurIPS, pages 8571-8580, 2018.
[23] H. Karimi, J. Nutini, and M. Schmidt. Linear Convergence of Gradient and Proximal-Gradien Methods Under the Polyak-Eooasiewiizz Condition. In ECMI. PKDD) pages 1811, 2016.
[24] N. Lee, T. Ajanthan, S. Gould, and P. H. S. Torr. A signal propagation perspective for pruning neural networks at initialization. ICLR, 2020.
[25] G. Li, Y. Yang, K. Bhardwaj, and R. Marculescu. Zico: Zero-shot nas via inverse coefficient of variation on gradients. In ICLR, 2023.
[26] Li, C. Wei, and T. Ma. Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks. NeurlPS, 2019.
[27] M. Lin, P. Wang, Z. Sun, H. Chen, X. Sun, Q. Q. Li, and R. Jin. Zen-nas: A zero-shot nas for pegh-peeformance deep image recognition. In ICCV, 2021.
[28] C. Liu, L. Zhu, and M. Belkin. On the linearity of large non-linear models: when and why the tangent kernel constant. NeurIPS, 2020.
[29] C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over- wer-parameteriz non- linear systems and neural networks. Applied and Computational Harmonic Analysis, 39:85-116. 2022.
[30] Y. Lu, C. Ma, Y. Lu, J. Lu, and L. Ying. Mean Field Analysis Of Deep ResNet And Beyond: Towards Provably Optimization Via Overparameterizztion From Depth. In ICML, 2020.
[31] J. Martens, A. Ballard, G. Desjardins, G. Swirszez, V. Dalibard, J. Sohl-Dickstein, and S. S. Schoenholz. Rapid training of deep neural networks without skip connections or normalization layers using deep kernel shaping. arXiv:2110.01760 2021.

---

[32] Q. Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths, NeurIPS, 2021.
[33] Q. Nguyen and M. Mondelli. Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology. In NeurlPS, 2020.
[34] Q. Nguyen, M. Mondelli, and G. Montufar. Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks. In ICML, 2021.
[35] A. E. Orhan and X. Pitkow. Skip Connections Eliminate Singularities. In ICLR, 2018.
[36] S. Oymak and M. Soltanolkotabi. Towards moderate overparamettrivation:: global convergence guarantees for training shallow neural networks. IEEE Journal Selected Areas in Information
Theory, 1:84-105, 2020.
[37] J. Pennington and P. Worah. Nonlinear random matrix theory for deep learning. NeurIPS, 2017.
[38] J. Pennington, S. S. Schoenholz, and S. Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. NeurlPS, 2017.
[39] Pennington, S. Schoenholz, and Ganguli. The emergence of spectral universality in deep networks. In AISTATS, 2018.
[40] S. Qiao, H. Wang, C. Liu, W. Shen, and A. Yuille. Micro-batch training with batch-channel normalization and weight standardization. arXiv: 1rXiv:1903.10520, 2019.
[41] T. Salismans and D. Kingma, Weight Normalization: A Simple Reparameterization to Acceler- ate Training of Deep Neural Networks. In NeurlPS, 2016.
[42] S. Santurkar, D. Tsipras, A. Ilyas, and A. Madry, How does batch normalization help optimiza- tion? In NewrIPS, 2018.
[43] A. M. Saxe, J. L. McClelland, and S. Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In ICLR, 2014.
[44] Z. Sun, M. Lin, X. Sun, Z. Tan, H. Li, and R. Jin. Mae-det: Revisiting maximum entropy principle in zero-shot nas for efficient object detection. ICML, 2022.
[45] D. Terjék and D. Gonzålez-Sānchezz arXiv:2205.135: 13507.
framework for overparameterized learning, 2022.
[46] L. Xiao, Y. Bahri, J. Dick-Dickstei, S. S. Schoenholz, and J. Pennington. Dynamical isometry and mean field theory of enns: How to train 10,000-layer vanilla convolutional neural networks. In ICML, 2018
[47] G. Yang. Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Archi- tecture are Gaussian Processes. In NeurlPS, 2019.
[48] G. Yang. Tensor Programs II: Neural Tangent Kernl for Any Architecture. arXiv:2006.14544 2020.
[49] G. Yang and S. S. Schoenholz. Mean Field Residual Networks: On the Edge of Chaos. In NeurlPS, 2017.
[50] G. Zhang, A. Botev, and Martens. Deep learning without shorteuts: Shaping the kernel with tailored rectifiers. In ICLR, 2022.
[51] D. Zou and Q Gu. An improved analysis of training over-parameterized deep neural networks. In NeurlPS. 2019.
[52] D. Zou, Y. Cao, D. Zhou, and Q Gu. Stochastic Gradient Descent Optimizes Over- wee-pparaeteriiedd Deep ReLU Networks. Machine Learning, 109:467-49 492, 2020.
12

---

Computational resources: Both the exploratory and final experiments for this paper were conducted using desktop machine with Nvidia RTX A6000 GPUs, for total running time of approximately 150 hours.
A Examples of MPS
All commonly used neural network layers fit into the framework of multilayer parameterised systems (MPS). Here we list the examples of most relevance to our work.
Example A.1. An affine layer aff: Rdd tdo x Id + g2 XN is given by the formula
aff(A,b, AX + b1%.
(16)
routine calculation shows that while
Jaff( A,, X) A Idw:
(17)
(A, (Ids, @ x Idd, @ In).
(18)
More generally, P:: RP + Rddx xd denotes any continuously differentiable map, then one obtains
a P P-parameterised affine layer
aff (efp(w,be X) == aff(P(w), = P(w)X t1
(19)
One has
Jaffp(w,b,X) = P(w) @ Idw
(20)
and, by the chain rule,
Daff X) = ((Ida, & x²) Ida, 3 1),,
(21)
where DP(w) RRdoNxp is the derivative of P at Common examples include c-weight normal- isation wn w) = (c+ )lom) ) w 41 and convolutions, which send convolutional kernels to associated Toeplitz matrices. We will also consider e-entry normalisation en(w) := (e - w²) w.
with operations applied entrywise.
Example A.2. (parumeter-free) elementwise nonlinearity RRdox - R defined by continuously differentiable function Φ IR + R is given by applying & to every component of matrix X E dR Extension to the parameterised case straightforward.
Example A.3. A (parameter-free) batch normalisation (BN) layer bn do + R X is given by the formula
- E[X]
bn (X)
(22)
VC+o[X]
where >> is some fixed hyperparameter and EE and a denote the row-wise mean and standard devia- tion. The parameterised BN layer from [21], with scaling and bias parameters 7 and 3 respectively, is
given simply by postcomposition affdiag (7, 3, o bn with tlag-parameterised affine layer (Example A.I.
Example A.4. A residual block f R x Rdox - xd can be defined given any other layer (or composite thereof) g IR do Rd.x X by the formula
f(0. = 1X + X),
(23)
where / R + R4 xN is some linear transformation. In practice, / is frequently the identity map 20) our main theorem will concern the case where / has all singular values equal to I.
B Proofs
Proof of Theurem 2.4
F) DF, we compute: 2 = (DF
Using the fact that DE = (Dy
(VV.EE10))DDEEOODPFO)))T7X 2 X(DEFO)))V>(((()))
2 (X(DF(()) (7((0)) - ((((1))
13

---

where the first inequality follows from the standard estimate (v. AATA) 2 Amin (AA7) [| and the final inequality follows from the fact that y p-PP over the set {F(() :0 E ].
Our proof of Proposition requires the following standard lemma.
Lemma B.1. Let {gi RP mm } be a family of malrix-valued functions. If, with respect
some submulippiiaative matrix norm, each gi is bounded by by and Lipschitz with constant G2 on
set S C RR, then their pointwise matrix product + II gi(0) is also bounded and Lipschitz on S.
with bound I by and Lipschitz constant 2x Ci (11 bz).
Proof of Lemma B.
We prove the lemma by induction. When n 2, adding and subtracting a copy
of gi (0') and using the triangle inequality implies that || (0) 9192 (0') is bounded by
1| (02 (0) g2(0"))l + (1 (0) 91 (0' (0))))2(( ())))))22)))) (0')
Applying submultiplicativity of the matrix norm and the bounds provided by the b, and gives
(0) 9192 (0") (bi02 b2c1 1|0 1'|l-
Now suppose we have the result for n = k. Writing h++1 9: as k+1
9s and applying the above
argument, the induction hypothesis tells us that + 9s is indeed bounded by [ b, and Lipschitz with Lipschitz constant E/= C2 ([1 by). The result follows.
Proof of Proposition 4.3
By Proposition
4.2 it suffices to show that for each 1 < S L, the function
- II Jf, 1= 5=1+1
(24)
bounded and Lipschitz on S. To show this, we must first prove that each map θ+ fe, X) is bounded and Lipschitz on S. This we prove by induction.
By hypothesis, 0 (0, X) X0), is bounded and Lipschitz S. Suppose now that for
j > one has 0 A fe, (0, X) bounded and Lipschitz on Then the range of S + fe)(0, is bounded subset of Rd, xN By hypothesis on fj. it then follows that 0 + fzs+1 = f, fe,, X)) is bounded and Lipschitz on S.
The hypothesis on the J and Díj now implies that the maps 0+ Jf (0,)
j < L, and 0 + fi (6), [0, x)) are all bounded and Lipschitz on S. In partieular, as a product of bounded and Lipschitz functions, the map given Equation (24) is also bounded and Lipschitz on S. Therefore DF is bounded and Lipschitz on S.
Proof of Corollary 4.4 By hypothesis, F(S) is a bounded subset of Rd,.N,, Continuity of y then implies that (S) bounded subset of IR, so that F(S) is contained in sublevel set of y. The result now follows from the hypotheses.
To prove Theorem 4.5 it will be convenient to recall some tensor calculus. If R"1 + R Xma
matrix- matrix-valued, differentiable function of a matrix-valued variable, its derivative DJ can be whose components are given by
regarded as map Xna
xn2 - Rm,
0f ax
DJ D
(x),
X E 1
where 1 < fa < Ma and 1 1 ja < na are the indices, a 1,2. It is easily deduced from the chain rule of ordinary calculus that if f Raixm + Rmx xm2 and g Rmixm - R4xx xl2 are differentiable, then y o f is differentiable with derivative (Dg o f) DJ R - R4 x1xxn, Xn2, where here denotes contraction over the my x m2 indices. The following lemmata then follow from routine calculation.
14

---

Lemma B.2. Let bn RAXN - BaxN be an e-batchnorm layer. Then one can write bn = m, where v, m : RaxN Id are given respectively by
v(Y)= = (Ne+ + || )
(25)
1
m(X) = X N
X
(26)
One has
0uj 0y
82 C.VNN(Ne 11b0113)- (0) (Ne + 11u'11))~
(27)
and
8 Oy dyy
= =6,6 VN 11) x
(3(Ne + V,,
(6/ 8nv} + 8%,5))
(28)
with
dm
8) (8) N-
(29)
Oxf
and all second derivatives of m being zero. Lemma B.3. Let wn 18 xd 1d xdo be an e-weight normalised parameterisation (Example
A.1
Then one has
Own' Owf
5% (1ll)(113) 2 (0) (e + 1
(30)
and
Own)
=6/5 (c 1| 111)--xx x
Owi Ow
x (3(e + ( whwff wot
(6) + 8/,0 + 8 w()).
(31)
Similarly, if en Rddxxoo + Rdh xdo is an e-entry-normalised parameterissaion, then
den Ouf
of (w
(32)
and
den'
5% 57 02 3c(c + (w BB]
(33)
Own Ow
Proof of Theorem 4.5 (1) follows from continuity the nonlinearity and its derivative, implying boundedness of both over bounded sets in _dxN
(2) and (3) follow from similar argument the following argument for batch norm, which we give following Lemma B.2 Specifically, for the composite f := bn aff IR xdo x Rd4 X - d
x
defined by an e-BN layer and an affine layer, we will prove that over any set B C do consisting of matrices X whose covariance matrix is nondegenerate, one has f, DJ and Jʃ all globally bounded and Lipschitz. Indeed, (Equation (25) clearly globally bounded, while De (Fquation (27) is
globally bounded, decaying like ||Y I out to infinity, and 2 (Equation (88 is globally bounded, decaying like || out to infinity. Consequently,
bn aff (m o aff),
D(bn aff') (Ju (Juo aff) (Jm aff) Daff, (bn aff) (Jvomoaf) aff) (Jm aff) Jaff,
15

---

and similarly the derivatives of (bn aff) and J [bnn o aft) are all globally bounded over R x x B. The hypothesis that B consist of matrices with nondegenerate covariance matrix is needed here aff decays like || A(X E[X] F out to infinity, the row-norm ||( [[(A(X
because while Jr (X-XXX = (A+)?) I
Cov(X) can only be guaranteed to increase with A if Cov(X) is nondegenerate. Thus, for instance, without the nondegeneracy hypothesis on Cov(X), A + J(bn (A, grows unbounded like (a, = A & I in any direction of degeneracy of (ov( Nonetheless, with the nondegenerate covariance assumption on elements of B, bn o aff satisfies the hypotheses of Proposition 4.3 over R4 xdo x B.
(2) and (3) now follow from essentially the same boundedness arguments as for batch norm, using Lemma B.3 in the place of Lemma B.2 However, since the row norms in this case are always defined by the usual Euclidean inner product row-vectors, opposed to the possibly degenerate inner product coming from the covariance matrix of the input vectors, one does not require any hypotheses aside from boundedness the set B. Thus entry- and weight- normal-eorm affine layers satisfy the hypotheses of Proposition 4.3
Finally, (5) follows from the above arguments. More specifically, if TRP x Rd RdxN is any
composite of layers of the above form, then g satisfies the hypotheses of Proposition 4.3 Consequently, so too does the residual block f(0, X) == X + g X), for which Jf X) = Id. x Idy + Jg( (0, X)
and (0 = XX)
Proof of Proposition 4.6 In the notation of Proposition 4.2, the product DF) is the sum of the positive-senne seniiee-semi matrices Do. (()) De, F(Ø)" Therefore ((DF(O) 2 E, F(D).. The result now follows from the inequality X(AB) 2 (()) applied inductively using Equation (I). Note that X(AB) 2 A(A)((B) is either trivial if one or both of A and B have more rows than columns (in which case the right hand side is zero), and follows from the well-known inequality a (AB) 2 (A)o for the smallest singular values if both A and B have at least as many columns as rows.
Theorem 4.7 follows from the following two lemmata.
Lemma B. Let g : Rd x RdoxN + Rd XN be a layer for which there exists 8 > such that [[] X)l22 < (1 for all I and X. Let : Rd N - 1d be linear map whose singular values are all equal to I. Then the residual block [(0, X)= = IX + g(0, X) has o (JS(0, (0,000 X)) >
for all 0 and X.
Proof. Observe that
(f = Idy + Jg(,
(34)
The result then follows from Weyl's inequality: all singular values of I @ Idy are equal to 1, that
a (JS(O, x)) 2 1 (1 X) 8
for all 0 and X.
Lemma B.5, Let P: R + Rd x be a parameterisation. Then
a (Daffp((, (DP())
(35)
for all w E IR and X E RdxxN
Proof. Follows from Equation 21 and the inequality o(AB) 2 (A))o(B).
Proof of Theorem 4.7 Hypothesis in Theorem 4.7 says that the residual branches of the ft, 1 2 2, > 0 for all / 2 2. By the
satisfy the hypotheses of Lemma B.4 so that
assumption that di-1 2 d, this means that (O) f(( X (J fe((0, X))) >
O. On the other hand, hypothesis 2 together with Lemma B.5 implies that (0,,
(D X))² > 0. The result now follows from Proposition 4.6
16

---

Proof of Theorem 5.7 By Theorem 4.5 all layers satisfy the Hypotheses of Proposition 4.3 and so by Corollary 4.4 the associated loss function is globally Lipschitz, with Lipschitz constant some B > O. Take y > 0 to be any number smaller than 2 thus the loss can be guaranteed to be decreasing with every gradient descent step.
We now show that the network satisfies the hypotheses of Theorem 4.7 The dimension constraints in item (1) are encoded directly into the definition of the network, while the operator-norm of each of the residual branches, as products of P(w) and D& matrices, are globally bounded by 1 by our hypotheses on these factors. For item (2), our data matrix full-rank since it consists of linearly independent data, while by definition we have everywhere full-rank since e-entry-normaliin normalisation is diffeomorphism onto its image for any Its hypotheses being satisfied by our
dido with Df1 = Daffen being
residual network, Theorem 4.7 implies the paramtter-function map F associated to {fi and X satisfies X(DF(O) o (DF(0))² > 0 for all parameters 0. There are now two cases to consider.
In the first case, the gradient descent trajectory never leaves some ball of finite radius in R4 xdo the parameter space for the first layer. In any such ball, recalling that the first layer's parameterisation is entry-normalisation (Example A.1 the smallest singular value
min σ (D (Den(w)) en(w)) ISiSUSSISA (E + (w))
(36)
of D ee(ww) is uniformly lower bounded by some positive constant. Thus by Lemmas B.S and B.4 the smallest singular value of DF also uniformly lower bounded by a positive constant in any such ball. It follows from Theorem 2.4 that the loss satisfies the Pł-inequality over such ball, so that gradient descent converges in this case at a linear rate to a global minimum.
The second and only other case that must be considered is when for each R >> O, there is some time for which the weight norm ||w/||| of the parameters in the first layer is greater than R for all t > T. That is, the parameter trajectory in the first layer is unbounded in time. In this case, inspection of Equation (36) reveals that the smallest singular value of DF cannot be uniformly bounded below by positive constant over all of parameter space. Theorem 2.4 then says that there is merely sequence (me )EN, with μr proportional to a (D en(w))), for which
4- < Ia ma)(Co - -E),
(37)
==
where a = 17(1 - -2)-'n) > 0. To guarantee convergence in this case, therefore, it suffices to show that 11 [1- - (4a)= = 0; equivalently, suffices to show that the infinite series
log(1 m(a))
(38)
diverges.
The terms of the series (38) form a sequence of negative numbers which converges to zero. Hence, for the series (38) to diverge, it is necessary that μ4 decrease sufficiently slowly with time. By the integral test, therefore, it suffices to find an integrable function m [to, oc) - R>o such that f 2 m(t) for each integer 2 to. for which the integral f. log(1 m())a) dt diverges.
We construct m by considering the worst possible case: where each gradient descent step in exactly the same direction going out to co, thereby decreasing a (D en(w) at the fastest possible rate. By applying an orthogonal-affine transformation to di we can assume without loss of generality that the algorithm is initialised at, and consistently steps the direction of, the first canonical basis vector en in di Specifically, letting 0 be the vector of parameters for all layers following the first and w E de the first layer parameters, for r E T2z1 we may assume that
Vall ( 0wg E(,, Je,,
(39)
SSee the supplementary material.
17

---

with (u)((0,re 2 0 for all (0,r). Let denote the convex function defined by the cost e (cf.
Equation (6), and let A(Ō, rei) denote the di do-dimensional row vector
L
(y((((, res)) Jf (fi, [(((
xx)).
(40)
1=2
Then, in this worst possible case, the single nonzero partial derivative defining the loss gradient with respect w at the point (6, r61) is given by
mmp 0m; - A(rrre)): (c+r2)) r2)
(41)
where rei) denotes the first component of the row vector A(O, re1) (cf. Equation (2T) By
Theorem 4.5 however, the magnitude of A(A, rei) can be globally upper bounded by some constant C. Thus
Cc
Ce
Ou ( re)) (e (2)
(42)
3
for all 0 a'and 2 1.
Let us therefore consider the Euler method, with step size n, applied over R21, starting from ro with respect to the vector field (r) = Cer 3, Labelling the iterates (rt)TeN. we claim that there exist constants 71 7/2 and a such that 0 < S 71 + 72(1 + 78)$ for all E N. Indeed, observe that the solution the flow equation r(() Cer(1) -3 is r(() (4Cet + 1) so the claim follows if can show that there exists a constant B such that [r; - -((t) < B for all integer t 2 0. However this follows from Theorem 10.6 of (17].
Now, since for each f, r, is an upper bound for the magnitude of the parameter vector wy E Rd see from Equation (36) that the smallest singular value a (Denww)) admits the lower bound
o (Dent (Den(wr)) (c+ (n 72(1 + 2))
(43)
for all t N. Clearly, (c+ + (Y1 + 72(1 12)+++))447 2)) O(t)). Hence there exist to > 0 and such that
r +
#4 N
(44)
for all integer 2 to- Then, setting m(l) = r7- ; the integral
tt ra
log(1 (og(1-m(tta)
log
dt
(45)
diverges. It follows that gradient descent converges - oo to a global minimum.
C Experimental details
For all our experiments, the data was standardised channel-wise using the channel-wise mean and standard deviation over the training set.
On CIFAR10/100, crop/horizontal flip data augmentation. We ran 10 trials over each of the learning rates 0.2, 0.1, 0.05 and 0.02. The only exception this is for CIFAR1O 10 with a learning rate of 0.2, where training diverged 6 our of 10 times on the original network, so we plotted only those trials where training did not diverge. Mean and standard deviation test accuracies, well averaged-over-final epoch loss values, are given in Tables
model were trained using SGD with batch size of 128 and random
and 2.
The plots at the optimal learning rate, 0.1 for CIFAR10 and 0.05 for CIFAR100, are in Figure 3 while we provide the plots for the other learning rates in Figures and
minimally modifying http:://gghubb.cooouuuuugu//u//u
18

---

Table 1: ResNet18 on CIFARIO
Original
Modified
Learning rate
Test accuracy
Final loss
Test accuracy
Final loss
0.20
48.14 19.95
1.3883 + 0.5503
62.71 + 6.14
0.9495 0.2150
0.10
91.64 + 0.24
0.0032 + 0.0002
91.42 + 0.61
0.0022 = 0.0002
0.05
91.22 + 0.25
0.0043 + 0.0003
91.14 0.25
0.0041 = 0.0001
0.02
89.50 + 0.32
0.0112 0.0004
88.94 + 0.35
0.0125 = 0.0004
Table 2: ResNet18 on CIFAR100
Original
Modified
Learning rate
Test accuracy
Final loss
Test accuracy
Final loss
0.20
69.67 + 0.58
0.0150 + 0.0005
70.07 + 0.53
0.0115 + 0.0005
0.10
70.05 + 0.43
0.0147 + 0.0004
70.87 0.42
0.0116 + 0.0003
0.05
70.04 + 0.48
0.0145 + 0.0003
70.34 + 0.56
0.0116 + 0.0003
0.02
69.75 + 0.56
0.0145 + 0.0003
70.13 + 0.55
0.0116 + 0.0004
10
orig.
10a
orig.
109
orig.
mod.
mod.
mod.
Loss
Loss
10-1
Loss
10
109
10-2
10-2
20
40
20
Epoch
Epoch
Epoch
(a) Ir 0.2
(b) Ir 0.05
(c) 0.02
Figure 4: Loss plots for ResNet18 on CIFARI0
orig.
orig. mod.
orig.
10a
mod.
10a
10a
mod.
Loss
Loss
10-1
10-1
10-1
10
10-2
10-2
20
40 Epoch
60
80
20
40
60
80
0
20
40
60
80
Epoch
Epoch
(a) Ir = 0.2
(b) Ir = 0.05
(c) Ir = 0.02
Figure Loss plots for ResNet18 on CIFAR100
19

---

Table 3: ResNet50 on ImageNet
Original
Modified
Learning rate
Test accuracy
Final loss
Test accuracy
Final loss
0.20
49.24 + 34.75
1.0285 + 0.0066
0.10
74.69 0.12
0.9201 0.0014
74.99 = 0.09
0.8949 0.0019
0.05
74.62 + 0.12
0.8563 = 0.0041
74.84 = 0.03
0.8420 = 0.0030
0.02
73.87 0.09
0.8690 0.0025
74.00 0.11
0.8441
0.0026
5
orig. 0.2
mod. 0.2
orig. 0.1
mod. 0.1
orig.
orig.
mod. 0.02
2
0
20
30
50
70
80
Epech
Figure 6: Loss for original and modified ResNet50 different learning rates on ImageNet. The modified architecture did not converge at the maximum learning rate of 0.2.
On ImageNet, the models were trained using the default Py PyTorch ImageNet example 1D with weight decay 1e and momentum of 0.9, batch size of 256, and random crop/horizontal flip data augmentation. See Table 3 for the validation accuracies, and Figure o for the plots of the training losses at different learning rates.
using SGD
20


Reviews:
[{"review_id": "DTv7EjXm1D", "reviewer": "Reviewer_kvh8", "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. ", "questions": "Please see above.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has following strengths:\n\n1. 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.\n\n2. The proposed theoretical framework may be useful for further theoretical studies on models with skip connections.\n\n3. 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.\n", "weaknesses": "The paper has following weaknesses:\n\n1. 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)?\n\n2. 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?\n\n3. 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their attentive reading of our submission.\n\n*Some of the assumptions…* We agree that the assumptions are strong, although they are not exceptionally strong in comparison to other theoretical works. It is also not entirely true that models usually have an increasing number of neurons: we point to ResNets as a counterexample, which, after the very first layer, have a non-increasing number of neurons in deeper layers. The cost functions that are most frequently used in practice are the square cost and the cross entropy. Since both of these are convex we do not believe this worsens the practicality of our results.\n\n*Instead of using a deterministic map…* We did not think of trying orthogonal initialisation on the 1x1 convolutions. However based on our theory, we would predict a similar boost in training speed to what we see with our proposed modification, as we would expect it to have a similar affect on the singular values of the model, at least at initialisation. We used average pool skip connections because they aligned closely with our Hypothesis 6.1.\n\n*There are a few important related works…* Thank you very much for the recommendations. We certainly agree that these related works are relevant and will include citation of them and some discussion with the extra space provided if our paper is accepted. \n"}, {"review_id": "ASIXoMQB6A", "reviewer": "Reviewer_aLTj", "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.", "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?\n\nIs it the case that convergence might be sub-linear?  If so are there any guarantees on the speed of convergence?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "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.\n\nThe proof also seems to sacrifice linear convergence, which makes the proof slightly less interesting.  Again, maybe I am wrong about this.\n\nMore 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.\n\nI 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).\n\nThis 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our work and for their kind words.\n\n*Although technically elegant…* The reviewer is correct on the point that our proof technique only works in the strictly overparameterised regime. However, the reviewer is incorrect that most people do not work in this regime. This regime is common to all theoretical works on this topic that we are aware of, as well as being common to many practical settings such as image classification. All previous theoretical works also require at least one layer where the number of parameters is of at least the order of the number of training samples. There are mathematical reasons for thinking that overparameterisation is necessary for the ease of convergence of gradient descent on deep neural networks (see our response to your Question below). \n\n*The proof also seems to sacrifice linear convergence…* For strongly convex cost functions such as the square cost, our Theorem is associated (by the usual arguments for PL functions) with a linear convergence rate. It is true, however, that for non-strongly convex cost functions (such as the cross-entropy cost), linear convergence is sacrificed. However, this is to be expected since even in convex optimisation, the best-known convergence rate for fixed steps-size gradient descent on non-strongly convex objectives is sublinear: only O(1/T), with T denoting the number of iterations [1].\n\n*I still need some convincing that the direction of research is leading somewhere…* We are sympathetic with your concerns: similar concerns of our own on the limitations of existing theory motivated this work. However, it is important when evaluating the direction of a line of research to keep in mind where the line of research originated.\nIt seems to us that your concerns could be directed with even greater force against the theoretical papers on the optimisation of deep nets to which our own paper is responding, many of which are published in NeurIPS, ICML and conferences of similar calibre. As a rule, these works all fall short of capturing deep learning in practice, and as outlined in Lines 25-58 the purpose of our paper is to address some of these shortcomings and bring theory closer to practice. As stated in Lines 43-58, our paper is successful in this aim. We believe it will be of interest to other theoreticians in the pursuit of more practical assumptions as well as practitioners in the principled design of architectures. Insofar as theory papers still have a place at conferences like NeurIPS, we believe that our success in our aims justifies the publication of our paper.\n\n*I found the empirical part of the paper slightly underwhelming…* We agree that the improvements were quantitatively small, but it must be remembered that we only changed four layers in each case, and these small modifications were made to architectures which are already known to be extremely easy to train (ResNets). Although the changes are small, to our knowledge no other paper in the deep learning optimisation theory literature (i.e. literature which has been concerned with proving convergence theorems) has been able to successfully make predictions about interventions on practical architectures.\nWe tried to rule out other possible explanations as much as possible with our experiments, for instance by running them at multiple learning rates, and by computing all relevant mediating quantities such as singular value histograms where possible (MNIST) and showing they behaved as predicted. However, the impossibility of ruling out all other explanations is a perennial problem in science. An experiment can never prove a hypothesis true: it can only ever prove a hypothesis false.\n\n*This was by far the hardest paper I had to review…* We are sincerely grateful for your time. We know it is a difficult paper.\n\n*Is the regime where there are more training data…* We would say that this regime is mathematically different. When there are a lesser number of parameters than training data, the system of equations one is trying to solve is overdetermined (i.e. has more constraints than degrees of freedom). Such systems generically have few if any exact solutions, and whatever solutions exist tend to be isolated in locally convex regions of parameter space. In contrast, when there are many more parameters than training data the system is underdetermined (i.e. has more degrees of freedom than constraints), and typically admits infinitely many solutions occurring in large, connected regions. We recommend Figure 1 of [2] for an intuitive picture of this. Deep learning often occurs in the overparameterised regime in practice, and this overparameterisation is universally used to account for ease of optimisation in theory.\n\n*Is it the case that convergence might be sub-linear?* Our theorem gives linear convergence for the square cost, just as is achieved in comparable works. For the cross-entropy cost specifically, the convergence is indeed strictly sublinear, as is common with gradient descent on non-strongly convex objectives. We do not presently have a precise convergence rate: while such a rate would in principle be computable, since the assumptions of the theoretical part are impractical (albeit no more so than other theoretical works in this area) we felt that our time was better spent setting ourselves apart further from these other works by focussing on the more practical implications of our ideas, rather than on additional theoretical quantification.\n\n[1] Dimitri P. Bertsekas. *Convex optimization algorithms.* 2015.\n\n[2] Liu et al. *Loss landscapes and optimization in over-parameterized non-linear systems and neural networks*, arXiv:2003.00307\n\n"}, {"review_id": "kp8diozVt2", "reviewer": "Reviewer_9ZMW", "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.\nInterestingly 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.", "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?", "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.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 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.\n\nAlso 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).\n", "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. \nRecall 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).\n\nClarity: To improve the impact the work would benefit from more accessible presentation. I leave it to authors to consider that for next iteration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their polite critique.\n\nWe must first clear up what appear to be some misapprehensions in the reviewer’s interpretation of our work that are apparent from the Summary and Strengths section.\n\n1.\tThe reviewer seems to be under the impression that we are applying NTK theory for our convergence proof. What is typically understood by “NTK theory” is the theory developed in [1], wherein it is shown that for MLPs, a certain matrix-valued function of the parameters (which, confusingly, has become known in the community as the “tangent kernel”, perhaps contributing to the reviewer's misunderstanding), converges in the infinite-width limit to a constant matrix (called the “Neural Tangent Kernel” or NTK, to which the reviewer seems to be referring) at random initialisation. **We do not invoke this theory at any time in our paper.** First, our theory concerns much more general architectures than only MLPs. Moreover, our theory does not require infinite width, nor does it require this matrix valued function (the “tangent kernel”, as opposed to the *constant* NTK) be constant (i.e. **we do not work in the NTK regime**, as the reviewer seems to think). In fact, much of the theoretical work in our paper is devoted to accounting for the variation of the smallest singular value of this matrix-valued function as training proceeds. In particular, the globality of the result does not follow from NTK theory as claimed by the reviewer.\n\n2.\tOn a related note, the reviewer claims that we establish a PL lower bound on the gradient norm. This again is not accurate: as we state at Lines 107-110, when working with general cost functions such as the cross-entropy cost, a PL lower bound (in the sense of a uniform lower bound) is impossible. The best we can do is show that the quotient $\\|\\nabla\\ell\\|^2/\\ell$ (to which the PL inequality gives a uniform lower bound) never vanishes. In fact, a good deal of the proof of our main theorem is spent showing how convergence to a global minimum is possible despite not having access to a uniform PL lower bound. Ours is the first work to propose such a technique.\n\nNow onto the Weaknesses:\n\n*Impact: From my perspective…* The critiques made regarding the strong assumptions could be made at least as forcefully about all other papers in the DL optimisation theory literature, over which our paper in fact makes several improvements as outlined in Lines 27-58. Many of these papers are justifiably published in outlets of similar calibre to NeurIPS, and despite strong assumptions have thousands of citations between them. It is inaccurate to say that they have had low impact. To say that our paper should be rejected based on strong assumptions alone is to say that NeurIPS shouldn’t be accepting DL optimisation theory papers at all, which we believe would be a great disservice to the field.\n\n*Recall that regularisation of skip connections have been reported…* We make no claim to be the first to have studied the effects of skip connections generally, however we do believe that we are the first to have made the link between the inclusion of skip connections and improvements to loss regularity *in the precise sense* of a larger value of $\\|\\nabla\\ell\\|^2 / \\ell$. The Hauser et al paper brought up by the reviewer, while very interesting and known to us, studies skip connections from a quite different perspective which we did not believe was relevant to our work. It was for this reason that we did not cite it. If the reviewer is alleging lack of novelty then we would very much like to know what papers we have missed that are making genuinely similar claims to our own.\n\n*Q1: The paper strives to establish new toolkit for a convergence theory in DL…* Beyond the results themselves, we believe our work has two primary contributions which will be of use to others working in DL convergence theory.\n\n1.\tThe framework itself. Our paper is the first we are aware of which abstracts from the any specific architectural choices, as considered in previous works, to give a general framework capable of treating all network layers on a common theoretical footing. Our framework is modular in reducing important properties of the total loss landscape to properties of the individual layers, where conditions are more easily checked, and is the first framework which allows this. Our main theorem is proof of concept of this general approach which we believe will be necessary in moving DL optimisation theory beyond the MLP examples typically considered and into more practical settings. We believe this modular approach may prove useful when trying to incorporate contributions from all layers into the estimation of PL-type bounds, which we stated as an open problem in our Discussion.\n\n2.\tOur new proof technique removes the need for a uniform PL bound. Prior to our work, all works on the optimisation of deep nets have required sufficient conditions for the optimisation trajectory to stay close to initialisation, so that a uniform PL bound computed at initialisation can be used to quantify loss decrease throughout training. These assumptions are violated for large learning rate schemes used in practice and mentioned in our Discussion. In contrast, our new proof technique is the first which permits proof of convergence without such a uniform PL bound and without insisting that the optimisation trajectory stay close to initialisation. As the only technique we are aware of that can handle such weak assumptions, we believe that it may be of utility in extending DL optimisation theory to more practical training regimes involving edge of stability.\n\nShould the paper be accepted, we will include this discussion in the extra space provided for the final iteration.\n\n\n[1] Jacot et al, Neural Tangent Kernel: Convergence and Generalization in Deep Neural Networks, NeuIPS 2018\n"}, {"review_id": "UuiO5il2NF", "reviewer": "Reviewer_LNGS", "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.", "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?\n- 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.\n- 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.\n\n**Update: after clarifications in the rebuttal, additional experiments, and reading the other reviews, I am increasing my score to 7**", "limitations": "Please see weaknesses, though the authors are quite fair about the limitations of their work and also future directions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well motivated; it address an important question (that of bridging the gap between theory and practice in deep learning optimisation)\n- The paper is well written and places itself clearly and fairly within the existing literature (in section 3)\n- 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.\n- 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).\n- 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.\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their attentive and detailed critique.\n\n*I'm not sure the extent to which the theoretical bounds…* You’re correct that the theoretical bounds are not practical. Thank you though for recognising that this is not a unique problem with our work, and is common to virtually all works in this area so far, many of which have been published in at venues such as NeurIPS and ICML.\n\n*I'm not sure if the statement in section 6…* We should have been clearer in our wording here. The “regularising effect” to which we are referring in Lines 138-146 is of a different kind to the “loss regularity” we refer to in Section 6. Specifically, by “loss regularity” in Section 6, we are referring precisely to a larger value of $\\|\\nabla\\ell\\|^2 / \\ell$ (i.e. a larger PL coefficient), which therefore relates directly to optimisation theory and convergence speed. While the other works cited in Lines 138-146 study “regularising” effects of skip connections, they do not make the specific connection to loss regularity in the form of a larger PL coefficient that we do. In particular, to our knowledge no other works have yet observed the improved training speed that we predict (and observe empirically) based on this better PL regularity. We will change our wording in Lines 138-146, as well as in Section 6, to clear up this confusion.\n\n*Moreover, as far as I understand the theoretical arguments in Theorems 4.7 and 5.1…* Your understanding of the argument for Theorem 4.7 is essentially correct, and we agree that the argument here is relatively simple. However the same argument does not apply in Theorem 5.1. Theorem 5.1 already assumes that one has a positive PL coefficient everywhere (which the argument in Theorem 4.7 gives), and then proves that convergence to a global minimum is still possible even when this PL coefficient is not uniformly bounded below by a positive constant (i.e. is not a PL constant), and decays to zero as training progresses. The argument for Theorem 5.1 is significantly more involved, requiring a number of estimates on the rate of decay of the PL coefficient relative to the rate of growth in parameter norm as the trajectory tends towards a global optimum at infinity. It turns out that in order to get convergence to this optimum, it is necessary that a certain infinite series diverges. We are able to show that the PL coefficient goes to zero just slowly enough that this infinite series does indeed diverge, and asymptotic convergence of training to a global optimum is assured. The full proof can be found in the appendix.\n\n*The experimental results seem a bit thin…* To alleviate your concern, we have run the same learning rate sweep for ImageNet (to the extent our computational resources and time constraints allowed), showing that the claimed convergence improvements indeed holds across different learning rates where convergence is possible at all. We will work on having a more complete sweep done for the final version, should our paper be accepted. Please note also that we have tested networks of different depths: we used six layer networks on MNIST, ResNet18 on CIFAR and ResNet50 on ImageNet, and we used standard training schemes commonly thought of as close to optimal. Since our theory only concerns simple gradient methods, we feel that adaptive methods such as Adam are outside the scope of predictions we can reasonably make. Moreover, our Hypothesis 6.1 cannot be applied to PostAct ResNet architectures due to the presence of an additional batch norm in the skip connection. Our hypothesis could be generalised to cover this, but such a generalisation would be out of the scope of this work.\n\n*I think the Deep Kernel Shaping recent line of work…* We agree, these works are certainly relevant. We will cite them in the next version of our paper.\n\n*Can the authors comment on the fact…* In order for us to be able to guarantee Lipschitz gradients and positive PL coefficient globally, it was necessary for us to assume that all weights were normalised. One consequence of this is that the outputs of the network are bounded functions of parameters for any given training set. Restricted to this bounded set of possible outputs, the cross-entropy cost attains its global minimum at points on the boundary of this set. In particular, the global minima of cross-entropy on this bounded set are not zero. The preimages of these boundary points are always points at infinity in parameter space due to the nature of normalisation formulas: the function $x\\mapsto x/\\sqrt{\\epsilon + x^2}$ is bounded, taking values in the interval $[-1,1]$, with the extreme values 1 and -1 only being attained at $x = \\pm\\infty$ respectively.\n\n*Can the authors clarify what they mean by 'I is an average pool'…* In PyTorch code, this average pool is just an nn.AvgPool2d, whose filter size and stride are both equal to the stride of the corresponding 1x1 convolution. We thus pool only over a fixed filter size. We will include more details in the next iteration of the paper.\n\nWe hope we have been able to adequately address your concerns in the Weaknesses section. \n"}]

Author rebuttal:
We refer the reviewers to the attached PDF for plots of our ImageNet experiment run at different learning rates, as requested by reviewer LNGS. Note that every trial we did of the modified network with the largest learning rate diverged. This is not surprising, given that it has been observed previously that adding skip connections increases the curvature of the loss [1]. At the other end, we see the same improvements at a learning rate of 0.05 as we predict by theory and as we observe in the 0.1 case already present in the paper. We were prevented from doing additional learning rates by time and computation constraints, and will do a more complete analysis in time for the final version if our paper is accepted.

[1] Ghorbani et al *An Investigation into Neural Net Optimization via Hessian Eigenvalue Density*, ICML 2019.

Meta-review: This paper explores how normalized residual networks (potentially obtained via batch normalization and skip connections) help with optimizing deep neural networks. The authors make strong claims under specific assumptions, saying they have the first proof of convergence for training a particular class of DNNs.

All reviewers agree that the paper is analytically strong. One reviewer questions its impact, but I think introducing new training strategies and strong hypothesis is still a valid methodology. My main concern is how well the experiments back up the theory. The authors claim to be the first to prove convergence in DNN training, so they should really confirm that their optimal solution is unique and works as expected in practice. The current experiments suggest a relation to a state-of-the-art setting, which is not enough. The final accuracy obtain would not be such a big matter as it would really allow a reader to understand in which regime the theory stated in this work applies.

I would like the authors to incorporate this point, yet this despite this issue, I still recommend accepting this paper.
Decision: Accept (poster)