Research map / Learning theory and algorithms / Sample complexity

Decomposition Polyhedra of Piecewise Linear Functions

ICLR 2025 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies minimal decompositions of CPWL functions into differences of two convex CPWL functions by fixing a compatible polyhedral complex, showing the solution set is a decomposition polyhedron whose vertices contain minimal solutions.

Problem

Decomposing a continuous piecewise linear function f into a difference g-h of two convex CPWL functions with as few linear pieces as possible; no finite procedure guaranteeing minimality was known.

Approach

Fix a compatible regular polyhedral complex; the set of convex decompositions then forms a polyhedron (intersection of two translated cones), whose bounded faces correspond to reduced decompositions and whose vertices contain all minimal decompositions, enabling enumeration/LP-based search. Also transfers to virtual polytopes and submodular set functions and improves neural network constructions.

Key results

• Proves the decomposition set for a fixed compatible complex is a polyhedron (intersection of two shifted cones); bounded faces are exactly the reduced decompositions.
• Shows minimal decompositions must be vertices of the decomposition polyhedron, and a unique vertex implies a unique minimal decomposition (e.g., median, hyperplane functions).
• Shows hyperplane-extension and local-maxima constructions need not yield vertices for the k-th order statistic, refuting a conjecture about the 2D balancing construction generalizing to higher dimensions.

Measured effects reported in the paper

Surprising findings

• The 2D balancing-based minimal decomposition does not generalize to higher dimensions in the suggested way.
• The global optimal decomposition is not necessarily contained in the decomposition polyhedra of the hyperplane-extension or local-maxima complexes.

Limitations

• Restricts solutions to those compatible with a fixed polyhedral complex, which may exclude the global optimum.
• No implementation of heuristic or exact decomposition methods is provided.
• Finding minimal decompositions remains very challenging even under the fixed-complex assumption.

Experimental setup

Baselines: hyperplane extension local maxima decomposition balancing in dimension 2

Builds on: tropical geometry balancing condition virtual polytopes local maxima decomposition hyperplane extension

Closest papers by meaning

• Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions (NeurIPS 2022 · similarity 0.86)
• The Multi-Block DC Function Class: Theory, Algorithms, and Applications (NeurIPS 2026 · similarity 0.84)
• Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses (NeurIPS 2026 · similarity 0.83)
• How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets (NeurIPS 2025 · similarity 0.83)
• SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions (NeurIPS 2026 · similarity 0.82)
• Depth-Bounds for Neural Networks via the Braid Arrangement (NeurIPS 2025 · similarity 0.82)