The Local Elasticity of Neural Networks
Authors: Hangfeng He
Weijie Su
Venue:  (2020)

Abstract: This paper presents a phenomenon in neural networks that we refer to as local elasticity. Roughly speaking, a classifier is said to be locally elastic if its prediction at a feature vector x' is not significantly perturbed, after the classifier is updated via stochastic gradient descent at a (labeled) feature vector x that is dissimilar to x' in a certain sense. This phenomenon is shown to persist for neural networks with nonlinear activation functions through extensive simulations on real-life and synthetic datasets, whereas this is not observed in linear classifiers. In addition, we offer a geometric interpretation of local elasticity using the neural tangent kernel (Jacot et al., 2018). Building on top of local elasticity, we obtain pairwise similarity measures between feature vectors, which can be used for clustering in conjunction with K-means. The effectiveness of the clustering algorithm on the MNIST and CIFAR-10 datasets in turn corroborates the hypothesis of local elasticity of neural networks on real-life data. Finally, we discuss some implications of local elasticity to shed light on several intriguing aspects of deep neural networks.

Published conference paper at ICLR 2020
THE LOCAL ELASTICITY OF NEURAL NETWORKS
Hangfeng He & Weijie J. Su
University of Pennsylvania
Philadelphia, PA
Mangfengesean upenn.
suwewhartoon.upem..edd
ABSTRACT
This paper presents a phenomenon in neural networks that we refer to as local elasticity. Roughly speaking, a classifier is said to be locally clastic if its pre- diction at a feature vector is not significantly perturbed, after the classifier is updated via stochastic gradient descent at a (labeled) feature vector that is dissimilar to x' in a certain sense. This phenomenon is shown to persist for neu- ral networks with nonlinear activation functions through extensive simulations on real-life and synthetic datasets, whereas this is not observed in linear classifiers. In addition, we offer a geometric interpretation of local elasticity using the neural tangent kernel (Jacot et al.) 2018). Building on top of local elasticity, we obtain pairwise similarity measures between feature vectors, which can be used for clus- tering in conjunction with K -mmans. The effectiveness of the clustering algorithm on the MNIST and CIFAR-10 10 datasets in turn corroborates the hypothesis local elasticity of neural networks real-life data. Finally, we discuss some implica- tions of local elasticity to shed light on several intriguing aspects deep neural networks.
INTRODUCTION
Neural networks have been widely used in various machine learning applications, achieving com- parable or better performance than existing methods without requiring highly engineered features (Krizhessky et al., 20122). However, neural networks have several intriguing aspects that defy con- ventional views of statistical learning theory and optimization, thereby hindering the architecture de- sign and interpretation of these models. For example, despite having more parameters than training examples, deep neural networks generalize well without explicit form of regularization (Zhang cct al. 2017 NNyshabby et al., 2017 Arora et al. 2019a). Zhang et al. (2017) also observe that neu- ral networks perfectly fit corrupted labels while maintaining a certain amount of generalization power]
In this paper, complement this line of findings by proposing hypothesis that fundamentally dis- tinguishes neural networks from linear classifier 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 x and its label y impact the prediction the neural networks at another imput x! ?
Taking this dynamic perspective, make the following three contributions.
First, we hypothesize that neural networks are locally elastic in the following sense: an extensive set of experiments synthetic examples demonstrate that the impact on the prediction of x' is significant if æ' is in a local vicinity of æ and the impact diminishes as x' becomes far from æ in elastic manner. In contrast, local elasticity is not observed in linear classifiers due to the leverage effect (Weisberg, 2005). Thus, at high level, local elasticity must be inherently related
"hii property also holds for the 1-nearest neighbors algorithm.
Without using the kernel trick, these classifiers include linear regression, logistic regression, support vector machine, and linear neural networks.

---

