Are wider nets better given the same number of parameters?
Authors: Anna Golubeva
Guy Gur-Ari
Behnam Neyshabur
Venue: ICLR 2021 Poster (2021)
Keywords: network width
over-parametrization
understanding deep learning

Abstract: Empirical studies demonstrate that the performance of neural networks improves with increasing number of parameters. In most of these studies, the number of parameters is increased by increasing the network width. This begs the question: Is the observed improvement due to the larger number of parameters, or is it due to the larger width itself? We compare different ways of increasing model width while keeping the number of parameters constant. We show that for models initialized with a random, static sparsity pattern in the weight tensors, network width is the determining factor for good performance, while the number of weights is secondary, as long as the model achieves high training accuarcy. As a step towards understanding this effect, we analyze these models in the framework of Gaussian Process kernels. We find that the distance between the sparse finite-width model kernel and the infinite-width kernel at initialization is indicative of model performance.

Published conference paper at ICLR 2021
ARE WIDER NETS BETTER GIVEN THE SAME NUMBER OF PARAMETERS?
Anna Golubeva"
Behnam Neyshabur Blueshift, Alphabet
Perimeter Institute for Theoretical Physics Waterloo, Canada
Mountain View, CA
agolubeva@pitp.co
neyshabur@google..com
Guy Gur-Ari
Blueshift, Alphahet Mountain View, CA
guygalgoogle.com com
ABSTRACT
Empirical studies demonstrate that the performance of neural networks improves with increasing number of parameters. In most these studies, the number parameters is increased by increasing the network width. This begs the question: the observed improvement due to the larger number of parameters, due to the larger width itself? We compare different ways of increasing model width while keeping the number of parameters constant. We show that for models initialized with random, static sparsity pattern in the weight tensors, network width is the determining factor for good performance, while the number weights is secondary, as long as the model achieves high training accuarcy. As a step towards understanding this effect, Gaussian Process kernels. We find that the distance between the sparse finite-width model kernel and the infinite-wide width kernel at initialization is indicative of model performance.
is it
analyze these models the framework of
INTRODUCTION
Deep neural networks have shown great em- pirical success solving a variety of tasks across different application domains. One of the prominent empirical observations about neural
num. weights
0.96
0.8m=05
nets is that increasing the number of parame- ters leads improved performance (Neyshabur al., 2015; 2019; Hestness et al., 2017: Kaplan et al., 2020). The consequences of this effect for model optimization and generalization have been explored extensively. In the vast majority of these studies, both empirical and theoretical, the number of parameters is increased by in- creasing the width of the network (Neyshabur et al., 2019; Du et al., 2019; Allen -hu et al., 2019). Network width itself the other hand has been the subject of interest studies analyz- ing its effect on the dynamics of neural network optimization, e.g. using Neural Tangent Ker- nels (Jacot al., 2018: Arora et al., 2019) and
accuracy
0.94
9.0le-05
1.2e--07
0.92
0.74
SVII
0.72
CIFARIO
0.70
CIFARIGO
ImageNet
0.68
10
10a widening factor
Figure 1: Test accuracy of ResNet-18 18 as function of width. Performance improves width is inereased, even though the number of weights is fixed. Please see Section 2.3 for more details.
"Work done while an intem at Blucshift. 'Code available ht tpa //1 th....bbb................ com /goog/ e- reseereeaareee wwwparrwwwwweeesep...eeee oat

---

Published conference paper at ICLR 2021
dixda
fdxxdb
daxfdo
dxd dxd
fdxdb dhxd
d:xd dxd.
dxxfd fdxda
(a) Linear Bottleneck
Non-linear Bottleneck
(c) Static Sparsity
Figure 2: Schematic illustration of the methods we use to increase network width while keeping the number of weights constant. Blue polygons represent weight tensors, red stripes represent non-linear activations, and diagonal white stripes denote sparsified weight tensor. We use to denote the widening factor.
Gaussian Process Kernels (Wilson et al., 2016; Lee et al., 2017).
When increasing the width, the number parameters is being increased as well, and therefore is not possible to separate effect of increasing width from the effect of increasing number of parameters. How does each of these factors width and number of parameters contribute to the improvement performance? We conduct principled study addressing this question, proposing and testing methods of increasing network width while keeping the number of parameters constant. Suprisingly, we find scenarios under which most of the performance benefits come from increasing the width.
All studies know of suffer from the same fundamental issue:
1.1
OUR CONTRIBUTIONS
In this paper we make the following contributions:
We propose three candidate methods (illustrated in Figure for increasing network width while keeping the number of parameters constant.
(a) Linear bottleneck: Substituting each weight matrix by product of two weight matrices. This corresponds to limiting the rank of the weight matrix.
(b) Non-linear bottleneck: Narrowing every other layer and widening the
(c) Static sparsity: Setting some weights to using mask that is randomly chosen initialization and remains static throughout training.
We show that performance can be improved by increasing the width, without increas- ing the number of model parameters. We find that test accuracy can be improved using method (a) or (c), while method (b) only degrades performance. However, we find that (a) suffers from another degradation caused by the reparameterization, even before widening focus the sparsity method (c), it leads the hest results and applicable to any network type.
the network. Consequently,
We empirically investigate different ways in which random, static sparsity can be distributed among layers of the network and, based on our findings, propose an algorithm do this effectively (Section 2.3).
We demonstrate that the improvement due widening (while keeping the number of parameters fixed) holds across standard image datasets and models. Surprisingly, we obesrve that for ImageNet, increasing the width according to (c) leads to almost identical performance as when allow the number of weights increase along with the width (Section 2.3).
To understand the observed effect theoretically, we study simplified model and show that the improved performance a wider, sparse network correlated with a reduced distance between its Gaussian Process kernel and that of an infinitely wide network. We propose that reduced kernel distance may explain the observed effect (Section 3).
1.2 RELATED WORK
Our work is similar in nature to the body of work studying the role of overparametrization and width. Neyshabur al. (2015) observed that increasing the number of hidden units beyond what

---

Published conference paper at ICLR 2021
necessary to fit the training data leads to improved test performance, and attributed this to the inductive bias of the optimization algorithm. Soltanolkotabi et al. (2018); Neyshabur et al. (2019); Allen-Zhu et al. (2019) further studied the role of parameterrizaiionn in improving optimization and generalization. Woodworth et al. (2020) studied the implicit regularization of gradient descent the over- wver-parameterized setting, and Belkin et al. (2019) investigated the behavior at interpolation. Furthermore, Lee al. (2017) showed that networks at initialization become Gaussian Processes in the large width limit, and Jacot al. (2018) showed that infinitely wide networks behave as linear models when trained using gradient flow. Lee et al. (2020) systematically compared these different theoretical approaches. In all the above works, the number of parameters is increased by increasing the width. However, this work, we conduct a controlled study of the effect of width by keeping the number of parameters fixed.
Perhaps Littwin et al. (2020) is the closest work to ours, which investigates overparametrizatioon achieved through ensembling opposed to layer width. Ensembling is achieved by connecting several networks in parallel into one "collegial" ensemble. They show that for large ensembles the optimization dynamics simplify and resemble the dynamics of wide models, yet scale much more favorably in terms of number of parameters. However, the method employed there is borrowed from the ResNeXt architecture (Xie et al., 2016), which involves altering the overall structure of the network as width is increased. In this work we try to make minimal changes to network structure, in order to isolate the effect of width network performance.
Finally, static sparsity is the basis of the main method we use increase network width while keeping the number of parameters fixed. There is a large body of work on the topic of sparse neural networks (Park et al., 2016; Narang et al.. 2017: Bellec et al., 2018; Frankle and Carbin, 2018: Elsen al., 2019; Gale al., 2019; You al., 2019), and many studies derive sophisticated approaches to optimize the sparsity pattern (Lee et al., 2018; Evci et al., 2019; Wang et al., 2020; Tanaka et al., 2020). In our study, however, sparsity itself is not the subject of interest. In order to minimize its effect in our controlled experiments, the sparsity pattern that we apply is randomly chosen and static, recent work (Frankle et al., 2020) demonstrates that random, fixed sparsity pattern leads to equal performance as the more involved methods for pruning applied at initialization, when the per-layer sparsity distribution is the same. However, do not explore this direction in our study.
2 EMPIRICAL INVESTIGATION
In this section, first explain our experimental methodology and then investigate the effectiveness of different approaches increase width while keeping the number of parmeters fixed. Finally, we discuss the respective roles of width and the number of parameters in improving performance.
2. METHODOLOGY
In order to identify how width and number of parameters separately affect performance, need to decouple these quantities. For a fully-connected layer, width the number of hidden units, and for a convolutional layer, width corresponds to the number of output channels. Increasing the width of one layer ordinarily entails increase in the number of weights. Therefore, some adjustment is required to keep the total number of weights constant. This adjustment can made the level of layers by reducing some other dimension (i.e., by introducing a "bottleneck"), or at the level of weights by setting some of them be zero. When choosing method for our analysis. take particular care about possible confounding variables, as many aspects neural network are intertwined. For example, we prefer to keep the number of non-linear layers in the network fixed, as it has been shown that changing it can significantly affect the experssive power, optimization dynamics and generalizaiton properties of the network. With these constraints in mind, we specify three different methods listed in Section 1.1. In this section, we discuss these methods in detail, evaluate them, and present the results obtained on image classification tasks.
In summary, our approach as follows: We select a network architecture which specifies layer types and arrangement (c.g., MLP with some number of hidden layers, or ResNet-18), 18), set layer widths, and count the number of weights. We refer to this model as the baseline, and derive other models from it by increasing the width while keeping the number of weights constant. In this way, we obtain a

