Pruning at Initialization -- A Sketching Perspective
This work addresses the lottery ticket hypothesis for neural network pruning, offering theoretical insights and algorithmic improvements that could enhance efficiency in machine learning model compression.
The paper tackles the problem of pruning neural networks at initialization by analyzing it through a sketching perspective in linear models, showing that finding sparse masks is equivalent to sketching for matrix multiplication and providing theoretical bounds on approximation error. It suggests a generic improvement to existing pruning algorithms, which is shown to be beneficial in data-independent cases.
The lottery ticket hypothesis (LTH) has increased attention to pruning neural networks at initialization. We study this problem in the linear setting. We show that finding a sparse mask at initialization is equivalent to the sketching problem introduced for efficient matrix multiplication. This gives us tools to analyze the LTH problem and gain insights into it. Specifically, using the mask found at initialization, we bound the approximation error of the pruned linear model at the end of training. We theoretically justify previous empirical evidence that the search for sparse networks may be data independent. By using the sketching perspective, we suggest a generic improvement to existing algorithms for pruning at initialization, which we show to be beneficial in the data-independent case.