Technical Summary: Tropical Circuits with Scalar Multiplication Gates

Problem Statement

The paper investigates the computational power of Scalar Tropical Circuits (STCs), a model extending standard tropical (max-plus) circuits by allowing gates that perform multiplication by positive real constants. Standard tropical circuits use only max and + gates and are known to model pure dynamic programs. While it is established that neural networks (specifically ReLU and maxout networks) are strictly more powerful than tropical circuits—largely due to their ability to implement subtraction via negative weights—the specific contribution of scalar multiplication (without subtraction) to computational power remained an open question.

The central problem addressed is whether allowing scalar multiplication with positive constants significantly reduces the circuit size required to compute support functions of specific polytopes, particularly those with 0-1 coefficients (multilinear tropical polynomials). Specifically, the authors ask: Are there polytopes with polynomial extension complexity that require STCs of exponential size?

Methodology

1. Model Definition

The authors define an STC as a directed acyclic graph with three types of gates:

• Max gates: Compute $\max(u, w)$.
• Plus gates: Compute $u + w$.
• Scalar gates: Compute $\lambda u$ for a constant $\lambda \in \mathbb{R}_{>0}$.
  The size of an STC is defined as the number of max and + gates, excluding scalar gates.

2. Geometric Duality

The analysis relies on the duality between support functions and polytopes. An STC computing a function $f$ corresponds to constructing a polytope $P$ (the Newton polytope) such that $f$ is the support function of $P$.

• max gates correspond to the convex hull of the union of polytopes: $P_{max} = \text{conv}(P_u \cup P_w)$.
• + gates correspond to the Minkowski sum: $P_{+} = P_u + P_w$.
• Scalar gates correspond to dilation: $P_{\lambda} = \lambda P_u$.

3. Decomposition Lemma (General Lower Bound Strategy)

The core technical contribution is a generalized decomposition lemma (Lemma 3.5) adapted for STCs. Unlike standard tropical circuits where the Newton polytope has only integral vertices, STCs can generate polytopes with non-integral vertices.
The lemma states that if a polytope $Q$ is computed by an STC of size $t$, then $Q$ can be decomposed as:
$$Q = \text{conv}\left(A_0 \cup \bigcup_{i=1}^k (A_i + B_i)\right)$$
where $k \le t$, and the polytopes $A_i$ are "simple" with respect to a chosen measure $\mu$. The measure $\mu$ must satisfy sub-additivity properties under Minkowski sums and convex hulls.

4. Measure Selection

To prove lower bounds, the authors construct specific measures $\mu$ tailored to the target polytopes. The strategy involves showing that any decomposition of the form above requires a large number of summands ($k$) because a single Minkowski sum $A_i + B_i$ (where $A_i$ is "simple") can only contain a small fraction of the vertices of the target polytope.

Key Contributions and Results

1. Exponential Lower Bounds for STCs

The paper proves that scalar multiplication does not significantly reduce the size of circuits for two fundamental combinatorial optimization problems:

• The Birkhoff Polytope ($P_{PERM}$): The convex hull of perfect matchings in a complete bipartite graph $K_{n,n}$.

  • Result: Any STC computing the support function of $P_{PERM}$ requires $\Omega(2^n)$ plus gates (Theorem 1.1).
  • Context: While the extension complexity of $P_{PERM}$ is polynomial ($O(n^2)$), the STC size is exponential. This demonstrates that the lower bound based on extension complexity can be exponentially loose.

• The Directed Spanning Tree Polytope ($P_{DST}$): The convex hull of arborescences rooted at node $n$ in a complete directed graph.

  • Result: Any STC computing the support function of $P_{DST}$ requires $\Omega(2^n)$ plus gates (Theorem 1.2).
  • Context: This extends the classic result by Jerrum and Snir [JS82] for standard tropical circuits to the scalar case.

2. Separation of Monotone and Non-Monotone Neural Networks

The authors derive corollaries regarding the complexity of neural networks:

• Definitions:
  • $nnc(P)$: Minimum size of a rank-2 maxout network computing $f_P$.
  • $mnnc(P)$: Minimum size of a rank-2 maxout Input-Convex Neural Network (ICNN) (monotone weights allowed only on input edges) computing $f_P$.
• Corollary 1.3: $mnnc(P_{PERM}) \in 2^{\Omega(n)}$.
• Corollary 1.4: For the directed spanning tree polytope, $nnc(P_{DST}) \in O(n^3)$ (polynomial) while $mnnc(P_{DST}) \in 2^{\Omega(n)}$ (exponential).
• Significance: This establishes an exponential size separation between monotone (ICNN) and non-monotone neural networks. It proves that enforcing convexity constraints (as in ICNNs) can necessitate exponentially larger networks to represent the same functions compared to unrestricted networks.

3. Simulation of Monotone Networks by STCs

A crucial step in the proof is Lemma 3.3, which shows that a bias-free monotone rank-$k$ maxout network of size $s$ can be simulated by an STC of size $O(s^2)$. This allows the lower bounds derived for STCs to be transferred directly to monotone maxout networks.

Significance and Claims

The paper claims the following significance:

1. Limitations of Scalar Multiplication: It demonstrates that for functions with 0-1 coefficients (support functions of 0-1 polytopes), the ability to multiply by arbitrary positive scalars does not provide a significant advantage in terms of circuit size over standard tropical circuits.
2. Dynamic Programming Limits: The results imply that "pure" dynamic programs augmented with positive scalar multiplications still require exponentially many iterations to solve the maximum weight directed spanning tree and bipartite perfect matching problems.
3. Neural Network Theory: The work provides a rigorous theoretical justification for the observation that input-convex neural networks (ICNNs) often perform worse or require more resources than unrestricted models. It proves that for specific classes of functions (like those related to directed spanning trees), the restriction to monotone/convex architectures forces an exponential blow-up in network size.
4. Refinement of Lower Bound Techniques: The paper introduces a polytopal decomposition technique that handles non-integral vertices, generalizing previous methods used for arithmetic and tropical circuits.

Limitations and Open Questions

The authors modestly note that while they prove exponential lower bounds, the constants in the exponents are weaker than those for standard tropical circuits (e.g., $2^{0.918n}$ vs $2^n$ for the Birkhoff polytope). They also highlight that it remains an open question whether polynomial-size STCs exist for the undirected spanning tree polytope, as the techniques used for the directed case rely on combinatorial structures that may not persist with scalar multiplications. Furthermore, the question of whether polynomial-size (max, +, -) circuits exist for the permanent (and thus whether $nnc(P_{PERM})$ is polynomial) remains open.