Deep Online Convex Optimization with Gated Games

Abstract

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.

13 pages. This paper renders arXiv:1509.01851 obsolete. It contains the same basic results, with major changes to exposition and minor changes to terminology

References in corpus (8)

• Deep Learning in Neural Networks: An Overview
• Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification
• Recurrent Models of Visual Attention
• Stochastic Variance Reduction for Nonconvex Optimization
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Gradient Descent Converges to Minimizers
• Norm-Based Capacity Control in Neural Networks
• Fast Incremental Method for Nonconvex Optimization

Cited by in corpus (6)

• Recovery Guarantees for One-hidden-layer Neural Networks
• The Shattered Gradients Problem: If resnets are the answer, then what is the question?
• Online Learning with Gated Linear Networks
• Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks
• Rapid training of deep neural networks without skip connections or normalization layers using Deep Kernel Shaping
• Dynamic Game Theoretic Neural Optimizer