An Online Portfolio Selection Algorithm With Regret Logarithmic In Price Variation

Elad Hazan, Satyen Kale

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

We present a novel efficient algorithm for portfolio selection which theoretically attains two desirable properties: Worst-case guarantee: the algorithm is universal in the sense that it asymptotically performs almost as well as the best constant rebalanced portfolio determined in hindsight from the realized market prices. Furthermore, it attains the tightest known bounds on the regret, or the log-wealth difference relative to the best constant rebalanced portfolio. We prove that the regret of the algorithm is bounded by O(logQ), where Q is the quadratic variation of the stock prices. This is the first improvement upon Cover's (1991) seminal work that attains a regret bound of O(logT), where T is the number of trading iterations. Average-case guarantee: in the Geometric Brownian Motion (GBM) model of stock prices, our algorithm attains tighter regret bounds, which are provably impossible in the worst-case. Hence, when the GBM model is a good approximation of the behavior of market, the new algorithm has an advantage over previous ones, albeit retaining worst-case guarantees. We derive this algorithm as a special case of a novel and more general method for online convex optimization with exp-concave loss functions.

Original languageEnglish (US)
Pages (from-to)288-310
Number of pages23
JournalMathematical Finance
Volume25
Issue number2
DOIs
StatePublished - Apr 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Accounting
  • Social Sciences (miscellaneous)
  • Finance
  • Economics and Econometrics
  • Applied Mathematics

Keywords

  • Online convex optimization
  • Portfolio selection
  • Regret minimization

Fingerprint

Dive into the research topics of 'An Online Portfolio Selection Algorithm With Regret Logarithmic In Price Variation'. Together they form a unique fingerprint.

Cite this