Dmitrii Ostrovskii, USC

Abstract: In the problem of online portfolio selection formulated by Cover (1991), a trader repeatedly allocates her unit wealth over d assets, in each of T rounds, with the goal of maximizing the total return. Cover proposed an algorithm, termed Universal Portfolios, that performs nearly as well as the best static (or offl ine") portfolio in hindsight, with an $O(d \log(T))$ regret guarantee for the log-return. Without imposing any assumptions on the market this guarantee is known to be worst-case optimal, and no other algorithm attaining it has ever been discovered. Unfortunately, Cover's algorithm crucially relies on computing some integrals in ${\bf R}^d$, and these integrals must be approximated to implement it; this results in a prohivitive $O(d^4T^{14})$ per-round runtime for the fastest known implementation due to Kalai and Vempala (2002). We propose a novel algorithm for online portfolio selection that admits the same, up to a constant factor, regret guarantee as Universal Portfolios, yet has a dramatically reduced runtime: in each round, one merely minimizes some self-concordant function, which can be done in $O(d^2T)$ via Newton's method. Surprisingly, the function to be minimized is the observed log-return regularized by its volumetric barrier, a concept first proposed in the context of interior point methods for linear   programming. This is a joint work with Rémi Jézéquel (Inria, ENS) and Pierre Gaillard (Inria, Univ. Grenoble Alpes)

Event Details

0 people are interested in this event

Join Zoom Meeting

Meeting ID: 986 5394 0653
Passcode: 441554

User Activity

No recent activity