---

Published conference paper at ICLR 2021
CIFAR-10
CIFAR-100
CIFAR-10
CIFAR-100
0.94
0,94
0.74
0.71
W.
occuracy
0.901
(1.62
0,90
0.64
107
0.88
0.54
0.86
0.54
10a
10P
10
100
10
10a
widening factor
widening factor
widening factor
Widening factor
(a) Linear bottleneck
(b) Non-linear bottleneck
Best test accuracy obtained by ResNet-18 models widened using the bottleneck methods. The performance of the baseline network (before introducing bottleneck layers) is denoted by dashed lines. The legend indicates the numher of weights in the haseline network. In (a), is equal to the number of weights before introducing bottleneck layers. In (b), it is equal to the total number of weights.
Figure 3:
lamily of models that we train using the same training procedure, and compare their test accuracies. For comparison and sanity check, we also consider the dense variants of the wider models.
We tested a variety simple models, and observed the same general behavior in the context of our research question. For the discussion in this paper, we focus on two model types: MLP with one hidden layer, and ResNet-18. 18. We chose the ResNet-18 architecture because it is standard model widely used in practice. Its size small enough that allows us to increase the width substantially, yet it has sufficient representational power to obtain nontrivial accuracy on standard image datasets. When creating family of ResNet- 18 models, convolutional layer as the width, and do not alter the default width ratios of all following layers. Further details of each experiment and figure are specified in Appendix A.
refer to the number of output channels of the first
2.2 BOTTLENECK METHODS
Here we discuss the two bottleneck methods described in the previous section and in Figure 2.
Linear Bottleneck: Substitute each weight matrix W e xd. by Wi W2, where W1 E B44 xd, W2 E Rds xd. and de S min(d, d.).2 Note that if d, min(d;, do), then this reparametrization has the exact same expressive power the original network. Now, one can make the network wider by increasing the number of hidden units (d, and d, here) and reducing the bottleneck size da. This would correspond to imposing low-rank constraint on the original weight matrix W. Linear bottleneck has been proposed as way reduce the number of parameters and improve training speed (Ba and Caruana, 2014; Urban et al., 2016). The caveat of this method is that, even though the expressive power of the reparametrized network is the same as the original one, the reparameterization changes the gradient descent trajectory and hence can affect the final results. It is therefore not possible to control the implicit regularization caused by this transfornation. Note that substituting the weight matrix by a product of two matrices changes the number of parameters of the model.
Non-linear Bottleneck: One way to create a non-linear bottleneck is to split each layer in two as described above and add non-linearity to the first layer. The problem with this approach is that adding non-linearity changes the expressive power of the model, and hence adds factor that we cannot control. An alternative approach, which is more favorable in our case and which we adopt here, is to modify the layers in pairs. The input dimension of the first layer is increased, while its output dimension (and consequently the input dimension of the second layer) reduced (d, < d). Non-linear bottlenecks are widely used in practice, particularly as a way to save parameters in very deep architectures, such as deeper variants of ResNet (He et al., 2016) and DenseNet (Huang et al.. 20.
The performance of these methods on CIFAR- 10 and CIFAR- 100 datasets demonstrated in Figure 3. The results indicate that increasing width using the linear bottleneck indeed leads to improved
"I the case of ResNet- 18 model. each convolutional layer is replaced by two convolutional layers with kernel dimensions 3 x and I 1, respectively, and with d, = d, = d. before widening. Here, expressive power refers the of functions that can he represented by the network.

---

Published conference paper at ICLR 2021
Weights per layer
Weights removed certain connectivity
Additional weights removed at lower connectivity
Layer
Figure 4: Iulustration of our algorithm for distributing sparsity over model layers. The code imple- menting this algorithm is included in Appendix B.
accuracy up to certain width. Moreover, this effect more pronounced smaller models that are less overparameterized. This is similar to the improvement gained when increasing the width along with the number of parameters (without bottleneck): The improvement tends to be diminished when the base network wider. However, as discussed above, the act substituting a weight matrix by a product of two weight matrices changes the optimization trajectory which could in turn affect generalization. Indeed, the performance of the original model, indicated by dashed horizontal lines the Figure, is significantly higher than that of transformed models. Therefore, even though the width increase at a constant number of weights with the linear bottleneck method improves the result of the most narrow model obtained after the transformation. it typically does not outperform the default ResNet-1 18 model. Due lack of control over the effect of inductive bias, we conclude that this choice does not qualify to be used in our controlled experiments.
The non- non-linear bottleneck method does not suffer from the same issues as the linear version in empirical
terms of inductive bias of reparametrization. However, Figure 3 demonstrates. improvement is obtained by increasing the width, except for the model with 1.8e+055 weights (and then the improvement is mild). Therefore, we conclude that the non- non-lineat linear bottleneck model does not show significant enough improvement be considered
effective method for our study.
2.3 SPARSITY METHOD
We now turn to sparsity method illustrated in Figure 2c, which is main method considered this work. We start with a baseline model that has dense weight tensors. We then increase the width by widening factor and sparsify the weight tensors such that the total number of trainable weights is the same as in the baseline model. In an attempt to run a controlled experiment and minimize the differences between the sparsified setup and the baseline setup, we choose the sparsity mask at random initialization and keep it static during training. In this sense, method differs from most literature, where the aim is to maximize performance. The
other pruning methods discussed advantage of the sparsity method over the bouleneck methods considered earlier is that it allows control the number of weights without altering the overall network structure. We define the connectivity of a sparse model to the ratio between the number of parameters and the number of parameters in dense model of the same width.
In order to implement the sparsity method, we need to choose how to distribute the sparsity both across network layers and within each layer. To prevent smaller layers from being we choose the number of weights to be removed in each layer to be proportional to the number weights in that layer (except for BatchNorm layers, which are kept intact). Figure 4 demonstrates the principle of our algorithm for sparsity distribution. Within each layer, we distribute the sparsity uniformly across all dimensions the weight tensor. Overall, this method of distributing the weights led to the best performance among the different methods we tried in our experiments (see Appendix C for more details).
entirely,

---

Published conference paper at ICLR 2021
1.0
0.95
1.0
*
0.9
0.9
0.90
fast
0.90
0.8
0.7
0.7
0.85
0.6-
0.85
0.6
0.55
0.80
0.4-
0.4
0.3
0.2
0.75
0.3
0.2
0.75
0.70
- 0.70
8e43
1.0
8c-03
1.0
connectivity of whole network
connectivity of whole network
(a) ReLU
(b) Linear
Figure 5: Test accuracy (color-coded) on MNIST obtained by MLP models with hidden layer and ReL. or linear activations, as function of overall connectivity (horizontal axis) and of connectivity in the last layer (vertical axis). White stars indicate points with the highest test accuracy.
MLP.
We study fully-connected network with one hidden layer trained on MNIST. We use this simple setup to compare different sparsity distribution patterns across layers for given network connectivity, and to compare the effects of increased width with and without ReLU non-linearities.
The dense MI.P width has weight matrices: The first layer matrix has size 784 and the last layer has size n x 10. In the experiments, we set the total number of weights to 3970 and consider widths ranging from 5 to 640, corresponding to network connectivities between and 5 5/640 ~ 0.008. At each width, we vary the connectivity of the last layer (the smaller of the two) between 1.0 and 0.1.
The results are shown in Figure baseline models for both ReL.U and linear activations. The ReLU model attains its maximum performance around 3 6% connectivity, which corresponds to widening factor of 16 or 32. At the optimal point the connectivity the last layer high, above 80%. therefore advantageous this case to remove more weights from the first layer than from the last layer. This makes intuitive sense: Removing weights from layer that starts out with fewer weights be expected to make optimization more difficult. This result motivates our choice remove weights proportionally layer size when sparsifying other models. Finally, the fact that larger width leads to improvement even in the deep linear model implies that the improvement cannot be attributed only to the increased model capacity that wider ReLU network enjoys.
find sparse, wide models can outperform the dense,
We train families ResNet-18 models on ImageNet, CIFAR-10, CIFAR-100 and SVHN, covering a range of widths and model sizes. A detailed example of the sparsity distribution over all layers is shown in Appendix D.
ResNet-18.
Table shows the results obtained ImageNet. As expected, the performance improves the width and the number of weights increase (row 1). However, up to a certain width, a comparable improvement is achieved when only the width grows and the number of weights remains fixed (row 2). We point that test accuracy declines around the same width that training accuracy declines (see additional plots presented in Appendix E). Therefore. in this case the determining factor for model performance is width rather than number of parameters. Figure 6 shows the results of training model families several additional datasets. We again find that performance improves with width a fixed number parameters, up to a certain widening factor. The effect most pronounced for more difficult tasks and for smaller models that do not reach 100% training accuracy, yet it is still present for models that do fit the training (see also Appendix E).
width
64
90
128
181
256
dense
68.03 (11.7) sparse
69.11 (22.8)
70.22 (45.7)
70.91 (90.7)
71.89 (180.6)
69.56 (11.7) 70.02 (11.7) 70.66 (11.7)
70.53 (11.7)
Table 1: ResNet-18 ImageNet: Top-1 test accuracy (in %) and in parentheses the number of weights in millions. All sparse models have the number weights the smallest dense model, yet the improvement obtained with increasing width par with the dense models, up certain width.

---

Published conference paper at ICLR 2021
Figure compares the performance improvement of sparse, wide model against that of dense model with the same width. In particular, it shows the fraction of the improvement that can be attributed to width alone: That is, the ratio between the sparse/baseline accuracy gap and the dense/baseline accuracy gap. We see that as long as the model can achieve high training accuracy, most of the improvement in performance can be attributed to the width.
SVHN
CHFAR- R-10
CIFAR- 100
0.97
0.96
0.80
weigitit
1.T++07
accuracy
0.96
0.94
0.75
4.4e+006
9.0e 06
0.95
0.92
0.70
1. 1.0e++U5
1.8m-405
0.94
0.90
0.65
0.93
0.88
0.60
10P
10a
10P
10
10"
10
widening factor
widening factor
widening factor
Figure 6: Best test accuracy obtained by ResNet-18 models of different width and size (i.e.. total number of weights; approximate value shown in the legend). The leftmost data point of each color corresponds to the dense buseline model, and all subsequent data points correspond to its wider and sparser variants. The decline of performance larger widening is because sparsity these levels harms the optimization procedure, making the training accuracy deteriorate. See Appendix E for the same data plotted as function of network connectivity, the corresponding training accuracy, and for the version with error bars.
SVHN 100
CIFAR-10
CIFAR-100
ImageNet
improement
1.00
1.00
100 1.00
90
1.50
90
tmin accurary (%)
1.00
0.50
0.50
0.50
80
80
explaned
0.50
0.00
90
0.00
90
0.00
70
0.00
70
10"
10P
10
10P
10
widening factor
widening factor
widening factor
widening factor
Figure 7: The fraction of test accuracy improvement (black triangles) obtained by widening the model without increasing the number of weights, compared to increasing the number of weights along with the width. The dashed vertical line indicates widening factor for maximal training accuracy (red circles). Note that for ImageNet, at width 90 (widening factor 1.4) the sparse model attained a higher test accuracy than the dense model, as reported in Table 1.
3 THEORETICAL ANALYSIS IN SIMPLIFIED SETTING
We showed empirically that wide, sparse networks with random connectivity patterns can outperform dense, narrower networks when the number of parameters fixed. The performance as a function of the width has maximum when the network is sparse. In this section we investigate potential theoretical explanation for this effect.
is well known that wider (dense) networks can achieve consistently better performance. In the infinite-width limit, the training dynamics of neural networks is equivalent under certain conditions to kernel-base learning, In particular, consider network function fa(z:) with model parameters 6. The Neural Tangent Kernel is defined by (x11, xr2) := Vo (x, ) VoJ (x))))) Jacot et al. (2018) showed that, in the infinite width limit (and with appropriate parameterization defined below), training the network fo using gradient flow is equivalent training linear model with the kernel O. Lee al. (2019) showed empirically that the NTK lineraization result can be a good approximation for the training dynamics of networks with large but finite width.
Based on these results, we propose a possible explanation for the main effect observed in this paper. which is valid for networks with sufficiently large but finite width. We conjecture that the kernel of

