Vision Systems & Engineering
Network Pruning
Removing weights, filters or channels from a trained network by a score of how much each one matters, from magnitude and Optimal Brain Damage to Optimal Brain Surgeon's inverse-Hessian update, Taylor and redundancy criteria for filters, channel selection by reconstruction, learned channel scales and lottery tickets.
advanced
Network pruning removes parts of a trained neural network, single weights or whole filters and channels, and keeps the rest. The question every method answers is which parts to remove: the smallest weights, the ones whose removal raises the training loss least, the filters that others can replace, or the channels the next layer can do without. The second question is what to do with what remains, since the surviving weights can be left as they are, adjusted in closed form, or retrained.
Model Compression places pruning beside quantization, distillation and factorization, and owns the general loop (train, score, remove, fine-tune), the difference between unstructured and structured pruning, N:M sparsity and its hardware support, Li et al.’s filter ranking and a PyTorch example that prunes a small digit classifier. This article goes into the scores themselves: where they come from, what they assume, and how the criteria for weights and for filters differ. Whether a pruned network actually runs faster is a question of latency and throughput on the target hardware, not of the number of weights removed.
Purpose
A trained network can have more parameters than its task needs. Optimal Brain Damage (LeCun, Denker & Solla, 1989), the method the LeNet article’s 1989 network was pruned with, starts from the observation that one can take a reasonable network, delete half or more of its weights and end up with one that works as well or better. Pruning makes that reduction systematic. Its uses are the ones Hassibi and Stork (1992) list in their abstract: better generalization, simpler networks, smaller hardware or storage needs, faster further training and, in some cases, rules that can be read from the pruned network. In the vision papers described below the aim is, in our reading, mainly the third: a smaller file, less memory traffic or fewer operations per image.
The two kinds of pruning serve different aims. Removing single weights (unstructured pruning) leaves tensors of the original shape with zeros in them, which saves storage once the zeros are encoded, but only saves time on hardware and libraries that skip them. Removing whole filters or channels (structured pruning) leaves a smaller dense network that any library runs faster; Model Compression gives the evidence for both statements.
When to Use It
Pruning is worth trying when a trained model is accurate enough but too large or too slow for its target, and when the target can turn the removed parameters into savings. Hoefler et al. (2021, §8.9), in a survey of the sparsity literature, note that many simple approaches reach moderate sparsity, 50–90% of weights removed, at the same or even higher accuracy, while sparsity above 95% needs more elaborate techniques. They write that structured pruning seems to provide a great trade-off between accuracy and performance on current architectures, partly because hardware and frameworks are tuned for dense blocked computation.
It helps less in three situations:
- The hardware ignores zeros. A network with most of its weights zeroed but its shapes unchanged runs no faster on dense kernels. Unless a sparse format or N:M pattern is supported end to end, only structured pruning changes the runtime, and even then the gain must be measured (Latency and Throughput).
- The network is already compact. Model Compression reports Blalock et al.’s finding that pruning a given architecture generally helps less than switching to a better architecture; a compact design such as MobileNet has less to remove.
- There is no data or compute to recover accuracy. Most methods below fine-tune after pruning, and some, such as Network Slimming, change the original training. In our reading, without training data only scores computed from the weights alone, such as magnitude, are available, and the closed-form compensation of Optimal Brain Surgeon needs data to estimate a Hessian.
How It Works
Saliency: the loss increase a deletion causes
LeCun, Denker and Solla (1989) define the saliency of a parameter as the change in the objective caused by deleting it, and estimate it from a local model of the loss rather than by deleting each parameter and re-evaluating. Hassibi and Stork (1992) write the Taylor series of the error in the weights as (their Eq. 1)
For a network trained to a local minimum the first term vanishes, and both papers neglect the higher-order terms. Deleting weight means imposing , or with the unit vector of weight (Eq. 2). Three criteria follow from three assumptions about :
- Optimal Brain Damage (OBD) ignores the off-diagonal terms of (the “diagonal” approximation) and moves only the deleted weight. Its saliency for parameter is , with the -th diagonal element of the Hessian; Model Compression gives the derivation and OBD’s results on a digit recognizer. OBD’s recipe sorts parameters by saliency, deletes some low-saliency ones, retrains, and repeats.
- Optimal Brain Surgeon (OBS) keeps the full Hessian and lets every other weight move to compensate. Minimizing under the deletion constraint with a Lagrange multiplier gives the optimal change of all weights and the resulting increase in error (Eq. 5, read from the rendered page of the NIPS 5 copy):
Hassibi and Stork call the saliency of weight and note that it includes OBD’s as the special case of a diagonal . Their procedure finds the weight with the smallest , deletes it if that increase is much smaller than , updates all weights by , recomputes and repeats.
- Magnitude pruning removes the smallest . In Hassibi and Stork’s terms (§7), magnitude methods assume an isotropic Hessian, , and OBD a diagonal one. Hoefler et al. (2021, §3.5.2) make the same point and call the assumption very strong and unlikely to hold in practice.
Both papers report that the second-order information matters. OBD’s Figure 1 shows the objective rising much less when parameters are deleted by saliency than by magnitude on their digit network. Hassibi and Stork state that the Hessians of every problem they considered were strongly non-diagonal; on a nine-weight XOR network, magnitude pruning and OBD each deleted a weight after which retraining could not recover zero error, while OBS deleted a different weight and its update alone returned the network to zero error. Across XOR networks trained from different starting points, only OBS deleted the correct weight in every case. On three MONK’s problems OBS kept the training and test accuracy of a backpropagation network with weight decay with 24%, 38% and 10% of its weights (their Table 1).
Scale and magnitude. A further property follows from the formulas (our derivation). If an input to a linear unit is multiplied by , a refitted weight on it is divided by , while the diagonal Hessian entry for that weight is multiplied by ; OBD’s and OBS’s are unchanged, but is not. Magnitude therefore ranks weights partly by the scale of what they multiply. Liu et al. (2017) make a related observation for channel scaling factors: in a network without batch normalization, separate scaling factors are not meaningful for ranking channels, because the convolution can absorb any rescaling.
Computing the inverse Hessian
OBS needs , which is the costly part. Hassibi and Stork approximate the Hessian of a network trained to small error by the sample covariance of its output gradients (their Eq. 10–14), dropping the term with the residual , and build its inverse in one pass over the training patterns with the matrix inversion lemma (Eq. 15–17). The recursion starts from with a small constant , so it actually inverts , which they describe as adding a penalty on large candidate jumps in weight space. Their §4 notes that is normally degenerate before much pruning has been done.
For modern networks the obstacles are size and invertibility. Hoefler et al. (2021, §3.5.3, §3.5.5) list the assumptions: a well-trained model with negligible gradient, an invertible Hessian that is constant along the pruning step, and one weight removed at a time with the Hessian recomputed after each removal. Methods that remove several weights in one step assume that correlations between the removed weights are negligible. They describe how such methods were applied at scale: approximating the Hessian by the empirical Fisher matrix, an average of outer products of per-sample gradients (an approach they trace to Hassibi and Stork), inverting it with the Sherman–Morrison recursion, or restricting it to blocks of a layer.
First-order importance for filters
Molchanov et al. (2019) define the importance of a parameter as the squared change in loss when it is removed, (their Eq. 3), and approximate it by a Taylor expansion. The first-order version needs only the gradient: (Eq. 5). For a filter they sum the importances of its parameters (Eq. 8), or place a gate after the batch-normalization layer, in which case the score is the squared gradient with respect to the gate. They prune during fine-tuning with a small learning rate, average the scores over minibatches, remove the lowest-scoring filters (usually about 2% of the initial filters per iteration) and continue. The authors report that the “group contribution” of Eq. 7, the square of a sum, correlates poorly with the true importance when the set of parameters is too large, which they attribute to the expected gradient tending to zero at convergence. On ResNets and DenseNets trained on ImageNet they measured a Spearman correlation above 93% between their scores and an estimate of the true importance from a greedy search (an “oracle”), and they report a 40% reduction in FLOPs for ResNet-101 by removing 30% of its parameters, with a 0.02% loss in top-1 accuracy on ImageNet (abstract).
Redundancy instead of size
Yang He, Liu, Wang, Hu and Yi Yang (2019) argue that ranking filters by norm, which they call the “smaller-norm-less-important” criterion, works only when two requirements hold: the filter norms must vary widely, and the smallest norms must be close to zero. They plot the norm distributions of filters in ResNet layers and state that these requirements are not always met. FPGM (Filter Pruning via Geometric Median) instead removes the filters closest to the geometric median of the layer’s filters, those with the smallest sum of Euclidean distances to the others (their Eq. 6), on the reasoning that their information can be represented by the remaining filters. Its algorithm zeroes the selected filters after each training epoch and builds the compact model at the end. They report more than 52% fewer FLOPs for ResNet-110 on CIFAR-10 with a 2.69% relative improvement in accuracy, and more than 42% fewer FLOPs for ResNet-101 on ILSVRC-2012 without a drop in top-5 accuracy (abstract).
Choosing channels by reconstructing the next layer
Two ICCV 2017 papers choose which channels of a layer to keep by how well the next layer’s output can be rebuilt without them. Removing a channel from a layer’s input also removes the filter that produced it in the previous layer.
- Yihui He, Zhang and Sun (2017), a different He from FPGM’s first author, sample input volumes and outputs of a convolution and minimize the reconstruction error with at most nonzero channel coefficients (Eq. 1). They relax the count to an penalty and alternate a LASSO step that selects channels (Eq. 3) with a least-squares step that refits the weights (Eq. 4); in practice they run the LASSO step until enough coefficients are zero and refit once. As a baseline they tried selecting channels by the absolute sum of their filter weights (Li et al.’s criterion) and found it sometimes worse than keeping the first channels, arguing that it ignores correlations between filters. Their abstract reports a 5× speed-up of VGG-16 with a 0.3% increase of error; the introduction attributes 4× with a 1.0% increase of top-5 error to channel pruning alone and the 5× result to channel pruning combined with tensor factorization.
- ThiNet (Luo, Wu & Lin, 2017) prunes layer using the statistics of layer , not of layer itself. From sampled inputs of layer it greedily builds the set of channels to remove, adding at each step the channel that gives the smallest value of its objective, the sum over samples of the squared total contribution of the removed channels to the sampled outputs (Eq. 6, Algorithm 1), then refits the remaining channels’ weights by least squares and fine-tunes for one or two epochs before the next layer. The authors call the greedy solution sub-optimal, with the gap compensated by fine-tuning, and report that it beat a sparse-coding alternative they tried. On ILSVRC-12 they report 3.31× fewer FLOPs and 16.63× compression for VGG-16 with a 0.52% drop in top-5 accuracy, and more than half of ResNet-50’s parameters and FLOPs removed at roughly a 1% drop in top-5 accuracy (abstract).
Both papers prune channels and keep the network dense, so the result runs on any library; reconstruction makes them data-driven, unlike magnitude ranking.
Learning which channels to drop
Network Slimming (Liu, Li, Shen, Huang, Yan & Zhang, 2017) changes the training rather than scoring a trained model. It adds an penalty on the scale factors of the batch-normalization layers, one per channel, so that training drives many of them toward zero. Channels are then removed with one global threshold set at a percentile of all scale factors (for example 70%), and the thinner network is fine-tuned. Reusing batch normalization’s adds no parameters, and the authors explain why a separate scaling layer would not work: in a network without batch normalization the convolution can compensate any rescaling, and a scaling layer placed before batch normalization is cancelled by the normalization. For VGGNet they report a 20× reduction in model size and a 5× reduction in computing operations with a multi-pass version (abstract).
How to Apply It
A practical pruning run follows Model Compression’s loop: start from a well-trained model, choose the structure (weights, N:M groups, filters or channels), choose a score, remove a fraction, recover accuracy, and repeat until the target size or the accuracy limit is reached. The choices that this article adds:
- Choose a score that matches what is removed. For single weights, magnitude is cheap and needs no data; second-order scores need a Hessian or Fisher estimate. For filters and channels, the Taylor criterion needs gradients during fine-tuning, FPGM needs only the weights, and the reconstruction methods need sampled activations of the next layer.
- Compensate or retrain. OBS’s update and the least-squares refits of He et al. and ThiNet adjust the surviving weights in closed form before any fine-tuning; magnitude and OBD rely on retraining.
- Allocate sparsity across layers. Hoefler et al. (§3.9) note that early work chose one global level, that later work found layers of different types and positions should be pruned differently, that two models with the same overall sparsity can need very different numbers of operations, and that many practitioners leave the first layers unpruned.
- Measure the result on the target. Count parameters and operations, but time the pruned model as Latency and Throughput describes.
Example: magnitude, OBD and OBS on a least-squares readout
A deep network’s loss is not quadratic, so OBD’s and OBS’s predictions are approximations there. A linear readout fitted by least squares has a quadratic loss, for which the second-order Taylor expansion is exact, so the predicted and actual loss increases can be compared to machine precision, and the criteria can be compared on images where the true weights are known. No network is trained.
Data. Each image has pixels (), flattened row by row. Its background is white Gaussian noise on a field, smoothed with scipy.ndimage.gaussian_filter ( pixel, default truncation at 4 standard deviations), cropped to its central (a 6-pixel margin, wider than the filter’s radius of 4) and divided by the norm of the filter’s impulse response, so that each pixel has variance 1. The background is multiplied by a vignetting gain , where is the distance of a pixel from the centre of the field at (row, column) and is that of the corner pixels. The gain falls from 0.9938 at the four central pixels to 0.25 at the corners, so the same weight multiplies a signal about four times weaker at the corners. The target is with , where is a horizontal edge detector of 12 pixels: on row 5 and on row 6, columns 1 to 6. Each seed draws 3,000 training and 3,000 test images; seeds 0 to 4 are run.
Loss and methods. The loss is , so , the convention of Hassibi and Stork’s Eq. 7 and 12 with patterns. The full model is fitted by numpy.linalg.lstsq. Each method then keeps weights (here counts the weights kept, not those removed):
- mag: the largest ; the rest set to zero, with no refit.
- OBD: the largest , computed once from the full fit; no refit.
- OBS: one weight at a time, the one with the smallest , with every surviving weight updated by Eq. 5. is the inverse of restricted to the surviving weights; after each removal it is downdated, , and row and column are dropped (our implementation; it keeps removed weights at zero).
- mag+refit: the support of mag, with the weights refitted by least squares on it.
Measures. For each and method the script prints the training-loss increase , the test mean squared error against the noisy test targets (the best possible value is 0.25), and the number of the 12 template pixels among the kept weights. mag and mag+refit keep the same pixels, so the table prints the hits of mag, OBD and OBS. Linear Regression’s example also counts the true pixels a method keeps on Gaussian-filtered patches, with different estimators (least squares, ridge, lasso and elastic net); it is the place to see the lasso select pixels.
Checks.
- C1: for every weight , from the full fit, OBS’s equals the actual after deleting and refitting the other 143 weights with
lstsq: the largest difference divided by is at most . - C2: OBD’s equals the actual of setting to zero with no refit, to the same bar.
- C3: at every , the iterative OBS weights equal
lstsqon the same support, to of the largest full-fit weight. - C4 (data): (i) the gain’s ratio of maximum to minimum is within 0.001 of 3.975; (ii) the background pixel variance of the training images is within 0.02 of 1; (iii) the template has 12 nonzero pixels; (iv) the full fit is learnable: its test MSE is at most 0.275, 1.1 times the floor; (v) the task is not trivial: with the signal variance computed exactly from the filter’s autocorrelation and the gain, the noise share is at least 0.10.
- C5 (base result): with noise-free targets, at every method keeps exactly the 12 template pixels and reaches a test MSE (against noise-free targets) of at most .
C1 to C5 are decided on seed 0.
Hypotheses. Decided unrounded, with ties allowed to an absolute :
- H1: at every , test MSE of OBS mag+refit mag. The script prints and for seed 0, and their minima over for every seed.
- H2: OBS keeps at least as many template pixels as mag at every , and more at one at least.
- H3: at every , of OBS OBD mag, the ordering of training error that Hassibi and Stork state, “to second order”, for the error after pruning.
The script uses NumPy 2.3.5 and SciPy 1.16.3 with one BLAS thread and runs in about 9 seconds; two runs gave identical output.
import os
os.environ["OPENBLAS_NUM_THREADS"] = "1"
os.environ["OMP_NUM_THREADS"] = "1"
import numpy as np
from scipy import ndimage, signal
S, M, SIG = 12, 6, 1.0 # 12 x 12 images, 6 px margin, filter sigma in px
N_TR = N_TE = 3000
NOISE = 0.5
KS = [144, 96, 64, 48, 32, 24, 16, 12, 8, 4]
TOL = 1e-12
# impulse response of the filter (normalises each pixel to variance 1)
F = S + 2 * M
delta = np.zeros((F, F)); delta[F // 2, F // 2] = 1.0
IMP = ndimage.gaussian_filter(delta, SIG)
NORM = np.linalg.norm(IMP)
# vignetting gain: 1 - 0.75 r^2 / r_c^2 from the centre (5.5, 5.5); 0.25 at the corner pixels
ii, jj = np.mgrid[0:S, 0:S]
R2 = (ii - 5.5) ** 2 + (jj - 5.5) ** 2
GAIN = 1 - 0.75 * R2 / R2.max()
# template: a horizontal edge detector, -1 on row 5 and +1 on row 6, columns 1-6
WSTAR = np.zeros((S, S)); WSTAR[5, 1:7] = -1.0; WSTAR[6, 1:7] = 1.0
WSTAR = WSTAR.ravel()
SUPP = set(np.flatnonzero(WSTAR))
def images(n, rng):
field = rng.standard_normal((n, F, F))
bg = ndimage.gaussian_filter(field, (0, SIG, SIG))[:, M:M + S, M:M + S] / NORM
return bg, (GAIN * bg).reshape(n, -1)
def loss(X, y, w):
r = X @ w - y
return 0.5 * (r @ r) / len(y)
def lstsq_on(X, y, keep):
w = np.zeros(X.shape[1])
w[keep] = np.linalg.lstsq(X[:, keep], y, rcond=None)[0]
return w
def obs_path(H, w0, ks):
"""Iterative OBS: remove the weight with the smallest L_q, update the survivors (Eq. 5)."""
alive = list(range(len(w0)))
w = w0.copy()
Hinv = np.linalg.inv(H) # inverse of H restricted to `alive`
out = {len(w0): w.copy()}
while len(alive) > min(ks):
wa = w[alive]
L = wa ** 2 / (2 * np.diag(Hinv))
j = int(np.argmin(L))
dw = -(wa[j] / Hinv[j, j]) * Hinv[:, j]
w[alive] = wa + dw
w[alive[j]] = 0.0
Hinv = Hinv - np.outer(Hinv[:, j], Hinv[j, :]) / Hinv[j, j]
Hinv = np.delete(np.delete(Hinv, j, 0), j, 1)
del alive[j]
if len(alive) in ks:
out[len(alive)] = w.copy()
return out
def run(seed, noise=NOISE, verbose=False):
rng = np.random.default_rng(seed)
bg_tr, Xtr = images(N_TR, rng)
_, Xte = images(N_TE, rng)
ytr = Xtr @ WSTAR + noise * rng.standard_normal(N_TR)
yte = Xte @ WSTAR + noise * rng.standard_normal(N_TE)
H = Xtr.T @ Xtr / N_TR
w = np.linalg.lstsq(Xtr, ytr, rcond=None)[0]
E0 = loss(Xtr, ytr, w)
res = {"bg_var": bg_tr.var(), "E0": E0, "full_test": np.mean((Xte @ w - yte) ** 2)}
# C1, C2: single deletions from the full fit
Hinv = np.linalg.inv(H)
c1 = c2 = 0.0
for q in range(len(w)):
keep = np.array([p for p in range(len(w)) if p != q])
L_obs = w[q] ** 2 / (2 * Hinv[q, q])
dE_refit = loss(Xtr, ytr, lstsq_on(Xtr, ytr, keep)) - E0
L_obd = 0.5 * H[q, q] * w[q] ** 2
wz = w.copy(); wz[q] = 0.0
dE_zero = loss(Xtr, ytr, wz) - E0
c1 = max(c1, abs(L_obs - dE_refit) / E0)
c2 = max(c2, abs(L_obd - dE_zero) / E0)
res["C1"], res["C2"] = c1, c2
obs = obs_path(H, w, KS)
sal = 0.5 * np.diag(H) * w ** 2
rows, c3 = [], 0.0
for k in KS:
sup = {}
sup["mag"] = np.argsort(-np.abs(w), kind="stable")[:k]
sup["OBD"] = np.argsort(-sal, kind="stable")[:k]
W = {}
for m in ("mag", "OBD"):
W[m] = np.zeros_like(w); W[m][sup[m]] = w[sup[m]]
W["OBS"] = obs[k]
sup["OBS"] = np.flatnonzero(obs[k]) if k < 144 else np.arange(144)
W["mag+refit"] = lstsq_on(Xtr, ytr, np.sort(sup["mag"]))
sup["mag+refit"] = sup["mag"]
c3 = max(c3, np.abs(W["OBS"] - lstsq_on(Xtr, ytr, np.sort(sup["OBS"]))).max() / np.abs(w).max())
row = {"k": k}
for m in ("mag", "OBD", "OBS", "mag+refit"):
row[m] = (loss(Xtr, ytr, W[m]) - E0, np.mean((Xte @ W[m] - yte) ** 2),
len(SUPP & set(int(i) for i in sup[m])), len(sup[m]))
rows.append(row)
res["C3"], res["rows"] = c3, rows
return res
def verdicts(rows):
h1 = all(r["OBS"][1] <= r["mag+refit"][1] + TOL and r["mag+refit"][1] <= r["mag"][1] + TOL for r in rows)
sub = [r for r in rows if r["k"] < 144]
h2 = all(r["OBS"][2] >= r["mag"][2] for r in sub) and any(r["OBS"][2] > r["mag"][2] for r in sub)
h3 = all(r["OBS"][0] <= r["OBD"][0] + TOL and r["OBD"][0] <= r["mag"][0] + TOL for r in sub)
return h1, h2, h3
# ---- data checks (seed 0) -------------------------------------------------
print(f"C4(i) gain min {GAIN.min():.4f} max {GAIN.max():.4f} ratio {GAIN.max() / GAIN.min():.4f}"
f" (expected 3.975): {abs(GAIN.max() / GAIN.min() - 3.975) <= 1e-3}")
ac = signal.correlate(IMP, IMP, mode="full") / NORM ** 2 # exact background covariance
c0 = ac.shape[0] // 2
def cov_b(p, q):
(a, b), (c, d) = divmod(p, S), divmod(q, S)
di, dj = c - a, d - b
return ac[c0 + di, c0 + dj] if abs(di) <= c0 and abs(dj) <= c0 else 0.0
idx = np.flatnonzero(WSTAR)
gw = (GAIN.ravel() * WSTAR)[idx]
SV = sum(gw[a] * gw[b] * cov_b(idx[a], idx[b]) for a in range(len(idx)) for b in range(len(idx)))
share = NOISE ** 2 / (NOISE ** 2 + SV)
r0 = run(0)
print(f"C4(ii) background pixel variance {r0['bg_var']:.4f}: {abs(r0['bg_var'] - 1) <= 0.02}")
print(f"C4(iii) template nonzeros {np.count_nonzero(WSTAR)}: {np.count_nonzero(WSTAR) == 12}")
print(f"C4(iv) full-fit test MSE {r0['full_test']:.6f} (floor 0.25): {r0['full_test'] <= 0.275}")
print(f"C4(v) exact signal variance {SV:.4f}, noise share {share:.4f}: {share >= 0.10}")
print(f"C1 OBS L_q vs refit dE, max |diff|/E: {r0['C1']:.1e}: {r0['C1'] <= 1e-9}")
print(f"C2 OBD s_q vs zeroing dE, max |diff|/E: {r0['C2']:.1e}: {r0['C2'] <= 1e-9}")
print(f"C3 iterative OBS vs lstsq on its support, max |diff|/max|w|: {r0['C3']:.1e}: {r0['C3'] <= 1e-6}")
rz = run(0, noise=0.0)
r12 = [r for r in rz["rows"] if r["k"] == 12][0]
ok = all(r12[m][2] == 12 and r12[m][3] == 12 and r12[m][1] <= 1e-20 for m in ("mag", "OBD", "OBS", "mag+refit"))
print("C5 noise-free, k = 12: " + " ".join(f"{m} hits {r12[m][2]} MSE {r12[m][1]:.1e}"
for m in ("mag", "OBD", "OBS", "mag+refit")) + f": {ok}")
print("\nseed 0: training-loss increase dE | test MSE | true pixels kept (of 12)")
print(f"{'k':>4} " + " ".join(f"{m:>11}" for m in ("mag", "OBD", "OBS", "mag+refit")) + " | "
+ " ".join(f"{m:>9}" for m in ("mag", "OBD", "OBS", "mag+refit")) + " | hits m/D/S")
for r in r0["rows"]:
print(f"{r['k']:>4} " + " ".join(f"{r[m][0]:11.4e}" for m in ("mag", "OBD", "OBS", "mag+refit")) + " | "
+ " ".join(f"{r[m][1]:9.6f}" for m in ("mag", "OBD", "OBS", "mag+refit"))
+ f" | {r['mag'][2]:2d}/{r['OBD'][2]:2d}/{r['OBS'][2]:2d}")
print("\nseed 0, H1 margins: d1 = MSE(mag+refit) - MSE(OBS), d2 = MSE(mag) - MSE(mag+refit)")
print(" " + " ".join(f"k={r['k']}: {r['mag+refit'][1] - r['OBS'][1]:.3e}, {r['mag'][1] - r['mag+refit'][1]:.3e}"
for r in r0["rows"]))
print("\nper seed: H1 (test MSE OBS <= mag+refit <= mag, every k), H2 (OBS hits >= mag, > once), "
"H3 (train dE OBS <= OBD <= mag, every k < 144)")
for s in range(5):
rs = r0 if s == 0 else run(s)
h1, h2, h3 = verdicts(rs["rows"])
fails1 = [r["k"] for r in rs["rows"] if not (r["OBS"][1] <= r["mag+refit"][1] + TOL and r["mag+refit"][1] <= r["mag"][1] + TOL)]
fails3 = [r["k"] for r in rs["rows"] if r["k"] < 144 and not (r["OBS"][0] <= r["OBD"][0] + TOL and r["OBD"][0] <= r["mag"][0] + TOL)]
hits = " ".join(f"{r['mag'][2]}/{r['OBS'][2]}" for r in rs["rows"])
m1 = min(r["mag+refit"][1] - r["OBS"][1] for r in rs["rows"]); m2 = min(r["mag"][1] - r["mag+refit"][1] for r in rs["rows"])
sub = [r for r in rs["rows"] if r["k"] < 144]
m3 = min(r["OBD"][0] - r["OBS"][0] for r in sub); m4 = min(r["mag"][0] - r["OBD"][0] for r in sub)
print(f"seed {s}: H1 {h1} (min d1 {m1:.3e}, min d2 {m2:.3e}, fails at k {fails1}) H2 {h2} (mag/OBS hits {hits})"
f" H3 {h3} (min dE(OBD)-dE(OBS) {m3:.3e}, min dE(mag)-dE(OBD) {m4:.3e}, fails at k {fails3})")
C4(i) gain min 0.2500 max 0.9938 ratio 3.9752 (expected 3.975): True
C4(ii) background pixel variance 0.9943: True
C4(iii) template nonzeros 12: True
C4(iv) full-fit test MSE 0.264451 (floor 0.25): True
C4(v) exact signal variance 6.5156, noise share 0.0370: False
C1 OBS L_q vs refit dE, max |diff|/E: 5.8e-14: True
C2 OBD s_q vs zeroing dE, max |diff|/E: 5.9e-14: True
C3 iterative OBS vs lstsq on its support, max |diff|/max|w|: 1.6e-12: True
C5 noise-free, k = 12: mag hits 12 MSE 1.1e-28 OBD hits 12 MSE 1.1e-28 OBS hits 12 MSE 4.6e-30 mag+refit hits 12 MSE 4.9e-30: True
seed 0: training-loss increase dE | test MSE | true pixels kept (of 12)
k mag OBD OBS mag+refit | mag OBD OBS mag+refit | hits m/D/S
144 0.0000e+00 0.0000e+00 0.0000e+00 0.0000e+00 | 0.264451 0.264451 0.264451 0.264451 | 12/12/12
96 3.0513e-01 2.7293e-01 7.0838e-04 1.6317e-03 | 0.929769 0.857457 0.264640 0.262753 | 10/12/ 8
64 2.8585e+00 5.1672e-01 2.2116e-03 3.9339e-03 | 6.093377 1.244433 0.262849 0.263523 | 9/10/ 8
48 1.8179e+00 3.3921e+00 2.9090e-03 5.4382e-03 | 3.864457 7.247424 0.261936 0.265694 | 8/ 9/ 8
32 3.3587e+00 2.5915e+00 4.8304e-03 1.9583e-02 | 7.184288 5.963359 0.261258 0.283967 | 8/ 8/ 8
24 2.3285e+00 3.2765e+00 6.8556e-03 2.6274e-02 | 5.210848 6.843112 0.262882 0.291883 | 8/ 8/ 8
16 2.7340e+00 5.0412e+00 1.3389e-02 3.3805e-02 | 5.796350 10.707597 0.272136 0.299763 | 6/ 6/ 8
12 5.2000e+00 3.1772e+00 1.8673e-02 3.6026e-01 | 10.220748 6.450695 0.277586 0.927381 | 5/ 6/ 8
8 7.6091e+00 7.6091e+00 2.3538e-02 3.8410e-01 | 15.316302 15.316302 0.284023 0.976717 | 5/ 5/ 6
4 9.1058e-01 9.1058e-01 4.7153e-01 4.7153e-01 | 2.020972 2.020972 1.138771 1.138771 | 4/ 4/ 4
seed 0, H1 margins: d1 = MSE(mag+refit) - MSE(OBS), d2 = MSE(mag) - MSE(mag+refit)
k=144: 0.000e+00, 0.000e+00 k=96: -1.887e-03, 6.670e-01 k=64: 6.735e-04, 5.830e+00 k=48: 3.758e-03, 3.599e+00 k=32: 2.271e-02, 6.900e+00 k=24: 2.900e-02, 4.919e+00 k=16: 2.763e-02, 5.497e+00 k=12: 6.498e-01, 9.293e+00 k=8: 6.927e-01, 1.434e+01 k=4: 9.370e-14, 8.822e-01
per seed: H1 (test MSE OBS <= mag+refit <= mag, every k), H2 (OBS hits >= mag, > once), H3 (train dE OBS <= OBD <= mag, every k < 144)
seed 0: H1 False (min d1 -1.887e-03, min d2 0.000e+00, fails at k [96]) H2 False (mag/OBS hits 12/12 10/8 9/8 8/8 8/8 8/8 6/8 5/8 5/6 4/4) H3 False (min dE(OBD)-dE(OBS) 2.722e-01, min dE(mag)-dE(OBD) -2.307e+00, fails at k [48, 24, 16])
seed 1: H1 True (min d1 0.000e+00, min d2 0.000e+00, fails at k []) H2 True (mag/OBS hits 12/12 9/10 9/9 9/9 7/9 6/9 6/8 4/7 3/7 2/4) H3 False (min dE(OBD)-dE(OBS) 2.227e-01, min dE(mag)-dE(OBD) -3.572e+00, fails at k [12])
seed 2: H1 False (min d1 -3.032e-03, min d2 0.000e+00, fails at k [96]) H2 True (mag/OBS hits 12/12 11/12 9/12 8/12 7/12 7/12 6/12 6/12 4/8 2/4) H3 False (min dE(OBD)-dE(OBS) 1.199e-01, min dE(mag)-dE(OBD) -1.117e+00, fails at k [48, 12, 4])
seed 3: H1 False (min d1 -4.376e-03, min d2 0.000e+00, fails at k [96]) H2 True (mag/OBS hits 12/12 10/11 9/10 9/10 9/10 6/10 5/9 4/8 4/8 4/4) H3 False (min dE(OBD)-dE(OBS) 2.035e-01, min dE(mag)-dE(OBD) -3.291e+00, fails at k [64, 48, 32, 12, 8])
seed 4: H1 False (min d1 -2.390e-03, min d2 0.000e+00, fails at k [96]) H2 True (mag/OBS hits 12/12 12/12 11/12 11/12 9/12 8/12 5/12 5/12 4/8 3/4) H3 False (min dE(OBD)-dE(OBS) 1.512e-01, min dE(mag)-dE(OBD) -3.809e-01, fails at k [64, 24, 4])
Checks. C1, C2 and C3 held, with largest relative differences of , and against bars of , and . For C1 and C2 this is what the derivation predicts (our derivation): with a quadratic loss and zero gradient at the least-squares fit, the Taylor expansion has no remainder, so OBS’s and OBD’s saliency are the exact loss increases of their deletions, and the differences are rounding. C3 shows that the downdated inverse reproduces a fresh least-squares fit on each support. The data checks C4(i) to C4(iv) held: a gain ratio of 3.9752, a background variance of 0.9943, 12 template pixels and a full-fit test MSE of 0.264451 against the bar of 0.275. C5 held: on noise-free targets, all four methods keep the 12 template pixels at , with test MSEs of (mag and OBD), (OBS) and (mag+refit).
C4(v) failed: the exact signal variance is 6.5156, so the noise share is 0.0370, below the bar of 0.10.
The pruning table (seed 0). Without a refit, mag and OBD raise the training loss by 0.27 to 7.6 at every below 144, and their test MSEs lie between 0.857457 and 15.316302, against 0.264451 for the full fit. OBS raises the training loss by 0.00070838 at and by 0.023538 at , and its test MSE stays between 0.261258 and 0.284023 down to . mag+refit lies between the two: its training-loss increase is above OBS’s at every from 96 to 8, and equal to it at , where the two also print the same test MSE, 1.138771. At , mag+refit’s test MSE is 0.927381 and OBS’s 0.277586.
Hypotheses. H1 failed on seeds 0, 2, 3 and 4, in each case at only, where OBS’s test MSE exceeds mag+refit’s by , , and . H1 held on seed 1. Its second inequality, mag+refit no worse than mag, held at every on every seed.
H2 failed on seed 0, where mag keeps 10 template pixels and OBS 8 at , and 9 against 8 at . H2 held on seeds 1 to 4.
H3 failed on every seed, through its second inequality: OBD’s training-loss increase exceeds mag’s at some on each seed (on seed 0 at , 24 and 16). Its first inequality, OBS no worse than OBD, held at every on every seed, with smallest margins of OBD over OBS of 0.2722, 0.2227, 0.1199, 0.2035 and 0.1512 on seeds 0 to 4.
How the example was planned. The set-up, the checks C1 to C5 and the hypotheses were written before any example script ran. A planning script, a copy of this script with extra unrounded prints, then ran the same set-up and printed every outcome before the plan was frozen, so the example illustrates rather than tests H1 to H3; that script’s running time, about 9 seconds, served as the runtime estimate. H3 was added at planning; the batch plan named H1 and H2. No bar was written after that script. C4(v) failed in the planning script and again in the pilot, and the set-up was kept unchanged. Compared with the batch plan’s description, the example fixes the open choices (the filter width, field size and crop, the unit-variance scaling, the gain formula, whose “4×” is 3.975 at pixel centres, the template, the noise level, the values of and seeds 0 to 4); writes the loss with as Hassibi and Stork do, a change of scale only; implements OBS with the restricted inverse, where the paper inverts with between and and recomputes, and ours downdates the restricted inverse with no because is full rank; normalizes the exact checks by rather than by each ; adds C3, the data checks C4 and the noise-free check C5; adds H3; evaluates each hypothesis on five seeds; makes H2’s “recovers more” decidable as stated above; prunes OBD in one shot from the full fit, without the retraining of OBD’s recipe; and leaves out the channel-pruning part the plan had declined. The pilot and the first run printed the same output.
Variants
Schedules. Hoefler et al. (§2.4) distinguish three schedules: train then sparsify, the most common, usually followed by fine-tuning; sparsify during training, which starts before convergence and is usually cheaper but more brittle to configure; and sparse training from the start, with weights allowed to regrow. Any of them can be repeated in an outer loop. They list gradual pruning schedules, starting each iteration from the most trained weights, among their best practices (§8.9).
Scope. Scores can be compared within each layer or across the whole network. Network Slimming uses one global threshold; FPGM and ThiNet set a rate per layer; Molchanov et al. state that their criterion has a consistent scale across layers, so it needs no per-layer sensitivity analysis.
Soft and hard removal. FPGM’s algorithm zeroes filters during training and lets them be updated again before the final compact model is built, while OBD and ThiNet delete and freeze. Hoefler et al. (§2.4.2) describe other schemes that keep masked weights and let them return.
Lottery tickets and rewinding. Model Compression describes Frankle and Carbin’s (2019) lottery ticket hypothesis: iterative magnitude pruning (IMP) finds subnetworks that, reset to their original initial values, train to the full network’s accuracy on small datasets. Frankle, Dziugaite, Roy and Carbin (2020) extended IMP to larger settings by rewinding the surviving weights to their values at an early iteration instead of to initialization; Frankle and Carbin’s version is the case . Their instability analysis trains two copies of a network from the same state with different samples of SGD noise and checks whether the error rises along the straight line between the results. They found that standard networks become stable to SGD noise early in training (after about 3% of training for ResNet-20 on CIFAR-10 and 20% for ResNet-50 on ImageNet), that IMP subnetworks reach full accuracy only when they are stable, and that subnetworks of standard ResNet-20, VGG-16, ResNet-50 and Inception-v3 rewound to initialization did no better than random pruning or reinitialization. Rewound early in training, IMP subnetworks of ResNet-50 and Inception-v3 on ImageNet became matching, the term they use instead of “winning tickets” for . They prune 20% of weights per iteration on the smaller networks, following Frankle and Carbin, and prune ImageNet networks in one shot.
Girish, Maiya, Gupta, Chen, Davis and Shrivastava (2021) studied lottery tickets for object detection, instance segmentation and keypoint estimation with Faster R-CNN and Mask R-CNN on Pascal VOC and COCO. They report that tickets found by pruning an ImageNet-pretrained network do not transfer well to these tasks, and give guidance for finding tickets with up to 80% overall sparsity on the sub-tasks without a drop in performance (abstract).
Hoefler et al. (§8.3) treat lottery tickets within the wider literature on sparse training.
Best Practices
- Use a score that sees the data when the inputs are not on one scale. Magnitude assumes an isotropic Hessian (Hassibi and Stork; Hoefler et al.); OBD and OBS, the Taylor criterion and the reconstruction methods weigh each parameter by what it multiplies.
- Compensate before fine-tuning. OBS’s update and the least-squares refits of He et al. and ThiNet adjust the surviving weights without gradient descent; Hassibi and Stork present OBS as not needing retraining after each deletion.
- Prune gradually and fine-tune. Hoefler et al. recommend gradual schedules, starting each iteration from the latest weights, when the aim is inference.
- Allocate sparsity by cost. Prune where parameters and operations are, and treat the first layers with care (Hoefler et al., §3.9, §8.9).
- Report what “pruned” means. State whether percentages are of weights removed or kept, whether they count parameters or operations, and whether the model was rebuilt with smaller shapes; Model Compression gives Blalock et al.’s checklist for comparisons.
Pitfalls
- Trusting a second-order score far from where it was computed. The Taylor expansion is local. OBD’s Figure 1b shows predicted and actual objectives agreeing for about the first 800 deleted parameters (about 30%) and then splitting, which the authors attribute to off-diagonal terms and higher-order terms growing as more and larger parameters are deleted.
- Removing many weights from one score. Scores computed once assume that removed weights do not interact; Hoefler et al. (§3.5.3) note that removing the lowest-scoring weight can make the next one more important.
- Ranking channels by weight norms alone. Yihui He et al. found the absolute-sum criterion sometimes worse than keeping the first channels, and Yang He et al. describe when norm ranking breaks down.
- Confusing rewinding with resetting. Rewinding to an early iteration (Frankle et al., 2020) is not the reset to initialization of the original lottery ticket experiments, and the two give different results on large networks.
- Counting zeros as speed. Unstructured sparsity only saves time where the hardware and software exploit it; time the deployed model.
- Confusing the senses of “pruning”. Pruning a decision tree, suppressing overlapping boxes, pruning hypotheses in a search, and removing images from a dataset are different operations; Dataset Curation describes the last, under the name data pruning.
Evidence and Impact
Second-order pruning is as old as the method itself: OBD (1989) introduced the diagonal saliency, and OBS (1992) the full inverse-Hessian criterion and its weight update, both on networks of nine to a few thousand weights. With deep convolutional networks, structured criteria followed: reconstruction-based channel selection and Network Slimming (2017), first-order Taylor importance and geometric-median redundancy (2019). The results these papers report are on ImageNet, CIFAR-10 and COCO with VGG, ResNet, DenseNet and Inception networks: from ResNet-101’s 40% fewer FLOPs at 0.02% top-1 loss (Molchanov et al.) to VGG-16’s 5× speed-up at 0.3% more error with tensor factorization added (Yihui He et al.) and 20× smaller VGGNets (Liu et al.), each in its own set-up, so, in our reading, they cannot be ranked against each other from their abstracts.
The lottery-ticket line asks why pruned networks train and found that, at scale, the answer depends on rewinding to an early point in training (Frankle et al., 2020) and that tickets can be found for detection and segmentation (Girish et al., 2021). Hoefler et al.’s survey (2021) collects the field: criteria, schedules, layer budgets, hardware support and open questions, among them how structured and unstructured sparsity compare and how to co-design hardware with pruned models.
Related
- Model Quantization
Storing and computing a trained network's weights and activations in low-precision formats such as INT8, INT4 or FP8, with a scale and zero point per tensor, channel or group; the integer arithmetic behind it, post-training calibration, quantization-aware training with the straight-through estimator, and what it costs in accuracy.
- Knowledge Distillation
Training a student network on a teacher network's softened predictions, or on its features or the relations between its outputs; temperature and the T² factor, why soft targets help, logit, feature, relational and self-distillation, born-again networks, the teacher–student capacity gap, function matching with consistent views and long schedules, DeiT's distillation token, and a worked example with an exact teacher.
- Sparse Convolutional Networks
Convolutional networks that store only the occupied sites of a voxel grid, as coordinates and feature rows, and convolve them through precomputed input–output pairs, with regular, submanifold and generalized sparse convolutions and the libraries that run them on LiDAR and indoor scans.
- MobileNet
Google's family of convolutional networks for phones and other small devices, from MobileNet v1 (2017), built from depthwise separable convolutions with width and resolution multipliers, through MobileNetV2's inverted residuals with linear bottlenecks and MobileNetV3's latency-driven architecture search, to MobileNetV4's universal inverted bottleneck and mobile attention (2024).
- LeNet
The family of small convolutional networks for handwritten character recognition that LeCun and colleagues built at Bell Labs from 1989 to 1998, from the zip-code network to LeNet-5, with its trainable subsampling, partial connection table and fixed RBF output codes, and how today's re-implementations differ.
- Linear Regression
The model that predicts a real-valued target as a weighted sum of input features, fitted by ordinary least squares, ridge, lasso or elastic net; what each estimator does to the coefficients, how scikit-learn scales its penalties, and how lasso selects pixels from image patches.
References
- LeCun, Y., Denker, J. S. & Solla, S. A. (1989). Optimal Brain Damage. Advances in Neural Information Processing Systems 2 (NIPS), 598–605.
- Hassibi, B. & Stork, D. G. (1992). Second order derivatives for network pruning: Optimal Brain Surgeon. Advances in Neural Information Processing Systems 5 (NIPS).
- He, Y., Zhang, X. & Sun, J. (2017). Channel Pruning for Accelerating Very Deep Neural Networks. IEEE International Conference on Computer Vision (ICCV) (read in the CVF open-access copy).
- Luo, J.-H., Wu, J. & Lin, W. (2017). ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression. IEEE International Conference on Computer Vision (ICCV) (read in the CVF open-access copy).
- Liu, Z., Li, J., Shen, Z., Huang, G., Yan, S. & Zhang, C. (2017). Learning Efficient Convolutional Networks through Network Slimming. IEEE International Conference on Computer Vision (ICCV) (read in the CVF open-access copy).
- Li, H., Kadav, A., Durdanovic, I., Samet, H. & Graf, H. P. (2017). Pruning Filters for Efficient ConvNets. International Conference on Learning Representations (ICLR) (not read; cited as Model Compression and He, Zhang & Sun describe it).
- Molchanov, P., Mallya, A., Tyree, S., Frosio, I. & Kautz, J. (2019). Importance Estimation for Neural Network Pruning. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (read in the CVF open-access copy).
- He, Y., Liu, P., Wang, Z., Hu, Z. & Yang, Y. (2019). Filter Pruning via Geometric Median for Deep Convolutional Neural Networks Acceleration. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (read in the CVF open-access copy).
- Frankle, J. & Carbin, M. (2019). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. International Conference on Learning Representations (ICLR) (not read; cited as Model Compression and Frankle et al., 2020, describe it).
- Blalock, D., Gonzalez Ortiz, J. J., Frankle, J. & Guttag, J. (2020). What is the State of Neural Network Pruning? Proceedings of Machine Learning and Systems 2 (MLSys), 129–146 (not read; cited as Model Compression reports it).
- Frankle, J., Dziugaite, G. K., Roy, D. M. & Carbin, M. (2020). Linear Mode Connectivity and the Lottery Ticket Hypothesis. Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR 119, 3259–3269.
- Girish, S., Maiya, S. R., Gupta, K., Chen, H., Davis, L. S. & Shrivastava, A. (2021). The Lottery Ticket Hypothesis for Object Recognition. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (read in the CVF open-access copy).
- Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N. & Peste, A. (2021). Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241), 1–124.