## Abstract

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 _{y}F(x, y). We restrict the classes of algorithms in our investigation to be either pure first-order methods or methods using proximal mappings. For problems with gradient Lipschitz constants (L_{x}, L_{y} and L_{xy}) and strong convexity/concavity constants (μ_{x} and μ_{y}), the class of pure first-order algorithms with the linear span assumption is shown to have a lower iteration complexity bound of Ω(Lxμx+Lxy2μxμy+Lyμy·ln(1ϵ)), where the term Lxy2μxμ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 Ω(Lxy2μxμy·ln(1ϵ)) is established under the linear span assumption, and optimal algorithms have already been developed in the literature. By exploiting the orthogonal invariance technique, we extend both lower bounds to the general pure first-order algorithm class and the proximal algorithm class without the linear span assumption. As an application, we apply proper scaling to the worst-case instances, and we derive the lower bounds for the general convex concave problems with μ_{x}= μ_{y}= 0. Several existing results in this case can be deduced from our results as special cases.

Original language | English (US) |
---|---|

Pages (from-to) | 901-935 |

Number of pages | 35 |

Journal | Mathematical Programming |

Volume | 194 |

Issue number | 1-2 |

DOIs | |

State | Accepted/In press - 2021 |

Externally published | Yes |

### Bibliographical note

Funding Information:We thank the two anonymous reviewers for their insightful suggestions on orthogonal invariance argument for breaking the linear span assumption and the suggestion on applying scaling to obtain lower bounds for general convex-concave problems.

Publisher Copyright:

© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

## Keywords

- First-order method
- Lower iteration complexity bound
- Min-max problem
- Proximal mapping
- Saddle point