Accelerated methods for saddle-point problem (Q2214606)

The paper deals with a class of smooth convex-concave saddle-point optimization problems with a special structure arising, e.g., in image processing and when solving various inverse problems. It is proposed to reduce the considered saddle-point problems to a combination of auxiliary minimization problems with smooth strongly convex functions that are separately formulated for different groups of variables. Each of the auxiliary problems can be solved by the aforementioned fast gradient method of Yu. E. Nesterov. In this case, the inaccuracy of solving a given auxiliary subproblem for one of the groups of variables leads to the concept of an inexact oracle, for which estimates of the convergence rate of the fast gradient method are known. The authors use the approach of accelerated sliding proposed by \textit{G. Lan} [First-order and stochastic optimization methods for machine learning. Cham: Springer (2020; Zbl 1442.68003)] and accelerate them using a transformation of the properties of smoothness and strong convexity (the curvature of the graph of a function, determined by the extremal values of its Hessian) under the Fenchel-Legendre transformation. This has permitted them to obtain new and significantly better estimates for the number of calculations of the gradient w.r.t. direct variables in nonlinear saddle-point problems with a structure. The conditions are presented under which the complexity of solving nonlinear convex-concave saddle-point problems is equal in order of magnitude to the complexity of solving bilinear problems with a structure.