Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers deep linear networks with batch normalization. The main contributions are:
1. Under a linear independence condition, it is proved that the orthogonality gap is the sum of a term that decreases exponentially fast with the depth, and a term that is basically number_of_samples / sqrt{width}. 
2. Under similar conditions, it is proved that the distribution of the hidden representation is close to the Gaussian distribution, and a Wasserstein distance bound is proved.
3. It is shown empirically that a larger orthogonality gap at initialization makes training slower, and that SGD decreases the orthogonality gap during training. This paper further proposes an "iterative orthogonalization" algorithm, which can enforce orthogonality and accelerate training when the depth is large.
main_review: I think the contributions of this paper are interesting. Intuitively, orthogonality would help with training, and it is nice to see that batch normalization can increase orthogonality. It is also interesting to see that SGD can increase orthogonality during training (even though there is no proof). The iterative orthogonalization algorithm may also be useful in practice.

I have the following concerns:
1. The main results require the width to be at least n^2, and if I understand it correctly, the width is also equal to the input dimension. It is also mentioned that the prior work by Daneshmand et al. (2020) requires all inputs to be linearly independent, which also seems to be required in this paper. These assumptions are strong.
2. As we can see in Figure 4 and 7, iterative orthogonalization always decreases the orthogonality gap, but it actually makes training slower for shallow (depth <= 20) networks.
3. In Figure 7(b), only the loss curves after 20 epochs are plotted, at which time the losses are still high. Can you also provide the loss curves after maybe 200 epochs?

Finally, the prior work "A deep conditioning treatment of neural networks" by Naman Agarwal, Pranjal Awasthi, and Satyen Kale may be related, where they studied the orthogonalization property of nonlinear activations.
limitations_and_societal_impact: The limitations are discussed above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This papers focuses on the analysis of batch normalization which has been attracting a lot of attention recently.  The key contribution of the paper is in the finding that batch normalization (under some rather mild and sensible assumptions) makes training samples increasingly orthogonal.
main_review: This paper is another contribution in the now rather hot area which attempts to understand better batch normalization, and NN normalization in general.  As such, it addresses a relevant and widely interesting topic.  The key findings are also rather interesting, novel, insightful, and practically important.  The bottom line demonstrated by the authors is rather simple to understand: predicated on a few mild assumptions, batch normalization makes training samples increasingly orthogonal.  This simple to understanding finding is rather insightful though and facilitates not only a better understanding of the normalization for its own sake, but also a series of practically important improvements, e.g. as the authors demonstrate, in the context of stochastic gradient descent application.  Overall, I consider the novelty and general technical quality of this paper to be well within the expected range for NIPS.  The quality of writing is also good - I have no objections to make.

Post Rebuttal:
Having considered my colleagues' reviews and the authors' response to these, I find myself no less positive about this paper and am in fact even more confident of my original positive recommendation.  Hence I see no need to alter my review or the recommendation.
limitations_and_societal_impact: All fine.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the effect of batch normalization on representations at random initialization.  They formally show that representations become increasingly orthogonal with layer depth up to a term inversely proportional to layer width. Using this, they prove that the distribution of the output contracts to a Wassertein ball around a Gaussian distribution and demonstrate empirically that orthogonal outputs save training time.  Lastly, they propose an initialization that ensures orthogonality even without batch normalization, which they empirically test.
main_review: **Originality/Significance:**
My greatest concern with this work is that it is not clear that it is a significant contribution beyond the ideas originally proposed in Daneshmand et al 2020 work "Batch Normalization Provably Avoids Rank Collapse for Randomly Initialised Deep Networks".  If we consider the contribution of this work to be in the algorithmic introduction of "iterative orthogonalization", then this work has not come close to meeting the bar for experimental benchmarking. This being said I think the ideas proposed in this paper, especially the empirical observations in section 6 (i.e. "SGD needs to orthogonalize deep representations in order to start classification") are quite interesting.  However, all the experiments provided are on very small scale networks and a much more thorough experimental section would be required to demonstrate this phenomenon holds generally.


**Clarity/Quality:**
Writing is very clear, notation is nicely introduced, and assumptions are clearly defined.  However, some experimental details are difficult to determine from both the main text and captions.



**Areas for Improvement:**

- "While the hidden representations of vanilla networks has been theoretically studied...up to the best of our knowledge, there is no theoretical analysis of BN networks".  This seems like way to strong of a claim.  For example, see Daneshmand et al 2020 work "Batch Normalization Provably Avoids Rank Collapse for Randomly Initialised Deep Networks" which you cite quite a bit or Lubana et al 2021 work "Beyond BatchNorm: Towards a General
Understanding of Normalization in Deep Learning".
- In general there seems to be quite a bit of overlap between this work and Daneshmand et al 2020.  Can you discuss the difference between your quantity of study "orthogonality gap" (equation 2 in your work) and their quantity "(stable) rank" (equation 4 in their work) and your upper bound (equation 3 in your work) and their lower bound (equation 5 in their work).
- In 4.3 Experimental validation section you are connecting your bound in equation 3 very loosely to the empirics.  Can you construct a quantitive prediction from your theory that you can validate empirically?  Of course you don't know the value of $\alpha$ but could you estimate it and then plot your bound on the same plot?  Or even plot your bound for varying levels of $\alpha$ so we can see the shape?  Making this section more quantitative would improve the empirical evidence. Also its not clear what network architecture or data sets is being used here. In general hard to determine where experimental details are.
- You write "Corollary 3 establishes the first non-asymptotic Gaussian approximation for deep random neural networks" and "the distribution of the outputs contracts to a Wassertein 2 ball around an isotropic Gaussian distribution as depth grow...the radius...is at most $\mathcal{O}(1/\sqrt{\text{width}})$".  These seem contradictory?  Only asymptotically (infinite depth/width) does the distribution of outputs according to corollary 3 become Gaussian.  Am I missing something?


