A Functional Characterization of Randomly Initialized Gradient Descent in Deep ReLU Networks
Authors: Justin Sahs
Aneel Damaraju
Ryan Pyle
Onur Tavaslioglu
Josue Ortega Caro
Hao Yang Lu
Ankit Patel
Venue:  (2020)
Keywords: Inductive Bias
Generalization
Interpretability
Functional Characterization
Loss Surface
Initialization

Abstract: Despite their popularity and successes, deep neural networks are poorly understood theoretically and treated as 'black box' systems. Using a functional view of these networks gives us a useful new lens with which to understand them. This allows us us to theoretically or experimentally probe properties of these networks, including the effect of standard initializations, the value of depth, the underlying loss surface, and the origins of generalization. One key result is that generalization results from smoothness of the functional approximation, combined with a flat initial approximation. This smoothness increases with number of units, explaining why massively overparamaterized networks continue to generalize well.

Under review as a conference paper at ICLR 2020
A FUNCTIONAL CHARACTERIZATION OF RANDOMLY INITIALIZED GRADIENT DESCENT IN DEEP RELU NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Despite their popularity and successes, deep neural networks are poorly under- stood theoretically and treated as 'black box' systems. Using a functional view of these networks gives useful new lens with which to understand them. Theoret- ical (in shallow) and experimentally probing properties these networks reveals insights into the effect of standard initializations, the value of depth, the underly- ing loss surface, and the origins of generalization. One key result that general- ization results from smoothness of the functional approximation, combined with a flat initial approximation. This smoothness increases with number of units, ex- plaining why massively overparamaterized networks continue generalize well.
INTRODUCTION
Deep neural networks, trained via gradient descent, have revolutionized the field of machine learn- ing. Despite their widespread adoption, theoretical understanding fundamental properties of deep learning the true value of depth, the root cause of implicit regularization, and the seemingly 'un- reasonable" generalization achieved by overparameterized networks remains mysterious.
Empirically, it is known that depth is critical to the success of deep learning. Theoretically, it has been proven that maximum expressivity grows exponentially with depth, with a smaller number of trainable parameters (Raghu et al.) 2017; Poole et al.) 2016). This theoretical capacity may not be used, as recently shown explicitly by (Hanin Rolnick (019). Instead, the number of regions within trained network is proportional the total number of hidden units, regardless of depth. Clearly deep networks perform better, but what is the value depth not in increasing expressivity?
Another major factor leading to the success and widespread adoption of deep learning has been its surprisingly high generalization performance (Zhang et al., 2016). In contrast to other machine learning techniques, continuing to add parameters to deep network (beyond zero training loss) tends to improve generalization performance. This is even for networks that are massively overpa- rameterized, wherein according traditional MI. theory they should (over)fit all the training data (Neyshabur et al. 2015). How does training deep networks with excess capacity lead to generaliza- tion? And how can be that this generalization error decreases with overparameetrrization?
We believe that taking a functional view allows us a new, useful lens with which to explore and understand these issues. In particular, focus on shallow and deep fully connected univariate ReLU networks, whose parameters will always result in Continuous Piecewise Linear (CPWL) approximation the target function. We provide theoretical results for shallow networks, with experiments showing that these qualitative results hold in deeper nets.
Our approach is related to previous work from (Savarese al., 2019 Arora et al. 2019 Frankle & Carbin, 2018) in that we wish to characterize parameterization and generalization. We differ from these other works by using small widths, rather than massively overparamaterized or infinite, and by using functional parameterization to measure properties such smoothness. Other prior works such as (Serra et al. 2017 Arora et al. 2016; Montufar et al., 2014)) attempt to provide theoretical upper lower bounds to the number of induced pieces in ReLU networks, whereas
more interested in the empirical number of pieces in example tasks. Interestingly, (Serra et al.) 2017) also Previous work
takes functional view, but is not interested in training and generalization

---

