The Local Elasticity of Neural Networks

Introduction

Neural networks have been widely used in various machine learning applications, achieving comparable or better performance than existing methods without requiring highly engineered features (Krizhevsky et al. 2012). However, neural networks have several intriguing aspects that defy conventional views of statistical learning theory and optimization, thereby hindering the architecture design and interpretation of these models. For example, despite having more parameters than training examples, deep neural networks generalize well without an explicit form of regularization (Zhang et al. 2017; Neyshabur et al. 2017; Arora et al. 2019a). Zhang et al. 2017 also observe that neural networks can perfectly fit corrupted labels while maintaining a certain amount of generalization power This property also holds for the $1$-nearest neighbors algorithm..

In this paper, we complement this line of findings by proposing a hypothesis that fundamentally distinguishes neural networks from linear classifiers Without using the kernel trick, these classifiers include linear regression, logistic regression, support vector machine, and linear neural networks.. This hypothesis is concerned with the dynamics of training neural networks using stochastic gradient descent (SGD). Indeed, the motivation is to address the following question:

How does the update of weights using SGD at an input $\bm{x}$ and its label $y$ impact the prediction of the neural networks at another input $\bm{x}^{\prime}$ ?

Taking this dynamic perspective, we make the following three contributions.

First, we hypothesize that neural networks are locally elastic in the following sense: an extensive set of experiments on synthetic examples demonstrate that the impact on the prediction of $\bm{x}^{\prime}$ is significant if $\bm{x}^{\prime}$ is in a local vicinity of $\bm{x}$ and the impact diminishes as $\bm{x}^{\prime}$ becomes far from $\bm{x}$ in an elastic manner. In contrast, local elasticity is not observed in linear classifiers due to the leverage effect (Weisberg 2005). Thus, at a high level, local elasticity must be inherently related to the nonlinearity of neural networks and SGD used in updating the weights. This phenomenon is illustrated by Figure 1. Additional synthetic examples and ImageNet (Deng et al. 2009) with a pre-trained ResNet (He et al. 2016) in Appendix A.2 further confirm local elasticity. For completeness, we remark that the notion of local elasticity seems related to influence functions on the surface (Koh & Liang 2017). The fundamental distinction, however, is that the former takes into account the dynamics of the training process whereas the latter does not. See Section 2 for a formal introduction of the notion of local elasticity.

Furthermore, we devise a clustering algorithm by leveraging local elasticity of neural networks. In short, this algorithm records the relative change of the prediction on a feature vector to construct a similarity matrix of the training examples. Next, the similarity matrix is used by, for example, $K$-means to partition the points into different clusters. The experiments on MNIST (LeCun 1998) and CIFAR-10 (Krizhevsky 2009) demonstrate the effectiveness of this local elasticity-based clustering algorithm. For two superclasses (e.g., mammal and vehicle), the algorithm is capable of partitioning the mammal class into cat and dog, and the second superclass into car and truck. These empirical results, in turn, corroborate our hypothesis that neural networks (with nonlinear activation) are locally elastic. The code is publicly available at https://github.com/hornhehhf/localelasticity. See the description of the algorithm in Section 3 and experimental results in Section 4.

Finally, this paper provides profound implications of local elasticity on memorization and generalization of neural networks, among others. In this spirit, this work seeks to shed light on some intriguing aspects of neural networks. Intuitively, the locality part of this property suggests that the neural networks can efficiently fit the label of an input without significantly affecting most examples that have been well fitted. This property is akin to the nearest neighbors algorithm (see, e.g., Papernot & McDaniel 2018). Meanwhile, the elasticity part implies that the prediction surface is likely to remain smooth in the training process, in effect regularizing the complexity of the nets in a certain sense. These implications are discussed in detail in Section 5.

There has been a line of work probing the geometric properties of the decision boundary of neural networks. Montufar et al. 2014 investigate the connection between the number of linear regions and the depth of a ReLU network and argue that a certain intrinsic rigidity of the linear regions may improve the generalization. Fawzi et al. 2017; Fawzi et al. 2018 observe that the learned decision boundary is flat along most directions for natural images. See Hanin & Rolnick 2019 for the latest development along this line and Fort et al. 2019 for a dynamic perspective on the landscape geometry.

