Open problem: Fast and optimal online portfolio selection

Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands, pp. 3864–3869

Abstract

Online portfolio selection has received much attention in the COLT community since its introduction by Cover, but all state-of-the-art methods fall short in at least one of the following ways: they are either i) computationally infeasible; or ii) they do not guarantee optimal regret; or iii) they assume the gradients are bounded, which is unnecessary and cannot be guaranteed. We are interested in a natural follow-the-regularized-leader (FTRL) approach based on the log barrier regularizer, which is computationally feasible. The open problem we put before the community is to formally prove whether this approach achieves the optimal regret. Resolving this question will likely lead to new techniques to analyse FTRL algorithms. There are also interesting technical connections to self-concordance, which has previously been used in the context of bandit convex optimization.

Authors 4

1. Tim van Erven Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, Netherlands

2. Dirk van der Hoeven Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Leiden, Netherlands

3. Wojciech Kotłowski

   Poznań University of Technology

   Affiliation as printed

   Poznań University of Technology, Poznan, Poland

4. Wouter M. Koolen

   Centrum Wiskunde & Informatica

   Affiliation as printed

   Centrum Wiskunde & Informatica, Amsterdam, Netherlands