The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality
Authors: Vincent Froese, Christoph Hertrich, Rolf Niedermeier
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Understanding the computational complexity of training simple neural networks with rectified linear units (Re LUs) 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 Re LU networks with respect to various loss functions. |
| Researcher Affiliation | Academia | Vincent Froese EMAIL Technische Universit at Berlin, Algorithmics and Computational Complexity, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany Christoph Hertrich EMAIL London School of Economics and Political Science, Department of Mathematics, Houghton Street, London WC2A 2AE, United Kingdom Rolf Niedermeier EMAIL Technische Universit at Berlin, Algorithmics and Computational Complexity, Ernst-Reuter-Platz 7, D-10587 Berlin, Germany |
| Pseudocode | No | The paper describes algorithms and methods in prose, such as 'Following the approach by Arora et al. (2018, Algorithm 1)', but does not include any clearly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code, nor does it include links to code repositories. |
| Open Datasets | No | The paper is theoretical and defines problems based on abstract 'Data points (x1, y1), . . . , (xn, yn) Rd R'. It does not refer to any specific publicly available datasets or provide access information for any data used in experiments. |
| Dataset Splits | No | As this is a theoretical paper focused on computational complexity, no specific datasets are used for experiments, and thus no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity analysis and algorithm design. It does not describe any experimental setup or mention specific hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental implementation, therefore no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper focuses on theoretical analysis of computational complexity and algorithm design. It does not include any experimental results or describe a specific experimental setup with hyperparameters or training settings. |