PaperlayerView exact revision on arXiv

Source-linked AI summary

On the loss landscape of a class of deep neural networks with no bad local valleys

Quynh Nguyen, Mahesh Chandra Mukkamala, Matthias Hein

arXiv:1809.10749v2cs.LGcs.AIcs.CVstat.ML

TL;DR

Training over-parameterized deep networks is difficult to characterize because their non-convex loss landscapes may contain many local minima. The paper identifies architectures with output skip connections and proves that every parameter point connects by a non-increasing path to arbitrarily low cross-entropy, while experiments show good SGD generalization.

  • Problem

    The paper asks whether practically relevant over-parameterized deep networks can have loss landscapes that avoid bad local minima without distributional assumptions on the data.

    Source: §1 · p. 1

  • Method

    It studies deep networks with output skip connections, establishes a full-rank feature condition using analytic activations, and analyzes their standard multi-class cross-entropy loss.

    Source: §1 · p. 1, §3 · p. 4

  • Results

    The identified networks have no bad local valleys, and from every parameter point a continuous non-increasing path reaches arbitrarily close to zero loss.

    Source: §1 · p. 2, §3 · p. 5

  • Takeaways & Limitations

    These networks provide a test bed for studying SGD's implicit regularization because they achieve zero training error yet generalize well, unlike a random-feature alternative.

    Source: §1 · p. 2, §6 · p. 9

    The proof requires an architectural activation-function condition and may require additional lower-to-upper-layer connections, although it does not require wide individual layers.

    Source: §3 · pp. 4–5

Abstract

from arXiv · show

We identify a class of over-parameterized deep neural networks with standard activation functions and cross-entropy loss which provably have no bad local valley, in the sense that from any point in parameter space there exists a continuous path on which the cross-entropy loss is non-increasing and gets arbitrarily close to zero. This implies that these networks have no sub-optimal strict local minima.

1 INTRODUCTION

The paper targets the apparent gap between non-convex neural-network training and the frequent success of local search by identifying architectures with guaranteed well-behaved loss landscapes. These networks admit non-increasing paths toward arbitrarily low cross-entropy loss while retaining practical relevance.

  • The setting uses over-parameterized deep convolutional networks, standard multi-class cross-entropy, and no distributional assumptions on training data.Source: §1 · pp. 1–2
  • The paper identifies deep networks with skip connections to the output layer whose loss landscape has no bad local valleys.Source: §1 · p. 1, Figure 1 · p. 1
  • From every parameter point, a continuous path exists along which cross-entropy is non-increasing and approaches zero, ruling out sub-optimal strict local minima.Source: §1 · p. 2
  • Architectures can be constructed by adding output skip connections from a random subset of N hidden neurons to an existing CNN.Source: §1 · p. 2
  • Despite achieving zero training error, these networks generalize well with SGD, whereas a zero-error random-feature training procedure generalizes significantly worse and overfits.Source: §1 · p. 2

2 DESCRIPTION OF NETWORK ARCHITECTURE

The analyzed architectures are directed acyclic deep networks with flexible connectivity, including shared weights and convolutional structure, but require at least N hidden neurons with independent output connections. The paper studies their cross-entropy behavior, including the distinction between arbitrarily small loss and attained global minima.

  • Hidden units may connect to arbitrary subsets of lower-layer units, while groups on a layer may use shared or non-shared weights.Source: §2 · p. 2
  • The framework covers deep fully connected and convolutional networks with directed connections from lower to upper layers and output skip connections distinct from DenseNet or ResNet identity skips.Source: §2 · p. 2
  • The architecture requires at least N hidden neurons, potentially across layers, to connect directly to outputs with independent weights.Source: §2 · pp. 2–3
  • The cross-entropy loss is nonnegative but need not attain its global minimum, because scaling a zero-training-error classifier can drive loss arbitrarily close to zero.Source: §2 · p. 3
  • Sufficiently small cross-entropy implies zero training error through the positivity-based margin condition described in the analysis.Source: §2 · pp. 3–4

3 MAIN RESULT

