NeuroFabric: Identifying Ideal Topologies for Training A Priori Sparse Networks
Authors: Mihailo Isakov
Michel A. Kinsy
Venue:  (2020)
Keywords: Sparsity
model compression
training
topology

Abstract: Long training times of deep neural networks are a bottleneck in machine learning research. The major impediment to fast training is the quadratic growth of both memory and compute requirements of dense and convolutional layers with respect to their information bandwidth. Recently, training `a priori' sparse networks has been proposed as a method for allowing layers to retain high information bandwidth, while keeping memory and compute low. However, the choice of which sparse topology should be used in these networks is unclear. In this work, we provide a theoretical foundation for the choice of intra-layer topology. First, we derive a new sparse neural network initialization scheme that allows us to explore the space of very deep sparse networks. Next, we evaluate several topologies and show that seemingly similar topologies can often have a large difference in attainable accuracy. To explain these differences, we develop a data-free heuristic that can evaluate a topology independently from the dataset the network will be trained on. We then derive a set of requirements that make a good topology, and arrive at a single topology that satisfies all of them. 

Under review as a conference paper at ICLR 2019
NEUROFABRIC: IDENTIFYING IDEAL TOPOLOGIES FOR TRAINING A PRIORI SPARSE NETWORKS
Anonymous authors Paper under double-bling review
ABSTRACT
Long training times of deep neural networks are bottleneck in machine learning research. The major impediment fast training is the quadratic growth of both memory and compute requirements of dense and convolutional layers with respect their information bandwidth. Recently, training 'a priori' sparse networks has been proposed as method for allowing layers to retain high information band- width, while keeping memory and compute low. However, the choice of which sparse topology should be used in these networks is unclear. In this work, we provide theoretical foundation for the choice of intra-layer topology. First, we derive new sparse neural network initialization scheme that allows to explore the space of very deep sparse networks. Next, we evaluate several topologies and show that scemingly similar topologies can often have a large difference in attain- able accuracy. To explain these differences, we develop a data-fre free heuristic that can evaluate topology independently from the dataset the network will be trained on. We then derive a set of requirements that make a good topology, and arrive at single topology that satisfies all of them.
INTRODUCTION
Training deep neural networks requires both powerful hardware and a significant amount of time. Long training times are a significant bottleneck deep learning research, researchers typically iteratively design and test new architectures for specific problem. While a lot of research has been dedicated to accelerating inference, we investigate training as (I) accelerating training can speed up research iteration, (2) evolutionary algorithms for DNN architecture exploration are increasingly being used as an alternative domain expertise (Jaderberg et al. 2017). and network training is moving to edge devices (Pirk et al., 2019). Unfortunatelly. the memory requirements, of dense, convolutional and recurrent layers grow quadratically with layer information bandwidth] [ other words, doubling the size of layer inputs and outputs quadruples the size of the layer. This causes making DNN training impractical without batch- ing, a method where training is performed on multiple inputs at a time and updates aggregated per batch. While batching alleviates the pressure on DRAM bandwidth, it can decrease model ac- euracy (Masters & Luschi 2018) especially when scaling training on large clusters (Akiba et al. 2017 Furthermore, larger models in off-chip memory become dominant energy cost (Han et al.
majority of the networks to be memory-boume
2015a), complicating on-line training on aattery-power devices.
Conventional dense and convolutional layers do not offer the user to individually tune layer size and the number of layer inputs and outputs. In this work, we seek a method to decouple the information bandwidth from layer expressivity. Such a method would allow us to (1) speed up training networks by storing them in on-chip memory, (2) remove the memory bottleneck and the need for batching, (3) allow more efficient training on distributed systems, and (4) reduce the energy consumption due to the excessive compute and storage requirements of modern DNNs, potentially allowing us to move training to edge devices. Several works have proposed a priori structured sparsity (Prabhu al., [017]] Isakov et al. (208)) or weight sharing (Ding et al.) (017) to allow training simpler but "wider" models. A priori sparsity, where the sparse network topology is selected before training has started, is a promising approach that allows the user to finely and transparently tune the ratio of information bandwidth to memory requirements. If the topology is structured, efficient software
We define layer's information handwidth the number of independent signals passing through that layer.

---

Under review as a conference paper at ICLR 2019
or hardware implementations can be built to accelerate processing with dense network performance However, before custom architectures or low-level kernels can be built, a general theory of why certain topologies perform underperform is needed. To the best of our knowledge, no work yet tackles the question of the existence of a 'best' topology for sparse neural network training. This paper provides answer how a topology should be selected.
Our contributions are as following:
We propose sparse cascade architecture that can replace dense or convolutional layers without affecting the rest of the network architecture.
We develop a sparse neural network initialization scheme that allows us to train very deep sparse networks without suffering from the vanishing gradient effect.
We evaluate sevaral topologies on matrix reconstruction task and show that the choice of topology has a strong effect on attainable network accuracy.
In order evaluate topologies independently of dataset, we develop data-free heuristic for predicting the expressiveness of a given sparse network.
From the heuristic, we derive requirements that make a good topology, and settle on a single family of sparse networks.
2 RELATED WORK
We classify methods that arrive at sparse network into those that enforce sparsity before, during, or after training. The following a brief description of each class.
Enforcing sparsity after training: In this class of methods, certain weights are zero-ed out after training has finished. This approach has the benefit of first discovering the baseline model accuracy, allowing the training mechanism to evaluate the accuracy size trade-off. Since training is per- formed using the dense model, only inference can benefit from these post-training pruning methods. One of the early pruning methods are Optimal Brain Damage (LeCun al. 1990) and Optimal Brain Surgeon (Hassibi & Stork 1993), where authors remove weights based on the second derivative of the loss w.r.t. each weight. The insight here is that removing a weight causes some perturbation in the network, and by picking weights with the smallest second derivative of the loss, the effect of the perturbation on the network functionality be minimized. DeepCompression (Han et al. 2015a uses a similar approach, but replaces the Hessian-based metric with weight magnitudes. Authors show that high (>95%) sparsity can be achieved as long as networks are finetuned after pruning to restore performance. Alternatively, in (Liu et al. 2015) authors decompose convolutional layers into a set of per-channel basis kernels, which are applied to input feature maps, and a sparse kernel matrix that mixes outputs of the basis kernels into the output feature maps. However, all of these methods lead to unstructured sparsity that is difficult to take advantage of. Structured sparsity, where some assumptions can be made on the structure of sparse kernels, has been explored as way to improve the execution efficiency of sparse structures on GPUs and CPUs. In (Anwar et al. 2015). authors use particle filters prune whole channels kernels. Similarly, Kadetotad et al. explore structured intra-layer sparsity, where instead of individual weights, small blocks of weights are pruned.
Enforcing sparsity during training: Instead of pruning after training, pruning can also be applied during training. This has the benefit of potentially reducing the computational load of the training phase, however, the device performing training must still be able store the whole dense model at the beginning of training. L1 regularization or L1 weight decay is known to cause sparsity dur- ing training, as unlike the case of L.2 regularization, all weights will equally be incentivized to approach zero. However, LI weight decay often causes decrease in accuracy, and the sparsity is unstructured. In (Wen et al., 2016), authors use Group Lasso (Yuan Lin 2006) regularization to enforce the sparsity of more coarse-grained structures instead of individual weights.
Enforcing sparsity before training: Model size can also be reduced before training has started. We focus on layer-level methods and not architecture level approaches, they are orthogonal. Majority of works reducing the size of layers before training have focused either on a priori sparsity or weight reuse. On the weight reuse side, HashedNets (Chen al. 2015) use a hash function to group multiple weights and have them share and train a single value. CirCNN (Ding et al., 2017) uses block-circulant matrices for storing weights, where elements are shared in predictable manner and
2

---

Under review as a conference paper at ICLR 2019
Fourier transforms used for inference, reducing the computational complexity of both inference and training.
On the priori sparsity side, several topologies have been proposed in literature. Deep Expander Networks (X-Nets) (Prabhu et al. 2017) replace dense layers with sparse layers with the expander graph topology. Authors give guarantees of each input neuron being connected to each output neuron within a logarithmic number of layers. Similarly, RadiX-Nets (Robinett & Kepner 2019) build on X-nets but use the radix topology instead of graph expanders. Alternatively, ClosNets (Isakov al.) 2018) replace single dense layer with a cascade of three sparse layers with the Clos topology. Clos topology guarantees full connectivity, and has a tunable parameter for the path diversity between all inputs and outputs. While deep expander networks grow in depth with the number of neurons per layer, ClosNets grow width.
None of the above a priori sparse network works give definitive answer to which topology maxi- mizes performance per weight. In this work we aim to answer that question.
3 APPROACH
The number of parameters in a neural network layer is decided by the number of input and output neurons (in case of fully-connected networks), the number of input and output channels (in the case of convolutional networks). This prevents decoupling the network bandwidth (i.e. number of inputs or outputs of a certain layer) and the parameter count. We propose that sparsifying layers can allow users to train wider networks without the quadratic growth in network size. Our approach is to replace each fully-connected layer with a cascade of sparsely-connectee layers, as shown in Figure[] The cascade topology and depth are selected at design time that the number of parameters in the cascade is lower than in the original dense layer. Hidden layer neurons in the cascade have linear activation function, while the output neurons the activation of the original network. The cascade needs to have certain properties such as connectivity between cascade input-output pairs, a small we explore the topology requirements further.
parameter count, and hardware efficiency. In Section 7
ReLU
Linear
ReLU
Linear
Sigmoid
Sigmoid
Dense
Dense
Sparse Cascade
Sparse Cascade
Figure 1: A 2-layer dense network replaced with two 3-layer sparse cascades. Cascades use linear activation functions in their hidden layers, and original activations their outputs.
Similarly, priori pruning can be applied convolutional networks. conventional CNN layers, each input channel is connected to each output channel by a convolution. For a filter of size f x f. e input and l output channels, the convolutional layer has f2c parameters. Since the number of input and output channels e and i directly control both the information bandwidth and the size of the network, we propose to disentangle the number of input/output features and the number of convolutional filters. We adopt the architecture of MobileNets (Howard et al. 2017) and break up convolutional layers into depthwise and pointwise convolutions, as seen in Figure 2a In the original MobileNets, the majority of parameters belong the pointwise convolutions, which simply dense neural networks applied to each 'ixeel' individually. We propose to prune only the pointwise convolutions in the same manner prune dense layers.

---

Under review as a conference paper at ICLR 2019
inppt feature maps
en intermediate maps
output Jeature maps
15 63
16
64
80
Layers
6
-70
60
10
-50
14
30
18
20
10
Sparsity
depthwise separable convolutions per channel
Clayers of sparse 1x1
convolutions
A priori sparse convolutional layer.
(b) Accuracy MNIST.
Figure 2: (Left) Decomposition of convolutional layer into a single depthwise and a cascade of sparse pointwise convolutions. (Right) Accuracy of sparse linear networks with varying depth and sparsity on the MNIST dataset.
4 INITIALIZING A PRIORI SPARSE NEURAL NETWORKS
Initializing deep neural networks highly affects the training accuracy of the models, but is often not given much attention network architecture. If network is suboptimally initialized, it may train slower than correctly initialized one or may even not train all. This problem has been extensively researched in the context of deep neural networks (Glorot & Bengio, 2010 He al., 2015a) and recurrent neural networks (Henaff et al. 2016). Our proposed approach replaces fully-connected layers with cascades of sparse layers. As such, the new network may be several times deeper than the original one, and may not train as efficiently. This problem is further compounded by the fact that networks priori sparse. Our tests show that deep sparse networks initialized with common initialization schemes like Xavier initalization (Glorot & Bengio, 2010) completely fail to learn. By observing the activation and error values of deep sparse networks, deduce that these networks suffer from the vanishing gradient problem, i.e., with each successive layer, the variance of both the activations and the errors drops exponentially. this section, develop a new initialization scheme for priori sparse networks that alleviates the vanishing gradient problem by taking layer sparsity into account.
4.1 SPARSE XAVIER INITIALIZATION
In Appendix A we briefly cover the original derivation of the Xavier initialization. Here gener- alize it to apply to sparse networks as well. We construct a sparse layer from matrix W E mxx by multiplying element- wise with the mask M {0, 1 jm with sparsity [0, 1]. For dom topology, each element My of the mask set as Mij = Ber(s), where Ber is the Bernoulli distribution. For layer W. with Nin input and nout output neurons, output neuron's 's activation variance depends on the variance of each input neuron, each weight connected to it, and the number of input neurons (Appendix Equation 21). For sparse networks, each output neuron is on average only connected to nan 8) neurons, hence we update Equation 21
(a(an)1) nin (1 (a)² (Wn+1) o2(8") = nout (1- s)- (6n+1)0 (Wn+1)
Updating the Xavier initialization take sparsity into account, we write our sparse initialization as: V6
W ~ U u[-
V6
(nz + (1 V(n, + 1)+1)
We test the new initialization on the MNIST dataset with networks of different sparsities and depths (Figure 2b). We train randomly-connected networks with 256 neurons in the hidden layers, 1 to 20 hidden layers, and with sparsities between 0 and 255/250 /566 Using the sparse Xavier initialization, we able to train deep sparse networks. For very sparse networks (sparsity of 63/64 and higher), often there exists no path between certain inputs and outputs, limiting trainability. better, non-random topology with the same amount of parameters may however be able train.
4

---

Under review as a conference paper at ICLR 2019
5 TOPOLOGY EXPLORATION
The choice of topology has strong impact on both the accuracy and the parallelizability of sparse network. In this section we aim to (1) answer how two topologies can be compared, and (2) create a metric for evaluating topology independently of task, given that we can assume nothing about training data beforehand. We first devise a task that allows us to experimentally evaluate a topology. We choose a matrix reconstruction problem where an original matrix Wo R is reconstructed as product of I sparse matrices S; E R with adjacency matrices M; E [0. 1j as:
L(Wo, MI.... Mi) min Wo (S, o (OSOMM)
The matrix Wo must be random, so that the network cannot abuse any regularities within it. The topology we seek should perform well independently of the matrix structure. Though topologies derived for a specific task may perform better, on average across all tasks, the general topology should achieve the best results. number of loss functions can be used for this evaluation but restrict ourselves to L2 loss for now. To gain intuition into the problem, we use the reconstruction loss in Equation on number of common topologies. Figure illustrates the impact of topology
Loss
10-2
Hypercube
Butterfly
Clos
Torus
Rank
Dense layer parameters
10-1
10000
20000
30000
40000
50000
60000
70000
Parameter count
Figure L2 loss of networks with different topologies and varying depths.
choice overall network accuracy. Our reasoning is that as topologies can underperform an unseen task, there exists a 'best' topology, one that on average achieves optimal performance. In this and the following section we aim find that topology.
Though we may arrive at an optimal topology purely through evolution, this approach has several issues: (1) evaluating topology random matrices is inherently noisy, and we would have to reconstruct many random matrices in order to compare the fitness of two different topologies, (2) the evolved topology is only point solution, and would have rerun the process for topology with a different number of inputs, outputs, parameters, or layers, and (3) the evolved topologies tell us nothing of the underlying reasons for why a certain topology is underperforming. Therefore, aim to develop a heuristic that can accurately predict the quality of a topology, so that by analyzing the heuristic we can arrive at the root cause of why certain topologies are underperforming, and produce conclusions on how to construct better performing ones.
5.1 LO CONSTRAINT SATISFACTION
We revisit Equation 3 and define the sparse decomposition Wa as:
W. = I
S o M
(4)
5

---

Under review as a conference paper at ICLR 2019
From here write an individual element Wai of matrix Wa from Equation by looking paths between input and output j as:
P(a.)) Wass Σ
P
II
Wmn
(5)
P
Cann
Ep
where P(i,j) ) is the set of all paths from imput neuron i to output neuron j. According to Equation 5 in order satisfy Wo Wa i.j, at least one edge in P(i, must be a specific value. Given an edge Cwn with weight Wnan that exists on some path between nodes i and j:
Wmn (Wo
P(L.)
P 1
)
P().5)
Pleme
WooLs
Σ
Σ
II 6x
Wry Eau
Way
P. Cmrn EP
Pyemun Ep
Due to the difficulty of analyzing the quality of topologies using an L2 loss, one approach is to use LO loss. Here, we task the matrix decomposition Wa with perfectly reconstructing as many individual elements of Wo as possible. The networks are still trained using SGD with LI loss. After training converges, we can count the number elements in Wo Wa where IWo Wa < for some arbitrarily small E R. As Wma cannot take multiple values, it can only satisfy a single constraint. Therefore, if Je] is the number satisfiable constraints, we can say that 0 < |Caar| < lel. At best, the topology can solve as many constraints as it has edges. As we will show in Section 7 this is not possible to achieve without several modifications to the sparse network.
edges in the network, and [Ceat] is the number of
Equation B allows us to reframe the problem of finding the minimal LO reconstruction loss as a bipar- tite maximal matching problem. First, create set of onput-output constraints C {(i, | T, E O), and a set of weights W- = {(w), }) Mii = 1}. An edge w E W is connected to all constraints (i, o) E where w E P(i, o). The problem of finding the largest number of elements in Wo that can be perfectly reconstructed by Wa becomes bipartite maximal matching problem, and can be solved in linear time. However, we find that the maximal number of constraints matched with edges is not a good heuristic for the performance of topology. Constraint satisfaction counting heuristics fail to account for topology fairness, and equally rate topologies that balance the satisfac- tion of all input-output pairs, and topologies that greedily satisfy only a subset of input-output-pain
GRAPH CONTROLLABILITY
In this section, we present a continious method of evaluating the capability of a topology to recon- struct a certain graph. While averaging reconstruction results many random matrices may provide an estimate of a topology quality, we develop data-free approach that (1) evaluates a topology in single pass, and (2) is not sensitive to the randomness of generated matrices.
6.1 NEURONS NEED ONLY LEARN INPUT RATIOS:
In this work focus networks that use ReLU activations between sparse cascades, and linear activations inside them. Both ReLU and linear functions are homogenous, i.e. f(cr) = (x)
for constants e R. Take a neuron with activation a and n inputs with activations and weights z, w E R", Activation a can be written as:
a = f(wz)
where f is homogenous function. We can extract the magnitude and normalize the vector w:
mvz) mv, ||v112 =1
Since the neurons using homogeneous activation functions, can shift the job of learning neuron magnitude to the next layer. Now the neuron is only tasked with learning the input ratios.
In the previous section we have used LO loss to measure the number of constraints network can solve. Here we see that for m X n constraints that exist when reconstructing a matrix W E R n of those constraints are magnitude constraints, and (m 1)n ratio constraints. In other words, neuron with m inputs has m ratio and magnitude constraint. In Appendix we give a practical way of eliminating magnitude constraints and only measuring the number of ratio constraints.

---

Under review as a conference paper at ICLR 2019
6.2 NEURON CONTROL
We define controllability of certain neuron n w.r.t. to an inputs and b as the ability of an optimizer the ratio of to b We give an inductive definition on three graph primitives: (1) individual input neurons, (2) neuron with two inputs and one output, and (3) neuron with one input and two outputs, and show how controllability propagates through them. We show how any sparse neural network can be decomposed into these primitives and how control can be calculated on neurons with larger numbers of inputs and outputs.
Definition 6.1. For neuron n connected to a set of inputs I, we define the controllability of imput E I relative to E 1 at Cafb(n). If (f))))()) 1 1, the optimizer can set the ratio a neuron n to any value, without impacting any other ratios already set in the network.
Lemma 6.1. For inputs a, b E I and any neuron n, controllability Cafo(n) is bounded as:
0 S Ca/b(n) + Cbfa(n) S
This is understandable since the optimizer can only set the ratio of inputs and b at neuron to single value, hence controllability of a to b plus controllability of cannot be greater than Lemma 6.2. For input neurons a, b, c II, controllability of ratio a/b at neuron e is:
Cafo(c) =
(10)
This is obvious since optimizer has no control over network inputs, and we will use this lemma as the base case of our induction.
Lemma 6.3. For an neuron connected to a set of inputs I,, total controllability of n is limited as:
ΣΣ (n) s |I| -1
(11)
This lemma a direct result of Section 6.1 limit on the number of ratios.
We now analyze two graph primitives that show how control propagates through the graph.
Theorem 6.4. Control aggregation: For neuron with two input neurons i and connected with weights Win and Wyn, where I, and II are the sets of inputs directly or indirectly connected to neurons i and j. the controllability Cajo(Ti,, a,b Uli is:
Cafo(n) min(1, max(0, (Cafb(1) + Cafoli) ACo,o(1))))
(12)
where
Σ (C) < 0, neither win Win. tunable least one of the weights tunable
(13)
Intuitively, neuron n inherits the controllabilities of inputs and j. and if at least one weight is tunable, can additionally control the ratio between the two input neurons. This allows it to set an additional ratio between any of the inputs in L, U Ml.. If the loss function is quadratic, instead of using this additional ratio to solve single constraint, the optimizer may want to partially satisfy multiple constraints. Hence, we allow added controllability AC.,/ to have a value in [o. 1]. Notice
that ACa, values in AC. In corollary C.O. we extend this Lemma for the case where has multiple inputs.
(1) abides by Lemma 6.1 and (2) the optimizer can tune all [T, U UT₁12 individual
Theorem 6.5. Contral fannout: For neuron and two output neurons and y connected with constant connections such that n = T. = y, x and y controllabilities Cafo(x) and Cafoly) abide by:
Ya, b II, Capo(z) + Cafb(y) Cafb(n))
(14)
In other words, neuron n's control is split across outputs. The optimizer chooses how best to split this control, i.e,, it does not have to be fair, In Appendix we show how graphs can be decomposed so that apply Theorems 6.4 a.5

---

Under review as a conference paper at ICLR 2019
Corollary 6.5.1. For neuron with set of outpur neurons O fa1 ... Iib connected with constant connections, output neuron controllabilities Cays(ry) abide by:
Va, EI,
Coob((e)) CCap(()
(15)
We can reframe Equation 15 using trainable ratios:
Ya, E I, Vxz
E D,
Ca/o(1zz) =nab((1)
(16)
10
Va, b E II
Σ (abs(n) =1, 0 S Taby(n) $
(17)
6.3 TRAINING CONTROLLABILITY
Finally, decompose the sparse cascade's topology that apply Theorems 6.4 and 6.5 in order to write out the equations for the controllability of each output neuron with respect to each input neuron.
Take a cascade with L layers. Each layer has |n'l sparsely connected neurons, with (n being the number of cascade inputs, and In'I being the number of cascade outputs. We define layer I controllability tensor C' [0, 1]mo 1] as a tensor where the element C C. represents neuron
ni 's control over ratio n2/nn.. The added controllability tensor AC [o, 1]m0x= x xnl represents the added controllábility added by the tunable connections between layer 1 and 7 + 1, as per Theorem 6.4 The element A A.C.j... represents the additional control over i/j provided by
the edge between n'n, and nkk I+1 Each tensor A.j...m abides by Equation 28 The ratio tensor
R' E [0, 10 x x represents the control split from Equation 16 with R.j.A.m representing
the portion of controllability (n/)(nim) passed on to Cits(mk, ).
We can propagate controllability through the network as:
c = C' R' Σ A.C.j.m
(18)
172
where the operation is defined as:
X B
R
Roj.j. Ci.j. Ri.j.k.
(19)
The controllability tensor C, added controllability tensor AC and ratio tensor still have to abide
by constraints in Lemmas 6.1 6.2 and Equations 1 I6
n4n is the number cascade inputs, we define the controllability loss as:
L(C²) ((
(20)
i.e. if certain neuron output ie has control over 7ki ratios, that neuron's 's loss We can now minimize this loss to discover how much control each cascade output has over the cascade inputs.
7 DERIVING BETTER TOPOLOGIES
In this section, we analyze the results of the controllability heuristic and answer (1) how topologies can be improved on the matrix reconstruction task, and (2) if there exists a definitive answer to what topology performs the best.
7.1 THE NEED FOR SKIP CONNECTIONS
Similar to skip connections used ResNet networks (He et al. 20156), we propose that skip connec- tions in can significantly improve the performance of sparse cascades, though for different reason.
8

---

Under review as a conference paper at ICLR 2019
As mentioned in Section 6.1 if network uses homogenous activation functions, each neuron only needs to learn the ratio of inputs at that neuron, as the job learning the magnitude can be shifted to the layer above. Since the number of learnable ratios at neuron is one less than the number of inputs of the same neuron, that neuron does not need to have all of it's connections trainable. One of the connections
have constant value of 1, and the network performance will not be impacted. This effect is particularly noticable in butterfly networks, where each neuron only has 2 inputs and 2 outputs, hence 50% of connections are wasted. We replace one connection per neuron with skip connection valued at I, and show their performance in Figure 4 See that skip connections significantly improve the performance of butterfly and hypereube networks.
10
L2 Loss
10:2
Hypercube
Butterfly
Clos
Torus
Low Rank
Parallel Butterfly
Dense layer parameters
10-2
10000
20000
30000
40000
50000
60000
70000
Parameter count
Figure 4: L2 loss of networks using skip connections
7.2 THE NEED FOR INPUT-OUTPUT PAIR EQUALITY
While skip connections help topologies achieve similar performance (see hypercube and butterfly in Figure 4. some topologies still outperform / underperform. We turn to our controllability heuristic for an explanation of this behavior. We train our controllability network from Section 6..3 with topologies from Figure 4 The trained network produces C²,, the controllability tensor of the last layer of the network. This 3D tensor where Cl specifies the optimizer's control of input ratio n//nnj at output neuron n Since we optimize for the number of ratios set, and not the specific configuration, we sum O in the second dimension with KL Ct We plot the resulting K matrices in Figure (a-d).
1.0
0.
0.4
02
0.0
(a) Hypercube
(b) Clos
(c) Butterfly
(d) Torus
Figure 5: Controllability matrix K after 1000 training iterations. All networks have 32 inputs and outputs, and 1152, 1152, 1152, and 120 edges, respectively. Clos router configuration (8, 9, 8), hypercube has layers, butterfly has 18 layers, and the torus has 8 rows and 4 columns.
The total controllability a network achieves is equal to the sum total "brightness" of (ag) With skip connections and topology that does not oversaturate certain input-output pairs, we can guarantee that the number controllable ratios is equal to the number of trainable edges in the graph. Notice that the hypercube and torus figures have significant variance, while Clos and butterfly networks are smooth. This means Clos and butterfly networks do not prioritize any specific input-output pair. Since torii and hypercubes world networks (Watts Strogatz 1998), these networks find easier to satisfy closer input-output pairs. Even though these networks trained with 1.2 loss, where outlier pairs incentivized
and can interpreted as the
examples of small-

---

Under review as a conference paper at ICLR 2019
to approach the mean, torus and hypercube networks show signifcant vraiance. This is important since when given a matrix Wo which is to be reconstructed, permuting Wo columns or rows in targeted way may improve reconstruction accuracy. Ideally, the position of an input within the topology should not impact the performance of the network. In Figure S we give four examples: hypereubes whose controllability matrix has high mean and high variance, Clos with high mean and low variance, butterfly with low mean and low variance, and torus with low mean and high variance.
7.3 THE NEED FOR SHALLOWNESS
Saxe et al. 2 explore the dynamics of training deep linear networks, and show that deep linear networks have at most a constant time slower convergence compared to shallow linear networks. This effect (1) may still be detrimental to training, and (2) to the best of our knowledge, has not been studied for the case of sparse deep linear networks. Hence, when choosing between two otherwise equivalent topologies (i.e., topologies with the same controllability mean and variance), we should choose the shallower one. Furthermore, observing Figure 3
that after certain depth, butter- fly. torus, and hypercube networks lose performance with depth, despite gaining parameters. This is likely due to issue with initializing very sparse deep networks, as sparse random initializations may be more vulnerable to noise compared to dense networks. On the other hand, constant-depth topologies such as Clos (with depth 3) and low rank (with depth 2) eventually outperform all other variable-depth topologies. Similarly, our ideal topology should have constant depth.
7.4 THE NEED FOR HIGH INFORMATION BANDWIDTH
In Figure 4 we notice that for small parameter counts, the Clos topology is outperformed by both butterflies and hypercubes. By analyzing the controllability matrices of low-parameter Clos net- works, we see that this behavior stems from the limited information bandwidth of Clos networks. In Figure Sa we show an example of a Clos network that underperforms due to limited bandwidth.
7.5 ONE TOPOLOGY TO RULE THEM ALI.
We evaluate different topologies with the above criterions. namely: (I) a topology should use skip connections, (2) the controllability matrix of a topology should have no variance, (3) the topology depth should not change with the number of parameters, and (4) the topology should have high information bandwidth, independent of the number of parameters. All of the above topologies can satisfy constraint (1) given skip connections, however, only Clos and butterfly satisfy constraint (2). Since butterfly, hypercube and torus topologies grow depth as the parameter budget grows, while Clos grows in width, only Clos satisfies constraint (3). However, while butterfly, hypercube, and torus satisfy requirement (4), Clos does not. Hence, we propose a topology we call parallel butterfly, which satisfies all of these constraints. Parallel butterfly consists p butterfly networks of maximum depth d, where d is a metaparameter selected ahead of time. All p networks are connected to the same inputs, and sum their outputs. With a small number of parameters at it's disposal, the parallel butterfly sets = 1, and grows in depth up to d layers. Afterwards, it grows in width by increasing the parameter p. In Figure we show that parallel butterfly outperforms all other topologies. In Appendix Figure 8b we give an example of parallel butterfly topology where p = 2.
8 CONCLUSION
In this work, we have explored accelerating DNN training by pruning networks ahead of time. We proposed replacing dense and convolutional layers using sparse cascades with topologies selected ahead of time. We presented an a priori sparse neural network initialization scheme that allows us to train very deep networks without the vanishing gradient problem. Since networks are pruned before the model has seen any training data, we investigated topologies that maximize accuracy over any domain. We have developed a data-free heuristic that can evaluate the sparse network's 's control of outputs with respect to inputs, allowing us to assess the expressiveness of given topology. We have extracted several requirements that make for a good topology. such as the need for skip connections, information bandwidth, shallowness, and onput-output pair equality. Finally, we have proposed topology we call parallel butterfly as the ideal topology for training a priori sparse networks, and have experimentally shown that it outperforms other considered topologies.
10

---

Under review as a conference paper at ICLR 2019
REFERENCES
Takuya Akiba, Shuji Suzuki, and Keisuke Fukuda. Extremely large minibatch SGD: training resnet- 50 on imagenet in 15 minutes. CoRR, abs/171 2017.
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural networks. CoRR, 15200151.. 2015.
Wenlin Chen, James T. Wilson, Stephen Tyree, Kilian Q. Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. CoRR, has/1554.04788. 2015.
Caiwen Ding, Siyu Liao, Yanzhi Wang, Zhe Li, Ning Liu, Youwei Zhuo, Chao Wang, Xuehai Qian, Yu Bai, Geng Yuan, Xiaolong Ma. Yipeng Zhang, Jian Tang, Qinru Qiu, Xue Lin, and Bo Yuan. Cirenn: Accelerating and compressing deep neural networks using block-circulant weight matri- ces. Proceedings of the 50th Annual IEEE/ACM International Symposiun on Microarchitec- ture, MICRO-50 17, pp. 395-399---01 408, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4952-9 doi: 10.11445/1233393312244
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth Interna- tional Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. CoRR, abs/1511 ht///11100019999 149,00014,,0000 2015a.
Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural networks. CoRR, Abs/1506.00222 2015b.
Babak Hassibi and David G. Stork. Second order derivatives for network pruning: Optimal brain surgeon. In S. J. Hanson, J. D. Cowan, and C. L. Giles (eds.), Advances in Neural Information Processing Systems 5, pp. 164-171. Morgan- Kaufmann, 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. CoRR, abs/1502.01882, 2015a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CoRR, abs/15 htt/1512.03388. 2015b.
Mikael Henaff, Arthur Szlam, and Yann LeCun. Orthogonal rnns and long-memory tasks. CoRR, abs/ bbbs/6022.0662. 2016.
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications. 2017. ISSN 0004-6361. doi: arXiv: 100.:1404.8861
Mihailo Isakov, Alan Ehret, and Michel A. Kinsy. Closnets: Batchless dnn training with on-chip priori sparse neural topologies. 2018
Max Jaderberg, Valentin Dalibard, Simon Osindero. Wojciech M. Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, Iain Dunning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukcuoglu. Population based training of neural networks. CoRR, htt/1711.098444 2017.
Deepak Kadetotad, Sairam Arunachalam, Chaitali Chakrabarti, and Jac-Sun Sco. Efficient Memory Compression in Deep Neural Networks Using Coarse- Sparsification for Speech Applica- tions. doi: 10. 111111///6668862977777 2967008
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In D. Touretzky (ed.), Bargan-Kaufmang 1990.
Advances in Neural Information Processing Systems 2, pp.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse convolu- tional neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 806-814, 2015.
11

---

Under review as a conference paper at ICLR 2019
Dominic Masters and Carlo Luschi. Revisiting small batch training for deep neural networks. CoRR, abs/1804.07612,, 2018.
Sören Pirk, Mohi Khansari, Yunfei Bai, Corey Lynch, and Pierre Sermanet. Online object represen- tations with contrastive learning. CoRR, abs/1906.04312, 2019.
Ameya Prabhu, Girish Varma, and Anoop M. Namboodiri. Deep expander networks: Efficient deep networks from graph theory. CoRR, abs/1711.08757, 2017.
Ryan A. Robinett and Jeremy Kepner. Radix-net: Structured sparse matrices for deep neural net- works. CoRR, abs//905. 9099000556.66 2019.
Andrew Saxe, James Mcclelland, and Surya Ganguli. Exact solutions the nonlinear dynamics of learning in deep linear neural networks. 12 2013.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of wooldd-worldd networks. Nature, 393(6684):440 442, 1998. ISSN 1476-4687. doi: 10.1038/30918.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. CoRR, abs//608.03665, 2016.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B, 68:49-67, 02 2006. doi: 10.1111jj1467-98666 00532.x.
A INITIALIZING DEEP LINEAR NEURAL NETWORKS
In (Glorot & Bengio 2010), authors propose that the difficulty of training deep neural networks lies in their initialization. They observe that for the common weight initialization W = -V- 1
Vn vnl
the variance of activations decreases the signal progresses through the layers. Similarly, the vari- ance of the gradients the highest the last layer, and decreases as gradients are backpropagated towards the input layer. We briefly cover derivation of the Xavier initialization here.
Given a layer with nin input and Nout output neurons, and a uniform dementt-wiee variance a² (a,) of i-th layer activations, (W;) of i-th layer weights, and (6:) of i-th layer gradients, we can calculate the variance the next / previous layer's actvations and gradients as:
o² (an+1) d²(8m) o 2 IWn+1)
(21)
order to maintain the variance accross layers, layer and + 1 activation gradient variances should be equal:
(a,) = (a((1)) (W 1
Thin 1
(22)
o² (8m) = -2(6m+1) (WW41))
Tout
For non-square weight matrices, authors compromise and set the weight variance
2² ( (w Thin + Nout
(23)
If the weight matrix is initialized with uniform distribution W = U(-r,r). the distribution vari- ance can be calculated as:
)U 2
(24)
12

---

Under review as a conference paper at ICLR 2019
From equations 23 and 24 have:
Nin + Pout
(25)
v6
Miin + Nout
Weights should then be initialized with the following distribution, commonly known as the Xavier initialization:
W u
v6
V6
(26)
Biin + Rout
VDin + Roott
B MEASURING THE NUMBER OF SOLVABLE RATIO CONSTRAINTS
On a practical note, one way to test how many ratios a network can learn is to append a 'diagonal layer' the end of the network (i.e., new layer with single neuron attached to each output), as seen in Figure [ The diagonal layer is a diagonal matrix whose only trainable elements are on the main diagonal, and all other values O. When training network, this diagonal layer only learn magnitudes, and not ratios between signals, because each neuron only has one input and cannot "mix" any signals. This gives
easy way of measuring the number of ratios network can correctly express: we train network with LI loss until it converges. We then count the number of constraints & the network has satisfied. These constraints can be ratio constraints or magnitude constraints. If we have output neurons, we know that the last layer will have satisfied all magnitude constraints. Hence, the number of ratios the network can satisfy kt n. For example, the network in Figure 6 (right, though true for left too) can satisfy three out of the 4 absolute constraints. of those are magnitude constraints, meaning can only satisfy one ratio constraint. That ratio is calculated at neuron n, either neuron or y get correct ratio of inputs, but not both. Of course, with L.2 loss, the network will settle for a solution that doesn't satisfy either, but picks some middle ground.
a
x
Figure 6: A 'diagonal layer' allows networks to solve magnitude constraints even if the network uses constant (non-tunable) connections in the last layer.
C CONTROLLABILITY COROLLARIES
Corollary C.O.1. For a neuron n with set of imput neurons (f,,.., in) connected with t trainable and l: constant connections, controllability Co,((n)) is:
Cr/ min(1, Σ Cajolis) ACa/b(Ti))
(27)
where
I
1
S minit, k 1--1) 1)
(28)
Notice that as at least one connection is constant, the network can make full use of all trainable connections.
D DECOMPOSING GRAPHS
We briefly show how graphs can be decomposed so that we can apply Theorems 6.4 and 6.5 In Figure 7 3-1-2 graph decomposed into graph where each neuron has most inputs
13

---

Under review as a conference paper at ICLR 2019
outputs. We apply Theorem 6.4 to subgraph {a, b, m) and {m, c, n. and Theorem 6.5 to subgraph (n, z', y/ J. Since neurons z and y only have one input, their controllability is identical to that of x' and y' respectively.
rumectionn
Cenuant connecionn
Original graph
Decomposed graph
Figure 7: Decomposition of a 3-1-2 graph into a new graph on which we can apply aggregation and fannout theorems.
E EXAMPLE TOPOLOGIES
(a) Example of Clos network that underperforms limited bandwidth the middle layer. Dotted lines represent constant-van valued connections.
(b) Example of parallel butterfly topology with two 4-input. 3-layer butterfly topologies parallel. Dot- ted lines represent constant- constant-valued connections.
Figure 8: Example topologies
14


Reviews:
[{"review_id": "rkev_8yLtr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper tackles the problem of finding a sparse network architecture before training, so as to facilitate training on resource-constrained platforms. To this end, the authors propose to replace dense layers with series of sparsely-connected linear layers. They then study how to initialize such sparse layers to avoid gradient vanishing. Furthermore, they propose an approach to finding the best topology by measuring how well the sparse layers can approximate random weights of their dense counterparts.\n\nMethodology/clarity:\nWhile I found the beginning of the paper, up to Section 4 (included), easy to follow, I must admit that I have been struggling with the remainder of the paper. In particular:\n- In Section 5, the authors propose to use the L2 difference between random weights of a dense layer and the reconstruction of these weights with sparse layers. It seems that the author take this as a proxy to network accuracy (as indicated by a statement just below Fig. 3). It is not clear to me, however, that a small L2 norm will indeed correspond to a similar accuracy in practice, and this is never demonstrated in the paper.\n- This L2 loss is then replaced by an L0 one, which again I fail to find any justification for. In fact, I don't see why the authors did not directly use the L0 norm in the first place.\n- If I understood correctly, the goal of Sections 5-6 is to find the best topology for the sparse layers. However, it seems the number and width of such layers still need to be pre-defined. Correct?\n- Below Eq. 6, the authors mention that the networks are still trained using SGD with L1 loss. I do not understand this statement. On what is the L1 loss computed?\n\nExperiments:\nUltimately, the authors argue that their approach allowed them to find a parallel butterfly architecture that outperforms the other ones. However:\n- There is no evidence that the resulting architecture is indeed better than the others when it comes to solving an actual problem (e.g., in terms of classification accuracy);\n- There still seem to be a fair bit of manual design in this parallel butterfly architecture, and it is therefore not clear to me that it is truly the best possible one.\n\nRelated work:\nA number of architecture designs have been proposed to obtain a compact network prior to training. MobileNets, used here as baseline CNN, is one of them, but so are MobileNetv2, ShuffleNet and ShuffleNetv2, SqueezeNet, and ERFNet. I believe that it would be worth discussing these architectures and showing the benefits of the proposed approach over them.\n\nSummary:\nI have been struggling to follow the second half of this paper, and I am not convinced by the hypothesis that the L2 (or L0) norm between dense and sparse parameters is a good proxy for network accuracy, which is not demonstrated. I therefore feel that this paper is not ready for publication.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "rJgxbE8wcS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a new weight initialization method for sparse neural networks and develop a weight topology that satisfies desirable properties. Their derivation is data-free, and thus the analysis should generalize to arbitrary datasets. They demonstrate that their new topology outperforms existing approaches on a matrix reconstruction task.\n\nOverall I think this work is an interesting direction for designing static sparse neural network weight topologies, but it’s lacking in empirical evidence of their claims and could do better to tie themselves to existing literature in training sparse neural networks. \n\nIf the authors could strengthen their results by a) experimenting with their newfound topology and initialization on standard sparsification benchmarks like CIFAR, ImageNet, and WMT EnDe b) comparing their approach to other static-sparse [1, 2, 3] and dynamic-sparse [4, 5] training algorithms this could be a good paper, but without more experimentation it’s unclear what can be taken away from this work. If the authors added results in this direction I would be willing to increase my score.\n\nComments on Claims of the Paper:\n\n1. “Cascades” are a known trick in both dense & sparse neural networks [2, 6].\n2. The authors describe their motivation for developing a new sparse initialization method in the first paragraph of section 4. It would be nice to see some of this experimental data, such that we could understand the magnitude of the vanishing gradient problem in these tests and see that the newly derived initialization alleviates it. The reason for my skepticism is that Liu et al [7] used a similar scheme where they re-scale the standard deviation of the gaussian based on the fraction of nonzero weights, but later found that it made no difference in their results for unstructured pruning (which I learned through discussion with the authors).\n4. The data-free derivation approach makes sense and I understand that this makes the approach theoretically applicable to arbitrary datasets, but the authors do not apply it to other datasets to show that it generalizes in practice.\n5. The authors show that their topology outperforms on the matrix reconstruction task, but they don’t compare with other sparsification approaches used in deep learning like sparse evolutionary training [4], or SNIP [1] (note that these techniques also maintain a sparse network during training, as opposed to pruning approaches like magnitude pruning [8] that are dense during training but sparse for inference).\n\nComments on the Results of the Paper:\n\nThe authors appear to contextualize their work in deep neural networks, but all of their experimental results are on matrix reconstruction or linear models on MNIST. This is sufficient for analysis and motivation, but taking the developed approaches and applying them to a deep neural network and showing improvements would go a long way towards improving this paper.\n\nAssorted Notes:\n\nIn the first paragraph of the introduction:\n\n“In other words, doubling the size of layer inputs and outputs quadruples the size of the layer. This causes majority of the networks to be memory-bound, making DNN training impractical without batching, a method where training is performed on multiple inputs at a time and updates are aggregated per batch.”\n\nIt is correct that a matrix-vector product (i.e., neural network training with batch size 1) is typically memory bound on accelerators like GPUs, but it’s not clear why the quadratic growth in computational cost with input/output size has anything to do with this. The cause of memory bound-ness is lack of reuse of operands, which can be alleviated by increasing the batch size s.t. the computation becomes a matrix-matrix product. Batch size 1 training is also not desirable. Recent work has shown that large batch sizes do not degrade model quality with proper hyperparameter tuning [9], and larger batch sizes are desirable from a hardware perspective to achieve higher throughput.\n\nReferences:\n1. https://arxiv.org/abs/1810.02340\n2. https://d4mucfpksywv.cloudfront.net/blocksparse/blocksparsepaper.pdf\n3. https://arxiv.org/abs/1903.05895\n4. https://www.nature.com/articles/s41467-018-04316-3\n5. https://openreview.net/forum?id=ryg7vA4tPB\n6. https://arxiv.org/abs/1811.10495v3\n7. https://arxiv.org/pdf/1810.05270v2.pdf\n8. https://arxiv.org/abs/1710.01878\n9. https://arxiv.org/abs/1811.03600", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyeuHcRxcH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a sparse cascade architecture that is a multiplication of several sparse matrices. Then the paper provides several considerations about the connectivity scheme. Finally, the paper proposes a specific connectivity pattern that outperforms other ones.\n\nI am not exactly in this area, but the paper is frequently confusing and hard to read. If I understand correctly, Sec 5 proposes a method to evaluate topologies. It seems that this method is strongly tied to the proposed cascade architecture, therefore cannot compare cascade vs non-cascade. The choice of the matrix reconstruction problem looks arbitrary. The paper finishes very abruptly.\n\nAnother consideration is that evaluating on random matrices doesn't demonstrate the ability to solve real world problems. There are no experimentation on real benchmarks or comparison to prior work on sparse networks. It should be possible to compare to methods that sparsify networks after training as well as to methods that enforce sparsity during/before training.\n\nOther:\n- it is strange to call a method by the first name of the researcher (Xavier)\n- there are some grammatical mistakes and problems with articles\n\nEDIT:\nAfter the rebuttal period paper still has weak experimentation. My score stays the same.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxHFA_PcS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to replace dense layers with multiple sparse linear layers.  The idea is that the product ABC (for A, B, C all sparse matrices)  can accurately approximate a dense matrix D, but A(B(Cx))) requires much less work than Dx.  The paper then continues with the assumption that topology of the sparse matrices should be fixed before training, and that given this assumption we would like to find the \"best\" fixed topology to pick.  The paper introduces a new task to determine the \"best\" topology - that of reconstructing a random dense matrix.  On somewhat of a tangent the paper also introduces a minor modification to the Xavier initialization scheme that works better for deep stacks of sparse layers.\n\nMy current decision is one of Weak Reject.  I think the paper tackles an interesting line of research with some interesting ideas, but I'm concerned that the implications of the major assumptions that are made are never examined.\n\nIt is briefly implied that if the topology were fixed, then we could build hardware for such a topology (motivating the approach).  But we could also build hardware to accelerate general dynamic sparsity.  Given that it seems important to try and understand the tradeoffs involved in using fixed sparse topologies like the ones proposed and dynamic sparsity techniques such as:\n\n1) Deep Rewiring (https://arxiv.org/abs/1711.05136)\n2) Sparse Evolutionary Training (https://www.nature.com/articles/s41467-018-04316-3)\n3) Dynamic Sparse Reparameterization (https://arxiv.org/abs/1902.05967) \n4) Sparse Networks from Scratch (https://arxiv.org/abs/1907.04840)\n5) Rigging the Lottery (https://openreview.net/forum?id=ryg7vA4tPB)\n\nThe tradeoffs both in terms of the hardware that could be built for these different regimes _and_ the effect of static topologies vs. dynamic ones on accuracy (for a given parameter / flop / energy / etc. budget).  These dynamic techniques could also be used to decompose a dense layer into a product of multiple learned sparse matrices.\n\nThe effect of assuming that we want each connection to have equal controllability seems non-obvious. For example, if we imagine that we're replacing a convolutional (or at least locally connected) layer, then we _want_ to be able to take advantage of the structure/particularities of the input and doing so will lead to a more efficient model than one which is forced to ignore them (as the proposed topology necessarily does.)   How much less efficient will the proposed architecture be in this case?\n\nMany of these questions could be answered by trying the dynamic sparse techniques and the proposed static topologies on real problems (MB on ImageNet for example), maybe some kind of language modeling task, etc.  I find the use of one artificial task (of matrix reconstruction) which serves mainly to confirm the assumptions that are made rather than test them on real data and real problems a big weakness of the paper.\n\nSome general notes:\n\nThe enforcing sparsity before training section should mention SNIP: Single-shot Network Pruning based on Connection Sensitivity https://arxiv.org/abs/1810.02340\n\nThe enforcing sparsity during training section, should mention both the dynamic techniques that are mentioned above, but also techniques that are dense -> sparse but which significantly outperform the L1 techniques mentioned.\n\nFor example:\n\n1) Iterative Pruning as used in Learning both Weights and Connections for Efficient Neural Networks (https://arxiv.org/abs/1506.02626) and popularized by The Lottery Ticket Hypothesis (https://arxiv.org/abs/1803.03635)\n2) To prune or not to Prune (https://arxiv.org/abs/1710.01878)\n3) Variational Dropout (https://arxiv.org/abs/1701.05369)\n4) Dynamic Network Surgery (https://arxiv.org/abs/1608.04493)\n\nThe mobilenet reference seems a bit out of place as mobilenets are never otherwise used in the rest of the paper.  It seems like something very similar has already been done in (https://dawn.cs.stanford.edu/2019/06/13/butterfly/).\n\nvraiance -> variance", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes new initialization and layer topologies for training a priori sparse networks. Reviewers agreed that the direction is interesting and that the paper is well written. Additionally the theory presented on the toy matrix reconstruction task helped motivate the proposed approach. However, it is also necessary to validate the new approach by comparing with existing sparsity literature on standard benchmarks. I recommend resubmitting with the additional experiments suggested by the reviewers.
Decision: Reject