Flat minima

Overview

Deep networks often reach zero training error and still differ widely on new data. Classical generalisation bounds cover the whole hypothesis class, so they cannot say which of many zero-error solutions will generalise 1706.10239 §2.2.

The flat-minima idea says that the local geometry of the training loss at a solution matters. A solution in a wide basin of attraction is expected to generalise better than one in a narrow, sharp basin, and ordinary training from a random start tends to land in a wide basin 1706.10239 §1 §3.2. The paper uses "flat" as the umbrella term; its own words are wide basins and sharpness. Sharpness is read through the Hessian of the training loss: large positive eigenvalues mark directions in which the loss rises quickly, so the basin is narrow 1706.10239 §5.2.

The shared invariant across the variants below: two solutions can have the same training error and still differ in the width of the basin around them, and the claim is that this width tracks generalisation.

Variants

The paper offers four distinct tools. They answer different questions, so pick by the question you need answered.

Basin-volume argument for random starts

The claim: gradient-based training from a random start converges to a good basin with probability close to 1, and to a bad one with probability close to 0 1706.10239 eq. 4. For a uniform start distribution this becomes a volume ratio that is close to 0 eq. 5. The authors call the ratio a conjecture; they check it only empirically §3.2.

The supporting experiment: six random initialisations all reached good solutions. LeNet on MNIST reached 98.99 to 99.19 % test accuracy and ResNet-18 on CIFAR-10 reached 79.06 to 84.56 % 1706.10239 tab. 2. Card: Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes.

Hessian-norm complexity bound for two-layer networks

For a two-layer network with hidden-unit weights b_k, biases c_k and output weights a_k, under least-squares loss, the paper bounds the expected squared input-gradient norm by a weight-norm term plus the Frobenius norm of a Fisher matrix 1706.10239 eq. 10. Replacing the Fisher matrix with the Hessian of the empirical risk, with respect to the hidden biases c, gives a bound with an extra error term of order √(Var/N). The paper leaves that term unquantified eq. 11 app. C. For ReLU activations the second-derivative constant is zero §4.

The bound covers two-layer networks only. The authors leave deeper networks to future work §4 and call a theoretical justification for them an open challenge §6.

Hessian-spectrum volume proxy V(k)

Sum the logs of the k largest positive Hessian eigenvalues [arxiv:1706.10239 eq. 13] §5.2. Larger values mean a sharper minimum §5.2. The authors call it a rough estimate and state that it cannot separate minima with equal generalisation §5.3. They applied it to a small network with 3,781 parameters app. A; k is not stated.

Probe estimate of the Hessian Frobenius norm

For larger models, estimate ‖H‖²_F with random Gaussian probe vectors and central differences of the gradient 1706.10239 eq. 14 §5.3. The paper used M = 100 probes and ε = 10⁻⁵ on ResNet-32 with about 0.5 M parameters §5.3. The estimate is exact only in the limit of many probes and small ε §5.3. Figure 3 relates test accuracy to both the volume proxy and this estimate; the authors describe the correlation as not tight and report no coefficient §5.3.

Building bad minima on purpose

To obtain solutions that fit the training set but generalise poorly, the paper adds a term that penalises the loss on an attack set with deliberately wrong labels, weighted by γ 1706.10239 eq. 12 §5.1. For the small networks, the first 512 training points were used for training and the rest as the attack set §5.3. This is a way to produce test material for the measures above, not a measure in its own right. The label assignment, γ and the attack-set size are not stated for each run §5.1.

When to use which

Implementation sketch

The two computations a reader is most likely to implement. Both follow the paper's definitions; the paper gives no reference code, so the details below are our own reading 1706.10239 eq. 13 eq. 14.

# Probe estimate of ||H||_F^2 without forming H  [§5.3] [eq. 14]
# Input:  grad(theta) returns the loss gradient; theta (p,); M probes; eps
# Output: scalar estimate of the squared Frobenius norm of H

def hessian_frobenius_sq(grad, theta, num_probes, eps):
    total = 0.0
    for m in range(num_probes):  # M = 100 in the paper  [§5.3]
        # Gaussian probe v ~ N(0, I); E||Hv||^2 equals ||H||_F^2
        v = random_normal(size=theta.shape)
        # Central difference approximates H v  [eq. 14]
        hv = (grad(theta + eps * v) - grad(theta - eps * v)) / (2 * eps)
        total = total + dot(hv, hv)
    return total / num_probes  # eps = 1e-5 in the paper  [§5.3]

# Log-eigenvalue volume proxy  [§5.2] [eq. 13]
# Input:  symmetric Hessian (p, p); integer k (not stated in the paper)
# Output: V(k); larger means sharper  [§5.2]

def volume_proxy(hessian, k):
    eigs = eigvalsh(hessian)                      # ascending, (p,)
    # Keep the positive eigenvalues, then the k largest  [§5.2]
    # The paper's wording also admits the reverse order
    positive = [lam for lam in eigs if lam > 0]
    top = sorted(positive, reverse=True)[:k]
    return sum(log(lam) for lam in top)           # eq. 13

Contradictions

• Which Hessian. The bound in eq. 11 uses the Hessian with respect to the hidden biases c. The experiments use the Hessian and its Frobenius norm with respect to all parameters §5.2 eq. 14. The paper does not justify the substitution 1706.10239 §4 §5.2.
• Node scaling. The Frobenius norm changes when a node's weights are rescaled, so it is not invariant. The paper reports that Dinh et al. (2017) raised this objection. The authors answer that near-zero initialisation lets the Hessian term dominate; they do not test that answer 1706.10239 §4.
• Loss. The theory uses least-squares loss, but the loss in the deep experiments is not named in the main text §4 §5.2.
• Strength of the correlation. The authors' claim that good minima have large basins is qualitative. They describe the link between the proxies and test accuracy as loose and give no coefficient §5.3.

Papers

• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes: argues that the loss landscape decides generalisation, with a basin-volume argument, a two-layer Hessian-norm bound, and Hessian-based sharpness proxies on MNIST, SVHN and CIFAR-10.