Exact Count of Boundary Pieces of ReLU Classifiers: Towards the Proper
  Complexity Measure for Classification
Paweł Piwek Adam Klukowski Tianyang Hu
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
$l_2$ 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.