Online Portfolio Selection and Regret Bounds for Follow-the-Regularized-Leader

Abstract

Online portfolio selection is a subfield of online convex optimization. Currently, algorithms tackling the problem of online portfolio selection suffer from problems that make it infeasible in real-world and machine learning applications. Algorithms like Universal Portfolio achieve the optimal regret but have large run-times, whereas algorithms like Follow-the-Leader are relatively easy to implement and have fast run-times, but have suboptimal regret bounds. There are other algorithms which achieve optimal regret bounds and have fast run-times, but also make intractable assumptions that make it hard to apply them in the real world, like bounded gradients. One algorithm that shows promise in having optimal regret bounds, fast run-time, and makes no such assumptions is Follow-the-Regularized-Leader. Currently, it is unknown as to whether or not Follow-the-Regularized-Leader has optimal regret bounds, but if such a fact were proven it would have applications in machine learning theory as an efficient and effective algorithm to solve online portfolio selection problems. In addition, the ideas and techniques used in such a proof would also have wider applications in the general field of online convex optimization as well. This thesis will take a closer look at Follow-the-Regularized-Leader and build on top of current work bounding the regret for the algorithm.