History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Kaiyi Ji;Zhe Wang-;Bowen Weng;Yi Zhou;W. Zhang;Yingbin Liang
中科院分区：
文献类型：
--
作者：
Kaiyi Ji;Zhe Wang-;Bowen Weng;Yi Zhou;W. Zhang;Yingbin Liang
降方差算法虽然在理论上取得了很好的性能，但在实际应用中由于需要对大量数据进行周期性梯度估计，导致算法运行缓慢。因此，批量大小自适应成为加速此类算法的一种有前途的方法。然而，现有的方案要么采用规定的批量大小自适应规则，要么通过额外的回溯和条件验证步骤沿着优化路径利用信息。在本文中，我们提出了一种新的方案，该方案消除了回溯线搜索，但仍然通过历史随机梯度调整批大小来利用优化路径上的信息。我们进一步从理论上证明，这种方案大大降低了流行的方差减少算法SVRG和SARAH/SPIDER在传统非凸优化和强化学习问题上的总体复杂性。为此，我们开发了一个新的收敛分析框架来处理批大小对历史随机梯度的依赖性。大量的实验验证了所提出的批量大小自适应方案的有效性。
Variance-reduced algorithms, although achieve great theoretical performance, can run slowly in practice due to the periodic gradient estimation with a large batch of data. Batch-size adaptation thus arises as a promising approach to accelerate such algorithms. However, existing schemes either apply prescribed batch-size adaption rule or exploit the information along optimization path via additional backtracking and condition verification steps. In this paper, we propose a novel scheme, which eliminates backtracking line search but still exploits the information along optimization path by adapting the batch size via history stochastic gradients. We further theoretically show that such a scheme substantially reduces the overall complexity for popular variance-reduced algorithms SVRG and SARAH/SPIDER for both conventional nonconvex optimization and reinforcement learning problems. To this end, we develop a new convergence analysis framework to handle the dependence of the batch size on history stochastic gradients. Extensive experiments validate the effectiveness of the proposed batch-size adaptation scheme.