TLDR: A new research paper investigates sparse maxout networks, where neurons have fixed input connections (indegree constraint) and use maxout activations. The study establishes a duality between functions computable by these networks and ‘virtual polytopes,’ using their geometry to analyze network expressivity. Key findings show that while deep sparse networks are universal, if sufficient depth is not reached, increasing network width cannot compensate for the expressivity limitations imposed by fixed indegree sparsity. This demonstrates that sparsity has a decisive and uncompensatable impact on what neural networks can represent.
Neural networks have achieved remarkable success in various applications, but a complete theoretical understanding of their inner workings, especially regarding their expressive power, remains an active area of research. A new study, titled On the expressivity of sparse maxout networks, delves into how network sparsity influences what these powerful computational models can learn and represent.
Understanding Sparse Maxout Networks
The research focuses on a specific type of neural network called ‘sparse maxout networks.’ In these networks, each neuron in a layer receives a fixed, limited number of inputs from the preceding layer. This is known as an ‘indegree constraint.’ Additionally, these neurons use ‘maxout’ activation functions, which are a generalized version of the widely used Rectified Linear Unit (ReLU) activations. This architecture is particularly relevant because it captures key characteristics of modern network types like convolutional neural networks (CNNs), which use localized kernels, and graph neural networks (GNNs), where connections are often constrained by graph structure.
The study investigates how this sparsity, or limited connectivity, interacts with other architectural parameters like network depth (number of layers) and width (number of neurons per layer). While previous research has shown that sufficiently deep networks can approximate any continuous function, this paper explores the exact class of functions that can be represented by these sparse architectures.
A Geometric Lens: Virtual Polytopes
A central innovation of this research is the establishment of a duality between the functions computable by sparse maxout networks and a mathematical concept called ‘virtual polytopes.’ Imagine functions as geometric shapes; this duality links the complexity and properties of these functions to the geometry of these virtual polytopes. By studying the ‘dimension’ of these virtual polytopes, the researchers gain insights into the expressivity of the networks. They derived a precise upper bound on this dimension and proved that this bound can actually be reached, making it a powerful tool for their analysis.
The Unyielding Impact of Sparsity
Building on this geometric understanding, the study constructs a sequence of ‘depth hierarchies.’ This means that as the network gets deeper, it can represent increasingly complex functions. While it’s true that sufficiently deep sparse maxout networks are ‘universal’—meaning they can, in theory, compute any continuous piecewise linear function—the paper reveals a critical limitation: if the network doesn’t reach the necessary depth, simply increasing its width (adding more neurons per layer) cannot compensate for the fixed indegree constraint. In simpler terms, a shallow but wide sparse network cannot always do what a sufficiently deep sparse network can, even if it has many more neurons.
One of the key findings is that for any fixed depth and indegree constraint, there are functions that a fully connected network (where every neuron connects to every input) can compute with just two hidden layers, but a sparse maxout network cannot, regardless of how wide it is. This highlights that sparsity imposes a fundamental restriction on a network’s expressive power that cannot be overcome by merely adding more neurons.
The researchers also provided a full characterization for a specific case where both the indegree constraint and the number of arguments in the maxout activation are fixed at two (d=r=2). This characterization further demonstrates a clear separation in what networks of different depths can represent.
Also Read:
- Boosting Reinforcement Learning Efficiency with Simplicial Embeddings
- Decoding AI’s Inner Workings: Introducing WeightLens and CircuitLens
Conclusion
This research underscores that sparsity is not just an efficiency measure but a decisive factor in the expressivity of neural networks. It shows that while depth can eventually lead to universal approximation, the architectural constraint of limited connections per neuron fundamentally restricts the class of functions a network can represent, and this restriction cannot be fully compensated by increasing the network’s width. This work provides valuable theoretical insights into the capabilities and limitations of sparse neural network architectures, which are prevalent in many practical applications.