Under Assumption 3.1, a broad class of deep networks with at least N suitable output-connected neurons has a loss landscape without bad local valleys. The result follows from almost-everywhere full rank of the hidden-feature matrix and implies zero-training-error solutions, no suboptimal strict local minima, and no local maxima.

  • The result applies to arbitrarily deep fully connected or convolutional networks with real-analytic, strictly increasing activations and suitable output skip-connections.The assumptions include bounded or softplus-specific conditions, distinct training-sample input patches, and at least N suitable neurons connected to the output.Source: §3 · p. 4
  • For almost every hidden-layer parameter configuration U, the feature matrix Ψ(U) has full rank N.The proof constructs one full-rank configuration and uses analyticity to show that rank failure occurs on a measure-zero set.Source: §3 · pp. 4–5
  • The paper conjectures that the same rank result may hold for softplus without the extra architectural condition, but proving this is harder because skip-connected neurons interact across layers.Source: §3 · p. 5
  • Theorem 3.4 establishes uncountably many zero-training-error solutions, no bad local valleys, no suboptimal strict local minima, and no local maxima.Source: §3 · p. 5
  • Full rank makes the linear system Ψ(U)V = Y solvable for every target matrix, yielding uncountably many output-layer solutions with zero training error.Source: §3 · p. 5
  • Convexity in the output weights lets every connected component of a cross-entropy sublevel set contain a path toward arbitrarily small loss, ruling out bad local valleys.The argument connects any point to a full-rank configuration while remaining within the same sublevel component.Source: §3 · pp. 5–6
  • The theorem also gives a continuous non-increasing-loss route from any parameter point toward zero training error.The paper contrasts this landscape property with a direct random-feature last-layer solver, which reaches zero training error but can generalize poorly.Source: §3 · pp. 6–7

4 EXPERIMENTS

The experiments test whether output skip-connections improve generalization in practical CNNs and whether SGD selects better-generalizing zero-training-error solutions than randomized features.

Experimental setup

  • The experiments compare original and skip-connected CNNs on MNIST and CIFAR10 using sigmoid or softplus activations, standard cross-entropy, and SGD or randomized-feature training.The skip networks connect a randomly selected subset of N hidden neurons to the output layer.Source: §4 · p. 7, Table 1 · p. 8, Table 2 · p. 8
  • CIFAR10 experiments use VGG11, VGG13, VGG16, and DenseNet121, with skip variants formed by randomly selecting N hidden neurons for output connections.The reported CIFAR10 results exclude data augmentation, while additional augmented results appear in the appendix.Source: §4 · p. 7, Table 2 · p. 8
  • CNN13-skip is constructed by selecting N = 55,000 of 179,840 hidden neurons for output connections in the MNIST experiment.Table 1 compares the original CNN13 with this corresponding skip-model.Source: Table 1 · p. 8

Discussion of results

  • Adding output skip-connections improves test accuracy in almost all evaluated networks trained with SGD, except Densenet121.For sigmoid activations, skip-connections enable reasonable performance for all models except Densenet121, whereas the original models fail.Source: §4 · pp. 7–8
  • The Densenet121 exception may reflect its existing hidden-layer skip-connections, which already improve the loss surface before output skip-connections are added.The authors therefore suggest that additional output connections are unnecessary for this architecture.Source: §4 · p. 8
  • The randomized-feature procedure also reaches zero training error but shows worsening test accuracy as networks become more complex, indicating overfitting.Here the hidden representation is fixed and only the output weights are optimized.Source: §4 · pp. 8–9, Table 2 · p. 8
  • SGD shows no sign of overfitting despite increased parameter counts and zero training error being attainable for every skip-model.The contrast with randomized features supports using these networks to study SGD’s implicit regularization.Source: §4 · pp. 8–9

5 RELATED WORK

Prior loss-surface results largely focus on shallow, linear, or structurally simplified networks, while this work studies deeper multi-class architectures with stronger landscape guarantees.

5 RELATED WORK

  • Existing theoretical results commonly concern shallow networks, deep linear networks, or architectures and data distributions under simplifying assumptions.The cited literature spans loss surfaces and SGD analyses across several restricted settings.Source: §5 · p. 9
  • Related work studies fully connected and convolutional multi-class networks when one layer exceeds the number of training samples, but the present guarantees are stronger.The paper claims no suboptimal local valleys or strict local minima with less over-parameterization when the number of classes is small.Source: §5 · p. 9
  • A closer binary-classification result eliminates bad local minima using one output skip-connected neuron with exponential activation under mild loss conditions.The present setting instead addresses standard multi-class problems and broader deep architectures.Source: §5 · p. 9

