Spurious Valleys and Clustering Behavior of Neural Networks

Samuele PollaciICML 2023 · OpenReview

Neural network training is fundamentally an optimization problem within a high-dimensional, non-convex "loss landscape." A major challenge in this domain is the presence of spurious valleys—topological traps where gradient descent can get stuck in sub-optimal solutions rather than finding the global minimum. While practitioners often bypass this issue by heavily over-parameterizing networks (making them very wide), the theoretical understanding of exactly how wide a network needs to be to guarantee a clean landscape has remained incomplete.

3D visualization of a non-convex loss landscape with valleys

This paper provides explicit theoretical guarantees for neural network training by identifying the precise hidden layer widths required to eliminate spurious valleys. Furthermore, it introduces a novel "geometric fingerprinting" method using algebraic geometry to determine whether a specific network architecture is capable of representing a given target function.

Methods: Algebraic Geometry in Loss Landscapes

The authors employ tools from algebraic geometry to analyze the loss landscape's structure, focusing on synthetic polynomial datasets designed to test networks with monomial activation functions (e.g., $x^r$).

  • Intrinsic Dimension Analysis: To establish width guarantees, the paper defines the "intrinsic dimension" of functional spaces created by different network layers. By comparing these dimensions to the actual number of neurons in a hidden layer, the authors derive sufficient conditions for the absence of spurious valleys.
  • Cut Loss Landscapes: To analyze representability, the study examines 2D cross-sections (slices) of the high-dimensional loss landscape.
  • Singular Point Clustering: By studying the "singular points" of these 2D slices—where the landscape's geometry changes abruptly—the authors discover that error values at these points organize into distinct clusters. The movement of these clusters as the training data is shifted provides a mathematical test for function representability.

Key Insights and Results

Width as a Guarantee

The paper proves that if a hidden layer's size ($h_k$) is greater than or equal to the "intrinsic dimension" of the preceding functional space, the loss landscape is guaranteed to have no spurious valleys. This provides a formal mathematical justification for why over-parameterization simplifies optimization. These explicit bounds generalize previous work to a much wider class of neural networks, both with and without bias terms.

The Representability "Fingerprint" and Clustering Theorem

The most striking discovery is the Clustering Theorem. For a 1-hidden-layer polynomial network, the error values at singular points of the landscape consistently form three distinct clusters.

Log-scale plot demonstrating the three distinct clusters of error values

This leads to the Middle Cluster Test: If a target function is representable by the network, the "middle cluster" of error values will shrink toward zero as the training data is translated to infinity (shifted by a factor $\delta$). Conversely, if the function is not representable, this cluster will diverge or remain bounded away from zero. This insight elegantly transforms a complex representability question into a limit-behavior problem, where the growth rate of these clusters is strictly tied to the target function's coefficients and the network's activation power.

Limitations and Future Work

While theoretically profound, the current clustering results are specifically proven for networks with monomial activation functions. Common activations like ReLU or Sigmoid possess "infinite intrinsic dimensions," meaning the specific bounds derived here do not apply to them directly.

Furthermore, while the spurious valley theorems cover deep networks, the detailed clustering analysis is currently focused on 1-hidden-layer architectures. Extending this geometric fingerprinting to deeper networks and moving from empirical risk (finite datasets) to population risk (the true underlying distribution) remain primary directions for future research.

Summary updated

Abstract

Neural networks constitute a class of functions that are typically non-surjective, with high-dimensional fibers and complicated image. We prove two main results concerning the geometry of the loss landscape of a neural network. First, we provide an explicit effective bound on the sizes of the hidden layers so that the loss landscape has no spurious valleys, which guarantees the success of gradient descent methods. Second, we present a novel method for analyzing whether a given neural network architecture with monomial activation function can represent a target function of interest. The core of our analysis method is the study of a specific set of error values, and its behavior depending on different training datasets.
BibTeX
@inproceedings{pollaci2023spurious,
  author = {Samuele Pollaci},
  title = {{Spurious Valleys and Clustering Behavior of Neural Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=TuHgrnPHZq},
}
Figure