# Algorithmic Complexities in Backpropagation and Tropical Neural Networks

Özgür Ceyhan
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

The main strategies for building capable and more efficient neural networks
can be summarised as

  1. (I)

Developing and manufacturing more capable hardware;

  2. (II)

Designing smaller and more robust versions of neural networks that realise the
same tasks;

  3. (III)

Reducing the computational complexities of learning algorithms without
changing the structures of neural networks or hardware.

The approach (I) is an industrial design and manufacturing challenge. The
approach (II) is essentially the subject of network pruning. This note will
focus only on a theoretical approach on (III) based on tropical arithmetics
and geometry.

The main training method of multi-layered neural networks is the
backpropagation algorithm and its variations (see, for instance [Ru16] for
variants of backpropagation and their properties). The backpropagation is
essentially a recursive gradient descent technique that works on large
matrices. However, the sizes of the matrices determined by the initial
parameters of neural networks are enormous: The state-of-the-art applications
may have $10^{6}$-$10^{7}$ neurons, therefore, have as many parameters as the
pairings of these neurons, see [DBBNG, §1.2.4]. Many neural network
implementations require adequately large computational resources when the
scale of computations is that big, see [DBBNG] and references therein.
Naturally, since the computational resources required are large, any reduction
in the algorithmic complexity of elementary operations is going to provide
substantial advantages. To this end, we would like to eliminate the basic
arithmetic operation of multiplication, which is algorithmically more complex
than addition, subtraction and $min/max$, without changing the nature of the
classification problem that we wish to realise with a neural network.

We propose to reach our goal by using tropical arithmetics and tropical
geometry. While tropicalisation is a relatively new concept, its core idea has
been used in engineering for decades in areas such as the linear control
theory and the combinatorial optimisation. The effective use of
tropicalization in mathematics goes back to Viro in the 80’s where he
constructs real algebraic varieties with prescribed topology to address
Hilbert’s 16th and related problems [Vi06]. Further studies on Viro’s method
revealed the tropical semiring, an algebraic structure whose arithmetics is
devoid of multiplication, is the key algebraic structure behind Viro’s results
[Vi01]. In this note we claim that the tropical geometry also provides a
suitable setup to construct the backpropagation algorithm with substantially
better complexity.

After briefly describing the sources of the algorithmic complexities in
backpropagation techniques in §2, and introducing the basic notions in
tropical arithmetics and tropical geometry in §3.1, we first define the
tropical limit of the rectified linear unit (ReLU) in §3.2, and explore the
multilayered feedforward neural networks using this tropical unit in §3.3. We
show that these tropical neural networks have the properties of the universal
approximator as the deep ReLU neural networks. The last section §4 focuses on
the topological realisation of the classification problems via backpropagation
based on the tropical semiring. In §4.1, we first reformulate the
classification problem as a topological problem of exploring the connected
components of the complement of the zero locus of a function approximated by a
neural network. Finally, we introduce the tropicalization of the
backpropagation algorithm in §4.2, that essentially approximates the original
classification problem. We conclude that, while we achieve an algorithm which
approximates the original problem with less algorithmic complexity, it does
not require substantial recoding, only the replacement of linear algebra
packages with their tropical versions.

###  1.1 Short history of this note and its current state

This note essentially summarises the results presented by the author at
Séminaire "Fables Géométriques" in University of Geneva on December 9,
2016.111 unige.ch/math/tggroup/doku.php?id=fables . The version at hand has
been submitted for publication in 2017. Since the completion of this note,
tropical neural networks started to attract considerable attention and there
has been a number of publications appeared. For instance, Tropical geometry of
neural networks appeared in ICML 2018 by Zhang et al was not available to the
author when this paper is written. This note is kept as it was initially
submitted and no new results has been incorporated.

##  2 Algorithmic complexity of backpropagation

###  2.1 Backpropagation in a nutshell

Assume we have a multi-layered neural network with the weight matrix
$\mathbf{W}^{(k)}=\left[w^{(k)}_{ij}\right]$ connecting the layers $k-1$ and
$k$. The backpropagation algorithm aims at minimising a predetermined error
function $E$ by using an iterative process of gradient descent. In this
algorithm, one calculates the gradient matrix

$(\nabla E)^{(k)}=\left[\frac{\partial E}{\partial
w^{(k)}_{ij}}\right],k=0,\dots,l$

