1 Introduction↩︎

Continuous piecewise linear (CPWL) functions play a crucial role in optimization and machine learning. While they have traditionally been used to describe problems in geometry, discrete and submodular optimization, or statistical regression, they recently gained significant interest as functions represented by neural networks with rectified linear unit (ReLU) activations [2]. Extensive research has been put into understanding which neural network architectures are capable of representing which CPWL functions [3]–[6]. A major source of complexity in all the aforementioned fields is nonconvexity. Indeed, not only are nonconvex optimization problems generally much harder to solve than convex ones, but also for neural networks, nonconvexities are usually responsible for making the obtained representations complicated.

It is a well-known folklore fact that every (potentially nonconvex) CPWL function \(f\colon \mathbb{R}^n\to\mathbb{R}\) can be written as the difference \(f=g-h\) of two convex CPWL functions [7], [8]. Consequently, a natural idea to circumvent the challenges induced by nonconvexity is to use such a decomposition \(f=g-h\) and solve the desired problem separately for \(g\) and \(h\). This is the underlying idea of many successful optimization routines, known as DC programming (see survey by [9]), and also occurs in the analysis of neural networks [10], [11]. However, the crucial question arising from this strategy is: how much more complex are \(g\) and \(h\) compared to \(f\)? A well-established measure for the complexity of a CPWL function is the number of its linear pieces. Therefore, the main question we study in this article is the following.

There exist many ways in the literature to obtain decompositions into two convex functions, as we discuss later, but none of them guarantees minimality or at least a useful bound on the number of pieces of \(g\) and \(h\) depending on those of \(f\). In fact, no finite procedure is known that guarantees to find a minimal decomposition, despite a recent attempt by [1].

1.1 Our Contributions↩︎

In this article, we propose a novel perspective on 1 making use of polyhedral geometry and prove a number of structural results. We then apply our approach to existing decompositions in the literature, as well as to the theory of submodular functions and to the construction of neural networks representing a given CPWL function, serving as an additional motivation. Our detailed contributions are outlined as follows.

Decomposition Polyhedra.↩︎

After setting the preliminaries in 2 and introducing different ways to represent and study CPWL functions in 3, 4 presents our new polyhedral approach to 1. Instead of aiming for a globally optimal decomposition, we propose to restrict to solutions that are compatible with a given regular polyhedral complex \(\mathcal{C}\). In short, this means fixing where the functions \(g\) and \(h\) may have breakpoints, that is, points where they are not locally linear. We prove that the set of solutions to decompose \(f\) in a way that is compatible with \(\mathcal{C}\) is a polyhedron \(\mathcal{D}_{\mathcal{C}}(f)\) that arises as the intersection of two shifted polyhedral cones (5). We call this the decomposition polyhedron of \(f\) with respect to \(\mathcal{C}\). We prove several structural properties of \(\mathcal{D}_{\mathcal{C}}(f)\). Among them, we show that the bounded faces of \(\mathcal{D}_{\mathcal{C}}(f)\) are exactly those that cannot easily be simplified by subtracting a convex function (7), and we show that a minimal solution must be a vertex of \(\mathcal{D}_{\mathcal{C}}(f)\) (11). The latter implies a finite procedure to find a minimal decomposition among those that are compatible with \(\mathcal{C}\), by simply enumerating the (potentially many) vertices of \(\mathcal{D}_{\mathcal{C}}(f)\). It also implies that, if there is a unique vertex, then there is a unique minimal decomposition. We demonstrate that this is indeed the case for important CPWL functions, e.g., the median function, or those computed by a 1-hidden-layer ReLU network.

Translation to Virtual polytopes↩︎

In 5, we demonstrate that our framework naturally translates to the setting of virtual polytopes [12]. We explain how decomposing a positively homogeneous CPWL function corresponds to finding representatives of a virtual polytope as a Minkowski difference of two conventional polytopes. Our main results translate directly, showing that minimal representatives, those with the fewest vertices, must correspond to vertices of an analogous “representative polyhedron”.

Existing Decompositions.↩︎

Afterwards, in 6, we put our investigations into a broader context within the existing literature. We compare our minimality conditions with existing methods to construct decompositions. Notably, in this context, we refute a conjecture by [1], who provide an optimal construction method in dimension 2 and suggest that it might generalize to higher dimensions. However, we show that the construction does not generalize in the suggested way.

Applications to Submodular Functions.↩︎

In 7, we show that our framework entails the setup of set functions which are decomposed into differences of submodular set functions. Representing a set function as such a difference is a popular approach to solve optimization problems similarly to DC programming, see [13]–[15]. We apply our results from 4 to obtain analogous structural insights about (submodular) set functions (8).

Application to Neural Network Constructions.↩︎

Finally, in 8, we study the problem of constructing neural networks representing a given CPWL function. For convex CPWL functions, we blend two incomparable previous constructions by [6] and [4] to let the user freely choose a trade-off between depth and width of the constructed networks. We then apply the results of this paper to extend this to the nonconvex case by first decomposing the input function as a difference of two convex ones.

Limitations.↩︎

We emphasize that the focus of our paper is fundamental research by building a theoretical foundation to tackle 1 and connecting it with other fields. As such, our paper does not imply any direct improvement for a practical task, but it might prove helpful for that in the future. In particular, it is beyond the scope of our paper to provide any implementation of a (heuristic or exact) method to decompose a CPWL function into a difference of two convex ones. We consider it an exciting avenue for future research to do so, and to apply it to DC programming, discrete optimization, or neural networks.

On the theoretical side, the approach of fixing an underlying compatible polyhedral complex imposes some restriction on the set of possible solutions and can therefore be seen as a limitation. However, we think that this assumption is well justified by the structural properties this assumption allows us to infer and by the examples we demonstrate to fit into the framework. Even with this assumption, the problem remains very challenging.

1.2 Further Related Work↩︎

Explicit constructions to decompose CPWL functions as differences of convex CPWL functions can be found in several articles, such as [8], [16]–[18]. This was initiated in the \(1\)-dimensional case by [19], and already laid out for positively homogeneous functions in general dimensions by [7]. Typically, such decompositions are based on certain representations of CPWL functions, which have been constructed, e.g., in [20]–[22]; see also [23], [24] for a fresh perspective. These representations also help to understand the representative capabilities of neural networks, see [2], [4], [6].

Recently, a minimal decomposition for the \(2\)-dimensional case was given by [1]. They use a duality between CPWL functions and polyhedral geometry, based on the “balancing condition” from tropical geometry. This condition has already been studied by [25] in terms of weight spaces of polytopes. Generally, methods from tropical geometry have been successfully used to understand the geometry of neural networks [10], [26], [27]. In this context, a central open question is the required depth to exactly represent CPWL functions on \(\mathbb{R}^n\) [3], [5], [6], [28], [29].

