Deep ReLU Networks Have Surprisingly Simple Polytopes
Feng-Lei Fan Wei Huang Xiangru Zhong Lecheng Ruan Tieyong Zeng Huan Xiong Fei Wang
A ReLU network is a piecewise linear function over polytopes. Figuring out
the properties of such polytopes is of fundamental importance for the research
and development of neural networks. So far, either theoretical or empirical
studies on polytopes only stay at the level of counting their number, which is
far from a complete characterization of polytopes. To upgrade the
characterization to a new level, here we propose to study the shapes of
polytopes via the number of simplices obtained by triangulating the polytope.
Then, by computing and analyzing the histogram of simplices across polytopes,
we find that a ReLU network has relatively simple polytopes under both
initialization and gradient descent, although these polytopes theoretically can
be rather diverse and complicated. This finding can be appreciated as a novel
implicit bias. Next, we use nontrivial combinatorial derivation to
theoretically explain why adding depth does not create a more complicated
polytope by bounding the average number of faces of polytopes with a function
of the dimensionality. Our results concretely reveal what kind of simple
functions a network learns and its space partition property. Also, by
characterizing the shape of polytopes, the number of simplices be a leverage
for other problems, \textit{e.g.}, serving as a generic functional complexity
measure to explain the power of popular shortcut networks such as ResNet and
analyzing the impact of different regularization strategies on a network's
space partition.