Generalization Bounds for Magnitude-Based Pruning via Sparse Matrix Sketching
This work provides improved theoretical guarantees for pruning algorithms, which is important for researchers and practitioners in machine learning seeking efficient model compression, though it is incremental as it builds on prior bounds.
The paper tackles the problem of bounding generalization error for magnitude-based pruning in overparameterized neural networks, achieving stronger bounds than state-of-the-art methods by improving approximation accuracy and reducing parameter count via sparse matrix sketching.
In this paper, we derive a novel bound on the generalization error of Magnitude-Based pruning of overparameterized neural networks. Our work builds on the bounds in Arora et al. [2018] where the error depends on one, the approximation induced by pruning, and two, the number of parameters in the pruned model, and improves upon standard norm-based generalization bounds. The pruned estimates obtained using our new Magnitude-Based compression algorithm are close to the unpruned functions with high probability, which improves the first criteria. Using Sparse Matrix Sketching, the space of the pruned matrices can be efficiently represented in the space of dense matrices of much smaller dimensions, thereby lowering the second criterion. This leads to stronger generalization bound than many state-of-the-art methods, thereby breaking new ground in the algorithm development for pruning and bounding generalization error of overparameterized models. Beyond this, we extend our results to obtain generalization bound for Iterative Pruning [Frankle and Carbin, 2018]. We empirically verify the success of this new method on ReLU-activated Feed Forward Networks on the MNIST and CIFAR10 datasets.