TY - GEN

T1 - Efficient learning algorithms for changing environments

AU - Hazan, Elad

AU - Seshadhri, C.

PY - 2009/12/9

Y1 - 2009/12/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=71149091248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71149091248&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:71149091248

SN - 9781605585161

T3 - Proceedings of the 26th International Conference On Machine Learning, ICML 2009

SP - 393

EP - 400

BT - Proceedings of the 26th International Conference On Machine Learning, ICML 2009

T2 - 26th International Conference On Machine Learning, ICML 2009

Y2 - 14 June 2009 through 18 June 2009

ER -