Identity Crisis: Memorization and Generalization Under Extreme Overparameterization
Authors: Chiyuan Zhang
Samy Bengio
Moritz Hardt
Michael C. Mozer
Yoram Singer
Venue:  (2020)
Keywords: Generalization
Memorization
Understanding
Inductive Bias

Abstract: We study the interplay between memorization and generalization of
overparameterized networks in the extreme case of a single training example and an identity-mapping task. We examine fully-connected and convolutional networks (FCN and CNN), both linear and nonlinear, initialized randomly and then trained to minimize the reconstruction error. The trained networks stereotypically take one of two forms: the constant function (memorization) and the identity function (generalization).
We formally characterize generalization in single-layer FCNs and CNNs.
We show empirically that different architectures exhibit strikingly different inductive biases.
For example, CNNs of up to 10 layers are able to generalize
from a single example, whereas FCNs cannot learn the identity function reliably from 60k examples. Deeper CNNs often fail, but nonetheless do astonishing work to memorize the training output: because CNN biases are location invariant, the model must progressively grow an output pattern from the image boundaries via the coordination of many layers. Our work helps to quantify and visualize the sensitivity of inductive biases to architectural choices such as depth, kernel width, and number of channels.


Published as a conference paper at ICLR 2020
IDENTITY CRISIS: MEMORIZATION AND GENERAL- IZATION UNDER EXTREME OVERPARAMETERIZATION
Chiyuan Zhang & Samy Bengio Google Research, Brain Team Mountain View, CA 94043, USA {chiyuan, bengi b www.ggoooo.ooooooooooooooooooo.. com
Moritz Hardt
University of California, Berkeley
Berkeley, CA 94720, USA
hardt&@berkeleey.cem
Michael C. Mozer
Yoram Singer
Google Research, Brain Team Mountain View, CA 94043, USA
Princeton University Princeton, NJ 08544, USA y se@princetoon.er
mcmozer@google. com
ABSTRACT
We study the interplay between memorization and generalization of overparame- terized networks the extreme case of a single training example and an identity- mapping task. We examine fully-connected and convolutional networks (FCN and CNN), both linear and nonlinear, initialized randomly and then trained to mini- mize the reconstruction emror. The trained networks stereotypically take of two forms: the constant function (memorization) and the identity function (gen- eralization). We formally characterize generalization in single-layer FCNs and CNNs. We show empirically that different architectures exhibit strikingly differ- ent inductive biases. For example, CNNs of up 10 layers are able generalize from a single example, whereas FCNs cannot learn the identity function reliably from 60k examples. Deeper CNNs often fail, but nonetheless to memorize the training output: because CNN biases are location invariant, the model must progressively grow an output pattern from the image boundaries via the coordination of many layers. Our work helps to quantify and visualize the sensitivity of inductive biases to architectural choices such as depth, kernel width, and number of channels.
astonishing work
INTRODUCTION
The remarkable empirical success of deep neural networks is often attributed to the availability of large data sets for training. However, sample size does not provide a comprehensive rationale since complex models often outperform simple ones on a given data set, even when the model size exceeds the number of training examples.
What form of inductive bias leads to better generalization performance from highly overparameter- ized models? Numerous theoretical and empirical studies of inductive bias in deep learning have been conducted in recent years (Dziugaite & Roy| 2016 Kawaguchi et al.] 2017 Bartlett et al.)
2017
Neyshabur al., 2017, Liang et al.) 2017 Neyshabur et al. [2018] Arora al. 2018 Zhou
et al.
2019) but these postmortem analyses do not identify the root source of the bias.
One cult belief among researchers is that gradient- optimization methods provide an implicit bias toward simple solutions (Neyshabur et al., 2014, Soudry et al. 2018)) [haah et al. 2018; Arora
al. 2019). However, when a network is sufficienlly large (e.g., the number of hidden units each layer is polynomial in the input dimension and the number of training examples), then under some mild assumptions, gradient methods are guaranteed fit the training set perfectly (Allen-Zhu et al.) 201 8b. Du et al. 2018a Zou et al. 2018). These results do not distinguish model trained on a data distribution with strong statistical regularities from one trained on the same inputs but with randomly shuffled labels. Although the former model might achieve good generalization, the latter can only memorize the training labels. Consequently, these analyses do not tell the whole story on the question of inductive bias.

---

