  In this paper, we study the lower complexity bounds for finite-sum
optimization problems, where the objective is the average of $n$ individual
component functions. We consider Proximal Incremental First-order (PIFO)
algorithms which have access to the gradient and proximal oracles for each
component function. To incorporate loopless methods, we also allow PIFO
algorithms to obtain the full gradient infrequently. We develop a novel
approach to constructing the hard instances, which partitions the tridiagonal
matrix of classical examples into $n$ groups. This construction is friendly to
the analysis of PIFO algorithms. Based on this construction, we establish the
lower complexity bounds for finite-sum minimax optimization problems when the
objective is convex-concave or nonconvex-strongly-concave and the class of
component functions is $L$-average smooth. Most of these bounds are nearly
matched by existing upper bounds up to log factors. We can also derive similar
lower bounds for finite-sum minimization problems as previous work under both
smoothness and average smoothness assumptions. Our lower bounds imply that
proximal oracles for smooth functions are not much more powerful than gradient
oracles.
