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{http://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:
    1. Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, Alexander Gasnikov, “High-Probability Complexity Bounds for Non-smooth Stochastic Convex Optimization with Heavy-Tailed Noise”, J Optim Theory Appl, 2024  crossref
    2. A. V. Kolnogorov, A. V. Nazin, D. N. Shiyan, “Two-Armed Bandit Problem and Batch Version of the Mirror Descent Algorithm”, Autom Remote Control, 83:8 (2022), 1288  crossref
    3. 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
    4. Alexander Kolnogorov, 2021 XVII International Symposium “Problems of Redundancy in Information and Control Systems” (REDUNDANCY), 2021, 74  crossref
    5. A. Anikin, A. Gasnikov, A. Gornov, D. Kamzolov, Yu. Maximov, Yu. Nesterov, “Efficient numerical methods to solve sparse linear equations with application to pagerank”, Optim. Method Softw., 2020  crossref  mathscinet  isi
    6. Alexander Kolnogorov, Denis Grunev, 2020 24th International Conference on Circuits, Systems, Communications and Computers (CSCC), 2020, 79  crossref
    7. 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
    8. 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
    9. 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
    10. 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
    11. 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
    12. 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
    13. A. V. Kolnogorov, “Adaptive normal two-armed bandit and data processing optimization”, IFAC PAPERSONLINE, 49:13 (2016), 241–246  crossref  mathscinet  isi  scopus
    14. Alexander Kolnogorov, Dmitry Shiyan, 2016 Third International Conference on Mathematics and Computers in Sciences and in Industry (MCSI), 2016, 241  crossref
    15. Alexander V. Kolnogorov, “A Generalization of Robust Normal Two-Armed Bandit**This work was supported in part by the Project Part of the State Assignment in the Field of Scientific Activity by the Ministry of Education and Science of the Russian Federation, project no. 1.949.2014/K.”, IFAC-PapersOnLine, 49:13 (2016), 247  crossref
    16. A. V. Gasnikov, “Ob effektivnoi vychislimosti konkurentnykh ravnovesii v transportno-ekonomicheskikh modelyakh”, Matem. modelirovanie, 27:12 (2015), 121–136  mathnet  elib
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Statistics & downloads:
    Abstract page:645
    Full-text PDF :177
    References:95
    First page:25
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025