2020/12/31 by Ostroukhov, Petr, Kamalov, Rinat, Dvurechensky, Pavel +1 · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2012.15595
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 ( ( \fracLp Rp - 1μ )^(2)/(p + 1) log (μR2)/(εG) ), where R is an estimate of the initial distance to the solution, and εG 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 ( ( \fracLp Rp - 1μ )^(2)/(p + 1)log \fracL2 R max \ 1, \fracL1μ \μ + log (log (L13)/(2 μ2 εG))/(log (L1 L2)/(μ2)) ). The third method is a modified version of the second method, and it solves gradient norm minimization SPP with O ( ( (Lp Rp)/(ε_∇) )^(2)/(p + 1) ) oracle calls, where ε_∇ 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.