for training data, and adjusts the weight matrix $\mathbf{W}^{(k)}$ by adding
a correction term $\Delta\mathbf{W}^{(k)}=-\epsilon\nabla^{(k)}E$ in order to
minimise the error function iteratively. The backpropagated error on the
$k$-th layer is computed via an iterative matrix multiplication

$\Delta\mathbf{W}^{(k)}=\mathbf{D}^{(k)}\mathbf{W}^{(k+1)}\cdots\mathbf{D}^{(l)}\mathbf{W}^{(l+1)}\mathbf{e}$
(1)

where for each layer $k$, the matrix $\mathbf{D}^{(k)}$ is the diagonal matrix
composed of the derivatives of the activation function with respect to its
arguments, and the vector $\mathbf{e}$ contains the derivatives of the output
errors with respect to the arguments of the last layer. For details, see for
instance [Ro96, §7.3.3] or [DBBNG, §6.5].

###  2.2 The sources of algorithmic complexity

The algorithmic complexity of the backpropagation algorithm as presented in
(1) has essentially two layers:

  1. (i)

The complexity of calculating the matrix product.

  2. (ii)

The complexity of the arithmetic operations involved in each step of the
matrix multiplications.

As we mentioned in the introduction, one can design smaller and more robust
neural networks performing the same task, but we would need different pruning
techniques. For various network pruning techniques, see for example [HMD15,
LKDSG, TF97, YCS16]. The ordinary multiplication algorithm of matrices of size
$n\times m$ and $m\times p$ has the algorithmic complexity of $O(nmp)$. Any
simplification in the structure of the network is going to decrease the
algorithmic complexity as the sizes of the resulting matrices will decrease.
Even though there are matrix multiplication algorithms with better asymptotic
complexities (see for instance [Ga12]), they are generally impractical due to
the large constant factors in their running times. It is also not very clear
whether these improved matrix multiplications algorithms are well-suited to
the GPU’s.

In this note, we propose to focus on the more subtle source of the complexity
(ii): the arithmetic operations. In algebraic terms, we propose replacing the
base field of real numbers and corresponding arithmetic operations with the
_tropical semiring of reals_ with its own simpler arithmetic operations. Since
we only swap the field of real numbers with the tropical ring of real numbers,
we note that any reduction on the algorithmic complexity of arithmetic
operations would not require any structural changes in the backpropagation
algorithm. We discuss these aspects in §4.2. Thus, such a swap requires
minimal adaptation in the existing code bases, i.e., swapping the classical
linear package with a tropical linear algebra package.

###### Remark 2.2.1

Approximation of activation function is also notable source of computational
complexity as it plays a role in (1) as entries of the matrices
$\mathbf{D}^{(k)}$. Most of the activation functions are intentionally non-
linear, and their evaluations require certain precision. However,
tropicalisation of activation functions and especially their approximations
are computationally less complex as they are realised in terms of piecewise
linear functions, see §3.2 below.

###  2.3 Complexities of $\min$/$\max$, addition and multiplication

There are substantial differences in (time) complexities of different the
elementary binary operations. The amount of the operations to sum two $n$-bits
numbers via schoolbook addition algorithm is $O(n)$. Similarly, the upper
bound of the number operations to decide the maximum (or the minimum) of the
two $n$-bits numbers is similarly $O(n)$. More importantly, the average-case
complexity of $\max$ (and $\min)$ is $O(1)$.

By contrast, the schoolbook multiplication for the same size is $O(n^{2})$.
While there are other multiplication algorithms with better algorithmic
complexity, such as the Karatsuba algorithm of order $O(n^{\log_{2}(3)})$
[Ka95], they all have the complexity of $O(n^{\lambda})$ with $\lambda>1$. It
is important to note that these lower algorithmic complexities are achieved
asymptotically in most cases, and they are usually effectively implement for
integers. Moreover, one may argue that the Kolmogorov complexities of these
_asymptotically better_ algorithms are not better as they are significantly
difficult to implement.

###  2.4 Execution time and energy consumption

The actual execution time of a specific code depends on numerous factors such
as the processor speed, the instruction set, disk speed, and the compiler
used. An old rule of thumb in designing numerical experiments that dictates
avoiding multiplications and divisions in simulations in favor of additions
and subtractions in order to improve the actual execution time may
heuristically seem redundant on modern processors as they closed the time-
cost-gap between addition and multiplication drastically. However, one can
still say the following on the algorithmic complexity of arithmetic
operations:

  * -