**Specific Comments:**
- [line 99-100] "When weights initialized randomly, linear and non-linear networks share similar properties." => "When weights [are] initialized...share similar properties [such as...]"
- [line 105] "diag(M) zeros out off-diagonal elements" => I found this initially confusing cause in equation (1) you have $diag(MM^\intercal)$ not $diag(M)$.  Maybe just write $diag(\cdot)$ when discussing the operator?
- [line 129-130] "We used highly correlated inputs for the BN network and perfectly orthogonal inputs for the Vanilla network to contrast their differences." => I don't understand this sentence.  In the caption there is no indication of this experimental detail.  Could you elaborate here or in the caption of Fig. 1?
- [line 138] "...is different from the covariance matrix... [used in batch normalization (equation (1))]" you might want to emphasis this point?
- [equation (2)] Why write $\|I_n\|^2_F$ and not just $n$?  I would simplify this expression and put $H^\intercal H$ into numerator of first term.
- [line 161] "This stability opens the door to more theoretical analysis of this chain, such as studying mixing and hitting times" => This is still a very general statement. Can you be more specific?  What sort of questions could this stability "open the door" to answering (potentially using mixing or hitting times as an analysis tool)?
- [line 169-170] "one can readily check that the orthogonality gap of hidden representations in vanilla networks..." Could you summarize this result mathematically so we can compare to the bound in equation (3)?  
- [fig. 2] "vertically versus $d$ horizontally." => dont you mean $log(d)$ horizontally?
- [fig. 4] You write earlier "to distinguish it from purely orthogonal weight initialization, we refer to this as iterative orthogonalization", but then in your label you write "orthogonal" and not "iterative orthogonalization" or "IO" or something like this.  Additionally you dont even compare to the original "orthogonal" initialization as introduced in Saxe et al.
- [Fig. 4] The yaxis label for fig4.b is "training orth"?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the proposition that batch normalization (BN) orthogonalizes representations in deep networks. To this end, the consider a model with linear activations and random weights. The authors prove that the "orthogonality gap", i.e. how non-orthogonal the activations are, decreases with depth when BN is used. It is also shown how the activations contract to a gaussian isotropic distribution with depth. Experimental verification is provided, and the authors also propose an initialization scheme that can be used to substitute BN.
main_review: Main Comments
---------------

Overall the paper is relatively well written. BN improving the conditioning of neural networks is folklore at this point, and it is important to provide quantitative non-asymptotic proof of this. The model the authors consider -- linear neural networks with random weights and BN without mean subtraction -- is a reasonable starting point towards a more realistic analysis. The theoretical results are reasonable, verified experimentally and interesting. The main issue with the paper is Assumption 1, which seems very strong. Consider e.g. random Guassian input. The singular values would follow the semi-circle law for random matrices, and \alpha should go to 0 as the dimensionality increases. Thus, it's not clear that it should hold for generic input. What are the reasons to think it would hold for intermediate layers? This assumption is very easy to test experimentally. Could the authors provide experimental verification that Assumption 1 holds in practice?

The contributions regarding proposing a new initialization scheme that works without BN is not very interesting in my mind. There is already plenty of work in training without normalization (see, e.g., High-Performance Large-Scale Image Recognition Without Normalization and references therein). The authors should compare against related work to show that their initialization is preferred.


Minor Comments
-----------


The authors state that "The BN function in Eq. (1) differs slightly from the commonly used definition for BN as the mean correction is omitted." This is not a minor difference, but a rather significant one. This should be highlighted more.

Fig 2b should have error bars.

It might be interesting to discuss relationships with layernorm. BN is often used for CNNs and LN is often used for MLPs which the author study here.

The authors state that they focus on "Multi-Layer Perceptron (MLP) with linear activation." This just means no activation function at all right? I find the term linear activation is confusing.

"Daneshmand et al. (2020) showes this difference does not change the network properties qualitatively." Does Daneshmand show this empirically? If so, it might only hold for the architectures they study and not in general.



Post Rebuttal Comments
-----------

The authors have clarified that the main assumption holds for the non-square case for random matrices, and also verified that it holds empirically. The assumption being strong was my main object, after the clarifications from the authors I now believe that it is reasonable. Hence, I will increase my score. 


limitations_and_societal_impact: n/a
review_title: null

Meta-review: This paper provides a setting and analysis where batch normalization increasingly orthogonalizes data as it is mapped through a network.  Reviewers are uniformly supportive and I recommend acceptance.  Even so, a few of the reviews (and responses) were quite detailed, and I request the authors adjust the paper to clarify these points in their revisions.
Decision: Accept (Spotlight)