Title: On the Compressive Power of Deep Rectifier Networks for High Resolution Representation of Class Boundaries,
Abstract: This paper provides a theoretical justification of the superior
classification performance of deep rectifier networks over shallow rectifier
networks from the geometrical perspective of piecewise linear (PWL) classifier
boundaries. We show that, for a given threshold on the approximation error, the
required number of boundary facets to approximate a general smooth boundary
grows exponentially with the dimension of the data, and thus the number of
boundary facets, referred to as boundary resolution, of a PWL classifier is an
important quality measure that can be used to estimate a lower bound on the
classification errors. However, learning naively an exponentially large number
of boundary facets requires the determination of an exponentially large number
of parameters and also requires an exponentially large number of training
patterns. To overcome this issue of "curse of dimensionality", compressive
representations of high resolution classifier boundaries are required. To show
the superior compressive power of deep rectifier networks over shallow
rectifier networks, we prove that the maximum boundary resolution of a single
hidden layer rectifier network classifier grows exponentially with the number
of units when this number is smaller than the dimension of the patterns. When
the number of units is larger than the dimension of the patterns, the growth
rate is reduced to a polynomial order. Consequently, the capacity of generating
a high resolution boundary will increase if the same large number of units are
arranged in multiple layers instead of a single hidden layer. Taking high
dimensional spherical boundaries as examples, we show how deep rectifier
networks can utilize geometric symmetries to approximate a boundary with the
same accuracy but with a significantly fewer number of parameters than single
hidden layer nets.