Research map / Learning theory and algorithms / Sample complexity
Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions
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.
Shows that neural network training with arbitrary activation functions is polynomial-time bireducible to the existential theory of the reals extended with those functions, and places effectively continuous activations (e.g., sigmoid) in low arithmetical hierarchy levels while sinusoidal training is undecidable.
Problem
The computational complexity of neural network training (deciding whether weights and biases exist achieving training error below a threshold) for non-linear activation functions such as sigmoid and sine, beyond ReLU and linear activations which are known to be ∃R-complete.
Approach
Generalizes the ∃R-completeness of NN training from ReLU/linear to arbitrary unary activation functions by defining complexity classes ∃R_τ over extended reals, proving NN training is ∃R_τ-complete, and using effective continuity and compactness to bound the complexity of ∃R_ECF in the arithmetical hierarchy (Σ0_3, and Σ0_1 without equality).
Key results
- NN training with arbitrary unary activation set τ is ∃R_τ-complete (Theorem 18).
- NN training with sigmoid activation is ∃R_exp-complete, so its decidability is equivalent to decidability of existential exponential arithmetic (Corollary 19).
- NN training with sinusoidal activations is undecidable but lies in Σ0_3 (Corollary 20).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use activation functions from τ together with identity activation | Neural network training · NNτ-TRAINING | computational complexity | Mixed |
| Use sigmoid activation | Neural network training · NNσ-TRAINING | computational complexity | Mixed |
| Use sinusoidal activation | Neural network training · NNsin-TRAINING | decidability | Hurt |
| Restrict the added functions to effectively continuous functions | Existential theory of the reals with added functions · ∃RECF | computational complexity | Helped |
| Disallow equality | Existential theory with effectively continuous functions · ∃R<ECF | computational complexity | Helped |
Surprising findings
- Training with sinusoidal activation functions is undecidable, giving theoretical grounding to observed training difficulties.
- Disallowing equality in the formulas drops the upper bound for effectively continuous activations from Σ0_3 to Σ0_1.
Limitations
- Upper bound for the identity-free existential theory of reals with effectively continuous functions is only Σ0_1; the exact relationship of ∃R_exp to Σ0_1 and Σ0_3 remains open.
- Open whether results hold for fully connected architectures with all weights and biases active, or networks with a single shared activation function.
- Open when complexities of NN-TRAINING and its restricted variants (≤, <) coincide.
Experimental setup
Builds on: ETR-completeness of ReLU network training (Abrahamsen, Kleist, and Miltzow 2021) Bertschinger et al. 2022 fully connected NN training is ∃R-complete Schaefer and Stefankovic 2017 4-FEAS Servi 2008 effectively continuous functions
Closest papers by meaning
- New Complexity-Theoretic Frontiers of Tractability for Neural Network Training (NeurIPS 2023 · similarity 0.89)
- Training Neural Networks is ER-complete (NeurIPS 2021 · similarity 0.87)
- On the Complexity of Learning Neural Networks (NeurIPS 2017 · similarity 0.87)
- L1-regularized Neural Networks are Improperly Learnable in Polynomial Time (ICML 2016 · similarity 0.87)
- On the Hardness of Training Deep Neural Networks Discretely (AAAI 2025 · similarity 0.84)
- Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Context (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.