Year: 2021

Abstract:
In this work, we show that training with SGD on ReLU neural networks gives rise to a natural set of functions for each image that are not perfectly correlated until later in training. Furthermore, we show experimentally that the intersection of paths for different images also changes during the course of training. We hypothesize that this lack of correlation and changing intersection may be a factor in explaining generalization, because it encourages the model to use different features at different times, and pass the same image through different functions during training. This may improve generalization in two ways. 1) By encouraging the model to learn the same image in different ways, and learn different commonalities between images, comparable to model ensembling. 2) By improving algorithmic stability, as for a particular feature, the model is not always reliant on the same set of images, so the removal of an image may not adversely affect the loss.

text: In this work, we show that training with SGD on ReLU neural networks gives rise to a natural set of functions for each image that are not perfectly correlated until later in training. Furthermore, we show experimentally that the intersection of paths for different images also changes during the course of training. We hypothesize that this lack of correlation and changing intersection may be a factor in explaining generalization, because it encourages the model to use different features at different times, and pass the same image through different functions during training. This may improve generalization in two ways. 1) By encouraging the model to learn the same image in different ways, and learn different commonalities between images, comparable to model ensembling. 2) By improving algorithmic stability, as for a particular feature, the model is not always reliant on the same set of images, so the removal of an image may not adversely affect the loss.

heading: 1 INTRODUCTION
text: Determining why neural networks generalize remains an interesting open problem. Training often succeeds even without the use of explicit regularizers like Dropout Srivastava et al. (2014), and even when the model is trained all the way to 100% training accuracy, or in the presence of over-parametrization Zhang et al. (2021). Existing bounds using capacity control Neyshabur et al. (2019), e.g. Rademacher complexity or VC dimension are difficult to analyze when there is zero label noise and zero empirical risk Belkin et al. (2018). Several interesting approaches have been explored to explain the generalization phenomenon. These include approaches based on applying algorithmic stability Bousquet & Elisseeff (2000) to SGD Hardt et al. (2016) Kuzborskij & Lampert (2018) , PAC Bayes based bounds Dziugaite & Roy (2017) approaches exploring properties of neural network functions like elasticity He & Su (2019). It has also been hypothesized that neural networks have a spectral bias towards low frequency functions Rahaman et al. (2019) . While discovering neural networks generalize on small datasets, Olson et al. (2018) introduced an algorithm to decompose a neural network into a set of uncorrelated trees, possibly explaining their ability to perform variance reduction. For many machine learning models, boosting Schapire (2003) and bagging Breiman (1996) are employed to improve generalization performance by either averaging over different trained models, or resampling the dataset so it contains different distributions of data points. The underlying intuition is that different models are unlikely to make the same mistake. One can also train models on different subsets of features and take an average to reduce variance. Additionally, one promising line of investigation surrounding neural network generalization is that of algorithmic stability, as analyzed by Bousquet & Elisseeff (2000) and Hardt et al. (2016) for the case of SGD.
In this work, we consider ReLU networks trained using SGD on image data. We show that training with SGD on ReLU neural networks gives rise to a natural set of functions for each image that are not perfectly correlated until later in training. Furthermore, we show experimentally that the intersection of paths for different images also changes during the course of training. We hypothesize that this lack of correlation and changing intersection may be a factor in explaining generalization, because it encourages the model to use different features at different times, and pass the same image through different functions during training. This may improve generalization in two ways. 1) By
encouraging the model to learn the same image in different ways, and learn different commonalities between images, comparable to model ensembling.
In particular, at time t, an image has access to a subset of features from image functions f tj , and this subset changes over time. Hence, f ti may not be too correlated with the end-to-end function f k j , k  t on the training set, allowing for generalization.
2) By improving algorithmic stability, as for a particular feature, the model is not always reliant on the same set of images, so the removal of an image may not adversely affect the loss.

