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

• 成果类型: Article
• 署名作者: Zhang, Junyu; Hong, Mingyi; Zhang, Shuzhong
• 署名单位: Princeton University; National University of Singapore; University of Minnesota System; University of Minnesota Twin Cities; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01660-z
• 发表日期: 2022
• 页码: 901-935
• 关键词: convergent newton method; variational-inequalities

摘要

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 (mu(x) and mu(y)), the class of pure first-order algorithms with the linear span assumption is shown to have a lower iteration complexity bound of Omega(root L-x/mu(x) + L-xy(2)/mu(x)mu(y) + L-y/mu(y) . ln (1/epsilon), where the term L-xy(2)/mu(x)mu(y) explains the coupling ' term 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(root L-xy(2)/mu(x)mu(y). ln (1/epsilon))( )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 mu(x )= mu(y) = 0. Several existing results in this case can be deduced from our results as special cases.