# Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper Complexity Measure for Classification

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 48 references that are in the map.
- First posted on arXiv 15 Jun 2023.

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

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Adversarially Robust Distillation](https://mlsanity.com/paper/1905.09747/) (2019)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Smooth Adversarial Training](https://mlsanity.com/paper/2006.14536/) (2020)
- [Controlling Neural Level Sets](https://mlsanity.com/paper/1905.11911/) (2019)
- [Adversarially robust transfer learning](https://mlsanity.com/paper/1905.08232/) (2019)
- [A Topological Regularizer for Classifiers via Persistent Homology](https://mlsanity.com/paper/1806.10714/) (2018)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [A Unified Gradient Regularization Family for Adversarial Examples](https://mlsanity.com/paper/1511.06385/) (2015)
- [Jacobian Adversarially Regularized Networks for Robustness](https://mlsanity.com/paper/1912.10185/) (2019)
- [Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network](https://mlsanity.com/paper/2007.02486/) (2020)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Calibrated Surrogate Losses for Adversarially Robust Classification](https://mlsanity.com/paper/2005.13748/) (2020)
- [A Tropical Approach to Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/1805.08749/) (2018)
- [Boundary thickness and robustness in learning models](https://mlsanity.com/paper/2007.05086/) (2020)
- [On the Decision Boundaries of Neural Networks: A Tropical Geometry Perspective](https://mlsanity.com/paper/2002.08838/) (2020)
- [Understanding Square Loss in Training Overparametrized Neural Network Classifiers](https://mlsanity.com/paper/2112.03657/) (2021)
- [Sharp Rate of Convergence for Deep Neural Network Classifiers under the Teacher-Student Setting](https://mlsanity.com/paper/2001.06892/) (2020)
- [MixACM: Mixup-Based Robustness Transfer via Distillation of Activated Channel Maps](https://mlsanity.com/paper/2111.05073/) (2021)
- [Understanding Deep Learning via Decision Boundary](https://mlsanity.com/paper/2206.01515/) (2022)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [Bounding The Number of Linear Regions in Local Area for Neural Networks with ReLU Activations](https://mlsanity.com/paper/2007.06803/) (2020)

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

- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Complexity Matters: Rethinking the Latent Space for Generative Modeling](https://mlsanity.com/paper/2307.08283/) (2023)
- [1-Lipschitz Neural Distance Fields](https://mlsanity.com/paper/2407.09505/) (2024)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [A Computational Tropical Geometry Framework for Neural Networks](https://mlsanity.com/paper/2405.20174/) (2024)
- [Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networks](https://mlsanity.com/paper/2605.04946/) (2026)
- [AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks](https://mlsanity.com/paper/2605.06218/) (2026)
- [Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks](https://mlsanity.com/paper/2605.06300/) (2026)
- [Implicit Hypersurface Approximation Capacity in Deep ReLU Networks](https://mlsanity.com/paper/2407.03851/) (2024)
- [ReLU Networks as Random Functions: Their Distribution in Probability Space](https://mlsanity.com/paper/2503.22082/) (2025)
- [Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity](https://mlsanity.com/paper/2606.21687/) (2026)

## Abstract (arXiv)

Classic learning theory suggests that proper regularization is the key to good generalization and robustness. In classification, current training schemes only target the complexity of the classifier itself, which can be misleading and ineffective. Instead, we advocate directly measuring the complexity of the decision boundary. Existing literature is limited in this area with few well-established definitions of boundary complexity. As a proof of concept, we start by analyzing ReLU neural networks, whose boundary complexity can be conveniently characterized by the number of affine pieces. With the help of tropical geometry, we develop a novel method that can explicitly count the exact number of boundary pieces, and as a by-product, the exact number of total affine pieces. Numerical experiments are conducted and distinctive properties of our boundary complexity are uncovered. First, the boundary piece count appears largely independent of other measures, e.g., total piece count, and l2 norm of weights, during the training process. Second, the boundary piece count is negatively correlated with robustness, where popular robust training techniques, e.g., adversarial training or random noise injection, are found to reduce the number of boundary pieces.