Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks, yet theoretical justification for their empirical success falls short. We consider a randomized greedy compression algorithm for pruning and quantization post-training and use it to rigorously show the existence of pruned/quantized subnetworks of multilayer perceptrons (MLPs) with competitive performance. We further extend our results to structured pruning of MLPs and convolutional neural networks (CNNs), thus providing a unified analysis of pruning in wide networks. Our results are free of data assumptions, and showcase a tradeoff between compressibility and network width. The algorithm we consider bears some similarities with Optimal Brain Damage (OBD) and can be viewed as a post-training randomized version of it. The theoretical results we derive bridge the gap between theory and application for pruning/quantization, and provide a justification for the empirical success of compression in wide multilayer perceptrons.

Abstract. We consider the problem of estimating the edge density of densest [Formula: see text]-node subgraphs of an Erdös–Rényi graph [Formula: see text]. The problem is well-understood in the regime [Formula: see text] and in the regime [Formula: see text]. In the former case it can be reduced to the problem of estimating the size of largest cliques, and its extensions [P. Balister, B. Bollobás, K. Gunderson, I. Leader, and M. Walters, Trans. Amer. Math. Soc., 370 (2018), pp. 7361–7389]. In the latter case the full answer is known up to the order [Formula: see text] using sophisticated methods from the theory of spin glasses. The intermediate case [Formula: see text], however, is not well studied and this is our focus. We establish that in this regime the density (that is the maximum number of edges supported by any [Formula: see text]-node subgraph) is [Formula: see text], w.h.p. as [Formula: see text], and provide more refined asymptotics under the [Formula: see text], for various ranges of [Formula: see text]. This extends earlier similar results in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019] where this asymptotic was confirmed only when [Formula: see text] is a small constant. We extend our results to the case of “weighted” graphs, when the weights have either Gaussian or arbitrary sub-Gaussian distributions. The proofs are based on the second moment method combined with concentration bounds, the Borell-TIS inequality for the Gaussian case and the Talagrand’s inequality for the case of distributions with bounded support (including the [Formula: see text] case). The case of general distribution is treated using a novel symmetrized version of the Lindeberg argument, which reduces the general case to the Gaussian case. Finally, using the results above we conduct the landscape analysis of the related Hidden Clique Problem, and establish that it exhibits an overlap gap property when the size of the clique is [Formula: see text], confirming a hypothesis stated in [D. Gamarnik and I. Zadik, The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property, preprint, https://arxiv.org/abs/1904.07174 , 2019].