New Algorithms for Repeated Play and Universal Portfolio Management

Abstract:

We introduce a new algorithm, smooth prediction, and a new analysis technique that is applicable to a variety of online optimization scenarios, including those studied by Hannan, Cover, Kalai and Vempala, Zinkevich and others. Our algorithm is more efficient and applies to a more general setting (e.g. when the payoff function is unknown).

The algorithm extends a method proposed by Hannan in the 1950's, namely ``Follow the Leader" scheme. It adds a barrier function to the convex optimization routine required to find the ``leader" at every iteration. This variant of Follow the Leader has optimal regret, answering a question of Kalai and Vempala.

One application of our algorithm is the well studied universal portfolio management problem, for which our algorithm is the first to combine optimal convergence rate with computational efficiency. For more general settings, our algorithm is the first to achieve optimal convergence rate.