PaperlayerView exact revision on arXiv

Source-linked AI summary

Pruning neural networks without any data by iteratively conserving synaptic flow

Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, Surya Ganguli

arXiv:2006.05467v3cs.LGcond-mat.dis-nncs.CVq-bio.NCstat.ML

TL;DR

The paper asks whether sparse trainable subnetworks can be found at initialization without training or data, avoiding the cost of iterative training-and-pruning discovery. It derives conservation laws explaining layer-collapse and introduces SynFlow, which preserves synaptic flow while pruning. SynFlow provably avoids layer-collapse and consistently matches or outperforms existing methods across 12 model–dataset combinations without pre-training.

  • Problem

    Finding sparse trainable subnetworks at initialization traditionally requires expensive iterative training and pruning, motivating a data-free alternative.

  • Method

    SynFlow iteratively prunes parameters using positive synaptic-flow scores derived from a data-independent loss, preserving total flow through the network.

  • Results

    SynFlow provably avoids layer-collapse, reaches Maximal Critical Compression, and consistently matches or outperforms existing algorithms across 12 model–dataset combinations.

  • Takeaways & Limitations

    Highly sparse trainable subnetworks can be identified at initialization without using training data or pre-training.

  • Takeaways & Limitations

    The pruning procedure’s behavior can depend significantly on whether a model is in evaluation or training mode because batch-normalization buffers are unlearned at initialization.

Abstract

from arXiv · show

Pruning the parameters of deep neural networks has generated intense interest due to potential savings in time, memory and energy both during training and at test time. Recent works have identified, through an expensive sequence of training and pruning cycles, the existence of winning lottery tickets or sparse trainable subnetworks at initialization. This raises a foundational question: can we identify highly sparse trainable subnetworks at initialization, without ever training, or indeed without ever looking at the data? We provide an affirmative answer to this question through theory driven algorithm design. We first mathematically formulate and experimentally verify a conservation law that explains why existing gradient-based pruning algorithms at initialization suffer from layer-collapse, the premature pruning of an entire layer rendering a network untrainable. This theory also elucidates how layer-collapse can be entirely avoided, motivating a novel pruning algorithm Iterative Synaptic Flow Pruning (SynFlow). This algorithm can be interpreted as preserving the total flow of synaptic strengths through the network at initialization subject to a sparsity constraint. Notably, this algorithm makes no reference to the training data and consistently competes with or outperforms existing state-of-the-art pruning algorithms at initialization over a range of models (VGG and ResNet), datasets (CIFAR-10/100 and Tiny ImageNet), and sparsity constraints (up to 99.99 percent). Thus our data-agnostic pruning algorithm challenges the existing paradigm that, at initialization, data must be used to quantify which synapses are important.

1 Introduction

The paper asks whether highly sparse, trainable subnetworks can be identified at initialization without training or data. It develops a theory-driven approach to answer this question.

  • Winning-ticket subnetworks can match the original network’s test accuracy when trained in isolation.
  • Identifying such subnetworks through iterative training and pruning is more computationally expensive than training the original network.
  • The paper investigates whether highly sparse trainable subnetworks can be found at initialization without training or using data.
  • The authors study layer-collapse, formulate conservation laws for synaptic saliency, and introduce a data-agnostic pruning algorithm.

2 Related work

Prior pruning methods largely compress pretrained models, while newer initialization-time methods either require costly iterative training or use single-shot gradients.

  • The paper focuses on neural-network pruning rather than alternative compression approaches such as micro-architectures or dimensionality reduction.
  • Pruning after training: Conventional pruning assigns scores after training and removes parameters with the lowest scores, reducing test-time but not training cost.
  • Pruning before training: Iterative Magnitude Pruning identifies sparse subnetworks at initialization through repeated training, pruning, and weight-rewinding cycles.
  • Pruning before training: Single-shot initialization pruning instead uses gradients of the training loss to score parameters before training.

3 Layer-collapse: the key obstacle to pruning at initialization

Layer-collapse is the key obstacle to extreme pruning at initialization: removing an entire layer makes the network untrainable. The paper proposes maximal critical compression as the criterion for avoiding this failure whenever possible.

  • Pruning algorithms score parameters and remove the lowest-scoring ones, using either global or layer-wise masking.
  • Max compression is N/L for a network with L layers and N parameters, while critical compression is the highest compression achieved without layer-collapse.
  • Figure 1: Figure 1 compares accuracy against compression for VGG-16 on CIFAR-100 and marks each algorithm’s critical compression.
  • The Maximal Critical Compression axiom requires an algorithm’s critical compression to equal the network’s maximum compression.
  • SynFlow preserves total synaptic-strength flow rather than individual strengths and is designed to satisfy maximal critical compression without using data.

