Batch normalization is sufficient for universal function approximation in CNNs
Authors: Rebekka Burkholz
Venue: ICLR 2024 poster (2024)
Keywords: deep learning
random features
batch normalization
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We prove that training layer normalization layers is sufficient if the remaining neural network parameters of convolutional architectures are drawn from random distributions.

Abstract: Normalization techniques, for which Batch Normalization (BN) is a popular choice, is an integral part of many deep learning architectures and contributes significantly to the learning success. We provide a partial explanation for this phenomenon by proving that training normalization parameters alone is already sufficient for universal function approximation if the number of available, potentially random features matches or exceeds the weight parameters of the target networks that can be expressed. Our bound on the number of required features does not only improve on a recent result for fully-connected feed-forward architectures but also applies to CNNs with and without residual connections and almost arbitrary activation functions (which include ReLUs). Our explicit construction of a given target network solves a depth-width trade-off that is driven by architectural constraints and can explain why switching off entire neurons can have representational benefits, as has been observed empirically. To validate our theory, we explicitly match target networks that outperform experimentally obtained networks with trained BN parameters by utilizing a sufficient number of random features.

Published as a conference paper at ICLR 2024
BATCH NORMALIZATION Is SUFFICIENT FOR UNIVERSAL FUNCTION APPROXIMATION IN CNNS
Rebekka Burkholz
CISPA Helmholtz Center for Information Security 66123 Saarbrücken, Germany burkhol z ci spa.de
ABSTRACT
Normalization techniques, for which Batch Normalization (BN) is popular choice, is an integral part of many deep learning architectures and contributes significantly to the learning success. We provide a partial explanation for this phenomenon by proving that training normalization parameters alone is already sufficient for universal function approximation if the number of available, potentially random features matches or exceeds the weight parameters of the target networks that can be expressed. Our bound on the number of required features does not only improve on a recent result for fully-connected feed-forward architectures but also applies CNNs with and without residual connections and almost arbitrary activation functions (which include ReLUs).. Our explicit construction of a given target network solves depth-width trade-off that driven by architectural constraints and can explain why switching off entire neurons can have representational benefits, as has been observed empirically. To validate our theory, we explicitly match target networks that outperform experimentally obtained networks with trained BN parameters by utilizing a sufficient number random features.
INTRODUCTION
Normalization techniques (Salimans & Kingma 2016 Huang et al.) 2017). for which Batch Normal- ization (BN) (Toffe & [rrgeddy[2015, is popular choice, is an integral part of many deep learning architectures and contributes significantly to the learning success of CNNs. has been designed to stabilize and accelerate the training process by normalizing intermediate feature maps during mini-batch processing. As it also enables the use of larger learning rates, it often improves the generalization performance (Bjorck al. 2018). Effectively, it learns affine linear transformations of neurons. Formally, these transfornations are redundant, as they could be integrated in the weights and biases of the preceding layer. For that reason, theoretical insights that try explain the significant impact of BN on generalization usually focus on its role for the training dynamics (Bjorck et al.) 2018 Santurkar et al.) 2018).
Yet Frankle et al. [2021) have observed an intriguing empirical phenomenon that suggests that batch normalization can still contribute substantially to the expressiveness of CNNs. Removing random BN parameters from the network impacts the performance of a trained model more severely than the removal of random parameters. This is in line with the finding that BN parameters are particularly effective in finetuning language models Ben Zaken et al. (2022): y; Lu et al. (2022). Furthermore, training BN parameters alone while keeping the remaining neural network parameters frozen their initial values can achieve nontrivial performance on standard image classification benchmark data, especially, if the network with or depth are increased (Frankle et al. 202T).
To explain these observations, we delve into the role of normalization as fundamental technique for universal function approximation within CNNs. We prove rigorously that training normalization layers alone is sufficient to represent a wide spectrum of target layers, as long as the underlying architecture sufficiently wide and deep. In doing so, we derive precise requirements on the width, depth, and their trade-off for convolutional and residual architectures and diverse set of activation functions. Our insights imply improvements of bounds that have been established for fully connected networks (Ginnoou et al. 2023)

---

Published as a conference paper at ICLR 2024
Utilizing our explicit constructions of target layers, we further provide empirical proof of concept that random CNNs with learned normalization layers can compete with targets that are fully trained, which could previously not be achieved by training normalization layers from scratch.
Our results thus establish that normalization layers contribute to the expressiveness of CNNs by linearly combining features. They furthermore lay the foundation for investigating to which degree we could save memory and computational costs by keeping a high proportion of neural networks fixed to random values.
Contributions 1) We prove that modern convolutional architectures with randomly initialized tensors fully expressive if they are wide and deep enough and only the normalization layers trained. Our results state precise width requirements to represent target networks of given size. 2) These improve previous bounds for fully-connected networks (Giannou al. 2023). 3) Our theorems apply to large class of activation functions including ReLUs, LeakyReLUUs ss tanh, and sigmoids. 4) Our experiments on CIFARIO and CIFARIO0 provide an empirical proof of concept that training only normalization layers can achieve competitive performance.
1.1 RELATED WORK
Insights into BN BN has been established as default component of most modern neural network architectures due to its significant benefit on training speed and generalization, as it enables training with larger learning rates (Bjorck et al. 2018). It makes the training success robust to different choices of parameter initializations, as it improves initial signal propagation (De & Smith 2020 Joudaki iet al. 2023), J and smoothens the loss landscape (Santurkar et al., 2018). An interesting mechanism how contributes to effective learning is the orthogonalization of features (Daneshmand al. 2021
in combination with learning their affine transformations.
Training only BN (Giannou al. 2023) is closest to work as they derive bounds for the width of fully-connected network layers with ReLUs that are affine linearly transformed to represent an arbitrary target layer. In comparison, our results apply convolutional structures (which encompass fully-connected layers as special case), apply to a large class of activation functions, and improve the bounds for the construction of target layer from two source layers in the fully-connected setting. Furthermore, we derive an novel construction that utilizes multiple source layers. It is based on CNNs (instead of residual targets) and achieves a much lower bound on the required target width. This work was inspired by (Frankle et al., 2021). who propose the conjecture that training BN layers might be fully expressive based on experimental insights for CNNs and ResNets. While (Rosenfeld & Tsotsos 2019) have also studied training only BN parameter experimentally, they could not reach the same conclusion, as they have focused on relatively short training periods.
Alternatives to BN The high computational and memory costs of BN and the fact that it breaks the independence of minibatch samples and prevents adversarial training (Wang et al.) 2022) are all major disadvantages, which have inspired the search for alternatives Zhang et al. (2018); Brock ct al. (2021b). A combination of scaled weight standardization and gradient clipping has recently outperformed BN (Brock al. 2021b). Our derivations for general affine transformations and different normalization mechanisms also apply to this setting. Otherwise, initialization approaches that are tailored specific architectures can also make BN obsolete (Balduzzi et al.) 2017 Burkholz & Dubatovka ka 2019: De & Smith, 20200; Zhang et al.) 2018 Gadhikar & Burkholz [0222) The generation of such random parameters might also induce an inductive bias that could induce fewer affine transformation parameters.
Lottery Ticket Existence Our theoretical set-up is similar to lottery ticket existence proofs in fully- connected layers (Orseau et al. Pensia et al.) [2020] Burkholz 2022b) and CNNs (da Cunha et al. 2022 Burkholz 2022a Burkholz et al. (022) in the sense that we construct targets based on two or more (Burkholz) 2022b; Gadhikar et al. 2023) random source network layers. Existence results in this context are also concerned with the question of universality versus specificity to targets that could reduce the width requirements (Burkholz et al. 2022) and solve trade-off's related to the depth and width of a target network representation. The underlying questions are fundamentally related, the search for strong lottery tickets extracts information from random source networks by pruming away connections (Zhou et al., 2019; Ramanujan et al., 2020), while this work studies a different extraction mechanism, i.e., affine linear transformations.
2

