The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

Vincent Froese, Christoph Hertrich, Rolf Niedermeier

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.

Architecture of a two-layer ReLU network with $d$ inputs and $k$ hidden 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$.

  1. 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.
  2. Algorithmic Design:
    • $\ell^\infty$-loss: For minimizing maximum error, a polynomial-time algorithm was developed using Linear Programming sequences and binary search.
  3. 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.

Summary of hardness results and algorithmic complexity for different 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

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},
}
Figure