Integer sums and $max/min$ take the same amount of time;

  * -

Floating-point operations are slower than integer operations of the same size;

  * -

Floating-point multiplications are slower than the sums. 222See for instance,
http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/ and
https://lemire.me/blog/2010/07/19/is-multiplication-slower-than-addition/

The energy consumption does not favour the multiplications over the summations
either: the required energy for multiplication is always considerably higher
than the summation [Hor14, pg. 32]. Even if we disregard the complexities in
CPU designs, both execution time and energy consumption criteria suggest that
the reduction of algorithmic complexity by eliminating the multiplications as
much as possible provide considerable benefits.

##  3 Tropical arithmetics and tropical neural networks

In this section, we introduce the basic notions in tropical arithmetics and
tropical geometry, then use them to introduce the tropical neural networks as
universal approximators.

###  3.1 Tropical semiring: Arithmetic without multiplication

The _tropical semiring_ is the limit $\hbar\to+\infty$ of the family
$S_{\hbar}:=(\mathbb{T},\oplus_{\hbar},\otimes_{\hbar})$ where
$\mathbb{T}:=\mathbb{R}\cup\\{-\infty\\}$ with the following arithmetic
operations; for $a,b\in\mathbb{T}$,

$\displaystyle a\oplus_{\hbar}b$
$\displaystyle:=\begin{cases}\log_{\hbar}(\hbar^{a}+\hbar^{b})&\text{ when
}\hbar\in(e,+\infty)\\\ \max\\{a,b\\}&\text{ when }\hbar\to+\infty\end{cases}$
(2) $\displaystyle a\otimes_{\hbar}b$
$\displaystyle:=\log_{\hbar}(\hbar^{a}\cdot\hbar^{b})=a+b.$ (3)

$S_{\hbar}$ form a semiring (a ring without additive inverses) and admit the
semiring isomorphism

$D_{\hbar}:(\mathbb{T},\times,+)\to S_{\hbar}$

for any finite value of $\hbar$, see [IMS, Vi01].333The parameter $\hbar$ is
not just the reminiscent of Planck constant. The tropical limit
$\hbar\to\infty$ is essentially the quasi-classical (i.e., zero temperature)
limit of a certain model in quantum mechanics.

The family $S_{\hbar}$ in (2) relates the ordinary addition and multiplication
operations on the set of real numbers with the tropical arithmetic in the
limit. This limiting process is also called the _Maslov dequantization_ [IMS,
Vi01]. The tropical limit $S_{\infty}$ admits a tropical division, however,
the subtraction is impossible due to the idempotency of $\oplus_{\hbar}$, i.e.
$x\oplus_{\infty}x=\max\\{x,x\\}=x$. The role of the additive zero is played
by $-\infty$, and the multiplicative unit becomes $0$.

###  3.2 The corner locus

A _tropical polynomial_ is a tropical sum of tropical monomials, therefore, a
polynomial of the form

$P(\mathbf{x})=\sum_{(j_{1},\dots,j_{n})\in
V}a_{j_{1},\dots,j_{n}}x_{1}^{j_{1}}\cdots x_{n}^{j_{n}},\ \text{with}\
\mathbf{x}:=(x_{1},\ldots,x_{n}),$

is evaluated in the following form in the tropical ring

$\displaystyle P^{tr}(\mathbf{x})$ $\displaystyle:=$ $\displaystyle
D_{\infty}(P(\mathbf{x}))=\bigoplus_{V}\left(a_{j_{1},\dots,j_{n}}\otimes_{\infty}x_{1}^{j_{1}}\otimes_{\infty}\cdots\otimes_{\infty}x_{n}^{j_{n}}\right)$
(4) $\displaystyle=$ $\displaystyle\max_{(j_{1},\dots,j_{n})\in
V}\\{a_{j_{1},\dots,j_{n}}+\sum j_{k}x_{k}\\}$

where $V\subset\mathbb{Z}^{n}$ is a finite set of points with non-negative
coordinates and the coefficients $a$’s are tropical numbers.

