Batch normalization is sufficient for universal function approximation in CNNs

We thank the reviewer for the constructive feedback. In the following, we address their questions and concerns.

• Indeed, we have used layer normalization when we meant normalization layers. We have revised the manuscript accordingly.

• Universal Approximation Theorems often have mild assumptions on the activation functions (e.g. that they are monotonously increasing and continuous) and the smoothness of the data generating function (usually that it is continuous) [1]. Depending on the considered architecture (e.g. a three layer neural network or a width-constrained perceptron with ReLUs, the approximation quality of the neural network is derived dependent on the number variable network parameters (e.g. the width of the 3-layer neural network or the depth of the width constrained perceptron) [2].

  • By formulating theorems with respect to a given target network that solves a task of interest, we are flexible in which universal function approximation theorem could be invoked. Our results would inherit the specific assumptions.
  • Also irrespective of the specific universal function approximation theorem, we can cover typical application cases, for which target networks have been obtained by training the networks in a classical way. We have clarified this argument on page 3.

• Our title refers to batch normalization, as it is one of the first and thus most well known normalization techniques. For that reason, several theoretical investigations have focused on understanding its contribution to successful deep learning. Our title embeds our work in this rich line of research but we would be happy to change the it upon request to highlight the more general scope of our insights.

• The analysis can be extended to IEBN and SwitchNorm. We thank the reviewer for pointing us these relevant references, which we have included as examples in our background section.

[1] Gühring, Raslan, Kutyniok (2022). Expressivity of Deep Neural Networks. In P. Grohs & G. Kutyniok (Eds.), Mathematical Aspects of Deep Learning (pp. 149-199). Cambridge: Cambridge University Press. doi:10.1017/9781009025096.004

[2] Shen, Yang, Zhang (2022). Optimal approximation rate of ReLU networks in terms of width and depth, Journal de Mathématiques Pures et Appliquées, Volume 157, Pages 101-135, ISSN 0021-7824.

Thank you for your detailed response. Upon reflecting on your response, I still find myself puzzled about whether normalization can be analyzed solely through $\gamma \mathbf{h} + \beta$. While I understand that more intricate normalization sub-operations, such as "minus the mean, etc.", are challenging to analyze, I feel the need for a more reasonable explanation. Furthermore, I appreciate the contributions of this work and look forward to a well-founded explanation specifically addressing this issue. And I tend to raise my score if there are some rational explanations.

We thank the reviewer for their constructive feedback and address their concerns below.

• According the reviewers suggestions, we have revised the manuscript and replaced our misnomer layer normalization by normalization or normalization layer.

• We have also addressed the broken Theorem link in the experiment section.

• One of our main contributions is that we have derived the precise scaling requirements. While our experiments primarily serve the validation of our theoretical claims, note that our insights have allowed us to achieve much better performance than previous empirical work [1].

  • However, as we discuss on page 7 in Section 3.1 and on page 8, we have to acknowledge that the precision of numerical solvers is limited in solving large scale linear systems of equations. Note that the matrix $M$ in our experiments has already a dimension of up to $90000 \times 90000$ roughly.
  • In fact, our theoretical results imply that training only BN parameters for computational savings is not a practically reasonable approach if we want to maintain high expressiveness. Only inductive bias in the weight distributions (e.g. as obtained by foundation models) could enable training success despite a low number of degrees of freedom (see Lemma 2.1).

[1] Frankle, Schwab, Morcos. Training BatchNorm and only BatchNorm: On the expressive power of random features in CNNs. ICLR, 2021.

We thank the reviewer for their positive assessment of our work.

We thank the reviewer for the time and effort they put into their review. To address their concern, in the following, we highlight the practical relevance and theoretical significance of our contributions.

Practical relevance:

• The practical relevance of our work is based on insights that can guide the design of neural network architectures, in which BN parameters contribute significantly to the expressiveness of the neural networks (like in WideResNets).

• Concretely, we have derived architectural constraints and make specific proposals how training only BN paramters can achieve the same performance as training a target network. This way, we could outperform previous experiments with architectures, where only BN parameters were trained [1].

• We have proven rigorously that a higher depth can compensate for a too narrow width. This is a relevant insight, in particular, since the random networks that were analyzed empirically were not wide enough.

• Our results imply that training only BN parameters for computational savings is not practically relevant if we want to maintain high expressiveness. Only inductive bias in the weight distributions (e.g. as obtained by foundation models) could enable training success despite a low number of degrees of freedom (see Lemma 2.1). Note that this insight was not well supported even for fully-connected networks because not all trainable parameters were actually utilized in the construction [2].

Significance of theoretical contributions:

• Convolutional layers are an important building block of many contemporary neural network architectures. Therefore, we have to understand their intricacies if we want to gain theoretical insights that are of practical relevance and, up to our knowledge, we are the first to do so in the context of training only training only normalization parameters. (Note that our insights actually allow us to outperform previous purely empirical work on that matter and explain their findings.)
• Convolutional architectures are challenging to analyze theoretically in our context, as the composition of multiple filters induces non-trivial equations that are quadratic (and not linear) in the trainable BN parameters. Furthermore, the composition of convolutional source filters has to overlap with a target filter, which induces additional constraints that do not occur in fully-connected layers.
• Even in comparison to previous work on fully-connected layers [2], we present an improved bound on the source width, which utilizes all trainable parameters (which requires solving a quadratic instead of a linear system of equations). Note that this improved bound is crucial for an important insight into the limitations of the overall approach. If we want to maintain full expressiveness, we cannot use fewer parameters. This insight is not fully supported by previous work [2], which does not utilize all trainable parameters.
• Furthermore, we cover almost arbitrary activation functions and not only linear ones or ReLUs.
• Conceptually, most challenging and novel is the proof of Theorem 2.5 that solves the depth versus width trade-off in the source network.

[1] Frankle, Schwab, Morcos. Training BatchNorm and only BatchNorm: On the expressive power of random features in CNNs. ICLR, 2021.

[2] Giannou, Rajput, Papailiopoulos. The expressive power of tuning only the normalization layers. COLT, 2023.