A Johnson-Lindenstrauss Framework for Randomly Initialized CNNs
Authors: Ido Nachum
Jan Hazla
Michael Gastpar
Anatoly Khina
Venue: ICLR 2022 Poster (2022)
Keywords: convolutional neural networks
Johnson-Lindenstrauss lemma
initialization
isometry
theory.

Abstract: How does the geometric representation of a dataset change after the application of each randomly initialized layer of a neural network? The celebrated Johnson-Lindenstrauss lemma answers this question for linear fully-connected neural networks (FNNs), stating that the geometry is essentially preserved. For FNNs with the ReLU activation, the angle between two input contracts according to a known mapping. The question for non-linear convolutional neural networks (CNNs) becomes much more intricate. To answer this question, we introduce a geometric framework. For linear CNNs, we show that the Johnson--Lindenstrauss lemma continues to hold, namely, that the angle between two inputs is preserved. For CNNs with ReLU activation, on the other hand, the behavior is richer: The angle between the outputs contracts, where the level of contraction depends on the nature of the inputs. In particular, after one layer, the geometry of natural images is essentially preserved, whereas for Gaussian correlated inputs, CNNs exhibit the same contracting behavior as FNNs with ReLU activation. 

Published as a conference paper at ICLR 2022
A JOHNSON-LINDENSTRAUSS FRAMEWORK FOR RANDOMLY INITIALIZED CNNS
Ido Nachum, Jan Hazda, Michael Gastpar School Computer and Communication Sciences École Polytechnique Fédérale de Lausanne 1015 Lausanne, Switzerland (forename. surname)@epfl.cht
Anatoly Khina
School of Electrical Engineering
Tel Aviv University
Tel Aviv 6997801, Israel
anatolykéeng tau.ac.i.
ABSTRACT
How does the geometric representation of dataset change after the application of each randomly initialized layer of a neural network? The celebrated Johnson- Lindenstrauss lemma answers this question for linear fully-connected neural net- works (FNNs), stating that the geometry is essentially preserved. For FNNs with the ReLU activation, the angle between two inputs contracts according to a known mapping. The question for non-linear convolutional neural networks (CNNs) be- comes much more intricate. To answer this question, we introduce a geometric framework. For linear CNNs, we show that the Johnson-Lindenstrune continues to hold, namely, that the angle between two inputs is preserved. For CNNs with ReLU activation, on the other hand, the behavior is richer: The angle between the outputs contracts, where the level of contraction depends on the na- ture of the inputs. In particular, after layer, the geometry of natural images is essentially preserved, whereas for Gaussian correlated inputs, CNNs exhibit the same contracting behavior as FNNs with ReLU activation.
lemma
INTRODUCTION
Neural networks have become a standard tool in multiple scientific fields, due to their success in clas- sification (and estimation) tasks. Conceptually, this success is achieved since better representation allowed by each subsequent layer until linear separability is achieved at the last (linear) layer. In- deed, in many disciplines involving real-world tasks, such computer vision and natural language processing, the training process is biased toward these favorable representations. This bias is prod- uct of several factors, with the ceural-network initialization playing a pivotal role (Sutskever et all 2013). Therefore, we concentrate in this work on studying the initialization of neural networks, with the following question guiding this work.
How does the geometric representation of a dataset change after the application of each randomly initialized layer of a neural network?
To answer this, we study how the following two geometrical quantities change after each layer.
(x, y) p: T
The scalar inner product between vectors x and y_
(0.9)
The cosine similarity (or simply similarity) between vectors and y.
The similarity p E [-1,1] between x and y equals p = cos(O), where is the angle between them.
Consider first one layer of a fully connected neural network (FNN) with an identity activation (linear FNN) that is initialized by independent identically distributed (i.i.d)) Gaussian weights with mean zero and variance 1/N, where N is the number of neurons in that layer. This random linear FNN induces an isometric embedding of the dataset, namely, the similarity Pin between any two inputs,
We mean here vector in a wider sense: and y may he matrices and tensors (of the same dimensions). In this situation, the standard inner product is equal the vectorization thereof: (æ,, y) (ver(z), vec(y)).

---

