Year: 2019

Abstract:
Even though recent works have brought some insight into the performance improvement of techniques used in state-of-the-art deep-learning models, more work is needed to understand the generalization properties of over-parameterized deep neural networks. We shed light on this matter by linking the loss function to the output’s sensitivity to its input. We find a rather strong empirical relation between the output sensitivity and the variance in the bias-variance decomposition of the loss function, which hints on using sensitivity as a metric for comparing generalization performance of networks, without requiring labeled data. We find that sensitivity is decreased by applying popular methods which improve the generalization performance of the model, such as (1) using a deep network rather than a wide one, (2) adding convolutional layers to baseline classifiers instead of adding fully connected layers, (3) using batch normalization, dropout and max-pooling, and (4) applying parameter initialization techniques.

text: Even though recent works have brought some insight into the performance improvement of techniques used in state-of-the-art deep-learning models, more work is needed to understand the generalization properties of over-parameterized deep neural networks. We shed light on this matter by linking the loss function to the output’s sensitivity to its input. We find a rather strong empirical relation between the output sensitivity and the variance in the bias-variance decomposition of the loss function, which hints on using sensitivity as a metric for comparing generalization performance of networks, without requiring labeled data. We find that sensitivity is decreased by applying popular methods which improve the generalization performance of the model, such as (1) using a deep network rather than a wide one, (2) adding convolutional layers to baseline classifiers instead of adding fully connected layers, (3) using batch normalization, dropout and max-pooling, and (4) applying parameter initialization techniques.

heading: 1 INTRODUCTION
text: In machine-learning tasks, the main challenge a network designer faces is to find a model that learns the training data and that is able to predict the output of unseen data with high accuracy. The first part is easily achievable in current over-parameterized deep neural networks. Yet the second part, referred to as generalization, demands careful expert hand-tuning (LeCun et al. (2015), Goodfellow et al. (2016)). Modern convolutional neural network (CNN) architectures that achieve state-of-the-art results in computer-vision tasks, such as ResNet (He et al., 2016) and VGG (Simonyan & Zisserman, 2014), attain high-generalization performance. Part of their success is due to recent advances in hardware and the availability of large amounts of data. However, among models applying these resources, some outperform others. Hence, the key questions about when and why some models generalize, still remain a mystery (Neyshabur et al., 2017).
In this paper, by investigating the link between sensitivity and generalization, we get one step closer to understanding the generalization properties of neural networks. Our findings suggest a relation between the sensitivity metric and the variance term in the bias-variance decomposition of the test loss (Geman et al. (1992), Tibshirani (1996), Neal et al. (2018)). This relation provides us with some intuition about the link, when the bias is small, between sensitivity and loss. We present strong empirical results on the link between the sensitivity and the test loss in well-established deep neural networks with ReLU (Nair & Hinton, 2010) non-linearity.
Building on this relation, we can use the sensitivity metric to examine which network is more prone to overfitting, and we rediscover the generalization properties of certain structures. We provide numerical evidence that a significant decrease in the network output’s sensitivity to input perturbations can be a good predictor of the generalization capability of certain techniques used in state-of-the-art models, such as batch normalization (Ioffe & Szegedy, 2015) and He initialization (He et al., 2015). Sensitivity also supports the commonly accepted observation that depth is better than width in deep neural networks (Bengio & Delalleau (2011), Montufar et al. (2014), Telgarsky (2016), Mhaskar et al. (2017)). Furthermore, in certain settings, the sensitivity of untrained networks can be used as a proxy for the generalization error of trained networks.

