Canal-U

Bubeck 3/9 - Some geometric aspects of randomized online decision making

This course is concerned with some of the canonical non-stochastic models of online decision making. These models have their origin in works from the 1950's and 1960's, and went through a resurgence in the mid-2000's due to many applications in the internet economy. This course focuses on a set of challenging conjectures around these models from the 1980's and 1990's. We present a unified approach based on a combination of convex optimization techniques together with powerful probabilistic tools, which will allow us to derive state of the art results in online learning, bandit optimization, as well as some classical online computing problems (k-server and metrical task systems). Special emphasis are given to proper introduction of the mathematical/algorithmic tools: gradient descent, mirror descent (i.e., Riemannian gradient descent), probabilistic embedding of metric spaces, some basic results in convex geometry, etc.