Nudged elastic band

Overview

Two separately trained networks sit at minima of the training loss. A minimum energy path (MEP) is a continuous path between them that keeps the largest loss on the path as low as possible. The maximum on the path is the saddle, and it is the number that matters for asking whether the two minima are connected without a loss barrier 1803.00885 §3.1.

The nudged elastic band (NEB) approximates an MEP with a finite chain of pivots. Each pivot is a full parameter vector. The chain is moved so that the path settles onto a low-loss route while the pivots stay spread along it 1803.00885 §3.1. The method comes from chemistry, where it is used to find the lowest pass between two stable molecular shapes 1803.00885 §1.

The invariant all variants share: the two endpoints are fixed at the minima, and the loss along the path is only sampled at finitely many points. The saddle is therefore an upper bound on the true barrier, not a certified value 1803.00885 §3.2.

Variants

Plain NEB with spring forces

Pivots are linked by springs. The total energy is the sum of the pivot losses and the spring energies, and the force on each interior pivot is the loss force with its component along the path removed, plus the spring force along the path 1803.00885 §3.1 1803.00885 eq. 1 1803.00885 eq. 2 1803.00885 eq. 3. The spring constant sets how evenly the pivots are spaced. The card for this paper lists the full equations (card).

String-method variant (infinite spring constant)

The authors set the spring constant to infinity and re-space the pivots at every step instead, so no spring force is used. The paper calls this the string-method variant 1803.00885 §3.1. It is the variant used in all the reported experiments 1803.00885 §4.1. The paper does not state the target spacing it re-spaces to; see Contradictions.

AutoNEB: adaptive pivot insertion

AutoNEB runs NEB for a short cycle, then inserts new pivots into gaps where the loss is poorly approximated by linear interpolation between the two neighbouring pivots 1803.00885 alg. 2 1803.00885 app. A. The insertion test compares that residual with a threshold, normalised by the range of the pivot losses 1803.00885 eq. 4. The paper gives the experiment schedule as 14 cycles with step counts and learning rates that fall across the cycles 1803.00885 §4.1. Each cycle uses a fresh optimiser 1803.00885 §4.1.

The paper's own threshold is given in prose as 20% 1803.00885 §4.1; see Contradictions before using a value.

Connecting many minima

One path per pair of minima is too few to describe a landscape. The paper runs AutoNEB on chosen pairs, keeps the saddle of each connected pair, and reduces the graph of pairs to a minimum spanning tree weighted by saddle training loss 1803.00885 §4 1803.00885 alg. 3. It also states that a full AutoNEB run costs about as much as training the network once per minimum pair 1803.00885 §3.2.

When to use which

The paper reports one method family on CIFAR-10 and CIFAR-100, and it does not compare these variants with each other or with other path finders. The table below states what each variant does and what the paper supports. It does not rank them.

Reported results (author-reported, from 1803.00885 app. B and 1803.00885 §4.3):

• For the deepest CIFAR-10 models the saddle training loss is close to the minimum: DenseNet-100-12-BC goes from 0.0005 to 0.0026 1803.00885 app. B.
• ResNet-20 on CIFAR-10 goes from 0.0162 to 0.0324, a factor of 2.0 1803.00885 app. B.
• Test error rises along the paths by at most 0.5 points on CIFAR-10 and 2.2 points on CIFAR-100 for the deep architectures 1803.00885 §4.3.
• Barriers are larger on CIFAR-100 than on CIFAR-10 1803.00885 §4.3. The paper's summary is that barriers fall as networks get deeper and wider, but the factor column is not monotone: ResNet-56 has 6.5 on CIFAR-10 against 4.8 for DenseNet-100-12-BC 1803.00885 app. B.
• The paper uses 10 minima per architecture, so the results come from a small set of minima 1803.00885 §4.

The paper's result is a suggestion that good solutions may lie on one connected low-loss region. It is not a proof, and the paper says it lacks a formal characterisation of when this holds 1803.00885 §5.

Implementation sketch

Our own pseudocode, following the string-method update and AutoNEB insertion described above. The pivot count, threshold and schedule are the values discussed in Contradictions, not settled facts.

# Connect two minima with an AutoNEB-style chain  [arxiv:1803.00885 alg. 2]
# first, second: parameter vectors at minima (endpoints, fixed)
# cycles: list of (steps, lr) per cycle  [arxiv:1803.00885 §4.1]

def auto_neb(first, second, cycles, threshold):
    # Start with a straight line between the minima  [arxiv:1803.00885 §3.1]
    pivots = interpolate_line(first, second, interior=3)
    fractions = equal_fractions(len(pivots) - 1)
    for index, (steps, lr) in enumerate(cycles):
        if index > 0:
            # Insert pivots where linear interpolation fits poorly  [arxiv:1803.00885 app. A]
            pivots, fractions = insert_at_largest_residuals(
                pivots, fractions, threshold
            )
        # Fresh optimiser each cycle  [arxiv:1803.00885 §4.1]
        momenta = zeros_like(pivots[1:-1])
        for _ in range(steps):
            # Re-space pivots, then move each interior pivot  [arxiv:1803.00885 §3.1]
            pivots, momenta = neb_update(pivots, momenta, fractions, lr)
        # Sample densely between pivots to estimate the saddle  [arxiv:1803.00885 §4.1]
        dense = evaluate_densely(pivots, points_per_gap=9)
    # Saddle is the largest sampled loss, an upper bound  [arxiv:1803.00885 §3.2]
    return pivots, max(dense)

The per-step update keeps only the loss gradient component perpendicular to the local path tangent, then applies the optimiser step. The tangent comes from the neighbouring pivots with the higher loss 1803.00885 §3.1 1803.00885 alg. 1.

Contradictions

• Insertion threshold. The paper's text gives 20% of the total energy difference 1803.00885 §4.1. The released code's default is 0.1 and no shipped config overrides it. The number of pivots depends on the threshold, so the paper's reported saddles cannot be tied to one value (card, Paper vs code).
• Appendix text vs table. Appendix B gives a ResNet error rise of up to 0.7 points on CIFAR-10 and 2.9 on CIFAR-100, but its own table gives 0.5 and 2.2 1803.00885 app. B 1803.00885 §4.3. Section 4.3 matches the table. The table is used on this page.
• Training length. The paper gives 136 and 266 epochs for the minima 1803.00885 app. B. The released configs give step counts that work out to about 164 and 320 epochs on the CIFAR-10 training set (card, Paper vs code).
• Path length. The paper gives the path length relative to the straight segment as "between 50% to 2.5 times" 1803.00885 §4.4. The wording is ambiguous, so this page does not give a number.
• Hessian claim. The arXiv abstract says every minimum has at least one vanishing Hessian eigenvalue beyond the trivial ones. The body has no Hessian computation 1803.00885 §6. Treat the body as the evidence.

Papers

• Essentially No Barriers in Neural Network Energy Landscape: applies AutoNEB to CIFAR-10/100 CNNs, ResNets and DenseNets, and reports low-loss paths between independently trained minima.