ResearchPod Summary
This paper investigates the computational power of "Scalar Tropical Circuits" (STCs)—a model of algebraic circuits that extends standard tropical (max-plus) circuits by allowing multiplication with positive constants. The authors aim to determine whether these additional gates significantly increase the expressivity of the model and what this implies for the size requirements of neural networks with convexity constraints, such as Input-Convex Neural Networks (ICNNs).
To analyze STCs, the authors move beyond standard tropical circuit techniques, which often rely on the assumption of integral coefficients. They utilize the duality between support functions and polytopes, developing a generalized decomposition lemma for Minkowski sums. By defining problem-specific measures, they show that any small STC must be composed of a limited number of "simple" Minkowski sums, which are insufficient to capture the complexity of the target polytopes (the Birkhoff polytope and the directed spanning tree polytope). This allows them to derive exponential lower bounds on the number of plus gates required.
This work clarifies the theoretical limits of convex and monotone neural networks. While ICNNs are popular for their interpretability and ability to incorporate prior knowledge, this paper proves that these benefits come at a potentially massive cost in model size. Furthermore, it bridges the gap between tropical circuit complexity and practical neural network architecture, suggesting that the inability to use negative weights (subtraction) is a fundamental bottleneck that cannot be bypassed by simply scaling inputs.
AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.