Title: Limitations on Variance-Reduction and Acceleration Schemes for Finite Sum Optimization,
Abstract: We study the conditions under which one is able to efficiently apply
variance-reduction and acceleration schemes on finite sum optimization
problems. First, we show that, perhaps surprisingly, the finite sum structure
by itself, is not sufficient for obtaining a complexity bound of
$\tilde{\cO}((n+L/\mu)\ln(1/\epsilon))$ for $L$-smooth and $\mu$-strongly
convex individual functions - one must also know which individual function is
being referred to by the oracle at each iteration. Next, we show that for a
broad class of first-order and coordinate-descent finite sum algorithms
(including, e.g., SDCA, SVRG, SAG), it is not possible to get an `accelerated'
complexity bound of $\tilde{\cO}((n+\sqrt{n L/\mu})\ln(1/\epsilon))$, unless
the strong convexity parameter is given explicitly. Lastly, we show that when
this class of algorithms is used for minimizing $L$-smooth and convex finite
sums, the optimal complexity bound is $\tilde{\cO}(n+L/\epsilon)$, assuming
that (on average) the same update rule is used in every iteration, and
$\tilde{\cO}(n+\sqrt{nL/\epsilon})$, otherwise.