Abstract
Training neural networks is a fundamental challenge in machine learning, often known to be NP-hard in general. This paper investigates the parameterized complexity of training two-layer ReLU networks, focusing on the data dimensionality $d$ as a key parameter. We demonstrate that training even a single-neuron ReLU network is W[1]-hard with respect to $d$. However, for fixed low dimensions, we provide exact algorithms for various loss functions, establishing that while training is generally difficult, it becomes tractable in low-dimensional spaces, albeit with a likely optimal $n^{O(d)}$ complexity.
Introduction
While deep neural network training is computationally demanding, researchers frequently hypothesize that specific constraints—such as a limited number of neurons or low-dimensional data manifolds—might alleviate this complexity. This study rigorously examines how the dimensionality $d$ of input data influences the difficulty of training a two-layer network with $k$ hidden ReLU neurons.
The authors specifically address whether a small $d$ allows for efficient training. While prior research established tractability for convex loss functions like Mean Squared Error, this work fills critical gaps regarding non-convex losses and provides theoretical lower bounds on algorithmic performance.
Methodology and Theoretical Framework
The research utilizes Parameterized Complexity Theory to analyze how running times scale with parameters $d$ and $k$.
- Hardness Reductions: By reducing the Multicolored Clique problem to the training task, the authors prove that training is W[1]-hard. This implies that no algorithm can be efficient for all dimensions unless a major breakthrough in complexity theory occurs.
- Algorithmic Design:
- $\ell^\infty$-loss: For minimizing maximum error, a polynomial-time algorithm was developed using Linear Programming sequences and binary search.
- Concave loss functions: The authors extended "XP-algorithms" by partitioning the data space into regions where ReLU neurons are either active or inactive, then enumerating vertices of the resulting polyhedral error surfaces.
As a theoretical study, the "data" consists of synthetic mathematical constructions designed to represent hard instances of combinatorial problems rather than standard empirical datasets.
Key Insights
- Complexity of a Single Neuron: Surprisingly, even a single ReLU neuron is difficult to train. The "breakpoint" in the ReLU function introduces sufficient combinatorial complexity to make the problem W[1]-hard relative to dimension $d$.
- Optimality of Brute Force: The paper establishes that algorithms with $n^{O(d)}$ running time are likely the best possible. Under the Exponential Time Hypothesis (ETH), no algorithm can achieve $n^{o(d)}$ time.
- Expanding the Loss Landscape: The study shows that concave losses, useful for outlier-robust training, are solvable in "XP-time" (polynomial time for a constant $d$).
- The $\ell^\infty$ Exception: Minimizing the maximum error ($\ell^\infty$-loss) for a single neuron is uniquely solvable in polynomial time, independent of dimension.
Key Results
The primary findings categorize the hardness and algorithmic complexity across different $\ell^p$ loss functions.
Key results include:
- Hardness: 1-ReLU training is NP-hard and W[1]-hard for $\ell^p$-loss where $p \in [0, \infty[$.
- Lower Bounds: No $n^{o(d)}$ algorithm exists unless ETH is false.
- New Algorithms: A concave loss algorithm running in $2^k(nk)^{O(dk)} \text{poly}(n, d, k)$ time and a polynomial-time algorithm for the $\ell^\infty$-loss case ($k=1$).
Conclusion and Future Work
This work clarifies the complexity of two-layer ReLU networks but leaves several avenues open. The complexity of deeper architectures within this parameterized framework remains unknown. Additionally, while $n^{O(d)}$ is technically polynomial for fixed $d$, it remains impractical for even moderate dimensions (e.g., $d=20$). Future research may focus on "Fixed-Parameter Tractable" (FPT) algorithms that avoid $d$ in the exponent, perhaps by exploiting data sparsity or investigating approximation ratios rather than exact solutions.
Summary updated