Published as a conference paper at ICLR 2020
7
5
3
3
4
Input
20-layer
7
9
5
3
8
4
CNN
10-layer
7
9
5
8
3
4
ReLU FCN
1laayer
7
9
5
3
3
4
linear model
Figure 1: Predictions of three architectures trained on the identity mapping task with 60k MNIST examples. The red dashed line separates 3 training examples from the test examples.
Another line of research characterizes sufficient conditions on the input and label distribution that guarantee generalization from a trained network. These conditions range from linear separabil- ity (Brutzkus et al. 2018) to compact structures (Li & Liang 2018). While very promising, this direction has thus far identified only structures that can be solved by linear or nearest neighbor classifiers over the original input space. The fact that in many applications deep neural networks networks.
significantly outperform these simpler models reveals a gap in our understanding of deep neural
As a formal understanding of inductive bias in deep networks has been elusive, we conduct a novel exploration in highly restrictive setting that admits visualization and quantification of in- ductive bias, allowing us to compare variations in architecture, optimization procedure, initialization scheme, and hyperparameters. The particular task investigate is learning identity mapping in regression setting. The identity mapping is interesting for four reasons. First, it imposes a structural regularity between the input and output, the type of regularity that could in principle lead system- atic generalization (He et al. 2016 Hardt & Ma (017). Second, it requires that every input feature is transmitted to the output and thus provides a sensitive indicator of whether a model succeeds in passing activations (and gradients) between inputs and outputs. Third, conditional image generation popular task in the literature (e.g., MMrza& & Osindero [014] Ledig et al.) (0177;; an identity mapping is the simplest form of such generative process. Fourth, and perhaps most importantly, it admits detailed analysis and visualization of model behaviors and hidden representations.
Consider networks trained on the identity task with 60k MNIST digits. Although only digit images are presented during the training, one might expect the strong regularity of the task to lead to good generalization to images other than digits. Figure I compares three different architectures. The top row shows various input patterns, and the next three rows are outputs from a 20-layer convolutional net (CNN), 10-layer fully connected net (FCN) with rectified-ling linear unit (ReLU) activation func- tions, and a I-layer FCN. The I-layer FCN amounts to a convex optimization problem with infinitely many solutions, however gradient decent converges a unique closed-form solution. All nets per- form well on the training set (first three columns) and transfer well to novel digits and digit blends (columns 4-6). Yet, outside of the hull of hand-printed digits, only the CNN discovers a reasonably good approximation to the identity function.
Figure D reffects architecture-specife inductive bias that persists even with 60k training examples. Despite this persistence, a model's intrinsic bias is more likely to be revealed with a smaller training set. In this paper, we push this argument the limit by studying learning with a single training example. Although models are free to reveal their natural proclivities in this maximally overparam- eterized regime, our initial intuition was that single example would be uninteresting as models would be algebraically equivalent to the constant function (e.g., via biases on output units). Further, it seemed inconceivable that inductive biases would be sufficiently strong to learn a mapping close to the identity. Unexpectedly, our experiments show that model behavior is subtle and architecture dependent. In a broad set of experiments, we highlight model characteristics iitrrtteristess-inncninnnn depth, ini- tialization, and hyperparameters- that determine where a model lands the continuum between memorization (learning a constant function) and generalization (learning the identity function). The simplicity of the training scenario permits rich characterization of inductive biases.
2

---

Published as a conference paper at ICLR 2020
7
2
Input
l-ayyer
7
linear
2-yayer
7
7
lincar
2-layer
7
7
7
ReLU
6-yayer
7
7
7
7
7
7
7
lineur
6-layer
7
7
7
7
7
7
7
7
7
7
ReLU
Figure 2: Visualization of the outputs of fully connected networks trained on a single exam- ple. The first row shows the single training example (7) and a set of evaluation images consisting of a linear combination of two digits, random digits from MNIST test set, random images from Fashion MNIST, and some algorithmically generated image patterns. Each row below indicates an architecture and the output from that architecture for given input.
2 RELATED WORK
The consequences overparameterized models in deep learning have been extensively studied in recently years, the optimization landscape and convergence of SGD (Allen-Zhu et al.) 2018b Du et al. 2018a b Bassily et al. 2018 Zou et al., 2018 Oymak & Soltanolkotabi 2018). as well the generalization guarantees under stronger structural assumptions of the data (Li & Liang. 2018 Brutzkus et al. 2018 Allen-Zhu et al.,
20)8 Another line of related work is the study of
the implicit regularization effects of SGD on training overparameteriize models (Neyshabur al.
2014 Zhang et al. 2017 Soudry et al. 2018 Shah et al. 2018 Arora et al. 2019)..
The traits of memorization in learning are also explicitly studied from various perspectives such as prioritizing learming of simple patterns (Arpit et al. 2017) or perfect interpolation of the training set (Belkin al. 2018 Feldman 2019). More recently, coincidentally with the writing of this paper, Radhakrishnan et al. (2018) reported on the effects of the downsampling operator in convolutional auto-encoders on image memorization. Their empirical framework is similar to ours, fitting CNNs to the autoregression problem with few training examples. We focus on investigating the general inductive bias in the extreme overparameteriiation case, and study a broader range of network types without enforcing a bottleneck in the architectures.
3 EXPERIMENTS
We explore progression of models: linear convex models, linear non-convex models (with multiple linear layers), fully-connected multilayered architectures with nonlinearities, and finally the case of greatest practical importance, fully convolutional networks. In all architectures study, ensure that there is a simple realization of the identity function (see Appendix B). We train networks by minimizing the mean squared error using standard gradient descent.
3.1 FULLY CONNECTED NETWORKS
Figure 2 shows examples of predictions from multi-layer fully connected networks. Infinitely many solutions exist for all models under this extreme over-parameterization. and the figure shows that all the models fit the training example perfectly. However, on new test examples, contrasting behaviors are observed between shallow and deep networks. In particular, deeper models bias toward predict- ing constant output, whereas shallower networks tend to predict random white noises on unseen inputs. The random predictions can characterized as follows (proof in Appendix
Theorem 1. A one-layer fully connected network, when trained with gradient descent single training example I,, converges to a solution that makes the following prediction on a test example x:
f(x) (1) RI (x),
3

---

Published as a conference paper at ICLR 2020
Input
7
7
4
9
1-layer
7
7
4
9
3-layer
7
7
4
9
5-layer
7
7
4 4 7
9
7-layer
7
7
9
9-layer
7
11-layer
7
7
12-layer
7
7
14-layer
7
15-layer
7
16-layer
7
18-layer
7
7
19-layer
7
7
7
20-layer
7
7
7 7
7
7
7
7
7
7
Visualization of predictions from CNNs trained on single example. The first row shows the single training example (7) and set of test inputs. Each row below shows the output of CNN whose depth is indicated to the left of the row. The hidden layers of the CNN consist of 5 convolution filters organized as 128 channels.
Figure 3:
where = [I] (z) decomposes x into orthogonal components that are parallel and perpen- dicular to the training example î; respective. R. is a random matrix from the network initialization, independent of the training data.
For test examples similar to the training example-i.e ie., where II (x) dominates II [x) (x))((t))t the out- puts resemble the training output; on the other hand, for test examples that are not highly correlated to the training example, II, (x) dominates and the outputs looks like white noise due to the ran- dom projection by R. The behavior can be empirically verified from the second Specifically, the first test example is a mixture of the training and an unseen test example, and the corresponding output
in Figure 2
mixture of white noise and the training output. For the remaining test examples, the outputs appear random.
Although Theorem [ characterizes only the l-layer linear case, the empirical results in Figure suggest that shallow (2 layer) networks tend to have this inductive bias. However, this inductive bias does not miraculously obtain good generalization: the trained model fails learn either the identity or the constant function. Specifically, it predicts well in the vicinity (measured by correlations) of the training example ă, but further away its predictions are random. In particular, when the test example is orthogonal to f, the prediction is completely random. In deeper (6 layer) nets, the deviations from the identity function take on a quite different characteristic form.
Interestingly, deeper linear networks behave more like deeper ReLU networks, with strong bias towards a constant function that maps any input to the single training output. A multilayer linear network with no hidden-layer bottleneck has essentially the same representational power 1-layer linear network, but gradient descent produces different learning dynamics that alter the inductive biases. See Appendix
B for more results and analysis on FCNs.

---

Published as a conference paper at ICLR 2020
correlation to constant function
correlation to Identity function
1.0
1.0
3
ConvNRt Depths
5
0.8
9
9
11
11
12
12
14
14
16
16
18
18
20
0.0
0.0
0.2
0.3
0.5
0.6
0.8
0.9
0.0
0.2
0.3
0.5
0.6
0.8
0.9
train-test
correlation
Figure 4: Predictions of CNNs on test examples different angles the training image. The horizontal axis shows the train-test correlation, while the vertical axis indicate the number of hidden layers for the CNNs being evaluated. The heatmap shows the similarity (measured in correlation) between the model prediction and the reference function (the constant the identity function).
3.2 CONVOLUTIONAL NETWORKS
We next study the inductive bias of convolutional neural networks with ReLU activation functions. Figure 3 shows predictions on various test patterns obtained by training CNNs of varying depths. Compared to FCNs, CNNs have strong structural constraints that limit the receptive field of each neuron to spatially local neighborhood and the weights are tied and being used across the spatial array. These two constraints match the structure of the identity target function. (See Appendix B3. for an example of constructing the identity function with CNNs.) Similar to the fully connected case, for one-layer CNN, can bound the error follows (proof in Appendix D).
Theorem 2. A one-layer convolutional neural network can learn the identity map from single training example with the mean squared error over all output pixels bounded as
[m(m/c- -r) (
(m(mjc-r))
MSE S Ō
C
where m. the number of network parameters, C is the number of channels in the image, and r S m/c is the rank of the subspace formed by the span of the local input patches.
The eтrоr grows with m, the number of parameters in the network. For example, learning CNNs with larger receptive field sizes will be harder. Even though the bound seems to decrease with more (input and output) channels in the image, note that the number of channels C' also contributes to the number of parameters (m C²), so there is a trade-off. Unlike typical generalization bound that decays with number of i.i.d. training examples, we have only one training example here, and the key quantity that reduces the bound the rank r of the subspace formed by the local image patches. The size of the training image implicitly affects bounds larger image generates more image patches. Note the rank r also heavily depends on the contents of the training image. For example, simply padding the image with zeros all boundaries will not reduce the bound. With enough linearly independent image patches, the subspace becomes full rank r = m/c, and learning of the global identity map is guaranteed.
The theorem guarantees only the one-layer case. Empirically-as shown in Figure CNNs with depth up-to-5 layers learn fairly accurate approximation the identity function, with the exception of a few artifacts at the boundaries. For a quantitative evaluation, we measure the performance by calculating the correlation (See Appendix J for the results in MSE.) to two reference functions: the identity function and the constant function that maps every input to the training point æ. To examine how model's response varies with similarity to the training image, we generate test images having correlation p E [o. 1] to the training image by: (1) sampling an image with random pixels, (2) adding at to the image, picking a such that the correlation with is p; (3) renormalizing the image to be of the same norm ã. For p O. the test images are orthogonal to é, whereas for 1, the test images equal f. The results for CNNs of different depths are shown in Figure 4 The quantitative findings consistent with the visualizations: shallow CNNs are able to learn the identity function from only one training example; very deep CNNs bias towards the constant function; and CNNs of intermediate depth correlate well with neither the identity nor the constant function. However,
5

---

Published as a conference paper at ICLR 2020
Figure 5: Illustration of the collapse of predie- tive power as function of layer's depth. Error rate is measured by using the representations com- puted at each layer to simple averaging based classifier on the MNIST test set. The error rate at each layer is plotted for number of trained CNNs of different depth. The thick red line shows the curve of an untrained 20- 20-layer CNN for reference.
unlike FCNs that produce white-noise-like predictions, from Figure 3 CNNs of intermediate depth behave like edge detectors.
To evaluate how much information is lost in the intermediate layers, we use the following simple criterion to assess the representation in each layer. We feed each image in the MNIST dataset through a network trained on our single example. We collect the representations at a given layer and perform simple similarity-weighee we predict its class as a weighted average of the (one hot) label vector of each example zy from the MNIST training set, where the weight the inner-produc of z; and zz--
classification. For each example x, from the MNIST test set,
This metric does not quantify how much information is preserved as the image representation prop- agates through the layers, because the representation could still be maintained yet not captured by the simple correlation weeighheee classifier. It nonetheless provides a simple metric for exploring the (identity) mapping: using the input image as the baseline, a layer represents the identity function, then the representation at that layer would obtain a similar error rate when using the input represen- tation; on the other hand, a layer degenerates into the constant function, then the corresponding representation would have error rate close to random guessing of the label. The results in Figure 5 The error curve for a randomly initialized 20-layer CNN is shown as reference: at random initialization, the smoothing effect renders the representations beyond the sixth layer un- useful for the averaging-base indicates loss and then recovery of the information present in the input. Trained networks try to recover the washed out intermediate layer representations as means to link the input and the output layer. However, the depth too large, the network tries infer input-oulput relations using partial information, resulting in models that behave like edge detectors. Finally, for the case of 20 layers, the curve shows that the bottom few layers do get small improvements in error rate comparing to random initialization, but the big gap between the input and output layer drives the network to learn the constant function instead. On first sight, this deems to underscore a vanishing gradient prob- lem, but Figure D reveals that given sufficient number of training examples, 20-layer CNN can still learn the identity map. See also Appendix G for further discussions on vanishing gradients. Since CNNs preserve spatial structure, layers. The visualization results, described in Appendix F are consistent with the aforementioned observations.
plotted
classifier. After training, the concave nonmonotonicity in the curves
also visualize information loss in the intermediate
3.3 ROBUSTNESS TO CHANGES INPUT SCALE
Whether a relatively shallow CNN learns the identity function from single training example or relatively deep CNN learns the constant function, both outcomes reflect an inductive bias because the training objective never explicitly mandates the model learn one structure or another. The spatial structure of CNNs enables additional analyses of the encoding induced by the learned function. In particular, we examined how changing the size of the input by scaling the dimensions of the spatial map affects the model predictions. Figure [ depicts the predictions of 5-layer CNN trained on a 28 x 28 image and tested on 7 x 7 and 1T2 112 images. Although the learned identity map generally holds up against larger-than than-trained input, the identity map is disturbed on smaller-than: trained inputs. See Appendix H. for a comprehensive description the results. Note that CNNs capable of encoding the identity function for arbitrary input and filter sizes (Appendix B.3
Figure shows the predictions on the rescaled input patterns of Figure 6 by a 20-layer CNN that has learned the constant function a 28 28 image. The learned constant map holds up over smaller range of input sizes than the learned identity map in a 5-layer CNN. It is nonetheless interesting to smooth changes as the input size increases to reveal the network's 's own notion of "7", clearly

---

Published as a conference paper at ICLR 2020
C
an
Figure 6: Visualization of a 5-layer CNN on test images different sizes. The two subfigures
show the results 7 inputs and 112 x 112 inputs, respectively.
P
P
P
P
P
P
36
/
/
/
/
40
7
7
7
7
7
7
7 7
7
7 7 7 7
7 7
7
7
7
7 7
112
Figure 7: Visualization of the predictions of 20-layer CNN on test images of different sizes (indicated by the number on each row). The input patterns are the same as in Figure ccoosttocen in different resolutions), which are not shown for brevity.
defined with respect to the corners of the input map (Figure 21 in Appendix H reveals interesting details on how the patterns progressively grow from image boundaries in intermediate layers). We performed additional experiments to directly feed test images to the upper subnet, which reveals more about the generative process by which the net synthesizes constant output (Appendix H).
3.4 VARYING OTHER FACTORS DURING TRAINING
We studied variety of common hyperparameters. including image dimensions, convolutional filter dimensions, number of kernels, weight initialization scheme, and the choice of gradient-based opti- mizer. With highly overparameterized networks, training converges to zero error for wide range of hyperparameters. Within the models that all perform optimally on the training set, we now address how the particular hyperparameter settings affect the inductive bias. We briefly present some of the most interesting observations here; please refer to Appendix for the full results and analyses.
Size of training image. Figure g shows, for varying training-imaee size, the mean correlation to the constant and the identity function different depths within the network. The training examples are resized versions of the same image. The bias toward the constant function at a given depth increases with smaller training images. This finding makes sense considering that smaller images provide fewer pixel-to-pin mapping constraints, which is aligned with Theorem
Size of convolution filters. Figure 9 illustrates the inductive bias with convolution filter size vary- ing from 5 5 to 57 x 57. Predictions become blurrier the filter size grows. With extremely large filters that cover the entire input array, CNNs exhibit a strong bias towards the constant function.
Avg correlation to constant
Avg correlation to identity
1.-
7x7
1.0
7x7
Figure 8: Comparing bias towards constant and identity when trained with different image sizes. The x- axis is the depth of the CNNs, while the y-axis is the mean correlation (av- erage of each row from the heatmaps like in Figure 4) Each curve cor- responds to training with different image size.
14x14
14x14
0.9
0.9
0.8
0.8
0.7
0.7
ConvNet Depth
ConvNet Depth

---

Published as a conference paper at ICLR 2020
7
9
9
Input
7
9
6
9
7
7
5
7
13x13
7
7
3
7
25x25
7
7
7
7
7
57x57
Figure 9: Visualizing the predictions from 5-layer CNNs with various filter sizes. The first row shows the single training example (7) and set of test inputs. Each row below shows the output of a CNN whose filter size is indicated by the number on the left. See Appendix forr more results.
Empui
7
7
S
9
Imput 7
2
O
7
?
5
7
7
7
7
7
7
7
7
7 7 7
7
7
7
178
7
7
5
7
138
7
7
7
7
7
7
7
7
7
7
7 7
7
7
7
S
?
7
7
7
7
7 7
7
7 7 7
(a) 5-layer
(b) 20-layer
Figure 10: Visualization of the predictions from CNNs for various number of hidden channels. The first shows single training example (7) and of test inputs. Each row below shows the output of CNNs differing in the number of channels. This number is indicated on the left of each row; for intermediate layers, the number specifies both the input and output channel count.
Because the training inputs are of size 28 x 28, a 29 x 29 filter size allows each neuron to see at least half of the spatial domain of the previous layer, assuming large boundary padding of the inputs. With 57 x 57 filters centered at any location within the image, each neuron sees the entire previous layer. This is also consistent with Theorem [ in which the error bound deteriorates the filter sizes increases. Note even with large filter, CNNs do not perform the same elementary computation as FCNs because the (shared) convolution filter is repeatedly applied throughout the spatial domain.
Number of channels. Appendix B.3 identity function for gray-scale inputs a straightforward construction. However, in practice the outcome of training may be quite different depending the channel count, shown in Figure 10)a). the one hand, the aggressively overparameterized network with 1024 channels (~~25M parame- ters per middle convolution layer) does not seem to suffer from overfitting. On the other hand, the results with three channels often lose content in the image center. The problem is not underfitting as the network reconstructs the training image (first column) correctly.
shows that in principle two channels suffice to encode the
A potential reason why 3-channel CNNs do not learn the identity map well might be poor initial- ization when there very few channels (Frankle & Carbin 2019). This issue is demonstrated in Figure 29 of Appendix[]] [I] Our study of training with different initialization schemes indeed con- firms that the random initial conditions have a big impact on the inductive bias (Appendix [
Figure b) shows the case for 20-layer CNNs. Surprisingly, having an order of magnitude more feature channels every layer does seem to help much making the information flow through layers, as the network still learns to ignore the inputs and construct a constant output.
4 CONCLUSIONS
We presented an systematic study the extreme case overparameterizztion when learning from single example. We investigated the interplay between memorization and generalization in deep
8

---

Published as a conference paper at ICLR 2020
neural networks. By restricting the learning task to the identity function, sidestepped issues such as the underlying optimal Bayes error of the problem and the approximation error of the hy- pothesis classes. This choice also facilitated rich visualization and intuitive interpretation of the trained models. Under this setup, we investigated gradient- -hased learning procedures with explicit ceamorrzationngeneralaaaate characterization. Our results indicate that different architectures hibit vastly different inductive bias towards memorization and generalization.
For future work, we plan to extend the study to other domains and neural network architectures, like natural language processing and recurrent neural networks, and aim for more qualitative relationship between the inductive bias and various architecture configurations.
ACKNOWLEDGMENTS
We would like thank Kunal Talwar, Hanie Sedghi, and Rong Ge for helpful discussions.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. CoRR, 1811.00 1.04918. 2018 8a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via Over- Parameterization. CoRR,
2018b.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. CoRR, arXiv:1802.0522 2018.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:1905.13655 2019.
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxin- der S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization deep networks. In International Conference on Machine Learning. 2017.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of SGD in non-convex over-parametrized learning. CoRR, arXiv: 18 111..2564, 2018.
Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for clas- sification and regression rules that interpolate. In Advances in Neural Information Processing Systems, 2018.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In ICLR, 2018
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. CoRR, 111i::1811.00804 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. CoRR, arXiv: 110.0004,, 2018b.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(du):2121-2155 201
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In UAI, 2016.
Vitaly Feldman. Does learning require memorization? short tale about long tail. arXiv preprint /9Xi://906602271. 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICI.R, 2019.

---

Published as a conference paper at ICLR 2020
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
Alex Graves. Generating sequences with recurrent neural networks. arXiv: 1308v:1308.000 0850, 2013.
arXiv preprint
Moritz
Hardt and Tengyu Ma. Identity matters deep learning. 2017.
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, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645. Springer, 2016.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. CoRR, arXiv:1710.05466. 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Christian Ledig, Lucas Theis, Ferene Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al. Photo-realistic sin- gle image super-resolution using generative adversarial network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4681-46900, 2017.
Yuanzhi Li and Yingyu Liang. Learning overparameterrized neural networks via stochastic gradient descent on structured data. In NIPS, 2018.
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geome- try, and complexity of neural networks. CoRR, 1rXiv:1711.015300 2017.
Mehdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint 1rXiv:1411.1784 2014.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. CoRR, arXiv:1412.661 2014.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-BBaesian approach to Spectrally-Normalizee margin bounds for neural networks. In ICLR, 2018.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? CoRR, 1tti::1812.10000 2018.
Adityamarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Downsampling leads to im- age memorization in convolutional autoencoders. CoRR, 1iti:::811.11333. 2018.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions the nonlinear dy- namics of learning in deep linear neural networks. In International Conference Learning Representations, 2014.
Vatsal Shah, Anastasios Kyrillidis, and Sujay Sanghavi. Minimum norm solutions do not always generalize well for over- wee-parameterized problems. CoRR, 1XXv:1811.00055 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. Journal of Machine Learning Research, 19(70), 2018.
10

---

Published as a conference paper at ICLR 2020
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.088 144, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P Adams, and Peter Orbanz. Non-vacuous generalization bounds at the ImageNet scale: a PAC-Bayesian compression approach. In ICLR, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterizee deep ReLU networks. CoRR, arXiv: 181 1.08888, 2018.

---

Published as a conference paper at ICLR 2020
A EXPERIMENT DETAILS AND
We specify the experiment setups and the hyper-parameters here. Unless otherwise specified in each study (e.g. when we explicitly vary the number convolution channels), the hyper-parameters are set according to the default values here.
The main study is done with the MNIST dataset. It consists grayscale images of hand written digits of size 28 x 28. For training, randomly sample one digit from the training set (a digit '7') with fixed random seed. For testing, we use random images from the test set MNIST and Beshion-MNIST1
well algorithmically generated structured patterns and random images. The training and test images are normalized by mapping the pixel values in {0, 1,..,, 255} } to [0, 1]. and then standardize with the mean 0.1307 and standard deviation 0.3081 originally calculated on the (full) MNIST training set.
The models trained by minimizing the mean squared error (MSE) loss with vanilla SGD (base learning rate 0.01 and momentum 0.9). The learning rate is scheduled as stagewise constant that decays with a factor of 0.2 at the 30%, 60% and 80% of the total training steps (2,000,000). No weight decay is applied during training.
For neural network architectures, the rectified linear unit (ReLU) activation used for both fully connected networks (FCNs) and convolutional networks (CNNs). The input and output dimensions are decided by the data. The hidden dimensions for the FCNs are 2,048 by default. The CNNs use 5 x 5 kernels with stride 1 and padding 2, so that the geometry does not change after each convolution layer.
B REPRESENTATION OF THE IDENTITY FUNCTION USING DEEP NETWORKS
In this section, provide explicit constructions how common types of neural networks can represent the identity function. Those constructions are only proof for that the models in our study have the capacity represent the target function. There identity map for each network architecture, but we try to provide the most straightforward and explicit constructions. However, during our experiments, even when the SGD learns (approximately) the identity function, there is no evidence suggesting that it is encoding the functions in similar ways as described here. We put some mild constraints (e.g. no "bottleneck" in the hidden dimensions) to allow more straightforward realization of the identity function, but this by means asserts that networks violating those constraints cannot encode the identity function.
many different ways construct the
B. LINEAR MODELS
For one-layer linear network f(z = Wz, where W E Raxd setting W to the identity matrix will realize the identity function. For a multi-layer linear network f(x) (Ile We)x, we need to require that all the hidden dimensions are not smaller than the input dimension. In this case, simple concrete construction is to set each W₂ to an identity matrix.
B.2 MULTI-LAYER RELU NETWORKS
The ReLU activation function o-)) max(0,-) discards all the negative values. There are many ways one can encode the negative values and recover it after ReLU. We provide simple approach that uses hidden dimensions twice the input dimension. Consider a ReLU network with one hidden layer (x) WWa(Wia) where W2 E ddx2d W, 22dxd The idea to store the positive and negative part of x separately, and then re-construct. This can be achieved by setting
W1 (-r.). W₂ (la -la)
where Ia is the d-dimensional identity matrix. For the case of more than two layers, we can use the bottom layer to split the positive and negative part, and the top layer merge them back. All the intermediate layers can be set to 2d-dimensional identity matrix. Since the bottom layer encode all the responsives in non-negative values, the ReL.U in the middle layers will pass through.
12

---

Published as a conference paper at ICLR 2020
B.3 CONVOLUTIONAL NETWORKS
In particular, we consider 2D convolutional networks for data with the structure of multi-channel images. mini-batch of data usually formatted as four-dimensional tensor of the shape B x C' x H x W. where B is the batch size, C' the number of channels (e.g. RGB or feature channels for intermediate layer representations), A convolutional layer (ignoring the bias term) is parameterized with another four-dimensional ten- sor of the shape C C x и x Kw. where C is the number of output feature channels, и and Kw are convolutional kernel height and width, respectively. The convolutional kernel is applied at local Kи x Kw patches of the input tensor, with optional padding and striding.
and W are image height and width, respectively.
For one convolution layer to represent the identity function, we can use only the center slice of the kernel tensor and set all the other values to zero. Note it is very rare to use even numbers as kernel size, in which case the "center" of the kernel tensor is not well defined. When the kernel size is odd, we can set
Wechw = ={0
c h [Kn/2], w [Kw/2]
otherwise
By using only the center of the kernel, we essentially simulate a x 1 convolution, and encode local identity function for each (multi-channel) pixel.
For multi-layer convolutional networks with ReLU activation functions, the same idea as in multi- layer fully- fully-connected networks can be applied. Specifically, we ask for twice as many channels as the input channels for the hidden layers. At the bottom layer, separately the positive and negative part of the inputs, and reconstruct them at the top layer.
C PROOF OF THBOREM 1
Consider the I-layer linear model fw( = Wa, where E Rd and W E IRd Let 7 be the single training example. The training objective is to minimize the empirical risk i 1/2ll (w)) x1 The optimization problem is convex and well understood. Due overparameetrrizatin,, the solution of the empirical risk minimization is not unique. However, given randomly initialized weights W gradient descent obtains a unique global minimizer.
The gradient of the empirical risk is
òR
= (W - 1)aa
(3)
OW
Gradient descent with step sizes n7 and initialization weights 8 updates weights as
T
W = Wo Σ
(W I)2t
W + uy
where WT E Rd is vector decided via the accumulation in the optimization trajectory. Because of the form of the gradient, it is easy to see the solution found by gradient descent will always have such parameterization structure. Moreover, under this parameterization, unique minimizer exists that solves the equation
= fw(() W uu
via
á (I W
(4)
|001
Therefore, the global minimizer can be written as
(x) (Wo
úu )m:
TT
T
4 + w
+
|
13

---

Published as a conference paper at ICLR 2020
For the one-layer network case, the optimization problem is convex. Under standard conditions in convex optimization, gradient descent will converge to the global minimizer shown above.
We can easily verify that the red term is exactly the projection of x onto the training example å, while the blue term is the residual projection onto the orthogonal subspace.
D PROOF OF THEOREM 2
Lemma 1. Consider the linear model f(=) WTx, where x E RD, W E RR Let the training set be {11 (1)..,.)..... (IN, yN Assume the model is overparameterized (N S d) and there is no sample redundancy (rank of the data matrix is N). Fitling J()) by optimizing the square loss with
gradient descent on the training set converges to f(x) = W x, where
W = -- +X (XX (V XWW).
(5)
Wo E R is the random initialization of weights, X = (II,...,IIN) E RND and Y (Ui,..., (UI....UUN) Nxd are the matrices formed by the imputs and outputs, respectively.
Lemma 2. With the same notation of Lemmal 7 assume the model is underparameterized (N > d) and there is no feature redundancy (rank of the data matrix is d). Fitting f()) by optimizing the square loss with gradient descent on the training set converges to f(x) = W where
W = (XTx) XTY.
(6)
Proof of Theorem 2 Let & E RX"X be the single training image of size H x W. and C color channels. Let K w the convolution receptive field size, so weights of convolution filters can be parameterized via 4-dimensional tensor O E K x www.xxCK xCxC Let E be the collection of 2D coordinates and (.) E IR K Kw xC be the local patch of centered at the coordinate (i,j) E E. Note for our case the input and output are of the same shape, so the convolution stride is one, and E H x W.
the local patches from the input image that the convolutional filter is applied to,
The empirical risk of fitting & with one-layer convolution model can be written
R Σ Σ
(i fzyzk)² (b.))E k=
where O.:k E K Kw xC the subset of convolution weights corresponding to the k-th output channel. and figh is the pixel value coordinate (i.j) and channel k.
CASE 1 - overparameteriizatio:: E < KH x Kw x x C. Assumme the patches are linearly independent] with slight abuse of notatons, represent the empirical risk in matrix form with the
When two patches are identical, or more generally, when there is patch (7,3) E E, which can be written as linear combination of other patches:
Bay s.t.
P (t)
Σ Pey)e,(
Note because each local patch contains the target pixel: Lisk E (c), Ak E [C]. so for all & E [C], the same coefficients {ai} }or can be used to written Z.zz. as the same linear combination of the other (corresponding) pixels. Therefore, can find linearly independent basis for the patches and rewrite the fitting objectives with the basis.
14

---

Published as a conference paper at ICLR 2020
following matrices
W (0........ ...c) B(KEKWO)XC X = (..., (i) .)" ER(EI((KKKC))
=
kif1
Bisc 3
and apply Lemma | to obtain W. For test example æ, the prediction of the (i,j)-th (multi-channel) pixel is
W PTy((()) = (wo + +x (XXT) (x-XW9) (x- Pi5(z)
-WOT (I-XT (XXT) x) Pzz(2) Y (XXT))'XP:;(G)
Note we are learning the identity map, the (i..))-th row of the learning target matrix Y is the (multi-channel) pixel the (i,j)-th coordinate of é. This is exactly the center of the (i, patch Pay (.), i.e. the (i,j)-th row of the matrix X. As result, there is a linear projection ma- trix A E R KW)CCC that maps X to Y: XA = Y. So
W Po)(t> WOT II (i)( + (
where u1 = =XT(XXT)- is the linear operator that projects a vector into the subspace spanned by the rows of X, and 1 I - mT is the operator projecting into the orthogonal subspace.
To compute the prediction errors, it is suffice look the errors at each ji. (multi-channel) pixel separately:
Error
(lf(x))s A (1)())1
A || II P (z)(() A -
1|(wo A) 1 (z)
S <(I || x (P)(())))*
Assume the absolute value of pixel values are bounded by B, then
[|Pr(()]| s BKK.K.C
The first two terms can be bounded according to the rank of the subspace projection I1K, Let the nullity of the projection be n K CwC - r. Note the projection matrix can be decomposed as
where {uuJa is orthonormal basis for the projection subspace.
=
UK
1=1
eAT2211
(Orthonormality of {ux hv)
(sub-multplicattiityy of the Frobenius norm)
VnC.
"In particular, W is used for both the "width" of the image and the parameters of the linear system. But the meaning should be clear from the context. The multi-dimensional tensors O..k and (.) are used inter- changeably with their flatten column counterparts.
15

---

Published as a conference paper at ICLR 2020
Similarly,
W |
WOT uxl l|
Assume the entries of p are initialized as i..d. Gaussians (N0, o²). Since {ox hy are orthonormal vectors, for each k; let Pk || vx|12// /o² then pk is distributed according to x distribution with C' degree of freedom. For any < 5 S M, where M a constant chosen a priori, and for each
k=
(ps 2 (C) 6 6 E [e (0
(Markov's inequality)
- (1 (1-2t) -0/2 Vt < 1/2,
(MGF of x²)
exp (-C + 1/2log(1 2t))),
cxp (-0/2(5 - +1 log( (gg())))))
(optimal at tt = 1/2(1 1/c))
exp
(-0/2(5- -1 loglog( \/M]])
By union bound,
P [I....,nn} n) : 12225 (C) S nexp (-0/2(5 - 1 log(H/M)))
(10)
Let å equals the right hand side, and solve for Ç, we get for any 6n 0, with probability at least
1 5
Vk: Pk < log (5) + C(1 + log M)
(11)
where 6, 2 2n/(C(M - log M 1)) is chosen to satisfy set M accordingly.
s M. We can also choose 8y first and
Putting everyting together, with probability at least - 6, the mean squared error (averaged over all output pixels)
Error
Error Kj* ijEz
E
(wno² no? (2log (5) + C(1 log M) + VnC B B ByKnKwc) /c.
(K Caa(1 l/ol//(1/))
(12)
C
Note K C2 is the number of parameters in the convolution net.
CASE 2 underparameterization: E > KH Kw C' x C. Using the same notation above, assuming no redundant features, we apply Lemma get the prediction of the (i,j)-th (multi- channel) pixel of test example
WTP = Y xxXXxxxx
= = = XXxXx)xx
A =
Recall the definition of A, which maps patch to the corresponding (multi-channel) pixel. In this case, prediction exact, and the error is zero. Since in this case n, this case can be merged with equation I2
Proof of Lemma ! The proof is an extension of Theorem | to the case of more than one training examples. Using the notation in the Lemma, the training objective can be written as the matrix form
1 |XW
Y
2
16

---

Published as a conference paper at ICLR 2020
and the gradient
OR aw = (XW -XX
Since the model is overparameterized, and there is no unique minimizer to the empirical risk. How- ever, gradient descent converges to a unique solution. Note the gradient descent step is:
a OW
W W 1)t
W=W
W n (XW2-1-
w Σ x x (XWT-X.
= 0 +
where U = -r= "XW" Y) E Rxd parameterizes the solution at iteration L. Since X X invertible in this case. A unique solution exists under this parameterization, which can be obtained by solving
X(Wo + +xū0== 0 = (xxT) -1 -
Plug this into the parameterization, we get
W r + +x (XXT)- (Y XW").
(13)
Proof of Lemma 2
Using the same notation as in the proof of Lemma I since the model is under- parameterized, unique minimizer of the empirical risk exists. Directly solving for the optimality
condition OR/äW 0, we get
W (xTxx) xTy.
(14)
E FULL RESULTS OF FULLY CONNECTED MULTI-LAYER NETWORKS
In this section, we present the detailed results on fully connected networks that are omitted from Section 3.1 space limit.
E.1 FULLY CONNECTED LINEAR NETWORKS
Figure shows the results on multi-layer linear networks with various number of hidden layers and hidden units. The depth of the architecture has a stronger effect on the inductive bias than the width. For example, the network with one hidden layer of dimension 2048 has 3.2M parameters, more than the 2.5M parameters of the network with three hidden layers of dimension 784, But the latter behaves less like the convex case.
E.2 TWO-LAYER FULLY CONNECTED RELU NETWORKS
Li Liang 2018 offer theoretical characterization of learning in two-layer ReLU neural net- work. They show that when the data consists of well separated clusters (i.e., the cluster diameters are much smaller than the distances between each cluster pair), training an overparameterized two- layer ReLU network will generalize well. To simplify the analysis, they study special case where the weights in the top layer are randomly initialized and fixed; only the bottom layer weights are learned.
17

---

Published as a conference paper at ICLR 2020
7
2
7
2
7
7
7
7
7
7
7
7
7
7
7
7
3
7
7
7
7
7
7
7
7
7
7
7
5
(a) Hidden dimension 784 (= input dimension)
(b) Hidden dimension 2048
Figure II: Visualization of predictions from trained multi-layer linear networks. The first row shows the input images for evaluation, including the single training image "7" at the beginning of the row. The remaining rows shows the prediction from trained linear network with 1, 3, and hidden layers, respectively.
7
9
4
7
9
4
7
7
2,048
7
7
7
7
16,384
(a) Training bottom layer only
(b) Training both layers
Figure 12: Visualization of predictions from two-layer ReLU networks. The first row shows the input images for evaluation, including the single training image "7" at the beginming of the row. The remaining rows shows the predictions from trained models with hidden dimension 2,048 and 16,384, repectively.
We study the problem of learning two-layer ReLU network under our identity-mapping task. Fig- ure compares the cases of learning the bottom layer only and learning both layers (left and right panels, respectively). The test images. When only the first layer is trained, the tendency is toward speckled noise, but when both layers are trained, the tendency toward a constant output (the image used for training). Our observation does not contradict the theoretical results of Li & Liang (201)), which assume a well separated and clustered data distribution.
cases demonstrate different inductive biases for predictions on unseen
For bottom-layer only training, we can analyze it in similar way to the one-layer networks. Let us denote
[w(() = (ox, ReLU(=)),
Wa
(15)
where W E Rm the learnable weight matrix, and a E R is randomly initialized and fixed. Although the trained weights longer have closed-form solution, the solution found by gradient descent is always parameterized as
W = W. + TT
(16)
where è the training example, and T R summarizes the efforts of gradient descent up to time T. In particular, the gradient of the empirical risk Å with respect to each row W,r of the learnable weight is
añ añ oz, okt $
(17)
OW, oz, oW, d2
Putting together, the full gradient
an aR
T
(18)
aW dz
Since the gradient lives in the span of the training example 2, the solution found by gradient descent always parameterized equation T6
18

---

Published as a conference paper at ICLR 2020
2
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
3
7
7
7
7
7
7
7
7
7
7
7
7
7
9
Figure 13: Visualization of predictions from multi-layer ReLU networks. The first row shows the input images for evaluation, including the single training image "7" at the beginning of the row. The remaining rows show the predictions from trained multi-layer ReLU FCNs with 1, and hidden layers.
correlation constant function
correlation to constant function
1.0
3-
0.8
0.8
raden
5-
0.6
0.6
9-
11
11
0.0
0.2
0.3
0.5
0.6
0.8
0.9
0.2
0.3
correlation to identity function
correlation to identity function
1.0
1.0
1-
0.8
7-
0.4
0.2
0.2
11
0.0
11
0.0
0.0
0.2
0.3
0.5
0.6
0.8
0.9
0.0
0.2
0.3
0.5
0.6
0.8
0.9
train test correlation
tho:
test correlation
(a) ReLU FCNs
(b) Linear FCNs
Figure 14: Quantitative evaluation of the learned model on randomly generated test samples at various angles (correlation) to the training image. The horizontal axis shows the train-test cor- relation, while the vertical axis indicate the number of hidden layers for the FCNs being evaluated. The heatmap shows the similarity (measured in correlation) between the model prediction and the reference function (the constant function or the identity function). (a) shows the results for FCNs with the ReLU activation function; (b) shows the results for linear FCNs.
The arguments applies multi-layer neural networks. The prediction any test example that orthogonal to å will depend only on randomly initialized W and upper layer weights. When only the bottom layer is trained, the upper layer weights will also be independent from the data, therefore the prediction is completely random. However, when all the layers are jointly trained, the arguments no longer apply. The empirical results presented in the main text that multi-layer networks bias towards the constant function verify this.
In particular, if the example orthogonal to å (i.c., TT. 0), the prediction depends solely on the randomly initialized values in W and therefore can be characterized by the distribution used for parameter initialization.
However, when both layers are trained, the upper layer weights are also tuned to make the prediction fit the training output. In particular, the learned weights the upper layer depend on W Therefore, the randomness arguments shown above no longer apply even for test examples orthogonal to á. As empirical results show, behavior indeed different.
E.3 NONLINEAR MULTI-LAYER FULLY CONNECTED NETWORKS
In this section, we consider the general case of multilayer fully connected networks (FCNs) with ReLU activation functions. Figure 133 visualize predictions from trained ReLU FCNs with 1,
19

---

Published as a conference paper at ICLR 2020
Trained 7-layer
Random 20-layer
Trained 14-layer
Trained 20-layer
7
Figure 15: Visualization the intermediate layers of CNNs with different number of layers. The first column shows a randomly initialized 20-layer CNN (random shallower CNNs look similar to the truncation of this). The rest of the columns show the trained CNNs with various number of layers.
hidden layers. The deepest network encodes the constant map with high confidence; the shallowest network shows behavior similar to that of one-layer linear net. Quantitative evaluations of the behaviors are shown in Figure 14] computed in the same way as Figure CNNs (see Section 3.2) The results for linear FCNs are also shown for comparison. The linear and ReLU FCNs behave similarly when measuring the correlation to the identity function: neither of them performs well for test images that are nearly orthogonal f.. For the correlation to the constant funetion, ReI.U FCNs overfit sooner than linear FCNs when the depth increases. This is consistent with our previous visual inspections: for shallow models, the networks learn neither the constant nor the identity function, as the predictions nearly orthogonal examples are random.
F VISUALIZATION OF THE INTERMEDIATE LAYER REPRESENTATIONS FOR CNNS
Unlike the FCNs, CNNs preserve the spatial relation between neurons in the hidden layers, so we can easily visualize the intermediate layers as images in comparison to the inputs and outputs, to gain more insights on how the networks are computing the functions layer-by-layer. In Figure 15 we visualize the intermediate layer representations on some test patterns for CNNs with different depths. In particular, for each example, the outputs from a convolutional layer in intermediate layer is a three dimensional tensor of shape (#channel, height, width). To get a compact visualization for multiple channels in each layer, we compute flatten the 3D tensor to matrix of shape (#channel, height& x width), compute SVD and visualize the top singular vector as a one-channel image.
In the first column, visualize 20-layer CNN random initializatior + As expected, the ran- domly initialized convolutional layers gradually smooth out the input images. The shape of the input images are (visually) wiped out after around 8 layers of (random) convolution. On the right of the figure, we show several trained CNNs with increasing depths. For 7-layer CNN. the holistic structure of inputs are still visible all the way to the top at random initialization. After training, the network approximately renders an identity function at the output, and the intermediate activations also become less blurry. Next we show 14-lr CNN, which fails learn the identity function.
Shallower CNNs at random initialization can be well represented by looking at (top) subset of the visu- alization.
20

---

Published as a conference paper at ICLR 2020
Figure 16: Visualizing the intermediate layers of trained 7-layer CNN. The three subfigures show for each layer: 1) the top singular vector across the channels; 2) the channel that maximally correlate with the input image; 2) a random channel, respectively.
Visualizing the intermediate layers of trained 14-layer CNN. The three subfigures show for each layer: 1) the top singular vector across the channels; 2) the channel that maximally correlate with the input image; 2) a random channel, respectively.
Figure 17:
However, it manages recover meaningful information in the higher layer activations that were (visually) lost in the random initialization. On the other hand, in the last column, the network is so deep that it fails to make connection from the input to the output. Instead, the network start from scratch and constructs the digit '7' from empty and predict everything as '7', However, note that around layer-8, we see the activations depict slightly more clear structures than the randomly ini- tialized network. This suggests that some efforts have been made during the learning, opposed to the case that the bottom layers not being learned due to complete gradient vanishing. Please refer to Appendix for further details related to potential gradient vanishing problems.
Two alternative visualizations to the intermediate multi channel representations are provided that show the channel that is maximally correlated with the input image, and random channel (channel 0). Figure 16 Figure 17 and Figure 18 illustrate a 7-layer CNN, a 14-layer CNN and a 20-layer CNN, respectively.
G MEASURING THE CHANGE WEIGHTS LAYERS POST TRAINING
In this section, we study the connection between the inductive bias of learning the constant function and the potential gradient vanishing problem. Instead measuring the norm of gradient during simple proxy that directly compute the distance of the weight tensor before and after training. In particular, for each weight tensor W at initialization and W after training, we compute the relative la distance
training.
d(wo W*) = | W
[
The results for CNNs with various depths are plotted in Figure 19 a). As general pattern, do see that as the network architecture gets deeper, the distances at lower layers do become smaller. But they are still non-zero, which is consistent with the visualization in Figure 15 showing that even
21

---

Published as a conference paper at ICLR 2020
Figure 18: Visualizing the intermediate layers trained 20-layer CNN. The three subfigures show for each layer: 1) the top singular vector across the channels; 2) the channel that maximally correlate with the input image; 2) a random channel, respectively.
0.06
0.10
11
11
6.12
0.08
0.10
0.05
0.04
0.06
0.00
6.00
layer index
layer index
(a) CNNs
(b) Linear FCNs
(c) ReLU FCNs
Figure 19: The relative l distance of the weight tensors before and after training each layer. The curves compare models at different depth. Most of the networks have significantly larger distances on the top-most layer. To see better resolution at the bottom layers, we cut off the top layer in the figures by manually restricting the axis.
22

---

Published as a conference paper at ICLR 2020
56
Figure 20: Visualization of 5-layer CNN test images of different sizes. Every show the inputs and model predictions. The numbers on the left indicate the input image size (both width and height).
for the 20-layer CNN, where the output layer fits to the constant function, the lower layers does get enough updates allow them to be visually distinguished from the random initialization.
In Figure 19(b) and (c), we show the same plots for linear FCNs and FCNs with ReLU activation, respectively. We see that especially for ReLU FCN with 11 hidden layers, the distances for the weight tensors at the lower layers are near zero. However, recall from Figure [3] in Section E.3 ReLU FCNs start to bias towards the constant function with only three hidden layers, which are by no means suffering from vanishing gradients as the plots here demonstrate.
H FULL RESULTS ON ROBUSTNESS OF INDUCTIVE BIASES
H.1 TESTING ON DIFFERENT INPUT IMAGE SIZES
Figure 6 Section 3.3 visualize the predictions 5-layer CNN on inputs of the extreme sizes of 7 x 7 and 112 x 112. Here in Figure 20 we provide more results on some intermediate image sizes.
trained 20-layer CNN on various input sizes (Figure 7 It is interesting that the constant map also holds robustly across wide range of input sizes. Especially from the prediction on large input images, we found hints on how the CNNs actually compute the constant function. It seems the artifacts from the outside boundary due to convolution padding are used cues to "grow" a pattern inwards to generate the digit "7". The visualizations of the intermediate layer representatiosn in Figure is consistent with our hypothesis: the CNN take the last several layers to realize this construction. This is very elever, because in CNNs, the same filter and bias is applied to all the spatial locations. Without relying the artifacts the boundaries, it would be very challenging to get sense of the spatial location in order to construct an image with a holistic structure (e.g. the digit "7" in case).
We also
H.2 THE UPPER SUBNETWORKS
In the visualization of intermediate layers (Figure 15), the intermediate layers actually represent the "lower" subnetwork from the inputs. Here we investigate the "upper" subnetwork. Thanks again to the spatial structure of CNNs, the intermediate layers and still get interpretable visualizations [4] Figure 22 shows the results for the top-one layer from CNNs with various depths. A clear distinction can be found at 15-layer CNN,
skip the lower layers and feed the test patterns directly to
'Specifically, the intermediate layers expect inputs with multiple channels, so repeat the grayscale inputs across channels match the expected input shape.
23

---

Published as a conference paper at ICLR 2020
(a) 16 X 16
(b) 28 x
(c) 36 36
(d) 48 x 48
Figure 21: Visualization of intermediate representations when testing images of different sizes from training images for a 20-layer trained CNN. The CNN is trained on a 28 x 28 image of the digit "7"
24

---

Published as a conference paper at ICLR 2020
9
7
4
5
7
9
9
7
8
6
9
7
7
7
7
9
7
7
191
7
Visualizing only the final layer in trained networks. The first row are the input images, which are directly fed into the final layer of trained networks (skipping the bottom layers). The remaining rows shows the predictions from the top layers of CNNs, with the numbers the left indicating their (original) depth.
Figure 22:
Indul
7
Figure 23: Visualizing only the top two layers trained networks. The first row are the input images, which directly fed into the top layer of trained networks (skipping the bottom layers). The remaining rows shows the predictions from the top two layers CNNs, with the numbers on the left indicating their (original) depth. More specifically, each of the top layers occupies one row. The colorful rows are the visualizations (as the top singular vector across channels) of the outputs of the second to the last layer from each network. The grayscale rows are the outputs of the final layer from each network.
which according to Figure Bis where the networks start to bias away from edge detector and towards the constant function.
The predictions from the final two layers of each network are visualized in Figure 23 Figure 24
focuses on the 20-layer CNN that learns the constant map, and visualize the upper layers, 6 layers and 10 layers, respectively. In particular, the last visualization shows that the 20-layer CNN is already starting to construct the digit "7" from nowhere when using only the upper half of the model.
25

---

Published as a conference paper at ICLR 2020
impot
100
top
10P 10
7X
7
7
Figure 24: Visualzing the top layers, layers and 10 layers of a 20-layer CNN. Visualizations formatted in the same way Figure 23
correlation function
correlation identity function
1.0
9
Coru Filter
13
0.6
0.6
17
17
25
29
0.2
29
02
0.2
rho: train-test correlation
moo train-test correlation
Figure 25: Inductive bias of 5-layer CNN with varying convolutional filter size. The heatmap arranged similarly as Figure 4 except that the rows correspond CNNs filter sizes.
I FULL RESULTS ON VARYING DIFFERENT FACTORS WHEN TRAINING CNNs
The study the effects of various hyperparameters the inductive bias of trained CNNs is briefly presented in Section 3.4 The full results are shown here.
Convolution filter sizes Figure 25 and Figure 26 illustrate the inductive bias with varying convo- lution filter size from 3 5 to 57 x 57. The visualization shows that the predictions become more and more blurry as the filter sizes grow. The heatmaps, especially the correlation to the identity function, not helpful in this images with different levels of blurry. With extremely large filter sizes that cover the whole inputs, the CNNs start to bias towards the constant function. Note our training inputs are of size 28 28, so 29 x 29 filter size allows all the neurons to see no less than half of the spatial domain from the previous layer. 57 57 filters centered any location within the image will able to see the whole previous layer. On the other hand, the repeated application of the same convolution filter through out the spatial domain is still used (with very large boundary paddings the inputs). So the CNNs are not trivially doing the same computation as FCNs.
the correlation metric is not very good at distinguishing
Convolution channel depths Figure TO in Section 3.4 shows that the learned identity function severely corrupted when only 3 channels are used in 5-layer CNNs. Figure 27 presents the correlation to the constant and the identity function when different numbers of convolution channels are used. The heatmap is consistent with the visualizations, showing that the 5-layer CNN fails to approximate the identity function when only three channels used in each convolution layer.
Furthermore, Figure 28 visualize the predictions trained 3-channel CNNs with various depths. The 3-channel CNNs beyond 8 layers fail to converge during training. The 5-layer and the 7-layer CNNs implement functions biased towards edge- detectin or countour- founingr-finding But the 6-layer and the 8-layer CNNs demonstrate very different biases. The potential reason that with only few
26

---

Published as a conference paper at ICLR 2020
7
7
9
7
7
6
9
7
7
6
7
7
7
6
7
7
7
5
7
13
7
7
5
7
15
7
7
5
7
17
7
7
5
7
25
7
7
7
29
7
7
7 7
57
7
7
7
Figure 26: Visualizing the predictions from CNNs with various filter sizes. The first row is the inputs, including the single training image "7". The remaining rows predictions, with the numbers on the left showing the corresponding filter sizes.
correlation to constant function
1.0
#chnn
3
128
0.6
0.4
1024
0.0
0.0
0.2
0.5
0.6
0.9
correlation to identity function
1.0
# #chnn
0.8
128
0.6
0.4
1024
0.0
0.0
0.2
0.3
0.5
0.6
0.8
0.9
rho: train-test correlation
Figure 27: Correlation to the constant and the identity function for different convolution chan- nels in a 5-layer CNN.
7
7
5
9
L5
7
7
5
7
16
7 -
7
L7
7
-
L8
7
Figure 28: Visualization predictions from CNNs with 3 convolution channels and with various number of layers (numbers on the left). The first row is the inputs, and the remaining rows illustrate the network predictions.
27

---

Published as a conference paper at ICLR 2020
7
9
7 7
9
(a) 3 channels, random init
(b) 128 channels, random init
Figure 29: Visualizing the randomly initialized models to compare two 5-layer CNNs with convolution channels per layer and 128 convolution channels per layer, respectively. The sub- figures visualize the predictions of intermediate layers of the network random initialization. The multi-channel intermediate layers are visualized as the top singular vectors.
7
7
9
7
7
(a) 3 channels, after training
(b) 128 channels, after training
Figure 30: Comparing two 5-layer CNNs with 3 convolution channels per layer and 128 convo- lution channels per layer, respectively. Layout similar Figure 29
channels, the random initialization does not have enough randomness smooth out "unlucky" bad cases. Therefore, the networks have higher chance to converge to various corner cases. Figure 29
and Figure 330 compare the random initialization with the converged network for 3-channel CNN
and a 128-channel CNN. From the visualizations the intermediate layers, the 128-channel CNN already behave more smoothly than the 3-channel CNN at initialization.
Initialization schemes In transfer learning, it is well known that initializing with pre-trained net- work weights could affect the inductive bias of trained models. On the other hand, different random initialization schemes are mainly proposed to help with optimization by maintaining information flow norms of representations at different depths. turns out that they also strongly affect the inductive bias of the trained models. Figure 33 31 visualizz the different inductive biases, Let fü. fo be the fan and fan out of the layer being initialized. We tested the following commonly used initial- ization schemes: 1) default: (100 0² =//(fffo)) 2) Xavier (a.k.a. Glorot) init (Glorot & Bengio
2010 (O, o² 2 (f. + fo)): 3) Kaiming init (He et al. 2015): (N 2/ 4) Orthog-
onal mit (Saxe et al.] 2014). Variations with uniform distributions instead Gaussian distributions also evaluated for Xavier and Kaiming inits. All initialization schemes bias toward the identity function for shallow networks. But Kaiming init produces heavy artifacts on test predictions. For the bias towards the constant function in deep networks, Xavier init behaves similarly the default init scheme, though more layers are needed to learn a visually good identity function. On the other hand, the corresponding results from the Kaiming init less interpretable.
Optimizers First order stochastic optimizers are dorminately used in deep learning due to the huge model sizes and dataset sizes. To improve convergence speed, various adaptive methods are introduced (Duchi et al. 2011 Kingma & Ba 2014 Graves 2013). It is known that those methods lead to worse generalization performances in some applications (e.g. Wu et al. (2016)). But they extremely popular in practice due to the superior convergence speed and easter hyper-parametts tuning than the vanilla SGD. We compare several popular optimizers our framework, and confirm that different optimizers find different global minimizers, and those minimizers show drastically
28

---

Published as a conference paper at ICLR 2020
7
7
9
7
7
?
7
X
7
7
5
9
7
5
7
X
7
6
9
7
7
5
9
K
7
9
5
9
7
5
1-layer CNNs
3-layer CNNs
7
7
7
7
7
X
7
7
5
7
7
7
X
7
7
5
7
7
K 7
Or 7
5-layer CNNs
14-layer CNNs
7
7
7
7
7 7
7
7
7
7
7
7
7 7
X
7
7
7
7
7
7
K
7
7
7
2
Or
7
7
F
7
20-layer CNNs
24-layer CNNs
Figure 31: Visualization of the predictions from CNNs trained with the D) default, Xn) Xavier normal, Xu) Xavier uniform, Kn) Kaiming normal, Ku) Kaiming uniform, and Or) orthogonal initialization schemes. The first row shows the inputs, and the remaining rows shows the predictions from each trained networks.
29

---

Published as a conference paper at ICLR 2020
7
7
9
7
7
5
7
7
S
7
7
7
6
7
7
7
7
7
7 7
5
7
7
7
S
7
7
7
7
7
5
7
5
7
7
5
7
5
3-layer CNNs
5-layer CNNs
7
7
9
10 10
7
7
7
7
7
7
7
NAKE
7
7
S
7
adinn adam
7
4
14-layer CNNs
17-layer CNNs
7
7
7
30
7
7
7 7
7
7
7
7
7
7
7
7
7
7
7 7
7
7
7
7
7
7
7
7
7
7
7
7
7
/ 1 P
M
7
7
7
7 7
7
7
7 7
7
7
7
7
7
7 7
7
7
7
7 7
7
7
7
7
adamm 365m
7
7
5
7
7
7
7
7
?
3
?
2
20-layer CNNS
24-layer CNNs
Figure 32: Visualization of the predictions from CNNs trained with different optimizers. The first row shows the inputs, the remaining rows shows the predictions from SGD (Ir 0.01), SGD (Ir 0.001), SGD (Ir 0.0001), Adagrad, RMSprop, Aam, and Adamax respectively.
Some optimizer requires a smaller base learning rate to avoid parameter exploding during training. In particular, use base learning rate 0.001 for Adagrad and Adamax, 0.0001 for Adam and RMSprop. For comparison, we also include results from SGD with those corresponding base learning rates.
different inductive biases on test examples, as shown in Figure 32
J CORRELATION VS MSE
Figure 33 Figure 34 and Figure 35 can be compared to their corresponding figures in the main text. The figures here are plotted with the MSE metric between the prediction and the groundtruth, while the figures in the main text the correlation metric. Each corresponding pair of plots overall consistent. But the correlation plots show the patterns more clearly and has a fixed value range of [0. 1] that is easier interpret.
30

---

Published as a conference paper at ICLR 2020
miee to constant function
mse to identity function
0.08
0.10
0.08
0.00
0.04
31
11
0.0
0.2
0.3
0.5
0.6
0.8
0.9
0.0
0.2
0.3
0.5
0.6
0.8
0.9
correlation
correlation
Figure 33:
Quantitative evaluation of linear FCNs. The same as Figure 14 a), except MSE is
plotted here instead of correlation.
mse constant function
to identity function
0.14
0.07
0.12
00
0.10
booden
0.00
0.01
0.3
0.3
Figure 34: Quantitative evaluation of ReLU FCNs. The same as Figure b4(b), except MSE is plotted here instead of correlation.
mse to constant function
mse to identity function
0.14
0.12
ConvNet Dopth
7-
0.12 5
0.10 7
0.10
11
0.08 11
12
12
0.06
14
0.06
16
0.04 16
0.04
19
0.02
0.02
20
0.00
0.2
0.3
0.0
rho: train-test correlation
rho: train-test correlation
Figure 35: Quantitative evaluation of CNNs. The same as Figure 4 except MSE is plotted here instead of correlation.
31