In another related direction, much effort has been expended on the expressivity of neural networks, starting from universal approximation theorems for two-layer networks (Cybenko 1989; Hornik et al. 1989; Barron 1993). Lately, deep neural networks have been shown to possess better representational power than their shallow counterparts (Delalleau & Bengio 2011; Telgarsky 2016; Eldan & Shamir 2016; Mhaskar & Poggio 2016; Yarotsky 2017; Chen et al. 2019). From a nonparametric viewpoint, approximation risks are obtained for neural networks under certain smooth assumptions on the regression functions (Schmidt-Hieber 2017; Suzuki 2018; Klusowski & Barron 2018; Liang 2018; Bauer & Kohler 2019; E et al. 2019a).

A less related but more copious line of work focuses on optimization for training neural networks. A popular approach to tackling this problem is to study the optimization landscape of neural networks (Choromanska et al. 2015; Soudry & Hoffer 2017; Zhou & Liang 2017; Safran & Shamir 2018; Du & Lee 2018; Liang et al. 2018; Soltanolkotabi et al. 2018). Another approach is to analyze the dynamics of specific optimization algorithms applied to neural networks (Tian 2017; Li & Yuan 2017; Soltanolkotabi 2017; Brutzkus & Globerson 2017; Du et al. 2018; Li & Liang 2018; Allen-Zhu et al. 2018; Zou et al. 2018; Du et al. 2019; Allen-Zhu et al. 2019). Alternatively, researchers have considered the evolution of gradient descent on two-layer neural networks using optimal transport theory (Song et al. 2018; Chizat & Bach 2018; Sirignano & Spiliopoulos 2019; Rotskoff & Vanden-Eijnden 2018). More recently, there is a growing recognition of intimate similarities between over-parameterized neural networks and kernel methods from an optimization perspective (Zhang et al. 2017; Daniely 2017; Belkin et al. 2018; Jacot et al. 2018; Yang 2019; Arora et al. 2019b; Lee et al. 2019; E et al. 2019b). For completeness, some work demonstrates a certain superiority of neural networks in generalization over the corresponding kernel methods (Wei et al. 2018; Allen-Zhu & Li 2019; Ghorbani et al. 2019).

Local Elasticity

In this context, we say that the classifier $f$ is locally elastic at parameters $\bm{w}$ if $|f(\bm{x}^{\prime},\bm{w}^{+})-f(\bm{x}^{\prime},\bm{w})|$, the change in the prediction at a test feature vector $\bm{x}^{\prime}$, is relatively large when $\bm{x}$ and $\bm{x}^{\prime}$ are similar/close, and vice versa. Here, by similar/close, we mean two input points $\bm{x}$ and $\bm{x}^{\prime}$ share many characteristics or are connected by a short geodesic path in the feature space. Intuitively, $\bm{x}$ and $\bm{x}^{\prime}$ are similar if $\bm{x}$ denotes an Egyptian cat and $\bm{x}^{\prime}$ denotes a Persian cat; they are dissimilar if $\bm{x}$ denotes a German shepherd and $\bm{x}^{\prime}$ denotes a trailer truck.

For illustration, Figure 2(a) shows that the (linear) classifier is not locally elastic since the SGD update on $\bm{x}$ leads to significant impact on the prediction at $\bm{x}^{\prime}$, though $\bm{x}^{\prime}$ is far from $\bm{x}$; on the other hand, the (nonlinear) classifier in Figure 2(b) is locally elastic since the change at $\bm{x}^{\prime}$ is relatively small compared with that at $\bm{x}$. In Section 2.3, we provide some intuition why nonlinearity matters for local elasticity in two-layer neural nets.

The essence of local elasticity is that the change in the prediction has an (approximate) monotonic relationship with the similarity of feature vectors. Therefore, the change can serve as a proxy for the similarity of two inputs $\bm{x}$ and $\bm{x}^{\prime}$:

2 Kernelized Similarity

Next, we introduce a different similarity measure that manifests local elasticity by making a connection to the neural tangent kernel (Jacot et al. 2018). Taking a small learning rate $\eta$, for a new feature point $\bm{x}^{\prime}$, the change in its prediction due to the SGD update in Equation (1) approximately satisfies:

The factor $-\eta\frac{\partial\mathcal{L}}{\partial f}$ does not involve $\bm{x}^{\prime}$, just as the denominator $|f(\bm{x},\bm{w}^{+})-f(\bm{x},\bm{w})|$ in Equation (2). This observation motivates an alternative definition of the similarity:

