Is deeper better? It depends on locality of relevant features
Authors: Takashi Mori
Masahito Ueda
Venue:  (2021)
Keywords: deep learning
generalization
overparameterization

Abstract: It has been recognized that a heavily overparameterized artificial neural network exhibits surprisingly good generalization performance in various machine-learning tasks. Recent theoretical studies have made attempts to unveil the mystery of the overparameterization. In most of those previous works, the overparameterization is achieved by increasing the width of the network, while the effect of increasing the depth has been less well understood. In this work, we investigate the effect of increasing the depth within an overparameterized regime. To gain an insight into the advantage of depth, we introduce local and global labels as abstract but simple classification rules. It turns out that the locality of the relevant feature for a given classification rule plays an important role; our experimental results suggest that deeper is better for local labels, whereas shallower is better for global labels. We also compare the results of finite networks with those of the neural tangent kernel (NTK), which is equivalent to an infinitely wide network with a proper initialization and an infinitesimal learning rate. It is shown that the NTK does not correctly capture the depth dependence of the generalization performance, which indicates the importance of the feature learning, rather than the lazy learning.

Under review as a conference paper at ICLR 2021
IS DEEPER BETTER? RELEVANT FEATURES
IT DEPENDS ON LOCALITY OF
Anonymous authors Paper under double-blind review
ABSTRACT
It has been recognized that heavily overparameterized artificial neural net- work exhibits surprisingly good generalization performance in various machine- learning tasks. Recent theoretical studies have made attempts to unveil the mys- tery of the overparameterivation. In most of those previous works, the overparam- eterization is achieved by increasing the width of the network, while the effect of increasing the depth has remained less well understood. In this work, we inves- tigate the effect of increasing the depth within an overparameterized regime. To gain an insight into the advantage of depth, we introduce local and global labels as abstract but simple classification rules. It turns out that the locality of the relevant feature for a given classification rule plays key role; our experimental results suggest that deeper better for local labels, whereas shallower is better for global labels. We also compare the results of finite networks with those of the neural tan- gent kernel (NTK), which is equivalent to an infinitely wide network with a proper initialization and an infinitesimal learning rate. It is shown that the NTK does not correctly capture the depth dependence of the generalization performance, which indicates the importance of the feature learning, rather than the lazy learning.
INTRODUCTION
Deep learning has achieved unparalleled success in various tasks of artificial intelligence such as im- age classification (Krizhevsky et al. 2012 LeCun et all 2015) and speech recognition (Hinton al., 2012). Remarkably, in modern machine learning applications, impressive generalization perfor- mance has been observed in an overparameterized regime, in which the number of parameters in the network is much larger than that of training data samples. Contrary to what we learn in classi- cal learning theory, an overparameterized network fits random labels and yet generalizes very well without serious overfitting (Zhang et all 2017). We do not have general theory that explains why deep learning works so well.
Recently, the learning dynamics and the generalization power of heavily overparameterized wide neural networks have extensively been studied. It has been reported that training of an overparame- terized network easily achieves
training error without getting stuck in local minima of the loss landscape (Zhang et al_ 2017: Baity-Jesi et al.- 2018). Mathematically rigorous results have also been obtained (Allen-Zhu et al_ 2019 Du et al 2019). From a different perspective, theory of the neural tangent kernel (NTK) has been developed as a new tool to investigate an overparameterized network with infinite width (Jacot et al. 2018: & Arora et al. 2019), which simply explains the reason why sufficiently wide neural network can achieve a global minimum of the training loss.
As for generalization, "double-descem" phenomenon has attracted much attention (Spigler al. 2019: Belkin et al. (2019). The standard bias- viasivvri tradeoff scenario predicts a U-shaped curve of the test error (Geman et al. 1992); however, one finds the double-descen curve, which implies that an increased model capacity beyond the interpolation threshold results in improved perfor- mance. This finding triggered detailed studies on the behavior of the bias and variance an over- parameterized regime (Neal et al.. 2019 D' Ascoli et al. 2020). The double-descent phenomenon not explained by traditional complexity measures such as the Vapmik-Chervonenke dimension and the Rademacher complexity (Mohri et all 2018), and hence seeks for new complexity mea- sures of deep neural networks that can prove better generalization bounds (Dziugaite & Rov. 2017 Neyshabur et al. 2017 2019. Arora et all 2018 Nagarajan & Kolter, 2017: Pérez et al. 2019).

---

Under review as a conference paper at ICLR 2021
These theoretical efforts mainly focus on the effect of increasing the network width, but benefits of the network depth remain unclear. is known that expressivity of a deep neural network grows ex- ponentially with the depth rather than the width (Poole et all (016). See also Bianchini & Scarselli (2014); Montúfar et al. (2014). However, it is unclear whether exponential expressivity does lead to better generalization (Ba & Caruana, 2014 |Bekkrr et all 2020). It is also nontrivial whether typical problems encountered in practice require such high expressivity. Although some works (Eldan & Shamin, 2016 Safran & Shamin, 2017) have shown that there exist simple and nat- ural functions that are efficiently approximated by a network with two hidden layers but not by a network with one hidden layer, recent work (Malach & Sawaat-S 2019) has demonstrated that a deep network can only learn functions that are well approximated by a shallow network by using a gradient-based optimization algorithm, which indicates that benefits of the depth are not due to high expressivity of deep networks. Some other recent works have reported no clear advantage of the depth in an overparameterized regime (Geiger et al. 201
To gain insight into the advantage of the depth, in the present paper, we report our experimental study on the depth and width dependences of generalization in abstract but simple, well-controlled classification tasks with fully connected neural networks. We introduce local labels and global labels, both of which give simple mappings between inputs and output class labels. By "local", mean that the label is determined only by few components of the input vector. On the other hand, a global label is determined by a global feature that is expressed as a sum of local quantities, and hence all components of input contribute the global label. Our experiments show strong of the generalization error for those simple input-output mappings. In particular, we find that deeper is better for local labels, while shallower is better for global labels. This result implies that the depth is not always advantageous, but the locality of relevant features would give us a clue for understanding the advantage the depth brings about.
We also compare the generalization performance of trained network of finite width with that of the kernel method with the NTK. The latter corresponds to the unfinite-width limit of fully connected network with an appropriate initialization and an infinitesimal learning rate (Jacot et all 2018), which is referred to as the NTK limit. In the NTK limit, the network parameters stay close to their initial values during training. which is called the lazy learning (Chizat et all 2019). It is known that a wide but finite network can still be in the lazy learning regime for sufficiently small learning rates ( & Telgarsky 2019 Chen et all 2019). We however find that even if the width increases, in some cases the generalization error at an optimal learning rate does not converge to the NTK limit. In such case, a finite-width network shows much better generalization compared with the kernel learning with the NTK. This finding indicates the importance of the feature learning, in which network parameters change to learn relevant features.
2 SETTING
We consider classification task with a training dataset D (ec())g(()) μ 2,2...., N). where _(()) E I is an input data and y(e) {1, 2...., K} is its label. In this work, we consider the binary classification, K = 2, unless otherwise stated.
2.1 DATASET
Each input x (I1, .2,..., x..) is d-dimensional vector taken from i.i.d. Gaussian random variables of zero mean and unit variance, where a" is the transpose of vector a. For each input x, we assign label y according one of the following rules.
k-LOCAL LABEL
We randomly fix integers (i1, i2, d with 1 < i < .... < S d. In the "k-local" label, the relevant feature is given by the product of the k components of an input x, that is, the label y is determined by
1 if Ti. 2 0;
y =
2 otherwise.
(1)
2

---

Under review as a conference paper at ICLR 2021
This label is said be local in the sense that is completely determined by just the &o components of an input = For fully connected networks considered this paper, without loss of generality, we choose i1 1, 2... in k because of the permutation symmetry with respect to indices of input vectors.
k-GLOBAL LABEL
We again fix i < ig ... < is S d. Let us define
d M
Σ 2
Tjth Eith T.fiis
(2)
where the convention Zdzi is used. The k-global label y for x is defined by
1
2 0:
(3)
2
otherwise.
The relevant feature M for this label is given by uniform of the product of components of the input vector. Every component of x contributes to this "k-global"" label, contrast to the kllocal label with & < d.
2.2 NETWORK ARCHITECTURE
In the present work, we consider fully connected feedforward neural networks with T, hidden layers of width И. We call L and the depth and the width of the network, respectively. The output of the network f(x) for input vector r E IRd is determined as follows:
(1x (L++)) ( + b(L+1);
20) = ip (w())(111) + bb) for 1, ..., ,,
20)
where x(x) max 0} is the component-wer ReLU activation function, 200) is the output of the Ith layer, and
k for ( = L + 1;
g HxH for 2,3, ..... L; 80 k for + +1;
(
(5)
R for = 1.2.....
Hxd for 1,
the weights and the biases, respectively. Let us denote by w the all the weights and biases in the network. We focus on an overparameterized regime, where the number of network parameters (the number of components of w) exceeds N, the number of training data points.
2.3 SUPERVISED LEARNING
The network parameters adjusted to correctly classify the training data. It done by minimiz- ing the softmax cross-entropy loss I-ww) given by
N Σ & (I(al)))
e(f(x),)) = -In ef((z)
L(w)=
Σ cfi()) = (x) + In Σ f.))
N
(6)
where the ith component of ((x is denoted by f((x).
The training of the network is done by the stochastic gradient descent (SGD) with learning rate and the mini-batch size B. That is, for each mini-batch D with [3] B, the network parameter
'Tee locality here does not necessarily imply that & points i i2, i are spatially close to each other. Such usage of the terminology "k-local" has been found (but k-global is also called "k-local") in the field of quantum information (Kempe al] 2006).
3

---

Under review as a conference paper at ICLR 2021
wy at time t is updated
Lø(w) 1 Σ e (Holl))) KEB
Σ
#+1 wa vwLD).
Throughout the paper, we fix B 50. Meanwhile, we optimize ') > 0 before training (we ex- plain the detail later). Biases are initialized to be zero, and weights are initialized using the Glorot initialization (Glorot & Bengio, 2010
The trained network classifies an input zn to the class g(m) = arg max KI) f((x(1)). Let us then define the training error as
E Etaain
Σ (1 kyin)
(8)
that is the miss-classiffcation rate for the training data D. We train network until Eraain O is achieved, i.e., all the training data samples are correctly classified, which is possible in an overparameterizee regime.
For training dataset D, we first perform the 10-fold cross validation to optimize the learning rate ? under the Bayesian optimization method (Snoek all 2012). and then perform the training via the SGD by using the full training dataset. In the optimization of we try to minimize the miss- classification ratio for the validation data.
The generalization performance of a trained network is measured by computing the test error. We prepare the test data Deest {(*"()) y y/(n)) 1t = 1, 2......, data D. The test error Eest is defined the miss clas-slassiiicattin ratio for D Pestt i.C.,
., Ntest) independently from the training
Nicat
Ejest
Σ
(1
Ntest
p=1
where g'(m)) arg max, fi(x'(a) is the prediction of our trained network. In our experiment dis- cussed in Sec. 3 we fix Niest 105.
2.4 NEURAL TANGENT KERNEL
Following et al (201g) and Cao & Gu 2019). let us consider network of depth L and width
H whose biases {b()} and weights (w(") are randomly initialized as b(") 366 with 5(0) (1) 1), and wij 22/nt-1w!
(I) with w (N 1) for every I, where is the number of neurons in the lth layer, i.e., 70 d,
=(t)
nr. = H. Let us denote by w the set of all the scaled weights (mx(0) and biases (8(0). The network output is written as f(x w). When the network sufficiently wide and the learning rate sufficiently small, the network parameters i stay close to their randomly initialized values during training, and hence f(z u) is approximated by a linear function of wo: f(x, w) = f(z, wp) + V (x, ( (w wp. As a result, the minimization of the mean-squared eтror LMSE = (1/N) In=Iff((m)) w) 5(m)? where g(P) E K the one-hot representation of the label (M)), is equivalent to the kernel regression with the NTK (1) (x, x') (i,j = 1, 1,,...., K) defined as
n2
(1) 1/ (x. x') = lim Es [[V (V 10000
(10)
where E, denotes the average over random initializations of t (acot et all 2018). The parameter 3 controls the impact of bias terms, and we set 8 = 0.1 in our numerical experiment following Jacot et all (2018). By using the ReLU activation function, we can give an explicit expression of the NTK that is suited for numerical calculations. Such formulas are given in Appendix(A)
We also tried the He initialization (He et al. 2015) and confirmed that results are similar to the ones ab- tained by the Glorot mitiallizatin, in particular when input vectors are normalized || 1.
4

---

Under review as a conference paper at ICLR 2021
(a) 1-local
(b) 1-global
0.4
depth width 6ol
13
degth 1, sddth 550
2010
0.35
depin 1, withh
150
depli willh 500
degili 7, will 500
0.3
lioee perceptrnn (dep1:: 01
0.3
lineer pentaplnng (dep 0)
NTS. depli
NTK. depil
tost antr
0.25
degtl
0.25
depili
0.2
0.2
0.15
0.15
0.1
0.1
3
0.05
0.05
0
2000
4000
6000
8000
10000
0
2000
4000
6000
8000
10000
N
Figure 1: Test error against the number of training data samples N for several network architectures specified by the depth and width for (a) the 1-local label and (b) the 1-global label. Test errors calculated by the NTK of depth and are also plotted. Error bars are smaller than the symbols.
It is shown that the NTK takes the form 0 (2,x') x²) mean caun--qareed error with an infinitesimal weight decay yields the output function
82., ((L) (z, z²), and the minimization of the
NTK (z)
Σ p,V=1
e (x, x(0) (K
jv g(y)
(11)
where K-1 is the inverse matrix of the Gram matrix KE (z1)), x( An input data is classified to arg e (K) JNTK(()) (z).
3 EXPERIMENTAL RESULTS
We now present our experimental results, For each data point, the training dataset D is fixed and we optimize the learning rate 1j via the 10-fold cross validation with the Bayesian optimization method (we used the package provided in Nogueira (2014)). We used the optimized 17 to train our network. At every 50 epochs we compute the training error Etrain, and we stop the training if Etrain O. For the fixed dataset 'D and the optimized learning rate 1). the training is performed 10 times and calculate the average and the standard deviation of test errors Erest-
We present experimental results for the softmax cross-entropy loss in this section and for the mean- square loss in Appendix [D Our main result holds for both cases, although the choice of the loss function quantitatively affects the generalization performance.
3.1 1-LOCAL AND 1-GLOBAL LABELS
In the I-local and 1-global labels, the relevant feature is linear function of the input vector. There- fore, in principle, even a linear network can correctly classify the data. Figure [ shows the gener- alization errors in nonlinear networks of the varying depth and width as well as those in the linear perceptron (the network of zero depth). The input dimension set to be d 1000. We also plotted test eтrors calculated by the NTK, but we postpone the discussion about the NTK until Sec. 3.3
Figure D shows that in both l-local and 1-global labels, the test error decreases with the network width, and a shallower network (T. 1) shows better generalization compared with deeper one (T. (T=77) 7). 7). The linear perceptron shows the best generalization performance, which natural because it is the simplest network that is capable of learning the relevant feature associated with the 1-local or 1-global label. Remarkably, test errors of nonlinear networks (L = and L = 7) are not so large compared with those of the linear perceptron, although nonlinear networks are much more complex than the linear perceptron.
For given network architecture, do not any important difference between the results for I-oocal and 1-global labels, which would be explained by the fact that these labels are transformed to each other via the Fourier transformation of input vectors.
5

---

Under review as a conference paper at ICLR 2021
(a) 2-local
(b) 3-local
0.5
0.4
0.4
depth L. witht 500 depil: widl 2000
0.3
wotth
0.3
NIS. desth NI depth
0.2
0.2
depth Midh
depti 1. wodth 2000 depta Mi2t0 100
0.1
depth
N.K,
NEK, depth
5000
10000
15000
20000
25000
30000
8000
12000
16000
20000
24000
(c) 2-global
(d) 3-global
0.5
depth wolth 500
0.5
with 100
0.4
depth wndth 500
0.4
NIS. depth 1
depth
tast
0.2
depti wicth 1030
deglt wiah 2000
0.1
0.1
deg 2. widlh 100
NTK. depil
NTR: K. depth?
5000
10000
15000
20000
25000
30000
5000
10000
15000
20000
30000
N
Figure 2: Test error against the number of training data samples N for several network architectures specified by the depth and the width for (a) the 2-local label, (b) the 3-cacal label, (c) 2-global label, and (d) 3-global label. Error bars indicate the standard deviation of the test error for 10 iterations of the network initialization and the training. Test errors calculated by the NTK of the depth of I and are also plotted.
3.2 OPPOSITE DEPTH DEPENDENCES FOR k-LOCAL AND &-GLOBAL LABELS WITH 2
For A: 2 2, it turns out that experimental results show opposite depth dependences for k-local and k-global labels. Let us first consider k-local labels with k > 2. Figure P (a) and (b) show test errors for varying N in various networks for the 2-local and the 3-local labels, respectively. The input dimension d is set to be d = 500 in the 2-local label and d 100 in the 3-local label. We see that the test error strongly depends on the network depth. The deeper network (L = 7) generalizes better than the shallower one (L 1). It should be noted that for d 500, the network of L- and larger than that of trainable parameters (= 105) in the network of L. and H 100. Nevertheless, the latter outperforms the former in the 2-local label as well as in the 3-local label with large N, which implies that inereasing the number of trainable parameters does necessarily imply better generalization. In k-local labels with & 2 2, the network depth is more strongly correlated to generalization compared with the network width.
2000 contains about 10 trainable parameters, the number of which is much
From Fig. 2 (b), it is obvious that the network of L 7 and H = 100 fails to learn the 3-local label for small N. We also see that error bars of the test error are large in the network of L 7 and = 100. The error bar represents the variance due to initialization and training. By increasing the network width H, both variances and test errors decrease. This result is consistent with the recent observation in the lazy regime that increasing the network width results in better generalization because it reduces the variance due to initialization (D' Ascoli et all 2020).
Next, we consider k-global labels with & = 2 and 3. The input dimension d is set as d 100 for the 2-global label and = 40 for the 3-global label. We plot test errors against (c) the 2- 2-global label and (d) the 3-global label. Again shallow networks (L = 1) outperform deep ones (L- = 7), contrary to the results for k-local labels. For I 7, we also find strong width dependences; the test emrr of a wider network more quickly
Fig. 2 for find strong depth dependences, but now

---

Under review as a conference paper at ICLR 2021
0.38
2-local
0.36
2-global
0.34
0.32
tast anu
0.3
0.28
0.26
0.24
0.22
depth
Figure 3: Depth dependence of the test error for N = 10 training samples with 2-local and 2-global labels. The dimension of input vectors set to be d 500 the 2-local label and d = 100 the 2-global label. The network width is fixed to be 500. An error bar indicates the standard deviation over 10 iterations of the training using the same dataset.
decreases with N. In particular, in the 3-global label, an improvement of the generalization with N is minor for L = 7 and H = 100. An increase in the width makes decrease in the test error with N much faster [sce the result for L 7 and H 500 in (d)).
To see more details of the effect of depth, we also plot the depth dependence of the test error for fixed training data samples. We prepare N 10000 training data samples for the 2-local and 2- global labels, respectively. The input dimension is 500 for the 2-local label and d = 100 for the 2-global label. By using the prepared training data samples. networks of the depth L and the width H 500 are trained up to L 10. The test errors of trained networks are shown in Fig. 3 The test error of the 2-local label decreases with increasing L. whereas the test error of the 2-global label increases with L. Thus, Fig. 3 clearly shows the opposite depth dependences for local and global labels.
3.3 COMPARISON BETWEEN FINITE NETWORKS AND NTKs
In Figs. anddn 2 test errors calculated by using the NTK are also plotted. the case of (Fig. 1 and the 2-global label [Fig. (c)), the generalization performance of the NTK is comparable to or lower than that of finite networks.
A crucial difference is seen in the case of the k-local label with k: = 2 and 3 and the 3-global label. In Fig. 2 (a) and (b), we see that the NTK almost completely fails to classify the data, although finite networks
successful. In the case of the 3-global label, the NTK of depth L = 7 correctly classifies the data, while the NTK of depth L = fails [see Fig. (d)). In those cases, the test error calculated by finite network does not seem to converge that obtained by the NTK as the network width increases.
The NTK has been proposed theoretical tool investigate the infinite-width limit. However, it should be kept in mind that the learning rate has to be sufficiently small to achieve the NTK limit (Jacot et al. 2018: Arora all 2019). The discrepancy between wide network and the NTK in Fig. stems from the strong learning- -rati dependence of the generalization performance. In our experiment, the learning rate has been optimized by performing a 10-fold eross validation. the optimized learning rate is not small enough for each width, the trained network may not be described by the NTK even the infinite-width limit.
In Fig. 4 (a), we plot the learning- rate dependence of the test error for the 2-laal label and the 2-global label in the network of the depth learning-rate dependence in the case of the 2-local label in contrast the case of the 2-global label. and = 7 in
and the width // = 2000. We observe a sharp
In Fig. (b), we compare the learning-rate dependences of the test error for L the case of the 3-global label (H 2000 in both cases). We see that the learning rate dependence for L = is much stronger than that for L = 7, which consistent with the fact that the NTK fails only for I = 1. It should be noted that Fig. 4 (b) shows that the deep network (J. outperforms
7

---

Under review as a conference paper at ICLR 2021
(b)
0.45
NTK (2-Toal)
NTK, depth 1
0.4
0.45
2/occal
depth wieth 2000
2-globel
-
0.4
depta 7, width 2000 -
tost antr
0.3
0.35
Awazt
NIK, depti 7
0.2
0.15
0.25
(2-0)
0.1
0.2
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
leaminng rste
learning rsle
Figure 4: Learning-rate dependence of the test error. (a) Numerical results for the 2-local and 2- global labels in the network with the depth of and the width of 2000. (b) Numerical results for the 3-global label in the networks with the depth of and 7 (the network width is set at 2000 for both cases). The dotted lines show the test error calculated by the NTK. Each data is plotted up to the maximum learning rate beyond which the zero training error is not achieved within 2500 epochs (in some cases training fails due divergence of network parameters during the training). Error bars indicate the standard deviation over 10 iterations of the training.
the shallow one (T. 1) in the regime of small learning rates, while the shallow one performs better than the deep one at their optimal learning rates.
Figure 4 also shows that the test error for a sufficiently small learning rate approaches the one obtained by the corresponding NTK. Therefore, the regime of small learning rates is identified as a lazy learning regime, while larger learning rates correspond important message of Fig. 4is that we should investigate the feature learning regime, rather than the lazy learning regime, to correctly understand the effect of the depth on generalization.
feature learning regime. An
4 DISCUSSION ON THE OBSERVED DEPTH DEPENDENCE
is crucial for our problem to understand why deeper (shallower) is better for local (global) labels. As a possible mechanism, we suggest that local features can naturally be detected with the help of the chaotic signal propagation through a deep network (Poole et al. (016)) due to multiplicative growth of small perturbation on an input across each layer.
An important distinction between the k-local label and the k-global label with < d lies in their stability against perturbations. We can typically change the k-local label of an input x E I2 by moving x to ã = x + z with || O(1), where E IRd is perturbation and || 1/1 stands for the Manhattan distance (the L distance). On the other hand, stronger perturbation ||=||| Ö(Vd) is typically needed to change the k-global label.
A recent study by De Palma et al. (011 shows that randomly initialized pre-trained wide neural network generates a label such that a perturbation with ||=||| Ö(vd) is typically needed to change i indicating that Ö(vd) is a natural scale of resolution for pre-trained random neural network. Compared with it, learning the k-local label requires finer resolution: two close inputs x and z' with || 2'111 O(1) should result in distinct outputs fax and f(z') when and z' have different labels. A deep neural network can naturally implement such a situation via chaotic signal propagation, and hence the depth is beneficial for learning local features. On the other hand, the k-global label is as stable as a typical label generated by a pre-trained network, and the chaoticity is not needed: two close inputs x and x' with || - æ'lla & Ö(vd) typically share the same label and therefore the outputs fx) and f(x') should also be close to each other. In this case, the chaoticity may bring about unnecessary high resolution and therefore he rather disadvantageous: shallower network is better for the k-global label. This is a likely explanation of the result obtained in Sec. [3.2
Thii statement has heen proved for binary inputs with the Hamming distance, but we expect that it also holds for continuous inputs with the Manhattan distance.
8

---

Under review as a conference paper at ICLR 2021
Whereas the chaotic signal propagation originally discussed to explain high expressivity of deep networks (Poole et al. 2016), we emphasize that the benefit of depth in local labels is not due to high expressivity since learning the k-local label with ht < d does not require high expressivity Nevertheless, the chaoticity of deep neural networks may play a pivotal role here.
To support the above intuitive argument, experimentally show in Appendix B that deeper network has a tendency towards learning more local features even in training random labels. That is, even for learning completely structureless dataset, learned features in a deep network tend to be more local compared with those in a shallow one, which is possibly due to chaoticity of deep networks and potentially explains the result of Sec. 3.2
CONCLUSION
In this work, we have studied the effect of increasing the depth in classification tasks. Instead of using real data, we have employed an abstract setting with random inputs and simple classification rules because such a simple setup helps us to understand under what situations deeper networks perform better worse. We find that the locality of relevant features for given classification rule plays a key role. In Sec. A we have proposed that the chaotic signal propagation in deep networks gives possible mechanism to explain why deeper is better in local labels.
is also an interesting observation that shallower networks do better than deeper ones for the k- global label, indicating that the depth is not necessarily beneficial. Although our dataset with the k-local or k-global label is artificial, there are some realistic examples in which k-global label is relevant, i.e., thermodynamic systems in physics. Thermodynamie variables in physics are usually expressed in the form of Eq. (2). i.e., a sum of local quantities over the entire volume of the system, and hence are regarded global features. Our result therefore implies that shallower network is more suitable for machine learning of thermodynamin systems. In Appendix C we demonstrate that it is indeed the case in a classification problem of spin confituraiions of the Ising model, which is a quintessential model of ferromagnets Nishimori & Ortiz (201 1). In typical image classification tasks, local features would be important and deeper networks do better, but we expect that there are some real datasets in which global features are more important, such as an example discussed in Appendix C
We believe that our finding is relevant to real datasets, including the physics models discussed above. is an important future problem to understand how to apply our findings to machine learning real datasets.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, 2019.
Sanjeev Arora, Rong Ge. Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, 2018.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On Exact Computation with an Infinitely Wide Neural Net. In Neural Information Processing Systems, 2019.
Jimmy Ba and Rich Caruana. Do deep networks really need to be deep? In Advances in Neural Information Processing Systems, 2014.
Marco Baity-Jesi, Levent Sagun, Mario Geiger. Stefano Spigler, Gérard Ben Arous, Chiara Cam- marota, Yann LeCun, Matthieu Wyart, and Giulio Biroli. Comparing Dynamics: : Deep Neural Networks versus Glassy Systems. In International Conference on Machine Learning, 2018
Simon Becker, Yao Zhang, and Alpha A Lee. Geometry of Energy Landscapes and the Optimizabil- ity of Deep Neural Networks. Physical Review Letters, 124(10):108301, 2020.
*It is confirmed that small network with one hidden layer of the width of about 10-100 is enough to express the 2-local label and the 3-local label almost perfectly.
9

---

Under review as a conference paper at ICLR 2021
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical of Sciences of the United States of America, 16632):15849-15855 2019.
trade-off. Proceedings of the National Academy
Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: com- parison between shallow and deep architectures. IEEE Transactions Neural Networks and Learning Systems, 25(8):1553-1565, 2014.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances Neural Information Processing Systems, 2019.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much ovamppaaraniiiiiiiaionnn is suffi- cient to learn deep ReLU networks? arXiv preprint arXiv: 2019.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Program- ming. In Neural Information Processing Systems, 2019.
Stéphane Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double Trouble in Double Descent: Bias and Variance(s) in the Lazy Regime. arXiv preprint arXir:2003.01054,20000 2020.
Giacomo De Palma, Bobak Toussi Kiani, and Seth Lloyd. Random deep neural networks are biased towards simple functions. Advances in Neural Information Processing Systems, 2019.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, 2019.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Uncertainty in Artificial Intelligence, 2017.
Ronen Eldan and Ohad Shamir. The Power Depth for Feedforward Neural Networks. In Pro- ceedings of Machine Learning Research, 2016.
Mario Geiger, Stefano Spigler, Stéphane Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart. Jamming transition paradigm to understand the loss landscape of deep neural networks. Physical Review E, 100(():012115, 2019a.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training deep neural networks. arXiv preprint arXiv: (rXiv:/906.0800 1906.08034, 2019b.
Stuart Geman, Flie Bienenstock, and René Doursat. Neural Networks and the Bias/Variance Dilemma. Neural Computation, 4(1):1-58, 1992.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of Machine Learning Research, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE International Conference on Computer Vision, 2015.
Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, and Others. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal processing magazine, 29(6):82-97, 2012.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbi- trarily small test error with shallow ReLU networks. arXiv preprint arXiv: 12292, 2019.
Julia Kempe, Alexii Kitaev, and Oded Regev. The complexity of the local Hamiltonian problem. SIAM Journal on Computing, 3570) 2006.
10

---

Under review as a conference paper at ICLR 2021
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521 2015.
Kaifeng Lyu and Jian Li. Gradient Descent Maximizes the Margin of Homogeneous Neural Net- works. In International Conference on Learning Representattonss 2020.
Eran Malach and Shai Shalev-Shwartz. Is Deeper Better only when Shallow is Good? In Advances in Neural Information Processing Systems, 2019.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems, 2014.
Vaishnavh Nagarajan and Zico Kolter. Generalization in Deep Networks: The Role of Distance from Initialization. In Advances in Neural Information Processing Systems, 2017.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and loannis Mitliagkas. A Modern Take on the Bias-Variance Tradeoff in Neural Net- works. In Workshop on Identifying and Understanding Deep Learning Phenomena, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nathan Srebro. Exploring Gener- alization in Deep Learning. In Advances in Neural Information Processing Systems, 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parameerizztioo in generalization of neural networks. In International Conference on Learning Representations, 2019.
Hidetoshi Nishimori and Gerardo Ortiz. Elements of Phase Transitions and Critical Phenomena.
Oxford University Press, 2011.
Atsushi Nitanda, Geoffrey Chinot, and Taiji Suzuki. Gradient Descent Learn Less Over-parameterizeed Two-layer Neural Networks on Classification Problems. arXiv preprint arXiv:1905. 09870,,00000000
Fernando Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014. URL htttps://githuu..om fmfn/ ian0pt imi inttiptiiiiiiiii zation
Guillermo Valle Pérez, Ard A Louis, and Chico Q Camargo. Deep learning generalizes because the parameter-funnttin map biased towards simple functions. In International Conference on Learning Representations, 2019.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Expo- nential expressivity in deep neural networks through transient chaos. In Advances in Neural Information Processing Systems, 2016.
Itay Safran and Ohad Shamir. wipth tradeoffs in approximating natural functions with neural networks. In International Conference on Machine Learning, 2017.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical Bayesian Optimization of Machine Learning Algorithms. In Advances in Neural Information Processing Systems, 2012.
Stefano Spigler, Mario Geiger, Stéphane D' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under- To over- over- parametrization affects generalization in deep learning. Journal of Physics A: Mathematical and Theoretical, 52(47):474001, 2019.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding Deep Learning Requires Rethinking of Generalization. In International Conference on Learning Representations, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine Learning, 109(3):467-422,202) 2020.

---

Under review as a conference paper at ICLR 2021
A EXPLICIT EXPRESSION OF THE NTK
We consider a network whose biases {6(0} and weights {wlO} are randomly initialized as 6,0) 36.") with 6 (O, 1) and w!! / 2/ 2/n1-1 with wiy (O, 1) for every where my is the number of neurons in the Ith layer, i.e., Rog = d, n1 limit H the pre-activation (()) = w 2(-1) + at every hidden layer tends to an i.i.d. Gaussian process with covariance [[-11) I2 x Rd
n2
nu H. In the infinite-
- lR that is defined recursively as
x TTx x'
Σ (x,
+ ge:
A0 E11-1)((;
-0-1)
(12)
1 (2', (d),z)
(z',)(
Σ (2,xx' = 2 (a.0)> ( [p(() +
for = 1.2..... L. We also define
(x, 2 (u. (p(U)
(13)
where و is the derivative of sp, The NTK is then expressed as O (x, x') = (,)))=),,0000 (x,,0(()2,, where
(1,
Σ (I,
x')
II
(14)
P=1
The derivation of this formula is given by |Arora et al. (2019)
Using the ReLU activation function (p()) max(u, 0}, we can further calculate 2 (xr, (xr, x¹) and (z, obtaining
(0 (x, x')
det A
20 x')
π 2
+ arctan
Dd- Id (x,
) + (15)
det AT)
and
1
2
Σ(11) (x,-) (xr,aa)))
Vdlt. A() )}
(x, x')
1 arctan
(16)
For r = x', we obtain (x, x) = [00) + 1
|0.12/d + (1 + 1).8. By solving eqs. (5)
and (6 iteratively, the NTK in Eq. 14) is obtained
B LOCAL STABILITY EXPERIMENT
Rather than considering general perturbations, here restrict ourselves to local perturbations, (ve()) where > 0 is the strength of perturbation and e is the unit vector in ith direction (i 1,2.....df d). For each sample (²(4) in the test data, if the network does not change its predicted label under any local perturbation for a given v, i.e., arg ]aj f (2/(w)) = arg max (x/(H) + [ } for any e [d] and a {=1}. we say that the network is v-stable at x'(n), We define (v) as s(a) (u) if the network is v-stable at x((M) and s g(m) 0 otherwise. The local
stability of the network is measured by a quantity
Niws
s(v)
((1) (v).
(17)
Neost
'When 3 = 0 (no bias), the equations are further simplified; x = |= cos l( and 5000 = g(6-1)
where ((0) E [0, π] is the angle between x and x', and (11)) is iteratively determined by
cos ( 1
sin 1(l + (ar g(l-1)) cos cos pll-1)]
π
12

---

Under review as a conference paper at ICLR 2021
0.8
depti I, width
depth 7, witth 500
0.7
2-local 2-globel
0.5
0.4
0.3
0.1
0
Figure 5: Local stability s(v) for shallow network (L = 500), deep network 7, H = 500), the 2-local label, and the 2-global label. The networks are trained on training dataset with randomized labels. We can see that s(v) for a deep network is smaller than that for a shallow one, which implies that deeper network has tendency to learning more local features even if the same dataset is given.
The e-stability can be defined similarly for the k-llcaal and k-global labels: a given label is said to be u-stable ((()) if the label does not change under any local perturbation with strength v. We can also define s()) for k-local and k-global labels. In our setting, v = O(1) is sufficient to change the Ö(Vd) is needed to alter the k-global label.
k-local label, whereas typically
500) and deep (I. 7 and H 500) networks trained on N = 10 datasets with random labels by using the SGD of the learning rate 1 0.1 and the minibatch size
We measure s(v) for shallow (I. = and
50. The dimension of input vectors is fixed as = 100. Fig. 5 s(v) is plotted for the shallow and deep networks well as for the 2-local and 2-global labels. We observe that s(v) the deep network is smaller than that in the shallow one. Moreover, s(v) in shallow network is close that of the 2-global label. These experimental results indicate that for learning a completely structureless dataset, learned features in a deep network tend to be more local compared with those in shallow one.
C CLASSIFICATION OF ISING SPIN CONFIGURATIONS
In the main text, we have considered rather artificial datasets (i.i.d. random Gaussian inputs and k-local or k-global label). Our main result that local (global) features are more efficiently learned by using deeper (shallower) networks. Here, demonstrate that this result is relevant to realistic dataset in physics, i.c., a dataset constructed from snapshots of Ising spin configurations.
The Ising model has been studied in physics nets (Nishimori & Ortiz, 20. At each site = 1,2..... d, a binary spin variable a; E (=1} is placed, and spin configuration x is specified by set of spin variables, i.c, (01, o2..... TT)T. In the one-dimensional Ising model at inverse temperature 3, spin configurations are generated ac- cording Gibbs distribution,
quintessential model for ferromag-
Pa(x)
(s)
(18)
Z3
where Zp is normalization constant known in statistical mechanics the partition function and
H(x) = Σ
0,0441
(19)
111
called the Hamiltonian, which gives the energy of the system.
Now we two different inverse temperatures 3, and 32, and generate spin configurations following either Pp, (z) or (x) with equal probability by using Markov-chain Monte Carlo method. Then we ask whether a given spin configuration x is generated by Po, (x) or (x).)). This is a classification problem, which can be solved by machine learning.
13

---

Under review as a conference paper at ICLR 2021
0.5
depth 1, width
depth 7, width 500
0.45
0.35
0.25
1000
2000
3000 4000 5000 6000 7000 8000 9000 10000
N
Figure 6: Test error against the number of training data samples N. A shallow network of depth and width 500 shows better generalization compared with a deep network of depth 7 and width 500.
We consider supervised learning for this classification problem, where we fix d 500, 31 0.1, and Bg 0.3. A training dataset D {x(11) gg()) -== 1,2, ........N N] consists of spin configura- tions (x(#) and their labels {y(m)). ). If .00) is generated at the inverse temperature 31 (or 32), its label is given by y(r) = (or 2). Training is done with the same procedure as in Sec. 2 After training, we measure the test error by using an independently prepared test dataset with 10 samples.
The temperature for a spin configuration is most successfully estimated by measuring its energy, ie., the value of (xr. Therefore (xx) plays the role of a relevant feature in this classification problem. It is obvious from Eq. (I9) that the energy is 2-global quantity, and hence, this problem
similar to the classification of the dataset with the 2-global label. We then expect that, from our main result discussed in the main text, a shallower network will do better than deeper one.
Experimental results for a shallow network (L = 1 and H = 500) and deep one (L = and H = 500) shown in Fig. 6 For small N, both networks show almost identical performance, while for larger N, the shallow network clearly outperforms the deep one.
Apart from this example, thermodynamic quantities in physics are usually expressed in terms of sum of local quantities over the entire volume of the system, and hence they are global variables. Our main result thus implies that shallower networks are more suitable for machine learning of thermodynamic systems.
D RESULTS FOR THE MEAN-SQUARE LOSS
We shall present experimental results for the mean-square loss. Figure[]shows test errors for varying N in various networks for (a) the 2-local label, (b) the 2-global label, (c) 3-local label, and (d) 3-global label. As for the depth dependences, we find qualitatively the same behavior as in the cross-entropy loss. That is, deeper is better for local labels, while shallower is better for global labels.
However, we also find that generalization performance quantitatively depends on the choice of the loss function. Overall, the cross coos-eyntropy loss yields better generalization than the mean-square loss. In particular, for the 2-local and 3-local labels, results for the square loss tend be closer to those in the NTK. It indicates that the network trained with the cross-entropy loss more easily gets out of the lazy learning regime compared with the network trained with the mean-square loss. This is natural since the weights in the network trained with the cross entropy loss will eventually go to infinity after all the training data samples are correctly classified (Lyu & Li 2020) no regulariza- tion such as the weight decay is used, On the other hand, for the mean-square loss, the network parameters can stay close to their initial values and therefore in the lazy learning regime throughout training Arora et al. (2019).
We also find that test errors for the mean-square loss show stronger dependences on the width of the network, especially for local labels. For example, let compare Fig. 2 (b) and Fig. 7 (b).
14

---

Under review as a conference paper at ICLR 2021
(a) 2-local
(b) 3-local
0.5
0.5
0.4
0.4
tost asor
0.3
eroor
0.2
0.2
degih 1. widht 500
depth wid.3 500
death 1, 1..dthhhh2 2000
depth 1, w00th 2000
0.1
depth 7. M1200 100
0.1
depth: 7. Mid7 100
degta
depth
depti:
NTK,
NEK. deptt
NTK, depta
10000
20000
25000
10000
20000
25000
30000
(c) 2-global
(d) 3-global
0.5
0.5
depih
drgith wirth 130
0.4
degith width son
0.9
degth
lost a000
022
0.2
depth writh
depth 1, wodth 2001 depth: Mi27 100
0.1
0.1
deptt NEK,
NER, deps
19000
25000
5000
N
Figure 7: Test error against the number of training data samples N for several networks trained with the mean-square loss for (a) the 2-local label, (b) the 3-local label, (c) 2-global label, and (d) 3-global label. Error bars indicate the standard deviation of the test error for 10 iterations of the network initialization and the training. Test errors calculated by the NTK of the depth of I and 7 are also plotted.
In the case of the cross-entropy loss, the network of 7 and H = 100 fails to generalize for small N (N S 15000) but generalizes well for larger N. On the other hand, the case of the reean-squrre loss, the same network does not generalize well at least up to N = 30000, although and
the network of with recent rigorous results (Zu et all. 2020: Nitanda et all, 201 Ji & Telgarsky, 2019; Chen all 2019), which show that the cross-cntropy loss requires a much smaller width compared with the mean-square loss to realize overparameeterized regime.
500 does. Strong width dependences found in Fig. 7 are consistent
15


Reviews:
[{"review_id": "wTNh0pyt-cG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "\nThis paper analyzes overparametrized networks evaluating how depth and width affect the generalization performance of the network. A set of experiments is designed in which labels are determined either by local or global interactions among the features, and generalization is observed for different values of width and depth of the network. NTK is also considered as a limit case of a network with infinite width.\n\nThe paper is well-written, and the experiments properly designed and explained. I appreciate the rigorous study, and the observations drawn, although theoretical arguments in support of the conclusion would have made them stronger. The connection between depth and local labels, and between shallowness and global label intuitively makes sense in the explanation of the authors, but I am left wondering how widely generalizable are these conclusions? What is the effect of the data generation procedure? Similarly the comparison with NTK is interesting, even if it seems to me more confirming NTK theory than providing clear support for the argument of the paper about the effects of depth; the conclusion of section 3.3 agrees with general NTK, but maybe it would have been helpful a longer discussion on how this relate to feature learning.\n\nIt seems to me that this work is good, but quite preliminary. It devised well-designed experiments, but all the contributions are empirical observations. It would definitely gain more value if a rigorous theoretical discussion of the results may be offered, or, if the same behavior may be observed on other, possibly real-world datasets.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "t_ioJsQf1dS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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 aims to empirically explore the depth dependence of overparameterized networks. The authors study fully-connected networks trained on a synthetic dataset consisting of random Gaussian inputs, with the label a simple function of the input. In one case, for \"local\" labels, the label is the parity of a product of a subset of the components. In the other case, for \"global\" labels, the label is a sum of such products of subsets with coverage over all the components. Broadly, the authors find that deeper MLPs are better able to learn the local labels, but shallower MLPs are better able to learn the global labels. Finally, the authors compare these results to the infinite width NTK and show that the NTK does not at all capture the behavior of the finite networks.\n\nI think the strongest point of the paper is that the authors are able to find such a robust effect. The design of the synthetic dataset is very clever, and the results on depth and finite vs. infinite width are very compelling.\n\nI think my biggest concern is whether this robust effect relates to global vs. local features in real data in the way that the authors suggest. I agree that the functions considered by the authors have a nice notion of \"local\" and \"global\" but I'm not sure how good a representation this is of the types of features that are present in real data. At the very least, it would have been nice to have some kind of discussion of the relationship, and at best the authors could have provided some kind of evidence that the features in an exemplar real dataset can be organized this way. I think that this is not completely obvious since the features considered here are multiplicative in components and the label is based on parity. (Do local features in images have this property? What do the authors have in mind for a global feature in an image? I highly doubt that things are arranged in sums of products over the whole image, with the parity of the result being important.) I understand that this is a toy model and I appreciate the nice result; I just would like to understand how representative this toy is.\n\nI think that this is a good paper, and I recommend that ICLR accepts.\n\nI think the experiments are clever, the results are robust, and -- despite my concerns about how to relate this dataset to \"real data\" -- the discrepancy between local and global information and depth is really interesting. I also find the comparison with the infinite width NTK to be very useful; it's really important to understand the ways in which infinite networks are good models for realistic finite networks, and here the authors demonstrate that such infinite networks completely fail on this task.\n\nOne question I had for the authors is why they think that shallow networks can learn global features better than deeper networks. I don't think the authors try to offer an explanation for this effect at any point.\n\nAdditionally, I was wondering whether the authors did any experiments for much larger k. Clearly k=d is not that interesting, but were there experiments in a middle regime rather than k << d? \n\nFinally, could the authors comment on the relationship of their results to that of arxiv2007.15801? In that paper, for MLPs, the authors seem to find that infinite width networks broadly perform better than finite width networks. Inspection of your Figure 2(c) suggests one possibility is that real data is more akin to having global information? On the other hand, in that paper the authors find that finite networks outperform infinite networks for convolution networks (which obviously care about features that are local in space, and not the less-restrictive k-local notion of locality). Did the authors consider or make any experiments on convolutional architectures?\n\nDid the authors consider any other initializations other than what's discussed in the paper and footnote 2?\n\nA minor comment: I think footnote 1 is a little misleading. The \"k-global\" label type would still be considered \"k-local\" from a quantum information perspective. (Of course the authors are welcome to describe their invented dataset however they like.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "iYBWx-4Xeyi", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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 proposes an empirical study of the nature of `\"local\" and \"global\" features and how well they can be approximated via fully connected networks under a highly controlled experimental setup.\n\nPros’:\nThe experiments are highly controlled and the research seems fairly reproducible\nThe paper is self-contained\nThe paper -- though containing a mathematical motivation linked to approximation theory -- is written in a very accessible way for non-expert researchers in the field (myself)\nThe overall question and motivation of the problem the authors are studying is of great importance in the fields of approximation theory, local vs global (Theory of Deep Learning, Applied Vision Science & Representation Learning) and learning capacity via SGD as well. [I am willing to raise my score if authors convince me what I have missed, or where I was confused -- see below].\n\nCons’:\nThere seems to be a misnomer on the definition of what local and global means. I am confused, and these two concepts that should be quite intuitive, are actually defined to mean different things (section 2.1 -- see critical observation below).\nAuthors present good empirical analysis but there is no potential explanation of their conclusion that suggests that global features can be approximated better with shallow networks, and local features with deeper networks. Arguments potentially linked to receptive field size and hierarchy like in vision science (Neyshabur, 2020; Deza, Liao, Banburki & Poggio 2020) would be interesting, but naturally authors cannot make such claims given that all networks trained/tested were fully connected with a R.F. size of 1.\n\n----\n\nCritical Observation [Section 2.1]\n\nK-local label vs K-global label: Why does each k-local label depend on a multiplication of all k entries, while k-global depends on a sum of all k-entries? There seems to be a misnomer on what local and global means here. It is as if in both cases the label is determined by “global” properties (as all the inputs are used to compute the label), but the only difference is the operation type: multiplication vs sum -- but I could have missed something. This is quite confusing even though the authors state in the paper that locality need not mean spatial locality.\n\nThe problem with the confusing definition of locality and global properties is that it permeates into the introduction and conclusion of the paper and other relevant work. For example the claim in the introduction: “deeper is better for local labels, while shallow is better for global labels” under this new definition is confusing as it suggests something that is not what it seems. Unless local here literally means spatially local or implies that a function ignores/zeroes out other inputs (as it would be for functions with restricted -- hence local -- domains to compute the output), then the claim of the paper is misleading/confusing with the relevant literature. Authors should do a better job in arguing why they choose multiplication as a proxy for a local operation and summation as a proxy for a global one. If anything it would make more sense that a k-local label is essentially a subset of the k-global label (example a partial sum, vs a different operation altogether). \n\nAgain, at a higher level: I would have expected a sort of definition where there is only a single “global” label (vs k-global label) computed from a feature vector, and `multiple’ k-local labels, depending on what entries in the feature vector are sampled, such that as k reaches the total input size k-local is equal to “global” -- but this does not seem to be the case.\n\n---\nSections 2.2 and onwards seem more clear.\n\nOther observations: I really like the dissociation for k-local (continuing with the definition proposed by authors) and k-global labels expressed in Figure 2. This is a neat result, but again I think the argument made should be pushed towards the fundamentally different nature of the operation (multiplication vs addition -- and not local vs global)\n\nThe rest of the paper Figure 3 seems quite interesting to find the point in depth such that there is equalized performance for the 2-local and 2-global cases. On the other hand, I am not sure what Figure 4 is supposed to bring to the table (it seems like comparisons to performance with NTK) -- but, so what? Why does this matter?\n\n---\n\nI think the paper overall proposes a good first step via empirical analysis of the local vs global problem (under the authors definitions), but I would have wished that the paper ended on a higher note with regards to, *why* is k-locality approximated better with deeper networks, and k-global labels with shallow ones. Not that a proof would be necessary, but at least an intuition given the mathematical structure of the network (stacked dot products + non-linearity), their approximation power, and the nature of the label (multiplication vs addition). \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5otdIN6fMW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "Recent theoretical study on the training of neural networks has introduced an important kernel function called neural tangent kernel. This paper studies the training of deep ReLU networks and compares it with the training directly using NTK by conducting experiments on synthetic data. Based on the experimental results, the authors conclude that deeper networks perform better on certain datasets whose labels are more “local”, while shallower networks are better at more “global” labels. Moreover, the authors observed that finite-width networks have better generalization than NTK. \n\nI am not convinced by the claims of this paper, for the following reasons:\n\n1. First of all, the definition of NTK in this paper in equation (10) may be wrong. If I understand it correctly, the definition of NTK in Jacot et al., 2018 uses gradient with respect to the W’s instead of the w’s. Therefore by chain rule, the definition in this paper differs from the correct definition by a large factor. This can be essential and may be the reason why the experimental performance of NTK is so bad. For the same reason, it may also be possible that not all layers of the network has been trained with the same importance (some layers change faster than other layers due to having a different chain-rule factor), and this can potentially lead to performance differences for NNs and NTKs with different depths.\n\n2. Moreover, the comparison done in this paper is between finite neural networks trained with *cross-entropy loss* and NTK trained with *mean square loss*. The authors commented that replacing cross-entropy loss with mean square loss does not make much difference. However, in the NTK literature there is indeed some difference in landscape properties, over-parameterization requirement, etc (Zou et al., (arXiv:1811.08888), Nitanda et al., (arXiv:1905.09870), Ji & Telgarsky, (arXiv:1909.12292), Chen et al., (arXiv:1911.12360)). Moreover, for classification losses, if the network is trained for a very long time, it will eventually escape from the NTK regime since cross-entropy encourages the weights to go to infinity after all training samples are correctly classified (Lyu & Li, (arXiv:1906.05890)), while the whole training path for square loss is in the NTK regime (Arora et al., (arXiv:1904.11955)). Therefore I suggest that the authors should add training results for finite-width NN using square loss as well, and comment on how their experimental results reflect the results in the references mentioned above.\n\n3. My third concern is closely related to the second one above. Throughout the paper, the authors discussed finite width NNs as if they are not in the NTK regime or lazy training regime (for example the 4th paragraph on page 2). This is not true, as almost all results in NTK regimes indeed study wide, but finite NNs. In fact, it is shown in Ji & Telgarsky, (arXiv:1909.12292) and Chen et al., (arXiv:1911.12360) that NNs with (almost) constant width can still fall in the NTK regime with classification losses (unless, of course, when trained for too long). It has been studied that whether the training is in NTK regime is not determined by the width, but the scaling of the network (Chizat et al., (arXiv:1812.07956), Mei et al., (arXiv:1902.06015), Chen et al., (arXiv:2002.04026)). \n\nBecause of the above two points 2 and 3, I am particularly skeptical about the authors’ explanation of the performance difference between finite NN and NTK.\n\n4. There have been some slight differences in the definition of NTK. Particularly, it is discussed in Cao and Gu, (arXiv:1905.13210) that different definitions of NTK may differ in a 2^L factor for ReLU networks. I briefly checked Section A of the submission and it seems that the calculation of this paper matches Cao and Gu, (arXiv:1905.13210). Since the network depth is the focus of this paper, the authors may consider clarifying it.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers found the construction is very clever and the empirical results are interesting. However, a more thorough theoretical explanation is needed for acceptance. 
Decision: Reject