Research map / Learning theory and algorithms / Sample complexity

On the Hardness of Training Deep Neural Networks Discretely

AAAI 2025 · Learning theory and algorithms › Sample complexity · approach: Hardness of learning neural networks · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Theoretical study showing discrete neural network training (D-NNT) on deep networks is not in NP under assumptions, and gives NP-hardness, ETH and pseudo-polynomial results for two-layer discrete and continuous training.

Problem

Computational complexity of neural network training (NNT) with discrete parameter sets (D-NNT) versus continuous parameters (C-NNT), especially how network depth affects hardness.

Approach

Reduces from straight-line program positivity (PosSLP) using identity/multiplication-like activations on a deep network with weights in {0,1,-1}, showing D-NNT is unlikely in NP; also gives NP-hardness, ETH lower bounds and a pseudo-polynomial DP for two-layer D-NNT with fixed dataset size.

Key results

• D-NNT on deep networks (input/output dimension 1, weights in {0,1,-1}) is not in NP under the Constructive Univariate Radical Conjecture and NP not in BPP.
• D-NNT on two-layer networks is NP-hard even with dataset size 1, dimension 1 and identity activation, unless P=NP.
• A pseudo-polynomial algorithm decides two-layer D-NNT in time poly(|I|) * M^{O(n_0)}.

Surprising findings

• D-NNT on deep networks is harder than any NP-complete problem under the stated assumptions, so depth alone isolates the source of hardness.
• Even a dataset of size one with a single neuron is NP-hard for discrete training.

Limitations

• Results rely on unproven conjectures (Constructive Univariate Radical Conjecture, ETH).
• Constructions use non-standard activations (multiplication/division-like), not ReLU or linear.
• Pseudo-polynomial algorithm is a theoretical proof-of-concept unlikely to be practical.

Experimental setup

Builds on: Constructive Univariate Radical Conjecture Exponential-Time Hypothesis

Closest papers by meaning

• Training Neural Networks is NP-Hard in Fixed Dimension (NeurIPS 2023 · similarity 0.91)
• Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy (NeurIPS 2023 · similarity 0.90)
• Deep Learning as a Mixed Convex-Combinatorial Optimization Problem (ICLR 2018 · similarity 0.89)
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (ICML 2019 · similarity 0.88)
• Understanding Deep Neural Networks with Rectified Linear Units (ICLR 2018 · similarity 0.88)
• Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.87)