Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable

M. S. Alkousa   ; A. V. Gasnikov   ; E. L. Gladin   ; I. A. Kuruzov   ; D. A. Pasechnyuk   ; F. S. Stonyakin

Sbornik. Mathematics, Tome 214 (2023) no. 3, pp. 285-333

Résumé

Algorithmic methods are developed that guarantee efficient complexity estimates for strongly convex-concave saddle-point problems in the case when one group of variables has a high dimension, while another has a rather low dimension (up to 100). These methods are based on reducing problems of this type to the minimization (maximization) problem for a convex (concave) functional with respect to one of the variables such that an approximate value of the gradient at an arbitrary point can be obtained with the required accuracy using an auxiliary optimization subproblem with respect to the other variable. It is proposed to use the ellipsoid method and Vaidya's method for low-dimensional problems and accelerated gradient methods with inexact information about the gradient or subgradient for high-dimensional problems. In the case when one group of variables, ranging over a hypercube, has a very low dimension (up to five), another proposed approach to strongly convex-concave saddle-point problems is rather efficient. This approach is based on a new version of a multidimensional analogue of Nesterov's method on a square (the multidimensional dichotomy method) with the possibility to use inexact values of the gradient of the objective functional. Bibliography: 28 titles.

Détail

Keywords: saddle-point problem, ellipsoid method, Vaidya's method, inexact subgradient, multidimensional dichotomy.
Mots-clés : hypercube

Bibliographie

[1] M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin, “Accelerated methods for saddle-point problem”, Zh. Vychisl. Mat. Mat. Fiz., 60:11 (2020), 1843–1866 ; English transl. in Comput. Math. Math. Phys., 60:11 (2020), 1787–1809 | DOI | MR | Zbl | DOI

[2] W. Azizian, I. Mitliagkas, S. Lacoste-Julien and G. Gidel, “A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games”, Proceedings of the twenty third international conference on artificial intelligence and statistics, Proceedings of Machine Learning Research (PMLR), 108, 2020, 2863–2873, https://proceedings.mlr.press/v108/azizian20b.html

[3] A. V. Gasnikov, P. E. Dvurechensky and Yu. E. Nesterov, “Stochastic gradient methods with inexact oracle”, Tr. Mosk. Fiz. Tekhn. Inst., 8:1 (2016), 41–91 (Russian)

[4] A. V. Gasnikov, D. M. Dvinskikh, P. E. Dvurechensky, D. I. Kamzolov, V. V. Matyukhin, D. A. Pasechnyuk, N. K. Tupitsa and A. V. Chernov, “Accelerated meta-algorithm for convex optimization problems”, Zh. Vychisl. Mat. Mat. Fiz., 61:1 (2021), 20–31 ; English transl. in Comput. Math. Math. Phys., 61:1 (2021), 17–28 | DOI | Zbl | DOI | MR

[5] Le Thi Khanh Hien, Renbo Zhao and W. B. Haskell, An inexact primal-dual framework for large-scale non-bilinear saddle point problem, arXiv: 1711.03669

[6] Guanghui Lan, First-order and stochastic optimization methods for machine learning, Springer Ser. Data Sci., Springer, Cham, 2020, xiii+582 pp. | DOI | MR | Zbl

[7] Tianyi Lin, Chi Jin and M. I. Jordan, “Near-optimal algorithms for minimax optimization”, Proceedings of thirty third conference on learning theory, Proceedings of Machine Learning Research (PMLR), 125, 2020, 2738–2779, https://proceedings.mlr.press/v125/lin20a.html

[8] I. Usmanova, M. Kamgarpour, A. Krause and K. Levy, “Fast projection onto convex smooth constraints”, Proceedings of the 38th international conference on machine learning, Proceedings of Machine Learning Research (PMLR), 139, 2021, 10476–10486, http://proceedings.mlr.press/v139/usmanova21a.html

[9] Ђ. V. Gasnikov, Modern numerical methods of optimization. The method of universal gradient descent, 2ns revised ed., Moscow Center for Continuous Mathematical Education, Moscow, 2021, 272 pp. (Russian)

