1 Introduction↩︎

A feedforward neural network is a directed, acyclic graph in which each vertex (neuron) defines a simple computation, usually a linear transformation composed with a scalar-valued, continuous and piecewise linear (CPWL) activation function. While a standard choice for the activation function is the rectified linear unit (ReLU) \(x\mapsto\max\{0,x\}\), in this paper we focus on the more general maxout networks. These allow to compute the maximum of constantly many linear functions at each neuron. As a result, the entire network computes a (potentially complex) CPWL function. One of the big challenges in the theoretical analysis of neural networks is to understand how many neurons one requires to exactly or approximately represent a given (CPWL) function. To the best of our knowledge, it is an open question whether there exists a family of CPWL functions, which we can evaluate in polynomial time, but which cannot be represented by polynomial-size neural networks.¹

The piecewise linear nature of the studied networks suggests to tackle such questions by means of polyhedral geometry, see, e.g., the recent survey by [1]. In fact, a similar problem to the question above used to be open for a long time in the context of linear programming, until [2] resolved it affirmatively: does there exist a polytope \(P\) over which we can optimize in polynomial time, but any linear programming formulation must have exponential size? This question can be formalized with the notion of extension complexity \(\mathop{\mathrm{xc}}(P)\), which describes the minimal number of facets of any polytope \(Q\) that projects onto \(P\). In this case, we call \(Q\) an extended formulation of \(P\). [2] proved that the matching polytope has exponential extension complexity even though the algorithm by [3] can be used to find the maximum weight matching or minimum weight perfect matching in polynomial time. Additionally, [4] proved that a couple of polytopes associated with NP-hard optimization problems like the traveling salesperson problem have exponential extension complexity. [2] and [4] received the Gödel Prize 2023 for their breakthrough results.

There is a direct translation between polytopes (as feasible sets of linear programs) and CPWL functions (represented by neural networks) through the notion of the support function \(f_P(c)=\max_{x\in P} c^\top x\) of a polytope \(P\). This (convex) CPWL function, which has one linear region for each vertex of \(P\), uniquely determines \(P\) via convex duality. Computing \(f_P(c)\) means determining the objective value when optimizing over \(P\) in \(c\)-direction. Each CPWL function \(f_P\) can be represented by a neural network [5], though the required number of neurons can be large. To quantify this, we define the neural network complexity \(\mathop{\mathrm{nnc}}(P)\) as the minimum number of neurons to represent \(f_P\) by a maxout neural network.

1.1 Our Contributions↩︎

The aim of this paper is to connect the world of extended formulations with the study of neural networks. A “dream result” in this direction would be to bound \(\mathop{\mathrm{xc}}(P)\) polynomially in \(\mathop{\mathrm{nnc}}(P)\). Then the breakthrough results on extension complexity would directly imply strong lower bounds on the size of neural networks. It turns out, however, that there is one feature of neural networks that seems to make the “dream result” difficult to obtain or maybe even wrong: namely the ability to use subtraction. There are two natural ways to circumvent this difficulty: either prove the “dream result” for a weaker version of neural networks, or prove it for a stronger version of extension complexity. We accomplish both of these variants in our paper.

Monotone and Input-Convex Neural Networks↩︎

A consequence of the discussion above is that, if we remove the ability to subtract within neural networks, we do indeed obtain our “dream result”, namely lower bounds through \(\mathop{\mathrm{xc}}(P)\). This leads to two different, but closely related neural network models: monotone [6] and input-convex neural networks (ICNNs; [7]). The former only allows nonnegative weights, therefore enforcing each neuron and the entire network to represent a monotone and convex function. The latter allows negative weights only on outgoing connections from the input neurons, therefore also enforcing the represented function to be convex, but no longer monotone.

Obviously, every network that is monotone in the sense defined above is also input-convex. In 3, we show that for computing monotone functions with maxout activations, ICNNs are not more efficient than monotone networks. So, in this case, both models are equivalent. In analogy to \(\mathop{\mathrm{nnc}}(P)\), we define the monotone neural network complexity \(\mathop{\mathrm{mnnc}}(P)\) as the minimum number of neurons to represent \(f_P\) by a monotone network or an ICNN.² We then show that exponential lower bounds on \(\mathop{\mathrm{xc}}(P)\) imply corresponding lower bounds on \(\mathop{\mathrm{mnnc}}(P)\) and consequently on exact and approximate representations with monotone networks and ICNNs.

