This paper delves into the computational complexity of training neural networks, a topic that has seen a resurgence of interest with the rise of deep learning. The authors aim to bridge the gap between the theoretical hardness of training neural networks and their practical success. They introduce new algorithms and theoretical results that shed light on when and how neural networks can be trained efficiently.
TL;DR
This paper revisits the computational efficiency of training neural networks, offering both theoretical hardness results and new algorithms for specific network architectures. It demonstrates that sufficiently over-specified networks are easier to train and introduces efficient algorithms for polynomial networks, suggesting that computational complexity can decrease with architectural choices and over-specification.
What Problem Does This Paper Address?
Neural networks, particularly deep ones, have achieved remarkable success in various machine learning tasks. However, from a theoretical standpoint, training them is often considered computationally hard, with many learning problems being NP-hard or even computationally infeasible in the worst case. This theoretical pessimism contrasts sharply with the practical efficiency observed when training modern neural networks using techniques like Stochastic Gradient Descent (SGD) and various "tricks" such as different activation functions (e.g., ReLU), over-specification (using larger networks than strictly necessary), and regularization.
This paper seeks to reconcile this discrepancy by re-examining the computational complexity of training neural networks from a modern perspective. It investigates how architectural choices, such as network depth and size, and training strategies like over-specification and regularization, influence the difficulty of finding a good predictor. The authors aim to provide a more nuanced understanding of when neural network training is computationally tractable and to develop provably efficient algorithms for certain classes of neural networks.
Methods
The paper employs a combination of theoretical analysis and algorithmic development. Key methods include:
- Theoretical Hardness Proofs: The authors leverage existing complexity-theoretic results (e.g., from cryptographic assumptions or average-case complexity) to prove that certain classes of neural networks, particularly those with threshold, sigmoidal, and ReLU activation functions without regularization, are not efficiently learnable. This is often achieved by showing that these classes contain known hard-to-learn problems like intersections of halfspaces.
- Polynomial Networks: A significant portion of the paper focuses on "polynomial networks," which use a squared activation function (σ(z) = z²). This choice allows the networks to compute polynomial functions of their inputs. The authors explore their expressiveness and learnability.
- Algorithmic Development (GECO): For polynomial networks, particularly depth-2 and depth-3 networks, the paper proposes and analyzes a practical, provably correct algorithm based on the Greedy Eigenvector Convex Optimization (GECO) framework. This algorithm iteratively adds neurons in a greedy fashion, solving an eigenvalue or tensor approximation problem at each step to minimize a loss function. This approach aims to circumvent the hardness results associated with other activation functions.
- Approximation Techniques: The paper utilizes approximations of the sigmoid function using Chebyshev polynomials to relate sigmoidal networks to polynomial networks, enabling learning guarantees for the former.
- Over-specification Analysis: The authors make a simple but important observation that for sufficiently over-specified networks, the optimization landscape becomes easier, with global optima being more ubiquitous and computationally accessible.
Datasets
- Pedestrian Detection Problem: The authors used a dataset of 200,000 image patches for a pedestrian detection task. These patches were either positive examples (pedestrians) or hard negative examples. Half of the dataset was used for training and the other half for testing.
- HoG Features: Histograms of Oriented Gradients (HoG) features were extracted from the image patches for use as input to the neural networks.
The paper does not introduce new benchmark datasets but rather uses a standard problem domain (pedestrian detection) to evaluate their proposed algorithms.
Key Insights and Ideas
- Over-specification Simplifies Optimization: The paper highlights that while over-specified networks might overfit, the optimization problem associated with training them becomes significantly easier, with global optima being more accessible. This suggests a trade-off between model complexity and training difficulty.
- Polynomial Networks as a Tractable Alternative: By switching to polynomial activation functions (e.g., squared activation), the authors demonstrate that certain classes of neural networks become efficiently learnable. This offers a theoretical pathway to circumventing the hardness results associated with more common activation functions.
- GECO Algorithm for Efficient Training: The proposed GECO algorithm provides a practical and provably correct method for training depth-2 and depth-3 polynomial networks. Its greedy approach, based on solving eigenvalue or tensor approximation problems, offers a more efficient alternative to standard gradient-based methods for these specific architectures.
- Bridging Theory and Practice: The paper actively tries to connect theoretical hardness results with practical training observations. It suggests that techniques like over-specification and the choice of activation functions are crucial for achieving computational efficiency in practice, even if theoretical worst-case scenarios remain hard.
Key Results
- Hardness Results: The paper proves that neural networks with threshold, sigmoidal, and ReLU activation functions (without regularization) are not efficiently learnable, even for depth-2 networks, under standard complexity assumptions.
- Expressiveness of Polynomial Networks: Polynomial networks with quadratic activation are shown to be as expressive as networks with threshold activation, capable of implementing any function computable by a Turing machine within a certain time bound.
- Efficient Learnability of Polynomial Networks: Constant-depth polynomial networks are shown to be efficiently learnable in polynomial time using a linearization trick.
- GECO Performance: In experiments on a pedestrian detection task, the GECO algorithm for training depth-2 polynomial networks was found to be competitive with, and often faster than, SGD for training similar networks with ReLU or squared activations. GECO achieved slightly better test errors and required fewer iterations for a good solution.
- Over-specification Benefit: Experiments demonstrated that SGD converges much faster when the network is over-specified, reinforcing the paper's theoretical observation.
Limitations and Future Work
- Practicality of Theoretical Algorithms: While theoretical results for polynomial networks are positive, some algorithms derived from them might still be impractical due to large polynomial dependencies on parameters like depth or dimension. The GECO algorithm aims to address this for specific depths.
- Assumptions for Hardness Results: The hardness results for sigmoidal and ReLU networks rely on specific complexity assumptions (e.g., cryptographic assumptions or average-case complexity). If these assumptions do not hold, the hardness might be circumvented.
- Generalization to Deeper Networks: The paper focuses on depth-2 and depth-3 polynomial networks for its practical algorithms. Extending these efficient algorithms to arbitrary depths remains an open challenge.
- Distribution-Free Learning: The paper primarily focuses on distribution-free learning settings. Results might differ under specific data distribution assumptions.
- Future Work: The authors suggest exploring polynomial networks with constant depth and bounded regularization for efficient learning. They also point to the potential of their GECO algorithm for other convex optimization problems with low-rank constraints. Further investigation into the interplay between over-specification, regularization, and computational complexity across various network architectures is also suggested.
Summary updated