---

Published as a conference paper at ICLR 2020
Iaput
F
1-layer
7
7
1-leyer
7 9
3-lyer
7
4
3-bayer 7
5-aaee
7
7
4
S-layer
7 9
7-kyer
7
7
7-layer
7
7
9-byye
7
7
9-1ayer
11-kyer
7
11-laye
12-layer
7
12-layer
14-layer
15-leyer
7
15 S--Yayer
16-layer
16-layer
18-layer
7
7
18-layer
19-haer
7
19-layer
20-layer
7
20-layer
7
7
(a) run
(h) 3rd run
Figure 36: Visualization of predictions from CNNs trained single example. The same training example is used as in the main text, but two extra runs of training and evaluation are listed show the robustness of our main observations the randomness in the experiments.
Inpur
3
Iaput
L-aayer
3
e
I-layer
3-layer
3
3-layer
5-layer
3
5-layer
7-layer
3
7-layer
D
9.layer
3
9-Jayer
11-layer
3
5
11-layer
12-layer
3
5
12-layer
14-layer
3
14-layer
15-layer
3
15-1ayer
16-layer
3
16-layer
18-layer
3
3
18-layer
19-layer
3
3
19-1ayer
20-layer
3
3
3
3
3
3
3
20-layer
(a) training with digit
(b) training with digit 0
Figure 37: Visualization of predictions from CNNs trained single example. Two different (randomly chosen) training images (a) digit 3, (b) digit 0, are shown to compare robustness of our main observations to different training images.
K ROBUSTNESS OF OBSERVATIONS TO RANDOM SEEDS
We evaluate the robustness our main observations to randomness from the experiments this section. In Figure 36 two different rums of training and evaluation compared side by side, and the results are very consistent. In Figure 337 further perturb the random seeds for data loading, so that different (single) training images are loaded for training. We that the main observations
32