Studying these restricted types of neural networks is justified both from a theoretical and a practical perspective. From the theoretical perspective, it is a natural approach in complexity theory to prove lower bounds first for monotone models of computation, to circumvent some additional challenges of the general case; see, e.g., [8]. From the practical perspective, it is sometimes desirable or even necessary to incorporate prior knowledge about monotonicity and/or convexity of the target function into a machine learning model. For convexity, ICNNs have been used extensively for exactly this purpose after they were introduced by [7]; see, e.g., the literature overview in [9]. For monotonicity, we refer to [6] and the references therein for recent studies of monotone neural networks in the machine learning community.

Depending on whether similar lower bounds can also be established for general neural networks or not, our exponential lower bounds on monotone networks and ICNNs could indicate that these models might not be the best solution for enforcing convexity of a machine learning model. This aligns with some observations by [9].

Virtual Extension Complexity.↩︎

In order to pave the way towards lower bounds for general neural networks, we propose the notion of virtual extension complexity \[\mathop{\mathrm{vxc}}(P)=\min\{\mathop{\mathrm{xc}}(Q)+\mathop{\mathrm{xc}}(R)\mid \text{Q and R are polytopes with } P+Q=R\}\;,\] where \(P+Q=\{p+q\mid p\in P, q\in Q\}\) is the Minkowski sum. In this definition, \(P\) is a (formal) Minkowski difference of two polytopes \(Q\) and \(R\). Note that this is not the same as \(R + (-1)\cdot Q\) but rather the inverse operation of Minkowski addition. The name virtual extension complexity is derived from virtual polytopes [10], a framework for the algebraic study of formal Minkowski differences of polytopes. Observe that \(\mathop{\mathrm{vxc}}(P)\leq \mathop{\mathrm{xc}}(P)\) because we can always choose \(Q=\{0\}\) with \(\mathop{\mathrm{xc}}(\{0\})=0\). In that sense, virtual extension complexity is really a strengthening of the ordinary extension complexity.

In 4.1, we deduce that \(\mathop{\mathrm{vxc}}(P)\) is indeed a lower bound for \(\mathop{\mathrm{nnc}}(P)\), up to a constant factor. This leaves the open question to find ways to lower-bound \(\mathop{\mathrm{vxc}}(P)\) in order to achieve the original goal to lower-bound \(\mathop{\mathrm{nnc}}(P)\). To this end, it seems to be crucial to generally obtain a better understanding of the complexity measure \(\mathop{\mathrm{vxc}}(P)\) and its relation to \(\mathop{\mathrm{xc}}(P)\). Observe that \(P+Q=R\) is equivalent to \(f_P=f_R-f_Q\) pointwise. Therefore, intuitively, in order to optimize over \(P\), one only needs to optimize over \(R\) and \(Q\) and subtract the results. We make this intuition formal in 4.2, implying that small extended formulations for \(Q\) and \(R\) are sufficient to optimize efficiently over \(P\). Furthermore, in 4.3, we provide a class of examples with \(P+Q=R\) demonstrating that \(\mathop{\mathrm{xc}}(R)\) can be much smaller than \(\mathop{\mathrm{xc}}(P)\). This gives important insights on how extension complexity behaves under Minkowski sum and implies that we really need to look at both \(\mathop{\mathrm{xc}}(Q)\) and \(\mathop{\mathrm{xc}}(R)\) in order to lower-bound \(\mathop{\mathrm{vxc}}(P)\).

Overall, we now have four different ways to represent a polytope or its support function through (virtual) extended formulations and (monotone) neural networks. 1 shows what we know about how the associated complexity measures \(\mathop{\mathrm{xc}}(P)\), \(\mathop{\mathrm{vxc}}(P)\), \(\mathop{\mathrm{nnc}}(P)\), and \(\mathop{\mathrm{mnnc}}(P)\) relate to each other.

1.2 Further Related Work↩︎

In this paper our lever to prove lower bounds on neural networks are combinatorial optimization problems. Complementing upper bounds were established by [11] for minimum spanning trees and maximum flows. Furthermore, [12] proved similar upper bounds for the knapsack problem, even though they are different in flavor because some integrality assumptions are made.

