Computer Science/Discrete Mathematics Seminar II

We introduce a new algorithm and a new analysis technique that is applicable to a variety of online optimization scenarios, including regret minimization for Lipschitz regret functions, universal portfolio management, online convex optimization and online utility maximization. The algorithm extends a method proposed by Hannan in the 1950's, called `Follow the Leader", and shows a surprising connection to the Newton method for offline optimization. One application from computational finance is universal portfolio management, for which our algorithm combines optimal regret with computational efficiency. For more general settings, our algorithm is the first to achieve optimal regret. The talk is based on work with Amit Agarwal and recent extensions with Amit Agarwal, Adam Kalai, Satyen Kale and Rob Schapire.