Published conference paper at ICLR 2020
1.0
Relative Similarity
1.00
Relative Simitanty
1.0
0.5
0.75
0.0
2
0.50
0.5
1.0
0.25
5
0.00
0.0
-5
Y
Geodesic Distance
Geodesic Distance
(a) The torus.
(b) Two-layer nets fitting the torus. (c) Two-layer linear nets fitting
the torus.
Relative similarity
1.25
Relative Similarty
1.00
1.0
0.75
0.50
10
0.25
10
0
20
30
10
30
10
Geodesic Distance
Geodesic Distance
(d) The two folded boxes.
(c) Three-layer nets fitting the (f) Three-layer linear nets fitting boxes.
the boxes.
Figure 1: Comparisons between ReLU neural networks and linear neural networks in terms of local elasticity. In the left column, the red points form one class and the blue points form the other class. The linear nets are of the same sizes their non-linear counterparts. The details how construct the torus and boxes can be found in Appendix A and the network architectures are described in Appendix A..4 During the training process of the neural networks, we plot the geodesic distance (see more details in Appendix A. between two blue points æ and , and their relative prediction changes (see its definition Equation (2)) in (b), (c), (e), and (f). The correlations of (b), (c), (e), and (f) are -0.97, -0.48. - 0..2., and -0 0.14, respectively. (b) and (e) show that the distance and the relative change exhibit decreasing monotonie relationship. thereby confirming local elasticity, while no monotonic relationship is found in (c) and (f).
to the nonlinearity neural networks and SGD used in updating the weights. This phenomenon illustrated by Figure [ Additional synthetic examples and ImageNet (Deng al.) (2009) with pre- trained ResNet (He et al. 2016) in Appendix A.2 further confirm local elasticity. For completeness, remark that the notion of local elasticity seems related to influence functions on the surface (Koh) & Liang 2017). The fundamental distinction, however, that the former takes into account the dynamics of the training process whereas the latter does not. See Section 2 formal introduction of the notion of local elasticity.
Furthermore, we devise clustering algorithm by leveraging local elasticity of neural networks. In short, this algorithm records the relative change of the prediction on 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 this local glasticity-basee clustering algorithm. For two superclasses (e.g., mammal and vehicle), the algorithm is capable of partitioning the mammal class into eat and dog, and the second superclass into car and truck. These empirical re- sults, in turn, corroborate our hypothesis that neural networks (with nonlinear activation) are locally elastic. See the description of the algorithm Section 3 and experimental results in Section
Finally, this paper provides profound implications of local elasticity memorization and gener- alization 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 exam- ples that have been well fitted. This property is akin the nearest neighbors algorithm (see, e.g., Papernot & McDaniel (2018)). Meanwhile, the elasticity part implies that the prediction surface is
2

---

Published conference paper at ICLR 2020
(a) Linear classifier updated by SGD.
(b) Neural networks updated by SGD.
Figure 2: An illustration of linear regression and neural networks updated via SGD. The prediction of changes a after an SGD update on æ in the linear case, though æ' is far away from æ. In contrast, the change in the prediction at æ' is rather small in the neural networks case.
likely to remain smooth in the training process, in effect regularizing the complexity of the nets in certain sense. These implications are discussed in detail in Section
1.1 RELATED WORK
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 certain intrinsic rigidity of the linear regions may improve the generalization. Fawzi al. (2017) 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 dynamic perspective on 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 Homik
et al. 1989 Barron 1993). Lately, deep neural networks have been shown to possess better rep- resentational power than their shallow counterparts (Delalleau Bengio 2001 Telgarsky 2016)
Eldan & Shamir 2016 Mhaskar & Poggio 2016 Yarotsky [017 Chen et al. 2019). From
parametric viewpoint, approximation risks are obtained for neural networks under certain smooth
assumptions on the regression functions (Schmidt-Hieber 2017 Suzuki 2018
Klusowski & Bar-
ron 2018 Liang 2018, Bauer Kohler 2019 E et al. 2019a).
A less related but more copious line of work focuses optimization for training neural networks. A popular approach to tackling this problem is to study the optimization landscape of neural net-
works (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 Soltanoktaao Bruzzkuu
Brutzkus & Globerson, 2017; Du et 2018 Li Liang
2018
Allen-Zhu al.) 2018 Zou al.) 2018 Du et al.] [2019] Allen-Zhu
al.] 2019). Alterna-
tively, researchers have considered the evolution of gradient descent on two-layer neural networks
using optimal transport theory (Song et al. 2018 8 Chizat & Bach 2018 Sirignano & Spiliopoulos/
2019
Rotskoff & Vanden-
2018). More recently, there is a growing recognition of intimate
similarities between over over- parameterizeedd neural networks and kernel methods from an optimization
perspective (Zhang al. 2017 Daniely 2017 Belkin et al. 2018 Jacot et al. 2018 Yang 2019 Arora et al., 2019b) et al. 2019 E ct al. 2019b). For completeness, some work demonstrates
certain superiority of neural networks in generalization
the corresponding kernel methods (Wei
et al. 2018 Allen-Zhu & 2019 Ghorbani et al. 2019)..

---