Concerning the general expressivity of (piecewise linear) neural networks, the celebrated universal approximation theorems state that a single layer of neurons is sufficient to approximate any continuous function on a bounded domain; see [13] for the original version for sigmoid activation functions and [14] for a version that encompasses ReLU. However, such shallow neural networks usually require a large number of neurons. A sequence of results demonstrates that deeper networks sometimes require exponentially fewer neurons to represent the same functions; see, e.g., [5], [15], [16]. While these works contain exponential lower bounds on the size of neural networks, they are focused on shallow networks. In contrast, we aim to prove lower bounds regardless of the depth.

In terms of exact representation, it is known that a function can be represented if and only if it is CPWL [5], and it is still an open question whether constant depth is sufficient to do so [17]–[20]. Interestingly, also for this question, monotone networks seem to be more amenable for proving lower bounds than their non-monotone counterparts [21], [22]. Furthermore, the related question of how to efficiently write a non-convex CPWL function as a difference of two convex ones received quite some attention recently [23], [24].

We would like to emphasize that we view neural networks as a model of real-valued computation, as opposed to binary models of computation like Boolean circuits and Turing machines. In fact, if one restricts the inputs of a neural network to be binary, it is not too difficult to simulate AND-, OR-, and NOT-gates [25]. Thus, in such a binary model, every problem in P can be solved with polynomial-size neural networks. However, such networks would usually be very sensitive to single bits in the input. This is undesirable for practical neural networks and makes it impossible to transform these constructions naturally into exact or approximate neural networks in the real-valued model, compare the discussion by [11]. The more useful connection to circuit complexity is through arithmetic [26], and in particular tropical circuits [27], which are also real-valued models of computation. Again we refer to [11] for a more detailed discussion.

In fact, the extension complexity has been related before to Boolean and arithmetic circuits, see [28], [29]. This is also related to the proof that the permutahedron has extension complexity \(\mathcal{O}(n\log n)\) [30], as this goes via sorting networks, which can be seen as a very specific version of a piecewise-linear arithmetic circuit.

2 Preliminaries↩︎

Polyhedra and Polytopes.↩︎

A polyhedron \(P\) is a finite intersection of halfspaces \(P=\{x\in\mathbb{R}^d\mid Ax\leq b\}\); the representation as such an intersection is called \(H\)-representation. The affine hull of \(P\) is the smallest affine subspace containing \(P\) and the dimension \(\dim(P)\) is defined as the dimension of its affine hull. A face \(F\) of \(P\) is the set of maximizers over \(P\) with respect to a linear objective function: \(F=\arg\max \{c^\top x\mid x\in P\}\) for some \(c \in \mathbb{R}^d\). Faces of polyhedra are polyhedra themselves. Zero-dimensional faces are called vertices. Faces of dimension \(\dim(P) - 1\) are called facets; let \(h(P)\) be the number of such facets of \(P\). The minimal \(H\)-representation contains precisely one inequality for each facet and potentially a bunch of equalities to describe the affine hull of \(P\).

If \(P\) is bounded, it is also called a polytope. By the Minkowski-Weyl theorem, a polytope \(P\) can equivalently be written as convex hull of finitely many points. The inclusion-wise minimal such representation is precisely the convex hull of the vertices \(V(P)\), the \(V\)-representation. We set \(v(P) = \lvert V(P)\rvert\).

Each of \(V\)- and \(H\)-representation of a polytope can be exponentially smaller than the other one. For example, the \(d\)-dimensional cube \(\{x\in \mathbb{R}^d\mid \lVert x \rVert_\infty \leq 1\}\) has \(2^d\) vertices but only \(2d\) facets. On the other hand, the \(d\)-dimensional cross-polytope \(\{x\in \mathbb{R}^d\mid \lVert x \rVert_1 \leq 1\}\) has only \(2d\) vertices, but \(2^d\) facets. Standard references for polytope theory are [31], [32].

Extended Formulations.↩︎

Sometimes, a more compact way of representing a polyhedron \(P\) can be obtained by representing it as the projection of a higher-dimensional polyhedron \(Q\subseteq\mathbb{R}^{e}\) with \(e\geq d\). Such a polytope \(Q\) with \(\pi(Q)=P\) for an affine projection \(\pi\) is called an extended formulation of \(P\subseteq\mathbb{R}^d\). The extension complexity of \(P\) is defined as \(\mathop{\mathrm{xc}}(P)=\min\{h(Q)\mid \pi(Q)=P\}\). The extension complexity is upper bounded by \(\min\{v(P),h(P)\}\), but can be exponentially smaller. For example, the spanning tree polytope of a graph with \(n\) vertices has extension complexity \(\mathcal{O}(n^3)\) [33], but the polytope itself has exponentially many vertices and facets in \(n\). See [34] for a (not very recent) survey on extended formulations.

