On the expressivity of sparse maxout networks
This addresses theoretical limitations in neural network design, particularly for convolutional or graph neural networks, but is incremental as it builds on existing expressivity studies.
The paper tackles the expressivity of sparse maxout networks, linking them to virtual polytopes and proving that depth is essential for universality, with width insufficient to compensate for sparsity constraints.
We study the expressivity of sparse maxout networks, where each neuron takes a fixed number of inputs from the previous layer and employs a, possibly multi-argument, maxout activation. This setting captures key characteristics of convolutional or graph neural networks. We establish a duality between functions computable by such networks and a class of virtual polytopes, linking their geometry to questions of network expressivity. In particular, we derive a tight bound on the dimension of the associated polytopes, which serves as the central tool for our analysis. Building on this, we construct a sequence of depth hierarchies. While sufficiently deep sparse maxout networks are universal, we prove that if the required depth is not reached, width alone cannot compensate for the sparsity of a fixed indegree constraint.