Model Architecture Controls Gradient Descent Dynamics: A Combinatorial Path-Based Formula
Authors: Xin Zhou
Newsha Ardalani
Venue:  (2020)

Abstract: Recently, there has been a growing interest in automatically exploring neural network architecture design space with the goal of finding an architecture that improves performance (characterized as improved accuracy, speed of training, or resource requirements). However, our theoretical understanding of how model architecture affects performance or accuracy is limited. In this paper, we study the impact of model architecture on the speed of training in the context of gradient descent optimization. We model gradient descent as a first-order ODE and use ODE's coefficient matrix H to characterize the convergence rate. We introduce a simple analysis technique that enumerates H in terms of all possible ``paths'' in the network. 
 We show that changes in model architecture parameters reflect as changes in the number of paths and the properties of each path, which jointly control the speed of convergence. We believe our analysis technique is useful in reasoning about more complex model architecture modifications.

Under review as a conference paper at ICLR 2020
MODEL ARCHITECTURE CONTROLS GRADIENT DE- SCENT DYNAMICS: A COMBINATORIAL PATH-BASED FORMULA
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, there has been a growing interest in automatically exploring neural network architecture design space with the goal of finding architecture that improves performance (characterized as improved accuracy, speed of training, or resource requirements). However, our theoretical understanding of how model architecture affects performance or accuracy is limited. In this paper, we study the impact of model architecture the speed of training in the context of gradient descent optimization. We use the ideas from prior work that shows gradient descent be modeled as first-order ODE and use ODE's coefficient matrix H to characterize the convergence rate. We introduce a simple analysis technique that enumerates H/ in terms of all possible "paths" in the network. We show that changes in model architecture parameters reflect as changes in the number of paths and the properties of each path, which jointly control the speed of convergence. We believe our analysis technique is useful in reasoning about more complex model architecture modifications.
INTRODUCTION
Gradient descent and its variants are the cornerstones of deep learning. The theoretical properties of gradient descent have been widely studied the literature; study of the convergence bounds and
guarantees 6 12
15 13, the characterization of the local geometry of stationary points [21
10
19
25
30
23
13 exploration of better algorithms to optimize the descent process 28
16
33
are just a few example of active research areas in this domain. Another major research area is the exploration of network architecture and its impact on performance. In recent years, network architecture search and design have shown major performance boosts in various aspects of deep 34].
learning [3 35 18
Recent thcoretical results trying to relate model architecture and gradient descent properties. It has been shown that over- paee-paamtttizztioon in width guarantees convergence in deep neural network ([5). It has also been shown that increasing depth has impact similar to adding momentum optimization and adaptive learning rate to the objective function 4..
The gradient descent process the continuous-time limit, in the form of x(() = (i)(((). In this paper, we study the properties of the coefficient matrix (t), which governs the dynamics of the gradient descent. Specifically, we formulate (1) in terms of all possible paths in the network. This representation powerful as it enables us analyze the gradient behavior symbolically and abstracts away the unnecessary bookkeeping of derivatives and weights. Specifically, we use this representation to explore the followings. (1) We study the impact of width on convergence. Using a simple path counting argument, we show that Ht) is sum of m i.i.d. terms where m is dictated by the width of the network. This has been implied in the work of Simon Du, et al. [12] for the special case a 2-layer RELUtactivated network. We contrast the ease of arriving at such conclusions using our representation against methods used in previous work 212 15 B 6 (2) We study the impact of depth convergence. While prior work [3] established the relationship between momentum and depth, we show a direct relationship between depth-induced induced momentum and the scale of the output value. We also discuss how depth-induced momentum is different than explicit momentum.
be described by system of first-order differential equations in

---

Under review as a conference paper at ICLR 2020
(3) We argue why the number of paths is more important than the number of nodes in network.
RELATED WORK
Related work can be categorized into three groups which we will explain in detail below. In general, the common theme across previous works is to show that if some conditions, such bound on models' width or depth or assumptions on geometrical properties of the loss landscape are met, gradient descent its variance converges to global minimum.
Landscape Analysis Researchers have extensively studied the properties of error surface in linear neural network (110 (1)) and have proved convergence to global minimum for non-convex opti- mizations if error surface shows certain properties, such as all saddle points to be strict (i.e. there exists negative curvature) [IT 19 25 30 24
23 13) However, it has been shown that the striet saddle property is not guaranteed for deep neural networks.
Width Analysis A number of recent work have characterized minimum width that guarantees convergence in terms of model architecture parameters and input data. We on the other hand study how convergence rate varies with width. Examples of finding width bounds include [55 where it has been shown that for 2-layer ReLU-activated neural network with squared loss, as long as every hidden layer wide enough, gradient descent converges to a global minimum at linear rate. In [14 I. it is extended to fully connected linear networks and ResNets. Du et. al. 12] has also generalized this work to an L-layer fully connected linear neural network and shows the convergence rate as a function of depth, output dimension and least eigenvalue of the Gram matrix for large enough hidden layers. Ardalani et. al. [2] have shown empirically that for a wide range of RNN applications, increasing width will reduce the number of steps to minimum validation loss. Neural tangent kernel [2 studies convergence in the infinite width limit.
Depth Analysis Bartlett et al. 6 have proven for a deep linear neural network with isotropic input and identity initialization that the number of steps to e-proximity of the best answer is polynomial in the number of layers. Neural ODE studies the convergence in the infinite depth limit (27 20 17). Work that motivated our depth analysis are [3, 4]. They have shown that paraaattttttttiioonnn accelerate training with these extra restrictions: (1) linear neural network with (2) fully-connected layers and (3) "balanced" initialization where (4) dimensions of hidden layers are at least the minimum of the input and output dimensions. We contribute in the following ways. We characterize depth- induced momentum in value space with an inequality and compare with explicit gradient descent momentum. We observe that momentum directly impacted by value of the sub-network. We lift the structure and activation restrictions.
NOTATIONS AND CONVENTIONS
Matrix entries are denoted with row and column indices, for instance H = (Hiz) is a matrix with entries Hij- When H is diagonalizable, matrix W, Wi;;)) and W(: denote the row vector in the i-th row and the column vector in the j-th column, respectively. Write Σwew for summing over all elements of W. We use pairs {X,, v1), s sis N to represent labeled data where X, is input and y; is the output. We write Ti, for the k-th component of X,. We denote loss by L. We work with feed-forward neural networks, which sometimes denote abstractly by a function f. or f(w, 2)) as function of input and weights w. We denote network weights individually by uz, Predictions are denoted by u, = f(w,X,) X,) 1 Isis S N. The prediction on all inputs is denoted by the vector 1p loss is defined as E u.)" for even integers p 2 2. We use angle brackets to denote inner products. i.c. (7, 2 = u,W;; represents inner product of two vectors. i.i.d. random variables stands for independent and identically distributed random variables. ODE stands for ordinary differential equations. NN stands for neural networks. GD stands for gradient descent.
denote by Amin(H) its smallest eigenvalue. For
4 BACKGROUND
We build upon prior work [15 which take gradient descent to continuous time limit and derive the Gram-matrix H governing gradient descent dynamics. In this section, we give a quick derivation for Equation (4) for completeness.
2

---

Under review as a conference paper at ICLR 2020
Convergence rate be characterized the rate of change in loss during the training process. If steps are infinitesimally small, the rate of change in loss can be characterized as:
dL
N
àL
du,
(1)
dt
Du: dt
Where (t) = f(w(t), X;) is the prediction on input X, at time t. For simplicity we focus on the dynamics of duj which can be expanded as follows: at
du;
m
Ou: Owr
dw,
m
Ous Owl
NV
ØL
Ouj Ow,
11
dt
dt
Oug
j=1
m
Ou, Juj 0L
Ou, oug
aL Ouz
Ow, Ow,,
Jug"
11
Sw Ow.
We use the definition of gradient descent and chain rule to derive the equation above. Gradient descent at infinitesimal small step is defined by:
dw, OL Ow;
aL
Oug
(3)
dt
Ouj
Ows
Observe that ØL Du
a column vector. Hence, we define Hij as:
m Ou: Ouj
Hij
(4)
ow, Ow,
Then simplify equation
in vector form
du
8L 80L
di
nH
(5)
dux
9L ZuN
Assuming is le loss, equation (5) simplifies to the following. This result will hold up to a constant for other lp losses (see Appendix A
du nH u.
dt
d(y u) du
dt dt - H (y- - u)
Notice that this puts y - u in a system differential equations whose single variable analogue is:
df(1) hf(()
The above equation's 's solution is:
f(t) = ch = co(1 - E)¹
when 0, hh and let a {. & governs the convergence rate Equation 9 In the actual system of equations 7., & will be determined by the minimum eigenvalue of H (t denoted Amin (1)).
MAIN IDEA: CHARACTERIZING H IN TERMS OF NETWORK PATHS
In order to state the path decomposition formula, we first establish some notations.
We denote the neural network abstractly with function f(X).

---

Under review as a conference paper at ICLR 2020
For any neural network, view the underlying network as directed graph where edges are in the backward propagation direction.
We define path p. as series of connected nodes and directed edges. We define an output path as path that starts with the output node. We denote the length of p by (p)).
We index the nodes as follows. Index the output node by O, the one after by 1, and so on. We denote the j-th node in the i-th path by pz.-
We allow different activation functions at nodes. We denote the activation function at ps by ds.
An example path that ends in input node may look like this:
Fn
Figure 1: Illustration of multilayer perceptron
The post-subnetwork at Wa is defined as the network formed by the subgraph rooted at the right vertex of w,, The pre-subnetwork at ws is defined the union of all output paths ending in Wa+ denoted by pre(ws).
For every input X,, we denote the activation value at the node after w, with f[wa](X;) (Xi). Note that this is equivalent to the value at the right vertex of w. once X; propagated through the post-subnetwork at W/..
We denote the local gradient wrt. input at node along the path p with T..
Given the pre-subnetwork at we write the explicit formula for du ow,
Ou: f[w.](X)
Σ
path_ gralggrrddinnttt (w. X,)
(10)
Ow,
pEpre(we)
where boell_gradient,oo (Ws, X;) is the gradient value along the path at the left vertex of ws. and can be expanded as follows using the chain rule:
path cecilgrrrdintt,, (w,,, X2) (rjWOrý, w1 ... - (1)))
(11)
refer to path gradient,, (W,, X,) PG, X;) for brevity from now on. Theorem 5.1. For a network f,
Hij = Σ ((oo)(())) ((o((x))(([((x))) [X,)(X,)
Σ pEpre(w)
PGp(w, X.))
(E PG,(w, x,)) pEpre(u))
(12)
which easily follows by substituting Equation (10) in Equation 4 In the of the paper, we will make many arguments most of which rely on the number of terms in this equation. Number of terms in Equation 12 is itself controlled by the number of paths in the pre-subnetworks at each weight.
Following examples provide some intuition.
Example 5.2. In this example, our network has structure as illustrated in Figure 2a The output node denoted with value one, indicating that the activation function at output layer an identity function. As shown in Figure[2h) there are only one path in each weight's 's pre-subnetwork. Therefore, there are only three terms in Equation|] 12 where euch summand of form PG,(W, X,) (w, X,). We refer to these terms as symmetrical pairs since both multipliers are representing the same path.
Example 5.3. A more complicated application of the formula can be found in Figure 2d There is one path in each of the following weights' presubnetwork: Wo, 20, W2.W3, and Ws. and three paths ws 's presubnetwork. Therefore, Equation 12 would have 5 + 32 14 sunmands, 8 of which are terms with symmetrical pairs and 6 are cross-terve induced by the paths in ws pre-subnetwork. In general, cross-terms will appear only if there happen if there are three or more number of layers in the network.
paths that share final edge which only
4

---

Under review as a conference paper at ICLR 2020
prolou)
prelin]
(a) Example 5.2
(c) Example 5.3
(b) Paths Example 5.2
pesting)
profog)
pro(as)
poije
(d) Paths Example 5.3
Figure 2: Path Decomposition Examples.
ARCHITECTURE IMPLICATIONS
6.1 CONVERGENCE RATE SCALES LINEARLY WITH WIDTH
In this Section, show that for sufficiently wide neural networks, convergence rate has linear relationship with the network's width. Results are drawn theoretically at time 0 assuming random i.i.d initialization. For these results to generalize across time, assume that H stays close to its initial we show empirical results that suggest this assumption is true. For the extreme case of infinitelywwin wide networks, has been shown that H constant throughout neural networks weights remain close to initialization, and so our argument holds true across training.
value. In the Appendices D and B
training [22]. Others [5] 15 have also shown that for sufficiently-
Proposition 6.1. For 2-layer neural network with hidden dimension m, the expected convergence rate scales linearly with m.
To demonstrate the simplicity and expressiveness of our approach, next we will discuss proofs with and without our approach.
Brute-force approach A 2-layer fully-connected linear neural network can be modeled as:
W11
Wid
21
u(X)
V x
-011
Um)
(13)
Wm1
Wmdd
where I..m and W mm. are the weights of the second and first layer, respectively and the input X is d-dimensional column vector. We begin the analysis with the simple case of 2-layer linear network where the network's width is one, i.e. m and u(X) = up (W(: 1), X).
Hi can be decomposed into two terms, partial derivatives with respect to weights of the first layer and partial derivatives with respect to weights the second layer.
Du, Ou, Hij Avn Ivo
Ou, du Ow dw
(W(;1), (W,1)),x o
X Xi,
(14)
WEW
For a more general case where the width m, we have:
H Σ t=1
(W(,)),x)) (W(.). + Σ X Xz,b
(15)
R=1
5

---

Under review as a conference paper at ICLR 2020
Adding non- non-linearity would make this equation more complex, which is the approach used in previous literature together with induction:
172
Hy
Xxx (W()),, ((W(s D. xz))
(16)
See Appendix [ for details of how we derive these equations. Since we assume all weights (Wys= v0) independent and identically distributed, the summands within Equations (15) and (16) are also independent and identically distributed. This indicates that Hij is composed of m i..d components, hence convergence rate scales linearly with
Our approach: Using Theorem 5.1 More generally, by applying Theorem 5.1 it is immediate to see every pre-subnetwork will be a path in 2-layer fully connected network. There two types of paths; m length paths and m length paths. The weights are independent and follow the same distribution, hence, 2-layer network's s H matrix always decomposes as i.i.d sums. Hence convergence rate scales linearly with m. This proves Proposition 6..
D
See Section 7 for empirical analysis that motivated this study. We show for a 2-layer linear and non-linear networks that convergence rate has linear relationship with width.
6.2 DEPTH-INDUCED FIRST-ORDER MOMENTUM
In this section, we use our formula to explain how depth has a momentum- effect. Take network f. Construct new network by adding multiplication layer on top, i.e. g(X) =f((X with an extra trainable parameter μa. We first present an inequality (with the proof left to Appendix []. then explain why the inequality implies momentum-lik, behavior and finally how they are different.
Proposition 6.2. With My = pugg,
du dt may Wg) 2 cos(
duy dt
Co8
Myy Uf)
(17)
where cos denotes cosine between two vectors.
Remark 6.3 (Momentum interpreted as directional preference). In physics, momentum is defined as the tendency of an object to follow its current velocity of motion. In gradient based optimization, momentum can be defined as in Equation (1) of [32].
Ut+1 m (
(18)
where o's are the updates, is the learning rate and mo is the momentum coefficient. Quantitatively, cos(ve11, v/)) increases with m A bigger ma implies stronger preference in Ct+1 for the direction oe For network depth, Proposition describes the stronger directional preference of the deeper network g the direction of the current value vector. In the depth-induced momentum experiment below, we show that this directional preferences can have similar effects on convergence rates as momentum gradient based optimizaaion.
Remark 6.4 (Difference to momentum). The key difference between depth-induced momentum and gradient descent momentum is the following. The depth-induced momentum a condition between u' and u, whereas gradient descent momentum is second order condition between u" and u' (see (29] Eq. (4) and (10)).
Remark 6.5 (Sensitivity to output scale). Since (u', 1 (u,
2 di |ull depth-induucd
momentum will be more pronounced when ||ul can increase. In Appendix G
we present an experiment
that shows that depth-induced momentum is more pronounced when output scale is larger.
6.3 ON THE IMPORTANCE OF NUMBER OF PATHS FOR CONVERGENCE
Here, we will provide some heuristic arguments, based on our formula, on why over- parametrization through increasing the number of paths can be more effective than increasing the number of nodes (pa- rameters) and conclude that increasing depth more effective than increasing width for accelerating the training process. We first introduce important terminology which will use below.
Definition 6.6. Given collection of vectors {g.}. the Gram matrix G is defined as a matrix whose -thth entry is (gt; 95) under the Euclidean inner product.

---

Under review as a conference paper at ICLR 2020
Remark 6.7. Based on the definition above it is easy to that Gram matrix is symmetric and posttive-semidefiiie and its rank is exactly the dimension of the subspace spanned by {g:}- Suppose
H H1 +.... Hn, are all Gram matrices. Then H is positive definite any of the H₃ is positive definite. This is because of supperaddiiiiiy of the minimum eigenvalue function, iee. Amin ( (H) 2
Amia (H1) +... Amin (Hn).
Strongly- -rrmm vs. Weakly-Gran Equation 12) in Theorem can can be expanded further as follows and the terms can be classified into two groups The first group will include all the symmetrical pairs and the second group will include all the cross-terms.
PG, (.)((()))))))))))) (
H₂ll) E
Σ
Σ pEpre(ws)
PGp(w; (x)s[w)((())
(wpre(w)
Σ
Σ
(Gp X.)[w] (G, (,M,,y))ff X,)f(uo((X)) +
(19)
w pEpre(w)
Σ
E
(w. (w, ( PGps (w, x,) (()
Pt Pa Epre(w)
P17P2
Σ
PG,(w, (i) (X,
Σ Σ
PGp, (x)
PGp, (w, (f)
P1.peEpre(w))
P1
+
(20)
We refer to the first group as strongly Gram, and denote by HJ),), and refer to the second group as weakly Gram and denote it by H1 (f), i.c. we have:
Remark 6.8 (Gramness of the atrongl-GGram component). Suppose there are q paths in the network, Pl, P2. ....... ...... Pq. Then Equation (79h implies that the strongly Gram component Gramian with vectors
gi = PG (w, (i)(((x)))
PGP, (w, (.),x))(
(21)
Remark 6.9 (Insignificance of the weakly Gram component). We claim that the weakly Gram component is insignificant, see Appendix C for heuristics and empirical evidence.
Remark 6.10 (Number paths vs. number of nodes). The Gram matrix 1S should ideally be of full rank for good convergence. So we want the subspace spanned by {gi} to have dimension at least N. N is the dimension of H and also the number of sample points. On the other hand, shown in Equation [7]g
gi 's are embedded as vectors in a a q-dimensional vector space where q is the number of paths.There)) Therefore, to ensure H is full-rank, q should satisfy q N. The bigger q is, the more likely they are linearly independent and make the matrix full rank. In deep learning, N is usually large, therefore, we need have networks whose number of paths is comparable N for best convergence.
Remark 6.11 (Depth vs. width). Adding new parameter of paths more effectively than adding it at an existing layer. In other words, making models deeper increases the number of paths faster than making models wider.
new layer can increase the number
7 EXPERIMENTS
In this section, we provide experimental results that demonstrate the impact of model structure on convergence.
Setup We employ a teacher-student framework to put our ideas to test. Our teacher model is a two-layer neural network with hidden dimension 100, input dimension 50 and output dimension 1. We assume a Gaussian distribution both for the inputs and ground-truth weights. The student models are also two-layer neural networks with variable hidden dimensions, and l2 loss. The convergence rate step /. is defined as Loss
Loss,
7

---

Under review as a conference paper at ICLR 2020
1,0055-000
Convergent seeergeeec Rate (A)
V O0x
R 0,9998
Training (log.
16.8
1,0015-000
250
L,0000--00
1.00002-00
5000
1550
Model's Width
#Staps InGredient Updates)
(b) Convergence Rate
(a) Training Curve
Figure 3: Training Curve Characterization for Two-layer Linear Neural Network.
100000120-00
1.0002008-000
y 3E-09x R 0,9997
Convergertt Convergence Rate
100000RE-000
1000007--00
Trapinng Locs 1log
283
L000006E-00
L000205E-00
3883
1.00004E-00
10000030-00
1000002E-00
1002001-000
9999900-01
Model's Width
(#Gradient Updates)
(b) Convergence Rate
(a) Training Curve
Figure Training Curve Characterization for Two-layer Non-Linear Neural Network.
Two-Layer Linear Neural Network As shown Figure 3a training curve in log scales look like straight lines. As shown in Figure 3b convergence rate (A) grows linearly with width.
Two-Layer Non-Linear Neural Network As shown in Figure 4a training curve for models with the sigmoid non-linearity begins in steep region where loss drops very quickly for short period of time and ends in a steady region where loss drops very slowly. We are interested in characterizing the curve the steady region. As shown in Figure 4b convergence
(A) grows linearly with width.
Depth induced momentum Figure 5 compares the convergence rate curves for 2-layer, 3-layer and 4-layer NN using GD, against 2-layer network with momentum optimizer. The deeper networks are constructed from 2-layer networks with additional scalar multiplication layers. As discusses in Section 4.5, one can observe depth-induced momentum in convergence rates, similar to using momentum optimizer with 2-layer NN.
CONCLUSION
In this paper, we provide a path-based combinatorial formula for the coefficient matrix H which governs the gradient descent dynamics. We advocate analyzing H with this path-based approach by showing the insights we could derive from this.
0.008
hidden dim 1000
hidden dim 2000
0.006
hidden dim 1000
Convergence Rate
momentum 0.2
0.004
hidden dim 1000
momentum
hidden dim 1000
0.002
momentum 0.8
hidden dims 1000, 1
hidden dims 1000, 1,1
2000
4000
6000
Steps
Figure 5: Depth induced momentum.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. arXiv preprint (IXi::811..03966 2018
[2] Joel Hestness Ardalani, Newsha and Gregory Diamos. Have models
larger faster.
cake and cat it faster too: A guideline to train larger
2018.
[3] Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. arXiv preprint arXiv:1810.02281, 2018.
[4] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. arXiv preprint 1xXivv/802.065000 2018.
[5] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grainee analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: 1901. 08584, 2019.
[6] Peter Bartlett, David P Helmbold, and Philip M Long. Gradient descent with identity initialization efficiently learns dositive-definite linear transformations by deep residual networks. Neural computation, 313)4477-502, 2019.
[7] Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint 11/1::/1//00666 2018.
[8] Lingjiao Chen, Hongyi Wang, Jinman Zhao, Dimitris Papailiopoulos, and Paraschos Koutris. The effect of network width on the performance of large-batch training. In Advances in Neural Information Processing Systems, pages 9302-9300000 92099 2018.
[9] Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pages 6571-6583, 2018.
[10] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pages 192-204, 2015.
[11] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non- convex optimization. In Advances in neural information processing systems, pages 2933-2941, 2014.
[12] Simon S Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. arXiv preprint arXiv: /0t.198722... 2019.
[13] Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. In Advances in neural information processing systems, pages 1067-1077, 2017.
[14] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 1.0.8804 2018.
[15] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02005. 2018.
[16] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(uu)::121-2155) 2011.
[17] Emilien Dupont, Arnaud Doucet, and Yee Whye Teh. Augmented neural odes. arXiv preprint urXiv:/904.4 /01.//94440///// 2019.
[18] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. arXiv preprint arXiv: / 8888888037777 2018.

---

Under review as a conference paper at ICLR 2020
[19] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points oointe-online stochastic gradient for tensor decomposition. Conference on Learning Theory, pages 797- 842, 2015.
[20] Amir Gholami, Kurt Keutzer, and George Biros. Anode: Unconditionally accurate memory- efficient gradients for neural odes. arXiv preprint
2019.
[21] Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. arXiv preprint 4rX.v41412.6544, 2014.
[22] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[23] Chi Jin, Rong Gc, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning-Voluee Volume 70, pages 1724-1732. JMLR. org, 2017.
[24] Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594, 2016.
[25] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. arXiv preprint arXiv: 009,04836, 2016.
[26] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[27] Yiping Lu, Aoxiao Zhong, Quanzheng Li, and Bin Dong. Beyond finite layer neural net- works: Bridging deep architectures and numerical differential equations. arXiv preprint arXiv:1710. 10121, 2017.
[28] Yu Nesterov.
Introductory lectures on convex programming. 1998.
[29] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks, 12(5)1155-15, 1999.
[30] Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks. arXiv preprini urXiv: 1605v:6605.080 003611 2016.
[31] Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nes- terov's accelerated gradient method: Theory and insights. In Advances in Neural Information Processing Systems, pages 2510-2518, 2014.
[32] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning. pages 1139 1147, 2013.
[33] Yazhen Wang. Asymptotic analysis via stochastic differential equations of gradient descent algorithms in statistical and computational paradigms. arXiv preprint arXiv:1711.09544 2017.
[34] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv:1605.0 (46, 2016.
arXiv preprint
[35] Yanqi Zhou, Siavash Ebrahimi, Sercan Ô Ank, Haonan Yu, Hairong Liu, and Greg Diamos. Resource-efficient neural architect. arXiv preprint arXiv:1806. 1.t.:1806.07922.. 2018.
[36] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 8697-8710, 2018
10

---

Under review as a conference paper at ICLR 2020
A Ip LOSS
We argue very briefly that without loss of generality, assume that work with l2 loss instead of other Lp norms. For Ip loss
aL
p. (1j Ug) )
(22)
Juj
So for la loss, Equation 5
becomes
du
nH(y u)
(23)
dt
Recall the argument for decay rate under Equation
8 The single variable analogue of the system is:
df(1) hf(()
(24)
the solution looks like:
f(t) cheht
(25)
and decays like:
f(t) co E)
(26)
with
== ch
(27)
When h is small, by Taylor expansion
h2 2 )
1 + h
(28)
Instead of using the closed form solution, this ODE could equivalently be solved using the series method and we would be getting the Taylor expansion of equation (25) on the right and equation (28) remains the same. Note that the series method (more fundamentally. Taylor expansion involving only
one matrix) works for both ODEs and systems with convergent assumptions on the coefficient matrix
H. q/ is small by assumption, so we have convergent Taylor expansions, so we continue to argue for Lp loss as if we are in the single variable case.
For general Ip loss, we have:
f h
(29)
then
cher
(30)
and the decay rate would be A scaled down by p. all the convergence rate statements make for the rest of the paper for remains true scaled by y.
B 2 LAYER LINEAR NETWORK
The detailed brute-force calculation of H,g for 2-layer fully connected linear network with 1 is as follows. Recall m is the width of the hidden layer.
Hij Σ Ou; Oug
Ous Ouj Ow Dw
Σ
Dr, Ou:
"EV
WEW
= (W.:, (: 1)) + Σ (Ub wik X2,)) (vo Wik Xz,0
[WW(: 1,) (W X)) + (Wik Xi,x) (wik Xix))
(31)

---

Under review as a conference paper at ICLR 2020
4.5000E-05
Convergence Rate (N
y= 1E-08X 3E-07
3.5000E-05 05
3.0000-05
R290.9188
2.5000E-05
1.5000E-05
1,0000 05
5,00005-06
0
500
1000
1500
2000
2500
3000
Model's Width
Figure 6: Convergence Rate for 3-layer RELU-activvted Network.
For a general m, we have:
Hij Σ
Ou, Ouj
Σ WEW
Ou, Oug dw Ow
+
Sv Ov,
vEV
(W,,)), X.) (),
in X1,k) . (wr xz,))
k=
(w(.), (W(:0,,))) + Σ (u) X(,k)) (1 -X,x))
m
(WGGD))))(WG)))). (W(, of Σ X1,k XiM
(32)
k=1
C WEAKLY GRAM MATRIX IS EMPIRICALLY INSIGNIFICANT
In terms of network architecture, the weakly Gram term would only appear when paths share final edge. That means the network needs to have at least 3 layers. The number of pairs could grow quadratically with width. Heuristically, each term PPP (w, X;) PGpp Xy)] tend be 0 because of independent weights in PG and the weights having expectation O. Hence, we focus on the strongly Gram part for the rest of the section. As in Equation (19) the number terms in weakly Gram component grows quadratically in the width of the hidden layer. One might expect this results a quadratic growth convergence, given all the terms are i.i.d. random variables and strictly positive. In order to test this hypothesis, exploit teacher-student framework outlined in Section 7 however the student models are 3-layer RELU-activated networks to ensure the number of terms in weakly Gram component is non-zero. We choose RELU activation function to ensure that the expected value the activation to be greater than zero. Our experimental results shows that the convergence rate relationship with width is linear (see Figure ( and not quadratic. This implies that weakly Gram components have expectation zero.
D JUSTIFY H STAYS CLOSE TO INITIALIZATION
Weights and H are indeed time-dependent and follow their respective stochastic process. However, theoretical results in the overparametrized regime suggest that every weight vector remains close to initialization (Lemma 5.3 (5) and Lemma 3.3 (15). We also observe that the mean and variance stay very close to initialization, A (O,00 0.1) (Figure 7). In Figure 3 we ran the Kolmogorov-Sminn Smioroo test to compare the weight distribution against the initialization distribution. As shown, the p-values overall stable and far from significance levels to invalidate the null hypothesis (Ho: trained weights follow N 0.1)).
12

---

Under review as a conference paper at ICLR 2020
Mean of Weights, Linear Network
Std of Weights, Linear Network
width 2000 layer
width 2000 layer
width 2000 layer
width 2000 layer 1
0.105
-0.0002
0.1
-0 -0.0004
-0.0006
0.095
4000
1000
2000
3000
4000
5000
Mean of Weights, Sigmoid
Std of Weights, Sigmoid
width 2000 layer
width 2000 layer
width 2000 layer
width 2000 layer 1
0.11
0.00011
-0.0002
-0.0003
0.09
20000 30000 40000 50000 60000 Figure 7: Mean and std across the training process. (X-axis is the number of steps)
10000 20000 30000 40000 50000 60000
layer 0, width : 2000, linear
layer 0, width:2000, sigmoid
layer 1, width: 2000, linear
layer 1, width:2000, sigmoid
0.75
0.75
value
value
0.5
0.25
0.25
1000
2000
3000
4000
5000
10000
20000
30000
40000
Steps
Steps
Figure 8: KS test p-values across the training process.
layer 0 width:2000, sigmoid
layer 0, width:2000, linear
layer width:2000, sigmoid
layer width220000
0.7
5
value
0.5
0.5
0.2
0.2
1000
3000
10000
20000
30000 Steps
40000
50000
Steps
Figure 9: Turning point test p-values
E JUSTIFY IID ASSUMPTION FOR WEIGHTS
The Turning Point Test is commonly used to check iid-ness. Figure 9 shows the p-value through the training process. As shown, p-values do not exhibit any major regime shifts and the null hypothesis (the weights are iid samples) stays far from rejectable with any commonly used significance levels 10.1, 0.05 ...). iid-ness can also be seen as a consequence of closeness to initialization response 1. By staying close to initialization, statistical properties preserved and the weights remain iid sample of the original distribution.
F PROOF OF PROPOSITION 6.2
Proof. By definition of f and g. in g, there's a new path of length 1 whose edge is f and all paths in are annexed by μ the front. Hence Hij for the new network g can be computed in terms of Hap
13

---

Under review as a conference paper at ICLR 2020
for the network f as follows:
Hiylg) =
+ f(x)) +(X f(x,)
(33)
This can be written in the matrix form as:
((g) - (((()++ + uy ug
(34)
We first calculate an inner product,
(g)) Ugg un) (((H(()) + us )F) un) ((PH()) + +us- - uii )uus uwss)
(35)
(36)
(WPH(F) pmm, + (uj ub i =m)(H()),,,us> + 12 (uj ut -us
(37)
(38)
= + uy
(39)
= =,((H()) uz) ,² |
(40)
Now we calculate cosines,
(g)g) Ug)
cos cos(H (g)))) Ug)
(41)
[H(g) u ||=al|
(H (f) up) 122 u
(42)
(g) 24
n² ( + +1ulll
(43)
H(g)up| [
Using equation 34 to expand the denominator,
1 (H()) ug) +1|25
(g))) Ug)
(44)
(n²H(f) uyuf)) 22 |
1² (2 uy
(45)
|²H(f)u
+|| +|/ |
suffices to check
1º (H(H))) uy) + +||
(H(f)y,uu) uy)
RHS
(46)
H //| + +||u/|
[Hff), ||
which after cross-multipiication, reduces to:
Hf)uu | 2 (H(f)u,
(47)
This follows from Cauchy-Schwarz inequality. Equality holds precisely when H(Juu is parallel to uy (Equation (4)..
(4
Remark F.1. One further remark that could be made after Remark 6.3 and 6.4 is the following. The proof above tells us that depth-induced momentum comes mainly from the extra term uy in Equation 34). Note that uys are the values of the networks at sub-network f. Comparing this with our bath-based expansion formula Equation (2) where all sub-networks' values appear with different scaling factors proportional to their path gradients sum, we can conclude qualitatively that this phenomenon is present across all sub-networks and each sub-network contributes to overall momentum proportional to its path gradients sums.
14

---

Under review as a conference paper at ICLR 2020
0.0027
2000_1_std_0.12
0.0025
2000_std_orr
Convergence Rate
0.0023
2000_1_std_0.06
2000_std_0.00
0.0021
2000_1_std_0.24
0.0019
2000 2000_std_022
0.0017
0.0015
10000
20000
30000
40000
50000
60000
Figure 10: Momentum's dependence on output scale.
G
THE IMPACT OF OUTPUT VALUE DISTRIBUTION ON DEPTH-INDUCED MOMENTUM
Figure 10 shows the impact of output distribution on momentum. The underscore separated strings represent hidden dimensions. "2000" represents hidden dimension of width 2000 and "2000_ 1" represents hidden layers of width 2000 and The number after "std" represents the output's standard deviation in the teacher network, equivalently scale as the mean is O. As we observe from the graph, momentum acceleration is not present for small standard deviation (0.06 and 02) and the behavior is more similar to shallow 2-layer network of the same width. When standard deviation is raised to 0.24, then we observe acceleration of the convergence rate. all of these experiments, is initialized to and empirically stays close to counteract the effect of 2 in equation (34).
15


Reviews:
[{"review_id": "SkxOcKDTYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a simple and intuitive interpretation of the dynamics of gradient descent between labels and predictions rewritten in terms of all possible paths from inputs to outputs in FC networks. The basic starting point is from the gradient flow (gradient descent in continuous time) by Du et al 2018 [13] on the difference y-u of labels y predictions u (eq (6) or (7) in the paper) instead of the standard gradient flow dW/dt = - ∂L(W)/∂w. The coefficient matrix H of the system is known to determine the convergence properties, and this can be rewritten with respect to path-wise sums of gradients through the chain rule (Theorem 4.1).  This provides some intuitive interpretations for several facts discussed in the community: 1) the linear convergence rate is more intuitively obtained compared to the naive derivations (Remark 5.2 with comparison to [13]). 2) the 'depth' of FC network affects the convergence like momentum (section 5.2). 3) the number of paths compared to the number of nodes has a predominant impact on the convergence (section 5.3). The paper also demonstrates several experiments to understand the impact of depth or paths on the convergence.\n\nThough the paper's contribution is a quite simple path decomposition using chain rules for the coefficient matrix H of the gradient flow, it indeed provides several intuitive understandings on the impact of paths onto the gradient-descent convergence. All implications are basically confirming already known things in different (path-based) words, and the impact or novelty is rather small, but nevertheless, it would be informative. \n\nOne concern is about the description in section 4.1 and 4.2 for preliminaries results. I would suggest that emphasizing the fact 4.1 as an already discussed fact makes easy for readers to follow the results and focus more on the paper's contribution. The cited paper by Du et al [13] was published at the last year's ICLR, and the contents in 4.1 and 4.2 would be due to it including the formulation as gradient flow (gradient descent in continuous time). Given that it is already known that H is the determining factor for the convergence, then the contribution and usefulness of the proposed new representation of eq (15) should be discussed. At the first glance, the use of gradient flow w.r.t prediction u instead of parameter w might be (misleadingly) seen as the idea of this paper. The sentences in the abstract can also mislead readers to this. Also check the paper by Du et al in ICML 2019 'Gradient descent finds global minimum of deep neural networks'. \n\nTwo minor points: \n1) parentheses for citing references and eq numbers are quite confusing. Please check the style format for citations.\n2) in Figure 2, pre(w_0) is written as \"presum(w_0)\".\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlaIEjQqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of understanding the impact of deep neural networks (DNN) model architecture on the convergence rate of gradient descent dynamics. To achieve this goal, the paper follows the recent trend of continuous-time perspective of optimization, and proposes to model gradient descent via the gradient flow, which is a first-order ODE. The induced loss dynamics is then also following a first-order ODE with a coefficient matrix H (that depends on the solution trajectory, and hence non-constant). The paper then claims that the convergence rate is characterized by the minimum eigenvalue of H, and analyzes this H through a straightforward path-based formula obtained by chain rules. In particular, the authors try to explain the effect of width, depth and number of paths on the convergence rate, and validated these through a few numerical experiments.\n\nAdmittedly, the idea of this paper is interesting. However, I think the novelty and rigorousness of this paper is not convincing, as explained in more details below.\n\n1. On the novelty side, characterizing the convergence via the H matrix is not new, and most of the discussions in Section 4 have appeared in exactly the same form in the previous works [13] (two-layer) and [25] (general), which are also cited in this paper. In addition, the path formula is also very closely related (if not completely the same as) with the expansion of G matrix in Section 4 of [25] (where G is the H in this paper), which decomposes the G (or H) matrix into summation over layers. These facts largely lower the contribution of this paper on a high level. \n\n2. On the rigorousness side, the paper is not very consistent in the notation. \n1) The notation is not very consistent. The authors use H in the notation section to denote the matrix, use X_i to denote the data input, but use \\bf{H} and x_i (lower cased) subsequently. \n2) In Section 4, the authors immediately start with the continuous-time perspective, without even mentioning the gradient dynamics or some related ansatz. The authors may want to mention that they use the ansatz w_k=W(kh), where W is a smooth curve, and take h to 0 to obtain the ODE models, as is done in [1].\n3) The notation list at the beginning of Section 4.3 is too long and not clear. In particular, l(p) is not even defined before appearing in (14), and \\sigma_s seems to be overridden by the notation activation(w_s, X_i) and does not appear later in the path gradient, which is weird. Shouldn't there be \\sigma_s inside the formula of (14)?\n\n3. Again on the rigorousness side, the paper is very non-rigorous when stating the claims and theorems.\n1) The authors claim that \"This result will hold for other l_p losses\", but indeed what holds is different for l_p losses (the rate is scaled by p/2).\n2) Section 4.2 does not make any sense. The authors should either directly cite the corresponding content in [25], which are much clearer, or directly invoke the standard linear ODE theory and use the matrix exponential and Taylor expansion to make the explanations.\n3) The paper seems to use a very informal argument that H stays close to its initial value to derive all the theory, which is only empirically checked in the appendix. But given the proportion of the theory part of this paper, I think the paper should either clearly state the assumption as H being constant, or follow the manner of [25] to prove that H stays close to some fixed matrix and use this to prove the other theorems rigorously. Otherwise, the theory part is both hard to understand and verify. \n4) Proposition 5.1 should clearly state whether the statement is in the expectation sense, or high probability sense, or something else. \n5) The explanation in Section 5.2 is rather unclear. In particular, I don't understand why \"eigenvalues of H(g) are pushed in the direction of g\" implies that \"the updates prefer the direction of u\", and why this then further implies something related to the momentum acceleration. The authors should provide a rigorous statement here.\n6) The authors claim at the bottom of page 1 that they show adding a new layer leads to H(t) being decomposed into an adaptive learning rate term and a momentum term. But the adaptive learning rate part is not showing anywhere later in the paper. \n\nMinor comments:\n1) In equation (5), there should be a minus sign on the right-hand side.\n2) In Section 5.2, there is no \"Equation 5.2\". It should be something else.\n3) The authors may want to add citations to [2] (which is a concurrent work with [25] on essentially the same topic) and [3] (which is a predecessor work of neural ODE).\n\n[1] Su, Weijie, Stephen Boyd, and Emmanuel Candes. \"A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights.\" Advances in Neural Information Processing Systems. 2014.\n[2] Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. \"A convergence theory for deep learning via over-parameterization.\" arXiv preprint arXiv:1811.03962 (2018).\n[3] Lu, Yiping, et al. \"Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations.\" arXiv preprint arXiv:1710.10121 (2017).\n\n################## post rebuttal ##################\nAfter reading the authors' rebuttal, I decide to raise my rating to 3 (weak reject).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BylpetaaFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the training dynamics of a neural network model as a dynamical system.  The authors proposed a path-based approach to compute the derivatives that would appear in the H matrix which governs the learning dynamics.  They further utilized this formulation to (1) simplify the analysis of convergence rate of 2-layer neural networks w.r.t. width; and (2) presented an argument for the similarity between added depth in the network and momentum-based optimization; and (3) also argued about the importance of the number of paths for fast convergence.\n\nThe dynamical systems view of the learning process is quite new to me, even though I’m aware of a few recent papers exploring this.  I found the paper to be mostly clear and not too hard to follow, and the dynamical systems perspective interesting.  The path gradient is quite intuitive, but I’m a bit surprised there’s no prior work (at least not discussed in this paper) studying the relationship between gradients and the paths in the network.\n\nIt is a bit hard for me to judge the significance of this work because of my lack of context.  The main implications of the path gradients were presented in section 5.  The first part shows that using their theorem 4.1 can simplify the derivation of the linear relationship between convergence rate and the width of 2-layer nets.  This is a simplification but the original derivation is not complicated either.  The second part tried to draw a relationship between added depth in a network and momentum-based optimization, which I found to be a bit hand-wavy.  In particular, I found the argument that, du/dt prefers the direction of u itself which carries information about past directions therefore this is similar to momentum, to be not convincing.  The third implication argues that we need H to be full-rank for fast convergence, and in order to achieve this we want to increase the number of paths in the network, which is interesting.\n\nThere are a few other things that could be clarified:\n- the terminology in section 4.3 is a bit confusing, w_s seems to be associated with an edge in the graph, but is also referred to as a node, “we denote the activation value at node w_s with activation(w_s, X_i) ”.\n- on page 6 there is a reference to Equation 5.2 which does not exist\n- the results in Figure 4a is counter-intuitive - is this showing wider networks actually converge slower?  Isn’t this against the argument of this paper?\n- it is unclear how the convergence rate lambda values are computed in Figure 4b, the curves in Figure 4a clearly doesn’t follow an exponential decay pattern.\n\nOverall I found this paper presented some interesting ideas, but may need a bit more work to be ready to be published.  Happy to change my judgement however, if other more experienced reviewers can comment better on the significance of this work.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper focuses on understanding the role of model architecture on convergence behavior and in particular on the speed of training. The authors study the gradient flow of training via studying an ODE's coefficient matrix H. They study the effect of H in terms of possible paths in the network. The reviewers all agreed that characterizing the behavior in terms of path is nice. However, they had concerns about novelty with respect to existing work on NTK. Other comments by reviewers include (1) poor literature review (2) subpar exposition and (3) hand-wavy and rack of rigor in some results. While some of these concerns were alleviated during the discussion. Reviewers were not fully satisfied.  I general agree with the overall assessment of the reviewers. The paper has some interesting ideas but suffers from lack of clarity and rigor. Therefore, I can not recommend acceptance in the current form.
Decision: Reject