  Methods from convex optimization are widely used as building blocks for deep
learning algorithms. However, the reasons for their empirical success are
unclear, since modern convolutional networks (convnets), incorporating
rectifier units and max-pooling, are neither smooth nor convex. Standard
guarantees therefore do not apply. This paper provides the first convergence
rates for gradient descent on rectifier convnets. The proof utilizes the
particular structure of rectifier networks which consists in binary
active/inactive gates applied on top of an underlying linear network. The
approach generalizes to max-pooling, dropout and maxout. In other words, to
precisely the neural networks that perform best empirically. The key step is to
introduce gated games, an extension of convex games with similar convergence
properties that capture the gating function of rectifiers. The main result is
that rectifier convnets converge to a critical point at a rate controlled by
the gated-regret of the units in the network. Corollaries of the main result
include: (i) a game-theoretic description of the representations learned by a
neural network; (ii) a logarithmic-regret algorithm for training neural nets;
and (iii) a formal setting for analyzing conditional computation in neural nets
that can be applied to recently developed models of attention.
