Title:

Self-concordance meets Laplace approximation: 

Fast and optimal algorithm for online portfolio selection

Abstract:

In 1991, Thomas M. Cover introduced a simple and elegant mathematical model for stock trading, which later on came to be known as online portfolio selection (OPS). In each round t = 1, 2, ..., T, the trader selects a portfolio—distribution pt ∈ R+d of the current capital over the set of d assets; then, the adversary generates a vector rt ∈ R+d of returns (i.e., relative prices of the assets), and the trader’s capital is multiplied by the “aggregated return” ptṙt. The model makes no further assumptions on the asset prices; in particular, they are not assumed to be sampled randomly from a distribution; at the same time, it captures the two key properties of the stock market: that it is naturally adversarial, and that money tends to accummulate multiplicatively. In the 30 years that followed, it had received a great deal of attention across several communities.

In the same paper, Cover also proposed an algorithm, termed Universal Portfolios, that admitted a strong performance guarantee: the regret of O(dlog T) against the best portfolio in hindsight, and without any restrictions of returns or portfolios. This guarantee was later on shown to be worst-case optimal; unfortunately, exact computation of a universal portfolio amounts to averaging over a log-concave distribution, which is a challenging task. To address this, Kalai and Vempala (2002) achieved the running time of O(d4T14) per round via sampling techniques. However, with such a running time essentially prohibiting problems of nontrivial size, yet remaining state-of-the-art, the problem of finding an optimal and practical OPS algorithm was left open.

In this talk, after discussing some of the arising technical challenges, I shall present a fast and optimal OPS algorithm that combines regret optimality with the runtime of O(d2T), thus dramatically improving state of the art. Its motivation and analysis turn out to be related to establishing a sharp bound on the accuracy of the Laplace approximation for a log-concave distribution with a polyhedral support; this result is of independent interest, and I shall explore the underlying connection. Finally, I shall present a broader perspective of these ideas beyond online portfolio selection.

Bio:

Dmitrii M. Ostrovskii is an Assistant Professor (RTPC) of Mathematics at the University of Southern California. Dmitrii graduated in 2018, advised by Anatoli Juditsky (University of Grenoble) and Zaid Harchaoui (University of Washington), and actively collaborated with Arkadi Nemirovski (Georgia Tech ISyE) when working on his PhD thesis. Prior to the present appointment, he was a postdoc first at Inria Research Institute in Paris, hosted by Francis Bach and funded by the ERCIM Alain Bensoussan fellowship (2018-2019), and then at USC Viterbi School of Engineering (2019-2021). Dmitrii's interests span several topics at the intersection of optimization theory, mathematical statistics, machine learning, and operations research. In particular, his recent work concerns nonconvex min-max optimization, robust estimation, statistical testing under privacy constraints, and tractable learning algorithms with near-optimal guarantees.