  We develop and analyze a new family of {\em nonaccelerated and accelerated
loopless variance-reduced methods} for finite sum optimization problems. Our
convergence analysis relies on a novel expected smoothness condition which
upper bounds the variance of the stochastic gradient estimation by a constant
times a distance-like function. This allows us to handle with ease {\em
arbitrary sampling schemes} as well as the nonconvex case. We perform an
in-depth estimation of these expected smoothness parameters and propose new
importance samplings which allow {\em linear speedup} when the expected
minibatch size is in a certain range. Furthermore, a connection between these
expected smoothness parameters and expected separable overapproximation (ESO)
is established, which allows us to exploit data sparsity as well. Our results
recover as special cases the recently proposed loopless SVRG and loopless
Katyusha.
