# Sharp bounds for the number of regions of maxout networks
and vertices of Minkowski sums

Guido Montúfar Department of Mathematics and Department of Statistics, UCLA,
Los Angeles, CA 90095, USA; Max Planck Institute for Mathematics in the
Sciences, 04103 Leipzig, Germany (montufar@math.ucla.edu). Yue Ren Department
of Mathematics, Swansea University, Swansea SA1 8EN, United Kingdom
(yue.ren@swansea.ac.uk). Leon Zhang Department of Mathematics, UC Berkeley,
Berkeley, CA 94720, USA (leonyz@berkeley.edu).

###### Abstract

We present results on the number of linear regions of the functions that can
be represented by artificial feedforward neural networks with maxout units. A
rank-$k$ maxout unit is a function computing the maximum of $k$ linear
functions. For networks with a single layer of maxout units, the linear
regions correspond to the upper vertices of a Minkowski sum of polytopes. We
obtain face counting formulas in terms of the intersection posets of tropical
hypersurfaces or the number of upper faces of partial Minkowski sums, along
with explicit sharp upper bounds for the number of regions for any input
dimension, any number of units, and any ranks, in the cases with and without
biases. Based on these results we also obtain asymptotically sharp upper
bounds for networks with multiple layers.
_Keywords:_ linear regions of neural networks, upper bound theorem for
Minkowski sums, hyperplane arrangement, tropical hypersurface arrangement,
Newton polytope.
_MSC2020:_ 68T07, 52B05, 14T15, 06A07.

##  1 Introduction

Artificial feedforward neural networks are parametric sets of functions given
as fixed compositions of units, i.e. elementary functions consisting of a
parametrized affine map followed by a fixed activation function. They are
extremely useful as sets of hypothesis functions in contemporary machine
learning applications. We are interested in the geometry and combinatorics of
the functions represented by networks with maxout units, which have an
activation function of the form
$\mathbb{R}^{k}\to\mathbb{R};\;(z_{1},\ldots,z_{k})\mapsto\max\\{z_{1},\ldots,z_{k}\\}$.
Maxout units were proposed in [14] generalizing the popular rectified linear
units (ReLUs) [13], which have activation function
$\mathbb{R}\to\mathbb{R};\;z\mapsto\max\\{0,z\\}$. The corresponding functions
are piecewise (affine) linear and induce subdivisions of the input space into
linear regions. We will be concerned with estimating the maximum number of
linear regions of the functions that can be represented by maxout networks
with given architectures.

The analysis of neural networks with piecewise linear activation functions
based on the number of linear regions of the represented functions was
proposed in [37, 35], showing that deep networks can represent functions which
have many more linear regions than any of the functions that can be
represented by shallow networks with the same number of units or the same
number of parameters. These kind of results illustrate the differences in
representational power and possible benefits of different network
architectures. Works in this direction include [47, 48, 12, 49, 54, 33, 38]
and earlier works for Boolean circuits and sum-product networks [21, 22, 11].
The number of linear regions of the functions represented by networks with
piecewise linear activations has sparked substantial interest in the study of
neural networks, with works including [35, 49, 34, 5, 42, 24]. Recent works
have explored approaches based on tropical geometry [57, 10, 3] and power
diagram subdivisions [6], while others have studied the expectated number of
linear regions for typical choices of the parameters in the case of ReLU
networks [19, 20], empirical enumeration [41], and the relations between
linear regions and the behavior of algorithms that are used to select the
parameters of neural networks based on data, such as speed of convergence and
implicit biases of gradient descent [46, 58, 27].

ReLU networks have been studied in much more detail than maxout networks. And
while ReLUs are currently more popular in applications, maxout networks are an
interesting generalization that enjoy similar benefits (e.g. linear operation,
no saturation) but without some of the possible drawbacks (e.g. dying
neurons). In this work we seek to advance the theory for maxout networks,
particularly in regards to their representational power, whereupon we develop
important connections to topics in combinatorial geometry and tropical
geometry.

The nonlinear locus of a ReLU $x\mapsto\max\\{0,z(x)\\}$ with a generic affine
function $z$ is a hyperplane. Hence, linear regions of functions
$x\mapsto[\max\\{0,z_{1}(x)\\},\ldots,\max\\{0,z_{m}(x)\\}]^{\top}$
represented by a layer of $m$ ReLUs are described by hyperplane arrangements.
Hyperplane arrangements have been investigated since the 19th century [45]. In
particular, Buck [9] showed that the number of regions and bounded regions
that can be obtained by slicing $n$-dimensional Euclidean space with $m$
hyperplanes is $\sum_{j=0}^{n}{m\choose j}$ and ${m-1\choose n}$,
respectively. Moreover, a celebrated result by Zaslavsky [55] gives a formula
for the number of faces and bounded faces of hyperplane arrangements based on
the poset of intersections. For a discussion of these results and other
properties of hyperplane arrangements see [44].

For maxout units one obtains a more general type of arrangement. Concretely, a
rank-$k$ maxout unit $x\mapsto\max\\{z_{1}(x),\ldots,z_{k}(x)\\}$ with generic
affine functions $z_{1},\ldots,z_{k}$ has a nonlinear locus of the form
$\\{x\in\mathbb{R}^{n}\colon
z_{i}(x)=z_{j}(x)=\max\\{z_{1}(x),\ldots,z_{k}(x)\\}\allowbreak\text{ for some
$i\neq j$}\\}$. In tropical geometry this is known as a tropical hypersurface
[32]. Hence the linear regions of the functions
$x\mapsto[\max\\{z_{11}(x),\ldots,z_{1k_{1}}(x)\\},\ldots,\max\\{z_{m1}(x),\ldots,z_{mk_{m}}(x)\\}]^{\top}$
represented by a layer of $m$ maxout units of ranks $k_{1},\ldots,k_{m}$ are
described by arrangements of tropical hypersurfaces. We will also refer to
these as maxout arrangements. The properties of such arrangements are not as
well understood, except in special cases, such as tropical hyperplane
arrangements [43, 4, 26], which correspond to networks with restricted
parameters, namely maxout networks whose affine maps are coordinate
projections plus constants, $z_{ij}(x)=x_{j}+b_{ij}$.

In order to obtain counting formulas and bounds for maxout networks, we will
exploit a correspondence between the regions of maxout arrangements and the
upper vertices of Minkowski sums of polytopes (Proposition 2.7). In the
special case of hyperplane arrangements (rank-$2$ maxout units), these reduce
to Minkowski sums of line segments, called zonotopes [59]. Minkowski sums of
polytopes are of relevance in numerous topics, including computational
commutative algebra, collision detection, robot motion planning, computer-
aided design, and have been the subject of an intensive research program over
the years. In particular, the work of Gritzmann and Sturmfels [16] showed that
for sums of polytopes with at most $r$ total nonparallel edges, the maximum
number of faces is attained by sums of $r$ line segments in general position.
Tight expressions for the maximum number of faces of Minkowski sums of two and
three full-dimensional polytopes were derived in [31, 30]. Relevant to our
discussion, Weibel [52] obtained an expression for the number of faces of
large Minkowski sums of full-dimensional polytopes in terms of the number of
faces of small subsums, and tight upper bounds for the total number of
vertices. Obtaining similar results for sums of polytopes of arbitrary
dimensions requires significantly more complex arguments. A full solution to
the so-called upper bound problem for Minkowski sums (UBPM) was obtained by
Adiprasito and Sanyal [2], giving tight upper bounds (in non-closed form) for
the number of faces of any dimension, of Minkowski sums of any polytopes with
given numbers of vertices.

We shall take Zaslavsky’s perspective (Theorem 5.5) to extend Weibel’s result
to the case of sums of polytopes of arbitrary dimensions (Theorem 6.3),
including the treatment of upper vertices (Theorem 6.2) and bounds on the
number of strict lower vertices (Theorem 6.9). Combining these with an
implication of Adiprasito-Sanyal’s result (Proposition 2.8), we obtain
explicit tight upper bounds for the total number of vertices and for the
number of upper vertices. Our results for Minkowski sums of polytopes
translate to tight upper bounds on the number of linear regions of the
functions represented by shallow maxout networks without and with biases
(Theorem 3.6). These are the first tight results for maxout networks (except
for the rank-$2$ case), closing significant gaps between the upper and lower
bounds from previous works [35]. Based on these results, we also derive
results for deep maxout networks (Theorem 3.12) improving previous lower and
upper bounds [35, 42].

This article is organized as follows. In Section 2 we provide definitions and
different perspectives on maxout networks and their linear regions. In Section
3 we present our main results on the maximum number of linear regions of
maxout networks. The main analysis is conducted in Sections 4, 5, and 6. In
Section 4 we present a modification of a result by Weibel to count the upper
faces of Minkowski sums. In Section 5 we present a modification of a result by
Zaslavski to count the faces of maxout arrangements. In Section 6 we combine
these two approaches to obtain a generalization of Weibel’s result to sums of
polytopes of arbitrary dimensions. In Section 7 we offer a discussion and
outlook.

##  2 Definitions and different perspectives

###  2.1 Maxout networks

We consider standard feedforward fully connected maxout networks with no skip
connections, called maxout networks for short. Maxout networks were introduced
in [14] as a generalization of ReLU networks.

######  Definition 2.1 (Maxout networks).

  1. 1.

Let $k,n\in\mathbb{N}$. A rank-$k$ maxout unit with $n$ inputs is a parametric
function

$\mathbb{R}^{n}\to\mathbb{R};\quad x\mapsto\max\\{\langle
A_{1},x\rangle+b_{1},\ldots,\langle A_{k},x\rangle+b_{k}\\},$

parametrized by $\theta=(A_{r},b_{r})_{r=1}^{k}$, $A_{r}\in\mathbb{R}^{n}$,
$b_{r}\in\mathbb{R}$, $r=1,\ldots,k$. Each affine function is called a pre-
activation feature. The parameters $A_{r}$ and $b_{r}$ are called weights and
biases.

  2. 2.

Let $m\in\mathbb{N}$ and $k_{1},\ldots,k_{m}\in\mathbb{N}$. A layer with $n$
inputs and $m$ maxout output units of ranks $k_{1},\ldots,k_{m}$ is a
parametric function $\mathbb{R}^{n}\to\mathbb{R}^{m}$, whose $j$th output
coordinate is a maxout unit of rank $k_{j}$, $j=1,\ldots,m$. A layer of maxout
units is also called a shallow maxout network.

  3. 3.

Let $L\in\mathbb{N}$ and $n_{0},n_{1},\ldots,n_{L}\in\mathbb{N}$. A maxout
network with $n_{0}$ inputs and $L$ layers of widths $n_{1},\ldots,n_{L}$ is a
parametric function $\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{L}}$ of the form
$f_{L}\circ\cdots\circ f_{1}$, where $f_{l}$ is a function represented by a
layer with $n_{l-1}$ inputs and $n_{l}$ maxout output units of given ranks,
$l=1,\ldots,L$. A network with multiple layers is called a deep network.

  4. 4.

The architecture of a maxout network as described above is determined by the
number of inputs $n_{0}$, the number of layers $L$, the number of units per
layer $n_{1},\ldots,n_{L}$, and the ranks of the maxout units in each layer
$k_{l,1},\ldots,k_{l,n_{l}}$, $l=1,\ldots,L$. The parameter of the network,
which we will denote by $\theta$, is the collection of weights and biases of
all units. For a given architecture, we denote $\mathcal{N}$ the set of
functions that can be represented by the network for all possible choices of
the parameter.

We will be concerned mostly with the analysis of shallow networks, from which
we will also derive results for deep networks. We will also present results
for networks without biases, in which case the affine functions $\langle
A_{r},x\rangle+b_{r}$ reduce to linear functions $\langle A_{r},x\rangle$.
Notice that each function represented by a maxout network is a composition of
continuous piecewise (affine) linear functions and is itself a continuous
piecewise linear function. When there is no risk of confusion we refer to
affine linear functions simply as linear functions.

######  Definition 2.2 (Linear regions).

Let $f$ be a continuous piecewise linear function with $n_{0}$ inputs. The
nonlinear locus of $f$ is the set $V(f)\subseteq\mathbb{R}^{n_{0}}$ of input
points $x$ at which $\nabla_{x}f$ is discontinuous. A linear region of $f$ is
a maximal connected component of $\mathbb{R}^{n_{0}}\setminus V$. The number
of linear regions of $f$ is denoted $N(f)$. The maximum of the number of
linear regions among all functions $f$ that can be expressed by a network
$\mathcal{N}$ is denoted $N(\mathcal{N})=\max_{f\in\mathcal{N}}N(f)$.

###  2.2 Tropical hypersurfaces

Maxout units can be regarded as tropical polynomials. We give a brief
description of these notions. For more details, please see [28, Chapter 1].

######  Definition 2.3.

Given two real numbers $a$ and $b$, their _tropical sum_ is $a\oplus
b=\max(a,b)$ and their _tropical product_ is $a\odot b=a+b$. A _tropical
(exponential) polynomial_ is a function

$f\colon\mathbb{R}^{n_{0}}\to\mathbb{R};\quad f(x)=c_{1}\odot
x^{\odot\alpha_{1}}\oplus\dots\oplus c_{k}\odot x^{\odot\alpha_{k}},$

where $c_{1},\dots,c_{k}\in\mathbb{R}$, $\alpha_{1},\dots,\alpha_{k}\in$
$\mathbb{R}^{n_{0}}$, and
$x^{\odot\alpha_{1}}=\alpha_{1}x_{1}+\dots\alpha_{n_{0}}x_{n_{0}}$. We refer
to the $c_{i}\odot x^{\odot\alpha_{i}}$ as _tropical monomials_ and call $f$ a
_tropical $k$-nomial_ if it is the sum of $k$ distinct monomials.

Classically, polynomials (tropical or non-tropical) only have non-negative
integer exponents. However, this restriction is not needed in our discussion.
A rank-$k$ maxout unit is equivalent to a tropical $k$-nomial.

######  Definition 2.4.

The tropical hypersurface of a tropical polynomial
$f:\mathbb{R}^{n_{0}}\to\mathbb{R}$ is

$\operatorname{Trop}(f):=\\{x\in\mathbb{R}^{n_{0}}:c_{i}x^{\alpha_{i}}=c_{j}x^{\alpha_{j}}=f(x)\text{
for }i\neq j\text{ two distinct monomials}\\}.$

The complement $\mathbb{R}^{n_{0}}\backslash\operatorname{Trop}(f)$ is a union
of convex polyhedral cells on which the function $f$ is linear. In particular,
the nonlinear locus of a maxout unit is a tropical hypersurface.

From the tropical perspective, the goal of the paper is to answer a question
in tropical combinatorics, namely to bound the number of regions of an
arrangement of tropical hypersurfaces. Similar questions on the combinatorics
of tropical hypersurface arrangements have been studied before. However, they
often focus on polynomials of bounded degree, e.g. degree $1$ [4, 26] or
degree $d$ [29], rather than a bounded number of monomials. The bounds are
important for the complexity of many algorithms in tropical geometry, which
often rely on a enumeration of cells in a tropical arrangement or tropical
variety.

###  2.3 Convex conjugates and Newton polytopes

We relate the regions of a maxout network and the vertices of certain
polytopes. The procedure has been explained in [57] from a tropical geometry
perspective. We give a brief description that relies only on convex duality.
For an introduction to convex analysis see [39].

Any continuous piecewise linear function can be expressed as the difference of
two convex piecewise linear functions; see [51]. Hence any function
$f\colon\mathbb{R}^{n}\to\mathbb{R}^{o}$ expressed by a maxout network can be
written, for each output coordinate $i=1,\ldots,o$, as the difference
$f_{i}=g_{i}-h_{i}$ of two piecewise linear convex functions $g_{i}$ and
$h_{i}$. Given such a decomposition, we define a surrogate function
$\bar{f}=g+h\colon\mathbb{R}^{n}\to\mathbb{R}$, where $g=\sum_{i=1}^{o}g_{i}$
and $h=\sum_{i=1}^{o}h_{i}$ are convex. This is a piecewise linear convex
function and hence it can be written as

$\bar{f}(x)=\max_{j=1,\ldots,M}\\{\langle a_{j},x\rangle+b_{j}\\},\quad
x\in\mathbb{R}^{n},$ (1)

for a finite collection of coefficients $a_{j}\in\mathbb{R}^{n}$,
$b_{j}\in\mathbb{R}$, $j=1,\ldots,M$. We will discuss the coefficients in more
detail further below.