The _zero set of a tropical polynomial_ $P^{tr}$ is the set of tropical
vectors $\mathbf{x}$ for which either $P^{tr}(\mathbf{x})=-\infty$, or there
exists a pair $i\neq j$ in $V$ such that

$a_{i_{1},\dots,i_{n}}\otimes_{\infty}x_{1}^{i_{1}}\otimes_{\infty}\cdots\otimes_{\infty}x_{n}^{i_{n}}=a_{j_{1},\dots,j_{n}}\otimes_{\infty}x_{1}^{j_{1}}\otimes_{\infty}\cdots\otimes_{\infty}x_{n}^{j_{n}}.$

Therefore, one can picture the tropical zero set as the union of intersections
of hyperplanes defined by the tropical monomials. In other words, the tropical
zero set defined by such a polynomial is given by the corner locus, that is
where the tropical polynomial (4) is not locally affine-linear.

###  3.3  Rectified linear unit and its tropical degeneration

In order to describe the tropical degeneration of the rectified linear unit
(ReLU)

$\sigma(\mathbf{x})=\max\left\\{0,b+\sum_{i=1}^{n}a_{i}x_{i}\right\\}\text{
where }\mathbf{x}=(x_{1},\dots,x_{n})\in\mathbb{R}^{n},$ (5)

we consider the $\log$-$\log$ plot of this activation function as family with
respect to a parameter $\hbar\in[e,\infty)$. The transition to the log paper
corresponds to the change of coordinates:

$v_{\hbar}=\log_{\hbar}(y),\ \ \text{and}\ \ u_{i}=\log_{\hbar}(x_{i})$

Then, we simply obtain

$v_{\hbar}=\log_{\hbar}(\sum_{i=1}^{n}\hbar^{\alpha_{i}}\hbar^{u_{i}}+\hbar^{\beta})$

where $b=\hbar^{\beta}$ and $a_{i}=\hbar^{\alpha_{i}},i=1,\dots,n$. In its
domain, the tropical limit $\hbar\to\infty$ of this $\log$-$\log$ graph of the
function ReLU becomes

$\sigma^{tr}:=\lim_{\hbar\to\infty}v_{\hbar}=\max\\{b,\max_{i=1,\dots,k}\\{a_{i}+x_{i}\\}\\}.$
(6)

In other words, the tropical degeneration of ReLU is another ReLU in an
appropriately defined domain.

###  3.4 Multi-layered neural networks as universal approximators

Multi-layered neural networks are used for approximating an unknown function
described by a sample of points in a large affine space $\mathbb{R}^{n}$
called a _data set_. The theoretical underpinnings of such an approximation
goes as far back as Kolmogorov [Sp64, Cy89, H91]. We know that for a given
bounded, and monotonically-increasing continuous function $\sigma$ and a
compact domain $\Omega\subseteq\mathbb{R}^{n}$, any continuous function
$f\colon\Omega\to\mathbb{R}$ can be approximated by finite linear sums of the
form

$F(x)=\sum_{i=1}^{N}\beta_{i}\ \sigma(b_{i}+\sum_{j=1}^{n}a_{ij}x_{j}).$ (7)

As a result, the neural networks with different activation function such as
the logistic function, $\arctan$, $\tanh$, SoftPlus etc., are often thought as
the universal approximator of continuous functions [Ro96, DBBNG].

We view neural networks as a concrete computational manifestation of this
_Universal Approximation Theorem_ where $\sigma$ plays the role of the
activation function in a neural network. Our focus in this paper is to develop
better computational methods in achieving such approximations.

###  3.5 Approximation via tropical neural networks

The rectified linear unit (ReLU) we defined in (5) also lies in this class of
functions that can be used for approximations of continuous and the piecewise
smooth functions on any compact domain in $\mathbb{R}^{n}$. As we observe in
(6) that ReLU can also be represented by using tropical unit on compact
domains. Thus, we can simply state that the ReLu and the tropical units
$\sigma^{tr}$ in (6) are equivalent from the perspective of aproximation
theory:

###### Proposition 3.5.1

Multilayered feedforward neural networks using tropical unit $\sigma^{tr}$ in
(6) as the activation function can give arbitrarily close approximations for
any continuous and piecewise smooth function on any compact domain in
$\mathbb{R}^{n}$.

For the deep ReLU networks, these approximations work as effectively. For
details see [PV17, Ya16].

