On the efficiency of a randomized mirror descent algorithm in online optimization problems

A. V. Gasnikov   ; Yu. E. Nesterov   ; V. G. Spokoiny

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 4, pp. 582-598

Résumé

A randomized online version of the mirror descent method is proposed. It differs from the existing versions by the randomization method. Randomization is performed at the stage of the projection of a subgradient of the function being optimized onto the unit simplex rather than at the stage of the computation of a subgradient, which is common practice. As a result, a componentwise subgradient descent with a randomly chosen component is obtained, which admits an online interpretation. This observation, for example, has made it possible to uniformly interpret results on weighting expert decisions and propose the most efficient method for searching for an equilibrium in a zero-sum two-person matrix game with sparse matrix.

Bibliographie

[1] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, M., 1979 http://www2.isye.gatech.edu/ñemirovs/Lect_EMCO.pdf | MR

[2] Beck A., Teboulle M., “Mirror descent and nonlinear projected subgradient methods for convex optimization”, Oper. Res. Lett., 31 (2003), 167–175 | MR | Zbl

[3] Nesterov Y., “Primal-dual subgradient methods for convex problems”, Math. Program. Ser. B, 120:1 (2009), 261–283 | MR

[4] Yuditskii A. B., Nazin A. V., Tsybakov A. B., Vayatis N., “Rekurrentnoe agregirovanie otsenok metodom zerkalnogo spuska s usredneniem”, Probl. peredachi informatsii, 41:4 (2005), 78–96 | MR | Zbl

[5] Bubeck S., Introduction to online optimization, Lecture Notes, Princeton University, 2011 http://www.princeton.edu/s̃bubeck/BubeckLectureNotes.pdf

[6] Grigoriadis M., Khachiyan L., “A sublinear-time randomized approximation algorithm for matrix games”, Oper. Res. Lett., 18:2 (1995), 53–58 | MR | Zbl

[7] Juditsky A., Lan G., Nemirovski A., Shapiro A., “Stochastic approximation approach to stochastic programming”, SIAM J. Optimizat., 19:4 (2009), 1574–1609 http://www2.isye.gatech.edu/ñemirovs/ | MR | Zbl

[8] Nazin A. V., Polyak B. T., “Randomizirovannyi algoritm nakhozhdeniya sobstvennogo vektora stokhasticheskoi matritsy s primeneniem k zadache PageRank”, Avtomatika i telemekh., 2011, no. 2, 131–141

[9] Lugosi G., Cesa-Bianchi N., Prediction, learning and games, Cambridge University Press, New York, 2006 | MR | Zbl

[10] Juditsky A., Nazin A. V., Tsybakov A. B., Vayatis N., “Gap-free bounds for stochastic multi-armed bandit”, Proc. 17$^{\mathrm{th}}$ World Congress IFAC (Seoul, Korea, July 6–11, 2008), 11560–11563

[11] Mansour Y., Algorithmic game theory and machine learning, Lect. 1, 2, 6, , 2011 http://www.tau.ac.il/m̃ansour/advanced-agt+ml/

[12] Rakhlin A., Lecture notes on online learning, , 2009 http://stat.wharton.upenn.edu/r̃akhlin/papers/online_learning.pdf

[13] Hazan E., “The convex optimization approach to regret minimization”, Optimiz. for Machine Learning, eds. S. Sra, S. Nowozin, S. Wright, MIT Press, 2011, 287–303

[14] Bubeck S., Cesa-Bianchi N., “Regret analysis of stochastic and nonstochastic multi-armed bandit problems”, Foundation and Trends in Machine Learning, 5:1 (2012), 1–122 http://www.princeton.edu/s̃bubeck/SurveyBCB12.pdf | Zbl

[15] Shi Z., Liu R., Online universal gradient method, 2013, arXiv: 1311.3832v2

[16] Juditsky A., Nemirovski A., “First order methods for nonsmooth convex large-scale optimization. I; II”, Optimizat. for Machine Learning, eds. S. Sra, S. Nowozin, S. Wright, MIT Press, 2012

[17] Boucheron S., Lugoshi G., Massart P., Concentration inequalities: a nonasymptotic theory of independence, Oxford University Press, 2013 | MR | Zbl

[18] Lan G., Nemirovski A., Shapiro A., “Validation analysis of mirror descent stochastic approximation method”, Math. Program., 134:2 (2012), 425–458 | MR | Zbl

[19] Andersen S. P., de Palma A., Thisse J. A.-F., Discrete choice theory of product differentiation, MIT Press, Camb., 1992 | MR

[20] Lidbetter M., Lindgren G., Rotsen Kh., Ekstremumy sluchainykh posledovatelnostei i protsessov, Mir, M., 1989 | MR

[21] Gasnikov A. V., Dorn Yu. V., Nesterov Yu. E., Shpirko S. V., “O trekhstadiinoi versii modeli statsionarnoi dinamiki transportnykh potokov”, Matem. modelirovanie, 26:6 (2014), 34–70, arXiv: 1405.7630 | Zbl

[22] Gasnikov A. V., Dmitriev D. Yu., “Ob effektivnykh randomizirovannykh algoritmakh poiska vektora PageRank”, Zh. vychisl. matem. i matem. fiz., 55:3 (2015), 355–371, arXiv: 1410.3120 | Zbl

[23] Vyugin V. V., Matematicheskie osnovy teorii mashinnogo obucheniya i prognozirovaniya, MTsNMO, M., 2013 http://www.iitp.ru/upload/publications/6256/vyugin1.pdf

[24] Nemirovski A., “Prox-method with rate of convergence $O(1/T)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems”, SIAM J. Optimizat., 15 (2004), 229–251 | MR | Zbl

[25] Nesterov Y., “Smooth minimization of non-smooth function”, Math. Program. Ser. A, 103:1 (2005), 127–152 | MR | Zbl

[26] Nesterov Y. E., “Subgradient methods for huge-scale optimization problems”, Math. Program. Ser. A, 2014 (to appear) ; CORE Discussion Paper 2012/2, 2012 | MR

[27] Nesterov Y. E., “Efficiency of coordinate descent methods on large scale optimization problem”, SIAM J. Optimizat., 22:2 (2012), 341–362 | MR | Zbl

[28] Bubeck S., Theory of convex optimization for machine learning, 2014, arXiv: 1405.4980

[29] Fercoq O., Richtárik P., Accelerated, parallel and proximal coordinate descent, 2013, arXiv: 1312.5799

[30] Tao T., Struktura i sluchainost, MTsNMO, M., 2013

[31] Motwani R., Raghavan P., Randomized algorithms, Cambridge Univ. Press, 1995 | MR | Zbl

[32] Dubhashi D. P., Panconesi A., Concentration of measure for the analysis of randomized algorithms, Cambridge University Press, 2009 | MR | Zbl

[33] Spielman D. A., Teng S.-H., “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time”, J. ACM, 51 (2004), 385–463 | MR | Zbl

[34] Ledoux M., Concentration of measure phenomenon, Math. Surveys Monogr., 89, Amer. Math. Soc., Providence, RI, 2001 | MR | Zbl