Deep ReLU Networks Preserve Expected Length
Authors: Boris Hanin
Ryan Jeong
David Rolnick
Venue: ICLR 2022 Poster (2022)
Keywords: deep learning theory
random ReLU networks
length distortion
initialization
expressivity

Abstract: Assessing the complexity of functions computed by a neural network helps us understand how the network will learn and generalize. One natural measure of complexity is how the network distorts length - if the network takes a unit-length curve as input, what is the length of the resulting curve of outputs? It has been widely believed that this length grows exponentially in network depth. We prove that in fact this is not the case: the expected length distortion does not grow with depth, and indeed shrinks slightly, for ReLU networks with standard random initialization. We also generalize this result by proving upper bounds both for higher moments of the length distortion and for the distortion of higher-dimensional volumes. These theoretical results are corroborated by our experiments.

Published as a conference paper at ICLR 2022
DEEP RELU NETWORKS PRESERVE EXPECTED LENGTH
Boris Hanin
Ryan Jeong"
David Rolnick
Dept. of Operations Research & Financial Engineering
Dept. of Mathematics University of Pennsylvania Philadelphia, PA 19104 USA rs rsjeongesas, upenn edu
School of Computer Science
McGill University
Princeton University
Montréal, QC H3A 0G4 Canada drolnick@ cs aogill.... ca
Princeton, NJ 08544 USA
bhanin@princeton.eddi
ABSTRACT
Assessing the complexity of functions computed by a neural network helps understand how the network will learn and generalize. One natural measure of complexity is how the network distorts length - if the network takes a unit-length curve input, what is the length of the resulting curve of outputs? It has been widely believed that this length grows exponentially in network depth. We prove that in fact this is not the case: the expected length distortion does not grow with depth, and indeed shrinks slightly, for ReLU networks with standard random ini- tialization. We also generalize this result by proving upper bounds both for higher moments of the length distortion and for the distortion of higher-dimennionnl vol- umes. These theoretical results corroborated by our experiments.
INTRODUCTION
The utility of deep neural networks ultimately arises from their ability to learn functions that are sufficiently complex to fit training data and yet simple enough to generalize well. Understanding the precise sense in which functions computed by given network have low or high complexity therefore important for studying when the network will perform well. Despite the fundamental importance of this question, our mathematical understanding of the functions expressed and learned by different neural network architectures remains limited.
A popular way to measure the complexity of a neural network function is to compute how it distorts lengths. This may be done by considering set of inputs lying along curve and measuring the length of the corresponding curve of outputs. It has been claimed in prior literature that in a ReLU network this length distortion grows exponentially with the network's depth |Pice & Tanner (201)); Raghu et al. (2017), and this has been used as justification of the power of deeper networks. We prove that, fact, for networks with the typical initialization used in practice expected length distortion does not grow at all with depth.
Our main contributions are:
1. We prove that for ReLU networks initialized with the usual 2/fan-in weight variance, the expected length distortion does not grow with depth at initialization, actually decreasing slightly with depth (Thm. 3.1) and exhibiting an interesting width dependency.
2. We prove bounds on higher moments of the length distortion, giving upper bounds that hold with high probability (Thm. 4.1). We also obtain similar results for the distortion in the volume of higher-dimensions. manifolds of inputs (Thm. 4.2).
3. We empirically verify that our theoretical results accurately predict observed behavior for networks at initialization, while previous bounds are loose and fail to capture subtle archi- tecture dependencies.
is worth explaining why our conclusions differ from those of Price & Tanner (019);; Raghu et al. 2017). First, prior authors prove only lower bounds on the expected length distortion, while we use
"quual contribution

---

