Pith. sign in

REVIEW 2 cited by

Training Neural Networks is NP-Hard in Fixed Dimension

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2303.17045 v2 pith:TW2WVAV3 submitted 2023-03-29 cs.CC cs.DScs.LGcs.NEstat.ML

Vincent Froese , Christoph Hertrich This is my paper · ORCID
classification cs.CCcs.DScs.LGcs.NEstat.ML
keywords complexitydimensionnumbertraininganswerdimensionslinearnetworks
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. [ICLR '18] and Khalife and Basu [IPCO '22] showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. [JAIR '22] proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 4 citations worldwide. Full citation record

  1. New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

    cs.LG 2026-07 conditional novelty 7.0 of 10

    Constant-size ReLU networks with hidden out-degree 1 and linear networks admitting an 'untangling' are optimizable in polynomial time, via hyperplane-partition enumeration and constrained linear regression.

  2. Computational Math with Neural Networks is Hard

    math.NA 2025-05 conditional novelty 7.0 of 10

    Under SETH, approximating integrals, Poisson solutions, or matrix-vector products for neural network inputs requires runtime at least accuracy^{-1+o(1)}.

Pith tools