heading: 2 PRIOR WORK
text: Keskar et al. (2019) investigate the effect of sharpness and flatness of minima on generalization, and find that flat minima generalize better. Dinh et al. (2017) find that if the network is re-parametrized, sharp minima can also generalize well. Smith & Le (2018) give a bayesian perspective on generalization and SGD. Dziugaite & Roy (2017) reveal a way to compute non-vacuous generalization bounds using PAC-Bayes He & Su (2019) study the local elasticity of neural networks, where the prediction at x is not significantly perturbed if a gradient update is performed on another dissimilar point x0. Deng et al. (2021) use local elasticity to compute a generalization bound.Poggio et al. (2020a) show that neural networks can avoid the curse of dimensionality. Poggio et al. (2020b) show that neural networks have complexity control by analyzing the normalized gradient. Veit et al. (2016) find that ResNets behave like ensembles of shallow networks by examining the paths the data travels through.
Algorithmic stability Bousquet & Elisseeff (2000) use McDiarmid’s method to show that algorithmic stability implies good generalization error. Hardt et al. (2016) analyze the algorithmic stability of SGD.
Studies on the gradient Sankararaman et al. (2020) study the impact of gradient confusion on the speed of neural network optimization concluding that SGD is fast when gradient confusion is low. Yin et al. (2018) Jain et al. (2018) study the effect of gradient diversity on the speed of optimization and show that greater gradient diversity leads to large mini-batches more effectively speeding up SGD. Fort et al. (2019) investigate the stiffness of neural networks and measure the cosine similarity between gradients as an approximation of how much one data point reduces loss on another. Chatterjee (2019) connects gradient averaging to algorithmic stability and generalization. Jacot et al. (2018) study generalization in the case that the network width reaches infinity, in which case dynamics are governed by the Neural Tangent Kernel. Arora et al. (2019) find that in practice, finite width CNTKs generalize better than infinite width models, indicating there may be some advantage to finite width. Novak et al. (2018) empirically study sensitivity measures such as the input output jacobian, and find that this correlates with generalization. Arpit et al. (2017) study memorization in neural networks. One quantity they consider is the gradient of the loss with respect to a particular input sample.
Variance reduction A key idea in traditional machine learning is that of variance reduction. Boosting and bagging are employed as techniques to reduce variance by averaging over different (uncorrelated) models.
SGD as noisy GD Mandt et al. (2016) show that SGD can be interpreted as an OrnsteinUhlenbeck process. Another line of work has investigated the anisotropic noise of SGD as compared to GD. Since the SGD update samples a minibatch to calculate the gradient instead of using the whole training set, they view the SGD update as a noisy version of the GD update. Zhu et al. (2019) explore the effectiveness of the anisotropic noise in SGD at escaping bad minima of the loss function.
Assessing Layerwise Convergence Raghu et al. (2017) Morcos et al. (2018) use canonical correlation analysis to reveal insights into the convergence across different neural networks. They consider each neuron to be a vector, with each entry corresponding to the neuron value on a training data point, and each layer to be a subspace spanned by its neurons’ vectors.
Assessing Activation Patterns Hanin & Rolnick (2019) investigated activation patterns in ReLU networks and found that they use surprisingly few such patterns. Cogswell et al. (2016) improved generalization of neural networks by introducing a regularizer that de-correlated activations.
Dropout Neural networks may be explicitly regularized using techniques such as dropout. Dropout imposes regularization by dropping nodes in a way that is typically sampled from a Bernoulli distribution. The resulting model can be considered an ensemble. Gao et al. (2019) investigate the effects of separating the forward from the backward pass.

heading: 3 ON FUNCTIONS
text: Mathematically, a function is a binary relation between two sets that associates each element of the first set with exactly one of the other set. ReLU functions clearly satisfy this definition, and all images pass through the same ReLU function. Yet, we will argue that each image is more accurately considered to have its own function, because the overall ReLU function is not particularly smooth, and does not, for example, satisfy the nice properties of polynomials use in function analysis. Although each image function is calculated on the same weights, we find that the varying ReLU paths make them sufficiently different.

