TL;DR
This paper bridges the gap between the theoretical NP-hardness of training neural networks and their massive success in practice. The authors show that while training fixed-size networks is generally hard, "over-specification" (using larger networks than necessary) and switching to polynomial activation functions can make the optimization problem provably efficient and practically faster.
What Problem Does This Paper Address?
In computer science theory, training a neural network is a notoriously "hard" problem. Specifically, finding the best weights for even a simple two-layer network is NP-hard. Yet, every day, researchers train massive deep learning models using Stochastic Gradient Descent (SGD) with great success.
This paper investigates this paradox. The authors ask: Under what conditions does training become computationally tractable? They explore how modern "tricks"—like using different activation functions, regularizing weights, and building networks much larger than the underlying data requires—change the complexity landscape from "impossible" to "efficient."
Methods
The authors approach the problem through three main lenses:
- Over-specification Analysis: They provide a simple but powerful observation: if a network has more neurons in its hidden layer than there are training examples ($n \ge m$), the optimization problem becomes much easier. In this regime, global optima become "ubiquitous" because the final layer's optimization becomes a convex problem.
- Polynomial Networks: They propose using the quadratic activation function $\sigma(a) = a^2$. These "polynomial networks" are theoretically interesting because they can approximate standard sigmoidal networks but allow for better mathematical analysis.
- The GECO Algorithm: For practical training, they adapt the Greedy Efficient Convex Optimization (GECO) algorithm. Instead of training all weights at once via SGD, GECO builds the network greedily. It adds one neuron at a time by solving an eigenvalue problem (for depth-2) or a tensor approximation problem (for depth-3), ensuring each step actually reduces the loss.
Datasets
The paper validates its theoretical findings using two primary setups:
- Pedestrian Detection: A dataset of 200,000 image patches (88x40 pixels) containing pedestrians or "hard" negatives (like cars and background clutter). They used Histograms of Oriented Gradients (HoG) as features.
- Synthetic Data: Randomly generated examples in $\mathbb{R}^{150}$ passed through a teacher network to test the specific effects of over-specification on convergence speed.
Key Insights and Ideas
- Improper Learning is a Superpower: Hardness results often assume "proper learning" (you must find the best weights for a fixed architecture). The authors argue that if we allow "improper learning" (finding a good predictor in a different or larger architecture), many hardness barriers vanish.
- The "Ubiquity" of Global Optima: In extremely over-specified networks, almost any random initialization of the internal layers allows the output layer to find a global minimum. This explains why huge models often converge easily despite the non-convexity of the overall objective.
- Activation Functions Matter for Complexity: While ReLU and Sigmoid lead to hardness results in certain settings, quadratic activations allow for linearization tricks that turn neural network training into a polynomial-time solvable problem.
- Regularization as a Complexity Bridge: The paper shows that depth-2 sigmoidal networks, which are hard to learn in general, become efficiently learnable if you apply strong enough $\ell_1$ regularization.
Key Results
The theoretical claims are backed by strong empirical evidence, particularly regarding the GECO algorithm and the benefits of over-specification.
- GECO vs. SGD: In the pedestrian detection task, the GECO algorithm trained a depth-2 polynomial network faster than SGD and achieved a slightly lower test error (as seen in the top chart above).
- Convergence Speedup: In synthetic tests, increasing the "over-specification factor" (making the network 2x, 4x, or 8x larger than the target function) led to significantly faster convergence for SGD (bottom chart).
- Expressivity: The authors proved that polynomial networks are just as expressive as threshold networks; they can even simulate Turing Machines given enough depth and size.
Limitations and Future Work
- Overfitting Risks: While over-specification makes optimization easy, the authors acknowledge it can lead to massive overfitting unless paired with proper regularization.
- Depth Challenges: The greedy GECO approach works well for depth-2 and depth-3, but as the network gets deeper, the "tensor approximation" problem required at each step becomes computationally expensive and harder to approximate.
- Activation Robustness: While $x^2$ activations are mathematically convenient, they may be more sensitive to outliers or exploding gradients in very deep architectures compared to the more stable ReLU. Future work could explore if these greedy methods can be adapted for non-polynomial activations.
Summary updated