Efficient learning algorithms for changing environments

Elad Hazan, C. Seshadhri

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

97 Scopus citations


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 data-streaming-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 International Conference On Machine Learning, ICML 2009
Number of pages8
StatePublished - 2009
Externally publishedYes
Event26th International Conference On Machine Learning, ICML 2009 - Montreal, QC, Canada
Duration: Jun 14 2009Jun 18 2009

Publication series

NameProceedings of the 26th International Conference On Machine Learning, ICML 2009


Other26th International Conference On Machine Learning, ICML 2009
CityMontreal, QC

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Software


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

Cite this