The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality

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.

References in corpus (10)

• Understanding Deep Neural Networks with Rectified Linear Units
• The parameterized complexity of some geometric problems in unbounded dimension
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Training Neural Networks is $\exists \mathbb{R}$-complete
• Approximation Schemes for ReLU Regression
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
• Training Fully Connected Neural Networks is $\exists \mathbb{R}$-Complete
• Refined Complexity of PCA with Outliers
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• Towards Lower Bounds on the Depth of ReLU Neural Networks

Cited by in corpus (3)

• Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size
• Towards Lower Bounds on the Depth of ReLU Neural Networks
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation