Rewinding to iteration k, not initialization

Frankle and Carbin’s 2019 result reset the pruning mask to the network’s original initialization W_0. For small networks (LeNet, small CIFAR CNNs) this reliably produced sparse subnetworks that trained to full accuracy. But when people tried the same recipe on ResNet-50 for ImageNet, the winning tickets evaporated: pruned-and-reset-to-W_0 subnetworks trained to noticeably worse accuracy than the dense model, no better than a randomly pruned network.

The fix, from Frankle, Dziugaite, Roy and Carbin (2020), is rewinding: rather than resetting surviving weights to W_0, reset them to their values W_k at some early iteration k — typically a fraction of a percent to a few percent into training. With that one substitution, matching subnetworks reappear at ResNet/ImageNet scale. The hypothesis was never wrong about sparse trainable subnetworks existing; it was wrong about the reference point they are trainable from.

Advertisement

Iterative magnitude pruning with rewinding, precisely

The concrete algorithm (IMP with rewinding) is a loop:

1. Randomly initialize W_0; train briefly to step k, saving W_k.
2. Continue training to convergence, W_final.
3. Prune the p% smallest-magnitude weights -> mask m.
4. Reset the SURVIVING weights to W_k (NOT W_0): W = m ⊙ W_k.
5. Retrain the masked network from W_k to convergence.
6. Repeat 2-5 on the sparser network until target sparsity.

Two design choices carry all the weight. First, pruning is iterative: removing (say) 20% per round and retraining between rounds finds far better masks than one-shot pruning to the same final sparsity, because each round re-estimates importance on a network already adapting to being sparse. Second, the rewind point is k, not 0 — the mask is still chosen by magnitude at convergence; only the weights you rewind to change.

Advertisement

Linear mode connectivity: the diagnostic

Why should rewinding a few hundred steps matter so much? The 2020 paper answers with linear mode connectivity (LMC). Take two trained networks with weights W_A and W_B and interpolate linearly between them, W(α) = (1−α)·W_A + α·W_B for α ∈ [0,1]. Evaluate the error along that straight line. Define the error barrier as the highest error on the path minus the mean error of the two endpoints:

barrier = max_α E(W(α))  −  (E(W_A) + E(W_B)) / 2

Two networks are linearly mode connected when that barrier is near zero: you can walk in a straight line from one to the other without the loss rising. A large barrier means the straight path climbs a ridge, so the two solutions sit in effectively different basins. LMC is stricter than general mode connectivity, which allows curved low-loss paths; here the path must be a naive average of parameters.

Stability to SGD noise

The bridge from LMC to lottery tickets is stability. Take the weights W_k at step k and finish training two copies from there, using two different samples of SGD randomness (data ordering and augmentation). Call the results W_A and W_B. The network is stable to SGD noise at step k if those two independently finished copies are linearly mode connected — the error barrier between them is essentially zero.

The empirical finding is the crux of the whole story: IMP finds a matching sparse subnetwork exactly when it rewinds to a step k at which the network has become stable. At k = 0 large networks are unstable — two runs from raw init land in different basins with a big barrier — and rewinding there produces no ticket. After a short amount of training the barrier collapses, and rewinding to that stable point yields sparse subnetworks that match the dense model. Stability is the predictor; the rewind step is chosen to reach it.

Why instability at init kills the ticket

The picture is geometric. Early SGD is chaotic: the first steps take large, noise-amplifying strides, so two runs from the same W_0 diverge into different loss basins. A pruning mask is computed from one converged solution, so retraining that mask from W_0 asks the network to reach the mask’s basin from a start whose own trajectory may head elsewhere — mask and init are mismatched.

Once the network is stable, all its finishing trajectories share one basin, so the mask is consistent with the rewound weights: retraining from W_k descends into the same low-loss region the mask was read off of. Small networks are stable almost from init — precisely why the original k = 0 recipe worked for them and only for them.

A worked barrier example

Make it concrete. Suppose two finished copies from W_k both reach 5.0% test error, and you sweep α from 0 to 1, measuring each averaged network:

Stable case:   endpoint errors 5.0%, 5.0%;  worst midpoint 5.3%
  barrier = 5.3% − (5.0% + 5.0%)/2 = 0.3%   -> connected, MATCHING ticket

Unstable case: endpoint errors 5.0%, 5.0%;  worst midpoint 34%
  barrier = 34%  − (5.0% + 5.0%)/2 = 29%    -> different basins, NO ticket

A barrier of 0.3% is within measurement noise: the averaged network is as good as its endpoints, so a straight line of parameters stays in one basin. A barrier of 29% means averaging the two solutions destroys them — they live in separate basins. ‘Stable’ is just ‘barrier ≈ 0’, and the transition from large to near-zero barrier is typically sharp and happens early in training.

Scaling: what rewinding buys at ResNet/ImageNet size

The scaling result is the practical payoff. On ImageNet-scale ResNets, IMP with rewinding produces subnetworks that match dense accuracy up to substantial sparsity (often 70–90% of weights removed), while IMP-to-W_0 and random pruning at the same sparsity do not — the difference between a real winning ticket and a dead one.

It scales because k is a knob: bigger, more sensitive networks need a slightly later rewind, and you can measure the barrier versus k and pick the earliest step where it collapses. This reframes the hypothesis for large models — not ‘winning tickets exist at initialization’ but ‘at an early, stable point in training,’ a weaker and more robust statement that survives large-scale experiments.

Pruning at initialization: SNIP, GraSP, SynFlow

If tickets really lived at init, we could skip training the dense network and prune W_0 directly. Several methods try: SNIP (Lee et al. 2019) keeps weights whose removal would most change the loss, scored by |g ⊙ W| on one minibatch; GraSP (Wang et al. 2020) preserves gradient flow via a Hessian-vector product; SynFlow (Tanaka et al. 2020) prunes data-free while provably avoiding layer collapse, the failure where a whole layer is pruned away and signal can no longer propagate.

These are useful, but the sobering finding (Frankle et al. 2021, ‘Pruning Neural Networks at Initialization: Why Are We Missing the Mark?’) is that at fixed sparsity they are often no better than randomly shuffling the mask within each layer — they discover a good per-layer sparsity budget, not a specific set of important connections. IMP with rewinding, which looks at trained magnitudes, still beats them: finding the right mask needs signal from training.