Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes

In plain words

Deep neural networks often have far more adjustable numbers than training examples, yet the models they train usually work well on new data. The question is why. Two training runs can fit the same training data perfectly and still differ sharply on new data: one may be right most of the time, the other no better than guessing. The paper asks what separates the good solutions from the bad ones, and why ordinary training almost always ends up at a good one.

The answer is about the shape of the loss landscape. Picture the training loss as a terrain of valleys. A wide, flat valley collects many possible starting points, and downhill steps from any of them end in a good solution. A narrow, sharp valley collects few. The paper argues that good solutions sit in wide valleys and bad ones in narrow valleys, so a random start is very likely to begin in a good valley. Noise in stochastic gradient descent is not what makes the difference, according to the authors' experiments.

To test this, the authors deliberately build bad solutions by adding training examples with wrong labels, then measure how sharply curved each solution is. A theoretical analysis of two-layer networks supports the same picture.

TL;DR

• Over-parameterised networks that fit their training data often generalise well, and classical generalisation bounds cannot explain this §1 §2.2.
• The paper's claim: the loss landscape decides. Good minima have larger basins of attraction, so random initialisation converges to good minima almost surely §3.2 eq. 4 eq. 5.
• For 2-layer ReLU networks, a complexity measure is bounded by the Frobenius norm of the Hessian with respect to the hidden-unit biases c §4 eq. 11.
• For deeper networks the evidence is numerical: attacked training sets, Hessian spectra and a Hessian-based volume proxy §5.
• Author-reported and small-scale. The deep-network part has no theory, and no official code was found.

Problem

Classical bounds (VC dimension, Rademacher complexity) cover the whole hypothesis class and therefore hold even for the worst solution. For deep networks they give only trivial bounds, so they cannot say which of many zero-training-error solutions generalises §2.2. The paper states two questions: what distinguishes good solutions from poor ones with the same small training error, and why optimisers started at random almost always reach good ones §1. The motivating example is MNIST at 100% training accuracy, where some minima exceed 95% test accuracy and others are close to a random guess §1.

The theory assumes an over-parameterised network and least-squares loss for the two-layer case §4. The experiments use ReLU activations §2.1, footnote.

Method

The argument has four parts.

1. Generalisation depends on the chosen solution. Via the central limit theorem §2, the test risk of one particular learned function is bounded by its training risk plus a term that depends on the variance of the loss, scaled by the square root of the sample size eq. 2. The authors read this as saying that, at equal small training error, simpler solutions generalise better §2 §2.1.

2. Random initialisation lands in good basins. Let B_good and B_bad be the basins of attraction of good and bad minima under gradient flow. Empirically, random starts always converge to good solutions §3.2 tab. 2, which the authors summarise as probabilities close to 1 and 0 eq. 4. For a uniform start distribution this becomes a volume ratio close to 0 eq. 5. The authors call the ratio a conjecture §3.2.

3. Two-layer networks. For f(x; θ) = Σ_k a_k σ(b_k^T x + c_k) eq. 6, with least-squares loss, the Hessian of the empirical risk splits into a Fisher-information term and a residual term eq. 7. The expected squared input-gradient norm, which measures how much the function varies over the input, equals a Fisher-matrix quadratic form in the hidden-unit biases c eq. 9. Theorem 1 bounds it by the squared norm of the weights B plus the Frobenius norm of that Fisher matrix eq. 10. Corollary 1 replaces the Fisher matrix by the Hessian of the empirical risk and adds a term in C_σ = sup |σ''| and D = max_k |a_k| ‖b_k‖², plus a Monte Carlo error term that the paper leaves unquantified eq. 11 app. C. For ReLU, C_σ = 0 §4. The paper imposes a norm constraint (node scaling) only in the analysis; it is not enforced in practice, and near-zero initialisation is said to keep solutions in that regime §4.

4. Experiments. Bad minima are constructed by minimising the training loss plus γ times the loss on an attack set with deliberately wrong labels [eq. 12] §5.1. The volume of a basin is estimated by the log of the top-k positive Hessian eigenvalues eq. 13 §5.2. For large networks the squared Frobenius norm of the Hessian is estimated with random probe vectors and finite differences of gradients eq. 14 §5.3.

The pseudocode below restates the three computational steps. It is a reading of the paper, not the authors' code.

# Build a solution with a poisoned attack term  [§5.1] [eq. 12]
# Input:  train set, attack set (wrong labels), weight gamma
# Output: parameters with low train loss, poor test accuracy

def train_with_attack_set(train, attack, gamma, num_steps):
    # Start from a N(0, 2/fan_in) initialisation  [fig. 3]
    theta = initialise_parameters()
    for step in range(num_steps):  # number of steps not stated
        # Train loss plus gamma times the attack-set loss  [eq. 12]
        loss = train_loss(theta, train) + gamma * attack_loss(theta, attack)
        theta = optimiser_update(theta, loss)  # optimiser not named
    return theta

# Basin-volume proxy from the Hessian  [§5.2] [eq. 13]
# Input:  symmetric Hessian (p, p); integer k
# Output: V(k); larger means sharper, i.e. a smaller basin  [§5.2]

def volume_proxy(hessian, k):
    eigenvalues = eigvalsh(hessian)          # (p,), ascending
    largest_first = eigenvalues[::-1]        # (p,), descending
    # Keep positive eigenvalues, then the k largest  [§5.2] (order ambiguous)
    positive = [lam for lam in largest_first if lam > 0]
    top = positive[:k]                       # at most k values
    return sum(log(lam) for lam in top)      # eq. 13

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

