Optimal Algorithm with Complexity Separation for Strongly Convex-Strongly Concave Composite Saddle Point Problems

Abstract

In this work, we focuses on the following saddle point problem ${\min }_x{\max }_{y}p(x)+R(x,y)-q(y)$ where $R(x,y)$ is $L_R$-smooth, ${\mu }_x$-strongly convex, ${\mu }_y$-strongly concave and $p(x),q(y)$ are convex and $L_p,L_q$-smooth respectively. We present a new algorithm with optimal overall complexity $\mathcal{O}\left(\left(\sqrt{\frac{L_p}{{\mu }_x}}+\frac{L_R}{\sqrt{{\mu }_x{\mu }_y}}+\sqrt{\frac{L_q}{{\mu }_y}}\right)\log \frac{1}{\epsilon }\right)$ and separation of oracle calls in the composite and saddle part. This algorithm requires $\mathcal{O}\left(\left(\sqrt{\frac{L_p}{{\mu }_x}}+\sqrt{\frac{L_q}{{\mu }_y}}\right)\log \frac{1}{\epsilon }\right)$ oracle calls for $\nabla p(x)$ and $\nabla q(y)$ and $\mathcal{O}\left(\max \left\{\sqrt{\frac{L_p}{{\mu }_x}},\sqrt{\frac{L_q}{{\mu }_y}},\frac{L_R}{\sqrt{{\mu }_x{\mu }_y}}\right\}\log \frac{1}{\epsilon }\right)$ oracle calls for $\nabla R(x,y)$ to find an $\epsilon$-solution of the problem. To the best of our knowledge, we are the first to develop optimal algorithm with complexity separation in the case ${\mu }_x\ne {\mu }_y$. Also, we apply this algorithm to a bilinear saddle point problem and obtain the optimal complexity for this class of problems.

work in progress