NeST¶

TLDR: NeST is a grow-and-prune synthesis method. It scores new connections and neurons with bridging matrices (batch activation–gradient cross-covariances), adds convolutional feature maps by loss-based random search, then compresses the result with magnitude pruning.

NeST [DYJ19] synthesizes a sparse network by alternating a growth phase (Policies 1–3) and a pruning phase (Policy 4). It is function-improving in the sense of Exploiting function geometry: unlike Net2Net or Variance Transfer, it does not preserve the network function at growth steps. Growth decisions are driven by bridging matrices \(\boldsymbol{B}\), formed from batched post-activations and pre-activation gradients, whose entry magnitudes estimate the first-order benefit of activating a dormant edge or inserting a neuron.

We reuse the notation of Neuron addition problem (layer index \(l\), widths \(C_l\), batched activations \(\boldsymbol{H}^{(l)}\), negative pre-activation gradients \(\boldsymbol{G}^{(l)}\), batch size \(N\), new fan-in/fan-out \(\boldsymbol{\psi}/\boldsymbol{\omega}\)). Prerequisites: Sparse growth and grow-prune methods.

Note

Source version. Methods and numbers follow the openly available arXiv preprint 1711.02017v3. The bibliography key [DYJ19] points to the IEEE Transactions on Computers (2019) version.

Policies at a glance¶

Table 14 NeST policies.¶
Policy	Role
Policy 1	Connection growth: activate dormant edges with the largest bridging scores \(\|B^{(l-1)}_{i,j}\|\).
Policy 2	Neuron growth (fully connected): keep the top-\(\beta\) bridging pairs in \(\boldsymbol{B}^{(l-2)}\) and initialize from them (Algorithm 1 / Eq. (7)).
Policy 3	Convolutional feature-map growth: sample random kernel candidates, keep the one that most reduces \(\mathcal{L}\).
Policy 4	Magnitude pruning of weights and neurons (partial-area convolution is a convolution-specific variant).

Bridging matrices¶

NeST keeps every layer at its full dense layout but holds most entries dormant (masked at zero); growth unmasks slots rather than reshaping the layer. The bridging matrices are the batch activation–gradient cross-covariances

(3)¶\[\boldsymbol{B}^{(l-1)} := \frac{1}{N}\big(\boldsymbol{H}^{(l-1)}\big)^\top \boldsymbol{G}^{(l)}, \qquad \boldsymbol{B}^{(l-2)} := \frac{1}{N}\big(\boldsymbol{H}^{(l-2)}\big)^\top \boldsymbol{G}^{(l)}.\]

On the fixed layout, \(B^{(l-1)}_{i,j} = -\,\partial\mathcal{L}/\partial W^{(l)}_{i,j}\) even where \(W^{(l)}_{i,j}=0\), so \(|B^{(l-1)}_{i,j}|\) is the gradient magnitude of a dormant edge. \(\boldsymbol{B}^{(l-2)}\) is the analogous quantity for a hypothetical edge that skips the layer where a new neuron is inserted.

Method¶

NeST exposes three growth operations and one pruning operation. We describe them through the usual how / where / when lens.

Flowchart from sparse seed through growth policies to magnitude pruning

Grow-and-prune pipeline: Policies 1–3 (growth), then Policy 4 (magnitude pruning).

How¶

Connections (Policy 1). Rank dormant edges \((i,j)\) of \(\boldsymbol{W}^{(l)}\) by \(|B^{(l-1)}_{i,j}|\) and unmask the largest. The paper does not state how a newly unmasked weight is initialized (see Limitations).

Neurons (Policy 2). To insert one unit at layer \(l-1\), rank candidate bridges by \(|B^{(l-2)}_{i,j}|\), keep the top \(\beta\times 100\%\) (set \(S_\beta\)), and initialize fan-in \(\boldsymbol{\psi}\) and fan-out \(\boldsymbol{\omega}\) from those entries. For a single retained pair \((i^\ast, j^\ast)\) Algorithm 1 sets a one-sparse pair

(4)¶\[\begin{split}\begin{aligned} \epsilon &\sim \mathrm{Uniform}(\{-1, 1\}),\\ \psi_{i^\ast} &= \epsilon\,\operatorname{sgn}\!\big(B^{(l-2)}_{i^\ast,j^\ast}\big)\sqrt{\big|B^{(l-2)}_{i^\ast,j^\ast}\big|},\qquad \omega_{j^\ast} = \epsilon\,\sqrt{\big|B^{(l-2)}_{i^\ast,j^\ast}\big|}, \end{aligned}\end{split}\]

