Theoretical Guarantees for One-Shot Magnitude Pruning and Compute-Adaptive Early Exit

• URL: http://arxiv.org/abs/2609.12337v1
• Date: Fri, 11 Sep 2026 01:38:44 GMT
• Title: Theoretical Guarantees for One-Shot Magnitude Pruning and Compute-Adaptive Early Exit
• Abstract summary: We study compute reduction in neural networks through a unified partial versus full view.<n>In an magnitude single-neuron model, we prove a concentration theorem for one-shot magnitude pruning with explicit rates.<n>We extend the analysis to deep networks, characterizing how pruning-induced distortions accumulate with depth.
• Score: 15.784279009967888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study compute reduction in neural networks through a unified partial versus full computation view, captured by one-shot magnitude pruning in the static regime and early exit in the adaptive regime. In an asymptotic single-neuron model, we prove a concentration theorem for one-shot magnitude pruning with explicit rates. We also introduce the conditional perceptron for early exit and show that its excess generalization error decays as a power of the compute gap, with an exponent that grows to infinity as the alignment between partial and full computations tends to one. We then extend the analysis to deep networks, characterizing how pruning-induced distortions accumulate with depth and deriving a corresponding compute-accuracy tradeoff for frozen-backbone early exit under a neural network Gaussian process model. Numerical simulations corroborate the predicted scaling laws.

Related papers

• Quantifying Uncertainty In Wide Two-Layer Neural Networks: On The Law Of The Limiting Fluctuation Process [3.0171175820634826]
  Uncertainty quantification in neural networks prediction is a main issue for usual applications.<n>Our approach seeks at reducing costs by directly evaluating uncertainty using PDE's information on the variance.<n>We thus study the law of the limiting process describing the random fluctuations around the mean-field limit of wide two-layer neural networks trained by gradient descent.
  arXiv  Detail & Related papers  (2026-06-04T10:25:23Z)
• Scaling Effects and Uncertainty Quantification in Neural Actor Critic Algorithms [0.0]
  We investigate the neural Actor Critic algorithm using shallow neural networks for both the Actor and Critic models.<n>We compare the convergence properties of the network outputs under various scaling schemes as the network width and the number of training steps tend to infinity.
  arXiv  Detail & Related papers  (2026-01-25T19:06:49Z)
• The Geometry of Grokking: Norm Minimization on the Zero-Loss Manifold [5.076419064097734]
  We argue that post-memorization learning can be understood through the lens of constrained optimization.<n>We show that gradient descent effectively minimizes the weight norm on the zero-loss manifold.<n>Experiments confirm that simulating the training process using our predicted gradients reproduces both the delayed generalization and representation learning characteristic of grokking.
  arXiv  Detail & Related papers  (2025-11-02T18:44:42Z)
• Adaptive kernel predictors from feature-learning infinite limits of neural networks [46.50233782149623]
  We show that neural networks trained in the rich, feature learning infinite-width regime are also described by kernel machines.<n>We provide explicit expressions for the kernel predictors and prescriptions to numerically calculate them.
  arXiv  Detail & Related papers  (2025-02-11T22:34:49Z)
• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  We present a unifying perspective on recent results on ridge regression.<n>We use the basic tools of random matrix theory and free probability, aimed at readers with backgrounds in physics and deep learning.<n>Our results extend and provide a unifying perspective on earlier models of scaling laws.
  arXiv  Detail & Related papers  (2024-05-01T15:59:00Z)
• Analyzing Neural Network-Based Generative Diffusion Models through Convex Optimization [45.72323731094864]
  We present a theoretical framework to analyze two-layer neural network-based diffusion models. We prove that training shallow neural networks for score prediction can be done by solving a single convex program. Our results provide a precise characterization of what neural network-based diffusion models learn in non-asymptotic settings.
  arXiv  Detail & Related papers  (2024-02-03T00:20:25Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  Neuro-symbolic approaches typically resort to fuzzy approximations of a probabilistic objective. We show how to compute this efficiently for tractable circuits. We test our approach on three tasks: predicting a minimum-cost path in Warcraft, predicting a minimum-cost perfect matching, and solving Sudoku puzzles.
  arXiv  Detail & Related papers  (2023-02-28T00:04:22Z)
• Error analysis for deep neural network approximations of parametric hyperbolic conservation laws [7.6146285961466]
  We show that the approximation error can be made as small as desired with ReLU neural networks. We provide an explicit upper bound on the generalization error in terms of the training error, number of training samples and the neural network size.
  arXiv  Detail & Related papers  (2022-07-15T09:21:09Z)
• 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)
• Precise characterization of the prior predictive distribution of deep ReLU networks [45.46732383818331]
  We derive a precise characterization of the prior predictive distribution of finite-width ReLU networks with Gaussian weights. Our results provide valuable guidance on prior design, for instance, controlling the predictive variance with depth- and width-informed priors on the weights of the network.
  arXiv  Detail & Related papers  (2021-06-11T21:21:52Z)
• Mean-Field Approximation to Gaussian-Softmax Integral with Application to Uncertainty Estimation [23.38076756988258]
  We propose a new single-model based approach to quantify uncertainty in deep neural networks. We use a mean-field approximation formula to compute an analytically intractable integral. Empirically, the proposed approach performs competitively when compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-06-13T07:32:38Z)

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.