Published as a conference paper at ICLR 2022
Fin and Vin is preserved together with their norm:
Pout R Pout
Pins
where Pout the similarity between the resulting random (due to the multiplication by the random weights) outputs, Xout and Yout (respectively), and Pout is the mean output similarity defined by
(Xout, Your) Pout = ||ont Yout|]
E [Xout Your)
and
Pout
(1)
E
X |1]
Ie [1I
1|
The proof of this isometric relation between the input and output similarities follows from the celebrated Johnson-Lindenstrrass lemma (Johnson and Lindenstrauss, [1984 Dasgupta and Gupta 1999). This lemma states that a random linear map of dimension N preserves the distance be- tween any two points up to > 0 contraction/exxpassoo with probability at least 1 d for all N > e clog(1/))/e² for an absolute constant c. In the context of randomly initialized linear FNNs, this result means that, for number of neurons N that satisfies N > clog
P (IPout - Pial < e) 21
So, conceptually, the Johnson- Lindenstrauss lemma studies how inner products (or geometry) change, in expectation, after applying random transformation and how well average of these random transformations is concentrated around the expectation. This is the exact setting of randomly initialized neural networks. The random transformations consist of random projection (multiplying the dataset by random matrix) which is followed by non-linearity.
Naturally, adding non-linearity complicates the picture. Let focus the case where the activa- tion function is a rectified linear unit (ReL.U). That is, consider random fully-connected layer with ReLU activation initialized with i.i.d. zero-mean Gaussian weights and two different inputs. For this case, Cho and Saul (2009), Girves et al. (2016), and Daniely et al. (2016) proved that
Pi + (N cos (Pin)) Pin
Pout Rd Pout.
π
Following Daniely et all (016), we refer to the resulting function in 2 of Pout in Pin as the dual activation of the ReL.U; this function is represented in Pgure[by the yellow eurve.
One may easily verify that the dual activation 2 of the ReLU satisfies Pout > Pin for Pm * 1, meaning that is contraction. Consequently, for deep FNNs, which comprise multiple layers, random initialization results in collapse of all inputs with the same norm (a sphere) to a single point at the output of the FNN (equivalently, the entire dataset collapses to single straight line).
Intuitively, this collapse is an unfavorable starting point for optimization. To see why, consider the gradient V
( of the weight w/(') of some neuron in deep layer i in randomly initialized ReLU FNN. By the chain rule (backpropagation), this gradient is proportional to the output of the previous layer a (i-1) for the corresponding input, i.e., it holds that V ",!()) x (i-1)) If the collapse is present
already at layer i, this output is essentially proportional to a fixed vector a". But this implies that, in the gradient update, the weights of the deep layer will move roughly along straight line which would impede, in turn, the process of achieving linear separability.
Indeed, it is considered that for a FNN to train well, its input-output Jacobian needs to exhibit dy- namical isometry upon initialization (aaxe et all, 2014). Namely, the singular values of the Jacobian Or /r must be concentrated around 1, where Tout and rin denote the input and output of the FNN, respectively. If the dataset collapses to a line, Tout is essentially invariant to (up to change in its norm), suggesting that the singular values of ox /Orin are close zero. Therefore, randomly initialized FNNs exhibit the opposite behavior from dynamical isometry and hence do not train well.
"The results in (Cho and Saul. 2009) and DDniely al. 2010) were derived assuming unit-norm vectors ||maa]| ||mlll = 1. The result here follows by the homogeneity of the ReI.U activation function: R(az)
R(x) for 0, and ergadicity, assuming multiple filters are applied.
2

---

Published as a conference paper at ICLR 2022
Upper bound
Upper bound
ReLU dual
Output similartty
Gaussian images
Output similartyy
F-MNIST
0.8
Lower bound
0.8
Linear
bound
0.4
[h]
0.2
0.2
0
-0.8-0... 0.6.-00---0
0.2 Input similarity
-0.8 -.6--044--0.
0.2 0.4 0.6 Input similarity
(a) Gaussian images, filter size 3 x
(b) F-MNIST. filter size 3 x 3
Upper bound
Upper bound
activation
ReLU activation
Output similarity
CIFAR-10
Output similarity
ImageNet
0.8
Linear
0.8
Linear fit
Lower bound
Lower bound
0.6
0.6
0.4
0.4
0.2
0
-1 -.6 1.8-0.6-0.4-0.2 -..4-022
0.2 0.4 0.6 0.8 similarity
-1 -0.8 -0.6 2..6-0.4-0.2
0.2 0.4 0.6 0.8 Input similarity
(c) CIFAR-10, 10, filter size x 3
(d) ImageNet, filter size 11 x 11 x 3
Figure 1: Input and output cosine similarities of single randomly initialized convolutional layer with 100 filters. Fach red circle in the figures represents random pair of images chosen from the corresponding dataset. 200 pairs were sampled in each figure.
1.1
OUR CONTRIBUTION
Our main interest lies in the following question.
Does the contraction observed in randomly initialized ReLU FNNs carry over to convolutional neu- ral networks (CNNs)?
As we will show, qualitatively, the answer is yes. However, quantitatively, the answer more subtle is illustrated in figure In this figure, the similarity between pairs of inputs sampled random from standard natural image datasets-Faahion MNIST (F-MNIST), CIFAR-10, and ImageNet- displayed against the corresponding output of randomly initialized CNN layer. For these datasets, clearly Pout ~ Pmn meaning that the relation of ReLU FNNs yellow surve-beekk down.
2 represented in figure [ by the
That said, for inputs consisting of i.i.d. zero-mean Gaussians (and filters comprising i.i.d. zero-mean Gaussian weights as before) with a Pearson correlation coefficient p between corresponding entries (and independent otherwise), the relation in (2) between Pout and Pin of ReLU FNNs does hold for ReLU CNNs as well, as illustrated in figure
This dataset-dependent behavior, observed in figure 1 suggests that, in contrast to randomly- initialized FNNs which behave according to (2) randomly-initializee CNNs exhibit a richer be- havior: Pout does not depend only Pin but the inputs Zin and ynn themselves. Therefore, in this work, we characterize the behavior Pout after applying one layer in randomly initialized CNNs.
We start by considering randomly initialized CNNs with general activation functions. We show in theorem [ that the expected (over the filters) inner product E [[(out. Yout)] and the mean similar- ity Pout depend Daniely et all (2016). In theorem 2 we further prove that, by taking multiple independent filters, (Xout, Yout) and Pout of concentrate around E [(oout Yout) and Pout, respectively.
Fia and Vnn (and not just (#m. Vin)) by extending the dual-activation notion of

---

Published as a conference paper at ICLR 2022
We then specialize these results to linear CNNs (with identity activation) and derive a convolution- based variant of the Pout 2 Pin for linear CNNs, both in expectation (Pont Pin for the latter) and with high probability.
lemma that shows that (Xout, Your) se (Tin: Min) and
For randomly initialized ReLUU CNNs, we derive the following tight upper and lower bounds for Pout in terms of Pin in theorem 3
1 + Pin
max (pin 0} S Pout
2
These bounds imply, in turn, that for Pmn o 1 each ReLU CNN layer is contracting, In theorem 4 we prove that Pout for random Gaussian data satisfies the relation in accordance with figure Ia
To explain the (almost) isometric behavior of CNNs for natural images (figure[I. we note that many natural images consist of large, relative to the filter size, approximately monochromatic patches. This observation leads to simple model of black and white (binary) images with "large patches". To describe this model mathematically, we define a notion of a shared boundary between two images in definition 2 and model large patches by bodies whose area is large compared to the shared boundary. We prove that Pout s Pin for this model, meaning that the lower bound in 3 is in fact tight.
1.2 RELATED WORK
In this paper, we study how various inputs are embedded by randomly initialized convolutional neural networks. Neural tangent kernel (NTK) (Jacot et all, 2018) is related line of work. This setting studies the infinite width limit (among other assumptions) in which one can consider neural network training regression over a fixed kernel; this kernel is the NTK. There are two factors that affect the calculation of the NTK: The embedding of the input space at initialization and the gradients at initialization. In this paper we study the first one.
Arora et all (019), and Bietti and Mairal 2019) give expressions for the NTK and the convolu- tional NTK (CNTK). Theorem D may be implicitly deduced from those expressions. Arora et al. (2019) provide concentration bounds for the NTK of fully connected networks with finite width. Bietti and Mairal (019)) derive smoothness properties for NTKs, e.g., upper bounds the defor- mation induced by the NTK in terms of the initial Euclidean distance between the inputs. A related approach to NTK is taken in (Bietti. 2021) where convolutional kernel networks (CKN) are used.
Standard initialization techniques use the Glorot initializtion (Glorot and Bengio, 2010) and He ini- tialization HHe et al. 2015). Both were introduced to prevent the gradients from exploding/vamishinn mean acti-
On a similar note, Hanin and Rolnick (2018) discuss how to prevent exploding/vanto vation length-which corresponds to the gradients to some degree-in FNN with and without skip connections. For comprehensive review on other techniques see (Narkhede et all 2202 -06-28).
Schoenholz et all 7): Poole al (2016); Yang and Schoenhold (2017) study the initialization of FNNs using mean-field theory, in a setting where the width of the network is infinite. They demonstrate that for some activation functions there exists an initialization variance such that the network does not suffer from vanishing/exploding gradients. In this case, the network is said to be initialized at the edge of chaos.
As mentioned earlier, Saxe et all (014)) introduced a stronger requirement than that of moderate gradients initialization, in the form of dynamical isometry. for linear FNNs, they showed that orthogonal initialization achieves dynamical isometry whereas Gaussian i.i.d. initialization does not.
For non-linear FNNs, Pennington et all (017)) show that the hyperbolic tangent (tanh) activation can achieve dynamical isometry while ReLU FNNs with Gaussian i.i.d. initialization or orthogonal initialization cannot. In contrast, Burkholz and Dubatovka (019) show that ReLU FNNs achieve dynamical isometry by moving away from i.idd. initialization. And lastly, Tarnowski et all (2019) show that residual networks achieve dynamical isometry over a broad spectrum of activations (in- cluding ReLU) and initializations.
Xiao et al. (018 trained tanh (and not ReLU) CNNs with 10000 layers that achieve dynamical isometry using the delta-orthogone initialization. Similarly, Zhang al. (2019) trained residual CNNs with 10000 layers without batch normalization using fixup iuup-inttillzzation that prevents explod- ing/vanishing gradients.
4

---

Published as a conference paper at ICLR 2022
2
SETTING AND DEFINITIONS
The output & E TR of a single filter of CNN is given by
== o x))
where 2 E Ruxxxx is the imput; F E RR"xxxd is the filter (or kernel) of this layer; and a R + IR the activation function this layer and is understood to apply entrywise when applied to tensors. The dimensions satisfy n, ... N,r S The first two dimensions of and are the image dimensions (width and height), while the third dimension commonly equal to either for grayscale images and 3 for RGB color images, is the dimension of the filter; denotes the cyclic convolution operation:
number of channels, and is most
(F x)
Σ iEZr.jEZ,KKEZz
Fijk Fu-i
where the subtraction operation the arguments is the subtraction operation modulo n. In this work, will concentrate on the ReLU activation function which is given by (z) max x).
Typically, single layer of a CNN consists multiple filters Fi,...,Fy FN.
The following definition is an adaptation of the dual activation of Daniely at (0016) CNNs.
Definition (Dual activation). The dual activation function Ō 1R x R x R function a is defined as
IR of an activation
(x, y. E (o(x)) o(vV)]
for input vectors x, R", and parameter O, where
N (()
|| (o.y)
(S)
(x. v)
Il
For tensors v, y paxxxd, the dual activation is defined in norms replaced by the standard inner product between tensors:
(5) with the inner products and
(x. v)
Σ
Tisk Yijks
|||||| = / (a, x).
iE :J EZ KEZ.
In the special of activation that is homogeneous, i.e., satisfying (cx) car for 2 we use an additional notation for -1 S p S 1, with some abuse of notation:
3 = E((x) a(p) = (x() o(Y)
{ N ()>x(())
x
( !) (6)
This is the dual activation function of Daniely et al. 2016). Note that, by this definition, @(1) = 1.
We will be mostly interested in the ReLU activation, denoted by R, for which the following holds (see, e.g., (Daniely et all 2016 Table 1 and Section C of supplement)
/ = 1/2, R(p) = E ((() R(Y))
VI p2 + (TT cos 1oos-10 -e))
VR
MAIN RESULTS
In this section, we present the main results of this work. The proofs of all the results in this section may be found in the appendix.
5

---

Published as a conference paper at ICLR 2022
Theorem 1. Let y Raxuxd be inputs convolution filter F E R with I and activation f a such that the entries of F are i..dd. Gaussian with variance v². Then,
[F * o * +))11
Σ ā (Lal) 2)
1.jEZ..
In particular, for homogeneous activation function have [F * o y))l = =² 22. 1/2 Σ
||
| ā (pt)),
(8)
E [F = 12 v2g 1 1=11
where Pij [[0]] [b
and v has been defined in
In particular, due to (9), for homogeneous activations we can choose = 1/(ugr) and get [a =>)] = ||-|| That is, the norms are preserved in expectation for every input a.
Note that theorem I may be deduced as a special case from existing more general formulas; see, e.g.. Arora et al. (2019) Bietti and Mairal (2019). Nevertheless, it is an important starting point for us.
While theorem I holds in the mean sense, it does not hold for specific realization of a single filter F, in general. The next theorem, whose proofs relies on the notions sub-Gaussian and sub- exponential RVs and their concentration of measure, states that theorem holds approximately for a large enough number of applied filters.
We apply basic, general concentration bounds on the activation. There exist sharper bounds in special cases, e.g., in the context of cosine similarity and ReLU, see (Buchanan et all 2021 app. E).
Theorem 2. Let v, E Raxxxd be inputs to N filters Fi,..., FN E Rxxxxx with S. n such that max
max 6.EE..
||<|||| R
|| RR J
(10)
all the entries of all the filters are i.i.d. Gaussian with zero mean and variance v², and a Lipschitz continuous activation function a with Lipschitz constant L and satisfying (0) 0. Then, for 8 > however small,
P
Σ t=1
[o(F' * x), o y)) - Σ ā (Lalie, bilgg v) 2 2
(1I)
J==1
for > max (K, K2) log 2n² 8 where K RR and > O is an absolute constant. Remark 1. Clearly, [|=]]]]]] |I and || in (T)) may be bounded by || and || respectively.
However, since r is typically much smaller than n, we prefer to state the result in terms of the norms of [x and [wlis-
Theorem 2 states a concentration result in terms of the inner product. We now give a parallel result for homogeneous activations in terms of the cosine similarity Pout- To that end, consider a homoge- neous activation a and N random filters Fi,..., FN; for these filters, the quantities of ① for two inputs z and y equal
ΣN (a (Fr x) (Fe v))
Eijer,
||]]||||
HM (pp)
Pout
ΣN 1lo (Fe )² EE ||a (Fe * y)
Pout
72 ||||||
(12)
where Pig is defined in theorem Applying theorem 2 to these quantities, yields the following. Corollary 1. Let x, be inputs to N filters Fi...., FN such that
|| |0]||
max E.
R,
JE
max
M&ll
S R
all the entries of the filters are i...d. Gaussian with zero mean and variance v², and a Lipschitz homogeneous activation with Lipsehitz constant L. Then, for < 1/10 and
PP (x 4) (a, S)1 2 e) <
for N max(K, K2) log .n² where K R² and D 0 is absolute constant. <u2,2

