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.

本文提出了一种适用于 Variance-reduced algorithms 的新型批量大小适应方案，通过历史随机梯度调整批量大小，避免了回溯线性搜索的步骤，有效地减少了 SVRG 和 SARAH/SPIDER 算法的复杂度，并开发了新的收敛分析框架来处理历史随机梯度对批量大小的依赖关系。