Every day, practitioners train massive neural networks with billions of parameters using simple, first-order optimization methods like Stochastic Gradient Descent (SGD). Empirically, these networks converge smoothly to highly effective solutions. Yet, if you ask a computer theorist about the worst-case complexity of this task, they will tell you it is a mathematical minefield.
This tension between empirical success and theoretical intractability forms the core of neural network learning theory. To understand why training can be so mathematically difficult, researchers isolate the problem by studying the loading problem: given a fixed network architecture and a static training dataset, how hard is it to find a configuration of weights that perfectly maps those inputs to their correct outputs?
The Loading Problem and the Myth of Scale
It is tempting to assume that the difficulty of training neural networks stems entirely from their scale—that billions of parameters create an overwhelmingly vast, labyrinthine search space. However, foundational theory shows that computational intractability is an inherent property of the weight-assignment task itself, independent of network size.
In a foundational early result, Blum et al. proved that training a minimal network with just two hidden nodes and one output node is NP-complete. As detailed by Honavar in a review of early complexity frameworks (Book Review:Neural Network Design and the Complexity of Learning, by J. Stephen Judd. Cambridge, MA: MIT Press, 1990), this intractability persists even in highly constrained, shallow architectures with low node connectivity. The difficulty is not a consequence of network scale, but a fundamental mathematical barrier of the optimization objective.
When moving from static feedforward networks to recurrent architectures, the complexity escalates from intractable to impossible. Wiklicky demonstrated in On the Non-Existence of a Universal Learning Algorithm for Recurrent Neural Networks that the dynamic feedback loops inherent in recurrent models render the loading problem completely undecidable, meaning no universal training algorithm can ever exist for them.
Why Smoothness and Nice Weights Do Not Help
Another common intuition is that the hardness of early networks was an artifact of discrete step activation functions, and that modern smooth, differentiable activations (like sigmoids) eliminate this complexity by providing clean gradient paths. This intuition turns out to be wrong.
Hammer proved in Training a sigmoidal network is difficult that transitioning to smooth sigmoidal activations does not resolve the fundamental NP-hardness of the loading problem. The geometric complexity of the decision boundaries themselves, rather than the lack of differentiability, drives the difficulty. Similarly, Song et al. showed that even with smooth activations and benign input distributions, simple one-hidden-layer networks can still require an exponential number of queries for gradient-based optimization to succeed.
What if the target weights themselves are well-behaved? One might hope that if a problem's optimal weights are drawn from a natural distribution, like a Gaussian or Uniform distribution, the optimization landscape would simplify. However, Daniely et al. demonstrated that learning depth-2 architectures remains computationally hard even under these "natural" weight assumptions. The hardness is a robust property of the function space, not a quirk of adversarial weight configurations.
The Intuition: Combinatorial Explosion of Activation Boundaries
To build intuition for why training simple networks is so difficult, we must look at how neural networks partition data geometrically. Consider a Rectified Linear Unit (ReLU). A single neuron splits the input space into two regions: one where it is active (behaving linearly) and one where it is inactive (outputting zero). The hyperplane where it transitions is its activation boundary.
Active Region (Linear)
---------------------------------- <- Activation Boundary
Inactive Region (Zero)
Training a single ReLU neuron on perfectly separable data can be achieved efficiently in polynomial time using linear programming. However, Goel et al. showed that the problem becomes exponentially hard the moment the network contains two or more neurons.
Why does adding a single neuron trigger exponential hardness? Because each additional neuron introduces another activation boundary, creating a combinatorially explosive number of ways to partition the data into distinct regions. Finding the globally optimal weight configuration requires searching through these discrete, fragmented regions of the optimization landscape.
This combinatorial explosion is incredibly resilient to simplification:
- Low Dimensions Do Not Help: Froese et al. proved that training a two-layer ReLU network remains NP-hard even if the input data is restricted to just two dimensions. The complexity of arranging the activation boundaries in a 2D plane is already enough to trigger intractability.
- High Dimensions Hurt Single Neurons: In the agnostic setting (where data contains noise), Froese et al. showed that even a single-neuron ReLU network is W[1]-hard when parameterized by data dimensionality. The single non-linear breakpoint introduces enough combinatorial complexity to resist exact optimization as dimensions scale.
When we move to standard fully connected architectures, the layers multiply together, creating complex non-linear dependencies. Bertschinger et al. demonstrated that finding globally optimal weights for a standard two-layer fully connected ReLU network is formally classified as $\exists\mathbb{R}$-complete. This means the problem is likely harder than NP-complete, requiring the exact solution of systems of high-degree polynomial equations.
Bypassing the Complexity Barriers
If the worst-case complexity is so bleak, why does deep learning work in practice? The answer lies in the fact that practical training avoids the strict conditions of the worst-case loading problem by altering the data distribution, the architecture, or the learning protocol.
1. Constraining the Data Distribution
While training is hard for arbitrary or adversarial data, specific structures make the landscape manageable. For instance, Brutzkus et al. proved that gradient descent can find globally optimal weights for a convolutional neural network in polynomial time if the inputs follow a Gaussian distribution. Similarly, Bakshi et al. showed that two-layer ReLU networks can be recovered exactly in polynomial time under Gaussian inputs, provided the network's output dimension is at least equal to the number of hidden units.
2. Overparameterization and Relaxations
Instead of finding the exact weights for a tight, fixed architecture, we can expand the network or relax the constraints. Bartan et al. demonstrated that while training a single neuron with quantized (discrete) weights is NP-hard (sharing the same complexity as the Max-Cut problem), overparameterization allows the problem to be relaxed and solved to global optimality in polynomial time via semidefinite programming.
3. Active Learning and Queries
The standard hardness results assume passive learning from a fixed, unchangeable dataset. Baum et al. demonstrated that if a learner is allowed to actively "query" an oracle for the output of arbitrary points in space, they can geometrically pin down the hidden units one by one. This active interaction completely bypasses the NP-hard complexity of passive backpropagation.
Key Foundational Work
Training a 3-Node Neural Network is NP-Complete (1988) — contributed 6 concept elements to this direction.
Constructing Hidden Units Using Examples and Queries (1990) — contributed 1 concept elements to this direction.