  We investigate the complexity of deep neural networks (DNN) that represent
piecewise linear (PWL) functions. In particular, we study the number of linear
regions, i.e. pieces, that a PWL function represented by a DNN can attain, both
theoretically and empirically. We present (i) tighter upper and lower bounds
for the maximum number of linear regions on rectifier networks, which are exact
for inputs of dimension one; (ii) a first upper bound for multi-layer maxout
networks; and (iii) a first method to perform exact enumeration or counting of
the number of regions by modeling the DNN with a mixed-integer linear
formulation. These bounds come from leveraging the dimension of the space
defining each linear region. The results also indicate that a deep rectifier
network can only have more linear regions than every shallow counterpart with
same number of neurons if that number exceeds the dimension of the input.
