Online learning in case of unbounded losses using follow the perturbed leader algorithm

Vladimir V. V'Yugin

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

In this paper the sequential prediction problem with expert advice is considered for the case where losses of experts suffered at each step cannot be bounded in advance. We present some modification of Kalai and Vempala algorithm of following the perturbed leader where weights depend on past losses of the experts. New notions of a volume and a scaled fluctuation of a game are introduced. We present a probabilistic algorithm protected from unrestrictedly large one-step losses. This algorithm has the optimal performance in the case when the scaled fluctuations of one-step losses of experts of the pool tend to zero.

Original languageEnglish
Pages (from-to)241-266
Number of pages26
JournalJournal of Machine Learning Research
Volume12
Publication statusPublished - Jan 2011
Externally publishedYes

Keywords

  • Adaptive learning rate
  • Expected bounds
  • Follow the perturbed leader
  • Hannan consistency
  • Online sequential prediction
  • Prediction with expert advice
  • Unbounded losses

Fingerprint

Dive into the research topics of 'Online learning in case of unbounded losses using follow the perturbed leader algorithm'. Together they form a unique fingerprint.

Cite this