heading: 2 RELATED WORK
text: Recently, Sokolić et al. (2017) suggested bounding the generalization error of deep neural networks with the spectral norm of the input-output Jacobian matrix, a measure of output sensitivity to its inputs. Empirical support for their conclusions is provided in Novak et al. (2018) through experiments on fully connected neural networks. Further research is needed to determine the conditions that are required to compare the generalization performance of models by using sensitivity metrics. For this purpose, we provide theoretical and empirical insights to the link between sensitivity and generalization by studying the relation between sensitivity and the variance term in the bias-variance decomposition of the loss function. To the best of our knowledge, this work is the first to find such a relation. In our work, we not only elaborate on the relation between sensitivity and loss for a wide range of networks (not limited to fully connected) but also empirically show that many state-of-the-art methods improve performance alongside reducing the sensitivity of the network.
To avoid overfitting in deep-learning architectures, regularization techniques are applied: for example, weight decay, early stopping, dropout (Srivastava et al., 2014), and batch normalization (BN) (Ioffe & Szegedy, 2015). Ioffe & Szegedy (2015) argues that the reason for the success of BN is that it addresses the internal-covariant-shift phenomenon. However, Santurkar et al. (2018) argues against this belief and explains that the success of BN is due to its ability to make the optimization landscape smoother. Here, we look at the success of dropout and BN from another perspective. These methods decrease the output sensitivity to random input perturbations in a same manner as decreasing the test loss, resulting in better generalization performance.
Designing neural network architectures is one of the main challenges in machine-learning tasks. One major line of work in this regard is comparing deep and shallow networks (Bengio & Delalleau (2011), Mhaskar et al. (2017), Wu et al. (2019), Ba & Caruana (2014), Montufar et al. (2014), and Simonyan & Zisserman (2014)). It is shown in Telgarsky (2016) that to approximate a deep network, a shallow network requires an exponentially larger number of units per layer. After finding a satisfactory architecture, the trainability of the network needs to be carefully assessed. In order to avoid exploding or vanishing gradients, Glorot & Bengio (2010) and He et al. (2015) introduce parameter initialization techniques that are widely used in current frameworks. By linking sensitivity and generalization, we present a new viewpoint on understanding the success of current state-of-the-art architectures and techniques.
Previous theoretical studies attempting to solve the mystery of generalization mostly include generalization error (GE) bounds that use complexity measures such as VC-dimension and Rademacher complexities (Xu & Mannor (2012), Kawaguchi et al. (2017), Arora et al. (2018), and Sokolić et al. (2017)). GE depends not only on the architecture of the network, but also on the structure of the data itself1. This is why the same network has a lower GE when trained with structured data than with random data (Zhang et al., 2016). Here, we do not study GE bounds; however, in order to find complexity measures to bound GE, we should take note of the link between sensitivity and generalization.
There has been research on sensitivity analysis in neural networks with sigmoid and tanh activation functions (Dimopoulos et al. (1995), Fu & Chen (1993), and Zeng & Yeung (2001)). Yang et al. (2013) introduce a sensitivity-based ensemble approach which selects individual networks with diverse sensitivity values from a pool of trained networks. Piche (1995) performs a sensitivity analysis in neural networks to determine the required precision of the weight updates in each iteration. In this work, we extend these results to networks with ReLU non-linearity with a different goal; to study the relation between sensitivity and generalization error in the state-of-the-art deep neural networks.
The metrics used for evaluating the network performance on training data cannot reflect generalization, because an over-parameterized model can achieve zero training loss for networks trained with randomly labeled data (Zhang et al., 2016). There have been recent attempts to predict the test loss for supervised-learning tasks (Novak et al. (2018), Jiang et al. (2018), and Wang et al. (2018)). Philipp & Carbonell (2018) introduces the non-linearity coefficient (NLC) as a gradient-based complexity measure of the neural network, which is empirically shown to be a predictor of the test error for fully connected neural networks. According to our results on both fully connected and convolutional neural networks, sensitivity is also a predictor of the test error, even before the networks are trained, which suggests sensitivity as a computationally inexpensive architecture-selection metric.
1In this work, we do not investigate the structure of the data set.
Paper Outline. We formally define loss and sensitivity metrics in Section 3.1 and Section 3.2, respectively. In Section 4, we state the main findings of the paper and present the numerical and analytical results supporting that. Later in Section 5, we propose a possible proxy for generalization properties of certain structures and certain methods. Finally in Section 6, we further discuss the observations followed up by a conclusion in Section 7. The empirical results presented in the paper are for an image-classification task on the CIFAR-10 dataset. In Appendix 8.6, we present the empirical results for MNIST and CIFAR-100 datasets. In Appendix 8.7, we present the empirical results for a regression task with the Boston housing dataset.

heading: 3 PRELIMINARIES
text: Consider a supervised-learning task, where the model predicts ground-truth output y ∈ Y := RK for an input x ∈ X := RD. The predictor Fθ : X → Y is a deep neural network parameterized by the parameter vector θ that is learned on the training dataset τt by using the stochastic learning algorithm A. The training dataset τt and the testing dataset τv consist of i.i.d. samples drawn from the data distribution p. With some abuse of notation, we use ∼ when the samples are uniformly drawn both from a set of samples and from a probability distribution.

heading: 3.1 LOSS
text: Our main focus is a classification task where the loss function is the cross-entropy criterion. The average test loss can be defined as
L = Eθ∗ [Lθ∗ ] = Eθ∗ [ E(x,y)∼τv [ − K∑ k=1 yk logF kθ∗(x) ]] , (1)
where θ∗ is the random2 parameter vector found by A minimizing the train loss defined on τt, K is the number of classes and F kθ∗ is the k-th entry of the vector Fθ∗ , which is the output of the softmax layer, i.e., Fθ∗ = softmax(fθ∗(x)), where fθ∗(x) is the output of the last layer of the network. In classification tasks, the output space is Y := [0, 1]K , and the output vector is the probability assigned to each class.

heading: 3.2 SENSITIVITY
text: Let us inject an external noise to the input of the network and compute the noise in the output. If the original input vector is x ∈ X and we add an i.i.d. normal noise vector εx ∼ N (0, σ2εxI) to the input, then the output noise due to the input noise εx ∈ X is εy = fθ(x + εx) − fθ(x) ∈ Y . We use the variance of the output noise3, averaged over its K entries, as a measure of sensitivity: Sθ = Var(εy). The average sensitivity is
S = Eθ[Sθ] = Eθ [Var(εy)] = Eθ [ Varx,εx [ 1
K K∑ k=1 εky
]] , (2)
where εky is the k-th entry of the vector εy. In the following sections, we use Sbefore = Eθ[Sθ] and Safter = Eθ∗ [Sθ∗ ] when the expectation is over the network parameters before and after training, respectively. We consider unspecific sensitivity (the average over the entries of the output noise), which requires unlabeled data samples, as opposed to specific sensitivity (the sensitivity of the output of the desired class) (Tartaglione et al., 2018). By expanding Equation (2) up to the first order, the sensitivity S is approximated by the product of the variance of the input noise vector σ2εx and the square of the Frobenius norm of the Jacobian of the output of the network (Novak et al., 2018). In experiments, we prefer S to the Jacobian, because in order to compute S it is enough to look at the network as a black box that given an input, generates an output, without requiring further knowledge of the model.
2The randomness is introduced by the stochastic optimization algorithm A and the randomized parameter initialization technique.
3Note that we consider the output of the neural network and not the output of the softmax layer. The softmax layer can be interpreted as a normalizing layer pushing the values to be between 0 and 1.

