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. Training deep neural networks requires both powerful hardware and a significant amount of time. Long training times are a significant bottleneck to deep learning research, as researchers typically iteratively design and test new architectures for a specific problem. While a lot of research has been dedicated to accelerating inference, we investigate training as (1) accelerating training can speed up research iteration, (2) evolutionary algorithms for DNN architecture exploration are increasingly being used as an alternative to 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 1 . 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. While batching alleviates the pressure on DRAM bandwidth, it can decrease model accuracy (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., 2015a) , complicating on-line training on battery-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 et al., 2017; Isakov et al., 2018) or weight sharing (Ding et al., 2017) 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 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 -or 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 an answer on how a topology should be selected. Our contributions are as following: • We propose a 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 a matrix reconstruction task and show that the choice of topology has a strong effect on attainable network accuracy. • In order to evaluate topologies independently of a dataset, we develop a 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. 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 control of outputs with respect to inputs, allowing us to assess the expressiveness of a given topology. We have extracted several requirements that make for a good topology, such as the need for skip connections, information bandwidth, shallowness, and input-output pair equality. Finally, we have proposed a 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. Weights should then be initialized with the following distribution, commonly known as the Xavier initialization: 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' to the end of the network (i.e., a new layer with a single neuron attached to each output), as seen in Figure 6 . The diagonal layer is a diagonal matrix whose only trainable elements are on the main diagonal, and all other values are 0. When training a network, this diagonal layer can only learn magnitudes, and not ratios between signals, because each neuron only has one input and cannot 'mix' any signals. This gives us an easy way of measuring the number of ratios a network can correctly express: we train a network with L1 loss until it converges. We then count the number of constraints k the network has satisfied. These constraints can be ratio constraints or magnitude constraints. If we have n output neurons, we know that the last layer will have satisfied all magnitude constraints. Hence, the number of ratios the network can satisfy is k − n. For example, the network in Figure 6 (right, though true for left too) can satisfy three out of the 4 absolute constraints. 2 of those are magnitude constraints, meaning it can only satisfy one ratio constraint. That ratio is calculated at neuron n, so either neuron x or y can get a correct ratio of inputs, but not both. Of course, with L2 loss, the network will settle for a solution that doesn't satisfy either, but picks some middle ground.
We investigate pruning DNNs before training and provide an answer to which topology should be used for training a priori sparse networks. The authors propose to replace dense layers with sparsely-connected linear layers and an approach to finding the best topology by measuring how well the sparse layers approximate random weights of their dense counterparts. The paper proposes a sparse cascade architecture that is a multiplication of several sparse matrices and a specific connectivity pattern that outperforms other provided considerations.