4 Conservation laws of synaptic saliency

The paper identifies conservation laws for gradient-based synaptic saliency and uses them to explain why single-shot pruning can collapse layers, especially large ones.

  • Existing pruning methods can prematurely remove an entire layer as compression increases, making the network untrainable.
  • Random pruning removes parameters at similar rates across layers, while magnitude pruning first eliminates the widest layers.
  • Synaptic saliency is a general class of gradient-based parameter scores, including metrics related to Skeletonization, Taylor-FO, and Optimal Brain Damage.
  • Synaptic saliency obeys neuron-wise and network-wise conservation laws for feedforward networks with continuous homogeneous activations.
  • Figure 3: Neuron-wise conservation compares incoming and outgoing scores for hidden units, with exact conservation represented by the black dotted line.
  • Conservation makes average scores inversely related to layer size, explaining why single-shot gradient methods disproportionately prune large layers.

5 Magnitude pruning avoids layer-collapse with conservation and iteration

Training causes magnitude-based pruning scores to approach layer-wise conservation, while iterative pruning uses this re-evaluation to avoid layer-collapse. IMP therefore avoids the catastrophic failure that can occur when an entire layer is pruned.

  • Iterative Magnitude Pruning: IMP requires repeated training–pruning cycles to avoid layer-collapse, whereas insufficient iterations produce sudden accuracy drops.Without training between pruning cycles, repeated pruning is equivalent to single-shot magnitude pruning.
  • Why collapse occurs: Conservation alone favors lower scores for parameters in larger layers, making those layers more vulnerable to layer-collapse.The resulting imbalance explains why single-shot pruning methods can prematurely remove an entire layer.
  • Why collapse is avoided: Iterative pruning counteracts this imbalance because a pruned large layer becomes smaller and its remaining parameters receive higher relative scores in later iterations.Together, conservation and iteration form a self-balancing pruning strategy that avoids layer-collapse with sufficient iterations.

6 A data-agnostic algorithm satisfying Maximal Critical Compression

The paper uses conservation and positive scores to design SynFlow, a data-independent iterative pruning algorithm satisfying Maximal Critical Compression. SynFlow evaluates scores repeatedly at initialization, preserving synaptic flow while remaining computationally feasible.

  • Algorithm design: SynFlow is designed to inherit conservation and iterative score evaluation while avoiding IMP’s impractical repeated training.Its score construction is data-independent and uses a loss function yielding positive synaptic saliency scores.
  • Maximal Critical Compression: SynFlow is motivated by a theorem showing that positive, conserved global scores can reach Maximal Critical Compression.The axiom requires avoiding layer-collapse whenever another parameter set of the same size can preserve trainability.
  • Synaptic Flow score: Synaptic Flow scores generalize magnitude scores by measuring products of synaptic strengths through parameters and accounting for inter-layer interactions.The score corresponds to the portion of the network’s l1-path norm flowing through each parameter.
  • Pruning procedure: SynFlow iteratively evaluates scores, finds a percentile threshold, updates the binary mask, and returns the masked initialization.The algorithm takes a network, compression ratio, and iteration count as inputs; model evaluation mode matters because batch-normalization buffers are unlearned.
  • Computational setting: 100 pruning iterations with an exponential schedule essentially prevent avoidable layer-collapse while remaining feasible for large networks.SynFlow uses 100 passes regardless of dataset, compared with 1000, 2000, and 10,000 passes for SNIP and GraSP on listed datasets.

7 Experiments

Across 12 model–dataset combinations, SynFlow is strongest and most stable at high compression, while data-dependent methods can suffer layer-collapse. The results also show that iteration improves SNIP but does not eliminate collapse, whereas SynFlow competes without using data.

  • Benchmark results: SynFlow consistently outperforms random pruning, magnitude pruning, SNIP, and GraSP in the high-compression regime.The comparison spans VGG-11, VGG-16, ResNet-18, and WideResNet-18 on CIFAR-10, CIFAR-100, and Tiny ImageNet.
  • Benchmark results: SynFlow demonstrates greater stability at high compression, as indicated by its tight performance intervals across runs.Figure 6 reports means and minimum–maximum ranges from three runs with different random seeds.
  • Benchmark results: SNIP and GraSP can partially outperform SynFlow at low compression, but both suffer sharp accuracy drops from layer-collapse.The low-compression regime is defined as ρ < 10^1.5, while high compression is 10^1.5 < ρ.
  • Iterative pruning: Iteration helps SNIP avoid early layer-collapse but increases computational cost, and iterative SNIP still collapses before maximum compression.SynFlow is provably guaranteed to reach maximal critical compression.
  • Ablation studies: SynFlow matches or outperforms data-dependent pruning methods at initialization without using data.This result challenges the effectiveness of using data to score parameters at initialization.

