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 算法的复杂度，并开发了新的收敛分析框架来处理历史随机梯度对批量大小的依赖关系。

通过历史梯度辅助批大小调整用于方差减小算法

History-Gradient Aided Batch Size Adaptation for Variance Reduced  Algorithms

Several useful variance-reduced stochastic gradient algorithms, such as SVRG,
SAGA, Finito, and SAG, have been proposed to minimize empirical risks with
linear convergence properties to the exact minimizer. The existing convergence
results assume uniform data sampling with replacement. However, it has been
observed in related works that random reshuffling can deliver superior
performance over uniform sampling and, yet, no formal proofs or guarantees of
exact convergence exist for variance-reduced algorithms under random
reshuffling. This paper makes two contributions. First, it resolves this open
issue and provides the first theoretical guarantee of linear convergence under
random reshuffling for SAGA; the argument is also adaptable to other
variance-reduced algorithms. Second, under random reshuffling, the paper
proposes a new amortized variance-reduced gradient (AVRG) algorithm with
constant storage requirements compared to SAGA and with balanced gradient
computations compared to SVRG. AVRG is also shown analytically to converge
linearly.

本文研究基于方差减小的随机梯度算法，探究了随机数据抽样和随机重排的条件下的线性收敛性和新的 AVRG 算法，并给出了理论保证。