Characterizing the Discrete Geometry of ReLU Networks
Blake B. Gaines, Jinbo Bi
We describe the geometry of the polyhedral complexes defined by the linear regions of ReLU networks, both by theoretically bounding their connectivity and diameter and by empirically characterizing it using experiments on trained networks.
Abstract
It is well established that ReLU networks define continuous piecewise-linear functions, and that their linear regions are polyhedra in the input space. These regions form a complex that fully partitions the input space. The way these regions fit together is fundamental to the behavior of the network, as nonlinearities occur only at the boundaries where these regions connect. However, relatively little is known about the geometry of these complexes beyond bounds on the total number of regions, and calculating the complex exactly is intractable for most networks. In this work, we prove new theoretical results about these complexes that hold for all fully-connected ReLU networks, specifically about their connectivity graphs in which nodes correspond to regions and edges exist between each pair of regions connected by a face. We find that the average degree of this graph is upper bounded by twice the input dimension regardless of the width and depth of the network, and that the diameter of this graph has an upper bound that does not depend on input dimension, despite the number of regions increasing exponentially with input dimension. We corroborate our findings through experiments with networks trained on both synthetic and real-world data, which provide additional insight into the geometry of ReLU networks. Code to reproduce our results can be found at https://github.com/bl-ake/ICLR-2026.
Theoretical bounds on polyhedral complex connectivity and diameter reveal fundamental ReLU network geometry properties.
- Upper bound on average degree of connectivity graph at twice input dimension regardless of depth
- Diameter upper bound independent of input dimension despite exponential region growth
- Empirical evidence that training data tends to lie in polyhedra with higher connectivity
- Implications for bounding empirical error based on network architecture
- Polyhedral geometry
- Graph theory
- ReLU network analysis
Results only apply to ReLU activations without immediate implications for nonlinear activations
from the paperCannot yet describe convolutional layers and skip connections effects on geometry
from the paperFurther investigation needed on why training puts data in high-connectivity regions
from the paper
Extend results to other piecewise-linear activation functions
from the paperAnalyze effects of convolutional layers and skip connections
from the paperInvestigate relationship between training data placement and network behavior
from the paper
Author keywords
- Polyhedrons
- Geometry
- ReLU
- Activations
Related orals
On The Surprising Effectiveness of a Single Global Merging in Decentralized Learning
Shows decentralized learning with single global merging achieves convergence rates matching parallel SGD under data heterogeneity.
Non-Convex Federated Optimization under Cost-Aware Client Selection
Develops efficient federated optimization algorithm with cost-aware client selection achieving best communication and local complexity.
Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
Analyzes phase retrieval learning dynamics with anisotropic data, deriving explicit scaling laws and three-phase trajectories.
A Representer Theorem for Hawkes Processes via Penalized Least Squares Minimization
Representer theorem for Hawkes processes shows dual coefficients are analytically fixed to unity via penalized least squares.
Quantitative Bounds for Length Generalization in Transformers
Quantitative bounds show training length required for length generalization depends on periodicity, locality, alphabet size, and model norms.