Generalized Optimistic Methods for Convex-Concave Saddle Point Problems

. The optimistic gradient method has seen increasing popularity as an efficient first-order method for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work A. Mokhtari, A. E. Ozdaglar, and S. Pattathil, SIAM J. Optim. , 30 (2020), pp. 3230–3251 proposed an interesting perspective that interprets the optimistic gradient method as an approximation to the proximal point method. In this paper, we follow this approach and distill the underlying idea of optimism to propose a generalized optimistic method, which encompasses the optimistic gradient method as a special case. Our general framework can handle constrained saddle point problems with composite objective functions. Moreover, we also develop a backtracking line search scheme to select the step sizes without knowledge of the smoothness coefficients. By instantiating our general framework with a second-order oracle, we propose a second-order optimistic method and prove a complexity bound of \ (O (^-. 5ex 2 -. 1em / -. 15em. 25ex \, 3) \) in terms of the primal-dual gap in the convex-concave setting and a complexity bound of \ (O ( (. 5ex L₂ D -. 1em / -. 15em. 25ex \, ) ^. 5ex 2 -. 1em / -. 15em. 25ex \, 3+ (. 5ex 1 -. 1em / -. 15em. 25ex \, ) ) \) in terms of the distance to the optimal solution in the strongly-convex-strongly-concave setting, where \ (L₂\) is the Lipschitz constant of the Jacobian, \ (\) is the strong convexity parameter, and \ (D\) is the initial Euclidean distance to the saddle point. We also establish convergence rates in terms of the tangent residual, which generalizes the operator norm as a metric in the unconstrained setting. Moreover, our line search scheme provably only requires a constant number of calls to a subproblem solver per iteration on average. Keywordsconvex-concave saddle point problemsoptimistic methodssecond-order methodsMSC codes90C2590C3390C47