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

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

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)580-596
Number of pages17
JournalComputational Mathematics and Mathematical Physics
Volume55
Issue number4
DOIs
Publication statusPublished - 1 Apr 2015
Externally publishedYes

Keywords

  • dual averaging method
  • exponential weighting
  • mirror descent method
  • multi-armed bandits
  • online optimization
  • randomization
  • stochastic optimization
  • weighting of experts

Fingerprint

Dive into the research topics of 'On the efficiency of a randomized mirror descent algorithm in online optimization problems'. Together they form a unique fingerprint.

Cite this