New Complexity-Theoretic Frontiers of Tractability for Neural Network Training

• URL: http://arxiv.org/abs/2607.20811v1
• Date: Thu, 23 Jul 2026 00:44:44 GMT
• Title: New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
• Abstract summary: In spite of the fundamental role of neural networks in machine learning research, our understanding of optimally training neural networks remains incomplete.<n>In this article we obtain novel algorithmic upper bounds for training and ReLU-activated neural networks to optimality.
• Score: 17.54018378847318
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective [51.908606610432194]
  Deep neural networks (DNNs) have achieved remarkable success across diverse machine learning tasks.<n>Recent research has uncovered several convexities in the loss of certain NN architectures.
  arXiv  Detail & Related papers  (2026-03-25T01:34:04Z)
• NeuralFastLAS: Fast Logic-Based Learning from Raw Data [54.938128496934695]
  Symbolic rule learners generate interpretable solutions, however they require the input to be encoded symbolically. Neuro-symbolic approaches overcome this issue by mapping raw data to latent symbolic concepts using a neural network. We introduce NeuralFastLAS, a scalable and fast end-to-end approach that trains a neural network jointly with a symbolic learner.
  arXiv  Detail & Related papers  (2023-10-08T12:33:42Z)
• When Deep Learning Meets Polyhedral Theory: A Survey [5.59187625600025]
  In the past decade, deep became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural learning.<n>Meanwhile, the structure of neural networks converged back to simplerwise and linear functions.
  arXiv  Detail & Related papers  (2023-04-29T11:46:53Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  We study weight decay regularized training problems of deep neural networks with threshold activations. We derive a simplified convex optimization formulation when the dataset can be shattered at a certain layer of the network.
  arXiv  Detail & Related papers  (2023-03-06T18:59:13Z)
• Spiking neural network for nonlinear regression [68.8204255655161]
  Spiking neural networks carry the potential for a massive reduction in memory and energy consumption. They introduce temporal and neuronal sparsity, which can be exploited by next-generation neuromorphic hardware. A framework for regression using spiking neural networks is proposed.
  arXiv  Detail & Related papers  (2022-10-06T13:04:45Z)
• Neural networks with linear threshold activations: structure and algorithms [1.795561427808824]
  We show that 2 hidden layers are necessary and sufficient to represent any function representable in the class. We also give precise bounds on the sizes of the neural networks required to represent any function in the class. We propose a new class of neural networks that we call shortcut linear threshold networks.
  arXiv  Detail & Related papers  (2021-11-15T22:33:52Z)
• A Weight Initialization Based on the Linear Product Structure for Neural Networks [0.0]
  We study neural networks from a nonlinear point of view and propose a novel weight initialization strategy that is based on the linear product structure (LPS) of neural networks. The proposed strategy is derived from the approximation of activation functions by using theories of numerical algebra to guarantee to find all the local minima.
  arXiv  Detail & Related papers  (2021-09-01T00:18:59Z)
• Validation of RELU nets with tropical polyhedra [7.087237546722617]
  We present an approach that abstracts ReLU feedforward neural networks using tropical polyhedra. We show how the connection between ReLU networks and tropical rational functions can provide approaches for range analysis of ReLU neural networks.
  arXiv  Detail & Related papers  (2021-07-30T06:22:59Z)
• Implicit recurrent networks: A novel approach to stationary input processing with recurrent neural networks in deep learning [0.0]
  In this work, we introduce and test a novel implementation of recurrent neural networks into deep learning. We provide an algorithm which implements the backpropagation algorithm on a implicit implementation of recurrent networks. A single-layer implicit recurrent network is able to solve the XOR problem, while a feed-forward network with monotonically increasing activation function fails at this task.
  arXiv  Detail & Related papers  (2020-10-20T18:55:32Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  We propose a topological perspective to represent a network into a complete graph for analysis. By assigning learnable parameters to the edges which reflect the magnitude of connections, the learning process can be performed in a differentiable manner. This learning process is compatible with existing networks and owns adaptability to larger search spaces and different tasks.
  arXiv  Detail & Related papers  (2020-08-19T04:53:31Z)
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks [54.27962244835622]
  This paper proposes a new mean-field framework for over- parameterized deep neural networks (DNNs) In this framework, a DNN is represented by probability measures and functions over its features in the continuous limit. We illustrate the framework via the standard DNN and the Residual Network (Res-Net) architectures.
  arXiv  Detail & Related papers  (2020-07-03T01:37:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.