---

Published conference paper at ICLR 2021
(a)
(b)
0.94
0.03
0.16
D experiimnt
0..2
accuracy
0.02
0.14
Test error
0.90
0.01
0.12
0.88
dense x sperso
H
0.86
0.00
0.10
250 width
500
0
125
250
375
500
width
Figure 8: MLP with hidden layer and biases trained subset of MNIST. (a) Test accuracy achieved by dense (filled circles) sparse (crosses) models different width. Mean squared distance the sparse model's kernel from the infinitewwddth model's kemee computed initialization (both experimental (blue) and thcoretical (grey) result), and the error attained by trained models (pink). The empirical distance D obtained by averaging squared distance (Ger (2, v) G y))² over 10 pairs of test samples over random initializations. See Appendix A for additional details.
finite-width network at initialization is indicative of performance, and that optimal performance is achieved when its distance the infinite-widd kernel is minimized. We further hypothesize that this distance can be reduced by increasing the network width fixed number of parameters. In the following, we formalize this conjecture and derive expressions for the kernel of a sparse unite-width network with one hidden layer. We calculate the kernel distance theoretically, and show that the distance predicted using this result is in good agreement with experiments.
Consider a 2-layer ReLU network function f Rd + I given by f(x) (nd) [ux] [2] == 2 (z). Here, x E Rd is the input, the network parameters are u E RRaxd and v E IR" (for simplicity, we omit the biases), and (-) the Heaviside step function. We note that in this section use NTK parameterization (Jacot al., 2018) for simplicity, whereas in previous sections we parameterization. Each network parameter is sampled independently from (0, o²) with probability and is set to with probability 1 p. We set の² =p- The probability density function for each parameter 0 therefore given by Pr(0)= = p(2ma²) 1-12 exp (-02/20² + p))( where 8(-) is the Dirac delta function. the following, we consider the Gaussian Process (GP) kernel the network, defined as GGr y) = (x)')
LeCun
Theorem 1. Consider the GP kernel Ocr of a 2-layer network with ReLU activations, where the weights are sampled from Pr(f). The mean distance squared between Ogr to the (dense) infinite-widd width kernel 0pp
Ee [Ocp(z,)) - (v,
[Riple,)) v) Ki Ke(e)))
pn [Kanle,) [1)(
(1)
Here,
Ria(2,)) v) 00
Σ
Ki(
(2)
(001))
Ki(z,y) (2mr)d/2
-1w1/// (w 1) (w w) H(w (-((w))lle (w v)
(3)
vector with elements {0, 1}, and x, = (S)z1,,... xasa) is the x vector with some elements zeroed out.
s= (S1,..., ...,,............ 8d)
The proof is provided in Appendix F. Also in the Appendix, we derive the following closed-form approximation to the kernel distance (1) under the assumptions that the input vectors I, y are independent random vectors and pd >>> 1:
E. [Oap(s,)) -0) ~
1 zd
-
1 x²
(4)

