Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
11/2021

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

Guido Montúfar, Yue Ren and Leon Zhang

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.

Received:
16.04.21
Published:
16.04.21
MSC Codes:
68T07, 52B05, 14T15, 06A07
Keywords:
linear regions of neural networks, upper bound theorem for Minkowski sums, hyperplane arrangement, tropical hypersurface arrangement, Newton polytope

Related publications

inJournal
2022 Repository Open Access
Guido Montúfar, Yue Ren and Leon Zhang

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

In: SIAM journal on applied algebra and geometry, 6 (2022) 4, pp. 618-649