Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
On the Hardness of Training Deep Neural Networks Discretely
Authors: Ilan Doron-Arad
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we show that the hardness of NNT is dramatically affected by the network depth. Specifically, we show that, under standard complexity assumptions, D-NNT is not in the complexity class NP even for instances with fixed dimensions and dataset size, having a deep architecture. This separates D-NNT from any NP-complete problem. Furthermore, using a polynomial reduction we show that the above result also holds for C-NNT, albeit with more structured instances. We complement these results with a comprehensive list of NP-hardness lower bounds for D-NNT on two-layer networks, showing that fixing the number of dimensions, the dataset size, or the number of neurons in the hidden layer leaves the problem challenging. Finally, we obtain a pseudopolynomial algorithm for D-NNT on a two-layer network with a fixed dataset size. |
| Researcher Affiliation | Academia | Ilan Doron-Arad Technion Israel Institute of Technology, Haifa, Israel EMAIL |
| Pseudocode | Yes | Algorithm 1: Dynamic Programming Algorithm Input: a D-NNT instance I Output: true if I is a Yes-instance 1: Compute the dynamic program Dim DP. 2: Compute the dynamic program Final DP. 3: Compute the model fθ based on Dim DP and Final DP. 4: return true if and only if Pn0 i=1 L (fθ(xi), yi) γ. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code, nor does it include links to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper defines the Neural Network Training (NNT) problem with a theoretical dataset D = {(xi, yi)}n i=1 but does not use any specific publicly available dataset for empirical studies or provide access information for any dataset. It's a theoretical paper. |
| Dataset Splits | No | The paper is theoretical and focuses on complexity analysis and algorithms without performing empirical experiments on specific datasets, therefore, it does not provide details on dataset splits. |
| Hardware Specification | No | The paper is theoretical, presenting complexity results and algorithms without conducting empirical experiments, hence it does not specify any hardware used. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation or empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis and algorithms. It does not include an experimental section with specific setup details, hyperparameters, or training configurations. |