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

• URL: http://arxiv.org/abs/2104.08135v1
• Date: Fri, 16 Apr 2021 14:33:21 GMT
• Title: Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums
• Authors: Guido Mont\'ufar and Yue Ren and Leon Zhang
• Abstract summary: A rank-k maxout unit is a function computing the maximum of $k$ linear functions. We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units.
• Score: 1.1602089225841632
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  We first show that a three-layer neural network can be designed to approximate an indicator function over a compact set. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. We prove the universal approximation property of three-layer ReLU networks using our topological approach.
  arXiv  Detail & Related papers  (2023-05-25T14:17:15Z)
• Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes [3.0079490585515343]
  We show that $lceillog_(n)rceil$ hidden layers are indeed necessary to compute the maximum of $n$ numbers. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry.
  arXiv  Detail & Related papers  (2023-02-24T10:14:53Z)
• Enumeration of max-pooling responses with generalized permutohedra [39.58317527488534]
  Max-pooling layers are functions that downsample input arrays by taking the maximum over shifted windows of input coordinates. We characterize the faces of such polytopes and obtain generating functions and closed formulas for the number of vertices and facets in a 1D max-pooling layer depending on the size of the pooling windows and stride.
  arXiv  Detail & Related papers  (2022-09-29T17:45:54Z)
• On the Number of Regions of Piecewise Linear Neural Networks [16.78532039510369]
  Many feedforward neural networks (NNs) generate continuous and piecewise-linear (CPWL) mappings. The number of these so-called linear regions offers a natural metric to characterize the expressiveness of CPWL NNs. We introduce a complementary framework to estimate the average number of linear regions produced by a CPWL NN.
  arXiv  Detail & Related papers  (2022-06-17T08:17:28Z)
• Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks [11.338307976409707]
  The number of linear regions has been considered a good measure for the expressivity of neural networks with piecewise linear activation. We present some estimates for the number of linear regions of the classic graph convolutional networks (GCNs) with one layer and multiple-layer scenarios.
  arXiv  Detail & Related papers  (2022-06-01T04:32:23Z)
• Spectral embedding and the latent geometry of multipartite networks [67.56499794542228]
  Many networks are multipartite, meaning their nodes can be divided into partitions and nodes of the same partition are never connected. This paper demonstrates that the node representations obtained via spectral embedding live near partition-specific low-dimensional subspaces of a higher-dimensional ambient space. We propose a follow-on step after spectral embedding, to recover node representations in their intrinsic rather than ambient dimension.
  arXiv  Detail & Related papers  (2022-02-08T15:52:03Z)
• Deep neural network approximation of analytic functions [91.3755431537592]
  entropy bound for the spaces of neural networks with piecewise linear activation functions. We derive an oracle inequality for the expected error of the considered penalized deep neural network estimators.
  arXiv  Detail & Related papers  (2021-04-05T18:02:04Z)
• A General Computational Framework to Measure the Expressiveness of Complex Networks Using a Tighter Upper Bound of Linear Regions [13.030269373463168]
  The upper bound of regions number partitioned by a rec-tifier network, instead of the number itself, is a more practical measurement ofexpressiveness of a DNN. We propose a new and tighter up-per bound regions number for any network structures. Our experiments show our upper bound is tighterthan existing ones, and explain why skip connections and residual structures can improve network performance.
  arXiv  Detail & Related papers  (2020-12-08T14:01:20Z)
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks [70.15611146583068]
  We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) Our theory utilizes semi-infinite duality and minimum norm regularization.
  arXiv  Detail & Related papers  (2020-02-24T21:32:41Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.