Asynchronous Mini-Batch Gradient Descent with Variance Reduction for Non-Convex Optimization
Asynchronous Mini-Batch Gradient Descent with Variance Reduction for Non-Convex Optimization
复制标题
DOI：
10.1609/aaai.v31i1.10940
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Zhouyuan Huo;Heng Huang
中科院分区：
文献类型：
--
作者：
Zhouyuan Huo;Heng Huang
我们提供了第一个非凸优化的异步小批量方差减少梯度下降（AsySVRG）的收敛速度的理论分析。异步随机梯度下降（AsySGD）已被广泛用于深度学习优化，并被证明对非凸优化具有O（1/\sqrt{T}）的收敛速度。最近，方差缩减技术被提出，并被证明可以大大加快SGD的收敛速度。证明了当问题为强凸时，采用方差缩减技术的异步SGD方法具有线性收敛速度。然而，目前还没有工作来分析这种方法对非凸问题的收敛速度。本文研究了方差缩减的小批量梯度下降法的两种异步并行实现：一种是分布式存储结构，另一种是共享存储结构。我们证明了这两种方法可以收敛的速度为O（1/T）的非凸优化，线性加速比是可以访问的，当我们增加工人的数量。我们通过在两个真实的数据集（MNIST和CIFAR-10）上优化多层神经网络来评估我们的方法，实验结果证明了我们的理论分析。
We provide the first theoretical analysis on the convergence rate of asynchronous mini-batch gradient descent with variance reduction (AsySVRG) for non-convex optimization. Asynchronous stochastic gradient descent (AsySGD) has been broadly used for deep learning optimization, and it is proved to converge with rate of O(1/\sqrt{T}) for non-convex optimization. Recently, variance reduction technique is proposed and it is proved to be able to accelerate the convergence of SGD greatly. It is shown that asynchronous SGD method with variance reduction technique has linear convergence rate when problem is strongly convex. However, there is still no work to analyze the convergence rate of this method for non-convex problem. In this paper, we consider two asynchronous parallel implementations of mini-batch gradient descent method with variance reduction: one is on distributed-memory architecture and the other is on shared-memory architecture. We prove that both methods can converge with a rate of O(1/T) for non-convex optimization, and linear speedup is accessible when we increase the number of workers. We evaluate our methods by optimizing multi-layer neural networks on two real datasets (MNIST and CIFAR-10), and experimental results demonstrate our theoretical analysis.