Decomposition Polyhedra of Piecewise Linear Functions
Authors: Marie-Charlotte Brandenburg
Moritz Leo Grillo
Christoph Hertrich
Venue: ICLR 2025 Spotlight (2025)
Keywords: Piecewise Linear Functions
Polyhedral Geometry
Minimal Convex Decompositions
Submodular Functions
Neural Networks
Primary area: learning theory
TL;DR: We describe the set of convex decompositions of a piecewise linear function as a polyhedron and apply this to submodular functions and neural networks.

Abstract: 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 and Wang [Minimal representations of tropical rational functions. Algebraic Statistics, 15(1):27–59, 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.

Published as a conference paper at ICLR 2025
DECOMPOSITION POLYHEDRA OF PIECEWISE LINEAR FUNCTIONS
Marie-Charlotis Brandenburg
Moritz Grillo
Enhr-Universitää Bochum
Technische Universität Berlin gri 11olmahh tu-berlin in de
harie-charlott..bradddee www.nnnnbuurrrru......
Christoph Hertrich
University of Technology Nuremberg christoph. hwrtrichhutn.ccommmm
A ABSTRACT
this paper we contribute to the frequently studied question of how to decompose continuous piccewise linear (CPWL) function into difference two convex CPWL functions. Every CPWL function has infinitely many such decompositions, but for applications in optimization and neural net- work theory, it is crucial to find decomposio ions with as few linear pieces as possible. This is highly challenging problem, as we further demonstrate by disproving a recently proposed approach by (Taa & Wang (2024). To make the problem more tractable, we propose to fix an underlying polyhe- dral complex determining the possible locus of nonlincarity. Under this as- sumption, we prove that the set of dccompositions forms polyhedron that arises 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 unique minimal decomposition, and illustrate how our insights have consequences in the theory of submodular functions. Finally, constructions of neural networks for a given convex CPWL function and apply our framework to obtain results in the nonconvex case.
improve upon previous
1 INTRODUCTION
Continuous piecewise linear (CPWL) functions play crucial role in optimization and ma- chine learning. While they have traditionally been used to describe problems in geometry, discrete and submodular optimization, statistical regression, they recently gained signif- icant interest as functions represented by neural networks with rectified linear unit (ReLU) activations (Arora al. 2018). Extensive research has been put into understanding which neural network architectures are capable of representing which CPWL functions (Chen al. 2022 Haase et al.) 2023 Hertrich al. 2021). major source of complexity in all the atorementioned fields is nonconvexity. Indeed, not only are nonconvex optimization problems generally much harder to solve than convex ones, but also for neural net nonconvexities are usually responsible for making the obtained representations complicated.
is well-known folklore fact that every (potentially nonconvex) CWPL function f: R E can be written as the difference f= -- h of two conver CPWL functions (Melzer 1986 Kripfganz & Schulze 1987). Consequently, a natural idea circumvent the challenges induced by nonconvexity is to use such decomposition f g h and solve the desired problem separately for 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 A well-established measure for the complexity of a CPWL function the number of its linear pieces. Therefore, the main question we study in this article the following.
g and h compared to f?

---

Published as a conference paper at ICLR 2025
Problem 1.1. How to decompose CPWL function f into difference f 9 h of two convez CPWL functions with as few pieces as possible?
There exist. many ways the literature to obtain such a decomposition, as we discuss later, but none of them guarantees minimality at least a useful bound the mumber of pieces of g and depending on those of f. In fact, no finite procedure is known that guarantees to find minimal decomposition, despite recent attempt by Tran & Wang 2024).
1.1 OUR CONTRIBUTIONS
In this article, propose novel perspective Problem making use of polyhedral geometry and prove a number of structural results. We then apply our approach to existing decompositions in the literature, well to the theory of submodular functions and to the construction of ncural 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 presents our new polyhedral approach to Problem 1.I Instead of aiming for a globally optimal decomposition, regular polyhedral complez P. In short, this means fixing where the functions g and may have breakpoints, that is; points where they are not. locally linear. We prove that the set of solutions to decompose ʃ 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 polghedron of f with respect to P. We prove several structural properties of (f).). Among them, we show that the bounded faces of Df( are exactly those that cannot casily be simplified by subtracting a convex function (Thcorem 3.8), and we show that minimal solution must be a vertex of Df(f) (Thcorem 3.13 The latter implics finite procedure to find minimal decomposition among those that are compatible with P, by simply enumerating the (potentially many) vertices of Dp()). It also implies that, only single vertex exists, then there is unique minimal decomposition. We demonstrate that this is indeed the case for important CPWL functions, e.g., the median function, or those computed by 1-hidden-layer ReLU network.
propose restrict to solutions that compotible with given
Existing Decompositions. Afterwrrss, in Section broader context within the existing literature. We compare our minimality conditions with existing methods to construct decompositions. Notably, in this context, we refute conjec- ture by Tran & Wang (2024), who provide an optimal construction method in dimension and suggest that it might generalize to higher dimensions. We show that it does not.
4 we pul our investigations into
Applications to Submodular Function. In Section we show that our framework entails the setup of set functions which are decomposed into differences of submodular set functions. Representing set function such difference is popular approach to solve optimization problems similarly to DC programming, see Narasimmha & Bilmes (2005) Iyer
& Bilmes 2002 El Halabi et al. (2023). We apply our results from Section 3 obtain
analogous structural insights about (submodular) set functions aoasssCororo (Corollary 5.4)
Application to Neural Network Constructions. Finally, in Section 6 we study the problem of constructing neural networks representing 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 tradc-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
difference of two convex ones.
Limitations. We emphasize that the focus of our paper is fundamental research by build- ing a thcoretical foundation to tackle Problem 1.1 and connecting with other fields. As such, our paper does not imply any direct improvement for practical task, but it might prove helpful for that in the future. In particular, it is beyond the scope of our paper to pro- vide any implementation of (heuristic exact) method to decompose a CPWL. function
2

---

Published as a conference paper at ICLR 2025
into 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 underlying compatible polyhedral com- plex imposes some restriction on the set of possible solutions and can therefore be seen as limitation. However, we think that this assumption is well justified by the structural propertics 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 func-
tions can be found in several articles, such as Kripfganz & Schulzo (1987): ; Zalgaller (2000);
Wang 2004); Schlüter & Darup (2021). This was imitiated in the 1-dimensional case by
Bittner 1970), and already laid out for positively homogeneous functions in general dimen-
sions by Melzer 1986). Typically, such decompositions are based on certain representa-
tions of CPWL functions, which have been constructed, e.g., in Tarela Martinez (1999) )
Ovchinnikov (2002); ; Wang & Sun (2005); see also Koutschan et al. 20223 2024) for fresh
perspective. These representations also help to understand the representative capabilities of neural networks, see Arora et al. (2018); Hertrich et al. [202]]: |: Chen et al. (2022)
Recently, a minimal decomposition for the 2-dimensional case was given by Tran & Waan (002)). 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 McMullen (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
Hertrchh Brandenburg et al. (0024).
e.g. Zhang et al. (2018): Hertrich et al. (2021); Montúfar et al. (2022) Haase al. (2023)
Submodular functions are somctimes called the discrete analoguc of convex functions, and optimizing over them is a widcly studied problem, which is also relevant for machine lcarning. submodular function can be minimized in polynomial time (Grötschel al. 1981). In
analogy to DC programming, this sparked the idea of minimizing general set function by representing it as a difference of two submodular ones [Narasimhan & Bilmes 2003 Iyer & Bilmes| 2012 El Halabi al. 2023). Related decompositions were recently studied by Bérczi et al. 2024j. 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 theo- rems [Cybenko) 1989), and specializing ReLU networks, their number of pieces, well
as septh-wiith--raddee tradeoffs (Telgarsky 2016 Eldan & Shamir 2016 Arora et al. 2018). In addition, Hertrich & Skutella (2023) Hertrich & Sering (2024) provide neural network con- structions for CPWL functions related to combinatorial optimization problems. Geometric insights have also proven to be uscful to understand the computational complexity of train- ing neural networks (Froese et al.) 2022: [Bettcchinger et al. 2024 Froese & Hertrich] 2024). Recently, Safran et al. (2024) give an explicit construction of how to elficiently approximale the maximum function with ReLU nolwsrks.
2 PRELIMINARIES
In this section we introduce the necessary preliminaries on polyhedral geometry and CPWL functions. For m E N, we write [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 it bounds closed halfspace containing P, and any intersection of P with such supporting hyperplane yields a face F of P. A face is a proper face if F C P and inclusion-maxima. proper faces referred to as facets. A polyhedral cone C C Ra is polyhedron such
3

---

Published as a conference paper at ICLR 2025
that du + pe C for every u, C and X. fu E Rz0. The dual cone of C' is CV fy E (R")* (z. v) 2 0 for all x E C}. cone is pointed it does not contain a line. A cone C' is simplicial, if there are linearly independent vectors UI...., Up E R" such that C= - devy | X 03. For a cone C and t E IR", we call t C a shifted cone or translated cone.
A polyhedral compler P is a finite collection of polyhedra such that ()) (ii) PP then all faces of P are in P, and (iil) if P. E P, then PnP' is a face both of P and P'. For a polyhedral complex P in R", we denote by p the set of d-dimensional polyhedra in P. Given two n-dimensional polyhedral complexes P, 2, the complex P is refinement of Q if for every т E Pm there exists a E Q" such that T C a. The complex Q coarsening of P if P is a refinement of Q.
The slar of a face T E P is the set of all faces containing T, L.e, starp(r) = (o E c... We only consider complete polyhedral complexes, i.e., complexes covering R 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 weight function w w: p I, as we describe as follows. Given a face a E P, we denote by aff(o) S I" the unique smallest affine subspace containing The relative interior of is the interior of inside the affine space aff For any dimonsion d $ n and any т E ppd-1, E pá with 7 S a, let eafr R" be the normal vector of with respect to d, that is, the unique vector with length one that is parallel to aff(o), orthogonal to aff(r), and points from the relative interior of into the relative interior of a. A pair (P, w) forms a balanced (weighted) polyhedral compler if the weight function satisfies the balancing condition at every ppn-2
2 (sec Figure lal:
Σ rEPR-1
w(o) 6a/T O.
TJT
We will see (Lemma 3.2 that considering only faces of codimension 2 indeed makes sense, see also the structure theorem of tropical geomeiry (Maclagan Sturmfels 2015).
Continuous Piecewise Linear Functions. A contimuous function f: R 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 / E pa is an affine function. If this condition is satisfied, we say that f and P are compatible with each other.
In line with Chen al. (2022), we define the number of pieces q of f to be the smallest possible number [P"] of full-dimensional regions of compatible polyhedral complex P. Note that this requires pieces to be conver sets, as they are polyhedra. The function might realize the same affine function on distinct pieces P,Q E Pr. To account for that, we define the number of affine components ie to be the the number of different affine functions realized on all the pieces in pm, Note that this quantity is independent of the choice of the particular compatible complex P.
It holds that A < y S k! and each of these inequalities can be strict, compare the discussion by Chen et al. 20222). We can assume that k > n (and thus q > n) because otherwise f can be written
composition of an affine projection to lower dimension n' followed by CPWL function defined on g=d..
If f is a conver CPWL function, then it can be uniquely written as the maximum of finitely many affine functions f(z) max (z) such that k q. It follows that there is unique coarsest compatible polyhedral complex P,, namely the one with Pj- = {(x gi(x)) = max, (z)3) i E [k]]. In particular, we have k if f is convex. We call polyhedral complex P regular, if there exists a convex CPWL function f such that P = Py.
3 DECOMPOSITION POLYHEDRA
In this section, we introduce and generally study the main concept of the paper, decompo- sition polyhedra. These polyhedra describe the set of possible decompositions of CPWT.
4

---

Published as a conference paper at ICLR 2025
-22
0 x3
21
81 - 2 x2
0 I 22
22
S 0
22 50 æ1
0
S 5
31
V2
(a) Parameterization of the median function via the weights on the 1-dimensional facets.
(b) Parameterization of the median function via its linear maps the maximal polyhedra.
Figure 1: Two different parameterizations of the function that computes the median of x2, This function has g pieces and k == 3 alline components, see Example A.1 for more details. In Figure Ta 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 h that are iompatible with a given polyhedral complex. We start by establishing a handful of general results concerning the space of CPWL. func- tions compatible with 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 linear subspace Vp of the space of continuous functions.
Let Aff(R") be the space of affine functions from R. to R. For many of our arguments, adding or subtracting an affine function a E Aff does not change anything. particular, function f is convex if and only if f is convex. Therefore it makes sense define the quotient space Vp == Vp AfT(R"), where we identify functions in Vp that only dilfer by adding an affine function. The following lemma shows that we can parameterize a function f T Vp by keeping track of "how convex or concave" the function is at the common face E pp--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
the proof adapted to our setting.
Lemma 3.2. The vector space Wp = {w: pa + IR (P,w) is balanced] is isomorphic to Vp.
For a function f E Vp, let wy E Wp be the corresponding weight function according to Lemma 3.2 Figure illustrates the different parameterizations of the median function according to Lemma 3.2 Moreover, from Lemma 3.2 we can deduce that Vp finite-
dimensional (Corollary E.1 and the following proposition.
Proposition 3.3. A function
Vp is conver if and only if wy is nonnegative. Morcover, f is conver with p = P, if and only if w is strictly positive.
The set V of conver functions in Vp forms polyhedral cone (Lemma E.2 In the following, we now fix function f Vp and consider the space of decompositions differences of convex functions which are also compatible with P. In Lemma E.3 we show that for a regular complex such a decomposition does indoed always exist. In particular,
h into
Vp = (V.). which implies that dim(Vp) = dim().)).
Definition 3.4. For a CPWL function f and a polyhedral complex P, the decomposition polyhedron of f with respect to P is Dp( ((ghh) g, h E V / g h}.

---

Published as a conference paper at ICLR 2025
The projection x((g.)) = induces isomorphism between Dp(f) and x(Dr(f)) since Dy(f) (9. E r(D((f))) We now show that this is indeed a polyhedron, which arises as the intersection of two shifted copies of cone.
Theorem 3.5. The set Dp(f) a polyhedron that arises as the intersection of conver functions with an affine hyperplane H; (()hh) | g namely Dp(f) (Vp x VD) H Under the bijection n, the decomposition polyhedron is the intersection of two shifted copies of the polyhedral cone Vp- More specificully, x(Dp([)) = n (Vp + f). Remark 3.6. Under the isomorphism of Lemma 3.2 we identily Dp(f) with the polyhedron {(Ug: wx) E W Wi Wgg - wh = w } in Wp x Wp and (Dp(ff) with the polyhedron [wg E W Wy 2 wy), where W = (w E Wp w 20.
For the remainder of this section, we analyze the faces of the polyhedron Vp in terms of the properties of the corresponding decompositions.
Definition 3.7. A dccomposition (g. h) E Dp(f) called reduced, if there is no convex function o E D \ {0} such that g & and h o are both convex.
If decomposition is not reduced, then we can obtain a "better" decomposition by simulta- neously simplifying both and h through subtracting convex function é. Hence, it makes sense put special emphasis on reduced decompositions. Conveniently, the following theorem links this notion to the geometry of Dp(s).
Theorem 3.8. A decomposition hg E Dp(f) reduced if and only if (g, h) is contained in bounded face of (f()).
Definition 3.9. We call a convex function g E x coarsening of another convex function
g' V if the unique coarsest polyhedral complex 'P of is a coarsening of the unique coarsest polyhedral complex Pgr. For a pair of convex CPWL functions (g, h); we call (g', , h²) coarsening of (g, h) if g h g' h and and h are coarsenings of g' and h' respectively. The coarsening is called non-trivial if (Py.Ph) + (Pg. Pw.). For a function f E Vp, let (J) = (o E pn-1 wg(o) 03.
Lemma 3.10. A conver function g' E V is coarsening of g Vi if and only if suppp(g') S (g). The coarsening is non-trivial if and only if supp c suppp(g). Theorem 3.11. Let (g, ft) Dp(f), then the following three statements are equivalent: 1. There no non-trivial coarsening of (g. h).
2. (g. h) is a verter of (f(
3. (y, h) is a verter of Do() for all polyhedral complezes Q compatible with and h. Definition 3.12. A decomposition (g. h) E Df( is called minimal, if it is not dominated by any other decomposition, that is, if there is no other decomposition (g',h') h!) E Dp(ff) where o' 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 visualization.
Phrasing it in terms of multi-objective optimization, we require that the number of pieces of J and g in minimal decomposition are Parelo-oplàmal. The number of pieces relates to the notion of monomial complezity studied Tran & Wang (2024). and minimal decomposition translates to a decompasition 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) E Dp(J) is always verter of Dp()).
This thcorem implics a simple finite procedure to find a minimal decomposition: enumcrate all the vertices of Df(f) and choose one satisfying Definition 3.12 It also suggests the following important special case.
Proposition 3.14. If Dp(f), or equivalently π (DD(ff)) has a unique vertez, then this verter corresponds to the unique minimal decomposition within (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(s)) V nvp + f), where

---

Published as a conference paper at ICLR 2025
V is a convex, pointed polyhedral cone. In Lemina E.6 we give some sulficient conditions for such intersections of shifted cones to yield a polyhedron with unique vertex. Moreover, the support of decomposition can serve as certificate to verify if decomposition is unique vertex, and hence minimal. For f E Vp, let supp = fo E P wy(a) > 0} and suppp(f) = fo {a E0 E (y(o) < 0}.
Proposition 3.15. for f & Vp, there are h E V such that g and (f) (g) as well as supp " (f) suppp (h), then (g.h) the unique verter of De(f) for every regular complete compler Q compatible with f. In this case, 9 and h have at most as many pieces as f.
While Proposition 3.15 sounds technical, it is powerful it allows to prove that important functions satisfy the condition of Proposition 3.14
Definition 3.16. A hyperplane function with & hyperplanes is a function f: R" + RR given by f(z) Eie(s] d max a.) b,, (2,c.) d for any a, R", ,,,,,,,,, d4, X E IR, E [K].
Hyperplane functions are precisely the functions that are computable by a ReLU neural network with one hidden layer and appear in this context 2-term max functions (Hertrich
ct al. (021)) They also coincide with functions computable with the hinging hyperplane model Breiman (1993); Wann & Sun (2005t). Morcover, in Example D.14 we will see that hyperplane function ions include continuous extensions of cut functions.
Definition 3.17. The k-th order statistic is the function f: R" > that returns the k-th largest entry of an input vector R". For k - 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 Proposi- tion 3.15 provides 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(J)) (
is reduced if and only if il is the optimal solution of a lineur program with feasible solutions (DD(()) and objective linear functional contained in the interior of the dual cone of V In particular, if (Dp(ff) has single verter, then the unique optimal solution is the unique reduced and minimal decomposition. Under the isomorphism to Wp, the objeclive function u. can be chosen as u(o)= = for all a.
ANALYSIS OF EXISTING DECOMPOSITIONS
Constructions of decompositions of CPWL. functions difference of two convex functions have appeared in many contexts. In this section, we relate some of these existing construc- tions our framework. Moreover, we provide counterexample proposed by Tran & Wang (0244) to obtain minimal decomposition in general dimensions.
construction which was
Hyperplane extension and local maxima decomposition. The literature contains 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, ht) in a way such that. they are compatible with the complex P that arises by extending the codimension-1 faces of P, 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 de- scribe 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 CPWL function such that constructions B.1 and B.2 do not provide a verter of Df(f) for any regulor polyhedral compler P compatible with J.
Moreover, Proposition B.3 shows that the suboptimality of the existing decompositions in the literature not caused by the concrete construction method, but rather by the polyhedral complexes underlying these methods.
Minimal decompositions,
construction for unique minimal decomposition for certain CPWL functions f in dimension 2 was presented by [Tran & Wang (0024), by intro- ducing& single new I-dimensional face to Py and an adapted weight function to satisly 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 Py is a polyhedral fan. Such functions are the support functions of their Newton polytopes, 1.2) and Maclagan & Sturmfels (2015. Chapter 2).
describe in more detail in Appendix C.1 also Joswig 22021 Section
propose a procedure to reduce the n-dimensional case to 2-dimensions via projections, which we describe in Con- struction C.2 in Appendix C.2 The final step in this procedure is to construct global function in dimensions by "gluing together" the projections. In Example C.3 we illustrate that this final step not always well-defined. Our conclusion is that the construction by Tran & Wang (2024) does not extend beyond the 2-dimensional case, lcaving it an open problem to find any finite algorithm that guarantecs return a minimal docomposition without fixing an underlying polyhedral complex. Note that for any fixed underlying poly- hedral complex, Theorem 3.13 implies a finite algorithm by enumerating the vertices of the decomposition polyhedron, as discussed earlier.
Based on their 2-dimensional construction, Tran & Wang 2024
5 SUBMODULAR FUNCTIONS
We demonstrate that a special case of our framework is to decompose a general set func- tion 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 (*) hyperplanes the vector space of set functions from 2 to RR.
I.j. with 1 S <i<j S n, and let F, be
Proposition 5.1. The mapping & that maps f E Vp to the set function F(S) = f(1s), where 1 Eies Ci2 is vector space isomorphism.
Conversely, starting with a set function F, then f= (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 provides a link between discrele submodular functions and continuous convex functions.
Definition 5.2. A set function F: 2(m) + R is called submodular F(A) + F(B) 2 F(AU B) + F) for all A, C [m]. F is called modular if equality holds for all A, B C [m].
Since a set function submodular if and only if its Lovása extension f + ( is convex Lovássz (1983), we can specialize Problem 1.1 in the setting of this section as follows.
Problem 5.3. Given set funclion F Faz how to decompose il inlo difference of
submodular set functions such that their Lovúsz exlensions have as few pieces as possible?
Having 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 argue in Appendix D for accordingly normalized submodular functions, the number of picces of the Lovász extension is preciscly 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 to the setting of submodular functions.
we can translate our results from Section
8

---

Published as a conference paper at ICLR 2025
Corollary 5.4 (informal). The set of decompositions of a general set function into dif- ference 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 resulls, the irreducible decompositions correspond precisely to the bounded faces of that polyhedron and every minimal decomposition is verter.
Example D.14 shows that the Lovász extensions of cut functions are hyperplane functions and thus admit 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.
NEURAL NETWORK CONSTRUCTIONS
In this section we consider the following question: Given a CPWL function f: R + R with q pieces and k alline components, what is the necessary depth, width, and size of neural network exactly representing this function? To this end, we first discuss the necessary background 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
difference of convex functions.
Background. For a number of hidden layers d 2 O, a neural network with rectified linear wnit (RcLU) activiations is defined by sequence of d+11 affine transformations T, R - R" E [d + 1j. We assume that Wo n and nd++1 = 1. If a denotes the function that computes the ReLU function x + max (1r, 0} in each component, the neural nelwork is said to compute the function f: R" + R given by f == Ta+1 o a Ta a o ...... o. o T2. We say that the neural network has depth ++1 width max R4, and size Eie(q n4.
is well-known that the maximum n numbers can be computed with depth [log n] + and overall size (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 rep- resentations 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: R.
with k affine components can be repre- sented by neural network with depth [log (n + 1)1 + and overall size O(k+tI).
The second one goes back to
Chen et al.
(002) and is based on the lattice representation Tarela & Martinez (1999).
of CPWI, functions, compare
Theorem 6.2 ( (Chen et al. 2022 ). Every CPWL function f: 12" + R with pieces and
affine components can be represented by neural network with depth [log, pl + [log2 q1 + and overall size (kg).
As noted before, one can assume that n < k S q, since otherwise we could affinely project to a lower dimension without losing information. In fact, would usually assume that the input dimension n is much lower than the number of affine components k. Therefore, Theorem 6.] 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 these representations? In other words: can we smoothly interpolate between the low- depth 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 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 conver CPWL function f: R" + R with l offine components be represented by a neural network with depth [log,(n + 1) + [log, rl + +1 and overall size O(rs+1), ) for any free choice of parometers r and s with 2 k = q-
9

---

Published as a conference paper at ICLR 2025
In order to see how this provides tradeoff between the representations of Theorem 6.1 and Theorem 6.2. is worth looking at the extreme cases. If we choose r = 1 and s k, we exactly obtain the bounds from Theorem [.1] On the other hand, if we choose
& and 8 = 1, we obtain a neural network with depth Olog k) and size (kk, 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 (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 interpolate between Theorem 66.1 and Theorem 6.2 but it has the big
limitation that it only works in the convex case. Simply mixing the two known representa- tions of Theorems [6. and 6.2 docs not appear to work 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 dif- ference of two convex ones and then apply Theorem 6.3 to these two functions. To do this efficiently, requires to find a good answer to Problem
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 For example, obtain the following result by combining Theorem 6.3 with Lemma E.3
Corollary 6.4. Let f: R R be CPWL function that is compatible with a regular polyhedral compler P with q = (pm| hall-dimensional polyhedra. Then, I can be represented by a newral network with depth [log2 (n + 1)] + [log2 r] + and overall size O(rs*t1,, for any free choice of parameters and with TS 2 q.
For given CPWL function f, provided that one can find regular polyhedral complex such that ğ is not much larger than the number of pieces q, Corollary 6.4 does indeed provide smooth tradeoff between Theorem 6.1 and Theorem 662 in the general, nonconvex case. As q is the minimal number of fulkdimensional polyhedra in any (potentially nonregular) polyhedral complex compatible with f, the big question is how much of restriction the assumption of regularity might be.
OPEN PROBLEMS
From the thelretical 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 crist a decomposition g h such that the namber of pieces of and h is polynomial in n and 9
Note that by definition, f is compatible with a polyhedral complex P with |P~| = To answer Problem 7.1 positively, by Lemma E.3 would be sufficient find regular poly- hedral complex @ with [Q"| poly(n,g) 9) 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 regular complex Q Therefore, to solve Problem 7.1 one needs to answer the following ques- tion: given an arbitrary complete polyhedral complex P, what is the "coarsest" refinement of ' 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 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 propertics 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 broad avenue for future research.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Maric-Charlote Brandenburg was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foun- dation. Moritz Grillo is supported by the Deutsche Forschungsgemiinccaal (DFG, German Research Foundation) under Germany's 's Excellence Strategy The Berlin Mathematies Re- search Center MATH+ (EXC-2046/L project ID; 390685689). Part of this work was com- pleted while Christoph Hertrich was affiliated with Université Libre de Bruxelles, Belgium, and reccived support by the European Union's Horizon Europe rescarch and innovation program under the Maric Sklodowska-Cuu grant agreement No 101153187-Nourxxx
REFERENCES
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--000999 009-922-99
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learving Representaltons, 2018.
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is 3RR-cmpllte. Advances in Newral Information Processing Systems, 36, 2024.
L. Bittner. Some representation theorems for functions and sets and their application to nonlinear programming. Numerische Mathemalik, 16(1):32 51, February 1970. doi: 10. 1007/b/02162405.
Marie-Charlotte Brandenburg, Georg Loho, and Guido Montufar. The real tropical geometry of neural networks for binary classification. Transactions on Machine Learning Reseorch, 2024.
L. Breiman. Hinging hyperplanes for regression, classification, and function approxima- tion. JEEE Transactions Information Theory, 99(3))099--013, 1993. doi: 10.1109/18. 256506.
Kristóf Bérezi, Boglárka Gehér, András Imolay, László Lovász, and Tamás Schwarcz. Mono- tonic decompositions of submodular set functions, 2024. arXiv:2406.0411 047288.
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 mini- mization via DC programming. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9172 9201. PMI.R, 23-29 Jul 2023.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning (heory, pp. 907 940. PMLR, 2016.
Vincent Froese and Christoph Hertrich. Training neural networks is NP-hard in fixed di- mension. Advances in Neural Information Processing Systems, 36, 2024.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775-17799 1790, 2022.
11

---

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 ReLU neural networks via lattice polytopes. In International Conference on Learning Representations, 2023.
Christoph Hertrich and Leon Scring. ReLU neural networks of polynomial size for exact maximum flow computation. Mathematical Programming, pp. 30, 2024.
Christoph Hertrich and Martin Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS journal on computing, 36(5)1109--1097, 2023.
Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards lower bounds on the depth of ReLU neural networks. Advances in Neural Information Processing Systems, 14: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-Fightt Conference Uncertainty in Artificial Intelligence, UAT12, pp. 407-417, 2012.
Katharina Jochemko and Mohan Ravichandran. Generalized permutahedra: Minkowski linear functionals and ehrhart positivity. Mathematika, 68(1):2117-2)) 236, January 2022. doi:
Michael Joswig. Essentials of Iropical combinatorics, volume 219 of Graduate Studies in Mathematics. 2021. ISBN 978-1-4004-6741-8.
Christoph Koutschan, Bernhard Moser, Anton Ponomarchuk, and Josef Schicho. Repre- senting piecewise linear functions by functions with small arily. Applicable Algebra in Engineering, Communication and Computing, pp. 1-16, 2023.
Christoph Koutschan, Anton Ponomarchuk, and Josef Schicho. Representing piccewiso- linear functions by functions with minimal arity. ar preprint 2aoo:40660222,, 2024.
Anita. Kripfganz and R. Schulze. Piccewise affine functions difference of two convex functions. Optimization, 18(1):23-25 29, 1987. doi: 01110000233138708880
Hoai An Le Thi and Tao Pham Dinh. De programming and dca: thirty years of develop- ments. Mathematical Programming, (1):5):5 68, 2018.
László Lovásu. Submodular functions and convexily. Mathemalicul 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. McMullen. Weights on polytopes. Discrete & Computational Geometry, 15(4):363-388,
April 1996. doi: 10.1007/bR02711550
Melzer. On the expressibility of piecewise-linent 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. SLAM Journal on Applied Algebra and Geometry, 6(4):618 649, 2022.
Mukund Narasimhan and Jeff Bilmes. submmouula-sspperoouula procedure with applica- tions to discriminative structure learning. In Proceedings of the Twenly- First Conference on Uncertainty in Artificial Intelligence, UA1'05, pp. 404 412, 2005.
Sergei Ovchinnikov. Max-min representation piecewise linear functions. Beitrüge Algebra Geom., 43(1):297-333 302, 2002. ISSN 0138-4821.
12

---

Published as a conference paper at ICLR 2025
Itay Safran, Daniel Reichman, and Paul Valiant. How many neurons does it take to ap- proximate the maximum? In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.
SIAM, 2024.
Nils Schlüter and Moritz Schulze Darup. Novel convex decomposition of piecewise afline functions, 2021.
JM Tarela and MV Martinez. Region configurations for realizability of lattice piccewise- linear models. Mathematical and Computer Modelling, 30(11-12):17227, 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) 59, 2024.
Shuming Wang. General constructive representations for continuous piccewise-linear func- lions. JEEE Transactions on Circuits and Systems I: Regular Papers, 51(9):1889-11 1896, 2004. doi: N0.1109/TCST.2004.8553
Shuning Wang and Xusheng Sun. Generalization of hinging hyperplanes. IEEE Transactions on Information Theory, (1(12):4425-44 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 1573- 8795. doi: 10.1007/s10956 101-0995800000000--4
Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural net- works, International Conference on Machine Learning, pp. 5824 5832. PMLR, 2018.
13

---

Published as a conference paper at ICLR 2025
A EXAMPLES
A.1 DIFFERENT PARAMETERIZATIONS OF MEDIAN FUNCTION
Example A.1 (Median). In this example, we have look the different parameterizations for the function that computes the median of 3 numbers. To have a 2-dimensional example, we set 23 = 0. Let the polyhedral complex
be induced by the maximal polyhedra P= {xr E I Tx(1)) S Tx(2) (x(3)) where æ: [3] + [3] is permutation and f: R + I be the function given by fle, (z) = 2x(2). The function f has concave breakpoints whenever the median and the higher coordinate change, i.e., the facets that are given as 0x,1 {o IK2 (n(1) I Tx(2) *x(3)} and convex breakpoints whenever the median and the lower coordinate change, that is, the facets that are given as 0n {x R² 2x(1) (x) S (x(3))- Since |le1 e2ll2 = 2 and ||ea = ||ell2 = 1, it holds that
wy((m,1)= -V2 T+(1) = 2z (n) # 2z
and wy((n.2) = [22 Tx(3) = 23
x3( # 43.
See Figure for 2-dimensional illustration.
A.2 ILLUSTRATION OF DEFINITION 3.
pieces of
pieces of g
pieces of h
pieces of h
(a) The blue point corresponds to minimal decomposition.
(b) The blue point corresponds to decompo- sition that not minimal.
Figure 2: Visualization of minimality, where a decomposition (g. h) is described by the number of pieces of and decomposition minimal, 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: R" + R be hyperplane function given as f(x) Eiels X; max a.) + by (x, e.) + d... We can assume without loss of generality that the hyperplanes
H; {o E R" (z, a.) + b, (z, c) + d3}
are pairwise distinct, because otherwise we can simply adjust d₁ The polyhedral complex P induced by the hyperplane arrangement {Hi))ejk is compatible with f. The convex functions 9, h given by
g(x) Σ >e (x, +b, (z. ct) +di) and h(x) - Σ X )- A,20
a.) (2,
A:<0
the unique minimal dccomposition of since (uppp(g) supp
(o 0 p lo
Ux.20 H.} and (h) (S) (a pa-1 Us.co H.).
14

---

Published as a conference paper at ICLR 2025
Example A.3 (Minimal decomposition of k-th order statistic). We construct polyhedral complex that is compatible with the function f: I= + R that outputs the k-th largest entry of Rd. For U [n] with [U| l and i E [n] \ U, let
Pa,r - {- E IR" x S 2; S Σ W
All such polyhodra and their faces form a polyhodral complex P that is compatible with the function f: R + R given by f(Pr,v) = Z4. It is not hard to see that f h where E Vi are convex functions given by
g(x)
max [[
Σ iE!
and Mxx)
max sg
Σ J4
=
1
iEi
Moreover, let otj.U = fx E R (g) (f) foru I
2i. < zj
S 3m for all m E U, E [n] U}. Then {orj.u
n UI k+1} and (h) sfppp(f)
U US [M] | = k). Thus, Proposition 3.15 implies that h) is the unique vertex 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 hyperplane, and the function g is defined as the sum all these functions. To analyze in our framework, let P be any polyhedral complex that is compatible with f and let wy E Wp be the weight function corresponding to f. For E p let Ho be the hyperplane spanned by a and A [H, wy(o) > 0} be the hyperplane arrangement consisting of the hyper- planes supporting the breakpoints where is convex. Let HJ be the common refinement of the polyhedral complex induced by A} and P. The weight function wn pn-1 + R wy(a') in Wxy and nonnegative and hence the corresponding oCH, "y((')>0
single
given by uy(a)= = Σ
function g E Vug is convex. It follows that h = 9 is convex as well, yiclding the desired decomposition.
Construction B.2 (Local Maxima Decomposition). Let [PI...,,Pm, p and fi be the unique linear exlension f|p,. Moreover, let M, == (j E [m] f((x) 2 [z(x) for all a E P.)
and 9 = maxjeM, Pj. Then
= kE|m]JEM sE(m]
min max fr = min g:
and == Eie(m) Ii is a convex function. Furthermore, let h2 = g gss then = max hi is convex function as well and it holds that
g h g
max (g 9:) = g (g min gi) 9 (g = iE(m)
(Eim
Let Hi = fo E RD f1(x) [イ(r)} and A, (Hi, i # j}. Furthermore, let Hy be the polyhodral complex induced by the hyperplanc arrangement Ay. Then we have that g, VH,-
Proposition B.3. There is a CPWL function f and convex CPWL functions g, h with f= g h such that every decomposition (g' (g',h") E DH, (f) well every decomposition 1') E E ENttDt (f) is dominated by (g. h).
Proof. T.et P be the polyhedral complex in R² with rays P cone((1,0), P2 cone((0. 1)), Pa = cone((1,2) and P4 = cone 1)). Let wy(p1) = wy(p2) = and (ps))) = (p4)
v's Then according to Theorem C.1 the unique minimal decomposition is given by the
complex obtained by adding the ray Ps cone(((11,11) and the weight function
(y(()
p (f)
(p(
p (U)
V2
p = ps
15

---

and i E [n] \ U, have that Published as a conference paper at ICLR 2025
as well w/, Wg wy. Nevertheless, the ray Ps is not contained in (the support of) Hy and hence this solution not in Di, (f). Since (g. h) is the unique (up to adding linear function) minimal decomposition, follows that any solution Dxy(f) must be dominated by (g, h). Since H} is coarsening of Hy, it holds that every decomposition in Dzy (ʃ) is contained in Due, (f) as well, impyling the result for n3 (f).
B.1 EXAMPLES OF EXISTING DECOMPOSITIONS
(hyperplane extension of k-th order statistic). Let be the function from Example A.3 For any i,j E [n] and U S [n] with i E and [U] = k + holds that Uig.U E supp (f) and Hor = {x R" = zj}. Hence, Pg is the braid fan and it holds that g(x) (_m) Lizj (x;, Thus, the unique vertex (g" 11*)) from Example A.3 is clearly 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 (f( for any regular polyhedral complex Q.
Example B.4
V2
2
31 + 202
202
202
2,2
2w1 122
2.11
0
02
2m11
0
202
31
V2
(a) g(x) max(22,00
max(11)22)) + max((r1 0) +
(b) h(x) g(x) [(x), where f is the median.
Figure 3: The hyperplane extension of the median (second largest number) of 0, 21, (i.e. n = 3) (Example B.4). which agrees with the local maxima decompasition (Example B.5
up to a factor 2. These representations do not agree for the median when n n>> 3.
Example B.5 (local maxima decomposition of k-th order statistic). Let f be the function from Example A.3 Then, for [n]] with |U]
(.,((z) = max Tz. Thus, jENN/
((x) (x) (n 1
Σ
max JES
9CMd
|S|=n-k+1
Note that 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 C [n] such that [T] k and any bijection m: [k] + [n] T, let.
Pr. = (ar E TR"
x3 S Tx(1) S (T((t))))E))
follows that the set of full-dimensional cones P of the unique coarsest polyhedral complex Pg compatible with g is given as Ph = (Prr) Again, the unique vertex (g", ht) from Example A.3 is clearly non-trivial coarsening of the decomposition obtained from the lattice representation and hence the decomposition cannot be a vertex of Do(f) for any regular polyhedral complex Q.
16

---

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 New- ton polytopes, adapted to our setup.
posilively homogenous convex CPWL function a function f such that f(0) = 0, and Py is polyhedral fan. In this case, it can be written as f(z) maXie(K] (2, v,), where E IR".. We define the Newton polytope of f as the convex hull Newt(f) = conv(ri,..... uk). Then f is the support function of Newt(f), ie., f(x) = maxpeNewi(f) (p, Z). We now give an interpretation of Py and wy in terms of the Newton polytope.
Given any n-dimensional polytope P C R", the (outer) normal cone of a k-dimensional face F of P is the (n diddinnnsinnaal cone
NP x
x e R" (2,2) = max x) for all 2 F}
(1)
pEp
In particular, if = New and v is a vertex of P, then the description of the normal cone turns into
N. (Newt((f)) = E E R" (v, f(x)}
and agrees with a maximal polyhedron in Py. The normal fan of a polytope is the collec- tion normal cones over all faces. Thus, for positively homogeneous convex functions, the polyhedral complex Py 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 Py and Newt(f) also establishes a bijection between faces a E -Pj-1 and edges of Newt(f), and for the corre- sponding weight function wy E Wp holds that wy equals the Euclidean length of the edge that dual σ. This correspondence extends to general convex CWPL functions, where Py is complex which is dual to polyhedral subdivision of Newt( and wy corresponds to lengths of edges in this subdivision (Maclagan & Sturmfels
2015
Chapter 3.4).
C.2 THE CONSTRUCTION FROM TRAN & WANG 2004
The duality between positively homogencous convex CPWL functions and Newton poly- topes, described in Appendix C.1 serves a motivation for Tran & Wang 22224) to construct minimal decompositions J= g h of positively homogeneous CPWL functions as the difference of two convex such functions in dimension 2.
Theorem C.1 (Tan & Wang 2024 For every positively homogeneous CPWL-fumction R: + exists a unique (up to adding a linear function) minimal representation as difference of two conver functions h.
The decomposition can be obtained as follows. Let Py be 2-dimensional polyhedral fan compatible with f with rays PI.....Pry Pm C R² and ray generators ri,..., I'm E R² such that ||rill for 1,...,m. m. Furthermore, let wy be the corresponding clement in Wp, and w = max(wy;:0 0). We now define an additional ray pm+1 with ray generator Tm+1 = - >m max(w)(p:), 0)r, and convex function through the weights
(y(pp)
if w w > 0, i [m]] if (w) S 0, i E [m]
(p.)
Dm max (w (pt),
if +1.
This defines the convex functions g, = g- f. f, and results in a minimal decomposition f= -- h in the 2-dimensional positively homogeneous case. Considering this construction through to the duality to Newton polytopes, we can identify rays of Py which correspond to convex breakpoints of f with edges of the Newton polytope Newt(g), and the construction from Theorem C.I 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.
17

---

Published as a conference paper at ICLR 2025
Construction C.2 TTan & Wang 2024 Section 4.1)). Let f: R" + R be positively homogeneous CWPL-tunction and a polyhedral fan compatible with f. The attempt is to balance wi locally around every E pa-2 and then "glue together' the local balancings to a global balancing. So, for some T E p suppose that fol.... oe} = starp(T) are the cones containing т. The rays spanned by ez./T that inherit the weights w (a:) for i i [A] induce a 2-dimensional fan Pr in the 2-dimensional lincar space span(r) orthogonal to span(r). Let Pr be the polygon in span(r)* corresponding to the minimal balancing of wj regarded as map w/ P7 + R. Now proceed with the following steps.
1. For every T E pn-2, construct the polygon Pr.
2. Place the polygons P. in IR" in such way, that whenever 71,72 ppn2 are faces of E suppp(f), then the edges Pr, and Pr2 that correspond a are identified with each other.
3. Take the convex hull Pg of the polygons {Pr)repm-2.
4. The support function y of the polytope Pg and h = g- f are a decomposition of f-
One can check that for some p=-1 and pa-? being face of o, the edge e, of length w(o) which is perpendicular in span(r)* to r is independent of the choice of the face In particular, the direction of the edge eo is normal to the hyperplane spanned by a. 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 E p the edges of the polygon Pr be given in cyclic way {eo...... Com J. Placing a polygon P. refers to choosing an 2, E R" and defining the placed polygon as P+(++) conv + ca, + Ca + Co....., Ir + -i= Placing them in a coherent way means choosing an Dr E R² for every E p such that Pr. (x+)) n Pr, ( = conv(ro, ea) for some 26 E R" whenever Tı and 72 are faces of a. A priori it is not clear that such 2, always exist. The following example will in fact show that the resulting linear equation system not always yields a solution.
m Cam)
C.3 COUNTEREXAMPLE TO THE CONSTRUCTION
In the remaining of this section, we give counterexample to Construction C.2 which is stated in TTan & Wang (2024) in terms of (virtual) Newlon polytopes as potential generalization of the 2-dimensional construction higher dimensions.
Example C.3 (Counterexample to Construction C.2 Figure is an illustration of 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: R + R given by
f(x) max(0, (0, max [minf22,2 - -211 (JE)
#j
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 et be the i-th standard unit vector. The rays are given as follows:
pl = =<cone(-e)) cone(e;), cone(es),cone(:;; + ee),, cone(e: +e, + 2ex), cone(e; + 2e, + 2ex), cone(e: + e; + 2ex), cone(e: + +ej + ex) i k E [3] pairwise distinct)
+ej+ee
and the 2-dimensional cones
p = (conn(e,, -e;), conel e te + 2ex), www.ococccoo + ex). conc(en, tej + 2cx).
conc(e, + Cb, Gs + ej + 20x), conc(e: + eg + 26,, e: + 2e, + 20x), conc(e; + Cj + 2c,, e + ej + cx),
cone(e; + 22g 2ex, ej + ee + ex), cone(e; ek, + 2e, + 2ex) j, k E [3] pairwise distinct)
18

---

Published as a conference paper at ICLR 2025
Cdy
Cas
P Pa
G
Cda
C02
Co
Ppr
Cae
Cas
Ca1s
Pa
Ca
Eda
Car
Ppz
Ed5
Edo
Figure 4: polygons that cannot be placed in a coherent way in R3
The weight function wy: p2 R given by
w(cone(e, - {j)) =
w(cono(-c, c ej + 2ex)) -3
w (ccone(-e;)) ex)) = v8
w (cooe(ee,, 2)x)) V2,
wccone(e; + + ej + 2ex)) = v3,
w (cone(e: 20, q + 2e, + 2ex)) = -5.
(conn(e, + 2c, e + ej + ex)) =2,
(conee(e; + 2e, + 26 + ej + ex)) = v2.
w<cone(e; + cx, 6 + 2ej 2cx)) 0
corresponds to the function f and is therefore balanced. See Figure 5 for a 2-dimensional illustration of P.
Consider the rays
P1 = cone (0, 1, 1)), P2 cone((1, co, 2)), cone(
We will see that the corresponding polygons Po,, Pos and Pp. equal the ones in Figure The 2-dimensional cones which are in the stars of the rays are the following:
01 = 10),
co, (1,2, 1)), Ø3 cone cone((0,1 1, (1, 11)).)),
0 cone((1, 1I), ds cone((1,1,2), (1, 1)), d6 cone((1,1,2) (0, 0, 1)), 07 conc((1,2,1), (0, 0)), ds = cone((1,2,1) (,),,))) dy =
1,),,
Ø10 cone (1,1,,,))) 1)), σ1
d12 = cone((1,1,1)) (2, 1,2),
013 cone (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.
19

---

Published as a conference paper at ICLR 2025
(0, 1,00
(0,0, -1)
07
(1,1,0)
0g
P3
(1,2,
12,2,
09
10
02
013
011
(-1,0,0)
P1 = (0,
21,
P1
1,1,1
(2, 1,
(1,0,0)
03
04
01
1,2) ---
(2, 1,2)
05
06
(1,0,1)
10,0,
(0, -1,0)
Figure 5: A 2-dimensional representation of P. The blue lines correspond to convex break- points of the function f, that is, a cone E p2 such that w(a) > 0. The concave breakpoints (w(a) 0) dashed and colored in orange. has no breakpoints the gray, dotted lines (w(a) = 0).
20

---

Published as a conference paper at ICLR 2025
Co2 = (0,2, ca2 = (L, (1,,, Eo2 = (-1,-1,1) co = (1, (1,-1,0) ca. = 1,,1,
6eo (-1,1,0, 60, (1, -1), c0s = (-1,1,-11 Egg = (-1,0,1), COLO (1, (1,01,0);
E01 (0, 6a12 = 0, Ea1s = 10,
In order to construct the polygons one needs consider the orientation of the edge (and the normal vector) in the particular polygon. One can convince themselves that the polygons Po., Pp, and Pe. of the 4 rays are given as:
(Tpp) conv(<p1 + Tp Eoi + Eogs Fp + ea₁ + Eo² + Eag)
(x conv (xpz - Cdgi Egg Eog, 22 - Eas Eo. c Egg Cos Eds Egg)
Pon(Ips conv - e02, loz + Coy,
eo, + eo, + Fpp Co2 + eor + Cox + Coo)
(Fp(F conv + eogs Ips + Eag + E010: Fps + to, + Eoio + eon Iips + Eoo + E010 + Eol1 + E0122
Jpa + Cog E0 + Co11 + E012 Eog: Tps Eog + E0 + Cos1 + E012 + Co. + E01s)
Figure 4 alrredy shows that they cannot be placed in a coherent way. To make this math- ematically precise, one obtains a system of linear equations for Tp Tpy TPg and ppy by plugging in the values for the normal vectors, that ensures that the edges for the same 2- dimensional cone in different polygons are identified. This linear equation system does not have solution.
D SUBMODULAR FUNCTIONS
This section is a detailed version of Section 5 where we demonstrate that a special case of our framework set funtions and translate our results to this setting. Such decompositions are popular approach to solve optimization problems as disussed the introduction.
docompose general set function into a difference of submodular
Definition D.1. The braid arrangement in R" is the hyperplane arrangement consisting of the ( hyperplanes vi = Ij, with 1 iiijjsn
For the remaining section, let P be the polyhedral complex arising from the braid arrange- ment. Let Fn be the vector space of set functions from 2(a) to R. We first show that functions in Vo are in one-to-one correspondence with the set functions Fr. To this end, for set S [n]], let 1g = Lieg e; be the indicator vector of S, that is, the vector that contains entries 1 for indices in and 0 otherwise.
Proposition D.2. The mapping that maps f E Vp the set function F(S) = s(1s) vector space isomorphism.
Proof. The map t is clearly a linear map. To prove that + is an isomorphism, we show
that a function Vp uniquely determined by its values { [1s]s[M) and any choice of real values {us (us)) give rise to function f e Vp such that f(1s) ys-
First, note that the maximal polyhedra P are of the form P. = {ar E R" Im(1) S S x+(n)} for permutation π: [n] + [n]. There are exactly the + 1 indicator vec- tors fis... contained in Px, where S, == {æ(n + 1- --)). i))....,T(p)))) [n)) for E [n] and So 0. Moreover, the vectors {1ls, Ji=0... are affinely independent and hence the values (((1s.))ioo.... uniquely determine the alline linear function flp,- Therefore, f is uniquely determined by {.f(1s,) )ss(())
Given any values (us) sg(m), by the discussion above, there are unique affine linear maps flp. yielding flp, (1s) ys for all S C [n] such that 1g Pa. It remains to show that the resulting function f well-defined on the facets pn-1, Any such facet is of the form
G = {x R² xT(1) S... S x()() 2x(++1) S ... S xz(1))
which is the intersection of P. and Pro(E,s4)) where (i, + 1) denotes the transposition swapping and + 1. However, the indicator vectors s1 ]e())) contained in on,
21

---

Published as a conference paper at ICLR 2025
subset of the indicator vectors contained in Px and Poo(ii41)- Therefore, it holds that flr, (x) = - (x) for all x E dnz implying that f is well-defined as CPWL function.
If we think this the other way around, starting with a set function F, then = $ (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). 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/(] + E, the Lovász extension f: R" + is defined by f(x) = Ei= (S;), where 0 = So C S C... C S [n] is chain such that E A, and À 2 0 for all i E [n 1] and do = 1- As
Remark D.4. many contexts in the literature, the Lovász extension only defined on the hypercube [0, 1|". For purposes, it is more convenient to omit this restriction, which 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 I, the Lovász extension writes x as an affine combination of indicator vectors S, and uses the coefficients of the affine combination to compute the value f(x). Following the intuition, see in the next proposition that & (F'(F)) is actually the Lovász extension F.
Proposition D.5. For a set function F Fn, the function f (F-((F) is precisely the Loná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 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 Tb (F). O
Definition D.6. A set function F: 2 + R is called submodulor if
+(A)+ + 2 F(AUB) + F(AnB)
(2)
for all A, S [n]. F is called modular if equality holds for all A, S [m].
The following well-known property is key to the insights of this section.
Proposition D.7 Lovász 1983 A sel function F is submodular if and only if ils Lovász
extension f == -- (F) is concer.
Applying our insights from Section to the previous proposition, we obtain the following well-known statement.
Corollary D.8. The set of submodular functions forms a polyhedral cone SM, 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 E Fa, how to decompose it into difference of submodular set functions such that their Lovász extensions have as few pieces as possible?
Having 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 special case of Problem [.] we are able to translate our results from Section to the setting of submodular functions.
Let. Mn C Fr 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 an affine function (Lovász) 1983). Since for any M Mns a set function F is submodular if and only if F submodular, we define the vector space F, F./M, of set functions modulo modular functions. Furthermore, let SM,, be the cone of submodular
22

---

Published as a conference paper at ICLR 2025
functions in this quotient. A decomposition HG E SM, XSM, of a set function F E Fu is called irreducible if there does not exist submodular function I SM, \ {0} such that G - I and H are submodular. Since a set function M E Fn is modular if and only T (M) is affine lincar, the isomorphism & of Proposition D.2 descends to an isomorphism Φ: Fn - Vp such that ((SMm) = =Vp-
For a set function F F the set of docompositions D(F) = ((G, E SM, x SM, = H) is polyhedron.
Corollary D.10. A decomposition (G, H) is irreducible if and only if (G, H) is contained in bounded face of D(F).
Proof. The extension of T5 to the cartesian product T क: Dp x Vp + F an isomorphism. Then the statement follows from the fact that D(F) = ( x (Dp (P) and Theorem 3.8
Definition D.11. For submodular function F: 2nm] defined as
R. the base polytope (FF) is
=(F)=(ze) Σ 24 F [n], Σx x F(n))
iES
VE[m
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) - O. In this case, f- $ --((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 FF submodular, f agrees with the support function of the base polytope B(F), and therefore (FF) is the Newton polytope Newt(f) of the Lovász extension f (see e.g. Aguuar & Ardila (2017) Theorem 12.3.). The Newton polytopes of functions that differ by linear map are a translation of each other linear functions. Hence, if we denote by Bn the
and modular functions correspond set of base polytopes in R" modulo translation, the maps B: Fn B,, ((F) and Newl: Vp + Br, I + N/w are well defined and we obtain the following diagramm:
F
B n
Newt
Vp
In this setting, we call a decomposition (G, H) E D(F) minimall if it is not dominated by any other decomposition, that is, if there is no other decomposition (G', HH) D(F) where B(G)) has at most as many vertices as BGG), B(H)) has at most as many vertices as ((H), and one of the two has strictly fewer vertices.
For a tuple of submodular functions (G, H) E SM x SM, let (Po. PH) be the tuple of the normal fans of the base polytopes B(G) and B(H). A decomposition (G', H') E (FF) is
called a (non-trivial) coarsening of (G, H) E D(F) if Por and PHr are coarsenings Pa and PH, respectively (and at least one of them is non-trivial coarsening).
Corollary D.12. (G E ((F) is a vertex if and only if there is no non-trivial coorsening of H).
Proof. Since g 4 (G) and h = (-H are the support functions of the base polytopes B(G) respectively B(H), the tuple of normal fans (Po, PH) agrees with the tuple (Pg. PP)) 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) and only if (g, h) is a vertex of Df( which is the case if and only if (G, is a vertex of D(F).
Corollary D.13. For a normalized set. function F E Faz a minimal decomposition of F verter of D(F).
Proof. If (G, H) is not a vertex, then there is a coarsening (G', H') E D(F) of (G.H)
implying that (G', H') dominates (G,
23

---

Published as a conference paper at ICLR 2025
The following example shows that the Lovász extensions of cut functions 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, F) be 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) E (N,)) c((u, v}), where Ö(S) = [u,v) E E'
S, E V S}. The function = t 1-100-111 (F) E Vp is given by f(x) = EiuooeE (((,,))) fu,((x), where (x) max Fn - Fos To Lnj. To see this, first note that f Vp. Thus, it suffices to check that F(S) ((1s) for all S [n], which follows due to the observation that
(1s) = {o
(u. E ((S) (u. & 6(5)
Hence, Example A.2 implies that the functions
Σ
ctu, v}) fu, and h Σ
c(fu fux
d(,)))>
a((u,))<c
form the unique minimal decomposition of f. Thus, = l(g) and = [(h), the submod- ular functions given by
G(S)
Σ (a))) a(fu,v})>0
v(u, and H(S)
Σ
c((u,)) v))
(u()) c((u,)))<0
are the unique minimal decompositions of F into submodular functions.
E PROOFS
E.1 PROOF OF LEMMA 3.1
Proof. Let f.g be CPWL functions which are compatible with P, and X, E R. Then for any P E Pn holds (Af + μg]lp= Afle + uglp, 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 E Vp. Since P is a complete polyhedral complex, for every pa-1, there are P,QE E pa such that o PP Q. Let ap,uq E IR" and bp, by R such that flp(s) = (ap,z) + bp and flo(x) (aq. .²) + bqq Consider the linear map o: Vp - Wp given by
wy(a) = (ep/m: ap) + (eq/n, = (ep)o, ap - -q)--
Note that if f locally convex at a, then (ep/o: ap - aQ) |ap aglla and if f is locally concave at 0, then (ep/o,ap- ap aq) -Iaap agll2. The proof proceeds analogously to the case where f has only convex brcakpoints and the coefficients of the affine maps are rational. In this case, the lemma follows from the structure thcorem of tropical geometry.
See See Maclagan & Sturmfels) 2015) Proposition 3.3.2 for a proof that wy E Wp and Maclagan Sturmlels (2015) Proposition 3.3.10 for a proof that & surjective. Here, we present an adjusted proof (to not necessarily convex functions and irrational coefficients. First, check that w E Wp. Let 7 E pm-2 and (PI...,, Ph....,Pm. Pm) = starp(7) pm ni and (oi...., STarp(7) n p be ordered Pm+1 Pt. Note that, since f is continuous, have that ap, - -ap span(eep.oo.. The linear map T;: a af satisfying T (e(,, ea,/r (given by rotation matrix)
a cyclic way, that is, P, n P.+. a; for E [m], where
24

---

Published as a conference paper at ICLR 2025
is automorphism, implying that
m wy(a) 60/7 Σ ==1
Σ
wy(a,) (epp,.))))
oepa-t
T
(en/o, Qp, -ap++.) -rr/oa
T,
(er./a (ap, ap.+1)
(0) 0
We procood by showing that the map & is surjective and its kernel is preciscly Aff(R") and therefore, it induces an isomorphism between Vp and Wp.
The kernel of & is (I" since Wy(o) (erjo: ap) + (eq/a, (epjo,ap ap aQ) 0 if and only if ap aq = 0 due to the fact that ap aq E span(ep/o). Due to the continuity
of f, this also implies that bp = bq and hence flq = flp and therefore the map f is affine linear.
To show surjectivity, let w E Wp. We aim to find an f E Vp such that w = o(f). Let p" .P..... .P....PP.. P& and for P E p", E p let bp// E such that a is contained in the hyperplane (x E R² (eP/o, + bp 0} and define the function fP Rn + R by (x/= (er/a: 2) + br/a. Since P is complete, the graph G (V, E) given by V P, E pn-1) is connected. Start by defining the function flp. = 0. For < i i k, let Imm be a path from 1 to i and for E [m - I], let at Pje n Pa and define the function
(1....,k) and E {(i,] [
m-1
fIe - w(az) fpa
First, we argue that fle, is well-defined, that is, the definition fle, docs not depend on the path from vertex 1 to i. Equivalently, it suffices to show that for any cycle (f.,...; km) in G with i im. holds that Σm w(or)frr, = O, where oj P. PP Since P is complete any cycle decomposes into cycles (d1,..., mm) corresponding to the star of a cone pn-22 that is, fo1.....,o,, 0m-1) for pn-1 10 T}. Since T, is an automorphism, it holds that Em. w(rr). C../T 0 if and only if ETT w(oz) EP.
So, let E R" be arbitrary and x' E aff(r) and x" E aff(r) such that x = x' + x". Since is in Wp, it holds that Σ u(o) 6g/T and hence follows that
oEPn-1
m-
w(or): (er,,/ars + x²) + br.,/a
w(oz) (e (ep,,/ons")
w(oz) -Pr,/or
=0
By definition, f is a CPWL function and compatible with and hence Vp. To see that ΦfJ), let P. E pm such that a = PnQ E pm-11 Then it holds that ap aq =
w(o) ep/a and hence
wy(o) = (eryo. ap) + (eq/a: ag) = (erjo: ap - aQ) = (er/a, wlo) erja) w(a). finishing the proof.
25

---

Published as a conference paper at ICLR 2025
E.3 COROLLARY
Corollary E.1. Vp finite-dimensional..
Proof. By Lemma 3.2 we have that V/ = Vp Aff(R*) = Wp. Thus, the dimension of Vip is bounded from above by dim(Wp) + dim((ff( S +n
E.4 PROOF OF PROPOSITION 3.3
Proof. The function f is convex if and only is locally convex around every Z RR. Tf is in the relative interior of some P E p then this is clearly satisfied since the function locally affine linear. Now, assume that f is not locally convex around a I E T for some E p In other words, there are y E I such that ((==+(1-A))))
( and such that the line between x and y intersects т. Let be the Lipschitz constant of f and 8 f(Az + (1 11--)y A)y) Xf(2) (1 X)f(y) 0. Let = > 0. Then there are v, w.we E R" with [|l]] | < & such that the line between + v and y + w does not intersect any face pn-2 But then,
f(A(2 + +)+ (1 A) w)) 2 f(2 A)y) E(lIAU] + +1(1 A)w())
> f A)y) 2LE
= (1(+)(())(1-A)))
-TLE
2 o) A) + +w) - 2L 2L
+
-f((= (1- + w)
and there must be a the relative interior of some a E p such that f is not locally convex around x'. Hence, f is convex if and only f is locally convex around every E p=-1, that is, f is locally convex around every x in the relative interior a. For any such x, there is À > such that + X Cp/o E P and x + À CQ/a Q, by construction of ep/a and eqja. Recall from the proof of Lemma 3.2 that wy(a) = (ep/o, up) + (eq/a: "Q), where flr(x)= = (ar, æ) + +bp and fl)(z)= (aq, x) tbq. Since P. E p" and ||ep/oll = |eq/oll 1, we have that x is the midpoint of
epjo and x + cq/a- Therefore, f convex and only if f(z) I f(x + X. epya) + f(( + X. eQjo). Equivalently.
0 f(x + A
ep/a) ).e
+ f(x + X eq/a)) 2f(x) = X((ep/a; ap) + (eaya, (q)) = À wy(o).
If P = Py; then we have strict local convexity at every pn-1, which means a strict inequality in the inequality above.
E.5 LEMMA
Lemma E.2. Dø forms polyhedral cone in Vp.
Proof. Lemma 3.2 and Proposition 3.3 imply that the set of convex functions in Vp satisfies D W = noepn- (w
Wp w(a) 2 0}. This is a finite intersection of linear inequalities, so Wi is a polyhedral cone. Moreover, "3"" is linear isomorphism, which implies that Di is a polyhedral cone.
E.6 LEMMA
Lemma E.3. Let P be regular polyhedral complex. Then every CPWL function compatible with can be wrillen as a difference of two conver CPWL functions that are also compatible with P. In particular, Vp = span(V
Proof. Let f E Vp be an arbirtary function. Since P is regular, by definition there exists a convex function g Vp such that P Py- Proposition 3.3 implies that wy(a) 0 for all
26

---

Published as a conference paper at ICLR 2025
pp-1, For sufficiently large O, it follows that wyt 0 and thus f (f ^)g) Xg a representation of f as a difference two compatible, convex functions, as clesied. 0
E.7 PROOF THEOREM 3.5
Proof. For the set of docompositions holds
Dr(f) ((g. h)
h - (V x D HH
For the projection we have
T(P((f) = x f)llleg--llleea - / // v
E.8
PROOF OF THEOREM 3.8
The statement follows from a more general statement about polyhedra. Recall that any polyhedron P can written the Minkowski sum
P= {a + gEQ,EE
where Q is bounded polytope, and C unique polyhedral cone, the recession cone of P. Proposition E.4. A point x E P is contained in a bounded face of P if and only if x-c4 Ve C {0}.
Proof. Any face of the polyhedron is of the form
p" p (x P (x, u) 2 (v. Vy P).
and for Minkowski sums holds p" = Q" + C". Let P a point contained in bounded
face pe of P. Since pa is bounded, we have that pa = Q" + C with C = {0} being the unique bounded face of C. Thuss (c, u) < (0, u) for all c C (0). This implies that (x- u), u) > (I, u) and therefore, by definition of pa we have that c & P.
Conversely, suppose that x P is not contained in a bounded face. We want to show that there exists some direction E C {0) such that x E P. Since æ is not contained in bounded face, it is contained the relative interior of an unbounded face F (where possibly F = P). Since the face is unbounded, it contains ray + Re for some direction C. On the other hand, since x E in)(F), we have that x - EC E F' for E > 0 small enough. As C is cone, have that Ec C, which finishes the proof.
Proof of Theorem 3.8 Since π induces a bijection between (f) and its image, this is also a bijection between bounded faces. By Theorem 3.5 x (Dp(J) is a polyhedron with recession cone VI Proposition E.4 implies that g contained in a bounded face if and only if there exists convex function & v such that g- E (DDp()). Therefore, - (g) = (g,h), h = g - coutained a bounded face Df( and only if there is no V such that (g 0.9 f Φ) (g é. h d) & Dp(f). Since (g (g-)) (h (1h-))= this is equivalent to g - o or o being nonconvex, i.c., (g. h) is roduced.
E.9 PROOF OF LEMMA 3 10
Proof. First note that B(g)
U a are exactly the points where g is not affine
(E)uppr(s)
lincar. Hence, the closures of the connected components of the complement of B(g) are the maximal polyhedra of the unique coarsest polyhodral complex Py compatible with g.
Let suppp(g') S sgppp(g). Equivalently, for the complement holds (IR" \ B(g)) C (IR" B(g')), and the same holds for the closures of the (open) connected components, i.c., the maximal faces in Pr and Py. Tn other words, this is equivalent to that for every face P E P
27

---

Published as a conference paper at ICLR 2025
there exists some P' E Py such that P P'. Thus, suppp(g') = suppp(g) if and only if Pg is a coarsening of pg.
The coarsening is non-trivial if and only if there is a P' E Po such that there is no P E P with P' S P. This is the case if and only if there is a E Pa-l that intersects the interior of P', which occurs if and only if E suppp(g) suppp(g)).
E.10 PROOF OF THEOREM
We first prove the following proposition that relates coarsenings of the docompositions to inclusion relations of the minimal faces that contain the decompositions.
Proposition E.5. For hg E Dp(f), let F be the minimal face of (D((f) containing (g. h). Then (g',h') h²) is coorsening of hg if and only if there is face G of Dp(f) with G S F such that (g', 1)) E GG The coarsening is non-trivial if and only if F G.G.
Proof. For face F. let Gr for pn-1 Wg(a) 0 for all (w)))wh) F} and Hr (o E pP--1 wa (x)
for all (Wyy wa) E 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 GC F if and only if GF C GG and HF S Hg. In other words, if (g', h') is contained in a face G F, then one can move from (g,h) h) to (g',h') without losing tight inequalities. Hence, Lemma 3.10 implies that (g', h²) is coarsening of (g, h). If G C F, then either GF C Ga or Hr C Ho. Thus, another incquality becomes tight when moving from (g. (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, J = g' hi' implies that (g', h²) E Dr(J)- Now, assume that there is no face G C F such that (g', (g, h) and (g', A') is not contained in F. Thus, a tight inequality gets lost when moving from (g, h) towards (g', ,!)). Hence, without loss generality, there is a a E suppp(g') suppp(g), which according to Lemma 3.10 is contradiction to (g R²) being coarsening of (g, D
G. Then the line between
Proof of Theorem 3. 11
and are equivalent by Proposition E.5
3 Irivially implies 2
Hence, remains show with and h such that (g. h) is not vertex of De(f). Then there is vertex (g'hh) of Do(f)
Assume that there is a polyhedral complex Q compatible
contained in the face containing (g, h). By Proposition E.5
follows that (g', h!) is a non-
trivial coarsening of h).
E.11 PROOF OF THROREM 1.
Proof. If (g, h) is not not a vertex, the by Theorem 3.11 there is coarsening (g', h!) of (g, h). Thus, (g, h) is dominated by (g, h) and therefore not minimal.
E.12 PROOF OF PROPOSITION 3.
Proof. As Dp(f) is nonempty, there must exist 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. LEMMA E.6
Lemma E.G. Let C C E be a convex, pointed polyhedral cone. If C is simplicial then Cn t) is (potentially shifted) cone, i.e. a polyhedron with single verter, for any translation t. If C is not simplicial, then C C (Ct) is a (shifted) cone if t C.
Proof. If C is simplicial full-dimensional cone, then it is the image of the nonnegative orthant under an affine isomorphism. Thus, it suffices to show that Cn (C + t) is a shifted cone for C = Bg Let i E Rdd such that i = max 0). Then
on (C t) (- x; 2 0 and x4 2 4 for xe 2 -
28

---

Published as a conference paper at ICLR 2025
On the other hand, if C' is an arbitrary polyhedral cone and t C, then Cn 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, & & C' does not imply that C' n (C' + is not a shfited cone. Indeed, let C' = cone (())
and t= ( Then (C(C+ = (1)
is a shifted cone.
On the other hand, the choice 1 = (g) yields the unbounded polyhedron Cn +
conv (()) (?)) C, which has two vertices and one line segment as bounded faces.
E. 14 PROOF OF PROPOSITION
Proof. Let Q be any regular complete complex that is compatible with f. Then, 9 and h are as well compatible with Q, since suppp(g), (h) S suppp(f) implies that (UpPo()),uppo/l
S (f). Let 1²', E Do(f). Then it holds that (f) S suppo (g') since W1 - wy- = Wh 2 O. Hence, suppo(g) C suppo(s') and Lemma 3.10 implies that g is coarsening of g' and analogously it follows that is a coarsening of h Therefore,
(g, h) is a coarsening of every decomposition and thus by Theorem 3.11 the only vertex of De(f). Clearly, g and cannot have more pieces than f.
E.15 PROOF OF THEOREM 3.
Before proving this statement, we give a description of the dual cone (V Recall that VI = Noep- {w Wp w(o) 2 0}, i.e., the intersection of the nonnegative orthant {w(o) 0} with the linear space Wp. By duality of intersections and sums, it follows that (V is isomorphic to the Minkowksi sum of the nonnegative orthant with W In particular, any with positive weights w(o) > 0 lies in the interior. Theorem 3.18 follows from a general fact about face of polyhedra.
Lemma E.8. Let C be conver, pointed polyhedral cone and P polyhedron with recession cone C. Then u E int(C") is a direction in the interior of the dual cone of C if and only if the face pa of P which minimized by u is a bounded face.
Proof. Tet p= C + Q where Q is a bounded polyhedron. Then for any direction + Q" As is a pointed cone, we have that C bounded if and only int(CV). Since Q" is bounded for any direction, it follows that pa is bounded if and only u E int((").
holds pa = =0"+Q
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 pa is bounded, the face p" coincides with the set of optimal solutions of the linear program. Now, P = V D is a polyhodron with recession cone Dz. Applying Lomma E.8 yields that for any u E (in)))))))) every minimizer in ((Dp(f)) lies in bounded face, which, by Theorem 3.8 are precisely the reduced decompositions. Moreover, if 7 (DDp(f) contains a unique vertex then by Proposition 3.14 this coincides with the unique minimal decompoition.
E.16 PROOF OF THEOREM
Proof. In the convex case, this is literally proven by Hertrich et al. (2021 While Hertrich
et al. (2021) have 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) = max4ela of bb; The idea is to split the k affine components of
29

---

Published as a conference paper at ICLR 2025
into groups of size at most 8, apply Theorem 6.1 compute the maximum within each group, and then simply compute the maximum of the group maxima in a traighttforwaat way.
Let us first focus on computing the maximum at most affine components within each of the groups. By Theorem 6.1
achieve this with neural network of depth
[1 + +1] +1 and overall size O(s*+1.. We put all these r neural networks in parallel to each other and add, the end, the simple neural network computing the maximum of
these maxima according to Arora et al. (2018), which has depth [logg r] + 1 and overall
size (rr). Altogether, the resulting neural network will have the desired depth and size. C
E.18 PROOF COROLLARY 6.4
Proof. By Lemma E.3. f can be decomposed into a difference of two convex functions which are compatible with Consoquently, cach of them has at most q affinc components. Ap-
plying Theorem 6.3 to both functions separately and simply putting the two corresponding neural nelworks in parallel, subtracting the outputs, yields neural network representing f with the desired size bounds.
30


Reviews:
[{"review_id": "SMw3DkYZ2H", "reviewer": "Reviewer_HSgx", "summary": "This paper deals with the following problem: given a continuous piecewise linear (CPWL) function, decompose it as the difference of two convex CPWL functions. This line of research is motivated by the DC paradigm for nonconvex optimization.  In this work the authors consider decompositions that are compatible with a given polyhedral complex and are “minimal” (for the definition of minimality, see Definition 3.12). The authors show that the set of all decompositions forms a polyhedron (Theorem 3.5) and that minimal decompositions are at a vertex of this polyhedron(Theorem 3.13). Thus, a minimal decomposition can be found by enumerating the vertices. They also identify a few special cases where there is a unique vertex, so there is no need for enumeration. In terms of applications, in Section 5 they apply their results to submodular functions. In Section 6, they revisit the problem of representing a CPWL function by a ReLU neural network. Their main result there is Corollary 6.4, providing “a smooth tradeoff between size and depth”, for the special class of CPWL functions that are compatible with a regular polyhedral complex.", "questions": "Page 1, Introduction: You write, “CWPL functions play a crucial role in ML.” If I understand correctly, this is the case because they are used as a test case for the universality theorems for NNs, where they can be concretely instantiated in terms of width, depth, etc. Is that correct, or are there more important applications? You do mention submodularity etc in the introduction, maybe elaborate on that somewhat?\n\npage 1: Are there problems where fixing the supporting polyhedral partition in DC decompositions is a natural constraint? \n\nPage 2, Section 1.1: Please point to a specific Theorem as your “main technical result.” I guess that is Theorem 3.13?\n\nPage 2, line 73: “cannot be easily simplified.” Explain why this is important. Also, when you say a “minimal” solution, what are you referring to?\nPage 2, line 75: “simply enumerating” seems to indicate there are not that many of them. Please elaborate on this.\n\npage 3. Please give a bivariate example of a CPWL function with two different compatible polyhedral complexes with a different number of maximal facets.\n\nPage 4: Please provide a simple example (with a figure) of a polyhedral complex illustrating (some of) the definitions in Section 2. In particular, at least one example of a polyhedral complex, the refinement, and the balancing condition should appear in the main text. Perhaps use the median example in Section 2. For example, to understand the balancing condition, I had to draw a 3D cube, a trivial case of a 3-dimensional polyhedral complex. According to the definition, for any 2-dimensional face \\sigma, we have a weight w(\\sigma). Then, for any 1-dimensional face \\tau and any 2-dimensional face containing \\tau, we have the vector e_{\\sigma/\\tau}. The balancing condition says that if we sum up all these vectors scaled by their weight, we should get the zero vector.\n\nPage 4: Why is the balancing condition required only for n-2 dimensional faces? Why do we not care about smaller faces?\n\nPage 4: It’s probably easy, but I couldn’t see it. Can you provide an example of a convex CPWL function with two different compatible partitions?\n\nPage 4, line 188: Give an example of the number of pieces. E.g., the number of pieces for the median function is 6, correct?\n\nPage 4, line 188: Same for affine components. For the median, it is 3, correct? Also, in terms of notation, shouldn’t that better be \\(\\text{aff}(\\mathcal{P})\\) or something like that?\n\nPage 4: What is the relationship between k, q and n? Knowing this is also important for the representation results in Section 6.\n\nPage 5, line 241: Recall that w are weights for codimension 1 faces.\n\nPage 5, line 247: You write that Figure 1 illustrates the different parameterizations of the median function according to Lemma 3.2. I was trying to understand what that means. I guess the numbers on the figure are the weights on each edge, and the only “n-2” face for which we need to check the balancedness conditions is the origin, and this is indeed balanced. But how does that illustrate the isomorphism from Lemma 3.2?\n\nPage 5, line 250: Have you defined “regular complex”?\n\nPage 5, definition 3.4: Could it be that although f is compatible with P, it has a DC decomposition where f and g are not compatible with P? That is, are the decompositions studied here a restricted class?\n\nPage 6, definition 3.12: I forgot what was meant by “pieces” here? It is the minimum number of facets in a compatible decomposition. Apparently, this is already used in the literature, but maybe a better term could be used?\n\nPage 6, line 302: Typo.\n\npage 6, Theorem 3.13. I may have missed this but have you argued that the decomp polyhedron always has an extreme point? \n\nPage 7, proposition 4.1: The word “function” appears twice.\n\nPage 7, line 371: What is proposition B.3?\n\nPage 9, line 468: Typo “certing.”\n\nPage 9, line 450: “this simple fact…” it is not clear what that means, please explain. Are Theorems 6.1 and 6.2 constructive? Would we be required to know the parameters q and k and their specific representations as CWPL functions?\n\nPage 9, Theorem 6.3: Writing q = k in the theorem statement makes it look like an assumption (which is not the case).\n\nPage 10, Corollary 6.4. This result is only applicable to CPWL functions that are compatible with a regular polyhedral complex. Maybe I missed it, but can you discuss whether this assumption is natural and/or easy to satisfy.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem of decomposing CPWL functions as the difference of convex CPWL functions is interesting. No finite procedure is currently known for finding a minimal decomposition. This work provides a new perspective, based on polyhedral geometry, that guarantees finite convergence, but in the special case where the factors have a fixed supporting polyhedral decomposition", "weaknesses": "The assumption that the DC decomposition should be with respect to a fixed polyhedral complex seems restrictive and perhaps unmotivated \n\nI feel that the paper is hard to read for non-experts in the area (e.g. many technical definitions with not many accompanying figures to help the reader-there are few, but mostly in the Appendix).\n\nThe main result in Section 6 (Corollary 6.4) for representing CPWL functions as NNs, is only applicable to CPWL functions that are compatible with a regular polyhedral complex. It is not clear whether this assumption is (1) natural and (2) easy to satisfy.  The existing decomposition results are applicable to any CPWL function.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AKiaesh6LU", "reviewer": "Reviewer_BUg5", "summary": "This paper studies the fundamental problem of decomposing a continuous piecewise linear (CPWL) function into two convex CPWL functions. This is a rather challenging problem with a long history and important practical applications. The authors adopt a novel perspective to tackle this problem: investigating the space of admissible convex CPWL functions while fixing the underlying pieces. The main contribution is a series of structural results concerning the geometric properties of the so-called (and new) decomposition polyhedra, which are connected to the space of admissible convex CPWL functions. With these structural results, the authors demonstrate some implications for submodular functions and for constructing neural networks according to a given convex CPWL function. Moreover, they refute a recent conjecture on algorithms for computing CPWL functions in the literature.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The DC representation of a general CPWL function is an old but fundamental problem with many applications in various engineering fields. This paper proposes an interesting perspective on how to understand and compute the DC components from a given CPWL function. Although I did not have time to check all the proofs in detail, the paper is generally well written, and the results are interesting. In particular, I appreciate the idea of fixing the underlying pieces and the clean characterization of the DC components.", "weaknesses": "While the pieces are assumed to be fixed in advance (which is, of course, a limitation, as also explicitly noted by the authors), I believe this work has great potential to motivate further investigation into both the theoretical and algorithmic aspects of the decomposition problem. \n\nMy comments are as follows:\n* L200, in the definition of $\\mathcal{P}_f^n$, I don't think the set {$x:g_i(x)=\\max_j g_j(x)$} must be full dimensional. This may depend on the representation of $f$ given in L199. Also, $k=q$ may not be true, as claimed in L202.\n* As for regular polyhedra complex, I understand the usage of the existence of convex CPWL in the proof of theorems. I'm curious about the irregular case and it will be very helpful to provide some details or examples to illustrate the existence of irregular polyhedra complex.\n* Some notation are used before defined in the whole paper. For example, in Proposition 3.3, it seems the function $w_f$ is not defined until the proof of Proposition 3.2.\n* L184, in the definition of CPWL functions, I think you need to require $f$ to be continuous.\n* L1283, what is $\\phi$ defined here?\n* In the proof of Proposition 3.3, I suggest providing more details to justify the equivalence claimed in line 1360. Intuitively, this is correct, but in convex geometry, counterintuitive phenomena can occur, so a rigorous and formal argument would be desirable.\n* L752, the function $h$ may not be convex as claimed.\n* L180, add a period.\n* L146, \"wit\" should be \"with\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PamHCN7Tkj", "reviewer": "Reviewer_UiL3", "summary": "The paper studies the problem of decomposing a given continuous piecewise linear function into the difference of two convex piecewise linear functions. Especially, the authors investigated the problem of finding such a decomposition with the least linear pieces. To tackle this,  a few new theoretical results were proposed and proved. After fixing the polyhedral complex, they study the geometrical properties of such decompositions. Specifically, they show that a minimal solution must be a vertex and hence can be obtained by a simple enumeration. The results can be applied to relu network with 1 hidden layer, statistics functions, submodular functions, and the construction of neural networks.", "questions": "1. Definition 3.12. The definition for the minimal decomposition seems same as the Pareto optimality in multi-objective optimization. \n2. Hyperplane functions introduced in Def 3.16 satisfy the assumptions. These are functions generated by a ReLU network with 1 hidden layer. Just wondering, does the result also hold for general ReLU networks with more layers? \n3. In theorem 3.18, what is the exact meaning of **minimizer**? It is also better to include an explicit linear programming problem described in Theorem 3.18.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents an innovative approach by linking decomposition problems with polyhedral geometry, leading to the concept of decomposition polyhedra. This is a very novel idea and may inspire many interesting future works. \n\n2. The theoretical analysis of the paper is very solid, providing us with a deep understanding of CPWL decomposition problem. \n\n3. The paper is well-written and well-organized, clearly stating the main contributions and their applications.\n\n4. The applications to ReLU activation, submodular optimization, neural network design, are very interesting.", "weaknesses": "The main weakness of the paper is that as stated in Limitations section of the paper. The paper mainly focuses on the development of theories, but does not provide practical implementations and applications of their results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pw4HDwTLH8", "reviewer": "Reviewer_So2m", "summary": "The paper studies decomposition of continuous piecewise linear (CWPL) functions into difference of two convex CWPL functions with as few linear pieces as possible.\nThe contributions of the paper include:\ni. A proof that the minimal solution must be vertices of a certain polyhedron which is a set of decompositions. This polyhedron arises as an intersection of two translated cones.\nii. A construction for a unique minimal decomposition for certain CWPL functions in dimension 2 by Tran & Wang (2024) does not extend to higher dimensions.\niii. Applications of the decomposition to submodular function optimization and neural network construction.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Paper is well-written. The problem studied is challenging.", "weaknesses": "The obvious limitation is that the underlying polyhedral complex is fixed.\nThere are no bounds shown for the number of pieces in the minimal decomposition. Would it be related to the notion of monomial complexity ? A discussion would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)