[10] B. Cox, A. Juditsky and A. Nemirovski, “Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators”, J. Optim. Theory Appl., 172:2 (2017), 402–435 | DOI | MR | Zbl

[11] Yu. Nesterov, “Excessive gap technique in nonsmooth convex minimization”, SIAM J. Optim., 16:1 (2005), 235–249 | DOI | MR | Zbl

[12] Junyu Zhang, Mingyi Hong and Shuzhong Zhang, “On lower iteration complexity bounds for the convex concave saddle point problems”, Math. Program., 194:1–2, Ser. A (2022), 901–935 | DOI | MR | Zbl

[13] Yuanhao Wang and Jian Li, “Improved algorithms for convex-concave minimax optimization”, NIPS 2020, Adv. Neural Inf. Process. Syst., 33, MIT Press, Cambridge, MA, 2020, 11 pp. ; arXiv: http://proceedings.neurips.cc/paper/20202006.06359

[14] A. Nemirovski, S. Onn and U. G. Rothblum, “Accuracy certificates for computational problems with convex structure”, Math. Oper. Res., 35:1 (2010), 52–78 | DOI | MR | Zbl

[15] A. Nemirovski, Information-based complexity of convex programming, Lecture notes, 1995, 268 pp. https://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf

[16] D. A. Pasechnyuk and F. S. Stonyakin, “One method for minimization a convex Lipschitz-continuous function of two variables on a fixed square”, Komp'yuter. Issled. Modelirovanie, 11:3 (2019), 379–395 (Russian) | DOI

[17] B. T. Polyak, Introduction to optimization, Nauka, Moscow, 1983, 384 pp. ; English transl., Transl. Ser. Math. Eng., Optimization Software, Inc., Publications Division, New York, 1987, xxvii+438 pp. | MR | Zbl | MR

[18] O. Devolder, F. Glineur and Yu. Nesterov, “First-order methods of smooth convex optimization with inexact oracle”, Math. Program., 146:1–2, Ser. A (2014), 37–75 | DOI | MR | Zbl

[19] P. M. Vaidya, “A new algorithm for minimizing convex functions over convex sets”, Math. Program., 73:3, Ser. A (1996), 291–341 | DOI | MR | Zbl

[20] S. Bubeck, “Convex optimization: algorithms and complexity”, Found. Trends Mach. Learn., 8:3–4 (2015), 231–357 | Zbl

[21] E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov and M. Alkousa, “Solving smooth min-min and min-max problems by mixed oracle algorithms”, MOTOR 2021: Mathematical optimization theory and operations research — recent trends, Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 19–40 | DOI | MR

[22] A. V. Gasnikov and Yu. E. Nesterov, “Universal method for stochastic composite optimization problems”, Zh. Vychisl. Mat. Mat. Fiz., 58:1 (2018), 52–69 ; English transl. in Comput. Math. Math. Phys., 58:1 (2018), 48–64 | DOI | Zbl | DOI | MR

[23] J. M. Danskin, “The theory of Max-Min, with applications”, SIAM J. Appl. Math., 14:4 (1966), 641–664 | DOI | MR | Zbl

[24] O. Devolder, Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, PhD thesis, UCL, CORE, Louvain-la-Neuve, 2013, vii+309 pp. https://dial.uclouvain.be/pr/boreal/en/object/boreal

[25] O. Devolder, F. Glineur and Yu. Nesterov, First-order methods with inexact oracle: the strongly convex case, CORE Discussion Papers, no. 2013/16, 2013, 35 pp. http://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2013_16web.pdf

[26] N. Z. Shor, Minimization methods for non-differentiable functions, Naukova dumka, Kiev, 1979, 199 pp. ; English transl., Springer Ser. Comput. Math., 3, Springer-Verlag, Berlin, 1985, viii+162 pp. | MR | Zbl | DOI | MR | Zbl

[27] Source code for experiments on GitHub, https://github.com/ASEDOS999/SPP

[28] P. Bernhard and A. Rapaport, “On a theorem of Danskin with an application to a theorem of von Neumann-Sion”, Nonlinear Anal., 24:8 (1995), 1163–1181 | DOI | MR | Zbl