# Decomposition Polyhedra of Piecewise Linear Functions

arXiv: https://arxiv.org/abs/2410.04907 · HTML: https://mlsanity.com/paper/2410.04907/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 53 references that are in the map.
- First posted on arXiv 7 Oct 2024.

## Builds on (most cited first, 22 of 22)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size](https://mlsanity.com/paper/2005.14105/) (2020)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Topological Expressivity of ReLU Neural Networks](https://mlsanity.com/paper/2310.11130/) (2023)
- [Representing Piecewise Linear Functions by Functions with Small Arity](https://mlsanity.com/paper/2305.16933/) (2023)
- [Novel convex decomposition of piecewise affine functions](https://mlsanity.com/paper/2108.03950/) (2021)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [Complexity of Injectivity and Verification of ReLU Neural Networks](https://mlsanity.com/paper/2405.19805/) (2024)
- [Representing Piecewise-Linear Functions by Functions with Minimal Arity](https://mlsanity.com/paper/2406.02421/) (2024)

## Built on by (most cited first, 9 of 9)

- [Algebra Unveils Deep Learning -- An Invitation to Neuroalgebraic Geometry](https://mlsanity.com/paper/2501.18915/) (2025)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2](https://mlsanity.com/paper/2503.13001/) (2025)
- [Discrete and Continuous Difference of Submodular Minimization](https://mlsanity.com/paper/2506.07952/) (2025)

## Abstract (arXiv)

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.