Harvard Theory of Computation Seminar

New Techniques in Online Convex Optimization and their Applications

Elad Hazan, Princeton University

Place and Time: Monday 3/13, Maxwell-Dworkin 319 Refreshments at 2:30, talk at 2:45.

ABSTRACT

In the first part of the talk we introduce a new algorithm and a new analysis technique that is applicable to a variety of online optimization scenarios, including regret minimization for Lipschitz regret functions studied by Hannan, universal portfolios by Cover, Kalai and Vempala, online convex optimization by Zinkevich, and others. Our algorithm is more efficient and applies to a more general setting then previous methods.

The algorithm extends a method proposed by Hannan in the 1950's, called `Follow the Leader", and shows a surprising connection to the Newton method for offline optimization. One application is the well studied universal portfolio management problem, for which our algorithm combines optimal regret with computational efficiency. For more general settings, our algorithm is the first to achieve logarithmic regret (as opposed to polynomial).

Time permitting, in the second part of the talk we survey the applications of online game playing algorithms for obtaining efficient offline optimization algorithms.