6 CONCLUSION

The paper identifies deep networks with no bad local valleys and observes that they generalize well under SGD despite zero training error. The appendix supplies analytic and topological tools used in the proofs.

6 CONCLUSION

  • The identified over-parameterized networks have no bad local valleys, achieve zero training error easily, and generalize well in practice when trained with SGD.A randomized-feature procedure also fits the training data but generalizes significantly worse, motivating these models as a test bed for SGD’s implicit regularization.Source: §6 · p. 9

A MATHEMATICAL TOOLS

  • The mathematical-tools appendix invokes the fact that a nonzero real analytic function’s zero set has Lebesgue measure zero.This property is used in the proof of Lemma 3.2.Source: A MATHEMATICAL TOOLS · p. 11
  • The appendix also uses continuity to establish that the preimage of an open set is open.This standard topological proposition is used in the proof of Theorem 3.4.Source: A MATHEMATICAL TOOLS · p. 11

B PROOF OF LEMMA 3.2

The proof constructs parameters making the feature matrix full rank, then uses analyticity to show rank deficiency occurs only on a measure-zero set.

B PROOF OF LEMMA 3.2

  • The proof first constructs a network configuration whose N×N feature submatrix has full rank, using distinct first-layer outputs and structured weights.Higher-layer neurons select one predecessor, while skip-connection biases and positive scaling parameters impose an ordered activation pattern.Source: B PROOF OF LEMMA 3.2 · p. 12
  • Strictly increasing activations make the ordering of skip-connection outputs follow the ordering of first-layer values, allowing a fixed permutation and triangular-dominant determinant argument.Non-identity permutation terms become arbitrarily small as the positive scaling parameter increases, while the identity term remains dominant.Source: B PROOF OF LEMMA 3.2 · pp. 12–13
  • The determinant expansion establishes full rank for a suitable scaling choice, including the bounded-activation and softplus cases.The non-identity terms are controlled by the activation bounds, and the resulting error can be made arbitrarily small by increasing α.Source: B PROOF OF LEMMA 3.2 · pp. 13–14
  • The construction preserves permitted weight-sharing constraints by assigning equal scaling factors to neurons on the same layer and separating skip-connected paths when necessary.For softplus, the assumptions additionally exclude weight sharing between skip-connection neurons and neurons on their backward paths.Source: B PROOF OF LEMMA 3.2 · pp. 13–14
  • Because feature-matrix entries are real analytic and one determinant is not identically zero, the set of parameters yielding low rank has Lebesgue measure zero.Thus almost every hidden-parameter configuration produces a full-rank feature matrix.Source: B PROOF OF LEMMA 3.2 · p. 15

C EXTENSION OF THEOREM 3.4 TO GENERAL CONVEX LOSSES

The appendix extends the loss-landscape result from cross-entropy to convex, lower-bounded losses by analyzing connected sublevel sets and their attainable infimum.

C EXTENSION OF THEOREM 3.4 TO GENERAL CONVEX LOSSES

  • The framework applies to cross-entropy, square, and multi-class hinge losses because these losses are convex and bounded below by zero.The generalized formulation directly studies the loss applied to the network output matrix G.Source: C EXTENSION OF THEOREM 3.4 TO GENERAL… · p. 15
  • Every nonempty connected component of an α-sublevel set contains points with loss arbitrarily close to the global infimum p∗, so no bad local valley exists.A full-rank feature matrix permits a target output attaining loss at most any ε between p∗ and α, and convexity keeps the connecting segment inside the same sublevel component.Source: C EXTENSION OF THEOREM 3.4 TO GENERAL… · pp. 15–16
  • Under convexity and a finite lower bound, the generalized objective has uncountably many zero-training-error solutions whenever the feature matrix has full rank.For almost every hidden-parameter choice, solving Ψ(U)V=Y yields a solution for every target matrix Y.Source: C EXTENSION OF THEOREM 3.4 TO GENERAL… · pp. 15–16
  • The absence of bad local valleys rules out suboptimal strict local minima.A strict suboptimal minimum would induce a connected sublevel component confined near it whose loss cannot approach p∗, contradicting the preceding property.Source: C EXTENSION OF THEOREM 3.4 TO GENERAL… · p. 16
  • For cross-entropy and square loss, the landscape has no local maximum.The Hessian with respect to the output-layer weights is simultaneously constrained by convexity and the local-maximum assumption, leading to a contradiction with the network assumptions.Source: C EXTENSION OF THEOREM 3.4 TO GENERAL… · pp. 16–17