---

Published conference paper at ICLR 2021
order to keep the number parameters fixed we change the width, we set rp = const. Under this constraint, and assuming 1, the distance (4) is minimized when p. 2 Vnp/4d.
In Figure 8h we compare this approximation with the GP kernel computed empirically initialization. We find good agreement with the theoretical prediction (4) when dp > 1. Furthermore, we see that the minimal kernel distance at initialization and the optimal performance of the trained network are obtained at similar width, providing evidence in support our hypothesis.
4 DISCUSSION
In this work we studied the question: Do wider networks perform better because they have more parameters, or because of the larger width itself? We considered several ways of increasing the width while keeping the number of parameters fixed, either by introducing bottlenecks into the network, or by sparsifying the weight tensors using a static, random mask. Among the methods we tested, the one that led the best results was removing weights random in proportion to the layer size, using a static mask generated at initialization, In our image classification experiments, increasing the width using this sparsity method (while keeping the total number of parameters constant) led to significant improvements in model performance. The effect was strongest when starting with narrow basline model. Additionally, when comparing the wide, sparse models against dense models of the same width, we found that the width itself accounts for most of the performance gains; this holds true up to the width above which the training accuracy of the sparse models begins to deteriorate, presumably due to low connectivity between neurons.
Focusing on the sparsity method, we initiated a theoretical study of the effect, hypothesizing that the improvemenet in performance is correlated with having Gaussian Process kernel that is closer to the infinite-win width kernel. We computed the GP kernel of sparse, 2-layer ReLU network, and derived a simple approximate formula for the distance between this kernel and the infinite-width dense kernel. In our experiment, we found surprisingly strong correlation between the model performance and the distance to the infinite- mnitt kernel.
While our work is fundamental in nature, and sparsity is not the subject of this paper, the method we propose may lead to practical benefits in the future. Using current hardware and available deep learning libraries, cannot reap the benefits of sparse weight tensor in terms of reduced computational budget. However, in our experiments we find that the optimal sparsity can be around 1-10% for convolutional models (corresponding to a widening factor of between 3-10). Therefore. using an implementation that natively supports sparse operations, our method may be used build faster, more memory-efficite networks.
ACKNOWLEDGEMENTS
The authors would like thank Ethan Dyer, Utku Evei, Etai Littwin, Joshua Susskind, and Shuangfei Zhai for useful discussions.
REFERENCES
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. In ICLR (Workshop), 2015. URL http: //arxiv. org/ 412. 6614.
Behnam Neyshabur, Zhiyuan Li. Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations, 2019. URL / http:///pppeeeeeeeeeeeeeee net www.mmidddmygggghaa....
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable. empirically. arXiv preprint 171,00999,,,4909, 2017.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiy:2001 108361, 2020.

---

