Universal intermediate gradient method for convex problems with inexact oracle. (English) Zbl 1493.90132

Kamzolov, Dmitry; Dvurechensky, Pavel; Gasnikov, Alexander V.

Optim. Methods Softw. 36, No. 6, 1289-1316 (2021).

Summary: In this paper, we propose new first-order methods for minimization of a convex function on a simple convex set. We assume that the objective function is a composite function given as a sum of a simple convex function and a convex function with inexact Hölder-continuous subgradient. We propose Universal Intermediate Gradient Method. Our method enjoys both the universality and intermediateness properties. Following the ideas of Y. Nesterov [Math. Program. 152, No. 1–2 (A), 381–404 (2015; Zbl 1327.90216)] on Universal Gradient Methods, our method does not require any information about the Hölder parameter and constant and adjusts itself automatically to the local level of smoothness. On the other hand, in the spirit of the Intermediate Gradient Method proposed by O. Devolder et al. [Intermediate gradient methods for smooth convex problems with inexact oracle. Techn. Rep., Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) (2013), https://EconPapers.repec.org/RePEc:cor:louvco:2013017], our method is intermediate in the sense that it interpolates between Universal Gradient Method and Universal Fast Gradient Method. This allows to balance the rate of convergence of the method and rate of the oracle error accumulation. Under the additional assumption of strong convexity of the objective, we show how the restart technique can be used to obtain an algorithm with faster rate of convergence.

MSC:

90C25	Convex programming
90C47	Minimax problems in mathematical programming
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

convex optimization; first-order methods; inexact oracle; intermediate gradient methods; complexity bounds

Citations:

Zbl 1327.90216

Software:

NESUN

References:

