  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 or VRADA 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.