Published conference paper at ICLR 2021
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwer-parameterized neural networks. In International Conference on Learning Representations, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, pages 8141-81 1550,, 2019.
Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric P Xing. Deep kernel learning. In Artificial intelligence and statisties, pages 370-378, 2016.
Jaehoon Lee. Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:1711.000 2017.
Mahdi Soltamolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-paramen parameterized shallow neural networks. IEEE Transactions on Information Theory, (5(2):742-769) 2018.
Blake Woodworth, Suriya Gunasekar, Jason D Lec, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. arXiv preprint arXiv:2002.09277 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varianee trade-off. Proceedings of the National Academy of Sciences, (5443)):15499-5555) 2019.
Jaehoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite Versus Infinite Neural Networks: an Empirical Study. arXiv e-prints, art. arXiv:2007.15801 July 2020.
Etai Littwin, Ben Myara, Sima Sabah, Joshua Susskind, Shuangfei Zhai, and Oren Golan. Collegial ensembles, 2020.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated Residual Transformations for Deep Neural Networks, arXiv e-prints, art. arXiv:1611.05431 November 2016.
Jongsoo Park, Sheng R. Li, Wei Wen, Hai Li, Yiran Chen, and Pradeep Dubey. Holistic sparseenn: Forging the trident of accuracy, speed, and size. ArXiv, abs//660800 2016.
Sharan Narang, Greg Diamos, Shubho Sengupta, and Erich Elsen. Exploring sparsity in recurrent neural networks. ArXiv, abs/1704.05 19, 2017.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert A. Legenstein. Deep rewiring: Training very sparse deep networks. ArXiv, 1t.s/771.0051.... 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Training pruned neural networks. CoRR, abs/ 003.03653. 2018. URL. http://aaxxvvoro/ /abs///////// 1 1803. 635.
Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets. ArXiv, Mts//911.09923,, 2019.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks, ArXiv, 990219994499 2019.
10

---

Published conference paper at ICLR 2021
Haoran You, Chaojian Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Towards more efficient training of deep networks, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. SNIP: singleshoot networ pruning based on connection sensitivity. CoRR, abs/1810.02344) 2018. URL http::/arxii..r abs/ 1810. 0 02340.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners, 2019.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow, 2020.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow, 2020.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark?, 2020.
Jimmy Ba and Rich Caruana. Do deep nets really need to deep? In Advances neural information processing systems, pages 2654-2662, 2014.
Gregor Urban, Krzysztof Geras, Samira Ebrahimi Kahou, Ozlem Aslan, Shengjie Wang. Rich Caruana, Abdelrahman Mohamed, Matthai Philipose, and Matt Richardson. Do deep convolutional nets really need to be deep and convolutional? arXiv preprint arXiv: 1603.05691, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In H. Wallach, Larochelle, A. Beygelzimer, F. d'Alché-Bue, Fox, R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8572-8583. Curran Associates, Inc., 2019.
Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in neural information processing systems, pages 342-350, 2009.

---