---

Published as a conference paper at ICLR 2024
(a)
(b)
4-11
*
(c)
c(2
NO c())
C
12i-2
22
121-1
Figure I: Construction idea. (a) The convolution of two tensors creates a larger tensor that represents target tensor. (b) Target 2d-convolutional layer. Each channel is represented by colored cuboid. A highlighted region visualizes a filter. (c) Two layers with random weights approximate a target layer.
UNIVERSAL APPROXIMATION
Standard convolutional neural networks (CNNs) and fully-connected heed-forward neural networks, which can be regarded as special case of CNNs, possess the universal approximation property. This means that they can approximate any continuous function if they are wide and deep enough Gühring al. (2022); Shen et al. (2022). Our main objective is to show how convolutional random CNNs with trainable affine linear transformations like BatchNorm inherit this ability.
Our argument is of the following structure. We want to show that source network fa with relatively arbitrary weight tensors can be adapted with affine linear feature transformations to solve general task of interest. Let assume that target network fa is given that solves such task. This target exists because of the universal function approximation property of neural networks. Given that target and the source weights, we thus have to find affine linear transformations parameterized by y that the source approximates the target f= 7) = f(().. To make these statements more precise, we introduce a more rigorous mathematical notation.
2.1 BACKGROUND AND NOTATION
Our expressiveness results hold for general convolutional structures with or without skip connections.
convolutional neural network f C R -> Re Rdz is defined on a compact domain and has channels ē = [Co. C1, ...,, ) i.e., depth I. and width in layer 1 E [L] := (O. L}. Without loss of generality, let D C [-1, 1 X be contained in an interval (which could always be achieved by rescaling the input). A layer is generally parameterized by a a bias vector b(9) E Ra and weight tensor (!!) xexx-1xx;; which comprises the filters (or convolutional kernels).
C--1
11) = o (n.",
h000 = (1) = Σ w 4 x (1-1) + 6DD
(1)
(I)
(.))) is called pre-activation and is transformed by univariate activation function (xx). To simplify and generalize our notation, we have flattened the filter dimension to kG. In case of the common 2d convolutions, the weight tensor would actually have the size (() E x so that k dim(k( ká The convolution operation between any 2-dimensional tensors K and X is in this case. We assume that the inputs are always suitably padded with zeros and that the symbol performs the convolutions in the right dimensions (for simplicity with stride 1). The flattened notation just makes it casier to discuss higher dimensional filters at the same time. The type of convolution determines the dimension of the effective filter dim &1, k2) that describes the composition of two consecutive filters with dimensions k and k2. For instance, the composition of a kí,1 x ki filter with 1/, x 12 results in a filter with dimension dim(k, , A2) (K4,, + K2 - 1) x (K/,1 + M2 1).
defined as (K X)++ Ev,r (o-x)(t-+++---00
In addition to convolutional layers, we also allow for residual and more general skip connections.
Skip connections modify the network above as x = (n + - s(l.t) * x (t) We
could accommodate this general form but this is not required for universal function approximation.
3

---

Published as a conference paper at ICLR 2024
In residual architectures, which are often employed to improve the trainability of very deep CNNs, usually, only one or two layers are skipped so that (!..)) is nonzero for / = 1+ 1 or I = 1 +
In addition, most modern architectures consist of additional normalization layers Nxx) that tend to substantially improve the training and generalization performance of the model. They are either positioned before the activation function and after the convolution operation &
or immediately after the activation function NV (o (n...) (h. in case of post-activation structure. As pre anevvvtiasiions usually lead to better performance, at least for Batch Normalization [offe & Szegedy (2015) in ResNets He et al. (2015b), we focus our analysis on this case. However, our general approach would also transfer to post-activations. Most normalization strategies apply an (affine) linear transformation of their input vector. Examples include BN, one of the most effective and frequently deployed approaches. Yet, it is highly memory intensive, since it works best in combination with relatively high batch sizes. Other variants like weight normalization (Salimans & Kingmal 2016 Huang et al. (017). weight standardization (Qiao et al. 2019), instance normalization (Ulyanov et al. [2016), Instance Enhancement Batch Normalization (Ling et al., (2200) switch normalization (Luo et al. (201)) can address this issue and still achieve competitive performance in several cases (Brock al. 2022 a). They all can be formulated effectively as / (h)= == 7h + B, where each channel is transformed separately. 7, B E R are learnable parameters in most cases. The shift is not always tuned but erucial to avoid singularites, completely (Qiao et al. 2019). 33 thus replaces the bias parameter of the previous convolutional layer, which is often removed by centering operation. y and / both have components that are estimated based on parameter (aannettrsSSmmansss [Salimans& & Kingma (2016) or batch statistics [loff & Szegedy (2015), which are implicitly integrated in the above formulation. Regarding them explicitly would not change our theoretical results.
which neurons get switched off
Note that in standard neural network architectures, 7, do not contribute to the expressiveness of the architectures and thus the functions that the networks can potentially represent, as they could be integrated into the weight tensor and bias of the previous convolutional layer. Thus, 7. 8 contribute to the overparameterizatioo of the networks. Their main role is to change the training dynamics and help avoid exploding weight norms or switching off neurons by accident.
Interestingly, our results together with (Frankle et al. 2021 Giannou et al. 2023) indicate that the normalization parameters might not just control the range of activations but might significantly contribute to learning meaningful representations, especially in the presence of high width and/or depth overparanneerrzztion. Given a convolutional layer, 7, / define linear combinations and shifts of pre-activation features that give the architecture full expressive power if sufficiently many features are available. As we prove, even if the weight tensor and the biases remain frozen in their initial random state and are not trained, learning only the normalization parameters y, 3 allows the network to represent any target layer of certain size.
2.2 Two CONVOLUTIONAL LAYERS FOR ONE TARGET LAYER
Our main goal is to derive a potentially random convolutional source network structure S that is able to represent arbitrary target convolutional layers (()) of given dimension only with the help of affine transformations. This implies that the affine transformations of the normalization layers of S are fully expressive. Our main construction approach represents each convolutional target layer by the composition of two convolutional source layers = (() as visualized in Fig. [ For simplicity, let us first assume that the activation functions of the first source layer are the identity. while the activation functions that follow the target layer and the second source layer coincide. Later, we will also discuss how to adapt our results to almost arbitrary activation functions of the first layer.
(t) For each possible target with parameters ff 1/ eters (g()), -3 (()))) for i E [[2]] E
we have find source param-
[cal.j E [cu] so that w!(
(1) (2) (2) E, E (Z()) w Wilp "jq" where the kernel indices p,q E I(k) correspond to the po- 71
(2)
sition i in the tensor that is formed by the composition ((2)((1) (see Fig. (a) for example). The biases fulfill 3
for linear activation functions and 8((2) = -((), While this system of equations
is quadratic, we can reduce it to linear one in (1) by solving for ( first. For each i [c2].
4

---

Published as a conference paper at ICLR 2024
choose a pivotal element (jx, ks) j,a (6) and use 7/
(2) to make sure that Wig,, is exactly
(e)
represented. Note that we could pick any element (ijk) with nonzero (t)
loggl We simply pick the
pivotal one for numerical stability. This transforms our problem
My 0, for M- (m1J) with mys
Σ
Wayp w
(2) (1) Jjn
W Ejkk
Σ
WiJp, Jiin:
(2) (1)
(x.0)
Si (PrOO)EZ((A))
(2)
that we have to solve for nontrivial (2)) o O. The index I corresponds to the position of the index set (i.j.k) in flattened representation, while J denotes the index of 7J (1) in that same representation.
The following theorem states the conditions when this system of linear equations has a solution.
Lemma 2.1 (Single layer reconstruction). Let two consecutive convolutional and normalization layers S (x) = - (C (NT() (CO) (x)))) of channel dimensions Cz C1, Co and kernel dimensions k2. k1 be given. Then, each target convolutional layer C(t) of dimensions Co, and ks with nonzero output channels Σj,t |u >> for all E [c2] can be represented exactly by adjusting N(O) and A/(2) ifM = (mrJ) as defined by Eq. 2 has nullspace dimension ker M 2 1.
Can all target networks be represented this way? Importantly, the matrix M with e2codim(ks ( k1) we picked the target network dependent on the source S, we could reduce the dimension of M's
C rows depends on the target, which has C2ca degrees of freedom. Thus,
(2) (1) (w w ( which can column space by 1, for instance, if lą = 1 and wiyk/ Wiyck = whip " only be fulfilled if the right hand side's magnitude is bounded by 1. We therefore have to incorporate an additional assumption on the target network to translate this insight into bound on the source width. In practice, this excludes an irrelevant target space, as we will also demonstrate in experiments.
(f) (t)
(2)
Theorem 2.2 (Minimum width requirement). Assume that the tensor entries of S are drawn inde- pendently from the target and mutually independently of each other from continuous probability distributions with finite mean and nonzero variance. Then Problem (2) has a nontrivial solution with high probability (i) Ak dim(k2,k1 kz) kt 2 0 and (ūi c1 2 e2Cydim( l2z, ka) C2 +
This result also covers fully-connected layers. where all channel dimensions are one one-dimensional l2 = k1 = k In contrast to Giannou et al, (2023), we only require width of c 2 C2 02 +1 instead of C2 The reason is that we also use the scale parameters 712) of the second layer for representing the target. Yet, we also have to exclude pathological targets in this statement. The maximum width requirement to really represent any possible target network can be derived by setting
(22) to arbitrary nonzero values, which makes M independent of the target network itself so that it becomes generally invertible.
Theorem 2.3 (Maximum width requirement). Let the tensor entries of S in Theorem 2. be drawn independently from continuous probability distributions with finite mean and finite nonzero variance. Then can represent any nonzero target with high probability (i) Ak = dlim(k2. k1) - kr 2 0 and (ii) C1 2 c2Cydim(k2,, k1).
Note that (ii) implies that our width requirement depends on how well our source kernel dimensions align with the kernel dimension of the target. Our flattened representation of the kernel dimension hides the fact that we need the kernel of the target layer to be fully covered by the convolution of the two source layers. If additional elements are produced by the product that are not present the target kernel, we need more parameters to guarantee that we can learn a representation of the target that sets such elements to zero. Thus, ideally, we consider convolutional layers with dim(k2, k1) k to minimize our width requirement in (i). This can be achieved most easily by choosing one of the convolutional source layers to be one-dimensional, e.g., k₁ = 1 and the other layer to have identical kernel dimensions the target layer, i.e., ha k. To simplify notations in the following, assume that log = k; and skip the index k = 1.
Residual blocks. While have focused exposition on convolutional source layers, Frankle et al. (202I) have primarily analyzed residual source blocks, as they could train deeper architectures more easily. Our results can be easily adapted to this case still assuming convolutional target layer. The
5

---

Published as a conference paper at ICLR 2024
adaptation depends on the position of the second normalization layer relative to the skip connections. In the simpler case, we have S = ((2 + C(aksp), Applying our previous results to the modified target (((1 - (<kkip) where ((skip)) is defined so that it is compatible with W would suffice. In the more common case of an outer normalization S = _V [c()) + C(skip)]. we have solve modified system of linear equations that relies on the same matrix M but does solve for but a vector с with
My (1) c; for C₁
w (t) Wj
Fiik (skip)
(3)
kjckk
2.3 ALMOST ARBITRARY ACTIVATION FUNCTIONS
Previously, we have assumed that the first layer of the source network has the identity as activation function, which made the biases of A(!) obsolete. Yet, most common neural network architectures employ non-line linear activation functions after every layer. To explain the experimental findings by (Frankle et al. 202T), we therefore have to cover at least ReLUS (xx) = max(x; L 0} after the first source layer. As we show, many activation functions enable an approximate reconstruction of target layer by modifying our results for linear activation functions. We just need to be able to scale and shift the bounded imput that it is approximately linearly transformed by c, as visualized in Fig. 2
Theorem 2.4. Assume that the conditions of Lemma 2.1 are met by S. Let another source S be defined S (x) = _N(22) (Ct2) (á (NO) (C(3) (x)))) with the same convolutional layers S but potentially different normalization layers. Based on the normalization layers of S, define two constants Q1 == max, 15000 Ex (1) and Q2 == max;, (:(2)) Σn [
If for given > O there exist constants 7,, b, m. E RR so that lØ(yz + b) - (myz + mb + c) S eym/Q2 for all x E [-Q1,, 101,Qil Q1). then the normalization layers can be adjusted such that [S(x) - (x)) S e for all E [-1,1] where . denotes the supremum norm.
The proof is presented in the appendix. Essentially, this theorem states that we can transfer our previous results to nonlinear activation functions long we find region of the activation function that is approxi- mately linear and the error scales sublinearly. Several relevant activation functions have this property. For instance, ReLUs ((x) max 0} and leakyReLUs o(z) = max x. 0} - a max( 2x, 0} inflict zero error with 7 1, b Qi m 1. c 0, and thus even work with = 0. d(x) = (anh(z) fulfills [x-)(x)] < x² 12//3 /3 for |ol < 1. Thus, the choice 7 = ((ce/2))
output
x mb c
my
x(x) ~ mx +
6 0. m 1, c 0 would be sufficient. Similarly, sigmoids d(x) (tanh(x/2) + 1)/2 work with
(1n(((22222))) 1/Q1), ). b = 0, m 1/4, c = 1/2. Thus. our theory attests that the experimental evidence for ReLUs Frankle et al. (202l) and theoretical results for ReL.Us on fully-connected networks (Giannou al. 2023) also transfer to other activation functions.
7e + b
input
Approximation of the iden- tity. After linear transformation of an in- put, the activation function 6(x) is eval- uated in an approximately linear region. Another linear transformations maps the output back to the original input.
Figure 2:
2.4 TRADE-OFF BETWEEN WIDTH AND DEPTH
So far we have established representation results for train- ing only the normalization layers of randomly initialized weight tensors for different activation functions, where we would approximate one target layer by exactly two source layers.
Multiple target layers. Similarly to lottery ticket existence proofs (Burkholz) 2022b da Cunha et al. (002), our results for the representation of a single target layer can also be transferred to the composition of multiple target layers by utilizing two consecutive layers in the source network to approximate target layer. In consequence, the source network would have double the depth of

---

Published as a conference paper at ICLR 2024
potential target network. As long each layer inflicts enror of maximally O(e/L), where L is the depth of the network, under mild assumptions on the target (Burkholz) 2022b da Cunha et al. 2022) the overall upproximation error can be bounded below e 0.
Implications of 2-layer construction. The width e₁ of the first source layer in our construction is very large in comparison with the input and output dimensions. To achieve full expressiveness, it has to scale quadratically in the input and output, i.e., C₁ x c2cokgki, which corresponds to the dimension of potential target tensor and thus the trainable parameters. Even if high proportion of the network parameters is set to random values, we still need to ensure that we have a sufficient number of degrees of freedom. Thus the number of trainable parameters in the normalization layer cannot be reduced magically. Only if the target tensor and the random weight would align well, could we expect to require fewer parameters. The experiments by Frankle et al. (202T), however, were conducted with an architecture that consists of multiple layers of more similar size. Yet, the authors observed that roughly 1/3 of output neurons was learned to be switched off.
Why can it be beneficial to switch off neurons? According to our theoretical results, removing neurons in the output layer has the effect that the number of channels e₁ in the first source layer could reach the required with to represent target output layer. Alternatively creating additional random outputs would negatively influence the representation, as random combinations would contribute to each output of the next layer. Yet, switching off neurons is not the only option to effectively utilize the available degrees of freedom.
Utilizing multiple source layers. Instead of using source layers with very wide hidden dimension, also more source layers of lower (and thus more balanced) width can be employed to represent a single target layer. This can be shown trivially for residual source networks that have least twice the width of the input channel dimension, as a target tensor can be represented as composition of multiple residual layers that concatenate the input x and current state of the target tensor construction as + Ex Wix (see (Ginnouu et al. 2023) for a construction for fully tully-connected source and target networks). The downside this representation parameters (at least by factor of 4) than a representation based on 2 layers. Our next next result for convolutional targets and source networks establishes a much stronger width requirement.
that it requires higher number of total trainable
Theorem 2.5 (Deeper source networks). Let the the source network S consist of L. consecutive random convolutional layers (with linear activation functions). Then the parameters of the normalization layers can be adjusted with high probability such that a given target convolutional layer can be represented exactly (i) Ak = dim(ki,... ..... kr.) - k2 2 0 and (ii) Et= C4 2 er,oodim(k) ..,, kI.. + L
and (iii) a Z co for all source layers 1 E [T]]
In conclusion, to utilize lower source widths q. we have to pay with L more trainable parameters. T. degrees of freedom are lost as the parameters 7 of different layers are scale invariant. The main construction idea of the proof is to show inductively that we can decompose the problem into a linear system of equations and system that is polynomial in fewer parameters 7/ than the original problem.
Implications. While it is remarkable that learning normalization layers is fully expressive, our theoretical results study primarily the conditions that allow to represent almost arbitrary target networks of given size and thus imply strong width requirements. In practice, however, specific random tensor distributions that fit a learning task might possess a relevant inductive bias that allows the training of smaller random networks. Understanding the nature of promising random distributions could be a viable strategy to effectively reduce the number of required trainable parameters in future.
EXPERIMENTS
3.1 RECONSTRUCTION ALGORITHMS
To reconstruct specific target tensors in our experiments based on random source networks, we have to solve large scale systems of linear equations. While there exist numerical algebra solvers such as the pytorch function torch. linall..ooloao.. solve, they suffer from accumulating approximation errors for larger matrices. To reduce the error, we finetune the resulting solutions with LBFGS as implemented by the Pytorch function torch.optim. LBFGS that minimizes the mean squared error between our constructed network and the target. The error can still be sufficiently high to hamper exact reconstruction (see Tables 1 and 2). Interestingly, solving an overparameterized linear system with LBFGS that focuses
7

---

Published as a conference paper at ICLR 2024
solving " and fixes "/2 to almost arbitrary values reduces the approximation greatly and enables near perfect reconstruction.
3.2 PROOF OF PRINCIPLE: BATCH NORMALIZATION SUFFICIENT
The goal of experiments is to verify the validity of our construction and provide empirical evidence for the fact that random features allow us to reconstruct a target network with exactly the same number of trainable parameters machine with Intel(R) Core(TM) 19-10850K CPU @ 3.60GHz processor and GPU NVIDIA GeForce RTX 3080 Ti and we report averages and 95%-confidence intervals for independent repetitions. To
need to represent the target. All experiments were conducted
Table I: Target reconstruction for CIFARIO. Averages and 0.95 standard confidence intervals are reported for independent source network initializations. Columns correspond different random feature distributions and rows to networks with different activation functions.
TARGET
HE NORMAL
HE UNIFORM
ORTHOGONAL
SPARSE HE NORMAL
RELU
94.12
94.1 + 0.08
94.0 + 0.1
94.12 + 0.07
94.12 + 0.07
LRELU
94.37
94.34 + 0.05
94.1 0.1
94.4 0.2
94.3 + 0.1
TANH
93.66
93.5 0.1
0.1
93.45 0.05
93.5 + 0.1
SIGMOID
92.9
92.8 0.04
92.5
92.7 0.1
92.8 0.04
obtain suitable targets with different activation functions, we have trained VGG18 (GG18-like structures that consists of 18 layers (17 convolutional with 3-dimensional filters, one final linear layer) of channel width 64 the intermediary layers with 592657 parameters in total. consider two standard image classifcation benchmark datasets, CIFAR10 10 and CIFAR 100 (Krizhevsky) 2009) and use standard training procedure: SGD with 5 warmup epochs and linear learning rate increase, followed by 200 epochs of cosine annealing with initial learning rate 0.1.
Our targets have only width c = 64, as this enables us to repeatedly solve the related large scale systems of linear equations with memory and time intensive specialized numerical linear algebra methods (as implemented by Pytorchs torch. liwalg..al.lo................. tirch. solve function). These equations arise when we explicitly match the targets according the construction of our theorems. As the number of rows of the involved matrix M scales as e²k, - + 6429 64 + 36801, we are still able to match target networks with different activation functions. Note that target performance still exceeds the accuracy of the networks which resulted from training only BN parameters of wide and deep ResNet or VGG architectures (Frankle al.) 2021). While previous experimental work was focused on ReLUs, we demonstrate that the same principles apply also to other activation functions. Specifically, we report results for ReLU, LeakyReLU, tanh, and sigmoid.
To verify the practical relevance of our theoretical claims, we explicitly construet scale and shift parameters of networks with random weights so that the source network with adapted affine linear transformations matches a given target network. To achieve that, we consider source networks where two layers represent one target layer as stated in Theorem 2.2] where the first layer has kernel dimension 1. The source weight tensors have been randomly sampled from standard distributions that are commonly applied to initialize neural networks before training. We consider normal or uniform distributions proposed by He et al. (He et al. 2015a), random orthogonal weight tensors (Pennington et al., 2017 Burkholz & Dubatovka| 2019). and a sparse He normal distribution, where each weight tensor element set to 0 with probability 0.5 (Liu al. 2021
Table 2: Target reconstruction for CIFAR100. (See Table for a detailed description.)
TARGET
HE NORMAL
HE UNIFORM
ORTHOGONAL
SPARSE HE NORMAL
RELU
70.46
70.34 0.02
70.1 0.2
70.3 + 0.2
70,2 0.2
LRELU
70.22
94.37 1 0.01
93.88 0.16
94.12 + 0.07
94.12 0.07
TANH
69.65
69.5 1 0.03
69.3 0.2
69.4 4 0.1
69.6 + 0.05
SIGMOID
67.42
94.1 + 0.08
0.08
93.88 0.16
94.12 0.07
94.12 + 0.07
8

---

Published as a conference paper at ICLR 2024
Note that the random weight matrix M, which is required to have full rank, meets this requirement. However, the approximation error for problems of this size is high enough to induce small performance variations in the reconstruction as visible in Tables I [ This problem is not substantially amplified for larger targets. As a proof of concept, we have additionally obtained target networks with width 100 and ReLUs that reach accuracy of 94.94 and 73.34 on CIFARIO and CIFAR 100, respectively. For He normal random weights, we our performance after reconstruction is 94.93 + O. 0.03 and 73.37 + 0.05, Altogether, our experiments verify our theory and target construction approach.
We could also attain higher reconstruction accuracy if we were willing to further increase the width of the source network above the required minimum, as our gradient based solution algorithms benefit greatly from this small amount of overparameterization in terms of learning speed and accuracy, as has also been observed in the context of learning deep neural networks. If we increase the width by less than 80 or 120 parameters per layer, we do not observe any performance degradation if we employ overparameterized LBFGS (a variant of gradient descent) to minimize the mean squared error between our construction and the target.
Adjusting only BN parameters is computationally feasible. From a conceptual point of view, we have thus presented not only theoretical but also practical existence proof that training only BN parameters sufficient, the required models are of feasible size and can still outperform the results that were obtained by learning only BN parameters from scratch Frankle et al. (2021).
Training from seratch misses the mark. Frankle et al. (021) have conducted experiments with standard convolutional and residual architectures on common image benchmark data, yet, could not achieve the expected performance of similar architectures. A possible explanation might be that the considered architectures were not designed based on the derived based on the presented insights and thus were neither sufficiently large nor structurally promising.
To test this hypothesis, we have trained a convolutional architecture that would theoretically corre- spond VGG18-like architecture with hidden width 100 on CIFARIO. Each target layer could be represented by two random source networks with linear activation function after the first layer. This choice avoids potential issues with switched off ReLUs after the first layer that could result from unstable learning dynamics. Yet, even if we provide it with additional overparameterizzttion (like 10a additional channels) and extended warmup cycles, training the normalization parameters only achieves generalization error of 90.35 + 0.1 in three independent runs. These are clearly not competitive with the generalization accuracy of potential target models (of at least 94%).
Training normalization parameters alone seems to require different specialized learning schedules. The future development of such algorithms could positively affect the learning dynamics of normal- ization layers also when they are trained in combination with the remaining network parameters.
CONCLUSIONS
Our work shows that normalization layers of modern convolutional neural network architectures are fully expressive if the weight tensors are sufficiently wide or deep and stay fixed to their initial random values. This rigorously proves the conjecture by (Frankle et al. 202 and derives the precise width and depth requirements for a random source network relative to a target network that enable the exact reconstruction of target network. In comparison with previous experimental results, we have extended the theoretical and experimental evidence to relatively general class of activation functions (that includes but not limited to ReLUs) and different random tensor distributions.
Based on the derived target reconstruction, we have provided an empirical proof of principle that normalization layers alone can achieve the expected performance on standard benchmark data, which was previously not attainable by training the normalization layers from scratch with standard learning schedules (Frankle et al. 2021).
This evidence complements insights into the diverse roles or normalization layers, in particular BN layers. As they add redundant parameters, normalization is primarily believed to impact the training dynamics positively, for instance, by enabling larger learning rates. The derived expressiveness of normalization layers suggests, however, that they could also contribute in a representational sense by learning linear combinations of currently available features.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We gratefully acknowledge funding from the European Research Council (ERC) under the Horizon Europe Framework Programme (HORIZON) for proposal number 101116395 SPARSE-ML.
REFERENCES
David Balduzzi, Mareus Frean, Lennox Leary, P. Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what is the question? In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 342-350, 2017.
Elad Ben Zaken, Yoav Goldberg, and Shauli Ravfogel. BitFit: Simple parameter-efficien fine- tuning for transformer-based masked language-models. In Annual Meeting of the Association for Computational Linguistics, 2022.
Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normaliza- tion. In Advances Neural Information Processing Systems, volume 31, 2018.
Andrew Brock, Soham De, and Samuel L Smith. Characterizing signal propagation to close the per- formance gap in unnormalized resnets. In International Conference Learning Representations, 2021a.
Andy Brock, Soham De, Samuel L Smith, and Karen Simonyan. high-performance large-scale image recognition without normalization. In International Conference on Machine Learning, pp- 1059-1071, 2021b. 2021b.
Rebekka Burkholz. Convolutional and residual networks provably contain lottery tickets. Interna- tional Conference on Machine Learning, 2022a.
Rebekka Burkholz. Most activation functions can win the lottery without excessive depth. In Advances in Neural Information Processing Systems, 2022b.
Rebekka Burkholz and Alina Dubatovka. Initialization of ReLUs for dynamical isometry. In Advances in Neural Information Processing Systems, volume 32, 2019.
Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. In International Conference on Learning Representations, 2022.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations, 2022.
Hadi Daneshmand, Amir Joudaki, and Francis Bach. Batch normalization orthogonalizes representa- tions in deep random networks. In Advances Neural Information Processing Systems, volume 34, pp. 4896-4906, 2021.
Soham De and Sam Smith. Batch normalization biases residual blocks towards the identity function in deep networks. Advances in Neural Information Processing Systems, 33:19994-19975. 2020.
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. Training BatchNorm and only BatchNorm: On the expressive power of random features in CNNs. International Conference on Learning Representations, 2021.
Advait Gadhikar and Rebekka Burkholz. Dynamical isometry for residual networks, 2022.
Advait Harshal Gadhikar, Sohom Mukherjee, and Rebekka Burkholz. Why random pruning is all we need to start sparse. In Proceedings of the 40th International Conference Machine Learning, volume 202, pp. 10542-10570, 2023.
Angeliki Giannou, Shashank Rajput, and Dimitris Papailiopoulos. The expressive power of tuning only the normalization layers. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195, 2023.
10

---

Published as a conference paper at ICLR 2024
Ingo Gühring, Mones Raslan, and Gitta Kutyniok. Expressivity of Deep Neural Networks, pp. 149-199. Cambridge University Press, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 20155b.
Lei Huang, Xianglong Liu, Yang Liu, Bo Lang, and Dacheng Tao. Centered weight normalization in accelerating training of deep neural networks. In IEEE International Conference on Computer Vision (ICCV), 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456, 2015.
Amir Joudaki, Hadi Daneshmand, and Francis Bach. On bridging the gap between mean field and finite width deep random multilayer perceptron with batch normalization. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. (3388-15400, 2023.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Senwei Liang, Zhongzhan Huang, Mingfu Liang, and Haizhao Yang. Instance enhancement batch normalization: An adaptive regulator of batch noise. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 2020.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. International Conference on Learning Representations, 2021.
Kevin Lu, Aditya Grover, Pieter Abbeel, and Igor Mordatch. Frozen pretrained transformers as universal computation engines. AAAI Conference on Artificial Intelligence, 36(7). 2022.
Ping Luo, Jiamin Ren, Zhanglin Peng. Ruimao Zhang, and Jingyu Li. Differentiable learning-to- normalize via switchable normalization. In International Conference on Learning Representations, 2019.
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Advances in Neural Information Processing Systems, 33, 2020.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. Advances in neural information processing systems, 30, 2017.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over-parameterization is sufficient. In Advances in Neural Information Processing Systems, volume 33, pp.
2020.
Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Micro-batch training with 2019.
batch-channel normalization and weight standardization. arXiv preprint
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in randomly weighted neural network? In Conference Computer Vision and Pattern Recognition, 2020.
A. Rosenfeld and J. K. Tsotsos. Intriguing properties of randomly weighted networks: Generalizing while learning next to nothing. In 2019 16th Conference on Computer and Robot Vision (CRV), pp. 9-16, 2019.
11

---

Published as a conference paper at ICLR 2024
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances in neural information processing systems, 29, 2016.
Shibani Santurkar, Dimitris Tsipras, Andrew Hyas, and Aleksander Madry. How does batch normal- ization help optimization? Advances in neural information processing systems, 31, 2018.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of relu networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, 2022.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv: 1607.08077, 2016.
Haotao Wang, Aston Zhang, Shuai Zheng, Xingjian Shi, Mu Li, and Zhangyang Wang. Removing batch normalization boosts adversarial training. In International Conference on Machine Learning. pp. 23433-23445, PMLR, 2022.
Hongyi Zhang, Yann N Dauphin, and Tengyu Ma. Fixup initialization: normalization. In International Conference on Learning Representatiins, 2018.
Residual learning without
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems, pp. 3597-3607, 2019.
A APPENDIX
A.1 PROOF OF LEMMA
Statement (Lemma 2.1 in main manuscript). Let two consecutive convolutional and normalization layers S (x) = (2) (c(2) (WC) (CO) (x))) of channel dimensions C22 C1, co and kernel dimen- sions k2, k1 be given. Then, each target convolutional layer c(+) of dimensions c2, and ke with (t)
nonzero output channels Ej |oykk > 0 for all i [e2] can be represented exactly by adjusting A(O)) and (22) if M = (mzJ) as defined by Eq. has nullspace dimension ker M 2 1.
Proof. For each possible target with parameters (wigh (()), we have to find source parameters (1) (2) 3(2 11 8)9) for i E [co], J E [ca],j [co] so that
(t) Gj
(2)
Σ Σ
(2) (1) (2) TJ w Jiq
(P-9)ET(()
where the kernel indices p and q correspond the position le in the tensor that is formed by (())
(see Fig. 1 (a) for an example). The biases fulfill 35 0 for linear activation functions and
(
While this system of equations is quadratic, we can reduce it to a linear one (1) by solving for (2) first. For each i [c2], we choose pivotal element (je, k2) argmax,,, woykl and use x( to
7
(1) make sure that w Wiyck is exactly represented.
This results in
( Apck;
(2)
7
(5)
Σ, E(P.)) w J 2J Jjsq:
2 11) (2)
Replacing this expression in Eq 4 leads to the stated definition of M.
12

---

Published as a conference paper at ICLR 2024
A.2 PROOF OF THM. 2.2
Statement (Thm. 2.2 in main manuscript). Assume that the tensor entries of S are drawn inde- pendently from the target and mutually independently of each other from continuous probability distributions with finite mean and nonzero variance. Then Problem (2) has a nontrivial solution with
high probability if (i) Ak dim(k2 k1) kt 2 0 and (ii) ci 2 e2cydim(k2,, k1) C2 +
Proof. Overall, we have to account for c2cgk; degrees of freedom of the target. Condition (i) ensures that the kernel dimension of our construction matches the kernel dimension our target network. If A > O, we obtain additional constraints, the constructed kernel also needs to assign 0 to values that do not overlap with the target kemnl.. Overall, we therefore have c2cjdim (b2, k1) degrees of freedom. C2 of those are automatically fulfilled by our choice of 7/ that results in
10
(2) (1)
(2) (1)
w fickk W Widp; w) "Jjvg"" Yet, we need an additional column to ensure that the nullspace dimension is ker M 2 such that a nontrivial
matrix entries mjj == (p.g))Z(()) W "ig Σ (pL.q:)EZ(kk))
solution y(t) exists to the respective system of linear equations. M therefore needs have least 2 غ = e2codim((2, ki) - + columns.
To construct a solution, we effectively add another condition to our set of equations, namely Ee 7
that demands a non-trivial and invert the respective matrix.
What left show is that a quadratic submatrix M, of M with ē rows and ē columns has full rank and is thus invertible with high probability. In this case, possible solution for our construction would fulfill " M, where the vector is defined via column of M that is not included in the submatrix. Without loss of generality, let this column be the first one and
M,
so that M, and 71
-1-- - (1)
Our proof concludes when we can show that M, has a full rank with high probability. To do so, we employ a similar strategy as Giannou et al. (2023), who show that the Khatri- Rao product of two random matrices full rank with high probability. Therefore, we also use the following Lemma 5 of (Giannou al. 2023).
Lemma A.1 (Lemma of (Giannou et al.
2023 Let p(x) be a polynomial of degree d, x E IR". If {x R p(x) = 0} is or measure zero (with respect
p is not the zero polynomial, then the set S
to the Lebesgue measure).
As a consequence, it sufficient to show that det M, is nonzero for specific assignment M of the otherwise random tensor elements. As this would imply that det M, is not the zero polynomial, the set S of source weight tensors that lead to non-invertible M, with det M, = 0 has zero probability measure.
A specific assignment that we consider for this purpose has elements w. W.pp = 0 and WiJp di, 8pp, (1) = 033 for one (p.g) E I(k), where stands for the Kronecker delta. Consequently, and WJj9
my, simplifies to the identity matrix (Mis) = (ōrJ) Thus, we have det M. = + 0 and random M, are invertible with high probability.
A.3 PROOF OF TIM. 2.3
Statement (Thm. 2.3 in main manuscript). Let the tensor entries of S in Theorem 2.1 be drawn independently from continuous probability distributions with finite mean and finite nonzero variance. Then S can represent any nonzero target with high probability if (i) Ak = dim(k2, ki) ke 2 0 and (ii) C1 2 c2cndim(k2,, ki).
Proof. The proof of this theorem is essentially already contained in the previous one. (ii) ensures that we can set (22) and still solve the resulting system of linear equations Mn((1) Wt, I with (1)
2 c2codim k2, k1) rows and columns, where myJ = (p)))) Wijp "Jjy"
We have already shown in the last proof that also a matrix with structure M = (1)
E(pareza) (1/ [jg) is invertible with high probability. We simply use again the assign-
13

---

Published as a conference paper at ICLR 2024
ment Wijp Spp for (p,9g= E I(k) and w339 dgg to construct the identity matrix, which has nonzero determinant.
(2)
(1)
A.4 PROOF OF THM. 2.4
Statement (Thm. 2.4 in main manuscript). Assume that the conditions of Lemma 2.1 met by S. Let another source S be defined as S (x) - (C!²) (& (AVC) (C() (x)))) with the same convo- lutional layers as & but potentially different normalization layers. Based on the normalization layers of S, define two constants Q1 := max, (n] Ez [Jj and Q2 == max;, 17 (2) Σ, [w
If for given > 0 there exist constants y, b, m, E R so that 1Ø( + b) - (myy + mb + c) S cym/Q2 for all E [-Q1, Qı), then the normalization layers can be adjusted such that [S(x) - c (x)) S e for all x E [-1, 1 where
denotes the supremum norm.
Proof. We have to show that [S(x) c (x)) S e under the stated assumptions.
To do so, let us first define the normalization parameters of S that impose the required scaling so that we can approximate (xx) mx + c.
n = -i. 850 = b, 7/ = 7.0) (mr)) and B8² = B(²) mb+e If the activation function
were @. (a) = m. + b. then these normalization parameters would make S. identical to S and thus also identical the target layer C. S. according to Lemma 2.1
With this definition, we get (N (x))) , my (Nre) (c (CU)) (x))) - b/ =
(1) (MiS J +x+b) -my?s " : *x + bl I eym/Q2 based our assumption ø. =(1) (1)
(1)
since the input
Σ 73 W) *x S Q1.
follows that
S(x) (x) [ Sm)( S max S(xx); Sm)x))
(6)
1.x
max 7/2
Σ
iip
(2)
-my ( (Nrc)) (ces) (x)) - my (Ney) (c(i))
-b]
(7)
J.P
Q2
Φ (Nr1)
(ca) (x)) my (NrW) (cwi)) -bl x
Q2
max Jx
c
(8)
my
my
Q2
A.5 PROOF OF THM. 2.5
Statement (Thm. 2.5 main manuscript). Let the the source network S consist of L consecutive random convolutional layers (with linear activation functions). Then the parameters the normaliza- tion layers can be adjusted with high probability such that given target convolutional layer can be represented exactly Ak dim(k .... k k; 2 0 and (ii) Σ ai 2 clcodim(kk,... k..,,K)) and (iii) 2 for all source layers E [L].
Proof. We will prove this statement by mathematical induction. The base case is covered by Thm. 2.2
with two source networks.
We want show that for any target network can solve with high probability
ΣII
1 Thh-ig 7h = Wt.I
(10)
14

---

Published as a conference paper at ICLR 2024
we can always eliminate the outer (L) 7 and reformulate our problem
As in the derivation of Thm. 2.2
mJJ
WL.J (D)
W WJ 1-.11-100 1--1--18- 197
II
111-111 19 19
!))
(1)
(11)
Wt
1=1
1=2
such that
Σ
miJ
11) 11
=0
(12)
I=1
with respect to tensor M = (mIJ) that depends on flattened index set with indicees I and J that correspond to index combinations (I1...., LL I1. 9L) and pivotal elements Wt,Jz whose indicees are signified with *.
Induction hypothesis: Assume that L 1 layers can represent any target network of the stated dimensions in the theorem. We furthermore assume that
L-1
L-1
(1)
71 =0
(13)
1=
be solved for a full rank M.
Induction step: Our goal to show that there exists a nontrivial solution to the larger system
MILI
7
!1)
-
(14)
To do that, we derive a tensor of reduced rank = (brJ) such that
11.
(L)
bI. = 0
(15)
T2
is solvable and
L
Σ II.I
MI
7
(1)
(16)
[=1
Essentially, B helps us to decompose the original problem two solvable smaller problems. The first one is linear and therefore feasible if B has full rank and the second one is covered by the induction hypothesis.
To derive B, let us distinguish two complementary subsets of all possible ē = Et a constraints. These index subsets are defined S and S. that SUS. [é]. The sizes correspond to the last layer width S = cτ. and the number of equations that can be solved based on our induction hypothesis, i.e., [S_
CL.
Solving Eq. 155 is only possible if the nullspace ker( 2 has a nonzero dimension. Furthermore, solving only ey equations must imply that the remaining č ez equations are automatically fulfilled. Thus, we require the columns of B to be linearly dependent. Concretely, there must exist scalars X such that
b1180
Σ
Combining this with Eq. (6). we obtain the following system of equations
L-1
Σ mi 18.
II
71
Σ
m
! 1
(17)
1=1
SES
or, equivalently,
L-1
Σ
m1,1s0 Σ
Th
O.
(18)
#ES
1=1
15

---

Published as a conference paper at ICLR 2024
If there exist constants 91s, (mJ - M1,,)) then the equation above becomes solvable according to the induction hypothesis. But do there exist A such that the right hand side varies only I and s.? In fact, Ass, also solves a linear system of equations with exactly cr. fē cz)) constraints corresponding to the indicees 7. and 8c- This can be easily derived by eliminating It for instance, by establishing mi, Is. mi, Is. -- Ass. (m Is) Solving this system leads us to define IIs., which enables us to solve Eg. 18 based on the induction hypothesis. Given (1) I1 71,-
have also identified B based Eq. 16 and finally solve Eq. 15 for Ei-=1 75,
(2)
Finally, note that all of relevant matrices are invertible, since they have sufficient random elements. This can also be shown rigorously in the other proofs by finding an exemplary assignment the weight tensors that is invertible.
We thus have shown that can solve the induction step, which concludes the proof.
16


Reviews:
[{"review_id": "bkCpJG32R5", "reviewer": "Reviewer_DqFm", "summary": "The paper provides a proof that a convolutional multi-layer perceptron with batch normalization is an universal function approximator even when only the batchnorm parameters are trainable and everything else is fixed to its random initialization.\nThe claim is proved by providing a practical construction for a number of common activation functions and parameter random distributions.\n\nMinimum model widths and depths are provided for the task of reproducing an arbitrary convolutional MLP.\n\nThe approach is validated by experiments on image classification of the CIFAR10 and CIFAR100 datasets.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Interesting theoretical contribution.", "weaknesses": "Unclear practical relevance. The contribution is marginal compared to known results about approximation with models with random fixed parameters.", "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": "", "extra_scores": {}}, {"review_id": "RGrTvNDh0e", "reviewer": "Reviewer_Zja7", "summary": "They provide explanation for the normalization by proving that training normalization layers alone is already sufficient for universal function approximation if the number of available, potentially random features matches or exceeds the weight parameters of the target networks that can be expressed.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1- The effectiveness has been well supported by experiments.\n\n2- Well organized and clearly written.\n\n3- The paper is appropriately placed into contemporary literature.", "weaknesses": "I read the whole paper excluding the appendix, I acknowledge the importance of their study and appreciate the detailed information.", "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": "", "extra_scores": {}}, {"review_id": "OM7VIKqXEz", "reviewer": "Reviewer_pcEF", "summary": "The paper shows that, under certain conditions, training just the batch normalization (BN) parameters is enough to make a CNN a universal function approximator.", "questions": "-", "limitations": "", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper practices experimental method really well (has hypothesis, describes experiments and shows results).", "weaknesses": "The work describes BN as a subset of a Layer Normalization (LN).\nI'd note that they are both normalization layers, but BN is NOT a type of LN.\n(I'm effectively rejecting the paper because it needs to be rewritten based on this)\n\nBN, LN, GroupNorm, etc are all normalization layers, the only difference is the dimension along which normalization is done; GroupNorm (https://arxiv.org/abs/1803.08494) paper has a pictorial depiction of this.\nFurthermore, given BN aggregates statistics across samples, the neural network (NN) output of BN changes if the set of images changes; during training this makes a NN with BN a statistical operator. LN operates within a sample; the NN output does NOT change depending on input samples; during training this makes a NN with LN a function (not statistical). The Online Normalization paper (https://arxiv.org/abs/1905.05894) does a good job talking about this.\n\n\n\n\n- Reference are broken (there are things like \"Theorem ??\" in the paper).\n- Paper's experiments are really small scale for modern Deep learning leaving the reader wondering if they will scale.", "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": "", "extra_scores": {}}, {"review_id": "QS6rtlFPds", "reviewer": "Reviewer_9YBa", "summary": "This paper explores the role of normalization techniques, particularly Batch Normalization (BN), in deep convolutional neural networks (CNNs). The authors provide a theoretical analysis to demonstrate that training normalization layers alone is adequate for universal function approximation, assuming a sufficient number of random features. This result applies to various CNN architectures, including those with or without residual connections and different activation functions, such as ReLUs. The authors also explain how this theory can elucidate the depth-width trade-off in network design and the empirical observation that disabling neurons can be beneficial.", "questions": "- In the introduction, I'm a bit confused about the normalization being explored in this paper. The title mentions batch normalization, but the statement \"we delve into the role of layer normalization\" suggests layer normalization. Is this a typo?\n\n- I'm puzzled by the assertion in Section 2 regarding the existence of $f_t$, which the author claims is due to the universal function approximation. Perhaps the author meant to refer to the Universal Approximation Theorem. However, such approximations in neural networks are typically conditional. Has the author considered these conditions? Generally, these conditions are not mild and are idealized. Does this affect the theory presented in this paper? The author should provide an explanation and discussion on this.\n\n- I'm not entirely sure why throughout the paper, normalization is reduced to just a linear transformation and shift, i.e., $\\gamma \\mathbf{h} + \\beta$. This includes batch norm, layer norm, instance norm, etc. They all have this form, so is their significance solely in the learnable parameters $\\gamma$ and $\\beta$? Of course, I understand that $[(x - \\mu) / \\sigma] \\times \\gamma + \\beta$ can be equivalent to $\\gamma \\mathbf{h} + \\beta$\" in the end, but why emphasize batch normalization in the title? Where does \"batch\" come into play?\n\n- Can the analysis apply to the existing advanced batch normalization improvements like IEBN [1] and SwitchNorm [2]. These missing works should be considered and added to the related works or analysis.\n\n- The author needs to clarify the above questions. If these issues are addressed, I will consider these clarifications along with feedback from other reviewers in deciding whether to raise my score.\n\n\n[1] Instance Enhancement Batch Normalization: An Adaptive Regulator of Batch Noise, AAAI\n\n[2] Differentiable Learning-to-Normalize via Switchable Normalization, ICLR", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a solid theoretical foundation for its claims, offering mathematical proofs and a well-structured argument.\n\n- This paper is written in a clear and easily comprehensible manner, making it easy for readers to follow.", "weaknesses": "See Questions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)