Structured vs. Unstructured Pruning: An Exponential Gap

• URL: http://arxiv.org/abs/2603.02234v2
• Date: Wed, 04 Mar 2026 08:56:15 GMT
• Title: Structured vs. Unstructured Pruning: An Exponential Gap
• Abstract summary: We study the problem of approximating a single bias-free ReLU neuron using a randomly bias-free two-layer ReLU network.<n>We show that neuron pruning requires a starting network with $(d/varepsilon)$ hidden neurons to $varepsilon$-approximate a target ReLU neuron.
• Score: 7.354394320088788
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Strong Lottery Ticket Hypothesis (SLTH) posits that large, randomly initialized neural networks contain sparse subnetworks capable of approximating a target function at initialization without training, suggesting that pruning alone is sufficient. Pruning methods are typically classified as unstructured, where individual weights can be removed from the network, and structured, where parameters are removed according to specific patterns, as in neuron pruning. Existing theoretical results supporting the SLTH rely almost exclusively on unstructured pruning, showing that logarithmic overparameterization suffices to approximate simple target networks. In contrast, neuron pruning has received limited theoretical attention. In this work, we consider the problem of approximating a single bias-free ReLU neuron using a randomly initialized bias-free two-layer ReLU network, thereby isolating the intrinsic limitations of neuron pruning. We show that neuron pruning requires a starting network with $Ω(d/\varepsilon)$ hidden neurons to $\varepsilon$-approximate a target ReLU neuron. In contrast, weight pruning achieves $\varepsilon$-approximation with only $O(d\log(1/\varepsilon))$ neurons, establishing an exponential separation between the two pruning paradigms.

Related papers

• Language Model Circuits Are Sparse in the Neuron Basis [50.460651620833055]
  We show that textbfMLP neurons are as sparse a feature basis as SAEs.<n>This work advances automated interpretability of language models without additional training costs.
  arXiv  Detail & Related papers  (2026-01-30T05:41:19Z)
• Training-Free Restoration of Pruned Neural Networks [7.317046947172644]
  We propose a more rigorous and robust method of restoring pruned networks in a fine-tuning free and data-free manner.<n>Our method is based on a theoretical analysis on how to formulate the reconstruction error between the original network and its approximation.
  arXiv  Detail & Related papers  (2025-02-06T05:30:48Z)
• Cluster-based classification with neural ODEs via control [0.0]
  We consider a single-neuron architecture with parameters fixed as piecewise constant functions of time.<n>Previous work has shown that classification can be achieved using a point-by-point strategy that requires $O(N)$ switches.<n>We propose a new control method that classifies any arbitrary dataset by sequentially steering clusters of $d$ points.
  arXiv  Detail & Related papers  (2023-12-21T12:56:40Z)
• Universal approximation property of Banach space-valued random feature models including random neural networks [3.3379026542599934]
  We introduce a Banach space-valued extension of random feature learning. By randomly initializing the feature maps, only the linear readout needs to be trained. We derive approximation rates and an explicit algorithm to learn an element of the given Banach space.
  arXiv  Detail & Related papers  (2023-12-13T11:27:15Z)
• Nonparametric regression using over-parameterized shallow ReLU neural networks [10.339057554827392]
  We show that neural networks can achieve minimax optimal rates of convergence (up to logarithmic factors) for learning functions from certain smooth function classes. It is assumed that the regression function is from the H"older space with smoothness $alpha(d+3)/2$ or a variation space corresponding to shallow neural networks. As a byproduct, we derive a new size-independent bound for the local Rademacher complexity of shallow ReLU neural networks.
  arXiv  Detail & Related papers  (2023-06-14T07:42:37Z)
• Gradient Descent in Neural Networks as Sequential Learning in RKBS [63.011641517977644]
  We construct an exact power-series representation of the neural network in a finite neighborhood of the initial weights. We prove that, regardless of width, the training sequence produced by gradient descent can be exactly replicated by regularized sequential learning.
  arXiv  Detail & Related papers  (2023-02-01T03:18:07Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Receding Neuron Importances for Structured Pruning [11.375436522599133]
  Structured pruning efficiently compresses networks by identifying and removing unimportant neurons. We introduce a simple BatchNorm variation with bounded scaling parameters, based on which we design a novel regularisation term that suppresses only neurons with low importance. We show that neural networks trained this way can be pruned to a larger extent and with less deterioration.
  arXiv  Detail & Related papers  (2022-04-13T14:08:27Z)
• 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)
• A global convergence theory for deep ReLU implicit networks via over-parameterization [26.19122384935622]
  Implicit deep learning has received increasing attention recently. This paper analyzes the gradient flow of Rectified Linear Unit (ReLU) activated implicit neural networks.
  arXiv  Detail & Related papers  (2021-10-11T23:22:50Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• And/or trade-off in artificial neurons: impact on adversarial robustness [91.3755431537592]
  Presence of sufficient number of OR-like neurons in a network can lead to classification brittleness and increased vulnerability to adversarial attacks. We define AND-like neurons and propose measures to increase their proportion in the network. Experimental results on the MNIST dataset suggest that our approach holds promise as a direction for further exploration.
  arXiv  Detail & Related papers  (2021-02-15T08:19:05Z)

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.