##  4 Backpropagation in tropical setting

###  4.1 Reformulating a classification problem as a topological problem

Consider a smooth map $f:\mathbb{R}_{+}^{n}\to\mathbb{R}$ defined over the
cone $\mathbb{R}^{n}_{+}=(0,\infty)^{n}$, and consider the zero locus
$Z_{f}:=\\{x\in\mathbb{R}^{n}\mid f(x)=0\\}$ of $f$. Let us define a map

$F:\mathbb{R}_{+}^{n}\setminus Z_{f}\to H_{0}(\mathbb{R}_{+}^{n}\setminus
Z_{f})$

from the complement of $Z_{f}$ to the set of connected components of
$\mathbb{R}_{+}^{n}\setminus Z_{f}$. The map $F$ simply sends each elements
$x\in\mathbb{R}_{+}^{n}\setminus Z_{f}$ to their homology classes $[x]\in
H_{0}(\mathbb{R}_{+}^{n}\setminus Z_{f})$, i.e. the connected component of
$\mathbb{R}_{+}^{n}\setminus Z_{f}$ containing $x$. For basics of (co)homology
theory, see [BT95].

Now, given an arbitrary finite data set (or a finite set of compact subsets)
$\Omega$ in $\mathbb{R}_{+}^{n}$, we can reformulate a classification problem

$N:\Omega\to\\{1,\cdots k\\}$ (8)

as a problem of finding a smooth map $f$ satisfying the following property:
for $x,y\in\Omega$,

$N(x)=N(y)\iff F(x)=F(y).$

Clearly, this reformulation requires that $\mathbb{R}_{+}^{n}\setminus Z_{f}$
has at least $k$ connected components so that $F$ can realise the same
classification problem (8).

###  4.2 Backpropagation and its tropicalisation

Let $f$ be a function which realises the classification problem in (8), and
let $\\{f_{i}\mid i=0,\dots,\infty\\}$ be a sequence of deep ReLU networks
coming from the backpropagation algorithm in (1)

$\lim_{k\to\infty}f_{k}=f.$

Each function $f_{k}$ is piecewise linear and continuous as they are realised
by multilayered ReLU networks. See Proposition 3.5.1.

The corner locus of each $f_{k}$ is mapped into the corner locus of the
tropical limit $f^{tr}_{k}=\lim_{\hbar\to\infty}f_{k}$. In addition to the
tropical images of these existing corner locus, the tropical limit of $f_{k}$
form additional corner locus which is the tropical limit of the zero locus
$Z_{f_{k}}=\\{f_{k}=0\\}\subset\mathbb{R}^{n}_{+}$ under tropical
degeneration. This new corner locus $Z^{tr}_{f_{k}}$ is the tropical zero set
of $f^{tr}_{k}$ defined by $\lim_{\hbar\to\infty}f_{k}$.

###### Lemma 4.2.1

The zero locus $Z_{f_{k}}$ of $f_{k}$ is homeomorphic to the tropical set
$Z^{tr}_{f_{k}}$.

This statement follows from the fact that the map

$\text{Log}_{\hbar}:\mathbb{R}^{n}_{+}\to\mathbb{R}^{n}:(x_{1},\dots,x_{n})\mapsto(\log_{\hbar}(x_{1}),\dots,\log_{\hbar}(x_{n}))$
(9)

is a diffeomorphism for all $\hbar<\infty$. Then the image
$\text{Log}_{\hbar}(Z_{f_{k}})$ is homeomorphic to $Z_{f_{k}}$ for any finite
$\hbar$. For the tropical limit $\hbar\to\infty$, we use the fact

$\lim_{\hbar\to\infty}\frac{d}{d\hbar}\text{Log}_{\hbar}=0$

to show that $Z^{tr}_{f_{k}}$ is homeomorphic to
$\text{Log}_{\hbar}(Z_{f_{k}})$ for sufficiently large $\hbar$.

We note that this statement is in fact a special case of Viro’s theorem
[Vi06]. Viro observed that tropical degeneration preserves the topology of
real algebraic varieties. He developed a method, known as _Viro patchworking_
, that combinatorially constructs any real algebraic variety with a prescribed
topology. We believe that Viro’s method in its general form can also be
directly used in classification problems in (8).

###### Corollary 4.2.2