Now, any linear region of $f$ is a union of linear regions of $\bar{f}$, or in
other words $f$ is linear on all linear regions of $\bar{f}$: Let $R$ be a
linear region of $\bar{f}$. Assume w.l.o.g. that $\bar{f}$ is constant $0$ on
$R$, i.e., $\bar{f}|_{R}=g|_{R}+h|_{R}=0$. This implies that $g|_{R}=-h|_{R}$,
which means that $g$ and $h$ are both convex and concave on $R$. Therefore,
they must be linear on $R$ and so must be $f$.

Moreover, any two distinct linear regions $R,Q\subseteq\mathbb{R}^{n}$ of
$\bar{f}$ are also distinct linear regions of $f$ unless $\nabla g|_{R}-\nabla
g|_{Q}=\nabla h|_{R}-\nabla h|_{Q}$, a tie which is broken, for instance,
whenever $g$ is scaled independently of $h$. One can show that for generic
choices of the network parameters $f$ and $\bar{f}$ actually have the same
number of linear regions.

Each linear region of $\bar{f}$ corresponds to a (full dimensional)
neighborhood of inputs $x$ over which one of the affine functions $\langle
a_{j},x\rangle+b_{j}$ attains the maximum. A representation of $\bar{f}$ as in
(1) may involve many redundant affine functions. One way to characterize the
affine functions which attain the maximum over a neighborhood of the input
space is as follows. Consider the convex conjugate of $\bar{f}$, which is the
convex piecewise linear function

${\bar{f}}^{\ast}(x^{\ast})=\sup_{x\in\mathbb{R}^{n}}\\{\langle
x,x^{\ast}\rangle-\bar{f}(x)\\},\quad x^{\ast}\in\mathbb{R}^{n}.$

If $\bar{f}(x)=\langle a,x\rangle+b$ for some $x\in\mathbb{R}^{n}$ and
$(a,b)\in\mathbb{R}^{n+1}$, then
$(x^{\ast},{\bar{f}}^{\ast}(x^{\ast}))=(a,-b)$. We conclude that the graph of
${\bar{f}}^{\ast}$ is the convex envelope of the points
$\\{(a_{j},-b_{j})\\}\subseteq\mathbb{R}^{n+1}$. The vertices of this envelope
correspond to the affine functions $\langle a_{j},x\rangle+b_{j}$ which attain
the maximum over a neighborhood of the input space. An equivalent way of
expressing this is as follows.

######  Definition 2.5 (Lifted Newton polytope).

For a function $\bar{f}(x)=\max_{j=1,\ldots,M}\\{\langle
a_{j},x\rangle+b_{j}\\}$, $x\in\mathbb{R}^{n}$, define its Newton polytope as
$\operatorname{conv}\\{a_{j}\colon j=1,\ldots,M\\}\subseteq\mathbb{R}^{n}$,
and its lifted Newton polytope as
$P_{\bar{f}}=\operatorname{conv}\\{(a_{j},b_{j})\colon
j=1,\ldots,M\\}\subseteq\mathbb{R}^{n+1}$.

The upper vertices of a polytope $P\subseteq\mathbb{R}^{n+1}$ are the vertices
$p$ which are ‘visible from above’, meaning that their normal cones
$\\{r\in\mathbb{R}^{n+1}\colon\langle r,p-q\rangle>0\text{ for all }q\in
P\setminus p\\}$ intersect the upper halfspace
$\mathbb{R}^{n}\times\mathbb{R}_{>0}$.

######  Proposition 2.6 ([28, Theorem 1.13]).

The linear regions of $\bar{f}(x)=\max_{j\in\\{1,\ldots,M\\}}\\{\langle
a_{j},x\rangle+b_{j}\\}$, $x\in\mathbb{R}^{n}$, correspond to the upper
vertices of its lifted Newton polytope $P_{\bar{f}}$.

The duality between faces of the nonlinear locus and faces of the lifted
Newton polytope goes beyond what is described in Proposition 2.6, and it is
fundamental for studying the combinatorics of tropical hypersurfaces.

###  2.4 Minkowski sums

The lifted Newton polytopes for single layer networks have a description as
Minkowski sums. Recall that the Minkowski sum of two sets $A$ and $B$ is
defined as $A+B=\\{a+b\colon a\in A,b\in B\\}$. For a single layer of $m$
maxout units of ranks $k_{1},\ldots,k_{m}$,

$\bar{f}(x)\\!=\\!\sum_{j\in[m]}\max_{r_{j}\in[k_{j}]}\\{\langle
w_{j,r_{j}},x\rangle+b_{j,r_{j}}\\}\\!=\\!\max_{r\in[k_{1}]\times\cdots\times[k_{m}]}\Big{\\{}\sum_{j\in[m]}\langle
w_{j,r_{j}},x\rangle+b_{j,r_{j}}\Big{\\}}\\!=\\!\max_{r}\\{\langle
w_{r},x\rangle+b_{r}\\},$

where $[k]:=\\{1,\ldots,k\\}$, and $w_{r}=\sum_{j\in[m]}w_{j,r_{j}}$,
$b_{r}=\sum_{j\in[m]}b_{j,r_{j}}$, for $r\in[k_{1}]\times\cdots\times[k_{m}]$.
To see this one may use that the distributive law holds for tropical addition
and multiplication [32, Section 1.1]. Notice that the resulting set of
coefficients is the Minkowski sum of the sets of coefficients of the
individual units, $\\{(w_{r},b_{r})\colon
r\in[k_{1}]\times\dots\times[k_{m}]\\}=\sum_{j\in[m]}\\{(w_{j,r_{j}},b_{j,r_{j}})\colon
r_{j}\in[k_{j}]\\}$. Now consider the lifted Newton polytope of the layer and
the polytopes of the individual units,
$P_{[m]}=\operatorname{conv}\left\\{(w_{r},b_{r})\colon
r\in[k_{1}]\times\dots\times[k_{m}]\right\\}$,
$P_{j}=\operatorname{conv}\left\\{(w_{j,r_{j}},b_{j,r_{j}})\colon
r_{j}\in[k_{j}]\right\\},\;j\in[m]$. Since the Minkowski sum of convex sets is
convex, we have

$P_{[m]}=\sum_{j\in[m]}P_{j}.$

In turn, the polytope for a layer is obtained by taking the Minkowski sum of
the polytopes of the individual units. This is all we will need in our
discussion. We note that, following the arguments of [57], one can also
describe how the polytopes corresponding to layers are combined to obtain a
polytope for a deep network. That work focused on ReLU networks, but the same
arguments extend naturally to maxout networks.

We collect a few observations in the next proposition. For maxout units of
ranks $k_{1},\ldots,k_{m}$ the polytopes $P_{1},\ldots,P_{m}$ are arbitrary
convex hulls of, respectively, $k_{1},\ldots,k_{m}$ points in
$\mathbb{R}^{n+1}$. For units without biases, the last coordinate of the
coefficients is always zero, so that the polytopes are in
$\mathbb{R}^{n}\times\\{0\\}$ and the upper vertices are simply the vertices.

######  Proposition 2.7.

The linear regions of a function represented by a layer with $n$ inputs and
maxout units of ranks $k_{1},\ldots,k_{m}$ correspond to the upper vertices of
a Minkowski sum of polytopes which are convex hulls of $k_{1},\ldots,k_{m}$
points in $\mathbb{R}^{n+1}$. For a layer without biases, the linear regions
correspond to the vertices of a Minkowski sum of polytopes which are convex
hulls of $k_{1},\ldots,k_{m}$ points in $\mathbb{R}^{n}$.

The difference between counting the vertices vs the upper vertices of
Minkowski sums of polytopes is analogous to the difference between counting
the regions of a central arrangement (without biases) vs counting the regions
of a non-central arrangement (with biases). The nonlinear locus $V(f)$ of a
function $f$ represented by a layer of maxout units without biases is the
normal fan of the Newton polytope. The nonlinear locus of a function with
biases is the intersection of the normal fan of the lifted Newton polytope in
$\mathbb{R}^{n+1}$ and the affine space $\mathbb{R}^{n}\times\\{1\\}$. The
hardest part in our proofs will be to upper bound the number of regions of
non-central arrangements.

A result of particular importance in our analysis is the Upper Bound Theorem
for Minkowski Sums by Adiprasito and Sanyal [2, Theorem 6.11], which shows
that the maximum number of $s$-dimensional faces of Minkowski sums of
polytopes with given numbers of vertices is attained by sums of so-called
Minkowski neighborly families. From their result we derive the following
proposition, which we will later use to obtain an explicit form of the upper
bound for vertices. It will also be an ingredient in our upper bound for upper
vertices. For a polytope $P$, let $f_{s}(P)$ denote the number of
$s$-dimensional faces of $P$.

######  Proposition 2.8.

Let $0\leq s\leq n$. If a Minkowski sum of polytopes
$P=P_{1}+\cdots+P_{m}\subseteq\mathbb{R}^{n+1}$ has the maximum number of
$s$-faces among all sums with given $f_{0}(P_{1}),\ldots,f_{0}(P_{m})$, then
$f_{0}(\sum_{i\in S}P_{i})=\prod_{i\in S}f_{0}(P_{i})$ for all
$S\subseteq[m]$, $|S|\leq n$.

Intuitively, this proposition states that if a sum of polytopes in
$\mathbb{R}^{n}$ with given vertex counts reaches the largest possible number
of vertices, then each partial sum of at most $n$ of the polytopes reaches a
trivial upper bound on the number of vertices.

###### Proof.

We explain how to derive the claim based on [2]. We refer the reader to that
paper for details on Minkowski neighborly families, Cayley polytopes,
(relative) Cayley complexes, $h$-vectors, and the corresponding Dehn-
Sommerville relations. That paper shows that a Minkowski sum
$P_{1}+\cdots+P_{m}$ of polytopes $P_{i}\subseteq\mathbb{R}^{d}$ attains the
maximum number of $k$-faces, $0\leq k\leq d$, if the family
$(P_{1},\ldots,P_{m})$ is Minkowski neighborly. (Following their notation,
here we use $k$ for the dimension of the faces). Of particular interest is the
classification of cases maximizing the number of faces of a particular
dimension $k_{0}$. Following [2, Theorem 6.11], for a given $k_{0}$, a
Minkowski sum $P_{1}+\cdots+P_{m}$ attains the maximum number of $k_{0}$-faces
if and only if the $h$-vector of its relative Cayley complex attains maximum
value at all entries $h_{k+m-1}$ with $k\leq k_{0}+1$. By the Dehn-Sommerville
relations, the entries with $k+m-1>\lfloor\frac{d+m-1}{2}\rfloor$ are
determined as positive linear functions of the entries with
$k+m-1\leq\lfloor\frac{d+m-1}{2}\rfloor$ of the $h$-vectors for sub-families
$(P_{i})_{i\in U}$, $U\subseteq[m]$. Hence we only need to verify that the
latter entries are maximal. By [2, Theorem 6.11(2a)], this is equivalent to
verifying that for any
$k^{\prime}+m^{\prime}-1\leq\lfloor\frac{d+m^{\prime}-1}{2}\rfloor$ and
$U\subseteq[m]$, $|U|=m^{\prime}$, the following holds. For all $S\subseteq
U$, all nonfaces of the Cayley polytope $T_{S}$ of cardinality
$k^{\prime}+|S|-1$ are supported in some vertex set $V(T_{R})$ with
$R\subsetneq S$. One can rewrite the cases as
$k^{\prime}\leq\lfloor\frac{d+m^{\prime}-1}{2}\rfloor-(m^{\prime}-1)$ and
nonfaces of cardinality $\leq\lfloor\frac{d-(m^{\prime}-1)}{2}\rfloor+|S|-1$.
For $m^{\prime}\geq d$, the condition is trivially satisfied. Hence we only
need to check cases with $m^{\prime}=d-r$, $r\geq 1$, and nonfaces of
cardinality $\leq\lfloor\frac{r+1}{2}\rfloor+|S|-1$, where $|S|\leq d-r$,
$r\geq 1$. This means that for any $S\subseteq[m]$ of cardinality $|S|\leq n$,
any selection of one vertex from each $P_{i}$, $i\in S$, results in a vertex
of the polytope $P_{S}=\sum_{i\in S}P_{i}$, and hence that $P_{S}$ attains the
trivial upper bound on the number of vertices, $f_{0}(P_{S})=\prod_{i\in
S}f_{0}(P_{i})$. ∎

$(0,0,0)$$(2,2,0)$$\max(0,2x+2y)$$(1,0,1)$$(0,1,1)$$(1,1,0)$$\max(x+1,y+1,x+y)$$(2,3,1)$$(3,3,0)$$(1,0,1)$$(1,1,0)$$+$$\cup$$=$$=$not
visible from above Figure 1: Upper vertices of Minkowski sums and regions of
maxout arrangements.

##  3 Number of linear regions for maxout networks

In this section we present our main results on the maximum number of linear
regions of maxout networks. First we provide general observations, then turn
to our main results on shallow networks, and derive implications for deep
networks. For shallow networks, we obtain sharp bounds and provide a
construction that attains them. The main analysis will be conducted in the
upcoming Sections 4, 5, and 6.

###  3.1 General observations

We begin with a simple general upper bound on the number of linear regions of
the functions represented by maxout networks:

######  Proposition 3.1 (Simple upper bound on the number of regions).

For any maxout network $\mathcal{N}$ with a total of $m$ maxout units of ranks
$k_{1},\ldots,k_{m}\in\mathbb{N}$, $N(\mathcal{N})\leq\prod_{j=1}^{m}k_{j}$.

###### Proof.

Let $n_{0}$ be the number of inputs. Let $L$ be the number of layers and
denote their widths $n_{1},\ldots,n_{L}$. Write $k_{l,j}$ for the rank of the
$j$th unit $j=1,\ldots,n_{l}$ in the $l$th layer $l=1,\ldots,L$. Fix the
parameters $A_{l,j,r}\in\mathbb{R}^{n_{l-1}}$, $b_{l,j,r}\in\mathbb{R}$ of all
preactivation features $r=1,\ldots,k_{l,j}$, of all units $j=1,\ldots,n_{l}$,
of all layers $l=1,\ldots,L$. Then, for each input $x$, the represented
function $f$ takes the form
$(\bar{A}_{L}\cdots\bar{A}_{1})x+(\sum_{l=1}^{L}\bar{A}_{L}\cdots\bar{A}_{l+1}\bar{b}_{l})$,
where each $\bar{A}_{l}\colon\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{l}\times
n_{l-1}}$ and $\bar{b}_{l}\colon\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{l}}$ is a
piecewise constant function of $x$ having $j$th row equal to one of the
$k_{l,j}$ values $A_{l,j,1},\ldots,A_{l,j,k_{l,j}}\in\mathbb{R}^{n_{l-1}}$ and
$b_{l,j,1},\ldots,b_{l,j,k_{l,j}}\in\mathbb{R}$, depending on which of the
preactivation features assumes the maximum. The list of preactivation features
that assume the maximum for each unit is called the activation pattern of the
network at the particular input. The set of inputs with a particular
activation pattern is determined by a list of linear inequalities and hence it
is a convex polyhedron. In summary, the input space is split into at most
$\prod_{l=1}^{L}\prod_{i=1}^{n_{l}}k_{l,i}$ connected regions on each of which
$f$ is linear. ∎

The following proposition states that generic perturbations of the parameters
do not decrease the number of linear regions. Here, generic means up to a null
set with respect to the Lebesgue measure in parameter space. This is
important, as later it will allow us to obtain sharp upper bounds by
considering polytopes that are in general orientation.

######  Proposition 3.2 (Generic perturbations of parameters do not decrease
the number of regions).

Consider a network $\mathcal{N}$ consisting of a finite number of maxout
units. Let $f_{\theta}\in\mathcal{N}$. Then there exists an
$\epsilon=\epsilon(\theta)>0$ such that for generic $\theta^{\prime}$ with
$\|\theta^{\prime}-\theta\|<\epsilon$, $N(f_{\theta^{\prime}})\geq
N(f_{\theta})$.

###### Proof.