Submodular functions are sometimes called the discrete analogue of convex functions, and optimizing over them is a widely studied problem, which is also relevant for machine learning. A submodular function can be minimized in polynomial time [30]. In analogy to DC programming, this sparked the idea of minimizing a general set function by representing it as a difference of two submodular ones [13]–[15]. Related decompositions were recently studied by [31]. In polyhedral theory, such a decomposition is equivalent to Minkowski differences of generalized permutahedra [32], [33].

Another closely related stream of work is concerned with the (exact and approximate) representative capabilities of neural networks, starting with universal approximation theorems [34], and specializing to ReLU networks, their number of pieces, as well as depth-width-tradeoffs [2], [35]–[37]. In addition, [11], [38], [39] provide neural network constructions and bounds for CPWL functions related to combinatorial optimization problems. Geometric insights have also proven to be useful to understand the computational complexity of tasks related to neural networks, like training and verification [40]–[44]. Recently, [45] give an explicit construction of how to efficiently approximate the maximum function with ReLU networks.

2 Preliminaries↩︎

In this section we introduce the necessary preliminaries on polyhedral geometry and CPWL functions; see [46] for more details.

2.1 Polyhedra and Polyhedral Complexes↩︎

For a vector \(a \in \mathbb{R}^{d}\) and a scalar \(b \in \mathbb{R}\), the hyperplane \[H_{a,b} \mathrel{\vcenter{:}}= \{x \in \mathbb{R}^d \mid \langle a,x \rangle+b=0\}\]subdivides \(\mathbb{R}^d\) into half-spaces \[H^{+}_{a,b} \mathrel{\vcenter{:}}= \{x \in \mathbb{R}^d \mid \langle a,x \rangle+b\geq 0\} \text{ and }H^{-}_{a,b} \mathrel{\vcenter{:}}= \{x \in \mathbb{R}^d \mid \langle a,x \rangle+b\leq0\}.\] A polyhedron \(P\) is the intersection of finitely many half-spaces and a polytope is a bounded polyhedron. A hyperplane supports \(P\) if it bounds a half-space containing \(P\), and any intersection of \(P\) with such a supporting hyperplane yields a face \(F\) of \(P\). For any direction \(u \in \mathbb{R}^d\), it holds that \(P^u \mathrel{\vcenter{:}}= \operatorname{argmax}\{\langle u,y \rangle \mid y \in P\}\) is a face of \(P\) and every face of \(P\) except for the empty face is of this form. A face is a proper face if \(F \subsetneq P\) and inclusion-maximal proper faces are referred to as facets. A polyhedral cone \(C \subseteq \mathbb{R}^d\) is a polyhedron such that \(\lambda u + \mu v \in C\) for every \(u,v \in C\) and \(\lambda, \mu \in \mathbb{R}_{\geq 0}\). The dual cone of \(C\) is \(C^\vee = \{y \in (\mathbb{R}^d)^* \mid \langle x,y \rangle\geq 0 \text{ for all } x \in C\}.\) A cone is pointed if it does not contain a line. A cone \(C\) is simplicial, if there are linearly independent vectors \(v_1,\ldots,v_k\in \mathbb{R}^d\) such that \(C=\{\sum_{i=1}^k\lambda_i v_i \mid \lambda_i \geq 0\}\). For a cone \(C\) and \(t \in \mathbb{R}^d\), we call \(t+C\) a shifted cone or translated cone. A ray \(\rho\) is a one-dimensional pointed cone; a vector \(r\) is a ray generator of \(\rho\) if \(\rho = \{\lambda\, r \mid \lambda \geq 0\}\). A ray \(\rho \subseteq C\) of a cone \(C\) is an extreme ray if there do not exist \(\lambda_1,\lambda_2 >0\) and distinct rays \(\rho_1,\rho_2 \subseteq C\) such that \(\rho = \lambda_1 \rho_1 + \lambda_2 \rho_2\). A polyhedral complex \(\mathcal{C}\) is a finite collection of polyhedra such that

1. \(\emptyset \in \mathcal{C}\)

2. if \(P \in \mathcal{C}\) then all faces of \(P\) are in \(\mathcal{C}\), and

