# decomposition_polyhedra_of_piecewise_linear_functions__bba5154c.pdf Published as a conference paper at ICLR 2025 Decomposition Polyhedra of Piecewise Linear Functions Marie-Charlotte Brandenburg Ruhr-Universität Bochum marie-charlotte.brandenburg@rub.de Moritz Grillo Technische Universität Berlin grillo@math.tu-berlin.de Christoph Hertrich University of Technology Nuremberg christoph.hertrich@utn.de In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions. Every CPWL function has infinitely many such decompositions, but for applications in optimization and neural network theory, it is crucial to find decompositions with as few linear pieces as possible. This is a highly challenging problem, as we further demonstrate by disproving a recently proposed approach by Tran & Wang (2024). To make the problem more tractable, we propose to fix an underlying polyhedral complex determining the possible locus of nonlinearity. Under this assumption, we prove that the set of decompositions forms a polyhedron that arises as intersection of two translated cones. We prove that irreducible decompositions correspond to the bounded faces of this polyhedron and minimal solutions must be vertices. We then identify cases with a unique minimal decomposition, and illustrate how our insights have consequences in the theory of submodular functions. Finally, we improve upon previous constructions of neural networks for a given convex CPWL function and apply our framework to obtain results in the nonconvex case. 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 (Re LU) activations (Arora et al., 2018). Extensive research has been put into understanding which neural network architectures are capable of representing which CPWL functions (Chen et al., 2022; Haase et al., 2023; Hertrich et al., 2021). 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) CWPL function f : Rn R can be written as the difference f = g h of two convex CPWL functions (Melzer, 1986; Kripfganz & Schulze, 1987). 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 Le Thi & Pham Dinh (2018)), and also occurs in the analysis of neural networks (Zhang et al., 2018). 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. Published as a conference paper at ICLR 2025 Problem 1.1. How to decompose a CPWL function f into a difference f = g h of two convex CPWL functions with as few pieces as possible? There exist many ways in the literature to obtain such a decomposition, 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 Tran & Wang (2024). 1.1 Our Contributions In this article, we propose a novel perspective on Problem 1.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 Section 2, Section 3 presents our new polyhedral approach to Problem 1.1. Instead of aiming for a globally optimal decomposition, we propose to restrict to solutions that are compatible with a given regular polyhedral complex P. 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 P is a polyhedron DP(f) that arises as the intersection of two shifted polyhedral cones (Theorem 3.5). We call this the decomposition polyhedron of f with respect to P. We prove several structural properties of DP(f). Among them, we show that the bounded faces of DP(f) are exactly those that cannot easily be simplified by subtracting a convex function (Theorem 3.8), and we show that a minimal solution must be a vertex of DP(f) (Theorem 3.13). The latter implies a finite procedure to find a minimal decomposition among those that are compatible with P, by simply enumerating the (potentially many) vertices of DP(f). It also implies that, if only a single vertex exists, 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 Re LU network. Existing Decompositions. Afterwards, in Section 4, 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 Tran & Wang (2024), who provide an optimal construction method in dimension 2 and suggest that it might generalize to higher dimensions. We show that it does not. Applications to Submodular Function. In Section 5, 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 Narasimhan & Bilmes (2005); Iyer & Bilmes (2012); El Halabi et al. (2023). We apply our results from Section 3 to obtain analogous structural insights about (submodular) set functions (Corollary 5.4). Application to Neural Network Constructions. Finally, in Section 6, we study the problem of constructing neural networks representing a given CPWL function. For convex CPWL functions, we blend two incomparable previous constructions by Hertrich et al. (2021) and Chen et al. (2022) 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 Problem 1.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 Published as a conference paper at ICLR 2025 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 Kripfganz & Schulze (1987); Zalgaller (2000); Wang (2004); Schlüter & Darup (2021). This was initiated in the 1-dimensional case by Bittner (1970), and already laid out for positively homogeneous functions in general dimensions by Melzer (1986). Typically, such decompositions are based on certain representations of CPWL functions, which have been constructed, e.g., in Tarela & Martinez (1999); Ovchinnikov (2002); Wang & Sun (2005); see also Koutschan et al. (2023; 2024) for a fresh perspective. These representations also help to understand the representative capabilities of neural networks, see Arora et al. (2018); Hertrich et al. (2021); Chen et al. (2022). Recently, a minimal decomposition for the 2-dimensional case was given by Tran & Wang (2024). 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 Mc Mullen (1996) in terms of weight spaces of polytopes. Generally, methods from tropical geometry have been successfully used to understand the geometry of neural networks, see e.g. Zhang et al. (2018); Hertrich et al. (2021); Montúfar et al. (2022); Haase et al. (2023); Brandenburg et al. (2024). 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 (Grötschel et al., 1981). 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 (Narasimhan & Bilmes, 2005; Iyer & Bilmes, 2012; El Halabi et al., 2023). Related decompositions were recently studied by Bérczi et al. (2024). In polyhderal theory, such a decomposition is equivalent to Minkowski differences of generalized permutahedra (Ardila et al., 2009; Jochemko & Ravichandran, 2022). Another closely related stream of work is concerned with the (exact and approximate) representative capabilities of neural networks, starting with universal approximation theorems (Cybenko, 1989), and specializing to Re LU networks, their number of pieces, as well as depth-width-tradeoffs (Telgarsky, 2016; Eldan & Shamir, 2016; Arora et al., 2018). In addition, Hertrich & Skutella (2023); Hertrich & Sering (2024) provide neural network constructions for CPWL functions related to combinatorial optimization problems. Geometric insights have also proven to be useful to understand the computational complexity of training neural networks (Froese et al., 2022; Bertschinger et al., 2024; Froese & Hertrich, 2024). Recently, Safran et al. (2024) give an explicit construction of how to efficiently approximate the maximum function with Re LU networks. 2 Preliminaries In this section we introduce the necessary preliminaries on polyhedral geometry and CPWL functions. For m N, we write [m] := {1, 2, . . . , m}. Polyhedra and Polyhedral Complexes. A polyhedron P is the intersection of finitely many closed halfspaces and a polytope is a bounded polyhedron. A hyperplane supports P if it bounds a closed halfspace containing P, and any intersection of P with such a supporting hyperplane yields a face F of P. A face is a proper face if F P and inclusion-maximal proper faces are referred to as facets. A polyhedral cone C Rn is a polyhedron such Published as a conference paper at ICLR 2025 that λu + µv C for every u, v C and λ, µ R 0. The dual cone of C is C = {y (Rn) | x, y 0 for all x C}. A cone is pointed if it does not contain a line. A cone C is simplicial, if there are linearly independent vectors v1, . . . , vk Rn such that C = {Pk i=1 λivi | λi 0}. For a cone C and t Rn, we call t + C a shifted cone or translated cone. A polyhedral complex P is a finite collection of polyhedra such that (i) P, (ii) if P P then all faces of P are in P, and (iii) if P, P P, then P P is a face both of P and P . For a polyhedral complex P in Rn, we denote by Pd the set of d-dimensional polyhedra in P. Given two n-dimensional polyhedral complexes P, Q, the complex P is a refinement of Q if for every τ Pn there exists σ Qn such that τ σ. The complex Q is a coarsening of P if P is a refinement of Q. The star of a face τ P is the set of all faces containing τ, i.e., star P(τ) = {σ P | τ σ}. We only consider complete polyhedral complexes, i.e., complexes covering Rn. A polyhedral fan is a polyhedral complex in which every polyhedron is a cone (see e.g., Figure 1b). An n-dimensional polyhedral complex can be equipped with a weight function w : Pn 1 R, as we describe as follows. Given a face σ P, we denote by aff(σ) Rn the unique smallest affine subspace containing σ. The relative interior of σ is the interior of σ inside the affine space aff(σ). For any dimension d n and any τ Pd 1, σ Pd with τ σ, let eσ/τ Rn be the normal vector of τ with respect to σ, that is, the unique vector with length one that is parallel to aff(σ), orthogonal to aff(τ), and points from the relative interior of τ into the relative interior of σ. A pair (P, w) forms a balanced (weighted) polyhedral complex if the weight function satisfies the balancing condition at every τ Pn 2 (see Figure 1a): X σ Pn 1: σ τ w(σ) eσ/τ = 0. We will see (Lemma 3.2) that considering only faces of codimension 2 indeed makes sense, see also the structure theorem of tropical geometry (Maclagan & Sturmfels, 2015). Continuous Piecewise Linear Functions. A continuous function f : Rn R is called continuous and piecewise linear (CPWL), if there exists a polyhedral complex P such that the restriction of f to each full-dimensional polyhedron P Pn is an affine function. If this condition is satisfied, we say that f and P are compatible with each other. In line with Chen et al. (2022), we define the number of pieces q of f to be the smallest possible number |Pn| of full-dimensional regions of a compatible polyhedral complex P. Note that this requires pieces to be convex sets, as they are polyhedra. The function f might realize the same affine function on distinct pieces P, Q Pn. To account for that, we define the number of affine components k to be the the number of different affine functions realized on all the pieces in Pn. Note that this quantity is independent of the choice of the particular compatible complex P. It holds that k q k! and each of these inequalities can be strict, compare the discussion by Chen et al. (2022). We can assume that k > n (and thus q > n) because otherwise f can be written as a composition of an affine projection to a lower dimension n followed by a CPWL function defined on Rn . If f is a convex CPWL function, then it can be uniquely written as the maximum of finitely many affine functions f(x) = maxi [k] gi(x) such that k = q. It follows that there is a unique coarsest compatible polyhedral complex Pf, namely the one with Pn f = {{x | gi(x) = maxj gj(x)} | i [k]}. In particular, we have k = q if f is convex. We call a polyhedral complex P regular, if there exists a convex CPWL function f such that P = Pf. 3 Decomposition Polyhedra In this section, we introduce and generally study the main concept of the paper, decomposition polyhedra. These polyhedra describe the set of possible decompositions of a CPWL Published as a conference paper at ICLR 2025 0 x2 x1 x1 0 x2 (a) Parameterization of the median function via the weights on the 1-dimensional facets. (b) Parameterization of the median function via its linear maps on the maximal polyhedra. Figure 1: Two different parameterizations of the function that computes the median of {0, x1, x2}. This function has q = 6 pieces and k = 3 affine components, see Example A.1 for more details. In Figure 1a, the convex breakpoints are colored in blue, and concave breakpoints are dashed and colored in red. The absolute value of the weights are given by the euclidean distance of the gradient of the affine components separated by these breakpoints. function f into a difference f = g h that are compatible with a given polyhedral complex. We start by establishing a handful of general results concerning the space of CPWL functions compatible with a given polyhedral complex. Proofs that are omitted from the main text as well as some auxiliary statements can be found in Appendix E. Lemma 3.1. Let P be a polyhredral complex. The set of CPWL functions compatible with P forms a linear subspace VP of the space of continuous functions. Let Aff(Rn) be the space of affine functions from Rn to R. For many of our arguments, adding or subtracting an affine function a Aff(Rn) 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 VP := VP/ Aff(Rn), where we identify functions in VP that only differ by adding an affine function. The following lemma shows that we can parameterize a function f VP by keeping track of how convex or concave the function is at the common face σ Pn 1 of two neighboring pieces. For the case that w is nonnegative and rational, the lemma follows from the structure theorem of tropical geometry (Maclagan & Sturmfels, 2015). In Appendix E.2, we present a generalization of the proof adapted to our setting. Lemma 3.2. The vector space WP := {w: Pn 1 R | (P, w) is balanced} is isomorphic to VP. For a function f VP, let wf WP be the corresponding weight function according to Lemma 3.2. Figure 1 illustrates the different parameterizations of the median function according to Lemma 3.2. Moreover, from Lemma 3.2 we can deduce that VP is finitedimensional (Corollary E.1) and the following proposition. Proposition 3.3. A function f VP is convex if and only if wf is nonnegative. Moreover, f is convex with P = Pf if and only if wf is strictly positive. The set V + P of convex functions in VP forms a polyhedral cone (Lemma E.2). In the following, we now fix a function f VP and consider the space of decompositions f = g h into differences of convex functions which are also compatible with P. In Lemma E.3, we show that for a regular complex P such a decomposition does indeed always exist. In particular, VP = span(V + P), which implies that dim(VP) = dim(V + P). Definition 3.4. For a CPWL function f and a polyhedral complex P, the decomposition polyhedron of f with respect to P is DP(f) := {(g, h) | g, h V + P, f = g h}. Published as a conference paper at ICLR 2025 The projection π((g, h)) = g induces an isomorphism between DP(f) and π(DP(f)) since DP(f) = {(g, g f) | g π(DP(f))}. We now show that this is indeed a polyhedron, which arises as the intersection of two shifted copies of a cone. Theorem 3.5. The set DP(f) is a polyhedron that arises as the intersection of convex functions with an affine hyperplane Hf = {(g, h) | f = g h}, namely DP(f) = (V + P V + P) Hf. Under the bijection π, the decomposition polyhedron is the intersection of two shifted copies of the polyhedral cone V + P. More specifically, π(DP(f)) = V + P (V + P + f). Remark 3.6. Under the isomorphism of Lemma 3.2, we identify DP(f) with the polyhedron {(wg, wh) W+ P W+ P | wg wh = wf} in WP WP and π(DP(f)) with the polyhedron {wg W+ P | wg wf}, where W+ P = {w WP | w 0}. For the remainder of this section, we analyze the faces of the polyhedron V + P in terms of the properties of the corresponding decompositions. Definition 3.7. A decomposition (g, h) DP(f) is called reduced, if there is no convex function ϕ V + P \ {0} such that g ϕ and h ϕ are both convex. 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 ϕ. Hence, it makes sense to put a special emphasis on reduced decompositions. Conveniently, the following theorem links this notion to the geometry of DP(f). Theorem 3.8. A decomposition (g, h) DP(f) is reduced if and only if (g, h) is contained in a bounded face of DP(f). Definition 3.9. We call a convex function g V + P a coarsening of another convex function g V + P if the unique coarsest polyhedral complex Pg of g is a coarsening of the unique coarsest polyhedral complex Pg . For a pair of convex CPWL functions (g, h), we call (g , h ) a coarsening of (g, h) if g h = g h and g and h are coarsenings of g and h respectively. The coarsening is called non-trivial if (Pg, Ph) = (Pg , Ph ). For a function f VP, let supp P(f) = {σ Pn 1 | wg(σ) = 0}. Lemma 3.10. A convex function g V + P is a coarsening of g V + P if and only if supp P(g ) supp P(g). The coarsening is non-trivial if and only if supp P(g ) supp P(g). Theorem 3.11. Let (g, h) DP(f), then the following three statements are equivalent: 1. There is no non-trivial coarsening of (g, h). 2. (g, h) is a vertex of DP(f). 3. (g, h) is a vertex of DQ(f) for all polyhedral complexes Q compatible with g and h. Definition 3.12. A decomposition (g, h) DP(f) is called minimal, if it is not dominated by any other decomposition, that is, if there is no other decomposition (g , h ) DP(f) where g has at most as many pieces as g, h has at most as many pieces as h, and one of the two has stricly fewer pieces. See Figure 2 in Appendix A.2 for a visualization. Phrasing it in terms of multi-objective optimization, we require that the number of pieces of f and g in a minimal decomposition are Pareto-optimal. The number of pieces relates to the notion of monomial complexity studied in Tran & Wang (2024), and 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 DP(f). Theorem 3.13. A minimal decomposition (g, h) DP(f) is always a vertex of DP(f). This theorem implies a simple finite procedure to find a minimal decomposition: enumerate all the vertices of DP(f) and choose one satisfying Definition 3.12. It also suggests the following important special case. Proposition 3.14. If DP(f), or equivalently π(DP(f)), has a unique vertex, then this vertex corresponds to the unique minimal decomposition within DP(f). 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 π(DP(f)) = V + P (V + P + f), where Published as a conference paper at ICLR 2025 V + P is a convex, pointed polyhedral cone. In Lemma E.6, 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 certificate to verify if a decomposition is a unique vertex, and hence minimal. For f V + P, let supp+ P(f) := {σ P | wf(σ) > 0} and supp P(f) := {σ P | wf(σ) < 0}. Proposition 3.15. If for f VP, there are g, h V + P such that f = g h and supp+(f) = supp P(g) as well as supp (f) = supp P(h), then (g, h) is the unique vertex of DQ(f) for every regular complete complex Q compatible with f. In this case, g and h have at most as many pieces as f. While Proposition 3.15 sounds technical, it is powerful as it allows us to prove that important functions satisfy the condition of Proposition 3.14. Definition 3.16. A hyperplane function with k hyperplanes is a function f : Rn R given by f(x) = P i [k] λi max{ x, ai + bi, x, ci + di} for any ai, ci Rn, bi, di, λi R, i [k]. Hyperplane functions are precisely the functions that are computable by a Re LU neural network with one hidden layer and appear in this context as 2-term max functions (Hertrich et al. (2021)). They also coincide with functions computable with the hinging hyperplane model (Breiman (1993); Wang & Sun (2005)). Moreover, in Example D.14 we will see that hyperplane functions include continuous extensions of cut functions. Definition 3.17. The k-th order statistic is the function f : Rn R that returns the k-th largest entry of an input vector x Rn. For k = n 2 , this coincides with the median. In Appendix A.3, we show that the conditions of Propositions 3.14 and 3.15 are indeed fulfilled for both, hyperplane functions and k-th order statistics. This shows that they admit decompositions with at most as many pieces as the function itself. Theorem 3.8 characterizes the reduced decompositions as bounded faces and Proposition 3.15 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. Theorem 3.18. A decomposition in π(DP(f)) = V + P (f + V + P) is reduced if and only if it is the optimal solution of a linear program with feasible solutions π(DP(f)) and objective linear functional contained in the interior of the dual cone of V + P. In particular, if π(DP(f)) has a single vertex, then the unique optimal solution is the unique reduced and minimal decomposition. Under the isomorphism to WP, the objective function u can be chosen as u(σ) = 1 for all σ. 4 Analysis of existing decompositions Constructions of decompositions of CPWL functions as 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 Tran & Wang (2024) to obtain a minimal decomposition in general dimensions. 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 P that arises by extending the codimension-1 faces of Pf to hyperplanes, see e.g. Zalgaller (2000) and Schlüter & Darup (2021). The second theme is to exploit the properties of the lattice representation of a CPWL function (Wang, 2004). Both of these themes were already illustrated by Kripfganz & Schulze (1987), and we describe their constructions in Appendix B as Construction B.1 ( hyperplane extensions ) and Construction B.2 ( local maxima decomposition ). In Appendix B.1, 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 Proposition 3.14. This implies the following result. Published as a conference paper at ICLR 2025 Proposition 4.1. There is a CPWL function f such that constructions B.1 and B.2 do not provide a vertex of DP(f) for any regular polyhedral complex P compatible with f. Moreover, Proposition B.3 shows that the suboptimality of the existing decompositions in the literature is not caused by the concrete construction method, but rather by the polyhedral complexes underlying these methods. Minimal decompositions. A construction for a unique minimal decomposition for certain CPWL functions f in dimension 2 was presented by Tran & Wang (2024), by introducing a single new 1-dimensional face to Pf and an adapted weight function to satisfy the balancing condition. Their approach builds on a duality theory between positively homogeneous convex CPWL functions and Newton polytopes. A CPWL function f is positively homogeneous if f(0) = 0 and Pf is a polyhedral fan. Such functions are the support functions of their Newton polytopes, as we describe in more detail in Appendix C.1; see also Joswig (2021, Section 1.2) and Maclagan & Sturmfels (2015, Chapter 2). Based on their 2-dimensional construction, Tran & Wang (2024) propose a procedure to reduce the n-dimensional case to 2-dimensions via projections, which we describe in Construction C.2 in Appendix C.2. The final step in this procedure is to construct a global function in n dimensions by gluing together the projections. In Example C.3 we illustrate that this final step is not always well-defined. Our conclusion is that the construction by Tran & Wang (2024) 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, Theorem 3.13 implies a finite algorithm by enumerating the vertices of the decomposition polyhedron, as discussed earlier. 5 Submodular Functions We demonstrate that a special case of our framework is to decompose a general set function into a difference of submodular set funtions and translate our results to this setting. Such decompositions are a popular approach to solve optimization problems as disussed in the introduction. Here, we sketch the idea, all details can be found in Appendix D. Let the polyhedral complex P be induced by the braid arrangement, that is, the hyperplane arrangement consisting of the n 2 hyperplanes xi = xj, with 1 i < j n, and let Fn be the vector space of set functions from 2[n] to R. Proposition 5.1. The mapping Φ that maps f VP to the set function F(S) = f(1S), where 1S = P i S ei, is a vector space isomorphism. Conversely, starting with a set function F, then f = Φ 1(F) is by definition a continuous extension of F, which is known as the Lovász extension (Lovász, 1983). 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. Definition 5.2. A set function F : 2[n] R is called submodular if F(A) + F(B) F(A B) + F(A B) for all A, B [n]. F is called modular if equality holds for all A, B [n]. Since a set function F is submodular if and only if its Lovász extension f = Φ 1(F) is convex (Lovász (1983)), we can specialize Problem 1.1 in the setting of this section as follows. Problem 5.3. Given a set function F Fn, how to decompose it into a difference of submodular set functions such that their Lovász extensions have as few pieces as possible? 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. Moreover, as we argue in Appendix D, for accordingly normalized submodular functions, the number of pieces of the Lovász extension is precisely the number of vertices of the base polytope, which, in turn, is precisely the Newton polytope of the Lovász extension. As Problem 5.3 is a special case of Problem 1.1, we can translate our results from Section 3 to the setting of submodular functions. Published as a conference paper at ICLR 2025 Corollary 5.4 (informal). The set of decompositions of a general set function into a difference of submodular functions (modulo modular functions) is a polyhedron that arises as the intersection of two shifted copies of the cone of submodular functions. In analogy to our general results, the irreducible decompositions correspond precisely to the bounded faces of that polyhedron and every minimal decomposition is a vertex. Example D.14 shows that the Lovász extensions of cut functions are hyperplane functions and 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. 6 Neural Network Constructions In this section we consider the following question: Given a CPWL function f : Rn 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. Background. For a number of hidden layers d 0, a neural network with rectified linear unit (Re LU) activiations is defined by a sequence of d+1 affine transformations Ti : Rni 1 Rni, i [d + 1]. We assume that n0 = n and nd+1 = 1. If σ denotes the function that computes the Re LU function x 7 max{x, 0} in each component, the neural network is said to compute the function f : Rn R given by f = Td+1 σ Td σ σ T1. We say that the neural network has depth d + 1, width maxi [d] ni, and size P It is well-known that the maximum of n numbers can be computed with depth log2 n + 1 and overall size O(n) (Arora et al., 2018). 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 Hertrich et al. (2021) and builds upon ideas from Wang & Sun (2005). We present it here in a slightly stronger form. Theorem 6.1. Every CPWL function f : Rn R with k affine components can be represented by a neural network with depth log2(n + 1) + 1 and overall size O(kn+1). The second one goes back to Chen et al. (2022) and is based on the lattice representation of CPWL functions, compare Tarela & Martinez (1999). Theorem 6.2 ((Chen et al., 2022)). Every CPWL function f : Rn R with q pieces and k affine components can be represented by a neural network with depth log2 p + log2 q + 1 and overall size O(kq). As noted before, one can assume that n < k q, since otherwise we could affinely project to a lower dimension without losing information. In fact, one would usually assume that the input dimension n is much lower than the number of affine components k. Therefore, Theorem 6.1 provides the better representation in terms of depth, while Theorem 6.2 provides the better representation in terms of size. However, both theorems are kind of inflexible for the user, dictating a certain depth and providing only these two specific options. 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 lowdepth high-size representation of Theorem 6.1 and the low-size high-depth representation of Theorem 6.2? In the remaining section we present results that achieve this to some extent. New Constructions for the Convex Case. In this part we prove that we can achieve the desired tradeoff easily in the convex case by mixing the two representations of Theorem 6.1 and Theorem 6.2. Theorem 6.3. Every convex CPWL function f : Rn R with k affine components can be represented by a neural network with depth log2(n + 1) + log2 r + 1 and overall size O(rsn+1), for any free choice of parameters r and s with rs k = q. Published as a conference paper at ICLR 2025 In order to see how this provides a tradeoff between the representations of Theorem 6.1 and Theorem 6.2, it is worth looking at the extreme cases. If we choose r = 1 and s = k, we exactly obtain the bounds from Theorem 6.1. On the other hand, if we choose r = k and s = 1, we obtain a neural network with depth O(log k) and size O(k), which is qualitatively close to the bounds of Theorem 6.2. 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 Theorem 6.1 and Theorem 6.2. Extension to the Nonconvex Case. The construction of Theorem 6.3 provides a nice blueprint of how to interpolate between Theorem 6.1 and Theorem 6.2, but it has the big limitation that it only works in the convex case. Simply mixing the two known representations of Theorems 6.1 and 6.2 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 Theorem 6.3 to these two functions. To do this efficiently, it requires to find a good answer to Problem 1.1. As discussed in this paper, it is quite challenging to give a satisfying answer to Problem 1.1 in full generality, but there are special cases, where we do have a good answer; see Section 3. For example, we obtain the following result by combining Theorem 6.3 with Lemma E.3. Corollary 6.4. Let f : Rn R be a CPWL function that is compatible with a regular polyhedral complex P with q = |Pn| full-dimensional polyhedra. Then, f can be represented by a neural network with depth log2(n + 1) + log2 r + 1 and overall size O(rsn+1), for any free choice of parameters r and s with rs q. For a given CPWL function f, provided that one can find a regular polyhedral complex such that q is not much larger than the number of pieces q, Corollary 6.4 does indeed provide a smooth tradeoff between Theorem 6.1 and Theorem 6.2 in the general, nonconvex case. As q is the minimal number of fulldimensional polyhedra in any (potentially nonregular) polyhedral complex compatible with f, the big question is how much of a restriction the assumption of regularity might be. 7 Open Problems From the theoretical perspective, the maybe most dominant open question is the following precise version of Problem 1.1. Problem 7.1. Given a CPWL function f in dimension n with q pieces, does there always exist a decomposition f = g h such that the number of pieces of g and h is polynomial in n and q? Note that by definition, f is compatible with a polyhedral complex P with |Pn| = q. To answer Problem 7.1 positively, by Lemma E.3 it would be sufficient to find a regular polyhedral complex Q with |Qn| = poly(n, q) that is a refinement of P. Conversely, if we can answer Problem 7.1 positively, then the underlying complex of g + h would give us such a regular complex Q. Therefore, to solve Problem 7.1, one needs to answer the following question: given an arbitrary complete polyhedral complex P, what is the coarsest refinement of P that is regular? A positive answer to Problem 7.1 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 Problem 7.1 could be to analyze which objective direction according to Theorem 3.18 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. Published as a conference paper at ICLR 2025 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 is 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 Neur Ex Co. Marcelo Aguiar and Federico Ardila. Hopf monoids and generalized permutahedra. Memoirs of the American Mathematical Society, 2017. Federico Ardila, Carolina Benedetti, and Jeffrey Doker. Matroid polytopes and their volumes. Discrete & Computational Geometry, 43(4):841 854, November 2009. doi: 10.1007/s00454-009-9232-9. Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018. Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is R-complete. Advances in Neural Information Processing Systems, 36, 2024. L. Bittner. Some representation theorems for functions and sets and their application to nonlinear programming. Numerische Mathematik, 16(1):32 51, February 1970. doi: 10. 1007/bf02162405. Marie-Charlotte Brandenburg, Georg Loho, and Guido Montufar. The real tropical geometry of neural networks for binary classification. Transactions on Machine Learning Research, 2024. L. Breiman. Hinging hyperplanes for regression, classification, and function approximation. IEEE Transactions on Information Theory, 39(3):999 1013, 1993. doi: 10.1109/18. 256506. Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, and Tamás Schwarcz. Monotonic decompositions of submodular set functions, 2024. ar Xiv:2406.04728. Kuan-Lin Chen, Harinath Garudadri, and Bhaskar D Rao. Improved bounds on neural complexity for representing piecewise linear functions. In Advances in Neural Information Processing Systems, volume 35, 2022. George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303 314, 1989. Marwa El Halabi, George Orfanides, and Tim Hoheisel. Difference of submodular minimization via DC programming. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9172 9201. PMLR, 23 29 Jul 2023. Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pp. 907 940. PMLR, 2016. Vincent Froese and Christoph Hertrich. Training neural networks is NP-hard in fixed dimension. Advances in Neural Information Processing Systems, 36, 2024. Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of Re LU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775 1790, 2022. Published as a conference paper at ICLR 2025 Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169 197, 1981. Christian Alexander Haase, Christoph Hertrich, and Georg Loho. Lower bounds on the depth of integral Re LU neural networks via lattice polytopes. In International Conference on Learning Representations, 2023. Christoph Hertrich and Leon Sering. Re LU neural networks of polynomial size for exact maximum flow computation. Mathematical Programming, pp. 1 30, 2024. Christoph Hertrich and Martin Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS journal on computing, 35(5):1079 1097, 2023. Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of Re LU neural networks. Advances in Neural Information Processing Systems, 34:3336 3348, 2021. Rishabh Iyer and Jeff Bilmes. Algorithms for approximate minimization of the difference between submodular functions, with applications. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, UAI 12, pp. 407 417, 2012. Katharina Jochemko and Mohan Ravichandran. Generalized permutahedra: Minkowski linear functionals and ehrhart positivity. Mathematika, 68(1):217 236, January 2022. doi: 10.1112/mtk.12122. Michael Joswig. Essentials of tropical combinatorics, volume 219 of Graduate Studies in Mathematics. 2021. ISBN 978-1-4704-6741-8. Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk, and Josef Schicho. Representing piecewise linear functions by functions with small arity. Applicable Algebra in Engineering, Communication and Computing, pp. 1 16, 2023. Christoph Koutschan, Anton Ponomarchuk, and Josef Schicho. Representing piecewiselinear functions by functions with minimal arity. ar Xiv preprint ar Xiv:2406.02421, 2024. Anita Kripfganz and R. Schulze. Piecewise affine functions as a difference of two convex functions. Optimization, 18(1):23 29, 1987. doi: 10.1080/02331938708843210. Hoai An Le Thi and Tao Pham Dinh. Dc programming and dca: thirty years of developments. Mathematical Programming, 169(1):5 68, 2018. László Lovász. Submodular functions and convexity. Mathematical Programming The State of the Art: Bonn 1982, pp. 235 257, 1983. D. Maclagan and B. Sturmfels. Introduction to Tropical Geometry. Graduate Studies in Mathematics. 2015. ISBN 9780821851982. P. Mc Mullen. Weights on polytopes. Discrete & Computational Geometry, 15(4):363 388, April 1996. doi: 10.1007/bf02711515. D Melzer. On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions. Quasidifferential calculus, pp. 118 134, 1986. Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618 649, 2022. Mukund Narasimhan and Jeff Bilmes. A submodular-supermodular procedure with applications to discriminative structure learning. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, UAI 05, pp. 404 412, 2005. Sergei Ovchinnikov. Max-min representation of piecewise linear functions. Beiträge Algebra Geom., 43(1):297 302, 2002. ISSN 0138-4821. Published as a conference paper at ICLR 2025 Itay Safran, Daniel Reichman, and Paul Valiant. How many neurons does it take to approximate the maximum? In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3156 3183. SIAM, 2024. Nils Schlüter and Moritz Schulze Darup. Novel convex decomposition of piecewise affine functions, 2021. JM Tarela and MV Martinez. Region configurations for realizability of lattice piecewiselinear models. Mathematical and Computer Modelling, 30(11-12):17 27, 1999. Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp. 1517 1539. PMLR, 2016. Ngoc M Tran and Jidong Wang. Minimal representations of tropical rational functions. Algebraic Statistics, 15(1):27 59, 2024. Shuning Wang. General constructive representations for continuous piecewise-linear functions. IEEE Transactions on Circuits and Systems I: Regular Papers, 51(9):1889 1896, 2004. doi: 10.1109/TCSI.2004.834521. Shuning Wang and Xusheng Sun. Generalization of hinging hyperplanes. IEEE Transactions on Information Theory, 51(12):4425 4431, 2005. V. A. Zalgaller. Representation of functions of several variables by differences of convex functions. Journal of Mathematical Sciences, 100(3):2209 2227, June 2000. ISSN 15738795. doi: 10.1007/s10958-000-0006-4. Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In International Conference on Machine Learning, pp. 5824 5832. PMLR, 2018. Published as a conference paper at ICLR 2025 A.1 Different parameterizations of median function Example A.1 (Median). In this example, we have a look at the different parameterizations for the function that computes the median of 3 numbers. To have a 2-dimensional example, we set x3 := 0. Let the polyhedral complex P be induced by the maximal polyhedra Pπ = {x R2 | xπ(1) xπ(2) xπ(3)} where π: [3] [3] is a permutation and f : R3 R be the function given by f|Pπ(x) = xπ(2). The function f has concave breakpoints whenever the median and the higher coordinate change, i.e., at the facets that are given as σπ,1 = {x R2 | xπ(1) xπ(2) = xπ(3)} and convex breakpoints whenever the median and the lower coordinate change, that is, at the facets that are given as σπ,2 = {x R2 | xπ(1) = xπ(2) xπ(3)}. Since e1 e2 2 = 2 and e1 2 = e2 2 = 1, it holds that 2 xπ(1) = x3 1 xπ(1) = x3 and wf(σπ,2) = 2 xπ(3) = x3 1 xπ(3) = x3. See Figure 1 for a 2-dimensional illustration. A.2 Illustration of Definition 3.12 pieces of g pieces of h (a) The blue point corresponds to a minimal decomposition. pieces of g pieces of h (b) The blue point corresponds to a decomposition that is not minimal. Figure 2: Visualization of minimality, where a decomposition (g, h) is described by the number of pieces of g and h. A decomposition is minimal, if the rectangle spanned with (0, 0) does not contain another decomposition. A.3 Examples for unique minimal decompositions Example A.2 (Minimal decomposition for hyperplane functions). Let f : Rn R be a hyperplane function given as f(x) = P i [k] λi max{ x, ai + bi, x, ci + di}. We can assume without loss of generality that the hyperplanes Hi = {x Rn | x, ai + bi = x, ci + di} are pairwise distinct, because otherwise we can simply adjust λi. The polyhedral complex P induced by the hyperplane arrangement {Hi}i [k] is compatible with f. The convex functions g, h given by λi 0 λi max{ x, ai +bi, x, ci +di} and h(x) = X λi<0 λi max{ x, ai +bi, x, ci +di} are the unique minimal decomposition of f since supp P(g) = supp+ P(f) = {σ Pn 1 | σ S λi 0 Hi} and supp P(h) = supp P(f) = {σ Pn 1 | σ S Published as a conference paper at ICLR 2025 Example A.3 (Minimal decomposition of k-th order statistic). We construct a polyhedral complex that is compatible with the function f : Rn R that outputs the k-th largest entry of x Rd. For U [n] with |U| = k and i [n] \ U, let Pi,U = {x Rn | xj xi xℓ ℓ U, j [n] \ U}. All such polyhedra and their faces form a polyhedral complex P that is compatible with the function f : Rn R given by f(Pi,U) = xi. It is not hard to see that f = g h where g, h V + P are convex functions given by g(x) := max I [n] |I|=k and h(x) := max I [n] |I|=k 1 Moreover, let σi,j,U := {x Rn | xℓ xj = xi xm for all m U, ℓ [n] \ U}. Then supp P(g) = supp+ P(f) = {σi,j,U | U [n], |U| = k+1} and supp P(h) = supp P(f) = {σi,j,U | U [n], |U| = k}. Thus, Proposition 3.15 implies that (g, h) is the unique vertex of every regular polyhedral complex compatible with f. B Constructions by Kripfganz & Schulze (1987) Construction B.1 (Hyperplane extension). For all convex breakpoints, the local convex functions are extended to global convex functions with breakpoints supported on a single hyperplane, and the function g is defined as the sum of all these functions. To analyze it in our framework, let P be any polyhedral complex that is compatible with f and let wf WP be the weight function corresponding to f. For σ Pn 1, let Hσ be the hyperplane spanned by σ and A+ f = {Hσ | wf(σ) > 0} be the hyperplane arrangement consisting of the hyperplanes supporting the breakpoints where f is convex. Let H+ f be the common refinement of the polyhedral complex induced by A+ f and P. The weight function wg : Pn 1 R given by wg(σ) := P σ Hσ , wf (σ )>0 wf(σ ) is in WH+ f and nonnegative and hence the corresponding function g VH+ f is convex. It follows that h := g f is convex as well, yielding the desired decomposition. Construction B.2 (Local Maxima Decomposition). Let {P1, . . . , Pm} = Pn and fi be the unique linear extension of f|Pi. Moreover, let Mi := {j [m] | fi(x) fj(x) for all x Pi} and gi := maxj Mi Pj. Then f = min i [m] max j Mi fi = min i [m] gi i [m] gi is a convex function. Furthermore, let hi := g gi, then h := maxi [m] hi is a convex function as well and it holds that g h = g max i [m](g gi) = g (g min i [m] gi) = g (g f) = f Let Hi,j := {x Rn | fi(x) = fj(x)} and Af = {Hi,j | i = j}. Furthermore, let Hf be the polyhedral complex induced by the hyperplane arrangement Af. Then we have that g, h VHf . Proposition B.3. There is a CPWL function f and convex CPWL functions g, h with f = g h such that every decomposition (g , h ) DHf (f) as well as every decomposition (g , h ) DH+ f (f) is dominated by (g, h). Proof. Let P be the polyhedral complex in R2 with rays ρ1 = cone((1, 0)), ρ2 = cone((0, 1)), ρ3 = cone((1, 2)) and ρ4 = cone((2, 1)). Let wf(ρ1) = wf(ρ2) = 1 and wf(ρ3) = wf(ρ4) = 5 3 . Then according to Theorem C.1 the unique minimal decomposition is given by the complex obtained by adding the ray ρ5 = cone(( 1, 1)) and the weight function wf(ρ) ρ supp+ P(f) 0 ρ supp P(f) Published as a conference paper at ICLR 2025 as well as wh = wg wf. Nevertheless, the ray ρ5 is not contained in (the support of) Hf and hence this solution is not in DHf (f). Since (g, h) is the unique (up to adding a linear function) minimal decomposition, it follows that any solution in DHf (f) must be dominated by (g, h). Since H+ f is a coarsening of Hf, it holds that every decomposition in DH+ f (f) is contained in DHf (f) as well, impyling the result for DH+ f (f). B.1 Examples of existing decompositions Example B.4 (hyperplane extension of k-th order statistic). Let f be the function from Example A.3. For any i, j [n] and U [n] with i, j U and |U| = k + 1 it holds that σi,j,U supp+(f) and Hσi,j,U = {x Rn | xi = xj}. Hence, Pg is the braid fan and it holds that g(x) = n k 1 P i =j max{xi, xj}. Thus, the unique vertex (g , h ) from Example A.3 is clearly a non-trivial coarsening of the decomposition obtained from the hyperplane extension (since g is a non-trivial coarsening of g) and hence the decomposition cannot be a vertex of DQ(f) for any regular polyhedral complex Q. 2x1 + x2 2x2 (a) g(x) = max(x1, x2) + max(x1, 0) + max(x2, 0) (b) h(x) = g(x) f(x), where f is the median. Figure 3: The hyperplane extension of the median (second largest number) of 0, x1, x2 (i.e., n = 3) (Example B.4), which agrees with the local maxima decomposition (Example B.5) up to a factor 2. These representations do not agree for the median when n > 3. Example B.5 (local maxima decomposition of k-th order statistic). Let f be the function from Example A.3. Then, for U [n] with |U| = k 1 and i [n] \ U, we have that gi,U(x) = max j [n]\U xj. Thus, i,U gi,U(x) = (n k + 1) X S [n] |S|=n k+1 max j S xj. Note that g has only breakpoints when two coordinates that are the two highest coordinates in some set S swap places in the ordering. So, for any T [n] such that |T| = n k and any bijection π: [k] [n] \ T, let PT,π := {x Rn | xj xπ(1) . . . xπ(k+1), j T}. It follows that the set of full-dimensional cones Pn g of the unique coarsest polyhedral complex Pg compatible with g is given as Pn g = {Pπ,T }π,T . Again, the unique vertex (g , h ) from Example A.3 is clearly a non-trivial coarsening of the decomposition obtained from the lattice representation and hence the decomposition cannot be a vertex of DQ(f) for any regular polyhedral complex Q. Published as a conference paper at ICLR 2025 C Counterexample to a construction of Tran & Wang (2024) C.1 Duality and Newton polytopes In this section we describe the duality between convex piecewiese linear functions and Newton polytopes, adapted to our setup. A positively homogenous convex CPWL function is a function f such that f(0) = 0, and Pf is a polyhedral fan. In this case, it can be written as f(x) = maxi [k] x, vi , where vi Rn. We define the Newton polytope of f as the convex hull Newt(f) = conv(v1, . . . , vk). Then f is the support function of Newt(f), i.e., f(x) = maxp Newt(f) p, x . We now give an interpretation of Pf and wf in terms of the Newton polytope. Given any n-dimensional polytope P Rn, the (outer) normal cone of a k-dimensional face F of P is the (n k)-dimensional cone NF (P) = x Rn z, x = max p P p, x for all z F . (1) In particular, if P = Newt(f) and v is a vertex of P, then the description of the normal cone turns into Nv(Newt(f)) = {x Rn | v, x = f(x)} , and agrees with a maximal polyhedron in Pn f . The normal fan of a polytope is the collection of normal cones over all faces. Thus, for positively homogeneous convex functions, the polyhedral complex Pf agrees with the normal fan of Newt(f), and the number of linear pieces of f equals the number of vertices of Newt(f). The duality between Pf and Newt(f) also establishes a bijection between faces σ Pn 1 f and edges of Newt(f), and for the corresponding weight function wf WP holds that wf(σ) equals the Euclidean length of the edge that is dual to σ. This correspondence extends to general convex CWPL functions, where Pf is a complex which is dual to a polyhedral subdivision of Newt(f), and wf corresponds to lengths of edges in this subdivision (Maclagan & Sturmfels, 2015, Chapter 3.4). C.2 The Construction from Tran & Wang (2024) The duality between positively homogeneous convex CPWL functions and Newton polytopes, as described in Appendix C.1, serves as a motivation for Tran & Wang (2024) to construct minimal decompositions f = g h of positively homogeneous CPWL functions as the difference of two convex such functions in dimension 2. Theorem C.1 (Tran & Wang (2024)). For every positively homogeneous CPWL-function f : R2 R exists a unique (up to adding a linear function) minimal representation as difference of two convex functions g, h. The decomposition can be obtained as follows. Let Pf be a 2-dimensional polyhedral fan compatible with f with rays ρ1, . . . , ρm R2 and ray generators r1, . . . , rm R2 such that ri = 1 for i = 1, . . . , m. Furthermore, let wf be the corresponding element in WPf and w+ f := max{wf, 0}. We now define an additional ray ρm+1 with ray generator rm+1 = Pm i=1 max(wf(ρi), 0)ri and a convex function g through the weights wf(ρi) if wf(ρi) > 0, i [m] 0 if wf(ρi) 0, i [m] Pm i=1 max(wf(ρi), 0) if i = m + 1. 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 Pf which correspond to convex breakpoints of f with edges of the Newton polytope Newt(g), and the construction from Theorem C.1 adds a "missing" edge to the Newton polygon Newt(g). We now describe the proposed construction to generalize the 2-dimensional method to higher dimensions. Published as a conference paper at ICLR 2025 Construction C.2 (Tran & Wang (2024, Section 4.1)). Let f : Rn R be a positively homogeneous CWPL-function and P a polyhedral fan compatible with f. The attempt is to balance w+ f locally around every τ Pn 2 and then glue together" the local balancings to a global balancing. So, for some τ Pn 2, suppose that {σ1, . . . σk} = star P(τ) are the cones containing τ. The rays spanned by eσi/τ that inherit the weights w+ f (σi) for i [k] induce a 2-dimensional fan Pτ in the 2-dimensional linear space span(τ) orthogonal to span(τ). Let Pτ be the polygon in span(τ) corresponding to the minimal balancing of w+ f regarded as map w+ f : P1 τ R. Now proceed with the following steps. 1. For every τ Pn 2, construct the polygon Pτ. 2. Place the polygons Pτ in Rn in such a way, that whenever τ1, τ2 Pn 2 are faces of σ supp+ P(f), then the edges in Pτ1 and Pτ2 that correspond to σ are identified with each other. 3. Take the convex hull Pg of the polygons {Pτ}τ Pn 2. 4. The support function g of the polytope Pg and h := g f are a decomposition of f. One can check that for some σ Pn 1 and τ Pn 2 being a face of σ, the edge eσ of length w(σ) which is perpendicular in span(τ) to τ is independent of the choice of the face τ. In particular, the direction of the edge eσ is normal to the hyperplane spanned by σ. 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 τ Pn 2 the edges of the polygon Pτ be given in a cyclic way {eσ1, . . . eσm}. Placing a polygon Pτ refers to choosing an xτ Rn and defining the placed polygon as Pτ(xτ) = conv(xτ, xτ + eσ1, xτ + eσ1 + eσ2, . . . , xτ + Pm i=1 eσm). Placing them in a coherent way means choosing an xτ Rn for every τ Pn 2 such that Pτ1(xτ1) Pτ2(xτ2) = conv(xσ, xσ +eσ) for some xσ Rn whenever τ1 and τ2 are faces of σ. A priori it is not clear that such xτ always exist. The following example will in fact show that the resulting linear equation system not always yields a solution. C.3 Counterexample to the construction In the remaining of this section, we give a counterexample to Construction C.2, which is stated in Tran & Wang (2024) in terms of (virtual) Newton polytopes as a potential generalization of the 2-dimensional construction to higher dimensions. Example C.3 (Counterexample to Construction C.2). Figure 4 is an illustration of 4 polygons with labelled edges that cannot be placed in R3 such that the edges of different polygons with the same label are identified with each other. Hence, applying the above procedure to the CPWL-function f : R3 R given by f(x) = max{0, max i,j [3] i =j {min{xi, xj xi}}} is not well-defined since these 4 polygons arise and should be identified in the indicated way, which is impossible. We describe the 2-skeleton of a polyhedral fan P that is compatible with f. Let ei be the i-th standard unit vector. The rays are given as follows: P1 = {cone( ei), cone(ei), cone(ei + ej), cone(ei + ej + 2ek), cone(ei + 2ej + 2ek), cone(ei + ej + 2ek), cone(ei + ej + ek) | i, j, k [3] pairwise distinct} and the 2-dimensional cones as P2 = { cone(ei, ej), cone( ei, ei + ej + 2ek), cone( ei, ej + ek), cone(ei, ei + ej + 2ek), cone(ej + ek, ei + ej + 2ek), cone(ei + ej + 2ek, ei + 2ej + 2ek), cone(ei + ej + 2ek, ei + ej + ek), cone(ei + 2ej + 2ek, ei + ej + ek), cone(ej + ek, ei + 2ej + 2ek) | i, j, k [3] pairwise distinct} Published as a conference paper at ICLR 2025 Figure 4: 4 polygons that cannot be placed in a coherent way in R3 The weight function wf : P2 R given by w(cone(ei, ej)) = 1 w(cone( ei, ei + ej + 2ek)) = w(cone( ei, ej + ek)) = w(cone(ei, ei + ej + 2ek)) = w(cone(ej + ek, ei + ej + 2ek)) = w(cone(ei + ej + 2ek, ei + 2ej + 2ek)) = w(cone(ei + ej + 2ek, ei + ej + ek)) = w(cone(ei + 2ej + 2ek, ei + ej + ek)) = 2, w(cone(ej + ek, ei + 2ej + 2ek)) = 0 corresponds to the function f and is therefore balanced. See Figure 5 for a 2-dimensional illustration of P. Consider the 4 rays ρ1 = cone((0, 1, 1)), ρ2 = cone((1, 1, 2)), ρ3 = cone((1, 2, 1)), ρ4 = cone((1, 1, 1)) We will see that the corresponding polygons Pρ1, Pρ3, Pρ3 and Pρ4 equal the ones in Figure 4. The 2-dimensional cones which are in the stars of the 4 rays are the following: σ1 = cone((0, 1, 1), ( 1, 0, 0)), σ2 = cone((0, 1, 1), (1, 2, 1)), σ3 = cone((0, 1, 1), (1, 1, 2)), σ4 = cone((1, 1, 2), (1, 1, 1)), σ5 = cone((1, 1, 2), (1, 0, 1)), σ6 = cone((1, 1, 2), (0, 0, 1)), σ7 = cone((1, 2, 1), (0, 1, 0)), σ8 = cone((1, 2, 1), (1, 1, 0)), σ9 = cone((1, 2, 1), (1, 1, 1)), σ10 = cone((1, 1, 1), (2, 2, 1)), σ11 = cone((1, 1, 1), (2, 1, 1), σ12 = cone((1, 1, 1), (2, 1, 2), σ13 = cone((1, 2, 2), (1, 1, 1)), The direction of the edges of the polygons are given by the normal vectors of the hyperplanes spanned by the corresponding 2-dimensional cone and their length by the weight of the corresponding 2-dimensional cone. Published as a conference paper at ICLR 2025 (0, 1, 0) (0, 0, 1) (0, 1, 0) (0, 0, 1) ρ1 = (0, 1, 1) (2, 1, 1) ρ2 = (1, 1, 2) ρ3 = (1, 2, 1) ρ4 = (1, 1, 1) σ1 Figure 5: A 2-dimensional representation of P. The blue lines correspond to convex breakpoints of the function f, that is, a cone σ P2 such that w(σ) > 0. The concave breakpoints (w(σ) < 0) are dashed and colored in orange. f has no breakpoints on the gray, dotted lines (w(σ) = 0). Published as a conference paper at ICLR 2025 eσ1 = (0, 2, 2), eσ2 = (1, 1, 1), eσ3 = ( 1, 1, 1), eσ4 = (1, 1, 0), eσ5 = (1, 1, 1), eσ6 = ( 1, 1, 0), eσ7 = (1, 0, 1), eσ8 = ( 1, 1, 1), eσ9 = ( 1, 0, 1), eσ10 = (1, 1, 0), eσ11 = (0, 1, 1), eσ12 = ( 1, 0, 1), eσ13 = (0, 1, 1) In order to construct the polygons one needs to consider the orientation of the edge (and the normal vector) in the particular polygon. One can convince themselves that the polygons Pρ1, Pρ3, Pρ3 and Pρ4 of the 4 rays are given as: Pρ1(xρ1) = conv(xρ1 + eσ1, xρ1 + eσ1 + eσ2, xρ1 + eσ1 + eσ2 + eσ3) Pρ2(xρ2) = conv(xρ2 eσ3, xρ2 eσ3 eσ4, xρ2 eσ3 eσ4 eσ5, xρ2 eσ3 eσ4 eσ5 eσ6) Pρ3(xρ3) = conv(xρ3 eσ2, xρ3 eσ2 + eσ7, xρ3 eσ2 + eσ7 + eσ8, xρ3 eσ2 + eσ7 + eσ8 + eσ9) Pρ4(xρ4) = conv(xρ3 + eσ9, xρ4 + eσ9 + eσ10, xρ4 + eσ9 + eσ10 + eσ11, xρ4 + eσ9 + eσ10 + eσ11 + eσ12, xρ4 + eσ9 + eσ10 + eσ11 + eσ12 + eσ4, xρ4 + eσ9 + eσ10 + eσ11 + eσ12 + eσ4 + eσ13) Figure 4 already shows that they cannot be placed in a coherent way. To make this mathematically precise, one obtains a system of linear equations for xρ1, xρ2, xρ3 and xρ4, by plugging in the values for the normal vectors, that ensures that the edges for the same 2dimensional cone in different polygons are identified. This linear equation system does not have a solution. D Submodular Functions This section is a detailed version of Section 5, where we demonstrate that a special case of our framework is to decompose a general set function into a difference of submodular set funtions and translate our results to this setting. Such decompositions are a popular approach to solve optimization problems as disussed in the introduction. Definition D.1. The braid arrangement in Rn is the hyperplane arrangement consisting of the n 2 hyperplanes xi = xj, with 1 i < j n. For the remaining section, let P be the polyhedral complex arising from the braid arrangement. Let Fn be the vector space of set functions from 2[n] to R. We first show that functions in VP are in one-to-one correspondence with the set functions Fn. To this end, for a set S [n], let 1S = P i S ei be the indicator vector of S, that is, the vector that contains entries 1 for indices in S and 0 otherwise. Proposition D.2. The mapping Φ that maps f VP to the set function F(S) = f(1S) is a vector space isomorphism. Proof. The map Φ is clearly a linear map. To prove that Φ is an isomorphism, we show that a function f VP is uniquely determined by its values on {1S}S [n] and any choice of real values {y S}S [n] give rise to a function f VP such that f(1S) = y S. First, note that the maximal polyhedra Pn are of the form Pπ = {x Rn | xπ(1) . . . xπ(n)} for a permutation π: [n] [n]. There are exactly the n + 1 indicator vectors {1Si}i=0,...,n contained in Pπ, where Si := {π(n + 1 i), . . . , π(n)} for i [n] and S0 := . Moreover, the vectors {1Si}i=0,...,n are affinely independent and hence the values {f(1Si)}i=0,...,n uniquely determine the affine linear function f|Pπ. Therefore, f is uniquely determined by {f(1Si)}S [n]. Given any values {y S}S [n], by the discussion above, there are unique affine linear maps f|Pπ yielding f|Pπ(1S) = y S for all S [n] such that 1S Pπ. It remains to show that the resulting function f is well-defined on the facets Pn 1. Any such facet is of the form σπ,i = {x Rn | xπ(1) . . . xπ(i) = xπ(i+1) . . . xπ(n)}, which is the intersection of Pπ and Pπ (i,i+1), where (i, i + 1) denotes the transposition swapping i and i + 1. However, the indicator vectors {1Si}i [n]\{i} contained in σπ,i are Published as a conference paper at ICLR 2025 a subset of the indicator vectors contained in Pπ and Pπ (i,i+1). Therefore, it holds that f|Pπ(x) = f|Pπ (i,i+1)(x) for all x σπ,i implying that f is well-defined as a CPWL function. If we think this the other way around, starting with a set function F, then f = Φ 1(F) is by definition a continuous extension of F. It turns out that this particular extension is known as the Lovász extension (Lovász, 1983), 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. Definition D.3. For a set function F : 2[n] R, the Lovász extension f : Rn R is defined by f(x) = Pn i=0 λi F(Si), where = S0 S1 . . . Sn = [n] is a chain such that Pn i=1 λi1Si = x and λi 0 for all i [n 1] and λ0 = 1 Pn i=1 λi. Remark D.4. In many contexts in the literature, the Lovász extension is only defined on the hypercube [0, 1]n. For our purposes, it is more convenient to omit this restriction, which is captured by the above definition. The intuition of the Lovász extension can already be seen in the proof of Proposition D.2: 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 1Si, and uses the coefficients of the affine combination to compute the value f(x). Following the intuition, we see in the next proposition that Φ 1(F) is actually the Lovász extension of F. Proposition D.5. For a set function F Fn, the function f = Φ 1(F) is precisely the Lovász extension of F. Proof. By the definition of the Lovász extension, it follows that it is compatible with P. Thus, the Lovász extension is contained in VP. Moreover, as it is an extension that fixes indicator vectors, it follows that Φ applied to the Lovász extension of F gives us back F. As Φ is an isomorphism by Proposition D.2, the Lovász extension must be exactly Φ 1(F). Definition D.6. A set function F : 2[n] R is called submodular if F(A) + F(B) F(A B) + F(A B) (2) for all A, B [n]. F is called modular if equality holds for all A, B [n]. The following well-known property is key to the insights of this section. Proposition D.7 (Lovász (1983)). A set function F is submodular if and only if its Lovász extension f = Φ 1(F) is convex. Applying our insights from Section 3 to the previous proposition, we obtain the following well-known statement. Corollary D.8. The set of submodular functions forms a polyhedral cone SMn in the vector space Fn. In particular, we can specialize Problem 1.1 in the setting of this section as follows. Problem D.9. Given a set function F Fn, how to decompose it into a difference of submodular set functions such that their Lovász extensions have as few pieces as possible? 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 Problem D.9 is a special case of Problem 1.1, we are able to translate our results from Section 3 to the setting of submodular functions. Let Mn Fn be the vector space of modular functions, that is, set functions that satisfy equation 2 with equality. Note that a set function is modular if and only if its Lovász extension is an affine function (Lovász, 1983). Since for any M Mn, a set function F is submodular if and only if F +M is submodular, we define the vector space Fn = Fn/Mn of set functions modulo modular functions. Furthermore, let SMn be the cone of submodular Published as a conference paper at ICLR 2025 functions in this quotient. A decomposition (G, H) SMn SMn of a set function F Fn is called irreducible if there does not exist a submodular function I SMn \ {0} such that G I and H I are submodular. Since a set function M Fn is modular if and only if Φ 1(M) is affine linear, the isomorphism Φ of Proposition D.2 descends to an isomorphism Φ: Fn VP such that Φ(SMn) = V + P. For a set function F Fn, the set of decompositions D(F) := {(G, H) SMn SMn | F = G H} is a polyhedron. Corollary D.10. A decomposition (G, H) is irreducible if and only if (G, H) is contained in a bounded face of D(F). Proof. The extension of Φ to the cartesian product Φ Φ: VP VP Fn Fn is an isomorphism. Then the statement follows from the fact that D(F) = (Φ Φ)(DP(Φ 1(F)) and Theorem 3.8. Definition D.11. For a submodular function F : 2[n] R, the base polytope B(F) is defined as B(F) := {x Rn | X i S xi F(S) S [n], X i [n] xi = F([n])}. Since we factored out modular functions, we can assume without loss of generality that a set function F Fn is normalized, that is, F( ) = 0. In this case, f = Φ 1(F) is positively homogeneous. For the remaining chapter, 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 Newt(f) of the Lovász extension f (see e.g. Aguiar & Ardila (2017) Theorem 12.3.). The Newton polytopes of functions that differ by a linear map are a translation of each other and modular functions correspond to linear functions. Hence, if we denote by Bn the set of base polytopes in Rn modulo translation, the maps B : Fn Bn, F 7 B(F) and Newt: VP Bn, f 7 Newt(f) are well defined and we obtain the following diagramm: In this setting, we call a decomposition (G, H) D(F) minimal, if it is not dominated by any other decomposition, that is, if there is no other decomposition (G , H ) 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) SM SM, let (PG, PH) be the tuple of the normal fans of the base polytopes B(G) and B(H). A decomposition (G , H ) D(F) is called a (non-trivial) coarsening of (G, H) D(F) if PG and PH are coarsenings of PG and PH, respectively (and at least one of them is a non-trivial coarsening). Corollary D.12. (G, H) D(F) is a vertex if and only if there is no non-trivial coarsening of (G, H). Proof. Since g = Φ 1(G) and h = Φ 1(H) are the support functions of the base polytopes B(G) respectively B(H), the tuple of normal fans (PG, PH) agrees with the tuple (Pg, Ph) of the unique coarsest polyhedral complexes compatible with g and h. Hence by Theorem 3.11, there is no non-trivial coarsening of (G, H) if and only if (g, h) is a vertex of DP(f) which is the case if and only if (G, H) is a vertex of D(F). Corollary D.13. For a normalized set function F Fn, a minimal decomposition of F is a vertex of D(F). Proof. If (G, H) is not a vertex, then there is a coarsening (G , H ) D(F) of (G, H) implying that (G , H ) dominates (G, H). Published as a conference paper at ICLR 2025 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. Example D.14 (Minimal decompositions of cut functions). Let G = (V, E) be a graph where V = [n] and c: E R a weight function on the edges. Let F Fn be the cut function given by F(S) = P {u,v} δ(S) c({u, v}), where δ(S) := {{u, v} E | u S, v V \ S}. The function f := Φ 1(F) VP is given by f(x) = P {u,v} E c({u, v}) fu,v(x), where fu,v(x) = max{xu xv, xv xu}. To see this, first note that f VP. Thus, it suffices to check that F(S) = f(1S) for all S [n], which follows due to the observation that fu,v(1S) = 1 {u, v} δ(S) 0 {u, v} δ(S) Hence, Example A.2 implies that the functions c({u,v})>0 c({u, v}) fu,v and h = X c({u,v})<0 c({u, v}) fu,v form the unique minimal decomposition of f. Thus, G = Φ(g) and H = Φ(h), the submodular functions given by {u,v} δ(S) c({u,v})>0 c({u, v}) and H(S) = X {u,v} δ(S) c({u,v})<0 are the unique minimal decompositions of F into submodular functions. E.1 Proof of Lemma 3.1 Proof. Let f, g be CPWL functions which are compatible with P, and λ, µ R. Then for any P Pn holds (λf + µg)|P = λf|P + µg|P , which is an affine function restricted to P. Thus, the set VP of CPWL functions compatible with P forms a linear subspace of the space of continuous functions. E.2 Proof of Lemma 3.2 Proof. Let f VP. Since P is a complete polyhedral complex, for every σ Pn 1, there are P, Q Pn such that σ = P Q. Let a P , a Q Rn and b P , b Q R such that f|P (x) = a P , x + b P and f|Q(x) = a Q, x + b Q. Consider the linear map ϕ: VP WP given by wf(σ) := e P/σ, a P + e Q/σ, a Q = e P/σ, a P a Q . Note that if f is locally convex at σ, then e P/σ, a P a Q = a P a Q 2 and if f is locally concave at σ, then e P/σ, a P a Q = a P a Q 2. The proof proceeds analogously to the case where f has only convex breakpoints and the coefficients of the affine maps are rational. In this case, the lemma follows from the structure theorem of tropical geometry. See Maclagan & Sturmfels (2015) Proposition 3.3.2 for a proof that wf WP and Maclagan & Sturmfels (2015) Proposition 3.3.10 for a proof that ϕ is surjective. Here, we present an adjusted proof (to not necessarily convex functions and irrational coefficients). First, we check that wf WP. Let τ Pn 2 and {P1, . . . , Pm} = star P(τ) Pn and {σ1, . . . , σm} = star P(τ) Pn 1 be ordered in a cyclic way, that is, Pi Pi+1 = σi for i [m], where Pm+1 = P1. Note that, since f is continuous, we have that a Pi a Pi+1 span(e Pi/σi). The linear map Tτ : aff(τ) aff(τ) satisfying Tτ(e Pi/σi) = eσi/τ (given by a rotation matrix) Published as a conference paper at ICLR 2025 is an automorphism, implying that X wf(σ) eσ/τ = i=1 wf(σi) Tτ(e Pi/σi) i=1 e Pi/σi, a Pi a Pi+1 e Pi/σi i=1 e Pi/σi, e Pi/σi (a Pi a Pi+1) = Tτ(0) = 0 We proceed by showing that the map ϕ is surjective and its kernel is precisely Aff(Rn) and therefore, it induces an isomorphism between VP and WP. The kernel of ϕ is Aff(Rn) since wf(σ) = e P/σ, a P + e Q/σ, a Q = e P/σ, a P a Q = 0 if and only if a P a Q = 0 due to the fact that a P a Q span(e P/σ). Due to the continuity of f, this also implies that b P = b Q and hence f|Q = f|P and therefore the map f is affine linear. To show surjectivity, let w WP. We aim to find an f VP such that w = ϕ(f). Let Pn = {P1, . . . Pk} and for P Pn, σ Pn 1, let b P/σ R such that σ is contained in the hyperplane {x Rn | e P/σ, x + b P/σ = 0} and define the function f P/σ : Rn R by f P/σ(x) = e P/σ, x + b P/σ. Since P is complete, the graph G = (V, E) given by V = {1, . . . , k} and E = {{i, j} | Pj Pi Pn 1} is connected. Start by defining the function f|P1 = 0. For 1 < i k, let (j1, . . . jm) be a path from 1 to i and for ℓ [m 1], let σℓ= Pjℓ Pjℓ+1 and define the function ℓ=1 w(σℓ) f Pjℓ/σℓ. First, we argue that f|Pi is well-defined, that is, the definition of f|Pi does not depend on the path from vertex 1 to i. Equivalently, it suffices to show that for any cycle (i1, . . . , im) in G with i1 = im, it holds that Pm 1 ℓ=1 w(σℓ)f Piℓ/σℓ= 0, where σℓ= Piℓ Piℓ+1. Since P is complete any cycle decomposes into cycles (i1, . . . , im) corresponding to the star of a cone τ Pn 2, that is, {σ1, . . . , σm 1} = {σ Pn 1 | σ τ}. Since Tτ is an automorphism, it holds that Pm 1 ℓ=1 w(σℓ) eσℓ/τ = 0 if and only if Pm 1 ℓ=1 w(σℓ) e Piℓ/σℓ= 0 So, let x Rn be arbitrary and x aff(τ) and x aff(τ) such that x = x + x . Since w is in WP, it holds that P σ τ σ Pn 1 w(σ) eσ/τ = 0 and hence it follows that ℓ=1 w(σℓ)f Piℓ/σℓ(x) = ℓ=1 w(σℓ) e Piℓ/σℓ, x + x + b Piℓ/σℓ ℓ=1 w(σℓ) e Piℓ/σℓ, x ℓ=1 w(σℓ) e Piℓ/σℓ,x = 0 By definition, f is a CPWL function and compatible with P and hence in VP. To see that w = ϕ(f), let P, Q Pn such that σ = P Q Pn 1. Then it holds that a P a Q = w(σ) e P/σ and hence wf(σ) = e P/σ, a P + e Q/σ, a Q = e P/σ, a P a Q = e P/σ, w(σ) e P/σ = w(σ), finishing the proof. Published as a conference paper at ICLR 2025 E.3 Corollary E.1 Corollary E.1. VP is finite-dimensional. Proof. By Lemma 3.2, we have that VP = VP/ Aff(Rn) = WP. Thus, the dimension of VP is bounded from above by dim(WP) + dim(Aff(Rn)) |Pn 1| + (n + 1). E.4 Proof of Proposition 3.3 Proof. The function f is convex if and only if it is locally convex around every x Rn. If x is in the relative interior of some P Pn, then this is clearly satisfied since the function is locally affine linear. Now, assume that f is not locally convex around a x τ for some τ Pn 2. In other words, there are z, y Rn such that f(λz+(1 λ)y) > λf(z)+(1 λ)f(y) and such that the line between x and y intersects τ. Let L be the Lipschitz constant of f and δ := f(λz + (1 λ)y) λf(z) + (1 λ)f(y) > 0. Let ε := δ 4L > 0. Then there are v, w Rn with v , w < ε such that the line between z + v and y + w does not intersect any face τ Pn 2. But then, f(λ(z + v) + (1 λ)(y + w)) f(λz + (1 λ)y) L( λv + (1 λ)w ) > f(λz + (1 λ)y) 2Lε = δ + λf(z) + (1 λ)f(y) 2Lε δ + λf(z + v) + (1 λ)f(y + w) 2Lε 2Lε = λf(z + v) + (1 λ)f(y + w) and there must be a x in the relative interior of some σ Pn 1 such that f is not locally convex around x . Hence, f is convex if and only f is locally convex around every σ Pn 1, that is, f is locally convex around every x in the relative interior of σ. For any such x, there is a λ > 0 such that x + λ e P/σ P and x + λ e Q/σ Q, by construction of e P/σ and e Q/σ. Recall from the proof of Lemma 3.2 that wf(σ) = e P/σ, a P + e Q/σ, a Q , where f|P (x) = a P , x +b P and f|Q(x) = a Q, x +b Q. Since P, Q Pn and e P/σ = e Q/σ = 1, we have that x is the midpoint of x + λ e P/σ and x + λ e Q/σ. Therefore, f is convex if and only if f(x) 1 2f(x + λ e P/σ) + 1 2f(x + λ e Q/σ). Equivalently, 0 f(x + λ e P/σ) + f(x + λ e Q/σ) 2f(x) = λ( e P/σ, a P + e Q/σ, a Q ) = λ wf(σ). If P = Pf, then we have strict local convexity at every σ Pn 1, which means a strict inequality in the inequality above. E.5 Lemma E.2 Lemma E.2. V + P forms a polyhedral cone in VP. Proof. Lemma 3.2 and Proposition 3.3 imply that the set of convex functions in VP satisfies V + P = W+ P := T σ Pn 1{w WP | w(σ) 0}. This is a finite intersection of linear inequalities, so W+ P is a polyhedral cone. Moreover, = is a linear isomorphism, which implies that V + P is a polyhedral cone. E.6 Lemma E.3 Lemma E.3. Let P be a regular polyhedral complex. Then every CPWL function compatible with P can be written as a difference of two convex CPWL functions that are also compatible with P. In particular, VP = span(V + P). Proof. Let f VP be an arbirtary function. Since P is regular, by definition there exists a convex function g VP such that P = Pg. Proposition 3.3 implies that wg(σ) > 0 for all Published as a conference paper at ICLR 2025 σ Pn 1. For sufficiently large λ > 0, it follows that wf+λg 0 and thus f = (f +λg) λg is a representation of f as a difference of two compatible, convex functions, as desired. E.7 Proof Theorem 3.5 Proof. For the set of decompositions holds DP(f) = {(g, h) | g V + P, h V + P, f = g h} = (V + P V + P) Hf. For the projection we have π(DP(f)) = π({(g, g f) | g V + P, g f V + P}) = {g | g V + P, g f + V + P} = V + P (f + V + P). E.8 Proof of Theorem 3.8 The statement follows from a more general statement about polyhedra. Recall that any polyhedron P can written as the Minkowski sum P = Q + C = {q + c | q Q, c C} where Q is a bounded polytope, and C a unique polyhedral cone, the recession cone of P. Proposition E.4. A point x P is contained in a bounded face of P if and only if x c P c C \ {0}. Proof. Any face of the polyhedron P is of the form P u = {x P | x, u y, u y P}, and for Minkowski sums holds P u = Qu +Cu. Let x P be a point contained in a bounded face P u of P. Since P u is bounded, we have that P u = Qu + Cu with Cu = {0} being the unique bounded face of C. Thus, c, u < 0, u for all c C \ {0}. This implies that x c, u = x, u c, u > x, u and therefore, by definition of P u, we have that x c P. Conversely, suppose that x P is not contained in a bounded face. We want to show that there exists some direction c C \ {0} such that x c P. Since x is not contained in a bounded face, it is contained in the relative interior of an unbounded face F (where possibly F = P). Since the face is unbounded, it contains a ray x + Rc for some direction c C. On the other hand, since x int(F), we have that x εc F for ε > 0 small enough. As C is a cone, we have that εc C, which finishes the proof. Proof of Theorem 3.8. Since π induces a bijection between DP(f) and its image, this is also a bijection between bounded faces. By Theorem 3.5, π(DP(f)) is a polyhedron with recession cone V + P. Proposition E.4 implies that g is contained in a bounded face if and only if there exists no convex function ϕ V + P such that g ϕ π(DP(f)). Therefore, π 1(g) = (g, h), h = g f is contained in a bounded face of DP(f) if and only if there is no ϕ V + P such that (g ϕ, g f ϕ) = (g ϕ, h ϕ) DP(f). Since (g ϕ) (h ϕ) = f, this is equivalent to g ϕ or h ϕ being nonconvex, i.e., (g, h) is reduced. E.9 Proof of Lemma 3.10 Proof. First note that B(g) := S σ supp P(g) σ are exactly the points where g is not affine linear. Hence, the closures of the connected components of the complement of B(g) are the maximal polyhedra of the unique coarsest polyhedral complex Pg compatible with g. Let supp P(g ) supp P(g). Equivalently, for the complement holds (Rn \ B(g)) (Rn \ B(g )), and the same holds for the closures of the (open) connected components, i.e., the maximal faces in Pn g and Pn g . In other words, this is equivalent to that for every face P Pn g Published as a conference paper at ICLR 2025 there exists some P Pn g such that P P . Thus, supp P(g ) supp P(g) if and only if Pg is a coarsening of Pg. The coarsening is non-trivial if and only if there is a P Pn g such that there is no P Pn g with P P. This is the case if and only if there is a σ Pn 1 g that intersects the interior of P , which occurs if and only if σ supp P(g) \ supp P(g ). E.10 Proof of Theorem 3.11 We first prove the following proposition that relates coarsenings of the decompositions to inclusion relations of the minimal faces that contain the decompositions. Proposition E.5. For (g, h) DP(f), let F be the minimal face of DP(f) containing (g, h). Then (g , h ) is a coarsening of (g, h) if and only if there is a face G of DP(f) with G F such that (g , h ) G. The coarsening is non-trivial if and only if F = G. Proof. For a face F, let GF = {σ Pn 1 | wg(σ) = 0 for all (wg, wh) F} and HF = {σ Pn 1 f | wh(σ) = 0 for all (wg, wh) F} be the set of facets where the corresponding inequalities ensuring convexity of the functions g and h are tight. It is not hard to see that G F if and only if GF GG and HF HG. In other words, if (g , h ) is contained in a face G F, then one can move from (g, h) to (g , h ) without losing tight inequalities. Hence, Lemma 3.10 implies that (g , h ) is a coarsening of (g, h). If G F, then either GF GG or HF HG. Thus, another inequality becomes tight when moving from (g, h) to (g , h ) implying that the coarsening is non-trivial. For the converse direction, let (g , h ) be a coarsening of (g, h), which in particular means that g and h are compatible with P. Hence, f = g h implies that (g , h ) DP(f). Now, assume that there is no face G F such that (g , h ) G. Then the line between (g, h) and (g , h ) is not contained in F. Thus, a tight inequality gets lost when moving from (g, h) towards (g , h ). Hence, without loss of generality, there is a σ supp P(g )\supp P(g), which according to Lemma 3.10 is a contradiction to (g , h ) being a coarsening of (g, h). Proof of Theorem 3.11. 1 and 2 are equivalent by Proposition E.5. 3 trivially implies 2. Hence, it remains to show 1 = 3. Assume that there is a polyhedral complex Q compatible with g and h such that (g, h) is not a vertex of DQ(f). Then there is vertex (g , h ) of DQ(f) contained in the face containing (g, h). By Proposition E.5, it follows that (g , h ) is a nontrivial coarsening of (g, h). E.11 Proof of Theorem 3.13 Proof. If (g, h) is not not a vertex, the by Theorem 3.11, there is a coarsening (g , h ) of (g, h). Thus, (g, h) is dominated by (g, h) and therefore not minimal. E.12 Proof of Proposition 3.14 Proof. As DP(f) is nonempty, there must exist a minimal decomposition. By Theorem 3.13, every minimal decomposition must be a vertex. As there is only one vertex, it must coincide with the unique minimal decomposition. E.13 Lemma E.6 Lemma E.6. Let C Rd be a convex, pointed polyhedral cone. If C is simplicial then C (C + t) is a (potentially shifted) cone, i.e. a polyhedron with a single vertex, for any translation t. If C is not simplicial, then C (C + t) is a (shifted) cone if t C. Proof. If C is a simplicial full-dimensional cone, then it is the image of the nonnegative orthant under an affine isomorphism. Thus, it suffices to show that C (C + t) is a shifted cone for C = Rd 0. Let ˆt Rd such that ˆti = max(ti, 0). Then C (C + t) = {x | xi 0 and xi ti} = {x | xi ˆti} = C + ˆt. Published as a conference paper at ICLR 2025 On the other hand, if C is an arbitrary polyhedral cone and t C, then C (C +t) = C +t, and hence a shifted cone. Example E.7. The converse of the second statement from Lemma E.6 does not hold, that is, t C does not imply that C (C + t) is not a shfited cone. Indeed, let C = and t = 0 1 1 . Then C (C + t) = C + 1 1 1 is a shifted cone. On the other hand, the choice t = 0 1 2 yields the unbounded polyhedron C (C + t) = + C, which has two vertices and one line segment as bounded faces. E.14 Proof of Proposition 3.15 Proof. Let Q be any regular complete complex that is compatible with f. Then, g and h are as well compatible with Q, since supp P(g), supp P(h) supp P(f) implies that supp Q(g), supp Q(h) supp Q(f). Let (g , h ) DQ(f). Then it holds that supp+ Q(f) supp Q(g ) since wg wf = wh 0. Hence, supp Q(g) supp Q(g ) and Lemma 3.10 implies that g is a coarsening of g and analogously it follows that h is a coarsening of h . Therefore, (g, h) is a coarsening of every decomposition and thus by Theorem 3.11 the only vertex of DQ(f). Clearly, g and h cannot have more pieces than f. E.15 Proof of Theorem 3.18 Before proving this statement, we give a description of the dual cone (V + P) . Recall that V + P = T σ Pn 1{w WP | w(σ) 0}, i.e., the intersection of the nonnegative orthant {w(σ) 0} with the linear space WP. By duality of intersections and sums, it follows that (V + P) is isomorphic to the Minkowksi sum of the nonnegative orthant with W P . In particular, any w with positive weights w(σ) > 0 lies in the interior. Theorem 3.18 follows from a general fact about face of polyhedra. Lemma E.8. Let C be a convex, pointed polyhedral cone and P a polyhedron with recession cone C. Then u int(C ) is a direction in the interior of the dual cone of C if and only if the face P u of P which is minimized by u is a bounded face. Proof. Let P = C + Q, where Q is a bounded polyhedron. Then for any direction u holds P u = Cu + Qu. As C is a pointed cone, we have that Cu is bounded if and only if u int(C ). Since Qu is bounded for any direction, it follows that P u is bounded if and only if u int(C ). Proof of Theorem 3.18. Recall that every polyhedron P is the set of feasible solutions to some linear program, and that, given a linear functional u such that P u is bounded, the face P u coincides with the set of optimal solutions of the linear program. Now, P = V + P (V + P +f) is a polyhedron with recession cone V + P. Applying Lemma E.8 yields that for any u (int((V + P) ), every minimizer in π(DP(f)) lies in a bounded face, which, by Theorem 3.8, are precisely the reduced decompositions. Moreover, if π(DP(f)) contains a unique vertex then by Proposition 3.14 this coincides with the unique minimal decompoition. E.16 Proof of Theorem 6.1 Proof. In the convex case, this is literally proven by Hertrich et al. (2021). While Hertrich et al. (2021) have a slightly weaker bound for the nonconvex case, it follows from Koutschan et al. (2023, Thm. 2.4) that the stronger bound for the convex case also applies to the nonconvex case. E.17 Proof of Theorem 6.3 Proof. Recall that a convex CPWL function can be written as the maximum of its affine components, that is, f(x) = maxi [k] a T i x+bi. The idea is to split the k affine components of Published as a conference paper at ICLR 2025 f into r groups of size at most s, apply Theorem 6.1 to compute the maximum within each group, and then simply compute the maximum of the r group maxima in a straight-forward way. Let us first focus on computing the maximum of at most s affine components within each of the r groups. By Theorem 6.1, one can achieve this with a neural network of depth log2(n + 1) + 1 and overall size O(sn+1). We put all these r neural networks in parallel to each other and add, at the end, the simple neural network computing the maximum of these r maxima according to Arora et al. (2018), which has depth log2 r + 1 and overall size O(r). Altogether, the resulting neural network will have the desired depth and size. E.18 Proof of Corollary 6.4 Proof. By Lemma E.3, f can be decomposed into a difference of two convex functions which are compatible with P. Consequently, each of them has at most q affine components. Applying Theorem 6.3 to both functions separately and simply putting the two corresponding neural networks in parallel, subtracting the outputs, yields a neural network representing f with the desired size bounds.