The Effect of Neural Net Architecture on Gradient Confusion & Training Performance
Authors: Karthik A. Sankararaman
Soham De
Zheng Xu
W. Ronny Huang
Tom Goldstein
Venue:  (2020)
Keywords: neural network architecture
speed of training
layer width
network depth

Abstract: The goal of this paper is to study why typical neural networks train so fast, and how neural network architecture affects the speed of training. We introduce a simple concept called gradient confusion to help formally analyze this.  When confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, data samples interact harmoniously, and training proceeds quickly. Through novel theoretical and experimental results, we show how the neural net architecture affects gradient confusion, and thus the efficiency of training. We show that increasing the width of neural networks leads to lower gradient confusion, and thus easier model training. On the other hand, increasing the depth of neural networks has the opposite effect. Finally, we observe empirically that techniques like batch normalization and skip connections reduce gradient confusion, which helps reduce the training burden of very deep networks.

Under review as a conference paper at ICLR 2020
THE EFFECT OF NEURAL NET ARCHITECTURE ON GRADIENT CONFUSION & TRAINING PERFORMANCE
Anonymous authors Paper under double-blind review
ABSTRACT
The goal of this paper is study why typical neural networks train fast, and how neural network architecture affects the speed of training. We introduce a simple concept called gradient confusion help formally analyze this. When confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, data samples interact harmoniously, and training proceeds quickly. Through novel theoretical and experimental results, we show how the neural net architecture affects gradient confusion, and thus the efficiency of training. We show that increasing the width of neural networks leads to lower gradient confusion, and thus easier model training. On the other hand, increasing the depth of neural networks has the opposite effect. Finally, we observe empirically that techniques like batch normalization and skip connections reduce gradient confusion, which helps reduce the training burden of very deep networks.
INTRODUCTION
Stochastic gradient descent (SGD) (Robbins & Monro, 1951) and its variants with momentum (Sutskever et al., 2013) have become the standard optimization routine for neural networks due to their fast convergence and good generalization properties (Wilson et al., 2017; Keskar & Socher, 2017: Sutskever et al., 2013). Yet the behavior of SGD on high-dimensional neural network models still eludes full theoretical understanding. both in terms of its convergence and generalization properties. In this paper, we study why SGD is so efficient converging to low loss values on most standard neural networks, and how neural net architecture design affects training performance.
Classical stochastic optimization theory predicts that the learning rate of SGD needs to decrease over time for convergence to be guaranteed to the minimizer of convex function (Shamir & Zhang, 2013; Bertsekas, 2011) 1). For strongly convex functions for example, such results show that a decreasing learning rate schedule of O(1/k) is required to guarantee convergence to within e-accuracy of the minimizer O(1/e) iterations, where denotes the iteration number. Such decay schemes, however, typically lead to poor performance standard neural network problems. Neural networks operate in a regime where the number of parameters is much larger than the number of training data. In this regime, SGD seems converge quickly with constant learning rates. Most neural net practitioners use a constant learning rate for the majority of training, with exponentially decaying learning rate schedules the end, without seeing the method stall (Krizhevsky et al., 2012; Simonyan & Zisserman, 2014; He et al., 2016; Zagoruyko & Komodakis, 2016). With constant learning rates, theoretical guarantees show that SGD converges quickly to a neighborhood of the minimizer, but then reaches noise floor beyond which it stops converging; this noise floor depends on the learning rate and the variance of the gradients (Moulines & Bach, 2011; 1; Needell et al., 2014). Some more recent results have shown that when models can fit the data completely while being strongly convex, convergence without noise floor is possible without decaying the learning rate (Schmidt Roux, 2013; Ma et al., 2017: Bassily et al., 2018; Vaswani et al. 2018).
While these results do give important insights, they do not fully explain the dynamics of SGD on neural nets, and how they relate to overparameterization Training performance is also highly affected by the neural network architecture. It is common knowledge among neural network practitioners that deeper networks train slower (Bengio et al., 1994; Glorot & Bengio, 2010). This has led to several innovations over the years to get deeper networks to train more easily, such as careful initialization strategies (Glorot & Bengio, 2010; He al., 2015; Zhang al., 2019), residual connections (He et al.,

---

Under review as a conference paper at ICLR 2020
2016), and various normalization schemes like batch normalization (loffe & Szegedy, 2015) and weight normalization (Salimans & Kingma, 2016). Furthermore, there is ample evidence to indicate that wider networks easier to train (Zagoruyko & Komodakis, 2016; Nguyen & Hein, 2017: Lee et al., 2019), and recent theoretical results suggest that the dynamics of SGD simplify considerably for very wide networks (Jacot al., 2018; Lee al., 2019). Several prior works have investigated the difficulties of training deep networks (Glorot & Bengio, 2010; Balduzzi et al., 2017), and the benefits of width (Nguyen & Hein, 2017: Lee et al., 2019; Du et al., 2018; Allen-Zhu et al., 2018). This work advances the existing literature by identifying and analyzing a condition that enables us to theoretically and empirically establish novel direct relationships between layer width, network depth, problem dimensionality, and SGD dynamics on overparameterized networks.
Our contributions. Typical neural nets are overparameterized (i.e., the number of parameters exceed the number of training points). In this paper, we ask how this overparameterization, and more neural net, affects the dynamics of SGD. We answer this question
specifically the architecture through extensive theoretical and experimental studies and show how network width, depth, batch normalization and skip connections affect the dynamics. We emphasize that our main contributions conceptual. In particular, following are main contributions.
We identify a condition, termed gradient confusion, that impacts the convergence properties of SGD overparameterized models. We prove that high gradient confusion may lead to slower convergence, while convergence is accelerated (and could be faster than predieted by existing theory) if confusion is low indicating regime where constant learning rates work well in practice (sections 2 and 3). We use this gradient confusion condition as the main proxy, to study the effect of various architecture choices on convergence.
We study the effect of neural net architecture on gradient confusion (section 4). and prove (a) gradient confusion increases as the network depth increases, and (b) at initialization, wider networks have lower gradient confusion. This indicates that deeper networks are more difficult to train and wider networks improves trainability of neural nets. Directly analyzing the gradient confusion bound enables us to derive novel and tight results the direct effect of depth and width, without requiring arguably restrictive assumptions like infinitely wide networks (Schoenholz et al., 2016; Lee et al., 2019). Our results hold for large family of neural networks with non-linear activations and a large class of loss-functions.
We test our theoretical predictions using extensive experiments on wide residual networks (WRNs) (Zagoruyko & Komodakis, 2016), convolutional networks (CNNs) and multi-layer perceptrons (MLPs) for image classification tasks on CIFAR-10, CIFAR-100 and MNIST (section 5 and appendix A). We find that our theoretical results consistently hold across all our experiments. We further show that innovations like batch normalization and skip connections in residual networks help lower gradient confusion, thus indicating why standard neural networks that employ such techniques are so efficiently trained using SGD.
GRADIENT CONFUSION
Notations. We denote vectors in bold lower-case and matrices in bold upper-case. We use (W),, ji.f to indicate the (i cell in matrix W and (W); for the 7th row of matrix W. [W]] denotes the operator norm of W. [N] denotes (1, N) and [N]o denotes 10..,,
Preliminaries. Given N training points (specified by the corresponding loss functions (Ji)aeN))) we use SGD to solve empirical risk minimization problems of the form,
wi F(w)= == min Rd 1 D Se(w);
using the following iterative update rule for T rounds:
W W W a fie (wx).
Here ar is the learning rate and St is function chosen uniformly at random from (fike[N at iteration k E [7). We use w' to denote the optimal solution, i.e., w' arg minw F(w).
DDe space constraints, all proofs and several additional experiments are delegated to the appendix.
2

---

Under review as a conference paper at ICLR 2020
Gradient confusion. SGD works by iteratively selecting a random function fk. and modifying the parameters move in the direction of the negative gradient of the objective term fu. It may happen that the selected gradient f& is negatively correlated with the gradient of another term f. When the gradients of different mini- maii-bacches are negatively correlated, the objective terms disagree on which direction the parameters should move, and we say that there is gradient confusion."
Definition 2.1. A set of objective functions [frbee[ has gradient confusion bound rj 2 0 if the pair-wise inner products between gradients satisfy, for a fixed w E IR4
(V)(()) VJ, (w)) =, vi + j E [N].
(3)
Remarks. Note that while the gradient confusion bound is defined for the worst-case gradient inner product, all the results in our paper can be trivially extended using a bound on the average gradient inner product: Σij=1 (w), V (w))/N² z -1). All theoretical results would remain the same up to constants. Further, note that definition 2.1 applicable even when the stochastic gradients are averaged over minibatches of size B. For minibatches of size B, the variance of the gradient inner product scales down as 1/B², and thus 1) is expected to decrease as B grows.
Observations in simplified settings. SGD converges fast when gradient confusion is low along its path. To see why, consider the case of training a logistic regression model on dataset with orthogonal vec- tors. We have f:()) = {(,,x, w), where e: R - IR is the logistic loss, (x) is set of orthogonal training vectors, and yı E 1, the label for the 7th training exam- ple. We then have (w( = (x2, where C = 31 (y x w). Note that the gradient confusion is 0 since (w). (w)) = (x, x,) = 0, V E [N] and + j. Thus, an update in the gradient direction f;
cembartt
f- 100, d 80 f = 100, d 120
10"
100, di
20000
c00c0 10000 20005
10000
2000 aVd0 10000 a000 100000 terations
Figure 1: Linear regression on an over- over--vraanene parameterimzee (d 120) and under- ander-parameterized (d = 80) model with N = 100 samples generated randomly from Gaussian, trained using SGD with minibatch size 1. Plots are averaged over 3 independent runs. Gradient cosine similarities were calculated over all pairs of gradients.
has no effect on the loss value of fj for i j In this case, SGD decouples into (deterministic) gradient descent each objective term separately, and we can expect to see the fast convergence rates attained by gradient descent.
Can expect problem to have low gradient confusion in practice? From the logistic regression problem, we have: (Vv((w) Vf (w))l = [xx, x,)| -(Gsy), This inner product is expected to be small for all w: the logistic loss satisfies |GG] < 1, and for fixed N the quantity maxij [Xx, x:) O(1Vvd) whenever {x; } are randomly sampled from a sphere (see lemma B.1 for the formal statement)." 3 Thus, we would expect a random linear model to have nearly orthogonal gradients, when the number of parameters "large" and the number of training data is "small", i.e., when the model over- over-paramett peer-paaamterized. This is further evidenced by toy example in figure 1, where we show slightly overparameterized linear regression model can have much faster convergence rates, as well as lower gradient confusion, compared to the underparameterizeed model.
Now consider more general neural net problems. There is evidence that the Hessian at the minimizer is very low rank for many standard overparameterized neural net models (Sagun et al., 2017: Cooper, 2018; Chaudhari et al., 2016; Wu et al., 2017; Ghorbani et al., 2019). What does this imply for the gradient confusion? For clarity in presentation, suppose each J' has minimizer at the origin (the same argument can be easily extended to the more general case). Suppose also that there is a Lipschitz constant for the Hessian of each function fi that satisfies | (w) H, (w")l < L ||w w'll (note that this is standard optimization assumption (Nesterov, 2018), with evidence that it is applicable for neural nets (Martens, 2016)). Then V (.() H,w + e, where is an error term bounded as: ||e|| < 1 a || |/] and we use the shorthand H, to denote (0). Then we have (appendix C)
(V (w). Vf,(w)) < | H. H, + 1 w H H. + H I)) + 143 w/|+
This is related to both gradient variance and gradient diversity (Yin et al., 2017), but with important differences. See section 6 for more discussion.
Generallly this is true whenever x; yi, where y, is isotropic random vector (Vershynin, 2018).
3

---

Under review as a conference paper at ICLR 2020
If the Hessians are sufficiently random and low-rank (e.g., of the form H, a.a? where a, R Vx are randomly sampled from a unit sphere), then one would expect the terms in this expression to be small for all w within neighborhood of the minimizer. While bit non-rigorous, this nonetheless suggests that for many standard neural network models, the gradient confusion might be small for a large class of weights near the minimizer.
The above arguments are rather informal, and ignore issues like the effect of the structure of neural networks. In the following sections, rigorously analyze the effect of gradient confusion on the speed of convergence on non-convex problems, and the effect of width and depth of the neural net architecture on the gradient confusion.
3 SGD IS EFFICIENT WHEN GRADIENT CONFUSION IS Low
Several prior papers have analyzed the convergence rates of constant learning rate SGD (Nedić & Bertsekas, 2001; Moulines & Bach, 201 I; Needell et al., 2014; Dieuleveut et al., 2017). These results show that for strongly convex and Lipschitz smooth functions, SGD with constant learning rate converges linearly to a neighborhood of the minimizer. The noise floor it converges to depends on the learning rate and the variance of the gradients the minimizer, i.e., V (w") convergence to c-accuracy in such a setting, the learning rate needs to be small, i.e., a = (cc) and the method requires T = O(1/c) iterations. Some more recent results show convergence of constant learning rate SGD without a noise floor and without small step sizes for models that can completely fit the data (Schmidt & Roux, 2013; Ma et al., 2017; Bassily et al., 2018; Vaswani et al., 2018).
(w" )| To guarantee
The gradient confusion bound is related to these classical results. Cauchy-Swart inequality implies that if EE, V f. (w*)]] (e), then E (V V fy confusion at the minimizer is small when the variance of the gradients at the minimizer is small. Further note that when the variance of the gradients at the minimizer Occ), a direct application of the results in (Moulines & Bach, 2011 1; Needell et al., 2014) shows that constant learning rate SGD has fast convergence to e-accuracy in T = O (log( (I/e)) iterations, without the learning rate needing to be small. Generally however, bounded gradient confusion does not provide bound on the variance of the gradients (see section for more discussion). Thus, it is instructive to derive convergence bounds of SGD explicitly in terms of the gradient confusion to properly understand its effect.
O()). Vi.j. Thus the gradient
We begin by considering functions satisfying the 1965), a condition related to, but weaker than, strong convexity, and provide bounds the rate of convergence in terms of the optimality gap. Then we look at a broader class of smooth non-convex functions, and analyze convergence to a stationary point. We first make standard assumptions.
(PL) inequality (Lojasiewicz.
(A1) (felie(N) are Lipschitz smooth: f.(w') S f(()) + V(((w) T (w' - -w) + [ - w/l?.
(A2) (fiHEIN satisfy the PL inequality: 1 f( > p(f((w) = minw f((w).
Theorem 3.1. If the objective function satisfies (AI) and (A2), and has gradient confusion nj. SGD with updates of the form (2) converges linearly to a neighborhood of the minima of problem (1) as:
[[F(wT) - F+] (F((o) - FF) + aq
1-p'
where <
2 NE. p= 1-
2u N (a 2 F= minw F(w) and wo is the initialized weights.
This result shows that SGD converges linearly to a neighborhood of a minimizer, and the size of this neighborhood depends on the level of gradient confusion. When the gradient confusion is small, i.e., 7) = (c). SGD has fast convergence to ((e)- in T O(log( iterations, without requiring the learning rate to be vanishingly small. We now extend this general smooth functions.
Theorem 3.2. If the objective satisfies (Al) and has gradient confusion bound rJ, then SGD converges to neighborhood of a stationary point as:
mitk-=1.... E
V
12 o(F(W))-F' + pT) T
for learning rate <
NT. p 2 Noo' and F min F(w).
2
2N
Thus, as long as 1) ((/T)) SGD has fast O(1/T) convergence on smooth non-convex functions. Theorems 3.1 and 3.2 predict an initial phase of optimization with fast convergence to the neighbor- hood of a minimizer or a stationary point. This behavior is often observed when optimizing neural
4

---

Under review as a conference paper at ICLR 2020
nets (Darken & Moody, 1992; Sutskever et al., 2013), where a constant learning rate reaches high level of accuracy on the model. As we show in subsequent sections, this is expected since for neural networks typically used, the gradient confusion is expected to be low. Convergence slows down as the iterates approach the noise floor, and at this point typically practitioners employ exponentially decaying learning rate schedules (Krizhevsky al., 2012; Simonyan & Zisserman, 2014; He et al., 2016; Zagoruyko & Komodakis, 2016; Ge et al., 2019). See section 6 for more discussion on theorems 3.1 and 3.2, and how they relate to results in previous works. We stress that our goal is not study convergence rates per se, nor is it to prove ofateoof-the-rr rate bounds for this class of problems. The main intention is to show the direct effect that the gradient confusion bound has on the convergence rate and the noise floor that constant learning rate SGD converges to. As we show in the following sections, this new perspective in terms of the gradient confusion helps us more directly understand how neural net architecture design affects SGD dynamics and why.
EFFECT OF NEURAL NET ARCHITECTURE ON GRADIENT CONFUSION
To draw a rigorous connection between neural net structure and training performance, we analyze gradient confusion for generic (i.e., random) model problems using methods from high-dimensional probability. In particular, this section considers the following scenarios: (a) Random data drawn from a unit sphere and the weights in a ball around the local minimizer (theorem 1. and corollary 4.1). (b) Random weights using standard initialization schemes and both arbitrary bounded data (theorem 4.2, part 1) and random data drawn from a unit sphere (theorem 4.2, part 2). Our results cover wide range of scenarios compared to prior work (e.g.. Chen et al. (2018); Schoenholz et al. (2016); Balduzzi et al. (2017)), require minimal additional assumptions, and hold for large family of neural nets with non-linear activations and a large class of loss-functte functions. In particular, our results hold for fully connected networks (and convolutional networks in some cases) with the square-loss and logistic-loss functions, and commonly used non-linear activations such as sigmoid, tanh and ReLU.
(a) Random Data, Bounded Weights Around Minimizer. In this subsection, we consider training data of the form D = {(x,, C(x.)) [N] for some labeling function C. : Ed + [-1, 1], and with data points (xx) drawn uniformly from the surface of a d-dimensional unit sphere. The labeling function satisfies [C(x)] < 1 and || [x)C(x)] < for ||x|| S
Note that this automatically holds for every model considered in this paper where the labeling function is realizable (i.e., where the model can express the labeling function using its parameters). More generally, this assumes Lipschitz condition on the labels (i.c., the labels don't change too quickly with the inputs). In this paper, we consider two loss-functions, namely, square-loss for regression and logistic loss function for classification. The square-loss function is defined as f((w) = 2 (C(x,) - Iw )x and the logistic function is defined as (w) = log(1 + exp( - C(xx (xx))) Here, Iw : R - IR denotes the parameterized function we fit to the training data and fi (w) denotes the loss coss-function of hypothesis Iw on data point x;-
Formally, let Wo E xdd and ( (Wp) ppppto such that W R be the given weight matrices. Let W denote the tuple (Wp) p) Define é := maxpels| lp to be the width and B to be the depth of the neural network. Then, the model gw is defined as
(x) == o (W go (Wa-1...oo o (W (Wox))
(4)
where a denotes the non-linear activation function applied point-wise to its arguments. We assume that the non-linear activation is given by a function ((x) with the following properties.
(P1) Boundedness: |o(x)) < 1 for vector x E [-1,1].
(P2) Bounded differentials: Let o'xx) and o²(x) denote the first and second sub- differentials respectively. Then, |o' [z())]] < and lo"(z)) < for all x E [-1,
When ||x|| < 1, in our random data model, activation functions such as sigmoid, tanh, sofimax and ReLU satisfy these requirements. Additionally, we make the following assumption on the weights.
Assumption 1 (Small Weights). We assume that the operator norm of the weight matrices { are bounded above by 1. In other words, for every E [3] we have || [ S 1.
(W, (W.j.
The operator norm of the weight matrices |||] being close to 1 is important for the trainability of neural nets as it ensures that the input signal is passed through the net without exploding shrinking
5

---

Under review as a conference paper at ICLR 2020
across layers (Glorot & Bengio, 2010). Proving non-vacuous bounds in case of such blow-ups in magnitude of the signal or the gradient is not possible in general, and thus, we consider this restricted class of weights. The small-weights assumption is not just theoretical concern, but also usually enforced in practice using weight decay regularizers of the form Σ; [| which keep the weights small during optimization. See appendix F for further discussion on the small weights assumption.
We now prove concentration bounds for the gradient confusion on neural nets.
Theorem 4.1. Consider the problem of training neural nets (equation 4) using either the square-loss or the logistic-loss function. Let 1) > 0 be a given constant. Let the weights satisfy assumption 1 and the non linearities in each layer satisfy properties (PI) and (P2). For some fixed constant >> 0, the gradient confusion bound in equation holds with probability at least
N2 N2 exp
coty
1666 (5+))*
For both the square-loss and the logistic-loss functions, Co S 2/B (from lemma D.I).
Thus, theorem 4.1 shows that, for given dimension d and number of samples N, when the network depth decreases, the probability that the gradient confusion bound equation holds increases, and vice versa. Note that the convergence rate results of SGD in section 3 assume that the gradient confusion bound holds at every point along the path of SGD. On the other hand, theorem 4. shows concentration bounds for the gradient confusion at fixed weight W. Thus, ensure that the above result is relevant for the convergence of SGD on overparameterized models, we now make the concentration bound in theorem 4.1 uniform over all weights inside a ball B, of radius r.
Corollary 4.1 (Uniform concentration for all weights around the minimizer). Select a point W- (Wo, W Wi...., WB), satisfying assumption 1. Consider ball B, centered at W of radius r >> 0. If the data {xs (xE) are sampled uniformly from a unit sphere, then the gradient confusion bound in equation holds uniformly at all points W' E B, with probability at least
N2 exp
edi"
ifr S/
(P+23
N2 exp
cdny 63C5(3+2)²
+
8dcar
otherwise.
Thus, corollary 4.1 shows that the probability that the gradient confusion bound holds decreases with increasing depth, for all weights in a ball around the minimizer. This explains why training very deep models is hard and typically slow with SGD (Bengio et al., 1994; Glorot & Bengio, 2010). Note that this is also related to the shattered gradients phenomenon (Balduzzi et al., 2017) that arises with depth (see appendix 6 for more discussion). This naturally raises the question why modern deep neural networks are so efficiently trained using SGD. While careful initialization strategies prevent vanishing or exploding gradients making deeper networks trainable, these strategies still suffer from high gradient confusion for very deep networks (as we show below in theorem 4.2). Thus, in section we empirically study how popular techniques like skip connections (He et al., 2016) and batch normalization (Ioffe & Szegedy, 2015) affect gradient confusion. We find that these techniques drastically lower gradient confusion, making very deep networks significantly easier to train. Note that the above results automatically hold for convolutional nets, since a convolution operation on can be represented as matrix multiplication Ux for an appropriate Toeplitz matrix U.
(b) Standard Weight Initializations and the Effect of Layer Width. Note that on assuming for each weight matrix W in our results in part I of section 4, the dependence of gradient confusion on the layer width goes away in general. A simple example that illustrates this is to consider the case where each weight matrix in the neural network has exactly one non-zero element, which is set to 1. The operator norm of each such weight matrix is 1, but the forward or backward propagated signals would not depend on the width. Thus, to better understand the effect of the layer width, in this subsection we focus on the behavior of neural nets at initialization by considering standard weight initialization strategies used when training neural nets. For completeness, we consider both the case where the data is arbitrary but bounded, well where the data is randomly drawn from unit sphere, A key point used in the following results is that typical weight initialization techniques ensure that the operator norm is bounded by I with high probability, thus enabling to derive tight bounds on the gradient confusion. We consider the following weight initialization strategy.
|[|]| <

---

Under review as a conference paper at ICLR 2020
depth 16
depth
-03
depth
depih
traning loss
-04
network
similartt
Figure 2: The effect of network depth with CNN-9-2 on CIFAR-10. Left plot: convergence curves of SGD, Middle plot: minimum of pairwise gradient cosine similarities at the end of training, Right plot: kernel density estimate of the pairwise gradient cosine similarities at the end of training (over all independent runs).
Strategy 4.1. Wo E Rxxd has independent N(0, 2)) entries. For every p E [3]. the weights WP E Rexxx=1 have independent N (0, refp_.. entries for some constant K >> 0.
This initialization strategy with different settings of к used almost universally for neural networks (Glorot & Bengio, 2010; He et al., 2015). The following theorem shows how the width & := maxpe[s] lp and the depth 3 affect the gradient confusion condition. particular, as width increases or depth decreases the probability that the gradient confusion bound (equation 3) holds increases.
Theorem 4.2 (Neural
with randomly chosen weights). Let Wo, W Wy...., Wg 3 be weight matri- ces chosen according to strategy 4.1. There exists fixed constants C1, > 0 such that we have:
1. Consider a fixed but arbitrary datasel X1, , XN with ||x:| Il s for every i [N]. For
1) > 4, the gradient confusion bound in equation 3 holds with probability at least
1 exp (-c,x2 N2 exp
-ol 3(n 6463
2. If the dataset {xi hEEN is such that each x; is an i.idd sample from the surface of d- dimensional unit sphere, then for every the gradient confusion bound in equation 3 holds with probability at least
- exp (-c)n2 N exp
(cg B)n" (6C)
Thus, theorem 4.2 shows that layer width improves the trainability of deep networks under most standard initialization techniques. Note that for reasons described above, almost all recent theoretical results neural nets have analyzed the effect of width initialization. Further, one can prove that when the layers are very wide, the weights move very little, and most of the conditions at initialization persist during training, considerably simplifying the learning dynamics of gradient descent (Jacot et al., 2018; Lee et al., 2019). Under this simplifying assumption of very wide networks, several authors have analyzed the effect of width during optimization on very wide networks (Allen-Zhu et al., 2018; Du et al., 2018). 8). Under this assumption and using standard application of the techniques used prior work, we can likely show that theorem 4.2 also holds during optimization. (and in appendix A), show substantial empirical evidence that, given a sufficiently deep network, increasing the layer width often helps in lowering gradient confusion and speeding up convergence for range of models, and that these effects persist throughout optimization for most models.
the next section
EXPERIMENTAL RESULTS
To test our theoretical results and to probe why standard neural nets efficiently trained with SGD, we now present experimental results showing the effect of the neural network architecture on the convergence of SGD and gradient confusion. It is worth noting that theorems 3.1 and 3.2 indicate that we would expect the effect of gradient confusion to be most prominent closer to the end of training.
We performed experiments wide residual networks (WRNs) (Zagoruyko & Komodakis, 2016), convolutional networks (CNNs) and multi-layer perceptrons (MLPs) for image classification tasks on CIFAR- 10, CIFAR-101 100 and MNIST. We present results for CNNs CIFAR-10 10 in this section,
7

---

Under review as a conference paper at ICLR 2020
TShn grad courr sinslerig
trehiing 46-1
QUTVity
230
-012 -0.2 0.0 0.61 0.00 0.35 326 422 -6.5
epocns
Isyer witth
painwtee gradient costne smilarity
Figure 3: The effect of width with CNN-16-E CIFAR-10 10. Left plot: convergence curves of SGD (for cleaner figures, we plot results for width factors and here), Middle plot: minimum of pairwise gradient cosine similarities at the end of training, Right plor: kernel density estimate of the pairwise gradient cosine similaritics at the end of training (over all independent runs).
BK: ship BXL stp ro BN, with stp wit sep
m grad coNTre simierty
Emai DAUE set accuaayy
(hell trahtin
with 5Nl skip
BN, with skip
wits DN 92
ENL slpp
with BNL skip
SMI with skip
with BM skdp
20
30
30
76
30
330
20
20
30
60
33
20
100
30
50
30 90 380
degtth
Sopth
Figure 4: The effect of adding skip connections and batch normalization CNN-3-2 CIFAR-10. 100. Plots show
the optimal training loss (left plot), minimum pairwise gradient cosine similarities (middle plot), and test accuracies (right plot) at end of training.
and present all other results in appendix A. We use CNN-3-E to denote WRNs that have skip connections or batch normalization, with a depth 3 and width factor We turned off dropout and weight decay for all our experiments. We used SGD the optimizer without any momentum. Following Zagoruyko & Komodakis (2016), we ran all experiments for 200 epochs with minibatches of size 128, and reduced the initial learning rate by factor of 10 epochs 80 and 160. We used the MSRA initializer (He et al., 2015) for the weights as is standard for this model, and used the same preprocessing steps for the CIFAR-10 images as described in Zagoruyko & Komodakis (2016). We ran each experiment 5 times, and we show the standard deviation across runs in our plots. We tuned the optimal initial learning rate for each model over logarithmically-speeee the run that achieved the lowest training loss value. To measure gradient confusion, at the end of every training epoch, we sampled 100 pairs of mini-batches each of size 128 (the same size as training batch size). We calculated gradients on each mini-batch, and then computed pairwise cosine similarities. See appendix A.2 for more details on the experimental setup and architectures used.
grid and selected
Effeet of depth. To test theoretical results, consider CNNs with fixed width factor of 2 and varying network depth. From figure 2, we see that our theoretical results are backed by the experiments: increasing depth slows down convergence, and increases gradient confusion. We also notice that with increasing depth, the density of pairwise gradient cosine similarities concentrates less sharply around 0 (indicating higher variance), which makes the network harder to train.
Effect of width. We now consider CNNs with a fixed depth of 16 and varying width factors. From figure 3, We further see that gradient cosine similarities concentrate around () with growing width, indicating that SGD decouples across the training samples with growing width. Note that the smallest network considered is still overparameterized and achieves high level of performance (see appendix A.3).
that inereasing width results in faster convergence and lower gradient confusion.
Effect of batch normalization and skip connections. To help understand why many standard deep nets are so efficiently trained using SGD, we test the effect of adding skip connections and batch normalization to CNNs of fixed width and varying depth. Figure 4 shows that adding skip connections or batch normalization individually help in training deeper models, but these models still suffer from worsening results and increasing gradient confusion as the network gets deeper. Both these techniques together keep the gradient confusion relatively low even for very deep networks, *The width factor denotes the number of filters relative to the original ResNet model.
8

---

Under review as a conference paper at ICLR 2020
significantly improving trainability of deep models. Note that all these observations consistent with previous work (Balduzzi et al., 2017; Santurkar et al., 2018; Yang et al., 2019).
6 CONNECTIONS TO RELATED WORK
The interpolation condition and connections to the gradient variance: The gradient confusion condition has interesting connections to the variance of the gradients. If we assume bounded gradient variance o², we can bound the gradient confusion parameter 1 in terms of other quantities. For example, suppose the true gradient y is defined as g = /1/2 92/ 22. Then we have:
Kg,, 92)l - 91 |21l s 1/2 (1l9 112 + (1 1/2- (( -9ll 1192 gll
+loll? +
=o² o +l99|1
where all gradients are defined at the same w.
More interestingly however, it is not possible in general to bound the gradient variance in terms of the gradient confusion parameter. As a counter-example, consider a problem with the following distribution the stochastic gradients: T-p samples with gradient _ and & samples with gradient e, p
where p c + O. In this case, the gradients are positive, so gradient confusion 77 O. The mean
of the gradients is given by 1+ + <(1 - e). which remains bounded as + 0. On the other hand, the variance (and thus the squared norm of the stochastic gradients) is actually unbounded (O(1/c) as c c-> 0). While this a contrived example, it does show why such a bound does not exist.
consequence of this is that in theorems 3.1 and 3.2 in section 3, the "noise term" (i.e., the second term in the RHS of the convergence bounds) does not depend on the learning rate in the general case. If gradients have unbounded variance, lowering the learning rate does not reduce the variance of the SGD updates, and thus does not reduce the noise term. This further indicates regime of high gradient variance but low gradient confusion where SGD would converge faster than predicted by classical convergence rate results (Moulines & Bach, 2011; Needell et al., 2014).
In practice, typically the gradient variance is bounded. In this case, tighter convergence rate bounds in terms of 1) are possible, which follow as simple corollaries from classical convergence bounds in terms of the gradient variance such as those in Moulines & Bach (201 1); Needell et al. (2014). The interpolation and strong growth conditions, as analyzed in Ma al. (2017); Bassily et al. (2018); Vaswani et al. (2018): Schmidt & Roux (2013), are related to this. These conditions imply that the variance of the gradients the minimizer is small. As shown above, this would imply that the gradient confusion is also small, leading to fast convergence of SGD. This is also similar to the condition of the minimal risk being small as in Srebro et al. (2010); Zhang & Zhou (2019).
That being said, it is worth noting that the main contribution of this paper is better understand how the network architecture impacts SGD. In general, it is not tractable to prove the concentration bounds in section 4 using the covariance matrix of the gradients alone without further unrealistic assumptions, such as infinitely wide networks (Schoenholz et al., 2016). A key contribution of this paper is to identify& a suitable surrogate (i.e., the gradient confusion bound) to help study this relationship using new tight and clean bounds.
Connections to gradient diversity: In Yin et al. (2017), the authors define a property called gradient diversity. This quantity is related to gradient confusion, but with important differences. Gradient diversity also measures the degree to which individual gradients at different data samples are different from each other. However, the gradient diversity measure gets larger the individual gradients become orthogonal to each other, and further increases as the gradients start pointing in opposite directions. In large batch, higher gradient diversity is desirable, and this leads improved convergence rates in distributed settings, as shown in Yin et al. (2017). On the other hand, gradient confusion between two individual gradients is zero unless the inner product between them is negative. This makes gradient confusion useful for studying convergence of small minibatch SGD. This is because different possible SGD updates do not conflict with each other unless they are negatively correlated with each other.
The choice of the definition of gradient diversity in Yin et al. (2017) has important implications when its behavior is studied in overparameterized settings. Chen et al. (2018) extends the work of Yin et al. (2017), where the authors prove on 2-layer neural nets (and multi-layer linear neural nets) that gradient diversity increases with increased width and decreased depth. This metric does not.

---

Under review as a conference paper at ICLR 2020
however distinguish between the cases where gradients become more orthogonal more negatively correlated. As we show in this paper, this can have very different effects on the convergence of SGD in overparameterized settings. Specifically, decreases gradient confusion, and makes these networks easier to train. In fact, we see that the gradients become more orthogonal to each other in this case as shown in section 5. Thus, view our papers to be complementary to each other, providing insights about different issues (large batch distributed training vs, small minibatch convergence).
show that increased width and decreased depth
Other work on the impact of neural net structure: Other works have also studied the impact of structured gradients SGD. Balduzzi et al. (2017) study the effects of shattered gradients at initialization for ReLU networks, which is when stochastic gradients at initialization become negatively correlated. The authors show how gradients get increasingly shattered with depth in ReLU networks. Hanin (2018) shows that the variance of gradients in fully connected networks with ReLU activations is exponential in the sum of the reciprocals of the hidden layer widths initialization. Further, Hanin & Rolnick (2018) show that this sum of the reciprocals of the hidden layer widths determines the variance of the sizes of the activations each layer during initialization. When this sum of reciprocals is too large, early training dynamics are very slow, suggesting the difficulties of starting training on deeper networks, as well as the benefits of increased width.
The convergence of SGD on over-parameterized models has received lot of attention recently. Arora et al. (2018b) study the behavior of SGD on over over-parameetnt parameterized problems, and show that SGD on over- wverpparameterized linear neural nets is similar to applying certain preconditioner while optimizing. This can sometimes lead to acceleration when overparameterizing by increasing the depth of linear neural networks. In this paper, we show that this property does not hold in general (as mentioned briefly in Arora et al. (2018b)), and that convergence typically slows down because of gradient confusion when training very deep networks. There has recently also been interest in analyzing conditions under which SGD converges to global minimizers of overparameterized linear and non-linear neural networks. Arora et al. (2018a) shows SGD converges linearly to global minimizers for linear neural nets under certain conditions. Du et al. (2018); Allen-Zhu et al. (2018); Zou et al. (2018); Brutzkus et al. (2017) also show convergence to global minimizers of SGD for non-linear nets. While all these results require the network to be sufficiently wide, they represent an important step in the direction of better understanding optimization on neural nets. This paper complements these recent results by studying how low gradient confusion contributes to SGD's 's success modern overparameterizee neural nets.
Other work on SGD convergence on overparameterized neural nets:
7 CONCLUSIONS
In this paper, we investigate how overparameterization and model architecture affect the dynamics of SGD on neural networks. To help formally analyze this, we introduce concept called gradient confusion, and show that when gradient confusion is low, SGD experiences fast convergence. We then show that increasing layer width leads to lower gradient confusion, making the model easier to train. In contrast, increasing network depth results in higher gradient confusion, making deeper models harder to train. We further show how techniques like batch normalization and skip connections help in tackling this problem.
Our results provide number of important insights that can be used for better neural net model design, as well as for better algorithms for better training and generalization. Our results on the test set accuracies in appendix A suggest that interesting topic for future work would be to investigate the connection between gradient confusion and generalization (Fort et al., 2019). The difference in the gradient confusion within the same class and across classes could also be an interesting tool to study adversarial training. Note that many previous results have shown how deeper models are more efficient at modeling higher complexity function classes than wider models, and thus depth is essential for the success of neural networks (Eldan & Shamir, 2016; Telgarsky, 2016; Raghu et al., 2017). Our results indicate that, given a sufficiently deep network, increasing the network width is important for the trainability of the model, and will lead to faster convergence rates. This is further supported by other recent research (Hanin, 2018; Hanin & Rolnick, 2018) that suggest that the width should increase linearly with depth in neural network to help dynamics at the beginning of training. Our results also suggest the importance of further investigation into good initialization schemes for neural networks that make training very deep models possible (Zhang et al., 2019).
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint 1XIi::8111.03962 2018.
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. 2018a.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. arXiv preprint arXiv: 06509, 2018b.
David Balduzzi, Marcus Frean, Lennox Leary, JP Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what is the question? arXiv preprint arXiv:1702.08:3 2017.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint arXhv:1811.02564 2018.
Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long- berg-temm dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
Dimitri Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimiza- tion: A survey. Optimization for Machine Learning, 2010(1-38):3, 2011.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. arXiv preprint 1rXiv:1710.10174 2017.
Pratik Chaudhari. Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. arXiv preprint arXiv: 1.01838 2016.
Lingjiao Chen, Hongyi Wang, Jinman Zhao, Dimitris Papailiopoulos, and Paraschos Koutris. The ef- feet network width on the performance of large-batch training. arXiv preprint arXiv:1806.0379) 2018.
Y Cooper. The loss landscape of overparameterized neural networks. 180i 10200, 2018
arXiv preprint
Christian Darken and John Moody. Towards faster stochastic gradient search. In Advances in neural information processing systems, pp. 1009-1016, 1992.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwe-tparamterrize neural networks. arXiv preprint arXiv:1810.0205: 2018.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 11008, 2017.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on Learning Theory, pp. 907-940, 2016.
Stanislav Fort, Pawel Krzysztof Nowak, and Srini Narayanan. Stiffness: new perspective on generalization in neural networks. arXiv preprint arXiv: 2019.
Rong Ge. Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure. arXiv preprint 1904. 2019.
11

---

Under review as a conference paper at ICLR 2020
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density, arXiv preprint 1rXiv:1901.10159 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and stafistics, pp. 249-256, 2010.
Boris Hanin. Which neural net architectures give rise to exploding and vanishing gradients? In Advances in Neural Information Processing Systems. pp. 582-591, 2018.
Boris Hamin and David Rolnick. How to start training: The effect of initialization and architecture. In Advances Neural Information Processing Systems, pp. 571-581, 2018
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEFE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8580-8589, 2018.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam sgd. arXiv preprint arXiv: 1711v:171..07628. 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances neural information processing systems, pp. 1097-1105, 2012.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9-48. Springer. 2012.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint 190x.0290,,00700, 2019.
Stanislaw Lojasiewicz. Ensembles semi-analytiques. Lectures Notes IHEE (Bures-sur-Yvetle) 1965.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern prermparamtrrized learning. arXiv preprint 1rXiv:1712.06655, 2017.
James Martens. Second-order optimization for neural networks. University of Toronto (Canada), 2016.
Vitali Milman and Gideon Schechtman. Asymptotic Theory of Finite Dimensional Normed Spaces. Springer-Verlle Berlin, Heidelberg, 1986. ISBN 0-387-16769-2.
Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, pp. 451-459, 2011.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint 101.v.190. 2019.
Angelia Nedié and Dimitri Bertsekas. Convergence rate incremental subgradient algorithms. In Stochastic optimization: algorithms and applications, pp. 223-264. Springer, 2001.
12

---

Under review as a conference paper at ICLR 2020
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in Neural Information Processing Systems, pp. 1017-1025, 2014.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of prramttrattiinnnioonn in generalization of neural networks. arXiv preprint arXiv: 12076, 2018.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 2603-2612. JMLR. org. 2017.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterizee nonlinear learning: Gradient descent takes the shortest path? arXiv preprint arXi:: 1812.10044 2018.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2847-2854. JMLR. org, 2017.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of wver-parametrized neural networks. arXiv preprint arXiv:1706.0444 2017.
Tim Salimans and Durk Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, pp. 901-909, 2016.
Shibani Santurkar, Dimitris Tsipras, Andrew llyas, and Aleksander Madry. How does batch normaliza- tion help optimization"((o, it is about internal covariate shift). arXiv preprint arXiv: 1604, 2018.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint 13...v:300.63377 2013.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propagation. arXiv preprint 16Xiv:1611.0023: 2016.
Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. arXiv preprint arXiv:1805, 18X5 10408, 2018
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pp. 71-79, 2013.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint ArXiv:1409.15555 2014.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with smooth loss. arXiv preprint arXiv:1009.388 2010.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. International conference on machine learning, pp. 1139-1147, 2013.
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Matus Telgarsky. Benefits of depth neural networks. arXiv preprint arXiv: 1OX2.0600000483 2016.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence sgd for over- parameterized models and accelerated perceptron. arXiv preprint 1rx 2018.
13

---

Under review as a conference paper at ICLR 2020
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stem, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4151-4161, 2017.
Lei Wu, Zhanxing Zhu, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: /706 10239, 2017.
Greg Yang, Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel S Schoenholz. A mean field theory of batch normalization. arXiv preprint arXiv:/902.088 2019.
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. Gradient diversity: a key ingredient for scalable distributed learning. arXiv preprint 17Xv::1706.5699, 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:1605.077 2016.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: Residual learning without normalization. arXiv preprint arXiv: 2019.
Lijun Zhang and Zhi-Hua Zhou. Stochastic approximation of smooth and strongly convex functions: Beyond the (I/t) convergence rate. Proceedings of Machine Learning Research vol, 19:1-20, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018.
14

---

Under review as a conference paper at ICLR 2020
A ADDITIONAL EXPERIMENTAL RESULTS
In this section, we present more details about our experimental setup, as well as, additional exper- imental results a range of models (MLPs, CNNs and Wide ResNets) and range of datasets (MNIST, CIFAR-I0, CIFAR-100).
A.1 MLPs ON MNIST
To further test the main claims in the paper, we performed additional experiments on an image classification problem on the MNIST dataset using fully connected neural networks. We iterated over neural networks of varying depth and width, and considered both the identity activation function (i.e., linear neural networks) and the tanh activation function. We also considered two different weight initializations that are popularly used and appropriate for these activation functions:
The Glorot normal initializer (Glorot & Bengio, 2010) with weights initialized by sampling from the distribution N (0, 2/ (fan-in + fan-out)), where fan-in denotes the number of input units in the weight matrix, and fan-out denotes the number of output units in the weight matrix.
The LeCun normal initializer (LeCun et al., 2012) with weights initialized by sampling from the distribution N (0, 1/ 1/fan-in).
We considered the simplified case where all hidden layers have the same width f. Thus, the first weight matrix W, E Rexd, where d = 784 for the 28 x 28-sized images of MNIST; all intermediate weight matrices ( pe Ext, and the final layer Wa IR 10 for the 10 image classes in MNIST. We added biases to each layer, which we initialized to O. We used softmax cross entropy as the loss function. We use MLP-3-L denote this fully connected network of depth 3 and width É, We used the standard train-valid-test splits of 40000-10000-1000 for MNIST.
This relatively simple model gave the ability to iterate over large number of combinations of network architectures of varying width and depth. and different activation functions and weight initializations. Linear neural networks are an efficient way to directly understand the effect of changing depth and width without increasing model complexity over linear regression. Thus, we considered both linear and non-linear neural nets in our experiments.
We used SGD with constant learning rates for training with a mini-batch size of 128 and trained each model for 40000 iterations (more than 100 epochs). The constant learning rate a was tuned over a logarithmicaaly-spean grid:
a E (10%, 10 10-2 10-2 10-3, 10-1 10-5, 10-9).
We ran each experiment 10 times (making sure at least 8 of them ran till completion), and picked the learning rate that achieved the lowest training loss value on average at the end of training. Our grid search was such that the optimal learning rate never occurred at one of the extreme values tested.
To measure gradient confusion at the end training, we sampled 1000 pairs of mini-batches each of size 128 (the same size as the training batch size). We calculated gradients each of these pairs of mini-batches, and then calculated the cosine similarity between them. To measure the worse-case gradient confusion, computed the lowest gradient cosine similarity among all pairs. We explored the effect of changing depth and changing width on the different activation functions and weight initializations. We plot the final training loss achieved for each model and the minimum gradient cosine similarities calculated over the 1000 pairs of gradients at the end of training. For each point, we plot both the mean and the standard deviation over the 10 independent runs.
The effect of depth. We first present results showing the effect of network depth. We considered a fixed width of f = 100, and varied the depth of the neural network, on the log scale, as:
3 EEl (3, 10, 30, 100, 300, 1000).
Figure 5 shows results neural networks with identity and tanh activation functions for the two weight initializations considered (Glorot normal and LeCun normal). Similar to the experimental results in section 5, and matching our theoretical results in section 4, notice the consistent trend of gradient confusion increasing with increasing depth. This makes the networks harder to train with increasing depth, and this is evidenced by an increase in the final training loss value. By depth
15

---

Under review as a conference paper at ICLR 2020
1000, the increased gradient confusion effectively makes the network untrainable when using tanh -on-lincarities.
The effect of width. We explored the effect width by varying the width of the neural network while keeping the depth fixed at 300. We chose very deep model, which is essentially untrainable for small widths (with standard initialization techniques) and helps better illustrate the effects of increasing width. We varied the width the network, again on the log scale, as:
E {10, 30, 100, 300, 1000}.
Crucially, note that the smallest network considered here, MLP-300-10, still has more than 50000 parameters (i.e., more than the number training samples), and the network with width / = 30 has almost three times the number of parameters the high-performing MLP-3-10 1-00 network considered in the previous section. Figure 6 show results on linear neural nets and neural nets with tanh activations for both the Glorot normal and LeCun normal initializations. As in the experimental results of section 5, we see the consistent trend of gradient confusion decreasing with increasing width. Thus, wider networks become easier to train and improve the final training loss value. We further see that when the width is too small (E = 30), the gradient confusion becomes drastically high and the network becomes completely untrainable.
35
(a) Linear NN, Glorot init (h) Linear NN, Glorot init (c) Linear NN, LeCun init (d) Linear NN, LeCun init
dach
(e) Tanh NN, Glorot init
(I) Tanh NN, Glorot
(g) Tanh NN, LeCun init
(h) Tanh NN, LeCun init
Figure Effect of varying depth on MLP-8- 10000
(a) Linear NN, Glorot init (b) Linear NN, Glorot init (c) Linear NN, LeCun init (d) Linear NN, LeCun init
w0th
with
(c) Tanh NN, Glorot init
(I) Tanh NN, Glorot
(g) Tanh NN, LeCun init
(h) Tanh NN, LeCun init
Figure 6: Effect of varying width on M
16

---

Under review as a conference paper at ICLR 2020
A.2 ADDITIONAL EXPERIMENTAL DETAILS FOR CNNS AND WRNS
In this section, we review the details of our setup for the image classification experiments on CNNs and WRNs on the CIFAR-10 and CIFAR- 100 datasets.
WIDE RESIDUAL NETWORKS
The Wide ResNet (WRN) architecture (Zagoruyko & Komodakis, 2016) for CIFAR datasets is a stack of three groups of residual blocks. There is downsampling layer between two blocks, and the number of channels (width of convolutional layer) doubled after downsampling. In the three groups, the width of convolutional layers is {166, 32C, 64é), respectively. Each group contains 3, residual blocks, and each residual block contains two 3 3 convolutional layers equipped with ReLU activation, batch normalization and dropout. There is a 3 x 3 convolutional layer with 16 channels before the three groups residual blocks. And there is a global average pooling, fully-connected layer and softmax layer after the three groups The depth of WRN is 6,, 4.
For our experiments, we turned off dropout. Unless otherwise specified, we also turned off batch normalization. We added biases to the convolutional layers when not using batch normalization to maintain model expressivity. We used the MSRA initializer (He et al., 2015) for the weights as is standard for this model, and used the same preprocessing steps for the CIFAR images as described in Zagoruyko & Komodakis (2016). This preprocessing step involves normalizing the images and doing data augmentation (Zagoruyko & Komodakis, 2016). We denote this network as WRN-3-E, where represents the depth and é represents the width factor of the network.
To study the effect of depth, we considered WRNs with width factor & and depth varying as:
8 {16. 22, 28, 34, 40, 52, 76, 100).
For cleaner figures, we sometimes plot subset of these results: 3 E (16, 28, 40, 52, 76, 100). To study the effect width, we considered WRNs with depth 3 = 16 and width factor varying as:
E {2, 2,5,44
CONVOLUTIONAL NEURAL NETS
The WRN architecture contains skip connections that, as we show, help in training deep networks. To consider VGG-like convolutional networks, we consider family of networks where we remove the skip connections from WRNs. Following the WRN convention, we denote these networks as CNN-3-E, where 3 denotes the depth and É denotes the width factor.
To study the effect of depth, we considered CNNs with width factor = 2 and depth varying as:
B E {16, 22, 28, 34, 40).
To study the effect width, we considered CNNs with depth 3 = 16 and width factor varying as: E {2, (2,
HYPERPARAMETER TUNING AND OTHER DETAILS
We used SGD as the optimizer without any momentum. Following Zagoruyko & Komodakis (2016), we ran all experiments for 200 epochs with minibatches of size 128, and reduced the initial learning rate by a factor of 10 at epochs 80 and 160. We turned off weight decay for all our experiments.
We ran each individual experiment 5 times. We ignored any runs that were unable decrease the loss from its initial value. We also made sure at least 4 out of the 5 independent runs ran till completion. When the learning rate is close the threshold at which training is still possible, some runs may converge, while others may fail to converge. Thus, these checks ensure that we pick learning rate that converges reliably in most cases on each problem. We show the standard deviation across runs in our plots.
We tuned the optimal initial learning rate for each model over a logarithmically grid:
(10*, xx 10 10" x 10 100111111000 10 1002
x 10 -3 1003,33 10 1,10'' 1,-1,3 10 -0-),
17

---

Under review as a conference paper at ICLR 2020
24
4.0
tha fost sit SCCUBII
traiiinining losp
depti
1.5
00
depth 14
depth 42
$212
depth
Figure 7: The effect of network depth with CNN-8-2 on CIFAR-10. 10. Left plot: final training loss values at the end of training. Middle plot: final test set accuracy values the end of training. Right plot: curves showing the minimum of pairwise gradient cosine similarities during training.
witth
firal traiting los
witth
6.00
mi
Iayer withh
lnyer with
apocts
Figure 8: The effect of width with CNN-16-E on CIFAR-10. Left plot: final training loss values at end training, Middle plor: final test set accuracy values at the end of training. Right plot: curves showing the minimum of pairwise gradient cosine similarities during training.
and selected the that achieved the lowest final training loss value (averaged the independent runs). Our grid search was such that the optimal learning rate never occurred at one of the extreme values tested. We used the standard train-valid-test splits of 40000-10000-1000 for CIFAR-10 and CIFAR-100.
To measure gradient confusion, at the end of every training epoch, we sampled 100 pairs of mini- batches each of size 128 (the same size as the training batch size). We calculated gradients on each mini-batch, and then computed pairwise cosine similarities. To measure the worse-case gradient confusion, we computed the lowest gradient cosine similarity among all pairs. We also show the kernel density estimation of the pairwise gradient cosine similarities of the 100 minibatches sampled the end of training (after 200 epochs), to see the concentration of the distribution. To do this, we combine together the 100 samples for each independent run and then perform kernel density estimation with a gaussian kernel on this data.
A.3 ADDITIONAL PLOTS FOR CIFAR- 10 ON CNNS
In section 5, we showed results for image classification using CNNs on CIFAR-10. In this section, we show some additional plots for this experiment. Figure 7 shows the effect changing the depth, while figure 8 shows the effect of changing the width factor of the CNN. We see that the final training loss and test set accuracy values show the same trends as in section deeper networks are harder to train, while wider networks are easier to train. As mentioned previously, theorems 3.1 and 3.2 indicate that we would expect the effect of gradient confusion to be more prominent near the end of training. From the plots we see that deeper networks have higher gradient confusion close to minimum, while wider networks have lower gradient confusion close to the minimum.
A.4 CIFAR-100 ON CNNS
We now consider image classifications tasks with CNNs on the CIFAR-100 dataset. Figure 9 shows the effect of varying depth, while figure 10 shows the effect of varying width. We notice the same trends as in results with CNNs on CIFAR-10. Interestingly, from the width results in figure 10, we see that while there is no perceptible change to the minimum pairwise gradient cosine similarity, the distribution still sharply concentrates around 0 with increasing width. Thus more gradients become orthogonal to each other with increasing width, implying that SGD on very wide networks becomes closer to decoupling over the data samples.
18

---

Under review as a conference paper at ICLR 2020
Seath
Seath
Seath
[na) Panio 82
3.4
mIn Oreet COULTE NITH
Seoth 34
-0.4 -0.2
3.0
0.2 3
SCtWOrk depth
patrmise gradient cosine similrity
Figure 9: The effect of network depth with CNN-8-2 CIFAR 100. Left plor: training loss values at the end of training. Middle plot: minimum of pairwise gradient cosine similarities at end training. Right plot: kernel density estimate of the pairwise gradient cosine similarities at the end of training.
Thin gredt cans sirileeity
traiiiggnggg loss
with
wilth
simdurity
Figure 10: The effect of width with CNN-16-E on CIFAR-100 Left plot: training loss values at the end of training. Middle plor: minimum of pairwise gradient cosine similarities at the end of training, Right plor: kerne density estimate of the pairwise gradient cosine similaritics at the end of training.
A.5 IMAGE CLASSIFICATION WITH WRNS ON CIFAR-10 10 AND CIFAR-100
We now show results for image classification problems using wide residual networks (WRNs) CIFAR- 10 and 100.R-100. The WRNs we consider do not have any batch normalization. Later we show results the effect of adding batch normalization these networks.
Figures 11 and 12 show results on the effect of depth using WRNs on CIFAR-10 10 and CIFAR-10K respectively. We again see the consistent trend of deeper networks having higher gradient confusion, making them harder to train. We further see that increasing depth results the pairwise gradient cosine similarities concentrating less around O.
Figures 13 and 14 show results the effect of width using WRNs on CIFAR-10 and CIFAR-100 respectively. We see that increasing width typically lowers gradient confusion and helps the network achieve lower loss values. The pairwise gradient cosine similarities also typically concentrate around 0 with higher width. We also notice from these figures that in some cases, increasing width might lead to diminishing returns, i.e., the benefits of increased width diminish after certain point, one would expect.
A.6 EFFECT OF BATCH NORMALIZATION
In section 5 we showed results on the effect of adding batch normalization to CNNs and WRNs on an image classification task on CIFAR-10. In this section, present similar results for image classification on CIFAR-10W 100. Similar to section 5, figure 15 shows that adding skip connections or batch normalization individually help training deeper models, but these models still suffer from worsening results and increasing gradient confusion as the network gets deeper. Both these techniques together keep the gradient confusion relatively low even for very deep networks, significantly improving trainability of deep models.
B NEAR ORTHOGONALITY OF RANDOM VECTORS
For completeness, we state and prove below lemma on the near orthogonality of random vectors. This result is often attributed to Milman & Schechtman (1986).
19

---

Under review as a conference paper at ICLR 2020
-1.0
depth
mm gred coutte simterty
-1.10
depth 52
depth-40
(Tra training lo6s
desth 76
-0.13
depch 100
70 n2twwrk: Sc
-0.4
-0.2
3.0
0.2 3
n2b6ork 0ppth
patrmise gradient cosine sinilaityy
Figure 11: The effect of depth with WRN-8-2 (no batch normalization) CIFAR-I0. Left plot: training loss values at end of training. Middle plot: minimum of pairwise gradient cosine similarities the training. Right plot: kernel density estimate of the pairwise gradient cosine similarities at the end of training.
-1.4
depch
100
depch
depci
depth
Indtranin
depth
-.114
-.14
137
50
60
1.0
73
-220 -6.5 -0.2 -0.3
0.35
0.55
3.0 0.35 3.20
networkk depth
meetwork death
painddse gradient costne siilanity
The effect of depth with WRN-3-22 (no batch normalization) CIFAR-100. Left plot: training loss values at the end training. Middle plot: minimum of pairwise gradient cosine similaritics at the end of training, Right plor: kernel density estimate of the pairwise gradient cosine similarities at the end of training.
Figure 12:
Lemma B.1 (Near orthogonality of random vectors). For vectors {xi {xi]iE[N] drawn uniformly from a unit sphere in d dimensions, and > 0,
Pr E X x5} > v)
S N2 V exp ( 2 v2).
d=1v2).
Proof. Given fixed vector a uniform random vector satisfies |x y| 2 only if y lies in one two spherical caps: one centered at x and the other at -x, and both with angular radius cos pos="(>) < A simple result often attributed to Milman & Schechtman (1986) bounds the probability of lying in either of these caps as
d - 2
Pr[[x y 2 S
exp
22
(5)
2
Because of rotational symmetry, the bound (5) holds if both x and y chosen uniformly random.
We next apply a union bound to control the probability that |x]]x, x;ı 2 v for some pair (1. There are fewer than N2 /2 such pairs, and so the probability of this condition is
2
π
d - 22
Pr[|x] xy} v, for some i. <
exp
2
2
C LOW-RANK HESSIANS LEAD TO LOW GRADIENT CONFUSION
In this section, slightly elaborate the argument that low-rank random Hessians result in low gradient confusion. For clarity in presentation, suppose each ft has minimizer at the origin (the same argument can be easily extended the more general case). Suppose also that there is Lipschitz constant for the Hessian of each function fi that satisfies HH [W() H. (ww")) L ||w w'll Then V fe (w) H.w + e, where e an error term bounded as: ||e|| 1 LH and we use the shorthand H, to denote (0) Then we have:
KV (w),, Vff(w))) = [(H H w + (e. H.w + H,w) ||||
|w|
H
|| + |e
w H + |H,|] II) + ||||
|||
H
Ln
|
H II) + + Lz llwls.
20

---

Under review as a conference paper at ICLR 2020
Ana soiliig kos
grad NiTr
420 -6.5 -012 -0.2 0os
0.65 0.00 0.35 326
Tayer width
Isyer witth
paindtse gradient costne siilority
Figure 13: The effect of width with WRN-16-E (no batch normalization) CIFAR-IO. Left plor: training loss values at the end training. Middle plot: minimum of pairwise gradient cosine similaritics at the end of training, Right plor: kernel density estimate of the pairwise gradient cosine similarities at the end of training.
th gredd contre NITHE anthy
final trahingg lose
watth
width
pairaise gradient simiantty
Figure 14:
The effect of width with WRN-16-E (no batch normalization) on CIFAR 1000 Left plot: training loss values at the end of training. Middle plot: minimum of pairwise gradient cosine similarities at the end of training, Right plot: kernel density estimate of the pairwise gradient cosine similarities the end of training.
If the Hessians are sufficiently random and low-rank (e.g., of the form H, a,a, where a, RR-xr are randomly sampled from a unit sphere), then one would expect the terms in this expression to be small for all w within neighborhood of the minimizer. Given that has been observed that many standard neural nets have low rank Hessians at the minimizer, this indicates that the gradient confusion might be low for a large class of weights near the minimizer for these models.
D MISSING PROOFS
D.1 PROOFS OF THEOREMS 3.1 AND 3.2
This section presents proofs for the convergence theorems of SGD presented in section 3, under the assumption of low gradient confusion. For clarity of presentation, we re-state each theorem before its proof.
Theorem 3.1.
If the objective function satisfies (AI) and (A2), and has gradient confusion πj, SGD with updates of the form (2) converges linearly to neighborhoud of the minima of problem (1) as:
E(F(wT) - [F] p= (FF(oo))))) - F
2u where a N.. p # (a
NLo² F+ minw F(w) and wo is the initialized weights.
Proof. Let i [N] denote the index of the realized function fx in the uniform sampling from (fi)eeN) at step k. From assumption (A1), we have
F(W++1) S F(WA) + (WF(W)), Wk+1 -wa) + W -
w
Lax
=(ww) a(VF(Ww) (Wx). [f((w))) +
2
= F((w)) a Laz [/ Σ (VS((w)), f(a())
N
Wirighi
< F(wW) a
La² |[
a(N 1)n
N
N
21

---

Under review as a conference paper at ICLR 2020
mmn grad CONTT sime Aameyay
foaltus Get accuracy
feaitthinn lass
154
2 2
skpp
33
2
network degth
NEtwork depth
network depth
Figure 15: The effect of adding skip connections and batch normalization CNN-3-2 on CIFAR-100. Plots show the training loss, minimum pairwise gradient cosine similaritics, and test accuracics at the end of training.
F(ws) - (N= )
La²
(w))) + om))
where the second-last inequality follows from definition 2.1. Let the learning rate < 2/NL. Then, using assumption (A2) and subtracting by F* = min F(w) on both sides, we get
La (f.(w))) fh) an,
F(WR+1) F S F(We) F 2/ N
where ft= = minw (w)). It is easy see that by definition have, [[[[[]] S F*. Moreover, from
assumption that NL. it implies that [ _La") O. Therefore, taking expectation both
sides we get,
F((++1) - F*] $ (1
2pa N
+ uTaa (dLaa)R[F(wa)) [[F((w)) - F*) an-
Writing p p= 1 3n0 N + pLa², and unrolling the iterations, we get
k
E[F(w++1) FM) / k+1 (F((o) - FF) +
Σ
p om
i=0
S (F(wo))
- FF) + Σ
plom am
p
1=0
= -F(L)(F(Wo))
F*) + 1
Theorem 3.2. the objective satisfies (Al) and has gradient confusion bound 1), then SGD converges to neighborhood of a stationary point as:
mink=I.... E RF (WFF(
)12 p(F(W))-F1) pM)
for learning rate < NT. P 2 Laa and F minw F(w).
2N
Proof. From theorem 3.1, we have:
F(WE+1) S F(ww)) (1- La² [/ + an..
(6)
Now we know that: E| f == V (Wk) - B/
Thus, taking expectation and assuming the step size < 2/(NNN) can rewrite equation 6 as:
2N
2Nr
V F 1
2a B[F(WL) F F(W + 2 N-LL
2a
Taking average over 7 iterations, and using F* = min F(w), we get:
min E VF
< T Σ
V 2a NLa²
2N F(w1) F
+
2N
T
2 NLa
22

---

Under review as a conference paper at ICLR 2020
D.2 PROOFS HELPER LEMMAS
Lemma D.I. Consider the set of loss-finntiios ( HEIN: where all ft are either the square-loss fincciin or the logistic-loss function. Consider a feed-forward neural network as defined in equation whose weights W satisfy assumption I,. Consider the gradient W Ie (W) (WW) of each function fo Note
(W)Wwwll that we can write V Vw fWW =x, (W) WVWww(xx (x:), where we define Cx. (W) Of((W)/Ogw. Then we have the following properties.
1. When ||x|| we have V (x:)ll S
2. There exists a constant So > such that 16x (W) S 2, Sx, (W)ll2 S So. Vx (W))22 S So-
We show that So S 2/B, where 3 is the depth of the neural network.
Proof. Let W denote the tuple peE Consider [xx [W) (0f((W) (W)/Ogwl. In the case
of square-loss function this evaluates to (xw(x) - C(x) I 2. In case of logistic regression, this
evaluates to [xexpt((x))wwxx I 1. Now we consider
V Sx. (W)ll- Consider the squared loss
function. We then have the following.
Gx (W)ll =
= (w( C(x:)]
S 9w (x,))++1.
Likewise, consider the logistic-loss function. We then have the following.
C(x,)²
(1 + (xxp(((x))9(xxx))) exp(C(x))gwxxx) (xx)) (w
Sx,
< V Vw (x,)
Thus, it suffices bound Vv. (x;) ||- Using assumption and the properties (P1), (P2) of this can be upper-bounded by 1.
Consider Vw, Sx, (W) for some layer index p [3]n- We will show that Vw, Sx. (W)l2 s 2. Then immediately follows that V>, (W)ll2 2/3. In the case of squared loss function. We have the following.
Ww, (W)l VV (W)I VW. (x:) - C(x))]
< V WWww (x;))l( +1
Likewise, consider the logistic-loss function. We then have the following.
C(x,)²
exp(C(x:)gw (x:)) (w,,w(xx))
Sx, (W)Ll
(1 + exp(((( (x;
< Ww, (x;)
Since |/ (x,))
< 1, we have that (W)) < 2 in both the cases. Thus, Co
2/B.
D.3 PROOFS OF THEOREM 4.1 AND COROLLARY 4.1
In this section, we will analyze the case when we have non-linear activations at each layer.
Theorem 4.1. Consider the problem of training neural nets (equation 4) using either the square-loss
or the logistic-loss function. Let 1) >> 0 be a given constant. Let the weights satisfy assumption 1 and the non- non-linen aon-linearities in each layer satisfy properties (PI) and (P2). For some fixed constant c: >> O, the gradient confusion bound equation holds with probability least
N exp
cody?
T6C4 (++
For both the square-loss and the logistic-loss functions, Co 2 (from lemma D.. 1).
23

---

Under review as a conference paper at ICLR 2020
Proof. We show two key properties. namely bounded gradient and non negative expectation. We will then use both these properties to complete the proof.
Bounded gradient. For every E [n]] define &x, (W) (W) For every p [8] define Hp as follows.
Hp(x) == (W, of (W p-1 a(.... .......0.. (Wu-x x)...)
Fix an i [N]. Then we have the following recurrence
go((,) == o' dHH((x)))
8p(x,) == (Wp+1 (x))(x;)) Diag(o' (x,())))
Vp E {0, ,0.., 1}.
Then the gradients can be written in terms of the above quantities as follows.
Vi, (o,[((W] (W) (x() Hp. (x;)
vp E 33]0-
We can write hw (x,, x,) follows.
Sx (W)),, (W)
Tr HT(H,-I(X)) (x,) (x)) H Hp-1(x:)
pE/S/o
We will now bound (xxxx))) (x,, (xx, x1) follows.
Consider Vx, (x,, This can be written as
(xx,Gx(W))) (W)) (W) (W)
Tr Tr (x))p(((x) Bx(xx) 8p(x,)) Hx-1(x))7)
PE|SIO
Sx. (W) (W)
Vx. (Hp- gp(x)) gx(x,) H. Hx-1(x)))]*
(8)
p
Observe that each of the entries in the diagonal matrix Diag(o (H,(()))) is at most 1. Thus, have that Diag(o' (iiag(o (x:))) < 1.
We have the following relationship.
(x.)(x))1 <
(x.)ll < [WT p+1
S
Vp (0, 1,,
Moreover we have,
Tr (x) Ep
(x)) s 1. S | (Il
Consider Vx, (x,) (x:) (x(x)) Hx,1(x:)) for every p E [3]o-
This can be upper-bounded by,
|/V I g, (x.) (1tp:///lllllccllllls///////////
V 8p (x,) T || H (x))
Note that Vx, Hp-1
(<)))]))((()))) x:)) W gp (x,) T. Thus, | H (x,) )| 1.
g1 (x:) Diag(
We will now show that Vx. (x.) when p B.
< 1 We prove this inductively. Consider the base case
V [x| ||
V σ (H₂(x:))
3 B 1.
Now, the inductive step.
- 1. V x. Sp (xx)) < V (xx)) + |V, Diag(o (HH,HHH))) 3pp
Thus, using equation 8 and the above arguments, we obtain, V /w (x)12 CB 1) CB 1) 2) < 2ç (3 2) and thus, (V.x,,,) (x; x,)112 4C3(3 (/13++20 22
24

---

Under review as a conference paper at ICLR 2020
Non-negative expectation.
Ex, x, [h(x,, xy)] =Ix, ((V fi W)) (W)))
[Fxx ) Rx, [W)[))))
||Ex, [.:(W)]]l' 2 0.
We have used the fact that (W) and Vfz W) are identically distributed and independent.
Concentration of Measure. We combine the two properties as follows. From Non-negative Expectation property and equation 23, we have that
cdn2 Pr(hw (x,, x,) S -n) & (x,, (x,, x3) S E (xx,,x,) (x)x nl S exp 16C8 + 2)
To obtain the probability that some value (V [i, VwJj) lies below -7, we use a union bound. There are N (N 1)/2 < 222 possible pairs of data points to consider, and this probability is ody"
bounded above by N2 exp 1657
Li
D.3.1 PROOF OF COROLLARY 4.1
Before we prove corollary 4.1 prove the following helper lemma.
Lemma D.2. Suppose maxw W fa (W)l I M, and both Wifw(W and V (W) are Lips- chitz in W with constant L. Then hw (x, X²) is Lipschitz in W with constant 2LM.
Proof. We view W as flattened vector. We now prove the above result for these two vectors. For two vectors w, w',
how (x;, hw xx,,,,)
KVWf((w), V [w]) (V fi('), V ((wW))
(VwSe(w) Wwrf((W) + V. (ww'( V. (w))
(V fs(w), (w Vw.f + V [w))
WV (w)) Wirf((w). (w))(w)) (V fiw'), V fw'' - V (w))
V wifi ((())((w)))))))))(())
(
fww') - (w)f(w))]
V w Si( w) - www/ [|]ll/ [W - (wfs(w)]
L|W w VIllII /V> w|l
S 2LM WWWll w'Il-
Here the first inequality uses the triangle inequality, the second inequality uses the Bluuch-SShwaare inequality, and the third and fourth inequalities use the assumptions that V fi() and V W (w) are Lipschitz in w and have bounded norm.
We are now ready to prove the corollary, which we restate here. The proof uses standard "epsilon-net" argument; we identify a fine net of points within the ball B,, If the gradient confusion small at every point in this discrete set, and the gradient confusion varies slowly enough with W, when we can guarantee small gradient confusion at every point B,.
Corollary 4.1 (Uniform concentration for all weights around the minimizer). Select a point W (Wo, W Wi...., W)). satisfying assumption Consider a ball B, centered W of radius r >> 0. If the data {xstig are sampled uniformly from a unit sphere, then the gradient confusion bound in equation 3 holds uniformly at all points W' E B, with probabiliyy at least
- N2 22 exp
odn"
ifr if n/43.
(1c3))
- N exexp
+ 8dcar
otherwise.
25

---

Under review as a conference paper at ICLR 2020
Proof. Define the function h (W) max;; hww xx,,,)) Our goal is find conditions under which h" (W) > -17 for all W in large set. To derive such conditions, we will need a Lipschitz constant for h (W), which is no larger than the maximal Lipschitz constant of (w(x,,x) for all i. We have that | w fall = ||6x; (W)x;ll S Çn- Now we need to get a W-Lipschitz constants w<, (W))x; S Ço- Using lemma D.2, we see that 2 is a Lipschitz constant for /ww (X, Xz), and thus also ht (W).
for V Gx: [W)x; Jx, By lemma D.I, have V (Gx, (W)x))|
Now, consider a minimizer W of the objective, and ball B, around this point of radius r. Define the constant - and create an e-net of points N,, = {W:} inside the ball. This net is sufficiently dense that any W' E B, is at most e units away from some W, E N₁, Furthermore, because h+ (W) is Lipschitz in W, 1h* (W") - h- -h"(W.)) 2Ç = n/22
We now know the following: we can guarantee that
ht (W,) 2 -/22, for all W, E.,,
(10)
then we also know that h+ (W" 2 -7 for all W B,. For this reason, prove the result by bounding the probability that (10) holds. It is known that NR can be constructed so that | S (2r/c 1 (8Grr/ + 1)d (see Vershynin (2018), corollary 4.1.13). Theorem 4.1 provides bound on the probability that each individual point in the net satisfies condition (10). Using a union bound, we see that all points in the net satisfy this condition with probability at least
1 1 1-N² 8C8
+1 exp (-
cd(nn2222
(- 1666
(11)
cdn² 64Ç
= 1 - N exp(d logdddog(@@000 ( + 1)) exp
(12)
(-
(_odhp
odip
2 1 - 2 cxp exp((8((3//10 exp
(13)
64Ç3
(_edn² edn2
8dL,"
N exp
(14)
64ç0
Finally, note that, r e, then can form net with [& 1. In this case, the probability of satisfying (10) is at least
N2 exp (- _cd(n/2)2
D.4 PROOF OF THEOREM 4.2
Theorem 4.2 (Neural nets with randomly chosen weights). Let Wo. Wi...., Wg be weight matri- ces chosen according to strategy 4.1. There exists fixed constants C1, C2 > 0 such that we have:
1. Consider fixed but arbitrary dataset X2........ with ||x,| S for every i [N]. For
1) > 4, the gradient confusion bound in equation 3 holds with probability at least
1 1 exp (-cix²() 22
GAC. GACH
2. If the dataset (x; IEE[ is such that each x; is an i.id. sample from the surface of d- dimensional unit sphere, then for every >> the gradient confusion bound in equation 3 holds with probability least
1 Bexp (-cnk2 2 exp
-c2(kd+
)
1363(3+2)
Both parts in theorem 4.2 depend on the following argument. From theorem 2.3.8 and Proposition 2.3.10 in Tao (2012) with appropriate scaling', we have for p 1, 3 we have that the matrix
norm W, < with probability at least 3 exp - and WWll < with probability at
least 1 - exp (-) when the weight matrices are initialized according to strategy 4.1. Thus,
'In particular, each entry has he scaled by for matrices (W, }pE(M] and 1/2 for the matrix Wo.
26

---

Under review as a conference paper at ICLR 2020
conditioning this event it implies that these matrices satisfy assumption 1. The proof strategy is similar to that of theorem 4.1. We will first show that the gradient of the function h(.,.) as defined in equation (7) with respect the weights is bounded. Note that in part (1) the random variable is the set of weight matrices (Wp) ppetp- Thus, the dimension used to invoke theorem E. 1.1 is at most 3. In part (2) along with the weights. the data x E IR is also random. Thus, the dimension used to invoke theorem E. is at most &d + g. Combining this with theorem E.1, the bound on the gradient of ((.,-) and taking a union bound, we get the respective parts of the theorem. Thus, all it remains to prove the bound on the gradient of the function h(.,,) as defined in equation (7) with respect the weights conditioning the event that |[W,] pll I 1 for every p (0,1,...,,).
We obtain the following analogue of equation (8).
(Vwsx. (W))se, (W)
Σ nE(A]o
Tr (x;) (x)()) H (xx)
(WWG, (W)),x (W)
Σ
Tr Tr(Hp-1(X)) (x:) [x(x)) Hp- +
pE(a]o
Sx. (x (W)
Σ
Vw (Hp-i(xi) (x,) (x3))) Hxpi(x))]] (15)
PE|O
As in the case of the proof for theorem 4.1, we will upper-bound the norm of the above expression. In particular, show the following.
(VWGe,
Σ pE/ATo
Tr(Hp-I (axxx)).p(xx)) (x(x)) -x
HH,-Hp- Hx-1(xx)7]
|1 S 26 2)².
(16)
| [[WGs, (W))Gx, (W)
Σ
Tr Tr (x,) (x,),) 8x(x)) Hx=1(x:
11
S S
pE|ATO
(17)
(W)Gx,
Σ
Vw (Hp-1(x;) (xx))xxxxx)))))))))) (x,) gx(x)) (x:)(
11, s 4C 22)
(18)
Equations (16) and 17 follow from the the fact that [[ (W)) < Co and the arguments in the proof for theorem 4.1. We will now show the proof sketch for equation (18). For every p [3]o- consider V (Hp-1 (x:) (x.) (x)(x)) Hx:1(x;)) ||. Using the symmetry between x; and Xj, the expression can be upper-bounded by.
2|| W (x,) (x;) [ll,,, (x, (x]) V (x, I1ll,,, (x,, || Hp- (x:)
As before we can use an inductive argument to find the upper-bound and thus, we obtain the following which implies equation (18).
V (Hp-1(x,) (x(x)) (x(x) (x;)) || - 4(3 2)
Next, we show that the expected value can be lower-bounded by -4 as the case theorem 4.2 above. Combining these two gives us the desired result. Consider Ew (x; We compute this expectation iteratively as follows.
Ew [ow ( x,)
Ew, Ew.[Ewl [Ew,l.. Ewa //i (x;, x;]]
2 -4EW.
Ew,
Ew
Σ
Tr(H--1 (x1)) 8x(x)) H Hx-1(x)))
PE(A)
27

---

Under review as a conference paper at ICLR 2020
The inequality combines Eq. (7) with Lemma D.1. We now prove the following inequality.
Ew
Ew,
Ew,
Σ
1r(Hp-1(x)) (x,) gx(x)) Hp (xx)
S
(19)
PE|SO
Consider the inner-most expectation. Note that the only random variable is W.. Moreover, the term inside the trace is scalar. Note that the activation function satisfies [o'(z) S 1. Using the linearity of expectation, the LHS in equation (19) can be upper-bounded by the following.
Ew
Ew, ... E....
[r(H 3 (-)(x) Hx-1(x;: ]]]]
(20)
Ewo
[wi, ... ..w,
TT(H--((x)) (x())) T (x(()) Hp- (x:) (x]]
(21)
rE(Ab)(())
The first sum in the above expression can be upper-bounded by 1, since (a(x)) 1. We will now show that the second sum is Consider the inner-most expectation. The weights W appears only in the expression gp (x;) (x))) Moreover, note that every entry W9 is an i.i.d. normal random variable with mean 0. Thus, the second summand simplifies to,
Ew
Ew,
Ew p-1
Tr(Hp-1(x)) (x(x,) (x())) Hx,1(x;) D]]] pE
Σ
Applying the above argument repeatedly obtain that the second summand (equation (21)) is 0. Thus, we obtain the inequality in equation (19) which implics that Ew/hw((n x,)] 2 -4.
E TECHNICAL LEMMAS
We will briefly describe some technical lemmas we require in our analysis. Chernoff-style concentration bound is proved in Chapter 5 of Vershynin (2018).
The following
Lemma E.1 (Concentration of Lipshitz function over sphere). Let Rdd be sampled uniformly from the surface of a d-dimensional sphere. Consider a Lipshitz function Rd - IR which is
differentiable everywhere. Let V|[2 denote suPxER= [|[[(x)]]2. Then for any 2 0 and some fixed
constant e 2 0, we have the following.
(- edt2
Pr [e(eex)) B[((x)] 2 S 2exp
(22)
12
where p 2 ||V
We will rely on the following generalization of lemma E.1. We would like to point out that the underlying metric is the Euclidean metric and thus we use the n-
Corollary F.I. Lei x, E RRd two mutually independent vectors sampled uniformly from the surface of d-dimensional sphere. Consider Lipshitz function & Edd x Rd + R which is differentiable everywhere. Let [[Vel|2 denote sup(x,y) xxd [| y)122 Then for any 2 0 and some fixed constant 2 0, we have the following.
(_ cdl2
Pr - -(e(x,)) 21 < 2exp
(23)
p
where p 2 ||
Proof. This corollary be derived from lemma E. as follows. Note that for every fixed ý Rd. equation 22 holds. Additionally, we have that the vectors x and y are mutually independent. Hence we can write the LHS of equation 23 as the following.
=00
2000
Pr [exx.v)
B[((x, v)1 2t y y
(())d(")....d d(})a.
(8)
18)==000
28

---

Under review as a conference paper at ICLR 2020
Here ( refers to the pdf of the distribution of y. From independence, the inner term in the integral evaluates to Pr [(x. - E[e(x, 8)] 2 t). We know this is less than or equal to 2 exp
cdt²
[
Therefore, the integral can be upper bounded by the following.
100=00
a=
( [TIVeL])
odd2
2 eexp
1-)=-000
15)==-00
Since (()) is a valid pdf, we get the required equation 23.
Additionally, we will use the following facts about a normalized Gaussian random variable.
Lemma E.2. For a normalized Gaussian x (i.e., an x sampled uniformly from the surface of a unit d-dimensional sphere) the following statements are true.
1. Vp E [d] we have that Ex ] = 0.
2. Vp [d] we have that [x = 1/d.
Proof. Part (1) can be proved by observing that the normalized Gaussian random variable is spherically symmetric about the origin. In other words, for every E [d] the vectors (x), T2, ;2,,..,; Tp.. ..p....,Tel (d)) and (I,, (2,,,2, Tpp...,aal aa) are identically distributed. Hence E[zp] =
B[-r,] which implies that E[z,] 0.
Part (2) can be proved by observing that for any p.p' E [d]. Tp and Ey are identically distributed. Fix any E [d]. We have that Epreja) Bi = x E[ Note that we have
(x)1=00
(x)
Eve(d (dd oi Exne(d ai.
E
((x))d(x)) .(x)) 1.
(x)x==o
P'E|d
(x)==000
Therefore [[2]]] = 1/d.
We use the following well-known Gaussian concentration incquality in our proof's (e.g. Chapter 5 in Boucheron al. (2013)).
Lemma E.3 (Gaussian Concentration). Let (I1, 22, ... F.) be i.i.d. NN v²) random vari- ables. Consider a Lipshitz function suPxERd [V((x)]2. Then for any i 0, we have the following.
Linshitsfunction ε RRd + I which is differemtialle everywhere. Let [ denote
82
Pr [(x) -r(((())B(((x)) E[((x)] 21 []]=22=_2) 2exp
(24)
2v 2v2p2
where p 2 ||Ve|12.
F ADDITIONAL DISCUSSION OF THE SMALL WEIGHTS ASSUMPTION (ASSUMPTION I)
Without the sealh- assumption, the signal propagated forward or the gradients V V fa could potentially blow up magnitude, making the network untrainable. Proving non-vacuous bounds in case of such blow-ups in magnitude of the signal or the gradient is not possible in general, and thus, we assume this restricted class of weights.
Note that the small-weights assumption is not just theoretical concern, but also usually enforced in practice. Neural networks are often trained with weight decay regularizers the form Σ, || which keep the weights small during optimization. The operator norm of convolutional layers have also recently been used as an effective regularizer as well for image classification tasks by Sedghi al. (2018).
29

---

Under review as a conference paper at ICLR 2020
In the proof of theorem 4.2 showed that assumption holds at initialization with high probability. While, in general, there is no reason to believe that such a smigh- assumption would continue to hold during optimization without explicit regularizers like weight decay, some recent work has shown evidence that the weights do not move too far away during training from the random initialization point for overparameterized neural nets (Neyshabur et al., 2018; Dziugaite & Roy, 2017: Nagarajan & Kolter, 2019; Zou et al., 2018; Allen-Zhu et al., 2018; Du et al., 2018; Oymak & Soltanolkotabi, 2018). is worth noting though that all these results have been shown under some restrictive assumptions, such as the width requiring to be much larger than generally used by practitioners.
30


Reviews:
[{"review_id": "ryeWNy9pFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\n[Summary]\nThis paper introduces gradient confusion, a bound on the negated dot product of gradients at two data points, and studies its effect on the optimization of neural networks with SGD. If gradient confusion is high, reducing the loss on one data point with SGD increases it on another data point. Theoretical results show that (1) with a fixed learning rate, lower gradient confusion results in faster learning, and (2) increasing the width and decreasing the depth of a network reduces gradient confusion. The experiments corroborate these findings and also show that batch normalization and skip connections can reduce gradient confusion and speed up the training. \n\n[Decision]\nI vote for accepting this paper. Although most of the results mirror classical bounds that considered gradient variance, the introduced measure allows analyzing the speed of learning even if gradient variance itself is unbounded or hard to analyze. This can help with understanding the current architectures and designing new ones with desirable properties. \n\n[Comments]\nTheorem 3.1 shows that, for a constant learning rate, gradient confusion controls the SGD noise floor. If the noise floor is small, convergence to a low error is possible with a larger learning rate, and this seems to be why reducing gradient confusion speeds up SGD. In the experiments, I would expect that the chosen learning rate for networks with low gradient confusion would generally be higher. Reporting the best learning rate schedule for each network can clarify if this is true.\n\nAre the effects of width, depth, batch normalization, and skip connections on L and \\mu in Theorem 3.1 well understood? It is possible that these architectural choices change the speed of learning by modifying these constants rather than just reducing gradient confusion.\n\nIn section G in the Appendix it is said: \"In general, it is not tractable to prove the concentration results in section 4 using the covariance matrix of the gradients alone without further unrealistic assumptions....\" Why is bounding the gradient variance under the assumptions like bounded weights and standard initialization hard (or impossible) and a different measure like gradient confusion is necessary?\n\n[Minor remarks]\n- In Section 5: \"selected the run that achieved the lowest training loss value\"->\"selected the learning rate that achieved...\"\n-------------\nAfter rebuttal: I have read the author's response, the other reviews, and the modification. The response addresses my questions. The new revision shows the proposed measure's practical significance and robustness to one sample. I raised my score. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJlu65EJcH", "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 introduces the concept of \"gradient confusion\" to explain why neural networks train fast with SGD. They also study the effects of width, depth on gradient confusion. \n- The theoretical results assume that the data is sampled from a sphere and do not really give much insight into the effect of width and depth. \n- There are some confounding factors in the experiments and there needs to be a better comparison to some related work. \nDetailed review below:\nSection 1:\n- Please clarify how \"gradient confusion\" relate to the interpolation conditon of Ma et al, 2017 and the strong growth condition of Vaswani et al? \n- If we run SGD with a constant step-size, it will bounce around the optimal point in a ball with radius that depends on the step-size. If I keep decreasing the step-size, this radius shrinks. How does gradient confusion relate to the step-size? Is it upper-bounded by a quantity that depends on the step-size and the batch-size?\nSection 2:\n- Definition 2.1: Why should this condition hold for \"all\" points w? Isn't it necessary only at w^* or in a small neighborhood around it? \n- The gradient confusion parameter \\eta should depend on the batch-size. Please clarify this. \n- Figure 1: Previous work (Ma et al, Vaswani et al, Gunasekhar, 2017) all have shown that fast convergence can be obtained using SGD with a constant step-size with over-parametrized models and explained it using interpolation. What is the additional insight from gradient confusion?\n- \"Suppose that there is a Lipschitz constant for the Hessian\" - This is a strong assumption and a vague argument, that is confusing rather than insightful. Please justify why this is a valid assumption for neural network models.\nSection 3:\n- If E_i || \\nabla f_i(w)  ||^2 = O(\\epsilon) => gradient confusion = O(\\epsilon). Isn't the E_i || \\nabla f_i(w)  ||^2 exactly the strong growth condition in Vaswani, et al. Can the gradient confusion results be directly derived from the results in that paper? Please compare. Also compare and cite \"Stochastic Approximation of Smooth and Strongly Convex Functions:\nBeyond the O(1/T ) Convergence Rate\", COLT 2019. \nSection 4:\n- Please compare against the previous results that assumed the data to be sampled from a sphere. \n- Thm 4.1: The theorem bounds the probability that gradient confusion holds for a given \\eta. But the bounds of section 3 are vacuous even if the theorem holds with probability one, but for a large value of \\eta. There needs to be an upper bound on \\eta. Please clarify this. \n- Please compare against the results of this paper by Arora et al: \"On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization\"\n- For the effect of layer width, the analysis is only for the initializated weights and does not consider the optimization, which is what the paper claimed in the introduction. Am I missing something? Please justify this. The gradient confusion can decrease as the optimization progresses? \nSection 5:\n- \"We reduce the learning rate by a factor of 10\" But all the theory is for a constant step-size. Please explain this discrepancy. \n- in Figure 2, in the second figure, why is there a sharp full in the pairwise cosine similarities. \n- In all these experiments, explain why the batch-size and the step-size is not a confounding factor?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJg5gjvqYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 targets to understand some key factors that might influence the training speed of neural networks. It defines a concept called \"gradient confusion\" to quantify these factors. Roughly speaking, this term captures the disagreement of the descending directions suggested by different samples. \n\nOn the positive side, to understand the training procedure is important to the deep learning community. The idea on \"gradient confusion\" is quite straightforward and easy to understand. The paper is clearly written. \n\nHowever, there are some essential drawbacks of the paper that make me lean towards rejecting it. \n\nFirst, this concept of \"gradient confusion\" is very similar to the \"gradient diversity\" introduced more than 2 years ago in [1]. The term proposed in [1] measures the \"gradient confusion\" relative to the average of gradient norms, and is an averaged case rather than the worst case version. (This actually brings a second issue of the \"gradient confusion\" which makes the definition less useful.) However the paper has not discussed this existing work and the contribution on top of it. \n\nSecond, the \"gradient confusion\" is not a robust term even to one outlier sample. Since the definition in Eqn. (3) measures the worst case scenario, one could add an outlier sample that easily makes the eta arbitrarily large and the latter bound on the convergence will be meaningless. In comparison, the \"gradient diversity\" in [1] of the averaged value makes more sense to me. \n\nThird, the proposal of a new theory should be in favor of at least some applicable cases. In this paper, the take-home message seems to be when the samples are pushing the gradient towards the same direction, the training becomes faster, which is very legit and people believe this. However, what can we do about this? The authors fail to propose some interesting applications that could make use of the \"gradient confusion\" to help the training. For instance, the work of [1] has made use of the gradient diversity to accelerate distributed learning which could be one application. I encourage the authors to work towards some useful applications concerning this new concept.  \n\nTo sum up, I don't think this paper brings out some real contributions to the community and should not be accepted. \n\n\n[1]  Yin, Dong, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. \"Gradient diversity: a key ingredient for scalable distributed learning.\" arXiv preprint arXiv:1706.05699 (2017).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the concept of gradient confusion to show how the neural network architecture affects the speed of training. The reviewers' opinion on this paper varies widely, also after the discussion phase.  The main disagreement is on the significance of this work, and whether the concept of gradient confusion adds something meaningful to the existing literature with respect to understanding deep networks. The strong disagreement on this paper suggest that the paper is not quite ready yet for ICLR, but that the authors should make another iteration on the paper to strengthen the case for its significance.

Decision: Reject