3. if \(P, P' \in \mathcal{C}\), then \(P \cap P'\) is a face both of \(P\) and \(P'\).

For a polyhedral complex \(\mathcal{C}\) in \(\mathbb{R}^d\) and \(k \leq d\) we denote by \(\mathcal{C}^k\) the set of \(k\)-dimensional polyhedra in \(\mathcal{C}\). A polyhedral fan is a polyhedral complex in which every polyhedron is a cone. We call \(\mathcal{C}^{d-1}\) the facets of \(\mathcal{C}\) and \(\mathcal{C}^d\) the regions of \(\mathcal{C}\). The dimension of a complex \(\mathcal{C}\) is the maximal dimension of its polyhedra. A polyhedral complex \(\mathcal{C}\) in \(\mathbb{R}^d\) is called pure of dimension \(k\) if all its maximal polyhedra have dimension \(k\), and complete if the union of its polyhedra covers \(\mathbb{R}^d\). In this paper, we mainly consider pure and complete polyhedral complexes.

Given two \(d\)-dimensional polyhedral complexes \(\mathcal{C}, \mathcal{Q}\), the complex \(\mathcal{C}\) is a refinement of \(\mathcal{Q}\) if for every \(\tau \in \mathcal{C}^d\) there exists \(\sigma \in \mathcal{Q}^d\) such that \(\tau \subseteq \sigma\). The complex \(\mathcal{Q}\) is a coarsening of \(\mathcal{C}\) if \(\mathcal{C}\) is a refinement of \(\mathcal{Q}\). The star of a face \(\tau \in \mathcal{C}\) is the set of all faces containing \(\tau\), i.e., \(\operatorname{star}_{\mathcal{C}}(\tau) = \{\sigma \in \mathcal{C}\mid \tau \subseteq \sigma\}\). The support of a polyhedral complex \(\mathcal{C}\) is given by \(|\mathcal{C}|=\bigcup_{P \in \mathcal{C}} P\).

2.2 CPWL Functions↩︎

A function \(f\colon\mathbb{R}^d\to\mathbb{R}\) is called continuous and piecewise linear (CPWL)¹, if there exists a complete polyhedral complex \(\mathcal{C}\) such that the restriction of \(f\) to each polyhedron \(P\in\mathcal{C}\) is an affine linear function. If this condition is satisfied, we say that \(f\) and \(\mathcal{C}\) are compatible with each other. A vector \(x \in \mathbb{R}^d\) is a breakpoint of \(f\) if there is no open set \(U \subseteq \mathbb{R}^d\) containing \(x\) such that \(f\) is affine linear on \(U\). The breakpoints of \(f\) are contained in the union \(\bigcup_{\sigma \in \mathcal{C}^{d-1}} \sigma\) of facets of every complex \(\mathcal{C}\) compatible with \(f\). The restriction \(f_{|R}\) of the function \(f\) to a region \(R\) of \(\mathcal{C}\) is called a linear component of \(f\). The number of pieces of \(f\) is the smallest possible number of regions \(\#\mathcal{C}^d\) of a compatible polyhedral complex \(\mathcal{C}\). We denote by \(\operatorname{CPWL}_d\) the vector space of CPWL functions from \(\mathbb{R}^d\) to \(\mathbb{R}\).

If \(f\) is a convex CPWL function, then it can be written as the maximum of its linear components \(f(x)=\max_{i\in[k]} \langle a_i,x \rangle + b_i\). It follows that there is a unique coarsest compatible polyhedral complex \(\mathcal{C}_f\), namely the one with \[\mathcal{C}_f^d = \{\{x\in \mathbb{R}^d\mid \langle a_i,x \rangle + b_i = f(x) \}\mid i \in [k]\}.\] Hence, for convex functions, the number of pieces and the number of linear components coincides. We denote by \(\operatorname{CPWL}^+_d\) the cone of convex CPWL functions from \(\mathbb{R}^d\) to \(\mathbb{R}\). We call a polyhedral complex \(\mathcal{C}\) regular, if there exists a convex CPWL function \(f\) such that \(\mathcal{C}=\mathcal{C}_f\).

3 Different Perspectives on CPWL functions↩︎

In this section, we describe several ways to represent and study CPWL functions from a polyhedral perspective. First, we show that CPWL functions can be parameterized by encoding their local convexity or concavity at the facets of a compatible polyhedral complex, leading to the notion of a balanced complex. Positively homogeneous convex CPWL functions, in particular, correspond to polytopes, and the associated balanced fan is the normal fan of the polytope. This section develops these correspondences in more detail. Most of the results are classical in tropical geometry (see e.g. [47] and [48]) and already appear in [25], but sometimes we adapt them slightly to fit our setting.

3.1 CPWL Functions and Balanced Polyhedral Complexes↩︎

A pure \(d\)-dimensional polyhedral complex \(\mathcal{C}\) can be equipped with a weight function \(w : \mathcal{C}^{d-1} \to \mathbb{R}\), as we describe as follows. Given a face \(\sigma \in \mathcal{C}\), we denote by \(\operatorname{aff}(\sigma) \subseteq \mathbb{R}^d\) the unique smallest affine subspace containing \(\sigma\). The relative interior of \(\sigma\) is the interior of \(\sigma\) inside the affine space \(\operatorname{aff}(\sigma)\). For any dimension \(k\leq d\) and any \(\tau \in \mathcal{C}^{k-1},\sigma \in \mathcal{C}^{k}\) with \(\tau \subseteq \sigma\), let \(e_{\sigma/\tau} \in \mathbb{R}^d\) be the normal vector of \(\tau\) with respect to \(\sigma\), that is, the unique vector with length one that is parallel to \(\operatorname{aff}(\sigma)\), orthogonal to \(\operatorname{aff}(\tau)\), and points from the relative interior of \(\tau\) into the relative interior of \(\sigma\). A pair \((\mathcal{C},w)\) forms a (weighted) balanced polyhedral complex if the weight function satisfies the balancing condition at every \(\tau \in \mathcal{C}^{d-2}\): \[\label{eq:balancing-condition} \sum\limits_{\substack{\sigma \in \mathcal{C}^{d-1}: \\ \sigma \supset \tau}} w(\sigma)\cdot e_{\sigma/\tau}=0.\tag{1}\]

In the case where \(\mathcal{C}\) is a polyhedral fan in \(\mathbb{R}^2\), there is only one \(0\)-dimensional face, namely the origin. The balancing condition then requires that the weighted sum of the unit-length ray generators of the rays in \(\mathcal{C}\) equals the zero vector. In higher dimensions, taking the star of a codimension-\(2\) face \(\tau\) and modding out \(\tau\) yields a two-dimensional fan. Intuitively, the balancing condition requires that this two-dimensional fan is balanced in the same sense as described above, see 1 for an illustration.

Let \(\operatorname{Aff}(\mathbb{R}^d)\) be the space of affine functions from \(\mathbb{R}^d\) to \(\mathbb{R}\). For many of our arguments, adding or subtracting an affine function \(a\in \operatorname{Aff}(\mathbb{R}^d)\) does not change anything. In particular, a function \(f\) is convex if and only if \(f+a\) is convex. Therefore it makes sense to define the quotient space \(\overline{\mathcal{V}}_\mathcal{C}\mathrel{\vcenter{:}}=\mathcal{V}_\mathcal{C}/\operatorname{Aff}(\mathbb{R}^d)\), where we identify functions in \(\mathcal{V}_\mathcal{C}\) that only differ by adding an affine function. 1 and 2 imply that we can parameterize a function \(f \in \overline{\mathcal{V}}_\mathcal{C}\) by keeping track of “how convex or concave” the function is at the common face \(\sigma \in \mathcal{C}^{d-1}\) of two neighboring pieces, as we summarize in the following lemma.

In the following proposition, we prove that nonnegative (positive) weights in fact correspond to the function being (strictly) convex.

3.2 Duality and Newton Polytopes↩︎

In this section, we describe the duality between positively homogeneous convex CPWL functions and polytopes. The Minkowski sum of two polytopes \(P,Q \subseteq \mathbb{R}^d\) is defined as \(P+Q\mathrel{\vcenter{:}}=\{p+q:p\in P,q\in Q\}\).

A CPWL function \(f \colon \mathbb{R}^d \to \mathbb{R}\) is positively homogeneous if \(f(\lambda x) = \lambda f(x)\) for all \(x \in \mathbb{R}^d\) and \(\lambda \geq 0\). If \(f\) is convex, then it is positively homogeneous if and only if \(f(0)=0\), and \(\mathcal{C}_f\) is a polyhedral fan. In this case, it can be written as \(f(x) = \max_{i \in [k]} \langle x,a_i \rangle\), where \(a_i \in \mathbb{R}^d\). We define the Newton polytope of such a function \(f\) as the convex hull \(\operatorname{Newt}(f) = \operatorname{conv}(a_1,\dots,a_k)\). Conversely, the support function \(f_P\) of a polytope \(P\) is given by \(f_P(x) = \max_{y \in P} \langle y,x \rangle\). See 3 for an example.

We now give an interpretation of \(\mathcal{C}_f\) and \(w_f\) in terms of the Newton polytope. Given any \(d\)-dimensional polytope \(P \subset \mathbb{R}^{d}\), the (outer) normal cone of a \(k\)-dimensional face \(F\) of \(P\) is the \((d-k)\)-dimensional cone \[\label{eq:normal-cone} N_F(P) = \left\{x \in \mathbb{R}^{d} \;\middle| \;\langle z,x \rangle = \max_{y \in P} \langle y,x \rangle \text{ for all } z \in F \right\}.\tag{2}\] In particular, if \(P = \operatorname{Newt}(f)\) and \(v\) is a vertex of \(P\), then the description of the normal cone turns into \[N_v(\operatorname{Newt}(f)) = \left\{x \in \mathbb{R}^{d} \;\middle| \;\langle v,x \rangle = f(x) \right\},\] and agrees with a polyhedron in \(\mathcal{C}_f^d\). The normal fan of a polytope is the collection of normal cones over all faces. Thus, for positively homogeneous convex functions, the polyhedral complex \(\mathcal{C}_f\) agrees with the normal fan of \(\operatorname{Newt}(f)\), and the number of linear pieces of \(f\) equals the number of vertices of \(\operatorname{Newt}(f)\). An example is given in 3. The duality between \(\mathcal{C}_f\) and \(\operatorname{Newt}(f)\) also establishes a bijection between facets \(\sigma \in \mathcal{C}_f^{d-1}\) and edges of \(\operatorname{Newt}(f)\), and for the corresponding weight function \(w_f\) holds that \(w_f(\sigma)\) equals the Euclidean length of the edge that is dual to \(\sigma\). This correspondence extends to general convex CPWL functions, where \(\mathcal{C}_f\) is a complex which is dual to a regular polyhedral subdivision of \(\operatorname{Newt}(f)\), and \(w_f\) corresponds to lengths of edges in this subdivision (see e.g. [47]).

3.3 Deformation Cones↩︎

We call a polytope \(Q\) a deformation of a polytope \(P\) if there exists a polytope \(R\) and a scalar \(\lambda > 0\) such that \(\lambda P = Q + R\). Equivalently, \(Q\) is a deformation of \(P\) if and only if the normal fan of \(Q\) is a coarsening of the normal fan of \(P\).

The deformation cone \(\mathcal{DC}(P)\) of a polytope \(P\) consists of all its deformations, which can be parameterized by translation and edge lengths. Specifically, assign a nonnegative real value to each edge of \(P\) such that for all \(2\)-faces form actual polygons, that is, the balancing condition is met. The resulting polytope is a deformation of \(P\), and all deformations of \(P\) arise in this way. The linear condition that the edge lengths form polygons for the \(2\)-faces is equivalent to the condition that the corresponding weight function is balanced [25]. In other words, if we mod out translation, the deformation cone modulo translation \(\overline{\mathcal{DC}}(P)\) becomes a pointed polyhedral cone, isomorphic to \(\mathcal{W}^+_{\mathcal{C}}\) where \(\mathcal{C}\) is the normal fan of \(P\). The following lemma summarizes the discussion.

Although general positively homogeneous CPWL functions may not admit a Newton polytope due to potential concave folds (which would correspond to negative edge lengths), the isomorphism between Newton polytopes and positively homogeneous convex CPWL functions extends to a linear isomorphism through the notion of virtual polytopes, which are formal Minkowski differences of polytopes.

3.4 Virtual polytopes↩︎

We now review the notion of virtual polytopes adapted to our setting. For a thorough introduction to virtual polytopes, we refer to [12]. The set of polytopes \(\mathcal{P}_d\) in \(\mathbb{R}^d\) together with Minkowski addition forms a commutative semigroup, having the \(0\)-dimensional polytope that consists only of the zero vector as neutral element. For any polytopes \(P,Q,R \in \mathcal{P}_d\), there holds the cancellation law, which says that if \(P+Q=R+Q\), then \(P=R\). This allows to construct the Grothendieck group \(\mathcal{VP}_d \mathrel{\vcenter{:}}=\{(P, Q) : P, Q \in \mathcal{P}_d\} / \sim\) where the equivalence relation \(\sim\) is defined by \[(P_1, Q_1) \sim (P_2, Q_2) \iff P_1 + Q_2 = P_2 + Q_1.\] We write the equivalence class represented by \((P,Q)\) as \(P-Q\) and call it a virtual polytope. Every CPWL function \(f\) is the difference of two convex functions \(g-h\) and it is easy to check that the virtual polytope \(\operatorname{Newt}(g) - \operatorname{Newt}(h)\) is independent of the choice of convex functions \(g\) and \(h\) allowing to define \(\operatorname{Newt}(f) \mathrel{\vcenter{:}}= \operatorname{Newt}(g) - \operatorname{Newt}(h)\). The set of virtual polytopes is a vector space with the scalar multiplication given by \(\lambda (P-Q) \mathrel{\vcenter{:}}= \lambda P - \lambda Q\) which is isomorphic to the vector space \(\operatorname{CPWL}^0_d\) of positively homogeneous CPWL functions.

4 Decomposition Polyhedra↩︎

In this section, we introduce and generally study the main concept of this paper, decomposition polyhedra. These polyhedra describe the set of possible decompositions of a CPWL function \(f\) into a difference \(f=g-h\) that are compatible with a given polyhedral complex.

The projection \(\pi((g,h))=g\) induces an isomorphism between \(\mathcal{D}_{\mathcal{C}}(f)\) and \(\pi(\mathcal{D}_{\mathcal{C}}(f))\) since \(\mathcal{D}_{\mathcal{C}}(f) = \{(g,g-f) \mid g \in \pi(\mathcal{D}_{\mathcal{C}}(f)) \}.\) We now show that \(\mathcal{D}_{\mathcal{C}}(f)\) is indeed a polyhedron, which arises as the intersection of two shifted copies of a cone.

For the remainder of this section, we analyze the faces of the polyhedron \(\mathcal{D}_{\mathcal{C}}(f)\) in terms of the properties of the corresponding decompositions.

If a decomposition is not reduced, then we can obtain a “better” decomposition by simultaneously simplifying both \(g\) and \(h\) through subtracting a convex function \(\phi\). Hence, it makes sense to put a special emphasis on reduced decompositions. Conveniently, the following theorem links this notion to the geometry of \(\mathcal{D}_{\mathcal{C}}(f)\).

The statement follows from a more general statement about polyhedra. Recall that any polyhedron \(P\) can written as the Minkowski sum \[P = Q + \operatorname{recc}(P) = \{ q + c \mid q \in Q, c \in \operatorname{recc}(P) \}\] where \(Q\) is a bounded polytope, and \(\operatorname{recc}(P)=\{v \in \mathbb{R}^d \mid x+tv \in P\) for all \(x\in P, t\geq0\}\) the recession cone of \(P\), see [46].

Having this at hand, we can prove 7.

Next, we describe the face relations of decomposition polyhedra by coarsenings of the corresponding functions.

Note that the entire definition does not depend on the underlying complex \(\mathcal{C}\) and the corresponding considered set \(\overline{\mathcal{V}}_\mathcal{C}^+\).

We now prove the following proposition that relates coarsenings of the decompositions to inclusion relations of the minimal faces that contain the decompositions.

The number of pieces relates to the notion of monomial complexity studied in [1], where a minimal decomposition translates to a decomposition which is minimal with respect to monomial complexity. We now give a geometric interpretation of this property in terms of \(\mathcal{D}_{\mathcal{C}}(f)\).

This theorem implies a simple finite procedure to find a minimal decomposition: enumerate all the vertices of \(\mathcal{D}_{\mathcal{C}}(f)\) and choose one satisfying 4. It also suggests the following important special case.

We now demonstrate that this case is not only convenient, but also it indeed arises for important classes of functions. To this end, recall that \(\pi(\mathcal{D}_{\mathcal{C}}(f)) = \overline{\mathcal{V}}_\mathcal{C}^+\cap (\overline{\mathcal{V}}_\mathcal{C}^++ f)\), where \(\overline{\mathcal{V}}_\mathcal{C}^+\) is a convex, pointed polyhedral cone. In the following lemma, we give some sufficient conditions for such intersections of shifted cones to yield a polyhedron with a unique vertex.

Moreover, the support of a decomposition can serve as a certificate to verify if a decomposition is a unique vertex, and hence minimal. For \(f \in \overline{\mathcal{V}}_\mathcal{C}\), let \(\operatorname{supp}_\mathcal{C}^+(f) \mathrel{\vcenter{:}}= \{\sigma \in \mathcal{C}\mid w_f(\sigma) > 0\}\) and \(\operatorname{supp}_\mathcal{C}^-(f) \mathrel{\vcenter{:}}= \{\sigma \in \mathcal{C}\mid w_f(\sigma) < 0\}\).

While 13 sounds technical, it is powerful as it allows us to prove that important functions satisfy the condition of 12.

Hyperplane functions are precisely the functions that are computable by a ReLU neural network with one hidden layer and appear in this context as 2-term max functions ([6]). They also coincide with functions computable with the hinging hyperplane model ([22], [50]).

7 characterizes the reduced decompositions as bounded faces and 13 provides a condition that can identify a given decomposition as the minimal one. The natural follow-up question is how to find these decompositions. In the following, we show that this can be done via linear programming over the decomposition polyhedron.

Before proving this statement, we give a description of the dual cone \((\overline{\mathcal{V}}_\mathcal{C}^+)^\vee\). Recall that \(\overline{\mathcal{V}}_\mathcal{C}^+\cong \bigcap_{\sigma \in \mathcal{C}^{d-1}}\{w \in \mathcal{W}_\mathcal{C}\mid w(\sigma) \geq 0\}\), i.e., the intersection of the nonnegative orthant \(\{w \colon \mathcal{C}^{d-1} \to \mathbb{R}\mid w(\sigma) \geq 0\}\) with the linear space \(\mathcal{W}_\mathcal{C}\). By duality of intersections and sums, it follows that \((\overline{\mathcal{V}}_\mathcal{C}^+)^\vee\) is isomorphic to the Minkowski sum of the nonnegative orthant with \(\mathcal{W}_\mathcal{C}^\perp\). In particular, any weight function \(w\) with positive weights \(w(\sigma) > 0\) lies in the interior. 14 follows from the following more general fact about faces of polyhedra.

5 Translation to Virtual Polytopes↩︎

The framework of decomposition polyhedra has a natural translation to the setting of virtual polytopes. In this section, we translate our main results to this context, providing structural insights into the problem of finding “minimal” representatives for a given virtual polytope.

As discussed in 3, the vector space \(\operatorname{CPWL}^0_d\) of positively homogeneous CPWL functions is isomorphic to the vector space \(\mathcal{VP}_d\) of virtual polytopes. Under this isomorphism, a convex positively homogeneous CPWL function corresponds to its Newton polytope. Consequently, decomposing a function \(f \in \operatorname{CPWL}^0_d\) into a difference of convex functions, \(f=g-h\), is equivalent to finding a representative for the virtual polytope \(\operatorname{Newt}(f)\) as a Minkowski difference of two conventional polytopes, \(\operatorname{Newt}(f) = \operatorname{Newt}(g) - \operatorname{Newt}(h)\).

This equivalence allows us to rephrase 1 in a purely geometric language, see also [1]. A common measure for the complexity of a polytope is its number of vertices. The geometric problem is thus:

Our theory provides a new perspective for this problem. Let \(R\) be a polytope and \(\mathcal{C}\) its normal fan. We restrict our search to representatives \(P-Q\) where \(P\) and \(Q\) are in the deformation cone of \(R\), or equivalently, the normal fans of \(P\) and \(Q\) are coarsenings of \(\mathcal{C}\). This is equivalent to requiring that the corresponding CPWL functions \(f_P\) and \(f_Q\) are compatible with \(\mathcal{C}\). For a virtual polytope \(V\) whose corresponding CPWL function \(f_V = \operatorname{Newt}^{-1}(V)\) is compatible with \(\mathcal{C}\), we define its representative polyhedron as \[\mathcal{R}_{\mathcal{C}}(V) \mathrel{\vcenter{:}}= \{(P,Q) \in \mathcal{P}_d \times \mathcal{P}_d \mid V = P-Q, P,Q \in \mathcal{DC}(R) \}.\] The linear isomorphism \(\operatorname{Newt}\) maps the decomposition polyhedron \(\mathcal{D}_{\mathcal{C}}(f_V)\) bijectively to the representative polyhedron \(\mathcal{R}_{\mathcal{C}}(V)\). This immediately allows us to translate our main theorems.

Similarly, we can translate the notion of a reduced decomposition. A representative \((P,Q)\) is irreducible if there is no non-trivial polytope \(A\) (i.e., \(A\) is not just a point) such that \(P' = P-A\) and \(Q' = Q-A\) are both still valid polytopes. If such an \(A\) exists, \((P', Q')\) would be a geometrically simpler representative of the same virtual polytope \(V\).

These results imply that the search for minimal representatives of a virtual polytope \(V\) that are in the deformation cone of a summand polytope \(R\) (with normal fan \(\mathcal{C}\)) can be performed by enumerating the vertices of its representative polyhedron \(\mathcal{R}_\mathcal{C}(V)\). If this polyhedron has a unique vertex, that vertex corresponds to the unique minimal representative.

6 Analysis of Existing Decompositions↩︎

Constructions of decompositions of CPWL functions as a difference of two convex functions have appeared in many contexts. In this section, we relate some of these existing constructions to our framework. Moreover, we provide a counterexample to a construction which was proposed by [1] to obtain a minimal decomposition in general dimensions.

6.1 Hyperplane Extension and Local Maxima Decomposition↩︎

The literature contains a variety of different constructions to decompose a CPWL function. It is worth noting, however, that these constructions usually follow one of two main themes. The first theme is to construct \((g,h)\) in a way such that they are compatible with the complex \(\mathcal{C}\) that arises by extending the codimension-\(1\) faces of \(\mathcal{C}_f\) to hyperplanes, see e.g. [16] and [18]. The second theme is to exploit the properties of the lattice representation of a CPWL function [17].

Both of these themes were already illustrated by [8], and we briefly describe their constructions here.

In the following, we show that for the functions that compute the \(k\)-th order statistic, both constructions do not yield the unique minimal decompositions, which exist by 12. This implies the following result.

16 and 17 provide decompositions and hence also regular polyhedral complexes \(\mathcal{H}_f\) respectively \(\mathcal{H}^+_f\) compatible with a given CPWL function \(f\). The two examples show that the constructions do not necessarily yield vertices of the decomposition polyhedra \(\mathcal{D}_{\mathcal{H}_f}(f)\) respectively \(\mathcal{D}_{\mathcal{H}^+_f}(f)\). One might be tempted to search within the polyhedra \(\mathcal{D}_{\mathcal{H}_f}(f)\) and \(\mathcal{D}_{\mathcal{H}^+_f}(f)\) for the global optimal solution. However, the global optimal solution is not necessarily contained in these polyhedra, as we will show later. For this, we will use the fact that in dimension two, there is always a unique minimal decomposition due to a result from [1], which we will sketch in the next section.

6.2 Balancing↩︎

The duality between positively homogeneous convex CPWL functions and Newton polytopes, as described in 3, serves as a motivation for [1] to construct minimal decompositions \(f = g-h\) of positively homogeneous CPWL functions as the difference of two convex such functions in dimension \(2\).

6.2.1 Balancing in dimension 2↩︎

In this section, we present their minimal decomposition which they accomplish by introducing a single new \(1\)-dimensional face to \(\mathcal{C}_f\) and an adapted weight function to satisfy the balancing condition.

The decomposition can be obtained as follows. Let \(\mathcal{C}_f\) be a \(2\)-dimensional polyhedral fan compatible with \(f\) with rays \(\rho_1,\dots,\rho_m \subset \mathbb{R}^2\) and ray generators \(r_1,\dots,r_m \in \mathbb{R}^2\) such that \(\|r_i\|=1\) for \(i=1,\dots,m\). Furthermore, let \(w_f\) be the corresponding element in \(\mathcal{W}_{\mathcal{C}_f}\) and \(w^+_f \mathrel{\vcenter{:}}= \max \{w_f,0\}\). We now define an additional ray \(\rho_{m+1}\) with ray generator \[r_{m+1} = -\sum_{i = 1}^m \max(w_f(\rho_i),0) r_i\] and a convex function \(g\) through the weights \[w_g(\rho_i) = \begin{cases} w_f(\rho_i) & \text{if } w_f(\rho_i) > 0, i \in [m] \\ 0 & \text{if } w_f(\rho_i) \leq 0, i \in [m] \\ \sum_{i = 1}^m \max(w_f(\rho_i),0) & \text{if } i = m+1. \end{cases}\] This defines the convex functions \(g\), \(h = g-f\), and results in a minimal decomposition \(f = g-h\) in the 2-dimensional positively homogeneous case. Considering this construction through to the duality to Newton polytopes, we can identify rays of \(\mathcal{C}_f\) which correspond to convex breakpoints of \(f\) with edges of the Newton polytope \(\operatorname{Newt}(g)\), and the construction from 19 adds a "missing" edge to the Newton polygon \(\operatorname{Newt}(g)\).

6.2.2 Fixing complex can be a problem↩︎

With 19, we can prove that the decomposition polyhedra \(\mathcal{D}_{\mathcal{H}_f}(f)\) and \(\mathcal{D}_{\mathcal{H}^+_f}(f)\) corresponding to the polyhedral complexes obtained from hyperplane extensions \(\mathcal{H}^+_f\) (16) and local maxima decompositions \(\mathcal{H}^+_f\) (17) do not necessarily contain the global minimal decomposition of \(f\) into convex functions.

6.2.3 Balancing in higher dimensions↩︎

Based on their \(2\)-dimensional construction, [1] propose a procedure to reduce the \(d\)-dimensional case to \(2\)-dimensions via projections.

One can check that for some \(\sigma \in \mathcal{C}^{d-1}\) and \(\tau\in \mathcal{C}^{d-2}\) being a face of \(\sigma\), the edge \(e_{\sigma}\) of length \(w(\sigma)\) which is perpendicular in \(\operatorname{span}(\tau)^\perp\) to \(\tau\) is independent of the choice of the face \(\tau\). In particular, the direction of the edge \(e_\sigma\) is normal to the hyperplane spanned by \(\sigma\). However, it remained unclear whether or not the second step in this procedure is always well-defined, that is, that placing the polygons in such a coherent way is possible. To make this more precise, let for some \(\tau \in \mathcal{C}^{d-2}\) the edges of the polygon \(P_\tau\) be given in a cyclic way \(\{e_{\sigma_1}, \ldots, e_{\sigma_m}\}\). Placing a polygon \(P_\tau\) refers to choosing an \(x_\tau \in \mathbb{R}^d\) and defining the placed polygon as \(P_\tau(x_\tau)=\operatorname{conv}(x_\tau,x_\tau+e_{\sigma_1},x_\tau+ e_{\sigma_1}+e_{\sigma_2},\ldots,x_\tau+\sum_{i=1}^m e_{\sigma_m})\). Placing them in a coherent way means choosing an \(x_\tau \in \mathbb{R}^d\) for every \(\tau \in \mathcal{C}^{d-2}\) such that \(P_{\tau_1}(x_{\tau_1}) \cap P_{\tau_2}(x_{\tau_2}) = \operatorname{conv}(x_\sigma, x_\sigma + e_\sigma)\) for some \(x_\sigma \in \mathbb{R}^d\) whenever \(\tau_1\) and \(\tau_2\) are faces of \(\sigma\). A priori it is not clear that such \(x_\tau\) always exist. The following example will in fact show that the resulting linear equation system not always yields a solution.

Our conclusion is that the construction by [1] does not extend beyond the \(2\)-dimensional case, leaving it an open problem to find any finite algorithm that guarantees to return a minimal decomposition without fixing an underlying polyhedral complex. Note that for any fixed underlying polyhedral complex, 11 implies a finite algorithm by enumerating the vertices of the decomposition polyhedron, as discussed earlier.

7 Submodular Functions↩︎

In this section, we demonstrate that a special case of our framework is to decompose a general set function into a difference of submodular set functions and translate our results to this setting. Such decompositions are a popular approach to solve optimization problems, as discussed in the introduction.

Let \(\mathcal{F}_d\) be the vector space of set functions from \(2^{[d]}\) to \(\mathbb{R}\). We first show that functions in \(\mathcal{V}_{\mathcal{B}_d}\) are in one-to-one correspondence with the set functions \(\mathcal{F}_d\). To this end, for a set \(S\subseteq[d]\), let \(\mathbb{1}_S=\sum_{i\in S} e_i\) be the indicator vector of \(S\), that is, the vector that contains entries \(1\) for indices in \(S\) and \(0\) otherwise.

If we think this the other way around, starting with a set function \(F\), then \(f=\Phi^{-1}(F)\) is by definition a continuous extension of \(F\). It turns out that this particular extension is known as the Lovász extension [51], as we argue below. The Lovász extension is an important concept in the theory and practice of submodular function optimization as it provides a link between discrete submodular functions and continuous convex functions.

The intuition of the Lovász extension can already be seen in the proof of 22: depending on the ordering of the components of an input vector \(x\), the Lovász extension writes \(x\) as an affine combination of indicator vectors \(\mathbb{1}_{S_i}\), and uses the coefficients of the affine combination to compute the value \(f(x)\). Following the intuition, we see in the next proposition that \(\Phi^{-1}(F)\) is actually the Lovász extension of \(F\).

The following well-known property is key to the insights of this section.

Applying our insights from 4 to the previous proposition, we obtain the following well-known statement.

In particular, we can specialize 1 in the setting of this section as follows.

Having a Lovász extension with few pieces is desirable because it allows the submodular function to be stored and accessed efficiently during computational tasks. As 26 is a special case of 1, we are able to translate our results from 4 to the setting of submodular functions.

Let \(\mathcal{MOD}_d\subseteq \mathcal{F}_d\) be the vector space of modular functions, that is, set functions that satisfy 3 with equality. Note that a set function is modular if and only if its Lovász extension is an affine function [51]. Since for any \(M \in \mathcal{MOD}_d\), a set function \(F\) is submodular if and only if \(F+M\) is submodular, we define the vector space \(\overline{\mathcal{F}}_d = \mathcal{F}_d / \mathcal{MOD}_d\) of set functions modulo modular functions. Furthermore, let \(\overline{\mathcal{SM}}_d\) be the cone of submodular functions in this quotient.

A decomposition \((G,H) \in \overline{\mathcal{SM}}_d \times \overline{\mathcal{SM}}_d\) of a set function \(F\in \overline{\mathcal{F}}_d\) is called irreducible if there does not exist a submodular function \(I \in \overline{\mathcal{SM}}_d\setminus \{0\}\) such that \(G-I\) and \(H-I\) are submodular. Since a set function \(M \in \mathcal{F}_d\) is modular if and only if \(\Phi^{-1}(M)\) is affine linear, the isomorphism \(\Phi\) of Proposition 22 descends to an isomorphism \(\Phi \colon \overline{\mathcal{F}}_d \to \overline{\mathcal{V}}_{\mathcal{B}_d}\) such that \(\Phi(\overline{\mathcal{SM}}_d) = \overline{\mathcal{V}}^+_{\mathcal{B}_d}\).

For a set function \(F \in \overline{\mathcal{F}}_d\), the set of decompositions \[\mathcal{D}_{}(F)\mathrel{\vcenter{:}}= \{(G,H) \in \overline{\mathcal{SM}}_d \times \overline{\mathcal{SM}}_d \mid F=G-H\}\] is a polyhedron.

Since we factored out modular functions, we can assume without loss of generality that a set function \(F \in \overline{\mathcal{F}}_d\) is normalized, that is, \(F(\emptyset) =0\). In this case, \(f=\Phi^{-1}(F)\) is positively homogeneous. For the remainder of this section, we will assume all set functions to be normalized and all CPWL functions to be positively homogeneous. If \(F\) is submodular, \(f\) agrees with the support function of the base polytope \(B(F)\), and therefore \(B(F)\) is the Newton polytope \(\operatorname{Newt}(f)\) of the Lovász extension \(f\) (see e.g. [52] Theorem 12.3.). The Newton polytopes of functions that differ by a linear map are translations of each other and modular functions correspond to linear functions [51]. Hence, the set of base polytopes in \(\mathbb{R}^d\) modulo translation is precisely the set of Newton polytopes of functions compatible with the braid fan, which are also known as generalized permutahedra. We denote the cone of generalized permutahedra by \(\overline{\mathcal{GP}}_d\) and hence the maps \[B \colon \overline{\mathcal{F}}_d \to \overline{\mathcal{GP}}_d, F \mapsto B(F)\] and \[\operatorname{Newt}\colon \overline{\mathcal{V}}^+_{\mathcal{B}_d} \to \overline{\mathcal{GP}}_d, f \mapsto \operatorname{Newt}(f)\] are well-defined and we obtain the following diagram: \[\begin{tikzcd} \overline{\mathcal{SM}}_d \arrow{r}{B} \arrow{d}[swap]{\overline{\Phi}}&\overline{\mathcal{GP}}_d \\ \overline{\mathcal{V}}^+_{\mathcal{B}_d} \arrow[swap]{ur}{\operatorname{Newt}}\end{tikzcd}\] In this setting, we call a decomposition \((G,H)\in\mathcal{D}_{}(F)\) minimal, if it is not dominated by any other decomposition, that is, if there is no other decomposition \((G',H')\in\mathcal{D}_{}(F)\) where \(B(G')\) has at most as many vertices as \(B(G)\), \(B(H')\) has at most as many vertices as \(B(H)\), and one of the two has strictly fewer vertices.

For a tuple of submodular functions \((G,H) \in \overline{\mathcal{SM}} \times \overline{\mathcal{SM}}\), let \((\mathcal{P}_{G},\mathcal{P}_H)\) be the tuple of the normal fans of the base polytopes \(B(G)\) and \(B(H)\). A decomposition \((G',H')\in\mathcal{D}_{}(F)\) is called a (non-trivial) coarsening of \((G,H)\in\mathcal{D}_{}(F)\) if \(\mathcal{P}_{G'}\) and \(\mathcal{P}_{H'}\) are coarsenings of \(\mathcal{P}_{G}\) and \(\mathcal{P}_H\), respectively (and at least one of them is a non-trivial coarsening).

The following example shows that the Lovász extensions of cut functions are hyperplane functions thus admit a unique minimal decomposition into submodular functions, which are themselves cut functions. In particular, the Lovász extensions of the decomposition have at most as many pieces as the Lovász extensions of the original cut function.

8 Neural Network Constructions↩︎

In this section we consider the following question: Given a CPWL function \(f\colon\mathbb{R}^d\to\mathbb{R}\) with \(q\) pieces and \(k\) affine components, what is the necessary depth, width, and size of a neural network exactly representing this function? To this end, we first discuss the necessary background on neural networks and known results on neural complexity. We then prove better results for the case of \(f\) being convex. Finally, we extend these results to nonconvex functions by writing them as a difference of convex functions.

8.1 Background↩︎

For a number of hidden layers \(\ell\geq0\), a neural network with rectified linear unit (ReLU) activations is defined by a sequence of \(\ell+1\) affine transformations \(T_i:\mathbb{R}^{n_{i-1}}\to\mathbb{R}^{n_i}\), \(i\in[\ell+1]\). We assume that \(n_0=d\) and \(n_{\ell+1}=1\). If \(\sigma\) denotes the function that computes the ReLU function \(x\mapsto \max\{x,0\}\) in each component, the neural network is said to compute the function \(f\colon\mathbb{R}^d\to \mathbb{R}\) given by \(f=T_{\ell+1}\circ\sigma\circ T_\ell\circ\sigma\circ\dots\circ\sigma \circ T_1\). We say that the neural network has depth \(\ell+1\), width \(\max_{i\in[\ell]} n_i\), and size \(\sum_{i\in[\ell]} n_i\).

It is well-known that the maximum of \(d\) numbers can be computed with depth \(\lceil \log_2d \rceil+1\) and overall size \(\mathcal{O}(d)\) [2]. This simple fact has been used in the literature to deduce exact representations of CPWL functions with neural networks from known representations of CPWL functions. We would like to focus on two of them here, which are in a sense incomparable. The first one goes back to [6] and builds upon ideas from [22]. We present it here in a slightly stronger form that follows from [23].

The second one goes back to [4] and is based on the lattice representation of CPWL functions, compare [20].

As noted before, one can assume that \(d< k \leq q\), since otherwise we could affinely project to a lower dimension without losing information. In fact, one would usually assume that the input dimension \(d\) is much lower than the number of affine components \(k\). Therefore, 27 provides the better representation in terms of depth, while 28 provides the better representation in terms of size. However, both theorems offer only fixed depth-size tradeoffs: each prescribes a particular depth and size bound, without allowing the user to interpolate between these two regimes. So, the naturally occurring question is: can we somehow freely choose a depth and trade depth against size in these representations? In other words: can we smoothly interpolate between the low-depth high-size representation of 27 and the low-size high-depth representation of 28? In the remaining section we present results that achieve this to some extent.

8.2 New Constructions for the Convex Case↩︎

In this part, we prove that in the convex case one can obtain a flexible depth-size tradeoff by grouping the affine components, applying the low-depth construction from 27 within each group, and then combining the group maxima using the standard ReLU construction for the maximum function.

In this sense, the construction interpolates between the low-depth representation of 27 and the low-size high-depth behavior of 28. In order to see how this provides a tradeoff between the representations of 27 and 28, it is worth looking at the extreme cases. If we choose \(r=1\) and \(s=k\), we exactly obtain the bounds from 27. On the other hand, if we choose \(r=k\) and \(s=1\), we obtain a neural network with depth \(\mathcal{O}(\log k)\) and size \(\mathcal{O}(k)\), which is qualitatively close to the bounds of 28. In fact, the even better size bound stems from the fact that our construction heavily relies on convexity.

In conclusion, by choosing an appropriate \(r\) (and corresponding \(s\)), the user can freely decide how to trade depth against size in neural network representations and thereby interpolate between the two extreme representations of 27 and 28.

8.3 Extension to the Nonconvex Case↩︎

The construction of 29 provides a nice blueprint of how to interpolate between 27 and 28, but it has the big limitation that it only works in the convex case. Simply mixing the two known representations of [thm:nnsfromwangsun,thm:nnsfromlattice] does not appear to work in the nonconvex case, as one cannot as easily identify groups of affine components that can be treated separately.

Instead we propose a different approach: given a CPWL function, first split it into a difference of two convex ones and then apply 29 to these two functions. To do this efficiently, it requires to find a good answer to 1.

As discussed in this paper, it is quite challenging to give a satisfying answer to 1 in full generality, but there are special cases, where we do have a good answer; see 4. In these special cases, we can extend the interpolation between the two representations in the following way. We need the following useful lemma.

We then obtain the following result by combining 29 with 10.

9 Outlook↩︎

From the theoretical perspective, the maybe most dominant open question is the following precise version of 1.

A positive answer to 30 would have useful consequences for our two applications in the context of (submodular) set function optimization and neural network representations. However, also a negative answer would be equally interesting.

One possible approach to resolve 30 could be to analyze which objective direction according to 14 leads to a good vertex of the decomposition polyhedron and prove theoretical properties about that vertex. The same theorem might also be key to developing algorithms that find good decompositions with linear programming. Generally, while beyond the scope of this paper, turning any of our insights into practical algorithms, preferably with theoretical guarantees, is a broad avenue for future research.

Acknowledgments↩︎

Marie-Charlotte Brandenburg was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. Moritz Grillo was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy — The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). 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↩︎

---

1. In our paper, we define piecewise linear functions to have finitely many pieces.↩︎