Support Functions.↩︎

For a polytope \(P\subseteq \mathbb{R}^d\), its support function \(f_P \colon \mathbb{R}^d \to \mathbb{R}\) is defined as \(f_P(c)=\max_{x\in P} c^\top x\). In other words, it maps a linear objective direction to the optimal value obtained by optimizing over the polytope. Support functions are convex, continuous, piecewise linear, and positively homogeneous functions; and every function with these properties is a support function of a polytope. Here, a function \(f \colon \mathbb{R}^d \to \mathbb{R}\) is positively homogeneous if \(f(\lambda x)=\lambda f(x)\) for all scalars \(\lambda\geq 0\). Let \(\mathcal{F}^d\) be the set of all such functions from \(\mathbb{R}^d\to\mathbb{R}\) and let \(\mathcal{P}^d\) be the set of all polytopes embedded in \(\mathbb{R}^d\). Then the map \(\mathcal{P}^d\to\mathcal{F}^d\), \(P\mapsto f_P\), is a bijection that is compatible with a certain set of operations:

(i) \(f_{P+Q} = f_P + f_Q\), where the “+” on the left-hand side is Minkowski sum;

(ii) \(f_{\lambda P} = \lambda f_P\) for \(\lambda\geq 0\), where \(\lambda P = \{\lambda p\mid p\in P\}\) is the dilation of \(P\) by \(\lambda\);

(iii) \(f_{\mathop{\mathrm{conv}}(P\cup Q)} = \max\{f_P, f_Q\}\).

The inverse map that maps a support function \(f_P\) to its unique associated polytope \(P\) is well-studied in tropical geometry. In fact, borrowing the name from (tropical) polynomials, we call \(P\) the Newton polytope of \(f_P\). The connection between CPWL functions and their Newton polytopes has previously been used in the study of neural networks and their expressivity [17], [18], [35]–[38].

Neural Networks.↩︎

For an introduction to neural networks, we refer to [39]. In this paper, we focus on so-called rank-\(k\) maxout neural networks for some natural number \(k\geq2\). They generalize the well-known neural networks with rectified linear unit (ReLU) activations. Such a neural network is based on a directed, acyclic graph with node set \(V\) and arcs \(A \subseteq V \times V\), where the nodes are called neurons and act as computational units. The \(d\geq1\) neurons with in-degree zero are called input neurons, all other \(s\geq1\) neurons are maxout units. We assume that among the maxout units there exists exactly one neuron with out-degree zero, the output neuron. All neurons that are neither input nor output neurons are called hidden neurons. The size of the neural network is defined as the number \(s\) of maxout units.

Each neuron \(v\) in the neural network defines a function \(z_v\colon\mathbb{R}^d\to \mathbb{R}\) as follows. Each input neuron \(v\) is associated with one element \(x_i\) of the input vector \(x\in\mathbb{R}^d\) and simply outputs \(z_v(x)=x_i\). Each maxout unit \(v\) comes with a tuple of weights \(w_{uv}^i\in\mathbb{R}\) for \(i=1,\dots,k\) and all \(u\in \delta^\mathrm{in}_v\), where \(\delta^\mathrm{in}_v\) is the set of in-neighbors of \(v\). The maxout neuron \(v\) represents the following expression dependent on the outputs of its in-neighbors: \[z_v=\max\Big\{\sum_{u\in\delta^\mathrm{in}_v} w_{uv}^i z_u \Bigm\vert i=1,\dots, k\Big\}\;,\] where \(k\) is called the rank of the maxout unit.

Finally, the output of the network is defined to be the output \(z_v\) for the output neuron \(v\). Note that our neural network represents a scalar-valued function as we assumed that there is only a single output neuron. A maxout network is called monotone if all weights of all maxout neurons are nonnegative [6]. It is called an input-convex neural network (ICNN) if negative weights are only allowed on arcs leaving an input neuron [7].