8 Conclusion

The paper develops a theory explaining layer-collapse in pruning at initialization and uses it to design SynFlow, a data-agnostic method that avoids collapse. Across 12 model–dataset combinations, SynFlow matches or outperforms existing algorithms without pre-training.

  • Conclusion: The framework explains why existing pruning algorithms at initialization suffer from layer-collapse.Layer-collapse is the premature pruning of an entire layer, making the network untrainable.
  • Conclusion: SynFlow provably avoids layer-collapse and reaches Maximal Critical Compression.The algorithm is designed from the paper’s conservation-law framework.
  • Conclusion: Across 12 distinct model–dataset combinations, SynFlow consistently matches or outperforms existing algorithms without data or pre-training.The conclusion identifies SynFlow as data-agnostic and requiring no pre-training.

Broader Impact

Pruning may improve energy efficiency, reduce training’s environmental impact, and ease deployment on edge devices. This work is mainly theoretical, so those potential impacts are not directly realized by the study.

  • Potential benefits: Pruning has the potential to increase neural-network energy efficiency and decrease the environmental impact of training.These are identified as potential broader impacts rather than demonstrated outcomes of this work.
  • Potential benefits: Pruning may facilitate deployment of trained neural-network models on edge devices such as mobile phones.The passage presents easier edge deployment as a potential benefit.
  • Scope: Because the work primarily explores pruning from a theoretical angle, these impacts are not directly applicable to the study.The passage leaves realization of these benefits to future work.

9 Proofs

The proofs establish conservation of synaptic saliency at neurons and across network-separating parameter sets. They then show that positive, iterative, conservative scoring can avoid layer-collapse whenever a non-collapsing pruning set is available.

  • Neuron-wise conservation: For homogeneous activations, incoming and outgoing synaptic saliency sums are equal at each hidden neuron.The theorem covers continuous homogeneous activations such as ReLU, Leaky ReLU, and linear activations.
  • Network-wise conservation: The total synaptic saliency is conserved across any parameter set that exactly separates network inputs from outputs.This is the network-wise conservation law for feedforward networks with homogeneous activations.
  • Network-wise conservation: The proof propagates neuron-wise conservation through successive partitions until the saliency sum reaches the output neurons.The argument iterates through the network’s neuron sets and parameter boundaries.
  • Maximal Critical Compression: Positive scores that conserve saliency layer-wise and prune less total score than an available cut satisfy Maximal Critical Compression.The theorem assumes global masking and a prune size strictly smaller than the cut size whenever possible.
  • Maximal Critical Compression: If such an algorithm caused layer-collapse despite an equally sized non-collapsing set, the separating set would have at least the cut’s total score.This contradicts the algorithm’s requirement that prune size remain below cut size whenever possible.

10 Pruning with batch normalization

Batch normalization changes synaptic-saliency conservation: incoming scores sum to zero, so SynFlow must score in evaluation mode, while inverse layer-size scaling remains empirically visible. Ablations and implementation studies examine SynFlow’s layer-collapse behavior, pruning schedule, and numerical limitations.

  • Batch normalization: Batch normalization makes incoming synaptic saliency sum to zero, forcing SynFlow scores before batch normalization to vanish unless scoring uses evaluation mode.The paper explains that evaluation mode effectively removes batch normalization at initialization.
  • Batch normalization: Inverse proportionality between layer size and average score remains empirically observed with batch normalization for SNIP and GraSP.Figure 8 plots layer average scores against inverse numbers of elements for VGG-19 pruned with ImageNet data.
  • Ablation studies: SynFlow’s performance drops immediately when its scores are inverted, supporting the claim that the scores preserve cross-layer importance to avoid layer-collapse.The corresponding inversion causes only a moderate SNIP drop and an unnoticeable GraSP drop.
  • Hyperparameter choices: Using 100 pruning iterations with an exponential compression schedule satisfies Theorem 3 over compression ratios 10^n for 0 ≤ n ≤ 3, unlike a linear schedule.These findings are reported for SynFlow and are illustrated in Figure 10.
  • Limitations: SynFlow may become numerically unstable in very deep networks because singular values can vanish or explode exponentially with depth, although this was not observed in the presented models.Layer-wise parameter scaling or increased numerical precision are suggested responses.
Loading 2006.05467v3…