On lower iteration complexity bounds for the convex concave saddle point problems

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 xmax yF(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 (Lx, Ly and Lxy) 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 languageEnglish (US)
Pages (from-to)901-935
Number of pages35
JournalMathematical Programming
Volume194
Issue number1-2
DOIs
StateAccepted/In press - 2021
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'On lower iteration complexity bounds for the convex concave saddle point problems'. Together they form a unique fingerprint.

Cite this