The intuition is that every linear region of $f_{\theta}$ contains a
neighborhood of an input point $x_{0}$, and small perturbations of the
parameter $\theta$ only cause small changes in the distance between $x_{0}$
and the nonlinear locus $V(f_{\theta})$, so that no linear regions can
‘disappear’ under small perturbations of the network parameters. The formal
argument is based on the correspondence between regions and upper vertices of
the lifted Newton polytope, Proposition 2.6. Consider the function
$f_{\theta}$ represented by the network $\mathcal{N}$ with parameter $\theta$,
and the corresponding convex function $\bar{f}_{\theta}=\max_{j}\\{\langle
a_{j}(\theta),x\rangle+b_{j}(\theta)\\}$ described in (1). The lifted Newton
polytope of $\bar{f}_{\theta}$ is the convex hull of points
$(a_{j}(\theta),b_{j}(\theta))\in\mathbb{R}^{n+1}$ that have a continuous, in
fact polynomial, parametrization in $\theta$. The statement now follows from
the lower semi-continuity of the face numbers of polytopes discussed in [17,
Section 5.3]. More precisely, denote by $\rho$ the Hausdorff metric which is
defined as $\rho(A_{1},A_{2})=\inf\\{\alpha>0\colon A_{1}\subseteq
A_{2}+B_{\alpha},A_{2}\subseteq A_{1}+B_{\alpha}\\}$, where $B_{\alpha}$ is a
radius-$\alpha$ ball around the origin. If $P$ is a bounded polytope, then
there exists an $\epsilon=\epsilon(P)>0$ such that for every $P^{\prime}$ with
$\rho(P^{\prime},P)<\epsilon$ we have $f_{k}(P^{\prime})\geq f_{k}(P)$ for any
$0\leq k\leq n$, where $f_{k}(P)$ is the number of $k$-faces of $P$. The same
statement clearly applies to the upper faces of polytopes, and hence to the
number of linear regions of $\bar{f}_{\theta}$. Since the linear regions of
$f_{\theta}$ and $\bar{f}_{\theta}$ are equal for generic choices of
parameters, the claim follows. ∎

###  3.2 Shallow networks

For shallow maxout networks, [35] obtained the following bounds. The upper
bound is based on embedding a maxout arrangement in a hyperplane arrangement
and using well known upper bounds for that case. We add a minor improvement
which was pointed out in [42] (substituting $k^{2}$ with $k(k-1)/2$).

######  Proposition 3.3 ([35, Proposition 7]).

For a network $\mathcal{N}$ with $n$ inputs and a single layer of $m$ rank-$k$
maxout units, $k^{\min\\{n,m\\}}\leq
N(\mathcal{N})\leq\sum_{j=0}^{n}{mk(k-1)/2\choose j}$.

Notice the significant gap between the lower and upper bounds in Proposition
3.3, of orders $\Omega(k^{n})$ and $O((mk^{2})^{n})$ in $m$ and $k$. The
construction for the lower bound can be generalized and improved, as we show
in the next proposition. In Theorem 3.6 we will show that this lower bound is
optimal.

######  Proposition 3.4 (Lower bound for shallow maxout networks).

For a network $\mathcal{N}$ with $n$ inputs and a single layer of $m$ maxout
units of ranks $k_{1},\ldots,k_{m}$,
$N(\mathcal{N})\geq\sum_{j=0}^{n}\sum_{S\in{[m]\choose j}}\prod_{i\in
S}(k_{i}-1)$. The bound is realized if each of the maxout units has a
nonlinear locus consisting of $k_{i}-1$ distinct parallel hyperplanes and the
normals of different units are in general position.

###### Proof.

We count the number of regions for the special case where each maxout unit has
a nonlinear locus consisting of $k_{i}-1$ parallel hyperplanes,
$i=1,\ldots,m$. This provides a lower bound on the maximum possible number of
regions. Zaslavsky’s theorem [55] states that the number of regions of an
arrangement $\mathcal{A}$ of affine hyperplanes in an $n$-dimensional real
vector space is $r(\mathcal{A})=(-1)^{n}\chi_{\mathcal{A}}(-1)$, where
$\chi_{\mathcal{A}}$ is the characteristic polynomial of $\mathcal{A}$. For
_generic translations of hyperplanes of a linear arrangement_ , Stanley [44,
pg. 22] shows that
$\chi_{\mathcal{A}}(t)=\sum_{\mathcal{B}}(-1)^{|\mathcal{B}|}t^{n-|\mathcal{B}|}$,
where $\mathcal{B}$ ranges over all subsets of hyperplanes in $\mathcal{A}$
with linearly independent normals. Applying these two results to an
arrangement $\mathcal{A}$ in $\mathbb{R}^{n}$ consisting of $m$ sets of
$k_{i}-1$ parallel hyperplanes, $i=1,\ldots,m$, with hyperplanes in different
sets being in general position, we obtain
$\chi_{\mathcal{A}}(t)=\sum_{j=0}^{n}(\sum_{{\smash[b]{S\in{[m]\choose
j}}}}\prod_{i\in S}(k_{i}-1))(-1)^{j}t^{n-j}$ and
$r(\mathcal{A})=(-1)^{n}\chi_{\mathcal{A}}(-1)=\sum_{j=0}^{n}(\sum_{S\in{[m]\choose
j}}\prod_{i\in S}(k_{i}-1))$. ∎

A similar argument can be used to obtain the following lower bound for the
maximum number of regions for functions represented by maxout networks without
biases. In Theorem 3.6 we will show that this lower bound is also optimal.

######  Proposition 3.5 (Lower bound for shallow maxout networks without
biases).

For a network $\mathcal{N}$ with $n$ inputs and a single layer of maxout units
of ranks $k_{1},\ldots,k_{m}$ and no biases, $N(\mathcal{N})\geq{m-1\choose
n-1}+\sum_{j=0}^{n-1}\sum_{S\in{[m]\choose j}}\prod_{i\in S}(k_{i}-1)$.

###### Proof.

Consider $\mathbb{R}^{n}$ and the hyperplane
$H=\\{x^{\prime}\in\mathbb{R}^{n}\colon x^{\prime}_{n}=1\\}$. Any linear
function $x^{\prime}\mapsto\langle w^{\prime},x^{\prime}\rangle$ on
$\mathbb{R}^{n}$ takes over $H$ the form $\langle w,x\rangle+b$, where
$w^{\prime}=(w,b)$ and $x^{\prime}=(x,1)$. Thus, setting the weights of our
layer without biases as $w_{i}^{\prime}=(w_{i},b_{i})\in\mathbb{R}^{n}$, with
$w_{i}\in\mathbb{R}^{n-1}$ the weights and $b_{i}\in\mathbb{R}$ the biases of
Proposition 3.4 for $n-1$ inputs, where $i$ runs over all preactivation
features of all units, we obtain a function whose restriction to $H$ has
$\sum_{j=0}^{n-1}\sum_{S\in{[m]\choose j}}\prod_{i\in S}(k_{i}-1)$ linear
regions. Now we argue that this function can be constructed so that it has
${m-1\choose n-1}$ additional linear regions that are not intersected by $H$.
By our construction, over $H$ the nonlinear locus of the $j$th unit
$\max\\{\langle w_{j,1},x\rangle+b_{j,1},\ldots,\langle
w_{j,k_{j}},x\rangle+b_{j,k_{j}}\\}$ consists of $k_{j}-1$ parallel
hyperplanes, meaning that all $w_{j,1},\ldots,w_{j,k_{j}}$ are equal to some
fixed $w_{j}$ up to scaling. Consider the hyperplane
$G=\\{x^{\prime}\in\mathbb{R}^{n}\colon x^{\prime}_{n}=-1\\}$. Over $G$, any
of the maxout units takes the form $\max\\{\langle\alpha_{1}w_{j},x\rangle-
b_{j,1},\ldots,\langle\alpha_{k_{j}}w_{j},x\rangle-b_{j,k_{j}}\\}$ and its
nonlinear locus includes (actually it consists precisely of) one hyperplane
$\\{x\in\mathbb{R}^{n-1}\colon(\alpha_{r}-\alpha_{s})\langle
w_{j},x\rangle-(b_{j,r}-b_{j,s})\\}$. Hence, over $G$ our layer has linear
regions determined by $m$ affine hyperplanes. Now, an arrangement of $m$
hyperplanes in general position in ${n-1}$ dimensions has ${m-1\choose n-1}$
relatively bounded regions. None of these intersect $H$. ∎

Our main result determines the maximal number of linear regions for shallow
maxout networks with and without bias, for any input dimension, any number of
maxout units, and any ranks. It shows that the lower bounds in Propositions
3.4 and 3.5 are sharp.

######  Theorem 3.6 (Optimal bound for shallow maxout networks).

For a shallow network $\mathcal{N}$ with $n$ inputs and a layer of $m$ maxout
units of ranks $k_{1},\ldots,k_{m}$, we have

$\displaystyle N(\mathcal{N})$
$\displaystyle=\sum_{j=0}^{n}\sum_{S\in{[m]\choose j}}\prod_{i\in
S}(k_{i}-1),$ where ${[m]\choose j}$ is the set of subsets of
$[m]=\\{1,\ldots,m\\}$ with cardinality $j$. Here ${[m]\choose
0}=\\{\emptyset\\}$, empty sums are $0$, and empty products are $1$. In
particular, if $k_{1}=\cdots=k_{m}=k$, we have
$N(\mathcal{N})=\sum_{j=0}^{n}{m\choose j}(k-1)^{j}$. Moreover, if
$\mathcal{N}$ is without biases, then $\displaystyle N(\mathcal{N})$
$\displaystyle={m^{\prime}-1\choose n-1}+\sum_{j=0}^{n-1}\sum_{S\in{[m]\choose
j}}\prod_{i\in S}(k_{i}-1),$

where $m^{\prime}$ is the number of maxout units of rank larger than $1$. In
particular, if $k_{1}=\cdots=k_{m}=k>1$, we have $N(\mathcal{N})={m-1\choose
n-1}+\sum_{j=0}^{n-1}{m\choose j}(k-1)^{j}$.

The proof relies on several results that will be developed in Sections 4, 5,
and 6. The most difficult part is the upper bound for the case with biases and
many units ($m\geq n+1$) possibly having small ranks (allowed to be smaller
than $n+2$), which also happens to be the case of highest practical interest.
The main ideas are as follows.

It is not difficult to adapt a result by Weibel to count upper faces of
Minkowski sums (Theorem 4.10). This provides us with a formula for the number
of linear regions (and other lower-dimensional features) for shallow maxout
networks. However, the formula consists of an alternating sum over sub-
arrangements whose maximum value is difficult to determine when some of the
polytopes are not full dimensional.

Studying whole polytopes instead of their upper faces allows us to leverage
Adiprasito-Sanyal’s Upper Bound Theorem for Minkowski Sums and its
implications for small Minkwoski subsums (Proposition 2.8). To obtain an
explicit formula for the maximum number of overall vertices, we generalize
Weibel’s formula for vertices to encompass possibly lower-dimensional
polytopes (Theorem 6.3) and upper vertices (Theorem 6.2). To this end we
formulate a maxout version of Zaslavsky’s theorem (Theorem 5.5). In order to
differentiate between all vertices and upper vertices, we study bounded
regions of maxout arrangements (Theorem 6.9). In summary, the key results
towards proving Theorem 3.6 are the following:

Propositions 3.4 and 3.5:

constructive lower bounds for the maximum number of linear regions of shallow
maxout networks with and without biases, improving a previous construction by
Montúfar et al. [35].

Proposition 2.8:

a consequence of the Upper Bound Theorem for Minkowski sums by Adiprasito-
Sanyal [2] to the number of vertices of small Minkowski subsums of polytopes
attaining said upper bound.

Theorem 5.5:

a maxout version of Zaslavsky’s theorem for hyperplane arrangements [55],
which expresses the number of regions of a maxout arrangement in terms of the
Euler characteristic and the Möbius function on the intersection poset.

Theorems 6.2 and 6.3:

a generalization of Weibel’s counting formula for Minkowski sums [52], which
expresses the number of regions of simple non-central and central maxout
arrangements in terms of the regions of small subarrangements (Minkowski
subsums).

Theorem 6.9:

a lower bound on the number of bounded regions of a maxout arrangement (strict
lower vertices of a Minkowski sum). This allows us to upper bound the number
of upper vertices of a Minkowski sum, given an upper bound on the total number
of vertices.

###### Proof of Theorem 3.6.

For networks with biases, if $m\leq n$, we can apply the trivial upper bound
given in Proposition 3.1. For $m\geq n+1$, the upper bound follows from the
upper bound theorem for Minkowski sums of polytopes Theorem 2.8 together with
the lower bound on the number of strict upper or lower faces given in Theorem
6.9 inserted into the counting formula given in Theorem 6.2 and reformulated
via Lemma 4.12. The construction attaining the maximum is given in Proposition
3.4. For networks without biases, if $m\leq n$, we can apply the trivial upper
bound given in Proposition 3.1. For $m\geq n+1$, the upper bound follows from
Theorem 2.8 inserted into the counting formula given in Theorem 6.3 and
reformulated via Lemma 4.12. The construction attaining the maximum is given
in Proposition 3.5. ∎

We illustrate Theorem 3.6 on a few examples.

######  Example 3.7.

  1. 1.

In the case of a single input, $n=1$, networks with biases represent functions
on the real line which have at most $\sum_{i=1}^{m}(k_{i}-1)$ break points and
a maximum of $1+\sum_{i=1}^{m}(k_{i}-1)$ linear regions. Networks without
biases and at least one unit of rank $\geq 2$ represent functions which have
at most $1$ break point and a maximum of $2$ linear regions.

  2. 2.

In the case of few units, $m\leq n$, networks with and without biases both
have the optimal bound $\prod_{i=1}^{m}k_{i}$. To see this, use the multi-
binomial theorem to evaluate the formula in our theorem. This matches the
simple upper bound given in Proposition 3.1.

  3. 3.

In the case of many units, $m\geq n$, the maximum number of regions is no
longer exponential in $m$, but only polynomial. For $k_{1}=\cdots=k_{m}=k$,
the order in $m$ and $k$ is $\Theta((mk)^{n})$ and $\Theta((mk)^{n-1})$ in the
cases with and without biases. This should be compared with the previous
bounds $\Omega(k^{n})$ and $O((mk^{2})^{n})$ from Proposition 3.3 for the case
with biases.

  4. 4.

In the case $k_{1}=\cdots=k_{m}=2$, we recover the well-known formulas for the
maximum number of regions of hyperplane arrangements, $\sum_{j=0}^{n}{m\choose
j}$, and central hyperplane arrangements, ${m-1\choose
n-1}+\sum_{j=0}^{n-1}{m\choose j}=2\sum_{j=0}^{n-1}{m-1\choose j}$. These are
also the optimal bounds for shallow ReLU networks with and without biases.

We finish this part with two corollaries. The first gives a lower bound on the
number of bounded regions.

######  Corollary 3.8 (Lower bound on the number of bounded regions).

For a network with $n$ inputs, a layer of $m$ maxout units of ranks at least
$2$, and generic parameters, the number of bounded regions is at least
${m-1\choose n}$. For networks without biases all regions are unbounded.

###### Proof.

This follows from Theorem 6.9. ∎

By Corollary 3.8, generic maxout arrangements with rank at least $2$ have at
least as many bounded regions as generic hyperplane arrangements, which have
${m-1\choose n}$ bounded regions. This observation is non-trivial, since the
polyhedral pieces of tropical hypersurfaces do not necessarily all intersect
each other. It is easy to draw examples in $\mathbb{R}^{2}$ showing that, in
contrast to hyperplane arrangements, maxout arrangements do not have a single
generic number of bounded regions. Lower bounds for generic parameters are
rare in the literature. A result of this kind is [1, Corollary 8.2]
(supplement to [2]), which shows that a Minkowski sum of $m$ polytopes in
general position has at least as many vertices as a sum of $m$ line segments.

The following is a simple corollary for the number of regions over an affine
subspace of the input space, which we will use in the next part on deep
networks.

######  Corollary 3.9 (Number of regions over an affine subspace).

Consider a network $\mathcal{N}$ with $n$ inputs and a layer of $m$ maxout
units. Let $A$ be an affine $n_{0}$-space, $n_{0}\leq n$. Then
$N(\mathcal{N}|_{A})=\sum_{j=0}^{n_{0}}\sum_{S\in{[m]\choose j}}\prod_{i\in
S}(k_{i}-1)$. Similarly, for a network $\mathcal{N}$ without biases and $A$ a
linear $n_{0}$-space, $n_{0}\leq n$, $N(\mathcal{N}|_{A})={m-1\choose
n_{0}-1}+\sum_{j=0}^{n_{0}-1}\sum_{S\in{[m]\choose j}}\prod_{i\in
S}(k_{i}-1)$.

###### Proof.

