Training a sigmoidal network is difficult

Barbara HammerESANN 1998 · OpenReview

Abstract

This paper addresses the "loading problem"—the task of determining if a specific neural network architecture can perfectly classify a given dataset. While previously known to be NP-complete for step-function activations, this work proves that the problem remains NP-hard for networks using smooth sigmoidal activation functions. By demonstrating this hardness for a minimal 3-node network with bounded weights and a required classification margin, the author establishes that the computational difficulty of training is an inherent property of sigmoidal architectures rather than a consequence of non-differentiability.

Introduction: The Loading Problem

In the late 1990s, despite the widespread use of neural networks, a significant gap persisted between theoretical understanding and practical training performance. Training was often prohibitively slow as input dimensions increased. The authors investigate this through the lens of the loading problem: given a fixed network architecture and a training set, does there exist a set of weights that allows the network to classify the data correctly?

While the loading problem was already proven NP-complete for "perceptron" (step-function) activations, there was hope that the smoothness and differentiability of sigmoidal activations (e.g., $1/(1+e^{-x})$) might simplify the search space. This paper provides a theoretical reality check, proving that smoothness does not bypass fundamental computational complexity.

Methods and Geometric Analysis

The proof relies on a classic reduction from the (2,3)-set splitting problem (SSP), a known NP-complete problem, to the loading problem. The author's approach is grounded in a rigorous geometric analysis of the decision boundaries produced by a 3-node network (two hidden sigmoidal units feeding into one output).

Geometric Taxonomy

The paper demonstrates that the decision boundary in the input space for such a network is a manifold. Depending on the signs of the weights, this manifold is either empty, convex, or S-shaped.

Geometric taxonomy of decision boundaries for a 3-node sigmoidal network, showing convex (a) and S-shaped (b) manifolds.

Pattern Construction and Reduction

To complete the reduction, the author constructs a specific set of "patterns" (data points) in a high-dimensional space. These points are strategically positioned such that a 3-node sigmoidal network can only classify them correctly if a valid "split" exists for the corresponding SSP instance.

Projection of high-dimensional patterns used in the reduction from the set splitting problem to the loading problem.

Crucially, the proof incorporates realistic constraints:

  • Classification Margin: The classification must maintain a minimum accuracy (a "margin" $\epsilon$).
  • Bounded Weights: Output weights must be bounded by a constant $B$. This ensures the result applies to realistic training scenarios where weights do not grow infinitely to mimic step functions.

Key Insights

  • Smoothness vs. Complexity: The differentiability of sigmoids does not prevent the combinatorial explosion of possible network configurations. The geometric complexity of the decision boundary alone is sufficient to encode NP-hard problems.
  • Minimal Architecture Hardness: It only takes two hidden units to create a decision boundary complex enough to make the loading problem NP-hard as the input dimension $n$ grows.
  • Generalization: The findings are not restricted to the standard sigmoid; they extend to any activation function $\sigma$ that can be closely approximated by a scaled or shifted sigmoid, such as $\tanh$.

Results

The primary result is formalized in Theorem 1: For a fixed accuracy $\epsilon \in (0, 0.5)$ and weight restriction $B \ge 2$, solving the loading problem for a 3-node sigmoidal architecture with unbounded input dimension is NP-hard. This result effectively settles the question of whether sigmoidal smoothness provides a computational "free lunch" for the loading problem.

Limitations and Future Work

While the problem is proven NP-hard, its membership in the class NP remains an open question. Verifying a solution in polynomial time is non-trivial because the required weights might be irrational or require infinite precision. Additionally, while the proof targets a single hidden layer, the author suggests the result likely generalizes to deeper networks. Future research might also explore whether these geometric constraints apply to other simple activations, such as ReLUs, which lack the specific "convex vs. S-shaped" boundary limitations of sigmoids.

Summary updated

BibTeX
@inproceedings{hammer1998training,
  author = {Barbara Hammer},
  title = {{Training a sigmoidal network is difficult}},
  booktitle = {ESANN},
  year = {1998},
  url = {https://openreview.net/forum?id=Bv0aZ3nIsFK},
}
Figure