heading: 4 SENSITIVITY VS. LOSS

heading: 4.1 MAIN OBSERVATION
text: After training, an ideal predictor is expected to have a good generalization ability. An ideal predictor should also be robust; given similar inputs, the outputs should be close to each other. Assuming that the unseen data is drawn from the same distribution as the training data, there should be a link between the two concepts of robustness and generalization. Robustness here is the average-case robustness, not the worst-case robustness (adversarial robustness). We measure the robustness by computing S (Equation (2)), and considering near-zero train loss, we refer to the test loss L (Equation (1)) as the generalization error. According to our observations on a wide set of experiments, we find a rather strong relation between the sensitivity S and the generalization error L. State-of-the-art networks decrease the generalization error alongside with the sensitivity of the output of the network with respect to the input (Figure 1).

heading: 4.2 NUMERICAL EXPERIMENTS
text: Many factors influence the generalization performance of deep-learning models, among which network topology, initialization technique, and regularization method. We study the influence of these three factors on the sensitivity S and keep all the other factors, including the learning algorithm, the same. We refer to fully connected neural networks as FC and convolutional neural networks as CNN. First, we examine the relation between Safter and L for different architectures, different initialization techniques, and different regularizations. We observe a strong link between Safter and L; a lower sensitivity has a lower test loss (Figures 2 and 3). This strong link suggests that, by comparing the sensitivity Safter, we can simply compare generalization performances of multiple neural networks that are fully trained (with various hyper-parameters, types of layer and regularization methods). Using sensitivity as a proxy for test loss is particularly advantageous in settings where labeled training data is limited; assessing generalization performance can be then done without having to sacrifice training data for the validation set. Next, when initialization is fixed to the standard normal distribution and no explicit regularization technique is applied, we investigate the link between Sbefore and L (Figure 4 in Section 6.1). We see again a clear relation between Sbefore and L; Sbefore can potentially be used as an architecture-selection metric before training the models.

heading: 4.3 BIAS-VARIANCE DECOMPOSITION
text: In this section, a crude approximate relation between sensitivity and generalization error is established through the link between sensitivity and the variance term in the bias-variance decomposition of the mean square error. First, we find the link between the cross-entropy loss and the mean square error. Then, we present the relation between sensitivity and the variance term in the bias-variance decomposition of the mean square error. Finally, the link between sensitivity S and generalization error L is established.
When the predictor Fθ∗(x) assigns the probability F cθ∗(x) to the correct class c and 1− F cθ∗(x) to another class (see Appendix 8.3 for details), the cross-entropy loss L can be approximated as
L ≈ E(x,y,θ∗)  1√ 2 √√√√ K∑ k=1 ( F kθ∗(x)− yk )2 . (3) We roughly approximate the right-hand side in Equation (3) with √ LMSE/2, where LMSE is the mean square error (MSE) criteria and is defined as
LMSE = Eθ∗ [Lθ∗MSE ] = Eθ∗ [ E(x,y)∼τv [ ‖Fθ∗(x)− y‖2 ]] . (4)
Consider the classic notion of bias-variance decomposition for the MSE loss (Geman et al. (1992)), where the generalization error is the sum of three terms: bias, variance and noise, i.e., LMSE = εbias + εvariance + εnoise. In this work, we consider the labels to be noiseless and neglect the third term εnoise. The bias term is formally defined as
εbias = Ex,y [ ‖Eθ∗ [Fθ∗(x)]− y‖2 ] ,
and the variance term is formulated as
εvariance = K∑ k=1 Ex [ Varθ∗(F kθ∗(x)) ] . (5)
Let us now draw an again crude approximate relation between εvariance and S under strong assumptions on the probability distributions of θ, x, and εx (refer to Appendix 8.2 for more details). Given a feed-forward neural network with M hidden layers and Hl, 1 ≤ l ≤M , units per layer, where the non-linear activation function is positive homogeneous4 with parameters α and β (Equation (10) in Appendix 8.2), we have
εvariance ≈ ( K − 1 K )( S · σ 2 x
σ2εx + χ
) , (6)
4ReLU is a positive homogeneous function with α = 1 and β = 0.
where
χ = 1
K M∑ l=1 σ2bl M∏ i=l+1 ( α2 + β2 2 ) σ2wiHi, (7)
and K is the number of units in the output of the softmax layer and σ2wl , σ 2 bl , σ2x, and σ 2 εx are the second moment of weights and biases of layer l, input x and input noise εx, respectively. Equation (7) can be extended to convolutional neural networks by replacing Hi with fanin of weights of layer i.
Given an infinite amount of training data, the bias represents the best performance of our model which can be approximated by the training loss (Mehta et al. (2019), Ng, Fortmann-Roe (2012)). In our experiments, the training loss is close to zero, hence if we neglect the bias term εbias in the test loss we have,
L ≈
√ 1
2 ( K − 1 K )( S · σ 2 x
σ2εx + χ
) , (8)
where χ is given by Equation (7). In experiments, we observe that σ2bl is usually very small or zero (for instance in ResNets bl = 0), making χ ≈ 0. According to Equation (6) and the relation between LMSE and L, to compare networks with the small value of εbias (which is usually the case in deep neural networks where the bias is approximated with the near-zero training loss), the test loss can be approximated by the sensitivity following Equation (8). Despite the strong assumptions and crude approximations to get Equation (8), the numerical experiments show a rather surprisingly good match with Equation (8) (Figures 1, 2 and 3), when χ is neglected in Equation (8). It is interesting to note that the right-hand side of Equation (8) is computed without requiring labeled data points.
If εbias can no longer be approximated by the training loss, which may in part explain the poorer match in lower values of Figure 1, we need more training data to make this approximation valid. In our experiments, we train the networks with only a subset of the training dataset, we also show in Appendix 8.8 that by training with more data samples, numerical results become closer to Equation (8).