def hessian_frobenius_sq(grad, theta, num_probes, eps):
    total = 0.0
    for i in range(num_probes):  # M = 100 in the paper  [§5.3]
        # Gaussian probe vector, v ~ N(0, I)  [§5.3]
        v = random_normal(size=theta.shape)
        # Central difference gives H v  [eq. 14]
        hv = (grad(theta + eps * v) - grad(theta - eps * v)) / (2 * eps)
        total = total + dot(hv, hv)
    # Divide by M; the paper uses eps = 1e-5  [§5.3]
    return total / num_probes

Hyperparameters

Results

Author-reported. All numbers are mean ± standard deviation over the runs stated. The paper's central claim is qualitative: good solutions lie in larger basins.

Test accuracy with full-batch versus mini-batch training tab. 1:

The authors read this as SGD helping only a little, which does not explain the large gap between good and bad minima §3.1.

Random initialisations, training with fixed epochs tab. 2:

Every initialisation reached a good solution, which the authors read as support for the random-start argument §3.2.

Figures, described in words:

• fig. 1: on five noisy cubic points, fully connected ReLU nets of several depths converge to smooth, low-complexity fits, while an overfitting fit exists but is constructed by hand. Kernel ridge regression needs a regulariser to avoid overfitting. Values are qualitative.
• fig. 2: for an mLeNet at 92% test accuracy with 100% training accuracy, most Hessian eigenvalues sit near zero and a few are negative. A bad solution has much larger top eigenvalues than a good one §5.2.
• fig. 3: test accuracy against the volume proxy V(k) and the Frobenius estimate for mLeNet on MNIST and SVHN, and for ResNet-32 on CIFAR-10. Good minima have large basins and bad minima small ones, but the authors say the correlation is not tight and that V(k) cannot separate minima of equal generalisation §5.3. No correlation coefficient is reported.

Paper vs code

No official code.

The paper contains no code link and no project page. Searches: the arXiv source's bibliography and text contain no URL; GitHub repository searches for the method's title and key terms returned only third-party repositories whose owners are not the authors; a GitHub search on the title returned no results. Attempts to query the GitHub search API partly failed with HTTP 403, so the search is not exhaustive.

Pitfalls

• "Full batch (10^5)" in tab. 1 is unexplained. The training set has 10,000 images §3.1, so 10^5 cannot be the batch size. It may be a step count or a label error. Not stated.
• Theory and experiments measure different Hessians. Corollary 1 uses the Hessian with respect to the output-side biases c eq. 11. The experiments compute Hessians and Frobenius norms with respect to all parameters θ §5.2 eq. 14. The paper does not justify replacing one by the other.
• Node scaling. The Frobenius norm of the Hessian changes under node scaling (a_k, b_k, c_k) → (a_k/t, t·b_k, t·c_k), so it is not an invariant complexity measure. The authors answer [Dinh et al. 2017] by arguing that near-zero initialisation makes the Hessian term dominate §4. This argument is not tested.
• Corollary 1 has an unquantified error term O(√(Var/N)) eq. 11. The bound is informative only if N is large relative to that variance; no sample size is given.
• Eq. 3 is informal. The paper says it presents the classical bound "in a non-rigorous way" §2.2.
• Eqs. 4 and 5 are empirical observations turned into probabilities. The volume ratio is conjectured, not measured. The uniform-start assumption is stated but never checked §3.2.
• "Top-k positive eigenvalues" is ambiguous. It can mean filtering positives first and then taking the top k, or the reverse. The card's pseudocode takes the first reading. k is not stated. Negative eigenvalues, which the paper observes §5.2, are dropped by the log.
• The volume proxy is rough. The authors call it "only a rough estimate" and say it cannot distinguish minima with equal generalisation §5.3. Treat fig. 3 as qualitative.
• Frobenius estimate. Finite differences with ε = 10^-5 and M = 100 are an approximation that is exact only in the limit ε → 0, M → ∞ §5.3. Floating-point precision is not stated. My inference, not from the paper: with small ε, rounding error in the gradient difference can dominate the estimate. Check against an exact Hessian on a small model.
• Attack construction is under-specified. How wrong labels are assigned, the value of γ, the attack-set size for each run, the optimisers, and the stopping rule are not stated §5.1 §5.3.
• Conjectures in the Hessian analysis. That the good solutions form a connected manifold and that the zero eigenvalues span its tangent space are conjectures §5.2.
• Inconsistent architectures. Table 2 uses ResNet-18 on CIFAR-10 tab. 2, while the Hessian experiment and fig. 3 use ResNet-32 §5.3.
• Theory covers two-layer networks only. The authors say deeper networks are left to future work §4 and that theoretical justification for them is still a challenge §6.
• Loss mismatch. The two-layer analysis uses least-squares loss §4. The loss used in the deep-network experiments is not named in the main text §5.2 fig. 2.
• The 1-D overfitting example is hand-built. The overfitting fit in fig. 1 is constructed on purpose and is not reached from random initialisation §2.1.

Lineage

• Builds on: flat-minimum and sharp-minimum ideas of Hochreiter and Schmidhuber (1995, 1997), large-batch versus small-batch sharpness of Keskar et al. (2016), the path-norm invariance of Neyshabur et al. (2015), and the variance-controlled initialisation of He et al. (2015) §1 §3.2 §4.
• Compared against: the view that SGD's implicit regularisation explains generalisation (Hardt et al., 2015; Zhang et al., 2016), and explicit regularisers such as weight decay and dropout §1 §3.1.
• Criticised by: Dinh et al. (2017), who argue that sharpness measures do not explain generalisation because they change under node scaling §4.
• Superseded by: not stated.