The functions represented by $\mathcal{N}$ on $A$ can be written as a layer
with $n_{0}$ inputs. ∎

###  3.3 Deep networks

In this subsection we derive consequences of our analysis of shallow networks
for deep networks. For deep maxout networks, [35] obtained the following lower
bound. The main point in that work was to show that the maximum number of
linear regions is exponential in the depth of the network. Upper bounds for
deep networks can be obtained by multiplying upper bounds for individual
layers, whereby the effective input dimension of each layer is bounded by the
dimension of the image of the previous layers [34]. The following upper bound
of this form was given in [42], whereby we correct a minor typo (the sum runs
up to $\min\\{n_{0},\ldots,n_{l-1}\\}$ rather than
$\min\\{n_{0},\ldots,n_{l}\\}$).

######  Proposition 3.10 ([35, Theorem 9] and [42, Theorem 10]).

For a rank-$k$ maxout network $\mathcal{N}$ with $n_{0}$ inputs and $L$ layers
of width $n_{0}$, $N(\mathcal{N})\geq k^{L-1}k^{n_{0}}$. For $L$ layers of
widths $n_{1},\ldots,n_{L}$,
$N(\mathcal{N})\leq\prod_{l=1}^{L}(\sum_{j=0}^{e_{l}}{n_{l}k(k-1)/2\choose
j})$, where $e_{l}=\min\\{n_{0},\ldots,n_{l-1}\\}$.

We observe that there is a significant gap between the lower and upper bounds,
of orders $\Omega(k^{L-1+n_{0}})$ and $O(\prod_{l=1}^{L}(n_{l}k^{2})^{n_{0}})$
in $n_{1},\ldots,n_{L}$ and $k$. We can refine the approach from [35] to
obtain the following lower bound of order
$\Omega(\prod_{l=1}^{L}(n_{l}k)^{n_{0}})$ in $n_{1},\ldots,n_{L}$ and $k$.
This not only grows exponentially with the depth $L$, but also grows with the
layer widths.

######  Proposition 3.11 (Lower bound for deep maxout networks).

Consider a network $\mathcal{N}$ with $n_{0}$ inputs and $L$ layers of
$n_{1},\ldots,n_{L}$ rank-$k$ maxout units. Let $n\leq
n_{0},\frac{1}{2}n_{1},\ldots,\frac{1}{2}n_{L-1}$. Assume $\frac{n_{l}}{n}$ is
even (else take the largest even lower bound and discard the rest). Then
$N(\mathcal{N})\geq(\prod_{l=1}^{L-1}(\frac{n_{l}}{n}(k-1)+1)^{n})(\sum_{j=0}^{n}{n_{L}\choose
j}(k-1)^{j})$. For the same network but without biases, assuming
$\frac{n_{l}-1}{n-1}$ is even,
$N(\mathcal{N})\geq(\prod_{l=1}^{L-1}(\frac{n_{l}-1}{(n-1)}(k-1)+1)^{n-1})(\sum_{j=0}^{n-1}{n_{L}\choose
j}(k-1)^{j})$.

###### Proof.

We follow the general arguments from [35] but modify the construction of the
weights to be similar to the one used in the same paper for ReLU layers. The
idea is to construct a many-to-one function, which allows us to multiply the
regions across layers.

Consider first the case with biases. We consider the restriction of the
network to inputs from a subspace of dimension $n$. Further, we insert a
linear layer of output dimension $n$ after each layer of maxout units. In this
way, the input dimension for each layer is $n$. This does not increase the
representational power of the network, since a linear layer can be subsumed
into the input weights and biases of the next layer, as
$A_{i+1}(B_{i}f_{i}(x)+c_{i})+b_{i+1}=(A_{i+1}B_{i})f_{i}(x)+(A_{i+1}c_{i}+b_{i+1})$.
For each layer $l=1,\ldots,L-1$, we organize the $n_{l}$ units into $n$ groups
of even size $\frac{n_{l}}{n}$. By choosing the parameters of the $i$th group
appropriately, we can achieve that their sum with alternating signs represents
a zig-zag function over $\mathbb{R}^{n}$ with $\frac{n_{l}}{n}(k-1)$
breakpoints along the $i$th coordinate. To see this, note that along any given
direction of its input, a maxout unit can represent any piecewise linear
convex function with $k-1$ break points. This way we can achieve that the
$i$th layer maps $[0,1]^{n}$ to $[0,1]^{n}$ in a
$(\frac{n_{l}}{n}(k-1)+1)^{n}$ to one manner. The function computed up to
layer $L-1$ multiplies these multiplicities. By Proposition 3.4, the last
layer can create $\sum_{j=0}^{n}{n_{L}\choose j}(k-1)^{j}$ regions over the an
$n$-dimensional subspace of its input space, which, by appropriate scaling
will intersect $[0,1]^{n}$. Each of these regions has multiplicity
$\prod_{l=1}^{L-1}(\frac{n_{l}}{n}(k-1)+1)^{n}$ over the input space of the
network, thus giving the indicated lower bound.

Consider now the case without biases. For each layer $l=1,\ldots,L$, we choose
the weights of all preactivation features of the $n_{l}$th unit as the
coordinate vector $e_{n_{l-1}}\in\mathbb{R}^{n_{l-1}}$, so that
$x^{l}_{n_{l}}=\max\\{x^{l-1}_{n_{l-1}},\ldots,x^{l-1}_{n_{l-1}}\\}=x^{l-1}_{n_{l-1}}$.
We consider the restriction of the network to the subset of inputs given by
the hyperplane $H=\\{x^{0}\in\mathbb{R}^{n_{0}}\colon x^{0}_{n_{0}}=1\\}$. The
number of linear regions of a function over this subset is a lower bound on
its number of regions over the entire input space $\mathbb{R}^{n_{0}}$. Notice
that, given our choice of weights, over $H$ the last unit of each layer takes
the fixed value $x^{0}_{n_{0}}=x^{1}_{n_{1}}=\cdots=x^{L}_{n_{L}}=1$. As in
Proposition 3.5, we choose the weights of the units $i=1,\ldots,n_{l}-1$ in
layer $l$ as $w^{\prime}_{i}=(w_{i},b_{i})\in\mathbb{R}^{n_{l-1}\times k}$,
with $w_{i}\in\mathbb{R}^{(n_{l-1}-1)\times k}$ the weights and
$b_{i}\in\mathbb{R}^{1\times k}$ the biases that are used above for a layer
with biases and $n_{l-1}-1$ inputs. Hence, over $H$ we obtain the same many-
to-one maps as above, but now with the widths substituted to
$n_{0}-1,\ldots,n_{L-1}-1$. Finally, note that the last layer can in fact be
chosen as in Proposition 3.5 with $n$ inputs and $n_{L}$ outputs. We take the
bound $\sum_{j=0}^{n-1}{n_{L}\choose j}(k-1)^{j}$ for the number of regions
intersecting $\\{x^{L-1}\in\mathbb{R}^{n_{L-1}}\colon x^{L-1}_{n_{L-1}}=1\\}$
and ignore other regions. ∎

Proposition 3.11 is given for networks where all units have the same rank $k$,
but it is straightforward to formulate corresponding results for networks with
units of different ranks. Also, it is not difficult to obtain minor
improvements if instead of discarding units one keeps them with small weights,
without altering the general construction. However, as we will see below, the
asymptotic is already tight.

We now derive upper bounds the number of linear regions $N(\Phi)$ of a
function $\Phi:\mathbb{R}^{n_{0}}\to\dots\to\mathbb{R}^{n_{L}}$ represented by
a deep neural network. Notice that each linear region of the function computed
up to the $(l-1)$th layer is split by the $l$th layer into at most the number
of linear regions of a shallow network with $n_{l-1}$ inputs and $n_{l}$
outputs. As pointed out in [34], the linear output pieces of the $(l-1)$th
layer have dimension bounded above by $\min\\{n_{0},\ldots,n_{l-1}\\}$, which
allows us to slightly improve the bound based on Corollary 3.9. Similar
discussions have also appeared in [42] and [57, Theorem 6.3]. We obtain the
following upper bound for deep networks. When all units have rank $k$, the
bound is of order $O(\prod_{l=1}^{L}(n_{l}k)^{n_{0}})$ in the layer widths
$n_{1},\ldots,n_{L}$ and rank $k$, which in view of Proposition 3.11 is tight.

######  Theorem 3.12 (Upper bound for deep maxout networks).

Let $\mathcal{N}$ be an network with $n_{0}$ inputs and $L$ layers of $n_{l}$
maxout units of ranks $k_{l,1},\ldots,k_{l,n_{l}}$, $l=1,\ldots,L$. Let
$e_{l}=\min\\{n_{0},\dots,n_{l-1}\\}$, $l=1,\ldots,L$. Then

$\displaystyle N(\mathcal{N})$
$\displaystyle\leq\prod_{l=1}^{L}\sum_{j=0}^{e_{l}}\sum_{S\in{[n_{l}]\choose
j}}\prod_{i\in S}(k_{l,i}-1).$ For the same network but without biases,
$\displaystyle N(\mathcal{N})$
$\displaystyle\leq\prod_{l=1}^{L}\Big{(}{n_{l}-1\choose
e_{l}-1}+\sum_{j=0}^{e_{l}-1}\sum_{S\in{[n_{l}]\choose j}}\prod_{i\in
S}(k_{l,i}-1)\Big{)}.$

Moreover, these bounds are asymptotically sharp.

###### Proof.

We write $\Phi^{(i,j)}:\mathbb{R}^{n_{i-1}}\to\dots\to\mathbb{R}^{n_{j}}$ for
the function represented by the network consisting of layers $i,\ldots,j$, and
write $\Phi^{(j)}$ for $\Phi^{(1,j)}$. For any $l\in[L]$ we have that
$\Phi=\Phi^{(l,L)}\circ\Phi^{(l-1)}$. We consider $N_{c}(\Phi)$, the smallest
number of convex regions that form a refinement of the linear regions of the
function $\Phi$. For a positive integer $e\leq n_{0}$, we will also need to
consider

$N_{c}(\Phi\mid
e):=\max\\{N_{c}(\Phi|_{\Omega}):\Omega\subseteq\mathbb{R}^{n_{0}}\text{ is an
}e\text{-dimensional affine space}\\}.$

Now, if $F$ is a layer with output dimension $d$, and $H=G\circ F$, where $G$
is a layer with a compatible number of inputs, then $N(H)\leq N_{c}(H)\leq
N_{c}(G\mid d)\cdot N_{c}(F)$. See [57, Theorem D.3] for a discussion. Hence
$N(\Phi)\leq N_{c}(\Phi^{(l,L)}\mid e_{l})\cdot
N_{c}(\Phi^{(l-1)})=N_{c}(\Phi^{(l,L)})\cdot N_{c}(\Phi^{(l-1)})$. The bounds
then follow by induction and Corollary 3.9, which bounds the number of regions
of a layer with inputs from an affine space of given dimension. Finally, the
asymptotic tightness of the bounds follows in view of Proposition 3.11. ∎

The bound is based on the observation that each of the linear regions of a
network with $l-1$ layers is mapped to a polyhedron of dimension at most
$e_{l}$ in the input space of the $l$th layer. The $l$th layer will split each
of these polyhedra into at most as many regions as it can create over an
affine space of dimension $e_{l}$. In principle, one can pursue a more refined
analysis by recursively investigating the arrangement that is induced by the
$l$th layer on the graph of the $(l-1)$-layer network, similar to the analysis
that we conduct in Sections 5 and 6 for maxout arrangements.

##  4 Face counting formulas à la Weibel

Weibel [52] obtained a counting formula for the number of faces of large
Minkowski sums of full-dimensional polytopes
$P_{1},\ldots,P_{m}\subseteq\mathbb{R}^{n+1}$, $m\geq n+1$, $\dim(P_{i})=n+1$,
in terms of the numbers of faces of partial sums of up to $n$ of the
polytopes. In the following we give a similar formula for the number of
_upper_ faces, which also holds when the summands have arbitrary dimensions.

The idea of [52] is to enumerate the $s$-faces of $P=P_{1}+\cdots+P_{m}$ by
inclusion-exclusion of the $s$-faces of the partial sums $P_{S}=\sum_{i\in
S}P_{i}$, $S\subseteq\\{1,\ldots,m\\}$ with $1\leq|S|\leq n$. In order to do
this, polytopes are associated with spherical complexes, and cells of the
complex are assigned a witness _westernmost corner_. We use similar
definitions with slight modifications.

######  Definition 4.1 (Spherical complex and upper complex of a polytope).

Let $P\subseteq\mathbb{R}^{n+1}$ be a polytope. To each face $F$ of $P$ we
associate the cell of directions it maximizes:
$C(F,P)=\\{l\in\mathbb{S}^{n}\colon\langle l,x-y\rangle>0\;\forall x\in F,y\in
P\setminus F\\}$. The set of all such cells is a spherical complex
$\mathcal{G}(P)$ dual to $P$. The upper complex $\mathcal{G}^{+}(P)$ consists
of the intersections of cells in $\mathcal{G}(P)$ with
$(\mathbb{R}^{n}\times\mathbb{R}_{>0})$. The upper part $P^{+}$ of a polytope
$P$ in $\mathbb{R}^{n+1}$, is the collection of faces $F$ of $P$ whose cells
$C(F,P)$ intersect $(\mathbb{R}^{n}\times\mathbb{R}_{>0})$. Let
$\mathbb{S}^{n}_{\geq
0}=\mathbb{S}^{n}\cap(\mathbb{R}^{n}\times\mathbb{R}_{\geq 0})$.

######  Definition 4.2 (General orientation).

A polytope $P\subseteq\mathbb{R}^{n+1}$ is said to be in general orientation
(relative to our coordinates) if none of the great circles defined by one-
dimensional cells in $\mathcal{G}(P)$ contains a standard unit vector. A
family of polytopes $P_{1},\dots,P_{m}\subseteq\mathbb{R}^{n+1}$ is in general
orientation, if each $P_{i}$ is in general orientation and for all
$S\subseteq[m]$ and any $C_{i}\in\mathcal{G}(P_{i})$, $i\in S$, the
intersection $\bigcap_{i\in S}C_{i}$ is either empty or has codimension at
least $\min\\{\sum_{i}\operatorname{codim}(C_{i}),n\\}$.

For $i=n+1,n-1,n-3,\ldots$, let $U^{i}$ be the $i$-dimensional subspace
$\operatorname{span}\\{e_{n+1-i+1},\ldots,e_{n+1}\\}$ if $i\geq 1$ and just
the zero space $\\{0\\}$ if $i\leq 0$. Given a fixed $U^{i}$, we write
$\hat{e}_{k}=e_{n+1-i+1+k}$ for $1\leq k\leq i$ so that
$\hat{e}_{1},\dots,\hat{e}_{i}$ is a basis of it.

######  Definition 4.3 (Direction west).

Let $i>1$. At every point in $\mathbb{S}^{n}\cap U^{i}\cong\mathbb{S}^{i-1}$
and not in $\mathbb{S}^{n}\cap U^{i-2}\cong\mathbb{S}^{i-3}$ define the
direction west as the direction of increasing $\theta_{1}$ in the coordinate
system given by
$\mathbb{S}^{1}=\\{\sin(\theta_{1})\hat{e}_{1}+\cos(\theta_{1})\hat{e}_{2}\colon\theta_{1}\in[0,2\pi)\\}$
and
$\mathbb{S}^{k}=\\{\sin(\theta_{k})\mathbb{S}^{k-1}+\cos(\theta_{k})\hat{e}_{k+1}\colon\theta_{k+1}\in[0,\pi]\\}$
for $k=2,3,\ldots,i-1$. Here, $\hat{e}_{k}=e_{n+1-i+1+k}$.

$<$west(a)$U^{1}=\text{span}\\{e_{3}\\}$$\mathbb{S}^{2}_{\phantom{\geq
0}}$$\mathbb{S}^{2}_{\phantom{\geq 0}}$(b)$\mathbb{S}^{2}_{\geq 0}$(c) blue
cell has no
westernmost point westernmost corner of blue cell Figure 2: (a) Shown is
$\mathcal{G}(P_{1}+P_{2}+P_{3})$, where $P_{1}$, $P_{2}$, $P_{3}$ have $2$,
$3$, $3$ vertices respectively, and the westernmost corners of its $0$-, $1$-,
and $2$-cells (westernmost corners of $2$-cells are colored by their support);
(b) Cells of $\mathcal{G}(P)$, $P$ lower-dimensional, may not have westernmost
points, but (c) cells of $\mathcal{G}^{+}(P)$ do.