heading: 5 SENSITIVITY AS A PROXY FOR GENERALIZATION
text: In this section, we argue that methods improving the generalization performance of neural networks remarkably reduce the sensitivity S. In particular, we revisit some common notions regarding generalization in deep neural networks: adding convolutional layers instead of fully connected layers, using deeper networks instead of wider ones, adding dropout, batch normalization (BN) and max-pooling layers, and initializing the network parameters by techniques such as Xavier and He.

heading: 5.1 COMPARING DIFFERENT ARCHITECTURES
text: Convolutional vs Fully Connected Layers. The relation between the sensitivity S and the generalization error L supports the common view that CNNs outperform FCs in image-classification tasks. We empirically observe that, given a CNN and an FC with the same number of parameters, the CNN has lower sensitivity and test loss than the FC. Moreover, some CNNs with more parameters than FCs have both lower sensitivity and lower test loss, even though they are more over-parameterized. Let us start from a baseline classifier with one hidden layer (2 layers in total), and we compare the effect of adding another fully connected layer versus adding a convolutional layer in Figure 2(e). We vary the number of parameters of 1-layer CNNs (which consist of 2 fc layers and 1 conv layer) from 450k to 10M by increasing the number of channels and hidden units, whereas the number of parameters for 3-layer FCs varies from 320k to 1.7M. Despite the large number of parameters of CNNs, they suffer from less overfitting and have a lower sensitivity S than FCs. Next, let us compare a FC to a CNN with the same number of parameters in Figure 2(e): a 3-layer FC with 140 units in each layer (yellow mark) and a 1-layer CNN with 5 channels and 100 units (green mark), both have 450k parameters. The CNN has remarkably lower sensitivity and test loss than the FC, which indicates better performance compared to the FC with the same number of parameters.
Depth vs Width. Consider a feedforward FC with ReLU activation function where all the network parameters follow the standard normal distribution and are independent from each other and from the
input. If we have M layers with H units in each hidden layer, K units in the output layer and the input layer with D units, then (see Appendix 8.4 for details)
S = D
K
( H
2
)M σ2εx . (9)
According to Equation (9), considering two neural networks with the same value for HM , one being deep and narrow (higher M and lower H), and the other being shallow and wide (lower M and higher H), subject to the same noise level σ2εx , the deeper network has lower sensitivity S. Assuming both networks have near-zero training losses, then, depth is better than width regarding generalization in fully connected neural networks. The empirical results in Figure 2(a) support Equation (9). For instance, a 4-layer FC with 500 units per layer (the last point among 4-layer FCs), has the same value for (H2 )
M as a 5-layer FC with 165 units per layer (the 4th point among 5-layer FCs). In Figure 2(a), these two networks have the same value for both sensitivity and loss, and all narrower 5-layer networks (with 100, 120, and 140 units) have better performance than the wide 4-layer network (with 500 units). Note that Equation (9) only holds for networks with parameters drawn from the standard normal distribution and does not hold when the parameter initialization is Xavier or He.

heading: 5.2 REGULARIZATION AND INITIALIZATION METHODS
text: Figures 2(b) and 2(d) show the sensitivity Safter versus the test loss L, for different regularization methods. In particular, we study the effect of dropout and BN on the sensitivity in the FCs; and we apply dropout, BN and max-pooling for the CNNs. The results are consistent with the relation between sensitivity S and loss L. For all mentioned regularization techniques, we observe a shift of the points towards the bottom left; this shift suggests that these techniques improve generalization by decreasing the network sensitivity to input perturbations. This is especially noticeable in the BN case, where both the sensitivity and test loss decrease dramatically. This suggests that batch normalization improves performance by making the network less sensitive to input perturbations.
Another interesting observation is the effect of various parameter initialization techniques on the sensitivity and loss values, after the networks are trained (Figure 3). We consider four initialization techniques for network parameters in our experiments: (i) Standard Normal distribution (SN), (ii) Xavier (Glorot & Bengio, 2010) initialization method with uniform distribution (XU), (iii) He (He et al., 2015) initialization method with uniform distribution (HU), and (iv) He initialization method with normal distribution (HN). As shown in Figure 3, the relation between sensitivity Safter and test loss L provides us a new view-point of the success of the state-of-the-art initialization techniques; the He initialization method with normal distribution has the best generalization performance, alongside the lowest sensitivity value.

heading: 6 DISCUSSION

heading: 6.1 SENSITIVITY OF UNTRAINED NETWORKS AS A PROXY FOR THE TEST LOSS
text: A similar trend, as in Section 4, is observed for neural networks that are not yet trained. In Figure 4, the sensitivity Sbefore is measured before the networks are trained, and the test loss L is measured after
the networks are trained on a subset of the training dataset. The parameters in the fully connected and convolutional networks are initialized by sampling from the standard normal distribution, and no explicit regularization (dropout, BN, and max-pooling) is used in the training process. These two conditions are necessary, because regularization techniques only affect the training process, hence Sbefore is the same for networks with or without regularization layers, and the He and Xavier initialization techniques force the sensitivity to be fixed regardless of the number of units in hidden layers. Hence, under these two conditions, the generalization performance of untrained networks with different architectures can be compared. The strong link between the sensitivity of untrained networks Sbefore and the test loss L suggests that generalization of neural networks can be compared before the networks are even trained, making sensitivity a computationally inexpensive architectureselection method.

