In this paper we present interpolation conditions for several important convex-concave function
classes: nonsmooth convex-concave functions, conditions for difference of strongly-convex
functions in a form that contains oracle information exclusively and smooth convex-concave
functions with a bilinear coupling term. Then we demonstrate how the performance estimation
problem approach can be adapted to analyze the exact worst-case convergence behavior of firstorder
methods applied to composite bilinear-coupled min-max problems. Using the performance
estimation problem approach, we estimate iteration complexities for several first-order fixed-step
methods, Sim-GDA and Alt-GDA, which are applied to smooth convex-concave functions with
a bilinear coupling term.
Keywords:
saddle point, convex-concave functions, bilinear coupling, performance estimation problem, interpolation conditions
Citation:
Krivchenko V. O., Gasnikov A. V., Kovalev D. A., Convex-Concave Interpolation and Application of PEP to the Bilinear-Coupled Saddle Point Problem, Rus. J. Nonlin. Dyn.,
2024, Vol. 20, no. 5,
pp. 875-893
DOI:10.20537/nd241215