IDEAS home Printed from https://ideas.repec.org/p/hal/wpaper/hal-03787674.html
   My bibliography  Save this paper

Efficient and Near-Optimal Online Portfolio Selection

Author

Listed:
  • Rémi Jézéquel

    (SIERRA - Statistical Machine Learning and Parsimony - DI-ENS - Département d'informatique - ENS Paris - 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 - Inria de Paris - Inria - Institut National de Recherche en Informatique et en Automatique)

  • Dmitrii M. Ostrovskii

    (USC - University of Southern California, SIERRA - Statistical Machine Learning and Parsimony - DI-ENS - Département d'informatique - ENS Paris - 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 - 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 - Inria Grenoble - Rhône-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)

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.

Suggested Citation

  • Rémi Jézéquel & Dmitrii M. Ostrovskii & Pierre Gaillard, 2022. "Efficient and Near-Optimal Online Portfolio Selection," Working Papers hal-03787674, HAL.
  • Handle: RePEc:hal:wpaper:hal-03787674
    Note: View the original document on HAL open archive server: https://hal.science/hal-03787674v1
    as

    Download full text from publisher

    File URL: https://hal.science/hal-03787674v1/document
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Markowitz, Harry M, 1991. "Foundations of Portfolio Theory," Journal of Finance, American Finance Association, vol. 46(2), pages 469-477, June.
    2. David P. Helmbold & Robert E. Schapire & Yoram Singer & Manfred K. Warmuth, 1998. "On‐Line Portfolio Selection Using Multiplicative Updates," Mathematical Finance, Wiley Blackwell, vol. 8(4), pages 325-347, October.
    3. Thomas M. Cover, 1991. "Universal Portfolios," Mathematical Finance, Wiley Blackwell, vol. 1(1), pages 1-29, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. R'emi J'ez'equel & Dmitrii M. Ostrovskii & Pierre Gaillard, 2022. "Efficient and Near-Optimal Online Portfolio Selection," Papers 2209.13932, arXiv.org.
    2. Seung-Hyun Moon & Yong-Hyuk Kim & Byung-Ro Moon, 2019. "Empirical investigation of state-of-the-art mean reversion strategies for equity markets," Papers 1909.04327, arXiv.org.
    3. Man Yiu Tsang & Tony Sit & Hoi Ying Wong, 2022. "Adaptive Robust Online Portfolio Selection," Papers 2206.01064, arXiv.org.
    4. James Chok & Geoffrey M. Vasil, 2023. "Convex optimization over a probability simplex," Papers 2305.09046, arXiv.org.
    5. Bin Li & Steven C. H. Hoi, 2012. "On-Line Portfolio Selection with Moving Average Reversion," Papers 1206.4626, arXiv.org.
    6. Ha, Youngmin & Zhang, Hai, 2020. "Algorithmic trading for online portfolio selection under limited market liquidity," European Journal of Operational Research, Elsevier, vol. 286(3), pages 1033-1051.
    7. Roujia Li & Jia Liu, 2022. "Online Portfolio Selection with Long-Short Term Forecasting," SN Operations Research Forum, Springer, vol. 3(4), pages 1-15, December.
    8. Ting-Kam Leonard Wong, 2015. "Universal portfolios in stochastic portfolio theory," Papers 1510.02808, arXiv.org, revised Dec 2016.
    9. Yong Zhang & Xingyu Yang, 2017. "Online Portfolio Selection Strategy Based on Combining Experts’ Advice," Computational Economics, Springer;Society for Computational Economics, vol. 50(1), pages 141-159, June.
    10. Zhengyao Jiang & Dixing Xu & Jinjun Liang, 2017. "A Deep Reinforcement Learning Framework for the Financial Portfolio Management Problem," Papers 1706.10059, arXiv.org, revised Jul 2017.
    11. Shuo Sun & Rundong Wang & Bo An, 2021. "Reinforcement Learning for Quantitative Trading," Papers 2109.13851, arXiv.org.
    12. Esther Mohr & Robert Dochow, 2017. "Risk management strategies for finding universal portfolios," Annals of Operations Research, Springer, vol. 256(1), pages 129-147, September.
    13. Dmitry B. Rokhlin, 2020. "Relative utility bounds for empirically optimal portfolios," Papers 2006.05204, arXiv.org.
    14. Leonard C. MacLean & Yonggan Zhao & William T. Ziemba, 2016. "Optimal capital growth with convex shortfall penalties," Quantitative Finance, Taylor & Francis Journals, vol. 16(1), pages 101-117, January.
    15. Panpan Ren & Jiang-Lun Wu, 2017. "Foreign exchange market modelling and an on-line portfolio selection algorithm," Papers 1707.00203, arXiv.org.
    16. Xingyu Yang & Jin’an He & Hong Lin & Yong Zhang, 2020. "Boosting Exponential Gradient Strategy for Online Portfolio Selection: An Aggregating Experts’ Advice Method," Computational Economics, Springer;Society for Computational Economics, vol. 55(1), pages 231-251, January.
    17. Freund, Yoav & Schapire, Robert E., 1999. "Adaptive Game Playing Using Multiplicative Weights," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 79-103, October.
    18. Parkes, David C. & Huberman, Bernardo A., 2001. "Multiagent Cooperative Search for Portfolio Selection," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 124-165, April.
    19. Purushottam Parthasarathy & Avinash Bhardwaj & Manjesh K. Hanawal, 2023. "Online Universal Dirichlet Factor Portfolios," Papers 2308.07763, arXiv.org, revised Nov 2023.
    20. Vajda, István & Ottucsák, György, 2006. "Empirikus portfólióstratégiák [Empirical portfolio strategies]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(7), pages 624-640.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:wpaper:hal-03787674. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.