[1]	Anikin, A. S.; Gasnikov, A. V.; Dvurechensky, P. E.; Tyurin, A. I.; Chernov, A. V., Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints, Comput. Math. Math. Phys., 57, 1262-1276 (2017) · Zbl 1380.49046 · doi:10.1134/S0965542517080048
[2]	Baimurzina, D. R.; Gasnikov, A. V.; Gasnikova, E. V.; Dvurechensky, P. E.; Ershov, E. I.; Kubentaeva, M. B.; Lagunovskaya, A. A., Universal method of searching for equilibria and stochastic equilibria in transportation networks, Comput. Math. Math. Phys., 59, 19-33 (2019) · Zbl 1419.90013 · doi:10.1134/S0965542519010020
[3]	Ben-Tal, A.; Margalit, T.; Nemirovski, A., The ordered subsets mirror descent optimization method with applications to tomography, SIAM J. Optim., 12, 79-108 (2001) · Zbl 0992.92034 · doi:10.1137/S1052623499354564
[4]	Ben-Tal, A. and Nemirovski, A., Lectures on modern convex optimization (Lecture notes), Personal web-page of A. Nemirovski, 2015. Available at http://www2.isye.gatech.edu/nemirovs/Lect_ModConvOpt.pdf.
[5]	Bogolubsky, L., Dvurechensky, P., Gasnikov, A., Gusev, G., Nesterov, Y., Raigorodskii, A.M., Tikhonov, A., and Zhukovskii, M., Learning supervised pagerank with gradient-based and gradient-free optimization methods, in Advances in Neural Information Processing Systems 29, D.D. Lee, M. Sugiyama, U.V. Luxburg, I. Guyon, and R. Garnett, eds., Curran Associates, Inc., Barcelona, 2016, pp. 4914-4922, arXiv:1603.00717.
[6]	Chernov, A., Dvurechensky, P., and Gasnikov, A., Fast primal-dual gradient method for strongly convex minimization problems with linear constraints, Discrete Optimization and Operations Research: 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings, Springer International Publishing, 2016, pp. 391-403. · Zbl 1391.90471
[7]	d’Aspremont, A., Smooth optimization with approximate gradient, SIAM J. Optim., 19, 1171-1183 (2008) · Zbl 1180.90378 · doi:10.1137/060676386
[8]	Devolder, O., Glineur, F., and Nesterov, Y., Intermediate gradient methods for smooth convex problems with inexact oracle (2013), CORE Discussion Paper 2013/17. · Zbl 1317.90196
[9]	Devolder, O.; Glineur, F.; Nesterov, Y., First-order methods of smooth convex optimization with inexact oracle, Math. Program., 146, 37-75 (2014) · Zbl 1317.90196 · doi:10.1007/s10107-013-0677-5
[10]	Dvurechensky, P.; Gasnikov, A., Stochastic intermediate gradient method for convex problems with stochastic inexact oracle, J. Optim. Theory Appl., 171, 121-145 (2016) · Zbl 1351.90150 · doi:10.1007/s10957-016-0999-6
[11]	Dvurechensky, P., Gasnikov, A., and Kroshnin, A., Computational optimal transport: complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm, Stockholm, Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 80, arXiv:1802.04367, 2018, pp. 1367-1376.
[12]	Dvurechensky, P., Gasnikov, A., Gasnikova, E., Matsievsky, S., Rodomanov, A., and Usik, I., Primal-dual method for searching equilibrium in hierarchical congestion population games, Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016) Vladivostok, Russia, September 19-23, 2016, arXiv:1606.08988, 2016, pp. 584-595.
[13]	Dvurechensky, P., Gasnikov, A., Omelchenko, S., and Tiurin, A., Adaptive similar triangles method: a stable alternative to sinkhorn’s algorithm for regularized optimal transport, preprint arXiv:1706.07622 (2017). · Zbl 1460.90029
[14]	Dvurechensky, P., Dvinskikh, D., Gasnikov, A., Uribe, C.A., and Nedić, A., Decentralize and randomize: faster algorithm for wasserstein barycenters, in Advances in Neural Information Processing Systems 31, NeurIPS 2018, arXiv:1806.03915, Curran Associates, Inc., 2018, pp. 10783-10793.
[15]	Fercoq, O. and Qu, Z., Restarting accelerated gradient methods with a rough strong convexity estimate, preprint arXiv:1609.07358 (2016). · Zbl 1432.90109
[16]	Fercoq, O.; Qu, Z., Adaptive restart of accelerated gradient methods under local quadratic growth condition, IMA J. Numer. Anal., 39, 2069-2095 (2019) · Zbl 07130820 · doi:10.1093/imanum/drz007
[17]	Gasnikov, A., Dvurechensky, P., and Kamzolov, D., Gradient and gradient-free methods for stochastic convex optimization with inexact oracle, Dynamics systems and control processes. Proceedings of the International Conference Dedicated to the 90th Anniversary of the Birth of Academic N. N. Krasovsky. (2015), pp. 111-117. Available at https://arxiv.org/abs/1502.06259.
[18]	Gasnikov, A.; Dvurechensky, P.; Nesterov, Y., Stochastic gradient methods with inexact oracle, Proc. Moscow Inst. Phys. Technol., 8, 41-91 (2016)
[19]	Gasnikov, A.; Kamzolov, D.; Mendel, M., Universal composite prox-method for strictly convex optimization problems, TRUDY MIPT, 8, 25-42 (2016)
[20]	Gasnikov, A.; Nesterov, Y., Universal fast gradient method for stochastic composite optimization problems, Comput. Math. Math. Phys., 58, 51-68 (2018)
[21]	Gasnikov, A.; Dvurechensky, P.; Kamzolov, D.; Nesterov, Y.; Spokoiny, V.; Stetsyuk, P.; Suvorikova, A.; Chernov, A., Universal method with inexact oracle and its applications for searching equillibriums in multistage transport problems, TRUDY MIPT, 7, 143-155 (2015)
[22]	Gasnikov, A., Kabanikhin, S., Mohamed, A., and Shishlenin, M., Convex optimization in Hilbert space with applications to inverse problems, preprint arXiv:1703.00267 (2017).
[23]	Gasnikov, A. V.; Dvurechensky, P. E., Stochastic intermediate gradient method for convex optimization problems, Doklady Math., 93, 148-151 (2016) · Zbl 1342.90131 · doi:10.1134/S1064562416020071
[24]	Gasnikov, A. V.; Tyurin, A. I., Fast gradient descent for convex minimization problems with an oracle producing a \((####)\)-model of function at the requested point, Comput. Math. Math. Phys., 59, 1085-1097 (2019) · Zbl 1531.90101 · doi:10.1134/S0965542519070078
[25]	Ghadimi, S.; Lan, G.; Zhang, H., Generalized uniformly optimal methods for nonlinear programming, J. Sci. Comput., 79, 1854-1881 (2019) · Zbl 1418.90191 · doi:10.1007/s10915-019-00915-4
[26]	Guminov, S. V.; Nesterov, Y. E.; Dvurechensky, P. E.; Gasnikov, A. V., Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems, Doklady Math., 99, 125-128 (2019) · Zbl 1418.90192 · doi:10.1134/S1064562419020042
[27]	He, N., Harchaoui, Z., Wang, Y., and Song, L., Fast and simple optimization for poisson likelihood models, preprint arXiv:1608.01264 (2016).
[28]	Juditsky, A.; Nesterov, Y., Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization, Stochastic Syst., 4, 44-80 (2014) · Zbl 1297.90097 · doi:10.1287/10-SSY010
[29]	Lan, G., An optimal method for stochastic composite optimization, Math. Program., 133, 365-397 (2012) · Zbl 1273.90136 · doi:10.1007/s10107-010-0434-y
[30]	Nemirovskii, A.; Nesterov, Y., Optimal methods of smooth convex minimization, USSR Comput. Math. Math. Phys., 25, 21-30 (1985) · Zbl 0591.90072 · doi:10.1016/0041-5553(85)90100-4
[31]	Nemirovsky, A.; Yudin, D., Problem Complexity and Method Efficiency in Optimization (1983), J. Wiley & Sons: J. Wiley & Sons, New York · Zbl 0501.90062
[32]	Nesterov, Y., A method for unconstrained convex minimization problem with the rate of convergence \(####\), in Doklady AN USSR, Vol. 269, 1983, pp. 543-547.
[33]	Nesterov, Y., Gradient methods for minimizing composite functions, Math. Program., 140, 125-161 (2013) · Zbl 1287.90067 · doi:10.1007/s10107-012-0629-5
[34]	Nesterov, Y., Universal gradient methods for convex optimization problems, Math. Program., 152, 381-404 (2015) · Zbl 1327.90216 · doi:10.1007/s10107-014-0790-0
[35]	Ogaltsov, A., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., and Spokoiny, V., Adaptive gradient descent for convex and non-convex stochastic optimization, arXiv:1911.08380 (2019).
[36]	Roulet, V. and d’Aspremont, A., Sharpness, restart and acceleration, in Advances in Neural Information Processing Systems, 2017, pp. 1119-1129.
[37]	Stonyakin, F., Gasnikov, A., Tyurin, A., Pasechnyuk, D., Agafonov, A., Dvurechensky, P., Dvinskikh, D., Kroshnin, A., and Piskunova, V., Inexact model: a framework for optimization and variational inequalities, arXiv:1902.00990 (2019). · Zbl 1437.90126
[38]	Stonyakin, F.S., Dvinskikh, D., Dvurechensky, P., Kroshnin, A., Kuznetsova, O., Agafonov, A., Gasnikov, A., Tyurin, A., Uribe, C.A., Pasechnyuk, D., and Artamonov, S., Gradient methods for problems with inexact model of the objective, in Mathematical Optimization Theory and Operations Research, Springer International Publishing, Cham, 2019, pp. 97-114, arXiv:1902.09001. · Zbl 1437.90126
[39]	Yurtsever, A., Tran-Dinh, Q., and Cevher, V., A universal primal-dual convex optimization framework, Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS’15, Montreal, Canada, MIT Press, Cambridge, MA, USA, 2015, pp. 3150-3158.