Dynamic sparse training

Overview

Dynamic sparse training (DST) keeps a network sparse during the whole run and changes which connections are active as training goes on. The invariant all variants share is a fixed sparsity budget: the number of active weights, and so the training and inference cost, is set before training starts 1911.11134 §1, §3. Each update step drops some active connections and grows the same number elsewhere, so the count stays the same 1911.11134 §3 (2)–(4).

The cards in this corpus cover one method in this family, RigL. The paper also names the other sparse-training methods it compares against (static sparse training, SNIP, SET, DSR, SNFS) 1911.11134 fig. 2; none of them has a card here, so this page does not describe them.

Variants

RigL (gradient-based growth)

Drops the smallest-magnitude active weights and grows the same number at the inactive positions with the largest gradient magnitude, starting them at zero 1911.11134 §3 (3)–(4). The update runs every ΔT = 100 iterations in the main ImageNet runs, with an initial drop fraction α = 0.3 and a cosine decay that stops at T_end 1911.11134 §4, tab. 1, app. J. Card: Rigging the Lottery: Making All Tickets Winners.

Random growth (SET-style)

The paper describes SET as the predecessor that grows connections at random 1911.11134 §2. It is a baseline in the paper's ImageNet table, where RigL beats it at both reported sparsities (74.6 vs 72.9 top-1 at 80%; 72.0 vs 69.6 at 90%) 1911.11134 fig. 2. The Erdős–Rényi distribution used by RigL comes from SET 1911.11134 §3 (1).

Sparsity distribution

Not a separate method but a choice every variant makes. The paper compares Uniform, Erdős–Rényi (ER) and Erdős–Rényi-Kernel (ERK); the latter two give larger layers a lower sparsity 1911.11134 §3 (1). Under ERK, RigL at 80% reaches 75.1% top-1 with 0.42x training FLOPs, against 74.6% at 0.23x with uniform sparsity 1911.11134 fig. 2. The two rows do not share a budget, so the gain is not a like-for-like comparison.

Drop schedule

The fraction of connections replaced per update decays over training. The paper uses cosine decay and reports that it works slightly better than the alternatives; constant and inverse-power schedules are in its appendix 1911.11134 §3 (2), app. G.

When to use which

Choose by constraint. The numbers are the paper's, on ImageNet ResNet-50 unless noted, and most baselines come from the original papers rather than the authors' reruns 1911.11134 fig. 2.

The cost of the dense gradient at update steps is amortised only when ΔT > 1/(1 − S), where S is the sparsity; at 99% sparsity this needs ΔT > 100 1911.11134 §3, app. H. The FLOP counts are estimates and do not measure wall-clock time 1911.11134 app. H.

Implementation sketch

Common core of the RigL-style method. Variants differ in the grow rule, the sparsity distribution and the decay schedule.

# Random sparse start with fixed per-layer sparsity   [arxiv:1911.11134 §3 (1)]
masks = random_masks(network, sparsities)
weights = init_weights(network) * masks

for step in range(num_steps):
    # Ordinary sparse SGD step on the active weights   [arxiv:1911.11134 alg. 1]
    loss = forward(network, weights * masks, batch)
    if step % dT == 0 and step < T_end:
        # Fraction to replace, decays with cosine      [arxiv:1911.11134 §3 (2)]
        frac = decay(step, alpha, T_end)
        for layer in layers:
            # Count is the same for drop and grow        [arxiv:1911.11134 §3 (2)]
            k = frac * (1 - sparsity[layer]) * layer.size
            # Drop k active weights of smallest magnitude [arxiv:1911.11134 §3 (3)]
            drop = smallest_k(abs(weights[layer]), k, masks[layer])
            masks[layer][drop] = 0
            # Grow k inactive positions with largest dense gradient
            #                                            [arxiv:1911.11134 §3 (4)]
            grad = dense_gradient(loss, layer)
            grow = largest_k(abs(grad), k, masks[layer] == 0)
            # New connections start at zero              [arxiv:1911.11134 §3 (4)]
            weights[layer][grow] = 0
            masks[layer][grow] = 1

Implementation notes that the paper leaves open or that differ from the reference code are listed on the card, not repeated here: Rigging the Lottery, section "Paper vs code" and "Pitfalls". They cover the momentum state of regrown connections, the first-layer rule, the drop-score tie-breaking and the ERK solve.

Contradictions

• Pruning parity. On CIFAR-10 with WideResNet-22-2, RigL "matches pruning with a fraction of the training resources" 1911.11134 §4.3. On character-level WikiText-103, RigL "does not match magnitude pruning" 1911.11134 §4.2. Both are the authors' results. The character-level values appear only in a figure, so the gap cannot be measured from the text.
• Within the paper's ImageNet table. The Static (ERK) row under the 95% and 96.5% headers repeats the 80% and 90% values, including the FLOPs 1911.11134 app. L, tab. 4. The paper does not explain this. Check it against a run before you cite those numbers.

Papers

• Rigging the Lottery: Making All Tickets Winners: RigL, a drop-and-grow rule that uses gradient magnitude for growth, with zero-initialised new connections and a fixed sparsity budget.