Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes

Luca Venturi, Afonso S. Bandeira, Joan BrunaJMLR 2019

TL;DR

This paper investigates "spurious valleys" in the loss landscapes of one-hidden-layer neural networks, which can trap optimization algorithms like gradient descent. They introduce the concept of "intrinsic dimension" to provide conditions for the absence of these valleys, showing that sufficient over-parameterization guarantees a smooth optimization path for polynomial activations. Conversely, they demonstrate that for certain non-polynomial activations and under-parameterized networks, arbitrarily bad spurious valleys can exist.

What Problem Does This Paper Address?

Neural networks, despite their non-convex loss functions, are often successfully optimized by gradient-based methods. A key question is why this works so well in practice. One potential explanation for optimization failures is the presence of "spurious valleys" – connected regions in the loss landscape that are not global minima but can trap optimizers. This paper aims to understand when these spurious valleys exist in a fundamental building block of neural networks: the one-hidden-layer network. They seek to characterize the conditions (related to network architecture, activation functions, and data distributions) under which these problematic valleys appear or disappear.

Methods

The core of the paper's methodology revolves around defining and utilizing two measures of the "intrinsic dimension" of the functional space spanned by a one-hidden-layer neural network: the upper intrinsic dimension and the lower intrinsic dimension.

  • Intrinsic Dimension: This concept quantifies the complexity of the function space a network can represent. The authors define an "upper intrinsic dimension" related to the dimension of the linear space spanned by the network's "filter functions" (outputs of individual hidden neurons) and a "lower intrinsic dimension" related to the minimum number of hidden units needed to represent any function in that space.
  • Spurious Valley Characterization: The absence of spurious valleys is linked to a property called "P.1," which guarantees the existence of a continuous path from any initial parameter to a global minimum, along which the loss is non-increasing. The authors use their intrinsic dimension measures to prove conditions under which P.1 holds.
  • Constructive Proofs: For positive results (absence of spurious valleys), they construct explicit descent paths. For negative results (presence of spurious valleys), they construct adversarial data distributions that create these problematic landscapes.
  • Random Features and Kernel Methods: The paper leverages connections to random features expansions and kernel methods, particularly in analyzing the behavior of the loss function and constructing paths.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis using generic data distributions and constructions of adversarial data distributions, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Intrinsic Dimension as a Predictor: The paper establishes a strong link between the "intrinsic dimension" of the network's function space and the existence of spurious valleys. This provides a principled way to analyze optimization landscapes.
  • Over-parameterization is Key (for Polynomials): For polynomial activation functions, sufficient over-parameterization (i.e., the width of the hidden layer being large enough relative to the intrinsic dimension) guarantees the absence of spurious valleys. This is a powerful positive result for practical deep learning.
  • Non-Polynomial Activations are Tricky: For non-polynomial activations (like ReLU), even with over-parameterization, spurious valleys can exist if the network is under-parameterized relative to the lower intrinsic dimension. The authors show how to construct data distributions that create these valleys.
  • Spurious Valleys are "Low Energy": Even when spurious valleys exist, they tend to be confined to low-risk (low loss) regions. This suggests why gradient descent often finds good solutions in practice, as it's less likely to get stuck in these "shallow" traps.
  • Linear and Quadratic Activations are Well-Behaved: The paper provides improved bounds for linear and quadratic activations, showing they can avoid spurious valleys with less over-parameterization than the general case.

Key Results

  • Theorem 8: For any continuous activation function with finite upper intrinsic dimension, spurious valleys are absent in the over-parameterized regime (hidden layer width $p > \text{dim}^*(\sigma, X)$).
  • Corollary 9 (ERM): For empirical risk minimization, spurious valleys are absent when $p > N$ (number of data points).
  • Corollary 10 (Polynomial Activations): For polynomial activations, spurious valleys are absent when $p \ge O(n^d)$, where $d$ is the degree of the polynomial.
  • Theorem 11 (Linear Networks): For linear networks of any depth, square loss functions admit no spurious valleys, regardless of over-parameterization.
  • Theorem 12 (Quadratic Networks): For one-hidden-layer networks with quadratic activations and scalar output, spurious valleys are absent when $p > 2n$.
  • Theorem 13: For non-polynomial activations and under-parameterized networks ($p < \text{dim}_*(\sigma, n-1)$), there exist data distributions that create arbitrarily bad spurious valleys.
  • Corollary 14 (Even Degree Polynomials): For $\sigma(z) = z^{2k}$, spurious valleys can exist if $p$ is below a bound related to the symmetric tensor rank.
  • Corollary 15 (Generic Architectures): For non-polynomial, continuous, non-negative activations (like ReLU, softplus, sigmoid), spurious valleys can exist for any hidden width $p > 1$ with appropriately chosen data.
  • Theorem 16: For typical data distributions, spurious valleys tend to be confined to low-energy thresholds, and large energy barriers are avoided with high probability as network width increases.

Limitations and Future Work

  • Bias Terms: The analysis often simplifies by omitting bias terms, though the authors note this can be addressed by incorporating them into weights and input variables.
  • Focus on One-Hidden-Layer: The primary focus is on one-hidden-layer networks. Extending these results to deeper architectures, especially convolutional neural networks (CNNs) and architectures with residual connections or normalization, is a significant open problem.
  • First Layer Dynamics: The positive results often reduce the problem to optimizing the output layer. Understanding the dynamics of the first layer remains a challenge.
  • Convergence Guarantees: While the absence of spurious valleys is shown, this doesn't automatically guarantee convergence of gradient descent to the global minimum. The paper notes that the existence of local descents from non-optimal points needs further investigation.
  • Generalization: The paper focuses on the optimization landscape itself. Connecting these findings to generalization error and understanding how the landscape influences generalization is a crucial next step.
  • Practical Regimes: The current results often apply to highly over-parameterized regimes, which may not fully capture the behavior of networks trained in more practical, moderately over-parameterized settings. Bridging this gap is an active area of research.

Summary updated

BibTeX
@article{venturi2019spurious,
  author = {Luca Venturi and Afonso S. Bandeira and Joan Bruna},
  title = {{Spurious Valleys in One-hidden-layer Neural Network Optimization Landscapes}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
}
Figure