Published conference paper at ICLR 2021
A EXPERIMENTAL DETAILS
In this section we provide experimantal details and additional information about the figures in the main text.
Figures and 6: In all experiments, we use a standard PyTorch implementation of the ResNet-1 18 model. We set the number of weights in the model by changing the number of output channels in the first convolutional layer (referred to as the model width), while leaving the width ratios between the first convolutional layer and the subsequent four blocks of the ResNet-18 18 at their default values 1 2: 4 8. We do not include the weights in the BatchNorm layers into the total weight count, and we do not sparsify these layers.
All models are trained using SGD with momentum=0.9, Cross- Cross-Entropy loss, and initial learning rate 0.1. The learning rate value and schedule were tuned for the smallest baseline model. We do not apply early stopping, and we report the best achieved test accuracy. For ImageNet, we use weight decay le-4, cosine learning rate schedule, and train for 150 epochs. Because of the computational cost of ImageNet experiments, we did not repeat each run multiple times. We have checked for two datapoints that the variance in training and test accuracy for different random seeds is smaller than 0.1%. For other datasets, we use weight decay 5e-4, train for 300 epochs, and the initial learning rate 0.1 is decayed at epochs 50, 120 and 200 with gamma=0.1. The reported results are averages over 3 runs with different random seeds.
In Figure the baseline model has width 64 (Ie7 weights) for ImageNet, and 18 (9e5 weights) for the other datasets.
In Figure 6, we consider baseline models with base widths [8, 12, 18, 40, 64), corresponding to a total of [1.8e5, 4.0e5, 9.0e5, 4.4e6, 1.177] weights respectively.
Figure 5: All networks are MLPs with one hidden layer, total of 3970 weights (base width is 5), and either (a) ReLU (b) Linear activation function. The networks parameterized according to the standard Pytorch implementation (weights and biases are randomly initialized from the uniform distribution). We train these models on MNIST for fixed number of 300 epochs (ensuring convergence), with SGD optimizer, no momentum, Cross-Entropy loss, with constant learning rate 0.1 and mini-batch size 100.
For ReLU, highest test accuracy (marked by white stars in the plot) is 96.3%, and is achieved by models with connectivity 0.06 (width 80) or 0.03 (width 160). For Linear, it is 92.7%, achieved at connectivity 0.13 (width 40). The color scheme centered at the test accuracy value attained by the baseline model (approximately 90% in both cases), and its upper limit is set to the respective highest achieved value. Empty (white) cells correspond to invalid combinations of connectivity values. Note that the range on the horizontal axis not equally spaced.
Figure 8: The MLP has one hidden layer, no biases, ReLU activation function, and NTK-style parameterization. It trained on a subset 2048 samples from the MNIST training set and tested on the full MNIST test set. The input is normalized with pixel mean and standard deviation as (image mean) / /stdev. We train for 300 epochs with vanilla SGD using Cross-Entropy loss and batch size 256. The learning rate was tuned separately for each width. The reported numbers are averages over 10 random seeds.
The number of weights in dense models is (784 + (iddwh while all sparse models have the same number weights as the smallest dense model (width 8): 6.352. The empirical approximation of the mnidt kernel is computed on a dense MI. with width 10a at initialization.
A.I IMAGENET DATA PREPROCESSING
In order to decrease the size of the dataset and be able to download to cloud instances with limited storage, we resized all images in the dataset by keeping their proportions fixed and setting their smallest dimension to 256. This procedure reduces the accuracy of ResNet models by aboud 1-2%.
Transformations for ImageNet: We follow the standard transformations used is training Imagenet. Following the list of py Torch data transformations applied on each image.
12

---

Published conference paper at ICLR 2021
RandonResizedCre (size=224, scale= (0.2, 1.0) > on the training set. Resize (256, transforms, CenterCrop (224)) ) the test set.
SPARSITY DISTRIBUTION CODE
The following code implements our algorithm for distributing sparsity model layers, Figure 4 illustrates the procedure.
def get_nt nt (num_to, _tt_tttfeeeeee_eeeeeeeeeee freeze_tot, num_R, tensor_dimg Distribute the total nomber of we nights to freeze over model layers.
Parameters
num_to_ freeze_tot (int) total number of weights to freeze. num_ W (diet) layer names (keys) and number of weights in layer (vals).
tensor dims (dict) layer names (keys) and the dimensions of layer tensor (vals).
Inamcs_sorte sorted fiist of str) layer names, sorted by magnitude in descending order.
Returns
ton_to_freeze flist of int) number weights freeze per layer, order corresponding Inames sorted.
#**
num num_layers len (1nhames_sorten nun_to_"reeze ne.zeros (num_layers, dtype-int) init
list of num. weights in layer, sorted order (largest first) num_ sortedd
[num [1name] for Iname in 1names_sorted)
compute num. weights differences between layers num W diffs np. diff (num W. sorted list) num W diffs (d) for d in num w [_diffs]]
auxiliary vector for the following dot product to compute the bins aux_vest np.arange 1, len (nun_M_diffa)
# the bins of the staggered sparsification array of max, num, of
weights that can be frozen within the given layer before the next-smallet layer gets involved into sparsification lims [np. dot (aux_vect vect [:k], nur W diffs((kk) for k in range rum [ayzs])
find in which bin nam_to_ freeze_tor falis this gives the number of layers to sparsify lim_val, lim_ind (nt Lims, num_to_"resze_tor
tors = =im
base fill: chunks of num. weights that are frozen in each involved layer until all involved layers have equal num. weights remaining ball_fill = [sun Wuum__difffa wafffflllnne flind:limiind: for lind in range iidiin)) base appendd))
the rest is distributed evenly over ail layers involved rest_tot nun_to_freeze_tot-ee (base_rill) rest int (mp. (rwst_tot/num http://mwnlaeer_____prrriiiiiiie num freeze :num layers ttweersst_ppprsiffl ar. (bale_fill) trest
sparsifyl
first layer gets the few additional frozen weights when rest_tot is
not evenly divisible by num pum_layee lateeaatto_sparrsee_____ssssssse to_sparsifyyyy mismatch
rest layers sparsiff nun_to_ nun_to_"reeze freze [0] rest_mi smatch

---

Published conference paper at ICLR 2021
assert sum (wwm_to_ (ou___to_freeee) = tttptuuntt_feeee_eeeeeee
return num num_tt__ _t__trezee
C SPARSITY DISTRIBUTION IN CONVOLUTIONAL LAYERS
The weight tensor of a convolutional layer has 4 dimensions: input, output, kernel width, kernel height. As discussed in section 2.3. when reducing network connectivity, remove weights randomly across all dimensions of weight tensor. A reasonable alternative for convolutional layers remove weights in the input and output dimensions only, leaving the kernels themselves unchanged. We test this approach on ResNet- 18 and find that it leads to very similar results in general. Specifically for smaller models, removing weights along all tensor dimensions results in better performance. For the smallest networks (base widths 8 and 12) and small connectivity, we observed gap up to 3% in test accuracy on both CIFAR datasets. Figure 9 shows results for CIFAR- 100, where the effect is more pronounced, for models with base widths 12 and 18 (1.8e5, 4.0e5 and 9.0e5 weights, respectively). Each experiment was repeated for 10 random seeds.
crunt
weights
0.72
f 1.8c++05
4.004405
9.0e+03
aecurac
0.70
0.68
0.66
0.0
0.1
0.2
0.3
0.4
0.5
connoctivity
Figure 9: Test accuracy achieved by ResNet-18 18 models on CIFAR-100, 100, comparing performance of sparse wide models of different size (number of weights indicated by color and printed in the legend) given sparsity distribution in the convolutional layers along all layer dimensions (filled circle) versus along input/output dimensions only (cross).
D SPARSITY DISTRIBUTION IN RESNET-18
On coarse level, the ResNet-18 architecture is as follows: one convolutional layer, followed by four modules, followed by one conle-connected layer; each module comprises two blocks, and each block contains two convolutional layers. The number of output channels in the first convolutional layer is the same for the first module, and the ratio of output channel numbers in the subsequent modules 1 : 2 4 8 we do not change this ratio in our experiments. When building a family of ResNet- 18 models, we vary the number of output channels of the first convolutional layer, and refer to this as the width of the model, while the widths of all subsequent layers are according the mentioned ratio.
When reducing the connectivity of ResNet-18 model, we remove weights from each layer according to layer size. More precisely, we first remove weights from the layer with the largest number of weights until it reaches the size of the next-smaller layer. We then proceed with removing weights from these two layers equally, and continue this procedure until the targeted total number weights in the network is achieved.
Figures 10 shows layer-wise sparsity distribution in ResNet-18 with 1.8e5 weights and various widths example.

---

Published conference paper at ICLR 2021
width 12
width 18
width 27 sparsity 90.99%
sparsity 55.01%
spansity 79.81%
conv1
layer1.0.comv 100.omv]]
layer1 1...om22
layer1.1.oogg 1.1oovvv
layer couvv
lsyer2.0.conv
layer2.0.conv2
layer2.0shorrteuu
leyer2.1.comg
leyer2.1.covv2
layer3.0.conv
13.
5000
layer3.0.corv2
86
72.
layer3.0.s l..re3...sbortent.
layer3.1.conv
9.6
735
2001
layer3.1.comg ccorv2
86
72A
layerd.f).oovv
leycr:.0.couv2
2254
03.2
90.3
Ayyrr...shorteet. 0
layer4.1 Lonv1
layer4.1 1onmv
2554
00.2
90.3
lincer
50
100
50
100
50
100
Sparsity (%)
Spansity (%)
Sparsity (%)
width 10
width 60
width 91 sparsity 99.20%
sparsity 95.88%
sparsity 98. 16%
conv
Dayer1.0.comv
56.4
72.0
8800
layer1 1.0.ou222
$6.4
720
28.0
layer Lconvl
layer 1.l.oonv2
720
1exer2.0.coovv
94.3
leyc:2.0.couvv
layer2.00hhorteuu..0
761
1.9er2.1.covv)
$3.9
1011
07.01
laycr2.1.coue
layer3.0.conv
91.9
94.3
layer3.0).comv2
16:3
10.33
(1
layer3.1.oovy
layer3.1.comr
18.5
10.33
layerd.0.convl
leyer1.0.conv2
$5.0
layer4. 0.4.0...oottut 0
01
00.5
layer4.1 convl
leyerd.1.oo 2oovv...covv2
35.0
lincar
7039
S1.1
x7.7
50
100
50
100
50
100
Spansity (%)
Spansity (%)
Sparsity (%)
Figure 10: Layer-wise sparsity distribution in ResNet- 18 of various widths with 1.8e5 weights, for the CIFAR-100 dataset.
ADDITIONAL HIGURES FOR RESNET-13 18 EXPERIMENTS
In this section show additional plots for ResNet-18 experiments Figures 11, 12, 13, and 14.

---

Published conference paper at ICLR 2021
SVHN
CIFAR-I0
CIFAR-I00
0.97
0.96
0.80
sunm weiggltte
1.le 07
0.96
0.94
0.75
aceuracy
4.4e-406
9.0e-400
0.95
0.92
0.70
1.0e+005
1.Se: 05
0.94
0.90
0.65
0.93
0.88
10a
10
10a
10"
widening factor
widening factor
widening factor
Figure 11: Same data as in Figure but with error bars.
SVHN
CIFAR-10 10
CIFAR-100
0.97
0.96
0.80
num.wcights
1.8e 05
accurac
0.96
0.94
0.75
4.0n++06
9.0e++115
0.95
0.92
0.70
L.le+07
0.94
0.65
0.93
0.88
0.60
10-3
10-2
10-1
16
10-3
10-2
10-1
10-3
10-2
10
10
connectivity
connectivity
connectivity
Figure 12: Same data as in Figure 6, but plotted as a function of network connectivity instead of width. Best test accuracy obtained by ResNet-18 models of different width (number of output channels of the first convolutional layer) and (total number weights, values indicated by marker color shown in the legend). The rightmost data point of each color (filled circle) corresponds to the dense baseline model (connectivity 1), all other data points (crosses) correspond to its wider and sparser variants. For smaller models (up 9.0e++5 weights), performance peaks at similar connectivity values.
explained improvemeent
weightts
aceuracy gap (%)
train accuracy (%)
84
*e num weights constant
2
1.00
0.50
80
widening factor
widening factor
Figure 13: The improvement in test accuracy due to widening, with constant or increasing number of weights. Data from the same experiments in Table 1.

---

Published conference paper at ICLR 2021
SVHN
CIFAR-10
CIFAR
1.00
1.00
sumn wei.weigttte
0.95
1.5e 06
0.98
0.98
aceuracy
4.0e-406
0.90
0.96
0.96
06
0.85
1.fe+06
0.94 X
0.94
Liee 107
0.80
0.92
0.92
0.75
0.90
0.70
10
10
10
10
2
10
10
10
10"
connoctivity
connectivity
connectivity
Figure 14: Training accuracy from the same experiments as in Figures 6 and 12. Larger models attain 100% training accuracy. For smaller models, the training accuracy shows similar behavior as the test accuracy: It increases up certain connectivity and then deteriorates when the connectivity decreases further.
F THEORETICAL DETAILS
this section we provide additional details on the theoretical analysis Section
Proof (Theorem 1). We begin by defining the integral
Ri,(z.u) = f d' II Pr(w)) =)(w v) Hww Hw v).
(5)
particular, for p = 1 we have the relation (x, Ki(z,y).
A straightforward calculation gives the following.
ki,(
Σ
Do (1 d)
(2To²)- / (der 1mmm (20 (w, x)) y) H - x)H(w, .v)
(6)
21
Σ
F0 (1-p) Si Ki(liss
(00.))
Here (S.,..., sa) is 0,1 vector of length d, Σ, Σd 8t, and w. (s) (1........ W.sa) is the vector with some elements zeroed out (x,, and ys are defined similarly). The integration over all the non-zero ws, namely dur, = [[ip= dw,.
Consider now the sparse kernel Ocp. is easy check that
1g|Oar v)] d K (=,,),))
(8)
Var(Ocp w)] d''m [2,((z))) (2,
Og be the dense kernel (with p = 1) width n, and let 0 lim, O be the dense wndtnite-width kernel. From (8) and (9)
that Eg ( K2 (z. y). and Oar y)] = 0. Using these results, mean square distance between the sparse and infinite- width kernels is now given by
Eg [OGr (2, (Gr v)) [Er[Orr(a (r. y)] O (a, 8)1² Var(OGr(2, g)]
(1,( (z, + dn
[ep(x, v) K v)
(10)

---

Published conference paper at ICLR 2021
F.1 APPROXIMATING THE KERNEL DISTANCE
Next, we derive the approximate form (4) by using plausible arguments. In this calculation we assume that dp > 1, and that z, y R are independent random vectors with elements sampled from (0 1). The derivation is not rigorous, but we compare the results against an empirical calculation in Figure& 8 and find good agreement when dp >> 1.
For given p we expect the dominant contribution to K₁ in the sum (7) to come from terms where Σg = E 8 =s pd, and so we consider a mask & with this property. We can then approximate 2, Vs dp and ||æu|| vdp(1 - 1/4dp) (and similarly for l1y)ll2)* * We denote by 0 the angle between and by 0g the angle between Is; Then, from the above we expect
E
sin O. 23 V
1 2dp
E
cos Og 23
O,
(II)
ddp
dp
2
ddp
where ç = 1 a random sign.
Next, we consider the integrals Ki v). We will rely on the following result from Cho and Saul (2009).3 For 2; y, Rdd,
1
/ dd ('we- 1111/222/2 x)(w 8) Hw x) (w v)
Ki(a.v)= =
(12)
(2m)
J((((,()
(13)
2x
T.y y
0(0.8/ 5) arceos
(14)
|x||b/|
(0) = sin 0 + (x 0) cos 0,
(15)
J2(0) = 3iin 0 cos 0 + (π 0)(1 + 2 cas" 0).
(16)
Using the random vector approximations, we find
dp
Ki (1 =
x [zllya|Ji
+
(17)
2T
2T
2d
1 12. (z.())
(dp)²
4
π
Kg(Ze18s)
(18)
2x
2T
2
dd
dp
((dp)3/2
3/2
sparse functions (1, y). we assume as before masks is concentrated where the mask M58; R dp. For a mask 8 obeying this condition we then have K1,( y) Re 2 K2 ( U.). In particular,
contribution from the sum over
T
1
(2,
14
(19)
2T
2
dp
2dp
d²
4
E
(2,(0,)) 8)
(20)
2T
2
ddp
dp
2(dp)3/2 3/2
We can also consider the diagonal elements, setting = y and 02 = = 0. We have ke, x)) R
2 Ki xz)
"dp(' 2n
[([-1)
J((0). In particular.
dp
(1, d
(21)
2
3d
2
12,
1
(22)
2
dp
'Here we used the fact that these are random vectors of effective dimension dp, and that for such vector
we have Ep ||==.111 [|6] 2//2 ((4+))/2)
T(d/2)
"The definition here factor of difference compared with Cho and Saul (2009).

---

Published conference paper at ICLR 2021
We are now ready derive the approximate kernel distance (4) from the exact relation (I). Using the approximations (19), (20), (21), (22), we end up with the following.
d
Eg (z O (z, w))
1
(23)
4d
4 vp
n²²
Eg -e
(2, x))
+ dp
(24)
n
We would like to find the minimum of the distance (23) when keeping the mean number of parameters with np constant. Assuming that the minimum at vp I, find that the minimum p.
np fixed. Roughly, we would like to minimize (1-1 1) + up
pa
(25)
4d


Reviews:
[{"review_id": "rvE4u8266Nk", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors analyze the enhancements brought by widening networks with the number of parameters fixed. From the experimental side, they conduct various experiments to compare the methods of widening the networks and demonstrate different ratios of widening different networks on diverse datasets. From the theoretical side, the authors relate the training dynamics of neural networks to kernel-based learning, in  the infinite-width limit. As a consequence, the authors claim that wider networks indeed improve the performance of algorithms under certain conditions.\n\nMy personal comments are listed below.\nPros.\n1. The idea of widening the neural networks with fixed number of parameters is novel and the authors conducts abundant experiments to support their assertions.\n2. The expressions and grammars are excellent.\n\nCons.\nI. Clarity Part.\n1. The authors spend much time and space to introduce linear and non-linear bottleneck methods to widening the neural networks with fixing the number of parameters, and, subsequently, prove the 2 methods are not qualified. From my opinion, since the authors have asserted that they try to avoid big adjustments on structure of the networks, the bottleneck-like methods are inherently excluded from the list. Meanwhile, the explanations for sparsity methods seems to be lack.\n\n2. While the authors provide meaningful and comprehensive plots to demonstrate the results of widening neural networks, the explanations and instructions of the plots and pictures are sometimes missing. For example, In figure 5, the trends of test accurarcy to widening factor are not always positive, some go down when the widening factors are big, others seems to be static. How do they happen? I think further explorations can be made.\n\n3. As for the theoretical side, the authors reference the NTK techniques (Jacot et al., 2018) to explain the relationships between the finite-width neual network and the kernel-based learning. However, NTK techniques are designed for infinite-width neural networks, and have constraints when applied on finite-width networks. As the authors assert, the synchronization of optimizations of 2 methods is only conjecture, which means the prove provide here can only be used to support the NTK theorems. Besides, the relationships between NTK and widening neural networks are not detailedly explained.\n\nII. Quality Part\n1. Figure 3, (b) has no horizontal baselines for traditional methods.", "extra_scores": {}, "extra_text": {}}, {"review_id": "6ZcIkx5Y0W3", "reviewer": "AnonReviewer2", "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": "Summary:\n\nThis paper analyzed the influence of neural network width on the network performances while fixing the total number of parameters. Specifically, the authors introduced several ways to change the model width without increasing the number of parameters, and showed experimentally that for widened networks with a random static mask on weights to keep the number of parameters, increasing the width can improve the performances of the models until the network become very sparse and hard to train. They author theoretically showed that for a not so sparse one-hidden-layer neural network, increasing width decreases the distance to the Gaussian Process kernel corresponding to the infinith-width limit, which partially supports their experimental findings.\n\nPros:\n\n1. Understanding the reason behind the generalization performance of neural networks is a very important problem, and the idea of decoupling the effects of network width and the number of parameters on the generalization performance is interesting.\n\n2. This paper is clearly written, well organized, and generally easy to understand. The figures in this paper are clear, and each figure was explained in detail. The methods/experimental settings are explained in detail, and the reasons why the authors use these models/methods are also discussed in the paper. The relationship to prior works has been clearly discussed.\n\n3. The experimental methodologies and theoretical computations appear to be correct.\n\nCons:\n\n1. The justification for this specific problem analyzed in this paper, i.e., fixing the number of parameters and changing the width, is a bit unclear. The number of parameters can be interpreted as a measure for the expressive power of the model, but this is not a very direct relationship because the expressive power is also related to other factors, e.g., the depth, the width, the choice and ordering of the layers. In the methods proposed in this paper, the authors were either changing the explicit number of parameters (e.g., linear bottlenetwork) or changing the expressive power of the network, which included other (perhaps unwanted) factors in this framework and could potentially influence the results. Details will be discussed in the next point.\n\n2. The definition of \"number of parameters\" is a bit unclear in this paper, making the problem that the authors want to analyze a bit vague. The authors didn't formally define it, but it is actually one of the core concept in this paper. The authors used three similar terms, i.e., \"number of parameters\"/\"number of tunable parameters\", \"effective number of parameters\", and \"expressive power\", in this paper. However, these three terms have slightly different meanings, and none of them is defined in this paper. From my understanding, \"expressive power\" is the set of all functions that can be reprensented by a model, and \"number of parameters\"/\"number of tunable parameters\" is a simple parameter count and can be used as a complexity measure of the expressive power, but \"effective number of parameters\" is kind of confusing. For instance, putting a low-rank constraint in Linear Bottleneck or using a sparse model actually changes the expressive power of the neural network but (claimed by this paper) does not change the \"effective number of parameters\". Due to the lack of formal definition of these three terms, I think the problem analyzed by this paper is not clear enough, making the points made in this paper unclear.\n\n3. The authors are explaining some of the experimental results in a very intuitive way without enough supporting evidence. For example, the authors said that Linear Bottleneck suffers from some \"implicit bias\", deleting weights from a sparse layer make optimization \"more difficult\", and small connectivity can hurt the \"trainability\" of the model. These terms are not formally defined or explained in detail, making the points made by the authors a little vague.\n\n4. The connection between the theory and experiments in this paper is a bit weak. People have observed that the performances of commonly-used neural networks always outperform their infinith-width limit, i.e., the corresponding infinith-width NTK. Therefore, in practical neural network models, simply decreasing the distance to the infinith-width limit may hurt the performance. Thus, I suspect that the explanation provided by the authors only works for some particular examples like small networks on MNIST.\n\nRecommendation:\n\nOverall, I vote for rejecting this paper. Although the idea of decoupling the influence of width and number of parameters is interesting, the problem analyzed in this paper is vague and a lot of terms used in this paper is not properly defined, making the arguments in this paper unclear.\n\nSupporting arguments for recommendation:\n\nSee \"Cons\".\n\nQuestions for the authors:\n\n1. Please address the cons mentioned above.\n\n2. For the experiments, I wonder whether you have done enough fine-tuning for the hyperparameters of each model and used the best test accuracy. Also, have you run each experiment multiple times or only once?\n\n3. I didn't understand why you do not consider the linear/non-linear bottleneck as an effective method. I think the goal is to analyze the effect of width but not to get a significant improvement on the test accuracy.\n\nMinor comments:\n\n1. Typo: Page 5, \"MLP\", paragraph 3, \"This results\" -> \"This result\"\n\n2. Page 5, paragraph 1, which model is \"the model with baseline width 8\"? Is it the model with the number of parameters 1.8e+5?", "extra_scores": {}, "extra_text": {}}, {"review_id": "3YYBqhVLdZ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 manuscript provides an intriguing discussion on the different roles that the width and parameter size could play in a neural network. While these two aspects are traditionally treated as -if not identical- correlated, the authors managed to develop a couple of configurations to decouple and analyze both separately. Especially the wide and sparse approach could be a new way to design neural networks that are supposed to be small and expressive at the same time. \nI'm only concerned about two aspects: i) The section 3 could have been perhaps easier to follow if the work by Jacot et al. 2018 had been briefly recapped. ii) The experiments are all conducted on image dataset. One might wonder whether we could draw the same conclusion for datasets of more general nature. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper investigates the interesting question whether increasing the width or the number of parameters is 
responsible for improved test accuracy. The paper is very well written and the question is novel and innovative.
From a methodological point of view, the experiments are well conducted, too.
The theoretical part of the paper is somewhat detached from the experimental part and constitutes more of
a heuristic conjecture. In addition, more experiments on a variety of other data sets would have been great.
Ideally, the theoretical section would thus be replaced by such additional experiments, but this is of course not 
an option for a conference reviewing system.
Given the innovative question and well-conducted experiments I think that the pros outweighs the cons,
and for this reason I recommend to accept the paper. Reviewer concerns have been well addressed by the authors in their rebuttal and updated version of the paper.
Decision: Accept (Poster)