Tight Lower Complexity Bounds for Strongly Convex Finite-Sum
  Optimization
  Finite-sum optimization plays an important role in the area of machine
learning, and hence has triggered a surge of interest in recent years. To
address this optimization problem, various randomized incremental gradient
methods have been proposed with guaranteed upper and lower complexity bounds
for their convergence. Nonetheless, these lower bounds rely on certain
conditions: deterministic optimization algorithm, or fixed probability
distribution for the selection of component functions. Meanwhile, some lower
bounds even do not match the upper bounds of the best known methods in certain
cases. To break these limitations, we derive tight lower complexity bounds of
randomized incremental gradient methods, including SAG, SAGA, SVRG, and SARAH,
for two typical cases of finite-sum optimization. Specifically, our results
tightly match the upper complexity of Katyusha when each component function is
strongly convex and smooth, and tightly match the upper complexity of SDCA
without duality and of KatyushaX when the finite-sum function is strongly
convex and the component functions are average smooth.
