Premium
AN ONLINE PORTFOLIO SELECTION ALGORITHM WITH REGRET LOGARITHMIC IN PRICE VARIATION
Author(s) -
Hazan Elad,
Kale Satyen
Publication year - 2015
Publication title -
mathematical finance
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.98
H-Index - 81
eISSN - 1467-9965
pISSN - 0960-1627
DOI - 10.1111/mafi.12006
Subject(s) - regret , portfolio , logarithm , mathematics , asymptotically optimal algorithm , hindsight bias , bounded function , mathematical optimization , constant (computer programming) , upper and lower bounds , portfolio optimization , computer science , economics , finance , statistics , psychology , mathematical analysis , cognitive psychology , programming language
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 (log Q ), 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 (log T ), 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.[Note 2. An extended abstract of this work appeared in Hazan ...]