|
This article is cited in 13 scientific papers (total in 13 papers)
Optimal control
Accelerated methods for saddle-point problem
M. S. Alkousaab, A. V. Gasnikovabc, D. M. Dvinskikhcd, D. A. Kovaleve, F. S. Stonyakinf a Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
b National Research University "Higher School of Economics", Moscow
c Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow
d Weierstrass Institute for Applied Analysis and Stochastics, Berlin
e King Abdullah University of Science and Technology
f Crimea Federal University, Simferopol
Abstract:
Recently, it has been shown how, on the basis of the usual accelerated gradient method for solving problems of smooth convex optimization, accelerated methods for more complex problems (with a structure) and problems that are solved using various local information about the behavior of a function (stochastic gradient, Hessian, etc.) can be obtained. The term “accelerated methods” here means, on the one hand, the presence of some unified and fairly general way of acceleration. On the other hand, this also means the optimality of the methods, which can often be proved rigorously. In the present work, an attempt is made to construct in the same way a theory of accelerated methods for solving smooth convex-concave saddle-point problems with a structure. The main result of this article is the obtainment of in some sense necessary and sufficient conditions under which the complexity of solving nonlinear convex-concave saddle-point problems with a structure in the number of calculations of the gradients of composites in direct variables is equal in order of magnitude to the complexity of solving bilinear problems with a structure.
Key words:
saddle problem, accelerated method, sliding, prox-friendly function.
Received: 01.12.2019 Revised: 20.12.2019 Accepted: 07.07.2020
Citation:
M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev, F. S. Stonyakin, “Accelerated methods for saddle-point problem”, Zh. Vychisl. Mat. Mat. Fiz., 60:11 (2020), 1843–1866; Comput. Math. Math. Phys., 60:11 (2020), 1787–1809
Linking options:
https://www.mathnet.ru/eng/zvmmf11157 https://www.mathnet.ru/eng/zvmmf/v60/i11/p1843
|
Statistics & downloads: |
Abstract page: | 177 | References: | 31 |
|