Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities

In this paper we propose three p-th order tensor methods for μ-strongly-convex-strongly-concave saddle point problems (SPP). The first method is based on the assumption of p-th order smoothness of the objective and it achieves a convergence rate of O left( left( fracLp Rp - 1μ right)^frac2p + 1 log fracμ R2varepsilonG right), where R is an estimate of the initial distance to the solution, and varepsilonG is the error in terms of duality gap. Under additional assumptions of first and second order smoothness of the objective we connect the first method with a locally superlinear converging algorithm and develop a second method with the complexity of O left( left( fracLp Rp - 1μ right)^frac2p + 1log fracL2 R max left 1, fracL1μ rightμ + log fraclog fracL132 μ2 varepsilonGlog fracL1 L2μ2 right). The third method is a modified version of the second method, and it solves gradient norm minimization SPP with tilde O left( left( fracLp Rpvarepsilon_nabla right)^frac2p + 1 right) oracle calls, where varepsilon_nabla is an error in terms of norm of the gradient of the objective. Since we treat SPP as a particular case of variational inequalities, we also propose three methods for strongly monotone variational inequalities with the same complexity as the described above.