  Many canonical machine learning problems boil down to a convex optimization
problem with a finite sum structure. However, whereas much progress has been
made in developing faster algorithms for this setting, the inherent limitations
of these problems are not satisfactorily addressed by existing lower bounds.
Indeed, current bounds focus on first-order optimization algorithms, and only
apply in the often unrealistic regime where the number of iterations is less
than $\mathcal{O}(d/n)$ (where $d$ is the dimension and $n$ is the number of
samples). In this work, we extend the framework of (Arjevani et al., 2015) to
provide new lower bounds, which are dimension-free, and go beyond the
assumptions of current bounds, thereby covering standard finite sum
optimization methods, e.g., SAG, SAGA, SVRG, SDCA without duality, as well as
stochastic coordinate-descent methods, such as SDCA and accelerated proximal
SDCA.
