Network pruning has emerged as a powerful technique for reducing the size of deep neural networks. Pruning uncovers high-performance subnetworks by taking a trained dense network and gradually removing unimportant connections. Recently, alternative techniques have emerged for training sparse networks directly without having to train a large dense model beforehand, thereby achieving small memory footprints during both training and inference.These techniques are based on dynamic reallocation of non-zero parameters during training. Thus, they are in effect executing a training-time search for the optimal subnetwork. We investigate a most recent one of these techniques and conduct additional experiments to elucidate its behavior in training sparse deep convolutional networks. Dynamic parameter reallocation converges early during training to a highly trainable subnetwork. We show that neither the structure, nor the initialization of the discovered high-performance subnetwork is sufficient to explain its good performance. Rather, it is the dynamics of parameter reallocation that are responsible for successful learning. Dynamic parameter reallocation thus improves the trainability of deep convolutional networks, playing a similar role as overparameterization, without incurring the memory and computational cost of the latter. Training high-performance compact networks is often a two-step process. A large network is first trained, then compressed using techniques such as pruning, distillation, or low-rank decomposition. Training a compact network from scratch typically fails to reach the same level of accuracy achieved by compressing a larger network BID0 .Network pruning is a common compression method that yields a high-performance subnetwork of an original network. A natural question is whether such high-performance subnetworks can be uncovered by a direct search over the space of subnetworks, without the two-step process of training a large network first and then pruning it down. The advantage of such a search-based procedure is that the full dense model need not be trained; instead, we start with an initial subnetwork and continuously modify it during training until we find a high-performance subnetwork. BID1 described such a search procedure. Their scheme starts with a sparse network and continuously reallocates during training its non-zero parameters throughout the network based on a simple heuristic. The resulting subnetworks perform on par with, and often better than, subnetworks obtained by iteratively pruning a large overparameterized model. This calls into question the belief that overparameterization is essential to successful learning. Here, we argue that dynamic parameter reallocation (DPR) is an equally effective approach to overparameterization to improving the trainability of deep convolutional networks (CNNs). We present results for a wide Resnet WRN-28-2 [Zagoruyko and Komodakis, 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada. The need for overparameterization during learning has often been attributed to the reduced likelihood of stochastic gradient descent (SGD) being trapped in bad local optima as the dimensionality of the loss surface (number of parameters) increases. An alternative hypothesis, "the lottery ticket hypothesis" BID7 , argues that starting with large, overparameterized networks simply provides more candidate subnetworks, making it more likely that one of these candidates becomes a "winning lottery ticket", i.e, having the right structure and initialization needed to learn the task. Our results did not support this hypothesis. We showed that structure and initialization alone or in combination were not sufficient to train compact sparse CNNs to high performance. Rather, successful learning seemed to depend on the dynamics and the extra degrees of freedom provided by DPR. Note that our results are not at odds with those in BID7 , which reported negative results on finding "winning tickets" in deep residual networks.DPR seems to play an analogous role to overparameterization when it comes to improving network trainability. Like overparameterization, DPR allows training to explore more degrees of freedom than those strictly necessary to solve the task. Unlike overparameterization where these degrees of freedom are extra parameters, DPR introduces extra degrees of freedom by simultaneous exploration of different subnetwork structures during training. In terms of computational and memory resources, DPR is a more attractive method than overparameterization in improving network trainability because it obviates the need to maintain or operate on large models, and requires a smaller memory footprint that is the same during training and inference.
Dynamic parameter-reallocation enables the successful direct training of compact sparse networks, and it plays an indispensable role even when we know the optimal sparse network a-priori