# New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

arXiv: https://arxiv.org/abs/2607.20811 · HTML: https://mlsanity.com/paper/2607.20811/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 46 references that are in the map.
- First posted on arXiv 23 Jul 2026.

## Builds on (most cited first, 19 of 19)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [On the Expressive Power of Deep Learning: A Tensor Analysis](https://mlsanity.com/paper/1509.05009/) (2015)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Complexity of Training ReLU Neural Network](https://mlsanity.com/paper/1809.10787/) (2018)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Effect of Activation Functions on the Training of Overparametrized Neural Nets](https://mlsanity.com/paper/1908.05660/) (2019)
- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Parameterized Complexity Results for Exact Bayesian Network Structure Learning](https://mlsanity.com/paper/1402.0558/) (2014)
- [Parameterized Algorithms for the Matrix Completion Problem](https://mlsanity.com/paper/1804.03423/) (2018)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [Parameterized Algorithms for MILPs with Small Treedepth](https://mlsanity.com/paper/1912.03501/) (2019)
- [High-contrast "gaudy" images improve the training of deep neural network models of visual cortex](https://mlsanity.com/paper/2006.11412/) (2020)
- [The Complexity of Bayesian Network Learning: Revisiting the Superstructure](https://mlsanity.com/paper/2602.10253/) (2026)

## Built on by (most cited first, 2 of 2)

- [Parameterized Complexity of Lp-Lipschitz Constants for Input Convex Neural Networks and Lp-Norm Maximization over Zonotopes](https://mlsanity.com/paper/2608.24865/) (2026)
- [Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions](https://mlsanity.com/paper/2609.27932/) (2026)

## Abstract (arXiv)

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of 1, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.