---

Published as a conference paper at ICLR 2020
7
9
0
3
4
Input
H0
7
9
7 9
7
7
11
7
9
7
9
7
9
9
7
7
9
9
7
7
9
H5
7
9
7
7
7
9
7
7
7
7
7
7
9
9
119
7
9
7
7
7
7
7
7
7
7
7
7
9
9
7
9
3
3
4
G5
7
9
3
3
4
C7
7
9
3
S
4
C14
9
3
3
4
C17
7
9
7
V
C
C20
7
9
7
7
9
7
7
7
C24
7
9
7
7
Figure 38: Visualization of the predictions from networks trained with 2 examples. The first two columns are training examples, and the remaining columns are unseen test cases. H0-H shows fully connected networks with the corresponding number of hidden layers. C3 C24 shows CNNs with the corresponding number of layers.
hold for both cases: CNNs learn the identity map, edge detector and the constant map as the depth increases.
L LEARNING WITH MULTIPLE EXAMPLES
We focus on learning from a single example in this paper because the two extreme inductive bi- ases of the identity map and the constant map be precisely defined and tested against. When training with multiple examples, the constant map is no longer a viable solution to the optimization problem. Nevertheless, we can still qualitatively evaluate the inductive bias via visualization of pre- dictions. Figure 38 shows the results on various networks trained with two examples. In particular, for networks that are known overfit the constant map when trained with one example (e.g. fully connected networks with 9 hidden layers, and 20-layer convolutional networks), similar overfitting behaviors are observed. In this case, a proper definition of constant map no longer holds, as the network perfectly reconstruct each individual digit from the training set. On the test set, notion of memorization can be recognized as always predicting mixture of the training samples. Note sometimes the prediction is biased more towards one of the training samples depending the input patterns.
Figure 39 shows the results with three examples, with similar observations. Figure 40 shows the situation when training with the full MNIST training set (60k examples). In this case, even the deepest convolutional networks networks learn the identity function on the manifold of digit inputs, but still cannot reconstruct meaningful results other test patterns.
tried successfully learn the identity function. Fully connected
33