The kernelized similarity in Equation (3) is approximately the inner product of the gradients of $f$ at $\bm{x}$ and $\bm{x}^{\prime}$ As opposed to the relative similarity, this definition does not take absolute value in order to retain its interpretation as an inner product. . This is precisely the definition of the neural tangent kernel (Jacot et al. 2018) (see also Arora et al. 2019b) if $\bm{w}$ is generated from i.i.d. normal distribution and the number of neurons in each layer tends to infinity. However, our empirical results suggest that a data-adaptive $\bm{w}$ may lead to more significant local elasticity. Explicitly, both similarity measures with pre-trained weights yield better performance of Algorithm 1 (in Section 3) than those with randomly initialized weights. This is akin to the recent findings on a certain superioritiy of data-adaptive kernels over their non-adaptive counterparts (Dou & Liang 2019).

3 Interpretation via Two-layer Networks

Assuming $\bm{w}$ are i.i.d. normal random variables and some other conditions, in the appendix we show that this neural networks with the SGD rule satisfies

The Local Elasticity Algorithm for Clustering

This section introduces a novel algorithm for clustering that leverages the local elasticity of neural networks. We focus on the setting where all (primary) examples are from the same (known) superclass (e.g., mammal) and the interest is, however, to partition the primary examples into finer-grained (unknown) classes (e.g., cat and dog). To facilitate this process, we include an auxiliary dataset with all examples from a different superclass (e.g., vehicle). See Figure 3 for an illustration of the setting. To clear off any confusion, we remark that the aim is to corroborate the hypothesis of local elasticity by showing the effectiveness of this clustering algorithm.

The centerpiece of our algorithm is the dynamic construction of a matrix that records pairwise similarities between all primary examples. In brief, the algorithm operates as if it were learning to distinguish between the primary examples (e.g., mammals) and the auxiliary examples (e.g., vehicles) via SGD. On top of that, the algorithm evaluates the changes in the predictions for any pairs of primary examples during the training process, and the recorded changes are used to construct the pairwise similarity matrix based on either the relative similarity in Equation (2) or the kernelized similarity in Equation (3). Taking the mammal case as earlier, the rationale of the algorithm is that local elasticity is likely to yield a larger similarity score between two cats (or two dogs), and a smaller similarity score between a cat and a dog.

Experiments

We evaluate the performance of Algorithm 1 on MNIST (LeCun 1998) and CIFAR-10 (Krizhevsky 2009). For the MNIST dataset, we choose the $6$ pairs of digits that are the most difficult for the binary $K$-means clustering. Likewise, $6$ pairs of classes are selected from CIFAR-10. For each pair (e.g., 5 and 8), we construct the primary data set by randomly sampling a total of 1000 examples equally from the two classes in the pair. The auxiliary dataset consists of 1000 examples that are randomly drawn from one or two different classes (in the case of two classes, evenly distribute the 1000 examples across the two classes).

2 Results

Comparison between architectures. The results of Algorithm 1 with the aforementioned three types of neural networks, namely FNN, CNN, and ResNet on MNIST are presented in Table 3. The results show that CNN in conjunction with the kernelized similarity has high classification accuracy. In contrast, the simple three-layer ResNet seems to not capture local elasticity.

To further evaluate the effectiveness of the local elasticity based Algorithm 1, we compare this clustering algorithm using CNN with two types of feature extraction approaches: autoencoder We use the autoencoder in https://github.com/L1aoXingyu/pytorch-beginner/blob/master/08-AutoEncoder/conv_autoencoder.py. and pre-trained ResNet-152 (He et al. 2016). An autoencoder reconstructs the input data in order to learn its hidden representation. ResNet-152 is pre-trained on ImageNet (Deng et al. 2009) and can be used to extract features of images. The performance of those models on MNIST Here, the comparison between our methods and ResNet-152 on CIFAR-10 is not fair since ResNet-152 is trained using samples from the same classes as CIFAR-10. are shown in Table 4. Overall, autoencoder yields worst results. Although ResNet-152 performs quite well in general, yet our methods outperform it in some cases. It is an interesting direction to combine the strength of our algorithm and ResNet-152 in classification tasks that are very different from ImageNet. Moreover, unlike ResNet-152, our methods do not require a large number of examples for pre-training As a remark, here we do not compare with other clustering methods that are based on neural networks, such as DEC (Xie et al. 2016). We can replace $K$-means by other clustering algorithms to possibly improve the performance in some situations..