For a polytope \(P\), we define the neural network complexity \(\mathop{\mathrm{nnc}}(P)\) as the minimum size of a rank-\(2\) maxout network representing \(f_P\). Moreover, we define the monotone neural network complexity \(\mathop{\mathrm{mnnc}}(P)\) as the minimum size of a rank-\(2\) maxout ICNN representing \(f_P\). We will see that, if \(f_P\) is a monotone function, this exactly equals the minimum size of a monotone rank-\(2\) maxout network. While the previous use of the word ‘monotone’ was for neural networks, recall that a multivariate function is called monotone if, for \(x,y\in \mathbb{R}^d\), the componentwise inequality \(x\leq y\) implies \(f(x)\leq f(y)\).

3 Lower Bounds for Monotone and Input-Convex Neural Networks↩︎

The goal of this section is to prove the following theorem and use it to derive exponential lower bounds on monotone and input-convex neural networks.

Before we dive into proving 3, however, we argue that for computing a monotone function, monotone and input-convex maxout networks are equally efficient.

Observe that the support function \(f_P\) of a polytope \(P\) is monotone if and only if \(P\) is contained in the nonnegative orthant \(\mathbb{R}_{\geq0}^d\). 4 implies that for the definition of \(\mathop{\mathrm{mnnc}}(P)\) of a polytope \(P\in\mathbb{R}_{\geq0}^d\), it does not matter whether we use monotone or input-convex neural networks.

We now prove 3 in two steps, represented by the next two propositions. The first proposition shows that small ICNNs imply small extended formulations of the epigraph. For a convex CPWL function, the epigraph is the polyhedron \(\mathop{\mathrm{epi}}(f)=\{(x,t)\in\mathbb{R}^d\times\mathbb{R}\mid t\geq f(x)\}\). The proposition is related to earlier works connecting the extension complexity to Boolean and arithmetic circuit complexity, see e.g., [28], [29]. A similar statement also appears in the paper introducing ICNNs, where [7] prove that ICNN inference can be written as a linear program.

The second ingredient for proving 3 is that the extension complexity of a polytope equals the extension complexity of the epigraph of its support function. This is related to other previous results about the extension complexity being (almost) preserved under various notions of duality, see, e.g., [33], [40], [41].

Now we are ready to prove 3.

Now we apply 3 to obtain strong lower bounds on monotone and input-convex neural networks based on known bounds on the extension complexity. For a complete graph \((V,E)\) with \(n\) vertices and a weight vector \(c=(c_e)_{e\in E} \in \mathbb{R}^E\), let \(f_{\mathrm{MAT}}(c)\) be the value of a maximum weight matching and \(f_{\mathrm{TSP}}(c)\) the value of a longest³ traveling salesperson (TSP) tour with respect to \(c\). We denote the matching polytope by \(P_{\mathrm{MAT}}\) and the TSP polytope by \(P_{\mathrm{TSP}}\).

In the same way, one can prove lower bounds for neural networks computing the support function of any polytope with high extension complexity, e.g., for neural networks solving the MAX-CUT problem or the stable set problem. The corresponding lower bounds on the extension complexity were first proven by [4], who also derived that the extension complexity of the TSP polytope is at least \(2^{\Omega(\sqrt{n})}\), before [2] improved it to \(2^{\Omega(n)}\).

We would like to explicitly highlight one additional result building on the following, which we will use again later.

In fact, the proof of this theorem in [44] shows that almost all matroid base polytopes must have exponential extension complexity. With 3 and 4, we get the following implication. For a family of matroids \(M_n\) on \(n\) elements and a weight vector \(c\in\mathbb{R}^n\), let \(f_n(c)\) be the value of the maximum weight basis in \(M_n\).

For machine learning applications, it is arguably less important to obtain neural networks that exactly represent a given function. Instead, approximating the desired output is often sufficient. We demonstrate that also in the approximate setting, lower bounds on the extension complexity can be transferred to neural networks. We would like to emphasize that there exist many different ways to define what it means to approximate a given function or problem “sufficiently well”, both in optimization and machine learning. The “correct” notion always depends on the context. See also [38] for a discussion of how approximations can be translated between polytopes and neural networks.

In particular, monotone and input-convex neural networks cannot serve as fully-polynomial approximation schemes for the matching problem, in the sense that they cannot have polynomial size in both \(n\) and \(1/\epsilon\) to approximate the matching problem to \(\epsilon\)-precision. We understand 11 as a prototype for the fact that, in principle, inapproximability results from extended formulations can be transferred to neural networks. See, e.g., a framework for such lower bounds in [47] and inapproximability up to a factor \(2\) for vertex cover in [48].