(all other entries zero). The square-root split imitates one backprop step on the skip edge: linearizing \(\sigma\) near zero, a new unit adds the rank-one shift \(\boldsymbol{\delta}_z \approx \sigma'(0)\,\boldsymbol{H}^{(l-2)}\boldsymbol{\psi}\boldsymbol{\omega}^\top\), maximized along the top entry of \(\boldsymbol{B}^{(l-2)}\). With \(|S_\beta|>1\), increments accumulate over pairs (independent \(\epsilon\) per pair). Eq. (7) then rescales by birth strength \(\alpha\),

(5)¶\[\boldsymbol{\psi} \leftarrow \alpha\,\boldsymbol{\psi}\, \frac{\bar{a}(\boldsymbol{W}^{(l-1)})}{\bar{a}(\boldsymbol{\psi})}, \qquad \boldsymbol{\omega} \leftarrow \alpha\,\boldsymbol{\omega}\, \frac{\bar{a}(\boldsymbol{W}^{(l)})}{\bar{a}(\boldsymbol{\omega})},\]

where \(\bar{a}(\cdot)\) is the mean absolute value over non-zero entries; the paper reports \(\alpha > 0.3\) as a workable range.

Feature maps (Policy 3). Convolutional connection growth reuses Policy 1 on dormant kernel entries. A new feature map has no closed-form score: NeST samples random candidate kernels \(\mathcal{K}_1,\ldots,\mathcal{K}_r\) (each adding one output map) and keeps the one minimizing the loss,

(6)¶\[\mathcal{K}^\ast = \mathop{\mathrm{\arg\!\min}}_{\mathcal{K}_s}\, \mathcal{L}\!\big(f_{\mathcal{K}_s}\big).\]

Where¶

NeST starts from a sparse seed (full layout, only a small active fraction). Policy 1 unmasks edges within the fixed layout; Policy 2 widens a layer; Policy 3 adds conv feature maps. The paper does not specify a layer order, the number of edits per step, or a per-step cap on connection growth.

When¶

The paper does not provide a clear explanation. It reports a grow-then-prune sequence of phases but no canonical alternating loop, growth trigger, or stopping rule; scheduling is left to the (unspecified) outer protocol.

Pruning (Policy 4)¶

Pruning is iterative: each step drops the smallest-magnitude weights in a layer (e.g. ~1% per layer), then retrains the whole network before the next pass; with batch normalization, pruning uses effective weights (BN scale folded into \(\boldsymbol{W}\)), and neurons left with no fan-in or fan-out are removed. Partial-area convolution is a convolution-specific variant that masks each feature map to fixed areas of interest before convolution to cut FLOPs; we skip its details, as the masking protocol is underspecified and only affects some FLOP figures.

Experimental results¶

The paper does not include a dedicated training section (no optimizer, learning-rate, or epoch budget is given, and weight updates during the growth phase are not described), so the headline numbers are hard to reproduce. The reported compression versus dense baselines is summarized below.

Table 15 Headline compression vs. dense baselines (arXiv abstract).¶
Dataset	Model	Parameters	FLOPs
Affine MNIST	LeNet-300-100	70.2× fewer	79.4× fewer
Affine MNIST	LeNet-5	74.3× fewer	43.7× fewer
ImageNet	AlexNet	15.7× fewer	4.6× fewer
ImageNet	VGG-16	30.2× fewer	8.6× fewer

NeST beats pure pruning (MNIST)¶

On affine-distorted MNIST the relevant baseline is Net prune — magnitude pruning of a trained dense network (Han et al.), with no growth step. At equal or better accuracy NeST reaches markedly smaller networks: on LeNet-300-100 it is both more accurate and ~3× smaller than Net prune, and on LeNet-5 it matches the error at ~6× fewer parameters.

Table 16 Selected affine-MNIST results — error / parameters / FLOPs [DYJ19].¶
Model	Method	Error	#Param	FLOPs
LeNet-300-100	Caffe	1.60%	266K	532K
LeNet-300-100	Net prune	1.59%	22K	43K
LeNet-300-100	NeST	1.29%	7.8K	14.9K
LeNet-5	Caffe	0.80%	431K	4586K
LeNet-5	Net prune	0.77%	35K	734K
LeNet-5	NeST	0.77%	5.8K	105K

NeST matches the dense baselines (ImageNet)¶

On ImageNet, NeST nearly matches the dense baselines at a large size reduction: it stays within 0.02 pp of the AlexNet baseline top-1 while using 15.7× fewer parameters and 4.6× fewer FLOPs. On VGG-16 it stays within 0.35 pp of the baseline top-1 at 13.9× fewer parameters and 4.9× fewer FLOPs.

Other findings¶

A LeNet seed-width sweep is the clearest scheduling study: narrower seeds yield smaller final networks but need longer growth, while larger post-growth networks prune more aggressively, so a moderately small seed is the practical sweet spot. Component checks credit Policy 3 with ~2× larger immediate loss reduction than random feature-map init, and partial-area convolution with ~2× extra FLOP reduction on LeNet-5.

Limitations and open questions¶

Outer loop unspecified. Local policies are defined, but not how to interleave grow and prune, how many edits per step, the layer order, or the stopping rule. The knobs \(\alpha, \beta, \gamma\) and the Policy 3 candidate count \(r\) appear with only isolated hints, so reproducing Table 15 implies untold benchmark-specific tuning. Broader context: When to grow?, Where to grow?.
Connection initialization. Policy 2 has a closed-form initializer, but Policy 1 only selects which dormant edge to wake; how the new weight is set (from \(B^{(l-1)}_{i,j}\), zero, or otherwise) is never stated.
Bridging-matrix estimates. Each \(\boldsymbol{B}\) is a batch statistic, so scores depend on batch size, data draw, and training stage; the paper does not say whether to accumulate over multiple batches before a decision.
Linearized neuron model. The square-root split is justified by linearizing \(\sigma\) near zero; when the new neuron operates far from that regime the rank-one approximation may be loose.

References¶

[DYJ19] (1,2,3)

Xiaoliang Dai, Hongxu Yin, and Niraj K. Jha. NeST: A Neural Network Synthesis Tool Based on a Grow-and-Prune Paradigm. IEEE Transactions on Computers, 68(10):1487–1497, October 2019. doi:10.1109/TC.2019.2914438.