Deep Online Convex Optimization with Gated Games
David Balduzzi
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 neura
中文速览
把训练深度卷积网络（rectifier convnet）的收敛性搞清楚，是深度学习理论中长期悬而未决的难题，因为整流线性单元（ReLU）和最大池化（max-pooling）让网络既不光滑也不凸，经典优化理论的收敛保证全部失效。这篇论文的突破口在于把网络里的每个神经元看作博弈中的"玩家"，并引入了一种新的"门控博弈"（gated game）框架——整流单元的开/关特性天然形成一扇"门"，让底层线性网络的凸博弈分析工具得以延伸到非凸、非光滑的真实网络。基于这一框架，作者证明了反向传播在整流卷积网络上以"门控遗憾"（gated regret）为核心量控制的速率收敛到临界点，这是该类网络首个有理论依据的收敛速率结果；顺带还给出了对数遗憾的训练算法以及分析条件计算（conditional computation）与注意力机制的理论接口。这项工作的重要性在于，它首次为工业界真正在用的网络架构提供了严格的收敛保证，并在博弈论与深度学习之间建立了一座可供后续研究深入利用的理论桥梁。
原文 arXiv:1604.01952;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1604.01952v1