D THE ARCHITECTURE OF CNN13 FROM TABLE 1: SEE TABLE 3

The MNIST CNN13 appendix reports the architecture size, while a two-dimensional visualization compares loss surfaces before and after adding output skip-connections.

D THE ARCHITECTURE OF CNN13 FROM TABLE 1: SEE TABLE 3

  • CNN13 contains 179,840 hidden neurons in the MNIST architecture described by Table 3.The table specifies the architecture of the 13-layer CNN used for MNIST.Source: Table 3 · p. 17

E VISUALIZATION OF THE LOSS LANDSCAPE BEFORE AND AFTER ADDING SKIP-CONNECTIONS TO THE OUTPUT LAYER

F DISCUSSION OF TRAINING ERROR IN TABLE 2

The experiments examine how skip-connections affect training error and convergence in shallow and very deep networks. Skip-connections support zero training error and improve optimization, while sigmoid plain networks can collapse to a constant classifier.

  • Zero training error is achieved in all Table 2 cases except original VGG models with sigmoid activation, which collapse to a constant zero classifier.Their training and test accuracy converge to 10%, and the loss converges to −log(1/10).Source: F DISCUSSION OF TRAINING ERROR IN… · p. 17
  • DenseNets avoid the sigmoid collapse observed in plain VGGs, likely because dense-block skip-connections allow gradients to reach every layer.Source: F DISCUSSION OF TRAINING ERROR IN… · pp. 17–18
  • For sigmoid models, random-sampling skip training often converges more slowly than full SGD, requiring 5000 versus 1000 epochs to ensure zero training error.For softplus models, all approaches often converge within 300 epochs.Source: F DISCUSSION OF TRAINING ERROR IN… · p. 18
  • Skip-connections enable a 150-layer softplus network to reach zero training error within 200 epochs, while the original network fails to converge after 1000 epochs.The original network also shows stronger training fluctuations.Source: F DISCUSSION OF TRAINING ERROR IN… · p. 18, Figure 5 · p. 19

G ADDITIONAL EXPERIMENTS: MAX-POOLING OF VGGS ARE REPLACED BY 2X2 CONVOLUTIONAL LAYERS OF STRIDE 2

Replacing VGG max-pooling with stride-2 convolutions makes the theoretical conditions applicable, while preserving the observed benefit of output skip-connections. The replacement reduces skip-model performance by 4−7% relative to Table 2.

  • Replacing VGG max-pooling with 2x2 stride-2 convolutions makes the networks consist only of convolutional and fully connected layers, so the theoretical results apply.The original max-pooling setting is not directly covered because it removes the analytic property needed for the full-rank argument.Source: G ADDITIONAL EXPERIMENTS: MAX-POOLING… · p. 19
  • Skip-connections remain helpful after replacement: they improve softplus results and make training deep sigmoid networks possible.Source: G ADDITIONAL EXPERIMENTS: MAX-POOLING… · p. 19
  • 4−7% lower skip-model performance follows replacement of max-pooling layers with 2x2 stride-2 convolutions, with a sharper decrease for sigmoid activation.Source: G ADDITIONAL EXPERIMENTS: MAX-POOLING… · p. 19
  • Table 4 reports VGG test accuracy after max-pooling is replaced by 2x2 stride-2 convolutions, using the same comparison notation as Table 2.Source: Table 4 · p. 20
  • Full-network SGD still yields significantly better generalization than the random-feature approach among solutions with zero training error.Source: G ADDITIONAL EXPERIMENTS: MAX-POOLING… · p. 20

H DATA-AUGMENTATION RESULTS FOR TABLE 2

The data-augmentation experiments add random crops and horizontal flips to the Table 2 comparison. Table 5 reports the resulting CIFAR10 test accuracies for CNN architectures with and without skip-connections.

Loading 1809.10749v2…