On-line learning algorithms for path experts with non-additive losses

Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Manfred K. Warmuth

Research output: Contribution to journalConference article

Abstract

We consider two broad families of non-additive loss functions covering a large number of applications: rational losses and tropical losses. We give new algorithms extending the Followthe- Perturbed-Leader (FPL) algorithm to both of these families of loss functions and similarly give new algorithms extending the Randomized Weighted Majority (RWM) algorithm to both of these families. We prove that the time complexity of our extensions to rational losses of both FPL and RWM is polynomial and present regret bounds for both. We further show that these algorithms can play a critical role in improving performance in applications such as structured prediction.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume40
Issue number2015
StatePublished - 2015
Event28th Conference on Learning Theory, COLT 2015 - Paris, France
Duration: Jul 2 2015Jul 6 2015

Keywords

  • Experts
  • Non-additive losses
  • On-line learning
  • Structured prediction

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'On-line learning algorithms for path experts with non-additive losses'. Together they form a unique fingerprint.

  • Cite this