######  Definition 4.4 (Westernmost point and westernmost corner).

We define a westernmost point of a cell $C\subseteq\mathbb{S}^{n}$ as follows:
Let $U^{i}$ be the smallest subspace in the sequence $U^{n+1},U^{n-1},\ldots$
which has a nonempty intersection with $C$. If $i>1$, a westernmost point of
$C$ is a local optimizer of the direction west in the closure of $C\cap
U^{i}$. If $i=1$, then $C\cap U^{i}\subseteq\\{\pm e_{n+1}\\}$. For $C\cap
U^{i}=\\{\pm e_{n+1}\\}$ the westernmost point of $C$ is $e_{n+1}$, otherwise
it is the single point in the intersection. Finally, we define a westernmost
corner of a cell as the intersection of its closure with a small ball around a
westernmost point.

The definition is illustrated in Figure 2 (a). Example 4.5 illustrates the
existence and non-existence of westernmost corners. Lemma 4.6 will state
sufficient conditions for existence and uniqueness.

######  Example 4.5.

  1. 1.

Consider the upper sphere $C=\mathbb{S}^{n}_{\geq 0}$. If $n$ is even, then
the smallest subspace among $U^{n+1},U^{n-1},\ldots,U^{1}$ which intersects
$C$ is $U^{1}$. Hence the westernmost point of $C$ is the north pole $C\cap
U^{1}=\\{(0,\ldots,0,1)\\}$. If $n$ is odd, then the smallest subspace which
intersects $C$ is $U^{2}$. Hence the westernmost point of $C$ is the optimizer
of $\theta_{1}$ over the half-circle $\mathbb{S}^{n}_{\geq 0}\cap
U^{2}\cong\mathbb{S}^{1}_{\geq 0}$, which is $\\{(0,\ldots,0,1,0)\\}$.

  2. 2.

If $P$ is not full dimensional, not every cell of $\mathcal{G}(P)$ needs to
have a westernmost point: Consider
$P=\operatorname{conv}\\{v,-v\\}\subseteq\mathbb{R}^{3}$ for a generic
$v\in\mathbb{S}^{2}$; see Figure 2 (b). Then $\mathcal{G}(P)$ consists of two
open half-spheres and a great circle. Each of the half-spheres intersects
$U^{1}$ at a single point, which is their westernmost point. The great circle
does not intersect $U^{1}$ and has no local optimum for the direction west.
Hence it has no westernmost point. Note however that each cell of
$\mathcal{G}^{+}(P)$ has a unique westernmost point; see Figure 2 (c).

  3. 3.

If a cell is not in general orientation relative to the $U^{i}$, then it can
have multiple westernmost points: Consider a segment of a great circle in
$\mathbb{S}^{2}$ passing through north and south poles. If it does not contain
either pole, then any of its points is a westernmost point.

######  Lemma 4.6.

Let $P\subseteq\mathbb{R}^{n+1}$ be a polytope. If $P$ is in general
orientation (relative to the coordinate system), then each cell of
$\mathcal{G}^{+}(P)$ has a unique westernmost corner. Additionally, if $P$ is
full-dimensional, then each cell of $\mathcal{G}(P)$ has a unique westernmost
corner.

###### Proof.

Note that cells of $\mathcal{G}^{+}(P)$ and, for $P$ full-dimensional, of
$\mathcal{G}(P)$ are spherically convex in the sense that any shortest arc
between two points is inside the set. Combined with $P$ being in general
orientation, [52, Lemma 6] shows that every cell has a westernmost point and
corner. Since $P$ is in general orientation, each cell has a single
westernmost point. ∎

######  Definition 4.7 (Support).

Let $P_{1},\ldots,P_{m}\subseteq\mathbb{R}^{n+1}$ be a family of polytopes.
The support of a point $w\in\mathbb{S}^{n}$ is defined as

$\operatorname{Supp}_{P_{1},\dots,P_{m}}(w)\coloneqq\\{i\in[m]\colon w\in
C_{i}\text{ for some }C_{i}\in\mathcal{G}(P_{i})\text{ with }\operatorname{co-
dim}(C_{i})\geq 1\\}\subseteq[m].$

In particular, the support of a generic point is $\emptyset$. The support
$\operatorname{Supp}_{P_{1},\dots,P_{m}}(W)$ of a westernmost corner $W$ of a
cell is defined to be the support of its westernmost point.

The following lemma points out that for polytopes in general orientation,
westernmost corners that appear in one sub-complex also appear in any larger
sub-complex.

######  Lemma 4.8.

Let $P_{1},\ldots,P_{m}$ be a family of polytopes in general orientation, and
let $W$ be a westernmost corner of an $s$-cell of $\mathcal{G}(P_{[m]})$. Then
$W$ is the westernmost corner of an $s$-cell of $\mathcal{G}(P_{S})$ if and
only if $\operatorname{Supp}_{P_{1},\ldots,P_{m}}(W)\subseteq S$.

###### Proof.

Note that $\mathcal{G}(P_{S})$ coincides with $\mathcal{G}(P_{[m]})$ locally
around $W$ if and only if its support
$\operatorname{Supp}_{P_{1},\ldots,P_{m}}(W)$ is contained in $S$. Thus the
claim is an immediate consequence of [52, Lemma 7], which states that for
spherically convex cells on $\mathbb{S}^{n}$ in general orientation
westernmost points are the local optima of the direction west. ∎

We will use the following lemma in order to enumerate the westernmost points
of Minkowski sums based on the above observation. Notice that ${m-r\choose
j-r}$ is the number of subsets of $[m]$ of cardinality $j$ which contain some
particular subset of $[m]$ of cardinality $r$.

######  Lemma 4.9.

For any integers $0\leq r\leq n<m$, we have
$\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}{m-r\choose j-r}=1$. In particular,
for any function $\xi_{(\cdot)}:2^{[m]}\rightarrow\mathbb{R}$ with
$\sum_{S\in\binom{[m]}{j}}\xi_{S}={m-r\choose j-r}$ for all $0\leq j\leq n$,

$\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in\binom{[m]}{j}}\xi_{S}=1.$

###### Proof.

The proof follows by induction over $m\geq n+1$, using for $m=n+1$ the fact
that $\sum_{j=0}^{n+1}(-1)^{j}{n+1-r\choose j-r}=0$ and hence
$\sum_{j=0}^{n}(-1)^{n-j}{n+1-r\choose j-r}=1$ for any $0\leq r<n+1$. ∎

We obtain the following linear relation between the number of upper $s$-faces
of a Minkowski sum of $m$ polytopes and the number of upper $s$-faces of
subsums of at most $n$ of the polytopes. This is a version of Weibel’s theorem
[52, Theorem 1] for the case of upper faces. Whereas that result is for sums
of full-dimensional polytopes, our statement is valid for any dimensions.

######  Theorem 4.10 (Number of upper faces of Minkowski sums).

Let $P_{1},\ldots,P_{m}$ be any positive dimensional polytopes in
$\mathbb{R}^{n+1}$ in general orientations, $m\geq n+1$, and
$P=P_{1}+\cdots+P_{m}$. Then for the number of $s$-faces of the upper part we
have

$f_{s}(P^{+})=\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}f_{s}(P_{S}^{+}),\quad s=0,\ldots,n,$

where $P_{S}=(\sum_{i\in S}P_{i})$ for any nonempty $S\subseteq[m]$, and
$P_{\emptyset}=\\{0\\}$.

###### Proof.

Consider the complex $\mathcal{G}^{+}(P)$, and recall that $s$-dimensional
upper faces of $P$ correspond to $(n-s)$-dimensional cells of
$\mathcal{G}^{+}(P)$. Let $W_{1},\dots,W_{N}$ be the westernmost corners of
$(n-s)$-cells of $\mathcal{G}^{+}(P)$ and let $I_{1},\dots,I_{N}\subseteq[m]$
denote their supports. Note that $0\leq|I_{i}|\leq n$ for all $i=1,\dots,N$.
Let $w_{s}(P_{S}^{+})$ denote the number of west-most corners of $(n-s)$-cells
of $P_{S}^{+}$, so that $w_{s}(P_{S}^{+})=f_{s}(P_{S}^{+})$. Writing
$f_{s}(P^{+})=N=\sum_{i=1}^{N}1$, we then obtain

$\displaystyle f_{s}(P^{+})\overset{Lem.}{\underset{\ref{lemma:inclusion-
exclusion}}{=}}\sum_{i=1}^{N}\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\\!\\!\\!\\!\sum_{S\in{[m]\choose
j}}\\!\\!\\!\mathbb{1}_{I_{i}\subseteq
S}=\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\\!\\!\\!\\!\sum_{S\in{[m]\choose
j}}\sum_{i=1}^{N}\mathbb{1}_{I_{i}\subseteq S}$
$\displaystyle\overset{Lem.}{\underset{\ref{lemma:sequence}}{=}}\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\\!\\!\sum_{S\in{[m]\choose
j}}w_{s}(P_{S}^{+})=\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\\!\\!\sum_{S\in{[m]\choose
j}}f_{s}(P_{S}^{+}).\qed$

One naturally wonders if the proof of Theorem 4.10 can be extended to count
the faces of the entire polytope, generalizing Weibel’s result to sums of
polytopes of arbitrary dimensions. Lemma 4.6 does not cover that case. We will
present an alternative approach in Section 6.

Weibel [52, Theorem 3] also shows, for sums of full-dimensional polytopes,
that the number of vertices is maximized when the partial sums attain the
trivial upper bound. The same arguments transfer to the case of upper
vertices, and one can show the following corollary. In the following we
consider families of polytopes $P_{i}$ satisfying $f_{0}(P_{i})=k_{i}$,
$i=1,\ldots,m$.

######  Corollary 4.11 (Upper bound for upper vertices of sums of full-
dimensional polytopes).

Let $m\geq n+1$ and $k_{1},\ldots,k_{m}\geq n+2$. Then
$f_{0}(P^{+})\leq\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}\prod_{i\in S}k_{i}$.

By comparison, Weibel’s upper bound for the total number of vertices is
$f_{0}(P)\leq\binom{m-1}{n}+$ $\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}\prod_{i\in S}k_{i}$. Unfortunately his argument
does not extend to the case where some of the $k_{i}$ are small, neither for
all vertices nor for upper vertices. To address that case, we will instead use
the upper bound theorem by Adiprasito-Sanyal [2]. Their result implies
Proposition 2.8, which states that if a Minkowski sum maximizes the number of
vertices, then the partial sums attain the trivial upper bound
$f_{0}(P_{S})=\prod_{i\in S}f_{0}(P_{i})$. The problem remaining is whether
maximizing the number of vertices $f_{0}(P)$ also entails maximizing the
number of upper vertices $f_{0}(P^{+})$ and whether the partial sums will also
attain the trivial upper bound for upper vertices. In Section 6 we will show
that this is indeed the case.

We find it useful to rewrite the alternating sum as follows.

######  Lemma 4.12.

Let $m\geq n+1\geq 1$ and $k_{1},\ldots,k_{m}\geq 2$. Then

$\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}\prod_{i\in S}k_{i}=\sum_{j=0}^{n}\sum_{S\in{[m]\choose j}}\prod_{i\in
S}(k_{i}-1).$

###### Proof.

We prove the equality by viewing both sides as polynomials in the variables
$k_{i}$ and examining the coefficient of each monomial. Fix a subset
$S\subseteq[m]$ of size $j$. The coefficient for the monomial
$k_{S}=\prod_{i\in S}k_{i}$ on the left-hand side of the equation is
$(-1)^{n-j}\binom{m-1-j}{n-j}$. On the right-hand side, the term $k_{S}$
appears with sign equal to $(-1)^{|T|-|S|}$ for each $T\supseteq S$. The
coefficient on the right-hand side is therefore $\sum_{T\supseteq
S}(-1)^{|T|-j}=\sum_{i=0}^{n-j}(-1)^{i}\cdot\binom{m-j}{i}$. The statement now
follows from the following observation, which is obtained by induction on $n$:
If $m\geq n+1\geq 1$, then
$\sum_{i=0}^{n}(-1)^{i}\binom{m}{i}=(-1)^{n}\binom{m-1}{n}$. ∎

##  5 Face counting formulas à la Zaslavsky

Zaslavsky [55] proved a theorem expressing the number of regions defined by a
hyperplane arrangement in terms of the characteristic polynomial, a function
obtained from the intersection poset of the arrangement. In the following we
derive a similar type of result for the case of maxout arrangements.
Hyperplanes are special in that their intersections are affine spaces and can
be discussed in terms of linear independence relations. In contrast, for
maxout arrangements the intersections involve linear equations and also linear
inequalities. In turn, the elements of the poset have a more complex topology
that needs to be accounted for. In general the poset also has a more complex
structure even if the arrangement is in general position.

######  Definition 5.1 (Maxout arrangement).

For a collection of $m$ maxout units
$z_{i}(x)=$$\max\\{A_{i,1}(x),\ldots,A_{i,k_{i}}(x)\\}$, $x\in\mathbb{R}^{n}$,
$i=1,\ldots,m$, we define the maxout arrangement
$\mathcal{A}=\\{H_{ab}^{i}\colon\\{a,b\\}\in{[k_{i}]\choose
2},i\in[m],\operatorname{co-dim}(H^{i}_{ab})=1\\}$ in $\mathbb{R}^{n}$ as the
collection of nonempty co-dimension $1$ indecision boundaries between pairs of
preactivation features, called atoms,

$H_{ab}^{i}=\left\\{x\in\mathbb{R}^{n}\colon
A_{i,a}(x)=A_{i,b}(x)=\max_{c\in[k_{i}]}\\{A_{i,c}(x)\\}\right\\}.$ (2)

We call the arrangement central if the affine functions $A_{i,a}$ of each unit
are linear.

We let $L(\mathcal{A})$ denote the set of all possible nonempty sets obtained
by intersecting subsets of elements in $\mathcal{A}$, including
$\mathbb{R}^{n}$ as the empty set intersection. The set $L(\mathcal{A})$ is
partially ordered by reverse inclusion, so that for any $s,t\in
L(\mathcal{A})$ we have $s\geq t$ if and only if $s\subseteq t$. The smallest
element, i.e. the $\hat{0}$ in this poset, is $\mathbb{R}^{n}$. For a given
arrangement $\mathcal{A}$, we denote by $r(\mathcal{A})$ the number of
connected components of $\mathbb{R}^{n}\setminus\cup_{H\in\mathcal{A}}H$,
called the regions of $\mathcal{A}$.

Note that rank-$1$ units have no indecision boundaries and can be ignored. In
the following we will therefore assume without loss of generality that
$k_{1},\ldots,k_{m}\geq 2$.

$H^{1}_{12}$$H^{1}_{23}$$H^{1}_{13}$$H^{2}_{12}$$H^{2}_{23}$$H^{2}_{13}$ |  $\mathbb{R}^{2}$$H^{1}_{12}$$H^{1}_{13}$$H^{1}_{23}$$H^{2}_{12}$$H^{2}_{13}$$H^{2}_{23}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
---|---
Figure 3: Shown is an arrangement of two maxout units of ranks $k_{1}=k_{2}=3$
on $\mathbb{R}^{2}$ along with its intersection poset discussed in Example 5.2
and 5.6.

######  Example 5.2.

Figure 3 shows a maxout arrangement of two rank-$3$ maxout units and their
intersection poset. The black indecision boundaries arise from
$z_{1}(x,y)=\max\\{2y,x+y+1,2\\}$, while the blue indecision boundaries arise
from $z_{2}(x,y)=\max\\{0,3x+2y,5x+y\\}$.

Recall that the Möbius function of a poset $L$ with partial order $\leq$ is
defined by $\mu_{L}(s,s)=1$ for $s\in L$, $\mu_{L}(s,u)=-\sum_{s\leq
t<u}\mu_{L}(s,t)$ for $s<u\in L$, and $\mu_{L}(s,u)=0$ for $s\not\leq u$. If
the poset has a minimal element $\hat{0}$, one also defines
$\mu_{L}(x):=\mu_{L}(\hat{0},x)$. The Möbius inversion formula for locally
finite posets states the following equivalence for functions $g$ and $h$ on
the poset [40]:

$\displaystyle g(t)=\sum_{s\leq t}h(s)\quad\forall t\in L\quad\text{if and
only if}\quad h(t)=\sum_{s\leq t}g(s)\mu_{L}(s,t)\quad\forall t\in L.$