---

Published as a conference paper at ICLR 2020
7
9
5
3
input
H0
7
9
5
HI
7
9
5
7
H3
7
9
5
7
7
7
H5
7
9
5
7
7
7
9
5
7
7
7
7
9
5
Ø
3
C5
7
9
5
Ø
3
4
C7
7
9
5
Ø
3
4
7
9
5
3
S
C17
7
9
5
3
7
9
5
7
4
C24
7
9
5
7
4
Figure 39: Visualization of the predictions from networks trained with examples. The first three columns are training examples, and the remaining columns are unseen test cases. H9-H9 shows fully connected networks with the corresponding number of hidden layers. C3 C24 shows CNNs with the corresponding number of layers.
34

---

Published as a conference paper at ICLR 2020
7
9 5
0
3
4
input
110
7
9
5
3
4
HI
7
9
5
3
4
115
7
9
5
Ø
3
4
7
9
5
3
4
LinFl
7
9
5
LinHS
7
9
5
3
4
LinHS
9 7
5
Ø
3
C3
7
9
5
Ø
3
4
C7
7
9
5
3
C14
7
9
5
Ø
3
C20
7
9
5
3
4
7
9
5
Figure 40: Visualization of the predictions from networks trained with 60k examples. The out of 60k) training examples, and the remaining columns unseen test cases. HO-H9 show fully connected networks (ReLU activation) with the corresponding number of hidden layers. LinHI-LinfH show linear fully connected networks (without activation) with the corresponding number of hidden layers. And C3-C24 show CNNs with the corresponding number of layers.
first three columns
35

