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

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2015, Volume 55, Number 4, Pages 582–598
DOI: https://doi.org/10.7868/S0044466915040043 (Mi zvmmf10186) 		 
This article is cited in 16 scientific papers (total in 16 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
Full-text PDF (701 kB) Citations (16)
References:
PDF
HTML
DOI: https://doi.org/10.7868/S0044466915040043
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.
Received: 03.09.2014
Revised: 29.10.2014
English version:
Computational Mathematics and Mathematical Physics, 2015, Volume 55, Issue 4, Pages 580–596
DOI: https://doi.org/10.1134/S0965542515040041
Bibliographic databases:
Document Type: Article
UDC: 519.658
MSC: Primary 90C15; Secondary 68W20
Language: Russian
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{https://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&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:
  • https://www.mathnet.ru/eng/zvmmf10186
  • https://www.mathnet.ru/eng/zvmmf/v55/i4/p582
    • This publication is cited in the following 16 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025