heading: 6.2 FINAL REMARKS
text: It is important to note that sensitivity is not the only factor affecting generalization. The sensitivity metric does not address the challenges brought by Zhang et al. (2016); the sensitivity of a randomlabeled input is the same as the sensitivity of a true-labeled input, with very different loss values. The pixel-wise linear input perturbations, considered in our experiments, might not be realistic; ideally, we would like to perturb the input in the latent space of the generative model of the input image. Also, the relation between S and L, requires the non-linearity to be positive homogeneous, hence the generalization properties of networks with sigmoid and tanh activation functions remain unexplained. It is not possible to find a single metric to explain the generalization properties across a space as large as deep neural networks and across the non-convex landscapes of deep-learning problems. But the sensitivity metric presented in this work is strongly related to generalization, and even though Equation (8) was derived under very strong assumptions and crude approximations, it is surprisingly quite close to the empirical results in a wide set of settings.
The sensitivity metric can be affected by re-scaling. If we re-scale all the indices of the very last layer of the neural network, the accuracy stays the same as the network predicts the same class, however, both the test loss and sensitivity are multiplied by the square of the scaling factor. Therefore, the relation highlighted in this paper between sensitivity and generalization error cannot always be extended to a relation between sensitivity and accuracy. Also note that, if we re-scale the input x, define a new input xnew = αx, and de-scale the output fnew(·) = f(·)/α, then due to homogeneity of f , we have Lnew = L, however, Snew = S/α2. Hence sensitivity cannot replace test loss and to compare the generalization error of models by using their sensitivity, the comparison needs to be made fairly; the input of both networks should be drawn from the same distribution.

heading: 7 CONCLUSION
text: We find that the sensitivity metric is a strong indicator of overfitting. Given multiple networks, with near-zero training loss, to choose from with various hyper-parameters, the best architecture appears to be the one with the lowest sensitivity value. Sensitivity can potentially be used as an early stopping criterion and as an architecture-selection method; given multiple networks to choose from by only computing the sensitivity to the given input, the best model is the one with the lowest sensitivity. One of the advantages of the sensitivity metric is that it can provide a loose prediction of the test loss without the use of any labeled data. This is especially important in applications where generating labels requires expensive experiments.

heading: 8 APPENDIX

heading: 8.1 EXPERIMENTAL DETAILS
text: The CIFAR-10 dataset5 is used for the experiments presented in the paper. The fully connected neural networks have the same number of units in the hidden layers, varying from 100 to 500 with a step size of 20. For the convolutional neural networks the number of channels in convolutional layers vary from 5 to 25 with a step size of 5 (note that each time a channel is added in the convolutional layers, an extra 20 units is added to the fully connected layers of the CNN accordingly). As it is computationally expensive to reach zero training loss for the entire dataset, we choose a subset of the training set containing 1000 samples of the CIFAR-10 dataset. Zero training loss is necessary for a fair comparison between different networks since we would like to have the same value for εbias and εnoise among them. For the optimization algorithm, we choose the Adam optimizer with its default parameters and we initialize the weights and biases with random values drawn from a distribution according to the initialization technique stated in each figure. The nonlinearity is set to be the ReLU function throughout the experiments. We stop the training when the training loss reaches below the threshold 10−5 for 10 times. In case this condition is not met, we stop the training after 2000 epochs (each epoch is iterations over the mini-batches of the entire training set). The noise added to the input image is a random tensor with the same size as the input and is drawn from the Gaussian distribution with zero mean and 0.1 standard deviation. The output noise is first averaged over all its K entries (for CIFAR-10 the number of classes is K = 10), then we take its variance over inputs of the testing dataset and the input noise, finally it is averaged over multiple runs.
Using the notations:
• Conv(number of filters, kernel size, stride, padding) • Maxpool(kernel size) • Linear(number of units) • Dropout(dropout rate)
for layers of a convolutional neural network where Conv and Linear layers also include the ReLU non-linearity except the very last linear layer. The configurations that are used are:
• The Alexnet (Krizhevsky et al., 2012): Conv(h, 3, 2, 1) - Maxpool(2) - Conv(3*h, 3, 1, 1) - Maxpool(2) - Conv( 6*h, 3, 1, 1) - Conv(4*h, 3, 1, 1) - Conv(4*h, 3, 1, 1) - Maxpool(2) - Dense layer - Dropout(0.5) - Linear(4096) - Dropout(0.5) - Linear(4096) - Linear(K) where h ∈ [16, 32, 48, 64, 80]
• VGG13 (Simonyan & Zisserman, 2014) : 2 x Conv(64*s, 3, 1, 1) - Maxpool(2) - 2 x Conv(128*s, 3, 1, 1) - Maxpool(2) - 2 x Conv(256*s, 3, 1, 1) - Maxpool(2) - 2 x Conv(512*s, 3, 1, 1) - Maxpool(2) - 2 x Conv(512*s, 3, 1, 1) - Maxpool(2) - Avgpool(2) - Dense layer - Linear(K) where s ∈ [0.25, 0.5, 1, 1.5, 2] and all Conv layers have batch normalization
• Each block of a ResNet (He et al., 2016) configuration: 2 x Conv(h, 3, 1, 1) + Conv(h, 1, 1, 1) which Conv layers include BN and ReLU and the result of the summation goes into a ReLU layer and h is the number of channels.
VGG16 is the same as VGG13 with the difference that it has three layers in the last three blocks. VGG11 configuration is the same as tVGG13 except that in the first and second block it has one convolutional layer instead of 2. VGG19 is the same as VGG13 except that there is 4 conv layers instead of 2 in the last three blocks. ResNet18 has 2 blocks with h=64*s, 2 blocks with h=128*s, 2 blocks with h=256*s, and 2 blocks with h=512*s where s ∈ [0.25, 0.5, 1, 1.5, 2]. ResNet34 has 3 blocks with h=64*s, 4 blocks with h=128*s, 6 blocks with h=256*s, and 3 blocks with h=512*s where s ∈ [0.25, 0.5, 1, 1.5, 2].

