  Recent advances in neural network pruning have shown how it is possible to
reduce the computational costs and memory demands of deep learning models
before training. We focus on this framework and propose a new pruning at
initialization algorithm that leverages the Neural Tangent Kernel (NTK) theory
to align the training dynamics of the sparse network with that of the dense
one. Specifically, we show how the usually neglected data-dependent component
in the NTK's spectrum can be taken into account by providing an analytical
upper bound to the NTK's trace obtained by decomposing neural networks into
individual paths. This leads to our Path eXclusion (PX), a foresight pruning
method designed to preserve the parameters that mostly influence the NTK's
trace. PX is able to find lottery tickets (i.e. good paths) even at high
sparsity levels and largely reduces the need for additional training. When
applied to pre-trained models it extracts subnetworks directly usable for
several downstream tasks, resulting in performance comparable to those of the
dense counterpart but with substantial cost and computational savings. Code
available at: https://github.com/iurada/px-ntk-pruning