To better appreciate local elasticity and Algorithm 1, we study the effect of parameter initialization, auxiliary examples and normalized kernelized similarity in Appendix A.4. More discussions on the expected relative change, activation patterns, and activation functions can also be found in Appendix A.4.

Implications and Future Work

In this paper, we have introduced a notion of local elasticity for neural networks. This notion enables us to develop a new clustering algorithm, and its effectiveness on the MNIST and CIFAR-10 datasets provide evidence in support of the local elasticity phenomenon in neural networks. While having shown the local elasticity in both synthetic and real-world datasets, we acknowledge that a mathematical foundation of this notion is yet to be developed. Specifically, how to rigorous formulate this notion for neural networks? A good solution to this question would involve the definition of a meaningful similarity measure and, presumably, would need to reconcile the notion with possible situations where the dependence between the prediction change and the similarity is not necessarily monotonic. Next, can we prove that this phenomenon occurs under some geometric structures of the dataset? Notably, recent evidence suggests that the structure of the training data has a profound impact on the performance of neural networks (Goldt et al. 2019). Moreover, how does local elasticity depend on network architectures, activation functions, and optimization strategies?

Broadly speaking, local elasticity implies that neural networks can be plausibly thought of as a local method. We say a method is local if it seeks to fit a data point only using observations within a window of the data point. Important examples include the $k$-nearest neighbors algorithm, kernel smoothing, local polynomial regression (Fan 2018), and locally linear embedding (Roweis & Saul 2000). An exciting research direction is to formally relate neural networks to local methods. As opposed to the aforementioned classic local methods, however, neural networks seem to be capable of choosing the right bandwidth (window size) by adapting the data structure. It would be of great interest to show whether or not this adaptivity is a consequence of the elasticity of neural networks.

In closing, we provide further implications of this notion by seeking to interpret various aspects of neural networks via local elasticity. Our discussion lacks rigor and hence much future investigation is needed.

Memorization. Neural networks are empirically observed to be capable of fitting even random labels perfectly (Zhang et al. 2017), with provable guarantees under certain conditions (Allen-Zhu et al. 2019; Du et al. 2019; Oymak & Soltanolkotabi 2019). Intuitively, local elasticity leads neural nets to progressively fit the examples in a vicinity of the input via each SGD update, while remaining fitting (most) labels that have been learned previously. A promising direction for future work is to relate local elasticity to memorization in a more concrete fashion.

Stability and generalization. Bousquet & Elisseeff 2002 demonstrate that the uniform stability of an algorithm implies generalization on a test dataset. As noted by Kuzborskij & Lampert 2018, due to its distribution-free and worst-case nature, uniform stability can lead to very loose bounds on generalization. The local elasticity of neural networks, however, suggests that the replace of one training point by another imposes limited perturbations on the predictions of most points and thus the loss might be more stable than expected. In this regard, it is possible to introduce a new notion of stability that relies on the metric of the input space for better generalization bounds.

We would like to thank Yu Bai, Zhun Deng, Simon Du, Jiaoyang Huang, Song Mei, Andrea Montanari, Yuandong Tian, and Qinqing Zheng for stimulating discussions. This work was supported in part by NSF via CAREER DMS-1847415 and CCF-1763314, and the Wharton Dean’s Research Fund.

References

Appendix A Experimental Details and Additional Results

The blue examples in the torus function (Figure 1(a)) can be defined parametrically by:

Similarly, the red examples in the torus function are defined by:

The blue examples in the two folded boxes function (Figure 1(d)) are sampled from:

Similarly, the red examples in the two folded boxes function are defined as:

Geodesic distance is used to measure the shortest path between two points in a surface, or more generally in a Riemannian manifold. For example, in Figure 1, the geodesic distance for the torus function and the two folded boxes function is the distance in the curve and the distance in the surface rather than the Euclidean distance.

A.2 More Simulations

More simulations can be found in Figure 4.

