Efficient Algorithms for Universal Portfolios
Adam Kalai, Santosh Vempala;
3(Nov):423-440, 2002.
Abstract
A constant rebalanced portfolio is an investment strategy that keeps
the same distribution of wealth among a set of stocks from day to day.
There has been much work on Cover's Universal algorithm, which
is competitive with the best constant rebalanced portfolio determined
in hindsight (Cover, 1991, Helmbold et al, 1998, Blum and Kalai, 1999,
Foster and Vohra, 1999, Vovk, 1998, Cover and Ordentlich, 1996a,
Cover, 1996c).
While this algorithm has good performance guarantees, all known
implementations are exponential in the number of stocks, restricting
the number of stocks used in
experiments (Helmbold et al, 1998, Cover and Ordentlich, 1996a,
Ordentlich and Cover, 1996b, Cover, 1996c, Blum and Kalai, 1999). We present an
efficient implementation of the Universal algorithm that is
based on non-uniform random walks that are rapidly mixing (Applegate
and Kannan, 1991, Lovasz and Simonovits, 1992, Frieze and Kannan, 1999).
This same implementation also works for
non-financial applications of
the Universal algorithm, such as data compression (Cover, 1996c) and language
modeling (Chen et al, 1999).
[abs]
[pdf]
[ps.gz]
[ps]
