Algorithmic Complexities in Backpropagation and Tropical Neural Networks
  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.
