Tuesday, April 19, 2016

Deep Online Convex Optimization with Gated Games

David sent me the following a while back:

Dear Igor,

I’ve enjoyed following your blog for a long time, and think the following preprint may be of interest: “Deep Online Convex Optimization with Gated Games,” http://arxiv.org/abs/1604.01952. It analyzes the convergence of gradient-based methods on rectifier neural networks, which are neither smooth nor convex, using ideas from game-theory.

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.

Thanks David !

Image Credit: NASA/JPL-Caltech/Space Science Institute  
W00097359.jpg was taken on April 14, 2016 and received on Earth April 14, 2016. The camera was pointing toward SATURN, and the image was taken using the MT2 and CL2 filters. This image has not been validated or calibrated.
Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: