Generalized Optimistic Methods for Convex-Concave Saddle Point Problems

The optimistic gradient method has seen increasing popularity for solvingconvex-concave saddle point problems. To analyze its iteration complexity, arecent work [arXiv:1906.01115] proposed an interesting perspective thatinterprets this method as an approximation to the proximal point method. Inthis paper, we follow this approach and distill the underlying idea of optimismto propose a generalized optimistic method, which includes the optimisticgradient method as a special case. Our general framework can handle constrainedsaddle point problems with composite objective functions and can work witharbitrary norms using Bregman distances. Moreover, we develop a backtrackingline search scheme to select the step sizes without knowledge of the smoothnesscoefficients. We instantiate our method with first-, second- and higher-orderoracles and give best-known global iteration complexity bounds. For ourfirst-order method, we show that the averaged iterates converge at a rate of$O(1/N)$ when the objective function is convex-concave, and it achieves linearconvergence when the objective is strongly-convex-strongly-concave. For oursecond- and higher-order methods, under the additional assumption that thedistance-generating function has Lipschitz gradient, we prove a complexitybound of $O(1/\epsilon^\frac{2}{p+1})$ in the convex-concave setting and acomplexity bound of$O((L_pD^\frac{p-1}{2}/\mu)^\frac{2}{p+1}+\log\log\frac{1}{\epsilon})$ in thestrongly-convex-strongly-concave setting, where $L_p$ ($p\geq 2$) is theLipschitz constant of the $p$-th-order derivative, $\mu$ is the strongconvexity parameter, and $D$ is the initial Bregman distance to the saddlepoint. Moreover, our line search scheme provably only requires a constantnumber of calls to a subproblem solver per iteration on average, making ourfirst- and second-order methods particularly amenable to implementation.