Georgia Institute of Technology College of Sciences

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 called 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 the expectation over certain log-concave density in R^d, so in a practical implementation this expectation has to be approximated via sampling, which is computationally challenging. In particular, the fastest known implementation, proposed by Kalai and Vempala in 2002, runs in $ O( d^4 (T+d)^{14} ) $ per round, which rules out any practical application scenario. Proposing a practical algorithm with a near-optimal regret is a long-standing open problem. We propose an algorithm for online portfolio selection with a near-optimal regret guarantee of $ O( d \log(T+d) ) $ and the runtime of only $ O( d^2 (T+d) ) $ per round. In a nutshell, our algorithm is a variant of the follow-the-regularized-leader scheme, with a time-dependent regularizer given by the volumetric barrier for the sum of observed losses. Thus, our result gives a fresh perspective on the concept of volumetric barrier, initially proposed in the context of cutting-plane methods and interior-point methods, correspondingly by Vaidya (1989) and Nesterov and Nemirovski (1994). Our side contribution, of independent interest, is deriving the volumetrically regularized portfolio as a variational approximation of the universal portfolio: namely, we show that it minimizes Gibbs's free energy functional, with accuracy of order $ O( d \log(T+d) ) $. This is a joint work with Remi Jezequel and Pierre Gaillard. 

A Coxeter group is a (not necessarily finite) group given by certain types of generators and relations. Examples of finite Coxeter groups include dihedral groups, symmetric groups, and reflection groups. They play an important role in various areas. In this talk, I will discuss why I am interested in Coxeter groups from a combinatorial perspective - the geometric concepts associated with the finite Coxeter groups form the language of Coxeter matroids, which are generalizations of ordinary matroids. In particular, finite Coxeter groups are related to Coxeter matroids in the same way as symmetric groups are related to ordinary matroids. The main reference for this talk is Chapter 5 of Borovik-Gelfand-White's book Coxeter Matroids. I will only assume basic group theory, but not familiarity with matroids.

The main result in this talk concerns a new fast algorithm to solve a minimal problem with many spurious solutions that arises as a relaxation of a geometric optimization problem. The algorithm recovers relative camera pose from points and lines in multiple views. Solvers like this are the backbone of structure-from-motion techniques that estimate 3D structures from 2D image sequences.   

Our methodology is general and applicable in areas other than computer vision. The ingredients come from algebra, geometry, numerical methods, and applied statistics. Our fast implementation relies on a homotopy continuation optimized for our setting and a machine-learned neural network.

(This covers joint works with Tim Duff, Ricardo Fabbri, Petr Hruby, Kathlen Kohn, Tomas Pajdla, and others. The talk is suitable for both professors and students.)

TBA