The classification $N:\Omega\to\\{1,\cdots k\\}$ in (8) can be realised by the
tropical set

$f^{tr}=\lim_{k\to\infty}f^{tr}_{k}$

as the tropical set that $f^{tr}$ defines is homeomorphic to $Z_{f}$.

Corollary 4.2.2 essentially means that we can simply apply
$\text{Log}_{\hbar}$ (9) to each step of the backpropagation algorithm given
in (1) to define the tropical version of the backpropagation algorithm. This
is done by taking tropical image of each entry of the matrices, and then
replacing the matrix addition and multiplication by their respective tropical
arithmetic operations $\oplus_{\infty}$ and $\otimes_{\infty}$ in (2): Let
$\mathbf{A}=[a_{ij}]$ and $\mathbf{B}=[B_{ij}]$ be $n\times m$ matrices. The
_tropical matrix sum_ , $\mathbf{A}\oplus_{\infty}\mathbf{B}$, is then
obtained by evaluating the tropical sum of the corresponding entries,

$(\mathbf{A}\oplus_{\infty}\mathbf{B})_{ij}:=a_{ij}\oplus_{\infty}b_{ij}=\max\\{a_{ij},b_{ij}\\}.$

The _tropical multiplication $\mathbf{A}\otimes_{\infty}\mathbf{B}$ of two
matrices_ $\mathbf{A}=[a_{ij}]\in\mathbb{R}^{m\times n}$ and
$\mathbf{B}=[b_{ij}]\in\mathbb{R}^{n\times p}$ is the given by the matrix
$\mathbf{C}=[c_{ij}]\in\mathbb{R}^{m\times p}$ with entries

$c_{ij}:=\oplus_{\infty}(a_{ik}\otimes_{\infty}b_{kj})=\max_{k}\\{a_{ik}+b_{kj}\\}.$

By using the error term (1) and tropical linear algebra defined above, we
formulate tropical gradient descent iteration as follows

$\displaystyle\mathbf{W}^{(k)}_{\text{new}}$ $\displaystyle=$
$\displaystyle\mathbf{W}^{(k)}\oplus_{\infty}\Delta\mathbf{W}^{(k)}$ (10)
$\displaystyle=$
$\displaystyle\mathbf{W}^{(k)}\oplus_{\infty}-\epsilon\left(\mathbf{D}^{(k)}\otimes_{\infty}\mathbf{W}^{(k+1)}\otimes_{\infty}\cdots\otimes_{\infty}\mathbf{D}^{(l)}\otimes_{\infty}\mathbf{W}^{(l+1)}\otimes_{\infty}\mathbf{e}\right).$

###### Corollary 4.2.3

The tropical backpropagation algorithm in (10) has a lower algorithmic
complexity relative to the vanilla backpropagation algorithm.

This statement follows from the construction of tropical backpropagation which
simply eliminates the complexities of multiplications.

###### Remark 4.2.4

On a machine with a fixed register size (the number of bits available to
represent a number), the improvements we get by swapping the ring of reals
with the tropical semiring of reals will only effect the _the constant factor_
of the complexity of matrix operations. On a classical machine with 128-bit
registers, the complexity of ordinary multiplication of two $n\times n$
matrices is $O(n^{3})$ with constant factor of $2^{14}$ while the same
multiplication on a tropical machine with the same size registers will take
again $O(n^{3})$ time but with the constant factor of $2^{7}$.

###### Remark 4.2.5

The tropical linear algebra is efficient and lowers the algorithmic complexity
of large matrix operations, and therefore, fits well with the backpropagation
and may be used in other applications. However, there are also serious
limitations as it does not admit matrix inversion due to its idempotent
nature.

##  5 Conclusion

In this note, we defined the tropical limit of the ReLU function which is used
in many neural network models. We also showed that the multilayered
feedforward neural networks using this tropical unit carry the properties of
the universal approximator. With further analysis, we established that the
topology of the zero loci of functions realised by the multilayered neural
networks do not change when their tropical limit is considered. This
observation allowed us to tropicalize the backpropagation algorithm solving
any classification problem. The tropical backpropagation algorithm is simply
obtained from the classical backpropagation algorithm in (1) and replacing the
matrix addition and multiplication with their tropical analogues based on the
tropical arithmetic operations $\oplus_{\infty}$ and $\otimes_{\infty}$ in
(2).