Under review as a conference paper at ICLR 2020
(Advani & Saxe 2017) has hinted the importance of small norm initialization, but the functional perspective allows us to prove generalization properties in shallow networks.
Main Contributions The main contribution of this work are as follows:
Functional Perspective of Initialization: Increasingly Flat with Depth. In the functional perspec- tive, neural network parameters determine the locations of breakpoints and their delta-slopes (de- fined in Section 2.1 in the CPWL reparameterization. We prove that, for common initializations, these distributions are mean O with low standard deviation. The delta-slope distribution becomes increasingly concentrated as the depth of the network increases, leading to flatter approximations. In contrast, the breakpoint distribution grows wider, allowing deeper network to better approxi- mate over broader range of inputs.
Value of Depth: Optimization, not Expressivity. Theoretically, depth adds exponential amount of expressivity. Empirically, this is not true in trained deep networks. We find that expressivity scales with the number of total units, and weakly if at all with depth. However, we find that depth makes it easier for GD to optimize the resulting network, allowing for a greater flexibility in the movement of breakpoints, as well as the number of breakpoints induced during training.
Generalization is due to Flat Initialization in the Overparameterized Regime. We find that gener- alization in overparametrized FC ReLu nets is due to three factors: (i) the very flat initialization, (ii) the curvature-based parametrization of the approximating function (breakpoints and delta- slopes) and (iii the role of gradient descent (GD) in preserving (i) and regularizing via (ii). In particular, the global, rather than local, impact of breakpoints and delta-slopes helps regularize the approximating function in the large gaps between training data, resulting in their smoothness. Due to these nonlocal effects, more overparameterivation leads to smoother approximations (all else equal), and thus typically better generalization (Neyshabur et al. 2018 2015).
2 THEORETICAL RESULTS
2.1 RELU NETS IN FUNCTION SPACE: FROM WEIGHTS TO BREAKPOINTS & SLOPES
Consider a fully connected ReLU neural net fo(x) with a single hidden layer of width H, scalar input x E IR and scalar output R. f-; 0) is continuous piecewise linear function (CPWL) since the ReLU nonlinearity is CPWL. We want understand the function implemented by this neural net, and so we ask: How do the CPWL parameters relate to the NN parameters? We answer this by transforming from the NN parametrization (weights and biases) to two CPWL. parametrizations:
H
f(z;(NN) 2
U. wwww + b,)+
(1)
i=1
Σ
H
pi(x - (3,) ( [ B.],
8, =; 1
f(z OBDSO)
(2)
11x < <.1,,
8, === -1
1=1
13p x Aptz] (myx Tp)
& f(x;0rw1)
where the Iversen bracket [b] is when the condition true, and 0 otherwise. Here the NN parameters ANN & {(w,, b,, , denote the input weight, bias, and output weight of neuron i, and (-)+ e max(0,.) } denotes the ReLU function. The first CPWL parametrization is θBDSO A ((3,, (s, 8:) 8:) where 3; neuron i, 14 2 w.o, is the delta-slope contribution of neuron i, and s; & sgn W. E {+1} is the orientation of B3 (left for 8; = 1, right for 8; +1). Intuitively, in good fit the breakpoints 3r will congregate in areas of high curvature in the ground truth function f='x)] 2 0, while delta- slopes μt will actually implement the needed curvature by changing the slope by μ. from one piece p(i) to the next p(i) + 1. As the number of pieces grows, the approximation will improve, and the delta-slopes (scaled by the piece lengths) approach the true curvature of f: limp-sso Mpt0) (8, (p-1) + (x Bi).
b. is (the x-coordinate of) the breakpoint (or knot) induced by
wi
2

---

Under review as a conference paper at ICLR 2020
We note that the BDSO parametrization of a ReLU NN is closely related but different than tra- ditional
m-th order spline parametrization (x) Σ (4 - 3, + Zi=0 cysr: BDSO (i) lacks the base polynomial, and (ii) has two possible breakpoint orientations 8t E [+1] whereas the spline only has one. We note in passing that adding in the base polynomial (for linear case m = 1) into the BDSO ReLU parametrization yields ReLU ResNet parametriza- tion. We believe this a novel viewpoint that may shed more light on the origin of the effectiveness of ResNets, but we leave it for future work.
The second parametrization the canonical one for PWL functions: Opwr. - ((pp Mpp 7p)) where 30 < B1 < ... < Bp A
< ... 3p is the sorted list of (the x-coordinates of) the P A H + 1 breakpoints (or knots), mpp Tp are the slope and y-intercept of piece p.
bpc))
Mp(()
Computing the analogous reparametrization function space for deep networks is more involved, so we present a basic overview here, and a more detailed treatment in Appendix B For L 2 2 layers
with widths (1), the neural network's 's activations are defined as: 2(5) = ΣØ= wij 2j
H (-1)
(8) (e-1)
+
6 1/ = (z. ++ (xx) = z(L+1) for all hidden layers E (1.2....,L) and for all neurons
i (1,2,... ..., H.O). Then B( is breakpoint induced by neuron in layer if it zero-crossing of the net input i.e. 2/ 2/"((1 (((5)) ) 0.
Considering these parameterizations (especially the BDSO parameterization) provides new, useful lens with which to analyze neural nets, enabling us to reason more easily and transparently about the initialization, loss surface, and training dynamics. The benefits of this approach derive from two main properties: (1) that we have 'modded out' the degeneracies in the NN parameterization and (2) the loss depends on the NN parameters N only through the BDSO parameters (the approximating function) BDDO i.e. v(ONN) BiOBDSo (f n )), analogous to the concept of a minimum sufficient statistic exponential family models. Much recent related work has also veered in this direction, analyzing function space (Hanin & Rolnick 2019 Balestriero et al. 2018
2.2 RANDOM INITIALIZATION IN FUNCTION SPACE
We now study the random initializations commonly used in deep learning in function space. These include the independent Gaussian initialization, with b; ~ (O, 0b), w; ~ (O, e (O, ow), and independent Uniform initialization, with by ~ Ul-as, anl. wi ~ U[-awe Ow.), w Ul,;,, uu., a.]. We find that common initializations result in flat functions, becoming flatter with increasing depth.
Theorem 1. Consider a fully connected ReLU neural net with sealar input and output, and a sin- gle hidden layer of width H. Let the weights and biases be initialized randomly according to zero-mean Gaussian or Uniform distribution. Then the induced distributions of the function space parameters (breakpoints B, delta-slopes μs) are as follows:
(a) Under an independent Gaussian initialization,
1 of +
Pa. P8. (3r.p4)
exp
2TToVol 02
(b) Under an independent Uniform initialization,
(32. [|a S min
9&a6 D. Owes Ur
minf
ab aw
av Using this result, we can immediately derive marginal and conditional distributions for the break- points and delta-slopes.
4a
|B,
Corollary 1. Consider the same setting as Theorem
(a) In the case of an independent Gaussian initialization,
(a( = Cauchy (;:0, x
Ob
202,3
0w
3

---

Under review as a conference paper at ICLR 2020
Pu(())= =
G
0.0)
Ko
20T
Voz
| I of + Bi
Pula(ee (i)) Laplace
pi 0,
exp
Vol
22
20
ObDnOw
where Gmm the Meijer G-function and Ko(,) ) the modified Bessel function of the second kind.
(b) In the case of an independent Uniform initialization,
min { ab 1.3:1
2
Pp(3.) 4ayaw
Pa(m)) [-a I M4 SS Oog
log
[agl
Pula (1a(( Bx) = Tri(uu au min min(as, (as/ (nr))) [leed S a, min (ann/a//////// awlll
(1- au min (ab/ (06/13/l.0 aw
(oin [3 aw)
where ar) is the symmetric triangular distribution with base [-a, and mode O.
Implications. Corollary I iimplies that the breakpoint density drops quickly away from the origin for common initializations. If has significant curvature far from the origin, then it may be far more difficult to fit. We show that this is indeed the case by training shallow ReLU NN with an initialization that does not match the underlying curvature, with training becoming casier if the initial breakpoint distribution better matches the function curvature. We also show that during training, breakpoint distributions move to better match the underlying function curvature, and that this effect increases with depth (see Section 3 Table [ and Appendix (A.6). This implies that data-dependent initialization, with a breakpoint distribution near areas high curvature, could potentially be faster and easier train.
Next, we consider the typical Gaussian He (e et al. 2015) or Glorot Gloort & Bengio) initializa- tions. In the He initialization, we have ow = 22, o 22/H. . In the Glorot initalization, we have w Tee 22/(H 1). We wish consider their effeect the smoothness of the initial function approximation. From here on, we measure the smoothness using a roughness metric, defined as 2 Σ; 123 where lower roughness indicates a smoother approximation.
Theorem 2. Consider the initial roughness Po under Gaussian initialization. In the He initializa- tion, we have that the tail probability is given by
Po - Elpol 2 A
1 NH
where Elpol 4. the Glorot initialization, we have that the tail probability given by
P E(pul 2 Al
A
where Elpo]
4H (#+1))
O (+).
128H
Thus, the width H increases, the distribution of the roughness of the initial function fo gets tighter around its mean. In the case of the He initialization, this mean is constant; in the Glo- rot initialization, it decreases with H. In either case, for reasonable widths, the initial rough- ness is small with high probability. This smoothness has implications for the implicit regulariza- tion/generalization phenomenon observed in recent work (Neyshabur et al. 2018) (see Section for generalizztioomsmootteesss analysis during training).
Related Work. Several recent works analyze the random initialization in deep networks. However, there are two main differences, First, they focus on the infinite width case (Savarese et al.) 2019) Jacot et al. 2018 Lee et al., (017)) and can thus use the Central Limit Theorem (CLT), whereas we Tocus on finite width case and cannot use the CLT, thus requiring nontrivial mathematical machinery (see Supplement for detailed proofs). Second, they focus on the activations as a function input whereas we also compute the joint densities of the BDSO parameters i.c. breakpoints and delta- slopes. The latter is particularly important for understanding the non aon-unfform density of breakpoints away from the origin noted above.
4

---

Under review as a conference paper at ICLR 2020
2.3 LOss SURFACE IN THE FUNCTION SPACE
We now consider the mean squared error (MSE) loss as a function of either the NN parameters ((ONN) A En 2m=12(0 (f(x:))) - ya)² or the BDSO parameters {(OBDSO)- Now consider some OBDSO- Then f(;0BDso) induces a partition = (mI,..., *H++) of the data [ such that the restriction of fEDSO to any piece of this partition, denoted f(: (BDso)l a linear function.
Theorem 3. Suppose that for all E [P], ((DDS)))) is an Ordinary Least Squares fit of the data in piece p. Then, OBDSO is critical point of ((OBDSO).
An open question is how many such critical points exist. A starting point is to consider that there are C(N+H, H) _ (N + HH!!N!!H! possible partitions of the data. Not every such partition will admit a piecewise-OLS solution which also continuous, and it is difficult to analytically characterize such solutions, so we resort to simulation and find lower bound that suggests the number of critical points grows at least polynomially in N and (Figure 7
Using Theorem 3 we can characterize growth of global minima in the overparameterized case. Call partition IT lonely each piece Tp contains at most one datapoint. Then, we can prove the following results:
Theorem 4. For any lonely partition IT, there are infinitely many parameter settings OBDSO that induce II and are global minima with E(0 = O.
Proof. Note that each linear piece p has two degrees of freedom (slope and intercept). By way of induction, start at (say) the left-most piece. If there is datapoint in this piece, choose an arbitrary slope and intercept that goes through it; otherwise, choose an arbitrary slope and intercept. At each subsequent piece, we can use one degree of freedom to ensure continuity with the previous piece, and use one degree of freedom to match the data (if there is any).
Remark 1. Suppose that the H breakpoints are uniformly spaced and that the N data points are uniformly distributed within the region of breakpoints. Then in the overparametrized regime H 2 aN2 for some constant a >> 1, the induced partition II is lonely with high probabilility 1 (N = = e- 11/a, Furthermore, the total number of lonely partitions, and thus lower bound on the total number of global minima of é is (H+ = O(NaN)
Thus, with only order 22 units, we can almost guarantee lonely partitions, where the piecewise OLSS solution on these lonely paratitions will be the global optimum. Note how simple and transparent the function space explanation is for why overparametrizztion makes optimization easy, as compared to the weight space explanation Arora et al. 2019, requiring order NV units.
2.4 GENERALIZATION: IMPLICIT REGULARIZATION VIA DELTA-SLOPE PARAMETRIZATION
The above sections argue that overparameterization leads to a flatter initial function approximation, and an easier time reaching a global minima over the training data. However, neural networks also exhibit unreasonably high generalization performance, which must be due to implicit regularization, since the effect is independent of loss function. Here we provide an argument that overparameteri- zation directly leads this implicit regularization, due to the increasing flatness of the initialization and the non-locality of the delta-slope parameters.
Consider dataset like that shown in Figure 3 with data gap between regions of two tinuous functions fz, fR and consider a breakpoint i with orientation s; in the gap. Starting with a flat initialization, the dynamics of the i-th delta-slope are ji,(t)
(é(t) (t))), + 3,(t) (é(t) @ at), 1) & r2.s, (t) + T3.s. (t) where (t), (t. are the (negative) net corre- lation and residual on the active side of i, in this case including data from the function fs, but not f-x.- Note that the both terms of the gradient i have weak dependence on through the orienta- tion 8; and the second term additionally depends on through (t). Thus the vector of delta-slopes with orientation s evolves according to μ = (t) r3. (t) Now consider the regime of overparametrization H > N. It will turn out to be identical to taking continuum limit H co yielding (4/(B; - -1-1) (xx, 1) & f"
(ar,AA 1), the curvature of the approximation (the discrete index
5

---

Under review as a conference paper at ICLR 2020
i has become continuous index 2) and (t) + 0 (following from Theorem 5 multiplying (t)
by (((tt//w(tt (t) and factoring out (t(() - 0). Integrating the dynamics ( t) = T2 (t) + -3. (t)x
over all time yields ps (z, t 00) = (a 0) R + R. where the curvature μag (2,
0) = 0 (Section 3 and R, & I dt' tt'r,, (t) < oo (convergence of residuals (t) and immobility
of breakpoints (t)
implies convergence of ry (t)). Integrating over space twice(from x' &, to x = 2) yields a cubic spline f(z,,) = co.. + c1.. (2 - Es) + 02., /2) C3 - /31 where C1, are integration constants determined by the per-piece boundary conditions (PBCs) f(x - E,, x0) A E.S.x = E.) = f(" = (.) and (( - E., l = xo) E. = E.) f' = E.), thus matching the 0-th and 1st derivatives at the gap endpoints. The other two coeffi- cients CR.. e a k E (2, 3) and serve to match the 2nd and 3rd derivatives at the gap endpoints. Clearly, matching the training data only requires the two parameters Co,s, C1,s; and yet, surprisingly, two unexpected parameters 02.e, c3,s emerge that endow f with smoothness in the data gap, despite the loss function not possessing any explicit regularization term. Tracing back to find the origin of these amoothness-indueing terms, we see that they emerge as a consequence of (i) the smoothness of the initial function and (ii) the active half space structure, which in turn arises due to the discrete curvature- based (delta-slope) parameterization. Stepping back, the ReLU net parameterization is a discretization of this underlying continuous 2nd-order ordinary differential equation. In Section 3 we conduct experiments to test this theory.
EXPERIMENTS
Breaking Bad: Breakpoint densities that are mismatched to function curvature makes opti- mization difficult We first test our initialization theory against real networks. We initialize fully- connected ReLU networks of varying depths, according to the popular He initializations (He et al. 2015). Figure shows experimentally measured densities of breakpoints and delta-slopes. Our theory matches the experiments well. The main points to note are that: (i) breakpoints are indeed more highly concentrated around the origin, and that (ii) as depth increases, delta-slopes have lower variance and thus lead to even flatter initial functions. We next ask whether the standard initial- izations will experience difficulty fitting functions that have significant curvature away from the origin (e.g. learning the energy function of a protein molecule). We train ReLU networks to fit a periodic function (sin(z)), which has high curvature both at and far from the origin. We find that the standard initializations do quite poorly away from the origin, consistent with our theory that breakpoints are essential for modeling curvature. Probing further, we observe empirically that breakpoints cannot migrate very far from their initial location, even if there are plenty of break- points overall, leading to highly suboptimal fits. We additionally show (see Appendix A.6 for de- tails) that breakpoint distributions change throughout training to more accurately match the ground truth curvature. In order to prove that it is indeed the breakpoint density that is causally responsible, attempt to rescue the poor fitting by using simple data-dependent initialization that samples breakpoints uniformly over the training data range [Emin, ]man], achieved by exploiting Eq. (2)
We train shallow ReLU networks on training data sampled from a sine and a quadratic function, two extremes on the spectrum of curvature. The data shows that uniform breakpoint density res- cues bad fits in cases with significant curvature far from the origin, with less effect on other cases, confirming the theory. We note that this could be potentially useful data-dependent initialization strategy, one that can scale to high dimensions, but we leave this for future work.
Init Standard
Sine
Quadratic
4.096 2.25
.1022 + 0404
Uniform 2.280 + .457
.1188 + .0248
Table 1: Test loss for standard vs uniform break- point initialization, on sine and quadratic 5
Explaining and Quantifying the Suboptimality of Gradient Descent. The suboptimality seen above begs a larger question: under what conditions will GD be successful? Empirically, it has been observed that neural nets must be massively overparameterized (relative to the number of parameters needed to express the underlying function), in order to ensure good training performance. Our theory provides a possible explanation for this phenomenon: if GD cannot move breakpoints too far from their starting point, then one natural strategy is to sample as many breakpoints possible everywhere allowing us to fit an arbitrary f. The downside of this strategy is that many breakpoints will add little value. In order to test this explanation and, more generally, understand the root causes

---

Under review as a conference paper at ICLR 2020
01
Figure 1: Left: Training loss vs number of pieces (x number of parameters) for various algorithms fittigg CPWL function to a quadratic. Middle: Breakpoint distribution for He initialization across a 3 layer network. Right: Delta-slope distribution for a He initialization across a layer network.
L
Sine
5 piece poly
Sawtooth
Arctan
Exponential
Quadratic
40
40 = 52 + 1.414
40 0
40 = 0
40 =
40 + 0
2
55.5 = 2.9
50 + .7
49.25 + 3.3
51.25 + 6.1
49.25 + 4.5
68 + 3.1
57.25 6.8
48.5 2.5
42.5 + 4.8
40.25 + 3.9
40.25 + 3.3
5
62.25 15.1
49 = 3.5
44.5 5.1
38 + 5.1
33.75 + 1.1
31.5 + 1.7
Table 2: Comparison of the number of pieces induced in a network of up to depth 5, with 40 units evenly distributed across layers, trained fit varying target functions.
of the GD's difficulty, we focus on the case of a fully connected shallow ReL.U network. A univariate input (i) enables us to use our theory, (ii) allows for visualization of the entire learning trajectory, and (ii) enables direct comparison with existing globally (near-)optima algorithms for fitting PWL functions. The latter include the Dynamic Programming algorithm (DP, (Bai & Perron 1998 ), and
a very fast greedy approximation known as Greedy Merge (GM, (Acharya et al. 2016)) How do these algorithms compare to GD, across different target function classes, terms of training loss,
and the number of pieces/hidden units? We use this metric for the neural network as well, rather than the total number of trainable parameters.
Taking the functional approximation view allows us to directly compare neural network performance to these PWL approximation algorithms. For a quadratic function (e.g. with high curvature, requir- ing many pieces), we find that the globally optimal DP algorithm can quickly reduce training error to near O with order 100 pieces. The GM algorithm, a relaxation of the DP algorithm, requires slightly higher pieces, but requires significantly less computational power. On the other hand all variants of GD (vanilla, Adam, SGD w/ BatchNorm) all require far more pieces to reduce error below a target threshold, and may not even monotonically decrease error with number of pieces. Interest- ingly, we observe a strict ordering of optimization quality with Adam outperforming BatchNorm SGD outperforming Vanilla GD. These results (Figure [ show how inefficient GD with respect to (functional) parameters, requiring orders of magnitude more for similar performance to exact or approximate PWL fitting algorithms.
Learned Expressivity is not Exponential in Depth. In the previous experiment, counted the number of linear pieces in the CPWL approximation as the number of parameters, rather than the number of weights. Empirically, we know that the greatest successes have come from deep learning. This raises the question: how does the depth of a network affect its expressivity (as measured in the number of pieces)? Theoretically, it is well known that maximum expressivity increases expo- nentially with depth, which, in a deep ReLU neural network, means an exponential increase in the number of linear pieces the CPWL approximation. Thus, theoretically the main power of depth is that it allows for more powerful function approximation relative to a fixed budget of parameters compared to a shallow network. However, recent work (Hanin & Rolnick] (019) has called this into question, finding that in realistic networks expressivity does not scale exponentially with depth. We perform a similar experiment here, asking how the number of pieces in the CPWL function approximation of deep ReLU network varies with depth.
The results in Table 2 clearly show that the number of pieces does not exponentially scale with depth. In fact, we find that depth only has a weak effect overall, although more study is needed to determine exactly what effect depth has on the number and variability of pieces. These results lend more support to the recent findings of (Hanin & Rolnick 2019), and of taking functional view
7

---

Under review as a conference paper at ICLR 2020
Function
Shallow
Spiky Shallow
Deep
Spiky Deep
Sine
42.95 6,406
6.406
157.5 = 60.27
31.48 + 7.078
122.0 + 128.2
Arctan
.01252 + .07650
2.499 + 1.257
0.9795 0.9355
32.57 + 26.10
Sawtooth
156.9 = 12.45
150.1 61.48
#
198.0 170.9
Cubic
3.608 = 1.683
136.7 = 124.1
56.77 9
191.6 + 114.1
Quadratic
3.559 + 4.553
150.6 + 49.00
1.741 1,296
46.02 + 19.42
Exp
.6509 + .5928
181.1 + 75.36
1.339 + 1.292
54.50 + 37.77
Table 3: Comparison of testing loss (generalization ability) of various network shallow and deep networks with standard vs 'spiky" initialization
of measuring parameterization. Intriguingly, variability in the number of pieces appears to increase with depth. From the functional approximation, know that unit induces breakpoints only when the ReLU function applied to the umit's input has zero crossings. In layer one, this happens exactly once per unit as the input each ReLU is just line over the input space. In deeper layers, the function approximation is learned, allowing for varying number of new breakpoints. Given our previous results on the flatness of the standard initializations, this will generally only happen once per unit, implying that the number of pieces will strongly correlate with the number of units at initialization.
Depth helps with Optimization by enabling the Creation, Annihilation and Mobility of Break- points. If depth does not strongly increase expressivity, then it is natural to ask whether its value lies with optimization. velops in each layer during learning, and how it depends on the target function. A good fit requires that breakpoints accumulate at areas of higher curvature in the training data, as these regions require more pieces. We argue that the deeper layers of network help with this optimization procedure, allowing the breakpoints more mobility as well as the power to create and annihilate breakpoints.
order test this, we examine how the CPWL function approximation de-
One key difference between the deeper layers of network and the first layer is the ability for single unit to induce multiple breakpoints. As these units' inputs change during learning, the number of breakpoints induced by deeper units in network vary, allowing for another degree of freedom for the network to optimize. Through the functional parameterization of the hidden layers, these "births and deaths" of breakpoints per layer. Another possible explanation for the value added of depth is breakpoint mobility, or that breakpoints in deeper layers can move more than those in shallow layers. We experiments comparing how the velocity and number of induced breakpoints varies between layers of a deeper network.
be tracked changes in the number of breakpoints induced
Babts Deaths
layer Figure 2: Total changes number of breakpoints induced and average Velocity of breakpoints relative to the first layer in each layer of a five layer ReLU network
Layer
Figure 2 shows the results. The number of breakpoints in deeper layers changes more often than in shallow layers. The breakpoint velocity in deeper layers is also higher than the first layer, although monotonically increasing. Both of these results provide support for the idea that later layers help significantly with optimization and breakpoint placement, even if they do not help as strongly with expressivity.
Note that breakpoints induced by layer of the network are present in the basis functions of all deeper layers. Their functional approximations thus become more complex with depth. However the roughness of the basis functions at initialization in the deeper layers is lower than that of the shallow layers. But, as the network learns, for complex functions most the roughness is in the later layers as seen in Figure (right).
Generalization: Implicit Regularization emerges from Flat Init and Curvature-based
Parametrization. The experiments above show that the functional view give a per-
8

---

Under review as a conference paper at ICLR 2020
Total Roughness (por lyerr
Tot2 Rough 1e55 jper Koyer
2
Spech
Figure 3: Roughness (summed by layer) during training for 5 layer ReLU network with 8 units per hidden layer, learning the quadratic function x²/ (left) and the periodic function sin(x) (right)
spective on how depth and parameterization affect the training of neural networks. One of the most useful and perplexing properties of deep neural networks has been that, in contrast other high capacity function approximators, overparameterizing a neural network does not tend to lead to ex- cessive overfitting (Savarese et al. 2019). Where does this generalization power come from? Much recent work (Neyshabur et al., 2018 (2015) has argued that it comes from an implicit regularization inherent in the optimization algorithm itself (i.e. SGD). In contrast, for the case of shallow and deep univariate fully connected ReLU nets, we provide causal evidence that it is due to the specific, very flat CPWL, initialization induced by common initialization methods. order to test this in both shallow and deep ReLU networks, we compare training with the standard flat initialization to "spiky" initialization.
For shallow ReLU network, we can test a 'spiky' initialization by exactly solving for network parameters to generate a given arbitrary CPWL. function. This network initialization is then com- pared against a standard initialization, and trained against smooth function with small number of training data points. Note that in a ID input space we need a small number of training data points to create situation similar that of the sparsity caused by high dimensional input, and to allow for testing generalization between data points. We find that both networks fit the training data near perfectly, reaching a global minima of the training loss, but that the 'spiky" initialization has much worse generalization error 3). Visually, we find that the initial 'spiky' features of the starting point CPWL representation are preserved in the final approximation of the smooth target function (Figures 4 and 6). For a deep ReLU network, it is more difficult to exactly solve for 'spiky' initialization. Instead, we train a network to approximate an arbitrary CPWL function, and call those trained network parameters the 'spiky" initialization. Once again, the 'spiky" initialization has near identical training performance, hitting all data points, but has noticeably worse generalization performance.
Ivbtal CPN, Approsmizaknn
P nal CPWL Appicdraaon
Sprg
22
15
18
44
35
95
-16
-10
-1
-20
-24 -15
10 35
-15 -10 20 08 13
Figure 4: 'Spiky' (orange) and standard initialization (blue), compared before (left) and after (right) training. Note both cases had similar, very low training set error.
appears that generalization performance it not automatically guaranteed by GD, but instead due to the flat initializations which then preserved by GD. 'Spiky' initializations also have their (higher) curvature preserved by GD. This idea makes sense, as generalization depends on our target function smoothly varying, and smooth approximation is promoted by a smooth initialization.

---

Under review as a conference paper at ICLR 2020
Smoothness in Data Gaps increases with Hidden Units and Decreases with Initial Weight Vari- ance. Our last experiment examines how smoothness (roughness) depends on the number of units, particularly in the case where there are large gaps in the training data. We use continuous and discontinuous target function (shown in Figure 8). We trained shallow ReLU networks with varying width H and initial weight variance ow on these training data until convergence, and measured the total roughness of resulting CPWL approximation in the data gaps.
Smoud
Smoots
Sharp
Shorp
Roughtess
50
Widden Units
Variance Intoas Weeghts
Figure 5: Roughness vs. Width (left) and the variance of the initialization (right) for both data gap cases shown in Figure g Each data point is the result of averaging over 4 trials trained to
convergence.
F shows that roughness in the data gaps decreases with width and increases with initial weight variance, confirming our theory. A spiky (and thus rougher) initialization leads to increased rough- ness at convergence as well, lending support to the idea that roughness in data gaps can be 'remem- bered' from initialization. On the other hand, higher number of pieces spreads out the curvature work over more units, leading to smaller overall roughness. Taken together, our experiments indicate that smooth, flat initialization is partly (if not wholly) responsible for the phenomenon of implicit reg- ularization in univariate fully connected ReI.U nets, and that increasing overparameterization leads even better generalization.
Conclusions. We show in this paper that examining deep networks through the lens of function space can enabled new theoretical and practical insights. We have several interesting findings: the value of depth in deep nets seems to be less about expressivity and more about Icarnability, enabling GD to finding better quality solutions. The functional view also highlights the importance initial- ization: smooth initial approximation seems encourage a smoother final solution, improving generalization. Fortunately, existing initializations used in practice start with smooth initial approx- imations, with smoothness increasing with depth. Analyzing the loss surface for a ReLU net in function space gives surprisingly simple and transparent view of the phenomenon of overpa- rameterization: makes clear that increasing width relative to training data size leads w.h.p. to lonely partitions of the data which are global minima. Function space shows us that the mysterious phenomenon of implicit regularization may arise due to a hidden 2nd order differential equation that underlies the ReL.U parameterization. In addition, this functional lens suggests new tools, architec- tures and algorithms. Can we develop tools to help understand how these CPWL functions change across layers or during training? Finally, our analysis shows that bad local minima are often due to breakpoints getting trapped in bad local minima: Can we design new learning al algorithms that make global moves in the BDSO parameterization in order to avoid these local minima?
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jayadev Acharya, Iaaas Diakonikolas, Jerry Li, and Ludwig Schmidt. Fast algorithms for segmented regression. arXiv preprint vrXiv:1607.03990 2016.
Madhu S Advani and Andrew Saxe. High-dimensional dynamics of generalization error neural networks. arXiv preprint arXf::1710.03667, 2017.. 2017.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint a6 1.01491, 2016.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- tine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019.
Jushan Bai and Pierre Perron. Estimating and testing linear models with multiple structural changes. Econometrica, pp. 47-78, 1998.
Randall Balestriero et al. A spline theory of deep networks. In International Conference on Machine Learning, pp. 383-392, 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:1803.03633. 2018.
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 statistics, pp. 249-256.
I.S. Gradshteyn and I.M. Ryzhik. Tables of Integrals, Series, and Products. edition, 2015. ISBN 978-0-12-373637-4
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. arXiv preprint arXiv:1906.00904 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems, pp. 8571 1- 8580, 2018
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv: 17..0066, 2017.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp- 2924-2932, 2014.
Behnam Neyshabur, Ruslan R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized opti- mization in deep neural networks. Advances Neural Information Processing Systems, pp- 2422-2430, 2015.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. 2018.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl- Dick-iicktt,,n, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural informa- fion processing systems, pp. 3360-3366 2016.
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 Machine Learning- Volume 70, pp. 2847-2854. JMLR. org, 2017.

---

Under review as a conference paper at ICLR 2020
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look function space? arXiv preprint 1rXiv:190..05040, 2019.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam, Bounding and counting linear regions of deep neural networks. arXiv preprint arXiv:1711.02114 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1r 2016.
12

---

Under review as a conference paper at ICLR 2020
A EXPERIMENTAL DETAILS
Th Wiw.opooooo rudie
CITI Approsmstiio
MMV
M
4.4
Figure 6: 'Spiky' (orange) and standard initialization (blue), compared before training (left) and post-training (right) using deep network
N/namum No Local Minanam
Kinasmm mber Local Meannam
55000
50000
WTT1
N narber of ports
16 narber of ports
Figure 7: Growth in the (minimum) amount of local minima, function of the number of break- points and data points. Right plot is identical, but with log scaling
A.1 UNIFORM INITIALIZATION
Trained on shallow, 21 unit FC ReLU network. Trained function over the interval [-2,2]. Learning rate = 5e-5, trained via GD over 10000 epochs. Compared against pytorch default of He initialization. Training data sampled uniformly every ,01 of the target interval. Each experiment was run times, with results reported as mean + standard deviation. Breakpoints values were taken from the original standard initialization for the uniform initialization plus small random noise term N(O,001), making initial condition within the target interval nearly identical.
A.2 ROUGHNESS BY LAYER PLOTS
Trained on deep. 5 layer network, with 4 hidden layers of width 8. Trained function over the interval [-2,2]. Learning rate le-4, trained via GD over 10000 epochs, with roughness measured every 50 epochs. Roughness per layer summed over all units within that layer.
A.3 SPIKY INITIALIZATION PLOTS
Shallow version trained on a 21 unit FC ReLU Network. Deep version trained on a deep, 5-layer network with 4 hidden layers of width 8. In both cases, the 'spiky' initialization was 20 breakpoint In the deep case, the spiky model was initialized with
CPWL function, with yn ~ Uniform(1-2) (1,,2) 2)). the same weights the non-spiky model, and then pre-trained for 10,000 epochs to fit the CPWL. After that, gradient descent training proceeded on both models for 20,000 epochs, with all training having learning rate le-4. Training data was 20 random points in the range [-2,2], while the testing
13

---

pre-training, as the 'spiky' model was directly set to be equal to the CPWL. the shallow model, training occurred for 20,000 epochs. All experiment were run over 5 trials, and values in table reported mean + standard deviation. Base shallow learning rate was le-4 using gradient descent method, with learning rate divided by for the spiky case due the initialization method generating larger weights. Despite differing learning rates, both models had similar training loss curves and similar final training loss values, e.g. for sine, final training loss was .94 for spiky and 1.02 for standard. Functions used were sin(x:) arctan(z), a sawtooth function from [-2,2] with minimum value of -1 at the endpoints, and 4 peaks of maximum value 1, cubic x² x² 4 Under review as a conference paper at ICLR 2020
data (used measure generalization) spaced uniformly at every Ar .01 of the target interval of the target function.
In the shallow case, there
2. quadratic x² and cxp(.5x) Note GD was chosen due to the strong theoretical focus of this paper similar results were obtained using ADAM optimizer, in which case no differing learning rates were necessary.
A.4 BREAKPOINTS INDUCED BY DEEP NETWORKS
We used networks with total of H = 40 hidden units, spread over L E 2,, 2, hidden layers. Training data consiste of uniform samples of function over the interval
[-3,3]. Learning rate - 10 10-5, trained via GD over 25, 000 epochs. The target functions tested were sin(sTr). 5-piece polynomial with maximum value of 2 the domain [-3, 3). a sawtooth with period and amplitude 1, (arctan(z)) (z). exp(x), and J Each value in the table was the average of 5 trials.
A.5 BREAKPOINT MOBILITY IN DEEP NETWORKS
We use a deep. 6-layer network, with 5 hidden layers of width 8. Training data consists of the 'smooth' and 'sharp' functions over the interval [-3, 3). Learning rate 5e-5, trained via GD until convergence, where convergence was defined as when the loss between two epochs changed by less than 10-8, Breakpoints were calculated every 50 epochs. The velocity of breakpoints was then calculated, and the values seen in the figure are normalized to the velocity of the first layer.
Figure 8: Training data sampled from two ground truth functions, one smoothly (left) and the other
sharply (right) discontinuous, each with a data gap [-0.5, 0.5).
A.6 BREAKPOINT DISTRIBUTIONS
Various function classes were trained until convergence on a depth or 4 ReLU network, with 500 total units distributed evenly across layers. Initial and final breakpoint distributions were measured using a kernel density estimate, and compared with the underlying curvature (absolute value of 2nd derivative) of the ground truth function. The cubic spline was a cubie spline fit to a small number of arbitrary data points.
Table shows that the breakpoint densities moved over training to become more correlated with the underlying curvature of the ground truth function. This effect was more pronounced with depth. In certain very simple functions (e.g. x? or exp(x), not shown), a failure case emerged where there no real change in correlation over training. Diagnostics appeared to show this was due to the function being so simple as to train almost instantaneously in our overparameterized network, meaning breakpoints had no time move. Figure&ssows what happens to the breakpoint densities
14

---

8.00 Thus, go(x) non-differentiable at æ if x ( for some (f, If no degenerate breakpoints exist, then the converse also holds. (If there do exist degenerate breakpoints ,3 and (e') Under review as a conference paper at ICLR 2020
Depth/Type
Sine
x3
Sin #²
Cubic Spline
Initial
-0.0770
-0.904
-0.754
-0.164
Final
0.324
-0.891
-0.592
0.289
4 Initial
-0.171
-0.900
-0.752
-0.133
Final
0.494
0.688
-0.212
0.798
1 A
0,401
0.0130
0.162
0,452
4
0.665
1.59
0.540
0.931
Table Top:
Correlation the BP distribution before and after training for depth and 4 networks across function classes, Bottom Change in correlation over training
over training in the shallow case, they are more constrained by the initial condition, and continue have higher density near the origin even when not necessary or appropriate.
B MORE DETAILS ON BREAKPOINTS FOR DEEP RELU NETS
Each neuron of the second hidden layer receives input the result of CPWL function 2(²)(z) as defined above. The output of this function then fed through a ReLU, which has two implications:
first, every zero crossing of zi²) is breakpoint of a!(²) second, any breakpoints 8381) of 2t²² such that (e8 O will not be breakpoints of x, Importantly, the number of breakpoints in go(x)) is now function of the parameters 0, rather than equal to fixed H as in the 7. = case; in other words, breakpoints can be dynamically created and annihilated throughout training. This fact will have dramatic implications when explore how gradient descent optimizes breakpoints in order to model curvature in the training data (see Section 3). But first, due to complexities of depth, we must carefully formalize the notion of breakpoint for deep network.
Definition 1. 3(() a breakpoint induced by neuron i layer zf (0(0)) = Since the function
2 (.) is nonlinear, neuron i may induce multiple breakpoints, which denote ((1) A breakpoint
((0)
Pik active if there exists some path through neuron such that for all other neurons + n, (E(i) 0, i.e. (x(x)) 1. If two neurons and j in layers and E induce the same breakpoint(s),
2j
((0) = 3102,, then both are referred to as degenerate breakpoints.
Let az (x)) Ilier āR Then, 3(0) active iff there exists some path i such that ब. is discontinuous
a(()) then it possible that n4 -M ( i.e. the changes in slope cancel out and go(x)) remains linear and differentiable.)
C PROOFS OF THEORETICAL RESULTS
C.I REPARAMETRIZATION FROM RELU NETWORK TO PIECEWISE LINEAR FUNCTION
Proof of Equations and 3
H
(x)
volwwo + bz)
www, + lwie + b, > 0]
Σ now; (x: - 3i)
#
[|0 > 3.]
w; >
where 3r A
bi
[ < 3.]
0
1=1
Σ px(xx - 3i) [ [ > 3.]
"
w; >
where 14s A 0200
[ [
0
15

---

Under review as a conference paper at ICLR 2020
Depth - 1, Dora loonge - 13:2
Depth - 4, Dota Rongo - 1%
04-
0.25
0.20
02-
0.30
0.58
0.55
Di. douiinn int Detmibuttion
111 Destricationn
0.03
curviture
0.-
Corveture
Dion Depth-
flang
0.5
SP drivation
Cotritutiin
curvature
04
04-
03-
011
0.-
Depth
Dato Tange 1%
Dopth - 4, Dota Rongo
- 11-2
Dioriation
drriutiin Cotritation
1.0
Curvature
06-
0.5
62-
0.-
0.-
Depth
Data hange
Dota Ronge
Detritation
Dicriuation Delribution
0.5
1st Doz
curvoarc
0.5
Carcoouc
62
0.
Figure 9: Shallow (left) and deep (right) plots of initial and final breakpoint distributions, along with the underlying true curvature of the functions (top to bottom) sin(x), 33, sin( (3"), ), and a cubic spline of a few arbitrary data points
This gives us Equation (2). as desired. Let the subscripts denote the parameters sorted by 3, value. this setting, let Bn 2 -00, and B11-1 & co. Then,
16

---

Pi du. Under review as a conference paper at ICLR 2020
H
P
H Σ
Hg Bg)
Hy Bg)
1 x < 5pl
p=0
1=1
g=p+1
16g >0
Wlg <0
H
H
Uggt - Mg +
13p S < 3pt1l [ )g)4)
p=0
9=1
4=p+1 +1
>0
Wi <0
p
Σ Mn
1 x 2p-11
1=p+111
p=p+1 th <0
Mig 20
H
Σ
Mg
My +
pgg
x
Pggo
[3p I < 8pti]
9=1
q=1
4= Wy50
g=p+1
Wi >0
>0
<U
Σ
My +
My
Mg
+ Σ Mq
[3p S < Bpt1l
g=p+1 We <0
@=p+1
10,00
<5
Emp
-p
H
MmpT 7p) 13p S x < Sp+1]
This gives us Equation desired.
C.2 RANDOM INITIALIZATION IN FUNCTION SPACE
Lemma 1. Suppose (b,, Ws Ui)) are initialized independently with densities fb().). fw(w),, and [v(U:). Then, the density of (Bi, pu) is given by
(3,,( = J fn( [n(Be))d((W))v
u
Proof. Suppose (bi, wy, v/) are initialized i.i.d. from a distribution with density f TB, (b;, wi, Uz)-
Then, we can derive the density of (3,, 14) by considering the invertable continuous transformation given by (3,, pú, u) = g(b,, Wi, vz) = (b:/w,, v. w.]ws,, w:). where g (B, μ4, u) = (3eu, u, pa p//lu)). The density of (3,, pi, u) is given by fB. (Bru, pi/ [u/[u)))J] where J is the Jacobian determi- nant of - Then, we have J sgu and |J| = 1. The density of (8i, mz) is then derived by integrating out the dummy variable u: (a, p4) = f Te.w.v(Brur u, E du. If (b,, wa, v.)
are independent, this expands S (Bau) fw (w) ( (#) du.
C.3 GAUSSIAN INITIALIZATION IN FUNCTION
Theorem [a). Consider fully connected ReLU neural with scalar input and output, and single hidden layer of width H. Let the weights and biases be initialized randomly according to zero-mean Gaussian or Uniform distribution. Then, under an independent Gaussian initialization.
|pil +
(3,5(3
2TO, Vo 2
exp
T
Proof. Starting with Lemma
(0, 4) = f (wl u
17

---

Under review as a conference paper at ICLR 2020
(du)
1
22
1
(u/u)2
20
20
20 du
-00
2
2TT
2
"Vo
(Sympy)
1 4>0
2ndv
of (3)²
unknown
otherwise
but the integrand is even in μa, giving
exp
Ohoadw
2TT. of + t
Corollary Ta). Consider the same setting Theorem 7 initialization,
In the case of an independent Gaussian
Pa(3:) = Cauchy
0;:0, Tb
Tb
σw
20 + tog)
Pp(H)) 1
1
2o.2
Ko
2TooOw
40 d0
0,0)
To,ow
Voz
o B2
1A4 V o o
Tbo
Pp) = Laplace
pi 0,
Vog
+
2010n.0
exp
where Goo (+)-) is the Meijer G-function and k.(-) the modified Bessel function of the second kind.
Marginalizing out μ from the joint density in Sympy returns the desired fo( from above. Sympy cannot compute the other marginal, so verify it by hand:
Proof.
92 92
|e| to + 82
exp
exp
/-
1
fa(1)
dr
dx
2To
of +
2TT
+ σ $2
|4/ /
exp
( 3
030.0w
dr
2no Ow
Vog
fz
(1(
from Gradshteyn Ryzhik 2015), Eq. 3.462.20, we have
exp
a B2 12
Ko(ab)
d3
[Rea > Reb > 0
32 + 1/2
000 exp
-ay B2 + 62
(integrand is even (3
d3
[Rea > 0, Reb > 0)
2 -00
V 32 + 6²
applying this with
In| and b ab.
abdLow
exp
d3
Ko
2T0
Vo + B2
no.Ow
as desired. We can then use these densities to derive the conditional:
lel
Vol + (B) exp
fa(18))
20.000w
18

---

Under review as a conference paper at ICLR 2020
Tw Voz σ (3)2
Laplace
C.4 UNIFORM INITIALIZATION IN FUNCTION SPACE
Theorem [bb. Consider a fully connected ReLU neural net with scalar input and output, and single hidden layer of width H. Let the weights and biases be initialized randomly according zero-mean Gaussian or Uniform distribution. Then, under an independent Uniform initialization,
(3,, [|ma S min(
asav [.
Ows av3l
ab [3
145
min
Ow
}
40
Proof. Starting with Lemma
J8 (3, =
In(Bu) (o (u)/v(u/u)d
Jaw
1
1
I-ab S Bu S asl
[-aw
S u S awl
[ S u/u /// S avl du
2ab
20
20
I a-aa//l ab/1$11 $ a S ab/l
-I-aw S u S awl
|lu S -lll/a aa V 2 /a// /al/aal du
2ab
20w
201
aw
1
1l--mmmam////////mmmmm aw S u Sus- -lul/a v lml/a
Sus min(as/18l,aae))
Sagawa
x||μ|| I 0181 du
[| I aba,//3111
I- min (31 S sus -lul/av v wn//a s minn(s/|13)) aw H du
[|m] S asa,/|/311
Ilul/a, mim/inna//8)) ane anllee du
[|m] S aba./133)
(min (a/// (33/ a Im4/a,) aw S S aw
aw
as desired.
Corollary lb). Consider the same setting as Theorem 1 In the case of an independent Uniform initialization,
au 1)
2
Pa(3,)
min+
Oh
4apaw
Pp(())
I-a I S awl
log
au [p4
[las] S an min (ss //al/11,,,, 3ml (1- a min fas/ 1.3 aw
Jas
Pa (pa)33) = Tri(uu a, min(at/128 (1cl,aw)))
aml))
ag min (as/ 1/,s//1,ll, aw)
where Tri(;;a) a) is the symmetric triangular distribution with base (-a, a) and mode 0. Proof. Beginning with the marginal of Bi,
fa(3) / (8, (3, du
M| S a50o/1311
(min(ar/13), aw) - -Il//a)) I-away S S awarl dp
4a
au
[| & a55a/18111
(min(as/13)) aw - |1l//a/) dp
4ara
yava [p /60,/181] (min (min(as/131) an} u/aa du
2asawa
19

---

Under review as a conference paper at ICLR 2020
Uue S asar/131] min(ab/13)) aw du
Lu S /aaa///lllu/a au du
am)) / aaway
lu apa 1atee/111llli av I (away
min(as/ (((aa//((,mm))
Lu asan/ /oat//1111 |B] [B]ccpp du
min (3) aw min aawa //13
u
Qa
av
1
min( (3n](a/133.00 a min awaay ( asar/ ||} (min ininda aw asa./ //8))
20,
Ory (min/aa//55) am)))
(ap min aw at/1/3 a//133))2
2a,
0g Oy (min(as/ aw)))²
(min (aws at/ /b/181))²)
2ag
2
4agaw
as desired. Then,
fa(1)) = / (2.
[| S Lasa//lo |81
(/l///a)) a-w S S a dB
--w S awa
[|l S asaa/1311 (minfas/ ///tnn/s//////// aw 1m//a,) d3
4asawa
ayady S anarl
[M|| S ana [1 (min am) lu//a,) d8
4ayawa
1 S awarl
[3 S ana |ul] (minfar/ aw) Im//aw) dg
4a
[- S S awd 2
aa all
min awd 1m1/a, ds
4ayawau
uw S 1 S award
min(arav//ee an//an
au - 11//av dB
40
rasas/lul
ab/B |u//a d3
--a S k S awarl,
as/aw
panaw/
lul/an d3
0a/B
lul/a, an d3
4ayawaa
Jan/aw
[ ayp S 11 S and
-
(as/aw)(aw 1aoi-1//aa (p1//a))
ab/3
1kl/an d3
4ayww
Jas/aw
awa Sus awall 2 4a
pasau/lel
(as/ an (a 1m1/aa))
ab/3d
Jas/au
(Iul/a))asaa - as/awt aw/
aapay S SKS awal, 2
a60./1ml
(as/aw))uw Im//aw) + log ab/a
(lel/a,) uv/aw)
4a
[ anp Su S awa
aban//ml
2ap log
4agawa
ab/Ow abar/li [M]
-- < 11 S and
log
20
ab/aw
aw S 1 S andll log
aw [u]
20

---

Under review as a conference paper at ICLR 2020
as desired. We can then these densities derive the conditional: I| /1
(min (asin(s//in (as/ [3,1 aw luil/a.) I-a M4g S aw
fx(4)3)) =
(min as. 10.5/135ll,, aw 3)²
1ng
I| Sasa, / -a S th, S Re (min ab/ 13: a,ww - leil/an
(min(as/ (at////l, ))
[14 E og min(as/ 1/al aw H Ou minfat/ [/ol: aw)
au min(as/ (ap/|/al,aad awd (1 (1-
Remarks. Note that the marginal distribution on μ4 is the distribution of product of two inde- pendent random variables, and the marginal distribution on 3; is the distribution of the ratio two random variables. For the Gaussian case, the marginal distribution on (4; is symmetric distribution with variance a. and excess Kurtosis 6. For the Uniform case, the marginal distribution of (3; symmetric distribution with finite higher moments. The marginal distribution of 14: is sym-
metric distribution with bounded support and variance 2 and excess Kurtosis of 81 3. 50ewe,
The conditional distribution of 14s given 8i is symmetric distribution with bounded support and variance min(as /18: ". 1)² and excess Kurtosis of
6
C.5 ROUGHNESS OF RANDOM INITIALIZATION
Theorem D
Consider the initial roughness Po under Gaussian initialization. In the He initializa- tion, we have that the tail probability is given by
Pl 2 2
1
X
where Elpol the Glorot initialization, we have that the tail probability given by
PIpoFFpoll 2 2 1+ 128H
(H+11
where E[po] (H+1y² O (
Proof. Using the moments of the delta-slope distribution computed Theorem above, we can compute:
Corollary and
Blu
Varly + FF Ho.00
1=1
Var[po]
Varlu²] H Varlu
-En
i=1
= (9 -
=
Applying the initializations, we have
2 2 11
=
1
4
4
128
Var
8H
H22
H
2
4H
E Glorot
11
O
+
1
1
(H + 1)2
4
4
128H
1
Varlpg Glone
8H
0
(H 112
(1+ Hy
(H
H3
By applying Cantelli's theorem, get the stated tail probabilities.
21

---

Under review as a conference paper at ICLR 2020
C.6 DYNAMICS IN FUNCTION SPACE (BREAKPOINTS AND DELTA-SLOPERS
Theorem 5. For hidden layer univariate ReLU network trained with gradient descent with respect to the neural network parameters NNN = {(W,, bi ")) the gradient flow dynamics of the function space parameters @BDSO {[Br, pi)) are governed by the following laws:
d3; dt
0l(0NN)
o1(() ((((t) O (t). 1) +B,(t) (é(t) (t,,
(4)
03: w;(t)
(t)(t) dt
d((0NN) (1) + w (1)) (ē(1) O ((), x) - -w; (1)b.) (ē(() o az()), (5)
residual
corretation
0p:
Proof.
Computing the time derivatives of the BDSO parameters and using the loss gradients of the loss with respect to the NN parameters gives
@l(0NN) = 0z(ē @ x)
Ow,
@l(0NN) = (è, (w,x + b,1)) (é a, wx b,1) w,(ē o xx,x) - b, o a,
du,
@l(ONN) v @ a, 1)
bb,
(B,(t) d dt
df (- 6,())
wt(()
(l( (b,(1) de
by: (4) de
w. (1)²
w.(()( (b,(C)
0M(NN) ) - b,(()(( 86(9
(1.
we (t)²
wi(() 06(0NN)
(l)
@c(@NN)
06.(0)
(t)
(t)()))()(((())) (t). 1) (a))))))((()))))))))))))))))))))
(1)
(t) (É(I) O (t),), wt)111 (t)x))
())
(1(()
é(() O (1()), bi(1)
x
(t)
wi(t)
(t)
é(t) O a (t), Bx(t)x
(t)
relevant residuals
(1(()
(((()) O (0. +1,(1) (é(1) c
x)).
(t)
(t)(t)
d
relevant residual
correlation
dt
df
dw;
wt du; dt
dt
dl(GNN)
0E(0NN)
Ow,
8v,
-u (e O a,, x) - o a, x) wxbblē o a.,
= (o, + w 2 x,, webb(é o 1)
This completes the proof.
22

---

Under review as a conference paper at ICLR 2020
C.7 LOss SURFACE IN FUNCTION SPACE
Theorem 3 Suppose that for all E [P], f(: ((;0nDo)) is an Ordinary Least Squares fit of the data in piece p. Then, BBDSO is critical point of ((OBDSO).
Proof. If, for all p. f(:0BDDO))l= is an OLS fit of the data Tp. then we must have (éa,: mp) = O, where êx, is the residual for xg. Similarly, must have that the net residual (Ộx, 1) = 0.
Next, consider, for any neuron j. the vector a,. If j is right-facing, å, - (O...., 0, 1..... 1), where the transition from Os to Is corresponds to the data index n where 2n > By: if is left- left-facing, 1-to-0 transition occurs at n. Thus, åy is constant for n E Tp, as the boundaries πр correspond to breakpoints 3 and B1+1- Noting that these inner products for any neuron j. (é @ åy. x) can be decomposed into a sum Σn, (Ctp: Tp) = O, where the sum is over the pieces on the active side of j. Similarly, (é @ Laa 1) Ex, (,Ty. 1) 0.
just sums of products, we have that,
Applying Theorem 5 BDDD))))
see that d8, du 0 for all j, and so BDSO is critical point of
23


Reviews:
[{"review_id": "SkeCSmD6Yr", "reviewer": "AnonReviewer3", "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": "\nThis paper proposes a functional characterization to understand the empirical success of deep neural networks. In particular, this paper focuses on the case of deep fully connected univariate ReLU networks, and show that the parameters will result in a Continuous Piecewise Linear (CPWL) approximation to the target function. Moreover, the authors derive the induced distributions of the function space parameters and show that increasing width can reduce the roughness of the initial function.\n\nBesides, this paper analyzes the loss surface in the function space and reveals some relationship between the critical points in the function space and original NN parameter space. Furthermore, a type of gradient descent dynamic in the function space has also been derived.\n\nMany experiments have been conducted to reveal how the expressiveness and optimization performance varies with the neural network width and depth.\n\nOverall, the functional characterization is interesting can potentially help explain the generalization/expressiveness of deep neural networks. However, this paper is not well written and organized, and there are some “??'s” appearing on page 4. The authors should pay more attention to improving the writing and organization of this paper. \n\nHere are the detailed comments:\n\nThe statements of theorems are not clear. For example, Theorems 3 and 4 convey too much information, I believe the authors should simplify the statements to make them more concise.  Moreover, the purpose of these two lemmas is not clear. Do they imply something related to expressiveness?\nThere should be some discussion in the surrounding text of Theorem 5. Some notations are also missing. For example, what’s $\\hat \\epsilon(t)$?, what’s $a_i(t)$? Besides, what’s the purpose of Theorem 5. It seems that this Theorem is used in the main part of this paper.\nOne major drawback of this paper is that it only provides the theoretical analysis for two-layer networks, but the title and claimed contributions are related to deep ReLU networks. I wonder whether the theory can be extended to deep cases?\nIn Theorem 2, I think He initialization will give you $\\sigma_w = \\sqrt{2/(H+1)}$ and $\\sigma_v = \\sqrt{2/k}$, if the output dimension is k. In this way, I am curious whether Theorem 2 can still hold. Besides, what’s the meaning of the so-called “roughness“?\nI don’t get the point in Implications of Corollary 1. For example, what do you mean “$f$ has significant curvature in the boundaries?”, why an initialization that allocates more breakpoints to the area where the curvature of $f$ lies can be faster to train? The authors should elaborate more on this.\n\n\nAfter reading the authors' response.\n\nThanks for your response.  I still think the contribution of this paper is not enough as the theoretical analysis may not be able to be generalized to deep networks. Thus I would like to keep my score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlbpRPycB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies a number of interesting phenomena in deep learning by characterizing the linear regions of fully connected ReLU networks. The advantage of FC ReLU networks is that they are piecewise linear, and so the overall function can be understood in terms of these linear regions. The paper characterizes both the break points (boundaries) and slopes of these linear regions, using them to shed light on loss surfaces, generalization, and training dynamics.\n\nThe paper has interesting analyses, but I think the main drawback is that the clarity and presentation could be improved.\n\nIn particular, while reading the paper, I found myself wanting:\n- More discussion of connections to relevant work. There have been a few papers (e.g. https://arxiv.org/abs/1611.01491, https://papers.nips.cc/paper/5422-on-the-number-of-linear-regions-of-deep-neural-networks.pdf, http://proceedings.mlr.press/v80/serra18b/serra18b.pdf) that use linear regions to understand deep networks. Reading this paper, I do not get a good understanding of how the work presented here fits into this larger research context.\n- More expository text for particular concepts. A number of results are presented, and it would be helpful to have brief high-level summaries of the main findings of each section after diving through technical details.\n- A number of terms are used before they are defined. For example, \"roughness\" is used on pages 1 and 2 but not defined until page 3. I think adding a preliminaries section with central terms/definitions in the paper clearly laid out could help with the exposition.\n\nOther comments\n- Consider defining breakpoints and delta-slopes when they are introduced at the bottom of pg. 1.\n- typo on pg. 1: by doing *so* using small widths", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJeNrfnRKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper wants to answer the question what is the value of the neural network’s depth? The author targets at Deep ReLU Network and uses Continuous Piecewise Linear (CWPL) to analyze the network’s parameter distribution. The main contributions of this paper are as follows, (1) For common initializations, this paper proves a deeper model will lead to flatter approximations and better approximation over a broader range of inputs. (2) A deeper model performs better when one optimizes with (Gradient Descent) GD methods. (3) Flat Initialization in the overparameterized regime could explain generalization. They found that the value of depth in deep nets seems less about expressivity, but enable GD to find better solutions.\n\nMy decision is Weak Accept, considering the following aspects.\nPositive points: (1) The theory seems solid, authors prove breakpoint and delta-slope distribution will influence by the depth of the network. (2) The conclusions of the paper are inspiring, e.g., depth makes it easier for GD to the optimizer.\n\nNegative points: (1) For the experiment, the authors find breakpoints can’t migrate very far from their initial location. I hope the author could explain this phenomenon since it is very crucial to proving the importance of the breakpoint’s initial distribution. (2) Some formulas in the appendix parts are beyond the scope of the page. \n\nSuggestions: I think that a figure that shows breakpoint and input data distribution together will be very interesting. I want to see the breakpoint’s distribution change as training and its relationship with input data distribution.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article sets out to study the advantages of depth and overparametrization in neural networks from the perspective of function space, with results on univariate shallow fully connected ReLU networks and some experiments on deep networks. 
The article presents results on the concentration /dispersion of the slope / break point distribution of the functions represented by shallow univariate ReLU networks for parameters from various distributions. The reviewers found that the article contains interesting analysis, but that the presentation could be improved. The revision clarified some aspects and included some experiments illustrating breakpoint distributions in relation to the curvature of some target functions. However, the reviewers did not find this convincing enough, pointing out that the analysis focuses on a very restrictive setting and that that presentation of the article still could be improved. The discussion of implicit regularisation in section 2.4 seems promising, but it would benefit from a clearer motivation, background, and discussion. 
Decision: Reject