heading: 8.2 COMPUTATION OF EQUATION (6)
text: Computations of this section do not depend on the stage of the training, hence θ denotes the parameter vector at any stage of training. Let us recall the sensitivity metric (Equation (2)) definition
S = Eθ [Varx,εx [εy]] , where εy = 1/K ∑K k=1 ε k y and εky is the k-th entry of output noise vector εy and is
εky = f k θ (x+ εx)− fkθ (x) u εx · ∇>x fkθ (x),
where we apply a first order Taylor expansion of the output. For a one hidden layer neural network with D input units, H hidden units, and K output units, we have θ = {w1 ∈ RD×H , w2 ∈ RH×K , b1 ∈ RH , b2 ∈ RK}
5https://www.cs.toronto.edu/~kriz/cifar.html
where wl and bl are the weights and biases of layer l (l = 1 is the hidden layer and l = 2 is the output layer) which are independently drawn from a zero-mean normal distribution: w1 ∼ N (0, σ2w1I), w2 ∼ N (0, σ 2 w2I), b1 ∼ N (0, σ2b1I), and b2 ∼ N (0, σ 2 b2 I) (which has been studied in Bellido & Fiesler (1993)). We have
fkθ (x) = H∑ h=1 whk2 a(p h) + bk2 ,
where wjkl is the weight connecting unit j in layer l to unit k in layer l+1, b h l is the bias term added to unit h in layer l + 1, ph is the output of the linear transformation in the hidden unit h, i.e.,
ph = D∑ d=1 wdh1 x d + bh1 ,
and the non-linear activation function a(·) is a positive homogeneous function of degree 1; i.e.,
a(x) =
{ αx x > 0,
βx otherwise, (10)
where α and β are non-negative hyper-parameters. ReLU follows Equation (10) with α = 1 and β = 0. By applying the chain rule we obtain
εky = D∑ d=1 εdx ∂fkθ (x) ∂xd
= D∑ d=1 εdx H∑ h=1 whk2 w dh 1 ∂a(ph) ∂ph .
Therefore, we have
εy = 1
K K∑ k=1 H∑ h=1 D∑ d=1 εdxw hk 2 w dh 1 ∂a(ph) ∂ph .
The network parameters are assumed to be independent, and it is assumed that x ⊥ θ, and εx ⊥ {θ, x}. Moreove, the entries of the input vector x are independent from each other with the same second moment, i.e., σ2x = E[(xd)2] for 1 ≤ d ≤ D. Consider the input noise εx to be a vector of zero mean random variables, hence S = Eθ,x,εx [(εy) 2]. Then sensitivity becomes
S = 1
K2 K∑ k=1 H∑ h=1 D∑ d=1 Eεx [(ε d x) 2]Eθ,x
[ (whk2 ) 2(wdh1 ) 2 ( ∂a(ph)
∂ph
)2]
= 1
K2 K∑ k=1 H∑ h=1 D∑ d=1 σ2εxσ 2 w2σ 2 w1 α2 + β2 2 , (11)
where the second equation is followed by computing the expectation for zero-mean normal parameters. Let
var = Ex [Varθ[out]] , (12) where out = 1/K ∑K k=1 f k θ (x). Because of the homogeneity of the non-linearity a(·), we have a(ph) = ph · ∂a(p h)
∂ph . Hence
out = 1
K K∑ k=1 [ H∑ h=1 whk2 ( D∑ d=1 wdh1 x d + bh1 ) ∂a(ph) ∂ph + bk2 ] .
Because the parameters are zero-mean, var = Eθ,x [ out2 ] and we have
var = 1
K2 K∑ k=1 H∑ h=1 D∑ d=1 E
[ (xd)2(whk2 ) 2(wdh1 ) 2 ( ∂a(ph)
∂ph
)2]
+ 1
K2 K∑ k=1 H∑ h=1 E [ (whk2 ) 2 ] E [ (bh1 ) 2 ( ∂a(ph) ∂ph )2] + 1 K2 K∑ k=1 E [ (bk2) 2 ]
= 1
K2 K∑ k=1 H∑ h=1 D∑ d=1 σ2xσ 2 w2σ 2 w1 α2 + β2 2
+ 1
K2 K∑ k=1 H∑ h=1 σ2w2σ 2 b1 α2 + β2 2 + 1 K2 K∑ k=1 σ2b2 ,
which is followed by taking the expectations over the parameters with zero-mean normal distributions. Therefore, we obtain
var = S · σ 2 x σ2εx + H K σ2w2σ 2 b1 α2 + β2 2 + σ2b2 K ,
where σ2 is the notation used for the second moment of a random variable. Following the same computations for a neural network with M hidden layers, we have
var = S · σ 2 x
σ2εx +
1
K M∑ l=1 σ2bl M∏ i=l+1 α2 + β2 2 σ2wiHi, (13)
where K is the number of units of the output layer M + 1. We refer to second term in the right-hand side of Equation (13) as χ. Its value is a very rough approximation given the numerous assumptions made above, but in practice it can often be neglected because σ2bl is very small or zero (the ResNet configurations do not have biases) in most of our experiments. The first order Taylor expansion for an arbitrary function at the average of the input is g(x) ≈ g(E[x]) + g′(E[x])(x− E[x]). Taking the variance of this equation we have
Var(g(x)) ≈ ( g′(E[x]) )2 Var(x). Here the function g(·) is the softmax function
F kθ (x) = exp(fkθ (x))∑K i=1 exp(f i θ(x)) .
The input of the softmax function is a K-dimensional vector, so the first order Taylor expansion includes the vector-matrix multiplication of the covariance and the input vector. We assume the outputs of the last layer are independent from each other, so the covariance matrix is considered a diagonal matrix. Because the parameters are considered to be zero-mean, the input of the softmax has zero mean, E[fkθ (x)] = 0 for 1 ≤ k ≤ K, then
Var(F kθ (x)) ≈ K∑ i=1 ( ∂F iθ(x) ∂f iθ(x) )2 Var(f iθ(x))
≈ ( 1 K · ( 1− 1 K ))2 Var(fkθ (x)) + ( 1 K2 )2 K∑ i=1 i 6=k Var(f iθ(x)),
since softmax(0) = 1/K. Therefore,
εvariance = K∑ k=1 Ex [ Var(F kθ (x)) ] ≈ ( (K − 1)2 K4 + K − 1 K4 ) ·K2var = ( K − 1 K )( S · σ 2 x σ2εx + χ ) ,
which completes the computations.

heading: 8.3 THE RELATION BETWEEN THE CROSS ENTROPY LOSS AND THE MEAN SQUARE ERROR
text: We rewrite the cross-entropy loss (Equation (1)) as L = Eθ∗ [Lθ∗ ] = Ex,c,θ∗ [− log(F cθ∗)] ,
where 1 ≤ c ≤ K is the index of the true class for the input x, i.e., yc = 1 and yk = 0 for k 6= c . For simplicity we use the notation F cθ∗ instead of F c θ∗(x) in this section. For the MSE loss we have
LMSE = Ex,y,θ∗ [ K∑ k=1 ( F kθ∗ − yk )2] .
Because K∑ k=1 F kθ∗ = F c θ∗ + K∑ j=1 j 6=c F jθ∗ = 1 the summation inside the above expectation can be rewritten as
K∑ k=1 ( F kθ∗ − yk )2 = (1− F cθ∗)2 + K∑ j=1 j 6=c ( F jθ∗ )2
= (1− F cθ∗)2 + (1− F cθ∗)2 − K∑ i=1 i 6=c K∑ j=1 j 6=i,c F iθ∗F j θ∗ = 2 (1− F cθ∗)2 − K∑ i=1 i6=c K∑ j=1 j 6=i,c F iθ∗F j θ∗ .
Since 0 ≤ F jθ∗ ≤ (1− F c θ∗) for 1 ≤ j ≤ K, j 6= c and K∑ j=1 j 6=c F jθ∗ = 1− F c θ∗ , the above equation is bounded as
( K
K − 1
) (1− F cθ∗)2 ≤ K∑ k=1 ( F kθ∗ − yk )2 ≤ 2 (1− F cθ∗)2 . (14)
The minimum occurs when F jθ∗ = (1− F c θ∗)/(K − 1) for 1 ≤ j ≤ K, j 6= c and the maximum occurs when all the remaining probability (i.e., 1 − F cθ∗ ) is given to one class besides the true class c, and the rest of the classes are assigned with zero probability. By applying the first order Taylor expansion for logarithm we have
− log(F cθ∗) ≈ 1− F cθ∗ ,
where following the inequality in Equation (14) we have√√√√1 2 K∑ k=1 ( F kθ∗ − yk )2 ≤ 1− F cθ∗ ≤ √√√√K − 1 K K∑ k=1 ( F kθ∗ − yk )2 .
Intuitively, the upper bound above is preferable in practice, because we would like to be less confidant in assigning probabilities to wrong classes. If we take the expectation of the above inequality because of Jenson’s inequality, the upper bound is upper bounded by √
K−1 K √ LMSE. However, here we consider the worst case approximation
and approximate 1− F cθ∗ with the lower bound above. In practice, we observe that this approximation holds, and the network overfits very confidently and assigns the probability 1− F cθ∗ to a wrong class and zero to the remaining classes. Hence, by roughly approximating the expectation of a squared root with the squared root of expectation, we have
L ≈ √ LMSE 2 .

heading: 8.4 COMPUTATION OF EQUATION (9)
text: Consider a feedforward FC with ReLU activation function where i.i.d. zero mean random noise εx with variance σ2εx is added to the input. Then, assuming the output noise entries are independent from each other, we have
S = 1
K2 K∑ k=1 Var [ εky ] = 1 K2 K∑ k=1 E [ (εky) 2 ] .
If we have M hidden layers with Hl, 1 ≤ l ≤ M units per layer, assuming the parameters are i.i.d. and independent from the input noise εx, and are drawn from the standard normal distribution, following the same computations as in Equation (11) for a network with M hidden layers, D input units and K output units,
S = 1
K2 K∑ k=1 Dσ2εx M∏ l=1 Hl 2 .
If all the hidden layers have the same number of units, H1 = H2 = · · · = HM = H , then,
S = D
K
( H
2
)M σ2εx .

heading: 8.5 CIFAR-10 EXPERIMENTS
text: Figure 5 presents the effect of different initialization techniques, and of adding dropout and batch normalization layers to fully connected and convolutional neural networks trained on 1000 samples of the CIFAR-10 training dataset, and evaluated on the entire CIFAR-10 testing dataset. We observe again the strong relation between sensitivity Safter and generalization error L and the effect of these techniques on both Safter and L. In Figure 6, we present the empirical results on the relation between var defined in Equation (12) and S defined in Equation (2). We experiment for 5 cases, where we change the second moment of the input σ2x and the input noise σ2εx . In Figures 6(a) and 6(b), the original CIFAR-10 images are considered and in Figures 6(c), 6(d) and 6(e), we normalize the inputs accordingly. In all figures, the empirical relation between var and S shows a good match with Equation (13). We further experiment on image classification tasks for the MNIST and CIFAR-100 datasets in Appendix 8.6. We also provide numerical experiments for a regression task for the Boston house price prediction in Appendix 8.7.

heading: 8.6 MNIST AND CIFAR-100 EXPERIMENTS
text: In this section, we present the experimental results for networks trained on 6000 samples of the MNIST6 training dataset and evaluated on the entire MNIST testing dataset. Figures 7(a) and 7(b) show the results for fully connected neural networks with different number of layers and units and using regularization techniques batch normalization and dropout. In Figures 7(c) and 7(d), the results for convolutional neural networks are presented. Finally, in Figures 7(e) 7(f), the results on the comparison of the sensitivity of untrained networks Sbefore with the test loss L after the networks are trained, are presented. Figure 8 presents the sensitivity S versus the loss L for networks trained on the 1000 samples of the CIFAR-100 dataset7. The results on these two datasets are consistent with the rest of the paper, and once again we observe the relation between sensitivity and generalization and the effect of state-of-the-art techniques on both sensitivity and generalization.

heading: 8.7 REGRESSION TASK AND MSE LOSS
text: In this section, we investigate the relation between sensitivity and generalization error for regression tasks with mean square error criteria. The loss function in this setting is defined as
LMSE = Eθ∗ [Lθ∗MSE ] = Eθ∗ [ E(x,y)∼τv [ (fθ∗(x)− y)2 ]] .
where θ∗ is found by minimizing the mean square error on training dataset τt using the stochastic learning algorithm A. Note that in this setting the output is the last layer of the neural network, the softmax layer is not added in this setting and the output layer has 1 unit, i.e., K = 1 and y is a scalar. The bias and variance term are
6http://yann.lecun.com/exdb/mnist/ 7https://www.cs.toronto.edu/~kriz/cifar.html
defined as εbias = Ex,y [ (Eθ∗ [fθ∗(x)]− y)2 ] ,
and εvariance = Ex [Varθ∗(fθ∗(x))] ,
respectively. We consider the Boston housing dataset8 where the objective is to predict the price of a house given 14 features (including crime rate, distance to employment centers, etc.). Figure 9 shows the results for comparing sensitivity and test loss among fully connected neural networks with 3-8 layers and 100-500 hidden units per
8https://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html
layer; the networks are trained on 70% of the dataset and then evaluated on the remaining 30%. The networks could not get to zero training loss, so we stopped the training after 1000 epochs. The results are consistent on the relation between sensitivity S and generalization error which for the regression task is LMSE (Figure 9(e)). For a more detailed view, we observe that sensitivity is related to the variance in the bias-variance decomposition of the MSE loss (Figure 9(d)), and the MSE loss is the summation of the bias term and the variance term (Figure 9(c)).
8.8 DISCUSSION REGARDING εBIAS
In this section, we present the results comparing Safter vs. L when the networks are trained on different numbers of training samples (Figures 10(b) and 10(c)) and at different stages of training (Figure 10(d)) to validate the approximation made in Equation (8) where we neglect εbias and εnoise. Figure 10(a) shows sensitivity versus loss after the networks are trained on a subset of 1000 samples of the CIFAR-10 training dataset. Clearly, the approximations made in the computation of Equation (8) do not hold for ResNet18 and ResNet34 networks and the match is poor, contrary to the other part. Figure 10(b) shows that this problem can be explained (at least in part) by training the networks with more samples. For instance, in Figure 10(b) the yellow mark is ResNet18 with s=1, and the green mark is Resnet34 with s=0.5, and the transition of the results, towards the linear relation between logS and logL, is clearly observed as we add more training data samples in the training process. Therefore, the larger the number of training samples, the better the approximation εbias ≈ trainloss becomes and εvariance becomes the dominant term in the test loss. Figure 10(d) shows the effect of the stage of the training. Both the sensitivity S and the loss L are computed at different stages of training (with some abuse of notation for L). In this figure, we observe the effect of the stage of training on the approximations made for computing Equation (8). At initial stages of the training, the bias εbias and noise εnoise term in the test loss cannot be neglected.

Review summaries:
This paper examines generalization performance of various neural network architectures in terms of a sensitivity metric that approximates how the error responds to perturbations of the input. A crude argument is presented for how the proposed sensitivity metric captures the variance term in the standard bias-variance decomposition of the loss. A number of experimental results are presented that show strong correlation between the sensitivity metric and the empirical test loss.