The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

Vincent Froese, Christoph Hertrich, Rolf Niedermeier

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.

The two-layer ReLU architecture studied in the paper, featuring $d$ inputs, $k$ hidden neurons, and one output.

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$.

  1. 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.
  2. 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.
  3. 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.

A summary of the hardness and algorithmic results for training a single ReLU neuron across different loss types.
  • 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

Abstract

Understanding the computational complexity of training simple neural networks with rectified linear units (ReLUs) has recently been a subject of intensive research. Closing gaps and complementing results from the literature, we present several results on the parameterized complexity of training two-layer ReLU networks with respect to various loss functions. After a brief discussion of other parameters, we focus on analyzing the influence of the dimension $d$ of the training data on the computational complexity. We provide running time lower bounds in terms of W[1]-hardness for parameter $d$ and prove that known brute-force strategies are essentially optimal (assuming the Exponential Time Hypothesis). In comparison with previous work, our results hold for a broad(er) range of loss functions, including $\ell^p$-loss for all $p\in[0,\infty]$. In particular, we extend a known polynomial-time algorithm for constant $d$ and convex loss functions to a more general class of loss functions, matching our running time lower bounds also in these cases.
BibTeX
@article{froese2022computational,
  author = {Vincent Froese and Christoph Hertrich and Rolf Niedermeier},
  title = {{The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.13547},
}

Loading related content...

Figure