Further, recall that if a space $X$ is suitably decomposed into cells with
$f_{s}$ cells of dimension $s$, then its Euler characteristic is defined as
$\psi(X):=f_{0}-f_{1}+f_{2}\mp\cdots$, whereby we follow the notation of [44].
Concretely, a polyhedral decomposition or a CW complex decomposition with
finitely many pieces are suitable for computing the Euler characteristic; see
[50, Chapter 4 Proposition 2.2]. The Euler characteristic is independent of
the specific decomposition.

A (closed) face of the arrangement $\mathcal{A}$ is a set of the form
$\emptyset\neq F=\overline{R}\cap x$, where $\overline{R}$ is the closure of a
connected component $R$ of $X\setminus\cup_{H\in\mathcal{A}}H$, and $x\in
L(\mathcal{A})$. Denote the set of faces of $\mathcal{A}$ by
$\mathcal{F}(\mathcal{A})$. The faces of an arrangement $\mathcal{A}$ in $X$
create a decomposition $X=\sqcup_{F\in
F(\mathcal{A})}\operatorname{relint}(F)$.

######  Definition 5.3 (Proper arrangement).

We call an arrangement $\mathcal{A}$ in a space $X$ proper if the set of faces
$\mathcal{F}(\mathcal{A})$ decomposes $X$ suitably for computing the Euler
characteristic.

######  Lemma 5.4.

A maxout arrangement in $\mathbb{R}^{n}$ is always proper. A central maxout
arrangement in $\mathbb{R}^{n+1}$ restricted to $\mathbb{S}^{n}$ is proper
whenever the associated Newton polytope in $\mathbb{R}^{n+1}$ has dimension
$n+1$.

###### Proof.

The maxout arrangement creates a polyhedral decomposition of $\mathbb{R}^{n}$.
For a central arrangement with full-dimensional polytope, the spherical cell
complex is equivalent to the boundary of the dual polytope, which is a CW
complex. ∎

We obtain the following counting formula for the number of regions of an
arrangement.

######  Theorem 5.5 (Number of faces of maxout arrangements).

Consider a proper arrangement $\mathcal{A}$ in a space $X$ (e.g.
$\mathbb{R}^{n}$ or $\mathbb{S}^{n}$). Then the number of regions defined by
$\mathcal{A}$ on $X$ satisfies

$r(\mathcal{A})=(-1)^{\dim(X)}\sum_{y\in
L(\mathcal{A})}\psi(y)\mu_{L(\mathcal{A})}(y).$

Moreover, writing $L(\mathcal{A})/x=\\{y\in L(\mathcal{A})\colon y\geq x\\}$,
the number of $s$-faces satisfies

$f_{s}(\mathcal{A})=\sum_{\begin{subarray}{c}x\in L(\mathcal{A})\\\
\dim(x)=s\end{subarray}}(-1)^{\dim(x)}\sum_{y\in
L(\mathcal{A})/x}\psi(y)\mu_{L(\mathcal{A})/x}(y),\quad s=0,\ldots,\dim(X)-1.$

This result is an instance of what Zaslavsky calls a fundamental theorem of
dissection theory [56, Theorem 1.2]. We note that if $\mathcal{A}$ is an
arrangement of hyperplanes in $\mathbb{R}^{n}$, then each $y\in
L(\mathcal{A})$ is an affine subspace with Euler characteristic
$\psi(y)=(-1)^{\dim(y)}$ and the statement of Theorem 5.5 corresponds to
Zaslavsky’s result [55, Theorem A], which states that for hyperplane
arrangements $r(\mathcal{A})=(-1)^{n}\sum_{x\in
L(\mathcal{A})}(-1)^{\dim(x)}\mu_{L(\mathcal{A})}(x)=(-1)^{n}\chi_{L(\mathcal{A})}(-1)$.
Here, the characteristic polynomial of $L(\mathcal{A})$ is defined as
$\chi_{L(\mathcal{A})}(t):=\sum_{x\in
L(\mathcal{A})}\mu_{L(\mathcal{A})}(x)t^{\dim(x)}$, $t\in\mathbb{R}$.

###### Proof of Theorem 5.5.

The proof follows the Eulerian method, i.e. the arguments of Zaslavsky’s quick
proofs in [55]. Consider an arrangement $\mathcal{A}$ in a space $X$. For any
$y\in L(\mathcal{A})$, denote the arrangement induced by $\mathcal{A}$ on $y$
as $\mathcal{A}^{y}:=\\{y\cap H\neq\emptyset\colon
H\in\mathcal{A},H\not\supseteq y\\}$. Now, every $k$-face of $\mathcal{A}$ is
closure of a region of exactly one $\mathcal{A}^{y}$, $y\in L(\mathcal{A})$,
$\dim(y)=k$. Hence we have

$f_{k}(\mathcal{A})=\sum_{\begin{subarray}{c}y\in L(\mathcal{A})\\\
\dim(y)=k\end{subarray}}r(\mathcal{A}^{y}).$ (3)

Hence, if $\mathcal{A}$ is proper, then we have
$\psi(X)=f_{0}(\mathcal{A})-f_{1}(\mathcal{A})\pm\cdots=\sum_{y\in
L(\mathcal{A})}(-1)^{\dim(y)}r(\mathcal{A}^{y})$. We have an analogous
expression for any $x\in L(\mathcal{A})$ in place of $X$. Note that if
$\mathcal{A}$ is proper, then so is $\mathcal{A}^{y}$ for any $y\in
L(\mathcal{A})$. Hence,

$\psi(x)=\sum_{\begin{subarray}{c}y\in L(\mathcal{A})\\\ y\geq
x\end{subarray}}(-1)^{\dim(y)}r(\mathcal{A}^{y})\quad\forall x\in
L(\mathcal{A}).$

The Möbius inversion formula then gives

$(-1)^{\dim(x)}r(\mathcal{A}^{x})=\sum_{\begin{subarray}{c}y\in
L(\mathcal{A})\\\ y\geq
x\end{subarray}}\psi(y)\mu_{L(\mathcal{A})}(x,y)\quad\forall x\in
L(\mathcal{A}).$

Substituting $x=X$ gives $(-1)^{\dim(X)}r(\mathcal{A})=\sum_{y\in
L(\mathcal{A})}\psi(y)\mu_{L(\mathcal{A})}(y)$. This completes the proof of
the first statement. The second statement is by (3) and applying the first
statement to each element of the intersection poset of dimension $s$. ∎

######  Example 5.6.

We illustrate Theorem 5.5. We consider the arrangement of two maxout units of
ranks $k_{1}=k_{2}=3$ in $\mathbb{R}^{n}$, $n=2$, shown in Figure 3. In this
example $\mu(\mathbb{R}^{2})=1$, $\mu(H^{i}_{ab})=-1$, $\mu(\bullet)=2$,
$\mu({\color[rgb]{0.2,0.2,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,1}\bullet})=2$,
$\mu({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=1$,
and $\psi(\mathbb{R}^{2})=(-1)^{2}=1$, $\psi(H^{i}_{ab})=1-1=0$,
$\psi(\bullet)=\psi({\color[rgb]{0.2,0.2,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,1}\bullet})=\psi({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=(-1)^{0}=1$.
By Theorem 5.5, the number of regions and $1$-faces are

$\displaystyle r(\mathcal{A})$ $\displaystyle=\sum_{y\in
L(\mathcal{A})}\psi(y)\mu_{L(\mathcal{A})}(y)=1+0(-1\\!-\\!1\\!-\\!1\\!-\\!1\\!-\\!1\\!-\\!1)+(-1)^{0}(2\\!+\\!2\\!+\\!1\\!+\\!1\\!+\\!1)=8,$
$\displaystyle f_{1}(\mathcal{A})$
$\displaystyle=\sum_{\begin{subarray}{c}x\in L(\mathcal{A})\\\
\dim(x)=1\end{subarray}}(-1)^{\dim(x)}\sum_{y\in
L(\mathcal{A})/x}\psi(y)\mu_{L(\mathcal{A})/x}(y)$
$\displaystyle=(-1)^{1}(\underbracket{(0\\!-\\!1\\!-\\!1)}_{x=H^{1}_{12}}+\underbracket{(0\\!-\\!1\\!-\\!1)}_{x=H^{1}_{13}}+\underbracket{(0\\!-\\!1\\!-\\!1)}_{x=H^{1}_{23}}+\underbracket{(0\\!-\\!1\\!-\\!1)}_{x=H^{2}_{12}}+\underbracket{(0\\!-\\!1)}_{x=H^{2}_{13}}+\underbracket{(0\\!-\\!1\\!-\\!1\\!-\\!1)}_{x=H^{2}_{23}})=12.$

For a general maxout arrangement, the Euler characteristic of the elements of
the intersection poset may depend not only on the dimension. Besides the case
of hyperplane arrangements, we note another special case where it depends only
on the dimension. For central arrangements of full-dimensional maxout units in
$\mathbb{R}^{n+1}$ (i.e. each of the polytopes $P_{1},\ldots,P_{m}$ has
dimension $n+1$), each $y\in
L(\mathcal{A})\setminus\\{\mathbb{R}^{n+1},\\{0\\}\\}$ is an unbounded pointed
cone with $\psi(y)=0$ (this can be deduced from the fact that any bounded
convex polytope has Euler characteristic $1$). Hence, noting that
$\psi(\mathbb{R}^{n+1})=(-1)^{n+1}$ and $\psi(\\{0\\})=1$, we may express the
number of regions of such an $\mathcal{A}$ in terms of the characteristic
polynomial $\chi_{L(\mathcal{A})}(t)=\sum_{y\in
L(\mathcal{A})}\mu_{L(\mathcal{A})}(y)t^{\dim(y)}$ as follows.

######  Proposition 5.7.

For a central arrangement $\mathcal{A}$ of full-dimensional maxout units in
$\mathbb{R}^{n+1}$, $r(\mathcal{A})=1+(-1)^{n+1}\chi_{L(\mathcal{A})}(0)$.

##  6 Region counting by regions of sub-arrangements

Our objective in this section is to write the number of regions
$r(\mathcal{A})$ of an arrangement $\mathcal{A}$ in terms of the numbers of
regions of small sub-arrangements. To this end we will focus on simple
arrangements, which arise from maxout units with generic parameters, and
combine the results from Sections 4 and 5. As before, we will assume that each
maxout unit has rank at least two. To draw a bridge between the upper vertices
and all vertices of Minkowski sums of polytopes, we consider both non-central
and central arrangements.

######  Definition 6.1 (Simple arrangements).

Let $\mathcal{A}=\\{H^{i}_{ab}\\}_{i\in[m],\\{a,b\\}}$ be a maxout
arrangement. For any $S\subseteq[m]$, write
$\mathcal{A}_{S}=\\{H^{i}_{ab}\\}_{i\in S,\\{a,b\\}}$ for the sub-arrangement
of atoms of units $i\in S$.

A maxout arrangement $\mathcal{A}$ is simple, or in general position, if the
intersection of any $j$ atoms of different units is either empty or has co-
dimension $j$. In the case of a central arrangement, all atoms contain the
origin $0$. A central maxout arrangement $\mathcal{A}$ is simple if the
intersection of any $j$ atoms of different units is either the origin or has
co-dimension $j$.

If $\mathcal{A}$ is simple, we define the support of an element
$y=\cap_{l=1}^{r}H^{i_{l}}_{a_{l}b_{l}}\in L(\mathcal{A})$, with $y\neq 0$ if
$\mathcal{A}$ is central, as the set $\\{i_{1},\dots,i_{r}\\}\subseteq[m]$.
Note that while $y$ may not have a unique representation as intersection of
atoms, the support is well-defined if $\mathcal{A}$ is simple and $y\neq 0$ if
$\mathcal{A}$ central.

###  6.1 Simple non-central arrangements

Simple non-central arrangements have the convenient property that an element
$y\in L(\mathcal{A})$ of the intersection poset is contained in the
intersection poset $L(\mathcal{A}_{S})$ of a sub-arrangement $\mathcal{A}_{S}$
if and only if the support of $y$ is contained in $S$. This mimics the
behavior of westernmost corners in Lemma 4.8, but without the need of a
coordinate system and local optimization. We obtain a formula similar to
Theorem 4.10 for upper vertices with a short proof based on Theorem 5.5.

######  Theorem 6.2 (Number of regions of a simple non-central arrangement).

Let $\mathcal{A}$ be a simple arrangement of $m\geq n+1$ maxout units of ranks
$k_{1},\ldots,k_{m}\geq 2$ in $\mathbb{R}^{n}$. Then

$\displaystyle r(\mathcal{A})=\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}r(\mathcal{A}_{S}).$

###### Proof of Theorem 6.2.

If $\mathcal{A}$ is simple, then any element in $L(\mathcal{A})$ can be
written as an intersection of at most $n$ atoms. Moreover, any $y\in
L(\mathcal{A})$ is included in $L(\mathcal{A}_{S})$ if and only if its support
is contained in $S$. Hence, using Lemma 4.9 and the fact that
$\mu_{L(\mathcal{A})}(y)=\mu_{L(\mathcal{A}_{S})}(y)$ for any $y\in
L(\mathcal{A}_{S})$, we can rewrite the expression from Theorem 5.5 as
follows:

$\displaystyle r(\mathcal{A})$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Thm.~{}\ref{thm:posetcounting}}}}{=}}(-1)^{n}\sum_{y\in
L(\mathcal{A})}\psi(y)\mu_{L(\mathcal{A})}(y)$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Lem.~{}\ref{lemma:inclusion-
exclusion}}}}{=}}(-1)^{n}\sum_{y\in
L(\mathcal{A})}\psi(y)\mu_{L(\mathcal{A})}(y)\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\sum_{S\in{[m]\choose
j}}\mathbb{1}_{y\in L(\mathcal{A}_{S})}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}(-1)^{n}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}\sum_{y\in
L(\mathcal{A}_{S})}\psi(y)\mu_{L(\mathcal{A}_{S})}(y)$ (4)
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Thm.~{}\ref{thm:posetcounting}}}}{=}}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}r(\mathcal{A}_{S}).\qed$

###  6.2 Simple central arrangements

Simple central arrangements come with the added challenge that the origin
$\\{0\\}=\hat{1}\in L(\mathcal{A})$ may be contained in several posets
$L(\mathcal{A}_{S})$ with $S\subseteq[m]$, $S\neq\emptyset$, while not being
contained in the poset corresponding to the intersection of these $S$. See
Figure 4. Consequently, there is no obvious way to define a support for
$\\{0\\}$ that is consistent with Lemma 4.8, which in turn makes it difficult
to apply Lemma 4.9. We thus need to treat $\\{0\\}$ separately. We consider
central arrangements in $\mathbb{R}^{n+1}$, corresponding to the ambient space
of the lifted Newton polytopes of maxout networks with input space
$\mathbb{R}^{n}$.

$\mathcal{A}_{\\{1,2\\}}$$L(\mathcal{A}_{\\{1,2\\}})=\\{\mathbb{R}^{2},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{R}\cdot
e_{1}},{\color[rgb]{0.2,0.2,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.2,0.2,1}\mathbb{R}\cdot
e_{2}},\\{0\\}\\}$$\mathcal{A}_{\\{1,3\\}}$$L(\mathcal{A}_{\\{1,3\\}})=\\{\mathbb{R}^{2},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{R}\cdot
e_{1}},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\mathbb{R}\cdot(e_{1}+e_{2})},\\{0\\}\\}$$\mathcal{A}_{\\{1\\}}$$L(\mathcal{A}_{\\{1\\}})=\\{\mathbb{R}^{2},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{R}\cdot
e_{1}}\\}$ Figure 4: The origin $\\{0\\}$ is contained in both the
intersection poset of $\mathcal{A}_{\\{1,2\\}}$ and of
$\mathcal{A}_{\\{1,3\\}}$, but not in the intersection poset of
$\mathcal{A}_{\\{1,2\\}\cap\\{1,3\\}}$.

#### Special case

First we present a simple approach to enumerate the regions of a central
arrangement in the special case that the $\mathcal{A}_{\\{i\\}}$ are proper.
We consider the arrangement $\mathcal{A}\cap\mathbb{S}^{n}$, which for
simplicity of notation we will still denote $\mathcal{A}$. For a central
arrangement in $\mathbb{R}^{n+1}$, the number of regions it defines in
$\mathbb{R}^{n+1}$ is equal to the number of regions it defines on
$\mathbb{S}^{n}$. Conveniently, $\\{0\\}$ no longer appears in the posets over
$\mathbb{S}^{n}$. For a central arrangement of $m\geq n+1$ units of ranks
$k_{1},\ldots,k_{m}\geq 2$, as before in (6.1),