We further explore the local elasticity of ResNet-152 on ImageNet. We find that, when the pre-trained ResNet-152 are updated on a tabby cat via SGD, the predictions of tiger cats change more drastically than the predictions of warplanes. We randomly pick $50$ examples from the tabby cat synset as updating points, $25$ examples from the tiger cat synset and $25$ examples from the warplane synset as testing points. After updating on a tabby cat, we can get the average change of predictions on the $25$ tiger cats and that on the $25$ warplanes. By conducting a Wilcoxon rank-sum test with SGD updates on $50$ different tabby cats, we find that the average change of the predictions on the tiger cat are significantly more drastic than that on the warplane with a p-value of $0.0007$. The overall average relative similarity between the tiger cats and the tabby cats is $4.4$, while the overall average similarity between the warplanes and the tabby cats is $6.6$. Note that the relative similarity is computed from the relative KL divergence between the original prediction and the updated prediction.

Specifically, we find that the change of the predictions (KL divergence of $0.03$) on the tiger cat (Figure 5(b)) is more drastic than that (KL divergence of $0.002$) on the warplane (Figure 5(c)) after a SGD update on the tabby cat (Figure 5(a)), although the Euclidean distance ($511$) between the warplane and the tabby cat is smaller than that ($854$) between the tiger cat and the tabby cat.

Moreover, we conduct a simulation study to examine local elasticity in the case of using mini-batch SGD for updates. Specifically, we consider updating the weights of ResNet-152 in one iteration using two images. The training and test images are displayed in Figure 6. We find that the changes of the predictions on the tabby cat (Figure 6(c), KL divergence of $0.021$) and on the warplane (Figure 6(d), KL divergence of $0.024$) are more substantial than that on the tree frog (Figure 6(e), KL divergence of $0.0004$) after an SGD update on the minibatch composed of a tabby cat (Figure 6(a)) and a warplane (Figure 6(b)).

A.3 Some Calculations

We brief explain how to obtain Equation (4) under the same assumptions of Li & Liang 2018.

A.4 More Aspects on the Experiments

We use $40960$ neurons with ReLU activation function for two-layer neural nets in simulations and experiments. We use $8192$ neurons for each hidden layer with ReLU activation function in three-layer neural networks in simulations. The ResNet we use in experiments is a three-layer net that contains $4096$ neurons and a ReLU activation function in each layer. The CNN for MNIST we use in experiments is the same architecture as that in https://github.com/pytorch/examples/blob/master/mnist/main.py.

Weights.

As discussed in Section 3, parameter initialization is important for local elasticity based clustering methods. We find that the optimal setting always outperforms the random setting. It supports the intuition that we can learn detailed features of primary examples to better distinguish them from auxiliary examples. The results of two different types of parameter initialization are shown in Table 5.

Auxiliary examples.

In general, we can choose those samples that are similar to primary examples as auxiliary examples, so they can help neural nets better learn primary examples. We analyze the primary examples pair $5$ and $8$ in MNIST with $6$ different settings of auxiliary examples. We find that the choice of auxiliary examples are crucial. For example, in our case $9$ is close to $5$ and $3$ is close to $8$ based on $K$-means clustering results, so that we can choose $9$ and $3$ as auxiliary examples for models to better distinguish $5$ and $8$. The results of different auxiliary examples for $5$ vs $8$ on MNIST are shown in Table 6.

Normalized kernelized similarity.

Expected relative change.

We compute the average relative change of two-layer neural nets and linear neural networks fitting the torus function. The average relative change of two-layer neural nets and linear neural networks are $0.44$ and $0.68$, indicating that SGD updates of two-layer neural nets are more local than that of two-layer linear neural networks. These findings further support our local elasticity theory of neural nets.

Activation patterns.

The key difference between our methods and linear baselines is nonlinear activation. We analyze the relations between the patterns of ReLU activation function of two-layer neural nets and corresponding Euclidean distances. For each input $\bm{x}$, we use $\bm{a}$ to denote the binary activation pattern of each neuron. The similarity between binary activation patterns is computed from the cosine similarity function. We find that the activation similarity is linearly dependent on the Euclidean distance, meaning that closer points in the Euclidean space will have more similar activation patterns. The activation analysis of neural nets local elasticity are shown in Figure 7(a).

Activation functions.

We experiment on another standard activation function, sigmoid, to see its local elasticity. We find that sigmoid can also provide neural nets with the local elasticity. The local elasticity of two-layer neural nets with sigmoid activation function on the torus function is shown in Figure 7(b).

Data normalization.

The performance of the methods without data normalization are shown in Table 8. The results show that normalization is important for our methods, which are consistent with our analysis in Section 5.