Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zh. Vychisl. Mat. Mat. Fiz., 2015, Volume 55, Number 4, Pages 582–598 (Mi zvmmf10186)  

This article is cited in 9 scientific papers (total in 9 papers)

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

A. V. Gasnikovabc, Yu. E. Nesterovbca, V. G. Spokoinyacb

a Moscow Institute of Physics and Technology, Institutskii per. 9, Dolgoprudnyi, Moscow oblast, 141700, Russia
b National Research University Higher School of Economics, Myasnitskaya ul. 20, Moscow, 101000, Russia
c Institute for Information Transmission Problems, Russian Academy of Sciences, Bolshoi Karetnyi per. 19, Moscow, 127051, Russia

Abstract: 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.

Key words: mirror descent method, dual averaging method, online optimization, exponential weighting, multi-armed bandits, weighting of experts, stochastic optimization, randomization.

DOI: https://doi.org/10.7868/S0044466915040043

Full text: PDF file (701 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2015, 55:4, 580–596

Bibliographic databases:

UDC: 519.658
MSC: Primary 90C15; Secondary 68W20
Received: 03.09.2014
Revised: 29.10.2014

Citation: A. V. Gasnikov, Yu. E. Nesterov, V. G. Spokoiny, “On the efficiency of a randomized mirror descent algorithm in online optimization problems”, Zh. Vychisl. Mat. Mat. Fiz., 55:4 (2015), 582–598; Comput. Math. Math. Phys., 55:4 (2015), 580–596

Citation in format AMSBIB
\Bibitem{GasNesSpo15}
\by A.~V.~Gasnikov, Yu.~E.~Nesterov, V.~G.~Spokoiny
\paper On the efficiency of a randomized mirror descent algorithm in online optimization problems
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2015
\vol 55
\issue 4
\pages 582--598
\mathnet{http://mi.mathnet.ru/zvmmf10186}
\crossref{https://doi.org/10.7868/S0044466915040043}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3343121}
\zmath{https://zbmath.org/?q=an:06458234}
\elib{https://elibrary.ru/item.asp?id=23299887}
\transl
\jour Comput. Math. Math. Phys.
\yr 2015
\vol 55
\issue 4
\pages 580--596
\crossref{https://doi.org/10.1134/S0965542515040041}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000354067600006}
\elib{https://elibrary.ru/item.asp?id=24027745}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84928879773}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10186
  • http://mi.mathnet.ru/eng/zvmmf/v55/i4/p582

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Gasnikov, “Ob effektivnoi vychislimosti konkurentnykh ravnovesii v transportno-ekonomicheskikh modelyakh”, Matem. modelirovanie, 27:12 (2015), 121–136  mathnet  elib
    2. A. V. Gasnikov, A. A. Lagunovskaya, I. N. Usmanova, F. A. Fedorenko, “Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex”, Autom. Remote Control, 77:11 (2016), 2018–2034  mathnet  crossref  isi  elib
    3. A. V. Gasnikov, P. E. Dvurechenskii, Yu. V. Dorn, Yu. V. Maksimov, “Chislennye metody poiska ravnovesnogo raspredeleniya potokov v modeli Bekmana i v modeli stabilnoi dinamiki”, Matem. modelirovanie, 28:10 (2016), 40–64  mathnet  elib
    4. A. Kolnogorov, D. Shiyan, “Parallel version of the mirror descent algorithm for the two-armed bandit problem”, Proceedings of the 3rd International Conference on Mathematics and Computers in Sciences and in Industry, MCSI 2016, IEEE, 2016, 241–245  crossref  isi
    5. A. V. Kolnogorov, “Adaptive normal two-armed bandit and data processing optimization”, IFAC PAPERSONLINE, 49:13 (2016), 241–246  crossref  mathscinet  isi
    6. A. V. Gasnikov, E. A. Krymova, A. A. Lagunovskaya, I. N. Usmanova, F. A. Fedorenko, “Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case”, Autom. Remote Control, 78:2 (2017), 224–234  mathnet  crossref  mathscinet  isi  elib
    7. A. Kolnogorov, “Minimax normal two-armed bandit with indefinite control horizon”, 2016 International Conference Applied Mathematics, Computational Science and Systems Engineering, ITM Web of Conferences, 9, eds. N. Bardis, J. Quartieri, C. Guarnaccia, N. Doukas, EDP Sciences, 2017, UNSP 01002  crossref  isi
    8. A. V. Kolnogorov, “Gaussian two-armed bandit and optimization of batch data processing”, Problems Inform. Transmission, 54:1 (2018), 84–100  mathnet  crossref  isi  elib
    9. Aleksandr V. Kolnogorov, Aleksandr V. Nazin, Dmitrii N. Shiyan, “Zadacha o dvurukom bandite i paketnaya versiya algoritma zerkalnogo spuska”, MTIP, 13:2 (2021), 9–39  mathnet
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:406
    Full text:67
    References:51
    First page:25

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022