TL;DR
Training even the simplest two-layer ReLU neural network is computationally "hard" when the number of data dimensions is the limiting factor. This research proves that for most common loss functions, the best possible training algorithms are essentially brute-force searches, settling a long-standing question about the role of data dimensionality in network training complexity.
What Problem Does This Paper Address?
In machine learning, we often assume that even if our data has thousands of features, it actually lives on a much simpler, "low-dimensional" manifold. If this is true, can we exploit that low dimensionality to train neural networks faster?
While linear models (like Support Vector Machines) are easy to train in polynomial time, adding even a single non-linear layer—like the Rectified Linear Unit (ReLU)—makes the math much messier. Previous research had shown that training ReLU networks is NP-hard in general, but it wasn't clear if the problem became easy when the data dimension ($d$) was small. This paper investigates the parameterized complexity of training two-layer ReLU networks, specifically focusing on how the input dimension $d$ affects the time it takes to find an optimal set of weights.
Methods
The authors employ the toolkit of parameterized complexity analysis. Instead of just asking if a problem is "fast" or "slow," they ask how the running time scales with specific parameters—in this case, the dimension $d$.
- Hardness Reductions: To prove the problem is difficult, they perform a reduction from the "Multicolored Clique" problem. They show that if you could train a single ReLU neuron efficiently for small $d$, you could also solve a known hard combinatorial problem, which is highly unlikely.
- Algorithm Design: On the positive side, they develop new algorithms for specific scenarios. For the $\ell^\infty$-loss (which minimizes the single largest error), they provide a polynomial-time algorithm using a series of linear programs.
- XP-Algorithms: For concave loss functions (often used for outlier robustness), they provide an "XP-algorithm," which runs in polynomial time if the dimension $d$ is held constant, but the exponent of the polynomial grows with $d$.
Datasets
As a theoretical complexity paper, this work does not use standard empirical benchmarks like ImageNet or CIFAR-10. Instead, it uses mathematical constructions to prove worst-case bounds. The "data" used in their proofs consists of synthetic points in $R^d$ designed to encode graph-theoretical problems, demonstrating that the training task is hard even for very sparse data with binary labels.
Key Insights and Ideas
- The "Single Neuron" Barrier: One of the most surprising findings is that training is hard even for a network with only one hidden neuron ($k=1$). This shows that the jump from a linear model to a non-linear one is where the primary computational explosion happens.
- Brute Force is Optimal: The authors show that existing "brute-force" strategies—which essentially try every possible way to partition data points with hyperplanes—are essentially the best we can do. Specifically, they show that under the Exponential Time Hypothesis (ETH), no algorithm can significantly beat a running time of $n^{O(d)}$.
- Loss Function Generality: Unlike previous work that focused almost exclusively on squared error ($\ell^2$-loss), these results apply to a massive range of $\ell^p$-loss functions, including those that are convex ($p \ge 1$), concave ($0 < p < 1$), and even the outlier-counting $\ell^0$-loss.
Key Results
The paper provides a complete classification of the complexity of training a single ReLU neuron across different loss functions.
- W[1]-hardness: Proved for all $\ell^p$-loss functions where $p < \infty$. This means that as the dimension $d$ increases, the training time grows explosively, and we shouldn't expect a "fixed-parameter tractable" (FPT) algorithm.
- $\ell^\infty$ is "Easy": They discovered that the $\ell^\infty$-loss is a rare exception that can be solved in polynomial time for a single neuron, regardless of dimension.
- Tight Bounds: For concave losses, they matched the lower bounds with a new algorithm that runs in $n^{O(dk)}$ time, effectively closing the gap between what is theoretically possible and what we currently know how to do.
Limitations and Future Work
While this paper settles the case for two-layer networks and the dimension parameter $d$, several doors remain open:
- Deeper Networks: The current proofs focus on two-layer networks. The complexity of training networks with three or more layers is likely even higher and requires new techniques to analyze.
- Approximation: The paper deals with finding exact optimal solutions. A natural next step is to see if "good enough" approximate solutions can be found in FPT-time (time where the exponent of $n$ doesn't depend on $d$).
- Data Structure: The authors suggest looking at other parameters, such as the "distance from triviality" of the input data, to see if specific data distributions allow for faster training.
Summary updated