Algorithmic Complexities in Backpropagation and Tropical Neural Networks

• URL: http://arxiv.org/abs/2101.00717v1
• Date: Sun, 3 Jan 2021 22:19:17 GMT
• Title: Algorithmic Complexities in Backpropagation and Tropical Neural Networks
• Authors: Ozgur Ceyhan
• Abstract summary: We introduce artificial neural networks in terms of tropical arithmetics and tropical algebraic geometry. We verify the algorithmic complexity is substantially lower than the usual backpropagation as the tropical arithmetic is free of the complexity of usual multiplication.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this note, we propose a novel technique to reduce the algorithmic complexity of neural network training by using matrices of tropical real numbers instead of matrices of real numbers. Since the tropical arithmetics replaces multiplication with addition, and addition with max, we theoretically achieve several order of magnitude better constant factors in time complexities in the training phase. The fact that we replace the field of real numbers with the tropical semiring of real numbers and yet achieve the same classification results via neural networks come from deep results in topology and analysis, which we verify in our note. We then explore artificial neural networks in terms of tropical arithmetics and tropical algebraic geometry, and introduce the multi-layered tropical neural networks as universal approximators. After giving a tropical reformulation of the backpropagation algorithm, we verify the algorithmic complexity is substantially lower than the usual backpropagation as the tropical arithmetic is free of the complexity of usual multiplication.

Related papers

• Tropical Expressivity of Neural Networks [0.0]
  We use tropical geometry to characterize and study various architectural aspects of neural networks. We present a new algorithm that computes the exact number of their linear regions.
  arXiv  Detail & Related papers  (2024-05-30T15:45:03Z)
• Riemannian Residual Neural Networks [58.925132597945634]
  We show how to extend the residual neural network (ResNet) ResNets have become ubiquitous in machine learning due to their beneficial learning properties, excellent empirical results, and easy-to-incorporate nature when building varied neural networks.
  arXiv  Detail & Related papers  (2023-10-16T02:12:32Z)
• 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)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  Tropical geometry has recently found several applications in the analysis of neural networks with piecewise linear activation functions. This paper presents a new look at the problem of tropical division and its application to the simplification of neural networks.
  arXiv  Detail & Related papers  (2023-06-27T02:26:07Z)
• A predictive physics-aware hybrid reduced order model for reacting flows [65.73506571113623]
  A new hybrid predictive Reduced Order Model (ROM) is proposed to solve reacting flow problems. The number of degrees of freedom is reduced from thousands of temporal points to a few POD modes with their corresponding temporal coefficients. Two different deep learning architectures have been tested to predict the temporal coefficients.
  arXiv  Detail & Related papers  (2023-01-24T08:39:20Z)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Generalization Error Bounds for Iterative Recovery Algorithms Unfolded as Neural Networks [6.173968909465726]
  We introduce a general class of neural networks suitable for sparse reconstruction from few linear measurements. By allowing a wide range of degrees of weight-sharing between the layers, we enable a unified analysis for very different neural network types.
  arXiv  Detail & Related papers  (2021-12-08T16:17:33Z)
• 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)
• ResNet-LDDMM: Advancing the LDDMM Framework Using Deep Residual Networks [86.37110868126548]
  In this work, we make use of deep residual neural networks to solve the non-stationary ODE (flow equation) based on a Euler's discretization scheme. We illustrate these ideas on diverse registration problems of 3D shapes under complex topology-preserving transformations.
  arXiv  Detail & Related papers  (2021-02-16T04:07:13Z)
• Compressive Sensing and Neural Networks from a Statistical Learning Perspective [4.561032960211816]
  We present a generalization error analysis for a class of neural networks suitable for sparse reconstruction from few linear measurements. Under realistic conditions, the generalization error scales only logarithmically in the number of layers, and at most linear in number of measurements.
  arXiv  Detail & Related papers  (2020-10-29T15:05:43Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)

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.