Efficient learning algorithms for changing environments

Elad E. Hazan, C. Seshadhri

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

6 Scopus citations

Abstract

We study online learning in an oblivious changing environment. The standard measure of regret bounds the difference between the cost of the online learner and the best decision in hindsight. Hence, regret minimizing algorithms tend to converge to the static best optimum, clearly a suboptimal behavior in changing environments. On the other hand, various metrics proposed to strengthen regret and allow for more dynamic algorithms produce inefficient algorithms. We propose a different performance metric which strengthens the standard metric of regret and measures performance with respect to a changing comparator. We then describe a series of datastreaming- based reductions which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead. Using this reduction, we obtain efficient low adaptive-regret algorithms for the problem of online convex optimization. This can be applied to various learning scenarios, i.e. online portfolio selection, for which we describe experimental results showing the advantage of adaptivity.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual International Conference on Machine Learning, ICML'09
DOIs
StatePublished - Sep 15 2009
Externally publishedYes
Event26th Annual International Conference on Machine Learning, ICML'09 - Montreal, QC, Canada
Duration: Jun 14 2009Jun 18 2009

Publication series

NameACM International Conference Proceeding Series
Volume382

Other

Other26th Annual International Conference on Machine Learning, ICML'09
CountryCanada
CityMontreal, QC
Period6/14/096/18/09

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Efficient learning algorithms for changing environments'. Together they form a unique fingerprint.

Cite this