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

2021/04/16 by Guido Montúfar, Yue Ren, Montúfar, Guido +3 · 6 citations
Computer Science · Engineering · Mathematics · #06A07 #14T15 #52B05 #68T07 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2104.08135

openalex publication_date 2021/04/16 · openalex created_date 2021/04/26 · openalex updated_date 2026/07/28

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.

Citations

• On the number of response regions of deep feed forward networks with\n piece-wise linear activations

Cited by

• Relu and softplus neural nets as zero-sum turn-based games
• The graph of implicit edge dependencies for indecomposability and beyond
• On the expressivity of sparse maxout networks
• Maxout Polytopes
• Constraining the outputs of ReLU neural networks
• Signed Minkowski decompositions of convex polygons into minimum simplices and factorization of max-plus functions

Related

• Maxout Polytopes
• Bounding and Counting Linear Regions of Deep Neural Networks
• Depth-Bounds for Neural Networks via the Braid Arrangement
• A Tropical Approach to Neural Networks with Piecewise Linear Activations
• Enumeration of max-pooling responses with generalized permutohedra