Published conference paper at ICLR 2020
2 LOCAL ELASTICITY
This section formalizes the notion of local elasticity and proposes associated similarity measures that will be used for clustering in Section 3 Denote by 2 E R and y the feature vector and the label of an instance (ax y), respectively. Let f(z w) be the prediction with model parameters w, and write L)),)) for the loss function. Consider using SGD to update the current parameters w using the instance (xe, y):
(LC(s(a,, dw
(a) [f(a, w)
w
(1)
Of
dr
In this context, we say that the classifier f is locally elastic at parameters w if [f(x,, w f(',, w)). the change the prediction at a test feature vector x'. relatively large when and x' are similar/close, and vice versa. Here, by similar/close, we mean two input points æ and a' share many characteristics or are connected by short geodesic path in the feature space. Intuitively, and x' are similar if æ denotes an Egyptian cat and x' denotes a Persian cat; they are dissimilar if a denotes a German shepherd and x' denotes trailer truck.
For illustration, Figure update on æ leads to significant impact on the prediction at æ', though a' is far from ax; on the other hand, the (nonlinear) classifier in Figure 2 is locally elastic since the change at x' is relatively small compared with that at æ. In Section 2.3 we provide some intuition why nonlinearity matters for local elasticity in two-layer neural nets.
a[a) shows that the (linear) classifier is not locally elastic since the SGD
2.1 RELATIVE SIMILARITY
The essence of local clasticity is that the change in the prediction has an (approximate) monotonic relationship with the similarity of feature vectors. Therefore, the change can serve proxy for the similarity of two inputs æ and x':
(2) |f(x', w f(x', 1aaa,,u, w)l
(2)
15(æ, w fxx w)l
In the similarity measure above, [f w+ f(x w)) is the change in the prediction of (æ: y) used for the SGD update, and , f(x,, w)] is the change in the output a test input a'. Note that (3, x²) not necessarily symmetric and, in particular, the definition depends on the weights w. Our experiments in Section (uggest the use of a near-optimal w (which is also the case in the second definition of local elasticity in Section 2.2p. In the notion of local elasticity, locality suggests that this ratio is large when and x' are close, and vice versa, while elasticity means that this similarity measure decreases gradually and smoothly, as opposed abruptly, when a' moves away from æ. Having evaluated this similarity measure for (almost) all pairs by performing SGD updates for several epochs, we can obtain a similarity matrix, whose rows are each regarded as a feature vector of its corresponding input. This can be used for clustering followed by K -means.
2.2 KERNELIZED SIMILARITY
Next, we introduce a different similarity measure that manifests local elasticity by making a connec- tion to the neural tangent kernel (Jacot et al., 2018). Taking small learning rate 77, for a new feature point x', the change in its prediction due to the SGD update in Equation
[1
approximately satisfies:
dL af(r,w)
f( f(x', w)) f (.. " 0f Ow
f(x',w)
1f w)
dw 1 AL
0f(x, w) f(),
f w)
of
Ow
OL @8(('' w) Ow
0f w)
-a dw The factor of 8C does not involve x'. just as the denominator [f w - f (xx, w)) in Equation 2
This observation motivates an alternative definition of the similarity:
f(x', w) - f(x', w)
Swer (x, x()
(3)
1) DCT (m w)))))
af

---

Published conference paper at ICLR 2020
In the case of the &z loss L(f,v) = 2 y)² for example, (x, x²)
f(x', -00) a0 In
(((-v)
Section [] we apply the kernel K-means algorithm to this similarity matrix for clustering.
The kernelized similarity in Equation (3) is approximately the inner product of the gradients of at a: and aF5 This is precisely the definition of the neural tangent kernel (Jacot al., 2018) (see also Arora et al. (2019b)) if 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 data-adaptive w may lead to more significant local elasticity. Explicitly, both similarity measures with pre-trained weights yield better performance of Algorithm (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).
2.3 INTERPRETATION VIA TWO-LAYER NETWORKS
We provide some intuition for the two similarity measures in Equation 2 and Equation (3) with two-layer neural networks. Letting œ = (xx 1) E Rd+1, denote the networks by f(x, w)
Ex=1 (,0(w0, æ), where (.) is the ReLU activation function (a((x) = x for x 2 0 and o (xr
otherwise) and w [w] ...... ) ) E Rmm(d+1), For simplicity, we set aş E 111.1. Note that
this does not affect the expressibility of this net due to the positive homogeneity of ReLU.
Assuming 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
f(x', w=) )- f w) fax (w,,w=) f(x, w)
(1 o()) (x x + +1) 12 Φ > 0311 V' 2 20}
(4)
(| 1) - 0}
Above, ||||| denotes the l2 norm. For comparison, we get f(m',u=) . fla a an)
+1 for the linear
neural networks f(zz) := -
For both cases, the change in the prediction at x' resulting
from an SGD update at (x, involves multiplicative factor of x x' However, the distinction is that the nonlinear classifier f gives rise dependence of the signed Sker x') on the fraction of neurons that are activated at both æ and x'. Intuitively, close similarity between and x' can manifest itself with large number of commonly activated neurons. This made possible by the nonlinearity of the ReLU activation function. We leave the rigorous treatment of the discussion here for future work.
3. 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) super- class (e.g., mammal) and the interest is, however, partition the primary examples into finer- mner-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 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. brief, the algorithm operates as 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 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.
As opposed to the relative similarity, this definition does not take absolute value in order to retain its interpretation as an inner product.
5

---

Published conference paper at ICLR 2020
Algorithm The Local Elasticity Based Clustering Algorithm.
Input: primary dataset P ) auxiliary dataset A = { 1- classifier f(æ, w), initial weights Wo, loss function L. learning rate T/, option o E(relative kernelized]
1: combine D {(x,, 3/ for æ; (( = -1) for E A}
2: set to n n matrix of all zeros
3: for t = 1 to m do
4: sample (æ: y) from w/o replacement
5: wr SGD(w,,1,,0 y, m))
6:
if y then
7:
p: -Fredict w/ P.f)
8:
find 1 - i S such that a = E P
9:
if o = re at ive then
10:
P: P
(. 11))-p-110
11:
else
12:
= GetGraciiettwu..111221
13:
8; Pi Pi-Pi-1
14:
end if
end if
16: set the ith row S(i,:)
end for
18: Saymm (S ST)
19:
Ysubelass = Clustering Ssymm)
20:
return Vaubclass
This method is formally presented in Algorithm [ with elaboration as follows. While the initial parameters wy often set to i.i.d. random variables, our experiments suggest that "pre-trained" weights can lead better clustering performance. Hence, use warm-up period to get nearly optimal we by training on the combined dataset D. When the SGD performed at a primary example x; (labeled yi 1) during the iterations. the function Predict (w, f) E R" eval- uates the predictions for all primary examples at w,, and these results are used to compute similarity measures between and other pri- mary feature vectors using Equation (2) or Equation (3). depending on the option. If one chooses use the kernelized similarity, the function GetGradient is called to the gradient of the loss function repeat the
Mammal (primary)
Dog
Cat
Vehicle (auxiliary)
L at w;-1, (z. y) with respect to f. In practice. loop multiple times and then average the similarity matrices over the epochs. Finally, using the symmetrized Ssymm, we apply off-the- shelf clustering method such as K K-means (for relative similarity) or kernel K K-means (for kernel similarity) partition the primary dataset P into subclasses.
Figure 3: Illustration of the primary dataset and auxil- iary dataset taken as input by the local elasticity based clustering algorithm.
EXPERIMENTS
4.1 EXPERIMENTAL SETTINGS
We evaluate the performance of Algorithm MNIST (LeCun) 1998) and CIFAR-10 Krizhevsky 2009]. For the MNIST dataset, we choose the 6 pairs digits that are the most difficutt for the binary K-means clustering, Likewise, 6 pairs of classes are selected from CIFAR-10. For each pair (e.g.. and 8), we construct the primary data set by randomly sampling a total 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 two classes, evenly distribute the 1000 examples across the two classes).
Our experiments consider two-layer feedforward neural networks (FNN, which is also used in Fig- ure D. CNN (Krizhevsky et al.) 2012), and ResNet (He al. 2016). We 40960 neurons with the ReLU activation function for two-layer FNN and details of the other architectures can found

---

Published conference paper at ICLR 2020
Primary Examples
5 vs
4 vs
v
v
3 v
3 vs 8
Auxiliary Examples
3,
5.7
4.
4, 8
8, 9
5
K K-means
50.4
54.5
55.5
56.3
69.0
76.5
PCA + K -means
50.4
54.5
55.7
56.5
70.7
76.4
(z-relative(linear)
51.0
54.6
51.3
58.8
58.3
58.7
22 2--kemelized (linear)
50.1
55.5
55.5
56.3
69.3
76.
BCE-relative (linear)
50.1
50.0
50.2
50.6
51.4
50.1
BCE-kemelized (linear)
50.7
56.7
62.3
55.2
53.9
51.6
Eg-relative (ours)
75,9
55.6
62.5
89.3
50.3
74.7
Eg lz-kernelized (ours)
71.0
63.8
64.6
67.8
71.5
78.8
BCE-relative (ours)
50.2
50.5
51.9
55.7
53.7
50.2
(ours)
52.1
59.3
64.5
58.2
52.5
51.8
Classification accuracy of Algorithm | and other methods on the MNIST dataset. BCE stands for the binary cross-entropy loss. We use K K-means for relative similarity based clustering algorithms, and kernel K K-means for kernelized similarity based clustering algorithms. For example, CCE-kkereliize (linear) denotes the setting that uses the BCE loss, kernelized similarity and the linear activation function. The highest accuracy score in each study is in boldface.
Table 1:
Primary Examples
Car vs Cat
Car vs Horse
Cat vs Bird
Dog vs Deer
Car vs Bird
Deer vs Frog
Auxiliary Examples
Bird
Cat, Binl
Car
Frog
Cat
Dog
K K-means
50.3
50.9
5T.1
51.6
51.8
52.4
PCA + K -eans
50.6
51.0
51.1
51.6
51.7
52.4
Eg-relative (linear)
50.0
56.8
55.2
50.6
56.3
52.5
ty lg-kernelized (linear)
50.4
50.7
51.1
51.3
51.9
52.8
BCE--rlative (lincar)
50.4
50.9
50.2
50.6
55.3
50.2
BCF-kernelized (lincar)
55.7
58.1
52.0
50.5
53.0
?z-relative (ours)
53.7
50.2
58.4
54.2
63.0
53.5
fz-kernelized (ours)
52.1
50.5
53.6
52.7
50.5
53.0
BCE-relative (ours)
51.1
53.5
50.7
51.1
55.6
50.3
BCE-kernelized (ours)
58.4
59.7
56.6
51.2
55.0
51.8
Table 2: Classification accuracy of Algorithm
I and other methods on the CIFAR-I0 dataset.
in Appendix A.4 We consider two types of loss functions, the lg loss and the cross-entropy loss C(F. y) y log( Note that neural networks with the cross-entropy loss have an extra sigmoid layer top of all layers. We run Algorithm (with the identity activation function) with the same architectures of their nonlinear counterparts are used baseline models. Here, the of linear neural networks instead of linear regression is to prevent possible influence of over-parameteriiztion on our experimental results [4] We also consider K-means and principal component analysis (PCA) followed by K-mean simple baselines.
epoch. For comparison, linear neural networks
4.2 RESULTS
Comparison between relative and kernelized similarities. Table and Table dableddisplay the results on MNIST and CIFAR-10, respectively. The relative similarity based method with the &g loss per- forms best CIFAR-10 10, while the kernelized similarity based method with the & loss outperforms the other methods on MNIST. Overall, our methods outperform both linear and simple baseline models. These results demonstrate the effectiveness of Algorithm and confirm our hypothesis of local elasticity in neural nets well.
The results of Algorithm with the aforementioned three types of neural networks, namely FNN, CNN, and ResNet on MNIST are presented in Table 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.
Comparison between architectures.
'In fact, our experiments show that the two models exhibit very similar behaviors.

---

Published conference paper at ICLR 2020
Primary Examples
vs
4 vs
7 v
vs
3 vs
3 vs 8
Auxiliary Examples
3.9
7,
4.5
4.
8, 9
5
6y-relative (FNN)
75.9
55.6
62.5
89.3
50.3
74.7
l2-kernelized (FNN)
71.0
63.8
64.6
67.8
71.5
78.8
12-relative (CNN)
54.2
53.7
89.1
50.1
50.1
83.0
2 ee-eenelized (CNN)
64.1
69.5
91.3
97.6
75.3
87.4
lg-relative (ResNet)
50.7
55.0
55,5
78.3
52.3
52.3
2g kernelizzed (ResNet)
50.2
60.4
54.8
76.3
66.9
68.8
Table 3: Comparison of different architectures for the local elasticity based clustering algorithm. We only consider the & loss on MNIST here for the sake of simplicity.
Primary Examples
5 vs 8
4 vs 9
7 vs 9
5 vs 9
3 v
vs
Auxiliary Examples
3,
5,
4,
4, 8
8,
AutoEncoder
50.9
54.0
61.8
70.0
64.3
67.1
ResNet-152
85.2
94.2
93.1
82.0
65.8
96.0
U2-relative (ours)
54.2
53.7
89.1
50.1
50.1
83.0
2/2 fa-kernelized (ours)
64.1
69.5
91.3
97.6
75.3
87.4
Table 4: Comparison with other feature extraction methods. For simplicity, we only consider CNN with &g loss on MNIST. The features from autoencoder and ResNet- 152 are clustered by K K-means.
To further evaluate the effectiveness of the local elasticity based Algorithm T we compare this clustering algorithm using CNN with two types of feature extraction approaches: autoencoder 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
ImageNet (Deng al.. 2009) and can be used to extract features of images. The performance of those models on MNIST 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 1esNet-112, our methods do not require a large number of examples for pre-training" To better appreciate local elasticity and Algorithm [] 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.
5 IMPLICATIONS AND FUTURE WORK
In this paper, we have introduced a notion of local elasticity for neural networks. This notion en- ables 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 neural networks. While having shown the local elasticity in both synthetic and real-world datasets, we acknowledge that mathematical foundation of this notion is yet to be developed. Specifically, how to rigorous formu- late 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 profound im-
com/ master/08-aa oEcooder www._aatoenccceeeeeeeoooo -py
We use the autoencoder in http:://hhhhcooccoococc...scssts
Here, the comparison between our methods and ResNet-152 152 on CIFAR-10 is not fair since ResNet-152
trained using samples from the same classes CIFAR-10.
"As remark, here we not compare with other clustering methods that are based neural networks, such as DEC (Xie et al. (0166). We can replace K-means by other clustering algorithms to possibly improve the performance in some situations.

---

Published conference paper at ICLR 2020
pact 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 local method. We say a method is local seeks to data point only using observations within 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 fiuting even random labels perfectly (Zhang al. 2017), with provable guarantees under certain conditions FAllen-Zhu et al.) 2019 Du et al. 2019; Oymak & Soltanolkotabi 2019). Intuitively, local elasticity leads neural nets to progressively fit the examples a vicinity of the imput 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-fre 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.
Data normalization and batch normalization. The two normalization techniques are commonly used improve the performance of neural networks (Gonzalez & Woods 2002: loffe & Szegedy 2013). The local elasticity viewpoint appears to imply that these techniques allow for a more solid relationship between the relative prediction change and a certain distance between feature vectors. (r. Section 2.2 reveals that the kernelized similarity Precisely, writing the lifting map (pxr) RV due
approximately satisfies err (x, x') a [|{p())) [|a=a=="==(="]]]======( x')x)²²²²² where d(æx, x') = [)+ pp(x']l. To obtain negative correlation between the similarity and the distance, therefore, one possibility is to have the norms of p(z) and p0x') about equal to a constant. This might be made possible by employing the normalization techniques. See some empirical results in Appendix [A.4] [..4 A venue for future investigation is to consolidate this implication on normalization techniques.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can ResNet learn efficiently, going beyond kernels? arXiv preprint arXiv: 10337, 2019.
Zeyuan Allen-Zhu Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. arXiv preprint arXiv:1811.04918 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In ICML, pp. 242-252, 2019.
Sanjeev Arora, Naday Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint
2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv:1904.11999 2019b.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function.
IEEE Transactions on Information Theory, 39(3)9930-945, 1993.

---

Published conference paper at ICLR 2020
Benedikt Bauer and Michael Kohler. On deep learning remedy for the curse of dimensionality in nonparametric regression. The Annals of Statistics, 47(4):221122285, 2019.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. In ICML, pp. 540-548, 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. JMLR, 2(Mar):499-526 2002.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for ConvNet with Gaussian inputs. In /CML, pp. 605-614. JMLR. org, 2017.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions low dimensional manifolds. arXiv preprint arXiv: (ee::::080.088 2019.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-
parameterized models using optimal transport. In NIPS, pp. 3036-3046, 2018.
Anna Choromanska, Mikael Henaff, Michael Mathicu, Gerard Ben Arous, and Yann LeCun. The loss surfaces multilayer networks. JMLR, 38:192-221188 192-204, 2015.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con- trol, Signals and Systems, 2(4):303-314 1989.
Amit Daniely. SGD learns the conjugate kernel class of the network. In NIPS, pp. 2422-2430, 2017.
Olivier Delalleau and Yoshua Bengio. Shallow vs. deep sum-product networks. In NIPS, pp. 666- 674, 2011.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, pp. 248-255, 2009.
Xialiang Dou and Tengyuan Liang. Training neural networks learning data-adaptive kemels:
Provable representation and approximation benefits. arXiv preprint arXiv:1901.07114 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global
minima of deep neural networks. In ICML, pp. 1675-1685, 2019.
Simon S Du and Jason D Lee. On the power of over-parametrization in neural networks with quadratic activation. In ICMI, pp. 1328- 1337, 2018
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint 1.10000/1000004. 2018.
Weinan E, Chao Ma, and Lei Wu. Barron spaces and the compositional function spaces for neural network models. arXiv preprint (0t6::990000033 2019a.
Weinan E, Chao Ma, and Lei Wu. A comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynam- ics. arXiv preprint arXiv: (000:1904.000 04326, 2019b.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In COLT, pp. 907-940. 2016.
Jianqing Fan. Local polynomial modelling and its applications: monographs on statistics and ap- plied probability 66. Routledge, 2018.
Alhussein Fawzi. Geyed-Mohsen Moosavi-Dezfooli, Pascal Frossard, and Stefano Soatto. Classifi- cation regions of deep neural networks. arXiv preprint / 2017.
Alhussein Fawzi, Seyed-Mohsen
Pascal Frossard, and Stefano Soatto. Empirical study of the topology and geometry of deep networks. In CVPR, pp. 3762-3770, 2018.
10

---

Published conference paper at ICLR 2020
Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: A new perspective on generalization neural networks. arXiv preprint arXiv: /911009901 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks high dimension. arXiv preprint arXiv:1904.12199 2019.
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdehorová. Modelling the influence of data structure on learning in neural networks. arXiv preprint arXiv: 1500, 2019.
Rafael C Gonzalez and Richard E Woods. Digital image processing, 2002.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In ICML, pp. 2596-2604 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, pp. 770-778, 2016.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural Networks, 2(5):359-366, 1989.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In JCML, pp. 448 456, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. In NIPS, pp. 8571-8580, 2018.
Jason M Klusowski and Andrew Barron. Approximation by combinations of relu and squared relu ridge functions with ε and in controls. IEEE Transactions on Information Theory, 64(12): 7649-7656, 2018
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In ICML, volume 70, pp. 1885-1894, 2017.
A Krizhevsky. Learning multiple layers of features from tiny images. Master's 's thesis, University of Tront, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convo- lutional neural networks. In NIPS, pp. 1097-1105, 2012.
μÍaa Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In ICMI,, pp. 2820-2829, 2018.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv: 190.:6990, 2019.
Yuanzhi Li and Yingyu I Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In NIPS, pp. 8157-8166, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In NIPS, pp. 597-607, 2017.
Shiyu Liang, Ruoyu Sun, Jason D) Lee, and Rayadurgam Srikant. Adding one neuron can eliminate all bad local minima. NIPS, pp. 4350 4360, 2018.
Tengyuan Liang. On how well generative adversarial networks learn densities: Nonparametric and parametric results. arXiv preprint arXiv: 2018.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep shallow networks: An approximation theory perspective, Analysis and Applications, 14(06):829-84) 848, 2016.

---

Published conference paper at ICLR 2020
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. NIPS, pp. 2922-2932, 2014.
Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, and Nathan Srebro. Geometry of opti- mization and implicit regularization in deep learning. arXiv preprint arXiv:/005.0307,, 2017.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizaaton:: global conver- gence guarantees for training shallow neural networks. arXiv preprint arXiv:1902.04674, 2019.
Nicolas Papernot and Patrick McDaniel. Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint arXiv:1803.04765 2018.
Grant M Rotskoff and Eric Vanden- Vanden-Eijnden, Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation emror. arXiv preprint /80iv
2018.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. Science, 290(5500):2333-2333 2322233 2000.
Itay Safran and Ohad Shamir. Spurious local minima common in two-layer relu neural networks. In ICML, pp. 4430 4438, 2018.
Johannes Schmidt- Hieber. Nonparametric regression using deep neural networks with relu activation function. arXiv preprint vrXivv1708.066... 2017.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. Stochastic Processes and their Applications, 2019.
Mahdi Soltanolkotabi. Learning ReLUs via gradient descent. In NIPS, pp. 2007-2017, 2017.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of pre-pparamteerized shallow neural networks. IEEE Transactions on Information Theory, 6562),742-766, 2018.
Mei Song, Andrea Montanari, and P Nguyen. A mean field view of the landscape of two-layers neural networks. Proceedings of the National Academy of Sciences, 115:E7665-E7671 2018.
Daniel Soudry and Elad Hoffer. Exponentially vanishing sub-optimal local minima in multilayer neural networks. arXiv preprint arXiv: 1702.057777 2017.
Taiji Suzuki. Adaptivity of deep relu network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:1810.08033 2018.
Matus Telgarsky. benefits of depth in neural networks. In COLT, pp. 1517-1539, 2016.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLu network and its applications convergence and critical point analysis. In ICML, pp. 3404-3413. JMLR, org, 2017.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kemnel. arXiv preprint arXiv:1810.05388 2018.
Sanford Weisberg. Applied linear regression, volume 528. John Wiley Sons, 2005.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In ICML, pp. 478-487, 2016.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:/902.044 2019.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
12

---

Published conference paper at ICLR 2020
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.
Yi Zhou and Yingbin Liang. Critical points of neural networks: Analytical forms and landscape properties. arXiv preprint arXiv: /205, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arXiv preprint
2018.
13

---

Published conference paper at ICLR 2020
A EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
A.1 CONSTRUCTION OF THE SYNTHETIC EXAMPLES IN FIGURE
The blue examples in the torus function (Figure T(a) can be defined parametrically by:
xx) (8 + sin(
0
v(0) () = (8 + sin (44) sin 0
(5)
x(0) = cos (40)
Similarly, the red examples in the torus function are defined by:
xx) (8 sin(40))
v(0) = (8 sin sin 0
(6)
=() cos (40)
The blue examples in the two folded boxes function (Figure I(d) are sampled from:
|0l 1.2 |
(7)
E [1,
Similarly, the red examples in the two folded boxes function are defined
lyl + 1.2 |=| = 11
1,
Geodesic distance is used to measure the shortest path between two points in a surface, or more generally in Riemannian manifold. For example, in Figure [ the geodesic distance for the torus function and the two folded boxes function is the distance in the curve and the distance the surface rather than the Euclidean distance.
A.2 MORE SIMULATIONS
More simulations can be found in Figure
We further explore the local elasticity of ResNet-152 on ImageNet. We find that, when the pre- trained ResNet-152 are updated on 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 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 the 25 warplanes. By conducting Wilcoxon rank-sum test with SGD updates on 50 different tabby cats, we find that the average change the predictions on the tiger cat significantly more drastic than that on the warplane with a p-value of 0.000.. 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 computed from the relative KL divergence between the original prediction and the updated prediction.
Specifically, we find that the change the predictions (KL divergence of 0.03) on the tiger cat (Figure ( is more drastic than that (KI. divergence of 0.002) on the warplane (Figure 5(c) after a SGD update on the tabby cat (Figure (5a)), 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 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
the tabby cat (Figure b(c) KL divergence of 0.021) and the warplane (Figure [[d] KL divergence of 0.024) are more substantial than that on the tree frog (Figure ((c) KI divergence of 0.0004) after SGD update the minibatch composed of tabby cat (Figure ((a) and a warplane (Figure
14

---

Published conference paper at ICLR 2020
Relative Similarity
1.0
1.00
0.5
0.75
0.50
0.0
0.25
-0.5
-
0
2
2 Geodesic Distance
x
(a) Two cosine functions.
(b) The local elasticity two-layer neural nets fitting these two cosine functions.
Relative Similarity
1.00
0.75
0 Z
0.25
3.3
-1....0000 0.5 1.0
0
2
3
0.3
Geodesic Distance
(c) The double helix function.
(d) The local elasticity of two-layer neural nets fitting the double helix function.
50
1.00
Relative Similarity
0.75
0.50
0.25
-50
-50
50
Geodesic Distance
(e) Two cycle functions.
(l) The local elasticity of two-layer neural fitting two cycle functions.
1.00
Relative Similarity
0.75
10
0.50
-10
0.25
-2
10
20
0.00
10
2 Geodesic Distance
110
X
10
20
20
(g) Two sphere functions.
(h) The local elasticity of two-layer neural fitting two sphere functions.
Figure 4: More simulations of the local elasticity.
15

---

Published conference paper at ICLR 2020
(a) A tabby cat.
(b) A tiger cat.
(c) A warplanc.
Figure 5: Simulations in real data. We show specific examples for a tabby cat, tiger cat and warplane.
(a) A tabby cat (train).
(b) A warplane (train).
(c) tabby cat (test).
(d) A warplane (test),
(c) tree frog (test).
Figure Simulations showing local elasticity with mini-batch SGD.
A.3 SOME CALCULATIOOS
We brief explain how to obtain Equation
under the same assumptions of Li & Liang (0188)
[ w++ f(x', w)
a a ((w (
xx))
Σ a x²)
OC
0,0
w.
xl x 2 20} x'
Σ aw x')
of
m
a,o
n of
a
x'1l
v'llww 20}
Σ
a, awo(w.x)
A A2
16

---

Published conference paper at ICLR 2020
where
dL m
A1 = -1 0f
Σ a
x I'I(
0fIfw, 2 0
0C
m
af x²'
[ 2 03T 20
and
0C
11 [ w x' "1 0 a. x' a'w 2 0) 2 0) 1( x' 2 20}
0C
|
01 o
x xl 2 0}
0C
dc
u x I'I(w, x 2 03 2 20 I[ x' 2 03
11
x x
T W x 2 0] [1
w, x²'
11 0f
0f
0f 0f
0L
x Ta'
m
T W x 2 03
w. _n x'
11 0f
OL
a, x' 2 0f I(w, x' 2 03
As shown in Li & Liang
2018). only vanishing fraction of the neurons lead to different patterns
between II {
u x'
0C Maf a x' 0) and I(w, x' 2 0}. Consequently, we get | < |41/.
thereby certifying
Oc f('', w+w f(x', w) - +()))
x Σ m 2 0f1(wW1 x' 2 20}
0f
x: Jxx Dr= (w ( x'' 2 0] (f(x, w f(x, w)).
= =11+
I x 2
r=
A.4
MORE ASPECTS ON THE EXPERIMENTS
Primary Examples
vs
vs
vs
5 vs
vs
Auxiliary Examples
3,9
5,
4, 5
4, 8
8, 9
5
f2-relative (random)
50.9
55.2
51.2
59.0
58.5
59.9
8
le-kennllzeed (random)
50.4
55.5
55.7
56.6
68.4
75.9
22-relative (ours)
75.9
55.6
62.5
89.3
50.3
74.7
87 ke-keelllized (ours)
71.0
63.8
64.6
67.8
71.5
78.8
Table 5: Comparison of two different settings, random and optimal (default), for parameter initial- ization. For simplicity, we only consider & loss on MNIST here.
Architectures We 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 three-layer net that contains 4096 neurons and a ReLU activation function in each layer. The CNN for MNIST we use in experiments the same architecture as that in https: //gituu com/ pytorch www.a/eee//oo///mmttteeeeeeeeeee
in experiments is
Weights. discussed in Section parameter initialization is important for local elasticity based clustering methods. We find that the optimal setting always outperforms the random setting. It
Primary Examples
5 vs 8
5 vs 8
5 vs 8
vs
5 8
vs
Auxiliary Examples
3, 9
6,
2,3
2, 6
3
Ey-relative (ours)
75.9
53.7
54.3
51.2
53.9
60.6
fz-kernelized (ours)
71.0
54.4
50.2
51.6
50.6
54.4
BCE-relative (ours)
50.2
50.4
50.1
50.2
52.3
50.1
CCE-kernelized (ours)
52.1
52.7
51.6
52.4
50.3
50.3
Table 6: Comparison of different auxiliary examples for 5 vs 8 on MNIST.
17

---

Published conference paper at ICLR 2020
Primary Examples
5 vs
vs
vvs
5
vs
3 vs 8
Auxiliary Examples
3.
5,7
4.5
4, 8
8, 9
5
f2 "g-kernelized (ours)
71.0
63.8
64.6
67.8
71.5
78.8
BCE-kernelized (ours)
52.1
59.3
64.5
58.2
52.5
51.8
n--nommalzzdd--emmeizzdd (ours)
71.3
62.3
64.8
68.0
73.0
79.5
hett-normalizze-keeeeelll (ours)
52.0
57.5
61.0
56.9
50.1
75.2
Table 7: Comparison between the kernelized similarity based methods and the normalized kemel-- ized similarity based methods on MNIST.
Primary Examples
vs 8
vs
v
vs 9
vs
3 vs
Auxiliary Examples
3.
5,7
4,
4.8
8, 9
5
lz-relative (unnormalized)
51.5
58.4
55.9
53.0
69.9
75.5
2g kernelized (unnormalized)
51.4
56.1
55.3
57.2
62.1
75.1
BCE-relative (unnormalized)
50.1
50.3
50.7
53.2
50.9
50.1
BCE-kernelized (unnormalized)
50.6
56.9
59.6
54.4
52.2
50.8
fg-relative (ours)
75.9
55.6
62.5
89.3
50.3
74.7
ly-kernelized (ours)
71.0
63.8
64.6
67.8
71.5
78.8
BBEErelative (ours)
50.2
50.5
51.9
55.7
53.7
50.2
BCEE-ernelized (ours)
52.1
59.3
64.5
58.2
52.5
51.8
Table 8: Comparison of the clustering algorithms without data normalization MNIST. Note that we use data normalization by default.
Activation Similarity
1.00
1.0
Relative Similarity
0.75
0.8
0.50
0.6
0.25
0.4
5
10 15
0
2
3
Euclidean Distance
Geodesic Distance
Activation analysis of two-layer neural nets with (b) The local elasticity of two-layer neural with sigmoid activation function on the torus function.
ReLU activation function on torus function.
Figure 7: The activation analysis and the activation function analysis of neural nets local elasticity. The Pearson correlation between the cosine similarity based activation patterns and the corre- sponding Euclidean distances is -0.97 on the torus function. The cosine similarity within activation patterns indicates the Euclidean distance between two data points. The Pearson correlation be- tween the relative similarity based on two-layer neural nets with sigmoid activation function and the geodesic distance is 00.99. It indicates that two-layer neural nets with sigmoid activation function also have a strong local elastic effect.
18

---

Published conference paper at ICLR 2020
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
Auxiliary examples. In general, we can choose those samples that are similar to primary examples auxiliary examples, they help neural nets better learn primary examples. We analyze the primary examples pair and 8 in MNIST with 6 different settings of auxiliary examples. We find that the choice of auxiliary examples crucial. For example, our case close to 8 based on K 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 on MNIST are shown in T
close 5 and is
Normalized kernelized similarity. The normalized kernelized similarity is
Sker (z, ar) == Swer (ar, a:) a/// Shee (æ. ar) Sker (x', (a:'
.r).
The normalized kernelized similarity can achieve more stable local elasticity. We compare clustering algorithms based on kernelized similarity and normalized kernelized similarity in MNIST. We find that the performance of the normalized kernelized similarity based methods is slightly better than that of kernelized similarity based methods with the le loss, although this conclusion no longer holds true with cross-entropy loss. The results of the normalized kernelized similarity are shown in Table 7
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 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 ReLU activation function of two-layer neural nets and corresponding Euclidean distances. For each input æ, we use a to denote the binary activation pattern 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 ((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 clasticity. The local elasticity of two-layer neural nets with sigmoid activation function on the torus function is shown in Figure 7(b)
Data normalization. Table The results show that normalization is important for our methods, which are consistent with analysis in Section
The performance of the methods without data normalization shown in
19


Reviews:
[{"review_id": "ryxdtTj1qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies an interesting phenomenon in neural network models that the classifier's prediction at a one input will not be significantly perturbed after the classifier is updated via sgd at another input that is dissimilar from the former one. This phenomenon is termed as the local elasticity, which provides another perspective seeking to interpret the neural networks. They present that this local elasticity characteristic does not hold for linear models. To further investigate this property, the paper introduces the relative similarity and kernelized similarity based on which a k-means like clustering algorithm is developed to further find fine-grained clusters within a coarse-grained category, like dogs and cats from the mammal category. Interpreting neural networks is a hot research topic, and a paper advancing knowledge in this area is certainly welcome. The paper is well presented (with a small typo in the definition of S_ker(x,x)). In the experiments, it will be interesting to further investigate how the local elastic property changes with large batch size in that large batch size may encourage more diversity of the examples in a batch. Furthermore, it will be even more interesting to explore how these similarities can improve the performance of a simple k-nearest neighbor classifier.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SylBdSQ6tH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper contributes to the understanding of neural networks and provides a new clustering technique:\n  1) The paper introduces the interesting notion of local elasticity which considers the relative variation in output values for two different inputs before and after an SGD-style update;\n  2) The derived similarity metric between input samples (obtained by as SGD unfolds) can be used for clustering and is amenable to a kernelized formulation;\n  3) Empirical measurements on visual classification tasks show that the new similarity metric can offer a better clustering performance than PCA + K-means.\n\nI found the paper very interesting but the writing appeared somewhat unclear at times. I believe that some rewriting is needed for the authors to argue that the newly introduced elasticity metric provides a significantly new understanding of neural networks. In particular, I did not find the argumentation around explaining generalization to be very convincing or clear.\n\nThe kernelized formulation of the elasticity metric seems compelling and I found that turning the insights developed by the theoretical section of the paper into an actionable algorithm for clustering was a nice contribution.\n\nUnfortunately, the empirical results did not really convince me that the resulting clustering algorithm really improves on the SOTA in clustering as only relatively weak baselines were considered.\n\nI believe that considering more solid baselines for the clustering experiments would help.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BklTr756KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n[Summary]\nThis paper proposes and studies the “local elasticity”, a quantitative measure for the ability of neural networks to only locally change its prediction (around x) after a stochastic gradient step at x. The paper verifies experimentally that nonlinear neural nets are locally elastic through showing that an elasticity-motivated similarity score can perform clustering well.\n\n[Pros]\nThe notion of local elasticity is interesting and has the potential of opening up lots of further directions. The way I understand it is to relate to memorization (as the authors have indeed discussed) --- I think “local elasticity” can be viewed as some sort of “local memorization ability”, in that the NN is able to change its prediction only in a small neighborhood of x---without affecting predictions at other remote x’s---after one SGD step on x. Conceptually this is something not covered by the existing narratives in deep learning theory, yet the phenomenon itself is quite convincing and could provide a new perspective into lots of things.\n\n[Cons]\nIt feels like the experimental results in the present paper is a rather indirect evidence for the local elasticity -- that the similarity score coming from the elasticity works well for a downstream clustering task. Could there be some more direct evidence about the local elasticity? How would the elasticity compare on different architectures? In the present form the experiments perhaps at most says that the similarity score makes sense, not yet that a fully quantitative characterization of the local elasticity.\n\nI’m also a little bit concerned about the fairness of the clustering experiment, in that the elasticity-motivated clustering algorithm utilizes an auxiliary dataset whereas simple baselines such as K-means and PCA K-means are not able to use that. Is there a way of modifying the K-means and PCA K-means so that they can also use this auxiliary dataset while still giving a sensible algorithm for the primary 2-class clustering task?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new phenomenon referred to as the "local elasticity of neural networks". The main argument is that the SGD update for nonlinear network at a local input x does not change the predictions at a different input x' (see Fig. 2). This is then connected to similarity using nearest-neighbor and kernel methods. An algorithm is also presented.

The reviewers find the paper intriguing and believe that this could be interesting for the community. After the rebuttal period, one of the reviewers increased their score.

I do agree with the view of the reviewers, although I found that the paper's presentation can be improved. For example, Fig. 1 is not clear at all, and the related work section basically talks about many existing works but does not discuss why they are related to this work and how this work add value to this existing works. I found Fig. 2 very clear and informative. I hope that the authors could further improve the presentation. This should help in improving the impact of the paper.

With the reviewers score, I recommend to accept this paper, and encourage the authors to improve the presentation of the paper.
Decision: Accept (Poster)