On the algorithmic construction of deep ReLU networks

• URL: http://arxiv.org/abs/2506.19104v1
• Date: Mon, 23 Jun 2025 20:35:52 GMT
• Title: On the algorithmic construction of deep ReLU networks
• Authors: Daan Huybrechs,
• Abstract summary: We take the perspective of a neural network as an algorithm.<n>In this analogy, a neural network is programmed constructively, rather than trained from data.<n>We construct and analyze several other examples, both existing and new.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is difficult to describe in mathematical terms what a neural network trained on data represents. On the other hand, there is a growing mathematical understanding of what neural networks are in principle capable of representing. Feedforward neural networks using the ReLU activation function represent continuous and piecewise linear functions and can approximate many others. The study of their expressivity addresses the question: which ones? Contributing to the available answers, we take the perspective of a neural network as an algorithm. In this analogy, a neural network is programmed constructively, rather than trained from data. An interesting example is a sorting algorithm: we explicitly construct a neural network that sorts its inputs exactly, not approximately, and that, in a sense, has optimal computational complexity if the input dimension is large. Such constructed networks may have several billion parameters. We construct and analyze several other examples, both existing and new. We find that, in these examples, neural networks as algorithms are typically recursive and parallel. Compared to conventional algorithms, ReLU networks are restricted by having to be continuous. Moreover, the depth of recursion is limited by the depth of the network, with deep networks having superior properties over shallow ones.

Related papers

• Algorithm Development in Neural Networks: Insights from the Streaming Parity Task [8.188549368578704]
  We study the learning dynamics of neural networks trained on a streaming parity task.<n>We show that, with sufficient finite training experience, RNNs exhibit a phase transition to perfect infinite generalization.<n>Our results disclose one mechanism by which neural networks can generalize infinitely from finite training experience.
  arXiv  Detail & Related papers  (2025-07-14T04:07:43Z)
• Verified Neural Compressed Sensing [58.98637799432153]
  We develop the first (to the best of our knowledge) provably correct neural networks for a precise computational task. We show that for modest problem dimensions (up to 50), we can train neural networks that provably recover a sparse vector from linear and binarized linear measurements. We show that the complexity of the network can be adapted to the problem difficulty and solve problems where traditional compressed sensing methods are not known to provably work.
  arXiv  Detail & Related papers  (2024-05-07T12:20:12Z)
• DeepCSHAP: Utilizing Shapley Values to Explain Deep Complex-Valued Neural Networks [7.4841568561701095]
  Deep Neural Networks are widely used in academy as well as corporate and public applications. The ability to explain their output is critical for safety reasons as well as acceptance among applicants. We present four gradient based explanation methods suitable for use in complex-valued neural networks.
  arXiv  Detail & Related papers  (2024-03-13T11:26:43Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• 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)
• Dive into Layers: Neural Network Capacity Bounding using Algebraic Geometry [55.57953219617467]
  We show that the learnability of a neural network is directly related to its size. We use Betti numbers to measure the topological geometric complexity of input data and the neural network. We perform the experiments on a real-world dataset MNIST and the results verify our analysis and conclusion.
  arXiv  Detail & Related papers  (2021-09-03T11:45:51Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
  arXiv  Detail & Related papers  (2021-07-31T10:25:26Z)
• Artificial Neural Networks generated by Low Discrepancy Sequences [59.51653996175648]
  We generate artificial neural networks as random walks on a dense network graph. Such networks can be trained sparse from scratch, avoiding the expensive procedure of training a dense network and compressing it afterwards. We demonstrate that the artificial neural networks generated by low discrepancy sequences can achieve an accuracy within reach of their dense counterparts at a much lower computational complexity.
  arXiv  Detail & Related papers  (2021-03-05T08:45:43Z)
• The Representation Theory of Neural Networks [7.724617675868718]
  We show that neural networks can be represented via the mathematical theory of quiver representations. We show that network quivers gently adapt to common neural network concepts. We also provide a quiver representation model to understand how a neural network creates representations from the data.
  arXiv  Detail & Related papers  (2020-07-23T19:02:14Z)
• Towards Understanding Hierarchical Learning: Benefits of Neural Representations [160.33479656108926]
  In this work, we demonstrate that intermediate neural representations add more flexibility to neural networks. We show that neural representation can achieve improved sample complexities compared with the raw input. Our results characterize when neural representations are beneficial, and may provide a new perspective on why depth is important in deep learning.
  arXiv  Detail & Related papers  (2020-06-24T02:44:54Z)

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.