Online learning with prior knowledge

Elad Hazan, Nimrod Megiddo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

The standard so-called experts algorithms are methods for utilizing a given set of "experts" to make good choices in a sequential decision-making problem. In the standard setting of experts algorithms, the decision maker chooses repeatedly in the same "state" based on information about how the different experts would have performed if chosen to be followed. In this paper we seek to extend this framework by introducing state information. More precisely, we extend the framework by allowing an experts algorithm to rely on state information, namely, partial information about the cost function, which is revealed to the decision maker before the latter chooses an action. This extension is very natural in prediction problems. For illustration, an experts algorithm, which is supposed to predict whether the next day will be rainy, can be extended to predicting the same given the current temperature. We introduce new algorithms, which attain optimal performance in the new framework, and apply to more general settings than variants of regression that have been considered in the statistics literature.

Original languageEnglish (US)
Title of host publicationLearning Theory - 20th Annual Conference on Learning Theory, COLT 2007, Proceedings
PublisherSpringer Verlag
Pages499-513
Number of pages15
ISBN (Print)9783540729259
DOIs
StatePublished - 2007
Externally publishedYes
Event20th Annual Conference on Learning Theory, COLT 2007 - San Diego, CA, United States
Duration: Jun 13 2007Jun 15 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4539 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th Annual Conference on Learning Theory, COLT 2007
CountryUnited States
CitySan Diego, CA
Period6/13/076/15/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Online learning with prior knowledge'. Together they form a unique fingerprint.

Cite this