  In this paper, we study the lower iteration complexity bounds for finding the
saddle point of a strongly convex and strongly concave saddle point problem:
$\min_x\max_yF(x,y)$. We restrict the classes of algorithms in our
investigation to be either pure first-order methods or methods using proximal
mappings. The existing lower bound result for this type of problems is obtained
via the framework of strongly monotone variational inequality problems, which
corresponds to the case where the gradient Lipschitz constants ($L_x, L_y$ and
$L_{xy}$) and strong convexity/concavity constants ($\mu_x$ and $\mu_y$) are
uniform with respect to variables $x$ and $y$. However, specific to the min-max
saddle point problem these parameters are naturally different. Therefore, one
is led to finding the best possible lower iteration complexity bounds, specific
to the min-max saddle point models. In this paper we present the following
results. For the class of pure first-order algorithms, our lower iteration
complexity bound is
$\Omega\left(\sqrt{\frac{L_x}{\mu_x}+\frac{L_{xy}^2}{\mu_x\mu_y}+\frac{L_y}{\mu_y}}\cdot\ln\left(\frac{1}{\epsilon}\right)\right)$,
where the term $\frac{L_{xy}^2}{\mu_x\mu_y}$ explains how the coupling
influences the iteration complexity. Under several special parameter regimes,
this lower bound has been achieved by corresponding optimal algorithms.
However, whether or not the bound under the general parameter regime is optimal
remains open. Additionally, for the special case of bilinear coupling problems,
given the availability of certain proximal operators, a lower bound of
$\Omega\left(\sqrt{\frac{L_{xy}^2}{\mu_x\mu_y}+1}\cdot\ln(\frac{1}{\epsilon})\right)$
is established in this paper, and optimal algorithms have already been
developed in the literature.
