New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

Cornelius Brand, Robert Ganian, Mathis Rocton

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networ…