Efficient and Near-Optimal Online Portfolio Selection

Rémi Jézéquel (), Dmitrii Ostrovskii () and Pierre Gaillard ()
Additional contact information
Rémi Jézéquel: SIERRA - Statistical Machine Learning and Parsimony - DI-ENS - Département d'informatique - ENS-PSL - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris Sciences et Lettres - Inria - Institut National de Recherche en Informatique et en Automatique - CNRS - Centre National de la Recherche Scientifique - CNRS - Centre National de la Recherche Scientifique - Centre Inria de Paris - Inria - Institut National de Recherche en Informatique et en Automatique
Dmitrii Ostrovskii: USC - University of Southern California, SIERRA - Statistical Machine Learning and Parsimony - DI-ENS - Département d'informatique - ENS-PSL - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris Sciences et Lettres - Inria - Institut National de Recherche en Informatique et en Automatique - CNRS - Centre National de la Recherche Scientifique - CNRS - Centre National de la Recherche Scientifique - Centre Inria de Paris - Inria - Institut National de Recherche en Informatique et en Automatique
Pierre Gaillard: Thoth - Apprentissage de modèles à partir de données massives - Centre Inria de l'Université Grenoble Alpes - Inria - Institut National de Recherche en Informatique et en Automatique - LJK - Laboratoire Jean Kuntzmann - Inria - Institut National de Recherche en Informatique et en Automatique - CNRS - Centre National de la Recherche Scientifique - UGA - Université Grenoble Alpes - Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology - UGA - Université Grenoble Alpes

Working Papers from HAL

Abstract: In the problem of online portfolio selection as formulated by Cover (1991), the trader repeatedly distributes her capital over $ d $ assets in each of $ T > 1 $ rounds, with the goal of maximizing the total return. Cover proposed an algorithm, termed Universal Portfolios, that performs nearly as well as the best (in hindsight) static assignment of a portfolio, with an $ O(d\log(T)) $ regret in terms of the logarithmic return. Without imposing any restrictions on the market this guarantee is known to be worst-case optimal, and no other algorithm attaining it has been discovered so far. Unfortunately, Cover's algorithm crucially relies on computing certain $ d $-dimensional integral which must be approximated in any implementation; this results in a prohibitive $ \tilde O(d^4(T+d)^{14}) $ per-round runtime for the fastest known implementation due to Kalai and Vempala (2002). We propose an algorithm for online portfolio selection that admits essentially the same regret guarantee as Universal Portfolios -- up to a constant factor and replacement of $ \log(T) $ with $ \log(T+d) $ -- yet has a drastically reduced runtime of $ \tilde O(d^2(T+d)) $ per round. The selected portfolio minimizes the current logarithmic loss regularized by the log-determinant of its Hessian -- equivalently, the hybrid logarithmic-volumetric barrier of the polytope specified by the asset return vectors. As such, our work reveals surprising connections of online portfolio selection with two classical topics in optimization theory: cutting-plane and interior-point algorithms.

Date: 2022-09-27
Note: View the original document on HAL open archive server: https://hal.science/hal-03787674v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://hal.science/hal-03787674v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-03787674

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().