As the tropical backpropagation algorithm works over the tropical semiring, it
comes with a considerably algorithmic advantages with almost no drawback:

  * •

Tropicalization reduces the algorithmic complexity significantly by
eliminating multiplications.

  * •

The performance gain out of tropicalization does not come with a cost of
substantial change in the existing code, since it only requires a swaping an
ordinary linear algebra library with an appropriate tropical linear algebra
library.

#### Acknowledgments

I wish to thank to Grisha Mikhalkin, not only for introducing me to the
tropical geometry over the years, but also for inviting me over to Geneva (in
various occasions) and listening my half baked ideas with Ilia Itenberg
patiently. I also thank to Yiğit Gündüç who introduced me to the concepts of
computational complexity decades earlier.

I am grateful to Atabey Kaygun, for being an unwearying friend and
collaborator. Main idea of this note appeared first during a discussion with
Atabey, and he read and commented on all versions of it, i.e., he is a secret
author of this paper. Saying that, all mistakes are mine, mine only.

## References

  * [BT95] R. Bott, L.W. Tu, Differential Forms in Algebraic Topology. Graduate Texts in Mathematics, Springer, 1995.
  * [Cy89] G. Cybenko, Approximations by superpositions of sigmoidal functions. Mathematics of Control, Signals, and Systems (1989), 2 (4),303–314.
  * [DBBNG] C. Dugas, Y. Bengio, F. Bélisle, C. Nadeau, R. Garcia, Incorporating Second-Order Functional Knowledge for Better Option Pricing. Advances in Neural Information Processing Systems 13, MIT Press, 2001, 472–478.
  * [HMD15] S. Han, H. Mao, W.J. Dally, Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. https://arxiv.org/abs/1510.00149
  * [H91] K. Hornik, Approximation Capabilities of Multilayer Feedforward Networks. Neural Networks, 4(2) (1991), 251–257.
  * [Hor14] M. Horowitz, 1.1 computing’s energy problem (and what we can do about it). Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2014.
  * [IMS] I. Itenberg, G. Mikhalkin, E.I. Shustin, Tropical Algebraic Geometry. Oberwolfach Series Birkhäuser; 2 edition (2009).
  * [Ka95] A.A. Karatsuba, The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics. 211 (1995): 16–183.
  * [LLPS] M. Leshno, V.Ya. Lin, A. Pinkus, S. Schocken, Multilayer Feedforward Networks With a Nonpolynomial Activation Function Can Approximate Any Function. Neural Networks, Vol. 6, pp. 861–867, 1993.
  * [Ga12] F. Le Gall, Faster algorithms for rectangular matrix multiplication, Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 514–523.
  * [LKDSG] H. Li, A. Kadav, I. Durdanovic, H. Samet, H.P. Graf, Pruning Filters for Efficient ConvNets. https://arxiv.org/abs/1608.08710
  * [PV17] P. Petersen, F. Voigtlaender, Optimal approximation of piecewise smooth functions using deep ReLU neural networks. https://arxiv.org/abs/1709.05289v3
  * [Ro96] R. Rojas, Neural Networks: A Systematic Introduction. Springer, 1996.
  * [Ru16] S. Ruder, An overview of gradient descent optimization algorithms. https://arxiv.org/pdf/1609.04747.pdf.
  * [Sp64] D. Sprecher, On the Structure of Continuous Functions of Several Variables, Transactions of the American Mathematical Society, Vol. 115 (1964), pp. 340–355.
  * [TF97] G. Thimm, E. Fissler, Pruning of neural networks. http://publications.idiap.ch/downloads/reports/1997/rr97-03.pdf
  * [Vi06] O. Viro, Patchworking Real Algebraic Varieties. https://arxiv.org/pdf/math/0611382.pdf
  * [Vi01] O. Viro, Dequantization of Real Algebraic Geometry on a Logarithmic Paper. Proceedings of the 3rd European Congress of Mathematicians, Birkhäuser, Progress in Math, 201, (2001), 135–146.
  * [Ya16] D. Yarotsky, Error bounds for approximations with deep ReLU networks. https://arxiv.org/abs/1610.01145
  * [YCS16] T.J. Yang, Y.H. Chen, V. Sze, Designing Energy-Efficient Convolutional Neural Networks using Energy-Aware Pruning. https://arxiv.org/abs/1611.05128