  The success of deep networks has been attributed in part to their
expressivity: per parameter, deep networks can approximate a richer class of
functions than shallow networks. In ReLU networks, the number of activation
patterns is one measure of expressivity; and the maximum number of patterns
grows exponentially with the depth. However, recent work has showed that the
practical expressivity of deep networks - the functions they can learn rather
than express - is often far from the theoretical maximum. In this paper, we
show that the average number of activation patterns for ReLU networks at
initialization is bounded by the total number of neurons raised to the input
dimension. We show empirically that this bound, which is independent of the
depth, is tight both at initialization and during training, even on
memorization tasks that should maximize the number of activation patterns. Our
work suggests that realizing the full expressivity of deep networks may not be
possible in practice, at least with current methods.
