2016/04/07 by David Balduzzi, Balduzzi, David · 1 voice · 7 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Algorithm #Artificial intelligence #Artificial neural network #Computer Science and Game Theory (cs.GT) #Computer science #Convergence (economics) #Convex optimization #Convolutional neural network #FOS: Computer and information sciences #Gradient descent #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine learning #Mathematical optimization #Mathematics #Neural and Evolutionary Computing (cs.NE) #Pooling #Rectifier (neural networks) #Recurrent neural network #Regret #Regular polygon #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Stochastic neural network #cs.GT #cs.LG #cs.NE #stat.ML
paper · pdf · doi:10.48550/arxiv.1604.01952
published in arXiv (Cornell University) (Cornell University) · 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
arxiv created 2016/04/07 · openalex publication_date 2016/04/07 · arxiv published 2016/04/07 · arxiv updated 2016/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.