Theoretical Compression Bounds for Wide Multilayer Perceptrons

• URL: http://arxiv.org/abs/2512.06288v1
• Date: Sat, 06 Dec 2025 04:32:25 GMT
• Title: Theoretical Compression Bounds for Wide Multilayer Perceptrons
• Authors: Houssam El Cheairi, David Gamarnik, Rahul Mazumder,
• Abstract summary: Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks.<n>We consider a randomized greedy compression algorithm for pruning and quantization post-training.
• Score: 18.425849654386393
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis [5.494111035517599]
  Quantization is an essential technique for making neural networks more efficient, yet our theoretical understanding of it remains limited.<n>Previous works demonstrated that extremely low-precision networks, such as binary networks, can be constructed by pruning large, randomly- approximationd networks.<n>We build on foundational results by Borgs et al. on the Number Partitioning Problem to derive new theoretical results for the Random Subset Sum Problem in a quantized setting.
  arXiv  Detail & Related papers  (2025-08-14T18:51:34Z)
• Pruning Deep Neural Networks from a Sparsity Perspective [34.22967841734504]
  Pruning is often achieved by dropping redundant weights, neurons, or layers of a deep network while attempting to retain a comparable test performance. We propose PQ Index (PQI) to measure the potential compressibility of deep neural networks and use this to develop a Sparsity-informed Adaptive Pruning (SAP) algorithm.
  arXiv  Detail & Related papers  (2023-02-11T04:52:20Z)
• A Theoretical Understanding of Neural Network Compression from Sparse Linear Approximation [37.525277809849776]
  The goal of model compression is to reduce the size of a large neural network while retaining a comparable performance. We use sparsity-sensitive $ell_q$-norm to characterize compressibility and provide a relationship between soft sparsity of the weights in the network and the degree of compression. We also develop adaptive algorithms for pruning each neuron in the network informed by our theory.
  arXiv  Detail & Related papers  (2022-06-11T20:10:35Z)
• On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
  We study how random pruning of the weights affects a neural network's neural kernel (NTK) In particular, this work establishes an equivalence of the NTKs between a fully-connected neural network and its randomly pruned version.
  arXiv  Detail & Related papers  (2022-03-27T15:22:19Z)
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks [79.74580058178594]
  We analyze the performance of training a pruned neural network by analyzing the geometric structure of the objective function. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned.
  arXiv  Detail & Related papers  (2021-10-12T01:11:07Z)
• Compact representations of convolutional neural networks via weight pruning and quantization [63.417651529192014]
  We propose a novel storage format for convolutional neural networks (CNNs) based on source coding and leveraging both weight pruning and quantization. We achieve a reduction of space occupancy up to 0.6% on fully connected layers and 5.44% on the whole network, while performing at least as competitive as the baseline.
  arXiv  Detail & Related papers  (2021-08-28T20:39:54Z)
• Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition [62.41259783906452]
  We present a novel global compression framework for deep neural networks. It automatically analyzes each layer to identify the optimal per-layer compression ratio. Our results open up new avenues for future research into the global performance-size trade-offs of modern neural networks.
  arXiv  Detail & Related papers  (2021-07-23T20:01:30Z)
• Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks [9.554646174100123]
  We show that the dynamics of the gradient descent training algorithm has a key role in obtaining compressible networks. We prove that the networks are guaranteed to be '$ell_p$-compressible', and the compression errors of different pruning techniques become arbitrarily small as the network size increases.
  arXiv  Detail & Related papers  (2021-06-07T17:02:59Z)
• Generic Perceptual Loss for Modeling Structured Output Dependencies [78.59700528239141]
  We show that, what matters is the network structure instead of the trained weights. We demonstrate that a randomly-weighted deep CNN can be used to model the structured dependencies of outputs.
  arXiv  Detail & Related papers  (2021-03-18T23:56:07Z)
• Successive Pruning for Model Compression via Rate Distortion Theory [15.598364403631528]
  We study NN compression from an information-theoretic approach and show that rate distortion theory suggests pruning to achieve the theoretical limits of NN compression. Our derivation also provides an end-to-end compression pipeline involving a novel pruning strategy. Our method consistently outperforms the existing pruning strategies and reduces the pruned model's size by 2.5 times.
  arXiv  Detail & Related papers  (2021-02-16T18:17:57Z)
• ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
  We show that a simple iterative mask discovery method can achieve state-of-the-art compression of very deep networks. Our algorithm represents a hybrid approach between single shot network pruning methods and Lottery-Ticket type approaches.
  arXiv  Detail & Related papers  (2020-06-28T23:09:27Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.