Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
The authors consider angle propagation in randomly-initialized convolutional
neural network layers -- given two input images that have cosine angle $\rho$,
what is the cosine angle of their feature embeddings when propagated through
the random layer? They show that the behavior is very different from the
standard feedforward case that has been discussed at length following the work
of Daniely et al. (2016): for filters of small spatial support and e.g. ReLU
activations, the output cosine angle can be as small as the ReLU of the input
cosine angle, or as large as a linear function of the input cosine angle,
depending on the patch structure of the input image. This has implications for
understanding signal propagation and issues like dynamical isometry in
convolutional networks. The authors give some measure concentration results, in
the spirit of Daniely et al.'s results for feedforward networks, that specify
the behavior in the convolutional case, and present examples of different types
of images (unstructured/gaussian; cartoons; CIFAR-10 data) where different
angle propagation behaviors are observed.

main_review: 
### Strengths

- The paper is well-written and enjoyable to read. There is a good mix of
  theory and intuition. The mathematics is written clearly and precisely.
- The basic observation around angle contraction in random convolution layers,
  while possibly implicit in some previous works (see request for clarification
  below), does not seem to have been presented systematically as the authors do
  so here, and is quite an interesting difference relative to the feedforward
  case. The way the authors study this issue, using tight lower and upper
  bounds for the new map with the ReLU activation, as well as examples with
  gaussian data, empirical data (Figure 1) and cartoon data (section 3.4), is
  sufficiently systematic to give a good entry point to understand various
  interesting aspects of this difference. I anticipate this will be useful for
  follow-up work.
- The issue is placed well in context via discussion of many related works
  about dynamical isometry and more generally accelerating training of
  deep networks.


### Weaknesses
- There is a large body of work on CNTKs that has appeared following the
  initial interest in the NTK, and I think it would be helpful if the authors
  spent some time in the related work section comparing to any relevant work in
  this line -- it seems to me, although I could be mistaken, that some of the
  formulas and concentration results the authors give in the paper may have
  been derived previously in these contexts due to the natural interest in such
  expressions for writing down CNTKs, and it is important to know of such
  overlaps to assess the authors' work's novelty. For example, [1-4] below.
- The concentration results are rather primitive: notably Theorem 2
  requires a stack of i.i.d.\ feature maps to be channel-averaged to obtain
  concentration, whereas one would expect it is possible to have a certain
  degree of concentration as long as the input size $n$ is sufficiently large
  relative to the kernel size $r$. This weakness is due to the authors using
  worst-case analysis of the convolutional structure in Theorem 2's proof -- a
  union bound is taken to control the concentration of the individual
  translates of the filter rather than something more sophisticated like
  chaining/decoupling tools, which are standard in the sharp analysis of
  RIP-type properties of convolutional operators (e.g. [5-6]). In this
  connection, the content of Section 3.1 seems superfluous. There also exist in
  the signal propagation literature significantly sharper analyses of the
  concentration behavior of the ReLU's dual activation that are relevant in the
  context of results like Corollary 1 applied to the ReLU [7, Lemma E.3]. All
  this said, I do not believe this necessarily diminishes the authors' results,
  as long as the previous point about comparisons to the literature is
  satisfied -- if this work is deriving these kinds of results for the first
  time in the literature, they of course do not need to be optimal -- but it is
  necessary to acknowledge these limitations to accurately place the results in
  context and make follow-up directions clear.
- Proof of theorem 2: the argument around the Lipschitz property is not
  correct: it is not true in general that a Lipschitz function of a
  sub-gaussian random variable is sub-gaussian (consider a Rademacher random
  vector). The argument should use the gaussian distribution of the random
  variables (and Gauss-Lipschitz concentration e.g. from Vershynin ch. 5 should
  be cited).

[1] http://arxiv.org/abs/1905.12173

[2] http://arxiv.org/abs/1904.11955 

[3] http://arxiv.org/abs/2102.10032

[4] http://arxiv.org/abs/1806.05393

[5] http://dx.doi.org/10.1002/cpa.21504

[6] http://arxiv.org/abs/1712.00716

[7] https://openreview.net/forum?id=O-6Pm_d_Q-


### Minor points:
- I don't immediately understand the statement "the unit vectors $x, y$ are
  $1$-dimensional" in Remark 2 -- is this thinking of $x$ and $y$ as being $1
  \times 1 \times 2$ images? In the next sentence we have $x, y \in \mathbb{R}^2$
  stated, i.e. not $1$-dimensional.
- It would be helpful to have some visualizations of the different regimes of
  behavior represented in the bounds of Theorem 3, as well as some more insight
  into the examples of Remarks 2 and 3. For example, can we understand when
  this bound is loose/tight based on the structure of the inputs across
  patches? (The gaussian example recovers the FFNN case -- when there are
  correlations across patches, does this lead us towards the other extremes?)
- First paragraph on page 3: typo "outout" (output)
- The last two paragraphs of the introduction (Section 1) are slightly hard to
  appreciate to this reader because they are written in what seems to be a
  deliberately technically imprecise way -- for example, it would be helpful to
  specify what kinds of depth-width and initialization regimes are being
  considered here (the discussion quickly jumps from angle propagation across
  one layer to angle propagation throughout many layers -- to have the points
  being made here have meaning, I believe it is necessary to be considering
  "edge of chaos" initialization). I particularly do not understand the last
  paragraph unless it is being assumed here that the depth is significantly
  larger than the width (e.g. width fixed as depth diverges).  I think the
  point made in the second to last paragraph is insightful and applies much
  more generally than the "diverging depth" setting.
- Corollary 1: the statement says the variance of the gaussian is $\nu^2$, but
  it seems from the value given for $K$ that a specific choice of $\nu$ is
  being used here.
- Theorem 5: Above the $r$-boundary is defined as a set -- is the usage here
  supposed to be the cardinality of the $r$-boundary?
- section 4.1: "curios"

summary_of_the_review: This is an interesting paper that combines theory and empirical insights to
highlight differences between angle propagation in random CNNs and feedforward
networks. The results should inspire interesting follow-up work in this
setting. I hope the authors will clarify the relationship to the theorems in
this work to any possible prior art in e.g. CNTK papers, as mentioned above.
The concentration results are basic, but probably enough as first-cuts (it
seems important to acknowledge limitations, however).
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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).
However, for images the authors try to explain why CNN+ReLU is isometric by considering images as objects with large monochromatic images. 

The 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.
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).
 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.
However, 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.

A 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. 

Questions:

- After the first CNN filter, the distribution might change. What is the effect of deeper layers on the isometry property?
- Can such kind of studies provide practical recommendations for initialization?

summary_of_the_review: Good, self-consistent and easy to ready paper. Some proofs are not needed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
main_review: Strengths:

The 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.


Weaknesses:

The 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_review: My major concern is the technical significance. At the current stage, I think this paper may not be strong enough for ICLR.

**** 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.
review_title: null

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)