Published as a conference paper at ICLR 2022
different methodology to calculate tight upper bounds, allowing to say that the expected length distortion does not grow with depth. As we show in Thm. T.m.55.1 and Fig. [ the prior bounds are in fact quite loose. Second, Thm. 3(a) in Raghu al. (2017) has a critical type which has unfortunately been perpetuated in Thm. 1 of Price & Tanner 2019). Namely, the "2" was omitted in the following statement (paraphrased from the original):
depth
E [length distortion] =22
T T width 2 B5/width+ +1
where / is the variance of the weight distribution. As we prove in Thm. 3.1 leaving out the 2 makes the statement false, incorrectly suggesting that length distortion explodes with depth for the standard He initialization ow = V2.
Finally, prior authors drew the conclusion that length distortion grows exponentially with depth by considering the behavior of ReLU networks with unrealistically large weights. If one multiplies by C' the weights and biases of a ReLU network, one multiplies the length distortion by Cheephh, so it should come as no surprise that there exist settings of the weights for which the distortion grows (or decays) exponentially with depth. The value of results comes in analyzing the behavior specifically at He initialization (o 22) He et al. 2015). This initialization is the one used in practice, since this is the weight variance that must be used the outputs Hanin & Rolnick] (2018) and gradients [Hanin (2018) are to remain well-controleed init. In the present work, show that this is also the correct initialization for the expected length distortion to remain well-behaved.
2 RELATED WORK
range of complexity measures for functions computed by deep neural networks have been consid- ered in the literature, dividing the prior work into at least three categories. In the first, the emphasis on worst-cuse (or best-case) scenarios what is the maximal possible complexity of functions computed by a given network architecture. These works essentially study the expressive power of neural networks and often focus on showing that deep networks are able to express functions that cannot be expressed by shallower networks. For example, it has been shown that it is possible to set the weights of a deep ReLUU network such that the number of linear regions computed by the network grows exponentially in the depth Daniely (2017): [ldan & Shamir (2016); Montúfar al.) (2014); Telgarsky 2015 2016). Other works consider the degree of polynomials approximable by networks of different depths Lin al. (2017); Rolnick & Tegmark (2018) and the topological invariants of networks Bianchini & Scarselli (2014).
While such work has sometimes been used to explain the utility of different neural network archi- tectures (especially deeper ones), a second strand of prior work has shown that a significant gap can exist between the functions expressible by a given architecture and those which may be learned in practice. Such average-cass analyses have indicated that some readily expressible functions are provably difficult to learn Shalev-Shward et al. (2017) or vanishingly unlikely for random networks Hanin & Nical [2020); Hanin & Rolnick (2019 2020), and that some functions learned more easily by deep architectures are nonetheless expressible by shallow ones Ba & Caruanal (2014). (While here we consider neural nets with ReLU activation. it is worth noting that for arithmetic circuits, worst-case and average-case scenarios may be more similar - in both scenarios, a significant gap exists between the matricization rank of the functions computed by deep and shallow architectures Cohen et al. (2016)) As noted earlier, average-case analyses in |Pice & Tanner (2019); Raghu et al.)
(2017) provided lower bounds on expected length distortion, while Poole et (2016) presented
similar analysis for the curvature of output trajectories.
Finally, number of authors have sought complexity measures that either empirically theoretically correlate with generalization Jiang et al. (2019). Such measures have been based on classification margins Bartlett al. (2017). network compressibility Arora et al. (2018. and PAC-Bayes consid-
erations Dziugaite & Roy (2017).
Wee have confirmed this in personal correspondence with the authors, and it is simple to verify the typo arises in the last step of the proof given in the Supplementary Material of Raghu et al. (2017.
2

---

Published as a conference paper at ICLR 2022
3 EXPECTED LENGTH DISTORTION
3.1 MOTIVATION
While neural networks are typically overparameterized and trained with little or no explicit reg- ularization, the functions they learn in practice often able to generalize to unseen data. This phenomenon indicates an implicit regularization that causes these learned functions to be surpris- ingly simple.
Why this occurs is not well-understood theoretically, but there is high level intuition. In a nutshell, randomly initialized neural networks will compute functions of low complexity. Moreover, as op- timization by first order methods is kind of greedy local search, network training is attracted to minima the loss that are not far from the initialization and hence will still be well-behaved.
While this intuition is compelling, key challenge in making it rigorous is to devise appropriate notions of complexity that are small throughout training. The present work is intended to provide piece of the puzzle, making precise the idea that, at the start of training, neural networks com- pute tame functions. Specifically, we demonstrate that neural networks at initialization have low distortion of length and volume, as defined in $32
important aspect our analysis is that we study networks in typical, average-case scenarios. A randomly initialized neural network could, in principle, compute any function expressible by network of that architecture, since the weights might with low probability take on any set of values. Some settings of weights will lead to functions of high complexity, but these settings may be unlikely to occur in practice, depending on the distribution over weights that is under consideration. As prior work has emphasized Price & Tanner (2019); Raghu al. (2017), atypical distributions of weights can lead to exponentially high length distortion. We show that, in contrast, for deep ReLU networks with the standard initialization, the functions computed have low distortion in expectation and with high probability.
(a)
(b)
Log mean detorrtor
-0.0
-035
widhh
-1 00
30
20
-1.2
Depth
Depth
Figure I: Mean length distortion as a function of depth, for randomly initialized ReLU networks of varying architecture. As described in Thm. B.I, distortion not only fails to grow, but shrinks with depth, especially for networks of small width. (a) compares the predictions of our Thm. 5.1 (solid lines) the lower bounds proven in prior work Raghu al. (2017) (dashed lines) and the true empirical means (colored dots), which closely track our predictions. (b) zooms in on the upper part of (a), showing the empirical mean length distortion
function of depth for different widths. The horizontal black line is y = 222.5) the mean length distortion we predict when no = ny in the limit of infinite width for any fixed depth. In each network, width is constant in all hidden layers, while input and output dimension are both The input curve is a fixed line segment of unit length. Length distortion is calculated for 500 different initializations of the weights and biases of the network (the weight variance 2/ fan-iin. For further experimental details, see Appendix B
T(3)
3.2 DEFINITIONS
Let L 2 1 be a positive integer and fix positive integers . n2., We consider a fully connected forwwrd ReL.U network V with input dimension no. output dimension n., and hidden layer
3

---

compute the Published as a conference paper at ICLR 2022
widths R1.... RL-1- Suppose that the weights and biases of N are independent and Gaussian with the weights W between layers & and and biases b(t) in layer satisfying:
wh (0, 20,,2//--1),
0/0) G(O,
Here, C. > is any fixed constant and G(j,, 0²) denotes a Gaussian with mean O and variance a². For any M S RNo, we denote by (MM) g the (random) image M under the map + (x). Our primary object of the study will be the size of the output (MM) relative to that of M. Specifically, when M a I-dimensional curve, define
length distortion len(N((M))
len(M)
Note that while a priori this random variable depends on M, we will find that its statistics depend only on the architecture of N (see Thms. 3.1 and 5.1)
3.3 RESULTS
We prove that the expected length distortion does not grow with depth in fact, it slightly de- creases. Our result may be informally stated thus (for formal statement and proof, see Thm. 5.1 and App. C):
Consider a ReLU Theorem 3.1 (Length distortion: Mean; Informal Statement of Theorem 5.1
network of depth L, input dimension no, output dimension n1, and hidden layer widths ne with weights given by standard He normal initialization He et al. (015)) The expected length distortion is upper bounded by / /TL/ TOL/To- More precisely:
1/2
au+1 2
n1
E llngthh distortion]
xe
exp
C:
70
r
Our experiments align with the the- orem. In Figure empirical mean of the length dis- tortion for randomly initialized deep ReLU networks of various archi- tectures with fixed input and out- dimension. The figure confirms three of our key predictions: (1) the expected length distortion does not grow with depth, and actually decreases slightly; (2) the decrease happens faster for narrower networks (since 1/ne is larger for smaller ne); and (3) for equal input and output di- mension ng n,, there is upper bound of 1 (in fact, the tighter upper bound of C is approximately 0.9515 for = 5. as shown in the fig- ure). The figure also shows the prior bounds in Raghu et al. (2017) to be quite loose. For further experimental details, see Appendix B
1.5
Network
[10, 10, 10]
1.0
[40, 40,
[10, 10, 10, 10, 10]
log (mean distortion)
0.5
[40, 40, 40]
0.0
-0.5
-10
-55
-20
-2
2
log (n (w_hhhhh Dj
Figure 2: Mean length distortion as a function of the ra- tio of output input dimension, for ReLU networks with various architectures (c.g. [10, 10, 10] denotes three hid- randomly initialized as in Figure M We sample 100 pairs of input dimension ng and output dimension n,, each most 50, such that the ratio of output to input dimension is distinct for each such pair. For each pair, 200 different network initializations are tested and the resulting length distortion calculated; the log of the empirical mean is plotted. The dashed black line plots log(y) = log(z), the approxi- mate prediction by Theorem
den layers, each of width 10). All networks
In Fig. 2 we instead fix the set of hid- den layer widths, but vary input and output dimensions. The results con- firm that indeed the expected length distortion grows as the square root of the ratio of output to input dimension.
Note that our theorem also applies for initializations other than He normal; the result in such cases simply less interesting. Suppose initialize the weights in each layer & as i.i.d. normal with
4

---

Published as a conference paper at ICLR 2022
variance /c2/ne11 instead of 2/ng-1- This is equivalent taking He normal initialization and multiplying the weights by c. Multiplying the weights and biases a depth-L ReLU network by simply multiplies the output (and hence the length distortion) by ch, so the expected distortion el times the value given in Thm. 3.1 This emphasizes why an exponentially large distortion necessarily occurs if one sets the weights too large.
3.4 INTUITIVE EXPLANATION
The purpose of this section is to give an intuitive but technical explanation for why, in Theorem 3.1 we find that the distortion (M(N(M)) (M)) of the length of a 1D curve M under the neura network N is typically not much larger than even for deep networks.
Our starting point is that, near a given point æ M, the length of the image under N of small portion of M with length dz is approximately given by [| dx, where Jz is the input-output Jacobian of at the input x and u the unit tangent vector at æ. Prior work (see Fact 7.2 in Allen-Zhu et al. 2019)).
In fact, Lemma on the moments of len(N((M)) (en())))))M))))))) in terms of the moments of the norm || of the Jacobian-vecte product Jzu.
of the Supp. Material, we use a simple argument to give upper bounds
Network Constant 20 Alterneting 10
Thus, upper bounds on the length dis- tortion reduce to studying the Jaco- bian Ja, which in network with hidden layers can be written as a product Jr
First half 10
distortion
JL.---JJ,,, of the layer - 1 to layer Jacobians Jr In worst-case analysis, the left sin- gular vectors of JL,x would align with right singular vectors of J causing the resulting product Jz to have a largest singular value that grows exponentially with L. How- ever, at initialization, this is provably not the with high probability. In- deed, the Jacobians Je.r are indepen- dent (see Lemma C.3 and their sin- gular vectors are therefore incoher- ent. We find in particular (Lemma C.2) the following equality in distri- bution:
0.0
-0.5
1.00
Sum layer reciprocals
Figure 3: Length distortion as function of E/ ny showing both mean and standard deviation across initial- izations. We test several types of network architecture with constant width 20, alternating between widths 30 and 10, and with the first (respectively, second) half of the lay- ers of width 30 and the rest width Each architecture type is tested for several depths. For each such network, we use no = nn 5 and compute length distortion for fixed line segment. As predicted in Thm. 4.1 the mean length distortion decreases with the sum of width reciprocals. Empirical standard devia- tion does not, in general, increase with greater depth, re- maining modest throughout, is consistent with the up- per bound on variance in Thm.
| II Iell
100 initializations
where is the first standard unit vec- tor and the terms in the product are independent. On average each term this product is close 1:
E [| = 1 0(m
This is a consequence of initializing weights to have variance 2/ 2/fan-in. Put together, the two pre- ceding displayed equations suggest writing
||
exp
Σ log(1 Jo
The terms being summed in the exponent are independent and the argument of each logarithm scales like 1 + O(n "). With probability 1 we have for all é that log(I]Jt,ren ll) en where is

---

Published as a conference paper at ICLR 2022
constant depending only on d. Thus, all together,
|| S exp
nt
E=1
with high probability. In particular, in the simple case where nh are proportional to single large constant n, we find the typical size of || is exponential in L/n rather than exponential in L, as in the worst case. If N is wider than it is deep, so that L/n is bounded above, the typical size of ||لير|| and hence of len(N(MM), len(M) remains bounded. Theorem |5. makes this argument precise. Moreover, let note that articles like Daniely) (2017); Giryes et al. (2016); Poole et al.) (2016) show low distortion of angles and volumes very wide networks. Our results, however, apply directly more realistic network widths.
4
FURTHER RESULTS
4.1 HIGHER MOMENTS
We have seen that the mean length distortion is upper-bounded by 1, and indeed by a function of the architecture that decreases with the depth of the network. However, small mean is insufficient by itself to ensure that typical networks have low length distortion. For this, we now show that fact well-controlled. Specifically, the variance is bounded above
all moments of the length distortion by the ratio of output to input dimension, and higher moments are upper-bounded by function that grows very slowly with depth. Our results may be informally stated thus:
Theorem 4.1 (Length distortion: Higher moments). Consider, before, ReLU network of depth L, input dimension ng, output dimension n,, and hidden layer widths ng with weights given by He normal initialization. We have the following bounds higher moments of the length distortion:
Varglength distortion]
n2 no
and E [length distortion)" 11
71LL
exp
CTTL
2
72g
710
c=
for some universal constant 0.
formal statement and proof of this result are given in Theorem 5.1 and Appendix C
We consider the mean and variance of length distortion for wide range of network architectures Figure 3 The figure confirms that variance is modest for architectures and does not increase with depth, and that mean length distortion is consistently decreasing with the sum of layer width reciprocals, as predicted by Theorem
4.2 HIGHER-DIMENSION VOLUMES
Another natural generalization consider is how ReLU networks distort higher-dimensional vol- umes: Given a d-dimensional input M, the output ((M) will in general also be d-dimensional, and we can therefore consider the volume distortion vol((N(MM)) vola(M). The theorems presented in 333 when d = 1 can be extended to all d, and the results may be informally stated thus:
Theorem 4.2 (Volume distortion). Consider a ReLU network of depth L, input dimension no, output dimension n, and hidden layer widths ng, with weights given by He normal initialization. Both the squared mean and the variance of volume distortion are upper-bounde by:
nL
d
L
cxp
n2
no
2
A formal statement and proof of this result are given in Theorem 5.2 and Appendix D
FORMAL STATEMENTS
In this section, we provide formal statements of results. Full proofs given in the appendices.

---

Published as a conference paper at ICLR 2022
5.1 ONE-DIMENSIONAL MANIFOLDS
Fix smooth one-dimensional manifold M C o0 (i.e. a curve) with unit length. Each point on M represents possible input to our ReLU network N. which we recall has input dimension vig, output dimension "L, and hidden layer widths 11:..... P The function x + NN()) computed by N is continuous and piecewise linear. Thus, the image (M) S R of M under this map is a piecewise smooth curve in R with finite number of pieces, and its length len(W((M)) )) is random variable. Our first result states that, provided N wider than it is deep, this distortion is small with high probability at initialization.
Let be a fully connected ReLU network with input dimension no output dimension L, hidden layer widths ,.,....,7 1-11 and independent centered Gaussian weights/biases with the weights having variance 2/fan-in in (as in ) Let M be a 1-dimensional curve of unit length in R Then, the mean length E (en(N((M) equals
Theorem 5.1.
T2L
1/2
r
2
X exp
I-1 5
Σ " +0
Σ
YAn
DL
1/2
t=1
P=1
where implied constants in (()) are universal and I() denotes the Gamma function. Moreover:
Varllen(V(MM)) nL
T4g
Finally, there exist universal constants C1, C2 > 0 such that if m < c1 min (ri...,, then
m/2
E ((en(N(MM)))
n2 nin
exp
C2m
n4
Theorem [5. is proved in CC Several comments are in order. First, we have assumed for simplicity
that M has unit length. For curves of arbitrary length, both the equality (2) and the bounds 3
and (4) all hold and are derived in the same way provided len(N(M)) is replaced by the distortion
len ( (M))/ (eM(M) per unit length.
Second, in the expression (2. note that the exponent tends to 0 as - Do for any fixed L. More precisely, when nhg n large and constant, it scales as -5L/8n. This shows that, for fixed Au. RL. n. the mean E (MM)) is actually decreasing with L. This somewhat surprising phe- [ and consequence of the fact that wide fully connected ReLU nets are strongly contracting (see e.g. Thms. 3 and 4 in Giryes et al. (2016))
nomenon is borne out in Fig.
Third, the pre-factor (nz/no) encodes the fact that, on average over initialization, for any vector of inputs R we have (see e.g. Cor. Hanin & Rolnick (2018)
E [IAT(=)))]]
n2 TiO
||=||
(5)
where the approximate equality becomes exact if the bias variance C₁, is set to 0 (see (I). In other words, at the start training, the network / rescales inputs by an average factor (nz, no) 1/2 This overall scaling factor also dilates (e)()) relative len(M).
Fourth, we stated Theorem 5. for Gaussian weights and biases (see TD). but the result holds for any weight distribution that is symmetric around has variance 2/ effan-in, and has finite higher moments. The only difference is that the constant 5/8 may need to be slightly enlarged (e.g. around 19)).
Finally, all the estimates (2), (3 and factor (mz//ro)1/2 the random variable (MM) is bounded above by log-normal distribution:
consistent with the statement that, up to the scaling
len (en(N((M) <
ni..
1/2
exp
G
B 2
8
where 8 = n and e is a fixed constant.
T10
2
1=1
5.2 HICHER-DIMENSIONAL MANIFOLDS
The results in the previous section generalize to the case when M has higher dimension. To consider this case, fix a positive integer d < min (no. -.. .... and smooth d' dimmensiional manifold M C
7

---

Published as a conference paper at ICLR 2022
R" of unit volume vM) = 1. Note that if d > min (nu..... ......... nL then ((M) is at most (d-1)-dimensions and its d-dimensional volume vanishes. Its image N (M) S IR is a piecewise smooth manifold of dimension at most d. The following result, proved in SD gives an upper bound on the typical value of the d d-dimensional volume of N (M).
Theorem 5.2. Let N be a fully connected ReLU network with imput dimension no. outpul dimension
nL, hidden layer widths n...... ,, and independent centered Gaussian weights/biases with the variance of the weights given by 2/fan-in (see D Let M be a d-dimensional smooth submanifold of 1o with unit volume and d S. min {no.... ................................ T.L }. Then, both the squared mean and the variance of the d didiinnsio volume (M(((MM) of ((M) is bounded above by
L
n2 no
d
exp
nt
(6)
2
PROOF SKETCH
The purpose of this section is to explain the main steps obtaining the mean and variance estimates
2 and (3) from Theorem 5.1 In several places, we will gloss over some mathematical subtleties that we deal with in the detailed proof of Theorem 5. given in Appendix C We will also content ourselves here with proving a slightly weaker estimate than 2 and show instead simply that
1/2
E [en(NV
<
12.,.
and
Var [len(NV
n1 nip
730
We refer the reader to Appendix Since have E [x]
C for a derivation of the more refined result stated in Theorem 5.1 and Var[X] <
< E
x
E [x]] both estimates in follow from
E len (MM)) =
Y1O
To obtain this bound, we begin by relating moments of len(A((M)) to those of the input-output Jacobian of N at a single point for which we need some notation. Namely, let us choose unit speed parameterization M; that is, fix a smooth mapping
7 R R",0
7(t (t)(t)..... Tmo (t))
for which M is the image under y of the interval [0, 1]. That y has unit speed means that for every t e [0, 1] we have [t) = 1, where (t) == (t)....... Ino (t)) Then, the mapping I := N o (for r R - R gives parameterization of the curve N (M). Note that this parameterization not unit speed. Rather the length of ((M) is given by
(en(N((M)) J (T))
Intuitively, the integrand [t)] dt computes, at given t, the length of I(ft, + dt)) as dt + 0. The following Lemma uses (9) to bound the moments of (e)(N((M) in terms of the moments of the norm of the input-output Jacobian Jz. defined for any x. E To by
(NN;
Ju = Ox, (x)
(10)
Isiens 15/50g
where Nr is the i-th component of the network output. Lemma 6.1. We have
E [len(V(M))] < / E [11 dt.
(11)
Sketch of Proof. Taking powers in and interchanging the expectation and integrals, we obtain
E [[eenN((MM)]] = J. /' (Ir((()))] (ta)ll dt
(12)
8

---

Published as a conference paper at ICLR 2022
Applying the inequality ab - (a² + b²), for a, a, I,, the integrand in 12 conclude
E [len(V(AA))] - / [[T(()])))) dt.
(13)
The chain rule yields (1) = (1). Substituting this into completes the proof.
Lemma 6.11 while elementary, appears to be new, allowing length in terms of local quantities such as the moments of [| In particular, having obtained the expression [ have reduced bounding the second moment of len(N((M))
bound global quantities such as
bounding the second moment of the random variable || for a fixed I E R" and unit vector u E R This is simple matter since in our setting the distribution of weights and biases Gaussian and hence, in distribution, || is equal to product of independent random variables:
Proposition 6.2. For any E TR and any unit vector u E RRo, the random variable || equal in distribution to a product of independent scaled chi-squared random variables
T--1
||
RL no0
II
2
Xme
1
X
nt
nLL
where the number of degrees of freedom in the fth term of the product (for I,...,,. 1) is given by an independent binomial ne 4 Bin (ne, 1/2) with ny trials and success probability 1/2. The number of degrees of freedom in the final term is deterministic and given by n.
This Proposition has been derived a number of times in the literature (see Theorem in Hanin 2018) and Fact 7.2 in Allen-Zhu et al. (2019). We provide an alternative proof based on Proposition 2 in Hanin & Nica (2199) in the Supplementary Material. Note that the distribution of [| the same at every and Thus, fixing E 1R and unit vector RRo0 we find
E [en(NV()) < E ||
To prove 8), we note that E
[XA]
=n/22 and apply Lemma 6.2 to find, as desired,
E
[|
n.y. n1
II
E
2
X
2
E
x
2 E
[g
Th
no
n1
710
LIMITATIONS AND FUTURE WORK
We show that deep ReLU networks with appropriate initialization do not appreciably distort lengths and volumes, contrary to prior assumptions of exponential growth. Specifically, we provide exact expression for the mean length distortion, which is bounded above by 1 and decreases slightly with increasing depth. We also prove that higher moments of the length distortion admit well- well-controlled upper bounds, and generalize this to distortion higher dimensional volumes. We show empirically that theoretical results closely match observations, unlike previous loose lower bounds.
There are several notable limitations of this paper, which offer promising directions for future work. First, prove statements for networks at initialization, and results do not necessarily hold after training; analyzing such behavior formally would require consideration of the loss function, optimizer, and data distribution. Second, our results, as stated, do not apply convolutional, resid- ual, or recurrent networks. We envision generalizations for networks with skip connections being straightforward, while formulations for convolutional and recurrent networks will likely be more complicated. In Appendix A we provide preliminary results suggesting that expected length distor- tion decreases modestly with depth both convolutional networks and those with skip connections. Third, we believe that various other measures of complexity for neural networks, such as curvature, likely demonstrate similar behavior to length and volume distortion in average-case scenarios with appropriate initialization. While somewhat parallel results for counting linear regions were shown in Hanin & Rolnick (2019; 2020). there remains much more to be understood for other notions of complexity. Finally, we look forward to work that explicitly ties properties such as low length distor- tion to improved generalization, as well as new learning algorithms that leverage this line of theory in order better control inductive biases fit real-world tasks.

---

Published as a conference paper at ICLR 2022
8 ETHICS STATEMENT
This paper falls within deep learning theory and is intended to advance innovation for more effective and reliable algorithms. However, insofar as our work shows that deep ReLU networks at initializa- tion are better-behaved than was previously believed, this could encourage the use of deeper neural networks. While deeper networks may enhance performance some contexts, larger numbers of pa- rameters are also associated with increased computational cost, which can both increase greenhouse gas emissions and exacerbate inequities caused by differential access to computational resources.
ACKNOWLEDGEMENTS
The authors gratefully acknowledge range of funding sources that supported this research. BH would like to acknowledge NSF grants REER grant DMS-2143754 and an ONR MURI on Foundations of Deep Learning. DR would like to acknowledge support from the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grants program and the Canada CIFAR Al Chairs program.
DMS-2133806 well NSF CA-
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning (ICML), 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference on Machine Learning (ICML), 2018.
Lei Jimmy Ba and Rich Caruana. Do deep nets really need to be deep? In Conference on Neural Information Processing Systems (NeurIPS), 2014.
Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally margin bounds for neural networks. Preprint arXiv:1706.00 084999 2017.
Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A com- parison between shallow and deep architectures. IEEE Transactions on Newral Networks and Learning Systems, 25(8):1553-1565 2014.
Nadav Cohen, Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis. In Conference Learning Theory (COLT), 2016.
Amit Daniely. Depth separation for neural networks. In Conference on Learning Theory (COLT), 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Preprint arXiv: 1008, 2017.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on Learning Theory (COLT), 2016.
Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random Gaussian weights: A universal classification strategy? IEEE Transactions on Signal Processing, 64(13); 3444-3457, 2016.
Boris Hanin. Which neural net architectures give rise to exploding and vanishing gradients? In Conference on Neural Information Processing Systems (NeurIPS), 2018.
Boris Hanin and Mihai Nica. Products of many large random matrices and gradients in deep neural networks. Communications Mathematical Physics, pp. 1-36, 2019.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. In International Conference Learning Representations (ICIR), 2020.
10

---

Published as a conference paper at ICLR 2022
Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture. In Conference on Neural Information Processing Systems (NeurIPS), 2018.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International
Conference on Machine Learning (ICML), 2019.
Boris Hanin and David Rolnick. Deep ReLU networks have surprisingly few activation patterns. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpass- ing human-level performance on ImageNet classification. In IEEE International Conference on Computer Vision (ICCV), 2015.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. Preprint arXiv:1912.02178. 2019.
Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work so well? Journal of Statisticul Physics, 16866):123-12247, 2017.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number lin- regions of deep neural networks. In Conference Neural Information Processing Systems (NeurIPS), 2014.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Expo- nential expressivity in deep neural networks through transient chaos. In Conference on Neural Information Processing Systems (NeurIPS), 2016.
Ilan Price and Jared Tanner. Trajectory growth lower bounds for random sparse deep ReLU net- works. Preprint arXiv:1911.1063 2019.
Maithra Raghu, Ben Poolc, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In International Conference Machine Learning (ICML), 2017.
David Rolnick and Max Tegmark. The power of deeper networks for expressing natural functions. In International Conference on Learning Representations, 2018.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient- deep learning- In International Conference on Machine Learning (ICML), 2017.
Matus Telgarsky. Representation benefits of deep feedforward networks.
Preprint
15Xiv:1509.08100 2015.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on Learning Theory (COLT),
2016.

---

Published as a conference paper at ICLR 2022
A EXPERIMENTS FOR CONVOLUTIONAL AND RESIDUAL NETWORKS
We here provide preliminary experimental results for the mean length distortion networks with convolutional layers and skip connections.
In Figure 4 a). we show results for networks with sequential convolutional layers (without pooling layers), initialized as before with weights ii.d. normal with variance 2/fan-in, and final fully connected layer. We use input dimension no = 16 x 16 x 3 = 768 and output dimension 5. Our results indicate that the mean length distortion is, as expected, approximately equal to Vnl/no R 0.08, and that it decays slightly with depth.
In Figure b). we consider residual networks. Here, the overall network N is defined in terms of residual modules W2,, , and scales 7/1 f2: ..... V according
(wx) = x + (x) + 72N2(( + (x)) +
7LN2 (a + (=)) 72/2
( +...))))
We all residual modules Nu be two-layer. fully connected ReLU networks. In keeping with Hanin & Rolnick (2018), we initialize all weights i.i.d. normal with variance 2/ 2/fan-in, while setting
7h = 1/2 ?I = T/T. Our results suggest that mean length distortion again decays modestly overall, with somewhat sharper decrease for small depths.
(a)
(b)
60m
Width
Layer
10
25
0000
Moant Maanterggh datartion
Mocan kongth distrtoon
1.0
0000
110
Depth
Figure 4: Mean length distortion function of depth, for networks with convolutional layers and skip connections, initialized using He normal initialization He et al. (2015). (a) shows results for networks having convolutional layers, where the input dimension no equals 16 x 16 x 3 768 and output dimension nt equals 5. Here width corresponds to the number of 3 x 3 kernels each layer. As expected, the mean length distortion /nL/no z 0.08 and decays modestly with depth. (b) shows results for networks with skip connections occurring between even layers (i.e. each residual block is fully-connected ReLU network of depth 2), again taking a line segment of unit length the input curve. Here, depth corresponds the total number of layers in the network, that depth-20 network includes 10 residual blocks. Both plots (a) and (b) show the empirical mean over 100 initializations of the weights and biases.
B EXPERIMENTAL DETAILS
For all experiments, weights were initialized from i.i.d. normal distributions with variance 2/fan-in and bias variance 0.1. We run several experiments that involve computing the length distortion of given line segment in Rd We remark how this was done, for which we rely on the notion of linear regions and bent hyperplanes associated with ReLU networks, explored in Hanin & Rolnick 2020 Telgarsky (2015). Specifically, ReLU networks partition input space into a collection of convex polytopes, which we call linear regions, as (generically) distinct linear functions are defined on each region corresponding neuron activated if its pre-activee activation nonnegative). The boundaries of these linear regions are given by sets of points for which a particular neuron has preactivation equal to 0.
different subset of the hidden neurons being activated (where
12

---

Published as a conference paper at ICLR 2022
Say given a line segment with endpoints P1. P2 R parametrized by unit speed on [0, 1], given by the set (P1 + t(P2 P1) e [0,1]]; for which we aim to compute the length distortion. Let w P1.
We first approximate the intersections of the line segment with linear region boundaries using a binary search subroutine. Specificallyy initialize the set S = [0, 0.5, 1], which will contain the parameter values for these approximations. For each iteration of the subroutine, we run the following procedure: for any three consecutive points 1 22; f3 E let X = Pi + (1 - Pi), x2 Pi + t2(P2 - Pi), X3 = P1 + (3 - Pt), and consider the values [V(xx))VVxx)) and (x) X2 These values are equal if the three points are in the same linear region, in which case we eliminate 4 and 13 from S. not equal, then there exists a linear region boundary in the segment from X1 to X3; we add the points fu and Laz to S. We iterate this procedure (15 times in our implementation); for the final iteration, we ensure that only the last point associated with a given linear region is in S.
x
Now take the set S [ti, (2,, 12...., f..] returned by the binary search procedure; we proceed to com- pute the parameter values denoting the exact intersections of the line segment with region bound- determine the set of activated neurons for both points at x; = Pi + (p22 - Pi), Xi+1 = PI + 44+1 (p2 - -PI). solve linear equation to determine the value tr E [0, 1] for which this neuron is O, and replace t, with the exact value t in S Finally, we append and 1 to the respective ends of S (6 0, .i,9....,,,. =1]
aries, which we shall store in S For consecutive points 4, 4i+1 E S, i i= 1, 1,...,
and find the neuron at which these sets differ;
Computing the length distortion is reduced to summing the lengths of the output segments cor- responding consecutive pairs ti, f++1 S Namely, for each such pair, the network is given by a single linear function on the segment of inputs between x; = Pi + f4(p2 - -P)) and Xi+1 = Pi 4++ (p2 10--p.. P1). We calculate the weight matrix W; of this linear function the length of the corresponding output segment is the product of W, with the vector w The total length distortion then given by the sum
W W.w11(((+119
C PROOF OF THEOREM 5.1
Our first step in proving Theorem 5.1 is to obtain bounds on the moments of len(N in terms of the input-output Jacobian of N at single point, which we recall was defined in (00). To accomplish them, we recall the notation from $6 Namely, fix a smooth unit speed parameterization of M = ((0, 1]) with
7 R RTd
(() (m) ... Ymo (1))
The mapping
T Noy, R R
gives parameterization of the curve (MM), and we have
len(N(MD) = /. dt)l
(14)
Let us note an important but ultimately benign technicality. The Jacobian J, of the map x + N(x) not defined at every x (namely those where some neuron turns from on off). Thus, priori, (1( exists only at those for which J-(e) exists. However, the formula (14) is still valid. Indeed, for any setting of weights and biases of N the map is Lipschitz. Thus. by Rademacher's 's theorem, ('(t) exists for almost every t [0. 1] and the length of the curve is given by integrating the norm of this almost-everywhere defined derivative. The following simple Lemma is a generalization of Lemma I and allows us to bound all moments of (M)) in terms of the moments of the norm of the Jacobian vector product [|]
Lemma C.1. For any integer m 2 1, we have
E (len(N <
E [ (ttl""
(15)
13

---

Published as a conference paper at ICLR 2022
Proof. Taking powers in 14 and using Tonelli's theorem to interchange the expectation and inte- grals, we obtain
E [le)(V(M)) = !.
E
(t))l
dt ... .....
(16)
To proceed, let us recall special case of the power mean inequality which says that for any o, we have
II
Applying this to the integrand in (16). we conclude
E (len(V(MM)" S
E [ITT" dt.
(17)
Next, fix E 10. For any neuron z N, denote by x + =(x) its pre-activation. Note that P(z(?(t)) 0) = 0 since our bias variance Cj is set to some fixed positive constant and hence the bias of each neuron has a continuous density. Therefore, with probability over the randomness in the weights and biases of N, there exists neighborhood U of (t) which 2(x) has constant sign for all x E U. The Jacobian Jy(1) is therefore well-defined and the chain rule yields
(t(t) J2(0) (0000)11)))) (t).
(18)
Substituting this into completes the proof.
Having obtained the expression 15
we have reduced bounding the moments len(N((M)) to bounding the moments of the random variable ||س,/|| for fixed E Re and unit vector E R" Prior work (e.g. Thm. in Hanin & Nica (2019) shows that these moments satisfy
E ||
2m
n2
m
exp
5
m
Σ m t=1
0
Σ m m
L-1
no
provided
m
min 1=1....
(19)
Substituting these moment estimates (15) completes the derivation of (4). However, the results in Hanin & Nical (2019) are subtle because they apply to any distribution of weights and biases. They also give the slightly sub-optimal restriction (19) that m must be smaller than constant times the minimum of the nı In the special case where the distribution of weights and biases is Gaussian, can do slightly better by computing the moments of ||اار|| more directly (note that in the statement of Theorem 5.I. required only that is smaller than constant times the minimum of the 's). We will need this anyway to derive the slightly more refined estimates in 22) and (3) Let us therefore check that, in distribution, [ is equal
product of independent random variables:
Proposition C.2. For any th and any unit vector u E IR"', the random variable || is equal distribution to product of independent scaled chi-squared random variables
|
nL
II [=1
2
Xme
1
X
Ti
ThE
n.
where the number of degrees freedom the Eth term of the product (for l. 1,..., L- by an independent binomial
1) given
ne Bin (ng, 1/2)
with ny trials and success probability 1/2. The number of degrees of freedom in the final term is deterministic and given by nt.
14

---

Published as a conference paper at ICLR 2022
Proof. Consider ReLU network / with imput dimension 1, output dimension nz. and hidden layer widths ....... RLL-1 Suppose the weight matrices W(() and bias vectors ((4) are independent with i..dd Gaussian components:
G(O, 2/002)/)))).
0 G(O, Cb);
where C. O is any fixed constant. For fixed network input x R with probability 1, the input-output Jacobian Jz is well-defined. Moreover, it can be written as
J+ w 1(4-)) (())
where ( is the matrix of weights from layer l layer l and D an ny x ne diagonal matrix:
D Diag 1 (10020))1-11.....
whose diagonal entries are 0 depending whether the an-aciivvation 2, (6) of neuron i in layer is positive at our fixed input x. Next, according to Proposition 2 in Hanin & Nical (2019), the marginal distribution of each D( that its diagonal entries are independent Bernoulli (1/2 l/2) random variables. Morcover, have the following equality in distribution:
Ju A 1W (D())
where D are independent of each other (and of W(9) resampled from the marginal distribution of ( and y is an independent diagonal matrix with independent diagonal entries that are + with equal probability. In particular, for fixed unit vector u E R"0 we have
| 11 D (()
We may rewrite this
W
(2) (
(20)
for (1) p00 [aa where we interpret the expression 20 as equal to O if D()) is the zero matrix. To complete the proof, need the following standard observation.
Lemma C.3. Suppose W is an x n' matrix with i.i.d. Gaussian entries and u. is random unit vector in T8" that is independent of W but otherwise has any distribution. Then W u is independent of u and is equal in distribution to We where is any fixed unit vector in R=".
Proof. For any fixed orthogonal matrix O, it is standard fact that WO is equal in distribution to W. Thus, for any measurable sets A C I² and B IR"", since u, W are independent have
[ gu
P [WWuEAuEE
P(W E A) dlP.(uu (wo),
where P.. (uo) is the distribution of u. Fix any up E Sm' and = (uo) any orthogonal matrix so that Oe, with el (1, 0, ......0) 0) is the first standard unit vector. Then, since W O is equal in distribution to W, we have
P P( ug E A)= (We E A),
which is independent of ug. We therefore find
PP P(Wu E B) (Wer A)P(uE
desired.
We in position complete the proof of Proposition C.2 20 we find that, distribution [|Juu|] equals
Combining Lemma C with
| 2 (2)) ( (1)
(21)
15

---

Published as a conference paper at ICLR 2022
Note that these two terms are independent. Repeating this argument, obtain that |Jau]] is equal in distribution to the product
[ ||D ull |DD()) al]-
(22)
The terms in this product are independent. To complete the proof note that for l 1,.... the number of non-zero entries in D( is a binomial random variable ng with ne trials, each with probability of success 1/2 and that
ID(O
precisely 2/ri times a sum of ny squares of independent standard Gaussians. Thus, for 1. 1.
|
Xne
(23)
nk-1
Similarly
||
u
Xns.
(24)
n
Substituting 233 and 24 into 22 completes the proof.
Evaluating the moments of (cn(W(M)) is now a matter of computing the moments some scaled chi-squared random variables with random number of degrees of freedom. For instance, recalling that
E
xi
k
and applying Lemma C.2 as well as the tower property of the expectation we find
E
||]
n
E
Xne
2
E
[n
xax
no
n1.
E=1
L-1
nz
2
E
E
Xur
ne
no
n
nL
2
E
[ne]
nu
ne
{=1
n0
Substituting this into 15
with m = yields
Var [len(N(MM)] <
72 no
yielding 3 To prove 2 we need to estimate E [len By taking expectations in 14 and
using 18), we find
f E (001 di E [|]),u]]),
E [ee))(MM
where we' we've used that by Lemma C.2 the distribution of [|| is the same for every Ro and every unit vector u. Moreover, again using Lemma
u||
C.2
we see that E [[]], equals
1/2
1/2
1/2
X
E
X
Tig
TT1.
To simplify this, a direct computation shows that
r (ktl)
(k x2) 1/2
E
r (()) (b) 1/2
16

---

Published as a conference paper at ICLR 2022
where r(-) is the Gamma function. Next, for any positive random variable X with E [X] 1 have
E X1/2 =E (1 (X 1))
1 Var[X] + +[Ix 118).
Recall that
Varlxa] 2k.
Using this and the law of total variance yields
1/2
2
E
2 Xne
Var Var[xnd O(n
2n
2
E Varlx
nel
2n
Var E [x
[e]]]
[E [2ne] + Var[ne]] + O
2n
ne + nt
+ +0
2n
4
5
O( 3)
8nz
Thus, we find that E [len(A(MM)) equals
1/2
21++1
5
exp
n O
Σ
n
1/2
as claimed. Finally, let us check the higher moment estimates following estimate
By Lemma
we have the
2
|
2 Xne
-1 2
n
XnL
no
11g
(=1
L-1
11
n
Σ
exp
Xne
no
n4g
where we used that x = x
+
< ---
For any m, we have
1
m
2
2m 2
E
Xmn.
1
1
nT.
y.
2j
m
< exp
exp
12
Therefore, ||]
(m is bounded above by
n
exp
L-1
2
Xns
2
-
+
m²
(25)
n2
t=1
Finally, for any fixed positive integer may write
A
2
Σ
Es
ZZ
2
1
n
17

---

Published as a conference paper at ICLR 2022
where are independent Bernouli(1122) random variables and Zą are independent standard Gaus- sians. A direct computation shows that the centered random variables &x Z are sub-exponential SE(r2 ax) with some universal parameters v², a. Thus, by the stability of sub-exponential random variables under summation have
2
4v/2
2a
2 Anz
1 SE
T/g
nt
Again using this property we conclude
4-1 2a
2
Xnr
SE
4v
n1
7ig
Th
where
n. = min ........ a nL-1)
Therefore, by 25 we find that
E
|
2m
<
n1..
E
[em)
exp
m
nn
where E SE [du2
Et=l 1
2a me" n.
)
By definition of sub-exponential random variables, we have
1
E mY
S
exp 4m v
T4g
provided m < n2/22 for some universal constant c > 0. This completes the derivation of and
completes the proof of Theorem 5.1
D PROOF OF THEOREM 5.2
The proof of Theorem 5.2 follows closely the argument for Theorem 5.1 For a given input x E R",,
will continue to write
Jv(x) (0,, (1Si5m)) [ISiSn))
for the input-output Jacobian of the network function, which exists for Lebesgue almost every x Re0 We will write II, M "o" + T.M for the orthogonal projection onto this tangent space. We have
vola(N(M)) - - (det JN(x))) JN (x 1/2 vola(dr),
where vola is the d- dimensiiona Hausdorff measure. Indeed, the integrand measures, at each x E M, the volume of the image of an infinitesimal cube M of volume vola(dæ) centered under the map + N()). Arguing precisely as in the proof of Lemma C.I we find that for any integer m 1
/
E. [voo)(((MM))''
E [det (rt vola(dx)
(26)
Fix E M and denote by
(I()). ea(x))
an orthonormal basis of the tangent space of M. Then, by the Gram identity, we may write
det (II, Jx()) = (J)(())) " A (
(27)
where we recall that the wedge product the anti-syymetrizztton of the tensor product. Just in the proof of Theorem 5. the key observation is that for Gaussian weights we have that ([Ja(z)) (x) A... (x(x)e((z)) is a product of i...d. random variables. The formal statement the following:
18

---

Published as a conference paper at ICLR 2022
Proposition D.1. For any R and collection of orthonormal unit vectors , Ud E R" the random variable
1| A... A J
equal distribution to product of independent scaled chi- mui-squrred random variables:
1-1
RL
2
Anc-jt1
II
Xny
j++1
n20
f=1
jim
n
where all the terms in the product are independent and for i = I,...,L L we 've written n. for independent Binomial random variables:
nt Bin (ng. 1/2)
with ni trials and success probability 1/2.
Proof. The proof is identical to that of Lemma C.2 following amplification of Lemma
The only difference is that we must invoke the
Lemma D.2. Let Ui ..... Ug R. be a collection of orthonormal vectors (i.e. collection) with any distribution. Let W be an independent n x v' matrix with i.i.d. Gaussian entries. Then
W(u1 A uu) - Wuy A ... A Wu
independent un A... A up and is equal in distribution W en Wee en where U1y...y Uk any fixed collection of orthonormal vectors.
Proof. The proof is identical that of Lemma except that we note that for that, given U1. Uk there exists an orthogonal matrix O = -w,,,... Uk) so that
= Oej, j= k
where ej are the standard basis vectors.
With Lemma D.I in hand, we complete the proof of Theorem 5.2 as follows. First, note that for any random variable X we have
E [
[x]]
1/2
Var[X]
< [
Hence, Theorem 5.2 will follow show that
E [N
n2
d
exp
n
730
2
Em
Combining Proposition D.I with 26 and
27
this estimate follows by showing that
E Jau A ... J
exp
n
(28)
no
E=1
To check this, recall that
[x2]
k.
Hence,
L--1
(I)())) A-. (-. (x(())c((=))
nr.
2
E
II j=1
E
s+1
710
Thg
nu
j=1
nL
d
L
d
j
Vio
8=1
[=1j=1
n1
d
exp
n2
71o
where in the last line used that
e This completes the proof.
19


Reviews:
[{"review_id": "wumjQj1TBlo", "reviewer": "Reviewer_MMSS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Overall, this is a well-written paper that follows all the best practices of making a theoretical contribution easy to assimilate in deep learning: they carefully introduce the main topic of interest, describe their results in plain English, informally state their main results and the intuition behind them while also generously illustrating those results through figures, then state the precise results with proofs in the appendix, and wrap up with a clear definition of what was achieved and what is left as future work. \n\nThe authors even include a section in the appendix on CNNs to avoid the typical reviewer question about having tried it in CNNs: I feel your pain!\n\n# Specific comments\n\nIn Section 2, when you say that \"it has been shown that it is possible to set the weights of a deep ReLU network such that the number of linear regions computed by the network grows exponentially in the depth\", you should also mention negative results in depth for linear regions such as the depth-width tradeoff discussed in [1]. \n\nWhen discussing expected results on linear regions, perhaps it would be worth also mentioning more recent results concerning maxout networks [2].\n\nIn Section 3, please rewrite this: \"This phenomenon indicates an implicit regularization towards causes these learned functions to be surprisingly simple.\"\n\nIn Figure 1: What is the number of hidden layers used? What happens when it varies?\n\nWhen you describe the setting in Section 3, it is not said explicitly that $L$ is the number of hidden layers. Hence, can you please rewrite \"and hidden layer widths\" as something like \"and $L$ hidden layers with widths\"? \n\nOther small issues in Section 3:\n- \"Our primary object of the study\": remove \"the\", or replace \"of\" with \"in\"\n- \"apply an $\\epsilon$-net argument\": please describe it in more detail\n\nWhen I first skimmed the paper, I was disappointed that there was no conclusion, only to find out later than the first paragraph of Section 7 is indeed a conclusion. Perhaps it would be worth renaming Secton 7 as something like \"Conclusion, Limitations, and Future Work\".\n\nIn Section 7, I would rewrite \"There are several notable limitations of this paper\" as \"This paper has several notable limitations\".\n\nAs you discuss looking into more detail on convolutional networks, perhaps it would be worth citing related work on linear regions for CNNs [3].\n\n# References cited\n\n[1] https://arxiv.org/abs/1711.02114\n\n[2] https://arxiv.org/abs/2107.00379\n\n[3] https://arxiv.org/abs/2006.00978", "summary_of_the_paper": "This paper presents results on the expected trajectory length of the outputs of a neural network at initialization with respect to the trajectory length of the inputs. The study of trajectory length is a spin-off of the study of linear regions in neural networks, since both are discussed in the first paper by Raghu et al. (2017). Notably, this paper analyzes trajectory length through the same lenses used in subsequent work on linear regions by Hanin and Rolnick (2019), which has shown that the number of linear regions for weights typically used at initialization does not allow the corresponding metric to grow exponentially on the depth of the network.\n\nIn addition, the authors point out at a missing coefficient in prior results on trajectory length that lead to very different conclusions; and they also provide results on higher moments of trajectory length as well as on the multi-dimensional case of expected volume.", "summary_of_the_review": "The paper is well organized, adds more nuance to our understanding of the expressiveness of neural networks, but also leaves a taste of the expected length after training being an obvious follow-up paper which could have fit here as well. I would have been happier to see the whole affair discussed as a single and stronger paper, but I believe that the contributions here are enough to cross the acceptance line.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "el4SEdS-XS", "reviewer": "Reviewer_VKDK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "## Strengths\n\nThe paper answers a relevant question which was previously addressed by the community albeit with wrong conclusions. The formal results and the proofs are as far as I can tell correct and they agree perfectly with the numerical simulations. The paper is very well written and easy to follow. The proofs are simple and sufficiently verbose to follow without difficulty.\n\nThe paper makes progress on understanding random neural networks which may be seen as a program analogous to that of random matrices, and is similarly likely to yield important insight and serve as a good model for real nonlinear systems.\n\n## Weaknesses\n\nThe paper does exactly what it advertises. I can list some weaknesses but they are more \"things that would be nice to have\" than real problems with the current manuscript. \n\n- One obvious question is what happens for activation functions other than the ReLU? The current manuscript relies on available estimates for ReLU networks. It would be interesting to probe this numerically and perhaps formulate some coarse conjectures.\n- Another small weakness is perhaps the lack of connections to other literature such as that on Lipschitz constant of ReLU nets and injectivity of ReLU nets. There may be interesting topological implications of length and volume preservation. But again, the paper is very clear and adding too much too fast could spoil the clarity.\n- While the result for curves ($d = 1$) gives (implies) matching upper and lower bounds on distortion, the result for general $d$-dimensional volumes is only an upper bound. Why is that the case? How hard would it be to get a lower bound?\n- (Again somehow related to injectivity): you write in Section 4.2 that the output $\\mathcal{N}(M)$ will in general be $d$-dimensional, but this seems to imply a condition on the layer widths. (E.g. a bottleneck would be problematic.) Now, since you take the expectation, even averaging $d/2$-dimensional sets will yield a $d$-dimensional set (analogously to how averaging random low-rank matrices gives a full rank matrix) and the result may hold, but I feel this merits a short discussion and perhaps a rewording.\n\n## Notes\n\n- The results seem to be related to bi-Lipschitzness and injectivity of ReLU networks, but not equivalent (since you calculate the $d$-dimensional Hausdorff volume). I wonder whether your techniques could indeed be used to say something about injectivity and conditioning of deep ReLU nets (perhaps along the lines of https://arxiv.org/abs/2006.08464)? A random question: what are the implications of letting the curve $M$ be a space-filling curve?\n- Still related (only rephrased): the results are given for a fixed curve. If the dimensions of the layers are chosen so that some of the layers are with high probability not injective, then for a given network one can find input curves that will be highly distorted. What can be said about the totality of curves for which low distortion can be expected?\n- What is the significance of the bound on $m$ in terms of the layer widths? Do you expect that similar moment bounds exist for large $m$ as well? (Related: currently you state results about the mean distortion length and moment bounds, but no high-probability result.)\n\n\n### Minor things and questions\n\n- In the introduction you write \"A popular way to measure the complexity of a neural network function is to compute how it distorts lengths.\"—one could imagine that a network does something really bad to a curve while keeping its length intact. That would mean that the network is in some sense complex and the criterion would have to be sharpened, no?\n- Section 5.1, \"... than it is deep, this distortion is... \" -> \"the length distortion is...\"\n- Section 5.1, \"... the constant 5/8 may need to be slightly enlarged (e.g. around (20))\" -> please expand the parenthesis to make it clearer what you mean\n- Proof of Theorem 5.2: \"... the orthogonal projection onto this tangent space...\" -> what is \"this\" referring to? Perhaps first define the tangent space. Also: please provide precise references for the used differential geometric results such as the transformed volume in the display before (27) or the Gram identity with wedge products in (28)\n- Proof of Lemma D.2: \"... except that we note that for that, given...\" -> \"except that given $u_1, \\ldots, u_k$, there exists...\"\n- After this proof you write \"With Lemma D.1 in hand, ...\". Should that be Lemma D.2?\n- Last display on page 17: should this equality be in distribution?\n- Second line of the first display on page 17: I suppose the meaning of the big-O here implies (or is missing) an expectation\n- page 16: \"where we've used that by Lemma C.2...\" -> should that be Proposition C.2? (or why not make it a Lemma?).  Please check globally for similar issues.\n- In the proof of Lemma C.3, should the integral in the first display be over $B$? Also, should $B \\subseteq \\mathbb{S}^{n'-1}$?\n", "summary_of_the_paper": "This paper shows that, given a fixed curve $M : [0, 1] \\to \\mathbb{R}^{n_0}$ of unit length, and a randomly-initialized (using standard He initialization) ReLU network $\\mathcal{N}$ with input dimension $n_0$ and layer widths $n_1, \\ldots, n_L$, the length of the curve $\\mathcal{N}(M)$ is close to $\\sqrt{n_L / n_0}$ on average (/with high probability). The work improves on (and corrects) related existing results for random neural networks. This existing work concludes that the length distortion grows exponentially with depth, but 1) depending on the weight normalization it is straightforward to see that this may happen; one should thus choose the standard 2/fan-in variance for initialization, 2) it contains a bug which makes it seem that even for the standard He initialization the length distortion explodes with increasing depth. The present manuscript shows (theoretically and experimentally) that this is not the case. The results make use of estimates from Giryes et al. (2016) and Hanin & Rolnick (2018) for random ReLU networks.\n\nThe main technical idea (which I find very nice) is to relate global quantities such as expected length or square-of-length to local properties of the Jacobian by using the AM-GM inequality. \n", "summary_of_the_review": "This is a very well-written paper about an important topic which clears up some confusion caused by bugs in prior work. The arguments are clear and simple and likely to be useful to other researchers. Improvements and additions are certainly imaginable but inessential. I therefore recommend acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IAx6IC2rnrA", "reviewer": "Reviewer_TwSU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "This paper is well written and addresses an important problem using very careful derivations. It is a welcome addition to the literature, since it was not obvious that typical network initialization yields a non-explosion of length distortion as the network grows deeper.\n\nThe main limitations I see are: (1) the results apply to randomly initialized networks and not to trained networks; (2) the results apply to fully connected networks and not to architectures like ResNet or Transformer. The authors are well aware of these limitations, and preliminary empirical results for (2) are present in Appendix A. I don't believe any further improvement to address these limitations is needed.\n\nThe following are minor comments that I have.\n\n* Page 3, third line of the first paragraph: “towards” → “that”\n* Caption of Figure 1: can you increase the margins a bit? Otherwise the caption can be confused with the main text. Also, this figure is in the middle of the page, but it could be placed at the top or bottom of the page instead to avoid interruption (since it is not even referenced in the current section, so there is no use in interrupting the flow of text there).\n* Page 4: it is quite confusing to have a discussion on Figure 1 side by side with Figure 2. Similarly, Figure 3 is far from the place where it is actually referenced. I think it would be good to re-organize the placement of all figures.\n* End of Section 6: better to place the qed symbol on the same line as the equation (you can use \\qedhere if you are inside a proof environment). This will also save you some space.", "summary_of_the_paper": "This paper computes/estimates the mean and higher moments of the length distortion of fully connected ReLU networks at initialization, assuming typical random initialization of the weights. In particular, it shows that length distortion does not grow with the depth of the network (as previously believed). The paper also presents analog results for the average distortion of higher-dimensional volumes.", "summary_of_the_review": "This paper provides a novel set of theorems on distortion of length and volume. It is well written and precise.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-TMebHTwD5q", "reviewer": "Reviewer_mxm7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The problem is interesting and the authors have motivated it well; However the results are far from surprising or novel. \n\nThe technical challenge is to bound the spectral norm of the Jacobian of each layer (for random weights). and then use independence. \nNevertheless, the appearance of ReLUs (non-linearities) makes things challenging. The main idea is effectively to prove that the Jacobian can be ``viewed\" as a product of i.i.d Gaussian and Diagonal matrices with Bernoulli random variables on the diagonal.\nThese technical ideas have appeared in other papers before (e.g., Allen Zhu et al \"A convergence theory for deep learning via overparameterization.\").  What seems quite frustrating is that the authors mention in the abstract \"it is widely believed that length grows exponentially in network depth\". They authors prove the contrary, but this counterintuitive fact was already proved to some extent and therefore the claim in the abstract is misleading. Moreover, I would like to note that even the result about distortion on manifolds may seem novel, it is basically reduced to the 1-dimensional case in a straightforward manner. \n\nOverall, this is some interesting but technically incremental work that I would be willing to give a score of weak accept, but not on its current form. I would be willing to increase my score in the next revision of the paper as long as the abstract is changed (remove the phrase \"it is widely believed...\") and authors add some comparison of their \\textbf{techniques} with those of the other papers like Allen-Zhu et al. (which are already cited) are added in the \\textbf{intro and related work}. In words, what are the technical merits of the paper compared to Allen-Zhu et al, Hanin etc? Moreover, Allen-Zhu et al Fact 7.2 is so related to this work but is not mentioned at the related work! \nIt is crucial to do some restructuring so that readers/researchers that are not familiar with the literature, will not to get a wrong impression/message.  \n\n===============================================================================\nAfter authors response and their changes in the document, I change my score to 6.\n", "summary_of_the_paper": "The paper's main focus is on the following question: \"How the length of the output of a NN is distorted with its input length\". \nThe main assumption is that the weights of the NN are sampled from Gaussian Distributions N(0, 2/fin) where fin is the size of the input for each particular neuron. We would like to note that this is a standard initialization that appears in the literature and implementation packages. \n\nThe authors prove upper bounds on the expected length of the output for unit length inputs where the expectation is taken with respect to the initialized. The authors also provide bounds for higher moments and prove similar results for higher dimensional manifolds (instead of 1-dimensional curves). The bound is roughly the ratio of the number of neurons of last and first layer and actually the length does not explode as the number of layers grows. This fact is claimed to be surprising by the authors (though I disagree, see my comments below).\n\n", "summary_of_the_review": "I feel that the results technically are incremental given the literature (e.g., Allen Zhu et al \"A convergence theory for deep learning via overparameterization.\" and other papers). Nevertheless, my main issue is the way the abstract is written (effectively overselling the result), since it is not widely believed (indeed there is a highly cited paper that claims what is \"widely believed\") but those researchers that have read Fact 7.2 in Allen Zhu et al do not believe this claim. Distortion on Manifolds and higher moment analysis makes the paper weak accept if my comments are addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the length distortion in a random (deep) ReLU network — namely, it bounds the expectation and higher moments of the length of the curve in feature space produced by applying a random ReLU work to a smooth curve. Because the product of layer norms grows exponentially in the depth, it might be natural to conjecture that the length grows exponentially in depth. Indeed, this has been claimed in previous theoretical work. The submission argues through rigorous mathematical analysis and corroborating experiments that this claim is incorrect. In fact, the length exhibits a slow (1/depth) contraction as the network depth increases. The paper also works out higher order moments and extensions to higher dimensional volumes. These results are obtained using nice (and natural) independence arguments and calculations. 

Initial reviews were mostly positive, with the reservation that the initial submission may have slightly over claimed (the reviewer correctly notes that it is impossible to prove interesting results about the NTK of deep networks with the incorrect exponential growth hypothesis, and that related, and correct, arguments are embedded in the proofs of a number of NTK adjacent papers). After responses and revisions from the authors, the reviewers uniformly recommend acceptance. This is a solid paper, with an important conceptual point — length/volume contraction is critical to reasoning correctly about feature evolution in deep networks. In addition, it corrects existing errors in the literature, and provides relatively transparent justifications of its main claims. 

The AC concurs with the reviewers’ evaluation of the paper, and recommends acceptance.
Decision: Accept (Poster)