New Algorithms Expand Tractability for Neural Network Training

Despite the widespread use of neural networks, the computational complexity of optimally training them, even with simple activation functions, remains a significant area of study. While recent work has established tighter lower bounds for training with linear and ReLU activations, less progress has been made in identifying new network architectures that are tractable in polynomial time. This paper addresses this gap by introducing novel algorithmic upper bounds for optimally training linear- and ReLU-activated neural networks. These new algorithms extend the known limits of tractability beyond the current state of the art. For ReLU networks, the research establishes polynomial-time tractability for all architectures where hidden neurons have an out-degree of 1, improving upon previous work. Furthermore, for networks employing linear activation functions, the study identifies the first non-trivial class of polynomial-time solvable networks. This is achieved through an algorithm capable of optimally training architectures that satisfy a newly defined "data throughput condition," opening new avenues for understanding and efficiently training specific network configurations.