4 Virtual Extension Complexity↩︎

In this section, we study the novel concept of virtual extension complexity \(\mathop{\mathrm{vxc}}(P)\). We first prove that \(\mathop{\mathrm{vxc}}(P)\) lower-bounds the size of general neural networks, motivating the study of \(\mathop{\mathrm{vxc}}(P)\) from a machine learning perspective. We then argue that, even though virtual extended formulations are more general than the ordinary extended formulations, they can still be used to optimize efficiently via linear programming, motivating the study of \(\mathop{\mathrm{vxc}}(P)\) from a combinatorial optimization perspective. Finally, we give an example demonstrating that Minkowski sum can indeed drastically reduce the extension complexity. More precisely, there exist polytopes \(P+Q=R\) with \(\mathop{\mathrm{xc}}(R)\) being way smaller than \(\mathop{\mathrm{xc}}(P)\). This means that for obtaining useful lower bounds on \(\mathop{\mathrm{vxc}}(P)\), we indeed need to look at both, \(\mathop{\mathrm{xc}}(Q)\) and \(\mathop{\mathrm{xc}}(R)\), and cannot just focus on \(\mathop{\mathrm{xc}}(R)\).

4.1 Neural Networks are Virtual Extended Formulations↩︎

We prove the following theorem stating that neural network sizes can be lower-bounded through virtual extension complexity.

The proof of this theorem requires three steps, two of which are already available through [prop:xcepi,prop:xcdual]. In addition, we need another proposition showing that every maxout network can be written as the difference of two monotone maxout networks each of which has the same size as the original network. This is related to writing functions represented by neural networks as tropical rational functions [35], [37].

4.2 Optimizing over Virtual Extended Formulations↩︎

One of the main reasons to study extension complexity is that it quantifies how well a given problem can be formulated as a linear program. Once we have a small-size extended formulation for a polytope \(P\), we can efficiently optimize over \(P\) by solving a single linear program. In this section, we argue that virtual extension complexity allows a natural progression of this idea: it describes the power of differences of two linear programs. Once we have a small-size virtual extended formulation for a polytope \(P\), we can optimize efficiently over \(P\) by solving two linear programs.

To this end, assume that we have polytopes \(P+Q=R\) with small extended formulations for \(Q\) and \(R\). Switching to support functions implies that for all objective directions \(c\in\mathbb{R}^d\) we obtain \(\max_{x\in P} c^\top x +\max_{x\in Q} c^\top x =\max_{x\in R} c^\top x\). Thus, to obtain the optimal objective value, it is sufficient to have small extended formulations for \(Q\) and \(R\), as we can really just optimize over \(Q\) and \(R\) and subtract the results. We now argue that this is basically also true for the solution itself.

The proof is based on the following fact about faces of Minkowski sums, which can be found, e.g., in [31].

14 implies that, for generic objective directions \(c\), we can efficiently find the optimal solution within \(P\) by linear programming using small extended formulations for \(Q\) and \(R\). However, the situation becomes more tricky if multiple optimal solutions exist within \(R\), and then potentially also within \(Q\). Indeed, in this case we would not know which of the optimal solutions we should subtract in order to obtain a solution that is feasible for \(P\). Therefore, we need to be more careful to handle non-generic objective functions \(c\). One solution would of course be to randomly perturb the objective function \(c\) by a tiny amount such that the optimal solution in \(R\) becomes unique. In practice, however, it is not clear how to ensure that the perturbation is actually small enough and generic enough at the same time.

The key idea is that we need to make sure that ties between equally good solutions are broken consistently across \(Q\) and \(R\). Therefore, we suggest a deterministic procedure based on a lexicographic objective function, which is a standard notion in multi-criteria optimization. By this, we mean a sequence of objective functions where later entries are only considered to break ties.

This lays the basis for [alg:optvirtextform].

4.3 Extension Complexity and Minkowski Sums↩︎

For a better understanding of virtual extension complexity, the behavior of extension complexity under Minkowski sum is crucial. It is well-known that \(xc(R) \leq xc(P) + xc(Q)\) for \(P + Q = R\). This follows from plugging the extended formulations for \(P\) and \(Q\) into the definition of the Minkowski sum. However, for bounding virtual extension complexity, one would need to bound \(\mathop{\mathrm{xc}}(P)\) in terms of \(\mathop{\mathrm{xc}}(Q)\) and \(\mathop{\mathrm{xc}}(R)\). In the following, we present a class of examples demonstrating that one cannot simply focus on \(\mathop{\mathrm{xc}}(R)\) for this, but also needs to take \(\mathop{\mathrm{xc}}(Q)\) into account.