---

Published as a conference paper at ICLR 2020
FCN num layers
2
4
10
hidden dim 784 hidden dim 2048
1,229,312
2,458.624
3,687,936
4,917,248
6,146,560
614.656
3,211,264
11,599,872
19,988,480
28,377,088
36,765,696
CNN num layers
3
5
6
7
5 filter, 3 channels
25
375
825
1,050
1,275
1,500
x 6 filter, 128 chamnels
25
416,000
1,235,200
1,644,800
2,054,400
2,464,000
5 1024 channels
78,694,400
131.123,200
7 filter, channels
1.617
2,058
2,499
2,940
7 filter, 128 channels
815,360
2,420,992
3,223,808
4.026.624
4.829,440
x 7 filter, 1024 channels
154,241,00 .204
257,001,472
CNN num layers
9
13
14
x 5 filter, 3 channels
1,725
1,950
2,175
2,400
2,625
2,850
2,873,600
3,283,200
3,692,800
4,102,400
4,512,000
4,921,600
5 filter, 1024 channels
262, 195,200
314,624.000
7 filter, 3 channels
3,381
3,822
4,263
4,704
5,145
5,586
X 7 filter, 128 chanaels
3,632,256
6,435,072
7,237,888 ,888
8,040,704
8,843,520
9,646,336
channels
513,902.592
616,663,040
layers
x G filter, 3 channels
3,075
3,300
3,525
3,975
4,200
5,100
5 filter, 128 channels
5,331,200
5,740.800
6,150,400
6,969,600
7,379,200
9,017.600
x 5 filter, 1024 channels
471,910,400
x 7 filter, 3 channels 7 filter, channels
6,027
6,468
6,909
7,791
8,232
9,996
10,449.152
11,251,968
12,054,784
13,660,16
14,463,232
17,674,496
7 filter, 1024 channels
924,944,384
CNN filter size
13
29
57
layers, channels
4,002,048
8,349.952
14,278,912
30,880,000
41,552,
160,526,592
Table 1: Number of parameters different neural network architectures used in this paper. The number of parameters are calculated for 28 x 28 grayscale input output sizes.
M PARAMETER COUNTS FOR NEURAL NETWORKS USED IN THIS PAPER
For convenience cross comparing the results of different architectures with similar number of parameters, list in Table [ the architectures used in this paper and their associated number of parameters.
N RESIDUAL NETWORKS
In this section, we evaluate training FCNs with residual connections. In particular, an identity skip connection is added for every two fully connected layers. other words, the networks are built with two-layer blocks that computes + ReLU(W ReL,((zzz) except that ReLU is applied at the output layer. Adding skip connection after ReLU ensures the input gets passed directly to the output layer. Because the residual structure requires the same input-output shape for every block, we use 784 hidden dimensions.
Comparing Figure 41 with the vanilla FCNs in Figure 2] the identity skip connection strongly bi- ased the FCNs towards learning the identity map. On the other hand, we can still observe that the prediction noises become stronger with larger number of hidden layers, suggesting that learning the identity function is non-trivial even with the explicit identity skip connections built into the archi- tectures.
O EXPERIMENTS ON CIFAR-10 IMAGES
In this section, we show experiments on some colored images from the CIFAR-10 dataset (32 x 32 RGB images). Figure 42 and Figure 4 show the results from two different randomly sampled training images, respectively. The network architectures used here are nearly identical to the ones used to train on MNIST digits in the main text of the paper: the CNNs are with 128 channels and 5x5
36

---

Published as a conference paper at ICLR 2020
7
2
7
2
/
7
2
/
3
7
2
/
5
7
2
1
7
2
1
9
Figure 41: Visualization of predictions from multi-layer ReLU networks with residual con- nections. The first row shows the input images for evaluation, including the single training image "7" at the beginning of the row. The remaining rows show the predictions from trained multi-layer ReLU FCNs with residual connections, with the numbers on the left indicating the number of hidden layers.
filters. The FCNs are slightly modified to have larger hidden dimensions 3072 32 x x2, to avoid explicitly enforcing bottlenecks in the hidden representations. The training loss and optimization algorithms are the same as in the MNIST case.
The main observations are consistent the results on the MNIST digits. In particular, shallow FCNs produce random noisy predictions on unseen evaluation inputs, but deep FCNs bias towards mem- orization and hallucinate the training image on all test outputs. For CNNs, shallow networks are capable of learning the identity function, but deep networks learn the constant function instead.
37

---

Published as a conference paper at ICLR 2020
Input
HO
H1
FCNs
H3
H5
H7
CI
C5
C9
C12
CNNs
C16
C20
C24
C28
Figure 42: Visualization of predictions from various networks trained on a single CIFAR-10 image (dog). The first row shows the input images, where the first one is the training image and the rest are images for evaluation. The evaluation images consist of unseen images from the CIFAR-10 10 test and artificially generated grayseale patterns. The grayscale patterns channels before feeding into the networks. The remaining rows show the predictions from trained FCNs and CNNs. For FCNs, the numbers indicate the number of hidden layers. For example, H3 means a 3-hidden-layer FCN, For CNNs, the numbers indicate the number of (convolutional) layers. For example, C16 means a 16-layer CNN.
duplicated into three
38

---

Published as a conference paper at ICLR 2020
Input
HO
H1
FCNs
H3
H5
H7
CI
C5
C9
C12
CNNs
C16
C20
C24
C28
Figure 43: Visualization of predictions from various networks trained on a single CIFAR-10 image (air plane). The first shows the input images, where the first one is the training image and the rest are images for evaluation. The evaluation images consist unseen images from the CIFAR- 10 test and artificially generated grayscale patterns. The grayscale patterns duplicated into three channels before feeding into the networks. The remaining rows show the predictions from trained FCNs and CNNs. For FCNs, the numbers indicate the number of hidden layers. For example, H3 means a 3-hidden-layer FCN, For CNNs, the numbers indicate the number of (convolutional) layers. For example, C16 means 16-layer CNN.
39


Reviews:
[{"review_id": "rkl93vlTKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the inductive bias of neural nets by considering the toy example of learning an identity map through a single data point (and hence the NNs are always overparametrized). The authors compare CNNs versus FCNs, and find that CNNs tend to “generalize” in terms of actually learning the concept of an identity, whereas FCNs are prone to memorization. The authors also present results under various different settings such as changing the filter size or the number of hidden channels of CNNs. The conclusion is that the simpler the network architecture is, the better it generalizes. Another observation is that deep CNNs exhibit extreme memorization.\n\nOverall, this is a well-written paper with an interesting set of experiments. However, I do have several concerns regarding the generality of the observed phenomenon in this paper. The first one is that the authors have chosen the comparison between CNNs and FCNs. In this case, I think a more fair comparison is to restrict the number of links (number of nonzero entries in the weight matrices) for both to be the same. In the current setup, however, the authors seem to consider the same number of hidden neurons, which naturally grants advantages to CNNs as they are of lower complexity.\n\nSecond, the training data is always a simple image from MNIST, and I am unsure how much this setting can generalize to other tasks, such as different data (say, music or text) or more complicated images (how do these experiments compare when we use a single data from ImageNet or CIFAR to train?). For instance, since CNNs are designed to capture invariances in natural images, it is unsurprising that they can generalize better on image data, but it would be quite astonishing if the same still holds true for acoustic data. In that case, the conclusion of this paper can be strengthened from “CNNs generalize better on image data” to “CNN generalize better”. Given the scope of the current paper, however, the best we can conclude is that “CNNs generalize better on MNIST”.\n\nLast, again regarding the fair comparison, when comparing deep CNNs versus shallow ones, it is also of interest to see that, when restricted to the same number of parameters, if the deep CNNs still exhibit worse generalization. Otherwise, if some network complexities keep growing, we cannot really tell whether it is the network architecture that induces the inductive bias or it is simply the effect of complexities.\n\nI also would like to suggest a future direction based on the idea in this paper: Comparing the inductive bias of GD versus SGD, a subject of intense study in the current literature. Since the authors considered a single training data, the results in this paper are always for GD. Now, say let us use 5 data, and compare the training of CNNs with different batch-size. Do the results differ? I think such a thought experiment would shed some light on the mysterious behaviors of the first-order algorithms that are widely used in practice.\n\nFinally, a question: another submission to ICLR2020 [1] seems to suggest that optimization methods do not play a role in generalization, which is the opposite observation of this paper. Do the authors have any insight towards this contradiction?\n\n[1] Fantastic Generalization Measures and Where to Find Them https://openreview.net/forum?id=SJgIPJBFvH", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SJlTDSnTFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies influence of different hyperparameters of neural networks: architecture, width, depth, initialization, optimizer, etc. on the generalization/memorization trade-off.\n\nTo do this, paper propose a clever trick: train a model to mimic identity function, so that output should be exactly the same, as input. This allows rich visualization and easy evaluation via correlation or MSE. Moreover, authors showed that it is possible to do the study on _single_ training example. Yet, in my opinion, the idea of using identity as training objective is even bigger contribution that the study itself.\n\nThe number of experiments is really terrific and lots of interesting observation is been made.  E.g, showing that over-parameterization by increasing width does not lead to overfitting, but the opposite is true. In the same time, it is hard for deeper networks to learn identity function regardless the width used.\n\nI definitely vote this to be the oral presentation and even for the best paper award. \n\nQuestions: \n    - Fig 14 (and similar): how it is possible, that for high train-test correlation, similarity of network outputs is high BOTH for constant prediction and identity? Or, might be I am just reading such visualization wrong. In that case, could you please make it more clear?\n    - It would be interesting to see, how resnets behave in such setup. \n    - It is surprising that He init was inferior to Xavier. Could you also try orthonormal init (Saxe et.al, ICLR 2014 https://arxiv.org/abs/1312.6120) and LSUV init (Mishkin and Matas, ICLR 2016 https://arxiv.org/abs/1511.06422)?\n\n\n****\nI would like to thank authors for the updated version. I agree with R2 that paper is relying too much on the appendix, but hope that authors could fix this somehow. \nNow I am even more convinced that paper should be accepted and is award-quality.\n    ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxFdVCItS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the inductive bias in deep neural networks. The authors train several FF image recognition networks and many CNN variants on a single image, and observe that most networks fall into one of two categories: either memorizing the output of the single training sample, or learning the identity function and generalizing to new, unseen images. The paper is clearly written, present a broad set of experiments, and provides interesting insights, that are somewhat surprising.\n\nAs someone from outside the area, my main concern with the paper is that I somehow missed the bigger picture. The authors present multiple different pieces of evidence that demonstrate the different conditions on which different model variants learn the different functions (memorization and generalization), but do not provide high level intuitions about what can be done with this information, and what are potential takeaways for the community. I would have expected to see some discussion after section 3, rather than jumping straight to the conclusions.\n\nAside from that, I think the paper puts too much of its content in the appendix (about 3 times as much content as in the main paper). \n\nMinor:\n-- section 3.2: \"... if *the a* layer ...\"", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the effect of various hyperparameters of neural networks including architecture, width, depth, initialization, optimizer, etc. on the generalization and memorization. The paper carries out a rather through empirical study of these phenomena. The authors also rain a model to mimic identity function which allows rich visualization and easy evaluation.  The reviewers were mostly positive but expressed concern about the general picture. One reviewer also has concerns about "generality of the observed phenomenon in this paper". The authors had a thorough response which addressed many of these concerns. My view of the paper is positive. I think the authors do a great job of carrying out careful experiments. As a result I think this is a good addition to ICLR and recommend acceptance.
Decision: Accept (Poster)