Adaptive Algorithms for Online Convex Optimization

Elad Hazan

IBM Almaden, Theory Group

Abstract

In this talk we study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions. We then describe a series of reductions which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead. These efficiency preserving reductions are based on data streaming and sketching techniques which are new to online learning.

We describe applications of this technique to various well studied online problems, such as online routing, portfolio management and the tree update problem. In all cases we explain how previous algorithms perform suboptimally and how the reduction technique gives adaptive algorithms.

This talk is self-contained - no prior knowledge in machine learning or optimization is required.

Joint work with C. Seshadhri, Princeton University