heading: 4 GENERALIZATION
text: At the start of training, both the training data and test data are assumed to be drawn from some distribution D. However, during training, input data are sampled uniformly from T , the training set, call this distribution U . The key question behind generalization is why optimizing over EU results in low loss over ED. In this work, we show that neural networks learn different functions for the same image during training, and that this function diversity may contribute to generalization.

heading: 5 FULLY CONNECTED NETWORK GRADIENTS
text: We use [N ] := {1, 2, ..., N}. SGD computes the following update on neural network parameters wt+1 = wt ⌘rwtL (1)
where rwtL denotes the gradient of the loss with respect to the weight parameters, and ⌘ the learning rate. We focus on the case of minibatch SGD, where the gradient update is computed over a batch of data. For a particular node n evaluated on an image xi, it will have incoming backpropagated gradient at time t of z(t,n)i . Let N be the number of nodes in the network and L the number of layers. We assume each node has an index, n, in [N ], and furthermore for the sake of notation that all nodes in the first layer are indexed {1, ...`1}, that the second layer is indexed {`1, ..., `2} etc. with `L = N . We will also write {` 1, ..., `0} to denote the coordinates of the input. Let !ai (t,`j :`k) be the vector of activations for image xi at time t from nodes in layers j to k. We define a function pti : [N ] ! {0, 1} that takes the index of the neural network’s N nodes, and returns 1 if it is on for image i at time t according to the ReLU activation function and returns 0 otherwise. With some abuse of notation, if we omit the function argument and write pti, we define this as the vector of length N containing pti(n) as each entry. Let Bt be the minibatch sampled at time t. So the gradient update for a particular node n in layer `k, k 2 [L] at time t is
X
i2Bt
z(t,n)i · p t i(n) · !ai (t,`k 2:`k 1) (2)
for the weight parameter and P
i2Bt z (t,n) i for the bias parameter.
Let f (t,n)i (x) = ⇣ z(t,n)i · p t i(n) · !ai (t,`k 2:`k 1) ⌘ · x+ z(t,n)i (3)
Then the overall function a fully connected node n computes at time t for input x is
f (t,n)(x) =
X
t
X
i2Bt
f (t,n)i (x) ! · ptx(n) (4)
where ptx(n) denotes the path function for image x (not necessarily in the training set), and the layer activations are given by
f (t,1:`1)(x) := [f (t,1)(x), f (t,2)(x), ..., f (t,`1)(x)] (5) where the square braces denote concatenation and the layer function for `j may be defined recursively.
F (t,`j)(x) = f (t,`j 1:`j) ⇣ · · ·f (t,1:`1)(x) ⌘ (6)
We will define the history of the neural network as
HT = { X
i2B1
f (1,[N ])i , ..., X
i2BT
f (T,[N ])i } (7)
The activations !ai (t,n) for an input image xi are found by projecting the image onto the history of the network, e.g.
!ai (t,1:`1) = f (t,1:`1)(xi) (8)
We will use the notation
pti|Ht (9) to project the path pti onto the history, i.e. to run the forward pass for F (t,`L) fixing ptx(n) in Equation 4 to be equal to pti for all n. Once enough updates have occurred, Equation 4 contains a term f (t,n) i for all i in the training set. It is therefore not obvious why continuing to update using only the i in the training set does not yield a function that is very correlated on the training set and only produces low values of the loss on those points (and not on the test set). The gradient of neural networks is sometimes treated as a black-box in terms of generalization. However, we can exploit the fact that many neural networks use some form of dot product for each neuron to write the ai terms in Equation 4. Experimentally, we will measure the normalized dot products of these activations, as well as path overlap.
Evaluating the same point using different functions Let t be the current time, xi 2 Bt and xj /2 Bt. At time t, data point xi is evaluated using Equation 6 which contains f (t,n) j as in Equation 4. One main observation is that f (t,n)j and f (t k,n) j for 1  k  t 1 may have different p t x(n) terms in Equation 4 (i.e. ptx(n) · pt kx (n) may not have high normalized dot product). That is to say, the same image at different times in training may follow a different evaluation path, i.e. the set of nodes activated for that image may be different.)
This also means that although each f (t,n)i may be correlated with the history Ht of the network, and hence be correlated with the other previous f (t k,n)j for 1  k  t 1, the ReLU activation causes pj to be new enough that the network may not already correlated with f (t,n) j at the current time t (until xj next updates.) This encourages generalization, as the network, despite having seen xj before, does not pass it through a function too correlated with xj . This means that although the network has seen image xj before, it learns it using a different function, encouraging generalization. In summary, we show experimentally that Neural networks learn differing functions for the same image during training
Earlier functions are destroyed by subsequent ones In an ensemble, typically an average of functions is taken to be the final predictor of the form wigi. In the setup described above, although image xi may follow pti at time t, it may subsequently not be assigned that same path again. Hence, it cannot use all of f ti in future rounds. We believe this also means that having extremely low correlation or independence is not as important as it is in ensembles. Rather, there is a tradeoff; more similarity may mean easier optimization, while somewhat less similarity may lead to more algorithmic stability, due to not re-using the same set of features.
Which functions are optimized We use pti|Ht to be the function found projecting the path pti onto the history Ht. Each data point xi at time t will have loss L(pti|Ht) where L is some loss
function (e.g. the cross entropy loss). Suppose xi is in the updating batch at time t, i.e. i 2 Bt, then rL(pti|Ht) is directly calculated, and a gradient step is taken to descend on this loss function. Furthermore, since the function pti|Ht depends on all previous images xj after the first epoch in training, it is not obvious why while descending on L(pti|Ht), the functions L(ptj |Ht) are not also optimized for images xj in the training set only. We hypothesize that even if the network tries to optimize L(pti|Ht) in terms of prior pkj |Hk for k < t, this does not correspond to optimizing xj in terms of its current function ptj |Ht.
From the last time xj updated, the network cannot re-run the forward pass on xj , and ptj will be reassigned according to the ReLU function and the current history Ht. So the i 2 Bt do not have access to the end to end back-propagated gradient along the updated ptj and instead calculate gradients along their own paths pti for i 2 Bt. Each of these pti have some intersection with the previous pkj for k < t, typically pti · pkj > 0. These paths pti serve to collectively update along ptj , but not by simple averaging or by linear combination of the whole paths. The sum of fi in Equation 4 do not correspond to a single back-propagated function, and are instead separate functions (Equation 3) stitched together according to the ReLU gate. When re-assigning xj to its new path, the z(t,n)i in Equation 3 may not correspond to the evaluation path ahead in the network that xj will actually follow (because ptj is unknown). The function xj follows at evaluation time is hence a sort of ’franken-function’ which is constructed on the fly and is not explicitly optimized. It also does not correspond to simply adding together the fi, as the px term in Equation 4 must be applied. Additionally, the previous path that xj was following is likely to be destroyed; we find experimentally that the image does not follow pkj at a later time t. Also, either all gradient updates to a node are applied (if it is on) or none are (if it is off), so data points may not selectively pick some functions to follow end-to-end.
Additionally, we find that training images xi and xj intersect in different places (along different paths) at different times in training, and that xi has highest dot product with different images throughout training. We interpret this to mean that The ReLU gate encourages the use of different features at different times.
We show experimentally that:
• For a particular previous fki k < t, each current updating f tj have only partial path intersection with fki . (They do not have complete access to all previous activations). Furthermore, they intersect on different nodes at different times. (Indicating they may learn from each other in different ways at different times)
• The f ti at different times t for some fixed image index i are different. (Self similarity is not perfect.)
• The overall layer function, Equation 6 is not too smooth, supporting the case for considering f ti for various i as different functions.
• For a particular image i, the ranking of which functions f tj are most path similar, for various times t, changes, indicating that which images are most similar to each other changes. This is in contrast, e.g., with K nearest neighbors, where the identity of the nearest neighbor remains fixed for fixed training data.
CNN layers the update for CNN networks may be computed comparably, with Equation 3 modified to contain a sum over patches cj of the original image
f (t,n)i (x) =
0 @ X
j
z(t,n)i · p t i(n) · !cj (t,`k 2:`k 1)
1 A · x+ X
j
z(t,n)j (10)

heading: 6 EXPERIMENTS BETWEEN DATA POINTS
text: Equation 4 involves three terms; a zi term, an ai term (the activations of the layer before), and a path term pi. In our experiments, we first focus on the pi term, as it reveals which nodes are on or off for a particular function. We use the usual definition of pi and allow the ReLU function on the current history Ht to determine if a node is on or off. Since the ai term in Equation 4 is dotted with x, which would be the activations of input x at the layer before, we also graph dot products between activations at the same layer. We concatenate all activations into a single vector for a layer. We also conduct experiments on the whole function f ti applied in isolation in Appendix Section C. Experimental details for training the model can be found in Appendix Section B.

heading: 6.1 ALEXNET CROSS PATH ALIGNMENT
text: We let denote the elementwise product. We omit the argument for pti and assume that it is (`k 1 : `k) We measure the quantity (pti p t j)·(p t 1 i p t 1 j )
|(pti ptj)||(p t 1 i p t 1 j )|
, which determines the overlap between
the intersection of paths pti and ptj at the current epoch t versus the previous epoch t 1. This answers the question, does image xi always have access to the same set of activations from xj? We see in Figure 1 that the answer is no. We hypothesize that this is the ReLU gate and SGD optimization encourages xi to use a different set of previous features from other images xj , and this this diversity could encourage generalization.
Figure 1: Cross path similarity
(pti p t j)·(p t 1 i p t 1 j )
|(pti ptj)||(p t 1 i p t 1 j )|
for AlexNet trained on CIFAR-10 data in the
left column and the quantity (ati a t j)·(a t 1 i a t 1 j )
|(ati atj)||(a t 1 i a t 1 j )| in the right column. The top row depicts the 4th layer of the network and the bottom row the 1rst layer of the network. We find that for a majority of training, there is not a perfect correlation for either quantity, indicating images intersect each other on different features at different points in training.

heading: 6.2 RESNET 18 ON CIFAR 10 CROSS PATH ALIGNMENT
text: For ResNet-18 trained on the CIFAR 10 dataset, we plot the normalized path overlap as we did for AlexNet. We plot our results in Figure 2. We find that in general, the correlations are higher than those found in AlexNet, but still not perfectly correlated until late in training. ResNet is also significantly deeper than AlexNet, and a small difference in each layer cumulatively leads to a different overall path. VGG-19 on CIFAR 10 cross path similarity We have similar findings for VGG-19 in Appendix Figure 16
Figure 2: Cross path similarity
(pti p t j)·(p t 1 i p t 1 j )
|(pti ptj)||(p t 1 i p t 1 j )| for ResNet-18 trained on CIFAR-10 data. Bot-
tom row depicts layer 2, top row depicts layer 6.
Figure 3: Cross path similarity
(pti p t j)·(p t 1 i p t 1 j )
|(pti ptj)||(p t 1 i p t 1 j )|
for ResNet-18 trained on ImageNet data.

heading: 6.3 RESNET 18 ON IMAGENET CROSS PATH ALIGNMENT
text: For ResNet trained on the ImageNet dataset, we plot the normalized distribution of (pti p t j)·(p t 1 i p t 1 j ) |(pti ptj)||(p t 1 i p t 1 j )|
We plot our results in Figure 3. We find that this distribution is not perfectly correlated, though it becomes more correlated later in training.

heading: 6.4 ALEXNET CIFAR 10 PATH DISTANCES
text: We run experiments to asses how different the f ti are for different i. We try to asses whether the overlap between path vectors is related to the distance between original points in data space. We plot our results in Figure 4. We find that there is not a clean linear relationship between distance in original space and overlap in path vectors, supporting the case for considering each image update as its own function, and again indicating that there is a kind of function diversity present in ReLU network training.
Resnet-18 on CIFAR-10: We have similar findings for Resnet -18 trained on CIFAR-10 in Appendix D

heading: 7 EXPERIMENTS ON SELF SIMILARITY
text: In this section, we seek to asses how different the paths and representations are for a single image throughout the course of training.

heading: 7.1 ALEXNET ON CIFAR 10
text: For AlexNet trained on the CIFAR 10 dataset, we plot the normalized distribution of pti([`k 1 : `k]) · p t 1 i ([`k 1 : `k]). We plot our results in Figure 5. We find that especially in the beginning of training, pti and p t 1 i are not perfectly correlated, indicating that the same image xi is passing through different nodes at different times t.

heading: 8 THE IDENTITY OF THE MOST SIMILAR IMAGE CHANGES
text: For three images we rank 128 other data points and restrict the resulting plot to the nearest 6 neighbors, where rank of 0 means it is the nearest neighbor. We use AlexNet on CIFAR 10 layer 2. We plot our results in Figure 6. Result using activation similarity We present analogous results to above using normalized activation similarity for layer 4 and 2 of AlexNet in Appendix E
TAKEWAY FROM EXPERIMENTS
We find that in all the architectures we examined, the self similarity and the intersection similarity between data points changed throughout (especially the early part) of training. These variations may lead to generalization for the similar reasons to ensembling over different models. Unlike in ensembling, we see that f ti is destroyed at a later time f t+k i , because xi may not pass through the whole pti and instead may only use part of it (the part that intersects with p t+k i ). Furthermore, each
other image function f tj is only correlated with parts of f ti (on certain nodes.) This may explain why averaging is not necessary for variance reduction.
Ratio of early to mid cross path overlap Finally, we can utilize the idea of cross path overlap in an attempt to predict generalization error. We hypothesize that higher (but not perfect) cross path overlap early is good, as typically the learning rate is high and this reflects a large number of shared features in the data On the other hand, high cross path overlap after decay may be bad, as diverse features are no longer being learnt. We plot (averaged over training data) the ratio of early (average over epochs before first decay) to mid (averaged over second stage of training) cross path overlap for various models against their generalization error in Figure 7. There is a roughly linear relationship, and improving such predictions could be an interesting avenue for future work.
CONCLUSION
We have studied neural networks from the perspective of considering each image, updating at a particular time, as a different function. We have highlighted some properties of practical neural networks, namely that they learn varying representations for a single image, and that each image intersects each other image in different places during training. We hypothesize that this diversity of representation could lead to better generalization, by encouraging the model to learn the same image in different ways (akin to model ensembling) and by improving algorithmic stability.

Review summaries:
This paper proposes a different look at why neural networks generalize despite optimizing to zero training error, over-parameterization, etc.  The contribution is mostly experimental in the sense of computing various statistics of a model during training and correlating those statistics with generalization performance.  The core idea is to define "image functions" which are determined by the training image and the current training iteration.  Correlation statistics on these functions for different and same training images show patterns in the training dynamics, which may indicate generalization for example as training continues towards zero error the statistics still vary.  The paper focuses on classification with CIFAR10 and ImageNet with AlexNet, VGG, and ResNet models.  In particular the results are specialized for ReLU networks training with SGD.

The authors present empirical results about the correlation between the activations in a neural network across time for a fixed pair of images.  They show that for the same pair of images xi and xj, the activations change over time until they settle when the learning rate is sufficiently small. The authors claim that this provides insight into why neural networks generalize, by arguing that the network uses different features at different epochs during training.