Source-linked AI summary
Deep Rewiring: Training very sparse deep networks
Guillaume Bellec, David Kappel, Wolfgang Maass, Robert Legenstein
TL;DR
Strict connectivity limits motivate training methods that can remain sparse throughout learning rather than pruning only after dense training. DEEP R jointly optimizes weights and connectivity through posterior-based stochastic sampling under a hard connection bound, and it achieves strong sparse-network performance across benchmark architectures, although simulating dormant connections is computationally inefficient.
Problem
Existing pruning methods remove connections after unconstrained training, leaving a need for methods that maintain strict connectivity bounds throughout training.
Method
DEEP R jointly samples network parameters and connectivity from a posterior while enforcing a hard constraint on total connections.
Results
DEEP R trains fully connected, convolutional, and recurrent architectures with extremely sparse connectivity and a marginal performance drop across benchmark tasks.
Takeaways & Limitations
DEEP R enables direct training of sparse deep networks under fixed connectivity limits, including 96.2 % MNIST accuracy at 1.3 % connectivity.
Takeaways & Limitations
DEEP R is computationally inefficient for sparse networks because dormant connections still have to be simulated.
Abstract
from arXiv · showhide
Neuromorphic hardware tends to pose limits on the connectivity of deep networks that one can run on them. But also generic hardware and software implementations of deep learning run more efficiently for sparse networks. Several methods exist for pruning connections of a neural network after it was trained without connectivity constraints. We present an algorithm, DEEP R, that enables us to train directly a sparsely connected neural network. DEEP R automatically rewires the network during supervised training so that connections are there where they are most needed for the task, while its total number is all the time strictly bounded. We demonstrate that DEEP R can be used to train very sparse feedforward and recurrent neural networks on standard benchmark tasks with just a minor loss in performance. DEEP R is based on a rigorous theoretical foundation that views rewiring as stochastic sampling of network configurations from a posterior.
1 INTRODUCTION
Deep rewiring addresses strict connectivity limits by adapting sparse network structure during supervised training rather than pruning only after dense training. DEEP R maintains a hard connection bound and achieves strong performance across sparse deep-network benchmarks.
- Motivation: Connectivity strongly affects neural-network hardware and software efficiency, with memory often dominating implementation costs.The cited examples include TPU on-chip memory limits and LSTM memory-reference energy exceeding ALU-operation energy by more than two orders of magnitude.
- Related work: Existing pruning methods typically train a larger network to convergence before removing connections, while other training-time methods usually begin fully connected.These approaches cannot maintain bounded computational resources throughout training.
- Contribution: DEEP R trains deep neural networks under strict connectivity constraints and automatically rewires connections during learning.The method is motivated by dynamic synaptic rewiring observed during learning in the brain.
- Results: Across benchmark tasks, DEEP R keeps fully connected, convolutional, and recurrent architectures extremely sparse throughout training with only a marginal performance drop.The reported evaluations include feedforward, convolutional, and LSTM networks.
- Results: 96.2 % classification accuracy was achieved on MNIST with 1.3 % connectivity.The paper also reports similar performance to state-of-the-art pruning, with DEEP R outperforming those methods at a few percent of full connectivity.
2 REWIRING IN DEEP NEURAL NETWORKS
DEEP R frames sparse-network training as posterior sampling over both parameters and constrained architectures. Its updates combine gradient dynamics, noise, and stochastic rewiring while enforcing a hard connectivity limit.
- Probabilistic formulation: The probabilistic formulation seeks parameter settings with high posterior probability, combining a structural prior with the network likelihood.A temperature parameter controls whether the tempered posterior is flattened or sharpened relative to the ordinary posterior.
- Probabilistic formulation: The paper extends stochastic-gradient MCMC to sample both network parameters and connectivity under a hard constraint on total connections.The resulting dynamics jointly sample network weights and constrained architectures.
- Algorithm: DEEP R guarantees a hard maximum connectivity during training while sampling network configurations in addition to weights and biases.This directly targets settings where memory or other resources are bounded throughout training.
- Algorithm: Each connection parameter encodes activity and signed weight: negative parameters are dormant, while nonnegative parameters define active weights with a fixed sign.The mapping uses wk = 0 for dormant connections and wk = skθk for active connections.
- Algorithm: Active parameters receive backpropagation gradients, ℓ1 regularization, and Gaussian noise during updates.The gradient is computed over a mini-batch in practice, and the noise scale is controlled by temperature T.
- Functional consequence: The rewiring dynamics are intended to adapt network connectivity online when task demands drift.The paper identifies this online adaptation as a functional consequence of the algorithm's stochastic dynamics.
- Algorithm: When a parameter crosses below zero, its connection becomes dormant and a uniformly selected dormant connection is activated with parameter zero.This mechanism performs stochastic rewiring while preserving the prescribed connectivity bound.
3 EXPERIMENTS
Experiments show that DEEP R trains sparse feedforward, convolutional, and recurrent networks while maintaining strict connectivity limits, with performance close to or better than relevant baselines. Rewiring also supports adaptation across changing tasks and remains comparatively stable in recurrent training.
- DEEP R achieved 96.2% MNIST accuracy at 1.3% connectivity and 84.1% CIFAR-10 accuracy at 5% connectivity.
- DEEP R reached 96.3% MNIST accuracy at 1.0% connectivity, representing less than a 2% drop from the fully connected baseline.This result used twice as many training epochs as the initial MNIST experiment.
- During training, the number of newly activated connections converged to a stable value after an initial transient and remained stable after performance converged.
- For the TIMIT LSTM, DEEP R outperformed soft-DEEP R and fixed-random connectivity at the connectivity levels tested, with only small error-rate glitches during training.Pruning and ℓ1-shrinkage instead produced large sudden error-rate increases, possibly from recurrent-network instabilities.
- Across MNIST, CIFAR-10, and TIMIT, DEEP R and soft-DEEP R remained competitive with pruning and ℓ1-shrinkage under strict connectivity constraints.Rewiring slightly outperformed unconstrained pruning on CIFAR-10 and TIMIT at all considered connectivity levels, while pruning was slightly better on MNIST at larger connectivities.
- At very low connectivities, pruning and ℓ1-shrinkage failed on MNIST and TIMIT, whereas DEEP R and soft-DEEP R still produced reasonable networks.
- With shuffled MNIST labels after each epoch, accuracy increased across tasks, while early-layer weights and outputs became more correlated across successive epochs.The authors interpret this pattern as preserved information and features invariant to the shuffled output coding convention.
4 CONVERGENCE PROPERTIES OF DEEP R AND SOFT-DEEP R
The convergence analysis treats soft-DEEP R and DEEP R as stochastic dynamics over parameters and constrained network configurations. It explains how rewiring samples high-performing sparse architectures while preserving a strict connectivity bound for DEEP R.
- Soft-DEEP R converges to a target distribution over network configurations rather than to one particular parameter vector.
- Soft-DEEP R keeps dormant connection parameters in random walks, allowing connections to reactivate when their parameters cross zero.Because dormant parameters continue evolving, soft-DEEP R imposes a soft constraint through ℓ1 regularization rather than a hard connectivity bound.
- Soft-DEEP R is computationally inefficient for sparse networks because dormant connections must still be simulated, whereas DEEP R adds a strict connectivity constraint.
- Each DEEP R iteration updates active connections and randomly replenishes connections that became dormant, maintaining the constrained architecture process.
- The theoretical construction links DEEP R to a compound Markov chain over parameters and connectivity constraints with exactly K allowed active synapses.
- DEEP R’s posterior matches soft-DEEP R’s posterior when the connectivity constraint is fulfilled.
- DEEP R samples high-performing parameter vectors within constrained connectivities, favoring connections with strong support under the objective function.Other connections are randomly tested and discarded when they are not useful.
5 DISCUSSION
DEEP R extends stochastic-gradient sampling to network connectivity, enforcing a hard architectural constraint while preserving theoretical tractability. It jointly samples weights and structures, unlike earlier approaches that sampled weights alone.
- 5 DISCUSSION: DEEP R samples network connectivity alongside parameters and imposes a hard constraint on the total number of connections.It extends stochastic-gradient Monte Carlo sampling from parameter updates to connectivity sampling under constrained architectures.
- 5 DISCUSSION: DEEP R provides a sampler that avoids simulating dormant connections, improving efficiency for sparse connection matrices.The paper introduces random reintroduction of connections and analyzes its convergence properties.
- 5 DISCUSSION: The method modifies backpropagation and backpropagation-through-time so weights and the connectivity graph are optimized simultaneously within a fixed connection bound.Dormant connections are replaced through random reintroduction rather than sign reversal.
A METHODS
The methods describe implementations, hyper-parameter selection, baselines, and benchmark setups for evaluating DEEP R under sparse connectivity. Experiments cover MNIST, CIFAR-10, and TIMIT with task-specific training procedures.
- A METHODS: DEEP R hyper-parameters include regularization coefficient α and temperature T, with task-specific learning rates and carefully selected α values.Performance was reported as relatively insensitive to T but more dependent on α.
- A METHODS: 96.3% accuracy was achieved on MNIST under 1% connectivity with α = 10−4 and T chosen so that T = η.This reports one selected sparse MNIST configuration.
- A METHODS: 84.1% accuracy was reached on CIFAR-10 with 5% connectivity using layer-specific α values.The reported values were α = [0, 10−7, 10−6, 10−9, 0] from input to output.
- A METHODS: The soft-DEEP R comparison does not impose a global connectivity constraint, unlike DEEP R.This is a drawback under strict hardware limits but can help when reachable task sparsity is unknown.
- A METHODS: The pruning baseline used repeated training and pruning phases, with hyper-parameters selected through a weight-decay and quality-factor search.The chosen procedure was training–pruning–training–pruning–training.
- A METHODS: MNIST experiments used a two-hidden-layer ReLU network with 200 neurons per layer, batch size 10, learning rate 0.05, and 10 training epochs.Reported performance was classification error on the MNIST test set.
B REWIRING DURING TRAINING ON MNIST
On MNIST, DEEP R continued rewiring throughout training under a 1% connectivity constraint. After an initial transient, activation rates stabilized relative to each layer’s potential connections.
- B REWIRING DURING TRAINING ON MNIST: Initially, few new connections were activated because unhelpful weights required iterations to reach zero.This initial transient affected all network layers.
- B REWIRING DURING TRAINING ON MNIST: After the transient, newly activated connections stabilized at rates proportional to each layer’s number of potential connections.The relative activation pattern is shown in the normalized panel of Figure 6.
- B REWIRING DURING TRAINING ON MNIST: DEEP R continued rewiring connections even late in the training process.Thus, rewiring was not confined to early optimization.
C DETAILS TO: CONVERGENCE PROPERTIES OF SOFT-DEEP R
The soft-DEEP R analysis establishes convergence of stochastic parameter dynamics to a unique stationary distribution under stated regularity conditions. The implementation uses a smooth parameter-to-weight mapping and random-walk dynamics for dormant connections.
- C DETAILS TO: CONVERGENCE PROPERTIES OF SOFT-DEEP R: The parameter distribution evolves according to a Fokker–Planck equation and converges to a well-defined unique stationary distribution.This describes the distribution-level convergence used in the proof.
- C DETAILS TO: CONVERGENCE PROPERTIES OF SOFT-DEEP R: Under a strictly positive, continuous, twice continuously differentiable target distribution and β > 0, the stochastic dynamics leave p∗(θ) invariant.The same p∗(θ) is the unique stationary distribution of the sampling dynamics.
- C DETAILS TO: CONVERGENCE PROPERTIES OF SOFT-DEEP R: The network uses wk = f(θk), with the nonlinear mapping determining whether each connection contributes a synaptic weight.In the large-γ limit, θk < 0 corresponds to a dormant connection with zero functional weight.
- C DETAILS TO: CONVERGENCE PROPERTIES OF SOFT-DEEP R: Dormant parameters receive no error-gradient contribution, so their changes are driven independently of the error gradient.This follows because the gradient vanishes for θk < 0.
- C DETAILS TO: CONVERGENCE PROPERTIES OF SOFT-DEEP R: The stochastic update combines Gaussian diffusion with ℓ1 regularization, but clipping at θmin is required because negative parameters can otherwise diverge to −∞.The paper reports that this clipped formulation works well in practice.
D ANALYSIS OF CONVERGENCE OF THE DEEP R ALGORITHM
DEEP R is analyzed as a compound Markov chain that alternately updates active parameters and the connectivity constraint. Under stated posterior and ergodicity conditions, the chain has a unique stationary distribution while maintaining exactly K active connections.
- Algorithmic formulation: Each DEEP R iteration updates parameters with Tθ and connectivity with Tc, corresponding to separate parameter and rewiring steps.Tθ evolves active connections and Tc updates the binary constraint vector.
- Connectivity constraint: The binary vector c encodes active connections, with ck = 1 allowing connection k to be active and ck = 0 requiring it to remain dormant.The constraint requires dormant parameters to satisfy θk < 0.
- Connectivity update: Tc samples uniformly among compatible constraint vectors and selects exactly K active connections, introducing new connections for missing active slots.Compatibility requires dormant parameters to be negative, while |c| = K fixes the number of active connections.
- Parameter update: Tθ evolves active parameters through the stochastic differential equation while leaving dormant parameters unchanged, and it preserves the conditional posterior p∗(θ|c).This invariance is established in Lemma 1 under the stated transition construction.
- Stationary distribution: The compound operator leaves a joint stationary distribution over θ and c invariant, combining the conditional parameter distribution with a uniform prior over constraint vectors containing K active connections.The result follows by combining Lemma 1 with Theorem 2.
- Uniqueness and scope: Under ergodicity, every connection can become dormant with non-zero probability, making the connectivity chain irreducible and the stationary distribution unique.The convergence formalization applies directly to Algorithm 3; extending it quantitatively to DEEP R is described as approximate and prior-dependent.