Abstract
Recent empirical work has shown that tuning only the normalization layers of a frozen, randomly initialized network can yield surprisingly high performance. This paper provides the first theoretical foundation for this phenomenon, proving that a frozen random network can perfectly mimic any smaller target network by adjusting only its "scale and shift" parameters. We demonstrate that through specific architectural constructions, such as wide layers or skip connections, these simple affine transformations can effectively re-weight random features to reconstruct complex target functions.
Introduction
In modern deep learning, the paradigm has shifted from training models from scratch to fine-tuning specific components of massive, pre-trained architectures. A striking discovery by Frankle et al. (2020) revealed that even with completely random, frozen weights, training only the Batch Normalization (BN) parameters allows models to achieve high accuracy on standard benchmarks like CIFAR-10.
This is theoretically puzzling because normalization layers are mathematically simple: they merely scale ($\gamma$) and shift ($\beta$) the output of a neuron. This paper addresses the fundamental question: How can these simple transformations "learn" complex features when the underlying feature-extracting weights are fixed at random values?
Methods
The authors employ a constructive proof approach to show how to set the $\gamma$ and $\beta$ parameters of a frozen network to achieve functional equivalence with a specific "target" network.
Key methodological components include:
- Wide Reconstructions: A 2-layer random network with width $d^2$ can exactly replicate a 1-layer target network of width $d$.
- Deep Reconstructions: By utilizing skip connections, the authors prove a trade-off between width and depth. A deeper random network can mimic a target network even if its width is significantly smaller, closer to the target's original width.
- Linearization Trick: The proofs rely on setting shift parameters ($\beta$) high enough to push ReLU activations into their linear regime, effectively transforming the first layer of a two-layer block into a tunable linear operator.
- Khatri-Rao Products: The mathematical core involves the invertibility of the Khatri-Rao product (a column-wise Kronecker product) of random matrices. For random weights, the system of equations required to match target weights is almost certainly solvable.
Key Insights and Results
The "Aha" Moment
Tuning the diagonal scaling matrix in a normalization layer is equivalent to selecting a specific linear combination of the columns of the preceding random weight matrix. Because the weights are random, they serve as a high-dimensional basis that can be recombined to form nearly any desired transformation.
Width-Depth and Sparsity
- Exact Reconstruction: A randomly initialized ReLU network of depth $2l$ and width $d^2$ can recover any target network of depth $l$ and width $d$ with probability 1.
- Efficiency: If the target network has low-rank weight matrices (rank $r$), the frozen network only requires a width of $O(dr)$.
- Sparse Robustness: The expressive power holds even if the random weights are heavily sparsified (e.g., only $O(\sqrt{\log d / d})$ entries remain), suggesting that normalization layers can re-weight existing connections even in highly pruned networks.
Experimental Validation
Numerical experiments using a synthetic teacher-student setup confirmed these theories. The authors' "Constructive" algorithm—setting parameters based on their proof—achieved near-zero loss instantly, significantly outperforming standard SGD optimization on the same parameters.
Discussion and Limitations
While this work establishes the expressivity of normalization layers, it distinguishes between existence and optimization. While a solution is proven to exist, standard algorithms like SGD may not always find it efficiently. Furthermore, the number of tunable parameters in the theoretical limit ($d^2$) is comparable to the original weight matrix, meaning the "efficiency" is architectural rather than a reduction in total trainable variables. Future work aims to extend these proofs to Convolutional Neural Networks and Transformers.
Summary updated