$\displaystyle r(\mathcal{A})=(-1)^{n}\\!\\!\sum_{y\in
L(\mathcal{A})}\\!\\!\\!\psi(y)\mu_{L(\mathcal{A})}(y)=$
$\displaystyle(-1)^{n}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\\!\\!\sum_{S\in{[m]\choose j}}\sum_{y\in
L(\mathcal{A}_{S})}\\!\\!\\!\psi(y)\mu_{L(\mathcal{A}_{S})}(y).$ (5)

Under the additional assumption that the arrangement $\mathcal{A}_{S}$ on
$\mathbb{S}^{n}$ is proper for all $S\neq\emptyset$ (e.g. the lifted Newton
polytopes of all maxout units are full-dimensional), we can use Theorem 5.5 to
rewrite (5) as

$\displaystyle r(\mathcal{A})=$ $\displaystyle(-1)^{n}{m-1\choose
n}\psi(\mathbb{S}^{n})+\sum_{j=1}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}r(\mathcal{A}_{S})$ $\displaystyle=$
$\displaystyle\psi(\mathbb{S}^{n})+\sum_{j=1}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}(r(\mathcal{A}_{S})-\psi(\mathbb{S}^{n})),$ (6)

in which we also use $\sum_{y\in
L(\mathcal{A}_{\emptyset})}\psi(y)\mu_{L(\mathcal{A}_{\emptyset})}(y)=\psi(\mathbb{S}^{n})$
and $\sum_{j=1}^{n}(-1)^{n-j}{m-1-j\choose n-j}{m\choose
j}=1-(-1)^{n}{m-1\choose n}$ which follows from Lemma 4.9. Since
$\psi(\mathbb{S}^{n})=0$ if $n$ is odd and $\psi(\mathbb{S}^{n})=2$ if $n$ is
even, (6) recovers the $k=0$ case of [52, Theorem 1].

#### General case

Next, we present an approach to handle the origin directly in
$\mathbb{R}^{n+1}$, which will allow us to address the general case where the
lifted Newton polytopes of the maxout units need not be full-dimensional. Our
goal is to prove the following theorem:

######  Theorem 6.3 (Number of regions of a simple central arrangement).

For a central simple arrangement $\mathcal{A}$ of $m$ maxout units of ranks
$k_{1},\ldots,k_{m}\geq 2$ in $\mathbb{R}^{n+1}$, $m\geq n+1$,

$r(\mathcal{A})={m-1\choose n}+\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}r(\mathcal{A}_{S}).$

To prove Theorem 6.3, we will use use Theorem 5.5 to write $r(\mathcal{A})$ as
a sum of terms $\psi(y)\mu_{L(\mathcal{A})}(y)$ over $y\in L(\mathcal{A})$.
For the elements $y\in L(\mathcal{A})\setminus\\{0\\}$ we can use similar
arguments as before. To handle $\\{0\\}=\hat{1}\in L(\mathcal{A})$ we will use
the Cross-cut Theorem:

######  Theorem 6.4 (Cross-cut Theorem [40]).

Let $L$ be a finite lattice. Let $X$ be a subset of $L$ such that
$\hat{0}\not\in X$ and such that if $y\in L$, $y\neq\hat{0}$, then some $x\in
X$ satisfies $x\leq y$. Let $N_{k}$ be the number of $k$ element subsets of
$X$ with join $\hat{1}$. Then
$\mu_{L}(\hat{0},\hat{1})=N_{0}-N_{1}+N_{2}\mp\cdots$.

In the following we will evaluate this formula for the case of the
intersection poset $L(\mathcal{A})$ of a simple central arrangement, and split
the expression into terms corresponding to sub-arrangements $\mathcal{A}_{S}$
with $0\leq|S|\leq n$. We will use following definitions.

######  Definition 6.5.

Let $\mathcal{A}$ be a simple central arrangement of $m$ maxout units. For
$S\subseteq[m]$ of cardinality $|S|\leq n$, let $N_{k}^{S}$ denote the number
of $k$ element subsets of $\mathcal{A}_{S}$ with join $\\{0\\}$. For $k>n$,
let $N_{k}^{\ast}$ denote the number of $k$ element subsets of $\mathcal{A}$
which contain atoms of at least $n+1$ units. Note that their join is
necessarily $\\{0\\}$ as $\mathcal{A}$ is simple.

First we note that the terms involving more than $n$ units can be grouped as
follows.

######  Lemma 6.6.

Let $\mathcal{A}$ be a simple central arrangement of $m$ maxout units in
$\mathbb{R}^{n+1}$, and let $M\coloneqq|\mathcal{A}|$ be the number of its
atoms. Then $\sum_{k=n+1}^{M}(-1)^{k}N_{k}^{\ast}=-(-1)^{n}{m-1\choose n}$.

###### Proof.

The statement follows from reformulations obtained by splitting $k$ element
subsets of $\mathcal{A}$ with atoms from $\mathcal{A}_{\\{i\\}}$, $i\in S$,
into a disjoint union of non-empty $J_{i}\subseteq\mathcal{A}_{\\{i\\}}$,
$i\in S$:

$\displaystyle\sum_{r=n+1}^{M}(-1)^{r}N_{r}^{\ast}=\sum_{r=n+1}^{m}\sum_{S\in{[m]\choose
r}}\sum_{\begin{subarray}{c}\emptyset\neq
J_{i}\subseteq\mathcal{A}_{\\{i\\}}\\\ \text{for all }i\in
S\end{subarray}}\\!\\!(-1)^{\sum_{i\in
S}|J_{i}|}=\sum_{r=n+1}^{m}\sum_{S\in{[m]\choose r}}\prod_{i\in
S}\sum_{j_{i}=1}^{|\mathcal{A}_{\\{i\\}}|}{|\mathcal{A}_{\\{i\\}}|\choose
j_{i}}(-1)^{j_{i}}$ $\displaystyle=\sum_{r=n+1}^{m}\sum_{S\in{[m]\choose
r}}\prod_{i\in S}\left(-1\right)=\sum_{r=n+1}^{m}{m\choose
r}(-1)^{r}=-\sum_{r=0}^{n}{m\choose r}(-1)^{r}=-(-1)^{n}{m-1\choose n}.\qed$

Now using Theorem 6.4 and Lemma 6.6, we obtain the following description of
$\mu_{L(\mathcal{A})}(\\{0\\})$.

######  Lemma 6.7.

Let $\mathcal{A}$ be a simple central arrangement of $m$ maxout units in
$\mathbb{R}^{n+1}$. Then

$\mu_{L(\mathcal{A})}(\\{0\\})=-(-1)^{n}{m-1\choose
n}+\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}\mu_{L(\mathcal{A}_{S})}(\\{0\\})\mathds{1}_{\\{0\\}\in
L(\mathcal{A}_{S})}.$

Here $\mathds{1}_{\\{0\\}\in L(\mathcal{A}_{S})}$ takes value $1$ if
$\\{0\\}\in L(\mathcal{A}_{S})$ and $0$ otherwise.

###### Proof.

Let $M\coloneqq|\mathcal{A}|$ be the number of atoms of $\mathcal{A}$, and for
a subset $A\subseteq\mathcal{A}$ let $\operatorname{Supp}(A)\subseteq[m]$
denote the minimal $S\subseteq[m]$ with $A\subseteq\mathcal{A}_{S}$. With
Theorem 6.4 we can decompose
$\mu_{L(\mathcal{A})}(\\{0\\})=\mu_{L(\mathcal{A})}(\hat{0},\hat{1})$ as

$\displaystyle\mu_{L(\mathcal{A})}(\\{0\\})\mathrel{\overset{\scriptsize{\eqmakebox[O]{Thm.~{}\ref{thm:cross-
cut}}}}{=}}\sum_{k=0}^{M}(-1)^{k}N_{k}=\bigg{[}\sum_{k=n+1}^{M}(-1)^{k}N_{k}^{\ast}\bigg{]}+\bigg{[}\sum_{k=0}^{M}(-1)^{k}\sum_{\begin{subarray}{c}A\in\binom{\mathcal{A}}{k}\\\
\text{join}(A)=\\{0\\}\\\ |\operatorname{Supp}(A)|\leq
n\end{subarray}}1\bigg{]}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Lem.~{}\ref{lemma:inclusion-
exclusion}}}}{=}}\bigg{[}\sum_{k=n+1}^{M}(-1)^{k}N_{k}^{\ast}\bigg{]}+\bigg{[}\sum_{k=0}^{M}(-1)^{k}\\!\\!\\!\sum_{\begin{subarray}{c}A\in\binom{\mathcal{A}}{k}\\\
\text{join}(A)=\\{0\\}\\\ |\operatorname{Supp}(A)|\leq
n\end{subarray}}\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\sum_{S\in\binom{[m]}{j}}\mathbb{1}_{\operatorname{Supp}(A)\subseteq
S}\bigg{]}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}\bigg{[}\sum_{k=n+1}^{M}(-1)^{k}N_{k}^{\ast}\bigg{]}+\bigg{[}\sum_{j=0}^{n}(-1)^{n-j}\binom{m-1-j}{n-j}\sum_{S\in\binom{[m]}{j}}\sum_{k=0}^{M}(-1)^{k}\\!\\!\\!\sum_{\begin{subarray}{c}A\in\binom{\mathcal{A}}{k}\\\
\text{join}(A)=\\{0\\}\\\ |\operatorname{Supp}(A)|\leq
n\end{subarray}}\mathbb{1}_{\operatorname{Supp}(A)\subseteq S}\bigg{]}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}\bigg{[}\sum_{k=n+1}^{M}(-1)^{k}N_{k}^{\ast}\bigg{]}+\bigg{[}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}\sum_{k=0}^{M}(-1)^{k}N_{k}^{S}\bigg{]}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}\bigg{[}\sum_{k=n+1}^{M}(-1)^{k}N_{k}^{\ast}\bigg{]}+\bigg{[}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose
j}}\mu_{L(\mathcal{A}_{S})}(\\{0\\})\mathds{1}_{\\{0\\}\in
L(\mathcal{A}_{S})}\bigg{]}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Lem.~{}\ref{lem:central-3}}}}{=}}-(-1)^{n}{m-1\choose
n}+\bigg{[}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}\mu_{L(\mathcal{A}_{S})}(\\{0\\})\mathds{1}_{\\{0\\}\in
L(\mathcal{A}_{S})}\bigg{]}.\qed$

We now have all the supporting results we need to prove Theorem 6.3.

###### Proof of Theorem 6.3.

Similar to the proof of Theorem 6.2, note that if $\mathcal{A}$ is simple,
then any element in $L(\mathcal{A})\setminus\\{0\\}$ can be written as an
intersection of at most $n$ atoms. Moreover, any $y\in
L(\mathcal{A})\setminus\\{0\\}$ is contained in $L(\mathcal{A}_{S})$ if and
only if its support is contained in $S$. This allows us to apply Lemma 4.9 as
in the proof of Theorem 6.2 for $y\in L(\mathcal{A})\setminus\\{0\\}$. Hence

$\displaystyle
r(\mathcal{A})\mathrel{\overset{\scriptsize{\eqmakebox[O]{Thm.~{}\ref{thm:posetcounting}}}}{=}}(-1)^{n+1}\psi(\\{0\\})\mu_{L(\mathcal{A})}(\\{0\\})+(-1)^{n+1}\sum_{y\in
L(\mathcal{A})\setminus\\{0\\}}\psi(y)\mu_{L(\mathcal{A})}(y)$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Lem.~{}\ref{lemma:inclusion-
exclusion}}}}{=}}(-1)^{n+1}\mu_{L(\mathcal{A})}(\\{0\\})+(-1)^{n+1}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\\!\\!\\!\sum_{S\in{[m]\choose j}}\sum_{y\in
L(\mathcal{A}_{S})\setminus\\{0\\}}\\!\\!\\!\\!\\!\psi(y)\mu_{L(\mathcal{A}_{S})}(y)$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Lem.~{}\ref{lem:central}}}}{=}}{m-1\choose
n}+(-1)^{n+1}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}\Big{(}\mu_{L(\mathcal{A}_{S})}(\\{0\\})\mathds{1}_{\\{0\\}\in
L(\mathcal{A}_{S})}$ $\displaystyle\hskip 278.837pt+\sum_{y\in
L(\mathcal{A}_{S})\setminus\\{0\\}}\psi(y)\mu_{L(\mathcal{A}_{S})}(y)\Big{)}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}{m-1\choose
n}+(-1)^{n+1}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}\sum_{y\in L(\mathcal{A}_{S})}\psi(y)\mu_{L(\mathcal{A}_{S})}(y)$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Thm.~{}\ref{thm:posetcounting}}}}{=}}{m-1\choose
n}+\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}r(\mathcal{A}_{S}).\qed$

Recall that units of rank $1$ have an empty arrangement and can be ignored.
Theorem 6.3 generalizes (6) and Weibel’s result [52, Theorem 1 for $k=0$] by
removing the requirement that $k_{1},\ldots,k_{m}\geq n+2$. We illustrate
Theorem 6.3 in the next example.

######  Example 6.8.

  1. 1.

Consider the arrangement of $m=2$ maxout units of ranks $k_{1}=3$, $k_{2}=2$
in $\mathbb{R}^{d}$, $d=n+1=2$ shown in the left part of Figure 5. In this
example $\mu(\mathbb{R}^{2})=1$, $\mu(H^{i}_{ab})=-1$,
$\mu({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bullet})=3$.
By Theorem 5.5, $r(\mathcal{A})=\sum_{y\in
L(\mathcal{A})}\psi(y)\mu_{L(\mathcal{A})}(y)=(-1)^{2}1+0(-1-1-1)+(-1)^{1}(-1)+(-1)^{0}3=5$.
By Theorem 6.3, this can be written as
$r(\mathcal{A})=\psi(\mathbb{S}^{n}){m-1\choose
n}+\sum_{j=1}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}r(\mathcal{A}_{S})=0+(-1)^{0}{0\choose 0}(3+2)=5$.

  2. 2.

Consider now the arrangement of $m=3$ maxout units of ranks $k_{1}=3$,
$k_{2}=3$, $k_{3}=2$ in $\mathbb{R}^{d}$, $d=n+1=3$, shown in the right part
of Figure 5. By Theorem 6.3, the number of regions is
$r(\mathcal{A})=2{3-1\choose 2}+(-1)^{2-1}{3-1-1\choose
2-1}(3+3+2)+(-1)^{2-2}{3-1-2\choose 2-2}(9+6+6)=15$.

$H^{1}_{12}$$H^{1}_{23}$$H^{1}_{13}$$H^{2}_{12}$ |  $\mathcal{A}_{1}$$\mathcal{A}_{2}$$\mathcal{A}_{3}$
---|---
Figure 5: Shown are two central maxout arrangements, one in $\mathbb{R}^{2}$
and one $\mathbb{R}^{3}$ (for clarity we show only the intersection with
$\mathbb{S}^{2}$), discussed in Example 6.8.

###  6.3 Strictly upper vertices or bounded regions

We now have counting formulas for the number of upper vertices and the total
number of vertices of a Minkowski sum of polytopes. Given a sharp upper bound
on the total number of vertices, we can obtain a sharp upper bound on the
number of upper vertices if we also have an appropriate lower bound on the
number of strict lower vertices. In this subsection we derive such a lower
bound.

The strict upper vertices of a Minkowski sum correspond to the bounded regions
that a central maxout arrangement defines on a hyperplane that does not
intersect the origin, which are the regions that do not intersect the negated
hyperplane. These are also equivalent to the bounded regions of a non-central
arrangement in one dimension lower. The case of central hyperplane
arrangements was studied in [15, Theorem 3.2], showing that, in that case, the
induced arrangement over a general hyperplane has $\mu(\hat{0},\hat{1})$
relatively bounded regions. A particular challenge in the case of maxout
arrangements is that the atoms need not be symmetric. This means that the
number of bounded regions it defines over a hyperplane may depend on the
particular choice of the hyperplane. We obtain a lower bound that is
independent of this choice.

######  Theorem 6.9 (Lower bound on the number of bounded regions).