---

Published as a conference paper at ICLR 2022
Remark 2. To make sense out of the constants in corollary 1 we point out that applying it to
inputs z, y E {=1]"xxxe (so that || = llyll = dn and ||
I || = dr") results in which does not depend on or v². There remains a log n² factor that increases with n. K Ee?
Dr.2.
In the remainder of this section, we derive an analogous result to the Johnson- Lindenssraaun lemma (Johnson and I Lindenstrauss, 1984; Dasgupta and Guptal (199)) in section 3.1 for random linear CNNs, namely, CNNs with identity activation functions. We then move to treating random CNNs with ReLU activation functions: We derive upper and lower bounds on the inner product between the outputs in section [.2] and prove that they are achievable for Gaussian inputs in section 3.3 and for large convex-body inputs in section 3.4 respectively.
3.1 LINEAR CNN
Theorem D yields variant of the Lindensrssss lemma where the random projection is replaced with random filtering, that is, by applying a (properly normalized) random filter, the inner product is preserved (equivalently, the angle).
Lemma 1. Consider the setting of theorem
7 with 1/r. Then, IE [[F xz F y)1 = (2r, v).
Lemma 2. Consider the setting of theorem 2 with v = 1/rr (and a (ar) = x.). Then,
IP M
Fe Fe y) (x, v)
<
for > max (K, K2) log
2nd 8 where K
n and D) > is an absolute constant. yd
Related result appears in Krahmer et al. (004)) (theorem 1.1) which shows norm preservation of sparse vectors for convolutional operators with filter dimension that equals the input dimension.
3.2 CNN WITH RELU ACTIVATION
The following theorem implies that every layer of neural network is contracting in expectation (over F). That is, the expected inner product between any two data points will get larger with each random CNN layer. We also develop an upper bound on the new correlation.
Theorem 3. Consider the setting of theorem 7 with ReLU activation function and variance v 2/1², for inputs x and with similarity p. Then,
1+p 2
max (x. 0) & [R(F + R), g>>
|>|||
|llll
(13)
Remark 3. All the bounds in theorem Fare tight. For simplicity, we present examples where the unit vectors 2, y are flat, i.e., they are not tensors and r 1. Similar examples can be drawn for tensor
inputs and > 1. The upper bound is realized for x, y E I22 of the form
1+e
1-
y V 1+e 1-2
Similarly, x,y R with x (VI- p. vp, 0), (0,
satisfy (r, p and E. (F(( x)) v)) 0 for r and 0 S S 1. Finally, we can take P. /p.0) and y = (0, /p. / p) to obtain (x, v) = E [a x) F y) = p.
These examples are illustrated in figure 3
Remark 4. Although the lower bound tight, in most typical scenarios it will be strict, so, in expectation, the convolutional layers will contract the dataset after application of enough layers. To see why, observe (23c); equality is achieved iff p.j = 1V [a]i, OV [w]'s O. For real data sets this will never hold over all (i.j). This can be observed in figures Ib ic and ld where the linear fit has slope of 0.97.
3.3 GAUSSIAN INPUTS
The following result shows that the behavior reported by (Daniely et all (016) [and illustrated in figure Ia by the orange curve] for FNNs holds for CNNs with Gaussian correlated inputs; this is illustrated in figure [al For simplicity. we state the result for (n x n inputs instead of x d); the extension to d > is straightforward.
7

---

Published as a conference paper at ICLR 2022
Theorem 4. Let X,Y Y E R be zero-mean jointly Gaussian with the following auto- and cross- correlation functions:
E = Yke)
= DE
Sss.6ge,
P E (X - bedzee
(14)
n2
i.e, X and Y have pairwise ii.dd entries which are correlated with a Pearson correlation coeffi- cient p. Assume further that the filter F E RRxr comprises zero-mean i.i.d. Gaussian entries with variance 2/7² and is independent of (X, Y). Then, for ReLU activation activation.uunction
BI (F, V1 p² + (T COS
c (p))
π
3.4 SIMPLE BLACK AND WHITE IMAGE MODEL
This section provides insight why we get roughly an isometry when embedding natural images via a random convolution followed by ReLU.
As conceptual model, we will work with binary pictures {0, 1) j=x or equivalently as subsets of Zn x Zn Also, when considering real-life pictures, an apparent characteristic is that they consist of relatively large monochromatic patches, so for the next theorem, one should keep in mind pictures that consist of large convex bodies.
To state our results, we define a notion of a shared r-boundary.
Definition 2 (Boundary). Let A, C Zn X 3, and let r E [n]. Then, the r-boundary of the intersection between A and B, denoted by (A, B), is defined the set of all pixels (1,j) Zn x Zn such that
3ag b1, c1, d1 (-T,...,,)) r) (i+ a1. ( E AA dd)
(15a) (15b)
Bay, b2, C2 d2 E E {-r,...,, r (i+ a2.j + b2) $ Av (2. + $
where the addition in 15a) and (5b) is over Zn.
In words, a pixel (i belongs to the r-boundary (,,A B) if, considering the square with edge size 2r 1 centered at the pixel: (1) the square intersects both A and B, (2) the square is not contained in A or not contained in B.
Example 1. Let A and B be axis-aligned rectangles of sizes a x b and e x d, respectively, and an intersection of size e x f where e, 2 2r. Then, (A, B) 4r(e f). This is illustrated in figure 2
The next theorem bounds the inner product between A and B after applying ReLU convolution layer in terms of the r-boundary of the intersection of and B.
Theorem 5. Let A, B c [m] [n] and a convolution filter F ((2++1)x(2++))) such that the entries in F are i..dd Gaussians with variance 2/(2r + 1)2. Then,
(A, B) (A, B)J E [RRFF A), D(R B)M S (4, B) + (0,A
(16a)
||-
14-BI" 2
(A, B) < E [ A) R(F BP
S ||A - B1 2 B)] (16b)
Theorem and corollary || limply
(, B) ||||] ||B||
|Paut Paul <
+c
with high probability for a large enough number of filters N. This shows that set of images con- [[][]][ is small (as in example[]oo small r), is embedded
sisting of "large patches", meaning that (A.B) almost-isometrically by random ReLU convolutional layer. Moreover, any of images may be
embedded almost-isometrically this way. To see how, fix r while increasing artificially (digitally)
the resolution of the images. The latter would yield (.(A. [[ B
- 0 as the resolution tends to infinity.
8

---

Published as a conference paper at ICLR 2022
Figure 2: Illustration of the shared r-boundary from definition 2 in of two axis-aligned rectan- gles. The boundary is marked in green.
4 DISCUSSION
4.1 GRAYSCALE VERSUS RGB IMAGES
The curious reader might wonder how the analysis over black-and-white (B/W) images can be ex- tended grayscale and RGB images. While we concentrated on B/W images this work, the definition of a shared boundary readily extends to grayscale images as does the result of theorem 5 This, in turn, explains the behavior of the grayscale-image dataset F-MNIST in figure
For RGB images, the framework developed in this work does not hold in general. To see why, consider two extremely simple RGB images: Red--consistig of all-zero green and blue channels and constant unit-norm red channel, and Green-consisting of all-zero red and blue channels and a constant unit-norm green channel. Clearly, (Red, Green) O. However, a simple computation, in the spirit this work, shows that E [R(F Red), R(F * Green)) = 1/T = R(0) which is far fully connected network and not according to the almost isometric behavior of theorem [ and figure ld
from O. That is, for such monochromatic pairs, the network behaves
So why does almost isometric relation appear in figures Ic and ld The answer is somewhat surprising and of an independent interest. It appears that for the RGB datasets CIFAR- 10 and Im- be surprising on its own),
ageNet, the RGB channels have high cosine similarity (which might Quantiaaively-averreed averaged over and additionally all the three channels have roughly the same norm. Quantitatively 10 images that were picked uniformly at random from the ImageNet dataset the angle between two channels 12.5 and the relative difference between the channel norms is 0.2%.
This phenomenon implies that our analysis for black and white images (as well as its extension to grayscale images) holds for RGB natural-images datasets. That said, there are images that are roughly monochromatic (namely, predominantly single-color images) but their measure is small and therefore these images can be treated as outliers.
4.2 FUTURE WORK
Figure [ demonstratess that a randomly initialized convolutional layer induces an ilmost-isometric yet contracting embedding of natural images (mind the linear fit with slo9e in the figure), and therefore the contraction intensifies ("worsens") with each additional layer.
In practice, the datasets preprocessed by operations such These operations induce a sharper contraction. Since a sharp collapse the deeper layers implies failure achieve dynamical isometry, natural goal for a practitioner would be prevent such a collapse. [axe et all (2014) propose to replace the i.i.d. Gaussian initialization with orthogonal initialization that is chosen uniformly over the orthogonal group for linear FNNs. However, the latter would fail to prevent the collapse phenomenon as well (see (Pennington et all, (017)). This can be shown by similar calculation to that of the dual activation of ReLU with i.i.d. Gaussian initialization. In fact, the dual activations of both initializations will coincide in the limit of large input dimensions.
removal and normalization.
That said, the collapse can be prevented by moving further away from i.i.d. initialization. For ex- ample, by drawing the weights of every filter from the Gaussian distribution under the condition that the filter's sum of weights is zero. Curiously, also including batch normalization between the layers prevents such a collapse. In both cases, the opposite phenomenon to a collapse happens, an expansion. In the deeper layers, the dataset ine-activation vectors become orthogonal to other. Understanding this expansion and why it holds for seemingly unrelated modifications is a compelling line of research.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The work of Nachum and M. Castpar in this paper was supported in part by the Swiss National Science Foundation under Grant 200364.
The work of A. Khina was supported by the ISRAEL SCIENCE FOUNDATION (grants No. 2077/20) and the WIN Consortium through the Israel Ministry of Economy and Industry.
REFERENCES
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initializa- tion and momentum in deep learning. In Proceedings of the International Conference on Machine Learning (ICML), pages 1139-1147, PMLR, 2013.
William B Johnson and Joram Lindenstrauss. Extensions Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26(189-206):1 1984.
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of the Johnson Lindenstrauss lemma. International Computer Science Institute, Technical Report, 22(1):1-5, 1999.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS), 2009.
Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random Gaussian weights: A universal classification strategy? IEEE Transactions Signal Processing. 64(13): 3444-3457, 2016.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: the power of initialization and a dual view on expressivity. In Proceedings of the International Conference Neural Information Processing Systems (NeurIPS), pages 2261-2269, 2016.
Andrew M. Saxe, James L. Mcclelland, and Surya Ganguli. Exact solutions to the nonlinear dy- namics of learning in deep linear neural network. In In International Conference on Learning Representations, 2014.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. arXiv preprint 1rXiv:1806.07572 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: 11955, 2019.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint arXiv: 12/73, 2019.
Alberto Bietti. Approximation and learning with deep convolutional models: a kernel perspective. arXiv preprini 102. 2021.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neu- ral networks. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Ma- chine Learning Research, pages 249-256. Chia Laguna Resort, Sardinia. Italy, 13-15 May 2010. PMLR. UtLpptt:::/ppcceeeee
mlr wwwpprrsssseeeee. http///ooottio0 10a 10a.html
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpass- ing human-level performance on imagenet classification. CoRR, abs/1502.01852, 2015. URL
http:://arxie www./orggg/b.ooo..ee.o www.///1//. 01852
Boris Hanin and David Rolnick. How to start training: The effect of initialization and architecture. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biance and R. Garnett, editors, Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Meenal V Narkhede, Prashant P Bartakke, and Mukul S Sutaone. A review on weight initialization strategies for neural networks, Artificial intelligence review, 2021-06-28. ISSN 0269-2821.
10

---

Published as a conference paper at ICLR 2022
Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep informa- tion propagation. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL
hittps://openrr eww. ew. net/ http//orrmmmmmmmm W1 g
Ben Poole. Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 1993360--3368 2016.
Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. In I. Guyon, U. Luxburg. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Jeffrey Pennington, Samuel S Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: Theory and practice. In Proceedings of the 31st Interna- tional Conference on Neural Information Processing Systems, pages 4788-4798, 2017.
Rebekka Burkholz and Alina Dubatovka. Initialization of relus for dynamical isometry. Advances in Neural Information Processing Systems,
2019.
Wojciech Tarnowski, Piotr Warchot, Stanistaw Jastrzębski, Jacek Tabor, and Maciej Nowak. Dy- namical isometry is achieved in residual networks universal way for any activation function. In The 22nd International Conference Artificial Intelligence and Statistics, pages 2221-2230. PMLR, 2019.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and mean field theory of cnns: How to train 10,000-layer vanilla convo- lutional neural networks. In International Conference on Machine Learning, pages PMLR, 2018
Hongyi Zhang, Yann N. Dauphin, and Tengyu Ma. Fixup initialization: Residual learn- ing without normalization. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
https: https://openreview net htt.:eeeeeeeoooo.ddledll.e.ooee Forum?20--HHosz20ck
Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem. In International Conference on Learning Representations (ICLR), 2021.
Felix Krahmer, Shahar Mendelson, and Holger Rauhut. Suprema of chaos processes and the re- stricted isometry property. Communications on Pure and Applied Mathematics, 67(11):11777- 1904, 2014.
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.

---

Published as a conference paper at ICLR 2022
A NOTATION
R. N, Z
The sets of real, natural, and integer numbers, respectively.
V,A
The logical 'or' and 'and' operators, respectively.
Zn. [n]
The sets {0, .,....,. 1} and {0, 1, 1}.
Agj. Tise
The (i,j) entry of the matrix A and the ( R)) entry of the tensor T, respectively. The sub-tensor of T formed from rows i + r and columns j to j + (and full third "layer" dimension).
[TT
I
The identity matrix of dimensions k k.
vec(.)
The vectorization operation of matrix tensor in systemic order. The standard inner product between vectors x and y. For matrix or tensor x and y (of the same dimensions) the inner product is defined as (x, v) = (vec(z), vec(y)).
(x, y)
|
The standard Euclidean norm, induced by the standard inner product: ||>|| = v (x), x).
The (cosine) similarity. The similarity between x and is defined as || ||ll
(x.
p
The mean similarity. between random X and Y is defined
E(XXY))
[
0.6
An activation function and its dual, respectively, as defined in definition I
R(x)
The ReLU applied to a: R(xx) == max {0, a:; for a tensor x the applied entrywise.
'(o))e
R(p)
The dual activation of the ReLU at [-1, 1]: R(p)
N( C)
A Gaussian vector with mean vector fr and covariance matrix C.
B PROOF OF THEOREM
To prove theorem we first prove the following simple result. Lemma 3. Let E R be two (deterministic) vectors, and let G, H E RR be zero-mean jointly Gaussian vectors with the following auto- and cross-correlation matrices:
E GG = H = v² Ik,
E GGH pu2Ix.
Then,
(u, G) (v, (1,11)
xF'G oF
Z
is a zero-mean Gaussian vector with a covariance matrix
1²2 ||u|1 E [zzz"] (plu,o)
p(u, v)) ||||
Proof of lemma 3 Furthermore,
Z is Gaussian vector as linear combination of two jointly Gaussian vectors.
E | = (uIG) =
E = O, (TE(H]]
GG o GHTTH
2 E [GG u Th
GHT H
[22" = E
(J (H
T HGT u TE
||ul
p(u,e)
p(u,)) v)
||a||
We are now ready to prove theorem
Proof of theorem]
7 The equation is proved as follows.
E [[o o( w))l Σ E(((((,())))) ([)))
(17a)
ijez
Σ
(I0lly (vli,
(17b)
iJez
12

---

Published as a conference paper at ICLR 2022
where T7a) follows from the definition of the cyclic convolution 4 and the linearity of expectation,
and (1bb) follows from definition I using lemma with F' taking the role of G and (with p = 1),
and b and [yl, taking the roles of and v, respectively.
Now, we set out to prove g
under the assumption that a is homogeneous and the following notation.
X Y/
||
<ooky w
))
N
(
([eliy. (ulg
||
(1
)
Yij
N
1
Pij
E [F x), (F w)>l E
ã (LzliS, w)
iježn
Σ [()(
(VVi)))
(18a)
||
M E (X [|] - (Xiy [X.)
(1X
i,jEZn
v²
Σ
||=||,||
E (x,) oYYr)
(18c)
v² v
Σ
||||||| |لااا| (p:s),
(18d)
where (8a) follows from defimition [ (18b) follows from the homogeneity of a, (18c follows from
standard random variable calculus, and [&d follows from 5
Finally, to obtain
9 we apply for x = y and use that Pıj = 1 and ((1) = 1:
E [F +) = 22
|| (p(())
E,j
2² v
Σ
||
(0(1)
i.j
2 v Σ
|| 112 = v² -12. - 1/11112
i.jEz
C PROOF OF THEOREM 2
To prove the concentration of measure results of this work, will make of the following definition.
Definition 3. The Orlicz norm a random variable (RV) X with respect (w.rt.) convex function 3): 00, x)) + [0, oo) such that (0) = O and lim (xx) = oc is defined by
X
X == inf
E
In particular, X is said be sub-Gaussian if || co, and sub-exponential ||X 1l oc. where v (x) = exp {x²} for p 1.
The following two results, whose proofs are available in Veessyynnn 2018 Ch. 2 and 5.2), will be useful for the proof of theorem
Lemma 4. Let X and Y be mub-Gaussian random variables (not necessarily independent). Then,
1. Sum of independent sub-Gaussians. If and Y are also independent, then their sum, X + Y, is nab-Gaussian. Moreover, ||X + yI, I C (IIX + +|x11 for an abso- lute constant C. The same holds (with the same constant C') also for sums of multiple independent
RVs.
13

---

Published as a conference paper at ICLR 2022
2. Centering. X-E(X] is Rub-Gaussian. Moreover, |X E E[X]l C 11 absolute constant C.
C|
for
3. Lipschitz functions of Gaussians. If is centered Gaussian and f is a function with Lipschitz constant L., then (X] [E S SC [| for absolute constant C.
4. Product of sub-Gaussians. XY sub-exponential. Moreover, || S l|
Theorem 6 (Bernstein's inequality for sub-exponentials), Let X1,...,X; XN be independent zero- mean sub-exponnntial RVs. Then
I 2cxp min {
6 1 J..NN.
IP
X X
21
44 2 0,
N
K2 K2'
where max;
|| and c > 0 an absolute constant.
We now ready prove the desired concentrationn-o--eeanur result.
Proof of theorem 2 (Fe, [xr]k] and (Fe, [vli)) are (jointly) Gaussian RVs-as as linear combinations of i..dd Gaussian RVs- mean zero and variances u² ||<]]]]]]]]]]]|] || and u² || respectively, for all E [N] and i E Z, Hence, (Fe, [m)g)) and (Fe, [ulig) are also aub-Gaussian with
(=))) CouR,
(Fe,, M S CouR,
[NE,N,
Vi,J An
for some universal constant Co 0. Define now
Xiee = (1ee, (z]l)) Ysee a ((Fe (I)))
vé [N],
Vi,j I...
Since a is Lipschitz continuous with a Lipschitz constant L, and since the inner products (Fi, [x][])
and (Fe, w)ls)) are centered Gaussians, by property lemma follows that Xije and Yige are Lub-Gaussian with
Kaee E [Xye]l,,, I CoLVR, ||ae E (Y CoLVR, VE E [N], Vi,j (19)
Due to the assumption (0) = 0 and the fact that a has Lipschitz constant L, inequality la(x) < L/ae| holds for every x E I. Accordingly,
bound the expectation of E [Xijt] with
E [x
< E X < LE (R, [M)]]]] < T. Var [(Fe, [+] & LuR,
(20)
where we applied the Cauchy-Schwarzz inequality. Similarly, it holds that
E [Yge]] S LvR.
(21)
Since by homogeneity of norm it also holds for any constant D E IR that |Dll I ColD), by triangle inequality it then follows from 19
20
and (1 that
Xagll S [Xiee - E [X,eell
+ E [xyelll < 2CoLvR,
[Ygell, < LCoLuR.
Therefore, subsequent application of properties 4 and 2 of lemma 4o to X Viye yields
| Yyyeeeel < <4C
(22)
X E [ S S4C/CUT..R.
14

---

Published as a conference paper at ICLR 2022
for all é E [M] and all i.j E En, where C' > 0 is is the absolute constant from lemma 4 follows
Now it
N (o(F
Σ
ā (L>liy [olij. v) 2c
N
1==1
P
XiieYase - [X
(23a)
N
[E[M]itEEZ
P
Σ
YejeY [Xjee Vijel {
AV
(23b)
PEIN]
P
max i.jEZn
Σ
- [[eeeeYajt)
(23c)
BE(NI
Σ P
n
Σ
X B [Xieetls }
2c
(23d)
N
iJEZ
RE(N]
1662
4e
< 2n
exp
-min
cN
(23e)
CA CiCUUTTRRn
where (23a follows from theorem [ and 19
23b
follows from the triangle inequality, 23d
follows from the union bound, and (3e) follows from 22 and theorem
Finally, noting that 11 holds for N > max proof.
concludes the log o
2n
16ce
1ce
D PROOF OF COROLLARY 1
Let us start by inspecting 122 to observe that, by homogeneity of neither the value of Pout nor the distribution Pout depend on or the norms of x and y. Therefore, let us assume without loss of generality that and are unit vectors, as well as that ver Furthermore, note that homogeneity of implies a (0) so theorem
2 can be applied with activation function σ.
Let A Ex (FF o xy)) B := Σn [ C == NN E (lo y)1 and A' = 1/2 E. || I[vl, (p(p)) Comparing against 12 12), we see that Pout = /BC
A
and that Pout = A'
now apply theorem three times, for pairs of vectors (x, (x, Φ) and (y v). respectively, with parameters of c/5 and 6/3. Using equations 7 99 from theorem [ check that indeed each of
Gn² the three following relations holds for > max K2) log 3 except with probability 8/3:
AA A' A
B 1-15
CC 1-115
(24)
By union bound, all three inequalities by elementary inequalities establish that if (24) holds for some A, A', B, C' R such that [A] < and < & 1/10, then it also holds that
hold simultaneously except with probability 5. Finally,
A
Pout
Pout
/BC
A' sc.
Since this occurs except with probability 8, the proof is concluded.
15

---

Published as a conference paper at ICLR 2022
E PROOF OF LEMMATA I AND 2
Proof of lemma Z Lemma[mmy be viewed as special case of theorem[[ithh an identity activation
function σ. Therefore,
E F
Σ a ([<li (ulgg
Σ
v [[<ly (1y
(x, v>,
i
where (a) follows from [ (b) follows from definition and (c) holds since 2² 1/r².
Proof of lemma 2
Again, lemma 2 follows from theorem 2 for (xr) (and hence L and
from lemma 1
F PROOF OF THEOREM 3
We start with the lower bound. Define Pij := ([e) Ivl
for all i,j E Zn Then, for all i,j E Zn.
[=]; My
= || || || Pe
(25a)
11- Přg + (TT
cos (a--cos-(pp)) (pis))pss
s ||>|||||||
||b]]]]
(25b)
= [a
((F (I11)) ((F
(25c)
where 25a
holds by the definition of Pij.
(55 holds since
a² ( cos (a)) a
a x
V/al S 1,
and 25ch follows from Daniely et al. 2016 Table and Section of supplement). Thus,
(x, v) = 1/r2
Σ (ely,blb <
E ((F) ((F, (F.()))) E (F r)o(F y)],
KJEZ
KJEZ
(26)
where the inequality follows from 25 and the last step is due to
17). Now, since the ReLU activa- tion is non-negative, E [o (F F y)], which completes the proof of the left inequality in
1
For the upper bound, we the following convexity argument. First, by homogeneity of ReLU, can assume without loss of generality that and have unit norm. Therefore, it remains to show E (F * () * y)] < 1+p for x. such that | = |lyll = 1 and (I. y) p.
Recall that Pij = ([]), ME) Me], M
We expand the definitions the same way as 26 and 25c
E. [a FF + n)) = Σ
[
((P, (P)))
i.jzZ
MIM lI R(pg).
Σ
(27)
is easily checked that R(1) 1, (--RR(( -1) 0 and that R(x) is convex for -1 S 1. Accordingly,
using the decomposition p= 1+ 1 1_p (-1), we have by Jensen's 'ss inequality for every i, z,
1 1
R ((:s) <
2
16

---

Published as a conference paper at ICLR 2022
y
y
I
y
vI
0
VI
0
1+2
1
vp
Vp
vP
vp
1-
1-
VI P
vI -
Pout 2
Pout
Pout P
Figure 3: An illustration of the examples from remark 3 structed in higher dimensions, e.g., by equally distributing the coefficients over a larger set of coor- dinates.
Note that similar examples can be con-
Substituting into
27
|
1 1+ Pij
E [ & x)) * b))
72
2
i
2r
2r
f.jE2n
i,jE2n
<
1
Σ
Σ
||
(2, v)
(28)
2r
LJEE
1 ++/
where in 28 we applied the Schwarz inequality and used the initial assumption ||>||| |yy|
G PROOF OF THEOREM 4
The proof follows from the following steps.
E E[o(F * X), -) =E E Σ ((F F
(29a)
[n'E [0r (Xp) (Yr)l]
(29b)
p² + ( cos (p)) P [|11
(29c)
π
v p² (T cos (p))
(29d)
π
where (9a) follows from the law of total expectation; 29hb follows from 14). from the indepen- dence F in (X, Y), and from lemma 3 with F taking the roles of and v, and [X] and [Y]; taking the roles of G and H. resulting in X and Yp which are zero-mean jointly Gaussian with vari- ances ?|] /n2 and Pearson correlation coefficient o; (29c) follows from the homogeneity of the ReLU activation function and from (Cho and Saul. 22009, eq. (6)). (Giryes et all 2016, Theorem 4), (Daniely all 2016 Section 8); (9d) holds by the definition of F.
17

---

Published as a conference paper at ICLR 2022
H PROOF OF THEOREM 5
In this section, we will use the following additional notations. [A]] will denote the submatrix of A formed from rows - i + and columns j - r to r, and 1xck will denote a & matrix with all entries equal 1.
The main effort in the proof is establishing T6a).
We apply theorem so have E (o A), (F * B)M = En [[A4]], BBy (2r - 1)). And specifically, for the ReLU acti- vation, it holds that
6 ([A]]), 2/(2r 1)) [[ || R(P()
(30)
(2r + 112
where Pij = [IAI,,BB1 [ [B
A natural way to show that the convolutional layer induces isometry in expectation would be to show a[A]] [B]; (2r + 1)) = Aij Bij
for all pairs (i, Unfortunately, this does not hold for all pairs. However, we will show that the only pairs for which it does not hold belong to the r-boundary (, B). There are two cases to consider Aij- Bij = O and A.; Bij = 1 since A and B are binary.
Let ōig = = (LA :: ), (2r + 1)). Let Eg = {(i,j) E Zn Ag By = O # 0} and
E1 {(1,j) E Z, Aij- Bij- = 1 A o5 + 1}. Since clearly 0 S ãig S 1 and (A, B) = (((i.)
A. B. 1}/, we have
()
Fa < Ep (a * o). B)] < (4, B Foo
In particular, if we show Eo, Ei C (A, B). then 16al will be established. This is what we show the rest of the proof.
For readability, we repeat here the two conditions for pair (i. j) to be included in the boundary, see definition Namely, (i,j) belongs to (A, B) if and only if both conditions below hold:
1. b1,,61,,1, c1, d1 E {-r,......) r (i+ a1 b1)
E AA (i + c1. d1) E B.
2. Baz, b2, C2, d2 E {-r,.... r. (i j
+ b2) & A V (i (i+ + 22 + d2) $ B.
Let (i,j) be such that Aij B3 = 0. By equation 30 /. = 0 if and only if [A]]] = 0 or [B] 0.
So, when Aij B.j = 0, for o. + 0 to hold it is necessary that there are 41, b1 c1, d1 E (-r....,? such that Aj-a
and Aster.td: The second item holds with = b2 C2 d2 0 since Aig Bij 0 so either A,j 0 or
which corresponds to the first item in definition
Bij = O. This shows that pairs of indices for which A.j Bij = and oij + are contained in
(A, in other words that Eo S (,,A, B).
Now take (i,5) such that Aij . Big = 1. By equation 30 ãG = 1 if and only if [A] =
1 ((2++1)x(2++1) and [B] ((2+)1)((2++))- So, when Ao Big 1 and ō, + 1, then there are a2 by, 022 d2 {-r.....77 r such that Altoz./+bz = 0 or B Bi+c,.+dz = 0 which corresponds to the second item in definition The first item holds with o₁ b C d1 = 0 since A.j Bij 1 so both A;j = and B:y 1. This shows that pairs of indices for which A.j B,j = and ō # 1 contained in (A, B), or equivalently that E, C (A,
This concludes the proof of (16a). As for (6b), follows easily by substituting in the formula ||A 2 |||||2 + | 2(A, B). We then the fact E [R A) = ||, which follows from 99, recalling that 22 2/(2r + 1)2 and vî 1/2.
18


Reviews:
[{"review_id": "OER9h99TBte", "reviewer": "Reviewer_DLps", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 is well-written. The introduction and related work section give plenty of background information and a notation table is also included to help the reader to access the technique details. I check the technical details and no major flaw is found.\n\n\nWeaknesses:\n\nThe technical strengths may not be strong enough. For the linear CNNs with random Gaussian weights, the underlying procedure is a sum of product between the inputs and random Gaussian random variables. It is expected that the JL lemma-type results will still be held. For the CNNs+ ReLU, since part of the information can be truncted by ReLU, the contraction behavior is also straightforward. If the authors think the proof contains nontrivial contributions, they should be highlighted. ", "summary_of_the_paper": "This paper studies the random initialized CNNs and analyzes the geometry preservation. For linear CNNs, the authors show the JL lemma type results hold. For  CNN+ ReLU, the output contracts and the level of contraction depend on the inputs. In numerical experiments, the authors verify the geometry of natural images is preserved, while for random gaussian correlated inputs, the contraction behavior appears. ", "summary_of_the_review": "My major concern is the technical significance. At the current stage, I think this paper may not be strong enough for ICLR.\n\n**** After seeing the author's comments. I agree the JL-type results for CNNs are different from those in the literature. I change my score accordingly.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "11RKNmqvyz5", "reviewer": "Reviewer_g6qL", "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": "The paper is not a typical paper that we read today. The formulation is simple, and the paper is easy to read (in the main part, which does not contain proofs, only formulation).\n Some results are easy to prove (such as Lemma 3 and Theorem 1). Some results have doubtful meaning, such as concentration of measure result (see 22e) for example, which contains very unrealistic constants.\nHowever, the theorems seem to be correct. Also, the authors test their results on different datasets and get intriguing results that show that the lower bound seems to be better suited for random convolutional filter, applied to CIFAR-10 or ImageNet datasets.\n\nA possible addition would be to study how the isometry property \"suffers\" during the training, but since the authors limit themselves to the analysis of the initialization, that is not formally connected to the results. \n\nQuestions:\n\n- After the first CNN filter, the distribution might change. What is the effect of deeper layers on the isometry property?\n- Can such kind of studies provide practical recommendations for initialization?\n", "summary_of_the_paper": "The paper shows (as clearly described in the introduction) two things: random filters have the distance preservation property. For random convolution + ReLU activation it is contracted (which is also expected, since ReLU throws away half of the entries).\nHowever, for images the authors try to explain why CNN+ReLU is isometric by considering images as objects with large monochromatic images. \n\nThe main motivation for such research in practice is initialization. A deep fully-connected network with ReLU may lead to collapse, whereas for CNNs it does not. The paper argues that the randomized theory presented here is a justification for such fact for images.", "summary_of_the_review": "Good, self-consistent and easy to ready paper. Some proofs are not needed.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "08hIvSHhOQo", "reviewer": "Reviewer_Mtqu", "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": "\n### Strengths\n\n- The paper is well-written and enjoyable to read. There is a good mix of\n  theory and intuition. The mathematics is written clearly and precisely.\n- The basic observation around angle contraction in random convolution layers,\n  while possibly implicit in some previous works (see request for clarification\n  below), does not seem to have been presented systematically as the authors do\n  so here, and is quite an interesting difference relative to the feedforward\n  case. The way the authors study this issue, using tight lower and upper\n  bounds for the new map with the ReLU activation, as well as examples with\n  gaussian data, empirical data (Figure 1) and cartoon data (section 3.4), is\n  sufficiently systematic to give a good entry point to understand various\n  interesting aspects of this difference. I anticipate this will be useful for\n  follow-up work.\n- The issue is placed well in context via discussion of many related works\n  about dynamical isometry and more generally accelerating training of\n  deep networks.\n\n\n### Weaknesses\n- There is a large body of work on CNTKs that has appeared following the\n  initial interest in the NTK, and I think it would be helpful if the authors\n  spent some time in the related work section comparing to any relevant work in\n  this line -- it seems to me, although I could be mistaken, that some of the\n  formulas and concentration results the authors give in the paper may have\n  been derived previously in these contexts due to the natural interest in such\n  expressions for writing down CNTKs, and it is important to know of such\n  overlaps to assess the authors' work's novelty. For example, [1-4] below.\n- The concentration results are rather primitive: notably Theorem 2\n  requires a stack of i.i.d.\\ feature maps to be channel-averaged to obtain\n  concentration, whereas one would expect it is possible to have a certain\n  degree of concentration as long as the input size $n$ is sufficiently large\n  relative to the kernel size $r$. This weakness is due to the authors using\n  worst-case analysis of the convolutional structure in Theorem 2's proof -- a\n  union bound is taken to control the concentration of the individual\n  translates of the filter rather than something more sophisticated like\n  chaining/decoupling tools, which are standard in the sharp analysis of\n  RIP-type properties of convolutional operators (e.g. [5-6]). In this\n  connection, the content of Section 3.1 seems superfluous. There also exist in\n  the signal propagation literature significantly sharper analyses of the\n  concentration behavior of the ReLU's dual activation that are relevant in the\n  context of results like Corollary 1 applied to the ReLU [7, Lemma E.3]. All\n  this said, I do not believe this necessarily diminishes the authors' results,\n  as long as the previous point about comparisons to the literature is\n  satisfied -- if this work is deriving these kinds of results for the first\n  time in the literature, they of course do not need to be optimal -- but it is\n  necessary to acknowledge these limitations to accurately place the results in\n  context and make follow-up directions clear.\n- Proof of theorem 2: the argument around the Lipschitz property is not\n  correct: it is not true in general that a Lipschitz function of a\n  sub-gaussian random variable is sub-gaussian (consider a Rademacher random\n  vector). The argument should use the gaussian distribution of the random\n  variables (and Gauss-Lipschitz concentration e.g. from Vershynin ch. 5 should\n  be cited).\n\n[1] http://arxiv.org/abs/1905.12173\n\n[2] http://arxiv.org/abs/1904.11955 \n\n[3] http://arxiv.org/abs/2102.10032\n\n[4] http://arxiv.org/abs/1806.05393\n\n[5] http://dx.doi.org/10.1002/cpa.21504\n\n[6] http://arxiv.org/abs/1712.00716\n\n[7] https://openreview.net/forum?id=O-6Pm_d_Q-\n\n\n### Minor points:\n- I don't immediately understand the statement \"the unit vectors $x, y$ are\n  $1$-dimensional\" in Remark 2 -- is this thinking of $x$ and $y$ as being $1\n  \\times 1 \\times 2$ images? In the next sentence we have $x, y \\in \\mathbb{R}^2$\n  stated, i.e. not $1$-dimensional.\n- It would be helpful to have some visualizations of the different regimes of\n  behavior represented in the bounds of Theorem 3, as well as some more insight\n  into the examples of Remarks 2 and 3. For example, can we understand when\n  this bound is loose/tight based on the structure of the inputs across\n  patches? (The gaussian example recovers the FFNN case -- when there are\n  correlations across patches, does this lead us towards the other extremes?)\n- First paragraph on page 3: typo \"outout\" (output)\n- The last two paragraphs of the introduction (Section 1) are slightly hard to\n  appreciate to this reader because they are written in what seems to be a\n  deliberately technically imprecise way -- for example, it would be helpful to\n  specify what kinds of depth-width and initialization regimes are being\n  considered here (the discussion quickly jumps from angle propagation across\n  one layer to angle propagation throughout many layers -- to have the points\n  being made here have meaning, I believe it is necessary to be considering\n  \"edge of chaos\" initialization). I particularly do not understand the last\n  paragraph unless it is being assumed here that the depth is significantly\n  larger than the width (e.g. width fixed as depth diverges).  I think the\n  point made in the second to last paragraph is insightful and applies much\n  more generally than the \"diverging depth\" setting.\n- Corollary 1: the statement says the variance of the gaussian is $\\nu^2$, but\n  it seems from the value given for $K$ that a specific choice of $\\nu$ is\n  being used here.\n- Theorem 5: Above the $r$-boundary is defined as a set -- is the usage here\n  supposed to be the cardinality of the $r$-boundary?\n- section 4.1: \"curios\"\n", "summary_of_the_paper": "\nThe authors consider angle propagation in randomly-initialized convolutional\nneural network layers -- given two input images that have cosine angle $\\rho$,\nwhat is the cosine angle of their feature embeddings when propagated through\nthe random layer? They show that the behavior is very different from the\nstandard feedforward case that has been discussed at length following the work\nof Daniely et al. (2016): for filters of small spatial support and e.g. ReLU\nactivations, the output cosine angle can be as small as the ReLU of the input\ncosine angle, or as large as a linear function of the input cosine angle,\ndepending on the patch structure of the input image. This has implications for\nunderstanding signal propagation and issues like dynamical isometry in\nconvolutional networks. The authors give some measure concentration results, in\nthe spirit of Daniely et al.'s results for feedforward networks, that specify\nthe behavior in the convolutional case, and present examples of different types\nof images (unstructured/gaussian; cartoons; CIFAR-10 data) where different\nangle propagation behaviors are observed.\n", "summary_of_the_review": "This is an interesting paper that combines theory and empirical insights to\nhighlight differences between angle propagation in random CNNs and feedforward\nnetworks. The results should inspire interesting follow-up work in this\nsetting. I hope the authors will clarify the relationship to the theorems in\nthis work to any possible prior art in e.g. CNTK papers, as mentioned above.\nThe concentration results are basic, but probably enough as first-cuts (it\nseems important to acknowledge limitations, however).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper focuses on understanding how the angle between two inputs change as they are propagated in a randomly-initialized convolutional neural network layers. They demonstrate very different behavior in different settings and provide rigorous measure concentration results. The reviewers thought the paper is well written and easy to read with nice theoretical results. They did raise a variety of technical concerns that were mostly addressed by the authors rebuttal. My own reading of the paper is that this is a nice contribution. I therefore agree with the reviewers and recommend acceptance.
Decision: Accept (Poster)