Fast Variance Reduction Method with Stochastic Batch Size
  In this paper we study a family of variance reduction methods with randomized
batch size---at each step, the algorithm first randomly chooses the batch size
and then selects a batch of samples to conduct a variance-reduced stochastic
update. We give the linear convergence rate for this framework for composite
functions, and show that the optimal strategy to achieve the optimal
convergence rate per data access is to always choose batch size of 1, which is
equivalent to the SAGA algorithm. However, due to the presence of cache/disk IO
effect in computer architecture, the number of data access cannot reflect the
running time because of 1) random memory access is much slower than sequential
access, 2) when data is too big to fit into memory, disk seeking takes even
longer time. After taking these into account, choosing batch size of $1$ is no
longer optimal, so we propose a new algorithm called SAGA++ and show how to
calculate the optimal average batch size theoretically. Our algorithm
outperforms SAGA and other existing batched and stochastic solvers on real
datasets. In addition, we also conduct a precise analysis to compare different
update rules for variance reduction methods, showing that SAGA++ converges
faster than SVRG in theory.