Let $\mathcal{A}$ be a simple central maxout arrangement in
$\mathbb{R}^{n+1}$. Let $g=\\{x\in\mathbb{R}^{n+1}\colon\langle
x,w\rangle=1\\}$ be an affine hyperplane that does not contain the origin. Let
$\mathcal{A}^{g}=\\{g\cap H\neq\emptyset\colon H\in\mathcal{A},H\not\supseteq
g\\}$. Then the number of regions of $\mathcal{A}$ which do not intersect $g$,
i.e. regions consisting of points with $\langle x,w\rangle\leq 0$, satisfies

$\displaystyle r(\mathcal{A})-r(\mathcal{A}^{g})\geq$
$\displaystyle{m-1\choose n}.$

###### Proof.

By Theorem 6.3 and Theorem 6.2, we have

$r(\mathcal{A})-r(\mathcal{A}^{g})={m-1\choose
n}+\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}(r(\mathcal{A}_{S})-r(\mathcal{A}_{S}^{g})).$

It remains to show that the second summand is non-negative. We define the
support of a region $R$ of $\mathcal{A}_{S}$ resp. $\mathcal{A}^{g}_{S}$ to be
the minimal $Q\subseteq[m]$ such that $R$ is a region of $\mathcal{A}_{Q}$
resp. $\mathcal{A}_{Q}^{g}$. Let $s(\mathcal{A}_{Q})$ resp.
$s(\mathcal{A}_{Q}^{g})$ be the number of regions of $\mathcal{A}_{Q}$ resp.
$\mathcal{A}^{g}_{Q}$ with support $Q$, so that
$r(\mathcal{A}_{S})=\sum_{Q\subseteq S}s(\mathcal{A}_{Q})$ and
$r(\mathcal{A}_{S}^{g})=\sum_{Q\subseteq S}s(\mathcal{A}_{Q}^{g})$. Then

$\displaystyle\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose n-j}\sum_{S\in{[m]\choose
j}}(r(\mathcal{A}_{S})-r(\mathcal{A}_{S}^{g}))$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{S\in{[m]\choose j}}\sum_{Q\subseteq
S}(s(\mathcal{A}_{Q})-s(\mathcal{A}_{Q}^{g}))$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\sum_{\begin{subarray}{c}Q\subseteq[m]\\\ |Q|\leq
j\end{subarray}}\binom{m-|Q|}{j-|Q|}(s(\mathcal{A}_{Q})-s(\mathcal{A}_{Q}^{g}))$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{}}}{=}}\sum_{\begin{subarray}{c}Q\subseteq[m]\\\
|Q|\leq
n\end{subarray}}(s(\mathcal{A}_{Q})-s(\mathcal{A}_{Q}^{g}))\sum_{j=0}^{n}(-1)^{n-j}{m-1-j\choose
n-j}\binom{m-|Q|}{j-|Q|}$
$\displaystyle\mathrel{\overset{\scriptsize{\eqmakebox[O]{Lem.~{}\ref{lemma:inclusion-
exclusion}}}}{=}}\sum_{\begin{subarray}{c}Q\subseteq[m]\\\ |Q|\leq
n\end{subarray}}(s(\mathcal{A}_{Q})-s(\mathcal{A}_{Q}^{g})).$

Finally, note that each summand in the final expression is non-negative since
the regions of a sub-arrangement $\mathcal{A}_{Q}$ intersecting $g$ is a
subset of the regions of $\mathcal{A}_{Q}$, and the same holds true for
regions that are not contained in a smaller arrangement
$\mathcal{A}_{Q^{\prime}}$, $Q^{\prime}\subsetneq Q$. ∎

##  7 Discussion and outlook

We presented sharp explicit upper bounds for the number of linear regions of
the functions that can be represented by shallow maxout networks with and
without biases. These results can be regarded as upper bound theorems for
tropical arrangements or upper bound theorems for the number of vertices and
upper vertices of Minkowski sums of polytopes with given numbers of vertices.
As a direct application of our sharp bounds for shallow maxout networks, we
obtained asymptotically tight bounds for deep maxout networks. These results
substantially improve previous lower and upper bounds.

We presented counting formulas for the number of faces of maxout arrangements
in terms of the intersection poset. In the case of simple arrangements or
Minkowski sums of polytopes in general orientations, we obtained formulas in
terms of sub-arrangements or Minkowski subsums. We also presented a lower
bound on the number of strict lower vertices of Minkowski sums of polytopes in
general orientations, which correspond to the bounded regions of maxout
arrangements. Our discussion connects the theoretical analysis of artificial
neural networks, tropical geometry, and geometric combinatorics. The results
that we have presented can serve as the basis for addressing several other
problems:

  * •

One possible extension of the results we presented here are explicit formulas
for the maximum number of faces of any dimensions or also for the number of
bounded faces. Explicit formulas for lower-dimensional faces are of particular
importance for the combinatorial complexity of tropical varieties [29], which
are intersections of tropical hypersurfaces, and consequently also for the
complexity of many algorithms in tropical geometry.

  * •

Further refining the bounds for deep networks is also an interesting endeavor
for future work. Even the case of ReLU networks is still the subject of
intense investigation. Another interesting avenue is the explicit number of
faces for specific families of non-simple arrangements, for example those that
one might obtain in convolutional networks or graph and simplicial networks,
which have been recently studied in the ReLU case [53, 8].

  * •

An interesting open problem is the estimation of the expected number of faces
for a given probability distribution over the parameters of shallow and deep
maxout networks. The case of ReLU networks was recently studied in [19, 20].
In shallow ReLU networks, any generic parameter gives rise to the maximum
number of regions (the number of regions of a generic hyperplane arrangement
or equivalently the number of upper vertices of a zonotope). In contrast, for
shallow maxout networks, generic choices of parameters can result in different
numbers of regions. The expected number of regions of a single maxout unit
with Gaussian weights corresponds to the number of (upper) vertices of a
Gaussian polytope, which has been studied in the literature [25]. However, for
a maxout layer one would need to consider Minkowski sums of random polytopes,
which to our knowledge have not yet been studied.

  * •

A further aspect of interest is the development of parameter initialization
strategies that would allow for faster optimization or better algorithmic
biases when training maxout networks. We have presented ways to select
parameters that lead to the maximum number of regions for shallow maxout
networks and to asymptotically maximal number of regions for deep maxout
networks. Other properties of the initialization that can be considered
include the normalization of the activation values across layers and the
distribution of linear regions over the space of inputs. Related aspects for
the case of ReLU networks have been studied in [23, 18, 46, 27, 58].

### Acknowledgment

We are grateful to both Raman Sanyal and especially Karim Adiprasito for
discussing their Upper Bound Theorem for Minkowski Sums with us. Guido
Montúfar has been supported by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant no
757983). Yue Ren has been supported by UK Research and Innovation (UKRI) under
the Future Leaders Fellowship programme (grant noMR/S034463/1).

## References

  * [1] K. A. Adiprasito.  Lefschetz and lower bound theorems for Minkowski sums.  arXiv:1711.07218, 2017.
  * [2] K. A. Adiprasito and R. Sanyal.  Relative Stanley–Reisner theory and upper bound theorems for Minkowski sums.  Publications mathématiques de l’IHÉS, 124(1):99–163, 2016\.
  * [3] M. Alfarra, A. Bibi, H. Hammoud, M. Gaafar, and B. Ghanem.  On the decision boundaries of deep neural networks: A tropical geometry perspective.  arXiv:2002.08838, 2020.
  * [4] F. Ardila and M. Develin.  Tropical hyperplane arrangements and oriented matroids.  Mathematische Zeitschrift, 262(4):795–816, 2009.
  * [5] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee.  Understanding deep neural networks with rectified linear units.  In International Conference on Learning Representations, 2018.
  * [6] R. Balestriero, R. Cosentino, B. Aazhang, and R. Baraniuk.  The geometry of deep networks: Power diagram subdivision.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 15832–15841. Curran Associates, Inc., 2019.
  * [7] P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian.  Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks.  Journal of Machine Learning Research, 20(63):1–17, 2019.
  * [8] C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. Montúfar, P. Lió, and M. Bronstein.  Weisfeiler and lehman go topological: Message passing simplicial networks.  In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1026–1037. PMLR, 18–24 Jul 2021.
  * [9] R. C. Buck.  Partition of space.  The American Mathematical Monthly, 50(9):541–544, 1943.
  * [10] V. Charisopoulos and P. Maragos.  A tropical approach to neural networks with piecewise linear activations.  arXiv:1805.08749, 2018.
  * [11] O. Delalleau and Y. Bengio.  Shallow vs. deep sum-product networks.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, pages 666–674. Curran Associates, Inc., 2011.
  * [12] R. Eldan and O. Shamir.  The power of depth for feedforward neural networks.  In V. Feldman, A. Rakhlin, and O. Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 907–940. PMLR, 2016.
  * [13] X. Glorot, A. Bordes, and Y. Bengio.  Deep sparse rectifier neural networks.  In G. Gordon, D. Dunson, and M. Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 315–323, Fort Lauderdale, FL, USA, 2011. PMLR.
  * [14] I. Goodfellow, D. Warde-Farley, M. Mirza, A. Courville, and Y. Bengio.  Maxout networks.  In S. Dasgupta and D. McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1319–1327, Atlanta, Georgia, USA, 2013. PMLR.
  * [15] C. Greene and T. Zaslavsky.  On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs.  Transactions of the American Mathematical Society, 280:97–126, 1983\.
  * [16] P. Gritzmann and B. Sturmfels.  Minkowski addition of polytopes: Computational complexity and applications to Gröbner bases.  SIAM Journal on Discrete Mathematics, 6(2):246–269, 1993.
  * [17] B. Grünbaum.  Arrangements of Hyperplanes, pages 432–454.  Springer New York, New York, NY, 2003.
  * [18] B. Hanin and D. Rolnick.  How to start training: The effect of initialization and architecture.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [19] B. Hanin and D. Rolnick.  Complexity of linear regions in deep networks.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2596–2604, Long Beach, California, USA, 2019. PMLR.
  * [20] B. Hanin and D. Rolnick.  Deep ReLU networks have surprisingly few activation patterns.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 361–370. Curran Associates, Inc., 2019\.
  * [21] J. Håstad.  Almost optimal lower bounds for small depth circuits.  In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, page 6–20, New York, NY, USA, 1986. Association for Computing Machinery.
  * [22] J. Håstad and M. Goldmann.  On the power of small-depth threshold circuits.  Computational Complexity, 1(2):113–129, 1991.
  * [23] K. He, X. Zhang, S. Ren, and J. Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE International Conference on Computer Vision, pages 1026–1034, 2015.
  * [24] P. Hinz and S. van de Geer.  A framework for the construction of upper bounds on the number of affine linear regions of ReLU feed-forward neural networks.  IEEE Transactions on Information Theory, 65(11):7304–7324, 2019\.
  * [25] D. Hug, G. O. Munsonius, and M. Reitzner.  Asymptotic mean values of Gaussian polytopes.  Beiträge zur Algebra und Geometrie, 45:531–548, 2004.
  * [26] M. Jaggi, G. Katz, and U. Wagner.  New results in tropical discrete geometry.  http://www.m8j.net/math/TropicalDiscreteGeometry.pdf.
  * [27] H. Jin and G. Montúfar.  Implicit bias of gradient descent for mean squared error regression with wide neural networks.  arXiv:2006.07356, 2020.
  * [28] M. Joswig.  Essentials of tropical combinatorics, volume 219.  Providence, RI: American Mathematical Society (AMS), 2021.
  * [29] M. Joswig and B. Schröter.  The degree of a tropical basis.  Proceedings of the American Mathematical Society, 146(3):961–970, 2017.
  * [30] M. I. Karavelas, C. Konaxis, and E. Tzanaki.  The maximum number of faces of the Minkowski sum of three convex polytopes.  In Proceedings of the Twenty-Ninth Annual Symposium on Computational Geometry, SoCG ’13, page 187–196, New York, NY, USA, 2013. Association for Computing Machinery.
  * [31] M. I. Karavelas and E. Tzanaki.  The maximum number of faces of the Minkowski sum of two convex polytopes.  Discrete Comput. Geom., 55(4):748–785, 2016.
  * [32] D. Maclagan and B. Sturmfels.  Introduction to tropical geometry, volume 161.  Providence, RI: American Mathematical Society (AMS), 2015.
  * [33] H. Mhaskar, Q. Liao, and T. Poggio.  When and why are deep networks better than shallow ones?  In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI’17, page 2343–2349. AAAI Press, 2017.
  * [34] G. Montúfar.  Notes on the number of linear regions of deep neural networks.  SampTA, 2017.  https://www.researchgate.net/publication/322539221_Notes_on_the_number_of_linear_regions_of_deep_neural_networks.
  * [35] G. Montúfar, R. Pascanu, K. Cho, and Y. Bengio.  On the number of linear regions of deep neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2924–2932. Curran Associates, Inc., 2014.
  * [36] Q. Nguyen, M. Mondelli, and G. Montúfar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks.  In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8119–8129. PMLR, 18–24 Jul 2021.
  * [37] R. Pascanu, G. Montúfar, and Y. Bengio.  On the number of response regions of deep feed forward networks with piece-wise linear activations.  In International Conference on Learning Representations 2014 (ICLR 2014), Banff, Alberta, Canada, 2013.
  * [38] M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, and J. Sohl-Dickstein.  On the expressive power of deep neural networks.  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2847–2854, International Convention Centre, Sydney, Australia, 2017. PMLR.
  * [39] R. T. Rockafellar.  Convex Analysis.  Princeton University Press, 1970.
  * [40] G.-C. Rota.  On the foundations of combinatorial theory I. Theory of Möbius functions.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2(4):340–368, 1964.
  * [41] T. Serra and S. Ramalingam.  Empirical bounds on linear regions of deep rectifier networks.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):5628–5635, 2020.
  * [42] T. Serra, C. Tjandraatmadja, and S. Ramalingam.  Bounding and counting linear regions of deep neural networks.  In ICML, volume 80 of Proceedings of Machine Learning Research, pages 4565–4573. PMLR, 2018.
  * [43] D. E. Speyer.  Tropical linear spaces.  SIAM Journal on Discrete Mathematics, 22(4):1527–1558, 2008.
  * [44] R. P. Stanley.  An introduction to hyperplane arrangements.  In Lecture notes, IAS/Park City Mathematics Institute, 2004.
  * [45] J. Steiner.  Einige Gesetze über die Theilung der Ebene und des Raumes.  Journal für die reine und angewandte Mathematik, 1:349–364, 1826\.
  * [46] I. Steinwart.  A sober look at neural network initializations.  arXiv:1903.11482, 2019.
  * [47] L. Szymanski and B. McCane.  Deep networks are effective encoders of periodicity.  IEEE Transactions on Neural Networks and Learning Systems, 25(10):1816–1827, 2014.
  * [48] M. Telgarsky.  Representation benefits of deep feedforward networks.  arXiv:1509.08101, 2015.
  * [49] M. Telgarsky.  Benefits of depth in neural networks.  In V. Feldman, A. Rakhlin, and O. Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517–1539, Columbia University, New York, New York, USA, 2016. PMLR.
  * [50] L. Van den Dries.  Tame Topology and O-minimal Structures.  London Mathematical Society Lecture Note Series 248. Cambridge University Press, 1998.
  * [51] S. Wang.  General constructive representations for continuous piecewise-linear functions.  IEEE Transactions on Circuits and Systems I: Regular Papers, 51(9):1889–1896, 2004.
  * [52] C. Weibel.  Maximal f-vectors of Minkowski sums of large numbers of polytopes.  Discrete Computational Geometry, 47:519–537, 2012.
  * [53] H. Xiong, L. Huang, M. Yu, L. Liu, F. Zhu, and L. Shao.  On the number of linear regions of convolutional neural networks.  In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10514–10523. PMLR, 2020.
  * [54] D. Yarotsky.  Error bounds for approximations with deep ReLU networks.  Neural Networks, 94:103–114, 2017.
  * [55] T. Zaslavsky.  Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes.  American Mathematical Society: Memoirs of the American Mathematical Society. American Mathematical Society, 1975.
  * [56] T. Zaslavsky.  A combinatorial analysis of topological dissections.  Advances in Mathematics, 25(3):267–285, 1977.
  * [57] L. Zhang, G. Naitzat, and L.-H. Lim.  Tropical geometry of deep neural networks.  In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5824–5832, Stockholmsmässan, Stockholm Sweden, 2018. PMLR.
  * [58] X. Zhang and D. Wu.  Empirical studies on the properties of linear regions in deep neural networks.  In International Conference on Learning Representations, 2020.
  * [59] G. M. Ziegler.  Lectures on polytopes.  Springer-Verlag, New York, 1995.