Fast Convergence Guarantees for Learning Simple Recurrent Neural Networks
Samet Oymak University of California, Riverside
Abstract
We study discrete time dynamical systems governed by the state equation $\bm{h}_{t+1}=\phi({\bm{A}}\bm{h}_{t}+{{\bm{B}}}{\bm{u}}_{t})$ . Here ${\bm{A}},{{\bm{B}}}$ are weight matrices, $\phi$ is an activation function, and ${\bm{u}}_{t}$ is the input data. This relation is the backbone of recurrent neural networks (e.g. LSTMs) which have broad applications in sequential learning tasks. We utilize stochastic gradient descent to learn the weight matrices from a finite input/state trajectory $\{{\bm{u}}_{t},\bm{h}_{t}\}_{t=0}^{N}$ . We prove that SGD estimate linearly converges to the ground truth weights while using near-optimal sample size. Our results apply to increasing activations whose derivatives are bounded away from zero. The analysis is based on i) a novel SGD convergence result with nonlinear activations and ii) careful statistical characterization of the state vector. Numerical experiments verify the fast convergence of SGD on ReLU and leaky ReLU in consistence with our theory.
中文速览
循环神经网络（RNN）的状态方程在序列学习中无处不在，但用随机梯度下降（SGD）训练它时需要多少数据、收敛速度究竟多快，理论上一直缺乏严格保证。这项工作针对带非线性激活函数（如leaky ReLU）的RNN状态方程，证明了SGD能够以线性速率收敛到真实权重矩阵，所需的轨迹长度仅为近乎最优的O(n+p)——即状态维度与输入维度之和——与未知参数数量基本匹配。关键分析分两步走：一是证明状态向量的协方差矩阵是良态的（条件数有界），二是建立一个新的SGD收敛定理，将非线性激活下的强凸性参数与线性情形挂钩，从而把非线性问题"归约"到线性动力系统的分析框架。这一结果首次为SGD训练RNN提供了端到端的非渐近理论保证，填补了RNN理论理解的重要空白，对序列建模和系统辨识的算法设计具有指导意义。
原文 arXiv:1809.03019;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1809.03019v1