Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
  and Construction
  The contribution of this paper includes two aspects. First, we study the
lower bound complexity for the minimax optimization problem whose objective
function is the average of $n$ individual smooth component functions. We
consider Proximal Incremental First-order (PIFO) algorithms which have access
to gradient and proximal oracle for each individual component. We develop a
novel approach for constructing adversarial problems, which partitions the
tridiagonal matrix of classical examples into $n$ groups. This construction is
friendly to the analysis of incremental gradient and proximal oracle. With this
approach, we demonstrate the lower bounds of first-order algorithms for finding
an $\varepsilon$-suboptimal point and an $\varepsilon$-stationary point in
different settings. Second, we also derive the lower bounds of minimization
optimization with PIFO algorithms from our approach, which can cover the
results in \citep{woodworth2016tight} and improve the results in
\citep{zhou2019lower}.