Recall that the regular permutahedron for \(n \in \mathbb{N}\) is the polytope \[\Pi_n = \mathop{\mathrm{conv}}\{ (\sigma(1),\sigma(2),\ldots,\sigma(n)) \mid \sigma \text{ is a permutation of }\{1,\dots,n\}\}\] arising as the convex hull of all permutations of the vector \((1,2,\ldots,n)\). The regular permutahedron has the property that all edge directions are of the form \(e_i - e_j\) for two unit vectors \(e_i, e_j\). More generally, polytopes fulfilling this form the class of generalized permutahedra. A different characterization is in terms of Minkowski sums: a polytope \(P\) is a generalized permutahedron if and only if there is a polytope \(Q\) with \(P + Q = \lambda\cdot \Pi_n\) for some \(\lambda\geq0\), see [49]. It turns out that every matroid base polytope is such a generalized permutahedron, and we can even choose \(\lambda=1\) in this case [50], [51].

Hence, we can apply 9 to deduce a statement about summands of \(\Pi_n\).

Considering a matroid polytope \(P\) with high extension complexity from the latter proof such that \(P + Q = \Pi_n\) for some other generalized permutahedron \(Q\), we cannot exclude that \(Q\) has also high extension complexity. Therefore, without a better understanding of \(Q\), this does not yield any useful bound on \(\mathop{\mathrm{vxc}}(P)\).

On a final note, we would like to emphasize that in the definition of the virtual extension complexity, it is important that \(Q\) and \(R\) are polytopes and not potentially unbounded polyhedra. A simple example is given by the choice of \(Q=R=\mathbb{R}^d\), which would immediately imply \(\mathop{\mathrm{vxc}}(P)=0\) for any polyhedron \(P\), if it was allowed. The important algebraic property that we need to make sure that we can recover \(P\) from \(Q\) and \(R\) is the cancellation property: For polytopes \(A,B,C\), it is true that \(A+C=B+C\) implies \(A=B\). The same is not true for potentially unbounded polyhedra.

5 Conclusions↩︎

In this paper we focused on proving strong lower bounds for monotone and input-convex neural networks based on existing breakthrough results about extension complexity. Furthermore, we paved the way towards transferring these bounds to general neural networks by introducing the notion of virtual extension complexity and relating it to neural networks.

An obvious question for future research is a thorough analysis of how much more powerful general neural networks are compared to monotone or input-convex neural networks. Can we find a function for which there is an exponential gap in the required size?

Closely related, and from the perspective of polyhedral theory and combinatorial optimization, the most intriguing open question is: Can \(\mathop{\mathrm{vxc}}(P)\) be (much) smaller than \(\mathop{\mathrm{xc}}(P)\)? If the answer is no, then this would imply strong lower bounds on neural networks. On the other hand, if the answer is yes, it implies that solving two linear programs and taking the difference is (much) more powerful than just solving one linear program. In fact, we are not even aware of an example for which we can prove that \(\mathop{\mathrm{vxc}}(P)<\mathop{\mathrm{xc}}(P)\). On the other hand, as for the usual extension complexity, we do not expect \(\mathop{\mathrm{vxc}}(P)\) to be polynomial for any polytope \(P\) associated with an NP-hard optimization problem. An obvious, but seemingly challenging approach to lower-bound virtual extension complexity is to take any previously successful method for lower-bounding extension complexity and try to adapt it such that it also works in the virtual case.

To summarize, we hope that this paper inspires researchers to find out: Are two LPs better than one?

Acknowledgments↩︎

We thank Alex Black, Daniel Dadush, Jesús A. De Loera, Samuel Fiorini, Neil Olver, László Végh, Matthias Walter, and Stefan Weltge for insightful discussions around (virtual) extension complexity that have shaped this paper.

Part of this work was completed while Christoph Hertrich was affiliated with Université Libre de Bruxelles, Belgium, and received support by the European Union’s Horizon Europe research and innovation program under the Marie Skłodowska-Curie grant agreement No 101153187—NeurExCo.

References↩︎