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.
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.