Search papers, labs, and topics across Lattice.
This paper investigates tropical circuits equipped with scalar multiplication gates, establishing exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. The findings reveal a significant separation in expressiveness between monotone and non-monotone maxout neural networks, which have implications for the architecture of neural networks. Notably, it concludes that input-convex neural networks (ICNNs) may require exponentially more resources than their non-convex counterparts to achieve equivalent functionality.
Enforcing convexity in neural networks can lead to exponential increases in size without improving expressiveness.
We study tropical circuits with scalar multiplication gates, that is, algebraic circuits whose gates implement $\max$, $+$, or multiplication with a positive constant. For such circuits, we prove exponential size lower bounds for computing maximum weight directed spanning trees and maximum weight bipartite perfect matchings. As a corollary, we obtain an exponential size separation between monotone and non-monotone maxout neural networks, which generalize the popularly used ReLU neural networks. One conclusion from this is that neural network models with enforced convexity constraints, such as input-convex neural networks (ICNNs), sometimes need to be exponentially larger than their unrestricted counterparts in order to express the same functions.
