Geodesic
On the efficiency of a randomized mirror descent algorithm in online optimization problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 4, pp. 582-598

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{ZVMMF_2015_55_4_a6,
     author = {A. V. Gasnikov and Yu. E. Nesterov and V. G. Spokoiny},
     title = {On the efficiency of a randomized mirror descent algorithm in online optimization problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {582--598},
     publisher = {mathdoc},
     volume = {55},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a6/}
}
TY  - JOUR
AU  - A. V. Gasnikov
AU  - Yu. E. Nesterov
AU  - V. G. Spokoiny
TI  - On the efficiency of a randomized mirror descent algorithm in online optimization problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2015
SP  - 582
EP  - 598
VL  - 55
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a6/
LA  - ru
ID  - ZVMMF_2015_55_4_a6
ER  - 
%0 Journal Article
%A A. V. Gasnikov
%A Yu. E. Nesterov
%A V. G. Spokoiny
%T On the efficiency of a randomized mirror descent algorithm in online optimization problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2015
%P 582-598
%V 55
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a6/
%G ru
%F ZVMMF_2015_55_4_a6
A. V. Gasnikov; Yu. E. Nesterov; V. G. Spokoiny. On the efficiency of a randomized mirror descent algorithm in online optimization problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 4, pp. 582-598. http://geodesic.mathdoc.fr/item/ZVMMF_2015_55_4_a6/