An Online Portfolio Selection Algorithm With Regret Logarithmic In Price Variation

Elad Hazan, Satyen Kale

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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
Issue number2
StatePublished - Apr 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • Online convex optimization
  • Portfolio selection
  • Regret minimization


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