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

arXiv:2609.12337v1 Announce Type: new 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

• Hierarchical End-to-End Taylor Bounds for Complete Neural Network Verification
• Nearly Tight Rademacher Bounds for Sparsely Activated Neural Networks
• Selection Plateau and a Sparsity-Dependent Hierarchy of Pruning Features

Source: arXiv cs.LG | 2026-09-14